SZEKERES DIFFERENCE SETS



Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin, 7.10.2015


Дифференциальные наборы, это наборы разностей q целых чисел, в которых наблюдается некоторая система, например, одинаковые разности встречаются λ раз. Причем, нам не обязательно рассматривать разности всех чисел между собой, а только разности с k числами. Считается, что впервые особое внимание на них обратил Джеймс Зингер в 1938, а Маршал Холл дал развивающий обзор в 1956 году. Дьёрдь Секереш (см. красивая теорема Секереша-Эрдеша) был фактическим супервизором PhD Дженнифер Себерри.

George Szekeres | PDF Whiteman 1971 | PDF Jennifer 1973 | PDF Yamada 2012
Kotsireas, Koukouvinos, Seberry, 2005 | Fletcher, Gysin, Seberry, 2001
Two border two circulant Hadamard Matrices | Jennifer 2013


Парные дифференциальные наборы Секереша A, B образуются элементами, встречающихся в первом сэте A только с одним знаком, а во втором B – только с двумя. В конечном поле Галуа GF(q) отрицательный элемент имеет значение qa. Для GF(4f+1) такие наборы можно составить, взяв в каждый сэт A или B значения двух экспонент (одна экспонента общая) x4t+i; t=0 ,..., f, i – номер экспоненты.

Получаем в итоге два множества A, B неуравновешенных и уравновешенных по знакам элементов, описывающих значения –1 бинарных последовательностей a, b пары циклических матриц. Если q – простое целое число, то возможно построение соответствующей матрица Адамара из бициклической матрицы удвоенного порядка 2q, и двойной каймы. Порядок подходящего поля отличается от квадрата степени простого числа на 4: q=p2+4=5 (mod 8).



Матрицы Адамара порядков 12 и 28



Матрицы Адамара порядков 60 и 108



Дифференциальные наборы Секереша описываются 3 параметрами 2-(q,k,λ), двойка впереди означает парный набор. Первый параметр q – размер задачи, k=2f, λ=2f–1.

Второй пример показывает несколько иной алгоритм расчета пар Секереса, основанный на нахождении точек пересечения экспоненты со смещенными аддитивной добавкой (единицею) ее же значениями.



Матрицы Адамара порядков 12 и 20

Cупружеская пара – Эстер и Дьёрдь Секереши известные математики, работавшие в Австралии. Задача со счастливым концом, названная так Палом Эрдёшем в связи с последующей свадьбой Дьёрдя, показывает насколько неразрывно математика была связана с жизнью Секереша. В 1933 году Дьёрдь и несколько других студентов часто встречались в Будапеште на математических семинарах. На одной из этих встреч Эстер Клейн предложила задачу:

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

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

ПРОПУЩЕННЫЕ ПОРЯДКИ


Пары близких целых. Порядки q=p(p+2), связанные с парами целых, не годятся для построения полей Галуа, что не препятствие для построения дифференциальных наборов, ряд таких случаев рассмотрел Маршал Холл, Стентон, Спротт и другие. Первый параметр q – размер задачи, k=(q–1)/2, λ=(q–3)/4. Параметры дифференциальных наборов связаны с параметрами блоков строящихся с их помощью матриц Адамара, например, второй k и третий λ параметры интерпретируются как число единиц в строке и число единиц в каждых двух строках циклического блока.

Блоки A=B базируются на паре экспонент с основаниями, равными значениям x=0 mod (p+2) и y – общему примитивному корню по mod (p) и mod (p+2), причем x=y mod (p). Для p=3, q=15, k=7, λ=3. Первое основание x=5 = 0 mod (5), второе y=2 (примитивный корень по модулям 3 и 5), x=y mod (3). Набор длиною k=7 содержит p=3 значений 5t mod (q), и kp=4 значений 2t mod (q).



Marshall Hall (1955) рассмотрел порядки 15, 35 (и 63)

NICK'S SHORT LIBRARY


Marshall Hall, A survey of difference sets, Proc. Amer. Math. Soc. 7, 1956, pp. 975-986.

R. G. Stanton and D.A. Sprott, A family of difference sets, Canad. J. Math. 10, 1958, pp. 73-77.

Последовательности Галуа. Помимо того, известны последовательности порядков q=2m–1, названные Манфредом Шредером последовательностями Галуа (PDF, 11Mb, см. стр. 322). Шредер, помимо экспонент, рассматривает решения разностных уравнений в поле GF(2m). Матрица Маршала Холла порядка 15, это решение уравнения xk+4=xk+1+xk с начальными условиями x0, x1, x3, x4 (возьмите с рисунка) в GF(24).



Матрицы Адамара порядков 32 и 128 (Galois sequences)


Поле GF(24) имеет размерность 16, генерируемая периодическая последовательность короче на единицу, ссылка на (генераторы, обыденность теории кодирования) [1], стр. 89, 106. Шредер физик, его интересовали периодические модели, волны, всплески.

1) F. J.MacWilliams, N. J. A. Sloane The Theory of Error-Correcting Codes (North-Holland, Amsterdam 1978).

Кососимметричные/симметричные матрицы A=B, с точностью до диагонали, можно посчитать через символы Лежандра, это актуально для случаев q=7, 17, 19, 25, (квадрат), 27 (куб), 31, 37, 43, для 45 нужен Матон, 47, 49 (квадрат). Часть таких матриц имеет необходимую простую циклическую форму.



Матрицы Адамара порядков 16 и 36



Матрицы Адамара порядков 40 и 64



Матрицы Адамара порядков 76 и 88



SYMMETRIC SZEKERES MATRICES CATALOGUE



Матрица Адамара порядка 8



Матрицы Адамара порядков 12 и 20



Матрицы Адамара порядков 24 и 28



Матрицы Адамара порядков 32 и 44



Матрицы Адамара порядков 48 и 60



Матрицы Адамара порядков 68 и 72



Матрицы Адамара порядков 80 и 84



Матрицы Адамара порядков 104 и 108



Rambler's Top100