Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
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). – Peter Shor Jan 7 '13 at 15:11
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. – domotorp Jan 7 '13 at 21:33
@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. – Jagadish Jan 8 '13 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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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