Probability and Number Theory: Some Examples of Connections

Jean-Marc Deshouillers

Mathématiques Stochastiques, Université Bordeaux 2

Algorithms Seminar

January 13, 1997

[summary by Alain Plagne]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
We illustrate some connections between probability theory and number theory. Examples are taken from multiplicative number theory (probabilistic behaviour of the function w), additive number theory (Sidon problem, where arithmetic results are proved by using probability theory; partitions; and Erdös-Rényi type models for sums of powers, where situations on which nothing is known, are modelled) and probability (upper bound for the concentration of the sum of independent and identically distributed integer random variables, where probabilistic results are obtained by using methods from additive number theory).



1   Introduction

One can distinguish at least four types of connections between probability theory and additive number theory.

Part 2 is devoted to multiplicative number theory. It provides examples for points (i) and (ii). The third part, which is the heart of this talk, is concerned with additive number theory and illustrated with Sidon's problem (point (ii)), partitions (points (i) and (ii)) and sums of s-th powers (points (i) and (iii)). In the fourth part, which deals with concentration functions, point (iv) is illustrated.

2   Multiplicative Number Theory

We begin with a famous result due to Hardy and Ramanujan [11] concerning the function w, which counts the number of divisors of an integer
w (n) = | { p such that p|n } |.
Here and in the sequel, p always denotes a prime number.
Theorem 1   Let Y (x) ® ¥. Then the set of integers such that
| w (n) - log log n | £ Y (n) (log log n )1/2     (1)
has density one.

This result means that
 
lim
N ® + ¥
| { 1 £ n £ N: (1) holds } |
N
=1.
The original proof is quite technical. We quote here an efficient way to get the result which is due to Turán [17].
N-1
 
å
n £ N
w (n)
= N-1
 
å
n £ N
 
å
p|n
1 = N-1
 
å
p £ N
 
å
n £ N
n=0mod p
1
 
=
N-1
 
å
p £ N
(N/p +O(1))=
 
å
p £ N
1/p +O(1)= log log N +O(1)
.
See for example [16] for the last equality. In the same way, we get
N-1
 
å
n £ N
w (n)2=(log log N)2+ O(log log N),
thus the number of exceptions to (1) up to N is
| { 1 £ n £ N: | w (n) - log log n| ³ Y (n) ( log log n)1/2 } | £
 
å
n £ N
(w (n) - log log n)2
Y(n)2 log log n
,
which is O(N/ Y(N)2). This proves the result.

Now let us show a probabilistic approach. Let (Xp) be a family of independent random variables defined by
Xp=
ì
í
î
1,     with probability 1/p,
0,     with probability 1-1/p.
The mathematical expectation of w = åp £ NXp is
E(w)=
 
å
p £ N
E(Xp)=
 
å
p £ N
1/p= log log N +o(log log N),
and the variance of w is
V(w)=
 
å
p £ N
V(Xp)=
 
å
p £ N
(1-1/p)/p= log log N +o(log log N).
Chebyshev's inequality yields
Pr { | w - E(w) | ³ Y (V(w))1/2 } £ 1/ Y2,
that is the result.

This result can be interpreted, with a probabilistic point of view, as a weak law of large numbers. A much more precise result, that is a central limit theorem, has been proved by Erdös and Kac in 1939 [4, 5].

Theorem 2   For u a real, one has
1
N
| { 1 £ n £ N: w (n) - log log n £ u (log log n )1/2 } | ¾®
 
N ® ¥
1
(2 p)1/2
ó
õ
u


- ¥
e
-t2/2
 
dt.     (2)

A natural question is now: can this result be extended to other (strongly) additive functions (that is such that f(n)=åp|nf(p))? More precisely, can one compare (and how far?)
1
N
| { 1 £ n £ N : f(n) £ u } |     with     Pr ì
í
î
 
å
p £ N
Xp £ u ü
ý
þ		 ,
where the Xp's are independent Bernoulli random variables such that Pr { Xp= f(p) } =1/p and Pr { Xp= 0 } =1-1/p. By sophisticated sieve arguments, it can be shown that
1
N
|{ 1 £ n £ N :
 
å
p|n, p £ r
f(p) £ u}| - Pr {
 
å
p £ r
Xp £ u} = O é
ê
ê
ë		 x-1/15+ exp æ
ç
ç
è		 -
1
8
log x
log r
log
log x
log r
ö
÷
÷
ø		 ù
ú
ú
û		 ,
which is o(1) when r=xe (x) tends to + ¥ but e (x) ® 0. This model is called the ``Kubilius model''.

3   Additive Number Theory

3.1   Sidon problem

In 1932, Sidon raised the following question: is it possible to find a sequence A of non-negative integers such that

In other words: is it possible to build a ``thin'' basis of order 2? In 1954, Erdös [3] answered positively the question, by proving a more precise result.

Theorem 3   There exists A and 0< c1 < c2 such that
c1 log n < | { a, n-a Î A } | < c2 log n,     (3)
for n ³ 2.

The proof is probabilistic and particularly short but absolutely not constructive: let (W, T,P) be a probabilistic space and X2,X3,... be independent Bernoulli random variables such that Pr { Xn=1 }= c ( (log n) /n)1/2. For w Î W, let A(w)= { 0,1 } È {n: Xn(w)=1 }. Then for almost all w Î W, A(w) satisfies (3). A very detailed proof of this result is given in the book by Halberstam and Roth [9, chap. 3].

3.2   Restricted partition function

This example underlies the probabilistic interpretation of the powerful Ramanujan-Hardy-Littlewood circle method [18].

For a given N, let q(N) be the number of ways to write
N= n1+n2+...+nr,
with 0<n1<n2<...<nr (£ N). Another way to say this is: let
EN= { 0,1 } ×...× { 0,N },
then
q(N)= 2N
| { x Î EN , å xn=N }|
| {x Î EN } |
.
Let X1,...,XN be independent random variables such that Xn takes the values 0 and n with probability 1/2. We have
q(N)= 2N Pr { X1+...+XN=N }.
Denote EN and VN the expectation and the variance of X1+...+XN. If we assume that a local limit theorem holds, then we can write
q(N)= 2N
1
(2 p VN)1/2
æ
ç
ç
è		 exp æ
ç
ç
è		 -
(N-EN)2
2 VN
ö
÷
÷
ø		 +o(1) ö
÷
÷
ø		 .
An easy computation shows that EN ~ N2/4, VN ~ N3/12 and that the exponential term is o(1) and so that q(N)= o(2NN-3/2) which is not interesting. This is due to the fact that N is too far from EN.

This approach is far from being perfect. The reason is quite clear: in the problem of partitions for an integer N, the integers 1,2,...,N do not have the same importance: the small values take part much more frequently in a decomposition of N than the large ones. Thus we have to refine the model by weighting the different integers, with a smaller weight for large integers.

Suppose now the Xi's are independent random variables taking only the values 0 and n with Pr { Xn=n } =pn. Then
q(N)=
 
å
x Î En, x1+...+xN=N
Pr { (X1,...,XN)=x }
 
Õ
n, xn=n
pn
 
Õ
n, xn=0
(1-pn)
.
If we take pn= exp(- s n)/(1+ exp (- s n)), for some s such that E(X1+...+XN)=N, that is to say
s =
p
2 (3N)1/2
(1 -1/8N+O(N-2)),
we can prove (this is naturally the heart of the matter) that
q(N) ~
1
4 (3N)1/4
exp (p N1/2/ (3)1/2)
(see [10, 13]). This argument has been recently developed in [8] in a more general context.

Proof goes as usual, by defining the characteristic function (i.e., the Fourier transform of the image measure)
fn(t)=(1-pn)+pn exp(2 p i nt).
Then
Pr { X1+...+XN=N } = ó
õ
 


R / Z
æ
ç
ç
è
 
Õ
n £ N
fn(t) ö
÷
÷
ø		 exp (-2 p i Nt) dt.
The main term (corresponding to major arc) comes from a neighbourhood of 0 on the torus R / Z. There ``remains'' (it is not easy!) to find an upper bound for | Õn £ N fn(t)| outside this neighbourhood, that is on the minor arc.

3.3   Probabilistic models for sums of powers

It is well known that sums of two squares have zero density. But for s ³ 3, nothing is known about (lower) density of the set of sums of s integral s-th powers, like sums of 3 cubes and of 4 biquadrates.

There are two conjectures. In 1968, Barrucand [1] conjectured that for s=3 and 4 the answer is NO. But, in 1986, Hooley [12] conjectured that the answer is YES for every s ³ 3.

In order to guess something in this hard problem, Erdös and Rényi [6], in 1960, considered ``pseudo s-th powers'', i.e., random sequences A(s) defined as in the answer to Sidon's question, and suggested that the number of representation rs(N) of an integer N as a sum of s elements from A(s) should follow (almost surely) a Poisson law. Unfortunately, their proofs contained a gap because of the difficulty of dealing with the quasi-independence of the sets involved. In 1965, Halberstam and Roth [9] overcame the difficulty when s=2, by combinatorial arguments. In 1995, Landreau [14] proved a correlation inequality, having its own probabilistic interest, which leads to the expected result.

Theorem 4   Let E1,..., EN be independent events, and A1,...,AT be such that each At is an intersection of some of the En's. Then
0 £ Pr (Ç
_
At
 
)- Õ Pr (
_
At
 
) £
 
å
1 £ t<t' £ T
( Pr (At Ç At')- Pr (At) Pr (At') ) .

4   Probability

We illustrate here the possibility of applying number theory ideas to probability theory with the following recent theorem taken from [2], of which we sketch the proof.

Theorem 5   Let log 4/log 3< s £ 2, n Î N* and e >0, X1,...,Xn be i.i.d. integral valued random variables such that
 
max
q £ 2
 
max
s mod q
 
å
l=s mod q
Pr { X1=l } £ 1 - e     (4)
and for all L ³ 2
Q(X1,L) £ 1-L
- s
 
,     (5)
where Q(Y,x) denotes suph Î R Pr { h< Y £ h+x }. Then there exists a constant c=c(s, e, Q(X1, 1)) such that
Q(X1+...+Xn;1) £ cn
-1/ s
 
.

The proof, in the same manner as above, uses the characteristic function f of X1. If Sn=X1+...+Xn, we have
Pr { Sn =k } = ó
õ
1


0
f (t)n exp (-2 p i kt) dt,
so that Q(Sn,1) £ ò01 | f (t)|n dt.

We are now reduced to study the large values of f. We first use a lemma which has been introduced in [15] (and which follows from Bochner's theorem).

Lemma 1   Let Eq= { t Î R / Z, | f (t)| ³ cos q }, where R / Z is once again the torus, we have for q1, q2 ³ 0 and q1+ q2 £ p /2,
E
 
q1
+ E
 
q2
Ì E
 
q1+ q2
.

Then we need a result by Freiman [7] on structure of set addition (it has been extended to the torus in [15]).

Theorem 6   Let A be a finite subset of Z such that
| A + A | £ 2 | A| -1 +b,
with b £ | A|-3, then there exists an arithmetic progression L with | A|+b elements that contains  A.

This enables us to show that either the set of the arguments for which f is large has a small measure, or it has a structure (it is located close to the vertices of a regular polygon), which is not possible in view of (4) and (5).

References

[1]
Barrucand (Pierre). -- Sur la distribution empirique des sommes de trois cubes ou de quatre bicarrés. Comptes-Rendus de l'Académie des Sciences, vol. 267, 1968, pp. 409--411.

[2]
Deshouillers (J.-M.), Freiman (G. A.), and Yudin (A. A.). -- On Bounds for the Concentration Function, 1. -- Prépublication n°M/95/37, IHES, 1995.

[3]
Erdös (P.). -- On a problem of Sidon in additive number theory. Acta Scientiarum Mathematicarum Szegediensis, vol. 15, 1954, pp. 255--259.

[4]
Erdös (P.) and Kac (M.). -- On the Gaussian law of errors in the theory of additive functions. Proceedings of the National Academy of Sciences of the USA, vol. 25, 1939, pp. 206--207.

[5]
Erdös (P.) and Kac (M.). -- The Gaussian law of errors in the theory of additive number theoretic functions. American Journal of Mathematics, vol. 62, 1940, pp. 738--742.

[6]
Erdös (P.) and Rényi (A.). -- Additive properties of random sequences of positive integers. Acta Arithmetica, vol. 6, 1960, pp. 83--110.

[7]
Freiman (G. A.). -- Foundations of a structural theory of set addition. -- American Mathematical Society, Providence, R. I., 1973, Translations of Mathematical Monographs, vol. 37. Translated from the Russian.

[8]
Freiman (Gregory A.) and Pitman (Jane). -- Partitions into distinct large parts. Journal of the Australian Mathematical Society, vol. 57, n°3, 1994, pp. 386--416.

[9]
Halberstam (Heini) and Roth (Klaus Friedreich). -- Sequences. -- Springer-Verlag, New York-Berlin, 1983, 2nd edition.

[10]
Hardy (G. H.) and Ramanujan (S.). -- Asymptotic formulæ in combinatory analysis. Proceedings of the London Mathematical Society, vol. 16, 1917, pp. 75--115.

[11]
Hardy (G. H.) and Ramanujan (S.). -- The normal number of prime factors of a number n. Quarterly Journal of Mathematics, vol. 48, 1917, pp. 76--92.

[12]
Hooley (Christopher). -- On some topics connected with Waring's problem. Journal für die Reine und Angewandte Mathematik, vol. 369, 1986, pp. 110--153.

[13]
Hua (Loo-Keng). -- On the number of partitions of a number into unequal parts. Transactions of the American Mathematical Society, vol. 51, 1942, pp. 194--201.

[14]
Landreau (Bernard). -- Étude probabiliste des sommes de s puissances s-ièmes. Compositio Mathematica, vol. 99, n°1, 1995, pp. 1--31.

[15]
Moskvin (D. A.), Freiman (G. A.), and Judin (A. A.). -- Inverse problems of additive number theory and local limit theorem for lattice random variables. In Number-theoretic studies in the Markov spectrum and in the structural theory of set addition, pp. 148--162. -- Kalinin. Gos. Univ., Moscow, 1973.

[16]
Tenenbaum (Gérald). -- Introduction to analytic and probabilistic number theory. -- Cambridge University Press, Cambridge, 1995, Cambridge Studies in Advanced Mathematics, vol. 46. Translated from the second French edition (1995).

[17]
Turán (P.). -- On a theorem of Hardy and Ramanujan. Journal of the London Mathematical Society, vol. 9, 1934, pp. 274--276.

[18]
Vaughan (R. C.). -- The Hardy-Littlewood method. -- Cambridge University Press, Cambridge, 1997, 2nd edition, Cambridge Tracts in Mathematics, vol. 125.
This document was translated from LATEX by HEVEA.