On perfect 2-colorings of the Q-ary hypercube.pdf Обозначим через Zq множество { 0 , . . . , q_ 1}. Декартово произведение Z^1 называет-ся q-значным n-мерным кубом (гиперкубом). Функция f : Z^1 ^ Zq называется корре-ляционно-иммунной порядка n _ m, если мощность пересечения грани размерности mс множеством f - 1 ( a ) зависит только от a G Zq. Через cor(f) будем обозначать мак-симальный порядок корреляционной иммунности. Плотностью булевозначной функ-ции XS будем называть отношение p(S) = |S|/qn. Если p(S) = 1/2, то булевозначнуюкорреляционно-иммунную функцию XS называют уравновешенной.Расстоянием Хэмминга d(x,y) между вершинами x = (x1, x 2 , . . . , xn) и y = (y1,y2,... , yn) называется число позиций, в которых наборы x и y различаются. Определимвеличину A(S) как среднее число вершин из S С Zq1, которые находятся на расстоя-нии 1 от вершины из дополнения Zq1 \ S, т. е. A(S) = -- |{y G S : d(x, y) = 1}|.q n -I S 1Отображение col : Zq1 ^ { 0 , . . . , k} называется совершенной раскраской с матрицейпараметров M = {mij}, если для любых i и j, для каждой вершины цвета i число со-седей цвета j равняется mij. В дальнейшем рассматриваются только раскраски в двацвета (2-раскраски). Будем считать, что {0,1} -множество цветов. В этом случае бу-левозначная функция col является характеристической функцией множества вершинцвета 1.Совершенный код (исправляющий одну ошибку) C С Zq1 можно рас-сматривать как множество единиц совершенной 2-раскраски с матрицей параметровы ( n(q - 1) - 1 М ^M = 1 ^(q 1) о J . Если число q является степенью простого числа, то рас-краска с такими параметрами существует только при n = (qj - 1)/(q - 1). При q = 2список известных параметров совершенных 2-раскрасок имеется в [1, 2].Известно (см., например, [3, 4]), что совершенная раскраска булева n-куба с мат-/ n -рицей параметров I I является корреляционно-иммунной функцией по-рядка (b + c)/2 - 1, т. е. из регулярной распределённости вершин некоторого множествапо шарам радиуса 1 следует равномерное распределение вершин этого множества пограням. Весьма интересным представляется выяснение возможности обратного след-ствия.В [5] доказано, что если для некоторого множества S С Z^ величины cor(xS) иp(S) совпадают с соответствующими параметрами для совершенного кода, то множе-ство S является совершенным кодом. В [3] установлено, что неуравновешенная булевафункция f = (S С Zn) удовлетворяет неравенству cor(f) ^ 2n/3 - 1. Кроме того,в случае равенства cor(f) = 2n/3 - 1 функция f является совершенной раскраской.Подобным образом, если для множества S С Zn неравенство Биербрауэра мана (см. [6, 7]) превращается в равенство p(S) 2= 1 n2 ( c o r-( f ) + 1) , то фун -кц Фияр ид-является совершенной 2-раскраской [8].Оказывается, имеет место следующий критерий.Теорема 1.а) Для каждой булевозначной функции f = , где S С Zq1, справедливо неравен-ство p(S)q(cor(f) + 1) ^ A(S).б) Булевозначная функция f = является совершенной 2-раскраской тогда итолько тогда, когда p(S)q(cor(f) + 1) = A(S).Таким образом, равномерное распределение вершин множества по граням гипер-куба при экстремальных условиях на плотность множества влечёт регулярное рас-пределение вершин множества по шарам. Более того, любая совершенная 2-раскраскаполучается как максимально равномерно распределённая по граням булевозначнаяфункция при некоторых дополнительных односторонних ограничениях на размеще-ние её единиц. При доказательстве теоремы использовались методы, развитые в [7].

Скачать электронную версию публикации