16
$\begingroup$

Suppose that I want to show a student that empirical evidence in mathematics is not enough and we do need proofs, what kind of examples can I use?

By empirical evidence, I mean that (most of the time) you cannot simply check the statement $S(n)$ for $n \in \{1,\dots, 10^9\}$ and conclude it's true for all $n \in \mathbb N$.

|improve this question
$\endgroup$

12 Answers 12

29
$\begingroup$

There are some collections of such examples at sister sites:

One rather simple example that can be checked with a calculator is the conjecture by Fermat, that all numbers of the form $$2^{2^n}+1, \qquad n \in \mathbb N_0$$ are prime.

In fact,

  • $2^{2^0} +1 = 3$ is prime
  • $2^{2^1} +1 = 5$ is prime
  • $2^{2^2} +1 = 17$ is prime
  • $2^{2^3} +1 = 257$ is prime
  • $2^{2^4} +1 = 65537$ is prime
  • $2^{2^5} +1 = 4294967297$ is not prime: $4294967297 = 641 \cdot 6700417$

So the original conjecture is clearly false, but it took nearly 100 years to find the counterexample. All following Fermat numbers appear to be composite, but this is an open problem.

|improve this answer
$\endgroup$
  • 4
    $\begingroup$ Why did it take nearly 100 years to come up with a counterexample when the counterexample is the fifth exponent (5) that a person tries. It's hard to imagine that no one tried with progressively larger exponents starting from 0 five times to see whether this conjecture was true at least five times, with easiest numbers available, 0 to 5. Are you essentially saying it took nearly a hundred years to find 4294967297 is not a prime number? $\endgroup$ – Zebrafish May 21 at 10:22
  • 22
    $\begingroup$ @Zebrafish : if you think it's easy, try calculating it yourself. Without a calculator. On a vellum. With a goose feather you have to dip into ink every few seconds. $\endgroup$ – vsz May 21 at 12:23
  • 4
    $\begingroup$ Many years ago I calculated up to 2^127 by hand. Granted, this was in a well-lit room with pencil and paper, but I suspect those obstacles could be overcome by someone sufficiently dedicated (or bored). On the other hand, showing that it’s composite seems like it would be much harder. $\endgroup$ – alex_d May 21 at 17:41
  • 4
    $\begingroup$ @vsz While it's certainly a very monotonous task that would probably take a day or two for one person to accomplish, there have been much more arduous computations carried out by hand even in Fermat's time (for example this contemporary book has over 190 pages of trigonometry tables) $\endgroup$ – SamYonnou May 21 at 21:28
  • 4
    $\begingroup$ @Zebrafish aside from Fermat nobody was seriously interested in number theory from the early 1600s until Euler came along around 100 years later. Fermat was worried at the end of his life that his work would be forgotten. When an area of math is obscure (calling number theory an "area of math" in Fermat's time is too generous; Fermat just called it "numbers") and Fermat's letters were scattered around Europe, it's surprising that you'd think its surprising that nobody between Fermat and Euler would really care about testing primality of $2^{2^5}+1$. $\endgroup$ – KCd May 22 at 0:40
19
$\begingroup$

Strangely, just this morning I asked Wolfram|Alpha to compute the sum $$\sum_{n=1}^{\infty}{\frac{1}{n\sin(n)}}$$ and it returned the approximate value of $-0.863507$. I asked it to "show more digits", and it returned a new approximation:

$-94.377284731050845020943145217217734512865979242824685504875914407196948018$

I was trying to illustrate a series for which convergence (or divergence) is difficult to determine and was treated to some very different approximations. Note that Wolfram did not tell whether the series converges.

|improve this answer
$\endgroup$
  • 7
    $\begingroup$ FWIW: You can see in MSE 665776 that the sequence $\frac{1}{n \sin(n)}$ does not converge; in particular, the sequence does not converge to $0$. So, the series described here does not converge. $\endgroup$ – Benjamin Dickman May 21 at 3:39
  • 1
    $\begingroup$ Nice find. I knew I had seen a proof of that at one time, but I couldn't come up with an argument about how frequently n gets close to a multiple of $\pi$. $\endgroup$ – Nick C May 21 at 5:05
  • $\begingroup$ Among experts, it's well-known that WA gives lots of Wrong Answers for limit questions, sometimes claiming it converges when it actually diverges (as in your example) or vice versa, and it is trivial to generate such examples. So while I think your example is a great piece of evidence for not trusting WA (thanks for that!), it is not a good example of misleading empirical evidence since there is simply no empirical evidence to begin with... $\endgroup$ – user21820 Jun 13 at 9:56
  • $\begingroup$ @user21820 That would be a perfect reason to downvote this answer. Perhaps I should have just made it a comment instead of an answer. $\endgroup$ – Nick C Jun 13 at 20:37
  • $\begingroup$ Yea it's not an answer, but I didn't feel like downvoting or flagging because I think too few people know the truth about WA, and last time whenever I posted a counter-example on Math SE someone would go and tweak the algorithm simply to give the right answer to the counter-example, so I stopped posting counter-examples. I wouldn't be surprised if within a few months someone does that to yours too, but that's just too bad haha.. $\endgroup$ – user21820 Jun 14 at 1:07
6
$\begingroup$

There's a great paper out there called "The Strong Law of Small Numbers", by Richard K Guy, which provides numerous examples of misleading patterns. A PDF copy can be found here: https://www.ime.usp.br/~rbrito/docs/2322249.pdf

The YouTube channel "Numberphile" (if you aren't already a subscriber, which you should be) has a video by the same name that's also worth a look. It's where I first learned about the paper.

On a personal note, I remember stumbling across Guy's Example 8 myself in a different form (very simply: construct a list starting with 0, ending with 1, and containing all unique fractions between the two where the denominator is $\leq n$. Now count the members of the list. You'll find that $n=1$ produces $2$, $n=2\rightarrow3$, $n=3\rightarrow5$, $n=4\rightarrow7...$) The sense of being on to something weird and exciting and possibly new, then suddenly seeing it all fall apart was something I'll never forget. Finding out it had been written up in a paper twenty-plus years ago was the cherry on the sundae, for sure.

|improve this answer
$\endgroup$
5
$\begingroup$

There is an old joke describing how various scientific disciplines "prove" that all odd numbers are prime. The part for mathematicians goes

1 is a special case, 3 is prime, 5 is prime, 7 is prime, the proof by induction is left to the reader.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ That's silly. The old Engineer, Physicist, Mathematician joke about black sheep in Scotland is much better. (Punchline: Mathematician: "Gentlemen, all we know is that in the whole of Scotland, there exists one sheep, one side of which is black"). $\endgroup$ – nigel222 May 21 at 9:51
  • 4
    $\begingroup$ @nigel222, at least one sheep, at least one side $\endgroup$ – Joel Reyes Noche May 21 at 14:07
  • 2
    $\begingroup$ @nigel222, the physicist would go "3 is prime, 5 is prime, 7 is prime, instrument error, 11 is prime, 13 is prime." The programmer says "1 is prime, 1 is prime, 1 is prime, ..." $\endgroup$ – o.m. May 21 at 14:34
  • 1
    $\begingroup$ This should be a comment. $\endgroup$ – llllllllllllllllllllllllllllll May 21 at 14:54
  • 1
    $\begingroup$ @Paracosmiste, why? It is an extremely simple example. It works for 3 steps to fail at the 4th. $\endgroup$ – o.m. May 21 at 14:59
5
$\begingroup$

The Miller-Rabin test may be a good example. It identifies "industrial strength primes," numbers which are strongly indicated to be prime through testing, but have not actually been proven to be prime. It is based off of the proof that $a^d \equiv 1 (mod\;p)$ for all prime numbers. The test flips that around into its contrapositive, and explores the idea that if we look for an $a$ which does not satisfy that equation, then we have found a "witness" which shows that $p$ is not prime. It can be shown that all composite numbers have at least one witness, but a simple algorithm for determining it has never been found. Instead, we test many $a$ and, if we find no witnesses, then we say $p$ is an "industrual strength prime" because we took a good swing at it and failed to disprove its primality.

As it turns out, testing small values of a is enormously successful. So successful that you might make the assumption that testing just $a=2$ and $a=3$ is sufficient to prove a number is prime. And you'd be right, so long as the number is smaller than 1,373,653, which is the first point where that test suggests a composite number is prime.

Maple's isprime() function relies on this test. It tests $a=2$, $a=3$, $a=5$, $a=7$, and $a=11$. This turns out to be a very fast and enormously effective test. But there are numbers which fail this. In fact, one mathematician identified a particular 397-bit number which passes all tests from $a=2$ through $a=307$, and yet is composite.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ The significance of the Miller--Rabin test is not that each composite odd $n > 1$ has at least one witness for this test, but that it has a lot of witnesses for this test: at least 75 percent of integers from 1 to $n-1$ are witnesses to the compositeness of $n$ in the Miller--Rabin test. Fermat's little theorem as a compositeness test (is $a^{n-1} \not\equiv 1 \bmod n$ for some $a$ from 1 to $n-1$?) has at least one witness when $n$ is composite, such as any factor of $n$ strictly between $1$ and $n-1$, but this does not make the Fermat test a good example because of Carmichael numbers. $\endgroup$ – KCd May 22 at 0:46
  • $\begingroup$ A simple algorithm for making the Miller--Rabin test deterministic has been known since the 1980s if you assume GRH for Dirichlet $L$-functions: an odd $n > 1$ is prime if and only if it has no witness for the Miller--Rabin test among the positive integers up to $2(\log n)^2$ (or $3(\log n)^2$, depending on how the test is described). $\endgroup$ – KCd May 22 at 0:49
  • $\begingroup$ It's a pity your answer has so few upvotes, when it is such a good example. $\endgroup$ – user21820 Jun 13 at 10:01
4
$\begingroup$

There is a classic undergrad example (apparently going back to Euler) still missing in this list:

$$n^2+n+41 \text{ is prime}$$

which is true for all $n<40$ but fails at $n=40$.

|improve this answer
$\endgroup$
3
$\begingroup$

Here is a straightforward example that knowing the first $k$ terms (no matter how big $k$ is) of a sequence $(x_n)$ tells you very little about the term $x_{k+1}$: I can generate a sequence whose first $k$ terms are $1,2,\dots,k$ but whose $(k+1)^{{\rm st}}$ term is an arbitrary $m$ of my choosing. For the given $k$, let $x_n = n + \frac {m-n}{k!}(n-1)(n-2)\dots(n-k)$.

Now, for any $n$ up to $k$, a factor in the product is $0$, forcing the entire product to be $0$, leaving $x_n=n$. Meanwhile, at $n=k+1$, the product $(k+1-1)\dots(k+1-k)=k!$, and straightforward arithmetic shows $x_{k+1}=m$.

Much more in fact is true. Linear algebra can be used to show, given completely arbitrary first terms $a_1,\dots,a_{k+1}\in\mathbb R$, there is a sequence $(x_n)$ for which $x_1=a_1,\dots,x_{k+1}=a_{k+1}$, and the generic term $x_n$ of $(x_n)$ is given as a polynomial in $n$ with degree at most $k$. (Indeed, the terms don't even need to be the ``first'' terms, we just need to know which terms they are.)

Without knowing something more about a sequence of real numbers than just ``these are some of the terms'', nothing of substance can be concluded about the sequence.

Edit (30 May 2019): Many standardized tests have questions along the lines of ``If a sequence starts with the numbers $1$, $2$, $4$, $8$, what is the next term in the sequence?" then proceeds to have a multiple choice answer, providing four numbers/answers. One main point behind this example is that all four answers are correct.

|improve this answer
$\endgroup$
2
$\begingroup$

The Pell equation $x^2-Dy^2=1$ (where $x$ and $y$ are positive integers) admits solutions if the natural number $D$ is not a square number. But for $D=61$ the smallest solution is astonishingly great: you can derive an example from this fact. https://proofwiki.org/wiki/Pell%27s_Equation/Examples/61

|improve this answer
$\endgroup$
2
$\begingroup$

Try representability by the sum of three cubes, $$ x^3 + y^3 + z^3 = k \text{.} $$

Early computer search paper, that turned up no new representable $k$s.: Gardiner, V.L., R.B. Lazarus, and P.R. Stein, Solutions of the Diophantine Equation $x^3 + y^3 = z^3 - d$, 1964. In this paper, no representations are found for $d = k = 30$ and $d = k = 33$ (and several more $d = k < 1000$). Contains the lines "Nevertheless, it is in our opinion rather unlikely that all the missing $|d|$'s will turn out to be expressible as sums of three cubes. It would be of interest to attempt a proof that, say, 30 cannot be so represented."

Recent paper: Huisman, S., Newer sums of three cubes, 2016. This paper finds that $33$ is the least $k$ with no known representation, so a representation for $k = 30$ was found in the interim.

Recent video: Haran, B. and A. Booker, 42 is the new 33 - Numberphile, 12 March 2019. A much larger empirical search found a representation for $k = 33$, leaving $k = 42$ as the least $k$ without a known representation.

Moral: empirical searches keep being inadequate.

|improve this answer
$\endgroup$
  • $\begingroup$ Is the equation in your first paper's title equivalent to the equation above? It looks to me like some negative signs are required to group the three cubes (but not on all of them). $\endgroup$ – jpmc26 May 23 at 9:05
  • $\begingroup$ @jpmc26 : $(-x)^3 + (-y)^3 + z^3 = d$; $x$, $y$, and $z$ can absorb needed sign changes because the variables are not assumed positive. $\endgroup$ – Eric Towers May 23 at 9:47
  • $\begingroup$ @EricTowers In case you didn't know, the Sep. $6$, $2019$ ScienceDaily article Sum of three cubes for 42 finally solved -- using real life planetary computer says an answer for $42$ was finally found, but it "took over a million hours of calculating to prove". As such, the problem has now been solved for all $k$ from $1$ to $100$. $\endgroup$ – John Omielan Nov 11 at 5:01
2
$\begingroup$

XKCD compiled a list of approximations several years back:

Many are just funny trivia, but you could use most of them as examples of the limits of empirical evidence, because empirical estimations using these formulas would seem to be strong evidence that they are correct, when mathematically they are complete nonsense.

|improve this answer
$\endgroup$
2
$\begingroup$

If you keep a running tally of primes of the form $4k+1$ vs $4k+3$, it seems like the latter are always at least as numerous. But it was eventually shown each type takes the lead infinitely many times; it's just you have to get into huge numbers before the first lead for $4k+1$.

|improve this answer
$\endgroup$
1
$\begingroup$

If you are open to other fields that strongly rely on mathematics, you can use the Rayleigh-Jeans catastrophe as an example:

The term "ultraviolet catastrophe" was first used in 1911 by Paul Ehrenfest, but the concept originated with the 1900 statistical derivation of the Rayleigh–Jeans law. The phrase refers to the fact that the Rayleigh–Jeans law accurately predicts experimental results at radiative frequencies below 105 GHz, but begins to diverge with empirical observations as these frequencies reach the ultraviolet region of the electromagnetic spectrum.1 Since the first appearance of the term, it has also been used for other predictions of a similar nature, as in quantum electrodynamics and such cases as ultraviolet divergence.

The beginning times of quantum physics is full of such examples. This particular one was solved by Max Planck and physics has never been the same since then.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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