New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences

Abstract

Zeckendorf's theorem states every positive integer has a unique decomposition as a sum of non-adjacent Fibonacci numbers. This result has been generalized to many sequences $\{a_n\}$ arising from an integer positive linear recurrence, each of which has a corresponding notion of a legal decomposition. Previous work proved the number of summands in decompositions of $m\in [a_n,a_{n+1})$ becomes normally distributed as $n\to \infty$, and the individual gap measures associated to each $m$ converge to geometric random variables, when the leading coefficient in the recurrence is positive. We explore what happens when this assumption is removed in two special sequences. In one we regain all previous results, including unique decomposition; in the other the number of legal decompositions exponentially grows and the natural choice for the legal decomposition (the greedy algorithm) only works approximately 92.6\% of the time (though a slight modification always works). We find a connection between the two sequences, which explains why the distribution of the number of summands and gaps between summands behave the same in the two examples. In the course of our investigations we found a new perspective on dealing with roots of polynomials associated to the characteristic polynomials. This allows us to remove the need for the detailed technical analysis of their properties which greatly complicated the proofs of many earlier results in the subject, as well as handle new cases beyond the reach of existing techniques.

arXiv commentVersion 1.0, 39 pages, 1 figure (added link in bibliography)

References in corpus (7)

• Generalizing Zeckendorf's Theorem to f-decompositions
• On the number of summands in Zeckendorf decompositions
• The Average Gap Distribution for Generalized Zeckendorf Decompositions
• Legal Decompositions Arising from Non-positive Linear Recurrences
• Central Limit Theorems for Gaps of Generalized Zeckendorf Decompositions
• A Generalization of Zeckendorf's Theorem via Circumscribed $m$-gons
• Individual Gap Measures from Generalized Zeckendorf Decompositions

Cited by in corpus (12)

• Legal Decompositions Arising from Non-positive Linear Recurrences
• Central Limit Theorems for Gaps of Generalized Zeckendorf Decompositions
• Summand minimality and asymptotic convergence of generalized Zeckendorf decompositions
• The Generalized Zeckendorf Game
• Individual Gap Measures from Generalized Zeckendorf Decompositions
• Gaps of Summands of the Zeckendorf Lattice
• Gaussian Behavior in Zeckendorf Decompositions From Lattices
• Generalizing Zeckendorf's Theorem to Homogeneous Linear Recurrences, II
• Central Limit Theorems for Compound Paths on the 2-Dimensional Lattice
• Limiting Distributions in Generalized Zeckendorf Decompositions
• On the Asymptotic Behavior of Variance of PLRS Decompositions
• Zeckendorf's Theorem Using Indices in an Arithmetic Progression