EXPONENTS & PENDULUMS



Hadamard matrix family catalogue and on-line algorithms
GF(p^m), GF(p^2), GF(27)=GF(3^3), GF(5^m), ..., GF(57^m)

© Nickolay A. Balonin, 20.10.2015


Все эти матрицы, которыми мы занимаемся в каталоге, нечто вроде "объемного" сопровождения чисел. Четные и нечетные по порядку матрицы по разному адаптируются, структурно. Четные норовят какую нибудь деталь присоединить, кайму, или диагональ. А нечетные норовят уровни поменять, значения элементов. Матрицы, будучи тенями чисел, в некотором смысле образуют тени всех известных числовых последовательностей – Мерсенна, Ферма. Мерсенн как то гениально уловил становой хребет, знал, чему имя давать, Ферма тоже.

В примерах подловлено сходство хаотических случайных аттракторов и мультипликативных групп полей Галуа, конечный аттрактор дает первую строку циклических или негациклических форм матриц – перечислены несколько методов расчета. По полочкам разложил тему в ревью.

Динамические системы в полях Галуа, пожалуй что, и обыденность. Чем то надо выделяться, примитивному элементу группы (или квадратичному вычету). Вот он и выделяется. Дает ортогональную, и часто – матрицу Мерсенна, а не Адамара. В развертке дин-процесса. Это как вариативный принцип механики – при естественном движении оптимизируется лагранжиан (разность кинетической и потенциальной энергий). Если привыкнуть, это будет естественным и не вызывать ощущение, что это нечто необычное. Возможно, помимо полей Галуа, есть еще заворачивающие конструкции. Там же дырки то есть, у полей. А в них матрицы преспокойно продолжают существовать.

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



Спирали аммонитов и аттрактор Пуассона


Именно таковы решения некоторых нелинейных дифференциальных уравнений в бесконечномерном трехмерном пространстве, это тоже сорт такой же кривой. 3D нужно, чтобы интегральной кривой было где разместиться без самопересечений. В свое время Лоренц (аттрактор Лоренца) наблюдал бесконечное блуждание интегральной кривой, оказывается, она заметает все поле, прошивает любую точку пространства один раз. В этом заключается подобие циклическим группам, образуемым степенями одного начального элемента (начального условия). В конечном поле так себя ведет тривиальная (казалось бы) линейная система первого порядка, описываемая простым разностным уравнением или показательной функцией (экспонентой, в общем ее толковании), что одно и то же. Нелинейность и обратная связь присутствует в формулах реализации полиномиальной арифметики и в виде квадратического критерия оптимизации.

Резюме. Циклические группы – родственники странных аттракторов. В самом деле, чтобы породить все адамаровы базисы, которые никак не могут ни найти, ни сосчитать, надо быть достаточно странным. Нелинейность сидит в полиномиальной арифметике. У динамических систем "заварот ума" происходит ввиду явной нелинейности. А экспонента с виду безобидный продукт линейной системы. Да, но арифметика то по модулю. Подкручивающая. Вот она и блуждает. Чтобы быть циклической группой или подгруппой, надо, чтобы экспонента обошла все ее точки по разу. Так именно таковы и случайные аттракторы.

Если экспонента описывает (n–1)/2 отрицательных элементов, то в качестве начального условия подходит квадратичный вычет, он порождает своей степенной формой циклическую подгруппу нужного размера. Вот этот "аттрактор" и дает первую строку циклической матрицы. Что такое примитивный элемент? Начало экспоненты. Берем пару экспонент из пары таких начал. Они перекручиваются, как червяки. Им же не деться никуда, с поля. Точки пересечения дают –1, остальные 1. Получается бинарное описание процесса пересечения. Где скрещиваются, там на веревке из 1 бельевая защепка –1. Это и есть алгоритм генерации первой строки негациклических матриц Адамара, если параметры экспонент подобрать. Есть сложность в виде "проектора" (одна из экспонент суммируется с собой, после "остепенения").

КОНСТРУИРУЕМ ПОЛЕ


При обсуждении полиномиальной арифметики термин "простое число" заменяется термином "неприводимый многочлен" (нередуцируемый). Полином называется неприводимым, если его нельзя представить в виде двух других полиномов (конечно же, кроме 1 и самого полинома). Полином x2 + 1 неприводим над целыми числами, это касается также любого конечного поля. Для поля Галуа GF(pm) в качестве "модулей" используются трехчлены xm+x+1, содержат много нулевых коэффициентов.

Полином, который в образованном с помощью неприводимого полинома поле является генератором (степенной функции, прошивающей все поле без самопересечений), называется примитивным или базовым (элементом поля), все его коэффициенты взаимно просты.

Если р простое и необходимо найти все примитивные элементы поля GF(р), то достаточно найти один, а дальше возводить его в степени взаимно простые с числом p–1 – так получатся все примитивные элементы, их количество – значение функции Эйлера φ(р–1). Не занимаясь оптимизацией процесса, можно брать элемент поля наудачу (опуская квадратичные вычеты), степенная функция искомого элемента приводит обратно не ранее исчерпания размера всего поля: xр–1=1 mod p, малая теорема Ферма (для произвольного p имеем xφ(р)=1 mod p, φ(р) – количество чисел взаимно простых с р (меньших его), для простых чисел функция Эйлера φ(р)=р–1, что не возьми, все подходит).

