zbMATH — the first resource for mathematics

A lower bound on the size of the largest metrically regular subset of the Boolean cube. (English) Zbl 1456.94102
Summary: Let \(A\) be an arbitrary subset of the Boolean cube, and \(\widehat {A}\) be the set of all vectors of the Boolean cube, which are at the maximal possible distance from the set \(A\). If the set of all vectors at the maximal distance from \(\widehat {A}\) coincides with \(A\), then the set \(A\) is called a metrically regular set. The problem of investigating metrically regular sets appears when studying bent functions, which have important applications in cryptography and coding theory. In this work a special subclass of strongly metrically regular subsets of the Boolean cube is studied. An iterative construction of strongly metrically regular sets is obtained. The formula for the number of sets which can be obtained via this construction is derived. Constructions for two families of large metrically regular sets are presented. Exact sizes of sets from these families are calculated. These sizes give us the best lower bound on sizes of largest metrically regular subsets of the Boolean cube.

94A60 Cryptography
94D10 Boolean functions
68R01 General topics of discrete mathematics in relation to computer science
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Oblaukhov, AK, Metric complements to subspaces in the Boolean cube, J. Appl. Ind. Math., 10, 397-403, (2016) · Zbl 1374.94798
[2] Tokareva, N., Duality between bent functions and affine functions, Discret. Math., 312, 666-670, (2012) · Zbl 1234.94068
[3] Tokareva, N.: Bent Functions: Results and Applications to Cryptography. Academic Press, New York (2015) · Zbl 1372.94002
[4] Rothaus, O., On bent functions, Journal of Combinatorial Theory, Series A, 20, 300-305, (1976) · Zbl 0336.12012
[5] Cohen, G.; etal., Covering codes, Elsevier, 54, 1-541, (1997)
[6] Tokareva, N., Gorodilova, A., Agievich, S., Idrisova, V., Kolomeec, N., Kutsenko, A., Oblaukhov, A., Shushuev, G.: Mathematical methods in solutions of the problems from the third international students’ olympiad in cryptography. arXiv:1710.05873
[7] Neumaier, A., Completely regular codes, Discret. Math., 106, 353-360, (1992) · Zbl 0754.94010
[8] Henry, W.: Gould Combinatorial Identities. Morgantown Printing and Binding Co., Morgantown (1972)
[9] Stanica, P., Sasao, T., Butler, J.T.: Distance Duality on Some Classes of Boolean Functions. Accepted in Journal of Combinatorial Mathematics and Combinatorial Computing · Zbl 1432.94228
[10] Cusick, T.W., Stanica, P.: Cryptographic Boolean Functions and Applications. Academic Press, New York (2017) · Zbl 1359.94001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.