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$.


  • 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.


1 Answer 1


Here is a partial (negative answer) to your first question:

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$

  • $\begingroup$ @ 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. $\endgroup$ Sep 27, 2020 at 17:08
  • $\begingroup$ @VincentGranville : Thank you for your comment. (The first letter of my first name, pronounced Yosef, is the upper case of i.) $\endgroup$ Sep 27, 2020 at 18:32
  • $\begingroup$ 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. $\endgroup$ Sep 27, 2020 at 19:26
  • $\begingroup$ When I'll write my article, there will be a reference (link) to your answer. $\endgroup$ Sep 27, 2020 at 20:10
  • $\begingroup$ @VincentGranville : I am glad this was of help. $\endgroup$ Sep 29, 2020 at 2:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .