American Institute of Mathematical Sciences

Advanced
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

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 fi elds, 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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 Google Scholar

[7]

D. K. Faddeev and I. S. Sominskii, "Problems in Higher Algebra," Freeman, San Francisco, 1965.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

N. Katz, Sums of Betti numbers in arbitrary characteristic, Finite Fields Appl., 7 (2001), 29-44. doi: 10.1006/ffta.2000.0303.  Google Scholar

[13]

E. Kunz, "Introduction to Commutative Algebra and Algebraic Geometry,'' Birkhäuser, Boston, 1985.  Google Scholar

[14]

A. Lascoux and P. Pragracz, Jacobian of symmetric polynomials, Ann. Comb., 6 (2002), 169-172. doi: 10.1007/PL00012583.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

R. Lidl and H. Niederreiter, "Finite Fields,'' 2nd edition, Addison-Wesley, Massachusetts, 1997.  Google Scholar

[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.  Google Scholar

[19]

I. R. Shafarevich, "Basic Algebraic Geometry: Varieties in projective space,'' Springer, Berlin, 1994.  Google Scholar

[20]

D. Wan, Generators and irreducible polynomials over finite fields, Math. Comp., 66 (1997), 1195-1212. doi: 10.1090/S0025-5718-97-00835-1.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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 Google Scholar

[7]

D. K. Faddeev and I. S. Sominskii, "Problems in Higher Algebra," Freeman, San Francisco, 1965.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

N. Katz, Sums of Betti numbers in arbitrary characteristic, Finite Fields Appl., 7 (2001), 29-44. doi: 10.1006/ffta.2000.0303.  Google Scholar

[13]

E. Kunz, "Introduction to Commutative Algebra and Algebraic Geometry,'' Birkhäuser, Boston, 1985.  Google Scholar

[14]

A. Lascoux and P. Pragracz, Jacobian of symmetric polynomials, Ann. Comb., 6 (2002), 169-172. doi: 10.1007/PL00012583.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

R. Lidl and H. Niederreiter, "Finite Fields,'' 2nd edition, Addison-Wesley, Massachusetts, 1997.  Google Scholar

[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.  Google Scholar

[19]

I. R. Shafarevich, "Basic Algebraic Geometry: Varieties in projective space,'' Springer, Berlin, 1994.  Google Scholar

[20]

D. Wan, Generators and irreducible polynomials over finite fields, Math. Comp., 66 (1997), 1195-1212. doi: 10.1090/S0025-5718-97-00835-1.  Google Scholar

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

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
[10]

Motoko Qiu Kawakita. Certain sextics with many rational points. Advances in Mathematics of Communications, 2017, 11 (2) : 289-292. doi: 10.3934/amc.2017020
[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]

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
[13]

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
[14]

Hui Liu, Duanzhi Zhang. Stable P-symmetric closed characteristics on partially symmetric compact convex hypersurfaces. Discrete & Continuous Dynamical Systems, 2016, 36 (2) : 877-893. doi: 10.3934/dcds.2016.36.877
[15]

Leonardo Manuel Cabrer, Daniele Mundici. Classifying GL$(n,\mathbb{Z})$-orbits of points and rational subspaces. Discrete & 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 & 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 & Continuous Dynamical Systems, 2017, 37 (1) : 15-31. doi: 10.3934/dcds.2017002
[18]

Zhongjie Liu, Duanzhi Zhang. Brake orbits on compact symmetric dynamically convex reversible hypersurfaces on $ \mathbb{R}^\text{2n} $. Discrete & Continuous Dynamical Systems, 2019, 39 (7) : 4187-4206. doi: 10.3934/dcds.2019169
[19]

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
[20]

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

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (55)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences