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

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?

share|improve this question
5  
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.? –  Stefan Kohl Dec 2 '13 at 18:11
5  
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". –  Derek Holt Dec 2 '13 at 20:46
3  
@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. –  Michael Dec 2 '13 at 21:18
4  
@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. –  David Speyer Dec 3 '13 at 18:12
3  
@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})$. –  Emil Jeřábek Dec 3 '13 at 22:59
show 8 more comments

3 Answers

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.

share|improve this answer
add comment

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$".

share|improve this answer
4  
This answer is wrong since $p(\theta) = 0 \in \{0,1\}$. -- If it would be that easy, the question wouldn't be interesting. –  Stefan Kohl Dec 2 '13 at 21:35
2  
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. –  Michael Dec 2 '13 at 21:46
10  
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. –  Joel David Hamkins Dec 2 '13 at 21:52
4  
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.) –  Joel David Hamkins Dec 2 '13 at 22:48
4  
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. –  Emil Jeřábek Dec 3 '13 at 12:30
show 3 more comments

Let me give it another try by conjecturing again that the answer is "no", but for a different reason: $lim_{N\to\infty}p_N(\theta)$ may not exist.

According to this, the number of groups of order $\le N$ is dominated by the groups of order $2^n$, where $n$ is the largest integer such that $2^n\le N$. Therefore the term

number of nonisomorphic groups $G$ of order $\le N$ such that $\theta$ is valid in $G$

is dominated by the term

number of nonisomorphic groups $G$ of order $2^n$ such that $\theta$ is valid in $G$, where $n$ is the largest integer such that $2^n\le N$

It now remains to specify a property $\theta$ that would be true for groups of order $2^{2k}$ and false for groups of order $2^{2k+1}$ to show that $p_N(\theta)$ need not converge as $N\to\infty$.

I don't know whether the property "being a group of order $2^{2k}$" qualifies as a first-order statement in the language of groups. If not, perhaps somebody else would come up with an appropriate $\theta$.

share|improve this answer
1  
No, it does not qualify. Things would be way too easy if we could express properties of the order like this. –  Emil Jeřábek Dec 3 '13 at 19:05
1  
In fact, I am confident there is no FO sentence $\phi$ such that $C_{2^n}\models\phi$ for infinitely many $n$, and $C_{2^n}\models\neg\phi$ for infinitely many (other) $n$. Otherwise by compactness, both $\phi$ and $\neg\phi$ would be consistent with the following set of FO sentences $T$: “$G$ is an abelian group with no element of odd order and a unique element of order $2$, $G$ is $p$-divisible for each odd prime $p$, $G/2G=C_2$, and there are elements of order $2^k$ for each $k$”. However, I believe $T$ is a complete theory (and has quantifier elimination in a suitably expanded language). –  Emil Jeřábek Dec 3 '13 at 20:18
    
@EmilJeřábek, could you remind which group is denoted $C_{2^n}$? Also, could you give an example of $G$ with the property $T$? –  Michael Dec 3 '13 at 20:57
    
$C_{2^n}$ is the cyclic group with $2^n$ elements. The example of $G$ relevant here would be an ultraproduct of $\{C_{2^n}:n\in X\}$ over a nonprincipal ultrafilter on $X$, however, an explicit example of such a group can be the direct sum of the Prüfer $2$-group and the additive group of $2$-adic integers. –  Emil Jeřábek Dec 3 '13 at 21:14
4  
I realized the point can be made in a much more simple way. There is no FO sentence that would separate two infinite sets of groups of the form $C_2^n$: both the sentence and its negation would then be satisfied in an infinite abelian group of exponent $2$, however the latter theory (which is a notational variant for infinite-dimensional vector spaces over $\mathbb F_2$) is categorical in every cardinality, and therefore complete. –  Emil Jeřábek Dec 3 '13 at 22:11
show 1 more comment

Your Answer

 
discard

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.