# Siegel zeros and Sarnak’s Conjecture

Jake Chinis

###### Abstract.

Assuming the existence of Siegel zeros, we prove that there exists an
increasing sequence of positive integers for which Chowla’s Conjecture on
$k$-point correlations of the Liouville function holds. This extends work of
Germán and Kátai, where they studied the case $k=2$ under identical
hypotheses.

An immediate corollary, which follows from a well-known argument due to
Sarnak, is that Sarnak’s Conjecture on Möbius disjointness holds. More
precisely, assuming the existence of Siegel zeros, there exists a subsequence
of the natural numbers for which the Liouville function is asymptotically
orthogonal to any sequence of topological entropy zero.

##  1\. Introduction

The Liouville function, $\lambda$, is the completely multiplicative function
defined by $\lambda(p):=-1$ for all primes $p$. As such, $\lambda(n)=1$ if $n$
has an even number of prime factors, counted with multiplicity, and
$\lambda(n)=-1$ otherwise. An important problem in analytic number theory is
to understand the asymptotic behaviour of the partial sums $\sum_{n\leq
x}\lambda(n)$. Viewing $\\{\lambda(n)\\}_{n}$ as a sequence of independent
random variables, each taking the value $\pm 1$ with equal probability, we
might expect that the partial sums of $\lambda$ exhibit some cancellation.
Indeed, the Prime Number Theorem (PNT) is equivalent to the fact

$\displaystyle\sum_{n\leq x}\lambda(n)=o(x),$

as $x\rightarrow\infty$. The Riemann Hypothesis (RH) is equivalent to the fact
that the partial sums of $\lambda$ exhibit “square-root cancellation:” for any
$\epsilon>0$,

$\displaystyle\sum_{n\leq x}\lambda(n)\ll x^{1/2+\epsilon},$

as $x\rightarrow\infty$. A famous conjecture due to Chowla [Cho65] states
similar estimates hold for multiple correlations of $\lambda$:

######  Conjecture 1.1 (Chowla’s Conjecture).

For any $k$ distinct integers $h_{1},\dots,h_{k}$,

$\displaystyle\sum_{n\leq x}\lambda(n+h_{1})\cdots\lambda(n+h_{k})=o_{k}(x),$

as $x\rightarrow\infty$, where we set $\lambda(n)=0$ for integers $n\leq 0$
and where the implied constant may depend on $h_{1},\dots,h_{k}$.

As stated earlier, the case $k=1$ is equivalent to the PNT. Chowla’s
Conjecture remains open for $k>1$ and the case $k=2$ is believed to be as
difficult as the Twin Prime Conjecture; see [Hil86].

######  Remark 1.1.

There are analogues of Chowla’s Conjecture over finite function fields. We
refer the reader to the work of Sawin and Shusterman [SS18], where they study
the relationship between Chowla’s Conjecture and the Twin Prime Conjecture
over finite function fields. It is interesting to note that Sawin and
Shusterman use the same general idea that we use in this paper (and that was
also used in [GK10]); namely, they approximate the Möbius function by a
Dirichlet character.

Although Chowla’s Conjecture still seems to be out of reach, there has been
much progress towards partial results of this conjecture, as well as proofs of
variations of Chowla’s original claim. For instance, Harman, Pintz, and Wolke
[HPW85] proved that

$\displaystyle-\frac{1}{3}+\mathcal{O}\Big{(}\frac{\log
x}{x}\Big{)}\leq\frac{1}{x}\sum_{n\leq x}\lambda(n)\lambda(n+1)\leq
1-\mathcal{O}_{\epsilon}\Big{(}\frac{1}{\log^{7+\epsilon}x}\Big{)},$

for all $\epsilon>0$. This was subsequently improved by Matomäki and Radziwiłł
[MR16] to

$\displaystyle\frac{1}{x}\Biggr{|}\sum_{n\leq
x}\lambda(n)\lambda(n+1)\Biggr{|}\leq 1-\delta,$

for some explicit constant $\delta>0$ and all $x$ sufficiently large.

Concerning weaker versions of Chowla’s Conjecture, Matomäki, Radziwiłł, and
Tao [MRT15] averaged over the parameters $h_{1},\dots,h_{k}$ and showed that,
for any $k\in\operatorname{\mathbb{N}}$ and any $10\leq h\leq x,$

$\displaystyle\sum_{1\leq h_{1},\dots,h_{k}\leq h}\Biggr{|}\sum_{n\leq
x}\lambda(n+h_{1})\cdots\lambda(n+h_{k})\Bigg{|}\ll k\Biggr{(}\frac{\log\log
h}{\log h}+\frac{1}{\log^{1/3000}x}\Biggr{)}h^{k}x,$

thus establishing an averaged form of Chowla’s Conjecture.

Tao [Tao16] made progress towards a logarithmically averaged version of
Chowla’s Conjecture by showing that

$\displaystyle\sum_{n\leq x}\frac{\lambda(n)\lambda(n+1)}{n}=o(\log x)$

as $x\rightarrow\infty.$ Following up on this, Tao and Teräväinen [TT18, TT19]
were able to establish a logarithmically averaged version of Chowla’s
Conjecture for odd $k$-point correlations; that is, for any odd
$k\in\operatorname{\mathbb{N}}$ and any integers $h_{1},\dots,h_{k}$,

$\displaystyle\sum_{n\leq
x}\frac{\lambda(n+h_{1})\cdots\lambda(n+h_{k})}{n}=o(\log x)$

as $x\rightarrow\infty$. Recently, Helfgott and Radziwiłł [HR21] improved the
bounds obtained by Tao in [Tao16] and Tao and Teräväinen in [TT19] for $k=2$.

######  Remark 1.2.

Note that the preceding results follow from Chowla’s Conjecture either
immediately or by partial summation. Furthermore, the same results can be
stated for the Möbius function, $\mu$, in place of $\lambda$, via the identity
$\mu(n)=\sum_{d^{2}|n}\mu(d)\lambda\left(\frac{n}{d^{2}}\right)$.

In this paper, we are concerned with the relationship between the Liouville
function and Siegel zeros. Our ultimate aim is to extend the work of Germán
and Kátai [GK10], where they studied $2$-point correlations of the Liouville
assuming the existence of Siegel zeros:

######  Theorem 1.1.

[GK10, Theorem 2] Let $\\{q_{\ell}\\}_{\ell}$ be an increasing sequence of
positive integers with corresponding sequence of real primitive characters
$\\{\chi_{\ell}\ (\text{mod}\ q_{\ell})\\}_{\ell}$. Suppose that
$L(s,\chi_{\ell})$ has a Siegel zero $\beta_{\ell}:=1-\frac{1}{\eta_{\ell}\log
q_{\ell}}$ with $\eta_{\ell}>\exp\exp(30)$ for all
$\ell\in\operatorname{\mathbb{N}}$. Then, there exists a constant $c>0$ and a
function $\varepsilon(x)\rightarrow 0$ as $x\rightarrow\infty$ such that

$\displaystyle\frac{1}{x}\Biggr{|}\sum_{n\leq
x}\lambda(n)\lambda(n+1)\Biggr{|}\leq\frac{c}{\log\log\eta_{\ell}}+\varepsilon(x),$

uniformly for $x\in[q_{\ell}^{10},q_{\ell}^{(\log\log\eta_{\ell})/3}]$.

The key to the work of Germán and Kátai is to approximate $\lambda$ by
$\chi_{\ell}$ on “large” primes via the completely multiplicative function
$\lambda_{r}$ defined by

$\displaystyle\lambda_{r}(p):=\left\\{\begin{array}[]{@{}l@{\quad}l@{}}\lambda(p)&\mbox{if
$p\leq r,$}\\\ \chi_{\ell}(p)&\mbox{if $p>r$,}\end{array}\right.$

for some well-chosen parameter $r=r_{\ell}$. Then, using similar ideas as
Heath-Brown in his work on Siegel zeros and the Twin Prime Conjecture [HB83],
Germán and Kátai show that the $2$-point correlations of $\lambda$ are well
approximated by the $2$-point correlations of $\lambda_{r}$, along a
subsequence. The added benefit to this approach is that we can now use sieve
theory, together with the definition of $\lambda_{r}$, to relate the $2$-point
correlations of $\lambda$ to some character sum, which is known to be small.
Following this same line of reasoning, we prove the corresponding result for
(general) $k$-point correlations:

######  Theorem 1.2.

Let $\\{q_{\ell}\\}_{\ell}$ be an increasing sequence of positive integers
with corresponding sequence of real primitive characters $\\{\chi_{\ell}\
(\text{mod}\ q_{\ell})\\}_{\ell}$. Suppose that $L(s,\chi_{\ell})$ has a
Siegel zero $\beta_{\ell}:=1-\frac{1}{\eta_{\ell}\log q_{\ell}}$ with
$\eta_{\ell}>\exp\exp(30)$ for all $\ell\in\operatorname{\mathbb{N}}$. Then,
for any distinct (positive) integers $h_{1},\dots,h_{k}$, there exists a
constant $c_{k}=c(h_{1},\dots,h_{k})>0$ such that

$\displaystyle\frac{1}{x}\Biggr{|}\sum_{n\leq
x}\lambda(n+h_{1})\cdots\lambda(n+h_{k})\Biggr{|}\leq\frac{c_{k}}{(\log\log\eta_{\ell})^{1/2}(\log\eta_{\ell})^{1/12}},$

uniformly for $x\in[q_{\ell}^{10},q_{\ell}^{(\log\log\eta_{\ell})/3}]$.

######  Remark 1.3.

Since $\eta_{\ell}\rightarrow\infty$ as $\ell\rightarrow\infty$ (see Section
2), Theorem 1.2 thus establishes Chowla’s Conjecture along a subsequence,
assuming the existence of Siegel zeros. Furthermore, one should think of
Theorem 1.1 as the multiplicative analogue of Heath-Brown’s result on Twin
Primes and Siegel zeros [HB83], while Theorem 1.2 is the multiplicative
analogue of the Hardy–Littlewood $k$-tuples conjecture (which is also known to
hold, assuming the existence of Siegel zeros).

######  Remark 1.4.

Notice that Theorem 1.2 is an improvement on Theorem 1.1 in two respects:
first, we can handle general $k$-point correlations (as opposed to the case
where $k=2$); further, we have an exponential improvement in our bounds (which
follows from using a different version of the Fundamental Lemma of Sieve
Theory and from taking a different choice of $r$ than those used in [GK10];
see Appendix A and the end of Section 4).

Note further that the work in [GK10] deals only with $h_{1}=0$ and $h_{1}=1$,
but the proof extends easily to general $h_{1}$, $h_{2}$ (with minor
modifications). The main difficulty in going from the case $k=2$ to general
$k$-point correlations lies in being able to parametrize integer solutions of
the following system of linear equations, in the unknowns $x_{0},x_{1},\dots
x_{k}$, for some integers $a_{0},a_{1},\dots,a_{k}$:

$\displaystyle\left\\{\begin{array}[]{@{}l@{\quad}l@{}}a_{1}x_{1}=a_{0}x_{0}+h_{1},\\\
\vdots\\\ a_{k}x_{k}=a_{0}x_{0}+h_{k}.\end{array}\right.$

It is to verify that, if this system is solvable, then the solutions are given
by $x_{i}=x_{i}^{*}+m\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})/a_{i}$, where
$(x_{0}^{*},x_{1}^{*},\dots,x_{k}^{*})$ is one particular solution and
$m\in\operatorname{\mathbb{Z}}$ (essentially generalizing Bezout’s Identity to
$k$ equations). From there, we need to bound character sums evaluated at the
polynomial $f(n):=(x_{0}^{*}+na_{0}^{*})\cdots(x_{k}^{*}+na_{k}^{*}),$ where
$a_{i}^{*}:=\operatorname{lcm}(a_{0},\dots,a_{k})/a_{i}$, as $n$ varies over
one complete residue class modulo $q_{\ell}$. Fortunately for us, these
character sums exhibit squareroot cancellation via Weil’s Bound, provided that
$f$ is not a square. For more details, see Appendices B and C.

