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

zbMATH Open1401.11030arXiv1606.09309MaRDI QIDQ4558130FDOQ4558130

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

Publication date: 21 November 2018

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.

Full work available at URL: https://arxiv.org/abs/1606.09309

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

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)

Cited In (9)

• Generalizing Zeckendorf's theorem to \(f\)-decompositions
• Title not available (Why is that?)
• Omitting types for finite variable fragments and complete representations of algebras
• A probabilistic approach to generalized Zeckendorf decompositions
• Omitting types algebraically and more about amalgamation for modal cylindric algebras
• Title not available (Why is that?)
• Martin's axiom, omitting types, and complete representations in algebraic logic
• Patterns in variations of the Fibonacci sequence
• Omitting types for algebraizable extensions of first order logic

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)