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

163
$\begingroup$

It was once conjectured that factors of $x^n-1$ over the rationals had no coefficient exceeding 1 in absolute value. The first counterexample comes at $n=105$.

$\endgroup$
9
  • 65
    $\begingroup$ And in fact these coefficients (eventually!!) grow exponentially fast. See wayback.cecm.sfu.ca/~ada26/cyclotomic for a nice compendium of cyclotomic polynomials with enormous coefficients. $\endgroup$ Feb 17, 2010 at 3:53
  • 3
    $\begingroup$ I often heard this, but I've never seen a citation. Who conjectured that? $\endgroup$ Jun 9, 2010 at 2:13
  • 7
    $\begingroup$ @Kevin, I don't know. I thought I once came across a reference to someone who computed up to $n=100$ in the year 1940 or so, stopped there and made the conjecture, but I haven't had any luck tracking it down. Noticing the breakdown at 105 is attributed to Migotti, 1883, and a proof that the coefficients can be arbitrarily large is due to Schur, published by Emma Lehmer in 1936, so if I'm right about the computations in 1940 then they were done by someone who was out of the loop and perhaps it's best not to embarrass any descendants by dredging up the reference. $\endgroup$ Jun 9, 2010 at 3:32
  • 2
    $\begingroup$ @Gerry: I know where I read it (annual collection "In the world of mathematics", vol 12 or 13, published in Kiev ca 1984, in Ukrainian). The article went on talking about Euler's pentagonal theorem and the recurrence for $\sigma(n)$, so I am stuck with the impression that Euler also conjectured the cyclotomic fact. $\endgroup$ Jun 12, 2010 at 22:58
  • 49
    $\begingroup$ This "conjecture", as well as the first counterexample, are due to the following fcat (Theorem): if $m$ has not more than two odd prime factors, then the cyclotomic polynomial $\phi_m$ has coefficients in $\{-1,0,1\}$. The first $m$ with three odd prime factors is $105$. $\endgroup$ Mar 31, 2016 at 7:54
167
$\begingroup$

The least positive integer for which the equality $$ \left\lceil \frac{2}{2^{1/n}-1}\right\rceil = \left\lfloor \frac{2n}{\log 2} \right\rfloor $$ fails is $n=777,\!451,\!915,\!729,\!368$. See https://oeis.org/A129935.

Another example that I like is the number $f(n)$ of inequivalent differentiable structures on $\mathbb{R}^n$. We have $f(n)=1$ if $n\neq 4$, while $f(4)=c$, the cardinality of the continuum.

$\endgroup$
84
$\begingroup$

The essence of the phenomenon of eventual counterexamples is that a certain pattern that holds among small numbers, turns out not to be universal. In the very best examples, such as the examples provided in the other answers, which I have enjoyed very much, what we have is an easily described property $P(n)$, whose first failing instance is very large in comparison. Indeed, the quality of answer might be measured by the difference between the size of the description of the property and the size of the first failing instance of it. When an easily described property holds for a very long time and then suddenly fails at some very large number, we are surprised. Therefore, to my mind the phenomenon of eventual counterexamples is intimately wrapped up with the possibility of providing very short descriptions of enormous numbers.

Surely we are all able easily to provide short descriptions of some very large numbers, such as $2^{100}$ or $2^{2^{100!}}$. In order to go beyond exponentiation and factorials, we might make use of other easily described functions exhibiting even more enormous growth. The Ackermann function, for example, defined by a simple one-line recursion, has diagonal values 1, 3, 7, 61, $2^{2^{2^{65536}}}$, with the next value $A(5)$ mind-bogglingly huge.

All such examples, short descriptions of large numbers, can be systematically transformed into instances of eventual counterexamples. For if $d$ is a short description of an enormous number $N$, then the property $P(k)=$"$k$ does not exhibit $d$" is easily described and holds for all values $k$ below $N$, but not of $N$ itself. Thus, it does very well by the quality measure I mentioned above.

So to my mind, the real issue is: what are the largest numbers that you can describe by a very short description?

