# Examples of eventual counterexamples

Define an "eventual counterexample" to be

• $P(a) = T$ for $a < n$

• $P(n) = F$

• $n$ is sufficiently large for $P(n) = T\ \ \forall n \in \mathbb{N}$ to be a 'reasonable' conjecture to make.

where 'reasonable' is open to interpretation, and similar statements for rational, real, or more abstractly ordered sets for $n$ to belong to are acceptable answers.

What are some examples of eventual counterexamples, famous or otherwise, and do different eventual counterexamples share any common features? Could we build an 'early warning system' set of heuristics for seemingly plausible theorems?

edit: The Polya conjecture is a good example of what I was trying to get at, but answers are not restricted to number theory or any one area.

-
Your question seems interesting. Could you put in at least one elementary example to explain your formal definition? – user2529 Feb 16 '10 at 13:18
I J Kennedy edited the title, changing "phenomena" to "phenomenon". Q Q J has now changed it back. I think "phenomenon" is better. It is an interesting phenomenon that there are eventual counterexamples. – Gerry Myerson Mar 31 '11 at 0:42
By the way... shouldn't it be "The phenonenON of eventual counterexamples"? – Mariano Suárez-Alvarez May 1 '11 at 5:48
The last 5 edits have consisted solely of toggling phenomena/phenomenon. Maybe we should just change the title to "Some eventual counterexamples". – Gerry Myerson Jul 2 '14 at 0:55
There are lots of answers that basically contain only the name of the result and a link to a paper/webpage; I find them very unhelpful and would like to invite the authors to put at least a quick explanation in the text of their answers. In general, link-only answers are frowned upon on many stack exchange websites. – Federico Poloni Oct 9 '14 at 14:30

I'm surprised no one has mentioned Graeco-Latin Squares http://en.wikipedia.org/wiki/Graeco-Latin_square

Euler showed these exist for $n$ odd, or any multiple of 4. As none exist for $n=2$ or $6$, he conjectured that none exist for any $n\equiv 2 (mod 4)$.

As it happens, such exist for any $n\geq 3$ except $6$. This is quite a famous example, if small.

-

The De Giorgi conjecture is true for dimensions $\leq 8$. I guess this doesn't really count because De Giorgi himself only conjectured it for those dimensions based on the fact that Bernstein Theorem of minimal graphs is only true in dimensions $\leq 8$...

(To stay within the realm of geometry, if someone finds a counterexample to the positive mass theorem in high dimensions, that would be an example too.)

-

I've had fun showing $1,2,4,8,16,31$ to people, both math and non-math people, actually. (OEIS)

-

R. M. Grassl and A. P. Mullhaupt, "Hook and Shifted Hook Numbers", Discrete Mathematics, Volume 79, Number 2, January (1990) pp. 153-167

"An infinite number of counter examples is provided for the conjecture that a shifted tableau shape is uniquely determined by its multiset of shifted hook numbers. Nevertheless, the previous conjecture of the first author that there was only one example of nonuniqueness is discussed and it is shown that it is «almost» true, based on computer search."

There were about five million examples before the counterexample, and approximately 1 mole of examples before the next counterexample is thought to occur.

-
The way I read the abstract (at sciencedirect.com/…), the 2nd counterexample came up somewhere in the first five million cases, and it was the 3rd counterexample that was expected to be a mole away. – Gerry Myerson Feb 18 '10 at 23:16
I think you're right. It's been a while since I looked at that; I'll edit my post. – Andrew Mullhaupt Feb 19 '10 at 0:58

It was a conjecture that number of three-dimensional Young diagram of volume $n$ is counted by the generating function $\prod(1-x^n)^{-n(n+1)/2}$, as analogous facts are true for usual Young diagrams (Euler) and two-dimensional (Macmahon?) It is so for first few coefficients, but fails in general.

-
MacMahon conjectured, but did not prove, the two-dimensional case. – Qiaochu Yuan May 5 '11 at 0:40

This one is a little bit a joke. If you calculate the powers $2^k$, it seems that the leading (decimal) digit can never be $7$.

Actually, the first digit happens to be $7$ not before $2^{46}$.

-
9 beats 7, holding out until $2^{53}$. – Gerry Myerson Feb 14 at 5:50
It's a joke because by taking logs, it should be immediately obvious that the density will be $\log_{10} 8 - \log_{10} 7$. – Todd Trimble Jun 27 at 18:17
If you look at the data, a better conjecture to make is that the leading digits of $2^n$ are periodic with period 10: they cycle through 2, 4, 8, 1, 3, 6, 1, 2, 5, 1 over and over for the first 40 powers of 2. The first time this pattern breaks is at $2^{46}$, where the expected 6 is a 7, as Denis points out. – KConrad Jun 30 at 0:31

I had a nice conjecture, but Robert Davis gave a counter-example to that. It boils down to the following:

Let the conditions $x_1\geq x_2 \geq \dots \geq x_p \geq 0$ and $x_1+\dots+x_d=n$ define the partition polytope $P(n,d)$. Let $\hat P(n,d)$ be the convex hull of the lattice points in $P(n,d)$.

Whenever $n+d\leq 25$, every integer point in the dilation $2\hat P(n,d)$ can be written as a sum of two integer points in $\hat P(n,d)$, but for $n=16$, $d=10$ there is a counterexample. The point $$({6, 6, 4, 3, 3, 3, 3, 2, 1, 1} ) \in 2\hat P(16,10)$$ is not expressible as a sum of two integer points in $P(16,10)$.

-

Consider the homomorphism defined by $\varphi(1) = 121; \ \varphi(2) = 12221$. This homomorphism has a infinite fixed point $r = r(0) r(1) r(2) \cdots$, which you obtain by iterating $\varphi$, starting with $1$.

Then the sequence $r$ satisfies the equality $r(16n+1) = r(64n+1)$ for $n = 0, 1, \ldots, 1864134$, but not for $n = 1864135$.

-
How is $\varphi$ a homomorphism, and of what? – Stefan Kohl Apr 9 at 12:49
It is a homomorphism on the free 2-generated monoid of strings on the 'letters' 1 and 2 (which can be extended to the blackboard bold Nth power of the alphabet to give one-sided infinite strngs). Gerhard "Benefits Of Universal Algebra Training" Paseman, 2016.04.09. – Gerhard Paseman Apr 9 at 16:38
I take it that $r_i$ and $r(i)$ are use interchangeably... – Yaakov Baruch Jun 27 at 20:32
Fixed, thanks very much. – Jeffrey Shallit Jun 27 at 22:09

While there is no known counterexample to the assumption that the probabilistic Baillie–PSW primality test is actually a proper primality test, there is strong evidence that there exist such counterexamples. -- In 1984, Carl Pomerance has even given a heuristic argument (see here) that for any $\epsilon > 0$ and large enough $x$, the number of composites $\leq x$ failing the test is larger than $x^{1-\epsilon}$ -- yet none is known so far.

-

Here is one from geometry where the number is small, yet larger than most people would guess.

Proposition: A regular polygon having n sides (n=3, 4, ...) can be constructed with a marked straightedge and compasses. We might suppose that a regular 11-gon would be the first counterexample. But Benjamin and Snyder proved otherwise in 2014, so the real first counterexample is not before n =23.

(Reference: ELLIOT BENJAMIN and C. SNYDER (2014). On the construction of the regular hendecagon by marked ruler and compass . Mathematical Proceedings of the Cambridge Philosophical Society, 156, pp 409-424 doi:10.1017/S0305004113000753)

-

Conditions:

$n$ such that $\ Ord_n(2) \mid n-1$ and $\ Ord_n(2) - 1 = 2^x,n \in 2 \mathbb{N}+1,\ x \in \mathbb{Z}_{\geq 0}$.

$\ Ord_n(b)\triangleq \min\{k\in\mathbb{N}:n|b^k-1\}$

$1227133513$ is the smallest known number matching the conditions which is not a prime number.

More info about $n=1227133513$:

$Ord_n(2) = 33$ and $n\ |\ 2^{33} - 1$.

$n-1=2^33^211\cdot31\cdot151\cdot331$

$n=(2^{33}-1)/7=23 \cdot 89 \cdot 599479$. $\ 599479\$ is one of the primes that match the conditions.

$n$'s base-$2$ representation is 10 occurrences of $100$, followed by $1$. Its base-$8$ representation is $11111111111$.

In the second of the sources listed below, another example $n=6657848551$ was given. Here

$Ord_n(2)=1025=2^{10}+1=5^2\cdot41$

$n-1=2\cdot3^25^217\cdot41\cdot21227$

$n=601\cdot1801\cdot 6151$

See:

http://math.stackexchange.com/questions/813293/are-there-composite-numbers-matching-the-conditions

-
To my surprise, 1227133513 appears in 17 sequences at the Online Encyclopedia of Integer Sequences. Only one seems at all related to its appearance here, namely, oeis.org/A086250 6657848551 is (currently) absent from the OEIS. – Gerry Myerson Jun 27 at 23:53

