\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)&= \frac{M_q(fg) - fg}{M_qx-x} \nonumber \\
&= \frac{M_q(f)M_q(g)-M_q(g)f+M_q(g)f-fg}
{M_q(x)-x} \nonumber \\
&= M_q(g)\frac{M_q(f)-f}{M_q(x)-x}+
f\frac{M_q(g)-g}{M_q(x)-x} \nonumber \\
&= M_q(g)D_q(f) + fD_q(g) \label{eq:prod1} \\
&= 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) &= D_q(g\frac{f}{g}) \nonumber \\
&= M_q(g)D_q(\frac{f}{g}) + \frac{f}{g}D_q(g), \nonumber
\intertext{we have}
D_q (\frac{f}{g}) &=\frac{gD_q(f)-fD_q(g)}{gM_q(g)} \label{eq:quot1}\\
&=\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))&=\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} \\
&=\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} \\
&=\frac{M_q(g(x^n))-g(x^n)}{M_q(x(x^n))-x(x^n)}\cdot D_q(x^n) \\
&=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) &= 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) &= f D_q(m) + M_q(m)D_q(f) \\
&= f\cdot 0 + mD_q(f) \\
&= 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} &= 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} &= D_q (x^e(x^m)) \nonumber \\
&= D_q (x^e)(x^m) \cdot D_q(x^m) \nonumber\\
&= x^e(x^m) \cdot [m]x^{m-1} \label{eq:bad} \\
&= x^{me} \cdot [m]x^{m-1} \nonumber \\
&= [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) &= D_q (x^{2e}) \\
&= D_q (x^e \cdot x^e) \\
&= x^e D_q(x^e) + M_q(x^e)D_q(x^e) \\
&= x^{2e} + q^e x^{2e} \\
&= (q^0(x^e)+q^1(x^e))\cdot (x^e)^2 \\
&= ([2]x^2)(x^e)
}\alx{
D_q (\exp^3) &= D_q (x^{3e}) \\
&= D_q (x^e\cdot x^{2e}) \\
&= x^{2e} D_q(x^e)+ M_q(x^e)D_q(x^{2e}) \\
&= x^{3e} + q^e\cdot (q^0+q^e) x^{3e} \\
&= (q^0(x^e) + q^1(x^e) + q^2(x^e)) (x^e)^3 \\
&= ([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) &= D_q(x^{me}) \\
&= D_q(x^ex^{(m-1)e}) \\
&= x^{(m-1)e} D_q(x^e) + M_q(x^e)D_q(x^{(m-1)e}) \\
&= x^{me} + q^ex^e \cdot ([m-1]x^{m-1})(x^e) \\
&= ((q^0+q[m-1])x^m)(x^e)\\
&= ([m]x^m)(x^e) \\
&= ([m]x^m)(\exp).
}
\section{Commutation}
As with the standard $q$-derivative, $[D_q,x\cdot] = M_q$:
\alx{
[D_q,x\cdot](f) &= D_q(xf) - xD_q(f) \\
&= fD_q(x) + M_q(x)D_q(f) - xD_q(f) \\
&= f + qxD_q(f) - xD_q(f) \\
&= f + d_q(x)D_q(f) \\
&= (x + d_q(x)D_q)(f) \\
&= (x + d_q(x)\frac{d_q}{d_q(x)})(f) \\
&= (x + d_q)(f) \\
&= 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) &= D_q(xf) - M_q(x)D_q(f) \\
&= fD_q(x) + M_q(x)D_q(f) - M_q(x)D_q(f)\\
&= f.
}
We can define a Hamiltonian operator via the anticommutator $H=\lbrace D_q, x\cdot \rbrace$ to get
\alx{
Hf &= D_q(xf) + xD_q(f) \\
&= fD_q(x) + qxD_q(f) + xD_q(f) \\
&= f + [2]xD_q(f),
}
so the ``energy'' of a finite field element $x^n(\theta)$ is
\alx{
Hx^n &= x^n+[2]xD_q(x^n) \\
&= (1+[2][n]) x^n \\
&= (1+(1+q)[n]) x^n \\
&= (1+[n]+q[n]) x^n \\
&= ([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) &= D_q(D_q(x^n)) \\
&= D_q([n]x^{n-1})\\
&= [n]D_q(x^{n-1}) + M_q(x^{n-1})D_q([n]) \\
&= [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) &= \frac{D_q(x^n \cdot x^m)}{x^n\cdot x^m} \\
&= \frac{M_q(x^n) D_q(x^m) + x^m D_q (x^n)}{x^n\cdot x^m}\\
&= \frac{M_q(x^n)}{x^n}\ld(x^m) + \ld(x^n) \\
&= q^n \ld(x^m) + \ld(x^n) \\
&= \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$ &$\theta^n$ & $D_x(\theta^n)$ & $D_{x^3}(\theta^n)$ & $D_{x^7}(\theta^n)$\\
\hline \\
$-\oo$ & 0000 & 0000 & 0000 & 0000 \\
0 & 0001 & 0000 & 0000 & 0000 \\
1 & 0010 & 0001 & 0001 & 0001 \\
4 & 0011 & 0001 & 0001 & 0001 \\
2 & 0100 & 0110 & 0001 & 0111 \\
8 & 0101 & 0110 & 0001 & 0111 \\
5 & 0110 & 0111 & 0000 & 0110 \\
10 & 0111 & 0111 & 0000 & 0110 \\
3 & 1000 & 1111 & 0111 & 0101 \\
14 & 1001 & 1111 & 0111 & 0101 \\
9 & 1010 & 1110 & 0110 & 0100 \\
7 & 1011 & 1110 & 0110 & 0100 \\
6 & 1100 & 1001 & 0110 & 0010 \\
12 & 1101 & 1001 & 0110 & 0010 \\
11 & 1110 & 1000 & 0111 & 0011 \\
13 & 1111 & 1000 & 0111 & 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}