arXiv:1509.05363v1 [math.CO] 17 Sep 2015
THE ERD
˝
OS DISCREPANCY PROBLEM
TERENCE TAO
Abstract. We show that for any sequence f : N Ñ 1, 1u
taking values in 1, 1u, the discrepancy
sup
n,dPN
ˇ
ˇ
ˇ
ˇ
ˇ
n
ÿ
j1
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
n
ÿ
j1
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). Ev-
ery function f : N Ñ 1, 1u has inﬁn i te discrepancy.
1
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
ˇ
ˇ
ˇ
ˇ
ˇ
n
ÿ
j1
χpjdq
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
χpdq
n
ÿ
j1
χ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 non-
principal 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 Ñ 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
ÿ
j1
˜χ
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
ÿ
i0
ÿ
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
THE ERD
˝
OS DISCREPANCY PROBLEM 3
for every i 0, . . . , k. Summing in i, we conclude that
n
ÿ
j1
˜χ
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
j1
˜χ
3
pjdq| is comparable
to log N. This can be compared with random sequences f : N Ñ
1, 1u, whose discrepancy would be expected to grow like N
1{2op1q
.
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
ÿ
j1
fpjq e
0
¨¨¨  e
k
and hence
n
ÿ
j1
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
ÿ
j1
fpjdq
H
ÿ
iě0:3
i
ďn
e
il
ÿ
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 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 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
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 prod-
uct σ-alg e bra ) . The n
sup
n
E
ˇ
ˇ
ˇ
ˇ
ˇ
n
ÿ
j1
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 con-
jecture). [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
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
ÿ
j1
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 (sto-
chastic) 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 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|
ř
n
j1
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
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 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
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