# 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