Multidimensional Fibonacci Coding

Abstract

Fibonacci codes are self-synchronizing variable-length codes that are proven useful for their robustness and compression capability. Asymptotically, these codes provide better compression efficiency as the order of the underlying Fibonacci sequence increases but at the price of the increased suffix length. We propose a circumvention to this problem by introducing higher-dimensional Fibonacci codes for integer vectors. The resulting multidimensional Fibonacci coding is comparable to the classical one in terms of compression; while encoding several numbers all at once for a shared suffix generally results in a shorter codeword, the efficiency takes a backlash when terms from different orders of magnitude are encoded together. In addition, while laying the groundwork for the new encoding scheme, we provide extensive theoretical background and generalize the theorem of Zeckendorf to higher order. As such, our work unifies several variations of Zeckendorf’s theorem while also providing new grounds for its legitimacy.

1. Introduction

A fundamental idea in data compression is to assign shorter codewords to symbols or groups of symbols that appear with higher probability in the source data [1]. This results in what is called a variable-length code, meaning that the length of each codeword may not be equal, and one of the earliest practical codes of such nature are the Huffman codes [2]. This code approaches theoretical compression limit under certain scenarios [1] and has recently been amended to create Tagged Huffman Codes [3] and End-Tagged Dense Codes [4] to accommodate database searches.

Popular alternatives to these codes are codes with suffix delimiters, where certain patterns mark the end of a codeword [5]. A competent example in this class of codes is the Fibonacci code, which is a result of a binary numeration system for the integers known as Zeckendorf representation. The scheme was introduced by [6] and generalized to a higher order in [7]. In terms of data compression, Fibonacci codes are optimal under some distributions and can be used as alternatives to Huffman codes [1,8]. Fibonacci codes are naturally suitable for integer data, where fast encoding and decoding algorithms can be implemented [9,10,11]. In addition, compared with other variable-length codes for the integers such as logarithmic ramp [12] and Elias codes [13], Fibonacci codes provide much better resistance against insertion and deletion errors. Other applications of the Fibonacci sequence in information science include the study of Morse code as a monoid [14,15], Wavelet trees [16], and zero-knowledge cryptography [17].

While suffix codes have been shown to offer adjustability to some extent [5], a great burden for a code with suffix delimiters to bear is its own suffix. A longer suffix gives more flexibility in the coded data, hence yielding denser codes, but obviously the codewords now have to carry longer appendage. This is particularly the case for the Fibonacci codes of higher order [18]. In this paper, we introduce Fibonacci coding for a sequential string of integers. In the proposed scheme, a constituent of integers is encoded together with a single delimiter, thus making Fibonacci codes of higher order more practical.

To generalize Fibonacci codes to the full extent, we re-examine their origin, which is the theorem of Zeckendorf. This much-celebrated theorem states that every positive integer n can be written uniquely as:

$$n=F_{i_1}+F_{i_2}+\cdots +F_{i_j}$$

where the $F_i$s are Fibonacci numbers and $i_1,i_2-i_1,\dots ,i_j-i_{j-1}\ge 2$. In other words, one may represent a positive integer as sum of nonconsecutive Fibonacci numbers. This theorem has been generalized and investigated in many directions; similar results can be stated for the negaFibonacci sequence [19,20], the generalized Fibonacci sequence of order k [21,22], and linear recurrence sequences [23,24]. The distribution of the number of terms in a Zeckendorf decomposition is studied in [25,26,27], where a probabilistic approach has recently been applied [28].

Meanwhile, the Fibonacci sequence itself has also been generalized in many directions. Here, noninteger Fibonacci sequences have been studied mostly on the complex numbers [29,30]. In particular, Jordan [31] and Harman [32] consider Fibonacci sequences whose initial terms and indices are Gaussian integers. Other generalizations usually involve an identity whose integer terms yield the classical Fibonacci numbers. For example, Binet’s formula is exploited in [33,34] where a Fibonacci function is defined over the real and complex numbers.

In this paper, we are interested in a generalization of Zeckendorf’s theorem in its purest form: We consider any mathematical sequences that satisfy the generalized Fibonacci recurrence relation and examine elements that can be written as a sum of terms from the sequence. As a result, mathematical spaces with minimal structure that meet our requirement are the free $\mathbb{Z}$-modules. Loosely speaking, they are spaces of vectors with integer components. This choice of spaces allows our generalizations to encompass, for example, integer vectors, arrays, or blocks of integers of fixed length; Gaussian and Eisenstein integers; lattices; and the ring $\mathbb{Z}\left[\alpha \right]$, where $\alpha$ is algebraic.

We summarize the contributions of this paper as follows:

• We introduce the notion of k-equivalent sequences. This approach technically treats elements that can be generated from a Fibonacci sequence as a number system using sequence elements as a basis. This key mechanism allows us to manipulate the “digits” of a representation of a number without an explicit knowledge of the underlying Fibonacci sequence. We prove that an element has a Zeckendorf decomposition if and only if it can be written as a finite sum (with multiplicities) of sequence elements.
• We provide a necessary and sufficient condition for Zeckendorf’s theorem to hold in a free $\mathbb{Z}$-module. Obviously, the classical Zeckendorf’s theorem can be viewed as a case of our generalization. We also give a sufficient condition that makes the representation unique.
• We propose multidimensional Fibonacci coding for free $\mathbb{Z}$-modules along with a natural and explicit encoding and decoding algorithm. This is the first work that makes possible native Fibonacci coding for non-integers. Not only that, the resulting codes inherit their robustness property from the standard Fibonacci codes, and they excel in terms of compression efficiency. We demonstrate both theoretically and numerically that the performance on the compression of multidimensional Fibonacci coding is comparable to the classical Fibonacci coding. The proposed scheme has an advantage in that the suffix now appears less frequently, thus cutting down on extraneous bits. However, it can be disadvantageous when a large integer appears together with a small integer in the source vector data. In such case, the larger integer could unproportionally drive up the length of the codeword.

The remainder of this paper is organized as follows. Section 2 sets the definitions that will be used throughout the paper. In Section 3, we prove several useful results concerning k-equivalent sequences. Generalizations of Zeckendorf’s theorem are given in Section 4. We establish multidimensional Fibonacci coding in Section 5, discuss its efficiency and demonstrate simulation results in Section 6, and conclude in Section 7.

2. Definitions and Terminologies

We first give a definition for free modules and Fibonacci sequences of higher order. A free $\mathbb{Z}$-module is a module over $\mathbb{Z}$ with a basis. Namely, M is a free $\mathbb{Z}$-module of rank l if it is a group under addition and

$$M={\alpha }_1\mathbb{Z}\oplus {\alpha }_2\mathbb{Z}\oplus \cdots \oplus {\alpha }_l\mathbb{Z}$$

for some ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_l$ that are integrally independent, meaning that the only integer solution to the equation $n_1{\alpha }_1+n_2{\alpha }_2+\cdots +n_l{\alpha }_l=0$ is $n_1=n_2=\cdots =n_l=0$. The elements ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_l$ are called a basis for M, and every element of M can be written uniquely as: $n_1{\alpha }_1+n_2{\alpha }_2+\cdots +n_l{\alpha }_l$, where $n_1,n_2,\dots ,n_l\in \mathbb{Z}$. For $n\in {\mathbb{Z}}^{+}$ and $m\in M$, we write $nm$ to mean $\underset{n\mathrm{times}}{\underbrace{m+m+\cdots +m}}$. Note that multiplication between module elements may or may not be defined.

We are interested in an extremely broad version of a Fibonacci sequence, so we adopt only the fundamental recurrence relation and a corresponding generalization of a Zeckendorf representation.

Definition 1.

A Fibonacci sequence of order k is a doubly infinite sequence:

$${\left(F_r\right)}_{r\in \mathbb{Z}}=(\dots ,F_{-1},F_0,F_1,\dots )$$

where

$$F_{n-k}+\cdots +F_{n-2}+F_{n-1}=F_n$$

for all integers n.

Here, a doubly infinite sequence (also called two-way infinite sequence) is a sequence that goes in both directions.

Definition 2.

Let ${\left(F_r\right)}_{r\in \mathbb{Z}}$ be a Fibonacci sequence of order k. An element m is Zeckendorf in $\left(F_r\right)$ if it can be written as a finite sum of terms in $\left(F_r\right)$ with no k consecutive terms. A set M is Zeckendorf in $\left(F_r\right)$ if every element of M is.

Note that we do not specify the initial condition for a Fibonacci sequence of order k. In fact, we will reverse engineer the theorem of Zeckendorf and identify all initial conditions that the theorem holds. In other words, instead of proving a version of Zeckendorf’s theorem for a particular sequence, we set forth to classify all sequences that are in favor of the theorem.

