Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We have some group word $w$ in $k$ letters. We say a $k$-tuple of group elements $\vec{g} = (g_1, g_2, \ldots , g_k) \in G^k$ satisfies the word $w$ if $w$ gives the identity at $\vec{g}$. More precisely: The word $w$ is an element of $F_k$, the free group on $k$ letters. The $k$-tuple $\vec{g}$ specifies some homomorphism $\varphi_{ \vec{g} } : F_k \longrightarrow G$ by the universal property. In this notation, $\vec{g}$ satisfies $w$ if $\varphi_{ \vec{g} } (w) = e$.

For a finite group $G$, we are interested in the probability that a random (uniformly chosen) $k$-tuple of group elements satisfies the word $w$. Call this probability $p_w(G)$.

Now consider some family of finite groups, each injecting into the next:

$$ G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_n \hookrightarrow \ldots $$

Is it true that $p_w(G_n)$ converges to a limit?

For instance, if the word $w$ is $x_1 x_2 x_1^{-1} x_2^{-1}$, then an easy group-theoretic argument shows that $p_w(G_n)$ decreases monotonically.

For the word $x_1^2$, the sequence need not be monotonic, but seems to converge anyway.

Does anyone know a proof that the limit exists? Or have a counterexample?

share|improve this question
Some comments: For a coinductive (productive?) sequence of groups $G_n \twoheadleftarrow G_{n+1}$, it's easy to see that $p_w(G_n)$ decreases monotonically. Also, your question could be asked more generally for not just any word, but any first-order formula. If anyone could think of a counterexample to this more general question, that would be interesting to see, as well. –  Gene S. Kopp Sep 25 '10 at 16:59
Excuse me, what is the precise meaning of satisfy in the sentence: "a k-tuple of group elements satisfies the word w"? –  Pietro Majer Sep 25 '10 at 21:25
@Pietro I've put in a definition. –  John Wiltshire-Gordon Sep 25 '10 at 22:41
@Gene: [I think it's "projective", not productive?] Regarding your question on first-order formulas, do you allow existential quantifiers over other variables, and do you allow "not equals to" in your formula? If existential quantifiers are allowed, I can think of counterexamples. Specifically, you can use first-order formulas to determine whether an element of the group is a commutator. For instance, we have an inductive family $A_n \hookrightarrow S_n \hookrightarrow A_{n+2} \hookrightarrow S_{n+2} \dots$. In $A_n$, all elements are commutators, in $S_n$, only half are. So, it oscillates. –  Vipul Naik Sep 26 '10 at 14:42
Also, your statement seems probably true, even with existential quantifiers, for abelian groups. But I can't think of an easy proof (unlike the words case, where it basically follows immediately). –  Vipul Naik Sep 26 '10 at 14:43

3 Answers 3

up vote 3 down vote accepted

John, you know this already, and this is far from an answer, but I thought I'd say it here for the benefit of others who may want to think about the problem.

Call a word $w(x_1,x_2,\dots,x_k)$ "groupy" in the variable $x_i$ if, for fixed values of the other variables, the set of values of $x_i$ such that $w$ is the identity element is a subgroup of the whole group. Call $w$ "groupy" if it is groupy in all its inputs.

We can show that if $w$ is groupy, and $H \le G$, then $p_w(H) \ge p_w(G)$, giving the monotonically decreasing property on $p_w(G_n)$.

The word $x$ and the word $e$ are groupy for trivial reasons. Beyond these, the only groupy word I can think of is the commutator word $[x_1,x_2]$.

On the other hand, if we restrict ourselves to the variety of abelian groups, all words power words (e.g., $x^2$ or $x^3$) are groupy, hence the monotonically decreasing property holds.

The iterated commutator $[[x_1,x_2],x_3]$ is groupy in $x_3$ but not (in general) in $x_1$ or $x_2$ -- however, it is likely that the groupiness argument can be extended somewhat to cover these kinds of words too.

share|improve this answer
I propose the notion of "cosetty" words, that is, when solving the equation $w(x_1,x_2, \ldots , g , \ldots, x_k) = e$, the possible values of $g$ form a coset. Many more words are cosetty; for instance, words where each variable appears exactly twice, and is inverted one of those times. I think cosetty words converge for the same reason that groupy ones do. –  John Wiltshire-Gordon Sep 26 '10 at 16:31
John, the argument does not go through, at least in the exact same form, for the "cosetty" words because, whereas any two subgroups must intersect, a coset can "live elsewhere" and hence avoid intersecting a subgroup completely, creating havoc for the intersection logic. Also, I suspect that many of the words you consider "cosetty" are not cosetty, at least in the general, non-abelian case. Do double check that. –  Vipul Naik Sep 26 '10 at 16:48
You're right -- for the words you mention, it is either a single coset of a centralizer or an empty set. (As we discussed in person, but MO isn't privy to our conversations). –  Vipul Naik Sep 28 '10 at 19:49

Edit: As John points out below, this doesn't work.

Let's look at the example where $w=x_{1}^{2}$. I'm pretty sure that $p_{w}(G\rtimes \mathbb{Z}/2\mathbb{Z}) \geq 1/2$ for any group $G$ (where we take the non-abelian choice for the semi direct product,) since if $g\in G$ and $z$ is the generator of $\mathbb{Z}/2\mathbb{Z}$, then $(gz)^{2}=gzgz=gg^{-1}zz=1$ (exactly half of the elements of $G\rtimes \mathbb{Z}/2\mathbb{Z}$ are of the form $gz$ where $g\in G$.)

On the other hand $p_{w}(G\times \mathbb{Z}/5\mathbb{Z}) \leq 1/5$, since if $g\in G$ and $z$ is the generator of $\mathbb{Z}/5\mathbb{Z}$, we know that $(gz^{a})^{2}=1$ can only happen if $z^{2a}=1$, which happens with probability $1/5$.

We can combine these two facts to get a sequence where $p_{w}$ won't converge. (E.g., $G_1 = \mathbb{Z}/2\mathbb{Z}$ and $\forall i\geq 1$, $G_{2i}=G_{2i-1}\rtimes \mathbb{Z}/2\mathbb{Z}$ and $G_{2i+1} = G_{2i}\times\mathbb{Z}/5\mathbb{Z}$.)

share|improve this answer
Hi David! (Haven't seen you in a while!) If $G$ is abelian, I certainly see how $\mathbb{Z} / 2 \mathbb{Z}$ acts nontrivially: by negation. If $G$ is non-abelian, there are times when all $\mathbb{Z} / 2 \mathbb{Z}$ actions are trivial (for instance if $\mathop{Aut} (G)$ has odd order). –  John Wiltshire-Gordon Sep 24 '10 at 4:50
More to the point, the equation $gzgz=gg^{-1}zz$ seems to rely on the action being negation. Unfortunately, negation is not a homomorphism for non-abelian groups. –  John Wiltshire-Gordon Sep 24 '10 at 5:07
Hello again. You're right of course, I forgot that negation isn't an automorphism. I still think there should be a counterexample to the conjecture, but you probably can't get to it with anything as easy as a chain of semi-direct products. –  David Cohen Sep 24 '10 at 5:29
I agree with you! My friend Gene Kopp thinks they always converge, but I'd like to be on record saying that it seems unlikely. –  John Wiltshire-Gordon Sep 24 '10 at 5:36
@John: did you see the book "Words" by Dan Segal? Similar questions are treated there. –  Mark Sapir Sep 24 '10 at 7:27

Original answer

This isn't an answer, but since there has been little activity on this (very interesting) question I guess I might as well say it.

What if we consider a set of generators of $G_1$ and keep extending it by adding some elements so that it generates $G_n$ at each step. Then, looking at the Cayley graphs we can put some distance on each group, making this a sequence of finite metric spaces. The idea would be to do this in such a way so that the spaces are converging in the Gromov-Hausdorff sense to some metric space $(X,d)$ and the uniform probabilities $\mu_n$ on each $(G_n,d_n)$ are converging to some probability measure $\mu$ on $X$.

Added later...

Compactification and weak limit of probabilities in the case of finite Abelian cyclic groups

Consider the case when all the groups are finite cyclic so that $G_k = \mathbb{Z}_{n_k}$ (i.e. the finite cyclic group of $n_k$ elements) for some non-decreasing sequence of natural numbers each of which divides the next $n_1 | n_2 | \cdots$.

Let $S = \mathbb{R}/\mathbb{Z}$, we can identify each $G_k$ with the subgroup $(\frac{1}{n_k}\mathbb{Z})/\mathbb{Z} \subset S$. The uniform probability measures on these finite subgroups either converge weakly to Lebesgue measure on $S$ or (if the sequence of numbers $n_k$ is eventually constant) are eventually equal to a constant measure supported on a finite subgroup.

Compactification and weak limit of probabilities in the case of general Abelian finite groups

Consider now the case in which all groups $G_k$ are abelian. By the clasification of finite abelian groups, one can decompose each $G_k$ into a direct sum of cyclic groups with orders that are powers of primes. This implies that one can obtain a group isomorphic to $G_{k+1}$ from $G_k$ by replacing some of these powers of primes by higher powers, and by forming the direct product with another cyclic group of power of prime order.

Let $G = S^{\mathbb{N}}$ be the cartesian product of countably many copies of $S$. This is a compact and metrizable group. One can identify each group $G_k$ with a subgroup of $G$ generated by a finite number of elements with power of prime order and only one non-null corrdinate. The extension from $G_k$ to $G_{k+1}$ is obtained by replacing one of these generators by another with the same non-null coordinate but whose order is a higher power of the same prime number, or by adding a new generator with power of prime order whose only non-null coordinate is distinct from that of all the other generators.

This procedure gives rise to an increasing family of subgroups of $G$. The sequence of uniform measures $\mu_n$ on these groups can be seen to have a weak limit since each projection to a coordinate does (it is either eventualy a constant uniform measure on a finite subgroup of prime power order, or converges to Lebesgue measure on the circle).

Further directions

The answer to the question posed here implies that there are countable groups that are not a subgroup of a compact group. Hence it might be possible to construct a counter-example using one of these countable groups as the union of the $G_n$. The simplest possible candidate seems to be obtained by taking $G_k = \text{SL}(2,\mathbb{F}_{2^k})$ where $\mathbb{F}_p$ is the field with $p$ elements.

Also, here several countable groups which contain all finite subgroups are defined. This might serve to reduce the discussion to one concrete chain such as $G_1 = S_3, G_{n+1} = S_{G_n}$ where $S_G$ denotes the group of permutations of the elements of $G$ (which contains $G$ a subgroup since each element of $G$ acts on $G$ as a permutation).

share|improve this answer
Instead of the G-H limit one can just take the cartesian product of these groups (a compact group) or an ultraproduct. The problem is that the existence of limit of probabilities is hard to express in these terms. –  Mark Sapir Sep 30 '10 at 1:25
Yes, I know their is a countable group $G$ containing all these finite groups. The problem is that the sequence of uniform measures $\mu_n$ supported on the group $G_n$ do not converge to a measure on $G$ (i.e. the sequence is not tight). The idea then is to find some mode of convergence so that the limit of the sequence $G_n$ is a compact group. Maybe, if done right, the probabilities will have a weak limit. And the supposed "limit values" are simply a probability in the limit group. For obtaining a compact limit I believe G-H might be useful. –  Pablo Lessa Sep 30 '10 at 13:26
arxiv.org/pdf/0810.4062 discusses measures on ultraproducts. –  Mark Sapir Oct 1 '10 at 8:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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