\documentstyle[11pt]{article}
\author{}
\title{Cubic CNS Polynomials}
\setlength{\parindent}{0pt} 
\setlength{\parskip}{5pt plus 2pt minus 1 pt}
\frenchspacing
\bigskip
\sloppy
\begin{document}
\maketitle
\begin{abstract}
A conjecture of W. J. Gilbert's on 
canonical number systems which are defined by cubic polynomials 
is partially proved, and it is shown that the conjecture is not complete.
\end{abstract}
\baselineskip=18pt
\section{Introduction}
Let $P \in {\bf Z} [X]$ be a monic polynomial 
with $\left|P(0) \right| > 1$ and
 $\cal{N}$ $ = \lbrace 0, 1, \dots$, \mbox{$\left|P(0) \right| - 1 \rbrace$.}
The pair $(P, \cal{N})$
is called a canonical number system (CNS)
if every non-zero element of $R :={\bf Z} [X]/P{\bf Z} [X]$ can 
uniquely be written in the form 

\centerline{$a_0 + a_1 x + \cdots + a_l x^l$}

with $a_0,...,a_l \in \cal{N}$, $a_l \neq 0$; here
$x$ denotes the image of $X$ under the canonical epimorphism from
${\bf Z} [X]$ to $R$.

The concept of canonical number systems in the general form described above was introduced
by  A. Peth\H o \cite{apetho91}; canonical number systems with more
restrictions on the defining polynomials have been
studied by several authors (see e.g. the introduction of
\cite{sakape00} and the references given there).

\vfill

\centerline{AMS classification 11R04, 11R16, 11R21, 12D99}

\newpage
S. Akiyama and A. Peth\H o \cite{sakape00} suggested that the
 characterization problem 
of canonical number  systems is only  
related  to the 
coefficients of the defining polynomial. Therefore
the term CNS polynomial (see the 
definition below) seems to be reasonable.

It is known that CNS polynomials can be applied in cryptography
\cite{apetho91} and fractal tilings of the Euclidean space
\cite{sakjmt01}. 

The present note aims at  a partial proof of
a conjecture of    
W. J. Gilbert \cite{wjgilb81}
on cubic CNS polynomials; further a new application of canonical
number systems is introduced.

\section{Notation and basic results on CNS polynomials}

As usual we denote by ${\bf Z}$ the ring of integers and by
${\bf N}$  the set of nonnegative integers.
Let $P = \sum_{i=0}^d p_i X^i \in {\bf Z} [X]$ with $d >0, p_d = 1$
and  $\left|p_0 \right| > 1$.
We often use the {\it length} of $P$ (cf. \cite{sakape00}) which is
given by $$L(P) = \sum_{i=1}^d \left| p_i \right|;$$ note that
this terminology slightly differs from the usual one.
 
{\bf Definition}. 
$P$ is a CNS polynomial if the pair $(P, \cal{N})$ forms a canonical number system.

Let $\cal{C}$ be the class of CNS polynomials.

The following lemma was proved  by  A. Peth\H o \cite{apetho91} (cf. the introduction
of \cite{sakape00}).

{\bf Lemma L-p91}  (A. Peth\H o).
If $P$ is a CNS polynomial then
all real zeroes of $P$ 
are less than $-1$ and  the absolute values of
all complex roots of $P$ exceed $1$. In particular
 $p_0 > 1$.

{\bf Remark}.
Note, however, that in case $d > 1$ these properties do not imply that the given polynomial
is a CNS polynomial (e.g. the roots of the non CNS polynomial 
$f= X^2 - 2 X + 2$ are $1 \pm \sqrt{-1}$; further the roots of the non CNS polynomial
$(X +2) f$ satisfy the above conditions).
 

In view of Lemma L-p91 we shall assume $p_0 > 1$ from now on.

{\bf Theorem Thm-KP00}  (B. Kov\'acs, A. Peth\H o). 

Let $ P= X^d+p_{d-1}X^{d-1}+ \cdots + p_1 X+p_0 \in {\bf Z} [X]$ such that  
$p_0 \geq p_1 \geq \dots \geq p_{d-1} \geq 1$ and none of the roots
of $P$ is a root of unity. Then
$P$ is a CNS polynomial.

{\bf Remark}. Note that in general the above condition on the roots
of $P$ cannot be omitted (e. g. 
$X^3+X^2+ p_0 X+p_0 $
is not a CNS polynomial because it vanishes at $-1$).

{\bf Corollary} (A. Peth\H o (28. 7. 2001), HB, July 2001) C-PB01 
\footnote {(A. Peth\H o (30. 7. 2001))
Ihre Abschaetzung ueber Produkte linearer CNS-Polynome ist
schoen, ich fuerchte aber, dass es bei der Loesung des
Problems nicht viel hilft. Betrachten Sie z.B. die Familie
der Polynome
$P_m(x)=(x+2)(x+3)(x+4)(x+m)$
$ =x^4 + (m+9)x^3 + (9m+26)x^2 + (26m+24)x + 24m.$
Die Koeffizientenfolge ist nie monoton fallend, da
$26m+24 > 24m$ gilt fuer alle $m \ge 0$. Ich versuchte die Zeugemenge
E fuer diese Polynome aufzubauen. Sie waechst aber mit m.
Die Differenz $P_{m+1}(x)-P_m(x)=(x+4)(x+3)(x+2)$ ist ein CNS
Polynom. Gegenbeispiele zeigen aber, dass die Summe CNS
Polynome erben nicht notwendig die CNS Eigenschaft. Man
braucht also neuere Ideen solche Probleme zu loesen.}

Let $d \geq 2$. Then there exists a constant $2 \leq c(d) \leq d$ with the
 following property: If $m_1,  \dots , m_d$ are integers with
$m_1,  \dots , m_d \geq c(d)$ then $$(X + m_1) \cdots (X + m_d)$$
is a CNS polynomial. One can choose $c(2) = c (3) = 2$.

{\bf Remark} (A. Peth\H o (28. 7. 2001)
The case $d=2$ is trivial. For $d=3$ and $m_1,m_2,m_3$
pairwise distinct one has to check only the trials
$(m_1,m_2,m_3)=(2,3,4); (2,3,5)$, which I did by computer.

{\bf Remark} (HB, July 2001)

The statement for $d=3$ be derived from the following result (some cases have to
be calculated explicitly):

Let $r,s,t$ be real numbers such that
$min \{r,s,t\} \geq 3$ or $(min\{r,s,t\} \geq 2$ and $max \{r,s,t\} \geq 5).$
If $f = (X + r) (X + s) (X + t)$ has integral coefficients then $f$ is 
a CNS polynomial.

{\bf Remark}. (HB (1. 9. 2001))

The square of  a CNS polynomial of degree larger than  $ 1$ 
is not necessarily a CNS polynomial (e.g. take $f = X^2 - X + p_0$;
by (\cite{sakape00}, Thm. 3)  $f^2 = X^4 - 2 X^3 + (2p_0 + 1) X^2 - 2p_0 X + p_0 ^2$ 
is not a CNS polynomial in case $p_0 \geq 5$.

Therefore the following conjecture has to be restricted (to nonnegative 
coefficients?).

{\bf Conjecture} (A. Peth\H o (28. 7. 2001), Conjecture 2)

If $P_1, P_2$ are CNS polynomial then
$P_1 P_2$ is a CNS polynomial, too
\footnote{Die Umkehrung  $P= fg \in \cal{C}$, $f,g$ normiert, ganzzahlig
impliziert wahrscheinlich nicht, da� es eine Konstante $c$ gibt mit der
Eigenschaft: Falls $f(0) > c$, dann ist $f\in \cal{C}$.}.
In this direction \footnote{zun�chst vielleicht: $(X + m) P \in \cal{C}$ ?}
 I have the result C-PB01.


{\bf Remark} (S. Akiyama (10. 2. 2001))

The sum of CNS polynomials of different degrees is not
 necessarily a CNS polynomial (e.g.
the polynomials
$f=X^3+4X^2-5X+6$ and
$g=X^2+2X+2$
are CNS polynomials by proposition P-hb00 and theorem Thm-G, respectively,
but $ f+g=X^3+5X^2-3X+8$
is not a CNS polynomial since the element $x^2+4x-9$ is periodic).


{\bf Theorem} (Rao, 18. 5. 2001). 

Let $P=X^d+p_{d-1}X^{d-1}+ \cdots + p_1 X+p_0 \in {\bf Z} [X]$ be a monic
 polynomial.
If $p_1,\dots, p_{d-1}$ are non negative and
$p_0> L(P)$ then $P$ is a CNS polynomial.
\footnote{ (S. Akiyama (18. 5. 2001)):
Rao claimed it can be done in some
cases with $p_1<0$, but for this part I did not check yet
the details.}

{\bf Theorem} (Rao, 23. 5. 2001). 

Let $P=X^d+p_{d-1}X^{d-1}+ \cdots  + p_1 X+p_0 \in {\bf Z} [X]$ be a monic
 polynomial.
If $p_1+ \cdots +p_{d-1}+1 \geq 0, p_0 \geq L(P),
p_2, \dots ,p_{d-1} \geq 0$
then $P$ is a CNS polynomial.

{\bf Remark}. (S. Akiyama (23. 5. 2001))

This theorem proves Conjeture 1 stated in the paper of
S. Akiyama and A. Peth\H o \cite{sakape00}.

{\bf Example}. If $p_0 \geq d$ and $p_1,  \dots, p_{d-1} \in  \{0,1\}$
then $P$ is a CNS polynomial because
$ L(P) = p_1+ \cdots +p_{d-1} +1 \leq d \leq p_0$. Note, however,
that $X^3+X^2+ 2$ is not a CNS polynomial by proposition P-B01.
 
The same method allows one to prove

{\bf Theorem} (Akiyama, 23. 5. 2001). 

Let $P=X^d+p_{d-1}X^{d-1}+ \cdots + p_1 X+p_0 \in {\bf Z} [X]$ be a monic
 polynomial.
If $p_2+p_4+...+p_{2[d/2]}\geq 0, p_0 \geq L(P),
p_1,p_3,p_4,...,p_{d-1} \geq 0$
then $P$ is a CNS polynomial
\footnote{(S. Akiyama (23. 5. 2001))
Akiyama and Rao also improved the algorithmic bound
appeared in the paper of
S. Akiyama and A. Peth\H o \cite{sakape00}.
The idea is essentially due to the thesis of Michael Hollander
on beta expansions, a different type of expansion.
He was a disciple of B. Solomyak and his idea was
in fact very sharp.}.

Let
$$\tau: {\bf Z}^n \longrightarrow {\bf Z}^n,
(a_1, \dots,a_n) \mapsto  (- \left\lfloor \frac{p_1 a_1 + \cdots +
 p_n a_n}{p_0} \right\rfloor,a_1,\dots,a_{n-1})\leqno(2)$$
(cf.  \cite{hbruno01}).

{\bf Theorem} (Pethoe, 10. 9. 2001). 

Let $P(x) = p_d x^d +p_{d-1} x^{d-1} + \dots +p_0 \in Z[x]$ be a square-free
polynomial, i.e. without multiple roots. Denote $\alpha_1, \dots , \alpha_d$
the roots of $P(x)$ and suppose that 
$|\alpha_i|>1 (1 \le i \le d)$ and the real roots are less then
$-1$. Then for every $a \in {\bf Z}^n$  there exists $k\ge 0$ such that
the absolute values  all coordinates of
$\tau^k(a)$ are less then
$$
(p_0 -1) \sum_{i=1}^d \frac{|\alpha_i^{d-1}|}{(|\alpha_i|-1)|P'(\alpha_i)|},
$$
where $P'$ denotes the derivative of $P$.

{\bf Remark}. (Pethoe, 10. 9. 2001).
This means that although $\tau$ is not contractive, but it is ultimative
contractive.
I also computed the bound for the polynomial $(x+2)(x+3)(x+4)(x+m)$, where
$m\ge 5$ integer, and it is 700 for large enough $m.$ It is quite large, but
independent from $m$!



The problem of characterizing CNS polynomials seems to be a hard
 one --- it maybe even be not possible algebraically.
By Lemma L-pe91, it is very easy to show that linear CNS polynomials
are given by 
 $X + p_0$  with $p_0   \geq 2$;
however, only very little is known about other types of polynomials. 
For the sake of completeness, we list the known results in this
direction.

{\bf Theorem} (W. J. Gilbert) Thm-G.

 $X^2 + p_1 X + p_0$  is a CNS polynomial if and only if $- 1 \leq p_1 \leq p_0$.

For a proof see e.g. (\cite{hbruno02}, Thm. 2).

{\bf Theorem} Thm-hb02

Let $d > 2$.

(i)  $X^d + p_1 X + p_0$ is a CNS polynomial if and only if
 $- 1 \leq p_1 \leq p_0 - 2$.

(ii) If $1 < q < d $ and and $q$ does not divide $d$ then 
$X^d + p_q X^q +p_0$ is a CNS polynomial if and only if
 $0 \leq p_q \leq p_0 - 2$.

For a proof see  (\cite{hbruno02}, Thm. 3).

These  two  statements suffice for a characterization of
CNS trinomials because we have the following result:

{\bf Theorem}.

Let $Q \in {\bf Z} [X]$ be a monic polynomial, $r \in {\bf N}, r \geq 2$
and $P(X)= Q(X^r)$. Then $P$ is a CNS polynomial if and only if $Q$
is a CNS polynomial.

For a proof see  (\cite{hbruno02}, Thm. 1).









\section{Cubic CNS polynomials}

From now on we shall essentially concentrate on cubic polynomials.
Therefore we let 
$P=X^3+p_2X^2+p_1 X+p_0 \in {\bf Z} [X]$ be a monic cubic polynomial
throughout this section.

The following theorem 
which states necessary conditions for cubic 
CNS polynomials is essentially one part of Gilbert's  \cite{wjgilb81}
conjecture; the major part of it was proved in (\cite{sakape00}, Prop. 1).  

{\bf Theorem} (one part of Gilbert's conjecture (1981)). Thm-G81

Let $P$ be a CNS polynomial. Then

$(i) \enspace p_0 \geq 2$\\
$(ii) \enspace 1+p_1+p_2 \geq 0$\\
$(iii) \enspace p_0 + p_2 \geq p_1 + 2$\\
$(iv) \enspace p_1 \leq 0$ implies $0 \leq p_2 \leq
 min \{p_0-2, (p_0^2 + p_1-2)/p_0\}$\\  
$(v)\enspace 1 \leq p_1 \leq p_0 - 1$ implies $0 \leq p_2 \leq p_0-1$\\
$(vi)\enspace p_1 \geq p_0$ implies $2 \leq p_2 \leq p_0$.

As the following example shows the above conditions are not
sufficient. 

{\bf Example} (S. Akiyama (10. 2. 2001))

Let $ p_2+1\leq p_0\leq(3p_2+1)/2$ and
$max \{2-p_2,-2p_2+p_0-1\} \leq p_1 \leq min \{p_2-p_0,-p_2/2\}$.
Then the element $x^2+(p_2-1)x+p_1-p_2-1$ is periodic.

Note that in this case there are infinitely
 many non CNS polynomials
 when $3p_2/2=p_0$ indeed by taking
$p_2=2m, p_1=-m$   or $-m-1, p_0=3m.$
\footnote{
HB (26. 8. 2001):
Prof. Akiyamas counterexample of Feb. 10th in case of negative $p_1$
can be slightly extended. Let $m, k \geq 3, p_0 = km,
p_1= - (k - 2) m + (k - 3), p_2= (k - 1)m$ then the corresponding
polynomial is non CNS.

Note that in theses cases we have $p_2 = (k - 1)p_0 / k$
and that on the other hand there exist CNS polynomials with
negative $p_1$ and $(k-2)p_0 / k < p_2 < (k-1)p_0 / k$
(e.g. $ p_0 \geq  k, p_1 = -1$).}


In an effort to prove sufficiency
Gilbert's result suggests the treatment of four different
types of polynomials according to the size of the coefficient $p_1$.
Recall that we assume $p_0 \geq 2$ throughout.

Firstly, we deal with negative coefficients $p_1$.

{\bf Proposition} (S. Akiyama (24. 2. 2001)) P-A01

Let
$ (i) -p_0 + p_2 + 1 \leq p_1 \leq 0,$

$ (ii)   0 \leq p_2  \leq p_0-2,$

$(iii) 1+p_2+p_1\geq 0,$

$ (vi) 1 \leq p_1+p_2 .$

 Then $P$ forms a CNS polynomial.

{\bf Proof}.
The method may be quite similar to the one used in \cite{hbruno01}.
I constructed the set E of 19 elements explicitly, that is,

${-1,-1,0},{-1,-1,1},{-1,0,0},{-1,0,1},{-1,1,1},\\
{0,-1,-1},{0,-1,0},{0,-1,1},{0,0,-1},{0,0,0},\\
{0,0,1},{0,1,-1},{0,1,0},{0,1,1},{1,-1,-1},\\
{1,0,-1},{1,0,0},{1,1,-1},{1,1,0}$

Then it is easy to construct a directed tree by our
CNS algorithm with minimal element (0,0,0) showing
that it is a CNS polynomial.

{\bf Proposition} (HB) P-hb

If

$ (i) p_1 \leq 0,$ \\
$(ii) 1 + p_1 + p_2  \geq 0,$\\
$(iii) 0 \leq p_2 <  min \{p_0 - 1, 2p_0/3\},$\\
then $P$ is a CNS polynomial
\footnote{S. Akiyama (10. 2. 2001):
According to the joint
paper of
S. Akiyama and A. Peth\H o \cite{sakape00}, $P$
is a CNS polynomial if $p_0$ is sufficiently large (cf. however,
the above mentioned consequence of Rao's theorem) if $p_2  \geq 0, 1+p_1+p_2\geq 0.$
So the problem is to classify all exceptions under above five
conditions.

I first tried to find out all such possible exceptions
by computer. There are lots of very sensitive cases so it
seems far from completed. But there exist three easy
exceptional cases:

1) $ p_1 \leq 0, p_2\geq 1, p_0=p_2+1, p_1+p_2>0$
\footnote{klar nach Satz von Gilbert}: $-x-p_2$ is periodic.

2) $ 1<p_1<p_0, p_0=p_2$ \footnote{klar nach Satz von Gilbert}: $x+p_2$ is periodic.

3) $ p_2+1\leq p_0\leq(3p_2+1)/2$,\\
$max \{2-p_2,-2p_2+p_0-1\} \leq p_1 \leq min \{p_2-p_0,-p_2/2\}$:\\
$x^2+(p_2-1)x+p_1-p_2-1$ is periodic.}

\footnote{S. Akiyama (5. 3. 2001):
While confirming the last statement of Prof. Brunotte,
I found my misleading: I wrote $ p_0>3p_2/2$ and other
necessary conditions seems enough to be CNS. But it is
too strong and should be replaced by $2p_0-2\geq  3p_2$
\footnote {Aus $2p_0-2\geq  3p_2$ folgt $ p_0>3p_2/2$!}.
The difference between them is small but it is essential
in proving our statement. In fact there exist counter
examples of non CNS polynomials in case 3):
$$max\{2-p_2,-2p_2+p_0-1\} \leq p_1 \leq min\{p_2-p_0,-p_2/2\}$$
with $p_2=2n+1, p_0=3n+1$. After this slight modification,
our proof works fine by writing basic graphs of size 19,
35, 43, and 15 (`basic' means that we need more graphs
to treat exceptional cases on the boundary).

Moreover it seems that the same method works when $p_1 \leq p_0$.
In other words,
the necessary conditions $2p_0-2\geq 3p_2$ and $ p_1 \leq p_0$
imply that it is a CNS polynomial. But I did not complete
the details. The only thing needed here is the careful treatment
of lots of linear inequalities so it can be done in a few days.

The remaining problem is the case $p_1>p_0$ which seems to
have no absolute bound on the size of the graph. But
there would be a way to settle this case using some family
of sets E, since the nature of growth of graphs has strong
regularity.}.

{\bf Remark} If $p_0$ is large enough then 
the coefficient $p_2$ of a CNS polynomial may exceed $2p_0/3$ (e. g. 
$p_0 = 7, p_1 = 0, p_2 = 5$ define a CNS polynomial by the above
 proposition. Further, Rao's theorem shows that $P $ is a 
CNS polynomial if $p_1 = -1 $ and $2p_0/3 \leq p_2 \leq p_0 - 3$).


{\bf Proposition} (HB)

If

$ (i) - p_0 + 1 \leq p_1 \leq -1$ \\
$(ii) 1 + p_1 + p_2 = 0$\\
then $P$ is a CNS polynomial.

In contrast to proposition P-hb we loosely list some results valid for
$p_2 = p_0 - 2$.

{\bf Proposition} (HB)

Let $p_2 = p_0 - 2$ and $ - p_0 + 1 \leq p_1 \leq -1$. 

 ??$ (i)$ If $p_0 \leq 5$ then $P$ is a CNS polynomial.\\
$ (ii)$ If $p_0 \geq 6$ and $  - p_0 + 4 \leq p_1 \leq 1 - p0 / 2$
then $P$ is a not a CNS polynomial.\\
$ (iii)$ If $p_0 \geq 6$ and $  p_1 \leq  - p0 + 3$
then the AP graph of $P$ is finite and does not contain any cycles.


In case of vanishing $p_1$ we immediately derive 
a necessary and sufficient condition
form
the above result on trinomials:

{\bf Proposition} 

$X^3+p_2X^2+p_0 \in {\bf Z} [X]$ is a CNS polynomial if and only if
$0 \leq p_2 \leq p_0 - 2.$



Thirdly, we  deal with small positive coefficients $p_1$.
Theorem Thm-KP00 tells us:

{\bf Proposition} 

If $1 \leq p_2 \leq p_1 \leq p_0 - 1$
then $P$ is a CNS polynomial.

{\bf Proposition} (HB, 9. 3. 2001)

If

$ (i) 1 \leq p_1 \leq p_ 0 - 1,$ \\
$(ii) 0 \leq p_2 \leq min \{p_0 - 1, (2p_0 -1) /3\}$\\
then $P$ is a CNS polynomial.



Finally, we  deal with large positive coefficients $p_1$.
The theorem Thm-KP00 immediately yields

{\bf Proposition} 

If
$ p_1 = p_ 0$ and
$ 2 \leq p_2 \leq p_0$
then $P$ is a CNS polynomial.

Further only very few results are known:

{\bf Proposition} (HB)

If
$ p_0 \le p_1$ 
then $P$ is a CNS polynomial if one of the following conditions holds:

$(1) p_1 = p_0 + 1$ and $3  \leq p_2 \leq p_0$\\
$(2) p_1 = p_0 + 2$ and $p_2 = (p_0 + 4)/2$\\
$(3)  p_0 < p_1, p_1 - p_2 <  p_0 - 1, 3 p_2 < 2 p_0,
4 p_1 - 3 p_2 < 4 p_0 -2$\\
$(4) p_2 \leq p_0, p_1 - p_2 <  p_0 - 2, 0 \leq p_1 - 2p_2,
 2 p_1 - p_2 \leq 2p_0$\\
$(5) (p_1,p_2) \neq (4,3), p_1 - p_2 <  p_0 - 1, -2 \leq p_1 - 2p_2,
 2 p_1 - p_2 < 2p_0$\\
$(6) 1 \leq p_2 \leq p_0, -1  \leq p_1 - 2p_2,
 2 p_1 - p_2 \leq 2p_0 - 1$\\
$(7) 2 \leq p_2 \leq p_0, p_1 - p_2 <  p_0 - 1, p_1 - 2p_2 \leq -2,
 2 p_1 - p_2 \leq 2p_0, p_0 - 1 \leq 2p_1 - 2 p_2, p_1 + p_2 \leq 2p_0 + 2$\\

{\bf Example}.  
$X^3+p_0X^2+(p_0 + 2) X+p_0$ is a CNS polynomial for $p_0= 4, 5, 6$,
but clearly it is not a CNS polynomial for $p_0= 2, 3$. 

To end this section we gather some more conditions which yield
CNS polynomials.

Rao's theorem immediately yields the following characterization of
cubic CNS polynomials if $p_0$ is large.

{\bf Theorem}  

Let $p_0 \geq  L(P)$. 
Then $P$ is a CNS polynomial if and only if
$p_2 \geq 0$ and $1+p_1+p_2 \geq 0$.


{\bf Proposition} (HB, Nov. 2000) P-B00

Let the coefficients of $P$
satisfy conditions $(i) - (iv)$ of theorem Thm-81. Then $P \in \cal{C}$
if one of the following conditions hold:

$(1)\enspace p_1 + p_2 + 1=0$\\
$(2)\enspace p_1 + p_2 = 0$\\
$(3)\enspace p_1  = 0$\\
$(4)\enspace -p_0 + p_2 \leq p_1  \leq - 1$\\
$(5)\enspace p_1 - p_2 \leq - p_0 -1, -p_0 +2 \leq 2p_1 + p_2,
3 \leq p_1 + 2 p_2 \leq p_0-2,\\ 6 \leq 2 p_2 \leq p_0 - 2, p_1 + p_2 = 1$


{\bf Counterexamples}

(i) S. Akiyama, A.  Peth\"o (Nov 2000)

Let $p_0,p_1,p_2$ be positive integers with
$$(1) \enspace 2 \leq p_2 - p_1 \leq p_1$$
$$(2) \enspace 2 \leq p_0 \leq min\{p_1 +p_2, 2p_2 - p_1\}$$
then the element $(p_1 - p_2 + 1) + (-p_2 -1)x - x^2$
is not representable.

(ii) (HB, Nov. 2000)

If
$2(p_0 +1) \leq p_1 + p_2 \leq 3 p_0 +1,
 2(p_0 +1) \leq 2p_1 -  p_2 \leq 3 p_0 +1,
 - p_0 - 3 \leq p_1 - 2 p_2 \leq -4,
 2p_0 - 1 \leq 3p_1 - 2 p_2 \leq 3 p_0 - 2,
 -1 \leq 2p_1 - 3 p_2 \leq p_0- 2,$
then $P$ is not a CNS polynomial because the element
 $1 -2p_1+p_2+(1-2p_2)x -2 x^2 $
is not representable in the canonical way.

{\bf Remark} (S. Akiyama (19. 2. 2001))

5) If $p_0+p_2/2+1 \leq p_1 \leq min \{2p_2-4, p_0+(2p_2-2)/3\}$
then $(x^2+p_2x+p_1)-2(x+p_2)+3$ is periodic.

6) If $max \{p_0+(2p_2-1)/3,3p_2/2-1\} \leq p_1 \leq 2p_2-4$
then $(x^2+p_2x+p_1)-2(x+p_2)+3$ is periodic.

7) If $max \{(p_0-2p_2+1)/2, (-p_2+3)/2, (-2p_0+p_2+4)/2\} \leq p_1 \leq
 min \{-2p_0+2p_2,(-2p_1+3)\}$
then $2(x^2+p_2x+p_1)-(x+p_2)-2$ is periodic.

and so on. I found another four cases as well but it takes
another several hours/days to formulate these in a similar
manner. Perhaps it will be too messy to state. I am not at
all sure that exceptional cases is finite.


\section{Research problems}

S. Akiyama (5. 3. 2001):

Question 1. Assume that $P$ is a CNS polynomial. Does there
always exist a finite set $E$ satisfying the conditions of
Prof. Brunotte?

Question 2. Can we estimate the minimum size of $E$ in terms of $P$?

Question 3. Must the predecessor of $(0,0,0)$ be $(0,0,1)$ for
the minimal graph $E$? This is a sufficient condition that
the CNS tile is connected.

\section{Application}
\subsection{Simultaneous representation of integers}
A. Peth\H o (28. 7. 2001) 

The following theoreom describes a remarkable connection between
simultaneous representation of integers and integral
interpolation.
It is based on CNS polynomials which decompose into products
of linear factors.

Indeed, let $a=(a_1,\dots,a_d)$, $m=(m_1,\dots, m_d) \in {\bf Z}^d$
 where $m_1,\dots, m_d$ are pairwise
 distinct negative integers. 

$(i)$ The vector $a$ is
called integrally interpolable by $m$ if there exists a
polynomial $A \in {\bf Z}[X]$ such that $A(m_i)=a_i$ for
all $1 \le i \le d.$

The chinese remainder theorem gives a
necessary and sufficient criterion for the solubility of the
integral interpolation problem, but that criterion is very
hard to apply.

$(ii)$ We call $a$ simultaneously
representable by $m$ if there exist integers $q_0, \dots, q_l$
such that
$$
a_i = \sum_{j=0}^l q_j m_i^j,
$$
where $0 \le q_j \le |m_1 \dots m_d|$.

Note that the digits do not depend on $i$!

Now I am able to prove

II. If $(X-m_1) \cdots (X-m_d)$ is a CNS polynomial
then $a$ is integrally interpolable by $m$ if and only if $a$ is
simultaneously representable by $m$.

The combination of I. and II. gives Thm-P01.
I strongly belive that such an assertion can not depend on
the size of the interpolation points, which supports
conjecture 2.

{\bf Theorem} (A. Peth\H o (2001)) Thm-P01

Let $d \geq 2$. Then there exists a constand $c(d) \leq d$ with the following
property: If $m_1,\dots,m_d \le -2$ are pairwise different
negative integers with 
 $|m_i| \le c(d)$ 
and $m=(m_1,\dots, m_d)$ then
$a\in {\bf Z}^d$ is integrally interpolable by $m$ if and only if $a$ is
simultaneously representable by $m$.
One can choose $c(2) = c(3) = 2$.


\subsection{Simplest cubic fields}

Let $m, t$ be integers, $P$ the minimal polynomial of $\Theta - m$ where
$\Theta$ is a zero of
$$X^3 - t X^2 - (t + 3) X - 1.$$

Then:
             
(i) If $t \leq -2$ then $P$ is a CNS polynomial if and only if $m \geq 2.$\\
(ii) If $t = -1$ then $P$ is a CNS polynomial if and only if $m \geq 3.$\\
(iii) If $t \geq 0$ then $P$ is a CNS polynomial if and only if $m \geq t + 3$. 


\section{Further Conjectures}

A. Peth\H o (28. 7. 2001) 

Conjecture 1.

If $P$ is a CNS polynomial, then there exists
a constant $c$ depending only on the coefficients of P such
that $P+k$ is a CNS polynomial for every integer $k\ge c$
too.
Maybe $c=1$ is true too.

It follows from Theorem 2 of the paper of Akiyama and myself,
that if $P \in Z[X]$ and $p_{d-1},\dots, p_2 \ge 0$ then
then exists a constant $c_1$
\footnote{If $P \in \cal{C}$ then $1+p_1+ \cdots p_{d-1} \geq 0$.
The assertion follows by using $ c_1 = max\{0,2L(P)-p_0\}$}
 such that $P+k$ is a CNS
polynomial for every integer $k\ge c_1.$
On the other hand this is not true for any polynomial with
integer coefficients, because if $p_{d-1} < -1$ then no
translation of $P$ yields a CNS polynomial.

\section{Problems}

\begin{enumerate}
\item
Warum keine alg. Charakterisierung?
\item
Ansatz $T(z) = Az + b(z)$ (aber $f(z) = A(z) f (Tz) + b(z)$ nach \cite{gloajp82})?
\item
Cryptographic applications of the results of A. Peth\H o \cite{apetho91}?
\item
Use of algebraic dynamical systems, 3 x + 1 -- problem?
\item
Proof of A. Peth\H o's bound and applications?
\item
Hints to the research questions above?
\item
Could Prof. Pethoe's Conjecture 1 be verified by
a thorough analysis of Euclid's algorithm for polynomials
(maybe even for P(X) + 1)?
\item
Might it be true that $P(X+1)$ is a CNS polynomial if
$P(X)$ is a CNS polynomial?
\end{enumerate}

\begin{thebibliography}{99}
\bibitem{sakape00}
{\sc S. Akiyama and A. Peth\H o}, On canonical number systems,
Theoret. Comp. Sci. (to appear)
\bibitem{sakhra02}
{\sc S. Akiyama and H. Rao}, 
(to appear)
\bibitem{sakjmt01}
{\sc S. Akiyama, J. M. Thuswaldner}, 
Topological Properties of Two-Dimensional Number Systems,
Journal de Theorie de Nombres de Bordeaux (2001 ?)
\bibitem{hbruno01}
{\sc H. Brunotte}, 
On trinomial bases of radix representations of algebraic integers,
Acta Sci. Math. (Szeged) {\bf 67}, 407 -- 413 (2001) 
(to appear)
\bibitem{hbruno02}
{\sc H. Brunotte}, 
Characterization of CNS Trinomials,
(manuscript)
\bibitem{wjgilb81}
{\sc W. J. Gilbert}, Radix Representations of Quadratic Fields,
J. Math. Anal. and Appl. {\bf 83}, 264 -- 274 (1981) 
\bibitem{bkovac81}
{\sc B. Kov\'acs}, Canonical number systems in algebraic number
fields, Acta Math. Hung. {\bf 37}, 405 -- 407 (1981)
\bibitem{gloajp82}
{\sc J. H. Loxton, A. J. van der Poorten},
J. Reine Angew. Math. {\bf 330}, 159 -- 172 (1982)  
\bibitem{apetho91}
{\sc A. Peth\H o}, 
On a polynomial transformation and its application to the construction
of a public key cryptosystem,
{\it Computational  Number Theory}, Proc., Walter de Gruyter Publ.
Comp.,  Eds.: A. Peth\H o, \mbox{M. Pohst,} H. G. Zimmer and H. C. Williams,
31 -- 44 (1991)
\end{thebibliography}
\end{document}