A Fibonacci sequence of order k has degree of freedom k; knowing any k consecutive terms is sufficient to generate the entire sequence. For $k\ge 2$, the characteristic polynomial of a Fibonacci sequence of order k is $x^k-x^{k-1}-x^{k-2}-\cdots -x-1$. It is known [35] that this polynomial has k distinct roots ${\lambda }_k,{\lambda }_{k,2},\dots ,{\lambda }_{k,k}$, where ${\lambda }_k\in (1,2)$ and ${\lambda }_{k,2},\dots ,{\lambda }_{k,k}$ lie in the unit circle. Note that the sequence ${\left({\lambda }_k^r\right)}_{r\in \mathbb{Z}}$ is a special case of Fibonacci sequence of order k. We call this sequence primitive.

Example 1.

In this example, we consider several Fibonacci sequences of order 3 (with respect to a different initial conditions for $F_0$, $F_1$, and $F_2$):

• The usual Tribonacci sequence is defined using $F_0=F_1=1$, $F_2=2$, and $F_{n-3}+F_{n-2}+F_{n-1}=F_n$. The first few terms of this sequence are:

  $$\begin{array}{cccccccccccc}\hfill 1,& \hfill 1,& \hfill 2,& \hfill 4,& \hfill 7,& \hfill 13,& \hfill 24,& \hfill 44,& \hfill 81,& \hfill 149,& \hfill 274,& \hfill \dots .\end{array}$$

  The doubly infinite generalization of this sequence is given by:

  $$\begin{array}{cccccccccccc}\hfill \dots ,& \hfill 5,& \hfill -8,& \hfill 4,& \hfill 1,& \hfill -3,& \hfill 2,& \hfill 0,& \hfill -1,& \hfill 1,& \hfill 0,& \hfill 0,\end{array}$$

  $$\begin{array}{cccccccccccc}\hfill 1,& \hfill 1,& \hfill 2,& \hfill 4,& \hfill 7,& \hfill 13,& \hfill 24,& \hfill 44,& \hfill 81,& \hfill 149,& \hfill 274,& \hfill \dots .\end{array}$$
• The three roots of a polynomial $x^3-x^2-x-1$ are ${\lambda }_3\approx 1.839$, ${\lambda }_{3,2}\approx -0.42-0.606i$, and ${\lambda }_{3,3}\approx -0.42+0.606i$. The primitive Fibonacci sequence of order 3 is the sequence ${\left({\lambda }_3^r\right)}_{r\in \mathbb{Z}}$, which is approximately:

  $$\begin{array}{ccccccccccc}\hfill \dots ,& \hfill 0.161,& \hfill 0.296,& \hfill 0.544,& \hfill 1,& \hfill 1.839,& \hfill 3.383,& \hfill 6.222,& \hfill 11.445,& \hfill 21.05,& \hfill \dots .\end{array}$$
• A Fibonacci sequence of order 3, where $F_0=0$, $F_1=1+i$, and $F_2=2+i$ is given by:

  $$\begin{array}{ccccccccc}\hfill \dots ,& \hfill 5+i,& \hfill -2-3i,& \hfill -1+2i,& \hfill 2,& \hfill -1-i,& \hfill i,& \hfill 1,& \\ & \hfill 0,& \hfill 1+i,& \hfill 2+i,& \hfill 3+2i,& \hfill 6+4i,& \hfill 11+7i,& \hfill 20+13i,& \hfill \dots .\end{array}$$

  Here, the element of this sequence are Gaussian integers, i.e., complex numbers of the form $a+bi$, where $a,b\in \mathbb{Z}$. The element $9+5i$, for example, is Zeckendorf in this sequence since $9+5i=(5+i)+(-1+2i)+\left(2\right)+(3+2i)=F_{-7}+F_{-5}+F_{-4}+F_3$.

In order to study elements that are Zeckendorf in $\left(F_r\right)$, it is natural to consider elements of the form $\left(x_r\right)·\left(F_r\right)$, where $\left(x_r\right)$ is a doubly infinite sequence of integers and · is an infinite dot product, i.e.:

$$\left(x_r\right)·\left(F_r\right)=\sum _{r\in \mathbb{Z}}{x}_r{F}_r.$$

Roughly speaking, a collection of all elements of the form $\left(x_r\right)·\left(F_r\right)$ is a number system with the base $\left(F_r\right)$ with the digit set $\mathbb{Z}$. Here, $\left(x_r\right)$ acts like digits or coefficients for the basis $\left(F_r\right)$. These so-called coefficients can be manipulated using the following methods.

Definition 3.

Let $k>1$ be an integer. Doubly infinite sequences $\left(x_r\right)$ and $\left(y_r\right)$ are k-equivalent, denoted as $\left(x_r\right)$∼${}_k\left(y_r\right)$, if $\left(y_r\right)$ can be obtained from $\left(x_r\right)$ using finite applications of the following two operations:

Operation 1: For some $n\in \mathbb{Z}$, subtract 1 from $x_n$ and add 1 to all of $x_{n-k},\dots ,x_{n-2},x_{n-1}$.

Operation 2: For some $n\in \mathbb{Z}$, add 1 to $x_n$ and subtract 1 from all of $x_{n-k},\dots ,x_{n-2},x_{n-1}$.

It is not hard to see that Operations 1 and 2 “cancel out”, and ${\sim }_k$ is an equivalence relation. These operations also preserve the value of the dot product: If $\left(F_r\right)$ is a Fibonacci sequence of order k and $\left(x_r\right)$∼${}_k\left(y_r\right)$, then $\left(x_r\right)·\left(F_r\right)=\left(y_r\right)·\left(F_r\right)$. As we will see later, this observation is an important ingredient of our results. Finally, we give a lexicographical order ≻ to doubly infinite sequences that are zero almost everywhere, i.e., ${\left(x_r\right)}_{r\in \mathbb{Z}}\succ {\left(y_r\right)}_{r\in \mathbb{Z}}$ if the term of $\left(x_r\right)$ is larger than that of $\left(y_r\right)$ at the rightmost index, where they are not equal. Here, a sequence is zero almost everywhere if the number of its nonzero terms is finite.

3. Properties of k-Equivalent Sequences

In a way, our approach in proving a generalized theorem of Zeckendorf is in asking the following converse question: Given a Fibonacci sequence $\left(F_r\right)$ of order k, which elements can be written as a finite sum of elements from $\left(F_r\right)$ using no k consecutive terms? It is not hard to see that they are elements of the form $\left(y_r\right)·\left(F_r\right)$ where $\left(y_r\right)$ is binary, is 0 almost everywhere, and has no k consecutive 1’s. Now, instead of characterizing these elements directly, we will focus on manipulating the coefficients $\left(y_r\right)$ using Operations 1 and 2 from Definition 3. These coefficient manipulations operate independently of the underlying Fibonacci sequence $\left(F_r\right)$ of order k, and so this approach frees us from having to worry about the choice of $\left(F_r\right)$. As we will see, our results hold in a broad sense and are not limited to just any specific Fibonacci sequence. Propositions 1 and 2 given in this section will provide an effective mechanism for identifying sequences that are k-equivalent to a binary sequence with the required properties.

Proposition 1.

For any sequence ${\left(x_r\right)}_{r\in \mathbb{Z}}$ of integers that is 0 almost everywhere, there exists a sequence ${\left(y_r\right)}_{r\in \mathbb{Z}}$ such that $\left(x_r\right){\sim }_k\left(y_r\right)$, and ${\left(y_r\right)}_{r\in \mathbb{Z}}$ is either:

• Zero everywhere;
• Positive at some k consecutive terms and zero elsewhere;
• Negative at some k consecutive terms and zero elsewhere.

In addition, if ${\left(x_r\right)}_{r\in \mathbb{Z}}\ne {\left(0\right)}_{r\in \mathbb{Z}}$ is non-negative, then the k consecutive nonzero terms of ${\left(y_r\right)}_{r\in \mathbb{Z}}$ are positive.

Proof. 

A finite contiguous subsequence of ${\left(x_r\right)}_{r\in \mathbb{Z}}$ is called a cluster if the terms in its complement subsequence are all 0. In other words, $(x_s,x_{s+1},x_{s+2},\dots ,x_{t-1},x_t)$ is a cluster of ${\left(x_r\right)}_{r\in \mathbb{Z}}$ if $x_r=0$ for all $r<s$ and all $r>t$. The number of terms in a cluster is called the size of the cluster. In addition, note that a cluster may contain, begin, or end with a 0.

A sequence ${\left(x_r\right)}_{r\in \mathbb{Z}}$ must have a cluster since it is 0 almost everywhere. Now, if the size of the cluster is greater than k, then one may apply either Operation 1 or 2 from Definition 3 to eliminate the rightmost nonzero term of $\left(x_r\right)$, hence reducing the size of the cluster. Therefore, $\left(x_r\right)$ is k-equivalent to a sequence $\left(y_r\right)$ whose cluster size is k. If the terms of the cluster of $\left(y_r\right)$ are all positive, negative, or zero, then we are done. Otherwise, one may continue eliminating the rightmost nonzero term the sequence and, as a result, shift the index of the cluster by 1. We formalize this process as follows.

