181
$\begingroup$

Define an "eventual counterexample" to be

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

  • $P(n) = F$

  • $n$ is sufficiently large for $P(a) = T\ \ \forall a \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.

$\endgroup$
18
  • 7
    $\begingroup$ Your question seems interesting. Could you put in at least one elementary example to explain your formal definition? $\endgroup$
    – user2529
    Feb 16, 2010 at 13:18
  • 3
    $\begingroup$ 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. $\endgroup$ Mar 31, 2011 at 0:42
  • 2
    $\begingroup$ By the way... shouldn't it be "The phenonenON of eventual counterexamples"? $\endgroup$ May 1, 2011 at 5:48
  • 7
    $\begingroup$ The last 5 edits have consisted solely of toggling phenomena/phenomenon. Maybe we should just change the title to "Some eventual counterexamples". $\endgroup$ Jul 2, 2014 at 0:55
  • 7
    $\begingroup$ The ring of integers of $\Bbb Q(\sqrt[n]{2})$ is not always $\Bbb Z[\sqrt[n]{2}]$. It is true for $n < 1000$, but not for $n=1093$. See kconrad.math.uconn.edu/blurbs/gradnumthy/integersradical.pdf. $\endgroup$
    – Watson
    Jun 5, 2021 at 14:47

60 Answers 60

1
2
11
$\begingroup$

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

$\endgroup$
3
  • 5
    $\begingroup$ 9 beats 7, holding out until $2^{53}$. $\endgroup$ Feb 14, 2016 at 5:50
  • 2
    $\begingroup$ It's a joke because by taking logs, it should be immediately obvious that the density will be $\log_{10} 8 - \log_{10} 7$. $\endgroup$
    – Todd Trimble
    Jun 27, 2016 at 18:17
  • 7
    $\begingroup$ 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. $\endgroup$
    – KConrad
    Jun 30, 2016 at 0:31
11
$\begingroup$

