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 semigroups (perhaps with the assumption that the semigroup is cancellative). Specifically:

> **Question:** Do there exist integers $k, c$ such that for every finite nonempty subset $A$ of any semigroup and for every $n$, $|A^n| \le \frac{|A^k|^{cn}}{|A|^{cn}}|A|$? If not, does the answer change if we restrict to cancellative semigroups?


----------


As a starting point, we have the following theorem of Ruzsa, proved using Plünnecke's graph theoretic method (Ruzsa states the theorem for groups, but the proof applies just as easily to semigroups):

> **Thm (Ruzsa):** If $A,B,C$ are finite subsets of a semigroup with $A$ nonempty, then for every real number $m \ge 1$ there is a subset $X \subseteq A$ such that $|X| > (1-1/m)|A|$ and $|CXB| \le (2m-1)\frac{|CA|}{|A|}\frac{|AB|}{|A|}|X|$.

Applying this inductively, we can show that for every natural number $i$ we can find a set $X_i \subseteq A$ with $|X_i| \ge \frac{|A|}{2^i}$ and $|X_i^{2^i+1}| \le 3^{2^i-1}(\frac{|AA|}{|A|})^{2^i}|X_i|$, which is *almost* the type of result we want, and the near miss makes me believe that the answer to this question ought to be "yes".