2
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ I tested it on Matlab, and $A\mapsto A-A$ is injective for $A$ Sidon and $n\leq 10$. $\endgroup$ Dec 12, 2012 at 3:36
  • $\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, 2012 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, 2012 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, 2012 at 4:52
  • $\begingroup$ 1,2,4,6,13,21 is such a set modulo 31. $\endgroup$ Dec 12, 2012 at 6:50

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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