User nick gill - MathOverflow

Answer by Nick Gill for element of order n such that $\pi(n)=\pi(G)$, where $\pi(n)$ denote the prime divisors of $n$

2013-04-30T08:45:01Z

There is a pathological example that pretty much demonstrates that the existence of such an element gives no significant information about the group:

Example 1. Let $H$ be any finite group, and let $\pi(H)=\{p_1,\dots, p_k\}$ . Now let $C$ be a cyclic group of order $p_1\cdot p_2\cdots p_k$ with generator $c$. Then $\pi(H\times C)=\pi(H)$ and $H\times C$ has an element $g=(1,c)$ of order $n=p_1\cdot p_2 \cdots p_k$, i.e $\pi(n)=\pi(H)$.

@Someone has suggested a second example which allows one to construct perfect groups with the required property (and thereby deals with my earlier remark "My hunch is that if you prescribe that $G$ is perfect, i.e. $G=G'$, then there will never exist an element of the kind you seek... But even then I'm not sure"):

Example 2. Let $S$ be any simple group and let $\pi(S)=\{p_1,\dots, p_k\}$ . Now let $G=\underbrace{S\times \cdots \times S}_k$ and observe that $\pi(G)=\pi(S)$. Now let $s_i$ be an element of order $p_i$ in $S$ and observe that $g=(s_1,\dots, s_k)\in G$ has order $\pi(S)$.

Both examples are also relevant to your generalized question.

Answer by Nick Gill for Resolvable designs from projective space

2013-04-23T13:17:33Z

The answer is yes, as the following paper makes clear:

Beutelspacher, Albrecht. On parallelisms in finite projective spaces. Geometriae Dedicata 3 (1974), 35–40.

According to the MSN review, the author proves that that any finite projective space of dimension $d=2^{i+1}−1$ (with $i=1,2,\dots$) admits a parallelism of lines. In other words, the set of points and lines form a resolvable design.

I also found a positive answer (in a different direction) in a comment in this paper:

Hishida, Takaaki; Jimbo, Masakazu Cyclic resolutions of the BIB design in PG(5,2). Australas. J. Combin. 22 (2000), 73–79.

Specifically, the authors remark that $PG(n,2)$ is resolvable for $n\geq 3$, although I don't know where you would find a proof.

I do not know if there is a full characterization of which projective spaces are resolvable.

Answer by Nick Gill for Distance between vertices in a vertex transitive graphs.

2013-04-22T09:44:30Z

The class of vertex-transitive graphs is too wild for this question to admit a coherent answer. The set of distances between vertices can vary a great deal - some examples:

$K_n$, the complete graph on $n$ vertices. Here all vertices are distance 1 from each other;
$K_{n,n}$, the complete bipartite graph with two lots of $n$ vertices. The set of distances is $\{1,2\}$ ;
$C_n$, a cycle on $n$-vertices. The set of distances between vertices is $\{1,2,\dots, \lfloor\frac{n}{2}\rfloor\}$ ;

These are just a tiny set of examples from the full class - there are lots of `sporadic' examples for which the set of distances will be equally sporadic. To see this have a look at Gordon Royle's list of vertex-transitive graphs with at most 31 vertices.

Edit: I had a look through Gordon's list and noticed that the following is true: for every $n\leq 8$ and for every $a\leq \lfloor \frac{n}{2}\rfloor$, there is a vertex-transitive graph $X_{n,a}$ which has $n$ vertices and for which the set of distances is $\{1,\dots, a\}$ . I wonder if this is true for all $n$?

Edit 2: The question has now been changed to ask for a proof that all vertices in a vertex-transitive graph have the same eccentricity. This is a simple consequence of vertex-transitivity, i.e. not research level.

Answer by Nick Gill for Conjugacy classes in PSL(3,q) and PSU(3,q)

2013-04-22T10:01:55Z

This is well-known, and there are a number of relevant references. Firstly, there are these by Wall (they are pretty hard to read though).

Wall, G. E. Conjugacy classes in projective and special linear groups. Bull. Austral. Math. Soc. 22 (1980), no. 3, 339–364.

Wall, G. E. On the conjugacy classes in the unitary, symplectic and orthogonal groups. J. Austral. Math. Soc. 3 1963 1–62.

You might also be interested in this paper which I personally find much more readable.

Macdonald, I. G. Numbers of conjugacy classes in some finite classical groups. Bull. Austral. Math. Soc. 23 (1981), no. 1, 23–48.

You could also look at Carter's Finite groups of Lie type (email me if you want a copy) although that is a rather hard text and is much more general than you need.

For conjugacy in $PSL_3(q)$ you could also just do a search on Jordan rational forms - these forms classify conjugacy in $GL_3(q)$, and this classification can then be adapted to deal with $PSL_3(q)$. I have a paper with Anupam Singh in which we describe how to do this (again in much greater generality than you need).

Answer by Nick Gill for 2-sylow subgroups

2013-04-18T09:47:23Z

Derek's comment answers this question, however maybe I can add a little detail for the one aspect that is slightly tricky.

It should be pretty clear how to turn a Sylow 2-subgroup of $S_{2^{r-1}}$ into a set of $2^r\times 2^r$-block matrices with blocks of size $2$. Which means that the only (potentially) tricky thing is to write down matrices for a Sylow $2$-subgroup of $GL_2(q)$. For this, there are two easy cases and a hard case:

If $q$ is even, then you can take your Sylow $2$-subgroup to be upper-unitriangular matrices. Easy.
If $q\equiv 1\pmod 4$, then a split torus of size $(q-1)^2$ will contain a Sylow $2$-subgroup of $GL_2(q)$, and you can just find a bunch of nice diagonal matrices to do the job.
If $q\equiv 3 \pmod 4$, then a Sylow $2$-subgroup will lie in a non-split torus, isomorphic to a cyclic subgroup of order $q^2-1$. So you'll need to write down a bunch of matrices corresponding to this torus - you can do it using the method outlined in Carter's Finite groups of Lie type: you need to `twist' the torus $T$ in $GL_2(q^2)$ consisting of diagonal matrices by an element $g$ such that $g^{-1}F(g)$ corresponds to a non-trivial element of the Weyl group with respect to $T$ (here $F$ is the Frobenius endomorphism). A nice way of doing this is to let $x$ be an element of $\mathbb{F}_{q^2}$ satisfying $x^q=-x$, and then let $g=\left(\begin{array}{cc} a & b \newline c& d \ \end{array}\right)$ such that $$\left(\begin{matrix} a^q & b^q \newline c^q & d^q \end{matrix}\right) = \left(\begin{matrix}a & b \newline c& d \end{matrix}\right)\left(\begin{matrix} & -x \newline x & \end{matrix}\right).$$ You can make your life easier by specifying that $\det g=1$, and you end up with $$g = \left(\begin{matrix} a & a^qx \newline c & c^qx \end{matrix}\right)$$ where $ac^qx - ca^qx=1$. Now the torus you are seeking is $gTg^{-1}$. The intersection of this torus with $GL_2(q)$ is a cyclic group of order $q^2-1$, and it will contain a Sylow $2$-subgroup of $GL_2(q)$ as required.

