Authors Avraham Ben-Aroya, Amnon Ta-Shma,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272
www.theoryofcomputing.org
Constructing Small-Bias Sets from
Algebraic-Geometric Codes∗
Avraham Ben-Aroya† Amnon Ta-Shma‡
Received February 21, 2011; Revised October 29, 2012; Published February 20, 2013
Abstract: We give an explicit construction of an ε-biased set over k bits of size
5/4
k
O 2 .
ε log(1/ε)
This improves upon previous explicit constructions when ε is roughly (ignoring logarith-
mic factors) in the range [k−1.5 , k−0.5 ]. The construction builds on an algebraic-geometric
code. However, unlike previous constructions, we use low-degree divisors whose degree is
significantly smaller than the genus.
ACM Classification: F.2.2, G.2
AMS Classification: 94B27, 12Y05
Key words and phrases: small-bias sets, algebraic geometry, AG codes, Goppa codes
1 Introduction
Explicitly constructing combinatorial objects with certain properties (such as expander graphs, extractors,
error correcting codes and others) is an intriguing challenge in computer science. Often, it is easy to
verify that a random object satisfies the required property with high probability, while it is difficult to pin
down such an explicit object.
∗ A preliminary version of this paper appeared in FOCS 2009 [3].
† Supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities, and by the European
Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848.
‡ Supported by Israel Science Foundation grant 217/05 and by USA Israel BSF grant 2004390.
© 2013 Avraham Ben-Aroya and Amnon Ta-Shma
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a005
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
In most cases it is believed (and sometimes proven) that a random object is nearly optimal. Therefore,
giving an optimal explicit construction becomes a derandomization problem. There are, however, rare
cases in which explicit constructions outperform naive random constructions. Perhaps the most remarkable
example of this type is that of algebraic-geometric codes (AG codes). In the seminal work of Tsfasman et
al. [10] it was shown that there are algebraic-geometric codes over constant size alphabets that lie above
the Gilbert-Varshamov bound, a bound that random codes achieve and that was believed to be optimal at
the time.
The important case of binary error correcting codes is still open. In the binary case, the Gilbert-
Varshamov bound gives the best known (explicit or non-explicit) codes to date. For codes with distance
close to half, the bound shows that random linear codes of length n = O(k/ε 2 ) are [n, k, (1/2 − ε)n]2
codes. Finding an explicit construction that attains this bound is an open problem.
Another closely related question is that of finding an [n, k, (1/2 − ε)n]2 binary code, in which the
relative weight of every non-zero codeword is in the range [1/2 − ε, 1/2 + ε]. Such codes are called
ε-balanced and they are related to another kind of combinatorial objects called ε-biased sets. An ε-biased
set is a set S ⊆ {0, 1}k such that for every non-empty subset T ⊆ [k], the binary random variable i∈T si ,
L
where s is sampled uniformly from S, has bias at most ε. It turns out that ε-biased sets are just ε-balanced
codes in a different guise: the rows of a matrix whose columns generate an ε-balanced code form an
ε-biased set, and vice versa. In terms of parameters, an [n, k]2 ε-balanced code is equivalent to an ε-biased
set S ⊆ {0, 1}k of size n.
The status of ε-balanced codes is similar to that of [n, k, (1/2 − ε)n]2 codes. In both cases the
probabilistic method gives non-explicit [n, k]2 ε-balanced codes with n = O(k/ε 2 ), whereas the best lower
bound is !
k
n=Ω .
ε 2 log( ε1 )
For a discussion of these bounds see [2, Section 7].
There are several explicit constructions of such codes. Naor and Naor [7] give a construction
with n = k · poly(ε −1 ), which was later improved in [1] to n = O(k/ε 3 ). Alon et al. [2] establish the
incomparable bound !
k2
n=O .
ε 2 log2 ( εk )
Concatenating algebraic-geometric codes with the Hadamard code gives
!
k
n=O .
ε 3 log( ε1 )
In this paper we show an explicit construction of an [n, k]2 ε-balanced code with
!5/4
k
n=O ,
ε 2 log( ε1 )
which improves upon previous explicit constructions when ε is roughly (ignoring logarithmic factors) in
the range of k−1.5 ≤ ε ≤ k−0.5 (see Figure 1).
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 254
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
7
k
AGHP [1]
Algebraic Geomtric code above the genus
k6 This paper
Gilbert−Varshamov bound
5
k
k4
n=kd
k3
k2
1
k
k−0.25 k−0.5 k−0.75 k−1 k−1.3 k−1.5 k−1.8 k−2
ε = k−c
Figure 1: Constructions of ε-biased sets for ε = k−c .
The construction is simple and can be described by elementary means. We first take a finite field Fq
of the appropriate size. We then carefully choose a subset A of Fq × Fq . The elements in the ε-biased set
are indexed by pairs ((a, b), c) ∈ A × Fq . For each ((a, b), c) ∈ A × Fq the corresponding element is the bit
vector h(ai b j ), ci2 i, j , where (i, j) range over all integers i, j whose sum is bounded by an appropriately
chosen parameter and the inner product is of the binary representation of the elements in Fq . The analysis
of the construction relies on Bézout’s Theorem.
To put the construction in context, we need to move to the terminology of algebraic function fields.
AG codes are evaluation codes where a certain set of evaluation functions is evaluated at a chosen set of
evaluation points. The space of evaluation functions used is a vector space (this is the reason we get a
linear error correcting code) and is determined by a divisor G of an algebraic function field F. We explain
these notions in Section 3, and for the time being continue with an intuitive discussion. We denote the
code associated with a divisor G by C(G).
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 255
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
The code C(G) has the following parameters.
• The length of the code is the number of evaluation points and is denoted by N = N(F).
• The distance of the code is N − deg(G), where deg(G) is the degree of G (formally defined in
Section 3).
• The dimension of the code, dim(G), is the dimension of the vector space of evaluation functions.
When the “degree” of G is larger than the genus g of the function field F (again, defined in Section 3)
the Riemann-Roch Theorem [8, Thm I.5.17] tells us exactly what the dimension dim(G) is, and it turns
out that
dim(G) = deg(G) − g + 1 .
This almost matches the Singleton bound, dim(G) ≤ deg(G) + 1, except for a loss of g. Thus, our goal
is to get as many evaluation points as possible while keeping the genus small. Indeed, a lot of research
has been done on the best possible ratio between the length of the code N(F) and the genus g. The
bottom line of this research, roughly speaking, is that N(F) can be larger than the genus by at most a
√
multiplicative q − 1 factor and this is essentially optimal.
A simple check shows that when deg(G) is larger than the genus, an AG code concatenated with the
Hadamard code cannot give ε-balanced codes with n better than
!
k
O
ε 3 log( ε1 )
(see Section 3.2). In contrast, our construction takes as an outer code an AG code C(G) where deg(G) is
much smaller than the genus, and we show that this leads to a better code.
A natural question is whether the ε-balanced codes we achieve are the best binary codes one can
achieve using this approach. We do not know the answer to this question. When deg(G) is smaller than
the genus, one cannot use the Riemann-Roch Theorem, and estimating dim(G) is often a challenging
task. Furthermore, dim(G) now depends on G itself, and not just on its degree as before. However, we
can formulate the question as follows. The important thing for us is not the best possible ratio between
the number of evaluation points N(F) and the genus. Instead, we are interested in the best possible ratio
between N(F) and deg(G), where G is a low-degree divisor having a large dimension.
Following the preliminary version of our work [3], Felipe Voloch [11] used a variant of Castelnuovo’s
bound to show our approach cannot lead to error correcting codes approaching the Gilbert-Varshamov
bound. We show that a careful analysis of Voloch’s argument implies that all k-dimensional ε-balanced
codes built using our approach must have length
!
k
n=Ω .
ε 2.5 log2 ( ε1 )
The rest of the paper is organized as follows. In Section 2 we describe the construction and its analysis
using Bézout’s Theorem. Section 3 contains a description of the same construction in the terminology
of algebraic function fields. In Subsection 3.1 we give the necessary background on algebraic function
fields and geometric Goppa codes. Finally, in Section 4 we analyze the limits of our approach based on
Voloch’s work.
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 256
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
2 A self-contained elementary description of the construction
We first recall the definition of an ε-biased set.
Definition 2.1. A set S ⊆ {0, 1}k is ε-biased if for every nonempty T ⊆ [k],
1
∑ (−1)∑i∈T si ≤ ε .
|S| s∈S
The construction Given k and ε, let p = 2` be a power of 2 in the range
" 1/4 #
1 k 1/4 k
2
, 2 .
2 ε ε
That is,
1 k k
2
≤ p4 ≤ 2 .
16 ε ε
2 3
Define q = p and r = ε p . Let Fq denote the finite field with q elements and F p its subfield with p
elements. Consider the vector space of bivariate polynomials over Fq with total degree at most r/(p + 1).
r r
V = φ ∈ Fq [x, y] : deg(φ ) ≤ = Span xi y j : i + j ≤ .
p+1 p+1
We denote the dimension of this space (over Fq ) by k0 . It follows that
2 2 6
0 r ε p 2 4
k =Θ = Θ = Θ ε p = Θ(k) .
p2 p2
Let A ⊆ Fq × Fq be the set of roots of the polynomial y p + y − x p+1 . The ε-biased set over k0 bits that
we construct is
bin(ai b j ), bin(c) 2 i+ j≤ r : (a, b) ∈ A and c ∈ Fq ,
S=
p+1
where bin : Fq → Z2` 2`
2 is any isomorphism between the additive group of Fq and the vector space Z2 and
2`
h·, ·i2 denotes inner product over Z2 .
The analysis Clearly, |S| = q|A|. We further claim:
Claim 2.2. The cardinality of A is p3 .
Proof. The trace function Tr(y) = y p + y maps Fq to F p . We claim that for every α ∈ F p , the number
of solutions in Fq to Tr(y) = α is p. To see this, observe that Tr is a linear function. Hence, the set of
solutions to Tr(y) = 0 is a subgroup of Fq that has at most p elements. For every α ∈ F p , the set of
solutions to Tr(y) = α is either empty or a coset of this subgroup. As every element of Fq is in one of
these cosets, it must be the case that for every α ∈ F p there are exactly p solutions.
The norm function N(x) = x p+1 also maps Fq to F p . Thus, for every α ∈ Fq there are exactly p values
β ∈ Fq such that Tr(β ) = N(α). Therefore, |A| = p3 .
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 257
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
In order to bound the bias ε, we need to invoke Bézout’s theorem, reviewed below. First, we need to
show that the bivariate polynomial y p + y − x p+1 is irreducible. We do this using Eisenstein’s Criterion:
Theorem 2.3 (Eisenstein’s Criterion [6, Thm 3.1]). Let U be a unique factorization ring and let K be its
field of fractions. Let f (x) = ∑ni=0 ai xi be a polynomial of degree n ≥ 1 in U[x]. Let ρ be a prime of U,
and assume:
• an 6= 0 (mod ρ),
• for every i < n, ai = 0 (mod ρ),
• a0 6= 0 (mod ρ 2 ).
Then f (x) is irreducible in K[x].
With that we conclude:
Claim 2.4. The polynomial y p + y − x p+1 is irreducible over Fq .
Proof. This follows from Eisenstein’s Criterion. The unique factorization ring we consider is U = Fq [y].
The prime element we use is ρ = y. The leading coefficient is a p+1 = −1 and −1 6= 0 (mod y). Every
other coefficient except the last is 0, hence it is 0 (mod y). The last coefficient is a0 = y p +y = 0 (mod y).
Finally, since p ≥ 2, y p = 0 (mod y2 ) but y 6= 0 (mod y2 ), hence a0 = y p + y 6= 0 (mod y2 ). Therefore
the univariate polynomial (in x) is irreducible over the field of fractions. As one of the coefficients is −1,
it follows that the bivariate polynomial is irreducible over the field Fq (see [6, Thm 2.3]).
We are now ready to recall Bézout’s Theorem and apply it to prove S is indeed ε-biased.
Theorem 2.5 (Bézout’s Theorem [4, Section 5.3]). Suppose φ and ψ are two bivariate polynomials over
some field. If φ and ψ have more than deg(φ ) · deg(ψ) common roots then they have a common factor.
√
Theorem 2.6. For every k and ε such that ε < 1/ k, S is an ε-biased set over k0 = Ω(k) bits of size
5/4
k
O 2 .
ε
Proof. By Claim 2.2,
5/4
5 k
|S| = |A| · q = p = O 2 .
ε
We now show that S is ε-biased. Let T ⊆ [k0 ] be some non-empty set. We identify [k0 ] with the set
r
(i, j) : i + j ≤
p+1
and T with the corresponding subset.
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 258
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
Let s ∈ S be an element specified by the pair ((a, b), c) ∈ A × Fq . Then,
* ! +
i j i j
∑ s(i, j) = ∑ bin(a b ), bin(c) 2 = bin ∑ ab , bin(c) .
(i, j)∈T (i, j)∈T (i, j)∈T 2
The polynomial φT = ∑(i, j)∈T xi y j is a non-zero polynomial. Clearly, for any (a, b) which is not a
root of φT , the inner product will be unbiased when ranging √
over c (i. e., exactly half of the values for c
will make the inner product 0). From the assumption ε < 1/ k it follows that deg(φT ) < p + 1, since
deg(φT ) r √
≤ 2
< ε p ≤ k1/4 ε < 1 .
p+1 (p + 1)
Hence, by Claim 2.4 it follows that φT and y p + y − x p+1 have no common factors. Therefore, by Bézout’s
r
theorem we conclude that the number of roots of φT that are in A is at most ( p+1 ) · (p + 1) = r and
1 r
∑ (−1)∑i∈T si ≤ |A| = ε .
|S| s∈S
Remark 2.7. The above construction can be improved to an ε-biased set of size
!5/4
k ε 1
O for every k and ε such that <√ .
ε log( ε1 )
q
2 k
log( ε1 )
To achieve this we choose !1/4
k
p=Θ .
ε log( ε1 )
2
We then observe that instead of taking a basis for V over Fq , we can actually afford to take a basis over F2 .
Finally, we need to use the fact that by the constraints we have on ε, it follows that log(1/ε) = Θ(log(p)).
When we restate the construction in the terminology of algebraic function fields, we also include this
improvement.
3 Restating the construction in the terminology of algebraic function fields
Without putting the above construction in the proper context, it may appear coincidental. We now describe
the general framework of algebraic-geometric codes and explain why the above construction fits into this
framework.
3.1 Algebraic geometry
We recall a few notions from the theory of algebraic function fields. A detailed exposition of the subject
can be found, e. g., in [8].
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 259
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
Let Fq denote the finite field with q elements. The polynomial ring Fq [x], where x is transcendental
over Fq , is the set of all polynomials in x with coefficients in Fq . The rational function field Fq (x), where
x is transcendental over Fq , contains all rational functions in x with coefficients in Fq . A field F is an
algebraic function field over Fq , denoted F/Fq , if F is a finite algebraic extension of Fq (x).
A place P of F/Fq is a maximal ideal of some valuation ring O of the function field. We denote
by OP the valuation ring that corresponds to the place P. We denote by vP the discrete valuation that
corresponds to the valuation ring OP . Therefore, we can write P and OP as
P = {y ∈ F : vP (y) > 0} and OP = {y ∈ F : vP (y) ≥ 0} .
Since P is a maximal ideal, FP = OP /P is a field. In fact, it is a finite field [8, Proposition I.1.14]. For
every y ∈ OP , y(P) denotes y (mod P) and is an element of FP . It can be thought of as the evaluation of
the function y at the “evaluation point” P. The degree of a place P is defined to be deg(P) = [FP : Fq ],
i. e., the dimension of FP as a vector space over Fq . In particular, if a place P is of degree 1 then FP is
isomorphic to Fq and the evaluation of y at the place P is an element of Fq .
We proceed with a simple example that illustrates the above notions.
Example 3.1. The rational function field Fq (x)/Fq is the simplest algebraic function field. For every
irreducible polynomial p(x) let O p denote the set of rational functions r(x) = u(x)/w(x) whose denom-
inator w(x) is not divisible by p. The set O p forms a ring. Furthermore, for every rational function r,
either r or r−1 belongs to O p , making O p a valuation ring. The place Pp is the set of rational functions
r(x) = u(x)/w(x) for which p divides u but does not divide w.
There is exactly one more valuation ring in Fq (x). Let O∞ denote the set of rational functions
r(x) = u(x)/w(x) for which deg(w) ≥ deg(u). Again, O∞ is a ring and furthermore, for every rational
function r(x) = u(x)/w(x), either r or r−1 belongs to O∞ , making O∞ a valuation ring. The place P∞ is
the set of rational functions r(x) = u(x)/w(x) for which deg(w) > deg(u).
For an irreducible polynomial p, the discrete valuation v p corresponding to O p is defined as follows.
For a polynomial u(x) ∈ Fq [x], v p (u) is the largest integer k such that pk divides u. For a rational function
r(x) = u(x)/w(x), v p (r) = v p (u) − v p (w). Thus, v p (r) counts the number of zeroes (or poles) that r has
when the irreducible polynomial p(x) is zero. If p is linear, i. e., p(x) = x − α, v p (r) counts the number of
zeroes (or poles) the polynomial p(x) has when setting x = α. If in addition r = u/w belongs to O p , i. e.,
p does not divide w, then r(Px−α ) = r mod (x − α) is well defined, and, in fact, is the element u(α)/w(α)
in Fq .
The discrete valuation v∞ corresponding to O∞ is defined as follows. For a polynomial u(x) ∈ Fq [x],
v∞ (u) is − deg(u). For a rational function r(x) = u(x)/w(x), v∞ (r) = v∞ (u) − v∞ (w) = deg(w) − deg(u).
Thus, v∞ (r) counts the number of zeroes (or poles) that r has when x = ∞. If r(x) = u(x)/w(x) belongs
to O∞ , i. e., deg(w) ≥ deg(u), then r(P∞ ) is well defined, and is either zero (if deg(w) > deg(u)) or the
element uk /wk in Fq , where uk and wk are the leading coefficients of the polynomials u and w respectively.
We let PF denote the set of places of F, and N(F) the number of places of degree 1 in F/Fq . N(F) is
always finite. DF is the free abelian group over the places of F. A divisor is an element in this group, i. e.,
it is a formal sum G = ∑P∈PF nP P with nP ∈ Z and where nP 6= 0 for only a finite number of places. We
also denote vP (G) = nP . The degree of the divisor ∑P nP P is defined to be ∑P nP · deg(P), and is always
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 260
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
finite. We say G1 ≥ G2 if G1 is component-wise larger than G2 , i. e., vP (G1 ) ≥ vP (G2 ) for every place P.
The support of a divisor G is Supp(G) = {P ∈ PF : vP (G) 6= 0}.
Each element 0 6= x ∈ F is associated with two divisors. The first is called the principal divisor of x
and it is defined by
(x) = ∑ vP (x)P .
P
The degree of a principal devisor is always 0. The second is the pole divisor of x and it is defined by
(x)∞ = ∑ −vP (x)P .
P:vP (x)<0
If x ∈ F \ Fq then deg((x)∞ ) = [F : Fq (x)].
Example 3.2 (Continued from Example 3.1). Let u ∈ Fq [x] be an arbitrary nonconstant polynomial. Then,
u has a pole at P∞ (since v∞ (u) < 0) and zero at Pp , for every irreducible polynomial p that divides u (since
v p (u) > 0). Thus, (u)∞ = deg(u)P∞ and deg((u)∞ ) = deg(u). Also, it turns out that deg(Pp ) = deg(p).
Thus, ∑ p v p (u) is the number of irreducible factors u has, and ∑ p v p (u) deg(Pp ) is the degree of u. In
total, deg((u)) = 0.
For a divisor G, we define the Riemann-Roch space L(G) to be:
L(G) = {x ∈ F : (x) ≥ −G} ∪ {0} .
Example 3.3 (Continued from Examples 3.1 and 3.2). For the divisor G = kP∞ the Riemann-Roch space
L(G) is the set of all polynomials of degree at most k over Fq .
The set L(G) is a vector space and furthermore has finite dimension. We define the dimension of G
by dim(G) = dim L(G) and we use the two notations interchangeably. The fact that the degree of each
principal divisor is 0 implies that if deg(G) < 0 then dim(L(G)) = 0.
3.1.1 Geometric Goppa codes
A Goppa code is specified by a triplet (F,Y, G), where F/Fq is a function field, Y = {P1 , . . . , Pn } is a set
of places of degree 1 and G is an arbitrary divisor with no support over any place in Y . Notice that for
any x ∈ L(G), vPi (x) ≥ 0 and therefore x ∈ OPi and x(Pi ) ∈ Fq . The triplet (F,Y, G) specifies the code:
C(Y ; G) = {(x(P1 ), . . . , x(Pn )) : x ∈ L(G)} ⊆ Fq n .
Claim 3.4 ([8, Cor II.2.3]). If deg(G) < n then C(Y ; G) is an [n, dim(G), n − deg(G)] linear code over
Fq .
We call n − deg(G) the designated distance of the code. Given the designated distance d, we would
like to find a code G with that designated distance and maximal dimension, i. e., maximize dim(G). It
turns out that for every G, dim(G) ≤ deg(G) + 1 (which is the Singleton bound in coding theory). Our
goal is to minimize the gap between dim(G) and deg(G). It turns out that for any function field F/Fq
there exists a constant g ∈ N, such that for any divisor G ∈ DF , deg(G) − dim(G) ≤ g − 1. The minimal
integer with this property is called the genus of F/Fq . The Riemann-Roch Theorem states that:
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 261
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
Theorem 3.5 ([8, Thm I.5.17]). If deg(G) ≥ 2g − 1 then dim(G) = deg(G) − g + 1.
This, in particular, allows one to easily compute the dimension of the code when deg(G) ≥ 2g − 1.
The only remaining question is whether there are function fields F/Fq with a large number N = N(F) of
evaluation points (i. e., degree 1 places) and a small genus g. A negative answer to that question is given
by the Hasse-Weil bound:
Theorem 3.6 (Hasse-Weil bound [8, Thm V.2.3]). Let F/Fq be a function field of genus g. Then, the
√
number N of places of degree one satisfies N ≤ (q + 1) + 2 qg.
The Drinfeld-Vlăduţ bound tells us that when g tends to infinity, the bound can be strengthened by
√
about a factor of 2, and roughly speaking, N ≤ g( q − 1). This is tight for prime power squares q.
On the positive side, the good news is that following much research, there are several beautiful explicit
constructions that meet the Drinfeld-Vlăduţ bound, and we refer the interested reader to the beautiful
survey paper [5, Chapter 1].
In this paper we look at divisors G whose degree is smaller than the genus. Much less is known about
such small-degree divisors. In this regime, dim(G) depends on the divisor G itself, and not only on its
degree, as is the case when deg(G) ≥ 2g − 1. For some special algebraic function fields the vector space
L(G) (and therefore also its dimension) is known in full. We discuss this below.
3.2 Concatenating AG codes with Hadamard
In this section we consider the concatenation of an outer code with the Hadamard code. If the outer code
is an [n1 , k1 , d]q code and q is a power of two, then concatenating it with the [q, log q, q/2]2 Hadamard
code gives an [n = n1 q, k = k1 log q]2 code that is ε = (n1 − d)/n1 balanced, because non-zero symbols
in the outer code expand by the concatenation to perfectly balanced blocks.1
Using a [q, k1 , q − k1 + 1]q Reed-Solomon code as the outer code, one gets an [n = q2 , k = k1 log q]2
code that is ε < k1 /q balanced. Rearranging the parameters, this gives an [n, k]2 ε-balanced code with
!2
k
n=O . (3.1)
ε log( εk )
This is one of the constructions in [2].
Taking the outer code to be an [N, dim(G), N − deg(G)]q AG code C(Y ; G) over Fq and concatenating
it with Hadamard, we get an [n = Nq, k = dim(G) log q]2 code that is ε = deg(G)/N balanced. We can
√
choose an AG code which uses a curve of genus g with N = Θ(g q) degree 1 places (the asymptotic is
over g going to infinity). Picking the divisor G to be of degree deg(G) ≥ 2g and setting q = 1/ε 2 results
in !
deg(G) dim(G) + g − 1 k
N= = =Θ ,
ε ε ε log( ε1 )
1 If q is a power of 2, then the resulting concatenated code is linear. Concatenation is well defined even when q is not a power
of 2. In such a case we embed Fq into F2 dlog qe using any one-to-one mapping. The resulting (non-linear) code has essentially
the same dimension and distance as in the previous case – the only difference is a small loss due to the fact that 2dlog qe is slightly
larger than q. From now on we will discuss the simpler case where q is a power of two, keeping in mind that everything also
holds for arbitrary q.
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 262
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
where the second equality follows from the Riemann-Roch Theorem. Thus, we get an ε-balanced code of
length !
k
n = Nq = O . (3.2)
ε 3 log( ε1 )
√
In fact, if one takes an AG code over Fq with large genus g ≥ q then
dim(G) k 1
N≥ = and q = Ω 2
ε ε log q ε
√
and equation (3.2) is tight. Taking an AG code with a small genus g ≤ q is essentially equivalent to
taking a Reed-Solomon outer code and cannot be better (up to constant factors) than equation (3.1). In
what follows, we show one can improve on both bounds when the AG code has degree much smaller than
the genus.
So we now turn our attention to the case where deg(G) ≤ 2g − 1. In this case dim(G) depends on
the divisor G and not just its degree. One special case is the case where G = rQ, r ∈ N and Q is a place
of degree 1. For any such r, dim(rQ) is either equal to dim((r − 1)Q) or to dim((r − 1)Q) + 1. In the
former case r is said to be a gap number of Q. The Weierstrass Gap Theorem [8, Thm I.6.7] says that for
any place Q there are exactly g = genus(F/Fq ) gap numbers, and they are all in the range [1, 2g − 1].
The non-gap numbers (also called pole numbers) form a semigroup of N (i. e., a set that is closed
under addition). This semigroup is sometimes referred to as the Weierstrass semigroup of Q. We say that
a semi-group S is generated by a set of elements {gi }, if each gi ∈ S and, furthermore, every element
s ∈ S can be expressed as s = ∑ ai gi with ai ∈ N.
The structure of the Weierstrass semigroup is crucial to our construction. We know that there are
exactly g non-gap elements of this semigroup in the range [1, 2g]. If these elements are too concentrated on
the upper side of the range then the behavior of dim(rQ) will be very similar to the case where r > 2g − 1.
√
Thus, our goal is to find a function field F that has many places of degree 1, say, N(F) ≥ Ω(g q), while
at the same time F has a degree 1 place Q with a “good” Weierstrass semigroup.
3.3 The construction
Let p be a prime power and q = p2 . The Hermitian function field over Fq (see [8, Lemma VI.4.4]) can be
represented as the extension field Fq (x, y) of the rational function field Fq (x) with y p + y = x p+1 . This
function field has 1 + p3 places of degree one. First, there is the common pole Q∞ of x and y. Moreover,
for each pair (α, β ) ∈ Fq with β p + β = α p+1 there is a unique place Pα,β of degree one such that
x(Pα,β ) = α and y(Pα,β ) = β and we already saw there are p3 such pairs. The genus of the Hermitian
function field is g = p(p − 1)/2.
For the outer code we take the Goppa code Cr = C(Y, G = rQ∞ ), where Y is the set of all degree 1
places Pα,β mentioned above and r = ε p3 . The Weierstrass semigroup of G is generated by p and p + 1,
and a basis for L(G) = L(rQ∞ ) is
i j
x y : j ≤ p − 1 and ip + j(p + 1) ≤ r .
The dimension of the code is
{(i, j) : j ≤ p − 1 and ip + j(p + 1) ≤ r} .
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 263
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
We can now see the similarity between this construction and the one in Section 2. The parameter r is
chosen such that the constraint ip + j(p + 1) ≤ r forces j ≤ p − 1. Therefore, both use evaluations of low
degree bivariate polynomials over the same set of p3 points.2
Theorem 3.7. For every k and every ε such that
ε 1
p ≤√ ,
log(1/ε) k
there exists an explicit [n, Ω(k)]2 code that is ε-balanced, with
5/4
k
n=O 2 .
ε log(1/ε)
Proof. For a given k and ε, let
" 1/4 1/4 #
1 k k
p∈ ,
2 ε 2 log(1/ε) ε 2 log(1/ε)
be a power of two. It can verified that
1 1
≤ ε ≤
16p4 p
as
2 1/4 1/4
ε2
1 ε log(1/ε)
≥ ≥ ε 2 log(1/ε) · = ε
p k log(1/ε)
and
1 2 2 1 k 1
ε = ε · ≥ ε · log ≥ 4
≥ ,
ε ε 16p 16p4
and so log(1/ε) = Θ(log(p)).
Let r = ε p3 and let Fq be the field with q = p2 elements. Let F denote the Hermitian function field
over Fq and let Y denote its set of places of degree 1, excluding Q∞ . This implies that |Y | = p3 . Define
the divisor G to be G = rQ∞ . Since r ≤ p2 ,
2
r 2 4
k
dim(rQ∞ ) ≥ =Ω ε p =Ω .
2(p + 1) log(p)
By Claim 3.4, the Goppa code that is obtained from the triplet (F,Y, G) is a
3 k 3
p ,Ω , p −r
log(p) p2
2 The only slight difference is that in this construction we take all bivariate polynomials with bounded weighted total degree.
However, the weight is nearly identical for both variables and so this does not affect much the parameters of the construction.
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 264
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
code. Concatenating this code with Hadamard gives a [p5 , Ω(k)]2 code that is ε-balanced (since r/p3 = ε).
Now, by our choice of p, it follows that
k
= Θ(p4 )
ε 2 log( ε1 )
and therefore !5/4
k
n = p5 = O
ε 2 log( ε1 )
as desired.
4 Limits of the approach
As explained in Section 3.1.1, the genus measures the maximal loss in dimension compared to the degree.
The Drinfeld-Vlăduţ bound implies that the number of evaluation points (which is bounded by the number
√
of degree one places N(F)) is at most O(g q) when N(F) q. In Section 3.2 we saw this implies
that when deg(G) > 2g, concatenating the best AG code C(Y ; G) with the Hadamard code cannot give
ε-balanced codes of dimension k and length
k
n=o 3 .
ε log(1/ε)
Our construction shows that substantially better results are possible when deg(G) g. Namely, we
show that there exists a code C(Y ; G) with deg(G) g such that when this code is concatenated with
Hadamard, it gives a k-dimensional ε-balanced code of length
5/4 !
k
n=O .
ε 2 log(1/ε)
It is therefore natural to ask what are the limits of our approach. More concretely we ask what are the best
codes one can construct by concatenating an AG code with a Hadamard code? Let us state the question
precisely. We look at constructions of the following structure:
• An outer AG code C = C(Y ; G), defined by an algebraic function field F/Fq , a set of degree 1
places Y and a divisor G ∈ DF with no support over any place in Y .
• An inner Hadamard code.
In the analysis we view C as a [|Y |, dim(G), |Y | − deg(G)]q code, and then the concatenated code has
parameters
1 deg(G)
|Y |q, dim(G) log(q), − .
2 |Y | 2
Notice that it may be the case that C has better distance than the so-called designated distance, but as
far as we are concerned the analysis does not take advantage of that, and we take the distance to be
|Y | − deg(G).
In this section we prove:
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 265
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
Theorem 4.1. Any ε-balanced [n, k]2 code that is constructed and analyzed as above, must have
( )!
k k 1
n≥Ω · min ,√ .
ε2 log2 ( εk ) ε log( εk )
For the proof we need definitions and theorems about finite extensions of algebraic functions fields.
Specifically, for an extension F of a function field F 0 , we use the following notation:
• A place P ∈ PF lying over a place P0 ∈ PF 0 , denoted by P|P0 , see [8, Def III.1.3],
• The ramification index of P over P0 , denoted by e(P|P0 ), see [8, Def III.1.5],
• The conorm of a divisor G0 ∈ DF 0 , denoted by ConF/F 0 (G0 ), see [8, Def III.1.8].
For more details we refer the reader to [8, Chapter III].
4.1 AG theorems about degree vs. dimension
It turns out that the above question boils down to the question of whether there are function fields with
many degree 1 places (compared to the genus) and with low-degree divisors (of degree much smaller
than the genus) of high dimension. We start by presenting two AG theorems relating degree to dimension
in the small degree regime (when the degree is smaller than the genus).
The first argument we present shows that any divisor with non-trivial dimension must have degree at
least N(F)/(q + 1). The argument was shown to us by Henning Stichtenoth [9].
Lemma 4.2. Let F/Fq be a function field and G ∈ DF a divisor with dim(G) > 1. Then N(F) ≤
deg(G) · (q + 1).
Proof. As dim(G) > 1, there exists some x ∈ F \ Fq such that (x) ≥ −G. Fix any such x. In particular,
deg((x)∞ ) ≤ deg(G). Also, by [8, Thm I.4.11], deg(x)∞ = [F : Fq (x)]. We may view F as a finite
extension over the rational function field Fq (x). Every place of degree 1 of F lies above some place of
degree 1 of Fq (x). There are exactly q + 1 places of degree 1 of Fq (x), and each one of them may split to
at most [F : Fq (x)] places of degree 1 of F (by the fundamental equality, [8, Thm III.1.11]). Altogether,
N(F) ≤ (q + 1)[F : Fq (x)] = (q + 1) deg(x)∞ ≤ (q + 1) deg(G).
Remark 4.3. Lemma 4.2 only uses the fact that G is non-trivial. We wonder if one can strengthen the
lemma for divisors G of high dimension. In particular, is it true that if dim(G) > ` then
deg(G) · (q + 1)
N(F) ≤
f (`)
for some function f that goes to infinity with `?
We now move to the second theorem. For a set S ⊆ F, where F is a field, let Closure(S) denote the
minimal subfield of F that contains S. Following our work, Voloch [11] showed, based on the Castelnuovo
bound, that:
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 266
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
Theorem 4.4 ([11, based on the Castelnuovo bound]). Let K be an arbitrary field. Let F/K be a
function field of genus g. Let G ∈ DF be a divisor with degree d + 1 and dimension ` + 2 such that
Closure(L(G)) = F. Let m = d div ` and r = d mod `. Then
g ≤ m(m − 1)` + m(2r + 1) ,
and, in particular, g ≤ m(m + 1)`.
Using Theorem 4.4 requires an assumption on the AG code, namely, that the closure of the Riemann
space of the divisor used to define the code is the entire function field F. The following lemma, based on
private communication with Voloch, shows that this assumption is inessential when analyzing the rate
versus distance problem.
Lemma 4.5. Let K be a finite field, F/K be a function field, G ∈ DF is a divisor. Let C be the Goppa code
of length n, dimension k, and designated relative distance δ , specified by some triplet (F,Y, G). Define a
function field F 0 = Closure(L(G)). Then there exists a Goppa code C0 defined by a triplet (F 0 ,Y 0 , G0 ), of
length n0 ≤ n, dimension k and designated relative distance δ 0 ≥ δ , such that Closure(L(G0 )) = F 0 .
Proof. We first define the new triplet (F 0 ,Y 0 , G0 ).
• We already have that F 0 = Closure(L(G)).
• Next let B = {s1 , . . . , sk } be a basis for L(G). Define,
G00 = ∑ max {−vP (si )} · P0 .
0
i
P0 ∈PF 0
We would like to exchange G00 with an equivalent divisor that has no support over places of degree
1. By the Weak Approximation Theorem [8, Thm I.3.1] there exists z ∈ F/K such that for every
place P of degree 1, vP (z) = −vP (G) and we let
G0 = G00 + (z) .
• Define a set Y 0 ⊂ PF 0 by
Y 0 = P0 ∈ PF 0 : ∃P ∈ Y such that P | P0 .
Observe that since Y consists only of places of degree 1 this is also true for Y 0 (see [8, Proposition
III.1.6]).
Consider the Goppa code C0 defined by the triplet (F 0 ,Y 0 , G0 ). Notice that Y 0 does not intersect G0
because Y 0 contains only degree 1 places and G0 has no support over degree 1 places. We will prove:
• The dimension of C0 is the same as C, i. e., dim(L0F (G0 )) = k.
• The length of C0 is at most the length of C, i. e., n0 = |Y 0 | ≤ |Y | = n.
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 267
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
• The designated relative distance of C0 is at least as good as in C, i. e.,
deg(G0 )
δ0 = 1− ≥δ.
|Y 0 |
For the proof we will show:
Claim 4.6.
G ≥ ConF/F 0 (G00 ) .
With that we can prove the three assertions above about C0 :
Dimension: Since LF 0 (G00 ) ⊆ LF (ConF/F 0 (G00 )), it follows that
dim(LF 0 (G00 )) ≤ dim(LF (ConF/F 0 (G00 ))) .
Thus, by Claim 4.6,
dim(LF (G)) ≥ dim(LF (ConF/F 0 (G00 ))) ≥ dim(LF 0 (G00 )) ≥ |B| = dim(LF (G)) ,
and therefore
dim(LF 0 (G00 )) = dim(LF (G)) = k .
The claim follows since dim(LF 0 (G0 )) = dim(LF 0 (G00 )) by [8, Lemma I.4.6].
Length: |Y | ≥ |Y 0 |, since every place of Y lies over exactly one place of Y 0 , see [8, Proposition III.1.7].
Designated distance: By Claim 4.6, deg(G) ≥ deg(ConF/F 0 (G00 )). By [8, Cor III.1.13],
deg(ConF/F 0 (G00 )) = [F : F 0 ] · deg(G00 ) .
Since deg(G00 ) = deg(G0 ) it follows that
deg(G) ≥ [F : F 0 ] · deg(G0 ) .
Also, since every place P0 can split to at most [F : F 0 ] places in F/K we have
|Y | ≤ |Y 0 | · [F : F 0 ] .
Altogether,
deg(G0 ) deg(G) deg(G)
δ0 = 1− 0
≥ 1− 0 0
≥ 1− =δ.
|Y | [F : F ] · |Y | |Y |
We are left with proving Claim 4.6.
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 268
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
Proof of Claim 4.6. By definition, B ⊆ L(G00 ), and therefore
F 0 = Closure(L(G)) = Closure(B) ⊆ Closure(L(G00 )) ,
and Closure(L(G00 )) = F 0 .
Also, for any P|P0 (where P0 ∈ PF 0 and P ∈ PF ) and for any i,
e(P|P0 ) · vP0 (si ) = vP (si ) ≥ −vP (G) ,
where the last inequality is simply because si ∈ L(G). Therefore
00 vP (si ) vP (G)
vP0 (G ) = max {−vP0 (si )} = max − ≤ ,
e(P|P0 ) e(P|P0 )
and the claim follows from the definition of the conorm.
4.2 The bound
We are now ready to prove Theorem 4.1.
Proof of Theorem 4.1. Assume a code is obtained by concatenating the AG code specified by the triplet
(F/Fq ,Y, G) with the Hadamard code. Let ` = dim(G) and d = deg(G). The AG code C(Y ; G) is a
[|Y |, `]q code, with designated distance |Y | − d. The concatenated code is therefore a
[n = |Y | · q, k = ` log(q)]2
code which is ε-balanced for
d
ε= .
|Y |
By Lemma 4.5 we can assume without loss of generality that Closure(L(G)) = F.
There are two extreme cases that we handle separately:
Large base field: If the base field size q is too large the theorem is trivially true. Namely, If q > εk3 we
are done because n ≥ q > k/ε 3 . We can therefore assume without loss of generality that
k
q ≤
ε3
and
k
log(q) = O log . (4.1)
ε
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 269
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
Few evaluation points: If the number of evaluation points is about the field size, we are essentially in
the Reed-Solomon case and we are done. Specifically, if |Y | ≤ 4q then
!
2 d2 `2 k2 k2
4n = |Y | · 4q ≥ |Y | = 2 ≥ 2 = 2 2 =Ω ,
ε ε ε log (q) ε 2 log2 ( εk )
and we are done. We can therefore assume without loss of generality that
|Y | > 4q .
√ √
This also implies that q < g since by Theorem 3.6, |Y | ≤ N(F) ≤ q + 1 + 2g q. We can therefore
conclude (again, by Theorem 3.6) that
√
N(F) ≤ 4g q . (4.2)
√
Let m = d div ` ≥ 1. By Theorem 4.4, g ≤ 2m2 `, and by equation (4.2), N(F) ≤ 8m2 ` q. Thus,
N(F) · |Y | · q N(F) · |Y | · q
n = |Y | · q = ≥ √ .
N(F) 8m2 ` q
Substituting m ≤ d/` and d = ε|Y | we see that
√
N(F) · q · `
n ≥ .
8ε 2 |Y |
Substituting ` = k/log(q) and using N(F) > |Y |,
√ √ !
q·k q·k
n ≥ 2
= Ω ,
8ε log(q) ε 2 log( εk )
where the last equality follows from equation (4.1). To finish the argument notice that by Lemma 4.2,
N(F) ≤ d(q + 1). This implies
d 1
= |Y | ≤ d(q + 1) and ε ≥ ,
ε q+1
hence, !
k
n=Ω .
ε 2.5 log( εk )
4.3 An open problem
Can one strengthen the above lower bound to match the parameters given in Section 3? More specifically
we ask whether it is possible to get a concatenated code with n = Õ(k/ε 2.5 ), where the Õ notation is used
to hide poly-logarithmic factors in q (or equivalently in k and ε). We know the following:
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 270
C ONSTRUCTING S MALL -B IAS S ETS FROM A LGEBRAIC -G EOMETRIC C ODES
• n = Õ(k2 /ε 2 ) implies N(F) = Ω̃(qm2 ). (We already saw that in the proof of Theorem 4.1.)
• A similar calculation shows n = Õ k/ε 2.5 implies N(F) = Ω̃(q2/3 m5/3 `).
We also know two upper bounds on N(F), namely:
• N(F) = Õ(qm`) (follows from N(F) ≤ d(q + 1)), and,
• N(F) = Õ(q1/2 m2 `) (since we can assume N(F) ≥ 2(q + 1), as explained in the proof of Theo-
rem 4.1).
√
Solving the constraints we get m = Θ̃( q). We thus see that the approach can lead to codes with
n = Õ(k/ε 2.5 ) if and only if the following question has a positive answer:
Open Problem 4.7. Given a prime power q and an integer d = Õ(q) is there an algebraic function field
√
F/Fq with Ω̃(q2 ) places of degree one, and a divisor G such that deg(G) = d and dim(G) ≥ Õ(d/ q).
One might suspect such a high dimension, low-degree divisor does not exist. However, Theorem 4.4
and Lemma 4.2 are not strong enough to disprove it. We remark that the lower bound could be improved,
if Lemma 4.2 could be strengthened to use the high-dimension of G, as suggested in Remark 4.3.
References
[1] N OGA A LON , J EHOSHUA B RUCK , J OSEPH NAOR , M ONI NAOR , AND RON M. ROTH:
Construction of asymptotically good low-rate error-correcting codes through pseudo-random
graphs. IEEE Trans. Inform. Theory, 38(2):509–516, 1992. Preliminary version in ISIT’91.
[doi:10.1109/18.119713] 254
[2] N OGA A LON , O DED G OLDREICH , J OHAN H ÅSTAD , AND R ENÉ P ERALTA: Simple constructions
of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304,
1992. Preliminary version in FOCS’90. [doi:10.1002/rsa.3240030308] 254, 262
[3] AVRAHAM B EN -A ROYA AND A MNON TA -S HMA: Constructing small-bias sets from algebraic-
geometric codes. In Proc. 50th FOCS, pp. 191–197. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/FOCS.2009.44] 253, 256
[4] W ILLIAM F ULTON: Algebraic Curves: An Introduction to Algebraic Geometry. Third edition, 2008.
Author’s version. 258
[5] A RNALDO G ARCIA AND H ENNING S TICHTENOTH, editors. Topics in Geometry, Coding Theory
and Cryptography. Volume 6. Springer, 2007. Available from Springer. 262
[6] S ERGE L ANG: Algebra. Springer, revised third edition, 2002. Available from Springer. 258
[7] J OSEPH NAOR AND M ONI NAOR: Small-bias probability spaces: Efficient constructions and
applications. SIAM J. Comput., 22(4):838–856, 1993. Preliminary version in STOC’90.
[doi:10.1137/0222053] 254
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 271
AVRAHAM B EN -A ROYA AND A MNON TA -S HMA
[8] H ENNING S TICHTENOTH: Algebraic Function Fields and Codes. Springer, 1993. Available from
Springer. 256, 259, 260, 261, 262, 263, 266, 267, 268
[9] H ENNING S TICHTENOTH: Private communication, 2009. 266
[10] M ICHAEL A. T SFASMAN , S ERGE G. V L ĂDU Ţ , AND T HOMAS Z INK: Modular curves, Shimura
curves, and Goppa codes, better than Varshamov-Gilbert bound. Mathematische Nachrichten,
109(1):21–28, 1982. [doi:10.1002/mana.19821090103] 254
[11] J OSÉ F ELIPE VOLOCH: Special divisors of large dimension on curves with many points over finite
fields. Portugaliae Mathematica, 68(1):103–107, 2011. [doi:10.4171/PM/1882] 256, 266, 267
AUTHORS
Avraham Ben-Aroya
postdoctoral researcher
The Weizmann Institute of Science
Rehovot, Israel
avraham ben-aroya weizmann ac il
http://www.wisdom.weizmann.ac.il/~benaroya/
Amnon Ta-Shma
professor
Tel-Aviv University
Tel-Aviv, Israel
amnon tau ac il
http://www.cs.tau.ac.il/~amnon
ABOUT THE AUTHORS
AVRAHAM B EN -A ROYA received his Ph. D. from Tel-Aviv University. His advisors were
Oded Regev and Amnon Ta-Shma. He is currently a postdoc at the Weizmann Institute
of Science.
A MNON TA -S HMA is a theoretical computer scientist at Tel-Aviv University.
T HEORY OF C OMPUTING, Volume 9 (5), 2013, pp. 253–272 272