¿Cuáles son las conjeturas de TCS que se probaron para primos y valores pequeños pero que luego resultaron ser falsas?

17

¿Hay conjeturas en la informática teórica que impliquen algún parámetro n y se hayan probado para valores pequeños de n AND para números primos pero luego resultaron ser falsos?

En teoría de números existen tales problemas, por ejemplo. como Aaron Meyerowitz señala el de los coeficientes de los polinomios ciclotómicos. De TCS solo conozco ejemplos como la Conjetura de Evasividad que aún están sin resolver.

domotorp
fuente

Respuestas:

3

Nota: Esto se parece más a un comentario extendido que a una respuesta.

Aquí hay un problema de la combinatoria cuyo estado es similar en sabor al de la conjetura de evasión:

Antecedentes . Un cuadrado latino de orden es una matriz n × n en la que cada elemento de {1,. . . , n} aparece exactamente una vez en cada fila y columna. Se dice que dos cuadrados latinos de orden n son ortogonales si obtiene n 2 pares ordenados distintos cuando los superpone. Se dice que un conjunto de cuadrados latinos son mutuamente ortogonales si cada par de ellos es ortogonal. Sea N ( n ) el número máximo de cuadrados latinos mutuamente ortogonales de orden n .nortenorte×nortenortenorte2norte(norte)norte

Se sabe que para todo n . Si n es una potencia principal, entonces sabemos que N ( n ) = n - 1 , pero para los valores generales de n, el estado de los límites inferiores está abierto.norte(norte)norte-1nortenortenorte(norte)=norte-1norte

Jagadish
fuente
44
No del todo completamente abierto. Se sabe que desde 1900 (G. Tarry), que N ( n ) 2 para n > 6 desde 1960 (Bose, Shrikande, Parker), y que N ( 10 ) < 9 desde 1989 ( Lam, Thiel, Swiercz). norte(6 6)=1norte(norte)2norte>6 6norte(10)<9
Peter Shor
1
Thx Jagadish, el problema es que esto es algo que son conjeturas que se deben cumplir solo para primos (potencias). Estoy buscando algo que FUE conjeturado como verdadero para todos los números, pero resultó ser falso.
domotorp
@domotorp Sí, mi respuesta no responde la pregunta exactamente. Tengo curiosidad por saber si hay algún ejemplo de este tipo, así que +1 para su pregunta.
Jagadish
3

En una respuesta no bastante relacionada a @ jagadish, después de ser definidos, los arreglos de Costas se encontraron rápidamente para números muy pequeños, y luego se encontraron para tamaños , donde p es primo. Sin embargo, está abierto si existen para todas n y las búsquedas por computadora están haciendo creer a las personas que no existen para n = 32 .pag-1pagnortenorte=32

Lev Reyzin
fuente