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

[2]

Y. Aubry and F. Rodier, Differentially 4-uniform functions,, in, (2010), 1.   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.  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, (2007), 296.  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.  doi: 10.1017/S0004972700036200.  Google Scholar

[6]

T. Ernst, Generalized Vandermonde determinants,, report 2000: 6 Matematiska Institutionen, (2000).   Google Scholar

[7]

D. K. Faddeev and I. S. Sominskii, "Problems in Higher Algebra,", Freeman, (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.   Google Scholar

[9]

S. Ghorpade and G. Lachaud, Number of solutions of equations over finite fields and a conjecture of Lang and Weil,, in, (2002), 269.   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.  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.  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.  doi: 10.1006/ffta.2000.0303.  Google Scholar

[13]

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

[14]

A. Lascoux and P. Pragracz, Jacobian of symmetric polynomials,, Ann. Comb., 6 (2002), 169.  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.  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.  doi: 10.1007/s11425-008-0066-3.  Google Scholar

[17]

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

[18]

F. Rodier, Borne sur le degré des polynômes presque parfaitement non-linéaires,, in, (2009), 169.   Google Scholar

[19]

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

[20]

D. Wan, Generators and irreducible polynomials over finite fields,, Math. Comp., 66 (1997), 1195.  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.   Google Scholar

[2]

Y. Aubry and F. Rodier, Differentially 4-uniform functions,, in, (2010), 1.   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.  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, (2007), 296.  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.  doi: 10.1017/S0004972700036200.  Google Scholar

[6]

T. Ernst, Generalized Vandermonde determinants,, report 2000: 6 Matematiska Institutionen, (2000).   Google Scholar

[7]

D. K. Faddeev and I. S. Sominskii, "Problems in Higher Algebra,", Freeman, (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.   Google Scholar

[9]

S. Ghorpade and G. Lachaud, Number of solutions of equations over finite fields and a conjecture of Lang and Weil,, in, (2002), 269.   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.  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.  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.  doi: 10.1006/ffta.2000.0303.  Google Scholar

[13]

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

[14]

A. Lascoux and P. Pragracz, Jacobian of symmetric polynomials,, Ann. Comb., 6 (2002), 169.  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.  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.  doi: 10.1007/s11425-008-0066-3.  Google Scholar

[17]

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

[18]

F. Rodier, Borne sur le degré des polynômes presque parfaitement non-linéaires,, in, (2009), 169.   Google Scholar

[19]

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

[20]

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

[1]

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

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378
[3]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[4]

Fabian Ziltener. Note on coisotropic Floer homology and leafwise fixed points. Electronic Research Archive, , () : -. doi: 10.3934/era.2021001
[5]

Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139
[6]

Peter H. van der Kamp, D. I. McLaren, G. R. W. Quispel. Homogeneous darboux polynomials and generalising integrable ODE systems. Journal of Computational Dynamics, 2021, 8 (1) : 1-8. doi: 10.3934/jcd.2021001
[7]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006
[8]

Eduard Marušić-Paloka, Igor Pažanin. Homogenization and singular perturbation in porous media. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020279
[9]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[10]

He Zhang, John Harlim, Xiantao Li. Estimating linear response statistics using orthogonal polynomials: An RKHS formulation. Foundations of Data Science, 2020, 2 (4) : 443-485. doi: 10.3934/fods.2020021
[11]

Ágota P. Horváth. Discrete diffusion semigroups associated with Jacobi-Dunkl and exceptional Jacobi polynomials. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021002
[12]

Teresa D'Aprile. Bubbling solutions for the Liouville equation around a quantized singularity in symmetric domains. Communications on Pure & Applied Analysis, 2021, 20 (1) : 159-191. doi: 10.3934/cpaa.2020262
[13]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[14]

Nicholas Geneva, Nicholas Zabaras. Multi-fidelity generative deep learning turbulent flows. Foundations of Data Science, 2020, 2 (4) : 391-428. doi: 10.3934/fods.2020019
[15]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020390
[16]

Hongfei Yang, Xiaofeng Ding, Raymond Chan, Hui Hu, Yaxin Peng, Tieyong Zeng. A new initialization method based on normed statistical spaces in deep networks. Inverse Problems & Imaging, 2021, 15 (1) : 147-158. doi: 10.3934/ipi.2020045
[17]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345
[18]

Craig Cowan, Abdolrahman Razani. Singular solutions of a Lane-Emden system. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 621-656. doi: 10.3934/dcds.2020291
[19]

Xinfu Chen, Huiqiang Jiang, Guoqing Liu. Boundary spike of the singular limit of an energy minimizing problem. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3253-3290. doi: 10.3934/dcds.2020124
[20]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences