The <Frankl-Wilson theorem> says that if $p$ is prime, $L\subseteq\mathbb F_p$ has $s\leq\min\{r,n-r\}$ elements, and $\mathcal F\subseteq[n]^{(r)}$ satisfies
$$
|A\cap B|\bmod p\in L\quad(A\ne B),
\qquad
r\bmod p\notin L,
$$
then $|\mathcal F|\leq\binom ns$.

For each $A\in\mathcal F$, form the multilinearization on the Boolean cube of
$$
P_A(x)=\prod_{\ell\in L}
\left(\sum_{i\in A}x_i-\ell\right).
$$
At the <characteristic vector of a set> $\mathbf1_B$, this polynomial vanishes for $B\ne A$ and is nonzero for $B=A$. Hence the restricted functions $P_A$ are linearly independent. On the $r$-slice, every square-free monomial of degree below $s$ can be raised to degree $s$ using the relation $\sum_i x_i=r$, so the degree-at-most-$s$ function space is spanned by the $\binom ns$ square-free degree-$s$ monomials. Linear independence gives the theorem.

Solution

Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 109 / 4 / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-109/4/solution