Skip to content

A Dumb Group Theory Question

November 10, 2018


A question on finite simple groups

Cropped from Schock Prize src

Michael Aschbacher is a professor of mathematics at Caltech. He was a leading figure in the classification of finite simple groups (CFSG).

Today Ken and I ask a simple question about proofs that appeal to CFSG.

The CFSG was originally announced in 1983 amid articles totaling tens of thousands of journal pages. The case of “quasithin” groups was however found to be incompletely analyzed, and it took until 2004 to close it in papers by Aschbacher with Stephen Smith. In a survey for AMS Notices that same year, Aschbacher reviewed what that means for confidence in the whole classification.

Here we are not playing on any doubt about the proof. Instead we focus on its power: What simply-stated facts about groups can one obtain using CFSG that are unknown without it, or known only in weaker forms? We could go through a whole book by Smith on applications of CFSG, but we’ll just choose one kind of example about hw many elements are needed to generate a group.

Generation Of Groups

Generation of a group is connected closely with elementary approaches to group isomorphism.

Definition 1 For {G} a finite group let {d(G)} be the cardinality of the smallest generating set of {G}.

It is easy to prove that {D(G)} is at most {\log_{2}(n)} for any group of order {n}. Adding any new generator {g} at least doubles the size of the group through the products of {g} with existing elements. The {\log_{2}(n)} bound is tight for the abelian group {\mathbb{Z}_2^n}. For simple groups in contrast we have:

Theorem 2 Assuming CFSG, if {G} is a simple group, then {d(G) \le 2}.

If the group {G} is an abelian simple group then {D(G)=1}. The above theorem was a longstanding conjecture, and is only proved now by using the CFSG. The proof is quite direct: For each type of family of non-abelian simple groups, one must check that they are all {2}-generated.

Without CFSG

I wondered the other day could if we prove something non-trivial about the generation of simple groups without the CFSG. The best I could see quickly is:

Theorem 3 Let {G} be a non-abelian simple group of order {n}. Then {G} is generated by at most

\displaystyle  0.5\log_{2}(n)

elements.

Of course this does not use the CFSG. It beats the “trivial” bound {\log_{2}(n)} by a factor of 2 in the case of simple groups.

Proof: Now {G} must have an element {x} of order at least {5}. This follows since a group with only order divisible by {2} and {3} is not simple unless it is abelian. Then, we argue that {G} is generated by the conjugates of {x}. \Box

Lemma 4 Suppose that {H} is a subgroup of {G}. Also suppose that {y^{p}=1} and {y} is not in {H} and {p} is a prime. Then

\displaystyle  \langle H,y \rangle

has cardinality at least {p|H|}.

Proof: Of course {\langle H,y \rangle} is a subgroup of {G} that contains {H}. We claim that the cosets

\displaystyle  y^{k}H

for {k=0,\dots,p-1} are all distinct. Suppose that

\displaystyle  y^{i}H = y^{j}H.

Then {y^{i-j}} is in {H}. But since {p} is a prime this implies the lemma. \Box

More Bounds Without CFSG?

The CFSG is also used to give bounds on generators for general groups. In a case of simultaneous discovery of a theorem 29 years ago, Andrea Lucchini proved and Robert Guralnick also proved the following theorem:

Theorem 5 (CFSG) For any finite group {G} and prime {p}, if each Sylow-{p} subgroup {H} has {D(H) \leq r} then {D(G) \leq r+1}.

It follows that if {a} is maximum such that {p^a} divides {|G|} for some prime {p}, then {d(G) \leq a+1}. This bound too, however, requires CFSG. What bounds can we obtain without it?

Fast-forwarding to a year ago, Lucchini includes Guralnick as a co-author on work analyzing the graph {\Gamma_G} whose nodes are members of {G} and {(g,h)} is an edge of {g,h} generate {G}. Since the identity is an isolated vertex unless {G} is cyclic, often it is omitted to eave what we’ll call {\Gamma'}. When {G} is finite and simple, not only is {E(\Gamma)} nonempty, but {\Gamma'} is connected and has diameter 2.

The graph also figures into a 2016 paper by Lucchini with Peter Cameron and Colva Roney-Dougal, which has the broad title, “Generating sets of finite groups.” This paper has a lot of interesting computational results and does not seem to lean heavily on CFSG. So it may be a conduit for asking and answering some of our questions about the power of CFSG.

Open Problems

I assume that even without CT there is a much better bound on the generators for a non-abelian simple group. I have yet to find it. So the open problem is to send us a better citation.

Advertisements

Micro Barriers To Diversity

October 30, 2018


And perhaps how to remove them

Cropped from Monash interview src

Elizabeth Croft is Dean of Engineering at Monash University in Australia. She was previously at the University of British Columbia in Canada and was the BC and Yukon Chair for Women in Science and Engineering.

Today Ken and I want to discuss barriers to gender equity in computer science.
Read more…

The Inscribed Square Problem

October 21, 2018


A remark on an open problem with an application of the Lebesgue Density Theorem

[ Toeplitz ]

Otto Toeplitz was a mathematician who made key contributions to functional analysis. He is famous for many things, including a kind of matrix named after him.

Today we discuss one of his conjectures that remains open.
Read more…

London Calling

October 18, 2018


For chess and science: a cautionary tale about decision models

Clarke Chronicler blog source

Marmaduke Wyvill was a British chess master and Member of Parliament in the 1800s. He was runner-up in what is considered the first major international chess tournament, London 1851, but never played in a comparable tournament again. He promoted chess and helped organize and sponsor the great London 1883 chess tournament. Here is a fount of information on the name and the man, including that he once proposed marriage to Florence Nightingale, who became a pioneer of statistics.

Today we use Wyvill’s London 1883 tournament to critique statistical models. Our critique extends to ask, how extensively are models cross-checked?

London is about to take center stage again in chess. The World Championship match between the current world champion, Magnus Carlsen of Norway, and his American challenger Fabiano Caruana will begin there on November 9. This is the first time since 1972 that an American will play for the title. The organizer is WorldChess (previously Agon Ltd.) in partnership with the World Chess Federation (FIDE). Read more…

Watching Over the Zeroes

October 10, 2018


How confident should we be that the Riemann Hypothesis is true?

Composite of src1, src2

Andrew Odlyzko and Herman te Riele, in a 1985 paper, refuted a once widely believed conjecture from 1885 that implies the Riemann Hypothesis. The belief began a U-turn in the 1940s, and by the late 1970s the community was convinced its refutation would come from algorithmic advances to bring the needed computation into a feasible range. Odlyzko and te Riele duly credit advances in algorithms—not mere computing power—for their refutation.

Today we consider reasons for and against a belief in the Riemann Hypothesis (RH), contrast them with the situation for {\mathsf{P = NP}}, and point out that there are numerous conjectures weaker than RH but wide open which an RH claimant might try to crack first.
Read more…

Reading Into Atiyah’s Proof

September 26, 2018


The Todd function method

MacTutor biography source

John Todd was a British geometer who worked at Cambridge for most of his life. Michael Atiyah took classes from him there. He was not Atiyah’s doctoral advisor—that was William Hodge—but he advised Roger Penrose, Atiyah’s longtime colleague at Oxford.

Today Ken and I want to add to the discussion of Atiyah’s proof of the Riemann Hypothesis (RH).
Read more…

Preview of the Atiyah Talk

September 23, 2018


Why the Riemann hypothesis is hard and some other observations.

ICM 2018 “Matchmaking” source

Michael Atiyah, as we previously posted, claims to have a proof that the Riemann Hypothesis (RH) is true. In the second half of a 9:00–10:30am session (3:00–4:30am Eastern time), he will unveil his claim.

Today we discuss what the RH is and why it is hard.
Read more…