arXiv:0704.1694v1  [cs.CC]  13 Apr 2007
Locally Decodable Codes From Nice Subsets of Finite Fields
and Prime Factors of Mersenne Numbers
Kiran S. Kedlaya
kedlaya@mit.edu
Sergey Yekhanin
yekhanin@mit.edu
Abstract
A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N -bit codeword C(x), such that
one can probabilistically recover any bit xi of the message by querying only k bits of the codeword C(x), even
after some constant fraction of codeword bits has been corrupted. The major goal of LDC related research is to
establish the optimal trade-off between length and query complexity of such codes.
Recently [34] introduced a novel technique for constructing locally decodable codes and vastly improved the
upper bounds for code length. The technique is based on Mersenne primes. In this paper we extend the work
of [34] and argue that further progress via these methods is tied to progress on an old number theory question
regarding the size of the largest prime factors of Mersenne numbers.
Specifically, we show that every Mersenne number m = 2t − 1 that has a prime factor p > mγ yields a family
of k(γ)-query locally decodable codes of length exp
. Conversely, if for some fixed k and all ǫ > 0 one can
use the technique of [34] to obtain a family of k-query LDCs of length exp (nǫ) ; then infinitely many Mersenne
numbers have prime factors larger than known currently.
1 Introduction
Classical error-correcting codes allow one to encode an n-bit string x into in N -bit codeword C(x), in such
a way that x can still be recovered even if C(x) gets corrupted in a number of coordinates. It is well-known
that codewords C(x) of length N = O(n) already suffice to correct errors in up to δN locations of C(x) for
any constant δ < 1/4. The disadvantage of classical error-correction is that one needs to consider all or most
of the (corrupted) codeword to recover anything about x. Now suppose that one is only interested in recovering
one or a few bits of x. In such case more efficient schemes are possible. Such schemes are known as locally
decodable codes (LDCs). Locally decodable codes allow reconstruction of an arbitrary bit xi, from looking only
at k randomly chosen coordinates of C(x), where k can be as small as 2. Locally decodable codes have numerous
applications in complexity theory [15, 29], cryptography [6, 11] and the theory of fault tolerant computation [24].
Below is a slightly informal definition of LDCs:
A (k, δ, ǫ)-locally decodable code encodes n-bit strings to N -bit codewords C(x), such that for every i ∈ [n],
the bit xi can be recovered with probability 1− ǫ, by a randomized decoding procedure that makes only k queries,
even if the codeword C(x) is corrupted in up to δN locations.
One should think of δ > 0 and ǫ < 1/2 as constants. The main parameters of interest in LDCs are the length
N and the query complexity k. Ideally we would like to have both of them as small as possible. The concept
of locally decodable codes was explicitly discussed in various papers in the early 1990s [2, 28, 21]. Katz and
http://arxiv.org/abs/0704.1694v1
Trevisan [15] were the first to provide a formal definition of LDCs. Further work on locally decodable codes
includes [3, 8, 20, 4, 16, 30, 34, 33, 14, 23].
Below is a brief summary of what was known regarding the length of LDCs prior to [34]. The length of optimal
2-query LDCs was settled by Kerenidis and de Wolf in [16] and is exp(n).1 The best upper bound for the length
of 3-query LDCs was exp
due to Beimel et al. [3], and the best lower bound is Ω̃(n2) [33]. For general
(constant) k the best upper bound was exp
nO(log log k/(k log k))
due to Beimel et al. [4] and the best lower bound
is Ω̃
n1+1/(⌈k/2⌉−1)
[33].
The recent work [34] improved the upper bounds to the extent that it changed the common perception of what
may be achievable [12, 11]. [34] introduced a novel technique to construct codes from so-called nice subsets
of finite fields and showed that every Mersenne prime p = 2t − 1 yields a family of 3-query LDCs of length
. Based on the largest known Mersenne prime [9], this translates to a length of less than exp
Combined with the recursive construction from [4], this result yields vast improvements for all values of k > 2. It
has often been conjectured that the number of Mersenne primes is infinite. If indeed this conjecture holds, [34] gets
three query locally decodable codes of length N = exp
log log n
for infinitely many n. Finally, assuming
that the conjecture of Lenstra, Pomerance and Wagstaff [31, 22, 32] regarding the density of Mersenne primes
holds, [34] gets three query locally decodable codes of length N = exp
log1−ǫ log n
for all n, for every ǫ >
1.1 Our results
In this paper we address two natural questions left open by [34]:
1. Are Mersenne primes necessary for the constructions of [34]?
2. Has the technique of [34] been pushed to its limits, or one can construct better codes through a more clever
choice of nice subsets of finite fields?
We extend the work of [34] and answer both of the questions above. In what follows let P (m) denote the
largest prime factor of m. We show that one does not necessarily need to use Mersenne primes. It suffices to have
Mersenne numbers with polynomially large prime factors. Specifically, every Mersenne number m = 2t − 1 such
that P (m) ≥ mγ yields a family of k(γ)-query locally decodable codes of length exp
. A partial converse
also holds. Namely, if for some fixed k ≥ 3 and all ǫ > 0 one can use the technique of [34] to (unconditionally)
obtain a family of k-query LDCs of length exp (nǫ) ; then for infinitely many t we have
P (2t − 1) ≥ (t/2)1+1/(k−2). (1)
The bound (1) may seem quite weak in light of the widely accepted conjecture saying that the number of
Mersenne primes is infinite. However (for any k ≥ 3) this bound is substantially stronger than what is currently
known unconditionally. Lower bounds for P (2t − 1) have received a considerable amount of attention in the
number theory literature [25, 26, 10, 27, 19, 18]. The strongest result to date is due to Stewart [27]. It says that
for all integers t ignoring a set of asymptotic density zero, and for all functions ǫ(t) > 0 where ǫ(t) tends to zero
monotonically and arbitrarily slowly:
P (2t − 1) > ǫ(t)t (log t)2 / log log t. (2)
1Throughout the paper we use the standard notation exp(x)
= eO(x).
There are no better bounds known to hold for infinitely many values of t, unless one is willing to accept some
number theoretic conjectures [19, 18]. We hope that our work will further stimulate the interest in proving lower
bounds for P (2t − 1) in the number theory community.
In summary, we show that one may be able to improve the unconditional bounds of [34] (say, by discovering a
new Mersenne number with a very large prime factor) using the same technique. However any attempts to reach
the exp (nǫ) length for some fixed query complexity and all ǫ > 0 require either progress on an old number theory
problem or some radically new ideas.
In this paper we deal only with binary codes for the sake of clarity of presentation. We remark however that
our results as well as the results of [34] can be easily generalized to larger alphabets. Such generalization will be
discussed in detail in [35].
1.2 Outline
In section 3 we introduce the key concepts of [34], namely that of combinatorial and algebraic niceness of
subsets of finite fields. We also briefly review the construction of locally decodable codes from nice subsets. In
section 4 we show how Mersenne numbers with large prime factors yield nice subsets of prime fields. In section 5
we prove a partial converse. Namely, we show that every finite field Fq containing a sufficiently nice subset, is an
extension of a prime field Fp, where p is a large prime factor of a large Mersenne number. Our main results are
summarized in sections 4.3 and 5.4.
2 Notation
We use the following standard mathematical notation:
• [s] = {1, . . . , s};
• Zn denotes integers modulo n;
• Fq is a finite field of q elements;
• dH(x, y) denotes the Hamming distance between binary vectors x and y;
• (u, v) stands for the dot product of vectors u and v;
• For a linear space L ⊆ Fm2 , L⊥ denotes the dual space. That is, L⊥ = {u ∈ Fm2 | ∀v ∈ L, (u, v) = 0};
• For an odd prime p, ord2(p) denotes the smallest integer t such that p | 2t − 1.
3 Nice subsets of finite fields and locally decodable codes
In this section we introduce the key technical concepts of [34], namely that of combinatorial and algebraic
niceness of subsets of finite fields. We briefly review the construction of locally decodable codes from nice
subsets. Our review is concise although self-contained. We refer the reader interested in a more detailed and
intuitive treatment of the construction to the original paper [34]. We start by formally defining locally decodable
codes.
Definition 1 A binary code C : {0, 1}n → {0, 1}N is said to be (k, δ, ǫ)-locally decodable if there exists a
randomized decoding algorithm A such that
1. For all x ∈ {0, 1}n, i ∈ [n] and y ∈ {0, 1}N such that dH(C(x), y) ≤ δN : Pr[Ay(i) = xi] ≥ 1− ǫ, where
the probability is taken over the random coin tosses of the algorithm A.
2. A makes at most k queries to y.
We now introduce the concepts of combinatorial and algebraic niceness of subsets of finite fields. Our defini-
tions are syntactically slightly different from the original definitions in [34]. We prefer these formulations since
they are more appropriate for the purposes of the current paper. In what follows let F∗q denote the multiplicative
group of Fq.
Definition 2 A set S ⊆ F∗q is called t combinatorially nice if for some constant c > 0 and every positive integer
m there exist two n = ⌊cmt⌋-sized collections of vectors {u1, . . . , un} and {v1, . . . , vn} in Fmq , such that
• For all i ∈ [n], (ui, vi) = 0;
• For all i, j ∈ [n] such that i 6= j, (uj , vi) ∈ S.
Definition 3 A set S ⊆ F∗q is called k algebraically nice if k is odd and there exists an odd k′ ≤ k and two sets
S0, S1 ⊆ Fq such that
• S0 is not empty;
• |S1| = k′;
• For all α ∈ Fq and β ∈ S : |S0 ∩ (α+ βS1)| ≡ 0 mod (2).
The following lemma shows that for an algebraically nice set S, the set S0 can always be chosen to be large. It
is a straightforward generalization of [34, lemma 15].
Lemma 4 Let S ⊆ F∗q be a k algebraically nice set. Let S0, S1 ⊆ Fq be sets from the definition of algebraic
niceness of S. One can always redefine the set S0 to satisfy |S0| ≥ ⌈q/2⌉.
Proof: Let L be the linear subspace of Fq2 spanned by the incidence vectors of the sets α+ βS1, for α ∈ Fq and
β ∈ S. Observe that L is invariant under the actions of a 1-transitive permutation group (permuting the coordinates
in accordance with addition in Fq). This implies that the space L
⊥ is also invariant under the actions of the same
group. Note that L⊥ has positive dimension since it contains the incidence vector of the set S0. The last two
observations imply that L⊥ has full support, i.e., for every i ∈ [q] there exists a vector v ∈ L⊥ such that vi 6= 0. It
is easy to verify that any linear subspace of Fq2 that has full support contains a vector of Hamming weight at least
⌈q/2⌉. Let v ∈ L⊥ be such a vector. Redefining the set S0 to be the set of nonzero coordinates of v we conclude
the proof.
We now proceed to the core proposition of [34] that shows how sets exhibiting both combinatorial and algebraic
niceness yield locally decodable codes.
Proposition 5 Suppose S ⊆ F∗q is t combinatorially nice and k algebraically nice; then for every positive integer
n there exists a code of length exp(n1/t) that is (k, δ, 2kδ) locally decodable for all δ > 0.
Proof: Our proof comes in three steps. We specify encoding and local decoding procedures for our codes and
then argue the lower bound for the probability of correct decoding. We use the notation from definitions 2 and 3.
Encoding: We assume that our message has length n = ⌊cmt⌋ for some value of m. (Otherwise we pad the
message with zeros. It is easy to see that such padding does not not affect the asymptotic length of the code.) Our
code will be linear. Therefore it suffices to specify the encoding of unit vectors e1, . . . , en, where ej has length n
and a unique non-zero coordinate j. We define the encoding of ej to be a q
m long vector, whose coordinates are
labelled by elements of Fmq . For all w ∈ Fmq we set:
Enc(ej)w =
1, if (uj , w) ∈ S0;
0, otherwise.
It is straightforward to verify that we defined a code encoding n bits to exp(n1/t) bits.
Local decoding: Given a (possibly corrupted) codeword y and an index i ∈ [n], the decoding algorithm A picks
w ∈ Fmq , such that (ui, w) ∈ S0 uniformly at random, reads k′ ≤ k coordinates of y, and outputs the sum:
yw+λvi . (4)
Probability of correct decoding: First we argue that decoding is always correct if A picks w ∈ Fmq such that
all bits of y in locations {w + λvi}λ∈S1 are not corrupted. We need to show that for all i ∈ [n], x ∈ {0, 1}n and
w ∈ Fmq , such that (ui, w) ∈ S0:
xj Enc(ej)
w+λvi
= xi. (5)
Note that
xj Enc(ej)
w+λvi
Enc(ej)w+λvi =
I [(uj , w + λvi) ∈ S0] , (6)
where I[γ ∈ S0] = 1 if γ ∈ S0 and zero otherwise. Now note that
I [(uj , w + λvi) ∈ S0] =
I [(uj , w) + λ(uj , vi) ∈ S0] =
1, if i = j,
0, otherwise.
The last identity in (7) for i = j follows from: (ui, vi) = 0, (ui, w) ∈ S0 and k′ = |S1| is odd. The last identity
for i 6= j follows from (uj , vi) ∈ S and the algebraic niceness of S. Combining identities (6) and (7) we get (5).
Now assume that up to δ fraction of bits of y are corrupted. Let Ti denote the set of coordinates whose labels
belong to
w ∈ Fmq | (ui, w) ∈ S0
. Recall that by lemma 4, |Ti| ≥ qm/2. Thus at most 2δ fraction of coor-
dinates in Ti contain corrupted bits. Let Qi =
{w + λvi}λ∈S1 | w : (ui, w) ∈ S0
be the family of k′-tuples
of coordinates that may be queried by A. (ui, vi) = 0 implies that elements of Qi uniformly cover the set Ti.
Combining the last two observations we conclude that with probability at least 1 − 2kδ A picks an uncorrupted
k′-tuple and outputs the correct value of xi.
All locally decodable codes constructed in this paper are obtained by applying proposition 5 to certain nice
sets. Thus all our codes have the same dependence of ǫ (the probability of the decoding error) on δ (the fraction
of corrupted bits). In what follows we often ignore these parameters and consider only the length and query
complexity of codes.
4 Mersenne numbers with large prime factors yield nice subsets of prime fields
In what follows let 〈2〉 ⊆ F∗p denote the multiplicative subgroup of F∗p generated by 2. In [34] it is shown
that for every Mersenne prime p = 2t − 1 the set 〈2〉 ⊆ F∗p is simultaneously 3 algebraically nice and ord2(p)
combinatorially nice. In this section we prove the same conclusion for a substantially broader class of primes.
Lemma 6 Suppose p is an odd prime; then 〈2〉 ⊆ F∗p is ord2(p) combinatorially nice.
Proof: Let t = ord2(p). Clearly, t divides p− 1. We need to specify a constant c > 0 such that for every positive
integer m there exist two n = ⌊cmt⌋-sized collections of m long vectors over Fp satisfying:
• For all i ∈ [n], (ui, vi) = 0;
• For all i, j ∈ [n] such that i 6= j, (uj , vi) ∈ 〈2〉.
First assume that m has the shape m =
m′−1+(p−1)/t
(p−1)/t
, for some integer m′ ≥ p − 1. In this case [34, lemma
13] gives us a collection of n =
vectors with the right properties. Observe that n ≥ cmt for a constant
c that depends only on p and t. Now assume m does not have the right shape, and let m1 be the largest integer
smaller than m that does have it. In order to get vectors of length m we use vectors of length m1 coming from [34,
lemma 13] padded with zeros. It is not hard to verify such a construction still gives us n ≥ cmt large families of
vectors for a suitably chosen constant c.
We use the standard notation F to denote the algebraic closure of the field F. Also let Cp ⊆ F
2 denote the
multiplicative subgroup of p-th roots of unity in F2. The next lemma generalizes [34, lemma 14].
Lemma 7 Let p be a prime and k be odd. Suppose there exist ζ1, . . . , ζk ∈ Cp such that
ζ1 + . . . + ζk = 0; (8)
then 〈2〉 ⊆ F∗p is k algebraically nice.
Proof: In what follows we define the set S1 ⊆ Fp and prove the existence of a set S0 such that that together S0
and S1 yield k algebraic niceness of 〈2〉. Identity 8 implies that there exists an odd integer k′ ≤ k and k′ distinct
p-th roots of unity ζ ′1, . . . , ζ
k ∈ Cp such that
ζ ′1 + . . . + ζ
k′ = 0. (9)
Let t = ord2(p). Observe that Cp ⊆ F2t . Let g be a generator of Cp. Identity (9) yields gγ1 + . . .+ gγk′ = 0, for
some distinct values of {γi}i∈[k′]. Set S1 = {γ1, . . . , γk′}.
Consider a natural one to one correspondence between subsets S′ of Fp and polynomials φS′(x) in the ring
F2[x]/(x
p − 1) : φS′(x) =
xs. It is easy to see that for all sets S′ ⊆ Fp and all α, β ∈ Fp, such that β 6= 0 :
φα+βS′(x) = x
αφS′(x
Let α be a variable ranging over Fp and β be a variable ranging over 〈2〉. We are going to argue the existence of a
set S0 that has even intersections with all sets of the form α+βS1, by showing that all polynomials φα+βS1 belong
to a certain linear space L ∈ F2[x]/(xp − 1) of dimension less than p. In this case any nonempty set T ⊆ Fp such
that φT ∈ L⊥ can be used as the set S0. Let τ(x) = gcd(xp−1, φS1(x)). Note that τ(x) 6= 1 since g is a common
root of xp−1 and φS1(x). Let L be the space of polynomials in F2[x]/(xp−1) that are multiples of τ(x). Clearly,
dimL = p− deg τ. Fix some α ∈ Fp and β ∈ 〈2〉. Let us prove that φα+βS1(x) is in L :
φα+βS1(x) = x
αφS1(x
β) = xα(φS1(x))
The last identity above follows from the fact that for any f ∈ F2[x] and any integer i : f(x2
) = (f(x))2
In what follows we present sufficient conditions for the existence of k-tuples of p-th roots of unity in F2 that
sum to zero. We treat the k = 3 case separately since in that case we can use a specialized argument to derive a
more explicit conclusion.
4.1 A sufficient condition for the existence of three p-th roots of unity summing to zero
Lemma 8 Let p be an odd prime. Suppose ord2(p) < (4/3) log2 p; then there exist three p-th roots of unity in F2
that sum to zero.
Proof: We start with a brief review of some basic concepts of projective algebraic geometry. Let F be a field, and
f ∈ F[x, y, z] be a homogeneous polynomial. A triple (x0, y0, z0) ∈ F3 is called a zero of f if f(x0, y0, z0) = 0.
A zero is called nontrivial if it is different from the origin. An equation f = 0 defines a projective plane curve χf .
Nontrivial zeros of f considered up to multiplication by a scalars are called F-rational points of χf . If F is a finite
field it makes sense to talk about the number of F-rational points on a curve.
Let t = ord2(p). Note that Cp ⊆ F2t . Consider a projective plane Fermat curve χ defined by
t−1)/p + y(2
t−1)/p + z(2
t−1)/p = 0. (10)
Let us call a point a on χ trivial if one of the coordinates of a is zero. Cyclicity of F∗
implies that χ contains
exactly 3(2t − 1)/p trivial F2t-rational points. Note that every nontrivial point of χ yields a triple of elements of
Cp that sum to zero. The classical Weil bound [17, p. 330] provides an estimate
|Nq − (q + 1)| ≤ (d− 1)(d − 2)
q (11)
for the number Nq of Fq-rational points on an arbitrary smooth projective plane curve of degree d. (11) implies
that in case
2t + 1 >
2t − 1
2t − 1
2t/2 + 3
2t − 1
there exists a nontrivial point on the curve (10). Note that (12) follows from
2t + 1 >
2t/2 −
23t/2+1
3 ∗ 2t
, (13)
and (13) follows from
2t > 22t+t/2/p2 and 2t/2+1 > 3.
Now note that the first inequality above follows from t < (4/3) log2 p and the second follows from t > 1.
Note that the constant 4/3 in lemma 8 cannot be improved to 2: there are no three elements of C13264529 that
sum to zero, even though ord2(13264529) = 47 < 2 ∗ log2 13264529 ≈ 47.3.
4.2 A sufficient condition for the existence of k p-th roots of unity summing to zero
Our argument in this section comes in three steps. First we briefly review the notion of (additive) Fourier
coefficients of subsets of F2t . Next, we invoke a folklore argument to show that subsets of F2t with appropriately
small nontrivial Fourier coefficients contain k-tuples of elements that sum to zero. Finally, we use a recent result of
Bourgain and Chang [5] (generalizing the classical estimate for Gauss sums) to argue that (under certain constraints
on p) all nontrivial Fourier coefficients of Cp are small.
For x ∈ F2t let Tr(x) = x + x2 + . . . + x2
denote the trace of x. It is not hard to verify that for all x,
Tr(x) ∈ F2. Characters of F2t are homomorphisms from the additive group of F2t into the multiplicative group
{±1}. There exist 2t characters. We denote characters by χa, where a ranges in F2t , and set χa(x) = (−1)Tr(ax).
Let C(x) denote the incidence function of a set C ⊆ F2t . For arbitrary a ∈ Ft2 the Fourier coefficient χa(C) is
defined by χa(C) =
χa(x)C(x), where the sum is over all x ∈ F2t . Fourier coefficient χ0(C) = |C| is called
trivial, and other Fourier coefficients are called nontrivial. In what follows
χ stands for summation over all 2
characters of F2t . We need the following two standard properties of characters and Fourier coefficients.
χ(x) =
2t, if x = 0;
0, otherwise.
χ2(C) = 2t|C|. (15)
The following lemma is a folklore.
Lemma 9 Let C ⊆ F2t and k ≥ 3 be a positive integer. Let F be the largest absolute value of a nontrivial Fourier
coefficient of C. Suppose
)1/(k−2)
then there exist k elements of C that sum to zero.
Proof: Let M(C) = # {ζ1, . . . , ζk ∈ C | ζ1 + . . .+ ζk = 0} . (14) yields
M(C) =
x1,...,xk∈F2t
C(x1) . . . C(xk)
χ(x1 + . . .+ xk). (17)
Note that χ(x1 + . . .+ xk) = χ(x1) . . . χ(xk). Changing the order of summation in (17) we get
M(C) =
x1,...,xk∈F2t
C(x1) . . . C(xk)χ(x1) . . . χ(xk) =
χk(C). (18)
Note that
χk(C) =
χ 6=χ0
χk(C) ≥
− F k−2
χ2(C) =
− F k−2|C|, (19)
where the last identity follows from (15). Combining (18) and (19) we conclude that (16) implies M(C) > 0.
The following lemma is a special case of [5, theorem 1].
Lemma 10 Assume that n | 2t − 1 and satisfies the condition
2t − 1
′ − 1
< 2t(1−ǫ)−t
, for all 1 ≤ t′ < t, t′ | t,
where ǫ > 0 is arbitrary and fixed. Then for all a ∈ F∗
x∈F2t
(−1)Tr(axn)
< c12
t(1−δ), (20)
where δ = δ(ǫ) > 0 and c1 = c1(ǫ) are absolute constants.
Below is the main result of this section. Recall that Cp denotes the set of p-th roots of unity in F2.
Lemma 11 For every c > 0 there exists an odd integer k = k(c) such that the following implication holds. If p is
an odd prime and ord2(p) < c log2 p then some k elements of Cp sum to zero.
Proof: Note that if there exist k′ elements of a set C ⊆ F2 that sum to zero, where k′ is odd; then there exist
k elements of C that sum to zero for every odd k ≥ k′. Also note that the sum of all p-th roots of unity is
zero. Therefore given c it suffices to prove the existence of an odd k = k(c) that works for all sufficiently large
p. Let t = ord2(p). Observe that p > 2
t/c. Assume p is sufficiently large so that t > 2c. Next we show that
the precondition of lemma 10 holds for n = (2t − 1)/p and ǫ = 1/(2c). Let t′ | t and 1 ≤ t′ < t. Clearly
gcd(2t
′ − 1, p) = 1. Therefore
2t − 1
2t − 1
′ − 1
2t − 1
′ − 1)
2t(1−1/c)
′ − 1
, (21)
where the inequality follows from p > 2t/c. Clearly, t > 2c yields 2t/(2c)/2 > 1. Multiplying the right hand side
of (21) by 2t/(2c)/2 and using 2(2t
′ − 1) > 2t′ we get
2t − 1
2t − 1
′ − 1
< 2t(1−1/(2c))−t
. (22)
Combining (22) with lemma 10 we conclude that there exist δ > 0 and c1 such that for all a ∈ F∗2t
x∈F2t
(−1)Tr
−1)/p
< c12
t(1−δ). (23)
Observe that x(2
t−1)/p takes every value in Cp exactly (2
t−1)/p times when x ranges over F∗
. Thus (23) implies
(2t − 1)(F/p) < c12t(1−δ), (24)
where F denotes that largest nontrivial Fourier coefficient of Cp. (24) yields F/p < (2c1)2
−δt. Pick k ≥ 3 to be
the smallest odd integer such that (1 − 1/c)/(k − 2) < δ. We now have
(1−1/c)t
(k−2) (25)
for all sufficiently large values of p. Combining p > 2t/c with (25) we get
)1/(k−2)
and the application of lemma 9 concludes the proof.
4.3 Summary
In this section we summarize our positive results and show that one does not necessarily need to use Mersenne
primes to construct locally decodable codes via the methods of [34]. It suffices to have Mersenne numbers with
polynomially large prime factors. Recall that P (m) denotes the largest prime factor of an integer m. Our first
theorem gets 3-query LDCs from Mersenne numbers m with prime factors larger than m3/4.
Theorem 12 Suppose P (2t − 1) > 20.75t; then for every message length n there exists a three query locally
decodable code of length exp(n1/t).
Proof: Let P (2t − 1) = p. Observe that p | 2t − 1 and p > 20.75t yield ord2(p) < (4/3) log2 p. Combining
lemmas 8,7 and 6 with proposition 5 we obtain the statement of the theorem.
As an example application of theorem 12 one can observe that P (223−1) = 178481 > 2(3/4)∗23 ≈ 155872 yields
a family of three query locally decodable codes of length exp(n1/23). Theorem 12 immediately yields:
Theorem 13 Suppose for infinitely many t we have P (2t − 1) > 20.75t; then for every ǫ > 0 there exists a family
of three query locally decodable codes of length exp(nǫ).
The next theorem gets constant query LDCs from Mersenne numbers m with prime factors larger than mγ for
every value of γ.
Theorem 14 For every γ > 0 there exists an odd integer k = k(γ) such that the following implication holds.
Suppose P (2t − 1) > 2γt; then for every message length n there exists a k query locally decodable code of length
exp(n1/t).
Proof: Let P (2t − 1) = p. Observe that p | 2t − 1 and p > 2γt yield ord2(p) < (1/γ) log2 p. Combining
lemmas 22,7 and 6 with proposition 5 we obtain the statement of the theorem.
As an immediate corollary we get:
Theorem 15 Suppose for some γ > 0 and infinitely many t we have P (2t − 1) > 2γt; then there is a fixed k such
that for every ǫ > 0 there exists a family of k query locally decodable codes of length exp(nǫ).
5 Nice subsets of finite fields yield Mersenne numbers with large prime factors
Definition 16 We say that a sequence
Si ⊆ F∗qi
of subsets of finite fields is k-nice if every Si is k alge-
braically nice and t(i) combinatorially nice, for some integer valued monotonically increasing function t.
The core proposition 5 asserts that a subset S ⊆ F∗q that is k algebraically nice and t combinatorially nice yields
a family of k-query locally decodable codes of length exp(n1/t). Clearly, to get k-query LDCs of length exp(nǫ)
for some fixed k and every ǫ > 0 via this proposition, one needs to exhibit a k-nice sequence. In this section
we show how the existence of a k-nice sequence implies that infinitely many Mersenne numbers have large prime
factors. Our argument proceeds in two steps. First we show that a k-nice sequence yields an infinite sequence of
primes {pi}i≥1 , where every Cpi contains a k-tuple of elements summing to zero. Next we show that Cp contains
a short additive dependence only if p is a large factor of a Mersenne number.
5.1 A nice sequence yields infinitely many primes p with short dependencies between p-th roots of unity
We start with some notation. Consider a a finite field Fq = Fpl, where p is prime. Fix a basis e1, . . . , el of Fq
over Fp. In what follows we often write (α1, . . . , αl) ∈ Flp to denote α =
i=1 αiei ∈ Fq. Let R denote the ring
F2[x1, . . . , xl]/(x
1 − 1, . . . , x
l − 1). Consider a natural one to one correspondence between subsets S1 of Fq and
polynomials φS1(x1, . . . , xl) ∈ R.
φS1(x1, . . . , xl) =
(α1,...,αl)∈S1
1 . . . x
It is easy to see that for all sets S1 ⊆ Fq and all α, β ∈ Fq :
φ(α1,...,αl)+βS1(x1, . . . , xl) = x
1 . . . x
φβS1(x1, . . . , xl). (26)
Let Γ be a family of subsets of Fq. It is straightforward to verify that a set S0 ⊆ Fq has even intersections with
every element of Γ if and only if φS0 belongs to L
⊥, where L is the linear subspace of R spanned by {φS1}S1∈Γ .
Combining the last observation with formula (26) we conclude that a set S ⊆ F∗q is k algebraically nice if and
only if there exists a set S1 ⊆ Fq of odd size k′ ≤ k such that the ideal generated by polynomials {φβS1}{β∈S}
is a proper ideal of R. Note that polynomials {f1, . . . , fh} ∈ R generate a proper ideal if an only if polynomials
{f1, . . . , fh, xp1 − 1, . . . , x
l − 1} generate a proper ideal in F2[x1, . . . , xl]. Also note that a family of polynomials
generates a proper ideal in F2[x1, . . . , xl] if and only if it generates a proper ideal in F2[x1, . . . , xl]. Now an
application of Hilbert’s Nullstellensatz [7, p. 168] implies that a set S ⊆ F∗q is k algebraically nice if and only
if there is a set S1 ⊆ Fq of odd size k′ ≤ k such that the polynomials {φβS1}{β∈S} and {x
i − 1}1≤i≤l have a
common root in F2.
Lemma 17 Let Fq = Fpl , where p is prime. Suppose Fq contains a nonempty k algebraically nice subset; then
there exist ζ1, . . . , ζk ∈ Cp such that ζ1 + . . .+ ζk = 0.
Proof: Assume S ⊆ F∗q is nonempty and k algebraically nice. The discussion above implies that there exists
S1 ⊆ Fq of odd size k′ ≤ k such that all polynomials {φβS1}{β∈S} vanish at some (ζ1, . . . , ζl) ∈ C
p. Fix an
arbitrary β0 ∈ S, and note that Cp is closed under multiplication. Thus,
φβ0S1(ζ1, . . . , ζl) = 0 (27)
yields k′ p-th roots of unity that add up to zero. It is readily seen that one can extend (27) (by adding an appropriate
number of pairs of identical roots) to obtain k p-th roots of unity that add up to zero for any odd k ≥ k′.
Note that lemma 17 does not suffice to prove that a k-nice sequence
Si ⊆ F∗qi
yields infinitely many primes p
with short (nontrivial) additive dependencies in Cp. We need to argue that the set {charFqi}i≥1 can not be finite. To
proceed, we need some more notation. Recall that q = pl and p is prime. For x ∈ Fq let Tr(x) = x+. . .+xp
l−1 ∈
Fp denote the (absolute) trace of x. For γ ∈ Fq, c ∈ F∗p we call the set πγ,c = {x ∈ Fq | Tr(γx) = c} a proper
affine hyperplane of Fq.
Lemma 18 Let Fq = Fpl , where p is prime. Suppose S ⊆ F∗q is k algebraically nice; then there exist h ≤ pk
proper affine hyperplanes {πγi,ci}1≤i≤h of Fq such that S ⊆
πγi,ci.
Proof: Discussion preceding lemma 17 implies that there exists a set S1 = {σ1, . . . , σk′} ⊆ Fq of odd size
k′ ≤ k such that all polynomials {φβS1}{β∈S} vanish at some (ζ1, . . . , ζl) ∈ C
p. Let ζ be a generator of Cp. For
every 1 ≤ i ≤ l pick ωi ∈ Zp such that ζi = ζωi . For every β ∈ S, φβS1(ζ1, . . . , ζl) = 0 yields
µ=(µ1,...,µl)∈βS1
i=1 µiωi = 0. (28)
Observe that for fixed values {ωi}1≤i≤l ∈ Zp the map D(µ) =
i=1 µiωi is a linear map from Fq to Fp. It is
not hard to prove that every such map can be expressed as D(µ) = Tr(δµ) for an appropriate choice of δ ∈ Fq.
Therefore we can rewrite (28) as
µ∈βS1
ζTr(δµ) =
ζTr(δβσ) = 0. (29)
Let W =
(w1, . . . , wk′) ∈ Zk
p | ζw1 + . . . + ζwk′ = 0
denote the set of exponents of k′-dependencies be-
tween powers of ζ. Clearly, |W | ≤ pk. Identity (29) implies that every β ∈ S satisfies
Tr((δσ1)β) = w1,
Tr((δσk′)β) = wk′ ;
for an appropriate choice of (w1, . . . , wk′) ∈ W. Note that the all-zeros vector does not lie in W since k′ is odd.
Therefore at least one of the identities in (30) has a non-zero right-hand side, and defines a proper affine hyperplane
of Fq. Collecting one such hyperplane for every element of W we get a family of |W | proper affine hyperplanes
containing every element of S.
Lemma 18 gives us some insight into the structure of algebraically nice subsets of Fq. Our next goal is to develop
an insight into the structure of combinatorially nice subsets. We start by reviewing some relations between tensor
and dot products of vectors. For vectors u ∈ Fmq and v ∈ Fnq let u⊗v ∈ Fmnq denote the tensor product of u and v.
Coordinates of u⊗ v are labelled by all possible elements of [m]× [n] and (u⊗ v)i,j = uivj . Also, let u⊗l denote
the l-the tensor power of u and u ◦ v denote the concatenation of u and v. The following identity is standard. For
any u, x ∈ Fmq and v, y ∈ Fnq :
(u⊗ v, x⊗ y) =
i∈[m],j∈[n]
uivjxiyj =
i∈[m]
j∈[n]
 = (u, x)(v, y). (31)
In what follows we need a generalization of identity (31). Let f(x1, . . . , xh) =
i cix
1 . . . x
h be a polynomial
in Fq[x1, . . . , xh]. Given f we define f̄ ∈ Fq[x1, . . . , xh] by f̄ =
1 . . . x
, i.e., we simply set all nonzero
coefficients of f to 1. For vectors u1, . . . , uh in F
q define
f(u1, . . . , uh) = ◦i ciu
1 ⊗ . . .⊗ u
h . (32)
Note that to obtain f(u1, . . . , uh) we replaced products in f by tensor products and addition by concatenation.
Clearly, f(u1, . . . , uh) is a vector whose length may be larger than m.
Claim 19 For every f ∈ Fq[x1, . . . , xh] and u1, . . . , uh, v1, . . . , vh ∈ Fmq :
f(u1, . . . , uh), f̄(v1, . . . , vh)
= f((u1, v1), . . . , (uh, vh)). (33)
Proof: Let u = (u1, . . . , uh) and v = (v1, . . . , vh). Observe that if (33) holds for polynomials f1 and f2 defined
over disjoint sets of monomials then it also holds for f = f1 + f2 :
f(u), f̄(v)
(f1 + f2)(u), (f̄1 + f̄2)(v)
f1(u) ◦ f2(u), f̄1(v) ◦ f̄2(v)
f1 ((u1, v1), . . . , (uh, vh)) + f2 ((u1, v1), . . . , (uh, vh)) = f ((u1, v1), . . . , (uh, vh)) .
Therefore it suffices to prove (33) for monomials f = cxα11 . . . x
. It remains to notice identity (33) for monomi-
als f = cxα11 . . . x
h follows immediately from formula (31) using induction on
i=1 αi.
The next lemma bounds combinatorial niceness of certain subsets of F∗q.
Lemma 20 Let Fq = Fpl, where p is prime. Let S ⊆ F∗q. Suppose there exist h proper affine hyperplanes
{πγr ,cr}1≤r≤h of Fq such that S ⊆
πγr ,cr ; then S is at most h(p − 1) combinatorially nice.
Proof: Assume S is t combinatorially nice. This implies that for some c > 0 and every m there exist two
n = ⌊cmt⌋-sized collections of vectors {ui}i∈[n] and {vi}i∈[n] in Fmq , such that:
• For all i ∈ [n], (ui, vi) = 0;
• For all i, j ∈ [n] such that i 6= j, (uj , vi) ∈ S.
For a vector u ∈ Fmq and integer e let ue denote a vector resulting from raising every coordinate of u to the power e.
For every i ∈ [n] and r ∈ [h] define vectors u(r)i and v
i in F
i = (γrui) ◦ (γrui)
p ◦ . . . ◦ (γrui)p
and v
i = vi ◦ v
i ◦ . . . ◦ v
i . (34)
Note that for every r1, r2 ∈ [h], v
i = v
i . It is straightforward to verify that for every i, j ∈ [n] and r ∈ [h] :
j , v
= Tr(γr(uj , vi)). (35)
Combining (35) with the fact that S is covered by proper affine hyperplanes πγi,ci we conclude that
• For all i ∈ [n] and r ∈ [h],
i , v
• For all i, j ∈ [n] such that i 6= j, there exists r ∈ [h] such that
j , v
∈ F∗p.
Pick g(x1, . . . , xh) ∈ Fp[x1, . . . , xh] to be a homogeneous degree h polynomial such that for a = (a1, . . . , ah) ∈
p : g(a) = 0 if and only if a is the all-zeros vector. The existence of such a polynomial g follows from [17,
Example 6.7]. Set f = gp−1. Note that for a ∈ Fhp : f(a) = 0 if a is the all-zeros vector, and f(a) = 1 otherwise.
For all i ∈ [n] define
u′i = f
i , . . . , u
◦ (1) and v′i = f̄
i , . . . , v
◦ (−1). (36)
Note that f and f̄ are homogeneous degree (p − 1)h polynomials in h variables. Therefore (32) implies that
for all i vectors u′i and v
i have length m
′ ≤ h(p−1)h(ml)(p−1)h. Combining identities (36) and (33) and using the
properties of dot products between vectors
discussed above we conclude that for every m there
exist two n = ⌊cmt⌋-sized collections of vectors {u′i}i∈[n] and {v′i}i∈[n] in Fm
q , such that:
• For all i ∈ [n], (u′i, v′i) = −1;
• For all i, j ∈ [n] such that i 6= j, (uj , vi) = 0.
It remains to notice that a family of vectors with such properties exists only if n ≤ m′, i.e., ⌊cmt⌋ ≤ h(p−1)h(ml)(p−1)h.
Given that we can pick m to be arbitrarily large, this implies that t ≤ (p− 1)h.
The next lemma presents the main result of this section.
Lemma 21 Let k be an odd integer. Suppose there exists a k-nice sequence; then for infinitely many primes p
some k of elements of Cp add up to zero.
Proof: Assume
Si ⊆ F∗qi
is k-nice. Let p be a fixed prime. Combining lemmas 18 and 20 we conclude
that every k algebraically nice subset S ⊆ F∗
is at most (p − 1)pk combinatorially nice. Note that our bound on
combinatorial niceness is independent of l. Therefore there are only finitely many extensions of the field Fp in the
sequence {Fqi}i≥1 , and the set P = {charFqi}i≥1 is infinite. It remains to notice that according to lemma 17 for
every p ∈ P there exist k elements of Cp that add up to zero.
In what follows we present necessary conditions for the existence of k-tuples of p-th roots of unity in F2 that
sum to zero. We treat the k = 3 case separately since in that case we can use a specialized argument to derive a
slightly stronger conclusion.
5.2 A necessary condition for the existence of k p-th roots of unity summing to zero
Lemma 22 Let k ≥ 3 be odd and p be a prime. Suppose there exist ζ1, . . . , ζk ∈ Cp such that
i=1 ζi = 0; then
ord2(p) ≤ 2p1−1/(k−1). (37)
Proof: Let t = ord2(p). Note that Cp ⊆ F2t . Note also that all elements of Cp other than the multiplicative
identity are proper elements of F2t. Therefore for every ζ ∈ Cp where ζ 6= 1 and every f(x) ∈ F2[x] such that
deg f ≤ t− 1 we have: f(ζ) 6= 0.
By multiplying
i=1 ζi = 0 through by ζ
, we may reduce to the case ζk = 1. Let ζ be the generator of Cp.
For every i ∈ [k − 1] pick wi ∈ Zp such that ζi = ζwi . We now have
i=1 ζ
wi + 1 = 0. Set h = ⌊(t − 1)/2⌋.
Consider the (k − 1)-tuples:
(mw1 + i1, . . . ,mwk−1 + ik−1) ∈ Zk−1p , for m ∈ Zp and i1, . . . , ik−1 ∈ [0, h]. (38)
Suppose two of these coincide, say
(mw1 + i1, . . . ,mwk−1 + ik−1) = (m
′w1 + i
1, . . . ,m
′wk−1 + i
k−1),
with (m, i1, . . . , ik−1) 6= (m′, i′1, . . . , i′k−1). Set n = m−m′ and jl = i′l − il for l ∈ [k − 1]. We now have
(nw1, . . . , nwk−1) = (j1, . . . , jl)
with −h ≤ j1, . . . , jk−1 ≤ h. Observe that n 6= 0, and thus it has a multiplicative inverse g ∈ Zp. Consider a
polynomial
P (z) = zj1+h + . . .+ zjk−1+h + zh ∈ F2[z].
Note that degP ≤ 2h ≤ t − 1. Note also that P (1) = 1 and P (ζg) = 0. The latter identity contradicts the fact
that ζg is a proper element of F2t . This contradiction implies that all (k−1)-tuples in (38) are distinct. This yields
pk−1 ≥ p
which is equivalent to (37).
5.3 A necessary condition for the existence of three p-th roots of unity summing to zero
In this section we slightly strengthen lemma 22 in the special case when k = 3. Our argument is loosely inspired
by the Agrawal-Kayal-Saxena deterministic primality test [1].
Lemma 23 Let p be a prime. Suppose there exist ζ1, ζ2, ζ3 ∈ Cp that sum up to zero; then
ord2(p) ≤ ((4/3)p)1/2 . (39)
Proof: Let t = ord2(p). Note that Cp ⊆ F2t . Note also that all elements of Cp other than the multiplicative
identity are proper elements of F2t. Therefore for every ζ ∈ Cp where ζ 6= 1 and every f(x) ∈ F2[x] such that
deg f ≤ t− 1 we have: f(ζ) 6= 0.
Observe that ζ1 + ζ2 + ζ3 = 0 implies ζ1ζ
2 + 1 = ζ3ζ
2 . This yields
2 + 1
= 1. Put ζ = ζ1ζ
Note that ζ 6= 1 and ζ, 1 + ζ ∈ Cp. Consider the products πi,j = ζ i(1 + ζ)j ∈ Cp for 0 ≤ i, j ≤ t− 1. Note that
πi,j, πk,l cannot be the same if i ≥ k and l ≥ j, as then
ζ i−k − (1 + ζ)l−j = 0,
but the left side has degree less than t. In other words, if πi,j = πk,l and (i, j) 6= (k, l), then the pairs (i, j) and
(k, l) are comparable under termwise comparison. In particular, either (k, l) = (i+a, j+b) or (i, j) = (k+a, l+b)
for some pair (a, b) with πa,b = 1.
We next check that there cannot be two distinct nonzero pairs (a, b), (a′, b′) with πa,b = πa′,b′ = 1. As above,
these pairs must be comparable; we may assume without loss of generality that a ≤ a′, b ≤ b′. The equations
πa,b = 1 and πa′−a,b′−b = 1 force a + b ≥ t and (a′ − a) + (b′ − b) ≥ t, so a′ + b′ ≥ 2t. But a′, b′ ≤ t − 1,
contradiction.
If there is no nonzero pair (a, b) with 0 ≤ a, b ≤ t − 1 and πa,b = 1, then all πi,j are distinct, so p ≥ t2.
Otherwise, as above, the pair (a, b) is unique, and the pairs (i, j) with 0 ≤ i, j ≤ t − 1 and (i, j) 6≥ (a, b) are
pairwise distinct. The number of pairs excluded by the condition (i, j) 6≥ (a, b) is (t− a)(t− b); since a+ b ≥ t,
(t− a)(t− b) ≤ t2/4. Hence p ≥ t2 − t2/4 = 3t2/4 as desired.
While the necessary condition given by lemma 23 is quite far away from the sufficient condition given by
lemma 8, it nonetheless suffices for checking that for most primes p, there do not exist three p-th roots of unity
summing to zero. For instance, among the 664578 odd primes p ≤ 108, all but 550 are ruled out by Lemma 23.
(There is an easy argument that t must be odd if p > 3; this cuts the list down to 273 primes.) Each remaining
p can be tested by computing gcd(xp + 1, (x + 1)p + 1); the only examples we found that did not satisfy the
condition of lemma 8 were (p, t) = (73, 9), (262657, 27), (599479, 33), (121369, 39).
5.4 Summary
In the beginning of this section 5 we argued that in order to use the method of [34], (i.e., proposition 5) to obtain
k-query locally decodable codes of length exp(nǫ) for some fixed k and all ǫ > 0, one needs to exhibit a k-nice
sequence of subsets of finite fields. In what follows we use technical results of the previous subsections to show
that the existence of a k-nice sequence implies that infinitely many Mersenne numbers have large prime factors.
Theorem 24 Let k be odd. Suppose there exists a k-nice sequence of subsets of finite fields; then for infinitely
many values of t we have
P (2t − 1) ≥ (t/2)1+1/(k−2). (40)
Proof: Using lemmas 21 and 22 we conclude that a k-nice sequence yields infinitely many primes p such that
ord2(p) ≤ 2p1−1/(k−1). Let p be such a prime and t = ord2(p). Then P (2t − 1) ≥ (t/2)1+1/(k−2).
A combination of lemmas 21 and 23 yields a slightly stronger bound for the special case of 3-nice sequences.
Theorem 25 Suppose there exists a 3-nice sequence of subsets; then for infinitely many values of t we have
P (2t − 1) ≥ (3/4)t2. (41)
We would like to remind the reader that although the lower bounds for P (2t − 1) given by (40) and (41) are
extremely weak light of the widely accepted conjecture saying that the number of Mersenne primes is infinite,
they are substantially stronger than what is currently known unconditionally (2).
6 Conclusion
Recently [34] came up with a novel technique for constructing locally decodable codes and obtained vast im-
provements upon the earlier work. The construction proceeds in two steps. First [34] shows that if there exist
subsets of finite fields with certain ’nice’ properties then there exist good codes. Next [34] constructs nice subsets
of prime fields Fp for Mersenne primes p.
In this paper we have undertaken an in-depth study of nice subsets of general finite fields. We have shown
that constructing nice subsets is closely related to proving lower bounds on the size of largest prime factors of
Mersenne numbers. Specifically we extended the constructions of [34] to obtain nice subsets of prime fields Fp
for primes p that are large factors of Mersenne numbers. This implies that strong lower bounds for size of the
largest prime factors of Mersenne numbers yield better locally decodable codes. Conversely, we argued that if one
can obtain codes of subexponential length and constant query complexity through nice subsets of finite fields then
infinitely many Mersenne numbers have prime factors larger than known currently.
Acknowledgements
Kiran Kedlaya’s research is supported by NSF CAREER grant DMS-0545904 and by the Sloan Research Fel-
lowship. Sergey Yekhanin would like to thank Swastik Kopparty for providing the reference [5] and outlining
the proof of lemma 9. He would also like to thank Henryk Iwaniec, Carl Pomerance and Peter Sarnak for their
feedback regarding the number theory problems discussed in this paper.
References
[1] M. Agrawal, N. Kayal, N. Saxena, “PRIMES is in P,” Annals of Mathematics, vol. 160, pp. 781-793, 2004.
[2] L. Babai, L. Fortnow, L. Levin, and M. Szegedy, “Checking computations in polylogarithmic time,”. In Proc.
of the 23th ACM Symposium on Theory of Computing (STOC), pp. 21-31, 1991.
[3] A. Beimel, Y. Ishai and E. Kushilevitz,“General constructions for information-theoretic private information
retrieval,” Journal of Computer and System Sciences, vol. 71, pp. 213-247, 2005. Preliminary versions in
STOC 1999 and ICALP 2001.
[4] A. Beimel, Y. Ishai, E. Kushilevitz, and J. F. Raymond. “Breaking the O
n1/(2k−1)
barrier for information-
theoretic private information retrieval,” In Proc. of the 43rd IEEE Symposium on Foundations of Computer
Science (FOCS), pp. 261-270, 2002.
[5] J. Bourgain, M. Chang, “A Gauss sum estimate in arbitrary finite fields,” Comptes Rendus Mathematique,
vol. 342, pp. 643-646, 2006.
[6] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. “Private information retrieval,” In Proc. of the 36rd
IEEE Symposium on Foundations of Computer Science (FOCS), pp. 41-50, 1995. Also, in Journal of the
ACM, vol. 45, 1998.
[7] D. Cox, J. Little, D. O’Shea, Ideals, varieties, and algorithms: an introduction to computational algebraic
geometry and commutative algebra. Springer, 1996.
[8] A. Deshpande, R. Jain, T. Kavitha, S. Lokam and J. Radhakrishnan, “Better lower bounds for locally decod-
able codes,” In Proc. of the 20th IEEE Computational Complexity Conference (CCC), pp. 184-193, 2002.
[9] Curtis Cooper, Steven Boone, http://www.mersenne.org/32582657.htm
[10] P. Erdos and T. Shorey, “On the greatest prime factor of 2p − 1 for a prime p and other expressions,” Acta.
Arith. vol. 30, pp. 257-265, 1976.
[11] W. Gasarch, “A survey on private information retrieval,” The Bulletin of the EATCS, vol. 82, pp. 72-107,
2004.
[12] O. Goldreich, “Short locally testable codes and proofs,” Technical Report TR05-014, Electronic Colloquim
on Computational Complexity (ECCC), 2005.
[13] O. Goldreich, H. Karloff, L. Schulman, L. Trevisan “Lower bounds for locally decodable codes and private
information retrieval,” In Proc. of the 17th IEEE Computational Complexity Conference (CCC), pp. 175-183,
2002.
[14] B. Hemenway and R. Ostrovsky, “Public key encryption which is simultaneously a locally-decodable error-
correcting code,” In Cryptology ePrint Archive, Report 2007/083.
[15] J. Katz and L. Trevisan, “On the efficiency of local decoding procedures for error-correcting codes,” In Proc.
of the 32th ACM Symposium on Theory of Computing (STOC), pp. 80-86, 2000.
[16] I. Kerenidis, R. de Wolf, “Exponential lower bound for 2-query locally decodable codes via a quantum
argument,” Journal of Computer and System Sciences, 69(3), pp. 395-420. Earlier version in STOC’03.
quant-ph/0208062.
[17] R. Lidl and H. Niederreiter, Finite Fields. Cambridge: Cambridge University Press, 1983.
[18] L. Murata, C. Pomerance, “On the largest prime factor of a Mersenne number,” Number theory, CRM Proc.
Lecture Notes of American Mathematical Society vol. 36, pp. 209-218, 2004.
[19] M. Murty and S. Wong, “The ABC conjecture and prime divisors of the Lucas and Lehmer sequences,” In
Proc. of Milennial Conference on Number Theory III, (Urbana, IL, 2000) (A. K. Peters, Natick, MA, 2002)
pp. 43-54.
[20] K. Obata, “Optimal lower bounds for 2-query locally decodable linear codes,” In Proc. of the 6th RANDOM,
vol. 2483 of Lecture Notes in Computer Science, pp. 39-50, 2002.
[21] A. Polishchuk and D. Spielman, ”Nearly-linear size holographic proofs,” In Proc. of the 26th ACM Sympo-
sium on Theory of Computing (STOC), pp. 194-203, 1994.
[22] C. Pomerance, “Recent developments in primality testing,” Math. Intelligencer, 3:3, pp. 97-105, (1980/81).
[23] P. Raghavendra, “A Note on Yekhanin’s locally decodable codes,” In Electronic Colloquium on Computa-
tional Complexity Report TR07-016, 2007.
[24] A. Romashchenko, “Reliable computations based on locally decodable codes,” In Proc. of the 23rd Inter-
national Symposium on Theoretical Aspects of Computer Science (STACS), vol. 3884 of Lecture Notes in
Computer Science, pp. 537-548, 2006.
[25] A. Schinzel, “On primitive factors of an − bn,” In Proc. of Cambridge Philos. Soc. vol. 58, pp. 555-562,
1962.
[26] C. Stewart, “The greatest prime factor of an − bn,” Acta Arith. vol. 26, pp. 427-433, 1974/75.
[27] C. Stewart, “On divisors of Fermat, Fibonacci, Lucas, and Lehmer numbers,” In Proc. of London Math. Soc.
vol. 35 (3), pp. 425-447, 1977.
[28] M. Sudan, Efficient checking of polynomials and proofs and the hardness of approximation problems. PhD
thesis, University of California at Berkeley, 1992.
[29] L. Trevisan, “Some applications of coding theory in computational complexity,” Quaderni di Matematica,
vol. 13, pp. 347-424, 2004.
[30] S. Wehner and R. de Wolf, “Improved lower bounds for locally decodable codes and private information re-
trieval,” In Proc. of 32nd International Colloquium on Automata, Languages and Programming (ICALP’05),
LNCS 3580, pp. 1424-1436.
[31] Lenstra-Pomerance-Wagstaff conjecture. (2006, May 22). In Wikipedia, The Free Encyclopedia. Re-
trieved 00:18, October 3, 2006, from http://en.wikipedia.org/w/index.php?title=Lenstra-Pomerance-
Wagstaff conjecture&oldid=54506577
[32] S. Wagstaff, “Divisors of Mersenne numbers,” Math. Comp., 40:161, pp. 385-397, 1983.
[33] D. Woodruff, “New lower bounds for general locally decodable codes,” Electronic Colloquium on Computa-
tional Complexity, TR07-006, 2007.
[34] S. Yekhanin, “Towards 3-query locally decodable codes of subexponential length,” In Proc. of the 39th ACM
Symposium on Theory of Computing (STOC), 2007.
[35] S. Yekhanin, Locally decodable codes and private information retrieval schemes. PhD thesis, MIT, to appear.

  A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit
codeword C(x), such that one can probabilistically recover any bit x_i of the
message by querying only k bits of the codeword C(x), even after some constant
fraction of codeword bits has been corrupted. The major goal of LDC related
research is to establish the optimal trade-off between length and query
complexity of such codes.
  Recently [Y] introduced a novel technique for constructing locally decodable
codes and vastly improved the upper bounds for code length. The technique is
based on Mersenne primes. In this paper we extend the work of [Y] and argue
that further progress via these methods is tied to progress on an old number
theory question regarding the size of the largest prime factors of Mersenne
numbers.
  Specifically, we show that every Mersenne number m=2^t-1 that has a prime
factor p>m^\gamma yields a family of k(\gamma)-query locally decodable codes of
length Exp(n^{1/t}). Conversely, if for some fixed k and all \epsilon > 0 one
can use the technique of [Y] to obtain a family of k-query LDCs of length
Exp(n^\epsilon); then infinitely many Mersenne numbers have prime factors arger
than known currently.

Introduction
Classical error-correcting codes allow one to encode an n-bit string x into in N -bit codeword C(x), in such
a way that x can still be recovered even if C(x) gets corrupted in a number of coordinates. It is well-known
that codewords C(x) of length N = O(n) already suffice to correct errors in up to δN locations of C(x) for
any constant δ < 1/4. The disadvantage of classical error-correction is that one needs to consider all or most
of the (corrupted) codeword to recover anything about x. Now suppose that one is only interested in recovering
one or a few bits of x. In such case more efficient schemes are possible. Such schemes are known as locally
decodable codes (LDCs). Locally decodable codes allow reconstruction of an arbitrary bit xi, from looking only
at k randomly chosen coordinates of C(x), where k can be as small as 2. Locally decodable codes have numerous
applications in complexity theory [15, 29], cryptography [6, 11] and the theory of fault tolerant computation [24].
Below is a slightly informal definition of LDCs:
A (k, δ, ǫ)-locally decodable code encodes n-bit strings to N -bit codewords C(x), such that for every i ∈ [n],
the bit xi can be recovered with probability 1− ǫ, by a randomized decoding procedure that makes only k queries,
even if the codeword C(x) is corrupted in up to δN locations.
One should think of δ > 0 and ǫ < 1/2 as constants. The main parameters of interest in LDCs are the length
N and the query complexity k. Ideally we would like to have both of them as small as possible. The concept
of locally decodable codes was explicitly discussed in various papers in the early 1990s [2, 28, 21]. Katz and
http://arxiv.org/abs/0704.1694v1
Trevisan [15] were the first to provide a formal definition of LDCs. Further work on locally decodable codes
includes [3, 8, 20, 4, 16, 30, 34, 33, 14, 23].
Below is a brief summary of what was known regarding the length of LDCs prior to [34]. The length of optimal
2-query LDCs was settled by Kerenidis and de Wolf in [16] and is exp(n).1 The best upper bound for the length
of 3-query LDCs was exp
due to Beimel et al. [3], and the best lower bound is Ω̃(n2) [33]. For general
(constant) k the best upper bound was exp
nO(log log k/(k log k))
due to Beimel et al. [4] and the best lower bound
is Ω̃
n1+1/(⌈k/2⌉−1)
[33].
The recent work [34] improved the upper bounds to the extent that it changed the common perception of what
may be achievable [12, 11]. [34] introduced a novel technique to construct codes from so-called nice subsets
of finite fields and showed that every Mersenne prime p = 2t − 1 yields a family of 3-query LDCs of length
. Based on the largest known Mersenne prime [9], this translates to a length of less than exp
Combined with the recursive construction from [4], this result yields vast improvements for all values of k > 2. It
has often been conjectured that the number of Mersenne primes is infinite. If indeed this conjecture holds, [34] gets
three query locally decodable codes of length N = exp
log log n
for infinitely many n. Finally, assuming
that the conjecture of Lenstra, Pomerance and Wagstaff [31, 22, 32] regarding the density of Mersenne primes
holds, [34] gets three query locally decodable codes of length N = exp
log1−ǫ log n
for all n, for every ǫ >
1.1 Our results
In this paper we address two natural questions left open by [34]:
1. Are Mersenne primes necessary for the constructions of [34]?
2. Has the technique of [34] been pushed to its limits, or one can construct better codes through a more clever
choice of nice subsets of finite fields?
We extend the work of [34] and answer both of the questions above. In what follows let P (m) denote the
largest prime factor of m. We show that one does not necessarily need to use Mersenne primes. It suffices to have
Mersenne numbers with polynomially large prime factors. Specifically, every Mersenne number m = 2t − 1 such
that P (m) ≥ mγ yields a family of k(γ)-query locally decodable codes of length exp
. A partial converse
also holds. Namely, if for some fixed k ≥ 3 and all ǫ > 0 one can use the technique of [34] to (unconditionally)
obtain a family of k-query LDCs of length exp (nǫ) ; then for infinitely many t we have
P (2t − 1) ≥ (t/2)1+1/(k−2). (1)
The bound (1) may seem quite weak in light of the widely accepted conjecture saying that the number of
Mersenne primes is infinite. However (for any k ≥ 3) this bound is substantially stronger than what is currently
known unconditionally. Lower bounds for P (2t − 1) have received a considerable amount of attention in the
number theory literature [25, 26, 10, 27, 19, 18]. The strongest result to date is due to Stewart [27]. It says that
for all integers t ignoring a set of asymptotic density zero, and for all functions ǫ(t) > 0 where ǫ(t) tends to zero
monotonically and arbitrarily slowly:
P (2t − 1) > ǫ(t)t (log t)2 / log log t. (2)
1Throughout the paper we use the standard notation exp(x)
= eO(x).
There are no better bounds known to hold for infinitely many values of t, unless one is willing to accept some
number theoretic conjectures [19, 18]. We hope that our work will further stimulate the interest in proving lower
bounds for P (2t − 1) in the number theory community.
In summary, we show that one may be able to improve the unconditional bounds of [34] (say, by discovering a
new Mersenne number with a very large prime factor) using the same technique. However any attempts to reach
the exp (nǫ) length for some fixed query complexity and all ǫ > 0 require either progress on an old number theory
problem or some radically new ideas.
In this paper we deal only with binary codes for the sake of clarity of presentation. We remark however that
our results as well as the results of [34] can be easily generalized to larger alphabets. Such generalization will be
discussed in detail in [35].
1.2 Outline
In section 3 we introduce the key concepts of [34], namely that of combinatorial and algebraic niceness of
subsets of finite fields. We also briefly review the construction of locally decodable codes from nice subsets. In
section 4 we show how Mersenne numbers with large prime factors yield nice subsets of prime fields. In section 5
we prove a partial converse. Namely, we show that every finite field Fq containing a sufficiently nice subset, is an
extension of a prime field Fp, where p is a large prime factor of a large Mersenne number. Our main results are
summarized in sections 4.3 and 5.4.
2 Notation
We use the following standard mathematical notation:
• [s] = {1, . . . , s};
• Zn denotes integers modulo n;
• Fq is a finite field of q elements;
• dH(x, y) denotes the Hamming distance between binary vectors x and y;
• (u, v) stands for the dot product of vectors u and v;
• For a linear space L ⊆ Fm2 , L⊥ denotes the dual space. That is, L⊥ = {u ∈ Fm2 | ∀v ∈ L, (u, v) = 0};
• For an odd prime p, ord2(p) denotes the smallest integer t such that p | 2t − 1.
3 Nice subsets of finite fields and locally decodable codes
In this section we introduce the key technical concepts of [34], namely that of combinatorial and algebraic
niceness of subsets of finite fields. We briefly review the construction of locally decodable codes from nice
subsets. Our review is concise although self-contained. We refer the reader interested in a more detailed and
intuitive treatment of the construction to the original paper [34]. We start by formally defining locally decodable
codes.
Definition 1 A binary code C : {0, 1}n → {0, 1}N is said to be (k, δ, ǫ)-locally decodable if there exists a
randomized decoding algorithm A such that
1. For all x ∈ {0, 1}n, i ∈ [n] and y ∈ {0, 1}N such that dH(C(x), y) ≤ δN : Pr[Ay(i) = xi] ≥ 1− ǫ, where
the probability is taken over the random coin tosses of the algorithm A.
2. A makes at most k queries to y.
We now introduce the concepts of combinatorial and algebraic niceness of subsets of finite fields. Our defini-
tions are syntactically slightly different from the original definitions in [34]. We prefer these formulations since
they are more appropriate for the purposes of the current paper. In what follows let F∗q denote the multiplicative
group of Fq.
Definition 2 A set S ⊆ F∗q is called t combinatorially nice if for some constant c > 0 and every positive integer
m there exist two n = ⌊cmt⌋-sized collections of vectors {u1, . . . , un} and {v1, . . . , vn} in Fmq , such that
• For all i ∈ [n], (ui, vi) = 0;
• For all i, j ∈ [n] such that i 6= j, (uj , vi) ∈ S.
Definition 3 A set S ⊆ F∗q is called k algebraically nice if k is odd and there exists an odd k′ ≤ k and two sets
S0, S1 ⊆ Fq such that
• S0 is not empty;
• |S1| = k′;
• For all α ∈ Fq and β ∈ S : |S0 ∩ (α+ βS1)| ≡ 0 mod (2).
The following lemma shows that for an algebraically nice set S, the set S0 can always be chosen to be large. It
is a straightforward generalization of [34, lemma 15].
Lemma 4 Let S ⊆ F∗q be a k algebraically nice set. Let S0, S1 ⊆ Fq be sets from the definition of algebraic
niceness of S. One can always redefine the set S0 to satisfy |S0| ≥ ⌈q/2⌉.
Proof: Let L be the linear subspace of Fq2 spanned by the incidence vectors of the sets α+ βS1, for α ∈ Fq and
β ∈ S. Observe that L is invariant under the actions of a 1-transitive permutation group (permuting the coordinates
in accordance with addition in Fq). This implies that the space L
⊥ is also invariant under the actions of the same
group. Note that L⊥ has positive dimension since it contains the incidence vector of the set S0. The last two
observations imply that L⊥ has full support, i.e., for every i ∈ [q] there exists a vector v ∈ L⊥ such that vi 6= 0. It
is easy to verify that any linear subspace of Fq2 that has full support contains a vector of Hamming weight at least
⌈q/2⌉. Let v ∈ L⊥ be such a vector. Redefining the set S0 to be the set of nonzero coordinates of v we conclude
the proof.
We now proceed to the core proposition of [34] that shows how sets exhibiting both combinatorial and algebraic
niceness yield locally decodable codes.
Proposition 5 Suppose S ⊆ F∗q is t combinatorially nice and k algebraically nice; then for every positive integer
n there exists a code of length exp(n1/t) that is (k, δ, 2kδ) locally decodable for all δ > 0.
Proof: Our proof comes in three steps. We specify encoding and local decoding procedures for our codes and
then argue the lower bound for the probability of correct decoding. We use the notation from definitions 2 and 3.
Encoding: We assume that our message has length n = ⌊cmt⌋ for some value of m. (Otherwise we pad the
message with zeros. It is easy to see that such padding does not not affect the asymptotic length of the code.) Our
code will be linear. Therefore it suffices to specify the encoding of unit vectors e1, . . . , en, where ej has length n
and a unique non-zero coordinate j. We define the encoding of ej to be a q
m long vector, whose coordinates are
labelled by elements of Fmq . For all w ∈ Fmq we set:
Enc(ej)w =
1, if (uj , w) ∈ S0;
0, otherwise.
It is straightforward to verify that we defined a code encoding n bits to exp(n1/t) bits.
Local decoding: Given a (possibly corrupted) codeword y and an index i ∈ [n], the decoding algorithm A picks
w ∈ Fmq , such that (ui, w) ∈ S0 uniformly at random, reads k′ ≤ k coordinates of y, and outputs the sum:
yw+λvi . (4)
Probability of correct decoding: First we argue that decoding is always correct if A picks w ∈ Fmq such that
all bits of y in locations {w + λvi}λ∈S1 are not corrupted. We need to show that for all i ∈ [n], x ∈ {0, 1}n and
w ∈ Fmq , such that (ui, w) ∈ S0:
xj Enc(ej)
w+λvi
= xi. (5)
Note that
xj Enc(ej)
w+λvi
Enc(ej)w+λvi =
I [(uj , w + λvi) ∈ S0] , (6)
where I[γ ∈ S0] = 1 if γ ∈ S0 and zero otherwise. Now note that
I [(uj , w + λvi) ∈ S0] =
I [(uj , w) + λ(uj , vi) ∈ S0] =
1, if i = j,
0, otherwise.
The last identity in (7) for i = j follows from: (ui, vi) = 0, (ui, w) ∈ S0 and k′ = |S1| is odd. The last identity
for i 6= j follows from (uj , vi) ∈ S and the algebraic niceness of S. Combining identities (6) and (7) we get (5).
Now assume that up to δ fraction of bits of y are corrupted. Let Ti denote the set of coordinates whose labels
belong to
w ∈ Fmq | (ui, w) ∈ S0
. Recall that by lemma 4, |Ti| ≥ qm/2. Thus at most 2δ fraction of coor-
dinates in Ti contain corrupted bits. Let Qi =
{w + λvi}λ∈S1 | w : (ui, w) ∈ S0
be the family of k′-tuples
of coordinates that may be queried by A. (ui, vi) = 0 implies that elements of Qi uniformly cover the set Ti.
Combining the last two observations we conclude that with probability at least 1 − 2kδ A picks an uncorrupted
k′-tuple and outputs the correct value of xi.
All locally decodable codes constructed in this paper are obtained by applying proposition 5 to certain nice
sets. Thus all our codes have the same dependence of ǫ (the probability of the decoding error) on δ (the fraction
of corrupted bits). In what follows we often ignore these parameters and consider only the length and query
complexity of codes.
4 Mersenne numbers with large prime factors yield nice subsets of prime fields
In what follows let 〈2〉 ⊆ F∗p denote the multiplicative subgroup of F∗p generated by 2. In [34] it is shown
that for every Mersenne prime p = 2t − 1 the set 〈2〉 ⊆ F∗p is simultaneously 3 algebraically nice and ord2(p)
combinatorially nice. In this section we prove the same conclusion for a substantially broader class of primes.
Lemma 6 Suppose p is an odd prime; then 〈2〉 ⊆ F∗p is ord2(p) combinatorially nice.
Proof: Let t = ord2(p). Clearly, t divides p− 1. We need to specify a constant c > 0 such that for every positive
integer m there exist two n = ⌊cmt⌋-sized collections of m long vectors over Fp satisfying:
• For all i ∈ [n], (ui, vi) = 0;
• For all i, j ∈ [n] such that i 6= j, (uj , vi) ∈ 〈2〉.
First assume that m has the shape m =
m′−1+(p−1)/t
(p−1)/t
, for some integer m′ ≥ p − 1. In this case [34, lemma
13] gives us a collection of n =
vectors with the right properties. Observe that n ≥ cmt for a constant
c that depends only on p and t. Now assume m does not have the right shape, and let m1 be the largest integer
smaller than m that does have it. In order to get vectors of length m we use vectors of length m1 coming from [34,
lemma 13] padded with zeros. It is not hard to verify such a construction still gives us n ≥ cmt large families of
vectors for a suitably chosen constant c.
We use the standard notation F to denote the algebraic closure of the field F. Also let Cp ⊆ F
2 denote the
multiplicative subgroup of p-th roots of unity in F2. The next lemma generalizes [34, lemma 14].
Lemma 7 Let p be a prime and k be odd. Suppose there exist ζ1, . . . , ζk ∈ Cp such that
ζ1 + . . . + ζk = 0; (8)
then 〈2〉 ⊆ F∗p is k algebraically nice.
Proof: In what follows we define the set S1 ⊆ Fp and prove the existence of a set S0 such that that together S0
and S1 yield k algebraic niceness of 〈2〉. Identity 8 implies that there exists an odd integer k′ ≤ k and k′ distinct
p-th roots of unity ζ ′1, . . . , ζ
k ∈ Cp such that
ζ ′1 + . . . + ζ
k′ = 0. (9)
Let t = ord2(p). Observe that Cp ⊆ F2t . Let g be a generator of Cp. Identity (9) yields gγ1 + . . .+ gγk′ = 0, for
some distinct values of {γi}i∈[k′]. Set S1 = {γ1, . . . , γk′}.
Consider a natural one to one correspondence between subsets S′ of Fp and polynomials φS′(x) in the ring
F2[x]/(x
p − 1) : φS′(x) =
xs. It is easy to see that for all sets S′ ⊆ Fp and all α, β ∈ Fp, such that β 6= 0 :
φα+βS′(x) = x
αφS′(x
Let α be a variable ranging over Fp and β be a variable ranging over 〈2〉. We are going to argue the existence of a
set S0 that has even intersections with all sets of the form α+βS1, by showing that all polynomials φα+βS1 belong
to a certain linear space L ∈ F2[x]/(xp − 1) of dimension less than p. In this case any nonempty set T ⊆ Fp such
that φT ∈ L⊥ can be used as the set S0. Let τ(x) = gcd(xp−1, φS1(x)). Note that τ(x) 6= 1 since g is a common
root of xp−1 and φS1(x). Let L be the space of polynomials in F2[x]/(xp−1) that are multiples of τ(x). Clearly,
dimL = p− deg τ. Fix some α ∈ Fp and β ∈ 〈2〉. Let us prove that φα+βS1(x) is in L :
φα+βS1(x) = x
αφS1(x
β) = xα(φS1(x))
The last identity above follows from the fact that for any f ∈ F2[x] and any integer i : f(x2
) = (f(x))2
In what follows we present sufficient conditions for the existence of k-tuples of p-th roots of unity in F2 that
sum to zero. We treat the k = 3 case separately since in that case we can use a specialized argument to derive a
more explicit conclusion.
4.1 A sufficient condition for the existence of three p-th roots of unity summing to zero
Lemma 8 Let p be an odd prime. Suppose ord2(p) < (4/3) log2 p; then there exist three p-th roots of unity in F2
that sum to zero.
Proof: We start with a brief review of some basic concepts of projective algebraic geometry. Let F be a field, and
f ∈ F[x, y, z] be a homogeneous polynomial. A triple (x0, y0, z0) ∈ F3 is called a zero of f if f(x0, y0, z0) = 0.
A zero is called nontrivial if it is different from the origin. An equation f = 0 defines a projective plane curve χf .
Nontrivial zeros of f considered up to multiplication by a scalars are called F-rational points of χf . If F is a finite
field it makes sense to talk about the number of F-rational points on a curve.
Let t = ord2(p). Note that Cp ⊆ F2t . Consider a projective plane Fermat curve χ defined by
t−1)/p + y(2
t−1)/p + z(2
t−1)/p = 0. (10)
Let us call a point a on χ trivial if one of the coordinates of a is zero. Cyclicity of F∗
implies that χ contains
exactly 3(2t − 1)/p trivial F2t-rational points. Note that every nontrivial point of χ yields a triple of elements of
Cp that sum to zero. The classical Weil bound [17, p. 330] provides an estimate
|Nq − (q + 1)| ≤ (d− 1)(d − 2)
q (11)
for the number Nq of Fq-rational points on an arbitrary smooth projective plane curve of degree d. (11) implies
that in case
2t + 1 >
2t − 1
2t − 1
2t/2 + 3
2t − 1
there exists a nontrivial point on the curve (10). Note that (12) follows from
2t + 1 >
2t/2 −
23t/2+1
3 ∗ 2t
, (13)
and (13) follows from
2t > 22t+t/2/p2 and 2t/2+1 > 3.
Now note that the first inequality above follows from t < (4/3) log2 p and the second follows from t > 1.
Note that the constant 4/3 in lemma 8 cannot be improved to 2: there are no three elements of C13264529 that
sum to zero, even though ord2(13264529) = 47 < 2 ∗ log2 13264529 ≈ 47.3.
4.2 A sufficient condition for the existence of k p-th roots of unity summing to zero
Our argument in this section comes in three steps. First we briefly review the notion of (additive) Fourier
coefficients of subsets of F2t . Next, we invoke a folklore argument to show that subsets of F2t with appropriately
small nontrivial Fourier coefficients contain k-tuples of elements that sum to zero. Finally, we use a recent result of
Bourgain and Chang [5] (generalizing the classical estimate for Gauss sums) to argue that (under certain constraints
on p) all nontrivial Fourier coefficients of Cp are small.
For x ∈ F2t let Tr(x) = x + x2 + . . . + x2
denote the trace of x. It is not hard to verify that for all x,
Tr(x) ∈ F2. Characters of F2t are homomorphisms from the additive group of F2t into the multiplicative group
{±1}. There exist 2t characters. We denote characters by χa, where a ranges in F2t , and set χa(x) = (−1)Tr(ax).
Let C(x) denote the incidence function of a set C ⊆ F2t . For arbitrary a ∈ Ft2 the Fourier coefficient χa(C) is
defined by χa(C) =
χa(x)C(x), where the sum is over all x ∈ F2t . Fourier coefficient χ0(C) = |C| is called
trivial, and other Fourier coefficients are called nontrivial. In what follows
χ stands for summation over all 2
characters of F2t . We need the following two standard properties of characters and Fourier coefficients.
χ(x) =
2t, if x = 0;
0, otherwise.
χ2(C) = 2t|C|. (15)
The following lemma is a folklore.
Lemma 9 Let C ⊆ F2t and k ≥ 3 be a positive integer. Let F be the largest absolute value of a nontrivial Fourier
coefficient of C. Suppose
)1/(k−2)
then there exist k elements of C that sum to zero.
Proof: Let M(C) = # {ζ1, . . . , ζk ∈ C | ζ1 + . . .+ ζk = 0} . (14) yields
M(C) =
x1,...,xk∈F2t
C(x1) . . . C(xk)
χ(x1 + . . .+ xk). (17)
Note that χ(x1 + . . .+ xk) = χ(x1) . . . χ(xk). Changing the order of summation in (17) we get
M(C) =
x1,...,xk∈F2t
C(x1) . . . C(xk)χ(x1) . . . χ(xk) =
χk(C). (18)
Note that
χk(C) =
χ 6=χ0
χk(C) ≥
− F k−2
χ2(C) =
− F k−2|C|, (19)
where the last identity follows from (15). Combining (18) and (19) we conclude that (16) implies M(C) > 0.
The following lemma is a special case of [5, theorem 1].
Lemma 10 Assume that n | 2t − 1 and satisfies the condition
2t − 1
′ − 1
< 2t(1−ǫ)−t
, for all 1 ≤ t′ < t, t′ | t,
where ǫ > 0 is arbitrary and fixed. Then for all a ∈ F∗
x∈F2t
(−1)Tr(axn)
< c12
t(1−δ), (20)
where δ = δ(ǫ) > 0 and c1 = c1(ǫ) are absolute constants.
Below is the main result of this section. Recall that Cp denotes the set of p-th roots of unity in F2.
Lemma 11 For every c > 0 there exists an odd integer k = k(c) such that the following implication holds. If p is
an odd prime and ord2(p) < c log2 p then some k elements of Cp sum to zero.
Proof: Note that if there exist k′ elements of a set C ⊆ F2 that sum to zero, where k′ is odd; then there exist
k elements of C that sum to zero for every odd k ≥ k′. Also note that the sum of all p-th roots of unity is
zero. Therefore given c it suffices to prove the existence of an odd k = k(c) that works for all sufficiently large
p. Let t = ord2(p). Observe that p > 2
t/c. Assume p is sufficiently large so that t > 2c. Next we show that
the precondition of lemma 10 holds for n = (2t − 1)/p and ǫ = 1/(2c). Let t′ | t and 1 ≤ t′ < t. Clearly
gcd(2t
′ − 1, p) = 1. Therefore
2t − 1
2t − 1
′ − 1
2t − 1
′ − 1)
2t(1−1/c)
′ − 1
, (21)
where the inequality follows from p > 2t/c. Clearly, t > 2c yields 2t/(2c)/2 > 1. Multiplying the right hand side
of (21) by 2t/(2c)/2 and using 2(2t
′ − 1) > 2t′ we get
2t − 1
2t − 1
′ − 1
< 2t(1−1/(2c))−t
. (22)
Combining (22) with lemma 10 we conclude that there exist δ > 0 and c1 such that for all a ∈ F∗2t
x∈F2t
(−1)Tr
−1)/p
< c12
t(1−δ). (23)
Observe that x(2
t−1)/p takes every value in Cp exactly (2
t−1)/p times when x ranges over F∗
. Thus (23) implies
(2t − 1)(F/p) < c12t(1−δ), (24)
where F denotes that largest nontrivial Fourier coefficient of Cp. (24) yields F/p < (2c1)2
−δt. Pick k ≥ 3 to be
the smallest odd integer such that (1 − 1/c)/(k − 2) < δ. We now have
(1−1/c)t
(k−2) (25)
for all sufficiently large values of p. Combining p > 2t/c with (25) we get
)1/(k−2)
and the application of lemma 9 concludes the proof.
4.3 Summary
In this section we summarize our positive results and show that one does not necessarily need to use Mersenne
primes to construct locally decodable codes via the methods of [34]. It suffices to have Mersenne numbers with
polynomially large prime factors. Recall that P (m) denotes the largest prime factor of an integer m. Our first
theorem gets 3-query LDCs from Mersenne numbers m with prime factors larger than m3/4.
Theorem 12 Suppose P (2t − 1) > 20.75t; then for every message length n there exists a three query locally
decodable code of length exp(n1/t).
Proof: Let P (2t − 1) = p. Observe that p | 2t − 1 and p > 20.75t yield ord2(p) < (4/3) log2 p. Combining
lemmas 8,7 and 6 with proposition 5 we obtain the statement of the theorem.
As an example application of theorem 12 one can observe that P (223−1) = 178481 > 2(3/4)∗23 ≈ 155872 yields
a family of three query locally decodable codes of length exp(n1/23). Theorem 12 immediately yields:
Theorem 13 Suppose for infinitely many t we have P (2t − 1) > 20.75t; then for every ǫ > 0 there exists a family
of three query locally decodable codes of length exp(nǫ).
The next theorem gets constant query LDCs from Mersenne numbers m with prime factors larger than mγ for
every value of γ.
Theorem 14 For every γ > 0 there exists an odd integer k = k(γ) such that the following implication holds.
Suppose P (2t − 1) > 2γt; then for every message length n there exists a k query locally decodable code of length
exp(n1/t).
Proof: Let P (2t − 1) = p. Observe that p | 2t − 1 and p > 2γt yield ord2(p) < (1/γ) log2 p. Combining
lemmas 22,7 and 6 with proposition 5 we obtain the statement of the theorem.
As an immediate corollary we get:
Theorem 15 Suppose for some γ > 0 and infinitely many t we have P (2t − 1) > 2γt; then there is a fixed k such
that for every ǫ > 0 there exists a family of k query locally decodable codes of length exp(nǫ).
5 Nice subsets of finite fields yield Mersenne numbers with large prime factors
Definition 16 We say that a sequence
Si ⊆ F∗qi
of subsets of finite fields is k-nice if every Si is k alge-
braically nice and t(i) combinatorially nice, for some integer valued monotonically increasing function t.
The core proposition 5 asserts that a subset S ⊆ F∗q that is k algebraically nice and t combinatorially nice yields
a family of k-query locally decodable codes of length exp(n1/t). Clearly, to get k-query LDCs of length exp(nǫ)
for some fixed k and every ǫ > 0 via this proposition, one needs to exhibit a k-nice sequence. In this section
we show how the existence of a k-nice sequence implies that infinitely many Mersenne numbers have large prime
factors. Our argument proceeds in two steps. First we show that a k-nice sequence yields an infinite sequence of
primes {pi}i≥1 , where every Cpi contains a k-tuple of elements summing to zero. Next we show that Cp contains
a short additive dependence only if p is a large factor of a Mersenne number.
5.1 A nice sequence yields infinitely many primes p with short dependencies between p-th roots of unity
We start with some notation. Consider a a finite field Fq = Fpl, where p is prime. Fix a basis e1, . . . , el of Fq
over Fp. In what follows we often write (α1, . . . , αl) ∈ Flp to denote α =
i=1 αiei ∈ Fq. Let R denote the ring
F2[x1, . . . , xl]/(x
1 − 1, . . . , x
l − 1). Consider a natural one to one correspondence between subsets S1 of Fq and
polynomials φS1(x1, . . . , xl) ∈ R.
φS1(x1, . . . , xl) =
(α1,...,αl)∈S1
1 . . . x
It is easy to see that for all sets S1 ⊆ Fq and all α, β ∈ Fq :
φ(α1,...,αl)+βS1(x1, . . . , xl) = x
1 . . . x
φβS1(x1, . . . , xl). (26)
Let Γ be a family of subsets of Fq. It is straightforward to verify that a set S0 ⊆ Fq has even intersections with
every element of Γ if and only if φS0 belongs to L
⊥, where L is the linear subspace of R spanned by {φS1}S1∈Γ .
Combining the last observation with formula (26) we conclude that a set S ⊆ F∗q is k algebraically nice if and
only if there exists a set S1 ⊆ Fq of odd size k′ ≤ k such that the ideal generated by polynomials {φβS1}{β∈S}
is a proper ideal of R. Note that polynomials {f1, . . . , fh} ∈ R generate a proper ideal if an only if polynomials
{f1, . . . , fh, xp1 − 1, . . . , x
l − 1} generate a proper ideal in F2[x1, . . . , xl]. Also note that a family of polynomials
generates a proper ideal in F2[x1, . . . , xl] if and only if it generates a proper ideal in F2[x1, . . . , xl]. Now an
application of Hilbert’s Nullstellensatz [7, p. 168] implies that a set S ⊆ F∗q is k algebraically nice if and only
if there is a set S1 ⊆ Fq of odd size k′ ≤ k such that the polynomials {φβS1}{β∈S} and {x
i − 1}1≤i≤l have a
common root in F2.
Lemma 17 Let Fq = Fpl , where p is prime. Suppose Fq contains a nonempty k algebraically nice subset; then
there exist ζ1, . . . , ζk ∈ Cp such that ζ1 + . . .+ ζk = 0.
Proof: Assume S ⊆ F∗q is nonempty and k algebraically nice. The discussion above implies that there exists
S1 ⊆ Fq of odd size k′ ≤ k such that all polynomials {φβS1}{β∈S} vanish at some (ζ1, . . . , ζl) ∈ C
p. Fix an
arbitrary β0 ∈ S, and note that Cp is closed under multiplication. Thus,
φβ0S1(ζ1, . . . , ζl) = 0 (27)
yields k′ p-th roots of unity that add up to zero. It is readily seen that one can extend (27) (by adding an appropriate
number of pairs of identical roots) to obtain k p-th roots of unity that add up to zero for any odd k ≥ k′.
Note that lemma 17 does not suffice to prove that a k-nice sequence
Si ⊆ F∗qi
yields infinitely many primes p
with short (nontrivial) additive dependencies in Cp. We need to argue that the set {charFqi}i≥1 can not be finite. To
proceed, we need some more notation. Recall that q = pl and p is prime. For x ∈ Fq let Tr(x) = x+. . .+xp
l−1 ∈
Fp denote the (absolute) trace of x. For γ ∈ Fq, c ∈ F∗p we call the set πγ,c = {x ∈ Fq | Tr(γx) = c} a proper
affine hyperplane of Fq.
Lemma 18 Let Fq = Fpl , where p is prime. Suppose S ⊆ F∗q is k algebraically nice; then there exist h ≤ pk
proper affine hyperplanes {πγi,ci}1≤i≤h of Fq such that S ⊆
πγi,ci.
Proof: Discussion preceding lemma 17 implies that there exists a set S1 = {σ1, . . . , σk′} ⊆ Fq of odd size
k′ ≤ k such that all polynomials {φβS1}{β∈S} vanish at some (ζ1, . . . , ζl) ∈ C
p. Let ζ be a generator of Cp. For
every 1 ≤ i ≤ l pick ωi ∈ Zp such that ζi = ζωi . For every β ∈ S, φβS1(ζ1, . . . , ζl) = 0 yields
µ=(µ1,...,µl)∈βS1
i=1 µiωi = 0. (28)
Observe that for fixed values {ωi}1≤i≤l ∈ Zp the map D(µ) =
i=1 µiωi is a linear map from Fq to Fp. It is
not hard to prove that every such map can be expressed as D(µ) = Tr(δµ) for an appropriate choice of δ ∈ Fq.
Therefore we can rewrite (28) as
µ∈βS1
ζTr(δµ) =
ζTr(δβσ) = 0. (29)
Let W =
(w1, . . . , wk′) ∈ Zk
p | ζw1 + . . . + ζwk′ = 0
denote the set of exponents of k′-dependencies be-
tween powers of ζ. Clearly, |W | ≤ pk. Identity (29) implies that every β ∈ S satisfies
Tr((δσ1)β) = w1,
Tr((δσk′)β) = wk′ ;
for an appropriate choice of (w1, . . . , wk′) ∈ W. Note that the all-zeros vector does not lie in W since k′ is odd.
Therefore at least one of the identities in (30) has a non-zero right-hand side, and defines a proper affine hyperplane
of Fq. Collecting one such hyperplane for every element of W we get a family of |W | proper affine hyperplanes
containing every element of S.
Lemma 18 gives us some insight into the structure of algebraically nice subsets of Fq. Our next goal is to develop
an insight into the structure of combinatorially nice subsets. We start by reviewing some relations between tensor
and dot products of vectors. For vectors u ∈ Fmq and v ∈ Fnq let u⊗v ∈ Fmnq denote the tensor product of u and v.
Coordinates of u⊗ v are labelled by all possible elements of [m]× [n] and (u⊗ v)i,j = uivj . Also, let u⊗l denote
the l-the tensor power of u and u ◦ v denote the concatenation of u and v. The following identity is standard. For
any u, x ∈ Fmq and v, y ∈ Fnq :
(u⊗ v, x⊗ y) =
i∈[m],j∈[n]
uivjxiyj =
i∈[m]
j∈[n]
 = (u, x)(v, y). (31)
