FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2001, VOLUME 7, NUMBER 2, PAGES 597-614

M. V. Alekhnovich

A. Ya. Belov

Abstract

View as HTML
View as gif image
View as LaTeX source

```
The article deals with the following problem.
Assume that there are two points
```$A$ and $B$ on the plane,
and a natural number $n$ is given. Our aim is to find
the third point $C$ on the line containing $A$ and $B$
so that the length $AC$ is $n$ times larger than the length $AB$
using only a compass and a straightedge. During every step
we can either construct a straight line containing two
constructed points, or a circle with a constructed point
as a center and with a radius equal to the distance between
two constructed points. Intersections of constructed lines and
circles form new constructed points. Denote the minimal number
of steps necessary to solve this problem
using only the compass as $\mathrm{C}(n)$ , and
the minimal number of steps necessary to solve this problem
using both the compass and the straightedge as $\mathrm{CS}(n)$ .
We want to estimate the asymptotic behavior of the functions
$\mathrm{C}(n)$ and $\mathrm{CS}(n)$ . Our main result is the following:
there exist constants $c_1, c_2>0$ such that
a) $c_1\ln n\le \mathrm{C}(n)\le c_2 \ln n$ ,
b) $c_1\ln\ln n\le \mathrm{CS}(n)\le \frac{c_2\ln n}{\ln\ln n}$ .

The most interesting result is obtained in connection
with the lower bound of $\mathrm{CS}(n)$ , where purely algebraic
notions, such as the height of a number etc., arise
quite unexpectedly.

All articles are published in Russian.

Main page | Contents of the journal | News | Search |

Location: http://mech.math.msu.su/~fpm/eng/k01/k012/k01216t.htm.

Last modified: October 31, 2001.