2.5. t-СХЕМЫ

Определение. Пусть X будет -множеством (т. е. множеством, состоящим из элементов), элементы которого называются точками или иногда (исторически) независимыми переменными. Назовем -схемой семейство различных подмножеств (называемых блоками) множества X, удовлетворяющих следующему свойству: любое -подмножество из X содержится точно в К блоках. Более образно, это — совокупность комиссий, выбранных из человек, причем каждая комиссия состоит из человек и любые человек работают вместе точно в комиссиях. Назовем такое семейство подмножеств Иногда -схемы называются также тактическими конфигурациями.

Пример. Семь точек и семь линий (одна из которых кривая) на рис. 2.12 образуют проективную плоскость порядка 2. Если в качестве блоков мы выберем линии, то они образуют -схему, так как через любые две точки из семи проходит точно одна линия. Эти семь блоков таковы:

Рис. 2.12. Проективная плоскость порядка 2

2-схема называется также уравновешенной неполной блок-схемой, и терминология в этой области возникла вследствие первоначального применения таких схем в агротехнических и биологических экспериментах. Предположим, например, что надо сравнить между собой различных видов удобрений по их влиянию на различных культур. В идеальном случае каждую культуру надо испробовать с каждым из видов удобрений, для чего требуется земельных участков (по одному на каждую культуру), причем каждый участок (или блок) имеет размер Получается -схема, которая называется полной схемой. Такое сравнение, однако, практически невозможно по экономическим соображениям, и мы ищем схему, в которой каждая культура испытывалась бы только с различными удобрениями (так что каждый блок имеет теперь размер и любые два разных вида удобрений использовались бы вместе одно и то же число К раз. Таким образом, схема является уравновешенной, если речь идет о сравнении пар разных видов удобрений. Итак, эта схема представляет собой -схему с блоками, и она является неполной, если

Некоторые другие -схемы также имеют свои собственные названия.

Определение. Системой Штейнера называется -схема, в которой параметр А равен 1, и обычно -схема обозначается через Таким образом, на рис. 2.12 был приведен пример системы 5 (2, 3, 7).

Определение. Проективной плоскостью порядка называется система Вот почему рис. 2.12 и изображает проективную плоскость порядка 2. (Подробнее см. в приложении В.)

Определение. Аффинной плоскостью порядка называется система

Теорема 9. Пусть обозначают любые различных элементов заданной -схемы и пусть равно числу блоков, содержащих элементы равно общему числу блоков в данной схеме. Тогда число , не зависит от выбора элементов действительности определяется следующим равенством:

Отсюда следует, что -схема является также -схемой для любого

Доказательство. По определению -схемы результат справедлив для так как любые элементов содержатся точно в Я блоках. Воспользуемся теперь индукцией по Предположим, что мы уже показали, что число не зависит от выбора элементов Для каждого блока В, содержащего элементы и для каждого элемента отличного от положим если если Тогда получаем

что доказывает независимость числа от выбора элементов и устанавливает справедливость (2.19).

Следствие 10. В -схеме общее число блоков равно

и каждый элемент встречается точно в блоках, где

Более того, в -схеме выполняется равенство

Доказательство. Так как то (2.21) следует из (2.19) при Так как то равенства (2.22) и (2.23) следуют из (2.20).

Если следовательно, то схема называется симметричной.

Следствие 11. Необходимым условием существования -схемы является целочисленность выражений

для всех значений

В некоторых случаях, как, например, для систем Штейнера это условие является также и достаточным, но так бывает не всегда. Например, мы увидим в гл. 19 что система ), или проективная плоскость порядка 6, не существует, хотя указанное выше условие выполнено.

Задача (нерешенная). (2.3). Имеется предположение, что для любых заданных , если выполняются условия следствия 11 и число достаточно велико, существует -схема. Но пока это предположение доказано только для (см. работы Вильсона [1420—1422]). В настоящее время не известно ни одной нетривиальной -схемы с

Определение. Пусть элементы, принадлежащие одному из блоков заданной -схемы. Рассмотрим блоки, которые содержат элементы но не содержат ни одного из элементов при рассмотрим блоки, которые не содержат а при блоки, которые содержат Если число таких блоков одно и то же независимо от выбора элементов то обозначим его через Параметры называются индексами блоковых пересечений.

Теорема 12. Параметры полностью определены для . В самом деле, при причем и все они находятся по теореме 9. Кроме того, если числа определены, то они удовлетворяют свойству Паскаля

Наконец, если схема является системой Штейнера , то следовательно, числа определены для всех значений

Доказательство. Свойство Паскаля выполняется, так как равно числу блоков, которые содержат элементы но не содержат элементов Эти блоки могут быть разбиты на две группы: блоки, содержащие элемент их число равно и блоки, не содержащие их число равно То что определены для всех является непосредственным следствием теоремы 9. Действительно, как общее число

блоков так и число блоков содержащих элемент не зависит от выбора Следовательно, число блоков, не содержащих равно и также постоянно, т. е. не зависит от выбора Последнее утверждение теоремы очевидно.

