What are conjectures that are true for primes but then turned out to be false for some composite number? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T14:22:49Z http://mathoverflow.net/feeds/question/117891 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/117891/what-are-conjectures-that-are-true-for-primes-but-then-turned-out-to-be-false-for What are conjectures that are true for primes but then turned out to be false for some composite number? domotorp 2013-01-02T19:03:10Z 2013-01-04T17:20:33Z <p>Note: This is an update formulation since many people misunderstood the question before.</p> <p>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?</p> <p>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$.</p> <p>Also the existence of <a href="http://en.wikipedia.org/wiki/Carmichael_number" rel="nofollow">Carmichael number</a>s 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 <a href="http://arxiv.org/abs/0910.4987" rel="nofollow">solved is Colorful Tverberg</a>, still unknown is <a href="http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture" rel="nofollow">Evasiveness</a> or <a href="http://mathoverflow.net/questions/26358/can-we-color-z-with-n-colors-such-that-a-2a-na-all-have-different-colors" rel="nofollow">this little MO problem</a>.</p> http://mathoverflow.net/questions/117891/what-are-conjectures-that-are-true-for-primes-but-then-turned-out-to-be-false-for/117936#117936 Answer by GH for What are conjectures that are true for primes but then turned out to be false for some composite number? GH 2013-01-03T07:25:00Z 2013-01-03T07:25:00Z <p>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 <a href="http://en.wikipedia.org/wiki/Wieferich_prime" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/117891/what-are-conjectures-that-are-true-for-primes-but-then-turned-out-to-be-false-for/117962#117962 Answer by Colin McQuillan for What are conjectures that are true for primes but then turned out to be false for some composite number? Colin McQuillan 2013-01-03T14:34:34Z 2013-01-03T16:33:04Z <p>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].</p> <p>Frankl gave a counterexample for $p=6$, and Grolmusz [2] gave strong counterexamples for all $p$ with at least two prime factors.</p> <p>[1] Frankl, P.; Wilson, R. M. <em>Intersection theorems with geometric consequences.</em> Combinatorica 1 (1981), no. 4, 357–368. <a href="http://www.ams.org/mathscinet-getitem?mr=647986" rel="nofollow">http://www.ams.org/mathscinet-getitem?mr=647986</a></p> <p>[2] Grolmusz, Vince <em>Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs.</em> Combinatorica 20 (2000), no. 1, 71–85. <a href="http://www.ams.org/mathscinet-getitem?mr=1770535" rel="nofollow">http://www.ams.org/mathscinet-getitem?mr=1770535</a>; </p> http://mathoverflow.net/questions/117891/what-are-conjectures-that-are-true-for-primes-but-then-turned-out-to-be-false-for/117985#117985 Answer by Aaron Meyerowitz for What are conjectures that are true for primes but then turned out to be false for some composite number? Aaron Meyerowitz 2013-01-03T19:42:21Z 2013-01-04T09:37:06Z <p>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$.</p> <p>The <a href="http://en.wikipedia.org/wiki/Cyclotomic_polynomial" rel="nofollow">cyclotomic polynomials</a> $\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$</p> <p>The second example is of great interest to me, but takes a little explanation For a finite integer set $A$, we say that $A$ <strong>tiles the integers by translation</strong> 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.$ </p> <p>Consider this property enjoyed by certain integers $m$: </p> <blockquote> <p>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}.$ </p> </blockquote> <p>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 <code>$\max{A} \gt 720$</code> (if we set $\min{A}=0$. )</p> <p>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$. </p> <blockquote> <p>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}.$ </p> </blockquote> <p>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.</p> <p>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 <a href="http://arxiv.org/abs/math.CO/9802122" rel="nofollow">Tiling the integers with translates of one finite set</a> which also proves the claims above and shows a link to cyclotomic polynomials.</p> <p>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 <code>$A \oplus C=\mathbb{Z}$</code> if and only if there is a set $C'$ with <code>$A' \oplus C'=\mathbb{Z}$</code> 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}.$</p> <p>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.</p> http://mathoverflow.net/questions/117891/what-are-conjectures-that-are-true-for-primes-but-then-turned-out-to-be-false-for/118071#118071 Answer by pollington for What are conjectures that are true for primes but then turned out to be false for some composite number? pollington 2013-01-04T17:20:33Z 2013-01-04T17:20:33Z <p>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. </p> <p>Are there any other such maps for large values of n. One can always find a map when n&lt;195. However they appear to get sparse for large values of n , except for those noted above.</p>