Quasiregular projective planes of order 16 [Elektronische Ressource] : a computational approach / Marc Röder

Description

Quasiregular ProjectivePlanes of Order 16A Computational ApproachMarc R¨oderVom Fachbereich Mathematik der Technischen Universit¨at Kaiserslauternzur Verleihung des akademischen Grades Doktor der Naturwissenschaften(Doctor rerum naturalium, Dr. rer. nat.) genehmigte Dissertation1. Gutachter: Prof. Dr. U. Dempwolff2. Gutachter: Prof. Dr. D. HeldVollzug der Promotion: 21. November 2006D386AbstractThisthesisdiscussesmethodsfortheclassificationoffiniteprojectiveplanesviaexhaustivesearch. In the main part the author classifies all projective planes of order 16 admittinga large quasiregular group of collineations. This is done by a complete search using thecomputer algebra system GAP. Computational methods for the construction of relativedifference sets are discussed. These methods are implemented in a GAP-package, which isavailable separately.As another result –found in cooperation with U. Dempwolff– the projective planesdefined by planar monomials are classified. Furthermore the full automorphism group ofthe non-translation planes defined by planar monomials are classified.ZusammenfassungDie Arbeit befasst sich mit Methoden zur Klassifikation endlicher projektiver Ebenenmittels vollsta¨ndiger Suche. Im Hauptteil werden die projektiven Ebenen der Ordnung16 klassifiziert, die eine große quasiregul¨are Kollineationsgruppe besitzen. Dies geschiehtdurch eine vollsta¨ndige Suche mit Hilfe des Computeralgebra Systems GAP.

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_kaiserslautern
• Publié le: 01 janvier 2006
• Nombre de lectures: 19
• Langue: Deutsch

Extrait

Quasiregular Projective Planes of Order16

A Computational Approach

MarcR¨oder

VomFachbereichMathematikderTechnischenUniversita¨tKaiserslautern zur Verleihung des akademischen Grades Doktor der Naturwissenschaften (Doctor rerum naturalium, Dr. rer. nat.) genehmigte Dissertation

1.

Gutachter: Prof. Dr. U. Dempwolff 2. Gutachter: Prof. Dr. D. Held

Vollzug der Promotion: 21.

D386

November 2006

Abstract

This thesis discusses methods for the classification of finite projective planes via exhaustive search. In the main part the author classifies all projective planes of order 16 admitting a large quasiregular group of collineations. This is done by a complete search using the computer algebra systemGAP. Computational methods for the construction of relative difference sets are discussed. These methods are implemented in aGAP-package, which is available separately. As another result –found in cooperation with U. Dempwolff– the projective planes defined by planar monomials are classified. Furthermore the full automorphism group of the non-translation planes defined by planar monomials are classified.

Zusammenfassung

Die Arbeit befasst sich mit Methoden zur Klassifikation endlicher projektiver Ebenen mittelsvollsta¨ndigerSuche.ImHauptteilwerdendieprojektivenEbenenderOrdnung 16klassifiziert,dieeinegroßequasiregul¨areKollineationsgruppebesitzen.Diesgeschieht durcheinevollsta¨ndigeSuchemitHilfedesComputeralgebraSystemsGAP¨fruewdr.aDen MethodenzurKonstruktionrelativerDifferenzmengenero¨rtert.DieseMethodenwurden vom Verfasser in einemGAP¨hretara.hciltlantiertundsindsep-aPekitpmelem Ein weiteres Resultat (in Zusammenarbeit mit U. Dempwolff) ist die Klassifikation derprojektivenEbenen,diedurchplanareMonomedefiniertsind.F¨urEbenen,diedurch Monome definiert und keine Translationsebenen sind, wird die volle Automorphismen- gruppeberechnet.Damitsindf¨uralleplanareMonomedieAutomoprhismengruppender zugeho¨rigenEbenenbekannt.

Mathematics Subject Classification (MSC 2000):

05B25Finite geometries 05B10Difference sets (number-theoretic, group-theoretic etc.) 51E15Affine and projective planes 51A35Non-Desarguesian affine and projective planes 12E10Special polynomials over general fields

Keywords:

relative difference set, projective plane, quasiregular group, Dembowski-Piper classifica- tion, planar function, non-Desarguesian plane,GAP

Schlagworte:

relativeDifferenzmenge,projektiveEbene,quasiregula¨reGruppe,Dembowski-PiperKlas- sifikation, planare Funktion, nicht- desarguessche Ebene,GAP

