¿Qué velocidad tienen la regla y el compás?

Question

Esto puede ser más una pregunta de matemáticas recreativas que de investigación, pero me lo he preguntado durante un tiempo. Espero que no sea inapropiada para MO.

Considere los supuestos estándar para las construcciones de regla y compás: Tenemos una hoja de papel infinitamente grande, que asociamos con el plano complejo, que está inicialmente en blanco aparte de los puntos 0 y 1 marcados. Además tenemos una regla infinita y un compás que se puede estirar hasta una longitud arbitraria.

Definamos un mover ser una de las dos acciones normalmente asociadas a una regla y un compás:

1. Utiliza la regla para trazar la línea definida por dos puntos distintos ya marcados en el papel.
2. Estira el compás desde un punto cualquiera marcado hasta otro y dibuja el círculo resultante.

Supongamos que todos los puntos de intersección entre líneas y círculos dibujados por estas operaciones se marcan automáticamente en el papel.

Ahora defina $D(n)$ para ser la distancia máxima entre dos puntos marcados cualesquiera que pueden ser construidos de esta manera con $n$ se mueve.

Preguntas:

1. ¿Alguien conoce los resultados de la función $D(n)$ ¿o algo equivalente?
2. No es difícil demostrar $D(n) > 2^{2^{cn}}$ para alguna constante positiva $c$ para un tamaño suficientemente grande $n$ . ¿Se puede hacer algo mejor? Si es así, ¿se puede demostrar un límite superior en $D(n)$ ?

Answer 1

Edición del 31 de julio: Ahora el límite superior es ajustado (hasta sustituir n por O(n)). La mejora con respecto a la versión anterior está en el argumento que sigue al lema 1. Ahora consideramos la altura logarítmica absoluta de Weil de un número algebraico en lugar de la longitud.

Aquí hay una prueba de que D(n) < 2 2 cn para alguna constante positiva c>0 para un n suficientemente grande. En otras palabras, la respuesta a la parte de la pregunta 2 "¿se puede hacer mejor?" es negativa.

Como señaló Terry Tao, este problema puede reformularse en forma algebraica. Tenemos z ₀ \=0 y z ₁ \=1, y cualquier z _n (n≥2) puede obtenerse a partir de números anteriores mediante suma, resta, multiplicación, división o raíz cuadrada. La afirmación se deduce si |z _n | < 2 2 O(n) .

Lema 1 : El grado de z _n sobre ℚ es como máximo 2 n .

Prueba: Sea F _n \=ℚ(z ₀ , , z _n ) sea el campo mínimo que contiene a ℚ∪{z ₀ , , z _n }. Entonces F ₀ \=ℚ, y F _n es igual a F _n-1 o una extensión de F _n-1 obtenida por la adición de una raíz cuadrada. Dado que al unir una raíz cuadrada de un elemento no cuadrado se obtiene una extensión de grado 2, el grado de extensión [F _n :F _n-1 ] es 1 o 2. Por la fórmula de grado, se cumple que [F _n :ℚ] = [F _n :F ₀ ] = [F _n :F _n-1 ][F _n-1 :F _n-2 ] [F ₁ :F ₀ ] ≤ 2 n . Por tanto, el grado de cada elemento de F _n sobre ℚ es también a lo sumo 2 n . (fin de la prueba del lema 1)

Existe una función llamada Altura logarítmica absoluta de Weil h(α) definida sobre números algebraicos α que toma valores reales no negativos. Véase la sección 3.2 de [Wal00] para su definición y la demostración de las siguientes propiedades:

1. Si α es un número algebraico de grado d, entonces |α| ≤ exp(dh(α)).
2. Si p y q son números enteros relativamente primos, entonces h(p/q) = ln max{|p|,|q|}.
3. Si α y β son números algebraicos, entonces h(α+β) ≤ h(α) + h(β) + ln 2.
4. Si α y β son números algebraicos, entonces h(αβ) ≤ h(α) + h(β).
5. Si α es un número algebraico y n es un número entero, entonces h(α) n ) = |n|h(α). En particular, h(√α)=h(α)/2.

Utilizando las propiedades 2-5 y la inducción matemática, podemos demostrar que h(z _n ) ≤ 2 n ln 2. Combinando la propiedad 1 y el lema 1, obtenemos que |z _n | ≤ 2 2 2n .

Referencias

[Wal00] Michel Waldschmidt: Aproximación diofantina en grupos algebraicos lineales: Propiedades de trascendencia de la función exponencial en varias variables , Springer, 2000.

Answer 2

Hasta factores constantes (es decir, sustituyendo n por cn), la pregunta es equivalente (hasta factores constantes) a preguntar cuál es el mayor número que puede ser generado por un circuito aritmético de complejidad n utilizando 0, 1, las operaciones aritméticas +, -, *, /, y la operación de raíz cuadrada, ya que cada operación de regla y compás puede ser modelada por un circuito de complejidad O(1) (y viceversa), básicamente por la fórmula cuadrática.

Entonces me parece por inducción que los números que uno genera después de n pasos deben ser números algebraicos de grado que crecen como máximo exponencialmente en n, y de altura que crece como máximo doble exponencialmente en n, lo que coincide con el límite inferior mencionado en el post.

EDIT: En realidad, los límites ingenuos son peores de lo que pensé en un principio. Tomar raíces cuadradas y recíprocas (o la negación) no es un problema, pero sumar o multiplicar dos números algebraicos puede elevar el grado al cuadrado y las alturas a una potencia comparable al grado (usando resultantes, etc.) Eso sólo nos da un límite exponencial doble en el grado y un límite exponencial triple en la altura, por lo que hay una brecha de un exponencial entre los límites superiores e inferiores fáciles...

Answer 3

Según este documento (MR0949111 Davenport, James H. Heintz, Joos La eliminación de cuantificadores reales es doblemente exponencial. J. Symbolic Comput. 5 (1988), no. 1-2, 29--35) el problema de decidir la verdad de una pregunta en la teoría de campos reales cerrados (una ligera extensión de la geometría euclidiana) es doblemente exponencial: el tiempo necesario para decidir la verdad de una frase de longitud n puede ser tanto como 2^2^cn, y creo que hay un algoritmo para hacerlo en este tiempo. Esto es más o menos lo mismo que el límite para D(n) dado en la pregunta. Tengo una especie de corazonada de que los dos límites pueden estar relacionados, pero no puedo ver de antemano una conexión directa entre ellos.

Answer 4

Esta es una construcción que muestra que $D(n) \ge 2^{2^{n-O(1)}}$ . Esto demuestra que cualquier constante $c<1$ en la pregunta original se puede lograr para un tamaño suficientemente grande $n$ . La construcción supone un número entero positivo fijo (pero arbitrario) $m$ .

1. Utilizando un número constante de movimientos, dibuja los ejes real e imaginario, y marca los puntos $A = -i$ y $B = -1$ . Sea $z_0 = 1$ .

2. Para $k = 1,2,3,\ldots,m$ , hacer

a) Si $k$ es impar, entonces dibuja un círculo centrado en $A$ y pasando por $z_{k-1}$ . Sea $z_k$ sea la intersección de este círculo con el eje imaginario positivo.

b) Si $k$ es par, entonces dibuje un círculo centrado en $B$ y pasando por $z_{k-1}$ . Sea $z_k$ sea la intersección de este círculo con el eje real positivo.

1. Utilizando un número constante de movimientos, construye el recíproco de $|z_m|$ .

Algunas cosas para observar:

1. El paso 2 utiliza exactamente $m$ movimientos, por lo que el número total de movimientos es $n = m + O(1)$ .
2. $z_k > 0$ para todos incluso $k$ y $-iz_k > 0$ para todos los impar $k$ .
3. Para todos $k\in\{1,\ldots,m\}$ tenemos $|z_k| = \sqrt{1+|z_{k-1}|^2}-1 \le |z_{k-1}|^2/2$ .
4. El hecho anterior combinado con la inducción sobre $k$ da $|z_k| \le 2^{-(2^k-1)}$ .
5. Por tanto, el punto construido en el paso 3 tiene norma al menos $2^{2^m-1} \ge 2^{2^{n-O(1)}}$ .

Answer 5

No estoy seguro pero quizás el clásico Geometrografía por Lemoine discute esta complejidad espacial así como la complejidad temporal. Véase también http://www.cs.mcgill.ca/~sqrt/cons/construcciones.html y http://geometrographie.org/ .

Creo que una vez vi un artículo sobre la complejidad del espacio, pero ahora mismo no lo encuentro.