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

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

share|improve this question
1  
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[49] = GF[7][x]/(x^2+3x+5)$ and $\theta=x$ and $k=1,\dots,6$. –  Greg Martin Dec 12 '12 at 19:22

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

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.