Таким образом, для любой -схемы мы можем образовать «треугольник Паскаля» из ее индексов блоковых пересечений:

Например, для системы Штейнера S(2, 3, 7), изображенной на рис. 2.12, получаем следующий треугольник:

Из данной -схемы с индексами блоковых пересечений можно получить несколько других схем. Пусть обозначает множество из блоков первоначальной схемы.

Предположим, что мы исключили один из элементов, скажем, из всех блоков и рассмотрим два множества получившихся блоков: первое, обозначим его состоит из блоков (каждый блок из элементов), не содержащих элемента в исходной схеме; второе, обозначим его состоит из блоков, содержащих по элементов.

Теорема 13. Блоки множества образуют -схему, индексы блоковых пересечений которой Блоки множества образуют -схему с индексами блоковых пересечений Эти схемы называются производными схемами.

Доказательство предоставляется читателю.

Следствие 14. Если существует система Штейнера то существует и система Штейнера

Если то, беря дополнения всех блоков из получаем дополнительную схему, которая является -схемой с индексами блоковых пересечений

Матрица инцидентности. Пусть задана -схема с элементами блоками Матрица («размера с элементами

называется матрицей инцидентности данной схемы.

Например, матрица инцидентности схемы, изображенной на рис. 2.12, имеет вид

(что это за матрица, читатель должен вспомнить по § 2.3).

Упражнение. (9). Показать, что при выполняются следующие соотношения:

Коды и схемы. Каждому блоку системы Штейнера соответствует строка матрицы инцидентности А. Если мы рассмотрим эти строки как кодовые слова, то система Штейнера образует нелинейный (двоичный) код с параметрами

Так как любые два блока содержат не более чем общих элементов (иначе имелось бы элементов, содержащихся в двух блоках, что приводит к противоречию), то, следовательно, расстояние Хэмминга между ними не меньше чем Заметим также, что каждое кодовое слово имеет вес этот код явля-, ется равновесным.

Можно также рассмотреть линейный код, порожденный блоками -схемы, но, по-видимому, в общем случае немногое известно о таких кодах. (Как мы увидим в гл. 13, имеются некоторые результаты для относительно кодов, порожденных аффинными и проективными плоскостями.)

Наоборот, если задан -код, то иногда можно получить -схему из кодовых слов фиксированного веса.

Теорема -код Хэмминга (см. § 1.7), и пусть код получен из кода добавлением общей проверки на четность. Тогда все кодовые слова веса 3 в коде образуют систему Штейнера а все кодовые слова веса 4 в коде образуют

Определение. Двоичный вектор покрывает двоичный вектор и, если позиции с единицами вектора и являются подмножеством позиций с единицами вектора так, например, вектор 1001 покрывает векторы 1001, 1000, 0001 и 0000. Эквивалентными формулировками являются следующие:

Доказательство теоремы 15. Первое утверждение теоремы следует из второго, если воспользоваться следствием 14. Для доказательства второго утверждения обозначим координаты кода буквами где соответствует общей проверке на четность. Пусть и — произвольный вектор веса 3, единицы которого занимают позиции где Надо показать, что имеется единственное кодовое слово веса 4 из которое покрывает вектор и. Конечно, двух таких кодовых слов в коде быть не может, иначе они находились бы друг от друга на расстоянии 2, что невозможно. Рассмотрим случай когда Так как совершенный код, исправляющий одиночные ошибки, то он содержит кодовое слово с на расстоянии самое большее 1 от вектора и. Тогда либо и в этом случае расширенное кодовое слово имеет вес 4, принадлежит коду и покрывает и, либо с имеет вес 4, и тогда нам подходит слово Случай Вектор и с единицами в координатах покрывается единственным кодовым словом с из веса 3, и тогда вектор покрывает наш исходный вектор и.

Следствие 16. Число кодовых слов веса 3 в коде Хэмминга равно

а число кодовых слов веса 4 в расширенном коде Хэмминга равно

Как мы увидим в гл. 13, кодовые слова веса 3 в коде могут быть отождествлены с линиями конечной проективной геометрии

Упражнение. (10). Найти все кодовые слова веса 3 в коде Хэмминга длины 7 и проверить следствие 16 для этого случая. Отождествить полученные кодовые слова с линиями на рис. 2.12.

Точно так же, как теорема 15, доказывается следующая теорема.

Теорема 17. Пусть — совершенный код длины исправляющий ошибок, где нечетное, и пусть код получен из кода добавлением общей проверки на четность. Тогда все кодовые слова веса в коде образуют систему Штейнера а кодовые слова веса в коде образуют

Обобщения сформулированного выше следствия, а также более обширные сведения о кодах и схемах будут приведены в гл. 6. Упражнение. (11). Пусть -матрица Адамара порядка и пусть матрица, определенная в упражнении (6). Показать, что если элементы —1 заменить на элементы 0, то строки образуют симметричную -схему, и наоборот.