# This file contains GAP code which we used to verify certain claims in the paper
# ``Characterizations of the Suzuki tower near polygons’’ by Anurag Bishnoi and
# Bart De Bruyn. The computations in the present file all involve the valuation
# geometry of the dual split Cayley hexagon of order 2, which we will denote here
# by H(2)^D.
# Author: Bart De Bruyn, Ghent University, bdb@cage.ugent.be
#———————————————————————————————————————————————————————————————————————————————
# We first implement a computer model of the generalized hexagon H(2)^D with point
# set [1..63], line set lines, automorphism group g and distance function dist(.,.)
g:=AllPrimitiveGroups(DegreeOperation,63)[2];
orbs:=Orbits(Stabilizer(g,1),[1..63]);
dist1 := Filtered(orbs,x->Size(x)=6)[1];
dist2 := Filtered(orbs,x->Size(x)=24)[1];
dist3 := Filtered(orbs,x->Size(x)=32)[1];
partition:=[[1],dist1,dist2,dist3];
perp := Union([1],dist1);
r:=RepresentativeAction(g,1,partition[2][1]);
line:=Intersection(perp,OnSets(perp,r));
lines:=Orbit(g,line,OnSets);
DistMat:=NullMat(63,63);
for x in [1..63] do
r:=RepresentativeAction(g,x,1);
for y in [1..63] do
z:=y^r;
i:=1; while not(z in partition[i]) do i:=i+1; od;
DistMat[x][y]:=i-1;
od;
od;
dist:=function(x,y)
return DistMat[x][y];
end;
# With every valuation H(2)^D, there is associated a hyperplane. For geometries
# having three points per line, there is a method which allows to generate
# hyperplanes in an easy and really fast way. Indeed, a proper set of points of
# a point-line geometry with three points per line is a hyperplane if and only
# if the characteristic vector of its complement is orthogonal with the
# characteristic vectors of all lines. Based on this principle, the following GAP
# code constructs representatives of all isomorphism classes of hyperplane
# complements. These representatives are collected in an array called
# hypcomplements. The characteristic vectors of the hyperplane complements are
# precisely the nonzero vectors of the vector space U. So, the total number of
# hyperplane complements is equal to 2^(Dimension(U))-1. The code below already
# makes use of the fact that the set of points at distance 3 from a given point
# is a hyperplane complement and that there are 63 such sets.
M:=NullMat(63,63,GF(2));
for i in [1..63] do for j in [1..63] do
if i in lines[j] then M[i][j]:=Z(2); fi;
od; od;
Y:=NullspaceMat(M);
U:=Subspace(GF(2)^(63),Y);
hypcomplements:=[Set(dist3)];
balance:=2^(Dimension(U))-64;
VectorToSet:=function(X) return Filtered([1..63],i->X[i]=One(GF(2))); end;
for w in U do
if w<>Zero(U) then
compl:=VectorToSet(w);
new:=true;
for i in [1..Length(hypcomplements)] do
if RepresentativeAction(g,compl,hypcomplements[i],OnSets) <> fail then
new:=false; break; fi;
od;
if new then
Append(hypcomplements,[compl]);
balance:=balance-Index(g,Stabilizer(g,compl,OnSets));
fi;
if balance=0 then break; fi;
fi;
od;
# The next step will be to construct the valuations from the various hyperplane
# complements. In contrast with the paper, the valuations here will be scaled in
# such a way that the maximal value is equal to 0 (rather then the minimal value).
# Valuations will be stored as arrays of length 63, where the value of the point
# i is stored as the i-th entry of the array. Not every hyperplane complement is
# associated with a valuation, and it is also possible that a particular hyperplane
# complement is associated with different valuations.
# The function ISVal2 below checks whether a certain array val consisting of 63
# integers is a semi-valuation. It uses the subroutine IsVal1 which verifies
# whether the values of val on a particular line L are consistent with those of
# a semi-valuation.
IsVal1:=function(val,L)
local S;
S:=[val[L[1]],val[L[2]],val[L[3]]]; Sort(S);
return S[2]=S[1]+1 and S[3]=S[1]+1;
end;
IsVal2:=function(val)
return ForAll(lines,l->IsVal1(val,l));
end;
# We also need code to verify whether two valuations val1 and val2 are isomorphic.
# The function IsoVals realizes this goal. This function makes use of two
# subroutines, Parts and Isomorphic, which we will now explain.
# If val is a valuation, then the subroutine Parts creates a partition of the point
# set in accordance with the values taken by the different points. This partition
# is in fact an ordered list consisting of four sets, where the points with value 0
# come first, followed with those having value -1, -2 and -3.
Parts:=function(val)
local i,parts;
parts:=[[],[],[],[]];
for i in [1..63] do Append(parts[-val[i]+1],[i]); od;
return parts;
end;
# Suppose h is a group of automorphisms of the hexagon, and each of X, Y is an
# array defining a partition of the point set (created by the subroutine Parts).
# The subroutine Isomorphic can be used to verify whether there exists a group
# element in h that maps X to Y (respecting the order of the elements in X and Y).
Isomorphic:=function(h,X,Y)
local X1,Y1,h1,k,x,i;
k:=Size(X);
if k<>Size(Y) then return false; fi;
x:=RepresentativeAction(h,X[k],Y[k],OnSets);
if x=fail then return false; fi;
if k=1 then return true; fi;
X1:=[]; Y1:=[];
h1:=Stabilizer(h,Y[k],OnSets);
for i in [1..k-1] do
Append(X1,[OnSets(X[i],x)]);
Append(Y1,[Y[i]]);
od;
return Isomorphic(h1,X1,Y1);
end;
IsoVals:=function(val1,val2)
return Isomorphic(g,Parts(val1),Parts(val2));
end;
# Our next goal is to compute all valuations associated with a given hyperplane
# complement. In an initial phase every point of the hyperplane complement will be
# given the value 0, and every other point the value fail. Call such an array an
# incomplete valuation. From such an incomplete valuation, one then attempts to
# create a valuation by a series of steps aimed at giving integer values to those
# points that were initially given the value fail.
# Given an incomplete valuation val, the following procedure Complete1 tries to
# attribute values to the points of a given line L. The procedure returns an array
# [Status,val1], where Status is false when an inconsistency occurred during the
# process. If no inconsistency occurred, then Status will be true, and a more
# complete version of val will be returned as val1.
Complete1:=function(val,L)
local X,I,val1,i,Status;
X:=Set(Filtered([1..63],x->val[x]<>fail));
I:=Intersection(L,X);
if Size(I)=3 then return [IsVal1(val,L),val]; fi;
if Size(I) in [0,1] then return [true,val]; fi;
if Size(I)=2 then
val1:=ShallowCopy(val);
Status:=true;
i:=Difference(L,I)[1];
if val[I[1]]=val[I[2]] then val1[i]:=val[I[1]]-1; fi;
if val[I[1]]=val[I[2]]-1 then val1[i]:=val[I[2]]; fi;
if val[I[2]]=val[I[1]]-1 then val1[i]:=val[I[1]]; fi;
if not(val[I[1]]-val[I[2]] in [-1,0,1]) then Status:=false; fi;
fi;
return [Status,val1];
end;
# Given an incomplete valuation val, the following procedure tries to create a more
# complete version of val, after having given the point x the value i. It makes
# several times use of the routine Complete1 applied to all lines of the hexagon.
# The procedure again returns an ordered pair [Status1,val2], where Status1 will be
# false or true depending on whether an inconsistency occurred during the
# completion process. The array val2, on the other hand, will again be a more
# complete version of val.
Complete2:=function(val,x,i)
local val1,val2,Status1,Status2,j,A;
val2:=ShallowCopy(val); val2[x]:=i;
Status1:=true; Status2:=true;
while Status1 and Status2 do
val1:=ShallowCopy(val2);
for j in [1..Size(lines)] do
A:=Complete1(val2,lines[j]);
Status1 := Status1 and A[1];
val2:=A[2];
od;
if val2 = val1 then Status2:=false; fi;
od;
return [Status1,val2];
end;
# If one wants to apply Complete2, it is often the intention to pick some point
# that has not yet been given a value. The following procedure determines such a
# point.
NoAssignedValue:=function(val)
local X;
X:=Set(Filtered([1..63],x->val[x]=fail));
if X=[] then return fail; fi;
if X<>[] then return X[1]; fi;
end;
# Given a certain hyperplane complement compl, the following GAP code allows to
# compute all valuations associated with it. This is realized in a gradual
# completion process. All incomplete valuations are stored in nonprocessed1 and
# nonprocessed2. The complete ones are stored in processed.
CreateVals:=function(compl)
local val1,val2,nonprocessed1,nonprocessed2,processed,i,x,Q;
val1:=ListWithIdenticalEntries(63,fail);
for i in compl do val1[i]:=0; od;
Q:=Complete2(val1,compl[1],0);
if Q[1] and NoAssignedValue(Q[2])=fail then
nonprocessed1:=[]; processed:=[Q[2]];
fi;
if Q[1] and NoAssignedValue(Q[2])<>fail then
nonprocessed1:=[Q[2]]; processed:=[];
fi;
if not(Q[1]) then
nonprocessed1:=[]; processed:=[];
fi;
while nonprocessed1<>[] do
nonprocessed2:=[];
for val1 in nonprocessed1 do
for i in [1..3] do
x:=NoAssignedValue(val1);
Q:=Complete2(val1,x,-i);
if Q[1] then
val2:=Q[2];
if NoAssignedValue(val2)=fail then Append(processed,[val2]); fi;
if NoAssignedValue(val2)<>fail then Append(nonprocessed2,[val2]); fi;
fi;
od;
od;
nonprocessed1:=nonprocessed2;
od;
return processed;
end;
# Using the routine CreateVals, we now construct an array valuation which contains
# a representative of each isomorphism class of valuations.
valuations:=[];
for i in [1..Size(hypcomplements)] do
vals1:=CreateVals(hypcomplements[i]);
vals2:=[];
for i in [1..Size(vals1)] do
new:=true;
for j in [1..Size(vals2)] do
if IsoVals(vals1[i],vals2[j]) then new:=false; break; fi;
od;
if new then Append(vals2,[vals1[i]]); fi;
od;
Append(valuations,vals2);
od;
# It turns out that H^D(2) has up to isomorphism four valuations.
# The following routine ValSet computes all valuations isomorphic to a given
# valuation val.
ValSet:=function(val)
local vals,r;
vals:=[];
for r in g do
vals:=Union(vals,[List([1..63],x->val[x^r])]);
od;
return vals;
end;
# The valuations of H^D(2) are given a type according to the isomorphism class
# in which they are contained. Also, all valuations of a given type are
# constructed.
TypeVal:=function(val)
if List(Parts(val),Length)=[40,22,1,0] then return "C"; fi;
if List(Parts(val),Length)=[32,26,5,0] then return "D"; fi;
if List(Parts(val),Length)=[16,32,14,1] then return "B"; fi;
if List(Parts(val),Length)=[32,24,6,1] then return "A"; fi;
end;
for i in [1..4] do
T:=TypeVal(valuations[i]);
if T="A" then valA:=valuations[i]; valsA:=ValSet(valA); fi;
if T="B" then valB:=valuations[i]; valsB:=ValSet(valB); fi;
if T="C" then valC:=valuations[i]; valsC:=ValSet(valC); fi;
if T="D" then valD:=valuations[i]; valsD:=ValSet(valD); fi;
od;
Vals:=Union(valsA,valsB,valsC,valsD);
# We now implement a procedure NB to determine whether two valuations
# are neighboring are not.
NBe:=function(val1,val2,e)
return IsSubset([-1,0,1],Set(val1+e-val2));
end;
NB:=function(val1,val2)
return NBe(val1,val2,-1) or NBe(val1,val2,0) or NBe(val1,val2,1);
end;
# If val1 and val2 are two distinct collinear valuations (in the valuation
# geometry), then the following procedure allows to compute the third
# valuation on the unique line through them. If val1=val2, then val1 will
# be returned. If val1 and val2 are not collinear, then fail is returned.
ThirdVal:=function(val1,val2)
local e,i,val3;
val3:=0*[1..63];
e:=fail;
for i in [-1,0,1] do
if NBe(val1,val2,i) then e:=i; break; fi;
od;
if e=fail then return fail; fi;
for i in [1..63] do
if val2[i]=val1[i]+e then val3[i]:=val2[i]-1; fi;
if val2[i]=val1[i]+e-1 then val3[i]:=val2[i]+1; fi;
if val2[i]=val1[i]+e+1 then val3[i]:=val2[i]; fi;
od;
return(val3-Maximum(val3));
end;
# Linetypes can be computed with the following routine.
LineType:=function(L)
local type;
type:=[TypeVal(L[1]),TypeVal(L[2]),TypeVal(L[3])]; Sort(type);
return type;
end;
# The function ThroughPoint1 collects the types of the lines in the
# valuation geometry that are incident with a given valuation val1.
ThroughPoint1:=function(val1)
local val2,val3,types;
types:=[];
for val2 in Difference(Vals,[val1]) do
val3:=ThirdVal(val1,val2);
if val3 in Vals then
types:=Union(types,[LineType([val1,val2,val3])]);
fi;
od;
return types;
end;
# With the aid of ThroughPoint1 we can easily collect all possible line types.
AllLineTypes:=[];
for i in [1..Size(valuations)] do
AllLineTypes:=Union(AllLineTypes,ThroughPoint1(valuations[i]));
od;
# Given three possible types T1, T2 and T3, the following function allows to
# compute the number of lines of Type T1,T2,T3 (in the valuation geometry) that
# are incident with a given valuation of Type T1.
ThroughPoint2:=function(T1,T2,T3)
local i,help,val1,val2,val3;
i:=1; while TypeVal(valuations[i])<>T1 do i:=i+1; od;
val1:=valuations[i]; help:=[];
for val2 in Difference(Vals,[val1]) do
val3:=ThirdVal(val1,val2);
if val3 in Vals and TypeVal(val2)=T2 and TypeVal(val3)=T3 then
help:=Union(help,[Set([val1,val2,val3])]);
fi;
od;
return Size(help);
end;
# We now show the connectedness of the subgeometry V’ of the valuation
# geometry V, defined on the Type B valuations by the lines of Type ABB
# and BBB. If this subgeometry is connected, then Status as defined below
# will be true. If this subgeometry is not connected, then Status will be
# false. The graph Gr defined below is the collinearity graph of V’.
LoadPackage("grape");
Adj:=function(val1,val2)
return val1<>val2 and NB(val1,val2);
end;
Gr:=Graph(Group(()),valsB,OnTuples,Adj,true);
Status:=IsConnectedGraph(Gr);