# Determinantal Conditions for Modules of Generalized Splines

Kariane Calta  Department of Mathematics, Vassar College, Poughkeepsie, NY,
12604  and  Lauren L. Rose  Department of Mathematics, Bard College,
Annandale-on-Hudson, NY, 12504<EMAIL_ADDRESS>
###### Abstract.

Generalized splines on a graph $G$ with edge labels in a commutative ring $R$
are vertex labelings such that if two vertices share an edge in $G$, the
difference between the vertex labels lies in the ideal generated by the edge
label. When $R$ is an integral domain, the set of all such splines is a
finitely generated $R$-module $R_{G}$ of rank $n$, the number of vertices of
$G$. We find determinantal conditions on subsets of $R_{G}$ that determine
whether $R_{G}$ is a free module, and if so, whether a so called ”flow-up
class basis” exists.

###### Key words and phrases:

generalized splines, commutative algebra, number theory, module theory, graph
theory

##  1\. Introduction

Rings, modules and vector spaces of polynomial splines have been well studied
in terms of their algebraic properties, for example in [5], [7], [15], [19],
[20]. The notion of a polynomial spline can be generalized to define splines
on edge labeled graphs over arbitrary rings. The study of generalized splines
over rings was introduced by Gilbert, Polster, and Tymoczko in [13].
Generalized integer splines were introduced in [16], where they constructed
module bases for integer splines on cycles.

If $R$ is a ring and $G$ is a graph with $n$ vertices, then the set of
generalized splines $R_{G}$ is a submodule of $R^{n}$. When $R_{G}$ is a free
$R$-module, the bases of particular interest are the flow-up class bases.
Elements of a flow-up class basis are $n$-tuples with $k$ leading zeros, where
$0\leq k\leq n-1$. As a result, if we order the basis elements according to
the number of leading zeroes, they form the columns of a lower triangular
matrix, whose determinant is easy to compute.

In this paper we address two questions about modules of generalized splines:

  1. (1)

For which rings do flow-up class bases for arbitrary graphs always exist?

  2. (2)

If a flow-up class basis doesn’t exist but the module $R_{G}$ is free, do we
have any information about bases?

As an answer to Question 1, we generalize results from [17] and show that
flow-up class bases for spline modules necessarily exist over principal ideal
domains. In particular, this includes Euclidean rings such as the integers and
polynomial rings in one variable over a field as well as non-Euclidean rings
such as $\mathbb{Z}[1/2(1+\sqrt{-19})]$. ([12]) We also find that for a fixed
ordering of the vertices of the graph $G$, the leading term of a basis element
is unique up to multiplication by a unit. We then give an example to show that
when $R$ is not a principal ideal domain, flow-up class bases don’t
necessarily exist, so our result is essentially the best possible.

In answer to Question 2, we first generalize results of [14], [18], [9],[2],
and [3] to show that over a principal ideal domain, a set of $n$ elements
$\mathcal{B}=\left\\{B_{1},\ldots,B_{n}\right\\}$ is a basis for $R_{G}$ if
and only the determinant of the matrix $[B_{1},\ldots,B_{n}]$ has a prescribed
form. We further show that over GCD domains (where flow-up class bases need
not exist), any set of elements with the same prescribed form will be a basis.
We prove the converse under certain conditions, but we conjecture that our
result is true in all cases.

In [21], Rose proved the following theorem for modules $M_{r}$ of
$r$-differentiable polynomial splines defined on $D$, a polyhedral subdivision
of $\mathbb{R}^{d}$:

######  Theorem 1.1.

Let $B=\left\\{B_{,}\dots,B_{n}\right\\}\subset M_{r}$. Then $B$ is a basis of
$M_{r}$ if and only if $\det[B_{1},\ldots B_{n}]=Q^{r+1}$, where $Q$ is the
product of the linear forms that define the co-dimension $1$ interior faces of
$D$.

In this setting, the linear forms are either relatively prime or equal, and
correspond to edge labels in the dual graph of $D$. In the case of generalized
polynomial splines, the situation is more complicated if you allow arbitrary
polynomials as edge labels. However, with a few restrictions on the edge
labels, we prove an analogous and more general result for arbitrary graphs
over a GCD domain:

######  Theorem 1.2.

Let $R$ be a GCD domain and let $G$ be a graph with edge labels
$a_{1},\ldots,a_{m}\in R$ that are pairwise relatively prime. Then $R_{G}$ is
free with bases $\mathcal{B}=\left\\{B_{1},\ldots,B_{n}\right\\}$ if and only
if $\det(B)=uQ$ for some unit $u\in R$.

##  2\. Preliminaries

We begin by defining a generalized spline over a commutative ring with unity.
Some of our results will require stronger assumptions about $R$, e.g. that $R$
is an integral domain, principal ideal domain, or a GCD domain.

Let $R$ be a commutative ring with unity and let $G$ be a connected graph with
$n$ vertices, edge set $E=\left\\{e_{1},\ldots,e_{m}\right\\}$, and
$A=\left\\{a_{1},\ldots,a_{m}\right\\}$ an assignment of edge labels in $R$.

######  Definition 2.1.

A generalized spline on $G$ over the ring $R$ is an assignment of an $n$-tuple
$F=(f_{1},\ldots f_{n})\in R^{n}$ to the vertices of $G$ such that for any two
vertices $v_{i}$ and $v_{j}$ that are connected by an edge $e_{k}$, we have
$f_{i}\equiv f_{j}\bmod{a_{k}}$. That is, $f_{i}-f_{j}\in<a_{k}>$, the ideal
in $R$ generated by $a_{k}$.

We denote the set of all $R$-splines on $(G,A)$, the graph $G$ with edge
weights $A$, by $R_{(G,A)}$ or just $R_{G}$ when $A$ is fixed. The following
basic properties are easily verified.

######  Remark 2.2.

  1. (1)

For any $G$, $R_{G}$ always contains $\mathbf{0}=(0,0,\ldots,0)$ and
$\mathbf{1}=(1,1,\ldots,1)$, since for all $a\in R$, $0\equiv 0\bmod a$ and
$1\equiv 1\bmod a$.

  2. (2)

The splines $R_{G}$ form a module over $\mathbb{Z}$ under componentwise
addition and scalar multiplication.

  3. (3)

When $R$ a principal ideal domain, $R_{G}$ is a free module, and hence has a
module basis. For other rings, freeness is not guaranteed.

When $R_{G}$ is free, the bases that are of particular interest to us are the
flow-up class bases, primarily because when placed as rows or columns of a
matrix, the matrix will be triangular, making it easy to compute the
determinant. In fact, the initial non-zero components of such basis elements
are unique up to multiplication by a unit, and are important to understanding
the structure of $R_{G}$.

######  Definition 2.3.

  1. (1)

For $0\leq i<n$, let
$\mathcal{F}_{i}=\left\\{F=(0,0,\ldots,f_{i+1},\ldots,f_{n}):F\in
R_{G}\right\\}$.

  2. (2)

We define $\mathcal{F}_{n}=\left\\{\mathbf{0}\right\\}$, the set containing
just the zero spline $\mathbf{0}=(0,0,\ldots,0)$.

  3. (3)

We refer to $\mathcal{F}_{i}$ as the $i$th flow-up class.

  4. (4)

A flow-up class basis for $R_{G}$ is a module basis consisting of an element
from each non-zero flow-up class.

######  Remark 2.4.

  1. (1)

By definition, the $\mathcal{F}_{i}$ form a partition of $R_{G}$.

  2. (2)

Our definition of $\mathcal{F}_{i}$ is stricter than that used by [13], which
only requires that the first $i$ components be zero. In their case, the sets
$\mathcal{F}_{i}$ are nested, rather than forming a partition.

######  Example 2.5.

Consider the graph $(C_{3},A)$ depicted in Figure 1, where
$A=(a_{1},a_{2},a_{3})$. A set of vertex labels $(f_{1},f_{2},f_{3})$ will
form a spline if and only if the following conditions hold:

$\displaystyle a_{1}|f_{1}-f_{2}$ $\displaystyle a_{2}|f_{2}-f_{3}$
$\displaystyle a_{3}|f_{3}-f_{1}$

$f_{1}$$f_{2}$$f_{3}$$a_{1}$$a_{2}$$a_{3}$

Figure 1. Generalized spline on a 3-cycle with edge weights
$a_{1},a_{2},a_{3}$

Next, we give a specific example of an integer spline.

######  Example 2.6.

In Figure 2 , the edge labels of $C_{3}$ are $a_{1}=4$, $a_{2}=5$ and
$a_{3}=1$. It is easy to verify that the vertex labeling $(3,15,5)$ is an
integer spline on $C_{3}.$

$3$$15$$5$$4$$5$$2$

Figure 2. Example of a Spline on a 3-cycle

##  3\. Flow-up Class Bases

We begin by showing that if $R$ is an integral domain and $G$ is an arbitrary
graph, the flow-up classes in $R_{G}$ are non-empty.

######  Lemma 1.

Let $R$ be an integral domain and let $(G,A)$ be an edge labeled graph with
$n$ vertices. Then $\mathcal{F}_{i}\subset R_{G}$ is non-empty for all $0\leq
i\leq n$.

###### Proof.

First note that $\mathbf{0}=(0,\ldots,0)\in\mathcal{F}_{n}$ and
$\mathbf{1}=(1,\ldots,1)\in\mathcal{F}_{0}$, so they are non-empty. For
$0<i<n$, let $F=(f_{1},\ldots,f_{n})\in\mathbb{R}^{n}$ be defined as follows.
Let $f_{j}=0$ if $j\neq i+1$ and let $f_{i+1}$ be the product of the edge
labels incident to vertex $v_{i+1}$. Consequently $F$ has the form
$F=(0,\dots,0,f_{i+1},0\ldots,0)$, with $f_{i+1}=a_{{i}_{1}}a_{{i}_{2}}\cdots
a_{{i}_{k}}$ where $e_{{i}_{1}},e_{{i}_{2}},\ldots,e_{{i}_{k}}$ are the edges
incident to vertex $v_{i+1}$.

Next, we show that $F$ is a spline. If edge $e_{p}$ is is not incident to
vertex $i+1$ then the defining equation for that edge will be $0\equiv 0\bmod
a_{p}$, which is always true. For edges $e_{{i}_{r}}$ incident to vertex
$v_{i+1}$, the defining equation will be $f_{i+1}\equiv 0\bmod a_{{i}_{r}}$.
Since $f_{i+1}=a_{{i}_{1}}a_{{i}_{2}}\cdots a_{{i}_{k}}$, we have that
$a_{{i}_{r}}|f_{i+1}$ for each $1\leq r\leq k$, so the equation holds. Since
$F$ satisfies the spline equations for each edge, $F\in R_{G}$ and since $F$
has exactly $i$ leading zeros, we have that $F\in\mathcal{F}_{i}$. Hence for
each $0\leq i\leq n$, $\mathcal{F}_{i}$ is non-empty. ∎

We define the leading term of a non-zero spline $F$ to be the first non-zero
entry of $F$.

######  Definition 3.1.

Let $F\in\mathcal{F}_{i}$, where $1\leq i<n$, so
$F=(0,0,\ldots,f_{i+1},\ldots,f_{n})$. We define the leading term of $F$,
$LT(F)=f_{i+1}$, the first non-zero entry of $F$.

Let $L(\mathcal{F}_{i})=\left\\{LT(F):F\in\mathcal{F}_{i}\right\\}$.

######  Lemma 2.

The set of all leading terms of splines in $\mathcal{F}_{i}$,
$L(\mathcal{F}_{i})$, is an ideal of $R$.

###### Proof.

Let $F$ and $H$ be splines in $\mathcal{F}_{i}$. Then $LT(F)+LT(H)$ is either
the leading term of an element of $\mathcal{F}_{i}$ or it’s zero, hence it is
in $L(\mathcal{F}_{i})$. If $r\in R$, and $r\neq 0$, then $rLT(F)=LT(rF)\in
L(\mathcal{F}_{i})$. Thus $L(\mathcal{F}_{i})$ is an ideal of $R$. ∎

When $R$ is a PID, we can define the notion of a minimal element of a flow-up
class.

######  Definition 3.2.

Let $R$ be a PID. A spline $B\in\mathcal{F}_{i}$ is called a minimal element
of $\mathcal{F}_{i}$ if $LT(B)$ is a generator of the ideal
$L(\mathcal{F}_{i})$.

Note that minimal elements are not in general unique, but their leading terms
are unique up to multiplication by a unit.

We now show that when we take a minimal element from each flow-up class
$\mathcal{F}_{i}$, where $0\leq i<n$, we will always get a flow-up class basis
for $R_{G}$. First, we need a lemma.

######  Lemma 3.

Let $F\in\mathcal{F}_{i}$, and let $B$ be a minimal element of
$\mathcal{F}_{i}$. There exists $r\in R$ such that $F-rB\in\mathcal{F}_{k}$
for some $k>i$.

###### Proof.

Since $LT(F)\in<LT(B)>$, there exists some $r\in R$ such that $LT(F)=rLT(B)$.
Let $J=F-rB$. Then the $i+1$st component of $J$ will be $0$, so $J$ has at
least $i+1$ leading zeros. Thus $J\in\mathcal{F}_{k}$ for some $k>i$. ∎

######  Theorem 3.3.

Let $R$ be a PID and $(G,A)$ be an edge-labeled graph with $n$ vertices. Then
$R_{G}$ is a free $R$-module, and it has a flow-up class basis. Moreover, if
$\mathcal{B}=\\{B_{1},\dots,B_{n}\\}\subset R_{G}$ where each
$B_{i}\in\mathcal{F}_{i}$ is minimal, then $\mathcal{B}$ is a flow-up class
basis.

###### Proof.

By the structure theorem for modules over a PID, $R_{G}$ is free for all $G$.
Let $B_{i}\in\mathcal{F}_{i}$ be such that $LT(B_{i})$ generates
$<L(\mathcal{F}_{i})>$. Note that the matrix
$\begin{bmatrix}B_{1}&\cdots&B_{n}\end{bmatrix}$ is a lower triangular matrix
where the diagonal entries are the leading terms of the $B_{i}$’s. Since the
leading terms are each non-zero, the determinant will be non-zero. It follows
that $\mathcal{B}$ is linearly independent over $R$. We will show by induction
that for every $H\in R_{G}$, $H\in span(\mathcal{B}_{i})$. Note that the only
element of $\mathcal{F}_{n}$, the zero spline, is trivially in the span.

Suppose $k>0$ and that whenever $0\leq j<k$, $\mathcal{F}_{n-j}\subset
span(\mathcal{B})$. Let $H\in\mathcal{F}_{n-k}$. By Lemma 3, there exists some
$q\in R$ and $i$ such that $n-k<n-i\leq n$ so that
$F=H-qB_{n-k}\in\mathcal{F}_{n-i}$. Thus $H=F+qB_{i}$ and $0\leq i<k$. By the
induction hypothesis, $F\in span(\mathcal{B})$, so $H\in span(\mathcal{B})$.
By induction we have shown that any for any $S\in R_{G}$, $S\in
span(\mathcal{B})$. Since $\mathcal{B}$ is a linearly independent set that
spans $R_{G}$, it is a basis. ∎

Note that the only property of splines that we used in this theorem is that
$R_{G}$ is a submodule of $R^{n}$ with non-empty flow-up classes. Thus, this
theorem can be stated more generally. If some of the flow-up classes are
empty, the result will still hold, i.e., submodules of spline modules will
also have flow-up class bases. In fact, when $R$ is a Euclidean domain we can
construct the leading terms explicitly in terms of the edge labels. See [22]
for details.

##  4\. Determinants

When $R$ is an integral domain and $M$ is a finitely generated submodule of
$R^{n}$, we have a nice criterion for when an arbitrary set of $n$ elements
will form a basis.

Throughout this section, we will need to refer to the determinant of a matrix
whose columns are elements of a subset of $M$. To simplify notation, we make
the following definition:

######  Definition 4.1.

Let $C=\left\\{C_{1},\ldots C_{n}\right\\}$ be an ordered subset of $M$. We
define $\det(C)=det\begin{bmatrix}C_{1},\ldots,C_{n}\end{bmatrix}$.

######  Theorem 4.2.

Let $R$ be an integral domain, $M$ a finitely generated rank $n$ submodule of
$R^{n}$, and suppose that $M$ is free with basis
$\mathcal{B}=\left\\{B_{1},.,.B_{n}\right\\}$. Then
$\mathcal{C}=\left\\{C_{1},\ldots,C_{n}\right\\}\subset M$ is another basis
for $M$ if and only if $\det(\mathcal{C})=u\det(\mathcal{B})$, where u is a
unit in $R$.

###### Proof.

First assume that $\mathcal{C}=\left\\{C_{1},\cdots,C_{n}\right\\}$ is a basis
for $R^{n}$. Since $\mathcal{B}$ is also a basis for $R^{n}$, for each
$C_{i}\in\mathcal{C}$, there exist $a_{ij}\in R$ with $1\leq i,j\leq n$ so
that $C_{i}=\sum_{j=1}^{n}a_{ij}B_{j}$. If we define
$A=\begin{bmatrix}a_{ij}\end{bmatrix}$, the matrix with $ij$th entry equal to
$a_{i}j$, $C=\begin{bmatrix}C_{1},\ldots,C_{n}\end{bmatrix}$ and
$B=\begin{bmatrix}B_{1},\ldots,B_{n}\end{bmatrix}$ then $C=AB$. Similarly,
since $\mathcal{C}$ is a basis for $R^{n}$, there exists a matrix $A^{\prime}$
so that $B=A^{\prime}C$. Then $C=AB=AA^{\prime}C$. Since $\mathcal{C}$ is a
basis, $\det(\mathcal{C})\neq 0$, hence $\det(A)\det(A^{\prime})=1$. This
implies that $\det(A)$ is a unit in $R$ and since $\det(C)=\det(A)\det(B)$,
the result follows.

Now assume that $\det(C)=u\det(B)$ for some unit $u\in R$. Since $\mathcal{B}$
is a basis for $R^{n}$, there exists some matrix $A$ so that $C=AB$. Then
$\det(C)=\det(A)\det(B)$, and since $\det(C)=u\det(B)$, we have that
$u\det(B)=\det(C)=\det(A)\det(B)$. Since $\mathcal{B}$ is a bais, $\det(B)\neq
0$, and it follows that $\det(A)$ is a unit. Thus there exists some matrix
$A^{\prime}$ so that $A^{\prime}A=I$ and so $A^{\prime}C=A^{\prime}AB=B$ so
$A^{\prime}C=B$. Since $\mathcal{B}$ is a basis, so is $\mathcal{C}$. ∎

We can now interpret this theorem in terms of spline modules.

######  Corollary 4.3.

Let $R$ be a PID and let $(G,A)$ be an arbitrary edg-labeled graph with $n$
vertices. Furthermore, suppose that
$\mathcal{B}=\left\\{B_{1},.,.B_{n}\right\\}$ is a flow-up class basis for
$R_{G}$. For each $i$, let $l_{i}$ be the leading term of $B_{i}$ and define
$Q=l_{1}\cdots l_{n}$. Then $\mathcal{C}=\left\\{C_{1},.,.C_{n}\right\\}$ is a
basis for $R_{G}$ if and only if $\det(\mathcal{C})=uQ$ for some unit $u\in
R$.

###### Proof.

First note that a flow-up class basis for $R_{G}$ is guaranteed to exist by
Theorem 3.3. If $\mathcal{B}$ is a flow-up class basis with leading terms
$l_{i}$, then $\det(\mathcal{B})=l_{1}\cdots l_{n}=Q$. Let
$\mathcal{C}=\left\\{C_{1},\ldots,C_{n}\right\\}$. By Theorem 4.2,
$\mathcal{C}$ is a basis if and only $\det(\mathcal{C})=u\det(\mathcal{B})=uQ$
for some unit $u\in R$.

∎

We would like similar criteria to determine whether a set of elements form a
basis of $R_{G}$, even when no flow-up class basis exists. For example, we
will prove later that if $R$ is not a PID, flow-up class bases need not exist,
even if $R_{G}$ is free.

For splines over integral domains, we provide a theoretical framework for such
criteria, and for GCD domains over graphs with relatively prime edge labels,
we provide an explicit construction of what $Q$ needs to be in this case.

######  Lemma 4.

Let $R$ be an integral domain. Suppose
$\det\begin{bmatrix}B_{1},\ldots,B_{n}\end{bmatrix}=Q$, where
$B_{1},\ldots,B_{n}\in R_{G}$. Then $QR^{n}\subset
span\left\\{B_{1},\ldots,B_{n}\right\\}$.

###### Proof.

Let $B=[B_{1},\ldots,B_{n}]$. If $B_{1},\cdots B_{n}$ are not linearly
independent, then $Q=det(B)=0$ and so $QR^{n}=\textbf{0}\in
span\left\\{B_{1},\ldots,B_{n}\right\\}$. Now suppose that the $B_{i}$ are
linearly independent and let $D\in R_{G}$. We will show that there exists some
$x_{1},\ldots,x_{n}\in R$ such that:

$\begin{pmatrix}b_{11}&b_{12}&\cdots&b_{1n}\\\ b_{21}&b_{22}&\cdots&b_{2n}\\\
\vdots&\vdots&\ddots&\vdots\\\
b_{n1}&b_{n2}&\cdots&b_{nn}\end{pmatrix}\begin{pmatrix}x_{1}\\\ x_{2}\\\
\vdots\\\ x_{n}\end{pmatrix}=\begin{pmatrix}Qd_{1}\\\ Qd_{2}\\\ \vdots\\\
Qd_{n}\end{pmatrix}$

Using Cramer’s rule, we have that for each $1\leq i\leq n$,

$\displaystyle x_{i}$
$\displaystyle=\frac{\begin{vmatrix}b_{11}&\cdots&Qd_{1}&\cdots&b_{1n}\\\
b_{21}&\cdots&Qd_{2}&\cdots&b_{2n}\\\ \vdots&\cdots&\vdots&\ddots&\vdots\\\
b_{n1}&\cdots&Qd_{n}&\cdots&b_{nn}\end{vmatrix}}{|B|}=\frac{Q\begin{vmatrix}b_{11}&\cdots&d_{1}&\cdots&b_{1n}\\\
b_{21}&\cdots&d_{2}&\cdots&b_{2n}\\\ \vdots&\cdots&\vdots&\ddots&\vdots\\\
b_{n1}&\cdots&d_{n}&\cdots&b_{nn}\end{vmatrix}}{Q}$
$\displaystyle=\begin{vmatrix}b_{11}&\cdots&d_{1}&\cdots&b_{1n}\\\
b_{21}&\cdots&d_{2}&\cdots&b_{2n}\\\ \vdots&\cdots&\vdots&\ddots&\vdots\\\
b_{n1}&\cdots&d_{n}&\cdots&b_{nn}\end{vmatrix}$

Since each of the entries in this last matrix is in $R$, $x_{i}\in R$. Hence
$QD\in span\left\\{B_{1},\cdots,B_{n}\right\\}$. Since $D$ was arbitrary,
$QR^{n}\subset span\left\\{B_{1},\cdots,B_{n}\right\\}$.

∎

If we can find an element $Q$ that divides the determinants of all $n$-element
subsets of $R_{G}$, this will give us a determinantal criterion in one
direction.

######  Theorem 4.4.

Let $R$ be an integral domain. Suppose there exists some $Q\in R$ so that
$Q|\det\begin{bmatrix}C_{1},\ldots C_{n}\end{bmatrix}$ for any
$\left\\{C_{1},\ldots C_{n}\right\\}\subset R_{G}$. Then if
$B=\left\\{B_{1},\ldots B_{n}\right\\}$ is any subset of $R_{G}$ for which
$\det(B)=Q$, then $B$ is a basis for $R_{G}$.

###### Proof.

Suppose that $\det\begin{bmatrix}B_{1},\ldots,B_{n}\end{bmatrix}=Q$. Note that
$Q\neq 0$, so $\left\\{B_{1},\ldots,B_{n}\right\\}$ must be linearly
indpendent over $R$. By Lemma 4, $QR^{n}\subset
span\left\\{B_{1},\ldots,B_{n}\right\\}$. Let $F\in R_{G}$. Then $QF\in
span\left\\{B_{1},\ldots,B_{n}\right\\}$ so $QF=\sum_{i=1}^{n}s_{i}B_{i}$
where each $s_{i}\in R$. Then

$\displaystyle s_{i}Q=$ $\displaystyle s_{i}\det[B_{1},\ldots,B_{n}]$
$\displaystyle=$
$\displaystyle\det[B_{1},\ldots,B_{i-1},s_{i}B_{i},B_{i+1},\ldots,B_{n}]$
$\displaystyle=$ $\displaystyle\det[B_{1},\ldots,B_{i-1},\sum
s_{j}B_{j},B_{i+1},\ldots,B_{n}]$ $\displaystyle=$
$\displaystyle\det[B_{1},\ldots,B_{i-1},QF,B_{i+1},\ldots,B_{n}]$
$\displaystyle=$ $\displaystyle
Q\det[B_{1},\ldots,B_{i-1},F,B_{i+1},\ldots,B_{n}]$

Since by hypothesis $Q$ divides the determinant of any set of $n$ elements in
$R_{G}$,

$Q\det[B_{1},\ldots,B_{i-1},F,B_{i+1},\ldots,B_{n}]=Q^{2}r$, for some $r\in
R$. Then $s_{i}Q=Q^{2}r$ implies $s_{i}=Qr$, so $Q$ divides $s_{i}$, and this
is true for each $i$.

Thus $F=\sum(s_{i}/Q)B_{i}\in span\left\\{B_{1},\ldots,B_{n}\right\\}$. So
$\mathcal{B}$ spans $R_{G}$, and hence is a basis. ∎

When $R$ is a GCD domain over an arbitrary graph $G$, we can always find a
non-unit $Q$ satifying the hypotheses of Theorem 4.4. Before we prove this
lemma, it is worth noting that the definitions of a $\gcd$ and an
$\mathrm{lcm}$ of two elements in a GCD domain are slightly different from the
usual defintions in $\mathbb{Z}$, in that $\gcd$’s and $\mathrm{lcm}$’s are
not unique, and the notion of a smallest or largest element doesn’t have an
analog in an arbitrary GCD domain.

######  Definition 4.5.

Let R be a GCD domain. Then $d$ is a $gcd$ of $a$ and $b$ if and only if the
following two conditions hold:

  1. (1)

$d|a$ and $d|b$

  2. (2)

if $c|a$ and $c|b$, then $c|d$.

######  Definition 4.6.

Let R be a GCD domain. Then $l$ is an $lcm$ of $a$ and $b$ if and only if the
following two conditions hold:

  1. (1)

$a|l$ and $b|l$

  2. (2)

if $a|c$ and $b|c$, then $l|c$.

It follows from this definition that in a GCD domain $R$, if $d_{1}$ and
$d_{2}$ are gcds of $a$ and $b$, then there exists a unit $u$ for which
$ud_{1}=d_{2}$, and similarly for lcms.

Furthermore, given $a,b\in R$ and $d$ a gcd of $a$ and $b$, an lcm $l$ of $a$
and $b$ can be chosen so that $dl=ab$. Equivalently, if $a$ and $b$ are
nonzero elements and $d$ is any gcd $d$ of $a$ and $b$, then $ab/d$ is an lcm
of $a$ and $b$.

Throughout the rest of this paper, we will use the notation $\gcd(a,b)$ and
$\mathrm{lcm}(a,b)$ with the understanding that they are only defined up to
multiplication by units. Furthermore, given a gcd of $a$ and $b$, we will
always choose an lcm so that $\gcd(a,b)=\frac{ab}{\mathrm{lcm}(a,b)}$.

Most basic facts about gcd’s and lcm’s still hold in GCD domains, but these
results must be proved without assuming either Bezout’s Theorem or unique
factorization. We provide proofs here for completeness.

######  Lemma 5.

Let $R$ be a GCD domain and let $a,b,x\in R$. Then $\gcd(ax,bx)=x\gcd(a,b)$.

###### Proof.

Let $g=\gcd(a,b)$ and $h=\gcd(ax,bx)$. Since $g|a$ and $g|b$, $gx|ax$ and
$gx|bx$. By definition, $gx|\gcd(ax,bx)=h$. Thus there exists some $y\in R$ so
that $gxy=h$. Since $h=\gcd(ax,bx)$, $h|ax$. Thus $gxy|ax$ and so $gy|a$. A
similar argument shows that $gy|b$. Since $g=\gcd(a,b)$, $gy|g$ and so $y$ is
a unit. But then $\gcd(a,b)xy=gxy=h=\gcd(ax,bx)$, so $\gcd(a,b)=\gcd(ax,bx)$.
∎

######  Lemma 6.

Let $R$ be a GCD domain. Then for any $a,b,c\in R$, if $a|bc$ and
$\gcd(a,b)=1$, then $a|c$

###### Proof.

Suppose that $a|bc$ and that $\gcd(a,b)=1$. Then there exists some $x\in R$ so
that $ax=bc$. If we let $g=\gcd(b,x)$, then $g|b$ and there exists a $y\in R$
for which $gy=b$. By Lemma 5, $ag=a\gcd(b,x)=\gcd(ab,ax)$. But
$\gcd(ab,ax)=\gcd(ab,bc)=b\gcd(a,c)=dy\gcd(a,c)$. Thus $a=y\gcd(a,c)$. By
defintion, $y|a$ and since $dy=b$, $y|b$. Together, these imply that
$y|\gcd(a,b)$ and since $\gcd(a,b)=1$, $y$ must be a unit. Since $a$ and
$\gcd(a,c)$ differ by a unit $a|c$. ∎

######  Lemma 7.

Let $R$ be a GCD domain and suppose that $a_{1},\ldots,a_{n}\in R$ are
pairwise relatively prime. Then so are $a_{1}^{m},\cdots,a_{n}^{m}$ for any
integer $m\geq 1$.

###### Proof.

We prove this in the case where $n=m=2$. A similar argument will give the more
general case. Suppose that $\gcd(a,b)=1$. We’ll show that this implies
$\gcd(a^{2},b^{2})=1$. Let $g=\gcd(a^{2},b^{2})$. Then there exist $x,y\in R$
so that $gx=a^{2}$ and $gy=b^{2}$. Thus $gxy=a^{2}y=b^{2}x$ and so $a|b^{2}x$.
Since $\gcd(a,b)=1$, Lemma 6 implies $a|x$, and so there exists some $z\in R$
so that $az=x$. Thus $a^{2}z^{2}=x^{2}$, which implies $gxz^{2}=x^{2}$, and so
$gz^{2}=x$. But this implies that $az=gz^{2}$ and so $a=gz$. Thus $g|a$. A
similar argument shows that $g|b$, and so $g|\gcd(a,b)$. Since $\gcd(a,b)=1$,
$g|1$ and so $\gcd(a^{2},b^{2})=1$, as desired. ∎

######  Theorem 4.7.

Let $R$ be a GCD domain and let $(G,A)$ be an edge-labeled graph where
$A=\left\\{a_{1},\ldots,a_{m}\right\\}$. Let
$Q=\mathrm{lcm}(a_{1},\cdots,a_{m})$. Then Q divides the determinant of any
set of $n$ elements of $R_{G}$. In particular, if $a_{1},\ldots,a_{m}$ are
pairwise relatively prime, then $Q=a_{1}\cdots a_{m}$.

###### Proof.

Let $C_{i}=(c_{i1},\ldots,c_{in})\in R_{G}$ and define
$C=[C_{1},\cdots,C_{n}]$. Then

$|C|=\begin{vmatrix}c_{11}&c_{12}&\cdots&c_{1n}\\\
c_{21}&c_{22}&\cdots&c_{2n}\\\ \vdots&\vdots&\ddots&\vdots\\\
c_{n1}&c_{n2}&\cdots&c_{nn}\\\
\end{vmatrix}=\begin{vmatrix}c_{11}-c_{21}&c_{12}-c_{22}&\cdots&c_{1n}-c_{2n}\\\
c_{21}&c_{22}&\cdots&c_{2n}\\\ \vdots&\vdots&\ddots&\vdots\\\
c_{n1}&c_{2n}&\cdots&c_{nn}\\\ \end{vmatrix}$

Let $a_{1}$ be the edge label between vertices $v$ and $w$. Without loss of
generality, assume $v=v_{1}$ and $w=v_{2}$. Then $a_{1}$ divides the
difference between the vertex labels associated to $v_{1}$ and $v_{2}$. This
means $a_{1}|c_{1j}-c_{2j}$ for all $1\leq j\leq n$, so $a_{1}||C|$. A similar
argument shows that for any $k$, $a_{k}||C|$. This implies that
$Q=\mathrm{lcm}(a_{1},\cdots,a_{n})||C|$. If $a_{1},\ldots,a_{m}$ are pairwise
relatively prime, $Q=\mathrm{lcm}(a_{1},\ldots,a_{m})=a_{1}\cdots a_{m}||C|$.
∎

We have an easy partial converse to Theorem 4.4 .

######  Proposition 4.8.

Let $R$ be an integral domain and let
$\mathcal{B}=\left\\{B_{1},\ldots,B_{n}\right\\}$ be a basis for $R_{G}$. Then
if $Q=\det(\mathcal{B})$, $Q|\det(C)$ for any n-element subset
$C=\left\\{C_{1},\dots,C_{n}\right\\}$ of $R_{G}$.

###### Proof.

Since $B_{1},\ldots,B_{n}$ form a basis for $R_{G}$, each $C_{i}$ is a linear
combination of the $B_{j}$’. Thus we may write
$C_{i}=\sum_{j=1}^{n}a_{ij}B_{j}$ for some $a_{ij}\in R$. Then if
$A=\begin{bmatrix}A_{i}j\end{bmatrix}$ is the matrix whose $ij$th entry is
$a_{i}j$, we have that

$\begin{bmatrix}C_{1},\ldots
C_{n}\end{bmatrix}=A\begin{bmatrix}B_{1},\ldots,B_{n}\end{bmatrix}$

Thus
$\det\begin{bmatrix}B_{1},\ldots,B_{n}\end{bmatrix}|\det\begin{bmatrix}C_{1},\dots,C_{n}\end{bmatrix}$,
as desired.

∎

We’d like a full converse to Theorem 4.4, but in order to do so we need to
find a $Q$ that is maximal with respect to dividing the determinants of all
$n$-element subsets of $R_{G}$. When the edge labels are relatively prime, the
desired $Q$ will be their product. We prove this result below, generalizing
Theorem 2.3 from [21] to GCD domains and arbitrary graphs. First we need a few
lemmas.

######  Lemma 8.

Let $R$ be a GCD domain and let $a_{1},\dots,a_{n}\in R$ be pairwise
relatively prime. Suppose $s|\hat{a_{i}}=a_{1}...a_{i-1}a_{i+1}...a_{n}$ for
all i. Then $s$ is a unit.

###### Proof.

Since $s$ is a common divisor of the $\hat{a_{i}}$ ,
$s|\gcd(\hat{a_{1}},\ldots,\hat{a_{n}})$. An argument from elementary number
theory shows that

$\gcd(\hat{a_{1}},\cdots,\hat{a_{n}})=\frac{a_{1}\cdots
a_{n}}{lcm(a_{1},\ldots,a_{n})}$

Since the $a_{i}$’s are pairwise relatively prime,
$\mathrm{lcm}(\hat{a}_{1},\cdots,\hat{a}_{n})=a_{1}\cdots a_{n}$. Then the
above equation implies that $gcd(\hat{a}_{1},\ldots,\hat{a}_{n})=1$, so $s|1$
and $s$ is a unit or $1$. ∎

We can now prove the main theorem of this section, which states that even when
no flow-up class basis exists, we not only have a formula for the determinant
of any basis of $R_{G}$, but we also have a criterion to determine if $R_{G}$
is free, as long as the edge labels are pairwise relatively prime.

######  Theorem 4.9.

Let $R$ be a GCD domain, let $G$ be a graph with relatively prime edge labels,
and let $Q=a_{1}\cdots a_{m}$. Then $R_{G}$ is free with basis
$\mathcal{B}=\\{B_{1},.,.B_{n}\\}$ if and only if $\det(\mathcal{B})=uQ$ for
some unit $u\in R$.

###### Proof.

Let $\mathcal{B}=\left\\{B_{1},\ldots,B_{n}\right\\}$ be a basis for $R_{G}$.
By Theorem 4.7, $\det(\mathcal{B})=sQ$ where $Q=a_{1}\cdots a_{m}$ and $s\in
R$. Let $Q_{{a}_{i}}=\hat{a_{i}}=a_{1}\cdots a_{i}a_{i+1}\cdots a_{n}$.
Without loss of generality, let $a_{1}$ be an edge connecting $v_{1}$ and
$v_{2}$ in $G$ and observe that

(4.1) $QQ_{{a}_{1}}^{n-1}=\begin{vmatrix}Q_{{a}_{1}}&0&0&\cdots&0\\\
Q_{{a}_{1}}&Q&0&\cdots&0\\\ 0&0&Q_{{a}_{1}}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&0\\\ 0&0&0&\cdots&Q_{{a}_{1}}\end{vmatrix}$

Since $a_{1}$ connects $v_{1}$ and $v_{2}$ in $G$, each column in the above
matrix is a spline in $R_{G}$, hence is in the span of the $B_{i}$’s. Since
$\det(\mathcal{B})=sQ$ , the determinant of the above matrix is equal to
$Qsr_{1}$ for some $r_{1}\in R$. But then $Qsr_{1}=Q(Q_{{a}_{1}})^{n-1}$, so
$(Q_{{a}_{1}})^{n-1}=sr_{1}$. Thus $s|(Q_{{a}_{1}})^{n-1}$. A similar argument
can be made for any edge $a_{i}$, so in fact we have that
$s|(Q_{{a}_{i}})^{n-1}$ for all edge labels $a_{i}$ and so $s|\hat{a_{i}}$ for
all $i$. Since the $a_{i}$ are pairwise relatively prime, by Lemma 8, $s$ is a
unit. Thus $\det(\mathcal{B})=sQ$, where $s$ is a unit, as desired.
Conversely, suppose $\det(\mathcal{B})=Q$. By Lemma 4.7, Q divides the
determinant of any set of $n$ elements of $R_{G}$, hence by Theorem 4.4,
$\mathcal{B}$ is a basis for $R_{G}$. ∎

We conjecture that when the edge labels are not relatively prime, the previous
theorem will be true when $Q$ is maximal with respect to dividing all
determinants of n-element subsets of $R_{G}$. In [22], Rose and Suzuki
constructed explicit flow-up class bases when $R=\mathbb{Z}$ \- but the proofs
extend easily to any PID - where the leading terms are described by least
common multiples and greatest common divisors of certain subsets of the edge
labels.

Let $(G,A)$ be an edge-labeled graph where $A=\\{a_{1},\ldots,a_{m}\\}$ is an
arbitrary set of elements of a GCD domain R. Let $\\{l_{1},\ldots,l_{n}\\}$
have the same theoretical form (in terms of gcds and lcms of edge labels) as
the leading terms of the flow-up class bases constructed in [22].

Conjecture. Let $R$ be a GCD domain and $Q$ be the product of the leading
terms $l_{i}$ defined above. Then $B$ is a basis for $R_{G}$ if and only if
$\det(B)=uQ$ for some unit $u\in R$.

######  Remark 4.10.

Gjoni [14], Mahdavi [18], and Blaine [9] proved this conjecture for integer
splines on cycles and diamond graphs, and Altinok and Sarioglan ([2], [3])
extended their results to arbitrary GCD domains in the special case of cycles
and diamond graphs.

##  5\. Spline Modules with no Flow-up Class Bases

The theorem below illustrates that Theorem 3.3 is likely the best possible,
i.e. if $R$ is not a PID, then a flow-up class basis is not guaranteed.

$f_{1}$$f_{2}$$f_{3}$$a$$b$$c$

Figure 3. Generalized spline on a 3-cycle with edge weights $a,b,c$

######  Theorem 5.1.

Let $R$ be a GCD domain that is not a PID. Then there always exists a spline
module that does not have a flow-up class basis.

###### Proof.

We prove this by finding an explicit graph and edge labels for which $R_{G}$
has no flow-up class basis. Let $G$ be a three-cycle with edge labels
$a,b,c\in R$ as in Figure 3.

Suppose that $a,b,c$ are pairwise relatively prime, where $<b,c>$ is not
principal and $a\notin<b,c>$.

The defining equations for the spline in Figure 3 imply that $a|f_{1}-f_{2}$,
$b|f_{2}-f_{3}$ and $c|f_{3}-f_{1}$. Thus, any flow up class basis has the
form $B_{1}=(1,1,1)$, $B_{2}=(0,ax,cy)$ and $B_{3}=(0,0,bcz)$ for some $x,y,z$
in $R$. Let $B=[B_{1},B_{2},B_{3}]$. Then $\det(B)=abcxz$. On the other hand,
since $a,b,c$ are pairwise relatively prime, $\det(B)=uabc$ for some unit
$u\in R$. Thus, $abcxz=uabc$ so $xzu^{-1}=1$ and so $x$ and $z$ are also units
in $R$. Since $b|f_{2}-f_{3}$ where $f_{2}=ax$ and $f_{3}=cy$, we have that
there exists some $w\in R$ so that $ax-cy=bw$. Since $x$ is a unit, we may
divide both sides by $x$ to obtain $a=x^{-1}cy+x^{-1}bw$ so that $a\in<b,c>$.
This is a contradiction. Thus no flow-up class basis for $R_{G}$ exists. ∎

$f_{1}$$f_{2}$$f_{3}$$x^{2}$$y^{2}$$(x+y)^{2}$

Figure 4. Generalized spline on a 3-cycle with edge weights
$x^{2},y^{2},(x+y)^{2}$

######  Proposition 5.2.

: Let $G$ be a three-cycle with edge labels $x^{2},y^{2}$ and $(x+y)^{2}$ over
the ring $R=k[x,y]$ where $\text{char}(k)\neq 2.$ Then $R_{G}$ is free, but
does not have a flow-up class basis.

.

###### Proof.

First note that $R_{G}$ is free by [20], since it corresponds to a polynomial
spline module in two variables over a subdivided disk. Assume it has a flow-up
class basis $\mathcal{B}=\\{B_{1},B_{2},B_{3}\\}$. Then by Theorem 4.9,
$\det(\mathcal{B})=ux^{2}y^{2}(x+y)^{2}$ for some unit $u\in k[x,y]$. Then we
can assume that $B_{1}=(1,1,1)$, $B_{2}=(0,f,g)$ and $B_{3}=(0,0,h)$.
Referring to Figure 4, the defining equations imply $f=rx^{2}$,
$g=s(x+y)^{2}$, $g-f=ty^{2}$, and $h=py^{2}(x+y)^{2}$, for some $r,s,t,p\in
k[x,y]$.

Then $\det[B_{1},B_{2},B_{3}]=fh=rpx^{2}y^{2}(x+y)^{2}$. Since this must also
equal $ux^{2}y^{2}(x+y)^{2}$ , we have that $rpu^{-1}=1$, so $r$ and $p$ are
units, hence nonzero constants. Since $g-f=ty^{2}$, we have that
$s(x+y)^{2}=rx^{2}+ty^{2}$. Equating coefficients, we see that $s=t=r$. Hence
$(x+y)^{2}=x^{2}+y^{2}$, which is false as long as $\text{char}(k)\neq 2.$ ∎

Although they are not guaranteed, flow-up class bases can exist over
$R=k[x,y]$. A trivial example would be if $G$ is a tree, since in this case
$R_{G}$ has a flow-up class basis over any commutative ring with unity.
([13].) However, there are non-trivial examples, as we see below.

$f_{1}$$f_{2}$$f_{3}$$x$$y$$x+y$

Figure 5. Generalized spline on a 3-cycle with edge weights (x,y,x+y)

######  Example 5.3.

Let $G$ be the 3-cycle graph in Figure 5 with edge labels $x$, $y$, and $x+y$.
Let $B_{1}=(1,1,1),B_{2}=(0,x,x+y)$ and $B_{3}=(0,0,y(x+y))$. It’s easy to see
that these satisfy the spline conditions, and that
$\det[B_{1},B_{2},B_{3}]=xy(x+y)$, the product of the edge labels. It follows
from Theorem 4.4, that $B_{1},B_{2},B_{3}$ form a flow-up class basis for
$R_{G}$.

## References

  * [1] P. Alfeld, L.L. Schumaker, M. Sirvent, On dimension and existence of local bases for multivariate spline spaces, J. Approx. Theory 70, (1992).
  * [2] S. Altinok and S. Sarioglan, Flow up bases for generalized spline modules over arbitrary graphs, Journal of Algebra and Its Applications, Vol. 20, No. 10, 2150180 (2021)
  * [3] S. Altinok and S. Sarioglan, Basis criteria for generalized spline modules via determinant, Discrete Mathematics, Volume 344, Issue 2,2021.
  * [4] K. Anders, Alissa Crans, Briana Foster-Greenwood, Blake Mellor, Julianna Tymoczko, Graphs admitting only constant splines, Pacific J. Math. 304, (2020) 385–400.
  * [5] L. Billera, The algebra of continuous piecewise polynomials, Advances in Math. 76 (1988), 170–183.
  * [6] L. Billera, Homology of smooth splines: generic triangulations and a conjecture of Strang, Transactions of the American Mathematical Society, 310 (1) (1998), 325–340.
  * [7] L. Billera, L. Rose, A dimension series for multivariate splines, Discrete Computational Geometry, 6 (2) (1991), 107–128.
  * [8] L. Billera, L. Rose, Modules of Piecewise Polynomials and their Freeness, Mathematische Zeitschrift, 209 (1992).
  * [9] K. Blaine, Determinantal Conditions on Integer Splines, Senior Thesis, Bard College, 2018.
  * [10] N. Bowden, M. King, S. Hagen, S. Reinders, Bases and Structure Constants of Generalized Splines with Integer Coefficients on Cycles,  arXiv:1502.00176 (2015).
  * [11] N. Bowden, J. Tymoczko, Splines $\mod m$. arXiv:1501.02027 (2015).
  * [12] Oscar A. C´ampoli, A principal ideal domain that is not a Euclidean domain, Amer. Math. Monthly, 95 (9) (1988), 868–871.
  * [13] S. Gilbert, J. Tymoczko, S. Viel, Generalized Splines on Arbitrary Graphs, Pacific Journal of Mathematics, 281 (2) (2016), 333–364.
  * [14] E. Gjoni,  Basis Criteria for n-cycle integer splines, Senior Thesis, Bard College, 2015.
  * [15] R. Haas, Module and vector space bases for spline spaces, Journal of Approximation Theory 65 (1) (1991), 73–89.
  * [16] M. Handschy, J. Melnick, S. Reinders, Integer Generalized Splines on Cycles. arXiv:1409.1481 (2014).
  * [17] J. Liu, L. Rose, K. Sangam, J. Suzuki and E. Zhang, Modules Bases for Integer Splines, in revision.
  * [18] E. Mahdavi, Integer Generalized Splines on the Diamond Graph, Student Thesis, Bard College, 2016.
  * [19] L. Rose,Combinatorial and topological invariants of modules of piecewise polynomials, Advances in Mathematics, 116 (1), (1995) 34–45.
  * [20] L. Rose, Graphs, syzygies and multivariate splines, Discrete and Computational Geomeomtry, 32 (4) (2004), 623–637.
  * [21] L. Rose, Module Bases for Multivariate Splines, Journal of Approx. Theory 86 No. 1, (1996).
  * [22] L. Rose and J. Suzuki, Generalized integer splines on arbitrary graphs, to appear in Discrete Math.
  * [23] J. Tymoczko, Splines in geometry and topology, Computer Aided Geometric Design, 45 (2016), 32–47.