Generalized Number Derivatives

Michael Stay Department of Computer Science University of Auckland Private Bag 92019 Auckland 1020 New Zealand

                      staym@clear.net.nz

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.

1 Introduction

The so-called “number derivative” seems to have been invented independently at least three times [3, 1, 4]. 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 [·] or by concatenation of symbols: x · x^{2} = xx^{2} = x^{3}. The notation x^{n} denotes a 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) ≠ g(f) · h(f).

1. 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 θ of the finite field GF(p^{k}) and express each finite field element as θ^{n}. Here, the parameter is θ.

2. 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 θ^{n} with the function x^{n}(y) = y^{n}.

3. Differentiate the function with respect to the parameters. The algorithm N computes D(f) = (∑_{i} \frac{∂}{∂x_{i}})(f). The algorithm S computes the s-derivative D_{s}(f).

4. 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=θ}.

2 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}(θ) is

D_{s}(x^{n})(θ) = \frac{M_{s}(x^{n}) − x^{n}}{M_{s}(x) − x} (θ) = \frac{x^{ns} − x^{n}}{x^{s} − x} (θ) = ([n]x^{n−1})(θ),

where

[n] ≡ \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 [2]. 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}(θ) is

D_{q}(x^{n})(θ) = \frac{M_{q}(x^{n}) − x^{n}}{M_{q}(x) − x} (θ) = \frac{q^{n}x^{n} − x^{n}}{qx − x} (θ) = ([n]x^{n−1})(θ),

where

[n] ≡ \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 θ.

3 Identities

For what functions q = x^{s−1}, if any, is this number derivative linear? Let θ^{a} + θ^{b} = θ^{c}. Then

D_{q}(x^{c})(θ) = \frac{x^{sc} − x^{c}}{x^{s} − x} (θ) = \frac{(θ^{a} + θ^{b})^{s} − θ^{c}}{θ^{s} − θ} .

On the other hand,

(D_{q}(x^{a}) + D_{q}(x^{b}))(θ) = \frac{x^{as} + x^{bs} − (x^{a} + x^{b})}{x^{s} − x}(θ) = \frac{θ^{as} + θ^{bs} − θ^{c}}{θ^{s} − θ} ,

so we want the cross terms in the binomial (θ^{a} + θ^{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:

D_{q}(fg) = \frac{M_{q}(fg) − fg}{M_{q}x − x}

= \frac{M_{q}(f)M_{q}(g) − M_{q}(g)f + M_{q}(g)f − fg}{M_{q}(x) − x}

= M_{q}(g)\frac{M_{q}(f) − f}{M_{q}(x) − x} + f \frac{M_{q}(g) − g}{M_{q}(x) − x}

= M_{q}(g)D_{q}(f) + fD_{q}(g)  (1)
= gD_{q}(f) + M_{q}(f)D_{q}(g),  (2)

where (2) follows by symmetry.

The same is true for the quotient rule. Since by (1),

D_{q}(f) = D_{q}(g \frac{f}{g})

= M_{q}(g)D_{q}(\frac{f}{g}) + \frac{f}{g} D_{q}(g),

we have

D_{q}(\frac{f}{g}) = \frac{gD_{q}(f) − fD_{q}(g)}{gM_{q}(g)}  (3)
= \frac{M_{q}(g)D_{q}(f) − M_{q}(f)D_{q}(g)}{gM_{q}(g)}  (4)

where (4) follows from (2) 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}(θ) to find one for this derivative:

D_{q}(g(x^{n})) = \frac{M_{q}(g(x^{n})) − g(x^{n})}{M_{q}(x) − x} · \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}} · \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})} · D_{q}(x^{n})

= D_{q}(g)(x^{n}) · D_{q}(x^{n})

While the product and quotient rules (1)-(4) are the same as those typically given [2], 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] and [n + 1] − [n] = q^{n}.

4 Constants

Under what conditions does

d_{q}(x^{n}) = 0?  (5)

We have

M_{q}(x^{n}) − x^{n} = 0

which implies

q^{n}x^{n} = x^{n}

and

q^{n} = x^{n(p^{j}−1)} = x^{0} = 1

if n ≠ −∞. Therefore, D_{q}x^{n} = 0 if (p^{k} − 1)|n(p^{j} − 1). We call elements satisfying (5) “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:

D_{q}(mf) = fD_{q}(m) + M_{q}(m)D_{q}(f)
= f · 0 + mD_{q}(f)
= mD_{q}(f)

5 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}

x^{es} = x^{s} − x + 1  (6)

so if θ^{s} − θ + 1 is generated by θ^{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}:

D_{q}x^{me} = D_{q}(x^{e}(x^{m}))
= D_{q}(x^{e})(x^{m}) · D_{q}(x^{m})
= x^{e}(x^{m}) · [m]x^{m−1}  (7)
= x^{me} · [m]x^{m−1}
= [m]x^{me+m−1}

but (7) does not follow. It is only when applied directly to θ that D_{q}x^{e} = x^{e}. Here, D_{q}x^{e} is applied to the function x^{m} and then to θ.

The true equation may be found by examining the derivatives of the first few powers of exp:

D_{q}(exp^{2}) = D_{q}(x^{2e})
= D_{q}(x^{e} · 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})) · (x^{e})^{2}
= ([2]x^{2})(x^{e})

D_{q}(exp^{3}) = D_{q}(x^{3e})

= D_{q}(x^{e} · x^{2e})

= x^{2e}D_{q}(x^{e}) + M_{q}(x^{e})D_{q}(x^{2e})

= x^{3e} + q^{e} · (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})

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 ([m − 1]x^{m−1})(exp). Then

D_{q}(exp^{m}) = D_{q}(x^{me})

= D_{q}(x^{e}x^{(m−1)e})

= x^{(m−1)e}D_{q}(x^{e}) + M_{q}(x^{e})D_{q}(x^{(m−1)e}) = x^{me} + q^{e}x^{e} · ([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).

6 Commutation

As with the standard q-derivative, [D_{q}, x·] = M_{q}:

[D_{q}, x·](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} ≡ fg − M_{q}(g)f, then we find that

[D_{q}, x·]_{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 = {D_{q}, x·} to get

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}(θ) is

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}

7 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 ϕ = F_{1} − F_{2}. Now D_{q}(ϕ) = 0; but any function for which that holds true is a constant by definition.

The integral operator ∫_{q}(d_{q}·) is the Moore–Penrose inverse of D_{q}. Thus the equation D_{q}(F) = f has a solution iff f = D_{q}(∫_{q}(fd_{q}))).

8 Higher derivatives

Because [n] is a function of x, there are correction terms on the higher derivatives. For instance,

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 {x, 1}, and may include more.

We can define an inner product in this subspace. Let J_{q} = ∫_{q}(d_{q}·) and without loss of generality, let n ≥ m. Then

⟨J_{q}^{n}, J_{q}^{m}⟩ = ⟨1, D_{q}^{n}J_{q}^{m}⟩ = δ_{n,m}.

The function exp is an eigenvector of D_{q}, so it is orthogonal to the subspace:

⟨J_{q}^{n}, exp⟩ = ⟨1, D_{q}^{n} exp⟩ = ⟨1, exp⟩ = 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.

9 Logarithmic q-derivative

The logarithmic derivative is defined as

ld ≡ \frac{D_{q}}{x} .

The logarithmic derivative of a product of terms is the q-deformed sum of the logarithmic derivatives of the terms:

ld(x^{n} · x^{m}) = \frac{D_{q}(x^{n} · x^{m})}{x^{n} · x^{m}}

= \frac{M_{q}(x^{n})D_{q}(x^{m}) + x^{m}D_{q}(x^{n})}{x^{n} · 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.

10 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.

\begin{matrix}n & θ^{n} & D_{x}(θ^{n}) & D_{x^{3}}(θ^{n}) & D_{x^{7}}(θ^{n}) \\ −∞ & 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{matrix}

10.1 q = x

We have constants 0, 1. “Trig” functions include θ^{10} = 0111 = exp, θ^{13} = 1111 = sinh, and θ^{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 θ has no antiderivative, so we have an inner product acting on the subspace {1, x} of the space {1, x, exp, sinh}.

10.2 q = x^{3}

Nonzero constants are θ^{0} = 1, θ^{5} = 0110, and θ^{10} = 0111, the cube roots of 1. There are no trig functions. A basis for the space is {1, x}.

10.3 q = x^{7}

We have the constants 0, 1 and the trig function exp. In this case, J_{q}θ = θ^{6}, so we have the inner product on a three-dimensional subspace {1, x, x^{6}}, while the complete basis is {1, x, x^{6}, exp}.

References

[1] G. L. Cohen and D. E. Iannucci, Derived sequences, J. Integer Sequences 6 2003, Article 03.1.1.

[2] V. Kac and P. Cheung, Quantum Calculus, Springer-Verlag, 2002.

[3] N. Kurokawa, H. Ochiai, and M. Wakayama, Absolute derivations and zeta functions, Doc. Math. 2003, Extra Vol., 565–584 (electronic).

[4] V. Ufnarovski and B. Åhlander, How to differentiate a number, J. Integer Sequences 6 2003, Article 03.3.4.

2000 Mathematics Subject Classification: Primary 05A30; Secondary 11T99 . Keywords: q-calculus, number derivative, arithmetic derivative.

Received August 24 2004; revised version received January 13 2005. Published in Journal of Integer Sequences, January 14 2005.

Return to Journal of Integer Sequences home page.