По мотивам задачника

Сложность алгоритмов при построениях циркулем и линейкой

М. В. Алехнович^a, А. Я. Канель-Белов^bc, А. О. Сулейкин<sup>d

a</sup> Университет Сан-Диего
^b Университет Бар-Илана
^c МФТИ
^d Мехмат МГУ

Аннотация: Статья посвящена решению задачи 32.9 (выпуск 32, с.181). Пусть на плоскости отмечены две точки $A$ и $B$ и задано натуральное число $n$. Наша цель—построить на прямой, проходящей через эти точки, третью точку $C$ так, чтобы длина отрезка $AC$ была в $n$ раз больше длины отрезка AB, с помощью линейки и (или) циркуля (при этом прямая $AB$ считается проведённой). На каждом шаге мы можем либо проводить линейкой прямую через две отмеченные точки, либо строить окружность с центром в отмеченной точке радиусом, равным расстоянию между отмеченными точками. При пересечении проведённых прямых и окружностей возникают новые отмеченные точки. Обозначим через $\text{Ц}(n)$ минимальное число шагов, необходимое при решении задачи одним циркулем, а через $\text{ЦЛ}(n)$ — число шагов, необходимых при решении её циркулем и линейкой. Задача заключается в оценке асимптотического поведения функций $\text{Ц}(n)$ и $\text{ЦЛ}(n)$. Основной результат работы заключается в следующем. Существуют такие константы $c_1, c_2 >0$, что:
$$ \text{а) } c_1 \ln n\leqslant \text{Ц}(n)\leqslant c_2 \ln n;\quad \text{б) } c_1 \ln \ln n \leqslant \text{ЦЛ}(n)\leqslant \frac{c_2 \ln n} {\ln \ln n}. $$
Наиболее интересный результат получается при нижней оценке функции ЦЛ(n), где совершенно неожиданно возникают чисто алгебраические понятия, такие как высота числа и др.
Над статьёй совместно работали М.В.Алехнович и А.Я.Канель-Белов. Работа была завершена А.Я.Канель-Беловым и А.О.Сулейкиным