# Karolyi's theorem for finite groups and its extensions

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:

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?

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.

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?

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.

-
Based on our exchange, I have a bit more clarity about your questions. You might ask quasigroup theorists about a corresponding theorem. Also, for finite magmas, shouldn't cancellative imply at least a one sided unit? Gerhard "Ask Me About Structure Design" Paseman, 2013.06.12 –  Gerhard Paseman Jun 12 '13 at 15:39
Also, I would like to point out that algebras that have "large" (i.e. more than 2 elements") subalgebras are deficient, and so algebras that are not deficient are a version of being "simple" in a subalgebra sense, which for groups relates to (but is not the same as) simple in the normal or congruential sense. If finite algebras interests you, reading the classic text on tame congruence theory by Hobby and McKenzie might inspire you. They use polynomial selfmaps to identify and classify minimal algebras. These might be C-D. Gerhard "Ask Me About System Design" Paseman, 2013.06.12 –  Gerhard Paseman Jun 12 '13 at 16:03
Thanks for the references. Just to be sure that we're speaking the same language: What do you mean by a quasigroup? Also, why do you mention that a finite cancellative magma should have a one sided unit? To wit, what's the link with the questions in the OP? Let it be as it may, if my guess is correct and you're using "unit" for "identity" (what else otherwise?), then I don't know the answer to your question. –  Salvo Tringali Jun 12 '13 at 17:40
As per your question, the answer is no. For, consider a set $S$ with three elements $a$, $b$ and $c$, and let $\diamond$ be the binary operation on $S$ given by the following (Cayley) table: $$\begin{array}{c|ccc} \diamond & a & b & c \\ \hline a & b & a & c \\ b & a & c & b \\ c & c & b & a \end{array}$$ Now, a magma $\mathbb A=(A,\ast)$ is cancellative if no row or column of its table contains repetitions, while an element $e \in A$ is a left (resp., right) identity (for $\mathbb A$) if it leaves unchanged its own row (resp., column) in the table of $\mathbb A$. –  Salvo Tringali Jun 12 '13 at 18:55
Thank you for your three element example (which I believe is a quasigroup and not a loop). I was unsure about the notion of cancellative and thought it might relate to their being a one sided identity (sorry for the identity-unit confusion on my part). Since I am misremembering details, I'll say I think quasigroups and quasigroups with identity (loops) are cancellative magmas, or groups without necessarily being associative, and that I am using it as JDH Smith uses the term quasigroup, which should be standard usage somewhat. Gerhard "Needs Another Cup Of Coffee" Paseman, 2013.06.12 –  Gerhard Paseman Jun 12 '13 at 19:49

This is weakly related to an answer to your second question. Also it is fragmentary, and possibly some details are misremembered. It relates to some of the first original mathematics I did over 20 years ago.

There is a result of Vadim Murskii, which goes by the tagline "Almost All Finite Algebras Are Finitely Based". Fix a similarity type which includes at least one function of arity two. (There may be a way to handle structures which have only unary functions, but I don't recall it.) Consider all structures of that type on a (labeled) set of n elements. Since it has a binary operation, there are at least n^(n^2) such structures, and likely many more. If one looks at a structure A, one can note a property that the structure has. A is finitely based if the equational theory of the variety generated by A is equivalent to a theory which is generated by finitely many axioms in equational logic. We say almost all algebras are finitely based if, as n gets large, the proportion of finitely based labeled algebras on n elements compared to all such algebras on n elements goes to 1.

There are a couple of ways to prove such a result, and I studied them and gave a talk on them as a graduate student. I went from notes of R. Quackenbush, as well as attempting to read Murskii's papers from the 1960's and 1970's. One key idea was to reduce the problem to looking at magmas, and another was to look at certain classes of magmas which were able to be algebraically classified and shown to be provably finitely based. Looking at idempotent magmas was one of the interesting features of the analysis.

Indeed, part of the argument was to show that if a magma had one of eight or ten special properties, then something nice occurred, generally you could show it was part of a negligible fraction of such algebras, or it was related to a finitely based magma, or something else that occurred.

To tie this back to your question, one of the properties talked about a deficient magma, which is a special form of your property. If A is a magma on n > 3 elements, it is deficient if there is a subset B of at least 3 and fewer than n elements, such that the cardinality of B is at least the cardinality of B*B, where I am using * for the magma operation. This is more general than having a not too small subalgebra. Also, being deficient turns out to be relatively rare. (I wondered why B having 2 elements was excluded. I discovered those magmas are not rare, and I also discovered a simpler proof that almost all magmas were not deficient.)

If you were to find the notes of Quackenbush, or use a citation index starting with Murskii, or do a web search of "almost all" finite algebras, you might find some papers like Ralph Freese's on probability in algebra, or work of Sapir and McNulty on the finite basis problem. Hopefully though, you will find something that fully addresses your question 2.

I don't quite understand what exactly you're claiming. If I take it correctly, I'd say that, given $m,n\in\mathbb N$ with $m\le n$, an $(m,n)$-deficient magma is a magma $\mathbb A=(A,\ast)$ for which there exists $X\subseteq A$ with $m\le |X|\le n$ s.t. $|X|\ge |X\ast X|$; in particular, you're looking at the case where $3\le m$, $n<|A|<\infty$. So, e.g., if $\mathbb A$ is a zero-left or zero-right sgrp (and hence a band), then it's $(m,n)$-deficient as long as $n\le |A|$. And it's clear that if $\mathbb A$ has at least one non-trivial idempotent then it does certainly satisfy the [...] –  Salvo Tringali Jun 11 '13 at 21:49
[...] "conjecture", but this is somewhat trivial. So let us focus on the case of $(m,n)$-deficient magmas with no non-trivial idempotents: Are you suggesting that these could verify/provide a counterexample for the general "conjecture"? Would you mention a class of examples of deficient magmas with no non-trivial idempotents? Also, in which sense the work that you're referring to at the end of your answer should hopefully fully address Q2, considering that it's not even known, for what I can say, whether or not it holds for infinite non-commutative groups? –  Salvo Tringali Jun 11 '13 at 22:02