Fermat's Library | The Erdos discrepancy problem annotated/explained version.

arXiv:1509.05363v1 [math.CO] 17 Sep 2015

THE ERD

OS DISCREPANCY PROBLEM

TERENCE TAO

Abstract. We show that for any sequence f : N Ñ t´1, `1u

taking values in t´1, `1u, the discrepancy

sup

n,dPN

j“1

fpjdq

of f is inﬁnite. This answers a question of Erd˝os. In fact the

argument also applies to sequences f taking values in the unit

sphere of a real or complex Hilbert space.

The argument uses three ingredients. The ﬁrst is a Fourier-

analytic reduction, obtained as part of the Polymath5 project on

this problem, which reduces the problem to the case when f is re-

placed by a (stochastic) completely multiplicative function g. The

second is a logarithmically averaged version of the Elliott conjec-

ture, established recently by the author, which eﬀectively reduces

to the case when g usually pretends to be a modulated Dirichlet

character. The ﬁnal ingredient is (an extension of) a further argu-

ment obtained by the Polymath5 project which shows unbounded

discrepancy in this case.

1. Introduction

Given a sequence f : N Ñ H t aking values in a real or complex

Hilbert space H, deﬁne the disc repancy of f to be the quantity

sup

n,dPN

›

j“1

fpjdq

›

In other words, the discrepancy is the largest magnitude of a sum

of f a long homogeneous arithmetic progressions td, 2d, . . . , ndu in the

natural numbers N “ t1, 2, 3, . . . u.

The main objective of this paper is to establish the f ollowing result:

Theorem 1.1 ( Erd˝os discrepancy pr oblem, vector-valued case). Let

H be a real or complex Hilbert space , and let f : N Ñ H be a function

such that } f pnq}

“ 1 for all n. Then the discrepancy of f is inﬁnite.

Specalising to the case when H is the reals, we thus have

Corollary 1.2 (Erd˝os discrepancy pr oblem, original formulation). Ev-

ery function f : N Ñ t´1, `1u has inﬁn i te discrepancy.

2 TERENCE TAO

This answers a question of Erd˝os [5], which was recently the subject

of t he Polymath5 project [13]; see the recent report [6] on the latter

project for further discussion.

It is instructive to consider some near-counterexamples to these re-

sults - that is to say, functions that are of unit magnitude, or nearly so,

which have surprisingly small discrepancy - to isolate the key diﬃculty

of the problem.

Example 1.3 (Dirichlet chara cter). Let χ : N Ñ C be a non-principal

Dirichlet character of p eriod q. Then χ is completely multiplicative

(thus χpnmq “ χpnqχpmq for any n, m P N) and has mean zero on any

interval of length q. Thus for any ho mo geneous arithmetic progression

td, 2d, . . . , ndu one has

j“1

χpjdq

“

χpdq

j“1

χpjq

ď q

and so the discrepancy of χ is at most q (indeed one can reﬁne this

bound further using character sum bounds such as the Burg ess bound

[2]). Of course, this does not cont r adict Theorem 1.1 or Corollary 1.2,

even when the character χ is real, because χpnq vanishes when n shares

a common factor with q. Nevertheless, this demonstrates the need to

exploit the hypothesis that f has magnitude 1 for all n (as opposed to

merely for most n).

Example 1.4 (Borwein-Choi-Coons example). [1] Let χ

be the non-

principal Dirichlet character of period 3 (thus χ

pnq equals `1 when

n “ 1 p3q, ´1 when n “ 2 p3q, and 0 when n “ 0 p3q), and deﬁne

the completely multiplicative function ˜χ

: N Ñ t´1, `1u by setting

˜χ

ppq :“ χ

ppq when p ‰ 3 and ˜χ

p3q “ `1 . This is about the simplest

modiﬁcation one can make to Example 1.3 to eliminate the zeroes. Now

consider t he sum

j“1

˜χ

pjq

with n :“ 1 `3 `3

`¨¨¨`3

for some large k. Writing j “ 3

m with

m coprime to 3 and i at most k, we can write this sum as

i“0

