# Largest sumset without multiplicity

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

• 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? – Aaron Rotenberg Jan 20 '20 at 19:31
• $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. – D.W. Jan 20 '20 at 19:33
• @AaronRotenberg considering non-abelian groups is of interest, but I am content to goodly think about module $N$ for now – Zachary Hunter Jan 20 '20 at 19:36
• @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. – Aaron Rotenberg Jan 20 '20 at 19:50
• @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.) – D.W. Jan 20 '20 at 19:56