Toric Codes

John B. Little

little@mathcs.holycross.edu

Department of Mathematics and Computer

Science, College of the Holy Cross Joint work with Hal Schenck (U. Illinois),

Ryan Schwarz (U. Connecticut), Alex Simao,

HC ’08.

AMS Special Session on Codes over Rings

and Modules, Kalamazoo October 17, 2008

Outline

1. Toric code basics – Codes from polytopes

2. Tools from algebraic geometry – toric varieties; an example

3. Higher dimensional polytopes and Vandermonde determinants – estimating d of a toric code.

[1] J. Little and H. Schenck Toric Codes and Minkowski Sums, SIAM Journal of Discrete Mathematics 20 (2006), 999–1014.

[2] J. Little and R. Schwarz, Toric Codes and Vandermonde Matrices, AAECC 18 (2007), 349–367.

§1. Toric Code Basics

Introduced by J. Hansen ∼ 1997. Elementary description:

• Let P be an integral convex polytope in ℝ^{m}, m ≥ 1.

• Points β in the finite set P ∩ℤ^{m} correspond to monomials x^{β} (multi-index notation)

• Let L_{P} = Span {x^{β} : β ∈ P ∩ ℤ^{m}}.

• Define

ev : L_{P} → 𝔽_{q}^{(q−1)^{m}}
f ↦ (f(γ) : γ ∈ (𝔽_{q}^{∗})^{m})

Image is the toric code C_{P} (𝔽_{q}).

• Example: RS(k, q) from P = [0, k − 1] ⊂ ℝ since L_{P} = Span {1, x, …, x^{k−1}}.

Why Are They Interesting?

• Have many properties parallel to RS codes, e.g. they are “m-dimensional cyclic” codes (set of codewords is closed under a large automorphism group).

• Computer searches by D. Joyner (USNA) showed that some very good m = 2 toric codes exist (better than any previously known codes in standard databases). A number of other isolated very good examples found too.

• (debatable, maybe!) Can apply lots of nice algebraic geometry to study their properties (toric varieties, intersection theory, line bundles, Riemann-Roch theorems)

When Are Toric Codes Equivalent?

Usually take P ⊂ [0, q − 2]^{m} ≃ (ℤ_{q−1})^{m}.

Theorem 1 If S = P ∩ ℤ^{m} and S′ = T (S) for some T = AGL(m, ℤ_{q−1}), the resulting evaluation code from S′ is monomially equivalent to C_{P} (𝔽_{q}).

Note: S′ may not be P′ ∩ ℤ^{m} for a convex polytope P′.

(Monomial equivalence: There is an n × n permutation matrix Π and an n × n invertible diagonal matrix Q such that G′ = GQΠ.)

Small Needles In Huge Haystacks!

For m = 3, q = 5, for instance, the generating function for the number of AGL(3, ℤ_{4})-orbits on subsets of ℤ_{4}^{3} of size k:

1 + x + 2x^{2} + 4x^{3} + 16x^{4} + 37x^{5} +
147x^{6} + 498x^{7} + 2128x^{8} + 8790x^{9} +
39055x^{10} + 165885x^{11} +
678826x^{12} + 2584627x^{13} + ⋯

The “middle term” here is:

333347580600x^{32}

“Most” of these subsets give quite uninteresting codes. But for instance, one of the 2128 orbits of size k = 8 consists of codes with d = 42 (better than best previously known d = 41 according to Grassl’s table). Clearly need some other tools(!)

§2. Tools from algebraic geometry

Toric codes and toric varieties

• A polytope P defines a normal fan Σ_{P}, hence an abstract toric variety X = X_{Σ_{P}} .

• Also get a line bundle L = L_{P} specified by P.

• Subpolytopes correspond to subspaces of H^{0}(X, L).

• In case m = 2, main results of L. and Schenck [1] show that for q sufficiently large d(C_{P} (𝔽_{q})) can be bounded above and below by looking at subpolytopes P′ ⊆ P that decompose as Minkowski sums

The Lower Bound

