[seqfan] Re: Coordination sequences (was "more")

[Joseph Myers]

(The following is long, skip if you want.)

In outline, here is my argument that the coordination sequences for any 
directed graph, periodic in d Euclidean dimensions (d linearly independent 
translations), with finitely many vertex classes up to those translations 
and finite vertex degrees, but not necessarily connected / strongly 
connected, must always be eventually polynomial on residue classes (and so 
have a generating function of the desired rational form).  Say the 
vertices are of the form (C, v), where C is one of the finitely many 
classes and v is a vector in Z^d.

The coordination sequence for any starting class of vertex A is just the 
sum of such sequences where we fix the ending class B as well, so in what 
follows suppose both A and B are fixed and we want to find the number of v 
for which the shortest path from (A, 0) to (B, v) has length n, as a 
function of n.  We do this by describing that length as a (possibly 
partial) function f of v with a special form, and then showing that for 
any function of that form, the number of v for which f(v) = n is 
eventually polynomial on residue classes as a function of n.

Say than an integer modulo polyhedral set (IMP-set for short) in Z^d is a 
set given by finitely many linear equations in the coordinates with 
integer coefficients, linear inequalities in the coordinates with integer 
coefficients, and linear congruences in the coordinates with integer 
coefficients (saying that the sum of certain integer multiples of the 
coordinates equals some integer, modulo some integer modulus).  Say an 
IMPU-set is the union of finitely many disjoint IMP-sets.  Then it's easy 
to see that complements, finite unions, finite intersections and set 
differences of IMPU-sets are IMPU-sets.

Now say that an IMP-linear function (IMPL-function for short) is a partial 
function on a Z^n, given by dividing Z^n into finitely many disjoint 
IMP-sets, and, on some of those sets, giving the function as a linear 
function in the coordinates with rational coefficients, such that all the 
values on points of that IMP-set are nonnegative integers (and on any of 
the IMP-sets where such a definition is not given, the function is 
undefined).  Given the properties above about intersections of IMPU-sets, 
it's easy to see that the minimum of two IMPL-functions is an 
IMPL-function (where min(x, undefined) = x), and that the sum of two 
IMPL-functions is an IMPL-function (where x + undefined = undefined).

We will show that the function f(v) above, giving the length of the 
shortest path from (A, 0) to (B, v), is an IMPL-function.  First, we 
divide into cases according to which subset of the vertex classes appear 
in the path from (A, 0) to (B, v) (including the endpoints).  For each 
subset, there is a (possibly partial) function giving the length of the 
shortest path with the constraint that the path goes through exactly those 
classes; the minimum of those functions is the original f.  We will show 
that each of those constrained functions is an IMPL-function, from which 
it follows that f is an IMPL-function.

Say there are c vertex classes that we are requiring to be in the path.  
Consider a shortest path from (A, 0) to (B, v) and repeatedly apply the 
following operation: take two vertices in the same class C, such that no 
vertex between them has class C, no two vertices between them have the 
same class and no class D has only one vertex of that class in the path, 
that vertex being between the two vertices of class C, and contract the 
path between those two vertices of class C (this modifies the final vector 
v for the path, while preserving the set of vertex classes).  It's easy to 
see that this process must end with a path of at most c^2 vertices, so 
there are at most finitely many paths it can end with.  Split 
consideration into separate cases for which such path you end with (again, 
using that the minimum of IMPL-functions is an IMPL-function).  Given an 
ending path, the original path can be reconstructed by repeatedly 
replacing vertices with paths from a vertex class to itself (replacing a 
vertex in class C, say, with a path from C to C that only goes through the 
allowed classes and doesn't go through C on the way or go through any 
other class twice).  There are finitely many possible such replacements 
(at most c edges in any such replacement).  Furthermore, such replacements 
can occur in any order.

So now we are looking at a function f(v) that is the minimum n = a_0 + 
n_1a_1 + n_2a_2 + n_3a_3 + ... + n_ka_k for which v_0 + n_1v_1 + n_2v_2 + 
... + n_kv_k = v, where n_i are nonnegative integers, v_0 is the vector of 
the path the contraction process ended with, v_i is the vector of the ith 
possible path from a vertex class to the same class and a_i is the length 
of the path with vector v_i.

This function is constructed iteratively.  Say f_i is the function where 
only the vectors up to v_i are allowed; f_0 is a_0 at v_0 and undefined 
everywhere else.  Then f_i(v) = min(n_ia_i + f_{i-1}(v - n_iv_i)), where 
n_i ranges over the nonnegative integers.  We wish to show that this is an 
IMPL-function.

For each IMP-set in the definition of f_{i-1}, say f_{i-1} = g (a linear 
function with rational coefficients) on that set.  Then n_ia_i + g(v - 
n_iv_i) is linear (in the coordinates of v together with n_i).  Consider 
all the linear equations and inequalities and modular arithmetic 
constraints for v - n_iv_i to be in the required set.  After splitting 
into cases for the values of the coordinates and n to appropriate moduli, 
we have various equations and inequalities for n in terms of the 
coordinates.  If n is given by an equation, the required minimum on that 
IMP-set is simply a linear function in the coordinates and we have some 
linear conditions for whether such n exists at all.  Otherwise, there are 
finitely many cases for the ordering of the linear expressions n is 
compared against, each of which (possibly after more splitting into cases 
to appropriate moduli) gives an IMP-set in which either there is no such 
n, or the largest and smallest such n are linear functions of the 
coordinates.  Thus min(n_ia_i + g(v - n_iv_i)), over all n for which v - 
n_iv_i is in the original IMP-set, is an IMPL-function.  f_i is now the 
minimum of that over all relevant IMP-sets.


So the original f(v) is an IMPL-function.  We wish to count the number of 
v for which f(v) = n, as a function of n; call this g(n).  Consider each 
IMP-set in the expression of f as an IMPL-function separately.  If this 
set is finite, g(n) is eventually zero.  Otherwise, changing variables as 
needed and splitting into cases to appropriate moduli, we have a possibly 
smaller number of coordinates (say e of them) such that the IMP-set is 
given only by inequalities and not equations in those coordinates and each 
of those coordinates is unbounded.  Furthermore, we may set the 
coordinates so that n is one of the coordinates.  Now, using induction on 
the dimension, we may adjust the IMP-set so that none of the inequalities 
has any constant term: the difference in each direction between the 
original IMP-set and the adjusted one is an IMPU-set, all of whose IMP-set 
components have infinite extent in at most e-1 dimensions and for which 
the number of v for which f(v) = n may thus be determined inductively.  
Given the adjusted set, say P(k) is the polytope (in the e-1 dimensions 
other than n - this time interpreted as R^{e-1}, not Z^{e-1}) of vectors 
with n = k, and because of the adjustment, P(k) = kP(1).  Now (possibly 
with further splitting into modulo cases) change variables again so that 
the origin is in P(k), and so P(k) is a subset of P(k+1).  Now the 
difference is an IMPU-set all of whose IMP-set components have infinite 
extent in at most e-1 dimensions, so the induction applies.  (The base 
case was e = 0, a finite set.)


It's quite plausible some or all of this appears in the literature (or 
indeed that better versions appear in the literature - this is more or 
less what I came up with off the top of my head, when first thinking about 
coordination sequences for OEIS a few years ago).  For example, Benson 
(Invent. math. 73, 251-269 (1983)) deals with the case of a group in which 
Z^n has finite index, using some similar ideas about polyhedral sets.


The algorithm implied by the above involves exponential blow-up in several 
places.  In practice, it would be better to look for patterns in f(v) 
allowing it to be described as an IMPL-function - and then once you have a 
conjectural pattern, it's a straightforward finite check to establish that 
it holds for long enough that it must continue indefinitely.  Given such a 
pattern, determining the coordination sequence should in practice be 
straightforward - even if the algorithm above for the last stage blows up, 
if you've shown that from N onwards, the sequence must be a sum of 
sequences of polynomials of degree at most d-1, one periodic with period 
P, one with period Q, one with period R (those periods falling out from 
the patterns found), you only need about N+d(P+Q+R) terms to solve the 
linear equations for the coefficients of the polynomials / g.f., not 
N+d*lcm(P,Q,R) that would be needed to spot a period naively.  It's 
possible that even for zeolites where the overall period length is large 
(140900760 in one case), a rigorous g.f. could be determined that way.

-- 
Joseph S. Myers
jsm at polyomino.org.uk