Генератор мультипликативной группы конечного поля GF(pm) называется примитивным элементом или первообразным корнем степени pm–1, так как xpm–1=1 mod p. Примитивный многочлен над полем GF(p) именуют минимальным многочленом примитивного элемента поля GF(pm). Обзор конечных полей смотрите тут, для GF(3): x3+2x+1=0 дает x3=x+2, см. on line поиск примитивных полиномов.


Поля Галуа GF(pm). Специфику этих полей составляет то, что единственное четная образующая p=2 в них противопоставлена всем остальным нечетным 3, 5, 7, .. (простым нечетным числам).

Поле GF(2m) выделено тем, что если даже pm–1 в нем не простое число, все равно есть метод расчета циклического блока такого размера с помощью реакции динамической системы порядка m в GF(2). Строки блочной матрицы порядка n=2m рассчитываются через эволюции длины 2m–1 динамической системы (сдвигового регистра) порядка m с переменными вектора состояния в поле GF(2). Для остальных полей работа в GF(p) не приводит к бинарной последовательности, для расчета, возможно, подойдут две последовательности с целью генерации бинарной матрицы посредством констатации их пересечений. При p=2m–1 простое GF(p) и сложное GF(2m) поля соседствуют, естественно работать в простом поле. В таком и остальных полях в расчетах фигурируют степенные функции, т.е. реакции динамических систем первого порядка длины pm, всю нагрузку по генерации циклических или бициклических матриц несет арифметика поля.

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



Вспомогательный полином дает веса обратных связей


Чаще всего это xm=sxd+r, при d=1 ко всем m младшим коэффициентам свертки прибавляются все старшие с множителями s, r за исключением крайних членов, к младшему коэффициенту произведения не дотягивается ветвь с весом s, к старшему коэффициенту – ветвь с весом r. При d>1 в этом простом алгоритме возникают поправки.



Потребность в s-ветви отпадает совсем для GF(p2), p – нечетное простое, произведение пары двухкомпонентных чисел (a,b)(с,d)=(aсrbd),(ad+bc). Это поле сходно с полем комплексных чисел, где –r – аналог –1 (квадрат невычета). Параметр r=2 помимо случаев r=1, p+1 кратно 4, и r=3, p+1 кратно 6. Для более сложных полей параметры задаются таблично.

 p 
 m 
 d 
 s 
 r 
2
2
1
1
1
2
3
1
1
1
2
4
1
1
1
2
5
2
1
1
2
6
1
1
1
2
7
1
1
1
2
8
5
1
1
3
3
1
1
1
3
4
1
1
1
3
5
1
1
1
3
6
1
1
1
3
7
2
1
2
3
8
2
1
1
3
9
5
1
1
5
3
1
1
1
5
4
1
1
1
5
5
1
1
1
5
6
1
1
3
5
7
1
1
2
5
8
1
0
2
 p 
 m 
 d 
 s 
 r 
7
3
1
0
2
7
4
1
1
3
7
5
1
1
3
7
6
1
0
3
7
7
1
1
1
7
8
1
1
1
7
9
1
0
2
7
 10 
1
2
1
 11 
3
1
1
3
 11 
4
1
1
6
 11 
5
1
1
1
 11 
6
1
1
1
 13 
3
1
0
2
 13 
4
1
0
2
 13 
5
1
1
1
 13 
6
1
0
2
 17 
3
1
1
2
 17 
4
1
0
3
 17 
5
1
1
6
 17 
6
1
1
4
 p 
 m 
 d 
 s 
 r 
 19 
3
1
0
2
 19 
4
1
1
1
 19 
5
1
1
3
 23 
3
1
1
4
 23 
4
1
1
3
 23 
5
1
1
2
 29 
3
1
1
1
 29 
4
1
1
1
 31 
3
1
0
3
 31 
4
1
1
1
 37 
3
1
0
2
 37 
4
1
1
1
 41 
3
1
0
2
 41 
4
1
1
7
 47 
3
1
1
1
 47 
4
1
1
1
 53 
3
1
1
4
 53 
4
1
1
2
 57 
3
1
1
8
 57 
4
1
1
5


Поиск весовых коэффициентов вспомогательного многочлена xm=sxd+r использует в качестве настройки номер алгоритма GFs=s, GFr=r, GFd=d<mпоказатель степени компоненты с параметром s. Вне таблицы [3,10,2,1,2],[3,11,2,1,2],[3,12,2,1,1][5,8,1,0,2],[5,9,4,1,4],[5,10,2,1,2],[11,7,1,1,4], [59,3,1,1,8].

Пример умножения. Разберем ниже случай xm=sxm –1+1. Обозначим как Ai, Bi усеченные до значения индекса i векторы A, B; Ak, Bk – то же самое, но компоненты взяты, напротив, с позиции k до завершения векторов (остаточные части векторов). Подчеркиванием обозначим расположение компонент в обратном порядке (флип-инверсию). Тогда формулы заметно упрощаются, первые компоненты i=0,...,m–2 рассчитываются отдельно от последней

ci=ATiBiTi+1Bi+1, cm–1Tm–1Bi+1


где Δi+1 – вектор с компонентами ATkSk, k меняется от i+1 до максимума; Sk=(s0, s1, ...) – вектор соответстующего Ak размера, зависящий от настраиваемого параметра s=2 (для полей малого размера, в табличке функции инициализации тестовой программы можно найти иные значения).

В покоординатной записи это имеет вид cik=0,iakbikk=i+1,m–1bm+ikΣj=k,m–1ajrjk, cm–1k=0,m–1bm–1–kΣj=k,m–1ajrkj.

СООТВЕТСТВИЕ ПОЛЕЙ ГАЛУА И МАТРИЦ


