\documentclass[12pt]{article}
% \usepackage{amsmath,amssymb,A4,varbbb2e,latexsym}
\usepackage{amsmath,amssymb,latexsym}
\hfuzz=7pt
\textwidth= 6.5in
\textheight= 9.0in
\topmargin = -20pt
\evensidemargin=0pt
\oddsidemargin=0pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9

\makeatletter %% this should really go into a style file!

\renewcommand\section{\@startsection {section}{1}{\z@}%
                                 % {-3.5ex \@plus -1ex \@minus -.2ex}%
        % here is your vskip of 30pt:
                                   {-30pt  \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\normalfont\normalsize\bfseries}}

\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
                                     {-3.25ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
        % add a point after section numbers:

\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad}

\makeatother

 \def\le{\leqslant}
 \def\ge{\geqslant}
 \def\Z{\mathbb Z}
 \def\N{\mathbb N}
 \def\epsilon{\varepsilon}
 \def\phi{\varphi}
  \newtheorem{defi}{Definition}
  \newcommand{\bd}{\begin{defi}}
  \newcommand{\ed}{\end{defi}}

  \newtheorem{lemm}[defi]{Lemma}
  \newcommand{\bl}{\begin{lemm}}
  \newcommand{\el}{\end{lemm}}

  \newtheorem{theo}[defi]{Theorem}
  \newcommand{\bt}{\begin{theo}}
  \newcommand{\et}{\end{theo}}

  \newtheorem{cor}[defi]{Corollary}
  \newcommand{\bc}{\begin{cor}}
  \newcommand{\ec}{\end{cor}}

  \newtheorem{pro}[defi]{Proposition}
  \newcommand{\bp}{\begin{pro}}
  \newcommand{\ep}{\end{pro}}

  \makeatletter
  \def\proof{\@ifnextchar[\opargproof{\opargproof[\it Proof.]}}
  \def\opargproof[#1]{\par\noindent {\bf #1 }}
  \def\endproof{{\unskip\nobreak\hfil\penalty50\hskip8mm\hbox{}
  \nobreak\hfil
  \(\Box\)\parfillskip=0mm \par\vspace{3mm}}}
  \makeatother

\def\x{{\text{\boldmath$x$}}}
\def\k{{\text{\boldmath$k$}}}
\def\l{{\text{\boldmath$l$}}}
\def\e{{\text{\boldmath$e$}}}
\def\r{{\text{\boldmath$r$}}}
\def\0{{\text{\boldmath$0$}}}

\begin{document}
\vspace*{-40pt} 
\centerline{\smalltt INTEGERS: 
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 
(2006), \#A23} 
\vskip 40pt

\begin{center}
\uppercase {\bf {A Generalization of the Smarandache
Function to  Several Variables}}
\vskip 20pt
{\bf Norbert Hungerb\"uhler}\\
{\smallit Department of Mathematics, University of Fribourg,
P\'erolles, 1700 Fribourg,
Switzerland}\\
{\tt norbert.hungerbuehler@unifr.ch}\\
\vskip 10pt
{\bf Ernst Specker}\\
{\smallit Department of Mathematics, ETH Z\"urich, 8092 Z\"urich,
Switzerland}\\
{\tt specker@math.ethz.ch}\\ 
\end{center}
\vskip 30pt
\centerline{\smallit Received: 1/16/06,
Accepted: 6/30/06, Published: 10/06/06}
\vskip 30pt






\centerline{\bf Abstract}
\noindent
We investigate polyfunctions in several
variables over $\Z_n$. We show in particular how the problem of determining
the cardinality of the ring of these functions leads
to a natural generalization of the classical Smarandache function.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: 
\smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6
(2006), \#A23\hfill}
\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 30pt

\section{Introduction}
Let us  consider the ring $\Z_n:=\Z/n\Z$, $n>1$, and a function
$$f:\Z_n^d\to \Z_n$$
of $d$ variables in $\Z_n$ with values in $\Z_n$. Such a function is called
a {\bf polyfunction} if there exists a polynomial
$$p\in\Z_n[x_1,\ldots,x_d]$$
%in the variables $x_1,\ldots,x_d$ with coefficients in $\Z_n$
such that
$$f(\x)\equiv p(\x)\mod n\qquad\forall\x=\langle x_1,\ldots,x_d\rangle\in\Z_n^d.$$
The set of polyfunctions of $d$ variables in $\Z_n$ with values in $\Z_n$,
equipped with pointwise addition and multiplication,
is a ring with unit element. We denote this ring by $G_d(\Z_n)$,
or, for simplicity, by $G(\Z_n)$ in the case of only one variable.

In the present article, we investigate polyfunctions in several
variables over $\Z_n$. We show in particular how the problem of determining
the cardinality of the ring of these functions leads
to a natural generalization of the classical Smarandache function (named after~\cite{sma})
\begin{equation}\label{smara}
\begin{split}
s : \N &\quad\to\quad      \N\\
     n  &\quad\mapsto\quad  s(n):=\min\{k\in \N : n\mid k ! \},
\end{split}
\end{equation}
which was studied by Lucas in~\cite{lucas}
for powers of primes, and by Kempner in~\cite{kempner}
and Neuberg in~\cite{neuberg} for general $n$. Indeed, $s(n)$
is the minimal degree of a normed polynomial which vanishes
(as a function) identically in $\Z_n$ (see~\cite{hhl}).
The key is then to reformulate the above definition by setting
$$s(n)=|\{ k\in \N_0 :  n\nmid k !  \}|.$$
This definition then generalizes in
a natural way to $d>1$ dimensions (see~(\ref{ernst1}) and~(\ref{ernst2})),
where the number can be interpreted as the number of irreducible monomials
$\x^\k$ modulo $n$ (see Section~\ref{number}).

The number of polyfunctions in $G_d(\Z_n)$ is multiplicative in $n$
(see Section~\ref{number}).
It therefore suffices to compute the values for $n=p^m$, $p$ prime.
By analysing the structure of the additive group of $G_d(\Z_{p^m})$,
which is completely described in Proposition~\ref{add},
we find
$$|G_d(\Z_{p^m})|=p^{\sum_{i=1}^ms_d(p^i)}$$
(see Theorem~\ref{finale}). However, the factors $p^{s_d(p^i)}$
do not correspond to additive subgroups of $G_d(\Z_{p^m})$.

In Section~\ref{char} we present a characterization which allows
us to test whether a given function $f:\Z_n^d\to \Z_n$ is a polyfunction,
and if so, to determine a polynomial representative of $f$.
%
In Section~\ref{uni} we characterize the units in the ring $G_d(\Z_n)$.
% The detailed algebraic structure of the ring $G_d(\Z_n)$ will be
% described in an upcoming publication.

We conclude this introduction with a short overview on the history
of polyfunctions. The study of polyfunctions in one variable goes
back to Kempner who discussed polyfunctions over $\Z_n$ in
connection with Kronecker modular systems ~\cite{kempner2}. He also
gave a formula for the number of polyfunctions over $\Z_n$. Later,
Carlitz  investigated properties of polyfunctions over $\Z_{p^n}$
for $p$ prime ~\cite{carlitz}. Keller and Olson gave a simplified
proof of Kempner's formula ~\cite{keller} and also determined the
number of polyfunctions which represent a permutation of $\Z_{p^n}$.
Null-polynomials over $\Z_n$ (i.e.,\ polynomials which represent the
zero-function) have been investigated by Singmaster
~\cite{singmaster}. Certain aspects of polyfunctions in several
variables over $\Z_n$ were addressed in~\cite{mullen}. Recently,
polyfunctions from $\Z_n$ to $\Z_m$ have attracted increasing
attention (see~\cite{chen}, \cite{chen2} and \cite{bhargava}). The
focus there is to find conditions on the pair $\langle m,n\rangle$
such that all functions (or certain subclasses) from $\Z_n$ to
$\Z_m$ are polyfunctions. In~\cite{redei} and~\cite{redei2}
polyfunctions over a general ring were discussed: the question asked
being ``for which rings $R$ one can find a ring $S$, such that all
functions on $R$ can be represented by polynomials over $S$?"

\section{Notation, Definitions and Basic Facts}
In order to keep the formulas short, we use
the following multi-index notation. For $\k=
\langle k_1,k_2,\ldots,k_d\rangle\in\N_0^d$ and
$\x:=\langle x_1,x_2,\ldots,x_d\rangle,$
let $$\x^\k:=\prod_{i=1}^dx_i^{k_i}$$ and $$\k ! :=\prod_{i=1}^dk_i ! .$$
Furthermore, we write $$|\k|:=\sum_{i=1}^d k_i$$ and
$$\binom{\x}{\k}:=\prod_{i=1}^d\binom{x_i}{k_i}.$$
Let $\e_i:=\langle0,\ldots,0,1,0,\ldots,0\rangle\in\Z_n^d
$, with the $1$
at place $i$. Then, we define the (forward) partial difference
operator $\Delta$ by
\begin{eqnarray*}
\Delta_i g(\x) &:=& g(\x+\e_i)-g(\x)\\
\Delta_i^0  &:=& \operatorname{identity}\\
\Delta_i^k  &:=& \Delta_i\circ\Delta_i^{k-1}.
\end{eqnarray*}
For a multi-index $\k$, let
$$
\Delta^\k:=\Delta_1^{k_1}\circ\ldots\circ\Delta_d^{k_d}.
$$
Notice that the $\Delta$ operators commute and that $\Delta^{\k_1}\circ\Delta^{\k_2}=
\Delta^{\k_1+\k_2}$.
We recall that
\begin{equation}\label{aha}
\Delta^\r g(\x)=\sum_{\k\le\r} g(\x+\r-\k)(-1)^{|\k|}\binom \r\k,
\end{equation}
where $\k\le\r$ means $0\le k_i\le r_i$ (see e.g.~\cite{SloanePlouffe}).
A polynomial $p$ equals its ``Taylor expansion''
\begin{equation}\label{taylor}
p(\x)=\sum_{|\k|\le\operatorname{deg}(p)}
\Delta^\k p(\0)\binom \x\k
\end{equation}
(see e.g.~\cite{hua}).   Observe, that  the monomial $x^l$  defines by
$((x+n)^l)_{n\in\Z}  $ for  any fixed  $x$ an  arithmetic  sequence of
order $l$. Therefor, one easily checks by induction, that
\begin{equation}\label{basic}
\Delta^r x^l=\begin{cases}\,\,0 & \text{ if $r>l$,}\\
\,\,r ! & \text{ if $r=l$.}\end{cases}
\end{equation}
Hence, the summation in~(\ref{taylor}) can be restricted to the {\bf
shadow} of $p$, i.e., the multi-indices $\k$ with the property that
$0\le\k\le\r$ for a monomial $\x^\r$ in $p$. Indeed, if $\k$ does
not belong to the shadow of $p$, then $\Delta^\k p(\0)=0$
by~(\ref{basic}).

It is well known (see e.g.~\cite{hua})
that a polynomial $p$ has integer coefficients if and only if the condition
\begin{equation}\label{tteilt}
\k ! \mid \Delta^\k p(\0)
\end{equation}
holds for all $\k$ in the shadow of $p$ (for other values of $\k$, the
condition~(\ref{tteilt}) is trivially satisfied by the previous remark).



\section{Characterization of Polyfunctions}\label{char}
Let $f:\Z_n^d\to \Z_n$ be a polyfunction, i.e.,\ there exists a
polynomial $p\in \Z_n[x_1,\ldots,x_d]$ such that
\begin{equation}\label{erg}
 f(\x)\equiv p(\x)\mod n\quad\text{for all $\x\in \Z_n^d$.}
\end{equation}
Since for all $x\in \Z_n$
$$\prod_{i=0}^{n-1}(x-i)= 0\text{ in $\Z_n$,}$$
we may assume, without loss of generality, that the degree of $p$
is, in each variable separately, strictly less than $n$. Thus, in $\Z_n$ we have %% by~(\ref{taylor})
for arbitrary $\x\in \Z_n^d,$
\begin{eqnarray*}
f(\x) &\overset{\text{by (\ref{erg})}}{=}&p(\x)\\ %%\operatorname{mod}(p(x),n)\\
     &\overset{\text{by (\ref{taylor})}}{=}&\sum_{k_i<n}\Delta^\k p(\0)\binom \x\k\\ %%\operatorname{mod}\big(\sum_{k=0}^{n-1}\Delta^k p(0)\binom xk,n\big)\\
     &\overset{\text{by (\ref{erg})}}{=}&\underbrace{\sum_{k_i<n}\Delta^\k f(\0)
\binom \x\k}_{=:h(\x)}.%%\operatorname{mod}\big(\underbrace{\sum_{k=0}^{n-1}\Delta^k f(0)\binom xk}_{=:h(x)},n\big).
\end{eqnarray*}
Hence, the polynomial $h$ represents $f$, but it does not
necessarily have integer coefficients. However, observing~(\ref{tteilt})
and exploiting the fact that in $\Z_n,$
$$\Delta^\k p(\0)= \Delta^\k f(\0)$$
 holds for all $\k$, we obtain:
\bl\label{22}
If $f:\Z_n^d\to \Z_n$ is a polyfunction, then
\begin{itemize}
\item[(i)] for all multi-indices $\k$ with components $k_i<n$, there exist
$\alpha_\k\in \Z$
such that for the numbers $\beta_\k:=\Delta^\k f(\0)+\alpha_\k n,$
\begin{equation}\label{invers}
\k ! \mid \beta_\k,
\end{equation}
 and
\item[(ii)] the polynomial $\displaystyle{\sum_{k_i<n}\beta_\k\binom \x\k}$
has integer coefficients and represents $f$.
\end{itemize}
\el
From~(\ref{invers}) it follows, that
\begin{equation}\label{teilt}
(n,\k ! )\mid \Delta^\k f(\0)\quad\footnote{$(a,b)$ denotes the greatest
common  divisor of  $a$ and $b$.}
\end{equation}
for all $\k$ with $k_i<n$. We will show now that
this condition characterizes polyfunctions. To this end,
we consider an arbitrary function $f:\Z_n^d\to \Z_n$.
Since there exists an interpolation polynomial for $f$, with degree
in each variable strictly less
than $n$, which agrees with $f$
on the set $\{0,1,\ldots,n-1\}^d$, we infer from~(\ref{taylor}) that, in
$\Z_n$,
$$f(\x)=\sum_{k_i<n}\Delta^\k f(\0)\binom \x\k %%\operatorname{mod}\big(\sum_{k=0}^{n-1}\Delta^k f(0)\binom xk,n\big)
$$
for all $\x\in\Z_n^d$. If condition~(\ref{teilt})
is satisfied for $f$, we find coefficients $\beta_\k=
\Delta^\k f(\0)+\alpha_\k n$, as above
in Lemma~\ref{22}(i), such that $\k ! \mid\beta_\k$. Hence, in $\Z_n$
$$f(\x)=\sum_{k_i<n}\beta_\k\binom \x\k %%
\operatorname{mod}\big(\sum_{k=0}^{n-1}\beta_k\binom xk,n\big),
$$
for all $\x\in\Z_n^d$.
In other words, condition~(\ref{teilt}) implies that
$f$ is a polyfunction and we have the following
characterization:
\bt\label{char1}
$f:\Z_n^d\to \Z_n$ is a polyfunction over $\Z_n$ if and only if
$(n,\k ! )\mid \Delta^\k f(\0)$ for all multi-indices $\k$ with $k_i<n$.
\et

\section{The Inverse of a Polyfunction}\label{uni}
Let $f:\Z_n^d\to\Z_n$. Then $f$ is invertible (i.e.,\ there exists a
function $g:\Z_n^d\to\Z_n$, such that for all $\x\in\Z_n^d$ there
holds $f(\x)g(\x)= 1$) if and only if
$\operatorname{Image}(f)\subset U(\Z_n)$. Here, $U(\Z_n)$ denotes
the multiplicative group of units in $\Z_n$. We want to show that
the same characterization holds for invertible polyfunctions over
$\Z_n$. \bp A polyfunction $f:\Z_n^d\to\Z_n$ is invertible in the
ring of polyfunctions (and hence a unit in $G_d(\Z_n)$) if and only
if
$$\operatorname{Image}(f)\subset U(\Z_n) .$$
\ep
\proof
The necessity of the condition is trivial. In order to prove that it is
also sufficient,
let $k:=\operatorname{lcm}\{\operatorname{ord}(x)\mid x\in U(\Z_n)\}$\footnote{ \,\, $\operatorname{lcm}(M)$ is the least common multiple
of all integer numbers in a finite set $M$. $\operatorname{ord}(x)$ denotes
the order of an element $x$ in a finite multiplicative group $G$,
i.e.,\ $\operatorname{ord}(x)$ is the smallest number $k\in\N$ such that
$x^k=1$.}. Then,
if $p$ denotes a polynomial representing $f$, we have
$$
p^k(\x)= 1\quad\text{in $\Z_n$}
$$
for all $\x\in\Z_n^d$. Hence, the polynomial $p^{k-1}$ represents
the inverse of $f$.
\endproof


\section{The Number of Polyfunctions}\label{number}
Let $a$ be an element of $\Z_n$.
We say, the monomial $a\x^\k\in \Z_n[\x]$ is {\bf reducible\/} (modulo $n$)
if a polynomial $p(\x)\in \Z_n[\x]$ exists with $\operatorname{deg}(p)
< |\k|$ such that $a\x^\k\equiv p(\x)\mod n$ for all $\x\in \Z_n^d$.
Moreover, we say that $a\x^\k$ is {\bf weakly reducible\/} (modulo $n$)
if $a\x^\k\equiv p(\x)\mod n$ for all $\x\in \Z_n^d$, for a polynomial
$p\in \Z_n[\x]$
with $\operatorname{deg}(p)\le |\k|$ (instead of
$\operatorname{deg}(p)< |\k|$),
and such that $\x^\k$ (or a multiple of it) does not appear as a monomial in $p$.
% then it follows by the same proof as above, that $k ! \,l ! \equiv 0\mod n$
% and hence, that $x^ky^l$ is reducible also in the strong sense.

The following lemma characterizes the tuples $\k$ for
which $a\x^\k$ is (weakly) reducible.

\bl\label{ver}
(i) If $a\x^\k\in \Z_n[\x]$ is weakly reducible modulo $n$, then
$n\mid a\k !  $. \\
(ii) If $n\mid a\k !  $, then
$a\x^\k$ is reducible modulo $n$.
\el
In particular, a monomial is reducible if and only if it is weakly
reducible.
\proof
(i)
We assume, that $p(\x)$
reduces $a\x^\k$ weakly. Hence,
$q(\x):=a\x^\k-p(\x)$ is a null-polynomial (i.e., a polynomial which
represents
the zero-function) in $d$ variables over $\Z_n$.
Then, we write $q$ in the form
\begin{equation}\label{coe}
q(\x)=\sum_{\substack{\l\in\N_0^d\\|\l|\le|\k|}}q_{\l}\x^\l
\end{equation}
for suitable coefficients $q_\l\in\Z_n$, with $q_\k=a$.
Using the linearity of the $\Delta$ operator, we obtain that, modulo $n$,
$$0=\Delta^\k q(\x)\overset{\text{(\ref{coe})}}{=}
\sum_{\substack{\l\in\N_0^d\\|\l|\le|\k|}}q_{\l}\Delta^\k \x^\l
\overset{\text{(\ref{basic})}}{=}a\k ! .$$
In fact, all terms in the above sum with $\l\neq\k$ vanish
by~(\ref{basic}), since $|\l|\le|\k|$ and
$\l\neq\k$ implies that $\k$ is not in the shadow of $\x^\l$.
And the only remaining term, $\Delta^\k x^\k$, equals $\k ! $,
again by~(\ref{basic}).


(ii) We assume, that $n\mid a\k !  $.
Then, the polynomial
$$
q(\x):=a\prod_{i=1}^d\,\prod_{l=1}^{k_i}(x_i+l)=a \k! %\prod_{i=1}^d \,\binom{x_i+k_i}{k_i}
\binom{\x+\k}{\k}
$$
is a  null-polynomial over $\Z_n$ and the term of maximal degree
is $a\x^\k$. Hence, $q(\x)-a\x^\k$ reduces to $a\x^\k$.
\endproof
Lemma~\ref{ver} allows us to count
the number of monomials $\x^\k$, $\k\in \N_0^d$, which are
not reducible. Let
\begin{equation}\label{ernst1}
S_d(n) := \{\k\in \N^d_0 :  n\nmid \k ! \}
\end{equation}
denote the set of multi-indices $\k$ such that $\x^\k$ is not reducible
modulo $n$. Its cardinality is the natural generalization
of the Smarandache function to the case of several variables:
\begin{equation}\label{ernst2}
s_d(n) := |S_d(n)|.
\end{equation}
Of course, for $d=1$ the function $s_1$ agrees with the usual number
theoretic Smarandache function (see introduction)---except for
$n=1$, since $s(1)=1$, but $s_1(1)=0$. Actually, by defining $s(n):=
\min\{k\in \N_0 : n\mid k ! \}$ (i.e., the minimum is taken over
$k\in\N_0$ rather than over $k\in\N$), this discrepancy could be
removed. Incidentally, Kempner originally defined $s(1)=1$
in~\cite{kempner}, but changed to $s(1)=0$ in~\cite{kempner2}. The
following table displays $s_d(n)$ for the first few values of $d$
and $n$.
\begin{center}
{\small
\begin{tabular}
{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c}\hline
$n$  &  1&2&3&4&5&6&7&8&9&10&11&12&13\\\hline\hline
$s_1$&  0&2&3&4&5&3&7&4&6&5&11&4&13\\\hline
$s_2$&  0&4&9&12&25&9&49&16&27&25&121&13&169\\\hline
$s_3$&  0&8&27&32&125&27&343&56&108&125&1331&39&2197\\\hline
$s_4$&  0&16&81&80&625&81&2401&176&405&625&14641&113&28561\\\hline
\end{tabular}
}

Table 1: Values of $s_d(n)$
\end{center}
Before we now start to compute the number of $\Psi_d(p^m)$ poyfunctions in $G_d(\Z_{p^m})$, it is
useful to include a general remark.  The notion of the ring of
polyfunctions $G(\Z_n)$ generalizes in a natural way to the ring
$G(R)$ of polyfunctions over an arbitrary ring $R$. If $R$ and $S$ are
commutative rings with unit element, then $G(R\oplus S)$ and
$G(R)\oplus G(S)$ are isomorphic as rings in the obvious way.  In
particular, since $\Z_n\oplus\Z_m\cong\Z_{nm}$ if $m$ and $n$ are
relatively prime, we have that $G(\Z_{nm})\cong G(\Z_n)\oplus G(\Z_m)$
if $(m,n)=1$.
% Therefore, we may confine ourselves to the case $n=p^m$, $p$ prime,
% without loss of generality.

Analogously in several variables, we have the decomposition
$G_d(\Z_{mn})\cong G_d(\Z_{m})\oplus G_d(\Z_{n})$ if $(m,n)=1$.
This means, e.g., that the number $\Psi_d(n)$ of polyfunctions in
$G_d(\Z_n)$ is multiplicative in $n$.  Therefore, we may restrict
ourselves to the case $n=p^m$ for $p$ prime.

Now, the strategy to count the number of polyfunctions is to seek a
unique standard representation of such functions by a polynomial. Such
a representation is given in Proposition~\ref{representation} below.
Then, we will just have to count these representing polynomials.  Let
us first consider the case of one variable.  Obviously,
$$\prod_{i=1}^{s_1(n)}(x-i)=\binom{x+s_1(n)}{s_1(n)}s_1(n) ! $$ is a
normed\footnote{i.e., its leading coefficient is 1} null-polynomial
in $G(\Z_n)$, and from Lemma~\ref{ver} it follows in particular that
there is no polynomial of smaller degree with this property.
Therefore, every polyfunction in one variable over $\Z_n$ has a (not
necessarily unique) representing polynomial of degree strictly less
than $s_1(n)$ (and here $s_1(n)$ cannot be replaced by a smaller
number). Basically by the same argument, Lemma~\ref{ver} allows us
to construct a unique representation of every polyfunction in $d$
variables over $\Z_{p^m}$. \bp\label{representation} Every
polyfunction $f\in G_d(\Z_{p^m})$ has a unique representation of the
form
\begin{equation}\label{6}
f(\x)\equiv\sum_{i=1}^m p^{m-i}\sum_{\k\in S_d(p^i)}\alpha_{\k i}\x^\k
\end{equation}
where $\alpha_{\k i}\in\Z_p$.
\ep
\proof
It is common to write $n=\prod p^{\nu_p(n)}$ for the prime decomposition of a
positive integer $n$. We adopt this notation and write
$$
\nu_p(\k ! )=\max\{x\in\N_0\,:\, p^x\mid \k!  \}
$$
for the number of factors $p$ in $\k ! $.
Notice that $\nu_p(\k ! )< i$ if and only if $\k\in S_d(p^i)$.
Then, as an immediate consequence of Lemma~\ref{ver}, we obtain, that
every polyfunction $f\in G_d(\Z_{p^m})$ has a unique
representation of the form
\begin{equation}\label{1}
f(\x)\equiv\sum_{\substack{\k\in\N_0^d\\ \nu_p(\k ! )< m}} \alpha_{\k}\x^\k,
\end{equation}
where $\alpha_{\k}\in\{0,1,\ldots,p^{m-\nu_p(\k ! )}-1\}$.
Since, on the other hand, every number
$\alpha_{\k}\in\{0,1,\ldots,$ $p^{m-\nu_p(\k ! )}-1\}$ has a unique
representation of the form
$$\alpha_{\k}=\sum_{\{i\le m\,:\,\k\in S_d(p^i)\}}p^{m-i}\alpha_{\k i}$$ for
certain coefficients $\alpha_{\k i}\in\Z_p$, we can rewrite~(\ref{1})
such that we obtain~(\ref{6}).
\endproof
As an immediate consequence of Proposition~\ref{representation},
we now get the formula for the number of poyfunctions in the following theorem.
Observe that we use the notation $\exp_pa:=p^a$
for better readability.
\bt\label{finale}
The number of polyfunctions
in $G_d(\Z_{p^m})$, $p$ prime, is given by
$$
\Psi_d(p^m)=\exp_p\Bigl(\sum_{i=1}^ms_d(p^i)\Bigr).
$$
\et
{\bf Example.} To compute the number of polyfunctions $\Psi_2(8)$ in two
variables over $\Z_8$, we need:
\begin{eqnarray*}
S_2(2) &=& \{\langle k_1,k_2\rangle : 0\le k_1\le 1, 0\le k_2\le 1\}\\
s_2(2) &=& 4\\
S_2(4) &=& \{\langle k_1,k_2\rangle : 0\le k_1\le 3, 0\le k_2\le 3,
k_1 k_2< 4\}\\
s_2(4) &=& 12\\
S_2(8) &=& \{\langle k_1,k_2\rangle : 0\le k_1\le 3, 0\le k_2\le 3\}\\
s_2(8) &=& 16.
\end{eqnarray*}
This gives $\Psi_2(8)=2^{4+12+16}=2^{32}$.\hfill$\bigcirc$

Notice that the formulas~(\ref{1}) and~(\ref{6}) reflect the
structure of the additive group of $G_d(\Z_{p^m})$. In fact
$$
A_{d\k}(\Z_{p^m}):=\{f\in G_d(\Z_{p^m})\,:\,f(x)\equiv \alpha \x^\k,\ \alpha\in\Z_{p^{m-\nu_p(\k ! )}}\}
\cong \Z_{p^{m-\nu_p(\k ! )}}$$
are additive subgroups in $G_d(\Z_{p^m})$ and hence, by~(\ref{1}):
\bp\label{add}
$\displaystyle
(G_d(\Z_{p^m}),+)\cong
%\bigoplus_{\nu_p(\k ! )<m}A_{d\k}(\Z_{p^m})\cong
\bigoplus_{\substack{\k\in\N_0^d\\ \nu_p(\k ! )< m}}\Z_{p^{m-\nu_p(\k ! )}}
%\cong |S_d(p)|\Z_{}\bigoplus_{\k\in S_d(p^m)}|S_d(p^{}
.$
\ep
As an immediate consequence of Theorem~\ref{finale} and Proposition~\ref{add}, we note
the following identity:
\bc\quad
$\displaystyle \sum_{i=1}^m s_d(p^i)=\sum_{\k\in S_d(p^m)}\bigl(m-\nu_p(\k ! )\bigr) =
m\, s_d(p^m)-  \sum_{\k\in S_d(p^m)}\nu_p(\k ! )$.
\ec
For completeness, we add an explicit formula for $\Psi_d(n)=|G_d(\Z_n)|$ for
general $n$. We start from the identity
$$
\Psi_d(n)=\Psi_d(\prod_{i=1}^k p_i^{\nu_{p_i}(n)})=\prod_{i=1}^k\Psi_d(p_i^{\nu_{p_i}(n)}).
$$
By taking the logarithm on both sides and using Theorem~\ref{finale}
we obtain
\begin{eqnarray}
\ln \Psi_d(n)&=&\sum_{i=1}^k \ln\Psi_d(p_i^{\nu_{p_i}(n)})\nonumber\\
&=&\sum_{i=1}^k \ln p_i\sum_{j=1}^{\nu_{p_i}(n)} s_d(p_i^j).\label{mangoldt}
\end{eqnarray}
Observe that the Mangoldt function
$$
\Lambda:\N\to\N,\quad x\mapsto\begin{cases}\ln p\quad &\text{if $x=p^k$, $p$ prime, $k\ge 1$}\\0&\text{else}
                  \end{cases}
$$
allows us to simplify~(\ref{mangoldt}) further and to obtain
$$
\ln \Psi_d(n)=\sum_{i=1}^k \sum_{j=1}^{\nu_{p_i}(n)} s_d(p_i^j)\Lambda(p_i^j).
$$
Since the Mangoldt function is zero on all numbers which are
not powers of primes, this last expression can be interpreted
as a sum over {\em all\/} divisors of $n$. Moreover, since $\Lambda(1)=0$,
the value of $s_d(1)$ is irrelevant. Hence, using
the Dirichlet convolution
$$
(f * g) (n) = \sum_{d\mid n} f\bigl(\frac nd\bigr)g(d)
$$
with $f\equiv 1$ and $g=s_d \, \Lambda$, we arrive at
$$
\ln \Psi_d(n) = \bigl(1*(s_d\,\Lambda)\bigr)(n).
$$
Hence, we have the following Theorem:
\bt\label{closed}
The number $\Psi_d(n)$ of polyfunctions
in $G_d(\Z_{n})$, $n>1$, is given by
$$
\Psi_d(n)=e^{1*(s_d\,\Lambda)(n)}.
$$
\et

\section{The Towers of Hano\"\i}
The Smarandache function can be used to solve the Towers of Hano\"\i{} problem.
In Theorem~\ref{finale}, for $p=2$ and one variable, we need the numbers
$$ s(2^k).$$
Let us consider the first difference sequence
$$a_k:=s(2^k)-s(2^{k-1}),\qquad\mbox{$k=1,2,3,\ldots$}$$
The sequence starts with
$$(a_k)_{k\in\N}=(2,2,\underbrace{0}_{\mbox{$\epsilon_1$}},
2,2,\underbrace{0,0}_{\mbox{$\epsilon_2$}},2,2,
\underbrace{0}_{\mbox{$\epsilon_3$}},2,2,
\underbrace{0,0,0}_{\mbox{$\epsilon_4$}},2,2,
\underbrace{0}_{\mbox{$\epsilon_5$}},2,2,\ldots).$$
Two 2s alternate with groups of  $\epsilon_k$ $0$s.
The sequence
\begin{eqnarray*}(\epsilon_k)_{k\in\N}&=&(1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,\\&&
\qquad 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,\ldots),
\end{eqnarray*}
with the property that $2^{\epsilon_k}$ divides exactly $2k$, is now
indeed the solution  of the Towers of Hano\"\i. It provides the
number of the disk, which is to be relocated in the $k$-th move.

Alternatively, knowing the solution of the Towers of Hano\"\i{}
one has an efficient way to compute $s(2^k)$.


\begin{thebibliography}{99}
\footnotesize 

\bibitem{bhargava}
M.\ Bhargava:
Congruence preservation and polynomial functions from $Z\sb n$ to $Z\sb m$.
Discrete Math.\ {\bf 173} (1997), no.\ 1--3, 15--21.

\bibitem{carlitz}
L.\ Carlitz:
Functions and polynomials $({\rm mod\ } p\sp{n})$.
Acta Arith.\ {\bf 9} (1964), 67--78.

\bibitem{chen}
Z.\ Chen:
On polynomial functions from $Z\sb n$ to $Z\sb m$.
Discrete Math.\ {\bf 137} (1995), no.\ 1--3, 137--145.

\bibitem{chen2}
Z.\ Chen:
On polynomial functions from $Z\sb {n\sb 1}\times Z\sb {n\sb
2}\times \cdots \times Z\sb {n\sb r}$ to $Z\sb m$.
Discrete Math.\ {\bf 162} (1996), no.\ 1--3, 67--76.

\bibitem{hhl}
L.\ Halbeisen, N.\ Hungerb\"uhler, H.\ L\"auchli:
Powers and polynomials in $\Z_m$.
Elem.\ Math.\ {\bf 54} (1999), 118--129.

\bibitem{hua}
L.\,K.\ Hua:
Introduction to Number Theory.
Springer, 1982.

\bibitem{keller}
G.\ Keller,  F.\,R.\ Olson:
Counting polynomial functions $({\rm mod\ }p\sp{n})$.
Duke Math.\ J.\ {\bf 35} (1968), 835--838.

\bibitem{kempner}
A.\,J.~Kempner:
Concerning the smallest integer
$m ! $ divisible by a given integer $n$. Amer.\ Math.\ Monthly
{\bf 25} (1918), 204--210.

\bibitem{kempner2}
A.\,J.~Kempner:
Polynomials and their residual systems.
Amer.\ Math.\ Soc.\ Trans.\ {\bf 22} (1921), 240--288.

\bibitem{lucas}
E.\ Lucas:
Question Nr.\ $^\times${\bf 288}. Mathesis {\bf 3} (1883), 232.

\bibitem{mullen}
G.\ Mullen, H.\ Stevens:
Polynomial functions $({\rm mod\ }m)$.
Acta Math.\ Hungar.\ {\bf 44} (1984), no.\ 3--4, 237--241.

\bibitem{neuberg}
J.\ Neuberg:
Solutions de questions propos\'ees,
Question Nr.\ $^\times${\bf 288}. Mathesis {\bf 7} (1887), 68--69.

\bibitem{redei}
L.\ R\'edei, T.\ Szele:
Algebraisch-zahlentheoretische Betrachtungen \"uber Ringe. I.
Acta Math.\ {\bf 79}, (1947), 291--320.

\bibitem{redei2}
L.\ R\'edei, T.\ Szele:
Algebraisch-zahlentheoretische Betrachtungen \"uber Ringe. II.
Acta Math.\ {\bf 82}, (1950), 209--241.

\bibitem{singmaster}
D.\ Singmaster:
On polynomial functions $({\rm mod}$ $m)$.
J.\ Number Theory {\bf 6} (1974), 345--352.

\bibitem{SloanePlouffe}
N.\,J.\,A.~Sloane, S.~Plouffe:
The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.

\bibitem{sma}
F.\ Smarandache:
A Function in the Number Theory.
Analele Univ.\ Timisoara, Fascicle 1, Vol.\ {\bf XVIII} (1980), 79--88.
%; Smarandache Function J. 1 (1990), no. 1, 3-17.
\end{thebibliography}
\end{document}