Solvability of Some Combinatorial Problems
Anthony Guttmann
Department of Mathematics, University of Melbourne, Australia
Algorithms Seminar
December 2, 1996
[summary by Dominique GouyouBeauchamps]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
Some of the most famous results in mathematics involve a proof of the intrinsic
unsolvability of certain problemssuch as the roots of a general quintic. In
mathematical physics such results are largely unknown. I will describe
a powerful
numerical technique that provides compelling evidence for (but is not a proof
of) the unsolvability of a wide variety of classical, unsolved problems in
Statistical Mechanics and Combinatorics, in terms of the ``standard'' functions
of mathematical physics (including Dfinite functions).
1 Inversion relation
An inversion relation is a functional relation satisfied by a transfer matrix,
and hence satisfied by the partition function (and hence satisfied by
correlation functions). It is connected with concepts of integrability
and the startriangle relation (Onsager [7], Baxter [1],
Maillard, Stroganoff [8]).
An inversion relation exists for many unsolved models e.g., 2d Ising model
in a magnetic field, 2d Potts model (noncritical), 3d Ising model (H=0) etc.
It gives a strong constraint on the partition function and correlation
function.
We first consider the transfer matrix for the Ising model with d=1 and
H¹ 0 (see [4, 3]). The free energy is
b H 
=K 

s_{i}s_{j}+H 

s_{i} 
with j=i+1, s_{i}=± 1 and s_{N+1}=s_{1}.
The interaction energy between each pair of successive atoms depends on
whether their internal coordinates are alike or different:
u(1,1)=u(1,1)=u(1,1)=u(1,1)=K.
The canonical partition function Z(K,H) of the model is defined as
Z(K,H) 
= 

e 

=


å 
s_{1},s_{2},...,s_{N}=± 1 

exp 
æ ç ç è 
 

u(s_{k},
s_{k+1})Hs_{k} 
ö ÷ ÷ ø 


= 

å 
s_{1},s_{2},... ,s_{N}=± 1 

exp 
æ ç ç è 

(Ks_{k} s_{k+1}+Hs_{k}) 
ö ÷ ÷ ø 
. 

We express this sum in terms of a transfer matrix T^{~} whose
elements are
where d is the Kronecker delta function. Then the summation over
(s_{1},s_{2},... ,s_{N}) is equivalent to matrix multiplication,
and we obtain
Z(K,H)= 

(s_{1} 

^{N}s_{1})=
Tr 
( 

^{N}). 
The transfer matrix
T^{~} is

= 
æ è 
e^{K+H} 
e^{K} 
e^{K} 
e^{K+H} 

ö ø 

and by inspection

(K,H) 

(K+ 

,H)=2isinh 
(2K) 

and the partition function verifies
Z(K,H)Z(K+ 

,H)=2isinh (2K). 
This inversion relation can be confirmed taking the
partition function definition:
Z(K,H)=e^{K}cosh H+(e^{2K}sinh ^{2}H+e^{2K})^{1/2}.
For the anisotropic 2d Ising model [7],
the free energy is
b H 
=K_{1} 

^{(1)}s_{i}s_{j}
+K_{2} 

^{(2)}s_{i}s_{j}. 
The diagonaltodiagonal transfer matrix leads to the following inversion
relation for the partition function
Z(K_{1},K_{2})Z(K_{1},K_{2}+ 

)=2isinh (2K_{2}). 
Let t_{1}=tanh (J_{1}/kT), t_{2}=tanh (J_{2}/kT). We define the reduced
partition function
L (t_{1},t_{2})=(2cosh K_{1}cosh K_{2})^{1}Z(K_{1},K_{2}).
This satisfies the functional relation
ln L (t_{1},t_{2})+ln L (1/t_{1},t_{2})=ln (1t_{2}^{2}).
Now a series expansions gives:
ln L (t_{1},t_{2}) 
= 

a_{mn}t_{1}^{2m}t_{2}^{2n} 


=t_{1}^{2}t_{2}^{2}+
t_{1}^{4}t_{2}^{2}+t_{1}^{2}t_{2}^{4}+t_{1}^{6}t_{2}^{2}+t_{1}^{2}t_{2}^{6}+ 

t_{1}^{4}t_{2}^{4}
+t_{1}^{8}t_{2}^{2}+t_{1}^{2}t_{2}^{8}+5t_{1}^{6}t_{2}^{4}+5t_{1}^{4}t_{2}^{6}+··· 

and a partial sum over m yields:
ln 
L (t_{1},t_{2})= 

R_{n}(t_{1}^{2})t_{2}^{2n} 
where R_{n}(t_{1}^{2})=å_{m}a_{m,n}t_{1}^{2m} is the generating functions
for graphs with 2n vertical steps. From graphical expansion, we obtain
R_{1}(t_{1}^{2})= 

,
R_{2}(t_{1}^{2})= 
t_{1}^{2}1/2t_{1}^{4}+1/2t_{1}^{6} 

(1t_{1}^{2})^{3} 

and from higher order terms we see a pattern [1]
R_{n}(t_{1}^{2})= 
P_{2n1}(t_{1}^{2}) 

(1t_{1}^{2})^{2n1} 

. 
The fact that the only singularity of the denominator occurs at t_{1}^{2}=1,
plus inversion relation, plus obvious symmetry
(L (t_{1},t_{2})=L (t_{2},t_{1})) completely determines the polynomials
P_{2n1}(t^{2}), and hence implicitly yields the Onsager solution [1].
The zerofield susceptibility of the triangular lattice Ising
model [5],
with coupling constants K_{1}, K_{2}, K_{3}, and t_{i}=tanh (K_{i}), satisfies
an inversion relation [6]
c (t_{1},t_{2},t_{3})+c (t_{1},t_{2},1/t_{3})=0.
Since the anisotropic square lattice can be obtained by setting one of
the anisotropic coupling constants to zero, it follows that the anisotropic
square lattice susceptibility satisfies the inversion relation
c (t_{1},t_{2})+c (1/t_{1},t_{2})=0, as well as the symmetry relation
c (t_{1},t_{2})=c (t_{2},t_{1})=0. Writing the high temperature expansion
c (t_{1},t_{2})= 

c_{mn}t_{1}^{m}t_{2}^{n}=


H_{n}(t_{1})t_{2}^{n}, 
the inversion relation then implies H_{n}(t_{1})+(1)^{n}H_{n}(1/t_{1})=0.
The first five values of H_{n}(x) were given in [5], and I. G. Enting
and A. J. Guttmann recently reported the calculation of H_{n}(x) for n£ 14.

H_{2}(t)= 
2(1+6t+8t^{2}+6t^{3}+t^{4}) 

(1t)^{3}(1+t) 

,
H_{3}(t)= 
2(1+8t+10t^{2}+8t^{3}+t^{4}) 

(1t)^{4} 

, 

H_{4}(t)= 
2(1+t^{10}+15(t+t^{9})+71(t^{2}+t^{8})+192(t^{3}+t^{7})+326(t^{4}+t^{6})+388t^{5}) 

(1t^{3})(1t)^{4}(1+t)^{3} 

,..., 

H_{10}(t)= 
2(1+t^{34}+45(t+t^{33})+758(t^{2}+t^{32})+... +
1075878111(t^{16}+t^{18})+1131919146t^{17}) 

(1t^{3})^{7}(1t)^{4}(1+t)^{9} 

. 

In all cases enumerated, the numerator polynomial is unimodal and symmetric
with positive coefficients. The numerator and denominator polynomials
(with no common factors) are of equal degree. The susceptibility of the
Ising model can be expressed as an expansion in terms of (2k+1) particle
excitations [9]. Hence the structure of the denominator is clear.
The contribution of the terms
from the 2k+1 particle excitations, which first contribute at, say, O(t^{2m}),
correspond to poles at t^{2k+1}=1 in H_{m}(t) in the anisotropic expansion
above. We can identify the first occurrence of the term (1t^{2k+1}) in the
denominator with the first occurrence of a (2k+1) particle excitation.
From this observation, we see that structure of H_{n}(t)
is that of a rational function whose poles all lie on the unit circle in the
complex t plane, so that poles become dense on the unit circle as n
gets large.
Hence c (t_{1},t_{2}) as a function of t_{1} for t_{2} fixed
(i.) has a natural boundary; (ii.) is not algebraic;
and (iii). cannot be expressed in terms of the ``usual''
functions of mathematical
physics, such as elliptic integrals, hypergeometric functions etc.
One family of solutions that does suggest itself as a possible candidate is
the family of qdeformations of standard functions. Several examples
are known already in the work done in both Camberra and Melbourne, as well
as Bordeaux and various other places.
Now this suggests a powerful tool: generalize to the anisotropic model and
study the distribution of zeros in the denominator of the analogue of
H_{n} functions. Then we can distinguish between those that appear
to be solvable in terms of standard functionswhen there is just a finite
number of singularities on the unit circleand those which are not, with
an infinite number of such singularities.
2 The anisotropic model
We have applied this approach to a number of other unsolved problems in statistical
mechanics of two dimensional systems.
Staircase polygons (or parallelogram polyominoes)
H_{m}(x^{2}) is the generating function for staircase polygons with 2m vertical
bonds.
H_{1}(x^{2}) 

