Properties of Multidimensional Vector Zeckendorf Representations

Abstract

Zeckendorf's Theorem says that for all $k\ge 3$, every nonnegative integer has a unique $k$-Zeckendorf representation as a sum of distinct $k$-bonacci numbers, where no $k$ consecutive $k$-bonacci numbers are present in the representation. Anderson and Bicknell-Johnson extend this result to the multidimensional context: letting the $k$-bonacci vectors ${\vec{\mathbf{X}}}_i\in {\mathbb{Z}}^{k-1}$ be given by ${\vec{\mathbf{X}}}_0=\vec{0}$, ${\vec{\mathbf{X}}}_{-i}={\vec{\mathbf{e}}}_i$ for $1\le i\le k-1$, and ${\vec{\mathbf{X}}}_n={\sum }_{i=1}^k{\vec{\mathbf{X}}}_{n-i}$ for all $n\in \mathbb{Z}$, they show that for all $k\ge 3$, every $\vec{\mathbf{v}}\in {\mathbb{Z}}^{k-1}$ has a unique $k$-bonacci vector Zeckendorf representation, a sum of distinct $k$-bonacci vectors where no $k$ consecutive $k$-bonacci vectors are present in the representation. Their proof provides an inductive algorithm for finding such representations. We present two improved algorithms for finding the $k$-bonacci vector Zeckendorf representation of $\vec{\mathbf{v}}$ and analyze their relative efficiency. We utilize a projection map $S_n:{\mathbb{Z}}^{k-1}\to {\mathbb{Z}}_{\ge 0}$, introduced in Anderson and Bicknell-Johnson work, that reduces the study of $k$-bonacci vector representations to the setting of $k$-bonacci number representations, provided a lower bound is established for the most negatively indexed $k$-bonacci vector present in the $k$-bonacci vector Zeckendorf representation of $\vec{\mathbf{v}}$. Using this map and a bijection between ${\mathbb{Z}}^{k-1}$ and ${\mathbb{Z}}_{\ge 0}$, we further show that the number of and gaps between summands in $k$-bonacci vector Zeckendorf representations exhibit the same properties as those in $k$-Zeckendorf representations and that $k$-bonacci vector Zeckendorf representations exhibit summand minimality.