THEOREMS AND CONJECTURES ON SOME RATIONAL GENERATING FUNCTIONS

NEW

Problem: Reconstructed statement: with $F_1=F_2=1$, $F_{i+2}=F_{i+1}+F_i$, fix $h,m\ge1$, $a_1,\dots,a_h\in\mathbb C$, and $P(x)\in\mathbb C[x]$. For

let $c_n(p)=[x^p]I_{h,P,n}(x)$, with $c_n(p)=0$ for $p<0$. For $\alpha=(\alpha_0,\dots,\alpha_{m-1})\in\mathbb Z_{\ge0}^m$ with $|\alpha|>0$, define

Then $\sum_{n\ge0}v_{h,P,\alpha}(n)x^n\in\mathbb C(x)$.

This is exactly Stanley’s Conjecture 4.2, except for the necessary convention issue: if $\mathbb N$ is taken to include $0$ and $\alpha=0$, then the summand is identically $1$ and the sum over $p\ge0$ diverges. The minimal natural repair is $|\alpha|>0$. If Stanley’s $\mathbb N$ means positive integers, no repair is needed.

Result: The repaired/intended statement is true.

Proof. List the shifts $s_1,\dots,s_R$, where $R=|\alpha|$, by repeating each $j\in\{0,\dots,m-1\}$ exactly $\alpha_j$ times. Then

First consider the “complete” correlation

The difference $W(n)-v(n)$ is a finite sum over $-m<T<0$ of products of fixed coefficients $c_n(q)$. For fixed $q$, $c_n(q)$ is eventually constant, because once $F_i>q$, all later nonconstant factor terms have degree $>q$. Hence the correction has rational generating function. It remains to prove rationality of $\sum W(n)x^n$.

Write $P(x)=\sum_{q\in Q} b_qx^q$. Expanding the $R$ coefficient factors independently, for each $(q_1,\dots,q_R)\in Q^R$ and each $i$, choose a letter

where $t_{r,i}=0$ means choosing $1$, and $t_{r,i}=k\ge1$ means choosing $a_kx^{F_{i+k-1}}$. Its weight is $\prod_r a_{t_{r,i}}$, with $a_0=1$. The equality $T=E_r-s_r$ for all $r$ is equivalent to $R-1$ equations

Thus $W(n)$ is a finite linear combination of weighted counts of words satisfying finitely many Fibonacci-linear equations.

We prove such counts are rational. Let $\beta=(1+\sqrt5)/2$, $\psi=(1-\sqrt5)/2$. For fixed finite alphabet $A$, weights $\lambda(a)$, integer vectors $\gamma_\tau(a)\in\mathbb Z^r$, $0\le\tau\le d$, and $b\in\mathbb Z^r$, define

Set $\Delta(a)=\sum_{\tau=0}^d\gamma_\tau(a)\beta^\tau\in\mathbb Z[\beta]^r$. By Binet’s formula, the constraint is equivalent to

For a word, define tail states

If the word is accepted, then both $Y_j$ and its conjugate are bounded by constants depending only on $A,\gamma,b$, not on $n$. Since $\mathbb Z[\beta]$ is a lattice under $z\mapsto(z,\bar z)$, only finitely many such states occur.

Therefore accepted words are recognized by a finite weighted automaton: start at $0$, read the word backwards, and use transitions

with weight $\lambda(a)$. Final states are those $Y$ satisfying

Hence $U_n$ is a finite matrix coefficient $e_0^TM^n f$, so

is rational.

Applying this finite-state lemma to the equations above proves rationality of $\sum W(n)x^n$, and the finite correction proves rationality of $\sum v(n)x^n$.

Verification audit. The proof uses only the stated data $h,a_i,P,\alpha$, with the necessary nonzero multi-index condition. The $p\ge0$ boundary is handled by the finite correction. The finite automaton hypotheses hold because the alphabet $\{0,\dots,h\}^R$ is finite and all Fibonacci coefficients in the constraints are integers. The conclusion is exactly rationality over $\mathbb C(x)$.

Citation: No external resolution is used. Source of the conjecture: Richard P. Stanley, “Theorems and Conjectures on Some Rational Generating Functions,” arXiv:2101.02131, Conjecture 4.2.