Algebraic Geometry Codes

Introduction: messages and information

‍

Data is usually stored and transferred as a sequence of 0’s and 1’s, where each individual element in this sequence is a bit. Let’s say you want to send the following message to your friend via Wi-Fi: “Hello!”. If we picture what happens very naively, you are sending this string of bits through the air with radio waves:

‍

“01001000 01100101 01101100 01101100 01101111 00100001”

‍

Your friend receives it, her device understands the radio signal representing that string of bits, and displays “Hello!”. But what guarantees that this radio signal arrives unaltered to your friend’s device? Couldn’t this signal interact with our atmosphere as it travels and be modified or lost? The answer is that it absolutely can, and it happens every day. If only two bits in the preceding message are flipped, you send “Hell!” — a much more sinister message.

‍

Now, say you stored all your most precious information in a hard drive. Unfortunately, the area where you live has been hit by a shower of cosmic radiation, probably after a violent solar flare. The resulting cosmic particles went through the transistors storing your data, flipping an unknown number of bits. The information you keep on your hard drive is now slightly different and might not even be readable anymore!

‍

These problems are real. They come up all the time and can have serious consequences. Though cosmic ray bit flips are extremely rare (if any exist), think about a scratched DVD or corrupted USB drive. There are naive ways to deal with this problem: one that comes to mind is to send or store the same information multiple times and use the majority of received/stored information to decide what the correct data should be. It is clear that such a method quickly becomes inefficient. One way to efficiently deal with this problem is by using a type of encoding called linear code. When correctly designed, it allows users to encode information efficiently and detect and correct errors in received/stored data.

‍

In this blog post, starting from the ubiquitous example of Reed-Solomon encoding, we explore another way of constructing such codes using the algebraic theory of curves over a finite field. These are particularly useful when the amount of data needing to be encoded becomes larger and larger. In fact, they are the best codes we know in these cases. We will focus on their construction rather than the decoding methods. We’ll also explore asymptotically good sequences of Algebraic Geometry (AG) codes at a very high level.

‍

‍

‍

What is a good (linear) code?

‍

Notation. For q =pⁿ an integer power of a prime number p, we denote by 𝔽q the unique (up to isomorphism) field with q elements. We can describe it as the splitting field of the polynomial X^q-X over 𝔽ₚ, where 𝔽ₚ is the set of integers {0, …, p — 1} with addition and multiplication modulo p. Alternatively, one can see 𝔽q as the quotient 𝔽ₚ[X]/(ƒ(X)) where ƒ is a monic irreducible polynomial over 𝔽ₚ with degree n.

‍

A linear code C of length n and dimension k ≤ n is an 𝔽q-sub-vector space of 𝔽qⁿ of dimension k. Elements of C are called codewords. Many times, we realize such subspaces as the image of an 𝔽q-linear map V→𝔽qⁿ, where V is an 𝔽q-vector space of dimension k. The (minimal) distance d of the linear code is the minimal Hamming distance between nonzero codewords, or equivalently the minimum number of nonzero coordinates of any nonzero codeword. We say that C is an [n,k,d]-code (sometimes we emphasize [n,k,d]q).

‍

‍

Error detection, error correction

‍

The distance of the code is intimately related to its ability to detect and correct errors in received messages. Intuitively, the larger this distance, the smaller the set of possible codewords close to the received message. We try to picture this in Figure 1 below.

‍

‍

The red points represent codewords; some elements in the ambient linear space are shown in blue. Our code has a minimal distance of 4 (it would be the minimum number of horizontal or vertical steps one has to take to go from one point to another and not the Hamming distance, but we use it to understand what is going on). On the left, there has only been one error while transmitting the message, so the received message is the blue point one step to the right of our bottom left red point. Someone receiving such a message can immediately deduce that the original message is most likely the closest codeword to this point, which is our original red point. On the right, there have been two errors while transmitting the message, and the received word is the blue point in the middle of the figure. Here, someone receiving this message can deduce that there has been an error, but it cannot determine whether the original message was the bottom left or the upper right red point, as both are at distance 2 from the received word. Therefore this code can correct at most 1 error (remark that 1=⌊(4–1)/2⌋, in fact, this is the relationship between the minimal distance and the maximum number of errors one can correct “uniquely”), as shown by the green circle on the left, representing the “Hamming ball” around our codeword.

