Article Contents
Article Contents

# On the number of bent functions from iterative constructions: lower bounds and hypotheses

• In the paper we study lower bounds on the number of bent functions that can be obtained by iterative constructions, namely by the construction proposed by A. Canteaut and P. Charpin in 2003. The number of bent iterative functions is expressed in terms of sizes of finite sets and it is shown that evaluation of this number is closely connected to the problem of decomposing Boolean function into sum of two bent functions. A new lower bound for the number of bent iterative functions that is supposed to be asymptotically tight is given. Applying Monte-Carlo methods the number of bent iterative functions in $8$ variables is counted. Based on the performed calculations several hypotheses on the asymptotic value of the number of all bent functions are formulated.
Mathematics Subject Classification: Primary: 06E30; Secondary: 94A60.

 Citation:

•  [1] S. V. Agievich, On the representation of bent functions by bent rectangles, in "Proc. of the Int. Petrozavodsk Conf. on Probabilistic Methods in Discrete Mathematics,'' (2000), 121-135; preprint, arXiv:math/0502087v1 [2] A. Canteaut and P. Charpin, Decomposing bent functions, IEEE Trans. Inform. Theory, 49 (2003), 2004-2019.doi: 10.1109/TIT.2003.814476. [3] A. Canteaut, M. Daum, H. Dobbertin and G. Leander, Finding nonnormal bent functions, Discrete Appl. Math., 154 (2006), 202-218.doi: 10.1016/j.dam.2005.03.027. [4] C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebraic immunities, in "Applied Algebra, Algebraic Algorithms and Error Correcting Codes,'' Las Vegas, USA, (2006), 1-28. [5] C. Carlet and A. Klapper, Upper bounds on the numbers of resilient functions and of bent functions, in "Proc. of 23rd Symposium on Information Theory,'' (2002), 307-314. [6] J.-J. Climent, F. García and V. Requena, On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables, Adv. Math. Commun., 2 (2008), 421-431.doi: 10.3934/amc.2008.2.421. [7] J. F. Dillon, "Elementary Hadamard Difference Sets,'' Ph.D Thesis, University of Maryland, 1974. [8] V. E. Gmurman, "Probability Theory and Mathematical Statistics,'' Higher Educ., Moscow, 2006. [9] P. Langevin, G. Leander, Counting all bent functions in dimension eight 99270589265934370305785861242880, Des. Codes Crypt., 59 (2011), 193-205. [10] R. L. McFarland, A family of difference sets in non-cyclic groups, J. Combin. Theory Ser. A, 15 (1973), 1-10.doi: 10.1016/0097-3165(73)90031-9. [11] O. Rothaus, On bent functions, IDA CRD W. P. No. 169, 1966. [12] O. Rothaus, On bent functions, J. Combin. Theory Ser. A, 20 (1976), 300-305.doi: 10.1016/0097-3165(76)90024-8. [13] N. N. Tokareva, Automorphism group of the set of all bent functions, Discrete Math. Appl., 20 (2010), 655-664.doi: 10.1515/DMA.2010.040. [14] N. N. Tokareva, Generalizations of bent functions. A survey, Discrete Anal. Oper. Res., 17 (2010), 34-64. [15] N. Tokareva, "Nonlinear Boolean Functions: Bent Functions and Their Generalizations,'' LAP LAMBERT Academic Publishing, Saarbrucken, Germany, 2011. [16] L. Wang and J. Zhang, A best possible computable upper bound on bent functions, J. West China, 33 (2004), 113-115.