Geometric Progressions meet Zeckendorf Representations

Diego Marques, Pavel Trojovský · 2025

Read Geometric Progressions meet Zeckendorf Representations by Diego Marques, Pavel Trojovský (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-19586.txt.

Introduction

Diego Marques and Pavel Trojovsky mix geometric progressions with the Zeckendorf writing system, where every integer is a sum of non-consecutive Fibonacci numbers. The work is prompted by an Erdős conjecture about ternary expansions and by recent results on progressions meeting Cantor-like sets in ordinary bases. Forbidden digit patterns are the heart of the question.

Fix any finite set of forbidden binary patterns and any window onto the last digits. The authors prove the exponents for which a progression term's Zeckendorf expansion avoids those patterns in the window form a set that is either finite or eventually periodic. Wild avoidance, in other words, cannot continue in a chaotic way.

Catalog record

CREATORDiego Marques, Pavel Trojovský
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-19586

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Geometric Progressions meet Zeckendorf Representations Diego Marques, Pavel Trojovský Abstract . Motivated by Erdős’ ternary conjecture and by recent work of Cui–Ma–Jiang [“Geometric progressions meet Cantor sets”, Chaos Solitons Fractals 163 (2022), 112567.] on intersections between geometric progressions and Cantor-like sets in standard bases, we study the corresponding problem in the Zeckendorf numeration system. We prove that, for any fixed finite set of forbidden binary patterns, any integers u ≥ 1 u\geq 1 , q ≥ 2 q\geq 2 , and any window size M M , the set of exponents n n for which the Zeckendorf expansion of u ​ q n uq^{n} avoids the forbidden patterns within its M M least significant digits is either finite or ultimately periodic. 2020 Mathematics Subject Classification Primary 11B39; Secondary 11K55, 37B10, 68Q45 1. Introduction The interplay between multiplicative structures (such as geometric progressions) and digital structures (such as numeration systems with local constraints) is a fertile source of problems at the interface of number theory, combinatorics, and symbolic dynamics. A classical example is Erdős’ ternary conjecture [ 3 ] , asserting that for all n\geq 9 the base- 3 expansion of 2^{n} contains the digit 2 . Interpreting the middle-third Cantor set as the set of reals whose ternary expansions avoid the digit 1 , this conjecture can be viewed as a finiteness statement for the intersection of a geometric progression with a Cantor-type digit-restricted set. For standard integer bases b\geq 2 , Cui, Ma, and Jiang [ 2 ] developed an algorithmic framework to study intersections of geometric progressions with Cantor-like subsets of the integers defined by forbidden blocks in base- b expansions. Their approach encodes the carry propagation of multiplication into a finite combinatorial object, leading to effective decidability results. In the present paper we pursue an analogous viewpoint in a non-standard numeration system, namely the Zeckendorf representation associated with the Fibonacci numbers. Let (F_{n})_{n\geq 0} be defined by F_{0}=0 , F_{1}=1 , F_{n+2}=F_{n+1}+F_{n} . By Zeckendorf’s theorem, every integer N\geq 1 admits a unique decomposition N=\sum_{i=2}^{k}\varepsilon_{i}F_{i}, with \varepsilon_{i}\in\{0,1\} , \varepsilon_{k}=1 , and \varepsilon_{i}\varepsilon_{i+1}=0 for 2\leq i<k . We write Z(N)=\varepsilon_{k}\varepsilon_{k-1}\cdots\varepsilon_{2} for this Zeckendorf word. Symbolically, the set of Zeckendorf words is the Golden Mean shift , i.e., the language over \{0,1\} with the block 11 forbidden (together with the usual “no leading zeros” convention). Remark on digit order. The representation Z(N)=\varepsilon_{k}\varepsilon_{k-1}\cdots\varepsilon_{2} lists digits from the most significant to the least significant. For local arithmetic (carry propagation) it is more natural to work with the reversed order \operatorname{rev}(Z(N))=\varepsilon_{2}\varepsilon_{3}\cdots\varepsilon_{k}, i.e., reading from the least significant digit upward. All subsequent notation will refer to this LSD-first stream. Fix a finite family \mathcal{F} of non-empty binary words, thought of as additional forbidden patterns. This defines a Zeckendorf-restricted subset \mathcal{K}_{\mathcal{F}}=\{N\geq 1:\ \mathrm{rev}(Z(N))\ \text{contains no factor from }\mathcal{F}\}, where \mathrm{rev}(Z(N)) lists the Zeckendorf digits from the least significant digit (the coefficient of F_{2} ) upward. Given integers u\geq 1 and q\geq 2 , we seek to understand the set of exponents S_{u}=\{n\geq 0:\ uq^{n}\in\mathcal{K}_{\mathcal{F}}\}. If \mathcal{F}=\{11\} , then \mathcal{K}_{\mathcal{F}} coincides with the full Zeckendorf language and S_{u}=\mathbb{N}_{\geq 0} , so the interesting case is when \mathcal{F} imposes genuinely new constraints. A direct analysis of S_{u} requires inspecting the entire Zeckendorf expansion of uq^{n} , whose length grows linearly with n . To obtain an effective result capturing the local arithmetic, we introduce a window-restricted variant. Let L=\max\{|f|:f\in\mathcal{F}\} and fix M\geq L . Since we will take prefixes of least-significant-digit streams, we adopt a padding convention that avoids artificially creating forbidden patterns when the true Zeckendorf expansion is shorter than the window. Let \#\notin\{0,1\} be a neutral padding symbol and define the rightinfinite word \widetilde{Z}(N):=\operatorname{rev}(Z(N))\,\#^{\omega}\in\{0,1,\#\}^{\mathbb{N}}. The symbol \# never equals 0 or 1 ; thus a forbidden binary pattern cannot be created by involving a \# . Hence the prefix of length M of \widetilde{Z}(N) consists only of genuine Zeckendorf digits whenever N is large enough, and otherwise contains \# ’s that do not affect the avoidance condition. We say that a finite word v\in\{0,1,\#\}^{*} avoids \mathcal{F} if no f\in\mathcal{F} occurs as a factor of v (equivalently, occurrences cannot use the symbol \# ). We then define \mathcal{K}_{\mathcal{F}}^{(M)}=\{N\geq 1:\ \mathrm{pref}_{M}(\widetilde{Z}(N))\ \text{avoids }\mathcal{F}\}, where for a word w=w_{0}w_{1}w_{2}\dots\in\{0,1,\#\}^{\mathbb{N}} and an integer M\geq 1 , \mathrm{pref}_{M}(w) denotes its prefix of length M , i.e., w_{0}w_{1}\dots w_{M-1} . Thus constraints are enforced only within the first M least significant Zeckendorf digits. Clearly \mathcal{K}_{\mathcal{F}}\subseteq\mathcal{K}_{\mathcal{F}}^{(M)} for every M , and with the above padding convention one has \mathcal{K}_{\mathcal{F}}=\bigcap_{M\geq L}\mathcal{K}_{\mathcal{F}}^{(M)}. Accordingly, we set S_{u}^{(M)}=\{n\geq 0:\ uq^{n}\in\mathcal{K}_{\mathcal{F}}^{(M)}\}. Our main result shows that, for each fixed window length M , the set S_{u}^{(M)} is always ultimately periodic, and the period and preperiod can be computed effectively. Theorem 1.1 . Let u\geq 1 , q\geq 2 be integers, and let \mathcal{F} be a finite family of non-empty binary words. Let L=\max\{|f|:f\in\mathcal{F}\} and fix M\geq L . Then the set S_{u}^{(M)}=\{n\geq 0:\ uq^{n}\in\mathcal{K}_{\mathcal{F}}^{(M)}\} is either finite or ultimately periodic. That is, there exist integers n_{0}\geq 0 and p\geq 1 such that n\in S_{u}^{(M)}\ \Longleftrightarrow\ n+p\in S_{u}^{(M)}\qquad(n\geq n_{0}). Moreover, one can effectively compute such a pair (n_{0},p) and decide whether S_{u}^{(M)} is finite or infinite. In the finite case, the same procedure outputs all elements of S_{u}^{(M)} . The proof is entirely finite-state. The crucial input is the fact that multiplication by a fixed integer q in the Fibonacci numeration system is realizable by a finite sequential transducer [ 4 ] . Reading digits from the least significant side, this transducer induces, for each M , a deterministic update rule on the set of length- M windows \{0,1,\#\}^{M} . After composing with the finite automaton that checks avoidance of \mathcal{F} inside the window, we obtain a deterministic dynamical system on a finite state space. The orbit associated with the progression (uq^{n})_{n\geq 0} is therefore eventually periodic, which yields ultimate periodicity of S_{u}^{(M)} as an immediate corollary. The same finite-state construction gives an explicit algorithm to compute the eventual period. Theorem 1.1 gives a rigorous and completely effective solution to the window-restricted problem. While passing from S_{u}^{(M)} to the global set S_{u} entails additional difficulties (one must control where forbidden patterns may first appear as n varies), the window-restricted variant already captures the local dynamics of Zeckendorf multiplication and provides a practical method to detect all exponents for which the low-order Zeckendorf digits of uq^{n} satisfy prescribed constraints. 2. The proof of Theorem 1.1 2.1. Automata-theoretic dictionary The proof of our main result relies on concepts from automata theory, which we briefly recall here for readers less familiar with this terminology. Our presentation follows standard references such as Frougny [ 4 ] and Allouche & Shallit [ 1 ] . Finite automaton. A deterministic finite automaton (DFA) consists of a finite set of states , an input alphabet, a transition function that specifies how to move between states when reading a symbol, a designated initial state, and a set of accepting states. Such an automaton processes an input word symbol by symbol, and accepts the word if it ends in an accepting state. DFAs precisely recognize the class of regular languages . Transducer. A finite-state transducer extends the automaton model by producing output. Formally, it is a

Read the complete text