Nate Eldredge has mentioned the Skewes number,and in fact it is not the only place where we can speak of counterexamples, within number theory: The Riemann hypothesis is a fairly good case where counterexamples have been sought for through huge amounts of computations. In the paper "The $10^{13}$ ﬁrst zeros of the Riemann Zeta function, and zeros computation at very large height" by Xavier Gourdon and Patrick Demichel (using an algorithm by Andrew Odlyzko), the authors have checked out the truth of the Riemann hypothesis (that all non-trivial zeroes of $\zeta(s)$ are encountered whenever $s = 1/2 + \mathcal{i} T, \ T \in \mathbb{R}$), from the first, up to precisely the $10^{13}$th zero. In the same paper Riemann hypothesis has been tested numerically, checking out some $10^{9}$ zeroes from heights of $T$ as large as $10^{24}$. Now then, in spite of the fact that we have available such large amount of numerical evidence, this does not constitute a proof of the Riemann hypothesis, simply because the amount of zeroes is infinite, and there is no telling (yet) on whether we might encounter some day an instance of $\zeta(s) = 0, s = a + \mathcal{i} T, a\neq 1/2$, and we might as well wait long time for a numerical counterexample, much in the same philosophy mentioned in Nate Eldredge's answer, and all this would constitute the answer to the second part of your first question: "do different eventual counterexamples share any common features?". In the cases discussed by Eldredge and in here, the common feature of the (possible) counterexamples is that in both cases a gigantic amount of numerical evidence was (has been, in the case of the Riemann hypothesis) amassed, and still there was (there is) the possibility of finding a counterexample.

Numerical calculations are still useful, tough, because there has been instances where the calculation does not have to be carried out that far. For example, the so-called Fermat's Little Theorem states that all numbers of the form $2^{2^{n}}+1$ are primes, and Fermat carried up calculations up to $n=4$. However, when $n=5$, Euler proved that such was no longer the case, since this "Fermat Number" can be factored into 641 and 6700417.

As for your second question: "Could we build an 'early warning system' set of heuristics for seemingly plausible theorems?" I am going to answer with something that must be taken "with a pinch of salt", but it is the closest I can think of an answer. I want you to refer to the p vs np problem (Polynomial time computer solving as opposite to Non-polynomial time algorithms). Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. I imagine, if someone solves this computer unsolved problem (finding a polynomial-time running algorithm for a known non-polynomial time problem), then perhaps we could answer your second question in the positive sense, at least for those theorems which involve computable problems. For other types of theorems (say, one non-expressible algorithmically) I cannot imagine at the moment how can one could set up anything that would resemble somehow an 'early warning system' (but it would be interesting, though, if someone could furnish something like that, at least for a restricted problem :-) ).

-

$1223$ is the smallest odd prime which does not divide any Carmichael number with $3$ prime factors -- cf. e.g. here.

-

Let $S_m$ denote the symmetric group on $n$ letters and let $P(m)$ denote the size of the outer automorphism group of $S_m$, i.e., the size of the quotient $\mathrm{Aut}/\mathrm{Inn}$ where $\mathrm{Inn}$ is the group of inner automorphisms (the ones induced by conjugation by an element of the group). Then $$\begin{cases} P(m)=1 &\text{ if } m\neq 6 \\ P(m)=2 &\text{ if } m= 6. \end{cases}$$ Of course, the "counter example" is not for a particularly large value, but only for a single one.

-
Then it's not a case of eventual counterexamples, is it? – Harry Altman May 1 '11 at 20:14
Dear Harry, I was sure someone would bring up this issue and even thought about making a comment on that. Sure. You are correct. Nevertheless, I believe this is a surprising fact. If you really want an "eventual counter example", then consider the function $Q(m)=P([m/N])$ for any $N\gg 0$. The philosophy of the question is, I think, about phenomena that seems to conform to a certain pattern for many many examples but does not do so for all examples. This certainly qualifies for that. If it still bothers your sense of justice, please feel free to vote it down. Cheers! – Sándor Kovács May 1 '11 at 20:58
It's an eventual counterexample if you start at infinity and work your way down. – Gerry Myerson May 1 '11 at 23:47
I second Gerry's comment. :) – Sándor Kovács May 2 '11 at 0:21

the Weaire–Phelan structure was found to be

a better solution of the "Kelvin problem" than the previous best-known solution, the Kelvin structure.

-
This is not a counterexample, eventual or otherwise, in the sense of this question, is it? – Gerry Myerson May 1 '11 at 23:46
@Gerry really? "The Kelvin conjecture was widely believed and no counter-example was known for more than 100 years, until it was disproved by the discovery of the Weaire–Phelan structure." – pageman May 2 '11 at 10:04
"Eventual", in the sense of this question, does not refer to time, but to number. – Gerry Myerson May 2 '11 at 12:48