Наименьшее евклидово поле

[george66]

Рассмотрим числа, которые можно получить из рациональных с помощью квадратного корня (из положительных), а также сложения, умножения, вычитания и деления. Например
$\sqrt{(\sqrt 2 + \sqrt 3)}$
Есть ли практически удобный способ сравнивать их по величине? Есть ли нетривиальные равенства? Например
$\sqrt 3 + \sqrt 3 = \sqrt {12}$
но это тривиально, поскольку
$2\cdot\sqrt 3 = \sqrt{4\cdot 3}$
Зачем это надо: пишу программу для интерактивных геометрических построений, координаты хочу записывать в виде таких выражений и проводить с ними символьные вычисления (иначе что-то может случайно совпасть из-за округления)

[Vince Diesel]

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

[Legioner93]

Ну есть штуки типа

$$\sqrt{2 -\sqrt 2} + \sqrt {2 + \sqrt 2} = \sqrt{4 + 2 \sqrt{2}},$$

с ними ещё в школе знакомят. А вы что хотите-то? Проверять тождества или уметь максимально упрощать такие выражения?

-- Чт мар 23, 2017 20:54:30 --

george66 в сообщении #1202921 писал(а):

проводить с ними символьные вычисления

Расскажите, как вы себе это представляете. Хранить вcё AST? Или что-то интереснее

[george66]

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

-- 23.03.2017, 21:49 --

Допустим, мы построили три точки в пространстве и нажимаем кнопку "провести плоскость". Перед этим надо проверить, не лежат ли они на одной прямой. А как проверить? По координатам? Координаты находятся с округлением, даже число 1/3 записывается не точно. Три точки могут оказаться на одной прямой в силу геометрических теорем, проверять это по координатам в любом случае "нехорошо". В перспективе надеюсь приделать пруфчекер.

[Legioner93]

Ваши числа называются constructible numbers, беглый гуглинг выдал вопрос на Mathoverflow, где спрашивают как раз об "unique representation of constructible numbers".
А в одном из ответов привели ссылку на учебник. Посмотрите, может вам подойдёт!

[george66]

Спасибо, некоторое решение там есть.

[arseniiv]

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

-- Пт мар 24, 2017 20:40:21 --

george66
Кстати, если не секрет, что вы планируете сделать в своей программе и чего точно не делать?

[george66]

Есть программа Geogebra, вот я рисовал расслоение Хопфа, оно же параллели Клиффорда
http://www.geogebra.org/m/hmjvu38Z
http://www.geogebra.org/m/VcV6h2ws
http://www.geogebra.org/m/YDnYbunA
http://ggbm.at/EcwwUHNV
Можно и нужно двигать ползунки, особенно нижние. Дальше я захотел сделать программу меньше (в Geogebra очень много всего), да лучше. А именно, будут геометрические построения в пространстве, геометрия будет не евклидова, а эллиптическая (она проще, а картинки красивее, смотрите параллели Клиффорда) и в перспективе, возможно, добавлю пруфчекер, если хватит терпения. На экране будет нарисован прозрачный шар (эллиптическое пространство), внутри него можно будет рисовать эллиптические прямые (изображаются дугами окружностей) и эллиптические плоскости (изображаются кусками сфер). Шар можно будет поворачивать и подвергать эллиптическим движениям, при которых окружности и сферы выпучиваются и раскорячиваются. Цель проекта - самому разобраться и потренироваться в программировании.

[arseniiv]

Это хорошо, удачи!

[arseniiv]

Вчера я написал неверное

arseniiv в сообщении #1203170 писал(а):

Вот эта же задача у меня бы тоже стояла, если бы не передумал.

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

[maxal]

Я реализовал когда-то сравнение чисел в алгебраических расширениях поля $\mathbb{Q}$.
Если мне не изменяет память, код был интегрирован в библиотеку Arageli.

[Andrey A]

george66 в сообщении #1202921 писал(а):

Есть ли практически удобный способ сравнивать их по величине? Есть ли нетривиальные равенства? Например
$\sqrt 3 + \sqrt 3 = \sqrt {12}$

$\sqrt{ab^2}+\sqrt{ac^2}=\sqrt{a(b+c)^2}$

Соответственно $\sqrt{a(b+c)^2}+\sqrt{ad^2}=\sqrt{ab^2}+\sqrt{a(c+d)^2}$, и это единственное точное равенство в целых радикалах.

Но хорошо выполняется $\sqrt{n}+\sqrt{n+1}\approx \sqrt{4n+2}$ для достаточно большого $n$. В отличии от точноых выражений, где произведение слагаемых под радикалами - целый квадрат, тут - $n(n+1)$. И для любых множителей $xy=n(n+1)$ тоже хорошо выполняется $\sqrt{x}+\sqrt{y}\approx \sqrt{m}$, где $m$ - некоторое целое составное число. Если бы удалось упорядочить арифметические суммы вида $\sqrt{x}+\sqrt{y}$ по величине, это дало бы ключ к нахождению лучшего приближения при заданном $m$, что почти равносильно факторизации: $(x-y)^2\equiv 1\mod m$. Я пробовал сортировать. Похоже на икоту из книги незабвенного Венедикта Ерофеева.

Сообщение отредактировано модератором Karan по просьбе автора.

[george66]

В рекомендованной выше книге
https://libgen.pw/download.php?id=336879
есть некоторое решение (автор D.Bouhineau, глава Solving Geometrical Constraint System)
Идея в том, что не надо придумывать обозначения для всех чисел сразу. Делая конкретное геометрическое построение циркулем и линейкой, мы добавляем к полю рациональных чисел некоторые квадратные корни и получаем расширение вроде $Q[\sqrt 2][\sqrt 3]$. Элементы каждого такого поля записываются как пары чисел из предыдущего поля, например, элементы $Q[\sqrt 2]$ имеют вид $a+b\sqrt 2$, где $a,b\in Q$. Выписывается простой рекурсивный алгоритм сравнения по величине (сравнение чисел сводится к сравнению чисел в предыдущем поле). Ключевая проблема - как не ввести поле вроде $Q[\sqrt 9]$ ? Bouhineau предложил алгоритм, проверяющий, является ли число полным квадратом в поле такого вида, мы можем проверить, что $\sqrt 9=3$ и расширять не надо. В конце статьи проблема, цитирую
The main result of this paper relies on the possibility to find explicit square root in algebraic extention of Q with square roots. Can this be extended to root of arbitrary degree?

И вот теперь новый интересный вопрос - можно ли это сделать? Я спрашивал у Bouhineau, он не знает.

[Andrey A]

Это мне надо разбираться, спасибо за ссылку. Нет ли чего подобного на русском?

[george66]

Andrey A в сообщении #1241852 писал(а):

Это мне надо разбираться, спасибо за ссылку. Нет ли чего подобного на русском?

Не встречал.