LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=
<Text-field style="Heading 1" layout="Heading 1">Find Group (Up to size 200)</Text-field> # Input: TDSteps (Three Dimensional Step Set) # Output: List (List of Group Elements) GenGP := proc(TDSteps) local add2,Am1,A0,A1,Bm1,B0,B1,Cm1,C0,C1,N,S,phi,psi,tau,List,t2I,t2P,t2T,newI,newP,newT,i,k; # Various things needed later add2 := set -> add(X^k*Y^k*Z^k,k=set): S := add2(TDSteps): Am1 := coeff(S,Z,-1): A0 := coeff(S,Z,0): A1 := coeff(S,Z,1): Bm1 := coeff(S,Y,-1): B0 := coeff(S,Y,0): B1 := coeff(S,Y,1): Cm1 := coeff(S,X,-1): C0 := coeff(S,X,0): C1 := coeff(S,X,1): phi := S -> simplify(subs(X=S,Y=S,Z=S,[(1/X)*Cm1/C1,Y,Z])): psi := S -> simplify(subs(X=S,Y=S,Z=S, [X,(1/Y)*Bm1/B1,Z])): tau := S -> simplify(subs(X=S,Y=S,Z=S, [X,Y,(1/Z)*Am1/A1])): # This iteration will stabalize if the group is finite List:= [ [[],[x,y,z]] ]: N := -1: while (N <> nops(List)) and (nops(List)<200) do N := nops(List): for i in List do newI := true: newP := true: newT := true: t2I := phi(i): t2P := psi(i): t2T := tau(i): t2I := map(x->normal(expand(numer(x))/expand(denom(x))),t2I): t2P := map(x->normal(expand(numer(x))/expand(denom(x))),t2P): t2T := map(x->normal(expand(numer(x))/expand(denom(x))),t2T): for k in List do if k=t2I then newI := false: fi: if k=t2P then newP := false: fi: if k=t2T then newT := false: fi: if not (newI or newP or newT) then break: fi: od: if newI then List := [ [[phi,op(i)],t2I], op(List)]: fi; if newP then List := [ [[psi,op(i)],t2P], op(List)]: fi; if newT then List := [ [[tau,op(i)],t2T], op(List)]: fi; if nops(List)>200 then break: fi: od: od: if nops(List)<200 then return List else return FAIL: fi: end:
<Text-field style="Heading 1" layout="Heading 1">Find Orbit Sum</Text-field> # Input: TDSteps (Three Dimensional Step Set) # Output: Ex (Expression resulting from orbit sum) # Requires GenGP function defined above OrbitSum := proc(TDSteps) local List,EQ,Ex,T,K,i,k; K := 1-simplify(t*add(x^k*y^k*z^k,k=TDSteps)): List := GenGP(TDSteps): # Sum the Kernel Equation after it's acted upon by the group elements EQ := Kk*X*Y*Z*Q(X,Y,Z) = X*Y*Z + F(Y,Z) + G(X,Z) + H(X,Y): Ex := 0: for i from 1 to nops(List) do T := subs(X=List[i],Y=List[i],Z=List[i],EQ): Ex := Ex+(-1)^nops(List[i])*T: od: #The result: Ex := expand(lhs(Ex)/(Kk*x*y*z)) = simplify(rhs(Ex)/(K*x*y*z)): return Ex: end:
<Text-field style="Heading 1" layout="Heading 1">Code to Generate 3D Counting Sequences</Text-field> # Updates walk locations after one iteration # Input: Current Locs, Place to Store New Locs, Step Set, and Bounds Update3D := proc(Locations,NewLocations,Steps,max) local i,j,k,s; for i from 0 to max do for j from 0 to max do for k from 0 to max do if type(Locations[i,j,k],integer) then for s in Steps do if (i+s)<0 or (j+s)<0 or (k+s)<0 then ; elif type(NewLocations[i+s,j+s,k+s],integer) then NewLocations[i+s,j+s,k+s] := NewLocations[i+s,j+s,k+s]+Locations[i,j,k]; else NewLocations[i+s,j+s,k+s] := Locations[i,j,k] #Was previously zero end if; end do; end if; end do; end do; end do; end: # Sums terms in a table # Input: Table and Bounds SumTab3D := proc(Table,max) local i,j,k,out; out := 0; for i from 0 to max do for j from 0 to max do for k from 0 to max do if type(Table[i,j,k],integer) then out := out + Table[i,j,k]; fi;od;od;od; return out; end: # Returns list with the number of walks up to length k # Input: Step set (as list of lists) and number of steps Count3D := proc(StepsT,k) local Steps,tt,Locations,NewLocations,F,Points,temp; Steps := eval(StepsT): Locations := 'Locations': Locations[0,0,0] := 1: NewLocations := 'NewLocations': F := : for temp from 1 to k do Update3D(Locations,NewLocations,Steps,temp-1); tt := SumTab3D(NewLocations,temp): F := [op(F),tt]; Locations := copy(NewLocations): NewLocations := 'NewLocations': end do: return F: end:
<Text-field style="Heading 1" layout="Heading 1">Code to Check Hadamard Decomposition</Text-field> # Checks Cartesian product condition of Hadamard definition (for V and T) # Input: Set of steps to check, d (as in Hadamard definition) checkCart := proc(ST,d) local dCoords,deltaCoords,CP,j,k: dCoords := {op(map(a->a[1..d],ST))}: deltaCoords := {op(map(a->a[d+1..-1],ST))}: CP := {}: for j in dCoords do for k in deltaCoords do CP := CP union {[op(j),op(k)]}: od:od: return evalb(CP = {op(ST)}),dCoords,deltaCoords: end: # Returns a (d,|S|-d) - Hadamard decomposition of a step set (if it exists) # Input: Set of steps to check, d (as in Hadamard definition) HadamardDecomp := proc(ST,d) local perms,S,j,k,U,T,V,flag: # Must check all permutations of the step set perms := combinat[permute]([seq(j,j=1..nops(ST))]): for k in perms do S := {op(map(x->[x[k],x[k],x[k]],ST))}: U := select(a->a[1..d]=[seq(0,k=1..d)],S): flag,V,T := checkCart(S minus U,d): U := map(x->x[d+1..-1],U): if flag then return [true,U,V,T]: fi: od: return [false,{},{},{}]: end:
read "ThreeDSteps.txt": # The list ThreeDSteps holds all three dimensional models we consider nops(ThreeDSteps); ThreeDSteps; Count3D(ThreeDSteps,15); IiYvMyM= NyU3JSEiIkYkIiIiNyUiIiFGJUYkNyVGJUYnRiU= NzIiIiJGIyIiIyIiJSIjNSIjQSIjZiIkXCIiJCdSIiVUNSIlMkgiJWd4IiY7PSMiJilIZyInVChwIiInYV1a # The list ProvenOrbit holds the models with non-zero orbit sum, # proven to admit D-finite generating functions by the kernel method nops(ProvenOrbit); ProvenOrbit; IiQzIg== NyY3JSEiIkYkRiQ3JUYkRiQiIiI3JUYkRiYiIiE3JUYmRihGKA== # The list Hadamard holds the models with zero orbit sum, # proven to admit D-finite generating functions by a Hadamard decomposition nops(Hadamard); Hadamard; IiNW NyY3JSEiIkYkRiQ3JUYkRiQiIiI3JSIiIUYmRig3JUYmRihGKA== # The list NonHadamard holds the models with zero orbit sum which are not Hadamard nops(NonHadamard); NonHadamard; IiM+ NyY3JSEiIkYkRiQ3JSIiIUYmIiIiNyVGJkYnRiY3JUYnRiZGJg== # The function genGP generates the elements of a model's group GenGP(ProvenOrbit); Nyo3JDclSSR0YXVHNiJJJHBoaUdGJkkkcHNpR0YmNyUqKiwoIiIiRiwqJClJInpHRiYiIiNGLEYsKiYpSSJ5R0YmRjBGLEYvRixGLEYsSSJ4R0YmISIiRjNGNUYvRjUqKCwmRixGLEYtRixGLEYzRjVGL0Y1KiRGL0Y1NyQ3JEYnRig3JUYqRjZGLzckNyRGKEYlNyVGNEY2Rjg3JDckRidGJTclRipGM0Y4NyQ3I0YlNyVGNEYzRjg3JDcjRig3JUY0RjZGLzckNyNGJzclRipGM0YvNyQ3IjclRjRGM0Yv # It fails if it detects 200 unique elements in the group GenGP(ThreeDSteps); SSVGQUlMRyUqcHJvdGVjdGVkRw== # The function OrbitSum gives the result of taking an orbit sum over the group elements OrbitSum(ProvenOrbit); LyxOKiopSSJ4RzYiIiIjISIiSSJ5R0YnRikpSSJ6R0YnIiIkRiktSSJRR0YnNiUqKiwoIiIiRjMqJClGLEYoRjNGMyomKUYqRihGM0YsRjNGM0YzRiZGKUYqRilGLEYpKigsJkYzRjNGNEYzRjNGKkYpRixGKSokRixGKUYzRikqKkYlRilGKkYpRixGKUYuRjNGKSoqRiVGKSlGKkYtRikpRiwiIiVGKUYuRjNGKSosRihGM0YlRilGPUYpRjVGKUYuRjNGKSooRiVGKUY9RilGLkYzRikqKkYlRilGKkYpRixGKS1GLzYlRjFGOEYsRjNGMyoqRiVGKUYqRilGLEYzRkNGM0YzKipGJUYpRj1GKUY1RilGQ0YzRjMqKkYoRjNGJUYpRj1GKUZDRjNGMyoqRiVGKUY9RilGNUYzRkNGM0YzKihGN0YpRitGKS1GLzYlRiZGOEY6RjNGMyooRjdGKUYsRilGSkYzRjMqKkYlRilGKkYpRitGKS1GLzYlRjFGKkY6RjNGMyoqRiVGKUYqRilGLEYpRk5GM0YzKipGJUYpRipGM0Y1RilGTkYzRjMqJkY1RiktRi82JUYmRipGOkYzRikqKEY3RilGLEYpLUYvNiVGJkY4RixGM0YpKihGN0YpRixGM0ZWRjNGKSoqRiVGKUYqRilGLEYpLUYvNiVGMUYqRixGM0YpKipGJUYpRipGKUYsRjNGWkYzRikqKEYlRilGKkYzRlpGM0YpLUYvNiVGJkYqRixGMywkKiwsNkYzRilGNEYpKiRGPkYzRjMqJClGLCIiJ0YzRjMqKEYlRjNGLEYzRipGM0YzKiYpRipGP0YzRjVGM0YzKihGJUYzRj1GM0Y1RjNGKSooKUYsIiImRjNGKkYzRiVGM0YpKiZGY29GM0Y+RjNGKSooRiVGM0Y9RjNGPkYzRjNGM0YrRilGJkYpRjdGKSwsKihGLEYzRiZGM0YqRjNGKUkidEdGJ0YzKiZGXHBGM0Y1RjNGMyooRlxwRjNGN0YzRixGM0YzKipGXHBGM0YlRjNGLEYzRipGM0YzRilGKQ== # The right hand side is zero for the walks with orbit sum zero rhs(OrbitSum(Hadamard)); IiIh # The function HadamardDecomp computes the Hadamard decomposition of a step set, if it exists # This step set has a (1,2)-Hadamard decomposition Hadamard; HadamardDecomp(Hadamard,1); NyY3JSEiIkYkRiQ3JUYkRiQiIiI3JSIiIUYmRig3JUYmRihGKA== NyZJJXRydWVHJSpwcm90ZWN0ZWRHPCQ3JCIiISIiIjckRihGJzwkNyMhIiI3I0YoPCM3JEYsRiw= # This step set has a (2,1)-Hadamard decomposition Hadamard; HadamardDecomp(Hadamard,1); HadamardDecomp(Hadamard,2); NyY3JSEiIkYkRiQ3JUYkIiIhIiIiNyVGJEYnRiY3JUYnRiZGJg== NyZJJmZhbHNlRyUqcHJvdGVjdGVkRzwiRiVGJQ== NyZJJXRydWVHJSpwcm90ZWN0ZWRHPCM3IyIiIjwlNyQhIiJGKjckIiIhRic3JEYnRiw8IzcjRio= LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=