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

Easy to approximate Sidon sets

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