%icdea.tex: ```Real' Analysis is a Degenerate Case
%of Discrete analysis"
%a Plain TeX file by Doron Zeilberger (8 pages)
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\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\lheading#1{\bigbreak \noindent {\bf#1}
}
\parindent=0pt
\overfullrule=0in
%end macros
\bf
\centerline
{
``REAL'' ANALYSIS Is A DEGENERATE CASE of DISCRETE ANALYSIS
}
\rm
\bigskip
\centerline{ {\it
Doron ZEILBERGER
}\footnote{$^1$}
{\eightrm \raggedright
Department of Mathematics, Rutgers Univ.,
New Brunswick, NJ 08903, USA.
%\break
{\eighttt zeilberg@math.rutgers.edu} \hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/ .}
Nov. 27, 2001. Supported in part by the NSF.
Transcript of a plenary talk delivered at the International
Conference on Difference Equations and Applications
(ICDEA 2001), Augsburg, Germany, Aug. 1, 2001, 9:00-10:00 a.m.
}
}
{\bf The ICDEA Conferences: An Asymptotically Stable Recurrence}
In one of yesterday's invited talks, Gerry Ladas outlined briefly
the history of the previous conferences, and how successful they were.
I totally agree. But no recursive sequence can exist without
{\it initial conditions}. Hence, special credit and thanks should
go to Saber Elaydi, whose initial idea it was, in 1994.
Well done, Saber!
The current term in this sequence,
$ICDEA_7$, is a huge success, thanks to the
efficient and {\it friendly}
organization of Bernd Aulbach and his gang of young
assistants.
{\bf Discrete Analysis: Yet Another Cinderella Story}
There are
many ways to divide mathematics into {\it two-culture} dichotomies.
An important one is the Discrete vs. the Continuous. Until
almost the end of the 20th century, the continuous culture was
dominant, as can be witnessed by notation.
An important family of Banach spaces of {\it continuous} functions
is denoted by $L^p$ , with a {\it Capital} $L$, while
their discrete analogs are denoted by the lower-case counterpart $l^p$.
A function of a {\it continuous} variable is denoted by $f(x)$, where
the continuous output, $f$, is written at the same level as the
continuous input $x$, but if the input is discrete, then
the function is given the derogatory name {\it sequence}, and
written $a_n$, where the continuous output, $a$, looks down on
the discrete input, $n$.
Indeed, the conventional wisdom, fooled by our misleading
``physical intuition", is that the real world is {\it continuous},
and that discrete models are necessary evils for approximating
the ``real'' world, due to the innate discreteness of the digital
computer.
Ironically, the opposite is true. The
{\bf REAL} REAL WORLDS (Physical and MATHEMATICAL) ARE DISCRETE .
Continuous analysis and geometry are just degenerate approximations
to the discrete world, made necessary by the very limited resources
of the human intellect. While discrete analysis is conceptually
simpler (and truer) than continuous analysis, technically it is
(usually) much more difficult.
Granted,
real geometry and analysis were necessary simplifications to enable
humans to make progress in science and mathematics,
but now that the {\it digital} Messiah has arrived, we can start
to study discrete math in greater depth, and do {\it real}, i.e.
discrete, analysis.
When we watch a movie we have the {\it appearance} of continuity,
but in fact it consists of a discrete sequence of frames. When we
look at a photograph, we have the {\it semblance} of a continuous
image, but it is really a collection of {\it discrete} pixels. On
a more fundamental level, we now know that energy and matter
and probably time and space too, are discrete, as described
so charmingly in Professor Trigiante's invited talk
given in this conference two days ago.
{\bf Don't Worry, the Continuous Heritage is not a Total Waste}
I will show later that while the efforts of Cauchy,
Weierstrass, Dedekind and many others for a `rigorous' foundation
of analysis were misguided, a lot (and perhaps most) of continuous
analysis can be salvaged as a special degenerate case of
``discrete symbolic analysis''.
{\bf My Perhaps Not So Foolish `April Fool's Jokes'}
As Dr. Peter Menacher,
the eloquent and erudite {\it Oberb\"urgermeister} of Augsburg,
said in yesterday's
lovely reception at the magnificent (and mathematically tiled!) City Hall,
Augsburg has seen many royalties, starting with its namesake, Emperor
Augustus. Now each self-respecting king or duke had a {\it court jester},
also known as the {\it fool}. Of course, that `fool' was usually
the least foolish person in the whole kingdom, but his position
enabled him to get away with much more freedom of speech than any other
subject, since it was all `in jest'.
Analogously, my own best ideas, far surpassing anything in my
`serious' papers, are contained in my annual {\it April Fool's}
jokes, sent to my E-correspondents and posted on my website.
This way I can express my `off the wall' ideas without being
considered a crackpot.
For example (2001), the idea of computerizing Tim Gowers's plan for
studying the asymptotics of the Ramsey numbers $R(n,n)$,
published in {\bf Ekhad and Zeilberger's personal journal},
{\tt http://math.rutgers.edu/\Tilde zeilberg/pj.html},
or my idea (1995) for proving the Riemann Hypothesis, also
published there. But the most promising idea is in my
1999 `joke', entitled: `Mathematical Genitalysis: A Powerful
New Combinatorial Theory that Obviates Mathematical Analysis',
that was also published in the `Personal Journal'.
The main thrust of that article was the concept of
`symbolic discretization',
akin to, but much more powerful than,
`numeric discretization'. I believe that this {\it crazy} idea
has a great potential. But, even more important, it suggests
a truly {\it rigorous} and {\it honest} foundation for the whole
of mathematics.
{\bf Towards a FINITE (and hence RIGOROUS) Foundation of Mathematics}
(i) The mathematical (and physical) universe is a huge
(but FINITE) {\bf DIGITAL} computer.
(ii) the traditional real line is a meaningless concept. Instead
the {\it real} {\bf REAL} `line', is neither real, nor a line.
It is a {\it discrete} necklace! In other words $R=hZ_p$, where $p$
is a huge and unknowable (but fixed!) prime number, and $h$ is
a tiny, but {\it not} infinitesimal , `mesh size'.
Hence even the {\it potential infinity} is a meaningless concept.
Since $h$ is so tiny, and $p$ is so large, and both are unknowable,
they should be denoted by symbols, like $h$ and $c$ in physics,
and $\pi$ and $e$ in math. This also explains why traditional
real analysis did so well in modeling nature, the same way that
Newtonian physics approximated nature so well, as long as you
didn't travel too fast, or penetrated with too high energy.
It is probably possible to {\it deconstruct} the whole of traditional
mathematics along finitism, but I doubt whether it is worth the effort.
Let's just redo a few basic definitions.
{\bf The True Derivative}
Leibnitz and Newton defined the derivative by
$$
Df(x)= {{f(x+h)-f(x)} \over {h}} \quad,
$$
where $h$ is {\it infinitesimal}, whatever that means. Then
Cauchy and Weierstrass found a `rigorous' definition:
$$
Df(x)= {{\lim} \atop {h \rightarrow 0}}
{{f(x+h)-f(x)} \over {h}} \quad,
$$
using the notion of {\it limit}, whatever it means. But
the only TRUE definition is:
$$
Df(x) \, := \, {{f(x+h)-f(x)} \over {h}} \quad,
$$
where $h$ is the Fundamental mesh size, a Mathematical Universal
constant, that unlike Planck's constant, we will never know, but
it is very tiny. Since it is so tiny, we keep it as a
{\it symbol}, but remember that it {\it signifies} a fixed constant.
When Einstein discovered General Relativity he already had
the mathematical framework for it, Riemannian Geometry.
Luckily, discrete calculus also already exits, but
there $D=\Delta_h$. (Speaking of $\Delta$, I love the
logo of this conference that is a graphic pun featuring the
finite difference operator $\Delta$ turned into the Pascal triangle mod 2
fractal.)
Let's recall the
{\bf Product Rule}:
$$
D(fg)=f(Dg)+(Df)g+h(Df)(Dg) \quad ,
$$
which implies Leibnitz's rule:
$$
D^n(fg)=\sum_{i+j+r=n}
{{n!} \over {i!j!r!}} (D^{i+r}f) (D^{j+r}g)h^r \quad.
$$
{\it Integration} is {\it not} a `limit' of Riemann sums,
but rather {\it is} a Riemann sum:
$$
\int_a^b f(x) dx :=h \, \cdot \,
\sum_{i=0}^{(b-a)/h} f(a+ih) \quad .
$$
{\bf REAL} (i.e. discrete) analysis is conceptually simpler than
traditional `real' (continuous) analysis, and of course is
much truer. But it is, on the whole,
technically more difficult. Hence
`Naked Brain' humans had no choice but to pursue the latter kind.
{\bf My First Love: DISCRETE Analytic Functions}
These are functions defined on the lattice
$hZ+ihZ$, satisfying:
$$
{{f(m+(1+i)h)-f(m)} \over {(1+i)h-0}}=
{{f(m+ih)-f(m+h)} \over {ih-h}} \quad.
\eqno(Duffin)
$$
In other words, the two ``derivatives" along the two diagonals
of any unit square $\{ m,m+h,m+(1+i)h,m+ih \}$ are the same.
Now $(Duffin)$ can be rewritten as
$$
{{f(m)+f(m+h)} \over {2}} \cdot h+
{{f(m+h)+f(m+h+ih)} \over {2}} \cdot ih+
$$
$$
{{f(m+h+ih)+f(m+ih)} \over {2}} \cdot (-h)+
{{f(m+ih)+f(m)} \over {2}} \cdot (-ih) \, = \, 0 \quad,
$$
which means that the ``integral" of an analytic function
around any fundamental square is zero, and since the
``integral" over any closed simple (discrete) `curve' is a (finite!)
sum of integrals over fundamental squares, we have immediately
both Cauchy's and Morera's theorems!
The theory of Discrete Analytic functions was initiated
by Jacqueline Ferrand-Lelong\footnote{$^2$}{
\eightrm A brilliant mathematician. She was the classmate
of Roger Ap\'ery, and tied with him for first-place,
but unlike Ap\'ery, Ferrand was a {\eighttt tala}
(one of those that {\eighttt von(t a la) messe}).} .
Dick Duffin made it into a full-fledged theory,
and it was further developed by myself
(in my Ph.D. thesis), and several others.
The main stumbling block in the further development
of the theory of Discrete Analytic Functions is the fact
that the property of being discrete-analytic is not
preserved under multiplication. But using
the discrete Leibnitz rule one can express the derivative
of a product, and then the product is ``almost analytic".
So I am sure that the full arsenal of {\it continuous}
complex analysis can be discretized, but the details might be
too complicated for humans.
{\bf Continuous Analysis is a DEGENERATE (not LIMITING)
case of Discrete Symbolic Analysis}
So one should be able to develop a full theory for
discrete analysis, with an {\it arbitrary} mesh-size
$h$. But {\it now} we declare that $h$ does not
represent a specific quantity (the mesh-size), but rather
represents itself, i.e. stays as a symbol. Then
continuous analysis is just the {\it degenerate}
case $h=0$ of the full $h$-theory.
So the following is the only valid definition of the
classical derivative
$$
f'(x):= {{f(x+h)-f(x)} \over {h}} \vert_{h=0} \quad,
$$
which in Maple would read:
{\tt subs(h=0, simplify((f(x+h)-f(x))/h))}.
For example,
$$
(x^2)'={{(x+h)^2-x^2} \over {h}}\vert_{h=0}=
{{2xh+h^2} \over {h}}\vert_{h=0}=
{2x+h}\vert_{h=0}=2x \quad .
$$
Another example is
$$
(a^x)'= {{a^{x+h}-a^x} \over {h}}\vert_{h=0}=
a^x \cdot {{a^{h}-1} \over {h}}\vert_{h=0}=
a^x \ln a \quad
$$
where, {\it by definition}
$$
\ln a \, := \, {{a^{h}-1} \over {h}}\vert_{h=0} \quad.
$$
Using this definition, we can recover all the properties of
$\ln$, for example:
$$
\ln (ab)= {{(ab)^{h}-1} \over {h}}\vert_{h=0}=
{{((ab)^{h}-b^h)+(b^h-1)} \over {h}}\vert_{h=0}=
{{b^h(a^{h}-1)+(b^h-1)} \over {h}}\vert_{h=0}=
$$
$$
b^0 \cdot {{a^{h}-1} \over {h}}\vert_{h=0} +
{{b^{h}-1} \over {h}}\vert_{h=0} =\ln a + \ln b
\quad .
$$
{\bf Neo-Pythagoreanism or: Anaxogoras deserved to be drowned}
It is utter nonsense to say that $\sqrt{2}$ is {\it irrational},
because this presupposes that it exists, as a {\it number}
or {\it distance}. The
truth is that there is no such number or distance. What does exist is
the {\it symbol}, which is just shorthand for an {\it ideal} object
$x$ that satisfies $x^2=2$. In Maple notation:
{\tt sqrt(2)=RootOf(x**2=2)}.
The fundamental metric in plane geometry is not
{\it length} but {\it area}. In the discrete plane
$(hZ)^2$, the area of a region is simply the number
of lattice points in the interior of that region.
So the {\it true} Pythagorean theorem is not
$c^2=a^2+b^2$, but rather $c^2=a^2+b^2+O(h)$.
The notion of {\it distance} is usually not
defined. What {\it does} make sense is {\it distance squared}
between point $A$ and point $B$,
which, {\it by definition},
is the area (i.e. the number of lattice points in the interior)
of the square one of whose sides is $AB$.
{\bf Interface with Numerics: Interval Arithmetics}
Whenever one wants to do fully rigorous analytical calculations
on the computer, one uses {\it interval arithmetics},
where one represents a `real' number by a closed (or open)
interval it is known to belong to. While this is done for
computational reasons, we can also do it philosophically,
and only talk about intervals $[a,b]$, where $a$ and $b$
are {\it rational} (and hence meaningful) numbers.
The statements $e=2.718281828...$ and $\pi=3.14159...$
are {\it meaningless}, while
$e=2.718281828$, $\pi=3$, $\pi^2=10$,
and $\pi=355/113$,
while wrong, are at least {\it meaningful}.
On the other hand $\pi \in [31415/10000,31416/10000]$
is correct and meaningful.
One has the
obvious rules: $[a,b]+[c,d]=[a+c,b+d]$ etc.
{\bf Blessed Are The $\Delta$iffernce Equations
for They Shall Inherit Math}
{\bf Project 1:} Use Difference Equations to prove the
Riemann Hypothesis.
I believe that the fundamental equations, both theoretically
and practically, are {\it difference} equations rather than
{\it differential} equations. And indeed they are all over
mathematics, and will become more and more prominent with
the advent of computers, both as substitutes to differential
equations and for their own sake.
Recall that the prime number theorem $\pi(x)- x/\log(x)=o(x/\log(x))$
is equivalent to $R(x):=\psi(x)-x= o(x)$, where
$$
\psi(x):=\sum_{p^m\leq x} \log p \quad.
$$
Tchebychev proved that,
for large $x$,
$A_1 x \leq \psi(x) \leq A_2 x$, by using the extremely simple
{\it recurrence}:
$$
(\log 2) \cdot x +O(log(x)) = \psi(x)-\psi(x/2)+\psi(x/3)-\psi(x/4) +
\dots \quad ,
$$
that yields $A_1=\log 2$ and $A_2=2 \log 2$.
This was considerably improved by
Tchebychev himself and James Joseph Sylvester, who found
other, more complicated, but still linear, recurrences, that brought
$A_1$ up and $A_2$ down.
The next step was realized by Erd\"os and Selberg, who combined
two simple recursive inequalities for $R(x):=\psi(x)-x$. The first one
is linear (in $\vert R(x)\vert$):
$$
\vert R(x) \vert \leq {{1} \over {\log x}} \sum_{n \leq x}
\vert R(x/n) \vert + O( {{x \log \log x} \over { \log x}}) \quad ,
$$
while the second one is quadratic:
$$
\sum_{n \leq x} {{\log n} \over {n}} R(n) =
- \sum_{n \leq x} {{1} \over {n}} R(n) R( x/n) + O(x) \quad,
$$
from which it follows that $\vert R(x)\vert\leq \sigma x$
for $x>x_\sigma$, for every $\sigma >0$. Hence
$R(x)=o(x)$.
{\bf Exercise:} Find more powerful recurrences (alias {\it difference
equations }) that would imply the stronger statement
$R(x)=O(x^{1/2+\epsilon})$, for every $\epsilon>0$. Collect
\$1000000.
{\bf Project 2: Find a Rigorous Proof of Fermat's Last Theorem}
Andrew Wiles's alleged `proof' of FLT, while a crowning {\it human}
achievement, is not rigorous, since it uses
continuous analysis, which is
meaningless. I do believe that it is possible to convert it into
a rigorous proof in an analogous way to converting a proof in combinatorics
that uses {\it convergent} (and hence meaningless) power series into
a proof that uses {\it formal} (and hence fully kosher) power series.
But the end-result would be very artificial.
I hope that one of you would be able to find a completely elementary
(and hence fully rigorous) proof of FLT using recurrences,
possibly along the following lines.
Let's define
$$
W(n;a,b,c):=(a^n+b^n-c^n)^2 \quad .
$$
$W$ satisfies lots of recurrences, e.g.
$$
\Delta_a^{2n+1} W=0 \quad .
$$
I am almost sure that there
exists a {\it polynomial}, discoverable by computer,
with {\it positive coefficients} such that
$$
W(n;a,b,c)=P(W(n;a-1,b,c) \, ,
\, W(n;a,b-1,c) \, , \, \dots, \, W(n-1;a,b,c), \dots )
$$
for $n>3$. Since $W>0$ for $n=3$ and $abc>0$, FLT would follow.
Of course it suffices that $P$ is a rational function both
whose numerator and denominator have positive coefficients.
{\bf Analogy:}
{\bf Theorem} (Askey-Gasper 1977)
Let $A(m,n,k)$ be the Maclaurin coefficients of
$R:=(1-x-y-z+4xyz)^{-1}$, i.e.:
$$
{{1} \over {1-x-y-z+4xyz}}=\sum_{m, n, k \geq 0}
A(m,n,k) x^my^nz^k \quad,
$$
then $A(m,n,k) > 0$ for all $m,n,k \geq 0$.
The obvious recurrence
$$
A(m,n,k)=A(m-1,n,k)+A(m,n-1,k)+A(m,n,k-1)-4A(m-1,n-1,k-1) \quad ,
$$
is {\it useless} because of the {\it minus} sign on the
right side, but Gillis and Kleeman
(1979) came up with another recurrence:
$$
mA(m,n,k)=(m+n-k)A(m-1,n,k)+2(m-n+k-1)A(m-1,n,k-1) \quad,
$$
which immediately implies positivity, by induction, in
$m \geq n \geq k \geq 0$, and by symmetry, for all $m,n,k \geq 0$.
This recurrence is ingenious, but once found, is completely
routine. Just check (or let Maple do it if you are too lazy)
that
$$
{{\partial} \over {\partial x}} R=
(1+2z)(
x{{\partial} \over {\partial x}}
-y{{\partial} \over {\partial y}}
+z{{\partial} \over {\partial z}}+1)R+
2(y{{\partial} \over {\partial y}}
-z{{\partial} \over {\partial z}} )R \quad.
$$
Now this differential equation satisfied by $R$ is not only
routine to {\it verify}, it is also routine to
{\it discover}, once you tell the computer what to look for.
Let's hope that a similar recurrence would be found for FLT.
{\bf Philosophical Conclusion}
I am not a professional philosopher of mathematics, nor an
expert logician or foundationalist, but I think that the
philosophy that I am advocating here is called
{\it ultrafinitism}. If I understand it correctly, the ultrafinitists
deny the existence of {\it any} infinite, not even the potential
infinity, but their motivation is `naturalistic', i.e. they believe
in a `fade-out' phenomenon when you keep counting.
Myself, I don't care so much about the natural world. I am a
platonist, and I believe that {\it finite}
integers, {\it finite} sets of {\it finite} integers,
and all {\it finite} combinatorial structures have an existence of
their own, regardless of humans (or computers).
I also believe that {\it symbols} have an independent existence.
What is completely meaningless is
any kind of {\it infinite}, actual or potential.
So I deny even the existence of the Peano axiom that every integer has
a successor. Eventually we would get an overflow error in the
big computer in the sky, and the sum and product of any two
integers is well-defined only if the result is less than $p$,
or if one wishes, one can compute them modulo $p$.
Since $p$ is so large, this is not a practical problem, since
the overflow in our earthly computers comes so much sooner than
the overflow errors in the big computer in the sky.
However, one can still have `general' theorems,
provided that they are interpreted correctly. The
phrase `for {\it all} positive integers' is meaningless.
One should replace it by: `for finite or symbolic integers'.
For example, the statement:
``$(n+1)^2=n^2+2n+1$ holds for all integers'' should
be replaced by:
``$(n+1)^2=n^2+2n+1$ holds for finite or symbolic integers $n$'' .
Similarly,
Euclid's statement: `There are infinitely many primes'
is meaningless. What is true is: if $p_1