ADDITIVE NUMBER THEORY: NOTES AND SOME PRO-

BLEMS

B R Shankar

Department of Mathematical and Computational Sciences, National Institute of Technology Karnataka, Surathkal,

Mangalore - 575025 (India).

E-mail:shankarbr@nitk.edu.in

ORCID:0000-0001-5084-0567

Reception: 24/10/2022 Acceptance: 08/11/2022 Publication: 29/12/2022

Suggested citation:

B.R. Shankar (2022). Additive Number Theory: Notes and Some Problems. 3C Empresa. Investigación y pensamiento

crítico,11 (2), 186-196.https://doi.org/10.17993/3cemp.2022.110250.186-196

https://doi.org/10.17993/3cemp.2022.110250.186-196

ABSTRACT

A brief account of some of the major results in additive number theory is given along with a small list

of problems.

KEYWORDS

Number theory

https://doi.org/10.17993/3cemp.2022.110250.186-196

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

186

ADDITIVE NUMBER THEORY: NOTES AND SOME PRO-

BLEMS

B R Shankar

Department of Mathematical and Computational Sciences, National Institute of Technology Karnataka, Surathkal,

Mangalore - 575025 (India).

E-mail:shankarbr@nitk.edu.in

ORCID:0000-0001-5084-0567

Reception: 24/10/2022 Acceptance: 08/11/2022 Publication: 29/12/2022

Suggested citation:

B.R. Shankar (2022). Additive Number Theory: Notes and Some Problems. 3C Empresa. Investigación y pensamiento

crítico,11 (2), 186-196.https://doi.org/10.17993/3cemp.2022.110250.186-196

https://doi.org/10.17993/3cemp.2022.110250.186-196

ABSTRACT

A brief account of some of the major results in additive number theory is given along with a small list

of problems.

KEYWORDS

Number theory

https://doi.org/10.17993/3cemp.2022.110250.186-196

187

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

1 INTRODUCTION

Additive number theory is a relatively young discipline and has seen some spectacular progress in the

last few decades. The aim of this short article is to give a brief description of some of the major results

and also list a few problems that are easy to state and undertstand but not clear how they can (or will)

be solved. The goal is to stimulate and kindle interest in the subject. This is a review paper and most

of the material is well known. The papers of Melvyn B. Nathanson [3], [4], Kannan Soundararajan [5],

Andrew Granville [2], and H V Chu et al [1] are especially informative and detailed. We begin with a

well known and popular result, the Friendship theorem. Friendship Theorem

At any party with at least six people, there are three people who are all either mutual acquaintances

(each one knows the other two) or mutual strangers.

Ramsey Theory

For any given integer

, any given integers

n1,...,n

, there is a number,

(

n1,...,n

), such that if the

edges of a complete graph of order

(

n1,...,n

)are coloured with

diﬀerent colours, then for some

between 1and c, it must contain a complete subgraph of order niwhose edges are all colour i.

The special case above has c=2and n1=n2=3.

Broad Philosophy

Can ﬁnd order in disorder. Are there such analogs in Number theory? Answer is

YES. Order is Arithmetic progressions (APs). 3-AP means 3 consecutive terms in AP and k-AP means

k consecutive terms in AP. One can ask under what conditions will a set A of integers contain atleast

one 3-AP? No 3-AP at all? Inﬁnitely many 3-APs?

Broadly, given a suﬃciently large set of integers

we interested in understanding additive patterns

that appear in

. An important example is whether

contains non-trivial arithmetic progressions of

some given length k.

Reason

: They are quite indestructible structures. They are preserved under translations and dilations

of A, and they cannot be excluded for trivial congruence reasons.

For example the pattern

and

all being in the set seems quite close to the arithmetic progression

case

a, b,

(

)

2, but the former case can never occur in any subset of the odd integers (and such

subsets can be very large).

Other questions

: Whether all numbers can be written as a sum of

elements from a given set

. For

example, all numbers are sums of four squares, nine cubes etc. Waring’s problem and the Goldbach

conjectures are two classical examples. In the same spirit, given a set

integers we may ask for

information about the sumset

a, b ∈A}

. If there are not too many coincidences, then

we may expect

A|N2

. But when

is an AP,

A|≤

|A|−

1. The subject may be said to

begin with a beautiful result of van der Waerden (1927).

Theorem 1. (van der Waerden)

. Let

and

be given. There exists a number

(

k, r

)such

that if the integers in [1

]are colored using

colors, then there is a non-trivial monochromatic k term

arithmetic progression.

van der Waerden’s proof was by an ingenious elementary induction argument on

and

. The proof

does not give any good bound on how large

(

k, r

)needs to be. A more general result was subsequently

found by Hales and Jewett (1963), with a nice reﬁnement of Shelah (1988), but again the bounds for

the van der Waerden numbers are quite poor.

Theorem 2. (Schur)

. Given any positive integer

1, if

N≥N

(

)and the integers in [1

]are

colored using rcolors then there is a monochromatic solution to x+y=z.

Lemma 1.

Suppose that the edges of the complete graph

are colored using

colors. If

N≥N

(

)

then there is a monochromatic triangle.

Proof:

We will use induction on

. It is very well known that if

=2and

N≥

6then there is a

monochromatic triangle. Suppose we know the result for

r−

1colorings, and we need

N≥N