H_{2}(x^{2}) 

H_{3}(x^{2}) 
= 
x^{2}(1+x^{2}) 

(1x^{2})^{5} 

, 

H_{4}(x^{2}) 
= 
x^{2}(1+3x^{2}+x^{4}) 

(1x^{2})^{7} 

, 

H_{5}(x^{2})= 
x^{2}(1+6x^{2}+6x^{4}+x^{6}) 

(1x^{2})^{9} 

,...,
H_{m}(x^{2})= 
x^{2}S_{m}(x^{2}) 

(1x^{2})^{2m1} 

. 
S_{m}(x^{2}) is a symmetric unimodal polynomial of degree (m2). H_{m}(x^{2})
satisfies the inversion relation
H_{m}(x^{2})+x^{2(m1)}H_{m}(1/x^{2})=0
and it follows that the generating function P(x,y) verifies
P(x,y)= 

+G(x,y) where
G(x,y)=x^{2}G(1/x,y/x) and P(x,y)=P(y,x)
. 
The complete solution is implicitly determined by these relations,
initial conditions and the fact that the only singularity of the
denominator occurs at x^{2}=1.
Convex polygons
H_{n}(x^{2}) is the generating function for convex polygons with 2n vertical
bonds.
H_{1}(x^{2})= 

,
H_{2}(x^{2})= 
x^{2}(1+x^{2})^{2} 

(1x^{2})^{3} 

, 

H_{3}(x^{2})= 
x^{2}(1+8x^{2}+13x^{4}+2x^{6}) 

(1x^{2})^{5} 

, 

H_{n}(x^{2})= 
x^{2}T_{n}(x^{2}) 

(1x^{2})^{2n1} 

. 

T_{n} is a unimodal (with positive coefficients), asymmetric (n>2)
polynomial of degree n. Absence of symmetry precludes solution by this
method.
Row convex polygons
P(x,y)¹ P(y,x), 
P(x,y)= 

x^{2n}H_{n}(y^{2})= 

y^{2m}A(x^{2}). 

H_{n}(y^{2})=T_{n}(y^{2})/(1y^{2})^{2n1} where T_{n}(y^{2}) is a symmetric,
unimodal polynomial of degree 2n1 in y^{2} and
H_{n}(y^{2})=H_{n}(1/y^{2}) so P(x,y)+P(x,1/y)=0.
A_{m}(x^{2})=U_{m}(x^{2})/(1x^{2})^{2m1} where U_{m}(x^{2}) is an asymmetric
(m>2), unimodal polynomial of degree 2n1 in x^{2}. Absence of symmetry
precludes solution by this method.
3 choice polygons
The number of 3 choice polygons of 2n steps grows like
If H_{n}(y^{2}) is the generating
function for 3 choice polygons with 2n horizontal bonds, then the general
generating function P(x,y) for 3 choice polygons satisfies
P(x,y)= 

x^{2n}H_{n}(y^{2}). 


H_{4}(y^{2})= 
6+19y^{2}+15y^{4}+4y^{6}) 

(1y^{2})^{7}(1+y^{2}) 

, 

H_{5}(y^{2})= 
10+75y^{2}+194y^{4}+237y^{6}+161y^{8}+66y^{10}5y^{12}12y^{14}+16y^{16}
6y^{20}+2y^{22} 

(1y^{2})^{9}(1+y^{2})^{3} 

. 
The denominator in general is
H_{n}=(1y^{2})^{2n1}(1+y^{2})^{2n7}=(1y^{2})^{6}(1y^{4})^{2n7} for n>3.
This is consistent with solvability and the solution is probably Dfinite.
Square lattice polygons (I. Enting)
We have no inversion relation for this model but P(x,y)=P(y,x).
We define R_{n}(x^{2}) by the relation
P(x,y)= 

