# Polynomial designs

For a family $\f$ of sets and a real number $l\geq 0$, let $\ddeg{\f}{l}$ denote the maximal possible number of sets in $\f$ containing a fixed set with $l$ (or more) elements. In other words, $\ddeg{\f}{l}$ is the maximal possible number of sets in $\f$ whose intersection has $l$ (or more) elements. In particular, if $m$ is the maximum cardinality of a set of $\f$, then $|\f|=\ddeg{\f}{0}\geq \ddeg{\f}{1}\geq \ldots\geq \ddeg{\f}{m}=1$, and $\ddeg{\f}{l}=0$ for all $l>m$. Note that a nonempty $m$-uniform family $\f$ is an $(m,d)$-design if and only if $\ddeg{\f}{d}=1$. Also, $\ddeg{\f}{1}=1$ means that all sets of $\f$ are disjoint.

Let $m$ be a prime power, $1\leq d\leq m$ an integer, and consider the grid $\gf{m}\times\gf{m}$. The polynomial $(m,d)$-design $\f$ consists of all $|\f|=m^d$ subsets $S$ of points in this grid of the form $S=\{(a,p(a))\colon a\in \gf{m}\}$ for a univariate polynomial $p=p(x)$ of degree at most $d-1$ over $\gf{m}$. Note that no two points of any of these sets $S$ lie in the same row of the grid.

The main combinatorial property of polynomial designs is the following.

Lemma: Let $\f$ be a polynomial $(m,d)$-design, and $1\leq d\leq m$. For every set of $l\leq d$ points of the grid $\gf{m}\times\gf{m}$, with no two in the same row, exactly $m^{d-l}$ sets of $\f$ contain this set. In particular, $\ddeg{\f}{l}\leq m^{d-l}$ holds for every $0\leq l\leq d$.
Proof: This is a direct consequence of a standard result in polynomial interpolation. For any $l\leq d$ distinct points $(a_1,b_1),\ldots,(a_l,b_l)$ in $\gf{m}\!\times\! \gf{m}$, the number of polynomials $p(x)$ of degree at most $d-1$ satisfying $p(a_1)=b_1,\ldots,p(a_l)=b_l$ is either $0$ (if $a_i=a_j$ holds for some $i\neq j$) or is exactly $m^{d-l}$: this latter number is exactly the number of solutions of the corresponding system of linear equations, with coefficients of $p$ viewed as variables. $\Box$

Back to "Notes on Monotone Arithmetic Circuits".