Cubic sieves, a primitive-ratio cut and a $20/37$ bound for the $abc$ exceptional set

Abstract.

We prove $N_{1}(X)\ll_{\varepsilon}X^{20/37+\varepsilon}$, where $N_{\lambda}(X)$ counts the $abc$ triples of exponent $\lambda$ in $[1,X]^{3}$. The previous full bound was $X^{13/20+\varepsilon}$. We use the anatomic reduction of Bernert, Browning, Lichtman and Teräväinen. Five families add new rows. The first two are an archimedean cover and a row from Heath-Brown’s uniform bound for diagonal cubic curves. Spacing gives $30$ two-arm clauses. Cubic characters and a fourth moment of Dirichlet $L$-functions give the cubic-sieve rows. Cochrane and Shi’s fourth moment gives the moment rows. An exact Farkas certificate with $394\,633$ leaves gives exponent $20/37$ for the box count. On each leaf the multipliers of all rows except nonnegativity sum to at most $586/201$. Exact rows are included in this sum. This pays for the losses at $\lambda=1$.

1. Introduction

For this paper $\mathbb{N}=\{1,2,\ldots\}$. For $n\neq 0$ put $\operatorname{rad}(n)=\prod_{p\mid n}p$, and write $\omega(n)=\#\{p:p\mid n\}$, with $\omega(1)=0$. Following [2], call $(a,b,c)\in\mathbb{N}^{3}$ with $\gcd(a,b,c)=1$ an $abc$ triple of exponent $\lambda$ if

(1.1) $$a+b=c,\qquad\operatorname{rad}(abc)<c^{\lambda}.$$

Let $N_{\lambda}(X)$ count these triples in $[1,X]^{3}$. The $abc$ conjecture of Masser and Oesterlé implies that $N_{\lambda}(X)=O_{\lambda}(1)$ for $\lambda<1$, so $\lambda=1$ is the endpoint of interest.

The bound $N_{\lambda}(X)\ll_{\varepsilon}X^{2\lambda/3+\varepsilon}$ is classical [2, Proposition 1.1]; it comes from de Bruijn’s count [5] of integers with restricted radical. For $\lambda\geq 2$, Kane’s result [10] gives $N_{\lambda}(X)\ll_{\varepsilon}X^{\lambda-1+\varepsilon}$ [2, Section 1]. On $2\leq\lambda\leq 3$ it matches $N_{\lambda}(X)\gg X^{\lambda-1-\varepsilon}$. Granville’s unpublished work gives the lower bound for $1<\lambda\leq 3$, as reported in [2, Section 1]. The question is Mazur’s. It can hold only for $\lambda\leq 3$, since $N_{\lambda}(X)\leq\#\{(a,b,c)\in[1,X]^{3}:a+b=c\}=O(X^{2})$. Browning, Lichtman and Teräväinen [3, Theorem 1.2] gave the first power saving below $2\lambda/3$, for $0.99<\lambda<1.001$. Bernert [1, Theorem 1] proved

(1.2) $$N_{\lambda}(X)\ll_{\varepsilon}X^{(23\lambda+3)/40+\varepsilon}\qquad(0<\lambda<2),$$

so $N_{1}(X)\ll_{\varepsilon}X^{13/20+\varepsilon}$. In the merged paper, [2, Theorem 1.2] states (1.2) for $0<\lambda\leq 2$. Its Theorem 1.3 gives $0.6$ for $0<\lambda<1$, with a constant depending on $\lambda$. At $\lambda=1$: a remark at the end of [1, Section 4] sketches $8/13=0.6153\ldots$; Li [11] obtains $56/85=0.6588\ldots$ from the method of [3], its limit without further optimisation by his account.

Theorem 1.

$N_{1}(X)\ll_{\varepsilon}X^{20/37+\varepsilon}$, where $20/37=0.5405\ldots$

Since $N_{\mu}\leq N_{1}$ for $\mu\leq 1$, Theorem 1 also improves [2, Theorem 1.3] on $0<\mu<1$, with a constant independent of $\mu$. Among the estimates cited here, the resulting exponent is $\min\{2\mu/3,20/37\}$ for $0<\mu\leq 1$. Thus the new exponent is best known for $30/37<\mu\leq 1$; it ties the classical exponent at $\mu=30/37$. Its crossing with the Bernert exponent alone is $\mu=689/851$.

Section 2 recalls the anatomic reduction of [3, 1, 2]. Fix $\varepsilon_{0}>0$ and $d=d(\varepsilon_{0})$. Every triple lies in a box. In a box, each side is a fixed coefficient times $\prod_{i\leq d}\mathfrak{s}_{i}^{\,i}$. The roots $\mathfrak{s}_{i}$ have fixed dyadic sizes. The three side values are pairwise coprime. Let $\mathcal{B}_{d}$ count the root-factorization tuples in a box, with distinct factorizations counted separately, and put $D=\log_{X}\mathcal{B}_{d}$. The proof is the chain. Section 2 works at a generic scale $X$ and exponent $\lambda$; Lemma 12.2 applies it at the scale $Y$ of (2.1), with $\lambda:=\mu$ and base-$Y$ logarithms. The quantity $V_{s}$ is the weighted exponent of the root product, excluding its fixed coefficient, as defined in Section 6; $h_{d}=d(d+1)/2$. The quantity $\rho$ is the largest finite right-hand-side shift in Lemma 12.2. The bound on $\rho$ holds for $Y\geq Y_{0}(\varepsilon_{0},d)$. Smaller $Y$ contribute $O_{\varepsilon_{0},d}(1)$, and $\mu\leq 0$ contributes nothing (Section 13).

$$\begin{gathered}N_{1}(X)\ll(\log X)^{2}\max_{Y\leq X,\ \mu\leq 1}N^{*}_{\mu}(Y),\qquad N^{*}_{\mu}(Y)\ll Y^{\varepsilon_{0}}\max\mathcal{B}_{d},\\ D\leq\frac{20}{37}+\Lambda_{U}\rho,\qquad\Lambda_{U}=\frac{586}{201},\qquad\rho\leq 19\varepsilon_{0},\end{gathered}$$

from (2.1), (2.3), Theorem 2 with Lemma 12.1, and Lemma 12.2. Since $19\Lambda_{U}+1=\frac{11335}{201}$, choosing $\varepsilon_{0}$ with $\frac{11335}{201}\,\varepsilon_{0}<\varepsilon/2$ proves Theorem 1.

The inequalities for $D$ are linear in $28$ exponents. They are the root and tail coordinates of the three sides, $D$, and three auxiliary Fourier variables. BBLT’s Theorem 1.3 gives the $3/5$ bound. Its Proposition 6.1 lists the $22$ inherited inequalities used here. We add the tail rows and the cut. Tail roots (Section 3) of index at least seven cost $X^{\tau_{s}}$ to enumerate. Here $\tau_{s}=s-\sum_{i\leq 6}s_{i}$. The tail product is at least $X^{v_{s}}$, where $v_{s}\geq 7\tau_{s}$. The cut (Section 5) fixes all but two coprime products $u,v$ on two sides:

$$\gcd(u,v)=1,\qquad u\equiv\xi v\pmod{M},\qquad 0<u\leq U_{\rm cut},\quad 0<v\leq V_{\rm cut}.$$

Here $M$ is built from roots on the third side, and $\xi$ lies in one of $X^{o(1)}$ classes. Lemma 4.1 counts these by $1+2U_{\rm cut}V_{\rm cut}/M$. There are

(1.3) $$3\,(64^{2}-1)\,127=1\,560\,195$$

cuts.

The paper adds five further families.

• Archimedean (Section 6). One of the side values $n_{a},n_{b}$ is at least $n_{c}/2$. In the limiting coordinates, $V_{a},V_{b}\leq V_{c}$, and $V_{c}\leq V_{a}$ or $V_{c}\leq V_{b}$. At finite scale, $V_{a},V_{b}\leq V_{c}+\varepsilon_{0}/2$, and one of $V_{c}\leq V_{a}+3\varepsilon_{0}/2+\log_{Y}2^{1+h_{d}}$ or $V_{c}\leq V_{b}+3\varepsilon_{0}/2+\log_{Y}2^{1+h_{d}}$ holds.

• Cubic (Section 7). Fix all roots but the three cube roots. Heath-Brown’s bound [8, Theorem 1.3] for primitive points on $\alpha x^{3}+\beta y^{3}=\gamma z^{3}$, uniform in the coefficients, gives $D\leq L-p_{3}$. Here $L$ and $p_{i}$ are as in Section 2.

• Spacing (Section 8). Consecutive $\ell$th powers are far apart: $30$ two-arm clauses.

• Cubic sieve (Section 9). Write one side as $Mx^{3}$. Sieve with cubic characters modulo primes $p\equiv 1\pmod{3}$. The error term needs a smooth fourth moment of character sums. It comes from the fourth moment of Dirichlet $L$-functions in [6, Lemma 4]: $1774$ clauses.

• Moments (Section 10). Expand the congruence of the cut modulo $M$ by characters. The fourth moment of Cochrane and Shi [4, Theorem 1] bounds the nonprincipal part: $188\,976$ clauses.

Section 11 proves $D\leq 20/37$ from these rows. The certificate is a finite trie. Each internal node splits on one clause, one child per arm. Each leaf carries nonnegative rational Farkas multipliers. There are $394\,633$ leaves, depth $49$, and no infeasible leaf. On a leaf the multipliers of all rows except nonnegativity sum to at most $\Lambda_{U}=586/201$, whence the term $\Lambda_{U}\rho$. This includes exact rows. A point of the installed system attains $20/37$; the qualification on this optimum appears in Section 11.2.

Section 12 treats $\mu=1$. In the proof of Theorem 1, the dyadic reduction only requires $0<\mu\leq 1$. At this endpoint the row $L\leq 1$ of [2] is unavailable: the proof of [2, Theorem 1.3] uses $\varepsilon_{0}\leq(1-\mu)/3$. We use $L\leq 1+3\varepsilon_{0}/4$ instead. The $L$-native Fourier and geometry rows cost $18\varepsilon_{0}$ and $6\varepsilon_{0}$. After the choice of $Y_{0}$ in Lemma 12.2, every new row costs at most $2\varepsilon_{0}$. Hence $\rho=18\varepsilon_{0}+o_{\varepsilon_{0},d}(1)$ and $\Lambda_{U}\rho=\frac{3516}{67}\,\varepsilon_{0}+o_{\varepsilon_{0},d}(1)$.

The proof in [2] does not use the determinant method; [3] used it together with Thue equations. Lemma 4.1 is an elementary lattice-point count of the kind used in [2, Proposition 4.1]. The cut applies it to two sides at once, with modulus $M$ built from roots on the third side.

Imported statements are cited where used. Citations of [2] refer to arXiv:2410.12234v2 (to appear in C. R. Math.); each imported statement was checked against it. The dyadic reduction (2.1) is only stated in [2, Section 2]; Section 2 proves it. Appendix A reproves the estimates of [2, Propositions 2.3, 3.1 and 4.1] for our boxes. They use the divisor bound, the count of solutions of $x^{j}-y^{j}=m$ (Lemma A.1) and the lattice-point bound [7, Lemma 3] (Theorem C). The new rows use the cubic bound [8, Theorem 1.3] and the fourth moments [6, Lemma 4] and [4, Theorem 1]. The cubic-sieve character expansion (Section 9) also uses the classical Jacobi-sum bound [9]. No conjecture is assumed. Theorem 2 has multiplier bound $\Lambda_{U}$. It is computer-assisted and uses a certificate checked by the standard-library programs in Appendix C. The analytic reductions and row families are proved in the text.

2. The anatomic reduction

Throughout this section $0<\lambda\leq 2$, $\varepsilon>0$ is arbitrary, $\varepsilon_{0}>0$ is fixed before $X$, and $d=d(\varepsilon_{0})$. We take $\varepsilon_{0}\leq 4/7$, so that the folded index $k=\lceil 4/\varepsilon_{0}\rceil$ of [2, Lemma 2.2] is at least $7$ (Section 3.1). Implied constants depend only on $\varepsilon,\varepsilon_{0},d$; $\lambda$ occurs only through the displayed $\ll_{\lambda}$ in (2.1). They never depend on the box, the coefficients or $X$.

Write $N^{*}_{\lambda}(X)$ for the number of triples counted by $N_{\lambda}(X)$ that satisfy in addition $c\geq X/2$ and $\operatorname{rad}(abc)\geq c^{\lambda}/2$. A dyadic decomposition and the pigeonhole principle give

(2.1) $$N_{\lambda}(X)\ll_{\lambda}(\log X)^{2}\max_{1\leq Y\leq X}\ \max_{\mu\leq\lambda}N^{*}_{\mu}(Y),$$

as in [2, Section 2]. In the application $\lambda=1$, and the bounds below for $N^{*}_{\mu}(Y)$ are uniform in $0<\mu\leq 1$ (Lemma 12.2).

Proof of (2.1).

Let $(a,b,c)$ be counted by $N_{\lambda}(X)$. Then $c\geq 2$ and $a,b<c\leq X$. Choose $l\geq 1$ with $c\in(X2^{-l},X2^{1-l}]$ and put $Y=X2^{1-l}\leq X$. Thus $Y/2<c\leq Y$. Put

$$\mu_{i}=\lambda-i/\log_{2}X\qquad(0\leq i\leq\lceil\lambda\log_{2}X\rceil).$$

Here $\log_{2}X=(\log X)/(\log 2)$. There are $O(\log X)$ such exponents, all at most $\lambda$, and the last is at most $0$. With $r=\operatorname{rad}(abc)$, we have $r<c^{\mu_{0}}$ and $r\geq 1\geq c^{\mu_{m}}$ for the last index $m$. Choose the largest $i$ with $r<c^{\mu_{i}}$. Then $r\geq c^{\mu_{i+1}}\geq c^{\mu_{i}}/2$, since $c\leq X$. Hence the triple is counted by $N^{*}_{\mu_{i}}(Y)$. There are $O(\log X)$ choices of $Y$ and $O(\log X)$ choices of $\mu_{i}$, which proves the claim. ∎

For $\mu\leq 0$, $N^{*}_{\mu}(Y)=0$: its defining condition would require $1\leq\operatorname{rad}(abc)<c^{\mu}\leq 1$. Thus the maximum in (2.1) may be restricted to $0<\mu\leq\lambda$.

For $n\geq 1$ write $[n]=\{1,\ldots,n\}$. Here $x\sim A$ means $A\leq x<2A$, as in [1]; [2] writes $x\sim A$ for $x\in(A,2A]$.

Let $d\in\mathbb{N}$ and $(a_{0},b_{0},c_{0})\in\mathbb{N}^{3}$. Let $\mathbf{A},\mathbf{B},\mathbf{C}\in\mathbb{N}^{d}$ have entries powers of two, $1$ included. Put $\mathfrak{a}_{0}=a_{0}$, $\mathfrak{b}_{0}=b_{0}$, $\mathfrak{c}_{0}=c_{0}$ and

(2.2) $$\mathcal{B}_{d}=\#\Bigl{\{}(\mathfrak{a}_{i},\mathfrak{b}_{i},\mathfrak{c}_{i})_{i=1}^{d}\in\mathbb{N}^{3d}:\begin{aligned} &\mathfrak{a}_{i}\sim A_{i},\ \mathfrak{b}_{i}\sim B_{i},\ \mathfrak{c}_{i}\sim C_{i}\quad(1\leq i\leq d),\\ &a_{0}\textstyle\prod_{i\leq d}\mathfrak{a}_{i}^{\,i}+b_{0}\prod_{i\leq d}\mathfrak{b}_{i}^{\,i}=c_{0}\prod_{i\leq d}\mathfrak{c}_{i}^{\,i},\\ &\gcd\bigl{(}\textstyle\prod_{i=0}^{d}\mathfrak{a}_{i},\prod_{i=0}^{d}\mathfrak{b}_{i},\prod_{i=0}^{d}\mathfrak{c}_{i}\bigr{)}=1\end{aligned}\Bigr{\}}.$$

For a side write $S_{j}\in\{A_{j},B_{j},C_{j}\}$ for its dyadic root size. When the side $s$ must be named, write $S_{s,j}$. Recall $h_{d}=d(d+1)/2$. Equation (2.2) counts root-factorization tuples, not distinct side-value triples; different factorizations are counted separately. It is the $B_{d}$ of [2], under our dyadic convention, with no condition within a side. We write $\mathcal{B}_{d}$ to avoid a clash with the size $B_{d}$.

Every interval $[A,2A)\cap\mathbb{N}$ has exactly $A$ integers, including $[1,2)\cap\mathbb{N}=\{1\}$. We keep every root coordinate, including those equal to $1$. The statements of [2, Propositions 2.3, 3.1 and 4.1] assume windows $(A,2A]$ with $A\geq 1$, which exclude roots equal to $1$. So we do not cite them for our boxes. We rerun the window-dependent steps of the reduction below. Appendix A proves the pair, Fourier and geometry bounds in our convention (Lemmas A.2, A.3 and A.4). Their constants depend only on $\varepsilon_{0}$ and $d$.

Roots equal to $1$ occur: in [2, Lemma 2.2], $m_{j}=\prod_{p^{j}\|n}p$ and $n_{j}=m_{j}$ for $j\neq k$, the folded index. So $n_{j}=1$ unless some prime has multiplicity exactly $j$. As $n$ has at most $\omega(n)$ distinct multiplicities, all but at most $\omega(n)$ indices $j\leq d$, $j\neq k$, give $n_{j}=1$. Our convention assigns these roots the size $A_{i}=1$ and keeps all $d$ indices in (2.2). By the proof of [2, Proposition 2.1], each $\varepsilon_{0}>0$ has a $d=d(\varepsilon_{0})$ with

(2.3) $$N^{*}_{\lambda}(X)\ll_{\varepsilon_{0}}X^{\varepsilon_{0}}\max\mathcal{B}_{d},$$

the maximum over pairwise coprime $1\leq a_{0},b_{0},c_{0}\leq X^{\varepsilon_{0}}$ and dyadic $A_{i},B_{i},C_{i}\in[1,X]$ with

(2.4) $$\begin{gathered}2^{-O_{d}(1)}X^{\lambda}\leq\prod_{j\leq d}A_{j}B_{j}C_{j}\leq X^{\lambda+3\varepsilon_{0}/4},\\ \prod_{j\leq d}A_{j}^{\,j}\leq X,\qquad\prod_{j\leq d}B_{j}^{\,j}\leq X,\qquad X^{1-\varepsilon_{0}/2}\leq\prod_{j\leq d}C_{j}^{\,j}\leq X,\end{gathered}$$

The power of two depends only on $d$. We rederive the lower bounds below. The upper bounds and the pigeonhole step of the source proof hold verbatim under $[A,2A)$, since $A_{i}\leq\mathfrak{a}_{i}<2A_{i}$. The lower bound uses the nontrivial branch of [2, Lemma 2.2]: $\varepsilon_{0}<4$, so the parameter $\varepsilon_{0}/4<1$ and $k=\lceil 4/\varepsilon_{0}\rceil\leq d$. Since $c\geq X/2$,

$$\prod_{j\leq d}A_{j}B_{j}C_{j}\geq 2^{-3d}\operatorname{rad}(abc)\geq 2^{-3d-\lambda-1}X^{\lambda}\geq 2^{-3d-3}X^{\lambda},$$

since $\lambda\leq 2$. Each of the $3d$ roots loses at most a factor $2$; the source proof prints $2^{-d}$ here. The weighted lower bound for the $c$-roots is

$$\prod_{j\leq d}C_{j}^{j}\geq 2^{-h_{d}}\prod_{j\leq d}\mathfrak{c}_{j}^{j}.$$

The factorization uses parameter $\varepsilon_{0}/4$, so $c_{0}\leq X^{\varepsilon_{0}/4}$ and $\prod_{j\leq d}\mathfrak{c}_{j}^{\,j}=c/c_{0}\geq 2^{-1}X^{1-\varepsilon_{0}/4}$. Since $C_{j}\geq\mathfrak{c}_{j}/2$,

$$\prod_{j\leq d}C_{j}^{j}\geq 2^{-h_{d}-1}X^{1-\varepsilon_{0}/4}\geq X^{1-\varepsilon_{0}/2}\quad\text{if }X\geq Y_{\rm red}:=2^{4(h_{d}+1)/\varepsilon_{0}}.$$

This gives the lower bound in (2.4). The global threshold $Y_{0}(\varepsilon_{0},d)\geq Y_{\rm red}$ is fixed in Lemma 12.2. This suffices, since $d$ is fixed before $X$. Fix such a box. For a side $s\in\{a,b,c\}$ set

(2.5) $$s_{i}=\log_{X}S_{i}\ (1\leq i\leq d),\qquad s=\log_{X}\!\prod_{i\leq d}S_{i}=\sum_{i\leq d}\log_{X}S_{i}.$$

Index $0$ is not a coordinate: $a_{0},b_{0},c_{0}$ are the integer coefficients. From here on $a,b,c$ denote coordinates, not the triple. Boxes with $\mathcal{B}_{d}=0$ do not attain the maximum in (2.3) unless $N^{*}_{\lambda}(X)=0$. So $\mathcal{B}_{d}\geq 1$, and we set

$$D=\log_{X}\mathcal{B}_{d}\geq 0.$$

For the tail put

(2.6) $$\tau_{s}=s-\sum_{i\leq 6}s_{i}=\sum_{7\leq j\leq d}\log_{X}S_{j},\qquad v_{s}=\sum_{7\leq j\leq d}j\log_{X}S_{j}.$$

Put $L=a+b+c$ and $p_{i}=a_{i}+b_{i}+c_{i}$; a bare $p$ is a prime. Moving a dyadic endpoint at scale $X$ changes the root coordinates by

(2.7) $$\Delta s_{i},\ \Delta s=O_{d}\!\left(\frac{1}{\log X}\right).$$

The left inequality of (2.4) uses $\prod_{j\leq d}n_{j}\geq\operatorname{rad}(n)$ with no loss, while in this direction [2, Lemma 2.2] gives only $\operatorname{rad}(n)\leq n^{\varepsilon_{0}}\prod_{j}n_{j}$. In the proof of that lemma $m_{j}=\prod_{p^{j}\|n}p$, and, for the folded index $k$, $n_{j}=m_{j}$ for $j\neq k$ and $n_{k}=m_{k}\prod_{j>d}m_{j}^{\lfloor j/k\rfloor}$. Since $d\geq k$, $\lfloor j/k\rfloor\geq 1$ for $j>d$, so

$$\prod_{j\leq d}n_{j}\ \geq\ \prod_{j\leq d}m_{j}\prod_{j>d}m_{j}\ =\ \operatorname{rad}(n).$$

Lemma 2.1.

The three side values of a box are pairwise coprime. Hence every factor of one side is a unit modulo every factor of another side.

Proof.

A prime dividing two side values divides the third by the equation in (2.2). If it divides $a_{0}\prod_{i=1}^{d}\mathfrak{a}_{i}^{\,i}$, it divides $\prod_{i=0}^{d}\mathfrak{a}_{i}$; likewise on the other sides. This contradicts the gcd condition in (2.2). ∎

The index $i=0$ in this gcd condition is needed. With $d=1$, the choice

$$a_{0}=b_{0}=1,\quad\mathfrak{a}_{1}=\mathfrak{b}_{1}=2,\quad c_{0}=4,\quad\mathfrak{c}_{1}=1$$

satisfies the condition with $i\geq 1$: $\gcd(2,2,1)=1$. Yet its side values $2$, $2$, $4$ share the prime $2$. The full condition excludes it: $\gcd(2,2,4)=2$.

Nothing is assumed within a side. Roots of one side may share primes with $a_{0}$. Unenumerated roots are recovered by a divisor bound, not by squarefreeness.

2.1. The inherited rows

