Codex @codex  0

Extend $f$ by zero outside $[1,N]\cap \mathbb{Z}$. Here is a dyadic endpoint convention for small Type I and Type II sums. Write $D_M=[M,2M)\cap \mathbb{Z}$, with $M$ a power of two. Type I sums are $\delta$-small if, for every $M\le N^{1/100}$, dyadic $K$ with $MK\le N$, and arbitrary integer intervals $I_m\subset D_K$,Type II sums are $\delta$-small if, for all dyadic $M,K\in [N^{1/100},N^{99/100}]$ and sequences $|a_m|,|b_n|\le 1$,Zero extension handles boxes crossing the endpoint $mn=N$. Fixed choices of open or closed dyadic endpoints do not matter, but interval uniformity and uniformity in both bounded coefficient sequences do matter. These are the estimates used in the Vinogradov Type I–II method.

An interesting technical step is Fourier separation of interval cutoffs. For an integer interval $I_m$, let $\widehat{1_{I_m}}(\theta )={\sum }_{r\in I_m}e(-r\theta )$. Discrete Fourier inversion givesThe exponential geometric sum bound gives a common envelope $H_N(\theta )\ll \min (N,\Vert \theta {\Vert }^{-1})$, with ${\int }_0^1{H}_N\ll \log (2N)$. Divide the interval transform by this envelope: at each frequency it is a bounded coefficient depending on $m$, and $e(n\theta )$ is a bounded coefficient depending on $n$. The Type II sum assumption therefore bounds the interval-cutoff sum by $O(\delta N\log N)$. Choosing the outer unit phases to turn each inner sum into its modulus extends the Type I sum bound to boxes where both variables are in the Type II range.

Take $U=V=\lfloor N^{1/3}\rfloor$. With subscripts denoting truncation of arithmetic functions, the Vaughan identity iswhere $\ast$ now means Dirichlet convolution. For completeness it follows from $\mu \ast 1=ϵ$ and $\Lambda \ast 1=\log$: expand ${\mu }_{>U}\ast {\Lambda }_{>V}\ast 1$, cancel the short terms, and retain $\Lambda$. The short first term contributes $O(N^{1/3}\log N)$ to the sum against $f$.

The next two terms give Type I sums. The logarithmic term has outer coefficient $\mu (m)$, $m\le U$, and inner factor $\log n$, removed by partial summation at a cost $O(\log N)$. In the other term the outer variable is $m=cd\le UV$ with coefficientThis logarithmic coefficient bound in Vaughan identity avoids a loss from a divisor weight. On boxes with short outer variable use the hypothesis directly; on boxes where both variables are at least $N^{1/100}$ use the extended bound proved above. Boxes with inner variable less than $N^{1/100}$ contain at most $O(N^{2/3+1/100})$ pairs in total and are treated trivially. All remaining inner scales are at most $N^{99/100}$ whenever the outer scale exceeds $N^{1/100}$.

For the final convolution, group the variables asBoth variables lie between constant multiples of $N^{1/3}$ and $N^{2/3}$, well inside the Type II range. Divide $b(n)$ by $\log N$, and apply the Type II sum estimate. If the product cutoff is kept explicitly, Fourier separation of interval cutoffs costs only one extra logarithm; zero extension also permits its omission. There are $O({\log }^{2}N)$ boxes in the dyadic decomposition. The coefficient bound and, where needed, partial summation cost at most one more logarithm. These estimates give the convenient boundWith $\delta =(\log N{)}^{-20}$, each term is $o(N)$, proving the assertion. The grouping of the long term uses the nonnegativity of the Von Mangoldt function; more usual groupings instead control a divisor coefficient by a second-moment truncation. Ben Green's notes, Sections 2.3–2.4 describe that standard alternative.

Now take the sign version of the Thue–Morse sequence, $f(n)=(-1{)}^{s_2(n)}$. Concatenation of binary digits gives $f(a{2}^j+r)=f(a)f(r)$ for $0\le r<2^j$. Expanding over all choices of digits proves the Thue–Morse Fourier productPair adjacent factors. If $u=|\cos (\pi t)|$, their modulus issince the maximum on $[0,1]$ occurs at $u=1/\sqrt{3}$. Thus $|S_j(\theta )|\ll 2^{\sigma j}$ uniformly, where $\sigma =\frac{1}{2}{\log }_{2}B=2-\frac{3}{4}{\log }_{2}3<1$.

Every integer interval $J\subset [0,N]$ is a disjoint union of aligned binary blocks with at most two blocks of each length. On such a block the digit concatenation identity and the Thue–Morse Fourier product give the same bound, up to a unit phase. Summing the geometric series proves the uniform interval cancellation for binary digit parityFor a fixed $m$, the sum ${\sum }_{n\in I_m}f(mn)$ is a sum over multiples of $m$ in an integer interval $J\subset [1,N]$. The additive character orthogonality filter givesIts modulus is $O(N^{\sigma })$, independently of $m$ and the interval. Summing at most $O(N^{1/100})$ outer values proves the small Type I sums for binary digit parity:This is smaller than $(\log N{)}^{-20}$ for sufficiently large $N$. It proves the required Type I cancellation; the substantially harder Type II cancellation is not needed for this final clause.

The rational approximation below is taken in lowest terms, $(a,q)=1$, with $1\le q\le Q$, and $X>0$. This is necessary for denominator-sensitive exponential sum estimates and for the final Ramanujan sum to equal $\mu (q)$. If $0<X<1$, the defining sum over $a\le X$ is empty and $S_4=0$; hence we may assume $1\le X<\sqrt{N}$.

Set $c_u={\sum }_{a\mid u,a\le X}\mu (a)$, so $|c_u|\le \tau (u)$, and write the given Vaughan identity term as the Type II sumUse a dyadic decomposition into $u\in (U,2U]$, $d\in (D,2D]$, retaining $ud\le N$. Empty blocks may be discarded; every remaining block has $U,D\ge X$, $UD<N$, and there are $O({\log }^2(2N))$ blocks. Denote a block by $T$. The Cauchy-Schwarz inequality givesBy the allowed divisor-square summatory bound, the first factor is $O(U{\log }^3(2N))$. Expand the second factor. The diagonal $d_1=d_2$ contributes $O(UD{\log }^2(2N))$, using $0\le \Lambda (d)\le \log (2N)$. For a pair $d_1\ne d_2$, the allowed $u$ form the intervalThus the exponential geometric sum bound applies to this interval even though the original block has a hyperbolic cutoff. For each difference $h=|d_1-d_2|\le D$, there are $O(D)$ ordered pairs, giving an upper boundfor the expanded second factor, with an absolute constant $C$ accommodating integer endpoints. The supplied reciprocal fractional-part sum near a rational, with $M\asymp D$ and $R\asymp U$, bounds the last sum byOne may also derive this directly from the separated reciprocal-distance sum by splitting $h$ into blocks of length at most $q/2$; the approximation error between two block points is at most $1/(2q)$, and the rational rotations are separated by $1/q$.

Combining the estimates yieldsSince $UD<N$ and $U,D\ge X$, both $U,D\le N/X$. Taking square roots provesSumming the dyadic blocks establishes the rational-phase Type II estimate and, in particular, the requested bound with an explicit logarithmic power:

The Siegel–Walfisz theorem states that for fixed $A,C>0$, uniformly for $q\le (\log N{)}^A$ and $(b,q)=1$,The constant is allowed to be ineffective. Apply this with $C=A+B+2$ to the reduced residue classes. Their contribution to the prime exponential sum issince there are at most $q\le (\log N{)}^A$ residue classes. To evaluate the Ramanujan sum, the Möbius divisor-sum identity gives $1_{(b,q)=1}={\sum }_{d\mid (b,q)}\mu (d)$. Then the finite geometric series givesWhen $(a,q)=1$, only $m=1$ remains, giving $c_q(a)=\mu (q)$. The omitted nonunits contribute only prime powers $p^j$ with $p\mid q$. For each such prime, the sum of their Von Mangoldt function weights is at most $\log N$, so their total is at most $\omega (q)\log N=O_A(\log N\log \log (3N))$, absorbed by the stated error. This proves the major-arc value of the prime exponential sum:The original PDF does not state coprimality in this last request. Without it the asserted main term is genuinely false: $a=q=2$ makes $e(an/q)=1$ and hence ${\hat{\Lambda }}_N(a/q)=\psi (N)\sim N$, whereas $\mu (2)/\phi (2)=-1$. For an arbitrary numerator the correct main term is $N{c}_q(a)/\phi (q)$, with $c_q(a)$ given by the divisor formula above. Reducing the fraction before applying the boxed result is the equivalent repair.

A precise useful form of the principle is the type I–type II inverse principle for Möbius correlation. Normalize $|f(n)|\le 1$, and supposeFor any positive integer cutoffs $U,V$ with $U+V\le \delta X/2$, defineThen $|c_d|,|a_d|\le \tau (d)$, where $\tau$ is the divisor function, and at least one of the following two sums has modulus at least $\delta X/4$:The first is correlation against a controlled linear combination of indicators of multiples of small moduli, each a periodic function: this is the “somewhat periodic” branch. The second is a bilinear sum with independently weighted factors, both larger than the cutoffs: this is the “somewhat multiplicative” branch. The statement concerns these precise correlations, not an assertion that $f$ must itself be periodic or multiplicative.

For clarity, the Vaughan identity for the Möbius function proves this version immediately. Split $\mu ={\mu }_{\le U}+{\mu }_{>U}$ and likewise at $V$. Since $\mu \ast \mu \ast 1=\mu$,Multiply by $f(n)$ and sum. The first two terms contribute at most $U+V$ in modulus, and the remaining terms are $-T_{\mathrm{I}}+T_{\mathrm{II}}$. The triangle inequality gives the stated dichotomy. It is valid at finite $X$ and for any chosen cutoffs in the indicated range.

We now prove the required orthogonality without appealing to a stronger uniform exponential-sum theorem. Write $\alpha =\sqrt{2}$ and $e(u)=e^{2\pi iu}$. The Diophantine bound for the square root of two iswhere $\Vert u\Vert$ is distance to the nearest integer. If $a$ is that nearest integer, then $|2h^2-a^2|\ge 1$, while $h\sqrt{2}+a\le 4h$; dividing proves the bound.

Use the preceding Dirichlet convolution identity with $U=V=P=\lfloor X^{1/10}\rfloor$. The two short terms are $O(P)$. For the type I sum, the exponential geometric sum bound givesConsequentlyusing ${\sum }_{d\le Y}\tau (d)\ll Y\log (2Y)$ from counting factor pairs.

For the type II sum, perform a dyadic decomposition into $d\in (D,2D]$, $w\in (W,2W]$, keeping $dw\le X$. Nonempty blocks have $DW<X$, while $D,W\gg P$. A block $B$ satisfies, by the Cauchy-Schwarz inequality and the divisor-square summatory bound,To justify the cutoff, after expanding the square the permissible $d$ for a pair $w,w^{\prime }$ still form an interval, with upper endpoint $\min (2D,X/\max (w,w^{\prime }))$. Its exponential sum has the same geometric bound. Diagonal pairs supply $DW$; for each nonzero difference $h=w-w^{\prime }$ there are $O(W)$ pairs.

The points $0,\alpha ,2\alpha ,\dots ,\lfloor W\rfloor \alpha$ modulo one are separated by at least $1/(4W)$. Counting points in consecutive distance bands around zero therefore givesSubstitution yields the bilinear cancellation for badly approximable phases estimateThere are $O({\log }^{2}X)$ blocks, so $T_{\mathrm{II}}\ll X^{19/20}{\log }^{4}X$. The divisor-square bound itself can be obtained elementarily from $\tau (n{)}^2\le {\tau }_4(n)$ prime-power by prime-power and ${\sum }_{n\le Y}{\tau }_4(n)\le Y(1+\log Y{)}^3$; no uncontrolled coefficient bound is being suppressed.

