\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 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}