R_{n}(x^{2})y^{2n}. 
Numerators of the R_{n}(x^{2}) are unimodal, positive, but not symmetric.
The degree of the numerator is equal to that of the denominator. The
denominator is
(1x^{2})^{2n1} for n£ 4, but for n>4 powers of 1x^{4} enter, and
for n>6 we see powers of 1x^{6} entering, while n=8 marks the first
occurrence of powers of 1x^{8} [3].
Self avoiding walks on square lattice (A. Conway)
We have no inversion relation for this model.
We define H_{n}(x) by the relation
H_{n}(x) (now known up to n=12) is equal to A_{n}^{m}/B_{n}^{m} where A_{n}^{m} and
B_{n}^{m} are polynomials of degree m, A_{n}^{m} is unimodal and B_{n}^{m}
is equal to
B_{n}^{m}(x)=(1x) 

(1+x) 

(1+x+x^{2}) 

(1+x^{2}) 

. 
Up to n=9, we have a=n+1, b=2(ë n/2û) with n>1,
g =n4 with n>4 and d=1,1,3 for 9³ n>6 [2].
Honeycomb polygons (brickwork)
H_{n}(x^{2})=P_{n}(x^{2})/Q_{n}(x^{2}).
The denominator pattern is quite regular. The denominators always have zeros
only on the unit circle [3], just at x^{2}=1 for n£ 3,
with powers of 1x^{4} appearing at n=4, powers of 1x^{6} entering at
n=7 and so on.
Numerators are positive coefficients, unimodal, but not symmetric. The
numerator and denominator are not of equal degree.
Anisotropic, hexagonal directed animals (A. J. Guttmann and A. R. Conway)
The generating function is G(z)=å_{n³ 1}a_{n}z^{n} where a_{n}
is the number of animals with n sites and one source. For square
and triangular lattice Dhar showed

that the generating function is algebraic;
 that the model is equivalent to hard squares in some sense;
 a_{n}~µ ^{n}/(n)^{1/2} with µ =3 for the square lattice
and µ =4 for the triangular lattice.
For the hexagonal lattice, Dhar found µ =2.0252± 0.0005 and
no generating function could be found. We extended the series to 99 terms,
found µ =2.025131± 0.000005 but no exact solution.
The study of an isotropic model G(x,y)=å_{n³ 0}H_{n}(x)y^{n} gives
H_{n}(x)=N_{n}(x)/D_{n}(x) where the denominator pattern can be guessed.
In this case, we have the symmetry G(x,y)=G(y,x).
References
 [1]

Baxter (R. J.). 
Exactly solved models. In Cohen (E. G. D.) (editor), Fundamental
Problems in Statistical Mechanics. vol. 5. 
Amsterdam, 1980. Proceedings of the 1980 Enschede
Summer School.
 [2]

Conway (A. R.) and Guttmann (A. J.). 
Square lattice selfavoiding walks and corrections to scaling. Physical Review Letters, vol. 77, n°26, 1996,
pp. 52845287.
 [3]

Guttmann (A. J.) and Enting (I. G.). 
Inversion relations, the Ising model and selfavoiding polygons.
Nuclear Physics (Proc. Suppl.), vol. 47, 1996,
pp. 735738.
 [4]

Guttmann (A. J.) and Enting (I. G.). 
Solvability of some statistical mechanical systems. Physical
Review Letters, vol. 76, n°3, 1996, pp. 344347.
 [5]

Hansel (D.), Maillard (J. M.), Oitmaa (J.), and Velga (M. J.). 
Analytical properties of the anisotropic cubic Ising model. Journal of Statistical Physics, vol. 48, n°1/2, 1987,
pp. 6980.
 [6]

Jaekel (M. T.) and Maillard (J. M.). 
A disorder solution for a cubic Ising model. Journal of
Physics Series A, vol. 18, 1985, pp. 641651.
 [7]

Onsager (L.). 
Crystal statistics. I. A two dimensional model with an
orderdisorder transition. Physical Review, vol. 65,
1944, p. 117.
 [8]

Stroganov (Y. G.). 
A new calculation method for partition functions in some lattice
models. Physical Letters, vol. 74A, n°1,2, 1979,
pp. 116118.
 [9]

Wu (T. T.), McCoy (B. M.), Tracy (C. A.), and Barouch (E.). 
Spinspin correlation functions for the twodimensional Ising
model: Exact theory in the scaling region. Physical Review B, vol. 13,
1976, pp. 316374.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.