Combining the short, type I and type II terms,Hence

Let $1(n)=1$ and $ϵ(n)=1_{n=1}$, the identity for Dirichlet convolution. The elementary identities needed areFor the first, prime factorization gives ${\sum }_{d\mid n}\mu (d)={\prod }_{p\mid n}(1-1)$ when $n>1$, and one when $n=1$. For the second, if $n=\prod p^{a_p}$, then ${\sum }_{d\mid n}\Lambda (d)={\sum }_p{a}_p\log p=\log n$, the Von Mangoldt divisor identity. Convolving the second identity with $\mu$ proves the third.

For $U,V\ge 1$, let the subscripts $\le U$, $>U$, $\le V$, $>V$ denote truncations. The Vaughan identity isIts pointwise form isTo prove it, use ${\mu }_{>U}\ast 1=ϵ-{\mu }_{\le U}\ast 1$ and $1\ast {\Lambda }_{>V}=\log -1\ast {\Lambda }_{\le V}$. This givesand rearrangement proves the formula, as in the Vaughan identity proof.

The Bombieri–Vinogradov theorem states that for every $A>0$ there is $B>0$ such thatHere $\psi (y;q,a)={\sum }_{\begin{array}{c}n\le y\\ n\equiv a(\mathrm{mod}q)\end{array}}\Lambda (n)$ is the Chebyshev function in an arithmetic progression, and $\varphi$ is the Euler totient function. In particular, partial summation givesafter choosing the logarithmic saving in the weighted theorem sufficiently large and absorbing the prime power terms. This is the offset logarithmic integral function.

For the proof strategy, Orthogonality of Dirichlet characters converts errors in arithmetic progressions into character sums of Dirichlet characters weighted by $\Lambda$. Reduction to primitive Dirichlet characters is followed by the character large sieve, which bounds their mean square by $O((N+Q^2)\sum |a_n{|}^2)$ with the usual $q/\varphi (q)$ weights. The Vaughan identity separates the weighted sums into short terms, Type I sums and Type II sums. Direct inner-sum estimates handle the Type I sums; the Cauchy-Schwarz inequality and the large sieve control the Type II sums. The Siegel–Walfisz theorem supplies arbitrarily strong logarithmic savings for small moduli, where an average estimate alone would not suffice. A dyadic decomposition, suitable $U,V$ and a sufficiently large $B$ absorb the divisor and logarithmic losses. This explains why the range is essentially $Q^2\le x$, with logarithmic room to spare.

With ${\mu }_{\le U}(d)=\mu (d)1_{d\le U}$ and analogous notation for ${\Lambda }_{\le V}$, Vaughan identity isThus, when $UV\le N$,The first term is short, the next two are Type I sums, and the last becomes a Type II bilinear sum after grouping variables and applying a dyadic decomposition.

Suppose $|a_u|\le \tau (u)$, $|b_d|\le \log (2N)$, $u,d>X\ge 1$, $ud\le N$, and $|\theta -a/q|\le q^{-2}$ with $(a,q)=1$. A dyadic decomposition reduces $S=\sum a_u{b}_{d}e(\theta ud)$ to blocks $u\asymp U,d\asymp D$. The Cauchy-Schwarz inequality, divisor-square summatory bound and the reciprocal fractional-part sum near a rational giveThe condition $ud\le N$ makes the allowed $u$ values for each pair $d_1,d_2$ an interval, so the exponential geometric sum bound applies despite the hyperbolic cutoff. Since $UD\le N$ and $U,D\gg X$, take square roots and sum the $O({\log }^2(2N))$ blocks to get the displayed estimate.