\documentclass[landscape]{slides}

%\usepackage[latin2]{inputenc}
%\usepackage[magyar]{babel}

%\topmargin -1cm
\usepackage{graphicx}
\usepackage{amsfonts,amssymb,amsbsy,amsmath,amscd,amstext,amsthm}

%\usepackage[active]{srcltx}

%\frenchspacing \sloppy
\newcommand{\G}{{\mathcal G}}
\newcommand{\A}{{\mathcal A}}
\newcommand{\OO}{{\mathcal O}}
\newcommand{\D}{{\mathcal D}}
\newcommand{\F}{{\mathcal F}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\K}{{\mathbb K}}
\newcommand{\DD}{{\mathcal D}}
\newcommand{\LL}{{\mathbb L}}
\newcommand{\oz}{\!\otimes_{\mathbb{Z}}\!}
\newcommand{\Qq}{\mathbb{Q}}
\newcommand{\Rr}{{\mathbb R}}

\newtheorem {Def}{Definition}
\newtheorem {theorem}{Theorem}
\newtheorem {Cor}{Corollary}
\newtheorem {Pro}{Proposition}
\newtheorem {Le}{Lemma}
\newtheorem {Con}{Conjecture}
\newtheorem{rem}{Remark}
\begin{document}

\begin{center}

 {\Large General shift radix systems and discrete rotation}\\
 \vspace{1cm}

{\large  Attila Peth\H{o} }

{Department of Computer Science\\ University of Debrecen
Debrecen, Hungary} \vspace{1.5cm}

Numeration 2019\\
Erwin Schr\"odinger Institut, Wien, July 3, 2019. \vspace{1.5cm}

{\small Talk is base on joint works with Jan-Hendrik Evertse, K\'alm\'an Gy\H{o}ry, Carolin Hannusch and J\"org Thuswaldner.}

\end{center}




\newpage
{\bf 1. CNS and SRS}\\


Let $p=p_nX^n+\ldots+p_1X+p_0\in \Z[X], p_n=1, |p_0|>1$ and $\DD=\{0,1,\ldots,|p_0|-1\}$. The pair $(p,\DD)$ is called {\it canonical number system polynomial} - CNS - if there exist for all $0\not=a\in \Z[X]$ integers $\ell$ and $a_0,\ldots,a_{\ell}\in \DD$ such that
$$
a \equiv a_0+\ldots+a_{\ell}X^{\ell} \pmod{p}.
$$

$\bullet$ This is a generalization of radix representation of integers. It was initiated by D. Knuth, and developed further by Penney, I. K\'atai, J. Szab\'o, B. Kov\'acs, etc.\\[0.5ex]
$\bullet$ Not all $(p,\DD)$ is a CNS! For example $\left(X^2+2X+2, \{0.1\}\right)$ is, but $\left(X^2-2X+2, \{0.1\}\right)$ is not a CNS. Characterization of CNS is a hard problem.

\newpage

To ${\bf r}\in \R^n$ associate the nearly linear mapping $\tau_{\bf r}\; \:\; \Z^n \mapsto \Z^n$ such that if $(a_1,\ldots,a_n) = {\bf a}\in \Z^n$ then
$$
\tau_{\bf r}({\bf a}) = (a_2,\ldots,a_n,-[{\bf ar}]),
$$
where $[.]$ denotes the integer part, and ${\bf ar}$ the inner product.

Akiyama et al., 2005, called $\tau_{\bf r}$ a {\it shift radix system} - SRS - if the orbit $\tau_{\bf r}^k({\bf a}), k=0,1,\ldots$ is eventually zero for all ${\bf a}\in \Z^n$.

They proved: $(p,\DD)$ is a CNS iff for ${\bf r}=\left(\frac{1}{p_0},\frac{p_{n-1}}{p_0}, \dots,\frac{p_n}{p_0} \right)$ the mapping $\tau_{\bf r}$ is a SRS.

Found relation between SRS and $\beta$-expansions too.

\newpage
{\bf 2. Generalized number system - GNS}\\

Let $\OO$ denote an order, that is a commutative ring
with $1$ whose additive group is free abelian of rank $d$.
Identify $m\in\Z$ with $m\cdot 1$, and thus assume $\Z\subset\OO$.

The order $\OO$ may be given explicitly by a basis $\{ 1=\omega_1,\omega_2\ldots\omega_d\}$ and a multiplication table
\begin{equation}\label{eq:multiplicationtable}
\omega_i\omega_j =\sum_{l=1}^d a_{ijl}\omega_l\ \
(i,j=2\ldots d)\ \ \text{with } a_{ijl}\in\Z,
\end{equation}
satisfying the commutativity and associativity rules.

\newpage
A \emph{generalized number system} over $\OO$ (GNS over $\OO$ for short)
is a pair $(p,\DD )$, where $p\in\OO [X]$ is a monic polynomial
such that $p(0)$ is not a zero divisor of $\OO$,
and where $\DD$ is a (necessarily finite) complete residue system of $\OO$ modulo $p(0)$
containing $0$.

An element $a\in \mathcal{O}[X]$ is \emph{representable in $(p,\mathcal{D})$} if there exist an integer $L\ge 0$ and $a_0,\dots,a_L\in \mathcal{D}$ such that
\begin{equation} \label{eq:kongruencia}
a \equiv \sum_{j=0}^L a_j X^j \pmod p.
\end{equation}
The set of in $(p,\mathcal{D})$ representable elements is $R(p,\mathcal{D})$. If $R(p,\mathcal{D}) = \OO$ then $(p,\mathcal{D})$ is called {\it GNS with finiteness property}.

A GNS $(p,\DD )$ over $\OO$ may be viewed as a matrix
number system introduced by Vince, 1993, with lattice $\Lambda =\OO [x]/(p)$, the linear mapping
$\varphi: f\pmod{p}\mapsto x\cdot f\pmod{p}$, and digit set $D=\DD$.

\newpage
We may view $\OO[X]$ as a free $\Z[X]$-module of finite rank,
and $a\mapsto p\cdot a$ as a $\Z [X]$-linear map from
$\OO[X]$ to itself. The determinant of this $\Z [X]$-linear map is a monic polynomial in $\Z [X]$, which we denote by $Np$.\\[0.5ex]

\begin{theorem}[Evertse, Gy\H{o}ry, Peth\H{o}, Thuswaldner, 2019] \label{non-ECNS1}
Let $(p,\DD )$ be a GNS over $\OO$ with $\deg p=n\geq 1$.
Then there is an effectively computable
number $C''$, depending on $\OO$, $p$ and $\DD$, such that the following are
equivalent:
\\
(i) $(p,\DD )$ has the finiteness property;
\\
(ii) the polynomial $Np$ is expansive, and every $a\in\OO [X]$
with $\| a\|\leq C''$, $\deg a <n$ belongs to $R(p,\DD )$.
\end{theorem}

\newpage
{\bf 3. Families of GNS}

We view $\OO$ as a full rank sublattice of the $\R$-algebra $\OO\oz\Rr$.
We recall that {\it $\theta\in\OO$ is not a zero divisor of $\OO$ if and only if it is invertible in $\OO\oz\Rr$}.

A fundamental domain for $\OO\oz\Rr/\OO$
is a subset of $\OO\oz\Rr$ containing precisely one element
from every residue class of $\OO\oz\Rr$ modulo $\OO$.
For a fundamental domain $\F$ for $\OO\oz\Rr/\OO$ with $0\in\F$
and
$\theta\in\OO$ which is not a zero divisor, we define
\[
\DD_{\F ,\theta} :=\theta\F\cap\OO =\{ \alpha\in\OO :\, \theta^{-1}\alpha\in\F\}.
\]


\begin{Le}\label{lem:fund-1}
Let $\F$ be a fundamental domain for $\OO\oz\Rr/\OO$ with $0\in\F$
and $\theta\in\OO$ not a zero divisor. Then $\DD_{\F ,\theta}$
is a complete residue system for $\OO$ modulo $\theta$ containing $0$.
\end{Le}

If $\F$ is a fundamental domain for $\OO\oz\Rr/\OO$ with $0\in\F$ and $p\in \OO[X]$ runs through the monic polynomials such that $p(0)$ is not a zero divisor then $(p,\DD_{\F,p(0)})$ is a family of GNS over $\OO$.

For example put $\OO=\Z$, $\F=[0,1)$ and $p\in \Z[X]$ with $p(0)>1$ then $\DD_{\F,p(0)}=\{0,1,\ldots,p(0)-1\}$, thus $(p,\DD)$ is exactly the CNS.

\newpage
{\bf 4. Generalization of SRS}

Let $0\in \mathcal{F}$ be a fundamental domain for $\mathbb{R}^d$. For any ${\bf v}\in \R^d$ there exist a unique ${\bf a} \in \Z^d$, such that ${\bf v} - {\bf a}\in \mathcal{F}$, which will be denoted by $\lfloor {\bf v} \rfloor_{\mathcal{F}}$.

For fixed matrices $R_1,\dots,R_n\in \R^{d\times d}$ define the sequence of integer vectors by the initial terms ${\bf a}_1,\dots{\bf a}_n\in \Z^d$ and for $m> n$ by the nearly linear recursive relation
\begin{equation}\label{eq:1}
  {\bf a}_{m} = - \left \lfloor \sum_{\ell=1}^{n} {R}_{\ell}{\bf a}_{m-n+\ell-1} \right\rfloor_{\mathcal{F}}.
\end{equation}

\newpage
With the $n$-tuple ${\bf R} =(R_1,\dots,R_n)$ of matrices define the mapping $\tau_{\bf R} \; : \;\Z^{d\times n} \mapsto \Z^{d\times n}$ such that if ${\bf A}=({\bf a}_1,\dots,{\bf a}_n)\in \Z^{d\times n}$ then
\begin{equation}\label{eq:21}
\tau_{\bf R}({\bf A}) = ({\bf a}_2,\dots,{\bf a}_n,{\bf a}_{n+1}),
\end{equation}
where ${\bf a_{n+1}}$ is defined by \eqref{eq:1} with $m=n+1$. The mapping $\tau_{\bf R}$ is called {\it generalized SRS, or short GSRS}.

For $k=1$ identify the matrices $R_1,\dots,R_n,$ with their real entries and ${\bf R}$ with a $n$-dimensional real vector. Similarly ${\bf A}$ can be identified with a $n$-dimensional integer vector. Further in \eqref{eq:1} in the bracket stays the inner product of ${\bf R}$ and ${\bf A}$. Choosing finally $\mathcal{F} = [0,1)$ we get the familiar definition of SRS.

\newpage
{\bf 5. Relation between GNS and GSRS}

We show similar relation between GNS and GSRS as between CNS and SRS.

Let $p \in \OO[X]$ of degree $n$ be monic, such that $p(0)$ is not a zero divisor and consider the GNS $(p,\DD)$, where $\DD= \DD_{\F,p(0)}$. Let $a\in \OO_n[X]$, where $\OO_n[X]$ denotes the elements of $\OO[X]$ of degree at most $n-1$.

\newpage
Let $T_p \; :\; \mathcal{O}_{n}[x] \mapsto \mathcal{O}_{n}[x]$ be the \emph{backward division mapping}, which is defined as
$$
T_p(a)(X) = \frac{a(X) - qp(X)- d}{X},
$$
where $d\in \mathcal{D}$ is the unique element of $\DD$ with $d \equiv a(0) \pmod{p_0}$ and $q=\frac{a(0)-d}{p_0}$. This means $q = \left\lfloor \frac{a(0)}{p_0}\right\rfloor_{\F}$.

Iterating  $T_p$ for $h$-times we obtain $d_0,\dots, d_{h-1} \in \mathcal{D}$, and $r\in \mathcal{O}[X]$ such that
\begin{equation}\label{eq:bRepH}
a(X) = \sum_{j=0}^{h-1} d_j X^j + X^h T_p^{h}(a)(X) + r(X)p(X).
\end{equation}
Clearly, $a\in R(p,\mathcal{D})$ if and only if there exists $h_0$ such that $T_p^h(a)= 0$ for all $h\ge h_0$.

\newpage
The mapping $T_p$ acts essentially on the coefficient vector ${\bf a}=(a_0,\ldots,a_{n-1})$ of $a=\sum_{i=0}^{n-1}a_i X^i$ by the rule
$$
T_p({\bf a}) = (a_1-qp_1,\dots,a_{n-1}-qp_{n-1},-qp_n) = T {\bf a} - q {\bf p},
$$
where $q = \left\lfloor \frac{a(0)}{p_0}\right\rfloor_{\F}$, ${\bf p} =(p_1,\dots,p_{n})$ and $T=(t_{ij})_{i,j=1,\dots,n}$ is the matrix with $t_{i,i+1}=1, i=1,\dots,n-1$ and all other entries are zero.

\newpage
Choosing a different basis for $\OO_n[x]$, as in Brunotte (2001) or Scheicher and Thuswaldner (2003)
$$
w_j = \sum_{m=1}^{j}p_{n-j+m} X^{m-1},\; j=1,\ldots,n
$$
we get a different form of this transformation. Writing
$$
a= \sum_{j=0}^{n-1} a_j X^j = \sum_{j=1}^n c_jw_j
$$
then
$$
T_p({\bf c}) = \left(c_2,\ldots,c_n,-\left\lfloor {\bf cp'}\right\rfloor_{\F}\right),
$$
where ${\bf c}=(c_1,\ldots,c_n)$ and $p'=\left(\frac{p_n}{p_0},\ldots,\frac{p_1}{p_0}\right)$.

\newpage
Now we prove that $T_p$ is a special case of $\tau_{\bf R}$.

Write $c_j = {\bf c}_j(\omega_1,\ldots,\omega_d)$ with ${\bf c}_j\in \Z^d, j=1,\ldots,d$  

The multiplication with any fixed element of $\OO$ is a linear mapping of $\OO$ into itself. As $p(0)$ is not a zero divisor, $1/p(0)$ is a well defined element of $\OO\oz\Rr/\OO$. One can extend the multiplication to $1/p(0)$ such that it is again a linear mapping on $\OO\oz\Rr/\OO$. Thus there exist $M_1,\ldots,M_n \in \Q^{d\times d}$ associated to the multiplication by $p_n/p_0,\ldots,p_1/p_0$. Thus
$$
{\bf cp'} = \sum_{j=1}^{n} M_j {\bf c_j},\; \mbox{i.e}, \; T_p({\bf c})= \tau_{M_1,\ldots,M_n}({\bf c_1},\ldots, {\bf c_n}).
$$
which proves the claim.

\newpage
\begin{theorem}
  Let $p\in \mathcal{O}[X]$ be monic and such that $p(0)$ is not a zero divisor. Let $\mathcal{F}$ be, a fundamental domain for $\mathbb{R}^d$. Then
$a \OO[X]$ is representable in $(p,\D_{\F,p(0)})$ if and only if the orbit of $\tau^k_{(M_1,\ldots,M_n)}({\bf c_1},\ldots, {\bf c_n})$ is ultimately zero.
\end{theorem}

\newpage
{\bf An example}

Let $\OO=\sqrt{-7}, \omega_1=1, \omega_2=\frac{1+\sqrt{-7}}{2}, {\bf \omega}=(\omega_1,\omega_2)$ and $\F=[0,1)^2$. Then
$$
\omega_1\left(
\begin{array}{c} \omega_1\\ \omega_2 \end{array}
  \right) = 
  \left(
\begin{array}{cc} 1&0\\ 0&1 \end{array}
  \right)  \quad \mbox{and} \quad
  \omega_2\left(
\begin{array}{c} \omega_1\\ \omega_2 \end{array}
  \right) =
  \left(
\begin{array}{cc} 0&1\\ -2&1 \end{array}
  \right).
  $$
  Let $p= X + \frac{-1+\sqrt{-7}}{2}$. Then
  \[
  \frac{1}{p(0)} = -\frac{1+\sqrt{-7}}{4} = - \frac{\omega_2}{2}.
  \]
  
  \newpage
  Hence $\DD=\{0,-1\}$ and the matrix associated to the multiplication by $1/p(0)$ is $M=\left(\begin{array}{cc} 0&-1/2\\ 1&-1/2 \end{array}
  \right).$ 
  
  Finally the searched dynamical system is $$\left(
\begin{array}{c} a_1\\ a_2 \end{array}
  \right) \mapsto \left(
\begin{array}{c} \lfloor -a_2/2\rfloor\\ \lfloor a_1 - a_2/2 \rfloor \end{array}
  \right),$$
  where $a_1,a_2\in \Z$.
  
  \newpage
  
  {\bf 6. Closer look at the case $n=1$}
  
  In the case $n=1$ the GSRS simplifies to 
  $$
  {\bf a}_{m} = \tau_R({\bf a}_{m-1})=-\left\lfloor R{\bf a}_{m-1} \right\rfloor_{\F},\; \mbox{for}\; m\ge 1,
  $$
  where $R \in \R^{d\times d}$ and ${\bf a}_{0}\in \Z^d$.
  
  \begin{theorem}
    If all orbits of $\tau_R$ are periodic then the spectral radius of $R$ is at most $1$, consequently $|\det R| \le 1$.
  \end{theorem}
  
  \begin{theorem}
    If the spectral radius of $R$ is less than $1$ then all orbits of $\tau_R$ are periodic.
  \end{theorem}
  
  Notice that the above properties are independent from $\F$. In the sequel $\F=[0,1)^d$.
  
  What happens when all eigenvalues of $R$ lie on the unit circle? 
  
  \newpage
  
  {\bf 6.1. Discrete rotation on the plane}
  
  We consider the case $n=1, d=2$ and $R\in \R^{2\times 2}$, which has two different eigenvalues on the unit circle. (Only $\pm1$ can be multiple eigenvalues.) A convenient representation of $R$ is
  $$
  R = T A_{\varphi} T^{-1},\quad A_{\varphi} = \left(
\begin{array}{rr}
\cos \varphi & -\sin \varphi\\
\sin \varphi & \cos \varphi
\end{array}
\right)
$$ 
where $T\in \R^{2\times 2}$ is an invertible matrix and $0\le \varphi<2\pi$. 

The points $R^k(a,b)^T, \; (a,b)\in \Z^2$ form a {\bf bounded set}; generally they lie on an ellipse, in the case $T=E$, i.e., $R=A_{\varphi}$ on the unit circle.

\newpage
Akiyama, Brunotte, Peth\H{o} and Steiner (2006) studied the case $n=2,d=1$, when $a_{m+1}=-\lfloor \lambda a_m +a_{m-1} \rfloor$ with $|\lambda|<2$.

We can write
\begin{eqnarray*}
% \nonumber % Remove numbering (before each equation)
  a_{m+1} &=& -\lfloor \lambda a_m +a_{m-1} \rfloor \\
  a_m &=& -\lfloor - a_m  \rfloor.
\end{eqnarray*}
Putting $R=\left(\begin{array}{cc}
                 \lambda & 1 \\
                 -1 & 0
               \end{array}
\right)$ we obtain
$$
\left(\begin{array}{c}
                 a_{m+1} \\
                 a_m
               \end{array} \right)= -\left \lfloor R 
\left(\begin{array}{c}
                 a_{m} \\
                 a_{m-1}
               \end{array} \right) \right \rfloor.
$$
Thus $n=2,d=1$ is a special case of $n=1,d=2$. 

\newpage
Akiyama et al. conjecture that the sequence $(a_m)$ is always periodic.

In 2008 they verified this conjecture for $\lambda=\pm \sqrt{2}, \pm \frac{1\pm\sqrt{5}}{2}$.

Akiyama and Peth\H{o} proved (2013) that for any $\lambda$ there are infinitely many starting values $a_0,a_1$ such that $(a_m)$ is periodic.

\newpage
\begin{center}\vbox{
\includegraphics{négyzet.jpg}\\
Staring value $(10,9), \varphi=0.001$.
}\end{center}

\newpage
\begin{center}\vbox{
\includegraphics{hatszög.jpg}\\
Staring value $(0,910), \varphi=0.001$.
}\end{center}

\newpage
\begin{center}\vbox{
\includegraphics{kör.jpg}\\
Staring value $(1904,0), \varphi=0.11$.
}\end{center}

\newpage
\begin{theorem}
  There are infinitely many $(a,b)\in Z^2$ such that the sequence ${\bf x}_0=(a,b), {\bf x}_{m+1} = \lfloor A_{\pi/4} {\bf x}_m, m=0,1,\ldots$ is periodic of length $8$. 
\end{theorem}

The proof is tiering computation with the integer part function. Its essence is:\\[0.5ex]

\begin{Le}
  	Let $a\in \N,$ $\omega=\lfloor \frac{1}{\sqrt{2}}a\rfloor$ and suppose $\lfloor \sqrt{2}\omega\rfloor = a-1.$ If $\{\frac{1}{\sqrt{2}}a\}\in \left[1-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right],$ and $\{\sqrt{2}\omega\}\in \left[1-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right],$ then $A_{\varphi}^8 (a,0)=(a,0).$
\end{Le}

\newpage
\begin{center}
  {\Huge Thank you for the attention!}
\end{center}

\end{document} 