# GAP code for ``The uniqueness of a certain octagon of order (2,4)’’, Part III # Author: Bart De Bruyn # In the following code, we determine the valuations of GO(2,1) without # invoking the connection with hyperplanes. The code is equivalent with # a backtrack search. At the end of the code, we will give one specific # point the value 0 and all its neighbors value 1. Then we try to complete # this ``partial valuation’’ to a valuation of GO(2,1). Once a partial # valuation has been completed, we add it to an array, called processed (see # the procedure ``CreateVals’’). Those which have not been completed remain # in an array, called ``nonprocessed1’’. A partial valuation which could not # be completed because of some inconsistency is removed from ``nonprocessed1’’ # Put J equal to 4 if one wants to compute all valuations, and equal to 2 if # one wants to compute only those valuations that are neither classical, nor # semi-classical. This code runs faster, as the maximal value of any such # valuation is at most 2. A separate code must then be written to determine # all semi-classical valuations. Such a code has not been implemented here. J:=4; # As before, we determine a computermodel for GO(2,1). g:=AllPrimitiveGroups(DegreeOperation,45,Size,1440)[1]; orbs:=Orbits(Stabilizer(g,1),[1..45]); dist1:=Filtered(orbs,x->Size(x)=4)[1]; dist2:=Filtered(orbs,x->Size(x)=8)[1]; perp:=Union([1],dist1); perp2:=OnSets(perp,RepresentativeAction(g,1,dist2[1])); dist3:=Filtered(orbs,x->Size(x)=16 and Intersection(x,perp2)<>[])[1]; dist4:=Filtered(orbs,x->Size(x)=16 and Intersection(x,perp2)=[])[1]; line:=Intersection(perp,OnSets(perp,RepresentativeAction(g,1,dist1[1]))); lines:=Orbit(g,line,OnSets); partition:=[[1],dist1,dist2,dist3,dist4]; DistMat:=NullMat(45,45); for x in [1..45] do r:=RepresentativeAction(g,x,1); for y in [1..45] 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; # The following code allows to verify whether the values assigned by val # to the points of a given line L are consistent with those of a 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; # The following code allows to verify this for all lines. IsVal2:=function(val) return ForAll(lines,l->IsVal1(val,l)); end; # The following code allows to verify whether val satisfies property (PV3) # in the definition of polygonal valuation. Dist1:=List([1..45],i->OnSets(Set(dist1),RepresentativeAction(g,1,i))); IsVal3:=function(val) local M,i,j,k,Status,A; Status:=true; M:=Maximum(val); for i in [1..45] do if val[i]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; # The following code allows to verify whether two valuations val1 and val2 # are isomorphic. IsoVals:=function(val1,val2) return Isomorphic(g,Parts(val1),Parts(val2)); end; # The following code can replace the above-defined functions Isomorphic and # IsoVals. However, the running time of the program would then increase. #IsoVals:=function(val1,val2) # return RepresentativeAction(g,Parts(val1),Parts(val2),OnTuplesSets)<>fail; #end; # Given a partial valuation val, the following procedure Complete1 tries to # attribute values to the points of a given line L. If some inconsistency has # occurred during the process, then fail is returned. If no inconsistency has # occurred, then a ``more completed’’ version of val will be returned as val1. Complete1:=function(val,L) local X,I,val1,i,Status; X:=Set(Filtered([1..45],x->val[x]<>fail)); I:=Intersection(L,X); if Size(I)=3 and not(IsVal1(val,L)) then return fail; fi; if Size(I)=3 and IsVal1(val,L) then return val; fi; if Size(I) in [0,1] then return 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]] and val[I[1]]=0 then Status:=false; 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; if not(Status) then return fail; fi; return val1; end; # Given a partial valuation val, the following procedure tries to create a more # complete version of val, after having given the point x (which had not yet been # assigned a value) the value i. It makes several times use of the routine # Complete1 applied to all lines of GO(2,1). The procedure again returns fail if # some inconsistency has occurred during the completion process, and a more # completed version of val (namely val2) if no inconsistency has occurred. 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<>fail; if A=fail then break; fi; val2:=A; od; if val2 = val1 then Status2:=false; fi; od; if not(Status1) then return fail; fi; return val2; end; # If one wants to apply Complete2, it is 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..45],x->val[x]=fail)); if X=[] then return fail; fi; if X<>[] then return X[1]; fi; end; # Given a partial incomplete valuation, the following code creates a list of # possible valuations arising from it (Property (PV3) has not yet been # verified for any of these possible candidates). CreateVals:=function(incomplete) local val1,val2,nonprocessed1,nonprocessed2,processed,i,x,Q; nonprocessed1:=[incomplete]; processed:=[]; while nonprocessed1<>[] do nonprocessed2:=[]; for val1 in nonprocessed1 do for i in [0..J] do x:=NoAssignedValue(val1); Q:=Complete2(val1,x,i); if Q<>fail then val2:=Q; 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; # The previous code is applied to the partial valuation for which one specific # point has value 0, and all its neighbors have value 1. The list of possible # valuations (valuations1) is subsequently reduced to those that are actually # valuations (valuations2). Then a complete list of nonisomorphic valuations # (valuations) is created. incomplete:=ListWithIdenticalEntries(45,fail); incomplete[1]:=0; for i in dist1 do incomplete[i]:=1; od; valuations1:=CreateVals(incomplete); valuations2:=Filtered(valuations1,val->IsVal(val)); valuations:=[valuations2[1]]; for i in [2..Size(valuations2)] do New:=true; for j in [1..Size(valuations)] do if IsoVals(valuations2[i],valuations[j]) then New:=false; fi; od; if New then Append(valuations,[valuations2[i]]); fi; od;