You are currently browsing the tag archive for the ‘completion of sums’ tag.

This is the final continuation of the online reading seminar of Zhang’s paper for the polymath8 project. (There are two other continuations; this previous post, which deals with the combinatorial aspects of the second part of Zhang’s paper, and this previous post, that covers the Type I and Type II sums.) The main purpose of this post is to present (and hopefully, to improve upon) the treatment of the final and most innovative of the key estimates in Zhang’s paper, namely the Type III estimate.

The main estimate was already stated as Theorem 17 in the previous post, but we quickly recall the relevant definitions here. As in other posts, we always take {x} to be a parameter going off to infinity, with the usual asymptotic notation {O(), o(), \ll} associated to this parameter.

Definition 1 (Coefficient sequences) A coefficient sequence is a finitely supported sequence {\alpha: {\bf N} \rightarrow {\bf R}} that obeys the bounds

\displaystyle  |\alpha(n)| \ll \tau^{O(1)}(n) \log^{O(1)}(x) \ \ \ \ \ (1)

for all {n}, where {\tau} is the divisor function.

  • (i) If {\alpha} is a coefficient sequence and {a\ (q) = a \hbox{ mod } q} is a primitive residue class, the (signed) discrepancy {\Delta(\alpha; a\ (q))} of {\alpha} in the sequence is defined to be the quantity

    \displaystyle  \Delta(\alpha; a \ (q)) := \sum_{n: n = a\ (q)} \alpha(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1} \alpha(n). \ \ \ \ \ (2)

  • (ii) A coefficient sequence {\alpha} is said to be at scale {N} for some {N \geq 1} if it is supported on an interval of the form {[(1-O(\log^{-A_0} x)) N, (1+O(\log^{-A_0} x)) N]}.
  • (iii) A coefficient sequence {\alpha} at scale {N} is said to be smooth if it takes the form {\alpha(n) = \psi(n/N)} for some smooth function {\psi: {\bf R} \rightarrow {\bf C}} supported on {[1-O(\log^{-A_0} x), 1+O(\log^{-A_0} x)]} obeying the derivative bounds

    \displaystyle  \psi^{(j)}(t) = O( \log^{j A_0} x ) \ \ \ \ \ (3)

    for all fixed {j \geq 0} (note that the implied constant in the {O()} notation may depend on {j}).

For any {I \subset {\bf R}}, let {{\mathcal S}_I} denote the square-free numbers whose prime factors lie in {I}. The main result of this post is then the following result of Zhang:

Theorem 2 (Type III estimate) Let {\varpi, \delta > 0} be fixed quantities, and let {M, N_1, N_2, N_3 \gg 1} be quantities such that

\displaystyle  x \ll M N_1 N_2 N_3 \ll x

and

\displaystyle  N_1 \gg N_2, N_3

and

\displaystyle  N_1^4 N_2^4 N_3^5 \gg x^{4+16\varpi+\delta+c}

for some fixed {c>0}. Let {\alpha, \psi_1, \psi_2, \psi_3} be coefficient sequences at scale {M,N_1,N_2,N_3} respectively with {\psi_1,\psi_2,\psi_3} smooth. Then for any {I \subset [1,x^\delta]} we have

\displaystyle  \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} \sup_{a \in ({\bf Z}/q{\bf Z})^\times} |\Delta(\alpha \ast \beta; a)| \ll x \log^{-A} x.

In fact we have the stronger “pointwise” estimate

\displaystyle  |\Delta(\alpha \ast \psi_1 \ast \psi_2 \ast \psi_3; a)| \ll x^{-\epsilon} \frac{x}{q} \ \ \ \ \ (4)

for all {q \in {\mathcal S}_I} with {q < x^{1/2+2\varpi}} and all {a \in ({\bf Z}/q{\bf Z})^\times}, and some fixed {\epsilon>0}.

(This is very slightly stronger than previously claimed, in that the condition {N_2 \gg N_3} has been dropped.)

It turns out that Zhang does not exploit any averaging of the {\alpha} factor, and matters reduce to the following:

Theorem 3 (Type III estimate without {\alpha}) Let {\delta > 0} be fixed, and let {1 \ll N_1, N_2, N_3, d \ll x^{O(1)}} be quantities such that

\displaystyle  N_1 \gg N_2, N_3

and

\displaystyle d \in {\mathcal S}_{[1,x^\delta]}

and

\displaystyle  N_1^4 N_2^4 N_3^5 \gg d^8 x^{\delta+c}

for some fixed {c>0}. Let {\psi_1,\psi_2,\psi_3} be smooth coefficient sequences at scales {N_1,N_2,N_3} respectively. Then we have

\displaystyle  |\Delta(\psi_1 \ast \psi_2 \ast \psi_3; a)| \ll x^{-\epsilon} \frac{N_1 N_2 N_3}{d}

for all {a \in ({\bf Z}/d{\bf Z})^\times} and some fixed {\epsilon>0}.

Let us quickly see how Theorem 3 implies Theorem 2. To show (4), it suffices to establish the bound

\displaystyle  \sum_{n = a\ (q)} \alpha \ast \psi_1 \ast \psi_2 \ast \psi_3(n) = X + O( x^{-\epsilon} \frac{x}{q} )

for all {a \in ({\bf Z}/q{\bf Z})^\times}, where {X} denotes a quantity that is independent of {a} (but can depend on other quantities such as {\alpha,\psi_1,\psi_2,\psi_3,q}). The left-hand side can be rewritten as

\displaystyle  \sum_{b \in ({\bf Z}/q{\bf Z})^\times} \sum_{m = b\ (q)} \alpha(m) \sum_{n = a/b\ (q)} \psi_1 \ast \psi_2 \ast \psi_3(n).

From Theorem 3 we have

\displaystyle  \sum_{n = a/b\ (q)} \psi_1 \ast \psi_2 \ast \psi_3(n) = Y + O( x^{-\epsilon} \frac{N_1 N_2 N_3}{q} )

where the quantity {Y} does not depend on {a} or {b}. Inserting this asymptotic and using crude bounds on {\alpha} (see Lemma 8 of this previous post) we conclude (4) as required (after modifying {\epsilon} slightly).

It remains to establish Theorem 3. This is done by a set of tools similar to that used to control the Type I and Type II sums:

  • (i) completion of sums;
  • (ii) the Weil conjectures and bounds on Ramanujan sums;
  • (iii) factorisation of smooth moduli {q \in {\mathcal S}_I};
  • (iv) the Cauchy-Schwarz and triangle inequalities (Weyl differencing).

The specifics are slightly different though. For the Type I and Type II sums, it was the classical Weil bound on Kloosterman sums that were the key source of power saving; Ramanujan sums only played a minor role, controlling a secondary error term. For the Type III sums, one needs a significantly deeper consequence of the Weil conjectures, namely the estimate of Bombieri and Birch on a three-dimensional variant of a Kloosterman sum. Furthermore, the Ramanujan sums – which are a rare example of sums that actually exhibit better than square root cancellation, thus going beyond even what the Weil conjectures can offer – make a crucial appearance, when combined with the factorisation of the smooth modulus {q} (this new argument is arguably the most original and interesting contribution of Zhang).

Read the rest of this entry »

This is one of the continuations of the online reading seminar of Zhang’s paper for the polymath8 project. (There are two other continuations; this previous post, which deals with the combinatorial aspects of the second part of Zhang’s paper, and a post to come that covers the Type III sums.) The main purpose of this post is to present (and hopefully, to improve upon) the treatment of two of the three key estimates in Zhang’s paper, namely the Type I and Type II estimates.

The main estimate was already stated as Theorem 16 in the previous post, but we quickly recall the relevant definitions here. As in other posts, we always take {x} to be a parameter going off to infinity, with the usual asymptotic notation {O(), o(), \ll} associated to this parameter.

Definition 1 (Coefficient sequences) A coefficient sequence is a finitely supported sequence {\alpha: {\bf N} \rightarrow {\bf R}} that obeys the bounds

\displaystyle  |\alpha(n)| \ll \tau^{O(1)}(n) \log^{O(1)}(x) \ \ \ \ \ (1)

