Return to Question

Update (12/06/2013). It was observed below, in the comments to Gerhard Paseman's answer, that there exist commutative non-associative magmas with arbitrarily large subsets for which Q2 is answered in the negative. So it seems natural to ask the following:

Update (12/06/2013). It was observed below, in the comments to Gerhard Paseman's answer, that there exist commutative non-associative magmas with arbitrarily large subsets for which Q2 is answered in the negative. So it seems natural to ask the following:

Suppose that $\mathbb A = (A, +)$ is a (possibly non-commutative) group, and denote by $p(\mathbb A)$ the minimum of $|S|$ as $S$ ranges in the set of non-trivial subgroups of $\mathbb A$, with the convention of taking $p(\mathbb A) := \infty$ if $\mathbb A$ is trivial. Then, pick non-empty subsets $X$ and $Y$ of $A$. It is a result from the folklore that

$$|X+Y| \ge \min(p(\mathbb A), |X| + |Y| - 1)$$ if $\mathbb A$ is commutative, which boils down to the (classical) Cauchy-Davenport theorem when $\mathbb A$ is a cyclic group of prime order. The same is known to hold if "commutative" in the previous statement is replaced with "finite"; this is a result by G. Károlyi [1], whose only known proof, to the best of my knowledge, is based on the Feit-Thompson theorem by reduction to the case of finite solvable groups. It is, then, natural to conjecture that the result is true for any group, no matter if finite or infinite, commutative or not. So my first question is:

Q1. A similar conjecture has almost surely a name. What is its name?

Now, the same conjecture can be restated in much more general terms by assuming that $\mathbb A$ is a unital magma (instead of a group) and replacing "subgroups" in the above with "submagmas".

I've something in these lines for the case when $\mathbb A$ is a cancellative monoid, $X \cap \mathbb A^\times$ is non-empty, and the smallest submonoid of $\mathbb A$ containing $X$ is commutative (or dually with $Y$ in place of $X$). Thus, I'd like to hear of alternative (or possibly more general) results.

For any purpose it may serve, let me mention that I believe I've a proof for this in the case when $\mathbb A$ is a cancellative monoid, either commutative or not, and $(X+Y) \cap \mathbb A^\times$ is non-empty. But I dislike much the assumption on the units, so any insight that could help to get rid of it would be greatly helpful.

Bibliography.

[1] G. Károlyi, The Cauchy-Davenport theorem in group extensions, L'Enseignement Mathématique 51 (2005), 239--254.

