Are there any conjectures in theoretical computer science that involve some parameter n and were proved for small values of n AND for primes but later turned out to be false?

In number theory such problems do exist, eg. as Aaron Meyerowitz points out the one about the coefficients of the cyclotomic polynomials. From TCS I only know examples like the Evasiveness Conjecture that are still unsettled.


2 Answers 2


Note: This is more like an extended comment than an answer.

Here is a problem from combinatorics whose status is similiar in flavor to that of Evasiveness Conjecture:

Background. A Latin square of order $n$ is an $n × n$ matrix in which each element from {1, . . . , n} occurs exactly once in each row and column. Two Latin squares of order $n$ are said to be orthogonal if you get $n^2$ distinct ordered pairs when you superimpose them. A set of Latin squares are said to be mutually orthogonal if every pair of them are orthogonal. Let $N(n)$ denote the maximum number of mutually orthogonal Latin squares of order $n$.

It is known that $N(n)\leq n-1$ for all $n$. If $n$ is a prime power then we know that $N(n)=n-1$, but for general values of $n$ the status of lower bounds is wide open.

  • 4
    $\begingroup$ Not quite completely wide open. It's been known that $N(6)=1$ since 1900 (G. Tarry), that $N(n) \geq 2$ for $n>6$ since 1960 (Bose, Shrikande, Parker), and that $N(10)<9$ since 1989 (Lam, Thiel, Swiercz). $\endgroup$ Jan 7, 2013 at 15:11
  • 1
    $\begingroup$ Thx Jagadish, the problem is that this is something that is conjectures to hold only for prime(power)s. I am looking for something that WAS conjectured to be true for all numbers but turned out to be false. $\endgroup$
    – domotorp
    Jan 7, 2013 at 21:33
  • $\begingroup$ @domotorp Yes, my response doesn't answer the question exactly. I'm curious to know if there are any such examples myself, so +1 for your question. $\endgroup$
    – Jagadish
    Jan 8, 2013 at 6:01

In a related not-quite answer to @jagadish's, after being defined, Costas arrays were quickly found for very small numbers, and were later found for sizes $p-1$, where $p$ is prime. However, it is open whether they exist for all $n$ and computer searches are making people believe that they do not exist for $n=32$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.