Examples of patterns that eventually fail

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 14

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.

Answer 15

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.

Answer 16

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

Answer 17

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.

Answer 18

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

Answer 19

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.

Answer 20

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.

Answer 21

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

Answer 22

I understand this observation may be child's play for most people here, but i believe it would be interesting for people with little background. To be precise, i just want to leave an observation concerning the idea that "interesting patterns must always continue", mainly because i think it is simple and didactic:

It is a direct consequence of the construction of Lagrange polynomials that, given $a_1, \dots a_n \in \mathbb{R}$ (that can be understood as the "first $n$ terms of a "pattern"), for each $a \in \mathbb{R}$ there exists a polynomial $f$ such that $f\left ( i \right ) = a_i$ and $f\left ( n+1 \right ) = a$. This gives an easy way to show the falsehood of the idea that "interesting patterns must always continue". For example, one could take the numbers 1, 2, 4, 8, 16, 32 and then 65 instead of 64, and with the consequence mentioned give a polynomial such that gives a pattern, but not the one expected. If you want a pattern true for a large number of small cases, but eventually false, the same example can be taken.

A broader result would be: Let $K$ be a field of characteristic zero, $a_1, \dots a_n \in K$.Then, for each $a \in K$ there exists $f \in K\left [ x \right ]$ such that $f\left ( i \right )=a_i$ and $f\left ( n+1 \right )=a$.

Answer 23

Given that nobody has mentioned it yet, Euler conjectured that Mutually Orthogonal Latin Squares (MOLS) of order $n$ do not exist for all $n = 4k+2$, based on the observation they do not exist for $n=2$ and the fact that he could not find one of order 6. Fairly straightforward constructions existed for non $4k+2$ orders. Gaston Tarry in 1901 proved by exhaustion that none exists of order 6, and Euler's conjecture stood until the 1950s when counterexamples of order 10 and 22 were found. It was finally proven that they do exist for all $n = 4k + 2 \geq 10$ in 1959, against the intuition of one of the greatest mathematicians of all time.

Answer 24

If one who has a 10 digit calculator, sees the value of $e$ as $$ 2.7\color{red}{18281828}$$ but if one checks in a more powerful computer or in OEIS then $$ e = 2.7\color{red}{18281828}45904...$$

Clearly the pattern fails.

Answer 25

\begin{array}{|c|c|} \hline \text{Number}& \text{Is prime} \\ \hline 91 & \color{red}{\text{False}} \\ \hline 9901 & \color{blue}{\text{True}} \\ \hline 999001 & \color{red}{\text{False}} \\ \hline 99990001 & \color{blue}{\text{True}} \\ \hline 9999900001 & \color{red}{\text{False}} \\ \hline 999999000001 & \color{blue}{\text{True}} \\ \hline 99999990000001 & \color{red}{\text{False}} \\ \hline 9999999900000001 & \color{blue}{\text{True}} \\ \hline 999999999000000001 & \color{red}{\text{False}} \\ \hline \end{array}

Can you guess if $99999999990000000001$, the next in the sequence, is a prime number? As it turns out, it is not! And it seems that all the next terms are not prime too.