# Iterated sumset inequalities in cancellative semigroups

This question is motivated by the following well-known theorems:

Thm (Plünnecke): If $$A$$ is a finite nonempty subset of an abelian group, then for every $$n$$ we have $$|A^n| \le \frac{|AA|^n}{|A|^n}|A|$$.

Thm (Ruzsa): If $$A$$ is a finite nonempty subset of a group, then for every $$n$$ we have $$|A^n| \le \frac{|AAA|^{2n}}{|A|^{2n}}|A|$$.

Here by $$A^n$$ I mean the set of all products of $$n$$ elements of $$A$$, so $$A^2 = AA$$ and $$A^3 = AAA$$.

I would like to know if there is any similar generalization to cancellative semigroups. Specifically:

Question: Do there exist integers $$k, c$$ such that for every finite nonempty subset $$A$$ of any cancellative semigroup and for every $$n$$, $$|A^n| \le \frac{|A^k|^{cn}}{|A|^{cn}}|A|$$?

Edit: There is a counterexample in the non-cancellative case. For any $$n$$, let $$E_n = \langle e \mid e^{n+2} = e^{n+1}\rangle$$. For any group $$G$$, let $$S$$ be the quotient of $$(G \times E_n)\cup\{0\}$$ where we identify $$(g,e^{n+1})$$ with $$0$$ for every $$g\in G$$. Let $$A$$ be the image of $$G\times \{e\}$$ in $$S$$. Then $$|A| = |AA| = \cdots = |A^n| = |G|$$, but $$|A|^{n+k} = 1$$ for every $$k \ge 1$$. Taking a product of many examples like this and a free semigroup, we can arrange that $$|A| = |AA| = \cdots = |A^n|$$, but $$|A^{n+k}| = |A|^{(n+k)/n}$$ for every $$k \ge 1$$.

Here's an easy result which actually uses cancellativity:

Thm: If $$A$$ is a subset of a cancellative semigroup $$S$$, then there is a subset $$P \subseteq AA$$ with $$|P| \ge \frac{|A|}{2}$$ such that for any subsets $$C,B$$ of $$S$$, we have $$|CPB| \le 2\frac{|CA|}{|A|}\frac{|AB|}{|A|}|AA|$$. In particular, $$|AP^nA| \le 2^n\frac{|AA|^{2n}}{|A|^{2n}}|AA|$$.

To prove this, take $$P$$ to be the set of products in $$AA$$ which can be written as a product in at least $$\frac{|A|^2}{2|AA|}$$ ways (the "popular" products) and write down a clever injection.

It turns out that the minimal axioms needed to carry out the standard proofs for non-commutative groups are associativity and cancellation. Petridis' proof probably works, but I verified the hypothesis for a Theorem 5.8 of the following paper: http://arxiv.org/pdf/1309.2191.pdf, which shows that for any pair of subsets $B,C$ of a cancellative semigroup there exists an $X\subseteq A$ such that

$$\frac{|BXC|}{|X|}\leq \frac{|BZ|}{|Z|}\frac{|ZC|}{|Z|}$$

for any $Z\subseteq A$. In particular,

$$|BXC|\leq \frac{|BZ|}{|Z|}\frac{|ZC|}{|Z|}|X|\leq \frac{|BA||AC|}{|A|}.$$

Presumably you could use an iterative argument to get a lower bound on the size of $X$, while losing a multiplicative constant.

The conditions that need to be checked are that the directed graph with vertex sets $A, AB, CA, CAB$ is "upwards and downwards square commutative". The upwards condition corresponds to associativity, and the downwards condition follows from cancellation.

• The ideas needed to carry this out are contained in a paper of Ruzsa cited in the linked paper, the generalizations in the linked paper are for another purpose. – Brendan Murphy Feb 23 '16 at 20:48
• The fact that Petridis's proof of this inequality generalizes to the cancellative case was part of the reason I asked this question - unfortunately, no matter how I tried I could not find a way to use it to prove the general growth bounds I am looking for. (For a completely graph-free proof check out Theorem 7 of my personal notes on the sum-product theorem: math.stanford.edu/~notzeb/sumproduct.pdf) – zeb Feb 23 '16 at 23:42
• Nice notes! I suppose I should have figured you tried this, but I happened to be thinking about commutative graphs for another reason and was reminded of your question. I don't know a way around using Ruzsa's triangle inequality to answer your question. – Brendan Murphy Feb 24 '16 at 1:04

Here is a cheap answer: if you can embed the semi-group in a group, then Ruzsa's theorems apply.

If $S$ is a commutative semi-group with cancellation, then you can embed it in its Grothendieck group $G(S)$. For non-commutative semi-groups, cancellation is sufficient for "right reversible" semi-groups, but not in general: https://math.stackexchange.com/questions/79453/when-a-semigroup-can-be-embedded-into-a-group

Perhaps it is possible prove a stand in for Ruzsa' triangle theorem (which seems to be the missing ingredient) by emulating an embedding locally for $A$ (e.g. perhaps weaker conditions suffice to find Freiman homomorphisms).

• There is no finite basis for the quasi-identities for embedding a semigroup into a group. Malcev has an infinite list. – Benjamin Steinberg May 29 '15 at 17:17
• Thanks for the correction, I removed that remark Malcev's conditions. – Brendan Murphy May 29 '15 at 19:11