This is a generalization of the following question by John Wiltshire-Gordon.

Consider an inductive family of finite groups: $$ G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i \hookrightarrow \ldots $$

We may view each group as a subgroup of the next. Let $G$ be the directed union of the $G_i$: $$ G := \bigcup_{i=0}^\infty \ G_i $$

Now, $G$ is a countable group. Suppose we're asked a question like, "What proportion of the elements of $G$ are commutators?", or "What proportion of pairs $(g,h) \in G^2$ satisfy $g^2h^2=1$ but $g^2 \neq 1$?" We try to make sense of such questions in terms of density on $G^n$, which is not defined for all subsets. For $E \subseteq G^n$, let $$ d(E) := \lim_{i \to \infty} \frac{|E \cap G_i^n|}{|G_i^n|}, $$ if the limit exists.

My question is: If $E$ is a subset of $G^n$ that is first-order definable in the language of groups, does the density of $E$ necessarily exist? John's question covers the (still unresolved) special case of when $E$ is defined by an atomic formula.

A first-order definable subset $E \subseteq G^n$ is the set of $n$-tuples of group elements where a particular first-order formula in $n$ free variables is true. Such a formula is a finite string of symbols and may involve multiplication, inversion, the identity element, equality, logical connectives ($\wedge$, $\vee$, $\neg$, $\implies$), quatifiers ($\exists$ and $\forall$), and parentheses. For example, the following first-order formula defines the set of commutators $g \in G$:

$$ (\exists x)(\exists y)(g = xyx^{-1}y^{-1}). $$

On the other hand, if you try to define the commutator subgroup by such a formula, you run into trouble. You might want to say, "$g$ is a commutator or $g$ is a product of two commutators or $g$ is a product of three commutators or ...," but infinite disjunctions are not allowed.

Please note that the counterexample to a similar question in a comment by Vipul Naik here is not a counterexample to this question. In the inductive family $$ A_3 \hookrightarrow S_3 \hookrightarrow \ldots \hookrightarrow A_{2i-1} \hookrightarrow S_{2i-1} \hookrightarrow A_{2i+1} \hookrightarrow S_{2i+1} \hookrightarrow \ldots, $$ the groups alternate between having all the elements as commutators and half the elements as commutators. However, in the directed union, which is $A_\infty$, all the elements are commutators. The upshot is that quantifiers in a first-order formula may demand that you "look ahead" in your inductive family.

  • $\begingroup$ This shouts "zero-one law" at me. Perhaps looking at limit laws, and works of Vardi, Fagin, and others on finite structures may give you what you want. Gerhard "Ask Me About System Design" Paseman, 2010.10.27 $\endgroup$ Oct 27, 2010 at 23:27
  • $\begingroup$ @Gerhard: It's not true that you'll always get density zero or one, if that's what you mean. For the union $S_\infty$ of the symmetric groups $$ S_1 \hookrightarrow S_2 \hookrightarrow \ldots \hookrightarrow S_n \hookrightarrow \ldots, $$ the set of commutators is $A_\infty$, and its density is $1/2$. An even more basic example would be the set of elements squaring to one in the union of the groups $\mathbb{Z}/3\mathbb{Z} \times (\mathbb{Z}/2\mathbb{Z})^i$, which has density $1/3$. $\endgroup$ Oct 29, 2010 at 8:36
  • $\begingroup$ It may also not be true that you will get a density, i.e. that there will be a limit law. I definitely don't know, but Vardi might. Gerhard "Ask Me About System Design" Paseman, 2010.11.02 $\endgroup$ Nov 2, 2010 at 8:06
  • 1
    $\begingroup$ This is a great question. $\endgroup$ Nov 4, 2010 at 16:28
  • 1
    $\begingroup$ I agree, cool question! $\endgroup$ Nov 4, 2010 at 20:56


Your Answer

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

Browse other questions tagged or ask your own question.