4
$\begingroup$

Given a group $G$, the sumset of two sets $A,B$ is denoted as $A+B = \{a+b:a\in A,b\in B\}$. We say $A$ injects $B$, if $A+B$ has no multiplicities, i.e. $|A+B| = |A||B|$. We let $I(B) = \max \{|A|:A \text{ injects } B\}$ . For practically, let's say $G$ is integer addition modulo $N$.

Given a set $B$, can we determine $I(B)$ in time polynomial in $N$?

Improve this question
$\endgroup$
6
  • $\begingroup$ The choice of terminology "$A$ injects $B$" seems a little misleading for abelian groups (including the integer addition modulo $N$ mentioned in the question), since for these groups the definition is symmetric: $A$ injects $B$ if and only if $B$ injects $A$. Are you interested in solutions for any nonabelian groups? $\endgroup$ – Aaron Rotenberg Jan 20 '20 at 19:31
  • 1
    $\begingroup$ $A$ injects $B$ iff $(A-A) \cap (B-B) = \{0\}$, so this is very loosely related to difference sets. I don't see how this helps, though. $\endgroup$ – D.W.♦ Jan 20 '20 at 19:33
  • $\begingroup$ @AaronRotenberg considering non-abelian groups is of interest, but I am content to goodly think about module $N$ for now $\endgroup$ – Zachary Hunter Jan 20 '20 at 19:36
  • $\begingroup$ @D.W. Does that mean that "injects" is symmetric even for nonabelian groups? I was considering that but it's making my head hurt to think about. $\endgroup$ – Aaron Rotenberg Jan 20 '20 at 19:50
  • 1
    $\begingroup$ @AaronRotenberg, I don't know. I don't see why it would be. My proof of that equivalence only holds for abelian groups. For nonabelian groups, I think the corresponding condition is $((-A)+A) \cap (B+(-B)) = \{0\}$, which is not equivalent as $(-A)+A$ isn't necessarily the same as $A+(-A)$. (But don't hold me to this; I might have made a mistake somewhere.) $\endgroup$ – D.W.♦ Jan 20 '20 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.