О рангах подмножеств пространства двоичных векторов, допускающих встраивание системы Штейнера S(2, 4, v) | ПДМ. 2014. № 1(23).

О рангах подмножеств пространства двоичных векторов, допускающих встраивание системы Штейнера S(2, 4, v)

Получена оценка ранга подмножества X пространства Fn через радиус покрытия кода, лежащего в подпространстве линейных зависимостей векторов из X. Получена верхняя оценка радиуса покрытия кода, порождённого матрицей инцидентности системы Штейнера S(2, 4,v). Получены верхняя точная и асимптотическая оценки ранга подмножества X пространства Fn, допускающего встраивание системы Штейнера S(2,4,v).

On ranks of subsets in the space of binary vectors admitting an embedding of a Steiner system S(2, 4, v).pdf Пусть X С Fn. Рангом множества X называется размерность dim(X) его линейной оболочки (X). Аффинным рангом множества X называется наименьшая размерность класса смежности линейного подпространства в Fn, содержащего X. Пусть их - взаимно-однозначное отображение векторов из X в компоненты пространства F2X|. Отображение их индуцирует взаимно-однозначное сопоставление каждому подмножеству I XI A С X характеристического вектора a = (ai,..., a|X|) = £х(A) в F2 |, такого, что ai = 1, если uX2(i) Е A, и ai = 0, если uXi(i) Е A, i = 1,..., |X|. Пусть BX = = {Bi,...,Bs} - совокупность всех таких подмножеств Bi = {x*1 ,... , xik;} множе-ki ства X, что Y1 xij = (0,... , 0). Тогда множество векторов £х(BX) = {£X(B1), ... , £X(Bs)}, j=i |X| очевидно, является линейным подпространством в F2 . Лемма 1. Имеет место равенство dim(X) = |X| - dim£X(BX). Доказательство леммы 1 практически очевидно, потому что если dim £х (Bx) = r, то в X найдется подмножество X' из |X| - r линейно независимых векторов, а все векторы из X \ X' могут быть выражены как линейные комбинации векторов из X'. Из леммы 1 получаем Следствие 1. Пусть C С £х (BX). Тогда dim(X) ^ |X| - dim(C). Произвольное множество C, C С Fm, называется кодом. Если C - линейное пространство в Fm, то C называется линейным кодом. Расстоянием (Хэмминга) d(a, b) между векторами a и b из Fm называется число компонент, в которых a и b различаются. Радиусом покрытия R = R(C) кода C, C С Fm, называется величина R = R(C) = maxmind(a,b). Радиусу покрытия и связанным с ним вопросам теоa&FV? b€C рии кодирования посвящена монография [1]. Из определения радиуса покрытия сразу следует, что мощность кода C, C С Fm, оценивается через его радиус покрытия R(C) как R(C) / m \ |C | ^ 2m/£ ( .). i=0 i Отсюда, если C - линейный код, то R(C) m dim C ^ m - Iog2 ( • ) . 2 i=0 i Из (1) и следствия 1 получаем следующую теорему. Теорема 1. Пусть C С (BX). Тогда R«C» (|X| dim(X) ^ log^ 1 1 1 i=0 Системой Штейнера S(t, k, v) называется пара (V, B), где V - множество мощности V, а B - семейство k-элементных подмножеств V, называемых блоками, таких, что любое t-элементное подмножество V целиком принадлежит ровно одному блоку. Будем говорить, что пара (V, B), являющаяся системой Штейнера S(t, k, v), встраивается во множество X, X С Fn, если существует биекция ^ : V ^ X, такая, что для любого блока B, B G B, выполнено соотношение У]

Ключевые слова

ранг, аффинный ранг, оценки, линейное подпространство, линейный код, радиус покрытия, система Штейнера, булевы функции, носитель спектра, rank, affine rank, bounds, linear subspace, linear code, covering radius, Steiner system, Boolean functions, spectrum support

Авторы

ФИООрганизацияДополнительноE-mail
Таранников Юрий ВалерьевичМосковский государственный университет им. М. В. Ломоносовакандидат физико-математических наук, доцентtaran@butovo.com
Всего: 1

Ссылки

Cohen G., Honkala I., Litsyn S., and Lobstein A. Covering codes. Elsevier Science, 1997.
Чашкин А. В. Дискретная математика. М.: Академия, 2012.
Зиновьев В. А., Зиновьев Д. В. Системы Штейнера S(v, k, к - 1): компоненты и ранг // Проблемы передачи информации. 2011. Т. 47. №2. С. 52-71.
Ковалевская Д. И., Соловьева Ф. И. Системы четверок Штейнера малых рангов и расширенные совершенные двоичные коды // Дискретный анализ и исследование операций. 2013. Т. 20. Вып. 4. С. 46-64.
Таранников Ю. В. Комбинаторные свойства дискретных структур и приложения к крип-тологии. М.: МЦНМО, 2011.
Reid C. and Rosa A. Steiner systems S(2,4,v) - a survey // Electron. J. Combinator. 2010. DS18.
Таранников Ю. В. О значениях аффинного ранга носителя спектра платовидной функции // Дискретная математика. 2006. Т. 18. Вып.3. C. 120-137.
Урбанович Т. А. О дизайнах специального вида на подмножествах булева куба: дипломная работа / механико-математический факультет МГУ им. М.В. Ломоносова. М., 2012.
 О рангах подмножеств пространства двоичных векторов, допускающих встраивание системы Штейнера S(2, 4, v) | ПДМ. 2014. № 1(23).

О рангах подмножеств пространства двоичных векторов, допускающих встраивание системы Штейнера S(2, 4, v) | ПДМ. 2014. № 1(23).

Полнотекстовая версия