Quelles sont les conjectures TCS qui ont été prouvées pour les nombres premiers et les petites valeurs mais qui se sont ensuite révélées fausses?

Existe-t-il des conjectures en informatique théorique qui impliquent certains paramètres n et qui ont été prouvées pour de petites valeurs de n ET pour des nombres premiers mais qui se sont révélées fausses par la suite?

Dans la théorie des nombres, de tels problèmes existent, par exemple. comme le souligne Aaron Meyerowitz celui sur les coefficients des polynômes cyclotomiques. De TCS, je ne connais que des exemples comme la conjecture d'évasivité qui sont encore instables.

Remarque: cela ressemble plus à un commentaire étendu qu'à une réponse.

Voici un problème de combinatoire dont le statut est similaire en saveur à celui de la conjecture d'évasivité:

Contexte . Un carré latin d'ordre est une matrice dans laquelle chaque élément de {1,. . . , n} apparaît exactement une fois dans chaque ligne et colonne. On dit que deux carrés latins d'ordre sont orthogonaux si vous obtenez paires ordonnées distinctes lorsque vous les superposez. On dit qu'un ensemble de carrés latins sont mutuellement orthogonaux si chaque paire d'entre eux est orthogonale. Soit le nombre maximal de carrés latins mutuellement orthogonaux d'ordre .$n$$n × n$$n$$n^2$$N(n)$$n$

On sait que pour tout . Si est une puissance première, alors nous savons que , mais pour les valeurs générales de l'état des bornes inférieures est grand ouvert.$N(n)\leq n-1$$n$$n$$N(n)=n-1$$n$

Dans une réponse connexe pas tout à fait à @ jagadish, après avoir été définie, les tableaux Costas ont été rapidement trouvés pour de très petits nombres, et ont ensuite été trouvés pour les tailles , où est premier. Cependant, il est ouvert qu'elles existent pour tous les et les recherches informatiques font croire aux gens qu'elles n'existent pas pour .$p-1$$p$$n$$n=32$