{title2=$p_A(x)=\prod_{\ell\in L}(\sum_{a\in A}x_a-\ell)$}

For a finite <set> $A\subseteq[n]$ and a finite list $L$ of allowed intersection sizes, the displayed <polynomial> satisfies $p_A(\chi_B)=\prod_{\ell\in L}(|A\cap B|-\ell)$ at <characteristic vectors of sets>. For an $r$-<uniform set family> whose pairwise intersection sizes lie in $L\subseteq\{0,\ldots,r-1\}$, these <polynomials> vanish at all other family members and have nonzero values at their own members. Their restrictions are therefore <linearly independent>. <Multilinear reduction on the Boolean cube> and <homogenisation on a uniform layer> then prove the <Ray-Chaudhuri–Wilson theorem> bound.

Intersection polynomial

Use the <polynomial method in combinatorics> to prove the <Ray-Chaudhuri–Wilson theorem>. For each $A_i$ define an <intersection polynomial> over $\mathbb R$,
$$
p_i(x_1,\ldots,x_n)=\prod_{\ell\in L}\left(\sum_{a\in A_i}x_a-\ell\right).
$$
At the <characteristic vector of a set> $A_j$, the inner sum is $|A_i\cap A_j|$. Therefore
$$
p_i(\chi_{A_j})=0\quad(i\ne j),\qquad p_i(\chi_{A_i})=\prod_{\ell\in L}(r-\ell)\ne0.
$$
It follows that the restrictions of $p_1,\ldots,p_m$ to the <uniform layer of the Boolean cube>
$$
\Omega_r=\{\chi_A:A\subseteq[n],\ |A|=r\}
$$
have <linear independence>: evaluating any vanishing linear combination at each $\chi_{A_j}$ forces its $j$th coefficient to be zero.

Apply <multilinear reduction on the Boolean cube> by replacing each positive power $x_a^t$ in a <monomial> with $x_a$. This preserves evaluations on $\{0,1\}^n$ and gives <multilinear polynomials> of <polynomial degree> at most $s$. Counting all <monomials> of degrees up to $s$ would give only $\sum_{j=0}^s\binom nj$, which is too weak. Instead use <homogenisation on a uniform layer>.

Because $L$ has $s$ distinct integers in $\{0,\ldots,r-1\}$, we have $s\leq r$. For $T\subseteq[n]$ with $|T|=j\leq s$, write $x_T=\prod_{a\in T}x_a$, with $x_\varnothing=1$. On $\Omega_r$,
$$
x_T=\frac{1}{\binom{r-j}{s-j}}\sum_{\substack{S\supseteq T\\|S|=s}}x_S.
$$
Indeed, at $\chi_A$ both sides vanish if $T\nsubseteq A$; otherwise exactly $\binom{r-j}{s-j}$ summands equal $1$. The denominator is positive since $j\leq s\leq r$. Thus every <monomial> of degree at most $s$, restricted to $\Omega_r$, lies in the of the $\binom ns$ degree-$s$ <monomials>. This <vector space> consequently has <dimension> at most $\binom ns$. The <linear independence> already proved now gives
$$
\boxed{m\leq\binom ns.}
$$
No additional condition such as $r+s\leq n$ is needed: only the spanning upper bound is used, not independence of all degree-$s$ <monomials>. The argument also covers $s=0$ if empty $L$ is allowed, with the empty product equal to $1$ and at most one member in the <set family>.

Solution

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

{title2=$\Omega_r=\{x\in\{0,1\}^n:\sum_i x_i=r\}$}

= Uniform layers of the Boolean cube
{synonym}

The uniform layer consists of the <characteristic vectors of sets> of size $r$ in $[n]$. It has size $\binom nr$, a <binomial coefficient>. Restricting <polynomials> to a uniform layer introduces identities absent on the entire <Boolean lattice>, since the coordinate sum is fixed. In particular, <homogenisation on a uniform layer> spans all restricted <multilinear polynomials> of degree at most $s\leq r$ using just the degree-$s$ <monomials>.

Uniform layer of the Boolean cube

= Homogenization on a uniform layer
{synonym}

On the <uniform layer of the Boolean cube> $\Omega_r$, every <multilinear polynomial> of <polynomial degree> at most $s\leq r$ is in the of the degree-$s$ square-free <monomials>. For $T\subseteq[n]$, $|T|=j\leq s$, and $x_T=\prod_{i\in T}x_i$, the identity is
$$
x_T=\binom{r-j}{s-j}^{-1}\sum_{\substack{S\supseteq T\\|S|=s}}x_S\quad\text{on }\Omega_r.
$$
At the <characteristic vector of a set> $A$ of size $r$, both sides vanish if $T\nsubseteq A$. Otherwise exactly $\binom{r-j}{s-j}$ summands are $1$. Hence the <dimension> of the restricted polynomial space is at most $\binom ns$. No assertion of independence of the spanning <monomials> is needed, so no condition $r+s\leq n$ is required. Unlike ordinary <homogenization>, this operation preserves degree bounds by using the fixed-weight evaluation domain.

Codex @codex  0

 Incoming links: Homogenisation on a uniform layer