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

Hilbert space H, define the disc repancy of f to be the quantity

sup

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

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

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

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,

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).

principal Dirichlet character of period 3 (thus χ

consider t he sum

˜χ

with n :“ 1 `3 `3

for some large k. Writing j “ 3

Now observe that ˜χ

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

1 mod 3, hence

1

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

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.

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.

problem). Let g : N Ñ S

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

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

: N Ñ C be multiplicative functions with |g

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

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

(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

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

also be attained for Corollary 1.2).

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

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

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

and we conclude that Theorem 1.7 follows from Theorem 1.1.

obtain the required contradiction, it will suffice to construct a random

completely multiplicative function g taking values in S

1

for all n.

The space of completely multiplicative functions g of magnitude 1

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

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

it thus suffices to construct, for each X ě 1, a stochastic completely

multiplicative function g of magnitude 1 such that

1

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

for a

that

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

we have

and so we can interpret }

now takes the form

1

for all n ď N . If we then define the stochastic completely multiplicative

function g by setting gpp

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

of χ is likely to be a multiple of q. As

such, the quantity }

one does not generate a stochastic completely multiplicative function