Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
5  
Your question seems interesting. Could you put in at least one elementary example to explain your formal definition? –  Colin Tan Feb 16 '10 at 13:18
1  
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
1  
By the way... shouldn't it be "The phenonenON of eventual counterexamples"? –  Mariano Suárez-Alvarez May 1 '11 at 5:48
2  
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 at 0:55
show 8 more comments

37 Answers 37

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.

share|improve this answer
show 1 more comment

Hmmm ... as yet, no examples have been given from geometry or dynamics. So here's one.

Supposing that we interpret $P(a)=T$ for $a<n$ to mean "geometric objects have property $P$ for most objects that arise naturally", and let $P$ be the ergodic property, then the Kolmogorov–Arnold–Moser theorem suggests itself as providing the "eventual counterexample."

Domokos Szasz' article "Boltzmann's Ergodic Hypothesis, a Conjecture for Centuries?" (1994) provides an historical overview of the long slow process by which dynamical conjectures that for centuries were widely believed, were eventually proved to be wrong.


Another (related) answer:

In Conway's LIFE game, if the starting patterns are arranged in lexical order, the first self-replicating life-form (known at present) is Andrew J. Wade's Gemini.

The Gemini life-form can be viewed as the first (known) counter-example to the hypothesis "life-forms are not self-replicating". The lexical index of Gemini (as computed from its bounding-box) is $2^{4217807\times4220191}$ ... obviously too large to find by a blind search.

It seems to be generically true of life-forms (both biological-type and Conway-type)—and perhaps formal proofs too?—that special properties are emergent at very large lexical order-number of starting structures.

share|improve this answer
add comment

This came up a few years ago from an error I noticed in the OEIS database. For all $0 \leq n \leq 58$, the numerator of $\sum_{k=0}^n \frac{2^{k+1}-1}{k+1}$ is equal to the numerator of $\sum_{k=0}^n \binom{n}{k}/(k+1)^2$. This fails first at $n=59$ and then at $n=1519, 7814, \ldots$. See A134652.

share|improve this answer
add comment

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.

share|improve this answer
1  
Then it's not a case of eventual counterexamples, is it? –  Harry Altman May 1 '11 at 20:14
5  
It's an eventual counterexample if you start at infinity and work your way down. –  Gerry Myerson May 1 '11 at 23:47
show 2 more comments

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}$.

$1227133513$ is the only known number matching the conditions but not a prime number. For next composite number they say need to go above $10^{385}$.

More info of $1227133513$:

$Ord_{1227133513}(2)$ = 33 and $1227133513\ |\ 2^{33} - 1$.

$1227133513=23 \cdot 89 \cdot 599479$ and $\ 599479\ $ is one of the primes that matching the conditions.

$1227133513$'s base $2$ is '100' repeats $10$ times then end with $1$,it's base $8$ is $11111111111$.

See:

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

http://www.mersenneforum.org/showthread.php?t=19393

share|improve this answer
add comment

the Weaire–Phelan structure was found to be

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

share|improve this answer
3  
"Eventual", in the sense of this question, does not refer to time, but to number. –  Gerry Myerson May 2 '11 at 12:48
show 2 more comments

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}$ first 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 :-) ).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.