Основное число, в расчетах матриц, размер блока, задающий прямо или косвенно (через степень) размер образующей p конечного поля Галуа GF(pm). Все остальные параметры вторичны и менее значимы, это понятно и по философии подхода. Иначе придется признавать связность неких целых чисел, через эту модель. А это должно быть заложено в самой числовой системе. Быть свойством чисел, как у близких пар целых.

Наблюдается и структурное соответствие блоков характеру конечного поля. Циклическим блокам нечетного порядка p отвечают простые числа (произведения пар простых чисел) с расчетом параметров блоков в полях Галуа GF(p), а негациклическим матрицам четного порядка p+1 отвечают гиперкомплексные числа размера m>1 с расчетом блоков в полях Галуа GF(pm).

Иными словами, ортогональные циклические блоки с каймой, это порождения простых полей. Например, 27 не простое число – нет циклического блока с каймой размера 27+1=28. Но оно равно 33, где 3 простое – есть ортогональная негациклическая матрица размера 28. И циклические и негациклические матрицы – теплицевы, но второй вариант отличается от первого.

Циклические блоки, однако, охватывают порядки, равные произведению простых чисел-близнецов, поэтому есть ортогональные циклические матрицы с каймой размеров 16=3*5+1, 36=5*7+1, но есть и дополнение 64=7*9+1 (дает сдвиговый регистр ниже, хотя 9 – не простое число), а вот размеру 100=9*11+1 отвечает блочная циклическая матрица, причем негациклических матриц нет на этих порядках!

Важное свойство расчетов матриц состоит в инвариантности вычислительных систем к параметрам экспонент, с помощью которых вычисляются матрицы. Она имеет место быть и у рядов Фурье: при кратности частот ортогональных функций sin(ωt), sin(2ωt), sin(3ωt), ... наблюдается инвариантность свойства ортогональности к частоте ω.

В математике часты "ссоры" из-за наименований. Core – ядро или "основа" (в переводе) матрицы, матрица без каймы. В то же время, классически ядром матрицы называется пространство векторов, умножение которых на матрицу дает ноль. Показательна функция, ее можно называть экспонентой конечного поля (нет трансцендентного основания). В теории групп есть иное понимание "экспоненты", как некого показателя группы. У динамических систем экспонентой называется тривиальное решение, отвечающее выделенному свободному движению. При работе на пересечениях теорий, спорность наименований сказывается.

Дифференциальные наборы, это наборы разностей 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


МЕТОДЫ ГЕНЕРАЦИИ МАТРИЦ МЕРСЕННА


Подведем итог. Всем числам, простым, степеням, числам Мерсенна, числам Ферма, и т.п. отвечают некоторые ортогональные матрицы. После приведения максимальных их элементов к 1, это субоптимальные матрицы локального максимума детерминанта, малоуровневые. Различие в числах Мерсенна простых и сложных выливается в различие структур матриц (один кубик, многоблочность), но есть и важнейшее ограничение сложности структуры. Матрица Мерсенна не сложнее бицикла с каймой, и разнообразие сортов чисел Мерсенна между собой (простые, сложные и т.п.) сводится к разнообразию генераторов бицикла. Подробнее о генераторах матриц ниже, развернем их к матрицам Адамара, матрицы Мерсенна, это они же, но без каймы, в виде ядра с пересчитанным отрицательным элементом.

Балонин Н. А., Сергеев М. Б., Мироновский Л. А. Вычисление матриц Адамара-Мерсенна // Информационно-управляющие системы. 2012. № 5. С. 92–94.

ПОКАЗАТЕЛЬНАЯ ФУНКЦИЯ В GF(q)



Показательная функция xλt в поле Галуа GF(107)


В поле GF(q), q – простое, т.е. при работе с вычислениями по модулю, различают случаи q=2 и q – простое нечетное число. В первом случае, в поле малой амплитуды, сложным поведением отличается динамическая система Xk=FXk–1, m – порядок модели, k – целое, с компонентами вектора состояния в поле GF(2). Этот генератор в виде динамической системы порядка m в состоянии продуцировать функции протяженности 2m–1, т.е. выдавать узкий спектр соответствующих матриц Мерсенна. Существует противоположный подход, когда поле, наоборот, большое GF(q), позволяет разгуляться амплитуде, а динамическая система, напротив, маленькая, порядка 1. Ее выход, показательная функция, на интервале T=(q-1)/2 выдает "дифференциальный набор" чисел с параметрами SBIBD (q, k, λ), т.е. ее номера дают позиции –1 более общей матрицы Мерсенна. И, наконец, степенная функция, т.е. функция, зависящая от основания x2, дает значения, принадлежность к которым чисел x поля GF(q) определяет индексы Лежандра.

Показательная функция в GF(q). В теории конечных полей показательные функции неприводимы, естественно, к зависимости с трансцендентым основанием, используемым в определении классической экспоненты. Этим словом "экспонента" мы будем пользоваться для полезной краткости, как обобщением и аналогом привычной в теории динамических систем (например, маятников), функции. Точно также, нет чисто синусных или косинусных зависимостей, хотя разность или сумма "экспонент" возможны.

Несколько необычно то, что "колебания" в конечном поле присущи не алгебраическим суммам, а показательной функции. Рост ее ограничен размерами поля. Неприложимо к конечному полю понятие псевдослучайной последовательности, поскольку что же в ней такого псевдослучайного, если мы не выходим за размеры поля? Она и есть чисто "случайная" зависимость, "белый шум" – абстракция из смежного раздела математики. Показательная (зависящая от показателя) и показательная (зависящая от основания) показательно-показательные функции распространены для описания элементарных последовательностей, кубиков, из которых собирается конструктив.

