Ore’s Conjecture and Computational Group Theory

Ore’s Conjecture and Computational Group Theory Final Degree Dissertation Degree in Mathematics Xabier de Juan Soriano Supervisor: Matteo Vannacci Leioa, June 22, 2023 Contents Symbols v Introduction vii 1 The classical groups 1 1.1 Iwasawa’s lemma ......................... 1 1.2 Linear groups ........................... 2 1.3 Bilinear forms ........................... 5 1.3.1 Definitions ........................ 5 1.3.2 Classification of alternating forms ........... 6 1.3.3 Classification of conjugate-symmetric sesquilinear forms 6 1.3.4 Classification of symmetric forms in odd characteristic 7 1.4 Symplectic groups ........................ 10 1.5 Unitary groups .......................... 14 1.6 Orthogonal groups in odd characteristic ............ 15 1.7 Orthogonal groups in characteristic 2 .............. 16 2 Character theory 19 2.1 Ore’s criterion ........................... 19 2.2 Computing character tables ................... 21 3 Ore’s conjecture 29 3.1 Generalizations .......................... 29 3.2 Alternating groups ........................ 29 3.3 Testing Ore’s conjecture ..................... 33 3.4 Testing Ore’s conjecture probabilistically ............ 34 3.5 Experimental results and final discussion ............ 35 A Exercises 41 A.1 Exercises from Chapter 1 .................... 41 A.2 Exercises from Chapter 3 .................... 43 B Source code 45 iii Symbols SnSymmetric group on nelements. AnAlternating group on nelements. |g|Order of the element g. ghConjugate h−1gh. hSiGNormal closure of a subset Sof a group G. ClG(g)Conjugacy class of gon a group G. CG(S)Centralizer of a subset Sof a group G. K(G)Set of all commutators of a group G. G0Derived subrgoup of G. xϕ or (x)ϕImage of xby the homomorphism ϕ. fg The composition of maps where we apply first fand then g. CGC-group algebra of the group G. IrrGSet of complex irreducible characters of G. FqFinite field of prime-power order q. k×Group of units of the field k. ATTranspose of the matrix A. trATrace of the matrix/linear map A. Ai,:i-th row of the matrix A. v[i]i-th component of the vector v. Mn(k)Algebra of n×nmatrices over a field k. Inn×nidentity matrix. diag(λ1, . . . , λn)Square diagonal matrix with the elements λ1, . . . , λnon the main diagonal. MB(f)Matrix representation by rows of the linear map fw.r.t. the basis B. V∗Dual space of V. (n, m)Greatest common divisor of nand m. ≡nCongruence mod n. 1AIdentity map on the set A. v Introduction A group is said to be simple if its only normal subgroups are the trivial one and the group itself. The finite simple groups play a crucial role in understanding finite groups as they can be thought of as their “basic building blocks”. The study of simple (non-abelian) groups can be dated back to the early 19th century, when Évariste Galois studied the simple group A5. He also constructed the simple groups PSL2(p)for primes p⩾5. This construction can be found in his last letter, addressed to his friend Auguste Chevalier1. There was not much progress in the theory of finite simple groups until the end of the 19th century. In 1870, Camille Jordan constructed in [Jor70] four families of simple matrix groups over the fields Fpof prime order. The beginning of the 20th century saw the creation of a well-developed theory of the finite groups. During the early 1960s, serious efforts to classify finite simple groups began. However, this task turned out to be much more challenging than what some people initially anticipated. Finally, in 2004 the classification of all finite simple groups was completed [Wil09]. The proof, which involved the collaboration of about 100 authors, consists of tens of thousands of pages spread over a hundred journal articles. This result is considered a milestone of twentieth-century Mathematics. Classification Theorem for Finite Simple Groups. Every finite simple group is isomorphic to one of the following: •a member of one of three infinite classes: (i) a cyclic group Cpof prime order p; (ii) an alternating group An, when n⩾5; (iii) a group of Lie type: 1It was written on May 29, 1832, one day before his fatal duel, at the age of 20. It is considered his testament as a mathematician. Galois asks Chevalier to publicly ask Jacobi or Gauss to give their opinion, not on the truth, but on the importance of the theorems that he has found in the letter, and to have the letter printed in the Revue encyclopédique. The letter was published in September 1832. vii viii –a classical group: linear: PSLn(q), n ⩾2,except PSL2(2) and PSL2(3); unitary: PSUn(q), n ⩾3,except PSU3(2); symplectic: PSp2n(q), n ⩾2,except PSp4(2); orthogonal: PΩ2n+1(q), n ⩾3, q odd; PΩε 2n(q), n ⩾4, ε ∈ {+,−} where qis a prime power; –an exceptional group of Lie type, G2(q), q ⩾3;F4(q);E6(q);2E6(q);3D4(q);E7(q);E8(q) where qis a prime power, or 2B2(22n+1);2G2(32n+1); 2F4(22n+1) where n⩾1, or the Tits group 2F4(2)0. •one of the 26 sporadic simple groups: (i) a Mathieu group M11,M12,M22,M23,M24; (ii) a Leech lattice group Co1,Co2,Co3,McL,HS,Suz,J2; (iii) a Fischer group Fi22,Fi23,Fi0 24; (iv) a Monstrous group M,B,Th,HN,He; (v) a pariah J1,J3,J4,O’N,Ly,Ru. In a group, the commutator of two elements xand yis defined as [x, y] = x−1y−1xy. In 1951, Øystein Ore dealt with commutators in [Ore51], where he proved that, if n⩾5, every permutation of Anis a commutator of two permutations of Sn. He also affirmed that the proof could be extended to show that in Anevery element is a commutator. In the final part of the same article he stated the following: “It is possible that a similar theorem holds for any simple group of finite order, but it seems that at present we do not have the necessary methods to investigate the question.” This has become known as Ore’s conjecture. Through different articles published throughout the 20th century, Ore’s conjecture was established by many authors for different families of finite simple groups. For instance, Noboru Ito proved the conjecture for the simple alternating groups in [Ito51]. In [NPC84], Ore’s conjecture was checked directly using computational methods for the sporadic groups. Several authors obtained partial results for finite simple groups of Lie type [Mal14]. In 1998, an important breakthrough was made by Erich Ellers Introduction ix and Nikolai Gordeev in [EG98], where they established Ore’s conjecture for groups of Lie type over a finite field Fq, if q⩾8. Finally, in 2009 the remaining cases (groups of Lie type over Fqwith q < 8) were proved in [LOST]. Combining this and the classification of the finite simple groups, Ore’s conjecture was finally proven. Main Theorem. If Gis a finite non-abelian simple group, then every element of Gis a commutator. In fact, in [LOST] a more general result was proved for the classical groups than Main Theorem. It was shown that in every quasisimple (perfect group Gsuch that G/Z(G)is simple) classical group every element is a commutator. Now, we give a rough idea of the strategy used in [LOST] to prove the conjecture. A dichotomy is established between elements with “small centralizer” and the rest. For an element with small centralizer, DeligneLusztig theory and the theory of dual pairs and Weil characters of classical groups are used to show that such an element is a commutator. On the other hand, for a fixed element whose centralizer is not small, the strategy consists of reducing to groups of Lie type of lower dimension and apply induction. For instance, for symplectic or orthogonal groups, it is possible to write such an element as a Jordan decomposition into several Jordan blocks. Therefore, this element lies in direct product of smaller symplectic or orthogonal groups. Hence, if one can inductively express each block as a commutator in a lower rank classical group, then the fixed element is a commutator. However, for the unitary groups, the inductive strategy using Jordan blocks does not work well, and therefore M. Liebeck et al. adopt a different approach. This dissertation arises from [LOST, Lemma 3.1], which we state and name as Main Lemma. This lemma serves as the base of the induction of the proof of the Main Theorem. Main Lemma. Every element of each of the following groups is a commutator: (i) Sp2m(2),3⩽m⩽6; (ii) Sp2m(3),2⩽m⩽5; (iii) SU3(q),3⩽q⩽17;SU4(q),q⩽7;SU5(q),q⩽4;SU6(q),q⩽4; SU7(2); (iv) Ω± n(2),8⩽n⩽12;Ω± n(3),7⩽n⩽11;Ω7(5); (v) simply connected D4(q),q⩽4;2D4(q),q⩽5; (vi) E6(2) or simply connected 2E6(2). 61.3. Bilinear forms f(u, v)for all u, v ∈V. Two forms on Vare said to be equivalent if they become equal after a change of basis. 1.3.2 Classification of alternating forms Before classifying the alternating forms, we will see that there are no spaces of odd dimension equipped with an alternating bilinear form. Theorem 1.3.1. Let (V, f)be a non-singular alternating bilinear space. Then dim Vis even. Proof. By induction on dim V. If dim V= 1 with basis {v}, then since fis an alternating form f(λv, µv) = λµf(v, v)=0. This contradicts the hypothesis of non-singularity. If dim V= 2 we get the desired result, so suppose that dim V⩾3. Take v∈V− {0}. Since fis non-singular, there exists w∈Vsuch that f(v, w)=1and that W=hv, wiis of dimension 2. The matrix of f|W with respect to the basis {v, w}is 0 1 −1 0 , which is invertible. Hence, the restriction f|Wis non-singular. Therefore, V=W⊕W⊥and W⊥is also non-singular. By induction hypothesis dim W⊥is even and thus dim Vso is. Let (V, f)be a non-singular alternating bilinear space. In the proof of Theorem 1.3.1 we have seen that for every non-zero vector v∈Vwe can find w∈Vsuch that: f(v, w)=1;V=W⊕W⊥, where W=hv, wiis of dimension 2; and both f|Wand f|W⊥are non-singular. The pair (v, w) is called a hyperbolic pair. By induction one can easily show that there is a basis {e1, . . . , em, f1, . . . , fm}of Vwith u⊥v= 0 for all basis vectors u, v except f(ei, fi) = −f(fi, ei) = 1. A basis that fulfills such conditions is called a symplectic basis and fis said to be a symplectic form. The matrix of fwith respect to {e1, . . . , fm}is 0Im −Im0. Therefore, up to equivalence, there is only one alternating form on a non-singular alternating bilinear space. 1.3.3 Classification of conjugate-symmetric sesquilinear forms As in the case of the alternating forms, up to equivalence, there is only one conjugate-symmetric sesquilinear form. In fact, we will prove that the matrix of the conjugate-symmetric sesquilinear form with respect to some basis is the identity matrix. Theorem 1.3.2. Let fbe a non-singular conjugate-symmetric sesquilinear form on a Fq2-vector space V. Then there is a basis of Vof mutually perpendicular vectors each of norm 1, i.e. f(v, v) = 1 for all basis vectors v. Such a basis is called an orthonormal basis. Chapter 1. The classical groups 7 Proof. By induction on dim V. For the case V={0}we use the empty basis and the result follows. Now let dim V=n⩾1. We claim that there is a vector vwith f(v, v)6= 0. Otherwise, for any u, w vectors we get that 0 = f(u+λw, u +λw) =f(u, u) + λf(u, w) + λf(w, u) + λλf(w, w) =λf(u, w) + λf(w, u).(1.3) Now choose two values of λthat form a Fq-basis of Fq2. For instance, λ1= 1 and some scalar λ2with λ26=λ2, that is λ2∈Fq2−Fq. Solving the equation (1.3) for these values we conclude that f≡0, which contradicts the hypothesis of non-singularity. Let vbe some vector with f(v, v)6= 0. Then f(v, v) = f(v, v), and f(v, v)is in the fixed field Fqof the field automorphism x7→ xq. Since the multiplicative group of the field is cyclic of order q2−1=(q+ 1)(q−1), there is λ∈Fq2such that λλ =λq+1 =f(v, v). Therefore, define v0=λ−1v, so that f(v0, v0) = 1. Now let Wbe the subspace spanned by v. Since f|Wis non-singular, we get that V=W⊕W⊥, and by induction there is an orthonormal basis of W⊥{v1, . . . , vn−1}. Clearly {v1, . . . , vn−1, v0}is an orthonormal basis of V. 1.3.4 Classification of symmetric forms in odd characteristic The classification of symmetric forms not only does require more work than the previous ones, but also it depends on the characteristic of the underlying field. After some preliminaries, we will be able to answer the equivalence question for finite fields of odd characteristic. Assume for the rest of this section that kis a field of odd characteristic and that Va finite dimensional k-vector space. Suppose that fis a symmetric form on V, then define Q:V→kas Q(v) = f(v, v), and call Qthe associated quadratic form. Observe that Q(λv) = λ2Q(v)for all λ∈kand v∈V, and that for all u, v ∈V Q(u+v) = f(u+v, u +v) = Q(u)+2f(u, v) + Q(v).(1.4) Therefore, since char k6= 2, we have that f(u, v) = 1 2(Q(u+v)−Q(u)−Q(v)), i.e. the quadratic form Qcompletely determines the bilinear form f. Theorem 1.3.3. Let fbe a symmetric bilinear form on V, then Vhas an orthogonal basis B={v1, . . . , vn}. That is, there are some λi6= 0 with MB(f) = diag(λ1, . . . , λr,0,...,0). Furthermore, {vr+1, . . . , vn}is a basis of radf; and for every 1⩽i⩽r,vican be replaced by civifor every ci∈k× and each λican be any non-zero field element in the image of the restriction of Qto hv1, . . . , vi−1i⊥. 81.3. Bilinear forms Proof. Assume that f6= 0, as otherwise the theorem trivially holds in that case. The proof is by induction on n= dim V. The case n= 1 is trivial, so suppose that n⩾2. First note that Q(v1)6= 0 for some v1∈V. Otherwise, by (1.4) we would have f(u, v)=0for all u, v ∈V, a contradiction since f6= 0. Define W=hv1iso Wis non-singular. Hence, V=W⊕W⊥. By induction, W⊥has an orthogonal basis {v2, . . . , vr}such that Q(vi) = λi6= 0 when 2⩽i⩽rand Q(vi)=0if r+ 1 ⩽i⩽n, for some r. Hence, the equality MB(f) = diag(λ1, . . . , λr,0,...,0) is clear. If v∈Vthen v∈radfif and only if v⊥vifor every i. Suppose that v=Piaivi, therefore if j > r,f(v, vj)=0, and f(v, vj) = ajλjotherwise. Hence, v∈radfif and only if aj= 0 for 1⩽j⩽r, or equivalently v∈ hvr+1, . . . , vni. Since Q(civi) = c2 iλi, every vican be replaced by civifor every ci∈k×. The other fact is immediate recalling the main proof of the theorem. We now define some concepts that will be useful in what follows. If fis a symmetric form on V, then v∈V− {0}is called isotropic if Q(v)=0; otherwise is called anisotropic. For technical reasons, v= 0 is taken to be anisotropic. If there exists an isotropic vector then f,Vand Qare called isotropic; otherwise are called anisotropic. A totally isotropic subspace of V is a subspace on which all non-zero vectors are isotropic. The form fand the quadratic form Qare called universal if Q(V) = k, i.e. Qis a surjective map. Proposition 1.3.4. Every non-singular isotropic symmetric bilinear form is universal. Proof. Let fbe any non-singular isotropic symmetric bilinear form. Take an isotropic vector u∈V−{0}. Since fis non-singular, there is some w∈V with f(u, w) = λ6= 0. We can replace wby w 2λso that f(u, w)=1/2. Define v=cu +w, where c∈kwill be determined later. Then, as uis isotropic, Q(v) = f(cu +w, cu +w)=2cf(u, w) + f(w, w) = c+f(w, w). Finally, for a∈k, set c=a−f(w, w). Therefore Q(v) = a−f(w, w) + f(w, w) = a. Suppose now that k=Fq, where qis a power of an odd prime. Let k×2 denote the subgroup of squares in the multiplicative group k×. The map θ:k×→k×given by x7→ x2is a group homomorphism and kerθ={±1}. Hence, |k×:k×2|= 2 and the two cosets correspond to the squares and the non-squares in k×. If b∈k×is a non-square, denote by Kthe splitting field of the polynomial x2−b, so [K:k]=2and |K|=q2. Therefore, we may write Chapter 1. The classical groups 9 K={a+c√b|a, c ∈k}. Moreover, as the map x7→ xqgenerates the Galois group Gal(K/k)∼ =C2, the field norm is given by NK/k(a+c√b) = Y σ∈Gal(K/k) σ(a+c√b)=(a+c√b)q+1. Note that the restriction N:= NK/k :K×→k×is a homomorphism and that ker N={α∈K|αq+1 = 1}, which is the unique subgroup of order q+1 of K×. Thus, the image of Nhas order q2−1 q+1 =q−1, i.e. Nis surjective. In general, if fis a symmetric form and λ∈k×, then fλ(u, v) = λf(u, v) is also a symmetric form and Qλ(v) = λQ(v)is the corresponding quadratic form. Observe that fis universal if and only if fλis universal for all λ∈k×. Proposition 1.3.5. Let kbe a finite field and let fbe non-singular symmetric bilinear form on a k-vector space Vof dimension n⩾2. Then fis universal. Conversely, if dim V= 1 then fis not universal. Proof. By Proposition 1.3.4 we can assume that fis anisotropic. Note that it suffices to show only the case n= 2, since every vector space (of dimension n⩾2) has a subspace of dimension 2, and applying the proof to this particular subspace the claim will follow. By Theorem 1.3.3 we may assume that there is an orthogonal basis B={v1, v2}for which MB(f) = diag(α, −β), where both αand βare non-zero; and by scaling the form we may assume that α= 1. Let v= av1+bv2be any non-zero vector of V, then Q(v) = a2−βb26= 0 because fis anisotropic. Hence, βis a non-square in k, so we consider K=k(√β). From the definition of the field norm NK/k we have that NK/k(a+b√β) = a2−βb2 and thus NK/k(a+b√β) = Q(v). Finally, by the discussion before this theorem we know that NK/k :K×→k×is surjective and consequently Qis surjective. Suppose now that dim V= 1. Recall that Q(λv) = λ2Q(v)for all λ∈k and v∈V. Therefore, one of the following must occur: Q(V)⊆k×2(kor Q(V)⊆c·k×2(k, where cis a non-square of k. Theorem 1.3.6. Let kbe a field of odd order and let fbe a non-singular symmetric bilinear form on a k-vector space Vof dimension n⩾2. Then there is a basis of Vwhich the matrix with respect to fequals diag(1,...,1, d), for some d∈k×. Proof. By Theorem 1.3.3 and Proposition 1.3.5 we know that there is some v1∈Vwith Q(v1)=1. By these same results we can continue choosing vectors viin an orthogonal basis, where Q(vi)=1, as long as hv1, . . . , vi−1i⊥ has dimension greater or equal than 2. This can be done for all 1⩽i⩽n−1. When i=nuniversality is no longer guaranteed, so vnis chosen as a vector from hv1, . . . , vn−1i⊥(which may have dimension 1, so we cannot apply Proposition 1.3.5) with Q(vn) = d6= 0, as in the proof of Theorem 1.3.3. 10 1.4. Symplectic groups Therefore, there are exactly two equivalence classes of non-singular symmetric bilinear forms over fields of odd order: the ones which have a matrix as in the theorem above with d= 1, and those which have such a matrix with d=a, where ais some non-square. Note that these two types are not equivalent, one has determinant 1, which lies in the coset of squares and the other has determinant a, which lies in the other coset. Before defining forms of plus type and minus type, we will give an example to motivate these definitions. Suppose that dim V= 2. Let f1and f2be two symmetric forms given with respect to an orthogonal basis {x, y}by f1(x, x) = f1(y, y), and f2(x, x)=1, f2(y, y) = dfor some non-square scalar d. If −1is a square in k(write −1 = i2), then f1(x+iy, x +iy)=0and f2(x+λy, x +λy) = 1 + λ2d, which cannot be 0 (otherwise, d=−λ−2= (λ−1i)2, which is impossible). Alternatively, when −1is not a square, −dis a square (write −d=λ−2for some λ∈k×), so f2(x+λy, x +λy) = 0 and f1(x+λy, x +λy)6= 0. It is well known that −1is a square in Fqif and only if q≡41. Hence, there is a non-zero isotropic vector for f1if and only if q≡41. Moreover, there is a non-zero isotropic vector for f2if and only if q≡43. Therefore, we say that a form is of plus type if there is an isotropic vector; otherwise we say that is of minus type. In general, a form in 2mdimensions is said to be of plus type if there exists a totally isotropic subspace of dimension m; otherwise is called of minus type. The Witt index of the form is defined as the maximal dimension of a totally isotropic subspace. It can be shown that when the form is of plus type the Witt index equals mand the forms with minus type have Witt index m−1[Wil09, p. 59]. 1.4 Symplectic groups The symplectic group4Sp(V, f)is defined as the isometry group of a symplectic form (non-singular alternating) fon a vector space V∼ =F2m q(when the form fis clear from the context, we simply write Sp(V)). In other words, Sp(V, f)is the subgroup of GL(V)that consists of elements gsuch that f(ug, vg) = f(u, v)for every u, v ∈V. If his another symplectic form on V, by the classification of alternating forms, hand fare equivalent. Hence, the resulting symplectic group respect to his conjugate to Sp(V, f)in GL(V). Equivalently, relative to appropriately chosen bases, Sp(V, f)and Sp(V, h) are isomorphic to a subgroup of GL2m(q). This resulting group of matrices is denoted by Sp2m(q), and by the classification of alternating forms it can 4This term is due to H. Weyl, who replaced the previous confusing name “complex group”, as these groups have nothing to do with complex numbers. As a curiosity, the term “symplectic” comes from the Greek word symplektikos, which is the Greek cognate of “complex”. Chapter 1. The classical groups 11 be easily shown that Sp2m(q) = nX∈GL2m(q)|XT0Im −Im0X=0Im −Im0o.(1.5) The centre Zof Sp2m(q)consists of the matrices I2mand −I2mif charFq6= 2, and Z={I2m}if char Fq= 2. The quotient group Sp2m(q)/Z is called the projective symplectic group and is denoted as PSp2m(q). In Exercise A.1.2 we compute the orders of these groups. We start by considering the symplectic groups when m= 1. By (1.5), a simple computation yields that a b c d ∈Sp2(q)if and only if ad −bc = 1. Thus, Sp2(q) = SL2(q). From now on in this section, Vwill be a Fq-vector space of dimension 2m and fwill be symplectic form on V. After proving some technical results we will be ready to apply Iwasawa’s lemma to PSp2m(q). Lemma 1.4.1. Let v∈Vand ϕ∈V∗. A transvection Tv(ϕ)is in Sp(V, f) if and only if ker ϕ=v⊥. In that case there is λ∈Fqsuch that xTv(ϕ) = x+λf(x, v)v.Tv(ϕ)is called a symplectic transvection and we write Tv(λ) instead of Tv(ϕ). Proof. τ=Tv(ϕ)is symplectic if and only if f(x, y) = f(xτ, yτ) = f(x, y) + yϕf(x, v) + xϕf(v, y) + f(v, v). The equation above is equivalent to yϕf(x, v) + xϕf(v, y)=0.(1.6) Suppose this holds and let w∈Vbe such that f(v, w)6= 0, which exists since fis non-singular. Then wϕf(x, v) + xϕf(v, w) = 0, and hence xϕ = −wϕ f(v,w)f(x, v) = λf(x, v)and λ∈Fqis independent of x. It is clear that in this case ker ϕ=v⊥. For the converse, if kerϕ=v⊥= ker f(·, v), there is λ such that xϕ =λf(x, v). Clearly (1.6) holds (fis an alternating form), and hence τis symplectic. Proposition 1.4.2. Let Tv(λ)and Tv(µ)be symplectic transvections. Then: (i) Tv(λ)Tv(µ) = Tv(λ+µ), (ii) Tµv(λ) = Tv(λµ2), (iii) Tv(λ)−1=Tv(−λ), (iv) Tv(λ)g=Tvg(λ)for any g∈Sp(V). Proof. Easy computation. Lemma 1.4.3. The subgroup Sgenerated by all symplectic transvections equals Sp(V). 12 1.4. Symplectic groups Proof. Part 1: Sacts transitively on V2−{(0,0)}. Let v, w be two distinct non-zero vectors. If f(v, w) = λ6= 0, then vTv−w(λ−1) = w. Otherwise, f(v, w) = 0. We aim to find an xsuch that f(v, x)6= 0 6=f(w, x). Such xexists because if not, there exist y, z such that f(v, y) = 0 = f(w, z)and f(v, z)6= 0 6=f(w, y). With this in mind, we see that a suitable linear combination of yand zhas the required properties. Now, we can construct T1and T2symplectic transvections such that vT1=z and zT2=w. Hence, we can map vto zand zto w. Part 2: Sacts transitively on the set of hyperbolic pairs. We have to show that there is a product of transvections which maps {ei, fi}to {ej, fj}. By Part 1, there is a transvection T1mapping eito ej. If we find a transvection T2such that fiT1T2=fjand ejT2=ej, then the claim is proven. We divide into two cases. If f(fiT1, fj) = λ6= 0, by Part 1, defining T2=TfiT1−fj(λ−1)we get fiT1T2=fjand since f(ej, fiT1−fj) = f(ei, fi)−f(ej, fj)=0,ejT2=ej, as we wanted. Now suppose that f(fiT1, fj) = 0. In this case f(fiT1, ej+fiT1) = −1. Moreover, f(ej+f1T1, fj) = f(ej, fj) = λ6= 0. Furthermore, f(ej,−ej) = 0 = f(ej, ej+fiT1−fj). Thus, by Part 1 there exist T2,1=T−ej(−1) and T2,2=Tej+f1T1−fj(λ−1)that both fix ej, and that f1T1T2,1=ej+fiT1and (ej+f1T1)T2,2=fj. Therefore, defining T2as the composition T2,2of T2,1 gives the desired result. Now we are ready to prove that S= Sp(V). We prove this by induction on dim V. When dim V= 2 by Lemma 1.2.1 the result follows since SL2(q) = Sp2(q). Suppose now that dim V > 2. Let (v, w)be a hyperbolic pair and define W=hv, wi. Since for any g∈Sp(V) (vg, wg)is a hyperbolic pair, and by Part 2 there is some T∈Swith vgT =vand wgT =w, then g|WT= 1W. Furthermore, as g|W⊥T∈Sp(W⊥)by induction hypothesis g|W⊥Tis a product of symplectic transvections t1, . . . , tron W⊥. Since V=W⊕W⊥, each tican be extended to a symplectic transvection on V,t0 i. This extension is done in the following way. By Lemma 1.4.1 we have that xti=x+ λf(x, v)vfor some scalar λand v∈W⊥, for every x∈W⊥. Hence, xt0 i=xti for all x∈Vdefines a transvection t0 iin Sp(V)and the equality gT =t0 1. . . t0 r holds. Finally, it follows that g=t0 1. . . t0 rT−1∈S, as desired. Corollary 1.4.4. Sp2m(q)⩽SL2m(q). Proof. Any transvection has determinant 1. Lemma 1.4.5. Sp2m(q)is perfect except when (m, q) = (1,2),(1,3) and (2,2) Proof. By Lemma 1.4.3 it suffices to show that every symplectic transvection is a commutator. We prove this by induction on dim V(V∼ =F2m qas always). Chapter 1. The classical groups 13 We start with the inductive step, when dim V⩾4. Since the conjugate of a commutator is a commutator again, Sp(V)acts on V− {0}transitively and by property iv) from Proposition 1.4.2, it suffices to verify that the transvections Tv(λ), for a fixed vector v, are a commutator for every scalar λ. Let B={e1, . . . , fm}be a symplectic basis of Vand T=Te1(λ)be a symplectic transvection. Clearly W=he2, f2i⩽e1⊥. The restriction τ=T|W⊥belongs to Sp(W⊥), and by induction it is a commutator. Since W⩽e1⊥, we have that T|W= 1W, and therefore Tand the extension of τto Vcoincide, as in the proof of Lemma 1.4.3. Hence, Tis clearly a commutator on Sp(V). Since Sp2(q) = SL2(q)and since in SL2(q)all transvections are commutators when q⩾4(see Lemma 1.2.3 from the previous section), the base of the induction is proven. When q= 2 induction starts at m= 3, and for q= 3 at m= 2. So we need to check that in both Sp4(3) and Sp6(2) every symplectic transvection is a commutator. We prove it in Exercise A.1.3. By Corollary 1.4.4 and recalling Section 1.2 there is an action of Sp2m(q) on the set Ωof 1-dimensional subspaces of Fn q. This action is transitive by Part 1 of the proof of Lemma 1.4.3. Since the kernel of this action coincides with Z(Sp2m(q)),PSp2m(q)acts faithfully and transitively on Ω. Lemma 1.4.6. Sp(V)acts primitively on Ω. Proof. Since SL2(q) = Sp2(q), we may assume that dim V > 1. Let B⊆Ω with |B|>1and either Bg =Bor Bg ∩B=∅for each g∈Sp(V). We need to show that B= Ω. We claim that there are hui,hvi ∈ Bsuch that f(u, v)6= 0. Suppose to the contrary that f(u, v) = 0 for all hui,hvi ∈ B. Choose hui 6=hvi in B. Since fis non-singular, there is x∈Vwith f(u, x) = 1. Hence, (u, x)is a hyperbolic pair and define the plane W=hu, xi. Set H= {g∈Sp(V)|g|W= 1W}. It can be easily shown that H⩽Sp(V). Since V=W⊕W⊥, any g∈Sp(W⊥)extends to g0∈Sp(V)with g0 |W= 1W, and hence Sp(W⊥) = {g|W⊥|g∈H}. Choose w∈W⊥− {0}. Since v∈W⊥, and Sp(V)acts transitively on V− {0}, there is g∈Hwith vg =w. As ug =u, we have that hui ∈ Bg ∩B, so Bg =B. Moreover, hwi=hvig∈B, and recall that wis an arbitrary non-zero vector in W⊥. Since m > 1, W⊥6={0}and there is a hyperbolic pair (y, z)in W⊥. Hence, hyi,hzi ∈ B, but f(y, z)=1, which is a contradiction. Therefore, we choose hui,hvi ∈ Bwith f(u, v) = 1. Hence, (u, v)is a hyperbolic pair. Now, take any hwi ∈ Ω. If f(u, w)6= 0 we can suppose that (u, w)is a hyperbolic pair. By Part 2 of the proof of Lemma 1.4.3, there is g∈Sp(V)with ug =uand vg =w. Since hui ∈ Bg ∩B, then Bg =Band hwi ∈ B. Otherwise, if f(u, w)=0there is x∈Vsuch that f(u, x) = f(w, x)=1. Using the same arguments as in the previous 14 1.5. Unitary groups paragraph, hxi ∈ B, and there is also some g∈Sp(V)with ug =wand xg =x. Once more, B=Bg and hwi=huig∈B. Hence, B= Ω. At this point we are ready to prove the simplicity of PSp2m(q)if (n, q)6= (1,2),(1,3),(2,2). The three cases in which PSp2m(q)is not simple we have the isomorphisms PSp2(2) = PSL2(2) ∼ =S3,PSp2(3) = PSL2(3) ∼ =A4and Sp4(2) ∼ =S6[Wil09, p. 61]. Theorem 1.4.7. The group PSp2m(q)is simple except when (m, q) = (1,2), (1,3) and (2,2). Proof. PSp2m(q)acts faithfully and primitively (by Lemma 1.4.6) on Ω. If hvi ∈ Ω, set H= StabSp2m(q)(hvi). Define N={Tv(λ)|λ∈Fq}. By Proposition 1.4.2,NPHand N∼ =Fq, so Nis abelian. For any g∈Sp2m(q), Ng={Tvg(λ)|λ∈Fq}. Since Sp2m(q)acts transitively on V−{0}, then {Ng|g∈Sp2m(q)}contains all the symplectic transvections. Therefore, by Lemma 1.4.3,Sp2m(q) = hNiSp2m(q). Finally, with the exceptions noted, PSp2m(q)is perfect by Lemma 1.4.5. Apply Iwasawa’s Lemma 1.1.1. 1.5 Unitary groups The (general)unitary group GUn(q)is defined as the isometry group of a non-singular conjugate-symmetric sesquilinear form fon a F2 q-vector space of dimension n. That is, GUn(q)is the subgroup of GLn(q2)consisting of matrices which preserve the form f. Therefore, by the classification of conjugate-symmetric sesquilinear forms it can be easily shown that GUn(q) = nX∈GLn(q2)|XT=X−1o where X= (xi,j)if X= (xi,j). Furthermore, one can show that |GUn(q)|=qn(n−1)/2 n Y i=1 (qi−(−1)i). The subgroup of GUn(q)which consists of matrices of determinant 1 is called special unitary group and is denoted by SUn(q). If Zis the subgroup of scalar matrices, then PSUn(q) = SUn(q)/Z is called the projective special unitary group and most of them are simple. As in the case for the symplectic groups, we have the following isomorphism: SU2(q)∼ =SL2(q). The groups which are not simple are the ones given by the isomorphism PSU2(q)∼ = PSL2(q)and PSU3(2), which is a soluble group of order 72. We check this in Exercise A.1.4 using the GAP system [GAP22]. We simply sketch the proof of the simplicity of the unitary groups. As SU2(q)∼ =SL2(q), we suppose that n > 2. As always, we aim to apply Iwasawa’s Lemma 1.1.1. We consider transvections of the same form as Chapter 1. The classical groups 15 the symplectic transvections, i.e. xTv(λ) = x+λf(x, v), for some isotropic vector v. By computation one can show that Tv(λ)∈SUn(q)if and only if λq−1=−1, and in that case Tv(λ)is called a unitary transvection. One can show that SUn(q)is generated by unitary transvections except when (n, q) = (3,2). Now, we consider the action of SUn(q)on the isotropic 1dimensional spaces, i.e. the set of all huiwith u∈Fn q2−{0}and f(u, u)=0. Since properties similar to Proposition 1.4.2 hold for unitary transvections, the set of unitary transvections for a fixed isotropic vector vform an abelian normal subgroup of the stabilizer of hvi. It can be easily shown that SUn(q) acts primitively on the set of isotropic 1-dimensional spaces. When n > 3, or n= 3 and q > 2, explicit computations show that all unitary transvections are commutators of matrices of SUn(q). Finally, as PSUn(q)acts faithfully on the set of isotropic 1-dimensional spaces, we get the following theorem: Theorem 1.5.1. The group PSUn(q)is simple except when (n, q) = (2,2),(2,3) and (3,2). 1.6 Orthogonal groups in odd characteristic In this section we will omit all the proofs. The interested reader on them is invited to read [Gro01], but it should be careful as we use a different notation. In Section 1.3.4 we proved that, up to equivalence, there are exactly two non-singular symmetric bilinear forms on a Fq-vector space V, with qodd. Let fbe a non-singular symmetric bilinear form on Vof dimension n. The (general) orthogonal group GO(V, f)is defined as the isometry group of f. That is, it is the subgroup of GL(V)that consists of the invertible linear maps gthat satisfy f(ug, vg) = f(u, v)for all u, v ∈V. It is clear that for any scalar λ,GO(V, f) = GO(V, λf). As in the other classical groups, all the groups defined in this section can be regarded as some groups of matrices. If nis even, it can be shown that fand λf are equivalent forms for any scalar λ. Alternatively, if nis odd and λis a non-square scalar, then fand λf are never equivalent. In this case there is only one orthogonal group up to isomorphism, and we denote it as GO(V), or GOn(q)without ambiguity (up to isomorphism). When nis even, there are two different orthogonal groups, in fact they do not even have the same order. If fis of plus type we denote GO(V, f)by GO+ 2m(q); and GO− 2m(q)when the form is of minus type. Observe that any isometry gin an orthogonal group has determinant ±1. To see this, let Jbe the matrix of the form f. Then gTJg =J, and by taking the determinant map we get that detg= (detg)−1. The isometries of determinant 1 form a subgroup of index 2, which is the special orthogonal group, and is denoted as SOn(q)when nis odd, and SOε n(q) when nis even and the corresponding form is of ε∈ {+,−} type. If n 22 2.2. Computing character tables and thus, λi(K) = |C|χi(g) χi(1) . Evaluating λiin the equality KjKk=Pr l=1 aj,k,lKl gives the desired result. We denote by j0the integer such that g−1 j∈Cj0. By the definition of the integer aj,k,l it is clear that the total number of triples (x, y, z)∈Cj×Ck×Cl with xy =zequals |Cl|aj,k,l. Moreover, this also equals the total number of such triples with y=x−1z, and hence |Cl|aj,k,l =|Ck|aj0,l,k. Substituting this in the right-hand side of (2.4) and interchanging jand j0we get |Cj|χi(gj0) χi(1) χi(gk) = r X l=1 χi(gl)aj,l,k (2.6) where 1⩽i, j, k ⩽r. Rewriting (2.6) in matrix form yields |Cj|χi(gj0) χi(1) (χi(g1), . . . , χi(gr)) = (χi(g1), . . . , χi(gr))   aj,1,1··· aj,1,r . . ..... . . aj,r,1··· aj,r,r    (2.7) for 1⩽i, j ⩽r. Hence, if we define Mjas the r×rmatrix whose (k, l)component is aj,k,l, what (2.7) tells us is that the rrow vectors (χi(g1), . . . , χi(gr)) are common eigenvectors of the matrices Mj. Such matrices are called class matrices. To compute the l-th column of Mj, we determine the conjugacy classes of yl=x−1glfor all x∈Cj. Hence, the (k, l)component of Mjis the number of these ylthat are in Ck. If we want to work efficiently in practice, the class map of G—the map f:G→ {1, . . . , r}such that x∈Cf(x)for every x∈G— should be cheap to compute1. Notice that the first column of Mjhas a unique non-zero entry |Cj|in row j0, so we may assume that the first column of a class matrix is always known. Working in a finite field We know that the values of the character table are related to the eigenvectors of the class matrices. Computations of such eigenvectors over the complex numbers involve floating point computations. Since this is not desirable, instead of working over C, Dixon showed in [Dix67] that the eigenvector computations could be performed in a finite field to later lift back the results to C. We present his work in this section. Let ebe the exponent of Gand let ζ∈Cbe a primitive e-th root of unity. Recall that for every character χof Gand all g∈G,χ(g)is a sum of χ(1) |g|-th roots of unity. Thus, for all the values χi(gj)of the character table we have that χi(gj)∈Z[ζ]. 1Instead of checking directly conjugacy for every representative, the number of conjugacy checks can be reduced if one compares conjugacy invariants beforehand. For example, the order of an element or the cycle decomposition in permutation groups. Chapter 2. Character theory 23 Theorem 2.2.2. Fix χ∈IrrG. For every g∈G, |ClG(g)|χ(g) χ(1) is an algebraic integer. Proof. It is easy to show that the abelian group R=hK1, . . . , Kriis in fact a ring. Let λ:Z(CG)→Cbe the homomorphism defined in the proof of Lemma 2.2.1, in this case the one that depends on the irreducible character χ. Thus, S=λ(R) = hλ(K1), . . . , λ(Kr)iis a ring. It is well known that a complex number zis an algebraic integer if and only if zis contained in a subring of Cwhose additive group is finitely generated. Hence, we conclude that all the λ(Ki)are algebraic integers. Define K=Px∈ClG(g)x. By (2.5) we have the equality, χ(1)λ(K) = |ClG(g)|χ(g), and hence the result follows. Corollary 2.2.3. The equations from (2.6), and consequently (2.7), involve elements from Z[ζ]. Proof. By Theorem 2.2.2 all the numbers |Cj|χi(gj)/χi(1) ∈Q(ζ)are algebraic integers. Moreover, it is well known that Z[ζ]is the ring of integers of Q(ζ), and therefore all the numbers |Cj|χi(gj)/χi(1) lie in Z[ζ]. The result follows. By Dirichlet’s theorem [Dir37] on primes in an arithmetic progression, there exists a prime pwith e|p−1and p > 2χi(1) for 1⩽i⩽r. At this point the degrees of the irreducible characters are unknown to us, but by the class equation these last inequalities can be replaced with the following condition: p > 2bp|G|c. As e|p−1, there is an element ω∈Fpwith multiplicative order e. Therefore, the assignation ζ7→ ωinduces a ring homomorphism Θ: Z[ζ]→Fpin the natural way: Θ e−1 X i=0 aiζi!7−→ e−1 X i=0 aiωi. Let X= (χi(gj)) be the character table of Gregarded as a matrix, and let Ybe the r×rmatrix with Y= (|Cj|χi(gj0)). By the second orthogonality relation we have that XY =|G|Ir, in particular det(X)det(Y)6= 0. Hence, the rows Xi,:= (χi(g1), . . . , χi(gr)), which by (2.7) are common eigenvectors of the matrices Mj, are linearly independent. Furthermore, every prime q that divides |G|also divides e, and as e|p−1,pdoes not divide |G|. Since |det(X)|divides |G|, the row vectors Θ(Xi,:)are also linearly independent over Fp. By Corollary 2.2.3 we can apply Θto the equations from (2.6) to get a system of equations over Fp. Since Θis a ring homomorphism, these vectors are common eigenvectors of the matrices Θ(Mj). 24 2.2. Computing character tables Let Xi,:and Xt,:be two distinct rows of X. Note that the corresponding eigenvalues |Cj|χi(gj0)/χi(1) and |Cj|χt(gj0)/χt(1) are different for at least one j. Otherwise, the i-th and t-th column of the matrix Ywould be the same. The same applies to any pair of distinct rows of Θ(X). Therefore, the set of rows of Θ(X)and a set of rlinearly independent common eigenvectors of the matrices Θ(Mj)are the same, up to scalar multiplication in each vector. Splitting eigenspaces of the class matrices Now we will show a method to find a set of rlinearly independent common eigenvectors of the matrices Θ(Mj). Instead of computing all the class matrices, Schneider showed in [Sch90] that it was sufficient to only compute some well-chosen columns of some class matrices. We call a subspace of Fr pacharacter space if it is spanned by some rows of Θ(X). Choose some j > 1and compute Mj. For example, one could take the jthat corresponds to the smallest non-trivial conjugacy class. We know that Fr p=V1⊕···⊕Vt, where the Viare the distinct eigenspaces of Θ(Mj). Note that all the Viare character spaces. Furthermore, we can compute a basis in echelon form for each Vi. If dim Vi= 1 for all i, then we have found rlinearly independent common eigenvectors of the matrices Θ(Mj). Otherwise, there is some Viwith dim Vi>1. In this case, we should find a different Θ(Mj)to split Viinto smaller dimensional character spaces. The next lemma tells us which class matrices will split Vi, just from looking at the first column of the class matrices, which are always known, as we noted on p. 22. Lemma 2.2.4 ([Sch90]).Let {b1, . . . , bs}be a basis of a character space V in echelon form. Define the subspace W=hb2, . . . , bsi. Then Vis contained in a single eigenspace of Θ(Mj)if and only if Wis fixed by Θ(Mj). Proof. Suppose that Vis contained in a single eigenspace of Θ(Mj). Then the base vectors b1, . . . , bmare all eigenvectors, and hence Wis fixed by Θ(Mj). For the converse, suppose that Wis fixed by Θ(Mj). Assume, for sake of contradiction, that Vdoes not lie in a single eigenspace of Θ(Mj). Therefore, there exist v1, v2∈Veigenvectors for different eigenvalues λ1and λ2of Θ(Mj). As v1and v2lie in different character spaces, their first component is non-zero, so we may assume that their first entry is 1. Since b1is the only basis vector of Vwith non-zero first component (by hypothesis, the basis is in echelon form), we may assume that v1=b1+w1for some w1∈W, and in an analogous way v2=b1+w2, where w2∈W. Therefore, λ1v1=v1Θ(Mj) = b1Θ(Mj) + w1Θ(Mj) Chapter 2. Character theory 25 and since by assumption Wis invariant under Θ(Mj),b1Θ(Mj)must have λ1as its first component. The same argument for v2yields λ1=λ2, which is a contradiction. We conclude that a character space V(of dimension greater than 1) is contained in a single eigenspace of Θ(Mj)if and only if each of its echelonized basis vector b2, . . . , bsis zero in position j0. Otherwise, we can use Θ(Mj) to decompose Vinto smaller character spaces. Note that always will exist such a j. Let jbe such that the character space Vis not contained in a single eigenspace of Θ(Mj). In order to determine the action of Θ(Mj)on Vit is no longer necessary to know the complete class matrix Mj, but only those columns k1, . . . , kswhere the first non-zero entry of biis in the ki-th entry. We will try to use the same Θ(Mj)matrix to split more than one character space of dimension greater than 1. However, different character spaces may require the computation of different columns of Mj, in order to determine their corresponding action. Suppose that V={V1, . . . , Vt}is a set of character spaces such that Fr p=V1⊕···⊕Vt, where for at least one Viits dimension is greater than 1. The cost of computing a class matrix Mjis proportional both to |Cj| and to the number of distinct columns required to determine its action in the character spaces it splits. We quantify the computational cost of the matrix Mjin the following way: set val = 0 and for each character space V∈ V with dimension greater than 1 and that is split by Θ(Mj), increase val by 1. Finally, divide val by |Cj|and by the number of columns required to determine all the actions of the character spaces that are split by Θ(Mj). The greater the value of val the more cost-effective it should be to determine the class matrix Mj. So, we define the number BestMat(V) = jif Mjis the class matrix with the highest val. Here we describe a procedure to compute a set of rlinearly independent common eigenvectors of the matrices Θ(Mj),1⩽j⩽r. Algorithm 1: Schneider 1Compute Mj, where jfulfills |Cj|= mini>1|Ci|; 2Compute the set V:={V1, . . . , Vt}of eigenspaces of Θ(Mj)and a base in echelon form for each Vi; 3while ∃i: dim Vi>1do 4j:=BestMat(V); 5for Vnot contained in a single eigenspace of Θ(Mj)do 6Determine the action of Θ(Mj)on Vas described above; 7Compute the eigenspaces ˜ V1,..., ˜ Vl⩽Vof Θ(Mj)on the space Vand their respective bases in echelon form; 8Replace Vby ˜ V1,..., ˜ Vlin V; 9return V; 26 2.2. Computing character tables In fact, this algorithm returns a set of rone-dimensional eigenspaces, but this is not a problem at all. Returning to the complex plane Let v1, . . . , vrfor Θ(Mj)be rlinearly independent common eigenvectors of the matrices Θ(Mj)computed using Algorithm 1. Each viis a multiple of some row of Θ(X), so we may assume to be of the i-th one. Thus, the first entry of viis a multiple of χi(1) 6= 0, so we normalize the vector to ensure that vi[1] = 1. Therefore, vi=1 χi(1)Θ(Xi,:), and by the first orthogonality relation r X j=1 |Cj|vi[j]vi[j0] = |G| χi(1)2. All in the left-hand side of this equation is known mod p, and therefore we compute the value of χi(1)2mod p. Since 1⩽χi(1) < p/2(we imposed this condition on p. 23), we can fully determine the value of the integer χi(1). Therefore, we can compute Θ(Xi,:) = χi(1)vifor 1⩽i⩽r, and get the matrix Θ(X). Finally, in the following lines we carry out the reconversion to the complex field. Unfortunately, Θis not invertible (it has non-trivial kernel), so the reconversion Cis not immediate. However, each χi(gj)is the sum of di=χi(1) powers of ζ. That is, χi(gj) = Pe−1 k=0 mi,j,kζkwhere mi,j,k are integers satisfying 0⩽mi,j,k ⩽|χi(gj)|⩽χi(1) < p. The following lemma will help us to determine such coefficients. Lemma 2.2.5. If χi(gj) = Pe−1 k=0 mi,j,kζk, then mi,j,k =e−1 e−1 X l=0 χi(gl j)ζ−kl.(2.8) Proof. For any l∈Zwe have that χi(gl j) = Pe−1 t=0 mi,j,tζtl. Then, e−1 e−1 X l=0 χi(gl j)ζ−kl =e−1 e−1 X t=0 mi,j,t e−1 X l=0 ζ(t−k)l. As ζis a primitive e-th root of unity, the sum Pe−1 l=0 ζ(t−k)lequals eif t=k and 0 otherwise. We get the desired equality. Applying Θto equation (2.8), we get the value of mi,j,k mod p: mi,j,k ≡pΘ(e−1) e−1 X l=0 Θ(χi(gl j))ω−kl. Since the matrix Θ(X)is known, it is clear that the values of Θ(χi(gl j)) can be computed. The value Θ(χi(gl j)) equals to the (f(gl j), i)-th entry of the Chapter 2. Character theory 27 matrix Θ(X), where fdenotes the class map with respect to the conjugacy classes we have fixed at the beginning. Finally, as 0⩽mi,j,k ⩽χi(1) < p, the values of the integers mi,j,k are fully determined, and hence the character table of Gis known. The following is a summary in pseudocode of the complete algorithm: Algorithm 2: Burnside-Dixon-Schneider Data: Gfinite group with 1 = g1, . . . , grrepresentatives of its conjugacy classes. fdenotes the class map of Gwith respect to these representatives. Result: The character table of Gas a matrix. 1e:=lcm(g1, . . . , gr); 2Choose a prime number pwith e|p−1and p > 2p|G|; 3Find v1, . . . , vrlinearly independent common eigenvectors of the matrices Θ(Mj),1⩽j⩽r, using Algorithm 1; 4for 1⩽i⩽rdo // Determine the values of the degrees χi(1) 5Compute the unique integer satisfying 1⩽di< p/2and Pr j=1 |Cj|vi[j]vi[j0]≡p|G|/d2 i; 6for 1⩽i⩽rdo // Compute the matrix Θ(X)row by row 7Θ(X)i,::=divi; 8for 1⩽i, j, k ⩽rdo 9mi,j,k := Θ(e−1)Pe−1 l=0 Θ(X)f(gl j),i ω−kl; 10 for 1⩽i, j ⩽rdo 11 χi,j :=Pe−1 k=0 mi,j,kζk; 12 return X= (χi,j)1⩽i,j⩽r; Note: The author’s implementation of this algorithm in the GAP system [GAP22] can be found in the file CharTab.g from the GitHub repository [Jua23] and in Appendix B. The algorithm described in this section can be improved in many ways. For example, one could first compute the linear characters and use this information to avoid computing class matrices. The interested reader should check [Hul93] for more details. Chapter 3 Ore’s conjecture Ore’s conjecture states that every element of every finite non-abelian simple group is a commutator. In 2009 the proof was completed. 3.1 Generalizations Obvious generalizations of Ore’s conjecture fail to hold. For example, in exercise A.2.1 we prove that for every prime number pthere is a group Gof order p12 such that G06=K(G), where K(G)denotes the set of commutators of G. Also, in exercise A.2.2 we check in the GAP system [GAP22] that the smallest group in which the property K(G)6=G0holds has order 96. Now we note an open problem related to Ore’s conjecture. There is a conjecture attributed to J. G. Thompson which asserts that if Gis a finite non-abelian simple group, then there is a conjugacy class C⊆Gwith G=C2. It is straightforward to check that Thompson’s conjecture implies Ore’s conjecture, as we do now. Let C= ClG(g). Since 1∈G=C2, we have that g−1∈C, and thus G= ClG(g−1)ClG(g). Hence, every element of Gis of the form w= (g−1)xgy, and consequently w= (h−1)zhis a commutator, where z=y−1xand h=gy. We remark that a weaker form of Thompson’s conjecture is true. If Gis a finite non-abelian simple group, in [GT15] was proved that there exists a conjugacy class C⊆Gwith G=C3. 3.2 Alternating groups The alternating groups are the “simplest” family of the simple non-abelian groups. In the present section we prove Ore’s conjecture for this particular groups. We use the usual convention for the product of two permutations, i.e. the product of two στ permutations will be the composition where we apply σfirst and then τ. Also, we write (x)σto denote the image of an element 29 30 3.2. Alternating groups xunder the permutation σ. We say that (a1. . . ai). . . (aj. . . an)involves elements from (b1. . . bl). . . (br. . . bm)when {ai}n i=1 ⊆ {bi}m i=1. We start, as always, with some technical lemmas. Lemma 3.2.1. Let Gbe a group. If a1, b1, a2, b2∈Gand a1and b1commute with both a2and b2, then [a1, b1][a2, b2]=[a1a2, b1b2]. Proof. First, recall that if x, y, z ∈G, then [xz, y]=[x, y]z[z, y]and [x, zy] = [x, y][x, z]y. Therefore, [a1a2, b1b2]=[a1, b1b2]a2[a2, b1b2] = ([a1, b2][a1, b1]b2)a2[a2, b2][a2, b1]b2= [a1, b1][a2, b2]. Lemma 3.2.2. Let c1, c2∈Anbe two cycles of the same length, i.e. c1= (a1. . . am)and c2= (b1. . . bm)for some 3⩽m⩽n. If c2fixes aiand aj with ai6=aj, then there exists ϕ∈Ansuch that c−1 1=cϕ 2and that the ai’s and bi’s appear in its decomposition. Proof. As c−1 1and c2are cycles of the same length, there exists ϕ∈Snsuch that c−1 1=cϕ 2. If ϕ∈An, the first part of the claim is proven. Otherwise, cϕ 2= ((b1)ϕ . . . (bm)ϕ) = c−1 1= (am. . . a1).(3.1) Therefore, as ai, aj/∈ {bi}m i=1, we conclude that c−1 1=c(aiaj)ϕ 2and (aiaj)ϕ∈ An. From (3.1) we deduce that we can suppose that any element different to the ai-s and bi-s can be fixed by ϕ, thus, they only appear ai’s and bi’s in ϕ’s decomposition. Now we are ready to prove our desired theorem. There may be shorter proves of it, but the one we present is interesting since it is constructive. Theorem 3.2.3. When n⩾5, every element of Anis a commutator. Proof. First, we show that some particular permutations of Anare commutators of two permutations that involve elements from the given permutation. Afterwards, we will see that this is sufficient to prove the theorem. We start writing cycles of odd order (greater than 3) as commutators. Case 1.1: If the order of the cycle is 2m+1, for some m⩾2and meven, then c= (a1a2a3. . . am+1am+2am+3 . . . a2m+1)(3.2) = (a1a2a3. . . am+1)(a1am+2am+3am+4 . . . a2m+1).(3.3) If we name c1the cycle on the left of the equation (3.3) and c2the one on the right, it is clear that they are of the same length, m+1; and that c1, c2∈An. Chapter 3. Ore’s conjecture 31 Furthermore, c2fixes a2and a3, consequently, by Lemma 3.2.2 there exists ϕ∈Ansuch that c−1 1=cϕ 2, hence, c=c1c2= [ϕ, c2]. Remember that from Lemma 3.2.2 we also know that ϕwill involve elements from c. Case 1.2: When the order of the cycle is 2m+ 1, for some m⩾3and m odd, then c= (a1a2a3. . . am+1am+2am+3 . . . a2m+1) = (a1am+2a2. . . am+1)(a1am+2a2am+3 . . . a2m+1). Defining c1and c2as in the previous case, c2fixes a3and a4;c1and c2are of length m+2; and c1, c2∈An. Thus, by Lemma 3.2.2 there exists ϕ∈An such that c=c1c2= [ϕ, c2]. Remember that from Lemma 3.2.2 we also know that ϕwill involve elements from c. Now, we consider the case where we have a pair of disjoint cycles of even order. Suppose that we have the product of a cycle of order 2kwith another of order 2m−2kfor some k, m ∈Nsuch that 0<2k⩽m. Case 2.1: When m= 2, the unique possibility for kis being 1, and the following proves the claim: (a1a2)(a3a4)=(a1a2a3)(a1a4a3) = [(a1a3)(a2a4),(a1a4a3)].(3.4) Case 2.2: If mis even and m⩾4: c= (a1a2. . . a2k)(a2k+1a2k+2 . . . am+1am+2am+3 . . . a2m) = (a1a2. . . am+1)(a1am+2am+3 . . . a2ma2k+1) Defining c1and c2as always, c2fixes a2and am. Evidently, both are of length m+1, so c1, c2∈An. Therefore, by Lemma 3.2.2 there exists ϕ∈An such that c=c1c2= [ϕ, c2]. Case 2.3: If m= 3 and k= 1 we have that: (a1a2a3a4)(a5a6)=(a2a3a5a4a6)(a1a2a5a4a6) = [(a1a6a2a4a3),(a1a2a5a4a6)]. Case 2.4: When mis odd and m⩾3but (m, k)6= (3,1), c= (a1a2a3. . . a2k)(a2k+1a2k+2 . . . am+1am+2am+3 . . . a2m) = (a1am+2a2. . . am+1)(a1am+2a2am+3 . . . a2ma2k+2) Defining c1and c2as always, we see that c2fixes a4and am+1. It is easy to see that both are of length m+2, so c1, c2∈An. Therefore, by Lemma 3.2.2 there exists ϕ∈Ansuch that c=c1c2= [ϕ, c2]. In the following lines we consider the cases when we deal with 3-cycles. Case 3.1: Let τ= (a1a2a3). . . (aiai+1ai+2)be the product of an even number of 3-cycles. Our aim is to find π1, π2, ϕ ∈Ansuch that τ=π1π2 38 3.5. Experimental results and final discussion in the GAP package CTblLib [Bre22]. Chapter 3. Ore’s conjecture 39 Table 3.2: Experimental results Some simple groups Group Order Classes CPU time (sec) Ore Test A.1 Test A.2 Test B PSL3(2) 23·3·76<1<1<1Yes PSL3(3) 24·33·13 12 <12.12 <1Yes PSL5(2) 210 ·32·5·7·31 27 32 — µ= 6.7,σ= 5.4Yes PSp4(3) 26·34·520 <1<1µ= 3.06,σ= 0.91 Yes PSp6(3) 29·39·5·7·13 74 21.5 — — Yes PSU4(3) 27·36·5·720 5.7 — µ= 9.2,σ= 6.87 Yes M11 24·32·5·11 10 <12.2 <1Yes M12 26·33·5·11 15 <15.5 <1Yes M22 27·32·5·7·11 12 <1190 <1Yes Suz 213 ·37·52·7·11 ·13 43 <1— — Yes M246 ·320 ·59·76·112·133·17 ·19 ·23 ·29 ·31 ·41 ·47 ·59 ·71 194 <1— — Yes J4221 ·33·5·7·113·23 ·29 ·31 ·37 ·43 62 <1— — Yes Note 1: All times have been obtained on an MacBook Pro running macOS 12.2.1 with a 2,5 GHz Quad-Core Intel Core i7 processor and 16 GB of RAM. Note 2: The orders and the number of classes have been computed using the GAP system [GAP22]. Note 3: For the sporadic groups Test A.1 means applying Test A to the precomputed character tables. Appendix A Exercises A.1 Exercises from Chapter 1 Exercise A.1.1. Compute the orders of the linear groups. Solution. An invertible matrix takes a basis to another basis and is determined by the image of an ordered basis. Only a condition is imposed to this image: the image of the i-th vector must be linearly independent to all the previous ones. Since the previous i−1vectors generate a subgroup of dimension i−1, which has qi−1vectors in it, we get that |GLn(q)|= (qn−1)(qn−q)(qn−q2). . . (qn−qn−1) =qn(n−1)/2(q−1)(q2−1). . . (qn−1). From the definition of SLn(q)it is clear that |SLn(q)|=|GLn(q)| q−1. Finally, to get |PSLn(q)|we need to count the number of scalar matrices λIn with determinant 1. Since the determinant of these scalar matrices is λn= 1 and the number of solutions to xn= 1 in Fqis (n, q −1), |PSLn(q)|=1 (n, q −1)qn(n−1)/2(q−1)(q2−1) . . . (qn−1). Exercise A.1.2. Compute the orders of the symplectic groups. Solution. Let Vbe a Fq-vector space of dimension 2m. By definition, Sp(V) acts faithfully and transitively on the set of ordered symplectic bases of V. Hence, |Sp2m(q)|equals the number of such bases. We start with e1which can be any non-zero vector, so there are q2m−1 ways of choosing it. Since e⊥ 1has dimension 2m−1, it has q2m−1vectors. Hence, the number of vectors vwith f(u, v)6= 0 is q2m−q2m−1= (q− 1)q2m−1. These come in sets of q−1scalar multiples, each one giving a 41 42 A.1. Exercises from Chapter 1 different value f(u, v). Thus, the number of ways of choosing f1is q2m−1, and by induction on m, we get that |Sp2m(q)|= m Y i=1 (q2i−1)q2i−1. Clearly, |PSp2m(q)|=|Sp2m(q)| (2, q −1) . Exercise A.1.3. Prove that the transvections in Sp4(3) and Sp6(2) are commutators. Solution. Let V∼ =F2m qbe a vector space. Since the conjugate of a commutator is a commutator again, Sp(V)acts on V− {0}transitively and by the property iv) from Proposition 1.4.2, it suffices to verify that the transvections Tv(λ), for a fixed vector v, are a commutator for every scalar λ. Let B={e1, . . . , fm}be a symplectic basis of V. Then, it is clear that MB(Tf1(λ)) = ImC 0Imwhere C∈Mm(Fq)and all the entries of Care zero except the entry (1,1), whose value is λ. From (1.5) we deduce that if A∈GLm(q)and Bis a m×msymmetric matrix, then MA=A−10 0AT∈Sp2m(q)and MB=ImB 0Im∈Sp2m(q). An easy computation shows that [MA, MB] = ImB−ABAT 0Im. The following choices establish the result. When m= 2 and q= 3, and if λ∈F× 3, A= 1λ 0 1!, B = 0 1 1 0!. When m= 3 and q= 2, A=   110 001 100  , B =   101 011 111  . Exercise A.1.4. Check in GAP that PSU3(2) is a soluble group. Solution. The following code solves the exercise: gap > IsSolvableGroup ( Proj e c t i v e SpecialUnitar y G r o u p ( 3 , 2 ) ) ; t r u e Appendix A. Exercises 43 A.2 Exercises from Chapter 3 Exercise A.2.1. [Rot95, p. 34] (i) Let k[x, y]denote the ring of all polynomials in two variables over a field k, and let k[x]and k[y]denote the subrings of all polynomials in xand in y, respectively. Define Gto be the set of all matrices of the form (f, g, h):=   1f h 0 1 g 0 0 1   where f∈k[x],g∈k[y]and h∈k[x, y]1. Prove that Gis a multiplicative group and that G0consists of all matrices for which f=0=g. (ii) If (0,0, h)is a commutator, then there are polynomials f1, f2∈k[x] and g1, g2∈k[y]with h=f1g2−f2g1. (iii) Show that if h(x, y) = x2+xy +y2, then (0,0, h)∈G0is not a commutator. (iv) Deduce that for every prime number pthere is a group Gof order p12 such that G06=K(G). Solution. (i) Let (f1, g1, h1),(f2, g2, h2)∈G, then as a consequence of the multiplication of matrices (f1, g1, h1)(f2, g2, h2)=(f1+f2, g1+g2, h1+h2+f1g2)(A.1) (f1, g1, h1)−1= (−f1,−g1, f1g1−h1)(A.2) whence we get that G⩽GL3(k[x, y]), and thus Gis a group. By direct computation, we have that [(f1, g1, h1),(f2, g2, h2)] = (0,0, f1g2−f2g1),(A.3) and thus K(G) = {(0,0, f1g2−f2g1)|f1, f2∈k[x], g1, g2∈k[y]}. Define H={(0,0, h)|h∈k[x, y]}. From (A.1) and (A.2) we deduce that M⩽G, and since K(G)⊆H, then G0=hK(G)i⩽H. For the other inclusion, write h(x, y) = Pi,j ai,jxiyj. By direct computation, we get that Y i,j [(ai,jxi,0,0),(0, yj,0)] = (0,0, h), and thus, H=G0. (ii) Apply (A.3). 1A group of this type is called a Heisenberg group. 44 A.2. Exercises from Chapter 3 (iii) Suppose that (0,0, h)∈G0is a commutator. Therefore, by part ii) there exist f1(x) = Pibixiand f2(x) = Picixisuch that h(x, y) = x2+xy +y2=X i bixig2(y)−X i cixig1(y).(A.4) In particular, y2=b0g2(y)−c0g1(y), y=b1g2(y)−c1g1(y), 1 = b2g2(y)−c2g1(y). Regarding k[y]as a k-vector space, we have that the linearly independent set {1, y, y2}is contained in the subgroup generated by g1and g2, and this is a contradiction. (iv) If k=Fp,k[x, y]is replaced by k[x, y]/(x3, y3, x2y, xy2),k[x]by k[x]/(x3) and k[y]/(y3), then the correspoding group Ghas order p12 =p6p3p3. It is clear that in this context we can apply parts i), ii) and iii). Hence, for every pprime number there is a group of order p12 such that G06=K(G). Exercise A.2.2. Check in GAP that the smallest group in which the property K(G)6=G0holds has order 96. Solution. The following code solves the exercise: CommutatorProp := function (G) l o c a l commutators ; commutators := Set ( L i s t ( Car tes ian (G, G) , x - > Comm( x ) ) ) ; r e t u r n S i z e ( commutators ) = Order ( DerivedSubgroup (G) ) ; end ; empty := AllSmallGroups ( [ 1 . . 9 5 ] , CommutatorProp , false ) ; examples := AllSmallGroups ( 96 , CommutatorProp , false ) ; Since the list empty is empty and examples is not, the exercise is solved. Appendix B Source code In this appendix we present all the programs that the author has written in the GAP [GAP22] system for this dissertation. The files are ordered in alphabetical order. At the beginning of each file the user can find the documentation of each program and after each file we show examples of the execution of each program. We finally note that all these files can be found also in the GitHub repository [Jua23], where is also available a README file which explains how to run these programs on one’s computer. AsCommutator.g 1################################################################################ 2## 3## This file contains an implementation of an algorithm that writes any even 4## permutation as a commutator of two even permutations. 5## 6## Created by Xabier de Juan Soriano on 2022 7## This file is part of the author’s final degree dissertation. 8## 9 10 DeclareGlobalFunction("CyclesToList"); 11 DeclareGlobalFunction("CommutatorEvenPair"); 12 DeclareGlobalFunction("CommutatorOddCycle"); 13 DeclareGlobalFunction("AsCommutatorLists"); 14 15 ################################################################################ 16 ## 17 #M AsCommutator( permutation ) 18 ## 19 ## This is the function that the user must call in order to write any even 20 ## permutation as a commutator of two even permutations. 21 ## 22 ## input: 23 ## permutation: an even permutation, $r \in A_n$ (the value of n is assumed 24 ## to be the smallest such thatr \in A_n) 25 ## If the permutation is not even an error message is raised. 26 ## 27 ## output: 28 ## <list>[1]: even permutation $\phi \in A_n$ 29 ## <list>[2]: even permutation $\psi \in A_n$ 45 46 30 ## r = [\phi,\psi] 31 ## 32 AsCommutator := function(permutation) 33 local list; 34 if SignPerm(permutation) = -1 then Error("permutation must be an even permutation"); fi; 35 list := CyclesToList(permutation); 36 return AsCommutatorLists(list[1],list[2],list[3]); 37 end; 38 39 ################################################################################ 40 ## 41 ## AsCommutatorLists( cycles, cycles2, cycles3 ) 42 ## 43 ## This is function is not supposed to be used by the user 44 ## 45 ## input: 46 ## cycles : a list containing cycles of odd order 47 ## cycles2 : a list containing pairs of cycles of even order 48 ## cycles3 : a list containing 3-cycles 49 ## The cycle (a,b,c) corresponds to the list [ a , b , c ] 50 ## in this setting. 51 ## 52 ## output: 53 ## The same as the main function 54 ## 55 InstallGlobalFunction(AsCommutatorLists, function(cycles, cycles2, cycles3) 56 local a, b, phi, psi, c, l, l1, l2, m, k, aux, max; 57 58 # the particular cases 59 aux := 0; # we will use this later 60 # when we only have a cycle of order 3 61 if Length(cycles) = 0 and Length(cycles2) = 0 and Length(cycles3) = 1 then 62 a := cycles3[1]; 63 max := Maximum(a); 64 if max < 5 then max := 5; fi; 65 b := [1..max]; 66 RemoveSet(b, a[1]); 67 RemoveSet(b, a[2]); 68 RemoveSet(b, a[3]); 69 a := Concatenation(a, [b[Length(b)-1], b[Length(b)]]); 70 return [(a[1] ,a[5], a[2]),(a[3], a[4], a[2])]; 71 fi; 72 # when we only have a pair of a 2-cycle and a 4-cycle 73 if Length(cycles) = 0 and Length(cycles3) = 0 and Length(cycles2) = 1 then 74 # we know that Length(cycles2[1][1]) <= Length(cycles2[1][2]) 75 # this is because we are applying the function "CylesToList" 76 if Length(cycles2[1][1]) = 2 and Length(cycles2[1][2]) = 4 then 77 a := Concatenation(cycles2[1][2], cycles2[1][1]); 78 return [(a[1],a[6],a[2],a[4],a[3]), (a[1],a[2],a[5],a[4],a[6])]; 79 fi; 80 fi; 81 # when we only have a pair of 2-cycles 82 if Length(cycles) = 0 and Length(cycles3) = 0 and Length(cycles2) = 1 then 83 if Length(cycles2[1][1]) = 2 and Length(cycles2[1][2]) = 2 then 84 a := Concatenation(cycles2[1][1], cycles2[1][2]); 85 return [ (a[1],a[3])(a[2],a[4]) , (a[1],a[4],a[3]) ]; 86 fi; 87 fi; 88 89 # the general case 90 phi := (); Appendix B. Source code 47 91 psi := (); 92 # the output will be: [phi,psi] 93 for cin cycles do 94 l := CommutatorOddCycle(c); 95 phi := phi*l[1]; 96 psi := psi*l[2]; 97 od; 98 # divide cases, if there are zero 3-cycles or >=2 99 if Length(cycles3) <> 1 then 100 for cin cycles2 do 101 l := CommutatorEvenPair(c[1],c[2]); 102 phi := phi*l[1]; 103 psi := psi*l[2]; 104 od; 105 for cin cycles3 do 106 l := CommutatorOddCycle(c); 107 phi := phi*l[1]; 108 psi := psi*l[2]; 109 od; 110 else # if there is only one 3-cycle 111 if cycles <> [] then 112 for cin cycles2 do 113 l := CommutatorEvenPair(c[1],c[2]); 114 phi := phi*l[1]; 115 psi := psi*l[2]; 116 od; 117 l := CommutatorOddCycle(cycles3[1]); 118 phi := phi*l[1]; 119 psi := psi*l[2]; 120 # from here we jump to "if SignPerm(phi) = -1 then" 121 elif cycles2 <> [] then # redundant? 122 for cin cycles2 do 123 a := c[1]; 124 b := c[2]; 125 k := Length(a)/2; 126 m := Length(b)/2 + k; 127 if m >= 4 then 128 for cin cycles2 do 129 l := CommutatorEvenPair(c[1],c[2]); 130 phi := phi*l[1]; 131 psi := psi*l[2]; 132 od; 133 l := CommutatorOddCycle(cycles3[1]); 134 phi := phi*l[1]; 135 psi := psi*l[2]; 136 aux := 1; 137 break; 138 # from here we jump to "if SignPerm(phi) = -1 then" 139 fi; 140 od; 141 # if we end up here that means that we are in the situation of the final part of the proof 142 if aux = 0 then 143 c := cycles3[1]; 144 a := cycles2[1][1]; 145 b := cycles2[1][2]; 146 if Length(b) = 2 then #2x2 147 a := Concatenation(c,a,b); 148 l1 := [a[4], a[5], a[6]]; 149 l2 := [a[4], a[7], a[6]]; 150 phi := phi *(a[1],a[2]) *MappingPermListList(l2,Reversed(l1 )); 54 176 CT.m[i,j][k] := 0; 177 fi; 178 od; 179 od; 180 od; 181 NewPrint(mode, "complete"); 182 NewPrint(mode, "writing the character table..."); 183 # write the character table 184 CT.X := IdentityMat(CT.r)-IdentityMat(CT.r); 185 CT.Zeta := E(CT.e); 186 for iin [1..CT.r] do 187 for jin [1..CT.r] do 188 #pol := List([1..CT.e], k-> CT.m[i,j][k]); 189 CT.X[i,j] := ValuePol(CT.m[i,j], CT.Zeta); 190 od; 191 od; 192 NewPrint(mode, "sorting the rows of the table"); 193 # sort the table by degrees 194 SortBy(CT.X, x -> x[1]); 195 # first character must be the trivial one 196 j := Position(CT.X, List([1..CT.r],x->1)); 197 CT.X_ := ShallowCopy(CT.X); 198 CT.X_[1] := CT.X[j]; 199 CT.X_[j] := CT.X[1]; 200 return [CT.X_, CT.g]; 201 end; 202 203 ################################################################################ 204 ## 205 ## ClassMatrix( C, g, j, r, permRepr ) 206 ## 207 ## Computes the class matrix M_j. 208 ## 209 ## input: 210 ## C : conjugacy classes of G 211 ## g : representatives of the conj. classes 212 ## (it is assumed that it is given in the same order as C) 213 ## j : integer with 1<=j<=r 214 ## r : # of conj. classes 215 ## 216 InstallGlobalFunction(ClassMatrix, function(C, g, j, r, permRepr) 217 local l, M; 218 M := IdentityMat(r); 219 for lin [1..r] do 220 M[l] := ClassMatrixColumn(C, g, j, r, l, permRepr); 221 od; 222 return TransposedMat(M); 223 end); 224 225 ################################################################################ 226 ## 227 ## ClassMatrixColumn( C, g, j, r, l, permRepr ) 228 ## 229 ## Computes the l-th column of the class matrix M_j. It is returned as a row 230 ## 231 InstallGlobalFunction(ClassMatrixColumn, function(C, g, j, r, l, permRepr) 232 local x, y, z, k, c, v; 233 z := g[l]; 234 v := List([1..r], x -> 0); 235 # the first column is easy to compute 236 if l=1then 237 v[ClassMap(g[j]^-1, C, permRepr)] := Size(C[j]); Appendix B. Source code 55 238 return v; 239 fi; 240 for xin C[j] do 241 y := x^-1*z; 242 k := ClassMap(y,C,permRepr); 243 v[k] := v[k] + 1; 244 od; 245 return v; # this is a row 246 end); 247 248 ################################################################################ 249 ## 250 ## ClassMap( g, C, permRepr ) 251 ## 252 ## Computes the image of g under the class map 253 ## C is a list of all the conjugacy classes 254 ## 255 InstallGlobalFunction(ClassMap, function(g, C, permRepr) 256 local c, j, possible, x; 257 if permRepr = true then 258 possible := Filtered([1..Length(C)], x->CycleStructurePerm(Representative (C[x]))=CycleStructurePerm(g)); 259 else # this is why we prefer permutation groups 260 possible := Filtered([1..Length(C)], x->Order(Representative(C[x]))=Order (g)); 261 fi; 262 if Length(possible) = 1 then return possible[1]; fi; 263 j := 1; 264 while j < Length(possible) do 265 if gin C[possible[j]] then 266 return possible[j]; 267 else 268 j := j+1; 269 fi; 270 od; 271 return possible[j]; 272 end); 273 274 ################################################################################ 275 ## 276 ## BestMat( K, g, r, CO, C, permRepr ) 277 ## 278 ## Returns the value j such that computing the matrix M_j is the best option 279 ## 280 InstallGlobalFunction(BestMat, function(K, g, r, CO, C, permRepr) 281 local j, j_, k, best, val, columns; 282 best := [1,0]; 283 columns := []; 284 for jin [2..r] do 285 columns := []; 286 j_ := ClassMap(g[j]^-1, C, permRepr); 287 val := 0; 288 for kin Kdo 289 UniteSet(columns,k); 290 if Position(k,j_) <> fail then 291 val := val + 1; 292 fi; 293 od; 294 val := val/CO[j]; 295 val := val/Size(columns); 296 if best[2] < val then 297 best[2] := val; 56 298 best[1] := j; 299 fi; 300 od; 301 return best[1]; 302 end); 303 304 InstallGlobalFunction(FieldToMod, function(V) 305 local x; 306 return List(V, x -> IntFFE(x)); 307 end); 308 309 InstallGlobalFunction(NewPrint, function(mode, str) 310 if mode = [] then 311 Info(InfoWarning,1,str); 312 fi; 313 end); Example B.0.2. We compute the table of irreducible characters of A6and SL2(4). The group A6is represented as a permutation group in GAP. On the other hand, SL2(4) is represented as a matrix group. gap> C:=CharTab(AlternatingGroup(6),false,"silent");; # in this case it is the same to write false or true in the second argument gap> Display(C[1]); [ [ 1, 1, 1, 1, 1, 1, 1 ], [ 5, 1, -1, 2, -1, 0, 0 ], [ 5, 1, 2, -1, -1, 0, 0 ], [ 8, 0, -1, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 8, 0, -1, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 9, 1, 0, 0, 1, -1, -1 ], [ 10, -2, 1, 1, 0, 0, 0 ] ] gap> Print(C[2]); [ (), (1,2)(3,4), (1,2,3), (1,2,3)(4,5,6), (1,2,3,4)(5,6), (1,2,3,4,5), (1,2,3,4,6) ] gap> D := CharTab(SpecialLinearGroup(2,4),true,"silent");; gap> Display(D[1]); [ [ 1, 1, 1, 1, 1 ], [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 4, 0, 1, -1, -1 ], [ 5, 1, -1, 0, 0 ] ] gap> Print(D[2]); [ (), ( 5, 6)( 7, 8)( 9,11)(10,12)(13,16)(14,15), ( 2, 3, 4)( 5,13, 9)( 6,15,12)( 7,16,10)( 8,14,11), ( 2, 5,10,11, 7)( 3, 9,15,16,12)( 4,13, 8, 6,14), ( 2, 5,14,16, 8)( 3, 9, 7, 6,10)( 4,13,12,11,15) ] gap> F := CharTab(SpecialLinearGroup(2,4),false,"silent");; # this character table is equivalent to the previous one gap> Display(F[1]); [ [ 1, 1, 1, 1, 1 ], [ 3, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4, 0 ], [ 3, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3, 0 ], [ 4, 0, -1, -1, 1 ], [ 5, 1, 0, 0, -1 ] ] # we get the elements represented in a different way gap> Print(F[2]); [ [ [ Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0 ] ], [[0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2) ] ], [[0*Z(2), Z(2)^0 ], [ Z(2)^0, Z(2^2) ] ], [[0*Z(2), Z(2)^0 ], [ Z(2)^0, Z(2^2)^2 ] ], [ [ Z(2^2), 0*Z(2) ], [ 0*Z(2), Z(2^2)^2 ] ] ] Appendix B. Source code 57 OreTest1.g 1################################################################################ 2## 3## This file contains an implementation of an algorithm that checks whether 4## in a group all elements are commutators 5## 6## Created by Xabier de Juan Soriano on 2023 7## This file is part of the author’s final degree dissertation. 8## 9 10 ################################################################################ 11 ## 12 ## OreTest1( CT ) 13 ## 14 ## input: 15 ## CT: ordinary character table of the group G as a matrix with values 16 ## in a cyclotomic field https://docs.gap-system.org/doc/ref/chap18.html 17 ## 18 ## output: 19 ## returns true if all the elements of G are commutators and false otherwise 20 ## 21 OreTest1 := function(CT) 22 local i, j, r; 23 r := Length(CT); 24 CT := TransposedMat(CT); 25 for iin [2..r] do 26 if Sum([1..r], j->CT[i,j]/CT[1,j]) = 0 then 27 return false; 28 fi; 29 od; 30 return true; 31 end; Example B.0.3. We check Ore’s conjecture for A6,S6and SL2(8). In order to compute the character tables, we apply the previous function gap> OreTest1(CharTab(AlternatingGroup(6),true,"silent")[1]); true gap> OreTest1(CharTab(SymmetricGroup(6),true,"silent")[1]); false gap> OreTest1(CharTab(SpecialLinearGroup(2,8),true,"silent")[1]); true OreTest2.g 1################################################################################ 2## 3## This file contains an implementation of an algorithm that checks whether in 4## a group all elements are commutators 5## 6## Created by Xabier de Juan Soriano on 2023 7## This file is part of the author’s final degree dissertation. 8## 9 10 ################################################################################ 11 ## 12 ## OreTest2( G ) 58 13 ## the program halts if and only if every element of G is a commutator 14 ## 15 ## input: 16 ## G : finite group G 17 ## 18 ## output: 19 ## returns true if all the elements of G are commutators 20 ## 21 OreTest2 := function(G) 22 local g, x, repr, order, index_cent, new_repr; 23 order := Order(G); 24 # we want permutations groups 25 if IsPermGroup(G) = false then G := Image(IsomorphismPermGroup(G)); fi; 26 repr := [()]; # to store the different representative of the classes 27 index_cent := 1; # cummulative sum of the index of the centralizers 28 while order <> index_cent do 29 new_repr := true; 30 g := Comm(Random(G),Random(G)); 31 if g <> () then 32 for xin repr do 33 # first cheap conjugation test 34 if CycleStructurePerm(x) = CycleStructurePerm(g) then 35 if IsConjugate(G, x, g) then 36 new_repr := false; 37 break; 38 fi; 39 fi; 40 od; 41 if new_repr then 42 Append(repr,[g]); 43 index_cent := index_cent + order/Size(Centralizer(G, g)); 44 fi; 45 fi; 46 od; 47 return true; 48 end; Example B.0.4. We check Ore’s conjecture for PSL3(3). gap> OreTest2(ProjectiveSpecialLinearGroup(3,3)); true Bibliography [Bre22] T. Breuer. GAP package CTblLib. 2022. url:https://www. gap-system.org/Packages/ctbllib.html. [Bur55] W. Burnside. Theory of Groups of Finite Order. New York: Dover Publications, 1955. [Cel+95] F. Celler et al. “Generating random elements of a finite group”. In: Communications in Algebra 23.13 (1995), pp. 4931–4948. doi: 10.1080/00927879508825509. [Con20] K. Conrad. Simplicity of PSLn(F). 2020. url:https://kconrad. math.uconn.edu/blurbs/grouptheory/PSLnsimple. pdf (Retrieved 05/05/2023). [CS97] J.J. Cannon and B. Souvignier. “On the Computation of Conjugacy Classes in Permutation Groups”. In: Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC 1997, Maui, Hawaii, USA, July 21-23, 1997. ACM, 1997, pp. 392–399. doi:10.1145/258726.258855. [CS99] H. Cuypers and A. Steinbach. “Linear transvection groups and embedded polar spaces”. In: Inventiones Mathematicae 137 (1999), pp. 169–198. doi:10.1007/s002220050328. [Dir37] P.G.L. Dirichlet. “Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält”. In: Abhandlungen der Königlich Preußischen Akademie der Wissenschaften 48 (1837), pp. 45–71. [Dix67] J.D. Dixon. “High speed computation of group characters”. In: Numer. Math. 10 (1967), pp. 446–450. doi:10.1007/BF02162877. [EG98] E.W. Ellers and N.L. Gordeev. “On the Conjectures of J. Thompson and O. Ore”. In: Transactions of the American Mathematical Society 350.9 (1998), pp. 3657–3671. [GAP22] GAP – Groups, Algorithms, and Programming, Version 4.12.0. The GAP Group. 2022. url:https://www.gapsystem. org/. 59 60 Bibliography [Gro01] L.C. Grove. Classical Groups and Geometric Algebra. American Mathematical Society, 2001. [GT15] R.M. Guralnick and P.H. Tiep. Effective Results on the Waring Problem for Finite Simple Groups. 2015. arXiv: 1302.0333. [HEO05] D.F. Holt, B. Eick, and E.A. O’Brien. Handbook of Computational Group Theory. Discrete Mathematics and Its Applications. CRC Press, 2005. [Hul93] A. Hulpke. “Zur Berechnung von Charaktertafeln”. Diploma thesis. Rheinisch Westfälische Technische Hochschule, 1993. [Isa94] I.M. Isaacs. Character Theory of Finite Groups. Dover, 1994. [Ito51] N. Ito. “A theorem on the alternating group An(n⩾5)”. In: Math. Japonicae 2 (1951), pp. 59–60. [Jor70] C. Jordan. Traité des substitutions et des équations algébriques. Gauthier-Villars, 1870. [Jua23] X. de Juan. TFGcode.https://github.com/xdejs/TFGcode. 2023. [KM05] L.C. Kappe and R. Morse. “On commutators in groups”. In: Journal of Group Theory 8 (2005), pp. 415–429. [Lan02] S. Lang. Algebra. Springer, 2002. [LOST] M. Liebeck et al. “The Ore conjecture”. In: Journal of the European Mathematical Society 012.4 (2010), pp. 939–1008. doi: 10.4171/JEMS/220. [Mal14] G. Malle. “The proof of Ore’s conjecture [after Ellers-Gordeev and Liebeck-O’Brien-Shalev-Tiep]”. In: Séminaire Bourbaki volume 2012/2013 : exposés 1059-1073 - Avec table par noms d’auteurs de 1948/49 à 2012/13. Astérisque 361. talk:1069. Société mathématique de France, 2014. [Mil99] G.A. Miller. “On the commutators of a given group”. In: Bulletin of the American Mathematical Society 6.3 (1899), pp. 105–109. [NPC84] J. Neubüser, H. Pahlings, and E. Cleuvers. “Each sporadic finasig Ghas a class Csuch that CC =G”. In: Abstracts AMS. Vol. 34. 6. 1984. [Ore51] O. Ore. “Some Remarks on Commutators”. In: Proceedings of the American Mathematical Society 2.2 (1951), pp. 307–314. doi: 10.2307/2032506. [Rot95] J.J. Rotman. An Introduction to the Theory of Groups. Springer New York, 1995. Bibliography 61 [Sch90] G. Schneider. “Dixon’s character table algorithm revisited”. In: Journal of Symbolic Computation 9.5 (1990), pp. 601–606. doi: 10.1016/S0747-7171(08)80077-6. [TL65] K’en-ch’eng Ts’eng and Chiung-sheng Li. “On the commutators of the simple Mathieu groups”. In: J. China Univ. Sci. Techn. 1 (1965), pp. 43–48. [Wey39] H. Weyl. The Classical Groups. Their Invariants and Representations. Princeton University Press, 1939. [Wil09] R.A. Wilson. The Finite Simple Groups. Springer, 2009.