THEOREMS AND CONJECTURES ON SOME RATIONAL GENERATING FUNCTIONS

NEW

Problem: For $k\ge2$, let $F^{(k)}_1=\cdots=F^{(k)}_k=1$ and

Define

For $m\ge1$ and $0\le a<m$,

The reconstructed conjecture is Stanley’s Conjecture 6.2: $H^{(k)}_{m,a}(x)$ is rational for all $k,m,a$ as above. The convention that zero coefficients between degree $0$ and $D_n$ are counted is supported by Stanley’s preceding definition for Stern coefficients, where $0\le p\le\deg$ is explicit.

Result: The conjecture is true.

Let

Then

A binary word $u=u_1\cdots u_N$ has value

Call $u$ legal if it has no run of $k$ consecutive $1$’s.

Every binary word of length $n$, padded by one final $0$, can be rewritten to a legal word of length $n+1$ by repeatedly replacing

which preserves value by the recurrence above. The process terminates because it strictly increases the word in reverse lexicographic order, and no bit beyond position $n+1$ can appear since

Legal representatives are unique: if two legal words first differ at position $r$, the one with a $1$ there has value larger, because the maximum value of a legal word using positions $<r$ is $<w_r$, proved by the same recurrence.

Thus nonzero coefficients of $I_n^{(k)}$ are indexed uniquely by legal words $y$ of length $n+1$, and the coefficient equals the number of binary words $z$ of length $n+1$ with $z_{n+1}=0$ and $V(z)=V(y)$.

Stanley proves that the equality relation

on pairs of equal-length binary words is a regular language. Explicitly, over paired letters

it is the Kleene star of the regular generator set

Hence a finite automaton recognizes all pairs $(y,z)$ with $V(y)=V(z)$.

Fix $m$. For each top word $y$, the number of bottom words $z$ accepted with $z_{n+1}=0$ can be computed modulo $m$ by a finite-state automaton whose state records, modulo $m$, the number of paths ending in each state of the equality automaton. Therefore, for each nonzero residue $a$, the set of legal words $y$ of length $n+1$ for which this number is congruent to $a\pmod m$ is regular. Counting words of length $n+1$ in a regular language gives a rational generating function. Thus $H^{(k)}_{m,a}(x)$ is rational for $a\ne0$.

For $a=0$,

Since $D_n=\sum_{i=1}^n w_i$ satisfies a linear recurrence, $\sum_{n\ge0}(D_n+1)x^n$ is rational. Hence $H^{(k)}_{m,0}(x)$ is rational too. For $m=1$, this formula directly gives $H^{(k)}_{1,0}(x)$ rational.

Therefore $H^{(k)}_{m,a}(x)$ is rational for all $k\ge2$, $m\ge1$, and $0\le a<m$.

Citation: Uses Stanley’s definitions and his regular/free-monoid lemma for equal $k$-bonacci subset sums: Richard P. Stanley, “Theorems and conjectures on some rational generating functions,” arXiv:2101.02131, Section 5 and Conjecture 6.2.