# The following code implements a model of HJ with point set [1..315], line set
# lines and automorphism group g.
g:=AllPrimitiveGroups(DegreeOperation,315)[3];
orbs := Orbits(Stabilizer(g,1),[1..315]);
dist1 := Filtered(orbs,x->Size(x)=10)[1];
dist2 := Filtered(orbs,x->Size(x)=80)[1];
dist3 := Filtered(orbs,x->Size(x)=160)[1];
dist4 := Filtered(orbs,x->Size(x)=64)[1];
perp := Union([1],dist1);
line := Intersection(perp,OnSets(perp,RepresentativeAction(g,1,dist1[1])));
lines := Orbit(g,line,OnSets);
# The file HallJanko2.g contains an isomorphic copy of each of the 470
# hyperplane complements of the Hall-Janko near octagon HJ (created by
# HallJanko1.g). These hyperplane complements will be used here to find all
# valuations of HJ.
Read("HallJanko2.g");
# The function ISVal2 below checks whether a certain array val consisting of 315
# integers is a semi-valuation (= valuation without the condition that the
# smallest value is equal to 0). 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, -3 and -4.
Parts:=function(val)
local i,parts;
parts:=[[],[],[],[],[]];
for i in [1..315] do Append(parts[-val[i]+1],[i]); od;
return parts;
end;
# Suppose h is a group of automorphisms of HJ, 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. These valuations will be scaled here in such a way that their
# maximal values are equal to 0. 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..315],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 HJ. 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..315],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(315,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..4] 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 valuations which contains
# a representative of each isomorphism class of valuations. Along the way we also
# verify that every hyperplane complement is associated with at most one valuation.
# If this is the case then Status1 will be true.
valuations:=[]; Status1:=true;
for i in [1..Size(hypcomplements)] do
vals1:=CreateVals(hypcomplements[i]);
if not(Size(vals1) in [0,1]) then Status1:=false; fi;
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 there are, up to isomorphism, five valuations (Type A, B, C, D
# or E). With the following function, we can determine the type of a valuation val.
TypeVal:=function(val)
if List(Parts(val),Length)=[ 64, 160, 80, 10, 1 ] then return "A"; fi;
if List(Parts(val),Length)=[ 192, 112, 10, 1, 0 ] then return "B"; fi;
if List(Parts(val),Length)=[ 160, 128, 26, 1, 0 ] then return "C"; fi;
if List(Parts(val),Length)=[ 200, 110, 5, 0, 0 ] then return "D"; fi;
if List(Parts(val),Length)=[ 160, 130, 25, 0, 0 ] then return "E"; fi;
end;
# With the following function, we can determine the hyperplane complement
# associated with a certain valuation val.
ValToCompl:=function(val)
return Parts(val)[1];
end;
# We determine all hyperplane complements associated with valuations.
for i in [1..5] do
val:=valuations[i];
if TypeVal(val)="A" then complsA:=Orbit(g,ValToCompl(val),OnSets); fi;
if TypeVal(val)="B" then complsB:=Orbit(g,ValToCompl(val),OnSets); fi;
if TypeVal(val)="C" then complsC:=Orbit(g,ValToCompl(val),OnSets); fi;
if TypeVal(val)="D" then complsD:=Orbit(g,ValToCompl(val),OnSets); fi;
if TypeVal(val)="E" then complsE:=Orbit(g,ValToCompl(val),OnSets); fi;
od;
# We determine all valuations.
ValsA:=List(complsA,x->CreateVals(x)[1]);
ValsB:=List(complsB,x->CreateVals(x)[1]);
ValsC:=List(complsC,x->CreateVals(x)[1]);
ValsD:=List(complsD,x->CreateVals(x)[1]);
ValsE:=List(complsE,x->CreateVals(x)[1]);
Vals:=Union(ValsA,ValsB,ValsC,ValsD,ValsE);
# 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..315];
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..315] 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;
LoadPackage("grape");
# We now implement the graph Gr whose vertices are the Type A, B and C valuations,
# where two distinct vertices are adjacent whenever they are incident with some
# line of Type AAA, ABB, ACC, BBC or CCC of the valuation geometry V.
# We first implement the adjacency relation.
Adj:=function(val1,val2)
return val1<>val2 and NB(val1,val2) and ThirdVal(val1,val2) in Vals and
LineType([val1,val2,ThirdVal(val1,val2)]) in [["A","A","A"],["A","B","B"],
["A","C","C"],["B","B","C"],["C","C","C"]];
end;
# The graph Gr is defined.
Gr:=Graph(Group(()),Union(ValsA,ValsB,ValsC),OnTuples,Adj,true);
# We compute all maximal cliques of Gr, and verify that they all have size 3.
# If this is the case, then Status2 will be true.
cliques:=CompleteSubgraphs(Gr);
Status2 := Set(List(cliques,Size))=[3];
# With the following code we verify that the diameter of Gr is 4. If this is
# the case then Status3 will be true
Status3 := Diameter(Gr)=4;
# The following function would write a list L in GAP to a file.
# The elements of L[i] are written in the ith line of the file.
WriteListToFile := function(L, name)
local f, l, p;
f := OutputTextFile(name, false);
for l in L do
for p in l do
AppendTo(f, p , " ");
od;
AppendTo(f, "\n");
od;
CloseStream(f);
end;
# We write the cliques of the graph "Gr" to the file "lines". This file can later
# be imported in SAGE to do certain computations.
WriteListToFile(cliques,"lines");
# In Sage we have verified that the graph Gr is the collinearity graph of a near
# octagon. We also determined its automorphism group and verified that its derived
# subgroup has index 2, and is a simple group of order |G2(4)|.
# We can also verify in GAP that Gr is the collinearity graph of a near octagon.
# This will be done below. If Gr is the collinearity graph of a near octagon, then
# Status 4 below will be true. The computation time in GAP is however much bigger
# than the computation time in SAGE.
# If you want to verify that Gr is the collinearity graph of a near octagon, then
# put Verification equal to true, otherwise equal to false.
Verification:=false;
if Verification then
# The following function allows to verify whether Axiom (NP2) in the definition of
# of near polygon is satisfied with respect to the point a.
check:=function(a)
local i,help,Status;
Status:=true;
for i in [1..Size(cliques)] do
help:=List(cliques[i],x->Distance(Gr,a,x));
Sort(help);
Status := Status and (help in [[0,1,1],[1,2,2],[2,3,3],[3,4,4]]);
od;
return Status;
end;
# By the definition of Gr, its automorphism group has at most three orbits on the
# set of vertices. So, in order to verify (NP2), we should use the function check
# only three times.
for i1 in [1..4095] do if VertexName(Gr,i1) in ValsA then break; fi; od;
for i2 in [1..4095] do if VertexName(Gr,i2) in ValsB then break; fi; od;
for i3 in [1..4095] do if VertexName(Gr,i3) in ValsC then break; fi; od;
Status4 := check(i1) and check(i2) and check(i3);
fi;