%small.tex:  
%Plain TeX
%TeXShop, compile with XeTeX
%begin macros

\def\mod{\rm mod}
\def\Z{\bf Z}
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\W{{\cal W}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}


%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{
\bf
Why the Cautionary Tales Supplied by Richard Guy's Strong Law of Small Numbers 
}
\centerline
{
\bf Should not be Overstated
}

\centerline
{\it By  Doron ZEILBERGER}

{\it 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 {\it 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\'as Oliveira e Silva ([S]).

As already pointed out in [ESZ], the most striking example is entry {\bf 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 {\it 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 {\it sometimes}, of course (see the many examples of
Guy's Strong of Law Numbers), but definitely not {\it always}, and, as I hope to show, {\bf 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 {\it demarcation}.


{\bf Two parodies of the purist clich\'e ``you can't trust a statement,  no matter how many (finite) cases  you have checked''}

{\bf Parody 1}: For all $n>0$
$$
\sum_{i=1}^{n} i \, = \, \frac{n(n+1)}{2} + \prod_{i=1}^{10^{1000000000000000000}} (n-i) \quad .
$$

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

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

{\bf Parody 2}: For all $n>0$
$$
\frac{n}{10^{1000000000000000000}} < 1 \quad .
$$

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

{\bf Debunking}: This is an {\bf inequality}, and ``empirical proofs'' are useless for them.

{\bf Beware of ``Identities" disguised as Inequalities}

There are many classes of identities, $A(n)=B(n)$, that I call {\it 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 {\it a-priori} integer such that checking them for the first $N_0$ values constitutes
a {\it fully-rigorous} proof. The simplest example is the {\it 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 $\leq N_0-1$ and
if it vanishes at $N_0$ distinct values, it is identically zero.

Other, less obvious, cases are the {\it Sch\"utzenberger ansatz} and the {\it 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 {\it 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 {\it 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 {\bf pernicious}, artificial, operation of "floor", $\lfloor . \rfloor$,
$x \rightarrow \lfloor x \rfloor $, the {\it integer part} of a real number $n$.

When one {\it defines}

$$
n :=\lfloor x \rfloor \quad,
$$

this is really saying that
$$
n \leq x < n+1 \quad ,
$$
so any ``identities'' involving sequences (like the Pisot sequences studied in [ESZ]), and OEIS sequence  {\bf A078608} mentioned above
that involve $\lfloor . \rfloor$ 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:= \lfloor \frac{ a_{n-1}^2}{a_{n-2}} +\frac{1}{2} \rfloor$,
satisfies the recurrence
$$
a_n=33a_{n-1}-2a_{n-2}+30a_{n-3}-11a_{n-4} \quad ,
$$
for $4 \leq n \leq 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 \leq n \leq 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\cdot (1.00003759711047)^n < \frac{1}{2} \quad .
$$
Taking logarithms
$$
(0.00003759629325) \cdot n <  0.5973299074 \quad,
$$
this is true for $n \leq 15888$ but fails later.
But this is {\bf exactly} like the second parody above. In other words the {\it identity} $a_n=b_n$ is not
a genuine identity, but because of the pernicious `integer part' operation $\lfloor . \rfloor$ is really
an {\bf inequality in disguise}, and the `empirical approach' fails miserably for these.


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


{\bf Conclusion}

Richard Guy's many examples of the Strong Law of Small Numbers should be studied carefully, and
be used to develop a {\it sane} methodology of empirical mathematics, and to form a test of
{\it 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 {\bf 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!

\vfill\eject

{\bf References}


[Ba] Charles Babbage, {\it Of Induction}, typeset and edited by
Martin Fagereng Johansen \hfill\break
{\tt http://martinfjohansen.com/ofinduction/ofinduction-2013-11-11-firstdraft.pdf} \quad .

[Bo] David W. Boyd, {\it 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, 
{\it 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, {\it Automated Proof (or Disproof) of Linear Recurrences Satisfied by Pisot Sequences},
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, posted Sept. 18, 2016.
{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/pisot.html}. Also {\tt https://arxiv.org/abs/1609.05570} \quad .

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

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

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

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

[S] Tom\'as Oliveira e Silva, {\it Extensive Pisot Data by Tom\'as Oliveira e Silva}, \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/pisotFeedbackTos.html} \quad .

[Z] Doron Zeilberger, {\it 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 \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/enquiry.html} \quad .

\bigskip
\hrule
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA; \hfill \break
DoronZeil at gmail dot com \quad ;  \quad {\tt http://www.math.rutgers.edu/\~{}zeilberg/} \quad .
\bigskip
\hrule
\bigskip
Exclusively published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger  \hfill \break
({\tt http://www.math.rutgers.edu/\~{}zeilberg/pj.html}) \quad .
\bigskip
\hrule
{\bf Sept. 30, 2016}

\end
















