Toric Surface Codes and the Periodicity of Polytopes

Amelia Gibbs, Eliza Hogan, Kelly Jabbusch, Jenna Plute, Nicholas Toloczko · 2025

Read Toric Surface Codes and the Periodicity of Polytopes by Amelia Gibbs, Eliza Hogan, Kelly Jabbusch, Jenna Plute, Nicholas Toloczko (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-21178.txt.

Introduction

Error correcting codes built from lattice polytopes are called toric codes, and their strength is measured here. The 2025 paper is by Amelia Gibbs and 4 co-authors. Toric codes are error correcting codes built from toric varieties. Those varieties match lattice polytopes, which are flat sided shapes on a grid. The paper studies two dimensional polytopes and the codes they define. It focuses on shapes with a period one property.

For period one shapes, the count of grid points scales in a simple way when the shape grows. The authors prove an explicit formula for the minimum distance of codes from one class of such shapes. Minimum distance measures how well a code can spot errors. They also use Vandermonde matrices, following Little and Schwarz, to find the distance for another class.

Catalog record

CREATORAmelia Gibbs, Eliza Hogan, Kelly Jabbusch, Jenna Plute, Nicholas Toloczko
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-21178

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Toric Surface Codes and the Periodicity of Polytopes Amelia Gibbs, Eliza Hogan, Kelly Jabbusch, Jenna Plute, Nicholas Toloczko Abstract . Toric codes are error-correcting codes that are derived from toric varieties, which hold a unique correspondence to integral convex polytopes. In this paper, we focus on integral convex polytopes P ⊆ ℝ 2 P\subseteq\mathbb{R}^{2} and the toric codes they define. We begin by studying period-1 polytopes – polytopes satisfying the property L ⁡ ( t ​ P ) L(tP) = t ​ L ​ ( P ) tL(P) for all t ∈ ℤ + t\in\mathbb{Z}^{+} , where t ​ P tP is the t t -dilate of P P , and we prove an explicit formula for the minimum distance of toric codes associated to a particular class of period-1 polytopes. We also apply the methods of Little and Schwarz, using Vandermonde matrices, to compute the minimum distance of another class of period-1 polytopes. 1. Introduction Toric codes are the natural extensions of Reed-Solomon codes. They were originally introduced by Hansen for two-dimensional spaces, (see [ 2 ] and [ 3 ] ), and subsequently studied by various authors including Joyner [ 4 ] , Little and Schenck [ 5 ] , Little and Schwarz [ 6 ] , Ruano [ 7 ] , and Soprunov and Soprunova [ 8 ] , [ 9 ] . To begin the construction of a toric code, we first fix a finite field \mathbb{F}_{q} and let P\subset\mathbb{R}^{m} be an integral convex polytope, which is contained in the m -dimensional box [0,q-2]^{m} and has k lattice points. The toric code C_{P}(\mathbb{F}_{q}) is obtained by evaluating linear combinations of monomials corresponding to the lattice points of P over the finite field \mathbb{F}_{q} . To determine if a given code is “good" from a coding theoretic perspective, one considers parameters associated to the code: the block length, the dimension, and the minimum distance (see Section 2 for the precise definitions). In general, an ideal code will have minimum distance and dimension large with respect to its block length. For the class of toric codes, the first two parameters are easy to compute. Given a toric code C_{P}(\mathbb{F}_{q}) , the block length is N=(q-1)^{m} , and the dimension of the code is given by the number of lattice points k=|P\cap\mathbb{Z}^{m}| , [ 7 ] . The minimum distance is not as easy to compute, and various authors have given formulas for computing (or bounding) minimum distances for toric codes defined by special classes of polytopes. In the case of toric surface codes (where m=2 ), Hansen computed the minimum distance for codes coming from Hirzebruch surfaces ( [ 2 ] , [ 3 ] ), Little and Schenck determined upper and lower bounds for the minimum distance of a toric surface code by examining Minkowski sum decompositions [ 5 ] , and Soprunov and Soprunova improved these bounds for surface codes by examining the Minkowski length [ 8 ] . In the higher dimensional case, Little and Schwarz used Vandermonde matrices to compute minimum distances of simplices and rectangular boxes [ 6 ] , and Soprunov and Soprunova extended these results in [ 9 ] . In this paper, we will focus on integral convex polytopes P\subset\mathbb{R}^{2} and the toric codes they define. We begin in Section 3 by investigating the Minkowski length of integral convex polytopes in the plane, and how polytope operations, such as dilation and Minkowski sum, effect the Minkowski length. In particular, we compute the Minkowski length of certain classes of polytopes. We further investigate which polytopes are of period 1 , that is, satisfy the property that the Minkowski length of a t -dialate of a polytope P is equal to t times the Minkowski length of P : L(tP)=tL(P) . Building on the results of Soprunov and Soprunova [ 8 ] , in Section 4 , we use maximal decompositions to compute the minimum distance of toric codes arising from certain integral convex period 1 polytopes in \mathbb{R}^{2}. As an application, we determine the minimum distance for codes arising from polytopes of the form Z=m[0,{e}_{1}]+n[0,{e}_{2}]+\ell[0,{e}_{1}+{e}_{2}] and Q=m[0,{e}_{1}]+n[0,{e}_{2}]+\ell[0,{e}_{1}+{e}_{2}]+s[0,{e}_{1}-{e}_{2}]+2\ell\Delta, where \Delta is the standard 2 -simplex, \Delta=\operatorname{conv}\{(0,0),(1,0),(0,1)\} (see Corollary 4.6 and Corollary 4.9 ). In [ 6 ] , Little and Schwarz used special configurations of points in (\mathbb{F}_{q}^{\times})^{m} and determinants of Vandermonde matrices to compute minimum distances of codes coming from simplices and rectangular polytopes in \mathbb{R}^{m} . This process gave a quite elementary method to compute minimum distances of certain toric codes. In Section 5 , we use their methods to derive the minimum distance formula for toric codes arising from polytopes of the form P=\ell\Delta+\ell[0,e_{1}]+\ell[0,e_{2}] , where \ell is any positive integer (see Corollary 5.9 ). 2. Preliminaries 2.1. Linear Codes We begin with some basics from coding theory. Fix a prime power q , a linear code C is a vector subspace of \mathbb{F}_{q}^{m} for some m\geq 1 where \mathbb{F}_{q} denotes the finite field with q elements. Any {c}=(c_{1},\ldots,c_{n})\in C is called a codeword of C and n is called the block length of C . Since C is a vector space, we define the dimension of the code C to simply be the dimension of C as a vector space: k=\dim C . Intuitively, the dimension of a linear code represents the amount of information that a codeword contains. Given two code words a,b\in C the Hamming distance between a and b is the number of non-zero entries in a-b . The Hamming weight of {a}\in C is simply the number of non-zero entries in {a} . The minimum distance of C , denoted d(C) , is the minimum Hamming distance between pairs of distinct codewords. Since C is linear, this is equivalent to the minimum Hamming weight of any non-zero codeword. Intuitively, the minimum distance of the code represents the number of errors the code can correct. 2.2. Newton Polytopes and Minkowski Sum Let f\in\Bbbk[t_{1}^{\pm 1},\ldots,t_{m}^{\pm 1}], where \Bbbk is a field. Write f=\sum_{\alpha\in\mathbb{Z}^{m}}c_{\alpha}t^{\alpha} where \alpha=(\alpha_{1},\ldots,\alpha_{m}) and t^{\alpha}=t_{1}^{\alpha_{1}}\cdots t_{m}^{\alpha_{m}} . The Newton polytope of f , denoted P_{f} , is defined as P_{f}=\operatorname{conv}\left\{\alpha\in\mathbb{Z}^{m}:c_{\alpha}\neq 0\right\}\subset\mathbb{R}^{m}. Note that there are only finitely many \alpha\in\mathbb{Z}^{m} with c_{\alpha}\neq 0 . Therefore, P_{f} is an integral convex polytope. Recall the Minkowski sum of two polytopes P,Q\subset\mathbb{R}^{m} is defined as P+Q=\left\{p+q:p\in P,q\in Q\right\}. Being able to write a polytope, P , as the Minkowski sum of “simpler” polytopes allows for factorization of any Laurent polynomial whose Newton polytope is P . In the case of Newton polytopes, note that P_{fg}=P_{f}+P_{g}. By a primitive line segment we mean a line segment whose only lattice points are the endpoints. If a polytope is a Minkowski sum of primitive lattice segments, we’ll call it a zonotope . 2.3. Toric Codes A toric code is defined as follows: fix an integral convex polytope P\subset\mathbb{R}^{m} and let \mathcal{L}_{P} denote the set of all f\in\mathbb{F}_{q}[t_{1}^{\pm 1},\ldots,t_{m}^{\pm 1}] such that P_{f}\subseteq P or, equivalently, \mathcal{L}_{P}=\operatorname{span}_{\mathbb{F}_{q}}\left\{t^{\alpha}:\alpha\in P\cap\mathbb{Z}^{m}\right\}. Define the evaluation map \begin{array}[]{rcl}\operatorname{ev}:\mathcal{L}_{P}&\to&\mathbb{F}_{q}^{(q-1)^{m}}\\ f&\mapsto&\left(f(\gamma):\gamma\in(\mathbb{F}_{q}^{\times})^{m}\right)\end{array}. The toric code associated to P , denoted by C_{P} , is defined to be the image of \operatorname{ev} . It is clear that the block length of C_{P} is n=(q-1)^{m} , and by [ 7 ] ,

Read the complete text