Vaughan's decomposition

In this post I will perform a routine task of verifying something routine.

Let $U,V,N$ be positive integers satisfying $UV < N^{0.9}$. The exponent here can be replaced by any positive number $<1$ but I don't want to complicate the notation.

For integers $N^{0.9} \le n\le N $ first note the following identity: \[ \mu (n) = \sum _{b,c \ge 1,\ bc | n} \mu (b) \mu (c) . \] Indeed we know by the Mobius inversion formula that $\mu * 1 $ is the identity element for Dirichlet's convolusion $*$ and hence $\mu = \mu *\mu * 1 $. Let us partition the sum according to whether $b\le U$ and $c\le V$ hold or not:

(1) $b\le U$, $c\le V$;

(2) $b>U$, $c\le V$;

(3) $b\le U$, $c>V$;

(4) $b>U$, $c\le V$, so that if we write $\sum _i $ for the partial sums we have $\mu (n) = \sum _1 + \sum _2 + \sum _3 + \sum _4$.

We claim that $\sum _1 + \sum _2=0 $. To see this note $\sum _1+\sum _2 = \sum _{c<V} \mu (c) \left( \sum _{b, b|\frac n c} \mu (b) \right) $. For each fixed $c$ (necessarily $< n$ because $c\le V<N^{0.9}\le n $), we know $\sum _{b, b| \frac n c } \mu (b) =0$. The claim follows. Likewise we have $\sum _1 +\sum _3 =0$. It follows that for any $N^{0.9} \le n \le N$: \[ \mu (n) = -\sum {}_1 +\sum {}_4 . \] This kind of decomposition is called Vaughan's identity.

Let $f\colon \mathbf N \to \mathbf C$ be a function. Let $\bar f \colon \mathbf N\to \mathbf C $ be the pointwise complex conjugation. Apply $\mathbb E_{n}(-)\cdot \bar f(n) $ on the previous decomposition to get the following, which we call the Vaughan decomposition for later reference: \[ \mathbb E _{N^{0.9} \le n \le N } \mu (n) \bar f(n) = - \mathbb E _{N^{0.9}\le n\le N} \sum _{b\le U,c\le V, bc|n } \mu (b) \mu (c) \bar f(n)  + \mathbb E _{N^{0.9}\le n\le N} \sum _{b>U,c>V,bc|n }\mu (b)\mu (c) \bar f(n) . \] At some stage we will want to show that the left hand side is small under certain conditions. To that end we assume to the contrary. Then at least one term in the right hand side must have large magnitude. To take advantage of that information we have to have a closer look at each term. In this post we address the first term.

Consider the paramaters $d=bc $ and $w=n/(bc) $ so that the first term can be written as \[ \frac 1{N-N^{0.9} } \sum _{d\le UV} \sum _{b,c; bc =d, b\le U,c\le V} \mu (b) \mu (c) \sum _{\frac{N^{0.9} }d\le w \le \frac N d } \bar f (dw ) .\] For any fixed $d$, the number of pairs $b,c $ appearing in the second $\sum $ is at most $\le t(d)$ where $t\colon \mathbf N \to \mathbf N $ is the "divisor function" which maps $n$ to the number of positive divisors of $n$ (for a TeXnical reason I'm typing $t$ for the Greek letter tau). This gives us a bound of the magnitude of this sum: \[ \le \frac 1{N-N^{0.9} } \sum _{d\le UV } t(d) \sum _{N^{0.9}/d < w < N/d} \bar f(dw ) = \sum _{d\le UV}t(d) \cdot \frac 1d \mathbb E_{N^{0.9}/d < w < N/d} \bar f(dw ).  \]

The right hand side can be seen as the inner product of the vectors $( t(d)/\sqrt d )_d$ and $\left( \frac 1{\sqrt d} \mathbb E _{N^{0.9}/d < w < N/d} \bar f(dw ) \right)_d $ so the Cauchy-Schwarz inequality gives: \[ (previous )^2 \le (\sum _{d\le UV } t(d)^2 /d ) ( \sum _{d\le UV} \frac 1d | \mathbb E_{N^{0.9}/d \le w \le N/d } \bar f (dw ) |^2 )  . \tag{*} \]

The sum $\sum _{d\le UV} t(d)^2 /d $ can be bounded by a familiar function (which seems to be classical). First we consider how to bound $\sum _{n\le N} t(n)^2$. Let $d_1, d_2 \le N$ be integers. For how many $n$ can $d_1$ and $d_2$ be both divisors of $n$? Well, $d_1$ and $d_2$ are both divisors of $n$ if and only if $n$ is a multiple of the least common multiple $[d_1,d_2] $. Therefore the number of such $n$ is bounded from above by $N/[d_1, d_2 ] $. It follows that \[ \sum _{n\le N} t(n)^2 \le \sum _{d_1,d_2\le N} \frac N{[d_1,d_2]} . \] Consider the quantities $\delta _0 = (d_1,d_2)$, $\delta _1 = d_1 / (d_1,d_2)$ and $\delta _2 = d_2/(d_1,d_2) $. Then $d_1$ and $d_2$ can be recovered from them by $d_i=\delta _0 \delta _i$ and we have $[d_1,d_2] = \delta _0 \delta _1 \delta _2 $. The right hand side is bounded by: \[ \le \sum _{\delta _0,\delta _1,\delta _2\le N } \frac N{\delta _0\delta _1\delta _2 } = N (\sum _{\delta =1}^N 1/\delta )^3 \ll N (\log N)^3  \] (the symbol $\ll $ means an inequality up to a bounded constant factor). Using this we bound $\sum _{d\le N} t(d)^2/d $ as follows. Partition the interval $[1,N]$ as $[1,2]\cup (2,4] \cup (4,8] \cup \cdots $. On the interval $(2^i, 2^{i+1}]$ we take the crude bound $\sum _{2^i<d\le 2^{i+1} } t(d)^2 /d  \ll \frac 1{2^i} \sum _{1\le d\le 2^{i+1} } t(d)^2 \ll 2^{i+1}  \log (2^{i+1} )^3 / 2^i  = 8 i^3 \log (2)^3 $. Adding them up for $1\le i\le \log _2 N $ we get $\ll (\log _2 N )^4 $. The bottom line is: \[ \sum _{1\le d\le UV}t(d)^2/d \ll (\log N )^4. \] 

It follows that the right-hand side of $(*)$ is bounded by \[ \le (\log N)^4 \sum _{d\le UV} \frac 1d | \mathbb E_{N^{0.9}/d \le w \le N/d } \bar f (dw ) |^2  \] Next we take the partition $[1,UV]=[1,2]\cup (2,4] \cup (4,8] \cup \cdots $ and find the subinterval $(D,2D] $ which maximizes the partial sum. Since the partition consists of at most $\log _2 N $ subintervals, with this $D$ we have: \[ \ll (\log N)^5 \frac 1 D \sum _{D< d\le 2D} | \mathbb E_{N^{0.9}/d \le w \le N/d } f (dw ) |^2. \]

Now if we assume $\delta < | \mathbb E_{N^{0.9}<n\le N} \mu (n) \bar f(n) | $ for some positive $\delta $ we conclude \[ \delta ^2 D (\log N)^{-5} \ll \sum _{D< d\le 2D} | \mathbb E_{N^{0.9}/d \le w \le N/d } f (dw ) |^2  \] for the $D$ above. Supposing $f\colon \mathbf N \to \mathbf C$ is bounded by $O(1)$, we conclude that, with $c_1,c_2>0$ appropriate small positive numbers, for $\ge c_1 \delta ^2 D (\log N)^{-5}$ values of $d$ we have \[ | \mathbb E_{N^{0.9}/d \le w \le N/d } f (dw ) |^2 \ge c_2 \delta ^2 D (\log N)^{-5} \tag{**} \] because otherwise we would have \[ \begin{array}{rl} \sum _{D< d\le 2D} | \mathbb E_{N^{0.9}/d \le w \le N/d } f (dw ) |^2  &\le O(1)\cdot c_1 \delta ^2 D (\log N)^{-5} + c_2 \delta ^2 (\log N)^{-5} \cdot D \\ &= (c_1O(1)+c_2 ) \delta ^2 D (\log N )^{-5} ,\end{array}\] a contradiction if the $c_1,c_2$ are appropriately chosen. Estimates like (**) will be useful the other day.

The second term in the Vaughan decomposition will be addressed in a separate post.