Стол Лейвера

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

Определение

Для любого неотрицательного целого числа n таблица n -я Лейвера — это 2-я таблица Лейвера. ^н × 2 ^н таблица, запись которой в ячейке в строке p и столбце q (1 ≤ p , q ≤ 2 ^н) определяется как ^[1]

L_{n}(p,q):=p\star _{n}q

где $\star _{n}$ — это уникальная бинарная операция, которая удовлетворяет следующим двум уравнениям для всех p , q в {1,...,2 ^н}:

p\star _{n}1=p+1\mod {2^{n}}

( 1 )

и

p\star _{n}(q\star _{n}r)=(p\star _{n}q)\star _{n}(p\star _{n}r).

( 2 )

Примечание. В уравнении ( 1 ) используются обозначения $x{\bmod {2}}^{n}$ означает уникальный член {1,...,2 ^н} конгруэнтно x по модулю 2 ^н.

Уравнение ( 2 ) известно как (левый) закон самораспределения , а множество, наделенное любой бинарной операцией, удовлетворяющей этому закону, называется полкой . Таким образом, n -я таблица Лейвера — это просто таблица умножения уникальной полки ({1,...,2 ^н}, $\star _{n}$ ), который удовлетворяет уравнению ( 1 ).

Примеры : Ниже приведены первые пять таблиц Лейвера. ^[2] т.е. таблицы умножения для полок ({1,...,2 ^н}, $\star _{n}$ ), n = 0, 1, 2, 3, 4:

$\star _{0}$	1
1	1

$\star _{1}$	1	2
1	2	2
2	1	2

$\star _{2}$	1	2	3	4
1	2	4	2	4
2	3	4	3	4
3	4	4	4	4
4	1	2	3	4

$\star _{3}$	1	2	3	4	5	6	7	8
1	2	4	6	8	2	4	6	8
2	3	4	7	8	3	4	7	8
3	4	8	4	8	4	8	4	8
4	5	6	7	8	5	6	7	8
5	6	8	6	8	6	8	6	8
6	7	8	7	8	7	8	7	8
7	8	8	8	8	8	8	8	8
8	1	2	3	4	5	6	7	8

$\star _{4}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	2	12	14	16	2	12	14	16	2	12	14	16	2	12	14	16
2	3	12	15	16	3	12	15	16	3	12	15	16	3	12	15	16
3	4	8	12	16	4	8	12	16	4	8	12	16	4	8	12	16
4	5	6	7	8	13	14	15	16	5	6	7	8	13	14	15	16
5	6	8	14	16	6	8	14	16	6	8	14	16	6	8	14	16
6	7	8	15	16	7	8	15	16	7	8	15	16	7	8	15	16
7	8	16	8	16	8	16	8	16	8	16	8	16	8	16	8	16
8	9	10	11	12	13	14	15	16	9	10	11	12	13	14	15	16
9	10	12	14	16	10	12	14	16	10	12	14	16	10	12	14	16
10	11	12	15	16	11	12	15	16	11	12	15	16	11	12	15	16
11	12	16	12	16	12	16	12	16	12	16	12	16	12	16	12	16
12	13	14	15	16	13	14	15	16	13	14	15	16	13	14	15	16
13	14	16	14	16	14	16	14	16	14	16	14	16	14	16	14	16
14	15	16	15	16	15	16	15	16	15	16	15	16	15	16	15	16
15	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16
16	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

Не существует известного выражения закрытой формы для непосредственного вычисления записей таблицы Лейвера. ^[3] но Патрик Дехорной предлагает простой алгоритм заполнения таблиц Лейвера. ^[4]

Характеристики

Для всех p , q из {1,...,2 ^н}: $\ \ 2^{n}\star _{n}q=q;\ \ p\star _{n}2^{n}=2^{n};\ \ (2^{n}-1)\star _{n}q=2^{n};\ \ p\star _{n}2^{n-1}=2^{n}{\text{ if }}p\neq 2^{n}$ .
Для всех p из {1,...,2 ^н}: $\ \ (p\star _{n}q)_{q=1,2,3,...}$ периодичен с периодом π _n (p), равным степени двойки.
Для всех p из {1,...,2 ^н}: $\ \ (p\star _{n}q)_{q=1,2,3,...,\pi _{n}(p)}$ строго возрастает от $p\star _{n}1=p+1\$ к $\ p\star _{n}\pi _{n}(p)=2^{n}$ .
Для всех p , q : $\ p\star _{n}q=(p+1)^{(q)},{\text{ where }}x^{(1)}=x,\ x^{(k+1)}=x^{(k)}\star _{n}x.$ ^[1]