Suppose that $\mathbb A = (A, +)$ is a (possibly non-commutative) group, and denote by $p(\mathbb A)$ the minimum of $|S|$ as $S$ ranges in the set of non-trivial subgroups of $\mathbb A$, with the convention of taking $p(\mathbb A) := 1$ if $\mathbb A$ is trivial. Then, pick non-empty subsets $X$ and $Y$ of $A$. The following result is part of the folklore (in fact, a straightforward application of Kneser's theorem):

Theorem 1. If $\mathbb A$ is commutative then $|X+Y| \ge \min(p(\mathbb A), |X| + |Y| - 1).$

(This boils down to the (classical) Cauchy-Davenport theorem when $\mathbb A$ is a cyclic group of prime order.) The same result is known to hold if "commutative" in the previous statement is replaced with "finite"; this was first proved by G. Károlyi in 2005 [1], based on the Feit-Thompson theorem by reduction to the case of finite solvable groups, and recently re-proved by Ruzsa (see the comments below) as a consequence of a stronger result, which gets even rid of the assumption of finiteness. I.e., Ruzsa proves the following:

Theorem 2. $|X+Y| \ge \min(p(\mathbb A), |X| + |Y| - 1)$ no matter if $\mathbb A$ is finite or infinite, commutative or not.

But Ruzsa's result is something new, so it is plausible that Theorem 2 has been presented as a "conjecture" for a while. Then, my first question is:

Q1. A similar "conjecture" should have at least one father/mother. What is his/her name? To wit, is there any paper, book, etc. where it has been first stated explicitly? For what I can say, this is the case neither with [1] nor with [2] (where Károlyi gives a self-contained proof of Theorem 2 for the abelian case that doesn't even refer to Kneser's theorem).

Now, Theorem 2 can be restated in much more general terms by assuming that $\mathbb A$ is a unital magma (instead of a group) and replacing "subgroups" in the above with "submagmas". So my next question is:

For any purpose it may serve, let me mention that I've something in these lines for the case when $\mathbb A$ is a cancellative monoid, $X \cap \mathbb A^\times$ is non-empty, and the smallest submonoid of $\mathbb A$ containing $X$ is commutative (or dually with $Y$ in place of $X$). Also, I believe I've a proof in the case when $\mathbb A$ is a cancellative monoid, either commutative or not, and $(X+Y) \cap \mathbb A^\times$ is non-empty. But I dislike much the assumption on the units (somehow, it doesn't look very "natural"), so any insight that could help to get rid of it would be greatly appreciated. In particular, I'd like to hear of alternative (or possibly more general) results.

Bibliography.

[1] G. Károlyi, The Cauchy-Davenport theorem in group extensions, L'Enseignement Mathématique 51 (2005), 239-254.

[2] -----------, A compactness argument in the additive theory and the polynomial method, Discrete Math. 302 Nos 1-3 (2005), 124-144.

Suppose that $\mathbb A = (A, +)$ is a (possibly non-commutative) group, and denote by $p(\mathbb A)$ the minimum of $|S|$ as $S$ ranges in the set of non-trivial subgroups of $\mathbb A$, with the convention of taking $p(\mathbb A) := \infty$ if $\mathbb A$ is trivial. Then, pick non-empty subsets $X$ and $Y$ of $A$. It is a result from the folklore that

$$|X+Y| \ge \min(p(\mathbb A), |X| + |Y| - 1)$$ if $\mathbb A$ is commutative, which boils down to the (classical) Cauchy-Davenport theorem when $\mathbb A$ is a cyclic group of prime order. The same is known to hold if "commutative" in the previous statement is replaced with "finite"; this is a result by G. Károlyi [1], whose only known proof, to the best of my knowledge, is based on the Feit-Thompson theorem by reduction to the case of finite solvable groups. It is, then, natural to conjecture that the result is true for any group, no matter if finite or infinite, commutative or not. So my first question is:

Q1. A similar conjecture has almost surely a name. What is its name?

Now, the same conjecture can be restated in much more general terms by assuming that $\mathbb A$ is a unital magma (instead of a group) and replacing "(non-trivial) subgroups" in the above with "(non-trivial) submagmas".

Q2. What is known about the general "conjecture"? That is, are there partial results related to (classes of) magmas which do not embed into a group?

I've something in these lines for the case when $\mathbb A$ is a cancellative monoid, $X \cap \mathbb A^\times$ is non-empty, and the smallest submonoid of $\mathbb A$ containing $X$ is commutative (or dually with $Y$ in place of $X$). Thus, I'd like to hear of alternative (or possibly more general) results.

Bibliography.

[1] G. Károlyi, The Cauchy-Davenport theorem in group extensions, L'Enseignement Mathématique 51 (2005), 239--254.

Suppose that $\mathbb A = (A, +)$ is a (possibly non-commutative) group, and denote by $p(\mathbb A)$ the minimum of $|S|$ as $S$ ranges in the set of non-trivial subgroups of $\mathbb A$, with the convention of taking $p(\mathbb A) := \infty$ if $\mathbb A$ is trivial. Then, pick non-empty subsets $X$ and $Y$ of $A$. It is a result from the folklore that

$$|X+Y| \ge \min(p(\mathbb A), |X| + |Y| - 1)$$ if $\mathbb A$ is commutative, which boils down to the (classical) Cauchy-Davenport theorem when $\mathbb A$ is a cyclic group of prime order. The same is known to hold if "commutative" in the previous statement is replaced with "finite"; this is a result by G. Károlyi [1], whose only known proof, to the best of my knowledge, is based on the Feit-Thompson theorem by reduction to the case of finite solvable groups. It is, then, natural to conjecture that the result is true for any group, no matter if finite or infinite, commutative or not. So my first question is:

Q1. A similar conjecture has almost surely a name. What is its name?

Now, the same conjecture can be restated in much more general terms by assuming that $\mathbb A$ is a unital magma (instead of a group) and replacing "subgroups" in the above with "submagmas".

Q2. What is known about the general "conjecture"? That is, are there partial results related to (classes of) magmas which do not embed into a group?

I've something in these lines for the case when $\mathbb A$ is a cancellative monoid, $X \cap \mathbb A^\times$ is non-empty, and the smallest submonoid of $\mathbb A$ containing $X$ is commutative (or dually with $Y$ in place of $X$). Thus, I'd like to hear of alternative (or possibly more general) results.

Update (12/06/2013). It was observed below, in the comments to Gerhard Paseman's answer, that there exist commutative non-associative magmas with arbitrarily large subsets for which Q2 is answered in the negative. So it seems natural to ask the following:

Q3. Does the general "conjecture" hold if $\mathbb A$ is associative and/or cancellative?

For any purpose it may serve, let me mention that I believe I've a proof for this in the case when $\mathbb A$ is a cancellative monoid, either commutative or not, and $(X+Y) \cap \mathbb A^\times$ is non-empty. But I dislike much the assumption on the units, so any insight that could help to get rid of it would be greatly helpful.

Bibliography.

[1] G. Károlyi, The Cauchy-Davenport theorem in group extensions, L'Enseignement Mathématique 51 (2005), 239--254.