\documentclass[12pt]{amsart}
\usepackage{amsfonts,amsmath,amssymb,a4wide,ifthen}
\usepackage{algorithmic,algorithm}
\usepackage{amsthm,array,url}



\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\card}{card}
\newcommand{\teilt}{\mid}
\newcommand{\teiltnicht}{\nmid}
\newcommand{\kongr}{\equiv}
\newcommand{\union}{\cup}
\newcommand{\bigunion}{\bigcup}
\newcommand{\assign}{\leftarrow}
\newcommand{\append}{\,\&\,}
\newcommand{\lexlt}{<_{\mathit{lex}}}
\newcommand{\lexge}{\ge_{\mathit{lex}}}
\newcommand{\NOT}{\textbf{not}\ }
\newcommand{\AND}{\textbf{and}\ }
\newcommand{\OR}{\textbf{or}\ }

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}


\newcommand{\klammern}[4][]%
{\ifthenelse{\equal{#1}{}}{\left#2}{\csname#1\endcsname#2}%
#4\ifthenelse{\equal{#1}{}}{\right#3}{\csname#1\endcsname#3}}

\newcommand{\betrag}[2][]{\klammern[#1]{\lvert}{\rvert}{#2}}
\newcommand{\fl}[2][]{\klammern[#1]{\lfloor}{\rfloor}{#2}}
\newcommand{\ceil}[2][]{\klammern[#1]{\lceil}{\rceil}{#2}}
\newcommand{\cond}[2][]{\klammern[#1]{[}{]}{#2}}
\newcommand{\fractional}[2][]{\klammern[#1]{\{}{\}}{#2}}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}%[section]

\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}


\numberwithin{equation}{section}


\newcommand{\eps}{\varepsilon}
\let\oldepsilon\epsilon
\renewcommand{\epsilon}{\DONOTUSE}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}


\newcommand{\replaced}{\rightarrow}
\newcommand{\replacedend}{\twoheadrightarrow}


\newenvironment{equationenumerate}{\begin{enumerate}%
    \let\origitem\item%
    \renewcommand{\item}{\refstepcounter{equation}\origitem[(\theequation)]}%
}%
{\end{enumerate}}

\title[Minimal Expansions in Redundant Number System]{On Minimal Expansions in Redundant Number Systems: Algorithms and
  Quantitative Analysis}
\author{Clemens Heuberger}
\address{Institut f\"ur Mathematik\\
Technische Universit\"at Graz\\
Steyrergasse 30\\
A-8010 Graz\\
Austria}
\email{cheub@weyl.math.tu-graz.ac.at}
\urladdr{http://finanz.math.tu-graz.ac.at/\textasciitilde cheub/}
\thanks{The first author has been partially supported by the
  Spezialforschungsbereich F 003 ``Optimierung und Kontrolle''/Projektbereich
  Diskrete Optimierung}

\author{Helmut Prodinger}
\address{The John Knopfmacher Centre for Applicable Analysis and Number
  Theory\\
  Department of Mathematics, University of the Witwatersrand\\
  P. O. Wits, 2050 Johannesburg, South Africa}
\email{helmut@gauss.cam.wits.ac.za}
\urladdr{http://www.wits.ac.za/helmut/index.htm}



\begin{document}

\begin{abstract}
  We consider digit expansions in base $q\ge 2$ with arbitrary integer digits
  such that the length of the expansion plus the sum of the absolute values of
  the digits is minimal. Since this does not determine a unique minimal
  representation, we describe some reduced minimal expansions.
  
  We completely characterize its syntactical properties, give a simple
  algorithm to compute the reduced minimal expansion and a formula to compute a
  single digit without having to compute the others, and we calculate the
  average cost of such an expansion.
\end{abstract}
\maketitle

\section{Introduction}
On several occasions, representations of integers in redundant number systems
have been studied. The motivation usually comes from various applications where
``better'' representations of an integer result in faster computations. 

We give an example from public key cryptography using elliptic curves: These
cryptosystems rely on the fact that it is rather easy to compute a multiple
$nP$ of a given point on an elliptic curve $E(\F_q)$, but there is no known
efficient way to calculate $n$ from the knowledge of $P$ and $nP$. Of course,
if the computation of $nP$ can be done even faster, larger values of the
parameters can be chosen in order to make the system less vulnerable. The usual
way to calculate $nP$ is a repeated doubling and addition algorithm, see Knuth
\cite{Knuth:1998:Art:2}. As it was remarked by Morain and Olivos
\cite{Morain-Olivos:1990}, a repeated doubling and addition or subtracting
scheme can be applied using a representation $n=\sum_{i=0}^l \eps_i 2^i$ where
$\eps_i\in\{0,\pm 1\}$. The time to compute $nP$ decreases as $l+1+\sum_i
\betrag{\eps_i}$ decreases, since it is as easy to add a point on an elliptic
curve as to subtract it.

Additionally, in the last years differential power analysis of cryptosystems
has attracted attention: it tries to recover secret keys by monitoring power
signals of cryptographic devices. Since in the usual doubling and addition
scheme it can easily be detected whether an addition and a doubling or a
doubling alone takes place, the binary representation of $n$ can be guessed.
But if digits $\pm 1$ are used, a potential attacker can gain less information.
We refer to Coron~\cite{Coron:1999} for further discussions.

This motivates the study of representations of an integer $n$ in base $q\ge 2$
with arbitrary digits, and we will denote the set of such representations by
\begin{equation}
  R_q(n):=\left\{\eps=(\eps_0,\dots,\eps_l): l\in\N, \eps_i\in\Z,
  n=\sum_{i=0}^l \eps_iq^i\right\}.
\end{equation}

We define the \emph{cost of a representation} $\eps\in R_q(n)$ as
\begin{equation}
  \label{eq:cost-definition}
  c(\eps)=c(\eps_0,\dots,\eps_l):=l+1+\sum_{i=0}^l \betrag{\eps_i}
\end{equation}
and look for representations of $n$ with minimum cost.

At several places in this paper, we will also consider a modified cost
function, which we will call \emph{relaxed costs,} namely
\begin{equation}
  \label{eq:relaxed-cost-definition}
  c'(\eps)=c'(\eps_0,\dots,\eps_l):=\sum_{i=0}^l \betrag{\eps_i}.
\end{equation}

We note that in general there is no unique minimal representation:
Both $(-1,2)\in R_3(5)$ and $(2,1)\in R_3(5)$ are representations of $5$ in
base $3$ with cost $c(-1,2)=c(2,1)=5$. It will be a consequence of
Theorem~\ref{th:unique-invariant-minimal-representation} that there are no 
cheaper expansions in $R_3(5)$.

Our first aim in Section~\ref{sec:reduced-representations} is to describe a
special minimal representation (which we will call a reduced representation),
which will be unique (cf.\ 
Theorem~\ref{th:unique-invariant-minimal-representation}). The proof of
uniqueness will immediately give an efficient algorithm to compute the reduced
representation (cf.\ Algorithm~\ref{alg:pseudo-cheub}). The corresponding
results for relaxed costs and the conversion rules between the two
representations will be discussed in
Section~\ref{sec:relaxed-reduced-representations}.

In Sections~\ref{sec:Odd-q} and \ref{sec:formula-even-q} we will give an
explicit formula for the digits of the reduced representation in the case of
odd and even $q$, respectively. These formul\ae{} will be very useful for the
computation of the frequencies of digits and the expected costs of the
representations, as will be shown in Section~\ref{sec:counting-digits}.

An overview on previous work in this area is postponed to 
Section~\ref{sec:previous-work}, where all required definitions will be
available.

We assume without loss of generality that $n>0$. The following notations will
be used throughout the paper: the set of nonnegative integers is
$\N:=\{0,1,\dots \}$, by $\fractional{x}:=x-\fl x$ we denote the fractional
part of a real number $x$, for a set $A$, $A^+$ is defined as $\bigunion_{n\ge
  1}A^n$, and $\append$ is the concatenation function $\append:A^+\times A\to
A^+$; $(a_0,\dots,a_l)\append a_{l+1}:=(a_0,\dots,a_l,a_{l+1})$.  As usual, the
minimum of the empty set is defined as $\infty$. We write
$\log_q(n):=\log(n)/\log(q)$ for the logarithm to base $q$.  We will use
Iverson's convention as in \cite{Graham-Knuth-Patashnik:1994}, i.~e. for any
expression $\mathit{expr}$, $\cond{\mathit{expr}}=1$ if $\mathit{expr}$ is true
and $=0$ otherwise.



\section{Reduced Representations}\label{sec:reduced-representations}

Let $n>0$ and $q\ge 2$ be fixed. We will describe ``reduction rules'' of the
shape $(\eta_0,\dots,\eta_r)\replaced (\eta'_0,\dots,\eta'_r)$. To apply such a
rule to a representation $\eps$ means to replace the first occurrence (from the
left, i.~e. the least significant digits) of $(\eta_0,\dots,\eta_r)$ in $\eps$
by $(\eta'_0,\dots,\eta'_s)$. Additionally, reduction rules
$(\eta_0,\dots,\eta_r)\replacedend (\eta'_0,\dots,\eta'_s)$ will occur, which
we are only allowed to apply at the end of the representation, i.~e. if
$\eps=(\eps_0,\dots,\eps_{l-r-1}, \eta_0,\dots,\eta_r)$. Note that in the case
of rules at the end, the length of the representation may change. We emphasize
that a reduction rule must be applied at the first occurrence of the pattern.

Furthermore, define $f:R_q(n)\to R_q(n)$ in the following way: Given
$\eps=(\eps_0,\dots,\eps_l)\in R_q(n)$, try the following reduction
rules (in the given order) until $\eps$ first changes and return this result.

\begin{equationenumerate}
\item $(0)\replacedend ()$.
\item\label{rule:eta-groesser-q/2-innen} For $\betrag{\eta_0}> q/2$,
  $\eta_1\in\Z$, and $u:=\ceil{\betrag{\eta_0}/q-1/2}$: $(\eta_0,\eta_1)
  \replaced (\eta_0-uq\sign(\eta_0),\eta_1+u\sign(\eta_0))$.
\item\label{rule:eta-groesser-q+1/2-ende} For $\betrag{\eta_0}>(q+1)/2$
  and $u:=\ceil{\betrag{\eta_0}/q-1/2}$:
  $(\eta_0)\replacedend (\eta_0-uq\sign(\eta_0),u\sign(\eta_0))$.
\item\label{rule:-q-1/2-1-ende} For $2\teiltnicht q$:
  $(-(q-1)/2,1) \replacedend ((q+1)/2)$.
\item\label{rule:-q/2--q/2+1-1-ende} For $2\teilt q$:
  $(-q/2,-q/2+1,1) \replacedend (q/2,q/2)$.
\item\label{rule:q/2-eta-0} For $\eta_0 < 0$ and $2\teilt q$:
  $(q/2, \eta_0)\replaced (-q/2,\eta_0+1)$.
\item\label{rule:-q/2-eta-0} For $\eta_0 >0$ and $2\teilt q$:
  $(-q/2,\eta_0) \replaced (q/2, \eta_0-1)$.
\item\label{rule:q/2-q/2-eta-0} For $\eta_0<q/2$ and $2\teilt q$:
  $(q/2, q/2, \eta_0)\replaced (-q/2, -q/2+1, \eta_0+1)$.
\item\label{rule:-q/2--q/2-eta-0} For $-q/2<\eta_0$ and $2\teilt q$:
  $(-q/2, -q/2, \eta_0) \replaced (q/2, q/2-1, \eta_0-1)$.
\item\label{rule:q/2-q/2-q/2} For $2\teilt q$:
  $(q/2, q/2, q/2) \replacedend (-q/2, -q/2+1, -q/2+1,1)$.
\end{equationenumerate}

We note that $f$ is well defined since all of the above reduction rules indeed
transform representations of $n$ to representations of $n$.

We say that $\eps\in\N^+$ is \emph{reduced} if $f(\eps)=\eps$. This is the case
if and only if the following holds:
\begin{equationenumerate}
\item There are no trailing zeros.
\item $-q/2\le \eps_i\le q/2$ for $0\le i\le l-1$ and $\betrag{\eps_l}\le
  (q+1)/2$.
\item The sequence does not end on $(-(q-1)/2, 1)$ or $(-q/2,-q/2+1,1)$.
\item If $\eps_{i}=q/2$ then $0\le \eps_{i+1}\le q/2-1$ except when $i=l-1$,
  where only $0\le \eps_{i+1}\le q$ is required, or when $i=l$.
\item If $\eps_{i}=-q/2$ then $-q/2+1\le \eps_{i+1}\le 0$ (except when $i=l$).
\end{equationenumerate}

\begin{lemma}\label{le:reduction-terminates}
  Given $\eps\in R_q(n)$. Then the sequence defined by
  $$\eps^{(0)}:=\eps, \qquad \eps^{(i+1)}:=f(\eps^{(i)}) \qquad \text{ for }i\ge 0$$
  stabilizes, i.~e. there is some $m\ge 0$ such that $\eps^{(i)}=\eps^{(m)}$
  for all $i\ge m$. 

  Additionally, $c(\eps^{(i+1)})\le c(\eps^{(i)})$ for $i\ge 0$.
\end{lemma}

\begin{proof}
  We define $\omega:\Z^+\to (\Z\union{\infty})^8$ by
  \begin{align*}
  \eps=(\eps_0,\dots,\eps_l)\mapsto
  \bigl(&c(\eps),\\
    &-\min\{0\le i\le l:\betrag{\eps_i}>q/2\},\\
    &-\min\{0\le i\le l:\betrag{\eps_i}>(q+1)/2\},\\
    &\card\{0\le i\le l:\betrag{\eps_i}=q/2\},\\
    &-\min\{0\le i\le l-1:(\eps_i,\eps_{i+1})=(q/2,q/2)\},\\
    &\min\{1\le i\le l-1: \exists \eta_0<q/2: (\eps_{i-1},\eps_i,\eps_{i+1})=
    (q/2,q/2,\eta_0)\},\\
    &-\min\{0\le i\le l-1:(\eps_i,\eps_{i+1})=(-q/2,-q/2)\},\\
    &\min\{1\le i\le l-1: \exists \eta_0>-q/2: (\eps_{i-1},\eps_i,\eps_{i+1})=
    (-q/2,-q/2,\eta_0)\}\bigr)
  \end{align*}
  and $\prec$ to be the relation on $\Z^+$ defined by
  $$\eps \prec \eps' :\iff \omega(\eps)\lexlt\omega(\eps').$$

  It is straightforward to prove that for all $\eps\in R_q(n)$ 
  \begin{equation}
    \label{eq:f-monoton-fallend}
    f(\eps)=\eps \text{ or } f(\eps)\prec \eps;
  \end{equation}
  we show the most complicate case only, namely the rule
  \eqref{rule:-q/2--q/2-eta-0}.
  
  Let 
  \begin{align*}
    \eps&=(\eps_0,\dots,\eps_{m-1}, -q/2, -q/2, \eta_0,
    \eps_{m+3},\dots,\eps_l),\\
    \eps'&=(\eps_0,\dots,\eps_{m-1}, q/2, q/2-1, \eta_0-1,
    \eps_{m+3},\dots,\eps_l).
  \end{align*}
  Since rule \eqref{rule:-q/2-eta-0} could not be applied (in that case, we
  would not have been allowed to apply \eqref{rule:-q/2--q/2-eta-0}), we have
  $\eta_0\le 0$ and therefore $-q/2\le \eta_0-1 < 0$.
  
  We calculate that $c(\eps')-c(\eps)=-1+\betrag{\eta_0-1}-\betrag{\eta_0}= 0$.
  Since $2\teilt q$ and rules \eqref{rule:eta-groesser-q/2-innen} and
  \eqref{rule:eta-groesser-q+1/2-ende} could not be applied, all
  $\betrag{\eps_i}, \betrag{\eps'_i}\le q/2$ and
  $\omega_2(\eps)=\omega_2(\eps')= \omega_3(\eps)=\omega_3(\eps')=-\infty$.

  We see that  $\omega_4(\eps')\le\omega_4(\eps)$ with equality if and only if
  $\eta_0=-q/2+1$.
  
  We note that $\eps_{m-1}=q/2$ cannot happen (either since $m=0$ or since
  rule~\eqref{rule:q/2-eta-0} would have been applied), therefore, the
  positions of blocks $(q/2,q/2)$ have not been changed, and we obtain
  $\omega_5(\eps')=\omega_5(\eps)$ and $\omega_6(\eps')=\omega_6(\eps)$.
  
  Let $s:=-\omega_7(\eps)$. Obviously $s\le m$. If $s\ge m-1$ then we have
  $-\omega_7(\eps')>s$, otherwise, we have $-\omega_7(\eps')=s$, but
  $\omega_8(\eps)= m+1 >\omega_8(\eps')=m-1$. Therefore,
  \eqref{eq:f-monoton-fallend} is proved for rule \eqref{rule:-q/2--q/2-eta-0}.
  
  Since the maximum length of the occurring representations is bounded by
  $c(\eps^{(0)})$, $\omega(\eps^{(i)})$ lies in the finite set
  $$\{-\infty, -c(\eps^{(0)}), \dots, 0,\dots,c(\eps^{(0)}),\infty\}^8
  $$
  for $i\ge 0$ and there must be an $m\ge 0$ with the required properties.
\end{proof}

\begin{lemma}\label{le:erste-Stelle}
  Let $n, q$ be fixed and $\eps\in R_q(n)$ be reduced.  Let $a:=n\bmod q$ and
  $b:=(n-a)/q \bmod q$.  Then
  $$\eps_0=
  \begin{cases}
    a   & \text{ if $a<q/2$ or ($a=q/2$ and $b<q/2$) or $n\in\{(q+1)/2, q/2+q^2/2\}$},\\
    a-q & \text{ otherwise}.\\
  \end{cases}$$
\end{lemma}

\begin{proof}
  From
  $$a\kongr n \kongr \eps_0\pmod q,$$
  $\betrag{\eps_0}<q$ and rules
  \eqref{rule:eta-groesser-q/2-innen} and \eqref{rule:eta-groesser-q+1/2-ende}
  we obtain that either $\eps_0=a$ or $\eps_0=a-q$.
  
  We note that by rules \eqref{rule:eta-groesser-q/2-innen} and
  \eqref{rule:eta-groesser-q+1/2-ende} and $n>0$ we have $\betrag{\eps_0}\le
  q/2$ except when $l=0$ and $\eps_0=n=(q+1)/2=a$.
  
  Let $a<q/2$. Since $a-q<-q/2$, we get $\eps_0=a$.
  
  Let $a=q/2$ and $b<q/2$. If $\eps_0=a-q=-q/2$, then by rule
  \eqref{rule:-q/2-eta-0} we have $l=0$ (which is impossible since $n>0$) or
  $\eps_1\le 0$. Since $\eps_1\kongr b+1 \pmod q$, this implies
  $\eps_1=b+1-q<-q/2+1$ (since $n>0$, this implies $l\ge 2$) and therefore
  $\eps_1=-q/2$. Rule \eqref{rule:-q/2--q/2-eta-0} leads to a contradiction,
  which yields $\eps_0=a$.

  If $n=(q+1)/2$ and $\eps_0=a-q=-(q-1)/2$, then we obtain
  $\sum_{i=0}^{l-1} \eps_{i+1}q^i=1$. We note that from
  $$q^{l-1}\le \betrag{\eps_l
    q^{l-1}}=\betrag{1-\sum_{i=0}^{l-2}\eps_{i+1}q^i}\le 1+\frac{q}2\cdot
  \frac{q^{l-1}-1}{q-1},
  $$
  we get $l\le1$ (because $2\teiltnicht q$ and therefore $q\ge 3$), which
  implies $l=1$ and $\eps_1=1$. This is a contradiction to rule
  \eqref{rule:-q-1/2-1-ende}, which shows $\eps_0=a$.
  
  Consider now the case $a>q/2$. $\eps_0=a$ yields $l=0$, $\eps_0=n=(q+1)/2$,
  which has been considered above.  Therefore $\eps_0=a-q$.
  
  We turn to the case $a=q/2$ and $b\ge q/2$. If $\eps_0=a=q/2$ then $b\kongr
  \eps_1 \pmod q$. By rule \eqref{rule:q/2-eta-0} we get $\eps_1\ge 0$ which
  implies $\eps_1=b\ge q/2$ and therefore $\eps_1=q/2$. By rules
  \eqref{rule:q/2-q/2-eta-0} and \eqref{rule:q/2-q/2-q/2} this leads to
  $n=q/2+q^2/2.$
  
  Finally, we have to consider $n=q/2+q^2/2$. If $\eps_0=a-q=-q/2$, then we get
  $\sum_{i=0}^{l-1} \eps_{i+1}q^i=q/2+1$, i.~e. $\eps'=(\eps_1,\dots,\eps_l)\in
  R_q(q/2+1)$ and $\eps'$ is reduced. By the proven parts of this lemma, this
  implies $(\eps_1,\dots, \eps_l)=(-q/2+1, 1)$ and therefore
  $\eps=(-q/2,-q/2+1,1)$, which is a contradiction to rule
  \eqref{rule:-q/2--q/2+1-1-ende}.
\end{proof}


\begin{algorithm}
  \caption{Computation of the reduced minimal representation of $n$}
  \label{alg:pseudo-cheub}

  \begin{algorithmic}
    \REQUIRE $n>0, q\ge 2$ integers.
    \ENSURE $\eps\in R_q(n)$ such that $c(\eps)=\min \{c(\eps'): \eps'\in
    R_q(n)\}$ and $\eps$ is reduced.
   
    \STATE $\eps\assign()$
    \STATE $m \assign n$
    
    \WHILE{$m>0$}
       \STATE $a\assign (m \bmod q)$.
       \IF{\NOT($a<q/2$ \OR ($a=q/2$ \AND $\fractional{m/q^2}< 1/2$) \OR $m=(q+1)/2$ \OR
       $m=q/2+q^2/2$)}
         \STATE $a\assign a-q$
       \ENDIF
       \STATE $m\assign (m-a)/q$
       \STATE $\eps\assign\eps\append a$
    \ENDWHILE
  \end{algorithmic}
\end{algorithm}

\begin{theorem}\label{th:unique-invariant-minimal-representation}
  Let $q\ge 2$ and $n>0$ be integers. Then there is a unique reduced
  representation $\eps\in R_q(n)$; this representation is minimal with respect
  to \eqref{eq:cost-definition}, and it can be computed by
  Algorithm~\ref{alg:pseudo-cheub}.
\end{theorem}

\begin{proof}
  The existence follows from Lemma~\ref{le:reduction-terminates} applied to any
  representation of $n$.
  
  Let $\eps=(\eps_0,\dots,\eps_l)\in R_q(n)$ be a reduced representation.  By
  Lemma~\ref{le:erste-Stelle}, $\eps_0$ is uniquely given in terms of $n$.
  Additionally, $\eps':=(\eps_1,\dots,\eps_l)\in R_q((n-\eps_0)/q)$ is reduced.
  By iterating Lemma~\ref{le:erste-Stelle} we see that all digits are uniquely
  determined by $n$, which proves uniqueness.
 
  Since $\fractional{n/q^2}=(a+bq)/q^2$ (where $a$ and $b$ are defined as in
  Lemma~\ref{le:erste-Stelle}), we obtain that $\fractional{n/q^2} <1/2$ if and
  only if $b<q/2$ (if $2\teilt q$; otherwise, we never have to consider a digit
  $q/2$); and therefore, Algorithm~\ref{alg:pseudo-cheub} computes the reduced
  representation of $n$.
  
  Let $\eps'\in R_q(n)$ be a representation of $n$ with minimum costs.
  Construct the sequence ${\eps'}^{(i)}$ as in
  Lemma~\ref{le:reduction-terminates}. By this lemma, there is some $m\ge 0$
  such that $f^m(\eps')=\eps$ and $c(\eps)\le c(\eps')$. Therefore, $\eps$ has
  minimum costs.
\end{proof}

\section{Relaxed Reduced
  Representations}\label{sec:relaxed-reduced-representations}

If we are looking for minimal representations with respect to
\eqref{eq:relaxed-cost-definition}, the main ideas of the previous section
remain the same, so we will only sketch the differences.

Since the length of a representation is not important, we may think of a
representation as of an infinite sequence of integers with finitely many
non-zero entries. This implies that we do not have to consider the reduction
rules which could only be applied at the end.

Therefore, we define $f':R_q(n)\to R_q(n)$ by the reduction rules (as in the
previous section, we have to apply the first rule which matches)
\eqref{rule:eta-groesser-q/2-innen}, \eqref{rule:q/2-eta-0},
\eqref{rule:-q/2-eta-0}, \eqref{rule:q/2-q/2-eta-0} and
\eqref{rule:-q/2--q/2-eta-0}. A representation $\eps$ is called \emph{relaxed
  reduced}, if $f'(\eps)=\eps$ and (if written as a finite sequence) $\eps$ has
no trailing zeros. It is easily seen that $\eps$ is relaxed reduced if and only
if the following conditions are satisfied:

\begin{equationenumerate}
\item There are no trailing zeros.
\item\label{eq:rrch-betrag} $-q/2\le \eps_i\le q/2$ for $i\ge 0$.
\item\label{eq:rrch-q/2} If $\eps_{i}=q/2$ then $0\le \eps_{i+1}\le q/2-1$.
\item\label{eq:rrch--q/2} If $\eps_{i}=-q/2$ then $-q/2+1\le \eps_{i+1}\le 0$.
\end{equationenumerate}

In the proof of the analogue of Lemma~\ref{le:reduction-terminates}, the length
of the representations is not bounded a priori by $c'(\eps_0)$.  However, if
the sequence does not terminate, then there are some $M$ and $i_0\in\N$ such
that $c'(\eps^{(i)})=M$ for all $i\ge i_0$. We note that there cannot be any
$j$ such that $\betrag[big]{\eps^{(i)}_j}\ge q$ for $i\ge i_0$ since we could
apply rule~\eqref{rule:eta-groesser-q/2-innen} and the costs would strictly
decrease in this case. Therefore, let $l_i:=\max\{j\in \N: \eps^{(i)}_j\neq
0\}$, and we get
\begin{equation*}
  q^{l_i}\le n+(q-1)\sum_{j={l_i}-M-1}^{{l_i}-1} q^j=n+ q^{l_i} - q^{l_i-M+1}.
\end{equation*}
This implies $l\le M-1+\log_q n$, i.~e. $\omega(\eps^{(i)})$ lies in the finite
set
\begin{equation*}
  \{-\infty, -c(\eps^{(0)})-\fl{\log_q\betrag{n}}+1, \dots, 0,\dots,
  c(\eps^{(0)})+\fl{\log_q\betrag{n}}-1,\infty\}^8
\end{equation*}
for $i\ge i_0$, which leads to a contradiction, and the analogue of
Lemma~\ref{le:reduction-terminates} is proved.

The analogue of Lemma~\ref{le:erste-Stelle} is
\begin{lemma}\label{le:relaxed-erste-Stelle}
  Let $n, q$ be fixed and $\eps\in R_q(n)$ be relaxed reduced.
  Let $a:=n\bmod q$ and $b:=(n-a)/q \bmod q$.
  Then 
  $$\eps_0=
  \begin{cases}
    a   & \text{ if $a<q/2$ or ($a=q/2$ and $b<q/2$), }\\
    a-q & \text{ otherwise, i.~e. if $a>q/2$ or ($a=q/2$ and $b\ge q/2$).}
  \end{cases}$$
\end{lemma}

\begin{algorithm}
  \caption{Computation of the relaxed reduced minimal representation of $n$}
  \label{alg:relaxed-pseudo-cheub}

  \begin{algorithmic}
    \REQUIRE $n>0, q\ge 2$ integers.
    \ENSURE $\eps\in R_q(n)$ such that $c'(\eps)=\min \{c'(\eps'): \eps'\in
    R_q(n)\}$ and $\eps$ is relaxed reduced.
   
    \STATE $\eps\assign()$
    \STATE $m \assign n$
    
    \WHILE{$m>0$}
       \STATE $a\assign (m \bmod q)$.
       \IF{$a>q/2$ \OR ($a=q/2$ \AND $\fractional{m/q^2}\ge 1/2$)}
         \STATE $a\assign a-q$
       \ENDIF
       \STATE $m\assign (m-a)/q$
       \STATE $\eps\assign\eps\append a$
    \ENDWHILE
  \end{algorithmic}
\end{algorithm}

This leads to the following result:
\begin{theorem}\label{th:unique-relaxed-invariant-minimal-representation}
  Let $q\ge 2$ and $n>0$ be integers. Then there is a unique relaxed reduced
  representation $\eps\in R_q(n)$; this representation is minimal with respect
  to \eqref{eq:relaxed-cost-definition}, and it can be computed by
  Algorithm~\ref{alg:relaxed-pseudo-cheub}.
\end{theorem}

Finally, we have to clarify the relation between the relaxed reduced and the
reduced representations:

\begin{theorem}\label{th:relaxed-versus-non-relaxed}
  Let $q\ge 2$ and $n>0$ be integers and $\eps=(\eps_0,\dots,\eps_l)$ and
  $\eps'=(\eps'_0,\dots,\eps'_{l'})$ the reduced and the relaxed reduced
  representation of $n$, respectively. 

  Then we have the following relations
  \begin{align}
    \eps&=
    \begin{cases}
      (\eps'_0,\dots,\eps_{l'-2}, (q+1)/2) & \text{if
      $(\eps'_{l'-1},\eps'_{l'})=(-(q-1)/2,1)$},\\
      (\eps'_0,\dots,\eps_{l'-3}, q/2, q/2) & \text{if
      $(\eps'_{l'-2},\eps'_{l'-1},\eps'_{l'})=(-q/2, -q/2+1,1)$},\\
      \eps'&\text{otherwise},
    \end{cases}\label{eq:from-relaxed-to-non-relaxed}\\
    \eps'&=
    \begin{cases}
      (\eps_0,\dots,\eps_{l-1}, -(q-1)/2, 1 ) & \text{if
      $\eps_{l}=(q+1)/2$},\\
      (\eps_0,\dots,\eps_{l-2}, -q/2, -q/2+1,1) & \text{if
      $(\eps_{l-1},\eps_{l})=(q/2, q/2)$},\\
      \eps&\text{otherwise.}
    \end{cases}\label{eq:from-non-relaxed-to-relaxed}
  \end{align}
\end{theorem}

\begin{proof}
  It is obvious that $f(\eps')=\eps'$ unless $\eps'$ corresponds to one of the
  two exceptional cases in \eqref{eq:from-relaxed-to-non-relaxed}, in which
  $f(\eps')$ is the expression on the right hand side of
  \eqref{eq:from-relaxed-to-non-relaxed}. To see that this expression is indeed
  reduced, we note that the only rules which might apply are
  \eqref{rule:q/2-q/2-q/2} and \eqref{rule:-q/2-eta-0}, but this cannot be the case
  since $\eps'$ was relaxed reduced which implies that $\eps'_{l'-3}\notin\{\pm
  q/2\}$. The other direction follows easily.
\end{proof}




\section{Formula for Odd $q$}\label{sec:Odd-q}

\begin{theorem}\label{th:q-odd:typabsolut-aus-q-adisch}
  Let $q\ge 3$ be odd and $n$ be a positive integer. Let
  $$\eps_r:=b_q^{(r)}(2n)-b_q^{(r)}(n), \qquad r\ge 0,$$
  where $b_q^{(r)}(n)$ is   
  the $r$-th digit of the ``usual'' $q$-adic expansion of $n$, i.~e. 
  $$b_q^{(r)}(n)=\fl{\frac{n}{q^r}}-q\fl{\frac{n}{q^{r+1}}},$$ 
  and $l:=\max\{r\ge 0: \eps_r\neq 0\}$.
  Then $\eps=(\eps_0,\dots,\eps_l)$
  is the relaxed reduced minimal representation.
\end{theorem}

\begin{proof}
  By definition, we have
  \begin{align*}
    \eps_r=b_q^{(r)}(2n)-b_q^{(r)}(n) &= \fl{\frac{2n}{q^r}}-q\fl{\frac{2n}{q^{r+1}}}
- \fl{\frac{n}{q^r}}+q\fl{\frac{n}{q^{r+1}}} \\
&= \fl{2q\frac{n}{q^{r+1}}}-q\fl{2\frac{n}{q^{r+1}}}
- \fl{q\frac{n}{q^{r+1}}}+q\fl{\frac{n}{q^{r+1}}}.
  \end{align*}
  For any positive integer $a$ and any real number $x$ the relation
  \begin{equation}
    \label{eq:floor-ax-expansion}
    \fl{ax}=\sum_{i=0}^{a-1}\fl{x+\frac ia}
  \end{equation}
  is well-known (see for instance \cite[3.26]{Graham-Knuth-Patashnik:1994}).
  Setting $x:=n/q^{r+1}$ we obtain
  \begin{align*}
    \eps_r &= \sum_{l=0}^{2q-1} \fl{x+\frac l{2q}}
    - q\left(\fl x+\fl{x+\frac12}\right) -
    \sum_{l=0}^{q-1}\fl{x+\frac lq} + q\fl x \\
    &=-(q-1)\fl{x+\frac12}+ 
    \sum_{\substack{m=0\\m\neq (q-1)/2}}^{q-1} \fl{x+\frac{2m+1}{2q}} .
  \end{align*}

  Let $0\le j\le q$ such that 
  $$\frac{2j-1}{2q}\le \{x\} < \frac{2j+1}{2q}.$$
  Then 
  \begin{align*}
    \sum_{m=0}^{q-1} \fl{x+\frac{2m+1}{2q}}&= q\fl x+j\\
    q\fl{x+\frac12}&=q\fl x + q\cond{j\ge \frac{q+1}2},
  \end{align*}
  which shows that
  \begin{equation}
    \label{eq:q-odd-range-eps-r}
    -\frac{q-1}2\le \eps_r \le \frac{q-1}2.
  \end{equation}
  
  By construction, $\eps_r\in R_q(n)$. By \eqref{eq:rrch-betrag} and
  \eqref{eq:q-odd-range-eps-r} we see that $\eps_r$ is the relaxed reduced
  representation of $n$.
\end{proof}



\section{Formula for Even $q$}\label{sec:formula-even-q}

We derive a formula for the digits of the relaxed reduced expansion (which
yields a formula for the reduced expansion by
Theorem~\ref{th:relaxed-versus-non-relaxed}), which will enable us to study the
distribution of the digits in the next section.

\begin{theorem}
  Let $q\ge 2$ be even.
  For $r\ge 0$ define
  \begin{equation}\label{eq:q-even-formula-explicit}
  \begin{aligned}
    \eps_r:=\sum_{i=0}^{q/2-1}\Biggl(
    \sum_{j=0}^{q/2-1} &\fl {\frac{n}{q^{r+2}}+ \frac{1+\frac
        q2+(q+1)(iq+j)}{q^2(q+1)}}\\
    -(q-1)&\fl{\frac{n}{q^{r+2}}+\frac{\frac{q}2+(q+1)(iq+q/2)}{q^2(q+1)}}\\
    +\sum_{j=q/2+1}^{q-1} &\fl{\frac{n}{q^{r+2}}+\frac{\frac{q}2+(q+1)(iq+j)}{q^2(q+1)}}\Biggr)\\
    +\sum_{i=q/2}^{q-1}\Biggl(
    \sum_{j=0}^{q/2-2} &\fl {\frac{n}{q^{r+2}}+ \frac{1+\frac
        q2+(q+1)(iq+j)}{q^2(q+1)}}\\
    -(q-1)&\fl{\frac{n}{q^{r+2}}+\frac{1+\frac{q}2+(q+1)(iq+q/2-1)}{q^2(q+1)}}\\
    +\sum_{j=q/2}^{q-1} &\fl{\frac{n}{q^{r+2}}+\frac{\frac{q}2+(q+1)(iq+j)}{q^2(q+1)}}\Biggr).
  \end{aligned}
  \end{equation}
  Let $l:=\max\{r\ge 0: \eps_r\neq 0\}$. 
  Then $\eps=(\eps_0,\dots,\eps_l)\in R_q(n)$
  is the relaxed reduced minimal representation.
\end{theorem}

\begin{example}
  For $q=2$, \eqref{eq:q-even-formula-explicit} is 
  \begin{equation}\label{eq:q-even-formula-q-2}
    \eps_r=\fl{\frac{n}{2^{r+2}}+\frac56}-
    \fl{\frac{n}{2^{r+2}}+\frac46}-
    \fl{\frac{n}{2^{r+2}}+\frac26}+
    \fl{\frac{n}{2^{r+2}}+\frac16},
  \end{equation}
  which is the formula also obtained in
  \cite{Prodinger:2000:binary-representations--1-0-1} (cf.\ Section~\ref{sec:previous-work}).
\end{example}

\begin{example}
  It is perhaps a good idea to explain what the formula
  \eqref{eq:q-even-formula-explicit} \emph{does}, which we will do for the instance
  $q=6$:

  \begin{align*}
    \eps_r=&+\fl{y+\frac{248}{252}}
    +\fl{y+\frac{241}{252}}
    +\fl{y+\frac{234}{252}}
    -5\fl{y+\frac{228}{252}}
    +\fl{y+\frac{221}{252}}
    +\fl{y+\frac{214}{252}}\\&
    +\fl{y+\frac{206}{252}}
    +\fl{y+\frac{199}{252}}
    +\fl{y+\frac{192}{252}}
    -5\fl{y+\frac{186}{252}}
    +\fl{y+\frac{179}{252}}
    +\fl{y+\frac{172}{252}}\\&
    +\fl{y+\frac{164}{252}}
    +\fl{y+\frac{157}{252}}
    +\fl{y+\frac{150}{252}}
    -5\fl{y+\frac{144}{252}}
    +\fl{y+\frac{137}{252}}
    +\fl{y+\frac{130}{252}}\\&
    +\fl{y+\frac{122}{252}}
    +\fl{y+\frac{115}{252}}
    -5\fl{y+\frac{108}{252}}
    +\fl{y+\frac{102}{252}}
    +\fl{y+\frac{95}{252}}
    +\fl{y+\frac{88}{252}}\\&
    +\fl{y+\frac{80}{252}}
    +\fl{y+\frac{73}{252}}
    -5\fl{y+\frac{66}{252}}
    +\fl{y+\frac{60}{252}}
    +\fl{y+\frac{53}{252}}
    +\fl{y+\frac{46}{252}}\\&
    +\fl{y+\frac{38}{252}}
    +\fl{y+\frac{31}{252}}
    -5\fl{y+\frac{24}{252}}
    +\fl{y+\frac{18}{252}}
    +\fl{y+\frac{11}{252}}
    +\fl{y+\frac{4}{252}},
  \end{align*}
  where $y=n/6^{r+2}$.
  
  
  Let us think about $y$ as a real variable.  It is plain to see that the
  expression with $q^2$ terms is periodic in $y$. For $y=0$ it is $0$; when $y$
  reaches $\frac{4}{252}$, the first term changes to $1$; when $y$ reaches
  $\frac{11}{252}$, the second term also changes to $1$, and so on.
  Accordingly, the digit changes from $0$ to $1$, then to $2$, then to $3$,
  then to $-2,-1,0$. That describes the first line of terms. This patterns
  repeats twice, but then in the second half the general pattern switches from
  $0,1,2,3,-2,-1$ to $0,1,2,-3,-2,-1$. The digits $0,1,2,3,-2,-1$ are not
  symmetric around $0$, and $0,1,2,-3,-2,-1$ are not, either. However, in
  combination, both coming with ``probability'' $\frac12$, the distribution of
  the digits becomes symmetric.
\end{example}

\begin{proof}
  We rewrite \eqref{eq:q-even-formula-explicit} as
  \begin{equation}
    \label{eq:q-even-formula-short}
    \eps_r=\sum_{i=0}^{q-1}\sum_{j=0}^{q-1}
    \fl{\frac{n}{q^{r+2}}+\frac{j}{q^2}+\frac{\cond{j< q/2}+q/2}{q^2(q+1)}+ \frac iq}
    -q \sum_{i=0}^{q-1}\fl{\frac{n}{q^{r+2}}+\frac iq +\frac{\cond{i<q/2}+q/2}{q(q+1)}}.
  \end{equation}
  Interchanging the order of summation in the first part, using
  \eqref{eq:floor-ax-expansion}, renaming $i$ to $j$ in the second part and
  collecting the two resulting sums, 
  we get
  \begin{equation*}
    \eps_r=\sum_{j=0}^{q-1}\biggl(
    \fl{\frac{n}{q^{r+1}}+\frac{j}{q}+\frac{\cond{j< q/2}+q/2}{q(q+1)}}
    -q \fl{\frac{n}{q^{r+2}}+\frac jq +\frac{\cond{j<q/2}+q/2}{q(q+1)}}\biggr).
  \end{equation*}
  Therefore, we calculate that
  \begin{equation}\label{eq:q-even-formula-proto-representation}
    \sum_{r=0}^{\infty} \eps_r q^r=\sum_{j=0}^{q-1}
    \fl{\frac{n}{q}+\frac{j}{q}+\frac{\cond{j< q/2}+q/2}{q(q+1)}}.
  \end{equation}
  We write $n=r+sq$ for $0\le r<q$ and observe that for an integer $0\le m<2q$
  and for $\sigma\in\{0,1\}$
  \begin{equation*}
    \fl{\frac{m}{q}+\frac{\sigma+q/2}{q(q+1)}}=\cond{m\ge q}.
  \end{equation*}
  Evaluating \eqref{eq:q-even-formula-proto-representation} in this way we
  obtain
  \begin{equation}\label{eq:q-even-formula-representation}
    \sum_{r=0}^{\infty} \eps_r q^r=\sum_{j=0}^{q-1}\left(
    s+\cond{j\ge q-r}\right)=n,
  \end{equation}
  and we proved that $\eps=(\eps_0,\dots,\eps_l)\in R_q(n)$ is indeed a
  representation of $n$.

  In order to investigate further properties of $\eps$ we fix some $r\ge 0$,
  write $x:=\fractional{n/q^{r+2}}$ and define
  \begin{equation}\label{eq:q-even-xi-h-definition}
    \xi_{i,j}:=\frac{\cond{j<q/2}+q/2+(q+1)(iq+j)}{q^2(q+1)} \text{\qquad and
    \qquad} h_{i,j}:=\fl{x+\xi_{i,j}}
  \end{equation}
  for $i,j\in\{0,\dots,q-1\}$.
  We note that for $(i,j)\lexlt (i',j')$ we have $0<\xi_{i,j}<\xi_{i',j'}<1$ and
  rewrite \eqref{eq:q-even-formula-explicit} as
  \begin{equation*}
    \begin{array}{@{}>{\displaystyle}r*{17}{@{\;}>{\displaystyle}l}}
      \eps_r&=&\sum_{i=0}^{\frac q2-1}
      &h_{i,0}&+&\dots&+&h_{i,\frac q2-2}&+&h_{i,\frac q2-1}
      &-(q-1)&h_{i,\frac q2}&+&h_{i,\frac q2+1}&+&\dots&+&h_{i,q-1}\\
    &+&\sum_{i=\frac q2}^{q-1}
      &h_{i,0}&+&\dots&+&h_{i,\frac q2-2}&-(q-1)&h_{i,\frac q2-1}
      &+&h_{i,\frac q2}&+&h_{i,\frac q2+1}&+&\dots&+&h_{i,q-1}.
    \end{array}
  \end{equation*}
  
  Choose $(i_0,j_0)$ lexicographically minimal such that $x+\xi_{i_0,j_0}\ge 1$
  --- if $x+\xi_{q-1,q-1}<1$ then we set $(i_0,j_0):=(\infty,\infty)$ ---,
  which implies that $h_{i,j}=\cond{(i,j)\lexge (i_0,j_0)}$ and therefore
  \begin{multline}\label{eq:q-even-formula-0-1-representation}
    \eps_r=\\\left\{
      \begin{array}{@{}r*{14}{@{\;}l}l}
        h_{i_0,0}&+&\dots&+&h_{i_0,\frac q2-2}&+&h_{i_0,\frac q2-1}
        &-(q-1)&h_{i_0,\frac q2}&+&h_{i_0,\frac q2+1}&+&\dots&+&h_{i_0,q-1}&
        \text{ if $i_0<\frac q2$}\\
        h_{i_0,0}&+&\dots&+&h_{i_0,\frac q2-2}&-(q-1)&h_{i_0,\frac q2-1}
        &+&h_{i_0,\frac q2}&+&h_{i_0,\frac q2+1}&+&\dots&+&h_{i_0,q-1}& \text{ if
          $i_0\ge \frac q2$}\\
        0&&&&&&&&&&&&&&&\text{ if $i_0=\infty$}.
      \end{array}\right.
  \end{multline}

  From \eqref{eq:q-even-formula-0-1-representation} we see that
  $\betrag{\eps_r}\le q/2$ and that 
  \begin{equation}
    \label{eq:q-even-eps-r-q-2-i-0-j-0-connection}
    \begin{aligned}
      \eps_r&=q/2 & &\iff & j_0&=q/2 \text { and } i_0 \ge q/2\\
      \eps_r&=-q/2& &\iff & j_0&=q/2 \text { and } i_0 < q/2.
    \end{aligned}
  \end{equation}
  
  Assume $j_0=q/2$. By definition of $(i_0,j_0)$ and by
  \eqref{eq:q-even-xi-h-definition} this implies that
  \begin{equation*}
    \fl{\frac{n}{q^{2+r}}}+1-\frac{i_0}q-\frac{q+2}{2q(q+1)}
    \le \frac{n}{q^{2+r}}<
    \fl{\frac{n}{q^{2+r}}}+1-\frac{i_0}q-\frac{1}{2(q+1)}.
  \end{equation*}
  Dividing by $q$, denoting $x':=\fractional{n/q^{3+r}}$ and 
  $a_{r+2}:=\fl{n/q^{2+r}}-q\fl{n/q^{3+r}}$ --- we remark that 
  $0\le a_{r+2}<q$ ---, we obtain
  \begin{equation}\label{eq:q-even-x-prime-abschrankung}
    \frac{a_{r+2}+1}{q}-\frac{i_0}{q^2}-\frac{q+2}{2q^2(q+1)}
    \le x' <
    \frac{a_{r+2}+1}{q}-\frac{i_0}{q^2}-\frac{1}{2q(q+1)}.
  \end{equation}
  
  Define
  \begin{equation}\label{eq:q-even-i-1-j-1-choice}
    (i_1,j_1):=
    \begin{cases}
      (q-1-a_{r+2}, i_0+1) & \text{ if $q/2\le i_0 < q-1$}\\
      (q-a_{r+2},0) & \text{ if $i_0=q-1$ and $a_{r+2}\neq 0$}\\
      (\infty, \infty) & \text{ if $i_0=q-1$ and $a_{r+2}=0$}\\
      (q-1-a_{r+2},i_0) & \text{ if $0\le i_0<q/2$}.
    \end{cases}
  \end{equation}
  Using \eqref{eq:q-even-x-prime-abschrankung} we check that in all cases, $(i_1,j_1)$ is
  lexicographically minimal such that $x'+\xi_{i_1,j_1}\ge 1$. From
  \eqref{eq:q-even-eps-r-q-2-i-0-j-0-connection},
  \eqref{eq:q-even-i-1-j-1-choice}, and
  \eqref{eq:q-even-formula-0-1-representation}
  we can deduce that
  \begin{equation}
    \label{eq:q-even-eps-r-eps-r+1-connection}
    \begin{aligned}
      \eps_r&=q/2 &&\Longrightarrow & \eps_{r+1} &\in \{0,\dots,q/2-1\}\\
      \eps_r&=-q/2 &&\Longrightarrow & \eps_{r+1} &\in \{-q/2+1,\dots, 0\}.
    \end{aligned}
  \end{equation}
  
  From the fact that $\betrag{\eps_i}\le q/2$,
  \eqref{eq:q-even-eps-r-eps-r+1-connection}, \eqref{eq:rrch-betrag},
  \eqref{eq:rrch-q/2}, and \eqref{eq:rrch--q/2}, we conclude that $\eps$ is indeed
  the relaxed reduced expansion.
\end{proof}



\section{Counting Digits in the Minimal Representations}\label{sec:counting-digits}

We are interested  to count how often a given digit $i$ occurs in the relaxed
reduced expansion
among the numbers $1$, $\dots$, $n$; call that
$\#_i(n)$.  By Theorem~\ref{th:relaxed-versus-non-relaxed} the corresponding
values for the reduced expansion will differ by at most $2n$, which will
not appear in the main term of the asymptotic formula anyway.

In the case $q$ odd, 
the reduced representation is actually the $(q,d)$ representation,
with $d=-\frac{q-1}{2}$, and digits $d,d+1,\dots,d+q-1$.
Digit counting in this representation is well known, see
\cite{Kirschenhofer-Prodinger:1984}. Every digit occurs with the same frequency 
$\frac{1}{q}$, and
\begin{equation}\label{eq:count-odd-digit-count}
\#_i(n)=\frac{1}{q}n\log_qn+\mathcal{O}(n).
\end{equation}
Actually, more is known about the error term. It can
be made fully explicit and is basically given by $n$ times
a periodic function in $\log_qn$. Here, we don't bother to
compute the periodic functions in detail. 

Summing \eqref{eq:count-odd-digit-count}, (multiplied by $\betrag i$), over all
possible digits $i$, we get the average value of $c'(\eps)$. It is
\begin{equation*}   
\left(\frac{q}{4}-\frac{1}{4q}\right)\log_qn+\mathcal{O}(1);
\end{equation*}     
the constant is computed via
\begin{equation*}   
2\sum_{i=1}^{(q-1)/2}i\frac{1}{q}.
\end{equation*}

In the instance $q$ even, things are a bit more complicated, but fortunately
not by much. The formula \eqref{eq:q-even-formula-explicit} tells us that digit
$0$ occurs with frequency $\frac{q+2}{q(q+1)}$, digits $\pm1,\dots, \pm \frac
q2-1$ with frequency $\frac{1}{q}$, digits $\pm\frac{q}{2}$ each with frequency
$\frac{1}{2(q+1)}$.  So we see that digit $0$ appears a bit more often than the
other digits, and the digits $\pm\frac{q}{2}$ (combined) appear a bit less
often than the other digits. In terms of costs, this is fortunate. Anyway, it
leads to
\begin{align*}
\#_0(n)&=\frac{q+2}{q(q+1)}n\log_qn+\mathcal{O}(n),\\
\#_i(n)&=\frac{1}{q}n\log_qn+\mathcal{O}(n),
&&\text{for $i= \pm1,\dots, \pm \frac q2-1$},\\
\#_i(n)&=\frac{1}{2(q+1)}n\log_qn+\mathcal{O}(n),
&&\text{for $i=\pm \frac q2$}.\\
\end{align*}

Again, summing this, (multiplied by $\betrag i$), over all possible digits $i$, we get the
average value of $\sum|\eps_i|$:

\begin{equation*}   
\left(\frac{q}{4}-\frac{1}{2(q+1)}\right)\log_qn+\mathcal{O}(1).
\end{equation*}     
The computation of the constant is done via
\begin{equation*}   
2\sum_{i=1}^{q/2-1}i\frac{1}{q}+2\frac{q}{2}\frac{1}{2(q+1)}.
\end{equation*}

The average length of the representation is
given by $\log_qn+\mathcal{O}(1)$. 

We sum up these results in the following theorem:

\begin{theorem}
  Let $q\ge 2$ and $n\ge 1$. Then the average costs $c(\eps)$ of the reduced expansions of the
  integers $1,\dots,n$ are
  \begin{align*}
    \left(1+\frac q4 - \frac{1}{2(q+1)}\right)&\log_q n + \mathcal{O}(1)&&\text{if
    $q$ is even},\\
    \left(1+\frac q4 - \frac{1}{4q}\right)&\log_q n + \mathcal{O}(1)&&\text{if
    $q$ is odd}.
  \end{align*}
\end{theorem}



\section{Previous Work}
\label{sec:previous-work}
We start our overview on related papers with the relaxed reduced expansion for
$q=2$. In this case, \eqref{eq:rrch-betrag}, \eqref{eq:rrch-q/2}, and
\eqref{eq:rrch--q/2} are clearly equivalent to $\eps_i\in\{0, \pm 1\}$ and
$\eps_i\eps_{i+1}=0$. This means that for $q=2$ our relaxed reduced expansion
is the so-called ``non-adjacent-form'' (NAF) or ``sparse signed digit
representation'' or ``balanced binary representation'' or ``Paul
representation'' (cf.\ G\"untzer and Paul~\cite{Guentzer-Paul:1987}) which has
been studied --- at least partly independently --- by several authors; we refer
to \cite[IV.2.4]{Blake-Seroussi-Smart:1999} and \cite{Gordon:1998} for some
references. It goes back at least to Reitwiesner \cite{Reitwiesner:1960}, who
proved existence and uniqueness of a NAF and that it has minimum $c'$. Jedwab
and Mitchell~\cite{Jedwab-Mitchell:1989} describe an algorithm which computes
the NAF from every redundant binary expansion with digits $0,\pm 1$.

Morain and Olivos~\cite{Morain-Olivos:1990} first applied the idea to elliptic
curves as sketched in the introduction and empirically found two algorithms,
which yield good results. Actually, the second of these algorithms leads
exactly to 
the NAF, therefore, Morain and Olivos reach the minimum $c'$ (and by
Theorem~\ref{th:relaxed-versus-non-relaxed} the minimum $c$ by up to one). They
give the main term of the expected costs (as in our calculations in
Section~\ref{sec:counting-digits}), whereas Thuswaldner~\cite{Thuswaldner:1999}
gives a further asymptotic term. Further properties of the NAF have been
described by the second author in \cite{Prodinger:2000:binary-representations--1-0-1}.

Demetrovics, Peth\H o, and R\'onyai~\cite{Demetrovics-Pethoe-Ronyai:1999} take
up Morain and Olivos' motivation and consider $c$ for $q=2$. They translate the
minimization problem into an infinite graph where minimal expansions correspond
to shortest paths and apply Dijkstra's algorithm to the solution of the
problem. This has been generalized to general $q$ by the first author in
\cite{Heuberger:1999:digitopt}, and it was proved that there exists a minimal
expansion such that $\betrag{\eps_i}\le q/2$, which characterizes the case of
odd $q$ almost completely. It is worth noting that \cite[Algorithm
1]{Heuberger:1999:digitopt} is not guaranteed to yield an expansion with digits
$\betrag{\eps_i}\le q/2$ because the choice between two paths of equal length
leading to the same vertex is made arbitrarily. If expansions with small digits
are preferred, then the algorithm yields the reduced representation of our
Algorithm~\ref{alg:pseudo-cheub}.  Of course, both algorithms need $O(\log_q
n)$ time, computational experiments show that Algorithm~\ref{alg:pseudo-cheub}
is faster by a factor of $3$.


Another generalization of the non-adjacent-form to arbitrary bases is described in
Clark and Liang~\cite{Clark-Liang:1973}. It is unique,  minimizes $c''(\eps):=\card\{i: \eps_i\neq 0\}$ and
can be computed from the usual $q$-adic expansions of $(q+1)/q$ and $1/q$, similarly to
our Theorem~\ref{th:q-odd:typabsolut-aus-q-adisch}. In the case $q=2$, this
property goes back to Chang and Tsao-Wu~\cite{Chang-Tsao-Wu:1968}. 

The generalized NAF (GNAF) and our reduced expansions were designed for different cost
functions, however, it may be instructive to compare how the two expansions 
behave with respect to both cost functions. To this aim, we calculate an
explicit formula for the $r$-th digit of the GNAF as we did it for the reduced
expansion in Section~\ref{sec:Odd-q} and we follow the lines of
Section~\ref{sec:counting-digits}. The result is shown in
Table~\ref{tab:performance-comparison}.

\begin{table}[htbp]
  \begin{center}
    \begin{tabular}{@{}l|*{2}{|>{$\displaystyle}l<{$}}@{}}
      Expansion& \text{Expected } c'(\eps) & \text{Expected }   c''(\eps)\\ \hline\hline
      Clark and Liang 
      &\frac{q-1}{3} \log_q n + \mathcal{O}(1) 
      & \left(1- \frac{2}{q+1}\right)\log_q n + \mathcal{O}(1)\\ \hline
%
      Relaxed Reduced, even $q$
      &\left(\frac q4-\frac{1}{2(q+1)}\right) \log_q n + \mathcal{O}(1) 
      & \left(1- \frac{q+2}{q(q+1)}\right)\log_q n +  \mathcal{O}(1)\\ \hline
%
      Relaxed Reduced, odd  $q$
      &\left(\frac q4-\frac{1}{4q}\right) \log_q n + \mathcal{O}(1) 
      & \left(1-\frac{1}{q}\right)\log_q n +  \mathcal{O}(1)
    \end{tabular}
    \caption{Comparison of the GNAF and the relaxed reduced expansion}
    \label{tab:performance-comparison}
  \end{center}
\end{table}

% \bibliography{../../numth}
% \bibliographystyle{amsplain}

\begin{thebibliography}{10}

\bibitem{Blake-Seroussi-Smart:1999}
I.~Blake, G.~Seroussi, and N.~Smart, \emph{Elliptic curves in cryptography},
  London Mathematical Society Lecture Note Series, vol. 265, Cambridge
  University Press, 1999.

\bibitem{Chang-Tsao-Wu:1968}
S.~H. Chang and N.~Tsao-Wu, \emph{Distance and structure of cyclic arithmetic
  codes}, Proc. {H}awaii International Conference on System Sciences, vol.~1,
  1968, pp.~463--466.

\bibitem{Clark-Liang:1973}
W.~Edwin Clark and J.~J. Liang, \emph{On arithmetic weight for a general radix
  representation of integers}, IEEE Trans. Information Theory \textbf{IT-19}
  (1973), 823--826.

\bibitem{Coron:1999}
J.-S. Coron, \emph{Resistance against differential power analysis for elliptic
  curve cryptosystems}, Workshop on Cryptographic Hardware and Embedded Systems
  (\c{C}. Ko\c{c} and Ch. Paar, eds.), Lecture Notes in Computer Science, vol.
  1717, Springer, 1999, pp.~292--302.

\bibitem{Demetrovics-Pethoe-Ronyai:1999}
J.~Demetrovics, A.~Peth\H{o}, and L.~R\'onyai, \emph{On $\pm1$-representations
  of integers}, Acta Cybernet. \textbf{14} (1999), 27--36.

\bibitem{Gordon:1998}
D.~M. Gordon, \emph{A survey of fast exponentiation methods}, J. Algorithms
  \textbf{27} (1998), no.~1, 129--146.

\bibitem{Graham-Knuth-Patashnik:1994}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik, \emph{Concrete mathematics. {A}
  foundation for computer science}, second ed., Addison-Wesley Publishing
  Company, Reading, MA, 1994.

\bibitem{Guentzer-Paul:1987}
U.~G{\"u}ntzer and M.~Paul, \emph{Jump interpolation search trees and symmetric
  binary numbers}, Inform. Process. Lett. \textbf{26} (1987), no.~4, 193--204.

\bibitem{Heuberger:1999:digitopt}
C.~Heuberger, \emph{Minimal expansions in redundant number systems and shortest
  paths in graphs}, Computing \textbf{63} (1999), 341--349.

\bibitem{Jedwab-Mitchell:1989}
J.~Jedwab and C.~J. Mitchell, \emph{{Minimum weight modified signed-digit
  representations and fast exponentiation}}, Electron. Lett. \textbf{25}
  (1989), no.~17, 1171--1172.

\bibitem{Kirschenhofer-Prodinger:1984}
P.~Kirschenhofer and H.~Prodinger, \emph{Subblock occurrences in positional
  number systems and {G}ray code representation}, J. Inform. Optim. Sci.
  \textbf{5} (1984), no.~1, 29--42.

\bibitem{Knuth:1998:Art:2}
D.~E. Knuth, \emph{Seminumerical algorithms}, The Art of Computer Programming,
  vol.~2, Addison-Wesley, Bonn, 1998.

\bibitem{Morain-Olivos:1990}
F.~Morain and J.~Olivos, \emph{Speeding up the computations on an elliptic
  curve using addition-subtraction chains}, RAIRO Inform. Th\'eor. Appl.
  \textbf{24} (1990), no.~6, 531--543.

\bibitem{Prodinger:2000:binary-representations--1-0-1}
H.~Prodinger, \emph{On binary representations of integers with digits $-1, 0,
  1$}, Integers \textbf{0} (2000), A08, available at
  \url{http://www.integers-ejcnt.org/vol0.html}.

\bibitem{Reitwiesner:1960}
G.~W. Reitwiesner, \emph{Binary arithmetic}, Advances in computers, Vol. 1,
  Academic Press, New York, 1960, pp.~231--308.

\bibitem{Thuswaldner:1999}
J.~M. Thuswaldner, \emph{Summatory functions of digital sums occurring in
  cryptography}, Period. Math. Hungar. \textbf{38} (1999), 111--130.

\end{thebibliography}


\end{document}






% LocalWords:  Morain Olivos Reitwiesner NAF Demetrovics Iverson's Jedwab Liang
% LocalWords:  GNAF
