From small-return increment bounds to a rational fast splitting

This chapter reconstructs the geometry-of-numbers argument in the proof of Lemma 4.3 on pages 17–18 of H, restricted to the one-parameter case needed in Lemma 6.1. The source is page 17 of the fixed October 5 version of An $L^3$ bound for the trilinear Hilbert transform. Page 41 applies this argument to the conclusion of the two-slot return analysis.

The preceding chapter turns a non-negligible two-slot correlation into a bound on the frequency increment of every sufficiently small return. This is the only analytic input used below. The proof compares successive minima of a body and its polar, bounds the numerators and denominators of a projection, and constructs a nonzero return with a quantitative lower bound on its length. The large real vector $V$ and the large real number $\Lambda$ do not enter the final complexity bound.

Back to the guide to H

1. Assumptions, conclusion, and the one-parameter scope

Let $d\ge0$ , let $C\in\mathbb Q^{d\times d}$ have entries of height at most $H\ge2$ , and let

V\in\mathbb R^d,\quad \Lambda\in\mathbb R

be arbitrary. Here $V$ is a single column vector, not a horizontal matrix with several parameter columns. Set

A=C-C^T,\quad C_{\mathrm{sy}}=\frac{C+C^T}{2},\quad C_{\mathrm{sk}}=\frac{C-C^T}{2}.

Choose a positive integer $P$ for which $PC$ is an integer matrix. This $P$ clears denominators; it is not the scale parameter in Section 6 of H.

Assume that there are $0<a\le1/2$ and $B_\Omega\ge1$ such that, for every

h\in\mathbb R,\quad m\in P\mathbb Z^d,\quad \delta=Vh-m,\quad |h|+\|\delta\|_2\le a

we have

|\Omega(h,m)|\le B_\Omega,\quad \Omega(h,m)=(2\Lambda+V^TCV)h-V^TAm. \tag{Return hypothesis}

In the two-slot argument we can take $B_\Omega=9$ , and its denominator-clearing integer $P_0$ can serve as $P$ here.

We seek a rational subspace $U\subset\mathbb R^d$ with orthogonal projections $P_f$ and $P_s=I-P_f$ such that

A|_{U\times U}=0,\quad V_f=P_fV,\quad V_s=P_sV,

\|V_s\|_2\le H',\quad |\Lambda_*|\le H',\quad \Lambda_*=\Lambda+\frac12V^TC_{\mathrm{sy}}V+V_f^TC_{\mathrm{sk}}V_s, \tag{Splitting target}

and both projections have rational height at most $H'$ .

The following uniform bound suffices:

H'=\exp\!\left(C_*(d+1)^4\mathcal T\right),\quad \mathcal T=1+\log H+\log P+\log(1/a)+\log(1+B_\Omega), \tag{Overall bound}

Here $C_*$ is a sufficiently large absolute constant. We first derive more explicit bounds for each step, then check that this expression dominates them.

2. Two returns produce an integer that must vanish

The absolute value of a matrix entry is at most its height, so

\|A\|_{\mathrm{op}}\le2dH.

Reduce the threshold to

a_0=\min\left(a,\frac1{100(1+B_\Omega+2dH)}\right).

Take two returns $Vh=m+\delta$ and $Vh'=m'+\delta'$ below this threshold. Since $V^TAV=0$ , direct expansion gives

\begin{aligned} \delta'^TA\delta &=(Vh'-m')^TA(Vh-m)\\ &=-h'V^TAm+hV^TAm'+m'^TAm, \end{aligned}

The first term in $\Omega$ cancels upon antisymmetrizing. Hence

h'\Omega(h,m)-h\Omega(h',m') =\delta'^TA\delta-m'^TAm. \tag{Antisymmetric identity}

This is an exact identity. No large term involving $V$ has been discarded.

Writing $m=Pz,m'=Pz'$ , we have

m'^TAm=P^2z'^T(C-C^T)z\in\mathbb Z

because $PC$ is an integer matrix. On the other hand,

|m'^TAm|\le2a_0B_\Omega+\|A\|_{\mathrm{op}}a_0^2<1.

this integer must vanish. Thus the integer displacements of all returns below the threshold $a_0$ satisfy the pairwise identities

m'^TAm=0. \tag{Integer isotropy}

This step requires a hypothesis on every small return and one common threshold for both returns.

3. The polar body and successive minima

First suppose $d\ge1$ . Define the centrally symmetric convex body

K=P^{-1}V[-1,1]+[-1,1]^d.

This Minkowski sum of a line segment and a cube is compact, convex, centrally symmetric, and contains the entire cube, so its interior is nonempty. It remains nondegenerate even when $V=0$ .

Its polar body is

K^\circ=\{q\in\mathbb R^d:\sup_{x\in K}|q\cdot x|\le1\}.

In this case we can compute the support function of the original body directly; it determines the polar:

\sup_{x\in K}|q\cdot x|=P^{-1}|q\cdot V|+\|q\|_1. \tag{Support function}

In particular, $K^\circ$ is also a centrally symmetric compact convex body with nonempty interior.

For $1\le j\le d$ , define

\lambda_j=\min\{t>0:tK\text{ contains }j\text{ linearly independent integer vectors}\},

and let $\mu_j$ be the corresponding minima of $K^\circ$ . Both sequences consist of finite positive numbers and are nondecreasing. Compactness and discreteness of the lattice ensure that these minima are attained.

4. The precise classical input

The only classical result from the geometry of numbers not reproved here is the upper bound in Minkowski's second theorem:

\left(\prod_{j=1}^d\lambda_j(B,\Gamma)\right)\operatorname{vol}(B) \le2^d\det\Gamma. \tag{Minkowski}

Its assumptions are that $B$ is a compact convex body centrally symmetric about the origin, with nonempty interior and that $\Gamma$ is a full-rank lattice. The source cited by H is Martin Henk, “Successive Minima and Lattice Points”, arXiv:math/0204158v1, Theorem 1.3 on page 2. That source states precisely this one-sided bound. Apply it with $B=K,K^\circ$ and $\Gamma=\mathbb Z^d$ ; both lattice determinants are $1$ . No stronger polar transference theorem is needed.

We now derive the required transference inequalities from this input.

5. A transference lower bound and a volume product

Choose $j$ independent integer vectors $x_1,\ldots,x_j\in\lambda_jK$ and $d+1-j$ independent integer vectors $q_1,\ldots,q_{d+1-j}\in\mu_{d+1-j}K^\circ$ .

If every cross inner product vanished, the latter span would lie in the orthogonal complement of the former. Its dimension $d+1-j>d-j$ makes this impossible. Hence some integer inner product is nonzero and has absolute value at least $1$ . The definition of the polar gives

1\le\lambda_j\mu_{d+1-j}. \tag{Transference lower bound}

For the upper bound, first establish a sufficient volume-product estimate. By compactness, in $K$ we can choose vectors $v_1,\ldots,v_d$ maximizing the absolute determinant of $T=(v_1,\ldots,v_d)$ . Since $K$ has interior, the maximum is positive. Put $B_1^d=\{t:\sum|t_j|\le1\}$ . Convexity and symmetry give

TB_1^d\subset K.

For any $x=Tt\in K$ , take the matrix $T$ and replace its column $j$ by $x$ . The new determinant is $t_j\det T$ . Maximality gives $|t_j|\le1$ , so

K\subset T[-1,1]^d.

Taking polars reverses inclusion:

K^\circ\supset T^{-T}B_1^d.

The cross-polytope $B_1^d$ is the union of $2^d$ simplices of volume $1/d!$ with disjoint interiors. Therefore

\operatorname{vol}(K)\operatorname{vol}(K^\circ) \ge|\det T|\frac{2^d}{d!}\,|\det T|^{-1}\frac{2^d}{d!} =\frac{4^d}{(d!)^2}. \tag{Volume product}

6. Derive the upper transference bound without a stronger theorem

Apply the Minkowski upper bound to $K$ and $K^\circ$ separately, and multiply:

\prod_{j=1}^d\lambda_j\mu_j \le\frac{4^d}{\operatorname{vol}(K)\operatorname{vol}(K^\circ)} \le(d!)^2.

This is the same product as $\prod_j\lambda_j\mu_{d+1-j}$ . Section 5 showed that each reverse-index factor is at least $1$ , so no single factor can exceed the whole product:

1\le\lambda_j\mu_{d+1-j}\le(d!)^2,\quad 1\le j\le d. \tag{Transference}

This is all the polar transference information required below.

7. A gap between successive minima gives an isotropic space

Put

L=16(d!)^2,\quad b_{\max}=\frac{a_0}{100P(d+2)}.

Here $L$ is only the gap ratio used in this argument. It is unrelated to a graph path length or the number of colours in H. Consider the $d+1$ disjoint half-open intervals

(b_{\max}L^{-j-1},\,b_{\max}L^{-j}],\quad j=0,\ldots,d.

There are only $d$ successive minima, so at least one interval contains no $\lambda_\nu$ . Denote its left endpoint by $b_0$ . Then

b_{\max}L^{-d-1}\le b_0\le b_{\max},\quad (b_0,Lb_0]\text{ contains no successive minimum}. \tag{Gap}

Define

U=\operatorname{span}_{\mathbb R}(\mathbb Z^d\cap b_0K),\quad r_0=\dim U.

Compactness of $b_0K$ makes its set of integer points finite, so $U$ is a rational subspace.

Every $n\in\mathbb Z^d\cap b_0K$ has a representation

n=P^{-1}Vh+w,\quad |h|\le b_0,\quad \|w\|_\infty\le b_0.

Set $m=Pn$ and $\delta=-Pw=Vh-m$ . Then

|h|+\|\delta\|_2\le b_0+P\sqrt d\,b_0\le a_0.

Thus these $m$ are displacements of small returns as in Section 2. Any two generators $n,n'$ satisfy $P^2n'^TAn=0$ , giving

A|_{U\times U}=0. \tag{Isotropy of the fast space}

If $r_0<d$ , the definition of the successive minima and the gap together imply

\lambda_{r_0+1}>Lb_0. \tag{Fast-slow gap}

The half-open endpoints matter: a minimum $\lambda=b_0$ is allowed and its directions are already included in $U$ , whereas $\lambda=Lb_0$ is excluded by the gap.

8. Short integer normals control both height and the slow part

First define $\beta=1/(16b_0)$ for every rank. If $r_0=d$ , take $P_f=I,P_s=0$ and skip the rest of this section. Otherwise, transference gives

\mu_{d-r_0}\le\frac{(d!)^2}{\lambda_{r_0+1}} <\frac{(d!)^2}{Lb_0}=\frac1{16b_0}=\beta.

There are therefore $d-r_0$ independent integer vectors $q_\nu\in\beta K^\circ$ . For every $n\in\mathbb Z^d\cap b_0K$ ,

|q_\nu\cdot n|\le\beta b_0=1/16<1.

the inner product is an integer, so it vanishes. The dimensions match exactly; hence these $q_\nu$ span $U^\perp$ .

The support-function formula above gives two distinct kinds of control at once:

\|q_\nu\|_1\le\beta,\quad |q_\nu^TV|\le P\beta. \tag{Two bounds on the normals}

The first bounds the integer coordinates and the projection height; the second bounds evaluation on the large vector $V$ . The first bound alone does not imply that $\|P_sV\|$ is bounded.

9. Expand the inverse Gram matrix without hiding a factor $\|V\|$

The following inverse-Gram and cofactor calculations apply only when the fast space is a proper subspace of the ambient space, so the number of rows is positive. In full dimension the slow projection has already been set to zero, and the uniform bound at the end of this section still applies.

Let $m_0=d-r_0$ , and arrange $q_\nu^T$ as the rows of an integer matrix $S$ . It has full row rank, and

G=SS^T,\quad P_s=S^TG^{-1}S.

The matrix $G$ is positive definite and integral. Thus $\det G$ is a positive integer and is at least $1$ .

Put $t=1+\beta\ge1$ . Entrywise,

|S_{\nu j}|\le t,\quad |G_{\nu\mu}|\le dt^2.

Expanding the determinant and cofactors gives

\det G\le m_0!(dt^2)^{m_0},\quad |\operatorname{cof}_{\nu\mu}G| \le(m_0-1)!(dt^2)^{m_0-1}. \tag{Integer Gram bounds}

When $m_0=1$ , the zeroth-order cofactor is $1$ , and the same formula applies.

Every entry of $P_s$ therefore has the common denominator $\det G$ , with numerator of absolute value at most

m_0^2t^2(m_0-1)!(dt^2)^{m_0-1}.

Reducing the fraction can only lower its height. For $P_f=I-P_s$ , adding $\det G$ to a numerator leaves a bound of the same form.

Crucially, use $SV$ directly, rather than bounding it by $\|S\|\|V\|$ :

|(SV)_\nu|\le P\beta\le Pt.

If $y=G^{-1}SV$ , the adjugate formula and $\det G\ge1$ give

|y_\nu|\le m_0(m_0-1)!(dt^2)^{m_0-1}Pt,

and hence

|(P_sV)_j|\le m_0^2t(m_0-1)!(dt^2)^{m_0-1}Pt.

All these quantities, together with $\|P_sV\|_2$ , are bounded by

Q=\bigl(4P(d+1)^2(1+\beta)^2\bigr)^{2d+4} \tag{Projection bound}

This deliberately generous expression absorbs square-root dimension factors, factorials, and the addition in $I-P_s$ . If $r_0=d$ , the same $Q$ remains a valid bound.

10. The pigeonhole return needs a lower bound on its length

An arbitrarily small nonzero return is not enough, because the final step divides by its length. We therefore construct a return with a quantitative positive lower bound.

Put

q=\left\lceil4/b_0\right\rceil,\quad M_0=q^d.

Partition $\mathbb T^d$ into $M_0$ half-open cubes with side length $1/q\le b_0/4$ . Take $M_0+1$ equally spaced times

t_j=\frac{jb_0}{M_0},\quad j=0,\ldots,M_0,

and consider $P^{-1}Vt_j\bmod\mathbb Z^d$ . Two points lie in the same small cube. Subtracting the earlier time from the later one gives

b_0/M_0\le h\le b_0,\quad P^{-1}Vh=n+\eta,\quad n\in\mathbb Z^d,\quad \|\eta\|_\infty\le b_0/4. \tag{Nonzero return}

Set $m=Pn$ and $\delta=P\eta$ . Then

|h|+\|\delta\|_2 \le b_0+P\sqrt d\,b_0/4\le a_0,

so the return hypothesis applies. Also,

n=P^{-1}Vh-\eta\in b_0K.

Thus $n\in U$ and hence $m\in U$ . The time difference is strictly positive, and its reciprocal satisfies

h^{-1}\le M_0/b_0,\quad M_0\le(1+4/b_0)^d. \tag{Reciprocal bound}

No Diophantine condition on $V$ is needed.

11. Cancel the large terms in the effective curvature

Write

F=P_fV,\quad V_s=P_sV,\quad \Delta=m-Fh=-P_f\delta.

Since $m,F\in U$ , we have $\Delta\in U$ and $\|\Delta\|_2\le\|\delta\|_2$ . Isotropy gives

F^TA\Delta=0,\quad V^TA\Delta=V_s^TA\Delta. \tag{Only the slow part remains}

In the one-parameter case $V^TC_{\mathrm{sk}}V=0$ , while

