# Hybrid numeration system on $[0,1]^2$

Let $$X_0,X_1\in [0,1]$$ and $$b_1,b_2>0$$ be integers. We are going to create a numeration system for vectors $$(X_0,X_1)$$, the base being the vector $$(b_1,b_2)$$, as follows.

Recursively define $$X_k=\{b_2 X_{k-1} + b_1 X_{k-2}\}$$, for $$k>1$$. Here $$\{\cdot\}$$ represents the fractional part function and $$X_k\in [0,1]$$. Clearly, $$d_k=b_1 X_k + b_2 X_{k+1} - X_{k+2}$$ is an integer between $$0$$ and $$b_1+b_2-1$$. The sequence $$d_0, d_1, d_2,d_3,\cdots$$ represents, by definition, the digits of $$(X_0,X_1)$$ in base $$(b_1,b_2)$$. If $$b_1=0$$ then the digits are just the standard digits of $$X_1$$ in base $$b_2$$.

Questions:

• Can two different vectors $$(X_0,X_1)$$ and $$(X_0',X_1')$$ have the exact same digits in base $$(b_1,b_2)$$, assuming $$b_1,b_2>0$$?
• Can you reconstruct $$(X_0,X_1)$$ if you only know its digits in base $$(b_1,b_2)$$?

My guess is that the answer to the first question is yes. So all that suffices is to provide an example. This would lead to a negative answer to my second question.

However, if the answer to the first question is negative, there would be the following interesting consequences. Let $$b=b_1+b_2$$. To each $$(X_0,X_1)$$ corresponds a unique number $$f(X_0,X_1)\in[0,b]$$ defined by its expansion in base $$b$$ as follows:

$$f(X_0,X_1)=\sum_{k=0}^\infty \frac{d_k}{b^{k}}.$$

The two consequences would be:

• Since for the immense majority of couples $$(X_0,X_1)$$ the distribution of the digits $$d_k$$ is NOT uniform on the set $$\{0,1,2,\cdots,b-1\}$$ (see below why), the number $$f(X_0,X_1)$$ is not normal. Since the set of non-normal numbers has zero Lebesgue measure, we mapped $$[0,1]^2$$ onto a set of Lebesgue measure zero. The mapping is bijective.
• We created an order on $$[0,1]^2$$. It is defined as follows: $$(X_0,X_1) < (X_0',X_1')$$ if and only if $$f(X_0,X_1) < f(X_0',X_1')$$.

Some useful results

In order to prove or disprove my claims, I offer the following result. While at this stage I strongly believe that the formula below is correct, I did not technically prove it. This is just based on pattern recognition techniques and experimental math, yet I think the proof should be easy.

$$X_k = \{A(k) X_1\} \mbox{ with } A(0) =\frac{X_0}{X_1}, A(1) =1, \mbox{ and } A(k)= b_2 A(k-1) + b_1 A(k-2).$$

More about this in my former MO question, here. In addition, as previously discussed, the digits of $$(X_0, X_1)$$ are almost surely NOT uniformly distributed over $$\{0,1,\cdots b-1\}$$, unlike classic digits of (say) $$\log 2$$ in base $$b$$. Just to give you an example (again based on strong empirical evidence but not a proof) this is the standard distribution of the digits in base $$(b_1=3, b_2=3)$$:

• digit $$0$$ appears with frequency $$1/18$$
• digit $$1$$ appears with frequency $$3/18$$
• digit $$2$$ appears with frequency $$5/18$$
• digit $$3$$ appears with frequency $$5/18$$
• digit $$4$$ appears with frequency $$3/18$$
• digit $$5$$ appears with frequency $$1/18$$

Essentially these are the frequencies you would observe in that base if you picked up $$X_0,X_1$$ randomly.

Proposition 1: Two different vectors $$(X_0,X_1)$$ and $$(X_0',X_1')$$ cannot have the exact same digits $$d_0,d_1,\dots$$ in base $$(b_1,b_2)$$, assuming $$b_1,b_2>0$$ and $$b_1>b_2+1$$.

Proof: Suppose the contrary. Then for $$k=0,1,\dots$$ we have $$X_{k+2}=b_1 X_k+b_2 X_{k+1}-d_k$$, $$X'_{k+2}=b_1 X'_k+b_2 X'_{k+1}-d_k$$, and hence $$Z_{k+2}=b_1 Z_k+b_2 Z_{k+1},$$ where $$Z_k:=X'_k-X_k$$. So, for some real $$c_+,c_-$$ and all $$k=0,1,\dots$$ we have $$Z_k=c_+ u_+^k+c_- u_-^k,$$ where $$u_+:=\frac{b_2+\sqrt{b_2^2+4b_1}}2,\quad u_-:=\frac{b_2-\sqrt{b_2^2+4b_1}}2$$ are the roots $$u$$ of the equation $$u^2=b_1+b_2 u$$; see e.g. linear difference equations with distinct characteristic roots.

Note that $$u_+>b_2\ge1$$ and also $$u_1>|u_2|$$. So, if $$c_+\ne0$$, then $$|Z_k|\to\infty$$ (as $$k\to\infty$$), which contradicts the conditions $$Z_k=X'_k-X_k$$, $$0\le X_k<1$$, $$0\le X'_k<1$$. So, $$c_+=0$$.

Now, for $$b_2>0$$, the condition $$b_1>b_2+1$$ is equivalent to $$|u_-|>1$$, whence $$|Z_k|=|c_-|\,|u_-|^k\to\infty$$ if $$c_-\ne0$$, which again contradicts the conditions $$Z_k=X'_k-X_k$$, $$0\le X_k<1$$, $$0\le X'_k<1$$. So, $$c_-=0$$, so that $$Z_k=0$$ and $$X'_k=X_k$$ for all $$k$$. In particular, $$(X_0,X_1)=(X_0',X_1')$$. $$\Box$$

• @ Losif: thank you again for your great answer. I did not mention it, but you can generalize to higher dimensions. The case discussed here is 2D. You can also work with negative $b_1,b_2$ though it requires some adjustments. Sep 27, 2020 at 17:08
• @VincentGranville : Thank you for your comment. (The first letter of my first name, pronounced Yosef, is the upper case of i.) Sep 27, 2020 at 18:32
• Sorry Iosef for making the same mistake a second time. While this may not be a popular topic, your answer is very valuable and one of the most useful I received. The fact that the digit representation is unique (at least for some $b_1,b_2$) has many interesting consequences, both theoretical and in cryptography applications. Sep 27, 2020 at 19:26
• When I'll write my article, there will be a reference (link) to your answer. Sep 27, 2020 at 20:10
• @VincentGranville : I am glad this was of help. Sep 29, 2020 at 2:21