3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are your $m$ and $n$ supposed to be the same? $\endgroup$ Jun 30, 2011 at 12:20
  • $\begingroup$ The correct topic name is “additive combinatorics”. $\endgroup$ Jun 30, 2011 at 12:21
  • $\begingroup$ Sorry. yes m=n. I try to improve it. $\endgroup$
    – greedyplot
    Jun 30, 2011 at 12:22
  • $\begingroup$ @Emil: Thank you for the keywords. Now I am able to find papers about this topic. $\endgroup$
    – greedyplot
    Jun 30, 2011 at 19:42

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very very much. This is exactly I am looking for. $\endgroup$
    – greedyplot
    Jun 30, 2011 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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