0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\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$ – Vincent Granville Sep 27 '20 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$ – Iosif Pinelis Sep 27 '20 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$ – Vincent Granville Sep 27 '20 at 19:26
  • $\begingroup$ When I'll write my article, there will be a reference (link) to your answer. $\endgroup$ – Vincent Granville Sep 27 '20 at 20:10
  • $\begingroup$ @VincentGranville : I am glad this was of help. $\endgroup$ – Iosif Pinelis Sep 29 '20 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.