arXiv:1710.10322v2 [] 28 Nov 2017

On Maximally Recoverable Local Reconstruction Codes
Sivakanth Gopi∗
Princeton University
sgopi@cs.princeton.edu

Venkatesan Guruswami†
Carnegie Mellon Univ.
venkatg@cs.cmu.edu

Sergey Yekhanin
Microsoft Research
yekhanin@microsoft.com

Abstract
In recent years the explosion in the volumes of data being stored online has resulted in distributed
storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs)
have emerged as the codes of choice for these applications. An (n, r , h, a, q)-LRC is a q-ary code, where
encoding is as a two stage process. In the ﬁrst stage, h redundant parity symbols are generated from k
data symbols. In the second stage, the k +h symbols are partitioned into sets of size r −a and each set is
extended with a redundant symbols using an MDS code to form a local group. Local groups ensure that
when at most a coordinates are erased, any missing coordinate can be recovered by accessing at most
r − a symbols. Also, if a larger number of coordinates is erased, the missing symbols can be recovered
by potentially accessing all remaining symbols.
An (n, r , h, a, q)-LRC code as above is Maximally Recoverable (MR), if it corrects all erasure patterns
which are information theoretically correctable given the presence of local groups. Obtaining MR LRCs
over ﬁnite ﬁelds of minimal size is important in practice and has been the goal of a line of work in coding
theory. In this work we make progress towards this goal. In particular:
– We show that
when a and
 h are constant and r may grow, for every maximally recoverable LRC,

min{a,h−2}
. Prior to our work, there was no super-linear lower bound known on
q > Ωa,h n · r
the ﬁeld size of MR LRCs for any setting of parameters.
– We obtain a family of MR (n, r , h = 2, a, q)-LRCs, where q = O(n) for all settings of parameters.
Prior to our work the best constructions required q to be quadratic in n for some regimes.
– We obtain a family of MR (n, r , h = 3, a, q)-LRCs, where q = O(n 3 ) for all settings of parameters.
Prior to our work the best constructions required q to be n Θ(a) for some regimes.
– Our results in the ﬁrst two bullets above suggest the setting of r = 3, a = 1, h = 3 as the ﬁrst
setting where existence of MR LRCs over ﬁelds of near linear size is an open question. We resolve
this question in the positive by developing a new approach to LRC constructions based on elliptic
curves and arithmetic progression free sets.

∗ Research supported by NSF CAREER award 1451191 and NSF grant CCF-1523816. Most of this work was done when the
author was visiting Microsoft Research.
† Research supported in part by NSF grant CCF-1563742. Most of this work was done during a visit by the author to Microsoft
Research, Redmond. The work was also partly done when the author was visiting the School of Physical and Mathematical
Sciences, Nanyang Technological University, Singapore.

1 Introduction
The explosion in the volumes of data being stored online means that duplicating or triplicating data is not
economically feasible. This has resulted in distributed storage systems employing erasure coding based
schemes in order to ensure reliability with low storage overheads. In recent years Local Reconstruction
Codes (LRCs) emerged as the codes of choice for many such scenarios and have been implemented in a
number of large scale systems e.g., Microsoft Azure [HSX+ 12] and Hadoop [SAP+ 13].
Classical erasure correcting codes [MS77] guarantee that data can be recovered if a bounded number
of codeword coordinates is erased. However recovering data typically involves accessing all surviving
coordinates. By contrast, Local Reconstruction Codes∗ (LRCs) distinguish between the typical case when
only a small number of codeword coordinates are erased (e.g., few machines in a datacenter fail) and a
worst case when a larger number of coordinates might be unavailable, and guarantee that in the prior case
recovery of individual coordinates can be accomplished in sub-linear time, without having to access all
surviving symbols.
LRCs are systematic linear codes, where encoding is a two stage process. In the ﬁrst stage, h redundant
heavy parity symbols are generated from k data symbols. Each heavy parity is a linear combination of all
k data symbols. During the second stage, the k + h symbols are partitioned into k+h
r −a sets of size r − a and
each set is extended with a local parity symbols using an MDS code to form a local group. Encoding as
above ensures that when at most a coordinates are erased, any missing coordinate can be recovered by
accessing at most r − a symbols. However, if a larger number of coordinates (that depends on h) is erased;
then all missing symbols can be recovered by potentially accessing all remaining symbols.
Our description of LRC codes above is not complete. To specify a concrete code we need to ﬁx coeﬃcients in linear combinations that deﬁne h heavy and k+h
r −a · a local parities. Diﬀerent choices of coeﬃcients
could lead to codes with diﬀerent erasure correcting capabilities. The best we could hope for is to have
an optimal choice of coeﬃcients which ensures that our code can correct every pattern of erasures that is
correctable for some setting of coeﬃcients. Such codes always exist and are called Maximally Recoverable
(MR) [CHL07, HCL07] LRCs.† Combinatorially, an (n, r, h, a, q)-LRC is maximally recoverable it if corrects
every pattern of erasures that can be obtained by erasing a coordinates in each local group and up to h
additional coordinates elsewhere. Explicit constructions of MR LRCs are available (e.g., [CK17]) for all
ranges of parameters. Unfortunately, all known constructions require ﬁnite ﬁelds of very large size.
Encoding a linear code and decoding it from erasures involve matrix vector multiplication and linear
equation solving respectively. Both of these require performing numerous ﬁnite ﬁeld arithmetic operations. Having small ﬁnite ﬁelds results in faster encoding and decoding and thus improves the overall
throughput of the system [PGM13, Section 2]. It is also desirable in practice to work over ﬁnite ﬁelds of
characteristic 2. Obtaining MR LRCs over ﬁnite ﬁelds of minimal size is one of the central problems in the
area of codes for distributed storage.

1.1

State of the art and our results

We now summarize what is known about the minimal ﬁeld size of maximally recoverable local reconstruction codes with parameters n, r, a and h and ﬁrst cover the easy cases.
– When a = 0, LRCs are equivalent to classical erasure correcting codes. In this case Reed Solomon
codes are maximally recoverable, and they have a ﬁeld size of roughly n, which is known to be
∗ The term local reconstruction codes is from [HSX+ 12]. Essentially the same codes were called locally repairable codes
in [PD14] and locally recoverable codes in [TB14]. Thankfully all names above abbreviate to LRCs.
† Maximally recoverable LRCs are called Partial MDS (PMDS) in [Bla13, BHH13] and many follow up works.

1

optimal up to constant factors [Bal12].
– When h 6 1, there are constructions of maximally recoverable LRCs over ﬁelds of size O(r ) [BHH13]
which is optimal.
– When r = a + 1, codes in the local groups are necessarily simple repetition codes. MR LRCs can
be obtained by starting with a Reed Solomon code of length n/r and repeating every coordinate r
times. Thus the optimal ﬁeld size is Θ(n/r ).
This leaves us with the main case, when a > 1, r > a + 2, and h > 2. A number of constructions have been
obtained [Bla13, BHH13, TPD16, GHJY14, HY16, GHK+ 17, CK17, BPSY16, GYBS17]. The best constructions
for the case of h = 2 are from [BPSY16] and require a ﬁeld of size O(a · n). For most other settings of
parameters the best families of MR LRCs are from [GYBS17]. They require ﬁelds of size

h 



and O max n/r, r h+a
O r · n (a+1)h−1
.
(1)
The ﬁrst bound is typically better when r = Ω(n). The second bound is better when r ≪ n. Both bounds
require q to grow rapidly with the codeword length. The results above exhibit code constructions but not
any inherent limitations. In particular, up until our work it remained a possibility that codes over ﬁelds of
size O(n) could exist for all ranges of LRC parameters. We now summarize our results:
– We obtain the ﬁrst lower bound on the ﬁeld size of MR LRCs. In particular, we show that when a
and h are constant and r may grow, for every maximally recoverable LRC, subject to h 6 n/r :


(2)
q > Ωa,h n · r min {a,h−2} .
– We obtain a family of MR (n, r, h = 2, a, q)-LRCs, where q = O(n) for all settings of parameters.
Prior to our work the best constructions [BPSY16] required q to be O(a · n) which in general may be
up to quadratic in n. If we require that the ﬁeld has characteristic two, we can get such codes with
q = n 1+o(1) .
– We obtain a family of MR (n, r, h = 3, a, q)-LRCs, where q = O(n 3 ) for all settings of parameters.
Prior to our work the best constructions (1) required q to be up to n Θ(a) for some regimes. If we
require that the ﬁeld has characteristic two, we can get such codes with q = n 3+o(1) .
– Our results in the ﬁrst two bullets above suggest the setting of r = 3, a = 1, h = 3 as the ﬁrst setting
where existence of MR LRCs over ﬁelds of near linear size is an open question. We resolve this
question in the positive by developing a new approach to LRC constructions based on elliptic curves
and AP free sets.

1.2

Our techniques

Similarly to most earlier works in the area we represent LRC codes via their parity check matrices. Such
matrices H have size a · nr + h ×n and a simple block structure. Columns are partitioned into r -sized local
groups. For each local group there is a corresponding collection of a rows that impose MDS constraints
on coordinates in the group, and have no support outside the group. Remaining h rows of H correspond
to heavy parity symbols and carry arbitrary values.
A LRC is MR if any subset of columns of H that can be obtained by selecting a columns from each
local group and then h more has full rank. Suppose all h additional columns are selected from distinct local
groups. In this case showing that some aд + h columns are independent easily reduces to showing that a
2

certain (ah + h) × (ah + h) determinant is non-zero. An important algebraic identity that underlies our ﬁrst
three results reduces such determinants to much smaller h × h determinants of determinants in the entries
of H . A special case of this identity when h = 2 and matrices are Vandermonde type appears in [BPSY16].
To establish our lower bound, we start with a parity check matrix of an arbitrary maximally recoverable local reconstruction code. We utilize the determinantal identity to obtain a family of large subsets
X 1 , . . . , X n/r in the projective space PFqh−1 , such that any collection of vectors x 1 , . . . , x h , where vectors
{x i }i ∈[h] belong to diﬀerent sets {Xj } has full rank. We use vertex expansion properties of the hyperplanepoint incidence graph of the projective space [Alo86] to bound the size of the families {Xj } and translate
this bound to the lower bound on the alphabet size.
Our code constructions both in the case of h = 2 and h = 3 also employ the determinantal identity.
In addition to that we utilize various properties of ﬁnite ﬁelds such as the structure of multiplicative subgroups and ﬁeld extensions. In the case of h = 3, we deviate from most existing constructions of MR LRCs
2
in that we do not use linearized constraints (x, x q , x q ) or Vandermonde constraints (x, x 2 , x 3 ) and instead
rely on Cauchy matrices [LN83] to specify heavy parities.
Our construction of MR (n, r = 3, h = 3, a = 1, q)-LRCs is technically disjoint from our other results.
We observe that in this narrow case, MR LRCs are equivalent to subsets A of the projective plane PFq2 ,
where A is partitioned in triples A = ⊔i {ai , bi , ci } so that some three elements of A are collinear if and
only if they constitute one of the triples {ai , bi , ci } in the partition. Moreover, minimizing the ﬁeld size
of maximally recoverable local reconstruction codes is in fact equivalent to maximizing the cardinality
of such sets A. By considering all the q + 1 lines through an arbitrary point of A, it is easy to see that
|A| 6 q + 3. We construct sets A with size |A| > q 1−o(1) . For our construction we start with an elliptic
curve E over Fq such that the group of Fq -rational points, E(Fq ), is a cyclic group of size Ω(q). We observe
that three points of E(Fq ) are collinear if only and only if they sum to zero in the group. We then select
a large AP-free set of points of E(Fq ) using the classical construction of Behrend [Beh46] and complete
these points to desired triples.

1.3

Related work

The ﬁrst family of codes with locality for applications in storage comes from [HCL07, CHL07]. These
papers also introduced the concept of maximal recoverability in a certain restricted setting. The work
of [GHSY12] introduced a formal deﬁnition of local recovery and focused on codes that guarantee local
recovery for a single failure. For this simple setting they were able to show that optimal codes must have a
certain natural topology, e.g., codeword coordinates have to be arranged in groups where each group has
a local parity. While [GHSY12] focused on systematic codes that provide local recovery for information
symbols, [PD14] considered codes that provide locality for all symbols and deﬁned local reconstruction
codes. In parallel works maximally recoverable LRCs have been studied in [BHH13, Bla13]. Construction
of local reconstruction codes with optimal distance over ﬁelds of linear size has been given in [TB14]. (Note
that distance optimality is a much weaker property than maximal recoverability, e.g., when a + h < r it
only requires all patterns of size a + h to be correctable, while MR property requires lots of very large
patterns including some of size (a + 1)h to be correctable.)
Maximal recoverability can be deﬁned with respect to more general topologies then just local reconstruction codes [GHJY14]. The ﬁrst lower bound for the ﬁeld size of MR codes in any topology was recently
given in [GHK+ 17]. This line of work was continued in [KLR17] where nearly matching upper and lower
bounds were obtained. The topology considered in [GHK+ 17, KLR17] is a grid-like topology, where codewords form a codimension one subspace of tensor product codes, i.e., codewords are matrices, there is one
heavy parity symbol, and each row / column constitutes a local group with one redundant symbol.
Finally, there are few other models of erasure correcting codes that provide eﬃcient recovery in typical
3

failure scenarios. These include regenerating codes [DGW+ 10, WTB17, YB17, GW16] that optimize bandwidth consumed during repair rather than the number of coordinates (machines) accessed during repair;
locally decodable codes [Yek12] that guarantee sub-linear time recovery of information coordinates even
when a constant fraction of coordinates are erased; and SD codes [Bla13, BPSY16] that correct a certain
subset of failure patterns correctable by MR LRCs.

1.4

Organization

In Section 2 we setup our notation, give formal deﬁnitions of local reconstruction codes and maximal
recoverability, and establish some basic facts about MR LRCs. In Section 3 we present our determinantal
identity and use it to obtain the lower bound on the alphabet size. In Section 4 we give a construction of
MR LRCs with two heavy parity symbols over ﬁelds of nearly linear size. In Section 5 we generalize the
determinantal identity and employ it together with some basic properties of ﬁnite ﬁelds to get explicit MR
codes over ﬁelds of nearly cubic size. Finally, in Section 6 we focus on the narrow case of codes with three
heavy parities, one parity per local group, and local groups of size three. We introduce the machinery of
elliptic curves and AP free sets and employ it to obtain maximally recoverable codes over ﬁelds of nearly
linear size. We conclude by listing some open problems in Section 7.

2 Preliminaries
We begin by summarizing few standard facts about erasure correcting codes [MS77].
– [n, k, d]q denotes a linear code (subspace) of dimension k, codeword length n, and Hamming distance
d over a ﬁeld Fq . We often write [n, k, d] or [n, k] instead of [n, k, d]q when the left out parameters
are not important.
– An [n, k, d] code is called Maximum Distance Separable (MDS) if d = n − k + 1.

– A linear [n, k, d]q code C can be speciﬁed via its parity check matrix H ∈ Fq(n−k)×n , where C = {x ∈
Fnq | H · x = 0}. A code C is MDS iﬀ every (n − k) × (n − k) minor of H is full rank.

– Let C be an [n, k] code with a parity check matrix H ∈ F(n−k)×n . Let E be a subset of the coordinates
of C. If coordinates in E are erased; then they can be recovered (corrected) iﬀ the matrix H restricted
to coordinates in E has full rank.

We proceed to formally deﬁne local reconstruction codes.
Deﬁnition 2.1. Let r | n, a < r, and h be integers and q be a prime power. Let д = nr . Assume h 6 n − aд and
let k = n −дa −h. A linear [n, k] code C over a ﬁeld Fq is an (n, r, h, a, q)-LRC if for each i ∈ [д], restricting C to
coordinates in {r (i −1)+1, . . . , ri}, yields a maximum distance separable code with parameters [r, r −a, a +1].
Let [n] = {1, . . . , n}. In what follows we refer to subsets {r (i − 1) + 1, . . . , ri} of the set of code coordinates [n] as local groups. There are д local groups and each such group has size r . It is immediate from
the Deﬁnition 2.1 that every (n, r, h, a, q)-LRC admits a parity check matrix H of the following form





H=






A1 0
0 A2
..
..
.
.
0
0
B1 B2
4






.

· · · Aд 
· · · Bд 
···
···
..
.

0
0
..
.

(3)

Here A1 , A2 , · · · , Aд are a × r matrices over Fq , B 1 , B 2 , · · · , Bд are h × r matrices over Fq . The rest of the
matrix is ﬁlled with zeros. Every matrix {Ai }i ∈[д] is a parity check matrix of an [r, r − a, a + 1] MDS code.
The bottom h rows of H serve to increase the code co-dimension from aд to aд + h. Conversely, every
matrix H as in (3), where rank(H ) = aд + h, and every a × a minor in each {Ai }i ∈[д] has full rank, deﬁnes
an (n, r, h, a, q)-LRC.
Deﬁnition 2.2. ‡ Let C be an arbitrary (n, r, h, a, q)-local reconstruction code. We say that C is maximally
recoverable if for any set E ⊆ [n], |E | = дa + h, where E is obtained by selecting a coordinates from each of д
local groups and then h more coordinates arbitrarily; E is correctable by the code C.
The term maximally recoverable code is justiﬁed by the following observation (e.g., [GHJY14]): if an
erasure pattern cannot be obtained via the process detailed in the Deﬁnition 2.2; then it cannot be corrected
by any linear code whose parity check matrix has the shape (3). Thus MR codes provide the strongest
possible reliability guarantees given the locality constraints deﬁning the shape of the parity check matrix.
Existence of MR LRCs can be established non-explicitly [GHJY14] (i.e., by setting the non-zero entries
in the matrix (3) at random in a large ﬁnite ﬁeld and then analyzing the properties of the resulting code).
There are also multiple explicit constructions available [CK17, GHJY14, GYBS17]. The key challenge in
this line of work is to determine the minimal size of ﬁnite ﬁelds where such codes exist. In practice one is
naturally mostly interested in ﬁelds of characteristic two.
Notation: We use A & B to denote A = Ω(B) and A . B to denote A = O(B). We use A = O ℓ (B) and
A = Ωℓ (B) to denote that the hidden constants can depend on some parameter ℓ but independent of other
parameters.

3 The lower bound
In this Section we establish our lower bound on the ﬁeld size of maximally recoverable local reconstruction
codes (Theorems 3.5 and 3.8). A code is MR if it corrects every erasure pattern that can be obtained by
erasing a symbols per local group, and then h more. Note that if some local group carries at most a
erasures; then it can be immediately corrected using only the properties of the local MDS code. Thus we
never need to consider erasure patterns spread across more than h groups. Our lower bound does not use
all the properties of MR LRCs, but only relies on code’s ability to correct all patterns obtained by erasing
a + h elements in a single group as well as all patterns obtained by erasing exactly a + 1 coordinates in
some h local groups.
The actual proof of the lower bound appears in Section 3.3, and in Sections 3.1 and 3.2 we prepare the
necessary machinery. In particular, in Section 3.1 we setup notation, introduce some linear algebra tools,
and establish an identity that allows us to reduce (ah +h) × (ah +h) determinants that arise when h distinct
local groups each experience a + 1 erasures, to h × h determinants of determinants in the entries of the
parity check matrix of the code. That identity is used in Section 3.3 to turn a parity check matrix of an MR
LRC over a small ﬁeld Fq into a family of large subsets X 1 , . . . , X д in the projective space PFqh−1, where no
hyperplane can simultaneously contain points from h diﬀerent sets {Xj }j ∈[д] . In Section 3.2 we use vertex
expansion properties of the hyperplane-point incidence graph of the projective space to bound the size of
such families {Xj }j ∈[д] and later translate this bound to the lower bound on the alphabet size.
‡ Alternatively, one could deﬁne MR LRCs is as follows. Consider a matrix (3). Each way of ﬁxing non-zero entries in (3) gives
rise to (instantiates) a linear code. An instantiation is MR if it corrects all erasure patterns that are correctable for some
other

instantiation. It can be shown that under such deﬁnition and the minor technical assumption of h 6 nr · (r − a) − max nr , r − a
local codes have to be MDS [GHK+ 17, Proposition 4] as required in Deﬁnition 2.1.

5

3.1

The determinantal identity

Given a partitioned matrix of the form
M=



A U
B V



where A is a square matrix of full rank, we can do column operations to remove U using linear combinations
of columns of A as follows:
 
 


0
I −A−1U
A
A U
·
=
.
B V
0
I
B V − BA−1U
The matrix V −BA−1U is called the Schur complement of A and is denoted by M/A. Since column operations
do not change the determinant, we have
det(M) = det(A) det(M/A).
In what follows we sometimes abuse notation and employ the same variable to denote a number x, a 1 × 1
matrix containing x, or a single element set containing x. When A is an a ×a matrix and M is (a +1)×(a +1)
matrix, the Schur complement is
det(M)
.
M/A =
det(A)
For an m × n matrix A, we denote by A(S ) (T ), the submatrix of A formed by choosing the subset S ⊆ [m]
of its rows and the subset T ⊆ [n] of its columns. When S = [m] or T = [n], we abbreviate A(S ) (T ) to
respectively A(T ) and A(S ) .
The following lemma allows us to reduce (ah + h) × (ah + h) determinants that can be obtained by
selecting a + 1 columns from some h diﬀerent local groups in a matrix (3) to simpler determinants of size
h × h. A special case of this lemma when h = 2 and matrices are Vandermonde type appears in [BPSY16].
We also prove and use a more general form of this lemma in our MR code construction for h = 3 in
Section 5, but we include the simpler form below for a self-contained treatment of our lower bound proof.
Lemma 3.1. Let C 1, · · · , Ch be a × (a + 1) dimensional matrices and D 1 , · · · , D h be h × (a + 1) dimensional
matrices over a ﬁeld and let D i(j) be the j t h row of D i . Then,





det 






C1
0
..
.

0
C2
..
.

0
0
D1 D2





 det C 1



D 1(1)



ah(h−1)

..
 = (−1) 2 det 
.




C1
· · · Ch 

det (h)

· · · D h 
D1

···
···
..
.

0
0
..
.


Ch 
· · · det (1) 
Dh 

..
..
.
.
.
 

Ch 
· · · det (h) 
D h 


Proof. As we are showing an algebraic identity, without loss of generality, we can assume that the ﬁrst a
columns of Ci are independent for each i ∈ [h]. We can add a linear combination of the ﬁrst a columns of Ci
to
of the (a + 1) × (a + 1) matrix
 the last column to make it zero and use the fact that the Schur complement


Ci
Ci
(j) with respect to leading principal a × a minor C i ([a]) is det
(j) /det(C i ([a])). The corresponding
Di
Di

6

column operation is shown below:
 Ci ([a])

0






 D (1) ([a]) det Ci /det(C ([a])) 
 i

i
 
(1)
Di


Ci

.
→
.
.

.
.
Di
.
.






Ci
 (h)

D i ([a]) det (h) /det(Ci ([a]))


Di



After such columns operations, we can permute the columns to get the following matrix:
 C 1 ([a])
0


0
C
([a])
2


..
..

.
.


0
0






 D ([a]) D ([a])
2
 1














· · · Ch ([a])






Ch
C1

det (1) /det(C 1 ([a])) · · · det (1) /det(Ch ([a])) 

Dh
D1

.
.
.

..
..
..
· · · D h ([a])







Ch
C1
det (h) /det(C 1 ([a])) · · · det (h) /det(Ch ([a])) 
Dh
D1

···
···
..
.

0
0
..
.

0
0
..
.

The above matrix is block triangular and so its determinant is the product of determinants of the diagonal
blocks. Since column operations do not change the determinant and permuting the columns changes the
sign of the determinant by (−1)ah(h−1)/2 , we get the desired result.

Next we establish the following basic linear algebra fact, that will be used in the proof of our ﬁeld size
lower bound.
Lemma 3.2. Let V be a (d − 1) × d dimensional matrix over F which is full rank. Then the one dimensional
subspace orthogonal to the row space of V is spanned by


V ⊥ = (−1)d+1 det(V ([d] \ {1})), − det(V ([d] \ {2})), · · · , (−1)d−1 det(V ([d] \ {d})) .
(4)
Moreover, for any vector u ∈ Fd , we have:

 
V
V , u = det
.
u
⊥

Proof. By Laplace expansion of the determinant, it is clear that
 
V
⊥
V , u = det
u

 
V
is deﬁned as above. Now u ∈
is spanned by the rows of V iﬀ the det
vanishes, so V ⊥ is
u
the vector orthogonal to the subspace spanned by the rows of V .

where V ⊥

Fd

7

3.2

Families of subsets of PFdq in general position

In this section we prepare the last ingredient (Lemma 3.4) of our ﬁeld size lower bound. Our lemma follows
from the following result regarding vertex expansion properties of the the point-hyperplane incidence
graph in PFdq .
Lemma 3.3. (Theorem 2.3 in [Alo86]) Let U = PFdq be the set of points and V = PFdq be the set of hyperplanes
in the d-dimensional projective space over Fq . Let G(U ∪ V , E) be the incidence bipartite graph where a point
p ∈ U is connected to a hyperplane H ∈ V iﬀ p lies on H . Then for every X ⊆ U ,
1

|V | 1+ d
|N (X )| > |V | −
|X |

where N (X ) is the neighborhood of X in G.

We are now ready to prove the Lemma.
Lemma 3.4. Let X 1 , · · · , XM ⊆ PFdq be mutually disjoint subsets of size t. If


M
t > (q + 1)(d + 1)
d +1

(5)

then there exists a hyperplane H ∈ PFdq which contains points from d + 1 distinct subsets among X 1 , · · · , XM .
Proof. Let G be the point-hyperplane incidence graph in PFdq and for X ⊆ PFdq , let N (X ) be the hyperplanes
incident to at least one point in X . Let n = |PFdq | = (qd+1 − 1)/(q − 1) be the number of points in PFdq . Set
 M 
and for i ∈ [d + 1], deﬁne
m = d+1
S i = X (i−1)m+1 ∪ X (i−1)m+2 ∪ · · · ∪ X im .

By Lemma 3.3 and (5),
n(q + 1)
n 1+1/d
n
6
<
.
mt
mt
d +1
By union bound there exists a hyperplane H such that H ∈ N (S 1 ) ∩ N (S 2 ) ∩ · · · ∩ N (Sd+1 ) and therefore
contains d + 1 points from distinct subsets among X 1 , · · · , Xm(d+1) .

|N (S i )| 6

3.3

Proof of the lower bound

We ﬁrst establish the following theorem that relies on the condition a + 2 6 h. Later in Theorem 3.8 we
generalize our argument to take care of the case when h < a + 2.
Theorem 3.5. When a + 2 6 h 6 n/r , any maximally recoverable (n, r, h, a, q)-local reconstruction code
must have
j n k  r 
·
− 1.
(6)
q>
rh 2
a+1

Proof. Consider an arbitrary maximally recoverable (n, r, h, a, q)-LRC C withд = nr local groups. According
to the discussion in Section 2 the code C admits a parity check matrix of the shape












A1 0
0 A2
..
..
.
.
0
0
B1 B2






.

· · · Aд 
· · · Bд 
···
···
..
.

8

0
0
..
.

(7)

Here A1 , A2 , · · · , Aд are a × r matrices over Fq , B 1 , B 2 , · · · , Bд are h × r matrices over Fq . The rest of the
matrix is ﬁlled with zeros. Every a × a minor in each matrix {Ai }i ∈[д] has full rank. For i ∈ [д] and each
subset S ⊆ [r ] of size |S | = a + 1, deﬁne pi,S ∈ Fhq as

pi,S




 det Ai (S) 

B (1) (S) 


 i

Ai (S) 


 det (2)
Bi (S)  .
= 

..




.




Ai (S) 

det (h)


B
i (S) 


The MR property implies that any subset of columns of the parity check matrix (7) which can be obtained
by picking a columns in each local group and h arbitrary additional columns is full rank. We will use this
property to make two claims about the vectors pi,S .
Claim
3.6. For every
 distinct ℓ1 , · · · , ℓh ∈ [д] and subsets S 1 , · · · , S h ⊆ [r ] of size a + 1 each, the h ×h matrix

pℓ1,S 1 , · · · , pℓh ,Sh is full rank.

Proof. Suppose we erase the coordinates corresponding to S 1 , · · · , Sh in groups ℓ1, · · · , ℓh respectively. MR
property implies that the following matrix is full rank:








· · · Aℓh (S h ) 
· · · B ℓh (S h ) 


By Lemma 3.1, the above matrix is full rank iﬀ the h × h matrix pℓ1,S 1 , · · · , pℓh ,Sh is full rank.
 Aℓ1 (S 1 )
0


0
Aℓ2 (S 2 )


..
..

.
.


0
0

 B (S ) B (S )
ℓ2 2
 ℓ1 1

···
···
..
.

0
0
..
.

(8)



[r ] 
In particular the vectors pi,S are nonzero for every i ∈ [д] and S ∈ a+1
. We can also conclude that
across diﬀerent local groups, pi,S and pj,T are never multiples of each other when i , j. In fact, we will
now show that even in the same local group, pi,S and pi,T are not multiples of each other unless S = T .
[r ] 
Claim 3.7. For every i ∈ [д], no two vectors in {pi,S : S ⊆ a+1
} are multiples of each other.

Proof. Suppose pi,S = λ · pi,T for some distinct sets S,T ⊂ [r ] of size a + 1 each and some nonzero λ ∈ Fq .

9

Let Ai (S)⊥ and Ai (T )⊥ be column vectors deﬁned as in (4). By Lemma 3.2,





0
0








..
..




.
.








0
0





 



 det Ai (S) 
 det Ai (T ) 




(1)



Bi (S) 
Bi(1) (T ) 
Ai (S)
Ai (T )


⊥
⊥




· Ai (S) − λ ·
· Ai (T ) = 
−λ· 
Ai (S) 
Ai (T ) 
Bi (S)
Bi (T )


 det (2)

 det (2)



Bi (S) 
Bi (T ) 




..
..








.
.








Ai (S) 
Ai (T ) 
det (h)

det (h)





B
(S)
B
(T
)

i


i





0
0
=
−λ·
=0
pi,S
pi,T

Note that every coordinate of Ai (S)⊥ and Ai (T )⊥ is nonzero as it carries the value of the
of an
 determinant

Ai (S ∪ T )
a × a minor of the matrix Ai . Thus we have a linear combination of the columns of
which is
Bi (S ∪ T )
zero. Moreover the combination is non-trivial because there is some j ∈ S \ T and the column Ai (j) has a
nonzero coeﬃcient. However
|S ∪ T | 6 2a + 2 6 a + h.
(9)
 
A
Observe however that any set of columns of the matrix i of cardinality at most a + h has to be full rank
Bi
by the MR property, as this set can be obtained by selecting (a subset of) a and then h more columns from

the matrix (7). Thus we arrive at a contradiction that completes the proof of the claim.
n
o
[r ] 
By Claim 3.7 and the discussion above the claim, we can think of pi,S : i ∈ [д], S ∈ a+1
as distinct
points in PFqh−1 . For brevity, from here on we assume that pi,S refers to the corresponding point in PFqh−1 .
n
o
[r ] 
r 
Deﬁne sets X 1 , · · · , X д ⊆ PFqh−1 as X i = pi,S : S ∈ a+1
, we have |X 1 | = |X 2 | = · · · = |X д | = a+1
and
they are mutually disjoint. Also д > h by the hypothesis. By Claim 3.6, there is no hyperplane in PFqh−1
which contains h points from distinct subsets of X 1 , · · · , X д . So applying Lemma 3.4,
jд k  r 
·
.
(q + 1)h >
a+1
h

Thus

which concludes the proof.

j n k  r 
q>
·
− 1,
rh 2
a+1




In the argumentabove we used vectors pi,S , where i varies across indices of д local groups and S
r
varies across all a+1
subsets of [r ] of size a + 1. In the proof we relied on the condition a + 2 6 h to ensure
that the union of any two such sets S has size at most a + h.
Parikshit Gopalan [Gop17] has recently observed (and kindly allowed us to include his observation
here) that we can generalize Theorem 3.5 to the case when h < a + 2. To do this, in cases when h < a + 2
we only consider sets S that have size a + 1 but are constrained to contain the set {1, 2, . . . , a + 2 − h},
10

as this ensures
that pairwise unions still have size at most a + h. Clearly, the total number of such sets is
r −a+h−2 
. The rest of the proof remains the same and yields the following
h−1

Theorem 3.8. Assume h < a + 2 and h 6 n/r ; then any maximally recoverable (n, r, h, a, q)-local reconstruction code must have
j n k r − a + h − 2
·
− 1.
(10)
q>
rh 2
h−1

The following corollary follows immediately from Theorems 3.5 and 3.8 and presents the asymptotic
form of our ﬁeld size lower bound.
Corollary 3.9. Suppose that a and h are arbitrary constants, but r may grow with n. Further suppose that
h 6 n/r . In every maximally recoverable (n, r, h, a, q)-LRC, we have:


(11)
q > Ωa,h n · r min {a,h−2} .

4 Maximally recoverable LRCs with h = 2
In this section we present our construction of maximally recoverable local reconstruction codes with two
heavy parity symbols. Our construction relies on the determinantal identity (Lemma 3.1) and properties
of ﬁnite ﬁelds. Let Fq∗ denote the multiplicative group of the ﬁeld Fq .
Lemma 4.1. Let r | n, a < r be integers. Let д = nr . Assume that n − дa − 2 is positive. Suppose q is a prime
power such that there exists a subgroup of Fq∗ of size at least r and with at least n/r cosets; then there exists
an explicit maximally recoverable (n, r, h = 2, a, q)-local reconstruction code.
Proof. Let G ⊂ Fq∗ be the multiplicative subgroup from the statement of the theorem. Let α 1 , α 2 , · · · , αr ∈ G
be distinct elements from G and let λ 1, λ 2 , · · · , λд ∈ Fq∗ be elements from distinct cosets of G. We specify
our code via a parity check matrix of the form (3). For i ∈ [д], we choose matrices {Ai } and {Bi } as:
α1 α2

α 2 α 2
2
 1
Ai =  .
..
 ..
.

α a α a
2
 1

· · · αr 


· · · αr2 
λi
λi
· · · λi
.  ; Bi = α a+1 α a+1 · · · α a+1 .
..
. .. 
r
2
1
· · · αra 

(12)

Suppose that we have a erasures per local group and two more. We can easily correct the coordinates
corresponding to local groups which have at most a erasures in them. This is because every matrix Ai is a
Vandermonde matrix and all its a × a minors are nonzero. Now we are left with two cases:

Case 1: Both the extra erasures occured in the same local group. Say, the it h local
group. In this case, we

Ai
(which is a Vandermonde
can correct the erased coordinates because any (a + 2) × (a + 2) minor of
Bi
matrix) is non degenerate.
Case 2: The two extra erasures occur in diﬀerent groups say groups ℓ and ℓ ′, so we are left with two groups
with a + 1 erasures in each. Let S be the columns erased in group ℓ and let S ′ be the columns erased in
group ℓ ′. We want to argue that the following (2a + 2) × (2a + 2) submatrix is full rank:
 Aℓ (S)
0

Aℓ′ (S ′)
M =  0
 B ℓ (S) B ℓ′ (S ′)

11



.




(13)

′ }, then by Lemma 3.1,
Let S = {γ 1 , γ 2 , · · · , γa+1 } and S ′ = {γ 1′, γ 2′, · · · , γa+1




′)



 det Aℓ (S)(1) det Aℓ′ (S′ (1)


′ (S )
B
(S)
B
ℓ
ℓ




  = 0
det(M) = 0 ⇐⇒ det 
′
Aℓ′ (S ) 
 det Aℓ (S)
det
(2)
′ (2) 

B
(S)
B
ℓ
ℓ ′ (S )


′


γ 1 · · · γa+1
· · · γa+1
γ′

© 2
ª 
© ′1 2
ª
2
2
′

­γ 1 · · · γa+1 ®
­ (γ 1 ) · · · (γa+1 ) ® 

­
 det ­­ .. . .
.. ®®
.. ®® 
..
det ­­ ...

.
.
.
.
. ® 
­
®

­
­
®
®
a
a
a
′
′

­γ 1 · · · γa+1 ®
­(γ 1 ) · · · (γa+1 )a ® 


λ ℓ′ ¬ 
«λ ℓ · · · λ ℓ ¬
« λ ℓ′ · · ·
⇐⇒ det 
′
′
 =0
γ 1 · · · γa+1
···
γa+1
γ1


© 2
© ′2
2 ª
′ )2 ª 

· · · γa+1
· · · (γa+1
­ γ1
­ γ1
® 
®

® 
­

.. ®® det ­­ ..
..
..
..
® 
 det ­­ ...
.
.
.
.
.
® 
­
®

­
­
® 
®
a
a
a
a
′
′

·
·
·
γ
)
γ
γ
·
·
·
(γ
® 
­ 1
­ 1

a+1
a+1 ®
′a+1 · · · (γ ′ )a+1 
a+1 · · · γ a+1

γ
γ
¬ 
«
«
¬

1
a+1
a+1
1


λ
λ ′
Î ℓ
⇐⇒ det Î ℓ
′ =0
i ∈[a+1] γ i
i ∈[a+1] γ i

(14)

(15)

(16)

where we factored out the (nonzero) Vandermonde determinant from each column. Since γi , γi′ ∈ G and
λ ℓ , λ ℓ′ are in diﬀerent cosets of G, the last determinant is not zero.

In Lemma 4.1, given n and r such that r | n, we want to ﬁnd a small ﬁeld Fq such that Fq∗ contains a
subgroup of size at least r and with at least n/r cosets. For example, if n + 1 is a prime power, then we can
take q = n + 1. The following lemma shows that one can always ﬁnd such a ﬁeld of size q = O(n). We defer
the proof to the Appendix.
Lemma 4.2. Let r, n be some positive integers with r 6 n. Then there exists a ﬁnite ﬁeld Fq with q = O(n)
such that the multiplicative group Fq∗ contains a subgroup of size at least r and with at least n/r cosets. If
p
additionally we require that the ﬁeld has characteristic two, then such a ﬁeld exists with q = n·exp(O( log n)).
Combining Lemma 4.2 with Lemma 4.1 gives the following theorem.

Theorem 4.3. Let r | n, a < r be integers. Let д = nr . Assume that n − дa − 2 is positive. Then there exists
an explicit maximally recoverable (n, r, h = 2, a, q)-local reconstruction
p code with q = O(n). If we require the
ﬁeld to be of characteristic 2, such a code exists with q 6 n · exp(O( log n)).

5 Maximally recoverable LRCs with h = 3
In this section, we present our construction of maximally recoverable local reconstruction codes with
three heavy parity symbols. Our construction extends the ideas in the construction of Section 4 using ﬁeld
extensions.

5.1

A determinantal identity

For our construction and analysis, we will need a generalization of the determinantal identity in Lemma 3.1.
To prove the generalization, we need the following expansion of determinant of a column partitioned
matrix.
12

Lemma 5.1. For i ∈ [ℓ], let Fi be an h × ti matrix with
Õ
det[F 1 |F 2 | · · · |F ℓ ] =

Íℓ

i=1 t i

S 1 ⊔···⊔S ℓ =[h], |S i |=ti

= h. Then,

sgn(S 1 , · · · , S ℓ )

Ö

det Fi(S i )

i ∈[ℓ]

where S 1 ⊔ · · · ⊔ S ℓ ranges over partitions of [h] such that |Si | = ti . Here sgn(S 1 , · · · , S ℓ ) is the sign of the
permutation taking (1, 2, · · · , h) to (S˜1 , S˜2 , · · · , S˜ℓ ) where S˜i is the tuple formed by ordering the elements of S i
in increasing order.
Proof. Given distinct integers a 1 , · · · , an , deﬁne sgn(a 1 , a 2 , · · · , an ) := (−1)t where t is number of transpositions needed to sort the elements a 1 , a 2 , · · · , an in increasing order. Thus for a permutation π ∈ Sh ,
sgn(π ) = sgn(π (1), π (2), · · · , π (h)). Let F = [F 1 |F 2 | · · · |F ℓ ] and for i ∈ [ℓ], let Ti = {ti−1 + 1, · · · , ti } where
t 0 = 0. We can expand det(F ) as:
det(F ) =

Õ

π ∈S h

sgn(π )

=

Õ

h
Ö
i=1

F π (i)i
Õ

π : π (Ti )=S i

S 1 ⊔···⊔S ℓ =[h], |S i |=ti

Note that if π (Ti ) = S i , then for i ∈ [ℓ],
sgn(π ) = sgn(S˜1 , · · · , S˜ℓ )

ℓ
Ö
i=1

sgn(π )

h
Ö
i=1

F π (i)i

sgn(π (ti−1 + 1), · · · , π (ti ))

because we can sort (π (1), · · · , π (h)) ﬁrst within each group to get (S˜1 , · · · , S˜ℓ ) and then sort it to get
(1, 2, · · · , h). Therefore,
Õ

π : π (Ti )=S i

=

sgn(π )
Õ

h
Ö
i=1

F π (i)i

σ1 :T1 →S 1, ..., σ ℓ :Tℓ →S ℓ

= sgn(S˜1 , · · · , S˜ℓ )
= sgn(S˜1 , · · · , S˜ℓ )

ℓ
Ö
i=1

ℓ
Ö

sgn(S˜1 , · · · , S˜ℓ )
Õ

σi :Ti →S i

ℓ
Ö
i=1

sgn(σi (ti−1 + 1), · · · , σi (ti ))

ti
Ö

j=ti −1 +1

F σi (j)j

!

(where the summation is over all bijections σi : Ti → Si )
!
ti
Ö
sgn(σi (ti−1 + 1), · · · , σi (ti ))
F σi (j)j
j=ti −1 +1

det Fi(S i ) .



i=1

The following is a generalization of Lemma 3.1.
Lemma 5.2. For i ∈ [ℓ], let Ci be an a×(a+ti ) matrix and D i be an h×(a+ti ) matrix for some t 1 +t 2 +· · ·+t ℓ = h
where ti > 1. Then,
 C1 0 · · · 0 


 0 C2 · · · 0 




Õ
Ö
Íℓ
Ci

 ..
.
.
a(
t
(ℓ−i))
.
i
i
=1
. . ..  = (−1)
..
sgn(S 1 , · · · , S ℓ )
det (S i )
det  .


Di
S
⊔···⊔S
=[h],
|S
|=t
i
∈[ℓ]

 0
1
i
i
ℓ
0 · · · Cℓ 

 D D ··· D 
2
ℓ 
 1
13

where S 1 ⊔ · · · ⊔ S ℓ ranges over partitions of [h] such that |Si | = ti and sgn(S 1 , · · · , S ℓ ) is deﬁned as in
Lemma 5.1.
Proof. Let





F = [F 1 |F 2 | · · · |F ℓ ] = 






C1
0
..
.






.

· · · C ℓ 
· · · D ℓ 

0
C2
..
.

···
···
..
.

0
0
D1 D2

0
0
..
.

Let [p, q] be the integers between p and q, i.e., [p, q] = {i : p 6 i 6 q}. By Lemma 5.1,
Õ
Ö
det F = det[F 1 |F 2 | · · · |F ℓ ] =
sgn(T1 , · · · ,Tℓ )
det Fi(Ti )
T1 ⊔···⊔Tℓ =[aℓ+h], |Ti |=a+ti

i ∈[ℓ]

Note that the only terms which survive correspond to partitions T1 ⊔ T2 ⊔ · · · ⊔ Tℓ of rows of F such
that for every i ∈ [ℓ], Ti contains the rows of Ci (i.e. [(i − 1)a + 1, ia]). In the other terms, there exists
some i ∈ [ℓ] such that Fi(Ti ) contains a zero row and thus det Fi(Ti ) = 0. Such partitions are given by
Ti = [(i − 1)a + 1, ia] ∪ S i where S 1 ⊔ S 2 · · · ⊔ S ℓ is some partition of rows of [D 1 |D 2 | · · · |D ℓ ] such that
|Si | = ti . So the expansion for det F can be written as:
Ö
Õ
det Fi([(i−1)a,ia]∪S i )
sgn([1, a] ∪ S 1 , · · · , [(ℓ − 1)a + 1, ℓa] ∪ S ℓ )
det F =
S 1 ⊔···⊔S ℓ =[aℓ+1,aℓ+h], |S i |=ti
Í
a( iℓ=1 ti (ℓ−i))

= (−1)

Í
a( iℓ=1 ti (ℓ−i))

= (−1)

Õ

i ∈[ℓ]

S 1 ⊔···⊔S ℓ =[aℓ+1,aℓ+h], |S i |=ti

Õ

Ö

S 1 ⊔···⊔S ℓ =[h], |S i |=ti

sgn([1, ℓa], S 1 , S 2 , · · · S ℓ )

sgn(S 1 , S 2 , · · · S ℓ )

Ö

i ∈[ℓ]

det





([(i−1)a,ia]∪S i )

det Fi

i ∈[ℓ]

Ci
.
D i(S i )



Applying the above lemma to a special case, we get the following corollary:
Corollary 5.3. Let C 1 be an a × (a + 1) matrix, C 2 be an a × (a + 2) matrix, D 1 be a 3 × (a + 1) matrix and
D 2 be a 3 × (a + 2) matrix and let D i(j) be the j t h row of D i . Then,
 C1 0 


det  0 C 2  = 0 ⇐⇒
 D1 D2 



5.2








C2
C2
C2
© (2)
ª
© (1)
ª
© (1)
ª
C1
C1
C1
­
­
­
®
®
det (1) · det ­D 2 ® − det (2) · det ­D 2 ® + det (3) · det ­D 2 ®® = 0
D1
D1
D1
(3)
(3)
(2)
«D 2 ¬
«D 2 ¬
«D 2 ¬

Code construction and analysis

Our construction is based on Cauchy matrices, and we will also need the the following lemma about the
determinants of such matrices.
Lemma 5.4. ([LN83]) Let α 1 , · · · , αm , β 1 , · · · , βm ∈ Fq be all distinct; then
 1
 α 1 −β1
 1
 α −β
det  1 . 2
 ..
 1
 α 1 −βm


1
α 2 −β1
1
α 2 −β2

..
.

1
α 2 −βm

···
···
..
.
···



 Î

i >j (α i − αj )(βj − β i )
Î
..  =
i, j (α i − βj )
. 

1

α m −βm 
1
α m −β1
1
α m −β2

14

Matrices of the above form are called Cauchy matrices. Every minor of a Cauchy matrix is nonzero
because the minors themselves look like a Cauchy matrix. We are now ready to present the construction
for three global parities.
Lemma 5.5. Let r | n, a < r be integers. Let д = nr . Assume that n − дa − 3 is positive. Suppose q 0 > 2r + 3 is
a prime power such that there exists a subgroup of Fq∗ 0 of size at least r + 2 and with at least n/r cosets. Then
there exists an explicit maximally recoverable (n, r, h = 3, a, q = q 30 )-local reconstruction code.
Proof. Let G ⊂ Fq∗ 0 be the multiplicative subgroup from the statement of the theorem. Choose distinct
βa+1 , βa+2 , βa+3 ∈ Fq0 and let


α − βa+2
∈G .
Ω = α ∈ Fq0 :
α − βa+3

Clearly |Ω| = |G | − 1 > r + 1, so we can choose distinct α 1 , · · · , αr ∈ Ω \ {βa+1 }. Finally, since q 0 > 2r + 3 >
r + a + 3, we can choose distinct β 1 , · · · , βa ∈ Fq0 \ {α 1 , · · · , αr , βa+1 , βa+2 , βa+3 }. Let µ 1 , · · · , µд ∈ Fq0 be
elements from distinct cosets of G.
Now let Fq be a degree 3 extension of Fq0 , so we have q = q 30 . As Fq is a 3-dimensional vector space
over Fq0 , choose a basis v 0 , v 1 , v 2 ∈ Fq for this space and choose distinct γ 1 , · · · , γд ∈ Fq0 . Deﬁne λi =
v 0 +γi v 1 +γi2v 2 . Then any three of the elements λ 1 , · · · , λд ∈ Fq are linearly independent over Fq0 ; we call
this property 3-wise independence over Fq0 . Deﬁne the matrices Ai and Bi as follows:
1
 α −β
 1 1

Ai =  ...
 1

 α 1 −βa

···
..
.
···

 λi

 α −β

..  ; B =  1 µi a+1

.  i  α 1 −βa+2
1 
 α −β1
α r −βa 
 1 a+3
1
α r −β1

···
···
···

λi

α r −βa+1 

µi
α r −βa+2 
1

α r −βa+3 

(17)

Now we will show that the above construction satisﬁes the MR property. We have a erasures per local
group and 3 more. We can easily correct groups with only a erasures because Ai are Cauchy matrices
where every a × a minor is non-degenerate. So we only need to worry about local groups with more than
a erasures. There are three cases.
 
Ai
is
Bi
a Cauchy matrix (except for some scaling factors in the rows), and therefore each of its (a + 3) × (a + 3)
minors is nonzero by Lemma 5.4.
Case 1: All three extra erasures in the same group.

Say we have a + 3 erasures in local group i, then we can correct these errors because the matrix

Case 2: The three extra erasures are distributed across two groups.
Suppose the extra erasures occur in groups ℓ, ℓ ′ with (a + 1) erasures in group ℓ corresponding to a subset
S ⊆ [r ] of its columns and (a + 2) erasures in group ℓ ′ corresponding to a subset S ′ ⊆ [r ] of its columns.
To correct these erasures we need to show the following matrix is full rank:
 Aℓ (S)
0

′
 0
′
A
ℓ (S )

 B ℓ (S) B ℓ′ (S ′)


15



 .




(18)

By Corollary 5.3, the above matrix fails to be full rank iﬀ



Aℓ′ (S ′)
Aℓ′ (S ′)
A
(S)
Aℓ (S)
ª
©
©
ℓ
′ (1) ª
det
· det ­B ℓ′ (S ′)(2) ® − det
(2) · det ­B ℓ ′ (S ) ®
B
(S)
B ℓ (S)(1)
ℓ
′ (3)
′ (3)
«B ℓ′ (S ) ¬
«B ℓ′ (S ) ¬


Aℓ′ (S ′)
Aℓ (S)
©
ª
+ det
· det ­B ℓ′ (S ′)(1) ® = 0
(3)
B ℓ (S)
′ (2)
«B ℓ′ (S ) ¬


The above determinant is a Fq -linear combination of λ ℓ and λ ℓ′ and the coeﬃcient of λ ℓ , which arises from
 
 
A′
Aℓ
and ℓ are Cauchy matrices. By 3-wise independence of λ’s, this
the ﬁrst term, is nonzero because
Bℓ
B ℓ′
linear combination cannot be zero, and therefore the matrix (18) has full rank.
Case 3: The three extra erasures occur in distinct groups.
Suppose the three extra erasures occur in groups ℓ1 , ℓ2 , ℓ3 ∈ [д] and let S 1 , S 2 , S 3 ⊆ [r ] be sets of size a + 1
corresponding to the erasures in the groups ℓ1 , ℓ2, ℓ3 respectively. To correct these erasures we need to
show the following matrix is full rank:
 Aℓ1 (S 1 )
0
0


0
A
(S
)
0
ℓ2 2


0
0
Aℓ3 (S 3 )

 B (S ) B (S ) B (S )
ℓ2 2
ℓ3 3
 ℓ1 1










By Lemma 3.1, if the above matrix is not full rank then
!
!
!

Aℓ3 (S 3 ) 
Aℓ1 (S 1 )
Aℓ2 (S 2 )

det (1)
det (1)

det (1)
B ℓ1 (S 1 )
B ℓ2 (S 2 )
B ℓ3 (S 3 ) 


!
!
!

Aℓ3 (S 3 ) 
Aℓ2 (S 2 )
Aℓ1 (S 1 )

det (2)
det (2)
det det (2)
 = 0.
B ℓ3 (S 3 ) 
B ℓ2 (S 2 )
B ℓ1 (S 1 )


!
!
!

Aℓ1 (S 1 )
Aℓ2 (S 2 )
Aℓ3 (S 3 ) 

det (3)
det (3)

det (3)
B ℓ1 (S 1 )
B ℓ2 (S 2 )
B ℓ3 (S 3 ) 



Î
Î
Î
For k ∈ {1, 2, 3}, let ck = i >j,i, j ∈S k (αi − αj ), d = i >j,i, j ∈[a] (βj − βi ), ek = i ∈S k , j ∈[a] (αi − βj ). By
Lemma 5.4, we can write down explicit expressions for the entries in the above determinant to get:
Î

λ c 1dÎ i ∈[a] (βi −βa+1 )
 ℓ1 e1 i ∈S (α i −βa+1 )
1



Î
(βi −βa+2 )
 c 1d
det µ ℓ1 e1 Îii∈S∈[a](α i −βa+2 )
1



Î
 c 1dÎ i ∈[a] (βi −βa+3 )
 e1
i ∈S 1 (α i −β a+3 )


λ ℓ2
µ ℓ2

Î
c 2d i ∈[a] (βi −βa+1 )
Î
e2 i ∈S 2 (α i −βa+1 )

Î
c 2d i ∈[a] (βi −βa+2 )
Î
e2 i ∈S 2 (α i −βa+2 )

Î
c 2d i ∈[a] (βi −βa+3 )
Î
e2 i ∈S 2 (α i −βa+3 )

λ ℓ3
µ ℓ3

Î
c 3d i ∈[a] (βi −βa+1 )
Î
e3 i ∈S 3 (α i −βa+1 )

Î
c 3d i ∈[a] (βi −βa+2 )
Î
e3 i ∈S 3 (α i −βa+2 )

Î
c 3d i ∈[a] (βi −βa+3 )
Î
e3 i ∈S 3 (α i −βa+3 )







 = 0.







We can scale rows and columns to conclude that






Î
Î
 Î
α i −βa+3
α i −βa+3
α i −βa+3 
λ
λ
λ
 ℓ1 i ∈S 1 α i −βa+1
ℓ2
ℓ3
i ∈S 2 α i −βa+1
i ∈S 3 α i −βa+1 
 Î






Î
Î

α
−β
α
−β
α i −βa+3  = 0.
i
a+3
i
a+3
det µ ℓ
µ
µ
ℓ2
ℓ3
i ∈S 2 α i −βa+2
i ∈S 3 α i −βa+2 
 1 i ∈S 1 α i −βa+2



1
1
1


16



Î
α −β
By the choice of α’s, i ∈Sj α ii −βa+3
∈ G for j = 1, 2, 3. By writing the Laplace expansion of the determia+2
nant over the ﬁrst row, the above determinant is a linear combination in λ ℓ1 , λ ℓ2 , λ ℓ3 with coeﬃcients from
Fq0 . The coeﬃcients of λ’s in this linear combination are nonzero because µ ℓ1 , µ ℓ2 , µ ℓ3 belong to distinct

cosets of G in Fq∗ 0 . Because λ’s are 3-wise independent over Fq0 , we get a contradiction.
Combining Lemma 5.5 with Lemma 4.2 gives the following theorem.
Theorem 5.6. Let r | n, a < r be integers. Let д = nr > 2. Assume that n −дa − 3 is positive. Then there exists
an explicit maximally recoverable (n, r, h = 3, a, q)-local reconstruction
code with q = O(n 3 ). If we require the
p
ﬁeld to be of characteristic 2, such a code exists with q = n 3 · exp(O( log n)).

6 Maximally recoverable LRCs from elliptic curves
Our construction of MR (n, r = 3, h = 3, a = 1, q)-LRCs is technically disjoint from our results in the
previous sections. We observe that in this narrow case, maximally recoverable LRCs are equivalent to
families of matching collinear triples in the projective plane PFq2 , i.e., sets of points partitioned into collinear
triples, where no three points other than those forming a triple are collinear. In Section 6.1 we state the
quantitative parameters of such a family A that we can obtain and translate those to parameters of an
MR LRC. The goal of Section 6.2 is to construct the family A using elliptic curves and 3-AP free sets. In
Section 6.2.1 we develop the necessary machinery of elliptic curves, and in Section 6.2.2 we carry out the
construction.

6.1

LRCs from matching collinear triples

We will reduce the problem of constructing maximally recoverable codes for h = 3, r = 3, a = 1 to the
problem of constructing matching collinear triples in PFq2 which we deﬁne below.
Deﬁnition 6.1. We say that A ⊂ PFq2 has matching collinear triples if A can be partitioned into triples,
A = ⊔m
i=1 {ai , bi , c i }, such that the only collinear triples in A are {ai , bi , c i } for i ∈ [m].
What is the largest subset A ⊂ PFq2 with matching collinear triples? If we consider all the q + 1 lines
through some ﬁxed point of A, at most one line can contain two other points of A. All other lines can
contain at most one other point of A. So |A| 6 q + 3. The following lemma shows that we can construct a
set A with size |A| > q 1−o(1) . It is an interesting open question if we can get |A| > Ω(q).
Lemma 6.2. For any prime power q, there is an explicit set A ⊂ PFq2 with matching collinear triples of size
p
|A| > q · exp(−C log q) where C > 0 is some absolute constant.
We will prove Lemma 6.2 in Section 6.2.2.

Lemma 6.3. Assume д > 2. There exists a subset S ⊂ PFq2 that has д matching collinear triples if and only
if there exists a maximally recoverable (3д, r = 3, h = 3, a = 1, q)-local reconstruction code.
д

Proof. We ﬁrst show how to obtain codes from families of collinear triples. Let S = ∪i=1 {ai , bi , ci } be such
that the only collinear triples in S are {ai , bi , ci } for i ∈ [д]. From now, we will think of elements of S as
vectors in Fq3 such that every triple of points except for the triples {ai , bi , ci } are linearly independent. We
can scale each vector with nonzero elements in Fq such that ai + bi + ci = 0 in Fq3 for every i ∈ [д]. For
i ∈ [д], deﬁne blocks Ai and Bi of the parity check matrix (3) as:




Ai = 1 1 1 ; Bi = 0 −bi ci .
17

We need to correct 1 erasure per group and any 3 extra erasures. We can correct groups with a single
erasure because Ai is a simple parity check constraint on all the coordinates of the group. We now have
to correct groups with more than one erasure, there are two cases:
Case 1: The three extra erasures are in two groups.
Suppose the two groups are i, j and in group i all the coordinates are erased and in group j the second and
third coordinates are erased (the other two cases are similar). To correct these erasures, we have to argue
that the following matrix is full rank:
0 0 
1 1 
−bj cj 

 1 1
1

 0 0
0

 0 −bi ci


Subtract the ﬁrst column in each group from the rest, it is equivalent to the following matrix being full
rank:
 1 0
0
0   1 0
0
0 
0
0

 0 0
0
1
0  =  0 0
0
1
0 

 0 −bi ci −bj cj + bj   0 −bi ci −bj aj 

 

which is true because bi , ci , aj are linearly independent.

Case 2: The three extra erasures are in distinct groups.
Suppose the three groups are i, j, k and in each group the second and third columns are erased (the other
cases are similar). To correct these erasures, we have to argue that the following matrix is full rank:









0 0
1 1
0 0
−bj cj

1
1
0
0
0
0
−bi ci

0
0
0
0
1
1
−bk ck










Subtract the ﬁrst column in each group from the rest, it is equivalent to the following matrix being full
rank:









1
0
0
−bi ci

0
0
0
+ bi

0
1
0
−bj cj

0
0
0
+ bj

0
0
1
−bk ck

0
0
0
+ bk

  1
 
  0
=
  0
 
  −b
i
 

0
0
0
−ai

0
1
0
−bj

0
0
0
−aj

0
0
1
−bk

0
0
0
−ak










which is true because ai , aj , ak are linearly independent.
Reverse connection. We now proceed to show how to obtain a set with matching collinear triples from
codes. Given a maximally recoverable (3д, r = 3, h = 3, a = 1, q)-local reconstruction code with a parity
check matrix (3), without loss of generality assume that for all i ∈ [д],




Ai = 1 1 1 ; Bi = vi1 vi2 vi3 ,
where {vis }s ∈[3],i ∈[д] ⊆ Fq3 . For each i ∈ [д], deﬁne
ai = vi2 − vi1

bi = vi3 − vi2

ci = vi1 − vi3 .

Clearly, for all i ∈ [д], ai + bi + ci = 0. Consider {ai , bi , ci }i ∈[д] as elements of PFq2 and deﬁne our family
д
to be S = ∪i=1 {ai , bi , ci }. It remains to show that all triples of elements of S other than {ai , bi , ci } are
18

β

ζ

γ

non-collinear. When all three elements viα − vi , vj − vjδ , vkε − vk belong to diﬀerent groups this follows
from the fact that, as implied by the MR property, the matrix










1
1
0
0
0
0
β
vi viα

0
1
0
vjδ

0
1
0
γ
vj

0
0
1
ζ
vk

0
0
1
vkε

  1
 
  0
 
= 0
 
  β
  vi viα
 

0
0
0
β
− vi
β

0
1
0
γ
vjδ vj

0
0
0
− vjδ

0
1
0
ζ
vk

0
0
0
ζ
ε
vk − vk

γ











is full rank. When triples come from two groups, (say, vi − viα , vi − viα , vjδ − vjε ) this again follows from
the MR property, as the matrix

is also full rank.

 1
1
1

 0
0
0

 α
 vi viβ viγ


0 0
1 1
vjε vjδ

  1
0
0
 
  0
0
0
=
  α
  vi viβ − viα viγ − viα
 

0
0
1
0
δ
ε
vj vj − vjε











Combining Lemma 6.2 and Lemma 6.3 along with the fact that all the constructions are explicit gives
the following theorem.
Theorem 6.4. For any n > 3 which is a multiple of 3 and for any ﬁnite ﬁeld Fq , there exists

 an explicit
 p maximally recoverable (n, r = 3, h = 3, a = 1, q)-local reconstruction code provided that q > Ω n · exp C log n
where C > 0 is some absolute constant.

6.2

Matching Collinear Triples from AP free sets

In this section, we will prove Lemma 6.2 by constructing a large A ⊂ PFq2 with matching collinear triples.
The main idea is to reduce the problem to constructing a large subset A ⊂ Z/N Z with matching tri-sums
where N = Ω(q). A subset A ⊂ Z/N Z has matching tri-sums if A can partitioned into disjoint triples,
A = ⊔i {ai , bi , ci } such that the only 3 element subsets of A which sum to zero are the triples {ai , bi , ci }
in the partition. Such sets can be constructed from subsets of [N ] without any non-trivial arithmetic
progressions. The best known construction of a subset of [N ] with no non-trivial three term arithmetic
progressions is due to Behrend [Beh46] which was slightly improved in [Elk11]. An explicit construction
with similar bounds as [Beh46] was given in [Mos53].
Theorem 6.5 ([Beh46, Mos53, Elk11]).
p For some absolute constant C > 0, there exists an explicit A ⊂
{1, 2, · · · , N } with |A| > N · exp(−C log N ) which doesn’t contain any 3 term arithmetic progressions i.e.
there doesn’t exist distinct x, y, z ∈ A such that x + z = 2y.
It is also known that any set A ⊂ {1, 2, · · · , N } with no non-trivial 3 term arithmetic progressions
(log log N )4
should have size |A| . log N · N [Blo16].

The reduction from matching collinear triples in Fq2 to subsets of Z/N Z with matching tri-sums is
simple when q is a prime. In this case we can set N = q. Three points (x 1 , y1 ), (x 2 , y2 ), (x 3 , y3 ) ∈ Fq2 on the
cubic curve Y = X 3 are collinear iﬀ x 1 + x 2 + x 3 = 0. So we can get a large subset of PFq2 with matching
collinear triples, from a large subset of Fq  Z/qZ with matching tri-sums. And from Theorem 6.5, we can
p
get such a set of size > q · exp(−O( log q)).
When q is not prime, the additive group of Fq is not cyclic anymore and subsets of Fq with matching
tri-sums are much smaller. For example, if Fq has characteristic 2, which is the main setting of interest
19

for us, the size of the largest subset of Fq with matching tri-sums is 6 qc for some absolute constant
c < 1 [Kle16]. We will use some results on elliptic curves which are a special kind of cubic curves to make
the reduction work over any ﬁeld.
6.2.1 Elliptic curves
We will give a quick introduction to elliptic curves, please refer to [Sil09, MBG+ 13] for proofs and formal
deﬁnitions. Let K be a ﬁnite ﬁeld and K be its algebraic closure. A Weierstrass equation deﬁned over K is
homogeneous cubic equation in three variables of the following form:
F (X , Y , Z ) = Y 2Z + a 1XYZ + a 3YZ 2 − X 3 − a 2X 2Z − a 4XZ 2 − a 6Z 3 = 0
2

where a 1 , a 2 , · · · , a 6 ∈ K. A point p ∈ PK is called a singular point if
∂F
∂F
∂F
(p) =
(p) =
(p) = 0.
∂X
∂Y
∂Z
If there are no such points, we call the equation non-singular, else we call the equation singular. Since the
equation is cubic, it can have at most one singular point. There is an explicit polynomial function ∆ in
variables a 1 , a 2 , · · · , a 6 and coeﬃcients in K called the discriminant, such that the Weierstrass equation is
singular iﬀ ∆(a 1 , · · · , a 6 ) = 0 (see Section III.1 in [Sil09] for the explicit polynomial). A singular Weierstrass
equation§ E with singularity at (X , Y , Z ) = (0, 0, 1) can be written as:
E : Y 2Z + a 1XYZ − a 3X 2Z = X 3 .
2

We associate with E the set of all points in PK which satisfy the equation E. There is exactly one point in
E with Z -coordinate equal to 0, namely (0 : 1 : 0), we call this special point the point at inﬁnity and denote
it by O. The set of non-singular K-rational points of E, denoted by Ens (K) is deﬁned as follows:
Ens (K) = {(x : y : 1)|F (x, y, 1) = 0, x, y ∈ K, (x, y) , (0, 0)} ∪ {O}.
Ens (K) is an Abelian group under a certain addition operation ‘+’, with the point at inﬁnity O as the group
identity. Under this operation, three points a, b, c ∈ Ens (K) satisfy a + b + c = O iﬀ a, b, c are collinear in
PK2 . The following theorem shows that Ens (K) is isomorphic to K∗ when E is of a special form.
Theorem 6.6 (Theorem 8.1 in [MBG+ 13]). Let E : (Y − αX )(Y − βX )Z = X 3 be a singular Weierstrass
equation with α, β ∈ K and α , β. Then the map ϕ : Ens (K) → K∗ deﬁned as:
ϕ : O 7→ 1

ϕ : (x, y, 1) 7→

y − βx
y − αx

is a group isomorphism.
Since K∗ is a cyclic group for any ﬁnite ﬁeld K, Ens (K) is isomorphic to Z/N Z for N = |K| − 1 when E
is a singular Weierstrass equation as in Theorem 6.6.
§ Usually elliptic curves are deﬁned as curves given by non-singular Weierstrass equations. But for our purpose, it is easier to
work with singular Weierstrass equations.

20

6.2.2 Proof of Lemma 6.2
Proof. Let E be a singular Weierstrass equation¶ deﬁned over Fq as in Theorem 6.6. By Theorem 6.6,
Ens (Fq )  Z/N Z where N = q − 1. Recall that a, b, c ∈ Ens (Fq ) satisfy a + b + c = 0 in the group iﬀ they
are collinear.
p
Let B ⊂ {1, 2, · · · , N /20} be an explicit subset of size |B| & N · exp(−C log N ) with no 3-term arithmetic progressions, as guaranteed by Theorem 6.5. Now deﬁne subsets A1 , A2 , A3 ⊂ Z/N Z as
 


 

N
N
A1 = {x : x ∈ B} , A2 =
+ x : x ∈ B , A3 = N −
− 2x : x ∈ B .
3
3
Clearly, A1 , A2 , A3 are disjoint. Finally we deﬁne Ã = A1 ∪ A2 ∪ A3 . Now we claim that the only triples
from Ã which sum to zero in Z/N Z are {x, ⌊N /3⌋ + x, N − ⌊N /3⌋ − 2x } for x ∈ B and these triples form a
partition of Ã.
It is not hard to see that if three distinct elements a, b, c ∈ Ã satisfy a + b + c = 0, then a, b, c should
come from 3 diﬀerent sets A1 , A2 , A3 . So after reordering, we can assume
a = x, b = ⌊N /3⌋ + y, c = N − ⌊N /3⌋ − 2z
for some x, y, z ∈ B. Thus a + b + c = 0 implies that x + y = 2z, which implies that x = y = z since B is free
from 3 arithmetic progressions.
Finally let A ⊂ PFq2 be the set of points in Ens (Fq ) which map to the set Ã ⊂ Z/N Z under the isomorphism Ens (Fq )  Z/N Z. Now it is easy to see that A has matching collinear triples and we have
p

|A| & q · exp(−C log q).

7 Open problems
In this work we made progress towards quantifying the minimal size of ﬁnite ﬁelds required for existence
of maximally recoverable local reconstruction codes and obtained both lower and upper bounds. There is
a wide array of questions that remain open. Here we highlight some of them:
– Our lower bound (2) implies that even in the regime of constant a and h, when h > 3 and r grows
with n there exist no MR codes over ﬁelds of size O(n). It would be of great interest to understand if
such codes always exist when all parameters a, h, and r are held constant and only n grows.
– Our Lemma 6.3 provides an equivalence between the parameters of families of matching collinear
triples in the projective plane and maximally recoverable local reconstruction codes with r = 3, h =
3, and a = 1. We hope that this reduction will be useful to obtain an ω(n) lower bound for the
alphabet size of MR (n, r = 3, h = 3, a = 1, q)-LRCs, or lead to a construction over ﬁelds of linear
size. It is also very interesting to see if techniques similar to those in Section 6.2 can be used to get
codes over ﬁelds of nearly linear size when r > 3 or a > 1 or h > 3.
– It is interesting to understand whether various technical conditions that appear in our theorems
are in fact necessary. For instance, can one relax the condition h 6 n/r in our main lower bound
(Theorems 3.5 and 3.8)? Also, in the case of ﬁelds of characteristic two, can one reduce the ﬁeld sizes
in Theorems 4.3 and 5.6 to O(n) and O(n 3 ) to match the case of prime ﬁelds?

– Finally, it is interesting to see if our lower bounds (Theorems 3.5 and 3.8) can be generalized to
the setting of non-linear codes. Basic results about LRCs such as distance vs. redundancy tradeoﬀ [GHSY12] have been generalized to non-linear setting in [SAP+ 13, FY14].
¶ It is not essential to work with singular Weierstrass equations. The proof also works with non-singular elliptic curves as long
the group of K-rational points is cyclic or has a large cyclic subgroup.

21

Acknowledgements
We would like to thank Parikshit Gopalan for allowing us to include his Theorem 3.8 in this paper. We
would also like to thank Cheng Huang for asking the question that led us to start this project, and Ilya
Shkredov for helpful discussions about this work. And ﬁnally we would like to thank Suryateja Gavva for
telling us about Theorem A.2.

References
[Alo86]

Noga Alon. Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory. Combinatorica, 6(3):207–219, 1986. 3, 8

[Bal12]

Simeon Ball. On sets of vectors of a ﬁnite vector space in which every subset of basis size is a
basis. Journal of European Mathematical Society, 14:733–748, 2012. 2

[Beh46]

Felix A Behrend. On sets of integers which contain no three terms in arithmetical progression.
Proceedings of the National Academy of Sciences, 32(12):331–332, 1946. 3, 19

[BFI86]

Enrico Bombieri, John B Friedlander, and Henryk Iwaniec. Primes in arithmetic progressions
to large moduli. Acta Mathematica, 156(1):203–251, 1986. 25

[BHH13]

Mario Blaum, James Lee Hafner, and Steven Hetzler. Partial-MDS codes and their application
to RAID type of architectures. IEEE Transactions on Information Theory, 59(7):4510–4519, 2013.
1, 2, 3

[Bla13]

Mario Blaum. Construction of PMDS and SD codes extending RAID 5. Arxiv 1305.0032, 2013.
1, 2, 3, 4

[Blo16]

Thomas F Bloom. A quantitative improvement for Roth’s theorem on arithmetic progressions.
Journal of the London Mathematical Society, page jdw010, 2016. 19

[BPSY16]

Mario Blaum, James Plank, Moshe Schwartz, and Eitan Yaakobi. Construction of partial MDS
and sector-disk codes with two global parity symbols. IEEE Transactions on Information Theory,
62(5):2673–2681, 2016. 2, 3, 4, 6

[CHL07]

Minghua Chen, Cheng Huang, and Jin Li. On maximally recoverable property for multiprotection group codes. In IEEE International Symposium on Information Theory (ISIT), pages
486–490, 2007. 1, 3

[CK17]

Gokhan Calis and Ozan Koyluoglu. A general construction fo PMDS codes. IEEE Communications Letters, 21(3):452–455, 2017. 1, 2, 5

[DGW+ 10] Alexandros G. Dimakis, Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, and Kannan
Ramchandran. Network coding for distributed storage systems. IEEE Transactions on Information Theory, 56(9):4539–4551, 2010. 4
[Elk11]

Michael Elkin. An improved construction of progression-free sets. Israel journal of mathematics, 184(1):93–128, 2011. 19

[FY14]

Michael Forbes and Sergey Yekhanin. On the locality of codeword symbols in non-linear codes.
Discrete mathematics, 324:78–84, 2014. 21
22

[GHJY14]

Parikshit Gopalan, Cheng Huang, Bob Jenkins, and Sergey Yekhanin. Explicit maximally recoverable codes with locality. IEEE Transactions on Information Theory, 60(9):5245–5256, 2014.
2, 3, 5

[GHK+ 17] Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, and Sergey
Yekhanin. Maximally recoverable codes for grid-like topologies. In 28th Annual Symposium
on Discrete Algorithms (SODA), pages 2092–2108, 2017. 2, 3, 5
[GHSY12] Parikshit Gopalan, Cheng Huang, Huseyin Simitci, and Sergey Yekhanin. On the locality of
codeword symbols. IEEE Transactions on Information Theory, 58(11):6925 –6934, 2012. 3, 21
[Gop17]

Parikshit Gopalan. Personal communication, 2017. 10

[GW16]

Venkatesan Guruswami and Mary Wootters. Repairing Reed-Solomon codes. In 48th ACM
Symposium on Theory of Computing (STOC), pages 216–226, 2016. 4

[GYBS17]

Ryan Gabrys, Eitan Yaakobi, Mario Blaum, and Paul Siegel. Construction of partial MDS codes
over small ﬁnite ﬁelds. In 2017 IEEE International Symposium on Information Theory (ISIT),
pages 1–5, 2017. 2, 5

[HCL07]

Cheng Huang, Minghua Chen, and Jin Li. Pyramid codes: ﬂexible schemes to trade space
for access eﬃciency in reliable data storage systems. In 6th IEEE International Symposium on
Network Computing and Applications (NCA 2007), pages 79–86, 2007. 1, 3

[HSX+ 12] Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li,
and Sergey Yekhanin. Erasure coding in Windows Azure Storage. In USENIX Annual Technical
Conference (ATC), pages 15–26, 2012. 1
[HY16]

Guangda Hu and Sergey Yekhanin. New constructions of SD and MR codes over small ﬁnite
ﬁelds. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 1591–1595,
2016. 2

[Kle16]

Robert Kleinberg. A nearly tight upper bound on tri-colored sum-free sets in characteristic 2.
arXiv preprint arXiv:1605.08416, 2016. 20

[KLR17]

Daniel Kane, Shachar Lovett, and Sankeerth Rao. Labeling the complete bipartite graph with
no zero cycles. In 58th IEEE Symposium on Foundations of Computer Science (FOCS), 2017. 3

[LN83]

Rudolf Lidl and Harald Niederreiter. Finite Fields. Cambridge University Press, Cambridge,
1983. 3, 14

[MBG+ 13] A.J. Menezes, I.F. Blake, X.H. Gao, R.C. Mullin, S.A. Vanstone, and T. Yaghoobian. Applications of Finite Fields. The Springer International Series in Engineering and Computer Science.
Springer US, 2013. 20
[Mos53]

Leo Moser. On non-averaging sets of integers. Canadian Mathematical Society, 1953. 19

[MS77]

F. J. MacWilliams and N. J. A. Sloane. The Theory of Error Correcting Codes. North Holland,
Amsterdam, New York, 1977. 1, 4

[PD14]

Dimitris Papailiopoulos and Alexandros Dimakis. Locally repairable codes. IEEE Transactions
on Information Theory, 60(10):5843–5855, 2014. 1, 3

23

[PGM13]

J. S. Plank, K. M. Greenan, and E. L. Miller. Screaming fast Galois ﬁeld arithmetic using Intel
SIMD instructions. In 11th Usenix Conference on File and Storage Technologies (FAST), pages
299–306, San Jose, February 2013. 1

[SAP+ 13]

Maheswaran Sathiamoorthy, Megasthenis Asteris, Dimitris S. Papailiopoulos, Alexandros G.
Dimakis, Ramkumar Vadali, Scott Chen, and Dhruba Borthakur. XORing elephants: novel
erasure codes for big data. In Proceedings of VLDB Endowment (PVLDB), pages 325–336, 2013.
1, 21

[Sil09]

J.H. Silverman. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. Springer
New York, 2009. 20

[TB14]

Itzhak Tamo and Alexander Barg. A family of optimal locally recoverable codes. IEEE Transactions on Information Theory, 60:4661–4676, 2014. 1, 3

[TPD16]

Itzhak Tamo, Dimitris Papailiopoulos, and Alexandros G. Dimakis. Optimal locally repairable
codes and connections to matroid theory. IEEE Transactions on Information Theory, 62:6661–
6671, 2016. 2

[WTB17]

Zhiying Wang, Itzhak Tamo, and Jehoshua Bruck. Optimal rebuilding of multiple erasures in
MDS codes. IEEE Transactions on Information Theory, 63:1084–1101, 2017. 4

[YB17]

Min Ye and Alexander Barg. Explicit constructions of high-rate MDS array codes with optimal
repair bandwidth. IEEE Transactions on Information Theory, 63:2001–2014, 2017. 4

[Yek12]

Sergey Yekhanin. Locally decodable codes. Foundations and trends in theoretical computer
science, 6(3):139–255, 2012. 4

A Proof of Lemma 4.2
The goal of the section is to prove Lemma 4.2 which is restated here for convenience.
Lemma A.1 (Restatement of Lemma 4.2). Let r, n be some positive integers with r 6 n. Then there exists a
ﬁnite ﬁeld Fq with q = O(n) such that the multiplicative group Fq∗ contains a subgroup of size at least r and
with at least n/r cosets.
p If additionally we require that the ﬁeld has characteristic two, then such a ﬁeld exists
with q = n · exp(O( log n)).
We will need some estimates from analytic number theory, we will setup some notation ﬁrst.
π (x;m, a) : number of primes p 6 x such that p ≡ a

mod m

π (x, y;m, a) = π (y;m, a) − π (x;m, a)
∫ x
1
dt
Li(x) =
ln
t
2
(m, a) : greatest common divisor of m and a

ϕ(m) : number of positive integers a 6 m such that (a, m) = 1 (Euler’s totient function)
By the prime number theorem, the number of primes 6 x is approximately Li(x) = Θ(x/log x). So if
the primes are equidistributed among diﬀerent congruence classes of m with no obvious divisors (i.e. a
mod m where (a, m) = 1), then we expect to see approximately Li(x)/ϕ(m) primes in each such congruence
class. The following theorem gives an upper bound on the error term in this approximation averaged over
√
m < x(log x)A .
24

Theorem A.2 (Theorem from [BFI86] (Page 250)). Let a , 0, A > 0 be some ﬁxed constants and x > 3. We
then have
Õ
(log log x)B
Li(x)
.a,A x
π (x;m, a) −
ϕ(m)
(log x)3
√
A
(m,a)=1; m< x (log x )

where B is an absolute constant.
Applying the above theorem with a = 1, A = 0 for x and 2x, and using triangle inequality, we get the
following corollary.
Corollary A.3. For x large enough,
Õ

√
m< x

π (x, 2x;m, 1) −

(log log x)B
(Li(2x) − Li(x))
.x
ϕ(m)
(log x)3

where B is an absolute constant.
Lemma A.4. Let a 6 b be some positive integers. Then there exists A > a,B > b such that AB + 1 is a prime
and AB = O(ab).
Proof. If there exists some A such that a 6 A 6 2a and there is a prime p between 4ab + 1 and 8ab which
is congruent to 1 mod A, then we can take B = (p − 1)/A > b. Suppose this is not true, we will arrive at a
contradiction. For every a 6 m 6 2a, we have π (4ab, 8ab;m, 1) = 0. Applying corollary A.3 with x = 4ab,
we get
ab

(log log ab)B
&
(log ab)3

Õ

√
m<2 ab

Õ

>

Õ

a6m<2a

=

a6m<2a

>a

π (4ab, 8ab;m, 1) −

(Li(8ab) − Li(4ab))
ϕ(m)

π (4ab, 8ab;m, 1) −

(Li(8ab) − Li(4ab))
ϕ(m)

(Li(8ab) − Li(4ab))
ϕ(m)

Li(8ab) − Li(4ab)
ab
&
2a
log(ab)

which is a contradiction when ab is large enough.



In practice, it is desirable to work with ﬁelds of characteristic two, the following lemma gives us such
ﬁelds.
Lemma A.5. Let a, b be some positive integerspand let n = ab. Then there exists A > a, B > b such that
q = AB + 1 is a power of two and q = n · exp(O log n).
Proof. Let m be a positive integer to be chosen later. Let ℓ be an integer such that
m −1)

2ℓ(2

m −1)

> Cn + 1 > 2(ℓ−1)(2

m

where C > 1 is some suﬃciently large constant to be chosen later and let x = 2ℓ , q = x 2 . We will now
show that for any a 6 n, we can factor q − 1 as A · B where A > a and B > n/a = b. We can factor
m
q − 1 = x 2 − 1 as:
Ö
m
i −1
x 2 − 1 = (x − 1)
(1 + x 2 ).
i ∈[m]

25

We will rearrange these factors to get the desired factorization of q − 1. Let 0 6 α 6 2m − 1 be such that
Í
x α −1 < a 6 x α . Expand α into its binary expansion as α = i ∈S 2i where S ⊂ {0, 1, · · · , m − 1}. Deﬁne
Î
m
i
A = i ∈S (1 + x 2 ) and deﬁne B = (x 2 − 1)/A. Clearly A > x α > a. We can lower bound B as follows:
m
2m − 1)
Ö
(x 2 − 1)
−2i −1 (x
=
(1 + x ) · Î
B=Î
2i
2i
i ∈S (1 + x )
i ∈S x
i ∈S
2m − 1)
Õ j (x 2m − 1)
Õ
−2 j (x
> exp(−
2−2 )
> exp(−
x )
α
x
xa
j >0
j >0

> exp(−

Õ
j >0

j

2−2 )

m −1

(x 2

a

− 1)

> exp(−

Õ
j >0

j

2−2 )

Cn n
>
a
a

Í
m
j
when C = exp( j >0 2−2 ). Now we need to bound q = x 2 as a function of n.
m −1)

m

q = 2ℓ2 = 2(ℓ−1)(2

m −1

· 2ℓ · 22

m −1

6 (Cn + 1) · 2ℓ · 22
m −1)

. n 1+1/(2

m −1

· 22

p
. n exp(O( log n))

p
if we choose m such that (2m − 1) = Θ( log n).



We are now ready to prove Lemma 4.2.
Proof of Lemma 4.2. By Lemma A.4, there exists A > r and B > n/r such that q = AB + 1 is prime and
q = O(n). Since Fq∗ is a cyclic group of size q − 1 and A divides q − 1, there exists a subgroup of Fq∗ of size
A > r with B > n/r cosets. To get a ﬁnite ﬁeld of characteristic two, we use Lemma A.5 instead.


26

