G ENERATEA G ROUP S ETSOF E LEMENTSTHAT P AIRWISE

(1)

OUTLINE

S ETS OF E LEMENTS THAT P AIRWISE

G ENERATE A G ROUP

Andrea Lucchini

University of Padova, Italy

Joint work with Attila Maroti

GLAUBERMAN CONFERENCE Chicago, 25 March 2008

(2)

O

1

A

GRAPH ASSOCIATED TO A

2-

GENERATED GROUP

2

F

INITE SIMPLE GROUPS

3

W

HAT CAN BE PROVED FOR ARBITRARY GROUPS

?

4

D

IRECT POWER OF SIMPLE GROUPS

5

A S

UDOKU

G

AME

6

S

OLVABLE GROUPS

(3)

AGRAPH ASSOCIATED TO A2-GENERATED GROUP FINITE SIMPLE GROUPS WHAT CAN BE PROVED FOR ARBITRARY GROUPS? DIRECT POWER OF SIMPLE GROUPS A SUDOKUGAME SOLVABLE GROUPS PROFINITE GROUPS

THE MAIN DEFINITION

GRAPH THEORETICAL TERMINOLOGY

DEFINITIONS

G a finite (non cyclic) group that can be generated by two elements;

µ(G) the largest positive integer m so that there exists a subset X in G of order m, with the property that any distinct pair of elements of X generates G.

(4)

DEFINITIONS

G a finite (non cyclic) group that can be generated by two elements;

µ(G) the largest positive integer m so that there exists a subset X in G of order m, with the property that any distinct pair of elements of X generates G.

EXAMPLE

µ(Alt(5)) = 8. We can consider

X := {(1, 2, 3), (3, 4, 5), (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5), (1, 2, 4, 5, 3), (1, 2, 5, 3, 4), (1, 2, 5, 4, 3)}

(5)

THE MAIN DEFINITION

IN GRAPH THEORETICAL NOTATIONS:

We define a graphΓ(G)on the set of elements of G, connecting two vertices by an edge if they generate G.

µ(G) is theclique numberof Γ(G) (the maximum size of a complete subgraph).

REMARK

µ(G) ≤ χ(Γ(G)), where χ(Γ(G)) is thechromatic numberof Γ(G), i.e the smallest number of colors needed to color the vertices of Γ(G) so that no two adjacent vertices share the same color.

REMARK

If G is a union of m proper subgroups, then χ(Γ(G)) ≤ m (we assign different colors to the different subgroups and a vertex can receive any of the colors associated to the covering subgroups containing

(6)

IN GRAPH THEORETICAL NOTATIONS:

We define a graphΓ(G)on the set of elements of G, connecting two vertices by an edge if they generate G.

µ(G) is theclique numberof Γ(G) (the maximum size of a complete subgraph).

REMARK

µ(G) ≤ χ(Γ(G)), where χ(Γ(G)) is thechromatic numberof Γ(G), i.e the smallest number of colors needed to color the vertices of Γ(G) so that no two adjacent vertices share the same color.

REMARK

If G is a union of m proper subgroups, then χ(Γ(G)) ≤ m. Hence χ(Γ(G)) ≤ σ(G), whereσ(G)is the least integer k such that G is the

(7)

THE MAIN DEFINITION

SUMMARIZING

Γ(G) {x, y } ∈ E(Γ(G)) ⇐⇒ hx, y i = G µ(G) maximum size of a complete subgraph

χ(Γ(G)) the smallest number of colors so that no two adjacent vertices share the same color

σ(G) the least integer k such that G is the union of k proper subgroups

µ(G) ≤ χ(Γ(G)) ≤ σ(G)

(8)

K NOWN RESULTS FOR SIMPLE GROUPS

Let S be a finite nonbelian simple group and letm(S)be the minimal index of a proper subgroup of S.

(Liebeck and Shalev, 1995)There exists a constant c such that for any S we have c · m(S) ≤ µ(S)(Using probabilistic results on the generation of finite simple groups combined with Turán’s Theorem of extremal graph theory).

(9)

K NOWN RESULTS FOR SIMPLE GROUPS

(Liebeck and Shalev, 1995)There is a constant c such that c · m(S) ≤ µ(S) for any finite nonabelian simple group S.

(Blackburn, 2006)If S = Alt(n), n is a sufficiently large integer and n ≡ 2 mod 4, then µ(S) = σ(S) = 2ⁿ⁻².

(10)

K NOWN RESULTS FOR SIMPLE GROUPS

(Britnell, Evseev, Guralnick, Holmes and Maroti, 2007)Let S = PSL(n, q), n ≥ 12. If q is odd or n 6≡ 2 mod 4, then µ(S) = σ(S). In any case ^µ(S)_σ(S) ≥ 1 −_q^q−1n−1 =1 − _m(S)¹ .

(11)

K NOWN RESULTS FOR SIMPLE GROUPS

(Britnell, Evseev, Guralnick, Holmes and Maroti, 2007)Let S = PSL(n, q), n ≥ 12. If q is odd or n 6≡ 2 mod 4, then µ(S) = σ(S). In any case ^µ(S)_σ(S) ≥ 1 −_q^q−1_n₋₁ =1 − _m(S)¹ . If S = Sz(q), then µ(S)/σ(S) = 1 − 1/m(S).

(12)

In general, it seems interesting to investigate the quotient µ(S)/σ(S) for a finite nonabelian simple group.

QUESTION

Is it true that

µ(S)

σ(S) → 1 as |S| → ∞ ? Does there exist a universal constant c such that

µ(S)

σ(S) ≥ 1 − c m(S) for all nonabelian finite simple groups S?

(13)

W HAT ABOUT ARBITRARY FINITE GROUPS ?

No result is known about µ(G) when G is an arbitrary finite 2-generated group.

QUESTION

For simple groups the numbers µ(G), χ(Γ(G)) and σ(G) are not too different and coincide in many cases. Does something similar hold for any finite (non cyclic) 2-generated group?

(14)

Thecrownsof a group play a relevant role in the discussion of problems about generation.

DEFINITIONS

LetLbe the set of the monolithic primitive epimorphic images L of G.

For L ∈ L and t ∈ N definethe crown based powerof size t:

Lt = (l1, . . . ,lt) ∈L^t

l1≡ · · · ≡ l_t mod soc L . LetRbe the set of normal subgroups R of G, minimal with respect to the property G/R ∼= Lt for some L ∈ L and t ∈ N.

PROPOSITION

x1, . . . ,xµpairwise generate G if and only if x1R, . . . , xµR pairwise

(15)

QUESTION

Assume that L is a 2-generated monolithic primitive group and define τ = τ (L)as the largest t with the property that Lt is 2-generated.

Compare µ(L) and µ(Lτ).How much smaller is µ(Lτ)than µ(L)?

(16)

D IRECT POWER OF SIMPLE GROUPS

If L is a finite nonabelian simple group, thenLτ=L^τ whereτis the number of the Aut(L)-orbits on the set of the generating pairs of L.

QUESTION

It is easy to prove that σ(L) = σ(L^τ); what about µ(L^τ)?

REMARK

Let {(xi,yi) |1 ≤ i ≤ τ } be a set of representatives for the orbits of Aut(L) on the set of the generating pairs of L;

define x := (x₁, . . . ,xτ) ∈L^τ,y := (y₁, . . . ,yτ) ∈L^τ. L^τ= h¯x , ¯y i ⇔ (¯x , ¯y ) = (x , y )^γ∃γ ∈ Aut(L^τ).

The non isolated vertices of Γ(L^τ)are the elements of the setΩof

¯

(17)

µ(L^τ)is the clique number of ¯Γand can be estimated using:

PROPOSITION

If X is a clique and Y a coclique in a vertex-transitive graph on m vertices, then |X ||Y | ≤ m.

If M is a proper subgroup of L, then {(l1, . . . ,lτ) ∈ Ω |l1∈ M} is a coclique in ¯Γ.

THEOREM

Define PMas the conditional probability that (l1,l2) ∈M × L, given that hl1,l2i = L. Then µ(L^τ) ≤1/PM.

COROLLARY

There exists a constant c such that for any nonabelian simple group L we have

(18)

REMARK

If n ≡ 2 mod 4 and n is large enough then σ(Alt(n)^τ) = σ(Alt(n)) = 2ⁿ⁻²;

µ(Alt(n)^τ) ≤cn.

Hence in general µ(L^τ)is much smaller than σ(L^τ).

QUESTIONS

How sharp is our upper bound for µ(L^τ)?

µ(G) ≥ 3 for any 2-generated finite group. Does there exist a non abelian simple group L with µ(L^τ) >3?

What about the chromatic number of Γ(L^τ)?

(19)

A S UDOKU G AME

µ(Alt(5)) = 8 and σ(Alt(5)) = 10.

G = Alt(5)¹⁹is the largest 2-generated direct power of Alt(5).

REMARK

If µ(Alt(5)¹⁹) ≥n, then there exists a n × 19 matrix, whose entries are elements of Alt(5), such that

the n elements in each column pairwise generate Alt(5);

if l1 l2

m1 m2

is a 2 × 2 submatrix, then (l1,m1)and (l2,m2)are not Sym(5)-conjugate.

(20)







5 3 5 5 5 3 3 2 5 5 5 2 2 3 5 5 5 3 3

5 3 3 5 3 5 5 3 2 5 2 5 5 2 3 5 3 5 5

∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗







The first two rows of the matrix are known (their columns are a set of representatives for the 19 Sym(5)-conjugate classes of generating pairs). The other rows must contain elements of a given order in the same proportion: 10 element of order 5, 6 elements of order 3, 3 elements of order 2.

A column contains at most two entries of order 3, and the elements of order 3 must be positioned in such a way that no 2 × 2 submatrix contains only elements of order 3. This implies

(21)

QUESTION

Decide whether µ(Alt(5)¹⁹) =3 or µ(Alt(5)¹⁹) =4.

µ(Alt(5)¹⁹=4 if and only if we can construct a matrix with the requested properties and where the orders of the elements are distributed in one of the two following way:







5 3 5 5 5 3 3 2 5 5 5 2 2 3 5 5 5 3 3

5 3 3 5 3 5 5 3 2 5 2 5 5 2 3 5 3 5 5

5 5 5 3 3 5 3 5 5 3 3 5 3 5 5 2 2 5 2

5 5 3 3 5 3 5 5 3 2 5 3 5 5 2 3 5 2 5













5 3 5 5 5 3 3 2 5 5 5 2 2 3 5 5 5 3 3

5 3 3 5 3 5 5 3 2 5 2 5 5 2 3 5 3 5 5

5 5 5 3 3 5 3 5 5 3 3 5 3 5 5 2 2 5 2







(22)

S OLVABLE GROUPS

In the case of solvable groups the precise value of σ(G) is known:

THEOREM(TOMKINSON1997)

Let G be a finite non-cyclic solvable group and let H/K be the smallest chief factor of G having more than one complement in G.

Then σ(G) = |H/K | + 1.

We want to study the relationship between µ(G) and σ(G) when G is a 2-generated solvable group. We start by considering the crown based power.

(23)

DEFINITIONS AND USEFUL REMARKS

Assume that L is a 2-generated solvable primitive group:

L = V o H, with H an irreducible subgroup of GL(V ).

LetF =EndH(V ),r = |EndH(V )| :

Lt=V^to H is 2-generated if and only if t ≤ r .

L_r =V^r o His the largest 2-generated crown based power of L.

We may identify H with a subgroup of GL(r , F ).

H = hX₁,X₂i ⇒ rank Ir − X₁ Ir− X₂ = r .

W ∈ V^r can be viewed as a r × r matrix with coefficients over F . PROPOSITION

Assume W₁,W₂∈ V^r and H = hX₁,X₂i:

L =V^r X ,W X i ⇔ detIr − X₁ Ir− X₂ 6= 0.

(24)

The study of the behavior of the crown based power is reduced to the following:

ALINEAR ALGEBRA QUESTION

Assume that Z1, . . . ,Zµare matrices in Mr ×r(F ) with the property that rank Zi Zj = r ∀i 6= j.

Can we find Y1, . . . ,Yµ∈ M_{r ×r}(F ) such that detZi Zj

Yi Yj

6= 0 ∀i 6= j ?

(25)

AN EASY EXAMPLE

Assume that X1, . . . ,Xµ pairwise generate H and that Xi− X_j is a non-singular matrix whenever i 6= j. Then

det1 − X_i 1 − X_j I_r I_r

=det1 − X_i X_i− X_j

I_r 0

6= 0;

we may take Y₁= · · · =Y_m=I_r and deduce thatµ(L_r) ≥ µ.

(26)

LEMMA

Assume that H is a 2-generated irreducible nilpotent subgroup of GL(V ). If L = V o H and r = dimEndH(V )V , then µ(Lr) = µ(L).

THEOREM

If G is a non cyclic 2-generated solvable group of Fitting length at most 2, then µ(G) = χ(Γ(G)) = σ(G).

QUESTION

Does there exist a 2-generated solvable group with µ(G) 6= σ(G)?

(27)

G ENERALIZATIONS TO PROFINITE GROUPS

DEFINITIONS

Let G be a profinite group that can be (topologically) generated by d ≥ 2 elements:

we denote byµ_d(G)the largest integer m with the property that there exists an m-tuple of elements of G such that any d distinct entries together (topologically) generate G.

LEMMA

If the non-cyclic group G can be generated by 2 elements, then (d − 1)µ₂(G) ≤ µ_d(G) ≤ (d − 1)σ(G).

(28)

LEMMA

µ₂(SL(2, Z)) = σ(SL(2, Z)) = 4;

µ_d(SL(2, Z)) = 4(d − 1) = µd(SL(2, Z/2Z)).

QUESTION

Is it true that µd(SL(n, Z)) = µd(SL(n, Z/2Z)) for all integers n and d greater than or equal to 2?

THEOREM

If n ≥ 12, then the following three statements are true.

1 µ_d( \SL(n, Z)) = µd(SL(n, Z/2Z)).

2 σ(SL(n, Z)) = σ( \SL(n, Z)) = σ(SL(n, Z/2Z)).

(29)

REMARK

LetG =SL(n, Z).\ Whenever n ≥ 3, d ≥ 2 and d ≤ k ≤ µd(G), the probability is positive that a randomly chosen k -tuple with entries from G has the property that any d entries will together generate G.

Let G be a profinite group that can be generated by d elements;

let ν be the normalized Haar measure on G (or on some direct power G^t);

for any k ≥ d , let Ω(G, k , d ) be the set of k -tuples of elements of G with the property that every d distinct entries generate G;

let P(G, k , d ) = ν(Ω(G, k , d )) and P(G, d ) = P(G, d , d ).

THEOREM