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.

  • $\begingroup$ 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. $\endgroup$ Feb 23 '16 at 20:48
  • $\begingroup$ 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) $\endgroup$
    – zeb
    Feb 23 '16 at 23:42
  • $\begingroup$ 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. $\endgroup$ 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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.