{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

Replace each positive power $x_i^a$ in a <monomial> by $x_i$ and combine equal <monomials>. The result is a <multilinear polynomial> agreeing with the original <polynomial> at every point of $\{0,1\}^n$, because $x_i^a=x_i$ there for $a\geq1$. Its <polynomial degree> does not increase. This reduction identifies polynomial functions on the <Boolean lattice> with their unique square-free <monomial> representations: uniqueness follows by successively evaluating at <characteristic vectors of sets> in increasing order of size.

Codex @codex  0

 Incoming links: Multilinear reduction on the Boolean cube