Let k ≥ 3, let mathbfW^(k) be the infinite-alphabet k-Bonacci word, and let B sqsubseteq mathbfW^(k) be a fixed non-empty factor. Write C_B^(k)(y) for its factor-occurrence generating function and c^(k)(B;n) for the number of occurrences of B in the finite iterate W_n^(k). Factor-occurrence rationality conjecture. For every fixed k ≥ 3 and every non-empty factor B sqsubseteq mathbfW^(k), there exist an integer s(B) ≥ 1 and a polynomial P_B(y) ∈ Z[y] such that C_B^(k)(y)=fracP_B(y)(1-y-y^2-…-y^k-1)^s(B). Equivalently, the sequence bigl(c^(k)(B;n)bigr)_n∈N satisfies a linear recurrence whose characteristic polynomial divides a power of nx^k-1-x^k-2-…-x-1. The paper establishes the corresponding formulas for digit occurrences and all length-2 factors, while the conjecture proposes that the same denominator phenomenon extends to every fixed non-empty factor. Its resolution would give a uniform description of factor-occurrence growth and recurrences throughout the infinite-alphabet k-Bonacci word.

Rationality conjecture for factor-occurrence generating functions in k-Bonacci words

Let $k \ge 3$ , let $\mathbf{W}^{(k)}$ be the infinite-alphabet $k$ -Bonacci word, and let $B \sqsubseteq \mathbf{W}^{(k)}$ be a fixed non-empty factor. Write $C_B^{(k)}(y)$ for its factor-occurrence generating function and $c^{(k)}(B;n)$ for the number of occurrences of $B$ in the finite iterate $W_n^{(k)}$ .

Factor-occurrence rationality conjecture. For every fixed $k \ge 3$ and every non-empty factor $B \sqsubseteq \mathbf{W}^{(k)}$ , there exist an integer $s(B) \ge 1$ and a polynomial $P_B(y) \in \mathbb{Z}[y]$ such that

C_B^{(k)}(y)=\frac{P_B(y)}{(1-y-y^2-\cdots-y^{k-1})^{s(B)}}.

Equivalently, the sequence $\bigl(c^{(k)}(B;n)\bigr)_{n\in\mathbb{N}}$ satisfies a linear recurrence whose characteristic polynomial divides a power of

\nx^{k-1}-x^{k-2}-\cdots-x-1.

The paper establishes the corresponding formulas for digit occurrences and all length- $2$ factors, while the conjecture proposes that the same denominator phenomenon extends to every fixed non-empty factor. Its resolution would give a uniform description of factor-occurrence growth and recurrences throughout the infinite-alphabet $k$ -Bonacci word.

References

Primary source

Narges Ghareghani, Mehdi Golafshan, Morteza Mohammad-Noori and Pouyeh Sharifani, “Enumeration of Factor Occurrences in k-Bonacci Words over an Infinite Alphabet”, arXiv:2604.01488 (2026).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

The original paper leaves the conjecture open, but a posted complete-proof attempt claims to settle every factor case and has not been independently checked.

Ghareghani, Golafshan, Mohammad-Noori, and Sharifani posed the conjecture in April 2026 for every fixed $k \ge 3$ and every non-empty factor. Their paper proves only the digit and length- $2$ cases and presents the arbitrary-factor statement as a conjecture.

Known results

Digit occurrences: the predicted denominator form is proved (Ghareghani, Golafshan, Mohammad-Noori, and Sharifani, 2026).
All occurring length- $2$ factors: the predicted form is proved (same authors, 2026).
Computational checks support factors of length at most $5$ for $k \le 6$ ; this is not a general proof.

Posted attempt

A complete-proof attempt claims that block decomposition eliminates boundary-crossing occurrences for sufficiently large iterates, yielding $D_k(y)^{q+1}C_B(y) \in \mathbb{Z}[y]$ with $q=\lfloor\min(B)/k\rfloor$ . It therefore claims the conjecture for arbitrary factors, with $s(B)=1+\lfloor\min(B)/k\rfloor$ , but the argument has not been independently verified.

Current status (as of August 2026): The digit and length- $2$ cases are proved and limited computations support the conjecture, while a posted attempt claims a complete proof for arbitrary factors but remains unverified.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

Complete proof for factors of arbitrary length, with an explicit denominator exponent and recurrence onset.

Let $k\ge2$ , and let $W_n=\phi_k^n(0)$ be the finite infinite-alphabet $k$ -Bonacci words from Ghareghani, Golafshan, Mohammad-Noori, and Sharifani, arXiv:2604.01488. For any nonempty finite word $B$ over $\mathbb N$ , including words that do not occur, define

c_B(n)=|W_n|_B,\qquad C_B(y)=\sum_{n\ge0}c_B(n)y^n,\qquad D_k(y)=1-y-y^2-\cdots-y^{k-1}.

Occurrences are counted with overlap. Write

m=\min(B),\qquad M=\max(B),\qquad q=\left\lfloor\frac{m}{k}\right\rfloor.

We prove the stronger explicit statement

\boxed{D_k(y)^{q+1}C_B(y)\in\mathbb Z[y].} \tag{1}

The paper's previously established Lemmas 1 and 3 supply the decomposition

W_n=W_{n-1}W_{n-2}\cdots W_{n-k+1} \bigl(k\oplus W_{n-k}\bigr),\qquad n\ge k, \tag{2}

and state that the final letter of $W_j$ is $j$ . Here $k\oplus V$ adds $k$ to each letter of $V$ .

Suppose $n\ge M+k$ . Every boundary between consecutive blocks in (2) is immediately preceded by the final letter of some unshifted block $W_j$ , where

n-k+1\le j\le n-1.

Consequently that boundary is immediately preceded by a letter

j\ge n-k+1\ge M+1>M.

Any occurrence crossing such a boundary would contain that letter, which is impossible because every letter of $B$ is at most $M$ . This argument works for words of arbitrary length, including occurrences that would cross several boundaries.

Hence every occurrence lies wholly inside exactly one block of (2). The unshifted blocks give $c_B(n-1),\ldots,c_B(n-k+1)$ . The shifted final block contributes zero if $m<k$ ; otherwise its occurrences correspond bijectively to occurrences of $B-k$ in $W_{n-k}$ . Thus

c_B(n)=\sum_{r=1}^{k-1}c_B(n-r) +\boldsymbol 1_{\{m\ge k\}}c_{B-k}(n-k), \qquad n\ge M+k. \tag{3}

Set

Q_B(y)=D_k(y)C_B(y) -\boldsymbol 1_{\{\min(B)\ge k\}}y^kC_{B-k}(y).

By (3), all coefficients of degree at least $M+k$ vanish. Therefore

Q_B(y)\in\mathbb Z[y],\qquad \deg Q_B\le M+k-1. \tag{4}

Iterating along $B,B-k,\ldots,B-qk$ , the last of which has minimum less than $k$ , gives

C_B(y)= \sum_{r=0}^{q} \frac{y^{kr}Q_{B-rk}(y)}{D_k(y)^{r+1}}.

It follows that

D_k(y)^{q+1}C_B(y) = \sum_{r=0}^{q} y^{kr}Q_{B-rk}(y)D_k(y)^{q-r} \in\mathbb Z[y],

proving (1). Moreover,

\deg\!\left(D_k(y)^{q+1}C_B(y)\right) \le M+k-1+q(k-1).

Consequently the occurrence counts satisfy a homogeneous linear recurrence with characteristic polynomial dividing

\bigl(x^{k-1}-x^{k-2}-\cdots-x-1\bigr)^{q+1}

at every index $n\ge M+k+q(k-1)$ .

For the exact stated conjecture $k\ge3$ , an admissible uniform exponent is therefore

s(B)=1+\left\lfloor\frac{\min(B)}k\right\rfloor.

The proof also covers $k=2$ , arbitrary factor lengths, nonfactors, overlapping occurrences, and an explicit finite numerator construction. The block decomposition and the length-one and length-two cases were already established in the cited paper; the disappearing-boundary argument proves the previously open arbitrary-length assertion.