Theorem 2 Let ℓ be the largest positive integer such that there is some P′ ⊆ P that decomposes as a Minkowski sum P′ = P_{1}+P_{2}+⋯+P_{ℓ} with nontrivial P_{i}. For all q >> 0, there is some P′ ⊆ P of this form such that

d(C_{P} (𝔽_{q})) ≥ ℓ ; ∑ ; i=1 d(C_{P_{i}}(𝔽_{q})) − (ℓ − 1)(q − 1)^{2}.

Intuition For Proof

Minkowski-reducible subpolygons ↔ reducible sections (Newton polygon of product of polynomials is a Minkowski sum).

Hasse-Weil upper and lower bounds for a curve Y:

q + 1 − 2g(Y)√q ≤ |Y (𝔽_{q})| ≤ q + 1 + 2g(Y)√q

⇒ when q > (a crude but explicit lower bound), reducible curves with ℓ components must have more 𝔽_{q}-rational points than those with m < ℓ components.

Bounds have been improved by Soprounov and Soprounova.

An Interesting Polygon

Consider P as below

[figure]

P ⊂ [0, q − 2]^{2} for all q ≥ 5.

• P contains P′ = conv {(1, 0), (2, 0), (1, 2), (2, 2)} (= P_{1} + P_{2} + P_{3}, P_{i} line segments) and P′′ = conv {(1, 0), (1, 1), (3, 2), (3, 3)} (similar).

• No other decomposable Q ⊂ P with more than three Minkowski summands

• ⇒ for q > #(P) + 3 = 12,

d(C_{P} (𝔽_{q})) ≥ (q − 1)^{2} − 3(q − 1).

Reducible Curves

From P′ we obtain curves x(x−a)(y−b)(y−c) = 0. If a, b, c ∈ 𝔽_{q}^{∗} and b ≠ c, then s has 3(q−1)−2 zeroes in (𝔽_{q}^{∗})^{2}. Hence,

d(C_{P} (𝔽_{q})) ≤ (q − 1)^{2} − 3(q − 1) + 2

and

d(C_{P} (𝔽_{q})) ≥ (q − 1)^{2} − 3(q − 1), q >> 0.

Computations using Magma show that

d(C_{P} (𝔽_{5})) = 6^{(∗)} vs. 4^{2} − 3 · 4 + 2 = 6
d(C_{P} (𝔽_{7})) = 20 vs. 6^{2} − 3 · 6 + 2 = 20
d(C_{P} (𝔽_{8})) = 28 vs. 7^{2} − 3 · 7 + 2 = 30
d(C_{P} (𝔽_{9})) = 42 vs. 8^{2} − 3 · 8 + 2 = 42
d(C_{P} (𝔽_{11} )) = 72 vs. 10^{2} − 3 · 10 + 2 = 72.

(^{(∗)} code over 𝔽_{5} is best known for n = 16, k = 9)

More On q = 8

Where does a codeword with 49−28 = 21 zero entries come from? Magma: exactly 49 such words. One of them comes, for instance, from the evaluation of

y + x^{3}y^{3} + x^{2} ≡ y(1 + x^{3}y^{2} + x^{2}y^{6})
≡ y(1 + x^{3}y^{2} + (x^{3}y^{2})^{3})

Here congruences are mod ⟨x^{7} − 1, y^{7} − 1⟩, the ideal of the 𝔽_{8}-rational points of the 2-dimensional torus. So 1 + x^{3}y^{2} + (x^{3}y^{2})^{3} has exactly the same zeroes in (𝔽_{8}^{∗})^{2} as y + x^{3}y^{3} + x^{2}.

Arithmetic Of 𝔽_{8} Matters

1 + u + u^{3} is one of the two irreducible polynomials of degree 3 in 𝔽_{2}[u], hence

𝔽_{8} ≅ 𝔽_{2}[u]/⟨1 + u + u^{3}⟩.

If β is a root of 1 + u + u^{3} = 0 in 𝔽_{8}, then 1 + x^{3}y^{2} + (x^{3}y^{2})^{3} =

(x^{3}y^{2} − β)(x^{3}y^{2} − β^{2})(x^{3}y^{2} − β^{4})

and there are exactly 3 · 7 = 21 points in (𝔽_{8}^{∗})^{2} where this is zero. Still a sort of reducibility that produces a section with the largest number of zeroes here, even though the reducibility only appears when we look modulo the ideal ⟨x^{7} − 1, y^{7} − 1⟩ (!).

Similar phenomena in many other cases for small q.

§3. Higher-dimensional Polytopes and Vandermonde Matrices

Some motivation:

Square submatrices of the generator matrix G for a Reed-Solomon code are usual (onevariable) Vandermonde matrices:

V = ( \begin{matrix}1 & 1 & ⋯ & 1 \\ α^{j_{1}} & α^{j_{2}} & ⋯ & α^{j_{k}} \\ ⋮ & ⋮ & ... & ⋮ \\ (α^{j_{1}})^{k−1} & (α^{j_{2}})^{k−1} & ⋯ & (α^{j_{k}})^{k−1} \end{matrix} )

(Well-known and standard observation for studying these codes – implies the rows of G are linearly independent, for instance.)

General Vandermondes

• Let P be an integral convex polytope, and suppose P ∩ ℤ^{m} = {e(i) : 1 ≤ i ≤ #(P)}.

• Let S = {p_{j} : 1 ≤ j ≤ #(P)} be any set of #(P) points in (𝔽_{q}^{∗})^{m}.

• Picking orderings, define V (P; S), the Vandermonde matrix associated to P and S, to be the #(P) × #(P) matrix

V (P; S) = (p_{j}^{e(i)} ) ,

where p_{j}^{e(i)} is the value of the monomial x^{e(i)} at the point p_{j}.

An Example

Let P = conv {(0, 0), (2, 0), (0, 2)} in ℝ^{2}, and S = {(x_{j}, y_{j})} be any set of 6 points in (𝔽_{q}^{∗})^{2}. For one particular choice of ordering of the lattice points in P, we have V (P; S) =

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & x_{6} \\ y_{1} & y_{2} & y_{3} & y_{4} & y_{5} & y_{6} \\ x_{1}^{2} & x_{2}^{2} & x_{3}^{2} & x_{4}^{2} & x_{5}^{2} & x_{6}^{2} \\ x_{1}y_{1} & x_{2}y_{2} & x_{3}y_{3} & x_{4}y_{4} & x_{5}y_{5} & x_{6}y_{6} \\ y_{1}^{2} & y_{2}^{2} & y_{3}^{2} & y_{4}^{2} & y_{5}^{2} & y_{6}^{2} \end{matrix} )

Minimum Distance Theorem

From L., Schwarz, [2]:

Theorem 3 Let P ⊂ ℝ^{m} be an integral convex polytope. Let d be a positive integer and assume that in every set T ⊂ (𝔽_{q}^{∗})^{m} with |T | = (q − 1)^{m} − (d − 1) there exists some S ⊂ T with |S| = #(P) such that det V (P; S) ≠ 0. Then the minimum distance satisfies d(C_{P}) ≥ d.

Proof: For all S, det V (P; S) ≠ 0 ⇒ the homogeneous linear system obtained the generator matrix, in columns corresponding to S, has only the trivial solution so there are no nonzero codewords with (q − 1)^{m} − (d − 1) zero entries. Hence every nonzero codeword has ≥ d nonzero entries.

Codes From Simplices, etc.

• Consider simplices of form

P_{ℓ} = Conv (ℓe_{i} : i = 1, …, m).

• Via a recursive determinant identity,

det V (P_{ℓ}; S) ≠ 0

for “simplicial configurations” of points S (essentially: sets of points that look combinatorially like the lattice points in a simplex of the same dimension, same ℓ)

• Such “simplicial configurations” exist in any T with |T | = ℓ(q − 1)^{m} + 1, so d(C_{P_{ℓ}}) = (q − 1)^{m} − ℓ(q − 1)^{m−1}.

• Can do something very similar for parallelotopes and codes from many subpolytopes.

Summary

• Toric codes are interesting and accessible (even for undergraduate projects!)

• But the results on toric codes from simplices and parallelotopes show that d is often quite small relative to k.

• It is an interesting problem to determine criteria for polytopes (or subsets of the lattice points in a polytope) that yield good evaluation codes.