Projective toric codes. (English) Zbl 1535.94094
Summary: Any integral convex polytope \(P\) in \(\mathbb{R}^N\) provides an \(N\)-dimensional toric variety \(\mathbf{X}_P\) and an ample divisor \(D_P\) on this variety. This paper gives an explicit construction of the algebraic geometric error-correcting code on \(\mathbf{X}_P\), obtained by evaluating global section of the line bundle corresponding to \(D_P\) on every rational point of \(\mathbf{X}_P\). This work presents an extension of toric codes analogous to the one of Reed-Muller codes into projective ones, by evaluating on the whole variety instead of considering only points with nonzero coordinates. The dimension of the code is given in terms of the number of integral points in the polytope \(P\) and an algorithmic technique to get a lower bound on the minimum distance is described.
MSC:
| 94B27 | Geometric methods (including applications of algebraic geometry) applied to coding theory |
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
| 94B05 | Linear codes (general theory) |
| 14M25 | Toric varieties, Newton polyhedra, Okounkov bodies |
| 14J20 | Arithmetic ground fields for surfaces or higher-dimensional varieties |
| 52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 52B11 | \(n\)-dimensional polytopes |
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
Software:
Code TablesReferences:
| [1] | Beelen, P., Datta, M. and Ghorpade, S. R., Vanishing ideals of projective spaces over finite fields and a projective footprint bound, Acta Math. Sinica (Engl. Ser.)35(1) (2019) 47-63. · Zbl 1411.14024 |
| [2] | Brown, G. and Kasprzyk, A. M., Seven new champion linear codes, LMS J. Comput. Math.16 (2013) 109-117. · Zbl 1311.14027 |
| [3] | Brown, G. and Kasprzyk, A. M., Small polygons and toric codes, J. Symbolic Comput.51 (2013) 55-62. · Zbl 1272.52017 |
| [4] | Carvalho, C. and Neumann, V. G. L., Projective Reed-Muller type codes on rational normal scrolls, Finite Fields Appl.37 (2016) 85-107. · Zbl 1402.94124 |
| [5] | Cox, D. A., Little, J. and O’Shea, D., Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, (Springer-Verlag, Berlin, 2007). · Zbl 1118.13001 |
| [6] | Cox, D. A., Little, J. B. and Schenck, H. K.. Toric Varieties, , Vol. 124 (American Mathematical Society, Providence, RI, 2011). · Zbl 1223.14001 |
| [7] | Fillastre, F. and Izmestiev, I., Shapes of polyhedra, mixed volumes and hyperbolic geometry, Mathematika63(1) (2017) 124-183. · Zbl 1367.52010 |
| [8] | Geil, O. and Hoholdt, T., Footprints or generalized Bezout’s theorem, IEEE Trans. Inform. Theory46(2) (2000) 635-641. · Zbl 1001.94040 |
| [9] | A. L. Gluher and P. Spaenlehauer, A fast randomized geometric algorithm for computing Riemann-Roch spaces, arXiv:1811.08237. · Zbl 1454.14140 |
| [10] | Goppa, V. D., Algebraico-geometric codes, Math. USSR-Izv.21(1) (1983) 75-91. · Zbl 0522.94013 |
| [11] | M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, (2007), http://www.codetables.de, accessed on 2021-01-15. |
| [12] | R. Guilbot, Low degree hypersurfaces of projective toric varieties defined over a \(c_1\) field have a rational point (2014). |
| [13] | Haché, G., Computation in algebraic function fields for effective construction of algebraic-geometric codes, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, eds. Cohen, G., Giusti, M. and Mora, T. (Springer, Berlin, 1995), pp. 262-278. · Zbl 0876.94047 |
| [14] | Hansen, J. P., Toric varieties, Hirzebruch surfaces and error-correcting codes, Appl. Algebra Eng. Comm. Comput.13(4) (2002) 289-300. · Zbl 1043.94022 |
| [15] | Hansen, J. P., Secret sharing schemes with strong multiplication and a large number of players from toric varieties, Contemp. Math.686 (2017) 171-185. · Zbl 1391.94831 |
| [16] | Hess, F., Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput.33(4) (2002) 425-445. · Zbl 1058.14071 |
| [17] | Joyner, D., Toric codes over finite fields, Appl. Algebra Eng. Comm. Comput.15(1) (2004) 63-79. · Zbl 1092.94031 |
| [18] | Lachaud, G., The parameters of projective Reed-Muller codes, Discrete Math.81(2) (1990) 217-221. · Zbl 0696.94015 |
| [19] | Le Brigand, D. and Risler, J.-J., Algorithme de Brill-Noether et codes de Goppa, Bull. Soc. Math. France116(2) (1988) 231-253. · Zbl 0721.14015 |
| [20] | Little, J. and Schenck, H., Toric surface codes and Minkowski sums, SIAM J. Discrete Math.20(4) (2006) 999-1014. · Zbl 1131.14026 |
| [21] | J. Little and R. Schwarz, On \(m\)-dimensional toric codes, J. Little and R. Schwarz, On \(m\)-dimensional toric codes. ArXiv Preprint ArXiv:Cs/0506102 (2005). |
| [22] | Little, J. B., Remarks on generalized toric codes, Finite Fields Appl.24 (2013) 1-14. · Zbl 1305.94116 |
| [23] | Luo, X., Yau, S. S.-T., Zhang, M. and Zuo, H., On classification of toric surface codes of low dimension, Finite Fields Appl.33 (2015) 90-102. · Zbl 1394.14017 |
| [24] | Nardi, J., Algebraic geometric codes on minimal Hirzebruch surfaces, J. Algebra535 (2019) 556-597. · Zbl 1433.14020 |
| [25] | Ruano, D., On the parameters of \(r\)-dimensional toric codes, Finite Fields Appl.13(4) (2007) 962-976. · Zbl 1210.94115 |
| [26] | Soprunov, I. and Soprunova, J., Toric surface codes and Minkowski length of polygons, SIAM J. Discrete Math.23(1) (2008/09) 384-400. · Zbl 1195.94088 |
| [27] | Sørensen, A. B., Weighted Reed-Muller codes and algebraic-geometric codes, IEEE Trans. Inform. Theory38(6) (1992) 1821-1826. · Zbl 0759.94006 |
| [28] | Sperber, S. I. and Voight, J., Computing zeta functions of nondegenerate hypersurfaces with few monomials, LMS J. Comput. Math.16 (2013) 9-44. · Zbl 1343.11097 |
| [29] | Sturmfels, B., Gröbner Bases and Convex Polytopes, , Vol. 8 (American Mathematical Society, Providence, RI, 1996). · Zbl 0856.13020 |
| [30] | Volcheck, E. J., Computing in the Jacobian of a plane algebraic curve, in Algorithmic Number Theory, eds. Adleman, L. M. and Huang, M.-D. (Springer, Berlin, 1994), pp. 221-233. · Zbl 0826.14040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