Например, позиции "–1" первой строки моноблоков порядков n=q+1 (с каймой): 4, 6, 8, [не 10, ибо 10-1=9], 12, 14, [не 16], 18, 20, 24, [не 26 и 28], 30, 32!, .. , q – простое, рассчитываются с помощью показательной функции xλt (реакции системы первого порядка: 1!). Заметим, что от параметров экспоненты (основания x, показателя степени λ и смещения φ) почти ничего не зависит. Неудачное сочетание параметров генератора, это, скорее, исключение из правил, чем правило. Движение систем непериодично и порождает ортогональную матрицу (в виде блока с каймой), генерируемые числа называют, как отмечалось, в отличие от абстрактного белого шума бесконечной протяженности, псевдослучайной последовательностью.



Skew conference matrices, based on exponent in GF(q)



Роль квадратичных вычетов. Поразительна игра цифр, берем число 7. Берем 1. Начинаем умножать на 4, получаем по модулю 7, числа 1, 4, 16=2, 1, .. Завершилась рано, перед нами подгруппа квадратичных вычетов, она короче на (q–1)/2. Подгруппа из чисел 1, 2, 4 (3-ки мы все числа обойдем). Посмотрим на сдвиговую матрицу Мерсенна 7, она как раз из чисел 1, 2, 4 состоит, это номера отличающихся знаком клеток в первой строке, помимо стартовой, с номером 0.



Skew conference matrices, based on exponent in GF(33)


Для того, чтобы не подбирать основание x, широко практикуется расчет не одной, а всех возможных показательных функций с x от 1, до q–1. Они служат для расчета символов Лежандра, которые равны 1, если x – квадратичный вычет, т. е. его значение встречается среди всех рассчитываемых "экспонент" на втором шаге (среди квадратов), которые только до значений квадратов и рассчитываются. Система квадратичных вычетов и невычетов обладает симметрией или антисимметрией знаков относительно их середины, что сокращает расчет. Как видно, вместо них можно обойтись всего одной экспонентой с основанием x=2, для некоторых порядков это основание повышается. Значения экспоненты дают позиции "–1" в первой строке циклического блока, это удобно, не надо заниматься сравнениями (сравнения заложены в более глубокий слой этого алгоритма, в саму арифметику конечного поля, реализуемую вычислением остатков).

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

Экспонента в конечном поле колеблется, в обычной арифметике мы ее в школе проходим как монотонно возрастающую (описание антитрения) или затухающую (трение) функцию. Модель линейная, но задача квадратичная, поскольку цель движения – получение диагонального матричного квадрата HTH. Система первого порядка, уместнее толковать в интерпретациях ее параметров о разном трении, чем о разных массах (при сильном трении массой пренебрегают, пример – автомобиль на шоссе описывается интегратором, моделью первого порядка). Интерпретации: маятник в среде с сильной вязкостью, катится бильярдный шар с цифрами на боках по столу с изменением темпа (трение или антитрение, это как посмотреть), и цифры, которые он "показывает", являются буквальными координатами –1 генерируемого моноблока. Это динамические системы не гамильтоновы, не консервативные, с трением.

Генераторы блоков матриц Адамара. Обратим внимание, что элементы поля GF(q), q=9=3×3 и т.п., могут быть образованы наборами индексов [0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]. Квадратичные вычеты GF(q) позволяют разделить (значениями символов Лежандра 1 и –1) элементы на принадлежащие квадратичным вычетам и невычетам. Цепочки символов Лежандра разделяются на фрагменты длиной p для построения циклических блоков блочно-циклических матриц Якобсталя.



Матрицы Якобсталя, построенные на блоках Лежандра для GF(9), GF(25)

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

Позиции –1 первой строки моноблока задает не одна, а пара экспонент xt, p значений, yt mod (q), kp значений при k=(q–1)/2, с основаниями x=y mod (p), x=0 mod (p+2), y – примитивный элемент обоих групп GF(p) и GF(p+2), иными словами – общий примитивный корень по mod (p) и mod (p+2).

В этих задачах нет явно выделенной диагонали в виде возможных 0 на диагонали, т. е. возможность построения разновидностей близких по смыслу ортогональных массивов убыла. Это серьезное препятствие, скажем, для процедур умножения порядков таких матриц (не построить витраж). Матрица есть, но она дефектна. Не может иметь потомство.

Пример. Для 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) q = 15, 35 (для 63 нужен иной метод)

РЕШЕНИЯ НА ПЕРЕСЕЧЕНИИ ФУНКЦИЙ


Пересечения – бинарные события, что позволяет, например, работать непосредственно в поле GF(pm). Позиции –1 дают не значения экспоненты, а определяются точками пересечения сигналов – экспонент и алгебраических сумм экспонент, аналогов синусов и косинусов, рассчитанных в количестве, равном размеру блока. В данном случае, для осуществления расчета нужны два примитивных элемента, тогда как ранее игра шла на квадратичных вычетах, дающих укороченную вдвое экспоненту. Большое дыхание, вместо малого. Поле и расчет в нем упрощаются, если длины бинарных последовательностей v уменьшены с четных до нечетных значений применением у блоков каймы. Поэтому, для начала остановимся на бициклической конструкции с каймой.

БИЦИКЛИЧЕСКИЕ МАТРИЦЫ С КАЙМОЙ


