3
$\begingroup$

For any two finite subsets $A,B$ of an abelian group, does the following ineqality hold?

$$|A+B|^2 |A-B|^2 \geq |A+A||A-A||B+B||B-B| \ $$

I’m interested in finding out if there are sumset inequalities that are sharper than the triangle inequalities and that show that some quantity related to sums and differences is smaller when the sums and differences are over the same sets.

Smaller examples don’t seem to work: $|A-B|^2 \geq |A-A||B-B|$ fails when $B = -A$ and $|A+A| < |A-A|$.

$|A+B|^2 \geq |A+A||B+B|$ doesn’t work when $B = -A$ and $|A-A| < |A+A|$.

The candidate given in the title combines the two and avoids these difficulties because of its symmetry. It also holds when $A$ is an arithmetic progression or a subspace (if such finite subspaces exist) and B is a random set.

$\endgroup$
6
  • $\begingroup$ 1) Just to be sure : by $|A-B|$ do you mean the number of elements of the set of all elements of the form $a-b$ with $a \in A, b \in B$ ? 2) Is the abelian group finite itself ? 3) Have you tested these inequalities on known abelian groups ? $\endgroup$
    – Jean Marie
    Mar 30 at 0:02
  • $\begingroup$ I have taken the liberty to change your title into a large sentence (containing the main keywords) and move your inequality into the text. Generally speaking, it is not advisable to place formulas into titles. I have also added "abelian-groups" into the list of tags. $\endgroup$
    – Jean Marie
    Mar 30 at 10:22
  • $\begingroup$ Are you aware of this MSc Thesis ? $\endgroup$
    – Jean Marie
    Mar 30 at 10:28
  • 1
    $\begingroup$ Sorry for the delay! I haven’t seen that specific thesis, but I am familiar with many of the results. Since this is an additive combinatorics question, the specifics of the abelian group don't really matter, except perhaps the characteristic. Really what I care about is A,B being finite and being able to talk about there sumsets and difference sets. $\endgroup$ Mar 30 at 18:49
  • 1
    $\begingroup$ 1: Yes, $A-B := \{a-b : a \in A, b \in B\}$. 2: it doesn’t matter because if there is a counterexample when $A,B \subset \mathbb{Z}$, then you can put $A,B$ in a large finite abelian group and get the same sum and difference set cardinalities. 3: The internal structure of $A, B$ is more important than the group they live in, since you can always move things around with translations and whatnot. That said, I have checked this on some extreme cases where $A,B$ have really large or really small additive or subtractive doubling. $\endgroup$ Mar 30 at 19:11

1 Answer 1

1
$\begingroup$

I have been looking for possible counter-examples in $\left(\mathbb{Z}/n \mathbb{Z},+\right)$ for different values of $n$ and different subsets $A$ and $B$ using a SAGE program that I give below.


I have found one modulo 7 with

$A = [0, 1, 3]$ and $B = [0, 3, 4, 5]$.

Indeed :

$A+B = [0, 1, 3, 4, 5, 6]$

$A+A = [0, 1, 2, 3, 4, 6]$

$A-B = A-A = B+B = B-B = [0, 1, 2, 3, 4, 5, 6]$

giving a LHS $(6 \times 7)^2$ less that the RHS $6 \times 7 \times 7\times 7$ in your formula.


I have found another counterexample modulo 8 :

with $A = [0, 1, 2, 5]$ and $B = [0, 4, 5, 7]$.


... and one modulo $12$ :

with $A = [0, 1, 3, 6, 9, 10, 11]$ and $B = [1, 7, 8, 10, 11]$.


and also mod 14 with :

$A=[2,4,5,9,10,12]$ and $B=[0,3,5,6,7,9,12]$.


Besides, your inequality is verified in almost all cases with, sometimes, an equality between the LHS and RHS.

Here is the SAGE program :

    from sage.misc.prandom import randrange
    n=6
    R=Integers(n); # integers mod n
    Li=list(R)
    X=Set([0,1,2,3,4,5]); # n elements  
    
    Y=X.subsets() # list of all the subsets of X
    ne=Y.cardinality()  # ne=2^n

    def selec(m) : # getting the m-th subset
        A=[];
        for x in Y[m] :
            A.append(Li[x])
        return list(A)

    def ol(L) : # opposite of a list
       mL=[] 
       for k in Li :
          mL.append(-k)
       return(mL)    
    
    def cs(A,B) : cardinality of the sum of 2 subsets 
       C=[]
       for a in A :
          for b in B :
             c=a+b
             if not(c in C) :
                C.append(c)
       return len(C)

    # Random selection of two subsets :
    m=randrange(ne);A=selec(m);show("A = ",A) 
    m=randrange(ne);B=selec(m);show("B = ",B)
    C=[cs(A,B),cs(A,ol(B)),cs(A,A),cs(A,ol(A)),cs(B,B),cs(B,ol(B))]
    show("Cardinalities of A+B, A-B, etc. : ",C)
    r=(C[0]*C[1])**2-C[2]*C[3]*C[4]*C[5];show("Diff, between LHS and RHS = ", r)
$\endgroup$
2
  • $\begingroup$ Thank you very much! It looks like they work as subsets of $\mathbb{Z}$ as well. It is interesting though, that $$\min(|A+A, A-A, B+B, B-B|) \leq \max(|A+B|, |A-B|)$$ in each of these examples, but I could see that being false for some large enough counterexample as well. Regardless, that is a question for another time! Thank you again! $\endgroup$ Apr 2 at 20:03
  • $\begingroup$ Here is another counterexample mod. 7 with the same A=[0,1,3] but a different B=[0,3,4,5] . $\endgroup$
    – Jean Marie
    Apr 2 at 20:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .