\( \def\<#1>{\left<#1\right>} \newcommand{\OR}[1]{\mathrm{OR}(#1)} \newcommand{\XOR}[1]{\mathrm{XOR}(#1)} \newcommand{\SUM}[1]{\mathrm{SUM}(#1)} \newcommand{\Geq}{\succcurlyeq} \newcommand{\Leq}{\preccurlyeq} \newcommand{\co}[1]{\overline{#1}} \newcommand{\rk}{{\rm rk}\,} \newcommand{\oA}{\overline{A}} \newcommand{\oB}{\overline{B}} \newcommand{\oM}{\overline{M}} \newcommand{\pr}[1]{\mathrm{rk}_+(#1)} \newcommand{\br}[1]{\mathrm{rk}_{\lor}(#1)} \newcommand{\FF}{\mathbb{F}_2} \newcommand{\dec}[1]{\chi(#1)} \newcommand{\Dec}[2]{\chi_{#2}(#1)} \newcommand{\nc}[1]{\mathfrak{nc}(#1)} \newcommand{\cc}[1]{\mathfrak{c}(#1)} \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \newcommand{\FF}{\mathbb{F}} \newcommand{\f}{\mathcal{F}} \newcommand{\Un}[1]{L(#1)} % Minkowski complexity \newcommand{\Unr}[2]{L_{#2}(#1)} \newcommand{\Unn}[1]{L^*(#1)} \newcommand{\gf}[1]{\mathrm{GF}(#1)} %\newcommand{\gf}[1]{\FF_{#1}} \newcommand{\cont}[1]{A_{#1}} \newcommand{\arithm}[1]{\mathrm{Arit}(#1)} \newcommand{\Nor}{\mu} % norm without argument \newcommand{\nor}[1]{\Nor(#1)} \newcommand{\nnor}[2]{\Nor_{#2}(#1)} \newcommand{\compl}[1]{Y_{#1}} \newcommand{\pr}[1]{X_{#1}} \newcommand{\mm}{p} \newcommand{\a}{b} \newcommand{\skal}[1]{\langle #1\rangle} \def\bar#1{\underline{#1}} \newcommand{\mon}[1]{\mathrm{mon}(#1)} \newcommand{\ddeg}[2]{\#_{#2}(#1)} \newcommand{\err}{\epsilon} \newcommand{\bal}{\gamma} \newcommand{\bbal}{\gamma} \)

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".