Равенство алгебраических чисел

[aeg]

Xaositect в сообщении #682044 писал(а):

Нет. Следует из результатов Тарского о разрешимости.

Это здорово, а то мне уже начало казаться, что почва уходит из под ног.

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

[nnosipov]

aeg в сообщении #682052 писал(а):

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

Перечислите, иначе просто непонятно, о чём речь. Заодно объясните, что Вы понимаете под "алгебраическим числом в радикалах". Без строгих определений здесь (в вопросе о невозможности чего-либо) вообще нечего обсуждать.

[aeg]

Запись алгебраического числа в радикалах опредляется грамматикой:

$A \to A \sigma A$

$A \to \sqrt [N] A$

$A \to N $

$A \to (A)$

$N \to 1 | 2 | 3 | ... $

$\sigma \to + | - | \cdot | \div $

Описывать преобразования в подобном виде не хочется, хотя это можно было бы сделать, я все же попытаюсь на словах:
1. Вынесение общего множетеля за скобки, раскрытие скобок.
2. Уможение числителя и знаменателя на одно и то же выражение, сокращение числителя и знаменателя на общий множитель.
3. Внесение сомножителей под общий знак корня, разделение корней (степень корня предполагается одинаковой).
4. Приведение подобных слагаемых, то есть слагаемых у которых все сомножители, стоящие под знаком корня совпадают. Соответственно, разделение произведений на подобные слагаемые.
5. Возведение в степень подкоренного выражения с соотвествующим умножением степени корня. Соотвественно, сокращение степеней подкоренного выражения и корня.
6. Объединение вложенных корней в один корень, разделение корня на два вложенных.

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

Наверняка я чего-то упустил, но так или иначе мне кажется в общем понятно о каком наборе преобразований идет речь.

[Xaositect]

aeg в сообщении #682070 писал(а):

Соотвественно, сокращение степеней подкоренного выражения и корня

Стоп.
Тут вылезают модули. Соответственно, в грамматику выражения придется добавить $A\to |A|$ и в преобразования - какой-то способ разобраться с модулем.

[nnosipov]

aeg в сообщении #682070 писал(а):

Описывать преобразования в подобном виде не хочется

Это понятно, но задачу нужно чётко сформулировать (как мне, неспециалисту в матлогике, кажется). Для практических приложений в компьютерной алгебре важен алгоритм проверки равенства $\alpha=0$, где $\alpha$ --- "алгебраическое число в радикалах". Более общая задача --- это упрощения вложенных радикальных выражений. В конкретных системах компьютерной алгебры она как-то решена, но до идеала далеко.

[aeg]

Xaositect в сообщении #682085 писал(а):

Стоп.
Тут вылезают модули

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

-- 10.02.2013, 16:00 --

nnosipov в сообщении #682086 писал(а):

Для практических приложений в компьютерной алгебре важен алгоритм проверки равенства

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

[nnosipov]

Ну, какой-то алгоритм предложить можно. Если $\alpha$ --- "алгебраическое число в радикалах", то $P(\alpha)=0$ для некоторого многочлена $P(x)$ с рациональными коэффициентами. Находим такой многочлен, локализуем его корни, приближённо вычисляем $\alpha$ и сравниваем с найденными корнями. Другое дело --- найти и реализовать алгоритм, который бы всё это делал побыстрее.

[aeg]

nnosipov в сообщении #682101 писал(а):

Ну, какой-то алгоритм предложить можно. Если --- "алгебраическое число в радикалах", то для некоторого многочлена с рациональными коэффициентами. Находим такой многочлен, локализуем его корни, приближённо вычисляем и сравниваем с найденными корнями. Другое дело --- найти и реализовать алгоритм, который бы всё это делал побыстрее.

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

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

[nikvic]

aeg в сообщении #682092 писал(а):

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

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

[nnosipov]

aeg в сообщении #682103 писал(а):

Другое дело, что хотелось бы иметь все же точное решение.

Я имел в виду алгоритм, который именно доказывает равенство $\alpha=0$, если оно имеет место. Здесь всё точно.

[Cash]

nikvic в сообщении #682104 писал(а):

НОД двух многочленов ищется известно как.

Если делать по "известно как", то возникает проблема с ростом коэффициентов. Там экспоненциальный рост количества цифр.