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

MaRDI QIDQ4558130zbMATH OpenFDO

Authors Minerva Catral, Pari L. Ford, Pamela E. Harris, Steven J. Miller, Dawn Nelson, Zhao Pan, Huanzhong Xu

Publication date 21 November 2018

Full work available at URL https://arxiv.org/abs/1606.09309, https://www.fq.math.ca/Abstracts/55-3/catral.pdf

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Density, gaps, topology (11B05) Numerical aspects of recurrence relations (65Q30)

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 $min[a_n,a_{n+1})$ becomes normally distributed as $noinfty$, 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.

Recommendations

• Omitting types for finite variable fragments and complete representations of algebras
• Martin's axiom, omitting types, and complete representations in algebraic logic
• Atom canonicity and first order definability in classes of algebras of relations
• Existence of certain finite relation algebras implies failure of omitting types for \(L_n\)
• Atom-canonicity in varieties of cylindric algebras with applications to omitting types in multi-modal logic

Cited in

(15)

• Bin decompositions
• Martin's axiom, omitting types, and complete representations in algebraic logic
• scientific article; zbMATH DE number 7676366 (Why is no real title available?)
• Legal decompositions arising from non-positive linear recurrences
• Omitting types for algebraizable extensions of first order logic
• A probabilistic approach to generalized Zeckendorf decompositions
• Generalizing Zeckendorf's theorem to \(f\)-decompositions
• Existence of certain finite relation algebras implies failure of omitting types for \(L_n\)
• Atom canonicity and first order definability in classes of algebras of relations
• Omitting types for finite variable fragments and complete representations of algebras
• Omitting types algebraically and more about amalgamation for modal cylindric algebras
• On the asymptotic behavior of variance of PLRS decompositions
• Atom-canonicity in varieties of cylindric algebras with applications to omitting types in multi-modal logic
• scientific article; zbMATH DE number 7676365 (Why is no real title available?)
• Patterns in variations of the Fibonacci sequence

This page was built for publication: New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558130)