Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.
Minimal Automaton and Asymptotics for the Parity of Zeckendorf Digit Sums
2025-11-04
We examine the parity behaviour of the Zeckendorf sum-of-digits function.
For each integer $n\ge0$, let $\sZ(n)$ denote the number of $1$’s in the canonical Zeckendorf representation of $n$, and define $\piZ(n)=\sZ(n)\bmod2$.
We prove that the sequence $\piZ$ is \emph{Fibonacci-automatic}: it is generated by a deterministic finite automaton with output whose states encode both Fibonacci-admissibility and digit-sum parity.
An explicit minimal automaton is constructed and its minimality is established via the Myhill–Nerode correspondence.
The transition structure of this automaton yields a homogeneous linear recurrence for the run-lengths of consecutive equal output bits, from which we derive a rational generating function and precise asymptotics with an effective error bound.
The results provide a complete algebraic and analytic description of the Zeckendorf parity sequence and illustrate the interaction between numeration systems, automata theory, and analytic combinatorics in the Fibonacci setting.
\emph{All tables and certificates are reproduced by a short console program \texttt{ZeckParity} included as ancillary material; see \Cref{rem:reprod-cert} and \Cref{app:ancillary}.}
(GitHub repository \ZeckParityRepo).
Ссылка для цитирования:
Kundnani R., Kant Sh., Alam K. 2025. Minimal Automaton and Asymptotics for the Parity of Zeckendorf Digit Sums. PREPRINTS.RU. https://doi.org/10.24108/preprints-3113841
Список литературы
1. J.-P. Allouche and J. Shallit, *Automatic Sequences: Theory, Applications, Generalizations*, Cambridge University Press, 2003.
2. C. Frougny, “Representations of Numbers and Finite Automata,” *Mathematical Systems Theory* **25** (1992), 37–60.
3. J.-P. Allouche and J. Shallit, “The Ubiquitous Prouhet–Thue–Morse Sequence,” in *Sequences and Their Applications (SETA)*, Springer, 1999, pp. 1–16.
4. M. Rigo and S. Wandelt, “On Fibonacci-automatic Words,” *Theoretical Computer Science* **410** (2010), 286–294.
5. J. Shallit et al., *Walnut* software, available at: [https://cs.uwaterloo.ca/~shallit/walnut.html](https://cs.uwaterloo.ca/~shallit/walnut.html)
6. *AutomataLib*, available at: [https://github.com/LearnLib/automatalib](https://github.com/LearnLib/automatalib)
7. C. Frougny and B. Solomyak, “Finite β-Expansions,” *Ergodic Theory and Dynamical Systems* **12** (1992), 713–723.
8. J. Berstel and C. Reutenauer, *Rational Series and Their Languages*, Springer, 1988.
9. R. K. Thakurdas, *ZeckParity Ancillary Code (v1.0.0)*, GitHub repository, [https://github.com/kundnanirt/ZeckParity2025](https://github.com/kundnanirt/ZeckParity2025), 2025.
10. S. Eilenberg, *Automata, Languages, and Machines, Vol. A*, Academic Press, 1974.
11. P. Flajolet and R. Sedgewick, *Analytic Combinatorics*, Cambridge University Press, 2009.