Являются ли периоды первого ряда неограниченными?

Глядя только на первую строку в n -й таблице Лейвера для n = 0, 1, 2,..., видно, что записи в каждой первой строке являются периодическими с периодом, который всегда равен степени двойки, как уже упоминалось. в свойстве 2 выше. Первые несколько периодов — это 1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, ... (последовательность A098820 в OEIS ). Эта последовательность неубывающая, и в 1995 году Ричард Лейвер доказал, в предположении, что существует ранг в ранг ( большое кардинальное свойство) , что она на самом деле неограниченно возрастает. (Неизвестно, доказуемо ли это также в ZFC без дополнительной аксиомы большого кардинала.) ^[5] Во всяком случае, он растет крайне медленно; Рэндалл Догерти показал, что число 32 не может появиться в этой последовательности (если вообще появится) до тех пор, пока n > A(9, A(8, A(8, 254))), где A обозначает функцию Аккермана–Петера . ^[6]

Ссылки

^ Перейти обратно: ^а ^б Биан, Филипп (2019). «Таблицы Лейвера и комбинаторика». arXiv : 1810.00548 [ math.CO ].
^ Дехорной, Патрик (2014). «Двух- и трехкоциклы для таблиц Лейвера». arXiv : 1401.2335 [ мат.КТ ].
^ Лебедь, Виктория (2014), «Таблицы Лейвера: от теории множеств к теории кос», Ежегодный симпозиум по топологии, Университет Тохоку, Япония (PDF) . См. слайд 8/33.
^ Дехорной, Патрик. Таблицы Лейвера (начиная со слайда 26). Проверено 11 декабря 2018 г.
^ Лейвер, Ричард (1995), «Об алгебре элементарных вложений ранга в себя», Advances in Mathematics , 110 (2): 334–346, doi : 10.1006/aima.1995.1014 , hdl : 10338.dmlcz/127328 , МР 1317621 .
^ Догерти, Рэндалл (1993), «Критические точки в алгебре элементарных вложений», Annals of Pure and Applied Logic , 65 (3): 211–241, arXiv : math.LO/9205202 , doi : 10.1016/0168-0072( 93)90012-3 , МР 1263319 , S2CID 13242324 .

Дальнейшее чтение

Дехорной, Патрик (2001), «Бесконечное как источник знаний», Spectrum of Science Special (1): 86–90 .
Дехорной, Патрик (2004), «Раскраски и приложения диаграмм» (PDF) , Труды Восточноазиатской школы узлов, ссылок и связанных тем , стр. 37–64 .
Полки и бесконечность: https://johncarlosbaez.wordpress.com/2016/05/06/shelves-and-the-infinite/

[Biane19-1] Перейти обратно: ^а ^б Биан, Филипп (2019). «Таблицы Лейвера и комбинаторика». arXiv : 1810.00548 [ math.CO ].

[2] Дехорной, Патрик (2014). «Двух- и трехкоциклы для таблиц Лейвера». arXiv : 1401.2335 [ мат.КТ ].

[3] Лебедь, Виктория (2014), «Таблицы Лейвера: от теории множеств к теории кос», Ежегодный симпозиум по топологии, Университет Тохоку, Япония (PDF) . См. слайд 8/33.

[Dehornoy-4] Дехорной, Патрик. Таблицы Лейвера (начиная со слайда 26). Проверено 11 декабря 2018 г.

[5] Лейвер, Ричард (1995), «Об алгебре элементарных вложений ранга в себя», Advances in Mathematics , 110 (2): 334–346, doi : 10.1006/aima.1995.1014 , hdl : 10338.dmlcz/127328 , МР 1317621 .

[6] Догерти, Рэндалл (1993), «Критические точки в алгебре элементарных вложений», Annals of Pure and Applied Logic , 65 (3): 211–241, arXiv : math.LO/9205202 , doi : 10.1016/0168-0072( 93)90012-3 , МР 1263319 , S2CID 13242324 .

[1]

[2]

[3]

[4]

[5]

[6]