Appendix: why a local residual detects a column

This appendix derives $(5)$ in the main text. We cover the detection argument on pp. 15–29 of H needed for the basic-column construction. Three-variable rational splitting and the finite expansion are treated in the technical appendix to Chapter 10. Here we use only their analytic conclusions, not that chapter's active-cell bound. The discrete input to the continuous inverse theorem remains an external theorem; we do not claim to reprove it below.

1. Atoms and admissible quantitative operations

H, p. 15 · H, p. 16

Write $e(t)=\exp(2\pi\mathrm i t)$. A quadratic chart atom has the form

$C$ is a rational matrix, and $\lambda,\beta,\theta$ are unrestricted real parameters. The complexity $H\ge e^2$ controls $d\le\log H$, the rational height of $C$, and the support box and fixed-order Gevrey derivative bounds of $\chi$. A quasipolynomial composition of any fixed number of such budgets still has the form

A bounded atom means an atom with absolute value at most one on the whole real line.

Conjugation and products of a fixed number of atoms are implemented by changing the sign of the matrix and taking direct sums of horizontal coordinates, respectively. Translation may create a large integer horizontal shift, which cannot be put directly into the amplitude derivatives. First choose $P$ to clear the denominators of $C$. Write the shift as $m_0+a_0$, where $m_0\in P\mathbb Z^d$ and $\|a_0\|_\infty\le P$, and reindex the lattice points. $m_0$ enters only the constant and linear phases; the amplitude sees only the bounded shift $a_0$. Affine rescaling changes only the unrestricted real parameters. This proves the stability required in Lemma 4.2 on pp. 15–16 of H.

2. Separation of two columns along a four-term arithmetic progression

H, p. 20 · H, p. 21

Fix two source slots $i,k$, with the other slots denoted by $a,b$. For the source atom $\phi_i$, first choose fixed rational numbers $\alpha_j$ satisfying

The heights of these coefficients depend only on the four slots. Insert nonnegative Gevrey partitions of unity by integer translates in $\theta y_a,\theta y_b,\theta t$, and denote the lifted variables by $d_a,d_b,d$. Set

Since $y_j=y_a+(j-a)t$, $k_j$ is an integer vector. The support restrictions leave only quasipolynomially many possible values. Also $k_a=0$. Enforce these equalities with equality cutoffs that vanish exactly at every nonzero integer vector. The expansion remains exact.

Set $S=\sum_jj^2\alpha_j$. Direct substitution and the two vanishing-moment relations yield

The last term is linear in $x,t$ and can be distributed between $y_a,y_b$. The remaining coupled amplitude is a smooth function of $(d_a,d_b,d)$ in a bounded box. After multiplying by product cutoffs, expand it in a Fourier series. Each Fourier term separates into three amplitudes. Repeat for $\phi_k$ and multiply to obtain

All three factors are bounded atoms independent of the interval scale. By fixing a sufficiently high derivative order, the sum of absolute coefficients in the index shell $T\le1+\|\nu\|<2T$ is at most $DT^{-100}$, and the complexity within the shell is at most $(DT)^C$. The number of integrations by parts exceeds the Fourier dimension by a fixed constant. That dimension is at most $\operatorname{poly}(\log H)$, so the prefactor is still quasipolynomial. This is the full algebraic input to Lemma 4.5.

3. From a single scale to two separated moments

H, p. 21 · H, p. 22

Fix a term in $(\mathrm{B3})$. First choose a fixed nonnegative smooth compactly supported function $\zeta$ equal to one throughout the $t/|I|$ support range of every admissible local kernel. A fixed Gevrey cutoff suffices. Let the fixed constant $C_\zeta$ satisfy $\operatorname{supp}\zeta\subseteq[-C_\zeta,C_\zeta]$, set $r=|I|$, and define

Expand the smooth kernel in the coordinates $(y_a,y_b)$ into an absolutely summable Fourier series. Each term only modulates the two inputs. What remains is a convolution operator with kernel $Q(t)\zeta(t/r)$. Plancherel, the fixed coordinate Jacobian, and the normalization factors bound its bilinear norm by $CA_r$. The bounded factors $\psi_a,\psi_b$ do not increase the $L^2$ norms of the inputs.

