%collatz.tex:
%%a Plain TeX file by Doron Zeilberger (x pages)
%begin macros
\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\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
\bf
\centerline
{
Teaching the Computer how to Discover(!) and then Prove(!!) (all by Itself(!!!))
}
\centerline
{
Analogs of Collatz's Notorious 3x+1 Conjecture
}
\rm
\bigskip
\centerline{ {\it
Doron
ZEILBERGER}\footnote{$^1$}
{\eightrm \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg} .
First version: March 23, 2009.
Accompanied by Maple package {\eighttt LADAS}
downloadable from
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/collatz.html}, where one
can also find (very interesting!) output, consisting of 144 computer-generated theorems and proofs.
Supported in part by the NSF.
}
}
{\bf Mathematics: an Experimental Science}
In spite of their exponential growth, computer-assisted and especially computer-generated mathematical research
are still in their infancy. One approach is that of {\it formal proofs} using the {\it axiomatic method}.
This method is based on the {\it myth}, that goes back to Euclid,
that mathematics is a {\it deductive} science, where one starts with
a bunch of axioms,
(initially supposed to be ``self-evident'', but later conceded as true-by-fiat)
and then uses {\it rules of deduction},
and step-by-step, arrives at (seemingly) non-trivial results.
Of course, mathematics {\it could} be presented that way, and unfortunately, often {\it is}.
But that is not how it is {\it discovered}. Pretending that the axiomatic method is how
mathematics should be done, and trying to indoctrinate poor computers to do it that way,
is a highly {\it inefficient} use of computers' time.
Deep inside, mathematics is, or at least should be, an {\it inductive} science. How do human mathematicians
come up with such amazing conjectures? By experimenting! How do they come up with such amazing
proofs? By experimenting!, and {\bf not} by combining axioms.
For many results in mathematics, one only needs one non-trivial ``axiom'', that of Peano's
``axiom'' of induction:
$$
P(0) \,\,\, \& \, \, \, ( P(n) \Rightarrow P(n+1)) \, \, \Rightarrow \, \,\, \, P(n) \quad for \quad all \quad n \geq 0 \quad .
$$
All we have to do then is to have the computer prove (all by itself) $P(0)$ (an a priori routine fact), and
the not-a-priori routine $P(n) \Rightarrow P(n+1)$, but, with the help of {\it symbolic computation},
treating $n$ as a {\it symbolic integer} (which is {\bf one} object) rather than as a {\it variable}
(ranging over positive integers), we might hope to have the computer do it for us.
Often one tries to prove a statement by induction, but {\it fails}. In that case one has
to {\it try again}. If $P(n)$ is inadequate to prove $P(n+1)$, perhaps we need
another statement $Q(n)$, such that $Q(n)$ and $P(n)$ imply $P(n+1)$. Alas, now we also
have to prove that $P(n)$ and $Q(n)$ imply $Q(n+1)$. This may be easier-said-than-done, and
we may be forced to introduce yet-another statement $R(n)$. If we want to avoid a
{\it Ponzi scheme}, we need this process to finally halt, but if we can train
our computer how to do it, it will be able to keep trying, before halting or giving up,
for a much longer time.
Human mathematicians also do {\it symbol crunching}, most of which is purely routine, and
that is much better delegated to computers.
{\bf Research is one percent Inspiration and ninety nine percent Perspiration}
At this time of writing, humans are still needed to find {\it ideas} and {\it strategies}
for generating conjectures, and for proving these conjectures. But once the human
has some ideas, it is much more efficient to teach the computer these ideas, and let the
computer search for {\it conjectures}, and most impressively, {\it proofs}, all by itself!
In this case-study in computer-generated mathematics, I will
describe how I read
{\it very carefully} a beautiful mathematical paper [AGKL],
written by four {\it brilliant} human
beings: Ed Grove and Gerry Ladas, and their (at the time)
respective students, Candy Kent
and Amal Amleh. I then extracted the {\it ideas},
looked at the {\it structure} of the proofs,
but ignored the details. I then {\it taught} (programmed) my beloved
computer to execute
these ideas, and since it is much more patient than a human being, it was able
to prove many more results.
A very preliminary output can be viewed at the webpage of this
article
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/collatz.html} ,
where there are 144 computer-generated results, that include those proved in [AGKL].
The computer did {\it all} the phases of mathematical research all by {\bf itself}:
conjecturing theorems, conjecturing proofs, and finally, verifying that the conjectured proofs are correct.
{\bf Background: The 3x+1 problem}
Mathematics abounds with easy-to-state yet (apparently) impossible-to-prove
statements, for example the Goldbach and twin-prime conjectures, but none
of them rivals the simplicity of statement, and most probably, difficulty
of proof, of the Collatz infamous 3x+1 conjecture, so beautifully exposited
in Jeff Lagarias' [L] masterpiece. I am sure that all the readers know it,
but for the sake of completeness, let me state it anyway.
{\bf The Collatz 3x+1 Problem}
Let $x(n), (n \geq 0$), be a sequence of positive integers defined by the
{\it first-order} recurrence
$$
x(n+1) = \cases{
{{x(n)} \over {2}} ,& if \quad $x(n)$ \quad is \quad even ;\cr
{{3x(n)+1} \over {2}} ,& if \quad $x(n)$ \quad is \quad odd .\cr} \quad,
$$
subject to the {\it initial condition} $x(0)=x_0$. Then
for {\it every} positive integer $x_0$, the sequence is eventually
periodic with the trivial cycle $(2,1)$.
Paul Erd\H{o}s claimed that mathematics is not yet ready for solving such
problems. I strongly believe that it very soon will be, thanks to the
emergence of computer-assisted and computer-generated methods, that
eventually would be able to {\it rigorously} prove such statements,
for {\it all} $x_0 < \infty$,
as opposed to just numerically verifying it for $x_0