<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\DeclareMathOperator{\ld}{ld}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Generalized Number Derivatives}
\vskip 1cm
\large
Michael Stay\\
Department of Computer Science\\
University of Auckland\\
Private Bag 92019\\
Auckland 1020\\
New Zealand \\
\href{mailto:staym@clear.net.nz}{\tt staym@clear.net.nz} \\
\end{center}

\vskip .2 in
\begin{abstract}
We generalize the concept of a number derivative, and examine one
particular instance of a deformed number derivative for finite field
elements.  We find that the derivative is linear when the deformation
is a Frobenius map and go on to examine some of its basic properties.

\end{abstract}

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

%\documentclass[reqno]{amsart}
%\usepackage{amsmath}

\newcommand{\ctr}[1]{\begin{center} #1 \end{center}}
\newcommand{\oo}[0]{\infty}
\newcommand{\al}[1]{\begin{align} #1 \end{align}}
\newcommand{\alx}[1]{\begin{align*} #1 \end{align*}}
\newcommand{\bigparens}[1]{\mbox{\huge (} #1 \mbox{\huge )}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

%\begin{document}




\section{Introduction}
The so-called ``number derivative'' seems to have been invented
independently at least three times \cite{KOW02,CI03,UA03}.  Here we
present a generalization of the number derivative that applies to
nearly anything one might reasonably call a number.  Afterwards, we
examine the case of a specific number derivative on finite fields and
some of its basic properties.

We generalize the concept of a number derivative to the following
algorithm; in order to illustrate each step, we will present the
corresponding step from the standard number derivative, denoted $N$,
and our number derivative, denoted $S$.

The notation we use below requires some care. Multiplication is denoted by a dot $[\cdot]$ or by concatenation of symbols: $x\cdot x^2=xx^2=x^3$.  The notation $x^n$ denotes a {\em function}: 
    $$x^n(y)=y^n,$$ 
so $x(y)=y$ is the identity function and $x^0(y)=1$ for all $y$.  Parentheses, when preceded by a function or operator, denote composition or application, respectively:
    $$x^2(x^n) = (x^n)^2 = x^{2n}.$$
Application is left associative:
    $$f(g)(h)=(f(g))(h),$$
and takes precedence over multiplication:
    $$gh(f)\ne g(f)\cdot h(f).$$

\begin{enumerate}
\item Choose a parameterized canonical form.  In the case of $N$, this
consists of representing each integer as a product of prime powers; the
parameters are the primes.  In the case of $S$, we choose a generator
$\theta$ of the finite field GF($p^k$) and express each finite field
element as $\theta^n$.  Here, the parameter is $\theta$.

\item Convert this canonical form into a function.  The algorithm $N$
takes each prime power $p_i^{k_i}$ to a function
$x_i^{k_i}(y_i)=y_i^{k_i}$.  The algorithm $S$ replaces $\theta^n$ with
the function $x^n(y)=y^n$.

\item Differentiate the function with respect to the parameters.  The
algorithm $N$ computes $D(f) = (\sum_{i}\frac{\partial}{\partial
x_i})(f)$.  The algorithm $S$ computes the $s$-derivative $D_s(f)$.

\item Evaluate the derivative at some function of the parameters,
typically the identity function.  The algorithm $N$ computes
$D(f)|_{y_i = p_i}$.  The algorithm $S$ computes $D_s(f)|_{y=\theta}$.
\end{enumerate}

\section{Exponential quantum calculus}

We begin with the operator $M_s(f)=f(x^s)$.  The $s$-differential is then $d_s=M_s-x$ and the $s$-derivative is
    $$D_s(f) = \frac{d_s (f)}{d_s (x)}.$$
The $s$-derivative of an element $x^n(\theta)$ is
    $$D_s(x^n)(\theta)=\frac{M_s(x^n)-x^n}{M_s(x)-x}(\theta)
              =\frac{x^{ns}-x^n}{x^s-x}(\theta)=([n]x^{n-1})(\theta),$$
where $$[n] \equiv \frac{x^{(s-1)n}-x^0}{x^{s-1}-x^0}.$$

The $s$-deformation has many similarities to the $q$-deformation that
results in the quantum calculus \cite{KC02}.  To get the
$s$-deformation from the $q$-deformation, one replaces the constant $q$
by the function $x^{s-1}$.  Since this is the same transformation we
chose to use in the second step of the algorithm $S$, both derivatives
give rise to the same number derivative.

Since the notation is somewhat simpler for the $q$-derivative, we will adopt it through most of the paper.  The operator $M_q = M_s$:
    $$M_s(f)=f(x^s)=f(x^{s-1}x)=f(qx)=M_q(f).$$  
The $q$-differential is $d_q=M_q-x$ and the $q$-derivative is
    $$D_q(f) = \frac{d_q(f)}{d_q(x)}.$$
The $q$-derivative of an element $x^n(\theta)$ is
    $$D_q(x^n)(\theta)=\frac{M_q(x^n)-x^n}{M_q(x)-x}(\theta)
              =\frac{q^nx^n-x^n}{qx-x}(\theta)=([n]x^{n-1})(\theta),$$
where $$[n] \equiv \frac{q^n-q^0}{q^1-q^0}.$$

Also, in the portions of the paper directly concerning the algorithm
$S$, we will usually omit the final application of the functions to
$\theta$.



\section{Identities}


For what functions $q=x^{s-1}$, if any, is this number derivative
linear?  Let $\theta^a+\theta^b=\theta^c$.  Then
    $$D_q(x^c)(\theta)=\frac{x^{sc}-x^c}{x^{s}-x}(\theta)
      =\frac{(\theta^a + \theta^b)^{s} -
      \theta^c}{\theta^{s}-\theta}.$$ 
On the other hand,
    $$(D_q(x^a)+D_q(x^b))(\theta)=\frac{x^{as}+x^{bs}-(x^a+x^b)}{x^s-x}(\theta)
=\frac{\theta^{as}+\theta^{bs}-\theta^c}{\theta^s-\theta},$$ so
we want the cross terms in the binomial $(\theta^a + \theta^b)^{s}$ to
be zero modulo $p$.  This only occurs when $s$ is a power of $p$, so
the derivative is linear if and only if $M_s$ is a Frobenius map.  In
the rest of the paper, we will only consider $q=x^{s-1}$ of this form.


The derivation of the product rule is the same as that for the $q$-derivative:
\al{
    D_q(fg)&amp;= \frac{M_q(fg) - fg}{M_qx-x} \nonumber \\
                 &amp;= \frac{M_q(f)M_q(g)-M_q(g)f+M_q(g)f-fg}
                         {M_q(x)-x} \nonumber \\
                 &amp;= M_q(g)\frac{M_q(f)-f}{M_q(x)-x}+
                    f\frac{M_q(g)-g}{M_q(x)-x} \nonumber \\
                 &amp;= M_q(g)D_q(f) + fD_q(g)   \label{eq:prod1} \\
                 &amp;= gD_q(f) + M_q(f)D_q(g), \label{eq:prod2}
}
where (\ref{eq:prod2}) follows by symmetry.




The same is true for the quotient rule.  Since by (\ref{eq:prod1}),
\al{
    D_q (f) &amp;= D_q(g\frac{f}{g}) \nonumber \\
             &amp;= M_q(g)D_q(\frac{f}{g}) + \frac{f}{g}D_q(g), \nonumber 
    \intertext{we have}
    D_q (\frac{f}{g}) &amp;=\frac{gD_q(f)-fD_q(g)}{gM_q(g)} \label{eq:quot1}\\
                    &amp;=\frac{M_q(g)D_q(f)-M_q(f)D_q(g)}{gM_q(g)}\label{eq:quot2}
}
where (\ref{eq:quot2}) follows from (\ref{eq:prod2}) instead.




Note that while there is not a general chain rule for the standard
$q$-derivative, we can use the fact that every element is of the form
$x^n(\theta)$ to find one for this derivative:
\alx{
    D_q(g(x^n))&amp;=\frac{M_q(g(x^n))-g(x^n)}{M_q(x)-x}\cdot \frac{M_q(x^n)-x^n}{M_q(x^n)-x^n} \\
               &amp;=\frac{M_q(g(x^n))-g(x^n)}{M_q(x^n)-x^n}\cdot \frac{M_q(x^n)-x^n}{M_q(x)-x} \\
               &amp;=\frac{M_q(g(x^n))-g(x^n)}{M_q(x(x^n))-x(x^n)}\cdot D_q(x^n) \\
               &amp;=D_q(g)(x^n)\cdot D_q(x^n)                   
}
While the product and quotient rules (\ref{eq:prod1})-(\ref{eq:quot2})
are the same as those typically given \cite{KC02}, this rule differs:
since $q$ is the function $x^{p^j-1}$ instead of a constant, we
evaluate it at $x^n$ rather than take the $q^n$-derivative of $g$ in
the first term.


Finally, the $q$-numbers $[n]$ satisfy 
    $$[n+1] = q^0+q[n] \mbox{\;\;and\;\;} [n+1]-[n]=q^n.$$

\section{Constants}

Under what conditions does \al{d_q(x^n) &amp;= 0 \label{eq:homogen}?}  We
have
    $$M_q(x^n) - x^n=0$$ 
    which implies
    $$q^nx^n = x^n$$ 
    and
    $$q^n = x^{n(p^j-1)} = x^0 = 1$$ if $n\ne -\oo$.  Therefore, $D_q
x^n = 0$ if $(p^k-1)|n(p^j-1)$.  We call elements satisfying
(\ref{eq:homogen}) ``constants.''



Constants behave as one might expect.  Adding a constant obviously does not change the derivative; multiplying by a constant $m$ scales the derivative by the same amount:
\alx{
    D_q (mf) &amp;= f D_q(m) + M_q(m)D_q(f)  \\
             &amp;= f\cdot 0  + mD_q(f)  \\
             &amp;= m D_q(f)
}



\section{The exponential function exp}

Consider the equation $D_q x^e = x^e$.  Then
    $$D_q x^e = [e]x^{e-1} = x^e$$ $$[e]x^{-1}=x^0$$
    $$\frac{x^{es}-x^0}{x^s-x}=x^0$$ \al{ x^{es} &amp;= x^s-x+1
    \label{eq:exp} } so if $\theta^s-\theta+1$ is generated by
$\theta^s$ then the equation will hold for at least one $e$.  We may
then define the function $\exp = x^e$; there is no reason to prefer one
solution over another.


We use $\exp$ to illustrate a subtlety of the chain rule.  One might conclude that $D_q (\exp^m)=[m]x^{me+m-1}$:
\al{
    D_q x^{me} &amp;= D_q (x^e(x^m)) \nonumber \\
               &amp;= D_q (x^e)(x^m) \cdot D_q(x^m) \nonumber\\
               &amp;= x^e(x^m) \cdot [m]x^{m-1} \label{eq:bad} \\
               &amp;= x^{me} \cdot [m]x^{m-1} \nonumber \\
               &amp;= [m]x^{me+m-1} \nonumber
}
but (\ref{eq:bad}) does not follow.  It is only when applied directly
to $\theta$ that $D_qx^e=x^e$.  Here, $D_qx^e$ is applied to the
function $x^m$ and then to $\theta$.


The true equation may be found by examining the derivatives of the first few powers of $\exp$:
\alx{
    D_q (\exp^2) &amp;= D_q (x^{2e}) \\
               &amp;= D_q (x^e \cdot x^e) \\
               &amp;= x^e D_q(x^e) + M_q(x^e)D_q(x^e) \\
               &amp;= x^{2e} + q^e x^{2e} \\
               &amp;= (q^0(x^e)+q^1(x^e))\cdot (x^e)^2 \\
               &amp;= ([2]x^2)(x^e)
}\alx{
    D_q (\exp^3) &amp;= D_q (x^{3e}) \\
               &amp;= D_q (x^e\cdot x^{2e}) \\
               &amp;= x^{2e} D_q(x^e)+ M_q(x^e)D_q(x^{2e})  \\
               &amp;= x^{3e} + q^e\cdot (q^0+q^e) x^{3e} \\
               &amp;= (q^0(x^e) + q^1(x^e) + q^2(x^e)) (x^e)^3 \\
               &amp;= ([3]x^3)(x^e)
}
%where $$([m]x^m)(y) = \frac{q(y^m)-1}{q(y)-1}y^m.$$  
The pattern is immedately clear: $D_q(\exp^m)= ([m]x^m)(\exp)$, as one
would hope.


We can now prove the result by induction.  Assume that $D_q(\exp^{(m-1)})$ is of the form $\nobreak{([m-1]x^{m-1})(\exp)}$.  Then
\alx{
    D_q (\exp^m) &amp;= D_q(x^{me}) \\
               &amp;= D_q(x^ex^{(m-1)e}) \\
               &amp;= x^{(m-1)e} D_q(x^e) + M_q(x^e)D_q(x^{(m-1)e}) \\
               &amp;= x^{me} + q^ex^e \cdot ([m-1]x^{m-1})(x^e) \\
               &amp;= ((q^0+q[m-1])x^m)(x^e)\\
               &amp;= ([m]x^m)(x^e) \\
               &amp;= ([m]x^m)(\exp).
}


\section{Commutation}

As with the standard $q$-derivative, $[D_q,x\cdot] = M_q$:
\alx{
    [D_q,x\cdot](f)  &amp;= D_q(xf) - xD_q(f) \\
              &amp;= fD_q(x) + M_q(x)D_q(f) - xD_q(f) \\
              &amp;= f + qxD_q(f) - xD_q(f) \\
              &amp;= f + d_q(x)D_q(f) \\
              &amp;= (x + d_q(x)D_q)(f) \\
              &amp;= (x + d_q(x)\frac{d_q}{d_q(x)})(f) \\
              &amp;= (x + d_q)(f) \\
              &amp;= M_q(f)
}

If we define the $q$-commutator $[f,g]_q \equiv fg-M_q(g)f$, then we find that 
\alx{
    [D_q,x\cdot]_q(f) &amp;= D_q(xf) - M_q(x)D_q(f) \\
                &amp;= fD_q(x) + M_q(x)D_q(f) - M_q(x)D_q(f)\\
                &amp;= f.
}

We can define a Hamiltonian operator via the anticommutator $H=\lbrace D_q, x\cdot \rbrace$ to get
\alx{
    Hf &amp;= D_q(xf) + xD_q(f) \\
       &amp;= fD_q(x) + qxD_q(f) + xD_q(f) \\
       &amp;= f + [2]xD_q(f),
}
so the ``energy'' of a finite field element $x^n(\theta)$ is
\alx{
    Hx^n &amp;= x^n+[2]xD_q(x^n) \\
         &amp;= (1+[2][n]) x^n \\
         &amp;= (1+(1+q)[n]) x^n \\
         &amp;= (1+[n]+q[n]) x^n \\
         &amp;= ([n+1]+[n]) x^n
}

\section{$q$-Antiderivative}

The $q$-derivative of a finite field element is an element itself.  If
we add the constant $1$, the derivative does not change, so at most
half of the elements have antiderivatives.  If an element has an
antiderivative, then it is unique up to an additive constant: suppose
$f$ has two antiderivatives $F_1$ and $F_2$.  Then let $\phi=F_1-F_2$.
Now $D_q(\phi)=0$; but any function for which that holds true is a
constant by definition.

The integral operator $\int_q(d_q\cdot)$ is the Moore--Penrose inverse
of $D_q$.  Thus the equation $D_q(F)=f$ has a solution iff $f =
D_q(\int_q(fd_q)))$.

\section{Higher derivatives}
Because $[n]$ is a function of $x$, there are correction terms on the higher derivatives.  For instance,
\alx{
    D_q^2(x^n) &amp;= D_q(D_q(x^n)) \\
               &amp;= D_q([n]x^{n-1})\\
               &amp;= [n]D_q(x^{n-1}) + M_q(x^{n-1})D_q([n]) \\
               &amp;= [n][n-1]x^{n-2} + (qx)^{n-1}D_q([n])
}

It is these extra terms that give rise to trigonometric-like
functions.  We've already seen exp; there are others like sinh and cosh
with larger periods.

There will be a subspace, however, for which iterated derivatives
eventually yield zero.  This subspace always includes the vectors
$\lbrace x, 1\rbrace$, and may include more.

We can define an inner product in this subspace.  Let $J_q =
\int_q(d_q\cdot)$ and without loss of generality, let $n\geq m$.  Then
    $$\langle J_q^n,J_q^m\rangle = \langle 1,D_q^nJ_q^m\rangle =
    \delta_{n,m}.$$ The function exp is an eigenvector of $D_q$, so it
is orthogonal to the subspace:
    $$\langle J_q^n, \exp\rangle = \langle 1, D_q^n \exp\rangle =
    \langle 1,\exp\rangle = 0.$$ Other trigonometric functions are
    defined by the period with which they repeat.  sinh, for example,
is an eigenvector of $D_q^2$, and a similar identity holds.

\section{Logarithmic $q$-derivative}
The logarithmic derivative is defined as
    $$ \ld \equiv \frac{D_q}{x}. $$
The logarithmic derivative of a product of terms is the $q$-deformed sum of the logarithmic derivatives of the terms:
\alx{
    \ld(x^n \cdot x^m) &amp;= \frac{D_q(x^n \cdot x^m)}{x^n\cdot x^m} \\
                       &amp;= \frac{M_q(x^n) D_q(x^m) + x^m D_q (x^n)}{x^n\cdot x^m}\\
                       &amp;= \frac{M_q(x^n)}{x^n}\ld(x^m) + \ld(x^n) \\
                       &amp;= q^n \ld(x^m) + \ld(x^n) \\
                       &amp;= \ld(x^m) + q^m \ld(x^n)
}

The logarithmic derivative of powers of exp has a nice form:
    $$ \ld(\exp^n) = \frac{D_q(\exp^n)}{\exp^n} =
    \frac{([n]x^n)(\exp)}{\exp^n} = [n](\exp) $$ which suggests a
``natural discrete $q$-logarithm'' for finite field elements.  However,
while this logarithm is easy to compute, the $q$-deformed
multiplication necessary to solve the Diffie-Hellman problem is hard.


\section{Examples}
We consider the field GF($2^4$) with the field polynomial $x^4-x-1$.
There are three possible values $q$ may take: $x^1, x^3,$ and $x^7$.
Each gives rise to different structures.

\ctr{\begin{tabular}{lllll}
    $n$  &amp;$\theta^n$ &amp; $D_x(\theta^n)$ &amp; $D_{x^3}(\theta^n)$ &amp; $D_{x^7}(\theta^n)$\\
    \hline \\
    $-\oo$ &amp; 0000  &amp; 0000 &amp; 0000 &amp; 0000 \\
    0      &amp; 0001  &amp; 0000 &amp; 0000 &amp; 0000 \\
    1      &amp; 0010  &amp; 0001 &amp; 0001 &amp; 0001 \\
    4      &amp; 0011  &amp; 0001 &amp; 0001 &amp; 0001 \\
    2      &amp; 0100  &amp; 0110 &amp; 0001 &amp; 0111 \\
    8      &amp; 0101  &amp; 0110 &amp; 0001 &amp; 0111 \\
    5      &amp; 0110  &amp; 0111 &amp; 0000 &amp; 0110 \\
    10     &amp; 0111  &amp; 0111 &amp; 0000 &amp; 0110 \\
    3      &amp; 1000  &amp; 1111 &amp; 0111 &amp; 0101 \\
    14     &amp; 1001  &amp; 1111 &amp; 0111 &amp; 0101 \\
    9      &amp; 1010  &amp; 1110 &amp; 0110 &amp; 0100 \\
    7      &amp; 1011  &amp; 1110 &amp; 0110 &amp; 0100 \\
    6      &amp; 1100  &amp; 1001 &amp; 0110 &amp; 0010 \\
    12     &amp; 1101  &amp; 1001 &amp; 0110 &amp; 0010 \\
    11     &amp; 1110  &amp; 1000 &amp; 0111 &amp; 0011 \\
    13     &amp; 1111  &amp; 1000 &amp; 0111 &amp; 0011
\end{tabular}}

\subsection{$q=x$} 
We have constants 0, 1.  ``Trig'' functions include
$\theta^{10}=0111=\exp$, $\theta^{13}=1111=\sinh$, and
$\theta^3=1000=\cosh$.  The names we've chosen are fairly arbitrary;
they are only meant to reflect the period with which the derivative
returns to itself.  The element $\theta$ has no antiderivative, so we
have an inner product acting on the subspace $\lbrace 1, x \rbrace$ of
the space $\lbrace 1, x, \exp, \sinh \rbrace$.

\subsection{$q=x^3$} Nonzero constants are $\theta^0=1, \theta^5=0110,$
and $\theta^{10}=0111$, the cube roots of 1.  There are no trig
functions.  A basis for the space is $\lbrace 1, x \rbrace$.

\subsection{$q=x^7$} We have the constants 0, 1 and the trig function
exp.  In this case, $J_q\theta=\theta^6$, so we have the inner product
on a three-dimensional subspace $\lbrace 1, x, x^6 \rbrace$, while the
complete basis is $\lbrace 1, x, x^6, \exp \rbrace$.

\begin{thebibliography}{9}

\bibitem{CI03} G. L. Cohen and D. E. Iannucci, 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Cohen/cohen6.html}{Derived sequences}, 
{\it J. Integer Sequences} {\bf 6} 2003, Article 03.1.1.

\bibitem{KC02} V. Kac and P. Cheung, {\it Quantum Calculus},
Springer-Verlag, 2002.

\bibitem{KOW02} N. Kurokawa, H. Ochiai, and M. 
Wakayama,
\href{http://www.mathematik.uni-bielefeld.de/documenta/vol-kato/kurokawa_ochiai_wakayama.dm.html}{Absolute derivations and zeta functions},  {\it Doc.
Math.} 2003, Extra Vol., 565--584 (electronic).

\bibitem{UA03} V. Ufnarovski and B. \AA hlander, 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Ufnarovski/ufnarovski.html}{How to differentiate a number},
{\it J. Integer Sequences} {\bf 6} 2003, Article 03.3.4.
 
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A30; Secondary 11T99 .

\noindent \emph{Keywords:} $q$-calculus,
number derivative, arithmetic derivative. 

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 24 2004;
revised version received January 13 2005.  
Published in {\it Journal of Integer Sequences},
January 14 2005.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in


\end{document}

                                                                                

\end{document}
</pre></body></html>