224
$\begingroup$

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$
30
  • 9
    $\begingroup$ $\mathcal L_{\text{grp}}=\{e,\circ,{}^{-1}\}$. What is unclear to you? $\endgroup$
    – Dominik
    Jun 30, 2013 at 21:09
  • 8
    $\begingroup$ No since, in first order logic, quantifiers refer only to elements of your group, not to functions or subsets of the group. $\endgroup$
    – Dominik
    Jun 30, 2013 at 21:14
  • 26
    $\begingroup$ @Alexander: there doesn't exist a first-order sentence in the language of groups which is true precisely of the nilpotent groups, although this isn't obvious. The reason is that the class of nilpotent groups isn't closed under ultraproducts (see en.wikipedia.org/wiki/Ultraproduct#.C5.81o.C5.9B.27s_theorem). However, there is a first-order sentence which is true precisely of the $k$-step nilpotent groups for a fixed $k$, the reason being that $k$-step nilpotence is equivalent to the vanishing of a finite collection of iterated commutators. $\endgroup$ Jun 30, 2013 at 21:21
  • 9
    $\begingroup$ Since nobody responded to my 500 bounty, I suggest you crosspost this question to MO, if you haven't already. $\endgroup$
    – Alexander Gruber
    Sep 16, 2013 at 23:23
  • 9
    $\begingroup$ The question has now been crossposted at mathoverflow.net/questions/150603 . $\endgroup$ Dec 5, 2013 at 14:14

2 Answers 2

4
$\begingroup$

Sharing the question within MO has brought some interesting comments - I send you there for reference - but in the last 2 years there has been no new contribution. So I'm wrapping it up for the less technical scope of SE:

As per now, a FO 0-1 law for group theory as defined by Dominik doesn't exist and may never exist.

The consensus seems to be that an accepted and complete view of what group theoretic concepts correspond to in a classical logic framework is needed to address the problem but - as per now - it is not available.

The actual methods available to cross-translate group theoretic concepts into logic ones seem to suggest that such a law cannot exist for the whole group theory or even for finite group theory. Limiting laws have infact been identified such that group theoretical entities can be partitioned into different classes exhibiting different logical behaviours (i.e. quantification over functions which is ubiquitous in group theory; but also abelianity appears to be relevant). While yet to be proven, some of these classes can be expected to obey a 0-1 law for FOL while some others can be expected to not obey it.

$\endgroup$
-6
$\begingroup$

Sentence proposals:

  1. The cardinality of $G$ is even.

    • I strongly suspect the limit diverges by having a zero $\lim\inf$ and a unit $\lim \sup$. Via supermultiplicity, the number of groups of order $2^k n$ is bounded below by the number of order $2^k$ times the number of order $n$, so is infrequently "small" ($n$ prime) and frequently large. Additionally, the number of groups of a given order is upper bounded (see http://www.jstor.org/stable/2946623 ) by something not too stupendously rapidly growing, so no $N$ is going to miraculously overwhelm the running average.
  2. Let $P(n)$ be the cardinality of the set of isomorphism classes of groups of order $n$. For all positive integers $n$, $P(n)>0$ since there is at least a cyclic group of order $n$. Let $C(n) = \sum_{i=1}^n P(n)$, which is clearly positive and monotonically increasing on the positive integers. Set $a_0=1$ and, for $j>0$, set $a_j = \min_i\{i \mid C(i)-a_{j-1} > 2^{2j}\}$, such an $i$ exists because $C$ is monotonically increasing. Let $T = \bigcup_{j=0}^\infty [a_{2j}, a_{2j+1})$ and let $\phi$ be the predicate $|G| \in T$. By construction, $p_N(\phi)$ swings by a factor of two through each interval $[a_j, a_{j+1})$ (from something < $2^{-j}$ to something $> 1- 2^{-j}$ and vice versa). Therefore, the limit as $N$ goes to infinity does not exist.

    • It's not clear to me how this sort of see-saw argument fails in any set that has something like a positive semidefinite inverse norm with infinite support. ($P(n)$ is that inverse norm here, taking cardinalities (a usual norm) to the number of isomorphism classes.)
$\endgroup$
26
  • 5
    $\begingroup$ Heuristically "almost all groups are $2$-groups," so we can confidently predict that "the cardinality of $G$ is even" will correspond to a probability of zero. $\endgroup$
    – anon
    Feb 12, 2014 at 8:22
  • 4
    $\begingroup$ @anon Shouldn't that be probability $1$ instead? $\endgroup$
    – EuYu
    Feb 12, 2014 at 8:28
  • 5
    $\begingroup$ @EricTowers The point is that before you get to the groups of order $3\cdot 2^k$ you hit the groups of order $2\cdot 2^k = 2^{k+1}$ and there are so vastly many of those that they dwarf the groups of $3\cdot 2^k$. The bias doesn't 'settle out' because 2 is the smallest number, so among the numbers with prime multiplicity $k$ $2^k$ is always smallest. $\endgroup$ Feb 12, 2014 at 17:29
  • 3
    $\begingroup$ @EricTowers More than 99% of all the groups of order less than 2047 have order 1024. And it's known that there are at least 20,000 times as many groups of order 2048 as of order 1024. I'm not sure where your 'gradual majority of odds to evens' is coming from. $\endgroup$ Feb 24, 2014 at 7:30
  • 7
    $\begingroup$ @EricTowers Can you point to a single $n\gt 256$ where the majority of groups of order $\leq n$ are not of order a power of 2? $\endgroup$ Feb 25, 2014 at 7:14

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