‍

This simple example shows that we should aim to have the maximum possible minimal distance. Unfortunately, there is a simple result constraining the possible values of d:

‍

Lemma (Singleton bound). If C is an [n,k,d]q linear code, then d≤ n-k+1

‍

proof. Let C be an arbitrary linear code over 𝔽q with minimal distance d. All codewords are distinct. If we delete the first d — 1 coordinates of every codeword, they are still pairwise distinct because every pair differs in at least d coordinates. The number of coordinates of the new codewords is n — d+1, but there is the same number of distinct codewords. It follows that |C|≤ qⁿ⁻ᵈ⁺¹. If C is linear of dimension k, we have |C|=qᵏ.

‍

It follows that the largest possible value of d is n — k+1 when we attain the singleton bound. Linear codes that attain this bound are called Maximum Distance Separable (MDS).

‍

‍

Decoding received messages

‍

At the same time, we need to encode messages into codewords using a relatively simple procedure. We also need an algorithm to decode received messages: this means translating back received messages m into codewords from C. Such an algorithm should take a message m and return the closest (or a list of close) codewords to m. There are inefficient ways to do this, e.g., to check all codewords. We are interested in efficient decoding algorithms, and this will usually depend on the search distance.

‍

‍

The example of Reed-Solomon (RS) encoding

‍

The Reed-Solomon encoding is one of the most important examples of linear codes. It is everywhere in modern storage and communication, which is all the more remarkable because of its elegant and simple nature.

‍

Fix a prime power q (this quantity is called the alphabet size), n distinct elements of 𝔽q, say y₁, …, yₙ (the integer n is called the blocklength) and suppose you want to send a message that consists of k < n≤ q elements (k is the dimension) x₁, …, xₖ in 𝔽q. We construct an extension of the message in the following way:

‍

• Consider the vector of elements (x₁, …, xₖ) to be sent as the coefficients of a degree at most k — 1 polynomial ƒ(X)=x₁+x₂X+ … + xₖXᵏ⁻¹ over 𝔽q.
• Compute the evaluations of ƒ at all yᵢ, that is compute ƒ(yᵢ) for i=1, …, n.
• Send all the computed evaluations by sending the vector (ƒ(y₁),…, ƒ(yₙ)).
  ‍

This description of RS codes does not exactly fit our definition of a linear code. To see the link, consider the space V of polynomials with coefficients in 𝔽q with degree strictly less than k. These can be described by their vector of coefficients of length k. This is an 𝔽q-sub-vector space of 𝔽qⁿ because k<n, and the fact that addition and scalar multiplication are defined component-wise. By using the obviously 𝔽q-linear evaluation map:

we see how any message encoded by using the previous description corresponds to exactly one element in the image of this map.

‍

If your message stays intact during communication or storage, then it is immediate to obtain your original message back by using polynomial interpolation. If not, RS codes possess many properties that allow for efficient decoding. For example, Reed-Solomon codes are MDS. Furthermore, the Berlekamp-Welch algorithm is an example of a decoding algorithm that is much more efficient than exhaustive search and can correct up to ⌊(d — 1)/2⌋ errors.

‍

‍

Algebraic geometry codes

‍

It is no wonder that RS codes satisfy all these nice properties; they are examples of a more general family of codes called Algebraic Geometry codes (over curves). We will explain later that they can be seen as evaluation codes over the projective line ℙ¹. Algebraic Geometry codes satisfy many desirable properties, including the fact that:

‍

• They are explicitly constructible.
• They are efficiently decodable.
• They have good bounds on their parameters, though they are not MDS when the genus of the curve is greater than 0, they remain close to the singleton bound.

‍

‍

Introduction to algebraic geometry (AG) codes (over curves)

‍

Let us consider a curve 𝔛 over 𝔽q, we can think of it as being the projectivization (and possibly desingularization) of the affine curve
𝔛ₐ:={ (x, y)∈ 𝔽q² ∣ p(x, y)=0 }, where p∈𝔽q[X, Y] is absolutely irreducible (irreducible over the algebraic closure of 𝔽q).

‍

Technical details about homogenization, projectivization, and singularities. Let p∈𝔽q[X,Y], consider F∈𝔽q[X₀, X₁, X₂] defined as:

