Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 16 / 3

The expectations use normalized counting measure on a finite abelian group $G$. This is the finite-group convention implicit in the averaging notation; an arbitrary infinite group has no normalized counting probability measure on all its points. For $h\in G$, define ${\Delta }_{h}f(x)=f(x)\overline{f(x+h)}$, and let $\mathcal{C}$ denote complex conjugation. The Gowers U3 norm isAveraging first over $h_3$ gives the Derivative identity for the Gowers U3 normIndeed, if $u(x)={\Delta }_{h_1}{\Delta }_{h_2}f(x)$, the average over $(x,h_3)$ is ${\mathbb{E}}_{x,h_3}u(x)\overline{u(x+h_3)}=|{\mathbb{E}}_{x}u(x){|}^2$. The eighth root is consequently well-defined. Homogeneity follows because the cube has four unconjugated and four conjugated factors, so $\Vert af{\Vert }_{U^3}=|a|\Vert f{\Vert }_{U^3}$. If the norm is zero, every squared term in the finite average vanishes. Taking $h_1=h_2=0$ gives ${\mathbb{E}}_x|f(x){|}^4=0$, so $f=0$ pointwise. This proves positive definiteness.

For the triangle inequality, we prove the needed Gowers-Cauchy-Schwarz inequality. For eight functions $F_{\omega }$ on a product of finite sets $X_1\times X_2\times X_3$, form the box norm multilinear averageFix a coordinate $j$. After averaging its two variables separately, this is $\mathbb{E}A\overline{B}$, where $A$ uses all vertices with ${\omega }_j=0$ and $B$ those with ${\omega }_j=1$, with the remaining parity conjugations. The Cauchy-Schwarz inequality giveswhere $S_j^b$ replaces the function at each vertex by the original function with its $j$th index set to $b$. Each right-hand average is a squared absolute value averaged over the other coordinates, hence nonnegative. Apply this operation successively for $j=1,2,3$, to every resulting factor. The eight final families each use one original $F_{\omega }$ at all vertices. Taking roots gives the box Cauchy-Schwarz inequalityNow take $X_j=G$ and $F_{\omega }(a,b,c)=f_{\omega }(a+b+c)$. With $x=a_0+b_0+c_0$ and $h_j=x_j^1-x_j^0$, these independent variables induce uniform $(x,h_1,h_2,h_3)$: each such tuple has exactly $|G{|}^2$ preimages. Therefore each box norm is the corresponding $U^3$ norm, and the mixed cube obeysExpand the eight factors in the cube expression for $f+g$. Its $2^8$ mixed terms are bounded by this inequality, and their bounds sum to $(\Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}{)}^8$. Thus $\boxed{\Vert f+g{\Vert }_{U^3}\le \Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}}$, completing the norm proof.

Two consequences will be useful below. Multiplication by a character of a finite abelian group leaves the norm unchanged, because the alternating character product around a three-dimensional cube equals one. Alsowhere the last inequality uses the $h=0$ term and $\Vert u{\Vert }_{U^2}^4={\sum }_{\chi }|\hat{u}(\chi ){|}^4\ge |\mathbb{E}u{|}^4$. Hence $\Vert f{\Vert }_{U^3}\ge |G{|}^{-1/8}\Vert f{\Vert }_2$.

Index the functions as $g_0,g_1,g_2,g_3$ and write $\Lambda ={\mathbb{E}}_{x,d}{\prod }_{j=0}^3{g}_j(x+jd)$. We first control $g_0$. Change variables to $y=x+3d$, average over $d$, and apply Cauchy-Schwarz in $y$, discarding the bounded factor $g_3(y)$. Expand the squared inner average with the second copy of $d$ written $d+h$, then put $x=y-3d$. This yieldsThe right side is real and nonnegative because it arose as an average of squared absolute values. Next use $y=x+2d$ and apply Cauchy-Schwarz in $(h,y)$, discarding the bounded $g_2$ derivative. Expanding with a displacement $k$ in $d$ givesFinally use $y=x+d$ and Cauchy-Schwarz in $(h,k,y)$, discarding the bounded $g_1$ double derivative. Expansion with displacement $r$ givesAll these changes of variables are bijections without any division in $G$.

Put $t_j=|G[j]|$, where $G[j]=\{z:jz=0\}$ is the torsion subgroup killed by an integer $j$. The variables $2k$ and $3h$ are uniform on $2G$ and $3G$, whose indices are $t_2,t_3$. Since the last squared integrand is nonnegative, its restricted average is at most $t_2{t}_3$ times the unrestricted average over the two increments. By part (i), that unrestricted average is $\Vert g_0{\Vert }_{U^3}^8$. Hence $|\Lambda |\le (t_2{t}_3{)}^{1/8}\Vert g_0{\Vert }_{U^3}$.

To control $g_1$, apply the same three eliminations in the order of slopes $3,0,2$. The surviving $g_1$ has increments $-2h,k,-r$. The last increment is uniform, and only the first is restricted to $2G$, so the resulting bound is $|\Lambda |\le t_2^{1/8}\Vert g_1{\Vert }_{U^3}$. Reversing the arithmetic progression by $(x,d)\mapsto (x+3d,-d)$ treats $g_3$ and $g_2$ respectively. This proves the four-term progression bound with torsion factors:For a fixed finite group, this positive constant tends to zero with $\alpha$. In ${\mathbb{Z}}_N$, $t_j=\gcd (j,N)$, so $\boxed{\beta =6^{1/8}\alpha \text{ suffices uniformly in }N}$. If multiplication by two and three are bijective, the sharper $\beta =\alpha$ holds.

A dependence on torsion is necessary if a bound uniform over all finite abelian groups is intended. In $G={\mathbb{F}}_2^m$, choose independent random signs $f(x)$. A cube with eight distinct vertices has sign product of expectation zero. Each of the twenty-eight possible collisions has probability $1/|G|$, so the expectation of $\Vert f{\Vert }_{U^3}^8$ is at most $28/|G|$. Some sign function therefore has norm at most $(28/|G|{)}^{1/8}$. But with factors $(f,1,f,1)$, every arithmetic progression is $(x,x+d,x,x+d)$ and its product is $f(x{)}^2=1$. Thus unbounded torsion obstructs uniform control of four-term progressions. The stated fixed-group bound, and the uniform cyclic-group bound needed in part (iii), are unaffected.

Let $\eta =|A|/N$ and $g=1_A-\eta$. In the norm convention, the quadratic uniformity of a set meansIf uniformity is parametrized instead by $\Vert g{\Vert }_{U^3}^8\le \alpha$, replace the parameter below by ${\alpha }^{1/8}$. We prove the genuine-progression conclusion by placing nonnegative weights on a region where wrapping and repeated entries are impossible.

First suppose $N\ge 16$. Put $M=\lfloor N/16\rfloor$, $J=\{0,\dots ,M-1\}$, $t=M/N$, and let $w=1_J\ast 1_J$ be the normalized convolution on a finite group. Define the weighted countBoth weights are nonnegative. Their supports require $0\le x\le 2M-2$ and $M\le d\le 3M-2$ in the ordinary representatives. In particular $d\ge 1$ and $x+3d\le 11M-8<N$. Every contributing arithmetic progression is therefore a set of four distinct integers in $\{0,\dots ,N-1\}$, with no modular wrap.

The averages of both weights are $t^2$. The convolution theorem on a finite group and the Parseval identity on a finite group giveTranslation multiplies coefficients by phases, so $w(d-M)$ has the same Fourier coefficient sum. Telescoping the product of the four indicators around ${\eta }^4$ produces four error terms, each with one factor $g$ and all other factors bounded by one.

To bound a weighted error, expand both weights in their finite Fourier series. For frequencies $r,s$, the extra character is $e^{2\pi i(rx+sd)/N}$. Write it asand absorb these two characters into the functions at slopes zero and one. Even if the balanced factor is one of those functions, its $U^3$ norm remains at most $\alpha$ by the character invariance proved in part (i). The cyclic bound of part (ii), with $C_0=6^{1/8}$, therefore bounds each unweighted Fourier term by $C_0\alpha$. Summing absolute coefficients costs at most $t^2$. ConsequentlySince $t\ge 1/32$ and $\eta \ge \delta$, this is positive whenever $\alpha <{\delta }^4/(4096C_0)$. A positive count supplies the required genuine arithmetic progression. This is the argument that triangular weights count genuine four-term progressions; it avoids losing powers of $\log N$ by cutting off a sharp interval.

For completeness, treat $4\le N<16$. If $A$ is a proper nonempty subset, then $\eta (1-\eta )\ge \delta /N$. The norm bound from part (i) givesChoose $\alpha$ below this bound as well. Then quadratic uniformity forces $A={\mathbb{Z}}_N$, which contains $\{0,1,2,3\}$. Thus, for every $N\ge 4$, a sufficient threshold isThe restriction $N\ge 4$ is necessary: for $N=1,2,3$, the full group has balanced subset indicator zero and is quadratically uniform for every positive parameter, but no subset has four elements. The printed conclusion needs this elementary size qualification.