¿Existe una ley 0-1 para la teoría de grupos?

Question

Hace varios meses, Dominik, la pregunta Es hay un 0-1 de la ley para la teoría de grupos? en mathstackexchange, pero a pesar de que su pregunta recibido la atención aún no hay respuesta. Con la pregunta aquí, espero encontrar algún resultado solucionar parcialmente el problema o motivar una respuesta posible.

Por conveniencia, se me pegue la pregunta completa a continuación.

---

Para cada uno de primer orden de la frase $\phi$ en el idioma de los grupos, definir :

$$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}$$

Por lo tanto, $p_N(\phi)$ puede ser considerado como la probabilidad de que $\phi$ es válido en un grupo elegido al azar de la orden de $\le N$.

Ahora defina $$p(\phi)=\lim_{N \to \infty}p_N(\phi)$$ si este límite existe.

Podemos decir que la teoría de los grupos de cumple de primer orden cero-uno de la ley si para cada frase $\phi$, $p(\phi)$ existe y es igual a cualquiera de las $0$ o $1$. Me pregunto si esta 0-1 ley tiene, de hecho, en teoría de grupos.

Ya que se cree que "casi cada grupo es un 2-grupo", declaraciones como las $\exists x: x\ne 1 \wedge x^2=1 \wedge \forall y:xy=yx$ (significado $2|Z(G)$) o $\forall x: x^3=1 \to x=1$ (ningún elemento tiene orden 3) debe tener una probabilidad de $1$ y no veo ninguna posibilidad de construir cualquier frase con $p\not \in \{0,1\}$. Me estoy perdiendo un evidente contraejemplo, o se puede mostrar (bajo la condición de que casi cada grupo es de hecho un 2-grupo) de que la teoría de grupos finitos cumple con este 0-1 ley?

Answer 1

Esto no es una respuesta a la pregunta, sino una expansión de mi comentario anterior. Voy a recapitular brevemente de Compton método para mostrar 0-1 leyes y límite de las leyes para las clases de estructuras algebraicas (en particular, abelian grupos). Por diversas razones, este método no es aplicable a no conmutativa grupos. Estoy confiando en la excelente presentación en [1], donde uno puede encontrar los detalles.

Consideramos clases de $\mathcal A$ finito de estructuras cerrado bajo finito directo de los productos con la propiedad de que todos los $A\in\mathcal A$ puede ser (hasta el isomorfismo) únicamente descomponerse como un producto directo de indecomposable estructuras de $\mathcal A$. Deje $a(n)$ el número de nonisomorphic $A\in\mathcal A$ del tamaño de la $n$, e $A(x)=\sum_{n\le x}a(n)$ (estos son los locales y globales contar funciones de $\mathcal A$, respectivamente). Del mismo modo, si $\mathcal B\subseteq\mathcal A$, vamos a $b(n)$ e $B(x)$ ser su local y global, contando funciones. El objetivo es encontrar condiciones suficientes para garantizar que siempre que $\mathcal B=\{A\in\mathcal A:A\models\phi\}$ para un primer orden de la frase $\phi$, el global asintótica de la densidad de $\mathcal B$, $$\Delta(\mathcal B)=\lim_{n\to\infty}\frac{B(n)}{A(n)},$$ existe (esto se llama una FO límite de la ley para $\mathcal A$), e idealmente, que siempre es $0$ o $1$ (una FO 0-1 de la ley).

Bajo los supuestos anteriores, el isomorfismo clases de $\mathcal A$ formar un multiplicativo de un número de sistema: una libre conmutativa monoid $(\mathsf A,1,\cdot)$ dotado de una norma función de $\|\cdot\|\colon\mathsf A\to(\mathbb N^+,1,\cdot)$ que es un monoid homomorphism tal que $\|x\|=1$ sólo si $x=1$. Aquí, el monoid multiplicación es inducida por el producto directo, y la norma es la cardinalidad. Los generadores libres de $\mathsf A$, o primos, corresponden a la indecomposable álgebras $A\in\mathcal A$. Deje $\mathsf P$ el conjunto de los números primos de $\mathsf A$, y $p(n)$ su local de la función de conteo. El Dirichlet generación de la función de $\mathsf A$ es $$\tag{$*$}\mathbf{A}(x)=\sum_{n\ge1}a(n)n^{-x}=\prod_{n\ge2}(1-n^{-x})^{-p(n)}.$$ Por último, una partición del conjunto es un subconjunto $\mathsf B\subseteq\mathsf A$ que puede ser escrito como $$\mathsf B=\mathsf P_1^{\gamma_1}\cdots\mathsf P_k^{\gamma_k},$$ donde $\mathsf P_1\cup\dots\cup\mathsf P_k=\mathsf P$ es un discontinuo de la partición de $\mathsf P$, y cada una de las $\gamma_i$ representa $m_i$, ${\ge}m_i$, o ${\le}m_i$ con $m_i\in\mathbb N$. Aquí, $\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$, y de la misma manera para ${\le}m$.

Ahora, la estrategia para demostrar la FO límite y 0-1 leyes va como sigue:

1. Si el de la serie de Dirichlet $\mathbf A(x)$ tiene un número finito de abscisa de convergencia $\alpha<\infty$, entonces cada conjunto de particiones $\mathsf B$ tiene una densidad de Dirichlet $$\partial(\mathsf B)=\lim_{x\to\alpha+}\frac{\mathbf B(x)}{\mathbf A(x)},$$ donde $\mathbf B(x)$ es la generación de la función de $\mathsf B$.

2. Si $A(n)$ cumplan algunas condiciones de regularidad (que mantenga por ejemplo, si $A(n)\sim cn^\alpha$), entonces uno puede demostrar que una Tauberian teorema muestra que cada partición tiene un mundial asintótica de la densidad, lo que concuerda con su densidad de Dirichlet. Bajo algunas condiciones, la densidad también resulta ser siempre 0 o 1.

3. Por el Feferman–Vaught teorema, la verdad de cualquier FO frase en un producto directo de $\prod_{i\in I}A_i$ es equivalente a $\mathcal P(I)\models\Phi([[\phi_1]],\dots,[[\phi_k]])$ donde $\Phi$ es una fórmula en el lenguaje de álgebras Booleanas, $\phi_1,\dots,\phi_k$ son frases en el idioma de $\phi$, e $[[\phi]]=\{i\in I:A_i\models\phi\}$. El uso de eliminación de cuantificadores para atómica álgebras Booleanas, se puede hacer aún más $\Phi$ un proposicional combinación de fórmulas afirmando $|[[\phi_j]]|\ge m_j$ de constantes enteras $m_j$. Esto puede ser usado para mostrar que en $\mathcal A$, cada FO frase define un discontinuo de la unión de un número finito de partición de conjuntos. Por lo tanto, si $\alpha<\infty$ e $A(n)$ satisface las condiciones de 2, $\mathcal A$ tiene una FO límite de la ley, o incluso un 0-1 de la ley.

Este mecanismo funciona bien para abelian grupos, y muestra que finito abelian grupos tienen una FO límite de la ley, y por una prima fija $p$, abelian $p$-grupos tienen un 0-1 de la ley. También se puede ver fácilmente que abelian grupos no tienen un 0-1 de la ley. Tenga en cuenta que abelian grupos han $$p(n)=\begin{cases}1&\text{if $n$ is a prime power,}\\0&\text{otherwise,}\end{cases}$$ por lo tanto, por $(*)$, su Dirichlet generación de la función es $$\mathbf A(x)=\prod_{n\ge1}\zeta(nx).$$ La clase $\mathcal B$ de abelian grupos de orden impar tiene un similar de generación de función, pero con los términos de potencias de $2$ eliminado. Desde la abscisa de convergencia es $\alpha=1$ aquí se deduce fácilmente que la de Dirichlet densidad de $\mathcal B$ en relación al $\mathcal A$ es $$\prod_{n\ge1}(1-2^{-n})\approx0{.}29,$$ y por los resultados generales, este también es su densidad asintótica. $\mathcal B$ es de primer orden definible, ya que se compone de abelian grupos con ningún elemento de orden $2$.

Desafortunadamente, esta estrategia no funciona para no conmutativa grupos. Por un lado, los métodos analíticos mediante la generación de Dirichlet de la serie se basan en la condición de que la serie converge al menos en algún lugar, es decir, que la abscisa de convergencia es finito. Esto es equivalente a la condición de que $a(n)$ es exponencialmente limitada. Sin embargo, por los resultados citados anteriormente en los comentarios, el número de grupos de orden $2^n$ es $2^{\tfrac2{27}n^3+O(n^{8/3})}$, que crece demasiado rápido. Lo que es aún peor es que si asumimos que casi todos los grupos se $2$-grupos, y que el número de $2$-grupos crece suavemente suficiente (la estimación anterior no es lo suficientemente precisa para esto), entonces, de hecho, casi todos los grupos están directamente indecomposable, lo que convierte a la que todo el enfoque en su cabeza: si trabajamos solamente con indecomposable estructuras, entonces el hecho de que cada fórmula define una unión de partición de conjuntos lleva cero información, y no hay manera de que todos los conjuntos de indecomposable estructuras podía haber asintótica de la densidad.

Referencia:

[1] Stanley N. Burris, el Número teórico de la densidad y el límite lógico de las leyes, Matemáticas Encuestas y Monografías vol. 86, AMS, 2001, xx+289 pp.

Answer 2

He aquí una propuesta para una posible sentencia con la probabilidad de que no convergen. En realidad, la prueba debe ser duro, y no estoy seguro de cómo la confianza de que debo de estar en ella, pero he pensado que me gustaría poner es: $$\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)$$

Como se discute en los comentarios, se cree que casi todos los grupos se $2$-grupos. El número de grupos de orden $p^n$ es $p^{(2/27) n^3 + O(n^{8/3})}$. (Si escribimos $N = p^n$, esto es $\exp ( (2/27) (\log N)^3/(\log p)^2 + \cdots)$, lo $2$-grupos de abrumar $p$ grupos para otros $p$.) Este es un teorema de Sims.

Vamos a entender lo que el $(2/27) n^3$ proviene. Mirar central extensiones $$0 \to C_p^{n-r} \to G \to C_p^r \to 0.$$ Si nos fijamos en isomorfismo clases de extensiones, esta se clasifica por una $H^2$ grupo de dimensión $f(r):= \binom{r}{2} (n-r) + r(n-r)$; Sims escribe esto explícitamente, cerca del inicio de su papel. Si queremos maximizar $f(r)$ como una función de la $r$, está optimizado en $$r = \begin{cases} 2m & n=3m \\ 2m \ \mbox{and} \ 2m+1 & n=3m+1 \\2m+1 & n=3m+2 \\ \end{cases}$$ y, en esos valores, es $\approx (2/27) n^3$. Por otra parte, esta maxima se encuentran fuertemente alcanzó su punto máximo: El valor de $f(r)$ para cualquier otro $r$ es algo como $n$ inferior. Por lo tanto, si tuviéramos que elegir $r$ en proporción a $\left| H^2(C_p^r, C_p^{n-r}) \right| = p^{f(r)}$, que sería la elección de los valores anteriores con una probabilidad de $1$.

En particular, si tuviéramos que elegir a $r$ en proporción a $|H^2|$, la probabilidad de que $r \geq 2(n-r)$ acercaría $1$ para $n \equiv 0 \bmod 3$, se dirigiría $1/2$ para $n \equiv 1 \bmod 3$ y se dirigiría $0$ para $n \equiv 2 \bmod 3$.

Fijo $w_1$ e $w_2 \in C_p^r$, el mapa de $z \mapsto (w_1 z w_1^{-1} z^{-1}, w_2 z w_2^{-1} z^{-1})$ da un lineal mapa de $C_p^r \to C_p^{2(n-r)}$. Por lo tanto, si $r<2(n-r)$, entonces este mapa no puede ser surjective y $(\ast)$ debe fallar. (En realidad, sólo falla si los conmutadores generar $C_p^{n-r}$. Que se siente como una probabilidad de $1$ declaración, pero el tema debe ser revisado.) Por otro lado, si $r \geq 2(n-r)$, no veo ninguna razón que $(\ast)$ no debe ser cierto.

Esto deja dos preguntas

• En el modelo en el que podemos seleccionar el $r$ proporcional a $\left| H^2(C_p^r, C_p^{n-r}) \right|$ y, a continuación, seleccione al azar de extensión, ¿cómo de probable es condición de $(\ast)$ en los casos en que $r \geq 2(n-r)$?

• Mucho más difícil pregunta: ¿qué tan cerca está el random $H^2$ modelo a la pregunta original? Higman y Sims probar algunos de los resultados a lo largo de esas líneas, pero están muy lejos de ser tan fuerte como nos gustaría. Podemos decir de forma heurística si debemos esperar que la situación real, para ser tan fuertemente alcanzó su punto máximo en un par de valores de $r$ como el juguete modelo es?

Answer 3

La respuesta debe ser "no" para el 0-1 de la ley. Tomemos, por ejemplo, esta frase:

"¿Cuál es la proporción de la plaza libre de números naturales?"

La respuesta es conocido por ser $6/\pi^2$

Luego la convierten en una pregunta sobre finito cíclico grupos:

"¿Cuántos grupos cíclicos $G$ de la orden menos de $N$ tienen la propiedad de que ninguno de sus no-elementos de la unidad $g\in G$ es una raíz cuadrada de la unidad, $g\ne e, g^2=e$?"

Por último, defina la propiedad $\theta$ para un grupo finito $G$, de manera simultánea, siendo cíclico y no tener raíces cuadradas de la unidad.

EDIT: como se señaló en los comentarios, $p(\theta)=0$ debido a que el denominador sigue siendo "todos los grupos de orden $\le N$", no "grupos cíclicos de orden $\le N$".