Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 147 / 1

For $x_1,x_2\in X$, let $d(x_1,x_2)$ be the number of vertices of $Y$ adjacent to both. The required number $Q$ of ordered quadruples isThe Cauchy-Schwarz inequality first givesReverse the order of counting. A vertex $y\in Y$ contributes $\mathrm{deg}(y{)}^2$ ordered pairs, so a second application of Cauchy-Schwarz and the assumed edge density of a bipartite graph giveTherefore the bipartite four-cycle count is

Write $1_A$ for the indicator function and use the normalized Fourier analysis on a finite abelian groupThere are $N^5$ sextuples satisfying the equation, since any five coordinates determine the sixth. The desired probability is consequentlyBy orthogonality of complex exponentials, the indicator of the equation isSubstitution makes all six sums independent and gives the sixth Fourier moment as a three-sum collision count:Because $1_A$ is real, $\hat{A}(-r)=\overline{\hat{A}(r)}$. Hence the probability is

We prove the polynomial nonvanishing below the field size by mathematical induction on $n$. The case $n=1$ is the Lagrange root bound over a field: a nonzero polynomial of degree below $p$ cannot have all $p$ elements of ${\mathbb{F}}_p$ as roots.

For the induction step, suppose that $P$ vanishes on all of ${\mathbb{F}}_p^n$ and writeThe upper limit is valid because the total degree of a polynomial is less than $p$. Fixing the first $n-1$ variables produces a univariate polynomial of degree below $p$ which vanishes at every $x_n\in {\mathbb{F}}_p$. It is therefore the zero polynomial, so every $P_j$ vanishes on all of ${\mathbb{F}}_p^{n-1}$. Each $P_j$ also has total degree below $p$, and the induction hypothesis gives $P_j=0$ for every $j$. Thus $P=0$.

Taking the contrapositive, every nonzero such $P$ has some $a\in {\mathbb{F}}_p^n$ for which

Remove the quadratic phase by settingThe phase around the parallelogram isso the hypothesis says exactly that $\Vert g{\Vert }_{U^2}^4\ge c$, with harmless negative choices of the increments. The Fourier identity for the Gowers U2 norm and the Parseval identity now givewhere the last inequality uses $\Vert f{\Vert }_{\infty }\le 1$. Thus the Quadratic phase detection by the Gowers U2 norm supplies an $r\in {\mathbb{Z}}_N$ such that