V^TAF=(F+V_s)^T(2C_{\mathrm{sk}})F =-2F^TC_{\mathrm{sk}}V_s.

We therefore have the exact identity

2\Lambda+V^TCV-V^TAF =2\left(\Lambda+\frac12V^TC_{\mathrm{sy}}V +F^TC_{\mathrm{sk}}V_s\right)=2\Lambda_*. \tag{Curvature identity}

Substituting $m=Fh+\Delta$ yields

\Omega(h,m)=2\Lambda_*h-V_s^TA\Delta.

The nonzero return from the preceding section now gives

|\Lambda_*| \le\frac{M_0}{2b_0} \left(B_\Omega+\|V_s\|_2\|A\|_{\mathrm{op}}\|\delta\|_2\right) \le\frac{M_0}{2b_0} \left(B_\Omega+Q(2dH)P\sqrt d\,b_0/4\right). \tag{Curvature bound}

The right-hand side contains no $\|F\|$ , $\|V\|$ , or $|\Lambda|$ . The large terms cancel in an exact identity before any estimates are applied.

12. Final parameter dependence and degenerate cases

Track the logarithms term by term. The definition of $a_0$ gives

\log(1/a_0)\le C(\mathcal T+\log(d+1)).

The choice $L=16(d!)^2$ and the gap construction give

\begin{aligned} \log(1/b_0) &\le\log(1/a_0)+\log(100P(d+2))+(d+1)\log L\\ &\le C\bigl(\mathcal T+(d+1)^2\log(d+2)\bigr). \end{aligned}

The projection, reciprocal, and curvature bounds then imply

\log\!\left(2+Q+\frac{M_0}{2b_0} \left[B_\Omega+Q(2dH)P\sqrt d\,b_0/4\right]\right) \le C(d+1)\bigl(\mathcal T+(d+1)^2\log(d+2)\bigr).

Since $\mathcal T\ge1$ and $\log(d+2)\le C(d+1)$ , this is controlled by the overall bound in Section 1. This completes the bounds for projection height, the slow part, and effective curvature.

If $d=0$ , no convex body or Gram matrix is needed. Take $h=a/2$ and the empty integer displacement $m=0$ . The return condition holds and $\Omega=2\Lambda h=\Lambda a$ , so

|\Lambda|\le B_\Omega/a.

Take $U=\{0\}$ ; the projections are empty matrices, assigned height $1$ . The overall bound still holds. If $d\ge1$ but $r_0=0$ , Sections 8–11 apply without change. If $r_0=d$ , use $P_s=0$ , but still control $\Lambda_*$ with the nonzero return from Section 10. A vanishing slow part does not eliminate the curvature step.

13. Return to Lemma 6.1 and separate the same-slot analysis

The two-slot return chapter gives $d\le2\log H$ , a denominator-clearing integer satisfying $\log P\le C(1+\log H)^3$ , and

B_\Omega=9,\quad \log(1/a)\le C(1+\log H+\log(1/\tau_2))^C.

Substitution into this chapter's overall bound yields

H'\le\exp\!\left(C(1+\log H+\log(1/\tau_2))^C\right).

This is the one-parameter version of (2) for the difference data. Choose $H_{\mathrm{ed}}\ge H'$ in advance from the uniform complexity of all columns. A two-slot correlation of absolute value greater than $\tau_2$ then forces the two tags to be joined by an edge, completing the contradiction for the distinct-slot branch.

The classical input has been stated precisely, and every remaining polar-body, projection, and curvature calculation has been given explicitly. This chapter does not prove all the matrix cases of Lemma 4.3 for general $1\le k\le3$ . In the multiparameter setting there is also the matrix term $V_s^TC_{\mathrm{sk}}V_s$ , and returns must be constructed along each parameter coordinate. A same-slot inner product must first yield the return hypothesis through smoothing and a one-dimensional Fourier energy argument. That analysis is treated separately in the next chapter.