Title: Theory / Unimportant / CS / Fundamental / Automata / Number / rational base/ / Powers of rationals modulo 1 and rational base number systems
Tags: hasSeenConjDef récupéré fromAlgorithm fromMath hasNotNewEffectReturnsMeaning mathToSee oldAlgoNewName

Question: Assumption about \(p\) and \(q\) ?
Answer: \(p>q\ge 2\) coprime
Page: 1
Context: Rational base number system

Name: The lexicographic order
Definition: \((uav,ubw')\) with \(u,v,w\) finite words over \(A\) and \(a<b\in A\)
Page: 4
Section: 2.1
Variables: \((A,\le)\) a totally ordered alphabet
Context: \(A^*\)
Notation: [$]\sqsubsetneq[/$]
Definition2: \((u,uv)\) with \(u,v\) finite words over \(A\),
Conjdef: containing
DefType: The order

Name: The radix order
Definition: \(|u_1|<|u_2|\) or
Page: 4
Section: 2.1
Variables: \((A,\le)\) a totally ordered alphabet
Context: \(A^*\)
Notation: [$]\precneq[/$]
Definition2: \(|u_1|=|u_2|\), and \(u_i=va_iw_i\) with \(v,w_1,w_2\) finite words over \(A\) and \(a_1<a_2\in A\)
Conjdef: The order on pair of words \((u_1,u_2)\) with either

Smaller0: \(|u|=|v|\)
Greater0: \(u\preceq v\) iff \(u\sqsubseteq v\)
Page: 4
Section: 2.1
Variables: \((A,\le)\) a totally ordered alphabet
\(u,v\in A^*\)
Hide middle: yes

Name: The prefix of \(u\) of length \(n\)
Page: 5
Section: 2.1
Variables: \((A,\le)\) a totally ordered alphabet
\(u\in A^\infty\)
\(n\in\mathbb N\)
Notation: \(u_{[n]}\)
Definition2: iff
Definition3: \(u\sqsubseteq v\)

Definition: The set of functions \(\mathbb Z\to A\)
Page: 5
Section: 2.1
Variables: \((A,\le)\) a totally ordered alphabet
\(u\in A^\infty\)
\(n\in\mathbb N\)
Notation: \(A^{\mathbb N}\)

Name: A letter-to-letter transducer
Definition: An automaton over alphabet \(A\times B\)
Page: 5
Section: 2.1
Variables: \(A,B\) alphabets
Denoted by: \(\mathcal T\)

Name: The underlying input automaton of \(\mathcal T\)
Definition: The automaton on \(A\) with the component of \(B\) deleted
Page: 5
Section: 2.1
Variables: \(A,B\) alphabets,
\(\mathcal T\) a transducer

Name: A (co)-sequential transducer
Definition: A transducer whose underlying input automaton is (co)-deterministic
Page: 6
Section: 2.1
Variables: \(A,B\) alphabets,

Name: A system of representation
Definition: A bi-infinite increasing sequence \((u_i)_{i\in\mathbb Z}\in\mathbb R^{\ge0}\) with \(\sum_{n\in\mathbb N}u_{-n}<+\infty\)
Page: 6
Section: 2.1
Denoted by: \(U\)

Name: A representation in the system \(U\) of \(x\)
Definition: A sequence \(d_k\dots d_0.d_{-1}\dots \) with \(d_i\in D\) such that this sequence represents \(x\)
Page: 6
Section: 2.1
Variables: \(U=(u_i)_{i\in\mathbb Z}\in\mathbb R^{\ge0}\) a system of representation
Let \(D\subseteq\mathbb N\) finite
\(x\in\mathbb R^{\ge 0}\)

Name: The number represented by \(\mathbf d\)
Definition: \(\sum_{-\infty}^{i=k}d_iu_i\)
Page: 6
Section: 2.1
Variables: \(U=(u_i)_{i\in\mathbb Z}\in\mathbb R^{\ge0}\) a system of representation
Let \(D\subseteq\mathbb N\) finite
\(\mathbf d=d_k\dots d_0.d_{-1}\dots \) with \(d_i\in D\)
Notation: \(\pi(\mathbf d)\)

Name: A finite representation of a real
Definition: A representation \(d_k\dots d_0.d_{-1}\dots \) with finitely many non-zero digits
Page: 6
Section: 2.1
Variables: \(U=(u_i)_{i\in\mathbb Z}\in\mathbb R^{\ge0}\) a system of representation
Let \(D\subseteq\mathbb N\) finite

Name: An integer representation of a real
Definition: A representation \(d_k\dots d_0.d_{-1}\dots \) with every \(d_i\) equals to \(0\) for \(i<0\)
Page: 6
Section: 2.1
Variables: \(U=(u_i)_{i\in\mathbb Z}\in\mathbb R^{\ge0}\) a system of representation
\(D\subseteq\mathbb N\) finite

Definition: \(N\) if \(i=0\)
Page: 7
Section: 3.1
Variables: \(p>q\ge 1\) integers,
\(N,i\in\mathbb N\),
Notation: \(N_i\)
Definition2: \(\left\lfloor\frac{qN_{i-1}}{p}\right\rfloor\) if \(i>0\)
Conjdef: Either

Definition: The remainder of the division of \(qN_i\) by \(p\)
Page: 7
Section: 3.1
Variables: \(p>q\ge 1\) integers,
\(N,i\in\mathbb N\),
Notation: \(a_i\)

Page: 7
Implementation: \(N_0=N\),
For \(i=0\) until \(N_{i}=0\)
-\(a_i\) is the remainder of the division of \(qN_i\) by \(p\)
-\(N_{i+1}=\frac{qN_i-a_i}p\)
Section: 3.1
Variables: \(p>q\ge 1\) integers,
\(N\in\mathbb N\),
Name: Modified division
Returns: A finite sequence \(a_i\) such that \(N=\sum_{i=0}^k\frac{a_i}q\left(\frac pq\right)^i\)
Abbreviation: MD

Name: The \(\frac pq\)-expansion of \(N\)
Definition: A sequence \(a_k\dots a_0\) such that \(N=\sum_{i=0}^k\frac{a_i}q\left(\frac pq\right)^i\)
Page: 7
Section: 3.1
Variables: \(p>q\ge 1\) integers,
\(N\in\mathbb N\),
Name2: A \(\frac pq\)-representation of \(N\)

Name: The \(\frac pq\) number system
Definition: The sequence \(\left(\frac 1q\left(\frac pq\right)^i\right)_{i\in\mathbb N}\) and the alphabet \(\{0,\dots , p-1\}\)
Page: 7
Section: 3.1
Variables: \(p>q\ge 1\) integers,

Smaller0: \(\pi(u)=\pi(v)\)
Greater0: \(0^*u\) intersect \(0^*v\)
Page: 8
Section: 3.1
Variables: \(p>q\ge 1\) integers,
\(u,v\in A^*\)
Index: 5
Kind: Lem
Smaller to greater: iff

Definition: The set of \({\frac pq}\)-expansion of naturals
Page: 8, 9
Section: 3.2.1
Variables: \(p>q\ge 1\) integers,
Notation: \(L_{\frac pq}\)
Index: 9
Kind: Cor
Property: Not context free

Definition: The set of \(w\in A^{\le k}\) such that there exists \(n\in \mathbb N\) such that \(\langle n\rangle_{\frac pq}w\in L_{\frac pq}\)
Page: 8
Section: 3.2.1
Variables: \(p>q>1\) integers,
\(k,n\in\mathbb N\)
Notation: \(RC_k(n)\)

Smaller0: \(RC_k(n)\cap RC_k(m)\) contains a word of length \(k\)
Greater0: \(n\equiv m\mod q^{k}\)
Page: 9
Section: 3.2.1
Variables: \(p>q>1\) integers,
\(k,n,m\in\mathbb N\)
Index: 6
Kind: Lem
Smaller to greater: iff

Smaller0: \(RC_k(n)\cap RC_k(m)\) contains a word of length \(k\)
Greater0: \(RC_k(n)=RC_k(m)\)
Page: 9
Section: 3.2.1
Variables: \(p>q>1\) integers,
\(k,n,m\in\mathbb N\)
Index: 6
Kind: Lem
Smaller1: \(n\equiv m\mod q^{k}\)
Connect Smaller0: or equivalently

Question: The coarsest right regular equivalence that saturates \(L_{\frac pq}\) is
Answer: the identity
Page: 9
Section: 3.2.1
Variables: \(p>q>1\) integers,
Index: 6
Kind: Lem

Question: \(w\) is the suffix of
Answer: the \(\frac pq\)-expansion of all integers \(p^k\mathbb N+n\) for an unique \(n\)
Page: 9
Section: 3.2.2
Variables: \(p>q>1\) integers,
\(k\in\mathbb N\)
\(w\in A^k\)
Index: 10
Kind: Prop

Name: \(L_{\frac pq}\)
Page: 9
Section: 3.2.2
Variables: \(p>q>1\) integers,
Under: prefix
Not2: not
Under2: suffix

Name: The odometer of the number system
Definition: The function which, given the representation of \(n\in\mathbb N\) gives the representation of \(n+1\).
Page: 11
Section: 3.2.3
Variables: \(p>q>1\) integers,
Typ: Implemented by a transducer

Smaller0: \(v,w\in L_{\frac pq}\)
Greater0: \(v\preceq w\)
Page: 11
Section: 3.2.4
Variables: \(p>q>1\) integers,
\(v,w\in \{0,\dots, p-1\}^*\)
Kind: Prop
Greater1: \(\pi(v)\le\pi(w)\)
Connect Greater0: iff
Counterexample: \(\pi(10)=\frac 34<\pi(2)=1\)

Smaller0: \(\pi(v)\le\pi(w)\)
Greater0: \(v\preceq w\)
Page: 11
Section: 3.2.4
Variables: \(p>q>1\) integers,
\(v,w\in \{0,\dots, p-1\}^*\)
Kind: Prop
Smaller to greater: iff
Assuming: \(v,w\in L_{\frac pq}\)

Smaller0: \(v,w\in 0^* L_{\frac pq}\)
Greater0: \(v\sqsubseteq w\)
Page: 11
Section: 3.2.4
Variables: \(p>q>1\) integers,
\(v,w\in \{0,\dots, p-1\}^*\)
Index: 12
Kind: Cor
Smaller1: \(|v|=|w|\)
Greater1: \(\pi(v)\le\pi(w)\)
Connect Greater0: iff
Counterexample: \(\pi(2000)=\frac {27}8<\pi(0212)=4\)

Definition: the set of nodes is \(\mathbb N\)
Page: 13
Section: 4.1
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}^*\)
Notation: \(T_{\frac pq}\)
Index: (ii)
Kind: Def
Definition2: for each node \(n\), for each [$]a\in \dd(n)[/$], an edge labelled by \(a\) from \(n\) to \(\tau_a(n)\)
Conjdef: The tree with

