CONSTRUCTION OF OPTIMAL LOCALLY REPAIRABLE CODES
VIA AUTOMORPHISM GROUPS OF RATIONAL FUNCTION
FIELDS

arXiv:1710.09638v1 [cs.IT] 26 Oct 2017

LINGFEI JIN, LIMING MA, AND CHAOPING XING

Abstract. Locally repairable codes, or locally recoverable codes (LRC for short) are
designed for application in distributed and cloud storage systems. Similar to classical
block codes, there is an important bound called the Singleton-type bound for locally
repairable codes. In this paper, an optimal locally repairable code refers to a block
code achieving this Singleton-type bound. Like classical MDS codes, optimal locally
repairable codes carry some very nice combinatorial structures. Since introduction
of the Singleton-type bound for locally repairable codes, people have put tremendous
effort on constructions of optimal locally repairable codes. Due to hardness of this
problem, there are few constructions of optimal locally repairable codes in literature. Most of these constructions are realized via either combinatorial or algebraic
structures.
In this paper, we employ automorphism groups of rational function fields to construct optimal locally repairable codes by considering the group action on the projective lines over finite fields. It turns out that we are able to construct optimal
locally repairable codes with reflexibility of locality as well as smaller alphabet size
comparable to the code length. In particular, we produce new families of q-ary locally repairable codes, including codes of length q + 1 via cyclic groups and codes via
dihedral groups.

1. Introduction
Due to recent applications to distributed and cloud storage systems, a new class of
block codes, i.e., locally repairable codes have been investigated by many researchers
[1, 8, 10, 7, 15, 2, 17, 6, 14, 19, 20]. A locally repairable code is just a block code with
an additional property called locality. As most of classical block codes do not carry
good locality, people have to investigate various constructions of block codes with good
locality.
Block codes with good locality were initially studied in [8, 10], although [10] considered a slightly different definition of locality, under which a code is said to have
information locality. Codes with information locality property were also studied in
[7, 6]. For a locally repairable code C of length n with k information symbols and
locality r (see the definition of locally repairable codes in Section 2.1), it was proved
in [7] that the minimum distance d(C) of C is upper bounded by
 
k
(1)
d(C) 6 n − k −
+ 2.
r
2010 Mathematics Subject Classification: 05B30, 51E22, 11R58, 94B27.
1

2

LINGFEI JIN, LIMING MA, AND CHAOPING XING

The bound (1) is called the Singleton-type bound for locally repairable codes and was
proved by extending the arguments in the proof of the classical Singleton bound on
codes. Like the classical Singleton bound, the Singleton-type bound (1) does not take
into account the cardinality of the code alphabet size q. Augmenting this result, a
recent work [2] established a bound on the distance of locally repairable codes that
depends on q, sometimes yielding better results. A locally repairable code achieving
any of these bound is optimal. However, in this paper, we specifically refer an optimal
locally repairable code to a block code achieving the bound (1).
1.1. Known results. Apparently, construction of optimal locally repairable codes,
i.e., block codes achieving the bound (1) is of both theoretical interest and practical
importance. However, due to hardness of this problem, there are few constructions
available in the literature and hence few classes of optimal locally repairable codes are
known. A class of codes constructed earlier and known as pyramid codes [10] were
shown to be optimal locally repairable codes. In [17], Silberstein et al. proposed a
two-level construction based on the Gabidulin codes combined with a single paritycheck (r + 1, r) code. Another construction in [20] used two layers of MDS codes, a
Reed-Solomon code and a special (r + 1, r) MDS code. A common shortcoming of
these constructions relates to the size of the code alphabet which in all the papers is an
exponential function of the code length, complicating the implementation. There was
an earlier construction of optimal locally repairable codes given in [15] with alphabet
size comparable to code length. However,
 k  the construction in [15] only produced a
specific value of the length n, i.e., n = r (r + 1). Thus, the rate of the code is very
close to 1.
A recent breakthrough construction was given in [19]. This construction naturally
generalizes the Reed-Solomon construction which relies on the alphabet of cardinality
comparable to the code length n. The idea behind the construction is very nice. The
only shortcoming of this construction is the restriction on locality r. Namely, r + 1
must be a divisor of either q − 1 or q, or r + 1 is equal to some special divisors of
q(q − 1).
There are also some existence results given in [15] and [19] with less restriction on
locality r. But both results require large alphabet size which is an exponential function
of the code length.
1.2. Our results and comparison. In this paper, we present a non-trivial generalization of optimal locally repairable codes given in [19] by employing automorphism
groups of rational function fields. This allows reflexibility of locality as well as smaller
alphabet of cardinality comparable to the code length n. More precisely, as long as
there is a subgroup of size r + 1 in the projective general linear group PGL2 (q) (see the
definition of PGL2 (q) in Section 2.3) with (r + 1)|n and n 6 q + 1, we can construct
an optimal locally repairable code of length n and locality r. Thus, to construct optimal locally repairable codes, we need to find all subgroups of PGL2 (q). Fortunately,
subgroups of PGL2 (q) have been completely determined in literature (see Section 2.3).
Thus, we are able to obtain q-ary optimal locally repairable codes of length n and

LRC VIA AUTOMORPHISM GROUP

3

locality r as long as there is a subgroup of size r + 1 in the projective general linear
group PGL2 (q) together with the conditions (r + 1)|n and n 6 q + 1.
However, it is unnecessary to write down all subgroups and provide the corresponding constructions of optimal locally repairable codes. Instead, we present a general
construction for all subgroups of PGL2 (q) in Section 2.3. We then present explicit constructions of optimal locally repairable codes from subgroups of the affine linear group
AGL2 (q) (see definition of AGL2 (q) in Section 2.2). It turns out that the construction
given in [19] can be realized by subgroups of AGL2 (q) under our framework.
In addition, we also present an explicit construction from subgroups of size that
divides q + 1. This construction produces optimal locally repairable codes of length
q + 1 that were not known before. Then in the last section, we give optimal locally
repairable codes from subgroups of a dihedral group that can be viewed as a subgroup
of PGL2 (q).
1.3. Organization of the paper. In Section 2, we introduce some backgrounds for
this paper such as definition of locally repairable codes, automorphism groups of rational function fields, projective general linear groups and their subgroups, Hilbert’s
ramification theory and algebraic geometry codes. Section 3 devotes to a general construction of optimal locally repairable codes from arbitrary subgroups of PGL2 (q). In
Section 4, we present explicit constructions of optimal locally repairable codes from
subgroups of AGL2 (q). In Sections 5 and 6, we give explicit constructions of optimal
locally repairable codes from subgroups of a cyclic group of order q + 1 and dihedral
groups, respectively. In the last section, we conclude the paper by summarizing our
main results of this paper.
2. Preliminaries
In this section, we present some preliminaries on locally repairable codes, automorphism groups of rational function fields, the subgroups of projective general linear
groups PGL2 (q), Hilbert’s ramification theory and algebraic geometry codes.
2.1. Locally repairable codes. Informally speaking, a block code is said with locality
r if every coordinate of a given codeword can be recovered by accessing at most r other
coordinates of this codeword. The formal definition of a locally repairable code with
locality r is given as follows.
Definition 1. Let C ⊆ Fnq be a q-ary block code of length n. For each α ∈ Fq and
i ∈ {1, 2, · · · , n}, define C(i, α) := {c = (c1 , . . . , cn ) ∈ C | ci = α}. For a subset
I ⊆ {1, 2, · · · , n} \ {i}, we denote by CI (i, α) the projection of C(i, α) on I. Then C
is called a locally repairable code with locality r if, for every i ∈ {1, 2, · · · , n}, there
exists a subset Ii ⊆ {1, 2, · · · , n} \ {i} with |Ii | 6 r such that CIi (i, α) and CIi (i, β) are
disjoint for any α 6= β.
Apart from the usual parameters: length, rate and minimum distance, the locality of
a locally repairable code plays a crucial role. In this paper, we always consider locally
repairable codes that are linear over Fq . Thus, a q-ary locally repairable code of length

4

LINGFEI JIN, LIMING MA, AND CHAOPING XING

n, dimension k, minimum distance d and locality r is said to be an [n, k, d]q -locally
repairable code with locality r.
If we ignore the minimum distance of a q-ary locally repairable code, then there is a
constraint on the rate [7], namely,
(2)

r
k
6
.
n
r+1

