\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.19}{25(2)}{2018}

\usepackage{microtype, mathtools}
\usepackage{diagbox}

% vectors https://tex.stackexchange.com/a/266741/8865

\usepackage{xparse}
\ExplSyntaxOn
\NewDocumentCommand{\rvect}{m}
 {
  \seq_set_split:Nnn \l_tmpa_seq { , } { #1 }
  \begin{bmatrix}
  \seq_use:Nn \l_tmpa_seq { & }
  \end{bmatrix}
 }
\ExplSyntaxOff

\usepackage{amsmath,amssymb}
%https://tex.stackexchange.com/a/130655/8865
\usepackage{amsthm}
%\newtheorem{definition}{Definition}
%\newtheorem{lemma}{Lemma}
%\newtheorem{theorem}{Theorem}
%\newtheorem{proposition}{Proposition}
%\newtheorem{corollary}{Corollary}

%\usepackage{thmtools}
%\declaretheorem[style=definition,qed=$\triangle$]{example}

\theoremstyle{definition}
\def\betweenskip{\vskip10pt}

\def\boxitat#1#2{\vbox             % from TeXbook Ex.21.3
     {\hrule\hbox{\vrule\kern#1%
     \vbox{\kern #1\hbox{#2}\kern#1}\kern#1\vrule}\hrule}}
\def\enclose#1{\boxitat{0pt}{#1}}

\def\qedspace{\null}
\def\qedblack{\qedspace                    % SOLID BOX
  \lower.6pt\hbox{\vrule height7pt width 5pt}}
\def\qedwhite{\qedspace                    % HOLLOW BOX
  \lower.6pt\enclose{%
        \hbox{\vrule height7pt width 0pt\hskip6pt}}}
\def\QED{\qedwhite}

\def\beq{\begin{equation}}
\def\eeq{\end{equation}}

\usepackage{amssymb} % gives special symbols like blackboard bold
\usepackage{csquotes}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\disjun}{\mathbin{\dot{\cup}}}
\def\complexes{{\mathbb C}}
\def\naturals{{\mathbb N}}
\def\reals{{\mathbb R}}
\def\integers{{\mathbb Z}}
\def\bep{{\mathbf \varepsilon}}
\def\eps{{\varepsilon}}
%% cal letters
\def\si{{\sigma}}
\def\om{{\omega}}
\def\sP{{\cal P}}
\def\sA{{\cal A}}
\def\sW{{\cal W}}
\def\sR{{\cal R}}
\def\sT{{\cal F}}
\def\sF{{\cal F}}
\def\sN{{\cal N}}
\def\mod{{\rm \,mod\,}}
\def\sC{{\cal C}}
\def\hC{{\hat C}}
\def\sL{{\cal L}}
\def\bx{{\bf x}}
\def\by{{\bf y}}
\def\bu{{\bf u}}
\def\bv{{\bf v}}
\def\bz{{\bf z}}
\def\bn{{\bf n}}
\def\bj{{\bf j}}
\def\bs{{\bf s}}
\def\bt{{\bf t}}
\def\bg{{\bf g}}
\def\bh{{\bf h}}


\def\fq{{\mathbb F}_q}
\def\fp{{\mathbb F}_p}
\def\Zk{{{\mathbb Z}_k}}
\def\Zp{{{\mathbb Z}_p}}
\def\mZ{{\mathbb Z}}

\def\cvec#1{{\mathbf{#1}}}
\def\term{\mbox{\boldmath $\beta$}}
\def\start{\mbox{\boldmath $\alpha$}}
\def\sS{{\cal S}}
\def\sR{{\cal R}}
\def\sT{{\cal T}}
\def\len{{\rm len}}
\def\SEQ{\textsc{Seq}}
% http://latex.org/forum/viewtopic.php?t=15689
\def\spn{{\sigma}}


\dateline{Jan 6, 2018}{Mar 4, 2018}{Apr 27, 2018}

\MSC{05A15, 05A16}

\Copyright{The authors. Released under the CC BY license (International 4.0).}

\title{Counting  compositions over finite abelian groups}


\author{
  Zhicheng Gao\thanks{This work is supported in part by NSERC.} \qquad
  Andrew MacFie \qquad
  Qiang Wang\thanks{This work is supported in part by NSERC.}\\
\small School of Mathematics and Statistics\\[-0.8ex]
\small Carleton University\\[-0.8ex]
\small Ottawa, Canada\\
\small \tt{zgao@math.carleton.ca}, \tt{andrewmacfie@carleton.ca},
  \tt{wang@math.carleton.ca}
}


\begin{document}


\maketitle


\begin{abstract}
We find the number of compositions over finite abelian groups under two types
of restriction: (i) each part belongs to a given subset and (ii) small
runs of consecutive parts must have given properties.
Waring's problem over finite fields can be converted to type~(i) compositions,
whereas Carlitz and \enquote{locally Mullen} compositions can be formulated as
type~(ii) compositions.
We use the {multisection formula} to translate the problem from
integers to group elements, the transfer matrix method to do exact counting,
and finally the Perron-Frobenius theorem to derive asymptotics.
We also exhibit bijections involving certain restricted classes of
compositions.

\bigskip\noindent \textbf{Keywords:} Integer composition, finite abelian group,
transfer matrix, enumeration.
\end{abstract}



\section{Introduction}

Let $n$ and $m$ be positive integers.
A \emph{composition} of $n$ is a sequence of positive integers whose sum
is $n$.
An \emph{$m$-composition} is a composition consisting of $m$ terms, also called
parts.
It is well known that there is a bijection between $m$-compositions of $n$
and $(m-1)$-subsets of $\{1, 2, \ldots, n-1\}$ and thus there are
$\binom{n-1}{m-1}$ $m$-compositions of $n$ and $2^{n-1}$ compositions of $n$.
A \emph{weak composition} is the same as a composition except terms equal to
$0$ are allowed.
Using substitution of variables, we can easily see that the number of weak
$m$-compositions of $n$ is equal to the number of $m$-compositions of $n
+ m$, which is $\binom{n+m-1}{m-1} = \binom{n+m-1}{n}$.
%The combinatorial interpretation of $\binom{n+m-1}{m-1} = \binom{n+m-1}{n}$ is
%the number of ways in selecting $n$-multisets from a set $M$
%with $m$ elements, which is sometimes called $n$-combinations of $M$
%with repetitions.
%Disregarding the order of the summands, we have the concepts of partitions of
%$n$ into $m$ parts, partitions of $n$ into at most $m$ parts,  and so on.
%For more details we refer the reader to \cite{Stanley}.


Problems on or related to compositions have been studied over algebraic
structures beyond the integers.
Let $\fq$ be a finite field of $q$ elements and let $\fq^*=\fq\setminus \{0\}$.
%The subset sum problem over a subset $S \subseteq \fq$ is to determine for a
%given $s \in \fq$, if there is a nonempty subset $\{x_1, x_2, \ldots, x_m\}
%\subseteq S$ such that $x_1 + x_2  + \cdots +x_m  = s$.
%This subset sum problem is known to be $\mathbf{NP}$-complete.
Li and Wan \cite{LiWan, LiWan:12} estimated the number
$$N(m, s, S) = \left| \left\{ \{x_1, x_2, \ldots, x_m\} \subseteq  S \mid  x_1
  + x_2  + \cdots + x_m  = s \right\} \right|$$
of $m$-subsets of $S
\subseteq \fq$ whose sum is $s \in \fq$.
In particular, exact formulas are obtained in cases where $S= \fq$ or $\fq^*$
or $\fq \setminus \{0, 1\}$. A shorter proof was given by Kosters
\cite{Kosters:13}  using character theory.
Motivated by the study by Li and Wan and the study of polynomials of prescribed
ranges over finite fields \cite{gacsetal,MuWa}, Muratovi\'{c} and Wang proposed
to study
$$c(m, s, S) = \left| \left\{ (x_1, x_2, \ldots, x_m) \in S \times S \times
  \cdots \times S \mid  x_1 + x_2  + \cdots + x_m = s \right\} \right|,$$
that is, the number of
ordered $m$-tuples  whose sum is $s$ and where each coordinate belongs to $S
\subseteq \fq$, as well as the number $M(m, s, S)$ which counts the number of
$m$-multisets over $S \subseteq \fq$ whose sum is $s \in \fq$.
In particular, when $S = \fq^*$,
%or $\fq$
this essentially gives the concept of
compositions and partitions over a finite field, respectively.

A \emph{partition} of $s\in \fq $ into $m$ parts is a multiset of $m$ elements
of $\fq^*$ whose sum is $s$.
The $m$ nonzero elements are refered to as the parts of the partition.
%We denote by $M(m, s, \fq^*)$  the  number of partitions of $s$ into $m$ parts over $\fq$.
%Similarly,  we denote by $M(m, s, \fq)$  the  number of
%partitions of $z$ into at most  $m$ parts over $\fq$
%and by $\tilde{P}(s)$ the total number of partitions of $s$ over finite field
%$\fq$.
%We remark that $N(m, s, \fq^*)$ is the number of partitions of an
%element $s$ over finite field $\fq$ such that all summands are
%distinct, and  $M(m, s, \fq^*)$ is the number of partitions of an
%element $s$ into $m$ parts over finite field $\fq$, dropping the restriction
%that all summands are distinct.
In \cite{MurWan2}, Muratovi\'{c} and Wang  obtain an exact formula for $M(m, s,
\fq^*)$,  the number of partitions of an element $s$ into $m$ parts over finite
field $\fq$.


A \emph{composition} of $s\in \fq $ with $m$ parts is a solution
$(x_1, x_2, \ldots, x_m)$  to the equation
\begin{equation} \label{eqCompo}
s=x_1+x_2+\cdots +x_m,
\end{equation}
with each $x_i \in \fq^*$. Similarly, a \emph{weak composition} of $w\in \fq $
with $m$ parts is
a solution $(x_1, x_2, \ldots, x_m)$ to Equation~(\ref{eqCompo}) with each $x_i \in \fq$.
We denote the number of compositions of $s$ having $m$ parts by
$c(m, s, \fq^*)$.
The number of weak compositions of $s$ with $m$ parts is denoted by $c(m, s,
\fq)$.
%% The total number of compositions of $s$ over $\fq$ is denoted by  $S(s)$.
A formula for $c(m,s,\mathbb{F}_p)$ can be found in \cite[p.~295]{BEW}.
A general formula for $c(m, s, \fq^*)$ for arbitrary $q$  and nonzero $s$ can
be obtained using a remark on the normalized Jacobi sum of the trivial
character given in \cite{Conrad} (see Remark~1 on page 144).
A recurrence relation for $c(m,s,\fq)$ is given in \cite{MurWan}.


\iffalse
\begin{theorem}\label{compositions}
Let $m>2$, $\fq$ be a finite field of $q=p^r$ elements with prime $p$, and
  $z\in \fq$.
The number of compositions of $z$ with $m$ parts over $\fq$ is given by
$$S_m(z)=(q-1)^{m-2}(q-2)+S_{m-2}(z).$$
It follows that
$$S_m(0)=\frac{(q-1)^m+(-1)^m(q-1)}{q}$$
and
$$S_m(z)=\frac{(q-1)^m-(-1)^m}{q}, \mbox{ if } z\neq 0.$$
\end{theorem}
\fi


Counting compositions over finite fields where parts are restricted to
a subset is conceptually related to Waring's problem and solutions to diagonal
equations.
In number theory, Waring's problem asks whether each natural number $k$ has an
associated positive integer $m$ such that every natural number is the sum of at
most $m$ natural numbers to the power of $k$.
The problem was originally posed in 1770 and answered in the affirmative for
integers by Hilbert in 1909.
Since then, there has been a good deal of research on estimating the Waring's
number $g(k)$ for every $k$, which denotes the minimum number $m$ of
$k$\textsuperscript{th} powers of naturals needed to represent all positive
integers.

Over finite prime fields $\fp$, Waring's number $g(k, p)$ is  the smallest
number $m$ such that for all $a \in \fp$, the equation
\begin{equation*}
x_1^k + x_2^k + \cdots + x_m^k \equiv a \pmod{p}
\end{equation*}
has a solution in integers $x_i$ (see for example~\cite{Cochrane}).
Waring's problem over finite fields is to estimate $g(k, p)$ and, when
possible, evaluate it.
This is equivalent to finding the smallest number $m$ such that
\begin{equation*}
x_1 + x_2 + \cdots + x_m \equiv a \pmod{p}
\end{equation*}
has a solution such that $x_i \in S$ where $S$ denotes the subset of $\fp$
consisting of all $k$\textsuperscript{th} powers in $\fp$.
Essentially we need to find the number of solutions $(x_1, x_2, \ldots, x_m)$
in $S\times S \times \ldots \times S$ and pick the minimum $m$ so that this
number is always positive for any $a\in \fp$.
However, this is a computationally difficult task in general.
%The number of solutions to Equation (\ref{eq:waring})
%can be viewed as the number of compositions over the ring $\Zp$ such that each
%part $x_i$ lies in a subset $S_i$ defined as above.


There is also extensive study on the number of solutions to \enquote{diagonal}
equations of the type
\begin{equation} \label{diagonal}
a_1 x_1^{d_1} + \cdots + a_m x_m^{d_m} = a,
\end{equation}
where $a_1, \ldots, a_m\in \fp^*$, $a\in \fp$ and $d_1, \ldots, d_n$ are
positive integers.
The pioneering work has been done by Weil \cite{Weil49}, who
expressed the number of solutions in terms of Jacobi sums.
Explicit
formulas for the number of solutions for certain choices of $a_1, \ldots, a_m,
a$, and exponents $d_1, \ldots, d_m$ can be deduced from Weil's expression;
one may consult
\cite{Baoulina10, Baoulina16,CaoSun07, Sun97, SunYuan96,Wolfmann92} and the
references therein for details.
For diagonal equations, the problem can be again viewed as a composition
problem over $\fp$, such that each part is restricted to lie in a coset of a
multiplicative subgroup.


Using the fact that the additive group $(\fq,+)$ is isomorphic to the
additive group $(\mathbb{F}_p^r,+)$,
we obtain that the numbers of partitions and compositions of
elements over $\mathbb{F}_p^r$ are the same as the numbers of partitions
and compositions of corresponding elements over $\fq$.
More generally, the number of partitions over an arbitrary finite abelian group
is given in \cite{MurWan2}.
However, problems of enumerating compositions over an arbitrary finite abelian
group are largely open.
We note that there have been some studies on compositions over integer tuples
\cite{Lou08,MPR09}, which are also called matrix compositions.

In the present work, we consider two general problems on restricted
compositions over finite abelian groups.
Let ${\mZ}_k$ denote the additive cyclic  group $\{0,1,2,\ldots, k-1\}$ and
${\mZ}^{*}_k:=\{1,2,\ldots,k-1\}$.
Since a finite abelian group $G$ is isomorphic to a direct sum $\bigoplus_{t=1}^r
\mZ_{k_t}$, in the following we use $G$ to denote such a direct sum.
Sometimes it is convenient to add (tuples of) elements of $\mZ_k$ as integers,
so when performing group addition in $G$ we explicitly speak of modular
addition.
In the rest of the paper, we also assume $|G|\ge 2$, and consequently $k_t\ge
2$ for each $1\le t\le r$.
We also use $\bf 0$ to denote the zero element of $G$ and
adopt the notation $G^*:=G\setminus \{{\bf 0}\}$.

\begin{definition}[Compositions over a finite abelian group]
An \emph{$m$-composition of $\bs\in G$ over $G$} is a solution to
$\bx_1+\cdots +\bx_m = {\bs}$, where each $\bx_i=(x_{i, 1}, \ldots, x_{i, r})$
is a nonzero element of $G$ and addition is taken component-wise and modulo
$k_t$ for $1\le t\le r$.
If we allow ${\bf 0}$ as a value for the $\bx_i$, then we speak of \emph{weak
compositions} over $G$.
\end{definition}

Firstly we are interested in finding the number of $m$-compositions over $G$
such that for $1 \leq j \leq m$, part $\bx_j$ is restricted to an abitrary
subset $S_j \subseteq G$.
Our contribution is Theorem~\ref{thm:Subset},
where we obtain an asymptotic formula for the number of such $m$-compositions
as $m\to \infty$.
%We first treat $G$ as the
%set of integer tuples in $\bigoplus_{t=1}^r \mZ_{k_t}$ and each $S_j =
%\prod_{t=1}^r S_{t, j}$ as a subset of $G$ and obtain the generating function
%for the number of $m$-compositions of integer tuples in $G$ such that each part
%is in $S_j$. Then we obtain the generating function for $m$-compositions over
%the finite abelain group $G$ using a multivariate multisection formula.


Secondly, we enumerate $m$-compositions over a finite abelian group $G$ such
that any $d$ consecutive parts satisfy certain conditions for a given positive
integer $d$.
These are called locally restricted compositions.
Bender and Canfield \cite{BC09} studied integer compositions under general
local restrictions.
For example, Carlitz compositions are those in which adjacent parts are
distinct.
In a private communication, G.\ L.\ Mullen   \cite{mullen} suggested the following problem:
Let $p$ be a prime, and let $d$ and $m$ be positive integers with $d \leq m$.
Let $N_m^{(d)}$ denote the number of solutions to the congruence $x_1 + \cdots
+ x_m \equiv 1 \pmod{p}$ where each subsum $\sum  x_j$ of at most $d$ parts is nonzero (modulo $p$).
Find $N_m^{(d)}$ when $d\geq 2$. Motivated by Mullen's problem, we consider a
related problem which falls within the locally-restricted framework.  Namely,
we estimate the number of solutions to the congruence $x_1 + \cdots + x_m
\equiv 1 \pmod{p}$ where  each subsum $\sum_{j=i}^{i+d-1}  x_j$  ($1\leq i \leq
m-d+1$) of at most $d$ consecutive parts is nonzero.  We call these
compositions {\it locally $d$-Mullen compositions}.
%A recurrence formula when $d=1$ was obtained by Mullen.
%However, it is still unsolved for general $d$.
%This motivates us to study compositions over finite albelian groups under more
%general local restrictions.
Generating functions for general locally restricted compositions over finite
abelian groups are given in Proposition~\ref{prop:local}.
Under moderate conditions, the asymptotic number of locally restricted
compositions is given in Theorem~\ref{thm:local}. As consequences, we obtain
asymptotics for a few concrete composition problems including locally
$d$-Mullen compositions (see Corollary~\ref{cor:local}, 
Corollary~\ref{cor:list},  and Theorem~\ref{theorem:locallyMullen}).

We present these main results in Section~\ref{sec:results}.
Some auxiliary propositions are discussed in Section~\ref{sec:propositions} and
the proofs of the main results are given in Section~\ref{sec:proofs}.
In Section~\ref{sec:biject} we present bijections which help illuminate
locally $d$-Mullen compositions.
Finally we give conclusions in Section~\ref{sec:conclusion}.







\section{Main results} \label{sec:results}
Recall that $G$ denotes the set of integer tuples in the direct sum
$\bigoplus_{t=1}^r\mZ_{k_t}$.
In the following we denote the order of $G$ by $|G|:=\prod_{t=1}^rk_t$.

\begin{theorem}[Subset restriction]\label{thm:Subset}
For each $j \in \{1, 2, \ldots\}$, let $S_j$ be the Cartesian product
$\prod_{t=1}^rS_{t,j}$ where
$S_{t,j}$ is a given subset of $\mZ_{k_t}$.
Let $c(\bs;S_1,\ldots,S_m)$ be the
number of  $m$-compositions of $\bs$ over
$G$ such that the $j\textsuperscript{th}$ part lies in
$S_j$, for each $j \in \{1, \ldots, m\}$.
Assume that for $1\le t\le r$ and $j \geq 1$ we have
$$\gcd\{a-b:a,b\in S_{t,j}\}=1.$$
Then, as $m \to \infty$,
$$c(\bs;S_1,\ldots,S_m)=\frac{1}{|G|}\left(\prod_{j=1}^m|S_{j}|\right)
  (1+O(\theta^m)),$$
where $0<\theta<1$ is a constant independent of $m$.
\end{theorem}


Let \(\SEQ_{m}(G) := \left\{ (\bx_1, \bx_2, \ldots, \bx_m): \bx_j \in G
\right\} = G^m\) denote the class of all possible weak $m$-compositions over
$G$.
The \emph{size} of a composition, denoted $|(\bx_1, \bx_2, \ldots, \bx_m)|$, is
defined to be the sum $\sum_{j=1}^m \bx_j$, using component-wise integer
addition.
Let $\SEQ(G) = \cup_{m\geq 0} \SEQ_{m}(G)$.
A subclass $\mathcal{A} \subseteq \SEQ(G)$ is called \emph{locally restricted}
if any $d$ consecutive parts satisfy certain restrictions for a given positive
integer $d$.
General locally restricted integer compositions were first studied in
\cite{BC09} using local restriction functions.
They can also be defined using local restriction digraphs.
For the purpose of this paper, we use the following definition, which is
essentially from \cite{BG16}.

\begin{definition}[Locally restricted compositions associated with a digraph] \label{def3}
Let $\spn$ be a positive integer.
We use $\eps$ to denote the empty composition, and we use $\eps_s$ to denote
a distinguished copy of $\eps$.
Let $\sT=\SEQ_{0}(G) \cup \cdots \cup \SEQ_{\si-1}(G)$, and let
$\sR$ be a nonempty subset of $\SEQ_{\spn}(G)$.
Let $D$ be a digraph with vertex set $V(D)=\{\eps_s\} \disjun \sR \disjun \sT$.
Assume $D$ satisfies the following conditions.
\begin{enumerate}
\item There is at least one arc from $\eps_s$ to $\sR$ and at least one arc from
  $\sR$ to $\sT$.
\item There are no arcs (including loops) between vertices in
  $\{\eps_s\} \disjun \sT$.
\item The sub-digraph $D_{\sR}$ of $D$ induced by $\sR$ is strongly
  connected and contains at least two vertices.
\end{enumerate}
The vertices in $\sR$ are called \emph{recurrent} vertices.
Let $\sW$
denote the set of directed walks from $\eps_s$ to $\sT$, and let $\SEQ(G;D)$
denote the class of compositions obtained by concatenating vertices in $\sW$.
Then $\SEQ(G;D)$ is called the class of \emph{locally restricted compositions
over $G$ associated with $D$}.
We call $\spn$ the {\em span} of $\SEQ(G;D)$.
\end{definition}

Informally, we are defining $\SEQ(G;D)$ by specifying two sets $\sR$ and $\sT$
of ``building block'' compositions, and saying how they may be combined
sequentially to form the compositions of interest:
Two blocks are allowed to be joined if there is an arc between them in $D$.
The structure of the graph implies that sequences of vertices forming a walk
from $\eps_s$ to $\sT$ are made up of one or more elements of $\sR$ followed
by one element of $\sT$.
Defining combinatorial objects by walks in graphs is a standard technique; see
e.g.\ \cite[Sec.~4.7]{Stanley}.

\begin{example}[Nonzero adjacent sum over $\Zk$] \label{exa:nonzero}
Take compositions over $\Zk$ such that the sum of two adjacent parts is
nonzero, modulo $k$.
We can represent these compositions using a local restriction digraph as
follows.
In the digraph $D$, set $\sR=\mathbb{Z}_k^* \subset \SEQ_{1}(\Zk)$, and
$\sT=\SEQ_0(\Zk)=\{\eps\}$.
Include an arc from $u$ to $v$ in $\sR$ if and only if $u+v\not\equiv 0$ (mod $k$).
In this case, we have locally restricted compositions over $\Zk$  with span
$\sigma=1$.
The digraph for weak compositions is defined similarly with $\sR=\Zk =
\SEQ_{1}(\Zk)$.
\end{example}

\begin{example}[Carlitz compositions over $\Zk$] \label{exa:carlweak}
Recall that Carlitz compositions are those where adjacent parts are distinct.
A corresponding local restriction digraph $D$ has vertex sets
$\sR=\mathbb{Z}_k^* \subset \SEQ_{1}(\Zk)$
(or $\sR=\Zk = \SEQ_{1}(\Zk)$ for weak compositions), $\sT=\{\eps\}$, and there
is an arc from any vertex in $\sR$ to any different vertex in $\sR$. In this
case, we have  locally restricted compositions over $\Zk$  with span
$\sigma=1$.
\end{example}

We note that it is possible for two different digraphs $D_1$ and $D_2$ to
define equal families $\SEQ(G; D_1)$ and $\SEQ(G; D_2)$ of compositions over
$G$.
For example, Carlitz compositions can also be defined using a digraph with span
$\spn=2$ such that each recurrent vertex is a pair of distinct nonzero elements
of $G$.

\begin{example}[Locally Mullen compositions] \label{exa:Mullen}
Recall that locally $d$-Mullen compositions over $G$ are those such that the
sum of at most $d$ consecutive terms is nonzero in $G$.
Example~\ref{exa:nonzero} gives locally 2-Mullen compositions.
A digraph $D$ with span $3$ for locally 3-Mullen compositions can be
defined as follows.
Let $\sR$ be the set of locally 3-Mullen compositions with 3 parts over $G$.
We join $\eps_s$ to every vertex in $\sR$, and
join a vertex $\bu\in \sR$ to a vertex $\bv\in \sR\cup \sT$ if the
concatenation $\bu\bv$ is a locally 3-Mullen composition.
\end{example}

\begin{theorem}[Local restriction]\label{thm:local}
Consider a class $\SEQ(G; D)$ of locally restricted compositions with span
$\spn$. Suppose the following are satisfied.
  \begin{enumerate}

    \item The greatest common divisor of the lengths of all directed cycles in
      $D_{\sR}$ is equal to $1$.
    \item For each $1\le t\le r$, there is a positive integer $\ell$,
      two recurrent vertices $\bu$ and $\bv$, and a nonempty set
      $\sW_{\sR}$ of directed walks in $D_{\sR}$ of length $\ell$ from $\bu$ to
      $\bv$ such that the following hold.
      \begin{enumerate}
        \item For each walk $W=\bu\bu_1\ldots\bu_{\ell-1}\bv$ in $\sW_{\sR}$
          and each $i\ne t$,
          we have $u_{i,j}=\phi_{i,j}$,
          where $u_{i,j}$ denotes  the $i\textsuperscript{th}$ coordinate of
          the size vector $|\bu_j|$   and $\phi_{i,j}$ is fixed over all walks
          in  $\sW_{\sR}$.
        \item We have $\gcd\{m-n:m,n\in N\}=1$, where $N=\{n:n=u_{t,1}+\cdots+
          u_{t,\ell-1} \hbox{ for some walk
          $\bu\bu_1\ldots\bu_{\ell-1}\bv\in \sW_{\sR}$} \}$.
      \end{enumerate}
  \end{enumerate}
  Let $m=a\spn +b$ for some integers $a,b$ with $a\ge 1$ and $0\le b<\si$, and let $c_m(\bs,D)$ be the
  number of $m$-compositions of
  $\bs$ in $\SEQ(G; D)$.
  Fix $b$ but allow $a$ to vary.
  Suppose further that there is at least one arc from $\sR$ to $\SEQ_b(G)$.
  Then there are constants $A>0, B>1$ and $0<\theta<1$ (that is, independent of
  $m$ but perhaps depending on $b$) such that
  $$c_m(\bs,D)=A\cdot B^{m}\left(1+O\left(\theta^{m}\right)\right),
  \qquad m=a\spn+b,~m\to\infty.$$
\end{theorem}

\noindent {\bf Remark.} Assumption~2 in Theorem~2 is a technical condition
which allows our proofs to work.
%enables us to apply the well-known Perron-Frobenius theorem (see
%Proposition~4 below) to the transfer matrix (see Definition~3 below)
%corresponding to the class $\SEQ(G; D)$.
It might be possible to relax this technical assumption.
%We also note that $A$ does not depend on $b$ whereas $B$ may depend on $b$.


\begin{corollary}\label{cor:local}
Assume the notation and conditions of Theorem~2. Let $H$ be the outdegree of $\eps_s$.
Suppose further that there are constants  $J$ and $K$ such that
\begin{enumerate}
  \item every recurrent vertex has outdegree $K$ in $D_{\sR}$, and
  \item every recurrent vertex is joined to $J$ vertices in $\SEQ_b(G)$.
\end{enumerate}
  Then Theorem~\ref{thm:local} holds with
\begin{equation}\label{cor1}
A=\frac{H\,J}{|G|K^{1+b/\spn}},~B=K^{1/\spn}.
\end{equation}
\end{corollary}

In the following we adopt the notation
$\displaystyle x^{\underline k}=x(x-1)\cdots (x-k+1).$

\begin{corollary}\label{cor:list}
Let $c_m (\bs)$ be the number of $m$-compositions of $\bs$ for each of the
following classes of compositions over $G$.
Then
  $$c_m(\bs)=A\cdot B^{m}\left(1+O\left(\theta^{m}\right)\right),
  \qquad m\to\infty,$$
where $A,B$ are given below.
\begin{enumerate}
  \item  For weak compositions such that there is no repeated part
    among any $d+1$ consecutive parts and $|G|\ge d+2$,  $$A=\frac{1}{|G|}|G|^{\underline d}(|G|-d)^{-d} ,~
   B=|G|-d.$$
  \item For compositions  such that there is no repeated part among
    any $d+1$ consecutive parts and $|G|\ge d+3$,  $$A=\frac{1}{|G|}(|G|-1)^{\underline d}(|G|-1-d)^{-d},~
   B=|G|-1-d.$$
  \item For weak compositions such that there is no repeated part
    among any $d+1$ consecutive parts and the first $d$ parts are nonzero, and
    $|G|\ge d+2$,
  $$A= \frac{1}{|G|}(|G|-1)^{\underline d}(|G|-d)^{-d},~B=|G|-d.$$
\item For weak compositions such that the sum of any $d$
    consecutive parts is nonzero and $|G|\ge 3, d\ge 2$,
   $$A=|G|^{d-2}(|G|-1)^{1-d},~
   B=|G|-1.$$
\item For compositions over $\fq$ such that the product of any $d$
    consecutive parts is not equal to $\bf 1$ and $q\ge 4, d\ge 2$,
   $$A=\frac{1}{q}(q-1)^{d-1}(q-2)^{1-d},~
   B=q-2.$$
\end{enumerate}
\end{corollary}

Next we give an example to which Corollary~\ref{cor:local} does not apply.

\begin{example}\label{exa:d3}
Consider the class of compositions over $G$ such that the sum of any three
consecutive parts is nonzero.
A corresponding restriction digraph $D$ is defined as follows.
The set $\sR$ consists of all ordered triples of nonzero elements of $G$
whose sum is nonzero.
We note that the sum of two consecutive parts might be
zero.
The vertex $\eps_s$ is joined to every vertex in $\sR$, and every
recurrent vertex is joined to the vertex $\eps$ in $\sT$.
A recurrent vertex
$\bu$ is joined to a vertex $\bv\in \sR\cup \SEQ_1(G^*) \cup \SEQ_2(G^*)$ if
the sum of any three consecutive parts in the concatenation $\bu\bv$ is
nonzero.
To compute the outdegree of each recurrent vertex, we need to distinguish two
cases.\\
Case~1: the recurrent vertex $\bu:=(u_1,u_2,u_3)$ where $u_1,u_2,u_3\ne {\bf
0}$ and $u_2+u_3={\bf 0}$.
Such a vertex is joined to a recurrent vertex
$\bv:=(v_1,v_2,v_3)$ if $v_1,v_2,v_3\ne {\bf 0}$, $u_3+v_1+v_2\ne {\bf 0}$ and
$v_1+v_2+v_3\ne {\bf 0}$.
The outdegree of $\bu$ in $\sR$ is equal to
\begin{align*}
&~|\{(v_1,-v_1,v_3):v_1,v_3\ne {\bf 0}\}|\\
&+|\{(v_1,v_2,v_3):v_1\ne {\bf 0};v_2\ne -v_1,-v_1-u_3,{\bf 0}; v_3\ne -v_1-v_2,{\bf 0} \}|\\
=& ~(|G|-1)^2+(|G|-1)(|G|-3)(|G|-2).
\end{align*}
The outdegree of $\bu$ in $\SEQ_1(G)$ is clearly equal to $|G|-1$.
The outdegree of $\bu$ in $\SEQ_2(G)$ is equal to
\begin{align*}
& |\{(-u_3,v_2):v_2\ne {\bf 0}\}|+|\{(v_1,v_2):v_1\ne -u_3,{\bf0};v_2\ne -v_1-u_3,{\bf 0},\}|\\
=& (|G|-1)+(|G|-2)^2.
\end{align*}
\noindent Case~2: the recurrent vertex $\bu:=(u_1,u_2,u_3)$ where
$u_1,u_2,u_3\ne {\bf 0}$ and $u_2+u_3\ne {\bf 0}$.
The outdegree of $\bu$ in $\sR$ is equal to
\begin{align*}
&~|\{(v_1,-v_1,v_3):v_1\ne -u_2-u_3,{\bf 0};v_3\ne {\bf 0}\}|\\
&+|\{(v_1,v_2,v_3):v_1\ne -u_2-u_3,{\bf 0};v_2\ne -v_1, -v_1-u_3,{\bf 0};v_3\ne -v_1-v_2,{\bf 0} \}|\\
=&~(|G|-2)(|G|-1)+(|G|-2)(|G|-3)(|G|-2).
\end{align*}
The outdegree of $\bu$ in $\SEQ_1(G)$ is clearly equal to $|G|-2$.
The outdegree of $\bu$ in $\SEQ_2(G)$ is equal to
\begin{align*}
& |\{(-u_3,v_2):v_2\ne {\bf 0}\}|+|\{(v_1,v_2):v_1\ne -u_3,-u_2-u_3,{\bf
  0};v_2\ne -u_3-v_1,{\bf 0}\}|\\
=& (|G|-1)+(|G|-3)(|G|-2).
\end{align*}

We show later that in fact Theorem~\ref{thm:local} can still apply to this
class.
\end{example}






\section{Propositions} \label{sec:propositions}

In this section we present results which are used to prove our main
theorems.

The following multivariate ``multisection formula'' might be known (the univariate case can be found in \cite[Ex.\ 1.1.9]{gold}), but we are unable to find a reference.
So we also include a proof.

For two vectors $\bz=(z_1,z_2,\ldots,z_r)$ and $\bn=(n_1,n_2,\ldots,n_r)$,  we
use $\bz^{\bn}$ to denote the product $\prod_{j=1}^rz_j^{n_j}$. In the rest of
the paper, we use the Iverson bracket $[P]$ which is equal to 1 if the
statement $P$ is true and 0 otherwise.
We also use $\om_k:=\exp(2\pi i/k)$ to denote the $k$\textsuperscript{th}
primitive root of unity which has the property
$$\sum_{j=0}^{k-1}\om_k^{sj}=k\left[s\equiv 0 \pmod k\right].$$

\begin{proposition}[Multivariate multisection formula]\label{prop:multisection}
Let $A(\bz)=\sum_{\bn}a_{\bn}\bz^{\bn}$ be a multivariate generating function,
where the indeterminate is $\bz:=(z_1,\ldots,z_r)$ and the sum is over all
$\bn:=(n_1,\ldots,n_r)$.
%Let  $\mathbf{k} = (k_1, \ldots, k_r)$ and $\bj = (j_1, \ldots, j_r)$ be $r$-tuples.
For any $\bs=(s_1,\ldots, s_r) \in G$, we have
$$\sum_{\bn\equiv\bs \pmod{\mathbf{k}}}
  a_{\bn}\bz^{\bn}=\left(\prod_{t=1}^r\frac{1}{k_t}\right)\sum_{\bj\in
  G}\left(\prod_{t=1}^r \om_{k_t}^{-j_ts_t}
  \right)A\left(z_1\om_{k_1}^{j_1},\ldots,z_r\om_{k_r}^{j_r}\right),$$
where $\om_{k_t} =\exp(2\pi i/k_t)$ is a  primitive $k_t$\textsuperscript{th}
root of unity for $1\leq t \leq r$.
\end{proposition}
\begin{proof}
 We have
\begin{align*}
&  \sum_{\bj\in
  G}\left(\prod_{t=1}^r \om_{k_t}^{-j_ts_t}
  \right)A\left(z_1\om_{k_1}^{j_1},\ldots,z_r\om_{k_r}^{j_r}\right)\\
  =&\sum_{\bn}a_{\bn}\bz^{\bn}\prod_{t=1}^{r}\sum_{j_t=0}^{k_t-1}
    \om_{k_t}^{j_t(n_t-s_t)} \\
  =&\sum_{\bn}a_{\bn}\bz^{\bn}\prod_{t=1}^{r}k_t\left[n_t\equiv s_t
    \pmod{k_t}\right]\\
  =&\prod_{t=1}^{r}k_t\sum_{\bn}a_{\bn}\bz^{\bn}\left[\bn\equiv \bs
    \pmod{\mathbf{k}}\right]. \qedhere
\end{align*}
\end{proof}


\begin{corollary} \label{cor:integer}
In this corollary compositions may be weak.
Fix some class $\mathcal{A} \subseteq \SEQ(G)$ of restricted compositions over
$G$.
For $\bs \in G$, let
  \[c_m(\bs) = \left|\{\mathbf{x}: \mathbf{x} = (\bx_1, \bx_2, \ldots, \bx_m)
  \in\mathcal{A}, |\mathbf{x}| \equiv \bs
  \pmod{\mathbf{k}}\}\right|.\]
For $\bn \in \mathbb{Z}_{\geq 0}^r$, we define the \emph{integer composition}
counting sequence
\[\hat{c}_m(\bn) = \left|\{\mathbf{x}: \mathbf{x} = (\bx_1, \bx_2, \ldots,
  \bx_m)\in\mathcal{A}, |\mathbf{x}| = \bn\}\right|,\]
and the generating function
\( \hat{C}_m(\bz) = \sum_{\bn} \hat{c}_m(\bn)\bz^\bn. \)
Then
\[
  c_m(\bs) =
\left(\prod_{t=1}^r\frac{1}{k_t}\right)\sum_{\bj\in
  G}\left(\prod_{t=1}^r \om_{k_t}^{-j_ts_t}
  \right)
  \hat{C}_m\left(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r}\right).
\]
\end{corollary}
\begin{proof}
Immediate from Proposition~\ref{prop:multisection}.
\end{proof}



\begin{example}[Unrestricted $m$-compositions over $G$]
The corresponding generating function for integer $m$-compositions
is
\[\hat{C}_m(\bz)=\left(\sum_{\bj\in
  G}\bz^{\bj}-1\right)^m=\left(\prod_{t=1}^r\sum_{j_t=0}^{k_t-1}z_t^{j_t}-1\right)^m
  = \left(\prod_{t=1}^r\frac{1-z_t^{k_t}}{1-z_t}-1\right)^m.
\]
It follows from Corollary~\ref{cor:integer} that the number of $m$-compositions
of $\bs$ over $G$ is
\begin{align*}
  c_m(\bs)
  &= \left(\prod_{t=1}^r\frac{1}{k_t}\right)\sum_{\bj\in
    G}\left(\prod_{t=1}^r\om_{k_t}^{-j_ts_t}\right)\hat{C}_m(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})\\
  &= \left(\prod_{t=1}^r\frac{1}{k_t}\right)\sum_{\bj\in
    G}\left(\prod_{t=1}^r\om_{k_t}^{-j_ts_t}\right)\left(\left[\bj={\bf
    0}\right]\prod_{t=1}^rk_t-1\right)^m\\
  &= \frac{1}{|G|}\left(\left(|G|-1\right)^m+(-1)^m
    \sum_{\bj\in G^*}\prod_{t=1}^r\om_{k_t}^{-j_ts_t}\right)\\
  &= \frac{1}{|G|}\left(\left(|G|-1\right)^m+(-1)^m
    \left(\prod_{t=1}^r\sum_{j_t=0}^{k_t-1}\om_{k_t}^{-j_ts_t}-1\right)\right)\\
  &= \frac{1}{|G|}\left(\left(|G|-1\right)^m+(-1)^m\left(\left[\bs={\bf
    0}\right]|G|-1\right)\right).
\end{align*}
Thus
\begin{align*}
  c_m(\bs) &= \frac{1}{|G|}\left(\left(|G|-1\right)^m-(-1)^m\right),~\hbox{ if }\bs\ne {\bf 0},\\
  c_m({\bf 0}) &=\frac{1}{|G|}
  \left(\left(|G|-1\right)^m+(-1)^m\left(|G|-1\right)\right).
\end{align*}
If $r=1$, this is the result given in \cite{MurWan}.
  We also note that $$c_m(\bs)\sim \frac{1}{|G|}\left(|G|-1\right)^m$$ for each
  $\bs \in G$  as $m\to \infty$, which agrees with the result given by
  Theorem~1.
\end{example}

\begin{example}[Unrestricted weak $m$-compositions over $G$]
The corresponding generating function for integer compositions is
$$\hat{C}_m(\bz)=\left(\prod_{t=1}^r\frac{1-z_t^{k_t}}{1-z_t}\right)^m.
$$
Applying Corollary~\ref{cor:integer}, we have
\begin{align*}
c_m(\bs) &= \left(\prod_{t=1}^r\frac{1}{k_t}\right)\sum_{\bj\in
    G}\left(\prod_{t=1}^r\om_{k_t}^{-j_ts_t}\right)\left(\prod_{t=1}^r\frac{1-\om_{k_t}^{j_tk_t}}{1-\om_{k_t}^{j_t}}\right)^m\\
  &= \left(\prod_{t=1}^r\frac{1}{k_t}\right)\sum_{\bj\in
    G}\left(\prod_{t=1}^r\om_{k_t}^{-j_ts_t}\right)\left(\left[\bj={\bf
    0}\right]\prod_{t=1}^rk_t\right)^m\\
  &= \left(\prod_{t=1}^r\frac{1}{k_t}\right)\left(\prod_{t=1}^rk_t\right)^m\\
  &= \left(\prod_{t=1}^rk_t\right)^{m-1}.
\end{align*}
This result can also be obtained by a direct counting argument: the first $m-1$
parts can be constructed in $\left(\prod_{t=1}^rk_t\right)^{m-1}$ ways, and the
last part is then uniquely determined by the equation
$\bx_1+\cdots+\bx_{m-1}+\bx_m = \bs$
in $G$.
\end{example}

\begin{example}
Let $c_m$ be the number of solutions to Equation (\ref{diagonal}). Let $y_j=a_jx_j^{d_j}$ and $S_j=\{a_jx_j^{d_j}:x_j\in \fp^*\}$.  Then $c_m$ is the number of $m$-compositions $y_1,\ldots,y_m$ of $a$
over $\fp$ such that $y_j\in S_j$. We have
$$|S_j|=|\{a_jx_j^{d_j}:x_j\in \fp\}|=|\{x_j^{d_j}:x_j\in \fp\}|=\frac{p-1}{\gcd(d_j, p-1)}.$$
  Viewing elements of $S_j, S_j-S_j$ as integers less than $p$,   the condition
\[\gcd \{ a_j s^{d_j}-a_j t^{d_j}: s,t\in \fp^*\}=1, \]
is satisfied when   $S_j - S_j$ contains two relatively prime integers.
\end{example}

\begin{definition}[Transfer matrix, weights, start and finish vectors]
  \label{def:transfer}
Let $\SEQ(G; D)$ be a class of locally restricted compositions from
Definition~\ref{def3}.
Fix an order on the vertices in $\sR$.
We define the \emph{transfer matrix} $T(\bz)$ as the square matrix whose rows
and columns are indexed by the vertices in $\sR$ such that
$T_{\bu,\bv}(\bz)=\bz^{|\bv|}$ if there is an arc from
$\bu$ to $\bv$, and $T_{\bu,\bv}(\bz)=0$  otherwise.
We say that $\bz^{|\bv|}$ is the \emph{weight} of an arc $(\bu,\bv)$.
The weight of a directed walk in $D$ is defined to be the product of the
weights of the arcs of the walk.
The \emph{start vector} $\start(\bz)$ is defined as the row vector whose
$j\textsuperscript{th}$ entry is the weight of the arc from $\eps_s$ to the
$j\textsuperscript{th}$ recurrent vertex (this entry is zero if such an arc
does not exist).
For each integer $0\le b<\si$, we define the \emph{finish vector}
$\term_b(\bz)$ as the column vector whose $j\textsuperscript{th}$ entry is the
sum of weights of all arcs from the $j\textsuperscript{th}$ recurrent vertex
to a vertex in $\SEQ_b(G)$.
\end{definition}



\begin{example}[Nonzero adjacent sum, continues Example \ref{exa:nonzero}]
For weak compositions, the transfer matrix $T(z)$ has
size $k\times k$ where $T_{i,j}(z)=z^j$ if $i+j\not\equiv 0 \pmod{k}$ and
$T_{i,j}(z)=0$ if $i+j \equiv 0 \pmod{k}$.
The start and finish vectors are, respectively,
$\start(z)=\rvect{1,z,\cdots,z^{k-1}}$ and $\term_0(z)=\rvect{1,1,\cdots,1}^\top$.
For example, if $k=3$, we have
\[
T(z)=\left[\begin{array}{cccc}
0&z&z^2\\
1&z&0\\
1&0&z^2
\end{array}\right],~\start(z)=\rvect{1,z,z^2},~\term_0(z)=\rvect{1,1,1}^\top.
%\qedhere
\]
\end{example}



Now we are ready to use the transfer matrix to enumerate locally restricted
compositions in $\SEQ(G;D)$.
\begin{proposition}\label{prop:local}
Let $m, \spn$ be positive integers and define integers $a,b$ such that
$m=a\spn +b$ where $0\leq b < \spn$.
Let $\bs=(s_1,\ldots, s_r)$ be a member of $G$ ($=\bigoplus_{j=1}^r \mZ_{k_j}$),
and let $\SEQ(G;D)$ be a class of locally restricted compositions with span
$\spn$.
As in Theorem~\ref{thm:local}, we let $c_m(\bs,D)$ denote the number of
$m$-compositions of $\bs$ in $\SEQ(G;D)$.
Let $T(\bz), \start(\bz), \term_b(\bz)$ be the corresponding transfer matrix,
start vector, and finish vector, and define
$$\hat{C}_m(\bz)=\start(\bz)T^{a-1}(\bz)\term_b(\bz).$$
Then we have
$$c_m(\bs,D)=\left(\prod_{t=1}^r\frac{1}{k_t}\right)\sum_{\bj\in
  G}\left(\prod_{t=1}^r \om_{k_t}^{-j_ts_t}
  \right)\hat{C}_m\left(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r}\right).$$
\end{proposition}
\begin{proof}
We note that the $(\bu,\bv)$ entry in $T(\bz)^{a-1}$ is the sum of weights of
all directed walks of length $a-1$ (that is, containing $a$ vertices) in $D_{\sR}$ from vertex $\bu$ to vertex $\bv$.
Since each vertex in $D_{\sR}$ is a sequence of parts from $G$ of length
$\spn$, it follows from the definition of $\start$ and $\term_b$ that
$\hat{C}_m(\bz)$ is the generating function of all directed walks
from $\eps_s$ to $\sT$ totaling $m=a\spn +b$ parts.
The result follows by applying Corollary~\ref{cor:integer}.
\end{proof}

\begin{example}[Carlitz compositions over $\Zk$, continues Example \ref{exa:carlweak}]
For Carlitz weak  compositions, it is clear that every recurrent vertex has
in-degree and out-degree equal to $k-1$ in $D_\sR$.
The transfer matrix $T(z)$ is given by $T_{i,i}(z)=0$ and $T_{i,j}(z)=z^j$ if
$i \ne j$.
The start and finish vectors are, respectively,
$\start(z)=\rvect{1,z,\cdots,z^{k-1}}$ and $\term_0(z)=\rvect{1,1,\cdots,1}^\top$.
So the generating function $\hat{C}_m(z)$
from Proposition~\ref{prop:local} for Carlitz weak
compositions is given by
$$\hat{C}_m(z)=\rvect{1,z,\cdots,z^{k-1}}T^{m-1}(z)\rvect{1,1,\cdots, 1}^\top,~~m\ge
  1.$$
For Carlitz compositions,
the transfer matrix $T(z)$ is obtained from the one above by
deleting row 1 and column 1.
The start and finish vectors are, respectively,
$\start(z)=\rvect{z,z^2, \cdots,z^{k-1}}$ and $\term_0(z)=\rvect{1,1,\cdots,1}^\top$.
This gives
\[
\hat{C}_m(z)=\rvect{z, z^2, \cdots,z^{k-1}}T^{m-1}(z)\rvect{1,1,\cdots,1}^\top,~~m\ge 1.
%\qedhere
\]
\end{example}

The following two propositions are used later to derive the asymptotic number
of compositions over $G$ from their generating functions.
Proposition~\ref{prop:aper} below shows that, under an aperiodicity condition,
a polynomial attains a unique maximum absolute value on the unit disc at $1$.
Its proof can be found in \cite[Lemma~1]{GaoWor99}.
Proposition~\ref{prop:eigen} is essentially the Perron-Frobenius theorem and its
proof can be found in \cite{BP}.

\begin{proposition}\label{prop:aper}
Let $F(z)=\sum_{j\ge 0}f_jz^j$ be a polynomial with nonnegative coefficients.
Define $J=\{j:f_j>0\}$.
Suppose $J$ is not empty and $\gcd \{j-k: j,k\in J\}=1$.  Then
$|F(z)|<F(1)$ for all $|z|\le 1,~z\ne 1$.
\end{proposition}

\begin{proposition}\label{prop:eigen}
Let $T(\bz)$ be a transfer matrix as in Definition~\ref{def:transfer},
and let $\rho(\bz)$ denote the spectral radius of $T(\bz)$.
Suppose the greatest common divisor of all directed cycle lengths of the
digraph $D_{\sR}$ is equal to $1$.
Then we have the following.
\begin{enumerate}
\item The value $\rho:=\rho({\bf1})$ is a simple eigenvalue of $T({\bf1})$ and
  the corresponding eigenspace is spanned by a positive vector.
\item All other eigenvalues of $T({\bf1})$ are smaller, in modulus, than
  $\rho$.
\item Suppose $|\bz|\ne 1, |z_t|\le 1$ for all $t$, and $T(\bz)\ne T({\bf 1})$.
  Then $\rho(\bz)<\rho$.
\end{enumerate}

\end{proposition}





\section{Proofs} \label{sec:proofs}

\begin{proof}[Proof of Theorem~\ref{thm:Subset}]
The generating function for integer compositions is
  $$\hat{C}_m(\bz)
  =\prod_{j=1}^m \sum_{\bn\in S_j}\bz^{\bn}
  =\prod_{j=1}^m\prod_{t=1}^r\sum_{n_t\in S_{t,j}}z_t^{n_t}.$$
We note $\hat{C}_m({\bf 1})=\prod_{j=1}^m|S_j|$.
%Let ${\bf g}=(g_1,\ldots,g_r)\in G$.
It follows from Corollary~\ref{cor:integer} that
\begin{align*}
  c(\bs;S_1,\ldots,S_m) &= \left(\prod_{t=1}^r\frac{1}{k_t}\right)\sum_{{\bf g}\in
    G}\left(\prod_{t=1}^r\om_{k_t}^{-g_ts_t}\right)
    \hat{C}_m(\om_{k_1}^{g_1},\ldots,\om_{k_r}^{g_r}) \\
  &= \frac{1}{|G|}\left( \prod_{j=1}^m |S_j| + \sum_{{\bf g}\in
    G^*}\left(\prod_{t=1}^r\om_{k_t}^{-g_ts_t}\right)
    \hat{C}_m(\om_{k_1}^{g_1},\ldots,\om_{k_r}^{g_r})\right).
\end{align*}

For a subset $A$ of $\mZ_{k_t}$,  define $P(z;A)=\sum_{a\in A}z^a$.
Let $\mathcal{I}:=\{A\subseteq \mZ_{k_t}: |P(z;A)|<|A| \hbox{ when  $|z|=1$ and
$z\ne 1$}\}$ and define $$\theta=\max
\left\{\frac{|P(\om_{k_t}^{g_t};A)|}{|A|}:1\le g_t\le k_t-1,1\le t\le r, A\in
\mathcal{I}\right\}.$$
Then $0\le \theta<1$. It follows from Proposition~\ref{prop:aper} that
$S_{t,j}\in \mathcal{I}$ and consequently $|P(z;S_{t,j})|<\theta|S_{t,j}|$.
Let $\mathbf{g}\in G$ satisfy $g_{t^*}>0$ for some $1\le t^*\le r$.
It follows that
\begin{align*}
  |\hat{C}_m(\om_{k_1}^{g_1},\ldots,\om_{k_r}^{g_r})|
   &=\left(\prod_{j=1}^m \left|\sum_{a\in S_{t^*,j}}\om_{k_{t^*}}^{ag_{t*}}\right|\right)\left(\prod_{t=1,t\ne t^*}^r\prod_{j=1}^m \left|\sum_{n_t\in S_{t,j}}\om_{k_t}^{n_tg_t}\right|\right) \\
   &=\left(\prod_{j=1}^m \left|P_{t^*,j}(\om_{k_{t^*}}^{g_{t*}})\right|\right)\left(\prod_{t=1,t\ne t^*}^r\prod_{j=1}^m \left|P_{t,j}(\om_{k_t}^{g_t})\right|\right) \\
  &<\left(\prod_{j=1}^m \theta |S_{t^*,j}|\right)\left(\prod_{t=1,t\ne t^*}^r\prod_{j=1}^m |S_{t,j}|\right) \\
  &= \theta^{m} \prod_{t=1}^r \prod_{j=1}^m |S_{t,j}| \\
  &= \theta^{m} \prod_{t=1}^r |S_t|.
\end{align*}
Now Theorem~1 follows immediately.
\end{proof}


\begin{proof}[Proof of Theorem~\ref{thm:local}]
As in Proposition~\ref{prop:eigen}, let $T(\bz)$ be the transfer matrix
of $\SEQ(G; D)$
and define $\rho(\bz)$ to be the absolute value of the dominant eigenvalue of
$T(\bz)$.
We abbreviate $\rho(\mathbf{1})$ simply as $\rho$.
Define
\begin{align*}
\theta_1 &= \max \left\{ \frac{|\lambda|}{\rho}: \lambda \hbox{ is any
    eigenvalue of $T({\bf1})$ other than } \rho \right\},\\
\theta_2 &= \max  \left\{\frac{\rho(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})}{\rho} : 0\le
    j_t\le k_t-1,\, 1\le t\le r, {\bf j}\ne {\bf 0} \right\}.
\end{align*}
It follows from item~2 of Proposition~\ref{prop:eigen} that
$0\le\theta_1<1$.
 Recall that the $(\bu,\bv)$-entry of $T^{\ell}(\bz)$, denoted by
 $\left(T^{\ell}(\bz)\right)_{\bu,\bv}$, is equal to the sum of the weights of
 all directed walks from vertex $\bu$ to vertex $\bv$ of length $\ell$.
 Let ${\bf j}=(j_1,\ldots,j_r)$ satisfy $0\le j_i\le k_i-1$ and $j_t\ne 0$
 for some $1\le t\le r$. Let $\sW_{\sR}$ be the set of directed walks given in
 condition~2.
Dividing the set of all directed walks of length $\ell$ from $\bu$ to $\bv$
into $\sW_{\sR}$ and its complement ${\bar \sW_{\sR}}$,  we obtain
\begin{align*}
  &\left|\left(T^{\ell}(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})
    \right)_{\bu,\bv}\right|\\
  \le &  \left|\sum_{W\in
    \sW_{\sR}}\prod_{i=1}^r\om_{k_i}^{j_i(v_i+\sum_{h=1}^{\ell-1}u_{i,h})}\right|+\left|\sum_{W\in
    {\bar
    \sW_{\sR}}}\prod_{i=1}^r\om_{k_i}^{j_i(v_i+\sum_{h=1}^{\ell-1}u_{i,h})}\right|\\
 \le& \left|\prod_{i=1,i\ne
   t}^r\om_{k_i}^{j_i(v_i+\sum_{h=1}^{\ell-1}\phi_{i,h})}\right|\left|\om_{k_t}^{j_tv_t}
   \right|  \left|\sum_{W\in
    \sW_{\sR}}\om_{k_t}^{j_t\sum_{j=1}^{\ell-1}u_{t,j}}\right|+\sum_{W\in
      {\bar \sW_{\sR}}}1\\
  \le & \left|\sum_{W\in
    \sW_{\sR}}\om_{k_t}^{j_t\sum_{h=1}^{\ell-1}u_{t,h}}\right|+\sum_{W\in
      {\bar \sW_{\sR}}}1.
\end{align*}
Applying condition~2 and Proposition~\ref{prop:aper}, we obtain
 $$\left|\sum_{W\in \sW_{\sR}}\om_{k_t}^{j_t\sum_{h=1}^{\ell-1}u_{t,h}}\right|<
 \sum_{W\in \sW_{\sR}}1.$$
 It follows that
 $$\left|\left(T^{\ell}(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})
    \right)_{\bu,\bv}\right| <\sum_{W\in \sW_{\sR}}1+\sum_{W\in
      {\bar \sW_{\sR}}}1= \left(T^{\ell}({\bf1})\right)_{\bu,\bv}.$$
Applying item~3 of Proposition~\ref{prop:eigen} to the matrix
$T^{\ell}\left((\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})\right)$, we obtain
$$\rho(T(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r}))^{\ell}<\rho(T({\bf
      1}))^{\ell},$$
and hence
$0\le \theta_2<1$.

Using the Jordan normal form of
$T(\bz)$, it is easy to see that, for each $\bz=(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})$ with $(j_1,\ldots,j_r) \ne (0,\ldots,0)$, all entries of $T^{a-1}(\bz)$ are of the order $O\left(a^N\rho^a\theta_2^a\right)$, where $N$ is the size of $T(\bz)$. Since $N$ is fixed (i.e., independent of $m$ or $a$), it follows that, for $(j_1,\ldots,j_r) \ne (0,\ldots,0)$,
$$
\hat{C}_m(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})
 = \start(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})
    T^{a-1}(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})
    \term_b(\om_{k_1}^{j_1},\ldots,\om_{k_r}^{j_r})
  = O\left(a^N\theta_2^a\right)\rho^{a}.
$$
Next we estimate $\hat{C}_m({\bf1})$. By Proposition~4(1), $\rho$ is a simple eigenvalue of $T({\bf 1})$ (and  $T^{\top}({\bf 1})$), so we may write the Jordan normal form of  $T({\bf 1})$ in the following block form
$$T({\bf 1})=[\bg~ L]\left[\begin{array}{cc}\rho&{\bf 0}\\{\bf 0}&\Lambda \end{array}\right]\left[\begin{array}{c}\bh\\H\end{array}\right]$$
  such that $\bg$ is a positive eigenvector of $T({\bf 1})$ corresponding to $\rho$,  $\bh^{\top}$ is a positive eigenvector of $T^{\top}({\bf1})$
corresponding to $\rho$,  the matrix $\Lambda$ corresponds to other eigenvalues of $T({\bf 1})$ which are all smaller, in absolute value, than $\rho$, and the matrix $\displaystyle \left[\begin{array}{c}\bh\\H\end{array}\right]$ is the inverse of
$[\bg~ L]$.

Since all entries of $\Lambda^{a-1}$ are of the order $O\left(a^N\rho^a\theta_1^a\right)$, it follows that
\begin{align*}
  \qquad  \hat{C}_m({\bf1})
 &= \start({\bf1})T^{a-1}({\bf1})\term_b({\bf1})\\
  &= (\start({\bf1})\cdot\bg)
    (\bh \cdot\term_b({\bf1}))\rho^{a-1}+
    \start({\bf1})L\Lambda^{a-1}H\term_b({\bf1})\\
&= (\start({\bf1})\cdot\bg)
    (\bh \cdot\term_b({\bf1}))\rho^{a-1}+ O\left(a^N\rho^a\theta_1^a\right).
\end{align*}
Since there is at least one arc from $\eps_s$ to $\sR$ and at least one arc
from $\sR$ to $\SEQ_b(G)$, both $\start({\bf1})$ and $\term_b({\bf1})$ are
non-negative vectors with at least one positive entry. Consequently both $\start({\bf1})\cdot\bg$ and
    $\bh \cdot\term_b({\bf1}))$ are positive.
Now Theorem~2 follows from Proposition~\ref{prop:local} with $\theta$ being any constant satisfying
$\max\{\theta_1^{1/\spn},\theta_2^{1/\spn}\}<\theta<1$, and
\[
A=\frac{1}{|G|}(\start({\bf 1})\cdot\bg)
    (\bh \cdot\term_b({\bf1}))\rho^{-1-b/\spn},~
    B=\rho^{1/\spn}.
\qedhere \]
\end{proof}


\begin{example}[Continues Example \ref{exa:d3}]
We again consider the class of compositions over $G$ such that the sum of any
three consecutive parts is nonzero.
To make matrices as convenient as possible, we use a span of $\spn=2$.
We specialize to the case $G = \mathbb{Z}_k$, where $k \geq 4$.
An argument similar to that used below in the proof of Corollary~2 Part~4 shows that $D_{\sR}$ is
 strongly connected.
The first condition of Theorem~\ref{thm:local} is satisfied by the loop at the vertex $(1,1)$.
The second condition is satisfied by setting $\mathcal{W}_\mathcal{R}$ to
contain the walks
$(1,1), (1,k-1), (2,1), (k-1,1), (k-1,k-1)$ and
$(1,1), (1,k-1), (2,2), (k-1,1), (k-1,k-1)$.

We further specialize, taking $k=4$,
and in this case, with the help of the Computer Algebra System {\em MAPLE}, we can apply Proposition~2 to derive
an exact formula as well as a simple approximation formula for $c_m(\bs)$.
The elements of $\sR$ are
$(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)$.
Using this ordering, we get

{\footnotesize
\begin{align*}
\start(z) &= \rvect{z^2, z^3, z^4, z^3, z^4, z^5, z^4, z^5, z^6}\\
\term_0(z) &= \rvect{1,1,1,1,1,1,1,1,1}^\top \\
\term_1(z) &=  \begin{bmatrix} z + z^3& z^2 + z^3& z + z^2 + z^3& z^2 + z^3& z
  + z^2 + z^3 & z + z^2& z + z^2 + z^3& z + z^2& z + z^3  \end{bmatrix}^\top \\
\end{align*}}
%   \end{matrix} \\
%&\qquad\qquad \begin{matrix} z + z^2& z + z^2 + z^3& z + z^2& z + z^3
%  \end{bmatrix}^\top \\
\begin{align*}
T(z) &= \begin{bmatrix}
 z^2 & 0 & z^4 & 0 & 0 & 0 & z^4 & z^5 & z^6 \\
 0 & 0 & 0 & z^3 & z^4 & z^5 & z^4 & z^5 & 0 \\
 z^2 & z^3 & z^4 & z^3 & z^4 & 0 & z^4 & 0 & z^6 \\
 0 & 0 & 0 & 0 & z^4 & z^5 & z^4 & z^5 & z^6 \\
 0 & z^3 & z^4 & z^3 & z^4 & z^5 & z^4 & z^5 & 0 \\
 z^2 & z^3 & z^4 & z^3 & z^4 & 0 & 0 & 0 & 0 \\
 z^2 & 0 & z^4 & 0 & z^4 & z^5 & z^4 & z^5 & z^6 \\
 0 & z^3 & z^4 & z^3 & z^4 & z^5 & 0 & 0 & 0 \\
 z^2 & z^3 & z^4 & 0 & 0 & 0 & z^4 & 0 & z^6 \\
\end{bmatrix}
\end{align*}


Using {\em MAPLE},  we find that the four matrices $T(1),T(-1),T(i),T(-i)$
 are all diagonlizable and
\begin{align*}
\hC_m(1)&=\frac{3}{2}(1+\sqrt{2})^m+\frac{3}{2}(1-\sqrt{2})^m,\\
\hC_m(-1)&=\hC_m(i)=\hC_m(-i)\\
&=(-1)^mf(r_1)r_1^{m/2}+f(r_2)r_2^{m/2}+(-1)^mf(r_3)r_3^{m/2}+2\Re\left(f(r_4)r_4^{m/2}\right),
\end{align*}
where
$$
f(r)=\frac{r^3-5r^2+6r-1}{r(4r^4-11r^3-13r^2-19r+17)},
$$
$r_1\doteq 3.848862156$, $r_2\doteq 0.4736256091$,  $r_3\doteq 0.3639455409$,  and $r_4\doteq -0.8432166528+0.892341334i$
 are eigenvalues of $T(-1),T(i), T(-i)$ satisfying
\[r^5-3r^4-3r^3-2r^2+4r-1=0.\]
It follows from Proposition~2 that
\begin{align*}
c_m(0)&= \frac{3}{8} (1 + \sqrt{2})^m+\frac{3}{8} (1 - \sqrt{2})^m+\frac{3}{4}(-1)^mf(r_1)r_1^{m/2}+\frac{3}{4}f(r_2)r_2^{m/2}\\
&+\frac{3}{4}(-1)^mf(r_3)r_3^{m/2}+\frac{3}{2}\Re\left(f(r_4)r_4^{m/2}\right)\\
&= \frac{3}{8} (1 + \sqrt{2})^m+\frac{3}{4}(-1)^mf(r_1)r_1^{m/2}+\frac{3}{2}\Re\left(f(r_4)r_4^{m/2}\right)+O\left(r_2^{m/2}\right),\\
c_m(1)&=c_m(2)=c_m(3)\\
&= \frac{3}{8} (1 + \sqrt{2})^m+\frac{3}{8} (1 - \sqrt{2})^m-\frac{1}{4}(-1)^mf(r_1)r_1^{m/2}-\frac{1}{4}f(r_2)r_2^{m/2}\\
&-\frac{1}{4}(-1)^mf(r_3)r_3^{m/2}-\frac{1}{2}\Re\left(f(r_4)r_4^{m/2}\right)\\
&= \frac{3}{8} (1 + \sqrt{2})^m-\frac{1}{4}(-1)^mf(r_1)r_1^{m/2}-\frac{1}{2}\Re\left(f(r_4)r_4^{m/2}\right)+O\left(r_2^{m/2}\right).
\end{align*}
Table~\ref{tab:asympt} shows numerical values for relevant sequences, where
$$a_m(0)= \frac{3}{8} (1 + \sqrt{2})^{m}+\frac{3}{4}(-1)^mf(r_1)r_1^{m/2}+
\frac{3}{2}\Re\left(f(r_2)r_2^{m/2}\right)$$ is evaluated up to one decimal
place.

\begin{table}[ht]
\centering
\begin{tabular}[c]{|cccc|}
\hline
$m$ & $c_m(1)$& $c_m(0)$ & $a_m(0)$ \\ \hline
2 &  2&3 & 2.7 \\
3 & 7&0 & -0.1 \\
4 & 10&21 & 20.8 \\
5 & 35&18 & 17.9 \\
6 &64& 105 & 104.9 \\
7 & 199&120 & 119.9 \\
8 & 396&543 & 542.9 \\
9 &1119& 822 & 821.9 \\
10 &2376& 2961 & 2960.9 \\
11 & 6373&5238 & 5237.9 \\
12 & 14142&16377 & 16376.9 \\
13 & 36589&32196 & 32195.9 \\
14 & 83532&92133 & 92132.9 \\
15 &211075& 194196 & 194195.9 \\
16 & 491110&524241 & 524240.9 \\
17 &1221885& 1156908 & 1156908.0 \\
18 & 2878806&3006279 & 3006279.0 \\
19 & 7089517&6839406 & 6839406.0 \\
20 & 16841988&17332647 & 17332647.0 \\
21 & 41196941&40234356 &40234356.0\\\hline
\end{tabular}
\caption{Values of $c_m(1)$, $c_m(0)$ and $a_m(0)$ from Example~\ref{exa:d3}. }
\label{tab:asympt}
\end{table}
\end{example}


\begin{proof}[Proof of Corollary~\ref{cor:local}]
We first note that the matrix $T({\bf 1})$ is a 0-1 matrix. Condition~1 implies
that each row of $T({\bf 1})$ contains exactly $K$ 1's.
Hence the dominant eigenvalue of
$T({\bf 1})$ is $\rho=K$ and $\rvect{1,1,\cdots, 1}^{\top}$ is a corresponding eigenvector.
Conditions~2 and 3 imply that $\start({\bf 1})$ contains exactly $H$ 1's and
$\term_b({\bf 1})=J\rvect{1,1,\cdots, 1}^{\top}$. Since $\term_b({\bf 1})$ is an eigenvector of $T({\bf 1})$ corresponding to the dominant eigenvalue $\rho$, $\hat{C}_m({\bf 1})$ can be evaluated exactly without using the Jordan normal form. And we have
\[\hat{C}_m({\bf 1})=\start({\bf1})T^{a-1}({\bf 1})\term_b({\bf
1})=\start({\bf1})K^{a-1}J\rvect{1,1,\cdots, 1}^{\top}=H\cdot J\cdot  K^{a-1},
\]
where we used the fact $H=\start({\bf1})\rvect{1,1,\cdots, 1}^{\top}$.
This establishes (\ref{cor1}).
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:list}]
We first define the digraph $D$ for each class and compute the values of $H,J$
and $K$.
For Part~1, we let $\sR$ be the set of all $(d+1)$-tuples of distinct elements
of $G$.
Hence $\spn=d+1$ and  $|\sR|=|G|^{\underline {d+1}}$.
The vertex $\eps_s$ is joined to all recurrent vertices and so
$H=|G|^{\underline {d+1}}$.
A recurrent vertex $\bu=(u_1,u_2,\ldots,u_{d+1})$ is joined to a recurrent
vertex $\bv=(v_1,v_2,\ldots,v_{d+1})$  if $v_j$ is different from
$v_1,\ldots, v_{j-1},u_{j+1},\ldots, u_{d+1}$ for each $1\le j\le d+1$.
Hence $\bu$ is joined to  $K=(|G|-d)^{d+1}$ recurrent vertices.
Similarly $\bu\in \sR$ is joined to a vertex $\bv=(v_1,v_2,\ldots,v_b)$ if
$v_j$ is different from $v_1,\ldots, v_{j-1},u_{j+1},\ldots, u_{d+1}$ for each
$1\le j\le b$.
Hence $J=(|G|-d)^b$.


For Part~2, we let $\sR$ be the set of all $(d+1)$-tuples of distinct elements
of $G^*$. So the remaining argument is exactly the same as for Part~1 with $G$
being replaced by $G^*$.


For Part~3,  the corresponding digraph $D$ is defined
as in Part~1 except
that there is an arc from $\eps_s$ to a vertex $\bv\in \sR$ only if the first
$d$ parts of $\bv$ are all nonzero.
Thus we have $\spn=d+1$,
$J=(|G|-d)^{b}$, $K=(|G|-d)^{d+1}$, and $H=(|G|-1)^{\underline d}(|G|-d)$.

For Part~4, we let
$\sR=\{(u_1,\ldots,u_d): u_j\in G,\sum_{j=1}^du_j\ne {\bf 0}\}$.
So we have $\spn=d$.
We note that for every choice of $(u_1,\ldots,u_{d-1})$, there are $|G|-1$
choices of $u_d$ such that the total sum is nonzero (we need the assumption
$d\ge 2$ here).
Hence $|\sR|=(|G|-1)|G|^{d-1}$.
The vertex $\eps_s$ is joined to all recurrent vertices and so
$H=(|G|-1)|G|^{d-1}$.
A recurrent vertex $\bu=(u_1,u_2,\ldots,u_{d})$ is joined to a vertex
$\bv=(v_1,v_2,\ldots,v_k)\in \sR\cup \SEQ_b(G)$ if $v_1+\cdots
+v_{j}+u_{j+1}+\cdots +u_d$ is not zero for each $1\le j\le k$.
Hence $K=(|G|-1)^{d}$ and $J=(|G|-1)^b$.


For Part~5, we take $\sR$ to be the set of all $d$-tuples $x_1,\ldots,x_d$ of
nonzero elements of $\mathbb{F}_q$ such that $x_d \neq (x_1 \cdots
x_{d-1})^{-1}$.
If $q=p^n$, each field element is represented as an $n$-tuple over $\Zp$.
This gives $\sigma = d$ and $H = |\sR| = (q-1)^{d-1}(q-2)$.
We have $K = (q-2)^d$ since to join $x_1,\ldots,x_d$ to $y_1,\ldots,y_d$,
each $y_i$ is constrained to be nonzero and not the multiplicative inverse
of the previous $d-1$ parts.
Similarly, $J = (q-2)^b$.\\

Next we verify that the digraph $D_{\sR}$ is strongly connected by showing that
there is a directed walk from any recurrent vertex  to any other recurrent
vertex.

For Part~1, Let ${\bf b}=(b_1,b_2,\ldots,b_{d+1})$ and ${\bf a}=(a_1,a_2,\ldots,a_{d+1})$ be any two distinct recurrent vertices.
Let $j$ be the smallest integer such that $a_{j+1}\ne b_{j+1}$. Thus we can write ${\bf a}=(b_1,\ldots,b_j,a_{j+1},\ldots,a_{d+1})$,
 where $0\le j\le d$ and $a_{j+1}\ne b_{j+1}$. We use induction on $d-j$ to show that there is a directed walk from $\bf b$ to $\bf a$. The basis case $j=d$ is obvious
 since ${\bf b}$ is joined to $\bf a$. Now we move to the inductive step by finding a recurrent vertex $(b_1,\ldots,b_j,b_{j+1},x_{j+2},\ldots,x_{d+1})$
which is joined to $\bf a$.  If $b_{j+1}\notin \{a_{j+2},\ldots,a_{d+1}\}$, then $(b_1,\ldots,b_j,b_{j+1},a_{j+2},\ldots,a_{d+1})$ is joined to $\bf a$.
If $b_{j+1}=a_k$ for some $k\in\{j+2,\ldots, d+1\}$, then for any $y\notin \{b_1,\ldots,b_{j+1},a_{j+1},\ldots,a_{d+1}\}$, it is easy to check that
$(b_1,\ldots,b_j,b_{j+1},a_{j+2},\ldots,a_{k-1},y,a_{k+1},\ldots,a_{d+1})$ is joined to $\bf a$.

The argument for Parts~2 and 3 is similar to above.

For Part~4, we show that there is a directed walk from a recurrent vertex ${\bf b}=(b_1,b_2,\ldots,b_{d})$ to another recurrent vertex
${\bf a}=(b_1,\ldots,b_j,a_{j+1},\ldots,a_{d})$ using induction on $d-j$ as for Part~1. When $j=d-1$, it is clear that $\bf b$ is joined to $\bf a$.
For the inductive step, let $y\in G$ satisfy
\begin{align*}
y+(b_1+\cdots+b_{j+1}+a_{j+3}+\cdots+a_d)&\ne 0,\\
y+(b_1+\cdots+b_j+a_{j+1}+a_{j+3}+\cdots+a_d)&\ne 0.
\end{align*}
Then it is easy to check that $(b_1,\ldots,b_j,b_{j+1},y,a_{j+3},\ldots,a_d)$ is joined to $\bf a$.

The argument for Part~5 is similar to that for Part~4.\\

Finally we verify the two conditions in Theorem~\ref{thm:local} for
the five classes of compositions.
The verification proceeds as follows.
For each $1\le t\le r$, we
find two distinct recurrent vertices $\bu=(u_1,u_2,\ldots,u_{\spn})$ and
$\bv=(v_1,v_2,\ldots,v_{\spn})$ such that $\bu$ is joined to itself and to
$\bv$, $\bv$ is joined to itself, and $|\bv|-|\bu|={\bf e}_t$ where
${\bf e}_t$ is the $t$\textsuperscript{th} unit vector of dimension $r$.
Hence condition~1 is satisfied because of the loop at $\bu$, and
$\sW_{\sR}=\{\bu\bu\bv,\bu\bv\bv\}$ is a set
of directed walks of length 2 from $\bu$ to $\bv$ which satisfies condition~2.

For Part~1, we choose $d$ distinct elements $u_1,\ldots,u_d$ from $G\setminus
\{{\bf0},{\bf e}_t\}$ and let $\bu=(u_1,\ldots,u_d,\mathbf{0})$ and
$\bv=(u_1,\ldots,u_d,{\bf e}_t)$.
It is easy to see that there are $(|G|-2)^{\underline d}>0$ choices of
$u_1,\ldots,u_d$.


For Part~2, we distinguish two cases.
If $r=1$, then $G=\mZ_k$ for some $k\ge d+3$.
In this case we simply let
$\bu=(3,4,\ldots,d+2,1)$ and $\bv=(3,4,\ldots,d+2,2)$.
If $r\ge 2$, we let $t$ and $t'$ be two distinct integers in
$\{1,2,\ldots,r\}$.
We then choose $d$ distinct elements $u_1,\ldots,u_d$ from
$G\setminus \{{\bf 0},{\bf e}_{t'},{\bf e}_{t'}+{\bf e}_t\}$ and let
$\bu=(u_1,\ldots,u_d,{\bf e}_{t'})$ and
$\bv=(u_1,\ldots,u_d,{\bf e}_{t'}+{\bf e}_t)$.
It is clear that there are $(|G|-3)^{\underline d}>0$ choices of
$u_1,\ldots,u_d$.

For Part~3, we may use the same $\bu$ and $\bv$ as in Part~1.

For Part~4, again we discuss two cases.
The case $G=\mZ_k$ is treated as in Part~2.
If $r\ge 2$, we let $t$ and $t'$ be two distinct integers in
$\{1,2,\ldots,r\}$, and choose $d-1$ elements $u_1,\ldots,u_{d-1}$ from $G$
such that $u_1+\ldots+u_{d-1}+{\bf e}_{t'}\ne {\bf 0}$ and
$u_1+\ldots+u_{d-1}+{\bf e}_{t'}+{\bf e}_{t}\ne {\bf0}$.
We then let
$\bu:=(u_1,\ldots,u_{d-1},{\bf e}_{t'}), \bv:=(u_1,\ldots,u_{d-1},{\bf
e}_{t'}+{\bf e}_t)$.
There are $(|G|-2)|G|^{d-2}$ choices of $u_1,\ldots,u_{d-1}$.

Part~5 is handled in a similar manner to Part~4.
\end{proof}


\section{Bijections and exact values}\label{sec:biject}
Here we first provide numerical values for the number of locally Mullen
compositions and Carlitz compositions.
Table~\ref{tab:2mul} shows initial values of $c_m(\bs)$ for locally 2-Mullen
compositions;
Table~\ref{tab:w3car} is similar for 2-Carlitz weak compositions; and
Table~\ref{tab:3car} is similar for 2-Carlitz compositions.

\begin{table}
\centering
\begin{tabular}[c]{|c|cccccccccc|}
\hline
\diagbox{$s$}{$m$} & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ \\ \hline
0 & 0 & 0 & 12 & 24 & 48 & 204 & 624 & 1680 & 5196 & 16008 \\
1 & 1 & 3 & 6 & 21 & 69 & 192 & 573 & 1767 & 5262 & 15681 \\\hline
%2 & 1 & 3 & 6 & 21 & 69 & 192 & 573 & 1767 \\
%3 & 1 & 3 & 6 & 21 & 69 & 192 & 573 & 1767 \\
%4 & 1 & 3 & 6 & 21 & 69 & 192 & 573 & 1767 \\\hline
\end{tabular}
\caption{Counts of locally 2-Mullen compositions over $\mathbb{Z}_5$.}
\label{tab:2mul}
\end{table}

\begin{table}
\centering
\begin{tabular}[c]{|c|ccccccccc|}
\hline
\diagbox{$s$}{$m$} & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$\\ \hline
0 & 4 & 24 & 88 & 320 & 1248 & 5120 & 20728 & 82284 & 326296 \\
1 & 6 & 18 & 72 & 320 & 1284 & 5120 & 20232 & 81738 & 329064 \\
2 & 4 & 18 & 88 & 320 & 1236 & 5120 & 20728 & 81738 & 326296 \\
3 & 6 & 24 & 72 & 320 & 1392 & 5120 & 20232 & 82284 & 329064 \\
4 & 4 & 18 & 88 & 320 & 1236 & 5120 & 20728 & 81738 & 326296 \\
5 & 6 & 18 & 72 & 320 & 1284 & 5120 & 20232 & 81738 & 329064 \\\hline
\end{tabular}
\caption{Counts of 2-Carlitz weak compositions over $\mathbb{Z}_6$.}
\label{tab:w3car}
\end{table}

\begin{table}
\centering
\begin{tabular}[c]{|c|ccccccccc|}
\hline
\diagbox{$s$}{$m$} & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$\\ \hline
0 & 4 & 12 & 32 & 80  & 280 & 812 & 2572 & 6644 & 23460 \\
1 & 4 & 6  & 34 & 82  & 284 & 748 & 2498 & 7372 & 21522 \\
2 & 2 & 12 & 32 & 80  & 274 & 866 & 2266 & 7484 & 21642 \\
3 & 4 & 12 & 16 & 136 & 224 & 820 & 2480 & 7384 & 21432 \\
4 & 2 & 12 & 32 & 80  & 274 & 866 & 2266 & 7484 & 21642 \\
5 & 4 & 6  & 34 & 82  & 284 & 748 & 2498 & 7372 & 21522 \\\hline
\end{tabular}
\caption{Counts of 2-Carlitz compositions over $\mathbb{Z}_6$.}
\label{tab:3car}
\end{table}

Next we give bijections between different families of compositions.
The following observation establishes a connection between Carlitz compositions
and  locally $d$-Mullen compositions.

\begin{proposition}\label{prop:bijection}
For each  $m$-composition $\bu=u_1,u_2,\ldots,u_m$ over $G$, let
$\bv=\phi(\bu)$ be an $m$-composition defined by $v_j=u_1+\ldots +u_j, 1\le
j\le m$.
Then $\phi$ is a bijection between locally $d$-Mullen $m$-compositions and
$d$-Carlitz weak $m$-compositions over $G$ such that the first $d$ parts are
nonzero.
\end{proposition}

\begin{proof}
It follows from the definition of the mapping $\phi$ that
$v_{i+j}=v_i+(u_{i+1}+\ldots+u_{i+j})$. It is clear that $v_i\ne v_{i+j}$ if and
only if $u_{i+1}+\ldots+u_{i+j}\ne 0$. It is important to note that $v_k$ might be
zero when $k>d$, however
$v_k\ne 0$ when $1\le k\le d$ when $\bu$ is locally $d$-Mullen.
Also $\bu$ and $\bv$ generally do not have the same sum.
\end{proof}

Using Corollary~2 Part~3 and the above proposition, we immediately obtain
the following.
\begin{theorem}\label{theorem:locallyMullen}
Let $G$ be a finite abelian group, and $d$ be a positive integer such that
$|G|\ge d+1$. Let $c_m(\bs)$ be the number of locally $d$-Mullen
$m$-compositions of $\bs\in G$. Then there is a positive constant $\theta<1$
such that
$$c_m(\bs)=\frac{1}{|G|}(|G|-1)^{\underline d}~(|G|-d)^{m-d}\left(1+O(\theta^m)\right),\hbox{ as }m\to \infty.$$
\end{theorem}

\begin{proposition}\label{prop:mullen}

\begin{itemize}
\item[1.] Let $\cal A$ be a family of compositions over a finite
abelian group $G$. Suppose $\cal A$ is closed under multiplication, that is,
if ${\bf x}:=(x_1,\ldots,x_m)$ belongs to $\cal A$ then $a{\bf
x}:=(ax_1,\ldots,ax_m)$ also belongs to $\cal A$ for every $a\in G^*$.
Let  $c_m(\bs; {\cal A})$ be the number of $m$-compositions of $\bs$ in $\cal
A$.
If $\bs\in G^*$ has a multiplicative inverse $\bs^{-1}$ in $G^*$, then
$c_m(\bs;{\cal A})=c_m({\bf 1}; {\cal A})$.
\item[2] Let $c_m(\bs)$ be the number of locally $d$-Mullen $m$-compositions of
$\bs \in G$.
Then $c_m(\bs) = c_m({\bf 1})$ for every $\bs \in G^*$.
\end{itemize}
\end{proposition}


\begin{proof}
1. It is clear that ${\bf x}\mapsto \bs^{-1}{\bf x}$ is a bijection between
compositions of $\bs$ and compositions of $\bf 1$ in $\cal A$.  \\
2.  The claim follows from Part~1 if $\bs^{-1}$ exists. For general $\bs\in G^*$, let
$\pi$ be a permutation of $G$ such that $\pi(\bs)={\bf 1}$ and $\pi({\bf
0})={\bf 0}$.
Then  it is easy to verify that  $\phi\pi\phi^{-1}$
is a bijection from locally $d$-Mullen $m$-compositions of $\bs$ to those of
${\bf 1}$.
\end{proof}

{\bf Remark.} The above proposition implies that the number of Carlitz
$m$-compositions of $s$ over a finite field is equal to that of 1 when $s\ne
0$. And the same is true for Carlitz weak compositions.







\section{Conclusion} \label{sec:conclusion}

The structure of finite abelian groups naturally leads us to use
Corollary~\ref{cor:integer} to go from a generating function for restricted
integer compositions to the number of restricted compositions over group
elements.
Assuming some aperiodicity conditions, asymptotic analysis of this expression
gives us the dominant term, as the number of parts goes to infinity.
Exact counts are available as well, by taking powers of the transfer matrix.
A couple of potential extensions to this work are apparent.
It would be interesting to get analogous asymptotic counting results for
non-abelian groups.
A similar level of generality is unlikely but one could be curious about what
techniques are necessary to generalize at least somewhat beyond the restriction
of commutativity.
It may also be interesting to consider further types of restriction such as
pattern avoidance.


\subsection*{Acknowledgements}
We thank E.\ A.\ Bender for indicating that our results
apply to general finite abelian groups not merely to finite fields.








% https://tex.stackexchange.com/questions/52368/how-can-i-insert-by-bib-file-into-my-tex-file/52370
{%\baselineskip 12pt \frenchspacing \footnotesize

\begin{thebibliography}{99}


\bibitem{Baoulina10}   I. N. Baoulina, On the number of solutions to certain diagonal equations over finite fields, {\it Int. J. Number Theory} {\bf 6} (2010), 1-14.


\bibitem{Baoulina16}  I. N. Baoulina, On a class of diagonal equations over finite field, {\it Finite Fields App.} {\bf 40} (2016) 201-223.


\bibitem{BC09} E. A. Bender and E. R. Canfield, Locally restricted compositions II.
General restrictions and infinite matrices, {\it Elec. J. Combin.}
{\bf 16} (2009) \#R108, 35pp.

\bibitem{BG16} E. A. Bender and Z. Gao, Locally restricted sequential
structures and runs in compositions, {\it Proceedings of the 27th International
Conference on Probabilistic, Combinatorial and Asymptotic Methods for the
Analysis of Algorithms},  Krak\'{o}w, Poland, 4-8 July 2016.

%\bibitem{BRW83}
%E.A. Bender, L. B. RICHMOND, and S. G. WILLIAMSON,
%Central and Local Limit Theorems Applied to Asymptotic Enumeration. III. Matrix Recursions,
%JOURNAL OF COMBINATORIAL THEORY, Series A {\bf 35}, 263-278 (1983).

\bibitem{BP} A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, 1979.


\bibitem{BEW} B. C. Berndt, R. J. Evans, K. S. Williams,  Gauss and Jacobi Sums.
Canadian Mathematical Society Series of Monographs and Advanced
Texts. A Wiley-Interscience Publication. John Wiley \& Sons, Inc.,
New York, 1998.



\bibitem{Bhaskaran}
M. Bhaskaran, Sums of $m$-th powers in algebraic and abelian number fields, {\it Arch. Math.
(Basel)}{ \bf 17} (1966), 497-504; Correction, ibid. 22 (1972), 370-371.




\bibitem{CaoSun07} W.  Cao and Q. Sun, Factorization formulae on counting zeros of diagonal equations over finite fields. {\it Proc. Amer. Math. Soc.} {\bf 135} (2007), no. 5, 1283-1291.




\bibitem{Cipra}  J. A. Cipra, Waring's number in finite fields, PhD thesis,
Kansas State University, 2010.

\bibitem{Cochrane} T. Cochrane, Waring's problem over finite fields,
\url{https://www.fields.utoronto.ca/programs/scientific/10-11/numtheoryconf/Todd_Cochrane.pdf}.




\bibitem{Conrad}
K. Conrad,   Jacobi sums and Stickelberger's congruence, {\it Enseign. Math.} \textbf{41} (1995), 141-153.



\bibitem{FS09} P. Flajolet and R. Sedgewick,
{\it Analytic Combinatorics}, Cambridge University Press, 2009.



\bibitem{gacsetal} A. G\'{a}cs, T. H\'{e}ger, Z. L. Nagy, D. P\'{a}lv\"{o}lgyi, Permutations,
hyperplanes and polynomials over finite fields, {\it Finite Field
Appl.}  \textbf{16} (2010), 301-314.

\bibitem{GaoWor99}  Z. Gao and N. Wormald, The Size of the Largest Components in Random Planar Maps, {\it SIAM J. Discrete Math.},
{\bf 12} (1999), 216-228.

\bibitem{gold}
I. P. Goulden and D. M. Jackson.
{\em Combinatorial enumeration}.
A Wiley-Interscience Publication. John Wiley \&\ Sons, Inc., New
  York, 1983.
Wiley-Interscience Series in Discrete Mathematics.

\bibitem{HM09}  S. Heubach and T. Mansour, {\em Combinatorics of Compositions and Words}, CRC / Taylor \& Francis 2009.


\bibitem{Hilbert} D. Hilbert,  {Beweis f\"ur die Darstellbarkeit der ganzen
Zahlen durch eine feste Anzahl $n$-ter Potenzen (Waringsches Problem)}.  {\it
Mathematische Annalen.} {\bf 67} (3): 28-300.

\bibitem{Kosters:13} M. Kosters,  The subset problem for finite abelian groups, {\it J. Combin. Theory Ser. A} \textbf{120} (2013),  527-530.


\bibitem{LiWan} J. Li and D. Wan, On the subset sum problem over finite
fields, {\it Finite Field Appl.},  {\bf14} (2008), 911-929.


\bibitem{LiWan:12} J. Li and D. Wan, Counting subset sums of finite
abelian groups, {\it J. Combin. Theory Ser. A} \textbf{119} (2012),
no. 1,  170-182.


\bibitem{Lou08}
G. Louchard, Matrix compositions: A probabilistic analysis, {\it
Pure Math. Appl.} {\bf 19} (2008), no. 2--3, 127--146.

\bibitem{mullen}  G. L. Mullen, A note on partition/compostion problem, private communication, 2016.


\bibitem{MPR09} E. Munarini, M. Poneti and S. Rinaldi, Matrix Compositions, {\it J. Integer Seq.}, \textbf{12} (2009) Article 09.4.8, 13 pp.

\bibitem{MuWa} A. Muratovi\'{c}-Ribi\'{c} and Q. Wang,
On a conjecture of polynomials with prescribed range, {\it  Finite
Field Appl.}  {\bf 18}  (2012), no. 4, 728--737.


\bibitem{MurWan} A. Muratovi\'{c}-Ribi\'{c} and Q. Wang, Partitions and compositions over finite fields. {\it Electron. J. Combin.} {\bf 20} (2013), no. 1, Paper 34, 14 pp.

\bibitem{MurWan2}  A. Muratov\'{i}c-Ribi\'{c} and Q. Wang, The multisubset sum problem for finite abelian groups. {\it Ars Math. Contemp.} {\bf 8} (2015), no. 2, 417-423.


\bibitem{Small}  C. Small, Waring's number mod $n$,  {\it Amer. Math. Monthly} {\bf 84} (1)(1977), 12-25.



\bibitem{Stanley} R. P. Stanley, Enumerative Combinatorics, Vol I, Cambridge University Press, 1997.

\bibitem{Sun97} Q. Sun On diagonal equations over finite fields. {\it Finite Fields Appl.} {\bf 3} (1997), no. 2, 175-179.


\bibitem{SunYuan96}  Q. Sun, P. Z.  Yuan, On the number of solutions of diagonal equations over a finite field. {\it Finite Fields Appl.}  {\bf 2} (1996), no. 1, 35-41.


\bibitem{Tornheim} L. Tornheim, Sums of $n$-th powers in fields of prime
characteristic, {\it Duke Math. J.} {\bf 4} (1938), 359-362.


\bibitem{Wan:06} D. Wan, Mirror symmetry for zeta functions, In Mirror Symmetry V, AMS/IP Studies in Advanced Mathematics, Vol.38,  2006, 159-184.

\bibitem{Wan:08}  D. Wan, Lectures on zeta functions over finite fields (Gottingen Lecture Notes).
in Higher Dimensional Geometry over Finite Fields, eds: D. Kaledin and Y. Tschinkel, IOS Press, 2008, 244-268.

\bibitem{Weil49}  A. Weil,  Numbers of solutions of equations in finite fields.
{\it Bull. Amer. Math. Soc.}  {\bf 55} (1949). 497-508.



\bibitem{Wolfmann92} J. Wolfmann,  The number of solutions of certain diagonal equations over finite fields. {\it J. Number Theory} {\bf 42} (1992), no. 3, 247-257.

\bibitem{Wong:08}  C. F. Wong, Zeta functions of projective toric hypersurfaces
over finite fields. PhD thesis, University of California, Irvine, 2008.
%available at http://arxiv.org/pdf/0811.0887





\end{thebibliography}}

\end{document}
