Fact: There exist $2^{2^{\Omega(n)}}$ sets $A\subseteq\{0,1\}^n$ such that $\Un{A}\geq 2^{\Omega(n)}$ but each of these sets can be approximated within a factor $r=1+o(1)$ by a single Minkowski circuit of size $O(n^2)$.Proof: Let $\Binom{n}{k}$ denote the set of all $|\Binom{n}{k}|=\binom{n}{k}$ vectors $a\in\{0,1\}^n$ with exactly $k$ ones.
Claim 1: For every $1\leq k\leq n$, the set $\Binom{n}{k}$ can be produced by a Minkowski circuit of size at most $2nk$, that is, $\Un{\Binom{n}{k}}\leq 2kn$.Proof: For $k\leq m\leq n$, let $\sel{m}{k}\subseteq \Binom{n}{k}$ consists of all vectors in $\Binom{n}{k}$ whose all $1$s are among the first $m$ positions. In particular, $\sel{m}{1}=\{\vec{e}_1,\ldots,\vec{e}_m\}$ and $\sel{m}{m}= \{\vec{e}_1+\cdots+\vec{e}_m\}$. The Pascal identity $\binom{m+1}{l}=\binom{m}{l}+\binom{m}{l-1}$ for binomial coefficients suggests to construct a Minkowski circuit using the recursion \[ \sel{m+1}{l}=\sel{m}{l}\cup \left(\sel{m}{l-1}+\{\vec{e}_{m+1}\}\right)\,. \] The resulting circuit has at most $2nk$ gates and produces the set $\Binom{n}{k}=\sel{n}{k}$. $\Box$
A set $C\subset\Binom{n}{k}$ is a Hamming code if every two vectors differ in $> 2$ positions.
Claim 2: For every $1\leq k\leq m$ a Hamming code $C\subset\Binom{n}{k}$ of size $|C|\geq \binom{n}{k}/2n$ exists.Proof: Let $l=\lfloor\log_2 n\rfloor+1$, and let $H=[v_1,\ldots,v_n]$ be a Boolean $l\times n$ matrix whose $i$th column $v_i$ is the binary representations of the integer $i$; hence, $v_i\neq v_j$ for all $i\neq j$. Associate with every vector $b\in \{0,1\}^l$, let $C_b$ be the set of all vectors $x\in\Binom{n}{k}$ such that $H\cdot x=b \mod{2}$ holds. We claim that each of the sets $C_b$ is a Hamming code. Assume to the contrary that some two vectors $x\neq y$ of $C_b$ differ in only the positions $i$ and $j$. Then $\vec{0}=Hx\oplus Hy=H(x\oplus y)=H(\vec{e}_i\oplus \vec{e}_j)$, which can only happen if $v_i=v_j$, a contradiction. So, each of the $2^l\leq 2n$ sets $C_b$ is a Hamming code, and at least one of them has $|C_b|\geq \binom{n}{k}/2n$ vectors, as desired. $\Box$
Claim 3: Let $2\leq k\leq n-2$ be a Hamming code $C\subset\Binom{n}{k}$. The set $B=\Binom{n}{k-1}$ approximates each of the $2^{|C|}$ sets $\Binom{n}{k}\setminus C\subseteq A\subseteq \Binom{n}{k}$ within the factor $r=1+1/(k-1)$.Proof: Since $r=k/(k-1)$, it is enough to show that the set $\Binom{n}{k-1}$ lies below any such set $A$. Take an arbitrary vector $x\in \Binom{n}{k-1}$. Since $k\leq n-2$, there are two positions $i$ and $j$ with $x_i=x_j=0$. Consider the the vectors $y=x+\vec{e}_i$ and $z=x+\vec{e}_i$ in $\binom{n}{k}$. Since these vectors differ in only two positions, the cannot both belong to the Hamming code $C$. So, at least one of them belongs to our set $A$ and contain the vector $x$. $\Box$
When applied with $k:=n/2$, Claims 2 and 3 give us $N\geq 2^{\binom{n}{k}/2n}=2^{2^{\Omega(n)}}$ sets $A\subseteq\Binom{n}{k}$ each of which, by Claim 1, is approximated within the factor $r=1+o(1)$ by a single set $B=\Binom{n}{k}$ with $\Un{B}\leq 2nk=n^2$. On the other hand, there are only $M(t)\leq (t+n)^{O(t)}$ distinct Minkowski circuits of size $\leq t$ (by a standard argument used for Boolean circuits). Since no Minkowski circuit can produce two distinct sets, we need $t$ be as large as $2^{\Omega(n)}$ to ensure $M(t)\geq \tfrac{1}{2}\cdot N$. So, $\Un{A}=2^{\Omega(n)}$ holds for at least $N/2$ of these sets $A$. $\Box$
Back to "Notes on Monotone Arithmetic Circuits".