In this paper, the minimum distance of a locally repairable code is taken into consideration and we always refer to the bound (1). For an [n, k, d]-linear code, k information
symbols can recover the whole codeword. Thus, the locality r is usually upper bounded
by k. If we allow r = k, i.e., there is no constraint on locality, then the bound (1)
becomes the usual Singleton bound that shows constraint on n, k and d only. The
other extreme case is that the locality r is 1. In this case, the locally repairable
code is a repetition code by repeating each symbol twice and the bound (1) becomes
d(C) 6 n − 2k + 2 which shows the Singleton bound for repetition codes.
2.2. Rational function fields and their automorphism groups. Let us introduce
some basic facts of rational function fields over finite fields. The reader may refer to
[4, 18] for the details.
Let F be the rational function field Fq (x) over Fq , where x is transcendental over Fq .
First of all, a well-known fact is that every subfield E of F with Fq E ⊆ F is again
a rational function field, i.e., E = Fq (z) for some element z ∈ F that is transcendental
over Fq (see [18, Proposition 3.5.9]).
For every irreducible polynomial P (x) ∈ Fq [x], we define a discrete valuation νP
which is a map from Fq [x] to Z ∪ {∞} given by νP (0) = ∞ and νP (f ) = a, where f is a
nonzero polynomial and a is the unique nonnegative integer satisfying P a |f but P a+1 ∤
f . This map can be extended to Fq (x) by defining νP (f /g) = νP (f ) − νP (g) for any
two polynomials f, g ∈ Fq [x] with g 6= 0. Apart from the above finite discrete valuation
νP , we have an infinite valuation ν∞ (or νP∞ ) defined by ν∞ (f /g) = deg(g) − deg(f )
for any two polynomials f, g ∈ Fq [x] with g 6= 0. Note that we define deg(0) = ∞. The
set of places of F is denoted by PF .
For each discrete valuation νP (P is either a polynomial or P∞ = ∞), by abuse of
notation we still denote by P the set {y ∈ F : νP (y) > 0}. Then the set P is called
a place of F . If P = x − α, then we denote P by Pα . The degree of the place P is
defined to be the degree of the corresponding polynomial P (x). If P is the infinite
place ∞, then the degree of ∞ is defined to be 1. A place of degree 1 is called rational.
In fact, there are exactly q + 1 rational places for the rational function field F over Fq .
Moreover, the genus of
PF is 0. For a nonzero function z of F , the zero divisor of z is
defined to be (z)0 := P ∈PF ,νP (z)>0 νP (z)P . Similarly, the pole divisor of z is defined
P
to be (z)∞ := − P ∈PF ,νP (z)<0 νP (z)P .
We denote by Aut(F/Fq ) the automorphism group of F over Fq , i.e.,
(3)

Aut(F/Fq ) = {σ : F → F | σ is an Fq -automorphism of F }.

LRC VIA AUTOMORPHISM GROUP

5

It is well known that any automorphism σ ∈ Aut(F/Fq ) is uniquely determined by
σ(x) and given by
(4)

σ(x) =

ax + b
cx + d

for some constants a, b, c, d ∈ Fq with ad − bc 6= 0 (see [4]). Denote by GL2 (q) the
general
linear group of 2 × 2 invertible matrices over Fq . Thus, every matrix A =


a b
∈ GL2 (q) induces an automorphism of F given by (4). Two matrices of
c d
GL2 (q) induce the same automorphism of F if and only if they belong to the same coset
of Z(GL2 (q)), where Z(GL2 (q)) stands for the center {aI2 : a ∈ F∗q } of GL2 (q). This
implies that Aut(F/Fq ) is isomorphic to the projective general linear group PGL2 (q) :=
GL2 (q)/Z(GL2 (q)). Thus, we can identify Aut(F/Fq ) with PGL2 (q).
Consider a subgroup of PGL2 (q):



a b
∗
(5)
AGL2 (q) :=
: a ∈ Fq , b ∈ Fq .
0 1


a b
The group AGL2 (q) is called the affine linear group. Every element A =
∈
0 1
AGL2 (q) defines an affine automorphism σ(x) = ax + b.
2.3. The subgroups of PGL2 (q). As we need subgroups of PGL2 (q) to construct
optimal locally repairable codes in this paper, we have to find out subgroup structures
of PGL2 (q). It is fortunate that all subgroup structures of PGL2 (q) are known. In this
subsection, we present these known results.
By an easy counting argument, we know that the order of GL2 (q) is (q 2 − 1)(q 2 − q).
Thus, the order of PGL2 (q) is q(q 2 − 1). The elements in PGL2 (q) with nonzero square
determinants in F∗q form a subgroup of PGL2 (q) which is called the projective special
linear group and denoted by PSL2 (q).
The structure of subgroups of PSL2 (q) was well known and first found by Moore
[12] and Wiman [23]. The reader may refer to Dickson’s book [5, Chapter XII] for the
details. If char(Fq ) = 2, then PGL2 (q) = PSL2 (q). Hence, we have the following result
(see [11, 16]).
Proposition 2.1. All the nontrivial subgroups of PGL2 (q) for q = 2s are listed as
follows.
(i) For each d|(q ± 1) with d > 2, there is one conjugacy class of q(q ∓ 1)/2 cyclic
subgroups that are isomorphic to Zd of order d.
(ii) For each d|(q ± 1) with d > 2, there is one conjugacy class of q(q 2 − 1)/(2d)
subgroups that are isomorphic to the dihedral group D2d of order 2d.
(iii) For even s, there is one conjugacy class of q(q 2 − 1)/12 subgroups that are
isomorphic to the alternating group A4 .
(iv) For even s, there is one conjugacy class of q(q 2 − 1)/60 subgroups that are
isomorphic to the alternating group A5 .

6

LINGFEI JIN, LIMING MA, AND CHAOPING XING
2

