Recovering Sidon sets from difference sets, part 2.

2012-12-12T11:17:32Z

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

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

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

Answer by Aaron Meyerowitz for Recovering Sidon sets from difference sets, part 2.

2012-12-15T02:06:52Z

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

Recovering Sidon sets from difference sets, part 2. - MathOverflow

Recovering Sidon sets from difference sets, part 2.

Answer by Aaron Meyerowitz for Recovering Sidon sets from difference sets, part 2.