Why the Cautionary Tales Supplied by Richard Guy’s Strong Law of Small Numbers

Should not be Overstated By Doron ZEILBERGER

For Jonathan Borwein (1951-2016) z”l and Richard Guy (b. Sept. 30, 1916) y”laa

One of the challenges to the reliability of results obtained by experimental, empirical, non-rigorous, mathematics, is Richard Guy’s Strong Law of Small Numbers. In two classical articles [G1][G2], he gave many examples of pairs of sequences that are equal for quite a few initial values, but eventually differ. Before him, Charles Babbage [B] has already discussed numerous examples, and recalled how Fermat was fooled by 2^{2^{n}} + 1 and Euler ([Eu]) was almost fooled to believe that the central trinomial coefficients are the product of consecutive Fibonacci numbers.

But in all these examples, the sequences only agree for a moderate number of terms. As shown by David Boyd[Bo] and David G. Cantor[Ca], so-called Pisot sequences provide much more dramatic examples of Richard Guy’s Strong Law of Small Numbers.

In a recent article, joint with Shalosh B. Ekhad and Neil Sloane ([ESZ]) (and dedicated to Richard Guy) these Pisot sequences were studied and even more dramatic examples were found. This last article inspired yet more dramatic examples by Tomás Oliveira e Silva ([S]).

As already pointed out in [ESZ], the most striking example is entry A078608 in [OEIS], where there are two sequences which agree for all n from 1 to 777451915729367 but differ at 777451915729368.

Unfortunately, these examples serve as ‘weapons’ in the propaganda efforts of rigorists, fanatical, ‘purists’, who see truth as black and white, and claim that you can’t guarantee the truth of a statement no matter how many special cases you have checked. They are correct sometimes, of course (see the many examples of Guy’s Strong of Law Numbers), but definitely not always, and, as I hope to show, usually not. Indeed one of the challenges to the foundation of Experimental Mathematics, expressed eloquently by our beloved guru, Jon Borwein, who sadly passed away two months ago, is to explain away these cautionary tales, and learning when to trust empirical results and when to doubt them. This is an important challenge, since notwithstanding old-guard conservative purists (unfortunately still the vast majority of currently living mathematicians), future mathematics will become experimental and empirical, and only a tiny fraction of results will be rigorizably provable by water-tight logical old-time standards.

In this article I will try to make a modest beginning in this demarcation.

Two parodies of the purist cliché “you can’t trust a statement, no matter how many (finite) cases you have checked”

Parody 1: For all n > 0

∑_{i=1}^{n} i = \frac{n(n + 1)}{2} + ∏_{i=1}^{10^{1000000000000000000}}(n − i) .

Empirical Proof: True for 0 < n ≤ 10^{1000000000000000000} (check!), hence true for all n.

Debunking: The left side is an extremely simple object, while the right side is extremely complicated, it is a category error to compare them.

Parody 2: For all n > 0

\frac{n}{10^{1000000000000000000}} < 1 .

Empirical Proof: True for 0 < n < 10^{1000000000000000000} (check!), hence true for all n.

Debunking: This is an inequality, and “empirical proofs” are useless for them.

Beware of “Identities” disguised as Inequalities

There are many classes of identities, A(n) = B(n), that I call ansatzes (see [Z]), where an N_{0}- principle applies. By a quick look at the format of the two sides, one can easily determine an a-priori integer such that checking them for the first N_{0} values constitutes a fully-rigorous proof. The simplest example is the polynomial ansatz. If A(n) and B(n) are two polynomials, given, say, as determinants of large matrices with polynomial entries. In this case N_{0} = max(deg(A), deg(B))+1, since the difference A(n)−B(n) is a polynomial of degree ≤ N_{0} −1 and if it vanishes at N_{0} distinct values, it is identically zero.

Other, less obvious, cases are the Schützenberger ansatz and the holonomic ansatz (see [Z]).

There are many examples of articles (that I will not name, out of politeness), still being published today, in quite a few journals (Journal of Integer Sequences, of course, but even more “prestigious” journals) that contain utterly trivial results, of the same ‘epistemological stature’ as the identity 3 + 5 = 4 + 4, for which the N_{0} principle applies. There are also other ansatzes, for which there is not yet ‘an N_{0} principle’, but there is very likely to be one in the future, and empirical verification for finitely (often not so many) special cases gives a sure proof that they are correct, in the level of certainty held in the physical “hard” sciences.

But one should be on one’s guard when using the pernicious, artificial, operation of ”floor”, ⌊.⌋, x → ⌊x⌋, the integer part of a real number n.

When one defines

n := ⌊x⌋ ,

this is really saying that

n ≤ x < n + 1 ,

so any “identities” involving sequences (like the Pisot sequences studied in [ESZ]), and OEIS sequence A078608 mentioned above that involve ⌊.⌋ are really inequalities in disguise, and as the second parody above illustrates so well, one can’t ‘jump to conclusions’ whenever inequalities are present.

For example, in [ESZ] it was shown that Pisot sequence E(30, 989) (defined by a_{0} = 30, a_{1} = 989, and for n > 1 a_{n} := ⌊\frac{a_{n−1}^{2}}{a_{n−2}} + \frac{1}{2}⌋, satisfies the recurrence

a_{n} = 33a_{n−1} − 2a_{n−2} + 30a_{n−3} − 11a_{n−4} ,

for 4 ≤ n ≤ 15888 but fails for n = 15889.

Defining b_{n} to be the (unique) sequence satisfying the linear recurrence b_{n} = 33b_{n−1} − 2b_{n−2} + 30b_{n−3} − 11b_{n−4}, subject to the initial conditions b_{0} = 30, b_{1} = 989, b_{2} = 32604, b_{3} = 1074844, we have that a_{n} = b_{n} holds for 4 ≤ n ≤ 15888, but fails for n = 15889.

If you apply the analysis in [ESZ] to this recurrence, then it turns out that the “identity” b_{n} = a_{n} holds as long as,

0.2751394860 · (1.00003759711047)^{n} < \frac{1}{2} .

Taking logarithms

(0.00003759629325) · n < 0.5973299074 ,

this is true for n ≤ 15888 but fails later. But this is exactly like the second parody above. In other words the identity a_{n} = b_{n} is not a genuine identity, but because of the pernicious ‘integer part’ operation ⌊.⌋ is really an inequality in disguise, and the ‘empirical approach’ fails miserably for these.

Note that the trump card of anti-empiricists, A078608 in [OEIS], also involves the “integer part” operation! The Skewes number also comes to mind, and indeed it involves an inequality valid for many values, but that ultimately fails.

Conclusion

Richard Guy’s many examples of the Strong Law of Small Numbers should be studied carefully, and be used to develop a sane methodology of empirical mathematics, and to form a test of demarcation of when checking an identity for many special cases provides overwhelming evidence (proof in the everyday sense of the word), and when such empirical evidence should not be trusted. The two parodies above are but two instances. We should look for many more.

At any rate, we, experimental mathematicians, should not be intimidated by narrow-minded fanatical purists, who flag these examples to claim that ‘any mathematical statement should not be trusted unless proved by traditional rigorous means’. If we do, we should never drive a car, or even walk, because there are so many examples of people who were killed in car (or even walking) accidents. If I can convince myself that the statement is true with probability > 1 − 10^{−100}, then this is proof enough for me!

References

[Ba] Charles Babbage, Of Induction, typeset and edited by Martin Fagereng Johansen

http://martinfjohansen.com/ofinduction/ofinduction-2013-11-11-firstdraft.pdf .

[Bo] David W. Boyd, Linear recurrence relations for some generalized Pisot sequences, Advances in Number Theory ( Kingston ON, 1991) 333-340, Oxford Sci. Publ., Oxford.

[Ca] David G. Cantor, Investigation of T-numbers and E-sequences., in: “Computers in Number Theory”, ed. AOL Atkins and BJ Birch, Acad. Press, NY (1971); pp. 137-140.

[ESZ] Shalosh B. Ekhad, N. J. A. Sloane and Doron Zeilberger, Automated Proof (or Disproof) of Linear Recurrences Satisfied by Pisot Sequences, Personal Journal of Shalosh B. Ekhad and Doron

Zeilberger, posted Sept. 18, 2016. http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/pisot.html.
Also https://arxiv.org/abs/1609.05570 .

[Eu] Leonhard Euler Exemplum Memorabile Inductionis Fallacis , Opera Omnia, Series Prima,15 (1911), 50-69, Teubner. Leipzig, Germany.

[G1] Richard K. Guy, The strong law of small numbers, American Mathematical Monthly 95 (1988), 697-712.

[G2] Richard K. Guy, The second strong law of small numbers, Mathematics Magazine 63 (1990), 3-20.

[OEIS] The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

[S] Tomás Oliveira e Silva, Extensive Pisot Data by Tomás Oliveira e Silva,

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/pisotFeedbackTos.html .

[Z] Doron Zeilberger, An Enquiry Concerning Human (and Computer!) [Mathematical] Understanding, in: C.S. Calude, ed., “Randomness and Complexity, from Leibniz to Chaitin” World Scientific, Singapore, 2007, pp. 383-410. Available from

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/enquiry.html .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA;

DoronZeil at gmail dot com ; http://www.math.rutgers.edu/~zeilberg/ .

Exclusively published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

(http://www.math.rutgers.edu/~zeilberg/pj.html) .

Sept. 30, 2016