Preface

During the last two decades, computational group theory and computational finite geometries have become very active fields of research. The most promi- nent result from this area is the proof of the non-existence of projective planes of order 10 [LTS89]. But besides the proof of conjectures by complete enumeration of the problem –or part of it– there is another reason for the popularity of computational methods. Experiments using computer algebra systems sometimes lead to new constructions or theorems as they encourage “inspired guessing”. Computer algebra systems likeGAPare of great help here as they are easy to use and provide plenty of functionality. So it is not necessary to do a lot of programming to just “have a look” at a few sample cases. The present thesis shows one instance of either case. In the main part, a computer search is done to classify a certain type of projective planes. In chapter 6 we prove a theorem (in cooperation with U. Dempwolff) which grew from related experiments and a close investigation of a sample case. This text is structured as follows: In chapter 1 we will have a look at the connection between projective planes and difference sets. Section 1.3 relates relative difference sets to pro- jective planes and divisible designs. With a view towards a computer search for relative difference sets, section 1.4 develops a tool called “coset signa- ture”. This tool enables us to use information about the subgroup structure of a group for the generation of relative difference sets in this group (and even in others with a similar subgroup structure). For the case of ordinary difference sets, chapter 2 demonstrates the use of representation theory to calculate coset signatures in a certain class of groups. As a result, a search for difference sets in groups of this class can (normally) be done much easier. In chapter 3 we approach the main objective of this thesis. The types

1

of planes given by the classification of Dembowski and Piper [DP67] are studied to find all projective planes of order 16 admitting a large quasiregular automorphism group. For each case, a difference set construction is given and the results of the corresponding computer search are stated as a theorem. The algorithmic part of this search is considered in chapter 4. After a general outline of the search algorithms, several aspects of the algorithms receive special attention. Some examples for the implementation inGAPare given in appendix B. In chapter 5 a few experiments in higher order are documented. This illustrates some possibilities for further searches using similar methods. Chapter 6 shows an example of how computer experiments may lead to general results. Calculations for projective planes of order 81, as described in chapter 5, led to the problem of identifying a projective plane (which turned out to be the one of Coulter and Matthews [CM97]). From the attempt to construct the full automorphism group of the projective plane and to find the defining planar polynomial, arguments for the classification of planar mono- mials in general were derived. The result is a theorem which classifies the projective planes defined by planar monomials and determines the full auto- morphism group for each of them. This part was done in cooperation with Prof. Dempwolff and is submitted to “Innovations in Incidence Geometry” [DR]. Finally, some open problems and possibilities for further work in this field are discussed.

Most of the functionality needed for the computational part of this text is implemented as aGAPpackage called “RDS” and is freely available from the “Packages” section of theGAPashom60dohT.]gape¨R[eatntnwiompeimele done such that relative difference sets withλ >–which do not play a role1 in thesis– can also be studied.

I would like to thank several people and institutions for their support. Prof. Dr. Dempwolff for giving me the chance to write this dissertation and for his advice in doing so. The state Rhineland-Palatinate for supporting my work with a scholarship. The University of Kaiserslautern, especially the Department of Mathematics and the RHRK for letting me use their Computers and other infrastructure. And all my friends and family for their support during this time.

2

Contents

Preface

1

2

3

4

1

General theory 6 1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Ordinary difference sets . . . . . . . . . . . . . . . . . . . . . 7 1.3 Relative difference sets . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Quotient images and signatures . . . . . . . . . . . . . . . . . 13 1.5 Central collineations of projective planes . . . . . . . . . . . . 17

Representation theoretic methods 2.1 Difference sets in extensions of C s ⋉C q . . . . . . . . . . . . .

Quasiregular relative difference sets 3.1 Ordinary difference sets:DP a . . . . . . .. . . . . . . . . . . 3.2 The caseDP b . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 CaseDP c  . . . . . . . . . . . , translation planes .. . . . . . . 3.4DP d  . . . . . . . . . . . . . . . . . . . .: Affine difference sets 3.5 The caseDP e . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 TypeDP f : direct product difference sets . . . . . . . . . . . . 3.7 TypeDP g . . . . . . . . . . . . . . . . . . . . . .  .: Neofields 3.8 Concluding theorem . . . . . . . . . . . . . . . . . . . . . . .

Implementation 4.1 Calculation of admissible signatures . . . . . . . . . . . . . . . 4.2 Startsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Brute force . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Tests for the isomorphism class of projective planes . . . . . .

3

20 22

26 28 29 32 33 33 34 35 36

38 38 43 45 46

CONTENTS

5 Computer aided experiments in higher order 51 5.1 TypeDP b . . . . . . . . . . . . . . .  52 .and a Baer involution

6 A result on planar functions 56 6.1 Planar monomials . . . . . . . . . . . . . . . . . . . . . . . . . 57

Future work

A The planes of order16and type DP b

63

65

B SomeGAPprograms 71 B.1 A simple example: CaseDP d . . . . . . . . . .  71. . . . . . . . B.2 CaseDP b . . . . . . . . . . . . . . .  72. . . . . . . . . . . . . .

4

List

of

Algorithms

1 New startsets for caseDP b  31. . . . . . . .. . . . . . . . . . . . 2 General idea for finding difference sets . . . . . . . . . . . . . 39 3 Calculation of admissible signatures for relative difference sets 40 4 Test for signatures of relative difference sets with forbidden subgroup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5 Calculation of ordered signatures for extensions of C s ⋉C q  42. . 6 Generate startsets . . . . . . . . . . . . . . . . . . . . . . . . . 43 7 Remaining completions . . . . . . . . . . . . . . . . . . . . . . 44 8 Signatures of partial difference sets . . . . . . . . . . . . . . . 44 9 Reduction of startsets . . . . . . . . . . . . . . . . . . . . . . 46 10 Brute force generation of difference sets . . . . . . . . . . . . . 47 11 Fano counter . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5

Chapter

General

1.1

1

theory

Notation

LetDbe an incidence structure andpa point ofD [. Thenp] denotes the set of blocks ofDincident withp. Analogously, for a blockB, the set of points incident withBis denoted by [B]. We will also identify blocks with point sets writingB={p 1      p n }= [B a set]. For{a 1      a n }of points (blocks), [a 1      a n ] is the set of blocks (points) incident with all ofa 1      a n . When talking about projective planes, blocks will also be called lines. Letpbe a point andBa block of an incidence structureD. The pair (p B) is called aflagifpis incident withBandanti-flagotherwise. The set of all prime numbers will be denoted byP groups and. All incidence structures are assumed to be finite. Forn∈N, the cyclic group of ordernis denoted by C n . Forp∈Pandn∈Nthe elementary abelian group of orderp n is denoted by E p n  a group. ForG, let Aut(G) denote the group of automorphisms and Aut ◦ (G) the group of automorphisms and anti-automorphisms.

1.1 Definition.LetMbe a set and:M→N, the pair (M ) is called a multiset all. Form∈M, the number(m) is calledmultiplicityofm. LetMbe a set andn∈N. Letm∈M n and letm˜ :={x∈M|x∈m} be the set containing the entries of the tuplem. Furthermore, let ˜m : ˜m→N mapx∈mon o ˜ t the number of timesxoccurs in thenn-tuplem. Then kmk= (m˜  m˜ ) is the multiset ofm. Loosely speaking, amultisetwhich may contain the same elementis a set several times. ForM⊆N(or any totally ordered set) with|M|<∞, the

6

1.2. ORDINARY DIFFERENCE SETS

multiset (M ) can be identified with the tuple (m 1      m n ) wherem i ≤ m i+1 for all 1≤i < n= P m∈M (m finite multisets may be compared). So pointwise.

1.2 Ordinary

difference sets

1.2 Definition.Let 1< n set Aand G a finite group.D⊆Gwithk=|D| is calleddifference setof ordern=k−λ, if for all 16=g∈Gthere exist exactlyλpairs (a b)∈D×Dsuch thatab −1 =g difference set. ADis called (v k λ)-difference set forv=|G|.

The following observations show the connection between difference sets and projective planes.

1.3 Lemma.LetD⊆Gbe a(v k λ) also-difference set. ThenD −1 is a (v k λ) for every-difference set. In other words:16=g∈Gthere are exactly λpairs(d 1  d 2 )∈D×Dwithg=d 1 −1 d 2 and exactlyλpairs(d 3  d 4 )∈D×D withg=d 3 d 4 −1 . Proof.First, letaD=bD. Then there are exactly|D|=k > λpairs (d 1  d 2 )∈D 2 such thatb −1 a=d 1 d 2 −1 holds. Hencea=b. Now let 16=g∈G there are exactly. Thenλsolutions ford 1 d 2 −1 =g, i.e. |D∩gD|=λ (. SoD{gD|g∈G}) is a symmetric (v k λ)-design. We may assume 1∈Dwithout loss of generality. 1 is contained Then exactly in the blocksd −1 Dwhered∈D. By the same argumentg6= 1 is contained exactly in the blocksgd −1 Dwithd∈D. But|[1]∩[g]|=λand so there are exactlyλpairs (d 1  d 2 )∈D 2 satisfying d 1 −1 D=gd 2 −1 D and exactlyλpairs (d 1  d 2 )∈D 2 satisfying −1 d 1 −1 =gd 2

1.4 Corollary.LetD⊆Gbe a(v k λ)-difference set andg h∈G. Fur- thermore, letd 1 i d 2 − i 1 =gh −1 be the presentations as quotients inDwith d 1 i  d 2 i ∈Dand1≤i≤λ. Thengandhare connected exactly by the lines Dd 2 − i 1 hwith1≤i≤λ.

7

CHAPTER 1. GENERAL THEORY

Proof.Obviouslyg∈Dd 2 −1 h. On the other han 2 − i 1 h=h. And asd 1 g=d 2 h⇐⇒ i gh −1 =d 1 −1 d 2 seheeaarllt d,D l d i 2 − n i 1 e h s c ∋ on d n 1 i e d ctinghto g.

1.5 Definition.LetGbe a group andD⊆G. DefineB={Dg|g∈G}, then the incidence structure devD:= (G B∈) is calleddevelopment ofD. 1.6 Theorem.LetGbe a group andD⊆Ga(n 2 +n+ 1 n+ 11)-difference set. ThendevDis a projective plane of ordern. Via right multiplication,Gdefines a group of collineations ofdevDacting regularly on points and blocks.

Proof.Letx y∈Gwithx6=y definition and 1.3 there is exactly one. By pair (d 1  d 2 )∈D×Dsatisfyingyx −1 =d 1 −1 d 2 and henceyd 1 =d 2 x the. So blocksxDandyDhave exactly one point in common. Now letx y∈G there is exactly one pair Again,be distinct points. (d 3  d 4 )∈D×Dwithxy −1 =d 3 d 4 −1 . Setz=d 4 −1 y, thenx=d 3  d 4 −1 y=d 3 z andy=d 4 z. Hence the blockDzcontains the pointsxandy. Letg∈G there are exactly. Then|D|blocks incident withg(asGacts regularly). For the same reason all blocks have size|D|.

1.7 Definition.LetDbe a design and letG≤Aut(D) act regularly on the points and blocks ofD. ThenGis calledSinger groupofD.

An important tool in the study of difference sets is the presentation as elements of the group ringZ[G]. This is done as follows:

: Pot(G)→Z[G] b M7→ X v g g g∈G

wherev g :=χ M (g)

whereχ M denotes the characteristic function ofM there is no risk of. If confusion, we identifyDwith its image underband writeD= P g∈G v g g. Define D −1 : = X v g g −1 g∈G |D|: = X v g g∈G

8

1.3. RELATIVE DIFFERENCE SETS

So difference sets may also be defined by the equation DD −1 =n1 +λG

Letϕ:G→Hbe an epimorphism with kerϕ=U. Thenϕis canonically lifted to the group ring by (1.7.1)  X v g g  ϕ = X v g g ϕ 

Then

(1.7.2)

(DD −1 )n1 ϕ +λ(G b ) ϕ =n1 ϕ +λ|U|H ϕ =

Note.As the same letter is used for the l b ifted and the origin c al homomor- phism, the problem arises that in general(G) ϕ is not equal toG ϕ  in this. So case, thbot be omitted. e may n Ifϕ:G→1is the trivial homomorphism, andD∈Z[G], thenDϕ= |D| 1 =k.

1.3 Relative difference sets

1.8 Definition.LetGbe a finite group and 1∈N⊆G. ThenD⊆G withk=|D|is calledrelative difference set with forbidden setN, if for some λ∈Nthe following equation inZ[G] holds: DD −1 =k+λ(G−N)

Dis called (|G||N||N| k λ)-difference set.

Note that|G||N| may be inconvenient Thisisn’t necessarily an integer. but as this notation is customary forN≤G, we will also use it in the general case.

Note.(a)Sometimes, difference sets with1∈Dare called “regular” dif- ference sets. For the ease of notation, we do only consider regular difference sets.

(b)Relative difference sets withN={1}are ordinary difference sets as defined on page 7.

9