Singularities of symmetric hypersurfaces and Reed-Solomon codes

Previous Article
Partitioning CCZ classes into EA classes
AMC Home
This Issue
Next Article
A note on the minimum Lee distance of certain self-dual modular codes

February 2012, 6(1): 69-94. doi: 10.3934/amc.2012.6.69

Singularities of symmetric hypersurfaces and Reed-Solomon codes

Antonio Cafure ^1, , Guillermo Matera ^2, and Melina Privitelli ^2,

1.	Instituto del Desarrollo Humano, Universidad Nacional de General Sarmiento, J.M. Gutiérrez 1150, Los Polvorines (B1613GSX) Buenos Aires, Argentina, and, Ciclo Básico Común, Universidad de Buenos Aires, Ciudad Universitaria, Pabellón III (1428) Buenos Aires, Argentina, and, National Council of Research and Technology (CONICET), Buenos Aires, Argentina
2.	Instituto del Desarrollo Humano, Universidad Nacional de General Sarmiento, J.M. Gutiérrez 1150, Los Polvorines (B1613GSX) Buenos Aires, Argentina, and, National Council of Research and Technology (CONICET), Buenos Aires, Argentina, Argentina

Received October 2010 Revised December 2011 Published January 2012

Abstract
Related Papers

We determine conditions on $q$ for the nonexistence of deep holes of the standard Reed-Solomon code of dimension $k$ over $\mathbb F_q$ generated by polynomials of degree $k+d$. Our conditions rely on the existence of $q$-rational points with nonzero, pairwise-distinct coordinates of a certain family of hypersurfaces defined over $\mathbb F_q$. We show that the hypersurfaces under consideration are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning the singular locus of these hypersurfaces, from which the existence of $q$-rational points is established.

Keywords: Reed-Solomon codes, deep holes, Finite fields, singular hypersurfaces, rational points., symmetric polynomials.

Mathematics Subject Classification: Primary: 11G25, 14G15; Secondary: 14G50,05E0.

Citation: Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69

References:

[1]	A. Adolphson and S. Sperber, On the degree of the L-function associated with an exponential sum, Compos. Math., 68 (1988), 125-159.
[2]	Y. Aubry and F. Rodier, Differentially 4-uniform functions, in "Arithmetic, Geometry, Cryptography and Coding Theory 2009" (eds. D. Kohel and R. Rolland), Amer. Math. Soc., (2010), 1-8.
[3]	A. Cafure and G. Matera, Improved explicit estimates on the number of solutions of equations over a finite field, Finite Fields Appl., 12 (2006), 155-185. doi: 10.1016/j.ffa.2005.03.003.
[4]	Q. Cheng and E. Murray, On deciding deep holes of Reed-Solomon codes, in "Theory and Applications of Models of Computation,'' Springer, Berlin, (2007), 296-305. doi: 10.1007/978-3-540-72504-6_27.
[5]	R. Coulter and M. Henderson, A note on the roots of trinomials over a finite field, Bull. Austral. Math. Soc., 69 (2004), 429-432. doi: 10.1017/S0004972700036200.
[6]	T. Ernst, Generalized Vandermonde determinants, report 2000: 6 Matematiska Institutionen, Uppsala Universitet, 2000; available online at http://www2.math.uu.se/research/pub/Ernst1.pdf
[7]	D. K. Faddeev and I. S. Sominskii, "Problems in Higher Algebra," Freeman, San Francisco, 1965.
[8]	S. Ghorpade and G. Lachaud, Étale cohomology, Lefschetz theorems and number of points of singular varieties over finite fields, Mosc. Math. J., 2 (2002), 589-631.
[9]	S. Ghorpade and G. Lachaud, Number of solutions of equations over finite fields and a conjecture of Lang and Weil, in "Number Theory and Discrete Mathematics" (eds. A.K. Agarwal et al.), Hindustan Book Agency, (2002), 269-291.
[10]	V. Guruswami and A. Vardy, Maximum-likelihood decoding of Reed-Solomon codes is NP-hard, IEEE Trans. Inform. Theory, 51 (2005), 2249-2256. doi: 10.1109/TIT.2005.850102.
[11]	J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24 (1983), 239-277. doi: 10.1016/0304-3975(83)90002-6.
[12]	N. Katz, Sums of Betti numbers in arbitrary characteristic, Finite Fields Appl., 7 (2001), 29-44. doi: 10.1006/ffta.2000.0303.
[13]	E. Kunz, "Introduction to Commutative Algebra and Algebraic Geometry,'' Birkhäuser, Boston, 1985.
[14]	A. Lascoux and P. Pragracz, Jacobian of symmetric polynomials, Ann. Comb., 6 (2002), 169-172. doi: 10.1007/PL00012583.
[15]	J. Li and D. Wan, On the subset sum problem over finite fields, Finite Fields Appl., 14 (2008), 911-929. doi: 10.1016/j.ffa.2008.05.003.
[16]	Y.-J. Li and D. Wan, On error distance of Reed-Solomon codes, Sci. China Ser. A, 51 (2008), 1982-1988. doi: 10.1007/s11425-008-0066-3.
[17]	R. Lidl and H. Niederreiter, "Finite Fields,'' 2^nd edition, Addison-Wesley, Massachusetts, 1997.
[18]	F. Rodier, Borne sur le degré des polynômes presque parfaitement non-linéaires, in "Arithmetic, Geometry, Cryptography and Coding Theory,'' Amer. Math. Soc., (2009), 169-181.
[19]	I. R. Shafarevich, "Basic Algebraic Geometry: Varieties in projective space,'' Springer, Berlin, 1994.
[20]	D. Wan, Generators and irreducible polynomials over finite fields, Math. Comp., 66 (1997), 1195-1212. doi: 10.1090/S0025-5718-97-00835-1.