I hope that makes sense. If you need more details, tell me. If you need an e-copy of Carter's book I'll happily share it.

Answer by Nick Gill for The "interplay" between additive and multiplicative structure in a field

2013-03-22T10:12:09Z

This answer is just adding flesh to @Frank Thorne's earlier answer. He noted that the idea of "addition and multiplication interacting" comes up in additive combinatorics. Perhaps the most obvious instance of this is in the study of the sum-product phenomenon (SPP).

Roughly speaking the SPP asserts that any subset of a field $F$ must ``grow'' under either addition or multiplication. The way one makes this rough statement precise depends on the field in question. Let me consider two instances:

Suppose $F=\mathbb{R}$. In this situation the central conjecture is due to Erdos and Szemeredi:

For every $\varepsilon\in (0,1)$, there exists $c>0$, such that for $A$ a finite subset of $\mathbb{R}$, $\max(|A+A|, |A\cdot A|) \geq c |A|^{2-\varepsilon}$.

This conjecture is still open, however progress has been made. The strongest statement is (I believe) due to Solymosi, but it's also worth mentioning the work of Elekes. With a very simple argument, he connected SPP to questions in incidence geometry in the plane and to the idea of the crossing number in $\mathbb{R}^2$ to prove:

There exists $c>0$, such that for $A$ a finite subset of $\mathbb{R}$, $\max(|A+A|, |A\cdot A|) \geq c |A|^{5/4}$.

One last remark - another way of thinking about the Erdos-Szemeredi conjecture is this: it says that a set $A$ of real numbers cannot simultaneously be both a geometric progression and an arithmetic progression (since, by results of Freiman and others, these are the classes of sets that do not grow under multiplication and addition, respectively).

Suppose $F=\mathbb{Z}/p\mathbb{Z}$. In this situation, the central result is due to Bourgain, Katz and Tao:

For every $\delta>0$ there exists $\varepsilon>0$ and $c>0$, such that for $A$ a finite subset of $\mathbb{Z}/p\mathbb{Z}$ with $|A| < p^{1-\delta}$, we have $\max(|A+A|, |A\cdot A|) \geq c |A|^{1+\varepsilon}$.

The statement is slightly different to that in $\mathbb{R}$ because it is clear that sets that are almost as large as the field itself cannot possibly grow.

This result has been generalized in various ways to arbitrary finite fields. However in this more general setting one has to deal with the presence of finite subfields (again this does not crop up in $\mathbb{R}$), and so statements tend to be slightly technical. There is also a wealth of work giving values for $\varepsilon$ when $\delta$ is, say, $\frac12$, as well as a lot of work connecting this result to geometry over finite fields (in the spirit of the work of Elekes).

Answer by Nick Gill for automorphisms of graphs and finite permutation groups

2013-03-26T09:34:54Z

This question is probably going to turn into a community-wiki style list of favourite open problems concerning permutation groups and graphs. So, for what it's worth, here are two of mine:

The Weiss Conjecture: Let $G$ act vertex-transitively on some graph $\mathcal{G}$ of valency $k$. Let $v$ be a vertex of $\mathcal{G}$ and assume that $G_v$ acts primitively on its neighbours. Then $|G_v| \leq f(k)$ where $f:\mathbb{N}\to \mathbb{N}$ is some function depending only on $k$.

There is a wealth of work on this conjecture by many people. I would particular recommend this paper by Potocnik, Spiga and Verret, where the conjecture is discussed at length and some more general conjectures are also proposed. I'd also recommend this paper by Praeger, Pyber, Spiga and Szabo, in which substantial progress towards a proof of the conjecture is made.

All of the papers dealing with this conjecture make heavy use of permutation group techniques; recent papers also tend to make use of results coming out of the classification of finite simple groups.

The classification of regular maps: A map is a `nice' embeding of a graph on a surface, in a way that generalizes the notion of a planar graph. The map is regular if (to choose one of several slightly different definitions) it admits an automorphism group that acts as homeomorphisms on the surface, and is transitive on vertex-edge incident pairs.

The subject is very old (cf. the platonic solids), but the modern concern with these things began with Brahana and Coxeter and, then a few years later, with this beautiful paper by Jones and Singerman. There is now a wealth of literature aimed at classifying regular maps subject to constraints on, for instance, the underlying surface, the underlying graph, or the automorphism group. Prominent authors include Conder, Siran, Jones, Nedela, Breda d'Azevedo, Tucker, Archdeacon etc etc. Permutation group techniques are commonly used, as well as ideas from topology, group generation, Riemann surfaces etc.

The notion of a map is closely related to the important notion of a dessin d'enfant which was the subject of a famous paper by Grothendieck. There is a whole other school of work looking at maps from this perspective, however (to my knowledge) the emphasis in this school is not on the permutation group approach, and so may not be of so much interest to you.

Answer by Nick Gill for Measures of non-abelian-ness

2013-03-25T09:56:41Z

For certain applications, the abelian-ness of a group is inversely proportional to the quasirandom-ness of a group. The latter notion is more obscure, so this observation might not be a help at first. On the other hand quasirandom-ness can be measured quantitatively in a number of basically equivalent ways.

This is all laid out very beautifully in the paper Quasirandom groups by Tim Gowers. This is the first paper where the notion of a quasirandom group rears its head, and Gowers gives five equivalent definitions. Perhaps the most accessible is this: a group is $c$-quasirandom if the smallest dimension of a non-trivial irreducible representation is at least $c$. Obviously abelian groups are 1-quasirandom, but not 2-quasirandom; indeed, the same is true of all non-perfect groups.

On the other hand Gowers makes this remark about the family of groups $PSL_2(q)$:

...the order of $PSL_2(q)$ is $q(q^2 − 1)/2$, so the lowest dimension of a non-trivial representation is proportional to the cube root of the order of the group. This tells us that, in a certain sense, $PSL_2(q)$ is very far from being abelian.

Answer by Nick Gill for a group with all sylow p subgroups cyclic

2013-03-25T09:49:05Z

There is a complete classification of groups with all Sylow-subgroups being cyclic. In fact one can weaken this: we say that a group $G$ is almost Sylow-cyclic if every Sylow subgroup of $G$ has a cyclic subgroup of index at most $2$. Almost Sylow-cyclic groups are fully classified in two papers:

M. Suzuki, On finite groups with cyclic Sylow subgroups for all odd primes, Amer. J. Math. 77 (1955) 657–691.

W.J. Wong, On finite groups with semi-dihedral Sylow 2-subgroups, J. Algebra 4 (1966) 52–63.

You may also be interested in an old paper by Holder from 1895 who proved that every group with all Sylow subgroups cyclic is solvable. (This is not true under the weaker supposition that a group is almost Sylow-cyclic, as the group $PSL_2(7)$ demonstrates.)

Answer by Nick Gill for What are dessins d'enfants?

2013-03-22T09:51:51Z

There are many good answers to this question already. However it seems important to me that the contribution of Jones and Singerman to this subject is noted. These two British mathematicians from the University of Southampton wrote an important paper on this subject some time before Grothendieck wrote his Esquisse.

The paper in question is:

MR0505721 Zbl0391.05024 Jones, Gareth A.; Singerman, David Theory of maps on orientable surfaces. Proc. London Math. Soc. (3) 37 (1978), no. 2, 273–307.

The paper is beautifully written, and outlines the correspondence between maps on topological surfaces, maps on Riemann surfaces, and groups with certain distinguished generators. They do not consider the Galois action, this being the aspect of the area that so excited Grothendieck. Their notion of a map is a particular instance of a dessin d'enfant (these days a map is also known as a clean dessin), the more general notion of hypermap which was considered subsequently corresponds to the general dessin d'enfant.

A later paper, by Bryant and Singerman, extended the treatment to surfaces with boundary.

Information about permutation character from local action

2013-03-12T16:06:26Z

Let $G$ be a finite permutation group acting transitively, but not regularly, on a set $V$. Let $H$ be the stabilizer of some point $v\in V$, and suppose that $H$ acts 2-transitively on one of its (non-trivial) orbits, i.e. $H$ acts 2-transitively on the (left) cosets of $H\cap H^g$ for an appropriate choice of $g\in G$.

General question: What can I conclude about the permutation character of $G$ acting on $V$?

Specifically:

Can I give a lower bound for the multiplicities of the non-trivial irreducible components of the permutation character of $G$ on $V$?
What about the dimensions of these components?
What about if I weaken '2-transitively' to 'primitively' or something similar?

Answer by Nick Gill for Classification of generously transitive groups

2013-02-28T16:46:01Z

I believe the answer is No, there is no good classification of these things. It might be helpful for you to know that a "generously transitive permutation group" is the same as a 2-star transitive group. (See for instance the introduction to "The k-star Property for Permutation Groups" by Clough, Praeger, Schneider.) I can email you a copy of this paper if you need it.

Answer by Nick Gill for Question on the projective special unitary group

2013-01-30T17:14:44Z

This can be answered on a case-by-case basis. Work in $SU(3,q)$ because it's easier, and observe that if $r>3$ then $r$ divides one of $q, q+1, q-1, q^2-q+1$. Now go through these one at a time.

E.g. if $r$ divides $q$, then $r=p$. Now either calculate the size of the normalizer of a Sylow $p$ or just observe $r+1$ is less than the minimal index of a subgroup of $G$. Similarly if $r$ divides $q^2-q+1$, then the normalizer of a Sylow has size $3(q^2-q+1)$ and its index is certainly bigger than $r+1$ for any $r$ dividing $q^2-q+1$. The other cases are all similar.

Constructing expanders in Z/pZ

2013-01-29T14:45:10Z

Fix a positive integer $k>0$. For $p>k$ a prime, let $A_p$ be a subset of the finite field $\mathbb{Z}/p\mathbb{Z}$ of size $k$ which contains a primitive element.

Define $G_p$ to be the (di)graph whose vertices are elements of $\mathbb{Z}/p\mathbb{Z}$, with two vertices $i,j$ joined by an edge provided $j=ia$ or $j=i+a$ for some $a\in A_p$.

(I'm mainly interested in the situation where $A_p$ is closed under the operations of taking multiplicative and additive inverses; under these assumptions I can think of $G_p$ as a graph rather than a digraph.)

Question: Is $(G_p)_{p \textrm{ a prime}}$ a family of expanders?

Background: I'm expecting the answer to be either "possibly" or "no" (because if it were "yes" I'd hope I'd have heard about it already).

My interest comes in studying the Bourgain-Gamburd machinery for proving expansion from results about growth. For the family $(G_p)$, the relevant growth result is the Bourgain-Katz-Tao sum-product theorem for fields of prime order.

One needs more than just a growth result of course, one also needs to have some notion of `quasirandomness' (but I think I can handle this), as well as a lower bound on the girth of the graph. I've not thought much about this last aspect so I guess this is the most likely to be the sticking point.

Answer by Nick Gill for Abelian subgroup of PSL(3,q)

2013-01-30T13:45:07Z

Here's a rough answer as I have very little time. I'm going to work in $K=SL(3,q)$ rather than $PSL(3,q)$ as it amounts to the same thing.

(1) Observe first that the centralizer of a $p$-element of $K$ has order $q^3$ or $q(q-1)$. This is just a matter of working with matrices. Then you can check that the centralizer of order $q(q-1)$ is abelian and you've got your first maximal. The only other possibility, then, is that a maximal abelian with order dividing $p$ has order dividing $q^3$. i.e. it lies in a Sylow $p$-subgroup, so is conjugate to a bunch of upper-triangular matrices. Now work with matrices to convince yourself that the maximal order is $q^2$.

(2) So we are left with abelian group of order dividing $(q-1)^2(q+1)$. You can use the theory of Jordan rational forms here: if a matrix has eigenvalues that don't lie in $\mathbb{F}_q$ then its centralizer has order $q^2-1$ and is abelian, hence maximal abelian. If all eigenvalues of all elements of your abelian group lie in $\mathbb{F}_q$, then they are simultaneously diagonalizable and so a maximal such group has order $(q-1)^2$.

Answer by Nick Gill for The maximal Abelian subgroups of PSL(3,q).2 the extension of PSL(3,q) by the graph automorphismAutomorphism

2013-01-23T11:01:48Z

It's not possible for extensions of ${\rm PSL}(3,q)$ to have the same maximal abelian subgroups as ${\rm PSL}(3,q)$ since these don't include the abelian subgroups not wholly contained in ${\rm PSL(3,q)}$.

However we can still try and classify the maximal abelian subgroups of extensions of ${\rm PSL}(3,q).$

Here's a rough sketch of how I'd approach this. Suppose that $H$ is a maximal abelian subgroup of a cyclic extension of $K$ where $K = {\rm PSL(3,q)}$. There are two cases:

$H\leq K$. These can be read off from the known subgroups of $PSL(3,q)$. (See Mitchell, Hartley or Bloom for the first classification of these. Or see Kleidman & Liebeck, or the survey article by King for a modern treatment.)
$H\not \leq K$. Then $H$ contains an outer automorphism $g$ and so, in particular $H \cap K$ lies in $C_K(g)$. Subcases that you are interested in:

(a) If $g$ is a graph automorphism of order $2$, then $C_K(g)\cong {\rm PSL}_2(q)$ or ${\rm PGL}_2(q)$ (since these are isomorphic to 3-dimensional orthogonal groups). The maximal subgroups of these groups are easy (Dickson gave the first proof), and the abelian subgroups can be read off.

(b) If $g$ is a graph automorphism of order greater than $2$, then we can assume it has order a multiple of $4$ (otherwise one of its powers is a graph aut of order $2$) and so $H$ contains an involution $h$ of $PSL(3,q)$. Now $C_K(h)=\hat GL(2,q)$ and, again, abelian subgroups can be read off.

(c) If $g$ is a field automorphism of order $3$, then $C_K(g)$ is a subfield subgroup. And so the classification of subgroups is the same as for $K$.

(d) If $g$ is a field automorphism of order greater than $3$. Again we can assume it has power a power of $3$, so $H$ contains an element of order $3$. Its centralizer can be calculated (its structure will depend on whether $3$ divides $q$, $q-1$ or $q+1$) and maximal abelians read off.

p.s. Some further thought made me wonder whether your comment about abelian subgroups being the same was supposed to be this:

A maximal abelian subgroup of ${\rm PSL}_3(q).2$ (graph aut) restricts to a maximal abelian subgroup of ${\rm PSL}_3(q)$.

I checked the ATLAS and this is not true: Let $K={\rm PSL}_3(5)$. Then $K.2 \backslash K$ contains an element of order $8$ whose centralizer $C$ is of order $8$, thus is maximal abelian. But $K\cap C$ (which has order $4$) is not maximal abelian in $K$.

Answer by Nick Gill for 2x2 subdeterminants of a matrix

2013-01-16T13:30:52Z

By "corresponding submatrices" I presume you mean those $2\times2$ minors obtained by deleting $n-2$ colums and $n-2$ rows, where these columns and rows have the same $n-2$ indices. Once you've calculated the determinants of these submatrices you recover the action of $A$ on the exterior square $\Lambda^2 V$.

Now the following paper: "An algorithm for recognising the exterior square of a matrix" by Catherine Greenhill explains how to then obtain the original matrix $A$. Here's the relevant quote:

One computational problem which presents itself immediately is this: how can we determine whether a given matrix $Y$ is equal to the exterior square of another matrix $X$? In particular, if such an $X$ exists then we would like to construct one. A polynomial-time algorithm which solves this problem is described in Section 5.

The paper can be downloaded here.

One needs to be slightly careful here, because the exterior square does not quite determine the matrix $X$ uniquely. Here is another quote from the paper:

We prove in Section 4 that two matrices $X$, $X'$ with rank at least three have the same exterior square if and only $X'\in \{X, -X\}$ .

So if the rank is at least three (which it is, since you are assuming invertibility), then we are pretty much done. I'm guessing that the situation where the rank is $\leq 2$ would be easy enough to resolve but in any case that's outside the scope of the question...

Answer by Nick Gill for Largest permutation group without 2-cycles or 3-cycles

2013-01-10T10:15:57Z

This is really an comment to @Dima's answer, but it's a bit long...

There is a classical result of Jordan in permutation group theory that says the following:

If a primitive group $G$ [on a set of order $n$] contains a $p$-cycle, where $p < n - 3$ is prime, then $G$ is the alternating or symmetric group of degree $n$.

(See Wielandt's Finite permutation groups for a proof.)

So any primitive group will satisfy the requirements of the OP. There are LOTS of papers written about the maximal orders of primitive groups, so you should investigate these. The starting point is classical work of W.A. Manning, but once the Classification of Finite Simple Groups was completed, much stronger results were possible. Here is a relevant quote:

"It is now known that the largest [primitive] groups [on a set of order $n$ occur for $n$ of the form $c(c − 1)/2$ and are $S_c$ and $A_c$ acting on the unordered pairs from a set of size $c$."

The quote comes from Permutation Groups and Normal Subgroups by Cheryl Praeger. So you can work out from this what the upper bound for the order of a primitive group containing neither 2-cycles nor 3-cycles. Which leaves the intransitive and imprimitive ones...

Answer by Nick Gill for New grand projects in contemporary math

2013-01-07T13:16:06Z

Within the realm of finite permutation group theory there are a series of projects that could be collectively entitled The classification of finite combinatorial objects subject to transitivity assumptions. These kinds of classifications have, of course, been around a long time (for instance the Greeks interest in platonic solids is a particular instance) but the nature of this work changed very dramatically with the completion of the Classification of Finite Simple Groups.

Particular threads of this grand project include:

The classification of distance-transitive graphs (cf. work of Saxl, Van Bon, Inglis and others);
The classification of flag-transitive designs (cf. the paper of Buekenhout, Delandtsheer, Doyen, Kleidman, Libeck and Saxl which gives an almost-complete classification). More recently the flag-transitivity condition has been relaxed, and progress has been made on classifying designs which are, for instance, line-transitive or point-primitive (cf. work by many authors!)
The classification of finite projective planes subject to various assumptions. This is a special case of the previous item. In 1959 Ostrom & Wagner gave a full classification of projective planes admitting 2-transitive automorphism groups; in 1987, and using CFSG, Kantor gave an almost-classification of projective planes admitting point-primitive automorphism groups; results have appeared subsequently dealing with the weaker situation of point-transitivity.
The classification of generalized polygons subject to various assumption. The previous item is a special case of this. (I know of recent work on generalized quadrangles due to Bamberg, Giudici, Morris, Royle and Spiga; not sure about hexagons and octagons.)
The classification of `special geometries'. This is work initiated (I believe) by Francis Buekenhout in an attempt to understand the sporadic groups (see the earlier answer by J Mckay). The idea is to find geometries on which the sporadic groups act, analogously to the way the groups of Lie type acts on Tits buildings.
The classification of regular maps (i.e. graphs embedded nicely on topological surfaces and admitting an automorphism group that is regular on flags/ directed edges). This is the thread that involves the Platonic solids; more recently there is a wealth of work by people like Conder, Siran, Tucker, Jones, Singerman, and many others.

There are many others but these give a flavour (skewed to my own interests).

In many of the threads just mentioned (but not all) a crucial first step in classifying objects is to use the Aschbacher-O'Nan-Scott theorem which describes the maximal subgroups of $S_n$. One then often needs information about maximal subgroups of the almost simple groups and so another famous theorem of Aschbacher comes into play (along with results by Kleidman, Liebeck, and others). These theorems are closely related to the answer given by Gil Kalai - the production of results of this ilk (facts about the finite simple groups) is, in itself, a grand project!

Answer by Nick Gill for Group PGL(2,p) where p is prime

2012-12-19T16:23:36Z

You should consult the papers of Akhlaghi, Khosravi and Khatam - they have two that are relevant. I don't have subscription access to the full text of the articles but I can access enough to say the following.

With regard to the group $PGL(2,q)$, the situation depends dramatically on whether or not $q$ is prime.

Case 1: $q=p$, a prime. Let me quote from the mathscinet review of this paper:

There are infinitely many nonisomorphic finite groups with the same prime graph as $PGL(2,p)$. In this paper, the authors determine the structure of finite groups $G$ such that $\Gamma(G)=\Gamma(PGL(2,p))$, where $11\neq p \neq19$ and $p$ is not a Mersenne or Fermat prime. In particular, if $p\neq 13$ then $G$ has a unique nonabelian composition factor which is isomorphic to $PSL(2,p)$ and if $p=13$ then G has a unique nonabelian composition factor which is isomorphic to $PSL(2,13)$ or $PSL(2,27)$.

Here I'm writing $\Gamma(G)$ to mean the prime graph of a group $G$. So, to answer your question, this result means that if a solvable group $G$ is to satisfy $\Gamma(G)=\Gamma(PGL(2,p))$ for some prime $p$, then $p$ is a Mersenne or Fermat prime.

Case 2: $q$ is not prime. Then this paper proves that the group $PGL(2,q)$ is characterized by its prime graph, i.e. there are no other groups sharing the same prime graph.

Answer by Nick Gill for Exponent of Sylow $p$-subgroup of classical groups over a field of characteristic $p$

2012-12-14T10:18:12Z

Here's a more naive approach than that suggested by Jim in his answer, and Kreck in comments.

One can explicitly write down the Sylow $p$-subgroup as a matrix group using a basis of hyperbolic pairs. If you order this basis correctly, then there will be a Sylow $p$-subgroup of the associated classical group which will be a bunch of upper-triangular matrices. (See Kleidman & Liebeck "The subgroup structure of the finite classical groups" for a full description.)

(Note: I'm avoiding questions about which version of the group you are interested in. Most of the time the natural matrix group version of the classical group is the universal version (the main exceptions involving certain orthogonal groups). In any case, if you avoid bad primes, as Jim describes above, the exponent of a Sylow $p$-subgroup of your group won't depend on which version you're using.)

So, for example, let $e_1,\dots, e_k, f_1,\dots, f_k$ be such a basis for a vector space $V$ over the field of order $q$ where $q$ is odd, where $V$ is equipped with a non-degenerate alternating bilinear form, then the isometry group of the form will be the symplectic group ${\mathrm Sp}_{2k}(q)$ and one can choose a Sylow $p$-subgroup of $G$ such that all elements are upper-triangular. Once you've done this it's easy to observe that $G$ contains an element $$\left(\begin{array}{ccccc} 1 & 1 & & & \\ & 1 & 1 & & \\ & & \ddots \ddots & & \\ & & & 1 & -1 \\ & & & & 1 \end{array}\right).$$ (The formatting is a bit screwed. It's supposed to indicate a diagonal of $1$'s. Then on my super-diagonal I have $k$ lots of $1$ to start and $k-1$ lots of $-1$ to finish.) I haven't double-checked, but I believe this is an element of maximal exponent. Its order is the least power of $p$ greater than $k+1$.

It's the same story with orthogonal groups. Again I haven't double-checked that I really am obtaining an element of maximal order, but this should be straight-forward.

In any case, these calculations suggest the following result.

Conjecture: Let $P$ be a Sylow $p$-subgroup of an untwisted classical group $G$ over $\mathbb{F}_q$, and suppose that $p$ is not a bad prime. Then the exponent of $P$ is equal to the least power of $p$ greater than ${\mathrm rk}(G)+1$.

(I'm stating the conjecture conservatively. It's possible that it holds for twisted groups, and for bad primes, but that would just be idle speculation!)

Answer by Nick Gill for Groups whose all normal subgroups are principal

2012-12-12T17:00:38Z

My initial answer was, it turns out, weak. So I'm going to add in some of the observations made in comments, and turn this answer into community wiki, so as not to get credit.

If G is principle, then the factors of its upper central series, lower central series and derived series are cyclic. There are many other immediate consequences of definition: If G is principal, then so are its quotients and its characteristic subgroups. Such a group has the max-n property. If it is hypercentral, then it is nilpotent. If solvable, then super-solvable.
For infinite groups, the observation of the previous bullet implies that Baumslag and Blackburn's paper ``Groups with Cyclic Upper Central Factors'' is relevant.
For finite $p$-groups, observe that any principal p-group P is cyclic as the Frattini quotient $P/[P,P]∗P^p$ is one dimensional (again, this follows from the first bullet point). This implies, in particular, that a finite principal nilpotent group is cyclic.
As for finite principal solvable groups, well, things are less clear. Note that $S_3$ is principal.
If $G$ is a finite $p$-group such that its proper normal subgroups are principal ($G$ itself is not principal), then $G$ has maximal class. The converse is also true.
If $G$ is finite nilpotent group such that its proper normal subgroups are principal, then $G$ is cyclic or it is a $p$-group of maximal class.

Answer by Nick Gill for Maximal number of maximal subgroups

2012-12-07T21:34:01Z

The document I linked to above is sufficiently striking as to warrant an answer of its own. I hope it complements the community wiki above.

As mentioned above the relevant conjecture in this area is due to Wall:

Conjecture The number of maximal subgroups of a finite group $G$ is less than the order of $G$.

This has been the subject of much study with the landmark work (until recently) being the above-cited work of Liebeck, Pyber and Shalev. In addition to the result mentioned above they show that the conjecture is true if the group $G$ is simple, up to a finite number of exceptions.

Now a quote from the linked document is relevant:

This largely directed attention to composite groups, where Wall in his original paper had at least shown the conjecture to be true for finite solvable groups. The key remaining cases were known to be semidirect products of a vector space V with a nearly simple finite group G acting faithfully and irreducibly on it.

It turns out that in this case Wall's conjecture implies some bounds on the cohomology groups $H^1(G,V)$. And, as the document relates, examples have now been found which violate these bounds. In particular, Wall's conjecture does not hold.

In light of this development, the bound $C|G|^{3/2}$ mentioned above, also due to Liebeck, Pyber and Shalev, assumes greater importance. Although, as the linked document mentions, it is likely that the value $3/2$ can be reduced a great deal.

One final interesting quote:

A conjecture of Aschbacker and Guralnick, not made at the conference... would now rise to be the main conjecture in maximal subgroup theory. (The conjecture states that it is the number of conjugacy classes of maximal subgroups that is bounded, less than the number of conjugacy classes of elements in the group.)

Anyone interested should definitely read the document. Not only is it interesting mathematically, it's a very engaging account of how this recent breakthrough was achieved.

Answer by Nick Gill for Groups that do not exist

2012-12-07T21:18:56Z

I'm not sure if this is quite what you're looking for but....

In this book "Finite simple groups", Gorenstein tells the story of Feit & Thompson's proof of the odd order theorem. Very roughly, it goes as follows:

Suppose $G$ is a simple group of odd order. Thompson studied the local structure of the group $G$ to obtain information about the structure of the maximal subgroups of $G$. Feit then applied the Brauer-Suzuki theory of exceptional characters to derive a great deal of character-theoretic information about the group $G$. So far so good.

But now they hit a problem. They were seeking, of course, to demonstrate a contradiction. But, as Gorenstein tells it, one of the possible configurations of maximal subgroups & character information proved extremely difficult to disprove. In the spirit of this question, one might say they found an example of a "group that does not exist". In the end, after spending a year being stuck, Thompson managed to demonstrate the required contradiction by a very delicate analysis of the generators and relations of the putative group $G$.

(I don't have a copy of Gorenstein's book with me. If I get chance I might return to this answer so I can provide some quotes. Gorenstein's account of the whole enterprise is really terrific.)

Answer by Nick Gill for Is (n,m)=(18,7) the only positive solution to n^2 + n + 1 = m^3 ?

2012-12-07T14:31:31Z

This is an old question, and has already been well-answered, but what I've got to say is slightly too long for a comment...

The equation $x^2+x+1 = y^3$ is of interest to finite geometers because $x^2+x+1$ is the number of points (and lines) in a finite projective plane of order $x$.

People have mentioned Ljunggren's name in comments above. The paper that's relevant is this:

Ljunggren, Wilhelm Einige Bemerkungen über die Darstellung ganzer Zahlen durch binäre kubische Formen mit positiver Diskriminante. (German) Acta Math. 75, (1943). 1–21.

I heartily recommend the Mathscinet review of that article, which says (amongst other things)...

... that Nagell [Norsk Mat. Forenings Skr. (I) no. 2 (1921)] proved that the equation

(1) $x^2+x+1=y^n$

has only trivial solutions unless $n$ is a power of $3$...

... And that Ljunggren then proved that (1) has only two nontrivial solutions, namely (18,7) and (-19, 7), for n=3.

Answer by Nick Gill for maximal subgroups of finite simple groups

2012-12-07T10:59:58Z

Prop: If $G$ is a finite simple group, then a maximal subgroup of $G$ is trivial or has composite order

Proof: A maximal subgroup of $G$ being trivial clearly corresponds to $G$ being cyclic of prime order. Assume, then, that $G$ is non-abelian.

If $G$ has a maximal subgroup $C$ of prime order, then the action of $G$ on cosets of $C$ is Frobenius. Thus $G$ is a Frobenius group, $C$ is a Frobenius complement and $G$ contains a Frobenius kernel, i.e. $G$ is not simple. QED

So this answers your first question. As for your more general question about finite groups. Well, again, if a group has a maximal subgroup of prime order, then it is Frobenius, so you should consult the literature on Frobenius groups. For this I particularly recommend Isaac's "Finite Group Theory" and Passman's "Permutation groups".

Examples of groups with a maximal subgroup of prime order include dihedral groups of order $2m$ ($m$ odd) or, more generally $C_n \rtimes C_p$ where $p$ is a prime and $C_p$ acts semi-regularly on $C_n$.

Answer by Nick Gill for Cardinals of transitive permutation groups acting on $\{1,\dots,n\}$

2012-11-19T11:29:39Z

As Derek suggests in his comment, this question is too difficult to answer in general. However one could limit the question as follows: clearly if $K$ is a transitive permutation group then $|K|$ divides $|M|$ where $M$ is a maximal transitive subgroup of ${\mathrm Sym}(n)$; thus we can ask about the cardinality of a maximal transitive subgroup $M$ of ${\mathrm Sym}(n)$.

The O'Nan-Scott theorem is the main tool here. Roughly speaking it asserts that such a subgroup $M$ is either imprimitive (and hence a wreath product, with order formula easy), or else it is in a bunch of primitive families. Most of these families have a geometric description and, as such, it is easy to calculate their order.

The `difficult' family in this regard is the family of primitive almost simple groups. In this case one basically needs an enumeration of the maximal subgroups of all almost simple groups, which is a difficult problem but one which has received a great deal of attention.

Depending on what level of information you need, there are complete enumerations of maximal subgroups for many of the almost simples (although not all). However there are also some very nice general statements about the possible sizes of maximal subgroups. One example is this paper by Martin Liebeck; there are many others like it (many by Liebeck and his collaborators).

Answer by Nick Gill for Where are the second- (and third-)generation proofs of the classification of finite simple groups up to?

2012-11-30T13:55:58Z

With respect to the second generation proof you can get an answer `from the horse's mouth' if you like: Ron Solomon gave an update on the program at BIRS recently and a video of his talk is here.

He starts the talk by comparing its progress to `the receding of the glaciers'! In reality, though, they've made very significant headway into the later volumes. (In particular he mentions, around 9:30, that volume 7 is in preparation, and it is mainly this volume that he's discussing in the talk.)

Answer by Nick Gill for Name for a particular subgroup of parabolic subgroups of the general linear groups.

2012-11-26T20:53:31Z

As David says $Q$ is the unipotent radical of $P$. The subgroup $T$ is a preimage of the Weyl group $W$ of the group $G_i\cong GL(V_i/ V_{i+1})$. This group $T$ looks a direct product of $Q$ with a big chunk of a Levi complement of $P$. The Levi complement is a direct product isomorphic to $G_1\times\cdots \times G_k$; to obtain the group $T$, you replace the $i$-th factor by the normalizer $N$ of a maximal split torus $T_0$ of $G_i$.

This is, in fact, the typical way to realize the Weyl group of $G_i$ -- $W$ is isomorphic to the quotient $N/T_0$ -- but this is effectively the same thing as your method of fixing a specific basis of $V_i/V_{i+1}$. The Weyl group rears its head in lots of different ways (most especially as a Coxeter group related to the Dynkin diagram of $G_i$) so this is certainly not the only way to realise it. I don't, however, see any other way to realise your group $T$ (although it depends what you mean by `realise'!).

As for references, it depends on what kind of approach you want. If you want a treatment of $GL_n$ as an algebraic group then I recommend anything by Carter or Humphreys, or else there is the book by Borel. All of these people work in much greater generality than $GL_n$ though. If you just want to understand $GL_n$, then standard algebra texts like the one of Jacobson might be your best bet. (I have e-copies of some of these. If you want them, email me.)

Answer by Nick Gill for Automorphism Group of a p-group : Looking for a Reference

2012-11-23T09:58:30Z

As @DavidLHarden explains in the link that you gave, this theorem is proved by attending to the $p$-part and $p'$-part separately.

For the $p'$-part the result follows from the following theorem of Burnside:

Let $\psi$ be a $p'$-automorphism of the $p$-group $P$ which induces the identity on $P/\Phi(P)$. Then $\psi$ is the identity automorphism of $P$.

This is the result that Geoff refers to in his comment above. It is discussed and proved in Section 5 of Gorenstein's Finite Groups, specifically Theorem 1.4 of that section.

I do not know of a reference for the $p$-part of the proof. You should certainly look at the paper by Neumann that Geoff mentions, however if I understand that proof correctly it only proves your bound for $|Out P|$, rather than $|Aut P|$. On the other hand Neumann is considering a much more general setting than just $p$-groups.

Comment by Nick Gill

2013-05-22T08:38:38Z

In that case weakly doubly transitive is the same as distance-transitive in other parts of the literature...

Comment by Nick Gill

2013-05-15T12:34:50Z

Ketan: are you perhaps interested in finite quotients rather than subgroups. So your question becomes: what relations must I add to obtain a finite group? (It's a question with no very straight-forward answer by the way.)

Comment by Nick Gill

2013-05-15T09:10:25Z

I haven't got a copy but here is a link to a blogpost which discusses the paper extensively: paramanands.blogspot.co.uk/2012/03/… (You could maybe email the author of the blog to see if he has a copy.)

Comment by Nick Gill

2013-05-01T09:34:48Z

@MarkSapir, The problem I'm having is not understanding the outer automorphism groups of FSGs - as you say this is well understood. The problem is understanding their centralizers. Or more precisely the centralizers of their nilpotent subgroups. The centralizers of individual automorphisms are well understood - Gorenstein, Lyons, Solomon vol. 3 does the job for instance - but understanding how these things intersect (i.e. calculating subgroup centralizers) seems like a rather subtle question. I doubt a centralizer will ever be trivial but, as I said above, I think proving it might be hard.

Comment by Nick Gill

2013-04-30T15:05:42Z

I've been musing on a this question under the (very strong) extra assumption that $G$ is simple, but even this seems a little tricky. I guess that $C_G(H)$ is never trivial here, but how to prove it? One could do an exhaustive analysis of the outer automorphism group, but that seems very unsatisfactory... I may well be missing an easy solution though...

Comment by Nick Gill

2013-04-30T10:35:09Z

Good point, shall edit.

Comment by Nick Gill

2013-04-30T08:45:48Z

Even better (in my opinion) would be to delete this answer, and to edit the original question to add this generalization.

Comment by Nick Gill

2013-04-29T14:43:03Z

I presume that by $\oplus$ you mean direct product... And that the $\phi_i$ and $\beta_i$ are all strictly positive. In which case this result can be proved easily by induction on $n$. You won't get more of an answer here as this is for research-level questions only. You could try MSE: math.stackexchange.com

Comment by Nick Gill

2013-04-29T14:36:45Z

Here it is: dropbox.com/s/yaocircrp2ygaaw/…

Comment by Nick Gill

2013-04-23T20:10:49Z

You are very generous about what I was assuming... But thanks for giving me the benefit of the doubt :-)

Comment by Nick Gill

2013-04-23T13:06:22Z

Are you talking about 2-designs here? Or λ-designs? And when you say "can lines in projective space form a resolvable design?" do you mean the design formed by the set of all lines and all points? This is certainly not resolvable when we're in the projective plane... I'd have to think some more about higher dimensions.

Comment by Nick Gill

2013-04-22T09:06:13Z

@unknown, yes there is. Suppose you've got a set of permutations generating the Sylow 2-subgroup of $S_{2^{r-2}}$. Write two copies of these, one as permutations on $[1, 2^{r-2}]$ and the other on $[2^{r-2}+1, 2^{r-1}]$. Add the permutation $(1,2^{r-2}+1)(2,2^{r-2}+2)\cdots$. This generates a wreath product on $[1,2^{r-1}]$ and you're done.

Comment by Nick Gill

2013-04-18T10:49:29Z

@Jan, good point! The $C_4\times C_4$ subgroups of $Q\times Q$ aren't all normal. In any case, the classification given in the wikipedia article includes some infinite groups, so the question is answered.

Comment by Nick Gill

2013-04-18T10:13:04Z

This should generalize easily to infinite groups, right? Just take a direct sum of an infinite number of quaternion groups...

Comment by Nick Gill

2013-04-18T09:58:50Z

$G$ is dihedral of order $2n$. I don't think this is a counter-example in general - only the center normalizes all the subgroups of order $2$.