Моноцикл (циклическая матрица) не может быть матрицей Адамара порядка больше, чем 4. Бициклические конструкции для ряда относительно более редких порядков есть, но их расчет сопряжен с значительными сложностями. Альтернатива – пожертвовать моноконструкцией в пользу двублочной конструкции с каймой, расчеты ведутся в поле GF(q), p=qm=n–1 – простое число или степень простого числа. В последнем случае арифметика усложняется, например, для p=33=27, p=73=343, но для метода пересечений это несущественно.

Позиции –1 определяются точками пересечения экспоненты xλ0t с суммой xλ1t+xλ2t (для первой последовательности) и разностью xλ1txλ2t (для второй), с аналогами косинусной и синусной зависимостей. В самом деле, расчет разрешим на значениях λ10, λ2=–λ1 mod q. Как и в большинстве таких задач, конкретные значения λ0, λ1 неважны. В простейшем случае λ2=0, λ1=1, т.е. в расчете используется сумма и разность экспоненты с 1, причем она же выступает в роли пороговой функции.

Ниже найденная матрица Адамара трансформируется в матрицу Мерсенна отсечением каймы и изменением отрицательного элемента с –1 до –t/(t+sqrt(t)).

Для степеней 2-ки размер поля GF(2m) на 1 больше размера циклической матрицы, и метод экспонент при варьировании показателей вытягивает рассогласование только до порядка 32. Дружит с этими порядками только сдвиговый регистр порядка m в GF(2) и алгоритм выше при p=n–1 (простое).

a=[1,-1,1,1,-1,-1,1,-1,-1,-1,1,1,1,1,-1]; b=[1,-1,1,1,-1,-1,1,-1,-1,-1,1,1,1,1,-1];

Дружат с полем GF(2m) и первые две первые бициклические матрицы Ферма размеров 5 и 17 (первая может рассматриваться как моноцикл). Так как матрица Ферма как четырехцикл размера 65 существует, не исключено, что этот метод общий для них.


МАТРИЦЫ БЕЗ КАЙМЫ: ЧЕТНЫЕ ДЛИНЫ ПОСЛЕДОВАТЕЛЬНОСТЕЙ


Последовательности бициклических и бинегациклических матриц малых порядков n=2v близки между собой настолько, что они совпадают и известны как последовательности Голея минимальных длин v=2, 10, и 26. Вне связанных с ними порядков n=2v есть довольно много исключений n=12, 24, 28, 36, 44, 48 ..., на которых бициклов попросту нет. Поэтому для стартовых порядков до 20-го включительно генераторы циклических и негациклических конструкций отличаются только настройкой, но не формулами.

НЕГАЦИКЛИЧЕСКИЕ МАТРИЦЫ


Элементы двух функций отображены цветными полосками


При расчете в полях Галуа GF(pm), p – размер образующей связан с длиной последовательности v=p+1. Параметр m задает арифметику, при m=2 она близка арифметике комплексных чисел, но можно брать этот параметр большим. Более того, если длина последовательности согласована с некоторой степенью p=qs простого числа q, вместо поля GF(pm) можно работать в поле GF(qsm), смена образующей не отражается на алгоритме расчета.

Основной вид негациклических матриц – моноблок. Это теплицева матрица, она шире просто циклической, потребность в бицикле возникает лишь для некоторых исключительных порядков. При расчете пар блоков основание x меняется, пороговая функция не нужна, две функции сравниваются сами с собой. Отсутствие каймы учитывается добавкой к экспоненте ее степени v–1 (высокочастотная составляющая, корректор).

Первая функция f1 содержит сумму экспоненты α=xλ1t с ее степенью f1=α+αv–1=C1xλ1t+C2xpλ1t, где λ1=v–1 (нечетное число).

Вторая функция построена на квадрате основания f2=β=x2t, λ2=v (четное число). В таком случае аддитивной добавкой βv–1 в β+βv–1 можно пренебречь, она не меняет расчет. Ради экономии вычислений число рассчитываемых точек квадрата можно сократить вдвое, да и последней точкой можно пренебречь.

Смещение φ=v/2 одинаково для последовательностей негациклических матриц, при расчете пар циклических блоков этот параметр варьируется, он равен, например, v–1 и v–4. Нечетное число, показатель первой экспоненты, можно упростить до тривиума λ1=1, тогда φ=1 и φ=4 для двух циклических блоков, у негациклических блоков эта настройка не меняется. Пересечения первой функции со второй отмечаем –1, это некоторый аналог символов Лежандра.

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



Нарезанная на строки зона пересечения и развертка строки


Для расчетов в поле GF(2m) эта форма тоже не приспособлена, последний порядок – 32, где еще можно видеть бинегацикл (при том, что 1N 128 существует).

БИБЛИОТЕКА МАТРИЦ ПОРЯДКА n=pt+1, GF(p2t)

БИЦИКЛИЧЕСКИЕ МАТРИЦЫ



Latest symmetric H32 and Dragomir's 68


Наличие порога разрешимости – порядок 20, классы матриц, получаемые умножениями, и матрицы – артефакты для особых порядков, характерные черты циклических бициклов. Высокие порядки для бициклов достигаются специфическим умножением стартовых последовательностей на последовательности Голея. Порядки, равные удвоенным размерам 22, 34, .. отсутствующих конференц матриц, проблемны. Причем если бицикла размера 44 вовсе нет, бицикл размера 68 существует. Он особой конструкции и недостижим описанным методом.

Пары Голея универсальны

SZEKERES DIFFERENCE SETS | БИЦИКЛЫ | TOEPLITZ MATRICES


