# The Erdos discrepancy problem

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/the-erdos-discrepancy-problem

- **Authors:** Terrence Tao
- **Published:** 2015
- **Original:** http://arxiv.org/pdf/1509.05363v1.pdf
- **Pages:** 20
- **Annotations:** 0 comments in 0 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/the-erdos-discrepancy-problem

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

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

ˇ ˇ ˇ ˇ ˇ

n ÿ

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 Fourieranalytic reduction, obtained as part of the Polymath5 project on this problem, which reduces the problem to the case when f is replaced by a (stochastic) completely multiplicative function g. The second is a logarithmically averaged version of the Elliott conjecture, 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 argument 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

› › › › ›

n ÿ

j“1

fpjdq

› › › › ›

H

.

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} H “ 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). Every function f : N Ñ t´1, `1u has inﬁn i te discrepancy.

1

#### Page 2

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 results - 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

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

χpjdq

ˇ ˇ ˇ ˇ ˇ “

ˇ ˇ ˇ ˇ ˇ χpdq

n ÿ

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 χ 3 be the nonprincipal Dirichlet character of period 3 (thus χ 3 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 ˜χ 3 : N Ñ t´1, `1u by setting ˜χ 3 ppq :“ χ 3 ppq when p ‰ 3 and ˜χ 3 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

n ÿ

j“1

˜χ 3 pjq

with n :“ 1 `3 `3 2 `¨¨¨`3 k for some large k. Writing j “ 3 i m with m coprime to 3 and i at most k, we can write this sum as

k ÿ

i“0

ÿ

1ďmďn{3 j

˜χ 3 p3 i mq.

Now observe that ˜χ 3 p3 i mq “ ˜χ 3 p3q i ˜χ 3 pmq “ χ 3 pmq. The function χ 3 has mean zero on every interval of length three, and tn{3 j u is equal to 1 mod 3, hence

ÿ

1ďmďn{3 j

˜χ 3 p3 i mq “ 1

#### Page 3

THE ERD ˝ OS DISCREPANCY PROBLEM 3

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

n ÿ

j“1

˜χ 3 pjq “ k ` 1 " log n.

Thus ˜χ 3 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 |

ř n j“1 ˜χ 3 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 ˜χ 3 .

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

be a real Hilbert space with ort honormal basis e 0 , e 1 , e 2 , . . . , let χ 3 be

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

deﬁned by setting f p3 a mq :“ χ 3 pmqe a 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 2 `¨¨¨`3 k ,

then

n ÿ

j“1

fpjq “ e 0 ` ¨¨¨ ` e k

and hence › › › › ›

n ÿ

j“1

fpjq

› › › › ›

H

“

?

k ` 1 "

a

log n.

Conversely, if n is a natural number and d “ 3 l d 1 for some l “ 0, 1, . . .

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

› › › › ›

n ÿ

j“1

fpjdq

› › › › ›

H

“

› › › › › ›

ÿ

iě0:3 i ďn

e i`l

ÿ

mďn{3 i

χ 3 pmd 1 q

› › › › › ›

ď

˜

ÿ

iě0:3 i ďn

1

¸ 1{2

!

a

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

#### Page 4

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 formulations of the Erd˝os discrepancy pr oblem and its variants, including the logical equivalence of Theorem 1.1 with the fo llowing assertion involving 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 1 be a stochastic completely multiplicative function taking values in the unit circle S 1 :“ tz P C : |z| “ 1u (where we give the space pS 1 q N of functions from N to S 1 the product σ-alg e bra ) . The n

sup

n

E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

“ `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 conjecture). [14, Theorem 1.3] Let a 1 , a 2 be natural numbers, and let b 1 , b 2 be integers such that a 1 b 2 ´a 2 b 1 ‰ 0. Let ε ą 0, and suppose that A is suﬃciently large dependi ng on ε, a 1 , a 2 , b 1 , b 2 . Let x ě ω ě A, and let g 1 , g 2 : N Ñ C be multiplicative functions with |g 1 pnq|, |g 2 pnq| ď 1 for all n, with g 1 “non-pretentious” in the sense that

ÿ

pďx

1 ´ Re g 1 ppq χppqp ´it

p ě 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

g 1 pa 1 n ` b 1 qg 2 pa 2 n ` b 2 q n

ˇ ˇ ˇ ˇ ˇ ˇ

ď ε 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

#### Page 5

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 it . 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 1 be a stochastic completely multiplicative function, such that

E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

ď C 2 (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 (stochastic) real number t “ O C,ε pXq such that

ÿ

pďX

1 ´ Re gppq χppqp ´it

p ! 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 multiplicative functions g that obey (1.4) with high probability for large X and small ε. Such functions g can be viewed as (somewhat complicated) 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|

ř n j“1 gpjq| 2 (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 1 , a 2 , b 1 , b 2 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

#### Page 6

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 q m,dPN , pb n q nPN of non-negative reals such that

ř

m,d c m,d “ 1 ,

ř

n b n “ 8, and such that the real quadratic form ÿ

m,d

c m,d px d ` x 2d ` ¨¨¨ ` x md q 2 ´

ÿ

n

b n x 2 n

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 ij q 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 1 , 2d 1 , . . . , n 1 d 1 u in t1, . . . , Nu such that

|

ÿ

iPP

ÿ

jPQ

a ij | ě C.

Setting a ij :“ xf piq, f pjqy H , we see that this would indeed imply Theorem 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 ij “ ˘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 “ OpY q to denote the assertion that |X| ď CY for some constant C. If we need C to depend on an additional par ameter we will denote this by subscripts, e.g. X “ O ε pY q denotes the bound |X| ď C ε Y for some C ε depending on Y . For any real number α, we write epαq :“ e 2πiα . All sums and products will be over t he natural numbers N “ t1, 2, . . . u unless otherwise speciﬁed, with the exception of sums and products over p which is always understood to be prime.

We use d|n to denote the assertion that d divides n, and n pdq to denote the residue class of n modulo d. We use pa, bq to denote the greatest common divisor of a and b.

We will frequently use probabilistic notation such as the expectatio n EX of a random variable X or a probability PpEq of an event E. We will use boldface symbols such as g to refer to random (i.e. stochastic) variables, to distinguish them from deterministic variables, which will be in non-boldf ace.

#### Page 7

THE ERD ˝ OS DISCREPANCY PROBLEM 7

1.2. Acknowledgments. The author is supported by NSF grant DMS-

0649473 and by a Simons Investigator Award. The author thanks Uwe

Stroinski for sugg esting a possible connection between Elliott-type re-

sults and the Erd˝os discrepancy problem, leading to the blog post at

terrytao.wordpress.com/2015/09/11 in which it was shown that a

(non-averaged) version of the Elliott conjecture implied Theorem 1 .1.

Shortly afterwards, t he author obtained the avera ged version of that

conjecture in [14], which turned out to b e suﬃcient to complete the

argument. The author also thanks Timothy Gowers for helpful dis-

cussions and encouragement, as well as Gil Kala i, Uwe Stroinski, and

anonymous blog commenters for corrections and comments on the blog

post that lead to this paper.

2. Fourier analytic reduction

In this section we establish the log ical equivalence between Theorem

1.1 and Theorem 1.7. The arguments here are taken fr om a website

1

of the Polymath5 project [13].

The deduction from Theorem 1.7 fro m Theorem 1.1 is straightfor-

ward: if g is a measurable ma p from a probability space pΩ, Pq to

completely multiplicative functions taking values in S

1

, then for each

natural number n, the random variable gpnq can be identiﬁed with a

unit vector f pnq in the complex Hilbert space H :“ L 2 pΩ, Pq. For any

homogeneous arithmetic progression td, 2d, . . . , ndu, one has

› › › › ›

n ÿ

j“1

fpjdq

› › › › ›

2

H

“ E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjdq

ˇ ˇ ˇ ˇ ˇ

2

“ E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

and we conclude that Theorem 1.7 follows from Theorem 1.1.

Now suppose for contradiction that Theorem 1.7 was true, but The-

orem 1 .1 failed. Thus we can ﬁnd a function f : N Ñ H taking values

in the unit sphere of a Hilbert space H and a ﬁnite quantity C such

that

› › › › ›

n ÿ

j“1

fpjdq

› › › › › H

ď C (2.1)

for all homo geneous arithmetic progr essions d, 2d, . . . , nd. By complex-

ifying H if necessary, we may take H to be a complex Hilbert space. To

obtain the required contradiction, it will suﬃce to construct a random

1 michaelnielsen.org/polymath1/index.php?title=Fourier reduction

#### Page 8

8 TERENCE TAO

completely multiplicative function g taking values in S 1

, such that

E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

! C 1

for all n.

The space of completely multiplicative functions g of magnitude 1

can be identiﬁed with the inﬁnite product pS

1

q

Z

since g is determined by

its values gppq P S

1

at the primes. In particular, this space is compact

metrisable in the product topology. The functions g ÞÑ |

ř n j“1 gpjq| 2

are

continuous in this topology for all n. By vague compactness of proba-

bility measures on compact metrisable spaces (Prokhorov’s theorem),

it thus suﬃces to construct, for each X ě 1, a stochastic completely

multiplicative function g of magnitude 1 such that

E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

! C 1

for all n ď X, where the implied constant is unifor m in n and X.

Let X ě 1, and let p 1 , . . . , p r be the primes up to X. Let M ě X

be a natural number that we assume to be suﬃciently larg e dep ending

on C, X. Deﬁne a function F : pZ{MZq r

Ñ H by the formula

F pa 1 , . . . , a r q :“ fpp

a 1 1 . . . p

a r r q

for a 1 , . . . , a r P t0, . . . , M ´ 1u, thus F takes values in the unit sphere

of H. We also deﬁne the function π : r1, Xs Ñ pZ{MZq

r

by setting

πpp

a 1 1 . . . p

a r r q :“ pa 1 , . . . , a r q whenever p

a 1 1 . . . p

a r r is in r1, Xs :“ tn P N :

1 ď Xu; note that π is well deﬁned for M ě X. Applying (2.1) fo r

n ď X and d of the form p

a 1 1 . . . p a r r with 1 ď a i ď M ´X, we conclude

that

› › › › ›

n ÿ

j“1

F px ` πpjqq

› › › › ›

H

! C 1

for all n ď X and all but O X pM

r´1

q of the M

r

elements x “ pa 1 , . . . , a r q

of pZ{MZq

r

. For the exceptional elements, we have the trivial b ound

› › › › ›

n ÿ

j“1

F px ` πpjqq

› › › › › H

ď X

from the triangle inequality. Square-summing in x, we conclude (if M

is suﬃciently large depending on C, X) that

1

M r

ÿ

xPpZ{MZq r

› › › › ›

n ÿ

j“1

F px ` πpjqq

› › › › ›

2

H

! C 1 (2.2)

#### Page 9

THE ERD ˝ OS DISCREPANCY PROBLEM 9

By Fourier expansion, we can write

F pxq “

ÿ

ξPpZ{MZq r

ˆ F pξqe

ˆ

x ¨ ξ

M

˙

where pa 1 , . . . , a r q ¨ pξ 1 , . . . , ξ r q :“ a 1 ξ 1 ` ¨¨¨ ` a r ξ r , and the Fourier

transform ˆ F : pZ{MZq r Ñ H is deﬁned by the formula

ˆ F pξq :“

1

M r

ÿ

xPpZ{MZq r

F pxqe

ˆ

´

x ¨ ξ

M

˙

.

A routine Fourier-analytic calculation (using the Plancherel identity)

then allows us to write the left-hand side of (2 .2) as

ÿ

ξPpZ{MZq r

} ˆ F pξq} 2 H

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

e

ˆ

πpjq ¨ ξ

M

˙ ˇ ˇ ˇ ˇ ˇ

2

.

On the other hand, from a further application of the Plancherel identity

we have

ÿ

ξPpZ{MZq r

} ˆ F pξq} 2 H “ 1

and so we can interpret } ˆ F pξq} 2 H as the probability distribution of a

random frequency ξ “ pξ 1 , . . . , ξ r q P pZ{MZq r

. The estimate (2.2)

now takes the form

E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

e

ˆ

πpjq ¨ ξ

M

˙ ˇ ˇ ˇ ˇ ˇ

2

! C 1

for all n ď N . If we then deﬁne the stochastic completely multiplicative

function g by setting gpp j q :“ epξ j {Mq for j “ 1, . . . , r, and gppq :“ 1

for all other primes, we obtain

E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

! C 1

for all n ď X, as desired.

Remark 2.1. It is instructive to see how the above argument breaks

down when one tries to use the Dirichlet chara cter example in Example

1.3. While χ often has magnitude 1 in the ordinary (Archimedean)

sense, the function pa 1 , . . . , a r q ÞÑ χpp a 1 1 . . . p a r r q is almost always zero,

since the argument p a 1 1 . . . p a r r of χ is likely to be a multiple of q. As

such, the quantity } ˆ F pξq} 2 H sums to something much less than 1, and

one does not generate a stochastic completely multiplicative function

g with bo unded discrepancy.

#### Page 10

10 TERENCE TAO

3. Applying the Elliott-type conjecture

In this section we prove Propo sition 1.9. Let g, C, ε be as in that

proposition. Let H ě 1 be a moderately large na t ural number depend-

ing on ε to be chosen later, and suppose that X is suﬃciently large

depending on H, ε. From (1.3) and the triangle inequality we have

E

ÿ

?

XďnďX

1

n

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

! C log X

so fr om Markov’s inequality we see with probability 1 ´ Opεq that

ÿ

?

XďnďX

1

n

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

! C,ε log X.

Let us condition to this event. Shifting n by H, we conclude (for X

large enough) that

ÿ

?

XďnďX

1

n

ˇ ˇ ˇ ˇ ˇ

n`H ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

! C,ε log X

and hence by the triangle inequality

ÿ

?

XďnďX

1

n

ˇ ˇ ˇ ˇ ˇ

n`H ÿ

j“n`1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

! C,ε log X,

which we rewrite as

ÿ

?

XďnďX

1

n

ˇ ˇ ˇ ˇ ˇ

H ÿ

h“1

gpn ` hq

ˇ ˇ ˇ ˇ ˇ

2

! C,ε log X. (3.1)

We can expand out the left-hand side of (3.1) as

ÿ

h 1 ,h 2 Pr1,Hs

ÿ

?

XďnďX

gpn ` h 1 q gpn ` h 2 q

n

.

The diagonal term h 1 , h 2 contributes a term of size " H log X to this

expression. Thus, choo sing H to be a suﬃciently large quantity de-

pending on C, ε, we can apply the triangle inequality and pigeonhole

principle to ﬁnd distinct (and stocha stic) h 1 , h 2 P r1, Hs such that

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

?

XďnďX

gpn ` h 1 q gpn ` h 2 q

n

ˇ ˇ ˇ ˇ ˇ ˇ

" C,ε,H 1.

By symmetry we can take h 2 ą h 1 . Setting h :“ h 2 ´ h 1 and shifting

n by h 1 , we conclude (for X large enough, noting that the diﬀerence

#### Page 11

THE ERD ˝ OS DISCREPANCY PROBLEM 11

between 1 n and 1 n´h 1 adds up to a negligible error) that ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

? XďnďX

gpnq gpn ` hq

n

ˇ ˇ ˇ ˇ ˇ ˇ

" ε 1.

Applying Theorem 1.8 in the contrapositive, we obtain the claim. (It is easy to check that the quantit ies χ, t produced by Theorem 1.8 can be selected to be measurable, for instance one can use continuity t o restrict t to be rational and then take a minimal choice of pχ, tq with respect to some explicit well-or dering of the countable set of possible pairs pχ, tq.)

4. A generalised Borwein-Choi-Coons analysis

We can now complete the proof of Theorem 1.7 (and thus Theorem 1.1 and Corollary 1.2). Our arguments here will be based on those from a website 2 of the Polymath5 project [13], which treated the case in which the functions g and χ appearing in Proposition 1.9 were realvalued (and the quantity t was set to zero).

Suppose for contradiction that Theorem 1.7 failed, then we can ﬁnd a constant C ą 0 and a stochastic completely multiplicative function g : N Ñ S 1 such that

E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

ď C 2

for all natural numbers n. We now allow a ll implied constants to depend on C, thus

E

ˇ ˇ ˇ ˇ ˇ

n ÿ

j“1

gpjq

ˇ ˇ ˇ ˇ ˇ

2

! 1

for all n.

We will need the following larg e and small parameters, selected in the fo llowing order:

‚ A quantity 0 ă ε ă 1 {2 t hat is suﬃciently small depending on

C. ‚ A natural number H ě 1 that is suﬃciently large depending on

C, ε. ‚ A quantity 0 ă δ ă 1{2 that is suﬃciently small depending on

C, ε, H. ‚ A natural number k ě 1 that is suﬃciently large depending on

C, ε, H, δ. ‚ A real number X ě 1 that is suﬃciently large depending on

C, ε, H, δ, k.

2 michaelnielsen.org/polymath1/index.php?title= Bounded discrepancy multiplicative functions do not correlate with characters

#### Page 12

12 TERENCE TAO

We will implicitly assume these size relationships in the sequel t o simplify the computations, for instance by absorbing a smaller error term into a larger if the latter dominates the for mer under the above assumptions. The reader may wish to keep the hierarchy

C ! 1 ε ! H ! 1 δ ! k ! X

in mind in the arguments that follow.

By Proposition 1.9, we see with probability 1´Opεq that there exists a Dirichlet character χ of period q “ O ε p1q and a real number t “ O ε pXq such that

ÿ

pďX

1 ´ Re gppq χppqp ´it

p ! ε 1. (4.1)

By reducing χ if necessary we may assume that χ is primitive.

It will be convenient to cut down the size of t.

Lemma 4.1. With probability 1 ´ Opεq, one has

t “ O ε pX δ q. (4.2)

Proof. By Propo sition 1.9 with X replaced by X δ , we see that with probability 1 ´ Opεq, one can ﬁnd a Dirichlet character χ 1 of period q 1 “ O ε p1q and a real number t 1 “ O ε pX δ q such that

ÿ

pďX δ

1 ´ Re gppq χ 1 ppqp ´it 1

p ! ε 1.

We may restrict to the event that |t 1 ´ t| ě X δ , since we are done otherwise. Applying the pretentious triang le inequality (see [7, Lemma 3.1]), we conclude that

ÿ

pďX δ

1 ´ Re χppq χ 1 ppqp ´ipt 1 ´tq

p ! ε 1.

However, from the Vinogradov-Korobov zero-free regio n for Lp¨, χ χ 1 q (see [12, §9.5]) and the bounds X δ ď |t 1 ´t| ! ε X, it is not diﬃcult to show that

ÿ

pďX δ

1 ´ Re χppq χ 1 ppqp ´ipt 1 ´tq

p " log log X

if X is suﬃciently large depending on ε, δ, a contra diction. The claim follows. 

Let us now condition to the probability 1´Opεq event that χ, t exist obeying (4.1) a nd the bound (4.2).

#### Page 13

THE ERD ˝ OS DISCREPANCY PROBLEM 13

The bound (4.1) asserts that g “pretends” to be like the completely

multiplicative function n ÞÑ χppqp it

. We can formalise this by making

the fa cto r isation

gpnq :“ ˜ χpnqn

it

hpnq (4.3)

where ˜ χ is the completely multiplicative function of ma gnitude 1 de-

ﬁned by setting ˜ χppq :“ χppq for p ∤ q and ˜ χppq :“ gppqp

´it

for p|q,

and h is the completely multiplicative function of magnitude 1 deﬁned

by setting hppq :“ gp p q χppqp ´it

for p ∤ q, and hppq “ 1 for p|q. The

function ˜ χ should be compared with the function ˜χ 3 in Example 1.4

(or the function f in Example 1.5).

With this notation, the bound (4.1) simpliﬁes to

ˇ ˇ ˇ ˇ ˇ

ÿ

pďX

1 ´ Re hppq

p

ˇ ˇ ˇ ˇ ˇ

! ε 1. (4.4)

We now perform some manipulatio ns to remove the n

it

and h factors

from g and isolate medium-length sums of the ˜ χ factor, which are

more tractable to compute with than the corresponding sums of g;

then we will perform more computations to arrive at an expression

just involving χ which we will be able to evalua te fairly easily.

We ﬁrst work to eliminate the role of n

it

. From (1.3) and the triangle

inequality we have

E

1

H

ÿ

HăH 1 ď2H

ˇ ˇ ˇ ˇ ˇ

H 1 ÿ

m“1

gpn ` mq

ˇ ˇ ˇ ˇ ˇ

2

! 1

for all n (even after conditioning to the 1 ´ Opεq event mentioned

above). The

1 H

ř

HăH 1 ď2H averaging will not be used until much later

in the argument, and the reader may wish to ignore it for the time

being.

By (4.3), the above estimate can be written as

E

1

H

ÿ

HăH 1 ď2H

ˇ ˇ ˇ ˇ ˇ

H 1 ÿ

m“1

˜ χpn ` mqpn ` mq

it

hpn ` mq

ˇ ˇ ˇ ˇ ˇ

2

! 1.

For n ě X 2δ

, we can use (4.2) and Taylor expansion to conclude that

pn ` mq

it

“ n

it

` O ε,H,δ pX

´δ

q. The contribution of the erro r term is

negligible, thus

E

1

H

ÿ

HăH 1 ď2H

ˇ ˇ ˇ ˇ ˇ

H 1 ÿ

m“1

˜ χpn ` mqn

it

hpn ` mq

ˇ ˇ ˇ ˇ ˇ

2

! 1

for all n ě X

2δ

. We can facto r out the n

it

factor to obtain

E

1

H

ÿ

HăH 1 ď2H

ˇ ˇ ˇ ˇ ˇ

H 1 ÿ

m“1

˜ χpn ` mqhpn ` mq

ˇ ˇ ˇ ˇ ˇ

2

! 1.

#### Page 14

14 TERENCE TAO

For n ă X 2δ we can crudely bound the left- hand side by H 2 . If δ is suﬃciently small, we can then sum weighted by 1 n 1`1{ log X and conclude that

E

1 H

ÿ

HăH 1 ď2H

ÿ

n

ˇ ˇ ˇ

ř H 1 m“1 ˜ χpn ` mqhpn ` mq

ˇ ˇ ˇ

2

n 1`1{log X ! log X.

(The zeta function type weight of 1 n 1`1{ log X will be convenient later in the argument when one has to perform some multiplicative number theory, as the relevant sums can be computed quite directly and easily using Euler products.) Thus, with probability 1 ´ Opεq, one has

1 H

ÿ

HăH 1 ď2H

ÿ

n

ˇ ˇ ˇ

ř H 1 m“1 ˜ χpn ` mqhpn ` mq

ˇ ˇ ˇ

2

n 1`1{log X ! ε log X.

We condition to this event. We have successfully eliminated the role of n it ; we now work to eliminate h. To do this we will have to partially decouple the ˜ χ and h factors in the above expression, which can be done 3 by exploiting the almo st periodicity properties of ˜ χ as follows. Call a residue class a p q k q bad if a ` m is divisible by p k for some p|q and 1 ď m ď H, and good otherwise. We restrict n to good residue classes, thus

1 H

ÿ

HăH 1 ď2H

ÿ

aPr1,q k s, good

ÿ

n“a pq k q

ˇ ˇ ˇ

ř H 1 m“1 ˜ χpn ` mqhpn ` mq

ˇ ˇ ˇ

2

n 1`1{log X

! ε log X.

By Cauchy-Schwarz, we conclude t hat

1 H

ÿ

HăH 1 ď2H

ÿ

aPr1,q k s, good

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

n“a pq k q

ř H 1 m“1 ˜ χpn ` mqhpn ` mq

n 1`1{log X

ˇ ˇ ˇ ˇ ˇ ˇ

2

! ε

log 2 X q k .

Now we claim that for n in a given good residue class a pq k q, the quantity ˜ χpn ` mq does not depend on n. Indeed, by hypot hesis, pn `m, q k q “ pa `m, q k q is not divisible by p k for any p|q and is thus a

3 The argument here was loosely inspired by the Maier matrix method [9].

#### Page 15

THE ERD ˝ OS DISCREPANCY PROBLEM 15

factor of q k´1 , and n`m pn`m,q k q “ n`m pa`m,q k q is coprime to q. We then factor

˜ χpn ` mq “ ˜ χppn ` m, q k qq ˜ χ

ˆ

n ` m pn ` m, q k q

˙

“ ˜ χppa ` m, q k qqχ

ˆ

n ` m pa ` m, q k q

˙

“ ˜ χppa ` m, q k qqχ

ˆ

a ` m pa ` m, q k q

˙

where in the last line we use the periodicity of χ. Thus we have ˜ χpn ` mq “ ˜ χpa ` mq, and so

1 H

ÿ

HăH 1 ď2H

ÿ

aPr1,q k s, good

ˇ ˇ ˇ ˇ ˇ ˇ

H 1 ÿ

m“1

˜ χpa ` mq

ÿ

n“a pq k q

hpn ` mq n 1`1{log X

ˇ ˇ ˇ ˇ ˇ ˇ

2

! ε

log 2 X q k .

Shifting n by m, we see that

ÿ

n“a pq k q

hpn ` mq n 1`1{log X “

ÿ

n“a`m pq k q

hpnq n 1`1{log X ` O H p1q

and t hus (for X large enough)

1 H

ÿ

HăH 1 ď2H

ÿ

aPr1,q k s, good

ˇ ˇ ˇ ˇ ˇ ˇ

H 1 ÿ

m“1

˜ χpa ` mq

ÿ

n“a`m pq k q

hpnq n 1`1{log X

ˇ ˇ ˇ ˇ ˇ ˇ

2

! ε

1 q k log 2 X .

(4.5)

Now, we p erform some mult iplicative number theory to understand the innermost sum in (4.5). From taking Euler products, we have

ÿ

n

hpnq n 1`1{log X “ S

where S is the Euler product

S :“

ź

p

ˆ

1 ´ hppq p 1`1{log X

˙ ´1

.

From (4.4) and Mertens’ theorem o ne can easily verify that

log X ! ε |S| ! ε log X. (4.6) More generally, for any Dirichlet character χ 1 we have ÿ

n

χ 1 pnqhpnq n 1`1{log X “

ź

p

ˆ

1 ´ hppqχ 1 ppq p 1`1{log X

˙ ´1

.

#### Page 16

16 TERENCE TAO

Using (4.4) and the prime number theorem in arithmetic progressions, we conclude that ÿ

n

χ 1 pnqhpnq n 1`1{log X ! q,k 1

for any non-principal character χ 1 of period dividing q k ; for a principal character χ 0 of period r dividing q k we have ÿ

n

χ 0 hpnq n 1`1{log X “

ź

p∤r

ˆ

1 ´ hppq p 1`1{log X

˙ ´1

“ S

ź

p|r

ˆ

1 ´ 1 p 1`1{log X

˙

“ Sp1 ` O k p 1 log X qq

ź

p|r

ˆ

1 ´ 1 p

˙

“ φprq

r S ` O k p1q

thanks to (4.6) and the fact that hppq “ 1 for all p|r. By expansion into Dirichlet characters we conclude that

ÿ

n“b prq

hpnq n 1`1{log X “ 1 r S ` O k p1q

for all r|q k and primitive residue classes b prq. For non-primitive residue classes b prq, we write r “ pb, rqr 1 and b “ pb, rqb 1 . The previous arguments t hen give

ÿ

n“b 1 prq 1

hpnq n 1`1{log X “ 1 r 1 S ` O k p1q

which since hppb, rqq “ 1 gives (again using (4.6))

ÿ

n“b prq

hpnq n 1`1{log X “ 1 r S ` O k p1q

for all b prq (not necessarily primitive). Inserting this back into (4.5) we see that

1 H

ÿ

HăH 1 ď2H

ÿ

aPr1,q k s good

ˇ ˇ ˇ ˇ ˇ

H 1 ÿ

m“1

˜ χpa ` mq

ˆ

1 q k S ` O q,k p1q

˙ ˇ ˇ ˇ ˇ ˇ

2

! ε

log 2 X q k

and t hus by (4.6) we conclude (for X large enough) that

1 q k

ÿ

aPr1,q k s good

1 H

ÿ

HăH 1 ď2H

ˇ ˇ ˇ ˇ ˇ

H 1 ÿ

m“1

˜ χpa ` mq

ˇ ˇ ˇ ˇ ˇ

2

! ε 1. (4.7)

We have now eliminated both t and h. The remaining task is to establish some lower bound on the discrepancy of medium-length sums

#### Page 17

THE ERD ˝ OS DISCREPANCY PROBLEM 17

of ˜ χ that will contradict (4.7). As mentioned above, this will be a more complicated variant of the analysis in Examples 1.4, 1.5, in which the perfect orthogonality in Example 1.5 is replaced by an almost orthogonality argument.

We turn to the details. We ﬁrst expand (4.7) to obtain

1 H

ÿ

HăH 1 ď2H

ÿ

m 1 ,m 2 Pr1,H 1 s

ÿ

aPr1,q k s, good

˜ χpa ` m 1 q ˜ χpa ` m 2 q ! ε q k .

Write d 1 :“ pa ` m 1 , q k q and d 2 :“ pa ` m 2 , q k q, thus d 1 , d 2 |q k´1 and for i “ 1, 2 we have

˜ χpa ` m i q “ ˜ χpd i qχ

ˆ

a ` m i d i

˙

.

We thus have

ÿ

d 1 ,d 2 |q k´1

˜ χpd 1 q ˜ χpd 2 q 1 H

ÿ

HăH 1 ď2H

ÿ

m 1 ,m 2 Pr1,H 1 s ÿ

aPr1,q k s, good:pa`m 1 ,q k q“d 1 ,pa`m 2 ,q k q“d 2

χ

ˆ

a ` m 1 d 1

˙

χ

ˆ

a ` m 2 d 2

˙

! ε q k .

(4.8)

We reinstate the bad a. The number of such a is at most Op2 ´k q k q, so their total cont ribution here is O H p2 ´k q k q which is negligible, thus we may drop the requirement in (4.8) that a is good.

For d 1 ě q k{10 or d 2 ě q k{10 , the inner sum in (4.8) is O H pq ´k{10 q k q, which by the divisor bound

ř

d|n 1 “ n op1q gives a neglig ible contribution. Thus we may restrict t o the case when d 1 , d 2 ă q k{10 . Note that as χ is already restricted to numbers coprime to q, and d 1 , d 2 divide q k´1 , we may replace the constraints pa ` m i , q k q “ d i with d i |a ` m i for i “ 1, 2.

We consider the contribution of an oﬀ-diagonal term d 1 ‰ d 2 for a ﬁxed choice of m 1 , m 2 . To handle these terms we expand the nonprincipal character χpnq as a linear combination of epξn{qq for ξ P pZ{qZq ˆ with (stochastic) Fourier coeﬃcients Op1q. Thus we can expand out

ÿ

aPr1,q k s:d 1 |a`m 1 ;d 2 |a`m 2

χ

ˆ

a ` m 1 d 1

˙

χ

ˆ

a ` m 2 d 2

˙

as a linear combination of Op1q expressions of t he form

ÿ

aPr1,q k s:d 1 |a`m 1 ;d 2 |a`m 2

e

ˆ

ξ 1 q

a ` m 1 d 1

´ ξ 2 q

a ` m 2 d 2

˙

with ξ 1 , ξ 2 P pZ{qZq ˆ and coeﬃcients of size Op1q.

#### Page 18

18 TERENCE TAO

The constraints d 1 |a ` m 1 ; d 2 |a ` m 2 are either inconsistent, or constrain a to a single residue class a “ b prd 1 , d 2 sq by the Chiense remainder theorem. Writing a “ b ` nrd 1 , d 2 s, we have

e

ˆ

ξ 1 q

a ` m 1 d 1

´ ξ 2 q

a ` m 2 d 2

˙

“ e

ˆ

θ ` n q

ˆ

ξ 1

rd 1 , d 2 s d 1

´ ξ 2

rd 1 , d 2 s d 2

˙˙

for some phase θ that can depend on b, m 1 , m 2 , d 1 , d 2 , q, ξ 1 , ξ 2 but is independent of n. If d 1 ‰ d 2 , then at least one of the two quantities rd 1 ,d 2 s d 1 and rd 1 ,d 2 s d 2 is divisible by a prime p|q that does not divide the other quantity. Therefore ξ 1 rd 1 ,d 2 s d 1 ´ ξ 2 rd 1 ,d 2 s d 2 cannot be divisible by p, and thus by q. We can then sum the geometric series in n (or a) and conclude that

ÿ

aPr1,q k s:d 1 |a`m 1 ;d 2 |a`m 2

e

ˆ

ξ 1 q

a ` m 1 d 1

´ ξ 2 q

a ` m 2 d 2

˙

! rd 1 , d 2 s ! q k{5

and so by the divisor bound the oﬀ-diagonal terms d 1 ‰ d 2 contribute at most O H pq k{5`opkq q to (4.8). For k large, this is negligible, and thus we only need to consider the diago nal contribution d 1 “ d 2 ă q k{10 . Here the ˜ χpd 1 q ˜ χpd 2 q t erms helpfully cancel, and we obtain

ÿ

d|q k´1 :dăq k{10

1 H

ÿ

HăH 1 ď2H

ÿ

m 1 ,m 2 Pr1,H 1 s

ÿ

aPr1,q k s:d|a`m 1 ,a`m 2

χ

´ a ` m 1 d

¯

χ

´ a ` m 2 d

¯

! ε q k .

We have now eliminated ˜ χ, leaving only the Dirichlet character χ which is much easier to work with. We gather terms and write the left-hand side as

ÿ

d|q k´1 :dăq k{10

1 H

ÿ

HăH 1 ď2H

ÿ

aPr1,q k s

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

mPr1,H 1 s:d|a`m

χ

´ a ` m

d

¯

ˇ ˇ ˇ ˇ ˇ ˇ

2

.

The summand in d is now non-negative. We can thus throw away all the d except of the form d “ q i with q i ă

?

H, to conclude that

ÿ

i:q i ă ? H

1 H

ÿ

HăH 1 ď2H

ÿ

aPr1,q k s

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

mPr1,H 1 s:q i |a`m

χ

ˆ

a ` m

q i

˙ ˇ ˇ ˇ ˇ ˇ ˇ

2

! ε q k .

It is now that we ﬁnally take advantage of the averaging 1 H

ř

HăH 1 ď2H to simplify the m summation. Observe from the triangle inequality

#### Page 19

THE ERD ˝ OS DISCREPANCY PROBLEM 19

that for any H 1

P rH, 3H{2s and a P r1, q k

s one has

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

H 1 ăaďH 1 `q i :q i |a`m

χ

ˆ

a ` m

q i

˙

ˇ ˇ ˇ ˇ ˇ ˇ

2

!

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

mPr1,H 1 s:q i |a`m

χ

ˆ

a ` m

q i

˙

ˇ ˇ ˇ ˇ ˇ ˇ

2

`

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

mPr1,H 1 `q i s:q i |a`m

χ

ˆ

a ` m

q i

˙

ˇ ˇ ˇ ˇ ˇ ˇ

2

;

summing over i, H

1 , a we conclude that

ÿ

i:q i ă

?

H

1

H

ÿ

H 1 PrH,3H{2s

ÿ

aPr1,q k s

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

H 1 ămďH 1 `q i :q i |a`m

χ

ˆ

a ` m

q i

˙

ˇ ˇ ˇ ˇ ˇ ˇ

2

! ε q

k

.

In particular, by the pigeonhole principle t here exists H

1

P rH , 3H{2s

such that

ÿ

i:q i ă

?

H

ÿ

aPr1,q k s

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

H 1 ămďH 1 `q i :q i |a`m

χ

ˆ

a ` m

q i

˙

ˇ ˇ ˇ ˇ ˇ ˇ

2

! ε q

k

.

Shifting a by H

1

and discarding some terms, we conclude that

ÿ

i:q i ă

?

H

ÿ

aPr1,q k {2s

ˇ ˇ ˇ ˇ ˇ ˇ

ÿ

0ămďq i :q i |a`m

χ

ˆ

a ` m

q i

˙

ˇ ˇ ˇ ˇ ˇ ˇ

2

! ε q

k .

Observe that f or a ﬁxed a there is exactly one m in the inner sum, and

a`m

q i “

Y

a q i

]

` 1. Thus we have

ÿ

i:q i ă

?

H

ÿ

aPr1,q k {2s

ˇ ˇ ˇ ˇ χ

ˆZ

a

q i

^

` 1

˙ ˇ ˇ ˇ ˇ

2

! ε q

k

.

Making the change of varia bles b :“

Y

a q i

]

` 1 and discarding some

terms, we thus have

ÿ

i:q i ă

?

H

q

i

ÿ

bPr1,q k´i {4s

|χpbq|

2

! ε q

k

.

But b ÞÑ |χpbq| 2

is periodic of period q with mean " 1, thus

ÿ

bPr1,q k´i {4s

|χpbq|

2

" q

k´i

which when combined with the preceding bound yields

ÿ

i:q i ă

?

H

1 ! ε 1,

#### Page 20

20 TERENCE TAO

which leads to a contradiction for H large enough (note the logarithmic growth in H here, which is consistent with the growth rates in Example 1.5). The claim follows.

References

[1] P. Borwein, S. Choi, M. Coons, Completely multiplicat ive functions taking

values in t1, 1u, Trans. Amer. Math. Soc. 362 (2010), no. 12, 6279–6291. [2] D. A. Burgess, On character sums and primitive roots, Proc. London Math.

Soc. (3), 12 (1962), 179–192. [3] S. Chowla, The Riemann hypothesis and Hilbert’s tenth problem, Gordon

and Breach, New York, 1965. [4] P. D. T. A. Elliott, On the correlation of multiplicative functions, Notas Soc.

Mat. Chile, Notas de la Sociedad de Matem´atica de Chile, 11 (1992), 1–11. [5] P. Erd˝os, Some uns olved problems, Michigan Math. J. 4 (1957), 299–300. [6] W. T. Gowers, Erd˝os and arithmetic progressions, Erd˝os Centennial, Bolyai

Society Mathematical Studies, 25, L. Lovasz, I. Z. Ruzsa, V. T. Sos eds., Springer 2013, pp. 265–287. [7] A. Granville, K. Soundararajan, Large character sums: pretentious characters

and the P´olya-Vinogradov theorem, J. Amer. Math. Soc. 20 (2007), no. 2, 357–384. [8] B. Konev, A. Lisitsa, Computer-aided proof of Erd˝os discrepancy properties,

Artiﬁcial Intelligence 224 (2015), 103–118. [9] H. Maier, Chains of large gaps between consecutive primes, Advances in Math-

ematics 39 (1981), 257–269. [10] K. Matom¨aki, M. Radziwi l l, Multiplicative functions in short intervals,

preprint. arXiv:1501.04585. [11] K. Matom¨aki, M. Radziwi l l, T. Tao, An averaged form of Chowla’s conjecture,

preprint. arXiv:1503.05121. [12] H. Montgomery, Ten lectures on the interface between analytic number the-

ory and harmonic analysis, volume 84 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1994. [13] D.H.J. Polymath, michaelnielsen.org/polymath1/index.php?title=

The Erd%C5%91s discrepancy problem [14] T. Tao, The logarithmically averaged Chowla and Elliott conjectures for two-

point correlations, preprint.

Department of Mathematics, UCLA, 405 Hilgard Ave, Los Angeles CA 90095, USA

E-mail address: tao@math.ucla.edu

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/the-erdos-discrepancy-problem. More annotated papers: https://fermatslibrary.com/llms.txt