Initialize $\left({}^{\left(0\right)}{y}_r\right)=\left(y_r\right)$, and let ${}^{\left(0\right)}\mathrm{\Gamma }=\left({}^{\left(0\right)}{y}_s,{}^{\left(0\right)}{y}_{s+1},\dots ,{}^{\left(0\right)}{y}_{s+k-1}\right)$ be a cluster of $\left({}^{\left(0\right)}{y}_r\right)$:

• If ${}^{\left(0\right)}{y}_{s+k-1}>0$, we apply Operation 1 to eliminate ${}^{\left(0\right)}{y}_{s+k-1}$ and obtain another sequence $\left({}^{\left(1\right)}{y}_r\right)$. Here, $\left({}^{\left(0\right)}{y}_r\right){\sim }_k\left({}^{\left(1\right)}{y}_r\right)$. The cluster of $\left({}^{\left(1\right)}{y}_r\right)$ has size k, but its index has shifted from that of $\left({}^{\left(0\right)}{y}_r\right)$ by 1. Namely, the cluster of $\left({}^{\left(1\right)}{y}_r\right)$ is:

  $$\begin{array}{c}\hfill \begin{array}{cc}\hfill {}^{\left(1\right)}\mathrm{\Gamma }& =\left({}^{\left(1\right)}{y}_{s-1},{}^{\left(1\right)}{y}_s,\dots ,{}^{\left(1\right)}{y}_{s+k-2}\right)\hfill \\ \hfill & =\left({}^{\left(0\right)}{y}_{s+k-1},{}^{\left(0\right)}{y}_s+{}^{\left(0\right)}{y}_{s+k-1},{}^{\left(0\right)}{y}_{s+1}+{}^{\left(0\right)}{y}_{s+k-1},\dots ,{}^{\left(0\right)}{y}_{s+k-2}+{}^{\left(0\right)}{y}_{s+k-1}\right).\hfill \end{array}\end{array}$$

  (1)
• If ${}^{\left(0\right)}{y}_{s+k-1}<0$, we apply Operation 2 to eliminate ${}^{\left(0\right)}{y}_{s+k-1}$ and obtain another sequence $\left({}^{\left(1\right)}{y}_r\right)$. Incidentally, since ${}^{\left(0\right)}{y}_{s+k-1}$ is negative, the cluster of $\left({}^{\left(1\right)}{y}_r\right)$ also follows from the Equation (1).
• If ${}^{\left(0\right)}{y}_{s+k-1}=0$, let $\left({}^{\left(1\right)}{y}_r\right)=\left({}^{\left(0\right)}{y}_r\right)$ and:

  $$\begin{array}{cc}\hfill {}^{\left(1\right)}\mathrm{\Gamma }& =\left({}^{\left(1\right)}{y}_{s-1},{}^{\left(1\right)}{y}_s,\dots ,{}^{\left(1\right)}{y}_{s+k-2}\right)\hfill \\ \hfill & =\left({}^{\left(0\right)}{y}_{s-1},{}^{\left(0\right)}{y}_s,\dots ,{}^{\left(0\right)}{y}_{s+k-2}\right)\hfill \\ \hfill & =\left({}^{\left(0\right)}{y}_{s+k-1},{}^{\left(0\right)}{y}_s+{}^{\left(0\right)}{y}_{s+k-1},{}^{\left(0\right)}{y}_{s+1}+{}^{\left(0\right)}{y}_{s+k-1},\dots ,{}^{\left(0\right)}{y}_{s+k-2}+{}^{\left(0\right)}{y}_{s+k-1}\right)\hfill \end{array}$$

  where the last equality follows from the fact that ${}^{\left(0\right)}{y}_{s-1}={}^{\left(0\right)}{y}_{s+k-1}=0$.

It follows that, in all cases:

$${}^{\left(1\right)}{\mathrm{\Gamma }}^{\top }=A·{}^{\left(0\right)}{\mathrm{\Gamma }}^{\top }$$

where:

$$A=\left(\begin{array}{cccccc}0& 0& 0& \cdots & 0& 1\\ 1& 0& 0& \cdots & 0& 1\\ 0& 1& 0& \cdots & 0& 1\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \cdots & 1& 1\end{array}\right)$$

and ${}^{\left(0\right)}\mathrm{\Gamma },{}^{\left(1\right)}\mathrm{\Gamma }$ are taken as a $1\times k$ vector. This process can be repeated indefinitely, resulting in a collection of k-equivalent sequences $\left({}^{\left(0\right)}{y}_r\right),\left({}^{\left(1\right)}{y}_r\right),\left({}^{\left(2\right)}{y}_r\right),\dots$. The cluster size of these sequences is k, but the index of the cluster is continually shifted. Here, the clusters are collected as ${}^{\left(0\right)}\mathrm{\Gamma },{}^{\left(1\right)}\mathrm{\Gamma },{}^{\left(2\right)}\mathrm{\Gamma },\dots$. It follows that ${}^{\left(n\right)}{\mathrm{\Gamma }}^{\top }=A^n·{}^{\left(\mathrm{o}\right)}{\mathrm{\Gamma }}^{\top }$, and it remains to show that there is an n for which $A^n·{}^{\left(\mathrm{o}\right)}{\mathrm{\Gamma }}^{\top }$ is either all positive, negative, or zero.

It should not be surprising that A is the transpose of the usual Fibonacci matrix. Thus, A has a characteristic equation $x^k-x^{k-1}-x^{k-2}-\cdots -x-1$ and eigenvalues ${\lambda }_{k,1},\dots ,{\lambda }_{k,k}$, where ${\lambda }_k={\lambda }_{k,1}\in (1,2)$ and the complex norm of ${\lambda }_{k,2},\dots ,{\lambda }_{k,k}$ is less than 1 [35]. We denote by $v_i$ an eigenvector corresponding to the eigenvalue ${\lambda }_{k,i}$. Note that:

$$v_1=\left(\begin{array}{c}{\lambda }_k^{k-2}\\ {\lambda }_k^{k-2}+{\lambda }_k^{k-3}\\ {\lambda }_k^{k-2}+{\lambda }_k^{k-3}+{\lambda }_k^{k-4}\\ ⋮\\ {\lambda }_k^{k-2}+{\lambda }_k^{k-3}+\cdots +{\lambda }_k+1\\ {\lambda }_k^{k-1}\end{array}\right)$$

is real and positive. Now, one may diagonalize A as $CD{C}^{-1}$, where $D=\mathsf{diag}({\lambda }_k,{\lambda }_{k,2},\dots ,{\lambda }_{k,k})$ and $C=\left(\begin{array}{ccc}{v}_1& \cdots & v_k\end{array}\right)$. It follows that:

$$\begin{array}{cc}\hfill {}^{\left(n\right)}{\mathrm{\Gamma }}^{\top }& =A^n·{}^{\left(\mathrm{o}\right)}{\mathrm{\Gamma }}^{\top }\hfill \\ \hfill & =C{D}^n{C}^{-1}·{}^{\left(\mathrm{o}\right)}{\mathrm{\Gamma }}^{\top }\hfill \\ \hfill & =\left(\begin{array}{cccc}{\lambda }_k^n{v}_1& {\lambda }_{k,2}^n{v}_1& \cdots & {\lambda }_{k,k}^n{v}_k\end{array}\right)C^{-1}·{}^{\left(\mathrm{o}\right)}{\mathrm{\Gamma }}^{\top }\hfill \\ \hfill & ={\lambda }_k^n{c}_1{v}_1+{\lambda }_{k,2}^n{c}_2{v}_2+\cdots +{\lambda }_{k,k}^n{c}_k{v}_k\hfill \end{array}$$

where ${(c_1,\dots ,c_k)}^{\top }=C^{-1}·{}^{\left(\mathrm{o}\right)}{\mathrm{\Gamma }}^{\top }$. Here, ${\lambda }_k^n{c}_1{v}_1$ is the dominant term in the sum. Specifically, let $\mathrm{\Lambda }=max\left\{\right|{\lambda }_{k,2}|,\dots ,|{\lambda }_{k,k}\left|\right\}<1$ and $V=max\left\{\right|c_2{v}_2|,\dots ,|c_k{v}_k\left|\right\}$. Thus,

$$|{\lambda }_{k,2}^n{c}_2{v}_2+\cdots +{\lambda }_{k,k}^n{c}_k{v}_k|<(k-1){\mathrm{\Lambda }}^{n}V.$$

