Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Toric Codes

John B. Little

Department of Mathematics and Computer Science College of the Holy Cross

Joint work with Hal Schenck (U. Illinois), Ryan Schwarz (U. Connecticut), Alex Simao (Holy Cross)

AMS Special Session on Linear Codes Over Rings and Modules – Kalamazoo, October 17, 2008

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Outline

1 Toric Code Basics

Codes from Polytopes

2 Tools From Algebraic Geometry

Toric Varieties An Example

3 Higher-dimensional Polytopes and Vandermonde Matrices

The Connection Estimating d of a Toric Code

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

The Definition And A First Example 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) is the case P = [0, k − 1] ⊂ ℝ since L_{P} = Span{1, x, …, x^{k−1}}.

John B. Little  Toric Codes

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

The Definition And A First Example 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) is the case P = [0, k − 1] ⊂ ℝ since L_{P} = Span{1, x, …, x^{k−1}}.

John B. Little  Toric Codes

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

The Definition And A First Example 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) is the case P = [0, k − 1] ⊂ ℝ since L_{P} = Span{1, x, …, x^{k−1}}.

John B. Little  Toric Codes

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

The Definition And A First Example 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) is the case P = [0, k − 1] ⊂ ℝ since L_{P} = Span{1, x, …, x^{k−1}}.

John B. Little  Toric Codes

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

The Definition And A First Example 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) is the case P = [0, k − 1] ⊂ ℝ since L_{P} = Span{1, x, …, x^{k−1}}.

John B. Little  Toric Codes

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

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)

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

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)

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

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)

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

When Are Toric Codes Equivalent? Usually take P ⊂ [0, q − 2]^{m} ≃ (ℤ_{q−1})^{m}.

Theorem 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Π; implies that parameters are the same.)

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

Small Needles In Huge Haystacks!

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

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 one of the 2128 orbits for k = 8 gives codes with d = 42 (best previously known: d = 41 according to Grassl’s table).

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

Small Needles In Huge Haystacks!

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

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 one of the 2128 orbits for k = 8 gives codes with d = 42 (best previously known: d = 41 according to Grassl’s table).

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

Small Needles In Huge Haystacks!

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

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 one of the 2128 orbits for k = 8 gives codes with d = 42 (best previously known: d = 41 according to Grassl’s table).

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

Codes from Polytopes

Small Needles In Huge Haystacks!

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

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 one of the 2128 orbits for k = 8 gives codes with d = 42 (best previously known: d = 41 according to Grassl’s table).

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Toric Codes And Toric Varieties

A polytope P specifies a normal fan Σ = Σ_{P}, hence an abstract toric variety X = X_{Σ}. Also get a line bundle L = L_{P} on X specified by P. Subpolytopes P_{i} correspond to subspaces of H^{0}(X, L). In case m = 2, main results of L. and Schenck “Toric surface codes and Minkowski sums” show that for q sufficiently large, d(C_{P}(𝔽_{q})) can be bounded above and below by looking at subpolygons P′ ⊆ P that decompose as Minkowski sums.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Toric Codes And Toric Varieties

A polytope P specifies a normal fan Σ = Σ_{P}, hence an abstract toric variety X = X_{Σ}. Also get a line bundle L = L_{P} on X specified by P. Subpolytopes P_{i} correspond to subspaces of H^{0}(X, L). In case m = 2, main results of L. and Schenck “Toric surface codes and Minkowski sums” show that for q sufficiently large, d(C_{P}(𝔽_{q})) can be bounded above and below by looking at subpolygons P′ ⊆ P that decompose as Minkowski sums.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Toric Codes And Toric Varieties

A polytope P specifies a normal fan Σ = Σ_{P}, hence an abstract toric variety X = X_{Σ}. Also get a line bundle L = L_{P} on X specified by P. Subpolytopes P_{i} correspond to subspaces of H^{0}(X, L). In case m = 2, main results of L. and Schenck “Toric surface codes and Minkowski sums” show that for q sufficiently large, d(C_{P}(𝔽_{q})) can be bounded above and below by looking at subpolygons P′ ⊆ P that decompose as Minkowski sums.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Toric Codes And Toric Varieties

A polytope P specifies a normal fan Σ = Σ_{P}, hence an abstract toric variety X = X_{Σ}. Also get a line bundle L = L_{P} on X specified by P. Subpolytopes P_{i} correspond to subspaces of H^{0}(X, L). In case m = 2, main results of L. and Schenck “Toric surface codes and Minkowski sums” show that for q sufficiently large, d(C_{P}(𝔽_{q})) can be bounded above and below by looking at subpolygons P′ ⊆ P that decompose as Minkowski sums.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

The Lower Bound

