# Examples of patterns that eventually fail

Often, when I attempt to define maths to the nonprofessional, I locate myself battling to encourage them of the relevance and also effect of "proof". I receive feedbacks like: "surely if Collatz holds true approximately $20×2^{58}$, after that it has to constantly be true?" ; and also "the series of variety of sides on a full chart begins $0,1,3,6,10$, so the next term has to be 15 etc"

Granted, this 2nd declaration is much less practically unbalanced than the first given that it is uncomplicated to see the reason that the series have to proceed thus ; however, the declaration was made on a property that comes down to "interesting patterns have to constantly continue".

I attempt to counter this reasoning by developing a ludicrous argument like "the numbers $1,2,3,4,5$ are much less than $100$, so undoubtedly all numbers are", yet this generally falls short to be persuading.

So, exist any kind of instances of non - unimportant patterns that seem real for a lot of tiny instances, yet after that fall short for some bigger instance? An excellent response to this inquiry should:

- be one which can be clarified to the nonprofessional without needing to subject them to a 24 lecture training course of history product, and also
- have as a marginal counterexample an instance which can not (probably) be examined without making use of a computer system

I think problems 1. and also 2. make my inquiry details adequate to have in some feeling a "right" (or at the very least a "not wrong") solution ; yet I would certainly enjoy to make clear if this is not the instance. I intend I'm anticipating a response to originate from number concept, yet can see that locations like chart concept, combinatorics extra usually and also set concept can possibly supply ideal solutions.

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 .

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

Here is an instance connecting to a Diophantine formula. Take into consideration favorable integer remedies of $a^3 + b^3 + c^3 = d^3$. The first couple of primitive remedies all have 2 weird and also 2 also integers, i.e. (3,4,5,6), (1,6,8,9), (3,10,18,19), (7,14,17,20), (4,17,22,25) and also (18,19,21,28). Yet after that the pattern damages down with (11,15,27,29).

A checklist of the tiny remedies goes to http://mathworld.wolfram.com/DiophantineEquation3rdPowers.html

The "Chinese remainder" prime - test:

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

falls short very first time at $n=341$ . That was just one of things that actually made me assuming when I started hobbying with number - concept in an extra significant means

Can a circle be reduced up right into a limited variety of components and also repositioned to create a square? Laczkovich confirmed in 1990 that this can be performed with around $10^{50}$ items.

An excellent resource for this example is "Old and also new unresolved troubles in aircraft geometry and also number concept, " by Klee and also Wagon. The benefit is that none of the troubles make use of greater than math and also geometry, so the instances come to individuals that aren't mathematicians.

Perhaps a little technological, yet I assume you can offer the flavour without the information. It was long thought that the logarithmic indispensable $\operatorname{Li}(x)$ is more than the prime checking function $\pi(x)$ for all $x$, and also calculations validated this for a great deal of "small" (yet by most individuals is criteria rather huge) $x$. It was confirmed to be incorrect in 1914 by J.E. Littlewood, that did not locate a counterexample clearly, yet revealed that have to exist - it is thought to be around $10^{316}$, means outside the series of calculations at the time.

So this instance isn't wonderful, due to the fact that the logarithmic indispensable is rather technological, yet the specifics of $\operatorname{Li}(x)$ aren't that vital, so it is nearly one function being larger than an additional.

Even more information on Wikipedia.

This could be a straightforward instance.

If we etch a circle of distance 1 in a square of side 2, the proportion of the location of the circle to the square is $\frac{\pi}{4}$. You can show that at any time we placed a square variety of circles right into this square, the proportion of the location of the circles to that of the square is (for the straightforward symmetrical setup) once more $\frac{\pi}{4} $. So for 1, 4, 9, 16 circles, this packaging is the most effective we can do.

I had actually erroneously thought, based upon this "obvious" pattern, that the restriction of optimum packagings of circles right into the square did not merge, yet instead remained to fall to this very same proportion every single time a square number was gotten to.

This ends up not to be real, as I found out here.

There are several various other instances, yet this acted as a suggestion for me.

Choose n factors around the area of a circle, and also sign up with every indicate every various other with a line sector. Thinking that no 3 of the line sectors consent, the amount of areas does this divide the circle right into?

There is an instead noticeable pattern, that damages down at n = 6.

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

Heather360 offers the adhering to enjoyable example:

United States head of states chosen in 1840, 1860, 1880, 1900, 1920, 1940, and also 1960 all passed away in workplace, yet Ronald Reagan did not.

Yet the copying is possibly extra along the lines of what you desired. The pattern is not long, yet it is really straightforward and also can be clarified to any person of any kind of background: http://threesixty360.wordpress.com/2008/10/26/one-two-three-four-six-again-and-then-again/

Additionally, given that you began your inquiry without reference to patterns, in itself, yet to the relevance of mathematical evidence, I would certainly indicate the Banach-Tarski paradox. I assume most individuals, specifically non - mathematicians, have problem thinking this outcome, so it is absolutely an instance of mathematical evidence developing a counter - instinctive outcome.

I am sort of partial to the old $n^2 + n + 41$ chestnut, particularly that the expression is prime for all $n$. It fools a horrible great deal of individuals.

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:

- $E(n) =$ number of positive integers less or equal to $n$ that are of even kind.
- $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.

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

The tiniest value of $n$ for which the function $f(n) = 991n^2 + 1$ is an excellent square is

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

On a comparable note, the tiniest value of $n$ such that the function $g(n) = 1,000,099n^2 + 1$ is an excellent square has $1116$ figures.

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

It holds for any kind of number that does not contend the very least $3$ distinctive weird prime variables, which suggests the tiniest counterexample is $3 \cdot 5 \cdot 7 = 105$. So an ignorant basic possibly will not ever before see a counterexample unless they are especially revealed $\phi_{105}$.

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

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

Fermat numbers would certainly be an example. The numbers $F_n = 2^{2^n}+1$ are prime for $n=1,2,3,4$, nonetheless $F_5 = 4,294,967,297 = 641 × 6,700,417$ is not prime. Actually, there are no well-known Fermat tops $F_n$ with $n > 4$.

Unquestionably this isn't difficult to examine by hand, yet the quick increase in $F_n$ makes it factoring such numbers by hand very not practical. I can not visualize any kind of nonprofessional that would certainly fit attempting to variable also a 10 figure number. When it comes to $F_5$, attempting to look for prime variables by strength you would certainly need to examine 115 tops prior to you reach 641.

The influential paper on this is Richard Guy is The Strong Law of Small Numbers Proclaiming "there aren't sufficient handful to fulfill the several needs constructed from them, " it details $35$ patterns that do not turn out. Others have actually increased on the 'regulation of handful' Such as here (and also a couple of even more web links on that particular web page)

A specifically wonderful instance from the 2nd link:

- $\gcd(n^{17}+9, (n+1)^{17}+9)$ appears to constantly be $1$. Actually, if you had your computer system examining this for $n=1, 2, 3, \dots$ together, it would certainly never ever locate a counter - instance. That is due to the fact that the first counter - instance is $$8424432925592889329288197322308900672459420460792433\;.$$

Does Goodstein's Theorem fit the costs?

(By the means, below is a nice applet.)

The inquiry was:

So, exist any kind of instances of non - unimportant patterns that seem real for a lot of tiny instances, yet after that fall short for some bigger instance? An excellent response to this inquiry should:

$(1)$ be one which can be clarified to the nonprofessional without needing to subject them to a $24$ lecture training course of history product, and also

$(2)$ have as a marginal counterexample an instance which can not (probably) be examined without making use of a computer system.

Need $(1)$ is clearly pleased.

Is need $(2)$ is pleased?

In some feeling it is not, due to the fact that a computer system would not aid.

Yet, in an additional feeling, it mores than completely satisfied, due to the fact that, despite having one of the most effective conceivable computer system, the declaration can not be examined. That is, it can not be examined by any kind of estimation, although it just entails enhancement, reproduction and also exponentiation of favorable integers. Yet with a really straightforward idea (that of ordinal), it comes to be virtually unimportant.

To claim it in an additional means: It is really simple to confirm that the noticeable pattern will certainly damage at some point, yet the argument does not offer the least idea concerning *when * it will certainly damage.

So, Goodstein is Theorem is, I assume, a fairly instructional item of maths.

Related questions