American Institute of Mathematical Sciences

Advanced
November  2011, 5(4): 609-621. doi: 10.3934/amc.2011.5.609

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

Natalia Tokareva 1,

1. 

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, pr. Koptyuga 4, 630090, Novosibirsk, Russian Federation, and Novosibirsk State University, st. Pirogova 2, 630090, Novosibirsk, Russian Federation

Received  July 2010 Revised  August 2011 Published  November 2011

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.
Keywords: bent sum decomposition, iterative construction, asymptotic value, Monte–Carlo methods., Bent function.
Mathematics Subject Classification: Primary: 06E30; Secondary: 94A6.
Citation: Natalia Tokareva. On the number of bent functions from iterative constructions: lower bounds and hypotheses. Advances in Mathematics of Communications, 2011, 5 (4) : 609-621. doi: 10.3934/amc.2011.5.609
References:
[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 Google Scholar

[2]

A. Canteaut and P. Charpin, Decomposing bent functions, IEEE Trans. Inform. Theory, 49 (2003), 2004-2019. doi: 10.1109/TIT.2003.814476.  Google Scholar

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

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

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

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

[7]

J. F. Dillon, "Elementary Hadamard Difference Sets,'' Ph.D Thesis, University of Maryland, 1974.  Google Scholar

[8]

V. E. Gmurman, "Probability Theory and Mathematical Statistics,'' Higher Educ., Moscow, 2006. Google Scholar

[9]

P. Langevin, G. Leander, Counting all bent functions in dimension eight 99270589265934370305785861242880, Des. Codes Crypt., 59 (2011), 193-205.  Google Scholar

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

[11]

O. Rothaus, On bent functions, IDA CRD W. P. No. 169, 1966.  Google Scholar

[12]

O. Rothaus, On bent functions, J. Combin. Theory Ser. A, 20 (1976), 300-305. doi: 10.1016/0097-3165(76)90024-8.  Google Scholar

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

[14]

N. N. Tokareva, Generalizations of bent functions. A survey, Discrete Anal. Oper. Res., 17 (2010), 34-64.  Google Scholar

[15]

N. Tokareva, "Nonlinear Boolean Functions: Bent Functions and Their Generalizations,'' LAP LAMBERT Academic Publishing, Saarbrucken, Germany, 2011. Google Scholar

[16]

L. Wang and J. Zhang, A best possible computable upper bound on bent functions, J. West China, 33 (2004), 113-115.  Google Scholar

show all references

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

[2]

A. Canteaut and P. Charpin, Decomposing bent functions, IEEE Trans. Inform. Theory, 49 (2003), 2004-2019. doi: 10.1109/TIT.2003.814476.  Google Scholar

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

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

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

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

[7]

J. F. Dillon, "Elementary Hadamard Difference Sets,'' Ph.D Thesis, University of Maryland, 1974.  Google Scholar

[8]

V. E. Gmurman, "Probability Theory and Mathematical Statistics,'' Higher Educ., Moscow, 2006. Google Scholar

[9]

P. Langevin, G. Leander, Counting all bent functions in dimension eight 99270589265934370305785861242880, Des. Codes Crypt., 59 (2011), 193-205.  Google Scholar

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

[11]

O. Rothaus, On bent functions, IDA CRD W. P. No. 169, 1966.  Google Scholar

[12]

O. Rothaus, On bent functions, J. Combin. Theory Ser. A, 20 (1976), 300-305. doi: 10.1016/0097-3165(76)90024-8.  Google Scholar

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

[14]

N. N. Tokareva, Generalizations of bent functions. A survey, Discrete Anal. Oper. Res., 17 (2010), 34-64.  Google Scholar

[15]

N. Tokareva, "Nonlinear Boolean Functions: Bent Functions and Their Generalizations,'' LAP LAMBERT Academic Publishing, Saarbrucken, Germany, 2011. Google Scholar

[16]

L. Wang and J. Zhang, A best possible computable upper bound on bent functions, J. West China, 33 (2004), 113-115.  Google Scholar

[1]

Sihem Mesnager, Fengrong Zhang, Yong Zhou. On construction of bent functions involving symmetric functions and their duals. Advances in Mathematics of Communications, 2017, 11 (2) : 347-352. doi: 10.3934/amc.2017027
[2]

Junchao Zhou, Nian Li, Xiangyong Zeng, Yunge Xu. A generic construction of rotation symmetric bent functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020092
[3]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052
[4]

Joan-Josep Climent, Francisco J. García, Verónica Requena. On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables. Advances in Mathematics of Communications, 2008, 2 (4) : 421-431. doi: 10.3934/amc.2008.2.421
[5]

Sihong Su. A new construction of rotation symmetric bent functions with maximal algebraic degree. Advances in Mathematics of Communications, 2019, 13 (2) : 253-265. doi: 10.3934/amc.2019017
[6]

Wenying Zhang, Zhaohui Xing, Keqin Feng. A construction of bent functions with optimal algebraic degree and large symmetric group. Advances in Mathematics of Communications, 2020, 14 (1) : 23-33. doi: 10.3934/amc.2020003
[7]

Jacques Wolfmann. Special bent and near-bent functions. Advances in Mathematics of Communications, 2014, 8 (1) : 21-33. doi: 10.3934/amc.2014.8.21
[8]

Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic & Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291
[9]

Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems & Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81
[10]

Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004
[11]

Theodore Papamarkou, Alexey Lindo, Eric B. Ford. Geometric adaptive Monte Carlo in random environment. Foundations of Data Science, 2021, 3 (2) : 201-224. doi: 10.3934/fods.2021014
[12]

Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041
[13]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069
[14]

Claude Carlet, Fengrong Zhang, Yupu Hu. Secondary constructions of bent functions and their enforcement. Advances in Mathematics of Communications, 2012, 6 (3) : 305-314. doi: 10.3934/amc.2012.6.305
[15]

Sihem Mesnager, Fengrong Zhang. On constructions of bent, semi-bent and five valued spectrum functions from old bent functions. Advances in Mathematics of Communications, 2017, 11 (2) : 339-345. doi: 10.3934/amc.2017026
[16]

Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335
[17]

Jiakou Wang, Margaret J. Slattery, Meghan Henty Hoskins, Shile Liang, Cheng Dong, Qiang Du. Monte carlo simulation of heterotypic cell aggregation in nonlinear shear flow. Mathematical Biosciences & Engineering, 2006, 3 (4) : 683-696. doi: 10.3934/mbe.2006.3.683
[18]

Samir Hodžić, Enes Pasalic. Generalized bent functions -sufficient conditions and related constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 549-566. doi: 10.3934/amc.2017043
[19]

Claude Carlet, Juan Carlos Ku-Cauich, Horacio Tapia-Recillas. Bent functions on a Galois ring and systematic authentication codes. Advances in Mathematics of Communications, 2012, 6 (2) : 249-258. doi: 10.3934/amc.2012.6.249
[20]

Ayça Çeşmelioǧlu, Wilfried Meidl, Alexander Pott. On the dual of (non)-weakly regular bent functions and self-dual bent functions. Advances in Mathematics of Communications, 2013, 7 (4) : 425-440. doi: 10.3934/amc.2013.7.425

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (58)
  • HTML views (0)
  • Cited by (20)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences