[FOM] Probability and Number Theory

[Dmytro Taranovsky]

Number theory is a concrete branch of mathematics.  Despite that--or
perhaps because of that--quasi-scientific reasoning and probability are
useful for estimating truth of arithmetical statements that have not yet
been proved.  For example, we know that white has a winning strategy in
chess if black plays without the queen, but we have no proof.  

In this posting, I illustrate probabilistic reasoning through several
interesting related conjectures of mine.  The foundational issue is how
do we perform such reasoning and what role should it play in
mathematics.

The topic is additive representation of integers in terms of numbers
given multiplicatively.  For example, every natural number is a sum of
distinct powers of two, and we believe that every even number larger
than two is the sum of two primes.

Conjectures: 
Every even integer larger than 8 is the sum of a prime and a power of
two and a power of five; same with five replaced by three.
Every odd integer that is larger than 7 and is not divisible by 3 is the
sum of a prime and a product of a power of 2 and a power of 3.
Every odd integer larger than 7 that is not a multiple of 15 is the sum
of a prime and two distinct powers of two.
(Note:  In "power", we can require that the exponent is a positive
integer.)

The conjectures have been verified up to 2000000000, but that alone is
insufficient.  After all, the least integer larger than 3 that is not
the sum of a prime and 2 or two powers of two is 1117175145.  What we
need is a theory of why they are true.  The key heuristic is that for
these purposes, the number of representations behaves randomly subject
to usually basic constraints.

The key constraint is the average number of representations (as a
function of size), which can usually be computed without difficulty.
Under randomness assumptions, we can then estimate the distribution of
the exceptions (if any).  The problem is finding out which categories of
numbers are resistant to representation and to what extent.  Usually,
the resistance comes from having a specific value mod a certain number.
Multiplies of 15 and especially 255 (and 65535) are resistant to being
the sum of a prime and two powers of two.  Integers that are 7 mod 8 are
not the sum of three squares.  However, one has to watch out for other
constraints.  For example, most squares are not the sum of a square and
a prime.  It is known that infinitely many natural numbers are not the
sum of two squares and a (positive) ninth power.

Computations are useful in identifying these constraints.  We note not
only the exceptions, but also numbers having only a small number of
representations.  Once satisfied that the least number of
representations grows fast enough, the conjectures are essentially
confirmed.  For the conjectures above, the average number of
representations grows logarithmically, which indicates that they are
nearly optimal and that their truth should depend on the proportionality
constant.  That is why the verification had to be run up to a large
number.  Continual finding of numbers having a unique representation as
a sum of a prime and two powers of 2 heralded existence of large numbers
not representable that way.

On the other hand, finding the largest exception is not necessary to
make conjectures.  Using probabilistic reasoning, we can conjecture:

"Every sufficiently large odd number is the sum of a square of a prime,
a cube of a prime, and a fifth power of a prime"

even though less than 0.8% of odd numbers below 10^100 are representable
in that form.  The largest odd number not so representable is expected
between 10^200 and 10^400.  However, the conjecture has not yet been
confirmed beyond a reasonable doubt; a special constraint might be
lurking in the exceptions.  

Using probabilistic reasoning one can make and evaluate more conjectures
like these.  Probabilistic reasoning is done carefully and
quasi-scientifically, and with formal results, theories, and
computations to back ip up.  Such reasoning is not a substitute for
proof, but it can lead to new mathematical truths and eventually to
proofs and possibly to axioms. 

Dmytro Taranovsky