# Recovering Sidon sets from difference sets, part 2.

This is inspired by a recent question. A set $$A \subset \mathbb{Z}/n\mathbb{Z}$$ with $$|A|=m$$ is a Sidon set if all the pairwise sums of distinct elements are unequal: $$A+A=\{a+a' \mid a,a' \in A, a \ne a'\}$$ has $$\binom{m}2$$ elements. Since $$a+b=c+d$$ implies $$a-c=b-d$$ it is equivalent to require that $$\{a-a'\mid a,a' \in A\}$$ has $$m(m-1)+1$$ elements (including 0.)

It is clear that when $$\lambda$$ is coprime to $$n$$, $$B=\lambda A$$ is also a Sidon set and $$B-B=\lambda(A-A).$$ I am going to restrict to the case that $$n$$ is prime (although more general rings could be of interest.) My question is if the converse is true (I'll explain why I call this the converse):

Suppose that $$n$$ is prime, $$A,B \subset \mathbb{Z}/n\mathbb{Z}$$ are Sidon sets and $$B-B=A-A.$$ Must it be the case that either

1. There are $$\lambda=\pm 1,k$$ with $$B=\lambda A+k$$? OR

2. $$A-A=B-B=\mathbb{Z}/n\mathbb{Z}$$ and there are $$\lambda,k$$ with $$B=\lambda A+k$$?

I can report that this is true in all the cases I checked which were most of the possibilities with $$n \le 29$$ and $$m \le 5$$ as well as $$n=31$$ and $$m=6.$$ However this may simply be the Strong Law of Small Numbers.

In that last case (as well as $$n=13$$ and $$m=4$$) we have $$A-A= \mathbb{Z}/n\mathbb{Z}$$ so it is not a surprise that there are choices of $$\lambda \ne \pm 1$$ with $$\lambda(A-A)=A-A.$$ In my limited explorations there were no other examples of $$\lambda(A-A)=A-A.$$ I think that this is really the only way this could happen (if not, change case 2 to simply have $$\lambda(A-A)=A-A$$.)

Let $$H$$ be the multiplicative subgroup generated by $$\lambda.$$ Then $$\lambda(A-A)=A-A$$ would require that $$A-A$$ is a union of translates of $$H$$ (along with $$0$$). This might be the start of a proof.

I called the question a converse because we could ask if $$B-B=\alpha(A-A)$$ requires that $$B$$ is a translate of a dilation of $$A$$, but (since I restricted to $$n$$ prime) there is an inverse with $$\alpha \beta=1$$ and then $$C-C=A-A$$ for $$C=\beta B.$$

• It might be worth pointing out that the statement is false when $n$ is not a prime power. For example, {1, 12, 22, 29, 31, 34, 35}, {6, 13, 15, 18, 19, 33, 44}, {4, 14, 21, 23, 26, 27, 41}, {2, 3, 17, 28, 38, 45, 47}, {9, 20, 30, 37, 39, 42, 43}, {5, 7, 10, 11, 25, 36, 46} are all Sidon sets modulo 48, but only the first and fifth ones are affinely related (in fact shifts by 8 of each other). These were constructed as in Section 2.2.2 of math.ubc.ca/~gerg/index.shtml?abstract=CGSS using the field $GF = GF[x]/(x^2+3x+5)$ and $\theta=x$ and $k=1,\dots,6$. Dec 12, 2012 at 19:22

N0. It is NOT the case that it is true in general. It is true for all cases with both $m \le 5$ and prime $n \lt 100$. It is also true for $m=6$ and $n = 31$. But actually it is false ( for $m=6$) over $\mathbb{Z}$ and also over $\mathbb{Z}/{n}\mathbb{Z}$ for any $n \ge 36$, prime or composite.
The sets $$A=\{0, 1, 4, 10, 12, 17 \} \text{ and } B=\{ 0, 1, 8, 11, 13, 17\}$$ are Sidon sets with $A-A=B-B$ in $\mathbb{Z}$. So the only restriction on $n$ is that they are Sidon sets. Since the elements of $A-A=B-B$ range from $-17$ to $17$, they are Sidon sets with $A-A=B-B$ in $\mathbb{Z}/{n}\mathbb{Z}$ for any modulus, prime or not, starting with $n=35.$ It does not work for $n=32,33,34$. It does also work for $n=31.$ However for $n=31$ we have $B=11A.$ Also, for $n=35$ we have $B=17A-11.$ These are the only cases where an affine map takes $A$ to $B$.
I found this example looking in $\mathbb{Z}/{n}\mathbb{Z}$ but it turns out to be known.
I think it could be decided if there are any exceptions for $m=4,5$ (other then the special case $m=4$ and $n=13$) however the method seems tedious. Here is a sketch: We may assume that $A=\{0,1,a,b\}.$ If $B-B=A-A$ then $s-r=1$ for some $r,s\in B.$ We can translate to have $r=0,s=1$ so that $B=\{0,1,w,x\}.$ Further more, $w,x$ are elements of $A-A.$ Three of the 13 elements ($-1,0,1$) are ruled out, leaving $\binom{10}{2}=55$ possible cases. Many of these (like $w=-x$, $w=1-x$ and $w=x-1$) are immediately seen to be impossible. The rest come in pairs $\{0,1,w,x\}$ and $\{0,1,1-w,1-x\}$ which are reflections of each other.
If we try $B=\{0,1,1-a,a-b\}$ then $A-A$ and $B-B$ overlap in $9$ elements leaving $\{b,-b,1-b,b-1\}$ unmatched in $A-A$ and $\{1-2a+b,-1+2a-b,a-b-1,1-a+b\}$ in $B-B$ If $b=1-2a+b$ then $n=2a-1$ and $B$ is seen to be a translated reflection of A. We can't have $b=1-a+b$ because $a \ne 1.$ The other two possibilities for $b$ also fail.
But if we try $B=\{0,1,-a,b-1\}$ there are $6$ unmatched expressions in each of $A-A$ and $B-B$ and running through the possible matchups of pairs one case is $b=-a-1,a-1=1-b-a$ which comes out to $a=3,b=-4$ which leaves the remaining elements as $\pm2,\pm 4,\pm 7$ for $A-A$ and $\pm2, \pm4, \pm6$ for $B-B$. So this sub-sub-case is possible for, but only for, $n=13$ where, it can be checked, $B$ is a translated diolation of $A$.