Growth from a slow decrease

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

This lesson proves the key step of the decay theorem (Lemma 2.1): if the Walsh norms of an operator decrease slowly between the indices $n-2m$ and $n$, then the Walsh norm at index $2(n-2m)$, almost twice as large, is still comparable to the one at $n$. The proof turns a Walsh test into three bounded scalar functions to which the coefficient lemma of A Fourier coefficient of binary rank two applies; a coefficient of binary rank $k\ge2$ then produces a Walsh test with $k$ independent factors. To make the scalar functions depend only on sign matrices, the vectors of the Walsh test are replaced by frames, linearly independent tuples, on which the general linear group over $\mathbb F_2$ acts transitively with prescribed pairings (Lemma 1.1).

Pairs of frames (Lemma 1.1).
Growth from a slow decrease (Lemma 2.1), in five steps.

The lesson follows [OpenAI-CC, Section 4.1]. Notation is that of Walsh norms and moment lifts: $V_n=\mathbb F_2^n$, $\chi(u,v)=(-1)^{u\cdot v}$, Walsh norms $w_n$, fixed-length cotype constants $c_m$, and the lift parameters $a,b$ of (3.1) there. For a function $h$ on a sign cube, $\mathcal Oh$ is its odd part.

1. Pairs of frames

A frame in $V_n$ is an ordered linearly independent tuple. Vectors and covectors are identified through the dot product; the group $\mathrm{GL}(n,\mathbb F_2)$ acts on primal frames by $U\mapsto HU=(Hu_i)$ and on covector frames by $V\mapsto H^{-\mathrm t}V$. The pairing matrix of a primal frame $U$ of length $r$ and a covector frame $V$ of length $s$ is $(u_i\cdot v_j)$, an $r\times s$ binary matrix; it is unchanged by $(U,V)\mapsto(HU,H^{-\mathrm t}V)$, since $Hu\cdot H^{-\mathrm t}v=u\cdot v$.

Lemma 1.1 (pairs of frames; [OpenAI-CC, Lemma 4.1]). The action $(U,V)\mapsto(HU,H^{-\mathrm t}V)$ of $\mathrm{GL}(n,\mathbb F_2)$ is transitive on pairs of frames of fixed lengths $r,s$ with a prescribed pairing matrix. If $n\ge r+s$, every binary $r\times s$ matrix is a pairing matrix.

Proof. Let $(U,V)$ and $(U',V')$ have the same pairing matrix. The maps $\pi(x)=(x\cdot v_j)_j$ and $\pi'(x)=(x\cdot v_j')_j$ from $V_n$ to $\mathbb F_2^s$ are surjective, since the $v_j$ and the $v_j'$ are independent. The isomorphism $\phi_0\colon\operatorname{span}U\to\operatorname{span}U'$, $u_i\mapsto u_i'$, satisfies $\pi'\phi_0=\pi$ on $\operatorname{span}U$, because the pairing matrices agree; so it maps $\operatorname{span}U\cap\ker\pi$ onto $\operatorname{span}U'\cap\ker\pi'$. The kernels have the same dimension $n-s$; extend the restriction of $\phi_0$ to an isomorphism $\kappa\colon\ker\pi\to\ker\pi'$. Together, $\phi_0$ and $\kappa$ define an isomorphism $\operatorname{span}U+\ker\pi\to\operatorname{span}U'+\ker\pi'$ with $\pi'H=\pi$. Choose a basis $c_1,\dots,c_t$ of a complement of $\operatorname{span}U+\ker\pi$; the vectors $\pi(c_l)$ are independent modulo $\pi(\operatorname{span}U)=\pi'(\operatorname{span}U')$. Choose $c_l'$ with $\pi'(c_l')=\pi(c_l)$ and put $Hc_l=c_l'$. Then $H$ is invertible, $HU=U'$, and $\pi'H=\pi$, which says $(Hx)\cdot v_j'=x\cdot v_j$ for all $x$, that is $H^{-\mathrm t}V=V'$.

For the second assertion, given a binary $r\times s$ matrix $D$, take $u_i=(e_i,0)$ and $v_j=(D_{:,j},e_j)$ in $\mathbb F_2^r\oplus\mathbb F_2^s\subseteq V_n$. $\blacksquare$

2. Growth from a slow decrease

Lemma 2.1 (growth; [OpenAI-CC, Lemma 4.2]). Let $m\ge1$ and $D_g,D_f\ge1$, and suppose that $m$ and the parameters $a,b$ of (3.1) of the previous lesson satisfy the hypotheses of Lemma 2.1 of A Fourier coefficient of binary rank two, with its constant $c_*$. Put $c_1=\min(1/2,c_*/2)$. If $\begin{gathered} c_m(G^*)\le D_g,\qquad c_m(F)\le D_f,\\ 0\ne T\colon G\to F, \end{gathered}$ and $n>4m$ satisfies $w_{n-2m}(T)\le2w_n(T), \tag{2.1}$ then $w_{2(n-2m)}(T)\ge c_1w_n(T). \tag{2.2}$ $T$ need not have finite rank.

Proof. Put $n'=n-2m$.

Step 1: exact Walsh signs. By (1.1) of the previous lesson there are $p_u\in G$ and $q_v\in F^*$, $u,v\in V_n$, with $\mathbb E_u\|p_u\|^2\le1$, $\mathbb E_v\|q_v\|^2\le1$ and $\gamma=\mathbb E_{u,v}\chi(u,v)\,q_v(Tp_u)\ge\tfrac12w_n(T)>0 .$ Let $T'$ be $T$ applied pointwise on $L_2(V_n\times V_n;G)$, and put $\begin{gathered} x_u'(\alpha,\beta)=(-1)^{u\cdot\beta+\alpha\cdot\beta}p_{u+\alpha},\\ y_v'(\alpha,\beta)=(-1)^{\alpha\cdot v}q_{v+\beta}. \end{gathered}$ By translation invariance of the uniform measure, $\|x_u'\|\le1$ and $\|y_v'\|\le1$. Modulo $2$, $\begin{aligned} u\cdot\beta+\alpha\cdot\beta&+\alpha\cdot v\\ &=(u+\alpha)\cdot(v+\beta)+u\cdot v, \end{aligned}$ so $\begin{aligned} y_v'(T'x_u')&=\chi(u,v)\,\mathbb E_{\alpha,\beta}\chi(u+\alpha,v+\beta)\\ &\qquad\cdot q_{v+\beta}(Tp_{u+\alpha})\\ &=\gamma\,\chi(u,v). \end{aligned}$ Amplify once more over $\mathscr G=\mathrm{GL}(n,\mathbb F_2)$: let $\widetilde T\colon\widetilde G\to\widetilde F$ be $T'$ applied pointwise on functions on $\mathscr G$, and put $x_u(R)=x_{Ru}'$, $y_v(R)=y_{R^{-\mathrm t}v}'$. For the bilinear form $\mathcal B(x,y)=y(\widetilde Tx)$, $\begin{gathered} x_u\in B_{\widetilde G},\qquad y_v\in B_{\widetilde F^*},\\ \mathcal B(x_u,y_v)=\gamma\,\chi(u,v), \end{gathered} \tag{2.3}$ since $Ru\cdot R^{-\mathrm t}v=u\cdot v$. The right translations $\Lambda(H)z(R)=z(RH)$, on $\widetilde G$ and on $\widetilde F^*$, are isometries, satisfy $\Lambda(H_1)\Lambda(H_2)=\Lambda(H_1H_2)$, preserve $\mathcal B$ when applied to both arguments, and $\Lambda(H)x_u=x_{Hu},\qquad\Lambda(H)y_v=y_{H^{-\mathrm t}v},$ because $(RH)^{-\mathrm t}=R^{-\mathrm t}H^{-\mathrm t}$. By Lemma 1.1(2) of the previous lesson, $w_j(\widetilde T)=w_j(T)$ for all $j$. By Section 2 there, $c_m(\widetilde F)\le D_f$ and $c_m(\widetilde G^*)\le D_g$, so the moment lifts of Lemma 3.2 there are available with the same $a,b$.

Step 2: equivariant lifts of frames. For a primal $m$-frame $U$ we want $P_{U,\varepsilon}\in B_{\widetilde G}$, $\varepsilon\in\{-1,1\}^m$, with $\begin{gathered} \mathbb E_\varepsilon\varepsilon_iP_{U,\varepsilon}=a\,x_{u_i}\quad(1\le i\le m),\\ \Lambda(H)P_{U,\varepsilon}=P_{HU,\varepsilon}. \end{gathered}$ Fix a frame $U_0$ and lifts $P_{U_0,\varepsilon}$ from Lemma 3.2 of the previous lesson, and replace them by their averages over the stabilizer $\{K:KU_0=U_0\}$ under $\Lambda$. The averages keep the moments, since $\Lambda(K)x_{u_i}=x_{Ku_i}=x_{u_i}$, lie in the unit ball, and are invariant under the stabilizer. For $U=HU_0$ put $P_{U,\varepsilon}=\Lambda(H)P_{U_0,\varepsilon}$. This is well defined, because two choices of $H$ differ on the right by a stabilizer element, and it is equivariant and has the required moments. The action on $m$-frames is transitive by Lemma 1.1. In the same way, with the action $H^{-\mathrm t}$, there are $Z_{V,\delta}\in B_{\widetilde F^*}$ for covector $m$-frames $V$, with $\begin{gathered} \mathbb E_\delta\delta_jZ_{V,\delta}=b\,y_{v_j},\\ \Lambda(H)Z_{V,\delta}=Z_{H^{-\mathrm t}V,\delta}. \end{gathered}$ By equivariance, the invariance of $\mathcal B$ and Lemma 1.1, the following numbers depend only on the displayed sign patterns and on $\varepsilon,\delta$: $\begin{aligned} \Phi(S,\varepsilon,\delta)&=\mathcal B(P_{U,\varepsilon},Z_{V,\delta}),\\ \phi(s,\varepsilon)&=\mathcal B(P_{U,\varepsilon},y_v),\\ \psi(t,\delta)&=\mathcal B(x_u,Z_{V,\delta}), \end{aligned}$ where $S_{ij}=\chi(u_i,v_j)$, $s_i=\chi(u_i,v)$ with $v\ne0$, and $t_j=\chi(u,v_j)$ with $u\ne0$. Every pattern occurs, since $n>4m\ge2m$. The moment identities and (2.3) give $\begin{aligned} &\mathbb E_\varepsilon\varepsilon_i\Phi(S,\varepsilon,\delta)\\ &\quad=a\,\psi(S_{i,:},\delta),\\ &\mathbb E_\delta\delta_j\Phi(S,\varepsilon,\delta)\\ &\quad=b\,\phi(S_{:,j},\varepsilon),\\ &\mathbb E_\varepsilon\varepsilon_i\phi(s,\varepsilon)=a\gamma\,s_i,\\ &\mathbb E_\delta\delta_j\psi(t,\delta)=b\gamma\,t_j . \end{aligned} \tag{2.4}$

Step 3: odd parts on a smaller cube. For all $\varepsilon,\delta$, the three numbers $\begin{gathered} \|\mathcal O\Phi(\cdot,\varepsilon,\delta)\|_\infty,\\ \|\mathcal O\phi(\cdot,\varepsilon)\|_\infty,\\ \|\mathcal O\psi(\cdot,\delta)\|_\infty \end{gathered} \tag{2.5}$ are at most $w_{n'}(T)$. Write $V_n=V_{n'}\oplus\mathbb F_2^m\oplus\mathbb F_2^m$ and fix $S_0=((-1)^{D_{ij}})$. For $u,v\in V_{n'}$ take the primal frame $U(u)_i=(u,e_i,0)$ and the covector frames $V^\pm(v)_j$, with $V^+(v)_j=(v,D_{:,j},e_j)$ and $V^-(v)_j=(v,D_{:,j}+\mathbf1,e_j)$, where $\mathbf1$ is the all-ones vector; the tags $e_i$, $e_j$ make them frames for every $u,v$. Their sign matrices are $\chi(u,v)S_0$ and $-\chi(u,v)S_0$, so $\begin{aligned} &\mathcal B\Bigl(P_{U(u),\varepsilon},\tfrac12\bigl(Z_{V^+(v),\delta}-Z_{V^-(v),\delta}\bigr)\Bigr)\\ &\quad=\chi(u,v)\,\mathcal O\Phi(S_0,\varepsilon,\delta). \end{aligned}$ The two families lie in the unit balls and depend only on $u$ and on $v$, respectively. Testing (1.1) of the previous lesson at $n'$ and using $w_{n'}(\widetilde T)=w_{n'}(T)$ gives the first bound. For $\phi$, keep $U(u)$ and use the nonzero covectors $(v,h,e_1)$ and $(v,h+\mathbf1,e_1)$, where $s_i=(-1)^{h_i}$, and half the difference of the corresponding $y$'s. For $\psi$, use the covector frame $(v,0,e_j)_j$ and half the difference of $x$'s at the nonzero vectors $(u,e_1,h)$ and $(u,e_1,h+\mathbf1)$, whose pairings with $(v,0,e_j)$ are $\chi(u,v)(-1)^{h_j}$ and its negative.

Step 4: a coefficient of rank at least two. Define the odd functions $\begin{aligned} f(s)&=\gamma^{-1}\,\mathcal O_s\,\mathbb E_\varepsilon\phi(\varepsilon s,\varepsilon),\\ g(t)&=\gamma^{-1}\,\mathcal O_t\,\mathbb E_\delta\psi(\delta t,\delta),\\ \Psi(S)&=\gamma^{-1}\,\mathcal O_S\,\mathbb E_{\varepsilon,\delta}\Phi(\varepsilon S\delta,\varepsilon,\delta), \end{aligned}$ where $\varepsilon s$ and $\delta t$ are entrywise products. Taking odd parts commutes with the averages, so by (2.5), (2.1) and $\gamma\ge w_n(T)/2$, all three sup norms are at most $w_{n'}(T)/\gamma\le4=M_0$. The substitution $s'=\varepsilon s$ and (2.4) give $\widehat f(e_i)=\gamma^{-1}\mathbb E_{s',\varepsilon}s_i'\varepsilon_i\,\phi(s',\varepsilon)=a,$ and likewise $\widehat g(e_j)=b$. For the row identity, note that $\mathbb E_\sigma\sigma_ih(\sigma S)$ does not change when $h$ is replaced by its odd part, because $\mathbb E_\sigma\sigma_ih(-\sigma S)=-\mathbb E_\sigma\sigma_ih(\sigma S)$. Substituting $\xi=\varepsilon\sigma$, and using (2.4) and that row $i$ of $\xi S\delta$ is $\xi_i\,\delta S_{i,:}$, $\begin{aligned} &\gamma\,\mathbb E_\sigma\sigma_i\Psi(\sigma S)\\ &=\mathbb E_{\xi,\varepsilon,\delta}\xi_i\varepsilon_i\,\Phi(\xi S\delta,\varepsilon,\delta)\\ &=a\,\mathbb E_{\xi,\delta}\xi_i\,\psi(\xi_i\,\delta S_{i,:},\delta)\\ &=a\,\mathbb E_\delta\tfrac12\bigl(\psi(\delta S_{i,:},\delta)-\psi(-\delta S_{i,:},\delta)\bigr)\\ &=a\gamma\,g(S_{i,:}). \end{aligned}$ Exchanging rows and columns gives $\mathbb E_\tau\tau_j\Psi(S\tau)=b\,f(S_{:,j})$. So the coefficient lemma applies: there is a binary matrix $P$ of rank $k\ge2$ with $|\widehat\Psi(P)|\ge c_*$. Since $\Psi$ is odd, $|P|$ is odd, and the coefficient is unchanged when the odd part is removed. With $\Phi_{\varepsilon,\delta}(S)=\Phi(S,\varepsilon,\delta)$, the substitution $S'=\varepsilon S\delta$ gives $\gamma\,\widehat\Psi(P)=\mathbb E_{\varepsilon,\delta}\Bigl[\prod_{i,j}(\varepsilon_i\delta_j)^{P_{ij}}\,\widehat{\Phi_{\varepsilon,\delta}}(P)\Bigr].$ So for some fixed $\varepsilon,\delta$ the function $h=\Phi_{\varepsilon,\delta}$ has $|\widehat h(P)|\ge c_*\gamma$.

Step 5: independent Walsh factors. Keep $P,\varepsilon,\delta$. For tuples $(u_i')_{i\le m}$ and $(v_j')_{j\le m}$ in $V_{n'}$ put $U_i=(u_i',e_i,0)$ and $V(D)_j=(v_j',D_{:,j},e_j)$ for binary $m\times m$ matrices $D$; these are frames, even if the tuples have repetitions or zeros. Their sign matrix has entries $(-1)^{u_i'\cdot v_j'+D_{ij}}$. Translating the uniform matrix $D$ by $(u_i'\cdot v_j')_{ij}$ in the Fourier average gives $\begin{aligned} &\mathcal B\Bigl(P_{U,\varepsilon},\mathbb E_D(-1)^{\langle P,D\rangle}Z_{V(D),\delta}\Bigr)\\ &\quad=\widehat h(P)\,(-1)^{\sum_{i,j}P_{ij}\,u_i'\cdot v_j'}, \end{aligned}$ with $\langle P,D\rangle=\sum_{i,j}P_{ij}D_{ij}$ modulo $2$. Both arguments lie in the unit balls; the first depends only on $(u_i')$, the second only on $(v_j')$. As $P$ has rank $k$, there are binary $m\times k$ matrices $I,J$ with $I^{\mathrm t}PJ=\mathrm{Id}_k$. For $\zeta,\eta\in(V_{n'})^k$ substitute $u_i'=\sum_{l=1}^kI_{il}\zeta_l,\qquad v_j'=\sum_{l=1}^kJ_{jl}\eta_l .$ The exponent becomes $\sum_l\zeta_l\cdot\eta_l$, the dot product of $V_{kn'}=(V_{n'})^k$. This is a Walsh test on $V_{kn'}$ with amplitude $\widehat h(P)$ and unit-ball families on both sides, so, by (1.1) and Lemma 1.1 of the previous lesson, $\begin{aligned} w_{2n'}(T)&\ge w_{kn'}(T)=w_{kn'}(\widetilde T)\\ &\ge|\widehat h(P)|\ge\tfrac{c_*}2\,w_n(T). \end{aligned}$ $\blacksquare$

3. Exercises

3.1. Show that for $r=s=1$ Lemma 1.1 says: $\mathrm{GL}(n,\mathbb F_2)$ acts transitively on pairs $(u,v)$ of nonzero vectors with $u\cdot v$ prescribed.

3.2. Verify the identity of Step 1: $u\cdot\beta+\alpha\cdot\beta+\alpha\cdot v$ equals $(u+\alpha)\cdot(v+\beta)+u\cdot v$ modulo $2$.

3.3. Why are the stabilizer averages in Step 2 needed? What goes wrong if the lifts are chosen independently for each frame?

3.4. Find binary $2\times2$ matrices $I,J$ with $I^{\mathrm t}PJ=\mathrm{Id}_2$ for $P=\begin{pmatrix}1&1\\0&1\end{pmatrix}$.

3.5. In Step 3, why does the vector $(u,e_1,h)$ need the tag $e_1$?

4. Solutions

3.1. Primal and covector frames of length one are nonzero vectors, and the pairing matrix is the number $u\cdot v$.

3.2. $(u+\alpha)\cdot(v+\beta)$ expands to $u\cdot v+u\cdot\beta+\alpha\cdot v+\alpha\cdot\beta$; add $u\cdot v$ and reduce modulo $2$.

3.3. Without equivariance, $\mathcal B(P_{U,\varepsilon},Z_{V,\delta})$ could depend on the pair of frames and not only on its sign matrix, and $\Phi$ would not be a function of $S$.

3.4. $P$ is invertible over $\mathbb F_2$ with $P^{-1}=P$. Take $I=\mathrm{Id}_2$ and $J=P$: then $PJ=P^2=\mathrm{Id}_2$.

3.5. If $u=0$ and $h=0$, the vector $(u,0,h)$ is zero, and $x_0$ is not covered by the definition of $\psi$, which needs a nonzero vector.

References

[OpenAI-CC] OpenAI, The cotype–cotype conjecture under the approximation property, OpenAI Math Release preprint, 23 September 2026, Section 4.1. https://github.com/openai/math/tree/main/preprints/The-cotype-cotype-conjecture-under-the-approximation-property-September-23-2026