Существует ли унив. алгоритм проверки кватернионных тождеств

[Eli]

Еще одна задача, которая кажется мне интересной.

Если мы сравниваем полиномиальные алгебраические выражения от
вещественных или комплексных чисел, мы всегда можем установить
истинность или ложность произвольной формулы с помощью стандартного
школьного алгоритма "приведение подобных".
Допустим, (a+3b)^2 = a^2 + 9b^2 +6ab.
Алгоритм этот прост, универсален и легко превращается в программу.

Что, однако, будет для кватернионов с их некоммутативным умножением?

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

Пояснение.
Проблема имеет не только чистый, но и практический аспект. Я использую
для проверки кватернионных тождеств программу, которая сводит их к паре
комплексных чисел. Далее все понятно. Но при таком сведении каждое
гиперкомплексное число превращается в два. В случае формул допустим степени 16,
объем памяти возрастает в 65 тыс. раз и она просто вылетает.
Если бы нашелся алгоритм прямой проверки кватернионных
тождеств (без сведения их к комплексным), подобная программа могла бы
работать относительно долго, но в пределах разумного количества памяти.

[lofar]

Eli писал(а):

Если мы сравниваем полиномиальные алгебраические выражения от
вещественных или комплексных чисел, мы всегда можем установить
истинность или ложность произвольной формулы с помощью стандартного
школьного алгоритма "приведение подобных".
Допустим, (a+3b)^2 = a^2 + 9b^2 +6ab.

Скобки можно раскрывать и в алгебре кватернионов, другое дело, что в виду отсутствия коммутативности: $(a+3b)^2=a^2+3ab+3ba+9b^2\quad (*)$. Но это тождество не представляет особого интереса, оно выполняется в любой ассоциативной алгебре.

В алгебре кватернионов есть тождества не выполняющиеся во всех других ассоциативных алгебрах, например $(xy-yx)^2z-z(xy-yx)^2=0$ (короче $[[x,y]^2,z]=0$ --- тождество Холла) или $\sum_{\sigma\in S_4}(-1)^{\sigma}x_{\sigma(1)}x_{\sigma(2)}x_{\sigma(3)}x_{\sigma(4)}=0$ (так называемое стандартное тождество степени 4). Вывести эти тождества, раскрывая скобки и приводя подобные, не получится. Чтобы лучше понять различие между этими тождествами и тождеством $(*)$ советую ознакомиться с началами PI-теории (PI = Polynomial Identity). Ключевые слова: полиномиальное тождество, многообразие, T-идеал, свободная алгебра, относительно свободная алгебра. Начать можно отсюда.

Изучение PI-теории позволит Вам лучше понять Вашу проблему. Другое дело, алгоритмическая часть этой науки (базисы Гребнера Т-идеалов) пока что находится в стадии разработки. Поэтому используемый Вами подход, апеллирующий к комплексному представлению, представляется наилучшим выбором на данный момент.

[незваный гость]

А в чем проблема? Вам нужен алгорифм? Так всё просто, как палка. Заменяете каждую переменную суммой $x \to (x_0 + x_1 \bar{i} + x_2 \bar{j} + x_3 \bar{k})$, раскрываете скобки, упрощаете цепочки произведений $i, j, k$ до 0-1 буквенного состояния и проверяете равенство нулю покомпонентно. И вся любовь к трём апельсинам.

Ручками это делать — вспотеешь кувыркаться. Но компьютер — он жалезный.

Меня, правда, смущает слово «прямой» в Вашей постановке задачи. Что такое «прямой» алгорифм, слишком сильно зависит от Вас.

[lofar]

незваный гость писал(а):

Заменяете каждую переменную суммой $x \to (x_0 + x_1 \bar{i} + x_2 \bar{j} + x_3 \bar{k})$...

Насколько я понимаю, Eli делает то же самое, только сводит кватернионы не к четырем действительным переменным, а к двум комплексным, пользуясь представлением

$a+bi+cj+dk\mapsto \left(\begin{array}{cc} E & F\\ -\overline F & \overline E\\ \end{array} \right)$, где $E=a+bi$ и $F=c+di$ --- комплексные числа.

