# Recovering Sidon sets from difference sets

How can I recover a Sidon set $A\subseteq \mathbb{Z}/n\mathbb{Z}$ from the set $A-A\subseteq \mathbb{Z}/n\mathbb{Z}$?

Is it even unique? (up to translation and reflection)

($A-A$ stands for the set of all differences of the form $a_1-a_2$ with both $a_1$ and $a_2$ in $A$ and a Sidon set is a set $A$ such that all the differences are distinct, except for the repeated zeros)

PS: I suspect Fourier Transforms won't help.

Thanks!

-
It is not unique. There are Sidon sets s.t. $A−A=\mathbb{Z}/n\mathbb{Z}$. Example: $\{1,2,4\}$ modulo $7$. Pick such an $A$ and consider a dilate $\lambda\cdot A$ for some non-zero $\lambda$. –  Boris Bukh Dec 12 '12 at 4:20
In your example, $\lambda \in \{1,2,4\}$ returns the original set, $\lambda \in \{3,5,6\}$ returns its reflection. Is there a bigger example? –  Will Sawin Dec 12 '12 at 4:50
$\{0,4,5,7\}$ works for $13$. Twice it is $\{0,1,8,10\}$ which is fundamentally different. So that's an example. –  Will Sawin Dec 12 '12 at 4:52
1,2,4,6,13,21 is such a set modulo 31. –  Per Alexandersson Dec 12 '12 at 6:50
Are there any counterexamples if you consider $A-A$ as a multiset (i.e. take into account the multiplicities of elements)? If yes, it would be the argument for not using Fourier... –  Ilya Bogdanov Dec 12 '12 at 13:06

If $A$ is a Sidon set in $\mathbb{Z}/n\mathbb{Z}$ and $|A|=m$ then $A-A$ has $m^2+m+1$ members including $0.$ For $\lambda$ co-prime to $n$, $B=\lambda A$ is also a Sidon set and $B-B=\lambda(A-A).$ For ease I'll assume that $n$ is prime. We do have $B-B=A-A$ in the case that $A-A=\mathbb{Z}/n\mathbb{Z}.$ As noted, there are examples for $n=7,13,31$ (The smallest primes $n$ of the required form.) For $n=7,$ the example is unique up to translation and reflection, but this is not so for $n=13,31.$ Curiously, it seems possible (based on several small examples) that the converse is true, perhaps the differences do determine $A$ up to reflection translation and dialation. I am going to ask that as a new question.

LATER It turns out that, for $u \ge 5$, The sets $$A=\{0, 1, u-1, 2u, 2u+2, 3u+2\}$$ $$B=\{0, 1, u+3, 2u+1,2u+3, 3u+2 \}$$ are Sidon sets in $\mathbb{Z}$ with $A-A=B-B.$ So they certainly enjoy the same property in $\mathbb{Z}/n\mathbb{Z}$ when $n \ge 6u+5$ (and maybe for some smaller $n$.) For $u=5$ this works $n \ge 36$ and the sets are not related by translations , reflection and dilation. It does also work for $n=31$ and $n=35$ but in those cases they are related.

-

I tested it on Matlab, and $A\mapsto A-A$ is injective for $A$ Sidon and $n\leq 10$.

(I'd like this to be a comment, but I have a noobie's reputation.)

-