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

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

2013-01-02T19:03:10Z

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.

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

2013-01-03T07:25:00Z

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.

Answer by Colin McQuillan for What are conjectures that are true for primes but then turned out to be false for some composite number?

2013-01-03T14:34:34Z

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;

Answer by Aaron Meyerowitz for What are conjectures that are true for primes but then turned out to be false for some composite number?

2013-01-03T19:42:21Z

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.

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

2013-01-04T17:20:33Z

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.