It follows that if n is a positive integer such that $(k-1){\mathrm{\Lambda }}^{n}V<\frac{1}{2}$, then ${}^{\left(\mathrm{n}\right)}{\mathrm{\Gamma }}^{\top }$ is the integer vector that is closest to ${\lambda }_k^n{c}_1{v}_1$. Since $v_1$ is real and positive, all entries of ${}^{\left(\mathrm{n}\right)}{\mathrm{\Gamma }}^{\top }$ will have the same sign as $c_1$. This completes the proof that ${}^{\left(n\right)}{\mathrm{\Gamma }}^{\top }=A^n·{}^{\left(\mathrm{o}\right)}{\mathrm{\Gamma }}^{\top }$ can be made all positive, negative, or zero.

For the last part of the proposition, if ${\left(x_r\right)}_{r\in \mathbb{Z}}\ne {\left(0\right)}_{r\in \mathbb{Z}}$ is non-negative, then we only need to use Operation 1, and so the cluster of ${\left(y_r\right)}_{r\in \mathbb{Z}}$ cannot be negative or zero.    □

Proposition 2.

For any sequence ${\left(x_r\right)}_{r\in \mathbb{Z}}$ of non-negative integers that is 0 almost everywhere, there exists a sequence ${\left(y_r\right)}_{r\in \mathbb{Z}}$ of 0 and 1 with no k consecutive 1’s such that $\left(x_r\right){\sim }_k\left(y_r\right)$.

Proof. 

Consider all sequences of non-negative integers that are k-equivalent to ${\left(x_r\right)}_{r\in \mathbb{Z}}$. Recall that if $\left(x_r\right){\sim }_k\left(y_r\right)$, then $\left(x_r\right)·\left({\lambda }_k^r\right)=\left(y_r\right)·\left({\lambda }_k^r\right)$, where $\left({\lambda }_k^r\right)$ is the primitive Fibonacci sequence of order k. Let N be an integer such that $\left(x_r\right)·\left({\lambda }_k^r\right)<{\lambda }_k^N$. Now, if a sequence of non-negative integers $\left(y_r\right)$ is k-equivalent to $\left(x_r\right)$, then we must have $\left(y_r\right)·\left({\lambda }_k^r\right)<{\lambda }_k^N$. Since $\left({\lambda }_k^r\right)$ is strictly positive, it follows that $y_r=0$ for all $r\ge N$. This allows us to conclude that, among all the sequences of non-negative integers that are k-equivalent to $\left(x_r\right)$, there must be one with the highest lexicographical order. We call this sequence ${\left(y_r\right)}_{r\in \mathbb{Z}}$ and claim that it satisfies the conditions required.

Suppose that $y_s\ge 2$ for some $s\in \mathbb{Z}$. We perform Operation 1 at $n=s$ and Operation 2 at $n=s+1$. This results in a sequence with higher lexicographical order than $\left(y_r\right)$, contradicting our choice of $\left(y_r\right)$. Suppose now that $y_{s-k}=\cdots =y_{s-2}=y_{s-1}=1$ for some $s\in \mathbb{Z}$. Perform Operation 2 at $n=s$ yields a sequence with higher lexicographical order, and once again that contradicts the choice of $\left(y_r\right)$. We conclude that $\left(y_r\right)$ consists only of 0 and 1 with no k consecutive 1’s.    □

We illustrate the transformations given in Propositions 1 and 2 in an example below.

Example 2.

We let $k=3$ and consider a doubly infinite sequence $\left(x_r\right)$ that is zero everywhere except $x_{-1}=-2$, $x_1=-1$, $x_2=-2$, and $x_4=1$, i.e.:

$$\left(x_r\right)=(\dots ,-2_{-1},0_0,-1_1,-2_2,0_3,1_4,\dots ).$$

Here, and throughout the example, indices are shown as subscript for improved readability. We now transform $\left(x_r\right)$ into a sequence that is positive at some three consecutive terms and zero elsewhere:

$$\begin{array}{cc}\hfill (\dots ,-2_{-1},0_0,-1_1,-2_2,0_3,1_4,\dots )& {\sim }_3(\dots ,-2_{-1},0_0,0_1,-1_2,1_3,0_4,\dots )\hfill \\ \hfill & {\sim }_3(\dots ,-2_{-1},1_0,1_1,\dots )\hfill \\ \hfill & {\sim }_3(\dots ,1_{-2},-1_{-1},2_0,0_1\dots )\hfill \\ \hfill & {\sim }_3(\dots ,1_{-3},2_{-2},0_{-1},1_0,0_1,\dots ).\hfill \\ \hfill & {\sim }_3(\dots ,2_{-3},3_{-2},1_{-1},0_0,0_1,\dots ).\hfill \end{array}$$

Here, Operation 1 is performed at indices 4,3,1,0,0 in order. Next, we transform

$(\dots ,2_{-3},3_{-2},1_{-1},\dots )$ into a binary sequence with no three consecutive ones:

$$\begin{array}{cc}\hfill (\dots ,2_{-3},3_{-2},1_{-1},\dots )& {\sim }_3(\dots ,1_{-3},2_{-2},0_{-1},1_0,\dots )\hfill \\ \hfill & {\sim }_3(\dots ,1_{-5},1_{-4},2_{-3},1_{-2},0_{-1},1_0,\dots )\hfill \\ \hfill & {\sim }_3(\dots ,1_{-5},0_{-4},1_{-3},0_{-2},1_{-1},1_0,\dots ).\hfill \end{array}$$

Here, Operations 2,1,2 are performed in order at indices $0,-2,-1$, respectively. Consider now a Fibonacci sequence of order 3 of Gaussian integers:

$$\begin{array}{ccccccc}\hfill \left(F_r\right)=(\dots ,& \hfill {(-1+2i)}_{-5},& \hfill {\left(2\right)}_{-4},& \hfill {(-1-i)}_{-3},& \hfill {\left(i\right)}_{-2},& \hfill {\left(1\right)}_{-1},& \\ & \hfill {\left(0\right)}_0,& \hfill {(1+i)}_1,& \hfill {(2+i)}_2,& \hfill {(3+2i)}_3,& \hfill {(6+4i)}_4,& \hfill \dots )\end{array}$$

from Example 1. Again, parentheses and subscript are added for readability. Note that all the above three-equivalent sequences represent the same quantity when multiplied by $\left(F_r\right)$. In particular, if $\left(y_r\right)=(\dots ,2_{-3},3_{-2},1_{-1},\dots )$ and $\left(z_r\right)=(\dots ,1_{-5},0_{-4},1_{-3},0_{-2},1_{-1},1_0,\dots )$, then

$$\left(x_r\right)·\left(F_r\right)=\left(y_r\right)·\left(F_r\right)=\left(z_r\right)·\left(F_r\right)=-1+i.$$

Indeed, the fact that $\left(x_r\right)·\left(F_r\right)=\left(y_r\right)·\left(F_r\right)=\left(z_r\right)·\left(F_r\right)$ would hold for any other Fibonacci sequences $\left(F_r\right)$ of order 3.

The last example illustrates a major strength of our approach–each equivalency class represents the same quantity under a given Fibonacci sequence. If one can find a legitimate Zeckendorf representation in an equivalency class, then the element represented by that class has a Zeckendorf decomposition. We finish this section with a powerful corollary to Proposition 2 and another example. The next result characterizes all elements that are Zeckendorf in a Fibonacci sequence $\left(F_r\right)$ of order k.

Corollary 1.

Let $\left(F_r\right)$ be a Fibonacci sequence of order k. An element m is Zeckendorf in $\left(F_r\right)$ if and only if m can be written as a finite sum (with multiplicities) of elements from $\left(F_r\right)$.

Proof. 

An element m is a finite sum of elements from $\left(F_r\right)$ if it is Zeckendorf in $\left(F_r\right)$. The converse of this statement follows from Proposition 2.    □

Example 3.

Consider the primitive Fibonacci sequence of order 2:

$$\begin{array}{ccccccccc}\hfill \dots ,& \hfill {\phi }^{-3},& \hfill {\phi }^{-2},& \hfill {\phi }^{-1},& \hfill 1,& \hfill \phi ,& \hfill {\phi }^2,& \hfill {\phi }^3,& \hfill \dots \end{array}$$

where $\phi =\frac{1+\sqrt{5}}{2}$ is the golden ratio. The elements that are Zeckendorf in this sequence are precisely positive elements in the ring $\mathbb{Z}\left[\phi \right]$, and this numeration system is known as the golden ratio base.

4. Zeckendorf’s Theorem for Free $\mathbb{Z}$-Modules

Intuitively, if an element m is Zeckendorf in a Fibonacci sequence $\left(F_r\right)$ of order k, then it is an integer combination of the initial terms (or, in fact, any k terms) of $\left(F_r\right)$. The integer span of these forms a module, so it is natural to attempt to represent every element of a module using sequence elements. The Section 4.1 below deals with doubly infinite Fibonacci sequences using tools developed in the previous section. The result is then specialized to one-way Fibonacci sequences in Section 4.2. This paves the way for the Zeckendorf decomposition and Fibonacci coding for modules.

4.1. Two-Sided Sequences