Theorem 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}.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Intuition For Proof Minkowski-decomposable subpolygons ⇔ reducible sections f_{1}f_{2} (Newton polygon of a product is the Minkowski sum). Hasse-Weil upper and lower bounds for a curve Y :

q + 1 − 2g(Y )\sqrt{q} ≤ |Y (𝔽_{q})| ≤ q + 1 + 2g(Y )\sqrt{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.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Intuition For Proof Minkowski-decomposable subpolygons ⇔ reducible sections f_{1}f_{2} (Newton polygon of a product is the Minkowski sum). Hasse-Weil upper and lower bounds for a curve Y :

q + 1 − 2g(Y )\sqrt{q} ≤ |Y (𝔽_{q})| ≤ q + 1 + 2g(Y )\sqrt{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.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Intuition For Proof Minkowski-decomposable subpolygons ⇔ reducible sections f_{1}f_{2} (Newton polygon of a product is the Minkowski sum). Hasse-Weil upper and lower bounds for a curve Y :

q + 1 − 2g(Y )\sqrt{q} ≤ |Y (𝔽_{q})| ≤ q + 1 + 2g(Y )\sqrt{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.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

An Interesting Polygon

[figure]

Figure: The polygon P

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).

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Reducible Curves From P′ we obtain x(x − a)(y − b)(y − c) = 0. If a, b, c ∈ 𝔽_{q}^{∗} and b ≠ c, then 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)

John B. Little  Toric Codes

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

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}.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary Toric Varieties An Example

Arithmetic Of 𝔽_{8} Matters Note: 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.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

Motivation – Reed-Solomon Case Square submatrices of the generator matrix G for a Reed-Solomon code are usual (one-variable) 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})

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

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}.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

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}.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

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}.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

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) =

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}

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

Minimum Distance Theorem From L., Schwarz, “Toric Codes and Vandermonde Matrices”

Theorem 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 detV (P; S) ≠ 0. Then the minimum distance satisfies d(C_{P}) ≥ d.

Proof: For all S, detV (P; S) ≠ 0 ⇒ homogeneous linear system 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.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

Codes From Simplices, etc. Consider simplices of form P_{ℓ} = Conv(ℓe_{i} : i = 1, …, m). Via a recursive determinant identity, detV (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 as before with |T | = ℓ(q − 1)^{m} + 1, so d(C_{P_{ℓ}}) = (q − 1)^{m} − ℓ(q − 1)^{m−1}. Can do something very similar for paralellotopes. Also implies results for codes from many subpolytopes of these.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

Codes From Simplices, etc. Consider simplices of form P_{ℓ} = Conv(ℓe_{i} : i = 1, …, m). Via a recursive determinant identity, detV (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 as before with |T | = ℓ(q − 1)^{m} + 1, so d(C_{P_{ℓ}}) = (q − 1)^{m} − ℓ(q − 1)^{m−1}. Can do something very similar for paralellotopes. Also implies results for codes from many subpolytopes of these.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

Codes From Simplices, etc. Consider simplices of form P_{ℓ} = Conv(ℓe_{i} : i = 1, …, m). Via a recursive determinant identity, detV (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 as before with |T | = ℓ(q − 1)^{m} + 1, so d(C_{P_{ℓ}}) = (q − 1)^{m} − ℓ(q − 1)^{m−1}. Can do something very similar for paralellotopes. Also implies results for codes from many subpolytopes of these.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

Codes From Simplices, etc. Consider simplices of form P_{ℓ} = Conv(ℓe_{i} : i = 1, …, m). Via a recursive determinant identity, detV (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 as before with |T | = ℓ(q − 1)^{m} + 1, so d(C_{P_{ℓ}}) = (q − 1)^{m} − ℓ(q − 1)^{m−1}. Can do something very similar for paralellotopes. Also implies results for codes from many subpolytopes of these.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary The Connection Estimating d of a Toric Code

Codes From Simplices, etc. Consider simplices of form P_{ℓ} = Conv(ℓe_{i} : i = 1, …, m). Via a recursive determinant identity, detV (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 as before with |T | = ℓ(q − 1)^{m} + 1, so d(C_{P_{ℓ}}) = (q − 1)^{m} − ℓ(q − 1)^{m−1}. Can do something very similar for paralellotopes. Also implies results for codes from many subpolytopes of these.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

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 and apparently subtle problem to determine criteria for polytopes (or subsets of the lattice points in a polytope) that yield good evaluation codes.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

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 and apparently subtle problem to determine criteria for polytopes (or subsets of the lattice points in a polytope) that yield good evaluation codes.

Toric Code Basics

Tools From Algebraic Geometry

Higher-dimensional Polytopes and Vandermonde Matrices Summary

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 and apparently subtle problem to determine criteria for polytopes (or subsets of the lattice points in a polytope) that yield good evaluation codes.

Appendix  For Further Reading

For Further Reading

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

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