67
$\begingroup$

Several months ago, Dominik asked the question Is there a 0-1 law for the theory of groups? on mathstackexchange, but although his question received attention there is still no answer. By asking the question here, I hope to find some result solving partially the problem or motivating a possible answer.

For convenience, I paste the complete question below.


For each first order sentence $\phi$ in the language of groups, define :

$$p_N(\phi)=\frac{\text{number of nonisomorphic groups $G$ of order} \le N\text{ such that } \phi \text{ is valid in } G}{\text{number of nonisomorphic groups of order} \le N}$$

Thus, $p_N(\phi)$ can be regarded as the probability that $\phi$ is valid in a randomly chosen group of order $\le N$.

Now define $$p(\phi)=\lim_{N \to \infty}p_N(\phi)$$ if this limit exists.

We say that the theory of groups fulfills a first order zero-one law if for every sentence $\phi$, $p(\phi)$ exists and equals either $0$ or $1$. I'm asking myself whether this 0-1 law holds indeed in group theory.

Since it is conjectured that "almost every group is a 2-group", statements like $\exists x: x\ne 1 \wedge x^2=1 \wedge \forall y:xy=yx$ (meaning $2|Z(G)$) or $\forall x: x^3=1 \to x=1$ (no element has order 3) should have probability $1$ and I don't see any possibility to construct any sentence with $p\not \in \{0,1\}$. Am I missing an obvious counterexample, or can you show (under the condition that almost every group is indeed a 2-group) that the theory of finite groups fulfills this 0-1 law?

$\endgroup$
14
  • 7
    $\begingroup$ I think your definition of $p_N(\phi)$ is maybe not really what one wants here, as the order of a group is not a good measure for how much structure it may have: e.g. why should one give the 2328 groups of order $2^7$ in a sense a higher weight than the 9310 groups of order $3^7$, the 34297 groups of order $5^7$, the 113147 groups of order $7^7$, etc.? $\endgroup$
    – Stefan Kohl
    Dec 2, 2013 at 18:11
  • 6
    $\begingroup$ It's an interesting question, and it would be very surprising indeed if the answer was no (even if it is not true that almost all groups are class 2 nilpotent, then it seems very implausible that half of there are), but unfortunately there seems to be no prospects at all of resolving it. Or rather, it could only be resolved if it could somehow be proved true without needing to know much about the intricate details of the structure of "almost all groups". $\endgroup$
    – Derek Holt
    Dec 2, 2013 at 20:46
  • 3
    $\begingroup$ @StefanKohl, I think $p_N(\theta)$ is a legitimate measure, in many way similar to the measure of natural numbers less than $N$. One can associate a natural number $n$ with the cyclic group $Z_n$ to show that natural numbers have "structure" (a.k.a. prime decomposition) and "order" (magnitude). And yet in the questions such as "what's the proportion of primes among natural numbers" one often takes essentially the same measure, the limit of the proportion among the natural numbers under $N$ for $N\to \infty$, as in this question for groups. $\endgroup$
    – Michael
    Dec 2, 2013 at 21:18
  • 4
    $\begingroup$ @Michael The number of groups of order $p^n$ is $p^{\frac{2}{27} n^3 + O(n^{8/3})}$, see plms.oxfordjournals.org/content/s3-15/1/151.full.pdf . The number of extensions $1 \to C_p^{\lceil n/3 \rceil} \to G \to C_p^{\lfloor 2n/3 \rfloor} \to 1$ is also $p^{\frac{2}{27} n^3 + O(n^{8/3})}$ (with the $O()$ representing a different function of course.) This is the basis for the conjecture that almost all groups are $2$-step extensions, although these bounds aren't tight enough to prove that. The division by $3$ suggests we might be able to detect $n \bmod 3$, but I couldn't figure out how. $\endgroup$ Dec 3, 2013 at 18:12
  • 3
    $\begingroup$ @Joel: According to math.uwaterloo.ca/~snburris/htdocs/DENSITY/overview.pdf , abelian groups have a limit law, but not a 0–1 law, and he gives an example that the probability of an abelian group having an element of order $2$ is $1-\prod_{n\ge1}(1-2^{-n})$. $\endgroup$ Dec 3, 2013 at 22:59

3 Answers 3

18
$\begingroup$

This is not an answer to the question, but an expansion of my comment above. I’m going to briefly recap Compton’s method for showing 0–1 laws and limit laws for classes of algebraic structures (in particular, abelian groups). For various reasons, this method is not applicable to noncommutative groups. I’m relying on the excellent presentation in [1], where one can find the details.

We consider classes $\mathcal A$ of finite structures closed under finite direct products with the property that every $A\in\mathcal A$ can be (up to isomorphism) uniquely decomposed as a direct product of indecomposable structures from $\mathcal A$. Let $a(n)$ be the number of nonisomorphic $A\in\mathcal A$ of size $n$, and $A(x)=\sum_{n\le x}a(n)$ (these are the local and global counting functions of $\mathcal A$, respectively). Likewise, if $\mathcal B\subseteq\mathcal A$, let $b(n)$ and $B(x)$ be its local and global counting functions. The goal is to find sufficient conditions to guarantee that whenever $\mathcal B=\{A\in\mathcal A:A\models\phi\}$ for a first-order sentence $\phi$, then the global asymptotic density of $\mathcal B$, $$\Delta(\mathcal B)=\lim_{n\to\infty}\frac{B(n)}{A(n)},$$ exists (this is called an FO limit law for $\mathcal A$), and ideally, that it is always $0$ or $1$ (an FO 0–1 law).

Under the assumptions above, the isomorphism classes of $\mathcal A$ form a multiplicative number system: a free commutative monoid $(\mathsf A,1,\cdot)$ endowed with a norm function $\|\cdot\|\colon\mathsf A\to(\mathbb N^+,1,\cdot)$ which is a monoid homomorphism such that $\|x\|=1$ only if $x=1$. Here, the monoid multiplication is induced by direct product, and the norm is cardinality. The free generators of $\mathsf A$, or primes, correspond to the indecomposable algebras $A\in\mathcal A$. Let $\mathsf P$ be the set of primes of $\mathsf A$, and $p(n)$ its local counting function. The Dirichlet generating function of $\mathsf A$ is $$\tag{$*$}\mathbf{A}(x)=\sum_{n\ge1}a(n)n^{-x}=\prod_{n\ge2}(1-n^{-x})^{-p(n)}.$$ Finally, a partition set is a subset $\mathsf B\subseteq\mathsf A$ that can be written as $$\mathsf B=\mathsf P_1^{\gamma_1}\cdots\mathsf P_k^{\gamma_k},$$ where $\mathsf P_1\cup\dots\cup\mathsf P_k=\mathsf P$ is a disjoint partition of $\mathsf P$, and each $\gamma_i$ stands for $m_i$, ${\ge}m_i$, or ${\le}m_i$ with $m_i\in\mathbb N$. Here, $\mathsf B\cdot\mathsf C=\{bc:b\in\mathsf B,c\in\mathbf C\}$, $\mathsf B^m=\underbrace{\mathsf B\cdots\mathsf B}_{m}$, $\mathsf B^{\ge m}=\bigcup_{n\ge m}\mathsf B^n$, and likewise for ${\le}m$.

Now, the strategy for proving FO limit and 0–1 laws goes as follows:

  1. If the Dirichlet series $\mathbf A(x)$ has a finite abscissa of convergence $\alpha<\infty$, then every partition set $\mathsf B$ has a Dirichlet density $$\partial(\mathsf B)=\lim_{x\to\alpha+}\frac{\mathbf B(x)}{\mathbf A(x)},$$ where $\mathbf B(x)$ is the generating function of $\mathsf B$.

  2. If $A(n)$ satisfies some regularity conditions (which hold e.g. if $A(n)\sim cn^\alpha$), then one can prove a Tauberian theorem showing that every partition set has a global asymptotic density, which agrees with its Dirichlet density. Under some conditions, the density also turns out to be always 0 or 1.

  3. By the Feferman–Vaught theorem, the truth of any FO sentence in a direct product $\prod_{i\in I}A_i$ is equivalent to $\mathcal P(I)\models\Phi([[\phi_1]],\dots,[[\phi_k]])$, where $\Phi$ is a formula in the language of Boolean algebras, $\phi_1,\dots,\phi_k$ are sentences in the language of $\phi$, and $[[\phi]]=\{i\in I:A_i\models\phi\}$. Using elimination of quantifiers for atomic Boolean algebras, one can further make $\Phi$ a propositional combination of formulas asserting $|[[\phi_j]]|\ge m_j$ for integer constants $m_j$. This can be used to show that in $\mathcal A$, every FO sentence defines a disjoint union of finitely many partition sets. Thus, if $\alpha<\infty$ and $A(n)$ satisfies the conditions from 2, $\mathcal A$ has an FO limit law, or even a 0–1 law.

