8 Block Designs and Projective Planes

Given a list of lists blocks which represents the blocks of a projective plane, a block design is generated. If the blocks is not a set of sets of the integers [1..v] for some v, the points are sorted and enumerated and the blocks are changed accordingly. But the original names are known to the returned BlockDesign.

The block design generated this way will contain two extra entries, jblock and isProjectivePlane. The matrix .jblock contains the number of the block containing the points i and j at the (i,j)th position. And isProjectivePlane will be true. If blocks do not form the lines of a projective plane, an error is issued.

Returns a matrix which has as ijth entry the point wich is contained in the blocks with numbers i and j. This matrix is also stored in plane. Some operations are faster if plane contains this matrix. If plane is not a projective plane, an error is issued.

gap> b:=[ [ 1, 3 ], [ 1, 6 ], [ 2, 4 ], [ 2, 7 ], 
>       [ 3, 5 ], [ 4, 6 ], [ 5, 7 ] ];;
gap> plane:=ProjectivePlane(b);
rec( isBlockDesign := true, v := 7, 
     blocks := [ [ 1, 3 ], [ 1, 6 ], [ 2, 4 ], [ 2, 7 ], 
                 [ 3, 5 ], [ 4, 6 ], [ 5, 7 ] ], 
     jblock := [ [ 0, 0, 1, 0, 0, 2, 0 ], [ 0, 0, 0, 3, 0, 0, 4 ], 
     [ 1, 0, 0, 0, 5, 0, 0 ], [ 0, 3, 0, 0, 0, 6, 0 ], 
     [ 0, 0, 5, 0, 0, 0, 7 ], [ 2, 0, 0, 6, 0, 0, 0 ], 
     [ 0, 4, 0, 0, 7, 0, 0 ] ], 
     isProjectivePlane := true )
gap> PointJoiningLinesProjectivePlane(plane);
[ [ 0, 1, 0, 0, 3, 0, 0 ], [ 1, 0, 0, 0, 0, 6, 0 ], [ 0, 0, 0, 2, 0, 4, 0 ], 
  [ 0, 0, 2, 0, 0, 0, 7 ], [ 3, 0, 0, 0, 0, 0, 5 ], [ 0, 6, 4, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 7, 5, 0, 0 ] ]
gap> RecNames(plane);
[ "isBlockDesign", "v", "blocks", "jblock", "isProjectivePlane", "jpoint" ]

This calculates the development of a (partial relative) difference set diffset in the group given by Gdata. That is, the associated block design.

diffset can be given as a list of group elements or a list of integers (positions in the set of group elements). Gdata can either be the record returned by PermutationRepForDiffsetCalculations or a group or a set of group elements.

In either case, the returned object is a BlockDesign in the sense of L. Soichers DESIGN package.

gap> G:=CyclicGroup(21);;  Gdata:=PermutationRepForDiffsetCalculations(G);; 
gap> AllDiffsets([2],[1..21],4,[],Gdata,1);                                  
[ [ 2, 5, 16, 17 ], [ 2, 6, 10, 18 ] ]
gap> d1:=DevelopmentOfRDS(Set(G){[2,5,16,17]},Set(G)); 
rec( isBlockDesign := true, v := 21, 
  blocks := [ [ 1, 2, 5, 16, 17 ], [ 1, 3, 14, 15, 21 ], [ 1, 4, 8, 10, 13 ], 
      [ 1, 6, 7, 9, 20 ], [ 1, 11, 12, 18, 19 ], [ 2, 3, 9, 10, 12 ], 
      [ 2, 4, 7, 15, 19 ], [ 2, 6, 8, 11, 21 ], [ 2, 13, 14, 18, 20 ], 
      [ 3, 4, 6, 17, 18 ], [ 3, 5, 8, 19, 20 ], [ 3, 7, 11, 13, 16 ], 
      [ 4, 5, 9, 11, 14 ], [ 4, 12, 16, 20, 21 ], [ 5, 6, 12, 13, 15 ], 
      [ 5, 7, 10, 18, 21 ], [ 6, 10, 14, 16, 19 ], [ 7, 8, 12, 14, 17 ], 
      [ 8, 9, 15, 16, 18 ], [ 9, 13, 17, 19, 21 ], [ 10, 11, 15, 17, 20 ] ], 
  autSubgroup := <permutation group with 21 generators>, 
  pointNames := [ <identity> of ..., f1, f2, f1^2, f1*f2, f2^2, f1^2*f2, 
      f1*f2^2, f2^3, f1^2*f2^2, f1*f2^3, f2^4, f1^2*f2^3, f1*f2^4, f2^5, 
      f1^2*f2^4, f1*f2^5, f2^6, f1^2*f2^5, f1*f2^6, f1^2*f2^6 ], 
  blockSizes := [ 5 ], blockNumbers := [ 21 ], isSimple := true, 
  isBinary := true )
gap> d2:=DevelopmentOfRDS([2,5,16,17],Gdata);;
gap> d1=d2
true
gap> d1=DevelopmentOfRDS(Set(G){[2,5,16,17]},G);  
true
gap> d1=DevelopmentOfRDS([2,5,16,17],G);        
true

Note that equality for block designs means equality of records. So DevelopmentOfRDS generates exactly the same record in each of the above examples. The output is in fact independent of the chosen data type of the input (as long as it is valid). In particular, the design always knows its pointNames.

Let plane be a projective plane. Let points be a set of non-collinear points (integers) of this plane. Then ProjectiveClosureOfPointSet returns a record with the entries .closure and .embedding.

Here .closure is the projective closure of points (the smallest projectively closed subset of plane containing the points points). It is not checked, whether this is a projective plane. As the BlockDesign .closure has points [1..w] and plane has poins [1..v] with w ≤ v, we need an embedding of .closure into plane. This embedding is the permutation .embedding. It is a permutation on [1..v] which takes the points of .closure to a set of points in plane containing points and preserving incidence. Note that nothing is known about the behaviour of .embedding on any point outside [1..w] and [1..w]^.embedding.

If maxsize is given and maxsize ≠ 0, calculations are stopped if the closure is known to have at least maxsize points and the plane plane is returned as .closure with the trivial permutation as embedding.

Let's find a Baer subplane in the desarguesian plane of order 4:

gap> G:=CyclicGroup(21);; Gdata:=PermutationRepForDiffsetCalculations(G);;
gap> AllDiffsets([2],[1..21],4,[],Gdata,1);                                  
[ [ 2, 5, 16, 17 ], [ 2, 6, 10, 18 ] ]
gap> plane:=DevelopmentOfRDS([2,5,16,17],Gdata);;
gap> ProjectiveClosureOfPointSet([1,3,4],plane);  
rec( closure := rec( isBlockDesign := true, v := 3, 
     blocks := [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ] 
     pointNames := [ <identity> of ..., f2, f1^2 ]), 
     embedding := (2,3,4) )
gap> IsProjectivePlane(last.closure);
false
gap> baer:=ProjectiveClosureOfPointSet([1,3,4,5],plane);;
gap> baer.closure.blocks;
[ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 1, 4, 7 ], [ 2, 3, 7 ], 
  [ 2, 4, 5 ], [ 3, 4, 6 ], [ 5, 6, 7 ] ]
gap> IsProjectivePlane(baer.closure);
true
gap> Set(baer.closure.blocks,b->OnSets(b,baer.embedding));
[ [ 1, 3, 14 ], [ 1, 4, 8 ], [ 1, 5, 17 ], [ 3, 4, 17 ], 
  [ 3, 5, 8 ], [ 4, 5, 14 ], [ 8, 14, 17 ] ]

8.1 Isomorphisms and Collineations

Isomorphisms of projective planes are mappings which take points to points and blocks to blocks and respect incidence. A collineation of a projective plane P is an isomorphism from P to P.

As projective planes are assumed to live on the integers, isomorphisms of projective planes are represented by permutations. To test if a permutation on points is actually an isomorphism of projective planes, the following methods can be used.

Let plane1, plane2 be two projective planes. IsIsomorphismOfProjectivePlanes test if the permutation perm on points defines an isomorphism of the projective planes plane1 and plane2.

Let plane be a projective plane and perm a permutation on the points of this plane. IsCollineationOfProjectivePlane(perm,plane) returns true, if perm induces a collineation of plane.

This is just another form to call IsIsomorphismOfProjectivePlanes(perm,plane,plane)

Let gens1 be a list of points generating the projective plane plane1 and gens2 a list of generating points for plane2. Then a permutation is returned representing a mapping from the points of plane1 to those of plane2 and taking the list gens1 to the list gens2. If there is no such mapping which defines an isomorphism of projective planes, fail is returned.

IsomorphismProjPlanesByGeneratorsNC does not check whether gens1 and gens2 really generate the planes plane1 and plane2.

Look at the above example again:

gap> P:=ProjectivePlane( [ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 1, 4, 7 ], 
>       [ 2, 3, 7 ], [ 2, 4, 5 ], [ 3, 4, 6 ], [ 5, 6, 7 ] ]);;
gap> pi:=IsomorphismProjPlanesByGenerators([1,2,3,4],P,[2,4,6,7],P);
(1,2,4,7,3,6,5)
gap> IsIsomorphismOfProjectivePlanes(pi,P,P);
true
gap> IsCollineationOfProjectivePlane(pi,P);                 
true
gap> IsomorphismProjPlanesByGenerators([1,2,3,4],P,[1,2,3,5],P);
fail
gap> ProjectiveClosureOfPointSet([1,2,3,5],P).closure.v;
4

8.2 Central Collineations

Let ϕ be a collineation of a projective plane which fixes one point block-wise (the so-called centre) and one block point-wise (the so-called axis). If the centre is contained in the axis, ϕ is called elation. Otherwise, ϕ is called homology. The group of elations with given axis is called translation group of the plane (relative to the chosen axis). A projective plane with transitive translation group is called translation plane. Here transitivity is on the points outside the axis.

Let centre be a point and axis a block of a projective plane plane . pair must be a pair of points outside axis and lie on a block containing center. Then there is a unique collineation fixing axis pointwise and centre blockwise (an elation) and taking point[1] to point[2].

If one of the conditions is not met, an error is issued. This method is faster, if plane.jpoint is known (see RDS:PointJoiningLinesProjectivePlane)

Let centre be a point and axis a block of the projective plane plane. AllElationsCentAx returns the group of all elations with centre centre and axis axis as a group of permutations on the points of plane.

If ``generators'' is set, only a list of generators of the translation group is returned. This method is faster, if plane.jpoint is known (see RDS:PointJoiningLinesProjectivePlane)

Let axis be a block of a projective plane plane. AllElationsAx returns the group of all elations with axis axis.

If ``generators'' is set, only a set of generators for the group of elations is returned. This method is faster, if plane.jpoint is known (see RDS:PointJoiningLinesProjectivePlane)

gap> P:=ProjectivePlane( [ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 1, 4, 7 ], 
>       [ 2, 3, 7 ], [ 2, 4, 5 ], [ 3, 4, 6 ], [ 5, 6, 7 ] ]);;
gap> pi:=ElationByPair(1,[1,2,6],[3,5],P);
(3,5)(4,7)
gap> AllElationsCentAx(1,[1,2,6],P);
Group([ (3,5)(4,7) ])
gap> AllElationsAx([1,2,6],P); 
Group([ (3,5)(4,7), (3,7)(4,5) ])
gap> AllElationsAx([1,2,6],P);
Group([ (3,5)(4,7), (3,7)(4,5) ])
gap> Size(last);
4

Returns true if the plane plane has a block b such that the group of elations with axis b is transitive outside b.

If infline is given, only the group of elations with axis infline is considered. This is faster than calculating the full translation group if the projective plane plane is not a translation plane. If plane is a translation plane, the full translation group is calculated.

This method is faster, if plane.jpoint is known (see RDS:PointJoiningLinesProjectivePlane)

gap> AllElationsAx(P.blocks[1],P);
Group([ (3,5)(4,7), (3,7)(4,5) ])
gap> Size(last);
4
gap> IsTranslationPlane(P);
true

HomologyByPair returns the homology defined by the pair pair fixing centre blockwise and axis pointwise. The returned permutation fixes axis pointwise and centre linewise and takes pair[1] to pair[2].

returns the group of homologies with centre centre and axis axis of the plane plane.

gap> HomologyByPair(3,[1,2,6],[4,5],P);
Error, The centre must be fixed blockwise called from
 # ...
gap> GroupOfHomologies(3,[1,2,6],P);   
Group(())

8.3 Collineations on Baer Subplanes

Let P be a projective plane of order n². A subplane B of order n of P is called Baer subplane. Baer suplanes are exactly the maximal subplanes of P.

If a projective plane contains a Baer subplane, collineations of the subplane may be lifted to the full plane. If such an extension to the full plane exists, it is uniquely determined by the image of one point outside the Baer plane.

Here baercoll is a collineation (a permutation of the points) of the projective plane baerplane. The permutation embedding is a permutation on the points of the full pane which converts the enumeration of baerplane to that of the full plane. This means that the image of the points of baerplane under embedding is a subset of the points of plane. Namely the one representing the Baer plane in the enumeration used for the whole plane. point and image are points outside the Baer plane.

The data for baerplane and embedding can be calculated using ProjectiveClosureOfPointSet.

InducedCollineation returns a collineation of the full plane (as a permutation on the points of plane) which takes point to image and acts on the Baer plane as baercoll does. If no such collineation exists, fail is returned.

This method needs plane.jpoint. If it is unknown, it is calculated (see RDS:PointJoiningLinesProjectivePlane)

Let's go back to an earlier example and find a planar collineation:

gap> G:=CyclicGroup(21);; Gdata:=PermutationRepForDiffsetCalculations(G);; 
gap> AllDiffsets([2],[1..21],4,[],Gdata,1); 
[ [ 2, 5, 16, 17 ], [ 2, 6, 10, 18 ] ]
gap> plane:=DevelopmentOfRDS([2,5,16,17],Gdata);;
gap> baer:=ProjectiveClosureOfPointSet([1,3,4,5],plane);; 
gap> pi:=InducedCollineation(baer.closure,(),21,15,plane,baer.embedding);
(2,16)(6,18)(7,12)(9,11)(10,13)(15,21)(19,20)
gap> 21^pi;
15
gap> ForAll(OnSets([1..7],baer.embedding),i->i^pi=i);
true