If $A_r\ge\delta>0$, the passage from a large Fourier coefficient to rational splitting and a finite uniform expansion in the Chapter 10 appendix yields, uniformly on the fixed rescaled region $|t|\le C_\zeta r$,

The complexity and the sum of absolute coefficients are quasipolynomial in $H,\delta^{-1},\varepsilon^{-1}$. Here we need only a finite uniform expansion at a single scale; the absolute scale-sum tail estimate is not used.

Distribute $e(\gamma t)$ between the two slots. The remaining smooth kernel has controlled derivatives in the rescaled coordinates, so apply a finite Fourier separation to it. A smooth interval bump can be represented as a chart atom using one additional slow horizontal coordinate with zero matrix: map $I$ into the interior of an integer cell and restrict the amplitude support to that cell. Then only the selected lattice-point term contributes. We obtain an approximation by a finite sum of the form

with an error that can be prescribed arbitrarily in advance. Every factor is bounded, and all budgets remain quasipolynomial.

4. The discrete inverse theorem is a specified external input

H, p. 22 · H, p. 23 · Discrete inverse source, p. 1 · Discrete inverse source, p. 7 · Discrete inverse source, p. 8 · Discrete inverse source, p. 11 · Discrete inverse source, p. 12 · Discrete inverse source, p. 15

We use the $s=2$ case of Leng–Sah–Sawhney's Theorem 1.2, arXiv:2402.17994v3, p. 1: for $0<\delta<1/2$, if a 1-bounded function on an interval has $U^3$ norm at least $\delta$, then its correlation with a polynomial nilsequence adapted to a filtration of degree at most two has a quasipolynomial lower bound. The dimension is polynomial in the logarithm of the inverse threshold, while the complexity, Lipschitz norm, and inverse correlation bound are quasipolynomial. Definitions 3.3–3.5 on pp. 11–12 specify a rational Malcev basis, the lattice of integer coordinates of the second kind, and a Lipschitz norm that includes a supremum-norm term. The theorem does not require mean zero.

The interval norm follows Definition 1.1, p. 1: extend by zero to a sufficiently large cyclic group and divide by the same-order norm of the interval indicator. The polynomial orbit must be adapted to the stated filtration; see Definitions 2.5–2.7, pp. 7–8 and Definition 3.14, p. 15. We use an unconjugated correlation pairing. Conjugating the output function in the original theorem makes this change without altering the correlation lower bound, Lipschitz norm, or complexity.

This is the only deep inverse theorem not reproved in this chapter. The passage from that theorem to continuous chart atoms below follows pp. 23–26 of H. Large real orbit parameters must not enter the complexity.

5. Sampling a continuous function without an a priori sample bound

H, p. 23

Normalize $I$ to $[0,1)$, extend by zero to the circle group $\mathbb R/(16\mathbb Z)$, and define the $U^3$ norm using probability Haar measure. The mixed eight-vertex cube form is bounded by the product of the eight $L^2$ norms. To see this, divide the vertices into

The four linear forms in each group define an invertible integer change of the four Haar variables. Apply Cauchy–Schwarz first, then change variables in the two factors. Cube Cauchy–Schwarz also proves the triangle inequality, so this norm is continuous under $L^2$ convergence.

For $|g|\le1$, set

For bounded continuous functions, the discrete cube average before interval normalization converges to the continuous average. For general $g$, approximate in $L^1$ by a 1-bounded continuous function. Subtracting the eight factors one at a time bounds the error by eight times the $L^1$ error. Taking cell averages does not increase it. Hence the same convergence holds.

A nonzero cube supported in $[0,1)$ has its three difference variables lifted to $[-1,1]$, with all vertices in $[-3,4]$. Reduction modulo 16 creates no additional supported vertices. The denominator in the discrete interval normalization also tends to a fixed positive constant. Thus, for large $L$, $\|g_L\|_{U^3[L]}\ge c\delta$. No quantitative choice of $L$ is needed.

6. From nilsequences to chart atoms on integer inputs

H, p. 23 · H, p. 24 · H, p. 25

In coordinates of the second kind $(z,s)$ adapted to the quadratic filtration, the group law is

$B$ is a controlled rational bilinear map. In the two-step case, interchanging coordinate factors produces only central commutators, so this representation requires no infinite BCH series. The lattice is exactly the set of integer coordinates. A polynomial orbit satisfies $z(n)=z_0+n\theta$, and $s(n)$ is an ordinary vector polynomial of degree at most two.

Take a nonnegative Gevrey partition $\sum_m\rho(z-m)=1$. Right multiplication by the lattice point $(-m,0)$ yields

$\widetilde F$ is periodic in the central coordinates and has a controlled coordinate Lipschitz norm on the bounded horizontal box. The latter assertion follows directly from

Only the bounded coordinate $w'$ occurs here, not the large orbit coordinates.

Insert a horizontal cutoff, periodize, and approximate by a product Fejér kernel. At degree $N$, the error is at most the coordinate Lipschitz constant times $Cd\log(2N)/N$. Choose a quasipolynomial $N$ so that the error is less than one quarter of the correlation. The resulting finite sum of absolute Fourier coefficients is at most $CK(2N+1)^d$, which is still quasipolynomial.

For a central frequency $k$, define $z^TC_kw=k^TB(z,w)$. The corresponding term is

The outer phase is an ordinary quadratic phase, and the horizontal parameter is affine. After removing the shift as in Section 1, the expression is a chart atom. The nonnegative partition makes the atom bounded. Distributing the correlation over the finite coefficient sum shows that some atom on integer inputs $a(n)$ has correlation with $g_L$ at least $\kappa$, while $\log(1/\kappa)$ and the logarithm of the complexity are both $\operatorname{poly}(\log(1/\delta))$.

7. Exact floor interpolation removes dependence on the sample size

H, p. 25 · H, p. 26

Simply using the same formula to extend an atom from integer inputs to a continuous function may fail: the extension can oscillate arbitrarily within each sampling cell. First choose $P$ to clear the denominators of $C$. On integer inputs, reindex the lattice to replace $\theta$ by a representative satisfying $0\le\theta_j<P$. Reduce the correspondingly adjusted $\lambda,\beta$ modulo one to $[0,1)$. These reductions need preserve equality only at integer points.

Set $\alpha=2\lambda+\theta^TC\theta$ and $\Theta=(\theta,1,\alpha)^T$, and use the block matrix

Choose $0\le\eta\le1$ supported in $(0,1)$ and equal to one outside endpoint strips of total length at most $2\varepsilon$. Also choose a one-dimensional Gevrey partition of unity by integer translates $\rho_0$. The new amplitude is

The new atom associated with $(\Theta,\widetilde C)$, denoted by $A(v)$, satisfies exactly

Here $\{v\}=v-\lfloor v\rfloor\in[0,1)$. Indeed, the support forces the integer index $m=\lfloor v\rfloor$, while the other lattice sum equals one. Write $h=v-m$ and $w=\theta v-n$. The phase becomes

Rearranging this expression yields $\lambda m^2+\beta m+(\theta m)^TC(\theta m-n)$.

All parameters entering the amplitude are now controlled, and, with the explicit choice below, $\varepsilon^{-1}$ incurs only a quasipolynomial cost. The atom satisfies $|A|\le1$. The exact cell-average identity is

Replacing the atom by $A(Ly)$ incurs an error of at most $2\varepsilon$. First decrease the correlation lower bound to at most one and choose $\varepsilon=\kappa/8$ explicitly. This preserves a controlled correlation and keeps the inverse accuracy within the quasipolynomial budget. Rescaling by $v=Ly$ changes only the unrestricted real parameters. The final complexity is therefore independent of the unknown, possibly large $L$. This proves Lemma 4.9.

8. The closure step in the Hahn–Banach decomposition

H, p. 26

Take $0<\tau<1/2$ and $\sigma=\tau/2$. Let $\mathcal A$ be the family of all bounded atoms supplied by the preceding section at threshold $\sigma^2$, with correlation lower bound $\kappa$. Explicitly choose $M=\max(1,2\sigma/\kappa)$, preserving both the required lower bound and the quasipolynomial upper bound, and consider

This set contains an $L^2$ neighborhood of zero because $\|u\|_U\le C\|u\|_2$. If $|f|\le1$ but it is not in the $L^2$ closure of the set, the real Hahn–Banach theorem and the complex Riesz representation theorem provide $h\in L^2$ such that

The balanced summands imply, respectively,

For the first bound, test the $L^1$ ball with bounded simple functions; no unstated $L^1$ dual representation is needed. The first strict pairing implies $\|h\|_2>1$. Taking $u=h$ then yields $\|\sigma h\|_U>\sigma^2$. The continuous inverse theorem supplies a moment of size at least $\kappa/\sigma>M^{-1}$, a contradiction.

Hence $f$ belongs to the closure. Choose $z=s+u+v\in\mathcal B$ so that $\|f-z\|_2<\tau/2$, where $s$ is a finite structured combination. Add the $L^2$ approximation error $f-z$ to the original $L^1$-small term $v$. We obtain

All three parts belong to $L^2$. The atom complexity and $D_\tau$ are quasipolynomial in $\tau^{-1}$. No infinite structured sum in the closure has been treated as a finite catalog.

9. Two decompositions for local form detection

H, p. 27 · H, p. 28 · H, p. 29 · Return to original-column detection

For $R,g\in L^2(I)$ and two further bounded inputs, apply Cauchy–Schwarz successively along the other three nonzero slot directions. This yields

First expand the fixed smooth kernel in an absolutely summable Fourier series; linear modulation leaves the norms above unchanged. A change to two-slot coordinates also gives

Suppose $q>2$, $C_1\ge1$, $0<\delta<1/2$, and $\|R\|_{2,I}\le C_1$. The other inputs satisfy $\|h\|_{q,I}\le1$ and $\|u\|_{2,I},\|v\|_{2,I}\le1$, and the absolute value of the form exceeds $\delta$. Take

Truncate the test inputs at absolute value $B$. For $h$, the $L^2$ tail is at most $B^{-(q-2)/2}$. For $u,v$, the $L^{q'}$ tails are at most $B^{-(q-2)/q}$. Apply the local absolute form bounds with exponent tuples $(2,2,2,2)$ and $(2,q,q',2)$, respectively. The total error is less than $\delta/4$.

For $h_B/B$, apply $(\mathrm{B6})$ with accuracy

The sum of absolute structured coefficients is $A_1=BD_{\tau_1}$. The uniform-term error is bounded by the generalized von Neumann estimate at the start of this section, and the error from the $L^1$-small term is bounded by $(\mathrm{B7})$. Next decompose $u_B/B$, taking

The error remains controlled after summing over the first atoms. Thus some pair of bounded atoms satisfies

Apply the separation $(\mathrm{B3})$. First discard high indices by the absolute shell tail bound, then choose a term that remains large. The bilinear upper bound in Section 3 forces its $A_r$ to have a quasipolynomial lower bound, so the finite single-scale moment separation $(\mathrm{B4})$ applies. Every moment of $v_B$ has absolute value at most one. The finite coefficient sum therefore forces some atom moment of $R$ to have a quasipolynomial lower bound.

There are only two bounded-input decompositions, one arithmetic-progression separation, and one single-scale separation. The only truncation power depending on $q$ is $q/(q-2)$. It enters only as a multiplicative constant in $\log B$ and does not change the logarithmic exponent in these fixed compositions. This yields exactly $(5)$ in the main text. As $q\downarrow2$, the constants may diverge. We claim neither the endpoint $q=2$ nor constants uniform over all $q>2$.

10. Inputs and scope of this appendix

H, p. 15 · H, p. 22 · H, p. 23 · H, p. 26 · H, p. 27 · H, p. 28 · H, p. 29

The external inputs are the discrete quadratic inverse theorem, Hahn–Banach, Plancherel, and basic Fourier and Gevrey estimates. The first is used with the theorem and complexity conventions specified in Section 4 and is not reproved here. Three-variable rational splitting and the finite expansion come from the technical appendix to Chapter 10. This part uses neither active-cell counting nor an assumed basic catalog.

The algebraic separation in Section 2, the passage to continuous atoms in Sections 5–7, the closure argument in Section 8, and the two decompositions in Section 9 together prove the required local detection. Later catalog termination, the construction of actual histories, and global absorption are outside the scope of this appendix.