In an inductive family of groups, does the probability that a particular word is satisfied converge? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T07:40:35Z http://mathoverflow.net/feeds/question/39798 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39798/in-an-inductive-family-of-groups-does-the-probability-that-a-particular-word-is In an inductive family of groups, does the probability that a particular word is satisfied converge? John Wiltshire-Gordon 2010-09-23T22:25:22Z 2010-10-05T23:18:21Z <p>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$.</p> <p>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)$.</p> <p>Now consider some family of finite groups, each injecting into the next:</p> <p>$$G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_n \hookrightarrow \ldots$$</p> <p>Is it true that $p_w(G_n)$ converges to a limit?</p> <p>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.</p> <p>For the word $x_1^2$, the sequence need not be monotonic, but seems to converge anyway.</p> <p>Does anyone know a proof that the limit exists? Or have a counterexample?</p> http://mathoverflow.net/questions/39798/in-an-inductive-family-of-groups-does-the-probability-that-a-particular-word-is/39819#39819 Answer by David Cohen for In an inductive family of groups, does the probability that a particular word is satisfied converge? David Cohen 2010-09-24T04:31:33Z 2010-09-24T05:19:32Z <p><strong>Edit</strong>: As John points out below, this doesn't work.</p> <p>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$.)</p> <p>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$.</p> <p>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}$.)</p> http://mathoverflow.net/questions/39798/in-an-inductive-family-of-groups-does-the-probability-that-a-particular-word-is/40027#40027 Answer by Vipul Naik for In an inductive family of groups, does the probability that a particular word is satisfied converge? Vipul Naik 2010-09-26T14:52:26Z 2010-09-26T16:44:45Z <p>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.</p> <p>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.</p> <p>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)$.</p> <p>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]$.</p> <p>On the other hand, if we restrict ourselves to the variety of abelian groups, <strike>all words</strike> power words (e.g., $x^2$ or $x^3$) are groupy, hence the monotonically decreasing property holds.</p> <p>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.</p> http://mathoverflow.net/questions/39798/in-an-inductive-family-of-groups-does-the-probability-that-a-particular-word-is/40283#40283 Answer by Pablo Lessa for In an inductive family of groups, does the probability that a particular word is satisfied converge? Pablo Lessa 2010-09-28T08:36:31Z 2010-10-05T23:18:21Z <p><strong>Original answer</strong></p> <p>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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Gromov%E2%80%93Hausdorff_convergence" rel="nofollow">the Gromov-Hausdorff sense</a> 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$.</p> <hr> <p><strong>Added later...</strong></p> <p><strong>Compactification and weak limit of probabilities in the case of finite Abelian cyclic groups</strong></p> <p>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$.</p> <p>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.</p> <p><strong>Compactification and weak limit of probabilities in the case of general Abelian finite groups</strong></p> <p>Consider now the case in which all groups $G_k$ are abelian. By the <a href="http://en.wikipedia.org/wiki/Finitely_generated_abelian_group" rel="nofollow">clasification of finite abelian groups</a>, 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.</p> <p>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.</p> <p>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).</p> <p><strong>Further directions</strong></p> <p>The answer to the question posed <a href="http://mathoverflow.net/questions/3420/countable-subgroups-of-compact-groups" rel="nofollow">here</a> 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.</p> <p>Also, <a href="http://mathoverflow.net/questions/28945/infinite-groups-which-contain-all-finite-groups-as-subgroups" rel="nofollow">here</a> 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).</p>