Definition: [$]\defFun{\mathbb N}{\mathbb N}{n}{\frac{pn+a}q\text{ if it is a natural number}}[/$]
Page: 13
Section: 4.1
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}^*\)
\(a\in A\)
Notation: \(\tau_a\)
Index: 16
Kind: Def

Definition: The set of \(a\in A\) such that \(\frac{pn+a}q\in\mathbb N\)
Page: 13, 15
Section: 4.1
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}^*\)
\(n\in\mathbb N\),
Notation: [$]\dd(n)[/$]
Index: 16 (i), 18(ii)(iii)
Kind: Def, Lem
Property: Subset of \(A\) closed under \(\pm q\)

Definition: The greatest \(a\in A\) such that \(\frac{pn+a}q\in\mathbb N\)
Page: 13, 15
Section: 4.1,
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}\)
\(n\in\mathbb N\),
Notation: \(\mathrm{Md}(n)\)
Index: 16 (i), 18(i)
Kind: Def, Lem
Definition2: [$]\dd(n)\cap\{p-q,\dots, p-1\}[/$]
Definition3: \(\mathrm{md}(n+1)+p-q\)

Definition: The least \(a\in A\) such that \(\frac{pn+a}q\in\mathbb N\)
Page: 13, 15
Section: 4.1
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}^*\)
\(n\in\mathbb N\),
Notation: \(\mathrm{md}(n)\)
Index: 16 (i), 18(i)
Kind: Def, Lem
Definition2: [$]\dd(n)\cap\{0,\dots, q-1\}[/$]

Name: Path label of \(s\)
Definition: The label of the path from the root of \(T_{\frac pq}\) to \(s\)
Page: 13
Section: 4.1
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}^*\)
\(s\) a node of \(T_{\frac pq}\)
Notation: \(\mathrm{p}(s)\)
Index: 16 (iii)
Kind: Def

Definition: The subtree of \(T_{\frac pq}\) made of nodes whose path label does not begin with a 0.
Page: 13
Section: 4.1
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}^*\)
Notation: \(I_{\frac pq}\)
Index: 16 (iii)
Kind: Def

Definition: 1 if \(n=0\)
Page: 13
Section: 4.1
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}^*\)
\(n\)
Context: Rational base number system
Notation: \(G_n\)
Index: 20
Kind: Def
Definition2: \(\left\lceil \frac pqG_{n-1}\right\rceil\) if \(n>0\)
Conjdef: Either
Extra: intuition

Question: The nodes of depth \(n\), in lexicographic order, are labelled by
Answer: integers from \(0\) to \(G_n-1\)
Page: 13
Section: 4.1
Variables: \(p>q>1\)
\(A=\{0,\dots,p-1\}^*\)
\(n\)
Index: 20
Kind: Def