Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 265

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 259 260 261 262 263 264 < 265 > 266 267 268 269 270 271 .. 371 >> Следующая

637
Здесь к (qm - 1)% - 1) - число точек одной гиперплоскости. Если мы
выделим те строки, которые содержат какое-то конкретное значение, скажем
0, то получим к гиперплоскостей, проходящих через точку а°. Эти к строк
имеют вид
Каждая точка, отличная от а0, встречается в этих к гиперплоскостях
столько раз, сколько имеется различных гиперплоскостей, проходящих через
две различные точки, а именно в % = (qm~x - - !)/(<? - 1) из них. Таким
образом, среди элементов, не стоящих на диагонали, каждый ненулевой вычет
по модулю и встречается ровно X раз. Следовательно, {d^ ..., dk] является
(и, к, ^-разностным множеством. Следующая теорема объединяет полученные
результаты.
9.79. Теорема. Точки любой гиперплоскости пространства PG{m,Tq) образуют
(и, k, X )• разностное множество с параметрами
9.80. Пример. Рассмотрим гиперплоскость проективного пространства PG (3,
lFa) (см. пример 9.71), определяемую уравнением ад - 0. Она содержит
точки Л, В, С, Я, /, J, К. Эти точки можно отождествить со степенями
элемента а, причем соответствующие показатели степени образует (15, 7,
3)-разностное множество (0, 2, 3, 6, 8, 13, 14}. ?
Другим разделом комбинаторики, в котором применяется теория конечных
полей, является теория ортогональных латинских квадратов.
9.81. Определение. Таблица
называется латинским квадратом порядка я, еслн любая строка и любой
столбец этой таблицы содержат ровно по одному разу каждый элемент из
данного множества, содержащего п элементов. Два латинских квадрата (atj)
и (Ьи) порядка п называются орто-гопадьными, если все я* упорядоченных
пар (ац, Ьи) различны.
d\ ¦- d\ d'2 - d\ ... dk - di
d\ - d% d% d% ... dk - tig
638
Гл. 9. Приложении конечных полей
* • .Mk
ш
&
'ф;,;
у
jT4:i
9.82, Теорема, Для любого натурального числа п существуя латинский
квадрат порядка п.
Доказательство. Рассмотрим таблицу (ati), где аи ^ {
4- j (mod п), 1 < аи < п. Тогда из равенства aXj - aih cj что / г у - / -
k (mod п), т. е. / = k (mod л), откуда j так как 1 i, /', k п. Аналогично
из равенства а^ = % дует, что г - k. Таким образом, элементы каждой
строки и кйшё дого столбца все различны.
Ортогональные латинские квадраты впервые изучались Эйл^ ром. Он выдвинул
гипотезу, что не существует пары ортогоиал^ ных латинских квадратов
порядка п, если п равно произведений и нечетного числа. Эта гипотеза была
опровергнута в 1959 ; после того, как была построена пара ортогональных
латинс&Ё квадратов порядка 22.
Для некоторых значений п существует более двух взаим ортогональных
латинских квадратов порядка п (т. е. таких тинских квадратов, каждая пара
которых ортогональна). Ни используя существование конечных полей порядка
q, мы по$ жем, что если число п ----- q является степенью простого числа,
1 существует q - 1 попарно ортогональных латинских квадра порядка q.
9.83. Теорема. Пусть а0 ¦ О, поля fq. Тогда таблицы вида
Ш
а}1 а
а
q-1
элемет
I-'1:.(r)
L
k
Oo ¦ ¦
Я/А '["¦ Й1 •. ад f Vi
aha2 aha2- -h"i ¦ 4~
, UtiOq_i 4~tfi . ahaq-l 4~ ag-l
•Va
/е = 1,
Я
I*
• •> : ¦Л • ч.
•Л**
образуют множество из q - 1 попарно ортогональных лат ских квадратов
порядка q.
Доказательство. Каждая таблица Lhy очевидно, является д
тинским квадратом. Пусть ац] - akai-i 1- a/~i есть (t, /)-й мент
латинского квадрата Lh. Если k Ф mf то предположим, для некоторых 1 -< i,
/, g. h q
,".tA
Up
' У
(ej)", в},"") = (4V, egf").'
T or да
(a$ai_i f a.j-it umajf - &g-i 1 Qmfl-g-1 \ &h-1)
откуда
ah (a(-1 - ag_x) = ah_x
a
}-!•> ttm (ai-l ~~ ag-l) - ah-1 -
¦Щ
иЩ
¦fe
*
OS
Щ
¦'i
•' %w.
.y '.6.ag
§ 4. Приложения к комбинаторике
639
Так как ак Ф ат, получаем, что aUl =*= ag^t ah_x - as_x и, следовательно,
i - g, / = h. Таким образом, все упорядоченные пары одинаково
расположенных элементов в Lk и Lm являются различными, т. е. Lk и Lm
ортогональны. ?
9.84. Пример. Ниже приводится множество из 4 попарно ортогональных
латинских квадратов порядка 5, построенных методом, указанным в теореме
9.83:
Li-
0 1 2 3 4) 0 1 2 3 4
1 2 3 4 0 2 3 4 0 1
2 3 4 0 1 4 4 0 1 2 3
3 4 0 1 2 1 2 3 4 0
4 0 1 2 3 4 3 L 4 0 1 2
0 1 2 3 4' 4 0 1 2 3 4
3 4 0 1 2 4 0 l 2 3
1 2 3 4 0 4 3 4 0 1 2
4 0 1 2 3 Ш 2 3 4 0 1
2 b 3 4 0 1 * 1 • 2 3 4 0 V
?
Следующий результат, рассматривающий случай латинских квадратов порядка
п, когда п не является степенью простого числа, доказывается методом,
аналогичным доказательству теоремы 9.83.
9.85. Теорема. Пусть qx, ..., qs - степени простых чисел, и
пусть
"О - О, Щ , U2 , . - - t aQt~f
элементы поля . Определим s-наборы bk = (4°, * * -• 4S))> где 0 < =
min (qt
l^i^s
1).
и пусть br+u ..., Ьп_ь п = qx ... qs, -все остальные s-наборы, которые
можно получить, беря в качестве i-й координаты элемент поля На множестве
этих s-наборов можно определить
операции покоординатного сложения и умножения. Тогда таблицы
вида
Lh ---
bo
bhb,
Ms
Ьх
bkb, + b! bkb% "Ь bi
* 9 *
bn-1
ЬкЬ\ + bn-i
& A + bn-i
. bkbn_i
Предыдущая << 1 .. 259 260 261 262 263 264 < 265 > 266 267 268 269 270 271 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed