[seqfan] Re: Coordination sequences (was "more")
Joseph Myers
jsm at polyomino.org.uk
Sat Dec 19 03:19:49 CET 2015
(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
More information about the SeqFan
mailing list