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

Previous Article
Explicit formulas for real hyperelliptic curves of genus 2 in affine representation
AMC Home
This Issue
Next Article
The merit factor of binary arrays derived from the quadratic character

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

Abstract
Related Papers

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

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

[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, 2021, 15 (4) : 721-736. 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 and 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]	Zhiyan Ding, Qin Li. Constrained Ensemble Langevin Monte Carlo. Foundations of Data Science, 2022, 4 (1) : 37-70. doi: 10.3934/fods.2021034
[8]	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
[9]	Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic and Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291
[10]	Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems and Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81
[11]	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
[12]	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
[13]	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
[14]	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
[15]	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
[16]	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
[17]	Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335
[18]	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
[19]	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
[20]	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

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Natalia Tokareva
on Google Scholar
Natalia Tokareva

[Back to Top]