\( \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} \newcommand{\Binom}[2]{E^{#1}_{#2}} \newcommand{\sel}[2]{E^{n}_{#1,#2}} \)

Hard to produce but easy to approximate sets

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