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.

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.

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

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".

Edit: I just realized that the non-cancellative case is a bit stupid, so I'm restricting the question to cancellative semigroups. 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.

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.

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".

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

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".

Edit: I just realized that the non-cancellative case is a bit stupid, so I'm restricting the question to cancellative semigroups. 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.