# What are conjectures that are true for primes but then turned out to be false for some composite number?

Note: This is an update formulation since many people misunderstood the question before.

Of course it is easy to make a statement like "Every n is a prime or at most 1000", which is true for every prime $n$ and every small $n$ but fails for $n=1002$. What are "real" conjectures that were known to hold for primes and small values, then turned out to be false?

An excellent example about cyclotomic polynomials was given by Aaron in the comments. Here the conjecture was that the coefficients are $0, \pm 1$ for every $n$. This holds for primes and small $n$'s, but fails for $105$.

Also the existence of Carmichael numbers comes close, but here the problem itself involves primes, I would like something less "primey". I know conjuctures that are or were known only for primes. Recently solved is Colorful Tverberg, still unknown is Evasiveness or this little MO problem.

-
Can you explain what you mean by "true for primes but failed"? – Stopple Jan 2 '13 at 19:07
I think the idea is to ask for conjectures involving an integral parameter $n$. So that the conjecture was known for $n$ a prime (and small $n$) yet then failed to be true for all $n$. – user9072 Jan 2 '13 at 19:10
How about conjecture: the coefficients in the cyclotomic polynomial $\Phi_n$ are are $-1,0$ and $+1$ This is true for primes, prime powers and even $n=2^ip^jq^k$ (numbers with up to two distinct odd prime divisors) But it fails at $n=105.$ I recall hearing that this was a believed (by some people) conjecture (at some time.) – Aaron Meyerowitz Jan 3 '13 at 5:52
@domotorp: I tried to formulate my almost example, but now as I try to write it down it seems still less fitting so only a comment. What I had in mind is Davenport constant of finite commutative groups mathworld.wolfram.com/DavenportConstant.html For Z/n_1+...+Z/n_r the direct lower bound is 1 + sum (n_i -1) and it seems early on (60s) the sense rather was this is always optimal and it was known if all n_i (or equivalently the order of the group) is a prime power and some other cases (up to order 50 or so). Yet then (fairly soon) a counter example was found. cont. – user9072 Jan 3 '13 at 15:23
In the more restricted case all n_i equal so (Z/n)^r the question whether it is always 1+r(n-1) is still open. Known for n a prime power (general r); and for r<=2 for all n, and very few other cases for certain r. But here always equality is still the standing conjecture; see for example conj A.5 in this paper by Alon-Friedland-Kalai tau.ac.il/~nogaa/PDFS/Publications/… – user9072 Jan 3 '13 at 15:39

I'll elevate my comment to an answer and give two more related ones. One seems less trivial for primes but has first exception at $30$, the other seems more obvious for primes but has first exception at $900$.

The cyclotomic polynomials $\Phi_d$ can be specified inductively by saying that, for all $n$, $\prod_{d|n}\Phi_d(x)=x^n-1.$ Equivalently, $\Phi_d(x)$ is the minimal polynomial of $e^{{2\pi i}/d}.$ It turns out that $\Phi_{15}=x^8-x^7+x^5-x^4+x^3-x+1.$ One might conjecture that the coefficients of $\Phi_m$ are always are always $0,1$ and $-1.$ This is true for primes, prime powers and even for numbers of the form $2^ip^jq^k$ (up to two distinct odd prime divisors) but it fails for $m=105$

The second example is of great interest to me, but takes a little explanation For a finite integer set $A$, we say that $A$ tiles the integers by translation if there is an integer set $C$ with $\{a+c \mid a \in A,c \in C \}=\mathbb{Z}$ and each $s \in \mathbb{Z}$ can be uniquely written in this form. Then we write $A \oplus C =\mathbb{Z}$. This property is not affected by translation so we will always assume that $0 \in A$ and $0 \in C.$

Consider this property enjoyed by certain integers $m$:

Whenever $A$ is an $m$ element set with $A \oplus C=\mathbb{Z}$ there is a prime divisor $p$ of $m$ such that $A \subset p\mathbb{Z}$ or $C \subset p\mathbb{Z}.$

It is true when $m$ is prime (but I don't consider it trivial) and also when $m$ is a prime power or a product $m=p^iq^j$ of two prime powers. It is not true for $m=30$ and other values with at least three distinct prime factors. The sets $A$ which provide counterexamples are rather spread out. If I recall correctly , a counterexample for $m=30$ will have $\max{A} \gt 720$ (if we set $\min{A}=0$. )

Here is a variant form: Write $A \oplus B=\mathbb{Z}_n$ when $A \oplus B$ is a complete set of residues $\mod n=|A||B|.$ Here we will assume $0=\min{A}=\min{B}$ and consider this property which is enjoyed by certain integers $n$.

Whenever $A \oplus B=\mathbb{Z}_n$ , there is a prime divisor $p$ of $n$ such that $A \subset p\mathbb{Z}$ or $B \subset p\mathbb{Z}.$

It always holds when $n$ is a prime, or prime power or even a product of two prime powers $n=p^jq^k.$ It fails when both $|A|$ and $|B|$ can have three distinct prime divisors so the first time is for $n=2^23^25^2=900$ as well as for $n=2\cdot3\cdot5\cdot 7 \cdot 11 \cdot 13=30030.$ So, while this seems trivial as a property of $n=|A||B|$, it is actually a property of $\min(|A|,|B|)$ (although it would take longer to explain why) and is not trivial when that minimum is a prime.

Now that I got to the property resisting digressions, let me explain why it is interesting (optional), mention the existence of an open problem and demystify the property a bit. For details see Tiling the integers with translates of one finite set which also proves the claims above and shows a link to cyclotomic polynomials.

It is interesting to characterize finite sets $A$ which tile the integers by translation: $A \oplus C=\mathbb{Z}.$ There are attractive sufficient conditions (T1 and T2 in the linked paper). These conditions are necessary when the size has at most two prime divisors, $|A|=p^{\alpha}q^{\beta}.$ The method of proof depends strongly on the property above. It is also not hard to show that if $A \subset p\mathbb{Z}$ (all elements of $A$ are multiples of $p$) Then there is $C$ with $A \oplus C=\mathbb{Z}$ if and only if there is a set $C'$ with $A' \oplus C'=\mathbb{Z}$ where $A'=\lbrace\frac{a}{p} \mid a \in A \rbrace.$  This reduction to a smaller case (along with the rest and a bit more) is what allows the proof that the sufficient conditions are also necessary for a set of size $|A|=p^{\alpha}q^{\beta}$ to tile the integers by translation. It is possible that the conditions are necessary for $A$ of any finite size, however the method of proof would have to be quite different. The first potential exception would be for $A$ with $30$ elements which tiles $\mathbb{Z}_{900}.$

Here is a way to restate the property above so that it does hold for all $m$ (but fails in general to allow the proof of necessity): If $A \oplus B=\mathbb{Z}_n$ then for one of the two sets , say $A$, none of the differences $a_i-a_j$ is coprime to $n$. Since $0 \in A$ this means that also every $a \in A$ shares a divisor with $n.$ So if $n=72$ then every member of $A$ and every difference is divisible by $2$ or $3$ or both. In fact they are all even or all multiples of 3 lest there be $a_x \in A$ not divisible by $2$ and $a_y \in A$ not divisible by $3$ as then $a_x-a_y$ would share no prime divisors with $72.$ So the reduction is possible and a theorem can be proved. When $A$ has 30 elements it can be the case that among them are $6,10,15$ and various of their multiples so the elements and differences all share a divisor with $30$ but no one divisor covers all cases and the proof is not available.

-
Thank you, very nice examples. I wonder if there are any examples that are not from number theory or that are not trivially true for primes. – domotorp Jan 4 '13 at 7:08
It is really a property of $\min(|A|,|B|$ rather than $n=|A||B|.$ and hence not so trivial. I realize I can express it more directly (and less trivially) another way so I have edited. – Aaron Meyerowitz Jan 4 '13 at 9:38
Maybe I misunderstood something, but isn't the cardinality ab? From this it would be trivial that a or b is 1. – domotorp Jan 4 '13 at 19:38
You are correct, as stated it is trivial for prime $n$ for the reason you said. If I have other reasons to edit I may change it. What I should have said was: Suppose $A$ is finite and either $A \oplus B=\mathbb{Z}_n$ or $A \oplus B=\mathbb{Z}.$ Then either of these is sufficient to imply " There is a prime $v$ with $A \subset v\mathbb{Z}$ or $B \subset v\mathbb{Z}.$" 1. At least one of $|A|,|B|$ is of the form $p$ or $p^i$ or $p^iq^j$ (then $v=p$ or $v=q$) The first counterexample has $|A|=30$ (and also $|B|=30$). Even the case of $|A|$ prime is, while easier than the later ones (cont.) – Aaron Meyerowitz Jan 5 '13 at 8:50
non-trivial (try $|A|=101$.) From this it follows that it is also sufficient that 2. $n$ has any of the forms $p,p^i,p^iq^j,p^iq^jr$ The first exception is $n=2^23^25^2=900.$ So this is indeed trivial if $n$ is prime. But I was tempted to go with this by the fact that the first exception is $n=900$ which seems more impressive then $30$. Of course the $900$ is because an exception must have $n=|A||B|$ where both $|A|$ and $|B|$ have three distinct prime divisors so $n=|A||B| \ge 30 \cdot 30.$ – Aaron Meyerowitz Jan 5 '13 at 8:55

Frankl and Wilson proved a certain theorem about set-systems with certain restrictions on their order and the order of their intersections modulo $p$ for $p$ prime, and wrote "it would be interesting to know whether it holds for composite $p$ as well" [1].

Frankl gave a counterexample for $p=6$, and Grolmusz [2] gave strong counterexamples for all $p$ with at least two prime factors.

[1] Frankl, P.; Wilson, R. M. Intersection theorems with geometric consequences. Combinatorica 1 (1981), no. 4, 357–368. http://www.ams.org/mathscinet-getitem?mr=647986

[2] Grolmusz, Vince Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs. Combinatorica 20 (2000), no. 1, 71–85. http://www.ams.org/mathscinet-getitem?mr=1770535;

-
Thank you but I think this rather fits to the category of true for only prime(power)s. I am looking for something not that hard to check for any $n$ but without a general proof. – domotorp Jan 3 '13 at 16:15
Oh - I didn't read the "and small numbers". Thanks for spotting that my statement of Grolmusz's result was not correct. – Colin McQuillan Jan 3 '13 at 16:35

An important question in matroid structure theory is given a matroid $M$, how many inequivalent representations does it have over a fixed finite field $\mathbb{F}$? Two $\mathbb{F}$-matrices $A$ and $B$ are equivalent if they are related by a projective transformation, in which case they clearly represent the same matroid.

In 1988, Kahn proved that $3$-connected $GF(4)$-representable matroids have a unique representation over $GF(4)$. In the same paper, he conjectured that for every prime power $q$, there is an $n(q)$, such that every $3$-connected $GF(q)$-representable matroid has at most $n(q)$ inequivalent representations. Oxley, Vertigan and Whittle proved Kahn's conjecture for $GF(5)$, but also showed that it fails for all larger finite fields. This naturally led to the question of what happens for $4$-connectivity, and the following weakening of Kahn's Conjecture.

Conjecture 1. For every prime power $q$, there is an $n(q)$ such that every $4$-connected $GF(q)$-representable matroid has at most $n(q)$ inequivalent representations over $GF(q)$.

One would expect that Conjecture $1$ holds for all finite fields, or fails for sufficiently large finite fields. However, remarkably there is a dichotomy depending on whether $q$ is prime!

Theorem 2. (Geelen and Whittle) For every prime $p$, there is an $n(p)$ such that every $4$-connected $GF(p)$-representable matroid has at most $n(p)$ inequivalent representations over $GF(p)$.

The proof of Theorem $2$ is not easy; the paper is $175$ pages.

Theorem 3. (Geelen, Gerards and Whittle) For every non-prime power $q \geq 9$, there is a $4$-connected $GF(q)$-representable matroid with arbitrarily many inequivalent representations over $GF(q)$.

-
Immediate question: what about 5-connected matroids and non-prime $q$? – Fedor Petrov Dec 19 '15 at 18:53
Actually, the examples in the Geelen, Gerards, and Whittle paper increase in connectivity as $q$ increases, so there is no fixed connectivity that will work for all finite fields. However, in joint work with Geelen, Gerards and van Zwam, we show that for each q, there is a connectivity c(q) and an n(q) such that every c(q)-connected GF(q)-representable matroid has at most n(q) inequivalent representations. We are still writing this up at the moment though. – Tony Huynh Dec 19 '15 at 19:16

Once it was conjectured (for a short time) that $2^p-2$ cannot be divisible by $p^2$ when $p$ is prime. The two known counterexamples are $1093$ and $3511$. For more detail and context read here.

-
I am sorry but I think you msunderstood the question. I want conjectures that are true for all primes but fail for some composite. – domotorp Jan 3 '13 at 9:05

The internal multiplicative structure of the set {1,2,3,...,n} may be mapped into a group of order n, preserving this multiplication. This is clearly possible when n+1=p, p a prime, just reduce mod p and when 2n+1=p, just use the squares mod p. But fails for composite values, for example 195.

Are there any other such maps for large values of n. One can always find a map when n<195. However they appear to get sparse for large values of n , except for those noted above.

-
See also mathoverflow.net/questions/26358/… (that Dömötör mentioned on the body of the question). – Andrés Caicedo Jan 4 '13 at 17:29
Sorry for missing that. – pollington Jan 4 '13 at 17:38
Yes, and unfortunately this is not a settled problem. – domotorp Jan 4 '13 at 18:35

An aliquot sequence is a recursive sequence in which each term is the sum of the proper divisors of the previous term. Catalan conjectured that no aliquot sequence is unbounded. The conjecture is trivially true for primes, since the aliquot sequence for $p$ is $p,1,0$ (terminating, since the sum of the proper divisors of zero is undefined). The conjecture is also true, by computation, for all $n\le275$. Strictly speaking, this doesn't qualify as an answer to the question, since there is no $n$ for which the conjecture has been proved to be false, but there are so many integers for which the aliquot sequence shows no sign of ever reaching a bound that it seems most plausible to conclude that the conjecture is false.

Here is a website dedicated to the problem.

-