Corollary 1 lays a strong foundation for our work. While it characterizes elements that are Zeckendorf in a sequence, it gives insufficient information on the algebraic structure of the set of all elements that have a legitimate representation. The following theorem now reverses the process. It gives a sufficient and necessary condition for every element of a free $\mathbb{Z}$-module M to be Zeckendorf in a Fibonacci sequence $\left(F_r\right)$.

Theorem 1.

Let M be a free $\mathbb{Z}$-module of rank l and ${\left(F_r\right)}_{r\in \mathbb{Z}}=(\dots ,F_{-1},F_0,F_1,\dots )$ be a Fibonacci sequence of order k. Then, M is Zeckendorf in $\left(F_r\right)$ if and only if both of the following conditions are satisfied:

• $F_i,\dots ,F_{i+k-1}$ span M for all i;
• $l<k$.

Proof. 

We first remark that the integral span of $F_i,\dots ,F_{i+k-1}$ is the same as the integral span of $F_{i+1},\dots ,F_{i+k}$ since $F_i+\cdots +F_{i+k-1}=F_{i+k}$. Thus, $F_i,\dots ,F_{i+k-1}$ span M for alli if and only if $F_i,\dots ,F_{i+k-1}$ span M for anyi.

It is easy to see that the first condition is necessary. Since the elements of ${\left(F_r\right)}_{r\in \mathbb{Z}}$ are integer combinations of $F_i,\dots ,F_{i+k-1}$, so must be any sums of the elements from this sequence. It follows that $F_i,\dots ,F_{i+k-1}$ span M. This readily implies $l\le k$. We will now show that l cannot be equal to k, thus establishing the necessity of the second condition.

Suppose that $l=k$, and let m be any nonzero element of M. Since both m and $-m$ are Zeckendorf in $\left(F_r\right)$, we have:

$$m=\left(x_r\right)·\left(F_r\right)\mathrm{and}-m=\left(y_r\right)·\left(F_r\right)$$

for some sequences $\left(x_r\right),\left(y_r\right)$ of 0 and 1 with no k consecutive 1’s. Hence, $0=(x_r+y_r)·\left(F_r\right)$. By Proposition 1, $(x_r+y_r)$ is k-equivalent to a sequence that is positive at some k consecutive terms and zero elsewhere. Thus, we have:

$$0=(x_r+y_r)·\left(F_r\right)=\left(z_r\right)·\left(F_r\right)=z_i{F}_i+z_{i+1}{F}_{i+1}+\cdots +z_{i+k-1}{F}_{i+k-1}$$

for some i, in which $z_i,z_{i+1},\dots ,z_{i+k-1}>0$. This, however, means that $F_i,F_{i+1},\dots ,F_{i+k-1}$ are integrally dependent, and so they cannot span a module of rank $l=k$.

We are left to show that the two conditions are sufficient. Since $F_0,\dots ,F_{k-1}$ spans M and $l+1\le k$, $F_1,\dots ,F_{k-1}$ must be integrally dependent. That is, we may write:

$$0=x_0{F}_0+\cdots +x_{k-1}{F}_{k-1}$$

where $x_0,\dots ,x_{k-1}$ are not all zeros. In other words, we have:

$$0=\left(x_r\right)·\left(F_1\right)$$

where $\left(x_r\right)$ is zero everywhere except for some k consecutive terms. We apply Proposition 1 and obtain a sequence $\left(y_r\right)$ that is k-equivalent to $\left(x_r\right)$ and contains k consecutive terms of the same sign and zero elsewhere. Note that $\left(y_r\right)$ cannot be zero everywhere since that would imply that $x_0=\cdots =x_{k-1}=0$.

Suppose now that $\left(y_r\right)$ is nonzero at the terms $y_i,\dots ,y_{i+k-1}$. This means:

$$0=y_i{F}_i+\cdots +y_{i+k-1}{F}_{i+k-1}$$

where either $y_i,\dots ,y_{i+k-1}>0$ or $y_i,\dots ,y_{i+k-1}<0$. Since $F_i,\dots ,F_{i+k-1}$ spans M, we can write any element $m\in M$ as:

$$m=z_i{F}_i+\cdots +z_{i+k-1}{F}_{i+k-1}$$

where $z_i,\dots ,z_{i+k-1}$ are integers. Now, we have:

$$m=m+0·N=(z_i+y_{i}N)F_i+\cdots +(z_{i+k-1}+y_{i+k-1}N)F_{i+k-1}$$

for all integers N. For a sufficiently large (and possibly negative) N, the terms $z_i+y_{i}N,\dots ,z_{i+k-1}+y_{i+k-1}N$ will all be positive, and it follows from Corollary 1 that m is Zeckendorf in $\left(F_r\right)$. This completes the proof of the theorem.    □

Corollary 2.

Let ${\left(F_r\right)}_{r\in \mathbb{Z}}=(\dots ,F_{-1},F_0,F_1,\dots )$ be a Fibonacci sequence of order k. If $F_1,\dots ,F_k$ are integrally dependent, then every element in the integral span of $F_1,\dots ,F_k$ is Zeckendorf in $\left(F_r\right)$.

In view of Theorem 1, every integer has a (classical) Zeckendorf representation since $\mathbb{Z}$ is a module over itself with rank 1, and the negaFibonacci sequence is of order 2 with $F_0=0$ and $F_1=1$. In fact, the same result would hold as long as $F_0$ and $F_1$ are relatively prime (and hence span $\mathbb{Z}$ integrally). This is technically the case for the Lucas sequence where $L_0=2$ and $L_1=1$. Next, we give an example for the case of Gaussian integers.

Example 4.

Consider a Fibonacci sequence:

$$\begin{array}{cccccccc}\hfill \dots ,& \hfill {(-2-3i)}_{-6},& \hfill {(-1+2i)}_{-5},& \hfill {\left(2\right)}_{-4},& \hfill {(-1-i)}_{-3},& \hfill {\left(i\right)}_{-2},& \hfill {\left(1\right)}_{-1},& \\ & \hfill {\left(0\right)}_0,& \hfill {(1+i)}_1,& \hfill {(2+i)}_2,& \hfill {(3+2i)}_3,& \hfill {(6+4i)}_4,& \hfill {(11+7i)}_5,& \hfill \dots \end{array}$$

of order 3 from Example 1. It follows from Theorem 1 that every Gaussian integer can be written as a sum of elements from this sequence with no 3 consecutive terms. For instance:

$$\begin{array}{cccc}\hfill -2& ={(-2-3i)}_{-6}+{(-1+2i)}_{-5}+{\left(i\right)}_{-2}+{\left(1\right)}_{-1}\hfill & \hfill -2i& ={(-2-3i)}_{-6}+{\left(2\right)}_{-4}+{\left(i\right)}_{-2}\hfill \\ \hfill -1& ={(-1-i)}_{-3}+{\left(i\right)}_{-2}\hfill & \hfill -i& ={(-1-i)}_{-3}+{\left(1\right)}_{-1}\hfill \\ \hfill 2& ={\left(2\right)}_{-4}\hfill & \hfill 2i& ={(-1+2i)}_{-5}+{\left(1\right)}_{-1}\hfill \\ \hfill 3& ={\left(2\right)}_{-4}+{\left(1\right)}_{-1}\hfill & \hfill 3i& ={(-1+2i)}_{-5}+{\left(i\right)}_{-2}+{\left(1\right)}_{-1}\hfill \\ \hfill 1+2i& ={(-1+2i)}_{-5}+{\left(2\right)}_{-4}\hfill & \hfill 1-2i& ={(-2-3i)}_{-6}+{\left(i\right)}_{-2}+{\left(1\right)}_{-1}\hfill \\ \hfill -2+i& ={(-1+2i)}_{-5}+{(-1-i)}_{-3}\hfill & \hfill -2-i& ={(-2-3i)}_{-6}+{(-1+2i)}_{-5}\hfill \\ \hfill & \hfill & & \phantom{=}+{\left(1\right)}_{-1}.\hfill \end{array}$$

One may observe that ${\left(i\right)}_{-2}+{\left(1\right)}_{-1}={(1+i)}_1$, and so the Zeckendorf representation for a Gaussian integer in this sequence is not unique. Nonetheless, we will see in the next subsection how certain adjustments can make unique representations possible.

On the contrary, no Fibonacci sequence of order 2 can generate all Gaussian integers. For example, $-1-i$ cannot be written as a sum of elements from the sequence:

$$\begin{array}{ccccccccc}\hfill \dots ,& \hfill -21+13i,& \hfill 13-8i,& \hfill -8+5i,& \hfill 5-3i,& \hfill -3+2i,& \hfill 2-i,& \hfill -1+i,& \\ & \hfill 1,& \hfill i,& \hfill 1+i,& \hfill 1+2i,& \hfill 2+3i,& \hfill 3+5i,& \hfill 5+8i,& \hfill \dots .\end{array}$$