Под «прямым алгоритмом» Eli, по-видимому, имеет в виду процедуру редукции по модулю базиса тождеств алгебры кватернионов, без сведения к комплексным или действительным представлениям.

[Eli]

Я уже писал, что при сведении кватернионов к паре комплексных чисел возникает
проблема нехватки машинной памяти, если степень формы (полинома) хотя бы = 16.
Уж тем более неэффективно водить кватернион к четверке действительных чисел:
тут и память вылетит, и время счета будет безобразным!
Идея в том, что прямой алгоритм, выразимый средствами самой алгебры, может быть
довольно долгим, но осуществимым. Проблема возникла из реальной практики.
Некоторые кватернионные тождества, которые я проверял, при разворачивании
в комплексные числа съедали всю мою оперативную память (два гигабайта однако).

Меня интересует алгоритмическая разрешимость или неразрешимость общей задачи
проверки некоторого полиномиального равенства от кватернионных переменных.
Кажется, что тут недостаточно существования отдельных тождеств типа тождества Хоппа.
Если же эта задача алгоритмически неразрешима (к чему я склоняюсь), то неплохо
было бы это как-то обосновать.

[PSP]

Интересно, а как должны выглядеть алгебраические уравнения, решениями которых были бы кватернионы?

[worm2]

PSP писал(а):

Интересно, а как должны выглядеть алгебраические уравнения, решениями которых были бы кватернионы?

Например, так:

$$axbxc + dxf + g = 0$$

, где a = 9+2i-j+3k, b = -1+2j, c = 4+k, d = 1+i-j-k, f = i+2j, g = -2-i-j+7k.

[PSP]

worm2 писал(а):

PSP писал(а):

Интересно, а как должны выглядеть алгебраические уравнения, решениями которых были бы кватернионы?

Например, так:

$$axbxc + dxf + g = 0$$

, где a = 9+2i-j+3k, b = -1+2j, c = 4+k, d = 1+i-j-k, f = i+2j, g = -2-i-j+7k.

Как я понимаю, это некоторый аналог квадратного уравнения.И как его решать?

[worm2]

Например, записать уравнения отдельно для каждого компонента вектора (x = y+zi+uj+vk) и решать систему из 4-х уравнений 2-го порядка с 4-мя вещественными неизвестными (y, z, u, v).

[PSP]

worm2 писал(а):

Например, записать уравнения отдельно для каждого компонента вектора (x = y+zi+uj+vk) и решать систему из 4-х уравнений 2-го порядка с 4-мя вещественными неизвестными (y, z, u, v).

По моему, есть алгоритм выражения кватерионов через компл числа.
А самый общий вид квадратного ур-ния - через компл числа.Тогда можно через систему 2-х квадратных уравнений выразить?

[незваный гость]

Может ли такое быть, что высота всех базовых тождеств (типа тождества Холла) ограниченна? Я невеликий специалист по кватернионам, но такое предположение выглядит логичным (в связи с конечностью размерности пространства).

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

[Hypokeimenon]

Одним из основных результатов pi-теории является теорема, гласящая, что если алгебра $A$ над полем нулевой характеристики удовлетворяет хотя бы одному полиномиальному тождеству, то все ее полиномиальные тождества следуют из некоторого конечного набора полиномиальных тождеств.

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

Что касается прямой проверки:
Как известно, в алгебрах над полем характеристики $0$ любое тождество эквивалентно некоторому полилинейному ( например $x^2=0$ эквивалентно $x_1x_2 + x_2x_1 = 0$ ),
а полилинейные тождества можно проверять поочередно подставляя вместо переменных элементы базиса.
Проблема в том, что если буква входит в тождество со степенью $n$, то после линеаризации она даст $n!$ слагаемых. ( При реализации проверяющего алгоритма хранить сами слагаемые необязательно, достаточно помечать переменные как симметризованные ).
Т.е. проблема вычисления в фиксированном объеме памяти разрешима, но перебор может занять весьма долгое время

