¿Cuál es el siguiente número en la secuencia de constructibilidad? ¿Y cuál es el crecimiento asintótico?

Question

Generemos sistemáticamente todos los puntos construibles en el plano. Comenzamos con sólo dos puntos, que especifican la distancia unitaria.

Con la regla, podemos construir la línea que los une. Y con el compás, podemos construir las dos circunferencias centradas en cada una de ellas, teniendo como radio ese segmento unitario. Estos círculos se intersecan entre sí y con la recta, creando cuatro puntos de intersección adicionales. Así, tenemos ahora seis puntos en total.

A partir de estos seis puntos, pasamos a la etapa siguiente, en la que construimos todas las rectas y circunferencias posibles utilizando esos seis puntos, y hallamos los puntos de intersección resultantes.

Creo que ahora tenemos 203 puntos. Procedamos de este modo para construir sistemáticamente todos los puntos construibles en el plano, en una jerarquía de etapas finitas. En cada etapa, formamos todas las líneas y círculos posibles que pueden formarse a partir de nuestros puntos actuales utilizando regla y compás, y luego encontramos todos los puntos de intersección a partir de las figuras resultantes.

Esto produce lo que yo llamo el secuencia de constructibilidad :

$$2\qquad\qquad 6\qquad\qquad 203\qquad\qquad ?$$

Cada entrada es el número de puntos construidos en esa fase. Tengo varias preguntas sobre la secuencia de constructibilidad:

Pregunta 1. ¿Cuál es el siguiente número de constructibilidad?

En la enciclopedia en línea no hay ninguna entrada de secuencias de números enteros que empiecen por 2, 6, 203, por lo que me gustaría crear una entrada para la secuencia de constructibilidad. Pero piden al menos cuatro números, por lo que parece que necesitamos saber el siguiente número. No estoy seguro de cómo proceder exactamente con esto, ya que si uno procede computacionalmente, entonces uno inevitablemente tendrá que decidir si dos puntos muy cercanos cuentan como idénticos no lo son, y no veo ninguna manera de principio para asegurar que esto se hace correctamente. Así que parece que uno tendrá que proceder con algún tipo de cálculo geométrico idealizado, que obtiene la respuesta correcta acerca de la coincidencia de puntos de intersección. [ Actualización: La secuencia existe ahora como A333944 .]

Pregunta 2. ¿Qué tipo de límites superiores asintóticos puede demostrar sobre el crecimiento de la secuencia de constructibilidad?

En cada etapa, cada par de puntos determina una línea y dos círculos. Y cada punto de intersección se realiza como la intersección de dos rectas, dos círculos o una recta y un círculo, que tienen como máximo dos puntos de intersección en cada caso. Por tanto, un límite superior aproximado es que a partir de $k$ puntos, no producimos más que $3k^2$ muchas líneas y círculos, y así como mucho $(3k^2)^2$ muchos pares de líneas y círculos, y así como máximo $2(3k^2)^2$ muchos puntos de intersección. Esto conduce a un límite superior de crecimiento algo así como $18^n2^{4^n}$ después de $n$ etapas. ¿Alguien puede dar un límite mejor?

Pregunta 3. ¿Y los límites inferiores?

Sospecho que la secuencia crece muy rápidamente, probablemente de forma doblemente exponencial. Pero para probar esto, parece que tendríamos que identificar un reino de patrones de construcción donde hay poca interferencia de coincidencia de intersección, de modo que uno puede estar seguro de un cierto crecimiento conocido en nuevos puntos.

Answer 1

He escrito algunas Haskell código para calcular el siguiente número de la secuencia de constructibilidad. Ha confirmado todo lo que ya habíamos establecido y me ha dado los siguientes resultados adicionales:

Existen $149714263$ intersecciones línea-línea en el 4º paso (calculado en ~14 horas). La aproximación de Pace Nielsen sólo se equivocó en 8 puntos. Esto incluye algunos puntos que están entre una distancia de $10^{-12}$ y $10^{-13}$ entre sí.

He encontrado el cuarto número de la secuencia de constructibilidad: $$1723816861$$ Lo he calculado dividiendo el primer cuadrante en secciones a lo largo del eje x, calculando los valores de estas secciones y combinándolos. El programa no era paralelo, pero el trabajo se dividió entre 6 procesos en 3 máquinas. Tardé aproximadamente 6 días en completarlo y cada proceso nunca utilizó más de 5 GB de RAM.

Mis datos se pueden encontrar aquí . He elaborado estos dos gráficos a partir de mis datos, que dan una idea de cómo se distribuyen los puntos: Si nos centramos en la zona de $0$ a $1$ obtenemos:

---

Detalles de la aplicación:

Represento los reales construibles como pares de una aproximación de 14 dígitos decimales (utilizando ireal ) y una representación simbólica (mediante constructible ). Esto se hace para acelerar las comparaciones: las aproximaciones nos dan funciones de comparación rápidas pero parciales, mientras que la representación simbólica nos da funciones de comparación más lentas pero totales.

Las líneas se representan mediante un par $\langle m, c \rangle$ tal que $y = mx + c$ . Para tratar las líneas verticales, creamos un tipo de datos mejorado con un valor infinito. Los círculos son triples $\langle a, b, r \rangle$ tal que $(x-a)^2 + (y-b)^2 = r^2$ .

Utilizo un algoritmo de línea de barrido para calcular el número de intersecciones en un rectángulo dado. Extiende el Algoritmo Bentley-Ottoman para permitir la comprobación de intersecciones tanto entre círculos como entre líneas. La idea que subyace al algoritmo es que tenemos una línea vertical que se desplaza de la cara izquierda a la derecha del rectángulo. Pensamos en esta línea como un conjunto estrictamente ordenado de objetos (líneas y círculos). Esto requiere cierto cuidado. Los círculos deben dividirse en sus semicírculos superior e inferior, y no sólo queremos ordenar los objetos en función de sus coordenadas y, si son iguales, también de su pendiente, y tenemos que tratar los círculos que son tangentes entre sí en un punto. La composición u orden de este conjunto puede cambiar de 3 formas según nos movemos de izquierda a derecha:

1. Incorporación: Llegamos al punto más a la izquierda de un objeto y lo añadimos a nuestro conjunto ordenado.
2. Supresión: Llegamos al punto más a la derecha de nuestro objeto, por lo que lo eliminamos de nuestro conjunto ordenado.
3. Intersección: Varios objetos se cruzan. Es la única manera de cambiar el orden de los objetos. Los reordenamos y observamos la intersección.

Llevamos la cuenta de estos eventos en una cola de prioridad, y nos ocupamos de ellos en el orden en que se producen a medida que avanzamos de izquierda a derecha.

La gran ventaja de este alograma sobre el enfoque ingenuo es que no requiere que llevemos la cuenta de los puntos de colisión. También tiene la ventaja de que si calculamos la cantidad de colisiones en dos rectángulos es muy fácil combinarlos, ya que sólo tenemos que sumar la cantidad de colisiones en cada uno, asegurándonos de que no estamos contando dos veces los bordes. Esto hace que sea muy fácil distribuir el cálculo. También tiene unas demandas de RAM muy razonables. Su uso de RAM debería ser $O(n)$ donde $n$ es la cantidad de líneas y círculos y la constante es bastante pequeña.

Answer 2

Mathematica tiene un comando para resolver sistemas de ecuaciones sobre los números reales; o uno puede simplemente resolverlos ecuacionalmente. También tiene un comando para encontrar el polinomio mínimo de un número algebraico. Así, los puntos de intersección entre rectas y círculos pueden hallarse usando aritmética exacta (como raíces numeradas de polinomios mínimos sobre $\mathbb{Q}$ ), al igual que las pendientes de las rectas y los radios de los círculos. Utilizando estos métodos, hay exactamente 17.562 líneas y 32.719 círculos distintos en la siguiente etapa.

Encontrar el polinomio mínimo de un número algebraico de esta forma es algo lento (puede haber formas de acelerarlo), pero estas rectas y círculos también se pueden encontrar en unos minutos si en su lugar utilizamos aproximaciones en coma flotante (10 dígitos).

Ahora he optimizado un poco el código, y utilizando esas aproximaciones en coma flotante, en poco menos de 21 horas calculo que hay al menos $$149,714,255$$ distintas intersecciones entre esas 17.562 líneas. Esto podría ser una subestimación, porque la aritmética de coma flotante podría hacernos pensar que dos puntos de intersección distintos son el mismo. Sin embargo, los cálculos no deberían llevar mucho más tiempo si se utilizaran 20 dígitos en coma flotante (pero necesitarían mucha más RAM). Espero que los números no cambien mucho, si es que cambian. Pero sí he visto cambios al pasar de aproximaciones de 5 a 10 dígitos, así que sería útil probar el cálculo con 20 dígitos.

Almacenar esos 10 dígitos, para algo más de cien millones de puntos de intersección, se estaba llevando la mayor parte de mi RAM. Parece que si intento hacer el mismo cálculo con las intersecciones circulares, superará mis límites de RAM. Sin embargo, es ciertamente factible, y estoy encantado de dar mi código a cualquiera que tenga acceso a un ordenador con un montón de RAM (sólo envíeme un correo electrónico; mi ordenador tiene 24 GB, por lo que querría un poco más que eso). El código todavía puede tener algunas áreas donde se puede acelerar - pero tomar menos de 1 día para encontrar todos los puntos de intersección entre las líneas ya es bastante agradable.

Otra opción sería almacenar estos puntos en el disco duro, pero hay ordenadores con suficiente RAM como para que ese cambio sea innecesario.

---

Editado para añadir: Encontré un ordenador que es ligeramente más lento que el mío pero que tenía mucha RAM. Tardé unas 6 semanas, y unos 360 GB de RAM, pero el cálculo terminó. Sigue siendo sólo una aproximación (no es aritmética exacta, sólo 10 dígitos de precisión más allá del decimal). El número de cruces que obtengo es $$ 1,723,814,005 $$ Si tienes una necesidad real de hacer aritmética exacta, probablemente podría hacerlo, pero tardaría un poco más. De lo contrario, lo consideraré suficientemente bueno.