gap> # gap> # ===================================================================== gap> # gap> # gap> # Yet another design classification gap> # --------------------------------- gap> # gap> # We classify the simple 2-(13,3,2) designs that are invariant gap> # under a group of odd order. gap> # gap> v:=13; 13 gap> k:=3; 3 gap> lambda:=2; 2 gap> G:=SymmetricGroup([1..v]); Sym( [ 1 .. 13 ] ) gap> CC:=List(ConjugacyClasses(G),x->Subgroup(G,[Representative(x)]));; gap> # gap> # Note that if H and K are conjugate subgroups of G then gap> # every K-invariant 2-(v,k,lambda) design is isomorphic to some gap> # H-invariant 2-(v,k,lambda) design. gap> # gap> CC:=Filtered(CC,x->IsPrimeInt(Size(x)) and Size(x)>2);; gap> # gap> # Thus, every (simple) 2-(v,k,lambda) design invariant under gap> # a group of odd order will be isomorphic to some (simple) gap> # 2-(v,k,lambda) design invariant under some H in CC. gap> # gap> designs:=[]; [ ] gap> for H in CC do > D := BlockDesigns( rec( v:=v, blockSizes:=[k], > blockMaxMultiplicities:=[1], # since we only want simple designs > tSubsetStructure:=rec(t:=2, lambdas:=[2] ), > requiredAutSubgroup:=H, > isoGroup:=Normalizer(G,H) # for efficiency > ) );; > Print("\n",H," ",Length(D),"\n"); > Append(designs,D); > od; Group( [ (1,2,3) ] ) 0 Group( [ (1,2,3)(4,5,6) ] ) 0 Group( [ (1,2,3)(4,5,6)(7,8,9) ] ) 344 Group( [ ( 1, 2, 3)( 4, 5, 6)( 7, 8, 9)(10,11,12) ] ) 43698 Group( [ (1,2,3,4,5) ] ) 0 Group( [ ( 1, 2, 3, 4, 5)( 6, 7, 8, 9,10) ] ) 0 Group( [ (1,2,3,4,5,6,7) ] ) 3 Group( [ ( 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11) ] ) 0 Group( [ ( 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13) ] ) 7 gap> Length(designs); 44052 gap> designs:=BlockDesignIsomorphismClassRepresentatives(designs);; gap> Length(designs); 44012 gap> Collected(List(designs,AllTDesignLambdas)); # a check [ [ [ 52, 12, 2 ], 44012 ] ] gap> Collected(List(designs,x->Size(AutomorphismGroup(x)))); [ [ 3, 43588 ], [ 6, 333 ], [ 9, 10 ], [ 12, 45 ], [ 13, 3 ], [ 18, 5 ], [ 24, 12 ], [ 36, 2 ], [ 39, 2 ], [ 42, 1 ], [ 48, 3 ], [ 54, 1 ], [ 72, 1 ], [ 96, 1 ], [ 144, 1 ], [ 156, 1 ], [ 168, 2 ], [ 5616, 1 ] ] gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The FinInG package gap> # ------------------ gap> # gap> # FinInG is a large and powerful GAP package for gap> # Finite Incidence Geometry. It requires the GAP packages gap> # GAPDoc, IO, Forms, cvec, Orb, GenSS, and GRAPE. gap> # gap> LoadPackage("fining"); ───────────────────────────────────────────────────────────────────────────── Loading cvec 2.7.4 (Compact vectors over finite fields) by Max Neunhöffer (http://www-groups.mcs.st-and.ac.uk/~neunhoef). maintained by: Max Horn (https://www.quendi.de/math). Homepage: https://gap-packages.github.io/cvec Report issues at https://github.com/gap-packages/cvec/issues ───────────────────────────────────────────────────────────────────────────── ------------------------------------------------------------------------------- ______________ ________ _________ __________ __ ___ ____/__(_)__________ _/________ ____/ __< /_ // / __ /_ __ /__ __ __ / __ __ / __ __ /_ // /_ _ __/ _ / _ / / /_/ / _ / / / /_/ / _ /_/__ __/ /_/ /_/ /_/ /_//___/ /_/ /_/____/ /_/_(_)/_/ ------------------------------------------------------------------------------- Loading FinInG 1.4.1 (Finite Incidence Geometry) by John Bamberg (http://school.maths.uwa.edu.au/~bamberg/) Anton Betten (http://www.math.colostate.edu/~betten) Jan De Beule (http://www.debeule.eu) Philippe Cara (http://homepages.vub.ac.be/~pcara) Michel Lavrauw (http://people.sabanciuniv.edu/~mlavrauw/) Max Neunhoeffer (http://www-groups.mcs.st-and.ac.uk/~neunhoef/) For help, type: ?FinInG --------------------------------------------------------------------- true gap> # gap> # A (finite) *incidence structure* consists of a finite set of gap> # *elements*, a reflexive symmetric *incidence* relation on the gap> # set of elements, and a function, called a *type* function, from the gap> # set of elements to a finite set of *types*, such that no two gap> # distinct elements having the same type are incident. gap> # gap> # An *incidence geometry* is an incidence structure such that gap> # every maximal set of pairwise incident elements contains an gap> # element of each type. gap> # gap> # gap> # FinInG provides efficient functionality for constructing and studying gap> # the following incidence structures: gap> # gap> # - projective and affine spaces gap> # gap> # - classical polar spaces gap> # gap> # - generalised polygons gap> # gap> # - coset incidence structures. gap> # gap> # gap> # FinInG also provides functionality for: gap> # gap> # - groups of automorphisms of incidence structures gap> # gap> # - specialised actions, orbits and stabilizers gap> # gap> # - morphisms of incidence geometries gap> # gap> # - algebraic varieties over finite fields. gap> # gap> # gap> # The FinInG manual includes much more information and many useful gap> # examples. See, in particular, Chapter 2. gap> # gap> # gap> # In this minicourse, we look into some FinInG functionality gap> # for projective spaces and coset incidence structures, gap> # concentrating on some applications by the minicourse lecturer. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The projective space PG(n,q) gap> # ---------------------------- gap> # gap> # gap> # Let V be an (n+1)-dimensional vector space over the gap> # finite field GF(q). gap> # gap> # In FinInG, the *projective space* PG(n,q) is the incidence gap> # geometry whose elements are the proper non-zero subspaces of V, gap> # with two elements being incident iff one is contained in the other, gap> # and having the same type iff they have the same dimension. gap> # gap> # The *points* and *lines* of PG(n,q) are respectively the gap> # 1- and 2-dimensional subspaces of V. gap> # gap> # gap> # Sample calculation in a projective space gap> # ---------------------------------------- gap> # gap> d:=4; 4 gap> q:=9; 9 gap> pg:=PG(d,q); ProjectiveSpace(4, 9) gap> IsIncidenceStructure(pg); true gap> IsLieGeometry(pg); true gap> IsProjectiveSpace(pg); true gap> Dimension(pg); 4 gap> Rank(pg); 4 gap> TypesOfElementsOfIncidenceStructure(pg); [ "point", "line", "plane", "solid" ] gap> lines:=Lines(pg); gap> lines=ElementsOfIncidenceStructure(pg,2); true gap> IsCollection(lines); true gap> IsList(lines); false gap> Size(lines); 605242 gap> points:=Points(pg); gap> IsCollection(points); true gap> Size(points); 7381 gap> point:=Enumerator(points)[1]; gap> line:=Enumerator(lines)[1]; gap> point*line; true gap> line*point; true gap> obj:=UnderlyingObject(point); gap> Unpack(obj); [ Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ] gap> obj:=UnderlyingObject(line); gap> Unpack(obj); [ [ Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ] ] gap> P:=ProjectivityGroup(pg); The FinInG projectivity group PGL(5,9) gap> Size(P); 78660280796419613491200 gap> C:=CollineationGroup(pg); The FinInG collineation group PGammaL(5,9) gap> Size(C); 157320561592839226982400 gap> # gap> # ===================================================================== gap> # gap> # gap> # Computation of partial spreads gap> # ------------------------------ gap> # gap> # gap> # A *partial spread* of lines in a projective space is a set of lines gap> # whose pairwise intersection is the zero-subspace (projectively, gap> # the *empty subspace*). gap> # gap> # gap> # We now use FinInG and GRAPE to classify the maximal partial spreads gap> # of lines in the projective space PG(3,4), first, up to the action gap> # of the projective general linear group PGL(4,4), and then, up to gap> # the action of the full collineation group PGammaL(4,4) of the space. gap> # gap> d:=3; 3 gap> q:=4; 4 gap> pg:=PG(d,q); ProjectiveSpace(3, 4) gap> TypesOfElementsOfIncidenceStructure(pg); [ "point", "line", "plane" ] gap> lines:=Lines(pg); gap> Size(lines); 357 gap> points:=Points(pg); gap> Size(points); 85 gap> lineset:=Set(List(lines));; gap> G:=ProjectivityGroup(pg); The FinInG projectivity group PGL(4,4) gap> Size(G); 987033600 gap> # gap> # Now construct the graph gamma, whose vertices are labelled gap> # by the lines of PG(3,4), with two vertices joined by an edge gap> # iff the corresponding lines have no point in common. gap> # gap> gamma := Graph(G, lineset, OnProjSubspaces, > function(x,y) return Meet(x,y)=EmptySubspace(pg); end, > true);; gap> GlobalParameters(gamma); [ [ 0, 0, 256 ], [ 1, 180, 75 ], [ 192, 64, 0 ] ] gap> Size(gamma.group); 987033600 gap> maximalpartialspreads := CompleteSubgraphs(gamma,-1,2); [ [ 1, 29, 48, 73, 108, 114, 124, 146, 180, 229, 255, 276, 318 ], [ 1, 29, 48, 73, 108, 114, 132, 142, 166, 239, 252, 255, 270, 337 ], [ 1, 29, 48, 73, 108, 114, 133, 146, 208, 270, 300 ], [ 1, 29, 48, 73, 108, 114, 142, 166, 207, 229, 238, 295, 331 ], [ 1, 29, 48, 73, 108, 114, 146, 162, 208, 270, 295 ], [ 1, 29, 48, 73, 108, 114, 146, 166, 180, 234, 252, 317 ], [ 1, 29, 48, 73, 108, 124, 146, 181, 215, 252, 318 ], [ 1, 29, 48, 73, 108, 124, 208, 239, 252, 259, 273, 352 ], [ 1, 29, 48, 73, 108, 126, 133, 146, 208, 261, 284, 300, 315 ], [ 1, 29, 48, 73, 108, 126, 133, 181, 244, 261, 274, 318, 343 ], [ 1, 29, 48, 73, 108, 126, 142, 166, 207, 246, 261, 273, 284, 331 ], [ 1, 29, 48, 73, 108, 126, 149, 160, 185, 194, 238, 252, 255, 352 ], [ 1, 29, 48, 73, 108, 129, 133, 146, 181, 229, 234, 276, 295, 318 ], [ 1, 29, 48, 73, 108, 129, 133, 146, 229, 234, 276, 295, 317 ], [ 1, 29, 48, 73, 108, 129, 142, 162, 208, 259, 295 ], [ 1, 29, 48, 73, 108, 129, 149, 160, 189, 207, 295, 317, 351 ], [ 1, 29, 48, 73, 108, 132, 143, 179, 198, 215, 234 ], [ 1, 29, 48, 73, 108, 166, 207, 246, 273, 317, 331 ], [ 1, 29, 48, 73, 110, 124, 146, 176, 208, 275, 284, 315, 348 ], [ 1, 29, 48, 73, 110, 124, 176, 198, 269, 275, 315, 351 ], [ 1, 29, 48, 73, 110, 126, 146, 166, 176, 185, 194, 246, 251, 255, 284, 336, 348 ], [ 1, 29, 48, 73, 110, 128, 147, 181, 198, 215, 239, 269, 351 ], [ 1, 29, 48, 73, 110, 129, 176, 198, 227, 239, 255, 274, 291 ], [ 1, 29, 48, 73, 110, 129, 176, 244, 259, 274, 295, 317, 348 ], [ 1, 29, 48, 73, 115, 126, 146, 167, 176, 208, 300, 336, 355 ], [ 1, 29, 48, 73, 115, 128, 143, 167, 180, 207, 215, 238, 259, 308, 317, 336, 351 ], [ 1, 29, 48, 73, 115, 129, 149, 167, 176, 239, 255, 337, 351 ], [ 1, 29, 48, 73, 115, 129, 149, 167, 176, 239, 255, 337, 355 ], [ 1, 29, 48, 73, 129, 149, 167, 176, 186, 207, 213, 225, 234, 276, 291, 295, 317 ] ] gap> # The maximal complete subgraphs of gamma, up to the action gap> # of gamma.group. See ?CompleteSubgraphs. gap> # gap> Collected(List(maximalpartialspreads,Length)); [ [ 11, 6 ], [ 12, 3 ], [ 13, 13 ], [ 14, 4 ], [ 17, 3 ] ] gap> VertexNames(gamma){maximalpartialspreads[1]}; [ , , , , , , , , , , , , ] gap> # gap> # Repeat the classification with G now being the collineation gap> # group of pg. gap> # gap> old_maximalpartialspreads:=maximalpartialspreads;; gap> G:=CollineationGroup(pg); The FinInG collineation group PGammaL(4,4) gap> Size(G); 1974067200 gap> hom:=ActionHomomorphism(G,VertexNames(gamma),OnProjSubspaces); gap> gamma:=NewGroupGraph(Image(hom),gamma);; gap> Size(gamma.group); 1974067200 gap> Size(AutomorphismGroup(gamma)); 3948134400 gap> maximalpartialspreads := CompleteSubgraphs(gamma,-1,2);; gap> Collected(List(maximalpartialspreads,Length)); [ [ 11, 4 ], [ 12, 2 ], [ 13, 8 ], [ 14, 3 ], [ 17, 3 ] ] gap> Collected(List(old_maximalpartialspreads,Length)); [ [ 11, 6 ], [ 12, 3 ], [ 13, 13 ], [ 14, 4 ], [ 17, 3 ] ] gap> # gap> # Let's do a check using SmallestImageSet. gap> # gap> smallest_maximalpartialspreads := > Set( List(old_maximalpartialspreads, > mps->SmallestImageSet(gamma.group,mps)) ); [ [ 1, 29, 48, 65, 78, 108, 114, 124, 146, 208, 226, 247, 346 ], [ 1, 29, 48, 65, 78, 108, 114, 124, 146, 208, 247, 318, 346 ], [ 1, 29, 48, 65, 78, 108, 114, 124, 146, 226, 238, 320, 346 ], [ 1, 29, 48, 65, 78, 108, 114, 124, 146, 229, 238 ], [ 1, 29, 48, 65, 78, 108, 114, 124, 146, 320, 349 ], [ 1, 29, 48, 65, 78, 108, 114, 127, 142, 166, 207, 229, 238, 266, 272, 295, 331 ], [ 1, 29, 48, 65, 78, 108, 114, 127, 142, 208, 266, 272, 295, 332 ], [ 1, 29, 48, 65, 78, 108, 114, 127, 166, 185, 238, 266, 295, 346 ], [ 1, 29, 48, 65, 78, 108, 114, 127, 179, 184, 207, 244, 295 ], [ 1, 29, 48, 65, 78, 108, 114, 127, 179, 207, 244, 266, 295 ], [ 1, 29, 48, 65, 78, 108, 124, 146, 178, 208, 226, 247, 261, 273, 284, 315, 346 ], [ 1, 29, 48, 65, 78, 108, 124, 146, 178, 229, 247, 284, 315 ], [ 1, 29, 48, 65, 78, 108, 124, 146, 178, 229, 247, 284, 349 ], [ 1, 29, 48, 65, 78, 108, 127, 142, 208, 218, 284, 332 ], [ 1, 29, 48, 65, 78, 108, 127, 179, 184, 207, 244, 315 ], [ 1, 29, 48, 65, 78, 108, 127, 179, 207, 244, 266, 273, 315 ], [ 1, 29, 48, 65, 78, 108, 127, 179, 208, 244, 266, 273, 315, 346 ], [ 1, 29, 48, 65, 78, 110, 127, 166, 185, 266, 295 ], [ 1, 29, 48, 65, 78, 114, 132, 184, 247, 259, 302 ], [ 1, 29, 48, 73, 129, 149, 167, 176, 186, 207, 213, 225, 234, 276, 291, 295, 317 ] ] gap> Collected(List(smallest_maximalpartialspreads,Length)); [ [ 11, 4 ], [ 12, 2 ], [ 13, 8 ], [ 14, 3 ], [ 17, 3 ] ] gap> smallest_maximalpartialspreads = > Set( List(maximalpartialspreads, > mps->SmallestImageSet(gamma.group,mps)) ); true gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Coset incidence structures in FinInG gap> # ------------------------------------ gap> # gap> # Let gamma be an incidence structure. gap> # gap> # A *flag* of gamma is a set of pairwise incident elements, gap> # and the *type* of a flag is the set of the types of its elements. gap> # gap> # A *chamber* of gamma is a flag containing an element of each type. gap> # gap> # The *residue* of a flag F of gamma is the incidence structure gap> # induced by gamma on the set of elements of gamma not in F, gap> # but incident with every element of F. gap> # gap> # An *automorphism* of gamma is a permutation phi of the elements gap> # of gamma preserving the type of each element and preserving incidence gap> # between elements. gap> # gap> # The incidence structure gamma is a *flag-transitive geometry* for gap> # a group G of automorphisms of gamma if gamma is an incidence gap> # geometry and G acts transitively on the set of chambers gap> # (and so G acts transitively on the flags of any given type). gap> # gap> # Suppose now gamma is a flag-transitive geometry for a group G of gap> # automorphisms. Consider a chamber {c_1,c_2,...,c_n} of gamma, gap> # such that c_i has type i, and let G_i be the stabilizer in G gap> # of c_i. Now G acts transitively on the elements of gap> # type i, so these elements are in 1-to-1 correspondence with the gap> # right cosets of G_i in G. Furthermore, two elements of gap> # gamma are incident if and only if the corresponding cosets have a gap> # nonempty intersection. gap> # gap> # Now let G be any finite group and let G_1,...,G_n be gap> # distinct subgroups of G. Then these determine an incidence gap> # structure called a *coset incidence structure* for G, with gap> # type set {1,...,n}, the elements of type i being the right cosets gap> # of G_i in G, and with two elements being incident precisely when they gap> # have nonempty intersection. gap> # gap> # A coset incidence structure need not be an incidence geometry. gap> # However, in FinInG, if the function IsFlagTransitiveGeometry applied gap> # to a coset incidence structure returns true, this guarantees that gap> # the argument is a (flag-transitive) incidence geometry. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # A flag-transitive geometry for M_{24} gap> # ------------------------------------- gap> # gap> # As an example, we now use FinInG to build a certain coset incidence gap> # structure for M_{24} and to determine the "diagram" of this well-known gap> # flag-transitive incidence geometry. gap> # gap> # gap> parabolics:=[]; [ ] gap> for i in [1..4] do > parabolics[i]:=Stabilizer(M24,[1..i],OnSets); > od; gap> octad1; [ 1, 2, 3, 4, 5, 8, 11, 13 ] gap> Add(parabolics,Stabilizer(M24,octad1,OnSets)); gap> List(parabolics,x->Size(M24)/Size(x)); [ 24, 276, 2024, 10626, 759 ] gap> gap> M24geom:=CosetGeometry(M24,parabolics); CosetGeometry( Group( [ ( 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23), ( 3,17,10, 7, 9)( 4,13,14,19, 5)( 8,18,11,12,23)(15,20,22,21,16), ( 1,24)( 2,23)( 3,12)( 4,16)( 5,18)( 6,10)( 7,20)( 8,14)( 9,21)(11,17) (13,22)(15,19) ] ) ) gap> # gap> # In FinInG, CosetGeometry makes a coset incidence structure. gap> # gap> IsFlagTransitiveGeometry(M24geom); true gap> # gap> # So M24geom is a flag-transitive incidence geometry. gap> # gap> TypesOfElementsOfIncidenceStructure(M24geom); [ 1 .. 5 ] gap> IsConnected(M24geom); true gap> IsThickGeometry(M24geom); false gap> IsFirmGeometry(M24geom); true gap> Size(BorelSubgroup(M24geom)); 192 gap> C:=StandardFlagOfCosetGeometry(M24geom);; gap> IsChamberOfIncidenceStructure(C); true gap> Type(C); [ 1, 2, 3, 4, 5 ] gap> F:=FlagOfIncidenceStructure(M24geom, > Filtered(ElementsOfFlag(C),c->Type(c) in [1..3]));; gap> Type(F); [ 1, 2, 3 ] gap> R:=ResidueOfFlag(F); CosetGeometry( Group( [ ( 4, 9, 6)( 5,14,12)(10,21,13)(11,18,17)(15,16,23)(20,22,24), ( 5,11,13)( 6, 9,19)(10,23,12)(14,15,17)(16,21,18)(20,22,24), ( 4,13)( 5,11)( 6,12)( 9,18)(10,14)(15,19)(16,23)(17,21), ( 4,11)( 5,13)( 6,12)( 7,22)( 9,10)(14,18)(17,21)(20,24), ( 4,24,17)( 5,20, 6)( 7,21,13)( 9,18,14)(11,22,12)(15,23,16), ( 4,11,16)( 5,10,20)( 7,15,22)( 8,21,17)( 9,13,24)(14,18,23), ( 4,11,14,17)( 5,20)( 6,10)( 7,22,18,21)( 8,12,23, 9)(13,15,24,16) ] ) ) gap> IsCosetGeometry(R); true gap> IsFlagTransitiveGeometry(R); true gap> IsConnected(R); true gap> Rank2Parameters(R); [ [ 3, 3, 3 ], [ 4, 21 ], [ 4, 21 ] ] gap> # gap> # FinInG can draw the "diagram" of a flag-transitive coset gap> # geometry, making use of GraphViz. gap> # gap> DrawDiagram(DiagramOfGeometry(M24geom),"M24geomdiagram"); gap> incidencegraph:=IncidenceGraph(M24geom);; gap> IsGraph(incidencegraph); true gap> Size(incidencegraph.group)=Size(M24); true gap> Length(incidencegraph.representatives); 5 gap> orbs:=Set(List(OrbitsDomain(incidencegraph.group, > Vertices(incidencegraph)),Set));; gap> List(orbs,Length); [ 24, 276, 2024, 10626, 759 ] gap> autM24geom:=AutGroupIncidenceStructureWithNauty(M24geom); gap> autM24geom=AutomorphismGroup(rec(graph:=incidencegraph,colourClasses:=orbs)); true gap> Size(autM24geom)/Size(M24); 1 gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Some more complicated applications of GAP, GRAPE, DESIGN, and FinInG gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # A flag-transitive geometry for J_2 and J_2.2 gap> # ----------------------------------------------- gap> # gap> # gap> # We now use GRAPE and FinInG to construct a flag-transitive gap> # geometry for the sporadic simple Hall-Janko group J_2 and its gap> # automorphism group J_2.2. gap> # gap> # As far as I am aware, this geometry has never been published. gap> # gap> n:=280; 280 gap> L:=AllPrimitiveGroups(NrMovedPoints,n,Size,604800,IsSimple,true); [ J_2 ] gap> J2:=L[1]; J_2 gap> H:=Stabilizer(J2,1); gap> orbs:=Set( List(Orbits(H,[1..n]),Set) );; gap> List(orbs,Length); [ 1, 108, 36, 135 ] gap> edge:=[1,First(orbs,x->Length(x)=36)[1]]; [ 1, 3 ] gap> gamma:=EdgeOrbitsGraph(J2,[edge]);; gap> GlobalParameters(gamma); [ [ 0, 0, 36 ], [ 1, 8, 27 ], [ 4, 32, 0 ] ] gap> AssignVertexNames(gamma,[1..n]); gap> f:=First(orbs,orb->Length(orb)=135)[1]; 4 gap> eps:=GeodesicsGraph(gamma,1,f); rec( adjacencies := [ [ 2, 4 ] ], group := Group([ (2,4), (2,4), (1,2,3,4), (1,3) ]), isGraph := true, isSimple := true, names := [ 3, 118, 223, 265 ], order := 4, representatives := [ 1 ], schreierVector := [ -1, 3, 4, 1 ] ) gap> GlobalParameters(eps); [ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ] gap> oct_vertices:=Union([1,f],VertexNames(eps)); [ 1, 3, 4, 118, 223, 265 ] gap> D:=Stabilizer(J2,oct_vertices,OnSets);; gap> Size(D); 96 gap> oct_graph:=InducedSubgraph(gamma,oct_vertices,D); rec( adjacencies := [ [ 2, 4, 5, 6 ] ], group := Group([ (4,6), (4,6), (2,4)(5,6), (1,2)(3,5)(4,6) ]), isGraph := true, isSimple := true, names := [ 1, 3, 4, 118, 223, 265 ], order := 6, representatives := [ 1 ], schreierVector := [ -1, 4, 4, 3, 3, 1 ] ) gap> GlobalParameters(oct_graph); [ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ] gap> Size(oct_graph.group); 48 gap> # gap> # oct_graph is our chosen special induced subgraph of gamma, gap> # and is isomorphic to (the 1-skeleton of) an octahedron. gap> # gap> K:=CompleteSubgraphsOfGivenSize(oct_graph,3,2); [ [ 1, 2, 4 ] ] gap> clique:=Set(List(K[1],x->VertexName(oct_graph,x))); [ 1, 3, 118 ] gap> # gap> # Now clique is the set of vertices in gamma of a triangle gap> # in oct_graph. gap> # gap> parabolics:=[]; [ ] gap> for i in [1..3] do > parabolics[i]:=Stabilizer(J2,clique{[1..i]},OnSets); > od; gap> Add(parabolics,D); gap> List(parabolics,x->Size(J2)/Size(x)); [ 280, 5040, 10080, 6300 ] gap> J2geom:=CosetGeometry(J2,parabolics); CosetGeometry( J_2 ) gap> IsFlagTransitiveGeometry(J2geom); true gap> Rank(J2geom); 4 gap> TypesOfElementsOfIncidenceStructure(J2geom); [ 1 .. 4 ] gap> IsThickGeometry(J2geom); false gap> IsFirmGeometry(J2geom); true gap> Size(BorelSubgroup(J2geom)); 2 gap> DrawDiagram(DiagramOfGeometry(J2geom),"J2geomdiagram"); gap> incidencegraph:=IncidenceGraph(J2geom);; gap> Size(incidencegraph.group); 604800 gap> Length(incidencegraph.representatives); 4 gap> orbs:=Set(List(OrbitsDomain(incidencegraph.group, > Vertices(incidencegraph)),Set));; gap> List(orbs,Length); [ 280, 5040, 10080, 6300 ] gap> autJ2geom:=AutGroupIncidenceStructureWithNauty(J2geom); gap> Size(autJ2geom); 1209600 gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # A nonsynchronizing group of degree 280 gap> # --------------------------------------- gap> # gap> # We now show that the image of the (faithful) action of autJ2geom gap> # (isomorphic to Aut(J_2) = J_2.2) on the 280 elements of type 1 in gap> # J2geom is nonsynchronizing. gap> # gap> n:=280; 280 gap> orbs[1]=[1..n]; true gap> autJ2:=Action(autJ2geom,orbs[1],OnPoints);; gap> L:=Filtered(GeneralizedOrbitalGraphs(autJ2),x->VertexDegrees(x)=[135]);; gap> Length(L); 1 gap> gamma:=L[1];; gap> omega:=CliqueNumber(gamma); 28 gap> # gap> # We prove that gamma is nonsynchronizing by showing that gap> # gamma has a proper vertex omega-colouring (invariant under gap> # a Sylow 7-subgroup of autJ2). Thus autJ2 is a nonsynchronizing gap> # primitive permutation group (and so is its derived subgroup gap> # isomorphic to J_2). gap> # gap> S:=SylowSubgroup(autJ2,7);; gap> delta:=ComplementGraph(gamma);; gap> blockreps:=CompleteSubgraphsOfGivenSize(delta,n/omega,2); [ [ 1, 4, 5, 17, 18, 23, 75, 76, 200, 201 ], [ 1, 4, 5, 18, 23, 30, 54, 62, 172, 229 ] ] gap> D:=BlockDesign(n,blockreps,delta.group);; gap> # gap> # Now the blocks of D are the co-cliques of gamma of size n/omega. gap> # gap> D.v; 280 gap> BlockSizes(D); [ 10 ] gap> AllTDesignLambdas(D); [ 13104, 468 ] gap> # gap> # Does D have an S-invariant spread, that is, an S-invariant gap> # 1-(280,10,1) subdesign? Let's find out. gap> # gap> P:=BlockDesigns(rec( v:=D.v, # number of points in each returned design > blockDesign:=D, # returned design(s) must be subdesigns of D > blockSizes:=BlockSizes(D), # possible block sizes in the returned design(s) > tSubsetStructure:=rec(t:=1, lambdas:=[1]), # for the returned design(s) > requiredAutSubgroup:=S, # returned design(s) must be S-invariant > isoGroup:=delta.group, # group determining design equivalence > isoLevel:=0)); # only require one design (if such exist) [ rec( autSubgroup := , blockNumbers := [ 28 ], blockSizes := [ 10 ], blocks := [ [ 1, 4, 9, 137, 138, 142, 179, 212, 233, 247 ], [ 2, 10, 23, 67, 121, 140, 155, 168, 232, 249 ], [ 3, 32, 42, 64, 84, 104, 125, 180, 206, 243 ], [ 5, 49, 60, 108, 118, 252, 256, 258, 259, 272 ], [ 6, 20, 91, 97, 106, 132, 173, 177, 181, 261 ], [ 7, 13, 25, 139, 144, 154, 156, 159, 176, 239 ], [ 8, 70, 105, 115, 149, 150, 178, 226, 234, 263 ], [ 11, 80, 109, 184, 202, 210, 215, 251, 260, 270 ], [ 12, 26, 51, 58, 93, 124, 126, 152, 192, 279 ], [ 14, 30, 48, 59, 77, 117, 123, 191, 227, 278 ], [ 15, 87, 88, 141, 147, 196, 209, 241, 255, 273 ], [ 16, 21, 29, 94, 98, 187, 204, 213, 248, 277 ], [ 17, 69, 129, 158, 201, 211, 214, 218, 236, 280 ], [ 18, 22, 28, 47, 54, 63, 89, 162, 174, 267 ], [ 19, 31, 33, 61, 73, 102, 145, 169, 172, 240 ], [ 24, 75, 134, 136, 165, 193, 216, 217, 225, 244 ], [ 27, 57, 71, 74, 79, 81, 83, 112, 222, 235 ], [ 34, 37, 143, 146, 157, 190, 199, 219, 265, 266 ], [ 35, 39, 82, 100, 161, 171, 194, 205, 264, 276 ], [ 36, 78, 90, 113, 120, 122, 130, 188, 189, 271 ], [ 38, 45, 65, 68, 96, 114, 148, 182, 220, 262 ], [ 40, 52, 56, 72, 76, 85, 135, 163, 185, 221 ], [ 41, 43, 62, 101, 153, 160, 166, 170, 246, 269 ], [ 44, 46, 103, 111, 119, 195, 200, 231, 238, 268 ], [ 50, 95, 99, 131, 164, 186, 198, 203, 242, 274 ], [ 53, 66, 107, 116, 127, 128, 183, 229, 257, 275 ], [ 55, 151, 175, 224, 228, 230, 237, 250, 253, 254 ], [ 86, 92, 110, 133, 167, 197, 207, 208, 223, 245 ] ], isBinary := true, isBlockDesign := true, isSimple := true, r := 1, tSubsetStructure := rec( lambdas := [ 1 ], t := 1 ), v := 280 ) ] gap> # gap> # Thus D has an S-invariant spread (parallel class), which gives gap> # us an omega-colouring of gamma. gap> # gap> partition:=P[1].blocks;; gap> colouring:=List(Vertices(gamma),v->First([1..Length(partition)], > i->v in partition[i]));; gap> # gap> # gap> # Let's double-check that this is an omega-colouring of gamma. gap> # gap> # gap> IsVertexColouring := function(gamma,C,k) > # > # Let gamma be a simple graph, let C be a dense list of positive > # integers of length OrderGraph(gamma), and let k be a non-negative > # integer. Then this function returns true if C is a proper > # vertex k-colouring of gamma, and returns false if not. > # > local v,w; > if not IsSimpleGraph(gamma) then > Error(" must be a simple graph"); > elif not (IsDenseList(C) and Length(C)=OrderGraph(gamma) and ForAll(C,IsPosInt)) then > Error(" must be a dense list of length OrderGraph() of positive integers"); > elif not (IsInt(k) and k>=0) then > Error(" must be a non-negative integer"); > fi; > if Length(Set(C))>k then > # too many colours > return false; > fi; > for v in Vertices(gamma) do > for w in Adjacency(gamma,v) do > if v if C[v]=C[w] then > # The adjacent vertices v and w have the same colour. > return false; > fi; > fi; > od; > od; > return true; > end; function( gamma, C, k ) ... end gap> gap> IsVertexColouring(gamma,colouring,omega); true gap> gap> # gap> # ===================================================================== gap> # gap> # gap> # Study of the Cohen-Tits near octagon gap> # ------------------------------------ gap> # gap> # There is a unique distance-regular graph with intersection array gap> # gap> # {10,8,8,2; 1,1,4,5}, gap> # gap> # that is, with global parameters gap> # gap> # [[0,0,10], [1,1,8], [1,1,8], [4,4,2], [5,5,0]]. gap> # gap> # This graph, of order 315 and diameter 4, is the point graph gap> # of the *Cohen-Tits near octagon*. The lines consist of all the gap> # 525 triangles (cliques of size 3) in the graph, which has the gap> # near polygon property that each point has minimal distance gap> # to a unique point on each line. gap> # gap> # See https://www.win.tue.nl/~aeb/graphs/HJ315.html gap> # gap> # We construct this point graph on the conjugacy class of involutions gap> # of autJ2 of size 315. gap> # gap> n:=315; 315 gap> CC:=Filtered(ConjugacyClasses(autJ2),x->Size(x)=n);; gap> Length(CC); 1 gap> CC:=CC[1];; gap> Order(Representative(CC)); 2 gap> pointgraph:=Graph(autJ2,AsSet(CC),OnPoints, > function(x,y) return x*y=y*x and x<>y; end, > true);; gap> GlobalParameters(pointgraph); [ [ 0, 0, 10 ], [ 1, 1, 8 ], [ 1, 1, 8 ], [ 4, 4, 2 ], [ 5, 5, 0 ] ] gap> # gap> # Now pointgraph is the point graph of the Cohen-Tits near octagon. gap> # gap> A:=AutomorphismGroup(pointgraph);; gap> A=pointgraph.group; true gap> RankAction(A,Vertices(pointgraph)); 5 gap> Diameter(pointgraph); 4 gap> Girth(pointgraph); 3 gap> names:=VertexNames(pointgraph);; gap> List(Layers(pointgraph,1),x->[Order(names[1]*names[x[1]]),Length(x)]); [ [ 1, 1 ], [ 2, 10 ], [ 4, 80 ], [ 3, 160 ], [ 5, 64 ] ] gap> m:=CliqueNumber(pointgraph); 3 gap> K:=CompleteSubgraphsOfGivenSize(pointgraph,m,2); [ [ 1, 3, 4 ] ] gap> nearoct:=BlockDesign(n,K,A);; gap> # gap> # Now nearoct is the Cohen-Tits near octagon as a block design gap> # in DESIGN package format. gap> # gap> nearoct.v; 315 gap> BlockSizes(nearoct); [ 3 ] gap> AllTDesignLambdas(nearoct); [ 525, 5 ] gap> dualnearoct:=DualBlockDesign(nearoct);; gap> dualnearoct.v; 525 gap> BlockSizes(dualnearoct); [ 5 ] gap> AllTDesignLambdas(dualnearoct); [ 315, 3 ] gap> # gap> # Does dualnearoct have a spread (parallel class)? gap> # gap> spreadsofdual := BlockDesigns(rec(v:=dualnearoct.v, > blockSizes:=BlockSizes(dualnearoct), > blockDesign:=dualnearoct, > tSubsetStructure:=rec(t:=1, lambdas:=[1]))); [ ] gap> # gap> # So the dual of nearoct has no 1-(525,5,1) subdesign, gap> # i.e. no spread. Equivalently, nearoct has no "ovoid". gap> # gap> # What about possible spreads and resolutions of nearoct? gap> # gap> # We shall first classify the spreads of nearoct invariant under gap> # a well-chosen subgroup S of its automorphism group A. gap> # gap> CC:=Set(ConjugacyClasses(A),x->Group(Representative(x)));; gap> S:=Filtered(CC,x->Size(x)=5 and Size(Centralizer(A,x))=300);; gap> Length(S); 1 gap> S:=S[1]; gap> # gap> # We now classify the S-invariant spreads of nearoct, up to the gap> # action of A. gap> # gap> spreads:=BlockDesigns(rec(v:=nearoct.v, > blockSizes:=BlockSizes(nearoct), > blockDesign:=nearoct, > isoGroup:=A, > requiredAutSubgroup:=S, > tSubsetStructure:=rec(t:=1, lambdas:=[1])));; gap> Length(spreads); 39 gap> # gap> # Now make each spread into a set of the indices of its blocks in nearoct. gap> # gap> spreads:=List(spreads,x->List(x.blocks, > B->PositionSorted(nearoct.blocks,B)));; gap> # gap> # We now make a graph whose vertices correspond to the spreads invariant gap> # under a conjugate in A of S, with two such spreads joined by an gap> # edge iff they are disjoint. gap> # gap> spreadsgraph:=Graph(Action(A,nearoct.blocks,OnSets), > spreads, > OnSets, > function(x,y) return Intersection(x,y)=[]; end);; gap> OrderGraph(spreadsgraph); 2645160 gap> List(spreadsgraph.representatives,x->VertexDegree(spreadsgraph,x)); [ 158, 179, 196, 248, 223, 173, 207, 832, 201, 269, 900, 327, 357, 212, 252, 226, 438, 179, 188, 1423, 176, 208, 173, 1432, 166, 395, 163, 312, 1879, 167, 327, 1369, 51, 53, 210, 383, 167, 1561, 4948 ] gap> Size(spreadsgraph.group); 1209600 gap> # gap> # Now a clique of size 5 in spreadsgraph would yield a resolution gap> # of nearoct. gap> # gap> res:=CompleteSubgraphsOfGivenSize(spreadsgraph,5,0)[1]; [ 606665, 1893146, 1911841, 2064670, 2090945 ] gap> # gap> # Let's convert res into a partition of the blocks of gap> # nearoct into partitions of the points. gap> # gap> res:=List(res,x->List(VertexName(spreadsgraph,x),y->nearoct.blocks[y]));; gap> res:=Set(res); [ [ [ 1, 3, 4 ], [ 2, 20, 21 ], [ 5, 156, 157 ], [ 6, 178, 179 ], [ 7, 56, 57 ], [ 8, 194, 195 ], [ 9, 31, 35 ], [ 10, 11, 18 ], [ 12, 306, 307 ], [ 13, 29, 34 ], [ 14, 228, 229 ], [ 15, 238, 239 ], [ 16, 256, 257 ], [ 17, 90, 91 ], [ 19, 74, 75 ], [ 22, 82, 83 ], [ 23, 26, 40 ], [ 24, 138, 139 ], [ 25, 158, 159 ], [ 27, 30, 43 ], [ 28, 222, 223 ], [ 32, 110, 111 ], [ 33, 104, 105 ], [ 36, 38, 45 ], [ 37, 68, 69 ], [ 39, 218, 219 ], [ 41, 248, 249 ], [ 42, 280, 281 ], [ 44, 276, 277 ], [ 46, 81, 145 ], [ 47, 209, 215 ], [ 48, 107, 112 ], [ 49, 141, 170 ], [ 50, 80, 96 ], [ 51, 124, 185 ], [ 52, 101, 166 ], [ 53, 128, 175 ], [ 54, 200, 202 ], [ 55, 115, 278 ], [ 58, 227, 291 ], [ 59, 100, 313 ], [ 60, 85, 135 ], [ 61, 103, 204 ], [ 62, 93, 287 ], [ 63, 150, 163 ], [ 64, 136, 269 ], [ 65, 233, 237 ], [ 66, 196, 284 ], [ 67, 203, 272 ], [ 70, 152, 174 ], [ 71, 117, 130 ], [ 72, 121, 198 ], [ 73, 140, 153 ], [ 76, 208, 285 ], [ 77, 201, 310 ], [ 78, 187, 226 ], [ 79, 92, 142 ], [ 84, 151, 259 ], [ 86, 97, 205 ], [ 87, 116, 193 ], [ 88, 127, 177 ], [ 89, 263, 266 ], [ 94, 146, 304 ], [ 95, 279, 300 ], [ 98, 225, 234 ], [ 99, 231, 309 ], [ 102, 162, 282 ], [ 106, 123, 292 ], [ 108, 183, 315 ], [ 109, 267, 303 ], [ 113, 171, 290 ], [ 114, 126, 264 ], [ 118, 241, 275 ], [ 119, 137, 210 ], [ 120, 131, 240 ], [ 122, 213, 253 ], [ 125, 147, 190 ], [ 129, 165, 167 ], [ 132, 154, 294 ], [ 133, 220, 243 ], [ 134, 181, 230 ], [ 143, 144, 186 ], [ 148, 245, 298 ], [ 149, 189, 191 ], [ 155, 173, 314 ], [ 160, 255, 312 ], [ 161, 261, 271 ], [ 164, 224, 254 ], [ 168, 265, 308 ], [ 169, 188, 244 ], [ 172, 182, 286 ], [ 176, 301, 311 ], [ 180, 252, 260 ], [ 184, 299, 305 ], [ 192, 206, 236 ], [ 197, 247, 293 ], [ 199, 212, 273 ], [ 207, 232, 302 ], [ 211, 274, 283 ], [ 214, 235, 250 ], [ 216, 262, 289 ], [ 217, 270, 297 ], [ 221, 288, 296 ], [ 242, 246, 295 ], [ 251, 258, 268 ] ], [ [ 1, 31, 32 ], [ 2, 3, 5 ], [ 4, 43, 44 ], [ 6, 246, 247 ], [ 7, 14, 34 ], [ 8, 142, 143 ], [ 9, 170, 171 ], [ 10, 128, 129 ], [ 11, 20, 45 ], [ 12, 264, 265 ], [ 13, 176, 177 ], [ 15, 28, 37 ], [ 16, 134, 135 ], [ 17, 206, 207 ], [ 18, 100, 101 ], [ 19, 80, 81 ], [ 21, 160, 161 ], [ 22, 236, 237 ], [ 23, 270, 271 ], [ 24, 296, 297 ], [ 25, 33, 41 ], [ 26, 112, 113 ], [ 27, 188, 189 ], [ 29, 124, 125 ], [ 30, 214, 215 ], [ 35, 180, 181 ], [ 36, 262, 263 ], [ 38, 164, 165 ], [ 39, 78, 79 ], [ 40, 288, 289 ], [ 42, 182, 183 ], [ 46, 199, 223 ], [ 47, 73, 245 ], [ 48, 50, 307 ], [ 49, 252, 266 ], [ 51, 72, 312 ], [ 52, 284, 300 ], [ 53, 242, 260 ], [ 54, 119, 305 ], [ 55, 138, 191 ], [ 56, 94, 152 ], [ 57, 133, 278 ], [ 58, 163, 225 ], [ 59, 84, 298 ], [ 60, 88, 121 ], [ 61, 146, 241 ], [ 62, 96, 292 ], [ 63, 179, 219 ], [ 64, 193, 303 ], [ 65, 166, 203 ], [ 66, 103, 213 ], [ 67, 97, 155 ], [ 68, 195, 306 ], [ 69, 217, 302 ], [ 70, 123, 276 ], [ 71, 104, 200 ], [ 74, 76, 204 ], [ 75, 85, 196 ], [ 77, 162, 243 ], [ 82, 117, 126 ], [ 83, 281, 290 ], [ 86, 141, 187 ], [ 87, 258, 294 ], [ 89, 130, 147 ], [ 90, 116, 157 ], [ 91, 228, 248 ], [ 92, 254, 275 ], [ 93, 145, 227 ], [ 95, 216, 274 ], [ 98, 272, 304 ], [ 99, 106, 208 ], [ 102, 198, 202 ], [ 105, 122, 230 ], [ 107, 137, 150 ], [ 108, 184, 285 ], [ 109, 154, 287 ], [ 110, 114, 192 ], [ 111, 279, 315 ], [ 115, 169, 257 ], [ 118, 250, 280 ], [ 120, 222, 244 ], [ 127, 256, 309 ], [ 131, 235, 255 ], [ 132, 153, 301 ], [ 136, 240, 282 ], [ 139, 156, 249 ], [ 140, 168, 194 ], [ 144, 210, 224 ], [ 148, 283, 314 ], [ 149, 158, 253 ], [ 151, 232, 286 ], [ 159, 186, 295 ], [ 167, 205, 267 ], [ 172, 226, 299 ], [ 173, 238, 251 ], [ 174, 190, 209 ], [ 175, 221, 311 ], [ 178, 234, 259 ], [ 185, 218, 273 ], [ 197, 211, 239 ], [ 201, 231, 277 ], [ 212, 233, 313 ], [ 220, 229, 268 ], [ 261, 293, 308 ], [ 269, 291, 310 ] ], [ [ 1, 62, 63 ], [ 2, 166, 167 ], [ 3, 46, 47 ], [ 4, 210, 211 ], [ 5, 146, 147 ], [ 6, 10, 35 ], [ 7, 22, 23 ], [ 8, 33, 44 ], [ 9, 312, 313 ], [ 11, 50, 51 ], [ 12, 86, 87 ], [ 13, 242, 243 ], [ 14, 66, 67 ], [ 15, 150, 151 ], [ 16, 39, 42 ], [ 17, 254, 255 ], [ 18, 102, 103 ], [ 19, 24, 36 ], [ 20, 268, 269 ], [ 21, 174, 175 ], [ 25, 136, 137 ], [ 26, 224, 225 ], [ 27, 76, 77 ], [ 28, 252, 253 ], [ 29, 118, 119 ], [ 30, 272, 273 ], [ 31, 216, 217 ], [ 32, 130, 131 ], [ 34, 230, 231 ], [ 37, 72, 73 ], [ 38, 282, 283 ], [ 40, 202, 203 ], [ 41, 58, 59 ], [ 43, 278, 279 ], [ 45, 234, 235 ], [ 48, 57, 204 ], [ 49, 142, 188 ], [ 52, 192, 199 ], [ 53, 60, 109 ], [ 54, 193, 314 ], [ 55, 266, 281 ], [ 56, 81, 264 ], [ 61, 185, 301 ], [ 64, 84, 180 ], [ 65, 141, 238 ], [ 68, 94, 170 ], [ 69, 80, 189 ], [ 70, 115, 258 ], [ 71, 206, 306 ], [ 74, 95, 143 ], [ 75, 183, 311 ], [ 78, 292, 297 ], [ 79, 116, 285 ], [ 82, 124, 239 ], [ 83, 181, 287 ], [ 85, 173, 290 ], [ 88, 100, 182 ], [ 89, 91, 259 ], [ 90, 111, 123 ], [ 92, 215, 288 ], [ 93, 101, 112 ], [ 96, 171, 245 ], [ 97, 152, 309 ], [ 98, 187, 315 ], [ 99, 219, 298 ], [ 104, 223, 250 ], [ 105, 162, 300 ], [ 106, 140, 291 ], [ 107, 198, 257 ], [ 108, 228, 293 ], [ 110, 176, 178 ], [ 113, 260, 305 ], [ 114, 184, 274 ], [ 117, 138, 229 ], [ 120, 201, 302 ], [ 121, 133, 227 ], [ 122, 236, 246 ], [ 125, 159, 233 ], [ 126, 209, 267 ], [ 127, 207, 294 ], [ 128, 172, 222 ], [ 129, 186, 241 ], [ 132, 160, 200 ], [ 134, 191, 275 ], [ 135, 208, 212 ], [ 139, 240, 256 ], [ 144, 153, 307 ], [ 145, 169, 205 ], [ 148, 261, 310 ], [ 149, 163, 262 ], [ 154, 164, 244 ], [ 155, 221, 247 ], [ 156, 277, 295 ], [ 157, 177, 237 ], [ 158, 197, 280 ], [ 161, 226, 303 ], [ 165, 232, 249 ], [ 168, 190, 299 ], [ 179, 265, 276 ], [ 194, 214, 284 ], [ 195, 286, 296 ], [ 196, 218, 289 ], [ 213, 251, 308 ], [ 220, 263, 271 ], [ 248, 270, 304 ] ], [ [ 1, 220, 221 ], [ 2, 314, 315 ], [ 3, 308, 309 ], [ 4, 232, 233 ], [ 5, 114, 115 ], [ 6, 116, 117 ], [ 7, 186, 187 ], [ 8, 96, 97 ], [ 9, 13, 39 ], [ 10, 132, 133 ], [ 11, 94, 95 ], [ 12, 25, 40 ], [ 14, 92, 93 ], [ 15, 310, 311 ], [ 16, 304, 305 ], [ 17, 27, 42 ], [ 18, 302, 303 ], [ 19, 140, 141 ], [ 20, 286, 287 ], [ 21, 162, 163 ], [ 22, 258, 259 ], [ 23, 190, 191 ], [ 24, 184, 185 ], [ 26, 212, 213 ], [ 28, 98, 99 ], [ 29, 84, 85 ], [ 30, 292, 293 ], [ 31, 54, 55 ], [ 32, 294, 295 ], [ 33, 208, 209 ], [ 34, 266, 267 ], [ 35, 250, 251 ], [ 36, 200, 201 ], [ 37, 204, 205 ], [ 38, 226, 227 ], [ 41, 274, 275 ], [ 43, 298, 299 ], [ 44, 192, 193 ], [ 45, 122, 123 ], [ 46, 77, 195 ], [ 47, 181, 225 ], [ 48, 105, 272 ], [ 49, 135, 235 ], [ 50, 240, 271 ], [ 51, 134, 157 ], [ 52, 151, 188 ], [ 53, 68, 280 ], [ 56, 166, 253 ], [ 57, 130, 173 ], [ 58, 147, 296 ], [ 59, 257, 301 ], [ 60, 168, 249 ], [ 61, 65, 231 ], [ 62, 129, 177 ], [ 63, 153, 260 ], [ 64, 72, 262 ], [ 66, 165, 170 ], [ 67, 161, 210 ], [ 69, 89, 203 ], [ 70, 148, 284 ], [ 71, 150, 270 ], [ 73, 108, 277 ], [ 74, 82, 136 ], [ 75, 244, 306 ], [ 76, 171, 265 ], [ 78, 131, 149 ], [ 79, 223, 278 ], [ 80, 172, 236 ], [ 81, 125, 268 ], [ 83, 146, 243 ], [ 86, 176, 254 ], [ 87, 189, 313 ], [ 88, 247, 307 ], [ 90, 101, 211 ], [ 91, 242, 264 ], [ 100, 230, 289 ], [ 102, 144, 248 ], [ 103, 255, 291 ], [ 104, 224, 256 ], [ 106, 124, 182 ], [ 107, 196, 237 ], [ 109, 143, 178 ], [ 110, 137, 245 ], [ 111, 128, 218 ], [ 112, 126, 222 ], [ 113, 206, 282 ], [ 118, 169, 297 ], [ 119, 156, 300 ], [ 120, 281, 288 ], [ 121, 159, 219 ], [ 127, 180, 273 ], [ 138, 154, 214 ], [ 139, 142, 197 ], [ 145, 175, 207 ], [ 152, 239, 263 ], [ 155, 241, 252 ], [ 158, 164, 279 ], [ 160, 238, 285 ], [ 167, 216, 276 ], [ 174, 228, 290 ], [ 179, 215, 269 ], [ 183, 199, 217 ], [ 194, 202, 246 ], [ 198, 234, 261 ], [ 229, 283, 312 ] ], [ [ 1, 284, 285 ], [ 2, 120, 121 ], [ 3, 48, 49 ], [ 4, 290, 291 ], [ 5, 14, 15 ], [ 6, 37, 41 ], [ 7, 244, 245 ], [ 8, 29, 38 ], [ 9, 144, 145 ], [ 10, 148, 149 ], [ 11, 168, 169 ], [ 12, 16, 21 ], [ 13, 70, 71 ], [ 17, 24, 28 ], [ 18, 22, 30 ], [ 19, 26, 32 ], [ 20, 196, 197 ], [ 23, 300, 301 ], [ 25, 172, 173 ], [ 27, 152, 153 ], [ 31, 60, 61 ], [ 33, 260, 261 ], [ 34, 198, 199 ], [ 35, 106, 107 ], [ 36, 52, 53 ], [ 39, 154, 155 ], [ 40, 108, 109 ], [ 42, 64, 65 ], [ 43, 240, 241 ], [ 44, 88, 89 ], [ 45, 126, 127 ], [ 46, 123, 305 ], [ 47, 87, 95 ], [ 50, 54, 58 ], [ 51, 77, 187 ], [ 55, 73, 101 ], [ 56, 218, 282 ], [ 57, 194, 313 ], [ 59, 67, 206 ], [ 62, 190, 201 ], [ 63, 139, 203 ], [ 66, 178, 297 ], [ 68, 230, 314 ], [ 69, 186, 308 ], [ 72, 142, 264 ], [ 74, 232, 250 ], [ 75, 309, 312 ], [ 76, 128, 270 ], [ 78, 202, 268 ], [ 79, 137, 167 ], [ 80, 180, 211 ], [ 81, 150, 281 ], [ 82, 254, 277 ], [ 83, 111, 307 ], [ 84, 94, 138 ], [ 85, 114, 271 ], [ 86, 122, 147 ], [ 90, 163, 170 ], [ 91, 212, 226 ], [ 92, 162, 233 ], [ 93, 185, 246 ], [ 96, 117, 289 ], [ 97, 184, 269 ], [ 98, 132, 136 ], [ 99, 130, 165 ], [ 100, 164, 174 ], [ 102, 276, 280 ], [ 103, 263, 315 ], [ 104, 189, 221 ], [ 105, 129, 239 ], [ 110, 227, 252 ], [ 112, 160, 249 ], [ 113, 214, 231 ], [ 115, 247, 255 ], [ 116, 272, 286 ], [ 118, 236, 310 ], [ 119, 141, 287 ], [ 124, 248, 278 ], [ 125, 216, 256 ], [ 131, 237, 265 ], [ 133, 151, 209 ], [ 134, 222, 293 ], [ 135, 279, 296 ], [ 140, 158, 259 ], [ 143, 220, 273 ], [ 146, 179, 207 ], [ 156, 234, 306 ], [ 157, 217, 298 ], [ 159, 181, 311 ], [ 161, 177, 188 ], [ 166, 294, 299 ], [ 171, 275, 303 ], [ 175, 213, 274 ], [ 176, 208, 262 ], [ 182, 200, 205 ], [ 183, 210, 258 ], [ 191, 238, 242 ], [ 192, 204, 288 ], [ 193, 235, 243 ], [ 195, 219, 228 ], [ 215, 253, 257 ], [ 223, 283, 295 ], [ 224, 266, 292 ], [ 225, 229, 302 ], [ 251, 267, 304 ] ] ] gap> # Now some checks: gap> Collected(List(res,Length)); [ [ 105, 5 ] ] gap> Collected(List(res,x->Size(Union(x)))); [ [ 315, 5 ] ] gap> Size(Union(res)); 525 gap> # gap> # Now consider the block graph bg of nearoct (i.e. the point graph gap> # of dualnearoct). gap> # gap> # Then bg has the 525 blocks of nearoct as vertices, with two gap> # distinct blocks joined by an edge iff they are not disjoint. gap> # gap> # By finding a resolution of nearoct we have shown that bg is gap> # nonsynchronizing. The set of blocks containing a given point gap> # is a 5-clique, and a 5-colouring is obtained by colouring each gap> # block in the i-th spread of the resolution with the same colour i. gap> # gap> IsPrimitive(A,nearoct.blocks,OnSets); true gap> IsPrimitive(DerivedSubgroup(A),nearoct.blocks,OnSets); true gap> AllPrimitiveGroups(NrMovedPoints,525); [ PSU(3, 5), PSigmaU(3, 5), PGU(3, 5), PGammaU(3, 5), J_2, J_2.2, A(525), S(525) ] gap> # gap> # It follows that any primitive degree 525 group gap> # isomorphic to J_2 or J_2.2 is nonsynchronizing. gap> # gap> # A theoretical geometrical construction can be used to show that gap> # the other non-2-transitve primitive groups of degree 525 are gap> # nonsynchronizing (and this was checked using FinInG). gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Maximal partial spreads in PG(3,7) invariant under a group of order 5 gap> # --------------------------------------------------------------------- gap> # gap> # gap> # We now classify the maximal partial spreads of lines in PG(3,7) gap> # that are invariant under a group of order 5, as described and gap> # justified in: gap> # gap> # L.H. Soicher, On classifying objects with specified groups gap> # of automorphisms, friendly subgroups, and Sylow tower groups, gap> # Port. Math. 74 (2017), 233-242. Preprint available at: gap> # http://www.maths.qmul.ac.uk/~lsoicher/friendly_revised_final.pdf gap> # gap> # Note in particular the use of the GRAPE function gap> # CollapsedCompleteOrbitsGraph and the use of gap> # CompleteSubgraphsOfGivenSize with positive integer vertex weights. gap> # gap> d:=3; 3 gap> q:=7; 7 gap> pg:=PG(d,q); ProjectiveSpace(3, 7) gap> lineset:=Set(List(Lines(pg)));; gap> Length(lineset); 2850 gap> G:=CollineationGroup(pg); The FinInG collineation group PGL(4,7) gap> gamma := Graph(G, lineset, OnProjSubspaces, > function(x,y) return Meet(x,y)=EmptySubspace(pg); end, > true);; gap> # Display information about gamma. gap> OrderGraph(gamma); 2850 gap> GlobalParameters(gamma); [ [ 0, 0, 2401 ], [ 1, 2016, 384 ], [ 2058, 343, 0 ] ] gap> hom:=ActionHomomorphism(G,VertexNames(gamma),OnProjSubspaces);; gap> H:=SylowSubgroup(G,5);; gap> Size(H); 25 gap> IsCyclic(H); true gap> H:=Subgroup(H,List(GeneratorsOfGroup(H),g->g^5));; gap> Size(H); 5 gap> # gap> # We shall classify the maximal partial spreads in PG(d,q) gap> # invariant under H. gap> # gap> N:=Normalizer(G,H);; gap> Size(N); 1600 gap> # gap> # Now if K is a subgroup of G containing H, then any subgroup gap> # of K isomorphic to H is in fact conjugate in K to H, or in gap> # other words, H is a *friendly* subgroup of K. gap> # This implies that N-equivalence is the same as G-equivalence gap> # for the H-invariant cliques of gamma. gap> # gap> alpha:=ShallowCopy(gamma);; gap> AssignVertexNames(alpha,[1..OrderGraph(alpha)]); gap> delta := CollapsedCompleteOrbitsGraph(Image(hom,H),alpha,Image(hom,N));; gap> # gap> # Now the vertices (actually vertex-names) of delta are the H-orbits gap> # inducing cliques in gamma, with two distinct such H-orbits joined gap> # by an edge iff their union induces a clique in gamma. gap> # gap> # The group delta.group associated to delta is the image of N gap> # acting on the vertex-names of delta (the set of which is N-invariant). gap> # gap> OrderGraph(delta); 410 gap> vertex_weights := List(VertexNames(delta),Length);; gap> # gap> # Now vertex_weights[i] is the length of the H-orbit naming gap> # vertex i of delta, and the the H-invariant complete subgraphs gap> # of size k of gamma are in 1-to-1 correspondence with the cliques gap> # of delta having vertex-weight sum equal to k. gap> # gap> Collected(vertex_weights); [ [ 5, 410 ] ] gap> for k in [1..q^2+1] do > K := CompleteSubgraphsOfGivenSize(delta,k,2,true,true,vertex_weights); > if K<>[] then > # > # Now create the corresponding H-invariant cliques in gamma. > # > K := Set(List(K,x->Union(List(x,y->VertexName(delta,y))))); > # > # Filter out the H-invariant maximal cliques in K. > # > M:=Filtered(K,x->Intersection(List(x,y->Adjacency(gamma,y)))=[]); > if M<>[] then > Print("\n",Collected(List(M,Length))); > fi; > fi; > od; [ [ 25, 426 ] ] [ [ 30, 1332 ] ] [ [ 35, 419 ] ] [ [ 40, 94 ] ] [ [ 45, 15 ] ] [ [ 50, 15 ] ] gap> Print("\n"); gap> # gap> # ===================================================================== gap> #