Lemma: There are explicit Sidon sets $A\subseteq\{0,1\}^n$ such that $\Un{A}\geq 2^{n/4}$ but $\Unr{A}{r}\leq n$ for the approximation factor $r=2$.Proof: Let $m$ be an odd integer, and $n=4m$. Consider the cubic parabola $C=\{(z,z^3)\colon z\in \{0,1\}^m\}\subseteq \gf{2^{2m}}$. As customary, we view vectors in $z\in\{0,1\}^m$ as coefficient-vectors of polynomials of degree at most $m-1$ over $\gf{2}$ when rising them to a power. As shown in Example 2, $C$ is a Sidon set. The set $C$ may be non-nomogeneous, i.e. vectors $c\in C$ may have different weights $|c|=\skal{c,c}$. We make the set homogeneous by taking pairs of complementary vectors: \[ A= \{(c,\bar{c})\colon c\in C\}=\left\{(a,a^3,\bar{a},\bar{a^3})\colon a\in\{0,1\}^m\right\}\subseteq\{0,1\}^{n}\,, \] where $\bar{a}$ denotes the componentwise negation of $a$; for example, if $a=(0,0,1)$ then $\bar{a}=(1,1,0)$. This set is already uniform: every vector of $A$ has exactly $2m$ ones. The set $A$ is also a Sidon set because the set $C$ was such. So, Theorem 4 yields the lower bound $\Un{A}\geq |A|=2^m=2^{n/4}$ on the size of Minkowski circuits producing the set $A$. It remains therefore to prove the upper bound $\Unr{A}{2}\leq n$.
Our approximating Minkowski circuit will produce the set $B=B'\cup B''$, where \[ B'=\{(a,0,\bar{a},0)\colon a\in \{0,1\}^m\}\ \ \mbox{ and }\ \ B''=\{(0,a,0,\bar{a})\colon a\in \{0,1\}^m\}\,. \] It is not difficult to see that $B$ is the set of exponent vectors of the polynomial $f(x)=g(x)+h(x)$, where \begin{align*} g(x)&=\sum_a\ \prod_{i=1}^m x_i^{a_i}\cdot \prod_{i=2m+1}^{3m} x_{i}^{1-a_{i}}\qquad\mbox{and}\qquad h(x)=\sum_a\ \prod_{i=m+1}^{2m} x_i^{a_i}\cdot\sum_{i=3m+1}^{4m} x_{i}^{1-a_i} \end{align*} with both sums taken over all vectors $a\in\{0,1\}^{4m}$. Since \[ g(x)=(x_1+x_{2m+1})(x_2+x_{2m+2})\cdots (x_m+x_{3m}) \] and similarly for $h(x)$, the polynomial $f$ can be computed by an arithmetic $(+,\times)$ circuit using only $4m=n$ gates. This shows $\Un{B}\leq n$.
It remains to show that the set $B$ $2$-approximates our Sidon set $A$.
For every vector $x=(a,a^3,\bar{a},\bar{a^3})$, we have $\skal{x,x}=2m$. Thus, $\skal{x,y}\geq m=\tfrac{1}{2}\cdot\skal{x,x}$ holds for the vector $y=(a,0,\bar{a},0)$. It remains to show that the set $B$ lies below the set $A$, i.e. that for every $x\in A$ there is an $y\in B$ such that $y\leq x$. That the first subset $B'$ lies below $A$ is obvious. To show that also the second subset $B''$ of $B$ lies below $A$ it is enough to show the equality \begin{equation}\label{eq:sidon} \left\{(0,a^3,0,\bar{a^3})\colon a\in \{0,1\}^m\right\} =\left\{(0,a,0,\bar{a})\colon a\in \{0,1\}^m\right\} =B''\,. \end{equation}
It is known that a polynomial $x^k$ permutes $\gf{q}$ if and only if $q-1$ and $k$ are relatively prime; see, for example, Theorem~7.8 in the book of Lidl and Niederreiter [...]. In our case, we have $q=2^m$ and $k=3$. Since $m$ is odd, we have $m=2t+1$ for some $t\in\NN$. Easy induction on $t$ shows that $p(t):=2^{2t+1}+1$ is divisible by $3$: the basis $t=0$ is obvious, because $p(0)=3$, and the induction step $p(t+1)=2^{2(t+1)+1}+1= 4(2^{2t+1}+1)-3=4\cdot p(t)-3$ follows from the induction hypothesis. So, $q-1=p(t)-2$ cannot be divisible by $3$, that is, $q-1$ and $3$ are relatively prime and, hence, the mapping $\gf{2^m}\ni a\mapsto a^3\in\gf{2^m}$ is a bijection. This proves the desired equality \eqref{eq:sidon}. $\Box$
Back to "Notes on Monotone Arithmetic Circuits".