###  1.1. Sarnak’s Conjecture

We should think of the previous results as instances of the so-called “Möbius
Randomness Law,” which states that the values of $\lambda$ (or $\mu$) are
random enough so that the twisted sums $\sum_{n\leq x}\lambda(n)a_{n}$ should
be small for any “reasonable” sequence of complex numbers $\\{a_{n}\\}_{n}$;
see [IK04, Section 13]. A famous conjecture due to Sarnak characterizes one
such family of “reasonable” sequences as those which are deterministic:

######  Definition 1.1.

Given a bounded sequence
$f:\operatorname{\mathbb{N}}\rightarrow\operatorname{\mathbb{C}}$, its
topological entropy is equal to the least exponent $\sigma$ for which the set

$\\{(f(n+1),f(n+1),\dots,f(n+m))\\}_{n=1}^{\infty}\subset\operatorname{\mathbb{C}}^{m}$

can be covered by $\mathcal{O}(\exp(\sigma m+o(m))$ balls of radius $\epsilon$
(in the $\ell^{\infty}$ metric), for any fixed $\epsilon>0$, as
$m\rightarrow\infty$. In the case where $\sigma=0$, we say that $f$ is
deterministic.

######  Conjecture 1.2 (Sarnak’s Conjecture).

Let $f:\operatorname{\mathbb{N}}\rightarrow\operatorname{\mathbb{C}}$ be a
deterministic sequence. Then,

$\displaystyle\sum_{n\leq x}\lambda(n)f(n)=o_{f}(x),$

as $x\rightarrow\infty.$

Although Sarnak’s Conjecture has yet to be resolved, there are many instances
for which the conjecture holds. For example, in the case where $f$ is
constant, Sarnak’s Conjecture is equivalent to the PNT; in the case where $f$
is periodic, it is equivalent to the PNT in arithmetic progressions. For a
more thorough survey on various instances for which Sarnak’s Conjecture holds,
see [FKPL18, KPL20].

By a well-known argument due to Sarnak, we also know that Chowla’s Conjecture
implies Sarnak’s Conjecture; as a result, Theorem 1.2 yields the following:

######  Corollary 1.1.

Let $f:\operatorname{\mathbb{N}}\rightarrow\operatorname{\mathbb{C}}$ be a
deterministic sequence. Under the hypotheses of Theorem 1.2,

$\displaystyle\sum_{n\leq x}\lambda(n)f(n)=o_{f}(x),$

for $x\in[q_{\ell}^{10},q_{\ell}^{(\log\log\eta_{\ell})/3}]$.

###### Proof.

The proof follows Sarnak’s argument verbatim, the details of which can be
found on Tao’s blog111https://terrytao.wordpress.com/2012/10/14/the-chowla-
conjecture-and-the-sarnak-conjecture/. For further work on the relationship
between Chowla’s Conjecture and Sarnak’s Conjecture, see [AKPLdlR17, GKL18,
GLdlR20]. ∎

###  1.2. Outline

Our paper is split as follows: in Section 2, we give a brief introduction on
Siegel zeros and the work of Heath-Brown on counting the number of primes $p$
such that $\chi(p)=1$; in Section 3, we use the work of Germán–Kátai/Heath-
Brown to relate the $k$-point correlations of $\lambda$ to those of
$\lambda_{r}$; from there, we use some estimates on character sums, sieve
theory, and elementary number theory to prove Theorem 1.2; Appendices A, B,
and C contain the relevant background information on sieve theory, character
sums, and Diophantine equations, which we use freely in the proof of Theorem
1.2.

##  2\. Siegel zeros and primes $p$ such that $\chi(p)=1$

In this section, we provide a brief introduction to Siegel zeros, culminating
in the work of Heath-Brown on primes $p$ such that $\chi(p)=1$. To begin, we
must first discuss zero-free regions of Dirichlet $L$-functions associated to
Dirichlet characters $\chi\ (\text{mod}\ q)$; we follow Chapter 12 of [Kou20]:

######  Theorem 2.1.

Let $q\geq 3$ and set $Z_{q}(s):=\prod_{\chi\ (\text{mod}\ q)}L(s,\chi)$.
Then, there is an absolute constant $c>0$ such that the region $\Re(s)\geq
1-\frac{c}{\log(q\tau)},$ where $\tau=\max\\{1,|\Im(s)|\\}$, contains at most
one zero of $Z_{q}$. Furthermore, if this exceptional zero exists, then it is
necessarily a real, simple zero of $Z_{q}$, say $\beta_{1}\in[1-c/\log q,1]$,
and there is a real, non-principal character $\chi_{1}\ (\text{mod}\ q)$ such
that $L(\beta_{1},\chi_{1})=0$.

###### Proof.

See [Kou20, Theorem 12.3], for example. ∎

We call the character $\chi_{1}$ in Theorem 2.1 an exceptional character and
its zero, $\beta_{1}$, is the associated exceptional zero, or
Siegel/Landau–Siegel zero. Note that this exceptional character depends on the
choice of absolute constant and that this relationship implies some
interesting facts:

  1. (1)

If we have one exceptional character, then we actually have infinitely many
exceptional characters: if we had only finitely many exceptional characters
$\chi_{i}\ (\text{mod}\ q_{i})$, we could set
$c^{\prime}:=\frac{1}{2}\min_{i}\\{(1-\beta_{i})\log q_{i}\\}$ and we would
then have that

$1-\frac{c}{\log q_{i}\tau}\leq\beta_{i}<1-\frac{c^{\prime}}{\log q_{i}\tau}$

for all $i$; in particular, replacing $c$ with $c^{\prime}$ in Theorem 2.1, we
no longer have any exceptional zeros.

  2. (2)

Similarly, we can take $c$ to be arbitrarily small: if there are no
exceptional zeros for $c$ small enough, then we are done.

Thus, when we talk about Siegel zeros/exceptional characters, we are actually
talking about an infinite sequence of real, primitive Dirichlet characters
$\\{\chi_{\ell}\ (\text{mod}\ q_{\ell})\\}_{\ell=1}^{\infty}$ for which
$L(s,\chi_{\ell})$ has a real zero

(2.1)
$\displaystyle\beta_{\ell}=1-o_{\ell\rightarrow\infty}\left(\frac{1}{\log
q_{\ell}}\right),$

and such that no product $\chi_{\ell}\chi_{\ell^{\prime}}$ is principal for
any $\ell\neq\ell^{\prime}$. Using Siegel’s Theorem, we can quantify the rate
of convergence in Equation (2.1):

######  Theorem 2.2 (Siegel).

Let $\epsilon>0$. Then, there is a constant $c(\epsilon)>0$, which cannot be
computed effectively, such that $L(\sigma,\chi)\neq 0$ for
$\sigma>1-c(\epsilon)q^{-\epsilon}$ and for all real, non-principal Dirichlet
characters $\chi\ (\text{mod}\ q)$.

###### Proof.

See [Kou20, Theorem 12.10], for example. ∎

In particular,

(2.2) $\displaystyle\eta_{\ell}:=((\beta_{\ell}-1)\log q_{\ell})^{-1}\ll
q_{\ell},$

as $\ell\rightarrow\infty$. In fact, one could show that $\eta_{\ell}\ll$ any
fixed power of $q_{\ell}$, but the above is all we need for our purposes.

Now that we know exactly what we mean by Siegel zeros/exceptional characters,
we can consider consequences of their existence. For example, Heath-Brown
[HB83] showed, under similar hypotheses to Theorem 1.2, that the existence of
Siegel zeros implies the Twin Prime Conjecture. Recently, Granville [Gra20]
used the existence of Siegel zeros to study problems in sieve theory, such as
improving (conditionally) lower bounds on the longest gaps between primes. For
our purposes, we are interested in the following lemma, due to Germán and
Kátai, which is a variation of Lemma 3 in [HB83]:

######  Lemma 2.1 ([GK10]).

Let $\\{\chi_{\ell}\ (\text{mod}\ q_{\ell})\\}_{\ell}$ denote a sequence of
exceptional characters with corresponding Siegel zero

$\beta_{\ell}=1-\frac{1}{\eta_{\ell}\log q_{\ell}},$

with $\eta_{\ell}>\exp(\exp(30))$. Then,

$\sum_{\begin{subarray}{c}{p\leq x}\\\
{\chi_{\ell}(p)=1}\end{subarray}}\frac{\log p}{p}\ll\exp\left(\frac{\log
x}{\log q_{\ell}}\right)(\log q_{\ell})(\log\eta_{\ell})^{-1/2},$

uniformly for $x\in[q_{\ell}^{10},q_{\ell}^{(\log\log\eta_{\ell})/3}].$

######  Remark 2.1.

Note that the upper bound in Lemma 2.1 is worse than that in Lemma 3 of
[HB83], but the range of admissible $x$ is larger: Lemma 3 of [HB83] yields
the upper bound $\ll(\log q_{\ell})(\log\eta_{\ell})^{-1/2}$, uniformly for
$x\in[q_{\ell}^{250},q_{\ell}^{500}]$ (so that Lemma 2.1 recovers Heath-
Brown’s result when $x$ is restricted to the interval
$[q_{\ell}^{250},q_{\ell}^{500}]$).

With Lemma 2.1 in tow, we can now approximate $\lambda$ by a Dirichlet
character on large primes; this is done in the next section.

##  3\. Going from $\lambda$ to $\lambda_{r}$

From now on, we fix a character $\chi_{\ell}\ (\text{mod}\ q_{\ell})$, so that
we may drop the dependence on $\ell$. Using Lemma 2.1, we can relate the
$k$-point correlations of the Liouville function to the $k$-point correlations
of the completely multiplicative function $\lambda_{r}$, which is defined by

(3.3)
$\displaystyle\lambda_{r}(p):=\left\\{\begin{array}[]{@{}l@{\quad}l@{}}\lambda(p)&\mbox{if
$p\leq r$}\\\ \chi(p)&\mbox{if $p>r$},\end{array}\right.$

where $r:=x^{1/((\log\log\eta)^{1/2}(\log\eta)^{1/12})}$. The details can be
found in pages 48-50 of [GK10]; we reproduce their results here, for
convenience/completeness222In [GK10], the authors take
$:r=x^{1/\log\log\eta}$, which produces an error of size $1/\log\log\eta$ in
Theorem 1.1. Making a different choice of $r$ and using a different version of
the FLST allows us to obtain better estimates; see the very end of Section 4
for why the choice of $r=x^{1/((\log\log\eta)^{1/2}(\log\eta)^{1/12})}$ was
made/is optimal.:

######  Lemma 3.1.

Suppose $h_{1},\dots,h_{k}$ are distinct (positive) integers. Set
$\lambda(n;k):=\lambda(n+h_{1})\cdots\lambda(n+h_{k})$ and define
$\lambda_{r}(n;k)$ in the same way. Then, under the assumptions of Theorem
1.2,

$\frac{1}{x}\sum_{n\leq x}\lambda(n;k)=\frac{1}{x}\sum_{n\leq
x}\lambda_{r}(n;k)+\mathcal{O}_{k}\left(\frac{1}{(\log\log\eta)^{1/2}(\log\eta)^{1/12}}\right),$

uniformly for $x\in[q^{10},q^{(\log\log\eta)/{3}}]$.

###### Proof.

Note that

$\displaystyle\sum_{n\leq x}\lambda(n;k)$ $\displaystyle=\sum_{n\leq
x}\Big{(}\lambda(n;k)\pm\lambda_{r}(n+h_{1})\lambda(n+h_{2})\cdots\lambda(n+h_{k})\Big{)}$
$\displaystyle=\sum_{n\leq
x}\Big{(}\lambda(n+h_{1})-\lambda_{r}(n+h_{1})\Big{)}\lambda(n+h_{2})\cdots\lambda(n+h_{k})+\sum_{n\leq
x}\lambda_{r}(n+h_{1})\lambda(n+h_{2})\cdots\lambda(n+h_{k}).$

Continuing by induction, we have that

$\displaystyle\left|\sum_{n\leq
x}\Big{(}\lambda(n;k)-\lambda_{r}(n;k)\Big{)}\right|$
$\displaystyle\leq\sum_{i=1}^{k}\sum_{n\leq
x}|\lambda(n+h_{i})-\lambda_{r}(n+h_{i})|$ $\displaystyle=k\sum_{n\leq
x}|\lambda(n)-\lambda_{r}(n)|+\mathcal{O}_{k}(1),$

where the last line follows from the “approximate translation-invariance” of
the partial sums, noting that the error term depends on $h_{1},\dots,h_{k}$.
To bound $\sum_{n\leq x}|\lambda(n;k)-\lambda_{r}(n;k)|,$ recall the
definition of $\lambda_{r}$ from Equation (3.3) and note that

$\displaystyle\sum_{n\leq x}|\lambda(n)-\lambda_{r}(n)|$
$\displaystyle=\sum_{n\leq
x}\Biggr{|}\prod_{p^{\alpha}||n}\lambda(p^{\alpha})-\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p\leq
r}\end{subarray}}\lambda(p^{\alpha})\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p>r}\end{subarray}}\chi(p^{\alpha})\Biggr{|}$ $\displaystyle=\sum_{n\leq
x}\Biggr{|}\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\ {p\leq
r}\end{subarray}}\lambda(p^{\alpha})\Biggr{(}\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p>r}\end{subarray}}\lambda(p^{\alpha})-\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p>r}\end{subarray}}\chi(p^{\alpha})\Biggr{)}\Biggr{|}$
$\displaystyle=\sum_{n\leq
x}\Biggr{|}\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p>r}\end{subarray}}\lambda(p^{\alpha})-\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p>r}\end{subarray}}\chi(p^{\alpha})\Biggr{|}.$

