# $(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".