Saarland Informatics Campus (SIC), Saarbrücken Graduate School of Computer
Science, Saarland University<EMAIL_ADDRESS>saarland.dehttps://orcid.org/0000-0002-0943-8282 University of Warwick, United
Kingdomchristian.ikenmeyer@warwick.ac.ukhttps://orcid.org/0000-0003-4654-177XEPSRC
EP/W014882/2 Julian Dörfler and Christian Ikenmeyer [500]Theory of computation
Automata extensions

###### Acknowledgements.

2

# Functional Closure Properties of Finite $\IN$-weighted Automata

Julian Dörfler  Christian Ikenmeyer

###### Abstract

We determine all functional closure properties of finite $\IN$-weighted
automata, even all multivariate ones, and in particular all multivariate
polynomials. We also determine all univariate closure properties in the
promise setting, and all multivariate closure properties under certain
assumptions on the promise, in particular we determine all multivariate
closure properties where the output vector lies on a monotone algebraic graph
variety.

###### keywords:

Finite automata, weighted automata, counting, closure properties, algebraic
varieties

###### category:

##  1 Finite $\IN$-weighted automata and functional closure properties

Let $\Sigma$ be a finite set, for example $\Sigma=\\{0,1\\}$. A finite
$\IN$-weighted automaton with all weights 1 is a nondeterministic finite
automaton that on input $w\in\Sigma^{\star}$ outputs the number of accepting
computation paths on input $w$, instead of just outputting whether or not an
accepting computation path exists, see Def. 2.1 for the formal definition
111We use the equality of the number of accepting paths of an NFA and the
output of the corresponding $\IN$-weighted automaton, see [10, Exa. 2.2]..
While every nondeterministic finite automaton determines a subset of
$\Sigma^{\star}$, a finite $\IN$-weighted automaton computes a function
$\Sigma^{\star}\to\IN$. A function $f:\Sigma^{\star}\to\IN$ can be presented
as the series $\sum_{w\in\Sigma^{\star}}f(w)w$, and the set of series is
denoted by
$\IN\mathopen{\hbox{\set@color${\langle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\langle}$}}\Sigma^{\star}\mathclose{\hbox{\set@color${\rangle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\rangle}$}}$
in the automata literature, see e.g. [10]222A series with finite support is
called a _polynomial_ , but we will not be concerned with the support of
series in this paper. Instead, we use the term _polynomial_ as it is used in
commutative algebra, and we mean multivariate polynomials with rational
coefficients.. The natural way of adding two functions $\Sigma^{\star}\to\IN$
and adding two series in
$\IN\mathopen{\hbox{\set@color${\langle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\langle}$}}\Sigma^{\star}\mathclose{\hbox{\set@color${\rangle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\rangle}$}}$
coincides, but in both presentations we have a natural way of taking the
product, and those do not coincide:

  1. 1.

Pointwise product of functions $\Sigma^{\star}\to\IN$. This is called the
Hadamard product.

  2. 2.

Convolution of series, called the Cauchy product.

A series $f$ is called _recognizable_ if there is a finite $\IN$-weighted
automaton that computes $f$. The set of recognizable series is denoted by
$\IN^{\textup{rec}}\mathopen{\hbox{\set@color${\langle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\langle}$}}\Sigma^{\star}\mathclose{\hbox{\set@color${\rangle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\rangle}$}}$
in [10], but we denote it by $\mathsf{\\#FA}$, to emphasise that we undertake
a study similar to $\mathsf{\\#P}$ in [13, Thm 3.13], [5, Thm 6], and recently
[14], but instead of polynomial-time Turing machines we study finite automata.
The Kleene-Schützenberger theorem states that $\mathsf{\\#FA}$ is the smallest
set that contains all support 1 series and is closed under sums, Cauchy
products, and Kleene-iterations (whenever well-defined, a Kleene-iteration is
the sum of all Cauchy powers), see [10, §4], but we will not need this
insight.

In this paper we study the functional closure properties333See [13, Sec. 1]
for the naming _functional closure property_. A different reasonable name
would be _pointwise closure property_. of $\mathsf{\\#FA}$. A function
$\varphi:\IN^{m}\to\IN$ is called a _functional closure property_ of
$\mathsf{\\#FA}$ if for all $f_{1}\in\mathsf{\\#FA}$,
$f_{2}\in\mathsf{\\#FA}$, $\ldots$, $f_{m}\in\mathsf{\\#FA}$ we have that
$\varphi(f_{1},\ldots,f_{m})\in\mathsf{\\#FA}$. By
$\varphi(f_{1},\ldots,f_{m})$ we mean the function that on input
$w\in\Sigma^{\star}$ outputs $\varphi(f_{1}(w),\ldots,f_{m}(w))$.

Classically, one of the simplest functional closure properties of
$\mathsf{\\#FA}$ is $\varphi:\IN^{2}\to\IN$,
$\varphi(f_{1},f_{2})=f_{1}+f_{2}$. This is a functional closure property of
$\mathsf{\\#FA}$, because given $f_{1}\in\mathsf{\\#FA}$ and
$f_{2}\in\mathsf{\\#FA}$, we can show
$\varphi(f_{1},f_{2})=f_{1}+f_{2}\in\mathsf{\\#FA}$ by an easy construction:
The new NFA consists of a copy of the NFA for $f_{1}$ and a copy of the NFA
for $f_{2}$, and makes an initial nondeterministic choice as to which NFA to
run, see Lemma 3.1 for the details.

Another classical simple functional closure property of $\mathsf{\\#FA}$ is
$\varphi:\IN^{2}\to\IN$, $\varphi(f_{1},f_{2})=f_{1}\cdot f_{2}$. This
corresponds to the Hadamard product. This is a functional closure property of
$\mathsf{\\#FA}$, because given $f_{1}\in\mathsf{\\#FA}$ and
$f_{2}\in\mathsf{\\#FA}$, we can show $\varphi(f_{1},f_{2})=f_{1}\cdot
f_{2}\in\mathsf{\\#FA}$ by the following construction: The new NFA consists of
the product NFA of the NFAs for $f_{1}$ and $f_{2}$, and the accepting states
correspond to pairs of accepting states, see Lemma 3.2 for the details. This
product construction corresponds to the Hadamard product.

The Cauchy product is also a product on the set $\mathsf{\\#FA}$, but we
explain now that the Cauchy product is not “functional”, and hence it is out
of scope for this type of studies. If $\varphi:\IN^{m}\to\IN$ is a functional
closure property of $\mathsf{\\#FA}$, then we can study the corresponding map
$\widetilde{\varphi}:\underbrace{\mathsf{\\#FA}\times\mathsf{\\#FA}\times\cdots\times\mathsf{\\#FA}}_{m\textup{
times}}\to\mathsf{\\#FA}$. Observe that if $\varphi$ is a functional closure
property of $\mathsf{\\#FA}$, then by definition we have that for all pairs
$(w,w^{\prime})\in\Sigma^{\star}\times\Sigma^{\star}$:
if $(f_{1}(w),\ldots,f_{m}(w))=(f_{1}(w^{\prime}),\ldots,f_{m}(w^{\prime}))$,
then
$\widetilde{\varphi}(f_{1},\ldots,f_{m})(w)=\widetilde{\varphi}(f_{1},\ldots,f_{m})(w^{\prime})$.
Let $\zeta:\mathsf{\\#FA}\to\mathsf{\\#FA}$ denote the Cauchy square. We use
the observation above to show that $\zeta$ is not equal to
$\widetilde{\varphi}$ for any $\varphi:\IN\to\IN$. Let $m=1$ and $f(w)=1$ if
$w=1$, $f(w)=0$ otherwise. Clearly, $f\in\mathsf{\\#FA}$. Then
$\zeta(f)(11)=1$, and $\zeta(f)(w)=0$ for all $w\neq 11$. In particular
$\zeta(f)(0)\neq\zeta(f)(11)$, even though $f(0)=f(11)$. Hence,
$\zeta\neq\widetilde{\varphi}$ for all $\varphi:\IN\to\IN$.

Numerous functional closure properties of $\mathsf{\\#FA}$ exist, for example
the safe decrementation $\max\\{0,f_{1}-1\\}$, and the binomial coefficient
$\binom{f_{1}}{2}$. But not all non-negative functions are functional closure
properties of $\mathsf{\\#FA}$, for example $(f_{1}-f_{2})^{2}$ is not, which
can be shown using the Pumping Lemma. In this paper, we determine _all_
functional closure properties of $\mathsf{\\#FA}$, see §1.2 for the detailed
statement.

###  1.1 Motivation

Functional closure properties can be studied for many different counting
machine models (also for example with different types of oracle access) and
different types of input sets. The first study of this type was done for
nondeterministic polynomial-time Turing machines, i.e., the class
$\mathsf{\\#P}$, see [13], [5], and the recent [14]. Recall that the class
$\mathsf{\\#P}$ is the class of functions $f:\Sigma^{*}\to\IN$ for which a
nondeterministic polynomial time Turing machine $M$ exists such that for all
$w\in\Sigma^{*}$ the number of accepting paths for the computation $M(w)$ is
exactly $f(w)$. The papers mentioned above prove that the relativizing
multivariate polynomial closure properties are exactly those polynomials that
have nonnegative integers in their expansion over the binomial basis, see
[14]. A functional closure property $\varphi:\IN^{m}\to\IN$ of $\mathsf{\\#P}$
is _relativizing_ if $\varphi$ is a closure property for all
$\mathsf{\\#P}^{A}$, where $A\subset\Sigma^{*}$ is some oracle. The hope is
that for simpler models of computation no oracle access is required to
determine the functional closure properties, and we show that this is true for
$\mathsf{\\#FA}$, see §1.2.

Functional closure properties can be used directly to construct combinatorial
proofs of equalities and inequalities. For example, Fermat’s little theorem
states that $p$ divides $a^{p}-a$. The quantity $\frac{1}{p}(a^{p}-a)$ has a
combinatorial interpretation, which can be deduced from the fact that
$\frac{1}{p}((f_{1})^{p}-f_{1})$ is a univariate functional closure property
of $\mathsf{\\#P}$, see [14, Prop. 7.3.1], which coincides with the original
proof [20], see also [19, eq. (5)]). On the other hand, if a function is not a
functional closure property, then this means in a very strong sense that there
is no combinatorial interpretation for the quantity it describes. For example,
the Hadamard inequality ([12, §2.13], [4, §2.11], [14, eq. (2)]) states that

$\textstyle\det\left(\begin{smallmatrix}a_{11}&\cdots&a_{1d}\\\
\vdots&\ddots&\vdots\\\
a_{d1}&\cdots&a_{dd}\end{smallmatrix}\right)^{2}\leq\prod_{i=1}^{d}(a_{i1}^{2}+\cdots+a_{id}^{2}).$

One could try to prove this by finding a combinatorial interpretation of the
difference $\mathcal{H}\geq 0$ of the right-hand side and the left-hand side,
but even for $d=3$ we have that

$\textstyle\varphi(f_{1},\ldots,f_{9})\ =\
(f_{1}^{2}+f_{2}^{2}+f_{3}^{3})\cdot(f_{4}^{2}+f_{5}^{2}+f_{6}^{3})\cdot(f_{7}^{2}+f_{8}^{2}+f_{9}^{3})-\det\left(\begin{smallmatrix}f_{1}&f_{2}&f_{3}\\\
f_{4}&f_{5}&f_{6}\\\ f_{7}&f_{8}&f_{9}\end{smallmatrix}\right)$

is not a 9-variate relativizing functional closure property of
$\mathsf{\\#P}$, see [14, §7.2]. In particular, if the function is not a
closure property of $\mathsf{\\#P}$, then there are instantiations
$f_{1},\ldots,f_{9}\in\mathsf{\\#P}$ such that $\varphi(f_{1},\ldots,f_{9})$
is not in $\mathsf{\\#P}$, whereas a combinatorial interpretation of
$\mathcal{H}$ should yield $\varphi(f_{1},\ldots,f_{9})\in\mathsf{\\#P}$. This
does not rule out a more indirect combinatorial proof for the inequality: For
example, for proving combinatorially that $(a-1)^{2}\geq 0$ one could try to
interpret the quantity $(a-1)^{2}$ combinatorially, but $(f_{1}-1)^{2}$ is not
a relativizing closure property of $\mathsf{\\#P}$. However,
$f_{1}\cdot(f_{1}-1)^{2}=6\binom{f_{1}}{3}+2\binom{f_{1}}{2}$ is a
relativizing closure property of $\mathsf{\\#P}$ (see [14, §2.4]). There is an
obvious combinatorial interpretation of $6\binom{a}{3}+2\binom{a}{2}$ as
counting size 2 and 3 subsets with multiplicity 6 and 2, respectively. Hence
this gives an indirect combinatorial proof for the inequality $(a-1)^{2}\geq
0$ by providing a combinatorial interpretation for $a(a-1)^{2}$.

Some inequalities are only true if the inputs satisfy certain constraints. For
example, the _Ahlswede Daykin inequality_ , see [1], [2], [14, §1.2(3)]: If
$a_{0}b_{0}\geq c_{0}d_{0}$ and $a_{0}b_{1}\geq c_{0}d_{1}$ and
$a_{1}b_{0}\geq c_{0}d_{1}$ and $a_{1}b_{1}\geq c_{1}d_{1}$, then
$(c_{0}+c_{1})(d_{0}+d_{1})\geq(a_{0}+a_{1})(b_{0}+b_{1})$. If all quantities
are in $\mathsf{\\#P}$, including the differences $c_{0}d_{0}-a_{0}b_{0}$, can
we conclude that $(c_{0}+c_{1})(d_{0}+d_{1})-(a_{0}+a_{1})(b_{0}+b_{1})$ is in
$\mathsf{\\#P}$? This is an example of a promise problem: We are given twelve
$\mathsf{\\#P}$ functions
$a_{0},a_{1},b_{0},b_{1},c_{0},c_{1},d_{0},d_{1},h_{1},h_{2},h_{3},h_{4}$ with
the guarantee that $a_{0}b_{0}+h_{1}=c_{0}d_{0}$,
$a_{0}b_{1}+h_{2}=c_{0}d_{1}$, $a_{1}b_{0}+h_{3}=c_{0}d_{1}$,
$a_{1}b_{1}+h_{4}=c_{1}d_{1}$. In other words, the 12-dimensional output
vector that we get for every $w\in\Sigma^{*}$ lies on a codimension 4
algebraic subvariety in $\mathbb{Q}^{12}$. Recall that an algebraic subvariety
is defined as the simultaneous zero set of a set of polynomials. Since the 4
variables $h_{1},\ldots,h_{4}$ are determined by the other 8, this variety is
a so-called _graph_ or _graph variety_. Numerous questions about combinatorial
proofs for inequalities from different areas of mathematics can be phrased in
the language of graph varieties, see [14]. The idea is to collect the
equations for a set $S$ (the variety) into what is called the _vanishing
ideal_ $I$, i.e.,
$I=I(S)=\\{\varphi\in\mathbb{Q}[f_{1},\ldots,f_{m}]\mid\forall(f_{1},\ldots,f_{m})\in
S:\varphi(f_{1},\ldots,f_{m})=0\\}$; and define the _coordinate ring_
$\mathbb{Q}[S]$ as the quotient ring $\mathbb{Q}[f_{1},\ldots,f_{m}]/I(S)$,
see [8]. An element in the quotient ring is a coset with respect to the
vanishing ideal. If there exists a representative $\varphi^{\prime}$ in a
coset $\varphi+I$ that is a functional closure property of $\mathsf{\\#P}$,
then every function in $\varphi+I$ is a promise closure property of
$\mathsf{\\#P}$ on the variety $S$. It is desirable to also have the opposite
direction, but this only holds under some reasonable restrictions on $S$, in
particular it holds for all graph varieties. This is used in [14, Prop. 2.5.1]
to show that $c_{0}d_{0}-a_{0}b_{0}$ is not a relativizing promise closure
property of $\mathsf{\\#P}$ on this graph variety. We prove the same strong
dichotomy for monotone graph varieties for $\mathsf{\\#FA}$ instead of
$\mathsf{\\#P}$, see Theorem 4.11.

The systematic study of combinatorial interpretations and combinatorial proofs
via definitions from computational complexity theory is a very recent research
direction [17, 18, 14, 19, 15, 6, 7]. The goal is to determine whether or not
certain quantities admit a combinatorial description or not. Famous open
questions of this type in algebraic combinatorics have been listed by Stanley
in [24], for example his problems 9, 10, and 12. As many combinatorialists do,
Stanley has phrased his questions in an informal way without mentioning
counting classes.

The class $\mathsf{\\#P}$ is the correct class for some purposes, but for
others it is too large. For example, the determinant of a skew-symmetric
matrix with entries from $\\{-1,0,1\\}$ is always non-negative, but this
quantity is trivially in $\mathsf{\\#P}$, because the determinant can be
computed in polynomial time. This gives no satisfying insight into whether or
not this quantity has a combinatorial interpretation. Smaller counting classes
are required (see also the discussion in [17, §1]), and we provide the first
study of functional closure properties for the subclass
$\mathsf{\\#FA}\subset\mathsf{\\#P}$. Unlike the classification for
$\mathsf{\\#P}$, our results do not rely on oracle separations, i.e., our
classification is entirely unconditional.

###  1.2 Our results

Let $n\operatorname{rem}p\in\\{0,\ldots,p-1\\}$ denote the smallest
nonnegative $r$ such that $n\equiv_{p}r$. A function $\varphi:\IN\to\IN$ is
called _ultimately PORC_ (Polynomial On Residue Classes444PORC functions are
also known as quasipolynomials or pseudopolynomials, but we want to avoid
those names for the potential confusion to quasipolynomial growth and
pseudopolynomial running times.) if $\exists p,N\in\IN$ and there exist
polynomials $\varphi_{0},\ldots,\varphi_{p-1}:\IN\to\mathbb{Q}$ such that for
every $n\geq N$ we have $\varphi(n)=\varphi_{n\operatorname{rem}p}(n)$ 555Note
that each $\varphi$ in this paper is defined on the natural numbers and maps
to the natural numbers, which is a subtle restriction. For example, a
univariate polynomial $\varphi:\mathbb{Q}\to\mathbb{Q}$ maps integers to
integers if and only if its coefficients in the binomial basis are integers,
see Section 2. However, non-negativity is not an algebraic property. Also note
that for the case of $\varphi$ being just a univariate polynomial, the
corresponding linear recursive sequence can have negative entries in the
matrix..

We first classify the univariate functional closure properties of
$\mathsf{\\#FA}$:

  * •

Theorem (see Theorem 3.36). A function $\varphi:\IN\to\IN$ is a functional
closure property of $\mathsf{\\#FA}$ if and only if $\varphi$ is an ultimately
PORC function.

More generally, we classify the multivariate functional closure properties of
$\mathsf{\\#FA}$:

  * •

Theorem (see Theorem 3.38). A function $\varphi:\IN^{m}\to\IN$ is a functional
closure property of $\mathsf{\\#FA}$ if and only if $\varphi$ can be written
as a finite sum of finite products of univariate ultimately PORC functions.

We analyze the special case of multivariate polynomials:

  * •

Theorem (see Lemma 3.42). A multivariate polynomial $\varphi:\IN^{m}\to\IN$
with rational coefficients is a functional closure property of
$\mathsf{\\#FA}$ iff for every $\psi$ that can be formed from $\varphi$ by
replacing any subset of variables – including the empty set – by constants
from $\IN$, then all dominating terms of $\psi$ in the binomial basis have
positive coefficients.

We lift this result to monotone graph varieties (and to more general sets, see
Theorem 4.7), where we get exactly the desirable classification given by the
vanishing ideal:

  * •

Theorem (see Theorem 4.11). Let $S$ be a monotone graph variety and let
$I=I(S)$ be its vanishing ideal. A multivariate polynomial $\varphi:S\to\IN$
is a functional promise closure property of $\mathsf{\\#FA}$ with regard to
$S$ if and only if there exists $\psi\in I$ such that $\varphi+\psi$ is a
multivariate functional closure property of $\mathsf{\\#FA}$.

##  2 Notation

Let $\IN=\\{0,1,2,\ldots\\}$. For a finite set $\Sigma$ let $\Sigma^{\star}$
denote the set of all finite length sequences with elements from $\Sigma$. The
vector space of multivariate polynomials $\mathbb{Q}[f_{1},\ldots,f_{m}]$ in
variables $f_{1},\ldots,f_{m}$ has a basis given by products of binomial
coefficients:
$\big{\\{}\prod_{i=1}^{m}\binom{f_{i}}{c_{i}}\big{\\}}_{c_{1},\ldots,c_{m}}$,
where each $c_{i}\in\IN$. Here we used
$\binom{x}{c}=\frac{1}{c!}x\cdot(x-1)\cdot\ldots\cdot(x-c+1)$ as a polynomial.
This is called the _binomial basis_. A multivariate polynomial $\varphi$ is
called _integer valued_ if $\varphi(\mathbb{Z}^{m})\subseteq\mathbb{Z}$, which
is equivalent to $\varphi(\IN^{m})\subseteq\mathbb{Z}$, and which is also
equivalent to all coefficients in the binomial basis being integers, see for
example [14, Prop. 4.2.1] for a short proof of this classical fact.

We now recall (see [10, Def. 2.1]) our main model of computation, the finite
$\IN$-weighted automaton, which we just call non-deterministic finite
automaton (NFA) for brevity.

######  Definition 2.1.

An NFA $M$ is a tuple $(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ where
the set of states $Q$ and the alphabet $\Sigma$ are finite sets and
$\textup{wt}:Q\times\Sigma\times Q\to\IN$ is the weighted transition function,
$\textup{in}:Q\to\IN$ are the weighted initial states and
$\textup{out}:Q\to\IN$ are the weighted accepting states666Note that in
definitions by other authors one can find simpler versions of NFAs, in
particular unweighted initial and accepting states and unweighted edges while
also restricting to a single initial state. We will see soon that working with
unweighted NFAs is not a restriction, but additionally restricting the model
to have a single initial state is strictly weaker, since this model could not
compute any function $f$ with $f(\varepsilon)>1$. To obtain the same
expressiveness one would have to additionally allow for
$\varepsilon$-transitions, while disallowing cycles of
$\varepsilon$-transitions to prevent infinite values for $f$. . A
_computation_ $P$ for a word $w=w_{1}\ldots w_{n}\in\Sigma^{\star}$ of length
$n$ is a sequence $q_{0}q_{1}\ldots q_{n}$ in $Q^{n+1}$. It has _multiplicity_
or _weight_ 777We will use both of these terms interchangeably. For a weighted
automaton, calling this weight is more natural, while when looking at the
underlying graph as a multigraph, multiplicity of paths and walks is more
natural.
${\mathbf{w}}(P)=\textup{in}(q_{0})\cdot\prod_{i=1}^{n}\textup{wt}(q_{i-1},w_{i},q_{i})\cdot\textup{out}(q_{n})$
and _partial weight_
${\underline{\mathbf{w}}}(P)=\textup{in}(q_{0})\cdot\prod_{i=1}^{n}\textup{wt}(q_{i-1},w_{i},q_{i})$.
We say that $M$ _computes_ $f:\Sigma^{\star}\to\IN$ where $f(w)$ is the sum of
the weights over all computations of $M$ on $w$. The class $\mathsf{\\#FA}$ is
defined as the set of all functions $f:\Sigma^{\star}\to\IN$ that are computed
by NFAs.

If needed to distinguish these for different automata, we use a corresponding
subscript, for example the weights of computations in $M_{f}$ would be denoted
by ${\mathbf{w}}_{f}$, etc.

######  Definition 2.2 (Simple NFA).

We say an NFA $M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ is _simple_
if
$\operatorname{im}\textup{wt},\operatorname{im}\textup{in},\operatorname{im}\textup{out}\subseteq\\{0,1\\}$.

The notion of a simple NFA also motivates our use of the term NFA opposed to
$\IN$-weighted automaton: We simply count the number of accepting paths of $M$
on a word $w$. This is in line with $\mathsf{\\#P}$ counting the number of
accepting paths on a polynomial time non-deterministic Turing machine.

######  Lemma 2.3 (Folklore).

For every NFA $M$ there exists a simple NFA $M^{\prime}$ computing the same
function.

A proof of this simple fact can be found in the Appendix, for the sake of
completeness. We denote by $a\equiv_{p}b$ that $a\in\IN$ and $b\in\IN$ are
congruent modulo $p\in\IN\setminus\\{0\\}$. The indicator function
$\mathbbm{1}_{n=c}:\IN\to\IN$ is defined as $n\mapsto\begin{cases}1&\text{if
$n=c$}\\\ 0&\text{otherwise}\end{cases}$ and analogously for different
conditions. By abuse of notation, if we have a function
$f:\Sigma^{\star}\to\IN$ and an expression $\varphi:\IN\to\IN$ in $n$, we
replace $n$ by $f$ in the expression to denote $\varphi\circ f$. For example
we use $\mathbbm{1}_{f=c}$ to denote the function
$w\mapsto\mathbbm{1}_{f(w)=c}$, similarly $\binom{f}{2}$ denotes the function
$w\mapsto\binom{f(w)}{2}$. Furthermore we use the notation $[n]$ to denote the
set $\\{1,\ldots,n\\}$ for any $n\in\IN$.

##  3 Functional closure properties

###  3.1 Univariate functional closure properties

We say a function $\varphi:\IN\to\IN$ is a functional closure property of
$\mathsf{\\#FA}$ if $\varphi(\mathsf{\\#FA})\subseteq\mathsf{\\#FA}$, i.e. if
for every function $f\in\mathsf{\\#FA}$ the function $\varphi\circ f$ is also
in $\mathsf{\\#FA}$. Our goal in this section is to classify all functional
closure properties of $\mathsf{\\#FA}$. They will be precisely the ultimately
PORC functions.

We call a function $\varphi:\IN\to\IN$ an _ultimately almost PORC function_ if
there is a _quasiperiod_ $p$, an _offset_ $N\in\IN$ and _constituents_
$\varphi_{0},\ldots,\varphi_{p-1}:\IN\to\mathbb{Q}$, where each $\varphi_{i}$
is either a polynomial with rational coefficients or a function in
$2^{\Theta(n)}$, and for every $n\geq N$ we have $\varphi(n)=\varphi_{n\rem
p}(n)$. If all the constituents are polynomials, we call $\varphi$ an
_ultimately PORC function_. The smallest representative of each constituent
and of the finite cases before the periodic behaviour is captured by the
_shifted remainder_ operator $n\operatorname{srem}_{p}N$, defined via

$n\operatorname{srem}_{p}N=\begin{cases}n&\text{if $n<N$}\\\ \min\\{k\geq
N\mid k\equiv_{p}n\\}&\text{if $n\geq N$}\end{cases}$

The first half of the section is dedicated to proving that every ultimately
PORC function is a functional closure property of $\mathsf{\\#FA}$, see Lemma
3.30. In order to prove this we show that $\mathsf{\\#FA}$ is closed under

######  Lemma 3.1 (Addition).

If $f,g\in\mathsf{\\#FA}$, then $f+g\in\mathsf{\\#FA}$.

######  Lemma 3.2 (Multiplication).

If $f,g\in\mathsf{\\#FA}$, then $f\cdot g\in\mathsf{\\#FA}$.

[Subtraction of constants]lemmarestatesubtraction If $f\in\mathsf{\\#FA}$,
then $\forall c\in\IN:\,\max(f-c,0)\in\mathsf{\\#FA}$.
[Clamping]lemmarestateclamping If $f\in\mathsf{\\#FA}$, then
$\min(f,c)\in\mathsf{\\#FA}$ for any constant $c\in\IN$. [Comparison with
constants]lemmarestateconst If $f\in\mathsf{\\#FA}$, then the functions
$\mathbbm{1}_{f=c}$, $\mathbbm{1}_{f\leq c}$, $\mathbbm{1}_{f\geq c}$ are in
$\mathsf{\\#FA}$ for any constant $c\in\IN$. [Division by
constants]lemmarestatedivision If $f\in\mathsf{\\#FA}$, then $\forall
c\in\IN\setminus\\{0\\}:\,\lfloor f/c\rfloor\in\mathsf{\\#FA}$. [Modular
arithmetic]lemmarestatemod If $f\in\mathsf{\\#FA}$, then the function
$\mathbbm{1}_{f\equiv_{c}d}$ is in $\mathsf{\\#FA}$ for any constants
$c\in\IN\setminus\\{0\\}$ and $d\in\mathbb{Z}_{c}$. [Binomial
coefficients]lemmarestatebinom If $f\in\mathsf{\\#FA}$, then
$\binom{f}{c}\in\mathsf{\\#FA}$ for any constant $c\in\IN$.

While addition and multiplication are technically bivariate functional closure
properties, we list them here already since they are abundantly used
throughout the proofs of the univariate functional closure properties. Proofs
of those two classical results can be found in [9][Ch. 4.1 and 4.2.2] and in
the appendix, for the sake of completeness.

With the exception of binomial coefficients all the other closure properties
need to be able to “remove” some of the possible computations. For example,
consider decrementation, the special case of truncated subtraction by one, and
consider some simple NFA $M$ computing some strictly positive function $f$. We
now want to construct an NFA $M^{\prime}$ that computes $f-1$, i.e. an NFA
that has exactly one non-zero computation less than $M$ (assuming computations
of weights zero or one). For this we want a procedure to single out one non-
zero computation of $M$ to then change its weight to zero. For stronger models
of computation – like polynomial time non-deterministic Turing machines – this
approach seems hopeless. Already deciding the existence of one such
computation is $\mathsf{NP}$-hard. However for NFAs, deciding the existence of
a non-zero computation can be decided by a deterministic finite automaton,
namely the powerset automaton. Adjusting the powerset construction to filter
out a single non-zero computation, namely the lexicographically minimal one
can then be used to show that decrementation is a closure property of
$\mathsf{\\#FA}$.

Generalizing this approach to more general properties about the computations
gives us the framework of stepwise computation properties:

######  Definition 3.3 (Stepwise computation property).

Let $M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ be an NFA. A _stepwise
computation property_ is defined as where $S$ is a finite set and
$\textup{init}:Q\to S$, and $\textup{cond}:S\to\\{0,1\\}$ are functions. For
$w=w_{1}\ldots w_{n}\in\Sigma^{\star}$ and a computation $P=q_{0}\ldots q_{n}$
of $M$ on $w$ we define a _step sequence_ $s_{0}:=\textup{init}(q_{0})$ and
$s_{i}:=$ for $i\in[n]$. We also write to be the evaluation of the property.

These stepwise computation properties now enable us, given a simple NFA, to
construct NFAs computing both of the following:

######  Lemma 3.7.

Let $M_{f}$ be a simple NFA computing a function $f$ and let be a stepwise
computation property. Then there is an NFA $M$ computing
$g(w)=\sum_{P}{\mathbf{w}}_{f}(P)\cdot$, where the sum is over all
computations $P$ of $M_{f}$ on $w$.

######  Lemma 3.8.

Let $M_{f}$ be a simple NFA computing a function $f$ and let be a stepwise
computation property. Then there is an NFA $M$ computing $g(w)=\sum_{P}$,
where the sum is over all computations $P$ of $M_{f}$ on $w$.

######  Proof 3.9.

For both of these lemmas, we construct a sort of product automaton of $M_{f}$
and (represented by the set $S$), the details can be found in the appendix.

In other words, stepwise computation properties allow us to either “disable”
specific computations of $M_{f}$ or they allow us to directly extract
information about the computations of $M_{f}$. Note that the restriction on
the finiteness of $S$ is necessary, as the elements of $S$ are hard-coded into
the state space of the NFA in Lemmas 3.7 and 3.8. In particular, these lemmas
do not hold for even countably infinite $S$, which can be seen with the
example $S=\IN$ when we define the stepwise computation property in such a way
that iff $|w|$ is prime, leading to an NFA recognizing the language of all
words of prime length, a well known contradiction.

Further note that these two constructions do not incur exponential blowups
themselves, however for most of our applications the set $S$ will be of
exponential size in the number of states of $M_{f}$.

Returning to our decrementation example, to use Lemma 3.7 we want to construct
a stepwise computation property with iff $P$ is the lexicographically smallest
non-zero weight computation on $w$. For this we can set $S=\mathcal{P}(Q)$ to
be the set of all subsets of states $Q$, denoting the set of states that
currently are the endpoints of lexicographically smaller partial computations
of non-zero weight than the partial computation $P$ we are on. We need to
store all such potential states, since some current partial non-zero weight
computations might not be possible to be completed to a full non-zero weight
computation. Initially this set contains all states that are smaller than the
start state of $P$, the function then checks which lexicographically smaller
partial computations can be extended and whether any new partial computations
that agreed with $P$ up to this state can be lexicographically smaller than
$P$. Finally the cond function then checks whether there are any such
lexicographically smaller partial computations left that can be completed to a
non-zero weight computation, i.e. that end on a state $q\in Q$ with
$\textup{out}(q)=1$.

We want to generalize this idea to be able to generally create stepwise
computation properties that argue about the number of non-zero computations,
either in total or lexicographically smaller than a given computation. However
doing this in general would require choosing the set $S$ as the set of
functions $Q\to\IN$, which is infinite. As a result we embed the number of
computations into finite semirings first to then extract the relevant
information. For this purpose we only consider semirings with both additive
and multiplicative identities. Homomorphisms $h$ from a semiring $\mathcal{R}$
into another semiring $\mathcal{R}^{\prime}$ need to fulfill
$h(a+b)=h(a)+h(b)$, $h(a\cdot b)=h(a)\cdot h(b)$,
$h(1_{\mathcal{R}})=1_{\mathcal{R}^{\prime}}$,
$h(0_{\mathcal{R}})=0_{\mathcal{R}^{\prime}}$. Since every element of $\IN$ is
either $0$ or can be formed by repeated addition of $1$, any homomorphism from
$\IN$ into any other semiring is uniquely defined.

We can then use $\mathcal{R}$ to construct stepwise computation properties
(the full proofs can be found in the appendix). Combined with Lemmas 3.7 and
3.8 these use similar ideas to [16].

######  Lemma 3.11.

Let $N=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ be a simple NFA and
let $\mathcal{R}$ be a finite semiring and let $\tau:\IN\to\mathcal{R}$ be the
unique homomorphism from $\IN$ to $\mathcal{R}$. For any function
$\pi:\mathcal{R}\to\\{0,1\\}$ there is a stepwise computation property with ,
where the sum is over all computations $P^{\prime}$ of $N$ on $w$, independent
of $P$.

######  Proof 3.12.

Construct via: $S=Q\to\mathcal{R}$,
$\textup{init}(q)=r\mapsto\tau(\textup{in}(r))$, , and
$\textup{cond}(s)=\pi\bigl{(}\textstyle\sum_{r\in
Q}s(r)\cdot\tau(\textup{out}(r))\bigr{)}$. Let $s_{0},\ldots,s_{n}$ be the
step sequence of any computation $P$ of $w$. Since $\tau$ is a homomorphism,
we can pull out $\tau$. Thus
$s_{i}(q)=\tau(\sum_{\tilde{P}}{\underline{\mathbf{w}}}(\tilde{P}))$, where
the sum is over all computations $\tilde{P}$ of $w_{1},\ldots w_{i}$ ending in
the state $q$. The condition cond then completes this to , where the sum is
over all computations $P^{\prime}$ of $N$ on $w$.

######  Lemma 3.15.

Let $M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ be a simple NFA with
some ordering $<$ of $Q$, let $\mathcal{R}$ be a finite semiring and let
$\tau:\IN\to\mathcal{R}$ be the unique homomorphism from $\IN$ to
$\mathcal{R}$. For any function $\pi:\mathcal{R}\to\\{0,1\\}$ there is a
stepwise computation property with for all non-zero computations $P$ of $N$ on
$w$, where the sum is over all computations $P^{\prime}$ of $N$ on $w$ that
are lexicographically smaller than $P$.

######  Proof 3.16.

Construct via: $S=Q\to\mathcal{R}$,
$\textup{init}(q)=r\mapsto\tau(\mathbbm{1}_{r<q}\cdot\textup{in}(r))$, ,
$\textup{cond}(s)=\pi(\textstyle\sum_{r\in Q}\tau(\textup{out}(r))\cdot
s(r))$. Let $s_{0},\ldots,s_{n}$ be the step sequence of any computation
$P=q_{0}\ldots q_{n}$ of $w$. Inductively we can show that
$s_{i}(r)=\sum_{P^{\prime}}\tau({\underline{\mathbf{w}}}(P^{\prime}))$ for all
$i\in\\{0,\ldots,n\\}$ and $r\in Q$, where the sum is over all computations
$P^{\prime}=q_{0}^{\prime}\ldots q_{i}^{\prime}$ of $N$ on $w_{1}\ldots w_{i}$
with $q_{i}^{\prime}=r$ that are lexicographically smaller than $q_{0}\ldots
q_{i}$. Initially the only computations $P^{\prime}=q_{0}^{\prime}$ that are
lexicographically smaller than the computation $q_{0}$ are the ones with
$q_{0}^{\prime}<q_{0}$. For $i>0$ for a computation
$P^{\prime}=q_{0}^{\prime}\ldots q_{i}^{\prime}$ to be lexicographically
smaller than $q_{0}\ldots q_{i}$ there are two possibilities. Either
$q_{0}^{\prime}\ldots q_{i-1}^{\prime}$ is already lexicographically smaller
than $q_{0}\ldots q_{i-1}$ or $q_{0}^{\prime}\ldots
q_{i-1}^{\prime}=q_{0}\ldots q_{i-1}$ and $q_{i}^{\prime}<q_{i}$. In the
second case the weight of $P^{\prime}$ is precisely
$w(q_{i-1},w_{i},q_{i}^{\prime})$ since $P$ is a computation of non-zero
weight and thus weight exactly $1$. Combining all of this, we can finish the
proof of the claim with a similar argument to Lemma 3.11.

Note that the previous lemma makes no statement about the value of for any
computations $P$ of weight zero. However, this is enough for our uses, since
we only combine it with Lemma 3.7, i.e., gets weighted by ${\mathbf{w}}(P)$.

Most commonly, as is the case for decrementation, we want to be able to
exactly distinguish the number of non-zero computations if it is less than $k$
and otherwise be able to tell that the number is at least $k$. This is
achieved by using the following capped semiring:

######  Definition 3.19 (Capped semiring).

For $k\in\IN$ we call the semiring $\mathcal{R}_{k}=\\{0,\ldots,k\\}$ with the
operations $a+_{\mathcal{R}}b:=\min(a+b,k)$ and
$a\cdot_{\mathcal{R}}b:=\min(a\cdot b,k)$ the _capped_ semiring.

We can now show that decrementation is a functional closure property by simply
using Lemma 3.15 using the capped semiring $\mathcal{R}_{1}$ and $\pi(a)=a$ to
construct our wanted stepwise computation property computing iff $P$ is the
lexicographically smallest non-zero weight computation on $w$.

Most of the remaining closure properties are now proven by using the capped
semiring of a specific size and choosing the function $\pi$ accordingly, we
will show this in detail for the example of subtraction, the remaining proofs
can be found in the appendix.

######  Proof 3.20.

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$ be
a simple NFA computing $f$ with an arbitrary ordering $<$ on $Q_{f}$. Lemma
3.15 on the capped semiring $\mathcal{R}_{c}$ with $\pi(a)=\mathbbm{1}_{a\geq
c}$ for all $a\in\mathcal{R}$ constructs a stepwise computation property with

for all computations $P$ on $w$ of non-zero weight, i.e., iff $P$ is one of
the $c$ lexicographically smallest computations on $w$ with non-zero weight.
It follows that the NFA $M$ constructed by Lemma 3.7 computes
$g(w)=\max(f(w)-c,0)$.

If instead of rejecting the $c$ lexicographically smallest computations, we
accept only those computations, we compute the minimum of $f$ and $c$.

By using the capped semiring $\mathcal{R}_{c+1}$ with
$\pi_{=}(a)=\mathbbm{1}_{a=c}$, $\pi_{\leq}(a)=\mathbbm{1}_{a\leq c}$ and
$\pi_{\geq}(a)=\mathbbm{1}_{a\geq c}$, we can compute the indicator functions
$\mathbbm{1}_{f=c}$, $\mathbbm{1}_{f\leq c}$ and $\mathbbm{1}_{f\geq c}$
respectively.

The previous lemma in particular also implies the following:

######  Lemma 3.21.

If $\varphi:\IN\to\IN$ is a functional closure property of $\mathsf{\\#FA}$
and $\psi:\IN\to\IN$ is an arbitrary function with $\varphi(n)=\psi(n)$ for
all but finitely many $n\in\IN$, then $\psi$ is also a functional closure
property of $\mathsf{\\#FA}$.

######  Proof 3.22.

Let $f\in\mathsf{\\#FA}$ be arbitrary. Further let $N\in\IN$ be such that
$\varphi(n)=\psi(n)$ for all $n\geq N$. Then $\textstyle(\psi\circ
f)(w)=\sum_{i=0}^{N-1}\mathbbm{1}_{f(w)=i}\psi(i)+\mathbbm{1}_{f(w)\geq
N}\varphi(f(w))$ for all $w\in\Sigma^{\star}$. In particular $\psi\circ
f\in\mathsf{\\#FA}$ since the $\psi(i)$ are constants and $\varphi\circ
f\in\mathsf{\\#FA}$.

Division and modular arithmetic however use a different semiring: they use the
finite cyclic semiring $\mathbb{Z}_{c}=\\{0,\ldots,c-1\\}$ with
$\pi(a)=\mathbbm{1}_{a=c-1}$ and $\pi(a)=\mathbbm{1}_{a=d}$ respectively.

The previous closure properties turn out to already be sufficient to generate
all functional closure properties, so in particular they are sufficient to
generate binomial coefficients by using subtraction of constants,
multiplication and division by constants by using the definition of binomial
coefficients as a polynomial:
$\binom{x}{c}=\frac{1}{c!}x\cdot(x-1)\cdot\ldots\cdot(x-c+1)$. Nonetheless, we
give an additional proof for binomial coefficients as a different interesting
application of the stepwise computation property framework.

######  Proof 3.23.

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$ be
a simple NFA computing $f$ and let $c\in\IN$. For $c<2$ the statement of this
lemma is trivially true, so assume $c\geq 2$.

We construct the $c$-fold product automaton
$M_{f}^{c}=(Q_{f}^{c},\Sigma,\textup{wt}_{f}^{c},\textup{in}_{f}^{c},\textup{out}_{f}^{c})$
with

$\displaystyle\textup{wt}_{f}^{c}((q_{1},\ldots,q_{c}),\sigma,(q_{1}^{\prime},\ldots,q_{c}^{\prime}))$
$\displaystyle=\textstyle\prod_{i=1}^{c}\textup{wt}_{f}(q_{i},\sigma,q_{i}^{\prime})$
$\displaystyle\textup{in}_{f}^{c}((q_{1},\ldots,q_{c}))$
$\displaystyle=\textstyle\prod_{i=1}^{c}\textup{in}_{f}(q_{i})$
$\displaystyle\textup{out}_{f}^{c}((q_{1},\ldots,q_{c}))$
$\displaystyle=\textstyle\prod_{i=1}^{c}\textup{out}_{f}(q_{i})$

$M_{f}^{c}$ is a simple NFA and every computation on $M_{f}^{c}$ is the
cartesian product of $c$ computations on $M_{f}$. Our aim is to now construct
a stepwise computation property such that iff $P$ is composed of $c$ pairwise
distinct computations888We could also require them to be sorted in
lexicographical order by having $S$ be the set of all total preorders, but
since we can divide by $c!$ we are going with the easier exposition. on
$N_{f}$.

For this let $S$ be the set of all equivalence relations on the set $[c]$. We
define $\textup{init}((q_{0},\ldots,q_{c}))$ to be the equivalence relation
$R_{0}$ with $(a,b)\in R_{0}$ iff $q_{a}=q_{b}$. Additionally we define
$\textup{cond}(R)=1$ iff $R$ is the equivalence relation where every element
is only equivalent to itself, i.e. a computation gets accepted iff all its
constituent computations are pairwise distinct. Finally we define to be the
equivalence relation $R^{\prime}$ defined via $(a,b)\in R^{\prime}$ iff
$(a,b)\in R$ and $q_{a}^{\prime}=q_{b}^{\prime}$. With a simple induction we
can prove that for a computation $P=P_{1}\times\ldots\times P_{c}$ and the
step sequence $R_{0},\ldots,R_{n}$ we have $(a,b)\in R_{i}$ iff the
computations $P_{a}$ and $P_{b}$ are identical for the first $i$ steps. It
follows that the NFA $M$ constructed by Lemma 3.7 computes
$g(w)=\binom{f(w)}{c}\cdot c!$. Now, $\binom{f}{c}\in\mathsf{\\#FA}$ by Lemma
3.2.

While the combination of the previous lemmas can be used to show that any
polynomial written in the binomial basis with non-negative integer
coefficients is a functional closure property of $\mathsf{\\#FA}$, we can do
better by considering a shifted binomial basis. For example, consider the
polynomial $\varphi(x)=\frac{x^{2}}{2}-\frac{3x}{2}+1$. This polynomial is
non-negative for all $x\in\IN$. Writing $\varphi$ in the binomial basis we get
$\varphi(x)=\binom{x}{2}-\binom{x}{1}+1$. If however we allow the upper
indices of the binomial basis to be shifted, we can write $\varphi$ without
the use of negative coefficients as $\varphi(x)=\binom{x-1}{2}$. While $x-1$
itself is not a functional closure property of $\mathsf{\\#FA}$ the function
$\max(x-1,0)$ is a functional closure property of $\mathsf{\\#FA}$ and is
different from $x-1$ for only finitely many $x\in\IN$. In the same way we see
that $\varphi^{\prime}(x):=\binom{\max(x-1,0)}{2}$ only differs from $\varphi$
for finitely many $x\in\IN$, namely $x=0$. Using Lemma 3.21 to change those
finitely many values, we see that $\varphi$ is indeed a functional closure
property of $\mathsf{\\#FA}$.

Generalizing this idea we will show with the next two lemmas that this is
possible for any $\varphi$ with integer coefficients in the binomial basis,
with a small restriction: We don’t show that $\varphi$ itself is a functional
closure property of $\mathsf{\\#FA}$, but rather that
$x\mapsto\max(\varphi(x),0)$ is one. Note that this restriction is the best we
can hope for, since no computation in an NFA can ever have negative weight.

######  Lemma 3.26.

Let $\varphi(x)=\sum_{i=0}^{r}a_{i}\cdot\binom{x}{i}$ with
$a_{i}\in\mathbb{Z}$ and $a_{r}>0$. Then there are $b_{0},\ldots,b_{r}\in\IN$
and $c_{0},\ldots,c_{r}\in\IN$ with
$\varphi(x)=\sum_{i=0}^{r}b_{i}\cdot\binom{x-c_{i}}{i}$.

######  Proof 3.27.

We inductively prove this claim by using the Chu-Vandermonde identity [23] on
the term of highest degree. It allows us to replace the highest degree
binomial via
$\binom{x-c_{r}}{r}=\sum_{i=0}^{r}(-1)^{r-i}\binom{r-i+c_{r}-1}{r-i}\binom{x}{i}$.
For sufficiently large $c_{r}\in\IN$ this implies that the leading term of
$\varphi(x)-a_{r}\cdot\binom{x-c_{r}}{r}$ again is positive and of smaller
degree.

A full proof of the previous lemma can be found in the appendix.

######  Lemma 3.28 (Integer-valued polynomials).

Let $f\in\mathsf{\\#FA}$ and let $\varphi:\mathbb{Q}\to\mathbb{Q}$ be an
integer-valued polynomial, then $\max(\varphi\circ f,0)\in\mathsf{\\#FA}$.

######  Proof 3.29.

We can assume the leading coefficient of $\varphi$ to be positive. Otherwise
$\max(\varphi\circ f,0)$ can be directly written as a finite sum
$\sum_{i}c_{i}\cdot\mathbbm{1}_{f=i}$ which is in $\mathsf{\\#FA}$ by Lemmas
3.1, 3.2 and 3.2. Write $\varphi$ in the binomial basis as
$\varphi(x)=a_{0}\cdot\binom{x}{0}+\ldots+a_{r}\cdot\binom{x}{r}$ with
$a_{r}>0$. Since $\varphi$ is integer-valued, all of the $a_{i}$ are integers,
see [14, Prop. 4.2.1]. Using Lemma 3.26 we get a representation
$\varphi(x)=\sum_{i=0}^{r}b_{i}\cdot\binom{x-c_{i}}{i}$ with
$b_{0},\ldots,b_{r}\in\IN$ and $c_{0},\ldots,c_{r}\in\IN$. For
$x\geq\max\\{c_{i}\mid 0\leq i\leq r\\}=:N$ we have that
$\binom{x-c_{i}}{i}=\binom{\max(x-c_{i},0)}{i}$ and thus
$\psi(x):=\sum_{i=0}^{r}b_{i}\cdot\binom{\max(x-c_{i},0)}{i}$ only differs
from $x\mapsto\max(\varphi(x),0)$ on finitely many inputs and is a functional
closure property of $\mathsf{\\#FA}$ by Lemmas 3.1, 3.2, 3.2 and 3.2. Lemma
3.21 then finishes off the claim.

We now have the tools available to show our claim that every ultimately PORC
function is a functional closure property of $\mathsf{\\#FA}$.

######  Lemma 3.30.

Every ultimately PORC function is a functional closure property of
$\mathsf{\\#FA}$.

######  Proof 3.31.

Let $\varphi:\IN\to\IN$ be an ultimately PORC function with period $p$
comprised of the polynomial constituents
$\varphi_{0},\ldots,\varphi_{p-1}:\IN\to\mathbb{Q}$ and $N\in\IN$, s.t. for
all $n\geq N$ we have $\varphi(n)=\varphi_{n\rem p}(n)$. Additionally let
$f\in\mathsf{\\#FA}$. We can write

$\textstyle\varphi\circ
f=\sum_{i=0}^{N-1}\mathbbm{1}_{f=i}\cdot\varphi(i)+\mathbbm{1}_{f\geq
N}\cdot(\sum_{i=0}^{p-1}\mathbbm{1}_{f\equiv_{p}i}\cdot\lfloor\max(\varphi_{i}\circ
f,0)\rfloor)\,.$

Combining Lemmas 3.1, 3.2, 3.2 and 3.2 this shows $\varphi\circ
f\in\mathsf{\\#FA}$, if we can show $\lfloor\max(\varphi_{i}\circ
f,0)\rfloor\in\mathsf{\\#FA}$ for all $i\in\\{0,\ldots,p-1\\}$. To show this
let $\alpha_{i}$ be the common denominator of the coefficients of
$\varphi_{i}$. Then $\alpha_{i}\cdot\varphi_{i}$ is a polynomial with integer
coefficients, so it in particular is an integer-valued polynomial and by Lemma
3.28 we have that $\max(\alpha_{i}\cdot\varphi_{i}\circ
f,0)\in\mathsf{\\#FA}$. Combining this with Lemma 3.2 we get that
$\left\lfloor\frac{\max(\alpha_{i}\cdot\varphi_{i}\circ
f,0)}{\alpha_{i}}\right\rfloor=\lfloor\max(\varphi_{i}\circ
f,0)\rfloor\in\mathsf{\\#FA}$.

The remainder of this section is dedicated to showing that no other functional
closure properties of $\mathsf{\\#FA}$ exist. This will make use of the
following well known algebraic interpretation of NFAs:

######  Lemma 3.32 (see [21]).

If $M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ is an NFA, then there
are matrices $A_{\sigma}\in\IN^{|Q|\times|Q|}$ for each symbol
$\sigma\in\Sigma$ and vectors $a,b\in\IN^{|Q|}$, s.t. $M$ computes
$a^{T}\cdot\left(\prod_{j=1}^{|w|}A_{w_{j}}\right)\cdot b$ for all
$w\in\Sigma^{\star}$.

######  Proof 3.33.

We index $A_{\sigma}$, $a$ and $b$ using states $q,q^{\prime}\in Q$. Choose
$(A_{\sigma})_{q,q^{\prime}}=\textup{wt}(q,\sigma,q^{\prime})$,
$a_{q}=\textup{in}(q)$ and $b_{q}=\textup{out}(q)$. It is now easy to see that
$M$ computes exactly $a^{T}\cdot\left(\prod_{j=1}^{|w|}A_{w_{j}}\right)\cdot
b$.

When restricting to a unary alphabet $\Sigma=\\{\sigma\\}$, this degenerates
the computed function to $a^{T}\cdot A_{\sigma}^{|w|}\cdot b$. In order to
analyze the behaviour of these functions we first analyze the behaviour of the
matrix power as a function in $|w|$ in the next two lemmas. Their proofs can
be found in the appendix.

######  Lemma 3.34.

Let $A\in\IN^{k\times k}$. Then any diagonal entry of $A^{n}$ is a function
$f:\IN\to\IN$ with one of the following properties:

  1. 1.

$f(n)=0$ for all $n\in\IN\setminus\\{0\\}$ and $f(0)=1$.

  2. 2.

There is a $p\in\IN\setminus\\{0\\}$, such that for all $n\in\IN$ we have
$f(n)=\mathbbm{1}_{n\equiv_{p}0}$.

  3. 3.

There is a $p\in\IN\setminus\\{0\\}$ and a function $g\in 2^{\Theta(n)}$, such
that for all $n\in\IN$ we have $f(n)=\mathbbm{1}_{n\equiv_{p}0}\cdot g(n)$.

These naturally correspond to vertices $v$ in the multigraph defined by the
adjacency matrix $A$ with

  1. 1.

no paths from $v$ to $v$.

  2. 2.

exactly one path from $v$ to $v$ of length $p$.

  3. 3.

multiple walks from $v$ to $v$ where the lengths of all the walks from $v$ to
$v$ have gcd $p$.

We can then lift this result to all entries of $A^{n}$.

######  Lemma 3.35.

If $A\in\IN^{k\times k}$, then each entry of $A^{n}$ is an ultimately almost
PORC function.

######  Theorem 3.36 (Classification of univariate functional closure
properties of $\mathsf{\\#FA}$).

A function $\varphi:\IN\to\IN$ is a functional closure property of
$\mathsf{\\#FA}$ iff $\varphi$ is an ultimately PORC function. This even holds
when $\mathsf{\\#FA}$ is restricted to unary languages.

######  Proof 3.37.

$S$$A$$1$ $1$ $1$

$S$$1,1$

Figure 1: NFAs computing the functions $1^{n}\mapsto n$ and $1^{n}\mapsto
2^{n}$ respectively. Edges with a multiplicity of $2$ are denoted by listing
the edge label twice.

Lemma 3.30 already shows that every ultimately PORC function is a closure
property of $\mathsf{\\#FA}$. It remains to show that all functional closure
properties of $\mathsf{\\#FA}$ are ultimately PORC functions. For this let
$\varphi:\IN\to\IN$ be a functional closure property of $\mathsf{\\#FA}$. The
function $f:\\{1\\}^{\star}\to\IN$ defined by $f(1^{n})=n$ is computed by the
left NFA in Figure 1 and thus in $\mathsf{\\#FA}$. Consequently $\varphi\circ
f\in\mathsf{\\#FA}$. Let $M=(Q,\\{1\\},\textup{wt},\textup{in},\textup{out})$
be an NFA computing $\varphi\circ f$. By Lemma 3.32 this NFA induces a
transition matrix $A\in\IN^{|Q|\times|Q|}$ and vectors $a,b\in\IN^{|Q|}$, s.t.
$a^{T}A^{n}b=\varphi(f(1^{n}))=\varphi(n)$ for all $n\in\IN$. Every entry of
$A^{n}$ is an ultimately almost PORC function by Lemma 3.35 and thus
$a^{T}A^{n}b=\varphi(n)$ is one as well. Let $p$ be the quasiperiod of
$\varphi$ and let $\varphi_{i}$ be one of the constituents of $\varphi$
corresponding to some residue class $i\in\\{0,\ldots,p-1\\}$. Assume for the
sake of contradiction that $\varphi_{i}$ grows in $2^{\Theta(n)}$, i.e. there
is a constant $\gamma\in\mathbb{R}^{+}$ and $N\in\IN$, s.t. for every $n\geq
N$ we have $\varphi_{i}(n)\geq 2^{\gamma n}$. Consider the function
$f_{p,i}:\\{1\\}^{\star}\to\IN$ defined by $f_{p,i}(1^{n})=p\cdot(2^{n}+N)+i$.
We claim $f_{p,i}$ is in $\mathsf{\\#FA}$. The function $1^{n}\mapsto 2^{n}$
is computed by the right NFA in Figure 1 and thus in $\mathsf{\\#FA}$. The
remainder of the claim follows by Lemma 3.1 and Lemma 3.2. Note that
$f_{p,i}(1^{n})\equiv_{p}i$, so $\varphi\circ f_{p,i}=\varphi_{i}\circ
f_{p,i}$ has to be in $\mathsf{\\#FA}$ as well. Furthermore
$\varphi(f_{p,i}(1^{n}))=\varphi_{i}(f_{p,i}(1^{n}))=\varphi_{i}(p\cdot(2^{n}+N)+i)\geq
2^{\gamma p\cdot(2^{n}+N)+\gamma i}$ for all $n\in\IN$ which is larger than
any NFA can compute, since NFAs can only compute functions that are at most
linearly exponential in the length of the input. We conclude that none of the
constituents $\varphi_{i}$ of $\varphi$ can be exponential, so they are
instead all polynomials, making $\varphi$ an ultimately PORC function.

###  3.2 Multivariate functional closure properties

######  Theorem 3.38 (Classification of multivariate functional closure
properties of $\mathsf{\\#FA}$).

A function $\varphi:\IN^{m}\to\IN$ is a functional closure property of
$\mathsf{\\#FA}$ iff $\varphi$ can be written as a finite sum of finite
products of univariate ultimately PORC functions.

######  Proof 3.39.

By Theorem 3.36 any univariate ultimately PORC function is a closure property
of $\mathsf{\\#FA}$. As such any finite sum or finite product of them is also
a closure property of $\mathsf{\\#FA}$ by Lemmas 3.1 and 3.2.

It remains to show that all functional closure properties of $\mathsf{\\#FA}$
are of this form. For this let $\varphi:\IN^{m}\to\IN$ be a functional closure
property of $\mathsf{\\#FA}$. Define the alphabet
$\Sigma=\\{\sigma_{1},\ldots,\sigma_{m}\\}$ and the functions
$f_{i}:\Sigma^{\star}\to\IN$ where $f_{i}(w):=\\#_{i}(w)$ is defined as the
number of occurences $\\#_{i}(w)$ of the symbol $\sigma_{i}$ in $w$. Applying
the closure property to $f_{1},\ldots,f_{m}$ gives that
$\varphi\circ(f_{1},\ldots,f_{m})\in\mathsf{\\#FA}$ and thus is computed by an
NFA $M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$. This induces
transition matrices $A_{\sigma}\in\IN^{|Q|\times|Q|}$ for each symbol
$\sigma\in\Sigma$ and vectors $a,b\in\IN^{|Q|}$, s.t.
$a^{T}\prod_{j=1}^{|w|}A_{w_{j}}b=\varphi(f_{1}(w),\ldots,f_{m}(w))$ for all
$w\in\Sigma^{\star}$. Restricting to words of the form
$w=\sigma_{1}^{n_{1}}\sigma_{2}^{n_{2}}\cdots\sigma_{m}^{n_{m}}$ for
$n_{1},\ldots,n_{m}\in\IN$ gives
$a^{T}\left(\prod_{i=1}^{m}A_{\sigma_{i}}^{n_{i}}\right)b=\varphi(n_{1},\ldots,n_{m})$.
Using Lemma 3.35 on each of the $A_{\sigma_{i}}^{n_{i}}$ we see that every
entry of $A_{\sigma_{i}}^{n_{i}}$ is an ultimately almost PORC function in
$n_{i}$. Consequently, every entry of $\prod_{i=1}^{m}A_{\sigma_{i}}^{n_{i}}$
is a finite sum of products of different ultimately almost PORC functions and
the same holds for
$a^{T}\left(\prod_{i=1}^{m}A_{\sigma_{i}}^{n_{i}}\right)b=\varphi(n_{1},\ldots,n_{m})$.

We now look at the individual summands of $\varphi$ and prove that we can
rewrite each one as a product of ultimately PORC functions by one-by-one
rewriting the exponential constituents. For this let
$\varphi^{(1)}(n_{1})\cdots\varphi^{(m)}(n_{m})$ be one of the summands of
$\varphi$ where $\varphi^{(1)},\ldots,\varphi^{(m)}$ are all ultimately almost
PORC functions, with periods $p_{1},\ldots,p_{m}$, offsets
$N_{1},\ldots,N_{m}$ and constituents
$\varphi^{(i)}_{0},\ldots,\varphi^{(i)}_{p_{i}-1}$ for each $i\in[m]$. If none
of the constituents are exponential we are done. Otherwise let
$\varphi^{(i)}_{j}$ be one of the exponential constituents, let
$\gamma\in\mathbb{R}^{+}$ and let $N\in\IN$, s.t.
$\varphi^{(i)}_{j}(n_{i})\geq 2^{\gamma n_{i}}$ for $n_{i}\geq N$. We claim we
can set $\varphi^{(i)}_{j}(n_{i})=0$ without changing the product
$\varphi^{(1)}(n_{1})\cdots\varphi^{(m)}(n_{m})$ for any
$n_{1},\ldots,n_{m}\in\IN$. Call the resulting functions $\psi^{(i)}$ and
$\psi^{(i)}_{j}$. Assume for the sake of contradiction, that there are some
$c_{1},\ldots,c_{m}\in\IN$ where
$\varphi^{(1)}(c_{1})\cdots\varphi^{(m)}(c_{m})\neq\varphi^{(1)}(c_{1})\cdots\varphi^{(i-1)}(c_{i-1})\cdot\psi^{(i)}(c_{i})\cdot\varphi^{(i+1)}(c_{i+1})\cdots\varphi^{(m)}(c_{m})$.
This implies that
$\varphi^{(1)}(c_{1})\cdots\varphi^{(i-1)}(c_{i-1})\cdot\varphi^{(i+1)}(c_{i+1})\cdots\varphi^{(m)}(c_{m})\neq
0$ and $c_{i}\geq N_{i}$ as we didn’t change any other functions except
$\varphi^{(i)}$ for $n_{i}\geq N_{i}$.

Constructing constant functions $f^{\prime}_{k}(w)=c_{k}$ for $k\neq i$ and
the function $f^{\prime}_{i}(w)=p_{i}\cdot(2^{|x|}+\max(N_{i},N))+j$ which are
all in $\mathsf{\\#FA}$. We see that
$\varphi\circ(f^{\prime}_{1},\ldots,f^{\prime}_{m})\in\mathsf{\\#FA}$. Note
that for any $w\in\Sigma^{\star}$ we have $f^{\prime}_{i}(w)\geq\max(N_{i},N)$
and $f^{\prime}_{i}(w)\equiv_{p_{i}}j$ and thus $\varphi^{(i)}\circ
f^{\prime}_{i}=\psi^{(i)}_{j}\circ f^{\prime}_{i}$. Combining all of this we
again reach a contradiction to the fact that NFAs can only compute at most
linearly exponential functions via

$\displaystyle\varphi(f^{\prime}_{1}(w),\ldots,f^{\prime}_{m}(w))$
$\displaystyle\geq\varphi^{(1)}(c_{1})\cdots\varphi^{(i-1)}(c_{i-1})\cdot\varphi^{(i)}(f^{\prime}_{i}(w))\cdot\varphi^{(i+1)}(c_{i+1})\cdots\varphi^{(m)}(c_{m})$
$\displaystyle\geq\varphi^{(i)}(f^{\prime}_{i}(w))\ =\
\varphi^{(i)}_{j}(f^{\prime}_{i}(w))\ =\
\varphi^{(i)}_{j}(p_{i}\cdot(2^{|w|}+\max(N_{i},N))+j)$ $\displaystyle\geq
2^{\gamma p_{i}\cdot(2^{|w|}+\max(N_{i},N))+\gamma j}\,.$

Note that the first inequality holds due to all summands of $\varphi$ being
non-negative.

Deciding whether a function $\varphi$ has such a representation may not always
be directly visible, however if $\varphi$ is a multivariate polynomial we can
be more explicit. Every integer-valued multivariate polynomial has integer
coefficients when represented in the binomial basis (see [14, Prop. 4.2.1] for
a proof of this fact). We say a term
$a\cdot\binom{x_{1}}{d_{1}}\cdots\binom{x_{m}}{d_{m}}$ dominates another term
$a^{\prime}\cdot\binom{x_{1}}{d^{\prime}_{1}}\cdots\binom{x_{m}}{d^{\prime}_{m}}$
if $d_{i}\geq d^{\prime}_{i}$ for all $i\in[m]$. A term is a dominating term
of $\varphi$ if it has non-zero coefficient and it is not dominated by any
other term with non-zero coefficient. We can use a similar approach to Lemma
3.26 to rewrite $\varphi$ as a positive integer linear combination of products
of shifted binomials (details can be found in the appendix).

######  Lemma 3.40.

Let
$\varphi(x_{1},\ldots,x_{m})=\sum_{i=1}^{r}a_{i}\cdot\prod_{j=1}^{m}\binom{x_{j}}{d_{i,j}}$
with $a_{i}\in\mathbb{Z}$ and the coefficients of the dominating terms being
positive. Then there are $a^{\prime}_{1},\ldots,a^{\prime}_{r^{\prime}}\in\IN$
and $c_{1},\ldots,c_{r^{\prime}}\in\IN$ with
$\varphi(x_{1},\ldots,x_{m})=\sum_{i=1}^{r^{\prime}}a^{\prime}_{i}\cdot\prod_{j=1}^{m}\binom{x_{j}-c_{i}}{d_{i,j}}$.

We can then use a generalization of Lemma 3.28 and replace subtractions
$x_{i}-c^{\prime}$ by $\max(x_{i}-c^{\prime},0)$. However special care has to
be taken for $x_{i}<c^{\prime}$, in which case $x_{i}$ has to be replaced by
the corresponding constants first. This adds the additional condition on
$\varphi$.

######  Lemma 3.41.

Let $\varphi:\IN^{m}\to\IN$ be a multivariate polynomial with rational
coefficients, such that whenever $\psi$ is formed from $\varphi$ by replacing
any set of variables – including the empty subset – by constants from $\IN$,
then all dominating terms of $\psi$ have positive coefficients. Then $\varphi$
is a functional closure property of $\mathsf{\\#FA}$.

######  Lemma 3.42.

A multivariate polynomial $\varphi:\IN^{m}\to\IN$ with rational coefficients
is a functional closure property of $\mathsf{\\#FA}$ iff for every $\psi$ that
can be formed from $\varphi$ by replacing any subset of variables – including
the empty set – by constants from $\IN$, then all dominating terms of $\psi$
have positive coefficients.

######  Proof 3.43.

Lemma 3.41 already proves that all multivariate polynomials of this form are
functional closure properties of $\mathsf{\\#FA}$. Now let
$\varphi:\IN^{m}\to\IN$ be a multivariate polynomial with rational coefficient
and a functional closure property of $\mathsf{\\#FA}$. By Theorem 3.38
$\varphi$ can be written as a finite sum of finite products of ultimately PORC
functions. Note that the leading coefficient of each constituent of these
ultimately PORC functions is positive. By multivariate polynomial
interpolation we can now show that $\varphi$ is already a finite sum of finite
products of these constituents. The dominating terms of $\varphi$ are then
formed by products of the leading coefficients of the constituents and thus
are positive.

##  4 Promise closure properties

######  Definition 4.1.

Let $S\subseteq\IN^{m}$ and let $\varphi:\IN^{m}\to\IN$ be a function. We call
$\varphi$ a _functional promise closure property_ of $\mathsf{\\#FA}$ with
regard to $S$ if for every $f_{1},\ldots,f_{m}\in\mathsf{\\#FA}$ defined on
some shared alphabet $\Sigma$ there is a function $g\in\mathsf{\\#FA}$ with
$g(w)=\varphi(f_{1}(w),\ldots,f_{m}(w))$ for every $w\in\Sigma^{\star}$ for
which $(f_{1}(w),\ldots,f_{m}(w))\in S$.

We now want to show that if $S$ fulfils some property, namely admitting
polynomial cluster sequences (we postpone the definition to Definition 4.6),
then for every functional promise closure property with regard to $S$ there is
a functional closure property of $\mathsf{\\#FA}$ that agrees with it on all
tuples in $S$. In other words we can interpolate the functional promise
closure property $\varphi$ on all values of $S$ to obtain a functional closure
property $\varphi^{\prime}$ for all of $\mathsf{\\#FA}$. The proof for this
follows along the following ideas: First, similar to Theorem 3.38, use the
functional closure property $\varphi$ on the unary counting functions to find
an equivalent function $\varphi^{\prime}$ that is almost a functional closure
property. However after this step some of the constituents of the ultimately
almost PORC functions might still be exponential. Theorem 3.38 then proceeded
by showing that we can replace all these exponential constituents by the
constant zero function, as otherwise we were able to reach a contradiction by
constructing functions $f^{\prime}_{1},\ldots,f^{\prime}_{m}$ and an infinite
sequence of inputs $w^{(i)}$, such that
$\varphi(f^{\prime}_{1}(w^{(i)}),\ldots,f^{\prime}_{m}(w^{(i)}))$ grows doubly
exponential in the length of the inputs. However when dealing with functional
promise closure properties we have to be more careful when choosing
$f^{\prime}_{1},\ldots,f^{\prime}_{m}$ and the $w^{(i)}$, because we need
$(f^{\prime}_{1}(w^{(i)}),\ldots,f^{\prime}_{m}(w^{(i)}))\in S$ to reach a
contradiction. Additionally we don’t replace the exponential constituents by
the constant zero-function but rather a polynomial that behaves the same for
small inputs. For this we need a special variant of univariate polynomial
interpolation that yields integer-valued polynomials that are non-negative for
all inputs from $\IN$:

######  Lemma 4.2.

Let $c_{0},\ldots,c_{N}\in\IN$. Then there is an integer-valued polynomial
$q:\mathbb{Q}\to\mathbb{Q}$ with $q(n)=c_{n}$ for all $n\in\\{0,\ldots,N\\}$
and $q(n^{\prime})\geq 0$ for all $n^{\prime}\in\IN$.

To be able to hit all of $S$ consistently we use independent binary encodings,
that allow us to hit all of $\IN^{m}$.

######  Lemma 4.3 (Folklore).

The function $f:\\{0,1\\}^{\star}\to\IN$ defined by being the value of
$w\in\\{0,1\\}^{\star}$ interpreted as a binary number is in $\mathsf{\\#FA}$.
Additionally it is possible to extend the domain of $f$ to any alphabet
$\Sigma\supseteq\\{0,1\\}$ where the value of $f$ is determined while ignoring
any symbols not in $\\{0,1\\}$.

For any $n\in\IN$ we denote by $\textup{bin}(n)$ the unique binary
representation of $n$ without leading zeros. We first show the methodology in
detail by proving the univariate case.

######  Theorem 4.4.

Let $S\subseteq\IN$. Then any function $\varphi:\IN\to\IN$ is a functional
promise closure property of $\mathsf{\\#FA}$ with regard to $S$ iff there is a
functional closure property $\psi:\IN\to\IN$ of $\mathsf{\\#FA}$ with
$\varphi_{|S}=\psi_{|S}$.

######  Proof 4.5.

If such a $\psi$ exists, we directly see that $\varphi$ is a functional
promise closure property of $\mathsf{\\#FA}$ with respect to $S$. Indeed for
any $f\in\mathsf{\\#FA}$ we construct $g=\psi\circ f\in\mathsf{\\#FA}$ and see
$g(w)=\varphi(f(w))$ for every $w\in\Sigma^{\star}$ with $f(w)\in S$.

Now on the other hand let $\varphi$ be any functional promise closure property
of $\mathsf{\\#FA}$ with regard to $S$. Again define the alphabet
$\Sigma=\\{1\\}$ and the function $f:\Sigma^{\star}\to\IN$ with $f(1^{n}):=n$.
Applying the closure property to $f$ gives that there is some
$g\in\mathsf{\\#FA}$ with $g(1^{n})=\varphi(f(1^{n}))=\varphi(n)$ for all
$n\in S$. Let $M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ be an NFA
computing $g$. This induces a transition matrix $A\in\IN^{|Q|\times|Q|}$ and
vectors $a,b\in\IN^{|Q|}$, s.t. $a^{T}A^{n}b=g(1^{n})$ for all $n\in\IN$ by
Lemma 3.32. We now define $\chi(n):=a^{T}A^{n}b$ and see
$\chi_{|S}=\varphi_{|S}$. Using Lemma 3.35 on $A^{n}$ we see that every entry
of $A^{n}$ is an ultimately almost PORC function in $n$ and as such $\psi$ is
also an ultimately almost PORC function. Let $p$ be the quasiperiod of $\chi$
and let $\chi_{0},\ldots,\chi_{p-1}$ be the constituents of $\chi$ and let
$N\in\IN$ be the offset after which $\chi$ is defined by the constituents.

We claim that we can now replace every exponential constituent by a polynomial
one without changing the value of $\chi$ for any $n\in S$. For each
$i\in\\{0,\ldots,p-1\\}$ we distinguish two cases, depending on whether
$S_{i}:=S\cap(p\mathbb{Z}+i)$ is finite or it is infinite. If $S_{i}$ is a
finite set, we replace $\chi^{\prime}_{i}$ with a polynomial that interpolates
the same values as $\chi_{i}$ on $S_{i}$. Lemma 4.2 ensures that this
polynomial is integer-valued and non-negative for all of $\IN$. If $S_{i}$ is
an infinite set, we replace $\chi_{i}$ by the constant zero function. Call the
resulting ultimately PORC function $\psi$ with constituents $\psi_{i}$. Assume
for the sake of contradiction there is an $c\in S$, s.t. $\chi(c)\neq\psi(c)$.
Clearly such a $c$ would have to be at least $N$. Now let $i$ be, s.t. $c\in
S_{i}$. It must hold that $\chi_{i}(c)\neq\psi_{i}(c)$. Hence $S_{i}$ cannot
be a finite set, since $\chi_{i}$ and $\psi_{i}$ agree on $S_{i}$. Therefore
$S_{i}$ must be infinite. Since $\chi_{i}$ is exponential there is a
$\gamma\in\mathbb{R}^{+}$ and $N^{\prime}\in\IN$, s.t. $\chi_{i}(n)\geq
2^{\gamma n}$ for all $n\geq N^{\prime}$. Let $f^{\prime}\in\mathsf{\\#FA}$ be
the function of binary evaluation from Lemma 4.3 over the alphabet
$\Sigma^{\prime}=\\{0,1\\}$. Then there is a $g^{\prime}\in\mathsf{\\#FA}$
with
$g^{\prime}(\textup{bin}(n))=\varphi(f^{\prime}(\textup{bin}(n)))=\chi(f^{\prime}(\textup{bin}(n)))$
for all $n\in S$. Since $S_{i}$ is infinite, in particular $S_{i}$ must
contain infinitely many values bigger than $\max(N,N^{\prime})$. For $n\in
S_{i}$ with $n\geq\max(N,N^{\prime})$ we now have

$\displaystyle
g^{\prime}(\textup{bin}(n))=\chi(f^{\prime}(\textup{bin}(n)))=\chi(n)=\chi_{i}(n)\geq
2^{\gamma n}\geq 2^{\gamma 2^{|\textup{bin}(n)|-1}},$

which is a contradiction to NFAs only being able to only compute functions
that are at most linearly exponential in the input length. In conclusion
$S_{i}$ cannot be infinite either and thus $c$ itself cannot exist.

######  Definition 4.6.

A set $S\subseteq\IN^{m}$ admits _polynomial cluster sequences_ if for every
$N_{1},\ldots,N_{m}\in\IN$, and $p_{1},\ldots,p_{m}\in\IN$ the projection
$\tau:S\to\\{0,\ldots,N_{1}+p_{1}-1\\}\times\ldots\times\\{0,\ldots,N_{m}+p_{m}-1\\}$
defined by $\tau(n_{1},\ldots
n_{m})=(n_{1}\operatorname{srem}_{N_{1}}p_{1},\ldots,n_{m}\operatorname{srem}_{N_{m}}p_{m})$
has the following property: Any preimage $T$ of a singleton set under $\tau$
for every $i\in[m]$ has either bounded $i$-th coordinate or there is a
polynomial $q:\IN\to\IN$ and an infinite subset $T^{\prime}\subseteq T$ with
unbounded $i$-th coordinate999note that this property also follows directly
from the polynomial bound on the other coordinates in the $i$-th coordinate,
but we have it as part of the definition for clarity. and with
$\sum_{j=1}^{m}n_{j}\leq q(n_{i})$ for all $(n_{1},\ldots,n_{m})\in
T^{\prime}$. We call such an infinite subset a _polynomial cluster sequence_
with regards to dimension $i$.

We call $\tau$ the _shifted grid projection_ of $S$ with respect to offsets
$N_{1},\ldots,N_{m}$ and quasiperiods $p_{1},\ldots,p_{m}$.

Intuitively this definition requires that each dimension is either bounded or
can grow reasonably quickly together with the other dimensions, even when
restricted to inputs from specific shifted residue classes. For example
$\\{(n^{2},n^{3})\mid n\in\IN\\}$ admits polynomial cluster sequences, while
$\\{(n,2^{n})\mid n\in\IN\\}$ does not.

######  Theorem 4.7.

Let $S\subseteq\IN^{m}$ admit polynomial cluster sequences. Then any function
$\varphi:\IN^{m}\to\IN$ is a functional promise closure property of
$\mathsf{\\#FA}$ with regard to $S$ iff there is a functional closure property
$\psi:\IN^{m}\to\IN$ of $\mathsf{\\#FA}$ with $\varphi_{|S}=\psi_{|S}$.

The technical proof of the theorem can be found in the appendix. There are
multiple natural families for the set $S$ such that $S$ admits polynomial
cluster sequences which we describe in the following.

######  Lemma 4.8.

Any finite set $S\subseteq\IN^{m}$ admits polynomial cluster sequences.

######  Proof 4.9.

Independent of the offsets and quasiperiods and $i\in[m]$ any subset of $S$
always is finite and thus bounded in every dimension.

An affine variety is defined as the zero set of a finite number of
multivariate polynomials. A special case of affine varieties are _graph
varieties_ (also just called _graphs_ , see [22, §2.4, Exe. 12]). An affine
variety $S$ is a graph variety if there exist a finite number of $j$-variate
polynomials $\mu_{1},\ldots,\mu_{k}$ such that
$S=\\{(s_{1},\ldots,s_{j},\mu_{1}(s_{1},\ldots,s_{j}),\ldots,\mu_{k}(s_{1},\ldots,s_{j}))\mid(s_{1},\ldots,s_{j})\in\mathbb{Q}^{j}\\}\subseteq\mathbb{Q}^{j+k}$.
We call $s_{1},\ldots,s_{j}$ the _free_ variables, and the remaining variables
the _dependent_ variables. We call $S$ a monotone graph variety if
$\mu_{1},\ldots,\mu_{k}$ are all monotone.

######  Lemma 4.10.

Let $S\subseteq\mathbb{Q}^{m}=\mathbb{Q}^{j+k}$ be a monotone graph variety.
Then the set $S\cap\IN^{m}=\IN^{j+k}$ admits polynomial cluster sequences.

The proof of this lemma can be found in the appendix. All in all this combines
to the following theorem which characterizes the special case of multivariate
polynomial functional promise closure properties, the technical details can be
found in the appendix.

######  Theorem 4.11.

Let $S\subseteq\mathbb{Q}^{m}=\mathbb{Q}^{j+k}$ be a monotone graph variety
and let $I=I(S)$ be its vanishing ideal. A multivariate polynomial
$\varphi:S\to\IN$ is a functional promise closure property of $\mathsf{\\#FA}$
with regard to $S$ if and only if there exists a $\psi\in I$ such that
$\varphi+\psi$ is a multivariate functional closure property of
$\mathsf{\\#FA}$.

##  5 Conclusion

We characterized the functional closure properties of $\mathsf{\\#FA}$ to be
precisely the ultimately PORC functions in the univariate case and
combinations of ultimately PORC functions in the multivariate case.
Additionally we characterize promise functional closure properties of
$\mathsf{\\#FA}$ with regard to some natural families of sets $S$. Natural
further directions of research are now whether we can characterize the promise
functional closure properties of $\mathsf{\\#FA}$ for more sets $S$ and
whether our methods can be applied to characterize functional closure
properties for more powerful models of computation.

## References

  * [1] Rudolf Ahlswede and David E Daykin.  An inequality for the weights of two families of sets, their unions and intersections.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 43:183–185, 1978.
  * [2] Noga Alon and Joel H Spencer.  The probabilistic method.  John Wiley & Sons, 2016.
  * [3] Matthias Beck and Sinai Robins.  Computing the continuous discretely, volume 61.  Springer, 2007.
  * [4] Edwin F Beckenbach and Richard Bellman.  Inequalities.  Springer, Berlin, 1961.
  * [5] Richard Beigel.  Closure properties of GapP and #P.  In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pages 144–146. IEEE, 1997.
  * [6] Swee Hong Chan and Igor Pak.  Computational complexity of counting coincidences.  2023\.
  * [7] Swee Hong Chan and Igor Pak.  Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy.  2023\.
  * [8] David Cox, John Little, and Donal O’Shea.  Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra.  Springer Science & Business Media, 2013.
  * [9] Manfred Droste, Werner Kuich, and Heiko Vogler.  Handbook of weighted automata.  Springer Science & Business Media, 2009.
  * [10] Manfred Droste and Dietrich Kuske.  Weighted automata.  pages 113–150.  in _Handbook of Automata Theory_ , European Mathematical Society.
  * [11] Mariano Gasca and Thomas Sauer.  Polynomial interpolation in several variables.  Advances in Computational Mathematics, 12:377–410, 2000.
  * [12] HG Hardy, JE Littlewood, and G. Pólya.  Inequalities.  Cambridge University Press, 1952.
  * [13] Ulrich Hertrampf, Heribert Vollmer, and Klaus W Wagner.  On the power of number-theoretic operations with respect to counting.  In Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, pages 299–314. IEEE, 1995.
  * [14] Christian Ikenmeyer and Igor Pak.  What is in #P and what is not?  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 860–871. IEEE, 2022.
  * [15] Christian Ikenmeyer, Igor Pak, and Greta Panova.  Positivity of the symmetric group characters is as hard as the polynomial time hierarchy.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3573–3586. SIAM, 2023.
  * [16] Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur.  Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton.  Theoretical Computer Science, 327(3):349–373, 2004.
  * [17] Igor Pak.  Complexity problems in enumerative combinatorics.  In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3153–3180. World Scientific, 2018.
  * [18] Igor Pak.  Combinatorial inequalities.  Notices of the AMS, 66(7), August 2019.
  * [19] Igor Pak.  What is a combinatorial interpretation?  to appear: Proc. Open Problems in Algebraic Combinatorics. https://www.samuelfhopkins.com/OPAC/files/proceedings/pak.pdf, 2022.
  * [20] J Peterson.  Beviser for wilsons og fermats theoremer.  Tidsskrift for mathematik, 2:64–65, 1872.
  * [21] Marcel Paul Schützenberger.  On the definition of a family of automata.  Inf. Control., 4(2-3):245–270, 1961.
  * [22] Igor R Shafarevich.  Basic algebraic geometry 1: Varieties in projective space.  Springer Science & Business Media, 3 edition, 2013.
  * [23] Michael Spivey.  The Chu-Vandermonde identity via Leibniz’s identity for derivatives.  The College Mathematics Journal, 47(3):219–220, 2016.
  * [24] Richard P Stanley.  Positivity problems and conjectures in algebraic combinatorics.  Mathematics: frontiers and perspectives, 295:319, 1999.

##  Appendix A Appendix: Missing proofs

###  A.1 Missing proofs from section 2

######  Proof A.1 (Proof of Lemma 2.3).

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$ be
an NFA computing $f$. We construct
$M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ with

$\displaystyle Q$
$\displaystyle=Q_{f}\times[\max(\operatorname{im}\textup{wt}_{f}\cup\operatorname{im}\textup{in}_{f})]\times[\max(\operatorname{im}\textup{out}_{f})]$
$\displaystyle\textup{wt}((q,\alpha,\beta),\sigma,(q^{\prime},\alpha^{\prime},\beta^{\prime}))$
$\displaystyle=\begin{cases}1&\text{if
$\alpha^{\prime}\leq\textup{wt}_{f}(q,\sigma,q^{\prime})$ and $\beta=1$}\\\
0&\text{otherwise}\\\ \end{cases}$
$\displaystyle\textup{in}((q,\alpha,\beta))$
$\displaystyle=\begin{cases}1&\text{if $\alpha\leq\textup{in}_{f}(q)$}\\\
0&\text{otherwise}\\\ \end{cases}$
$\displaystyle\textup{out}((q,\alpha,\beta))$
$\displaystyle=\begin{cases}1&\text{if $\beta\leq\textup{out}_{f}(q)$}\\\
0&\text{otherwise}\\\ \end{cases}$

Intuitively $M$ consists of multiple identical copies of $M_{f}$, where all
the weights are handled explicitly as separate computations.

Fix any word $w=w_{1}\ldots w_{n}\in\Sigma^{\star}$. Let $P=q_{0}q_{1}\ldots
q_{n}$ be a computation of $M_{f}$ on $w$. Then for
$\alpha_{0}\in[\textup{in}_{f}(q_{0})]$ and
$\alpha_{i}\in[\textup{wt}(q_{i-1},w_{i},q_{i})]$ for $i\in[n]$ and
$\beta_{0}=\beta_{1}=\ldots=\beta_{n-1}=1$ and
$\beta_{n}\in\textup{out}_{f}(q_{n})$ we have that
$P^{\prime}:=(q_{0},\alpha_{0},\beta_{0})(q_{1},\alpha_{1},\beta_{1})\ldots(q_{n},\alpha_{n},\beta_{n})$
is a computation of $M$ on $w$ of weight exactly $1$ while any other choices
of the $\alpha_{i}$ and $\beta_{i}$ would lead to a computation of weight $0$.
In particular there are
$\textup{in}_{f}(q_{0})\cdot\prod_{i=1}^{n}\textup{wt}_{f}(q_{i-1},w_{i},q_{i})\cdot\textup{out}_{f}(q_{0})$
non-zero computations in $M$ corresponding to $P$, which coincides with the
weight of $P$ in $M_{f}$. Additionally every computation on $M$ can be
projected onto a computation on $M_{f}$ via $(q,i,j)\mapsto q$ and thus $M$
computes $f$.

###  A.2 Missing proofs from section 3

See 3.1

######  Proof A.2.

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$
and $M_{g}=(Q_{g},\Sigma,\textup{wt}_{g},\textup{in}_{g},\textup{out}_{g})$ be
NFAs computing $f$ and $g$ respectively.

We construct the direct union NFA
$M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ with

$\displaystyle Q$ $\displaystyle=Q_{f}\dot{\cup}Q_{g}$
$\displaystyle\textup{wt}(q,\sigma,q^{\prime})$
$\displaystyle=\begin{cases}\textup{wt}_{f}(q,\sigma,q^{\prime})&\text{$q,q^{\prime}\in
Q_{f}$}\\\ \textup{wt}_{g}(q,\sigma,q^{\prime})&\text{$q,q^{\prime}\in
Q_{g}$}\\\ 0&\text{otherwise}\\\ \end{cases}$ $\displaystyle\textup{in}(q)$
$\displaystyle=\begin{cases}\textup{in}_{f}(q)&\text{if $q\in Q_{f}$}\\\
\textup{in}_{g}(q)&\text{if $q\in Q_{g}$}\\\ \end{cases}$
$\displaystyle\textup{out}(q)$
$\displaystyle=\begin{cases}\textup{out}_{f}(q)&\text{if $q\in Q_{f}$}\\\
\textup{out}_{g}(q)&\text{if $q\in Q_{g}$}\\\ \end{cases}$

Any computation with non-zero weight in $M$ is now fully contained in exactly
one of the sub-NFA equivalent to $M_{f}$ or $M_{g}$ and any computation path
on $M_{f}$ or $M_{g}$ naturally embeds into $M$ and thus $M$ computes $f+g$.

See 3.2

######  Proof A.3.

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$
and
$\textup{wt}_{g}=(Q_{g},\Sigma,\textup{wt}_{g},\textup{in}_{g},\textup{out}_{g})$
be NFAs computing $f$ and $g$ respectively. We use the product automaton
construction to construct the NFA
$M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$:

$\displaystyle Q$ $\displaystyle=Q_{f}\times Q_{g}$
$\displaystyle\textup{wt}((q_{1},q_{2}),\sigma,(q_{1}^{\prime},q_{2}^{\prime}))$
$\displaystyle=\textup{wt}_{f}(q_{1},\sigma,q_{1}^{\prime})\cdot\textup{wt}_{g}(q_{2},\sigma,q_{2}^{\prime})$
$\displaystyle\textup{in}((q_{1},q_{2}))$
$\displaystyle=\textup{in}_{f}(q_{1})\cdot\textup{in}_{g}(q_{2})$
$\displaystyle\textup{out}((q_{1},q_{2}))$
$\displaystyle=\textup{out}_{f}(q_{1})\cdot\textup{out}_{g}(q_{2})$

Fix some $w=w_{1}\ldots w_{n}\in\Sigma^{\star}$. Let
$\mathcal{P}_{f}=Q_{f}^{n+1}$ be all computations of $M_{f}$ on $w$ and let
$\mathcal{P}_{g}=Q_{g}^{n+1}$ be all computations of $M_{g}$ on $w$. Then
$\mathcal{P}_{f}\times\mathcal{P}_{g}\cong(Q_{f}\times Q_{g})^{n+1}$ are
precisely the computations of $M$ on $x$ by identifying $((q_{f,0}\ldots
q_{f,n}),(q_{g,0}\ldots q_{g,n}))$ with the computation
$(q_{f,0},q_{g,0})\ldots(q_{f,n},q_{g,n})$. Additionally the computation
$(P_{f},P_{g})\in\mathcal{P}_{f}\times\mathcal{P}_{g}$ has weight
${\mathbf{w}}((P_{f},P_{g}))={\mathbf{w}}_{f}(P_{f})\cdot{\mathbf{w}}_{g}(P_{g})$
where ${\mathbf{w}}_{f}$ and ${\mathbf{w}}_{g}$ denote the weights of
computations of $M_{f}$ and $M_{g}$ respectively. Thus we have

$\Bigl{(}\sum_{P_{f}\in\mathcal{P}_{f}}{\mathbf{w}}_{f}(P_{f})\Bigr{)}\cdot\Bigl{(}\sum_{P_{g}\in\mathcal{P}_{g}}{\mathbf{w}}_{g}(P_{g})\Bigr{)}=\sum_{P_{f}\in\mathcal{P}_{f}}\sum_{P_{g}\in\mathcal{P}_{g}}{\mathbf{w}}_{f}(P_{f})\cdot{\mathbf{w}}_{g}(P_{g})=\sum_{(P_{f},P_{g})\in\mathcal{P}_{f}\times\mathcal{P}_{g}}{\mathbf{w}}_{f}((P_{f},P_{g}))$

and $M$ computes $f\cdot g$.

See 3.7

######  Proof A.4.

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$.
We construct the NFA $M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ with
$Q=Q_{f}\times S$ and

$\displaystyle\textup{in}((q,s))$
$\displaystyle=\begin{cases}\textup{in}_{f}(q)&\text{if
$s=\textup{init}(q)$}\\\ 0&\text{otherwise}\\\ \end{cases}$
$\displaystyle\textup{out}((q,s))$
$\displaystyle=\textup{out}_{f}(q)\cdot\textup{cond}(s)$
$\displaystyle\textup{wt}((q,s),\sigma,(q^{\prime},s^{\prime}))$
$\displaystyle=\begin{cases}\textup{wt}_{f}(q,\sigma,q^{\prime})&\text{if
$s^{\prime}=\step(q,\sigma,q^{\prime},s)$}\\\ 0&\text{otherwise}\\\
\end{cases}$

Fix some $w=w_{1}\ldots w_{n}\in\Sigma^{\star}$. Any computation
$P=(q_{0},s_{0})\ldots(q_{n},s_{n})$ of $M$ on $w$ directly corresponds to the
computation $q_{0}\ldots q_{n}$ of $M_{f}$. If $s_{0}\neq\textup{init}(q_{0})$
or if $s_{i}\neq$ for any $i\in[n]$ then $P$ has weight $0$. Otherwise $P$ has
weight ${\mathbf{w}}(P)={\mathbf{w}}_{f}(q_{0}\ldots
q_{n})\cdot\textup{cond}(s_{n})={\mathbf{w}}_{f}(q_{0}\ldots q_{n})\cdot$. The
claim on the function computed by $M$ directly follows.

See 3.8

######  Proof A.7.

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$.
We construct the NFA $M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ with
$Q=Q_{f}\times S$ and

$\displaystyle\textup{in}((q,s))$ $\displaystyle=\begin{cases}1&\text{if
$s=\textup{init}(q)$}\\\ 0&\text{otherwise}\\\ \end{cases}$
$\displaystyle\textup{out}((q,s))$ $\displaystyle=\textup{cond}(s)$
$\displaystyle\textup{wt}((q,s),\sigma,(q^{\prime},s^{\prime}))$
$\displaystyle=\begin{cases}1&\text{if
$s^{\prime}=\step(q,\sigma,q^{\prime},s)$}\\\ 0&\text{otherwise}\\\
\end{cases}$

Any computation $P=(q_{0},s_{0})\ldots(q_{n},s_{n})$ of $M$ directly
corresponds to the computation $q_{0}\ldots q_{n}$ of $M_{f}$. If
$s_{0}\neq\textup{init}(q_{0})$ or if $s_{i}\neq$ for any $i\in[n]$ then $P$
has weight $0$. Otherwise $P$ has weight
${\mathbf{w}}(P)=\textup{cond}(s_{n})=$. The claim on the function computed by
$M$ directly follows.

See 3.11

######  Proof A.10.

We construct as follows:

$\displaystyle S$ $\displaystyle=Q\to\mathcal{R}$
$\displaystyle\textup{init}(q)$ $\displaystyle=r\mapsto\tau(\textup{in}(r))$
$\displaystyle=r\mapsto\textstyle\sum_{r^{\prime}\in
Q}s(r^{\prime})\cdot\tau(\textup{wt}(r^{\prime},\sigma,r))$
$\displaystyle\textup{cond}(s)$ $\displaystyle=\pi\Bigl{(}\textstyle\sum_{r\in
Q}s(r)\cdot\tau(\textup{out}(r))\Bigr{)}$

Note that and init depend on neither $q$ nor $q^{\prime}$. So for a fixed
$w=w_{1}\ldots w_{n}\in\Sigma^{\star}$ the step sequence $s_{0},\ldots,s_{n}$
collapses to $s_{0}=r\mapsto\tau(\textup{in}(r))$ and
$s_{i}=r\mapsto\sum_{r^{\prime}\in
Q}s_{i-1}(r^{\prime})\cdot\tau(\textup{wt}(r^{\prime},w_{i},r))$ for $i\in[n]$
independent of the specific computation of $N$ on $x$.

We first prove that for all $w=w_{1}\ldots w_{n}\in\Sigma^{\star}$ and $q\in
Q$ we have $s_{n}(r)=\tau(\sum_{P_{r}}{\underline{\mathbf{w}}}(P_{r}))$ where
the sum is over all computations $P_{r}=q_{0}\ldots q_{n}$ of $N$ on $w$ with
$q_{n}=r$. We prove this by induction over $n$. For $n=0$ this holds directly.
For $n>0$ we have

$\displaystyle s_{n}(r)$ $\displaystyle=\sum_{q_{n-1}\in
Q}s_{n-1}(q_{n-1})\cdot\tau(\textup{wt}(q_{n-1},w_{n},r))$
$\displaystyle=\sum_{q_{n-1}\in Q}\tau\Bigl{(}\sum_{q_{0},\ldots,q_{n-2}\in
Q}{\underline{\mathbf{w}}}(q_{0}\ldots
q_{n-1})\Bigr{)}\cdot\tau(\textup{wt}(q_{n-1},w_{n},r))$
$\displaystyle=\tau\Bigl{(}\sum_{q_{n-1}\in Q}\sum_{q_{0},\ldots,q_{n-2}\in
Q}{\underline{\mathbf{w}}}(q_{0}\ldots
q_{n-1})\cdot\textup{wt}(q_{n-1},w_{n},r)\Bigr{)}$
$\displaystyle=\tau\Bigl{(}\sum_{q_{0},\ldots,q_{n-1}\in
Q}{\underline{\mathbf{w}}}(q_{0}\ldots q_{n-1}r)\Bigr{)}\,.$

We can thus finish the proof with

$\displaystyle=\textup{cond}(s_{n})$ $\displaystyle=\pi\Bigl{(}\sum_{q_{n}\in
Q}s_{n}(r)\cdot\tau(\textup{out}(q_{n}))\Bigr{)}$
$\displaystyle=\pi\Bigl{(}\sum_{q_{n}\in
Q}\tau\Bigl{(}\sum_{q_{0},\ldots,q_{n-1}\in
Q}{\underline{\mathbf{w}}}(q_{0}\ldots
q_{n})\Bigr{)}\cdot\tau(\textup{out}(q_{n}))\Bigr{)}$
$\displaystyle=\pi\Bigl{(}\tau\Bigl{(}\sum_{q_{n}\in
Q}\sum_{q_{0},\ldots,q_{n-1}\in Q}{\underline{\mathbf{w}}}(q_{0}\ldots
q_{n})\cdot\textup{out}(q_{n})\Bigr{)}\Bigr{)}$
$\displaystyle=\pi\Bigl{(}\tau\Bigl{(}\sum_{q_{0},\ldots,q_{n}\in
Q}{\mathbf{w}}(q_{0}\ldots q_{n})\Bigr{)}\Bigr{)}\,.$

See 3.15

######  Proof A.14.

We construct as follows:

$\displaystyle S$ $\displaystyle=Q\to\mathcal{R}$
$\displaystyle\textup{init}(q)$
$\displaystyle=r\mapsto\tau(\mathbbm{1}_{r<q}\cdot\textup{in}(r))$
$\displaystyle=r\mapsto\textstyle\sum_{r^{\prime}\in
Q}s(r^{\prime})\cdot\tau(\textup{wt}(r^{\prime},\sigma,r))+\tau(\mathbbm{1}_{r<q^{\prime}}\cdot\textup{wt}(q,\sigma,r))$
$\displaystyle\textup{cond}(s)$ $\displaystyle=\pi(\textstyle\sum_{r\in
Q}\tau(\textup{out}(r))\cdot s(r))$

Fix some $w=w_{1}\ldots w_{n}\in\Sigma^{\star}$ and some computation
$P=q_{0}\ldots q_{n}$ of $N$ on $w$ of non-zero weight. This fixes the step
sequence $s_{0},\ldots,s_{n}$. We now prove by induction over $i$ that
$s_{i}(r)=\sum_{P^{\prime}}\tau({\underline{\mathbf{w}}}(P^{\prime}))$ for all
$i\in\\{0,\ldots,n\\}$ and $r\in Q$, where the sum is over all computations
$P^{\prime}=q_{0}^{\prime}\ldots q_{i}^{\prime}$ of $w_{1}\ldots w_{i}$ with
$q_{i}^{\prime}=r$ that are lexicographically smaller than $q_{0}\ldots
q_{i}$. For $i=0$ this is trivially the case since the only computations
$P^{\prime}=q_{0}^{\prime}$ that are lexicographically smaller than the
computation $q_{0}$ are the ones with $q_{0}^{\prime}<q_{0}$. For $i>0$ for a
computation $P^{\prime}=q_{0}^{\prime}\ldots q_{i}^{\prime}$ to be
lexicographically smaller than $q_{0}\ldots q_{i}$ there are two
possibilities. Either $q_{0}^{\prime}\ldots q_{i-1}^{\prime}$ is already
lexicographically smaller than $q_{0}\ldots q_{i-1}$ or $q_{0}^{\prime}\ldots
q_{i-1}^{\prime}=q_{0}\ldots q_{i-1}$ and $q_{i}^{\prime}<q_{i}$. In the
second case the weight of $P^{\prime}$ is precisely
$\textup{wt}(q_{i-1},w_{i},q_{i}^{\prime})$ since $P$ is a computation of non-
zero weight and thus weight exactly $1$. Combining all of this we can finish
the proof of the claim with a similar argument to Lemma 3.11:

$\displaystyle s_{i}(r)$ $\displaystyle=\sum_{q_{i-1}^{\prime}\in
Q}s_{i-1}(q_{i-1}^{\prime})\cdot\tau(\textup{wt}(q_{i-1}^{\prime},w_{i},r))+\tau(\mathbbm{1}_{r<q_{i}}\cdot\textup{wt}(q_{i-1},\sigma,r))$
$\displaystyle=\tau\Bigl{(}\sum_{\begin{subarray}{c}q_{0}^{\prime}\ldots
q_{i-1}^{\prime}\\\ \text{lex. smaller than}\\\ q_{0}\ldots
q_{i-1}\end{subarray}}{\underline{\mathbf{w}}}(q_{0}^{\prime}\ldots
q_{i-1}^{\prime}))\cdot\textup{wt}(q_{i-1}^{\prime},w_{i},r)\Bigr{)}+\tau(\mathbbm{1}_{r<q_{i}}\cdot{\underline{\mathbf{w}}}(q_{0}\ldots
q_{i-1}r))$
$\displaystyle=\tau\Bigl{(}\sum_{\begin{subarray}{c}q_{0}^{\prime}\ldots
q_{i-1}^{\prime}\\\ \text{lex. smaller than}\\\ q_{0}\ldots
q_{i-1}\end{subarray}}{\underline{\mathbf{w}}}(q_{0}^{\prime}\ldots
q_{i-1}^{\prime}r)+\mathbbm{1}_{r<q_{i}}\cdot{\underline{\mathbf{w}}}(q_{0}\ldots
q_{i-1}r))\Bigr{)}$
$\displaystyle=\tau\Bigl{(}\sum_{\begin{subarray}{c}q_{0}^{\prime}\ldots
q_{i-1}^{\prime}r\\\ \text{lex. smaller than}\\\ q_{0}\ldots
q_{i-1}q_{i}\end{subarray}}{\underline{\mathbf{w}}}(q_{0}^{\prime}\ldots
q_{i-1}^{\prime}r)\Bigr{)}$

The statement of this lemma then follows analogously to Lemma 3.11.

*

######  Proof A.17.

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$ be
a simple NFA computing $f$ with an arbitrary ordering $<$ on $Q_{f}$. Lemma
3.15 on the capped semiring $\mathcal{R}_{c}$ with $\pi(a)=\mathbbm{1}_{a<c}$
for all $a\in\mathcal{R}$ constructs a stepwise computation property with

for all computations $P$ of $M_{f}$ on $w$ of non-zero weight, i.e. iff $P$ is
one of the $c$ lexicographically smallest computations on $w$ with non-zero
weight. It follows that the NFA $M$ constructed by Lemma 3.7 computes
$g(w)=\min(f(w),c)$.

*

######  Proof A.18.

Let $M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$ be
a simple NFA computing $f$ with an arbitrary ordering $<$ on $Q_{f}$. Lemma
3.11 on the capped semiring $\mathcal{R}_{c+1}$ with
$\pi_{=}(a)=\mathbbm{1}_{a=c}$, $\pi_{\leq}(a)=\mathbbm{1}_{a\leq c}$ and
$\pi_{\geq}(a)=\mathbbm{1}_{a\geq c}$ for all $a\in\mathcal{R}$ constructs
stepwise computation properties , and respectively with

$\displaystyle=\begin{cases}1&\text{if the number of non-zero computations
$P^{\prime}$ on $w$ is exactly $c$}\\\ 0&\text{otherwise}\\\ \end{cases}$
$\displaystyle=\begin{cases}1&\text{if the number of non-zero computations
$P^{\prime}$ on $w$ is at most $c$}\\\ 0&\text{otherwise}\\\ \end{cases}$
$\displaystyle=\begin{cases}1&\text{if the number of non-zero computations
$P^{\prime}$ on $w$ is at least $c$}\\\ 0&\text{otherwise}\\\ \end{cases}$

for all computations $P$ of $M_{f}$ on $w$. It follows that the NFAs
$M_{=},M_{\leq}$ and $M_{\geq}$ constructed by Lemma 3.8 compute
$g_{=}(w)=\mathbbm{1}_{f(w)=c}\cdot|Q_{f}|^{|w|+1}$,
$g_{\leq}(w)=\mathbbm{1}_{f(w)\leq c}\cdot|Q_{f}|^{|w|+1}$ and
$g_{\geq}(w)=\mathbbm{1}_{f(w)\geq c}\cdot|Q_{f}|^{|w|+1}$ respectively. Since
$|Q_{f}|^{|w|+1}$ is always positive Lemma 3.2 finishes the proof with

$\displaystyle\min(g_{=}(w),1)$ $\displaystyle=\mathbbm{1}_{f(w)=c}$
$\displaystyle\min(g_{\leq}(w),1)$ $\displaystyle=\mathbbm{1}_{f(w)\leq c}$
$\displaystyle\min(g_{\geq}(w),1)$ $\displaystyle=\mathbbm{1}_{f(w)\geq c}\,.$

*

######  Proof A.19.

For $c=1$ the statement is trivially true, so let $c\geq 2$. Let
$M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$ be a
simple NFA computing $f$ with an arbitrary ordering $<$ on $Q_{f}$. We use the
finite cyclic semiring $\mathcal{R}=\mathbb{Z}_{c}$ with the usual addition
and multiplication. Lemma 3.15 with $\pi(a)=\mathbbm{1}_{a=c-1}$ for all
$a\in\mathcal{R}$ constructs a stepwise computation property with

for all computations $P$ of $M_{f}$ on $w$ of non-zero weight. It follows that
the NFA $M$ constructed by Lemma 3.7 computes
$g(w)=\left\lfloor\frac{f(w)}{c}\right\rfloor$.

*

######  Proof A.20.

For $c=1$ the statement is trivially true, so let $c\geq 2$. Let
$M_{f}=(Q_{f},\Sigma,\textup{wt}_{f},\textup{in}_{f},\textup{out}_{f})$ be a
simple NFA computing $f$ with an arbitrary ordering $<$ on $Q_{f}$. We use the
finite cyclic semiring $\mathcal{R}=\mathbb{Z}_{c}$ with the usual addition
and multiplication. Lemma 3.11 with $\pi(a)=\mathbbm{1}_{a=d}$ for all
$a\in\mathcal{R}$ constructs a stepwise computation property with

for all computations $P$ of $M_{f}$ on $w$ of non-zero weight. It follows that
the NFA $M$ constructed by Lemma 3.8 computes
$g(w)=\mathbbm{1}_{f(w)\equiv_{c}d}\cdot|Q_{f}|^{|w|+1}$. Since
$|Q_{f}|^{|w|+1}$ is always positive Lemma 3.2 finishes the proof with
$\min(g(w),1)=\mathbbm{1}_{f(w)\equiv_{c}d}$.

See 3.26

######  Proof A.21.

We prove this via induction on $r$. For $r=0$ we can choose $b_{0}=a_{0}$ and
$c_{0}=0$ to see that $\varphi$ is of the required form. For $r>0$ we choose
$b_{r}=a_{r}$ and $c_{r}=\max\\{-a_{r-1}+1,0\\}$.

We define the polynomial
$\varphi^{\prime}(x):=\varphi(x)-b_{r}\cdot\binom{x-c_{r}}{r}$ and analyze the
leading binomial $\binom{x-c_{r}}{r}$. Using the Chu-Vandermonde identity [23]
we see
$\binom{x-c_{r}}{r}=\sum_{i=0}^{r}\binom{-c_{r}}{r-i}\binom{x}{i}=\sum_{i=0}^{r}(-1)^{r-i}\binom{r-i+c_{r}-1}{r-i}\binom{x}{i}$.

Combining this with $\varphi(x)=\sum_{i=0}^{r}a_{i}\cdot\binom{x}{i}$ we see
that
$\varphi(x)-b_{r}\cdot\binom{x-c_{r}}{r}=\sum_{i=0}^{r-1}a^{\prime}_{i}\cdot\binom{x}{i}$
with $a^{\prime}_{i}=a_{i}-b_{r}\cdot(-1)^{r-i}\cdot\binom{r-i+c_{r}-1}{r-i}$.
Furthermore we have $a^{\prime}_{r-1}>0$ due to
$b_{r}\cdot(-1)^{r-(r-1)}\binom{r-(r-1)+c_{r}-1}{r-(r-1)}=-b_{r}c_{r}<a_{r-1}$.
By induction there are $b^{\prime}_{0},\ldots,b^{\prime}_{r-1}\in\IN$ and
$c^{\prime}_{0},\ldots,c^{\prime}_{r-1}\in\IN$ s.t.
$\varphi^{\prime}(x)=\sum_{i=0}^{r-1}b^{\prime}_{i}\cdot\binom{x-c^{\prime}_{i}}{i}$.
Thus by choosing $c_{i}=c^{\prime}_{i}$ and $b_{i}=b^{\prime}_{i}$ for
$i\in\\{0,\ldots,r-1\\}$ we get
$\varphi(x)=\sum_{i=0}^{r}b_{i}\cdot\binom{x-c_{i}}{i}$.

See 3.34

######  Proof A.22.

To prove the lemma, let $v$ be arbitrary and let $f_{v}(n)=(A^{n})_{vv}$. Note
that we always have $f_{v}(0)=1$ since $A^{0}$ is the identity matrix. We
split into three cases:

$f_{v}(n)=0$ for all $n>0$:

In this case we are done.

$f_{v}(n)\in\\{0,1\\}$ for all $n\in\IN$ and there is some $\ell>0$ with
$f_{v}(\ell)=1$:

Let $p\geq 1$ be minimal with $f_{v}(p)=1$. Then we directly know that for any
multiple $i\cdot p$ we have
$f_{v}(ip)=(A^{ip})_{vv}\geq((A^{p})_{vv})^{i}=f_{v}(p)^{i}=1$. In the setting
if $A$ is interpreted as the adjacency matrix of a multigraph, this
corresponds to a walk consisting of repeating the same path of length $p$ from
$v$ to itself $i$ times.

Assume for the sake of contradiction there is any other $n$ that is not a
multiple of $p$ with $f_{v}(n)=1$. Then we have that $f_{v}(n\cdot
p)=(A^{np})_{vv}\geq(A^{p})_{vv}^{n}+(A^{n})_{vv}^{p}=f_{v}(p)^{n}+f_{v}(n)^{p}=2$,
a contradiction. Going back to the graph setting, this corresponds to the
choice of either repeating a walk from $v$ to $v$ of length $n$ a total of $p$
times or repeating a walk from $v$ to $v$ of length $p$ a total of $n$ times,
leading to two different walks of length $n\cdot p$ from $v$ to $v$ since
neither does $p$ divide $n$ nor vice-versa.

There is some $\ell\in\IN$ with $f_{v}(\ell)\geq 2$:

Let $p$ be the gcd of the set $Z=\\{n\in\IN\mid f_{v}(n)\geq 1\\}$. If
$n\in\IN$ is not divisible by $p$ we directly have $f_{v}(n)=0$ since this
implies $n\notin Z$.

Additionally there is some finite subset $Z^{\prime}\subseteq Z$ with the same
gcd $p$. By Bézout’s lemma there is some $N\in\IN$ which is a multiple of $p$
s.t. that every number of the form $N+i\cdot p$ with $i\in\IN$ can be written
as a non-negative linear combination of elements from $Z^{\prime}$. Let
$n=N+i\cdot p$ for any $i\in\IN$. We can write

$\displaystyle n$
$\displaystyle=N+\underbrace{\frac{n-N-\lfloor\frac{n-N}{\ell}\rfloor\cdot\ell}{p}}_{\alpha:=}\cdot
p+\underbrace{\left\lfloor\frac{n-N}{\ell}\right\rfloor}_{\beta:=}\cdot\ell\,.$
(1)

since $\ell\in Z$ implies that $p$ divides $\ell$. Furthermore both $\alpha$
and $\beta$ are non-negative integers and $\beta$ is maximal with this
property. In particular we can write $N+\alpha\cdot p$ as a non-negative
linear combination with elements from $Z^{\prime}$. This gives $N+\alpha\cdot
p=\sum_{p_{j}\in Z^{\prime}}\kappa_{j}\cdot p_{j}$ for $\kappa_{j}\in\IN$.
Putting this together we have

$\displaystyle f_{v}(n)$ $\displaystyle=(A^{n})_{vv}$
$\displaystyle=(A^{N+\alpha\cdot p+\beta\cdot\ell})_{vv}$
$\displaystyle=(A^{\sum_{p_{j}\in Z^{\prime}}\kappa_{j}\cdot
p_{j}+\beta\cdot\ell})_{vv}$
$\displaystyle\geq(A^{\beta\cdot\ell})_{vv}\cdot\prod_{p_{j}\in
Z^{\prime}}(A^{\kappa_{j}\cdot p_{j}})_{vv}$
$\displaystyle\geq(A^{\ell})_{vv}^{\beta}\cdot\prod_{p_{j}\in
Z^{\prime}}(A^{p_{j}})_{vv}^{\kappa_{j}}$
$\displaystyle=f_{v}(\ell)^{\beta}\cdot\prod_{p_{j}\in
Z^{\prime}}f_{v}(p_{j})^{\kappa_{j}}$ $\displaystyle\geq f_{v}(\ell)^{\beta}$
$\displaystyle\geq 2^{\beta}$ $\displaystyle\geq 2^{\frac{n-N}{\ell}-1}\in
2^{\Omega(n)}$

Note that no entry in $A^{n}$ can grow faster than linearly exponential, so
this lower bound directly induces a function $g_{v}\in 2^{\Theta(n)}$ rather
than a function $g_{v}\in 2^{\Omega(n)}$.

In the graph setting this corresponds to repeating different walks from $v$ to
$v$ of length $\ell$ for most of the walk, thus accumulating a linearly
exponential amount of different walks and then finishing with some bounded
amount of walks from $v$ to $v$ with lengths in $Z^{\prime}$.

See 3.35

######  Proof A.23.

We use the description of the diagonal entries of the matrices $A_{S}^{n}$
given by Lemma 3.34 for all sets $S\subseteq[k]$ where $A_{S}$ is the matrix
$A$ obtained by removing the rows and columns given by $S$. These correspond
to the number of walks of length $n$ from a vertex $v$ to itself in the
multigraph associated with the adjacency matrix $A$, restricted to the induced
subgraph spanned by all the vertices not in $S$. For any $S\subseteq[k]$ we
will index $A_{S}$ the same way as we index $A$, i.e. $(A_{S})_{ij}=A_{ij}$
whenever $i,j\in[k]\setminus S$. Lemma 3.34 in particular already proves this
lemma for the diagonal entries.

Let $G=(V,E)$ with $V=[k]$ be the multigraph defined by the adjacency matrix
$A$. Let $W$ be any walk on $G$. Then we can obtain a unique simple path
$P_{W}$ from $W$ by repeatedly contracting cycles in $W$. We call two walks
$W_{1}$ and $W_{2}$ equivalent if $P_{W_{1}}=P_{W_{2}}$. Note that this forms
an equivalence relation on the walks on $G$ and there is a bijection between
paths on $G$ and equivalence classes of walks on $G$ and we can construct
every walk in the equivalence class $\mathcal{W}_{P}$ corresponding to a
path101010A path here is a sequence of edges, so in particular two paths with
the same sequence of vertices do not have to be the same since $G$ is a
multigraph $P=v_{1}\to\ldots\to v_{r}$ as follows: At every vertex $v_{i}$ we
can add any walk from $v_{i}$ back to $v_{i}$ of any length $\ell_{i}$, given
that it doesn’t pass through any of the vertices $v_{1},\ldots,v_{i-1}$. Note
that this restriction is not necessary in general, but it ensures that every
walk is uniquely constructed, a necessity for our proof. This construction
gives a walk of length $r-1+\sum_{i=1}^{r}\ell_{i}$.

Fix some $u\neq v\in V$ and let $P=v_{1}\to\ldots\to v_{r}$ be any path from
$u$ to $v$, i.e. $v_{1}=u$ and $v_{r}=v$. Then the class $\mathcal{W}_{P}$
contains exactly

$f_{P}(n):=\sum_{(\ell_{1},\ldots,\ell_{r})}\prod_{i=1}^{r}(A_{S_{i}}^{\ell_{i}})_{v_{i}v_{i}}$

walks of length $n\in\IN$ where the sum is over all
$(\ell_{1},\ldots,\ell_{r})\in\IN^{r}$ with $n=r-1+\sum_{i=1}^{r}\ell_{i}$ and
we define $S_{i}=\\{v_{1},\ldots,v_{i-1}\\}$. By Lemma 3.34 we know the
structure of each of the $(A_{S_{i}}^{\ell_{i}})_{v_{i}v_{i}}$ as a function
in $\ell_{i}$. Call the $v_{i}$ either $0$-vertices, $1$-vertices or
$\exp$-vertices respectively for each of the three cases of Lemma 3.34.
Additionally denote by $p_{i}$ the corresponding period for the $1$-vertices
and $\exp$-vertices and in case of $\exp$-vertices denote by $N_{i}$ the
smallest multiple of $p_{i}$, s.t. $(A_{S_{i}}^{N_{i}+j\cdot
p_{i}})_{v_{i}v_{i}}>0$ for all $j\in\IN$. Define $I_{0}:=\\{i\in[r]\mid
v_{i}\text{\ is a $0$-vertex}\\}$ and let $I_{1}$ and $I_{\exp}$ be defined
analogously.

We first look at the case $I_{\exp}=\emptyset$. Then
$\prod_{i=1}^{r}(A_{S_{i}}^{\ell_{i}})_{v_{i}v_{i}}=1$ iff $\ell_{i}=0$ for
all $i\in I_{0}$ and $\ell_{i}$ is a multiple of $p_{i}$ for all $i\in I_{1}$,
otherwise $\prod_{i=1}^{r}(A_{S_{i}}^{\ell_{i}})_{v_{i}v_{i}}=0$. Thus
$f_{P}(n)$ is given as the number of integer points in the polytope defined by
$\sum_{i\in I_{1}}\ell_{i}\cdot p_{i}=n-r+1$ and $\ell_{i}\geq 0$ for all
$i\in I_{1}$. This is a scaled polytope with rational vertices and thus
$f_{P}(n)$ is the Ehrhart quasi-polynomial (see [3, Chapter 3] for an
introduction to Ehrhart Theory).

We now look at the case $I_{\exp}\neq\emptyset$. Let $v_{e}$ be one vertex
with $e\in I_{\exp}$ and let $p$ be the gcd of all $p_{i}$ with $i\in
I_{1}\cup I_{\exp}$. This implies that
$\prod_{i=1}^{r}(A_{S_{i}}^{\ell_{i}})_{v_{i}v_{i}}=0$ whenever any of the
$\ell_{i}$ with $i\in[r]$ are not a multiple of $p$ and thus $f_{P}(n)=0$ if
$n\not\equiv_{p}r-1$. Additionally by Bézout’s lemma there is some $N\in\IN$
which is a multiple of $p$ s.t. that every number of the form $N+j\cdot p$
with $j\in\IN$ can be written as a non-negative linear combination of the
$p_{i}$ with $i\in I_{1}\cup I_{\exp}$. Define $N^{\prime}:=N+r-1+\sum_{i\in
I_{\exp}}N_{i}$. Let $n=N^{\prime}+j\cdot p$ for any $j\in\IN$. We can write

$\displaystyle n$
$\displaystyle=N^{\prime}+\underbrace{\frac{n-N^{\prime}-\lfloor\frac{n-N^{\prime}}{p_{e}}\rfloor\cdot
p_{e}}{p}}_{\alpha:=}\cdot
p+\underbrace{\left\lfloor\frac{n-N^{\prime}}{p_{e}}\right\rfloor}_{\beta:=}\cdot
p_{e}\,.$ (2)

since $e\in I_{\exp}$ implies that $p$ divides $p_{e}$. Furthermore both
$\alpha$ and $\beta$ are non-negative integers and $\beta$ is maximal with
this property. In particular we can write $N+\alpha\cdot p$ as a non-negative
linear combination with elements $p_{i}$ with $i\in I_{1}\cup I_{\exp}$. This
gives $N^{\prime}+\alpha\cdot p=r-1+\sum_{i\in I_{\exp}}N_{i}+\sum_{i\in
I_{1}\cup A_{\exp}}\kappa_{i}\cdot p_{i}$ for $\kappa_{i}\in\IN$. We choose
$\ell_{i}=0$ for $i\in I_{0}$ and $\ell_{i}=\kappa_{i}\cdot p_{i}$ for $i\in
I_{1}$ and $\ell_{i}=N_{i}+\kappa_{i}\cdot p_{i}$ for $i\in
I_{\exp}\setminus\\{e\\}$ and $\ell_{e}=N_{e}+\kappa_{e}\cdot p_{e}+\beta\cdot
p_{e}$. This describes a subset of the walks of length

$\displaystyle r-1+\sum_{i\in[r]}\ell_{i}$ $\displaystyle=r-1+\sum_{i\in
I_{\exp}}N_{i}+\sum_{i\in I_{1}\cup I_{\exp}}\kappa_{i}\cdot p_{i}+\beta\cdot
p_{e}=n_{1}+\alpha\cdot p+\beta\cdot p_{e}=n\,.$

In particular we have $(A_{S_{i}}^{\ell_{i}})_{v_{i}v_{i}}\geq 1$ for all
$i\in[r]$ and $(A_{S_{i}}^{\ell_{i}})_{v_{i}v_{i}}\in
2^{\Theta(\ell_{i})}=2^{\Theta(n)}$ and thus $f_{P}(n)\geq 2^{\Omega(n)}$ for
any $n\geq n_{1}$ with $n\equiv_{p}r-1$. Note again that $f_{P}(n)$ can never
grow faster than linearly exponential as it is bounded by the total number of
walks through $G$, so $f_{P}(n)$ is of the form required by the statement of
this lemma.

To finish the proof note that the class of ultimately almost PORC functions is
closed under addition and multiplication. If we multiply a polynomial
constituent with an exponential constituent, then either the polynomial
constituent is identical to $0$ or there is some $N\in\IN$, s.t. the
polynomial is strictly positive for every $n\geq N$. We have

$(A^{n})_{uv}=\sum_{P}f_{P}(n)$

where the sum is over all paths $P$ starting at $u$ and ending at $v$. For any
fixed $u,v\in V$ this is a sum of constantly many elements, bounded by
$(k\cdot\max(A))^{k-1}$, where $\max(A)$ denotes the maximum entry of $A$. We
conclude that $(A^{n})_{uv}$ is an ultimately almost PORC function.

See 3.40

######  Proof A.24.

Let $D_{\varphi}$ be the set of dominating terms of $\varphi$. We consider a
set of dominating terms $D$ to be smaller than another set of dominating terms
$D^{\prime}$, whenever $D\neq D^{\prime}$ and all terms of in $D$ are
dominated by terms in $D^{\prime}$. We prove the statement via induction over
$D$. In case $D_{\varphi}=\emptyset$ we have $\varphi=0$ which is trivially a
functional closure property. So let $D_{\varphi}\neq\emptyset$ and let
$a\cdot\binom{x_{1}}{d_{1}}\cdots\binom{x_{m}}{d_{m}}$ be any term from
$D_{\psi}$. We use a similar idea to Lemma 3.26 and replace the binomial basis
by a shifted binomial basis. Consider the terms
$a_{i}\cdot\binom{x_{1}}{d_{1}}\cdots\binom{x_{i-1}}{d_{i-1}}\binom{x_{i}}{d_{i}-1}\binom{x_{i+1}}{d_{i+1}}\cdots\binom{x_{m}}{d_{m}}$
in $\psi$ for all $i\in[m]$ with $d_{i}\geq 1$. These are precisely the
(potentially new) dominating terms of
$\varphi-a\cdot\binom{x_{1}}{d_{1}}\cdots\binom{x_{m}}{d_{m}}$. In order to
ensure the positivity of the $a_{i}$ we instead consider
$\psi:=\varphi-a\cdot\binom{x_{1}-c}{d_{1}}\cdots\binom{x_{m}-c}{d_{m}}$ for
some $c\in\IN$ with $c>-\frac{a_{i}}{a}$ for all $i\in[m]$ with $d_{i}\geq 1$.
We recall that the Chu-Vandermonde identity gives us
$\binom{x-c}{r}=\sum_{i=0}^{r}(-1)^{r-i}\binom{r-i+c-1}{r-i}\binom{x}{i}$.
Thus the new coefficient $a^{\prime}_{i}$ of
$\binom{x_{1}}{d_{1}}\cdots\binom{x_{i-1}}{d_{i-1}}\binom{x_{i}}{d_{i}-1}\binom{x_{i+1}}{d_{i+1}}\cdots\binom{x_{m}}{d_{m}}$
in $\psi^{\prime}$ is $a_{i}+a\cdot(-c)>0$. The new coefficient of
$\binom{x_{1}}{d_{1}}\cdots\binom{x_{m}}{d_{m}}$ in $\psi$ is zero and thus
$D_{\psi}$ is smaller than $D_{\varphi}$. By induction we know that $\psi$ can
be written as a positive linear combination of products of shifted binomials
and thus
$\varphi=\psi+a\cdot\binom{x_{1}-c}{d_{1}}\cdots\binom{x_{m}-c}{d_{m}}$ has
the same property.

See 3.41

######  Proof A.25.

We prove the statement via induction over the number of variables $m$. If
$m\leq 1$, then $\varphi$ is a constant polynomial and thus a functional
closure property of $\mathsf{\\#FA}$ by Lemma 3.28. If $m\geq 2$, and let
$f_{1},\ldots,f_{m}\in\mathsf{\\#FA}$. Write $\varphi$ as a positive integer
linear combination of products of shifted binomials using Lemma 3.40 and let
$c\in\IN$ be the maximum occurring shift. We now distinguish between the
$f_{i}$ assuming values from $\\{0,\ldots,c-1\\}$ and them assuming values of
at least $c$ and all combinations thereof for the different $f_{i}$. Using the
fact that all subtractions subtract at most a value of $c$ we can replace the
subtractions $x_{i}-c^{\prime}$ by $\max(x_{i}-c^{\prime},0)$ without changing
the value for $x_{i}\geq c$ and get the following:

$\displaystyle\psi(f_{1}(w),\ldots,f_{m}(w))=\Bigl{(}\prod_{i\in[m]}\mathbbm{1}_{f_{i}(w)\geq
c}\Bigr{)}\cdot\varphi_{\text{clamped}}(f_{1}(w),\ldots,f_{m}(w))\quad\quad\quad\quad\quad\quad\quad\quad$
$\displaystyle\quad\quad\quad\quad\quad+\sum_{\emptyset\subsetneq
I\subseteq[m]}\sum_{\rho}\Bigl{(}\prod_{i\in
I}\mathbbm{1}_{f_{i}(w)=\rho(i)}\Bigr{)}\cdot\Bigl{(}\prod_{i\in[m]\setminus
I}\mathbbm{1}_{f_{i}(w)\geq
c}\Bigr{)}\cdot\psi_{I,\rho}(f_{1}(w),\ldots,f_{m}(w))$

where $\rho$ sums over all functions $I\to\\{0,\ldots,c-1\\}$,
$\varphi_{\text{clamped}}$ is $\varphi$, but with all subtractions
$x_{i}-c^{\prime}$ replaced by $\max(x_{i}-c^{\prime},0)$ and
$\varphi_{I,\rho}$ is $\varphi$, but all variables $x_{i}$ with $i\in I$ are
replaced by the constants $\rho(i)$. The $\varphi_{I,\rho}$ are non-negative
integer-valued multivariate polynomials in fewer variables and when replacing
any variables by further constants we only obtain polynomials that can also be
obtained by replacing variables directly in $\varphi$. Thus by induction the
$\varphi_{I,\rho}$ are a functional closure property of $\mathsf{\\#FA}$ and
$\varphi(f_{1},\ldots,f_{m})\in\mathsf{\\#FA}$ by Lemmas 3.1, 3.2, 3.2, 3.2,
and 3.2.

See 3.42

######  Proof A.26.

Lemma 3.41 already proves that all multivariate polynomials of this form are
functional closure properties of $\mathsf{\\#FA}$.

Now let $\varphi:\IN^{m}\to\IN$ be a multivariate polynomial with rational
coefficient and a functional closure property of $\mathsf{\\#FA}$. By Theorem
3.38 $\varphi$ can be written as a finite sum of finite products of ultimately
PORC functions. W.l.o.g. let all quasiperiods be the same $p\in\IN$ and all
offsets be the same $N\in\IN$ and a multiple of $p$, for example by choosing
the lowest common multiple of the quasiperiods and choosing the lowest
multiple of $p$ that is bigger than all offsets. Then

$\displaystyle\varphi(x_{1},\ldots,x_{m})$
$\displaystyle=\textstyle\sum_{i=1}^{r}\prod_{j=1}^{m}\varphi^{(i,j)}(x_{j})$
(3)

where $\varphi^{(i,j)}$ is an ultimately PORC function with constituents
$\varphi^{(i,j)}_{0},\ldots,\varphi^{(i,j)}_{p-1}$. Consider inputs on a grid
of the form $(N+i_{1}\cdot p,N+i_{2}\cdot p,\ldots,N+i_{m}\cdot p)$ for
$i_{1},\ldots,i_{m}\in\IN$. For all these inputs each of the ultimately PORC
functions always use the same constituents, namely the $\varphi^{(i,j)}_{0}$.
Thus $\varphi$ agrees with
$\varphi^{\prime}(x_{1},\ldots,x_{m}):=\sum_{i=1}^{r}\prod_{j=1}^{m}\varphi^{(i,j)}_{0}(x_{j})$
on all inputs from this grid. Furthermore the grid is infinite in all
dimensions and thus $\varphi=\varphi^{\prime}$ by multivariate polynomial
interpolation (see [11] for an exposition of multivariate polynomial
interpolation). W.l.o.g. assume that $\varphi^{(i,j)}_{0}$ is not the constant
zero function. Then it has a positive leading coefficient, otherwise
$\varphi^{(i,j)}$ would not be a PORC function. Combined with the fact that
each of the $\varphi^{(i,j)}_{0}$ is univariate the product
$\prod_{j=1}^{m}\varphi^{(i,j)}_{0}(x_{j})$ for a fixed $i\in[r]$ has exactly
one dominating term when written in the binomial basis. Its coefficient is
precisely the product of the leading coefficients of the $\varphi^{(i,j)}_{0}$
and thus positive. As a result all dominating terms in the binomial basis of
$\varphi^{\prime}$ (and thus $\varphi$) have positive coefficients, since no
cancellations can occur unless the dominating term of a summand dominates the
dominating term of another summand, in which case the smaller term would no
longer be a dominating term.

Note that whenever any variable, for example $x_{j}$, in $\varphi$ is replaced
by a constant $c$, then this only changes each function
$\varphi^{(i,j)}(x_{j})$ and thus $\varphi^{(i,j)}_{0}(x_{j})$ to be the
constant $\varphi^{(i,j)}(c)$ which is non-negative.

###  A.3 Missing proofs from section 4

See 4.3

######  Proof A.27.

$S$$A$$0,1$$0,0,1,1$$1$ Figure 2: NFA computing the binary the value of its
input interpreted as a binary number. Edges with a multiplicity of $2$ are
denoted by listing the edge label twice.

We define

$\displaystyle a$ $\displaystyle=\begin{pmatrix}1\\\ 0\\\ \end{pmatrix},$
$\displaystyle A_{\sigma}$ $\displaystyle=\begin{pmatrix}1&\sigma\\\ 0&2\\\
\end{pmatrix},$ and $\displaystyle b$ $\displaystyle=\begin{pmatrix}0\\\ 1\\\
\end{pmatrix}\,.$

A visualization of the corresponding NFA $M$ via Lemma 3.32 can be found in
Figure 2. We prove that $M$ computes $f$ by showing via induction that for
every $w\in\\{0,1\\}^{\star}$ with $|w|=n$ we have

$\displaystyle\prod_{i=1}^{n}A_{w_{i}}=\begin{pmatrix}1&f(w)\\\ 0&2^{n}\\\
\end{pmatrix}\,.$

For $n=0$ this is obviously correct as $f(\varepsilon)=0$. For the induction
step consider the word $w\sigma$ of length $n+1$ for $\sigma\in\\{0,1\\}$.
Then

$\displaystyle\left(\prod_{i=1}^{n}A_{w_{i}}\right)\cdot
A_{\sigma}=\begin{pmatrix}1&f(w)\\\ 0&2^{n}\\\
\end{pmatrix}=\begin{pmatrix}1&\sigma+2f(w)\\\ 0&2^{n+1}\\\
\end{pmatrix}=\begin{pmatrix}1&f(w\sigma)\\\ 0&2^{n+1}\\\ \end{pmatrix}$

and we are done. Extending the alphabet and ignoring those new symbols can be
done by adding a self-loop to each state of $M$. This corresponds to an
identity matrix and thus doesn’t influence the result.

See 4.2

######  Proof A.28.

We inductively construct integer-valued polynomials $q_{0},\ldots,q_{N}$, that
each interpolate one value more. We start by setting
$q_{0}(x):=c_{0}\cdot\binom{x}{0}$. Clearly $q_{0}(0)=c_{0}$. We proceed
inductively by setting
$q_{i+1}(x):=q_{i}(x)+(c_{i+1}-q_{i}(i+1))\cdot\binom{x}{i+1}$. Note that
$\binom{n}{i+1}=0$ for $n\in\\{0,\ldots,i\\}$ and thus $q_{i+1}$ and $q_{i}$
agree on all such $n$. The final $q$ is then constructed as
$q(x):=q_{N}(x)+\alpha\cdot\binom{x}{N+1}$, for some big enough
$\alpha\in\IN$, s.t. $q(n^{\prime})\geq 0$ for all $n^{\prime}\in\IN$. Such an
$\alpha$ always exists since $\binom{x}{N+1}$ has higher degree than $q_{N}$.

See 4.7

######  Proof A.29.

If such a $\varphi^{\prime}$ exists, we directly see that $\varphi$ is a
functional promise closure property of $\mathsf{\\#FA}$ with respect to $S$.
Indeed for any $f_{1},\ldots,f_{m}\in\mathsf{\\#FA}$ we construct
$g=\varphi^{\prime}\circ(f_{1},\ldots,f_{m})\in\mathsf{\\#FA}$ and see
$g(w)=\varphi(f_{1}(w),\ldots,f_{m}(w))$ for every $x\in\Sigma^{\star}$ with
$(f_{1}(w),\ldots,f_{m}(w))\in S$.

Now on the other hand let $\varphi$ be any functional promise closure property
of $\mathsf{\\#FA}$ with regard to $S$. Again define the alphabet
$\Sigma=\\{\sigma_{1},\ldots,\sigma_{m}\\}$ and the functions
$f_{i}:\Sigma^{\star}\to\IN$ where $f_{i}(w):=\\#_{i}(w$ is defined as the
number of occurences $\\#_{i}(w)$ of the symbol $\sigma_{i}$ in $w$. Applying
the closure property to $f_{1},\ldots,f_{m}$ gives that there is some
$g\in\mathsf{\\#FA}$ with $g(w)=\varphi(f_{1}(w),\ldots,f_{m}(w))$ for all
$w\in\Sigma^{\star}$ with $(f_{1}(w),\ldots,f_{m}(w))\in S$. Let
$M=(Q,\Sigma,\textup{wt},\textup{in},\textup{out})$ be an NFA computing $g$.
This induces transition matrices $A_{\sigma}\in\IN^{|Q|\times|Q|}$ for each
symbol $\sigma\in\Sigma$ and vectors $a,b\in\IN^{|Q|}$, s.t.
$a^{T}\prod_{j=1}^{|w|}A_{w_{j}}b=g(x)$ for all $w\in\Sigma^{\star}$.
Restricting to words of the form
$w=\sigma_{1}^{n_{1}}\sigma_{2}^{n_{2}}\cdots\sigma_{m}^{n_{m}}$ for
$n_{1},\ldots,n_{m}\in S$ gives
$a^{T}\left(\prod_{i=1}^{m}A_{\sigma_{i}}^{n_{i}}\right)b=\varphi(n_{1},\ldots,n_{m})$.
Using Lemma 3.35 on each of the $A_{i}^{n_{i}}$ we see that every entry of
$A_{i}^{n_{i}}$ is an ultimately almost PORC function in $n_{i}$. Consequently
every entry of $\prod_{i=1}^{m}A_{\sigma_{i}}^{n_{i}}$ is a finite sum of
products of different ultimately almost PORC functions and the same holds for
$\chi(n_{1},\ldots,n_{m}):=a^{T}\left(\prod_{i=1}^{m}A_{\sigma_{i}}^{n_{i}}\right)b$.
Note that $\chi_{|S}=\varphi_{|S}$.

Remains to show that we can rewrite $\chi$ as some $\psi$ with
$\psi_{|S}=\chi_{|S}$, s.t. none of the constituents are exponential. Again we
do this by looking at each summand individually and replacing one exponential
constituent at a time. For this let $\chi^{(1)}(n_{1})\cdots\chi^{(m)}(n_{m})$
be one of the summands of $\chi$ where $\chi^{(1)},\ldots,\chi^{(m)}$ are all
ultimately almost PORC functions, with periods $p_{1},\ldots,p_{m}$, offsets
$N_{1},\ldots,N_{m}$ and constituents
$\chi^{(i)}_{0},\ldots,\chi^{(i)}_{p_{i}-1}$ for each $i\in[m]$. W.l.o.g.
choose the offsets big enough, such that every constituent $\chi^{(i)}_{j}$ is
either constant zero for $n_{i}\geq N_{i}$ or never zero for any $n_{i}\geq
N_{i}$. Let $\chi^{(i)}_{j}$ be one of the exponential constituents and let
$\gamma\in\mathbb{R}^{+}$ and $N\in\IN$ be, s.t. $\chi^{(i)}_{j}(n_{i})\geq
2^{\gamma n_{i}}$ for $n_{i}\geq N$. Let $B_{\max,i}$ be the maximum the
$i$-th coordinate assumes in any preimage of a singleton set under $\tau$
where the $i$-th coordinate is bounded. We replace $\chi^{(i)}_{j}$ with a
polynomial that interpolates $\chi^{(i)}$ for all values of at most
$B_{\max,i}$. Lemma 4.2 ensures this is possible with an integer-valued
polynomial that is non-negative for all of $\IN$. Call the resulting functions
after replacement $\psi^{(i)}$ and $\psi^{(i)}_{j}$. We claim that this does
not affect the value of the product for any $(n_{1},\ldots,n_{m})\in S$. For
the sake of contradiction the value of the product did change for some
$(c_{1},\ldots,c_{m})\in S$. We thus have

$\chi^{(1)}(c_{1})\cdots\chi^{(m)}(c_{m})\neq\chi^{(1)}(c_{1})\cdots\chi^{(i-1)}(c_{i-1})\cdot\psi^{(i)}(c_{i})\cdot\chi^{(i+1)}(c_{i+1})\cdots\chi^{(m)}(c_{m})$

which implies
$\chi^{(1)}(c_{1})\cdots\chi^{(i-1)}(c_{i-1})\cdot\chi^{(i+1)}(c_{i+1})\cdots\chi^{(m)}(c_{m})\neq
0$ and $c_{i}\geq N_{i}$ as no function except $\chi^{(i)}$ for inputs at
least as big as $N_{i}$ has been changed. By the same reason we know
$\chi^{(i)}_{j}(c_{i})\neq\psi^{(i)}_{j}(c_{i})$ and $c_{i}\equiv_{p_{i}}j$.

Consider the preimage
$T=\tau^{-1}(c_{1}\operatorname{srem}_{N_{1}}p_{1},\ldots,c_{m}\operatorname{srem}_{N_{m}}p_{m})$.
Clearly $(c_{1},\ldots,c_{m})\in T$. The $i$-th coordinate of $T$ has to be
unbounded, because $c_{i}\leq B_{\max,i}$ would imply
$\psi^{(i)}_{j}(c_{i})=\chi^{(i)}(c_{i})=\chi^{(i)}_{j}(c_{i})$ by the
construction of $\psi^{(i)}_{j}$. Furthermore the behaviour of each of the
$\chi^{(k)}$ is only dictated by at most one of the constituents each. By our
choice of the offsets we have $\chi^{(k)}(n_{k})\neq 0$ for all $k\neq i$ and
all $(n_{1},\ldots,n_{m})\in T$. Since $S$ admits polynomial cluster sequences
there is a polynomial cluster sequence $T^{\prime}\subseteq T$ with regards to
dimension $i$ with polynomial $q:\IN\to\IN$.

We construct $m$ functions $f^{\prime}_{k}\in\mathsf{\\#FA}$ over the alphabet
$\Sigma=\\{\sigma_{1,0},\sigma_{1,1},\ldots,\sigma_{m,0},\sigma_{m,1}\\}$ with
$2m$ symbols, by using Lemma 4.3 on the symbols $\sigma_{k,0}$ and
$\sigma_{k,1}$ each while ignoring any of the other symbols. This allows us to
encode any $(n_{1},\ldots,n_{m})\in T^{\prime}$ as independent binary
representations without leading zeros for each $n_{k}$ into a string of total
length $\sum_{k=1}^{m}\lfloor\log_{2}(n_{k})+1\rfloor\leq
m\cdot\lfloor\log_{2}(q(n_{i}))+1\rfloor$ which is in $O(\log(n_{i}))$ for
fixed $m$ and $q$.

Now let $w\in\Sigma^{\star}$ be any such string corresponding to a value
$(n_{1},\ldots,n_{m})\in T^{\prime}$. Combining all of this we again reach a
contradiction to the fact that NFAs can only compute at most linearly
exponential functions via

$\displaystyle\varphi(f^{\prime}_{1}(w),\ldots,f^{\prime}_{m}(w))$
$\displaystyle\geq\chi^{(1)}(c_{1})\cdots\chi^{(i-1)}(c_{i-1})\cdot\chi^{(i)}(f^{\prime}_{i}(w))\cdot\chi^{(i+1)}(c_{i+1})\cdots\chi^{(m)}(c_{m})$
$\displaystyle\geq\chi^{(i)}(f^{\prime}_{i}(w))$
$\displaystyle=\chi^{(i)}_{j}(f^{\prime}_{i}(w))$
$\displaystyle=\chi^{(i)}_{j}(n_{i})$ $\displaystyle\geq 2^{\gamma n_{i}}\,.$

Note that $|w|\in O(\log(n_{i}))$ implies $2^{\gamma n_{i}}$ is doubly
exponential in the input length.

See 4.10

######  Proof A.30.

Let $N_{1},\ldots,N_{m}\in\IN$ and $p_{1},\ldots,p_{m}\in\IN$ be fixed and
consider the preimage $T$ of any singleton
$(c_{1},\ldots,c_{m})\in\\{0,\ldots,N_{1}+p_{1}-1\\}\times\ldots\times\\{0,\ldots,N_{m}+p_{m}-1\\}$
under the corresponding shifted grid projection $\tau$ of $S$. Let
$(n_{1},\ldots,n_{m})\in T$ and let $i\in[m]$ be arbitrary. If the $i$-th
coordinate in $T$ is bounded then we are done. If the $i$-th coordinate in $T$
is unbounded we distinguish two cases.

In case $1\leq i\leq j$, we choose the $T^{\prime}$ to be the part of $S$
spanned by choosing the values of the free variables as
$\\{(n_{1},\ldots,n_{i-1},n_{i}+\kappa\cdot
pd,n_{i+1},\ldots,n_{j})\mid\kappa\in\IN\\}$ where $p$ is the lcm of
$p_{1},\ldots,p_{m}$ and $d$ is the common denominator of all of the
$\mu_{1},\ldots,\mu_{k}$. Clearly the $i$-th coordinate of $T^{\prime}$ is
unbounded and $T^{\prime}$ is infinite. Further since all other free variables
are constant, each dependent variable is a monotone univariate polynomial in
the $i$-th coordinate and thus the sum of all coordinates is bounded by some
polynomial in the $i$-th coordinate. Remains to show $T^{\prime}\subseteq T$.
For this let $(n^{\prime}_{1},\ldots,n^{\prime}_{m})\in T^{\prime}$. Clearly
$n^{\prime}_{\ell}\operatorname{srem}_{N_{\ell}}p_{\ell}=n_{\ell}\operatorname{srem}_{N_{\ell}}p_{\ell}$
for $\ell\in[j]\setminus\\{i\\}$, since $n^{\prime}_{\ell}=n_{\ell}$.
Additionally
$n^{\prime}_{i}\operatorname{srem}_{N_{i}}p_{i}=n_{i}\operatorname{srem}_{N_{i}}p_{i}$,
since $n^{\prime}_{i}=n_{i}+\kappa\cdot pd$ and $n_{i}\geq N_{i}$. Furthermore
$n^{\prime}_{\ell}\operatorname{srem}_{N_{\ell}}p_{\ell}=n_{\ell}\operatorname{srem}_{N_{\ell}}p_{\ell}$
for $\ell\in[m]\setminus[j]$, because either $n^{\prime}_{\ell}=n_{\ell}$ or
the $\ell$-th coordinate is unbounded and thus $n^{\prime}_{\ell}\geq
n_{\ell}\geq N_{\ell}$ and $n^{\prime}_{\ell}\equiv_{p_{\ell}}n_{\ell}$ since
$n^{\prime}_{\ell}$ is dependent on $n^{\prime}_{i}$ as a univariate
polynomials and for any univariate polynomial $q(x)$ we have
$q(x)\equiv_{p_{\ell}}q(x+\delta)$ if $\delta$ is a multiple of $p_{\ell}\cdot
h$. Thus $(n^{\prime}_{1},\ldots,n^{\prime}_{m})\in T$.

Remains to consider the case where $i>j$. Since the $i$-th coordinate in $T$
is unbounded, $n_{i}$ is a function depending on at least one of the free
variables $n_{i^{\prime}}$. We repeat the previous argument by continuing with
$i^{\prime}$ instead of $i$ which finishes the proof, since
$n_{i}\geq\alpha\cdot n_{i^{\prime}}$ for some $\alpha\in\mathbb{R}^{+}$.

See 4.11

######  Proof A.31.

If there exists a $\psi\in I$ such that $\varphi+\psi$ is a multivariate
functional closure property of $\mathsf{\\#FA}$, then
$(\varphi+\psi)_{|S}=\varphi_{|S}$ and thus $\varphi$ is a functional promise
closure property of $\mathsf{\\#FA}$ with regard to $S$ by definition. On the
other hand if $\varphi$ is a functional promise closure property of
$\mathsf{\\#FA}$ with regard to $S$, then there is a functional closure
property $\varphi^{\prime}$ of $\mathsf{\\#FA}$ with
$\varphi_{|S}=\varphi^{\prime}_{|S}$. Note that a priori $\varphi^{\prime}$
might not be a polynomial, but just a finite sum of finite products of
univariate ultimately PORC functions.

Wlog all thresholds $N$ and quasiperiods $p$ of $\varphi^{\prime}$ coincide.
We write $p^{\times m}=(p,p,\ldots,p)$ and $N^{\times m}=(N,N,\ldots,N)$. For
each $\vv i\in\\{0,\ldots,p+N-1\\}^{m}$ we have a polynomial
$\varphi^{\prime}_{\vv i}$, and $\varphi^{\prime}(\vv n)=\varphi^{\prime}_{\vv
n\operatorname{srem}^{\times m}_{N}p}(\vv n)$ for all $\vv n\in\IN^{m}$.
Define the set $S^{\prime}=\vv\mu^{-1}(\IN^{m})\subseteq\IN^{j}$ as all $\vv
s\in\IN^{j}$, s.t. $\mu_{a}(\vv s)\in\IN$ for all $a\in[k]$. Let
$\widetilde{\varphi}^{\prime}_{\vv i}:\mathbb{Q}^{j}\to\mathbb{Q}$ denote the
pullback via $\mu$, i.e., $\widetilde{\varphi}^{\prime}_{\vv
i}(s_{1},\ldots,s_{j})=\varphi^{\prime}_{\vv i}(s_{1},\ldots,s_{j},\mu_{1}(\vv
s),\ldots,\mu_{k}(\vv s))$. Analogously define the polynomial
$\widetilde{\varphi}:S^{\prime}\to\mathbb{Q}$. Since $\varphi^{\prime}$ is
only defined on $\IN^{m}$, the definition of its pullback requires a bit more
care, but since the pullback of $\varphi^{\prime}$ is defined for all of
$S^{\prime}$, we can then analogously define
$\widetilde{\varphi}^{\prime}:S^{\prime}\to\mathbb{Q}$. Observe that
$\widetilde{\varphi}$ and $\widetilde{\varphi}^{\prime}$ coincide on
$S^{\prime}$. Let $d$ be the common denominator of $\mu_{1},\ldots,\mu_{k}$.
Note that for any fixed $a\in[k]$ and $\vv o\in S^{\prime}$ we have that
$\mu_{a}(\vv o+dp\vv b)$ is constant for all $\vv b\in\IN^{j}$. In particular
we also have $\vv o+dp\vv b\in S^{\prime}$. Due to the monotonicity of each of
the $\mu_{a}$, for big enough $\vv b$, $\mu_{a}(\vv o+dp\vv b)$ will either
always be at least $N$ or $\mu_{a}$ is a constant function. Thus there is now
some $\vv o\in S^{\prime}$ with $\vv o\geq N^{\times j}$, such that even
$\mu_{a}(\vv o+dp\vv b)\operatorname{srem}_{N}p$ is constant for all $\vv
b\in\IN^{j}$. Let $\vv{\theta}=(\vv o,\mu_{1}(\vv o),\ldots,\mu_{k}(\vv
o))\operatorname{srem}_{N}p^{\times m}$. Hence, for all $\vv b\in\IN^{j}$ we
have $\widetilde{\varphi}^{\prime}(\vv o+dp\vv
b)=\widetilde{\varphi}^{\prime}_{\vv{\theta}}(\vv o+dp\vv b)$. Since
$\widetilde{\varphi}$ and $\widetilde{\varphi}^{\prime}$ coincide on
$S^{\prime}$, it follows that $\widetilde{\varphi}$ and
$\widetilde{\varphi}^{\prime}_{\vv{\theta}}$ coincide on an infinitely large
full-dimensional subgrid (namely on the grid formed by $\vv o+dp\vv b$ for
$b\in\IN^{j}$). Hence by multivariate polynomial interpolation,
$\widetilde{\varphi}=\widetilde{\varphi}^{\prime}_{\vv{\theta}}$. Hence,
$\varphi_{|S}=\varphi^{\prime}_{\vv\theta|S}$. Their difference
$\varphi^{\prime}_{\vv\theta}-\varphi$ is the desired polynomial $\psi\in I$.
It remains to show that $\varphi^{\prime}_{\vv\theta}$ is a multivariate
closure property of $\mathsf{\\#FA}$. Repeating the same argument as in Lemma
3.42 to proves that the dominating terms of $\varphi^{\prime}_{\vv\theta}$
have positive coefficients, even after replacing some variables by constants.
Using Lemma 3.42 again, shows that $\varphi^{\prime}_{\vv\theta}$ is a
multivariate closure property of $\mathsf{\\#FA}$.