show all references

References:

[1]	A. Adolphson and S. Sperber, On the degree of the L-function associated with an exponential sum, Compos. Math., 68 (1988), 125-159.
[2]	Y. Aubry and F. Rodier, Differentially 4-uniform functions, in "Arithmetic, Geometry, Cryptography and Coding Theory 2009" (eds. D. Kohel and R. Rolland), Amer. Math. Soc., (2010), 1-8.
[3]	A. Cafure and G. Matera, Improved explicit estimates on the number of solutions of equations over a finite field, Finite Fields Appl., 12 (2006), 155-185. doi: 10.1016/j.ffa.2005.03.003.
[4]	Q. Cheng and E. Murray, On deciding deep holes of Reed-Solomon codes, in "Theory and Applications of Models of Computation,'' Springer, Berlin, (2007), 296-305. doi: 10.1007/978-3-540-72504-6_27.
[5]	R. Coulter and M. Henderson, A note on the roots of trinomials over a finite field, Bull. Austral. Math. Soc., 69 (2004), 429-432. doi: 10.1017/S0004972700036200.
[6]	T. Ernst, Generalized Vandermonde determinants, report 2000: 6 Matematiska Institutionen, Uppsala Universitet, 2000; available online at http://www2.math.uu.se/research/pub/Ernst1.pdf
[7]	D. K. Faddeev and I. S. Sominskii, "Problems in Higher Algebra," Freeman, San Francisco, 1965.
[8]	S. Ghorpade and G. Lachaud, Étale cohomology, Lefschetz theorems and number of points of singular varieties over finite fields, Mosc. Math. J., 2 (2002), 589-631.
[9]	S. Ghorpade and G. Lachaud, Number of solutions of equations over finite fields and a conjecture of Lang and Weil, in "Number Theory and Discrete Mathematics" (eds. A.K. Agarwal et al.), Hindustan Book Agency, (2002), 269-291.
[10]	V. Guruswami and A. Vardy, Maximum-likelihood decoding of Reed-Solomon codes is NP-hard, IEEE Trans. Inform. Theory, 51 (2005), 2249-2256. doi: 10.1109/TIT.2005.850102.
[11]	J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24 (1983), 239-277. doi: 10.1016/0304-3975(83)90002-6.
[12]	N. Katz, Sums of Betti numbers in arbitrary characteristic, Finite Fields Appl., 7 (2001), 29-44. doi: 10.1006/ffta.2000.0303.
[13]	E. Kunz, "Introduction to Commutative Algebra and Algebraic Geometry,'' Birkhäuser, Boston, 1985.
[14]	A. Lascoux and P. Pragracz, Jacobian of symmetric polynomials, Ann. Comb., 6 (2002), 169-172. doi: 10.1007/PL00012583.
[15]	J. Li and D. Wan, On the subset sum problem over finite fields, Finite Fields Appl., 14 (2008), 911-929. doi: 10.1016/j.ffa.2008.05.003.
[16]	Y.-J. Li and D. Wan, On error distance of Reed-Solomon codes, Sci. China Ser. A, 51 (2008), 1982-1988. doi: 10.1007/s11425-008-0066-3.
[17]	R. Lidl and H. Niederreiter, "Finite Fields,'' 2^nd edition, Addison-Wesley, Massachusetts, 1997.
[18]	F. Rodier, Borne sur le degré des polynômes presque parfaitement non-linéaires, in "Arithmetic, Geometry, Cryptography and Coding Theory,'' Amer. Math. Soc., (2009), 169-181.
[19]	I. R. Shafarevich, "Basic Algebraic Geometry: Varieties in projective space,'' Springer, Berlin, 1994.
[20]	D. Wan, Generators and irreducible polynomials over finite fields, Math. Comp., 66 (1997), 1195-1212. doi: 10.1090/S0025-5718-97-00835-1.