We call F the homogenization of p with respect to X₂. This polynomial is homogeneous, meaning that for any λ∈𝔽q, we have:

The projectivization of the affine curve 𝔛ₐ can therefore be defined as:

Here ℙ²(𝔽q) is the projective plane over 𝔽q, which we define as the quotient of the space 𝔽q³∖{(0,0,0)} by the equivalence relation (z₀, z₁, z₂) ∼ (λz₀, λz₁, λz₂), ∀ λ∈𝔽q*. We will encounter the projective line ℙ¹(𝔽q) later on and give a bit more intuition into how to think about it.

‍

Not crucial for understanding the post: The resolution of singularities part is somewhat more challenging to explain. Recall that a singularity of the projectivization is given by a point [x₀:x₁:x₂] in the projectivization such that ∂F/∂Xᵢ(x₀, x₁, x₂)=0 for i=0, 1, 2. We can assume that this does not happen, i.e., that the projectivization is nonsingular, without harming our argument.

‍

‍

Preliminaries

‍

Consider a “closed point” P of 𝔛, which we can think about as a triple [x₀: x₁: x₂]∈ℙ²(𝔽q) such that F(x₀,x₁,x₂)=0, where F is the homogenization of p. We have to be careful here because 𝔽q is not algebraically closed, but this gives a good feeling for what a point might be. For each such point P, there exists a corresponding valuation (see below), or place, νₚ: K(𝔛)→ ℤ∪{∞}, where K(𝔛)=Frac(𝔽q[X,Y]/(p(X,Y))) is the function field of 𝔛 (here for an integral ring R we denote by Frac(R) its field of fractions). We recall that a valuation is such that:

In analogy with the theory of curves over ℂ and their meromorphic functions, we can think of νₚ(ƒ) as being the order of the “rational function” ƒ at P: if νₚ(ƒ)>0 we can think of ƒ as having a zero of order νₚ(ƒ) at P, if νₚ(ƒ)<0 we can think of ƒ as having a pole of order — νₚ(ƒ) at P.

‍

For each place νₚ, there is an associated local ring 𝒪ₚ={ƒ ∈K(𝔛)*|νₚ(ƒ)≥0}⋃{0} with unique maximal ideal 𝔪ₚ={ƒ∈K(𝔛)*|νₚ(ƒ)>0}⋃{0} (a “rational function” ƒ in 𝒪ₚ is invertible “at P” if and only if νₚ(ƒ)=0).

The quotient 𝒪ₚ/𝔪ₚ:=kₚ, called the residue field at P, is a vector space over 𝔽q, and we define:

The idea now is to consider functions with prescribed zeros and poles because this will allow us to build linear maps from finite-dimensional vector spaces to 𝔽qⁿ, whose images are precisely what we defined as linear codes. Furthermore, it can help us specify the type of functions we are looking for (as we will see, polynomials have a characteristic structure of zeros and poles over ℙ¹). We do this by associating formal sums to rational functions which encode their multiplicities. We set:

It can be proven that for any ƒ∈ K(𝔛)*, there are only finitely many points where ƒ has zeros or poles, so the previous sum makes sense. Sums of the form (1) are called principal divisors. We can also show that zeros and poles of rational functions compensate exactly when taken with the correct multiplicity, that is, for all ƒ∈ K(𝔛)*:

The sum is meaningful because all but finitely many valuations are zero. There are also non-principal divisors, which arise when we allow arbitrary finite linear combinations of points D=∑ₚ cₚ ⋅ P, where all cₚ∈ℤ (the degree of D is defined in the same way). By using the properties of valuations above, it is easy to see that div(ƒ ⋅ g)=div(ƒ)+div(g), from which it follows that principal divisors form an additive subgroup of the additive group of divisors.

‍

We can impose conditions on the order of zeros and poles of ƒ by taking a divisor D=∑ₚ cₚ ⋅ P and asking that all coefficients of div(ƒ) + D = ∑ₚ(νₚ(ƒ) + cₚ)⋅ P are positive. We denote this div(ƒ)+D ≥ 0, or div(ƒ) ≥ — D. Taking degrees is compatible with this partial ordering, meaning that if E ≥ D, then deg(E) ≥ deg(D).

‍

For an arbitrary divisor D, its associated Riemann-Roch space is defined to be the following sub-vector space of K(𝔛):

