Solvability of Some Combinatorial Problems

Anthony Guttmann

Department of Mathematics, University of Melbourne, Australia

Algorithms Seminar

December 2, 1996

[summary by Dominique Gouyou-Beauchamps]

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 problems---such 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 D-finite 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 star-triangle 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 (non-critical), 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
 
<i,j>
sisj+H
 
i
si
with j=i+1, si= 1 and sN+1=s1. 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)
=
 
s
e
-b H
 
=
 
s1,s2,...,sN= 1
exp


-
 
k
u(sk, sk+1)-Hsk


 
=
 
s1,s2,... ,sN= 1
exp


 
k
(Ksk sk+1+Hsk)


.
We express this sum in terms of a transfer matrix T~ whose elements are
(s |
~
T
 
|s ')=e
-u(s ,s ') +Hd
 
s ,s '
 
= e
Ks s '+Hd
 
s ,s '
 
where d is the Kronecker delta function. Then the summation over (s1,s2,... ,sN) is equivalent to matrix multiplication, and we obtain
Z(K,H)=
 
s1
(s1|
~
T
 
N|s1)= Tr (
~
T
 
N).
The transfer matrix T~ is
~
T
 
=

eK+H e-K
e-K eK+H

and by inspection
~
T
 
(K,H)
~
T
 
(K+
ip
2
,-H)=2isinh (2K)
~
1
 
and the partition function verifies
Z(K,H)Z(K+
ip
2
,-H)=2isinh (2K).
This inversion relation can be confirmed taking the partition function definition:
Z(K,H)=eKcosh H+(e2Ksinh 2H+e-2K)1/2.


For the anisotropic 2d Ising model [7], the free energy is
-b H =K1
 
<i,j>
(1)sisj +K2
 
<i,j>
(2)sisj.
The diagonal-to-diagonal transfer matrix leads to the following inversion relation for the partition function
Z(K1,K2)Z(-K1,K2+
ip
2
)=2isinh (2K2).

Let t1=tanh (J1/kT), t2=tanh (J2/kT). We define the reduced partition function
L (t1,t2)=(2cosh K1cosh K2)-1Z(K1,K2).
This satisfies the functional relation
ln L (t1,t2)+ln L (1/t1,-t2)=ln (1-t22).
Now a series expansions gives:
ln L (t1,t2)
=
 
m,n
amnt12mt22n
 
=t12t22+ t14t22+t12t24+t16t22+t12t26+
5
2
t14t24 +t18t22+t12t28+5t16t24+5t14t26+
and a partial sum over m yields:
ln L (t1,t2)=
n=1
Rn(t12)t22n
where Rn(t12)=mam,nt12m is the generating functions for graphs with 2n vertical steps. From graphical expansion, we obtain
R1(t12)=
t12
1-t12
,     R2(t12)=
t12-1/2t14+1/2t16
(1-t12)3
and from higher order terms we see a pattern [1]
Rn(t12)=
P2n-1(t12)
(1-t12)2n-1
.

The fact that the only singularity of the denominator occurs at t12=1, plus inversion relation, plus obvious symmetry (L (t1,t2)=L (t2,t1)) completely determines the polynomials P2n-1(t2), and hence implicitly yields the Onsager solution [1].

The zero-field susceptibility of the triangular lattice Ising model [5], with coupling constants K1, K2, K3, and ti=tanh (Ki), satisfies an inversion relation [6] c (t1,t2,t3)+c (-t1,-t2,1/t3)=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 (t1,t2)+c (1/t1,-t2)=0, as well as the symmetry relation c (t1,t2)=c (t2,t1)=0. Writing the high temperature expansion
c (t1,t2)=
m,n=0
cmnt1mt2n=
n=0
Hn(t1)t2n,
the inversion relation then implies Hn(t1)+(-1)nHn(1/t1)=0. The first five values of Hn(x) were given in [5], and I. G. Enting and A. J. Guttmann recently reported the calculation of Hn(x) for n 14.
H0(t)=
1+t
1-t
,     H1(t)=
2(1+t)2
(1-t)2
,
H2(t)=
2(1+6t+8t2+6t3+t4)
(1-t)3(1+t)
,     H3(t)=
2(1+8t+10t2+8t3+t4)
(1-t)4
,
H4(t)=
2(1+t10+15(t+t9)+71(t2+t8)+192(t3+t7)+326(t4+t6)+388t5)
(1-t3)(1-t)4(1+t)3
,...,
H10(t)=
2(1+t34+45(t+t33)+758(t2+t32)+... + 1075878111(t16+t18)+1131919146t17)
(1-t3)7(1-t)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(t2m), correspond to poles at t2k+1=1 in Hm(t) in the anisotropic expansion above. We can identify the first occurrence of the term (1-t2k+1) in the denominator with the first occurrence of a (2k+1) particle excitation. From this observation, we see that structure of Hn(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 (t1,t2) as a function of t1 for t2 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 q-deformations 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 Hn functions. Then we can distinguish between those that appear to be solvable in terms of standard functions---when there is just a finite number of singularities on the unit circle---and 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)

Hm(x2) is the generating function for staircase polygons with 2m vertical bonds.

H1(x2)
=
x2
1-x2
,
     H2(x2)
=
x2
(1-x2)3
,
H3(x2)
=
x2(1+x2)
(1-x2)5
,
     H4(x2)
=
x2(1+3x2+x4)
(1-x2)7
,

H5(x2)=
x2(1+6x2+6x4+x6)
(1-x2)9
,..., Hm(x2)=
x2Sm(x2)
(1-x2)2m-1
.
Sm(x2) is a symmetric unimodal polynomial of degree (m-2). Hm(x2) satisfies the inversion relation
Hm(x2)+x-2(m-1)Hm(1/x2)=0
and it follows that the generating function P(x,y) verifies
P(x,y)=
x2y2
1-x2
+G(x,y)  where   G(x,y)=-x2G(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 x2=1.

Convex polygons

Hn(x2) is the generating function for convex polygons with 2n vertical bonds.


H1(x2)=
x2
1-x2
,   H2(x2)=
x2(1+x2)2
(1-x2)3
,
H3(x2)=
x2(1+8x2+13x4+2x6)
(1-x2)5
,
Hn(x2)=
x2Tn(x2)
(1-x2)2n-1
.

Tn 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)=
 
n
x2nHn(y2)=
 
m
y2mA(x2).

Hn(y2)=Tn(y2)/(1-y2)2n-1 where Tn(y2) is a symmetric, unimodal polynomial of degree 2n-1 in y2 and Hn(y2)=-Hn(1/y2) so P(x,y)+P(x,1/y)=0.

Am(x2)=Um(x2)/(1-x2)2m-1 where Um(x2) is an asymmetric (m>2), unimodal polynomial of degree 2n-1 in x2. Absence of symmetry precludes solution by this method.

3 choice polygons

The number of 3 choice polygons of 2n steps grows like
22n-5
(np)1/2
(15.13161+
3(3)1/2
p
ln n).
If Hn(y2) 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)=
 
n
x2nHn(y2).
H2(y2)=
1
(1-y2)3
,
H3(y2)=
3+2y2
(1-y2)5
,
H4(y2)=
6+19y2+15y4+4y6)
(1-y2)7(1+y2)
,

