Задаёт ли таблица чисел группу?

[B@R5uk]

Имеется таблица чисел размера N на N. Столбцы и строки нумеруются от 1 сверху вниз и слева направо. В первом столбце и строке стоят числа от 1 до N (номера, соответственно, строк и столбцов). Во всех столбцах и строках каждое число от 1 до N встречается ровно один раз. Требуется доказать, что такая таблица чисел задаёт группу на множестве чисел от 1 до N с групповой операцией, которая ставит паре чисел a и b в соответствие число из таблицы, стоящее в строке a в позиции b (столбец b).

Мои соображения следующие. По определению, группа — это множество с бинарной операцией на нём, удовлетворяющее трём условиям:
1) ассоциативность операции;
2) наличие нейтрального элемента;
3) наличие обратного элемента.

Множество и бинарная операция в наличии. Нейтральным элементом является единица: поскольку в первом столбце стоят номера строк, а в первой строке, соответственно, — номера столбцов, операция с единицей (слева или справа) даёт исходное число. Поскольку в каждой строке и столбце имеется единица (каждое число встречается один раз), требование на обратный элемент тоже удовлетворено.

Проблема с ассоциативностью. Без понятия как с ней подойти. В какую сторону копать? От противного?

[dgwuqtj]

Так это и неверно, есть неассоциативные лупы.

[B@R5uk]

О! Забавно. И минимальный контрпример будет таким:

1 2 3 4 5
2 1 4 5 3
3 5 1 2 4
4 3 5 1 2
5 4 2 3 1

Каждый элемент себе обратный, операция неаблева и неассоциативная:

$$(2*3)*5=4*5=2\ne 5=2*4=2*(3*5)$$

dgwuqtj, спасибо.

Правда теперь у меня вопрос: какое условие добавить к требованиям в первом посте, чтобы выявить именно группу, но не делать при этом брутфорс с $4N^3$ операциями умножения?

[dgwuqtj]

B@R5uk в сообщении #1639665 писал(а):

какое условие добавить к требованиям в первом посте, чтобы выявить именно группу, но не делать при этом брутфорс с $4N^3$ операциями умножения?

Обозначим таблицу через $(a_{ij})_{i, j = 1}^N$, где $a_{1 i} = a_{i 1} = i$. Есть такой quadrangle criterion: таблица задаёт группу тогда и только тогда, когда из $a_{ik} = a_{i'k'}$, $a_{il} = a_{i'l'}$, $a_{jk} = a_{j'k'}$ следует $a_{jl} = a_{j'l'}$ (для произвольных индексов $i, j, k, l ,i', j', k', l'$). Но это хорошо только для проверки вручную.

С другой стороны, если бы речь шла не про лупы, а про магмы вообще, то есть такой негативный результат. Для всех $N \geq 4$ и всех $x, y, z \in \{1, \ldots, N\}$ существует операция умножения на $\{1, \ldots, N\}$ такая, что тождество $(a b) c = a (b c)$ выполнено в точности для всех троек $(a, b, c) \neq (x, y, z)$. Наличие единицы мало что меняет.

[B@R5uk]

dgwuqtj в сообщении #1639666 писал(а):

quadrangle criterion

Спасибо, не слышал про такое. Правда, не совсем понятно, что фиксируется, а что проверяется.

dgwuqtj в сообщении #1639666 писал(а):

Но это хорошо только для проверки вручную.

Можете наглядно пояснить на примере таблицы для группы $D_8$, например?

1 2 3 4 5 6 7 8 - 1
2 1 4 3 6 5 8 7 - a
3 5 1 7 2 8 4 6 - b
4 6 2 8 1 7 3 5 - ab
5 3 7 1 8 2 6 4 - ba
6 4 8 2 7 1 5 3 - aba
7 8 5 6 3 4 1 2 - bab
8 7 6 5 4 3 2 1 - abab

[dgwuqtj]

Ну, например, есть прямоугольник с вершинами 1, 3, 5, 7, который в пересечении строк 2 и 3 со столбцами 2 и 4. Есть также строки 6 и 2, пересекающие 6 и 8 по прямоугольнику, у которого 3 вершины такие же: 1, 3, 5. Последняя вершина тоже должна быть 7, тут всё хорошо. И аналогично ещё кучу прямоугольников проверить. Кажется, для порядка 8 это всё же слишком медленно. Может, есть и какие-то специализированные алгоритмы, я не в курсе.

[B@R5uk]

dgwuqtj в сообщении #1639666 писал(а):

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

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

-- 19.05.2024, 21:39 --

dgwuqtj в сообщении #1639675 писал(а):

есть прямоугольник с вершинами 1, 3, 5, 7... Последняя вершина тоже должна быть 7

Спасибо, понял. Рассматриваются пары прямоугольников с одинаковыми тройками вершин, четвёртая тоже должна совпадать.

[dgwuqtj]

B@R5uk в сообщении #1639677 писал(а):

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

Там некоторая явная конструкция, не сильно сложная. Можете посмотреть в Ляпин, Полугруппы, параграф 1.2.

[B@R5uk]

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

Я вот тут, например, обнаружил, что даже проверку равенства

$$a(ba)=(ab)a$$

выкинуть нельзя. Правда, в примере выше оно всегда работает, контрпример должен быть таким:

1 2 3 4 5
2 1 4 5 3
3 5 2 1 4
4 3 5 2 1
5 4 1 3 2

тогда

$$(4*4)*4=2*4=5\ne 3=4*2=4*(4*4)$$

Пока моя рабочая идея заключается в том, чтобы рассмотреть некоторое подмножество A петли L, для которого бинарная операция ассоциативна, добавить к нему новый элемент $b\in L\setminus A$. Если проверку ассоциативности на множестве $A\cup\left\{b\right\}$ можно сделать за линейное время, то в целом задача имеет квадратичную сложность, если же промежуточная проверка требует квадратичное время, то ничего не поделаешь, вся задача будет порядка $O\left(N^3\right)$, но может хотя бы получится коэффициент по-меньше получить.

Вопрос в том, можно ли распространить ассоциативность на новый элемент, воспользовавшись ассоциативностью имеющихся и минимальным числом проверок?

[lek]

B@R5uk в сообщении #1639696 писал(а):

Вопрос в том, можно ли распространить ассоциативность на новый элемент, воспользовавшись ассоциативностью имеющихся и минимальным числом проверок?

Можно, но обычно сразу выбирается порождающее лупу $L$ подмножество $A$. И только потом проверяется ассоциативность операции на $A$, что гарантирует ассоциативность $L$. Подобную проверку можно провести за время $O(N^2log_2N)$ (тест ассоциативности Лайта). Кроме того, есть программа для Mathematica (Light's test).

[B@R5uk]

Так и знал, что здесь есть трюк! Я даже немного негодую на себя за то, что не сообразил сам, так как я использовал этот же трюк для проверки групп и подгрупп на абелевость, нормальность, центральность и так далее. lek, большое СПАСИБО!