Surprisingly (because K(𝔛) is a vector space of infinite dimension over 𝔽q), L(D) is finite-dimensional for all divisors D, with dimension ℓ(D). One of the greatest results of the theory of curves is the following:

‍

Theorem (Riemann-Roch). There exists a divisor K called the canonical divisor such that for all divisors D, the following holds:

‍The quantity ℓ(K) is called the genus of the curve 𝔛, denoted g. We have deg(K)=2g — 2. In particular, since ℓ(K — D) is the dimension of a vector space, we find:

‍

Remark first that since deg(div(ƒ))=0, if the degree of D is strictly negative, there are no rational functions such that div(ƒ) ≥ — D, and so ℓ(D)=0. From this, we obtain the following:

‍

Corollary to Riemann-Roch. If deg(D)>2g — 2, then ℓ(D)=deg(D)+1 — g.

‍

‍

Evaluation codes

‍

We have now obtained a roadmap for building (hopefully good) linear codes: we use linear maps from the finite-dimensional Riemann-Roch spaces to obtain linear codes and apply Riemann-Roch type arguments to obtain bounds on the length, dimension, and distance of the resulting codes. This is exactly what we do.

‍

Let 𝔛 be a curve over 𝔽q, let G be an arbitrary divisor, and let 𝒫={P₁, …, Pₙ} a set of n 𝔽q-rational points (with coordinates in 𝔽q, alternatively such that kₚ=𝔽q) such that for all i, the coefficient associated to Pᵢ in the sum defining the divisor G is 0. Associate a very simple divisor to 𝒫 as follows:

For any place νₚ there is a natural way to “evaluate” a rational function ƒ∈ 𝒪ₚ “at P”: just send it to its image ƒₚ in the residue field kₚ=𝒪ₚ/𝔪ₚ by the natural quotient map. We define ƒₚ:=ƒ(P). If P is 𝔽q-rational, this means in particular that kₚ=𝔽q, and therefore we find that ƒ(P)∈𝔽q. Furthermore, in this case, the evaluation map is 𝔽q-linear, that is:

This allows us to make the following definition.

‍

Definition (Evaluation code). The evaluation code C(𝔛,𝒫, G) is defined as the image of the linear map:

For this definition to make sense, in view of our previous observations, we need ƒ∈ 𝒪ₚ for all ƒ∈ L(G) and P=Pᵢ. This is indeed the case because the coefficient associated with each Pᵢ is 0 in the sum defining the divisor G, therefore any function ƒ verifying ƒ ≥ — G is such that vₚ(ƒ) ≥ 0 for all P=Pᵢ.

‍

We can now obtain the following basic estimates:

‍

Theorem. The evaluation code C(𝔛,𝒫, G) is a linear code of length n=deg(Dₚ) (all degrees deg(Pᵢ) are 1 because they are 𝔽q-rational points) and dimension:

In particular if deg(G)<n, then:

And if 2g — 2< deg(G)< n, then:

Its minimum distance d satisfies:

proof. The first equality follows from Rank-Nullity, as the map is linear we find:

Now the dimension of the image of ev is k by definition. If ƒ∈ L(G) is such that ev(ƒ)=0, then this means that νₚ(ƒ) > 0 for all P=Pᵢ. Since in the sum defining the divisor G the Pᵢ’s do not appear, we find that:

or in other words ƒ∈ L(G — Dₚ). The converse follows from the same argument. This shows that ker(ev)=L(G — Dₚ), and therefore dim(ker(ev))=ℓ(G — Dₚ). The inequalities involving k are a direct application of Riemann-Roch and its Corollary.

‍

For the minimal distance, suppose ev(ƒ) is a nonzero vector in the image. Let w be its Hamming weight (the number of nonzero coordinates). Then ev(ƒ) has n — w coordinates equal to 0, w.l.o.g. assume these are the first n — w. This means that ƒ(P)=0 for P=Pᵢ and i=1, …, n — w, and in turn this means that νₚ(ƒ)>0 for P=Pᵢ and i=1, …, n — w. As before, we find:

Taking degrees and using equation (2) from above, together with the fact that the Pᵢ are 𝔽q-rational we obtain:

Since ev(ƒ) was an arbitrary nonzero vector in the image, the same inequality holds for the minimal distance in place of w.