For these limiting rows take $0<\lambda\leq 1$. The finite box bound is $L\leq\lambda+3\varepsilon_{0}/4\leq 1+3\varepsilon_{0}/4$. We use this endpoint envelope throughout, so no choice of $\varepsilon_{0}$ depends on the gap $1-\lambda$. Lemmas A.2 and A.3 and Corollary A.5 are our forms of [2, Propositions 2.3, 3.1 and 4.1]. In the coordinates (2.5) they yield the $22$ inequalities of [2, Proposition 6.1]. We display them in exact limiting form, as Section 11 uses them. At finite resolution each right-hand side rises by the amount in Lemma 12.2 and Table 12.1; (2.9) and (2.10) hold exactly. The reduction has constants depending only on $\varepsilon_{0},d$. So do the bounds of Appendix A. They use $\lambda$ only through $ABC\leq X^{\lambda+3\varepsilon_{0}/4}$ in Corollary A.5. The condition $\varepsilon_{0}\leq(1-\mu)/3$ occurs only in the final step of the proof of [2, Theorem 1.3], where it ensures $ABC\leq X^{\mu+3\varepsilon_{0}}\leq X$.

The radical bound in (2.4) gives [2, (6.1)],

(2.8) $$L\leq 1,$$

derived there for $\lambda<1$. At $\lambda=1$ only $L\leq 1+3\varepsilon_{0}/4$ holds (Lemma 12.2). Roots sum into their side, [2, (6.2)]:

(2.9) $$\sum_{i\leq 6}s_{i}\leq s\qquad(s=a,b,c).$$

The side-value bound in (2.4) gives [2, (6.3)],

(2.10) $$7s-1\leq 6s_{1}+5s_{2}+4s_{3}+3s_{4}+2s_{5}+s_{6}\qquad(s=a,b,c).$$

Two sides determine the third up to a divisor factor (Lemma A.2). This is [2, (6.4)]:

(2.11) $$D\leq\min(a+b,\ a+c,\ b+c).$$

Geometry of numbers (Corollary A.5) gives the thirteen min-disjunctions [2, (6.5)–(6.9)], labelled (G1)–(G13) in Appendix B. The Fourier estimate (Lemma A.3) gives [2, (6.10)],

(2.12) $$\sum_{s=a,b,c}\max(s_{2}+s_{4}+s_{6},\ s_{3}+s_{6},\ s_{5})\leq 4L-6D.$$

One argument per maximum gives $27$ linear rows. Section 11 encodes them with three auxiliary variables.

The Python listing of [2, Appendix A] transcribes the first line of [2, (6.9)] as p1+a2+b3+a3, where the displayed formula reads $p_{1}+a_{2}+b_{3}+c_{3}$. We use the displayed formula. It is what Corollary A.5 gives with the printed second argument $1-a_{2}-2b_{3}-2c_{3}$. For (2.10) we use

(2.13) $$7s-1\leq 7s-\sum_{i\leq d}i\,s_{i}=\sum_{i\leq 6}(7-i)s_{i}+\sum_{7\leq i\leq d}(7-i)s_{i}\leq\sum_{i\leq 6}(7-i)s_{i},$$

since $7-i\leq 0$ for $i\geq 7$. In our system (2.10) is the sum of the two tail rows of Section 3, so it is redundant.

3. The multiplicity-at-least-seven tail

The tail rows we use are

(3.1) $$\tau_{s}\geq 0,\qquad v_{s}\geq 7\tau_{s},\qquad\sum_{i\leq 6}i\,s_{i}+v_{s}\leq 1\qquad(s=a,b,c).$$

The first is (2.9). The second: $\log_{X}S_{j}\geq 0$, with weight $j\geq 7$ in $v_{s}$ and weight $1$ in $\tau_{s}$. The third is the side-value bound in (2.4). Adding the last two,

$$(v_{s}-7\tau_{s})+(1-\sum_{i\leq 6}is_{i}-v_{s})\geq 0,$$

that is, $\sum_{i\leq 6}is_{i}+7\tau_{s}\leq 1$; with $\tau_{s}=s-\sum_{i\leq 6}s_{i}$ this is (2.10). With the upper row $v_{s}\leq d\tau_{s}$, these rows describe the real relaxation of the pairs $(\tau_{s},v_{s})$ exactly. We omit that row, so the system $\mathcal{S}$ of Section 11 is free of $d$.

Lemma 3.1.

Fix a side $s\in\{a,b,c\}$ and let $M_{\mathrm{tail}}=\prod_{7\leq j\leq d}\mathfrak{s}_{j}^{\,j}$ with $\mathfrak{s}_{j}\sim S_{j}$. Then

(3.2) $$\begin{gathered}\#\{(\mathfrak{s}_{7},\dots,\mathfrak{s}_{d})\in\mathbb{N}^{d-6}:\mathfrak{s}_{j}\sim S_{j}\}\leq\prod_{7\leq j\leq d}S_{j}=X^{\tau_{s}},\\ M_{\mathrm{tail}}\geq\prod_{7\leq j\leq d}S_{j}^{\,j}=X^{v_{s}},\end{gathered}$$

and every prime $p$ dividing $M_{\mathrm{tail}}$ does so with $\operatorname{ord}_{p}(M_{\mathrm{tail}})\geq 7$, where $\operatorname{ord}_{p}$ denotes the $p$-adic valuation.

Proof.

Each interval $[S_{j},2S_{j})$ contains exactly $S_{j}$ integers, which gives the count, and $\mathfrak{s}_{j}\geq S_{j}$ gives the modulus bound. If $p\mid\mathfrak{s}_{j}$ with $j\geq 7$ then $\operatorname{ord}_{p}(M_{\mathrm{tail}})\geq j\geq 7$. ∎

The count is exact for $[N,2N)$ and for $(N,2N]$. A closed $[N,2N]$ would overcount by a factor of up to $2^{d-6}$, attained when all $S_{j}=1$.

So the tail costs $X^{\tau_{s}}$ to enumerate. The bound is on roots, not on $\operatorname{rad}(M_{\mathrm{tail}})$, and uses no squarefreeness. Let $\sigma$ and $T$ be the modulus side and index set of Section 5. Then $M_{\mathrm{tail}}$ divides the side value and is at least $X^{v_{\sigma}}$. Hence $T$ may contain the tail.

3.1. Folded roots

For the rest of the proof fix $0<\varepsilon_{0}\leq 4/7$. This is allowed, as $\varepsilon_{0}$ is arbitrarily small at the endpoint step. In [2, Lemma 2.2] the very high multiplicities are folded into one index $k$. The folded root need not be squarefree; the remainder goes into $n_{0}$. The proof of [2, Proposition 2.1] uses that lemma with parameter $\varepsilon_{0}/4$. So

$$k=\lceil 4/\varepsilon_{0}\rceil,\qquad d=6\lceil(4/\varepsilon_{0})^{2}\rceil.$$

Then $k\geq 7$, and $d\geq 6(4/\varepsilon_{0})^{2}>4/\varepsilon_{0}+1>k$. So the folded root lies in the tail, $M_{\mathrm{tail}}$ still divides the side value, and $\operatorname{ord}_{p}(n_{k}^{\,k})=k\operatorname{ord}_{p}(n_{k})\geq 7$ for $p\mid n_{k}$. The overlap of $n_{0}$ and $n_{k}$ is within one side, so Lemma 2.1 is untouched. Unenumerated roots are recovered by Lemma 4.3. The folding costs the factor $X^{3\varepsilon_{0}/4}$ in the upper radical bound of (2.4). It also costs the choice of $a_{0},b_{0},c_{0}$ in the $X^{\varepsilon_{0}}$ of (2.3). Both are already charged. It changes neither Lemma 3.1 nor (3.1).

4. Three lattice and divisor lemmas

Lemma 4.1.

Let $M\geq 1$, let $\xi$ be a unit modulo $M$ and let $U,V\geq 1$. Then

(4.1) $$\#\{(u,v)\in\mathbb{N}^{2}:u\leq U,\ v\leq V,\ \gcd(u,v)=1,\ u\equiv\xi v\ (M)\}\leq 1+\frac{2UV}{M}.$$

Proof.

Put $\mathcal{L}_{\xi}=\{(u,v)\in\mathbb{Z}^{2}:u\equiv\xi v\ (M)\}$, of index $M$ in $\mathbb{Z}^{2}$. Any two of its points have determinant in $M\mathbb{Z}$. Positive collinear integer points with $\gcd(u,v)=1$ coincide. Thus the points of $\mathcal{L}_{\xi}$ with $\gcd(u,v)=1$ in $[1,U]\times[1,V]$ have distinct slopes; order them by slope. Consecutive points span with $0$ a triangle of area $\geq M/2$. These triangles have disjoint interiors and lie in $[0,U]\times[0,V]$. With $P$ points, $(P-1)M/2\leq UV$. ∎

The proof does not use that $\xi$ is a unit. The constant $2$ is sharp. For odd $n\geq 3$ take $U=n$, $V=n+4$, $M=n^{2}+2n-4$, $\xi=n-1$. The primitive points are $(n-1,1)$, $(n,n+4)$, $(1,n+3)$, with consecutive determinants $M$, and $(P-1)M/(UV)\to 2$.

Lemma 4.2.

Let $1\leq q\leq 6$, let $M\geq 1$ and let $K$ be a unit modulo $M$. The congruence $\eta^{q}\equiv K\pmod{M}$ has at most $8^{\omega(M)}$ solutions in units $\eta$, hence $X^{o(1)}$ solutions uniformly for $M\leq X^{O(1)}$.

Proof.

The solution set is empty or a coset of the kernel of $\eta\mapsto\eta^{q}$. Odd prime power: the unit group is cyclic, so the kernel has order at most $q\leq 6$. Modulus $2^{e}$, $e\leq 2$: the unit group has order at most $2$. Modulus $2^{e}$, $e\geq 3$: $(\mathbb{Z}/2^{e}\mathbb{Z})^{\times}\cong C_{2}\times C_{2^{e-2}}$, so the kernel has order $\gcd(q,2)\gcd(q,2^{e-2})\leq 8$; the $2$-part of $q\leq 6$ is at most $4$. Multiply by the Chinese remainder theorem. As $\omega(M)\ll\log M/\log\log M$ for $M\geq 3$,

$$8^{\omega(M)}=\exp\bigl{(}O(\log M/\log\log M)\bigr{)}=X^{O(1/\log\log X)}\qquad(M\leq X^{O(1)}).$$

The form $C^{\omega(M)}\ll_{C,\delta}M^{\delta}$, for fixed $C\geq 1$ and $\delta>0$, alone gives no rate. For $M\leq 2$ there is one class. No bound $B^{\omega(M)}$ with $B<8$ holds. For $q=4$, $e\geq 4$, the group $C_{2}\times C_{2^{e-2}}$ has $\gcd(4,2)\gcd(4,2^{e-2})=8$ fourth roots of unity. And $q=4$ occurs in (5.2). Local kernel size $8$ occurs only for $2^{e}$, $e\geq 4$, $q=4$. So for $\omega(M)\geq 2$ the product of local kernel sizes is at most $8\cdot 6^{\omega(M)-1}<8^{\omega(M)}$. ∎

Lemma 4.3.

Write $\operatorname{div}(N)=\#\{m\in\mathbb{N}:m\mid N\}$ for $N\in\mathbb{N}$. For $r\geq 1$ and positive integers $e_{1},\dots,e_{r}$,

$$\#\{(x_{1},\dots,x_{r})\in\mathbb{N}^{r}:x_{1}^{e_{1}}\cdots x_{r}^{e_{r}}=N\}\leq\operatorname{div}(N)^{r-1}\ll_{r,\delta}N^{\delta}\qquad(\delta>0),$$

uniformly in $e_{1},\dots,e_{r}$. For $N\geq 3$ the maximal-order bound gives the rate

$$\operatorname{div}(N)^{r-1}=\exp\!\bigl{(}O_{r}(\log N/\log\log N)\bigr{)},$$

so for $N\leq X^{O_{d}(1)}$ and $r\leq d$ the count is $X^{O_{d}(1/\log\log X)}$.

Proof.

Each $x_{i}$ divides $N$. The equation determines $x_{r}$ from $x_{1},\dots,x_{r-1}$, for any $e_{i}$. Apply the divisor bound and, for the rate, the maximal order of $\operatorname{div}(N)$. ∎

Thus an unfactored product of roots determines those roots up to $X^{o(1)}$.

5. The cut

Fix a box. Let $(y,z)$ be the other two sides in alphabetical order: $(b,c)$, $(a,c)$, $(a,b)$ for $\sigma=a,b,c$. Write $[6]=\{1,2,3,4,5,6\}$. Choose a nonempty

(5.1) $$\begin{gathered}T\subseteq\{1,2,3,4,5,6,\mathrm{tail}\},\\ \kappa_{T}=\sum_{t\in T\cap[6]}\sigma_{t}+\mathbf{1}_{\mathrm{tail}\in T}\tau_{\sigma},\qquad\Omega_{T}=\sum_{t\in T\cap[6]}t\,\sigma_{t}+\mathbf{1}_{\mathrm{tail}\in T}v_{\sigma}.\end{gathered}$$

Here $\kappa_{T}$ is the selected root mass for this section. The symbols $u,v,M,\xi$ below are local to the cut and are not the corresponding symbols in Sections 9 and 10; $v$ is also distinct from the tail coordinate $v_{\sigma}$. Choose free sets $R_{y},R_{z}\subseteq[6]$, not both empty, and put

(5.2) $$q=\gcd(\gcd R_{y},\gcd R_{z}),\qquad F=\sum_{i\in R_{y}}i\,y_{i}+\sum_{j\in R_{z}}j\,z_{j},$$

with $\gcd\emptyset=0$. For such a choice $(\sigma,T,R_{y},R_{z})$, the quantities in (5.1)–(5.2) are fixed by the box and the index sets. As $R_{y}\cup R_{z}\neq\emptyset$, $1\leq q\leq 6$ and $q$ divides every element of $R_{y}\cup R_{z}$. By the choice of $d$ in Section 3.1, $d=6\lceil(4/\varepsilon_{0})^{2}\rceil\geq 294$, so the tail notation applies. Write $\max\{t,0\}=\max\{t,0\}$.

Proposition 5.1.

Let a box satisfy the constraints after (2.3), with $\mathcal{B}_{d}\geq 1$. Then

(5.3) $$D\leq\Bigl{(}y-\sum_{i\in R_{y}}y_{i}\Bigr{)}+\Bigl{(}z-\sum_{j\in R_{z}}z_{j}\Bigr{)}+\kappa_{T}+\max\{\frac{F}{q}-\Omega_{T},0\}+o_{\varepsilon_{0},d}(1),$$

uniformly over the finitely many choices of $(\sigma,T,R_{y},R_{z})$.

For later use write

$$\mathsf{A}_{\rm cut}=\Bigl{(}y-\sum_{i\in R_{y}}y_{i}\Bigr{)}+\Bigl{(}z-\sum_{j\in R_{z}}z_{j}\Bigr{)}+\kappa_{T},\qquad\mathsf{B}_{\rm cut}=F/q-\Omega_{T}.$$

The limiting form of (5.3) is $D\leq\mathsf{A}_{\rm cut}+\max(0,\mathsf{B}_{\rm cut})$.

Proof.

Sizes. The box fixes $n_{a,0}=a_{0}$, $n_{b,0}=b_{0}$ and $n_{c,0}=c_{0}$. Write $n_{\sigma,0},n_{y,0},n_{z,0}$ for these coefficients and $S_{\sigma,i},S_{y,i},S_{z,i}$ for the dyadic root sizes of the $\sigma,y,z$ sides. Besides (2.2), the proof uses the dyadic ranges and $\prod_{i}A_{i}^{i}$, $\prod_{i}B_{i}^{i}$, $\prod_{i}C_{i}^{i}\leq X$. So all products and cofactors are at most $X^{O_{d}(1)}$, and Lemmas 4.2 and 4.3 cost $X^{o(1)}$. The coefficients enter no size estimate.

Enumeration. Write $\mathfrak{m}_{i},\mathfrak{y}_{i},\mathfrak{z}_{i}$ for the roots of the $\sigma$-, $y$- and $z$-sides, so $\mathfrak{m}_{i}\sim S_{\sigma,i}$, $\mathfrak{y}_{i}\sim S_{y,i}$, $\mathfrak{z}_{i}\sim S_{z,i}$. Enumerate: the roots of $y$ outside $R_{y}$; of $z$ outside $R_{z}$; the selected roots of $\sigma$. Tails go through Lemma 3.1. The $y$- and $z$-tails are never in $R_{y},R_{z}\subseteq[6]$, so they are enumerated too. The cost is

(5.4) $$X^{(y-\sum_{i\in R_{y}}y_{i})+(z-\sum_{j\in R_{z}}z_{j})+\kappa_{T}+o_{\varepsilon_{0},d}(1)}.$$

Modulus. The tail roots of $\sigma$ are $\mathfrak{m}_{j}$, $j\geq 7$. Put

(5.5) $$M=\prod_{t\in T\cap[6]}\mathfrak{m}_{t}^{\,t}\,M_{\mathrm{tail}}^{\mathbf{1}_{\mathrm{tail}\in T}},\qquad M_{\mathrm{tail}}=\prod_{7\leq j\leq d}\mathfrak{m}_{j}^{\,j}.$$

Then $M$ divides the $\sigma$-side value. Also $\mathfrak{m}_{t}\geq S_{\sigma,t}=X^{\sigma_{t}}$ (left-closed intervals), and Lemma 3.1 bounds the tail. So

(5.6) $$M\geq X^{\Omega_{T}}.$$

Put

(5.7) $$u=\prod_{i\in R_{y}}\mathfrak{y}_{i}^{\,i/q},\qquad v=\prod_{j\in R_{z}}\mathfrak{z}_{j}^{\,j/q},$$

an empty product being $1$; the exponents are integers by (5.2).

Congruence. By Lemma 2.1, every factor of the $y$- and $z$-sides is a unit modulo $M$. This covers the coefficients, the enumerated roots, $u$ and $v$. The equation of (2.2) modulo $M$ gives

(5.8) $$(uv^{-1})^{q}\equiv K\pmod{M}$$

with

(5.9) $$K\equiv\epsilon_{\rm cut}E_{z}E_{y}^{-1}\pmod{M},\qquad\epsilon_{\rm cut}=\begin{cases}-1,&\sigma=c,\\ +1,&\sigma\neq c,\end{cases}$$

where

$$E_{y} =n_{y,0}\prod_{i\in[6]\setminus R_{y}}\mathfrak{y}_{i}^{\,i}\prod_{7\leq j\leq d}\mathfrak{y}_{j}^{\,j},$$

$$E_{z} =n_{z,0}\prod_{j\in[6]\setminus R_{z}}\mathfrak{z}_{j}^{\,j}\prod_{7\leq j\leq d}\mathfrak{z}_{j}^{\,j}.$$

So $K$ is a unit fixed by the enumerated data.

Count. By Lemma 4.2, $\xi=uv^{-1}$ lies in one of $X^{o(1)}$ classes. By Lemma 2.1, $\gcd(u,v)=1$. Also

$$u\leq 2^{\sum_{i\in R_{y}}i/q}\prod_{i\in R_{y}}S_{y,i}^{\,i/q}=:U_{\rm cut},\qquad v\leq 2^{\sum_{j\in R_{z}}j/q}\prod_{j\in R_{z}}S_{z,j}^{\,j/q}=:V_{\rm cut},$$

with $U_{\rm cut},V_{\rm cut}\geq 1$; the powers of $2$ cost $O_{d}(1/\log X)$, as $\sum_{r\leq 6}r=21$. Hence

$$U_{\rm cut}=X^{\sum_{i\in R_{y}}i\,y_{i}/q+O_{d}(1/\log X)},\qquad V_{\rm cut}=X^{\sum_{j\in R_{z}}j\,z_{j}/q+O_{d}(1/\log X)},$$

so $U_{\rm cut}V_{\rm cut}=X^{F/q+O_{d}(1/\log X)}$. Lemma 4.1 and (5.6) bound the pairs $(u,v)$ in one class by

(5.10) $$1+\frac{2U_{\rm cut}V_{\rm cut}}{M}\ll_{d}X^{\max\{F/q-\Omega_{T},0\}+O_{d}(1/\log X)}.$$

Recovery. Lemma 4.3 recovers the free roots from $u,v$ up to $X^{o(1)}$. Then the $y$- and $z$-side values are known, and the equation fixes the $\sigma$-side value. Divide by $n_{\sigma,0}$ and the selected roots:

$$Q_{\sigma}=\prod_{i\in[6]\setminus T}\mathfrak{m}_{i}^{\,i}\,\left(\prod_{7\leq j\leq d}\mathfrak{m}_{j}^{\,j}\right)^{1-\mathbf{1}_{\mathrm{tail}\in T}}.$$

Lemma 4.3 recovers these unselected roots up to $X^{o(1)}$. Multiplying (5.4) by $X^{o(1)}$ and (5.10) gives (5.3). ∎

If one free set is empty, $U_{\rm cut}=1$ or $V_{\rm cut}=1$, and Lemma 4.1 still applies. The exponent $q$ depends only on the index sets $R_{y},R_{z}$, not on which roots equal $1$. Counting coefficients is charged to (2.3): inside a box $a_{0},b_{0},c_{0}$ are fixed.

Count: $64$ subsets of $[6]$ per counted side, $127$ sets $T$, three sides $\sigma$. Without the pair of empty free sets this is $3(64^{2}-1)127=1\,560\,195$, as in (1.3).

6. Archimedean rows

Throughout Sections 6–8, assume $0<\mu\leq 1$. Take $\varepsilon_{0}\leq 4/7$ and $d=d(\varepsilon_{0})$ as fixed in Section 3.1. Fix a box admissible in (2.3) at scale $Y$, with $\lambda$ replaced by $\mu$ and $\mathcal{B}_{d}\geq 1$. Of the constraints (2.4) only the side-value bounds are used below, with the coefficient bound $1\leq n_{s,0}\leq Y^{\varepsilon_{0}}$. We also use the equation, the gcd condition and the windows of (2.2). For the finite estimates take $Y\geq Y_{0}$, the threshold of Lemma 12.2; it depends only on $\varepsilon_{0},d$, and $Y_{0}\geq\exp(\exp(1))$. All coordinates $s,\tau_{s},v_{s},L,p_{i}$ from Section 2 are now read at base $Y$. The integer side values are denoted by $n_{s}$; $V_{s}$ is the exponent coordinate of the root product, not of $n_{s}$. The root mass of side $s$ is $s=\sum_{i\leq d}s_{i}$. Put $s_{i}=\log_{Y}S_{s,i}$ and $D=\log_{Y}\mathcal{B}_{d}$.

(6.1) $$V_{s}=\log_{Y}\prod_{j\leq d}S_{s,j}^{\,j}=\sum_{i\leq 6}i\,s_{i}+v_{s}\qquad(s=a,b,c).$$

For a tuple of the box write $n_{s}=n_{s,0}\prod_{j\leq d}\mathfrak{s}_{j}^{\,j}$ for its side values, so $n_{a}+n_{b}=n_{c}$. Here $n_{s,0}$ is the coefficient $a_{0},b_{0}$ or $c_{0}$ on side $s$. Since $S_{j}\leq\mathfrak{s}_{j}<2S_{j}$ and $1\leq n_{s,0}\leq Y^{\varepsilon_{0}}$,

(6.2) $$Y^{V_{s}}\leq n_{s}<2^{h_{d}}\,n_{s,0}\,Y^{V_{s}}\leq 2^{h_{d}}\,Y^{V_{s}+\varepsilon_{0}}.$$

The side-value constraints of (2.4) read

(6.3) $$V_{a}\leq 1,\qquad V_{b}\leq 1,\qquad 1-\frac{\varepsilon_{0}}{2}\leq V_{c}\leq 1.$$

Lemma 6.1.

$$V_{a}\leq V_{c}+\frac{\varepsilon_{0}}{2},\qquad V_{b}\leq V_{c}+\frac{\varepsilon_{0}}{2}.$$

Proof.

By (6.3), $V_{a}\leq 1\leq V_{c}+\varepsilon_{0}/2$. Likewise for $V_{b}$. ∎

Lemma 6.2.

At least one of

$$V_{c}\leq V_{a}+\frac{3\varepsilon_{0}}{2}+\log_{Y}2^{1+h_{d}},\qquad V_{c}\leq V_{b}+\frac{3\varepsilon_{0}}{2}+\log_{Y}2^{1+h_{d}}$$

holds.

Proof.

As $\mathcal{B}_{d}\geq 1$, choose one tuple of the box. Then $n_{a},n_{b}\geq 1$ and $n_{a}+n_{b}=n_{c}$, so $\max(n_{a},n_{b})\geq n_{c}/2$. Suppose $n_{a}\geq n_{c}/2$. By (6.3) and (6.2),

$$Y^{1-\varepsilon_{0}/2}\leq Y^{V_{c}}\leq n_{c}\leq 2n_{a}<2^{1+h_{d}}\,Y^{V_{a}+\varepsilon_{0}}.$$

Take $\log_{Y}$:

$$1\leq V_{a}+\frac{3\varepsilon_{0}}{2}+\log_{Y}2^{1+h_{d}}.$$

With $V_{c}\leq 1$ this is the first inequality. If $n_{b}\geq n_{c}/2$, the same argument gives the second. ∎

The choice in Lemma 6.2 uses one tuple. The conclusion concerns the dyadic endpoints, so it holds for the whole box.

Corollary 6.3.

Put $\rho_{\mathrm{arch}}=3\varepsilon_{0}/2+\log_{Y}2^{1+h_{d}}$. Every nonempty admissible box satisfies

(6.4) $$V_{a}\leq V_{c}+\rho_{\mathrm{arch}},\qquad V_{b}\leq V_{c}+\rho_{\mathrm{arch}},$$

and at least one arm of

(6.5) $$V_{c}\leq V_{a}+\rho_{\mathrm{arch}}\quad\text{or}\quad V_{c}\leq V_{b}+\rho_{\mathrm{arch}}.$$

Proof.

Lemmas 6.1 and 6.2, and $\varepsilon_{0}/2\leq\rho_{\mathrm{arch}}$. ∎

In the limit $\rho_{\mathrm{arch}}\to 0$, the first arm of (6.5) with (6.4) gives $V_{a}=V_{c}\geq V_{b}$, the second $V_{b}=V_{c}\geq V_{a}$. A cover node of the certificate carries both arms.

7. The cubic row

We use the following theorem of Heath-Brown [8, Theorem 1.3], with its counting function $\rho$ renamed $\mathcal{R}$. In this theorem $B$ is a height and $a,b,c$ are coefficients.

Theorem A ([8, Theorem 1.3]).

Let $\mathcal{R}(B;a,b,c)$ be the number of integer solutions $x,y,z$ to the equation

$$ax^{3}+by^{3}+cz^{3}=0$$

with $\gcd(x,y,z)=1$ and $\max(|x|,|y|,|z|)\leq B$. Then

$$\mathcal{R}(B;a,b,c)\ll_{\varepsilon}B^{\varepsilon}$$

for any $\varepsilon>0$, uniformly for all non-zero integer $a,b,c$.

The implied constant depends on $\varepsilon$ alone. The coefficients need not be coprime or positive.

Proposition 7.1.

For every $\varepsilon_{1}>0$,

(7.1) $$D\leq\sum_{s=a,b,c}(s-s_{3})+\varepsilon_{1}+O_{\varepsilon_{1}}\Bigl{(}\frac{1}{\log Y}\Bigr{)}=L-p_{3}+\varepsilon_{1}+O_{\varepsilon_{1}}\Bigl{(}\frac{1}{\log Y}\Bigr{)}.$$

The implied constant depends only on $\varepsilon_{1}$.

Proof.

Enumeration. Send a tuple of the box to its roots $(\mathfrak{a}_{i},\mathfrak{b}_{i},\mathfrak{c}_{i})_{i\neq 3}$ and to $(x_{a},x_{b},x_{c})=(\mathfrak{a}_{3},\mathfrak{b}_{3},\mathfrak{c}_{3})$. This map is injective. As $\#\{\mathfrak{s}:\mathfrak{s}\sim S\}=S$, the first component takes at most

$$\prod_{s=a,b,c}\ \prod_{i\leq d,\ i\neq 3}S_{s,i}=Y^{\sum_{s}(s-s_{3})}$$

values. The tail roots $i\geq 7$ are enumerated one by one, as in Lemma 3.1.

Equation. Fix the first component. Put

$$\alpha=a_{0}\prod_{i\neq 3}\mathfrak{a}_{i}^{\,i},\qquad\beta=b_{0}\prod_{i\neq 3}\mathfrak{b}_{i}^{\,i},\qquad\gamma=c_{0}\prod_{i\neq 3}\mathfrak{c}_{i}^{\,i}.$$

These are positive integers. The equation of (2.2) becomes

$$\alpha x_{a}^{3}+\beta x_{b}^{3}+(-\gamma)x_{c}^{3}=0.$$

Primitivity. $x_{a}\mid n_{a}$, $x_{b}\mid n_{b}$, $x_{c}\mid n_{c}$, and the side values are pairwise coprime by Lemma 2.1. Hence $\gcd(x_{a},x_{b},x_{c})=1$.

Height. $1\leq x_{a}<2A_{3}\leq 2\bigl{(}\prod_{j}A_{j}^{\,j}\bigr{)}^{1/3}\leq 2Y$ by (6.3). Likewise $x_{b},x_{c}<2Y$.

Count. By Theorem A with $B=2Y$ and coefficients $(\alpha,\beta,-\gamma)$, the number of $(x_{a},x_{b},x_{c})$ is at most $\mathcal{R}(2Y;\alpha,\beta,-\gamma)\leq C(\varepsilon_{1})(2Y)^{\varepsilon_{1}}$, uniformly in $\alpha,\beta,\gamma$. Hence

$$\mathcal{B}_{d}\leq C(\varepsilon_{1})\,2^{\varepsilon_{1}}\,Y^{\sum_{s}(s-s_{3})+\varepsilon_{1}}.$$

Take $\log_{Y}$. ∎

The bound is uniform in the coefficients $a_{0},b_{0},c_{0}$ and in the enumerated roots. A constant depending on $\alpha,\beta,\gamma$ would not give a row.

8. Spacing rows

Choose $e\in\{a,b,c\}$, either ordering $(y,z)$ of the other two sides, and $2\leq\ell\leq 6$. Put

(8.1) $$\mathsf{A}_{\rm sp}=y+(z-z_{\ell}),\qquad\mathsf{B}_{\rm sp}=V_{e}-V_{z}+z_{\ell}.$$

Here $y$ and $z$ also denote the root masses of these sides, as in (2.5).

For side $e$, write $n_{e,0}$ for its coefficient and $\mathfrak{e}_{j}$ for its roots (Section 6). Choose $K_{d}$ so that

$$\operatorname{div}(N)^{d-1}\leq Y^{K_{d}/\log\log Y}\quad\text{if }Y\geq\exp(\exp(1)),\quad N\leq 2^{h_{d}}Y;$$

such a constant exists by the divisor bound.

Proposition 8.1.

(8.2) $$D\leq\mathsf{A}_{\rm sp}+\max\{\mathsf{B}_{\rm sp},0\}+\varepsilon_{0}+O_{d}\Bigl{(}\frac{1}{\log\log Y}\Bigr{)}.$$

Proof.

Signs. From $n_{a}+n_{b}=n_{c}$,

$$n_{e}=\varsigma_{y}n_{y}+\varsigma_{z}n_{z},\qquad(\varsigma_{y},\varsigma_{z})=\begin{cases}(1,1),&e=c,\\ (-1,1),&e\neq c,\ z=c,\\ (1,-1),&e\neq c,\ y=c.\end{cases}$$

This ordering need not be the alphabetical order used in Section 5.

Enumeration. Enumerate all roots $\mathfrak{y}_{j}$ $(j\leq d)$ of $y$ and all roots $\mathfrak{z}_{j}$ $(j\leq d,\ j\neq\ell)$ of $z$. As $\#\{\mathfrak{s}:\mathfrak{s}\sim S\}=S$, there are

(8.3) $$\prod_{j\leq d}S_{y,j}\prod_{j\neq\ell}S_{z,j}=Y^{y+z-z_{\ell}}$$

choices. Fix one. Then $n_{y}$ is fixed, and

$$n_{z}=\Pi_{z}\,x^{\ell},\qquad\Pi_{z}=n_{z,0}\prod_{j\neq\ell}\mathfrak{z}_{j}^{\,j},\qquad x=\mathfrak{z}_{\ell}\in[S_{z,\ell},2S_{z,\ell}).$$

Interval. By (6.2), $n_{e}$ lies in an interval $I_{e}$ of length $|I_{e}|<2^{h_{d}}Y^{V_{e}+\varepsilon_{0}}$. Then

$$x^{\ell}=\varsigma_{z}\,\frac{n_{e}-\varsigma_{y}n_{y}}{\Pi_{z}}\in J,\qquad J=\varsigma_{z}\,\frac{I_{e}-\varsigma_{y}n_{y}}{\Pi_{z}},$$

an interval of length $|I_{e}|/\Pi_{z}$. As $\Pi_{z}\geq\prod_{j\neq\ell}S_{z,j}^{\,j}=Y^{V_{z}-\ell z_{\ell}}$,

$$|J|<2^{h_{d}}\,Y^{V_{e}-V_{z}+\ell z_{\ell}+\varepsilon_{0}}.$$

Spacing. Let $\mathcal{X}$ be the integers $x\in[S_{z,\ell},2S_{z,\ell})$ for which $x^{\ell}\in J$, and put $m=|\mathcal{X}|$. If $m=0$, this enumeration choice contributes nothing. Otherwise write $x_{1}<\dots<x_{m}$ for $\mathcal{X}$. For $i\geq 2$,

$$x_{i}^{\ell}-x_{i-1}^{\ell}\geq\ell\,x_{i-1}^{\ell-1}\geq S_{z,\ell}^{\ell-1}=Y^{(\ell-1)z_{\ell}}.$$

So $(m-1)Y^{(\ell-1)z_{\ell}}\leq x_{m}^{\ell}-x_{1}^{\ell}<|J|$, and

(8.4) $$m<1+2^{h_{d}}Y^{\mathsf{B}_{\rm sp}+\varepsilon_{0}}\leq 2^{1+h_{d}}\,Y^{\max\{\mathsf{B}_{\rm sp},0\}+\varepsilon_{0}}.$$

This includes $S_{z,\ell}=1$, where $x=1$ and $m\leq 1$.

Recovery. Given $x$, $n_{z}$ and then $n_{e}=\varsigma_{y}n_{y}+\varsigma_{z}n_{z}$ are fixed. Put $N=n_{e}/n_{e,0}=\prod_{j\leq d}\mathfrak{e}_{j}^{\,j}<2^{h_{d}}Y$. By Lemma 4.3 the roots of $e$ take at most $Y^{K_{d}/\log\log Y}$ values.

Total. Multiply (8.3), (8.4) and the recovery factor:

$$\mathcal{B}_{d}\leq 2^{1+h_{d}}\,Y^{\mathsf{A}_{\rm sp}+\max\{\mathsf{B}_{\rm sp},0\}+\varepsilon_{0}+O_{d}(1/\log\log Y)}.$$

Take $\log_{Y}$; $2^{1+h_{d}}$ costs $O_{d}(1/\log Y)$. ∎

Corollary 8.2.

Put

$$\rho_{\mathrm{sp}}=\varepsilon_{0}+\frac{K_{d}}{\log\log Y}+\log_{Y}2^{1+h_{d}}.$$

This is the error in (8.2). For each of the $3\cdot 2\cdot 5=30$ choices of $(e,y,z,\ell)$, a nonempty admissible box satisfies at least one arm of

(8.5) $$D\leq\mathsf{A}_{\rm sp}+\rho_{\mathrm{sp}}\quad\text{or}\quad D\leq\mathsf{A}_{\rm sp}+\mathsf{B}_{\rm sp}+\rho_{\mathrm{sp}}.$$

Proof.

$\mathsf{A}_{\rm sp}+\max\{\mathsf{B}_{\rm sp},0\}=\max(\mathsf{A}_{\rm sp},\mathsf{A}_{\rm sp}+\mathsf{B}_{\rm sp})$. ∎

All these errors are $\mu$-free. With $\varepsilon_{1}=\varepsilon_{0}$, each is at most $2\varepsilon_{0}$ for $Y\geq Y_{0}$. Table 12.1 lists them with the others.

9. Cubic-sieve rows

9.1. Setting

Fix $\varepsilon_{0}\leq 4/7$ and $d=d(\varepsilon_{0})$ as in Section 3.1. Assume $Y\geq Y_{0}$, the threshold of Lemma 12.2. Fix parameters for a nonempty box counted by $\mathcal{B}_{d}$ in (2.3) at scale $Y$, and put $D=\log_{Y}\mathcal{B}_{d}$. For each side $s\in\{a,b,c\}$, write $n_{s,0}$ for its coefficient and $\mathfrak{r}_{s,j}\sim S_{s,j}$ $(1\leq j\leq d)$ for its roots. The symbols $M,x,u,v,U,V,\xi$ below are local to this section. Its $M$ is the canonical coefficient of (9.3). The modulus $Q$ is local to each analytic-input lemma and to Steps 5–7 of Proposition 9.10. Here $v_{s}$ is the tail coordinate, while $v$ is a represented-side label. The integer $V$ (as in $V_{\mathfrak{o}}$, $V(\mathbf{u})$, $V_{\iota}$) is distinct from the coordinate $V_{s}$. The side values

$$n_{s}=n_{s,0}\prod_{j\leq d}\mathfrak{r}_{s,j}^{\,j}$$

satisfy $n_{a}+n_{b}=n_{c}$ and are pairwise coprime by Lemma 2.1. The coordinates are

(9.1) $$\begin{gathered}s_{s,j}=\log_{Y}S_{s,j},\qquad r_{s}=\sum_{j\leq d}s_{s,j},\qquad t_{s}=\sum_{7\leq j\leq d}s_{s,j},\\ v_{s}=\sum_{7\leq j\leq d}j\,s_{s,j},\qquad V_{s}=\sum_{j\leq 6}j\,s_{s,j}+v_{s}.\end{gathered}$$

In the notation of Section 2, $r_{s}=s$ and $t_{s}=\tau_{s}$; the coordinate $s_{s,j}$ is the earlier $s_{j}$. By (2.4), $V_{s}\leq 1$. Hence $n_{s}\leq n_{s,0}\prod_{j}(2S_{s,j})^{j}\leq 2^{d^{2}}Y^{1+\varepsilon_{0}}\leq Y^{2}$ for large $Y$.

Fix a powered side $\sigma$. Its two represented sides $u,v$ and the sign $\epsilon_{\rm pw}$ are

(9.2) $$(\sigma;u,v;\epsilon_{\rm pw})\in\{(a;b,c;-1),\ (b;a,c;-1),\ (c;a,b;+1)\},\qquad n_{v}+\epsilon_{\rm pw}\,n_{u}=n_{\sigma}>0.$$

So $\sigma\in\{a,b\}$ uses the positive difference $n_{c}-n_{u}$. The side $\sigma=c$ uses the sum $n_{a}+n_{b}$. Put

(9.3) $$M=n_{\sigma,0}\,\mathfrak{r}_{\sigma,1}\mathfrak{r}_{\sigma,2}^{\,2}\mathfrak{r}_{\sigma,4}\mathfrak{r}_{\sigma,5}^{\,2}\prod_{7\leq j\leq d}\mathfrak{r}_{\sigma,j}^{\,j},\qquad x=\mathfrak{r}_{\sigma,3}\mathfrak{r}_{\sigma,4}\mathfrak{r}_{\sigma,5}\mathfrak{r}_{\sigma,6}^{\,2}.$$

Then $n_{\sigma}=Mx^{3}$. We call $M$ the canonical coefficient. Its labels are the tuple

$$(\mathfrak{r}_{\sigma,j})_{j\in\{1,2,4,5,7,\dots,d\}}.$$

Put

(9.4) $$\mathcal{C}_{\sigma}=r_{\sigma}-s_{\sigma,3}-s_{\sigma,6},\qquad W_{\sigma}=v_{\sigma}+s_{\sigma,1}+2s_{\sigma,2}+s_{\sigma,4}+2s_{\sigma,5},\qquad R_{\sigma}=r_{u}+r_{v}.$$

Here $R_{\sigma}$ is the combined root mass of the represented sides. Put $\zeta_{\sigma}=\log_{Y}n_{\sigma,0}$. The coefficient range in (2.3) gives $0\leq\zeta_{\sigma}\leq\varepsilon_{0}$. Since each labelled root lies in $[S_{\sigma,j},2S_{\sigma,j})$, the finite-box modulus satisfies

(9.5) $$W_{\sigma}+\zeta_{\sigma}\leq\log_{Y}M<W_{\sigma}+\zeta_{\sigma}+\frac{\bigl{(}6+\sum_{7\leq j\leq d}j\bigr{)}\log 2}{\log Y}=W_{\sigma}+\zeta_{\sigma}+O_{d}\!\left(\frac{1}{\log Y}\right).$$

Lemma 9.1.

1. There are at most $Y^{\mathcal{C}_{\sigma}}$ label tuples.

2. Every label tuple gives $M\geq Y^{W_{\sigma}}$.

3. $W_{\sigma}-\mathcal{C}_{\sigma}=s_{\sigma,2}+s_{\sigma,5}+(v_{\sigma}-t_{\sigma})\geq 0$.

4. A given integer $M\leq Y^{2}$ arises from $Y^{o_{d}(1)}$ label tuples.

Proof.

(i) $\#\{\mathfrak{r}:\mathfrak{r}\sim S\}=S$, and $\prod_{j\neq 3,6}S_{\sigma,j}=Y^{r_{\sigma}-s_{\sigma,3}-s_{\sigma,6}}$. (ii) $n_{\sigma,0}\geq 1$ and $\mathfrak{r}_{\sigma,j}\geq S_{\sigma,j}$, so $M\geq Y^{W_{\sigma}}$. Also

$$M\leq n_{\sigma,0}\prod_{j\leq d}\mathfrak{r}_{\sigma,j}^{\,j}<2^{h_{d}}Y^{V_{\sigma}+\varepsilon_{0}}\leq Y^{2}$$

for large $Y$, since $V_{\sigma}\leq 1$ and $\varepsilon_{0}<1$. (iii) Expand (9.4); $v_{\sigma}\geq 7t_{\sigma}$ by (9.1). (iv) $n_{\sigma,0}$ is fixed; apply Lemma 4.3 to $M/n_{\sigma,0}$ with $r=d-2$. ∎

All $o(1)$ below tend to $0$ as $Y\to\infty$, for fixed $\varepsilon_{0}$, $d$ and the parameter $\theta$ of the sieve. They are uniform in the box.

9.2. Analytic inputs

Fix once and for all $w\in C^{\infty}(\mathbb{R})$ with $0\leq w\leq 1$, $\operatorname{supp}w\subset[1/2,4]$ and $w=1$ on $[1,2]$. For a Dirichlet character $\chi$, extended by $0$ on nonunits, and $N\geq 1$ put

(9.6) $$F_{N}(\chi)=\sum_{n\geq 1}\chi(n)\,w(n/N).$$

We quote the all-character estimate of [6, Lemma 4]. In this section $Q$ denotes the modulus of an analytic input, or the modulus $M\mathfrak{p}_{1}\mathfrak{p}_{2}$ of Steps 5–7 of Proposition 9.10. It is local to that input or step. It differs from the cut cofactor $Q_{\sigma}$ and the geometry forms $Q_{j}$. The $L(s,\chi)$ below is the Dirichlet $L$-function, not the root mass $L$; $s$ in this subsection is a complex variable.

Lemma 9.2 ([6, Lemma 4], “Hybrid fourth moment estimate”).

Let $H\geq 2$ and $q_{0}\geq 2$. Then

$$\sum_{\chi}\int_{|t|\leq H}\bigl{|}L(\tfrac{1}{2}+it,\chi)\bigr{|}^{4}dt\ll H\varphi(q_{0})\log(Hq_{0})^{4},$$

where the sum is over all characters modulo $q_{0}$.

The all-character estimate in Lemma 9.2 is the only input needed for the next lemma. Since $\varphi(Q)\leq Q$, it implies the weaker form used below.

Lemma 9.3.

For $H\geq 2$ and $Q\geq 2$,

$$\sum_{\chi\bmod Q}\int_{|t|\leq H}|L(\tfrac{1}{2}+it,\chi)|^{4}\,dt\ll HQ\log(HQ)^{4}.$$

Proof.

Apply Lemma 9.2 with $q_{0}=Q\geq 2$ and use $\varphi(Q)\leq Q$. In our applications $Q\leq Y^{O_{d,\theta}(1)}$. The factor $Q/\varphi(Q)$ lost here is paid in Step 7 of Proposition 9.10. ∎

Lemma 9.4.

For all integers $Q\geq 2$ and reals $N\geq 1$,

(9.7) $$\sum_{\begin{subarray}{c}\chi\bmod Q\\ \chi\neq\chi_{0}\end{subarray}}|F_{N}(\chi)|^{4}\ll Q\,N^{2}\log(2Q)^{4}.$$

The implied constant depends only on $w$.

Proof.

Let $\widetilde{w}(s)=\int_{0}^{\infty}w(y)y^{s-1}dy$. It is entire. Four integrations by parts give, for $\tfrac{1}{2}\leq\Re s\leq 2$,

$$\widetilde{w}(s)=\frac{1}{s(s+1)(s+2)(s+3)}\int_{0}^{\infty}w^{(4)}(y)\,y^{s+3}dy\ll(1+|s|)^{-4}.$$

By Mellin inversion,

$$F_{N}(\chi)=\frac{1}{2\pi i}\int_{(2)}L(s,\chi)\,\widetilde{w}(s)\,N^{s}\,ds.$$

Let $\chi\neq\chi_{0}$. Its partial sums $A_{\chi}(y)=\sum_{n\leq y}\chi(n)$ satisfy $|A_{\chi}(y)|\leq\varphi(Q)$. Partial summation gives $L(s,\chi)=s\int_{1}^{\infty}A_{\chi}(y)y^{-s-1}dy$. Thus $L(s,\chi)$ is holomorphic in $\Re s>0$, and $|L(s,\chi)|\leq 2Q(1+|s|)$ for $\Re s\geq\frac{1}{2}$. The integrand is therefore $\ll QN^{2}(1+|s|)^{-3}$ on $\tfrac{1}{2}\leq\Re s\leq 2$. Move the line to $\Re s=\frac{1}{2}$; there is no pole. With $k_{w}(t)=|\widetilde{w}(\tfrac{1}{2}+it)|\ll(1+|t|)^{-4}$,

$$|F_{N}(\chi)|\leq\frac{N^{1/2}}{2\pi}\int_{\mathbb{R}}\bigl{|}L(\tfrac{1}{2}+it,\chi)\bigr{|}\,k_{w}(t)\,dt.$$

Hölder with respect to $k_{w}(t)\,dt$ gives

$$|F_{N}(\chi)|^{4} \leq\frac{N^{2}}{(2\pi)^{4}}\Bigl{(}\int k_{w}\Bigr{)}^{3}\int_{\mathbb{R}}\bigl{|}L(\tfrac{1}{2}+it,\chi)\bigr{|}^{4}k_{w}(t)\,dt$$

$$\ll N^{2}\int_{\mathbb{R}}\bigl{|}L(\tfrac{1}{2}+it,\chi)\bigr{|}^{4}(1+|t|)^{-4}dt.$$

Sum over $\chi\neq\chi_{0}$ and enlarge to all $\chi\bmod Q$. Split $|t|\leq 2$ and $2^{j-1}<|t|\leq 2^{j}$ $(j\geq 2)$. By Lemma 9.3 with modulus $Q$ and $H=2^{j}$,

$$\sum_{\chi\neq\chi_{0}}|F_{N}(\chi)|^{4}\ll N^{2}\sum_{j\geq 1}2^{-4(j-1)}\,2^{j}Q\log(2^{j}Q)^{4}\ll N^{2}Q\log(2Q)^{4}\sum_{j\geq 1}2^{4-3j}j^{4}.$$

The last sum converges. ∎

Lemma 9.5.

For $N^{\prime},N^{\prime\prime}\geq 1$ and a Dirichlet character $\chi$, put

$$G(\chi)=F_{N^{\prime}}(\chi)F_{N^{\prime\prime}}(\chi^{2}),\qquad Z_{0}=4^{6}(N^{\prime}N^{\prime\prime\,2})^{2}.$$

For every integer $Q\geq 1$ and $\delta>0$,

(9.8) $$\sum_{\chi\bmod Q}|G(\chi)|^{4}\ll_{\delta}\varphi(Q)\,(N^{\prime}N^{\prime\prime})^{2}\,Z_{0}^{\delta}\Bigl{(}1+\frac{Z_{0}}{Q}\Bigr{)}.$$

The sum includes the principal character.

Proof.

Complete multiplicativity gives

$$G(\chi)=\sum_{n\geq 1}A(n)\chi(n),\qquad A(n)=\sum_{n_{1}n_{2}^{2}=n}w(n_{1}/N^{\prime})\,w(n_{2}/N^{\prime\prime})\geq 0.$$

The coefficients do not depend on $\chi$. Then $G(\chi)^{2}=\sum_{m}B(m)\chi(m)$ with $B=A*A\geq 0$. Now $B(m)=0$ unless $m\leq(4N^{\prime}(4N^{\prime\prime})^{2})^{2}=Z_{0}$, and

$$B(m)\leq\#\{(n_{1},n_{2},n_{3},n_{4}):n_{1}n_{2}^{2}n_{3}n_{4}^{2}=m\}\ll_{\delta}m^{\delta}$$

by Lemma 4.3. Also

$$\sum_{m}B(m)=\Bigl{(}\sum_{n}A(n)\Bigr{)}^{2}=\Bigl{(}\sum_{n_{1}}w(n_{1}/N^{\prime})\Bigr{)}^{2}\Bigl{(}\sum_{n_{2}}w(n_{2}/N^{\prime\prime})\Bigr{)}^{2}\leq(16N^{\prime}N^{\prime\prime})^{2}.$$

Orthogonality over all characters modulo $Q$ gives

$$\sum_{\chi\bmod Q}|G(\chi)|^{4}=\sum_{\chi\bmod Q}\Bigl{|}\sum_{m}B(m)\chi(m)\Bigr{|}^{2}=\varphi(Q)\sum_{\begin{subarray}{c}m\equiv m^{\prime}\ (\mathrm{mod}\ Q)\\ (mm^{\prime},Q)=1\end{subarray}}B(m)B(m^{\prime}).$$

For fixed $m$, at most $1+Z_{0}/Q$ integers $m^{\prime}\in[1,Z_{0}]$ satisfy $m^{\prime}\equiv m\pmod{Q}$. Hence the right side is at most

$$\varphi(Q)\sum_{m}B(m)\cdot\max_{m^{\prime}\leq Z_{0}}B(m^{\prime})\cdot\Bigl{(}1+\frac{Z_{0}}{Q}\Bigr{)}.$$

Insert the two bounds. ∎

Lemma 9.6.

Let $\ell$ be prime, $\psi$ a nonprincipal and $\nu$ any character modulo $\ell$, and $\epsilon\in\{\pm 1\}$. Then

$$\Bigl{|}\sum_{t\in(\mathbb{Z}/\ell)^{\times}}\nu(t)\,\psi(1+\epsilon t)\Bigr{|}\leq\sqrt{\ell}.$$

Proof.

If $\nu$ is principal the sum is $\sum_{y\in\mathbb{F}_{\ell}}\psi(y)-\psi(1)=-1$. Otherwise substitute $y=-\epsilon t$. The sum becomes $\nu(-\epsilon)\mathcal{J}(\nu,\psi)$ with $\mathcal{J}(\nu,\psi)=\sum_{y\in\mathbb{F}_{\ell}}\nu(y)\psi(1-y)$, both characters nonprincipal. Then $|\mathcal{J}(\nu,\psi)|=\sqrt{\ell}$ if $\nu\psi$ is nonprincipal and $|\mathcal{J}(\nu,\psi)|=1$ otherwise [9, Ch. 8, §3]. ∎

Lemma 9.7.

Let $M\geq 1$, and let $\mathfrak{p}_{1}\neq\mathfrak{p}_{2}$ be primes not dividing $M$. Put $Q=M\mathfrak{p}_{1}\mathfrak{p}_{2}$. Let $\xi$ be a character modulo $\mathfrak{p}_{1}\mathfrak{p}_{2}$. Assume its components modulo $\mathfrak{p}_{1}$ and $\mathfrak{p}_{2}$ are both nonprincipal. Let $\tilde{\xi}$ be the character modulo $Q$ induced by $\xi$, and fix $\epsilon\in\{\pm 1\}$. There are coefficients $c_{\epsilon}(\alpha)\in\mathbb{C}$ for characters $\alpha$ modulo $Q$, with

(9.9) $$|c_{\epsilon}(\alpha)|\leq\sqrt{\mathfrak{p}_{1}\mathfrak{p}_{2}},$$

such that for all integers $U,V$

(9.10) $$\mathbf{1}_{(UV,Q)=1}\,\mathbf{1}_{M\mid V+\epsilon U}\;\xi\Bigl{(}\frac{V+\epsilon U}{M}\Bigr{)}=\frac{\overline{\xi(M)}}{\varphi(Q)}\sum_{\alpha\bmod Q}c_{\epsilon}(\alpha)\,\alpha(U)\,(\tilde{\xi}\bar{\alpha})(V).$$

The left side is read as $0$ when $M\nmid V+\epsilon U$.

Proof.

If $(UV,Q)>1$, then $\alpha(U)(\tilde{\xi}\bar{\alpha})(V)=0$ for every $\alpha$, and both sides vanish. Let $(UV,Q)=1$. By the Chinese remainder theorem each $\alpha$ is $\alpha=\eta\nu$ with unique $\eta\bmod M$ and $\nu\bmod\mathfrak{p}_{1}\mathfrak{p}_{2}$; then $\tilde{\xi}\bar{\alpha}=\bar{\eta}\cdot\xi\bar{\nu}$. Define

$$c_{\epsilon}(\alpha)=\eta(-\epsilon)\,\hat{f}(\nu),\qquad\hat{f}(\nu)=\sum_{y\in(\mathbb{Z}/\mathfrak{p}_{1}\mathfrak{p}_{2})^{\times}}\bar{\nu}(y)\,\xi(1+\epsilon y).$$

Orthogonality on the finite group $(\mathbb{Z}/M)^{\times}$, for any $M$, gives

$$\frac{1}{\varphi(M)}\sum_{\eta\bmod M}\eta(-\epsilon U)\bar{\eta}(V)=\mathbf{1}_{-\epsilon U\equiv V\ (\mathrm{mod}\ M)}=\mathbf{1}_{M\mid V+\epsilon U}.$$

Fourier inversion of $f(y)=\xi(1+\epsilon y)$ on $(\mathbb{Z}/\mathfrak{p}_{1}\mathfrak{p}_{2})^{\times}$, at $y=UV^{-1}$, gives

$$\frac{1}{\varphi(\mathfrak{p}_{1}\mathfrak{p}_{2})}\sum_{\nu\bmod\mathfrak{p}_{1}\mathfrak{p}_{2}}\hat{f}(\nu)\,\nu(U)\,(\xi\bar{\nu})(V)=\xi(V)\,\xi(1+\epsilon UV^{-1})=\xi(V+\epsilon U).$$

Multiply; $\varphi(Q)=\varphi(M)\varphi(\mathfrak{p}_{1}\mathfrak{p}_{2})$. The right side of (9.10) becomes

$$\overline{\xi(M)}\,\mathbf{1}_{M\mid V+\epsilon U}\,\xi(V+\epsilon U).$$

If $M\mid V+\epsilon U$, then $\xi(V+\epsilon U)=\xi(M)\,\xi((V+\epsilon U)/M)$ and $|\xi(M)|=1$. This is (9.10). Write $\xi=\xi_{\mathfrak{p}_{1}}\xi_{\mathfrak{p}_{2}}$ and $\nu=\nu_{\mathfrak{p}_{1}}\nu_{\mathfrak{p}_{2}}$. The Chinese remainder theorem factors $\hat{f}(\nu)$ into two sums of the shape of Lemma 9.6, with $\psi=\xi_{\mathfrak{p}_{1}}$, $\xi_{\mathfrak{p}_{2}}$. This gives (9.9). ∎

No division by $x$ occurs in (9.10), and $M$ need not be squarefree, odd or prime to $x$. For $\epsilon=+1$ this is the sum identity; for $\epsilon=-1$ the difference identity.

Lemma 9.8.

Let $K_{\rm sv}\geq 1$ and $\theta>0$. Let $M\leq Y^{K_{\rm sv}}$ be a positive integer and

$$\mathcal{P}_{M}=\{p\ \text{prime}:\ p\equiv 1\ (\mathrm{mod}\ 3),\ Y^{\theta}\leq p\leq 2Y^{\theta},\ p\nmid M\}.$$

For $p\in\mathcal{P}_{M}$ fix a character $\chi_{p}\bmod p$ of exact order $3$. Let $(\varpi_{\iota},U_{\iota},V_{\iota},n_{\iota})_{\iota\in\mathcal{I}}$ be a finite family with $\varpi_{\iota}\geq 0$ and nonzero integers $U_{\iota},V_{\iota},n_{\iota}$ satisfying $|U_{\iota}V_{\iota}n_{\iota}|\leq Y^{K_{\rm sv}}$. If $Y\geq Y_{\rm sv}(K_{\rm sv},\theta)$, then $|\mathcal{P}_{M}|\geq Y^{\theta}/(3\theta\log Y)$ and

(9.11) $$\sum_{\iota:\,n_{\iota}\in\mathrm{Cub}}\varpi_{\iota}\leq\frac{4}{|\mathcal{P}_{M}|}\sum_{\iota}\varpi_{\iota}+\frac{4}{|\mathcal{P}_{M}|^{2}}\sum_{\begin{subarray}{c}\mathfrak{p}_{1},\mathfrak{p}_{2}\in\mathcal{P}_{M}\\ \mathfrak{p}_{1}\neq\mathfrak{p}_{2}\end{subarray}}\Bigl{|}\sum_{\iota}\varpi_{\iota}\,\mathbf{1}_{(\mathfrak{p}_{1}\mathfrak{p}_{2},U_{\iota}V_{\iota})=1}\,\chi_{\mathfrak{p}_{1}}(n_{\iota})\overline{\chi_{\mathfrak{p}_{2}}(n_{\iota})}\Bigr{|},$$

where $\mathrm{Cub}=\{m^{3}:m\in\mathbb{Z}\}$ is the set of integer cubes.

Proof.

By the prime number theorem in progressions modulo $3$,

$$\#\{p\in[Y^{\theta},2Y^{\theta}]:p\equiv 1\pmod{3}\}\geq\frac{Y^{\theta}}{2.5\,\theta\log Y}$$

for large $Y$. At most $K_{\rm sv}/\theta$ of them divide $M$. This gives the bound for $|\mathcal{P}_{M}|$. For $\iota\in\mathcal{I}$ put

$$\mathcal{Z}_{\iota}=\sum_{\begin{subarray}{c}p\in\mathcal{P}_{M}\\ p\nmid U_{\iota}V_{\iota}n_{\iota}\end{subarray}}\chi_{p}(n_{\iota}).$$

Since $0<|U_{\iota}V_{\iota}n_{\iota}|\leq Y^{K_{\rm sv}}$, at most $K_{\rm sv}/\theta$ primes of $\mathcal{P}_{M}$ divide $U_{\iota}V_{\iota}n_{\iota}$. If $n_{\iota}=m^{3}$ and $p\nmid n_{\iota}$, then $\chi_{p}(n_{\iota})=\chi_{p}(m)^{3}=1$. So $n_{\iota}\in\mathrm{Cub}$ gives $\mathcal{Z}_{\iota}\geq|\mathcal{P}_{M}|-K_{\rm sv}/\theta\geq|\mathcal{P}_{M}|/2$ for large $Y$. Hence

$$\mathbf{1}_{n_{\iota}\in\mathrm{Cub}}\leq\frac{4|\mathcal{Z}_{\iota}|^{2}}{|\mathcal{P}_{M}|^{2}}\qquad(\iota\in\mathcal{I}).$$

Expand $|\mathcal{Z}_{\iota}|^{2}$. The diagonal terms $\mathfrak{p}_{1}=\mathfrak{p}_{2}$ equal $1$, and there are at most $|\mathcal{P}_{M}|$ of them. For $\mathfrak{p}_{1}\neq\mathfrak{p}_{2}$, the conditions $\mathfrak{p}_{1},\mathfrak{p}_{2}\nmid n_{\iota}$ may be dropped, because $\chi_{\mathfrak{p}_{1}}(n_{\iota})=0$ when $\mathfrak{p}_{1}\mid n_{\iota}$. Multiply by $\varpi_{\iota}$, sum over $\iota\in\mathcal{I}$, and use the triangle inequality in $(\mathfrak{p}_{1},\mathfrak{p}_{2})$. ∎

9.3. Descriptors and the master estimate

A slot is a pair $(s,j)$ with $s\in\{u,v\}$ and $1\leq j\leq 6$. Its mass is $s_{s,j}$.

Definition 9.9.

A descriptor is a triple $\mathfrak{D}=(\sigma,\mathcal{G},\mathcal{U})$. Here $\sigma$ is a powered side; $\mathcal{G}$ is a set of groups, each of the form $g_{s}=\{(s,1),(s,2)\}$ with $s\in\{u,v\}$; $\mathcal{U}$ is a set of singleton slots disjoint from $\bigcup\mathcal{G}$; and $|\mathcal{G}|+|\mathcal{U}|=4$. Its retained set, retained mass, grouped lengths and generic exponent are

(9.12) $$J=\mathcal{U}\cup\bigcup\mathcal{G},\qquad P_{J}=\sum_{(s,j)\in J}s_{s,j},\qquad\mathcal{L}_{g_{s}}=s_{s,1}+2s_{s,2},\qquad E_{\mathfrak{D}}=\mathcal{C}_{\sigma}+R_{\sigma}-\tfrac{1}{2}P_{J}.$$

Write $\widehat{\mathcal{U}}=\{\{(s,j)\}:(s,j)\in\mathcal{U}\}$ and $\mathcal{F}_{\mathfrak{D}}=\mathcal{G}\cup\widehat{\mathcal{U}}$ for the four analytic factors.

So $|J|=4$, $5$ or $6$. There are always four analytic factors, one per group and one per singleton. Aggregate tails are never slots. $\mathcal{G}=\emptyset$ is ordinary $\mathrm{POW3}$.

Proposition 9.10.

Let $\mathfrak{D}$ be a descriptor and $\theta>0$ with

(9.13) $$W_{\sigma}+2\theta\geq 2\mathcal{L}_{g}\qquad(g\in\mathcal{G}).$$

Then

(9.14) $$D\leq\max\bigl{(}E_{\mathfrak{D}}+\theta,\ R_{\sigma}-\theta\bigr{)}+o(1).$$

Proof.

Write $C=\mathcal{C}_{\sigma}$, $W=W_{\sigma}$, $R=R_{\sigma}$ and $\mathfrak{r}_{s,j}$, $S_{s,j}$ for the roots and sizes of the represented sides.

Step 1. Outer configurations. An outer configuration $\mathfrak{o}$ consists of the labels of $M$ and all roots $\mathfrak{r}_{s,j}$ $(s\in\{u,v\},\ 1\leq j\leq d,\ (s,j)\notin J)$. By Lemma 9.1(i) and $\#\{\mathfrak{r}\sim S\}=S$,

(9.15) $$\#\{\mathfrak{o}\}\leq Y^{C}\prod_{(s,j)\notin J}S_{s,j}=Y^{C+R-P_{J}}.$$

Fix $\mathfrak{o}$. For $(s,j)\in J$ write $\mathfrak{r}_{s,j}=\mathfrak{u}_{s,j}$ and $\mathbf{u}=(\mathfrak{u}_{s,j})_{(s,j)\in J}$. Then

(9.16) $$n_{u}=U_{\mathfrak{o}}\prod_{(u,j)\in J}\mathfrak{u}_{u,j}^{\,j},\qquad n_{v}=V_{\mathfrak{o}}\prod_{(v,j)\in J}\mathfrak{u}_{v,j}^{\,j},$$

with $U_{\mathfrak{o}},V_{\mathfrak{o}}$ fixed. Write $U(\mathbf{u}),V(\mathbf{u})$ for the right sides. Given $\mathfrak{o}$ and $\mathbf{u}$, (9.2) fixes $n_{\sigma}=V+\epsilon_{\rm pw}U$ and (9.3) fixes $x=(n_{\sigma}/M)^{1/3}$. By Lemma 4.3, $\mathfrak{r}_{\sigma,3}\mathfrak{r}_{\sigma,6}^{2}=x/(\mathfrak{r}_{\sigma,4}\mathfrak{r}_{\sigma,5})$ has $Y^{o(1)}$ solutions. Pairwise coprimality of the sides gives $(M,UV)=1$. Hence

(9.17) $$\begin{gathered}\mathcal{B}_{d}\leq Y^{o(1)}\sum_{\mathfrak{o}}N(\mathfrak{o}),\\ N(\mathfrak{o})=\#\Bigl{\{}\mathbf{u}:\ \begin{aligned} &\mathfrak{u}_{s,j}\sim S_{s,j},\ (M,UV)=1,\ M\mid V+\epsilon_{\rm pw}U,\\ &(V+\epsilon_{\rm pw}U)/M\ \text{is a positive integer cube}\end{aligned}\Bigr{\}}.\end{gathered}$$

Step 2. Positive ambientization. For $\mathbf{u}\in\mathbb{N}^{J}$ put

(9.18) $$\varpi_{\mathfrak{o}}(\mathbf{u}) =\prod_{(s,j)\in J}w\bigl{(}\mathfrak{u}_{s,j}/S_{s,j}\bigr{)}$$

$$\quad\cdot\mathbf{1}_{(M,UV)=1}\,\mathbf{1}_{V+\epsilon_{\rm pw}U\neq 0}\,\mathbf{1}_{M\mid V+\epsilon_{\rm pw}U},$$

$$n(\mathbf{u}) =\frac{V+\epsilon_{\rm pw}U}{M}.$$

Since $w\geq 0$ and $w=1$ on $[1,2)$, pointwise

(9.19) $$N(\mathfrak{o})\leq\sum_{\mathbf{u}\in\mathbb{N}^{J}}\varpi_{\mathfrak{o}}(\mathbf{u})\,\mathbf{1}_{n(\mathbf{u})\in\mathrm{Cub}}.$$

We drop the condition $\gcd(U,V)=1$ and the sharp dyadic windows of the retained roots, and keep $(M,UV)=1$. We also weaken the positive-cube condition to: $n(\mathbf{u})$ is a nonzero integer cube. These changes only increase the count. We retain $M$, its labels, every unretained represented root and every tail in $\mathfrak{o}$. On the support, $\mathfrak{u}_{s,j}\leq 4S_{s,j}$, so $|UVn|\leq Y^{8}$ for large $Y$.

Step 3. Sieve. Apply Lemma 9.8 with $K_{\rm sv}=8$ to the family $(\varpi_{\mathfrak{o}}(\mathbf{u}),U,V,n(\mathbf{u}))$ restricted to its support. Then

(9.20) $$\begin{gathered}N(\mathfrak{o})\leq\frac{4}{|\mathcal{P}_{M}|}\sum_{\mathbf{u}}\varpi_{\mathfrak{o}}(\mathbf{u})+4\max_{\begin{subarray}{c}\mathfrak{p}_{1},\mathfrak{p}_{2}\in\mathcal{P}_{M}\\ \mathfrak{p}_{1}\neq\mathfrak{p}_{2}\end{subarray}}|\mathcal{E}_{\mathfrak{p}_{1},\mathfrak{p}_{2}}(\mathfrak{o})|,\\ \mathcal{E}_{\mathfrak{p}_{1},\mathfrak{p}_{2}}(\mathfrak{o})=\sum_{\mathbf{u}}\varpi_{\mathfrak{o}}(\mathbf{u})\mathbf{1}_{(\mathfrak{p}_{1}\mathfrak{p}_{2},UV)=1}\,\xi(n(\mathbf{u})),\end{gathered}$$

with $\xi=\chi_{\mathfrak{p}_{1}}\bar{\chi}_{\mathfrak{p}_{2}}$, a character modulo $\mathfrak{p}_{1}\mathfrak{p}_{2}$ whose components are $\chi_{\mathfrak{p}_{1}}$ and $\bar{\chi}_{\mathfrak{p}_{2}}$, both nonprincipal. Also $|\mathcal{P}_{M}|^{-1}\leq Y^{-\theta+o(1)}$.

Step 4. Diagonal. Split $\mathfrak{o}=(\mathfrak{m},\mathfrak{y})$ into the labels $\mathfrak{m}$ of $M$ and the represented part $\mathfrak{y}$. For fixed $(\mathfrak{y},\mathbf{u})$ the integers $U,V$ are fixed and $V+\epsilon_{\rm pw}U\neq 0$ on the support. Then $M\mid V+\epsilon_{\rm pw}U$ leaves at most $\operatorname{div}(|V+\epsilon_{\rm pw}U|)$ values of $M$, each with $Y^{o(1)}$ label tuples by Lemma 9.1(iv). Hence

$$\sum_{\mathfrak{o}}\sum_{\mathbf{u}}\varpi_{\mathfrak{o}}(\mathbf{u}) \leq Y^{o(1)}\sum_{\mathfrak{y}}\ \prod_{(s,j)\in J}\sum_{\mathfrak{u}\geq 1}w(\mathfrak{u}/S_{s,j})$$

$$\leq Y^{o(1)}\,Y^{R-P_{J}}\prod_{(s,j)\in J}4S_{s,j}=Y^{R+o(1)}.$$

The diagonal part of (9.20), summed over $\mathfrak{o}$, is therefore $\leq Y^{R-\theta+o(1)}$. Summing first over $\mathfrak{m}$ would give $Y^{C+R-\theta}$; the divisor recovery removes $C$.

Step 5. Fourier expansion. Fix $\mathfrak{o}$ and $\mathfrak{p}_{1}\neq\mathfrak{p}_{2}$ in $\mathcal{P}_{M}$. Put $Q=M\mathfrak{p}_{1}\mathfrak{p}_{2}$. Since $\xi(0)=0$ and $(M,UV)=1$ is in $\varpi_{\mathfrak{o}}$,

$$\mathcal{E}_{\mathfrak{p}_{1},\mathfrak{p}_{2}}(\mathfrak{o})=\sum_{\mathbf{u}}\prod_{(s,j)\in J}w\bigl{(}\mathfrak{u}_{s,j}/S_{s,j}\bigr{)}\,\mathbf{1}_{(UV,Q)=1}\,\mathbf{1}_{M\mid V+\epsilon_{\rm pw}U}\,\xi\Bigl{(}\frac{V+\epsilon_{\rm pw}U}{M}\Bigr{)}.$$

Apply Lemma 9.7. Dirichlet characters are completely multiplicative and vanish on nonunits, and $\mathbf{u}$ runs over a product set. So

(9.21) $$\mathcal{E}_{\mathfrak{p}_{1},\mathfrak{p}_{2}}(\mathfrak{o})=\frac{\overline{\xi(M)}}{\varphi(Q)}\sum_{\alpha\bmod Q}c_{\epsilon_{\rm pw}}(\alpha)\,\alpha(U_{\mathfrak{o}})\,(\tilde{\xi}\bar{\alpha})(V_{\mathfrak{o}})\prod_{f\in\mathcal{F}_{\mathfrak{D}}}\Phi_{f}\bigl{(}\gamma_{f}(\alpha)\bigr{)},$$

where $\gamma_{f}(\alpha)=\alpha$ if $f$ lies on side $u$ and $\gamma_{f}(\alpha)=\tilde{\xi}\bar{\alpha}$ if $f$ lies on side $v$, and

$$\Phi_{\{(s,j)\}}(\chi)=F_{S_{s,j}}(\chi^{j}),\qquad\Phi_{g_{s}}(\chi)=G_{s}(\chi)=F_{S_{s,1}}(\chi)\,F_{S_{s,2}}(\chi^{2}).$$

For the group this uses $\chi(\mathfrak{u}_{1})\chi(\mathfrak{u}_{2})^{2}=\chi(\mathfrak{u}_{1}\mathfrak{u}_{2}^{2})$. By (9.9),

(9.22) $$|\mathcal{E}_{\mathfrak{p}_{1},\mathfrak{p}_{2}}(\mathfrak{o})|\leq\frac{\sqrt{\mathfrak{p}_{1}\mathfrak{p}_{2}}}{\varphi(Q)}\sum_{\alpha\bmod Q}\ \prod_{f\in\mathcal{F}_{\mathfrak{D}}}\bigl{|}\Phi_{f}(\gamma_{f}(\alpha))\bigr{|}.$$

This is one family of $\varphi(Q)$ modes. Each $\gamma_{f}$ is a bijection of the character group modulo $Q$.

Step 6. Torsion modes. Here $Q=M\mathfrak{p}_{1}\mathfrak{p}_{2}$, as in Step 5. Let $\mathcal{T}_{\rm tor}=\{\alpha:\ \gamma_{f}(\alpha)^{j}=\chi_{0}\ \text{for some}\ f=\{(s,j)\}\in\widehat{\mathcal{U}}\}$. The character group modulo $Q$ is isomorphic to $(\mathbb{Z}/Q)^{\times}$, whose $j$-torsion has at most $j^{\omega(Q)+1}$ elements. So $|\mathcal{T}_{\rm tor}|\leq 4\cdot 6^{\omega(Q)+1}=Y^{o(1)}$, as $Q\leq Y^{2}\cdot 4Y^{2\theta}=Y^{O_{d,\theta}(1)}$. Trivially $|\Phi_{f}|\leq\prod_{(s,j)\in f}4S_{s,j}$. By Lemma 9.1(ii), $\varphi(Q)\geq Q\,Y^{-o(1)}\geq Y^{W+2\theta-o(1)}$. The modes in $\mathcal{T}_{\rm tor}$ contribute to (9.22) at most

$$\frac{2Y^{\theta}}{Y^{W+2\theta-o(1)}}\,Y^{o(1)}\,4^{6}Y^{P_{J}}=Y^{P_{J}-W-\theta+o(1)}.$$

Sum over $\mathfrak{o}$ with (9.15). By Lemma 9.1(iii) the total is

$$Y^{C+R-W-\theta+o(1)}\leq Y^{R-\theta+o(1)}.$$

Step 7. Generic modes. By Hölder with four exponents $4$,

$$\sum_{\alpha\notin\mathcal{T}_{\rm tor}}\prod_{f\in\mathcal{F}_{\mathfrak{D}}}\bigl{|}\Phi_{f}(\gamma_{f}(\alpha))\bigr{|}\leq\prod_{f\in\mathcal{F}_{\mathfrak{D}}}\Bigl{(}\sum_{\alpha\notin\mathcal{T}_{\rm tor}}\bigl{|}\Phi_{f}(\gamma_{f}(\alpha))\bigr{|}^{4}\Bigr{)}^{1/4}.$$

Singleton $f=\{(s,j)\}$: for $\alpha\notin\mathcal{T}_{\rm tor}$ the character $\gamma_{f}(\alpha)^{j}$ is nonprincipal. The map $\alpha\mapsto\gamma_{f}(\alpha)^{j}$ has fibres of size $\leq 6^{\omega(Q)+1}$. Lemma 9.4 gives

$$\sum_{\alpha\notin\mathcal{T}_{\rm tor}}|\Phi_{f}(\gamma_{f}(\alpha))|^{4}\leq 6^{\omega(Q)+1}\sum_{\chi\neq\chi_{0}}|F_{S_{s,j}}(\chi)|^{4}\leq\varphi(Q)\,S_{s,j}^{\,2}\,Y^{o(1)}.$$

Here $Q/\varphi(Q)=Y^{o(1)}$, since $Q\leq Y^{O_{d,\theta}(1)}$. Group $f=g_{s}$: $\gamma_{f}$ is a bijection, so by Lemma 9.5

$$\sum_{\alpha}|G_{s}(\gamma_{f}(\alpha))|^{4}=\sum_{\chi\bmod Q}|G_{s}(\chi)|^{4}\leq\varphi(Q)\,(S_{s,1}S_{s,2})^{2}\,Y^{o(1)}\Bigl{(}1+\frac{4^{6}Y^{2\mathcal{L}_{g_{s}}}}{Q}\Bigr{)}.$$

Here $Q\geq MY^{2\theta}\geq Y^{W+2\theta}\geq Y^{2\mathcal{L}_{g_{s}}}$ by Lemma 9.1(ii) and (9.13). So the bracket is $\leq 1+4^{6}$. The guard is closed: equality in (9.13) still leaves a bounded number of shifts $m^{\prime}\equiv m\pmod{Q}$. Multiply the four bounds:

$$\sum_{\alpha\notin\mathcal{T}_{\rm tor}}\prod_{f\in\mathcal{F}_{\mathfrak{D}}}\bigl{|}\Phi_{f}(\gamma_{f}(\alpha))\bigr{|}\leq\varphi(Q)\,Y^{o(1)}\prod_{(s,j)\in J}S_{s,j}^{1/2}=\varphi(Q)\,Y^{P_{J}/2+o(1)}.$$

In (9.22) the factor $\varphi(Q)$ cancels. Since $\sqrt{\mathfrak{p}_{1}\mathfrak{p}_{2}}\leq 2Y^{\theta}$, the generic modes contribute $Y^{\theta+P_{J}/2+o(1)}$. Sum over $\mathfrak{o}$ with (9.15):

$$Y^{C+R-P_{J}+P_{J}/2+\theta+o(1)}=Y^{E_{\mathfrak{D}}+\theta+o(1)}.$$

Step 8. Assembly. By (9.17), (9.19), (9.20) and Steps 4, 6, 7,

$$\mathcal{B}_{d}\leq Y^{o(1)}\bigl{(}Y^{R-\theta}+Y^{R-\theta}+Y^{E_{\mathfrak{D}}+\theta}\bigr{)}.$$

Take $\log_{Y}$. ∎

The proof uses four fourth moments in every case. With two groups,

$$\sum_{\alpha}|G_{s}G_{s^{\prime}}\Phi_{f}\Phi_{f^{\prime}}|\leq\|G_{s}\|_{4}\|G_{s^{\prime}}\|_{4}\|\Phi_{f}\|_{4}\|\Phi_{f^{\prime}}\|_{4},$$

over the one mode family; no mixed correlation and no eighth moment enter. Both guards are imposed at the same $\theta$.

9.4. Elimination of $\theta$

Lemma 9.11.

Let $0\leq k\leq 2$, let $E,R,\Gamma_{1},\dots,\Gamma_{k}$ be real, and let $0<\rho_{0}\leq 1$. Put

$$\theta^{*}=\max\bigl{(}0,\tfrac{1}{2}(R-E),\Gamma_{1},\dots,\Gamma_{k}\bigr{)},\qquad\Theta(\rho_{0})=\{m\rho_{0}:\ m\in\mathbb{Z},\ 1\leq m\leq 4/\rho_{0}\},$$

and assume $\theta^{*}\leq 3$. Some $\theta\in\Theta(\rho_{0})$ satisfies $\theta\geq\Gamma_{i}$ for all $i$ and

$$\max(E+\theta,R-\theta)\leq\max\bigl{(}E,\tfrac{1}{2}(E+R),E+\Gamma_{1},\dots,E+\Gamma_{k}\bigr{)}+\rho_{0}.$$

Proof.

Let $\theta$ be the least element of $\Theta(\rho_{0})$ with $\theta\geq\theta^{*}$. It exists since $\max\Theta(\rho_{0})>4-\rho_{0}\geq 3$. Then $\theta^{*}\leq\theta\leq\theta^{*}+\rho_{0}$. As $\theta\geq\frac{1}{2}(R-E)$, $R-\theta\leq E+\theta$. So the left side is $E+\theta\leq E+\theta^{*}+\rho_{0}$, and $E+\theta^{*}$ is the displayed maximum. ∎

Proposition 9.12.

Let $0<\rho_{0}\leq 1$. There is $Y_{\rm el}=Y_{\rm el}(\varepsilon_{0},d,\rho_{0})$ such that for $Y\geq Y_{\rm el}$ and every descriptor $\mathfrak{D}$:

1. if $\mathcal{G}=\emptyset$,

   (9.23) $$D\leq E_{\mathfrak{D}}+2\rho_{0}\quad\text{or}\quad D\leq\tfrac{1}{2}(E_{\mathfrak{D}}+R_{\sigma})+2\rho_{0};$$

2. if $\mathcal{G}=\{g\}$,

   (9.24) $$D\leq E_{\mathfrak{D}}+2\rho_{0}\quad\text{or}\quad D\leq\tfrac{1}{2}(E_{\mathfrak{D}}+R_{\sigma})+2\rho_{0}\quad\text{or}\quad D\leq E_{\mathfrak{D}}+\mathcal{L}_{g}-\tfrac{1}{2}W_{\sigma}+2\rho_{0};$$

3. if $\mathcal{G}=\{g,g^{\prime}\}$,

   (9.25) $$\begin{gathered}D\leq E_{\mathfrak{D}}+2\rho_{0}\quad\text{or}\quad D\leq\tfrac{1}{2}(E_{\mathfrak{D}}+R_{\sigma})+2\rho_{0}\quad\text{or}\\ D\leq E_{\mathfrak{D}}+\mathcal{L}_{g}-\tfrac{1}{2}W_{\sigma}+2\rho_{0}\quad\text{or}\quad D\leq E_{\mathfrak{D}}+\mathcal{L}_{g^{\prime}}-\tfrac{1}{2}W_{\sigma}+2\rho_{0}.\end{gathered}$$

Here $E_{\mathfrak{D}}$, $P_{J}$, $\mathcal{L}_{g}$ are as in (9.12) and $\mathcal{C}_{\sigma}$, $W_{\sigma}$, $R_{\sigma}$ as in (9.4).

Proof.

Write $\mathcal{G}=\{g^{(1)},\dots,g^{(k)}\}$ and take $\Gamma_{i}=\mathcal{L}_{g^{(i)}}-\frac{1}{2}W_{\sigma}$ in Lemma 9.11. Its hypothesis holds: $\mathcal{C}_{\sigma}\geq 0$ and $P_{J}\leq R_{\sigma}$ give $E_{\mathfrak{D}}\geq\frac{1}{2}R_{\sigma}\geq 0$. Also $R_{\sigma}\leq 2$, since $r_{s}\leq V_{s}\leq 1$ for each represented side. Thus $\frac{1}{2}(R_{\sigma}-E_{\mathfrak{D}})\leq\frac{1}{4}R_{\sigma}\leq\frac{1}{2}$; and $\Gamma_{i}\leq\mathcal{L}_{g^{(i)}}\leq V_{s}\leq 1$. The chosen $\theta\in\Theta(\rho_{0})$ satisfies (9.13). Proposition 9.10 at this $\theta$ gives

$$D\leq\max\bigl{(}E_{\mathfrak{D}},\tfrac{1}{2}(E_{\mathfrak{D}}+R_{\sigma}),E_{\mathfrak{D}}+\Gamma_{1},\dots,E_{\mathfrak{D}}+\Gamma_{k}\bigr{)}+\rho_{0}+o(1).$$

The grid $\Theta(\rho_{0})$ and the set of descriptors are finite. So the $o(1)$ is $\leq\rho_{0}$ for $Y\geq Y_{\rm el}$. Since $E_{\mathfrak{D}}+\max(0,\Gamma_{i})=\max(E_{\mathfrak{D}},E_{\mathfrak{D}}+\Gamma_{i})$, the maximum is the largest arm. A bound by a maximum is the stated disjunction. ∎

Each clause is used together with the direct row (2.11), $D\leq R_{\sigma}$. So (a) reads $D\leq\min\bigl{(}R_{\sigma},\max(E_{\mathfrak{D}},\tfrac{1}{2}(E_{\mathfrak{D}}+R_{\sigma}))\bigr{)}$ up to the relaxation. A clause may not be replaced by the conjunction of its arms.

9.5. The installed descriptor families

Proposition 9.12 holds for every descriptor. The system of Section 11 installs the following finite families. For brevity, $s_{j}$ in a descriptor denotes the slot $(s,j)$; its mass is always $s_{s,j}$.

1. $\mathcal{G}=\emptyset$, $\mathcal{U}=J$ any four of the twelve slots $u_{1},\dots,u_{6},v_{1},\dots,v_{6}$. For $\sigma=b$ and $\sigma=c$ all $\binom{12}{4}=495$ sets are installed. For $\sigma=a$, install the $486$ sets not containing $\{b_{1},c_{1},c_{4}\}$. The nine omitted sets are valid rows, but were not installed in the finite system. Including them would remove the displayed witness; the optimum of the enlarged system is not computed here.

2. $\sigma=c$, $y\in\{a,b\}$, $z$ the other represented side, $\mathcal{G}=\{g_{y}\}$, $\mathcal{U}=\{y_{4},z_{1},z_{4}\}$. Two clauses.

3. $\sigma\in\{a,b\}$, $z$ the represented side other than $c$, $\mathcal{G}=\{g_{c}\}$, $\mathcal{U}$ any three of $c_{3},c_{4},c_{5},c_{6},z_{1},\dots,z_{6}$. In total $2\binom{10}{3}=240$ clauses.

4. $\sigma\in\{a,b\}$, $z$ as before, $\mathcal{G}=\{g_{c},g_{z}\}$, $\mathcal{U}$ any two of $z_{3},z_{4},z_{5},z_{6},c_{3},c_{4},c_{5},c_{6}$. In total $2\binom{8}{2}=56$ clauses.

For these families, (9.4) and (9.12) read as follows. In $\mathrm{GROUP12c}(y)$,

$$\begin{gathered}C=c-s_{c,3}-s_{c,6},\qquad R=a+b,\qquad P_{J}=s_{y,1}+s_{y,2}+s_{y,4}+s_{z,1}+s_{z,4},\\ W=v_{c}+s_{c,1}+2s_{c,2}+s_{c,4}+2s_{c,5},\qquad\mathcal{L}_{g_{y}}=s_{y,1}+2s_{y,2}.\end{gathered}$$

In $\mathrm{GROUP12ab}(\sigma)$ and $\mathrm{GROUP1212ab}(\sigma)$, $C=\sigma-s_{\sigma,3}-s_{\sigma,6}$, $W=v_{\sigma}+s_{\sigma,1}+2s_{\sigma,2}+s_{\sigma,4}+2s_{\sigma,5}$, $R=r_{z}+r_{c}$, $\mathcal{L}_{g_{c}}=s_{c,1}+2s_{c,2}$, $\mathcal{L}_{g_{z}}=s_{z,1}+2s_{z,2}$. Here a bare side letter is its root mass $r_{s}=\sum_{j\leq d}s_{s,j}$ from (9.1).

All clauses of this section carry the one relaxation $2\rho_{0}$; we take $\rho_{0}=\varepsilon_{0}/2$. Table 12.1 records it.

10. Moment rows

10.1. Setting

Fix $\varepsilon_{0}\leq 4/7$ and $d=d(\varepsilon_{0})$ as in Section 3.1. Work in a nonempty box admissible in (2.3) at scale $Y$, and put $D=\log_{Y}\mathcal{B}_{d}$. Fix $\sigma\in\{a,b,c\}$, and let $(y,z)$ be the other sides in alphabetical order. Choose nonempty $T\subseteq\{1,\dots,6,\mathrm{tail}\}$, with $\kappa_{T},\Omega_{T}$ as in (5.1). Write $\mathfrak{m}_{i}$, $\mathfrak{y}_{i}$, $\mathfrak{z}_{i}$ for the roots of the $\sigma$-, $y$- and $z$-sides. Let $M$ be the modulus (5.5), and

$$\epsilon_{\rm mo}=-1\ (\sigma=c),\qquad\epsilon_{\rm mo}=+1\ (\sigma\neq c).$$

Then the side values satisfy $n_{y}\equiv\epsilon_{\rm mo}\,n_{z}\pmod{M}$, as $M\mid n_{\sigma}$ and $n_{a}+n_{b}=n_{c}$. Here $M$ is the cut modulus of (5.5); the cubic-sieve section uses its own local coefficient $M$. The function $\varphi$ denotes Euler’s totient.

A block is a pair $\beta=(s,j)$, where $s\in\{y,z\}$ and $1\leq j\leq d$. Its root $x_{\beta}$ is $\mathfrak{y}_{j}$ or $\mathfrak{z}_{j}$. Let $S_{\beta}$ be its dyadic size, and put $j_{\beta}=j$ and $h_{\beta}=\log_{Y}S_{\beta}$. Thus $h_{\beta}$ is $y_{j}$ or $z_{j}$; it is unrelated to $h_{d}=d(d+1)/2$. The block is ordinary when $j\leq 6$. For a set $\mathcal{H}$ of blocks put $h_{\mathcal{H}}=\sum_{\beta\in\mathcal{H}}h_{\beta}$, and let $\mathcal{H}_{y},\mathcal{H}_{z}$ be its blocks on $y$ and $z$. Put

(10.1) $$P_{\rm mo}=\sum_{\beta}h_{\beta},$$

the sum over all $2d$ blocks: the total root mass of the sides $y$ and $z$. Tails are included in $P_{\rm mo}$.

All $o(1)$ terms below tend to $0$ as $Y\to\infty$ for fixed $\varepsilon_{0}$ and $d$ (and $\delta$ in Proposition 10.9). They are uniform in the box, in $(\sigma,T)$ and in $\mathcal{H}$.

Lemma 10.1.

For $Y\geq Y_{0}$, $Y^{\Omega_{T}}\leq M\leq Y^{2}$ and $\varphi(M)\geq M/\operatorname{div}(M)\geq Y^{\Omega_{T}-o(1)}$. Every root $x_{\beta}$ is prime to $M$. Moreover $\Omega_{T}\leq 1$ and $h_{\beta}\leq 1/j_{\beta}$.

Proof.

The lower bound is (5.6) at scale $Y$. $M$ divides $\prod_{j}\mathfrak{m}_{j}^{\,j}<2^{d(d+1)/2}Y^{V_{\sigma}}\leq Y^{2}$ for large $Y$, by (2.4). Next $\varphi(M)=M\prod_{p\mid M}(1-1/p)\geq M2^{-\omega(M)}\geq M/\operatorname{div}(M)$, and $\operatorname{div}(M)=Y^{o(1)}$ for $M\leq Y^{2}$. Coprimality is Lemma 2.1. Finally $\Omega_{T}\leq V_{\sigma}\leq 1$ and $j_{\beta}h_{\beta}\leq V_{s}\leq 1$ by (2.4). ∎

10.2. Reduction and orthogonality

For a set $\mathcal{H}$ of blocks, a unit $K$ modulo $M$ and a character $\psi$ modulo $M$ put

(10.2) $$\begin{gathered}\Sigma_{\beta}(\psi)=\sum_{S_{\beta}\leq x<2S_{\beta}}\psi(x),\\ N_{\mathcal{H}}(K)=\#\Bigl{\{}(x_{\beta})_{\beta\in\mathcal{H}}:\ \begin{aligned} &S_{\beta}\leq x_{\beta}<2S_{\beta},\ (x_{\beta},M)=1,\\ &\textstyle\prod_{\beta\in\mathcal{H}_{y}}x_{\beta}^{\,j_{\beta}}\equiv K\prod_{\beta\in\mathcal{H}_{z}}x_{\beta}^{\,j_{\beta}}\ (\mathrm{mod}\ M)\end{aligned}\Bigr{\}}.\end{gathered}$$

Lemma 10.2.

For every set $\mathcal{H}$ of blocks,

$$\mathcal{B}_{d}\leq Y^{\kappa_{T}+P_{\rm mo}-h_{\mathcal{H}}+o(1)}\max_{K}N_{\mathcal{H}}(K),$$

the maximum over the outer data fixed in the proof and over units $K$ modulo the resulting $M$.

Proof.

Enumeration. Enumerate the roots of $\sigma$ selected by $T$. Its individual tail roots are among them exactly when $\mathrm{tail}\in T$. Also enumerate the roots of all blocks outside $\mathcal{H}$, on $y$ and $z$. A tail block in $\mathcal{H}$ remains unenumerated. As $\#\{x:S\leq x<2S\}=S$, there are $Y^{\kappa_{T}}\cdot Y^{P_{\rm mo}-h_{\mathcal{H}}}$ choices. Fix one. Then $M$ is fixed.

Congruence. Write $n_{y}=\Pi_{y}\prod_{\mathcal{H}_{y}}x_{\beta}^{\,j_{\beta}}$ and $n_{z}=\Pi_{z}\prod_{\mathcal{H}_{z}}x_{\beta}^{\,j_{\beta}}$. The coefficients $n_{y,0},n_{z,0}$ are fixed by the box, so $\Pi_{y},\Pi_{z}$ are fixed. They are units modulo $M$ by Lemmas 10.1 and 2.1. So $n_{y}\equiv\epsilon_{\rm mo}n_{z}$ gives the congruence of (10.2) with $K\equiv\epsilon_{\rm mo}\Pi_{z}\Pi_{y}^{-1}$. The sign $\epsilon_{\rm mo}$ equals $\epsilon_{\rm cut}$ in (5.9). The roots $x_{\beta}$ are units. So the remaining tuples number at most $N_{\mathcal{H}}(K)$.

Recovery. Given all roots of $y$ and $z$, the side values $n_{y},n_{z}$ are fixed, hence $n_{\sigma}$. Divide by $n_{\sigma,0}$ and by the selected part. The quotient $Q_{\sigma}=\prod_{i\in[6]\setminus T}\mathfrak{m}_{i}^{\,i}\cdot(\prod_{j\geq 7}\mathfrak{m}_{j}^{\,j})^{1-\mathbf{1}_{\mathrm{tail}\in T}}<2^{d^{2}}Y$ determines the unselected roots of $\sigma$ up to $\operatorname{div}(Q_{\sigma})^{d-1}=Y^{o(1)}$ choices by Lemma 4.3. ∎

Lemma 10.3.

$$N_{\mathcal{H}}(K)=\frac{1}{\varphi(M)}\sum_{\chi\bmod M}\overline{\chi}(K)\prod_{\beta\in\mathcal{H}_{y}}\Sigma_{\beta}(\chi^{j_{\beta}})\prod_{\beta\in\mathcal{H}_{z}}\Sigma_{\beta}(\overline{\chi}^{\,j_{\beta}}).$$

Proof.

For units $g_{1},g_{2}$, $\varphi(M)^{-1}\sum_{\chi}\chi(g_{1})\overline{\chi}(g_{2})=\mathbf{1}_{g_{1}\equiv g_{2}}$. Take $g_{1}=\prod_{\mathcal{H}_{y}}x_{\beta}^{\,j_{\beta}}$, $g_{2}=K\prod_{\mathcal{H}_{z}}x_{\beta}^{\,j_{\beta}}$. Characters vanish on nonunits, so summing over all $x_{\beta}$ in the windows imposes $(x_{\beta},M)=1$. Expand by complete multiplicativity. ∎

10.3. Moment inputs

Lemma 10.4.

Let $j\geq 1$. Then $\#\{\chi\bmod M:\chi^{j}=\chi_{0}\}\leq(2j)^{\omega(M)}$, and every fibre of $\chi\mapsto\chi^{j}$ has at most $(2j)^{\omega(M)}$ elements. For $j\leq d$ and $M\leq Y^{2}$ this is $Y^{o(1)}$.

Proof.

