Additive Combinatorics
Recall our discussion of Erd}os’s multiplication table problem: how many dierent numbers are there in the
N
N
multiplication table? Erd}os discovered that the answer is
o
(
N
2
). That is, if
A
(
N
) is the number of
dierent integers in the
N
N
multiplication table, then as
N
!1
we have
A
(
N
)
=N
2
!
0.
Theorem
(Erd}os)
.
The number of distinct entries appearing in the
N
N
multiplication table, denoted
A
(
N
), is in
o
(
N
2
).
We shall sketch a proof of this theorem. The overarching idea is to look at the number of distinct prime
factors of integers up to
N
2
. Almost all such numbers have
log log
N
prime factors, while almost all entries
in the multiplication table have
2 log log
N
prime factors. We introduce the notation
!
(
n
) =
P
p
j
n
1, the
number of distinct prime factors of
n
. Note that the behaviour of
!
(
n
) is very hard to predict. Particularly,
from time to time it simply equals 1 (whenever we hit a prime). Instead of trying to predict
!
(
n
), we can
describe its
average
behaviour.
Lemma 1.
1
x
X
n
x
!
(
n
) = log log
x
+
O
(1)
:
The proof of this lemma relies on Euler’s famous result that the sum of the reciprocal of primes diverges.
Lemma
(Euler)
.
X
p
x
p
prime
1
p
= log log
x
+
O
(1)
:
Proof of Lemma 1.
In the following calculation we take
p
to be a prime. We calculate:
1
x
X
n
x
!
(
n
) =
1
x
X
n
x
X
p
j
n
1 =
1
x
X
p
x
X
n
x
p
j
n
1 =
1
x
X
p
x
X
d
x
p
1 =
1
x
X
p
x
x
p
=
1
x
X
p
x
x
p
+
O
(1)
=
1
x
X
p
x
x
p
+
O
0
@
1
x
X
p
x
1
1
A
=
X
p
x
1
p
+
O
(
x
)
x
= log log
x
+
O
(1)
:
Recall that
(
x
) denotes the number of primes
x
, so that
(
x
)
=x
2
O
(1).
Now since log log
x
grows extremely slowly, the upshot of Lemma 1 is that for \most”
n
x
we have
log log
n
log log
x
and therefore
!
(
n
)
log log
n
. This intuitive reasoning is made precise by a famous
theorem of Hardy and Ramanujan, sometimes referred to as Hardy-Ramanujan
normal order
theorem.
Theorem
(Hardy-Ramanujan, 1917)
.
Let
” >
0. Then for almost every
n
,
!
(
n
) = log log
n
+
O
”
(log log
n
)
1
2
+
”
Recall that in this class log
x
is the natural logarithm ln
x
.
1
The phrase \for almost every
n
” means that the number of exceptions is tiny; more precisely, the number
of
n
x
for which the theorem fails to hold is
o
(
x
).
In 1934, the Hungarian mathematician Pal Turan (who also frequently collaborated with Erd}os) gave a
simpler proof of the above theorem. His statement of the theorem is also more immediately usable for our
purposes.
Theorem
(Turan, 1934)
.
1
x
X
n
x
(
!
(
n
)
log log
x
)
2
log log
x
These theorem(s) characterize the error in our approximation, which is suciently small. To conclude we
now have that for almost every
n
N
2
!
(
n
)
log log
N
2
= log(2 log
N
) = log 2 + log log
N
log log
N:
By contrast, we expect almost every entry appearing in the multiplication table to have roughly double
that number of distinct prime factors, since
!
(
ab
) =
!
(
a
) +
!
(
b
)
2 log log
N
. The problem with this
heuristic is that
!
(
ab
) =
!
(
a
) +
!
(
b
) i
a
and
b
are coprimes. This motivates the following denition. Dene
A
(
N
) =
f
(
a;b
) :
a;b
2
N
and gcd(
a;b
) = 1
g
. The following claim solves our problem:
Lemma 2.
j
A
(
N
)
j
=
o
(
N
2
) =
) j
A
(
N
)
j
=
o
(
N
2
)
:
Exercise 1.
Prove Erd}os’s Theorem using the two lemmas above.
Proof of Lemma 2.
First note that
n
2
A
(
N
) =
)
n
=
a
b
=
)
a
gcd(
a;b
)
b
gcd(
a;b
)
=
n
gcd(
a;b
)
2
:
Therefore, if we denote
d
n
:=
gcd(
a;b
)
2
, then
n
gcd(
a;b
)
2
2
A
(
N=d
n
) and so
j
A
(
N
)
j
X
d
N
A
N
d
:
Exercise 2.
Carefully justify the last inequality.
Now, the fact that
j
A
(
N
)
j
=
o
(
N
2
) formally tells us that
8
” >
0
;
9
C
”
>
0 s.t.
j
A
(
M
)
j
“M
2
whenever
M > C
”
. Fix an
” >
0 and the corresponding
C
”
>
0, and let
N
be suciently large. Picking up where we
left o:
X
d
N
A
N
d
=
X
d
N
C
”
A
N
d
+
X
N
C
”
<d
N
A
N
d
X
d
N
C
”
”
N
2
d
2
+
X
N
C
”
<d
N
N
2
d
2
=
“N
2
X
d
N
C
”
1
d
2
+
N
2
X
N
C
”
<d
N
1
d
2
“N
2
+
N
2
X
N
C
”
<d
N
1
(
N=C
”
)
2
“N
2
+
C
2
”
N
=
”
+
C
2
”
N
N
2
:
Exercise 3.
Why is the proof complete?
* * *
* *
2
Let us now shift gears. Recall the following conjecture from the previous lecture:
Conjecture
(Erd}os-Szemeredi)
.
8
A
Z
max(
j
A
+
A
j
;
j
A
A
j
) =
j
A
j
2
o
(1)
:
Incidentally, in cases where the statement holds and
j
A
+
A
j
=
j
A
j
2
o
(1)
, we say that \
A
is
random
with
respect to addition.” The interesting idea behind this piece of jargon is that the typical behaviour of \ran-
dom” sets with respect to arithmetical operations gives us a way of measuring randomness.
The strongest positive result addressing this conjecture was achieved by Jozsef Solymosi in 2009.
Theorem
(Solymosi, 2009)
.
8
A;B
R
j
A
B
jj
A
+
B
jj
B
+
B
j
j
A
j
2
j
B
j
2
log(
j
A
jj
B
j
)
:
This result was later extended to
C
, though we shall prove it only for the case where
A;B
R
>
0
. We also
note that the log(
j
A
jj
B
j
) factor at the denomenator of the RHS is in fact log(
j
C
j
) where
C
:=
min(
j
A
j
;
j
B
j
).
Finally, note the following immediate corollary to Solymosi’s theorem.
Corollary.
8
A
R
max(
j
A
+
A
j
;
j
A
A
j
)
j
A
j
4
3
o
(1)
:
Before we proceed to prove Solymosi’s theorem, we stop to dene the following useful notation.
Denition.
Let
be a binary operation. Then
r
A
B
(
x
)
:=
jf
(
a;b
) :
a
b
=
x;a
2
A;b
2
B
gj
:
To famliarize yourself with this notation, convince yourself that
X
x
2
A
B
r
A
B
(
x
) =
j
A
B
j
=
j
A
jj
B
j
:
Proof of Solymosi’s Theorem.
We assume throughout that
A;B
R
>
0
. Solymosi’s rst key insight was to
observe that
X
x
2
A
B
r
A
B
(
x
)
2
=
X
m
2
B
A
r
B
A
(
m
)
2
:
(1)
Exercise 4.
Prove the equality above.
The LHS of this equality is called the \multiplicative energy” (introduced by Terence Tao?) of
A
and
B
.
One way to interpret that sum intuitively is
f
(
a;b
); (
a
0
;b
0
)
2
(
A
B
)
2
:
ab
=
a
0
b
0
g
, though it is not clear
how to use this characterisation. For this proof we will trivially bound LHS from below.
Coming back to Solymosi’s insight,
r
B
A
on the RHS can be interpreted geometrically. We have
r
B
A
=
jf
(
a;b
)
2
A
B
:
b=a
=
m
gj
;
so we are counting the number of (
A
B
)-lattice points on the line
L
m
of slope
m
through the origin,
y
=
mx
. This geometrical insight will allow us to bound the RHS from above. Combining this with the
lower bound on the LHS will yield the desired result. Let us start with the trivial lower bound on the LHS.
From Cauchy-Schwarz we have
X
x
2
A
B
r
A
B
(
x
)
!
2
X
x
2
A
B
r
A
B
(
x
)
2
!
X
x
2
A
B
1
2
!
() j
A
j
2
j
B
j
2
j
A
B
j
X
x
2
A
B
r
A
B
(
x
)
2
:
Therefore, in light of equation (1), suces it to show that
X
m
2
B
A
r
B
A
(
x
)
2
j
A
+
A
jj
B
+
B
j
log(
j
A
jj
B
j
)
:
This is exactly what we shall do in our next lecture. In preperation:
Exercise 5.
j
A
+
A
jj
B
+
B
j
=
j
(
A
B
) + (
A
B
)
j
:
3
PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT 🙂