This machinery works well for abelian groups, and shows that finite abelian groups have an FO limit law, and for a fixed prime $p$, abelian $p$-groups have a 0–1 law. One can also readily see that abelian groups do not have a 0–1 law. Note that abelian groups have $$p(n)=\begin{cases}1&\text{if $n$ is a prime power,}\\0&\text{otherwise,}\end{cases}$$ hence by $(*)$, their Dirichlet generating function is $$\mathbf A(x)=\prod_{n\ge1}\zeta(nx).$$ The class $\mathcal B$ of abelian groups of odd order has a similar generating function but with the terms for powers of $2$ removed. Since the abscissa of convergence is $\alpha=1$ here, it follows easily that the Dirichlet density of $\mathcal B$ relative to $\mathcal A$ is $$\prod_{n\ge1}(1-2^{-n})\approx0{.}29,$$ and by the general results, this is also its global asymptotic density. $\mathcal B$ is first-order definable, as it consists of abelian groups with no element of order $2$.

Unfortunately, this strategy does not work for noncommutative groups. For one thing, the analytic methods using Dirichlet generating series rely on the condition that the series converges at least somewhere, i.e., that the abscissa of convergence is finite. This is equivalent to the condition that $a(n)$ is polynomially bounded. However, by results quoted above in the comments, the number of groups of order $2^n$ is $2^{\tfrac2{27}n^3+O(n^{8/3})}$, which grows much too fast. What is even worse is that if we assume that almost all groups are $2$-groups, and that the number of $2$-groups grows smoothly enough (the estimate above is not precise enough for this), then in fact almost all groups are directly indecomposable, which turns the whole approach on its head: if we deal only with indecomposable structures, then the fact that every formula defines a union of partition sets carries zero information, and there is no way that all sets of indecomposable structures could have asymptotic density.

Reference:

[1] Stanley N. Burris, Number theoretic density and logical limit laws, Mathematical Surveys and Monographs vol. 86, AMS, 2001, xx+289 pp.

$\endgroup$
8
$\begingroup$

Here is a proposal for a possible sentence with probability that doesn't converge. Actually proving it should be hard, and I'm not sure how confident I should be in it but I thought I'd put it out there: $$\exists_{w_1,w_2} \forall_{x_1, y_1, x_2, y_2} \exists_{z} \ w_1 z w_1^{-1} z^{-1} = x_1 y_1 x_1^{-1} y_1^{-1} \ \mbox{and} \ w_2 z w_2^{-1} z^{-1} = x_2 y_2 x_2^{-1} y_2^{-1} \quad (\ast)$$

As discussed in comments, it is thought that almost all groups are $2$-groups. The number of groups of order $p^n$ is $p^{(2/27) n^3 + O(n^{8/3})}$. (If we write $N = p^n$, this is $\exp ( (2/27) (\log N)^3/(\log p)^2 + \cdots)$, so $2$-groups overwhelm $p$ groups for other $p$.) This is a theorem of Sims.

Let's understand where the $(2/27) n^3$ comes from. Look at central extensions $$0 \to C_p^{n-r} \to G \to C_p^r \to 0.$$ If we look at isomorphism classes of extensions, this is classified by an $H^2$ group of dimension $f(r):= \binom{r}{2} (n-r) + r(n-r)$; Sims writes this down explicitly near the start of his paper. If we maximize $f(r)$ as a function of $r$, it is optimized at $$r = \begin{cases} 2m & n=3m \\ 2m \ \mbox{and} \ 2m+1 & n=3m+1 \\2m+1 & n=3m+2 \\ \end{cases}$$ and, at those values, it is $\approx (2/27) n^3$. Moreover, this maxima are sharply peaked: The value of $f(r)$ for any other $r$ is something like $n$ lower. So, if we were to choose $r$ in proportion to $\left| H^2(C_p^r, C_p^{n-r}) \right| = p^{f(r)}$, we would be choosing the values above with probability $1$.

In particular, if we were choosing $r$ in proportion to $|H^2|$, the probability that $r \geq 2(n-r)$ would approach $1$ for $n \equiv 0 \bmod 3$, would approach $1/2$ for $n \equiv 1 \bmod 3$ and would approach $0$ for $n \equiv 2 \bmod 3$.

For fixed $w_1$ and $w_2 \in C_p^r$, the map $z \mapsto (w_1 z w_1^{-1} z^{-1}, w_2 z w_2^{-1} z^{-1})$ gives a linear map $C_p^r \to C_p^{2(n-r)}$. So, if $r<2(n-r)$, then this map can't possibly be surjective and $(\ast)$ must fail. (Actually, it only fails if commutators generate $C_p^{n-r}$. That feels like a probability $1$ statement, but the issue should be checked.) On the other hand, if $r \geq 2(n-r)$, I see no reason that $(\ast)$ shouldn't be true.

This leaves two questions

  • In the model where we select $r$ proportional to $\left| H^2(C_p^r, C_p^{n-r}) \right|$ and then select a random extension, how likely is condition $(\ast)$ in the cases where $r \geq 2(n-r)$?

  • A much more difficult question: How close is the random $H^2$ model to the original question? Higman and Sims prove some results along those lines, but they are very far from as strong as we'd want. Can we say heuristically whether we should expect the real situation to be as strongly peaked at a few values of $r$ as the toy model is?

$\endgroup$
2
  • $\begingroup$ Just to check -- I'm guessing the initial $w_1 z w_1^{-1} z$ in the statement should be $w_1 z w_1^{-1} z^{-1}$? $\endgroup$ Aug 8, 2014 at 13:40
  • $\begingroup$ @HarryAltman Oops! Thanks for the correction. $\endgroup$ Aug 8, 2014 at 13:42
-1
$\begingroup$

The answer should be "no" for the 0-1 law. Take, for example, this sentence:

"What is the proportion of square-free natural numbers?"

The answer is known to be $6/\pi^2$

Then turn it into a question about finite cyclic groups:

"How many cyclic groups $G$ of order less than $N$ have the property that none of its non-unit elements $g\in G$ is a square root of unity, $g\ne e, g^2=e$?"

Finally, define property $\theta$ for a finite group $G$ as simultaneously being cyclic and having no square roots of unity.

EDIT: as pointed out in the comments, $p(\theta)=0$ because the denominator remains "all groups of order $\le N$", not "cyclic groups of order $\le N$".

$\endgroup$
8
  • 4
    $\begingroup$ This answer is wrong since $p(\theta) = 0 \in \{0,1\}$. -- If it would be that easy, the question wouldn't be interesting. $\endgroup$
    – Stefan Kohl
    Dec 2, 2013 at 21:35
  • 2
    $\begingroup$ Oops, you are right, I meant $p(\theta)/p(being_{ }cyclic)=6/\pi^2$. Need to think whether the answer is recoverable for the property of not having square roots of unity alone, w/out being cyclic. $\endgroup$
    – Michael
    Dec 2, 2013 at 21:46
  • 11
    $\begingroup$ Another problem with this answer is that being cyclic is not expressible in the language of groups. So the assertion $\theta$ that is discussed is not in the desired language. $\endgroup$ Dec 2, 2013 at 21:52
  • 5
    $\begingroup$ The language of groups allows you to form terms using the group operation, to express equalities and inequalities, to use logical connectives and to quantify over the elements of the group ("there is a group element $x$ such that..." or "for every element $x$ in the group..."). You may not generally quantify over natural numbers, over subsets of the group, over homomorphisms etc. (Those are expressible in more powerful languages, such as the language of set theory or suitable category-theoretic languages, but not in the language of groups.) $\endgroup$ Dec 2, 2013 at 22:48
  • 4
    $\begingroup$ Joel is quite right, but I think it should be mentioned that while the question asks specifically about first-order logic, where cyclicity is indeed not expressible, there is nothing particularly fundamental about this choice. People have studied 0–1 laws for various extensions of FO that can express cyclicity, like FO(TC), FO(IFP), or MSO. Even more importantly, when we discuss a 0–1 law for a certain logic relative to a class of structures, there is no need for this class to be itself definable in said logic. It makes perfect sense to consider an FO 0–1 law on the class of all cyclic groups. $\endgroup$ Dec 3, 2013 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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