−1)
(v) If q is a power of ℓ, there is one conjugacy class of q(q
subgroups that are
ℓ(ℓ2 −1)
isomorphic to PGL2 (ℓ).
(vi) There are one conjugacy class of q + 1 elementary abelian subgroups of order
q, and (q 2 − 1)/(pk − 1) conjugacy classes of elementary abelian subgroups of
order pv for each positive integer 1 6 v 6 s − 1, where k = gcd(s, v).
(vii) There are (q 2 − 1)ps−v /(pk − 1) conjugacy classes of subgroups of order upv
which are semidirect products of an elementary abelian group of order pv and a
cyclic group of order u, for every positive integer 1 6 v 6 s and every positive
integer u > 2 such that u|(pk − 1), where k = gcd(s, v).
Furthermore, the subgroups in (vi) and (vii) are contained in the subgroups that are
isomorphic to AGL2 (q).

Let q = ps be a power of an odd prime p and let ε be 1 or −1 which is determined by
q ≡ ε (mod 4). The projective general linear group PGL2 (q) is a subgroup of PSL2 (q 2 )
and has a unique normal subgroup PSL2 (q) of index 2. Hence, the subgroup structures
of PGL2 (q) can be determined (see [3, 11]).
Proposition 2.2. All the nontrivial subgroups of PGL2 (q) with q = ps for any odd
prime p are listed as follows.
(i) There are two conjugacy classes of cyclic subgroups of order 2.
(ii) There is one conjugacy class of q(q ∓ ε)/2 cyclic subgroups of size d for every
divisor d > 2 of (q ± ε).
(iii) There are two conjugacy classes of q(q 2 − 1)/6 subgroups that are isomorphic
to the dihedral group D4 (or Klein 4-group).
(iv) There are two conjugacy classes of q(q 2 − 1)/(2d) subgroups that are isomorphic
to the dihedral group D2d of order 2d for every divisor d > 2 of q±ε
.
2
2
(v) There is one conjugacy class of q(q − 1)/(2d) subgroups that are isomorphic to
the dihedral group D2d of order 2d for every divisor d > 2 of (q ± ε) such that
(q ± ε)/d is an odd integer.
(vi) There are q(q 2 − 1)/24 subgroups isomorphic to A4 ; q(q 2 − 1)/24 subgroups
isomorphic to S4 , and q(q 2 − 1)/60 subgroups isomorphic to A5 when q ≡
±1(mod 10).
2 −1)
(vii) There is one conjugacy class of q(q
subgroups that are isomorphic to PSL2 (ℓ),
2
ℓ(ℓ −1)
where q is a power of ℓ.
(viii) PGL2 (q) contains the subgroups PGL2 (ℓ), where q is a power of ℓ.
(ix) PGL2 (q) contains the elementary abelian subgroups of order pv for 1 6 v 6 s.
(x) PGL2 (q) contains the subgroups of order upv that are semidirect products of an
elementary abelian subgroup of order pv with 1 6 v 6 s and a cyclic subgroup
of order u > 1 for every pair (u, v) satisfying u| gcd(q − 1, pv − 1).
2.4. Hilbert’s ramification theory. For any subgroup G of Aut(F/Fq ), let F G be
the fixed subfield of F with respect to G, i.e.,
(6)

F G = {y ∈ F : σ(y) = y for all σ ∈ G}.

By the Galois theory, the extension F/F G is a Galois extension with the Galois group
Gal(F/F G ) = G (see [9, Theorem 11.36]).

LRC VIA AUTOMORPHISM GROUP

7

From the Hurwitz genus formula (see [18, Theorem 3.4.13]), one has
2g(F ) − 2 = |G| · [2g(F G ) − 2] + deg Diff(F/F G ),
where g(F ) stands for the genus of F and Diff(F/F G ) is the different of F/F G . Let Q
be a place of F G and let P1 , · · · , Pt be all the places of F lying over P . The Galois
group G acts transitively on the set {P1 , · · · , Pt } of extensions of Q in F (see [18,
Theorem 3.7.1]). Then the ramification indices ePi (F/F G ) (resp. different exponents
dPi (F/F G )) of Pi |Q are independent of Pi for 1 6 i 6 t, and we can denote them by
eQ (F/F G ) (resp. dQ (F/F G )). Hence, the degree of the different of F/F G can be given
by
deg Diff(F/F G ) =

X

dP (F/F G ) deg(P ) =

P ∈PF

X dQ (F/F G )
· |G| · deg(Q).
G
e
Q (F/F )
Q∈P
FG

The i-th ramification group Gi (P ) of P |Q for each i > −1 is defined by
Gi (P ) = {σ ∈ G : vP (σ(z) − z) > i + 1 for all z ∈ OP },
where OP is the integral ring of P in F and vP is the normalized discrete valuation of F
corresponding to P . In fact, the order of G1 (P ) is a power of char(Fq ), G0 (P )/G1(P ) is a
cyclic group whose order is relatively prime to char(Fq ), Gi+1 (P ) is a normal subgroup
of Gi for each i > 1, and there exists an integer a such that Gi (P ) = {id} for all i > a
(see [18, Proposition 3.8.5]). Moreover, the different exponent dQ (F/F G ) is
G

dQ (F/F ) =

∞
X
i=0

|Gi (P )| − 1



from Hilbert’s Different Theorem [18, Theorem 3.8.7]. Furthermore, we have the following ramification structures for rational function fields (see [9, Theorem 11.92]).
Proposition 2.3. Let F be the rational function field Fq (x) over Fq . Denote by A the
automorphism group Aut(F/Fq ), then the extension F/F A has the following properties.
(i) Every rational place P of F is wildly ramified in F/F A ; G−1 (P ) = G0 (P ) is
the semidirect product of an elementary abelian p-group of order q with a cyclic
group of order q − 1; G1 (P ) is an elementary abelian p-group of order q and
Gi (P ) is trivial for any i > 2. Furthermore, all rational places form a single
orbit of size q + 1 under the group action of A on the set of places of F .
(ii) Every place Q of degree 2 of F is tamely ramified in F/F A ; G0 (Q) is a cyclic
group of order q + 1. Furthermore, all places of degree 2 form a single orbit of
size (q 2 − q)/2 under the group action of A on the set of places of F .
(iii) Other places of F are unramified in F/F A .
In fact, one can explicitly compute all the ramification groups of rational places and
places of degree 2. For instance, let P∞ be the pole
G−1 (P∞ ) = G0 (P∞ ) =
of x. Then

1 b
AGL2 (q) and G1 (P∞ ) is isomorphic to the group
: b ∈ Fq ≃ (Fq , +).
0 1

8

LINGFEI JIN, LIMING MA, AND CHAOPING XING

2.5. Algebraic geometry codes. In this subsection, we introduce a modification
of the algebraic geometry codes. The reader may refer to [13, 21, 22] for details on
algebraic geometry codes.
Let F/Fq be the rational function field. Let P = {P1 , . . . , Pn } be a set of n distinct
rational places of F . For a divisor G with 0 < deg(G) < n and supp(G) ∩ P = ∅, the
algebraic geometry code is defined to be
(7)

C(P, G) := {(f (P1 ), . . . , f (Pn )) : f ∈ L(G)}.

Then C(P, G) is an [n, deg(G) + 1, n − deg(G)]-MDS code. If V is a subspace of L(G),
we can define a subcode of C(P, G) by
(8)

C(P, V ) := {(f (P1), . . . , f (Pn )) : f ∈ V }.

The code C(P, V ) is usually no longer an MDS code, but the minimum distance is still
lower bounded by n − deg(G).
For the purpose of our paper, we need to modify the above construction. We can
remove the condition that supp(G) ∩ P = ∅. Assume that G is a divisor of F and let
mi = νPi (G). Choose a local parameter πi of Pi for each i ∈ {1, 2, · · · , n}. Then for
any nonzero function f ∈ L(G), we have νPi (πimi f ) = mi + νPi (f ) > mi − νPi (G) = 0.
Define a modified algebraic geometry code as follows
(9)

C(P, G) := {((π1m1 f )(P1 ), . . . , (πnmn f )(Pn )) : f ∈ L(G)}.

We claim that C(P, G) is still an [n, deg(G) + 1, n − deg(G)]-MDS code in this case.
It is sufficient to show that the Hamming weight of the codeword

(π1m1 f )(P1 ), . . . , (πnmn f )(Pn )

is at least n − deg(G) for every nonzero function f ∈ L(G). Let IPbe the subset
of {1, 2, .P
. . , n} such that (πimi f )(Pi ) = 0. Then we have f ∈ L(G − i∈I Pi ). Thus,
deg(G− i∈I Pi ) > 0, i.e., |I| 6 deg(G). This gives a lower bound n−|I| > n−deg(G)
on the Hamming weight of the codeword. Now, for a subspace V of L(G), we can define
a subcode of C(P, G) by

(10)

C(P, V ) := {((π1m1 f )(P1), . . . , (πnmn f )(Pn )) : f ∈ V }.

Again, the minimum distance of C(P, V ) is lower bounded by n − deg(G).
3. General construction of optimal LRC codes
The idea of our construction works as follows. Let F/Fq be the rational function field.
Let G be a subgroup of Aut(F/Fq ) of order r + 1. Then there is a subfield E of F such
that F/E is a Galois extension with the Galois group Gal(F/E) = G. Now assume that
Q1 , Q2 , . . . , Qm are rational places of E and they are all splitting completely in F/E.
Let Pi,1 , Pi,2 , . . . , Pi,r+1 denote the r + 1 rational places of F that lie over Qi for all 1 6
i 6 m. Put n = (r +1)m and put P = {Pij }16i6m,16j6r+1. Choose a divisor G of degree
k + t − 2 with k = rt for some integer 1 6 t 6 m, a function z of E with deg(z)∞ = 1
(here (z)∞ is considered as a divisor of E) and a function
x of F with deg(x)∞ = 1.

Pr−1 Pt−1
j
i
x ; aij ∈ Fq } is an optimal q-ary
Then the code {(f (P ))P ∈P : f ∈ i=0
j=0 aij z
[n, k, d]-locally repairable code with locality r, k = rt and d = n − k −

k
r

+ 2 (see the

LRC VIA AUTOMORPHISM GROUP

9

proof of Theorem 3.1 below). Apparently, to construct optimal locally repairable codes
using this idea, one has to analyze the splitting behavior of places of E in F . In order to
do so, we need to have explicit structure of the subgroup G. As all subgroup structures
are given in Propositions 2.1 and 2.2, we are able to produce optimal locally repairable
codes from an arbitrary subgroup of PGL2 (q). On the other hand, it is unnecessary
to provide explicit constructions from all subgroups of PGL2 (q) one by one. Instead,
in this section, we give a general construction of optimal locally repairable codes for
all the subgroups of automorphism groups of rational function fields over finite fields
by estimating the number of ramified rational places in F . Explicit constructions
corresponding to subgroups of the affine linear group AGL2 (q), the cyclic group of size
q + 1 and the dihedral groups D2(q±1) for even q are provided in the following sections.
Proposition 3.1. Assume that there is a subgroup of PGL2 (q) of order r + 1 with
1 6 r 6 3q . Put n = m(r + 1) for any positive integer m 6 q+1−2r
. Then, for any
r+1
integer t with 1 6 t 6 m, there exists an optimal q-ary [n, k, d]-locally repairable code
with locality r, k = rt and d = n − k − kr + 2.
Proof. Let F/Fq be the rational function field. Then there exists a subgroup G of
Aut(F/Fq ) of order r + 1. Denote by {R1 , R2 , . . . , Rs } the set of rational places of F
which are ramified in F/F G . By the Hurwitz genus formula, we have
G

2g(F ) − 2 > (r + 1)(2g(F ) − 2) +

s
X

dRi (F/F G ) deg(Ri ) > −2(r + 1) + s.

i=1

This gives s 6 2r. Hence, there are at least q + 1 − s > q + 1 − 2r > m(r + 1) rational
places of F which are unramified in F/F G . As a rational place of F is either ramified
or splitting completely in F/F G , there are m rational places {Q1 , Q2 , · · · , Qm } of F G
which split completely in F/F G . Denote by P = {P1 , P2 , . . . , Pn } the set of rational
places of F lying over {Q1 , Q2 , · · · , Qm }.
Let P∞ be a rational place of F such that P∞ ∈
/ P. Then there exists an element
x ∈ F such that (x)∞ = P∞ and F = Fq (x) (see [18, Proposition 1.6.6]). Let Q∞ be the
restriction of P∞ to F G . Similarly, there exists an element z ∈ F G such that (z)∞ = Q∞
in F G and F G = Fq (z). Thus, supp((z)∞ ) ∩ P = ∅. Note that as a divisor of F G , we
have (z)∞ = Q∞ . However, as a divisor of F , we have deg(z)∞ = [F : F G ] = r + 1.
For t > 1, consider the set of functions
( r−1 t−1
!
)
X X
V :=
aij z j xi ∈ F : aij ∈ Fq .
i=0

j=0

First of all, as [Fq (x) : Fq (z)] = r + 1, the set {1, x, . . . , xr−1 } is linearly independent
over Fq (z). Thus, the vector space V over Fq has dimension rt. Consider the subcode
of the algebraic geometry code
C(P, V ) = {(f (P1 ), . . . , f (Pn )) : f ∈ V }.
Then we claim that C(P, V ) is an optimal [n, k, d]-locally repairable code with locality
r, k = rt and d = n − k − kr + 2.

10

LINGFEI JIN, LIMING MA, AND CHAOPING XING

Firstly, it is clear that C(P, V ) is an Fq -linear code of length n. For every nonzero
function f ∈ V , the pole divisor of f is at most (t − 1)(z)∞ + (r − 1)(x)∞ . Thus,
deg(f )∞ 6 (t − 1)(r + 1) + (r − 1) = (r + 1)t − 2 (note that we consider divisors of F
here, and hence deg(z)∞ = [F : F G ] = r + 1). Thus, f has at most (r + 1)t − 2 zeros.
This implies that the Hamming weight of (f (P1 ), . . . , f (Pn )) is at least n − rt − t + 2 =
n − k − kr + 2 > 0. Therefore, the dimension of C(P, V ) is k = rt and d > n − k − kr + 2.
By the Singleton-type bound (1), we obtain d = n − k − kr + 2 if C(P, V ) has locality
r.
Finally let us prove that C(P, V ) has locality r. We claim that x(Pα ) 6= x(Pβ ) for
any two different rational places Pα , Pβ ∈ P. Otherwise, x − c would have two zeros Pα
and Pβ , where c = x(Pα ) = x(Pβ ) ∈ Fq . Thus, deg(x − c)0 > 2. This is a contradiction
to the fact that deg(x − c)0 = deg(x − c)∞ = deg(x)∞ = 1.
Let Aℓ be the set of rational places of F which lie over Qℓ for 1 6 ℓ 6 m. Suppose
that the erased symbol of the codeword is cα = f (Pα ), where Pα ∈ Aℓ . Put bi =
Pt−1
j
G
j=0 aij z (Pα ) for all 0 6 i 6 t − 1. As z is a function of F , we have z(Pβ ) = z(Pα )
for all β ∈ Aℓ . Hence, for any Pβ ∈ Aℓ , we have
!
r−1
t−1
r−1
X
X
X
f (Pβ ) =
aij z j (Pβ ) xi (Pβ ) =
bi xi (Pβ ).
i=0

j=0

i=0

Define the decoding polynomial δ(x) =
δ(x)(Pβ ) =

Pr−1

r−1
X

i=0

bi xi . Then

bi xi (Pβ ) = f (Pβ ).

i=0

Since δ(x) is a polynomial of degree at most r − 1 and {x(Pβ )}β∈Aℓ \{Pα } are pairwise
distinct, it can be interpolated from these r symbols cβ = f (Pβ ) for Pβ ∈ Aℓ \ {Pα }.
Hence, the erased symbol cα = δ(x)(Pα ) can be recovered by the Lagrange interpolation. This completes the proof.

Combining Proposition 3.1 with Propositions 2.1 and 2.2, we immediately obtain
the following optimal locally repairable codes.
Theorem 3.2. If a positive integer r 6 3q satisfies
one of the following conditions, then

q+1−2r
that is divisible by r + 1 and any integer
for any positive integer n 6 (r + 1) r+1
n
t with 1 6 t 6 r+1 , there exists an optimal q-ary [n, k, d]-locally repairable code with
locality r, k = rt and d = n − k − kr + 2.
(i) r + 1 is a divisor of q − 1;
(ii) r + 1 is a divisor of q;
(iii) r + 1 = upv , where u > 2, v > 1 and u is a common divisor of q − 1 and pv − 1;
(iv) r + 1 is a divisor of q + 1;
for odd q;
(v) r + 1 = 2h, where h > 2 is a divisor of q ± 1 for even q or q±1
2
(vi) r + 1 = ℓ(ℓ2 − 1), where q is a power of ℓ;
(vii) r + 1 = ℓ(ℓ2 − 1)/2, where q is odd and q is a power of ℓ;
(viii) r + 1 = 12, if q is an even power of 2 or q is odd.
(ix) r + 1 = 24, if q is odd;

LRC VIA AUTOMORPHISM GROUP

11

(x) r + 1 = 60, if q is an even power of 2 or q ≡ ±1(mod 10).
Remark 1. The advantage of Theorem 3.2 is that one can produce optimal q-ary locally
repairable codes without knowing explicit structures of subgroups of PGL2 (q), while
the disadvantage of Theorem 3.2 is that it is an existence result.
Remark 2. For a subgroup G of Aut(F/Fq ) of order r + 1, let s > 1 be the number
of rational places of F which are ramified in F/F G (see [9, Theorem 11.91]). Then,
the length n of the optimal locally repairable codes can be as large as q + 1 − s. In
the following sections, by analyzing explicit subgroup structures, we will construct the
optimal locally repairable codes explicitly.
Let us look at some examples by plugging some values of q, r, t and n in Theorem
3.2.
Example 3.3.
(i) Let q = 27. Then for r ∈ {1, 2, 3,5, 6, 8},
 there is a subgroup of
and any integer t with
PGL2 (27) of order r + 1. Thus, for n = (r + 1) 28−2r
r+1
 28−2r 
1 6 t 6 r+1 , there exists an optimal q-ary [n, k, d]-locally repairable code
with locality r, k = rt and d = n−k − kr +2. For instance, for r = 2, there exists
an optimal 27-ary [24, 2t, 26 − 3t]-locally repairable code with locality 3 for any
1 6 t 6 8. If we take r = 3, we obtain an optimal 27-ary [20, 3t, 22 − 4t]-locally
repairable code with locality 3 for any 1 6 t 6 5.
(ii) Let q = 64. Then for r ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 15, 17,
20},there is a
 65−2r
subgroup of PGL2 (64) of order r + 1. Thus, for n = (r + 1) r+1 and any


, there exists an optimal q-ary [n, k, d]-locally
integer t with 1 6 t 6 65−2r
r+1
repairable code with locality r, k = rt and d = n − k − kr + 2. For instance,
for r = 3, there exists an optimal 64-ary [56, 3t, 58 − 4t]-locally repairable code
with locality 3 for any 1 6 t 6 14. If we let r = 5, then there exists an optimal
64-ary [54, 5t, 56 − 6t]-locally repairable code with locality 5 for any 1 6 t 6 9.
By Proposition 3.1, Propositions 2.1 and 2.2, we can give a result on some small
locality for locally repairable codes over finite fields of small characteristics.
Corollary 3.4. If a pair (q, r) of positive integers
satisfies
 q+1−2r
 one of the following conditions, then for any positive integer n 6 (r + 1) r+1
that is divisible by r + 1 and
n
any integer t with 1 6 t 6 r+1 , there exists an optimal q-ary [n, k, d]-locally repairable
code with locality r, k = rt and d = n − k − kr + 2.
(i)
(ii)
(iii)
(iv)

q
q
q
q

= 2s
= 3s
= 4s
= 5s

with
with
with
with

s>4
s>4
s>3
s>3

and
and
and
and

r
r
r
r

∈ {1, 2, 5};
∈ {1, 2, 3, 5, 11, 23};
∈ {1, 2, 3, 4, 5, 9, 11};
∈ {1, 2, 3, 4, 5, 9, 11, 19, 23}.

Proof. (i) follows from Proposition 3.1 and the fact that PGL2 (q) contains the group
PGL2 (2) and PGL2 (2) contains subgroups of order 2, 3 and 6.
(ii) For q = 3s with s > 4, 2|(q − 1), 3|q, 4|(q − 1) for even s or 4|(q + 1) for odd s.
Thus, there is a subgroup of PGL2 (q) of order r + 1 for r ∈ {1, 2, 3}. There is also an

12

LINGFEI JIN, LIMING MA, AND CHAOPING XING

affine subgroup of order 6 since 2|(3 − 1) from Theorem 3.2(iii). The order of A4 is 12,
and the order of PGL2 (3) is 24.
(iii) There is a subgroup of PGL2 (q) of order r + 1 for r ∈ {1, 2, 3, 4, 5, 9, 11} since
2|q, 3|(q − 1), 4|q, 5|(q − 1) for even s or 5|(q + 1) for odd s; the order of PGL2 (2) is
6; there is a dihedral subgroup of order 10 from Theorem 3.2(v); and the order of A4
is 12.
(iv) There is a subgroup of PGL2 (q) of order r + 1 for r ∈ {1, 2, 3, 4, 5, 9, 11, 19, 23}
since both 2 and 4 are divisors of q − 1; both 3 and 6 are divisors of q − 1 for even s or
q + 1 for odd s; 5|q; there are affine subgroups of order 10 and 20, respectively, since
2|(5 − 1) and 4|(5 − 1) from Theorem 3.2(iii); the order of A4 is 12; and the order of
S4 is 24.

4. Explicit construction via affine subgroups
In the previous section, we provided a construction for arbitrary subgroups of PGL2 (q)
by estimating the number of ramified rational places. From this section onwards, we
will consider some particular subgroups and analyze ramification of rational places.
In this section, we will construct optimal locally repairable codes from subgroups of
AGL2 (q). It turns out that the optimal locally repairable codes constructed in [19] are
examples in this section.
Let Fq be the finite field with q = ps elements and let F be the rational function field
Fq (x) over Fq . The proof of the following proposition provides explicit group structures
of affine linear group AGL2 (q).
Proposition 4.1. Let q = ps . Let v be an integer with 0 6 v 6 s and let u be a positive
integer satisfying u|(q − 1) and u|(pv − 1). Then there is a subgroup G of AGL2 (q) of
order upv .
Proof. If u is a divisor of q − 1, then there exists a subgroup H of the multiplicative
group F∗q of order u. As u|(pv −1), the field Fp (H) is contained in Fpv . Put ℓ = min{t >
0 : u|(pt − 1)}. Then we have Fp (H) = Fpℓ and ℓ| gcd(v, s).
Let W be a vector subspace of Fq over Fpℓ with dimension v/ℓ. Put



a b
(11)
G :=
: a ∈ H, b ∈ W .
0 1
Then it is easy to verify that G is a subgroup of AGL2 (q) of order upv .



The ramification information of the F/F G are provided in the following proposition.
In particular, the number of ramified rational places of F in the extension F/F G can
be determined.
Proposition 4.2. Let q = ps . Let G be a subgroup of AGL2 (q) with order upv that is
defined in Equation (11). Then the extension F/F G has the following properties.
(i) [F : F G ] = upv .
(ii) The infinity place P∞ of F is totally ramified in F/F G with ramification index
eP∞ (F/F G ) = upv and different exponent dP∞ (F/F G ) = upv + pv − 2, where
P∞ is the unique pole place of x. There is a rational place of F G which splits

LRC VIA AUTOMORPHISM GROUP

13

into pv rational places {P1 , P2 , · · · , Ppv } of F , each place Pi has ramification
index ePi (F/F G ) = u and different exponent dPi (F/F G ) = u − 1 in F/F G .
Furthermore, there are (q − pv )/(upv ) rational places of F G that split completely
in F/F G .
(iii) The unique zero place of x is ramified in F/F G with ramification index u. Hence,
P0 ∈ {P1 , P2 , · · · , Ppv }.
(iv) Other places of F are unramified in F/F G .
Proof. (i) is clear.
To prove (ii), let A denote the automorphism group Aut(F/Fq ). From Proposition
2.3 and the paragraph after Proposition 2.3, we know that the inertia group of the
infinite place P∞ in F/F A is AGL2 (q). Thus, the infinite place P∞ is totally ramified
in F/F AGL2 (q) . Since G is a subgroup of AGL2 (q), P∞ is totally ramified in F/F G , i.e.,
eP∞ (F/F G ) = upv . It is straightforward to verify that the orders of ramification groups
of P∞ in F/F G are given by
|G0 (P∞ )| = upv , |G1 (P∞ )| = pv and |Gi (P∞ )| = 1 for i > 2.
Hence, the different exponent is dP∞ (F/F G ) = upv + pv − 2 from Hilbert’s Different
Theorem. Assume that Q1 , · · · , Qk are the remaining ramified places of F G in F/F G
with ramification indices ei and different exponents di for 1 6 i 6 k. Form the Hurwitz
genus formula, one has
(12)

2g(F ) − 2 = |G| · [2g(F G ) − 2] + upv + pv − 2 +

k
X
di
i=1

ei

· |G|.

Since any fixed subfield of the rational function field is again P
a rational function field,
G
we have g(F ) = g(F ) = 0. Hence, it follows from (12) that ki=1 deii = u−1
. If u = 1,
u
then k = 0. Otherwise we must have k = 1 and e1 = u, and the place Q1 splits into pv
rational places in F . Then there are q − pv rational places of F which are unramified
in F/F G . Hence, there are (q − pv )/(upv ) rational places of F G that split completely
in F/F G .
Again, it is straightforward to verify that the orders of ramification groups of P0 in
F/F G are given by |G0 (P0 )| = u, and |Gi (P0 )| = 1 for i > 1. Thus, P0 is ramified in
F/F G with ramification index u. This proves (iii).
(iv) follows from the proof of (ii).

Now we can provide explicit constructions of optimal locally repairable codes from
the subgroups of AGL2 (q).
Theorem 4.3. Let q = ps . Let v be a positive integer less than or equal to s. Put
r = pv − 1 and n = m(r + 1) for any positive integer m 6 q/(r + 1). Then for any
integer t with 1 6 t 6 m, there exists an optimal [n, k, d]q -locally repairable code with
locality r, k = rt and d = n − k − kr + 2.
Proof. Let F be the rational function field Fq (x) and let P∞ be the infinite place of F ,
i.e., (x)∞ = P∞ . Let G be the subgroup of AGL2 (q) with order r + 1 = pv constructed
from Equation (11). Then by Proposition 4.2, except for P∞ all other q rational places

14

LINGFEI JIN, LIMING MA, AND CHAOPING XING

of F split completely. Denote by P a set of m(r + 1) rational places of F that lie over
m rational places of F G .
Let Q∞ be the place of F G that lies under P∞ and choose an element z ∈ F G such
that (z)∞ is equal to Q∞ as a divisor of F G . Thus, (z)∞ is equal to (r + 1)P∞ as a
divisor of F .
For t > 1, consider the set of functions
!
)
( r−1 t−1
X X
V :=
aij z j xi : aij ∈ Fq .
i=0

j=0

Then by mimicking the proof of Proposition 3.1, one can show that the code C(P, V )
is an optimal [n, k, d]q -locally repairable code with locality r, k = rt and d = n − k −
k
+ 2.

r
Q
Remark 3. In the proof of Theorem 4.3, one can choose the function z to be b∈W (x+b),
where W is the Fp -vector space of dimension v used to define G in Equation (11). Thus,
Theorem 4.3 provides the same construction as the one using additive subgroups in
[19, Proposition 3.2].
In Theorem 4.3, we make use of a subgroup G of AGL2 (q) that is isomorphic to an
additive subgroup of Fq . The following theorem will use a subgroup G of AGL2 (q) that
is isomorphic to a multiplicative subgroup of F∗q .
Theorem 4.4. Let r be a positive integer with (r +1)|(q −1). Put n = m(r +1) for any
positive integer m 6 (q −1)/(r +1). Then for any integer t with 1 6 t 6 m, there exists
an optimal [n, k, d]q -locally repairable code with locality r, k = rt and d = n − k − kr + 2.
Proof. Let F be the rational function field Fq (x) and let P∞ be the pole place of x,
i.e., (x)∞ = P∞ . Let G be the subgroup of AGL2 (q) with order r + 1 constructed from
Equation (11). Then by Proposition 4.2, except for P∞ and the zero of x, all other
q − 1 rational places of F split completely. Denote by P a set of m(r + 1) rational
places of F that lie over m rational places of F G .
Let Q∞ be the place of F G that lies under P∞ and choose an element z ∈ F G such
that (z)∞ is equal to Q∞ as a divisor of F G . Thus, (z)∞ is equal to (r + 1)P∞ as a
divisor of F .
For t > 1, consider the set of functions
( r−1 t−1
!
)
X X
V :=
aij z j xi : aij ∈ Fq .
i=0

j=0

Then by mimicking the proof of Proposition 3.1, one can show that the code C(P, V )
is an optimal [n, k, d]q -locally repairable code with locality r, k = rt and d = n − k −
k
+ 2.

r
Q
Remark 4. In the proof of Theorem 4.3, one can choose the function z to be a∈H ax =
xr+1 , where H is the subgroup of F∗q used to define G in Equation (11). Thus, Theorem
4.4 provides the same construction as the one using multiplicative subgroups in [19,
Proposition 3.2].

LRC VIA AUTOMORPHISM GROUP

15

Now we consider subgroups of AGL2 (q) that mix additive subgroups of Fq and multiplicative subgroups of F∗q .
Theorem 4.5. Let u > 2 be a common divisor of q − 1 and pv − 1 for some 1 6 v 6 s.
Let r be a positive integer such that r + 1 = upv . Put n = m(r + 1) for any positive
integer m 6 (q − pv )/(upv ). Then for any integer t with 1 6 t 6 m, there exists an
optimal [n, k, d]q -locally repairable code with locality r, k = rt and d = n − k − kr + 2.
One can imitate the proof of Theorem 4.3 or Theorem 4.4 by considering a subgroup
of AGL2 (q) of size upv defined in Equation (11). We skip the details.
Example 4.6.
(i) Let q = 27. If we let r = 2 and m = 9 in Theorem 4.3, then we
can explicitly construct an optimal 27-ary [27, 2t, 29−3t]-locally repairable code
with locality 2 for any 1 6 t 6 9. Note that the code length gets enlarged compared with Example 3.3(i). This is because we know the ramification situation.
If we let r = 12 and m = 2 in Theorem 4.4, then we can explicitly construct an
optimal 27-ary [26, 12t, 28 − 13t]-locally repairable code with locality 12 for any
1 6 t 6 2. If we let r = 5 and m = 4 in Theorem 4.5, then we can explicitly
construct an optimal 27-ary [24, 5t, 26 − 6t]-locally repairable code with locality
5 for any 1 6 t 6 4.
(ii) Let q = 64. If we let r = 3 and m = 16 in Theorem 4.3, then we can explicitly
construct an optimal 64-ary [64, 3t, 66 − 4t]-locally repairable code with locality
3 for any 1 6 t 6 16. Note that the code length gets enlarged compared with
Example 3.3(ii). If we let r = 8 and m = 7 in Theorem 4.4, then we can
explicitly construct an optimal 64-ary [63, 8t, 65 − 9t]-locally repairable code
with locality 8 for any 1 6 t 6 7. If we let r = 11 and m = 5 in Theorem 4.5,
then an optimal 64-ary [60, 11t, 62 − 12t]-locally repairable code with locality
11 for any 1 6 t 6 5 can be constructed.
5. Explicit construction of LRC codes of length n = q + 1
In this section, we give an explicit construction of optimal locally repairable codes
of length n = q + 1 via the subgroups of a cyclic group of order q + 1 of Aut(F/Fq ).
First of all, we provide an explicit characterization of the fixed subfields of the rational
function field Fq (x) with respect to the subgroups of a cyclic group of order q + 1.
Lemma 5.1. Let F be the rational function field Fq (x). Let f (x) be a quadratic primitive polynomial
x2 + ax + b ∈ Fq [x] of order q 2 − 1. Then its companion matrix

0
1
Af =
generates a cyclic group of order q + 1 in PGL2 (q). Furthermore,
−b −a
P
let G be a subgroup of hAf i. Then we have F G = Fq (Tr(x)), where Tr(x) = τ ∈G τ (x).
Proof. Let us first prove that Af has order q + 1 in PGL2 (q).
2
q
Let α and αq be the two distinct
roots
 of f (x) in Fq2 . Then ord(α) =
 q −1, α+ α =

α 0
1 1
. It is
−a and αq+1 = b. Put P =
. Then we have P −1 Af P =
α αq
0 αq
easy to verify that q + 1 is the smallest positive integer k such that αk = αqk = c for

16

LINGFEI JIN, LIMING MA, AND CHAOPING XING


α 0
some c ∈
Thus,
has order q + 1 and hence Af generates a cyclic group
0 αq
of order q + 1 in PGL2 (q).
Let ak = (αqk − αk )/(αq − α). Then we obtain
 k

α
0
k
· P −1
Af = P ·
0 αqk


1
αq+k − αqk+1
αqk − αk
=
αq − α αq+k+1 − αq(k+1)+1 αq(k+1) − αk+1


−bak−1 ak
=
.
−bak ak+1
F∗q .



Moreover, it is easy to see that ak satisfies the following recursive formula
ak+2 + aak+1 + bak = 0 with a0 = 0, a1 = 1.

Let σ be the automorphism of Fq (x) corresponding to the matrix Af , i.e., σ(x) =
1/(−bx − a). Then the order of σ is q + 1. For 1 6 k 6 q, we have
−bak−1 x + ak
(13)
σ k (x) =
.
−bak x + ak+1
It is easy to verify that ak = 0 if and only if αk = αqk , i.e., (q + 1)|k. Hence, ak 6= 0
for all 1 6 k 6 q. By a direct computation, one has
aj+1
ak+1
6=
bak
baj
for all 1 6 k 6= j 6 q.
P
Let G be a subgroup of hσi. Then Tr(x) = τ ∈G τ (x) ∈ F G and deg(Tr(x))∞ = |G|.
By [18, Theorem 1.4.10], we have
|G| = [F : F G ] 6 [F : Fq (Tr(x))] = deg(Tr(x))∞ = |G|.

Hence, F G = Fq (Tr(x)).


G

The ramification properties of F/F are given in the following proposition and the
number of the ramified rational places of F in F/F G can be completely determined.
Proposition 5.2. Let σ be an automorphism of F of corresponding to the matrix Af
defined in Lemma 5.1. Let G be a subgroup of hσi of order r +1 such that (r +1)|(q +1).
Then the extension F/F G has the following properties.
(i) [F : F G ] = r + 1.
(ii) There is a unique place Q of degree 2 of F which is totally ramified in F/F G
with ramification index eQ (F/F G ) = r+1 and different exponent dQ (F/F G ) = r.
There are exactly (q + 1)/(r + 1) rational places of F G which split completely in
F/F G .
(iii) All other places of F are unramified in F/F G .
Proof. From Proposition 2.3, there is a unique place Q of degree 2 of F which is totally
ramified in F/F hσi with ramification index eQ (F/F hσi ) = q + 1. Since G is a subgroup
of hσi, then Q is totally ramified in F/F G with ramification index eQ (F/F G ) = r + 1.

LRC VIA AUTOMORPHISM GROUP

17

It is easy to see that r + 1 is relative prime to the characteristic of Fq , i.e., Q is tamely
ramified in F/F G . Hence, the different exponent dQ (F/F G ) = eQ (F/F G ) − 1 = r.
From the Hurwitz genus formula, we have
2g(F ) − 2 = |G|(2g(F G ) − 2) + deg Diff(F/F G ).
It follows that deg Diff(F/F G ) = 2r = deg(rQ). Hence, Q is the unique ramified place
in F/F G . Then there are q + 1 rational places of F which are unramified in F/F G .
Hence, there are exactly (q + 1)/(r + 1) rational places of F G which split completely
in F/F G .

Now we can provide an explicit construction of optimal locally repairable codes with
length n = q + 1 from the subgroups of a cyclic subgroup of order q + 1 of Aut(F/Fq ).
Theorem 5.3. Let r be a positive integer such that (r +1)|(q +1). Put n = m(r +1) for
. Then for any integer t with 1 6 t 6 m, there exists an
any positive integer m 6 q+1
r+1
optimal q-ary [n, k, d]-locally repairable code with locality r, k = rt and d = n−k− kr +2.
Proof. We prove the result only for m = q+1
. This case gives the largest length
r+1
n = q + 1. The reader may refer to Proposition 3.1 for the proof of the case where
m < q+1
.
r+1
Let F be the rational function field Fq (x) and let G be a subgroup of the cyclic
group of order q + 1 defined in Lemma 5.1 and Proposition 5.2. In fact, there are
exactly m rational places {Q1 , · · · , Qm } of F G which split completely in F/F G . Let
Aj = {P(j−1)(r+1)+1 , · · · , Pj(r+1) } be the set of rational places of F lying over Qj for
1 6 j 6 m. Choose an element z of F G such that (z)∞ = Q1 in F G . Then we must
have F G = Fq (z). It is easy to see that (z)∞ = P1 + · · · + Pr+1 in F and z is a
constant function on each Aj since z(P(j−1)(r+1)+ℓ ) = z(Qj ) for every 1 6 ℓ 6 r + 1 and
2 6 j 6 m.
Choose an element y ∈ F such that (y)∞ = Pr+2 and F = Fq (y). For t > 1, consider
the set of functions
( r−1 t−1
!
)
X X
i
j
V :=
aij z y : aij ∈ Fq .
i=0

j=0

Let G = (t − 1)(z)∞ + (r − 1)(y)∞ = (t − 1)(P1 + · · · Pr+1 ) + (r − 1)Pr+2 . Then V is a
subspace of the Riemann-Roch space L(G).
Let mi = νPi (G), then m1 = m2 = · · · = mr+1 = t − 1, mr+2 = r − 1 and
mr+3 = · · · = mn = 0. Put π1 = · · · = πr+1 = 1/z and πr+2 = 1/y. Consider the
subcode of the modified algebraic geometry code
m

r+2
C(P, V ) = {((π1m1 f )(P1 ), . . . , (πr+2
f )(Pr+2 ), f (Pr+3), . . . , f (Pn ))) : f ∈ V }.

