\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 {\QQ}  {{\mathbb Q}}
\newcommand {\ZZ}  {{\mathbb Z}}
\newcommand {\C}  {{\mathbb C}}
\newcommand {\R}  {{\mathbb R}}
\newcommand {\PP}  {{\mathbb P}}
\newcommand {\NN}  {{\mathbb N}}
%\newcommand {\FF}  {{\mathbb F}}
\newcommand {\K}  {{\mathbb  K}}
\newcommand {\BB}  {{\mathfrak B}}
\newcommand {\DD}  {{\mathcal D}}
\newcommand {\FF}  {{\mathcal F}}
\newcommand {\OO}  {{\mathcal O}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{conj}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{ex}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}

\begin{document}

\begin{center}

 {\Large Number systems over orders of\\[0.5 cm] algebraic number fields}
 \vspace{1.5cm}

{\large Attila Peth\H{o} }

\vspace{.5 cm}

{\small Department of Computer Science, University of Debrecen, Hungary\\
and University of Ostrava, Faculty of Science, Czech Republic} \vspace{1.5cm}

{Joint work with J\"org Thuswaldner, Leoben, Austria}

\vspace{.8 cm}

{\small Numeration 2018\\
Paris, May 22 - 25, 2018}



\end{center}


\newpage


{\bf 1. Introduction}

In the last century mainly through the work of Gr\"unwald, Knuth, Penney, K\'atai, Gilbert, J\'ulia Szab\'o, B. Kov\'acs, K\"ormendi, K\"ornyei evolved the notation of number systems or equivalently the radix representations in $\mathbb{Z}[x]$ and in algebraic number fields.

Generalizations to larger ground rings:\\[.5ex]
$\bullet$ Jacob and Reveilles (1995), Brunotte, Kirschenhofer and Thuswaldner (2011): $\ZZ[i]$\\
$\bullet$ Scheicher, Surer, Thuswaldner and van de Woestijne (2014): commutative rings\\
$\bullet$ Peth\H{o} and Varga (2017): Euclidean imaginary quadratic number fields.

\newpage
We generalize here the number system concept in two directions:\\[.5ex]
$\bullet$ Allow orders of algebraic number fields as ground rings. (Radix representation in relative extensions.)\\
$\bullet$ The digit set is defined on a uniform way, which allow the investigation of families of polynomials. {\it We show that the canonical digit set is extraordinary, it has very special properties.}

\newpage

{\bf 2. Definitions and basic properties}

Notations:\\[.5ex]
$\bullet$ $\mathbb{K}$ number field of degree $k$,\\
$\bullet$ $\alpha^{(1)}, \dots, \alpha^{(k)}$ the conjugates of $\alpha\in \K$,\\
$\bullet$ $\mathcal{O}$ an order in $\mathbb{K}$, {\it i.e.}, a ring which is a full $\mathbb{Z}$-module in $\mathbb{K}$. \\
$\bullet$ $1=\omega_1,\omega_2,\dots,\omega_k$ a $\mathbb{Z}$-basis of $\OO$, \\
$\bullet$ $H(a) = \max\{|a_l^{(j)}|,\; l=0,\dots,n, \; j =1,\dots,k \}$ the {\it height} of $a$, provided $a(x) = \sum_{l=0}^{n} a_l x^l\in \mathcal{O}[x]$.\\

A \emph{generalized number system over $\mathcal{O}$} (GNS for short) is a pair $(p,\mathcal{D})$, where $p \in \mathcal{O}[x]$ is monic, $p_0\not=0$ and $\mathcal{D}\subset\mathcal{O}$ is a complete residue system modulo $p(0)$. The polynomial $p$ is called \emph{basis} of this number system, $\mathcal{D}$ is called its set of \emph{digits}.

For the GNS $(p,\mathcal{D})$ denote $R(p,\DD)$ the set of $a\in \mathcal{O}[x]$ for which there exists $b\in \DD[x]$ such that
$$
a \equiv b \pmod{p}.
$$

The GNS $(p,\mathcal{D})$ has the \emph{finiteness property}, if $R(p,\DD)= \mathcal{O}[x]$.

\newpage
Let $\mathcal{F}$ be a bounded fundamental domain for the action of $\mathbb{Z}^k$ on $\mathbb{R}^k$, {\it i.e.}, a set that satisfies $\mathbb{R}^k=\mathcal{F}+\mathbb{Z}^k$ without overlaps. For $\alpha\in\mathcal{O}$ define
\begin{equation}\label{eq:DF}
D_{\mathcal{F}}= D_{\mathcal{F},\alpha} = \Big\{\tau\in \mathcal{O} \; : \; \frac{\tau}{\alpha} = \sum_{j=1}^{k}r_j \omega_j, \,(r_1,\ldots, r_k) \in \mathcal{F} \Big\}.
\end{equation}

\begin{lemma}
$D_{\mathcal{F},\alpha}$ is a complete residue system modulo $\alpha$.
\end{lemma}

\begin{lemma}\label{lem:domaindigit}
Let $(p,\mathcal{D})$ be a GNS over $\mathcal{O}$. Then there is a  bounded fundamental domain $\mathcal{F}$ for the action of $\mathbb{Z}^k$ on $\mathbb{R}^k$ such that $\mathcal{D}=D_{\mathcal{F},p(0)}$.
\end{lemma}

A fixed fundamental domain $\mathcal{F}$ defines a whole class of GNS, namely,
\[
\mathcal{G}_\mathcal{F} := \{ (p, D_\mathcal{F}) \;:\; p \in \mathcal{O}[x]  \}.
\]


\newpage

Examples:

$\bullet$ {\it Classical CNS} Let $\mathbb{K}=\mathbb{Q}$ and $\mathcal{O}=\mathbb{Z}$. Choose $\mathcal{F}=[0,1)$ which obviously is a fundamental domain of $\mathbb{Z}$ acting on $\mathbb{R}$. We look at the class
$
\mathcal{G}_\mathcal{F} := \{ (p, D_\mathcal{F}) \;:\; p \in \mathbb{Z}[x]  \}.
$
For an integer $\alpha\ge 2$ we have
\[
D_{\mathcal{F},\alpha} = \left\{\tau\in \mathbb{Z} \; : \; \frac{\tau}{\alpha} = r, r \in [0,1) \right\}=\{0,\ldots, |\alpha|-1\},
\]
which is the digit set of a canonical number system.

If, however, $\alpha \le -2$ then
\[
D_{\mathcal{F},\alpha} = \left\{\tau\in \mathbb{Z} \; : \; \frac{\tau}{\alpha} = r, r \in [0,1) \right\}=\{\alpha+1, \ldots, 0,\} = -\{0,\ldots, |\alpha|-1\}.
\]

\newpage
$\bullet$ {\it Symmetric CNS} $(p,\mathcal{D})$ is a symmetric CNS if $p\in\mathbb{Z}[x]$ and
$$
\mathcal{D}=\big[-\frac{|p(0)|}2,\frac{|p(0)|-1}2\big) \cap \mathbb{Z}.
$$
These number systems were studied for instance by Akiyama and Scheicher (2007), Brunotte (2009), K\'atai (1995) and Scheicher, Surer, Thuswaldner and van de Woestijne (2014). They are equal to the class $\mathcal{G}_\mathcal{F} := \{ (p, D_\mathcal{F}) \;:\; p \in \mathbb{Z}[x]  \}$ with $\mathcal{F}=[-\frac12,\frac12)$ of GNS.


\newpage

\begin{proposition} \label{Prop1}
Let $(p,\mathcal{D})$ be a GNS with finiteness property. Then all roots of each conjugate polynomial $p^{(j)}(x)$,  $j\in\{1,\dots,k\}$, lie outside the closed unit disk.
\end{proposition}


Adapting the proof of Akiyama and Rao (2004) or Peth\H{o} (2006) to orders one can prove the following algorithmic criterion for checking the finiteness property of a given GNS $(p, \mathcal{D})$. \\[1ex]


\begin{theorem} \label{non-ECNS1}
Let $\mathbb{K}$ be a number field of degree $k$ and let $\mathcal{O}$ be an order in $\mathbb{K}$.
Let $(p,\mathcal{D})$ be a GNS over $\mathcal{O}$. There exists a computable constant $C=C(p,\mathcal{D})$ such that $(p,\mathcal{D})$ is a GNS with finiteness property if and only if the polynomial $\prod_{i=1}^{k} p^{(i)}(x)$ is expansive and
\[
\{
a \in \mathcal{O}[x] \;:\; \deg a < \deg p \hbox{ and } H(a) \le C
\} \subset R(p,\mathcal{D}).
\]
\end{theorem}


\newpage

{\bf 3. General criterion for the finiteness property}\\[1ex]

\begin{theorem}[B. Kov\'acs (1981)]
  Let $p=x^n+a_{n-1}x^{n-1}+\ldots+a_0\in \ZZ[x]$ such that $1\le a_{n-1}\le \ldots \le a_0, a_0\ge 2$. Then $(p,\{0,1,\ldots,a_0-1\})$ is a GNS.
\end{theorem}

Generalizations: Akiyama and Peth\H{o} (2002), Scheicher and Thuswaldner (2004), or Peth\H{o} and Varga (2017).\\
In each of these results $|p(0)|$ dominates over the other coefficients of $p$. In general, $\mathcal{O}$ does not have a natural ordering. However, inclusion properties of some sets can be used to express dominance of coefficients in $\mathcal{O}$.

\newpage
For $p(x)=x^n+p_{n-1}x^{n-1}+\cdots+p_0 \in \mathcal{O}[x]$ let $(p,\mathcal{D})$ be a GNS and let $\mathcal{F}$ be an associated fundamental domain. 

We call $\mathbf{z}'\in \mathbb{Z}^k$ a \emph{neighbor} of $\mathbf{z}\in \mathbb{Z}^k$ if $\mathcal{F}+\mathbf{z}$ ``touches'' $\mathcal{F}+\mathbf{z}'$, {\it i.e.}, if $(\overline{\mathcal{F}} + \mathbf{z}) \cap (\overline{\mathcal{F}}+\mathbf{z}') \not= \emptyset$. Let $\mathcal{N}$ be the set of neighbors of $\mathbf 0$.

Set  (letting $p_n=1$)
{\small
\begin{equation}\label{eq:deltaz}
\Delta = \bigg\{\sum_{j=1}^k \eta_j\omega_j \;:\; (\eta_1,\ldots, \eta_k) \in \mathcal{N} \bigg\}
\quad
\hbox{and}
\quad
Z=\bigg\{
\sum_{j=1}^n \delta_j p_j \;:\; \delta_j\in \Delta
\bigg\},
\end{equation}
}
and note that, since $\mathcal{F}$ is bounded, these sets are finite.

\newpage
\begin{theorem}\label{th:1}
Let $p(x)=x^n+p_{n-1}x^{n-1}+\cdots+p_0\in \mathcal{O}[x]$ and $(p,\mathcal{D})$ be a GNS. Let $\mathcal{F}$ be an associated fundamental domain and define $\Delta$ and $Z$ as in \eqref{eq:deltaz}. Assume that the following conditions hold:\\[.5ex]
{\bf (i)} $Z + \mathcal{D} \subset \bigcup_{\delta \in \Delta} (\mathcal{D} + p_0\delta)$, \\[.5ex]
{\bf (ii)}
$Z \subset \mathcal{D} \cup (\mathcal{D} - p_0)$, \\[.5ex]
{\bf (iii)} $\left\{ \sum_{j\in J} p_j \;:\; J\subseteq\{1,\ldots, n\}  \right\} \subseteq \mathcal{D}$.\\[.5ex]
Then $(p,\mathcal{D})$ has the finiteness property.
\end{theorem}


\newpage
{\bf 4. The finiteness property for large constant terms}

Notations:\\[.5ex]
$\bullet$ $(M)_\varepsilon$ \emph{$\varepsilon$}-neighborhood of a set $M\subset \R^k$,\\[.5ex]
$\bullet$ ${\rm int}_+$ is the interior taken w.r.t.\ the subspace topology on $\{(r_1,\ldots, r_k) \in \mathbb{R}^k\;:\; r_1 \ge 0\}$. The symbol ${\rm int}_-$ is defined by replacing $r_1 \ge 0$ with $r_1 \le 0$.

\newpage
\begin{theorem}\label{th:newKovacs}
Let $\mathbb{K}$ be a number field of degree $k$ and let $\mathcal{O}$ be an order in $\mathbb{K}$. Let a monic polynomial $p\in \mathcal{O}[x]$ and a bounded fundamental domain $\mathcal{F}$ for the action of $\mathbb{Z}^k$ on $\mathbb{R}^k$ be given. Suppose that\\[.5ex]
$\bullet$ $\mathbf{0} \in {\rm int}(\mathcal{F} \cup (\mathcal{F}-\mathbf{e}_1))$, where $\mathbf{e}_1=(1,0,\ldots,0)$ and \\[.5ex]
$\bullet$ $\mathbf{0} \in {\rm int}_+(\mathcal{F})$.\\[.5ex]
Then there is $\eta > 0$ such that $(p(x + \alpha),D_\mathcal{F})$ has the finiteness property whenever $\alpha = m_1\omega_1 + \dots + m_k \omega_k\in \mathcal{O}$ satisfies $\max\{1,|m_2|,\ldots,|m_k|\}< \eta m_1 $.
\end{theorem}

{\it If $\FF$ satisfies the conditions of Theorem \ref{th:newKovacs} the set $\{(p,\DD_{\FF,p(0)}\}$ contains infinitely many GNS with finiteness property.}


\newpage
Theorem~\ref{th:newKovacs} immediately admits the following corollary.\\[1ex]

\begin{cor}\label{cor:newKovacs}
Let $\mathbb{K}$ be a number field of degree $k$ and let $\mathcal{O}$ be an order in $\mathbb{K}$. Let a monic polynomial $p\in \mathcal{O}[x]$ and a bounded fundamental domain $\mathcal{F}$ for the action of $\mathbb{Z}^k$ on $\mathbb{R}^k$ be given. If $\mathbf{0} \in {\rm int}(\mathcal{F})$ then there is $\eta > 0$ such that $(p(x + \alpha),D_\mathcal{F})$ has the finiteness property whenever $\alpha = m_1\omega_1 + \dots + m_k \omega_k\in \mathcal{O}$ satisfies $\max\{1,|m_2|,\ldots,|m_k|\}< \eta |m_1|$.
\end{cor}

\newpage
{\it
Under the conditions of Theorem~\ref{th:newKovacs}
\[
\exists \; M\in\mathbb{N}:\;(p(x+m),\mathcal{F}) \hbox{ is a GNS with finiteness property for } m\ge M,
\]
while under the more restrictive conditions of Corollary~\ref{cor:newKovacs}
\[
\exists\; M\in\mathbb{N}:\; (p(x\pm m),\mathcal{F})  \hbox{ is a GNS with finiteness property for}\; m\ge M.
\]
}

\newpage
The next Corollary answers partially a question of Akiyama.\\[1ex]

\begin{cor} \label{cor:Akiyama}
Let $\mathbb{K}$ be a number field of degree $k$ and let $\mathcal{O}$ be an order in $\mathbb{K}$. Let a monic polynomial $p\in \mathcal{O}[x]$ and a bounded fundamental domain $\mathcal{F}$ for the action of $\mathbb{Z}^k$ on $\mathbb{R}^k$ be given. Suppose that $\mathbf{0} \in {\rm int}(\mathcal{F})$ then there is $\eta > 0$ such that $(p(x) \pm \alpha,D_\mathcal{F})$ has the finiteness property whenever $\alpha = m_1\omega_1 + \dots + m_k \omega_k\in \mathcal{O}$ satisfies $\max\{1,|m_2|,\ldots,|m_k|\}< \eta |m_1|$.
\end{cor}

\newpage
{\it
  If $k=1$, and $0< \varepsilon<1$ then $\mathcal{F}_{\varepsilon}=[-\varepsilon,1-\varepsilon)$ satisfies the conditions of Corollary \ref{cor:Akiyama}, hence for any $p\in \ZZ[x]$ there exists $M\in \ZZ$ such that $(p(x)\pm m, \mathcal{F}_{\varepsilon})$ is a GNS with finiteness property in $\ZZ[x]$.\\[1ex]
The assumptions of Theorem \ref{th:newKovacs} hold for $\mathcal{F}_{\varepsilon}$ even if $ \varepsilon=0$. Hence, if all coefficients of $p$ are non-negative, then we can conclude  $(p(x)+m, \mathcal{F}_{0})$ is a GNS with finiteness property in $\ZZ[x]$.\\[1ex]
  However, if some of the coefficients of $p$ are negative, then our method fails and, we do not have similar statement. The example $p=x^2-2x+2$ shows that $(p(x)+m, \mathcal{F}_{0})$ is not a GNS with finiteness property in $\ZZ[x]$ for any $m\ge 0$.

}

\newpage
{\it
  If there are infinitely many units in $\mathcal{O}$ then for all $p\in \mathcal{O}[x]$ there exist infinitely many $\alpha \in \mathcal{O}$ such that the constant term of $p(x) + \alpha$, {\it i.e.}, $p(0) + \alpha$ is a unit, hence $p(x) + \alpha$ is not GNS with finiteness property. Notice that Condition (iii) of Theorem \ref{th:1} holds under the assumptions of Corollary \ref{cor:Akiyama} only if the norm of $p(0) + \alpha$ is large.
}

\newpage
{\bf 5. GNS without finiteness property}\\

We start with a partial generalization of a Theorem of Kov\'acs and Peth\H{o} (1991) to polynomials with coefficients of $\mathcal O$.\\[0.5ex]

\begin{lemma} \label{non-ECNS2}
Let $(p,\mathcal{D})$ be a GNS. If there exist $h \in \mathbb{N}$, $d_0,d_1,\dots,d_{h-1} \in \mathcal{D}$ not all equal to $0$ and $q_1,q_2 \in \mathcal{O}[x]$ with
    \begin{equation} \label{non-ECNSeq1}
   \sum_{j=0}^{h-1} d_j x^j  =  (x^{h} - 1) q_1(x) + q_2(x)p(x).
    \end{equation}
then $(p,\mathcal{D})$ doesn't have the finiteness property.
  \end{lemma}

\newpage
Our main result in this section is the following theorem.\\[0.5ex]

\begin{theorem} \label{non-ECNSmain}
Let $\mathbb{K}$ be a number field of degree $k$ and let $\mathcal{O}$ be an order in $\mathbb{K}$. Let a monic polynomial $p\in \mathcal{O}[x]$ and a bounded fundamental domain $\mathcal{F}$ for the action of $\mathbb{Z}^k$ on $\mathbb{R}^k$ be given. Suppose that
%$\mathbf{0} \in {\rm int}(\mathcal{F} \cup (\mathcal{F}-\mathbf{e}_1))$ and
$\mathbf{0} \in {\rm int}_{-}(\mathcal{F}-\mathbf{e}_1)$.
There exists $M \in \mathbb{N}$ such that $(p(x-m),D_\mathcal{F})$ doesn't have the finiteness property for $m\ge M$.
\end{theorem}


\newpage
{\bf 6. GNS in number fields}\\

Let $\alpha \in \mathcal{O}_{\mathbb{L}}$ and let $\mathcal{N}$ be a complete residue system modulo $\alpha$. The pair $(\alpha,\mathcal{N})$ is called a {\it number system in $\mathcal{O}_{\mathbb{L}}$}. If for each $\gamma \in \mathcal{O}_{\mathbb{L}}$ there exist integers $\ell\ge 0$, $d_0,\dots,d_{\ell-1}\in \mathcal{N}$ such that
$$
\gamma = \sum_{j=0}^{\ell-1}d_j \alpha^j
$$
then we say that $(\alpha,\mathcal{N})$ has the {\em finiteness property}.
If the digit set is chosen to be $\mathcal{N}=\{0,1,\dots,|N_{\mathbb{L}/\mathbb{Q}}(\alpha)|-1\}$ then $(\alpha,\mathcal{N})$ is called a {\it canonical number system in $\mathcal{O}_{\mathbb{L}}$}.

\newpage
Kov\'acs (1981) proved that there exists a canonical number system with finiteness property in $\mathcal{O}_{\mathbb{L}}$ if and only if $\mathcal{O}_{\mathbb{L}}$ admits a power integral bases. Later Kov\'acs and Peth\H{o} (1991) proved the stronger result.\\[1ex]


\begin{proposition}
  Let $\mathcal{O}$ be an order in the algebraic number field $\mathbb{L}$. There exist $\alpha_1,\dots,\alpha_t \in \mathcal{O}$, $n_1,\dots,n_t \in \mathbb{Z}$, and $N_1,\dots,N_t$ finite subsets of $\mathbb{Z}$, which are all effectively computable, such that $(\alpha,\mathcal{N}(\alpha))$ is a canonical number system with finiteness property in $\mathcal{O}$ if and only if $\alpha=\alpha_i-h$ for some integers $i,h$ with $1\le i \le t$ and either $h\ge n_i$ or $h\in N_i$.
\end{proposition}

\newpage
From Corollary \ref{cor:newKovacs} we derive that for number systems the relation is usually stronger, the theorem of Kov\'acs and Peth\H{o} describes a kind of ``boundary case'' {\it viz.} a case where $0\in\partial\mathcal{F}$.\\[1ex]

\begin{theorem} \label{thm:newKovacsPetho}
Let $\mathbb{L}$ be a number field of degree $l$ and let $\mathcal{O}$ be an order in $\mathbb{L}$. Let $\mathcal{F}$ be a bounded fundamental domain for the action of $\mathbb{Z}$ on $\mathbb{R}$. If $0 \in {\rm int}(\mathcal{F})$ then all but finitely many generators of power integral bases of $\mathcal{O}$ form a basis for a number system with finiteness property. Moreover, the exceptions are effectively computable.
\end{theorem}

The proof combines a deep result of Gy\H{o}ry (1978) with Corollary~\ref{cor:newKovacs}.

\newpage
{\it
The assumption $0\in {\rm int}(\mathcal{F})$ implies that $\{-1,0,1\} \subseteq D_{\mathcal{F},p_j(\delta m)}$ for all $m$ large enough. Of course $-1 \notin \mathcal{N}_0(\alpha+m)$, hence, the proof of Theorem~\ref{thm:newKovacsPetho} does not work in the case of canonical number systems.
}
{\it Gy\H{o}ry's theorem holds for relative extensions as well. To generalize Theorem~\ref{thm:newKovacsPetho} to this situation would require the generalization of Corollary~\ref{cor:newKovacs} to all $m \in \mathcal{O}$, such that all conjugates of $m$ are large enough. We have no idea how to prove such a result.}

\newpage

\centerline{\Huge Thank you for your attention!}
\end{document}