1ďmďn{3

˜χ

mq.

Now observe that ˜χ

mq “ ˜χ

p3q

˜χ

pmq “ χ

pmq. The function χ

has mean zero on every interval of length three, and tn{3

u is equal to

1 mod 3, hence

1ďmďn{3

˜χ

mq “ 1

THE ERD

OS DISCREPANCY PROBLEM 3

for every i “ 0, . . . , k. Summing in i, we conclude that

j“1

˜χ

pjq “ k ` 1 " log n.

Thus ˜χ

has inﬁnite discrepancy, but the diverg ence is only logarithmic

in the n parameter; indeed it is not diﬃcult to show by a modiﬁcation

of the above arguments that sup

nďN;dPN

j“1

˜χ

pjdq| is comparable

to log N. This can be compared with random sequences f : N Ñ

t´1, `1u, whose discrepancy would be expected to grow like N

1{2`op1q

See the paper of Borwein, Choi, and Coons [1] for further analysis of

functions such as ˜χ

Example 1.5 (Vector-valued Borwein-Choi-Coons example). Let H

be a real Hilbert space with ort honormal basis e

, e

, . . . , let χ

the character from Example 1.4, and let f : N Ñ H be the function

deﬁned by setting f p3

mq :“ χ

pmqe

whenever a “ 0, 1, 2 . . . and m is

coprime to 3 . Thus f takes values in the unit sphere of H. Repeating

the calculation in Example 1.4, we see that if n “ 1 `3 `3

`¨¨¨`3

then

j“1

fpjq “ e

` ¨¨¨ ` e

and hence

›

j“1

fpjq

›

“

k ` 1 "

log n.

Conversely, if n is a natural number and d “ 3

for some l “ 0, 1, . . .

and d

coprime to 3, we see from Pythagoras’s theorem that

›

j“1

fpjdq

›

“

›

iě0:3

ďn

i`l

mďn{3

pmd

›

iě0:3

ďn

1{2

log n.

Thus the discrepancy of this function is inﬁnite and diverges like

log N .

Example 1.6 (Numerical examples). In [8] a sequence fpnq supported

on n ď N :“ 116 0, with values in t´1, `1u in that range, was con-

structed with discrepancy 2 (and a SAT solver was used to show that

1160 was the larg est possible value of N with this property). A similar

sequence with N “ 130 000 of discrepancy 3 was also constructed in

that paper, as well as a sequence with N “ 127 645 of discrepancy 3

that was the restriction to t1, . . . , Nu of a completely multiplicative

sequence taking values in t´1, `1u (with the latt er value o f 127 645

4 TERENCE TAO

being the best possible value of N ). This slow growth in discrepancy

may be compared with the

log N type divergence in Example 1.5.

The above examples suggest that completely multiplicative functions

are an important test case for Theorem 1.1 and Corollary 1.2. Indeed

the Polymath5 project [13] obtained a number of equivalent formula-

tions of the Erd˝os discrepancy pr oblem and its variants, including the

logical equivalence of Theorem 1.1 with the fo llowing assertion involv-

ing such functions. We deﬁne a stoc hastic element of a measurable

space X to be a random variable g taking values in X, or equivalently

a measurable map g : Ω Ñ X from an ambient probability space pΩ, Pq

to X.

Theorem 1.7 (Equivalent form o f vector-valued Erd˝os discrepancy

problem). Let g : N Ñ S

be a stochastic completely multiplicative

function taking values in the unit circle S

:“ tz P C : |z| “ 1u

(where we give the space pS

of functions from N to S

the prod-

uct σ-alg e bra ) . The n

sup

j“1

gpjq

“ `8.

The equivalence between Theorem 1.1 and Theorem 1.7 wa s obtained

in [13] using a Fourier-analytic argument; for the convenience of the

reader, we reproduce this argument in Section 2.

It thus remains to establish Theorem 1.7. To do this, we use a

recent result of the a uthor [14] regarding correlations o f multiplicative

functions:

Theorem 1.8 (Logarithmically averaged nonasymptotic Elliott con-

jecture). [14, Theorem 1.3] Let a

, a

be natural numbers, and let b

, b

be integers such that a

´a

‰ 0. Let ε ą 0, and suppose that A is

suﬃciently large dependi ng on ε, a

, a

, b

. Let x ě ω ě A, and let

, g

: N Ñ C be multiplicative functions with |g

pnq|, |g

pnq| ď 1 for

all n, with g

“non-pretentious” in the sense that

pďx

1 ´ Re g

ppq

χppqp

´it

ě A (1.1)

for all Diric hlet characters χ of period at most A, and all real n umbers

t with |t| ď Ax. Then

x{ωănďx

n ` b

ď ε log ω. (1.2)

This t heorem is a variant of the Elliott conjecture [4] (as corrected

in [11]), which in turn is a g eneralisation of a well known conjecture of

Chowla [3]. See [14] for f ur t her discussion o f this result, the proof of

THE ERD

OS DISCREPANCY PROBLEM 5

which relies on a number of tools, including the recent results in [10],

[11] on mean values of multiplicative functions in short intervals. It

can be viewed as a sort of “inverse theorem” for pair correlations of

multiplicative functions, asserting that such correlations can only be

large when bot h of the multiplicative functions “pretend” to be like

modulated Dirichlet characters n ÞÑ χpnqn

Using this result and a standard van der Corput arg ument, one can

show that the only counterexamples to (1 .7) come from (stochastic)

completely multiplicative functions that usually “pretend” to be like

modulated Dirichlet characters (cf. Examples 1.3 , 1.4). More precisely,

we have

Proposition 1.9 (van der Corput argument). Le t g : N Ñ S

be a

stochastic completely multiplicative function, such that

j“1

gpjq

ď C

(1.3)

for some ﬁnite C ą 0 and all natural numbers n (thus, g is a countere x -

ample to Theorem 1.7). Let ε ą 0, and suppose that X is suﬃciently

large depending on ε, C. Then with probability 1 ´ Opεq, one can ﬁnd

a (stochastic) Dirichlet character χ of period q “ O

C,ε

p1q and a (sto-

chastic) real number t “ O

C,ε

pXq such that

pďX

1 ´ Re gppq

χppqp

´it

C,ε

1. (1.4)

(See Section 1.1 below for our asymptotic notation conventions.)

We give the (easy) derivation of Proposition 1.9 from Theorem 1.8 in

Section 3.

It remains to demonstrate Theorem 1.7 for ra ndo m completely mul-

tiplicative functions g that obey (1.4) with high probability for large

X and small ε. Such functions g can be viewed as (somewhat compli-

cated) generalisations of the Borwein-Choi-Coons example (Example

1.4), and it turns out that a more complicated version of the analysis

in Example 1.4 (or Example 1.5) suﬃces to establish a lower bound

for E|

j“1

gpjq|

(of loga r ithmic type, similar to that in Example 1.5)

which is enough to conclude Theorem 1.7 and hence Theorem 1.1 and

Corollary 1.2. We give this argument in Section 4.

In principle, the argments in [14] provide an eﬀective value for A

as a function o f ε, a

, a

, b

in Theorem 1.8, which would in turn

give an explicit lower bound for the divergence of the discrepancy in

Theorem 1.1 or Corollary 1.2. However, this bound is likely to be far

too weak to match the

log N type divergence observed in Example

1.5. Nevertheless, it seems reasonable to conjecture that the

log N

order of divergence is b est possible for Theorem 1.1 (although it is

6 TERENCE TAO

unclear to the aut hor whether such a slowly diverging example can

also be attained for Corollary 1.2).

Remark 1.10. In [13, 6], Theorem 1.1 was also shown to be equivalent

to the existence of sequences pc

m,d

m,dPN

, pb

nPN

of non-negative reals

such that

m,d

“ 1 ,

“ 8, and such that the real quadratic

form

m,d

` x

` ¨¨¨ ` x

is po sitive semi-deﬁnite. The arguments of this paper thus abstractly

show that such sequences exist, but do not appear to give any explicit

construction for such a sequence.

Remark 1.11. In [6, Conjecture 3.12 ], the following stronger version

of Theorem 1.1 was proposed: if C ě 0 and N is suﬃciently lar ge

depending on C, then f or any matrix pa

1ďi,jďN

of r eals with diagonal

entries equal to 1, there exist homogeneous arithmetic progressions

P “ td, 2d, . . . , ndu and Q “ td

, 2d

, . . . , n

u in t1, . . . , Nu such that

iPP

jPQ

| ě C.

Setting a

:“ xf piq, f pjqy

, we see that this would indeed imply The-

orem 1.1 and thus Corollary 1.2. We do not know how to r esolve this

conjecture, although it appears that a two-dimensional variant of the

Fourier-analytic arguments in Section 2 below can handle the special

case when a

“ ˘1 for all i, j (which would still imply Corollary 1.2

as a special case). We leave this modiﬁcation of the argument to the

interested reader.

1.1. Notation. We adopt the usual asymptotic notation of X ! Y ,

Y " X, or X <

Comments