Balonin N. A., Djocovich D. Z. Negaperiodic Golay pairs and Hadamard matrices. // Informatsionno-upravliaiushchie sistemy [Information and Control Systems], 2015, no. 5, pp. 2–17. doi:10.15217/issn1684-8853.2015.5.2

ДИНАМИЧЕСКИЕ СИСТЕМЫ ПОРЯДКА, БОЛЬШЕГО, ЧЕМ 1


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



Круги на воде (сложное в стесненном пространстве) и биллиард (встречи в просторном)


Роль пространства состояний, задающих арифметику, играют конечные поля GF(p) и GF(2). Траектории генераторов искусственного хаоса "развертывает" до матрицы сдвиговый регистр развертки – еще одна динамическая система.

Динамические модели размера m, это, в частности, рекурсии: Xk=FXk–1, k=1, 2, 3, ... Вектор Xk от начального состояния X0 стремится к главному собственному вектору S матрицы F, если система устойчива. Когда доходит, процесс замирает на его воспроизведении. Динамическая система исчерпывает свое разнообразие. Возьмем теперь в качестве выхода системы одну компоненту вектора состояния. Этот колебательный процесс мы заводим в сдвиговый регистр. Запускаем, и сдвиговый регистр заполняет сдвигами циклическую матрицу.



Генератор и сдвиговый регистр, две динамические системы


Заметим, попутно, что сдвиговый регистр тоже описывается моделью Yk=FYk–1, где F – фробениусова матрица. Мы малой динамической системой возбуждаем другую, систему побольше и "без трения", образовав выходом первой системы вектор начального состояния Y0 второй. Если матрица, заполненная сдвиговым регистром, ортогональна, она такова же, как и матрица Адамара. Обобщает ее.

Констатируем. Динамическая система порядка m исчерпывает свое разнообразие за v=2m–1 шагов. Ее выход – процесс – с помощью сдвигового регистра (модель волнообразования бассейна, простая, тоже, динамическая) мы заполняем матрицу. Добавляем кайму. И это дает матрицу Адамара.


Уравнения динамических систем в GF(2). Дискретная модель маятника Xk=FXk–1, m=2 – порядок модели, k – целое, описывает все те же колебания маятника от начального состояния, где параметры фробениусовой матрицы соответствующим образом пересчитываются, чтобы сохранить не только качественное, но и количественное подобия моделей. Наращивая размер вдвое, мы переходим к модели, восходящей в первооснове своей к двузвенной конструкции маятника (к модели двойного маятника). В более общем случае перед нами предстает модель колебания нити или тросовой системы, для которой можно брать в рассмотрение четные и нечетные размеры модели динамической системы.

Генераторы последовательностей в GF(2m). Рассмотрим динамическую систему Xk=FXk–1 с элементами и вектором состояния, определенными в поле GF(2), X0=[a0, a1, … , am–1]T – вектор ее начального состояния, ak = CXk, при С=[1, 0, … , 0, 0], – выход.

Модель дает бинарную последовательность a=[a0, a1, … , av–1] элементов со значениями {0, 1}, где первые m членов последовательности равны элементам вектора начального состояния, а остальные vm элементов дополняют значения выхода динамической системы. Последовательности длины n=v+1=2m, состоящие из 1 и продуктов циклического сдвига a, можно рассматривать, в свою очередь, как элементы поля GF(2m).

Вместе с единичным элементом, они образуют матрицу A с одной каймой и циклическим основанием, которая переходит в матрицу Адамара при замене 0 на –1 при подходящем выборе вектора начального состояния в пространстве состояний.



Матрицы Адамара порядков n=2m: 16 и 32


Порядки матриц n=2m известны как сильвестровы, сильвестрова конструкция образуется вложением матрицы Адамара в самою себя, но при вложении не получается циклическая структура, порождаемая динамическими моделями осцилляций. Тем не менее, это матрицы эквивалентные, см. линк ниже. Отметим, что матрицу порядка 16 не найти через символы Лежандра, поскольку 15 – не простое число.

PSEUDO-NOISE MATRICES


Преимущество этого метода поиска перед прямым перебором знаков элементов бинарной последовательности длины n состоит в том, что n заметно больше 2m – количества неизвестных параметры динамической системы и вектора ее начального состояния.

Генераторы усекаемых последовательностей. Для n, отличных от 2m (и в случае модификации каймы), порядок осциллирующей динамической системы s перестает отвечать размеру заполняемой ее колебаниями матрицы, что не означает невозможности найти матрицу Адамара. В таком случае всего лишь сужаются размеры области параметров фробениусовой матрицы, т.е. число маятниковых систем, и области начальных состояний, из которых построение возможно. Эта тактика годится для систем, чьи размеры согласованы с простыми числами.

Генераторы усекаемых последовательностей с коррекцией. К генератору матриц полезно добавить алгоритм коррекции ошибок ортогональности. Отыскав s параметров приемлемой динамической системы, с одним начальным состоянием, далее мы ищем другие начальные состояния.



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


Отметим, что матрица порядка 36, 35 отвечает произведению двух близких целых, ищется плохо: похоже, решение единственно.

a=[-1,-1,1,1,1,-1,1,-1,-1,1,-1,-1,1,1,-1,1,-1,1,-1,-1,-1,-1,1,-1,-1,1,1,1,-1,1,1,1,1,1,-1];