Then, using the fact that

$\left|\prod_{i}x_{i}-\prod_{i}y_{i}\right|\leq\sum_{i}|x_{i}-y_{i}|,$

for all $x_{i},y_{i}\in\\{-1,0,1\\}$, we have that

$\displaystyle\sum_{n\leq
x}\Biggr{|}\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p>r}\end{subarray}}\lambda(p^{\alpha})-\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p>r}\end{subarray}}\chi(p^{\alpha})\Biggr{|}$ $\displaystyle\leq\sum_{n\leq
x}\sum_{\begin{subarray}{c}{p^{\alpha}||n}\\\
{p>r}\end{subarray}}|\lambda(p^{\alpha})-\chi(p^{\alpha})|$
$\displaystyle\leq\sum_{\begin{subarray}{c}{p^{\alpha}\leq x}\\\
{p>r}\end{subarray}}|\lambda(p^{\alpha})-\chi(p^{\alpha})|\sum_{\begin{subarray}{c}{n\leq
x}\\\ {p^{\alpha}||n}\end{subarray}}1$ $\displaystyle\ll
x\sum_{\begin{subarray}{c}{p^{\alpha}\leq x}\\\
{p>r}\end{subarray}}\frac{|\lambda(p^{\alpha})-\chi(p^{\alpha})|}{p^{\alpha}}$
$\displaystyle=x\sum_{r<p\leq
x}\frac{|\lambda(p)-\chi(p)|}{p}+x\sum_{\begin{subarray}{c}{p^{\alpha}\leq
x}\\\ {p>r}\\\ {\alpha\geq
2}\end{subarray}}\frac{|\lambda(p^{\alpha})-\chi(p^{\alpha})|}{p^{\alpha}}.$

The sum over the higher prime powers can be bounded trivially:

$\displaystyle x\sum_{\begin{subarray}{c}{p^{\alpha}\leq x}\\\ {p>r}\\\
{\alpha\geq
2}\end{subarray}}\frac{|\lambda(p^{\alpha})-\chi(p^{\alpha})|}{p^{\alpha}}\ll
x\sum_{p>r}\sum_{\alpha\geq 2}\frac{1}{p^{\alpha}}\ll\frac{x}{r}.$

For the sum over the primes, recall that $\lambda(p)=-1$, which yields:

$\displaystyle x\sum_{r<p\leq x}\frac{|\lambda(p)-\chi(p)|}{p}$
$\displaystyle=x\sum_{\begin{subarray}{c}{r<p\leq x}\\\
{\chi(p)=1}\end{subarray}}\frac{2}{p}+x\sum_{\begin{subarray}{c}{r<p\leq x}\\\
{\chi(p)=0}\end{subarray}}\frac{1}{p}$ $\displaystyle\ll\frac{x}{\log
r}\sum_{\begin{subarray}{c}{r<p\leq x}\\\ {\chi(p)=1}\end{subarray}}\frac{\log
p}{p}+\frac{x}{\log r}\sum_{\begin{subarray}{c}{r<p\leq x}\\\
{\chi(p)=0}\end{subarray}}\frac{\log p}{p},$

where the last line follows from the fact that $\log p/\log r>1$ for all
$p>r$. Since $\chi(p)=0$ iff $p|q$, the sum over primes $p$ such that
$\chi(p)=0$ can be bounded above by

$\displaystyle\frac{x}{\log r}\sum_{\begin{subarray}{c}{r<p\leq x}\\\
{\chi(p)=0}\end{subarray}}\frac{\log p}{p}$ $\displaystyle\ll\frac{x}{\log
r}\left(\sum_{p\leq\log q}\frac{\log p}{p}+\sum_{\begin{subarray}{c}{\log
q<p\leq x}\\\ {p|q}\end{subarray}}\frac{\log p}{\log q}\right)$
$\displaystyle\ll\frac{x}{\log r}\left(\log\log q+1\right)$
$\displaystyle\ll\frac{x\log\log q}{\log r}.$

For the remaining sum, we can apply Lemma 2.1, which yields:

$\displaystyle\frac{x}{\log r}\sum_{\begin{subarray}{c}{r<p\leq x}\\\
{\chi(p)=1}\end{subarray}}\frac{\log p}{p}$ $\displaystyle\ll\frac{x}{\log
r}\exp\left(\frac{\log x}{\log q}\right)(\log q)(\log\eta)^{-1/2}.$

Recalling that $x\in[q^{10},q^{{(\log\log\eta)}/{3}}],$
$r=x^{1/((\log\log\eta)^{1/2}(\log\eta)^{1/12})}$, and $\eta\ll q$, the total
error is then bounded above by

$\displaystyle\frac{x}{\log r}$ $\displaystyle\left(\exp\left(\frac{\log
x}{\log q}\right)(\log q)(\log\eta)^{-1/2}+\log\log
q\right)+\frac{x}{r}\ll\frac{x}{(\log\log\eta)^{1/2}(\log\eta)^{1/12}},$

which follows from the fact that

$\frac{1}{\log r}\exp\left(\frac{\log x}{\log q}\right)(\log
q)(\log\eta)^{-1/2}=\frac{(\log\log\eta)^{1/2}(\log\eta)^{1/12}}{\log
x}\exp\left(\frac{\log x}{\log q}\right)(\log q)(\log\eta)^{-1/2}$

is an increasing function of $x$ (for $x\geq q$), whose maximum on the
interval $[q^{10},q^{(\log\log\eta)/3}]$ will occur at
$x=q^{(\log\log\eta)/3}.$ In any case, we then have that

$\displaystyle\frac{1}{x}\sum_{n\leq x}\lambda(n;k)=\frac{1}{x}\sum_{n\leq
x}\lambda_{r}(n;k)+\mathcal{O}_{k}\left(\frac{1}{(\log\log\eta)^{1/2}(\log\eta)^{1/12}}\right),$

as claimed. ∎

From Lemma 3.1, it now suffices to bound the $k$-point correlations of
$\lambda_{r}$ in order to prove Theorem 1.2; the next section is dedicated to
this task.

##  4\. Proof of Theorem 1.2

In this section, we complete the proof of Theorem 1.2 by bounding the
$k$-point correlations of $\lambda_{r}$. Our main tool is the Fundamental
Lemma of Sieve Theory (Lemma A.1), but before we can use this, we must first
control the so-called “level of distribution” of the sieve; this is done with
some preliminary sieving, by removing integers with “small” prime factors:

######  Lemma 4.1 (Controlling the level of distribution).

Let $r<x$ and suppose $A_{x}\rightarrow\infty$ as $x\rightarrow\infty$.
Then333In [GK10], the bound $x/A_{x}$ is simply written as $o(x)$, which is
where this $\varepsilon(x)$ function comes from in Theorem 1.1. Keeping track
of this error and then optimising the choice of $r$ is how we obtain the
improvements in Theorem 1.2.:

$\\#\\{n\leq x:\prod_{\begin{subarray}{c}{p^{\alpha}||n}\\\ {p\leq
r}\end{subarray}}p^{\alpha}>r^{A_{x}}\\}\ll\frac{x}{A_{x}}.$

###### Proof.

This follows from Chebyshev’s Inequality. ∎

Using Lemma 4.1, we can now restrict ourselves to integers $n\leq x$ such that
the $r$-smooth parts of $n+h_{i}$ are all bounded above by $r^{A_{x}}$, for
some $A_{x}$ going to infinity slowly enough with respect to both $x$ and
$\eta$:

$\sum_{n\leq x}\lambda_{r}(n;k)=\sum_{\begin{subarray}{c}{n\leq x}\\\
{\prod_{\begin{subarray}{c}{p^{\alpha}||(n+h_{i})}\\\ {p\leq
r}\end{subarray}}p^{\alpha}}\leq
r^{A_{x}}\end{subarray}}\lambda_{r}(n;k)+\mathcal{O}\left(\frac{x}{A_{x}}\right).$

Note: we will eventually choose
$A_{x}\asymp_{k}(\log\log\eta)^{1/2}(\log\eta)^{1/12}$, which produces an
admissible error in Theorem 1.2. For simplicity, we assume that $h_{1}=0$ and
relabel the remaining indices: this amounts to shifting the sum over $n$ by
$h_{1}$ (which incurs an error of $\mathcal{O}_{k}(1)$), so that
$h_{i}:=h_{i}-h_{1}$ for $i=2,3,\dots,k$. Relabeling the indices as
$i=1,2,\dots,k$, it suffices to bound

$\sum_{\begin{subarray}{c}{n\leq x}\\\
{\prod_{\begin{subarray}{c}{p^{\alpha}||(n+h_{i})}\\\ {p\leq
r}\end{subarray}}p^{\alpha}}\leq
r^{A_{x}}\end{subarray}}\lambda(n)\lambda_{r}(n+h_{1})\cdots\lambda_{r}(n+h_{k}),$

where we should think of $k$ as $k-1$, with $h_{0}=0$.

Next, write $n$ as $a_{0}b_{0}$, where $a_{0}$ is the $r$-smooth part of $n$
and where $b_{0}$ is the $r$-sifted part. Doing the same procedure for
$n+h_{i}$, $i=1,\dots,k$, we have that $a_{i}b_{i}=a_{0}b_{0}+h_{i}$ and, in
order for this system to be solvable, it is necessary that
$(a_{i},a_{j})|(h_{i}-h_{j})$ for all $i\neq j$, recalling that $h_{0}=0$.
Then:

$\sum_{\begin{subarray}{c}{n\leq x}\\\
{\prod_{\begin{subarray}{c}{p^{\alpha}||(n+h_{i})}\\\ {p\leq
r}\end{subarray}}p^{\alpha}}\leq
r^{A_{x}}\end{subarray}}\lambda_{r}(n)\lambda_{r}(n+h_{1})\cdots\lambda_{r}(n+h_{k})=\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\lambda(a_{0})\lambda(a_{1})\cdots\lambda(a_{k})\sum_{\begin{subarray}{c}{b_{0}\leq
x/a_{0}}\\\ {a_{i}b_{i}=a_{0}b_{0}+h_{i}}\\\ {p|b_{i}\Rightarrow
p>r}\end{subarray}}\chi(b_{0})\chi(b_{1})\cdots\chi(b_{k}),$

which follows from the definition of $\lambda_{r}$ and after writing each
$n+h_{i}$ as a product of its $r$-smooth and its $r$-sifted parts.

The key now is to parametrize the $b_{i}$’s and to notice that if the system

$\displaystyle\left\\{\begin{array}[]{@{}l@{\quad}l@{}}a_{1}b_{1}=a_{0}b_{0}+h_{1},\\\
\vdots\\\ a_{k}b_{k}=a_{0}b_{0}+h_{k},\end{array}\right.$

is solvable in the unknowns $b_{0},b_{1},\dots,b_{k}$, then the solutions are
given by

$b_{i}=b_{i}^{*}+m\frac{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}{a_{i}}=:b_{i}^{*}+ma_{i}^{*},$

where $(b_{0}^{*},b_{1}^{*},\dots,b_{k}^{*})$ is one particular solution to
the system and where $m$ ranges over all integers; see Appendix C.
Furthermore, we can take the $b_{i}^{*}$’s to be positive and minimal, in the
sense that $b_{i}^{*}>0$ for all $i$, while $b_{i}^{*}-a_{i}^{*}<0$ for at
least one $i$ (this allows us to restrict ourselves to non-negative integers
$m$ and makes it so that $0<b_{i}^{*}<a_{i}^{*}$ for at least one $i$, both of
which are required to be completely rigorous in the next step). Then, using
the fact that $\chi$ is periodic modulo $q$, we can write our sum as

(4.1) $\displaystyle\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\lambda(a_{0})\lambda(a_{1})\cdots\lambda(a_{k})\sum_{\begin{subarray}{c}{b_{0}\leq
x/a_{0}}\\\ {a_{i}b_{i}=a_{0}b_{0}+h_{i}}\\\ {p|b_{i}\rightarrow
p>r}\end{subarray}}\chi(b_{0})\chi(b_{1})\cdots\chi(b_{k})$ (4.2)
$\displaystyle=\sideset{}{{}^{*}}{\sum}_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\lambda(a_{0})\lambda(a_{1})\cdots\lambda(a_{k})\sum_{n=0}^{q-1}\chi(b_{0}^{*}+na_{0}^{*})\chi(b_{1}^{*}+na_{1}^{*})\cdots\chi(b_{k}+na_{k}^{*})$
(4.3)
$\displaystyle\quad\quad\quad\times\left(\\#\left\\{m\leq\frac{x}{q\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}:\left(\prod_{i=0}^{k}(b_{i}^{*}+na_{i}^{*}+mqa_{i}^{*}),\prod_{p\leq
r}p\right)=1\right\\}+\mathcal{O}_{k}(1)\right),$

where the last factor counts the number of solutions which fall into each
congruence class modulo $q$ and where $\sideset{}{{}^{*}}{\sum}$ indicates
that we are only summing over the $a_{i}$’s for which the system is solvable.
The conditions on $a_{i}$ which make the system solvable are determined by the
Smith Normal Form of the system; see Appendix C. For our purposes, we only
care about the necessary condition $(a_{i},a_{j})|(h_{i}-h_{j})$: this will
allow us to control $\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})$, which will
be needed later on in the proof. Note: the Big-O term comes from the fact that
we are really looking at $b_{0}=b_{0}^{*}+na_{0}^{*}+mqa_{0}^{*}\leq x/a_{0}$
(so that $m\leq x/(qa_{0}a_{0}^{*})-b_{0}^{*}/qa_{0}^{*}-n/q$, with $0\leq
n\leq q-1$).

Now, the Fundamental Lemma of Sieve Theorem (FLST, Lemma A.1) can be used to
count the number of solutions which fall into each congruence class. The
starting point for this is to get an asymptotic estimate for the number of
such $m$ which fall into the arithmetic progression $0\ (\text{mod}\ d)$ for
$d|\prod_{p\leq r}p$. So, let

$\nu(d):=\\#\left\\{m\in\operatorname{\mathbb{Z}}/d\operatorname{\mathbb{Z}}:\prod_{i=0}^{k}(b_{i}^{*}+na_{i}^{*}+mqa_{i}^{*})\equiv
0\ (\text{mod}\ d)\right\\}$

and note that

$\displaystyle\\#\left\\{m\leq\frac{x}{q\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}:\prod_{i=0}^{k}(b_{i}^{*}+na_{i}^{*}+mqa_{i}^{*})\equiv
0\ (\text{mod}\ d)\right\\}$
$\displaystyle=\frac{x}{q\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}\frac{\nu(d)}{d}+\mathcal{O}(\nu(d)).$

By the Chinese Remainder Theorem, $\nu(d)$ is completely determined by
$\nu(p)$, for $p\leq r$. Moreover, $\nu(p)$ is equal to the number of distinct
solutions $m\ (\text{mod}\ p)$ to any of the following linear congruences:

$\displaystyle\left\\{\begin{array}[]{@{}l@{\quad}l@{}}(qa_{0}^{*})m\equiv-(b_{0}^{*}+na_{0}^{*})\
(\text{mod}\ p)\\\ (qa_{1}^{*})m\equiv-(b_{1}^{*}+na_{1}^{*})\ (\text{mod}\
p)\\\ \vdots\\\ (qa_{k}^{*})m\equiv-(b_{k}^{*}+na_{k}^{*})\ (\text{mod}\
p).\end{array}\right.$

In order to obtain precise estimates for $\nu(p)$, we consider various
possibilities depending on whether or not $qa_{i}^{*}$ is invertible modulo
$p$. For starters, we restrict the sum over $n$ to the sum over $n$ such that
$(b_{i}^{*}+na_{i}^{*},q)=1$ for all $i$; otherwise,
$\chi(b_{i}^{*}+na_{i}^{*})=0$, which contributes nothing to Equation 4.1. We
consider the following scenarios:

  1. (1)

$p|q$: In the case where $p|q$, there are no solutions because this would
require that $p|b_{i}^{*}+na_{i}^{*}$ for at least one $i$, contrary to our
hypothesis that $(b_{i}^{*}+na_{i}^{*},q)=1$ for all $i$; i.e., $\nu(p)=0$
when $p|q$.

  2. (2)

$p\nmid qa_{0}a_{1}\dots a_{k}$: In the case where $p\nmid q$ and $p\nmid
a_{i}$ for any $i$, we have that $qa_{i}^{*}$ is invertible modulo $p$ for all
$i$; in particular, each equation in the system produces exactly one solution.
If, in addition, we have that $p>\max_{i}\\{h_{i}\\}$, then we have that
$\nu(p)=k+1$. To see this, let
$m_{i}:=-(qa_{i}^{*})^{-1}(b_{i}^{*}+na_{i}^{*})\ (\text{mod}\ p)$ for all $i$
and note that $m_{i}=m_{j}$ iff $a_{i}^{*}b_{j}^{*}=a_{j}^{*}b_{i}^{*}\
(\text{mod}\ p)$. Then, using the fact that
$a_{i}^{*}=\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})/a_{i}$, together with
the fact that both $\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})$ and $a_{i}$
are invertible $\ (\text{mod}\ p)$, we have that $m_{i}=m_{j}$ iff
$a_{i}b_{i}^{*}=a_{j}b_{j}^{*}\ (\text{mod}\ p)$. Then, recalling our
definition of the $b_{i}^{*}$’s, we have that $m_{i}=m_{j}$ iff
$p|(h_{i}-h_{j}).$ Since $1\leq|h_{i}-h_{j}|\leq\max_{i}\\{h_{i}\\}$, it
follows that the $m_{i}$’s are distinct for $p>\max_{i}\\{h_{i}\\}$, which
implies that $\nu(p)=k+1$ for such $p$. In other words, the $a_{i}$’s are
relatively prime on the primes $p>\max_{i}\\{h_{i}\\}$ and this makes it so
that there are exactly $k+1$ solutions to our system of linear congruences,
provided $p$ is large enough. For the smaller primes, we content ourselves
with the fact that $\nu(p)\leq p$.

  3. (3)

$p\nmid q,p|a_{i}$ (for at least one $i$): As mentioned above, the $a_{i}$’s
are pairwise relatively prime on the primes $p>\max_{i}\\{h_{i}\\}$; that is,
if $p|a_{i}$ for at least one $i$ and if $p>\max_{i}\\{h_{i}\\}$, then
$p|a_{i}$ for exactly one $i$, say $a_{i_{0}}$. Moreover, this implies that
$p\nmid a_{i_{0}}^{*}$ and that $p|a_{i}^{*}$ for all $i\neq i_{0}$, which
again follows from the fact that the $a_{i}$’s are pairwise relatively prime
on the primes $>\max_{i}\\{h_{i}\\}$. In particular, there is exactly one
solution for the $i_{0}$-th equation (as $a_{i_{0}}^{*}$ is invertible modulo
${p}$) and there are either no solutions for the other equations or $p$
solutions, depending on whether or not $p|b_{i}^{*}$ for some $i\neq i_{0}$.
To summarize the case where $p\nmid q,p|a_{i_{0}}$, we have precisely one of
the following: (for $p>\max_{i}\\{h_{i}\\}$) either $\nu(p)=1$ or $\nu(p)=p$
and these situations occur if $p\nmid b_{i}^{*}$ for all $i\neq i_{0}$ or
$p|b_{i}^{*}$ for some $i\neq i_{0}$, respectively.

There are a few key points to notice from the above analysis. First, note that
$\nu(p)$ is independent of $n$: this is clear if $p>\max_{i}\\{h_{i}\\}$ or if
$p|q$, but even in the case where $p\leq\max_{i}\\{h_{i}\\}$ and $p\nmid q$,
we either have that $p|a_{i}^{*}$ for some $i$ (so that we either have no
solutions or $p$ solutions for the $i$-th equation) or $p\nmid a_{i}^{*}$ for
some $i$ (in which case, two solutions $m_{i},m_{j}$ are equal iff
$a_{i}^{*}b_{j}^{*}=a_{j}^{*}b_{i}^{*}$, so that $\nu(p)$ is still independent
of $n$). Next, we can simply restrict the sum over the $a_{i}$’s so that
$\nu(p)=\nu(p;a_{0},\dots,a_{k})\neq p$ for any $p$; in the case where
$\nu(p)=p$, the sum over the $b_{i}$’s is $0$, as all $s$ are such that
$(qa_{i}^{*})s\equiv-(b_{i}^{*}+na_{i}^{*})\ (\text{mod}\ p)$, for some $i$
(which implies that there is no $m$ such that
$\left(\prod_{i=0}^{k}(b_{i}^{*}+na_{i}^{*}+mqa_{i}^{*}),\prod_{p\leq
r}p\right)=1$), and there is nothing to prove.

After verifying that $\nu(p)$ satisfies Axioms A.1 and A.2, the FLST (Lemma
A.1) then yields the following:

$\displaystyle\\#\left\\{m\leq\frac{x}{q\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}:\left(\prod_{i=0}^{k}(b_{i}^{*}+na_{i}^{*}+mqa_{i}^{*}),\prod_{p\leq
r}p\right)=1\right\\}$
$\displaystyle\quad\quad\quad\quad\quad\quad=(1+\mathcal{O}_{k}(u^{-u/2}))\frac{x}{q\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}\prod_{\begin{subarray}{c}{p\leq
r}\\\ {p\nmid
q}\end{subarray}}\left(1-\frac{\nu(p)}{p}\right)+\mathcal{O}\left(\sum_{\begin{subarray}{c}{d\leq
r^{u}}\\\ {d|\prod_{p\leq r}p}\end{subarray}}\nu(d)\right),$

uniformly for $u\geq 1$.

Plugging the above back into Equation 4.1, we are left to bound

$\displaystyle\sideset{}{{}^{*}}{\sum}_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\lambda(a_{0})\lambda(a_{1})\cdots\lambda(a_{k})\sum_{n=0}^{q-1}\chi(b_{0}^{*}+na_{0}^{*})\chi(b_{1}^{*}+na_{1}^{*})\cdots\chi(b_{k}+na_{k}^{*})$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\times(1+\mathcal{O}_{k}(u^{-u/2}))\frac{x}{q\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}\prod_{\begin{subarray}{c}{p\leq
r}\\\ {p\nmid
q}\end{subarray}}\left(1-\frac{\nu(p)}{p}\right)+\mathcal{O}\left(\sum_{\begin{subarray}{c}{d\leq
r^{u}}\\\ {d|\prod_{p\leq r}p}\end{subarray}}\nu(d)\right),$

which we break into three parts, according to the three summands in the last
factor.

###  4.1. Bounding the error term containing the sum over $d\leq r^{u}$.

Our goal in this subsection is to choose $u$ (the level of distribution) as
large as possible, while minimizing the “error” term containing the sum over
$d\leq r^{u}$. To begin, recall that $\nu(p)\leq\min\\{k+1,p\\}$; in
particular, $\nu(d)\leq(k+1)^{\omega(d)}$ for all $d|\prod_{p\leq r},$ where
$\omega(d)$ counts the number of prime divisors of $d$. If we let
$\tau_{\kappa}$ denote the $\kappa$-th divisor function (which counts the
number of representations an integer has as a product of $\kappa$ integers),
it is clear that $(k+1)\leq\tau_{k+1}(p)$ for all $p$, so that
$(k+1)^{\omega(d)}\leq\tau_{k+1}(d)$. Hence,

$\displaystyle\sum_{\begin{subarray}{c}{d\leq r^{u}}\\\ {d|\prod_{p\leq
r}p}\end{subarray}}\nu(d)$ $\displaystyle\leq\sum_{d\leq
r^{u}}\tau_{k+1}(d)\ll_{k}r^{u}(u\log r)^{k+1},$

which follows from the average order of $\tau_{\kappa}$; see Exercise 3.10 in
[Kou20]. The total contribution to Equation (4.1) is then bounded by

$\displaystyle\ll_{k}qr^{(k+1)A_{x}}\cdot r^{u}(u\log r)^{k+1}\ll x^{1/2},$

as $x\rightarrow\infty$, provided
$A_{x}\leq((\log\log\eta)^{1/2}(\log\eta)^{1/12})/(10(k+1))$ and
$u\leq((\log\log\eta)^{1/2}(\log\eta)^{1/12})/10$, say, recalling that
$r=x^{1/((\log\log\eta)^{1/2}(\log\eta)^{1/12})}$ with $q^{10}\leq x$.

###  4.2. Bounding the error from the “main term” in the FLST

For the main term, we use Lemma B.1, with
$f(x)=(b_{0}^{*}+a_{0}^{*}x)(b_{1}^{*}+a_{1}^{*}x)\cdots(b_{k}+a_{k}^{*}x)$,
to bound the character sum:

$\displaystyle\sum_{n=0}^{q-1}\chi(b_{0}^{*}+na_{0}^{*})\chi(b_{1}^{*}+na_{1}^{*})\cdots\chi(b_{k}^{*}+na_{k}^{*})\ll_{k}q^{1/2+\epsilon};$

the key is to note that $f$ is not a square modulo $p$ for any prime
$p>\max_{i}\\{h_{i}\\}$, which follows from the fact that
$a_{j}^{*}b_{i}^{*}=a_{i}^{*}b_{j}^{*}$ iff $p|(h_{i}-h_{j})$. Hence,

$\displaystyle\frac{x}{q}\sideset{}{{}^{*}}{\sum}_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{\lambda(a_{0})\lambda(a_{1})\cdots\lambda(a_{k})}{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}\prod_{\begin{subarray}{c}{p\leq
r}\\\ {p\nmid
q}\end{subarray}}\left(1-\frac{\nu(p)}{p}\right)\sum_{n=0}^{q-1}\chi(b_{0}^{*}+na_{0}^{*})\chi(b_{1}^{*}+na_{1}^{*})\cdots\chi(b_{k}+na_{k}^{*})$
$\displaystyle\ll_{k}\frac{x}{q^{1/2-\epsilon}}\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow\leq r}\\\
{(a_{i},a_{j})|i-j}\end{subarray}}\frac{1}{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p\nmid a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p|a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right),$

where we have removed the contribution from the small prime factors (which is
$\ll_{k}1$), where we have bounded the sum over the $a_{i}$’s trivially, and
where we have split the product over the primes according to the value of
$\nu(p)$.

######  Remark 4.1.

Here is a more detailed approach to showing that $f$ is not a square modulo
$p$ for all but finitely-many $p$: we need to consider two cases, depending on
whether or not $p|a_{i}$, for some $i$. So, suppose $p>\max_{i}\\{h_{i}\\}$
and that $p\nmid a_{i}$ for any $i$; then $p\nmid a_{i}^{*}$ for any $i$, so
that $a_{i}^{*}$ is invertible modulo $p$ for all $i$ and that $f$ can only be
a square if $b_{i}^{*}(a_{i}^{*})^{-1}\equiv b_{j}^{*}(a_{j}^{*})^{-1}\
(\text{mod}\ p)$ for at least some $i\neq j$, but this occurs, as we say
before, iff $p|(h_{i}-h_{j})$ which cannot occur for $p>\max_{i}\\{h_{i}\\}$.
In the case where $p|a_{i}$ for some $i$, then $p|a_{i}$ for exactly one $i$
(otherwise, by the condition that $(a_{i},a_{j})|(h_{i}-h_{j})$, we would get
a contradiction); in particular, $p|a_{j}^{*}$ for all $j\neq i$, so that
$f(x)\equiv c(b_{i}^{*}+a_{i}^{*}x)\ (\text{mod}\ p),$ for some
$c\in\operatorname{\mathbb{Z}}/p\operatorname{\mathbb{Z}}$ and where $p\nmid
a_{i}^{*}$ and $f$ is clearly not a square.

Next, using the fact that

$\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})\geq\prod_{i<j}(a_{i},a_{j})^{-1}a_{0}a_{1}\cdots
a_{k},$

together with the fact that $(a_{i},a_{j})|(h_{i}-h_{j})$, we can bound our
sum by

$\displaystyle\ll_{k}\frac{x}{q^{1/2-\epsilon}}\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{1}{a_{0}a_{1}\cdots
a_{k}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq r}\\\ {p\nmid q}\\\
{p\nmid a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p|a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right).$

Again recalling that the $a_{i}$’s are pairwise relatively prime on the primes
$p>\max_{i}\\{h_{i}\\}$, we can actually separate the variables in our sum, so
that

$\displaystyle\frac{1}{a_{0}a_{1}\cdots
a_{k}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq r}\\\ {p\nmid q}\\\
{p\nmid a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p|a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right)$
$\displaystyle\quad\quad\quad\quad\quad\quad=\prod_{i=0}^{k}\frac{1}{a_{i}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p\nmid
a_{i}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p|a_{i}}\end{subarray}}\left(1-\frac{1}{p}\right).$

To deal with the products over the primes, we can multiply and divide by
“complements” of the given divisibility conditions, the idea being that we
want to “complete” our products to keep only divisibility conditions (as
opposed to saying $p\nmid q$, for example):

$\displaystyle\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq r}\\\
{p\nmid q}\\\ {p\nmid
a_{i}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p|a_{i}}\end{subarray}}\left(1-\frac{1}{p}\right)$
$\displaystyle=\prod_{{\max_{i}\\{h_{i}\\}<p\leq
r}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\
{p|q}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\
{p|a_{i}}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|q}\\\ {p|a_{i}}\end{subarray}}\left(1-\frac{k+1}{p}\right)$
$\displaystyle\quad\quad\quad\quad\quad\quad\times\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\
{p|a_{i}}\end{subarray}}\left(1-\frac{1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|q}\\\ {p|a_{i}}\end{subarray}}\left(1-\frac{1}{p}\right)^{-1}$
$\displaystyle\leq\prod_{{\max_{i}\\{h_{i}\\}<p\leq
r}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\
{p|q}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|a_{i}}\end{subarray}}\left(\frac{p-1}{p-(k+1)}\right),$

where we have combined the factors for $p|a_{i}$ and where we have trivially
bounded the product of the factors over $p|q,a_{i}$ by $\leq 1$.

Putting all of this together, we have that

$\displaystyle\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{1}{a_{0}a_{1}\cdots
a_{k}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq r}\\\ {p\nmid q}\\\
{p\nmid a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p|a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right)$
$\displaystyle\ll\prod_{{\max_{i}\\{h_{i}\\}<p\leq
r}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\
{p|q}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}\left(\sum_{\begin{subarray}{c}{a\leq
r^{A_{x}}}\\\ {p|a\Rightarrow p\leq
r}\end{subarray}}\frac{1}{a}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|a}\end{subarray}}\left(\frac{p-1}{p-(k+1)}\right)\right)^{k+1}.$

Finally, we can bound the sum over $a$ by an Euler product, as the
corresponding summand is a multiplicative function supported over the
$r$-smooth integers:

$\displaystyle\sum_{\begin{subarray}{c}{a\leq r^{A_{x}}}\\\ {p|a\Rightarrow
p\leq
r}\end{subarray}}\frac{1}{a}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|a}\end{subarray}}\left(\frac{p-1}{p-(k+1)}\right)$
$\displaystyle\leq\prod_{p\leq
k+1}\left(1-\frac{1}{p}\right)^{-1}\prod_{\max_{i}\\{h_{i}\\}<p\leq
r}\left(1+\frac{p-1}{p-(k+1)}\left(\frac{1}{p}+\frac{1}{p^{2}}+\dots\right)\right)$
$\displaystyle\ll_{k}\prod_{\max_{i}\\{h_{i}\\}<p\leq
r}\left(1+\frac{1}{p-(k+1)}\right).$

Therefore, the total contribution from the “main term” in the FLST is bounded
above by

$\displaystyle\ll_{k}\frac{x}{q^{1/2-\epsilon}}\prod_{{\max_{i}\\{h_{i}\\}<p\leq
r}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\
{p|q}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}\prod_{\max_{i}\\{h_{i}\\}<p\leq
r}\left(1+\frac{1}{p-(k+1)}\right)^{k+1}$
$\displaystyle\ll_{k}\frac{x}{q^{1/2-\epsilon}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|q}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1},$

where the last line follows from the fact that

$\displaystyle\prod_{{\max_{i}\\{h_{i}\\}<p\leq
r}}\left(1-\frac{k+1}{p}\right)\left(1+\frac{1}{p-(k+1)}\right)^{k+1}$
$\displaystyle=\prod_{\max_{i}\\{h_{i}\\}<p\leq
r}\left(1+\mathcal{O}\left(\frac{1}{p^{2}}\right)\right)=\mathcal{O}(1),$

which in turn follows from the Binomial Theorem. Hence, the main term is
bounded above by

$\displaystyle\frac{x}{q^{1/2-\epsilon}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|q}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}$
$\displaystyle\ll_{k}\frac{x\log^{k+1}q}{q^{1/2-\epsilon}},$

where the first line follows by taking exp-log of the product and using the
Taylor series expansion of $\log$ and which produces an admissible error,
after recalling that $x\leq q^{(\log\log\eta)/3}$.

###  4.3. Dealing with the error from $u^{-u/2}$.

For the error containing the term $u^{-u/2}$, we have that Equation (4.1) is
bounded above by

$\displaystyle\ll_{k}u^{-u/2}\frac{x}{q}\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{1}{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}\sum_{n=0}^{q-1}|\chi(b_{0}^{*}+na_{0}^{*})\chi(b_{1}^{*}+na_{1}^{*})\cdots\chi(b_{k}^{*}+na_{k}^{*})|\prod_{\begin{subarray}{c}{p\leq
r}\\\ {p\nmid q}\end{subarray}}\left(1-\frac{\nu(p)}{p}\right)$
$\displaystyle=u^{-u/2}\frac{x}{q}\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{1}{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}\prod_{\begin{subarray}{c}{p\leq
r}\\\ {p\nmid
q}\end{subarray}}\left(1-\frac{\nu(p)}{p}\right)\sum_{\begin{subarray}{c}{n=0}\\\
{\left(\prod_{i=0}^{k}(b_{i}^{*}+na_{i}^{*}\right),q)=1}\end{subarray}}^{q-1}1.$

To estimate the sum over $n$, we use the fact that

$\sum_{d|n}\mu(n)=\left\\{\begin{array}[]{@{}l@{\quad}l@{}}\text{$1$ if
$n=1$}\\\ \text{$0$ otherwise},\end{array}\right.$

which yields:

$\displaystyle\sum_{\begin{subarray}{c}{n=0}\\\
{\left(\prod_{i=0}^{k}(b_{i}^{*}+na_{i}^{*}\right),q)=1}\end{subarray}}^{q-1}1$
$\displaystyle=\sum_{\begin{subarray}{c}{n=0}\end{subarray}}^{q-1}\sum_{d|\left(\prod_{i}(b_{i}^{*}+na_{i}^{*}),q\right)}\mu(d)$
$\displaystyle=\sum_{d|q}\sum_{\begin{subarray}{c}{n=0}\\\
{d|\prod_{i}(b_{i}^{*}+na_{i}^{*})}\end{subarray}}^{q-1}\mu(d)$
$\displaystyle=q\sum_{d|q}\frac{N(d)}{d},$

where $N(d)$ is the number of
$n\in\operatorname{\mathbb{Z}}/d\operatorname{\mathbb{Z}}$ such that
$\prod_{i=0}^{k+1}(b_{i}^{*}+na_{i}^{*})\equiv 0\ (\text{mod}\ d),$ $d|q$. By
the CRT, $N(d)$ is multiplicative, so that the sum can be written as

$\displaystyle q\sum_{d|q}\frac{\mu(d)N(d)}{d}$
$\displaystyle=q\prod_{p|q}\left(1-\frac{N(p)}{p}\right)$

and it remains to compute $N(p)$; we consider various cases, depending on
whether or not $a_{i}^{*}$ is invertible $\ (\text{mod}\ p)$, noting that
$N(p)$ is equal to the number of $n\ (\text{mod}\ p)$ such that
$na_{i}^{*}\equiv-b_{i}^{*}\ (\text{mod}\ p)$, for any $i$.

  1. (1)

$p\nmid a_{0}a_{1}\cdots a_{k}$: In this case, all the $a_{i}^{*}$ are
invertible modulo $p$ so that exactly one $n$ satisfies the given congruence
in the $i$-th equation. Assuming further that $p>\max_{i}\\{h_{i}\\}$, we get
$k+1$ distinct solutions as
$(a_{i}^{*})^{-1}b_{i}^{*}=(a_{j}^{*})^{-1}b_{j}^{*}\ (\text{mod}\ p)$ iff
$p|(h_{i}-h_{j})$; that is, $N(p)=k+1$ if $p>\max_{i}\\{h_{i}\\}$, with $1\leq
N(p)\leq p$ otherwise.

  2. (2)

$p|a_{0}a_{1}\cdots a_{k}:$ Similarly, $N(p)=1$ if $p>\max_{i}\\{h_{i}\\}$
with $N(p)\leq p$ otherwise. The idea here is that the $a_{i}$’s are pairwise
relatively prime on the primes $p>\max_{i}\\{h_{i}\\}$ so that exactly one
$a_{i}$ is divisible by $p$ if $p|a_{0}\cdots a_{k}$, say $a_{i_{0}}$; in
particular, we get exactly one solution at level $i_{0}$ and the other
congruences are solvable iff $b_{i}^{*}\equiv 0\ (\text{mod}\ p)$ for some
$i$. In the latter case, we have that $N(p)=p$ and the product is $0$, so we
may assume that $p\nmid b_{i}^{*}$ for all $i$.

Thus, the second error term is bounded above by

$\displaystyle\ll_{k}u^{-u/2}x\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{1}{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}$
$\displaystyle\quad\quad\quad\times\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p\nmid a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p\nmid q}\\\ {p|a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p}\\\
{p|q}\\\ {p\nmid a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p}\\\
{p|q}\\\ {p|a_{0}a_{1}\cdots a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right)$
$\displaystyle\ll_{k}u^{-u/2}x\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{1}{a_{0}a_{1}\cdots
a_{k}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq r}\\\ {p\nmid
a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|a_{0}a_{1}\cdots a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right)$
$\displaystyle\ll_{k}u^{-u/2}x\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\end{subarray}}\left(1-\frac{k+1}{p}\right)\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{1}{a_{0}a_{1}\cdots
a_{k}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq r}\\\
{p|a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|a_{0}a_{1}\cdots a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right).$

Again using the fact that the $a_{i}$’s are pairwise relatively on the primes
$p>\max_{i}\\{h_{i}\\}$, we can separate the variables in the sum over the
$a_{i}$’s:

$\displaystyle\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\frac{1}{a_{0}a_{1}\cdots
a_{k}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq r}\\\
{p|a_{0}a_{1}\cdots
a_{k}}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|a_{0}a_{1}\cdots a_{k}}\end{subarray}}\left(1-\frac{1}{p}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}{a_{0},a_{1},\dots,a_{k}\leq
r^{A_{x}}}\\\ {p|a_{i}\Rightarrow p\leq r}\\\
{(a_{i},a_{j})|(h_{i}-h_{j})}\end{subarray}}\left(\prod_{i=0}^{k}\frac{1}{a_{i}}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\
{p|a_{i}}\end{subarray}}\left(1-\frac{k+1}{p}\right)^{-1}\left(1-\frac{1}{p}\right)\right)$
$\displaystyle\leq\left(\sum_{\begin{subarray}{c}{a\leq r^{A_{x}}}\\\
{p|a\Rightarrow p\leq
r}\end{subarray}}\frac{1}{a}\prod_{\begin{subarray}{c}{\max_{i}\\{h_{i}\\}<p\leq
r}\\\ {p|a}\end{subarray}}\left(\frac{p-1}{p-(k+1)}\right)\right)^{k+1}$
$\displaystyle\leq\left(\prod_{p\leq\max_{i}\\{h_{i}\\}}\left(1-\frac{1}{p}\right)^{-1}\prod_{\max_{i}\\{h_{i}\\}<p\leq
r}\left(1+\frac{p-1}{p-(k+1)}\left(\frac{1}{p}+\frac{1}{p^{2}}+\dots\right)\right)\right)^{k+1}.$

Therefore, the total contribution from the secondary error term is

$\displaystyle\ll_{k}u^{-u/2}x\prod_{\max_{i}\\{h_{i}\\}<p\leq
r}\left(1-\frac{k+1}{p}\right)\left(1+\frac{1}{p-(k+1)}\right)^{k+1}$
$\displaystyle\ll_{k}u^{-u/2}x,$

noting that this is the same product over the primes that we encountered
earlier and which we saw was $\ll_{k}1$. Taking
$u\asymp(\log\log\eta)^{1/2}(\log\eta)^{1/12}$ produces an admissible error
and thus establishes Theorem 1.2.

###  4.4. Fitting the pieces.

In this section, we want to say a few words which justify our choice of
parameters for $r,A_{x},$ and $u$. Setting $r=x^{1/\alpha}$, we need to choose
the largest possible $A_{x}$ and $u$ for which the following errors are
minimized, while optimizing $\alpha$:

$\displaystyle\left\\{\begin{array}[]{@{}l@{\quad}l@{}}\frac{x}{\log
r}\left(\exp\left(\frac{\log x}{\log q}\right)(\log
q)(\log\eta)^{-1/2})+\log\log q\right)+\frac{x}{r}\quad\mbox{(error from the
proof of Lemma \ref{lambda_r})},\\\ \frac{x}{A_{x}}\quad\mbox{(error from
Lemma \ref{Pre-Sieve})},\\\ qr^{(k+1)A_{x}+u}(u\log r)^{k+1}\quad\mbox{(error
from Section \ref{Error-1})},\\\
\frac{x\log^{k+1}q}{q^{1/2-\epsilon}}\quad\mbox{(error from Section
\ref{Error-2})},\\\ xu^{-u/2}\quad\mbox{(error from Section
\ref{Error-3})}.\end{array}\right.$

For the error from Section 4.1, we can get power savings by taking
$(k+1)A_{x}=u=C\alpha$, for $C>0$ sufficiently small. The error from Lemmas
3.3 and 4.1, after normalizing by $x$, are of the form
$\alpha/((\log\log\eta)(\log\eta)^{1/6})$ and $1/\alpha$, respectively, which
yields the optimal choice of $\alpha:=(\log\log\eta)^{1/2}(\log\eta)^{1/12},$
thus establishing Theorem 1.2.

##  5\. Acknowledgements

The author would like to thank Maksym Radziwiłł for suggesting this problem
and for his continuous support throughout the research phase of this paper.
The author would also like to thank Dimitris Koukoulopoulos, Mariusz
Lemańczyk, Patrick Meisner, James Rickards, and Peter Zenz for many helpful
discussions and comments. Finally, some of this work was conducted while the
author was visiting CalTech; he is grateful for their hospitality.

## References

  * [AKPLdlR17] Houcein El Abdalaoui, Joanna Kułaga-Przymus, Mariusz Lemańczyk, and Thierry de la Rue.  The Chowla and the Sarnak conjectures from ergodic theory point of view.  Discrete and Continuous Dynamical Systems, 37:2899–2944, 2017.
  * [Bur63] David A. Burgess.  On character sums and $L$-series, II.  Proceedings of the London Mathematical Society, s3-13(1):524–536, 1963.
  * [Cho65] Sarvadaman Chowla.  The Riemann Hypothesis and Hilbert’s Tenth Problem, volume 4 of Mathematics and its Applications.  Gordon and Breach Science Publishers, New York-London-Paris, 1965.
  * [FKPL18] Sébastien Ferenczi, Joanna Kułaga-Przymus, and Mariusz Lemańczyk.  Sarnak’s Conjecture – what’s new. In: Ferenczi, S., Kułaga-Przymus, J., Lemańczyk, M. (eds) Ergodic Theory and Dynamical Systems in their Interactions with Arithmetics and Combinatorics - Lecture Notes in Mathematics, vol 2213.  Springer International Publishing, 2018.
  * [GK10] László Germán and Imre Kátai.  Multiplicative functions at consecutive integers.  Lithuanian Mathematical Journal, 50(1):43–53, 2010.
  * [GKL18] Alexander Gomilko, Dominik Kwietniak, and Mariusz Lemańczyk.  Sarnak’s Conjecture Implies the Chowla Conjecture Along a Subsequence. In: Ferenczi S., Kułaga-Przymus J., Lemańczyk M. (eds) Ergodic Theory and Dynamical Systems in their Interactions with Arithmetics and Combinatorics - Lecture Notes in Mathematics, vol 2213.  Springer, Cham, 2018.
  * [GLdlR20] Alexander Gomilko, Mariusz Lemańczyk, and Thierry de la Rue.  Möbius orthogonality in density for zero entropy dynamical systems.  Pure and Applied Functional Analysis, 5:1357–1376, 2020.
  * [Gra20] Andrew Granville.  Sieving intervals and siegel zeros.  Preprint, arXiv: math/2010.01211, 2020.
  * [HB83] David Rodney Heath-Brown.  Prime twins and Siegel zeros.  Proc. Lond. Math., 47(3):193–224, 1983.
  * [Hil86] Adolf Hildebrand.  Multiplicative functions at consecutive integers.  Math. Proc. Cambridge Philos. Soc., 100(2):229–236, 1986.
  * [HPW85] Glyn Harman, Jànos Pintz, and Dieter Wolke.  A note on the Möbius and Liouville functions.  Stud. Sci. Math. Hung., 20:295–299, 1985.
  * [HR21] Harald A. Helfgott and Maksym Radziwiłł.  Expansion, divisibility, and parity.  Preprint, arXiv: math/2103.06853, 2021.
  * [IK04] Henryk Iwaniec and Emmanuel Kowalski.  Analytic number theory, volume 53 of American Mathematical Society Colloquium Publications.  American Mathematical Society, Providence, RI, 2004.
  * [Kou20] Dimitris Koukoulopoulos.  The Distribution of Prime Numbers.  Graduate Studies in Mathematics 203. American Mathematical Society, 2020\.
  * [KPL20] Joanna Kułaga-Przymus and Mariusz Lemańczyk.  Sarnak’s conjectures from the ergodic theory point of view.  To appear in Encyclopedia of Complexity and Systems Science, arXiv: math/2009.04757, 2020.
  * [MR16] Kaisa Matomäki and Maksym Radziwiłł.  Multiplicative functions in short intervals.  Annals of Mathematics, 183(3):1015–1056, 2016.
  * [MRT15] Kaisa Matomäki, Maksym Radziwiłł, and Terence Tao.  An averaged form of Chowla’s conjecture.  Algebra and Number Theory, 9(9):2167–2196, 2015.
  * [MV07] Hugh L. Montgomery and Robert C. Vaughan.  Multiplicative Number Theory I: Classical Theory.  Cambridge studies in advanced mathematics. Cambrigde University Press, 1st edition, 2007.
  * [Sch76] Wolfgang M. Schmidt.  Equations over Finite Fields An Elementary Approach.  Lecture Notes in Mathematics. Springer-Berlin-Heidelberg, 1st edition, 1976.
  * [SS18] Will Sawin and Mark Shusterman.  On the Chowla and twin primes conjectures over $\mathbb{F}_{q}[t]$.  Preprint, arXiv:math/1808.04001, 2018.
  * [Tao16] Terence Tao.  The logarithmically averaged Chowla and Elliott conjectures for two-point correlations.  Forum of Mathematics, Pi, 4(8):1–36, 2016.  doi:10.1017/fmp.2016.6.
  * [TT18] Terence Tao and Joni Teräväinen.  Odd order cases of the logarithmically averaged Chowla conjecture.  Journal de Théorie de Nombres de Bordeaux, 30(3):997–1015, 2018\.
  * [TT19] Terence Tao and Joni Teräväinen.  The structure of logarithmically averaged correlations of multiplicative functions, with applications to the Chowla and Elliott conjectures.  Duke Math J., 168(11):1977–2027, 2019.  doi:10.1215/00127094-2019-0002.

Department of Mathematics and Statistics, McGill University, 805 Sherbrooke
St. W., Montreal, QC H3A 2K6, Canada

Email address: mailto:iakov.chinis<EMAIL_ADDRESS>
##  Appendix A The Fundamental Lemma of Sieve Theory

In this section, we present the Axioms of Sieve Theory, culminating in the
Fundamental Lemma of Sieve Theory (FLST). We use the ideas presented here in
order to move from a character sum over $r$-sifted integers to a character sum
over one complete residue class (see Section 4). We follow Chapters 18 and 19
of [Kou20] and start off by listing some notation and the appropriate
hypotheses needed for the FLST.

Let $\mathcal{A}$ denote a finite set of integers and let $\mathcal{P}$ denote
a finite set of primes. We are interested in counting the number of elements
of $\mathcal{A}$ which are relatively prime to $\mathcal{P}$; that is, we are
interested in bounding the quantity

$S(\mathcal{A},\mathcal{P}):=\\#\\{a\in\mathcal{A}:(a,\mathcal{P})=1\\},$

where $(a,\mathcal{P})=1$ means that $a$ has no prime factors in
$\mathcal{P}$. In order to do so, it suffices to look at elements of
$a\in\mathcal{A}$ which are divisible by $d|\prod_{p\in\mathcal{P}}p$; see
Examples 18.1-18.6 in [Kou20]. More precisely, we are interested in having an
asymptotic estimate for

$\mathcal{A}_{d}:=\\#\\{a\in\mathcal{A}:a\equiv 0\ (\text{mod}\ d)\\},$

so we assume the following:

######  Axiom A.1.

There exists a multiplicative function $\nu$, a parameter $X$, and a sequence
of remainders $(r_{d})_{d|\mathcal{P}}$ such that

$\mathcal{A}_{d}=\frac{\nu(d)}{d}X+r_{d}$ for all $d|\mathcal{P}$

and

$\nu(p)<p$ for all $p\in\mathcal{P}$.

######  Remark A.1.

Note that $d|\mathcal{P}$ is shorthand for $d|\prod_{p\in\mathcal{P}}p$.

We should think of $\nu(p)$ as the number of residue classes modulo $p$ we are
“removing” in order to capture elements of our set $\mathcal{A}$ which are
prime to $\mathcal{P}$. As such, we want some sort of control over $\nu(p)$:

######  Axiom A.2.

There are constants $\kappa,k\geq 0$ and $\epsilon\in(0,1]$ such that

$\sum_{p\in\mathcal{P}\cap[1,\omega]}\frac{\nu(p)\log
p}{p}=\kappa\log\omega+\mathcal{O}(1)$ for all $\omega\leq\max\mathcal{P}$

and

$\nu(p)\leq\min\\{k,(1-\epsilon)p\\}$ for all $p\in\mathcal{P}$.

Assuming that Axioms A.1 and A.2 hold, we are able to compute
$S(\mathcal{A},\mathcal{P})$:

######  Lemma A.1 (The Fundamental Lemma of Sieve Theory).

Suppose $\mathcal{A}$ and $\mathcal{P}$ satisfy Axioms A.1 and A.2 for some
constants $\kappa,k\geq 0$, $\epsilon\in(0,1]$, and let $y=\max\mathcal{P}$.
Then:

$S(\mathcal{A},\mathcal{P})=(1+\mathcal{O}_{\kappa,k,\epsilon}(u^{-u/2}))X\prod_{p\in\mathcal{P}}\left(1-\frac{\nu(p)}{p}\right)+\mathcal{O}\left(\sum_{d\leq
y^{u},d|\mathcal{P}}|r_{d}|\right),$

uniformly for $u\geq 1$.

###### Proof.

See [Kou20, Chapters 18-19]. ∎

######  Remark A.2.

We call $D=y^{u}$ the level of distribution of the sieve. As Koukoulopoulos
remarks in his book, the level of distribution is “a measure of how well we
can control the distribution of $\mathcal{A}$ among the progressions $0\
(\text{mod}\ d)$,” with $d|\mathcal{P}$. In order to control the level of
distribution, we often use a “preliminary sieve,” which removes integers with
smaller prime factors and then use another sieve to remove larger primes. This
is exactly what we do in the proof of Theorem 1.2 by sieving out the integers
whose $r$-smooth part is “large.”

##  Appendix B Character Sums

The key to the work of Germán and Kátai is to approximate the Liouville
function by a real, primitive Dirichlet character $\chi\ (\text{mod}\ q)$ on
“large” primes, so that, with the help of some sieve theory, we can change our
problem of bounding $k$-point correlations of $\lambda$ to one of bounding
character sums with a polynomial argument, which are well understood. For our
purposes, we need to bound character sums of the form

$\sum_{n\ (\text{mod}\ q)}\chi(f(n)),$

where $f$ is some polynomial with integer coefficients which can be factored
into distinct linear factors, with $q$ equal to the conductor/modulus of the
real, primitive character $\chi$. There are various instances of these types
of bounds when the conductor $q$ is a prime, dating back to the work of Weil
on the Riemann Hypothesis over finite function fields; see, [Bur63], for
example, and also [Sch76] for an elementary approach to understanding curves
over finite fields. In [GK10], they look at $f(x)=x(x+1),$ it which case it is
known that the above character sum is exactly equal to $-1$. For general $f$,
we have the following, due to Weil:

######  Lemma B.1 (Weil).

Let $\chi$ be a Dirichlet character modulo $p$ of order $d|(p-1)$. If
$f\in\operatorname{\mathbb{Z}}[x]$ is not a $d$-th power modulo $p$ (i.e.,
$f(x)\not\equiv cg(x)^{d}\ (\text{mod}\ p)$ identically for any
$c\in\operatorname{\mathbb{Z}}$ and any $g\in\operatorname{\mathbb{Z}}[x]$)
and if $f$ has $m$ distinct roots modulo $p$, then:

$\left|\sum_{n\ (\text{mod}\ p)}\chi(f(n))\right|\leq(m-1)p^{1/2},$

where the sum runs over an entire residue class modulo the prime $p$.

###### Proof.

See [Sch76, Theorem 2C’ (pg. 43)] (or even [IK04, Theorem 11.23]/[MV07, Lemma
9.25]). ∎

Our goal is to apply Lemma B.1 with $\chi$ a real, primitive Dirichlet
character modulo $q$, with $q$ not necessarily a prime. Fortunately for us,
all such characters have conductor $q=2^{j}m$, where $j\leq 3$ and where $m$
is an odd, squarefree integer; see [MV07, Section 9.3], for example.
Furthermore, the Chinese Remainder Theorem allows us to write each $n\
(\text{mod}\ q)$ uniquely as

$n=a_{1}\frac{q}{p_{1}^{\alpha_{1}}}+\dots+a_{s}\frac{q}{p_{s}^{\alpha_{s}}},$

for any $q=p_{1}^{\alpha_{1}}\cdots p_{s}^{\alpha_{s}}$, with $a_{i}$ varying
over a complete residue class modulo $p_{i}^{\alpha_{i}}$. In particular, for
characters $\chi$ modulo $q$ such that $\chi=\chi_{1}\cdots\chi_{s}$ with
$\chi_{i}$ a character modulo $p_{i}^{\alpha_{i}}$,

$\displaystyle\sum_{n\ (\text{mod}\ q)}\chi(f(n))$
$\displaystyle=\sum_{a_{1},\dots,a_{s}}\prod_{i=1}^{s}\chi_{i}\left(f\left(a_{1}\frac{q}{p_{1}^{\alpha_{1}}}+\dots+a_{s}\frac{q}{p_{s}^{\alpha_{s}}}\right)\right)$
$\displaystyle=\prod_{i=1}^{s}\sum_{a_{i}\ (\text{mod}\
p_{i}^{\alpha_{i}})}\chi_{i}\left(f\left(a_{i}\frac{q}{p_{i}^{\alpha_{i}}}\right)\right),$

where the last line follows from the fact that $\chi_{i}$ is periodic with
period $p_{i}^{\alpha_{i}}$. Then, using the fact that every real, primitive
character $\chi\ (\text{mod}\ q)$ can be written uniquely as
$\chi=\chi_{1}\cdots\chi_{s}$ with each $\chi_{i}$ being real and primitive,
Lemma B.1 implies that

$\displaystyle\sum_{n\ (\text{mod}\ q)}\chi(f(n))$
$\displaystyle\ll(\deg(f)-1)^{s}q^{1/2},$

provided $f$ is not a square modulo $p$ for all but finitely many primes $p$.
Setting $N=\deg(f)-1$ and noting that $\omega(q)=s$, we then have that
$N^{\omega(q)}\leq\tau_{N}(q)\ll q^{\epsilon}$, for any $\epsilon>0$, so that

$\displaystyle\sum_{n\ (\text{mod}\ q)}\chi(f(n))$ $\displaystyle\ll
q^{1/2+\epsilon},$

for any real, primitive Dirichlet character modulo $q$, provided $f$ is not a
square modulo $p$ for all but finitely-many $p$.

##  Appendix C Parametrization

In this section, we briefly discuss how to use the Smith Normal Form of a
matrix in order to solve a system of Diophantine equations. Our ultimate goal
is to apply this technique in order to show that the solutions of the
following system of integer equations

$\displaystyle\left\\{\begin{array}[]{@{}l@{\quad}l@{}}a_{1}b_{1}=a_{0}b_{0}+h_{1},\\\
\vdots\\\ a_{k}b_{k}=a_{0}b_{0}+h_{k},\end{array}\right.$

in the unknowns $b_{0},b_{1},\dots,b_{k}$, are given by

$b_{i}=b_{i}^{*}+m\frac{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}{a_{i}}=:b_{i}^{*}+ma_{i}^{*},$

where $(b_{0}*,b_{1}^{*},\dots,b_{k}^{*})$ is one particular solution of the
system and where $m$ ranges over all the integers.

######  Remark C.1.

In the case where $k=1$ and $(a_{0},a_{1})=1$, Bezout’s Lemma tells us that
the $b_{i}$’s can be parametrized as

$b_{i}=b_{i}^{*}+m\frac{a_{1}a_{2}}{a_{i}},$

where $(b_{0}^{*},b_{1}^{*})$ is one particular solution of the system and
where $m$ ranges over all integers. The proof of Bezout’s Lemma follows from
the Chinese Remainder Theorem; it is very likely that the proof generalizes,
but we prefer to use a more direct method. Also, it is clear that such
$b_{i}$’s generate a set of solutions and seems likely that one could show
that all solutions must be of the form above. In any case, the SNF gives us a
versatile tool to handle more general cases.

Let $A$ be an $m\times n$ matrix with integer entries and consider the system
$AX=C$, for a given integer matrix $C$. Then, there exist invertible matrices
$U$ and $V$ with integer entries such that $B:=UAV$ is (almost) diagonal: in
general, $B$ may not be a square matrix, but the non-diagonal entries will be
zero. We call $B$ the Smith Normal Form of $A$ and finding the matrices $U$
and $V$ amounts to using limited versions of the elementary row and column
operations which preserve integer entries: since we are looking for invertible
matrices $U$ and $V$ with integer entries, we must ensure that whatever
operations we apply to the matrix $A$ will preserve our integer entries. What
is important here is that solving $AX=C$ in the integers is equivalent to
making the change of variable $Y=V^{-1}X$ and solving the system $BY=D$, where
$D:=UC$. In particular, the original system will have integer solutions iff
$b_{ii}y_{i}=d_{i}$ for all $i$ (where $D$ is a column matrix and $d_{i}$ is
the entry in row $i$). This last system is then solvable over the integers iff
$b_{ii}|d_{i}$ whenever $b_{ii}\neq 0$ and $d_{i}=0$ whenever $b_{ii}=0$, in
which case,

$X=V\begin{bmatrix}\frac{b_{11}}{d_{1}}\\\ \frac{b_{22}}{d_{2}}\\\ \vdots\\\
\frac{b_{kk}}{d_{k}}\\\ f_{k+1}\\\ \vdots\\\ f_{n}\end{bmatrix},$

where the $b_{ii}$’s are arranged so that $b_{ii}\neq 0$ for all $i=1,\dots,k$
and where $f_{k+1},\dots,f_{n}$ are arbitrary integers (representing the $n-k$
free variables).

The above decomposition hinges on our ability to find invertible matrices $U$
and $V$ such that $UAV$ is diagonal. We illustrate how to do this for the
following system of equations in the unknowns $b_{0},b_{1},\dots,b_{k}$,

$\displaystyle\left\\{\begin{array}[]{@{}l@{\quad}l@{}}a_{1}b_{1}=a_{0}b_{0}+h_{1},\\\
\vdots\\\ a_{k}b_{k}=a_{0}b_{0}+h_{k},\end{array}\right.$

proving each solution $(b_{0},b_{1},\dots,b_{k})$ can be parametrized as

$b_{i}=b_{i}^{*}+ma_{i}^{*},$

where $(b_{0}^{*},b_{1}^{*},\dots,b_{k}^{*})$ is one particular solution of
the system (assuming that the system is solvable) and where

$a_{i}^{*}:=\frac{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}{a_{i}},$

for $i=0,1,\dots,k$.

To show the above, we simply use the algorithm which produces the SNF of $A$.
So, let

$A:=\begin{bmatrix}a_{0}&-a_{1}&0&\dots&0&0\\\ 0&a_{1}&-a_{2}&\dots&0&0\\\
\vdots&&&&&\\\ 0&0&0&\dots&a_{k-1}&-a_{k}\end{bmatrix},$
$X:=\begin{bmatrix}b_{0}\\\ b_{1}\\\ \vdots\\\ b_{k},\end{bmatrix}$

and

$C:=\begin{bmatrix}-h_{1}\\\ h_{1}-h_{2}\\\ \vdots\\\
h_{k-1}-h_{k}\end{bmatrix}.$

Our goal it to solve the system $AX=C$ over the integers. To begin, let
$d_{0,1}:=(a_{0},a_{1})$. Then, there exist integers $x_{0,1},y_{0,1}$ such
that $d_{0,1}=a_{0}x+a_{1}y$; in particular,
$1=x_{0,1}a_{0}/d_{0,1}+y_{0,1}a_{1}/d_{0,1}$. Embedding this information into
a $(k+2)\times(k+2)$ identity matrix $V_{1}$, we can get the following:

$\displaystyle AV_{1}$
$\displaystyle=\begin{bmatrix}a_{0}&-a_{1}&0&\dots&0&0\\\
0&a_{1}&-a_{2}&\dots&0&0\\\ \vdots&&&&&\\\
0&0&0&\dots&a_{k-1}&-a_{k}\end{bmatrix}\begin{bmatrix}x_{0,1}&a_{1}/d_{0,1}&0&\dots&0\\\
-y_{0,1}&a_{0}/d_{0,1}&0&\dots&0\\\ 0&0&1&\dots&0\\\ \vdots&&&&\\\
0&0&0&\dots&1\end{bmatrix}$
$\displaystyle=\begin{bmatrix}d_{0,1}&0&0&\dots&0&0\\\
-a_{1}y&a_{0}a_{1}/d_{0,1}&-a_{2}&\dots&0&0\\\ \vdots&&&&&\\\
0&0&0&\dots&a_{k-1}&-a_{k}\end{bmatrix}.$

To get zeros below the leading variable, consider the $(k+1)\times(k+1)$
matrix $U_{1}$ defined by

$U_{1}:=\begin{bmatrix}1&0&0&\dots&0\\\ a_{1}y&d_{0,1}&0&\dots&0\\\
0&0&1&\dots&0\\\ \vdots&&&&\\\ 0&0&0&\dots&1\end{bmatrix}$

and note that

$U_{1}AV_{1}=\begin{bmatrix}d_{0,1}&0&0&\dots&0&0\\\
0&a_{0}a_{1}&-d_{0,1}a_{2}&\dots&0&0\\\ \vdots&&&&&\\\
0&0&0&\dots&a_{k-1}&-a_{k}\end{bmatrix}.$

We continue in the same manner: let
$d_{01,2}=(a_{0}a_{1},d_{0,1}a_{2})=d_{0,1}(a_{0}a_{1}/d_{0,1},a_{2})$, then
there exist integers $x_{01,2},y_{01,2}$ such that
$d_{01,2}=a_{0}a_{1}x_{01,2}+d_{0,1}a_{2}y_{01,2}$. Embedding this information
in another $(k+2)\times(k+2)$ identity matrix $V_{2}$, we have that

$\displaystyle U_{1}AV_{1}V_{2}$
$\displaystyle=\begin{bmatrix}d_{0,1}&0&0&\dots&0&0\\\
0&a_{0}a_{1}&-d_{0,1}a_{2}&\dots&0&0\\\ 0&0&a_{2}&\dots&0&0\\\ \vdots&&&&&\\\
0&0&0&\dots&a_{k-1}&-a_{k}\end{bmatrix}\begin{bmatrix}1&0&0&\dots&0\\\
0&x_{01,2}&a_{2}d_{0,1}/d_{01,2}&\dots&0\\\
0&-y_{01,2}&a_{0}a_{1}/d_{01,2}&\dots&0\\\ \vdots&&&&\\\
0&0&0&\dots&1\end{bmatrix}$
$\displaystyle=\begin{bmatrix}d_{0,1}&0&0&0&\dots&0&0\\\
0&d_{01,2}&0&0&\dots&0&0\\\
0&-a_{2}y_{01,2}&a_{0}a_{1}a_{2}/d_{01,2}&-a_{3}&\dots&0&0\\\ \vdots&&&&&&\\\
0&0&0&0&\dots&a_{k-1}&-a_{k}\end{bmatrix}$

To get zeros below the leading variable, consider the $(k+1)\times(k+1)$
matrix $U_{2}$ defined by

$U_{2}:=\begin{bmatrix}1&0&0&0&\dots&0\\\ 0&1&0&0&\dots&0\\\
0&-a_{2}y_{01,2}&d_{01,2}&0&\dots&0\\\ \vdots&&&&&\\\
0&0&0&0&\dots&1\end{bmatrix}$

and note that

$U_{2}U_{1}AV_{1}V_{2}=\begin{bmatrix}d_{0,1}&0&0&0&\dots&0&0\\\
0&d_{01,2}&0&0&\dots&0&0\\\ 0&0&a_{0}a_{1}a_{2}&-a_{3}d_{01,2}&\dots&0&0\\\
\vdots&&&&&&\\\ 0&0&0&0&\dots&a_{k-1}&-a_{k}\end{bmatrix}$

Continuing by induction, we see that the Smith Normal Form of the matrix $A$
has diagonal entries $d_{01\cdots j,j+1}$, for $j=0,1,\dots,k-1$, which are
defined recursively by

$d_{01\cdots j,j+1}:=\gcd(a_{0}a_{1}\cdots a_{j},a_{j+1}d_{01\cdots j-1,j})$

with

$d_{0,1}:=\gcd(a_{0},a_{1}).$

What is important to note here is that the SNF of $A$ has the maximal rank; in
particular, if the SNF satisfies some nice divisibility properties in relation
to the matrix $D=UC$, we get infinitely-many solutions which are parametrized
by exactly one free variable (because we have full rank, but the matrix $A$
has dimensions $k\times(k+1)$). Furthermore, the solutions will then be given
by

$X=V\begin{bmatrix}\frac{b_{11}}{d_{1}}\\\ \frac{b_{22}}{d_{2}}\\\ \vdots\\\
\frac{b_{kk}}{d_{k}}\\\ f_{k+1}\\\ \end{bmatrix}$

and all that is left for us to do is to compute the last column of the matrix
$V$. A quick calculation shows that the last column of $V$ has entry

$\frac{a_{0}a_{1}\cdots a_{i-1}a_{i+1}\cdots a_{k}}{d_{01\cdots k-1,k}}$

in row $i$, for $i=0,1,\dots,k$ and that this is equal to

$\frac{\operatorname{lcm}(a_{0},a_{1},\dots,a_{k})}{a_{i}},$

as claimed.