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.


  • $\begingroup$ 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$. $\endgroup$ – Boris Bukh Dec 12 '12 at 4:20
  • $\begingroup$ 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? $\endgroup$ – Will Sawin Dec 12 '12 at 4:50
  • $\begingroup$ $\{0,4,5,7\}$ works for $13$. Twice it is $\{0,1,8,10\}$ which is fundamentally different. So that's an example. $\endgroup$ – Will Sawin Dec 12 '12 at 4:52
  • $\begingroup$ 1,2,4,6,13,21 is such a set modulo 31. $\endgroup$ – Per Alexandersson Dec 12 '12 at 6:50
  • $\begingroup$ 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... $\endgroup$ – 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.