It is easy to see that the code C(P, V ) is an [n, k, d] code with k = rt and d >
n − k − kr + 2.
It remains to prove that the code C(P, V ) has locality r. Denote by (c1 , c2 , . . . , cn )
Pr−1
mr+2
m1
the
codeword
((π
f
)(P
),
.
.
.
,
(π
f
)(P
),
f
(P
),
.
.
.
,
f
(P
))
for
some
f
=
1
r+2
r+3
n
1
r+2
i=0
P

t−1
j
i
y ∈ V with aij ∈ Fq . Suppose that the erased symbol of the codeword
j=0 aij z

18

LINGFEI JIN, LIMING MA, AND CHAOPING XING

is cα = (παmα f )(Pα ), where Pα ∈ Ah with 1 6 h 6 m. For 3 6 h 6 m, the locality
property follows from the proof of Proposition 3.1. For h = 1, define the decoding
polynomial
r−1 X
t−1
r−1
X
X
t−1 j
i
δ(y) =
ai,j π1 z (Pα )y =
ai,t−1 y i .
i=0 j=0

i=0
t−1
(π1 f )(Pα ) =

δ(y)(Pα) can be recovered
Then as we have shown in Proposition 3.1,
t−1
from the other r symbols cβ = (π1 f )(Pβ ) for Pβ ∈ A1 \ {Pα } by the Lagrange interPt−1
P
j
j
polation. For h = 2, since t−1
j=0 aij z (Pr+2 )
j=0 aij z is constant on A2 , we let bi =
for 0 6 i 6 r − 2. Then we have
r−1
r−1


X
X
i
i
(cr+2 , cr+3 , · · · , c2r+2 ) = br−1 ,
bi y (Pr+3 ), · · · ,
bi y (P2r+2 ) .
i=0

i=0

Case 1: the erased symbol is cr+2 at Pr+2 . Since y(Pℓ ) are pairwise distinct for
r + 3 6 ℓ 6 2r + 2, the coefficients bi for 0 6 i 6 r − 1 can be determined by the
Lagrange interpolation. Hence, the erased symbol cr+2 can be recovered.
Case 2: the erased symbol is cw at Pw with r + 3 6 w 6 2r + 2. Then we have
r−2
X

bi y i (Pℓ ) = cℓ − br−1 y r−1(Pℓ )

i=0

for each ℓ with r + 3 6 ℓ 6= w 6 2r + 2. Hence, the coefficients b0 , · · · , br−2 can
be determined by thePLagrange interpolation, i.e., the erased symbol cw can also be
r−1
bi y i (Pw ).

recovered from cw = i=0