The character group is isomorphic to $(\mathbb{Z}/M)^{\times}$, and the fibres of a homomorphism are cosets of its kernel. By the Chinese remainder theorem count $\eta^{j}=1$ locally. Odd $p^{e}$: cyclic, at most $\gcd(j,\varphi(p^{e}))\leq j$. $2^{e}$: the group is $1$, $C_{2}$ or $C_{2}\times C_{2^{e-2}}$, at most $\gcd(j,2)\gcd(j,2^{e-2})\leq 2j$. Finally $\omega(M)\ll\log M/\log\log M$. ∎

We use the 2009 author-preprint formulation of [4, Theorem 1]; the published article is listed in the bibliography. The displayed bound is meaningful for $m\geq 3$, where $\log\log m>0$. For $m=1,2$ the nonprincipal character set is empty, so those cases contribute zero.

Theorem B ([4, Theorem 1]).

For every integer $m\geq 3$ and integers $a,B$ with $B>0$ we have

$$\frac{1}{\varphi(m)}\sum_{\chi\neq\chi_{0}}\Bigl{|}\sum_{x=a+1}^{a+B}\chi(x)\Bigr{|}^{4}\ll 8^{\omega(m)}\operatorname{div}(m)(\log m)^{3}(\log\log m)^{7}B^{2}.$$

Here $\chi$ runs over all characters modulo $m$, including imprimitive characters. The published reference is J. Number Theory 130 (2010), no. 3, 767–785; the frozen source is the 2009 author preprint. The window $S\leq x<2S$ is $a=S-1$, $B=S$.

Lemma 10.5.

Let $r,S,M\in\mathbb{N}$ with $r\geq 1$, $S\geq 1$ and $S^{r}\leq M$. Then

$$\sum_{\chi\bmod M}\Bigl{|}\sum_{S\leq x<2S}\chi(x)\Bigr{|}^{2r}\leq(2^{r}+1)\,\varphi(M)\,S^{r}\max_{n\leq(2S)^{r}}\operatorname{div}(n)^{r-1}.$$

Proof.

Expand the $2r$-th power and apply orthogonality. The left side is $\varphi(M)$ times the number of $(\mathbf{x},\mathbf{x}^{\prime})\in[S,2S)^{2r}$ with all coordinates prime to $M$ and $x_{1}\cdots x_{r}\equiv x^{\prime}_{1}\cdots x^{\prime}_{r}\pmod{M}$. Fix $\mathbf{x}^{\prime}$: $S^{r}$ choices. Then $n=x_{1}\cdots x_{r}<(2S)^{r}\leq 2^{r}M$ lies in a fixed class modulo $M$: at most $2^{r}+1$ values. Each $n$ has at most $\operatorname{div}(n)^{r-1}$ factorizations by Lemma 4.3. ∎

Lemma 10.6.

Let $\beta$ be a block, $j=j_{\beta}$, $S=S_{\beta}$, and $\mathcal{E}_{j}=\{\chi\bmod M:\chi^{j}=\chi_{0}\}$.

1. $\displaystyle\sum_{\chi\notin\mathcal{E}_{j}}|\Sigma_{\beta}(\chi^{j})|^{4}\leq\varphi(M)\,S^{2}\,Y^{o(1)}$.

2. If $r_{\max}\in\mathbb{N}$, $1\leq r\leq r_{\max}$ and $S^{r}\leq M$, then $\displaystyle\sum_{\chi\bmod M}|\Sigma_{\beta}(\chi^{j})|^{2r}\leq\varphi(M)\,S^{r}\,Y^{o(1)}$, the $o(1)$ depending on $r_{\max}$.

Proof.

(i) For $\chi\notin\mathcal{E}_{j}$, $\psi=\chi^{j}$ is nonprincipal, and each $\psi$ has at most $(2j)^{\omega(M)}$ preimages (Lemma 10.4). So the sum is at most $(2j)^{\omega(M)}\sum_{\psi\neq\psi_{0}}|\Sigma_{\beta}(\psi)|^{4}$. For $M\leq 2$ this vanishes. For $M\geq 3$ apply Theorem B with $m=M$, $a=S-1$, $B=S$. Its factor is at most $\operatorname{div}(M)^{4}(2\log Y)^{10}=Y^{o(1)}$. (ii) The same fibre bound reduces to all $\psi$; apply Lemma 10.5. The total factor is $(2j)^{\omega(M)}(2^{r_{\max}}+1)\max_{n\leq(2S)^{r}}\operatorname{div}(n)^{r-1}$, which is $Y^{O_{d,r_{\max}}(1/\log\log Y)}$. ∎

Lemma 10.7.

Let $\mathcal{X}$ be a set of characters modulo $M$ and $\mathcal{H}$ a finite set. For $\beta\in\mathcal{H}$ let $f_{\beta}:\mathcal{X}\to\mathbb{C}$, $S_{\beta}\geq 1$, $C_{\rm H}\geq 1$ and integers $r_{\beta}\geq 1$ satisfy

$$|f_{\beta}|\leq S_{\beta},\qquad\sum_{\chi\in\mathcal{X}}|f_{\beta}(\chi)|^{2r_{\beta}}\leq C_{\rm H}\,\varphi(M)\,S_{\beta}^{\,r_{\beta}}.$$

Let $0\leq\vartheta_{\beta}\leq 1$ with $\sum_{\beta}\vartheta_{\beta}/(2r_{\beta})\leq 1$. Then

$$\frac{1}{\varphi(M)}\sum_{\chi\in\mathcal{X}}\prod_{\beta\in\mathcal{H}}|f_{\beta}(\chi)|\leq C_{\rm H}^{|\mathcal{H}|}\prod_{\beta\in\mathcal{H}}S_{\beta}^{\,1-\vartheta_{\beta}/2}.$$

Proof.

$|f_{\beta}|\leq S_{\beta}^{1-\vartheta_{\beta}}|f_{\beta}|^{\vartheta_{\beta}}$. Apply Hölder to the functions $|f_{\beta}|^{\vartheta_{\beta}}$ $(\vartheta_{\beta}>0)$ with exponents $2r_{\beta}/\vartheta_{\beta}$, and to the constant $1$ with the complementary exponent. With $|\mathcal{X}|\leq\varphi(M)$,

$$\sum_{\mathcal{X}}\prod_{\beta}|f_{\beta}|^{\vartheta_{\beta}} \leq\varphi(M)^{1-\sum\vartheta_{\beta}/(2r_{\beta})}$$

$$\quad\cdot\prod_{\beta}\bigl{(}C_{\rm H}\varphi(M)S_{\beta}^{\,r_{\beta}}\bigr{)}^{\vartheta_{\beta}/(2r_{\beta})}$$

$$\leq C_{\rm H}^{|\mathcal{H}|}\varphi(M)\prod_{\beta}S_{\beta}^{\,\vartheta_{\beta}/2}.$$

Multiply by $\prod_{\beta}S_{\beta}^{1-\vartheta_{\beta}}$. ∎

10.4. The rows

Proposition 10.8 (CS4).

Let $\mathcal{H}$ be a set of at most four blocks, in total over $y$ and $z$. Then

(10.3) $$D\leq\kappa_{T}+P_{\rm mo}-\min\Bigl{(}\Omega_{T},\frac{h_{\mathcal{H}}}{2}\Bigr{)}+o(1).$$

Proof.

If $\mathcal{H}=\emptyset$, then $N_{\emptyset}(K)=\mathbf{1}_{K\equiv 1\pmod{M}}\leq 1$, and the assertion is immediate. Write $h=h_{\mathcal{H}}$. By Lemma 10.2 it suffices to show $N_{\mathcal{H}}(K)\leq Y^{\max(h-\Omega_{T},\,h/2)+o(1)}$ uniformly in $K$. Expand by Lemma 10.3. Let $\mathcal{E}=\bigcup_{\beta\in\mathcal{H}}\mathcal{E}_{j_{\beta}}$, the characters for which some held power is principal. It contains $\chi_{0}$.

Torsion. $|\mathcal{E}|\leq 4(2d)^{\omega(M)}=Y^{o(1)}$ by Lemma 10.4. On $\mathcal{E}$ use $|\Sigma_{\beta}|\leq S_{\beta}$. By Lemma 10.1 these characters contribute at most

$$\frac{|\mathcal{E}|}{\varphi(M)}\prod_{\beta}S_{\beta}\leq Y^{h-\Omega_{T}+o(1)}.$$

Generic. Let $\mathcal{X}$ be the complement of $\mathcal{E}$. For $\chi\in\mathcal{X}$ and every $\beta$, $\chi^{j_{\beta}}$ and $\overline{\chi}^{\,j_{\beta}}$ are nonprincipal, and $|\Sigma_{\beta}(\overline{\chi}^{\,j_{\beta}})|=|\Sigma_{\beta}(\chi^{j_{\beta}})|$. Lemma 10.6(i) gives the hypothesis of Lemma 10.7 with $r_{\beta}=2$, $C_{\rm H}=Y^{o(1)}$. Take $\vartheta_{\beta}=1$; then $\sum_{\beta}\vartheta_{\beta}/4=|\mathcal{H}|/4\leq 1$. The generic characters contribute at most $Y^{o(1)}\prod_{\beta}S_{\beta}^{1/2}=Y^{h/2+o(1)}$.

Total. $N_{\mathcal{H}}(K)\leq Y^{o(1)}(Y^{h-\Omega_{T}}+Y^{h/2})$. With Lemma 10.2,

$$D\leq\kappa_{T}+P_{\rm mo}-h+\max\Bigl{(}h-\Omega_{T},\frac{h}{2}\Bigr{)}+o(1)=\kappa_{T}+P_{\rm mo}-\min\Bigl{(}\Omega_{T},\frac{h}{2}\Bigr{)}+o(1).$$

∎

No case distinction in $\Omega_{T}$ occurs. The proof holds for every $M\geq 1$; for $M\leq 2$ the generic sum is empty. If $\mathcal{H}=\emptyset$ the row is trivial.

Proposition 10.9 (PS23).

Let $0<\delta\leq 1/2$. Then

(10.4) $$D\leq\kappa_{T}+P_{\rm mo}-\min\Bigl{(}\frac{P_{\rm mo}}{2},\frac{2\Omega_{T}}{3}\Bigr{)}+d\delta+o(1),$$

the $o(1)$ depending on $\delta$.

Proof.

Paid blocks. Let $\mathcal{H}=\{\beta:h_{\beta}\geq\delta\}$ and $h=h_{\mathcal{H}}$. The other blocks number at most $2d$, so $P_{\rm mo}-h<2d\delta$.

Orders. For $\beta\in\mathcal{H}$ put

$$r_{\beta}=2\quad(h_{\beta}>\Omega_{T}/2),\qquad r_{\beta}=\lfloor\Omega_{T}/h_{\beta}\rfloor\quad(h_{\beta}\leq\Omega_{T}/2).$$

In the second case $2\leq r_{\beta}\leq 1/\delta$, by Lemma 10.1, and $S_{\beta}^{\,r_{\beta}}=Y^{r_{\beta}h_{\beta}}\leq Y^{\Omega_{T}}\leq M$. In both cases

(10.5) $$r_{\beta}h_{\beta}\geq\frac{2\Omega_{T}}{3}.$$

Indeed $2h_{\beta}>\Omega_{T}$ in the first case. In the second, put $t=\Omega_{T}/h_{\beta}\geq 2$: for $t<3$, $\lfloor t\rfloor/t=2/t>2/3$; for $t\geq 3$, $\lfloor t\rfloor>t-1\geq 2t/3$.

Moments. Expand $N_{\mathcal{H}}(K)$ by Lemma 10.3. Let $\mathcal{E}=\bigcup_{\beta\in\mathcal{H}}\mathcal{E}_{j_{\beta}}$ and $\mathcal{X}$ its complement. On $\mathcal{X}$,

$$\sum_{\chi\in\mathcal{X}}|\Sigma_{\beta}(\chi^{j_{\beta}})|^{2r_{\beta}}\leq\varphi(M)\,S_{\beta}^{\,r_{\beta}}\,Y^{o(1)}\qquad(\beta\in\mathcal{H}),$$

by Lemma 10.6(i) if $h_{\beta}>\Omega_{T}/2$, and by Lemma 10.6(ii) with $r_{\max}=\lfloor 1/\delta\rfloor$ if $h_{\beta}\leq\Omega_{T}/2$.

Budget. Put $b_{\rm H}=\sum_{\beta\in\mathcal{H}}1/(2r_{\beta})$ and $\vartheta=\min(1,1/b_{\rm H})$, with $\vartheta=1$ if $\mathcal{H}=\emptyset$. Then $\sum_{\beta}\vartheta/(2r_{\beta})\leq 1$. By (10.5),

$$\frac{\vartheta}{2}\,h=\vartheta\sum_{\beta}\frac{r_{\beta}h_{\beta}}{2r_{\beta}}\geq\frac{2\Omega_{T}}{3}\,\vartheta b_{\rm H}.$$

If $b_{\rm H}\leq 1$, then $\vartheta=1$ and the saving $\vartheta h/2$ equals $h/2$. If $b_{\rm H}>1$, then $\vartheta b_{\rm H}=1$ and $\vartheta h/2\geq 2\Omega_{T}/3$. In both cases $\vartheta h/2\geq\min(h/2,2\Omega_{T}/3)$.

Generic. Lemma 10.7 with $\vartheta_{\beta}=\vartheta$ and $|\mathcal{H}|\leq 2d$ bounds the generic characters by $Y^{h-\vartheta h/2+o(1)}\leq Y^{h-\min(h/2,2\Omega_{T}/3)+o(1)}$.

Torsion. $|\mathcal{E}|\leq 2d(2d)^{\omega(M)}=Y^{o(1)}$. As in Proposition 10.8 these characters contribute $Y^{h-\Omega_{T}+o(1)}$. Since $\min(h/2,2\Omega_{T}/3)\leq\Omega_{T}$, this is dominated.

Total. By Lemma 10.2,

$$D\leq\kappa_{T}+P_{\rm mo}-\min\Bigl{(}\frac{h}{2},\frac{2\Omega_{T}}{3}\Bigr{)}+o(1).$$

Finally $\min(h/2,2\Omega_{T}/3)\geq\min(P_{\rm mo}/2,2\Omega_{T}/3)-(P_{\rm mo}-h)/2$ and $(P_{\rm mo}-h)/2<d\delta$. ∎

If $h_{\beta}\leq\Omega_{T}/2$, then $S_{\beta}^{\,2}\leq M$, and Lemma 10.6(ii) with $r=2$ gives the bound of Lemma 10.6(i). Thus this proof invokes Theorem B only for blocks with $h_{\beta}>\Omega_{T}/2$. When every block is at most $\Omega_{T}/2$, the elementary moment suffices.

For larger blocks the elementary moment with Lemma 10.7 falls short. Take $\Omega_{T}=1$ and four block masses

$$\frac{3}{5},\quad\frac{17}{50},\quad\frac{17}{50},\quad\frac{1}{50}.$$

The target saving is $\min(P_{\rm mo}/2,2\Omega_{T}/3)=13/20$. With the elementary moment, the available orders satisfy $r_{\beta}\leq\lfloor\Omega_{T}/h_{\beta}\rfloor$, giving $r=(1,2,2,50)$. The best saving with per-block exponents is the fractional-knapsack value

$$\max_{\begin{subarray}{c}0\leq\vartheta_{i}\leq 1\\ \sum_{i}\vartheta_{i}/(2r_{i})\leq 1\end{subarray}}\frac{1}{2}\sum_{i}\vartheta_{i}h_{i}=\frac{161}{250},\qquad(\vartheta_{1},\vartheta_{2},\vartheta_{3},\vartheta_{4})=\left(\frac{49}{50},1,1,1\right).$$

The greedy order is by the ratio $r_{i}h_{i}$. A uniform exponent instead gives $\vartheta=100/101$ and saving $65/101$. Even the per-block optimum is short by

$$\frac{13}{20}-\frac{161}{250}=\frac{3}{500}.$$

The masses and $\Omega_{T}$ are homogeneous. Rescale them into the admissible region $L\leq 1$. This concerns only that method. It is no counterexample to Proposition 10.9.

Corollary 10.10.

Put $\delta=\varepsilon_{0}/(2d)$. Fix $Y\geq Y_{0}$, a pair $(\sigma,T)$, and a set $\mathcal{H}$ of at most four ordinary blocks. Then at least one arm of each displayed disjunction holds:

(10.6) $$D\leq\kappa_{T}+P_{\rm mo}-\Omega_{T}+\rho_{\mathrm{CS}}\quad\text{or}\quad D\leq\kappa_{T}+P_{\rm mo}-\tfrac{1}{2}h_{\mathcal{H}}+\rho_{\mathrm{CS}},$$

(10.7) $$D\leq\kappa_{T}+\tfrac{1}{2}P_{\rm mo}+\rho_{\mathrm{PS}}\quad\text{or}\quad D\leq\kappa_{T}+P_{\rm mo}-\tfrac{2}{3}\Omega_{T}+\rho_{\mathrm{PS}}$$

with $\rho_{\mathrm{CS}}=O_{d}(1/\log\log Y)\leq\varepsilon_{0}/2$ and $\rho_{\mathrm{PS}}=\varepsilon_{0}/2+O_{\varepsilon_{0},d}(1/\log\log Y)\leq\varepsilon_{0}$.

Proof.

Propositions 10.8 and 10.9 apply, since $d\delta=\varepsilon_{0}/2$. The divisor, prime-factor and logarithmic factors are each $Y^{O_{d}(1/\log\log Y)}$. The exponents depend on $d$ and $1/\delta$. The constants contribute $O(1/\log Y)$. The families are finite. A maximum gives the disjunction of its arms. ∎

The installed families are: $\mathrm{CS4}(\sigma,T,\mathcal{H})$ with $|\mathcal{H}|=4$ ordinary blocks, $3\cdot 127\cdot\binom{12}{4}=188\,595$ descriptors; and $\mathrm{PS23}(\sigma,T)$, $3\cdot 127=381$ descriptors. Table 12.1 records the relaxation of each arm. The certificate fixes the actual held set $\mathcal{H}$ of each $\mathrm{CS4}$ clause.

11. The finite system

The variables are the $28$ nonnegative exponents

(11.1) $$(a,b,c;\,a_{1},\dots,a_{6},b_{1},\dots,b_{6},c_{1},\dots,c_{6};\,v_{a},v_{b},v_{c};\,f_{a},f_{b},f_{c};\,D).$$

Here $L$, $p_{i}$, $\tau_{s}$ and $V_{s}$ of (6.1) are linear forms. The auxiliary variables $f_{s}$ encode (2.12):

(11.2) $$\begin{gathered}f_{s}\geq s_{2}+s_{4}+s_{6},\qquad f_{s}\geq s_{3}+s_{6},\qquad f_{s}\geq s_{5}\qquad(s=a,b,c),\\ f_{a}+f_{b}+f_{c}\leq 4L-6D.\end{gathered}$$

A point satisfies (2.12) if and only if some $f_{s}$ satisfy (11.2); take $f_{s}$ the maximum. Since $\mathsf{A}_{\rm cut}+\max\{\mathsf{B}_{\rm cut},0\}=\max(\mathsf{A}_{\rm cut},\mathsf{A}_{\rm cut}+\mathsf{B}_{\rm cut})$, the limiting cut (5.3) is the clause

(11.3) $$D\leq\mathsf{A}_{\rm cut}\quad\text{or}\quad D\leq\mathsf{A}_{\rm cut}+\mathsf{B}_{\rm cut}.$$

Let $\mathcal{S}$ be the following system.

• $29$ linear rows: (2.8), (2.9), (2.10), (2.11), the last two rows of (3.1) per side, the ten rows of (11.2), (7.1) and (6.4).

• The clauses of Table 11.1, each with all its arms.

All rows are in the limiting form of Table 12.1: every entry in its last column is dropped. A clause holds if one of its arms holds. It is never replaced by the conjunction of its arms. Coefficients, dyadic bounds, tail enumeration and recovery costs are inside the rows. So the theorems below are finite statements about (11.1).

Table 11.1. The clauses of $\mathcal{S}$.

clause	arms	number	source
(G1)–(G13)	$2$	$13$	Appendix B
(6.5)	$2$	$1$	Corollary 6.3
(8.5)	$2$	$30$	Corollary 8.2
(11.3)	$2$	$1\,560\,195$	Proposition 5.1
(10.6)	$2$	$188\,595$	Corollary 10.10
(10.7)	$2$	$381$	Corollary 10.10
(9.23)	$2$	$1476$	Proposition 9.12(a)
(9.24)	$3$	$242$	Proposition 9.12(b)
(9.25)	$4$	$56$	Proposition 9.12(c)

The descriptor sets are those of Sections 5, 8, 9.5 and 10. The $242$ one-group clauses are the two $\mathrm{GROUP12c}$ clauses and the $240$ $\mathrm{GROUP12ab}$ clauses. In total $\mathcal{S}$ has $29$ linear rows and $1\,750\,989$ clauses. The certificate below uses only these families.

11.1. The certificate

Theorem 2 (Computer-assisted).

Every nonnegative solution of $\mathcal{S}$ satisfies $D\leq 20/37$.

Proof.

Write $x$ for the vector (11.1). Let $e_{D}$ be the unit vector in the $D$ coordinate. The certificate is a finite rooted trie. Each internal node carries one clause of $\mathcal{S}$ and all its arms as children. Each leaf $t$ carries a set $I(t)$ of rows. These are the linear rows of $\mathcal{S}$, the rows $-x_{k}\leq 0$ and the arms on the path from the root to $t$. No other row is admissible. Write each row as $\langle g_{i},x\rangle\leq b_{i}$. The certificate gives $\eta_{i}\geq 0$ in $\mathbb{Q}$ on $I(t)$. The checker verifies at every leaf

(11.4) $$\sum_{i\in I(t)}\eta_{i}g_{i}=e_{D},\qquad\sum_{i\in I(t)}\eta_{i}b_{i}\leq\frac{20}{37}.$$

Let $x\geq 0$ satisfy $\mathcal{S}$. At each internal node $x$ satisfies one arm of its clause. Descend into that child. So $x$ reaches a leaf $t$, and every row of $I(t)$ holds at $x$. Hence

(11.5) $$D=\langle e_{D},x\rangle=\sum_{i\in I(t)}\eta_{i}\langle g_{i},x\rangle\leq\sum_{i\in I(t)}\eta_{i}b_{i}\leq\frac{20}{37}.\qed$$

The checker also verifies that no leaf path is a prefix of another. The clause (6.5) may occur at any depth; every (6.5) node has both children. Put

(11.6) $$\Lambda_{U}=\max_{t}\sum_{\begin{subarray}{c}i\in I(t)\\ \text{not }-x_{k}\leq 0\end{subarray}}\eta_{i}.$$

Each row is encoded in the normalisation of its displayed source and of Table C.1. In that normalisation its right-hand side rises by at most the entry of Table 12.1. The checker gives $\Lambda_{U}=586/201$, attained at leaf $95\,263$. Tables 11.2 and 11.3 give the statistics. The combined row for the two grouped families in Table 11.3 records their certificate census together.

Table 11.2. The certificate of Theorem 2.

leaves (all of kind upper)	$394\,633$
internal nodes	$394\,243$
nodes	$788\,876$
depth	$49$
infeasible leaves	$0$
$\Lambda_{U}$	$586/201$
worst certificate value $\sum_{i}\eta_{i}b_{i}$	$20/37$
leaves with certificate value exactly $20/37$	$1\,358$
largest number of nonzero multipliers on a leaf	$28$
distinct cuts (11.3) on paths	$17\,256$

Table 11.3. Census of the certificate by family. A row of a clause family is one of its arms.

family	internal nodes	distinct clauses on paths	distinct rows with $\eta_{i}>0$	pairs (leaf, row) with $\eta_{i}>0$
linear rows of $\mathcal{S}$			29	2 061 265
nonnegativity			21	2 478 333
(6.5)	4 972	1	2	26 673
(G1)–(G13)	27 223	13	26	675 941
(8.5)	15 468	30	60	479 423
(11.3)	236 038	17 256	34 116	2 417 940
(10.6)	48 765	10 649	21 220	644 485
(10.7)	61 110	155	310	673 495
(9.23)	387	75	149	1 924
(9.24), (9.25)	280	27	89	2 679

11.2. The optimum

Let $x^{*}$ be the point

(11.7) $$\begin{gathered}a=\tfrac{17}{37},\ a_{1}=\tfrac{7}{37},\ a_{3}=\tfrac{10}{37};\qquad b=\tfrac{7}{37},\ b_{1}=\tfrac{2}{37},\ v_{b}=\tfrac{35}{37};\\ c=\tfrac{13}{37},\ c_{1}=\tfrac{5}{37},\ c_{4}=\tfrac{8}{37};\qquad f_{a}=\tfrac{10}{37},\ f_{c}=\tfrac{8}{37};\qquad D=\tfrac{20}{37},\end{gathered}$$

with every unlisted coordinate zero.

Proposition 11.1.

$x^{*}$ satisfies $\mathcal{S}$. Thus $20/37$ is the exact optimum of the installed system $\mathcal{S}$.

Proof.

The witness verifier of Appendix C checks every row and every arm at $x^{*}$ in exact arithmetic. Table 11.4 gives the result. We check the binding rows by hand.

Linear rows. $L=1$, and

$$V_{a}=\tfrac{7}{37}+3\cdot\tfrac{10}{37}=1,\qquad V_{b}=\tfrac{2}{37}+\tfrac{35}{37}=1,\qquad V_{c}=\tfrac{5}{37}+4\cdot\tfrac{8}{37}=1.$$

So (6.4) and $\sum_{i\leq 6}is_{i}+v_{s}\leq 1$ hold with equality. Also $\tau_{a}=\tau_{c}=0$ and $\tau_{b}=5/37$, so $v_{b}=7\tau_{b}$. Then (2.10) holds with equality on all three sides. The pair rows give $b+c=20/37=D$. For (11.2), $f_{a}=a_{3}$, $f_{b}=0$, $f_{c}=c_{4}$, and $f_{a}+f_{b}+f_{c}=18/37\leq 28/37=4L-6D$. For (7.1), $L-p_{3}=27/37$.

Clauses. One arm suffices. Both arms of (6.5) hold. For (G2), $P_{2}=24/37$, $Q_{2}=17/37$ and $L-Q_{2}=20/37$. For (8.5) with $(e,y,z,\ell)=(a,b,c,2)$, $\mathsf{B}_{\rm sp}=V_{a}-V_{c}+c_{2}=0$ and $\mathsf{A}_{\rm sp}=b+c-c_{2}=20/37$. For (11.3) with $\sigma=c$, $T=\{1,4\}$, $R_{y}=\{1,3\}$, $R_{z}=\{1\}$: $q=1$,

$$\begin{gathered}\mathsf{A}_{\rm cut}=(a-a_{1}-a_{3})+(b-b_{1})+c_{1}+c_{4}=\tfrac{18}{37},\\ \mathsf{B}_{\rm cut}=(a_{1}+3a_{3}+b_{1})-(c_{1}+4c_{4})=\tfrac{39}{37}-1=\tfrac{2}{37}.\end{gathered}$$

For (10.7) with $\sigma=b$, $T=\{\mathrm{tail}\}$: $\kappa_{T}=\tau_{b}=5/37$, $\Omega_{T}=v_{b}$, $P_{\rm mo}=a+c=30/37$, and $\kappa_{T}+P_{\rm mo}/2=20/37$. For (10.6) with $\sigma=a$, $T=\{1\}$, $\mathcal{H}=\{b_{1},b_{2},c_{1},c_{4}\}$: $\kappa_{T}=\Omega_{T}=7/37$, and $\kappa_{T}+P_{\rm mo}-\Omega_{T}=b+c=20/37$. For (9.23) with $\sigma=c$, $J=\{a_{1},a_{2},a_{3},b_{1}\}$: $C_{c}=13/37$, $R_{c}=24/37$, $P_{J}=19/37$, and $E_{\mathfrak{D}}=55/74>20/37$. This is the smallest bound within $\mathrm{POW3}(c)$. ∎

Table 11.4. Smallest bound at $x^{*}$ per family. The bound of a clause is its largest arm. For (9.23)–(9.25) it is taken before intersection with (2.11). The other linear rows hold.

family	entries	smallest bound
(2.11)	$3$	$20/37$
(7.1)	$1$	$27/37$
(G1)–(G13)	$13$	$20/37$
(8.5)	$30$	$20/37$
(11.3)	$1\,560\,195$	$20/37$
(10.6)	$188\,595$	$20/37$
(10.7)	$381$	$20/37$
$\mathrm{POW3}(a)$, $(b)$, $(c)$	$486$, $495$, $495$	$41/74$, $26/37$, $55/74$
$\mathrm{GROUP12c}$, group on $a$; on $b$	$1$; $1$	$33/37$; $65/74$
$\mathrm{GROUP12ab}(a)$; $(b)$	$120$; $120$	$21/37$; $26/37$
$\mathrm{GROUP1212ab}(a)$; $(b)$	$28$; $28$	$21/37$; $26/37$

The nine $\mathrm{POW3}(a)$ descriptors with $J\supseteq\{b_{1},c_{1},c_{4}\}$ are valid rows. They are not in $\mathcal{S}$. At $x^{*}$ they have $P_{J}=15/37$, $E_{\mathfrak{D}}=39/74<20/37$ and $\tfrac{1}{2}(E_{\mathfrak{D}}+R_{a})=79/148<20/37$. Both arms fail at $x^{*}$. Leaving out valid rows keeps Theorem 2 true. The point $x^{*}$ lies in the installed $\mathcal{S}$. Adding the nine valid rows removes this witness; the optimum of that enlarged system is not asserted here. The point is not an $abc$ triple and gives no lower bound for $N_{1}(X)$.

12. Stability and the endpoint

Lemma 12.1.

Let $\rho\geq 0$ and $x\geq 0$. Suppose that, with right-hand sides raised by $\rho$,

• every linear row of $\mathcal{S}$ holds at $x$;

• every clause of $\mathcal{S}$ has an arm that holds at $x$.

The rows $-x_{k}\leq 0$ are not relaxed. Then

(12.1) $$D\leq\frac{20}{37}+\Lambda_{U}\rho.$$

Proof.

Descend the trie as in the proof of Theorem 2, with relaxed arms. At the leaf, (11.5) with relaxed right-hand sides adds

$$\rho\sum_{i\ \text{not }-x_{k}\leq 0}\eta_{i}\leq\Lambda_{U}\rho.\qed$$

Lemma 12.2.

Let $0<\mu\leq 1$. Let $Y_{0}=Y_{0}(\varepsilon_{0},d)$ be the largest of $Y_{\rm red}$ of Section 2, $\exp(\exp(1))$, $Y_{\rm sv}(8,\theta)$ for $\theta\in\Theta(\varepsilon_{0}/2)$, $Y_{\rm el}(\varepsilon_{0},d,\varepsilon_{0}/2)$ and two further thresholds. The first is the point beyond which the statements made for large $Y$ in Sections 6–10 hold. The second is the least $Y$ beyond which each displayed vanishing loss, including $\log_{Y}2^{1+h_{d}}$, is at most $\varepsilon_{0}/2$. It depends only on $\varepsilon_{0}$ and $d$. Let $Y\geq Y_{0}$, and take a nonempty box admissible in (2.3) at scale $Y$. Then every linear row of $\mathcal{S}$ holds in a $\mu$-free form. So does at least one arm of every clause. Each right-hand side rises by at most the amount in Table 12.1. In particular (2.8) becomes $L\leq 1+3\varepsilon_{0}/4$. Consequently

(12.2) $$\rho=18\varepsilon_{0}+o_{\varepsilon_{0},d}(1)$$

is admissible in Lemma 12.1, and $\rho\leq 19\varepsilon_{0}$ for $\mu\leq 1$ and $Y\in[Y_{0},X]$.

Table 12.1. The relaxation carried by each family of $\mathcal{S}$. Here $\varepsilon_{1}=\varepsilon_{0}$, $\rho_{0}=\varepsilon_{0}/2$ and $\delta=\varepsilon_{0}/(2d)$.

family	source	raised by
(2.8)	[2, (6.1)]	$3\varepsilon_{0}/4$
(2.9), (2.10), (3.1), the $f_{s}$ rows of (11.2)	definitions and (2.4)	$0$
(2.11)	Lemma A.2	$O_{d}(1/\log\log Y)$
Appendix B	Corollary A.5	$6\varepsilon_{0}+o_{\varepsilon_{0},d}(1)$
(2.12), the last row of (11.2)	Lemma A.3, $D$-coefficient $6$	$18\varepsilon_{0}+o_{\varepsilon_{0},d}(1)$
(5.3), (11.3)	Proposition 5.1	$o_{\varepsilon_{0},d}(1)$
(6.4)	Lemma 6.1	$\varepsilon_{0}/2$
(6.5), each arm	Lemma 6.2	$3\varepsilon_{0}/2+\log_{Y}2^{1+h_{d}}$
(7.1)	Proposition 7.1	$\varepsilon_{0}+O_{\varepsilon_{0}}(1/\log Y)$
(8.5), each arm	Proposition 8.1	$\varepsilon_{0}+O_{d}(1/\log\log Y)$
(9.23)–(9.25), each arm	Proposition 9.12	$2\rho_{0}=\varepsilon_{0}$
(10.6), each arm	Corollary 10.10	$O_{d}(1/\log\log Y)$
(10.7), each arm	Corollary 10.10	$\varepsilon_{0}/2+O_{\varepsilon_{0},d}(1/\log\log Y)$

Proof.

Run Section 2 at scale $Y$ with $\lambda$ replaced by $\mu$ and $\log_{Y}$ in place of $\log_{X}$ in (2.5). In (2.4), $\mu$ occurs only in the radical constraint. Its upper half is

(12.3) $$L\leq\mu+3\varepsilon_{0}/4\leq 1+3\varepsilon_{0}/4,$$

the one row of $\mathcal{S}$ that depends on $\mu$. Its lower half is

(12.4) $$\mu\leq L+O_{d}\Bigl{(}\frac{1}{\log Y}\Bigr{)}.$$

The proof of [2, Theorem 1.3] uses the weaker radical bound

$$\prod_{j\leq d}A_{j}B_{j}C_{j}\leq Y^{\mu+3\varepsilon_{0}}\leq Y.$$

This needs $\varepsilon_{0}\leq(1-\mu)/3$, false at $\mu=1$ for every $\varepsilon_{0}>0$. It is the only use of $\mu<1$ in that proof, and the visible source of its $\mu$-dependent constant. We keep (12.3) as a relaxed row instead.

By (12.4), $\mu$ leaves the other rows. The other constraints of (2.4) are $\mu$-free. So (2.9), (2.10), (3.1) and Lemma 3.1 are $\mu$-free and exact. So are the rows $f_{s}\geq\cdots$ of (11.2), which define $f_{s}$. The constants of the reduction and of Appendix A depend only on $\varepsilon_{0}$ and $d$, not on $\mu$. The condition $\varepsilon_{0}\leq(1-\mu)/3$ is needed for the separate step $ABC\leq Y$ in the proof of [2, Theorem 1.3].

Pair row. [2, Proposition 2.3] has no rate in $Y$. Lemma A.2 at scale $Y$ gives (2.11) with the factor $\Delta=Y^{O_{d}(1/\log\log Y)}$. So (2.11) costs $O_{d}(1/\log\log Y)$, as in Table 12.1.

Cut. The proof of Proposition 5.1 uses only the dyadic ranges, (2.2) and the fixed-$d$ lemmas. The same argument at scale $Y$ applies for every $0<\mu\leq 1$. Its divisor and root-class factors cost $O_{d}(1/\log\log Y)$.

Fourier and geometry. Lemma A.3 at scale $Y$ contains no $\mu$; its $\varepsilon_{0}$-exponent is $3\varepsilon_{0}$. Our Fourier row is $\kappa_{F}$ times the logarithm of that bound, with

$$\kappa_{F}=\frac{[D]_{\text{row}}}{[D]_{\text{lemma}}}=\frac{6}{1}=\frac{[L]_{\text{row}}}{[L]_{\text{lemma}}}=\frac{4}{2/3}=\frac{1}{1/6}=6$$

on the $D$, $L$ and root terms. So $3\varepsilon_{0}$ becomes $18\varepsilon_{0}$. Corollary A.5 has $\varepsilon_{0}$-exponents $4\varepsilon_{0}$, $6\varepsilon_{0}$, and $\mu$ appears as $Y^{\mu}$ and $Y^{\mu-1}$. By (12.4), $\mu\to L$ costs $O_{d}(1/\log Y)$. The rows (G1)–(G13) have coefficient $1$ on $D$ and $L$, so they rise by at most $6\varepsilon_{0}$.

New rows. Sections 6–10 work at scale $Y$ with $\log_{Y}$ coordinates. They use (2.2), the dyadic ranges, the coefficient bound and the $\mu$-free constraints of (2.4). So their rows are $\mu$-free. Their errors are those of Corollary 6.3, Proposition 7.1 with $\varepsilon_{1}=\varepsilon_{0}$, Corollary 8.2, Proposition 9.12 with $\rho_{0}=\varepsilon_{0}/2$, and Corollary 10.10 with $\delta=\varepsilon_{0}/(2d)$. For $Y\geq Y_{0}$ each is at most $2\varepsilon_{0}$. The cubic-sieve proofs use only $M\geq Y^{W_{\sigma}}$; the coefficient $n_{\sigma,0}\geq 1$ is the only coefficient property used in that bound. The factor $Q/\varphi(Q)$ is accounted for in Step 7 of Proposition 9.10. The factor six above multiplies only the printed $3\varepsilon_{0}$ of the Fourier row. No other row carries it.

These are the entries of Table 12.1; the largest is (12.2). All constants depend only on $\varepsilon_{0}$ and $d$, not on $\mu$. The $Y$-dependent errors are the displayed $O_{d}(1/\log Y)$, $O_{d}(1/\log\log Y)$ and $o_{\varepsilon_{0},d}(1)$ terms. They include the constants of the reduction in Section 2, of Lemma A.3 and of Corollary A.5. The $Y_{0}$ threshold absorbs them. ∎

By (12.2),

(12.5) $$\Lambda_{U}\rho=\frac{586}{201}\bigl{(}18\varepsilon_{0}+o_{\varepsilon_{0},d}(1)\bigr{)}=\frac{3516}{67}\,\varepsilon_{0}+o_{\varepsilon_{0},d}(1).$$

The certificate has no infeasible leaf, so no infeasibility margin enters.

Lemma 12.2 removes the restriction $\lambda<1$ of [2, Theorem 1.3]. At $\mu=1$ the row (2.8) is lost, and Lemma 12.1 prices the relaxation $\rho$ at $\Lambda_{U}\rho$ in the exponent. The constant does not depend on $\mu$. $\mathcal{S}$, its certificate and $\Lambda_{U}$ are free of $\varepsilon_{0}$ and $d$. So choosing $\varepsilon_{0}$ from $\Lambda_{U}$ is not circular. The parameters are chosen in this order:

$$\begin{gathered}\varepsilon\ \longrightarrow\ \text{freeze certificate}\ \longrightarrow\ \varepsilon_{0}\ \longrightarrow\ d=d(\varepsilon_{0}),\\ \delta=\frac{\varepsilon_{0}}{2d},\ \rho_{0}=\frac{\varepsilon_{0}}{2},\ \varepsilon_{1}=\varepsilon_{0}\ \longrightarrow\ X.\end{gathered}$$

The grid $\Theta(\rho_{0})$ of Lemma 9.11 is finite once $\rho_{0}$ is fixed. Proposition 10.9 needs no tail cutoff: $d$ is fixed before $\delta$, and the paid blocks cost $d\delta=\varepsilon_{0}/2$.

13. Proof of Theorem 1

Fix $\varepsilon>0$. Choose $\varepsilon_{0}>0$ with $\frac{11335}{201}\,\varepsilon_{0}<\varepsilon/2$ and with folded index at least seven (Section 3.1). This fixes $d=d(\varepsilon_{0})$, then $\delta$, $\rho_{0}$ and $\varepsilon_{1}=\varepsilon_{0}$ as above. The factors $8^{\omega(M)}$, $(2j)^{\omega(M)}$ and $\operatorname{div}(N)^{O_{d}(1)}$ are $Y^{o(1)}$ for fixed $d$ (Lemmas 4.2, 4.3, 10.4); they need no budget. Dyadic constants and the count of boxes are inside (2.3).

Let $\mu\leq 1$ and $Y\leq X$. If $\mu\leq 0$, then $N^{*}_{\mu}(Y)=0$, as $\operatorname{rad}(abc)\geq 1\geq c^{\mu}$. Let $0<\mu\leq 1$. If $Y<Y_{0}(\varepsilon_{0},d)$, then $N^{*}_{\mu}(Y)\leq Y^{3}\ll_{\varepsilon_{0},d}1$. If $Y\geq Y_{0}$, then for a nonempty box Lemma 12.2 raises every row and arm of $\mathcal{S}$ by at most $\rho\leq 19\varepsilon_{0}$. So the stability and reduction losses are at most

$$19\Lambda_{U}\varepsilon_{0}+\varepsilon_{0}=\frac{11335}{201}\,\varepsilon_{0}<\frac{\varepsilon}{2}.$$

Thus Theorem 2 and Lemma 12.1 give

(13.1) $$\mathcal{B}_{d}\leq Y^{20/37+\frac{11134}{201}\,\varepsilon_{0}}.$$

By (2.3) at scale $Y$, at a further cost $Y^{\varepsilon_{0}}$, $N^{*}_{\mu}(Y)\ll_{\varepsilon}Y^{20/37+\varepsilon/2}$. The constant depends only on $\varepsilon$. Finally (2.1) with $\lambda=1$ absorbs $(\log X)^{2}$ and the maxima into the remaining $\varepsilon/2$. ∎

Appendix A BBLT estimates in the half-open convention

We prove the pair, Fourier and geometry bounds of [2, Propositions 2.3, 3.1 and 4.1] for the boxes (2.2). The reduction [2, Proposition 2.1] is rerun in Section 2. Work at scale $X$ with exponent $\lambda$, in a box satisfying (2.4). Windows are $\mathcal{I}(S)=[S,2S)\cap\mathbb{N}$ with $S\geq 1$ a power of two, so $\#\mathcal{I}(S)=S$ and $\mathcal{I}(1)=\{1\}$. Roots equal to $1$ are allowed. Put

$$A=\prod_{i\leq d}A_{i},\qquad B=\prod_{i\leq d}B_{i},\qquad C=\prod_{i\leq d}C_{i},$$

so $ABC=X^{L}$. For a side $s$ with roots $\mathfrak{s}_{i}\in\mathcal{I}(S_{s,i})$ put $N_{s}=\prod_{i\leq d}\mathfrak{s}_{i}^{\,i}$, so the side value is $n_{s,0}N_{s}$. Since $\mathfrak{s}_{i}<2S_{s,i}$ and $\prod_{i}S_{s,i}^{\,i}\leq X$,

(A.1) $$1\leq N_{s}<2^{h_{d}}X.$$

Put

$$\Delta=\max_{1\leq N<2^{h_{d}}X}\operatorname{div}(N)^{d}.$$

By the maximal order of $\operatorname{div}$, $\Delta=X^{O_{d}(1/\log\log X)}$ for $X\geq 3$. So $\Delta\ll_{d,\delta^{\prime}}X^{\delta^{\prime}}$ for every fixed $\delta^{\prime}>0$. By Lemma 4.3, a product $\prod_{i\in I}\mathfrak{s}_{i}^{\,i}<2^{h_{d}}X$ with $I\subseteq[d]$ determines the roots $(\mathfrak{s}_{i})_{i\in I}$ up to $\Delta$ choices. The constants below depend only on $d$ and $\varepsilon_{0}$. They do not depend on $\lambda$, the coefficients or the box.

Lemma A.1.

Let $j\geq 2$ and $m\in\mathbb{Z}\setminus\{0\}$. Then

$$\#\{(x,y)\in\mathbb{N}^{2}:x^{j}-y^{j}=m\}\leq 2(j-1)\operatorname{div}(|m|).$$

Proof.

Put $t=x-y$. Then $t\neq 0$, and $t\mid m$ since $x^{j}-y^{j}=t\sum_{i<j}x^{j-1-i}y^{i}$. So $t$ takes at most $2\operatorname{div}(|m|)$ values. For fixed $t$, $x^{j}-(x-t)^{j}$ is a polynomial in $x$ of degree $j-1\geq 1$ with leading coefficient $jt\neq 0$. So it equals $m$ for at most $j-1$ values of $x$, and $y=x-t$. ∎

Lemma A.2 (pair bound).

$\mathcal{B}_{d}\leq\Delta\min(AB,AC,BC)$.

Proof.

Fix the $a$- and $b$-roots: exactly $AB$ choices. The equation in (2.2) fixes $c_{0}N_{c}$, hence $N_{c}$. By (A.1), the $c$-roots take at most $\Delta$ values. The pairs $(a,c)$ and $(b,c)$ are the same, since $b_{0}N_{b}=c_{0}N_{c}-a_{0}N_{a}$ and $a_{0}N_{a}=c_{0}N_{c}-b_{0}N_{b}$. ∎

Lemma A.3 (Fourier bound).

Let $2\leq j,k,\ell\leq d$ and put

$$\Pi_{F}=\prod_{j\mid i}A_{i}\prod_{k\mid i}B_{i}\prod_{\ell\mid i}C_{i},$$

the products over $i\leq d$. Then

$$\mathcal{B}_{d}\leq(3d)^{1/2}\Delta^{5/2}\,\frac{(ABC)^{2/3}}{\Pi_{F}^{1/6}}\ll_{\varepsilon_{0},d}X^{3\varepsilon_{0}}\,\frac{(ABC)^{2/3}}{\Pi_{F}^{1/6}}.$$

Proof.

Orthogonality. Write $e(t)=e^{2\pi it}$. For a side $s$ put

$$\Sigma_{s}(\alpha)=\sum e(\alpha\,n_{s,0}N_{s})\qquad(\alpha\in\mathbb{R}),$$

the sum over all root tuples of $s$ in the windows of the box. The integral

$$\int_{0}^{1}\Sigma_{a}(\alpha)\Sigma_{b}(\alpha)\overline{\Sigma_{c}(\alpha)}\,d\alpha$$

counts the root tuples with $a_{0}N_{a}+b_{0}N_{b}=c_{0}N_{c}$. Dropping the gcd condition, this is at least $\mathcal{B}_{d}$, and at most $\int_{0}^{1}|\Sigma_{a}\Sigma_{b}\Sigma_{c}|$. By Hölder with exponents $3,3,3$ and Cauchy–Schwarz,

(A.2) $$\mathcal{B}_{d}\leq\prod_{s=a,b,c}\Bigl{(}\int_{0}^{1}|\Sigma_{s}|^{3}\Bigr{)}^{1/3},\qquad\int_{0}^{1}|\Sigma_{s}|^{3}\leq\Bigl{(}\int_{0}^{1}|\Sigma_{s}|^{2}\Bigr{)}^{1/2}\Bigl{(}\int_{0}^{1}|\Sigma_{s}|^{4}\Bigr{)}^{1/2}.$$

We treat side $a$ with $j$. Sides $b$ and $c$, with $k$ and $\ell$, are the same. Write $\mathbf{a}=(\mathfrak{a}_{i})_{i\leq d}$ and $N(\mathbf{a})=N_{a}$. As $a_{0}\geq 1$, $\int_{0}^{1}e(\alpha a_{0}m)\,d\alpha=\mathbf{1}_{m=0}$ for $m\in\mathbb{Z}$.

Second moment. $\int_{0}^{1}|\Sigma_{a}|^{2}$ counts pairs $(\mathbf{a},\mathbf{a}^{\prime})$ with $N(\mathbf{a})=N(\mathbf{a}^{\prime})$. Choose $\mathbf{a}$ in $A$ ways; then $\mathbf{a}^{\prime}$ takes at most $\Delta$ values. So

$$\int_{0}^{1}|\Sigma_{a}|^{2}\leq A\Delta.$$

Fourth moment. Let $J=\{i\leq d:j\mid i\}$, so $j\in J$. Split $\mathbf{a}=(\mathbf{a}^{\circ},\mathbf{a}^{\bullet})$ into the roots with $i\notin J$ and $i\in J$, and put

$$u(\mathbf{a}^{\circ})=\prod_{i\notin J}\mathfrak{a}_{i}^{\,i},\qquad W(\mathbf{a}^{\bullet})=\prod_{i\in J}\mathfrak{a}_{i}^{\,i}.$$

The tuple $\mathbf{a}^{\circ}$ runs over exactly $A^{\circ}=\prod_{i\notin J}A_{i}=A/\prod_{j\mid i}A_{i}$ values. Cauchy–Schwarz over $\mathbf{a}^{\circ}$ gives

$$|\Sigma_{a}(\alpha)|^{2}\leq A^{\circ}\,\mathcal{T}(\alpha),\qquad\mathcal{T}(\alpha)=\sum_{\mathbf{a}^{\circ}}\ \sum_{\mathbf{a}^{\bullet},\mathbf{a}^{\prime\bullet}}e\bigl{(}\alpha a_{0}\,u(\mathbf{a}^{\circ})(W(\mathbf{a}^{\bullet})-W(\mathbf{a}^{\prime\bullet}))\bigr{)}\geq 0.$$

Expand $|\Sigma_{a}|^{2}$ over pairs $(\mathbf{a}^{\prime\prime},\mathbf{a}^{\prime\prime\prime})$ and integrate:

$$\int_{0}^{1}|\Sigma_{a}|^{4}\leq A^{\circ}\int_{0}^{1}\mathcal{T}|\Sigma_{a}|^{2}=A^{\circ}\,\mathcal{N},$$

Here $\mathcal{N}$ counts the tuples $(\mathbf{a}^{\circ},\mathbf{a}^{\bullet},\mathbf{a}^{\prime\bullet},\mathbf{a}^{\prime\prime},\mathbf{a}^{\prime\prime\prime})$ with

(A.3) $$u(\mathbf{a}^{\circ})\bigl{(}W(\mathbf{a}^{\bullet})-W(\mathbf{a}^{\prime\bullet})\bigr{)}=N(\mathbf{a}^{\prime\prime\prime})-N(\mathbf{a}^{\prime\prime}).$$

Zero case. If the right side of (A.3) is $0$, then $W(\mathbf{a}^{\bullet})=W(\mathbf{a}^{\prime\bullet})$. Choose $(\mathbf{a}^{\circ},\mathbf{a}^{\bullet})$ and $\mathbf{a}^{\prime\prime}$ in $A^{2}$ ways. Then $\mathbf{a}^{\prime\bullet}$ and $\mathbf{a}^{\prime\prime\prime}$ take at most $\Delta$ values each. This gives at most $A^{2}\Delta^{2}$ tuples.

Nonzero case. Choose $\mathbf{a}^{\prime\prime},\mathbf{a}^{\prime\prime\prime}$ in $A^{2}$ ways, with right side $m_{0}\neq 0$. By (A.1), $|m_{0}|<2^{h_{d}}X$. Each $\mathfrak{a}_{i}$ with $i\notin J$ divides $m_{0}$, so $\mathbf{a}^{\circ}$ takes at most $\operatorname{div}(|m_{0}|)^{d}\leq\Delta$ values. Then $m=m_{0}/u(\mathbf{a}^{\circ})\neq 0$ is fixed, and $|m|<2^{h_{d}}X$. As $j\mid i$ for $i\in J$,

$$W(\mathbf{a}^{\bullet})=x^{j},\quad W(\mathbf{a}^{\prime\bullet})=y^{j},\qquad x=\prod_{i\in J}\mathfrak{a}_{i}^{\,i/j},\quad y=\prod_{i\in J}\mathfrak{a}_{i}^{\prime\,i/j},$$

with $x,y\in\mathbb{N}$ and $x^{j}-y^{j}=m$. Lemma A.1 gives at most $2(j-1)\operatorname{div}(|m|)\leq 2d\Delta$ pairs $(x,y)$. Since $x\leq x^{j}<2^{h_{d}}X$ and $y\leq y^{j}<2^{h_{d}}X$, Lemma 4.3 recovers $\mathbf{a}^{\bullet}$ from $x$ and $\mathbf{a}^{\prime\bullet}$ from $y$, with at most $\Delta$ values each. This gives at most $2dA^{2}\Delta^{4}$ tuples.

Hence $\mathcal{N}\leq 3dA^{2}\Delta^{4}$ and

$$\int_{0}^{1}|\Sigma_{a}|^{4}\leq 3d\,\Delta^{4}\,\frac{A^{3}}{\prod_{j\mid i}A_{i}}.$$

Combination. By (A.2),

$$\int_{0}^{1}|\Sigma_{a}|^{3}\leq(3d)^{1/2}\Delta^{5/2}\,\frac{A^{2}}{\bigl{(}\prod_{j\mid i}A_{i}\bigr{)}^{1/2}}.$$

Multiply the three sides and take the cube root. Finally $\Delta^{5/2}\ll_{\varepsilon_{0},d}X^{3\varepsilon_{0}}$. ∎

Take $\log_{X}$, multiply by $6$, keep only $i\leq 6$ and choose $j,k,\ell\in\{2,3,5\}$. Since all coordinates are nonnegative, this gives the $27$ rows of (2.12), each raised by $18\varepsilon_{0}+O_{\varepsilon_{0},d}(1/\log X)$.

For the geometry bound we import the following lattice-point count, in the form used in the proof of [2, Proposition 4.1].

Theorem C ([7, Lemma 3]).

Let $a^{\prime},b^{\prime},c^{\prime}$ be nonzero integers with $\gcd(a^{\prime},b^{\prime},c^{\prime})=1$, and let $H_{a},H_{b},H_{c}\geq 1$. The number of $(x,y,z)\in\mathbb{Z}^{3}$ with $\gcd(x,y,z)=1$, $a^{\prime}x+b^{\prime}y=c^{\prime}z$ and $|x|\leq H_{a}$, $|y|\leq H_{b}$, $|z|\leq H_{c}$ is

$$\ll 1+\frac{H_{a}H_{b}H_{c}}{\max\{|a^{\prime}|H_{a},|b^{\prime}|H_{b},|c^{\prime}|H_{c}\}},$$

with an absolute implied constant $C_{\rm HB}$.

Lemma A.4 (geometry bound).

Let $I,I^{\prime},I^{\prime\prime}\subseteq[d]$ and put

$$\Pi_{1}=\prod_{i\in I}A_{i}\prod_{i\in I^{\prime}}B_{i}\prod_{i\in I^{\prime\prime}}C_{i},\qquad\Pi_{2}=\prod_{i\in I}A_{i}^{i-1}\prod_{i\in I^{\prime}}B_{i}^{i-1}\prod_{i\in I^{\prime\prime}}C_{i}^{i-1}.$$

Then

$$\mathcal{B}_{d}\leq C_{\rm HB}\,\Delta^{3}\Bigl{(}\frac{ABC}{\Pi_{1}}+2^{3h_{d}}X^{-1+\varepsilon_{0}/2}\,ABC\,\Pi_{2}\Bigr{)}.$$

Proof.

Variables. For a tuple counted by $\mathcal{B}_{d}$ put

$$a^{\prime} =a_{0}\prod_{i\notin I}\mathfrak{a}_{i}^{\,i}, b^{\prime} =b_{0}\prod_{i\notin I^{\prime}}\mathfrak{b}_{i}^{\,i}, c^{\prime} =c_{0}\prod_{i\notin I^{\prime\prime}}\mathfrak{c}_{i}^{\,i},$$

$$x =\prod_{i\in I}\mathfrak{a}_{i}^{\,i}, y =\prod_{i\in I^{\prime}}\mathfrak{b}_{i}^{\,i}, z =\prod_{i\in I^{\prime\prime}}\mathfrak{c}_{i}^{\,i}.$$

Then $a^{\prime}x+b^{\prime}y=c^{\prime}z$ and $a^{\prime},b^{\prime},c^{\prime}\geq 1$. The integers $a^{\prime},b^{\prime},c^{\prime}$ divide the three side values, and so do $x,y,z$. The side values are pairwise coprime by Lemma 2.1. So $\gcd(a^{\prime},b^{\prime},c^{\prime})=1$ and $\gcd(x,y,z)=1$.

Heights. Put

$$H_{a}=2^{h_{d}}\prod_{i\in I}A_{i}^{\,i},\qquad H_{b}=2^{h_{d}}\prod_{i\in I^{\prime}}B_{i}^{\,i},\qquad H_{c}=2^{h_{d}}\prod_{i\in I^{\prime\prime}}C_{i}^{\,i}.$$

These are at least $1$. Since $\mathfrak{a}_{i}<2A_{i}$, $0<x<H_{a}$; likewise $y<H_{b}$ and $z<H_{c}$. As $c_{0}\geq 1$ and $\mathfrak{c}_{i}\geq C_{i}$,

$$c^{\prime}H_{c}\geq\prod_{i\notin I^{\prime\prime}}C_{i}^{\,i}\prod_{i\in I^{\prime\prime}}C_{i}^{\,i}=\prod_{i\leq d}C_{i}^{\,i}\geq X^{1-\varepsilon_{0}/2}$$

by (2.4).

Count. Fix the complementary roots $\mathfrak{a}_{i}$ $(i\notin I)$, $\mathfrak{b}_{i}$ $(i\notin I^{\prime})$ and $\mathfrak{c}_{i}$ $(i\notin I^{\prime\prime})$: exactly $ABC/\Pi_{1}$ choices. They fix $a^{\prime},b^{\prime},c^{\prime}$. By Theorem C, the number of $(x,y,z)$ is at most

$$C_{\rm HB}\Bigl{(}1+\frac{H_{a}H_{b}H_{c}}{c^{\prime}H_{c}}\Bigr{)}\leq C_{\rm HB}\Bigl{(}1+2^{3h_{d}}X^{-1+\varepsilon_{0}/2}\prod_{i\in I}A_{i}^{\,i}\prod_{i\in I^{\prime}}B_{i}^{\,i}\prod_{i\in I^{\prime\prime}}C_{i}^{\,i}\Bigr{)}.$$

Each of $x,y,z$ is less than $2^{h_{d}}X$. So it fixes its selected roots up to $\Delta$ values. Multiply, and use

$$\frac{ABC}{\Pi_{1}}\prod_{i\in I}A_{i}^{\,i}\prod_{i\in I^{\prime}}B_{i}^{\,i}\prod_{i\in I^{\prime\prime}}C_{i}^{\,i}=ABC\,\Pi_{2}.\qed$$

Corollary A.5.

For $I,I^{\prime},I^{\prime\prime}\subseteq[d]$,

$$\mathcal{B}_{d}\ll_{\varepsilon_{0},d}\frac{X^{\lambda+4\varepsilon_{0}}}{\Pi_{1}}+X^{\lambda-1+6\varepsilon_{0}}\,\Pi_{2}.$$

Proof.

By (2.4), $ABC\leq X^{\lambda+3\varepsilon_{0}/4}$, and $\Delta^{3}\ll_{\varepsilon_{0},d}X^{\varepsilon_{0}/4}$. Lemma A.4 gives

$$\mathcal{B}_{d}\ll_{\varepsilon_{0},d}\frac{X^{\lambda+\varepsilon_{0}}}{\Pi_{1}}+X^{\lambda-1+3\varepsilon_{0}/2}\,\Pi_{2},$$

which is stronger, as $X\geq 1$. ∎

This is [2, Proposition 4.1] in our convention, with the same exponents. Lemmas A.2–A.4 use the windows, (2.2), $n_{s,0}\geq 1$ and the $\lambda$-free constraints of (2.4). Corollary A.5 also uses $ABC\leq X^{\lambda+3\varepsilon_{0}/4}$. At scale $Y$ with $\lambda:=\mu$ they give the entries of Table 12.1 for (2.11), (2.12) and (G1)–(G13).

Appendix B The thirteen min-disjunctions

We work at scale $X$ with exponent $\lambda$; Lemma 12.2 uses the same derivation at scale $Y$ with $\mu$. Put $p_{i}=a_{i}+b_{i}+c_{i}$, $L=a+b+c$. Each row is Corollary A.5 for one triple $I,I^{\prime},I^{\prime\prime}\subseteq[6]$. A sum of two terms is at most twice the larger, so

$$D\leq\max(\lambda+4\varepsilon_{0}-P,\lambda+6\varepsilon_{0}-Q)+O_{\varepsilon_{0},d}(1/\log X),$$

where $P=\sum_{i\in I}a_{i}+\sum_{i\in I^{\prime}}b_{i}+\sum_{i\in I^{\prime\prime}}c_{i}$ and $Q=1-\sum_{i\in I}(i-1)a_{i}-\sum_{i\in I^{\prime}}(i-1)b_{i}-\sum_{i\in I^{\prime\prime}}(i-1)c_{i}$. With $C_{\varepsilon_{0},d}$ the constant of Corollary A.5, the constant and the factor $2$ cost $\log(2C_{\varepsilon_{0},d})/\log X=O_{\varepsilon_{0},d}(1/\log X)$. By the lower bound in (2.4) and (2.5),

$$2^{-O_{d}(1)}X^{\lambda}\leq\prod_{j\leq d}A_{j}B_{j}C_{j}=X^{L},\qquad\lambda\leq L+O_{\varepsilon_{0},d}(1/\log X).$$

Hence $\min(P,Q)\leq L-D+6\varepsilon_{0}+O_{\varepsilon_{0},d}(1/\log X)$. The certificate uses the limiting form below, free of $\varepsilon_{0}$; the slack $6\varepsilon_{0}+O_{\varepsilon_{0},d}(1/\log X)$ is charged in Lemma 12.2 and Table 12.1. The choices, from the proof of [2, Theorem 1.3]:

$$\begin{array}[]{ll}\text{row }1:&I=I^{\prime}=I^{\prime\prime}=\{1,2,4\};\\ \text{rows }2\text{--}4:&I=I^{\prime}=\{1,2\},\ I^{\prime\prime}=\{1,2,3\}\ \text{and permutations};\\ \text{rows }5\text{--}7:&I=\{1,2\},\ I^{\prime}=I^{\prime\prime}=\{1,2,3\}\ \text{and permutations};\\ \text{rows }8\text{--}10:&I=I^{\prime}=\{1,2\},\ I^{\prime\prime}=\{1,3\}\ \text{and permutations};\\ \text{rows }11\text{--}13:&I=\{1,2\},\ I^{\prime}=I^{\prime\prime}=\{1,3\}\ \text{and permutations}.\end{array}$$

Written out:

(G1) $$P_{1} =p_{1}+p_{2}+p_{4}, Q_{1} =1-p_{2}-3p_{4}$$

(G2) $$P_{2} =p_{1}+p_{2}+a_{3}, Q_{2} =1-p_{2}-2a_{3}$$

(G3) $$P_{3} =p_{1}+p_{2}+b_{3}, Q_{3} =1-p_{2}-2b_{3}$$

(G4) $$P_{4} =p_{1}+p_{2}+c_{3}, Q_{4} =1-p_{2}-2c_{3}$$

(G5) $$P_{5} =p_{1}+p_{2}+a_{3}+b_{3}, Q_{5} =1-p_{2}-2a_{3}-2b_{3}$$

(G6) $$P_{6} =p_{1}+p_{2}+b_{3}+c_{3}, Q_{6} =1-p_{2}-2b_{3}-2c_{3}$$

(G7) $$P_{7} =p_{1}+p_{2}+c_{3}+a_{3}, Q_{7} =1-p_{2}-2c_{3}-2a_{3}$$

(G8) $$P_{8} =p_{1}+a_{3}+b_{2}+c_{2}, Q_{8} =1-2a_{3}-b_{2}-c_{2}$$

(G9) $$P_{9} =p_{1}+b_{3}+a_{2}+c_{2}, Q_{9} =1-2b_{3}-a_{2}-c_{2}$$

(G10) $$P_{10} =p_{1}+c_{3}+a_{2}+b_{2}, Q_{10} =1-2c_{3}-a_{2}-b_{2}$$

(G11) $$P_{11} =p_{1}+a_{2}+b_{3}+c_{3}, Q_{11} =1-a_{2}-2b_{3}-2c_{3}$$

(G12) $$P_{12} =p_{1}+b_{2}+a_{3}+c_{3}, Q_{12} =1-b_{2}-2a_{3}-2c_{3}$$

(G13) $$P_{13} =p_{1}+c_{2}+a_{3}+b_{3}, Q_{13} =1-c_{2}-2a_{3}-2b_{3}$$

and each row is used as the disjunction $D\leq L-P_{j}$ or $D\leq L-Q_{j}$.

Appendix C Computer checks

The paper comes with external files. They are the certificate report of Theorem 2 and the checking programs of Table C.2. The rows, witness (11.7), and verification procedures are specified in the text. All arithmetic is exact. No checking program imports a numerical package or an LP solver.

C.1. The report

The file final-report.raw.json.xz decompresses to the report. normalize_completed_report.py recomputes its derived trie statistics; on this report its output equals its input byte for byte. The report is one JSON object with fields target ("20/37"), system, search_flags, complete, stats, certificates, survivors, open_stack and elapsed_s. The lists survivors and open_stack are empty. Each certificate has exactly four fields.

• kind: always "upper".

• path: the list of arm labels from the root to the leaf.

• terms: a list of [row-label,"p/q"], multipliers positive.

• rhs: the value $\sum_{i}\eta_{i}b_{i}$.

The paths form the trie of Theorem 2. A label names one row or arm of $\mathcal{S}$ (Table C.1). The verifier rebuilds each row from its label and reads no stored coefficient vector. The metadata string system also contains the label DET. It names a row family outside $\mathcal{S}$. The verifier builds no row from it, and no path or multiplier in this certificate uses such a row.

program	what it checks
verify_tree_report_clean.py	Standard library only. Strict JSON, duplicate keys rejected; target, system string and flags. At each leaf: every label well formed and in $\mathcal{S}$; every term a linear row, a row $-x_{k}\leq 0$, or an arm on the path; (11.4) exactly, that is $\sum_{i}\eta_{i}g_{i}=e_{D}$ and $\sum_{i}\eta_{i}b_{i}\leq 20/37$; the declared rhs. The trie: paths distinct and prefix-free; the children of each internal node are exactly the arms of one clause, (6.5) included at any depth. It recomputes Tables 11.2 and 11.3 and $\Lambda_{U}$. It rejects $46$ corrupted reports, among them a missing arm, a missing (6.5) arm, a tampered multiplier, a row outside its path, a forbidden $\mathrm{POW3}(a)$ descriptor and a prefix leaf.
verify_tree_report.py	a second replay of (11.4) and of the node counts
verify_witness_clean.py	$x^{*}$ against every clause of $\mathcal{S}$ (Table 11.4); it rejects $19$ corrupted constructors
audit_clause_compiler.py, compiler_differential_used.py	every row used by the certificate, and every $\mathrm{POW3}$ and grouped descriptor, rebuilt by the search program’s compiler and compared with the verifier’s row

The driver runs these programs and writes their output:

run_verification.sh $\longrightarrow$ FROZEN_VERIFICATION.stdout.

Soundness uses the displayed row definitions and the label map in Table C.1. It also uses the exact Farkas identities at every leaf and the admissibility and trie checks of the first program. The compiler differential also compares the verifier’s row builder with the search compiler. The coefficient formulas and derivations in Sections 2–B identify those rows with the system $\mathcal{S}$.

Table C.1 gives the labels. Here $s\in\{a,b,c\}$; $\sigma$ is the modulus or powered side; $(y,z)$ is as in Section 5. A set $T\subseteq\{1,\dots,6,\mathrm{tail}\}$ is written as the integer $\sum_{t\in T}2^{t-1}$, with the tail counted as $t=7$. Free sets $R_{y},R_{z}$ are written likewise, in $[1,63]$ or $0$. Slots are written a1, …, c6.

Table C.1. Verifier labels and their sources.

verifier label	row or arm
L	(2.8)
roots<=s, rad-s	(2.9), (2.10)
tail7-s, val-s	$v_{s}\geq 7\tau_{s}$, $\sum_{i\leq 6}is_{i}+v_{s}\leq 1$ of (3.1)
pair-xy	(2.11)
fourier-s-j, $j=0,1,2$; fourier-sum	the rows $f_{s}\geq s_{2}+s_{4}+s_{6}$, $s_{3}+s_{6}$, $s_{5}$; the last row of (11.2)
HB3	(7.1)
ARCH:a<=c, ARCH:b<=c	(6.4)
ARCH:max-a, ARCH:max-b	the arms of (6.5)
G0; G1-s; G2-st; G3-s; G4-s; suffix :0, :1	(G1); (G2)–(G4); (G5)–(G7), $st=ab,bc,ca$; (G8)–(G10); (G11)–(G13); the $P$ arm, the $Q$ arm
SP:e:y:z:k:0, :1	The field $k$ equals the spacing exponent $\ell$; the two arms of (8.5)
UN:$\sigma$:$R_{y}$:$R_{z}$:$T$:00, :10	$D\leq\mathsf{A}_{\rm cut}$, $D\leq\mathsf{A}_{\rm cut}+\mathsf{B}_{\rm cut}$ of (11.3)
CS4:$\sigma$:$T$:$\mathcal{H}$:W, :h2	the two arms of (10.6); $T$ is the integer mask above, and $\mathcal{H}$ is the four comma-separated, lexicographically sorted held slots
PS:$\sigma$:$T$:half, :2W3	the two arms of (10.7)
POW3$\sigma$:$J$:S, :avg	$D\leq E_{\mathfrak{D}}$, $D\leq\frac{1}{2}(E_{\mathfrak{D}}+R_{\sigma})$ of (9.23)
GROUP12c:… GROUP12a:c1c2sq+… GROUP12b:c1c2sq+… suffix :S, :avg, :gate	the three arms of (9.24); after c1c2sq+ come three canonical singleton slots separated by +
GROUP1212a:b1b2sq+c1c2sq+… GROUP1212b:a1a2sq+c1c2sq+… suffix :S, :avg, :gate-$s$	the four arms of (9.25); after the two fixed squared groups come two canonical singleton slots separated by +
nonneg:x	$-x\leq 0$

Table C.2. SHA-256 of the files this paper depends on.

file	SHA-256
MANIFEST.sha256 (20/37 package)	7ba2202c473e0204baf7752a8fd41923
	82111ca4cd189a6db584e3912a3bcf43
final-report.raw.json.xz	f0412ad682389d463d410b96737144e6
	65afba13ef26c29f64c7a13f128e24e0
report (decompressed, normalized)	9cf43afd90bb683897290c18a9ebfb58
	697d0baafe8c9d2c6ae6ff71e8f5e2f7
normalize_completed_report.py	f38667a2fe45bda186c0ef0ae827f11c
	8c68cfac0976da043f7eba59bbd9c701
verify_tree_report_clean.py	9c301c46a2561e2d3c7c27a2c258186d
	66703d89a52f86d74c2f1e6604ad2d0d
verify_tree_report.py	d7abb356e4098127e775c4f003ef4bd8
	2660cbd734547154ab5f8b3f1b394f4a
verify_witness_clean.py	b795b735b3ec81177b57f6402b746d26
	2b5fae0a102eadc5f6b07777b9944cf3
audit_clause_compiler.py	ea40e6d7cbac17b5a2662b31e4d2b96a
	2ee3a1805ae137892d947311d15df929
compiler_differential_used.py	39ece2ea82da2cd5e221624707de6f0b
	4d5e7cd18a6599b3e53f02452f9072e3
run_verification.sh	dacd0fe7868341f22c4ed5b94a284492
	df3c8c45dc4f9da578800ba8b0db215b
FROZEN_VERIFICATION.stdout	3c7494813ddb89721817b77f48bdac05
	5f9bef2f298b3ca7291799e4565df947

Statements and declarations

Competing interests. The author has no competing interests.

Funding. No funding was received for this work.

Data availability. The certificates, the checking programs of Appendix C and their outputs accompany this paper. Their SHA-256 values are in Table C.2.