8.4 Invariants for Projective Planes

The functions NrFanoPlanesAtPoints, PRank@RDS, FingerprintAntiFlag and FingerprintProjPlane calculate invariants for finite projective planes. For more details see RoederDiss and MoorhouseGraphs. The values of some of these invariants are available from the homepages of Moorhouse and Royle for many planes.

For a projective plane plane, NrFanoPlanesAtPoints(points,plane) calculates the so-called Fano invariant. That is, for each point in points, the number of subplanes of order 2 (so-called Fano planes) containing this point is calculated. The method returns a list of pairs of the form [point ,number ] where number is the number of Fano sub-planes in point.

This method is faster, if plane.jpoint is known (see RDS:PointJoiningLinesProjectivePlane). Indeed, if plane.jpoint is not known, this method is very slow.

gap> G:=CyclicGroup(4^2+5);
<pc group of size 21 with 2 generators>
gap> diffset:=OneDiffset(G);        
[ f1, f1*f2, f1^2*f2^4, f1*f2^5 ]
gap> P:=DevelopmentOfRDS(diffset,G);;
gap> NrFanoPlanesAtPoints([3],P);
[ [ 3, 240 ] ]

returns a matrix I, where the columns are numbered by the blocks and the rows are numbered by points. And I[i][j]=1 if and only if points[i] is incident (contained in) blocks[j] (an 0 else).

Let I be the incidence matrix of the projective plane plane and p a prime power. The rank of I·I^t as a matrix over GF(p) is called p-rank of the projective plane. Here I^t denotes the transposed matrix. Note that this is a method within the RDS workspace, so it has to be called as PRank@RDS

gap> G:=CyclicGroup(2^2+3);
<pc group of size 7 with 1 generators>
gap> P:=DevelopmentOfRDS(OneDiffset(G),G);;
gap> IncidenceMatrix(P);
[ [ 1, 1, 1, 0, 0, 0, 0 ], [ 1, 0, 0, 1, 1, 0, 0 ], [ 0, 1, 0, 1, 0, 1, 0 ], 
  [ 1, 0, 0, 0, 0, 1, 1 ], [ 0, 0, 1, 1, 0, 0, 1 ], [ 0, 0, 1, 0, 1, 1, 0 ], 
  [ 0, 1, 0, 0, 1, 0, 1 ] ]
gap> PRank@RDS(P,3);
6
gap> PRank@RDS(P,2);
4

For each anti-flag (p,l) of a projective plane plane of order n, define an arbitrary but fixed enumeration of the lines through p and the points on l. Say l₁,...,l_n+1 and p₁,...,p_n+1 The incidence relation defines a canonical bijection between the l_i and the p_i and hence a permutation on the indices 1,...,n+1. Let σ_(p,l) be this permutation.

Denote the points and lines of the plane by q₁,... q_n²+n+1 and e₁,...,e_n²+n+1. Define the sign matrix as A_ij=sgn(σ_(qi,ej)) if (q_i,e_j) is an anti-flag and =0 if it is a flag. Then the fingerprint is defnied as the multiset of the entries of |AA^t|.

Let m₁,...,m_n+1 be the lines containing point and E₁,...,E_n+1 the points on the line given by linenr such that E_i is incident with m_i. Now label the points of m_i as point =P_i,1,...,P_i,n+1=E_i and the lines of E_i as line =l₁,...,l_i,n+1=m_i. For i ≠ j, each P_j,k lies on exactly one line l_i,kσi,j containing E_i for some permutation σ_i,j

Define a matrix A, where A_i,j is the sign of σ_i,j if i ≠ j and A_i,i=0 for all i. The partial fingerprint is the multiset of entries of |AA^t| where A^t denotes the transposed matrix of A.

Look at the above example again:

gap> NrFanoPlanesAtPoints([1,2,3],plane);
[ [ 1, 240 ], [ 2, 240 ], [ 3, 240 ] ]
gap> Set(NrFanoPlanesAtPoints([1..plane.v],plane),i->i[2])=[240];
true
gap> PRank@RDS(plane,2);
10
gap> PRank@RDS(plane,3);
21
gap> PRank@RDS(plane,5);
20
gap> FingerprintProjPlane(plane);
[ [ 12, 420 ], [ 16, 21 ] ]
gap> FingerprintAntiFlag(1,6,plane);
[ [ 3, 20 ], [ 4, 5 ] ]

[Up] [Previous] [Next] [Index]