Example 4.7 (An Infinite Group Model)

Proving the group of a small step quadrant model is infinite.
Requirements: None

# Define the step set under consideration and its characteristic polynomial
var('x,y,X,Y')
ST = [(-1,-1), (0,-1), (0,1), (1,0), (-1,0)]
S = add(X^i*Y^j for [i,j] in ST)
S

X + Y + 1/X + 1/Y + 1/(X*Y)

# First, we prove through direct computation that the group is infinite
# Start by computing the unique stationary point with positive coordinates
Sx = diff(S,X).numerator()
Sy = diff(S,Y).numerator()
R.<a,b> = QQbar[]
J = R.ideal(Sx(a,b),Sy(a,b))
[stat] = [k for k in J.variety(QQbar) if a.subs(k)>0 and b.subs(k)>0]
print(stat)

{b: 1.324717957244746?, a: 1.324717957244746?}

# These algebraic coordinates are stored and manipulated exactly in Sage
a.subs(stat).radical_expression()

(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3) + 1/3/(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3)

# Compute the Jacobian matrix of the map Θ(x,y) = Φ(Ψ(x,y)) at the stationary point (a,b)
Am1 = S.coefficient(Y,-1);  A0 = S.coefficient(Y,0);  A1 = S.coefficient(Y,1)
Bm1 = S.coefficient(X,-1);  B0 = S.coefficient(X,0);  B1 = S.coefficient(X,1)
def Ψ(SS): return [L.subs(X=SS[0],Y=SS[1]).simplify() for L in [(1/X)*Bm1/B1,Y]]
def Φ(SS): return [L.subs(X=SS[0],Y=SS[1]).simplify() for L in [X,(1/Y)*Am1/A1]]
T = Φ(Ψ([x,y]))
J = jacobian(T, (x,y)).subs(x=a.subs(stat),y=b.subs(stat))
show(J)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rr} -1 & -0.4301597090019468? \\ 0.4301597090019468? & -0.814962624751361? \end{array}\right)$$

# Compute the eigenvalues of the Jacobian
eig = MatrixSpace(QQbar,2,2)(J).eigenvalues()
eig

[-0.907481312375681? + 0.4200924513591182?*I, -0.907481312375681? - 0.4200924513591182?*I]

# The eigenvalues are not roots of unity, so the group of the model is infinite
[arg(k) for k in eig]

[pi - arctan(0.4629213248032239?), -pi + arctan(0.4629213248032239?)]

# ALTERNATIVELY, following the argument of the text the following computation gives an annihilating polynomial of the eigenvalues
var('L')
eq1 = (L^2 - (1/(1+x)/(1+y)-2)*L+1).numerator()
eq2 = Sx(x,y)
eq3 = Sy(x,y)
res = eq1.resultant(eq2,x).resultant(eq1.resultant(eq3,x),y).factor()
res

-(L^6 + 8*L^5 + 28*L^4 + 41*L^3 + 28*L^2 + 8*L + 1)*(L^2 + 3*L + 1)^2*(L + 1)^2*L^2

# Of course, the roots of this polynomial includes the two eigenvalues as computed above
QQbar['L'](res).roots(multiplicities=False)

[-2.618033988749895?,
 -1,
 -0.3819660112501051?,
 0,
 -2.874631498544436? - 2.220293676030299?*I,
 -2.874631498544436? + 2.220293676030299?*I,
 -0.907481312375681? - 0.4200924513591182?*I,
 -0.907481312375681? + 0.4200924513591182?*I,
 -0.2178871890798835? - 0.1682906307285094?*I,
 -0.2178871890798835? + 0.1682906307285094?*I]

# Standard bounds (for instance, Thm 8.8.7 in Bach and Shallit, Algorithmic Number Theory Vol. 1, 1996) on the degrees
# of cyclotomic polynomials imply any cyclotomic polynomial of degree <= 6 has index < 30. Thus the group is
# infinite as long as the degree six factor of the polynomial res above is not in the following list.
from sage.rings.polynomial.cyclotomic import cyclotomic_coeffs
P = QQ['L']
[P.cyclotomic_polynomial(k) for k in range(1,30) if P.cyclotomic_polynomial(k).degree() <= 6]

[L - 1,
 L + 1,
 L^2 + L + 1,
 L^2 + 1,
 L^4 + L^3 + L^2 + L + 1,
 L^2 - L + 1,
 L^6 + L^5 + L^4 + L^3 + L^2 + L + 1,
 L^4 + 1,
 L^6 + L^3 + 1,
 L^4 - L^3 + L^2 - L + 1,
 L^4 - L^2 + 1,
 L^6 - L^5 + L^4 - L^3 + L^2 - L + 1,
 L^6 - L^3 + 1]