‍

Combining the above inequalities, it follows that if deg(G) <n, then:

‍

That is, the singleton defect of C(𝔛, 𝒫, G) is at most the genus of 𝔛. In particular, it follows that if the curve has genus 0, then d=n — k+1 because of the singleton bound. That is, the code C(𝔛, 𝒫, G) is MDS.

‍

‍

Codes from ℙ¹

‍

The projective line is the prototypical example of a genus 0 curve. As a set, we think of it as being the quotient:

‍

Elements of ℙ¹ are therefore represented by equivalence classes of points (z₁, z₂)∈ 𝔽q²∖{(0,0)} which we denote [z₁:z₂]. Essentially ℙ¹ can be thought of as the line containing the elements of 𝔽q represented by classes [z:1] for z∈𝔽q, together with a point “at infinity” ∞ = [1:0]. As a curve, its function field can be described as the field of rational functions in one formal variable 𝔽q(X) (using the equivalence between function fields and nonsingular projective curves).

‍

Recall the definition of the Reed-Solomon codes:

‍

Definition (Reed-Solomon codes). Let x =(x₁, …, xₙ)∈𝔽qⁿ be a tuple of distinct elements. The Reed-Solomon code RSₖ(x) of dimension k <n is the linear evaluation code defined as follows:

‍

It turns out that the nice properties of RS codes can be obtained from the fact that they are a particular type of AG code from the projective line:

‍

Proposition. Let x =(x₁, …, xₙ)∈𝔽qⁿ be a tuple of distinct elements.
Set 𝒫={ [x₁ :1], …, [xₙ :1] } and ∞=[1:0].

‍
Then the evaluation code C(ℙ¹, 𝒫, (k — 1)∞) is nothing but RSₖ(x).
In particular, RSₖ(x) is MDS.

‍

proof. The set L((k — 1)∞) consists of rational functions in one variable which have a pole of order strictly less than k at “infinity”. These are precisely the polynomials of degree < k. This can be shown by using the fact that the valuation corresponding to ∞ is the natural extension to the field of rational functions in one variable of the valuation associated with the prime ideal (1/X) in 𝔽q[1/X]. Since g(ℙ¹)=0, equation (3) shows that RSₖ(x) is MDS.

‍

There exists an extension of RS codes, called generalized RS codes, defined in the following way:

‍

Definition (Generalized RS codes). Let x =(x₁, …, xₙ), y=(y₁, …, yₙ)∈𝔽qⁿ be two tuples of distinct elements. The Generalized Reed-Solomon code GRSₖ(x) of dimension k <n is the linear evaluation code defined as follows:

It is possible to obtain the following result (for proof, we refer to [1], p.15):

‍

Theorem. Every Generalized Reed-Solomon code is an AG code from the projective line whose evaluation points avoid ∞, and conversely.

‍

‍

‍

Beyond the alphabet size

‍

We have now constructed linear codes by using curves over finite fields. As a particular example, we have obtained RS and even GRS codes. But if RS codes are so efficient and elegant, why do we need other codes? The answer lies in the integer n, which we call the blocklength of the RS code. Remark that in the definition, we asked for the n evaluation points to be distinct. Otherwise, we would have redundant information in our encoding. This constrains n to be, at most q, the alphabet size. We find that RS codes can encode messages that have a length at most q — 1.

‍

If we need to send longer messages, we need to work over larger prime numbers or higher degree extensions. This makes decoding more expensive and implies having to implement many different finite fields (in our computers) depending on the lengths of the messages we want to send or store. One natural question, therefore, is the following: for a fixed alphabet size q, is it possible to obtain linear codes that can encode arbitrarily large amounts of information while still having error correction capabilities?

‍

This question turned out to be very challenging. It was first understood that those were possible, but an explicit construction was lacking. Not only did AG codes provide the first explicit examples of such codes, but they are currently the best that we know of, too.

‍

‍

Asymptotically good codes

‍

In this section, we omit proofs.

‍

For a [n,k,d]q code C define the information rate R=k/n and the relative minimal distance δ=d/n. An asymptotically good sequence of codes is a sequence of codes C₁, C₂,… with lengths n₁, n₂, …, dimensions k₁, k₂, …and minimal distances d₁, d₂, … respectively, such that:

I.e., a sequence of codes with strictly positive asymptotic information rate/relative minimal distance. This condition means that as nᵢ grows arbitrarily large, the amount of information kᵢ and the minimal distance dᵢ do not become negligible with respect to nᵢ. This shows that we can encode an arbitrarily large amount of information while still having non-trivial error-correcting capabilities (because the minimal distance is not negligible w.r.t. nᵢ).

‍

A non-constructive argument given independently by Gilbert and later Varshamov (using different techniques) shows that an asymptotically good sequence of codes exists over any finite field 𝔽q with 0 <δ <1–1/q and R=1-Hq(δ) where:

is the q-ary entropy function.

‍

For a long time, it was an open question to determine an explicit/computable construction of asymptotically good codes. Algebraic geometry codes provide a possible answer. Coming back to equation (3), it can be seen as a tradeoff: as n increases, the minimal distance increases, but as the genus g increases, the distance decreases. Since n is ultimately related to the number of distinct 𝔽q-rational points, the aim would be to find curves with low genus and a large number of 𝔽q-rational points. Rewrite (3) as:

Letting n → ∞ in (4) motivates the following definition:

‍

Definition (Ihara constant). The Ihara constant of 𝔽q is defined as follows:

Where 𝔛 runs through all curves over 𝔽q and n(𝔛) denotes the number of 𝔽q-rational points of 𝔛.

‍

It is then possible to obtain the following result:

‍

Theorem (Asymptotic AG codes). Assume A(q)>1. For any R,δ >0 satisfying R+δ=1 — 1/A(q), there exists asymptotically good codes with asymptotic rate and minimal distance at least R and δ respectively.

‍

For the result to be meaningful, we need estimates on A(q). Hasse-Weil immediately implies that A(q)≤ 2 √q. Several improvements culminated in the following upper bound:

‍

Theorem (Drinfeld-Vlăduţ). For any q, A(q) ≤ √q — 1. Using Shimura curves, Ihara showed that when q is a square, then A(q) ≥ √q — 1, and so in fact, A(q)=√q — 1. Ihara’s lower bound, combined with the Theorem about asymptotic AG codes, shows that there exist asymptotically good codes with

This is known as the Tsfasman-Vlăduţ-Zink bound, and for q ≥ 49 it gives better asymptotic codes than the Gilbert-Varshamov bound!

‍

And for general q? For general q, Serre showed in [9] that A(q) ≥ c log(q). Later, the constant was improved, and we now know that c can be taken to be 1/(96 log(2)). When q is prime, this is often the best-known estimate.

‍

‍

‍

Related work

‍

Theoretically, we can outline some of the major lines of work in the development of AG codes.

‍

One has focused on improving the minimal distance bound in (3). As explained in [1], these can broadly be categorized based on whether they rely on the use of “base points” of divisors related to G or on the use of a filtration:

with some clever estimates on the number of points in C(𝔛, 𝒫, Gᵢ)∖C(𝔛, 𝒫, Gᵢ₊₁). There are also some improvements that rely on the particular embedding of curves in projective space.

‍

Decoding AG codes has also been the subject of extensive research. The first algorithm was proposed by Justesen et al. in [5], and the generalization to arbitrary AG codes has been given by Skorobogatov and Vlăduţ in [6]. These algorithms allow correcting errors up to half of the minimal distance minus some term depending on the genus. A productive direction has been to correct this defect. The key insight of Sudan in [7] is that at the cost of returning a list of possible close codewords, we can decode errors that exceed the usual error-correction bound. Guruswami and Sudan then gave an improved algorithm correcting errors up to the so-called Johnson bound [8].

‍

We only introduced AG codes over curves, but we can use some more theory to define codes over higher dimensional varieties. For a review, see [4].

‍

AG codes also have been gaining some traction because of their potential in proof systems, where they would replace polynomial encodings and potentially enable more efficient protocols.

‍

‍

‍

Conclusion

‍

So why aren’t AG codes everywhere yet? The answer, for now, seems to be that their definition is quite abstract, and, to the best of our knowledge, an efficient computer implementation of all the necessary pieces has not been completed. It is our opinion, however, that this is only a matter of time and that, eventually, general AG codes will be widespread and universally adopted for communication, storage, and maybe even proof systems.