20.5. СИСТЕМА ШТЕЙНЕРА S(5, 8, 24) ЕДИНСТВЕННА

Цель этого раздела — доказать следующую теорему.

Теорема 9. Существует единственная система Штейнера ). Более точно, если имеются две системы Штейнера ), обозначим их через и то существует перестановка, действующая на 24 точках, которая переводит октады системы в октады системы (В этом разделе октада означает блок системы Штейнера

Для доказательства удобно воспользоваться таблицей значений приведенной на рис. 2.14. В частности, из последней строки этой таблицы следует, что две октады пересекаются в 0, 2 или 4 точках. Мы начнем с нескольких лемм.

Лемма 10. (Лемма Тодда.) Если октады системы ), пересекающиеся в 4 точках, то также является октадой.

Доказательство. Пусть и предположим, что не является октадой. Тогда октада содержащая точки должна содержать еще ровно одну точку из С и имеет, например, вид Аналогично октада, содержащая точки должна иметь вид Но теперь невозможно найти октаду, содержащую точки и пересекающуюся с октадами В, С, D, Е в 0, 2 или 4 точках. Это приводит к противоречию, так как должна существовать октада, содержащая любые 5 точек.

Лемма 11. Если известны 280 октад, пересекающих данную октаду О в четырех точках, то все 759 октад определены.

Доказательство. Согласно рис. 2.14 мы должны найти 30 октад, не пересекающихся с О и 448 октад, пересекающихся с О в двух точках, т. е. 16 октад, пересекающихся с О в двух заданных точках

Пусть Помимо О имеется еще четыре октады, содержащие точки скажем, и 4 октады, содержащие точки скажем, Согласно лемме

10 суммы представляют собой октады, и легко видеть, что все они различны и являются 16 октадами, содержащими точки Шесть сумм являются октадами, не пересекающимися с О. Ясно, что они различны и что Так как точку а можно выбрать пятью способами, то это и дает 30 октад, не пересекающихся с О.

Определение секстета. Любые четыре точки определяют разбиение 24 точек на 6 множеств по 4 точки в каждом, называемых тетрадами и удовлетворяющих следующему свойству: объединение любых двух таких тетрад является октадой. Это множество из 6 тетрад называется секстетом (т. е. шесть тетрад). (Чтобы убедиться в этом, выберем пятую точку Существует единственная октада, содержащая точки скажем, Тогда вторая тетрада. Девятая точка определяет октаду и тетраду Согласно лемме Тодда является октадой и т. д.)

Лемма 12. Пересечения любой октады с 6 тетрадами секстета имеют следующий вид: 3-15, или 42-04, или 24-02. (Первое из этих выражений 3-15 означает, что октада пересекает одну тетраду в трех точках, а другие пять — в одной точке.)

Доказательство. Две октады пересекаются в 0, 2 или 4 точках.

Лемма 13. Матрица пересечений тетрад из двух секстетов имеет один из следующих видов:

Доказательство. Следует из леммы 12 и определения секстета.

Доказательство теоремы 9. Пусть — фиксированная октада в системе Штейнера S(5, 8, 24). Идея доказательства заключается в том, что однозначно определяются все октады, пересекающие О в 4 точках; теорема тогда будет следовать из леммы 11. Чтобы найти эти октады, мы построим 7 секстетов

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

Таким образом, октада О состоит из двух первых столбцов этой матрицы.

Согласно лемме 12 пересечение октады, содержащей точки должно иметь вид 3-15, и поэтому, изменив соответствующим образом нумерацию точек мы можем выбрать эту октаду в виде Тетрада определяет секстет, который согласно лемме 13 может быть выбран в виде

Эта диаграмма означает, что тетрадами секстета являются множества . В этих обозначениях

Замечание. Мы описали сейчас 30 октад, не пересекающихся с октадой О. Эти октады представляют собой (i) суммы любых двух строк матрицы

(ii) суммы любых двух столбцов этой матрицы, (iii) суммы октад вида Схематически это можно проиллюстрировать следующим образом:

Пересечение октады, содержащей точки с обоими секстетами имеет вид 3-15, и поэтому эта октада может быть выбрана в виде множества Тетрада определяет секстет, который можно выбрать в виде

если воспользоваться леммой 13 и рассмотреть пересечения с 30 октадами, указанными в предшествующем замечании. Здесь мы отметим, что секстеты инвариантны относительно следующих перестановок точек множества

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

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

Аналогичным способом получаем, что

Далее пересечение октады, содержащей точки имеет вид , и поэтому, используя перестановку , можно предположить, что пересечение этой октады с первыми четырьмя столбцами секстета имеет вид 24. Поэтому в качестве этой октады мы можем выбрать множество Это приводит к секстету

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

Остается показать, что все 280 октад, пересекающих О в 4 точках, определяются секстетами

Если два секстета пересекаются равномерно (т. е. если матрица пересечений тетрад из этих секстетов совпадает с третьей матрицей, приведенной в лемме 13), то мы можем сложить в них соответствующие октады и получить новую октаду и новый секстет. Например, из получаем

Легко проверить, что таким способом мы получим все

секстетов, которые определяются четырьмя точками О. Но эти секстеты дают все октады, пересекающие октаду (3 в 4 точках.

Первоначальное доказательство Витта теоремы 9 заключается в последовательном доказательстве единственности систем Штейнера (4, 7, 23) и, наконец, ). Отправные точки этого доказательства даются в следующих упражнениях.

Упражнения. (12). Доказать единственность аффинных плоскостей для значений (см. § 2.5 и теорему 11 приложения В). [Указание. Выбрать семейство из непересекающихся блоков системы и назвать их «горизонтальными прямыми», а другое семейство из непересекающихся блоков назвать «вертикальными прямыми». Точка пересечения вертикальной прямой и горизонтальной прямой у определяется координатами Каждый из оставшихся блоков состоит из точек вида ( Образовать -матрицу строками которой являются

векторы Показать, что для значений матрица по существу единственна].

(13). Доказать единственность проективных плоскостей для значений [Указание. Так как аффинные плоскости единственны, то их можно построить с помощью конечных полей (что приведено в § 2 приложения В). Существует единственный способ расширения такой плоскости до проективной плоскости.]

(14). Доказать единственность систем Штейнера S(3, 6, 22) и S(4, 7, 23). [Указание. Пусть Р - фиксированная точка S(3, 6, 22). Идея состоит в доказательстве того, что блоки, содержащие точку образуют систему S(2, 5, 21), которая единственна в силу упражнения (13), а другие блоки образуют овалы (с. 321 гл. 11) в системе Штейнера S(2, 5, 21) (см. Витт [1424] или Лунберг [866]).]

(15). (а). Показать, что матрица Адамара 8 порядка 8 единственна с точностью до эквивалентности (ср. с. 56 гл. 2). [Указание. Воспользоваться тем, что система единственна.] (Ь). Показать, что матрица Адамара единственна.

(16). Показать, что система Штейнера ) единственна, и, следовательно, расширенный -код Хэмминга также единствен.