Generalizing Zeckendorf's Theorem to f-decompositions

• Published in 2013
• Added on 2014-04-28

A beautiful theorem of Zeckendorf states that every positive integer can be uniquely decomposed as a sum of non-consecutive Fibonacci numbers $\{F_n\}$, where $F_1 = 1$, $F_2 = 2$ and $F_{n+1} = F_n + F_{n-1}$. For general recurrences $\{G_n\}$ with non-negative coefficients, there is a notion of a legal decomposition which again leads to a unique representation, and the number of summands in the representations of uniformly randomly chosen $m \in [G_n, G_{n+1})$ converges to a normal distribution as $n \to \infty$. We consider the converse question: given a notion of legal decomposition, is it possible to construct a sequence $\{a_n\}$ such that every positive integer can be decomposed as a sum of terms from the sequence? We encode a notion of legal decomposition as a function $f:\N_0\to\N_0$ and say that if $a_n$ is in an "$f$-decomposition", then the decomposition cannot contain the $f(n)$ terms immediately before $a_n$ in the sequence; special choices of $f$ yield many well known decompositions (including base-$b$, Zeckendorf and factorial). We prove that for any $f:\N_0\to\N_0$, there exists a sequence $\{a_n\}_{n=0}^\infty$ such that every positive integer has a unique $f$-decomposition using $\{a_n\}$. Further, if $f$ is periodic, then the unique increasing sequence $\{a_n\}$ that corresponds to $f$ satisfies a linear recurrence relation. Previous research only handled recurrence relations with no negative coefficients. We find a function $f$ that yields a sequence that cannot be described by such a recurrence relation. Finally, for a class of functions $f$, we prove that the number of summands in the $f$-decomposition of integers between two consecutive terms of the sequence converges to a normal distribution.

Links

• http://arxiv.org/abs/1309.5599
• http://arxiv.org/pdf/1309.5599v1

Other information

BibTeX entry

@article{Demontigny2013,
	key = {Demontigny2013},
	type = {article},
	title = {Generalizing Zeckendorf's Theorem to f-decompositions},
	author = {Demontigny, Philippe and Do, Thao and Kulkarni, Archit and Miller, Steven J. and Moon, David and Varma, Umang},
	abstract = {A beautiful theorem of Zeckendorf states that every positive integer can be
uniquely decomposed as a sum of non-consecutive Fibonacci numbers {\$}\{\{}F{\_}n\{\}}{\$},
where {\$}F{\_}1 = 1{\$}, {\$}F{\_}2 = 2{\$} and {\$}F{\_}{\{}n+1{\}} = F{\_}n + F{\_}{\{}n-1{\}}{\$}. For general
recurrences {\$}\{\{}G{\_}n\{\}}{\$} with non-negative coefficients, there is a notion of a
legal decomposition which again leads to a unique representation, and the
number of summands in the representations of uniformly randomly chosen {\$}m \in
[G{\_}n, G{\_}{\{}n+1{\}}){\$} converges to a normal distribution as {\$}n \to \infty{\$}.
  We consider the converse question: given a notion of legal decomposition, is
it possible to construct a sequence {\$}\{\{}a{\_}n\{\}}{\$} such that every positive integer
can be decomposed as a sum of terms from the sequence? We encode a notion of
legal decomposition as a function {\$}f:\N{\_}0\to\N{\_}0{\$} and say that if {\$}a{\_}n{\$} is in
an "{\$}f{\$}-decomposition", then the decomposition cannot contain the {\$}f(n){\$} terms
immediately before {\$}a{\_}n{\$} in the sequence; special choices of {\$}f{\$} yield many
well known decompositions (including base-{\$}b{\$}, Zeckendorf and factorial). We
prove that for any {\$}f:\N{\_}0\to\N{\_}0{\$}, there exists a sequence
{\$}\{\{}a{\_}n\{\}}{\_}{\{}n=0{\}}^\infty{\$} such that every positive integer has a unique
{\$}f{\$}-decomposition using {\$}\{\{}a{\_}n\{\}}{\$}. Further, if {\$}f{\$} is periodic, then the unique
increasing sequence {\$}\{\{}a{\_}n\{\}}{\$} that corresponds to {\$}f{\$} satisfies a linear
recurrence relation. Previous research only handled recurrence relations with
no negative coefficients. We find a function {\$}f{\$} that yields a sequence that
cannot be described by such a recurrence relation. Finally, for a class of
functions {\$}f{\$}, we prove that the number of summands in the {\$}f{\$}-decomposition of
integers between two consecutive terms of the sequence converges to a normal
distribution.},
	comment = {},
	date_added = {2014-04-28},
	date_published = {2013-09-01},
	urls = {http://arxiv.org/abs/1309.5599,http://arxiv.org/pdf/1309.5599v1},
	collections = {Unusual arithmetic,Fibonaccinalia,Integerology},
	month = {sep},
	url = {http://arxiv.org/abs/1309.5599 http://arxiv.org/pdf/1309.5599v1},
	year = 2013,
	archivePrefix = {arXiv},
	eprint = {1309.5599},
	primaryClass = {math.NT},
	urldate = {2014-04-28}
}