User davidlharden - MathOverflow

Known and unknown about Ramanujan's tau function

2013-03-16T10:59:09Z

What is a good reference for open problems relating to the Ramanujan tau function?

I know about Lehmer's conjecture. I know the following reductions of the problem: the smallest counterexample must be a power of a prime (by the multiplicativity of $\tau$), it must be a prime (by considering the linear recurrence expressing $\tau(p^{n})$ in terms of $\tau(p^{n-1})$ and $\tau(p^{n-2})$ ), and it must be a prime $p$ such that $p \equiv -1 \mod{691}$ (this follows from the congruence $\sigma_{11}(n) \equiv \tau(n) \mod{691}$). Are all the other reductions, like the last one I mentioned, just obtained from congruences satisfied by $\tau$?

I have read that problems about the sign of $\tau$ tend to be hard, but I don't know precisely about this (aside from the problem I just mentioned about the vanishing of $\tau$). Where would problems about the sign of $\tau$ be discussed in detail?

A non-commutative ring from SU(2)

2012-12-30T09:32:38Z

$SU(2)$, which will be regarded here as the group of unit quaternions under multiplication, has 3 conjugacy classes of finite subgroups which don't have cyclic subgroups of index 1 or 2. They are:

of order $24$, the binary tetrahedral group $ T^{ * } \cong SL(2,3)$
of order $120$, the binary icosahedral group $ I^{ * } \cong SL(2,5)$
of order $48$, the binary octahedral group $ O^{ * }$, which doubly covers $S_{4}$ but is not isomorphic to $SL(2, \mathbb{Z}/(4))$ or $GL(2,3)$

The ring of all sums (using quaternion addition) of elements of $ T^{ * }$ is the Hurwitz ring of integral quaternions. The ring of all sums of elements of $ I^{ * } $ is the icosian ring, which was studied by Hamilton and can be identified with the $E_{8}$ root lattice.
My questions are about the ring of sums of elements of $O^{ * }$. I did not see references to it in SPLAG (which even comes close when discussing lattices over the subring $\mathbb{Z}[e^{\frac{2\pi i}{8}}]$, and discusses both the $E_{8}$ and Leech lattices as icosian lattices), and it's hard to look up a structure whose name I don't know. Does anyone know of a reference that explores this ring in non-trivial depth? Does this ring have a standard name?

Answer by DavidLHarden for Groups that do not exist

2012-12-08T20:49:46Z

There was a point during the history of the Classification when pursuers of sporadic groups distinguished the Baby Monster, the Middle Monster and the Super Monster. The first two actually turned out to exist (though the word "Middle" was dropped), but the third turned out to be a dud.

http://www.neverendingbooks.org/index.php/tag/simples/page/2 has an account of this.

Answer by DavidLHarden for Examples where adding complexity made a problem simpler

2012-11-26T02:26:44Z

Some smaller examples: sometimes a group is best understood by embedding it in a larger group. One can use the embedding of a finite group in a large enough $GL(n, \mathbb{C})$ as a very general example (representation theory is quite powerful, even just in characteristic 0), but some far more localized examples:

The reason plenty of subgroups of $S_{6}$ have two non-conjugate embeddings in $S_{6}$ is explainable by embedding $S_{6}$ in $Aut(S_{6})$. Likewise for $AGL_{3}(2)$ and $M_{12}$.

Much of the structure of $M_{22}$ and $M_{23}$ is most easily understood in terms of $M_{24}$.

Answer by DavidLHarden for "Mathematics talk" for five year olds

2012-10-01T22:07:31Z

When I was an undergrad, I heard a story where a young child was excited by watching 6 equal-sized equilateral triangles fit together to form a regular hexagon. I don't remember what her age was, but this sounds doable for 5-year-olds, especially if you make the triangles take the colors of the rainbow, excluding indigo.
This is exceptional, in that this is the only example of a regular polygon decomposable as the finite disjoint (except for boundaries) union of smaller regular polygons of a different shape. If one drops the "different shape" requirement, one can put equilateral triangles together to make a bigger equilateral triangle or put squares together to make a bigger square.
But 5 may be too young to get a feel for how, for example, angles work. I don't know how they'll handle failing to put equilateral triangles to make a square, for example.

Globally irreducible lattices

2012-06-27T10:42:06Z

Here I am only interested in globally irreducible lattices over $\mathbb{Z}$.

The basic theorem concerning these says that a globally irreducible lattice is similar to a lattice which is integral and unimodular. With that scaling, the lattice will also be even, except in the degenerate case where the dimension is 1 and the lattice is just $\mathbb{Z}$ itself.
I see how the proof goes, except for one gap:

Let $\Lambda$ be globally irreducible. This means that, for any prime $p \in \mathbb{Z}$, $Aut(\Lambda)$ acts irreducibly on $\Lambda / p\Lambda$. It is easy to show (so I will skip the proof) that this condition implies every invariant sublattice of $\Lambda$ is of the form $k\Lambda$ for some nonnegative integer $k$.
Global irreducibility is not affected by scaling $\Lambda$. The gap: I am assuming any two nonzero inner products of vectors in $\Lambda$ have a rational quotient.
Assuming that, let $v_{1}, \ldots , v_{n}$ be an integral basis for $\Lambda$ (so $n = \mathrm{dim}(\Lambda)$). Then it is possible to scale $\Lambda$ so that all $v_{i} \cdot v_{j}$, where $1 \leq i \leq j \leq n$, are integers whose greatest common factor is 1. Then $\Lambda$ is integral.
Evenness is immediate: Since $\Lambda$ is integral, the identity $|u+v|^{2} = |u|^{2} + |v|^{2} + 2u \cdot v$ means that the set of vectors $v$ such that $|v|^{2}$ is even is an invariant sublattice of $\Lambda$ (whose index, as an additive subgroup, is 1 or 2). But also this sublattice is of the form $k\Lambda$ for some $k \geq 1$ and the index of this sublattice is $k^{\mathrm{dim}(\Lambda)}$. If $\mathrm{dim}(\Lambda) > 1$, $k^{\mathrm{dim}(\Lambda)} = 2$ is impossible so $k^{\mathrm{dim}(\Lambda)} = 1$ and $k = 1$.
Unimodularity sounds not so hard to prove: If there is a prime $p$ dividing the determinant of the Gram matrix of $\Lambda$, the choice of scaling means $p$ does not divide all the entries in the Gram matrix. Then the row space of the Gram matrix should lead to (though I am unclear on the details of this, I am not asking about this at the moment) an invariant subspace of $\Lambda / p\Lambda$ (which should be proper since the Gram matrix is nonzero modulo $p$ but the determinant modulo $p$ is 0).

What is the easiest way to fill in the gap?

Does the quaternion group Q_8 have a presentation of this form?

2012-01-30T06:20:15Z

In http://mathoverflow.net/questions/77517/, a key step in the proof of the congruence saying that $G$ being a $p$-group means that $|G| \equiv c(G) \mod{(p^{2}-1)(p-1)}$ is the construction of a finite group (denoted $P$ in that post) whose relations, as given, are satisfied by ${every}$ word in the generators.

Let $Q$ denote a finite $p$-group which has a presentation of the kind possessed by $P$. More precisely, suppose $Q$ is generated by $x_{1}, \ldots, x_{r}$ and that the relations defining $Q$ are given in infinite families, where each family is of the form $w( e_{1}, \ldots, e_{L} ) = 1$, where $w$ is some word in the free group on $L$ generators and $e_{1}, \ldots, e_{L}$ vary independently over all words in $x_{1}, \ldots, x_{r}$.

