# American Institute of Mathematical Sciences

November  2020, 14(4): 651-676. doi: 10.3934/amc.2020036

## Three parameters of Boolean functions related to their constancy on affine spaces

 1 LAGA, Department of Mathematics, University of Paris 8 (and Paris 13 and CNRS), Saint–Denis cedex 02, France and University of Bergen, Norway 2 University of Yaoundé 1, Faculty of Sciences, Department of Mathematics, P.O.BOX 812 Yaoundé, Cameroon

* The work of this author was partially supported by PRMAIS

Received  November 2018 Revised  July 2019 Published  November 2019

The $k$-normality of Boolean functions is an important notion initially introduced by Dobbertin and studied in several papers. The parameter related to this notion is the maximal dimension of those affine spaces contained in the support $supp(f)$ of the function or in its co-support $cosupp(f)$. We denote it by $norm\,(f)$ and call it the norm of $f$.

The norm concerns only the affine spaces contained in either the support or the co-support; the information it provides on $f$ is then somewhat incomplete (for instance, two functions constant on a hyperplane will have the same very large parameter value, while they can have very different complexities). A second parameter which completes the information given by the first one is the minimum between the maximal dimension of those affine spaces contained in $supp(f)$ and the maximal dimension of those contained in $cosupp(f)$ (while $norm\,(f)$ equals the maximum between these two maximal dimensions). We denote it by $cons\,(f)$ and call it the (affine) constancy of $f$.

The value of $cons\,(f)$ gives global information on $f$, but no information on what happens around each point of $supp(f)$ or $cosupp(f)$. We define then its local version, equal to the minimum, when $a$ ranges over $\Bbb{F}_2^n$, of the maximal dimension of those affine spaces which contain $a$ and on which $f$ is constant. We denote it by $stab\,(f)$ and call it the stability of $f$.

We study the properties of these three parameters. We have $norm\,(f)\geq cons\,(f)\geq stab\,(f)$, then for determining to which extent these three parameters are distinct, we exhibit four infinite classes of Boolean functions, which show that all cases can occur, where each of these two inequalities can be strict or large.

We consider the minimal value of $stab\, (f)$ (resp. $cons\,(f)$, $norm\,(f)$), when $f$ ranges over the Reed-Muller code $RM(r,n)$ of length $2^n$ and order $r$, and we denote it by $stab\, _{RM(r,n)}$ (resp. $cons\, _{RM(r,n)}$, $norm\, _{RM(r,n)}$). We give upper bounds for each of these three integer sequences, and determine the exact values of $stab\, _{RM(r,n)}$ and $cons\, _{RM(r,n)}$ for $r\in\{1,2,n-2,n-1,n\}$, and of $norm\, _{RM(r,n)}$ for $r = 1,2$.

Citation: Claude Carlet, Serge Feukoua. Three parameters of Boolean functions related to their constancy on affine spaces. Advances in Mathematics of Communications, 2020, 14 (4) : 651-676. doi: 10.3934/amc.2020036
##### References:
 [1] E. F. Assmus Jr., On the Reed-Muller codes, Discrete Math., 106-107 (1992), 25-33.  doi: 10.1016/0012-365X(92)90526-L.  Google Scholar [2] J. Boyar and M. G. Find, Constructive relationships between algebraic thickness and normality, in Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., 9210, Springer, Cham, 2015,106–117. doi: 10.1007/978-3-319-22177-9_9.  Google Scholar [3] A. Canteaut, C. Carlet, P. Charpin and C. Fontaine, On cryptographic properties of the cosets of $R(1, m)$, IEEE Trans. Inform. Theory, 47 (2001), 1494-1513.  doi: 10.1109/18.923730.  Google Scholar [4] A. Canteaut, M. Daum, H. Dobbertin and G. Leander, Normal and non-normal bent functions, Proceedings of the Workshop on Coding and Cryptography, 2003, 91–100. Google Scholar [5] C. Carlet, Two new classes of bent functions, in Advances in Cryptology, Lecture Notes in Comput. Sci., 765, Springer, Berlin, 1994, 77–101. doi: 10.1007/3-540-48285-7_8.  Google Scholar [6] C. Carlet, On cryptographic complexity of Boolean functions, Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Springer, Berlin, 2002, 53–69. doi: 10.1007/978-3-642-59435-9_4.  Google Scholar [7] C. Carlet, Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications, IEEE Trans. Inform. Theory, 54 (2008), 1262-1272.  doi: 10.1109/TIT.2007.915704.  Google Scholar [8] C. Carlet, Boolean functions for cryptography and error-correcting codes, in Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge University Press, 2010, 257-397. Preliminary version available at: http://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf. doi: 10.1017/CBO9780511780448.011.  Google Scholar [9] C. Carlet, Boolean and vectorial plateaued functions, and APN functions, IEEE Trans. Inform. Theory, 61 (2015), 6272-6289.  doi: 10.1109/TIT.2015.2481384.  Google Scholar [10] C. Carlet and S. Feukoua, Three basic questions on Booleans functions, Adv. Math. Commun., 11 (2017), 837-855.  doi: 10.3934/amc.2017061.  Google Scholar [11] C. Carlet and S. Mesnager, Four decades of research on bent functions, Des. Codes Cryptogr., 78 (2016), 5-50.  doi: 10.1007/s10623-015-0145-8.  Google Scholar [12] P. Charpin, Normal Boolean functions, J. Complexity, 20 (2004), 245-265.  doi: 10.1016/j.jco.2003.08.010.  Google Scholar [13] G. Cohen and A. Tal, Two structural results for low degree polynomials and applications, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Leibniz Int. Proc. Inform., 40, Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, 2015,680–709.  Google Scholar [14] J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D thesis, University of Maryland in College Park, 1974.  Google Scholar [15] H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in Fast Software Encryption, Lecture Notes in Comput. Sci., 1008, Springer, Berlin, 1995, 61–74. doi: 10.1007/3-540-60590-8_5.  Google Scholar [16] R. E. Jamison, Covering finite field with cosets of subspaces, J. Combinatorial Theory Ser. A, 22 (1977), 253-266.  doi: 10.1016/0097-3165(77)90001-2.  Google Scholar [17] T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes, IEEE Trans. Information Theory, 16 (1970), 752-759.  doi: 10.1109/tit.1970.1054545.  Google Scholar [18] A. Logachev, V. Yashchenko and M. Denisenko, Local affinity of Boolean mappings, in Boolean Functions in Cryptology and Information Security, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., 18, IOS, Amsterdam, 2008,148–172.  Google Scholar [19] F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar [20] R. L. McFarland., A family of difference sets in non-cyclic groups, J. Combinatorial Theory Ser. A, 15 (1973), 1-10.  doi: 10.1016/0097-3165(73)90031-9.  Google Scholar [21] J. C. C. McKinsey, On Boolean Functions of Many Variables, Ph.D thesis, University of California in Berkeley, 1936.  Google Scholar [22] S. Mesnager, Bent Functions: Fundamentals and Results, Springer, Cham, 2016. doi: 10.1007/978-3-319-32595-8.  Google Scholar [23] O. S. Rothaus, On "bent" functions, J. Combinatorial Theory Ser. A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar [24] Zheng and Zhang, Maiorana-McFarland construction of plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215-1223.   Google Scholar

show all references

##### References:
 [1] E. F. Assmus Jr., On the Reed-Muller codes, Discrete Math., 106-107 (1992), 25-33.  doi: 10.1016/0012-365X(92)90526-L.  Google Scholar [2] J. Boyar and M. G. Find, Constructive relationships between algebraic thickness and normality, in Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., 9210, Springer, Cham, 2015,106–117. doi: 10.1007/978-3-319-22177-9_9.  Google Scholar [3] A. Canteaut, C. Carlet, P. Charpin and C. Fontaine, On cryptographic properties of the cosets of $R(1, m)$, IEEE Trans. Inform. Theory, 47 (2001), 1494-1513.  doi: 10.1109/18.923730.  Google Scholar [4] A. Canteaut, M. Daum, H. Dobbertin and G. Leander, Normal and non-normal bent functions, Proceedings of the Workshop on Coding and Cryptography, 2003, 91–100. Google Scholar [5] C. Carlet, Two new classes of bent functions, in Advances in Cryptology, Lecture Notes in Comput. Sci., 765, Springer, Berlin, 1994, 77–101. doi: 10.1007/3-540-48285-7_8.  Google Scholar [6] C. Carlet, On cryptographic complexity of Boolean functions, Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Springer, Berlin, 2002, 53–69. doi: 10.1007/978-3-642-59435-9_4.  Google Scholar [7] C. Carlet, Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications, IEEE Trans. Inform. Theory, 54 (2008), 1262-1272.  doi: 10.1109/TIT.2007.915704.  Google Scholar [8] C. Carlet, Boolean functions for cryptography and error-correcting codes, in Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge University Press, 2010, 257-397. Preliminary version available at: http://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf. doi: 10.1017/CBO9780511780448.011.  Google Scholar [9] C. Carlet, Boolean and vectorial plateaued functions, and APN functions, IEEE Trans. Inform. Theory, 61 (2015), 6272-6289.  doi: 10.1109/TIT.2015.2481384.  Google Scholar [10] C. Carlet and S. Feukoua, Three basic questions on Booleans functions, Adv. Math. Commun., 11 (2017), 837-855.  doi: 10.3934/amc.2017061.  Google Scholar [11] C. Carlet and S. Mesnager, Four decades of research on bent functions, Des. Codes Cryptogr., 78 (2016), 5-50.  doi: 10.1007/s10623-015-0145-8.  Google Scholar [12] P. Charpin, Normal Boolean functions, J. Complexity, 20 (2004), 245-265.  doi: 10.1016/j.jco.2003.08.010.  Google Scholar [13] G. Cohen and A. Tal, Two structural results for low degree polynomials and applications, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Leibniz Int. Proc. Inform., 40, Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, 2015,680–709.  Google Scholar [14] J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D thesis, University of Maryland in College Park, 1974.  Google Scholar [15] H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in Fast Software Encryption, Lecture Notes in Comput. Sci., 1008, Springer, Berlin, 1995, 61–74. doi: 10.1007/3-540-60590-8_5.  Google Scholar [16] R. E. Jamison, Covering finite field with cosets of subspaces, J. Combinatorial Theory Ser. A, 22 (1977), 253-266.  doi: 10.1016/0097-3165(77)90001-2.  Google Scholar [17] T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes, IEEE Trans. Information Theory, 16 (1970), 752-759.  doi: 10.1109/tit.1970.1054545.  Google Scholar [18] A. Logachev, V. Yashchenko and M. Denisenko, Local affinity of Boolean mappings, in Boolean Functions in Cryptology and Information Security, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., 18, IOS, Amsterdam, 2008,148–172.  Google Scholar [19] F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar [20] R. L. McFarland., A family of difference sets in non-cyclic groups, J. Combinatorial Theory Ser. A, 15 (1973), 1-10.  doi: 10.1016/0097-3165(73)90031-9.  Google Scholar [21] J. C. C. McKinsey, On Boolean Functions of Many Variables, Ph.D thesis, University of California in Berkeley, 1936.  Google Scholar [22] S. Mesnager, Bent Functions: Fundamentals and Results, Springer, Cham, 2016. doi: 10.1007/978-3-319-32595-8.  Google Scholar [23] O. S. Rothaus, On "bent" functions, J. Combinatorial Theory Ser. A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar [24] Zheng and Zhang, Maiorana-McFarland construction of plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215-1223.   Google Scholar
 [1] 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 [2] Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $U_2$ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056 [3] Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $\mathbb{Z}_{4}$. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020121 [4] Ferenc Weisz. Dual spaces of mixed-norm martingale hardy spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020285 [5] Andreas Koutsogiannis. Multiple ergodic averages for tempered functions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1177-1205. doi: 10.3934/dcds.2020314 [6] Alessandro Carbotti, Giovanni E. Comi. A note on Riemann-Liouville fractional Sobolev spaces. Communications on Pure & Applied Analysis, 2021, 20 (1) : 17-54. doi: 10.3934/cpaa.2020255 [7] Giulia Cavagnari, Antonio Marigonda. Attainability property for a probabilistic target in wasserstein spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 777-812. doi: 10.3934/dcds.2020300 [8] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [9] Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098 [10] Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006 [11] Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378 [12] Federico Rodriguez Hertz, Zhiren Wang. On $\epsilon$-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365 [13] Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250 [14] Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049 [15] Giulia Luise, Giuseppe Savaré. Contraction and regularizing properties of heat flows in metric measure spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 273-297. doi: 10.3934/dcdss.2020327 [16] Dmitry Dolgopyat. The work of Sébastien Gouëzel on limit theorems and on weighted Banach spaces. Journal of Modern Dynamics, 2020, 16: 351-371. doi: 10.3934/jmd.2020014 [17] Anna Anop, Robert Denk, Aleksandr Murach. Elliptic problems with rough boundary data in generalized Sobolev spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020286 [18] 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 [19] Haruki Umakoshi. A semilinear heat equation with initial data in negative Sobolev spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 745-767. doi: 10.3934/dcdss.2020365 [20] Lin Shi, Dingshi Li, Kening Lu. Limiting behavior of unstable manifolds for spdes in varying phase spaces. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021020

2019 Impact Factor: 0.734

## Tools

Article outline

Figures and Tables