Commutative $\mathbb{N}$-Rational Series of Polynomial Growth

Let us define $M:=(\{1\},\times )$ which is a finite aperiodic monoid, $\mu :{\mathrm{\Sigma }}^{\ast }\to M$ defined by $\mu (w):=1$, and $\pi :M^2\to \mathbb{N}$ that is the constant function equal to $1$. We check that for all $w\in {\mathrm{\Sigma }}^{\ast }$: ${\pi }^{†}(w)={\sum }_{uv=w}1=|w|+1=f(w)$. $◀$

Let us remark that the set $P_w$ of distinct pairs of positions in a word $w$ is in bijection with the set $D_w$ of decompositions of the form $w=xyz$, where $x$ and $y$ are non-empty, via the map $(i,j)\mapsto (w_{1,i},w_{i+1,j},w_{j+1,|w|})$. Let us write $M:=(\{0,1\},\max )$ which is a finite aperiodic monoid, and $\mu :{\mathrm{\Sigma }}^{\ast }\to M$ that maps the empty word $\epsilon$ to $0$ and the other words to $1$. Then, let us define $\pi :M^3\to \mathbb{N}$ via $\pi (x,y,z)=x\times y$. We conclude because:

$◀$

One of the appeals of $\mathbb{N}\mathrm{𝖯𝗈𝗅𝗒}$ and $\mathbb{Z}\mathrm{𝖯𝗈𝗅𝗒}$ are the numerous characterizations of these classes in terms of logic, weighted automata, and the larger class of polyregular functions [5, 8]. In this paper, the main focus will be the connection to weighted automata, which is based on the notion of growth rate. The growth rate of a function $f:{\mathrm{\Sigma }}^{\ast }\to \mathbb{Z}$ is defined as the minimal $d$ such that $|f(w)|=𝒪\left({|w|}^d\right)$. If such a $d$ exists, we say that the function $f$ has polynomial growth. It turns out that for all $k\in \mathbb{N}$, $\mathbb{Z}{\mathrm{𝖯𝗈𝗅𝗒}}_d$ (resp. $\mathbb{N}{\mathrm{𝖯𝗈𝗅𝗒}}_d$) are precisely functions in $\mathbb{Z}\mathrm{𝖲𝖾𝗋𝗂𝖾𝗌}$ (resp. in $\mathbb{N}\mathrm{𝖲𝖾𝗋𝗂𝖾𝗌})$ that have growth rate at most $d$.

Let us introduce some compositional properties of $\mathbb{Z}$-polyregular functions that will be used in this paper to construct $\mathbb{Z}$-polyregular functions.

Let us briefly state that commutativity is a decidable property of $\mathbb{Z}$-rational series, hence of $\mathbb{Z}$-polyregular functions. As a consequence, we are working inside a relatively robust and decidable subclass of $\mathbb{Z}$-rational series.

Remark that the group of permutations of $\{1,\mathrm{\dots },n\}$ is generated by the cycle $c:=(n,1,\mathrm{\dots },n-1)$ and the transposition $t:=(1,2)$. As a consequence, a function $f$ is commutative if and only if $f\circ c=f=f\circ t$. When $f$ is a rational series, $f\circ c$ and $f\circ t$ are both rational series that can be effectively computed from $f$,¹¹1 This can be done by guessing the second (resp. last) letter of the input word, remembering the first letter in a state, and then running the original automaton for $f$ on the modified input, checking at the second position (resp. the end of the word) if the guess was correct. and since equivalence of rational series is decidable [1, Corollary 3.6], we have obtained a decision procedure. $◀$

Because of the stability properties of $\mathbb{N}\mathrm{𝖲𝖥}$ (Lemma 7), we only need to check that given $r,s\in \mathbb{N}$, the function $x\mapsto \left(\genfrac{}{}{0pt}{}{x-r}{s}\right)$ is represented by a function $f_{r,s}\in \mathbb{N}\mathrm{𝖲𝖥}$. Let us prove it when $r=0$, since the other functions can be obtained by translating $f_{r,s}$. By definition, $\left(\genfrac{}{}{0pt}{}{x}{s}\right)=|P_{x,s}|$, where . Let us proceed as in Example 5 and define $D_{w,s}:=\{(u_1,\mathrm{\dots },u_s,u_{s+1})\in {({\mathrm{\Sigma }}^{+})}^s\times {\mathrm{\Sigma }}^{\ast }\mid w=u_1{u}_2\mathrm{\cdots }{u}_s{u}_{s+1}\}$. It is clear that $D_{a^x,s}$ is in bijection with $P_{x,s}$ for all $x\in \mathbb{N}$ using the map $(x_1,\mathrm{\dots },x_s)\mapsto (a^{x_1},\mathrm{\dots },a^{x_s})$. Now, using the monoid $M:=(\{0,1\},\max )$ and the morphism $\mu (\epsilon ):=0$ and $\mu (a):=1$, one can compute $|D_{w,s}|$ as ${\pi }^{†}(w)$ where $\pi :M^{s+1}\to \mathbb{N}$ is defined by $\pi (m_1,\mathrm{\dots },m_s,m_{s+1}):=m_1\times \mathrm{\cdots }\times m_s$. We conclude that $f_{0,s}\in \mathbb{N}{\mathrm{𝖲𝖥}}_s$ is a star-free polyregular function. $◀$

The multiplicative factor $\omega$ is necessary in Lemma 20. Indeed, the function $f:{\{a\}}^{\ast }\to \mathbb{N}$ defined as $0$ when the input is of odd length and $1$ when the input is of even length is $\mathbb{N}$-polyregular, but $f(a^X)$ is not a polynomial. We can trade off this multiplicative factor for a constant term addition under the extra assumption that the function is star-free polyregular, as described in the following Lemma 21. This lemma is not immediately of use, but is crucial for the upcoming characterization of $\mathbb{N}$-rational polynomials in Theorem 34, which in turn is a key ingredient of our main Theorem 40.

Because natural binomial functions behave as polynomials with non-negative maximal monomials on large enough inputs, we can conclude from Lemma 20 that $\mathbb{N}$-rational polynomials are in $\mathrm{𝖯𝗈𝗅𝗒𝖲𝗍𝗋𝖭𝖭𝖾𝗀}$.

Let $f$ be a commutative $\mathbb{N}$-rational series with domain defined as $\mathrm{\Sigma }:=\{a_1,\mathrm{\dots },a_p\}$ that represents $P$. Because $f$ has polynomial growth, $f\in \mathbb{N}\mathrm{𝖯𝗈𝗅𝗒}$ (Lemma 6). Using Lemma 20, there exists a number $\omega \in {\mathbb{N}}_{\ge 1}$ and natural binomial function $Q$ such that for all $n_1,\mathrm{\dots },n_p\ge 1$:

For large enough values of $X$, the simple binomial function $\left(\genfrac{}{}{0pt}{}{X-p}{k}\right)$ coincides with a polynomial whose leading coefficient is $1/k!$ which is non-negative. We conclude that the maximal monomials of $P(\omega X_1,\mathrm{\dots },\omega X_p)$ are non-negative, and since $\omega \ge 1$, we conclude that the maximal monomials of $P$ have non-negative coefficients.

For every partial valuation $\nu :\overrightarrow{X}\rightharpoonup \mathbb{N}$, the polynomial ${[P]}_{\nu }$ continues to be represented by a $\mathbb{N}$-polyregular function, namely $f_u:w\mapsto f(uw)$ where $w$ belongs to a restricted alphabet. As a consequence, the maximal monomials of ${[P]}_{\nu }$ are also non-negative, and we have proven that $P\in \mathrm{𝖯𝗈𝗅𝗒𝖲𝗍𝗋𝖭𝖭𝖾𝗀}$. $◀$

We prove the result for monomials, as it extends to $\mathbb{N}$-linear combinations by linearity. Let $P={\prod }_{i=1}^k{X}_i^{{\alpha }_i}$ be a monomial. Notice that ${\tau }_K(P)={\prod }_{i=1}^k{(X_i+K)}^{{\alpha }_i}$, and using a binomial expansion we list all the possible divisors of $P$, all of which with coefficients that are positive integers and multiples of $K$ except the coefficient of the maximal monomial (equal to $P$ itself) which is $1$. As a consequence, ${\tau }_K(P)-P$ is simply obtained by removing this maximal monomial, which concludes the proof. $◀$

Let us first tackle the specific case where $P$ is a constant polynomial. In this case, $P_1=P$ and $P_2=0$. Furthermore, ${\mathrm{\Delta }}_K(P_1)=0$ for all $K\in \mathbb{N}$. We conclude that ${\mathrm{\Delta }}_K(P_1)+{\tau }_K(P_2)=0$ for all $K\in \mathbb{N}$, hence belongs to $\mathbb{N}[\overrightarrow{X}]$. Selecting $K=0$ we conclude. Assume now that $P$ is not a constant polynomial. We will use Lemma 24 on a well-selected value of $K$. Let us write $\alpha$ to be the maximal absolute value of a coefficient in $P$. Let $D$ be the number of unitary monomials that divide some monomial appearing in $P$. We can now define $K:=D\times \alpha$, and let $Q:=({\mathrm{\Delta }}_K(P_1)+{\tau }_K(P_2))$. Remark that ${\mathrm{\Delta }}_K(P_1)$ is already in $\mathbb{N}[\overrightarrow{X}]$, and the constant coefficient of ${\tau }_K(P_2)$ is also in $\mathbb{N}$. For any other monomial of $P_2$, by the maximality of $P_1$, it strictly divides some monomial of $P_1$, and equals some monomial of ${\mathrm{\Delta }}_K(P_1)$ up to a multiplication by a factor in $\mathbb{Q}$. Because every monomial of ${\mathrm{\Delta }}_K(P_1)$ has a coefficient that is a multiple of $K=\alpha \times D$, we can compensate every monomial of $P_2$ by a monomial of ${\mathrm{\Delta }}_K(P_1)$. Therefore, $Q\in \mathbb{N}[\overrightarrow{X}]$. $◀$

We prove the result by induction on the number of indeterminates of $P$. In the proof, we write $\overrightarrow{X}$ for the indeterminates appearing in $P$, that is, we assume without loss of generality that all indeterminates are used.

Base case: If the (unique) maximal monomial of $P$ is a constant term. Since $P\in \mathrm{𝖯𝗈𝗅𝗒𝖲𝗍𝗋𝖭𝖭𝖾𝗀}$, $P=n\in \mathbb{N}$, and therefore $P$ is represented by a constant star-free $\mathbb{N}$-polyregular function.

Induction: Assume that $P$ is not a constant polynomial, and let us write $P=P_1+P_2$ where $P_1$ is the sum of the maximal monomials of $P$. We compute a bound $K$ such that $Q:=({\mathrm{\Delta }}_K(P_1)+{\tau }_K(P_2))\in \mathbb{N}[\overrightarrow{X}]$ (Lemma 25). In particular, $Q$ is represented by a star-free $\mathbb{N}$-polyregular function using Lemma 9, the latter being effectively computable from $Q$. Let us now remark that $P_1\in \mathbb{N}[\overrightarrow{X}]$, and is therefore (effectively) represented by a star-free $\mathbb{N}$-polyregular function (using again Lemma 9). As a consequence, ${\tau }_K(P)=P_1+Q$ is (effectively) represented by a function $f_{\mathrm{\Delta }}$.

For all partial valuations $\nu :\overrightarrow{X}\rightharpoonup \{0,\mathrm{\dots },K\}$ fixing at least one indeterminate, one can use the induction hypothesis to compute a star-free $\mathbb{N}$-polyregular function $f_{\nu }$ that represents ${[P]}_{\nu }$. This is possible because we assumed that all indeterminates in $\overrightarrow{X}$ are used in $P$.

Let us assume that the alphabet over which the (commutative) functions $f_{\mathrm{\Delta }}$ and $f_{\nu }$ are defined is $\{a_1,\mathrm{\dots },a_k\}$, with $a_i$ representing the indeterminate $X_i$ of the polynomials. Now, let us define by case analysis the following commutative star-free $\mathbb{N}$-polyregular function, defined on words $w$ of the form $w:=a_1^{x_1}\mathrm{\cdots }{a}_k^{x_k}$, with $x_1,\mathrm{\dots },x_k\ge 0$.

Remark that $f$ is a commutative star-free $\mathbb{N}$-polyregular function that represents $P$. $◀$

While Lemma 26 provides an effective conversion procedure, it does not explicitly state that the membership is decidable to keep the proof clearer. A similar proof scheme can be followed to conclude that membership is decidable, and even show that elements in $\mathrm{𝖯𝗈𝗅𝗒𝖲𝗍𝗋𝖭𝖭𝖾𝗀}$ are, up to suitable translations, polynomials in $\mathbb{N}[\overrightarrow{X}]$ (Lemma 27). Beware that partial applications are still needed in this characterization, as Example 28 illustrates.

We now have all the tools to prove the corrected version of Flawed 12.

The implications Item 4 $⟹$ Item 3 $⟹$ Item 2 are obvious. Lemma 26 proves Item 1 $⟹$ Item 4, while Corollary 22 proves Item 2 $⟹$ Item 1. Note that the lemmas provide effective conversion procedures, and that Lemma 27 also provides a decision procedure. $◀$

For completeness, let us remark that the counterexample of Lemma 15 uses three indeterminates, and this is not a coincidence: in the particular cases of one or two indeterminates, the classes $\mathrm{𝖯𝗈𝗅𝗒𝖲𝗍𝗋𝖭𝖭𝖾𝗀}$ and $\mathrm{𝖯𝗈𝗅𝗒𝖭𝖭𝖾𝗀}$ coincide. In particular, the examples appearing in [10] are not invalidated, as they all use at most two indeterminates. Note that the equivalence is clear for the univariate case, where being non-negative and having non-negative maximal coefficient clearly imply being an $\mathbb{N}$-rational polynomial.

It is clear that $\mathrm{𝖯𝗈𝗅𝗒𝖲𝗍𝗋𝖭𝖭𝖾𝗀}[X,Y]\subseteq \mathrm{𝖯𝗈𝗅𝗒𝖭𝖭𝖾𝗀}[X,Y]$, by considering the empty valuation $\nu :\{X,Y\}\rightharpoonup \mathbb{N}$. For the converse inclusion, let us consider $P(X,Y)$ that is non-negative, such that the maximal monomials are non-negative.

If we fix none of the variables, then the maximal monomials are non-negative by assumption. If we fix one of the variables, we can assume without loss of generality that we fix $X=k$ for some $k\in \mathbb{N}$. Then $P(k,Y)$ is a non-negative univariate polynomial, and therefore must either have a positive leading coefficient (which is the unique maximal monomial in this case) or be constant equal to 0. In both cases, the maximal monomials have positive coefficient. The same reasoning applies a fortiori in the case where we fix the two indeterminates, leading to a constant polynomial. $◀$

The implications Item 4 $⟹$ Item 3 $⟹$ Item 2 $⟹$ Item 1 are obvious. Now, Item 1 $⟹$ Item 5 is a direct consequence of Lemma 30. Finally, Item 5 $⟹$ Item 4 follows from the fact that $\bullet \left(\genfrac{}{}{0pt}{}{X-p}{k}\right)\bullet$ is represented by a star-free $\mathbb{Z}$-polyregular function defined by hardcoding the output values (in $\mathbb{Z}$) when $0\le X\le p$, and using a star-free $\mathbb{N}$-polyregular function when $X>p$ (Lemma 19). Because $\mathbb{Z}\mathrm{𝖲𝖥}$ is closed under products and $\mathbb{Z}$-linear combinations, we conclude. $◀$

Obtaining an analogue of Theorem 31 for $\mathbb{N}$-polyregular functions requires a bit more work, as polynomials in $\mathbb{Q}[\overrightarrow{X}]$ that are represented by $\mathbb{N}\mathrm{𝖯𝗈𝗅𝗒}$ are not exactly natural binomial polynomials (see Example 32). To address the issues raised by the former example, we introduce the notion of strongly natural binomial polynomials, as the polynomials $P\in \mathbb{Q}[X]$ such that for all partial valuation $\nu :\rightharpoonup \mathbb{N}$, ${[P]}_{\nu }$ is a natural binomial polynomial, which characterizes the class of polynomials that are represented by $\mathbb{N}\mathrm{𝖯𝗈𝗅𝗒}$ (Theorem 34).

Let us first remark that $\mathbb{N}\mathrm{𝖯𝗈𝗅𝗒}\subseteq \mathbb{N}\mathrm{𝖲𝖾𝗋𝗂𝖾𝗌}$, and that if $P$ is represented by a function $f\in \mathbb{N}\mathrm{𝖲𝖾𝗋𝗂𝖾𝗌}$, then said function has polynomial growth, and in particular $f\in \mathbb{N}\mathrm{𝖯𝗈𝗅𝗒}$ thanks to Lemma 6. As a consequence, Item 2 $\iff$ Item 3. For the implication Item 3 $⟹$ Item 1, we obtain $\alpha P\in \mathrm{𝖯𝗈𝗅𝗒𝖲𝗍𝗋𝖭𝖭𝖾𝗀}$ via Theorem 17 by remarking that $\mathbb{N}$-polyregular functions have output in $\mathbb{N}$ and are closed under multiplication by a constant $\alpha \in \mathbb{N}$. The fact that $P$ is integer-valued follows from Theorem 31 and the fact that $\mathbb{N}\mathrm{𝖲𝖥}\subseteq \mathbb{Z}\mathrm{𝖯𝗈𝗅𝗒}$. The implication Item 1 $⟹$ Item 5 is obtained thanks to Lemma 33.

Let us now prove by induction on the number of indeterminates that Item 5 $⟹$ Item 4. Note that by construction, there exists a number $K\in \mathbb{N}$ such that when the input values of $P$ are all greater than $K$, $P$ coincides with a natural binomial function, which is itself represented by a star-free $\mathbb{N}$-polyregular function. If some input value $X_i$ is set to a number $x_i\le K$, then one can leverage the fact that ${[P]}_{X_i=x_i}$ remains a strongly natural binomial polynomial to conclude by induction that ${[P]}_{X_i=x_i}$ is represented by a star-free $\mathbb{N}$-polyregular function. Combining these, we obtain a star-free $\mathbb{N}$-polyregular function representing $P$.

Finally, the implication Item 4 $⟹$ Item 3 is immediate as $\mathbb{N}\mathrm{𝖲𝖥}\subseteq \mathbb{N}\mathrm{𝖯𝗈𝗅𝗒}$. $◀$

Let us remark that Theorem 34 shows that the class of polynomials represented by $\mathbb{N}\mathrm{𝖯𝗈𝗅𝗒}$ is the same as the class of polynomials represented by $\mathbb{N}\mathrm{𝖲𝖥}$, which is a non-trivial statement that will be reused in the study of more general commutative functions in $\mathbb{Z}\mathrm{𝖯𝗈𝗅𝗒}$.