Singularities of symmetric hypersurfaces and Reed-Solomon codes

Antonio Cafure; Guillermo Matera; Melina Privitelli

doi:10.3934/amc.2012.6.69

Article Contents

2012, Volume 6, Issue 1: 69-94. Doi: 10.3934/amc.2012.6.69

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

Singularities of symmetric hypersurfaces and Reed-Solomon codes

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

Received: September 30, 2010

Revised: November 30, 2011

Published: January 2012

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.