Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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