Другая хитрость использует то, что полиномиальные тождества кватернионов в точностью совпадают с полиномиальными тождествами матриц порядка 2. А при проверке матричного тождества с помощью подстановки в него обобщенных матриц, вместо одной из матриц можно подставлять диагональную.
Например, при проверке кватернионного тождества $a^{100}d_1b^2d_2d_3-a^{50}d_1a^{50}bd_2bd_3 = 0$
достаточно вместо $b$ поставить матрицу $\sum_{i,j=1}^2b_{ij}e_{ij}$, вместо $a$ -- диагональную матрицу $a_{11}e_{11}+a_{22}e_{22}$, а вместо $d_i$, т.к. они входят в тождество линейно, поочередно подставлять матричные единички $e_{kl}$.

[lofar]

Пусть $X=\{x_1,x_2,\ldots\}$ --- счетный набор переменных. Используя эти переменные можно составлять ассоциативные полиномы с коэффициентами из $\mathbb R$. Например, $2x_1+1\;$, $x_1x_2x_1+x_2^2+x_{45}\;$, $x_1x_2-x_2x_1\;$. Важно понимать, что в отличие от обычных коммутативных полиномов, переменные переставлять нельзя: $x_1x_2x_1+7$ и $x_1^2x_2+7$ --- разные полиномы. Множество всех ассоциативных полиномов с коэффициентами из $\mathbb R$ обозначается $\mathbb R\!\!<\!\!X\!\!>$ и называется свободной ассоциативной алгеброй.

Пусть $A$ --- произвольная $\mathbb R$-алгебра (алгебра кватернионов если угодно). Ассоциативный полином $f(x_1,x_2,\ldots)$ называется тождеством в $A$ если для любых $a_1, a_2,\ldots\in A$ имеем $f(a_1, a_2, \ldots)=0$. Например, полином $x_1x_2-x_2x_1$ является тождеством в алгебре комплексных чисел и не является тождеством в алгебре кватернионов.

Множество всех тождеств алгебры $A$ обозначается $T(A)$. Ясно, что $T(A)$ --- идеал в $\mathbb R\!\!<\!\!X\!\!>$ (сумма тождеств --- тождество, произведение тождества на полином --- тождество). Важно, что идеал $T(A)$ обладает еще одним свойством: Если $f(x_1, x_2,\ldots)$ лежит в $T(A)$ и $g_1, g_2,\ldots$ --- произвольные ассоциативные полиномы, то $f(g_1, g_2, \ldots)$ тоже принадлежит $T(A)$ (замени в тождестве переменные на полиномы --- получишь тождество). Идеалы с таким свойством называюся вполне характеристическими идеалами или T-идеалами.

Приведенную Eli задачу проверки тождеств можно переформулировать так: "Дан произвольный ассоциативный полином $f(x_1, x_2,\ldots)$, требуется определить лежит ли он в T-идеале $T(\mathbb H)$" (здесь $\mathbb H$ --- алгебра кватернионов). То есть нужно решить задачу принадлежности полинома идеалу.

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

Стандартные базисы T-идеалов были определены В. Н. Латышевым в 2006-м году. Связанная с ними наука крайне сложна, например, до сих пор не известно имеет ли всякий T-идеал конечный стандартный базис (комбинаторная проблема Шпехта). Еще предстоит разработать алгоритмы построения этих базисов, а до тех пор, проверку тождеств придется так или иначе сводить к базисным элементам алгебры.

[Eli]

Можно ли сделать вывод, что предложенная выше проблема существования универсального алгоритма проверки кватернионных тождеств не имеет на сегодня решения в рамках накопленных алгебраических сведений и инструментов?

Может быть здесь скорее нужны не средства алгебры, а какие-то элементы теории алгоритмов?

[Hypokeimenon]

Eli писал(а):

Можно ли сделать вывод, что предложенная выше проблема существования универсального алгоритма проверки кватернионных тождеств не имеет на сегодня решения в рамках накопленных алгебраических сведений и инструментов?

Алгоритм проверки существует и достаточно прост (указан мной выше)