Robert Baillie has a paper on arxiv today (https://arxiv.org/abs/1105.3943) which shows how in principle one can construct examples of formulae which hold for $N=0,1,2,\ldots,k$, for arbitrarily large $k$, then fail for all larger $N$.

His largest example holds with $k\approx \exp(\exp(\exp(\exp(\exp(\exp(e))))))$.

$\endgroup$
1
  • 4
    $\begingroup$ That's the same paper Seva linked to in his answer, posted about 3 hours earlier than this one. $\endgroup$ May 20, 2011 at 10:47
11
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

From the Wikipedia category of disproved conjectures:

  • Borsuk's conjecture
  • The Chinese hypothesis
  • Euler's sum of powers conjecture
$\endgroup$
10
$\begingroup$

Here's a recent one I didn't see on either page. The following are true statements:

$\displaystyle{ \int_0^\infty \frac{\sin t}{t} \, dt = \frac{\pi}{2} }$
$\displaystyle{ \int_0^\infty \frac{\sin t}{t} \, \frac{\sin \left(\frac{t}{101}\right)}{\frac{t}{101}} \, dt = \frac{\pi}{2} }$
$\displaystyle{ \int_0^\infty \frac{\sin t}{t} \, \frac{\sin \left(\frac{t}{101}\right)}{\frac{t}{101}} \, \frac{\sin \left(\frac{t}{201}\right)}{\frac{t}{201}} \, dt = \frac{\pi}{2} }$
$\displaystyle{ \int_0^\infty \frac{\sin t}{t} \, \frac{\sin \left(\frac{t}{101}\right)}{\frac{t}{101}} \, \frac{\sin \left(\frac{t}{201}\right)}{\frac{t}{201}} \, \frac{\sin \left(\frac{t}{301}\right)}{\frac{t}{301}} \, dt = \frac{\pi}{2} }$

Is it true that

$\forall n,\displaystyle{ \int_0^\infty \prod_0^n\frac{\sin \left(\frac{t}{100n+1}\right)}{\frac{t}{100n+1}} \, dt = \frac{\pi}{2} }$

?


No, it's not. However, you could have a computer calculating this for the rest of your life and never find a counter-example. The first counter-example for n has 43 digits.

I found this example here. It was specially constructed to have a large counter-example - the page gives a way to construct similar statements with arbitrarily large counter-examples.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 18, 2010 at 23:16
  • $\begingroup$ I think you're right. It's been a while since I looked at that; I'll edit my post. $\endgroup$ Feb 19, 2010 at 0:58
7
$\begingroup$

The Busemann-Petty Problem.

$\endgroup$
7
$\begingroup$

The sequence $$1, 19, 9243, 540569, 71564873\dots$$ giving the absolute value of the real part of $(19+98i)^n$, $n=0,1,\dots$ is monotone increasing – until you get to $n=484$. The real part of $(19+98i)^{484}$ is $4.2157\times10^{965}$ (to five significant figures), which is less than the real part of $(19+98i)^{483}$, which is $4.2176\times10^{965}$.

This comes from Bruce Reznick, On the nonmonotonicity of (|Im(zn)|), Journal of Number Theory Volume 78, Issue 1, Pages 144-148 (September 1999), MR1706901 (2001a:11134).

$\endgroup$
3
  • $\begingroup$ Reznick - On the non-monotonicity of $\lvert\operatorname{Im}(z^n)\rvert$ (MSN). $\endgroup$
    – LSpice
    May 28, 2019 at 19:55
  • 3
    $\begingroup$ There isn't anything special about $19+98i$ here, by the way - the results of the paper imply that this holds for powers of any Gaussian integer $a+bi$ except those with $a = 0, b = 0$, or $|a| = |b|$. The paper was published in 1999 and presumably written in 1998. $\endgroup$ Feb 25, 2021 at 17:10
  • $\begingroup$ @Michael, yes, I have a preprint from Bruce, dated 12 June 1998. $\endgroup$ Feb 25, 2021 at 22:51
6
$\begingroup$

Let $Q(n), n \in \mathbb{N}$ denote Hofstadter's Q sequence -- i.e. $Q(1) = Q(2) = 1$, and $Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))$ for $n > 2$. Then we have:

  • $Q(3 \cdot 2^0) = 2$,
  • $Q(3 \cdot 2^1) = 4$,
  • $Q(3 \cdot 2^2) = 8$,
  • $Q(3 \cdot 2^3) = 16$,
  • $Q(3 \cdot 2^4) = 32$,
  • $Q(3 \cdot 2^5) = 64$,
  • $Q(3 \cdot 2^6) = 128$,
  • $Q(3 \cdot 2^7) = 256$,
  • $Q(3 \cdot 2^8) = 512$

Guess something? -- Well, NO! --

  • $Q(3 \cdot 2^9) = 808$,
  • $Q(3 \cdot 2^{10}) = 1627$,
  • $Q(3 \cdot 2^{11}) = 3127$,
  • $Q(3 \cdot 2^{12}) = 6113$
$\endgroup$
6
$\begingroup$

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.)

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ MacMahon conjectured, but did not prove, the two-dimensional case. $\endgroup$ May 5, 2011 at 0:40
5
$\begingroup$

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

$\endgroup$
3
  • 7
    $\begingroup$ How is $\varphi$ a homomorphism, and of what? $\endgroup$
    – Stefan Kohl
    Apr 9, 2016 at 12:49
  • 4
    $\begingroup$ 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. $\endgroup$ Apr 9, 2016 at 16:38
  • $\begingroup$ I take it that $r_i$ and $r(i)$ are use interchangeably... $\endgroup$ Jun 27, 2016 at 20:32
5
$\begingroup$

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[1], so the real first counterexample is not before $n = 23$.

Reference

  1. 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)
$\endgroup$
2
  • $\begingroup$ So this is not in fact a counterexample? The result of Benjamin and Snyder is that $11$ is not a counterexample to the statement labeled a "Proposition" (which apparently has the status of an open conjecture)? $\endgroup$ Oct 20, 2022 at 3:23
  • $\begingroup$ That's why we had to push the first counterexample to 23. $\endgroup$ Oct 20, 2022 at 3:57
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

To extend my previous answer, in the world of polytopes, there are plenty of eventual counter-examples.