H5(y2)=
10+75y2+194y4+237y6+161y8+66y10-5y12-12y14+16y16 -6y20+2y22
(1-y2)9(1+y2)3
.
The denominator in general is
Hn=(1-y2)2n-1(1+y2)2n-7=(1-y2)6(1-y4)2n-7    for n>3.
This is consistent with solvability and the solution is probably D-finite.

Square lattice polygons (I. Enting)

We have no inversion relation for this model but P(x,y)=P(y,x). We define Rn(x2) by the relation
P(x,y)=
n=1
Rn(x2)y2n.
Numerators of the Rn(x2) are unimodal, positive, but not symmetric. The degree of the numerator is equal to that of the denominator. The denominator is (1-x2)2n-1 for n 4, but for n>4 powers of 1-x4 enter, and for n>6 we see powers of 1-x6 entering, while n=8 marks the first occurrence of powers of 1-x8 [3].

Self avoiding walks on square lattice (A. Conway)

We have no inversion relation for this model. We define Hn(x) by the relation
C(x,y)=
n=0
Hn(x)yn.
Hn(x) (now known up to n=12) is equal to Anm/Bnm where Anm and Bnm are polynomials of degree m, Anm is unimodal and Bnm is equal to
Bnm(x)=(1-x)
a
 
(1+x)
b
 
(1+x+x2)
g
 
(1+x2)
d
 
.
Up to n=9, we have a=n+1, b=2( n/2) with n>1, g =n-4 with n>4 and d=1,1,3 for 9 n>6 [2].

Honeycomb polygons (brickwork)

Hn(x2)=Pn(x2)/Qn(x2). The denominator pattern is quite regular. The denominators always have zeros only on the unit circle [3], just at x2=1 for n 3, with powers of 1-x4 appearing at n=4, powers of 1-x6 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 1anzn where an is the number of animals with n sites and one source. For square and triangular lattice Dhar showed 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 0Hn(x)yn gives Hn(x)=Nn(x)/Dn(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 self-avoiding walks and corrections to scaling. Physical Review Letters, vol. 77, n°26, 1996, pp. 5284--5287.

[3]
Guttmann (A. J.) and Enting (I. G.). -- Inversion relations, the Ising model and self-avoiding polygons. Nuclear Physics (Proc. Suppl.), vol. 47, 1996, pp. 735--738.

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

[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. 69--80.

[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. 641--651.

[7]
Onsager (L.). -- Crystal statistics. I. A two dimensional model with an order-disorder 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. 116--118.

[9]
Wu (T. T.), McCoy (B. M.), Tracy (C. A.), and Barouch (E.). -- Spin-spin correlation functions for the two-dimensional Ising model: Exact theory in the scaling region. Physical Review B, vol. 13, 1976, pp. 316--374.

This document was translated from LATEX by HEVEA.