Example 5.4. For q = 11, we provide an explicit construction of an optimal [12,2t,143t]-locally repairable code with locality 2 for 1 6 t 6 4. First of all, we choose a
quadratic primitive polynomial x2 − 4x + 2 in F11 [x]. Let σ the an automorphism
of F11 (x) sending x to 1/(−2x + 4). Then the order of σ is 12. Let ak be the
numbers defined in the proof of Lemma 5.1. Hence, they can be computed, i.e.,
(a0 , a1 , · · · , a8 , a9 ) = (0, 1, 4, 3, 4, −1, −1, −2, −6, 2). Let G = hσ 4 i. It follows that
F G = F11 (z), where
5x + 4 4x − 6
3x3 + x + 3
+
= 2
3x − 1
x+2
3x + 5x − 2
from Equation (13). The infinity place ∞ of z, the zero places of z − 2, z − 3 and
z − 4 in F G are splitting completely into {P∞ , P4 , P9 }, {P2 , P5 , P6 }, {P1 , P3 , P10 } and
{P0 , P7 , P8 } in F/F G respectively. Let y = 1/x. Then (y)∞ = (x)0 = P0 . Put
!
)
( 1
t−1
X X
V :=
aij z j y i : aij ∈ F11 .
z = x + σ 4 (x) + σ 8 (x) = x +

i=0

j=0

Then the algebraic geometry code
n
C(P, V ) =
(z −3 f )(P∞ ), (z −3 f )(P4 ), (z −3 f )(P9), (y −1f )(P0 ), f (P7 ), f (P8 ),

o
f (P2 ), f (P5 ), f (P6 ), f (P1), f (P3 ), f (P10 ) : f ∈ V .

LRC VIA AUTOMORPHISM GROUP

19

is an optimal [12, 2t, 14 − 3t]-locally repairable code with locality 2 for 1 6 t 6 4.
Furthermore, a generator matrix of an optimal [12, 8, 2]-locally repairable code can be
computed as follows:


0 0 0 0 1 1 1 1 1 1 1 1
 0 0 0 1 8 7 6 9 2 1 4 10 


 0 0 0 0 4 4 2 2 2 3 3 3 


 0 0 0 4 10 6 1 7 4 3 1 8 
.

 0 0 0 0 5 5 4 4 4 9 9 9 
 0 0 0 5 7 2 2 3 8 9 3 2 


 1 1 1 0 9 9 8 8 8 5 5 5 
0 3 5 9 6 8 4 6 5 5 9 6
Example 5.5. Let q = 27. Then by Theorem 5.3, one can explicitly construct optimal
27-ary locally repairable codes with the following parameters
(i) [28, t, 30 − 2t]-locally repairable codes with locality 1 for any 1 6 t 6 14;
(ii) [28, 3t, 30 − 4t]-locally repairable codes with locality 3 for any 1 6 t 6 7;
(iii) [28, 6t, 30 − 7t]-locally repairable codes with locality 6 for any 1 6 t 6 4;
(iv) [28, 13t, 30 − 14t]-locally repairable codes with locality 13 for any 1 6 t 6 2.
Example 5.6. Let q = 64. Then by Theorem 5.3, one can explicitly construct optimal
64-ary locally repairable codes with the following parameters
(i) [65, 4t, 67 − 5t]-locally repairable codes with locality 4 for any 1 6 t 6 13;
(ii) [65, 12t, 67 − 13t]-locally repairable codes with locality 12 for any 1 6 t 6 5.
6. Explicit construction via dihedral subgroups
Let F be the rational function field Fq (x). In this section, we give an explicit
construction of optimal locally repairable codes from a subgroup G of Aut(F/Fq ) that
is isomorphic to some dihedral subgroup D2h with h > 2. For odd q, the order 2h
of D2h is a divisor of q − 1 or q + 1. Thus, such localities r have been obtained in
Sections 4 and 5 already. In this section, we only consider even q. From the Hurwitz
genus formula, there are 2 + h rational places of F which are ramified in F/F G (see [9,
Theorem 11.91(iii)]).
6.1. h is a divisor of q − 1. In this subsection, let h > 2 be a positive divisor of
q − 1. Let σ be the automorphism of Fq (x) determined by σ(x) = ax for a ∈ F∗q with
ord(a) = h and let τ be the automorphism of Fq (x) determined by τ (x) = 1/x. Let
G be the subgroup of Aut(F/Fq ) generated by σ and τ . Then it is easy to verify that
G = hσ, τ i = hσ, τ |σ h = 1, τ 2 = 1, τ σ = σ −1 τ i ∼
= D2h .
Theorem 6.1. Let h > 2 be a positive divisor of q − 1 for even q. Put r = 2h − 1
and n = (r + 1)m for any positive integer m 6 q−1−h
. Then for any integer t with
2h
1 6 t 6 m, there exists an optimal [n, k, d]q -locally repairable code with locality r,
k = rt and d = n − k − kr + 2.
Proof. Let F be the rational function field Fq (x). Let G = hσ, τ i be the subgroup
of Aut(F/Fq ) of order r + 1 = 2h that is isomorphic to the dihedral subgroup D2h ,

20

LINGFEI JIN, LIMING MA, AND CHAOPING XING

where σ, τ are defined in this subsection. Let P∞ be the unique pole place of x, i.e.,
(x)∞ = P∞ . It is easy to verify that z = xh + x−h is an element of F G . Moreover, the
pole divisor of z in F is (z)∞ = hP∞ + hP0 . Hence, F G = Fq (z). For t > 1, consider
the set of functions
!
)
( r−1 t−1
X X
V :=
aij z j xi : aij ∈ Fq .
i=0

j=0

The rest of the proof is similar as that of Proposition 3.1.



Example 6.2. Let q = 16 and F16 = F2 (α) with α4 + α + 1 = 0. We give an
explicit construction of an optimal [12,5t,14-6t]-locally repairable code with locality
5 for 1 6 t 6 2. Let F be the rational function field F16 (x), let σ(x) = α5 x be an
automorphism of F16 (x) of order 3 and let G = hσ, τ i be the dihedral subgroup D6
of Aut(F/F16 ). It follows that F G = F16 (z) where z = x3 + x−3 . It is easy to verify
that the infinity place ∞ of F G splits into two places {P∞ , P0 } in F with ramification
index 3, the zero place of z of F G splits into three places {P1 , Pα5 , Pα10 } in F with
ramification index 2, the zero places of z − (α2 + α + 1) and z − (α2 + α) of F G split
completely in F . In particular, (z − α2 − α − 1)0 = Pα + Pα4 + Pα6 + Pα9 + Pα11 + Pα14
and (z − α2 − α)0 = Pα2 + Pα3 + Pα7 + Pα8 + Pα12 + Pα13 . Put
( 4
!
)
t−1
X X
V :=
aij z j xi : aij ∈ F16 .
i=0

j=0

Then the algebraic geometry code
n
C(P, V ) =
f (Pα ), f (Pα4 ), f (Pα6 ), f (Pα9 ), f (Pα11 ), f (Pα14 ),

o
f (Pα2 ), f (Pα3 ), f (Pα7 ), f (Pα8 ), f (Pα12 ), f (Pα13 ) : f ∈ V .

is an optimal [12,5t,14-6t]-locally repairable code with locality 5 for 1 6 t 6 2. Similar
to Example 5.4, a generator matrix of such a code can be obtained as well. We skip
the details.
Example 6.3. Let q = 64. Then
(i) by Theorem 6.1, there exists an optimal 64-ary [60, 5t, 62−6t]-locally repairable
code with locality 5 for any 1 6 t 6 10;
(ii) by Theorem 6.1, there exists an optimal 64-ary [56, 13t, 58 − 14t]-locally repairable code with locality 13 for any 1 6 t 6 4;
(iii) by Theorem 6.1, there exists an optimal 64-ary [54, 17t, 56 − 18t]-locally repairable code with locality 17 for any 1 6 t 6 3.
6.2. h is a divisor of q + 1. Let h > 2 be a positive divisor of q + 1 in this subsection.
Theorem 6.4. Let r be a positive integer such that r + 1 = 2h, where h > 2 is a
. Then for
positive divisor q + 1. Put n = m(r + 1) for any positive integer m 6 q−1−h
r+1
any integer t with 1 6 t 6 m, there exists an optimal q-ary [n, k, d]-locally repairable
code with locality r, k = rt and d = n − k − kr + 2.

LRC VIA AUTOMORPHISM GROUP

21

Proof. Let F be the rational function field Fq (x) and let P∞ be the infinite place of F ,
i.e., (x)∞ = P∞ . Let σ be the automorphism of Fq (x) of order q + 1 defined in Lemma
q+1
5.1. Then G := hσ h , τ i is isomorphic to the dihedral subgroup D2h of Aut(F/Fq ),
where τ is given by τ (x) = x1 . Put
X
µ(x) =
ρ(x).
ρ∈hσ

q+1
h i

It is easy to verify that z = µ(x) · µ(x−1 ) is an element of F G . Moreover, the degree
of the pole divisor of z in F is deg(z)∞ = 2h. Hence, F G = Fq (z). For t > 1, consider
the set of functions
( r−1 t−1
!
)
X X
V :=
aij z j xi : aij ∈ Fq .
i=0

j=0

Similarly, the proof can be completed by following that of Proposition 3.1.



Example 6.5. Let q = 64. For each divisor h > 2 of 65, then
(i) by Theorem 6.4, there exists an optimal 64-ary [50, 9t, 52−10t]-locally repairable
code with locality 9 for any 1 6 t 6 5;
(ii) by Theorem 6.4, there exists an optimal 64-ary [26, 25, 2]-locally repairable code
with locality 25.
7. Conclusion
In this paper, we show that as long as there is a subgroup G of PGL2 (q) of order r+1,
one can construct an optimal locally repairable code with locality r. These optimal
locally repairable codes can be explicitly constructed as all subgroups of PGL2 (q) have
explicit structures. In this paper we provide explicit construction of optimal locally repairable codes only for several subgroups such as affine subgroups, subgroups of a cyclic
group of order q + 1 and dihedral subgroups. We also provide a general construction
by estimating the number of ramified places regardless of subgroup structures.
It is clear that the construction given in this paper can be generalized to arbitrary
function fields. We are currently working on the construction of locally repairable codes
from Hermitian function fields and asymptotically optimal towers.
References
[1] A. Barg, I. Tamo, and S. Vlăduţ, Locally recoverable codes on algebraic curves, IEEE Trans.
Inform. Theory 63(8)(2017), 4928–4939.
[2] V. Cadambe and A. Mazumda, An upper bound on the size of locally recoverable codes, 2013
International Symposium on Network Coding, August 2013.
[3] P. J. Cameron, G.R. Omidi and B. Tayfeh-Rezaie, 3-Designs from PGL(2, q), The Electronic
Journal of Combinatorics 13(2006), #R50.
[4] C. Chevalley, Introduction to the Theory of Algebraic Functions of one Variable, Mathematical
Surveys 6, 1951.
[5] L. E. Dickson, Linear Groups: With an Exposition of the Galois Field Theory, Dover Publications
Inc., New York, 1958.

22

LINGFEI JIN, LIMING MA, AND CHAOPING XING

[6] M. Forbes and S. Yekhanin, On the locality of codeword symbols in non-linear codes, Discrete
Mathematics 324(6)(2014), 78–84.
[7] P. Gopalan, C. Huang, H. Simitci and S. Yekhanin, On the locality of codeword symbols, IEEE
Trans. Inf. Theory 58(11)(2012), 6925–6934.
[8] J. Han and L. A. Lastras-Montano, Reliable memories with subline accesses, Proc. IEEE Internat.
Sympos. Inform. Theory, 2007, 2531–2535.
[9] J. W. P. Hirschfeld, G. Korchmáros and F. Torres, Algebraic Curves over a Finite Field, Princeton
Series in Applied Mathematics, Princeton University Press, 2008.
[10] C. Huang, M. Chen, and J. Li, Pyramid codes: Flexible schemes to trade space for access efficiency
in reliable data storage systems, Sixth IEEE International Symposium on Network Computing
and Applications, 2007, 79–86.
[11] D. Leemans and E. Schulte, Polytopes with groups of type PGL2 (q), Ars Math. Contemp. 2(2009),
163–171.
[12] E. H. Moore, The subgroups of the generalized finite modular group, Decennial Publications of
the University of Chicago 9(1904), 141–190.
[13] H. Niederreiter and C.P. Xing, Rational Points on Curves over Finite Fields: Theory and Applications, LMS 285, Cambridge, 2001.
[14] D. S. Papailiopoulos and A.G. Dimakis, Locally repairable codes, IEEE Trans. Inf. Theory
60(10)(2014), 5843–5855.
[15] N. Prakash, G.M. Kamath, V. Lalitha and P.V. Kumar, Optimal linear codes with a local-errorcorrection property, Proc. 2012 IEEE Int. Symp. Inform. Theory, 2012, 2776–2780.
[16] J.D. Saedeleer and D. Leemans, On the rank two geometries of the groups PSL(2, q): Part I, Ars
Math. Comtemp. 3(2010), 177–192.
[17] N. Silberstein, A.S. Rawat, O.O. Koyluoglu and S. Vichwanath, Optimal locally repairable codes
via rank-matric codes, Proc. IEEE Int. Symp. Inf. Theory, 2013, 1819–1823.
[18] H. Stichtenoth, Algebraic Function Fields and Codes, Graduate Texts in Mathematics 254,
Springer Verlag, 2009.
[19] I. Tamo and A. Barg, A family of optimal locally recoverable codes, IEEE Trans. Inform. Theory
60(8)(2014), 4661–4676.
[20] I. Tamo, D.S. Papailiopoulos and A.G. Dimakis, Optimal locally repairable codes and connections
to matroid theory, IEEE Trans. Inform. Theory 62(12)(2016), 6661–6671.
[21] M. A. Tsfasman and S.G. Vlăduţ, Algebraic-Geometric Codes, Dordrecht, The Netherlands:
Kluwer, 1991.
[22] M. A. Tsfasman, S.G. Vlăduţ and D. Nogin, Algebraic Geometric Codes: Basis Notions, American
Mathematical Soc., 1990.
[23] A. Wiman, Bestimmung aller untergruppen einer doppelt unendlichen reihe von einfachen gruppen, Bihan till K. Svenska Vet.-Akad. Handl. 25(1899), 1–147.
Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433, China.
E-mail address: lfjin@fudan.edu.cn
School of Mathematical Sciences, Yangzhou University, Yangzhou China 225002
E-mail address: lmma@yzu.edu.cn
Division of Mathematical Sciences, School of Physical & Mathematical Sciences,
Nanyang Technological University, Singapore 637371
E-mail address: xingcp@ntu.edu.sg