I ran into several such counter-examples in my research, and put them together here (arxiv).

Some of the smallest counter-examples I have show up in dimensions >100.

I saw another comment regarding hooks, which have a polytope interpretation (hook values determine a volume of a certain polytope). It is natural to ask if hook values determine the Ehrhart polynomial also, but this fails for a pair of partitions of size 16.

$\endgroup$
4
$\begingroup$

The Laver tables give and will continue to give examples of sentences $\forall n P(n)$ which are known to be false under strong large cardinal assumptions but where no such $n$ where $P(n)$ is false has been explicitly found nor is known to exist under any weaker large cardinal assumptions. Since set theorists typically believe in either the consistency or the existence of large cardinals and since the algebraic structures that arise from the sufficiently strong large cardinal embeddings support the existence of such strong large cardinal hypotheses. Furthermore, since the classical Laver tables and similar structures are constructed using a double recursion that resembles the Ackermann function, one should expect the Laver tables to produce many examples of eventual counterexamples.

The Laver tables should be thought of as a combinatorial object that has many features such that under large cardinal assumptions, there will always come a point where these features no longer hold.

All these results on the final matrix and the Laver-like algebras are my own while the results on the classical Laver tables are not my own.

Classical Laver tables

The $n$-th classical Laver table is the unique algebra $A_{n}=(\{1,\dots,2^{n}\},*_{n})$ where $x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z),x*_{n}1=x+1\mod 2^{n}$ for $x,y,z\in\{1,\dots,2^{n}\}$.

Under strong large cardinal hypotheses, the classical Laver tables should be thought of as algebraic structures consisting of patterns that will all eventually end but only after a very long time.

If $x\in A_{n}$, then let $o_{n}(x)$ be the least number $m$ with $x*_{n}2^{m}=2^{n}$. If $x\in\{1,\dots,2^{n}\}$, then let $\vartheta_{n}(x)$ be the least number $m$ with $x*_{n+1}m>2^{n}$.

Fact: (Randall Dougherty) If $n<\mathrm{Ack}(9,\mathrm{Ack}(8,\mathrm{Ack}(8,254)))$, then $o_{n}(1)<5$.

Eventual counterexamples: (Richard Laver) If for all $n$, there exists an $n$-huge cardinal, then $\lim_{n\rightarrow\infty}o_{n}(1)\rightarrow\infty$. No upper bound for the least $n$ with $o_{n}(1)=5$ has proven in ZFC. This fact the source of many eventual counterexamples one may have about the classical Laver tables.

Fact: If $n<9$ and $o_{n}(x)=o_{n+1}(x)=o_{n+2}(x)$, then $\vartheta_{n+1}(x)\leq\vartheta_{n}(x)$. Thomas Jech conjectured that this result holds for all $n$, but a suitably motivated human could even have computed a counterexample by hand, so this conjecture is easily disproven.

Eventual counterexample: $o_{9}(34)=o_{10}(34)=o_{11}(34)$, but $\vartheta_{9}(34)=5,\vartheta_{10}(34)=8$.

Eventual counterexample: A linear ordering $\preceq$ on $A_{n}$ is said to be compatible with $A_{n}$ if $y\preceq z\Rightarrow x*_{n}y\preceq x*_{n}z$. If $n>0$ and $\preceq$ is a linear ordering on $A_{n}$ compatible with $A_{n}$, then define a linear ordering $\preceq'$ on $A_{n-1}$ by letting $x\preceq^{'}y$ iff $x+2^{n-1}\preceq x+2^{n-1}$.

Let $P(n)$ denote the statement that for every linear ordering $\preceq^{\sharp}$ on $A_{n-1}$, there is a linear ordering $\preceq$ on $A_{n}$ with $\preceq'=\preceq^{\sharp}$. Then $P(n)$ is true for $n\leq 17$, but $P(18)$ is false.

The final matrix

If $A$ is a set, then let $(A^{\leq 2^{n}})^{+}$ denote the collection of all non-empty strings from the alphabet $A$ with length at most $n$. Then $(A^{\leq 2^{n}})^{+}$ can be endowed with a unique operation $*_{n}$ that satisfies the following rules:

  1. $\mathbf{x}*_{n}(\mathbf{y}*_{n}\mathbf{z})=(\mathbf{x}*_{n}\mathbf{y})*_{n}(\mathbf{x}*_{n}\mathbf{z})$ for $\mathbf{x},\mathbf{y},\mathbf{z}\in(A^{\leq 2^{n}})^{+}$.

  2. $\mathbf{x}*_{n}\mathbf{y}=\mathbf{y}$ whenever $|\mathbf{x}|=2^{n}$, and

  3. $\mathbf{x}*_{n}a=\mathbf{x}a$ whenever $|\mathbf{x}|<2^{n},a\in A$.

Let $FM_{n}^{-}:\{1,\dots,2^{n}\}\times\{1,\dots,2^{n}\}\rightarrow\mathbb{Z}$ be the mapping where if $r$ is the least natural number where $|a_{-1}\dots a_{-i}*_{n}a_{1}\dots a_{r}|=2^{n}$, then $$a_{-1}\dots a_{-i}*_{n}a_{1}\dots a_{r}=a_{FM_{n}^{-}(i,1)}\dots a_{FM_{n}^{-}(i,2^{n})}.$$ We shall call $FM_{n}^{-}$ the final matrix.

The motivation behind the data $FM_{n}^{-}$ is that all the combinatorial complexity about the operation $*_{n}$ is coded inside the function $FM_{n}^{-}$.

  1. For $n<7$, if $FM_{n}^{-}(x,y)>0$ and $y\leq 2^{n-1}$, then $FM_{n}^{-}(x,y+2^{n-1})>0$ as well. However, $FM_{7}^{+}(8,16)=1,FM_{7}^{+}(8,16+2^{6})=-4$.

  2. If $n<9$ and $FM_{n}^{-}(i,j)>0,FM_{n}^{-}(i,j+1)>0$, then $FM_{n}^{-}(i,j+1)=FM_{n}^{-}(i,j)+1$. But

$FM_{9}^{-}(8,175)=1,FM_{9}^{-}(8,176)=3$,

$FM_{9}^{-}(8,191)=1,FM_{9}^{-}(8,192)=4,$ and

$FM_{9}^{-}(8,143)=1,FM_{9}^{-}(8,144)=1$.

  1. If $n<11$ and $FM_{n}^{-}(i,j)>0,FM_{n}^{-}(i,j+1)>0$, then $FM_{n}^{-}(i,j+1)\geq FM_{n}^{-}(i,j)-1,$ but $FM_{11}^{-}(8,255)=3,FM_{11}^{-}(8,256)=1$.

  2. If $n<7,FM_{n}^{-}(x,y)>0$, then $\gcd(2^{n},x,y)\leq\gcd(2^{n},FM_{n}^{-}(x,y))$, but $FM_{7}^{-}(8,16)=1$.

The following counterexamples form $FM_{n}^{-}$ have only been established through large cardinal hypotheses.

Let $(x)_{a}$ be the unique natural number where $x=(x)_{a}\mod a$ and $1\leq (x)_{a}\leq a$.

Let $ST_{0}=\{(1,1)\}$. Let $(x,y)\in ST_{n+1}$ if and only if $((x)_{2^{n}},(y)_{2^{n}})\in ST_{n}$ and either $x\leq 2^{n}$ or $y>2^{n}$.

$\textbf{Hypothesis:}$ $(SE_{n})$

Suppose that $i,j\in\{0,\ldots,2^{n}-1\}$. Then

  1. $FM_{2^{n}}^{-}(2^{i},2^{j})>0$ if and only if $i$ is even, $j$ is odd, and $(i+1,j)\in \mathrm{ST}_{n}$.

  2. If $FM_{2^{n}}^{-}(2^{i},2^{j})>0$, then $FM_{2^{n}}^{-}(2^{i},2^{j})=2^{i}.$

  3. Suppose that $FM_{2^{n}}^{-}(2^{i},2^{j})<0$. Then $FM_{2^{n}}^{-}(2^{i},2^{j})=-2^{k}$ for some $k$. Furthermore,

i. if $j$ is odd, then $0<k\leq i$, and $$FM_{2^{n}}^{-}(2^{i'},2^{j})=-2^{k}$$ for $k\leq i'\leq i$, and $$FM_{2^{n}}^{-}(2^{k-1},2^{j})=2^{k-1}.$$

ii. if $j$ is even and $FM_{2^{n}}^{-}(2^{i},2^{j+1})>0$, then $$FM_{2^{n}}^{-}(2^{i},2^{j})=-FM_{2^{n}}^{-}(2^{i},2^{j+1}).$$

iii. if $j$ is even and $FM_{2^{n}}^{-}(2^{i},2^{j+1})<0$, then $$2\cdot FM_{2^{n}}^{-}(2^{i},2^{j})=FM_{2^{n}}^{-}(2^{i},2^{j+1}).$$ . The following table gives a picture for the hypothesis $SE_{4}$. The $(i,j)$-th entry in the following table is set to be $+\log_{2}(FM_{16}^{+}(2^{i},2^{j})$ whenever $FM_{16}^{+}(2^{i},2^{j})>0$ and it is set to be $-\log_{2}(-FM_{16}^{+}(2^{i},2^{j})$ whenever $FM_{16}^{+}(2^{i},2^{j})<0$.

$\begin{array}{r|rrrrrrrrrrrrrrrrr} &0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline 0&-0&+0&-0&+0&-0&+0&-0&+0&-0&+0&-0&+0&-0&+0&-0&+0&4\\ 1&-0&-1&-0&-1&-0&-1&-0&-1&-0&-1&-0&-1&-0&-1&-0&-1&4\\ 2&-0&-1&-2&2&-0&-1&-2&2&-0&-1&-2&2&-0&-1&-2&2&4\\ 3&-0&-1&-2&-3&-0&-1&-2&-3&-0&-1&-2&-3&-0&-1&-2&-3&4\\ 4&-0&-1&-2&-3&-4&4&-4&4&-0&-1&-2&-3&-4&4&-4&4&7\\ 5&-0&-1&-2&-3&-4&-5&-4&-5&-0&-1&-2&-3&-4&-5&-4&-5&8\\ 6&-0&-1&-2&-3&-4&-5&-6&6&-0&-1&-2&-3&-4&-5&-6&6&8\\ 7&-0&-1&-2&-3&-4&-5&-6&-7&-0&-1&-2&-3&-4&-5&-6&-7&8\\ 8&-0&-1&-2&-3&-4&-5&-6&-7&-8&8&-8&8&-8&8&-8&8&11\\ 9&-0&-1&-2&-3&-4&-5&-6&-7&-8&-9&-8&-9&-8&-9&-8&-9&12\\ 10&-0&-1&-2&-3&-4&-5&-6&-7&-8&-9&-10&10&-8&-9&-10&10&12\\ 11&-0&-1&-2&-3&-4&-5&-6&-7&-8&-9&-10&-11&-8&-9&-10&-11&12\\ 12&-0&-1&-2&-3&-4&-5&-6&-7&-8&-9&-10&-11&-12&12&-12&12&14\\ 13&-0&-1&-2&-3&-4&-5&-6&-7&-8&-9&-10&-11&-12&-13&-12&-13&14\\ 14&-0&-1&-2&-3&-4&-5&-6&-7&-8&-9&-10&-11&-12&-13&-14&14&15\\ 15&-0&-1&-2&-3&-4&-5&-6&-7&-8&-9&-10&-11&-12&-13&-14&-15&15\\ 16&+0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \end{array}$

Theorem: If there exists a rank-into-rank cardinal, then there is a natural number $n$ where $SE_{n}$ is false.

I can currently calculate an arbitrary entry in the table $FM_{n}^{-}$ whenever $n\leq 48$. With modern computational technology, it should be possible to calculate arbitrary entries in $FM_{n}^{-}$ for $n\leq 96$. I have experimentally verified $SE_{n}$ for $n\leq 5$, and it is feasible to verify $SE_{6}$ as soon as someone gets the time to do so. I suspect that the least $n$ where $SE_{n}$ fails is exceedingly large. Perhaps, $SE_{n}$ is larger than the running time of any computer program of length at most $10^{100}$ characters which can be proven to terminate in "ZFC+There is a supercompact cardinal" with a proof of length at most $10^{1000}$.

$\textbf{Hypothesis:}$ ($EP_{n}$) Suppose that $r$ is a natural number and $x<2^{2^{r}}-1$. Then $FM_{n}^{-}(x,2^{y})=FM_{n}^{-}(x,2^{z})$ whenever $y=z\mod 2^{r}$ and $\max(y,z)<j\cdot 2^{r}<n$ for some $j$.

$\textbf{Theorem:}$ If there exists a rank-into-rank cardinal, then there is a natural number $n$ where $EP_{n}$ is false.

No known counterexample to $EP_{n}$ is known to exist in ZFC.

Laver-like counterexamples

Define the Fibonacci terms $t_{n}(x,y)$ for all $n\geq 1$ by letting $t_{1}(x,y)=y,t_{2}(x,y)=x,t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y)$.

We say that an algebra $(X,*,1)$ that satisfies the identities $x*1=1,1*x=x,x*(y*z)=(x*y)*(x*z)$ is permutative if for all $x,y\in X$, there is some $n$ where $t_{n}(x,y)=1$. Define $x^{0}*y=y,x^{n+1}*y=x*(x^{n}*y)$ for $n\geq 0$. Define $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ if and only if there Is some $n$ with $x^{n}*y=1$. Then $\{\mathrm{crit}(x)\mid x\in X\}$ is always linearly ordered set. There is a unique operation $\circ$ on $X$ where $(X,\circ,1)$ is a monoid and $x\circ y=(x*y)\circ x$ for all $x,y\in X$.

$\mathbf{Theorem:}$ Suppose that all large cardinals exist. Suppose that $s,t,u$ are terms in the language $*,\circ$ with $s,t$ unary and $u$ binary. Suppose furthermore that $A_{1}\models\mathrm{crit}(s(x))=\mathrm{crit}(t(x))=\mathrm{crit}(x)$. Then there is a finite permutative algebra $(X,*,1)$ along with $x,y\in X$

  1. $s(x)*x=s(y)*y$

  2. $u(x,y)\neq 1$

  3. $\mathrm{crit}(x)=\mathrm{crit}(y)$

  4. $\mathrm{crit}(r*r*s)\leq\mathrm{crit}(r*s)$ for all $r,s\in X$.

In the above theorem, for some very simple terms $u,s,t$, I have not been able to compute examples of such algebras.

Besides these counterexamples which are known to exist, there are many different kinds of Laver-like algebras which I conjecture to exist but for which I have no proof even if I assume large cardinals exist and for which I conjecture the first example of such algebra is extremely large.

$\endgroup$
4
$\begingroup$

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:

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

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 27, 2016 at 23:53
4
$\begingroup$

A nice eventual counterexample comes from here: For every integer $n\ge 2$ , define $$f(n):=\Phi_n(n)$$ where $\Phi(n)$ is the $n$ th cyclotomic polynomial. Then $f(n)$ is squarefree for all $n<28341$, but $$283411^2\mid \Phi_{28341}(28341).$$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Ed Sandifer has a nice article for the MAA wherein he describes Euler's attempts to derive a recursion for the central trinomial coefficients (OEIS A002426).

Euler lets the reader think he has derived such a formula as $a_{n+1}=3a_n-F_n(F_n+1)$ (OEIS A011769), but they disagree after the 9th term.

Euler calls this eventual counterexample an "EXEMPLUM MEMORABILE INDUCTIONIS FALLACIS," which has a pretty good ring to it.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

The equation $x^3+y^3=313^2z^3$ (or the closely-related equation $313(x^3+y^3)=z^3$) has attracted some attention. All the results I will mention can be found at https://math.stackexchange.com/questions/1613119/a-diophantine-equation-with-only-titanic-solutions

Elkies found the smallest solution in integers, $$\small x_0 = 355507307842882624593086325021133856149447336710120844428552934573043094018915 289363\\ \small y_0 = -354602746692986709129018423204648314355484458881941451025238387384142099383045 862152 \\ \small z_0 =1517122651849438712721950935044230084378368307868200665761294465082177989014675811$$

Note that $y_0<0$. Tito Piezas III reports a solution in positive integers with $z$ a bit larger than $10^{21388}$. Allan MacLeod reports a solution in positive integers with roughly $6770$ digits, although it's not clear to me that MacLeod is solving exactly the same equation.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Then it's not a case of eventual counterexamples, is it? $\endgroup$ May 1, 2011 at 20:14
  • $\begingroup$ 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! $\endgroup$ May 1, 2011 at 20:58
  • 9
    $\begingroup$ It's an eventual counterexample if you start at infinity and work your way down. $\endgroup$ May 1, 2011 at 23:47
  • $\begingroup$ I second Gerry's comment. :) $\endgroup$ May 2, 2011 at 0:21
1
$\begingroup$

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 :-) ).

$\endgroup$
0
1
$\begingroup$

There is a famous paper by John Milnor, "On fundamental groups of complete affinely flat manifolds", where he conjectures that "every solvable Lie group of dimension $n$ admits a complete affinely flat structure invariant under left translation". This holds for small $n$, but counterexamples are known for $n=11$ by Yves Benoist and for $n=10$ by myself (and Fritz Grunewald for $n=11$).

More precisely, the question involves the following invariant $\mu(L)$ of a given $n$-dimensional Lie algebra $L$ over a field $K$, which is defined as the minimal dimension of a faithful $L$-module. By Ado's theorem, $\mu (L)<\infty$.

Conjecture: Every solvable Lie algebra of dimension $n$ over a field $K$ of characteristic zero satisfies $$ \mu(L)\le n+1. $$ The counterexamples to Milnor's conjecture correspond to nilpotent Lie algebras $L$ of dimension $10$ and $11$, where $\mu(L)\ge n+2$.

$\endgroup$
1
$\begingroup$

Saw this one recently on James Grime channel: it was conjectured that the sum of every even amicable pair is divisible by 9. The first counterexample is Poulet's pair (the 495th pair of amicable numbers) 666030256 and 696630544. The sum of these is 1362660800 = 5 mod 9.

$\endgroup$
1
  • 1
    $\begingroup$ Ops! Guess I pasted the sum from other place $\endgroup$
    – Tadashi
    Sep 7, 2020 at 21:37
0
$\begingroup$

Numerically, one finds that the function $$ f(n) \ := \ \sum_{p \leq n, \\ p \ \text{prime}} \frac{1}{p} \left(1 - \frac{1}{\ln(\ln(p))}\right) $$ appears to take its maximum at $n = 2$. While already from taking a first glance it is clear that this cannot be, and that $f$ is unbounded, I claim that it is numerically challenging to find the smallest $n$ for which we have $f(n) > f(2)$ ... .

$\endgroup$
0
$\begingroup$

The story of Legendre's constant seems to qualify. Based on numerical evidence available at the time and the hardness of computing more digits, it was eminently reasonable to conjecture he was not just renaming "1"in his name.

$\endgroup$
3
  • $\begingroup$ How is this an example of a counterexample? And where is a "large number" involved? $\endgroup$ Jan 27, 2021 at 21:44
  • $\begingroup$ @GerryMyerson a large number of terms of the sequence (more than what was achievable at the time?) are needed to compute the constant to sufficiently high precision to rule the conjecture out. (Of course, it could also be disproven directly without those numerical computations.) $\endgroup$
    – Clement C.
    Jan 27, 2021 at 22:11
  • 1
    $\begingroup$ I don't see how any finite number of primes could be used to refute Legendre's conjectured value. That required advances in theory, not computation. $\endgroup$ Jan 27, 2021 at 22:14
0
$\begingroup$

This answer explores further the problem described this one, where base-10 numbers that become squares when the digits are repeated twofold are identified (e.g. $13223140496\to1322314049613223140496=36363636364^2$).

In any such square concatenation, the number of digits in each "half" of the square is a value of $n$ for which $10^n+1$ has a squared prime factor. For instance, $10^{11}+1$ is divisible by $11^2$, so there are eleven-digit numbers that become square when concatenated twofold, like the one noted above.

We can identify various solutions for $n$ corresponding to a given squared prime factor by the following process.

  1. Select a value of $m$ such that $p|10^m+1$. Such a value of $m$ will be an odd number times half the base-ten repeating decimal period length of $1/p$; the period length itself must be even for the selected $p$ or no solution exists.

  2. Render $10^m=K-1$ where $K=10^m+1$ and raise to the power of $p$, writing the right side of $(K-1)^p$ as a polynomial in $K$ via the Binomial Theorem.

  3. Each term in that binomial- power expansion is constructed to be a multiple of $p^2$ except the $-1$ term at the end, so $10^{mp}+1$ is a certified multiple of $p^2$.

Results for small primes $p$ suggest that if we choose the minimal value of $m$ for a given factor $p$, then $n=mp$ derived in this way is the minimal solution to $p^2|10^n+1$. For instance, $p=11$ pairs with $m=1$ (because $10^1+1$ is $11$ itself), giving $10^{11}+1$ as the smallest augmentedpower of ten divisible by $11^2$. Similarly, $10^8+1$ is the smallest augmented power of ten divisible by $17$, and the solution found by the procedure above, $10^{136}+1$, is the minimal augmented power of ten divisible by $17^2$.

All is as expected until we hit $\color{blue}{p=487}$. The minimal $m$ value is $243$, so we we find from the above lifting procedure that that $487^2|10^{118431}+1$ ... but OEIS sequence A086981 reports that instead $487^2|10^{243}+1$ as the minimal solution for that factor -- that is, $10^m+1$ instead of $10^{mp}+1$. The minimal solution for that squared prime factor slips in before using the binomial power expansion, not after as is usually the case.

Such a counterexample is connected with the fact that any residue $r\bmod p$, maps into $p$ residues $\bmod p^2$. One of these mapped residues is $\equiv r^p$, and this one is a $p$-power residue $\bmod p^2$. The other residues $\bmod p^2$ are not $p$-power residues.

For instance, with $p=7$ we render

$10^7\equiv3^7=2187\equiv31\bmod 49,$

so $31$ is a seventh-power residue $\bmod 49$ and other residues congruent to it $\bmod 7$, including $10$, are not seventh-power residues.

With other prime factors that allow a solution to $p|10^m+1$ (and thus also $p^2|10^n+1$), we get the following from residue $10\bmod p$:

$p=11\to10^{11}\equiv120\bmod11^2$

$p=13\to10^{13}\equiv23\bmod13^2$

$p=17\to10^{17}\equiv214\bmod17^2$

...

$p=463\to10^{463}\equiv12974\bmod463^2$

$\color{blue}{p=487\to10^{487}\equiv10\bmod487^2}$

So unlike all smaller primes in scope, $p=487$ renders $10$ a $p$-power residue $\bmod p^2$, causing an extra factor of $p$ to appear in $10^m+1$ for appropriates value of $m$. Hence for this particular case, we did not have to multiply the initial exponent $m=243$ by $487$ to get an augmented power of ten divisible by $487^2$. If we do choose to multiply the exponent, we find that $10^{118341}+1$ is divisible by $487^3$.

The documentation of OEIS A086981 reports no other counterexamples below $1000$. Larger counterexamples are expected to become rare because the $p$-power residue condition becomes less probable for larger primes $p$.

$\endgroup$
-4
$\begingroup$

the Weaire–Phelan structure was found to be

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

$\endgroup$
3
  • $\begingroup$ This is not a counterexample, eventual or otherwise, in the sense of this question, is it? $\endgroup$ May 1, 2011 at 23:46
  • $\begingroup$ @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." $\endgroup$
    – pageman
    May 2, 2011 at 10:04
  • 7
    $\begingroup$ "Eventual", in the sense of this question, does not refer to time, but to number. $\endgroup$ May 2, 2011 at 12:48
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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