Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
для существования блок-схемы с параметрами b, г, к, X. Однако эти условия
не являются достаточными для ществования соответствующей блок-схемы. Так,
например, веетно, что блок-схем с параметрами у Ь 43, г к -и X - 1 не
существует.
Элементы и блоки симметричной (у, к, Х)-блок-схемы с к X 1 удовлетворяют
условиям, которым должны удовлетш
• "У- Л
УЖ.*'?
IS
и
рять точки и прямые конечной проективной плоскости. Верно обратное. Таким
образом, понятия симметричной (у, к, 1)-блоЩ схемы с к ^ 3 и конечной
проективной плоскости эквталентныЩ Рассмотрим блок-схему из примера 9.73.
Будем рассматрн|| вать элементы этой блок-схемы 0, 1,2, 3, 4, 5, 6 как
целые чисда| по модулю 7. Каждый блок этой схемы обладает тем свойством!!
что разности между различными входящими в него элементами! пробегают все
ненулевые вычеты по модулю 7. Это п к следующему определению.
§ 4. Приложения к комбинаторике
635
9.75. Определение. Множество D - {4Ъ ..., dh}, состоящее из k ^ 2
различных вычетов по модулю v, называется (v, к, Я)-розностным
множеством, если для любого d ф 0 (mod v) существует ровно Я
упорядоченных пар (d^ dj), dh dj?D, таких, ч-ю dj - dj = d (mod v).
Следующий результат устанавливает связь между разностными множествами,
блок-схемами и конечными проективными плоскостями.
9.76. Теорема. Пусть {dt, ..., dk} является (v, к, к)-разностным
множеством. Тогда если в качестве элементов взять все вычеты по модулю и,
а в качестве блоков-множества вида
Bt - \dL 4- /, . . dh /), / - О, I, ..v - I,
Ч
то мы получим симметричную (v, к, Я)-блок-схему с очевидным отношением
инцидентности.
Доказательство. Каждый вычет по модулю у, скажем а, встречается только в
тех блоках, нижний индекс которых равен одной из величин а - dx, .... а -
dk по модулю и. Отсюда получаем, что каждый элемент инцидентен одному и
тому же числу блоков, равному к. Каждая пара различных вычетов но модулю
и, скажем а и с, принадлежит одному блоку Bt тогда и только тогда, когда
а (tm) dt -f t (mod и) и с = dj 4- t (mod v) для некоторых dt и dj.
Следовательно, a - с и dt - dj (mod и). Верно и обратное: еслн пара (dt,
dj) является решением последнего сравнения, to оба элемента а и с
встречаются в блоке Bt, где t = а - dt (mod у). По условию теоремы
имеется ровно Я различных решений вйда (di} dj), поэтому выполнены все
условия для существования симметричной (и, к, Я)-блок-схемы. ?
9.77. Следствие. Пусть dk} является (и, к, \уразностным множеством с к ^
3. Тогда вычеты по модулю и и блоки Sf, t = 0, 1, ..., и- I, определенные
в теореме 9.76, удовлетворяют всем условиям, налагаемым на точки и прямые
конечной проективной плоскости порядка к- 1.
Доказательство. Сформулированное утверждение следует из теоремы 9.76 и
того, что симметричная (и, k, 1)-блок-схема с к ^ 3 является конечной
проективной плоскостью. ?
Из теоремы 9.76 и соотношения (9.10) следует, что параметры разностного
множества и, к и Я связаны тождеством k (к - 1) -
Я (о- 1). Это тождество можно также получить непосредственно из
определения разностного множества.
636
Гл. 9. Приложения конечных полей
•
9.78. Пример. Множество {0, 1, 2, 4, 5, 8, 10}, составленн. из вычетов по
модулю 15, является (15, 7, 3)-разностным множ ством. По теореме 9.76
блоки вида
Я* = f + 1, ^ + 2, 4, t -f 5Л + 8, t + 10},
t - 0, 1, 14,
"1#
•*y
.vSfi
-11
v-'$
образуют симметричную (15, 7, 3)-блок-схему. Ее блоки мож отождествить с
15 плоскостями проективной геометрии PG{
IF2), в то время как все 15 вычетов по модулю 15 отождествляют^!! с
точками той же геометрии. Каждая из этих плоскостей являетеЩ плоскостью
Фа но PG (2, f2). Для каждого блока Bt все его np|f мые можно получить из
прямой
|/, t-fl, t + 4},
принадлежащей плоскости Bt, с помощью циклической nepeei новки
: !& .. •'¦So
¦ -А
t
t 10 V / 8 -v t.
1. 2, 4,
Например, прямые, лежащие в плоскости В0 - {0,
10, 8}, имеют вид
{0, 1, 4}, fl, 2, 5}, {2, 4, 10}, {4, 5, 8}, {5,'.10, 0}, |10} 8, 1
0, 2}.
• 'Д..4
/Щ
ъй,
щ
. \YjW-4
.V
*5 <Р
Примеры разностных множеств можно строить на основе нечных проективных
геометрий. Отождествим, как и в рассу нни, предшествующем примеру 9.71,
точки проективной геб трии PG (т, f9) со степенями элемента а, где а
является митивным элементом поля F^m+ь причем показатели степени э
мента а берутся по модулю v - (qm+l - 1 )l(q- I). Пусть S' произвольная
гиперплоскость в PG (m, fl^). Тогда S имеет цикл и, таким образом, все
гиперплоскости Sh - ahS, h ~ 0, I, v- 1, являются различными, Атак как
число всех гиперплб| костей этого пространства равно у, то ими
исчерпываются все г] пер плоскости пространства PG (m, f?). Таким
образом, привод: мый ниже список является полным списком всех
гиперплоскос проективного пространства PG (т, F?) (в нем точки, лежащие
соответствующей гиперплоскости, задаются соответствующим п казателем
степени элемента а):
Ж
.гол
Sff:
Sx:
dx
d\
1
d%
d% -f 1
t I I
dk
dk -f 1
.! tUW #
%
§ 4, Приложения к комбинаторике