This question can be made precise by requiring the description to be expressible in a particular formal language. Once the language is rich enough, however, this problem will certainly wade into interesting foundational waters, for the question of whether a given description actually succeeds in describing a number---for example, "the length of the shortest proof of a contradiction in ZFC"---may be independent of our basic axioms, even if it is enormous.

$\endgroup$
8
  • 9
    $\begingroup$ This is a great perspective $\endgroup$
    – Q.Q.J.
    Jun 15, 2010 at 14:32
  • 7
    $\begingroup$ Yes, but it seems that one has to take into account also the difficulty of generating the underlying sequence. For example, the polynomial x^2−x+41 gives primes up to x=40, and 40 is not a big number by "absolute" measure, it is big compared to say other polynomials in generating primes. $\endgroup$
    – timur
    Oct 10, 2010 at 3:15
  • 26
    $\begingroup$ 2^2^2^65536 isn't `mind-bogglingly huge'?! $\endgroup$ May 20, 2011 at 9:26
  • 7
    $\begingroup$ Another relevant blog post: scottaaronson.com/writings/bignumbers.html $\endgroup$
    – Ramsay
    Feb 25, 2012 at 14:19
  • 1
    $\begingroup$ And my blog post on a "largest number contest" I recently conducted: jdh.hamkins.org/largest-number-contest $\endgroup$ Jun 20, 2013 at 21:38
70
$\begingroup$

Strong Law of Small Numbers by Guy.

Steve

$\endgroup$
7
  • 21
    $\begingroup$ Item 13: D.H. & Emma Lehmer discovered that $2^n\equiv 3 (\mod n)$ for $n=4700063497,$ but for no smaller $n>1.$ $\endgroup$ Jun 13, 2010 at 1:15
  • 1
    $\begingroup$ There is a part 2 of Guy's paper, Richard K Guy, The second strong law of small numbers, Math Mag 63 (1990) 3-20, MR 91a:11001 (and also by the same author, Graphs and the strong law of small numbers, in Graph Theory, Combinatorics, and Applications, Vol 2, Wiley, 1991, pages 597-614). $\endgroup$ Jun 17, 2010 at 6:14
  • 4
    $\begingroup$ Do you mean $n > 2$? Last I checked we have $2^2 \equiv 3 \pmod{2}$. $\endgroup$ Jul 29, 2010 at 20:28
  • 39
    $\begingroup$ @David Mandell Freeman: Huh? Isn't the left side even and the right side odd? $\endgroup$ Jul 3, 2011 at 20:36
  • 4
    $\begingroup$ Here's a working link: maa.org/sites/default/files/pdf/upload_library/22/Ford/… $\endgroup$ Aug 30, 2015 at 3:08
64
$\begingroup$

In reference to the Prime Number Theorem (then Conjecture) both Gauss and Riemann further conjectured that $\pi(n) < \operatorname{Li}(n)$ (where $\pi(n)$ is the number of primes from $1$ to $n$ and $\operatorname{Li}(n)$ is the logarithmic integral, $\int_2^n \frac{1}{\ln(t)} \, dt$).

Although it has been proven that this does not hold (Littlewood), that there exists some $n$ such that $\pi(n) \geq \operatorname{Li}(n)$, the first $n$ where this takes place is so huge no-one has worked it out yet (allegedly). The number is known as Skewes' Number. It is known to be between $10^{14}$ and $1.39822\times 10^{316}$, and strongly believed to be about $1.397162914\times 10^{316}$. (References at the foregoing link.)

