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

Let $k,m\in\mathbb{N}$ be given. Let $M:=\{0,... , m-1\}$. How to find a subset $T\subset M$, $|T|=k$ such that $|T+T|$ is maximal, where $T+T=\{ (a+b)\mathbin\%m \mid a\in T,b\in T \}$ (“%” means modulo)?

I tried to construct a sequence of numbers which maximize $|T+T|$. But I couldn’t figure out:

  • Is it possible to cover the whole set $M$ for $k\leq \sqrt{m}$?
  • What is the best way to construct such a sequence in theory?

I am looking for papers which deals with this topic or any word to find those papers. I don’t think this problem is running under the ordinary topic name “set covering problems”.

My idea to construct such a sequence is $a_0=0;a_{i+1}=a_i+(k-i)$ for $T=\{a_i\mid i=0,...,k-1\}$ to get as small number of collisions as possible among the sums in $T+T$. But random subsets of $M$ show me that there are better subsets.

In my opinion it is hard to find such an optimal subset $T$.

Sorry for my bad English.

share|improve this question
    
Are your $m$ and $n$ supposed to be the same? –  Gerry Myerson Jun 30 '11 at 12:20
    
The correct topic name is “additive combinatorics”. –  Emil Jeřábek Jun 30 '11 at 12:21
    
Sorry. yes m=n. I try to improve it. –  greedyplot Jun 30 '11 at 12:22
    
@Emil: Thank you for the keywords. Now I am able to find papers about this topic. –  greedyplot Jun 30 '11 at 19:42
add comment

1 Answer

up vote 5 down vote accepted

A relevant keyword in this context is Sidon set (however Sidon is also used in a different context, so when searching do not be surprised if you stumble also over unrelated things).

A subset $T$ of an abelian group $G$, written additively, in your case $\mathbb{Z}/m \mathbb{Z}$ with addition, is called a Sidon set if for $a_1,a_2,a_3,a_4 \in G$ one has $a_1+a_2 = a_3+a_4$ if and only if $\{a_1,a_2\} = \{a_3,a_4\}$ (the sets), in other words $(a_1,a_2)$ or $(a_2,a_1)$ is equal to $(a_3,a_4)$ (the pairs). Or, verbally, their is no non-trivial way that two sums can be equal (the trivial one being of course that the summands are just flipped).

In yet another way, a simple upper bound for $|T+T|$ is, for $|T|=k$, the expression $k(k+1)/2$, arising as ($k$ choose $2$) plus $k$ [the sum of the elements of two-element subsets plus the 'symmetric sums'] or equivalently $(k^2 - k)/2 + k$ [half the number of pairs with distinct entries plus those pairs with twice the same entry]. Then, a Sidon set is a set that attains this upper bound. For a Sidon set $|T+T|$ is maximal among all elements of this cardinality, and one knows the cardinality precisely.

This upper bound also answers one of your questions. For $k \le \sqrt{M}$, one has the upper bound for $|T+ T|$ of the form $(M + \sqrt{M})/2$ which is less than $M$ (except for $1$). So for $k \le \sqrt{M}$ you can never get all elements (except for $M=1$).

Thus to some extent your question is really about Sidon sets. However, if $k$ is too large relative to $M$ the problem arises that no Sidon sets of that cardinality exists anymore. For very large $k$, the problem becomes 'cheap'. For example if $k > |G|/2$, then you have that $T\cap (g - T)$ is nonempty for each element of $g$ of $G$ and, thus, since $a_1=g-a_2$ with $a_i \in T$ one has in fact $g \in T+T$ and $T+T$ is the full group, and of course cannot be larger. Since this argument works for each set this can of course be improved (considerably). A key-word here would be 'additive basis of order two'. I do not continue on this as it seems to me, you care more about small $k$ (in a relative sense).

Regarding your second question, on construction, this is an open problem (towards which however various results are known). The problem is that the precise maximal cardinality of a Sidon set is not known. So you do not know up to which exact value the bound $(k+1)k/2$ will actually be the right value. However, there are good constructions for Sidon sets known, and perhaps this is sufficient for you. For a detailed overview of results on Sidon-related resuls see Kevin O'Bryant's annotated bibliography (many mant references). Note however that it is mainly on results in the integers (Sidon sets in the first $n$ integers, or infinite ones, then often called Sidon sequences). Yet, it also contains a section on cyclic groups and in part the results on integers are relevant too.

share|improve this answer
    
Thank you very very much. This is exactly I am looking for. –  greedyplot Jun 30 '11 at 19:42
    
You are welcome! –  quid Jun 30 '11 at 23:04
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.