Objeto de finitud comprobada, ¿pero sin algoritmo descubierto?

Question

Explico mi título con dos ejemplos en teoría de números:

Los puntos racionales en una curva elíptica sobre cuerpos de números forman un grupo abeliano finitamente generado, por lo que su rango es un número entero, pero hasta ahora no tenemos un algoritmo que produzca este número una vez que introducimos una ecuación, en tiempo finito.

Otro ejemplo es la conjetura de Mordell sobre la finitud de puntos racionales en curvas de género superior, que fue demostrada por Faltings. No estoy seguro de que los avances recientes puedan producir el número de soluciones una vez que introducimos una ecuación de género mayor que uno, en tiempo finito.

Mi pregunta, que tal vez debería ser de la comunidad wiki, pide más ejemplos (en teoría de números y en otras áreas por supuesto) como estos dos, objetos interesantes que han sido demostrados finitos pero que aún no se ha encontrado un algoritmo. Creo que tales ejemplos son interesantes, porque esto significa que su demostración no proporciona un algoritmo. Sin embargo, existen resultados de finitud y su demostración, como lo que ocurre con los grupos de clase de cuerpos de números, sí proporcionan al menos en principio algoritmos para calcularlos.

Answer 1

La mayoría de las aproximaciones diofánticas caen en esa categoría. Por ejemplo, el teorema de Roth dice que para cualquier número algebraico no racional $\alpha\in\overline{\mathbb Q}\smallsetminus\mathbb Q$ y cualquier $\epsilon>0$, solo hay un número finito de números racionales $p/q\in\mathbb Q$ que satisfacen $$ \left|\frac{p}{q}-\alpha\right| \le \frac{1}{|q|^{2+\epsilon}}, \tag{$*$}\label{475221_star}$$ pero no hay un algoritmo probado para encontrar todos los $p/q$ para un $\alpha$ y un $\epsilon$ dados. Hay resultados, similares a los que se mencionan para los puntos racionales en las curvas, que dan un límite superior para el número de soluciones, pero no dan el número exacto de soluciones a \eqref{475221_star}. De hecho, la prueba de Vojta de la conjetura de Mordell sigue las líneas de las pruebas clásicas de aproximación diofántica, razón por la cual da límites para el número de soluciones, pero no para el tamaño de la solución más grande.

Answer 2

Heath-Brown demostró que la conjetura de Artin sobre raíces primitivas tiene como máximo dos contraejemplos. Por lo tanto, por ejemplo, sabemos que la conjetura es verdadera para al menos un elemento del conjunto $\{2,3,5\}$, pero no tenemos ningún algoritmo que nos diga cuál(es).

Otro resultado con un sabor similar es que sabemos, gracias al trabajo de Zudilin (basado en el trabajo de Rivoal), que al menos uno de los elementos del conjunto $\{\zeta(5), \zeta(7), \zeta(9), \zeta(11)\}$ es irracional, pero no podemos decir cuál. Consulta el artículo de Sprang para obtener más información.

Answer 3

El teorema del menor de gráficos implica que cualquier familia de gráficos cerrada bajo menores tiene una caracterización finita de menores prohibidos, pero la prueba no conduce a un algoritmo para encontrar los menores. Por ejemplo, hay una lista finita de menores prohibidos para la clase de gráficos toroidales (aquellos que pueden ser incrustados en la superficie de un toro), pero la lista completa no se conoce, y no hay un algoritmo conocido para calcularlos. Para más información, ver Un Conjunto Grande de Obstrucciones Toroidales y Cómo Fueron Descubiertas por Myrvold y Woodcock.

Answer 4

Otro ejemplo es el problema del número idoneal de Euler, uno de los problemas más antiguos en la teoría de números. Asevera que $1848$ es el número más grande $n$ tal que el grupo de clases del orden cuadrático $\mathbb{Z}[\sqrt{-n}]$ tiene exponente $2$. El teorema de Siegel, que demuestra que $h(-n) \gg_\varepsilon n^{1/2 - \varepsilon}$, prueba que hay un número idoneal más grande (ya que para que $n$ sea un número idoneal uno debe tener $h(-n) = 2^{\omega(n) - 1} = O(n^{1/\log \log n})$. Sin embargo, el límite inferior de Siegel debe tener en cuenta la posible existencia de ceros excepcionales (es decir, ceros de Siegel) y por lo tanto es ineficaz. Si es que ceros de Siegel no existen, entonces se puede demostrar fácilmente un límite superior para el número idoneal más grande.

Answer 5

Existe un entero positivo $N \le 246$ tal que hay infinitos números primos $p$ para los cuales $p + N$ también es primo. Sin embargo, no existe un valor específico de $N$ para el cual esto esté probado.