Найдено: n=36 s=12 IS=5 h/hmin=1/1.05 max=4 tick=13107 y1=[1,-1,1,-1,1,1,1,-1,-1,-1,-1,-1]; s=16 y1=[-1,-1,-1,-1,-1,1,1,-1,-1,1,-1,1,1,1,1,1] or y1=[1,-1,1,1,-1,-1,-1,1,-1,-1,-1,1,-1,1,-1,1]; h/hmin=1/1.05 max=4 tick=4819.

DYNAMIC MODEL IN GF(3)





Trinary sequences based matrices W(14,13) and W(14,10)



Бициркулянты. Матрица порядка 36, столь редкая, как выше, встречается заметно чаще, если искать ее в форме бициклической матрицы с двойной каймой. По сути, проблема разрешима привлечением пары комплиментарных маятниковых систем порядка 18 (что альтернативно поиску конференц-матрицы).



Матрица Адамара 36 с каймой и парой клеток – симметрична


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



Несимметричная и симметричная конструкции бицикла H32

Для бициклических конструкций основания процедуры симметризации и антисимметризации дает теорема Секереша, посвященная свойствам знакоуравновешенных и неуравновешенных последовательностей.

В том случае, если A – в принципе несимметричная матрица, симметричная основа от генератора будет порождать решения с близкими к симметрии (или антисимметрии, по выбору) вариантами.

Сложные матрицы. Далеко не все матрицы просто устроены, в частности, это касается матриц абсолютного максимума детерминанта нечетных порядков, для четных порядков известны аналогичные проблемы у конференц матриц порядков 46 (конструкция Матона), 66, 86, два последних не разрешены до сих пор. Матрица максимума детерминанта порядка 11, например, имеет тройной бордюр и сэт различных по размерам циклических блоков.



Матрица максимума детерминанта 11


МАТЕМАТИКА И ИНТУИЦИЯ


Об этом задумывался еще и Адамар, в своем обзоре роли интуиции в математике. И Пенроуз, блуждая вокруг "изобретение или открытие". Когда плотник вытесывает из болванки куклу, он изобретает. Но когда он ощупью находит во тьме куклу, он ее открывает.

Как только Галуа придумал полиномиальную обратную связь, что, конечно же, не столь уж далеко уводит нас от совершенно общей идеи модульной арифметики, так моментально объективно стала существовать вся эта огромная числовая система со всеми ее неизвестными пока коэффициентами, и нанизанными на них матрицами – негациклическими матрицами Адамара.

Был ли это акт творения? Возможно, даже, и нет, поскольку вычисления по модулю были заложены еще в индийскую арифметику, с ее потенциальной возможностью замыкания переносом 1-ки вместо старшего разряда в младший. Выходит, что Галуа весьма вторичен и зависит от каких то там неведомых индийских математиков, чей след теряется в глубинах веков. Идея переноса 1 из младшего разряда в старший, это, опять таки, не более, чем идея переливания воды в серии кувшинов, из кувшина в кувшин, с образованием цепочки фонтанов и подъемом воды наверх, согласно канонам индийской математики нужно "просто смотреть". На эти сады Семирамиды.

Вне полей Галуа нет и согласованных с ними в размерах негациклических матриц Адамара, или, тех же размеров, что и поля, матриц Мерсенна. Но так как есть матрицы с прочими структурами, логично заключить, что есть и не понятые еще числовые структуры, сходные с полями Галуа. В частности, полно матриц, построенных на произведениях, это специфическое опушение еще полей Галуа. Формулы Скарпи, Кронекера и т.п. Допустим, мы принимаем во внимание историю гипотезу Таниямы. Гипотеза Таниямы, это пример необъяснимой, для математиков середины прошлого века, связи двух разных по своей природе математических объектов – когда есть модулярная форма, есть и эллиптическая кривая. И наоборот. У нас аналогичная совершенно вещь. Если есть число Мерсенна, то есть и матрица Мерсенна.

Так как в числах Мерсенна дырок нет, то ... а далее все раскручивается так, что поля Галуа, с их экспонентами-спиралями, это только часть – обозримая – этого математического клубка.

Гипотеза, более полная, говорит, что числовой системе, числам, во всех ее сложности вторит система ортогональных матриц и базисов. Это естественно. Числам Мерсенна отвечают матрицы Мерсенна.Числам Ферма отвечают матрицы Ферма. И т.п., мы перечисляем признаки таких матриц и обращаем внимание, как и Адамар, на оптимальность или субоптимальность матриц по детерминанту.

А далее начинает работать грандиозная мельница оптимизации. Ведь оптимизация – экзистенциальная вещь. Не существует для точки. Обязательно нужна вторая. А вторая точка – это точка ряда, т.е. иррациональное число.

Так появляются, из небытия, изобретенные ли, открытые ли, как судить, малоуровневые субоптимальные ортогональные по столбцам матрицы с иррациональными элементами, отвечающими точкам числовой оси, знаменитым числам Мерсенна. Простым числам Мерсенна отвечают матрицы относительно простой структуры, более сложное отображается блочными матрицами, но в любом случае сохраняется общий для всех этих матриц иррациональный уровень. Кроме того, есть понятие ограниченной сложности структуры, все матрицы Мерсенна, и простые и сложные, можно уложить в рамки окаймленного бицикла. Все остальное – более второпоказательные детали расчета матриц, которые мы рассматриваем.

ГИПОТЕЗА ЮТАКИ ТАНИЯМЫ


Модулярные формы появляются в различных обличьях, но каждую из форм можно представить в виде бесконечной суммы слагаемых специального вида, которые и отличают одну форму от другой. Эти бесконечные ряды, с помощью которых модулярная форма задается однозначно, называют модулярными рядами, или M-рядами.

