# Computations involving the generalized hexagons of order 2 and their valuation geometries
# for the paper 'On semi-finite hexagons of order (2, t) containing a subhexagon'.
# Author:
# Anurag Bishnoi
# Ghent University
# anurag.2357@gmail.com, Anurag.Bishnoi@ugent.be
# -----------------------------------------------------------------------------------------
# There are precisely two such generalized hexagons, the split Cayley hexagon of order 2 and its dual.
# Both of them have precisely 63 points and an automorphism group that acts primitively and distance
# transitively on the points.
# The two non isomorphic actions of degree 63 can be found in the GAP library of primitive groups.
# Depending on the value of IsDual we choose the appropriate group.
IsDual := false;
if IsDual then G := AllPrimitiveGroups(DegreeOperation,63,Size,12096)[1];
else G := AllPrimitiveGroups(DegreeOperation,63,Size,12096)[2];
fi;
# Now that we have the full automorphism group of our generalized hexagon which acts distance transitively
# on the points, we can construct the points and lines of our geometry.
# The following global variables will be used later in some of the functions:
# - 'G', the full automorphism group of the hexagon
# - 'points', the list of numbers from 1 to 63 where each number denotes a point of the hexagon
# - 'lines', the set of lines of the hexagon stored as triples of points
# - 'dist', the distance function for the collinearity graph
points:= List([1..63]);
diam := 3;
orbs := Orbits(Stabilizer(G,1),points);
dist1 := Filtered(orbs,x->Size(x)=6)[1];
dist2 := Filtered(orbs,x->Size(x)=24)[1];
dist3 := Filtered(orbs,x->Size(x)=32)[1];
perp := Union([1],dist1);
line := Intersection(perp,OnSets(perp,RepresentativeAction(G,1,dist1[1])));
lines := Orbit(G,line,OnSets);
partition := [[1],dist1,dist2,dist3]; #Diameter of the polygon is Size(partition) - 1
DistMat := NullMat(Size(points), Size(points));
for i in [1..Size(points)] do
for j in [i+1..Size(points)] do
k := j^RepresentativeAction(G,i,1);
temp := 0;
while not(k in partition[temp+1]) do temp := temp + 1; od;
DistMat[i][j] := temp;
DistMat[j][i] := temp;
od;
od;
dist := function(x,y)
return DistMat[x][y];
end;
# To compute the valuations we first compute the hyperplanes of the hexagons. Since we know that each valuation
# gives rise to a hyperplane we can first compute the hyperplanes of our hexagon and then find the set of all
# valuations corresponding to each hyperplane up to isomorphism.
# Computation of hyperplanes is an easy task in this case since each line has exactly three points on it.
# Therefore, a subset of points is a hyperplane if and only if the characteristic vector of its complement is
# orthogonal to the characteristic vector of every line, over GF(2). Based on this idea we can easily compute
# the set of all hyperplane complements as the nullspace of the incidence matrix over GF(2).
SetVect := function(S)
#I: subset of points
#O: characteristic vector of S
return One(GF(2))*List(points,function(i) if i in S then return 1;
else return 0; fi; end);
end;
VectSet:=function(v)
#I: characteristic vector
#O: subset of points corresponding to v
return Set(Filtered(points,i->v[i]=One(GF(2))));
end;
IncidenceMatrix := TransposedMat(List(lines, SetVect));
Y := NullspaceMat(IncidenceMatrix);
U := Subspace(GF(2)^(Size(points)),Y); # each non zero vector of U corresponds to a unique hyperplane complement
# Now we compute a list of distinct representatives of the isomorphism classes of hyperplane complements and
# store it in the global variable 'hypcomplements'. Note that in a near polygon the set of points opposite to
# a given point is always a hyperplane complement.
hypcomplements:=[Set(dist3)];
balance := 2^(Dimension(U))- 1 - Size(points); # Index(G,Stabilizer(G,dist3,OnSets)) = Size(points)
while balance > 0 do
w := Random(U);
if w <> Zero(U) then
compl := VectSet(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
Add(hypcomplements, compl);
balance:=balance-Index(G,Stabilizer(G,compl,OnSets));
fi;
fi; od;
# The next step is to check if a given hyperplane complement corresponds to a valuation and if it does then
# compute all valuations arising from that up to isomorphism.
# The function 'CreateSemiVal' below takes as input a hyperplane complement and returns the list of valuations
# that correspond to it. If the list is empty then we discard the hyperplane complement.
# This function uses some auxilarry function which are explained below.
CheckV2 := function(L)
#I: a list of values on a subset of [1..Size(points)]
#O: true if and only if there is a unique index for which L[x] = Minimum(L) and every other element is one more than that
local M; M := ShallowCopy(L);
Sort(M);
return (M[1] = M[2] - 1) and (M[2] = M[Size(L)]);
end;
MakeClosure := function(val)
local X,x,L,f,S;
f := ShallowCopy(val);
X := Filtered(points, x -> val[x] <> fail);
for L in lines do
S := Intersection(L,X);
if Size(S) = 2 then
x := Difference(L,X)[1];
if AbsInt(val[S[1]] - val[S[2]]) > 1 then return [false,val]; fi;
if val[S[1]] = val[S[2]] then f[x] := val[S[1]] - 1;
else f[x] := Maximum(val[S[1]], val[S[2]]); fi;
fi;
if Size(S) = 3 then
if not CheckV2(val{S}) then return [false, val];fi;
fi;
od;
return [true,f];
end;
AssignValue := function(val, x, i)
local f,g,temp;
f := [];
g := ShallowCopy(val);
g[x] := i;
while f <> g do
f := ShallowCopy(g);
temp := MakeClosure(g);
if not temp[1] then return [false, val]; fi;
g := temp[2];
od;
return [true,f];
end;
ChoosePoints := function(val)
local x, L, X;
X := Filtered(points, x -> val[x] <> fail);
for L in lines do
if Size(Intersection(L,X)) = 1 then break;fi;
od;
if Size(Intersection(L,X)) <> 1 then Print(L,X,val); fi;
return [Difference(L,X)[1], Intersection(L,X)[1]];
end;
AreIsomorphicVal := function(val1,val2)
#I: a pair of functions val1, val2 on points
#O: checks if there is group element g such that val2[x] = val1[x^g] for all points x
return val2 in Set(G, g -> List(points, x -> val1[x^g]));
end;
CreateSemiVal := function(compl)
#I: a hyperplane complement compl
#O: all possible semi-valuations corresponding to compl
local i, p, x, q, X, temp, complete, incomplete,val;
complete := [];
incomplete := [];
val := ListWithIdenticalEntries(Size(points), fail);
for x in compl do val[x] := 0; od;
temp := AssignValue(val, compl[1], 0);
if temp[1] then
if ForAll(points, x -> temp[2][x] <> fail) then Add(complete, temp[2]);
else Add(incomplete, temp[2]);
fi;
else return [];
fi;
while incomplete <> [] do
val := Remove(incomplete);
temp := ChoosePoints(val);
p := temp[1];
q := temp[2];
for i in [1..diam] do
temp := AssignValue(val, p, -i);
if temp[1] then
if ForAll(points, x -> temp[2][x] <> fail) then
if not ForAny(complete, f -> AreIsomorphicVal(f, temp[2])) then
Add(complete,temp[2]);
fi;
else Add(incomplete, temp[2]);
fi;
fi;
od;
od;
return Set(complete, L -> List(L, x -> x - Minimum(L)));
end;
Valuations := [];
for h in hypcomplements do
S := CreateSemiVal(h);
if S <> [] then
Append(Valuations,S);
fi;
od;
# Now that we have the full set valuations of the hexagon we can study them and give them certain labels.
# We would also like to have some function to study these semivaluations.
ValueDistribution := function(val)
#I: a valuation val
#O: a list L where L[i] is the number of points of value i-1
local L, M;
M := Maximum(val);
L := [];
for i in [0..M] do Add(L, Size(Filtered(val, x -> x = i))); od;
return L;
end;
HyperplaneComplement := function(val)
#I: a valuation val
#O: the hyperplane complement assocaited with val, i.e., the set of points of maximal value
local M;
M := Maximum(val);
return Set(Filtered(points,x -> val[x] = M));
end;
# The labels we give to the valuations are of course dependent on whether it is the split Cayley hexagon or
# its dual.
if IsDual then
TypeSemi := function(val)
local h;
h := HyperplaneComplement(val);
if Size(h) = 32 and Maximum(val) = 3 then return "A"; fi;
if Size(h) = 40 then return "C"; fi;
if Size(h) = 16 then return "B"; fi;
return "D";
end;
else
TypeSemi := function(val)
local h;
h := HyperplaneComplement(val);
if Size(h) = 32 then return "A"; fi;
if Size(h) = 34 then return "B_3"; fi;
if Size(h) = 36 then return "B_2"; fi;
if Size(h) = 40 then return "B_1"; fi;
if Size(h) = 24 then return "B_5"; fi;
if Size(h) = 28 then return "B_4"; fi;
return "C";
end;
fi;
# We know modify our list 'Valuations' by changing each entry to a triple [H,val,T] where H is the hyperplane complement of
# the type T valuation val.
Valuations := List(Valuations, x -> [HyperplaneComplement(x), x, TypeSemi(x)]);
GenerateOrbit := function(s)
#I: a triple [H,val,T]
#O: the orbit of this triple under group G
return Set(G, g -> [OnSets(s[1], g), List(points, x -> s[2][x^Inverse(g)]), s[3]]);
end;
# We are now ready to construct the table of valuations as mentioned in the paper.
Table1 := [];
for s in Valuations do
Add(Table1, [TypeSemi(s[2]),Size(GenerateOrbit(s)), Maximum(s[2]), Size(Filtered(s[2], x -> x = 0)), ValueDistribution(s[2])]);
od;
# To construct table 2 we need to find the lines of the valuation geometry. We need to be able to determine when to valuations are
# neighbouring and a function to construct f1*f2.
IsNeighboring := function(val1, val2)
#I: two semi-valuations val1 and val2
#O: returns whether they are neighbouring or not
local S;
if val1 = val2 then return false; fi;
S := List(points, x -> val1[x] - val2[x]);
Sort(S);
if S[Size(S)] - S[1] > 2 then return false; fi;
return true;
end;
Epsilon := function(val1, val2)
#I: two neighbouring semi-valuations val1 and val2
#O: the integer e for which |val1(x) - val2(x) + e| <= 1
local e, p, l, x1, x2;
for l in lines do
x1 := Filtered(l, x -> val1[x] = Minimum(val1{l}))[1];
x2 := Filtered(l, x -> val2[x] = Minimum(val2{l}))[1];
if x1 <> x2 then break; fi;
od;
return val2[x2] - val1[x1];
end;
ThirdFromTwo := function(val1, val2)
#I: two valuations val1 and val2
#O: the product val1*val2
local e, x, val3;
e := Epsilon(val1, val2);
val1 := val1 + e;
val3 := 0*points;
for x in points do
if val1[x] = val2[x] then val3[x] := val1[x] - 1;
else val3[x] := Maximum([val1[x], val2[x]]);
fi;
od;
return val3 - Minimum(val3);
end;
ThroughPoint := function(s, S)
#I: a member s of the list Valuations and a list S of some valuations of S
#O: the types of lines through point val of the valuation geometry when the other two points (valuations) lie in set S
local val1, val2, val3, L, e, types, x, g, i, T;
val1 := s[2];
types := Set([]);
for val2 in List(S, x -> x[2]) do
if IsNeighboring(val1, val2) then
val3 := ThirdFromTwo(val1, val2);
if val3 in List(S, x -> x[2]) then
L := [val1, val2, val3];
T := [TypeSemi(val1), TypeSemi(val2), TypeSemi(val3)]; Sort(T);
i := Position(List(types, x -> x[1]), T);
if i <> fail then types[i][2] := types[i][2] + 1/2;
else AddSet(types, [T,1/2]); fi;
fi;
fi;
od;
return types;
end;
# Now we can construct the table 2
Table2 := [];
S := Set([]);
for s in Valuations do S := Union(S,GenerateOrbit(s)); od;
for s in Valuations do
Add(Table2,[TypeSemi(s[2]), ThroughPoint(s,S)]);
od;
Print("Data for the points of the valuation geometry:\n");
for x in Table1 do Print(x,"\n"); od;
Print("\nData for the lines of the valuation geometry:\n");
for x in Table2 do Print(x,"\n"); od;
# It is convenient to store the valuation geometries as point-line geometries along with their collinearity graph.
# The following function takes a set S of valuations as input and returns the geometry (P,L,T) where P = {1,...,|S|}
# and lines are sets of the type {i,j,k} such that {S[i],S[j],S[k]} is a line in the valuation geometry.
LoadPackage("grape");
ConstructValuationGeometry := function(S)
#Input is a set of valuations with each element of the form [hyperplane complement, valuation, type]
#Output is the point line geometry with points as valuations and lines as the neighboring sets
local P, L, Adj, i, j, k, x, y,T;
P := [1..Size(S)];
Adj := NullMat(Size(P), Size(P), 1);
L := Set([]);
for i in [1..Size(S)] do
for j in [i+1..Size(S)] do
if IsNeighboring(S[i][2], S[j][2]) then
x := ThirdFromTwo(S[i][2], S[j][2]);
k := Position(List(S, y -> y[2]), x);
if k <> fail then T := Set([i,j,k]); AddSet(L,T); Adj[i][j] := 1; Adj[j][i] := 1; fi;
fi;
od;
od;
return [P,L, Graph(Group(()),P, OnPoints, function(x,y) return Adj[x][y] = 1; end, true)];
end;
if IsDual then
#We will now check all the results of Lemma 3.1. The results are stored in the variables check1, check2 and check3.
S := GenerateOrbit(Valuations[2]);
Geom := ConstructValuationGeometry(S); #the geometry of valuations of type C
P := Geom[1];
L := Geom[2];
T := Geom[3]; #the collinearity graph
proj := function(x) #computing the unique point of value 0 of a type C valuation
return Filtered(points, p -> S[x][2][p] = 0)[1];
end;
check1 := IsConnectedGraph(T);
check2 := ForAll(L, l -> ForAll(Combinations(l,2), x -> dist(proj(x[1]),proj(x[2])) = 3));
ThirdPoint := function(T,x,y)
return Intersection(DistanceSet(T,1,x), DistanceSet(T,1,y))[1];
end;
CheckGrid := function(T,x,y)
local I,i,j,p,q,x1,x2,x3,x4;
I := Intersection(DistanceSet(T,1,x),DistanceSet(T,1,y));
if Size(I) = 1 then return false; fi;
for i in Combinations(I,2) do
p := i[1]; q := i[2];
x1 := ThirdPoint(T,x,p);
x2 := ThirdPoint(T,y,q);
x3 := ThirdPoint(T,x,q);
x4 := ThirdPoint(T,y,p);
if Distance(T,x1,x2) = 1 and Distance(T,x3,x4) = 1 then
if ThirdPoint(T,x1,x2) = ThirdPoint(T,x3,x4) then return true; fi;
fi;
od;
return false;
end;
p := 1; #it suffices to make this computation on one fixed point since all type C points are isomorphic
check3 := ForAll(Filtered(DistanceSet(T,2,p), x -> CheckGrid(T,p,x)), y -> dist(proj(p), proj(y)) = 3);
fi;