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.

- $(\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}$.

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