The reasoning from before should apply (though I cannot fill in all gaps) to describe $Aut(Q)$ (and obtain its order):
Since $Q$ is finite, an endomorphism $\phi: Q \to Q$ is injective iff it is surjective. So an endomorphism of $Q$ is an automorphism iff it is surjective. If $\phi(x_{1}), \ldots, \phi(x_{r})$ do not generate all of $Q$, then they subgroup they generate is contained (since $Q$ is finite) in some maximal subgroup $M$ of $Q$. $M$ contains the Frattini subgroup $\Phi(Q)$, so this endomorphism fails to be surjective when it is converted to an endomorphism of the maximal elementary abelian quotient $Q/ \Phi(Q)$.
Gap 1: I do not immediately see how to prove that $|Q/ \Phi(Q)| = p^{r}$. It is clear that, since $Q$ is generated by an $r$-element set, $|Q/ \Phi(Q)| \leq p^{r}$. The nature of the relation set should imply that $Q$ is trivial if $|Q/ \Phi(Q)| < p^{r}$.
Assuming Gap 1 is fillable, when the words expressing $\phi(x_{1}), \ldots, \phi(x_{r})$ are written in terms of $x_{1}, \ldots, x_{r}$, one can form the matrix whose $(i,j)$ entry is the sum of the exponents, regarded as an element of $\mathbb{Z}/(p)$, to which $x_{i}$ appears in $\phi(x_{j})$.
Gap 2: I do not immediately see how to prove that element of $\mathbb{Z}/(p)$ is well-defined.
Assuming Gap 2 is also fillable, the matrix thus obtained will be invertible iff $\phi$ is surjective, and thus an automorphism of $Q$. Since all $r \times r$ matrices over $\mathbb{Z}/(p)$ arise this way from endomorphisms of $Q$ (assuming Gap 1 is filled), construction of this matrix yields a surjective homomorphism from $Aut(Q)$ to $GL(r,\mathbb{Z}/(p))$. What is the kernel of this homomorphism?
The kernel consists of all preimages of the identity matrix under that abelianization modulo $p$ map. If $|Q| = p^{E}$, assuming Gap 1 is filled, $|\Phi(Q)| = p^{E-r}$. Then any kernel element can be obtained by sending $x_{i}$ to $x_{i}f_{i}$ for all $i$, where $f_{i} \in \Phi(Q)$. This means that the order of the kernel is $p^{r(E-r)}$, and that $|Aut(Q)| = p^{r(E-r)} \Pi_{k=0}^{r-1} (p^{r}-p^{k})$.

Going back to this question for the quaternion group Q_{8}, $Aut(Q_{8}) \cong S_{4}$ so $Aut(Q_{8})$ has $GL(2, \mathbb{Z}/(2) ) \cong S_{3}$ as a quotient. The kernel of this quotient map consists of the automorphisms of $Q_{8}$ which send each element of $Q_{8} \setminus \Phi(Q_{8})$ to itself, except possibly for sign. Since { $\pm{1}$ } $ = \Phi(Q_{8})$, this sounds exactly like what was covered in the discussion of $Aut(Q)$ above.
Yet I still have trouble obtaining a presentation of the kind $Q$ satisfies for the quaternion group of order 8:

One may say that, in $Q_{8}$, all elements have order dividing 4: $e^{4} = 1$ for all words $e \in < x,y >$.
One may also say that, in $Q_{8}$, all elements square to an element of the center: $e_{1}^{2}e_{2} = e_{2}e_{1}^{2}$ for all words $e_{1}, e_{2} \in < x,y >$.

These two statements do not capture $Q_{8}$ completely, since the group with those relations turns out to have order $32$:

$T = < x,y| e^{4}=1, e_{1}^{2}e_{2} = e_{2}e_{1}^{2} >$ is nonabelian, since the nonabelian group $Q_{8}$ is one of its quotients.
Now consider the element $x^{2}y^{2}(xy)^{2} \in T$. This element is clearly a product of squares, so it is a product of central elements of order dividing 2. It therefore has order dividing 2 itself.
Yet $T/< x^{2}y^{2}(xy)^{2} >$ is abelian, since $x^{2}y^{2}(xy)^{2} = 1$ implies $x^{2}y^{2} = (xy)^{-2})$, which implies (since every element has order dividing 4) $x^{2}y^{2} = (xy)^{2} $, which implies (left-multiplying by $x^{-1}$ and right-multiplying by $y^{-1}$) $xy = yx$.
Therefore $x^{2}y^{2}(xy)^{2}$ is a nontrivial element of $T$, so it has order 2. $T/< x^{2}y^{2}(xy)^{2} >$ is, therefore, the largest 2-generated abelian group of exponent 4 (and being abelian subsumes the centrality of squares). So $T/< x^{2}y^{2}(xy)^{2} > \cong C_{4} \times C_{4}$ and it is now clear that $|T| = 32$.

The question indicated by the title asks whether more relations can be added, in this symmetric fashion, to $T$ to obtain $Q_{8}$. The natural extension of this question is whether or not there exists a 'nice' criterion for looking at an arbitrary $p$-group and determining whether or not it has a presentation of the kind discussed here. Clearly the discussion of $Aut(Q)$ gives some preliminary necessary conditions for the existence of such a presentation.

Answer by DavidLHarden for finite groups of SL(4,C)

2012-04-20T19:43:49Z

Any group of order 42 is isomorphic to $C_{42}$, $AGL(1,7) = C_{7} \rtimes C_{6}$, $D_{14} \times C_{3}$, $D_{6} \times C_{7}$, $D_{42}$ or $(C_{7} \rtimes C_{3}) \times C_{2}$. (Here $D_{2n}$ denotes the dihedral group of order $2n$.)
Any finite cyclic group can be embedded in $GL(3, \mathbb{C})$ as a group of scalar matrices, so those factors in the Cartesian products given can be taken care of. The largest dimension of an irreducible (complex) representation of a dihedral group is 2, and the largest dimension of an irreducible representation of $C_{7} \rtimes C_{3}$ is 3. These largest-dimensional representations are all faithful. So these groups are all subgroups of $GL(3, \mathbb{C})$, which is isomorphic to a subgroup of $SL(4, \mathbb{C})$.
This leaves only $C_{7} \rtimes C_{6}$. The irreducible representations of this group have dimensions 1, 1, 1, 1, 1, 1 and 6. Any combination of the 1-dimensional representations will be an abelian representation and thus not be faithful. The 6-dimensional representation can't be found in $SL(4, \mathbb{C})$, so any group of order 42 will be isomorphic to a subgroup of $SL(4, \mathbb{C})$ or isomorphic to $AGL(1,7) = C_{7} \rtimes C_{6}$.

Answer by DavidLHarden for Applications for p-Sylow subgroups theorem

2012-03-28T05:20:27Z

Even the cyclicity of the groups of order 15, or the existence of a normal Sylow 5-subgroup in any group of order 100, is not merely a toy example.
The fact that Sylow p-subgroups of a finite group are always conjugate is one way to prove that normal implies characteristic for a Sylow p-subgroup. (So if a group has simple subgroups of index 100 which generate it, and no normal subgroup of order 25, the group itself is simple. Hence, the Higman-Sims group is simple because the Mathieu group $M_{22}$ is simple. This is done in Wilson's "The Finite Simple Groups".) Two consequences of this are that if $P$ is a Sylow p-subgroup of a finite group $G$ and $K$ is a subgroup satisfying $N_{G}(P) \leq K \leq G$, then $[K:N_{G}(P)] \equiv [G:K] \equiv 1 \mod{p}$ and $K$ is self-normalizing in $G$. In particular, the maximal subgroups of $G$ containing $N_{G}(P)$ are constrained by these results.
The cyclicity of groups of order 15 is more than just a toy example, since the cyclicity of groups of order 299 = 13*23 (which is provable the same way) is used in Thompson's original proof of the simplicity of the Conway group $Co_{1}$. (This proof also gives an example of the use of the Frattini argument.)
If you want to prove the Burnside $p^{a}q^{b}$-Theorem, you need to exploit the existence of Sylow subgroups. This is one of the few commonalities of the character-theoretic and character-free proofs of the theorem. Via character theory, the basic group-theoretic result is that a finite group with a conjugacy class whose size is a power of a prime cannot be simple -- but you can only get a conjugacy class of size equal to a power of a prime in a group of order $p^{a}q^{b}$ by choosing a nontrivial central element of a Sylow subgroup (unless you made a bad choice and it's in the center of the whole group, in which case nonsimplicity of the group is immediate unless the group is cyclic of prime order).
Eschewing character theory, Sylow subgroups are indispensable, whether you use the Glauberman $ZJ$-theorem or any other local-analytic tools to do the heavy lifting in the proof. They are also essential even for much lighter lifting which happens in these proofs.
When using the transfer to prove a finite group satisfying certain conditions is not perfect, it's good to have a subgroup from which this fact is visible. It is good to have a subgroup $H$ such that one knows $\phi : G \to A$ is nontrivial because its restriction to $H$ is nontrivial. If p is a prime dividing $| \phi(G) |$, then any subgroup whose index is a nonmultiple of p will work. A Sylow p-subgroup of $G$ fits the bill perfectly, and often comes with a fair amount of information about its own structure, to boot.
It is possible to build off of the Burnside $p^{a}q^{b}$-Theorem to prove the that the existence of Sylow systems characterizes finite solvable groups. Sylow system normalizers are all conjugate in a finite solvable group, and these facts form the starting point of the theory of finite solvable groups (which is substantial in its own right, as one can read in "Finite Soluble Groups", by Doerk and Hawkes).

Doubly covering an even lattice

2012-03-14T21:00:56Z

I have read that there is a way to construct a group which is a double cover of an even lattice. The very tantalizing thing about this is that if the even lattice is chosen to be the Leech lattice, the resulting double cover is supposed to admit a natural action of the Monster group.

(i) What is a good place to read about how to construct this double cover?
(ii) What is a good place to read about how to define the Monstrous action on the double cover of the Leech lattice?

A solvability theorem

2011-02-08T05:17:07Z

There is a theorem which says:

Let $G$ be a finite group. Suppose that every maximal subgroup of $G$ has index equal to a prime or the square of a prime. Then $G$ is solvable.

Reading existing proofs and other results, I have cobbled together my own proof:

Proof. Suppose, to the contrary, that a counterexample exists. Let $G$ be a minimal counterexample. Since $G$ is nontrivial, let $p$ be the largest prime factor of $|G|$, and let $P$ be a Sylow $p$-subgroup of $G$.

If $P$ is normal in $G$, then the maximal subgroups of $G/P$ correspond to maximal subgroups of $G$ containing $P$. These have index equal to a prime or the square of a prime, so $G/P$ is a smaller group for which the condition holds and therefore $G/P$ is solvable. Then, since $P$ is also solvable, $G$ is solvable. Therefore we assume that $P$ is not normal in $G$.

Then the normalizer $N_{G}(P)$ is a proper subgroup of $G$. Then let $M$ be a maximal subgroup of $G$ containing $N_{G}(P)$. Then $[G:M] = \frac{[G:N_{G}(P)]}{[M:N_{G}(P)]} = \frac{[G:N_{G}(P)}{[M:N_{M}(P)]} \equiv \frac{1}{1} = 1 \mod{p}$.

Since $M$ is a proper subgroup of $G$, $[G:M] \geq p+1 > p$. Since $p$ is the largest prime factor of $|G|$, $[G:M]$ is not prime. Therefore there is a prime $q$ such that $q^{2} = [G:M]$. Since $q \neq p$ and $q | |G|$, $q < p$. Then $p \nmid q-1$ so $q^{2} \equiv 1 \mod{p}$ implies $q \equiv -1 \mod{p}$. Then, since $q < p$, we have $q = p-1$. Since $p$ and $q$ are both prime, we have $p=3$ and $q=2$.

Since $p=3$ and $p$ is the largest prime factor of $|G|$, $|G| = 2^{a}3^{b}$ for nonnegative integers $a,b$. This means all maximal subgroups of $G$ have index $2$, $3$, $4$, or $9$. The Frattini subgroup $\Phi(G)$ is nilpotent, so, since $G$ is a counterexample, $G/ \Phi(G)$ must be unsolvable. $\Phi(G)$ is the intersection of all maximal subgroups of $G$. Since the conjugate of a maximal subgroup is also a maximal subgroup, $\Phi(G)$ is the intersection of the cores of the maximal subgroups of $G$. If $N$ and $M$ are normal subgroups of $G$ with $G/N$ and $G/M$ solvable, then $G/(N \cap M)$ is also solvable. Therefore, since $G/ \Phi(G)$ is unsolvable, there is a maximal subgroup $K$ of $G$ such that $G/Core_{G}(K)$ is unsolvable. The quotient $G/Core_{G}(K)$ is the image, in the symmetric group $S_{[G:K]}$, of the action-on-cosets homomorphism based on the subgroup $K$. Therefore, if $G/Core_{G}(K)$ is unsolvable, the symmetric group $S_{[G:K]}$ must be unsolvable. This means that $[G:K] > 4$, so that $[G:K] = 9$.

Then $G/Core_{G}(K)$ is a transitive (in fact, primitive, since $K$ is maximal in $G$) unsolvable subgroup of the symmetric group $S_{9}$. Also, since $|G| = 2^{a}3^{b}$ for some nonnegative integers $a,b$, $|G/Core_{G}(K)| = 2^{\alpha}3^{\beta}$ for some nonnegative integers $\alpha , \beta$. From now on, we denote $G/Core_{G}(K)$ by $H$. The contradiction is obtained by showing no such subgroup of $S_{9}$ exists:

First of all, since $H$ is a subgroup of $S_{9}$, we have $\alpha \leq 7$ and $\beta \leq 4$ (from Lagrange's Theorem and the factorization of $9!$). If $\alpha = 7$, then $H$ is a primitive subgroup of $S_{9}$ containing a whole Sylow $2$-subgroup of $S_{9}$, and thus containing a transposition. Then $H = S_{9}$, contradicting $|H| = 2^{\alpha}3^{\beta}$. Therefore $\alpha \leq 6$. If $\beta = 4$, then $H$ is a primitive subgroup of $S_{9}$ containing a whole Sylow $3$-subgroup of $S_{9}$, and thus containing a $3$-cycle. Then $H$ contains $A_{9}$, for a similar contradiction. Therefore $\beta \leq 3$.

It suffices to prove this claim when $|H| = 864$. The number of Sylow $3$-subgroups of $H$ is $1$, $4$, or $16$. If this number is $1$ or $4$, then a Sylow $3$-subgroup normalizer is a solvable subgroup of $H$ having index at most $4$. Any group having a solvable subgroup of index at most $4$ is solvable, so $H$ is solvable. Therefore assume that the number of Sylow $3$-subgroups of $H$ is $16$.
$H$ acts transitively by conjugation on its Sylow $3$-subgroups. A Sylow $3$-subgroup $P$ fixes itself and acts without fixed points on the other Sylow 3-subgroups. Since $9 \nmid 16-1$, one of these suborbits must have exactly $3$ points in it. This gives us two Sylow $3$-subgroups $R, Q$ such that $[R: R \cap Q] = [Q: R \cap Q] = 3$. This means $R \cap Q$ is normalized by both $R$ and $Q$, so that $N_{H}(R \cap Q)$ has more than one Sylow $3$-subgroup of $H$. How many Sylow $3$-subgroups does it have? $4$ or $16$.
If $N_{H}(R \cap Q)$ has $16$ Sylow $3$-subgroups, then $|N_{H}(R \cap Q)|$ is a multiple of $16$ and $27$, so it is a multiple of $432$ and it is $432$ (in which case $N_{H}(R \cap Q)$ is normal in $H$ because its index is $2$) or $864$ (in which case $R \cap Q$ is normal in $H$, $R \cap Q$ is solvable because it is a $3$-group, and $H/(R \cap Q)$ is solvable because a Sylow $2$-subgroup of it is a solvable subgroup of index $3$, and a group with a solvable subgroup of index at most $4$ is solvable). If $N_{H}(R \cap Q)$ has $4$ Sylow $3$-subgroups, then its order is a multiple of $27$ and $4$, so its order is a multiple of $108$. Then $[H : N_{H}(R \cap Q)] | 8$, and the solvability of $H$ follows (since a group with a solvable subgroup of index at most $4$ is solvable), except possibly when $N_{H}(R \cap Q)$ is a maximal subgroup of $H$. If $N_{H}(R \cap Q)$ is maximal in $H$, let $H$ act on its cosets and let $L$ be the kernel of this homomorphism from $H$ to the symmetric group $S_{8}$. Since $27 | |H|$ but $27$ does not divide $8!$, $3 | |L|$. If $9 | |L|$, then $L$ is solvable because $L$ is a $3$-group and $H/L$ is solvable because a Sylow $2$-subgroup of $H/L$ is a solvable subgroup of index $1$ or $3$. If $3$ exactly divides $|L|$, then $H/L$ is a primitive subgroup of $S_{8}$ whose order is a multiple of $9$. Then $H/L$ contains a whole Sylow $3$-subgroup of $S_{8}$ and thus $H/L$ contains a $3$-cycle. Then, since $H/L$ is primitive on $8$ points, $H/L$ contains $A_{8}$, contradicting $|H| = 864$.

Now it only remains to handle the cases when $\alpha = 6$, or, equivalently, when $|H| = 576$ or $1728$. If $|H| = 576$, then $H$ is solvable:

The number of Sylow $3$-subgroups of $H$ is $1$, $4$, $16$, or $64$. If the number is $1$ or $4$, then $H$ has a Sylow $3$-subgroup normalizer (itself obviously solvable) which has index $1$ or $4$ in $H$. Therefore $H$ is solvable. If $H$ has $64$ Sylow $3$-subgroups, each is self-normalizing. Since they are abelian (for they have order $9$), the Burnside $p$-complement Theorem applies to show that $H$ has a normal Sylow $2$-subgroup and so is solvable. Therefore assume that $H$ has exactly $16$ Sylow $3$-subgroups. As before, we may obtain two Sylow $3$-subgroups $Q, R$ such that $[Q: Q \cap R] = [R: Q \cap R] = 3$. Then let $x$ be chosen so that $ < x > = Q \cap R$. Then the centralizer $C_{H}(x)$ contains two Sylow $3$-subgroups of $H$, so it contains at least $4$ Sylow $3$-subgroups of $H$. In fact, the number of Sylow $3$-subgroups of $H$ it contains is $4$ or $16$. If it is $16$, then $C_{H}(x)$ is a subgroup of index $4$ in $H$. $C_{H}(x)$ is solvable because $C_{H}(x)/ < x >$ has a Sylow $2$-subgroup of index $3$, so $H$ is solvable. So assume that the number of Sylow $3$-subgroups of $H$ in $C_{H}(x)$ is $4$. In this case, $C_{H}(x)/ < x >$ is a group of order $12$ which has $4$ Sylow $3$-subgroups, so $C_{H}(x)/ < x > \cong A_{4}$. Then the subgroup $V$ of order $4$ in $A_{4}$ lifts to a subgroup $N$ of order $12$ in $C_{H}(x)$. Since $V$ is normal in $A_{4}$, $N$ is normal in $C_{H}(x)$. Moreover, since $N$ centralizes $x$, $N$ is abelian. Therefore $N$ has a characteristic subgroup $W$ of order $4$ which is normal in $C_{H}(x)$. But also $W$ is contained in a Sylow $2$-subgroup $P$ of $H$, and $N_{P}(W) > W$. Therefore $N_{H}(W)$ contains $C_{H}(x)$ which has order $36$, and $N_{P}(W)$, whose order is a multiple of $8$. Therefore $|N_{H}(W)|$ is a multiple of $72$, so it is $72$, $144$, $288$, or $576$. $N_{H}(W)/W$ has order dividing $144$, so it is solvable. Therefore $N_{H}(W)$ is solvable. If $|N_{H}(W)|$ is $144$, $288$, or $576$, then $H$ has a solvable subgroup of index at most $4$ and is therefore solvable. Therefore, assume $|N_{H}(W)| = 72$. Since the solvability of $H$ follows if $N_{H}(W)$ is not maximal in $H$, assume $N_{H}(W)$ is maximal in $H$. Then let $H$ act on the cosets of $N_{H}(W)$, and let $L$ be the kernel of the homomorphism obtained from $H$ to $S_{8}$. If $|L|$ is a nonmultiple of $3$, $H/L$ contains a whole Sylow $3$-subgroup of $S_{8}$ and so contains a $3$-cycle. Then $H/L$ is primitive on $8$ points and contains a $3$-cycle, so $H/L$ contains $A_{8}$, contradicting $|H| = 576$. So assume that $|L|$ is a multiple of $3$. Then $H/L$ is a transitive subgroup of $S_{8}$, so $8 | |H/L|$. This means that $|L| | 72$, so $|L| | 864$ and $L$ is solvable. Then, since $3 | |L|$, $H/L$ has a Sylow $2$-subgroup of index at most $3$ and so is solvable. Therefore $H$ is solvable, as claimed.

We now come to the final case, in which it will be shown that $S_{9}$ has no primitive subgroup $H$ with $|H| = 1728$: If $H$ has a subgroup of index $2$, then it is solvable and therefore $H$ is solvable. Therefore we assume that $H$ has no subgroup of index $2$, so that $H < S_{9}$ implies $H < A_{9}$. Since $H$ is a transitive group on $9$ points, a point stabilizer in $H$ has order $192$. Since all of the subgroups of order $192$ in $A_{8}$ are conjugate, in $S_{8}$, to the stabilizer, in $A_{8}$, of the partition $12|34|56|78$ of the $8$ indices, we conclude that $H$ is doubly transitive on $9$ points and that any $2$-point stabilizer has a third fixed point. How many sets of $3$ points arise as the fixed point sets of $2$-point stabilizers in $H$? This number is $\frac{\binom{9}{2}}{\binom{3}{2}} = 12$. Since $H$ is doubly transitive, all the $2$-point stabilizers in $H$ are conjugate in $H$. Therefore $H$ also acts transitively on the $12$ sets of $3$ that arise as fixed point sets of $2$-point stabilizers. This means that the stabilizer $M$, in $H$, of one of these sets of $3$ has order $144$. How does $M$ act on the other $6$ points? It can't act faithfully, since $S_{6}$ has no subgroup of order $144$ (for $S_{n}$ has no subgroup of index strictly between $2$ and $n$, except when $n = 4$). Then a nontrivial element of $M$ fixing the $6$ points can only be a $3$-cycle or a transposition, so that $H$ is a primitive permutation group containing a transposition or a 3-cycle and thus $H$ contains $A_{9}$, contradicting $|H| = 1728$.

My question is: what is the easiest way to prove this solvability theorem? (The Burnside $p^{a}q^{b}$ Theorem is too magical via character theory, and too hard without it, for my taste.)

Jordan's Theorem on primitive permutation groups

2012-01-09T03:08:00Z

The theorem I am referring to in the title is this:

Theorem. If $p$ is a prime and $n$ is an integer with $n \geq p+3$, then the only primitive permutation groups on $n$ points containing a $p$-cycle are $A_{n}$ and $S_{n}$.

Without using the Classification of Finite Simple Groups, it seems hopeless to extend this to a statement detailing when it's possible to have a $p$-cycle in a primitive permutation group on $p+1$ points, since the Mathieu groups $M_{11}$, $M_{12}$ and $M_{24}$ arise this way when $p = 11$ or $23$.

The intermediate case is when $n=p+2$, and here there is a readily available family of examples: If $p = 2^{q}-1$ is a Mersenne prime, then the group $SL(2,2^{q})$ is primitive on the $2^{q}+1$ points of the projective line over $\mathbb{F_{2^{q}}}$. It contains $(2^{q}-1)$-cycles as the only elements fixing exactly 2 points. These groups can also be enlarged by adjoining field automorphisms, though the primality of $q$ means that the only larger group obtainable this way is the whole $\Sigma L(2,2^{q}) = SL(2,2^{q}):q$.

I have read that Burnside was able to prove that the only finite simple groups of even order in which every element has order 2 or odd order are $SL(2,2^{m})$ for some $m \geq 2$. My question is: Are methods not much stronger than the methods Burnside used to prove that result usable to prove no groups aside from those already mentioned act primitively on $p+2$ points and contain $p$-cycles?

The number of conjugacy classes and the order of the group

2011-10-08T04:43:52Z

In my response to the OP in http://mathoverflow.net/questions/64653 (I continue notation from my response in that thread), I indicated the possibility that lifting elements from $GL_{2}(\mathbb{Z}/(p))$ to $Aut(B(2,p))$ could extend the ability of character-free methods in proving congruences relating the order of a group and its number of conjugacy classes. I can now report a small bit of concrete progress in this direction. Specifically, what I can prove is:

Theorem. If $G$ is a finite group of exponent 3, then $|G| \equiv c(G) \mod{16}$.

Proof. We regard the Burnside group $B(2,3) = < x,y|(*)^{3}=1 >$ (here $ * $ ranges over every word in the generators) as $< x,y>$ and specify elements of $Aut(B(2,3))$ by their action on $x$ and $y$. Specifically, consider the following elements of $Aut(B(2,3))$:

$\alpha: (x,y) \to (xy,x^{-1}y)$
$\beta: (x,y) \to (x,y^{-1})$

By checking that $\beta^{2} = 1$ and $\beta\alpha\beta = \alpha^{3}$, we see that $<\alpha,\beta>$ is a quotient of the semidihedral group of order $16$. By checking that $\alpha^{4}$ sends $(x,y)$ to $(x^{-1},xy^{-1}x^{-1})$ so that $\alpha^{4} \neq 1$, we see that $<\alpha,\beta>$ is semidihedral of order $16$.

Now let $<\alpha,\beta>$ act on non-commuting pairs of elements of our group $G$ of exponent 3. We wish to show that every non-identity element of $<\alpha,\beta>$ has no fixed points in its action on the set of non-commuting pairs of elements of $G$. Every non-identity element of $<\alpha,\beta>$ has a power equal to $\alpha^{4}$ or is conjugate to $\beta$, so it suffices to check this property for just $\alpha^{4}$ and $\beta$.

If $(x,y)$ is a fixed point of $\alpha$, then $x = x^{-1}$ so $x^{2} = 1$ and, since $x^{3} = 1$, $x = 1$ and $(x,y)$ is not a non-commuting pair.
If $(x,y)$ is a fixed point of $\beta$, then $y = y^{-1}$ so $y^{2} = 1$ and, since $y^{3} = 1$, $y = 1$ and $(x,y)$ is not a non-commuting pair.

Therefore every orbit for the action of $<\alpha,\beta>$ on the set of non-commuting pairs of elements of $G$ has exactly 16 elements and we conclude that 16 divides $|G|(|G| - c(G))$ . Since $|G|$ is odd, we conclude that $|G| \equiv c(G) \mod{16}$.

I do not know how to give a character-free proof of this congruence (either for general $p$-groups or just those of exponent $p$) for any prime $p$ with $p \equiv 3 \mod{4}$ and $p > 3$. Complicating hopes of extending this is the fact that $B(2,n)$ is not known to be finite for any larger odd value of $n$.

(i) I'm probably just not thinking clearly enough right now, but how does one use this to prove the congruence when $G$ is an arbitrary 3-group?
(ii) Is it hopeless to expect to extend this to larger primes congruent to 3 mod 4?

Answer by DavidLHarden for Generating a finite group from elements in each conjugacy class

2011-11-30T08:04:11Z

A superficially different counting argument, which boils down to the same proof as before:

If $H$ is a proper subgroup whose conjugates completely cover $G$, then let $G$ act on the right cosets of $H$ by right multiplication. This action is transitive. Since $H$ is a point stabilizer, the conjugates of $H$ are just all the point stabilizers. Then saying that the conjugates of $H$ cover $G$ is saying that every element of this permutation group has a fixed point. In a transitive permutation group, the average number of fixed points is $1$. The number of fixed points of the identity is the number of points, $[G:H]$. The only way every permutation can have at least the average number of fixed points is for every permutation to have exactly the average number of fixed points, so $[G:H]=1$ contradicting the assumption that $H$ is proper.

Parker-like loop of order 2187?

2011-03-20T20:04:08Z

The Parker loop has order $2^{13}$, and reducing it modulo its 'center' yields -- not just a $12$-dimensional $\mathbb{Z} /(2)$-vector space, but one which can be naturally identified with the subspace of $(\mathbb{Z} /(2))^{24}$ which is the extended $24$-bit Golay code.

Analogous to the extended $24$-bit Golay code is the $12$-coordinate extended ternary Golay code, which is a $6$-dimensional subspace of $(\mathbb{Z} /(3))^{12}$. Is there likewise a known analogue of the Parker loop which has order $3^{7}$ and which may be likewise identified with the extended ternary Golay code once it quotiented by its center? (And, if no such thing is known, is it because it has been proven not to exist?)

Answer by DavidLHarden for Being a subgroup: proof by character theory

2011-11-05T21:27:47Z

There is another example of sorts, but it's not a good example since it appeals to a result known only as a consequence of the Classification of Finite Simple Groups (whose proof involves A LOT of character theory, instead of one more new technique, or one more variation on an old basic character-theoretic technique). It does, however, strictly generalize that theorem of Frobenius (by letting $n$ be the order of the Frobenius kernel):

Let $G$ be a finite group, and suppose $n$ is a positive integer dividing $|G|$. If the number of solutions in $G$ to $x^{n} = 1$ is exactly $n$, these solutions form a subgroup of $G$.

For the proof, see

Nobuo Iiyori and Hiroyoshi Yamaki, On a conjecture of Frobenius, Bulletin of the American Mathematical Society (New Series) 25 (1991), no. 2, 413-416 .

As with the theorem of Frobenius which this result generalizes, it is easy to prove this subset of $G$ contains the identity and is closed under taking inverses. So the only difficulty is in proving closure under composition...

Answer by DavidLHarden for The number of conjugacy classes and the order of the group

2011-10-26T07:40:20Z

It is not hopeless to extend this argument so that it applies to all finite groups of odd prime power order. Let $p$ be an odd prime, and let $K$ be a $p$-group. The congruence $|K| \equiv c(K) \mod{16}$ can be proven as a consequence of the stronger (when $p > 3$) congruence $|K| \equiv c(K) \mod{(p^{2}-1)(p-1)}$. This congruence is the best possible in the sense that there are $p$-groups (nonabelian groups of order $p^{3}$) for which $|K| - c(K) = (p^{2}-1)(p-1)$.

Let the exponent of $K$ be $p^{k}$, and let $L$ be the nilpotence class of $K$. It is difficult to work with $B(2,p^{k})$ or $Aut(B(2,p^{k}))$ when $p^{k} > 3 $ and neither of those groups is known to be finite, or, worse, when $p^{k} \geq 673$ and they are known to be infinite.
Instead, we build from $K$ the group

$P = < x,y| w^{p^{k}}=1, [w_{1}, \ldots , w_{L+1}]=1 >$,
where $w, w_{1}, \ldots , w_{L+1}$ range independently over every possible word in the generators.

Claim. $P$ is finite.
Proof of Claim. We regard $k$ as fixed and proceed by induction on $L$. When $L = 1$, $P$ is abelian and generated by two elements of order dividing $p^{k}$ so $|P| \leq p^{2k}$ and the base case is proved.
If $L > 1$, it suffices to prove that the group $P_{L}$ in the descending central series of $P$ is finitely generated, since it is abelian and all its elements have finite order dividing $p^{k}$. Then every $(L-1)$-fold commutator $[w_{1}, \ldots , w_{L}]$ is central so $P/P_{L}$ is a quotient of the group which has the same definition as $P$, except for the replacement of $L$ by $L-1$. Since that group is finite by induction, $P/P_{L}$ is finite and the finiteness of $P_{L}$ implies the finiteness of $P$. To prove this, we use the

Commutator Lemma. If $G = < g_{1}, \ldots , g_{m} >$ and $H = < h_{1}, \ldots , h_{r} > \leq G$ for some positive integers $m$ and $r$, then the commutator subgroup $[G,H]$ has a generating set consisting of iterated commutators $[e_{1}, \ldots , e_{C}]$, where each $e_{i} \in $ {$g_{1}^{\pm 1}, \ldots , g_{m}^{\pm 1}, h_{1}^{\pm 1}, \ldots , h_{r}^{\pm 1}$}.

Proof of Commutator Lemma.
Recall the commutator identities $[t, uv] = [t,v][t,u][t,u,v]$ and $[tu, v] = [t,v][t,v,u][u,v]$.
An arbitrary element of $[G,H]$ is a product of commutators of the form $[g,h]$, where $g = \gamma_{1} \ldots \gamma_{s_{1}}$, $h = \eta_{1} \ldots \eta_{s_{2}}$, each $\gamma_{i} \in$ {$g_{1}^{\pm 1}, \ldots , g_{m}^{\pm 1}$} and each $\eta_{i} \in$ {$h_{1}^{\pm 1}, \ldots , h_{r}^{\pm 1}$}. We prove it for commutators of this form by reducing the length of $h$ and then reducing the length of $g$ as follows:

If $s_{2} > 1$,

$[g, \eta_{1} \ldots \eta_{s_{2}}] = [g, \eta_{2} \ldots \eta_{s_{2}}][g, \eta_{1}][g, \eta_{1}, \eta_{2} \ldots \eta_{s_{2}}]$.

If $s_{2} = 1$ and $s_{1} > 1$,

$[\gamma_{1} \ldots \gamma_{s_{1}}, \eta_{1}] = [\gamma_{1}, \eta_{1}][\gamma_{1}, \eta_{1}, \gamma_{2} \ldots \gamma_{s_{1}}][\gamma_{2} \ldots \gamma_{s_{1}}, \eta_{1}]$.
The middle factor on the right hand side can be written as a product of commutators of the desired form by repeatedly applying the equation cited for handling the $s_{2} > 1$ case. Then the final factor has the length of $g$ reduced by 1, as desired. The Commutator Lemma is now proven.

Then $[P,P]$ is generated by a set of such iterated commutators involving $x$, $y$, $x^{-1}$ and $y^{-1}$. Since these have at most $L$ arguments, this gives a generating set of at most $\frac{4^{L+1} - 16}{3}$ elements for $[G,G]$. Then, if one has a $\rho$-element generating set for the subgroup $P_{i}$ in the descending central series of $G$, the Commutator Lemma gives a generating set for $P_{i+1}$ consisting of at most $\frac{(2\rho + 2)^{L+1} - (2\rho + 2)^{2}}{2\rho + 1}$ elements (these finite geometric series arise from summing over the possible lengths of such commutators). Then, continuing in this way, all of the subgroups in the descending central series for $P$ are finitely generated, and the finiteness of $P$ is proven.

Here $\Phi$ denotes the Frattini subgroup.
Denote $|P|$ by $p^{E}$. Let $W_{1}(x,y)$ and $W_{2}(x,y)$ be elements of $P$, considered as words in $x$ and $y$ (well-defined up to the relations). Any substitution $(x,y) \to (W_{1}(x,y),W_{2}(x,y))$ turns relations into other relations (due to the way the relations defining $P$ involve all possible words), so any such substitution defines an endomorphism of $P$. Such a substitution defines an automorphism of $P$ if and only if it is invertible. Since $P$ is finite, an endomorphism from $P$ to itself is invertible if and only if it is surjective. If an endomorphism $\psi$ of $P$ is not surjective, then $\psi(P)$ is contained in some maximal subgroup of $P$ and $\psi(P)\Phi(P)/\Phi(P)$ is a subspace of $P/\Phi(P)$ of positive $\mathbb{Z}/(p)$-codimension. So the endomorphism $\psi$ of $P$ is an automorphism if and only if its action on $P/\Phi(P)$ is via an element of $GL(2,\mathbb{Z}/(p))$. This means that the proportion of endomorphisms of $P$ which are automorphisms is the proportion of 2x2 matrices over $\mathbb{Z}/(p)$ which are invertible. Therefore, we obtain the result that $|Aut(P)| = p^{2E-3}(p^{2}-1)(p-1)$.
Now we let $Aut(P)$ act on the set of non-commuting pairs of elements of $K$. This is well-defined since the relations that hold in $P$ also hold in $K$, and in the subgroup of $K$ generated by two non-commuting elements. To get information about the size of an orbit of a non-commuting pair under this action, it suffices to get information about the order of the stabilizer in $Aut(P)$.
If $a,b \in K$ form a non-commuting pair such that $a = W_{1}(a,b)$ and $b = W_{2}(a,b)$, then $1 = a^{-1}W_{1}(a,b) = b^{-1}W_{2}(a,b)$. $| < a,b > /\Phi(< a,b >)| = p^{2}$, since $< a,b >$ is noncyclic ($< a,b >$ is nonabelian since $(a,b)$ is a non-commuting pair) and generated by 2 elements. This means that, passing to $< a,b >/\Phi(< a,b >)$, we see that $(a,b) \to (W_{1}(a,b),W_{2}(a,b))$ is mapped to the identity matrix in $GL(2,\mathbb{Z}/(p))$. Then likewise, in $Aut(P)$, $(x,y) \to (W_{1}(x,y),W_{2}(x,y))$ must be in the subgroup of order $p^{2E-4}$ which is the kernel of the homomorphism from $Aut(P)$ to $GL(2,\mathbb{Z}/(p))$. Therefore any orbit for the action of $Aut(P)$ on the set of non-commuting pairs of elements of $K$ has size equal to a multiple of $(p^{2}-1)(p^{2}-p)$, and therefore $(p^{2}-1)(p^{2}-p)$ divides $|K|(|K| - c(K))$. Since $|K|$ is a power of $p$, we obtain the congruence $|K| \equiv c(K) \mod{(p^{2}-1)(p-1)}$ as claimed.

A 'generalized Four Squares Theorem'?

2011-08-21T07:28:09Z

The $4$-dimensional lattice $\mathbb{Z}^{4}$ has vectors of length $\sqrt{n}$ for any positive integer $n$ by the Four Squares Theorem, but this need not be true for higher-dimensional integral, unimodular lattices for two reasons:

(i) Some small positive integers could be skipped as squared lengths of lattice vectors. For example, the odd Leech lattice has no $v$ with $v \cdot v = 1$ or $2$.
(ii) The lattice may be even.

Therefore, the way to word the question to recognize these possibilities is:

Let $\Lambda$ be an integral unimodular lattice of dimension $d$, where $d \geq 4$.
(i) If $\Lambda$ is odd, then is it true that every sufficiently large positive integer arises as the squared length of a vector in $\Lambda$?
(ii) If $\Lambda$ is even, then is it true that every sufficiently large even positive integer arises as the squared length of a vector in $\Lambda$?

Answer by DavidLHarden for Automorphism Group of Paley Graph

2011-07-25T17:08:54Z

It is a natural first guess to think that if $F$ is a finite field and $S$ is a subgroup of the multiplicative group $F^{\times}$ containing $-1$ which generates $F$ additively, then the automorphism group of the Cayley graph (of the additive group $F^{+}$, using $S$ as the generating set) is the semidirect product of the additive group $F^{+}$ and the multiplicative group $S$. But that group needs, in turn, to have its semidirect product taken with the group of automorphisms of $F$ (as an extension of its prime subfield). But even this modified conjecture should have (verification, please?) at least two counterexamples:

(i) $|F| = 2048$ and $|S| = 23$, in which case the automorphism group should be $2^{11}: M_{23}$
(ii) $|F| = 243$ and $|S| = 22$, in which case the automorphism group should be $3^{5}: (M_{11}\times 2)$.

But since these apparent counterexamples involve sporadic groups, this version of the conjecture is probably largely on the right track. (This should not come into play in the Paley graph question, but it should serve as a warning that sometimes the problem of determining the automorphism group for such a family of graphs can exhibit unexpected irregularities.)

Is there a Mathieu groupoid M_31?

2011-07-18T21:48:41Z

I have read something which said that the large amount of common structure between the simple groups $SL(3,3)$ and $M_{11}$ indicated to Conway the possibility that the Mathieu groupoid $M_{13}$ might exist.
Indeed, it exists, and the group of permutations of the other points generated by paths in which the hole starts and ends at the same point is the Mathieu group $M_{12}$.

It is natural to ask whether or not something analogous exists for the Mathieu group $M_{24}$. The corresponding linear group seems to be $GL(5,2)$.
$2^{4}:A_{8}$ is a vector (or hyperplane) stabilizer in $GL(5,2)$ and an octad stabilizer in $M_{24}$. $2^{6}:(GL(2,2)\times GL(3,2))$ is likewise the stabilizer of a 2-dimensional (or 3-dimensional) space in $GL(5,2)$, and the stabilizer of a 'trio' (to use the term from SPLaG) in $M_{24}$.

The natural setting, therefore, in which to look for something analogous to $M_{13}$ is $(\mathbb{Z}/(2))^{5} \backslash 0$. (This can also be regarded as $4$-dimensional projective space over $\mathbb{Z}/(2)$, but I will here think of it as $5$-dimensional space over $\mathbb{Z}/(2)$ with the origin removed.)
Then, to have $24$ points left over when the 'holes' are put in place, it would be natural to have a 'missing $3$-dimensional space' for a hole.
A move should consist of moving the $3$-dimensional 'hole' to some other $3$-dimensional subspace (minus the origin) of $(\mathbb{Z}/(2))^{5}$. The intersection of these spaces can have dimension $1$ or $2$, and there should be different rules for moving the hole to another location depending on the dimension of its intersection with the new location.

Who has tried this before? Are there any papers on it?

Answer by DavidLHarden for Are there any solutions to $2^n-3^m=1$

2011-07-01T22:34:44Z

There is another method that allows one to handle $a^{n}-b^{m}=k$ (here I call the bases $a$ and $b$ because primality is not important to how the method works). Specifically, if one has a solution, it allows a larger solution to be found, or proven to not exist.

As an example of this method, it is easy to outline a proof that $2^{n} - 5^{m} = 3$ has no solutions larger than $(m,n)=(3,7)$:

Suppose $m>3$, $n>7$, and $2^{n}-5^{m}=3$.
Rewrite the equation as $2^{n}=5^{m}+3$.
Now, to use the largest solution we know, subtract $2^{7}=5^{3}+3$ from both sides to obtain $2^{7}(2^{n-7}-1)=5^{3}(5^{m-3}-1)$.
Since $m$ and $n$ give a solution larger than the one we know, both sides are positive integers. Since $n>7$, the highest power of $2$ dividing the right side is $2^{7}$.

Since the order of $5$ in $(\mathbb{Z}/(128))^{\times}$ is $32$, we know that $32$ divides $m-3$, and $5^{32}-1$ divides both sides. Then $29423041$, as a prime factor of $5^{32}-1$, divides both sides. Then $29423041$ divides $2^{n-7}-1$, so since the order of $2$ in $(\mathbb{Z}/(29423041))^{\times}$ is $122596$, $2^{122596}-1$ divides both sides. (This is probably not a profitable direction to take, but it can work as an illustration of the method.)

The contradiction would be obtained by concluding that $5^{4}$ divides the right side, or $2^{8}$ divides the left side.
In the case where a larger solution exists, the ability to bounce back and forth between the two sides of the equation only goes as far as concluding that the larger solution (that is, the common value of both sides when the larger solution is plugged in) minus the common value from the known solution divides both sides.

Larger cycle than 4, 2, 1 in Collatz iteration?

2011-06-24T17:02:55Z

(Here I discuss the Collatz problem only for positive integers.)
It is possible, by computation, to find all cycles in the Collatz iteration of a fixed length.
It is clear that an increase must be followed by a decrease (for if $n$ is odd, then $3n+1$ is even) and a decrease can be followed by either an increase or decrease (for if $n$ is even, $\frac{n}{2}$ may be odd or even).
Using this, it is easy, for example, to show $4, 2, 1$ is the only cycle of length $3$:
Over the course of a cycle, we must have both increases and decreases. Position an increase at the beginning of the cycle. Then the changes of the cycle must be $IDD$ (where $I$ stands for increase and $D$ stands for decrease), for there is no other way to include an increase and avoid two consecutive increases. Then the cycle consists of $a, 3a+1, \frac{3a+1}{2}$, so that $a = \frac{3a+1}{4}$ and $a = 1$, leading to the familiar $1, 4, 2 = 4, 2, 1$ cycle.

For length $4$, there are two possibilities for a pattern of increase and decrease along a cycle which start with an increase: $IDID$ and $IDDD$.
The $IDID$ possibility leads to $a = \frac{9a+5}{4}$ so $a = -1$.
The $IDDD$ possibility leads to $a = \frac{3a+1}{8}$ so $a = \frac{1}{5}$. Neither of these values of $a$ is a positive integer, so there are no cycles of length $4$.

Likewise, for length $5$, there are only $3$ possibilities: $IDDDD$, $IDIDD$, and $IDDID$. Since last two are equivalent, this leads to $IDDDD$ and $IDIDD$.
$IDDDD$ leads to $a = \frac{3a+1}{16}$ so $a = \frac{1}{13}$.
$IDIDD$ leads to $a = \frac{9a+5}{8}$ so $a = -5$. So there are no cycles of length $5$.

There is more to be said for this way of considering cycles in the Collatz iteration. If a sequence of increases and decreases leads to the equation $a = Ta + U$, then $T$ is positive and $T \neq 1$, since $T = \frac{3^{m}}{2^{n}}$ for some positive integers $m, n$. The positivity of $T$ and the fact that $T \neq 1$ ensure that the solution of $a = Ta + U$ also solves (and therefore is the only solution to) $a = T(Ta + U) + U$ (or the equation for fixed points of higher-multiplicity iterates of the function $f(a) = Ta + U$), so that only cycles that form primitive circular words need to be considered (and $IDID$ was unnecessary, given how it reduces to $ID$). With this noted, it becomes very easy to handle cycles of length $6$:

The number of increases in a cycle is $1$, $2$, or $3$, since no two of them can be consecutive (and since there must be at least one increase). $3$ increases in a cycle can only be realized by $IDIDID$, which is not a primitive circular word. $2$ increases in a cycle can be realized by $IDIDDD$, $IDDIDD$, or $IDDDID$. $IDIDDD$ and $IDDDID$ are equivalent, while $IDDIDD$ is not a primitive circular word. So the only cases to consider are $IDDDDD$ and $IDIDDD$.
$IDDDDD$ leads to $a = \frac{3a+1}{32}$ so $a = \frac{1}{29}$.
$IDIDDD$ leads to $a = \frac{9a+5}{16}$ so $a = \frac{5}{7}$.
So there are no cycles of length $6$.

This is natural and simple enough that someone must have considered it before. Who has, and in what paper(s)? Also, has this been used to settle the question of whether or not there is a cycle in the positive integers larger (both in length, and in member-wise comparison) than the $4, 2, 1$ cycle?

Orders of automorphism groups of p-groups

2011-06-17T23:15:30Z

There is a theorem that says that if $p$ is a prime and $G$ is a $p$-group with $|G| = p^{n}$, $|Aut(G)|$ divides $\Pi_{k=0}^{n-1} (p^{n}-p^{k})$.
This theorem is sharp, since $\Pi_{k=0}^{n-1} (p^{n}-p^{k}) = |GL(n,p)| = |Aut(E)|$, where $E$ is an elementary abelian group of order $p^{n}$.
The proof I know is by proving the $p$-part and the $p^{'}$-part of the divisibility separately.
The $p^{'}$-part of the divisibility boils down to the integrality of the binomial coefficient analogues which count decompositions of a vector space over $\mathbb{Z}/(p)$ into two subspaces whose sum is the space and whose intersection is $0$.
The $p$-part of the divisibility is the divisibility statement for the order of a Sylow $p$-subgroup of $Aut(G)$, and it uses induction and the fact that a $p$-group will have fixed points whenever it acts on a set whose cardinality is a nonmultiple of $p$.
Is there a book that covers this theorem? If so, how far (and where) does the book run with it?

Answer by DavidLHarden for Collatz related question

2011-06-12T22:30:14Z

The existence of such a function is equivalent to the unproven statement that all n eventually settle into the $4, 2, 1$ cycle. Or do I misunderstand your question?

Schur multipliers for Lie groups?

2011-05-24T21:38:30Z

In the interest of pursuing the analogies between finite groups and (finite-dimensional) Lie groups, it seems natural to call the Schur multiplier of a finite group analogous to the fundamental group of a Lie group. Just as the Schur multiplier limits what groups can arise as central subgroups of a group $G$ with fixed (isomorphism type of) $Inn(G)$, does the fundamental group do the same thing for Lie groups?

One baby example of this question: If $G$ is a Lie group with a central subgroup $Z$ with $|Z|=4$ and $G/Z \cong SO(3)$, does it follow that $G$ has a subgroup of index $2$?
Also, in the above situation, if $G$ has no subgroup isomorphic to $SO(3)$ and $Z$ is cyclic, does it follow that $G \cong H $, where $H$ is the subgroup of $U(2)$ obtained by adjoining $i$ times the identity matrix to $SU(2)$?

Answer by DavidLHarden for Embedding $S_3$ into $Aut(F_2)$

2011-05-16T22:00:06Z

I have wondered about such lifts myself, and I want to give what I hope is a tantalizing hint of what such lifts may be able to tell us:

The lift you give of $S_{3}$ from $GL_{2}( \mathbb{Z} )$ to $Aut(F_{2})$ also gives an embedding of $C_{3} = A_{3}$ into $Aut(F_{2})$. Why is this useful? It gives a character-free proof of a congruence about conjugacy classes of a finite group (here $c(G)$ denotes the number of conjugacy classes of the group $G$):

Theorem. If $G$ is a finite group with $|G|$ not divisible by $3$, then $|G| \equiv c(G) \mod{3}$.

Proof, with character theory: $|G|$ is the sum of the squares of the dimensions of the complex irreducible representations of $G$. The number of these is $c(G)$. Since $|G|$ is not a multiple of $3$, these dimensions aren't multiples of $3$. Now reduce modulo $3$ and obtain the congruence.

Proof, without character theory: $|G|(|G| - c(G))$ is the number of non-commuting ordered pairs of elements of $G$. Since $|G|$ is a nonmultiple of $3$, the congruence may be proved by showing that this set has a number of elements which is a multiple of $3$. Now just let the lift of $\tau$ act on it: If $(x,y)$ is a fixed point, then reading the first coordinate gives $x=y$, which trivially implies $xy=yx$. So the action is fixed-point-free, and we are done.

Theorem. If $G$ is a finite group of odd order, then $|G| \equiv c(G) \mod{8}$.

Proof, with character theory: $|G|$ is the sum of the squares of the dimensions of the complex irreducible representations of $G$. The number of these is $c(G)$. Since $|G|$ is odd, these dimensions are odd. Now reduce modulo $8$ and obtain the congruence.

Proof, without character theory: Instead of lifting $S_{3}$ to $Aut(F_{2})$, lift the dihedral group of order $8$, which is generated by the involutions $(x,y) \to (x^{-1},y)$ and $(x,y) \to (y,x)$. It suffices to check that none of the $5$ involutions of this group has a fixed point in the action on the non-commuting pairs of elements of $G$. This is easy to do, and it involves recalling that, since $|G|$ is odd, $t^{2}=1$ implies $t=1$ for $t \in G$.

This is all well and good, but, it is not the end of the story:

Theorem. The number of rows in the character table of $G$ which are entirely real-valued is the number of conjugacy classes $C$ of $G$ such that $x \in C$ iff $x^{-1} \in C$.

Corollary. If $|G|$ is odd, then the only entirely real-valued character of $G$ is the trivial character.

This leads to a strengthening of the character theory argument used above, so that it now proves that $|G| \equiv c(G) \mod{16}$.
In fact, $16$ is the highest power of $2$ that works here, since for any prime $p \equiv 3 \mod{8}$, we can let $G$ be a nonabelian group of order $p^{3}$. This gives $|G| - c(G) = p^{3} - (p^{2}+p-1) = (p^{2}-1)(p-1) \equiv 16 \mod{32}$.

The really tantalizing thing here is that $(p^{2}-1)(p-1)$ is the $p$-free part of the order of the general linear group $GL_{2}(\mathbb{Z} / (p))$.
I do not know whether $|G|-c(G)$ is always a multiple of $(p^{2}-1)(p-1)$ when $G$ is a $p$-group (though the theorems whose proofs I outlined above establish it when $p = 2$ or $p = 3$), and I do not know if some analogue of the lifting argument works, possibly with $Aut(F_{2})$ replaced by $Aut(B(2,p))$ or $Aut(B(2,p^{k}))$, where $B(r,n)$ denotes the rank $r$, exponent $n$ Burnside group.

Also see Bjorn Poonen's paper:
Congruences relating the order of the group to the number of conjugacy classes, American Mathematical Monthly, 105(1995), 440-442.

Answer by DavidLHarden for Character free proof that Frobenius kernel is a normal subgroup?

2011-04-28T20:38:40Z

You may also be interested in the following references:

K. Corr´adi and E. Horv´ath, Steps towards an elementary proof of Frobenius’ Theorem, Comm. in Algebra, 24, No. 7 1996, 2285-2292.

Paul Flavell, A Note on Frobenius Groups, Journal of Alegbra, 228, 2000, 367-376.

(I hope I didn't screw these up too badly.)

(A very limited instance of) Lagrange's Theorem's converse and A_5

2011-04-16T03:58:09Z

Suppose $G$ is a finite simple group and $|G|$ is a multiple of $60$. Does it follow that $G$ has a subgroup isomorphic to $A_{5}$? If so, can this be proven without using the Classification?

Answer by DavidLHarden for The multiplicative order of 2 modulo primes

2011-04-04T00:26:31Z

A small correction regarding Artin's conjecture is in order: it doesn't just exclude squares. You also need to exclude $-1$.

Efficient presentations for finite groups

2011-03-29T04:05:06Z

A finitely presented group which has more generators than relations has an infinite abelianization and so is an infinite group. Therefore, for a finite group, all presentations must have at least as many relations as generators. A presentation for a finite group is called efficient if the number of generators equals the number of relations.

I know the following examples of efficient presentations for finite groups with $2$ generators:

$< x,y | x^{2} = y^{2} = (xy)^{n}>$, for any $n \geq 2$, which is a group of order $4n^{2}-4n$ in which $xy$ has order $2n^{2}-2n$ and conjugating through $x$ or $y$ sends $xy$ to $(xy)^{2n-1}$. (When $n=2$, this is the quaternion group of order $8$.)

$< x,y | x^{3} = y^{3} = (xy)^{2}>$, which is a double cover of $A_{4}$ isomorphic to $SL(2,3)$. This group is isomorphic to the group of quaternion units, together with $\pm \frac{1}{2} \pm \frac{i}{2} \pm \frac{j}{2} \pm \frac{k}{2}$.

$< x,y | x^{4} = y^{3} = (xy)^{2}>$, which is a double cover of $S_{4}$ not isomorphic to $GL(2,3)$. This is isomorphic to the preceding group, together with every quaternion of the form $\pm \frac{u}{\sqrt{2}} \pm \frac{v}{\sqrt{2}}$, where $u$ and $v$ are two distinct elements of the set $\{ 1, i, j, k \}$.

$< x,y | x^{5} = y^{3} = (xy)^{2}>$, which is a double cover of $A_{5}$ isomorphic to $SL(2,5)$. This is isomorphic to the group of unit quaternions representing $SL(2,3)$ as above, together with a set of icosians explicitly described in Conway and Sloane's SPLAG, which I am too lazy to describe here.

All of these groups have a central element of order $2$, and except for the members of the infinite family that have $n$ being odd, a subgroup isomorphic to the quaternion group of order $8$.

How does this generalize to larger numbers of generators, or, at least, what are some examples of efficient presentations of finite groups using $3$ generators? (I need not explain why I know all examples of efficiently presented groups with a single generator.) Is there a group analogous to the quaternion group of order $8$ for each number of generators? Is there a group analogous to $SU(2)$, which has subgroups isomorphic to the smallest member of the infinite family and all three exceptional examples? Is the center of a nontrivial finite group possessing an efficient presentation always nontrivial? (And what is a good reference for discussing this?)

Comment by DavidLHarden

2013-03-20T19:23:25Z

The mod $\l$ representation of what group is degenerate modulo 691? 691 doesn't divide the order of any Conway group -- indeed, no prime exceeding 71 divides the order of a sporadic group.

Comment by DavidLHarden

2013-03-17T07:44:32Z

You mean, it's 50-50 for those $n$ such that $\tau(n) \neq 0$. If there is a prime $p$ such that $\tau(p) = 0$, then multiplicativity of $\tau$ yields $\tau(pm) = 0$ whenever $m$ is a nonmultiple of $p$, giving a set of density $\frac{1}{p} - \frac{1}{p^{2}}$ on which $\tau$ vanishes. Thanks for the update on Sato-Tate.

Comment by DavidLHarden

2013-02-26T23:13:31Z

No. $\sin{t} = \sin{\pi - t}$ for all real numbers $t$, so the kernel of your homomorphism would contain the difference $\pi - 2t$ for all real numbers $t$. Since the kernel is all of $\mathbb{R}$, the homomorphism must be trivial. You can try to remedy this by taking an appropriate linear combination of sine and cosine, but the only examples of this which should work are those which are scalar multiplies of $\cos{t} + i \cdot \sin{t} = e^{i \cdot t}$.

Comment by DavidLHarden

2013-01-15T10:26:07Z

What do you mean by "analytic methods"? What algebraic properties of the real numbers would you appeal to to distinguish it from fields for which this is not true, if you don't use properties established by using what's usually called analysis? For example, if you allow the Intermediate Value Theorem, you can reduce to the case where you consider a $2n \times 2n$ matrix. But this is analytic, since it is proven by noting that polynomials are continuous functions.

Comment by DavidLHarden

2012-12-25T09:57:08Z

I am surprised no one has mentioned dms.umontreal.ca/~andrew/PDF/PNTforaps.pdf in this thread.

Comment by DavidLHarden

2012-11-26T02:04:06Z

There is some material that is pretty close to a proof of this (it contains most, if not all, of the elements of the proof) in Marshall Hall Jr.'s "Theory of Finite Groups".

Comment by DavidLHarden

2012-11-25T11:15:54Z

Why is a reference considered preferable to a proof? A proof is what you want to find in the reference.

Comment by DavidLHarden

2012-11-11T11:06:41Z

Well, geometrically, that can be described as the (limiting) probability that a (uniformly) randomly chosen lattice point is visible from the origin.

Comment by DavidLHarden

2012-11-10T02:20:03Z

Another counterexample: $M_{22}$ on 22 points is a counterexample to Lemma 5 of math.GM/0204209 . (As Gerry Myerson noted, this is overkill. However, I'm interested in the sporadic simple groups and this is a way to use one of them.)

Comment by DavidLHarden

2012-09-24T02:41:12Z

Shameless Mathieu plug: Even more mysterious about #1: the smallest group containing subgroups isomorphic to both $A_{8}$ and $PSL_{3}(4)$ is the Mathieu group $M_{23}$. $PSL_{3}(4)$ is also beastly on its own because its outer automorphism group is large, its Schur multiplier is very large (order 48), and its Schur multiplier is related to the notoriously elusive Schur multiplier of $M_{22}$, in which $PSL_{3}(4)$ is a subgroup of index 22. To see $A_{8} \cong GL_{4}(2)$, one can consider how the stabilizer of an octad in $Aut S(5,8,24) = M_{24}$ acts on the 24 points.

Comment by DavidLHarden

2012-06-27T19:29:41Z

Now, thinking more clearly, it is clear that the sublattice used to prove unimodularity is the set of v such that, for all u∈Λ, v⋅u is a multiple of p. The dimension of this space is the modulo p codimension of the rowspace, so the rowspace's being a proper subspace of $\Lambda / p\Lambda$ implies that this space is an invariant sublattice of Λ strictly between Λ and pΛ. But my original question still stands

Comment by DavidLHarden

2012-04-14T23:54:36Z

PSL(4,2) and A_8 are isomorphic; the other simple group of that order is PSL(3,4).

Comment by DavidLHarden

2012-02-25T18:29:34Z

Minor quibble: $S_{5} = \Sigma L(2,2^{2})$ is sharply 4-transitive, so "p > 2" should be strengthened to "p > 3".

Comment by DavidLHarden

2011-10-31T22:44:40Z

Thanks for describing this construction which accounts for all loops! Since I am interested in the sporadic groups and related objects, my question is: how does one obtain the Parker loop of order $2^{13}$ from this?

Comment by DavidLHarden

2011-10-08T23:24:17Z

Thanks! I mistranscribed the formula for $\alpha$. Will edit now.