\(
\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}}
\)
$(1,1)$-thin sets are Sidon sets
Let $A\subset\NN^n$ be a $(1,1)$-thin set. Our goal is to show that $A$ is a Sidon set. The argument is due to Igor Sergeev.
Assume that $A$ is not a Sidon set. Then
there are vectors $a,b,c,d\in A$ such that $a+b=c+d$ but
$c\not\in\{a,b\}$. To show that then the set $A$ is not $(1,1)$-thin,
we have to show
that there exist vectors $x\neq x'$ and $y\neq y'$ in $\NN^n$ such
that $x+y=a$, $x'+y'=b$ and $\{x,x'\}+\{y,y'\}\subseteq A$. We
define the desired vectors componentwise.
If $a_i < c_i$ then take $x_i =0$, $x'_i=c_i-a_i$, $y_i=a_i$ and
$y'_i=d_i$ ($=a_i-c_i+b_i$). If $a_i\geq c_i$ then take $x_i
=a_i-c_i$, $x'_i=0$, $y_i=c_i$ and $y'_i=b_i$ ($=c_i-a_i+d_i$).
Then all four vectors $x,x',y,y'$ belong to $\NN^n$, vectors $x+y=a$
and $x'+y'=b$ belong to $B$, and the ``cross-vectors'' vectors
$x+y'=d$ and $x'+y=c$ belong to $A$. Moreover, $c\neq a$ implies
$x\neq x'$, and $c\neq b$ implies $y\neq y'$.
$\Box$
Back to "Notes on Monotone Arithmetic Circuits".