Подобно тому, как E-ряды служат своего рода ДНК для эллиптических кривых, M-ряды играют роль ДНК для модулярных форм. Изменяя слагаемые M-ряда можно породить совершенно другую, но столь же симметричную, модулярную форму или полностью разрушить симметрию и создать новый объект, который не является модулярной формой. Если слагаемые выбраны произвольно, то построенный объект скорее всего будет обладать малой симметрией или даже будет полностью асимметричным.

Модулярные формы сами по себе играют весьма важную роль в математике. Они никак не связаны с предметом исследований Уайлса в Кембридже – эллиптическими кривыми. Модулярная форма — объект необычайно сложный, открытый только в XIX веке и ставший предметом пристального изучения главным образом из-за его симметрии. Кубические уравнения, соответствующие эллиптическим кривым, были известны с античных времен и не были никак связаны с симметрией.

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

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

Это открытие было поразительным, потому что не было никакой видимой причины, по которой модулярную форму можно было связать с эллиптической кривой. Однако, математические ДНК (E- и M-ряды), составляющие самую сущность обоих математических объектов, оказались тождественными.

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

Сингх о доказательсте теоремы Ферма


ДИНАМИЧЕСКИЕ СИСТЕМЫ


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

Наиболее простая и доходчивая линейная динамическая модель периодического или близкому к перидическому движения – модель маятника, которая на случай учета трения имеет вид T2x''+2ξTx'+x=0, где T=(L/g)1/2 – постоянная времени динамической системы с периодом колебаний 2πT, L – длина маятника, g – величина ускорения свободного падения, ξ≤1 – коэффициент демпфирования, характеризующий трение.

Модель принято сводить к матричному уравнению X'=FX в пространстве состояний X=(x1, x2) с переменными x1 = x, x2 = x' и матрицей в форме Фробениуса F=[0 1;f0 f1], f0=–1/T2, f1=–2ξ/T. Эта динамическая модель на промежутке времени T0 описывает затухающие колебания x=x(t) с частотой ω0=1/T, которые в некоторых случаях нам будет удобно противопоставлять инверсному, перевернутому во времени, процессу u=x(T0t).



Процессы u=x(T0t) и x=x(t) динамической системы


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

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

Когда мы работаем в арифметике 1, –1, то она и есть блок матрицы Адамара, нужны только стенки из 1-к. Буквально напоминает бассейн. Оказывается, что для порядков 2, 4, 8, 16, 32, .. где мы кронекеровым произведением получаем матрицы друг за другом, но вида Сильвестра, где нет цикличности, динамические системы малых порядков s генерируют верхнюю строчку циклического блока матрицы Адамара размера N=2s–1.

Это очень похоже на образование песчаных дюн, стоячих полосок песка на дне реки. Динамическая система (генератор) вступает в своеобразный резонанс с полостью. Резонанс полости образует в ней стоячие волны. Впервые характерные для матриц Адамара порядки обнаружил акустик Манфред Шредер. Шредера емкости и заполнения живо интересовало. Где то, что то, вроде глиняной свистульки, внутри горошина мотается. Вода с горошиной, это система один. А полость свистульки заполняют волны. Возбуждаем диссипативную систему. А она заряжает полость колебаниями.

Это напоминает и электромагнитную волну. Есть осциллятор. Контур электрический. Есть испускаемая им волна, заполняющая пространство. И даже проблемы те же – сдвиговый регистр мало годится на роль модели упругости среды. Хотя возбуждаемая система может ведь быть и посложнее. Кроме того, хорошо известны генераторы ортогональных функций на базе пространства состояний системы в сбалансированной канонической форме. Увы, не в конечном пространстве, но корни там.

ELECTRONIC EDITION


Balonin N. A., Seberry, Jennifer. Visualizing Hadamard Matrices: the Propus Construction, Electronic edition, 2014.

N. A. Balonin, Jennifer Seberry Conference Matrices with Two Borders and Four Circulants, Electronic edition, 2014.

N. A. Balonin, Remarks on pendulums in GF(2), 2015, 7 pages. Алгоритм ищет стартовые матрицы, опираясь на рекурсии [2] в полях Галуа и дожимает их алгоритмом оптимизации детерминанта.

МАТРИЦЫ АДАМАРА И КРИТСКИЕ МАТРИЦЫ


N. A. Balonin and Jennifer Seberry, Remarks on extremal and maximum determinant matrices with moduli of real entries ≤ 1 // Informatsionno-upravliaiushchie sistemy, 2014, № 5 (71), pp. 2–4.

Балонин Н. А., Мироновский Л. А. Матрицы Адамара нечетного порядка // Информационно-управляющие системы. 2006, № 3. C. 46–50.

Балонин Н. А., Джокович Д. Ж. Симметрия двуциклических матриц Адамара и периодические пары Голея. // Информационно-управляющие системы. 2015. № 3. С. 2–16.

Балонин Н. А. О существовании матриц Мерсенна 11-го и 19-го порядков // Информационно-управляющие системы. 2013. № 2. С. 90–91.

Балонин Н. А., Сергеев М. Б. К вопросу существования матриц Адамара и Мерсенна // Информационно-управляющие системы. 2013. № 5. С. 2–8.

Балонин Н. А., Сергеев М. Б. Матрица золотого сечения G10 // Информационно-управляющие системы. 2013. № 6. С. 2–5.

Балонин Н. А., Сергеев М. Б. Матрицы локального максимума детерминанта // Информационно-управляющие системы. 2014. № 1. С. 2–15.

Rambler's Top100