The Chowla conjecture asserts that all non-trivial correlations of the Liouville function are asymptotically negligible; for instance, it asserts that

\displaystyle \sum_{n \leq X} \lambda(n) \lambda(n+h) = o(X)

as {X \rightarrow \infty} for any fixed natural number {h}. This conjecture remains open, though there are a number of partial results (e.g. these two previous results of Matomaki, Radziwill, and myself).

A natural generalisation of Chowla’s conjecture was proposed by Elliott. For simplicity we will only consider Elliott’s conjecture for the pair correlations

\displaystyle \sum_{n \leq X} g(n) \overline{g}(n+h).

For such correlations, the conjecture was that one had

\displaystyle \sum_{n \leq X} g(n) \overline{g}(n+h) = o(X) \ \ \ \ \ (1)

as {X \rightarrow \infty} for any natural number {h}, as long as {g} was a completely multiplicative function with magnitude bounded by {1}, and such that

\displaystyle \sum_p \hbox{Re} \frac{1 - g(p) \overline{\chi(p)} p^{-it}}{p} = +\infty \ \ \ \ \ (2)

for any Dirichlet character {\chi} and any real number {t}. In the language of “pretentious number theory”, as developed by Granville and Soundararajan, the hypothesis (2) asserts that the completely multiplicative function {g} does not “pretend” to be like the completely multiplicative function {n \mapsto \chi(n) n^{it}} for any character {\chi} and real number {t}. A condition of this form is necessary; for instance, if {g(n)} is precisely equal to {\chi(n) n^{it}} and {\chi} has period {q}, then {g(n) \overline{g}(n+q)} is equal to {1_{(n,q)=1} + o(1)} as {n \rightarrow \infty} and (1) clearly fails. The prime number theorem in arithmetic progressions implies that the Liouville function obeys (2), and so the Elliott conjecture contains the Chowla conjecture as a special case.

As it turns out, Elliott’s conjecture is false as stated, with the counterexample {g} having the property that {g} “pretends” locally to be the function {n \mapsto n^{it_j}} for {n} in various intervals {[1, X_j]}, where {X_j} and {t_j} go to infinity in a certain prescribed sense. See this paper of Matomaki, Radziwill, and myself for details. However, we view this as a technicality, and continue to believe that certain “repaired” versions of Elliott’s conjecture still hold. For instance, our counterexample does not apply when {g} is restricted to be real-valued rather than complex, and we believe that Elliott’s conjecture is valid in this setting. Returning to the complex-valued case, we still expect the asymptotic (1) provided that the condition (2) is replaced by the stronger condition

\displaystyle \sup_{|t| \leq X} |\sum_{p \leq X} \hbox{Re} \frac{1 - g(p) \overline{\chi(p)} p^{-it}}{p}| \rightarrow +\infty

as {X \rightarrow +\infty} for all fixed Dirichlet characters {\chi}. In our paper we supported this claim by establishing a certain “averaged” version of this conjecture; see that paper for further details. (See also this recent paper of Frantzikinakis and Host which establishes a different averaged version of this conjecture.)

One can make a stronger “non-asymptotic” version of this corrected Elliott conjecture, in which the {X} parameter does not go to infinity, or equivalently that the function {g} is permitted to depend on {X}:

Conjecture 1 (Non-asymptotic Elliott conjecture) Let {\varepsilon > 0}, let {A \geq 1} be sufficiently large depending on {\varepsilon}, and let {X} be sufficiently large depending on {A,\varepsilon}. Suppose that {g} is a completely multiplicative function with magnitude bounded by {1}, such that

\displaystyle \inf_{|t| \leq AX} |\sum_{p \leq X} \hbox{Re} \frac{1 - g(p) \overline{\chi(p)} p^{-it}}{p}| \geq A

for all Dirichlet characters {\chi} of period at most {A}. Then one has

\displaystyle |\sum_{n \leq X} g(n) \overline{g(n+h)}| \leq \varepsilon X

for all natural numbers {1 \leq h \leq 1/\varepsilon}.

The {\varepsilon}-dependent factor {A} in the constraint {|t| \leq AX} is necessary, as can be seen by considering the completely multiplicative function {g(n) := n^{2iX}} (for instance). Again, the results in my previous paper with Matomaki and Radziwill can be viewed as establishing an averaged version of this conjecture.

Meanwhile, we have the following conjecture that is the focus of the Polymath5 project:

Conjecture 2 (Erdös discrepancy conjecture) For any function {f: {\bf N} \rightarrow \{-1,+1\}}, the discrepancy

\displaystyle \sup_{n,d \in {\bf N}} |\sum_{j=1}^n f(jd)|

is infinite.

It is instructive to compute some near-counterexamples to Conjecture 2 that illustrate the difficulty of the Erdös discrepancy problem. The first near-counterexample is that of a non-principal Dirichlet character {f(n) = \chi(n)} that takes values in {\{-1,0,+1\}} rather than {\{-1,+1\}}. For this function, one has from the complete multiplicativity of {\chi} that

\displaystyle |\sum_{j=1}^n f(jd)| = |\sum_{j=1}^n \chi(j) \chi(d)|

\displaystyle \leq |\sum_{j=1}^n \chi(j)|.

If {q} denotes the period of {\chi}, then {\chi} has mean zero on every interval of length {q}, and thus

\displaystyle |\sum_{j=1}^n f(jd)| \leq |\sum_{j=1}^n \chi(j)| \leq q.

Thus {\chi} has bounded discrepancy.

Of course, this is not a true counterexample to Conjecture 2 because {\chi} can take the value {0}. Let us now consider the following variant example, which is the simplest member of a family of examples studied by Borwein, Choi, and Coons. Let {\chi = \chi_3} be the non-principal Dirichlet character of period {3} (thus {\chi(n)} equals {+1} when {n=1 \hbox{ mod } 3}, {-1} when {n = 2 \hbox{ mod } 3}, and {0} when {n = 0 \hbox{ mod } 3}), and define the completely multiplicative function {f = \tilde \chi: {\bf N} \rightarrow \{-1,+1\}} by setting {\tilde \chi(p) := \chi(p)} when {p \neq 3} and {\tilde \chi(3) = +1}. This is about the simplest modification one can make to the previous near-counterexample to eliminate the zeroes. Now consider the sum

\displaystyle \sum_{j=1}^n \tilde \chi(j)

with {n := 1 + 3 + 3^2 + \dots + 3^k} for some large {k}. Writing {j = 3^a m} with {m} coprime to {3} and {a} at most {k}, we can write this sum as

\displaystyle \sum_{a=0}^k \sum_{1 \leq m \leq n/3^j} \tilde \chi(3^a m).

Now observe that {\tilde \chi(3^a m) = \tilde \chi(3)^a \tilde \chi(m) = \chi(m)}. The function {\chi} has mean zero on every interval of length three, and {\lfloor n/3^j\rfloor} is equal to {1} mod {3}, and thus

\displaystyle \sum_{1 \leq m \leq n/3^j} \tilde \chi(3^a m) = 1

for every {a=0,\dots,k}, and thus

\displaystyle \sum_{j=1}^n \tilde \chi(j) = k+1 \gg \log n.

Thus {\tilde \chi} also has unbounded discrepancy, but only barely so (it grows logarithmically in {n}). These examples suggest that the main “enemy” to proving Conjecture 2 comes from completely multiplicative functions {f} that somehow “pretend” to be like a Dirichlet character but do not vanish at the zeroes of that character. (Indeed, the special case of Conjecture 2 when {f} is completely multiplicative is already open, appears to be an important subcase.)

All of these conjectures remain open. However, I would like to record in this blog post the following striking connection, illustrating the power of the Elliott conjecture (particularly in its nonasymptotic formulation):

Theorem 3 (Elliott conjecture implies unbounded discrepancy) Conjecture 1 implies Conjecture 2.

The argument relies heavily on two observations that were previously made in connection with the Polymath5 project. The first is a Fourier-analytic reduction that replaces the Erdos Discrepancy Problem with an averaged version for completely multiplicative functions {g}. An application of Cauchy-Schwarz then shows that any counterexample to that version will violate the conclusion of Conjecture 1, so if one assumes that conjecture then {g} must pretend to be like a function of the form {n \mapsto \chi(n) n^{it}}. One then uses (a generalisation) of a second argument from Polymath5 to rule out this case, basically by reducing matters to a more complicated version of the Borwein-Choi-Coons analysis. Details are provided below the fold.

There is some hope that the Chowla and Elliott conjectures can be attacked, as the parity barrier which is so impervious to attack for the twin prime conjecture seems to be more permeable in this setting. (For instance, in my previous post I raised a possible approach, based on establishing expander properties of a certain random graph, which seems to get around the parity problem, in principle at least.)

(Update, Sep 25: fixed some treatment of error terms, following a suggestion of Andrew Granville.)

— 1. Fourier reduction —

We will prove Theorem 3 by contradiction, assuming that there is a function {f} with bounded discrepancy and then concluding a violation of the Elliott conjecture.

The function {f: {\bf N} \rightarrow \{-1,+1\}} need not have any multiplicativity properties, but by using an argument from Polymath5 we can extract a random completely multiplicative function which also has good discrepancy properties (albeit in an probabilistic sense only):

Proposition 4 (Fourier reduction) Suppose that {f: {\bf N} \rightarrow \{-1,+1\}} is a function such that

\displaystyle \sup_{n,d \in {\bf N}} |\sum_{j=1}^n f(jd)| < +\infty. \ \ \ \ \ (3)

Then there exists a random completely multiplicative function {g} of magnitude {1} such that

\displaystyle {\bf E} |\sum_{j=1}^n g(j)|^2 \ll 1

uniformly for all natural numbers {n} (we allow implied constants to depend on {f}).

Proof: For the readers convenience, we reproduce the Polymath5 argument.

The space of completely multiplicative functions {g} of magnitude {1} can be identified with the infinite product {(S^1)^{\bf Z}} since {g} is determined by its values {g(p) \in S^1} at the primes. In particular, this space is compact metrisable in the product topology. The functions {g \mapsto |\sum_{j=1}^n g(j)|^2} are continuous in this topology for all {n}. By vague compactness of probability measures on compact metrisable spaces (Prokhorov’s theorem), it thus suffices to construct, for each {X \geq 1}, a random completely multiplicative function {g} of magnitude {1} such that

\displaystyle {\bf E} |\sum_{j=1}^n g(j)|^2 \ll 1

for all {n \leq X}, where the implied constant is uniform in {n} and {X}.

By hypothesis, we have

\displaystyle |\sum_{j=1}^n f(jd)| \ll 1 \ \ \ \ \ (4)

for all {n,d} (the implied constant can depend on {f} but is otherwise absolute). Let {X \geq 1}, and let {p_1,\dots,p_r} be the primes up to {X}. Let {M \geq X} be a natural number that we assume to be sufficiently large depending on {X}. Define a function {F: ({\bf Z}/M{\bf Z})^r \rightarrow \{-1,+1\}} by the formula

\displaystyle F( a_1,\dots,a_r ) := f( p_1^{a_1} \dots p_r^{a_r} )

for {a_1,\dots,a_r \in \{0,\dots,M-1\}}. We also define the function {\pi: [1,X] \rightarrow ({\bf Z}/M{\bf Z})^r} by setting {\pi( p_1^{a_1} \dots p_r^{a_r} ) := (a_1,\dots,a_r)} whenever {p_1^{a_1} \dots p_r^{a_r}} is in {[1,X]} (this is well defined for {M \geq X}). Applying (4) for {n \leq X} and {d} of the form {p_1^{a_1} \dots p_r^{a_r}} with {1 \leq a_i \leq M - X}, we conclude that

\displaystyle |\sum_{j=1}^n F( x + \pi(j) )| \ll 1

for all {n \leq X} and all but {O_X( M^{r-1} )} of the {M^r} elements {x = (a_1,\dots,a_r)} of {({\bf Z}/M{\bf Z})^r}. For the exceptional elements, we have the trivial bound

\displaystyle |\sum_{j=1}^n F( x + \pi(j) )| \leq X.

Square-summing in {x}, we conclude (if {M} is sufficiently large depending on {X}) that

\displaystyle {\bf E}_{x \in ({\bf Z}/M{\bf Z})^r} |\sum_{j=1}^n F( x + \pi(j) )|^2 \ll 1 \ \ \ \ \ (5)

By Fourier expansion, we can write

\displaystyle F(x) = \sum_{\xi \in ({\bf Z}/M{\bf Z})^r} \hat F(\xi) e( \frac{x \cdot \xi}{M} )

where {(a_1,\dots,a_r) \cdot (\xi_1,\dots,\xi_r) := a_1 \xi_1 + \dots + a_r \xi_r}, {e(\theta) := e^{2\pi i \theta}}, and

\displaystyle \hat F(\xi) := {\bf E}_{x \in ({\bf Z}/M{\bf Z})^r} F(x) e( -\frac{x \cdot \xi}{M} ).

A little Fourier-analytic calculation then allows us to write the left-hand side of (5) as

\displaystyle \sum_{\xi \in ({\bf Z}/M{\bf Z})^r} |\hat F(\xi)|^2 |\sum_{j=1}^n e( \frac{\pi(j) \cdot \xi}{M} )|^2.

On the other hand, from the Plancherel identity we have

\displaystyle \sum_{\xi \in ({\bf Z}/M{\bf Z})^r} |\hat F(\xi)|^2 = 1

and so we can interpret {|\hat F(\xi)|^2} as the probability distribution of a random frequency {\xi = (\xi_1,\dots,\xi_r) \in ({\bf Z}/M{\bf Z})^r}. The estimate (5) now takes the form

\displaystyle {\bf E} |\sum_{j=1}^n e( \frac{\pi(j) \cdot \xi}{M} )|^2 \ll 1

for all {n \leq N}. If we then define the completely multiplicative function {g} by setting {g(p_j) := e( \xi_j / M )} for {j=1,\dots,r}, and {g(p) := 1} for all other primes, we obtain

\displaystyle {\bf E} |\sum_{j=1}^n g(j)|^2 \ll 1

for all {n \leq X}, as desired. \Box

Remark 5 A similar reduction applies if the original function {f} took values in the unit sphere of a complex Hilbert space, rather than in {\{-1,+1\}}. Conversely, the random {g} constructed above can be viewed as an element of a unit sphere of a suitable Hilbert space, so the conclusion of Proposition 4 is in fact logically equivalent to failure of the Hilbert space version of the Erdös discrepancy conjecture.

Remark 6 From linearity of expectation, we see from Proposition 4 that for any natural number {N}, we have

\displaystyle {\bf E} \frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n g(j)|^2 \ll 1

and hence for each {N} we conclude that there exists a deterministic completely multiplicative function of unit magnitude such that

\displaystyle \frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n g(j)|^2 \ll 1.

This was the original formulation of the Fourier reduction in Polymath5, however the fact that {g} varied with {N} made this formulation inconvenient for our argument.

— 2. Applying the Elliott conjecture —

Suppose for contradiction that Conjecture 1 holds but that there exists a function {f: {\bf N} \rightarrow \{-1,+1\}} of bounded discrepancy in the sense of (3). By Proposition 4, we may thus find a random completely multiplicative function {g} of magnitude {1} such that

\displaystyle {\bf E} |\sum_{j=1}^n g(j)|^2 \ll 1 \ \ \ \ \ (6)

for all {n}.

We now use Elliott’s conjecture as a sort of “inverse theorem” (in the spirit of the inverse sumset theorem of Frieman, and the inverse theorems for the Gowers uniformity norms) to force {g} to pretend to behave like a modulated character quite often.

Proposition 7 Let the hypotheses and notation be as above. Let {\varepsilon > 0}, and suppose that {X} is sufficiently large depending on {\varepsilon}. Then with probability {1-O(\varepsilon)}, one can find a Dirichlet character {\chi} of period {q = O_\varepsilon(1)} and a real number {t = O_\varepsilon(X)} such that

\displaystyle \sum_{p \leq X} \hbox{Re} \frac{1 - g(p) \overline{\chi(p)} p^{-it}}{p} \ll_\varepsilon 1. \ \ \ \ \ (7)

Proof: We use the van der Corput trick. Let {H \geq 1} be a moderately large natural number depending on {\varepsilon} to be chosen later, and suppose that {X} is sufficiently large depending on {H,\varepsilon}. From (6) and the triangle inequality we have

\displaystyle {\bf E} {\bf E}_{n \in [1,X]} |\sum_{j=1}^n g(j)|^2 \ll 1

so from Markov’s inequality we see with probability {1-O(\varepsilon)} that

\displaystyle {\bf E}_{n \in [1,X]} |\sum_{j=1}^n g(j)|^2 \ll_\varepsilon 1.

Let us condition to this event. Shifting {n} by {H} we conclude (for {X} large enough) that

\displaystyle {\bf E}_{n \in [1,X]} |\sum_{j=1}^{n+H} g(j)|^2 \ll_\varepsilon 1

and hence by the triangle inequality

\displaystyle {\bf E}_{n \in [1,X]} |\sum_{j=n+1}^{n+H} g(j)|^2 \ll_\varepsilon 1,

which we rewrite as

\displaystyle {\bf E}_{n \in [1,X]} |\sum_{h=1}^{H} g(n+h)|^2 \ll_\varepsilon 1,

We can square the left-hand side out as

\displaystyle \sum_{h_1, h_2 \in [1,H]} {\bf E}_{n \in [1,X]} g(n+h_1) \overline{g(n+h_2)}.

The diagonal term {h_1,h_2} contributes {H} to this expression. Thus, for {H=O_\varepsilon(1)} sufficiently large depending on {\varepsilon}, we can apply the triangle inequality and pigeonhole principle to find distinct {h_1,h_2 \in [1,H]} such that

\displaystyle |{\bf E}_{n \in [1,X]} g(n+h_1) \overline{g(n+h_2)}| \gg_\varepsilon 1.

By symmetry we can take {h_2 > h_1}. Setting {h := h_2 - h_1}, we conclude (for {X} large enough) that

\displaystyle |{\bf E}_{n \in [1,X]} g(n) \overline{g(n+h)}| \gg_\varepsilon 1.

Applying Conjecture 1 in the contrapositive, we obtain the claim. \Box

The conclusion (8) asserts that in some sense, {g} “pretends” to be like the function {n \mapsto \chi(n)n^{it}}; as it has magnitude one, it should resemble the function {\tilde \chi} discussed in the introduction. The remaining task is to find some generalisation of the argument that shows that {\tilde \chi} had (logarithmically) large discrepancy to show that {g} likewise fails to obey (6).

— 3. Ruling out correlation with modulated characters —

We now use (a generalisation of) this Polymath5 argument. Let {g} be the random completely multiplicative function provided by Proposition 4. We will need the following parameters:

  • A sufficiently small quantity {0 < \varepsilon < 1/2}.
  • A natural number {H \geq 1} that is sufficiently large depending on {\varepsilon}.
  • A quantity {0 < \delta < 1/2} that is sufficiently small depending on {\varepsilon,H}.
  • A natural number {k \geq 1} that is sufficiently large depending on {\varepsilon,H,\delta}.
  • A real number {X \geq 1} that is sufficiently large depending on {\varepsilon,H,\delta,k}.

By Proposition 7, we see with probability {1-O(\varepsilon)} that there exists a Dirichlet character {\chi} of period {q=O_\varepsilon(1)} and a real number {t = O_\varepsilon(X)} such that

\displaystyle \sum_{p \leq X} \hbox{Re} \frac{1 - g(p) \overline{\chi(p)} p^{-it}}{p} \ll_\varepsilon 1. \ \ \ \ \ (8)

By reducing {\chi} if necessary we may assume that {\chi} is primitive.

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

Lemma 8 With probability {1-O(\varepsilon)}, one has

\displaystyle t = O_{\varepsilon}(X^\delta). \ \ \ \ \ (9)

