English version:
Journal of Applied and Industrial Mathematics, 2016, 10:3, 397-403

Volume 23, No 3, 2016, P. 93-106

UDC 519.7
A. K. Oblaukhov
Metric complements to subspaces in the Boolean cube

We study the metric complements to sets in the Boolean cube; i. e. the subsets maximally distant from given subset. We obtain the general form for the metric complement of a linear subspace and some more exact description for the class of subspaces with basis of a special form. It is proved that the completely regular codes (including perfect and uniformly packed) are metrically regular.
Bibliogr. 9.

Keywords: subspace, metrically regular set, metric complement, completely regular code, bent-function.

DOI: 10.17377/daio.2016.23.513

Alexey K. Oblaukhov 1
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: oblaukhov@gmail.com

Received 22 September 2015
Revised 9 March 2016


[1] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977 (North-Holland Math. Libr., Vol. 16). Translated under the title Teoriya kodov, ispravlyayushchikh oshibki, Svyaz’, Moscow, 1979.

[2] C. Carlet, Lower bounds on the higher order nonlinearities of Boolean functions and their applications to the inverse function, in Proc. 2008 IEEE Inf. Theory Workshop, Porto, Portugal, May 5–9, 2008, pp. 333–337, IEEE, Piscataway, 2008.

[3] S. Kavut, S. Maitra, and M. D. Yucel, Search for Boolean functions with excellent profiles in the rotation symmetric class, IEEE Trans. Inf. Theory, 53, No. 5, 1743–1751, 2007.

[4] S. Maitra and P. Sarkar, Maximum nonlinearity of symmetric Boolean functions on odd number of variables, IEEE Trans. Inf. Theory, 48, No. 9, 2626–2630, 2002.

[5] A. Neumaier, Completely regular codes, Discrete Math., 106, 353–360, 1992.

[6] O. S. Rothaus, On “bent” functions, J. Comb. Theory, Ser. A, 20, No. 3, 300–305, 1976.

[7] G. Sun and C. Wu, The lower bound on the second-order nonlinearity of a class of Boolean functions with high nonlinearity, Appl. Algebra Eng. Commun. Comput., 22, No. 1, 37–45, 2011.

[8] N. N. Tokareva, Duality between bent functions and affine functions, Discrete Math., 312, No. 3, 666–670, 2012.

[9] N. N. Tokareva, Bent Functions: Results and Applications to Cryptography, Academic Press, San Diego, 2015.
 © Sobolev Institute of Mathematics, 2015