ПРИЛОЖЕНИЕ В. КОНЕЧНЫЕ ГЕОМЕТРИИ

1. Введение

Конечные геометрии представляют собой такой же важный комбинаторный объект, как и коды, и поэтому нет ничего удивительного в том, что они возникают во многих главах этой книги (см., в частности, гл. 13). В данном прило-. жении мы даем эскиз основ теории конечных геометрий, начиная (в § 2) с ределения проективной и аффинной геометрий. Наиболее важными (для нас) примерами конечных геометрий являются проективная геометрия и аффинная (или евклидова) геометрия размерности конструкции торых основаны на конечном поле Для этим исчерпываются все возможные конечные геометрии (теорема 1).

В § 3 этого приложения исследуются свойства геометрий и в частности их группы колливеаций (теорема 7 и следствие 9), и выводится формула для числа подпространств данной фиксированной размерности (теоремы 4—6).

Дело обстоит нескольюо сложнее, если размерность Проективная плоскость эквивалентна системе Штейнера для некоторого а аффинная плоскость — системе для некоторого (теорема 10). Но в этом случае существуют и другие типы плоскостей, отличные от и (см. § 4).

2. Конечные геометрии PG(m, q) и EG(m, q)

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

(i). Через любые две различные точки проходит только одна прямая (обозначаемая через ).

(ii). Каждая прямая содержит по меньшей мере три точки.

(iii). Если различные прямые имеют общую точку и если точки и I прямой не равны точке и точки прямой не равны точке то прямые также имеют общую точку (см. рис. ПВ.1).

(iv). Для любой точки найдутся по меньшей мере две прямые, не содержащие и для любой прямой найдутся по меньшей мере две точки, не принадлежащие

Подпространством проективной геометрии называется такое подмножество для которого выполняется условие:

(v). Если различные точки из то все точки прямой принадлежат

Рис. ПВ.1. Аксиома (iii)

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

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

Множество точек в аффинной или проективной геометрии называется независимым, если для каждого точка не принадлежит никакому

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

Проективная геометрия Наиболее важные примеры проективной и аффинной геометрий получаются из конечных полей.

Пусть конечное поле (см. гл. 3, 4), и предположим, что 2. Выберем в качестве точек множества ненулевые -последовательности

положив, что последовательности

задают одну и ту же точку для любого ненулевого элемента X из GF(q). Это так называемые однородные координаты точки. Всего имеется ненулевых -последовательностей, и каждой точке соответствует последовательностей, так что число точек в множестве равно

Прямая, проходящая через две различные точки состоит из точек вида

где не равны одновременно нулю. Прямая состоит из точек, так как всего имеется возможностей выбора пары и каждая точка появляется при этом в раз. Аксиомы (i) и (ii), очевидно, выполняются.

Упражнение. (1). Проверить выполнение аксиом (iii) и (iv).

Определенная так проективная геометрия обозначается через

Упражнение. (2). Доказать, что размерность геометрии равна

Примеры. (1). Если то проективная плоскость состоит, как показано на рис. ПВ.2, из семи точек (100), (001), (010), (011), (101), (110), (111) (ср. с рис. 2.12).

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

Рис. ПВ.3 13 точек и 9 из 13 прямых проективной плоскости

(2). Если то получаем проективную плоскость содержащую точек

и 13 прямых линий, 9 из которых показаны на рис. ПВ.З.

Удобно расширить определение геометрии включив значения и 1, хотя эти вырожденные геометрии не удовлетворяют аксиоме (iv). При этом — пустое множество, — точка и прямая.

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

Такая гиперплоскость на самом деле представляет собой геометрию и будет в дальнейшем обозначаться через Отметим, что при любом соответствуют одной и той же гиперплоскости (т. е. гиперплоскости при и на рис. обозначены именно таким образом. Ясно, что точка принадлежит гиперплоскости тогда и только тогда, когда

Упражнения. (3). Показать, что точки геометрии допускают однозначную нумерацию последовательностями, крайняя левая ненулевая координата которых равна 1 (как в примере 2).

(4). Показать, что геометрия может быть построена из векторного пространства V размерности над полем GF(q) путем объявления точками геометрии всех одномерных подпространств в V, а прямыми — двумерных подпространств в

(5) Провести четыре пропущенные на рис. прямые.

(6). Построить

Аффинная, или евклидова геометрия Она получается из геометрии путем удаления точек гиперплоскости (безразлично какой именно в силу следствия 8). Например, удаление прямой линии [100] на рис. ПВ.2 приводит к :

В общем случае, если в качестве выбирается гиперплоскость , состоящая из всех точек, для которых то остаются точки, допускающие нумерацию последовательностями ( Таким образом, точек геометрии можно нумеровать просто «-последовательностями

Мы опять примем, что пустое множество, точка прямая.

Упражнение. (7) Доказать, что (определенная выше) размерность геометрии равна Показать также, что является векторным пространством размерности над полем GF(q).

Замечание. Все ненулевые элементы поля соответствуют точкам геометрии но каждой точке при этом соответствует различных элементов поля. Например, пусть Тогда элементы поля представляют собой одну и ту же точку геометрии Прямая, проходящая через точки (100) и (010), содержит пять точек.

Точками аффинной геометрии являются все элементы поля

Дезарговы геометрии. Все аффинные и проективные геометрии, размерность которых больше двух, строятся с помощью конечных полей. Но в двумерном случае дело обстоит несколько сложнее.

Теорема 1. Если то всякая конечная проективная геометрия размерности является геометрией для некоторого и всякая аффинная геометрия размерности является для некоторого

Геометрия называется дезарговой, так как в ней выполняется теорема Дезарга.

Доказательство теоремы 1 проводится в три шага. (i). Показывается, что в проективной геометрии, размерность которой больше двух, выполняется теорема Дезарга. (ii). Доказывается, что все точки дезарговой геометрии могут быть заданы координатами, принадлежащими, возможно, некоммутативному полю Если -конечно, то оно коммутативно и, следовательно, для некоторого Детальное доказательство можно найти в книгах: Артин [29, гл. 2], Бэр [56, гл. 7], Дембовский [370, гл. 1], Херстейн [642], Веблен и Янг [1368, т. 1, гл. 21.

3. Свойства геометрий PG(m, q) и EG(m, q)

Подпространства геометрии Упражнение. (8). Доказать, что если подпространство в то является также подпространством в для некоторого и что может быть задано как множество точек, удовлетворяющих системе независимых однородных линейных уравнений.

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

В общем случае при пересечение (определяемой уравнениями) и (определяемой уравнениями) имеет размерность или или При подпространства могут не пересекаться.

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

Аналогично существует взаимно-однозначное соответствие между подпространствами размерности и подпространствами размерности сохраняющее отношение инцидентности (и называемое иногда корреляцией). Например, если две геометрии пересекаются в одной точке, то линейная оболочка объединения двойственных геометрий равна гиперплоскости.

Это соответствие удовлетворяет принципу двойственности, согласно которому любое утверждение относительно геометрии остается справедливым, если заменить «точку» на «гиперплоскость», на «пересечение» на «линейную оболочку объединения» и «содержит» на «содержится».

Важнейшим следствием этого принципа является следующий факт.

Теорема 2. Если то число подпространств в геометрии содержащих данную геометрию равно числу подпространств содержащихся в данной геометрии

Упражнение. (9). Доказать непосредственно следующий частный случай теоремы 2: число линий, проходящих через заданную точку, равно числу точек а гиперплоскости.

Число подпространств. Теорема 3. Число подпространств содержащихся в геометрии равно

где

— гауссовский биномиальный коэффициент, определенный в упражнении (3) гл. 15.

Доказательство. Число способов выбора независимых точек в геометрии определяющих геометрию равно числителю выражения (2). Однако многие из этих множеств точек задают одну и ту же геометрию и поэтому мы должны поделить выражение (2) на знаменатель, который равен числу способов выбора независимых точек в геометрии

Аналогичным образом доказывается следующее утверждение.

Теорема 4. Пусть в геометрии выполняется условие Тогда чисто подпространств размерности таких, что равно

Упражнение. (10). Используя теорему 3, доказать, что число подпространств содержащихся в геометрии равно числу подпространств содержащихся в геометрии

Подпространства и плоскости в геометрии Подпространство геометрии называется плоскостью.

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

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

Теорема 5. Число -плоскостей в геометрии равно

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

Теорема. 6. Пусть в геометрии имеет место включение где Число плоскостей размерности для которых равно

Доказательство. Вытекает из теоремы 4.

Заметим, что в проективной геометрии любые две гиперплоскости пересекаются по подпространству размерности в то время как в аффинной геометрии две гиперплоскости могут пересекаться по подпространству любой размерности или вообще не пересекаться. Непересекающиеся гиперплоскости называются параллельными.

Упражнение. (12). Доказать, что геометрию можно разложить, на взаимно параллельных плоскостей.

Группа коллинеаций геометрии Определение. Коллинеацией проективной или аффинной геометрии называется такая перестановка ее точек, которая переводит прямые линии в прямые. Отсюда следует, что каждое подпространство отображается в подпространство той же размерности.

Например, перестановка является коллинеацией геометрии (см. рис.

Множество всех коллинеаций геометрии образует ее группу коллинеаций. Предположим, что где простое. Напомним, что согласно теореме 12 гл. 4 группа автоморфизмов поля является циклической группой порядка и порождается отображением Отображение очевидно, является коллинеацией геометрии

Пусть С — обратимая -матрица над Тогда перестановка точек геометрии задаваемая отображением

С, также является коллинеацией. Ясно, что матрицы задают одну и ту же коллинеацию.

Отображение и матрицы С порождают группу, состоящую из перестановок вида

Всего имеется таких перестановок, но только

из них задают различные коллинеации. Эта группа коллинеаций обозначается через

Теорема 7. (Основная теорема проективной геометрии.) Группа является полной группой коллинеаций геометрии

Доказательство этой теоремы можно найти, например, у Артина [29], Бэра [56, гл. 3] или Кармайкла [250].

Так как группа дважды транзитивна, то справедливы следующие утверждения.

Следствие 8. Имеется по существу только один способ построения геометрии из геометрии

Следствие 9. Полная группа коллинеаций геометрии равна подгруппе группы относительно которой инвариантна бесконечно удаленная гиперплоскость, и имеет порядок

(см., например, Кармайкл [250]).

Упражнение. (13). Доказать, что для заданной геометрии имеется по существу только один способ добавления гиперплоскости, приводящий к геометрии

4. Проективные и аффинные плоскости

Проективная геометрия размерности 2 называется проективной плоскостью. В отличие от случаев большей размерности проективная плоскость не обязательно представляет собой геометрию для некоторого

В § 5 гл. 2 мы определили проективную плоскость как систему Штейнера для некоторого или, иными словами (определение 2), как совокупность точек и прямых, причем на каждой прямой лежат точки и через любые две точки проходит точно одна прямая. Однако наилучшим определением проективной плоскости является следующее.

Определение 3. Проективной плоскостью называется совокупность точек и прямых, удовлетворяющая следующим условиям: (i) через любые две точки проходит точно одна прямая; (ii) любые две различные прямые пересекаются в одной точке и (iii) существуют четыре точки, из которых никакие три не лежат на одной прямой линии.

Теорема 10. Все три определения проективной плоскости эквивалентны.

Набросок доказательства. Определение определение 3. Необходимо только доказать, что любые две прямые пересекаются. Это следует из того, что в противном случае две прямые будут содержать четыре независимые точки, так что размерность пространства не будет равна 2.

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

Определение 2 определение 1. Чтобы доказать покажем, что любые две прямые пересекаются. Для доказательства этого факта используются два разных метода подсчета где функция равна

I, если и равна 0 в противном случае, а суммирование ведется по всем точкам и парам различных прямых Размерность системы равна 2, так как если четыре независимые точки, то прямые не пересекаются.

Система Штейнера называется проективной плоскостью порядка я. Таким образом, на рис. показаны проективные плоскости порядков 2 и 3. В общем случае является проективной плоскостью порядка Согласно теореме 7 гл. 4 это дает нам дезарговы проективные плоскости всех порядков, равных степени простого числа.

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

Теорема 11. Проективные плоскости порядков 2, 3, 4, 5, 7, 8 определены однозначно (и представляют собой дезарговы плоскости

Для доказательства теоремы см. упражнение (13) гл. 20 и результаты, приведенные Домбовским [370, с. 144].

Из упражнения (11) гл. 19 мы узнаем, что не существует ни одной проективной плоскости порядка 6. Это утверждение является частным случаем следующего результата.

Теорема 12. (Брук и Райзер.) Если или и если не является суммой двух квадратов, то не существует проективной плоскости порядка я.

Доказательство этой теоремы можно найти в книге Холла [587] или в работе Хьюза и Пайпера [674].

Таким образом, известны проективные плоскости порядков Известно (теорема 12), что не существует плоскостей порядков и вопрос остается открытым для порядков 10, 12, 15, Связь между кодами и плоскостями порядков , где дается в упражнении (11) гл. 19.

Аффинные, или евклидовы, плоскости. Аффинной плоскостью называется аффинная геометрия порядка 2; она получается из проективной плоскости удалением всех точек некоторой фиксированной линии. В § 5 гл. 2 было дано второе определение аффинной плоскости: аффинной плоскостью называется система Штейнера Третье определение выглядит следующим образом. Аффинной плоскостью называется множество точек и прямых, удовлетворяющих следующим условиям: (i) через любые две точки проходит точно одна прямая; (ii) для любой заданной прямой и любой точки существует прямая линия, проходящая через и не пересекающаяся с (iii) существуют три

точки, не лежащие на одной прямой Эти три определения опять эквивалентны, и мы будем обозначать через аффинную плоскость порядка Тогда все приведенные выше результаты о возможных порядках проективных плоско стей переносятся на счучай и для аффинных плоскостей

Замечания к приложению В

Проективные геометрии изучали Артин [29], Бэр [56], Бигс [143], Биркгофф [152, гл 8], Кармайкл [250], Дембовский [370], Холл [583, гл 12], Мак Нейш [869], Сегре [1173], Веблен и Юнг [1368] Что касается проективных плоскостей, см Альберт и Сандлер [20], Холл [582, гл 20 и 587, гл 12], Сегре [1173] и в особенности Дембовский [370], Хьюджс и Пайпер [674] Подсчет числа подпространств можно найти например у Кармайкла [250] или у Голдмана и Роты [519] См также серию работ Зе Хяна, Бен Фу, Зонг-Ду и Ху-Нинга [103, 104, 1441, 1457—1460, 1474]

СПИСОК ЛИТЕРАТУРЫ

В конце каждой ссылки в квадратных скобках стоит число, указывающее номер главы или приложения, к которым относится данная ссылка Мы стара лись, где только возможно, давать ссылки на публикации на английском языке, отметим что работы из журналов «Проблемы передачи информации», «Доклады Академии наук СССР», «Электроника и связи в Японии», а также некоторые другие работы являются переводами с других языков

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

СПИСОК ЛИТЕРАТУРЫ НА РУССКОМ ЯЗЫКЕ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

УТОЧНЕНИЕ К СПИСКУ ЛИТЕРАТУРЫ, ПРИСЛАННЫЕ АВТОРАМИ К РУССКОМУ ПЕРЕВОДУ

(см. скан)

(см. скан)