(

r−

for that result. Pick a vertex. There are

N−

1edges coming out of it. So for some color there are

[(

N−

]+1edges starting from this vertex having the same color. Now the complete graph on the

https://doi.org/10.17993/3cemp.2022.110250.186-196

other vertices of these edges must be colored using only

r−

1colors. Thus if

N≥rN

(

r−

−r

+2we

are done.

Proof of Schur’s Theorem:

Consider the complete graph on

vertices labeled 1through

Color the edge joining

using the color of

|a−b|

. By our lemma, if

is large then there is a

monochromatic triangle. Suppose its vertices are

a<b<c

, then (

c−a

)=(

c−b

)+(

b−a

)is a solution,

proving Schur’s theorem.

Theorem 3. (Hales-Jewett)

. Let

and

be given. There exists a number

(

k, r

)such that if

the points in [1

]

are colored using

colors then there is a monochromatic “combinatorial line”. Here

a combinatorial line is a collection of

points of the following type: certain of the coordinates are ﬁxed,

and a certain non-empty set of coordinates are designated as “wildcards” taking all the values from 1 to

A picturesque way of describing the Hales-Jewett theorem is that a “tic-tac-toe” game of getting k in

a row, played by r players, always has a result in suﬃciently high dimensions. Since there is obviously

no disadvantage to going ﬁrst, the ﬁrst player wins; but no constructive strategy solving the game

is known. One can recover van der Waerden’s theorem by thinking of [1

]

as giving the base

digits(shifted by 1) of numbers in [0,k

N−1].

Erdos and Turan proposed a stronger form of the van der Waerden, partly in the hope that the

solution to the stronger problem would lead to a better version of van der Waerden’s theorem.

The Erdos-Turan conjecture

: Let

and

be given. There is a number

(

k, δ

)such that any

set A⊂[1,N]with |A|≥δN contains a non-trivial arithmetic progression of lenghth k.

In 1953, Roth proved the Erdos - Turan conjecture in the case k=3.

Theorem 4. (Roth)

. There exists a positive constant

such that if

A⊂

]with

|A|≥CN/ log log N

then

has a non-trivial three term AP. In other words,

(

δ,

≤exp

(

exp

(

C/δ

)) for some positive

constant C.

This stronger result does in fact give a good bound on the van der Waerden numbers for

=3. We

know now(Bourgain), that

|A|N

(

log log N/log N

)

1/2

suﬃces. Thus the double exponential bound

can be replaced by a single exponential.

Let

(

)denote the size of the largest subset of [1

]having no non-trivial three term APs. Then

as mentioned above,

(

)

Nlog log N/log N

. What is the true nature of

(

)?Ifwepicka

random set

in [1

]we may expect that it has about

|A|3/N

three term APs. This suggests that

(

)is perhaps of size

. However, in 1946 Behrend found an ingenious construction that does

much much better.

Theorem 5. (Behrend)

. There exists a set

A⊂

]with

|A|Bexp

(

−c√logN

)containing no

non-trivial three term arithmetic progressions. In other words r3(N)Nexp(−c√log N).

Roth’s proof is based on Fourier analysis. It falls naturally into two parts: either the set

looks

random in which case we may easily count the number of three term progressions, or the set has some

structure which can be exploited to ﬁnd a subset with increased density. The crucial point is that the

idea of randomness here can be made precise in terms of the size of the Fourier coeﬃcients of the set.

This argument is quite hard to generalize to four term progressions (or longer), and was only extended

recently with the spectacular work of Gowers.

Returning to the Erdős-Turan conjecture, the next big breakthrough was made by Szemeredi who

in 1969 established the case

=4, and in 1975 dealt with the general case

k≥

5. His proof was a

tour-de-force of extremely ingenious and diﬃcult combinatorics. One of his ingredients was van der

Waerden’s theorem, and so this did not lead to a good bound there.

Theorem 6. (Szemeredi)

. Given

and

δ>

0, there exists

(

k, δ

)such that any set

A⊂

]

with |A|≥δN contains a non-trivial kterm arithmetic progression.

https://doi.org/10.17993/3cemp.2022.110250.186-196

189

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

An entirely diﬀerent approach was opened by the work of Furstenberg (1977) who used ergodic

theoretic methods to obtain a new proof of Szemeredi’s theorem. The ergodic theoretic approach also

did not lead to any good bounds, but was useful in proving other results previously inaccessible. For

example, it led to a multi-dimensional version of Szemeredi’s theorem, also a density version of the

Hales-Jewett theorem (due to Katznelson and Ornstein), and also allowed for the common diﬀerence of

the APs to have special shapes (e.g. squares).

In 1998-2001 Gowers made a major breakthrough by extending Roth’s harmonic analysis techniques

to prove Szemeredi’s theorem. This approach ﬁnally gave good bounds for the van der Waerden numbers.

Theorem 7. (Gowers)

. There exists a positive constant

such that any subset

in [1

]with

|A|N/(log log N)ckcontains a non-trivial kterm arithmetic progression.

One of the major insights of Gowers is the development of a “quadratic theory of Fourier analysis”

which substitutes for the “linear Fourier analysis” used in Roth’s theorem. Gowers’s ideas have trans-

formed the ﬁeld, opening the door to many spectacular results, most notably the work of Green and

Tao.

The Green-Tao Theorem (2003)

. The primes contain arbitrarily long non-trivial arithmetic

progressions.

By the Prime Number Theorem, upto

there are about

N/ log N

primes. This density is much

smaller than what would be covered by Gowers theorem; even in the case

=3it is not covered by the

best known results on r3(N). Another result is the celebrated three primes theorem.

Theorem 8. (Vinogradov, 1937). Every large odd number is the sum of three primes.

Another brilliant result of Green and Tao, developing Gowers ideas, is that

(

)

N

(

log N

)

−c

where r4(N)denotes the largest cardinality of a set in [1,N]containing no four term progressions.

Another theme is Freiman’s theorem on sumsets. If

is a set of

integers then

is bounded above

(

+ 1)

2, and below by 2

N−

1. The lower bound is attained only when

is highly structured,

and is an arithmetic progression of length

. Clearly if

is a subset of an arithmetic progression of

length

then

A|≤

C|A|

. More generally suppose

d1, ..., dk

are given numbers, and consider

the set

{a0

a1d1

...

akdk

≤ai≤Ni

for 1

≤i≤k}

. We may think of this as a generalized

arithmetic progression (GAP) of dimension

. Note that this GAP has cardinality at most

N1...Nk

. If

these sums are all distinct (so that the cardinality equals

N1...Nk

) we call the GAP

proper

. Note that

if A is contained in a GAP of dimension

and size

≤CN

then

A|≤

kCN

. Freiman’s theorem

provides a converse to this showing that all sets with small sumsets must arise in this fashion.

Theorem 9. (Freiman)

. If

is a set with

A|≤C|A|

then there exists a proper GAP of dimension

k(bounded in terms of C) and size ≤C1|A|for some constant C1depending only on C.

Qualitatively Freiman’s theorem says that any set with a small sumset looks like an arithmetic

progression. Similarly we may expect that a set with a small product set should look like a geometric

progression. But of course no set looks simultaneously like an arithmetic and a geometric progression!

This led to the following conjecture which says either the sumset or the product set must be large.

Erdős-Szemeredi Conjecture.

is a set of

integers then

|A.A|N2−

, for any

>0.

This is currently known for

>

4The sum-product theory (and its generalizations) is another

very active problem in additive combinatorics, and has led to many important applications (bounding

exponential sums etc).

Poincare recurrence:

Let

be a probability space with measure

, and let

be a measure preserving

transformation (so

(

T−1A

(

)). For any set

with positive measure there exists a point

x∈V

such that for some natural number n,Tnxalso is in V.

https://doi.org/10.17993/3cemp.2022.110250.186-196

Proof:

This is very simple: note that the sets

V,T−1V,T−2V, ...

cannot all be disjoint. Therefore

T−mV∩T−m−nV

for some natural numbers

and

. But this gives readily that

V∩TnV

needed.

It is clear from the proof that the number

in Poincare’s result may be found below 1

/µ

(

). As an

example, we may take

to be the circle

R/Z

, and take

to be the interval [

−

], and

be the map x→x+θfor some ﬁxed number θ. We thus obtain:

Theorem 10. (Dirichlet)

. For any real number

, and any

Q≥

1there exists 1

≤q≤Q

such that

||qθ|| ≤ 1/Q. Here ||x|| denotes the distance between xand its nearest integer.

happens also to be a separable (covered by countably many open sets) metric space, then we

can divide

into countably many balls of radius

/

2. Then it follows that almost every point of

returns to within of itself. That is, almost every point is recurrent.

We don’t really need a probability space to ﬁnd recurrence. Birkhoﬀ realized that this can be

achieved purely topologically and holds for compact metric spaces.

Theorem 11. (Birkhoﬀ’s Recurrence)

. Let

be a compact metric space, and

be a continuous

map. Then there exists a recurrent point in

; namely, a point

such that there is a sequence

nk→∞

with Tnkx→x.

Proof:

Since

is compact, any nested sequence of non-empty closed sets

Y1⊃Y2⊃Y3...

has a

non-empty intersection. Consider

-invariant closed subsets of

; that is,

with

TY ⊂Y

. By Zorn’s

lemma and our observation above, there exists a non-empty minimal closed invariant set

. Let

any point in

and consider the closure of

y, Ty, T2y, ...

This set is plainly a closed invariant subset of

Y, and by minimality equals Y. Therefore yis recurrent.

These are some basic simple results, of the same depth as Dirichlet’s pigeonhole principle and its

application to Diophantine approximation. In the example of Diophantine approximation, we see that

if ||nθ|| is small then so are ||2nθ||,||3nθ|| etc. This suggests the possibility of multiple recurrence.

Topological Multiple Recurrence.

Let

be a compact metric space, and

be a continuous map.

For any integer

k≥

1there exists a point

x∈X

and a sequence

nl→∞

with

Tjnlx→x

for each

1≤j≤k.

This theorem is analogous to van der Waerden’s theorem, and indeed implies it. To see this, let

Λ=

{

, ..., r}

represent

colors, and consider Ω=Λ

Thus Ωis the space of all

colorings of the

integers, and by

x∈

Ωwe understand a particular

coloring of the integers. We make Ωinto a compact

metric space (check using sequential compactness), by taking as the metric

(

x, y

)=0if

and

(

x, y

)=2

−l

where

is the least magnitude for which either

(

)



(

)or

(

−l

)



(

−l

). We deﬁne

the shift map Tby Tx(n)=x(n+ 1).

Now suppose we are given a coloring

of the integers. Take

to be the closure of

Tnξ

where

ranges

over all integers. By deﬁnition this is a closed invariant compact metric space, and so by the Topological

Multiple Recurrence Theorem there is a

x∈X

and some

n∈Z

with

(0) =

(

...

(

But from the deﬁnition of the space

we may ﬁnd an

m∈Z

such that

Tmξ

and

agree on the

interval [

−kn, kn

]. Then it follows that

(

...

(

)producing a

+1term AP.

The above argument gives an inﬁnitary version of the van der Waerden theorem where we color all

the integers. But from it we may deduce the ﬁnite version. Suppose not, and there are

colorings of

[

−N,N

]with no monochromatic k-APs for each natural number

. Extend each of these colorings

arbitrarily to

, obtaining an element in Ω. By compactness we may ﬁnd a limit point in Ωof these

elements. That limit point deﬁnes a coloring of

containing no monochromatic k-APs, and this is a

contradiction.

The ergodic theoretic analog of Szemeredi’s theorem is Furstenberg’s multiple recurrence theorem

for measure preserving transformations, and this implies Szemeredi by an argument similar to the one

above.

https://doi.org/10.17993/3cemp.2022.110250.186-196

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

190

An entirely diﬀerent approach was opened by the work of Furstenberg (1977) who used ergodic

theoretic methods to obtain a new proof of Szemeredi’s theorem. The ergodic theoretic approach also

did not lead to any good bounds, but was useful in proving other results previously inaccessible. For

example, it led to a multi-dimensional version of Szemeredi’s theorem, also a density version of the

Hales-Jewett theorem (due to Katznelson and Ornstein), and also allowed for the common diﬀerence of

the APs to have special shapes (e.g. squares).

In 1998-2001 Gowers made a major breakthrough by extending Roth’s harmonic analysis techniques

to prove Szemeredi’s theorem. This approach ﬁnally gave good bounds for the van der Waerden numbers.

Theorem 7. (Gowers)

. There exists a positive constant

such that any subset

in [1

]with

|A|N/(log log N)ckcontains a non-trivial kterm arithmetic progression.

One of the major insights of Gowers is the development of a “quadratic theory of Fourier analysis”

which substitutes for the “linear Fourier analysis” used in Roth’s theorem. Gowers’s ideas have trans-

formed the ﬁeld, opening the door to many spectacular results, most notably the work of Green and

Tao.

The Green-Tao Theorem (2003)

. The primes contain arbitrarily long non-trivial arithmetic

progressions.

By the Prime Number Theorem, upto

there are about

N/ log N

primes. This density is much

smaller than what would be covered by Gowers theorem; even in the case

=3it is not covered by the

best known results on r3(N). Another result is the celebrated three primes theorem.

Theorem 8. (Vinogradov, 1937). Every large odd number is the sum of three primes.

Another brilliant result of Green and Tao, developing Gowers ideas, is that

(

)

N

(

log N

)

−c

where r4(N)denotes the largest cardinality of a set in [1,N]containing no four term progressions.

Another theme is Freiman’s theorem on sumsets. If

is a set of

integers then

is bounded above

(

+ 1)

2, and below by 2

N−

1. The lower bound is attained only when

is highly structured,

and is an arithmetic progression of length

. Clearly if

is a subset of an arithmetic progression of

length

then

A|≤

C|A|

. More generally suppose

d1, ..., dk

are given numbers, and consider

the set

{a0

a1d1

...

akdk

≤ai≤Ni

for 1

≤i≤k}

. We may think of this as a generalized

arithmetic progression (GAP) of dimension

. Note that this GAP has cardinality at most

N1...Nk

. If

these sums are all distinct (so that the cardinality equals

N1...Nk

) we call the GAP

proper

. Note that

if A is contained in a GAP of dimension

and size

≤CN

then

A|≤

kCN

. Freiman’s theorem

provides a converse to this showing that all sets with small sumsets must arise in this fashion.

Theorem 9. (Freiman)

. If

is a set with

A|≤C|A|

then there exists a proper GAP of dimension

k(bounded in terms of C) and size ≤C1|A|for some constant C1depending only on C.

Qualitatively Freiman’s theorem says that any set with a small sumset looks like an arithmetic

progression. Similarly we may expect that a set with a small product set should look like a geometric

progression. But of course no set looks simultaneously like an arithmetic and a geometric progression!

This led to the following conjecture which says either the sumset or the product set must be large.

Erdős-Szemeredi Conjecture.

is a set of

integers then

|A.A|N2−

, for any

>0.

This is currently known for

>

4The sum-product theory (and its generalizations) is another

very active problem in additive combinatorics, and has led to many important applications (bounding

exponential sums etc).

Poincare recurrence:

Let

be a probability space with measure

, and let

be a measure preserving

transformation (so

(

T−1A

(

)). For any set

with positive measure there exists a point

x∈V

such that for some natural number n,Tnxalso is in V.

https://doi.org/10.17993/3cemp.2022.110250.186-196

Proof:

This is very simple: note that the sets

V,T−1V,T−2V, ...

cannot all be disjoint. Therefore

T−mV∩T−m−nV

for some natural numbers

and

. But this gives readily that

V∩TnV

needed.

It is clear from the proof that the number

in Poincare’s result may be found below 1

/µ

(

). As an

example, we may take

to be the circle

R/Z

, and take

to be the interval [

−

], and

be the map x→x+θfor some ﬁxed number θ. We thus obtain:

Theorem 10. (Dirichlet)

. For any real number

, and any

Q≥

1there exists 1

≤q≤Q

such that

||qθ|| ≤ 1/Q. Here ||x|| denotes the distance between xand its nearest integer.

happens also to be a separable (covered by countably many open sets) metric space, then we

can divide

into countably many balls of radius

/

2. Then it follows that almost every point of

returns to within of itself. That is, almost every point is recurrent.

We don’t really need a probability space to ﬁnd recurrence. Birkhoﬀ realized that this can be

achieved purely topologically and holds for compact metric spaces.

Theorem 11. (Birkhoﬀ’s Recurrence)

. Let

be a compact metric space, and

be a continuous

map. Then there exists a recurrent point in

; namely, a point

such that there is a sequence

nk→∞

with Tnkx→x.

Proof:

Since

is compact, any nested sequence of non-empty closed sets

Y1⊃Y2⊃Y3...

has a

non-empty intersection. Consider

-invariant closed subsets of

; that is,

with

TY ⊂Y

. By Zorn’s

lemma and our observation above, there exists a non-empty minimal closed invariant set

. Let

any point in

and consider the closure of

y, Ty, T2y, ...

This set is plainly a closed invariant subset of

Y, and by minimality equals Y. Therefore yis recurrent.

These are some basic simple results, of the same depth as Dirichlet’s pigeonhole principle and its

application to Diophantine approximation. In the example of Diophantine approximation, we see that

if ||nθ|| is small then so are ||2nθ||,||3nθ|| etc. This suggests the possibility of multiple recurrence.

Topological Multiple Recurrence.

Let

be a compact metric space, and

be a continuous map.

For any integer

k≥

1there exists a point

x∈X

and a sequence

nl→∞

with

Tjnlx→x

for each

1≤j≤k.

This theorem is analogous to van der Waerden’s theorem, and indeed implies it. To see this, let

Λ=

{

, ..., r}

represent

colors, and consider Ω=Λ

Thus Ωis the space of all

colorings of the

integers, and by

x∈

Ωwe understand a particular

coloring of the integers. We make Ωinto a compact

metric space (check using sequential compactness), by taking as the metric

(

x, y

)=0if

and

(

x, y

)=2

−l

where

is the least magnitude for which either

(

)



(

)or

(

−l

)



(

−l

). We deﬁne

the shift map Tby Tx(n)=x(n+ 1).

Now suppose we are given a coloring

of the integers. Take

to be the closure of

Tnξ

where

ranges

over all integers. By deﬁnition this is a closed invariant compact metric space, and so by the Topological

Multiple Recurrence Theorem there is a

x∈X

and some

n∈Z

with

(0) =

(

...

(

But from the deﬁnition of the space

we may ﬁnd an

m∈Z

such that

Tmξ

and

agree on the

interval [

−kn, kn

]. Then it follows that

(

...

(

)producing a

+1term AP.

The above argument gives an inﬁnitary version of the van der Waerden theorem where we color all

the integers. But from it we may deduce the ﬁnite version. Suppose not, and there are

colorings of

[

−N,N

]with no monochromatic k-APs for each natural number

. Extend each of these colorings

arbitrarily to

, obtaining an element in Ω. By compactness we may ﬁnd a limit point in Ωof these

elements. That limit point deﬁnes a coloring of

containing no monochromatic k-APs, and this is a

contradiction.

The ergodic theoretic analog of Szemeredi’s theorem is Furstenberg’s multiple recurrence theorem

for measure preserving transformations, and this implies Szemeredi by an argument similar to the one

above.

https://doi.org/10.17993/3cemp.2022.110250.186-196

191

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

Theorem 12. (Furstenberg)

. Let

be a probability measure space and let

be a measure preserving

transformation. If

is a set of positive measure, then there exists a natural number

such that

V∩T−nV∩T−2nV∩... ∩T−knVhas positive measure.

Behrend’s Example. Behrend constructed a surprisingly large set in [1,N]with no 3-APs.

Behrend’s Theorem A.

There is a set

in [1

]which is free of 3 APs and satisﬁes

|A|

Nexp(−c√log N). Here cis an absolute positive constant.

Behrend’s Theorem B.

There exists a set

in [1

]with

|A|≥δN

which has

δclog (1/δ)N2

three

term progressions. Here cis an absolute positive constant, and δ>0.

Theorem 13. (Varnavides)

. For every

δ>

0there exists

(

)

0such that if

A⊂

]with

|A|≥δN then Acontains at least C(δ)N2three term progressions.

Erdos and Szemeredi

: Expect that additive and multiplicative structures are independent. Hence

one of the two sets, i.e., sumset and product set, must be large.

Theorem 14. (Solymosi)

. Let

and

be ﬁnite sets of real numbers, each having at least two

elements. Then

|A+B|×|A.C|(|A|3|B||C|)1/2

In particular, if

A, B

and

all have cardinality

then either

A.C

has cardinality

N5/4

Note:

Both,

Erdos-Turan conjecture

and

Szemeredi’s Theorem

assume that the set

has a

positive density (Schnirelman density). However, the primes have zero density because of the

prime

number theorem. Hence Green - Tao theorem is much harder.

Now we consider ﬁnite sets: For any set Aof integers, we deﬁne the sumset

A+A={a+a:a, a∈A}

and the diﬀerence set

A−A={a−a:a, a∈A}.

We consider ﬁnite sets of integers, and the relative sizes of their sumsets and diﬀerence sets. If

is a

ﬁnite set of integers and

x, y ∈Z

, then the

translation

is the set

a∈A}

and the dilation of Aby yis y∗A={ya :a∈A}. We have

(x+A)+(x+A)=2x+2A

and

(x+A)−(x+A)=A−A.

Similarly,

y∗A+y∗A=y∗(A+A)

and

y∗A−y∗A=y∗(A−A).

It follows that

|(x+y∗A)+(x+y∗A)|=|2A|

and

|(x+y∗A)−(x+y∗A)|=|A−A|

https://doi.org/10.17993/3cemp.2022.110250.186-196

So the cardinalities of the sum and diﬀerence sets of a ﬁnite set of integers are invariant under aﬃne

transformations of the set. Easy to see that if

|A|

, then

is bounded above by

(

+ 1)

and below by 2N−1. The latter occurs when Ais an AP or symmetric.

The set

is symmetric with respect to the integer

z−A

or, equivalently, if

a∈A

if and

only if z−a∈A. For example, the set {4,6,7,9}is symmetric with z= 13. If Ais symmetric, then

A+A=A+(z−A)=z+(A−A)

and so

|A−A|

. Equality also holds if

is an AP. Examples of equality exists even if

neither symmetric nor an AP.

{

}

is neither symmetric nor an AP but

|A−A|

If A={a, b, c}with a<b<cand a+c=2b, then |A+A|=6<7=|A−A|.

{

}

then

= [0

14]

}

A−A

−

\ {−

}

and

= 12

13=|A−A|.

This is the typical situation. Since 2+7=7+2but 2−7=7−2

It is natural to expect that in any ﬁnite set of integers there are always at least as many diﬀerences

as sums. There had been a conjecture, often ascribed incorrectly to John Conway, that asserted that

|A+A|≤|A−A|for every ﬁnite set Aof integers.

This conjecture is false, and a counterexample is the set A={0,2,3,4,7,11,12,14}, for which

A+A= [0,28] \{1,20,27}

A−A=[−14,14] \ {±6,±13}and |A+A|= 26 >25=|A−A|.

Given the existence of such aberrant sets, we can ask for the smallest one. The set

above satisﬁes

|A|=8.

Problem 1.

What is the smallest such A?

i.e. ﬁnd min{|A|:A⊆Zand |A+A|>|A−A|}?

Note:

Hegarty has proved that this minimum is indeed equal to 8and is aﬃnely equivalent to the set

A={0,2,3,4,7,11,12,14}. One may also ask:

Problem 2.

What is the structure of ﬁnite sets satisfying |A+A|>|A−A|?

is a ﬁnite set of integers and

is a suﬃciently large positive integer (for example,

2 max({|a|:a∈A}), then the set

At=t−1



i=0

aimi:ai∈Afor i=0,1,...,t−1

has the property that

|At

At|

A|t

and

|At−At|

|A−A|t

. This can be seen as follows: the

elements of

can be thought of as having a base-m expansion with ’digits’ coming from the set

A+A.

It follows that if |A+A|>|A−A|, then At+A−t|>|At−At|and, moreover,

lim

t→∞ |At+At

|At−At|= lim

t→∞ |A+A|

|A−A|t

=∞

The sequence of sets

{At}∞

t=1

is the standard parametrized family of sets with more sums than diﬀerences

(called MSTD sets).

Problem 3.

Are there other parametrized families of sets satisfying |A+A|>|A−A|?

Even though there exist sets

that have more sums than diﬀerences, such sets should be rare, and

it must be true with the right way of counting that the vast majority of sets satisﬁes

|A−A|>|A

Problem 4.

Let

(

)denote the number sets

A⊆

,n−

1] such that

|A−A|<|A

, and let

(

n, k

)denote the

https://doi.org/10.17993/3cemp.2022.110250.186-196

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

192

Theorem 12. (Furstenberg)

. Let

be a probability measure space and let

be a measure preserving

transformation. If

is a set of positive measure, then there exists a natural number

such that

V∩T−nV∩T−2nV∩... ∩T−knVhas positive measure.

Behrend’s Example. Behrend constructed a surprisingly large set in [1,N]with no 3-APs.

Behrend’s Theorem A.

There is a set

in [1

]which is free of 3 APs and satisﬁes

|A|

Nexp(−c√log N). Here cis an absolute positive constant.

Behrend’s Theorem B.

There exists a set

in [1

]with

|A|≥δN

which has

δclog (1/δ)N2

three

term progressions. Here cis an absolute positive constant, and δ>0.

Theorem 13. (Varnavides)

. For every

δ>

0there exists

(

)

0such that if

A⊂

]with

|A|≥δN then Acontains at least C(δ)N2three term progressions.

Erdos and Szemeredi

: Expect that additive and multiplicative structures are independent. Hence

one of the two sets, i.e., sumset and product set, must be large.

Theorem 14. (Solymosi)

. Let

and

be ﬁnite sets of real numbers, each having at least two

elements. Then

|A+B|×|A.C|(|A|3|B||C|)1/2

In particular, if

A, B

and

all have cardinality

then either

A.C

has cardinality

N5/4

Note:

Both,

Erdos-Turan conjecture

and

Szemeredi’s Theorem

assume that the set

has a

positive density (Schnirelman density). However, the primes have zero density because of the

prime

number theorem. Hence Green - Tao theorem is much harder.

Now we consider ﬁnite sets: For any set Aof integers, we deﬁne the sumset

A+A={a+a:a, a∈A}

and the diﬀerence set

A−A={a−a:a, a∈A}.

We consider ﬁnite sets of integers, and the relative sizes of their sumsets and diﬀerence sets. If

is a

ﬁnite set of integers and

x, y ∈Z

, then the

translation

is the set

a∈A}

and the dilation of Aby yis y∗A={ya :a∈A}. We have

(x+A)+(x+A)=2x+2A

and

(x+A)−(x+A)=A−A.

Similarly,

y∗A+y∗A=y∗(A+A)

and

y∗A−y∗A=y∗(A−A).

It follows that

|(x+y∗A)+(x+y∗A)|=|2A|

and

|(x+y∗A)−(x+y∗A)|=|A−A|

https://doi.org/10.17993/3cemp.2022.110250.186-196

So the cardinalities of the sum and diﬀerence sets of a ﬁnite set of integers are invariant under aﬃne

transformations of the set. Easy to see that if

|A|

, then

is bounded above by

(

+ 1)

and below by 2N−1. The latter occurs when Ais an AP or symmetric.

The set

is symmetric with respect to the integer

z−A

or, equivalently, if

a∈A

if and

only if z−a∈A. For example, the set {4,6,7,9}is symmetric with z= 13. If Ais symmetric, then

A+A=A+(z−A)=z+(A−A)

and so

|A−A|

. Equality also holds if

is an AP. Examples of equality exists even if

neither symmetric nor an AP.

{

}

is neither symmetric nor an AP but

|A−A|

If A={a, b, c}with a<b<cand a+c=2b, then |A+A|=6<7=|A−A|.

{

}

then

= [0

14]

}

A−A

−

\ {−

}

and

= 12

13=|A−A|.

This is the typical situation. Since 2+7=7+2but 2−7=7−2

It is natural to expect that in any ﬁnite set of integers there are always at least as many diﬀerences

as sums. There had been a conjecture, often ascribed incorrectly to John Conway, that asserted that

|A+A|≤|A−A|for every ﬁnite set Aof integers.

This conjecture is false, and a counterexample is the set A={0,2,3,4,7,11,12,14}, for which

A+A= [0,28] \{1,20,27}

A−A=[−14,14] \ {±6,±13}and |A+A|= 26 >25=|A−A|.

Given the existence of such aberrant sets, we can ask for the smallest one. The set

above satisﬁes

|A|=8.

Problem 1.

What is the smallest such A?

i.e. ﬁnd min{|A|:A⊆Zand |A+A|>|A−A|}?

Note:

Hegarty has proved that this minimum is indeed equal to 8and is aﬃnely equivalent to the set

A={0,2,3,4,7,11,12,14}. One may also ask:

Problem 2.

What is the structure of ﬁnite sets satisfying |A+A|>|A−A|?

is a ﬁnite set of integers and

is a suﬃciently large positive integer (for example,

2 max({|a|:a∈A}), then the set

At=t−1



i=0

aimi:ai∈Afor i=0,1,...,t−1

has the property that

|At

At|

A|t

and

|At−At|

|A−A|t

. This can be seen as follows: the

elements of

can be thought of as having a base-m expansion with ’digits’ coming from the set

A+A.

It follows that if |A+A|>|A−A|, then At+A−t|>|At−At|and, moreover,

lim

t→∞ |At+At

|At−At|= lim

t→∞ |A+A|

|A−A|t

=∞

The sequence of sets

{At}∞

t=1

is the standard parametrized family of sets with more sums than diﬀerences

(called MSTD sets).

Problem 3.

Are there other parametrized families of sets satisfying |A+A|>|A−A|?

Even though there exist sets

that have more sums than diﬀerences, such sets should be rare, and

it must be true with the right way of counting that the vast majority of sets satisﬁes

|A−A|>|A

Problem 4.

Let

(

)denote the number sets

A⊆

,n−

1] such that

|A−A|<|A

, and let

(

n, k

)denote the

https://doi.org/10.17993/3cemp.2022.110250.186-196

193

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

number of such sets A⊆[0,n−1] with |A|=k. Compute

lim

n→∞

f(n)

and

lim

n→∞

f(n, k)

n

k

What about other functions that count ﬁnite sets of nonnegative integers with respect to sums and

diﬀerences?

Problem 5.

Prove that

|A−A|>|A

for almost all sets

with respect to other appropriate counting functions.

Binary linear forms:

The problem of sums and diﬀerences can be considered a special case of a more

general problem about binary linear forms

f(x, y)=ux +vy

where uand vare nonzero integers. For every ﬁnite set Aof integers, let

f(A)={f(a, a):a, a∈A}.

We are interested in the cardinality of the sets

(

). For example, the sets associated to the binary

linear forms

s(x, y)=x+y

and

d(x, y)=x−y

are the sumset s(A)=A+Aand the diﬀerence set d(A)=A−A.

To every binary linear form there is a unique normalized binary linear form

(

x, y

such that

u≥|v|≥1and (u, v)=1.

The natural question is: If

(

x, y

)and

(

x, y

)are two distinct normalized binary linear forms, do there

exist ﬁnite sets

and

of integers such that

(

)

|>|g

(

)

and

(

)

|<|g

(

)

, and, if so, is there

an algorithm to construct Aand B?

Brooke Orosz gave constructive solutions to this problem in some important cases. For example, she

proved the following: Let u>v≥1and (u, v)=1, and consider the normalized binary linear forms

f(x, y)=ux +vy and g(x, y)=ux −vy.

For u≥3, the sets

A={0,u

2−v2,u

2,u

2+uv}

and

B={0,u

2−uv, u2−v2,u

satisfy the inequalities

|f(A)|= 14 >13=|g(A)|

https://doi.org/10.17993/3cemp.2022.110250.186-196

and

f(B)=13<14=|g(B)|.

For

=2,

=1we have

(

x, y

)=2

and

(

x, y

)=2

x−y

. The sets

{

}

and

B={0,4,6,7}satisfy the inequalities |f(A)|= 13 >12 = |g(A)|and |f(B)|= 13 <14 = |g(B)|. The

problem of pairs of binary linear forms has been completely solved by Nathanson, O’Bryant, Orosz,

Ruzsa, and Silva.

Theorem 15.

Let

(

x, y

)and

(

x, y

)be distinct normalized binary linear forms. There exist ﬁnite sets

A, B, C with |C|≥2such that |f(A)|>|g(A)|,|f(B)|<|g(B)|and |f(C)|=|g(C)|.

Problem 6.

Let

(

x, y

)and

(

x, y

)be distinct normalized binary linear forms. Determine if

(

)

|>|g

(

)

for

most or for almost all ﬁnite sets of integers A.

These results should be extended to linear forms in three or more variables.

Problem 7.

Let

(

x1,,...,x

u1x1

...

unxn

and

(

x1,...,x

v1x1

...

vnxn

be linear forms with

integer coeﬃcients. Does there exist a ﬁnite set Aof integers such that |f(A)|>|g(A)|?

Polynomials over ﬁnite sets of integers and congruence classes

An integer-valued function is a function

(

x1,x

2,...,x

)such that if

x1,x

2,...,x

n∈Z

, then

f(x1,x

2,...,x

n)∈Z. The binomial polynomial

x

k=x(x−1)(x−2) ...(x−k+ 1)

is integer-valued, and every integer-valued polynomial is a linear combination with integer coeﬃcients

of the polynomials x

k,(George Polya). For any set A⊆Z, we deﬁne

f(A)={f(a1,a

2,...,a

n):ai∈Afor i=1,2,...,n}⊆Z.

Problem 8.

Let

(

x1,x

2,...,x

)and

(

x1,x

2,...,x

)be integer-valued polynomials. Determine if there exist

ﬁnite sets

A, B, C

of positive integers with

|C|≥

2such that

(

)

|>|g

(

)

(

)

|<|g

(

)

and

|f(C)|=|g(C)|. There is a strong form of Problem 8.

Problem 9.

Let f(x1,x

2,...,x

n)and g(x1,x

2,...,x

n)be integer-valued polynomials. Does there exist a sequence

{Ai}∞

i=1 of ﬁnite sets of integers such that

lim

i→∞ |f(Ai)|

|g(Ai)|=∞?

There is also the analogous modular problem. For every polynomial

(

x1,x

2,...,x

)with integer

coeﬃcients and for every set A⊆Z/mZ, we deﬁne

f(A)={f(a1,a

2,...,a

n):ai∈Afor i=1,2,...,n}⊆Z.

Problem 10.

Let

(

x1,x

2,...,x

)and

(

x1,x

2,...,x

)be polynomials with integer coeﬃcients and let

m≥

Do there exist sets

A, B, C ⊆Z/mZ

with

|C|>

1such that

(

)

|>|g

(

)

(

)

|<|g

(

)

, and

|f(C)|=|g(C)|.

Problem 11.

Let

(

x1,x

2,...,x

)and

(

x1,x

2,...,x

)be polynomials with integer coeﬃcients. Let

(

f,g

)denote

https://doi.org/10.17993/3cemp.2022.110250.186-196

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

194

number of such sets A⊆[0,n−1] with |A|=k. Compute

lim

n→∞

f(n)

and

lim

n→∞

f(n, k)

n

k

What about other functions that count ﬁnite sets of nonnegative integers with respect to sums and

diﬀerences?

Problem 5.

Prove that

|A−A|>|A

for almost all sets

with respect to other appropriate counting functions.

Binary linear forms:

The problem of sums and diﬀerences can be considered a special case of a more

general problem about binary linear forms

f(x, y)=ux +vy

where uand vare nonzero integers. For every ﬁnite set Aof integers, let

f(A)={f(a, a):a, a∈A}.

We are interested in the cardinality of the sets

(

). For example, the sets associated to the binary

linear forms

s(x, y)=x+y

and

d(x, y)=x−y

are the sumset s(A)=A+Aand the diﬀerence set d(A)=A−A.

To every binary linear form there is a unique normalized binary linear form

(

x, y

such that

u≥|v|≥1and (u, v)=1.

The natural question is: If

(

x, y

)and

(

x, y

)are two distinct normalized binary linear forms, do there

exist ﬁnite sets

and

of integers such that

(

)

|>|g

(

)

and

(

)

|<|g

(

)

, and, if so, is there

an algorithm to construct Aand B?

Brooke Orosz gave constructive solutions to this problem in some important cases. For example, she

proved the following: Let u>v≥1and (u, v)=1, and consider the normalized binary linear forms

f(x, y)=ux +vy and g(x, y)=ux −vy.

For u≥3, the sets

A={0,u

2−v2,u

2,u

2+uv}

and

B={0,u

2−uv, u2−v2,u

satisfy the inequalities

|f(A)|= 14 >13=|g(A)|

https://doi.org/10.17993/3cemp.2022.110250.186-196

and

f(B)=13<14=|g(B)|.

For

=2,

=1we have

(

x, y

)=2

and

(

x, y

)=2

x−y

. The sets

{

}

and

B={0,4,6,7}satisfy the inequalities |f(A)|= 13 >12 = |g(A)|and |f(B)|= 13 <14 = |g(B)|. The

problem of pairs of binary linear forms has been completely solved by Nathanson, O’Bryant, Orosz,

Ruzsa, and Silva.

Theorem 15.

Let

(

x, y

)and

(

x, y

)be distinct normalized binary linear forms. There exist ﬁnite sets

A, B, C with |C|≥2such that |f(A)|>|g(A)|,|f(B)|<|g(B)|and |f(C)|=|g(C)|.

Problem 6.

Let

(

x, y

)and

(

x, y

)be distinct normalized binary linear forms. Determine if

(

)

|>|g

(

)

for

most or for almost all ﬁnite sets of integers A.

These results should be extended to linear forms in three or more variables.

Problem 7.

Let

(

x1,,...,x

u1x1

...

unxn

and

(

x1,...,x

v1x1

...

vnxn

be linear forms with

integer coeﬃcients. Does there exist a ﬁnite set Aof integers such that |f(A)|>|g(A)|?

Polynomials over ﬁnite sets of integers and congruence classes

An integer-valued function is a function

(

x1,x

2,...,x

)such that if

x1,x

2,...,x

n∈Z

, then

f(x1,x

2,...,x

n)∈Z. The binomial polynomial

x

k=x(x−1)(x−2) ...(x−k+ 1)

is integer-valued, and every integer-valued polynomial is a linear combination with integer coeﬃcients

of the polynomials x

k,(George Polya). For any set A⊆Z, we deﬁne

f(A)={f(a1,a

2,...,a

n):ai∈Afor i=1,2,...,n}⊆Z.

Problem 8.

Let

(

x1,x

2,...,x

)and

(

x1,x

2,...,x

)be integer-valued polynomials. Determine if there exist

ﬁnite sets

A, B, C

of positive integers with

|C|≥

2such that

(

)

|>|g

(

)

(

)

|<|g

(

)

and

|f(C)|=|g(C)|. There is a strong form of Problem 8.

Problem 9.

Let f(x1,x

2,...,x

n)and g(x1,x

2,...,x

n)be integer-valued polynomials. Does there exist a sequence

{Ai}∞

i=1 of ﬁnite sets of integers such that

lim

i→∞ |f(Ai)|

|g(Ai)|=∞?

There is also the analogous modular problem. For every polynomial

(

x1,x

2,...,x

)with integer

coeﬃcients and for every set A⊆Z/mZ, we deﬁne

f(A)={f(a1,a

2,...,a

n):ai∈Afor i=1,2,...,n}⊆Z.

Problem 10.

Let

(

x1,x

2,...,x

)and

(

x1,x

2,...,x

)be polynomials with integer coeﬃcients and let

m≥

Do there exist sets

A, B, C ⊆Z/mZ

with

|C|>

1such that

(

)

|>|g

(

)

(

)

|<|g

(

)

, and

|f(C)|=|g(C)|.

Problem 11.

Let

(

x1,x

2,...,x

)and

(

x1,x

2,...,x

)be polynomials with integer coeﬃcients. Let

(

f,g

)denote

https://doi.org/10.17993/3cemp.2022.110250.186-196

195

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

the set of all integers

m≥

2such that there exists a ﬁnite set

of congruence classes modulo

such

that |f(A)|>|g(A)|. Compute M(f,g).

Note that if there exists a ﬁnite set

of integers with

(

)

|>|g

(

)

, then

(

f,g

)contains all

suﬃciently large integers.

Finally we mention two famous open problems:

1. Erdos:

ai∈N

, such that

∞

i=1 1

∞

, then

{ai}

contains arbitrarily long APs. Green-Tao is

a special case since ∞

i=1 1

pi=∞, where piare all primes.

2. The abc-conjecture:

This says roughly that if a lot of small primes divide

and

, then only a

few large ones will divide their sum

. More precisely, we deﬁne the

radical

n∈N

rad(n)=the product of the distinct prime factors of n. Eg: rad(16)=2, rad(17)=17, rad(18)=6.

Statement

For every

>

0, there exist only ﬁnitely many triples (

a, b, c

)of coprime positive integers with

and c > rad(abc)1+.

This has lot of consequences for mathematics. In particular this also implies the truth of Fermat’s Last

Theorem.

Recently, Shinichi Mochizuki from Japan has claimed a proof of the abc-conjecture. The 500 odd

-page proof is published by the RIMS(Research Institute of Mathematical Sciences), Kyoto, Japan. And

the author is one of editors of the journal. However there is no consensus among mathematicians about

the correctness of the proof. Only future will tell.

REFERENCES

[1] Chu, H. V.

McNew, N.

Miller, S. J.

Xu, V.

and

Zhang S.

(2008). When sets can and cannot

have sum-dominant subsets.J. Integer Seq. 2018. 21(8), 18,8

[2] Granville, A.

, (2007). An introduction to additive combinatorics. In Additive combinatorics.AMS.

2007.Volume 43, 1-27

[3] Nathanson, M. B.

, (2006). Problems in additive number theory, i. arXiv preprint math/0604340,

2006.

[4] Nathanson, M. B.

, (2006). Sets with more sums than diﬀerences. arXiv preprint math/0608148,

2006.

[5] Soundararajan„ K., (2010). Additive combinatorics: Winter 2007. Web, 2010.

https://doi.org/10.17993/3cemp.2022.110250.186-196

3C Empresa. Investigación y pensamiento crítico. ISSN: 2254-3376

Ed. 50 Vol. 11 N.º 2 August - December 2022

196