$\endgroup$
3
  • 2
    $\begingroup$ Is Skewes' number the first $n$ where it happens, or is it the (much larger) bound Skewes found for the first such $n$? $\endgroup$ Oct 11, 2010 at 5:59
  • $\begingroup$ It is the first $n$ where it happens. There are actually two `Skewes' Number's, each assuming whether the Riemann Hypothesis is true or false respectively. See the link to mathworld in the post. $\endgroup$
    – ADL
    Oct 12, 2010 at 16:08
  • $\begingroup$ Remember reading in a book by Ogilvy (Excursions in Number Theory) following theorem of Littlewood : the function $\pi(n)-$Li$(n)$ changes sign infinitely often (I read it in my undergraduate days, and never seen that book again) $\endgroup$ Jan 1 at 0:25
60
$\begingroup$

I'm trying to reconstruct an example I saw somewhere some years back. It goes something like this: $\gcd(n^5-5,(n+1)^5-5)=1$ is true for $n=1,2,\dots,1435389$ but fails for $n=1435390$ (when the gcd is 1968751).

$\endgroup$
5
  • 14
    $\begingroup$ I found a place which has this example, and it has many more examples: math.niu.edu/~rusin/known-math/96/smallnums $\endgroup$ Feb 17, 2010 at 1:16
  • $\begingroup$ Pretty impressive! Specifically, gcd(n^17+9, (n+1)^17+9)=1 for all n up to some crazy explicit number, the number of digits of which I couldn't even count. This begs the question, is there a reasonably simple proof that this gcd isn't always 1? $\endgroup$
    – Alon Amit
    Feb 17, 2010 at 1:26
  • 5
    $\begingroup$ The resultant of $x^{17}+9$ and $(x+1)^{17}+9$ is some (large) integer, D. So there are polynomials $a(x)$ and $b(x)$ with integer coefficients and degree at most 16 such that $a(x)(x^{17)+9)-b(x)((x+1)^{17}+9)=D$. Now reduce modulo a prime p dividing D to get the equation $a(x)(x^{17)+9)=b(x)((x+1)^{17}+9)$ in Z_p[x]. Now $x^{17}+9$ has 17 distinct zeros in Z_p, and they can't all be zeros of a(x), so at least one of them is a zero of $(x+1)^{17}+9$, and you're done. $\endgroup$ Feb 17, 2010 at 2:23
  • 5
    $\begingroup$ I don't understand why sometimes I get to see a math preview and sometimes not. I didn't see one when I made the comment above and it appears that I left out some closing braces, so some formulas are missing. I don't know how to edit my comment to put those braces in, but it doesn't matter, since my argument was more complicated than necessary anyway. If the resultant of two polynomials is divisible by some prime p, then the two polynomials have a common factor over the integers modulo p. These polynomials either split completely or are irreducible, so they must have a common linear factor. $\endgroup$ Feb 17, 2010 at 5:17
  • 4
    $\begingroup$ Since the link in Gerry Myerson's comment is dead now, I will add the link to version in the Internet Archive. $\endgroup$ May 29, 2016 at 7:06
55
$\begingroup$

Freeman Dyson observed in my presence that the sequence with initial condition $a_0=3,a_1=0,a_2=2$, and recurrence $a_{n+3}=a_{n+1}+a_{n}$ almost has the property that $n\mid a_n$ if and only if $n$ is prime or 1, except that it doesn't.

He challenged us (grad students) to explain this ``near-phenomenon'', as it seems too close to being too good to be true to be coincidence. I've never seen an explanation.

Since this is Math Overflow, I'll give the spoiler, the first counterexample is $n=521^2=271441$.

$\endgroup$
7
  • 19
    $\begingroup$ a_n is the sum of the nth powers of the roots of x^3 = x + 1, so the divisibility follows from the fact that the Frobenius map permutes the roots of a polynomial. Are you asking for an explanation of the failure of the converse? I see no reason to expect the converse to be true. $\endgroup$ Jun 9, 2010 at 2:44
  • 9
    $\begingroup$ I guess if anything needs an explanation it's why does it take so long for a counterexample to turn up. These numbers are (I think) the "Perrin pseudoprimes," see research.att.com/~njas/sequences/A013998 $\endgroup$ Jun 9, 2010 at 3:40
  • 1
    $\begingroup$ Suppose for example that n = pq for p, q distinct primes and let a, b, c be the roots of x^3 = x + 1. In order for a^n + b^n + c^n to be divisible by n we require that a^q + b^q + c^q be divisible by p and a^p + b^p + c^p be divisible by q. This is just highly unlikely; one might expect that a^p, b^p, c^p and a^q, b^q, c^q are just the roots of some random irreducible cubic polynomial mod q and mod p, respectively. Replacing x^3 = x + 1 by an irreducible polynomial of higher degree might conceivably lead to even larger pseudoprimes. $\endgroup$ Jun 9, 2010 at 3:56
  • 6
    $\begingroup$ Here is a related perspective. a_n counts the number of closed walks of length n on a certain graph G on 3 vertices; the cyclic group Z/nZ acts on these walks in the obvious way and the residue of a_n mod n is the number of walks lying in an orbit which is not of full size. When n is prime, orbits can either have size p or size 1 and the latter can't occur if there are no loops in G, which there aren't. When n is composite, the situation is much more complicated and it would be very surprising if the number of walks in non-full orbits was still divisible by n. $\endgroup$ Jun 9, 2010 at 4:02
  • 22
    $\begingroup$ I think the spirit of the observation was akin to observing that $e^{\pi \sqrt{163}}$ is an integer, except that it isn't.'' Or that the image of $0,1,\dots$, under $x\mapsto x^2-x+41$ is always prime, except that it isn't.'' Now, nobody would expect these criteria hold, but it is shocking that such simple expressions can come so close. And ultimately, there is deeper meaning to the observations. In the current phenomenon, no informed number theorist would suspect that the sequence detects primes perfectly, but it is shocking (to me, at least) that so simple a sequence comes so close. $\endgroup$ Jun 9, 2010 at 15:52
48
$\begingroup$

A famous example is the isomorphism problem for integral group rings: suppose $G$ and $H$ are two finite groups of order $n$ such that $\mathbb{Z}G \cong \mathbb{Z}H$ does it mean that $G \cong H$? It was proved to be true for many cases and for many $n$'s and I think it was believed to be true in all cases. Nonetheless, eventually a counter example was found, see Hertweck, Martin. A Counterexample to the Isomorphism Problem for Integral Group Rings. Annals of Mathematics, vol. 154, no. 1, 2001, pp. 115–138. https://www.jstor.org/stable/3062112.

$\endgroup$
1
40
$\begingroup$

The numbers 12, 121, 1211, 12111, 121111, etc., are all composite - until you get to the one with 138 digits, that's a prime. Saw this in a talk Lenny Jones gave at the New Orleans meeting earlier this month.

$\endgroup$
3
  • 32
    $\begingroup$ If you take a random sequence that grows like 12*10^n, the prime number theorem says you have something like a 13% chance of making it to 137 digits without seeing a prime. So, even if you've seen that the first 137 numbers of the form 12111...11 are composite, is the conjecture that all such numbers are composite really a reasonable one to make? $\endgroup$
    – Vectornaut
    Apr 21, 2011 at 2:26
  • 21
    $\begingroup$ @Vectornaut, while I think your point is valid, it needs to be adjusted slightly, because the sequence is far from random. For example, in a pattern like that you won't get any primes unless the final digits are odd, and that increases the chance that any individual term is prime, which in turn decreases by quite a bit the chance that 137 terms are composite. $\endgroup$
    – gowers
    Apr 21, 2011 at 11:10
  • 18
    $\begingroup$ 40, 403, 4033, 40333, ... are all composite until you reach 483 3's; the first prime of 45, 451, 4511, 45111, ... has 772 1's. $\endgroup$ Jan 15, 2020 at 21:46
34
$\begingroup$

Any finite loop space has the rational cohomology of a Lie group -- up to rank 65. From then on, there are counterexamples in every dimension. The smallest known dimension of a counterexampe is 1250, but whatever the actual smallest dimension is, counterexamples will occur in every dimension after that.

$\endgroup$
1
  • 15
    $\begingroup$ And, for the record, a finite loop space is a finite CW-complex $X$ that is homotopy equivalent to $\Omega Y$ for some space $Y$. $\endgroup$ May 1, 2011 at 21:53
34
$\begingroup$

The Borwein Integrals are integrals of products of the sinc function. They exhibit certain "apparent patterns" which, while eventually breaking down, are actually indicative of something larger at work. (The example given on the Wikipedia page is a good one.)

$\endgroup$
1
29
$\begingroup$

In answering another MathOverflow question on Graham's number, I quoted from Harvey Friedman's Enormous Numbers in Real Life. Perhaps eventual counterexamples bear some relation to proof strength in certain systems of logic? Anyway, that example there could be rephrased to fit the current question.

Suppose I look at strings on three symbols, and given a word w of length n I look at subwords of the form (forgive the AWK notation) spc[i] = substr(w,i,i+1), i.e. those substrings starting at the $i$th character going for length $i+1$ characters. So spc[1] gets the first two characters of $w$, spc[2] == w[2]w[3]w[4], and so on.

I manage to find, for every $n$ that I can compute, a string $w_n$ that I use for $w$ above such that for $0 < i < j \leq \frac{n}{2}$, spc[i] is not a subsequence of spc[j]. Others find such examples for even larger values of $n$. It would be reasonable for me to believe I could find arbitrarily long strings with this property.

Enter Harvey Friedman:

"Theorem 8.1. Let $k \geq 1$. There is a longest finite sequence $x_1, \dots ,x_n$ from $\{ 1, \dots ,k \}$ such that for no $i < j \leq \frac{n}{2}$ is $x_i, \dots ,x_{2i}$ a subsequence of $x_j , \dots ,x_{2j}$.

For $k \geq 1$, let $n(k)$ be the length of this longest finite sequence.

Paul Sally runs a program for gifted high school students at the University of Chicago.

He asked them to find $n(1), n(2), n(3)$. They all got $n(1) = 3$. One got $n(2) = 11$. Nobody reported much on $n(3)$. I then started to ask several mathematicians to give an estimate on $n(3)$, some of them very famous. I got guesses like this: $60, 100, 150, 200, 300$.

They were not in combinatorics. Recently I asked Lovasz, telling him about these five guesses. He guessed $20000$.

Theorem 8.2. $n(3) > A(7,184)$.

Lovasz wins, as his guess is closer to $A(7,184)$ than the other guesses.

Recall the discussion about $A(5,5)$ being incomprehensibly large. With the help of computer investigations (with R. Dougherty), I got:

Theorem 8.3. $n(3) > A(7198, 158386)$.

A good upper bound for $n(3)$ is work in progress. Crude result: $A(n,n)$, where $n = A(5,5).$"

Here $A(n,n)$ is defined earlier in Friedman's paper as an Ackermann-like sequence.

I suspect $n(3)$ squishes Graham's number quite unlike a galactic black hole absorbing a prion or even a quark.

EDIT: I have been corrected; in the squishing hierarchy, $n(4)$ squishes Graham's number, which squishes $n(3)$. Again, unlike any physical realization I can imagine. END EDIT

The moral here is: "Don't jump to conclusions without a sufficiently strong proof system as back up".

Gerhard "Ask Me About System Design" Paseman, 2010.02.17

$\endgroup$
3
  • $\begingroup$ I'm not familiar with the notation $A(m,n)$. Is it the entry of a particular adjacency matrix or something? $\endgroup$
    – Q.Q.J.
    Feb 17, 2010 at 21:29
  • $\begingroup$ Sorry. Above I mentioned A(n,n) after the quotation as being an Ackermann like sequence. You should check the paper for his particular definition of A(n,m), but it involves iterated composition. The "kicker" part of the definition is A(n+1,m+1) = A(n, A(n+1,m)), or something like that. A(4,n) is something like 2 tetrated n times, so A(4,5) is already 2^65536. You can check out the MathOverflow question on Graham's number for more info. $\endgroup$ Feb 17, 2010 at 21:53
  • 1
    $\begingroup$ In the above mentioned post on Graham's number, it was pointed out that Graham's number is bigger than n(3) but smaller than n(4). I apologize for getting the index wrong. $\endgroup$ Feb 21, 2010 at 1:42
27
$\begingroup$

The Mertens conjecture.

$\endgroup$
2
  • 2
    $\begingroup$ And related, a counterexample to the Riemann hypothesis, if it exists, should be a prime example. $\endgroup$ Feb 16, 2010 at 15:10
  • 4
    $\begingroup$ I think that Littlewood's result on the difference between the number of primes <x and li(x) was a surprise to many. $\endgroup$ Jun 9, 2010 at 2:41
24
$\begingroup$

Let $a_1=1$, $a_{n+1}=(1+a_1^2+a_2^2+\dots+a_n^2)/n$. Are all terms integer? No, the first non-integer is $a_{44}$. I do not know neither reference (my source is private communication by Dmitry Rostovsky, and he does not remember where is it from), nor deep reason (if they exist) why first 43 terms are integer.

$\endgroup$
2
  • 3
    $\begingroup$ This is discussed in E15 of Guy, Unsolved Problems In Number Theory. He says F Gobel found the recursion yielded many integers, but Hendrik Lenstra found that first counterexample. Guy gives generalizations and many references. $\endgroup$ Oct 11, 2010 at 3:11
  • 3
    $\begingroup$ Following up some of those references, I found a claim that $a_1=11$, $a_{n+1}=a_n(a_n^2+n)/(n+1)$ gives integers up to (but not beyond) $n=600$ or so. $\endgroup$ Oct 11, 2010 at 5:57
22
$\begingroup$

Smallest counterexample to "There is no positive integer $n$ such that the concatenation of (the decimal representation of) $n$ with itself is a square" is $n=13223140496$, according to https://oeis.org/A102567; $1322314049613223140496 = 36363636364^2$.

$\endgroup$
5
  • 8
    $\begingroup$ Are all those 3s and 6s on the RHS an accident? $\endgroup$ Jul 29, 2010 at 20:33
  • 5
    $\begingroup$ Yes - and no. If you look at research.att.com/~njas/sequences/A106497 which is the sequence of right sides, they are all highly patterned numbers, related to the decimal expansions of $a/11$ and $a/7$ for various $a$. Whether they must be of this form, I do not know. $\endgroup$ Jul 29, 2010 at 23:24
  • 3
    $\begingroup$ @DavidMandellFreeman If $(10^n+1) m$ is square for $m<10^n$, then $10^n+1$ must have a square divisor, say $10^n+1 = s^2 t$ and $m = r^2 t$. Then $\sqrt{(10^n+1)m} = rst \approx 10^n (r/s)$. So the RHS will look very close to a decimal expansion of $r/s$. The first non-squarefree numbers of the form $10^n+1$ are $11^2 | 10^{11}+1$ and $7^2 | 10^{21}+1$. If you search further, I'm sure other denominators occur. $\endgroup$ Mar 12, 2015 at 14:56
  • 1
    $\begingroup$ For example,$13^2|10^{39}+1$ and $384615384615384615384615384615384615385^2 = (147928994082840236686390532544378698225)*(10^{39}+1)$, reflecting that $5/13 = 0.384615\cdots$. $\endgroup$ Mar 12, 2015 at 16:56
  • 1
    $\begingroup$ Secondary eventual counterexample: the solutions all seem to have an odd number of digits in each "half" of the square number. An even number of digits in each half would be at least 136 digits! $\endgroup$ Oct 19, 2022 at 13:00
21
$\begingroup$

Here's another one, maybe mostly of historical interest. Fermat once conjectured that all numbers of the form $$ p=2^{2^n}+1 $$ are prime, which he had the means to verify up to $n=4$. It took more than 100 years until Euler showed that this fails at $n=5$. Today we still don't know if there are any other Fermat primes, so quite possibly Fermat's conjecture fails in the worst possible way.

$\endgroup$
20
$\begingroup$

Recently I saw that in any $2,3,4,5,\ldots$ consecutive integers, one of them is comprime to the rest, then I conjectured that it should be trivially true for any $k$ consecutive integers, but I didn't able to prove this and I asked this question in MSE, and I surprised by Noah Schweber answer! It's true only for $1,2,\ldots,16$ and the first counterexample is the sequence of length $17$ beginning with $2184$.
There are infinitely many counterexamples for $17\leq k $.
https://oeis.org/A090318/internal

$\endgroup$
6
  • $\begingroup$ There are infinitely many counterexamples for any $k\ge 17$. $\endgroup$
    – user236182
    Mar 30, 2016 at 17:08
  • $\begingroup$ In the MSE link you gave the answer by Noah Schweber claimed that Brauer proved it. In this another answer he links to the Brauer's paper with a proof. $\endgroup$
    – user236182
    Mar 30, 2016 at 17:41
  • 3
    $\begingroup$ If there is one counterexample $x+1, \ldots, x+k$, there are infinitely many: just add any common multiple of $x+1, \ldots, x+k$. $\endgroup$ Mar 30, 2016 at 19:31
  • 4
    $\begingroup$ This is closely related to the Erdos-Woods numbers, see en.wikipedia.org/wiki/Erdős–Woods_number $\endgroup$ Mar 30, 2016 at 22:38
  • 2
    $\begingroup$ @GerryMyerson's link, clickably: Erdös–Woods number. $\endgroup$
    – LSpice
    May 28, 2019 at 19:51
20
$\begingroup$

Shapiro inequality: Let $x_1,x_2,\dots, x_n,x_{n+1},x_{n+2}$ be positive real numbers with $x_{n+1}=x_1$ and $x_{n+2}=x_2$. Now the inequality $\sum_{i=1}^{n} \dfrac{x_i}{x_{i+1}+x_{i+2}} \geq \dfrac{n}{2}$ must be true if $n<14$ or if $n\leq 23$ and $n$ is odd. So $n=14$ is the first $n$ where a counterexample can be found. I know that 14 is not that large a number, but remember that for each $n$ we have a problem with a lot of freedom.

$\endgroup$
18
$\begingroup$

This is a bit tongue-in-cheek, but what about Special Relativity? In this case let property $P(x), x\in \mathbb{R}$ be the property that a given velocity $x$ is attainable. After all, Galilean Transforms allow one to change to a frame moving at an arbitrary velocity. Only Einstein's interpretation of the discoveries of Lorenz and Poincaré allowed for us to realize that property $P$ is only true if $x \in [-3 \times 10^8, 3 \times 10^8]$

$\endgroup$
17
$\begingroup$

One of my favourite examples in this context is the following: Define a sequence $(s_n)$ by $s_1=8$, $s_2=55$ and for $n\geq3$ $s_n$ the smallest integer such that $s_n/s_{n-1}>s_{n-1}/s_{n-2}$ so that $s_3=379$ as $379/55>55/8$. Then we have $s_n=6s_{n-1}+7s_{n-2}-5s_{n-3}-6s_{n-4}$ for $5\leq n\leq11056$ but not for $n=11057$ (I have lost track of the name of the person to whom this is due, but it is, nowadays, easily verified on a computer).

$\endgroup$
4
  • 4
    $\begingroup$ This may have come out of David Boyd's research on PV and Salem numbers. $\endgroup$ Jun 12, 2010 at 23:53
  • $\begingroup$ Thank you, Gerry! I was struggling to remember the name of the object it reminded me of: Pisot sequence, $a_{n+1}=N(a_n^2/a_{n-1}),$ where $N$ is the nearest integer function (round down if the fractional part is exactly 1/2). Boyd showed that many Pisot sequences aren't linearly recurrent. $\endgroup$ Jun 13, 2010 at 2:06
  • 4
    $\begingroup$ I found the source; David W Boyd, Linear recurrence relations for some generalized Pisot sequences, Advances In Number Theory 333-340, Oxford University Press, 1993, MR 96i:11017. Boyd had several earlier papers on Pisot sequences, and this example may also be given in one of the earlier papers. $\endgroup$ Jun 15, 2010 at 3:51
  • 8
    $\begingroup$ Umm, not a big deal or anything, but I was the one who found this example, and told David Boyd about it, back in 1990. $\endgroup$ Apr 9, 2016 at 11:34
15
$\begingroup$

How about this paper?

$\endgroup$
15
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ You can really throw people off by showing it to them as $1, 2, 4, 8, 16, \ldots, 256, \ldots$ - they don't realize that the 256 isn't in the right place for the sequence to be powers of two. $\endgroup$ Oct 19, 2022 at 15:20
14
$\begingroup$

I'm surprised no one has mentioned Graeco-Latin Squares https://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.

$\endgroup$
13
$\begingroup$

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 \dfrac{2^{k+1}-1}{k+1}$ is equal to the numerator of $\sum_{k=0}^n \dfrac{\binom{n}{k}}{(k+1)^2}$. This fails first at $n=59$ and then at $n=1519, 7814, \ldots$. See A134652.

$\endgroup$
13
$\begingroup$

The first counterexample to the second Hardy-Littlewood conjecture is expected to occur somewhere between $10^{174}$ and $10^{1199}$ (at least, according to the references from the Wikipedia page), though it has not yet been definitively established that such a counterexample exists.

$\endgroup$
2
  • $\begingroup$ Some problem with Wikipedia link :( $\endgroup$ Mar 30, 2012 at 6:16
  • 1
    $\begingroup$ I fixed the link (hopefully...) $\endgroup$ Mar 30, 2012 at 6:48
13
$\begingroup$

I'm late to the party, but here's one from algebraic number theory.

The ring of integers of $\mathbb Q(\sqrt[n]2)$ is exactly $\mathbb Z[\sqrt[n]2]$ for $2\leq n \leq 1092$. At $n =1093$, the ring of integers is bigger. One can show that $\displaystyle\frac{(\sqrt[1093]{2}-2)^{1092}}{1093}$ is an algebraic integer, but is not in $\mathbb Z[\sqrt[1093]2]$.

Keith Conrad has a nice paper on this: https://kconrad.math.uconn.edu/blurbs/gradnumthy/integersradical.pdf

$\endgroup$
1
  • 1
    $\begingroup$ This is correlated with the fact that for $p=1093$, the number $2$ is a $p$- power residue $\bmod p^2$. Thereby, the claimed fraction can be given a defined integer residue $\bmod 1093$, surmounting an obstacle that stops analogous expressions for smaller primes. $\endgroup$ Dec 3, 2022 at 12:51
12
$\begingroup$

D. H. Lehmer showed that the first prime value of the Ramanujan tau-function, defined by $$\sum_{n=1}^\infty \tau(n) q^n = q \prod_{n=1}^\infty (1-q^n)^{24} = q - 24q^2 + 252q^3 - 1472q^4 + \dots,$$ occurs at the 63001st term. This is slightly less surprising when one knows that prime values can only occur for odd square inputs.

$\endgroup$
2
  • 4
    $\begingroup$ When does the first zero value occur? :P $\endgroup$ Jun 12, 2010 at 22:50
  • 1
    $\begingroup$ As far as I know, the non-vanishing question is still open. I haven't heard of any lower bounds that are better than Lehmer's $10^{15}$. $\endgroup$
    – S. Carnahan
    Jun 13, 2010 at 2:47
12
$\begingroup$

I had a conjecture that for any two natural numbers with the same least prime factor, there must be at least one number in between them with a higher least prime factor. It seemed very robust for reasonably-sized numbers and empirical trends suggested it would hold for arbitrarily large numbers as well.

Months later, I found a paper giving some freshly computed large terms for the Jacobsthal primorial function $h(n)$, and using those, ferreted out a counterexample starting at $$724968762211953720363081773921156853174119094876349.$$

I think this may be the smallest counterexample; even if not, you can show that if there is one smaller, it can't be by much. Until I found this, I would have said I was certain my conjecture was correct. Lesson learned!

$\endgroup$
2
  • 2
    $\begingroup$ Very neat example! I believe the interval $7310131732015251470110369$ to $7310131732015251470110511$ should be a smaller counterexample. The endpoints both have least prime factor $71$, and each number in between is divisible by something less than $71$. The prime $71$ is the smallest one which can be the least prime factor of the endpoints, but this is probably not the best example using it. I also cannot rule out the possibility of using a slightly larger prime like $73$ instead. $\endgroup$ Jan 1 at 5:32
  • $\begingroup$ @MatthewBolan Wow, well done! I guess I stand corrected. It would be nice if you have the time to write that up as an answer on my relevant post, ideally explaining something about how you found it. I know I'm curious. $\endgroup$
    – Trev
    Jan 1 at 9:29
11
$\begingroup$

The Pólya conjecture.

$\endgroup$
11
$\begingroup$

In this thread search down for the answer by sigfpe .

$\endgroup$
1

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.