In what follows we need a generalization of identity (31). Let f(x1, . . . , xh) =
i cix
1 . . . x
h be a polynomial
in Fq[x1, . . . , xh]. Given f we define f̄ ∈ Fq[x1, . . . , xh] by f̄ =
1 . . . x
, i.e., we simply set all nonzero
coefficients of f to 1. For vectors u1, . . . , uh in F
q define
f(u1, . . . , uh) = ◦i ciu
1 ⊗ . . .⊗ u
h . (32)
Note that to obtain f(u1, . . . , uh) we replaced products in f by tensor products and addition by concatenation.
Clearly, f(u1, . . . , uh) is a vector whose length may be larger than m.
Claim 19 For every f ∈ Fq[x1, . . . , xh] and u1, . . . , uh, v1, . . . , vh ∈ Fmq :
f(u1, . . . , uh), f̄(v1, . . . , vh)
= f((u1, v1), . . . , (uh, vh)). (33)
Proof: Let u = (u1, . . . , uh) and v = (v1, . . . , vh). Observe that if (33) holds for polynomials f1 and f2 defined
over disjoint sets of monomials then it also holds for f = f1 + f2 :
f(u), f̄(v)
(f1 + f2)(u), (f̄1 + f̄2)(v)
f1(u) ◦ f2(u), f̄1(v) ◦ f̄2(v)
f1 ((u1, v1), . . . , (uh, vh)) + f2 ((u1, v1), . . . , (uh, vh)) = f ((u1, v1), . . . , (uh, vh)) .
Therefore it suffices to prove (33) for monomials f = cxα11 . . . x
. It remains to notice identity (33) for monomi-
als f = cxα11 . . . x
h follows immediately from formula (31) using induction on
i=1 αi.
The next lemma bounds combinatorial niceness of certain subsets of F∗q.
Lemma 20 Let Fq = Fpl, where p is prime. Let S ⊆ F∗q. Suppose there exist h proper affine hyperplanes
{πγr ,cr}1≤r≤h of Fq such that S ⊆
πγr ,cr ; then S is at most h(p − 1) combinatorially nice.
Proof: Assume S is t combinatorially nice. This implies that for some c > 0 and every m there exist two
n = ⌊cmt⌋-sized collections of vectors {ui}i∈[n] and {vi}i∈[n] in Fmq , such that:
• For all i ∈ [n], (ui, vi) = 0;
• For all i, j ∈ [n] such that i 6= j, (uj , vi) ∈ S.
For a vector u ∈ Fmq and integer e let ue denote a vector resulting from raising every coordinate of u to the power e.
For every i ∈ [n] and r ∈ [h] define vectors u(r)i and v
i in F
i = (γrui) ◦ (γrui)
p ◦ . . . ◦ (γrui)p
and v
i = vi ◦ v
i ◦ . . . ◦ v
i . (34)
Note that for every r1, r2 ∈ [h], v
i = v
i . It is straightforward to verify that for every i, j ∈ [n] and r ∈ [h] :
j , v
= Tr(γr(uj , vi)). (35)
Combining (35) with the fact that S is covered by proper affine hyperplanes πγi,ci we conclude that
• For all i ∈ [n] and r ∈ [h],
i , v
• For all i, j ∈ [n] such that i 6= j, there exists r ∈ [h] such that
j , v
∈ F∗p.
Pick g(x1, . . . , xh) ∈ Fp[x1, . . . , xh] to be a homogeneous degree h polynomial such that for a = (a1, . . . , ah) ∈
p : g(a) = 0 if and only if a is the all-zeros vector. The existence of such a polynomial g follows from [17,
Example 6.7]. Set f = gp−1. Note that for a ∈ Fhp : f(a) = 0 if a is the all-zeros vector, and f(a) = 1 otherwise.
For all i ∈ [n] define
u′i = f
i , . . . , u
◦ (1) and v′i = f̄
i , . . . , v
◦ (−1). (36)
Note that f and f̄ are homogeneous degree (p − 1)h polynomials in h variables. Therefore (32) implies that
for all i vectors u′i and v
i have length m
′ ≤ h(p−1)h(ml)(p−1)h. Combining identities (36) and (33) and using the
properties of dot products between vectors
discussed above we conclude that for every m there
exist two n = ⌊cmt⌋-sized collections of vectors {u′i}i∈[n] and {v′i}i∈[n] in Fm
q , such that:
• For all i ∈ [n], (u′i, v′i) = −1;
• For all i, j ∈ [n] such that i 6= j, (uj , vi) = 0.
It remains to notice that a family of vectors with such properties exists only if n ≤ m′, i.e., ⌊cmt⌋ ≤ h(p−1)h(ml)(p−1)h.
Given that we can pick m to be arbitrarily large, this implies that t ≤ (p− 1)h.
The next lemma presents the main result of this section.
Lemma 21 Let k be an odd integer. Suppose there exists a k-nice sequence; then for infinitely many primes p
some k of elements of Cp add up to zero.
Proof: Assume
Si ⊆ F∗qi
is k-nice. Let p be a fixed prime. Combining lemmas 18 and 20 we conclude
that every k algebraically nice subset S ⊆ F∗
is at most (p − 1)pk combinatorially nice. Note that our bound on
combinatorial niceness is independent of l. Therefore there are only finitely many extensions of the field Fp in the
sequence {Fqi}i≥1 , and the set P = {charFqi}i≥1 is infinite. It remains to notice that according to lemma 17 for
every p ∈ P there exist k elements of Cp that add up to zero.
In what follows we present necessary conditions for the existence of k-tuples of p-th roots of unity in F2 that
sum to zero. We treat the k = 3 case separately since in that case we can use a specialized argument to derive a
slightly stronger conclusion.
5.2 A necessary condition for the existence of k p-th roots of unity summing to zero
Lemma 22 Let k ≥ 3 be odd and p be a prime. Suppose there exist ζ1, . . . , ζk ∈ Cp such that
i=1 ζi = 0; then
ord2(p) ≤ 2p1−1/(k−1). (37)
Proof: Let t = ord2(p). Note that Cp ⊆ F2t . Note also that all elements of Cp other than the multiplicative
identity are proper elements of F2t. Therefore for every ζ ∈ Cp where ζ 6= 1 and every f(x) ∈ F2[x] such that
deg f ≤ t− 1 we have: f(ζ) 6= 0.
By multiplying
i=1 ζi = 0 through by ζ
, we may reduce to the case ζk = 1. Let ζ be the generator of Cp.
For every i ∈ [k − 1] pick wi ∈ Zp such that ζi = ζwi . We now have
i=1 ζ
wi + 1 = 0. Set h = ⌊(t − 1)/2⌋.
Consider the (k − 1)-tuples:
(mw1 + i1, . . . ,mwk−1 + ik−1) ∈ Zk−1p , for m ∈ Zp and i1, . . . , ik−1 ∈ [0, h]. (38)
Suppose two of these coincide, say
(mw1 + i1, . . . ,mwk−1 + ik−1) = (m
′w1 + i
1, . . . ,m
′wk−1 + i
k−1),
with (m, i1, . . . , ik−1) 6= (m′, i′1, . . . , i′k−1). Set n = m−m′ and jl = i′l − il for l ∈ [k − 1]. We now have
(nw1, . . . , nwk−1) = (j1, . . . , jl)
with −h ≤ j1, . . . , jk−1 ≤ h. Observe that n 6= 0, and thus it has a multiplicative inverse g ∈ Zp. Consider a
polynomial
P (z) = zj1+h + . . .+ zjk−1+h + zh ∈ F2[z].
Note that degP ≤ 2h ≤ t − 1. Note also that P (1) = 1 and P (ζg) = 0. The latter identity contradicts the fact
that ζg is a proper element of F2t . This contradiction implies that all (k−1)-tuples in (38) are distinct. This yields
pk−1 ≥ p
which is equivalent to (37).
5.3 A necessary condition for the existence of three p-th roots of unity summing to zero
In this section we slightly strengthen lemma 22 in the special case when k = 3. Our argument is loosely inspired
by the Agrawal-Kayal-Saxena deterministic primality test [1].
Lemma 23 Let p be a prime. Suppose there exist ζ1, ζ2, ζ3 ∈ Cp that sum up to zero; then
ord2(p) ≤ ((4/3)p)1/2 . (39)
Proof: Let t = ord2(p). Note that Cp ⊆ F2t . Note also that all elements of Cp other than the multiplicative
identity are proper elements of F2t. Therefore for every ζ ∈ Cp where ζ 6= 1 and every f(x) ∈ F2[x] such that
deg f ≤ t− 1 we have: f(ζ) 6= 0.
Observe that ζ1 + ζ2 + ζ3 = 0 implies ζ1ζ
2 + 1 = ζ3ζ
2 . This yields
2 + 1
= 1. Put ζ = ζ1ζ
Note that ζ 6= 1 and ζ, 1 + ζ ∈ Cp. Consider the products πi,j = ζ i(1 + ζ)j ∈ Cp for 0 ≤ i, j ≤ t− 1. Note that
πi,j, πk,l cannot be the same if i ≥ k and l ≥ j, as then
ζ i−k − (1 + ζ)l−j = 0,
but the left side has degree less than t. In other words, if πi,j = πk,l and (i, j) 6= (k, l), then the pairs (i, j) and
(k, l) are comparable under termwise comparison. In particular, either (k, l) = (i+a, j+b) or (i, j) = (k+a, l+b)
for some pair (a, b) with πa,b = 1.
We next check that there cannot be two distinct nonzero pairs (a, b), (a′, b′) with πa,b = πa′,b′ = 1. As above,
these pairs must be comparable; we may assume without loss of generality that a ≤ a′, b ≤ b′. The equations
πa,b = 1 and πa′−a,b′−b = 1 force a + b ≥ t and (a′ − a) + (b′ − b) ≥ t, so a′ + b′ ≥ 2t. But a′, b′ ≤ t − 1,
contradiction.
If there is no nonzero pair (a, b) with 0 ≤ a, b ≤ t − 1 and πa,b = 1, then all πi,j are distinct, so p ≥ t2.
Otherwise, as above, the pair (a, b) is unique, and the pairs (i, j) with 0 ≤ i, j ≤ t − 1 and (i, j) 6≥ (a, b) are
pairwise distinct. The number of pairs excluded by the condition (i, j) 6≥ (a, b) is (t− a)(t− b); since a+ b ≥ t,
(t− a)(t− b) ≤ t2/4. Hence p ≥ t2 − t2/4 = 3t2/4 as desired.
While the necessary condition given by lemma 23 is quite far away from the sufficient condition given by
lemma 8, it nonetheless suffices for checking that for most primes p, there do not exist three p-th roots of unity
summing to zero. For instance, among the 664578 odd primes p ≤ 108, all but 550 are ruled out by Lemma 23.
(There is an easy argument that t must be odd if p > 3; this cuts the list down to 273 primes.) Each remaining
p can be tested by computing gcd(xp + 1, (x + 1)p + 1); the only examples we found that did not satisfy the
condition of lemma 8 were (p, t) = (73, 9), (262657, 27), (599479, 33), (121369, 39).
5.4 Summary
In the beginning of this section 5 we argued that in order to use the method of [34], (i.e., proposition 5) to obtain
k-query locally decodable codes of length exp(nǫ) for some fixed k and all ǫ > 0, one needs to exhibit a k-nice
sequence of subsets of finite fields. In what follows we use technical results of the previous subsections to show
that the existence of a k-nice sequence implies that infinitely many Mersenne numbers have large prime factors.
Theorem 24 Let k be odd. Suppose there exists a k-nice sequence of subsets of finite fields; then for infinitely
many values of t we have
P (2t − 1) ≥ (t/2)1+1/(k−2). (40)
Proof: Using lemmas 21 and 22 we conclude that a k-nice sequence yields infinitely many primes p such that
ord2(p) ≤ 2p1−1/(k−1). Let p be such a prime and t = ord2(p). Then P (2t − 1) ≥ (t/2)1+1/(k−2).
A combination of lemmas 21 and 23 yields a slightly stronger bound for the special case of 3-nice sequences.
Theorem 25 Suppose there exists a 3-nice sequence of subsets; then for infinitely many values of t we have
P (2t − 1) ≥ (3/4)t2. (41)
We would like to remind the reader that although the lower bounds for P (2t − 1) given by (40) and (41) are
extremely weak light of the widely accepted conjecture saying that the number of Mersenne primes is infinite,
they are substantially stronger than what is currently known unconditionally (2).
6 Conclusion
Recently [34] came up with a novel technique for constructing locally decodable codes and obtained vast im-
provements upon the earlier work. The construction proceeds in two steps. First [34] shows that if there exist
subsets of finite fields with certain ’nice’ properties then there exist good codes. Next [34] constructs nice subsets
of prime fields Fp for Mersenne primes p.
In this paper we have undertaken an in-depth study of nice subsets of general finite fields. We have shown
that constructing nice subsets is closely related to proving lower bounds on the size of largest prime factors of
Mersenne numbers. Specifically we extended the constructions of [34] to obtain nice subsets of prime fields Fp
for primes p that are large factors of Mersenne numbers. This implies that strong lower bounds for size of the
largest prime factors of Mersenne numbers yield better locally decodable codes. Conversely, we argued that if one
can obtain codes of subexponential length and constant query complexity through nice subsets of finite fields then
infinitely many Mersenne numbers have prime factors larger than known currently.
Acknowledgements
Kiran Kedlaya’s research is supported by NSF CAREER grant DMS-0545904 and by the Sloan Research Fel-
lowship. Sergey Yekhanin would like to thank Swastik Kopparty for providing the reference [5] and outlining
the proof of lemma 9. He would also like to thank Henryk Iwaniec, Carl Pomerance and Peter Sarnak for their
feedback regarding the number theory problems discussed in this paper.
References
[1] M. Agrawal, N. Kayal, N. Saxena, “PRIMES is in P,” Annals of Mathematics, vol. 160, pp. 781-793, 2004.
[2] L. Babai, L. Fortnow, L. Levin, and M. Szegedy, “Checking computations in polylogarithmic time,”. In Proc.
of the 23th ACM Symposium on Theory of Computing (STOC), pp. 21-31, 1991.
[3] A. Beimel, Y. Ishai and E. Kushilevitz,“General constructions for information-theoretic private information
retrieval,” Journal of Computer and System Sciences, vol. 71, pp. 213-247, 2005. Preliminary versions in
STOC 1999 and ICALP 2001.
[4] A. Beimel, Y. Ishai, E. Kushilevitz, and J. F. Raymond. “Breaking the O
n1/(2k−1)
barrier for information-
theoretic private information retrieval,” In Proc. of the 43rd IEEE Symposium on Foundations of Computer
Science (FOCS), pp. 261-270, 2002.
[5] J. Bourgain, M. Chang, “A Gauss sum estimate in arbitrary finite fields,” Comptes Rendus Mathematique,
vol. 342, pp. 643-646, 2006.
[6] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. “Private information retrieval,” In Proc. of the 36rd
IEEE Symposium on Foundations of Computer Science (FOCS), pp. 41-50, 1995. Also, in Journal of the
ACM, vol. 45, 1998.
[7] D. Cox, J. Little, D. O’Shea, Ideals, varieties, and algorithms: an introduction to computational algebraic
geometry and commutative algebra. Springer, 1996.
[8] A. Deshpande, R. Jain, T. Kavitha, S. Lokam and J. Radhakrishnan, “Better lower bounds for locally decod-
able codes,” In Proc. of the 20th IEEE Computational Complexity Conference (CCC), pp. 184-193, 2002.
[9] Curtis Cooper, Steven Boone, http://www.mersenne.org/32582657.htm
[10] P. Erdos and T. Shorey, “On the greatest prime factor of 2p − 1 for a prime p and other expressions,” Acta.
Arith. vol. 30, pp. 257-265, 1976.
[11] W. Gasarch, “A survey on private information retrieval,” The Bulletin of the EATCS, vol. 82, pp. 72-107,
2004.
[12] O. Goldreich, “Short locally testable codes and proofs,” Technical Report TR05-014, Electronic Colloquim
on Computational Complexity (ECCC), 2005.
[13] O. Goldreich, H. Karloff, L. Schulman, L. Trevisan “Lower bounds for locally decodable codes and private
information retrieval,” In Proc. of the 17th IEEE Computational Complexity Conference (CCC), pp. 175-183,
2002.
[14] B. Hemenway and R. Ostrovsky, “Public key encryption which is simultaneously a locally-decodable error-
correcting code,” In Cryptology ePrint Archive, Report 2007/083.
[15] J. Katz and L. Trevisan, “On the efficiency of local decoding procedures for error-correcting codes,” In Proc.
of the 32th ACM Symposium on Theory of Computing (STOC), pp. 80-86, 2000.
[16] I. Kerenidis, R. de Wolf, “Exponential lower bound for 2-query locally decodable codes via a quantum
argument,” Journal of Computer and System Sciences, 69(3), pp. 395-420. Earlier version in STOC’03.
quant-ph/0208062.
[17] R. Lidl and H. Niederreiter, Finite Fields. Cambridge: Cambridge University Press, 1983.
[18] L. Murata, C. Pomerance, “On the largest prime factor of a Mersenne number,” Number theory, CRM Proc.
Lecture Notes of American Mathematical Society vol. 36, pp. 209-218, 2004.
[19] M. Murty and S. Wong, “The ABC conjecture and prime divisors of the Lucas and Lehmer sequences,” In
Proc. of Milennial Conference on Number Theory III, (Urbana, IL, 2000) (A. K. Peters, Natick, MA, 2002)
pp. 43-54.
[20] K. Obata, “Optimal lower bounds for 2-query locally decodable linear codes,” In Proc. of the 6th RANDOM,
vol. 2483 of Lecture Notes in Computer Science, pp. 39-50, 2002.
[21] A. Polishchuk and D. Spielman, ”Nearly-linear size holographic proofs,” In Proc. of the 26th ACM Sympo-
sium on Theory of Computing (STOC), pp. 194-203, 1994.
[22] C. Pomerance, “Recent developments in primality testing,” Math. Intelligencer, 3:3, pp. 97-105, (1980/81).
[23] P. Raghavendra, “A Note on Yekhanin’s locally decodable codes,” In Electronic Colloquium on Computa-
tional Complexity Report TR07-016, 2007.
[24] A. Romashchenko, “Reliable computations based on locally decodable codes,” In Proc. of the 23rd Inter-
national Symposium on Theoretical Aspects of Computer Science (STACS), vol. 3884 of Lecture Notes in
Computer Science, pp. 537-548, 2006.
[25] A. Schinzel, “On primitive factors of an − bn,” In Proc. of Cambridge Philos. Soc. vol. 58, pp. 555-562,
1962.
[26] C. Stewart, “The greatest prime factor of an − bn,” Acta Arith. vol. 26, pp. 427-433, 1974/75.
[27] C. Stewart, “On divisors of Fermat, Fibonacci, Lucas, and Lehmer numbers,” In Proc. of London Math. Soc.
vol. 35 (3), pp. 425-447, 1977.
[28] M. Sudan, Efficient checking of polynomials and proofs and the hardness of approximation problems. PhD
thesis, University of California at Berkeley, 1992.
[29] L. Trevisan, “Some applications of coding theory in computational complexity,” Quaderni di Matematica,
vol. 13, pp. 347-424, 2004.
[30] S. Wehner and R. de Wolf, “Improved lower bounds for locally decodable codes and private information re-
trieval,” In Proc. of 32nd International Colloquium on Automata, Languages and Programming (ICALP’05),
LNCS 3580, pp. 1424-1436.
[31] Lenstra-Pomerance-Wagstaff conjecture. (2006, May 22). In Wikipedia, The Free Encyclopedia. Re-
trieved 00:18, October 3, 2006, from http://en.wikipedia.org/w/index.php?title=Lenstra-Pomerance-
Wagstaff conjecture&oldid=54506577
[32] S. Wagstaff, “Divisors of Mersenne numbers,” Math. Comp., 40:161, pp. 385-397, 1983.
[33] D. Woodruff, “New lower bounds for general locally decodable codes,” Electronic Colloquium on Computa-
tional Complexity, TR07-006, 2007.
[34] S. Yekhanin, “Towards 3-query locally decodable codes of subexponential length,” In Proc. of the 39th ACM
Symposium on Theory of Computing (STOC), 2007.
[35] S. Yekhanin, Locally decodable codes and private information retrieval schemes. PhD thesis, MIT, to appear.