Proof: By Proposition 7 with {X} replaced by {X^\delta}, we see that with probability {1-O(\varepsilon)}, one can find a Dirichlet character {\chi'} of period {q' = O_\varepsilon(1)} and a real number {t' = O_\varepsilon( X^\delta )} such that

\displaystyle \sum_{p \leq X^\delta} \hbox{Re} \frac{1 - g(p) \overline{\chi'(p)} p^{-it'}}{p} \ll_\varepsilon 1.

We may assume that {|t'-t| \geq X^\delta}, since we are done otherwise. Applying the pretentious triangle inequality (see Lemma 3.1 of this paper of Granville and Soundararajan), we conclude that

\displaystyle \sum_{p \leq X^\delta} \hbox{Re} \frac{1 - \chi(p) \overline{\chi'(p)} p^{-i(t'-t)}}{p} \ll_\varepsilon 1.

However, from the Vinogradov-Korobov zero-free region for {L(\cdot,\chi \overline{\chi'})} (see this previous blog post) it is not difficult to show that

\displaystyle \sum_{p \leq X^\delta} \hbox{Re} \frac{1 - \chi(p) \overline{\chi'(p)} p^{-i(t'-t)}}{p} \gg \log\log X

if {X} is sufficiently large depending on {\varepsilon,\delta}, a contradiction. The claim follows. \Box

Let us now condition to the probability {1-O(\varepsilon)} event that {\chi}, {t} exist obeying (8) and the bound (9).

The bound (8) asserts that {g} “pretends” to be like the completely multiplicative function {n \mapsto \chi(p) p^{it}}. We can formalise this by making the factorisation

\displaystyle g(n) := \tilde \chi(n) n^{it} h(n) \ \ \ \ \ (10)

where {\tilde \chi} is the completely multiplicative function of magnitude {1} defined by setting {\tilde \chi(p) := \chi(p)} for {p \not | q} and {\tilde \chi(p) := g(p) p^{-it}} for {p|q}, and {h} is the completely multiplicative function of magnitude {1} defined by setting {h(p) := g(p) \overline{\chi(p)} p^{-it}} for {p \not | q}, and {h(p) = 1} for {p|q}. The function {\tilde \chi} should be compared with the function of the same name studied in the introduction.

The bound (8) then becomes

\displaystyle |\sum_{p \leq X} \hbox{Re} \frac{1-h(p)}{p}| \ll_\varepsilon 1. \ \ \ \ \ (11)

We now perform some manipulations to remove the {n^{it}} and {h} factors from {g} and isolate the {\tilde \chi} factor, which is more tractable to compute with; then we will perform more computations to arrive at an expression just involving {\chi} which we will be able to evaluate fairly easily.

From (6) and the triangle inequality we have

\displaystyle {\bf E} {\bf E}_{H' \in [H/2,H]} |\sum_{m=1}^{H'} g(n+m)|^2 \ll 1

for all {n} (even after conditioning to the {1-O(\varepsilon)} event). The {{\bf E}_{H' \in [H/2,H]}} averaging will not be used until much later in the argument, and the reader may wish to ignore it for now.

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

\displaystyle {\bf E} {\bf E}_{H' \in [H/2,H]} |\sum_{m=1}^{H'} \tilde \chi(n+m) (n+m)^{it} h(n+m)|^2 \ll 1.

For {n \geq X^{2\delta}} we can use (9) to conclude that {(n+m)^{it} = n^{it} + O_{\varepsilon,H,\delta}(X^{-\delta})}. The contribution of the error term is negligible, thus

\displaystyle {\bf E} {\bf E}_{H' \in [H/2,H]} |\sum_{m=1}^{H'}\tilde \chi(n+m) n^{it} h(n+m)|^2 \ll 1

for all {n \geq X^{2\delta}}. We can factor out the {n^{it}} to obtain

\displaystyle {\bf E} {\bf E}_{H' \in [H/2,H]} |\sum_{m=1}^{H'} \tilde \chi(n+m) h(n+m)|^2 \ll 1.

For {n < X^{2\delta}} we can crudely bound the left-hand side by {H^2}. If {\delta} is sufficiently small, we can then sum weighted by {\frac{1}{n^{1+1/\log X}}} and conclude that

\displaystyle {\bf E} {\bf E}_{H' \in [H/2,H]} \frac{1}{\log X} \sum_n \frac{1}{n^{1+1/\log X}} |\sum_{m=1}^{H'} \tilde \chi(n+m) h(n+m)|^2 \ll 1.

(The zeta function type weight of {\frac{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-O(\varepsilon)}, one has

\displaystyle {\bf E}_{H' \in [H/2,H]} \sum_n \frac{1}{n^{1+1/\log X}} |\sum_{m=1}^{H'} \tilde \chi(n+m) h(n+m)|^2 \ll_\varepsilon \log X.

We condition to this event. We have successfully eliminated the role of {n^{it}}; we now work to eliminate {h}. Call a residue class {a \hbox{ mod } q^k} bad if {a+m} is divisible by {p^k} for some {p|q} and {1 \leq m \leq H}. and good otherwise. We restrict {n} to good residue classes, thus

\displaystyle {\bf E}_{H' \in [H/2,H]}\sum_{a \in [1,q^k], \hbox{ good}} \sum_{n = a \hbox{ mod } q^k} \frac{1}{n^{1+1/\log X}} |\sum_{m=1}^{H'}\tilde \chi(n+m) h(n+m)|^2

\displaystyle \ll_\varepsilon \log X.

By Cauchy-Schwarz, we conclude that

\displaystyle {\bf E}_{H' \in [H/2,H]} \sum_{a \in [1,q^k], \hbox{ good}}

\displaystyle |\sum_{n = a \hbox{ mod } q^k} \frac{1}{n^{1+1/\log X}} \sum_{m=1}^{H'} \tilde \chi(n+m) h(n+m)|^2

\displaystyle \ll_\varepsilon \frac{1}{q^k} \log^2 X.

Now we claim that for a {n} in a good residue class {a \hbox{ mod } q^k}, the quantity {\chi(n+m)} does not depend on {n}. Indeed, by hypothesis, {(n+m,q^k) = (a+m,q^k)} is not divisible by {p^k} for any {p|q} and is thus a factor of {q^{k-1}}, and {\frac{n+m}{(n+m,q^k)} = \frac{n+m}{(a+m,q^k)}} is coprime to {q}. We then factor

\displaystyle \tilde \chi(n+m)= \tilde \chi((n+m,q^k)) \tilde \chi( \frac{n+m}{(n+m,q^k)} )

\displaystyle = \tilde \chi((a,q^k)) \chi( \frac{n+m}{(a+m,q^k)} )

\displaystyle = \tilde \chi((a,q^k)) \chi( \frac{a+m}{(a+m,q^k)} )

where in the last line we use the periodicity of {\chi}. Thus we have {\tilde \chi(n+m) = \tilde \chi(a+m)}, and so

\displaystyle {\bf E}_{H' \in [H/2,H]} \sum_{a \in [1,q^k], \hbox{ good}}

\displaystyle |\sum_{m=1}^{H'} \tilde \chi(a+m) \sum_{n = a \hbox{ mod } q^k} \frac{1}{n^{1+1/\log X}} h(n+m)|^2

\displaystyle \ll_\varepsilon \frac{1}{q^k} \log^2 X.

Shifting {n} by {m} we see that

\displaystyle \sum_{n = a \hbox{ mod } q^k} \frac{1}{n^{1+1/\log X}} h(n+m)

\displaystyle = \sum_{n = a+m \hbox{ mod } q^k} \frac{1}{n^{1+1/\log X}} h(n) + O_H(1)

and thus (for {X} large enough)

\displaystyle {\bf E}_{H' \in [H/2,H]} \sum_{a \in [1,q^k], \hbox{ good}} |\sum_{m=1}^{H'} \tilde \chi(a+m) \sum_{n = a+m \hbox{ mod } q^k} \frac{h(n)}{n^{1+1/\log X}}|^2 \ \ \ \ \ (12)

\displaystyle \ll_\varepsilon \frac{1}{q^k} \log^2 X.

Now, we perform some multiplicative number theory to understand the innermost sum. From taking Euler products we have

\displaystyle \sum_n \frac{h(n)}{n^{1+1/\log X}} = {\mathfrak S}

for {{\mathfrak S} := \prod_p (1 - \frac{h(p)}{p^{1+1/\log X}})^{-1}}; from (11) and Mertens’ theorem one can easily verify that

\displaystyle \log X \ll_\varepsilon |{\mathfrak S}| \ll_\varepsilon \log X. \ \ \ \ \ (13)

More generally, for any Dirichlet character {\chi_1} we have

\displaystyle \sum_n \frac{\chi_1(n) h(n)}{n^{1+1/\log X}} = \prod_p (1 - \frac{h(p) \chi_1(p)}{p^{1+1/\log X}})^{-1}.

Since

\displaystyle \prod_p (1 - \frac{\chi_1(p)}{p^{1+1/\log X}})^{-1} = L(1+\frac{1}{\log X}, \chi_1) \ll_{q,k} 1

we have

\displaystyle \sum_n \frac{\chi_1(n) h(n)}{n^{1+1/\log X}} \ll_{q,k} \exp( \sum_p \frac{|1-h(p)|}{p^{1+1/\log X}})

which after using (11), Cauchy-Schwarz (using {|1-h(p)| \ll (1-\hbox{Re} h(p))^{1/2})} and Mertens theorem gives

\displaystyle \sum_n \frac{\chi_1(n) h(n)}{n^{1+1/\log X}} \ll_{q,k} \exp(O_\varepsilon(\sqrt{\log\log X}))

for any non-principal character {\chi_1} of period dividing {q^k}; for a principal character {\chi_0} of period {r} dividing {q^k} we have

\displaystyle \sum_n \frac{\chi_0 h(n)}{n^{1+1/\log X}} = \prod_{p \not | r} (1 - \frac{h(p)}{p^{1+1/\log X}})^{-1}

\displaystyle = \frac{\phi(r)}{r} {\mathfrak S} + O_{q,k}(1)

since {h(p)=1} and hence {\frac{h(p)}{p^{1+1/\log X}} = \frac{1}{p} + O(\frac{1}{\log X})} for all {p|r}, where we have also used (13). By expansion into Dirichlet characters we conclude that

\displaystyle \sum_{n = b \hbox{ mod } r} \frac{h(n)}{n^{1+1/\log X}} = \frac{1}{r} {\mathfrak S} + O_{q,k}(\exp(O_\varepsilon(\sqrt{\log\log X})))

for all {r|q^k} and primitive residue classes {b \hbox{ mod } r}. For non-primitive residue classes {b \hbox{ mod } r}, we write {r = (b,r) r'} and {b = (b,r) b'}. The previous arguments then give

\displaystyle \sum_{n = b' \hbox{ mod } r'} \frac{h(n)}{n^{1+1/\log X}} = \frac{1}{r'} {\mathfrak S} + O_{q,k}(\exp(O_\varepsilon(\sqrt{\log\log X})))

which since {h((b,r))=1} gives (again using (13))

\displaystyle \sum_{n = b \hbox{ mod } r} \frac{h(n)}{n^{1+1/\log X}} = \frac{1}{r} {\mathfrak S} + O_{q,k}(\exp(O_\varepsilon(\sqrt{\log\log X})))

for all {b \hbox{ mod } r} (not necessarily primitive). Inserting this back into (12) we see that

\displaystyle {\bf E}_{H' \in [H/2,H]}\sum_{a \in [1,q^k] \hbox{ good}} | \sum_{m=1}^{H'}\tilde \chi(a+m) (\frac{1}{q^k} {\mathfrak S} + O_{q,k}(\exp(O_\varepsilon(\sqrt{\log\log X})))) |^2 \ll_\varepsilon \frac{1}{q^k} \log^2 X

and thus by (13) we conclude (for {X} large enough) that

\displaystyle \frac{1}{q^k} \sum_{a \in [1,q^k] \hbox{ good}} {\bf E}_{H' \in [H/2,H]} |\sum_{m=1}^{H'} \tilde \chi(a+m)|^2 \ll_\varepsilon 1. \ \ \ \ \ (14)

We have now eliminated both {t} and {h}. The remaining task is to establish some lower bound on the discrepancy of {\tilde \chi} that will contradict (14). As mentioned above, this will be a more complicated variant of the Borwein-Choi-Coons analysis in the introduction. The square in (14) will be helpful in dealing with the fact that we don’t have good control on the {\tilde \chi(p)} for {p|q} (as we shall see, the squaring introduces two terms of this type that end up cancelling each other).

We expand (14) to obtain

\displaystyle {\bf E}_{H' \in [H/2,H]} \sum_{m_1,m_2 \in [1,H']} \sum_{a \in [1,q^k], \hbox{ good}} \tilde \chi(a+m_1) \overline{\tilde \chi(a+m_2)} \ll_\varepsilon q^k.

Write {d_1 := (a+m_1,q^k)} and {d_2 := (a+m_2,q^k)}, thus {d_1,d_2 | q^{k-1}} and for {i=1,2} we have

\displaystyle \tilde \chi(a+m_i) = \tilde \chi(d_i) \chi( \frac{a+m_i}{d_i} ).

We thus have

\displaystyle \sum_{d_1,d_2|q^{k-1}} \tilde \chi(d_1) \overline{\tilde \chi}(d_2) {\bf E}_{H' \in [H/2,H]} \sum_{m_1,m_2 \in [1,H']}

\displaystyle \sum_{a \in [1,q^k], \hbox{ good}: (a+m_1,q^k)=d_1, (a+m_2,q^k)=d_2}

\displaystyle \chi(\frac{a+m_1}{d_1}) \overline{\chi}(\frac{a+m_2}{d_2}) \ll_\varepsilon q^k.

We reinstate the bad {a}. The number of such {a} is at most {O(2^{-k} q^k )}, so their total contribution here is {O_H(2^{-k} q^k)} which is negligible, thus

\displaystyle \sum_{d_1,d_2|q^{k-1}} \tilde \chi(d_1) \overline{\tilde \chi}(d_2) {\bf E}_{H' \in [H/2,H]} \ \ \ \ \ (15)

\displaystyle \sum_{m_1,m_2 \in [1,H']} \sum_{a \in [1,q^k]: (a+m_1,q^k)=d_1, (a+m_2,q^k)=d_2}

\displaystyle \chi(\frac{a+m_1}{d_1}) \overline{\chi}(\frac{a+m_2}{d_2}) \ll_\varepsilon q^k.

For {d_1 \geq q^{k/10}} or {d_2 \geq q^{k/10}}, the inner sum is {O_H(q^{-k/10} q^k )}, which by the divisor bound gives a negligible contribution. Thus we may restrict to {d_1,d_2 < q^{k/10}}. Note that as {\chi} is already restricted to numbers coprime to {q}, and {d_1,d_2} divide {q^{k-1}}, we may replace the constraints {(a+m_i,q^k)=d_i} with {d_i|a+m_i} for {i=1,2}.

We consider the contribution of an off-diagonal term {d_1 \neq d_2} for a fixed choice of {m_1,m_2}. To handle these terms we expand the non-principal character {\chi(n)} as a linear combination of {e( \xi n / q )} for {\xi \in ({\bf Z}/q{\bf Z})^\times} with Fourier coefficients {O(1)}. Thus we can expand out

\displaystyle \sum_{a \in [1,q^k]: d_1|a+m_1; d_2|a+m_2} \chi(\frac{a+m_1}{d_1}) \overline{\chi}(\frac{a+m_2}{d_2})

as a linear combination of {O(1)} expressions of the form

\displaystyle \sum_{a \in [1,q^k]: d_1|a+m_1; d_2|a+m_2} e(\frac{\xi_1}{q} \frac{a+m_1}{d_1} - \frac{\xi_2}{q} \frac{a+m_2}{d_2})

with {\xi_1,\xi_2 \in ({\bf Z}/q{\bf Z})^\times} and coefficients of size {O(1)}.

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 \hbox{ mod } [d_1,d_2]}. Writing {a = b + n [d_1,d_2]}, we have

\displaystyle e(\frac{\xi_1}{q} \frac{a+m_1}{d_1} - \frac{\xi_2}{q} \frac{a+m_2}{d_2}) = e( \theta + \frac{n}{q} ( \xi_1 \frac{[d_1,d_2]}{d_1} - \xi_2 \frac{[d_1,d_2]}{d_2} ) )

for some phase {\theta} that can depend on {b,m_1,m_2,d_1,d_2,q,\xi_1,\xi_2} but is independent of {n}. If {d_1 \neq d_2}, then at least one of the two quantities {\frac{[d_1,d_2]}{d_1}} and {\frac{[d_1,d_2]}{d_2}} is divisible by a prime {p|q} that does not divide the other quantity. Therefore {\xi_1 \frac{[d_1,d_2]}{d_1} - \xi_2 \frac{[d_1,d_2]}{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

\displaystyle \sum_{a \in [1,q^k]: d_1|a+m_1; d_2|a+m_2} e(\frac{\xi_1}{q} \frac{a+m_1}{d_1} - \frac{\xi_2}{q} \frac{a+m_2}{d_2}) \ll [d_1,d_2] \ll q^{k/5}

and so by the divisor bound the off-diagonal terms {d_1 \neq d_2} contribute at most {O_H( q^{k/5 + o(k)} )} to (15). For {k} large, this is negligible, and thus we only need to consider the diagonal contribution {d_1 = d_2 < q^{k/10}}. Here the { \tilde \chi(d_1) \overline{\tilde \chi}(d_2)} terms helpfully cancel, and we obtain

\displaystyle \sum_{d|q^{k-1}: d < q^{k/10}} {\bf E}_{H' \in [H/2,H]} \sum_{m_1,m_2 \in [1,H']} \sum_{a \in [1,q^k]: d | a+m_1, a+m_2}

\displaystyle \chi(\frac{a+m_1}{d}) \overline{\chi}(\frac{a+m_2}{d}) \ll_\varepsilon q^k.

We have now eliminated {\tilde \chi}, leaving only the Dirichlet character {\chi} which is much easier to work with. We gather terms and write the left-hand side as

\displaystyle \sum_{d|q^{k-1}: d < q^{k/10}} {\bf E}_{H' \in [H/2,H]} \sum_{a \in [1,q^k]} |\sum_{m \in [1,H']: d|a+m} \chi(\frac{a+m}{d})|^2 \ll \varepsilon q^k.

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 < \sqrt{H}}, to conclude that

\displaystyle \sum_{i: q^i < \sqrt{H}} {\bf E}_{H' \in [H/2,H]} \sum_{a \in [1,q^k]} |\sum_{m \in [1,H']: q^i|a+m} \chi(\frac{a+m}{q^i})|^2 \ll_\varepsilon q^k.

It is now that we finally take advantage of the averaging {{\bf E}_{H' \in [H/2,H]}} to simplify the {m} summation. Observe from the triangle inequality that for any {H' \in [H/2, 3H/4]} and {a \in [1,q^k]} one has

\displaystyle |\sum_{H' < a \leq H' + q^i: q^i|a+m} \chi(\frac{a+m}{q^i})|^2

\displaystyle \ll |\sum_{m \in [1,H']: q^i|a+m} \chi(\frac{a+m}{q^i})|^2 + |\sum_{m \in [1,H'+q^i]: q^i|a+m} \chi(\frac{a+m}{q^i})|^2;

summing over {i,H',a} we conclude that

\displaystyle \sum_{i: q^i < \sqrt{H}} {\bf E}_{H' \in [H/2,3H/4]} \sum_{a \in [1,q^k]} |\sum_{H' < m \leq H'+q^i: q^i|a+m} \chi(\frac{a+m}{q^i})|^2 \ll_\varepsilon q^k.

In particular, by the pigeonhole principle there exists {H' \in [H/2,3H/4]} such that

\displaystyle \sum_{i: q^i < \sqrt{H}} \sum_{a \in [1,q^k]} |\sum_{H' < m \leq H'+q^i: q^i|a+m} \chi(\frac{a+m}{q^i})|^2 \ll_\varepsilon q^k.

Shifting {a} by {H'} and discarding some terms, we conclude that

\displaystyle \sum_{i: q^i < \sqrt{H}} \sum_{a \in [1,q^k/2]} |\sum_{1 \leq m \leq q^i: q^i|a+m} \chi(\frac{a+m}{q^i})|^2 \ll_\varepsilon q^k.

Observe that for a fixed {a} there is exactly one {m} in the inner sum, and {\frac{a+m}{q^i} = \lfloor \frac{a}{q^i} \rfloor + 1}. Thus we have

\displaystyle \sum_{i: q^i < \sqrt{H}} \sum_{a \in [1,q^k/2]} |\chi(\lfloor \frac{a}{q^i}\rfloor + 1)|^2 \ll_\varepsilon q^k.

Making the change of variables {b := \lfloor \frac{a}{q^i} \rfloor + 1}, we thus have

\displaystyle \sum_{i: q^i < \sqrt{H}} q^i \sum_{b \in [1,q^{k-i}/4]} |\chi(b)|^2 \ll_\varepsilon q^k.

But {b \mapsto |\chi(b)|^2} is periodic of period {q} with mean {\gg 1}, thus

\displaystyle \sum_{b \in [1,q^{k-i}/4]} |\chi(b)|^2 \gg q^{k-i}

and thus

\displaystyle \sum_{i: q^i < \sqrt{H}} 1 \ll_\varepsilon 1,

which leads to a contradiction for {H} large enough (note the logarithmic growth in {H} here, matching the logarithmic growth in the Borwein-Choi-Coons analysis). The claim follows.