Note that Corollary 2 does not apply here since 1 and i are not integrally dependent. However, it follows from Corollary 1 that every element of the form $a+bi$, $a,b\in {\mathbb{Z}}^{+}$, is Zeckendorf in this sequence.

4.2. One-Sided Sequences and Unique Representation

For dense code, we need a one-to-one mapping. However, we see in Example 4 that a two-sided sequence do not provide such luxury. Note that this is observed in the classical Fibonacci sequence as well. It is only when the negaFibonacci sequence is extracted from the two-sided infinite sequence:

$$\dots ,34,-21,13,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,13,21,34,\dots$$

that every integer has a unique Zeckendorf representation. In this subsection, we establish analogous results for Fibonacci sequences of higher order. The key ingredient of this development is Corollary 3, which states that binary sequences with no k consecutive 1’s cannot be k-equivalent.

Lemma 1.

Let a be an integer, and let ${\left({\lambda }_k^r\right)}_{r\in \mathbb{Z}}$ be the primitive Fibonacci sequence of order k. Then:

$$\sum _{\begin{array}{c}r<a\\ k\nmid a-r\end{array}}{\lambda }_k^r={\lambda }_k^a.$$

Proof. 

We have:

$$\begin{array}{cc}\hfill \sum _{\begin{array}{c}r<a\\ k\nmid a-r\end{array}}{\lambda }_k^r& =\sum _{r<a}{\lambda }_k^r-\sum _{\begin{array}{c}r<a\\ k\mid a-r\end{array}}{\lambda }_k^r\hfill \\ \hfill & =\frac{{\lambda }_k^a}{{\lambda }_k-1}-\frac{{\lambda }_k^a}{{\lambda }_k^k-1}\hfill \\ \hfill & ={\lambda }_k^a\left(\frac{({\lambda }_k^{k-1}+{\lambda }_k^{k-2}+\cdots +1)-1}{{\lambda }_k^k-1}\right)\hfill \\ \hfill & ={\lambda }_k^a\left(\frac{{\lambda }_k^k-1}{{\lambda }_k^k-1}\right)\hfill \\ \hfill & ={\lambda }_k^a.\hfill \end{array}$$

   □

Corollary 3.

Let $\left(x_r\right)$ and $\left(y_r\right)$ be doubly infinite binary sequences with no k consecutive 1’s that are 0 almost everywhere:

• If $\left(x_r\right)$≻${}_k\left(y_r\right)$, then $\left(x_r\right)·\left({\lambda }_k^r\right)>\left(y_r\right)·\left({\lambda }_k^r\right)$.
• If $\left(x_r\right)$∼${}_k\left(y_r\right)$, then $\left(x_r\right)=\left(y_r\right)$.

Proof. 

Suppose that $\left(x_r\right){\succ }_k\left(y_r\right)$, and let a be the largest index where $\left(x_r\right)$ and $\left(y_r\right)$ are not equal. It follows that $\left(x_a\right)=1$, $\left(y_a\right)=0$, and

$$\begin{array}{cc}\hfill \left(x_r\right)·\left({\lambda }_k^r\right)& \ge {\lambda }_k^a+\sum _{r>a}{x}_r{\lambda }_k^r\hfill \\ \hfill & =\sum _{\begin{array}{c}r<a\\ k\nmid a-r\end{array}}{\lambda }_k^r+\sum _{r>a}{x}_r{\lambda }_k^r\hfill \\ \hfill & >\sum _{r\le a}{y}_r{\lambda }_k^r+\sum _{r>a}{y}_r{\lambda }_k^r=\left(y_r\right)·\left({\lambda }_k^r\right).\hfill \end{array}$$

Now, if $\left(x_r\right)\ne \left(y_r\right)$, then we may assume without loss of generality that $\left(x_r\right){\succ }_k\left(y_r\right)$. This means $\left(x_r\right)·\left({\lambda }_k^r\right)>\left(y_r\right)·\left({\lambda }_k^r\right)$, and so $\left(x_r\right){\nsim }_k\left(y_r\right)$. This readily establishes part 2.    □

Typically, $\left(x_r\right)$∼${}_k\left(y_r\right)$ means that $\left(x_r\right)·\left(F_r\right)=\left(y_r\right)·\left(F_r\right)$, and so $\left(x_r\right)$ and $\left(y_r\right)$ are two representations of the same element. Corollary 3 now allows us to identify the Fibonacci sequences (or parts of them) that permit unique Zeckendorf representation: If a sequence $\left(F_r\right)$ has the property that $\left(x_r\right)·\left(F_r\right)=\left(y_r\right)·\left(F_r\right)$ implies $\left(x_r\right)$∼${}_k\left(y_r\right)$, then any element that is Zeckendorf in $\left(F_r\right)$ will have a unique representation. Since we are interested in generating every element in a $\mathbb{Z}$-module, we look into generalizing negaFibonacci sequence, which is technically a one-sided Fibonacci sequence to the left whose first excluded term is 0. It turns out that this observation generalizes well to modules.

Theorem 2.

Let $k\ge 2$ be an integer and M be a free $\mathbb{Z}$-module of rank $k-1$. Let ${\left(F_r\right)}_{r\in \mathbb{Z}}=(\dots ,F_{-1},F_0,F_1,\dots )$ be a Fibonacci sequence of order k, where $F_0=0$ and $F_{-k+1},\dots ,F_{-1}$ span M. Then, every element $m\in M$ can be uniquely written as a finite sum of elements from the one-way sequence:

$$\dots ,F_{-3},F_{-2},F_{-1}$$

with no k consecutive terms.

Proof. 

We first prove the existence. Let $m\in M$ and write:

$$m=x_{-k+1}{F}_{-k+1}+\cdots +x_{-2}{F}_{-2}+x_{-1}{F}_{-1}$$

where $x_{-k+1},\dots ,x_{-2},x_{-1}$ are integers. We extend $x_{-k+1},\dots ,x_{-2},x_{-1}$ to a sequence ${\left(x_r\right)}_{r\in \mathbb{Z}}$ that is zero everywhere except $r=-k+1,\dots ,-2,-1$. Now, consider all sequences of integers that are k-equivalent to ${\left(x_r\right)}_{r\in \mathbb{Z}}$ such that the terms with positive indices are zero, and the terms with negative indices are non-negative. Such a sequence exists since one may apply Operation 1 from Definition 3 to $\left(x_r\right)$ at $n=0$ for $\max \left\{\right|x_{-k+1}|,\dots ,|x_{-2}|,|x_{-1}\left|\right\}$ times. We denote by ${\left(y_r\right)}_{r\in \mathbb{Z}}$ the sequence that has the aforementioned properties with highest lexicographical order. We claim that $\left(y_r\right)$ gives a Zeckendorf representation for m in $\dots ,F_{-3},F_{-2},F_{-1}$.

We first note that $y_r=0$ for $r\in {\mathbb{Z}}^{+}$ and $F_0=0$, and so $\left(y_r\right)·\left(F_r\right)={\sum }_{r\in {\mathbb{Z}}^{-}}{y}_r{F}_r$. If $y_s\ge 2$ for some $s\in {\mathbb{Z}}^{-}$, then we perform Operation 1 at $n=s$ and Operation 2 at $n=s+1$ to obtain a sequence with higher lexicographical order than $\left(y_r\right)$. If $y_{s-k+1}=\cdots =y_{s-1}=y_s=1$ for some $s\in {\mathbb{Z}}^{-}$, then performing Operation 2 at $n=s$ results in a sequence with higher lexicographical order. Thus, $\left(y_r\right)$ is binary with no k consecutive 1’s, and ${\sum }_{r\in {\mathbb{Z}}^{-}}{y}_r{F}_r$ is a Zeckendorf representation for m in $\dots ,F_{-3},F_{-2},F_{-1}$.

Suppose now for the sake of contradiction that there exists an element $m\in M$ that has two representations as a finite sum of elements from the sequence $\dots ,F_{-3},F_{-2},F_{-1}$ with no k consecutive terms. That is, we have $m=\left(x_r\right)·\left(F_r\right)=\left(y_r\right)·\left(F_r\right)$ where $\left(x_r\right)\ne \left(y_r\right)$ are doubly infinite binary sequences which are zero for $r\ge 0$. Now, we keep applying either Operation 1 or 2 to eliminate the leftmost nonzero term of $\left(x_r\right)$ and $\left(y_r\right)$ and obtain sequences $\left(x_r^{\prime }\right)$ and $\left(y_r^{\prime }\right)$, which are zero everywhere except for $r=-k+1,\dots ,-2,-1,0$. This means:

$$\begin{array}{cc}\hfill \left(x_r^{\prime }\right)·\left(F_r\right)& =x_{-k+1}^{\prime }{F}_{-k+1}+\cdots +x_{-2}^{\prime }{F}_{-2}+x_{-1}^{\prime }{F}_{-1}+x_0^{\prime }{F}_0\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill \left(y_r^{\prime }\right)·\left(F_r\right)& =y_{-k+1}^{\prime }{F}_{-k+1}+\cdots +y_{-2}^{\prime }{F}_{-2}+y_{-1}^{\prime }{F}_{-1}+y_0^{\prime }{F}_0.\hfill \end{array}$$

are both equal to m. Since $F_{-k+1},\dots ,F_{-1}$ span M of rank $k-1$, we must have $x_r^{\prime }=y_r^{\prime }$ for $r=-k+1,\dots ,-2,-1$. If $x_0^{\prime }=y_0^{\prime }$, then $\left(x_r\right){\sim }_k\left(x_r^{\prime }\right)=\left(y_r^{\prime }\right){\sim }_k\left(y_r\right)$, and so $\left(x_r\right)$ and $\left(y_r\right)$ must be the same from Corollary 3. Otherwise, we assume without loss of generality that $x_0^{\prime }>y_0^{\prime }$. We now have:

$$\begin{array}{cc}\hfill \left(x_r\right)·\left({\lambda }_k^r\right)-\left(y_r\right)·\left({\lambda }_k^r\right)& =\left(x_r^{\prime }\right)·\left({\lambda }_k^r\right)-\left(y_r^{\prime }\right)·\left({\lambda }_k^r\right)\hfill \\ \hfill & =(x_0^{\prime }-y_0^{\prime }){\lambda }_k^0\hfill \\ \hfill & \ge 1.\hfill \end{array}$$

Since $\left(y_r\right)$ is binary, it follows that $\left(x_r\right)·\left({\lambda }_k^r\right)\ge 1$. However, we see the following from Lemma 1:

$$\left(x_r\right)·\left({\lambda }_k^r\right)<\sum _{\begin{array}{c}r<0\\ k\nmid -r\end{array}}{\lambda }_k^r={\lambda }_k^0=1,$$

which is a contradiction. This completes the proof of the theorem.    □

Obviously, the generalized Zeckendorf theorem over the negaFibonacci sequence [19] serves as an instance of Theorem 2. We give another example using Gaussian integers.

Example 5.

Consider the following Fibonacci sequence:

$$\begin{array}{cccccccc}\hfill \dots ,& \hfill {(-2-3i)}_{-6},& \hfill {(-1+2i)}_{-5},& \hfill {\left(2\right)}_{-4},& \hfill {(-1-i)}_{-3},& \hfill {\left(i\right)}_{-2},& \hfill {\left(1\right)}_{-1},& \\ & \hfill {\left(0\right)}_0,& \hfill {(1+i)}_1,& \hfill {(2+i)}_2,& \hfill {(3+2i)}_3,& \hfill {(6+4i)}_4,& \hfill {(11+7i)}_5,& \hfill \dots \end{array}$$

of order 3 from Examples 1 and 4. One can see that every representation given in Example 4 only involve terms from the sequence:

$$\begin{array}{ccccccc}\hfill \dots ,& \hfill {(-2-3i)}_{-6},& \hfill {(-1+2i)}_{-5},& \hfill {\left(2\right)}_{-4},& \hfill {(-1-i)}_{-3},& \hfill {\left(i\right)}_{-2},& \hfill {\left(1\right)}_{-1}.\end{array}$$

In fact, every Gaussian integer can be uniquely written as a sum of elements from this sequence with no three consecutive terms. This property will be exploited when we develop multidimensional Fibonacci coding for Gaussian integers in Example 6 in the next section.

5. Multidimensional Fibonacci Coding

The classical Fibonacci code of order 2 is quite simple. By virtue of Zeckendorf’s theorem, integers are written in base Fibonacci and encoded as a string of 0’s and 1’s in reverse order together with a suffix 1. For example, 11 is encoded as 001011 since it is the sum of the third and the fifth Fibonacci numbers, which are 3 and 8, respectively. The widely-accepted Fibonacci code of higher order is not so straightforward. Note that simply adding consecutive runs of 1 no longer makes the code uniquely decodable [7]. The integers are instead mapped to a lexicographically ordered string of 0’s and 1’s with a single k-consecutive 1 at the end. This encoding, though artificial, provides dense codes.

We see from Theorem 2 that it is possible to write any element of a module as a sum of entries from a sequence using no k consecutive terms. This suggests a multidimensional Fibonacci coding for modules with the use of k consecutive 1’s as a separator. This intuition formalizes into Algorithm 1. Here, we denote k consecutive 1’s, $\underset{k}{\underbrace{11\dots 1}}$, by $1_k$.

Algorithm 1 Multidimensional Fibonacci Encoding

Input: A Fibonacci sequence $\dots ,F_{-3},F_{-2},F_{-1}$ of order k where $F_{-k}+\cdots +F_{-1}=0$ and $F_{-k+1},\dots ,F_{-1}$ span a free $\mathbb{Z}$-module M of rank $k-1$, and an element $m\in M$.

Output: multidimensional Fibonacci code for m.

1: If $m=0$, output $1_k$. END. 2: Find the module coordinate of m under the basis $F_{-k+1},\dots ,F_{-1}$. We will have $$m=x_{-k+1}{F}_{-k+1}+\cdots +x_{-2}{F}_{-2}+x_{-1}{F}_{-1}.$$ (2) Set $x_0=0$ and $x_r=0$ for $r\le -k$. 3: If $\check{x}=min\{x_{-k+1},\dots ,x_{-2},x_{-1}\}<0$, subtract $\check{x}$ from $x_{-k},x_{-k+1},\dots ,x_{-2},x_{-1}$. 4: Find the largest index $s<0$ such that $x_{s-k+1},\dots ,x_s\ge 1$. If there is none, go to Step 5. Otherwise, subtract 1 from $x_{s-k+1},\dots ,x_s$, add 1 to $x_{s+1}$, and repeat this step. 5: Find the largest index $s<0$ such that $x_s\ge 2$. If there is none, go to Step 6. Otherwise, subtract 2 from $x_s$, add 1 to $x_{s-k}$ and $x_{s+1}$, and go to Step 4. 6: Find the smallest index $s<0$ such that $x_s=1$. Output $x_{-1}{x}_{-2}{x}_{-3}\dots x_{s+2}{x}_{s+1}{01}_k$. END.

Note that the coefficients are encoded in reverse order, and Step 2 may depend on the initial condition $F_{-k},\dots ,F_{-1}$ of the Fibonacci sequence of order k. If $F_{-k+1},\dots ,F_{-1}$ is chosen to be the standard basis of the module, then $x_{-k+1},\dots ,x_{-2},x_{-1}$ will simply be the coordinate of m in the usually sense. Generally, one may also find $x_{-k+1},\dots ,x_{-2},x_{-1}$ by solving (2) as a system of linear equations. In the final step, we replace the last 1 with ${01}_k$ to make our code uniquely decodable. This frees us from having to keep the lookup table but makes the code suboptimal in terms of density.

In addition, note that the algorithm simply mimics the arguments given in the proof of Theorem 2. This guarantees that the algorithm terminates since the operations performed in Step 4 and 5 increase the lexicographical order of the sequence. At every step, the value ${\sum }_{r\in {\mathbb{Z}}^{-}}{x}_r{F}_r$ remains unchanged. This fact makes the decoding, which is outlined as Algorithm 2, straightforward.

Algorithm 2 Multidimensional Fibonacci Decoding

Input: A Fibonacci sequence $\dots ,F_{-3},F_{-2},F_{-1}$ of order k, and a binary string $x_{-1}{x}_{-2}{x}_{-3}\dots x_{-s+1}{x}_{-s}{1}_k$.

Output: An element m. 1: If $x_{-1}{x}_{-2}{x}_{-3}\dots x_{-s+1}{x}_{-s}$ is empty, output 0. END. 2: Output $x_{-1}{F}_{-1}+x_{-2}{F}_{-2}+\cdots +x_{-s+1}{F}_{-s+1}+F_{-s}$. END.

To illustrate, we consider once again the Gaussian Fibonacci sequence of order 3 used through Examples 1, 4 and 5.

Example 6.

Consider the following Fibonacci sequence:

$$\dots ,{(-4+4i)}_{-8},{(5+i)}_{-7},{(-2-3i)}_{-6},{(-1+2i)}_{-5},{\left(2\right)}_{-4},{(-1-i)}_{-3},{\left(i\right)}_{-2},{\left(1\right)}_{-1}$$

of order 3, and let $m=-2+3i$. To encode, we initialize $x_{-2}=3$, $x_{-1}=-2$ and obtain $x_{-3}=2$, $x_{-2}=5$, $x_{-1}=0$ after Step 3. We shorthand this sequence as $2_{-3},5_{-2},0_{-1}$. The iterations of Step 4 and 5 now yield:

$$\begin{array}{cc}\hfill 2_{-3},5_{-2},0_{-1}& \to 1_{-5},0_{-4},2_{-3},3_{-2},1_{-1}\hfill \\ \hfill & \to 1_{-5},0_{-4},1_{-3},2_{-2},0_{-1}\hfill \\ \hfill & \to 2_{-5},0_{-4},1_{-3},0_{-2},1_{-1}\hfill \\ \hfill & \to 1_{-8},0_{-7},0_{-6},0_{-5},1_{-4},1_{-3},0_{-2},1_{-1}.\hfill \end{array}$$

Thus, $m=-2+3i$ is encoded as 10110000111. This string can then be decoded as $F_{-1}+F_{-3}+F_{-4}+F_{-8}={\left(1\right)}_{-1}+{(-1-i)}_{-3}+2_{-4}+{(-4+4i)}_{-8}=-2+3i$. The length of the encoded Gaussian integer $a+bi$ where $-1000\le a,b\le 1000$ under this initial condition is illustrated in Figure 1. Here, the region of the same color represents the Gaussian integer of the same encoded length using the basis given in this example.

Clearly, one may replace i in Example 6 with any other quadratic integer and obtain a multidimensional Fibonacci coding for the corresponding ring of quadratic integers. Next, we give an example of multidimensional Fibonacci coding for a lattice.

Example 7.

Consider the lattice $E_8$ given by:

$$E_8=\left\{\mathrm{x}\in {\mathbb{Z}}^8\cup {(\mathbb{Z}+\frac{1}{2})}^8\mid \sum x_i\equiv 0(mod2)\right\}.$$

This lattice provides optimal sphere packing and kissing number in eight dimensions and has many other interesting properties [36]. We set the basis for $E_8$ as:

$$\begin{array}{cccc}\hfill {\mathbf{v}}_1& =(2,0,0,0,0,0,0,0)\hfill & \hfill {\mathbf{v}}_2& =(-1,1,0,0,0,0,0,0)\hfill \\ \hfill {\mathbf{v}}_3& =(0,-1,1,0,0,0,0,0)\hfill & \hfill {\mathbf{v}}_4& =(0,0,-1,1,0,0,0,0)\hfill \\ \hfill {\mathbf{v}}_5& =(0,0,0,-1,1,0,0,0)\hfill & \hfill {\mathbf{v}}_6& =(0,0,0,0,-1,1,0,0)\hfill \\ \hfill {\mathbf{v}}_7& =(0,0,0,0,0,-1,1,0)\hfill & \hfill {\mathbf{v}}_8& =(\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2})\hfill \end{array}$$

and consider a Fibonacci sequence of order 9 given by:

$$\dots ,2{\mathbf{v}}_2-{\mathbf{v}}_1,2{\mathbf{v}}_1,-{\mathbf{v}}_1-{\mathbf{v}}_2-{\mathbf{v}}_3-{\mathbf{v}}_4-{\mathbf{v}}_5-{\mathbf{v}}_6-{\mathbf{v}}_7-{\mathbf{v}}_8,{\mathbf{v}}_8,{\mathbf{v}}_7,{\mathbf{v}}_6,{\mathbf{v}}_5,{\mathbf{v}}_4,{\mathbf{v}}_3,{\mathbf{v}}_2,{\mathbf{v}}_1.$$

It follows from Theorem 2 that every element of $E_8$ can be written as a sum of elements from this sequence with no nine consecutive terms. For example, let $\mathbf{m}=(\frac{1}{2},1\frac{1}{2},1\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2})\in E_8$. Then, $\mathbf{m}={\mathbf{v}}_1+2{\mathbf{v}}_2+{\mathbf{v}}_3+{\mathbf{v}}_8=(2{\mathbf{v}}_2-{\mathbf{v}}_1)+\left(2{\mathbf{v}}_1\right)+\left({\mathbf{v}}_8\right)+\left({\mathbf{v}}_3\right)$ and can be encoded as 00100001010111111111.

6. Compression Efficiency and Simulation Results

In this section, we give an overview for the compression efficiency of the proposed scheme, both theoretically and numerically. We refer interested readers to [1] for a comprehensive survey on the topic of data compression.

Let ${\lambda }_k$ be the dominating root of $x^k-x^{k-1}-x^{k-2}-\cdots -x-1=0$, i.e., the $k^{\mathrm{th}}$-order golden ratio. It takes approximately ${log}_{{\lambda }_k}\left(A\right)+k-1$ bits to encode a single integer A using the Fibonacci code of order k. Unfortunately, due to the erratic nature of the higher-order number system, a simple formula cannot be made to approximate the number of bits needed to encode the string $A_1,A_2,\dots ,A_k$ using our proposed algorithm (see also Figure 1). Here, we shall attempt to give a very crude estimate. Theorem 2 guarantees a one-to-one correspondence between modules element and sequences of 0’s and 1’s with no k consecutive 1’s. Consider a k-dimensional hypercube with sides parallel to the axes, and the origin and $(A_1,A_2,\dots ,A_k)$ are opposite vertices. It takes at least ${log}_{{\lambda }_k}(A_1{A}_2\cdots A_k)$ bits to assign each integer point in this hypercube a unique binary strings under multidimensional Fibonacci coding. Thus, if $A_1,A_2,\dots ,A_k$ are sufficiently large, one may estimate the number of bits needed to encode them altogether as ${log}_{{\lambda }_k}(A_1{A}_2\cdots A_k)+k$. If A is the geometric mean of $A_1,A_2,\dots ,A_k$, then the per-element average of the number of bits used to write each of the $A_i$’s is ${log}_{{\lambda }_k}\left(A\right)+1$. This can be interpreted as the burden of the k-bit suffix being shared across the string entries.

While there exist several modern compression techniques [3,4,5,37], each with different strengths and trade-offs, we compare a multidimensional Fibonacci code with the classical one, using the well-established Huffman code as a benchmark.

Figure 2 plots the average length of the codewords as a function of the number of elements in the source data on a logarithmic scale for Huffman, classical Fibonacci (Fib2, Fib3, Fib4), and multidimensional Fibonacci (MultiFib3, MultiFib4) coding. Next, we define the normalized compression ratio as the average codeword length divided by the entropy of the source data and present the comparison in this factor in Figure 3. Here, we see that multidimensional Fibonacci codes outperform their classical counterpart across all orders when n is sufficiently large (≈100). This is not surprising, since the burden of the suffix is shared across several alphabets in the proposed scheme.

Next, Figure 4 and Figure 5 consider the case when the distribution of the source data follows Zipf’s law, which is known to typically govern the distribution of letters and words in a natural language [38]. Here, it turns out that the performance of multidimensional Fibonacci codes are slightly behind their classical counterparts. This phenomenon could probably be explained by the fact that multidimensional encoder receives a hold-back when “frequent” and “infrequent” alphabets are encoded together in the same group. We give a quick example to illustrate this circumstamce.

Example 8.

Suppose that three strings 2 2, 10 10, and 10 2 are to be encoded with the classical and multidimensional Fibonacci coding of order 3 (Fib3 and MultiFib3, respectively), where Fib3 encodes each number separately and MultiFib3 encodes the two numbers together. The results are given in

Table 1. Average codeword lengths under Zipf distribution.

String	Fib3		MultiFib3
	Codeword	Length	Codeword	Length
2 2	01110111	8	10010111	8
10 10	10001111000111	14	0101000100111	13
10 2	01111000111	10	0000010000111	13

.

Here, MultiFib3 performs better when the input integers are equally large but gains no reduction in codeword length when one of the inputs is significantly reduced.

To this end, multidimensional Fibonacci coding takes us to a strange paradox where encoding a constituent of data as whole reduces the use of delimiter, thus improving upon the compression rate. However, as the encoding is performed collectively rather than individually, the system suffers a disadvantage when numbers that are considerably different in magnitude are encoded together. This could be particularly troublesome in a skewed distribution such as Zipf, where an input with high frequency is not mapped to a short codeword it deserves and may not bring much benefit to the block it belongs to. Finally, we remark here that while Huffman code outperform Fibonacci code numerically, it works well only when there are finite alphabets and the distribution is known a priori. Fibonacci code is also advantageous in that it provides robustness against errors and works naturally on the set of integers. In this sense, the multidimensional Fibonacci code could be of particular interest when integers of unknown sign and magnitude are to be encoded.

7. Conclusions

In this paper, we generalize Zeckendorf’s theorem to modules. The notion of equivalent sequences allows us to identify elements that can be represented as a sum of entries from a Fibonacci sequence of order k. This results in the necessary and sufficient conditions for a Fibonacci sequence of higher order to generate a module. In addition, under certain circumstances the representation is unique, allowing us to establish multidimensional Fibonacci coding for modules. Future work involves identifying other conditions to which the representation remains unique. Under such environments, one can view the Zeckendorf representation as a number system and develop a generalized Zeckendorf arithmetic. It would also be interesting to study the proposed coding algorithm from the perspective of data compression and computational complexity.