627
$\begingroup$

Often, when I try to describe mathematics to the layman, I find myself struggling to convince them of the importance and consequence of "proof". I receive responses like: "surely if Collatz is true up to $20×2^{58}$, then it must always be true?"; and "the sequence of number of edges on a complete graph starts $0,1,3,6,10$, so the next term must be 15 etc."

Granted, this second statement is less logically unsound than the first since it's not difficult to see the reason why the sequence must continue as such; nevertheless, the statement was made on a premise that boils down to "interesting patterns must always continue".

I try to counter this logic by creating a ridiculous argument like "the numbers $1,2,3,4,5$ are less than $100$, so surely all numbers are", but this usually fails to be convincing.

So, are there any examples of non-trivial patterns that appear to be true for a large number of small cases, but then fail for some larger case? A good answer to this question should:

  1. be one which could be explained to the layman without having to subject them to a 24 lecture course of background material, and
  2. have as a minimal counterexample a case which cannot (feasibly) be checked without the use of a computer.

I believe conditions 1. and 2. make my question specific enough to have in some sense a "right" (or at least a "not wrong") answer; but I'd be happy to clarify if this is not the case. I suppose I'm expecting an answer to come from number theory, but can see that areas like graph theory, combinatorics more generally and set theory could potentially offer suitable answers.

$\endgroup$
18
  • 164
    $\begingroup$ The sentence: ""the numbers 1,2,3,4,5 are less than 100, so surely all numbers are" - Is interesting. $\endgroup$
    – NoChance
    Commented Feb 20, 2012 at 22:01
  • 11
    $\begingroup$ @yasmar, I was thinking of this: mathoverflow.net/questions/15444/… $\endgroup$ Commented Feb 20, 2012 at 22:26
  • 37
    $\begingroup$ This doesn't satisfy b), but how about "$n^2-n+41$ is always prime"? (it's true for $1\le n\le 40$). $\endgroup$ Commented Feb 20, 2012 at 22:39
  • 26
    $\begingroup$ @EmmadKareem After reading halfway through this page, this looks like a challenge to see who can give the most mind blowing example of this simplified version: "N not equals 82174583229565384923 for N = 1,2,3,4... breaks down at N = 82174583229565384923" $\endgroup$
    – Jake
    Commented Feb 22, 2012 at 13:27
  • 63
    $\begingroup$ $e = 2.7 \, 1828 \, 1828 \quad $ :O $ \quad 459045235 \,$ :( $\endgroup$
    – Lenar Hoyt
    Commented Jul 14, 2013 at 22:48

45 Answers 45

423
$\begingroup$

I'll translate an entry in the blog Gaussianos ("Gaussians") about Polya's conjecture, titled:

A BELIEF IS NOT A PROOF.

We'll say a number is of even kind if in its prime factorization, an even number of primes appear. For example $6 = 2\cdot 3$ is a number of even kind. And we'll say a number is of odd kind if the number of primes in its factorization is odd. For example, $18 = 2·3·3$ is of odd kind. ($1$ is considered of even kind).

Let $n$ be any natural number. We'll consider the following numbers:

  1. $E(n) =$ number of positive integers less or equal to $n$ that are of even kind.
  2. $O(n) =$ number of positive integers less or equal to $n$ that are of odd kind.

Let's consider $n=7$. In this case $O(7) = 4$ (number 2, 3, 5 and 7 itself) and $E(7) = 3$ ( 1, 4 and 6). So $O(7) >E(7)$.

For $n = 6$: $O(6) = 3$ and $E(6) = 3$. Thus $O(6) = E(6)$.

In 1919 George Polya proposed the following result, know as Polya's Conjecture:

For all $n > 2$, $O(n)$ is greater than or equal to $E(n)$.

Polya had checked this for $n < 1500$. In the following years this was tested up to $n=1000000$, which is a reason why the conjecture might be thought to be true. But that is wrong.

In 1962, Lehman found an explicit counterexample: for $n = 906180359$, we have $O(n) = E(n) – 1$, so:

$$O(906180359) < E(906180359).$$

By an exhaustive search, the smallest counterexample is $n = 906150257$, found by Tanaka in 1980.

Thus Polya's Conjecture is false.

What do we learn from this? Well, it is simple: unfortunately in mathematics we cannot trust intuition or what happens for a finite number of cases, no matter how large the number is. Until the result is proved for the general case, we have no certainty that it is true.

$\endgroup$
17
  • 287
    $\begingroup$ No matter how smart I feel like I'm getting, when I want to be humbled, I simply type math.stackexchange.com into my URL bar. $\endgroup$
    – orokusaki
    Commented Feb 21, 2012 at 1:23
  • 14
    $\begingroup$ Note that “y por tanto” is Spanish for “and therefore”. $\endgroup$
    – tchrist
    Commented Feb 21, 2012 at 1:28
  • 53
    $\begingroup$ In 1942, Ingham showed that Polya's conjecture implies the Riemann hypothesis and that the positive imaginary parts of the nontrivial zeros of the Riemann zeta-function are linearly dependent over $\mathbf Q$. The second conclusion is very suspicious, so in principle this should have cast doubt on Polya's conjecture (I don't know if it really did). And in 1958 the conjecture was disproved by Haselgrove without a specific counterexample being found, much like Matt's answer about the size switch between $\pi(x)$ and ${\rm Li}(x)$. $\endgroup$
    – KCd
    Commented Feb 21, 2012 at 1:42
  • 13
    $\begingroup$ @phkahler if you go by the fact that $1$ is not a prime then $1$ is of even kind because it has $0$ prime factors (and last I checked $0$ is even) $\endgroup$ Commented Feb 22, 2012 at 0:56
  • 30
    $\begingroup$ @orokusaki: If you want to feel not just humbled but baffled, look at Math Overflow instead. $\endgroup$
    – Joe Z.
    Commented Mar 12, 2013 at 19:58
364
$\begingroup$

From "Experimentation in Mathematics" Borwein, Bailey and Girgensohn 2004 : $$\sum_{n=1}^{\infty} \lfloor n\cdot e^{\frac{\pi}3\sqrt{163}}\rfloor 2^{-n}=1280640\ \ \text{(correct to at least half a billion digits!)}$$ Using the $\mathrm{sinc}$ function ($\mathrm{sinc}(x)=\frac{\sin(x)}x$ and this paper) : $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\,\mathrm dx=\frac{\pi}2$$ $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\cdot \mathrm{sinc}\left(\frac x3\right)\,\mathrm dx=\frac{\pi}2$$ $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\cdot \mathrm{sinc}\left(\frac x3\right)\cdot \mathrm{sinc}\left(\frac x5\right)\,\mathrm dx=\frac{\pi}2$$ $$\cdots$$ $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\cdot \mathrm{sinc}\left(\frac x3\right)\cdot \mathrm{sinc}\left(\frac x5\right)\cdots \mathrm{sinc}\left(\frac x{13}\right)\,\mathrm dx=\frac{\pi}2$$ $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\cdot \mathrm{sinc}\left(\frac x3\right)\cdots \mathrm{sinc}\left(\frac x{15}\right)\,\mathrm dx=\frac{467807924713440738696537864469}{ 935615849440640907310521750000}\pi$$


In fact the story doesn't end here! It was found (see Baillie and Borweins' "Surprising Sinc Sums and Integrals") that you could replace the integrals by the corresponding $\frac 12 + \sum_1^{\infty}$ series : $$\frac 12 + \sum_{m=1}^{\infty} \prod_{k=0}^N \mathrm{sinc}\left(\frac m{2k+1}\right)=\int_0^{\infty} \prod_{k=0}^{N} \mathrm{sinc}\left(\frac x{2k+1}\right)\,\mathrm dx.$$

for the previous values of ($N=0,1,2,3\cdots 7$) but also for larger values of $N$ up to $40248$. For $N\gt 40248$ the left part is always larger than the integral at the right!

At this point the reciprocals of the odd integers could be replaced by other values (see the paper for the conditions required for the equality to hold) for example by the reciprocals of the prime numbers. Now, because of the slow divergence in this case, the equality breaks down only for $N \approx 10^{176}$ (when the sum of values slowly crosses the $2\pi$ barrier) and with an error smaller than $\displaystyle 10^{-10^{86}}$.

$\endgroup$
17
  • 46
    $\begingroup$ That is just uproariously funny! $\endgroup$ Commented Feb 21, 2012 at 0:27
  • 59
    $\begingroup$ The 'trick' in the sinc integrals, incidentally, is that the last one is the first for which the sum of the arguments (at x=1) exceeds 2: 1/1+1/3+1/5+...+1/13 = 1.9551..., but add 1/15 and the sum becomes 2.0218... - the behavior is, roughly, tied to that sum. $\endgroup$ Commented Feb 21, 2012 at 1:20
  • 15
    $\begingroup$ The $\sqrt{163}$ sum leaves me cold but the sinc integrals are just great. I learned something today, thanks. $\endgroup$
    – Did
    Commented Feb 21, 2012 at 15:34
  • 21
    $\begingroup$ @DidierPiau, it probably has something to do with 163 being one of the Heegner numbers, as they produce near integers in this fashion (eg. $e^{\pi \sqrt{163}}$)... $\endgroup$ Commented Feb 21, 2012 at 16:51
  • 23
    $\begingroup$ There is a probabilistic interpretation of the sinc result. We have $$\int_0^\infty \prod_{j=0}^n \text{sinc}\left({x\over 2j+1}\right)\,dx= 2\pi g_n(0)$$ where $g_n$ is the density function of the sum $U_0+\dots+U_n$ of independent random variables $U_j$ uniformly distributed over the interval $(-2/(2j+1),2/(2j+1))$. As shown in my paper (stat.ualberta.ca/people/schmu/preprints/rhs.pdf), $g_n(0)=1/4$ for $0\leq n\leq 6$, but $g_7(0)<1/4$. $\endgroup$
    – user940
    Commented Feb 21, 2012 at 21:47
283
$\begingroup$

The seminal paper on this is Richard Guy's The Strong Law of Small Numbers Proclaiming "there aren't enough small numbers to meet the many demands made of them," it lists $35$ patterns that don't pan out. Others have expanded on the 'law of small numbers' Such as here (and a few more links on that page)

A particularly great example from the second link:

  • $\gcd(n^{17}+9, (n+1)^{17}+9)$ seems to always be $1$. In fact, if you had your computer checking this for $n=1, 2, 3, \dots$ successively, it would never find a counter-example. That is because the first counter-example is $$8424432925592889329288197322308900672459420460792433\;.$$
$\endgroup$
6
  • 27
    $\begingroup$ The counter was found analytically? $\endgroup$
    – mrk
    Commented Jan 30, 2014 at 20:07
  • 21
    $\begingroup$ @saadtaame: Such examples are found using resultants and factoring polynomial a mod $p$. See the top answer at mathoverflow.net/questions/130783/… for a similar example. $\endgroup$
    – KCd
    Commented Sep 12, 2014 at 3:49
  • $\begingroup$ What is the gcd for the number provided at the end? $\endgroup$ Commented May 8, 2021 at 2:57
  • 3
    $\begingroup$ @EkadhSingh-ReinstateMonica $8936582237915716659950962253358945635793453256935559.$ (I just entered the expression into Wolfram Mathematica, which is natively capable of long exact arithmetic.) $\endgroup$
    – Ruslan
    Commented Nov 14, 2021 at 9:31
  • 2
    $\begingroup$ @GitGud They mean the gcd given in the answer, $\gcd(n^{17}+9, (n+1)^{17}+9)$ for $n = 8424432925592889329288197322308900672459420460792433$. $\endgroup$ Commented Mar 28, 2023 at 13:14
152
$\begingroup$

Choose n points around the circumference of a circle, and join every point to every other with a line segment. Assuming that no three of the line segments concur, how many regions does this divide the circle into?

There's a rather obvious pattern, that breaks down at n=6.

$\endgroup$
7
  • 8
    $\begingroup$ For reference, this is OEIS A000127, discussed on the Math Forum. $\endgroup$
    – user856
    Commented Feb 21, 2012 at 2:45
  • 5
    $\begingroup$ This was exactly the example that I was going to give, +1 from me $\endgroup$
    – Francesco
    Commented Feb 21, 2012 at 7:36
  • 35
    $\begingroup$ SpikedMath had a post about this one, in case one needs pictures. $\endgroup$
    – Charles
    Commented Feb 21, 2012 at 9:07
  • 23
    $\begingroup$ You can also tell people that the tenth element of this sequence is 256, and they think "aha! the pattern continues!" $\endgroup$ Commented Mar 6, 2012 at 22:24
  • 7
    $\begingroup$ 3Blue1Brown Has this excellent video about this nigh-pattern too! youtube.com/watch?v=84hEmGHw3J8 $\endgroup$
    – Xoque55
    Commented Apr 24, 2018 at 13:36
124
$\begingroup$

Claim: The cyclotomic polynomials $\phi_n(x)$ have coefficients in the set $$\{ -1, 0, 1 \}$$

It holds for any number that doesn't have at least $3$ distinct odd prime factors, which means the smallest counterexample is $3 \cdot 5 \cdot 7 = 105$. So a naive undergrad probably won't ever see a counterexample unless they are specifically shown $\phi_{105}$.

$\endgroup$
5
  • 3
    $\begingroup$ Yea, I am not sure I have ever seen one. I think Dummit and Foote mentions that they are not always in -1, 0, or 1 but doesn't say anything else about it, unless I am mistaken. $\endgroup$
    – GeoffDS
    Commented Feb 21, 2012 at 23:39
  • 4
    $\begingroup$ Another antidote to this line of thinking is when you are shown theorems about the "height" of $\phi_n$ (the height being the absolute value of the largest coefficient). For some reason, this measure is of particular interest for cyclotomic polynomials, but shouldn't it always be $1$? $\endgroup$ Commented Apr 7, 2014 at 9:10
  • 2
    $\begingroup$ I'd like to vote for this answer, but I will desist since it (now) has 105 votes. $\endgroup$ Commented Feb 7, 2021 at 16:27
  • 2
    $\begingroup$ I've been told verbally without a citation that this was actually really conjectured to be true when cyclotomic polynomials were first being studied, and someone had calculated them up to $\phi_{100}$. $\endgroup$
    – JoshuaZ
    Commented Jul 8, 2021 at 17:53
  • $\begingroup$ A reference for anyone interested in the details is On the size of the coefficients of the cyclotomic polynomial by P.T. Bateman which shows that the absolute value of the largest coefficient in $\phi_n$ can be "almost exponentially large" in $n$. $\endgroup$ Commented Feb 11, 2023 at 11:19
115
$\begingroup$

Take from Joseph Rotman's "A First Course in Algebra: with applications":

The smallest value of $n$ for which the function $f(n) = 991n^2 + 1$ is a perfect square is

$$ n = \mbox{12,055,735,790,331,359,447,442,538,767}. $$


On a similar note, the smallest value of $n$ such that the function $g(n) = 1,000,099n^2 + 1$ is a perfect square has $1116$ digits.

$\endgroup$
15
  • 3
    $\begingroup$ @Chaz: Correct. The values of $f(n)$ for $1 \leq n \leq 12,055,735,790,331,359,447,442,538,766$ are all non-squares. $\endgroup$
    – JavaMan
    Commented Feb 21, 2012 at 3:41
  • 15
    $\begingroup$ That doesn't feel like much of a pattern. It's more of the absence of one! $\endgroup$
    – 8128
    Commented Feb 23, 2012 at 9:45
  • 23
    $\begingroup$ @fluteflute: After checking the first $12,000,000,000,000,000,000,000,000,000$ values you wouldn't guess that ALL values are nonsquares? $\endgroup$
    – JavaMan
    Commented Feb 23, 2012 at 12:45
  • 10
    $\begingroup$ Well, no. There is no intuition of a reason why ALL values would be nonsquares. $\endgroup$
    – Wok
    Commented May 4, 2012 at 11:18
  • 12
    $\begingroup$ How do you compare $n$, a pure number, with a quantity measured in square dollars? $\endgroup$
    – bof
    Commented Jul 15, 2014 at 1:57
108
$\begingroup$

I am kind of partial to the old $n^2 + n + 41$ chestnut, namely that the expression is prime for all $n$. It fools an awful lot of people.

$\endgroup$
14
  • 20
    $\begingroup$ The chestnut being what exactly? $\endgroup$
    – Dason
    Commented Feb 21, 2012 at 3:07
  • 37
    $\begingroup$ This doesn't really satisfy condition (2.) of the original question. No sane person needs a computer to check the $n=41$ counterexample. $\endgroup$
    – Tib
    Commented Feb 21, 2012 at 17:27
  • 17
    $\begingroup$ @Tib: It is easy to check if you push them in the right direction. $41^2 + 41 + 41$ is clearly divisible by 41. $\endgroup$
    – Mike Boers
    Commented Feb 23, 2012 at 20:45
  • 63
    $\begingroup$ $40^2+40+41$ is also clearly divisible by 41. $\endgroup$
    – MJD
    Commented Jun 2, 2012 at 23:24
  • 23
    $\begingroup$ I had my introCS students going on this today.... I subbed in for a few integer and heard, "We can prove this by induction!" Snicker. $\endgroup$ Commented Sep 23, 2014 at 1:38
83
$\begingroup$

Perhaps a little technical, but I think you can give the flavour without the details. It was long believed that the logarithmic integral $\operatorname{Li}(x)$ is greater than the prime counting function $\pi(x)$ for all $x$, and computations verified this for a lot of "small" (but by most people's standards fairly large) $x$. It was proved to be false in 1914 by J.E. Littlewood, who did not find a counterexample explicitly, but showed that one must exist - it is believed to be around $10^{316}$, way outside the range of computations at the time.

So this example isn't great, because the logarithmic integral is fairly technical, but the specifics of $\operatorname{Li}(x)$ aren't that important, so it's just about one function being bigger than another.

More details on Wikipedia.

$\endgroup$
64
$\begingroup$

The "Chinese remainder" prime-test:

$$ \text{if } 2^n - 1 \equiv 1 \mod n \text{ then } n \in \mathbb{P} $$

fails first time at $n=341$. That was one of the things that really made me thinking when I began hobbying with number-theory in a more serious way...

$\endgroup$
8
  • 10
    $\begingroup$ Hey Gottfried -- this is basically the base-$2$ Fermat primality test; it fails first for $n=341$ i.e. $341$ is the first base-$2$ Fermat pseudoprime. I'm surprised you call it by this funny name? $\endgroup$ Commented May 25, 2013 at 20:45
  • 3
    $\begingroup$ Well the Chinese remainder theorem is that if $(x,y)=1$ then for any $a$ and $b$, the congruences $n\equiv a\ (\operatorname{mod x})$ and $n\equiv b\ (\operatorname{mod y})$ uniquely determine $n\ (\operatorname{mod xy})$. But I've never seen what you've written named that way. $\endgroup$ Commented May 25, 2013 at 21:20
  • 1
    $\begingroup$ @Douglas: one google for "chinese primality test" gave www-math.mit.edu/phase2/UJM/vol1/DORSEY-F.PDF (sec. 2 pg 134 ff) - but, well, it seems just not worth making a big thing of it... $\endgroup$ Commented May 25, 2013 at 21:38
  • 1
    $\begingroup$ "In 1640, Fermat rediscovered what the ancient Chinese had known nearly 2000 years before him." Well you learn something every day. I wasn't trying to make a bit thing of it -- I honestly wanted to know. $\endgroup$ Commented May 25, 2013 at 21:51
  • 3
    $\begingroup$ You know, Gottfried, I have 31 articles on my computer about primality tests, and searching all of them for "Chinese" doesn't bring up anything about this. However, the paper you linked to references Dickson's History of the Theory on Numbers, where it indeed says: "The Chinese seem to have known as early as 500 B.C. that $2^p - 2$ is divisible by the prime $p$." [Dickson, Vol. 1, pp.59]. I suspect this is scarcely known among number theorists. $\endgroup$ Commented May 26, 2013 at 20:04
57
$\begingroup$

Heather360 gives the following amusing example:

US presidents elected in 1840, 1860, 1880, 1900, 1920, 1940, and 1960 all died in office, but Ronald Reagan did not.

But the following example is probably more along the lines of what you had in mind. The pattern is not very long, but it is very simple and could be explained to anyone of any background:

http://threesixty360.wordpress.com/2008/10/26/one-two-three-four-six-again-and-then-again/

Also, since you started your question without reference to patterns, per se, but to the importance of mathematical proof, I would point to the Banach-Tarski paradox. I think most people, especially non-mathematicians, have trouble believing this result, so it is certainly an example of mathematical proof establishing a counter-intuitive result.

$\endgroup$
5
  • 33
    $\begingroup$ That (Banach-Tarski) is not an example you should use to make people believe in mathematics ;-) $\endgroup$
    – phkahler
    Commented Feb 21, 2012 at 15:40
  • $\begingroup$ Well if we're going to go with examples outside of math, how about the famous claim that the winner of the superbowl (whether home or away) will determine whether the stock market goes up or down? Sounds ridiculous, but it held true for something like 15 years straight, then the majority of the next 10. $\endgroup$ Commented Feb 21, 2012 at 19:32
  • $\begingroup$ @phkahler You are absolutely right!! $\endgroup$ Commented Feb 4, 2014 at 2:03
  • 5
    $\begingroup$ Your list of years for elected US presidents who died in office left out 1848, the year Zachary Taylor was elected (he died in 1850). Of course that wrecks the multiple-of-twenty pattern, but it's worth mentioning so those unfamiliar with US history don't think 1840, 1860, ..., 1960 is the complete list of years for elected US presidents who died in office. $\endgroup$
    – KCd
    Commented Sep 9, 2015 at 20:16
  • $\begingroup$ @phkahler Nor in physics: physical space is modeled as locally Euclidean, so the construction goes through there just as well. Chemistry, which relies on Physics, becomes equally suspect. And so on... $\endgroup$ Commented Aug 20, 2019 at 17:22
56
$\begingroup$

I like to point to the many tuples of numbers that are part of multiple sequences at OEIS.org. I just typed in 1, 1, 2, 3, 5 and got 751 results.

$\endgroup$
5
  • 20
    $\begingroup$ Even with 1,1,2,3,5,8,13,21,34,55,89 you still get 26 results. While many contain the word "Fibonacci" in the description, there's also "Expansion of 1/(1 - x - x^2 + x^18 - x^20)." $\endgroup$
    – celtschk
    Commented Sep 15, 2012 at 21:41
  • 12
    $\begingroup$ You can actually get up to 10946 and still have a result that's not directly related to the Fibonacci sequence. $\endgroup$
    – Joe Z.
    Commented Mar 21, 2013 at 20:37
  • 13
    $\begingroup$ Joe, that sequence is directly related to the Fibonacci sequence. Read the description closely. All the elements from the 8th (2) to the 26th (10946) are defined as the sum of the previous two numbers. You can't get any more "Fibonacci-related" than that! $\endgroup$ Commented Apr 13, 2015 at 19:18
  • $\begingroup$ Agree with @GuriHarari: the formula for A132916 contains $[n^{1/3}]$, but using the integer part of something that grows slowly will flatten this sub-series to 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... series values from $1^3=1$ to $2^3-1=7$ will match A000012, from $2^3=8$ to $3^3-1=26$ will match A000045 (Fibonacci), from $3^3=27$ to $4^3-1=63$ will match Tribonacci variation of A000073 with different initial numbers, etc. If instead it had used $[α(n)^{1/3}+1]$ with $α$ being the inverse Ackermann function, then we would have an unimaginable number of matches with Fibonacci. $\endgroup$
    – Cœur
    Commented Sep 3, 2018 at 16:47
  • $\begingroup$ Oh well, $$f(0)=0;\ f(1)=1;\ f(n)=\sum_{k=1}^{\alpha(\alpha(n))}f(n-k)\text{ for }n≥2.$$ where $\alpha(n)$ is the smallest integer i such that TREE(i) ≥ n should have more common consecutive terms with Fibonacci than anyone would be willing to ever calculate. $\endgroup$
    – Cœur
    Commented Sep 3, 2018 at 18:42
50
$\begingroup$

This is taken from Inside Interesting Integrals by Paul J. Nahin. $$\begin{align}\int_0^\infty\cos(x)\frac{\sin(4x)}{x}\,dx&=\frac{\pi}{2}\approx1.57079632679\ldots\\\int_0^\infty\cos(x)\cos\left(\frac{x}{2}\right)\frac{\sin(4x)}{x}\,dx&=\frac{\pi}{2}\approx1.57079632679\ldots\\\int_0^\infty\cos(x)\cos\left(\frac{x}{2}\right)\cos\left(\frac{x}{3}\right)\frac{\sin(4x)}{x}\,dx&=\frac{\pi}{2}\approx1.57079632679\ldots\\\end{align}$$ and so on, all the way out to $$\int_0^\infty\cos(x)\cos\left(\frac{x}{2}\right)\cos\left(\frac{x}{3}\right)\cdots\cos\left(\frac{x}{30}\right)\frac{\sin(4x)}{x}\,dx=\frac{\pi}{2}\approx1.57079632679\ldots$$ One may suspect $$\int_0^\infty\prod_{k=1}^n\cos\left(\frac{x}{k}\right)\frac{\sin(4x)}{x}\,dx=\frac{\pi}{2}\qquad,\qquad\text{for all $n$}.$$ This is exciting! But then the pattern fails for $n=31$ since $$\int_0^\infty\cos(x)\cos\left(\frac{x}{2}\right)\cos\left(\frac{x}{3}\right)\cdots\cos\left(\frac{x}{30}\right)\cos\left(\frac{x}{31}\right)\frac{\sin(4x)}{x}\,dx\approx1.57079632\color{red}{533\ldots}$$

$\endgroup$
5
  • $\begingroup$ Looks much like the Borwein integrals mentioned here. $\endgroup$ Commented Nov 15, 2014 at 14:05
  • $\begingroup$ Out of curiosity, does that finite product of cosines have a closed form? $\endgroup$
    – David H
    Commented Nov 15, 2014 at 14:10
  • $\begingroup$ @DanielFischer I thought so but I then checked the cited paper in the answer. This integral isn't mentioned in that paper, but I wouldn't say this is not Borwein-like integrals. $\endgroup$
    – Venus
    Commented Nov 15, 2014 at 14:18
  • $\begingroup$ @DavidH I don't know, I've just bought the book. It possibly doesn't have it. $\endgroup$
    – Venus
    Commented Nov 15, 2014 at 14:20
  • 13
    $\begingroup$ @Venus The Borwein integrals stop being $\frac{\pi}{2}$ when $\sum_{k=0}^n \frac{1}{2k+1} > 2$, these stop when $\sum_{k=1}^n \frac{1}{k} > 4$. That makes me suspect there is a relation beyond the superficial similarity, but it's not obvious. Anyway, if you haven't already read it, don't miss this hilarious story about the Borwein integrals. $\endgroup$ Commented Nov 15, 2014 at 14:51
49
$\begingroup$

I think Expected outcome for repeated dice rolls with dice fixing qualifies. You roll $n$ standard six-sided dice and may fix any non-empty subset of them, then re-roll the others and again fix at least one of them, and so on until all dice are fixed. The intuition that you should always fix any $6$s you roll if you want to maximise the expected sum of the dice holds true for $n\le199$ and first fails for $n=200$.

$\endgroup$
43
$\begingroup$

Fermat numbers would be a good example. The numbers $F_n = 2^{2^n}+1$ are prime for $n=1,2,3,4$, however $F_5 = 4,294,967,297 = 641 × 6,700,417$ is not prime. In fact, there are no known Fermat primes $F_n$ with $n > 4$.

Admittedly this isn't impossible to check by hand, but the rapid increase in $F_n$ makes it factoring such numbers by hand highly impractical. I can't imagine any layman who would be comfortable trying to factor even a 10 digit number. In the case of $F_5$, trying to check for prime factors by brute force you would have to check 115 primes before you get to 641.

$\endgroup$
2
  • 20
    $\begingroup$ When telling this story, it's highly effective to mention that Fermat himself was fooled by this, having apparently not bothered to check $n=5$! Also, it drives the point home to mention that we're now in the opposite situation, where one is tempted to conjecture that $F_n$ is prime iff $n=1,2,3,$ or $4\ldots$ $\endgroup$ Commented Apr 10, 2013 at 2:33
  • $\begingroup$ It's not actually non-checkable by hand: one can simply start with 2, square it $2^5=32$ times, modulo $641$, then check the result is congruent to $-1$ modulo $641$. $\endgroup$
    – pzq_alex
    Commented Jul 15, 2023 at 11:07
41
$\begingroup$

Does Goodstein's Theorem fit the bill?

(By the way, here is a nice applet.)

The question was:

So, are there any examples of non-trivial patterns that appear to be true for a large number of small cases, but then fail for some larger case? A good answer to this question should:

$(1)$ be one which could be explained to the layman without having to subject them to a $24$ lecture course of background material, and

$(2)$ have as a minimal counterexample a case which cannot (feasibly) be checked without the use of a computer.

Requirement $(1)$ is obviously satisfied.

Is requirement $(2)$ is satisfied?

In some sense it is not, because a computer wouldn't help.

But, in another sense, it is over satisfied, because, even with the most powerful imaginable computer, the statement cannot be checked. That is, it cannot be checked by any calculation, although it only involves addition, multiplication and exponentiation of positive integers. But with a very simple notion (that of ordinal), it becomes almost trivial.

To say it in another way: It is very easy to prove that the apparent pattern will break eventually, but the argument doesn't give the slightest clue about when it will break.

So, Goodstein's Theorem is, I think, a quite instructive piece of mathematics.

$\endgroup$
2
  • 2
    $\begingroup$ A particular instance, such as the claim "the Goodstein sequence $G(4)$ does not terminate" would satisfy (2) as well as (1). $\endgroup$ Commented Sep 12, 2012 at 22:02
  • 2
    $\begingroup$ This reminds me of Kruskal's tree theorem, which states the function TREE(n) must have a finite value. TREE(n) is the length of a longest sequence of n-labelled trees T1,...,Tm in which each Ti has at most i vertices, and no tree is embeddable into a later tree. TREE(1) = 1, TREE(2) = 3, but TREE(3) is so enormous it makes Graham's number almost nothing. Graham's number is about A^64(4), where A is the Ackermann function. An EXTREMELY weak lower bound for TREE(3) is A^(A(187196))(1). $\endgroup$
    – zhuli
    Commented Apr 9, 2014 at 12:13
37
$\begingroup$

This is a bit complicated for laymen, but it's great for aspiring number theorists. We have two conjectures:

(1) The prime $k$-tuples conjecture: every admissible sequence occurs infinitely often, and with the asymptotic frequency derived using a heuristic that essentially treats prime numbers as random (see the link for the exact expression). This is a generalization of the twin prime conjecture, which corresponds to the $k=2$ case. The $k=3$ case implies that there are infinitely many $p \in \mathbb{N}$ such that $p$, $p+2$, and $p+6$ are all prime.

(2) The Hardy-Littlewood convexity conjecture: $\pi(x+y)\leq \pi(x)+\pi(y)\ \forall\ x,y\geq 2$, where $\pi(x)$ is the prime counting function. This conjecture claims that the primes are densest for small $x$.

No counterexamples are known for either (1) or (2). In isolation, both (1) and (2) seem reasonable. However, it turns out that (1) and (2) are mutually exclusive, which you might imagine if you stare at them both long enough with a glass of whisky.

This example comes from Crandall and Pomerance, pp. 20-21: "... the current thinking is that the Hardy-Littlewood convexity [conjecture] is false ... but it also may be that any value of $x$ required to demolish the convexity conjecture is enormous."

For laymen, what you can say is that there are conjectures for which no counterexamples are known, even after checking many billions of cases with computers, but which are nevertheless known to be false. Another such example is the $\pi(x) < \operatorname{Li}(x)$ false conjecture in Matt Pressland's answer.

$\endgroup$
2
  • $\begingroup$ I didn't know that result was from Crandall and Pomerance. I thought it was from Hensley and Richards. $\endgroup$
    – bof
    Commented Jul 15, 2014 at 2:08
  • 2
    $\begingroup$ @bof, the result is from Hensley and Richards, the discussion is from Crandall and Pomerance. $\endgroup$ Commented Jul 15, 2014 at 2:46
33
$\begingroup$

This recent question on math.SE provides an example, although the apparent pattern is fairly short.

Consider two unit spheres in $n$ dimensions whose centers are $1$ unit apart. What is the fraction $\phi_n$ of the area of one sphere that lies inside the other?

As it turns out, the answer is quite nice for small $n$, but quickly breaks down: $$\begin{align} \phi_1 &= \frac12, \\ \phi_2 &= \frac13, \\ \phi_3 &= \frac14, \\ \phi_4 &= \frac13-\frac{\sqrt3}{4\pi} \approx 0.195501\!\ldots, \\ \phi_5 &= \frac5{32}, \\ &\vdots \end{align}$$

The general formula is $$\phi_n = \frac{\int_{\pi/6}^{\pi/2}\cos^{n-2}\theta\,\mathrm d\theta}{\int_{-\pi/2}^{\pi/2}\cos^{n-2}\theta\,\mathrm d\theta} = \frac12 I_{3/4}\left(\frac{n-1}2,\frac12\right)$$ (thanks @joriki and Wikipedia), where $I_x(a,b)$ is the regularized incomplete beta function.

$\endgroup$
1
  • 9
    $\begingroup$ This is why any geometry in more than four dimensions is completely mind-fizzling. $\endgroup$
    – Joe Z.
    Commented Mar 12, 2013 at 19:57
29
$\begingroup$

Euler's sum of powers conjecture, proposed in 1769, is a generalization of Fermat's Last Theorem about the following Diophantine equation $$\sum_{i=1}^n X_i^k=Y^k\textrm{, where }n\neq 1$$

It states that for the equation to have any solutions in positive integers, $n$ must be at least $k$ (FLT is the statement that $n\ge 3$ if $k\ge 3$). For small values of $X_i,Y$, the conjecture appears to be true.

In 1966, L. J. Lander and T. R. Parkin found a counterexample for the $k=5$ case:

$$25^5+84^5+110^5+133^5=144^5.$$

In 1986, Noam Elkies found an infinite family of solutions to $X^4+Y^4+Z^4=W^4$ - another counterexample. In 1988, Roger Frye used a computer and Elkies's method to find the smallest such counterexample to the $k=4$ case:

$$95800^4+217519^4+414560^4=422481^4.$$

This is the only solution where $W,X,Y$ and $Z$ are less than $1,000,000$.

$\endgroup$
2
  • 13
    $\begingroup$ A related pattern would be $$3^2+4^2=5^2\\3^3+4^3+5^3=6^3, $$ which fail at the next step$$3^4+4^4+5^4+6^4\neq 7^4$$...+1 $\endgroup$
    – draks ...
    Commented Jun 2, 2014 at 13:35
  • 13
    $\begingroup$ @draks... It also fails at the previous step ($3^1 \neq 4^1$)! $\endgroup$
    – wchargin
    Commented May 25, 2015 at 22:21
27
$\begingroup$

Can a circle be cut up into a finite number of parts and rearranged to form a square? Laczkovich proved in 1990 that this can be done with about $10^{50}$ pieces.

A good source for this kind of thing is "Old and new unsolved problems in plane geometry and number theory," by Klee and Wagon. The advantage is that none of the problems use more than arithmetic and geometry, so the examples are accessible to people who aren't mathematicians.

$\endgroup$
1
  • 21
    $\begingroup$ I'm not sure the dissection is a great example; there's no 'easy' way of showing that it doesn't happen for smaller counts of pieces, and even for the large piece-counts they're not 'parts' in the ways that people would really expect (in particular, their boundaries aren't proper curves). $\endgroup$ Commented Feb 21, 2012 at 1:24
24
$\begingroup$

This might be a simple example.

If we inscribe a circle of radius 1 in a square of side 2, the ratio of the area of the circle to the square is $\frac{\pi}{4}$. You can show that any time we put a square number of circles into this square, the ratio of the area of the circles to that of the square is (for the simple symmetric arrangement) again $\frac{\pi}{4} $. So for 1, 4, 9, 16 circles, this packing is the best we can do.

I had mistakenly assumed, based on this "obvious" pattern, that the limit of optimal packings of circles into the square did not converge, but rather continued to drop down to this same ratio every time a square number was reached.

This turns out not to be true, as I learned here.

The pattern breaks down at n=49 circles. At 49 circles the optimal packing, given here, is not the simple square lattice arrangement.

There are many other examples, but this served as a reminder for me.

$\endgroup$
2
  • 6
    $\begingroup$ One way of 'intuitively' seeing why this pattern had to break, incidentally, is that if the density of a given (infinite) packing is $d$, then the number of circles (of diameter 1) that can be packed into a square of size $N$ is $dN^2-O(N)$ - the latter term being the result of boundary effects (since only $O(N)$ circles will be 'on the boundary'). Since $d$ for the hexagonal packing ($\frac\pi{2\sqrt{3}}$)is larger than the $d$ for the square packing ($\frac\pi4$), then eventually the $dN^2$ term will overwhelm the $O(N)$ 'boundary effect'. $\endgroup$ Commented Jul 22, 2013 at 22:25
  • 2
    $\begingroup$ @StevenStadnicki: I am getting 'math processing errors' at the moment but this looks like an interesting approach and I will study it hopefully in an hour or three when my computer is cooperating. --Oh here it is. Yes, this is intuitive and helpful, thank you. $\endgroup$
    – daniel
    Commented Jul 23, 2013 at 0:15
23
$\begingroup$

Let $$\pi^{(4)}_1(N) = \text{ Number of primes }\leq N\text{ that are of the form } 1 \bmod 4$$ and $$\pi^{(4)}_3(N) = \text{ Number of primes }\leq N\text{ that are of the form } 3 \bmod 4$$

$$ \begin{array}{ccc} N & \pi^{(4)}_1(N) & \pi^{(4)}_3(N) \\ 100 & 11 & 13\\ 200 & 21 & 24\\ 300 & 29 & 32\\ 400 & 37 & 40\\ 500 & 44 & 50 \end{array} $$

Looking at the pattern, one can wonder if $\pi^{(4)}_1(N) \leq \pi^{(4)}_3(N)$ is true for all $N$. In fact, this remains true for $N$ up-to $26,860$.

$26,861$ is a prime $\equiv 1 \bmod 4$ and we find that $\pi^{(4)}_1(26,861) = \pi^{(4)}_3(26,861) + 1 > \pi^{(4)}_3(26,861)$. You can read more about this and similar questions on primes here.

$\endgroup$
1
22
$\begingroup$

Here is a true story which might be entertaining, if not strictly following your conditions.

We were working on an algorithm for solving problem X. As is quite usual with algorithms, there is some parameter $n$ measuring the complexity of the input. Our algorithm depended on a set of parameters for each $n$. We were able to find suitable parameters for each $n$.

Then we tried to generalize the algorithm to problem Y, using the same parameters derived for problem X. We worked hard on proving that this approach works. My coauthor proved the cases $n=2,3,4,5$ by hand, each progressively more difficult. The computer (with my help) was able to find a proof for $n = 6$. When asked about $n = 7$, the computer thought for a while and then announced that it couldn't find a proof because for $n = 7$ our approach fails!

Not only were our hearts broken (we stopped working on the problem for a few months), but we were quite at a loss to figure out what goes wrong at $n = 7$, and how to fix it. When algorithms fail, the minimal counterexample is usually small and there is hope of getting around the problem. Not so in this case.

Fortunately, later on we were able to find another set of parameters for problem Y which did work for $n = 7$. This time we held our breath until the computer verified all cases up to $n = 50$, though we were not in peace with ourselves until we proved that our new parameters work for all $n$.

$\endgroup$
2
  • $\begingroup$ I'm really curious; do you have a published reference? =) $\endgroup$
    – user21820
    Commented May 19, 2019 at 0:40
  • $\begingroup$ @user21820 Yes, but the story is not described there. $\endgroup$ Commented May 19, 2019 at 6:02
21
$\begingroup$

From Fermat's Little theorem, for primes $p$, we know that

$$ p \mid 2^p - 2. $$

For which primes $p$ does

$$p^2 \mid 2^{p} - 2 ?$$


Most people when first seeing this question, would try small cases of $p$, and realize that it doesn't work. They may then look at

$$\frac{(1+1) ^p - 2}{p} = \frac{{ p \choose 1} + { p\choose 2} + \ldots + { p \choose p-1}}{p} \equiv \frac{1}{1} + \frac{-1}{2} + \frac{1}{3} + \ldots + \frac{(-1)^{p}}{p-1} \pmod{p}$$

and try and prove that it is not 0.

As it turns out, the Wieferich primes satisfy $p^2 | 2^p-2$. There are only 2 known examples of such primes, namely $p=1093, 3511$. There are no other examples less than $10^{17}$.

$\endgroup$
0
19
$\begingroup$

Prove or disprove that ${F_{n}}^2 + 41$ is always a composite conjectures that when $F$ is a fibonacci number, $F^2+41$ is composite. As reported there, computer calculations find that the conjecture is false; the smallest counterexample occurs at the $12588$th fibonacci number, which has 2630 digits.

$\endgroup$
17
$\begingroup$

Here is a short sequence: 1, 2, 3, 4, 5, 6 What is next term ? Next term is 1000, obviously.

$a(n)= n + ((n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(p-7))/6! $

Choose p = 1000 and you´ll get seventh term a(7)= p = 1000, obviously. Choose p = 7 and you´ll get 7, also obviously. We get $a(7) = p$ and so a(7) is always whatever you want; but $a(8) = 7p -41 ; a(9) = 56p -383$ are deteremined by p. Naturally you can easily extend the formula to whatever 1,2,3,4,5,6,7,8,9,1000111,... as an also obvious example. I found this formula in the book "Planetas" by the Spaniard astrophysicist Eduardo Battaner. I recommend reading his great book: "Física de las noches estrelladas", full of equations but the better divulgative astrophysics (and in general) book i have ever read, and i read a few. Great book to learn how to divulgate ¿"difficult"? problems to amateurs and newcomers in general who could not formally learn it at school/university. After reading it you´ll have a much better idea of what the Universe is without being messed with the abundant (bad) literature. I do not think, though, there is a translation of the 280 pages book into English or French or German.

See :

http://lit-et-raire.blogspot.com.es/2013/02/una-sucesion-muy-natural-y-tu-medida.html

$\endgroup$
3
  • 1
    $\begingroup$ No, $a(7)=7,$ but $a(8)=14$ and $a(9)=37$ $\endgroup$ Commented Feb 16, 2013 at 4:48
  • $\begingroup$ See:lit-et-raire.blogspot.com.es/2013/02/… $\endgroup$
    – user55514
    Commented Feb 17, 2013 at 9:46
  • 12
    $\begingroup$ Also: The first three terms of a sequence are $1$. What is the fourth? Well, $-17$ of course: $1^0-0^1=1$, $2^1-1^2=1$, $3^2-2^3=1$, $4^3-3^4=-17$. $\endgroup$
    – celtschk
    Commented Jul 22, 2013 at 21:32
15
$\begingroup$

The number below might serve as a good example: $$13532385396179.\tag{$\star$}$$ It turns out that if we want to find the prime factorisation of this number, we get that this is equal to $$13\times 53^2\times 3853\times 96179.$$ This number is a counter-example to one of John Conway's five problems $-$ the very last one, as a matter of fact. Problem $5$ is known as Climb to a Prime and is stated as follows:

Problem 5. Climb to a Prime${}$:

Let $n\in\mathbb{Z}^+$. Write the prime factorisation of $n$ in the usual way, e.g. $60 = 2^2\times 3\times 5$, in which the primes are written in increasing order, and exponents of $1$ are omitted. Then, bring the exponents down to the line and omit all multiplication signs, obtaining a number $f(n)$. Now, repeat.

So for example, $f(60) = f(2^2\times 3\times 5) = 2235$. Next, because $2235 = 3\times 5\times 149$, it maps under $f$ to $35149$, and since $35149$ is prime, it maps to itself. Thus, $60\to 2235\to 35149$ $\to 35149\to 35149\to\ldots$, so we have climbed to a prime and we stop there forever.

The conjecture, in which John Conway seemed to be the only believer at the time, was that every number eventually climbs to a prime. The number $20$, however, has not been verified to do so. Observe that $20\to 225\to 3252\to 223271\to\ldots$, eventually getting to more than one hundred digits without yet reaching a prime!

Of course, the number $(\star)$ is a counter-example. It is the first counter-example thus far, and is larger than $10^{14}$, which in my opinion, would make this number fairly big.

$\endgroup$
14
$\begingroup$

Fermat's ‘little’ theorem states that if $n$ is prime, then $$a^n\equiv a\pmod n\tag{$\ast$}$$ holds for all $a$. The converse, which is false, states that if $(\ast)$ holds for all $a$, then $n$ is prime.

Counterexamples to this converse are uncommon; the smallest is $n=561$.

$\endgroup$
11
$\begingroup$

Here is an example relating to a Diophantine equation. Consider positive integer solutions of $a^3 + b^3 + c^3 = d^3$. The first few primitive solutions all contain 2 odd and 2 even integers, i.e. (3,4,5,6), (1,6,8,9), (3,10,18,19), (7,14,17,20), (4,17,22,25) and (18,19,21,28). But then the pattern breaks down with (11,15,27,29).

A list of the small solutions is at http://mathworld.wolfram.com/DiophantineEquation3rdPowers.html

$\endgroup$
1
  • 2
    $\begingroup$ In general, Diophantine equations can get very nasty, as there is no general method to solve all of them but the solutions can be wild. Here's another example: $$\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} = N$$ If we are looking for strictly positive solutions, even when $N=4$, the smallest solution has $80$ digits. Paper: ami.ektf.hu/uploads/papers/finalpdf/AMI_43_from29to41.pdf Blog post: quora.com/… $\endgroup$
    – zhuli
    Commented Jan 8, 2020 at 14:15
9
$\begingroup$

An example of a pattern I thought would hold is Waring's Problem. The theorem is that for any natural numbers $k$ and $n$ if $n>n_0$ there is a $l$ such that $n$ is expressible as the sum of $l$ $k$-th powers. The patter comes in when we attempt to compute these numbers. Obviously any number is the sum of $1$ first power. Lagrange's Theorem shows that any $n$ is the sum of $4$ squares. Also, any large enough $n$ is the sum of $9$ cubes. One may be tempted to think that we would want $16$ fourth powers, however, this is where the pattern diverges. We actually need $19$, and we need $37$ fifth powers, and $73$ sixth powers.

$\endgroup$
9
$\begingroup$

You have not died every day since you were born.

$\endgroup$
4
  • 1
    $\begingroup$ Well, that's kind of true and maybe kind of funny, if you like dark humor. The OP was most likely more interested in something technical, so I fear your memento mori is not answer (let alone the fact that it's off-topic). $\endgroup$
    – user228113
    Commented May 25, 2015 at 23:05
  • 7
    $\begingroup$ My humor is 71% dark. It may not be the best tasting, but it is better for you. $\endgroup$ Commented May 25, 2015 at 23:52
  • $\begingroup$ Well, it's related to logic. Not very technical, but easy to understand. $\endgroup$
    – GregT
    Commented Apr 18, 2018 at 9:34
  • 1
    $\begingroup$ Isn't it the same as $\mathrm{1,2,3,4,5,}\cdots$ is less than $\mathrm{100}$ so surely all numbers are less than $\mathrm{100}$ $\endgroup$ Commented Aug 20, 2021 at 5:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .