DO LARGE NUMBERS
REALLY EXIST?

E.B. Davies

King's College Mathematics Summer School
27June 2003

Why do we say that
2+3=5  ?
Perhaps because | | | combined with | | leads to | | | | |. The same argument may be used to justify
7×9=63
but it is less convincing for
1257×3142=3949494.
Do decimal numbers really stand for piles of tokens?
Small Numbers: For 10,000 one can think about the number of steps in a two hour walk.
Medium Numbers: A trillion dollars cannot be counted. One can count 36,000 per day at one per second. A trillion grains of sugar would fill two semi-detached houses. The exact number of people in the world does not make sense. There are about 6.3 billion people alive at present, and about 350,000 babies are born every day.
Large Numbers: The number of atoms in a cat may be about 1030, but this does not make sense as a counting number. The number of particles in the universe is often said to be about 1080. In science all large enough numbers are related to measurement, not to counting, and should have error bars.

1  Fibonacci Numbers

The Fibonacci numbers, first defined in 1202, are
1,1,2,3,5,8,13,21,34,...
The rule for generating them is
fn=fn-1+fn-2.
The formula of de Moivre (not Binet) is
fn=  1
Ö5
 æ
è 		 1+Ö5
2
 ö
ø 		n

 
 -  1
Ö5
 æ
è 		 1-Ö5
2
 ö
ø 		n

 
Nevertheless even the first digit of fn is uncomputable for n=10100.

2  The Proposition Pn

For the sake of definiteness we organize our discussion around a particular proposition; many others could be used to equal effect. One may routinely use induction to prove
Pn: There exists a positive integer m such that 9n-1=8×m.
For n=2 there are four ways of proving this, using counting, arithmetic, algebra
and geometry. Thus
92-1=(9-1)×(9+1)=8×10.
The same holds for n=3. For larger values of n the idea that one could verify Pn by such means is implausible. Let us consider, for example, the identity
9100-1
=
265613988875874769338781322
03577962682923345265339449
5974574961739092490901
302182994384699044000
=
8×332017486094843461673
4766525447245335365418
1581674311996821870217
3865613626627728742980
87380500.
We next consider an algebraic proof of P100 which is of a more theoretical nature. This uses the identity
9100-1=(9-1)×(999+998+...+9+1).
The symbol 9 need not refer to the number nine in this context, or indeed to any number, since the identity holds for any value of the symbol  9  in any commutative ring.

The issues involved in the use of induction are clearer if one considers a much larger value of n. Let us define N to be the number produced by the following computer program.

n:=1;
for r from 1 to 100 do
n:=nn+1;
end;
N:=n;
This produces a sequence of numbers which we label with subscripts: n0=1, n1=2, n2=5 and n3=55+1=3126. The number n4=31263126+1 is still just small enough to be computable using current PC's: it has 10,926 digits and can be printed out on about ten pages of A4 paper.

One may justify the existence of a huge number such as N on the basis that a huge iterative procedure can be carried out in principle, even though it obviously cannot be in practice. An alternative attitude is that the program constitutes a valid sequence of formal expressions and therefore defines an expression N within the rules of Peano arithmetic: the symbol N does not need to refer to anything.

The statement of PN, that (9-1) is a factor of (9N-1), cannot be verified except by using the general version of Peano's postulates. The proof makes no use of the particular values which the symbols 9 and N happen to have, and there is no alternative way of verifying the truth of the statement.

3  The Principle of Induction

The principle of induction is usually regarded as being the statement of an obvious property of any counting system, but it was not discovered/invented until about 1600. It states:
If P1 and (Pn implies Pn+1), then Pn is true for all n.
If one considers Peano arithmetic as a formal system no justification of the principle is needed: it is just one of the rules of the game.

4  Prime Numbers

Euclid's Elements Book 9, Proposition 20:
Prime numbers are more than any assigned multitude of prime numbers.

Let A, B and C be the assigned prime numbers. I say that there are more prime numbers than A, B and C. Take the least number DE measured by A, B and C. Add the unit DF to DE. etc. Euclid proves the existence of an unlimited number of primes, not of an infinite number. However, Euclid did not state the fundamental theorem of arithmetic:

Every number n may be written uniquely in the form
n=p1m1p2m2p3m3... pkmk.
Large prime factors.
729938 = 2×11×33179
The issue is whether one prime factor is bigger than the square root of the number. This happens 69.3% of the time.

We say that some proposition Pn has asymptotic probability c if
  #{ m:m £ n and Pm}
n
 ® c
as n ®¥.

Theorem 1 If k ³ 3 then the second largest prime factor q(n) of the number n satisfies q(n)k ³ n with asymptotic probability greater than
ó
õ 		1/2

1/3 
 log æ
è 		 1-x
x
 ö
ø 		   dx
 x
+ ó
õ 		1/3

1/k 
 log æ
è 		 1-x
1-2x
 ö
ø 		   d x
 x
   .

Example:
729938267777777777777777771
=13×61×371936510706073× 2474822939.
For k=10 the right hand side is approximately 0.5059. We conclude that completely factorizing a number m with 10,000 or more digits is usually as hard as factorizing the product of two primes, each of which has 1000 or more digits. The existence of a complete factorization of a number into primes is (almost surely) computationally intractable for most large numbers.

File translated from TEX by TTH, version 3.05.
On 29 Jun 2004, 12:54.