<p>In a related not-quite answer to @jagadish's, after being defined, <a href="http://en.wikipedia.org/wiki/Costas_array" rel="nofollow">Costas arrays</a> 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$.</p>

CC BY-SA 3.0
2013-01-08T05:59:21.620Z
2013-01-08T05:59:21.620Z
Lev Reyzin
<p>Note: This is more like an extended comment than an answer.</p>

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

<blockquote>
  <p><strong>Background</strong>. 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$.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2013-01-07T15:11:17.460Z
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 
CC BY-SA 3.0
2013-01-07T21:33:22.367Z
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
CC BY-SA 3.0
2013-01-08T06:01:11.600Z
@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
CC BY-SA 3.0
2013-01-07T11:57:19.670Z
2013-01-08T05:53:13.497Z
2013-01-08T05:53:13.497Z
Jagadish
<p>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?</p>

<p>In number theory such problems do exist, eg. as <a href="https://mathoverflow.net/questions/117891/what-are-conjectures-that-are-true-for-primes-but-then-turned-out-to-be-false-for/117985#117985">Aaron Meyerowitz points out</a> the one about the coefficients of the cyclotomic polynomials. From TCS I only know examples like the <a href="http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture" rel="nofollow noreferrer">Evasiveness Conjecture</a> that are still unsettled.</p>

<big-list><primes>
What are TCS conjectures that were proved for primes and small values but then turned out to be false?
domotorp
# What are TCS conjectures that were proved for primes and small values but then turned out to be false?

(Asked by: username_0 on 2013-01-06)

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](https://mathoverflow.net/questions/117891/what-are-conjectures-that-are-true-for-primes-but-then-turned-out-to-be-false-for/117985#117985) the one about the coefficients of the cyclotomic polynomials. From TCS I only know examples like the [Evasiveness Conjecture](http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture) that are still unsettled.

**Tags:** big-list, primes

---

## 2 answers

### Answer by username_1 on 2013-01-08. Score: 3

In a related not-quite answer to @jagadish's, after being defined, [Costas arrays](http://en.wikipedia.org/wiki/Costas_array) 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$.


---

### Answer by username_2 on 2013-01-07. Score: 3

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.

> **Comments:**
> **username_3**: 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).  
> **username_0**: 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.  
> **username_2**: @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.  

---

