A divisibility approach to the open boundary cases of Cusick-Li-Stǎnicǎ’s conjecture

详细信息    查看全文

• 作者：Francis N. Castro ; Oscar E. González ; Luis A. Medina
• 关键词：Boolean functions ; Cusick ; Li ; Stǎnicǎ’s conjecture ; 2 ; divisibility ; 05E05 ; 11T23 ; 06E30
• 刊名：Cryptography and Communications
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：7
• 期：4
• 页码：379-402
• 全文大小：1,081 KB
• 参考文献：1.Adolphson, A., Sperber, S.: p-adic estimates for exponential sums and the of chevalley-warning. Ann. Sci. Ec. Norm. Super., 4 e série 20, 545-56 (1987)MathSciNet
  2.Ax, J.: Zeros of polynomials over finite fields. Amer. J. Math. 86, 255-61 (1964)MathSciNet View Article
  3.Bassalygo, L.A., Zinoviev, V.A.: On divisibility of exponential sums of polynomials of special type over fields of characteristic 2. Des. Codes Cryptogr 66, 129-43 (2013)MathSciNet View Article
  4.Canteaut, A., Charpin, P., Dobbertin, H.: Weight divisibility of cyclic codes, highly nonlinear functions on G F(2 m ) and cross correlation of maximum-length sequences. SIAM J. Discret. Math. 13, 105-38 (2000)MathSciNet View Article
  5.Castro, F., Medina, L.: Linear recurrences and asymptotic behavior of exponential sums of symmetric boolean functions. Elec. J. Combinatorics 18, #P8 (2011)MathSciNet
  6.Castro, F., Medina, L.: Asymptotic behavior of perturbations of symmetric functions. Ann. Comb. 18, 397-17 (2014)MathSciNet View Article
  7.Castro, F., Medina, L., Rubio, I.: Exact Divisibility of exponential sums over the binary field via the covering method. Contemp. Math. 537, 129-36 (2009)MathSciNet View Article
  8.Castro, F., Rubio, I.: Exact p-divisibility of exponential sums via the covering method. Proc. Amer. Math. Soc., electronically published on October 29,2014, doi: 10.-090/?S0002-9939-2014-12315-X (to appear in print)
  9.Castro, F., Rubio, I.: Construction of Systems of polynomial equations with exact p-divisibility via the covering method. J. Algebra Appl. 13 (6), 1450013 (2014)MathSciNet View Article
  10.Cusick, T.W., Li, Y., Stǎnicǎ, P. IEEE Trans. Inf. Theory 5, 1304-307 (2008)MathSciNet View Article
  11.Cusick, T.W., Li, Y., Stǎnicǎ, P.: On a conjecture for balanced symmetric Boolean functions. J. Math. Crypt. 3, 1-8 (2009)MathSciNet View Article
  12.Davis, K.S., Webb, W.A.: Lucas-theorem for prime powers. Europ. J. Comb. 11, 229-33 (1990)MathSciNet View Article
  13.Guo, Y., Gao, G., Zhao, Y.: Recent Results on Balanced Symmetric Boolean Functions. http://?iacr.?org , e-print #93 (2012)
  14.Granville, A.: Zaphod Beeblerox’s brain and the fifty-ninth row of Pascal’s triangle. American. Math. Monthly 44, 318-31 (1992)MathSciNet View Article
  15.Güneri, C., McGuire, G.: Supersingular curves over finite fields and weight divisibility of codes. J. Comput. Appl. Math. 259, part B, 474-84 (2014)View Article
  16.Huard, J.G., Spearman, B.K., Williams, K.: Pascal triangle (mod 8). Europ. J. Comb. 19, 45-1 (1998)MathSciNet View Article
  17.Gao, G-P., Liu, W-F, Zhang, X-Y.: The degree of balanced elementary symmetric Boolean functions of 4k+3 variables. IEEE Trans. Inf. Theory 57, 4822-825 (2011)MathSciNet View Article
  18.Kolountzakis, M., Lipton, R.J., Markakis, E., Metha, A., Vishnoi, N.K.: On the fourier spectrum of symmetric Boolean functions. Combinatorica 29, 363-87 (2009)MathSciNet View Article
  19.Moreno, O., Castro, F.: Divisibility properties for covering radius of certain cyclic codes. IEEE Trans. Inform. Theory 49 (12), 3299-303 (2003)MathSciNet View Article
  20.Moreno, O., Moreno, C.J.: Improvement of the Chevalley-warning and the Ax-Katz theorems. Amer. J. Math 117, 241-44 (1995)MathSciNet View Article
  21.Moreno, O., Moreno, C.J.: The MacWilliams-Sloane conjecture on the tightness of the Carlitz-Uchiyama bound and the weights of dual of BCH codes. IEEE Trans. Inform. Theory 40, 1894-907 (1994)MathSciNet View Article
  22.Moreno, O., Shum, K., Castro, F.N., Kumar, P.V.: Tight bounds for Chevalley-Warning-Ax type estimates, with improved applications. Proc. London Math. Soc. 88, 545-64 (2004)MathSciNet View Article
  23.Shpilka, A., Tal, A.: On the minimal fourier degree of symmetric Boolean functions. Combinatorica 88, 359-77 (2014)MathSciNet View Article
  24.von zur Gathem, J., Roche, J.R.: Polynomial with two values. Combinatorica 17, 345-62 (1997)MathSciNet View Article
  25.Wei, S., Tang, X., Pott, A.: A note on a conjecture for balanced elementary symmetric Boolean functions. IEEE Trans. Inf. Theory 59, 665-71 (2013)View Article
  
• 作者单位：Francis N. Castro (1)
  Oscar E. González (1)
  Luis A. Medina (1)
  
  1. Department of Mathematics, University of Puerto Rico, Box 70377, 00931-3355, San Juan, Puerto Rico
  
• 刊物类别：Computer Science
• 刊物主题：Coding and Information Theory
  Mathematics of Computing
  
• 出版者：Springer New York
• ISSN：1936-2455

文摘

In this paper we compute the exact 2-divisibility of exponential sums associated to elementary symmetric Boolean functions. Our computation gives an affirmative answer to most of the open boundary cases of Cusick-Li-Stǎnicǎ’s conjecture. As a byproduct, we prove that the 2-divisibility of these families satisfies a linear recurrence. In particular, we provide a new elementary method to compute 2-divisibility of symmetric Boolean functions.