\( \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} \)

Proof of the balanced decomposition lemma

Recall that norm-measure of vectors in $\NN^n$ is any assignment $\Nor:\NN^n\to\RR_+$ of nonnegative real numbers to vectors in $\NN^n$ such that every $0$-$1$ vector with at most one $1$ gets norm at most $1$, and the norm is monotone and subadditive: $\nor{x}\leq \nor{x+y}\leq \nor{x}+\nor{y}$ holds for all vectors $x,y\in\NN^n$.
Lemma 3 (Balanced decomposition lemma): If a set $B\subset\NN^n$ can be produced by a Minkowski circuit of size $t$, then $B$ is a union of $t$ sumsets $X+Y\subseteq B$ with the following property.
  1. $(\ast)$ For every norm-measure $\Nor:\NN^n\to\RR_+$, for every vector $\a\in B$ of norm $\nor{\a}>0$, and every $\bbal$ satisfying $1/\nor{\a}\leq \bbal < 1$ at least one of these sumsets $X+Y$ contains vectors $x\in X$ and $y\in Y$ such that $x+y=\a$ and \[ \tfrac{\bbal}{2}\cdot\nor{\a}<\nor{x}\leq \bbal\cdot \nor{\a}\,. \]

Proof: Let $\Phi$ be a Minkowski $(\cup,+)$ circuit of size $t$ producing the set $B$. Since we have only $t$ gates in the circuit, it is enough to show that the collection of sumsets $\pr{v}+\compl{v}$ associated with the gates $v$ of $\Phi$ has the desired property $(\ast)$. So, fix some norm-measure $\mu:\NN^n\to\RR_+$, some vector $\a\in B$ of norm $\mm:=\nor{\a}>0$, and a real number $1/\mm\leq \bbal < 1$.

By a decomposition of the vector $\a$ (or just a decomposition, because the vector $\a$ is fixed throughout the proof) at a gate $v$ we will mean a pair $(x,y)\in\pr{v}\times\compl{v}$ of vectors (if there is one) such that $x+y=\a$. The norm of such a decomposition is the norm $\nor{x}$ of the first vector (that in the set $\pr{v}$). Note that at the output gate, we have the unique decomposition $(x,y)=(\a,\vec{0})$ of $\a$ of norm $\nor{x}=\nor{\a}=\mm$.

Claim 2: Let $v$ be a gate entered from gates $u$ and $w$. If there is a decomposition $(x,y)$ of vector $\a$ at gate $v$, then there is a decomposition $(x',y')$ of $\a$ at $u$ or at $w$ such that $\tfrac{1}{2}\cdot\nor{x}\leq \nor{x'}\leq \nor{x}$.
Proof: If $v=u\cup w$ is a union gate, then $\pr{v}=\pr{u}\cup \pr{w}$ and, hence, $\compl{v}=\compl{u}\cap \compl{w}$. So, the same pair $(x,y)$ is a decomposition at the gate $u$ (if $x\in\pr{u}$) or at the gate $w$ (if $x\in\pr{w}$), and the claim is trivial in this case.

Assume now that $v=u+w$ is a Minkowski sum gate. Then $x=x_u+x_w$ for some vectors $x_u\in\pr{u}$ and $x_w\in\pr{w}$. Since vector $y$ belongs to the residue $\compl{v}$ of gate $v$, we know that $\pr{u}+\pr{w}+y\subseteq B$ holds. In particular, both inclusions $\pr{u}+(x_w+y)\subseteq B$ and $\pr{w}+(x_u+y)\subseteq B$ must hold. So, vector $x_w+y$ belongs to the residue $\compl{u}$ of gate $u$, and vector $x_u+y$ belongs to the residue $\compl{w}$ of gate $w$. This implies that the pair $(x_u,x_w+y)$ is a decomposition of vector $\a$ at the gate $u$, and the pair $(x_w,x_u+y)$ is a decomposition of $\a$ at the gate $w$. Since $x=x_u+x_w$, the monotonicity of the norm implies that both $\nor{x_u}$ and $\nor{x_w}$ are at most $\nor{x}$, while the subadditivity of the norm implies that one of the norms $\nor{x_u}$ and $\nor{x_w}$ of these decompositions must be at least $\tfrac{1}{2}\cdot\nor{x_u+x_w}=\tfrac{1}{2}\cdot\nor{x}$, and we can take that input $u$ or $w$ at which the decomposition has larger norm. $\Box$

We now start at the output gate with the unique decomposition $(x,y)=(\a,\vec{0})$ of the vector $\a$, and traverse an input-output path $P$ in the circuit backwards by using the following rule: if $v$ is a currently reached gate, and $(x,y)$ is a decomposition at this gate, then go to that of the two inputs of $v$ which has a decomposition $(x',y')$ of $\a$ of norm $\nor{x'}\geq \tfrac{1}{2}\cdot\nor{x}$ (if both input gates have this property, then go to any of them). Claim 2 ensures that we will eventually reach some input node.

If this input node holds the set $\{\vec{0}\}$, then the only decomposition $(x,y)=(\vec{0},\a)$ of vector $\a$ at this gate has norm $\nor{x}=\nor{\vec{0}}\leq 1$, and if this gate holds $\{\vec{e}_i\}$, then the only decomposition $(x,y)=(\vec{e}_i, \a-\vec{e}_i)$ of $\a$ at this gate has also norm $\nor{x}=\nor{\vec{e}_i}\leq 1$. In both cases, we have that $\nor{x}\leq 1$, which is at most $\bbal\mm$, because $\bbal\geq 1/\mm$.

On the other hand, the (also unique) decomposition $(x,y)=(\a,\vec{0})$ of the vector $a$ at the output gate has norm $\nor{x}=\nor{\a}= \mm$, which is strictly larger than $\bbal \mm$, because $\bbal <1$ and $\mm > 0$. So, there must be an edge $(u,v)$ in the path $P$ at which the jump from $\leq \bbal \mm$ to $> \bbal \mm$ happens. That is, there must be a decomposition $(x,y)$ at the gate $v$ and a decomposition $(x',y')$ at the gate $u$ such that $\nor{x} >\bbal \mm$ but $\nor{x'} \leq \bbal \mm$. By the above claim, we have $\nor{x'}\geq \tfrac{1}{2}\cdot\nor{x}$. We have thus found a sumset $\pr{u}+\compl{u}$ and vectors $x'\in \pr{u}$ and $y'\in\compl{u}$ such that $x'+y'=\a$ and $\tfrac{1}{2}\bbal \mm < \nor{x'}\leq \bbal \mm$, as desired. $\Box$

Back to "Notes on Monotone Arithmetic Circuits".