for all {n}, where {\tau} is the divisor function.

  • (i) If {\alpha} is a coefficient sequence and {a\ (q) = a \hbox{ mod } q} is a primitive residue class, the (signed) discrepancy {\Delta(\alpha; a\ (q))} of {\alpha} in the sequence is defined to be the quantity

    \displaystyle  \Delta(\alpha; a \ (q)) := \sum_{n: n = a\ (q)} \alpha(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1} \alpha(n). \ \ \ \ \ (2)

  • (ii) A coefficient sequence {\alpha} is said to be at scale {N} for some {N \geq 1} if it is supported on an interval of the form {[(1-O(\log^{-A_0} x)) N, (1+O(\log^{-A_0} x)) N]}.
  • (iii) A coefficient sequence {\alpha} at scale {N} is said to obey the Siegel-Walfisz theorem if one has

    \displaystyle  | \Delta(\alpha 1_{(\cdot,q)=1}; a\ (r)) | \ll \tau(qr)^{O(1)} N \log^{-A} x \ \ \ \ \ (3)

    for any {q,r \geq 1}, any fixed {A}, and any primitive residue class {a\ (r)}.

  • (iv) A coefficient sequence {\alpha} at scale {N} is said to be smooth if it takes the form {\alpha(n) = \psi(n/N)} for some smooth function {\psi: {\bf R} \rightarrow {\bf C}} supported on {[1-O(\log^{-A_0} x), 1+O(\log^{-A_0} x)]} obeying the derivative bounds

    \displaystyle  \psi^{(j)}(t) = O( \log^{j A_0} x ) \ \ \ \ \ (4)

    for all fixed {j \geq 0} (note that the implied constant in the {O()} notation may depend on {j}).

In Lemma 8 of this previous post we established a collection of “crude estimates” which assert, roughly speaking, that for the purposes of averaged estimates one may ignore the {\tau^{O(1)}(n)} factor in (1) and pretend that {\alpha(n)} was in fact {O( \log^{O(1)} n)}. We shall rely frequently on these “crude estimates” without further citation to that precise lemma.

For any {I \subset {\bf R}}, let {{\mathcal S}_I} denote the square-free numbers whose prime factors lie in {I}.

Definition 2 (Singleton congruence class system) Let {I \subset {\bf R}}. A singleton congruence class system on {I} is a collection {{\mathcal C} = (\{a_q\})_{q \in {\mathcal S}_I}} of primitive residue classes {a_q \in ({\bf Z}/q{\bf Z})^\times} for each {q \in {\mathcal S}_I}, obeying the Chinese remainder theorem property

\displaystyle  a_{qr}\ (qr) = (a_q\ (q)) \cap (a_r\ (r)) \ \ \ \ \ (5)

whenever {q,r \in {\mathcal S}_I} are coprime. We say that such a system {{\mathcal C}} has controlled multiplicity if the

\displaystyle  \tau_{\mathcal C}(n) := |\{ q \in {\mathcal S}_I: n = a_q\ (q) \}|

obeys the estimate

\displaystyle  \sum_{C^{-1} x \leq n \leq Cx: n = a\ (r)} \tau_{\mathcal C}(n)^2 \ll \frac{x}{r} \tau(r)^{O(1)} \log^{O(1)} x + x^{o(1)}. \ \ \ \ \ (6)

for any fixed {C>1} and any congruence class {a\ (r)} with {r \in {\mathcal S}_I}.

The main result of this post is then the following:

Theorem 3 (Type I/II estimate) Let {\varpi, \delta, \sigma > 0} be fixed quantities such that

\displaystyle  11 \varpi + 3\delta + 2 \sigma < \frac{1}{4} \ \ \ \ \ (7)

and

\displaystyle  29\varpi + 5 \delta < \frac{1}{4} \ \ \ \ \ (8)

and let {\alpha,\beta} be coefficient sequences at scales {M,N} respectively with

\displaystyle  x \ll MN \ll x \ \ \ \ \ (9)

and

\displaystyle  x^{\frac{1}{2}-\sigma} \ll N \ll M \ll x^{\frac{1}{2}+\sigma} \ \ \ \ \ (10)

with {\beta} obeying a Siegel-Walfisz theorem. Then for any {I \subset [1,x^\delta]} and any singleton congruence class system {(\{a_q\})_{q \in {\mathcal S}_I}} with controlled multiplicity we have

\displaystyle  \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} |\Delta(\alpha \ast \beta; a_q)| \ll x \log^{-A} x.

The proof of this theorem relies on five basic tools:

  • (i) the Bombieri-Vinogradov theorem;
  • (ii) completion of sums;
  • (iii) the Weil conjectures;
  • (iv) factorisation of smooth moduli {q \in {\mathcal S}_I}; and
  • (v) the Cauchy-Schwarz and triangle inequalities (Weyl differencing and the dispersion method).

For the purposes of numerics, it is the interplay between (ii), (iii), and (v) that drives the final conditions (7), (8). The Weil conjectures are the primary source of power savings ({x^{-c}} for some fixed {c>0}) in the argument, but they need to overcome power losses coming from completion of sums, and also each use of Cauchy-Schwarz tends to halve any power savings present in one’s estimates. Naively, one could thus expect to get better estimates by relying more on the Weil conjectures, and less on completion of sums and on Cauchy-Schwarz.

Read the rest of this entry »

Archives