[1]	Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[2]	Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
[3]	Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057
[4]	Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[5]	Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
[6]	José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467
[7]	Daniele Bartoli, Leo Storme. On the functional codes arising from the intersections of algebraic hypersurfaces of small degree with a non-singular quadric. Advances in Mathematics of Communications, 2014, 8 (3) : 271-280. doi: 10.3934/amc.2014.8.271
[8]	Jayadev S. Athreya, Gregory A. Margulis. Values of random polynomials at integer points. Journal of Modern Dynamics, 2018, 12: 9-16. doi: 10.3934/jmd.2018002
[9]	Motoko Qiu Kawakita. Certain sextics with many rational points. Advances in Mathematics of Communications, 2017, 11 (2) : 289-292. doi: 10.3934/amc.2017020
[10]	Susanne Pumplün. Finite nonassociative algebras obtained from skew polynomials and possible applications to (f, σ, δ)-codes. Advances in Mathematics of Communications, 2017, 11 (3) : 615-634. doi: 10.3934/amc.2017046
[11]	Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021
[12]	Hui Liu, Duanzhi Zhang. Stable P-symmetric closed characteristics on partially symmetric compact convex hypersurfaces. Discrete and Continuous Dynamical Systems, 2016, 36 (2) : 877-893. doi: 10.3934/dcds.2016.36.877
[13]	Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459
[14]	Thomas Gauthier, Gabriel Vigny. Distribution of postcritically finite polynomials Ⅱ: Speed of convergence. Journal of Modern Dynamics, 2017, 11: 57-98. doi: 10.3934/jmd.2017004
[15]	Leonardo Manuel Cabrer, Daniele Mundici. Classifying GL$(n,\mathbb{Z})$-orbits of points and rational subspaces. Discrete and Continuous Dynamical Systems, 2016, 36 (9) : 4723-4738. doi: 10.3934/dcds.2016005
[16]	Rich Stankewitz. Density of repelling fixed points in the Julia set of a rational or entire semigroup, II. Discrete and Continuous Dynamical Systems, 2012, 32 (7) : 2583-2589. doi: 10.3934/dcds.2012.32.2583
[17]	José Carmona, Pedro J. Martínez-Aparicio. Homogenization of singular quasilinear elliptic problems with natural growth in a domain with many small holes. Discrete and Continuous Dynamical Systems, 2017, 37 (1) : 15-31. doi: 10.3934/dcds.2017002
[18]	Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[19]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[20]	Zhongjie Liu, Duanzhi Zhang. Brake orbits on compact symmetric dynamically convex reversible hypersurfaces on $ \mathbb{R}^\text{2n} $. Discrete and Continuous Dynamical Systems, 2019, 39 (7) : 4187-4206. doi: 10.3934/dcds.2019169

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Antonio Cafure Guillermo Matera Melina Privitelli
on Google Scholar
Antonio Cafure Guillermo Matera Melina Privitelli

[Back to Top]