Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 141
Текст из файла (страница 141)
Пусть (д,, ..., йь) является (и, я, 1)-разностным множеством с я -- 3. Тогда вычеты по модулю и и блоки Во С =. О, 1, ..., и — 1, определенные в теореме 9.76, удовлетворяют всем условиям, налагаемым на точки и прямые конечной ~роективной плоскости порядка я — 1. Доказательство. Сформулированное утверждение следует из теоремы 9.76 и того, что симметричная (о, я, 1)-блок-схема с я ) 3 является конечиои проективной плоскостью.
Н Из теоремы 9.76 и соотношения (9.!О) следует, что параметры разиостиого множества и, я и Х связаны тождеством й (я — 1) = >. (о — !). Это тождество можно также получить непосредственно из определения разностного множества. Гл. 9. Пркложепяя конечных полей 9.78. Пример. Множество (О, 1, 2, 4, 5, 8, !О), составленн . из вычетов по модулю 15, является (15, 7, 3)-разностным множ ством. По теореме 9.7б блоки вида В~ —— — (г, г + 1, г + 2, г + 4, г + 5, г + 8, г + 10), Г=-= 0,1, ...,!4, образуют симметричную (15, 7, 3)-блок. схему.
Ее блоки мож отождествить с 15 плоскостями проективной геометрии Р6 ( ' Ге), в то время как все 15 вычетов по модулю 15 отождествляю с точками той же геометрии. Каждая из этих плоскостей являете' плоскостью Фано Р6 (2, Ке). Для каждого блока В, все его пря мые можно получить из прямой 7., = в, () в,, =- (г, г + 1, 1+ 4), принадлежащей плоскости В,, с помощью циклической пересе ' вовки Г- !+1- !+2 !+4 !+5- !+10- 1+8 й" Например, прямые, лежащие в плоскости В„= (О, 1, 2, 4,: 10, 8), имеют вид (О, 1, 4), (1, 2, 5), (2, 4, 10), (4, 5, 8), (5, 10, О), (1О, 8, Ц (8, О, 2). Примеры разностных множеств можно строить на основе вечных проективных геометрий. Отождествим, как и в рассу нии, предшествующем примеру 9,71, точки проективной гео' трии Р6 (гп, Ке) со степенями элемента се, где а является пр митивным элементом поля !(',, и причем показатели степени э мента и берутся по модулю и =- (д'"+' — 1)!(д — 1).
Пусть В;; произвольная гиперплоскость в Р6 (и, !1' ). Тогда Я имеет цикл',, и, таким образом, все гиперплоскости Вя = аЯВ, Ь = О, 1,;.' ...„о — 1, являются различными. А так как число всех гиперпл костей этого пространства равно о, то нми исчерпываются все г перплоскости пространства Р6 (и, ~ ).
Таким образом, привод мый ниже список является полным сйиском всех гиперплоскос проективного пространства Р6 (ле, Ке) (в нем точки, лежащие соответствующей гиперплоскости, задаются соответствующим п казателем степени элемента а): Во'. е(е ! (к+1 ля+ 1 ... А,+1 5 4. Приложения к комбинаторяке Здесь й = (о — 1)!(д — !) — число точек одной гиперплоскости. Г.'сли мы выделим те строки, которые содержат какое-то конкретное значение, скажем О, то получим и гиперплоскостей, проходя!ц!!х через точку сс'.
Эти й строк имеют вид а! — й1 йз — й1 ... йк — а1 й! — йз йт — йз й — А й1 — ач й2 — г!к ° йх — ак Каждая точка, отличная от а', встречается в этих й гиперплоскостях столько раз, сколько имеется различных гиперплоскостей, проходящих через две различные точки, а именно в Х = (д -'— --!)!(о — !) из них. Таким образом, среди элементов, не стоящих пз диагонали, каждый ненулевой вычет по модулю о встречается ровно к раз. Следовательно, (й„..., йд) является (о, и, Л)-разностным множеством.
Следующая теорема объединяет полученные результаты. 9.79. Теорема. Точки любой гипврплоскости пространства Р6 (т, ~4) образуют (и, и, Х)-разностное множество с парамегпрами ~п+! ! гй ! ~сп — 1 е †! ' д †!' д — 1 9.80. Пример. Рассмотрим гиперплоскость проективного пространства Рб (3, К,) (см.
пример 9.71), определяемую уравнением х, =-: О. Она содержит точки А, В, С, Н, !, .7, К. Эти точки можно отождествить со степенями элемента гс, причем соответствующие показатели степени образу!рт (15, 7, 3)-разностное множество (О, 2, 3, 6, 8, 13, !4). ь) Другим разделом комбинаторики, в котором применяется теория конечных полей, является теория ортогональных латинских квадратов. 9.8!. Определение. Таблица ам ам ..
а,„ ам аае ... ая„ ь =(аы) = а„е ... а„„ называется латинским квадратом порядка и, если любая строка н любой столбец этой таблицы содержат ровно по одному разу каждый элемент из данного множества, содержащего и элементов. Лва латинских квадрата (ам) и (6гт) порядка п называются ортогональными, если все пе упорядоченных пар (аен Ь;;) различны. Гл.
9. Приложения конечных полей а -1 аьа1 + ачл айаг + ач-т аь а, а„а, аьа, + а„ а„а, а„а, + а, ьь = аьач 1 адад т + а1 аьач, + а, Н образуют множество из д — 1 попарно ортогональных лат сках квадратов порядка д. Доказательство. Каждая таблица 1.„, очевидно, является тинским квадратом. Пусть а» =- аьа,, + а; 1 есть (1, !)-й эл ьм мент латинского квадрата Е».
Если я ~ т, то предположим, для некоторых 1 < 1, 1, д, й ~~ д (а$~~~! а! !) = (а~„~!, аг!ь!) Тогда (а„аьл + аз „а,„а,, + а, т) = (адаг 1 + а ь 1 абае 1 + ал 1) откуда а (а~1 — а 1)=аь1 — а1» а,„(а~1 — ав1)=аь1 — ари 9.92. Теорема, Для любого натурального числа и сушествуе латинский квадрат порядка и. Доказательство. Рассмотрим таблицу (а»), где а» -=-= ! ф -1- ! (тод и), 1 ~ а» ~ и. Тогда из равенства а» = ам следуеф что !+! =- !+я(пюди), т.е.
! = я(води), откуда 1=9' так как 1.-, 1, !', !г < и. Аналогично из равенства а» =- аь еле( дует, что ! = )г, Таким образом, элементы каждой строки и кащ'; дого столбца все различны. Ортогональные латинские квадраты впервые изучались Эйле' ром. Он выдвинул гипотезу, что не существует пары ортогон ных латинских квадратов порядка п, если и равно произведению' и нечетного числа. Эта гипотеза была опровергнута в 1959 ",' после того, как была построена пара ортогональиых латинск . квадратов порядка 22. Для некоторых значений п существует более двух взаим ортогональных латинских квадратов порядка и (т, е.
таких тинских квадратов, каждая пара которых ортогональна). Ни' используя существование конечных полей порядка о, мы пок" жем, что если число и = д является степенью простого числа, существует о — 1 попарно ортогональных латинских квадра . порядка д. 9.83.
Теорема. Пусть а, = О, а„а„..., а, — злемен поля Кч, Тогда таблааы вада 4 4. Приложения к комбиннторике Так как а» чь а, получаем, что аьл = — ав,, ае т =- аьл и, следовательно, ! === д, / = — !и Таким образом, все упорядоченные пары одинаково расположенных элементов в Е» и Л являются различными, т. е, Л» и Е ортогональны. П 8.84. Пример. Ниже приводится множество из 4 попарно ортогональных латинских квадратов порядка 5, построенных методом, указанным в теореме 9.83: Следующий результат, рассматривающий случай латинских квадратов порядка п, когда п не является степенью простого числа, доказывается методом, аналогичным доказательству теоремы 9.83. 9.85.
Теорема. Пусть уо ..„в, — степени простых чисел, и пусть а~~о = О, аги аы! агп ао =,а,,а,, ...,а... — элемента поля ген Определим э-наборы Ь» = '!а»н', .... аЯ, гдг 0 (Ь (г = ппп !о; — 1), ~сесе и пусть Ь„„, ..., Ье о п = д, ... о„— всг остальные э-наборы, которые можно получить, беря в качестве ~'-й координаты элемент поля ген Оа множестве этих э-наборов можно определить операции покоординатного сложения и умножения. Тогда таблицы вида Ь, Ь,Ь, + Ь, Ь„Ь, + Ь, Ье к Ь Ь,+Ь„, Ь Ь,+Ь„ о Ь Ь, Ь»Ь, 8=1,..., г, Ь»Ь„» Ь»Ь„, + Ь» ...
Ь»Ь„.л+ Ьи к 0 1 2 3 44 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 О 1 2 3 0 1 2 3 44 3 4 0 1 2 ! 2 3 4 0 4 0 1 2 3 2 3 4 О 1 О 1 2 3 4 2 3 4 0 ! 4 0 1 2 3 1 2 3 4 О 3 4 0 ! 2 0 1 2 3 4 4 О 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 О 640 Гл. 9. Прилол«ения конечных полей образуют множество из г попарно ортогональных латински' квадратов порядка и.
Схемы инцидентности и латинские квадраты используютс" при планировании статистических экспериментов. Наприме пусть нам требуется сравнить урожайность и сортов пшениц, на данном типе почвы. Пусть опытный участок представляет с,' бой прямоугольное поле, разбитое на пе участков. Даже если мь». будем очень тщательно выбирать опытное поле, все равно разлнчд ные его участки будут отличаться по плодородию почвы. Поэтому'; если засеять участки первого ряда одним сортом пшеницы, т»»~, может оказаться, что именно первый ряд участков отличается' наиболее высоким плодородием почвы, н мы сделаем неправиль-,"; ный вывод о высокой урожайности этого сорта пшеницы. Нашйч оценки будут более правильными, если засеять участки таким; образом, что один сорт пшеницы будет встречаться по одному.
разу в каждом вертикальном и каждом горизонтальном рядах.". Другими словами, посев и сортов пшеницы надо провести таким.' образом, чтобы получился латинский квадрат порядка и. Часто бывает необходимо одновременно учесть и другие фак-й торы, влияющие на урожайность.
Пусть, например, мы хотим:, использовать п различных видов удобрений и оценить эффектив-", ность нх использования. Тогда мы распределим удобрения и сорта,: пшеницы по и' участкам таким образом, чтобы как размещеииф удобрений, так и размещение сортов пшеницы определяли латка',, скнй квадрат порядка п н чтобы при этом каждый сорт пшениц»я' и каждое удобрение «сходнлись» ровно на одном участке. Такнмй образом, на языке комбинаторики латинские квадраты, соответ'" ствующие размещению сортов пшеницы и размещению видо ', удобрений, должны быть ортогональиы. Аналогичные приме",з пения существуют и для уравновешенных неполных блок-схем." В качестве еще одного примера применения теории конечный,' полей к комбинаторике рассмотрим так называемые матрицы Адв-~ мара.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
