Derivatives over Certain Finite Rings

Show more

1. Introduction

Derivative plays a very fundamental role in the analysis of functions over the real and the complex number fields. In these fields, their properties and applications are well-studied, since they reflect well on our everyday lives. Over finite rings the notion of a derivative first appeared some 75 year ago in the paper by Hasse [2] . This derivative is the so called Hasse derivative, and has been successfully used in areas where finite fields play an important role, such as Coding Theory as reported by Massey, von Seeman, Schoeller [3] .

Suppose that R is a commutative ring and let $f\left(x\right)={\displaystyle {\sum}_{n=1}^{n}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{a}_{i}{x}^{i}$ be a polynomial

over R. Then rth-Hasse derivative of $f\left(x\right)$ is ${f}^{\left[r\right]}\left(x\right)={\displaystyle {\sum}_{i=0}^{n}}\left(\begin{array}{c}i\\ r\end{array}\right){a}_{i}{x}^{i-r}$ with $\left(\begin{array}{c}i\\ r\end{array}\right)=0$ for $i<r$ . It is well-known that over a finite field K all functions

are polynomial. In fact, if $\left|K\right|=m$ , then there are ${m}^{m}$ functions over K. In addition, there is a 1-1 correspondence between a function $f\mathrm{:}K\to K$ and polynomial of degree less than m. So with Hasse derivatives one has every thing as far as a derivative of a function over K.

If R is a finite commutative ring, then only a fraction of functions on R are polynomials as shown by Frisch [4] . So for a function $f$ on R which can not be represented by a polynomial over R, its Hasse derivative can not be determined. The aim of this paper is to introduce a derivative on a set of relations on certain rings.

Suppose that R is a finite ring and consider a relation $\rho $ on R in a variable x, which shall be usually denoted by $\rho \left(x\right)$ . Then the image of $\rho $ may sometimes be an array, see de Souza, de Oliveira, de Souza, Vasconcelos [5] . For instance, the image of a function on R is an $s\times 1$ -array. In Section 2 we will look into exponential relations and their arrays over the ring $R={\mathbb{Z}}_{n}$ for an integer n, and then we give sufficient conditions for an exponential relation to be a function over R.

Let R be the finite ring ${\mathbb{Z}}_{n}$ , where n is an odd integer. Given a relation $\rho $ , and a point $a\in R$ , what should be the derivative of $\rho $ at a? In real analysis we take the slope of a tangent line at a, provided it exists. Moreover for a relation on the real number fields, we have at lest one slope at a point: one along each column (picture the derivative of $\sqrt{x}$ ). Over a finite field this is not possible, because a point has more than one tangent! In addition, slopes of tangents can be computed along a column of $\rho $ as well as across it. In Section 3 we show that the slope of the closest secant to a point $x\in R$ along a column k is the best candidate for the derivative of $\rho $ at x, which shall be denoted by $D{r}_{k}^{\left(1\right)}\left(\rho \left(x\right)\right)$ or simply ${\rho}_{k}^{\left(1\right)}\left(x\right)$ , the k-th derivative of $\rho $ at x. This derivative has similar properties as the derivative of the real number field, like: linearity; product and quotient rules and how it acts on polynomials and exponential relations. The definition of the derivative requires some ordering of the elements of R. In Section 1, we consider the ring R as cyclically ordered set, which is very natural since R is a finite set.

Let $R={\mathbb{F}}_{q}$ be a finite field with q elements and let $\rho \mathrm{:}R\to R$ be a relation. Define the set of directions of $\rho $ (slopes of secants of the graph of $\rho $ ) by:

$D\left(\rho \right):=\left\{\frac{\rho \left(a\right)-\rho \left(b\right)}{a-b}|a\ne b\in R\right\}$ (1)

The problem of determining the bound on the size of $D\left(\rho \right)$ has be studied extensively both geometrically and combinatorically. The problem was first examined Blockhuis, Ball, Brouwer, Storme and Szonyi [6] , then by Ball [7] [8] who has done an extensive investigation. However, there has not been any attempt on computing the directions themselves, so far.

Given a graph of a column of a relation $\rho $ over R, the size s of the graph is the number of elements in the domain of $\rho $ . Note that s is less than or equal to q. Now, ideally if one want to find all directions, one may have to compute up to $s\left(s-1\right)/2$ directions. The algorithm is as follow: you start at the first point and then find $s-1$ directions, then move to the second point and compute $s-2$ directions, and so on. Since $D\left(\rho \right)$ is a subset of R, as show by Ball [8] [9] , there is a lot of unnecessary computations in this algorithm. In Section 4 we show that for some relations $\rho $ over prime fields, the derivatives of ${\rho}_{k}$ is all one needs to find all the directions of the graph of $\rho $ .

2. Preliminaries

In this section we collect some of the preliminaries that will be needed in this paper. We fix the following notation: If R is a ring with unity, then ${R}^{\mathrm{*}}$ will denote the group of units of R. Unless otherwise specified, by order of an element $a\in R$ we mean the multiplicative order of a.

Throughout the paper, ${\mathbb{Z}}_{n}$ will denote the set all modulo integers $amodn$ , which is a class containg all integers b such that $n\mathrm{|}\left(b-a\right)$ . The $gcd\left(a\mathrm{,}b\right)$ denote the greatest common divisor of integers a and b, which is unique.

2.1. Immediate Successor and Predecessor

Most people are very familiar with linear ordering. However, cyclic order is not a household term. We give a formal definition of cyclic order and use it to define some terminologies as explained by Garcia-Colin, Montejano, Montejano, Oliveros [10] .

Let X be a set of at least 3 elements. A ternary relation C is a subset of the Cartesian product $X\times X\times X$ which satisfies the following axioms:

1) Cyclicity: if $\left[a\mathrm{,}b\mathrm{,}c\right]$ is in C, then $\left[b\mathrm{,}c\mathrm{,}a\right]$ is in C.

2) Asymmetry: if $\left[a\mathrm{,}b\mathrm{,}c\right]$ is in C, then $\left[c\mathrm{,}b\mathrm{,}a\right]$ is not in C.

3) Transitivity: if $\left[a\mathrm{,}b\mathrm{,}c\right]$ and $\left[a\mathrm{,}c\mathrm{,}d\right]$ are in C, then $\left[a\mathrm{,}b\mathrm{,}d\right]$ is in C.

4) Totality or Completeness: if a, b and c are distinct, then either $\left[a\mathrm{,}b\mathrm{,}c\right]$ is in C or $\left[c\mathrm{,}b\mathrm{,}a\right]$ is in C.

If C satisfies the first three axioms, then it is called partial cyclic ordering on X, and consequently the pair $\left(X\mathrm{,}C\right)$ is a partially cyclically ordered set. If C satisfies all four axioms, it is called (total) cyclic ordering on X, as a result we get cyclically ordered set $\left(X\mathrm{,}C\right)$ .

If a cyclically ordered set X is finite of cardinality n, then there is a 1-1 correspondence between X and the cyclically ordered set $\left\{\mathrm{1,2,}\cdots \mathrm{,}n\mathrm{,1}\right\}$ . We can use this correspondence to identify positions on X. Now, let X be a finite cyclically ordered set and let $x\in X$ be at position i (using the above correspondence), where i is an integer. Then the element in the position $i+1$ will be called an immediate successor of x, and will be denoted by ${x}_{+}$ , while that in the position $i-1$ will be called immediate predecessor of x and will be denoted by ${x}_{-}$ .

2.2. Unity Ordering

Let G be a finite group. The cyclic orderings on G which are of interest to us, are those that depend on generators of the group and the binary operation of the group. For example, for the additive group ${\mathbb{Z}}_{5}$ , we have the orderings $\left\{\mathrm{1,2,3,4,0}\right\}$ , $\left\{\mathrm{3,1,4,2,0}\right\}$ , $\left\{\mathrm{2,4,1,3,0}\right\}$ and $\left\{\mathrm{4,3,2,1,0}\right\}$ , while for the multiplicative group ${\mathbb{Z}}_{5}^{\mathrm{*}}$ we have orderings $\left\{\mathrm{2,4,3,1}\right\}$ and $\left\{\mathrm{3,4,2,1}\right\}$ . Given a generator g of a finite cyclic group, if the group is additive, then the ordering determined by g will be referred to g-additive cyclic ordering, where as if the group is multiplicative, then the ordering will be referred to as g-multiplicative cyclic ordering.

Suppose that G is a finite cyclically ordered group of order $n\ge 3$ with a binary operation. Then G has at least one cyclic ordering, namely the one determined by each generator of G. For $a\mathrm{,}b\in G$ , define the length from a to b, denoted by $l\left(a\mathrm{,}b\right)$ , to be $b\ast {a}^{-1}\in G$ , where ${a}^{-1}$ is the inverse of a. For example, in the cyclically ordered set ${\mathbb{Z}}_{5}=\left\{\mathrm{0,4,3,2,1}\right\}$ , we have that $l\left(0,3\right)=3,l\left(2,2\right)=0$ , while for the multiplicative group ${\mathbb{Z}}_{5}^{\mathrm{*}}=\left\{\mathrm{1,3,4,2}\right\}$ modulo 5 which is cyclically ordered, we have $l\left(1,3\right)=3$ and $l\left(3,2\right)=4$ .

Now, for our group G above, we have that every element $a\in G$ has an immediate predecessor and successor. Then the length $l\left(a\mathrm{,}{a}^{+}\right)$ will be referred to as the least length of a, and will be denoted by $\delta \left(a\right)$ . For example, for multiplicative cyclically ordered group ${\mathbb{Z}}_{5}^{\mathrm{*}}=\left\{\mathrm{1,2,4,3}\right\}$ , we have that $\delta \left(x\right)=3$ for all $x\in {\mathbb{Z}}_{5}^{\mathrm{*}}$ . The following fact can be easily proved.

Fact 1.1. Let R be a ring with unity ${1}_{R}$ and isomorphic to the ring ${\mathbb{Z}}_{n}$ .

1) For any additive ordering on R the least length $\delta \left(a\right)=\delta $ is constant for all $a\in R$ .

2) There is an additive ordering on R such that $\delta \left(a\right)=\delta ={1}_{R}$ .

The cyclic ordering of Fact 1.1 (2) on a ring R will be called the unity ordering.

For the rest of the paper, we impose the following assumption on our ring R:

Assumption 1.2. R is the ring ${\mathbb{Z}}_{q}$ where q is an odd integer. Moreover, the ordering on R is the associated additive cyclic ordering.

Remark 1.3. Under the above assumption our ring R will have a canonical cyclic ordering, which will be fundamental throughout the paper. Moreover, no matter what additive cyclic ordering one takes on R, the element ${x}_{+}-{x}_{-}\in R$ will be a unit, since the ordering is determined by a generator of R.

3. Exponential and Hyperbolic Relations over R

In real analysis, exponential functions ${\alpha}^{x}$ are very fundamental, and they can easily be used to define other functions. Over finite ring, the mapping determined by ${\alpha}^{x}$ , for a unit $\alpha $ , is not necessarily a function. We have the following definition, which is motivated by de Souza, de Oliveira, Kauffman, Paschoal [5] and de Souza, de Oliveira, Kauffman, Paschoa [11] .

Definition 2.1. Let $\alpha \in R$ be a unit of order N. Then, the exponential relation $\rho \mathrm{:}R\to R$ is the relation $\rho \left(x\right)={\alpha}^{x}$ . The image of $\rho $ is an $N\times t$ -array $\left[{\rho}_{i}\left(x\right)\right]$ with the a-th row, $\rho \left(a\right)=\left\{{\alpha}^{a},{\alpha}^{a+q},\cdots ,{\alpha}^{a+\left(t-1\right)q}\right\}$ , where $t\le N$ . The k-th column of $\rho $ , ${\rho}_{k}\left(x\right)={\alpha}^{x+kq}$ , where $x=0,1,\cdots ,N-1$ , will be called the k-th exponential relation of $\rho $ .

Example 1. We consider examples:

1) Let $R={\mathbb{Z}}_{7}$ and consider the relation $\rho \left(x\right)=2x\mathrm{mod}7$ . Then the array of $\rho $ is

$\left[{\rho}_{k}\left(x\right)\right]=\left[\begin{array}{ccc}{2}^{0}& {2}^{7}& {2}^{14}\\ {2}^{1}& {2}^{8}& {2}^{15}\\ {2}^{2}& {2}^{9}& {2}^{16}\end{array}\right]=\left[\begin{array}{ccc}{2}^{0}& {2}^{1}& {2}^{2}\\ {2}^{1}& {2}^{2}& {2}^{3}\\ {2}^{2}& {2}^{3}& {2}^{1}\end{array}\right]=\left[\begin{array}{ccc}1& 2& 4\\ 2& 4& 1\\ 4& 1& 2\end{array}\right]$

2) If $R={\mathbb{Z}}_{9}$ and our relation is $\rho \left(x\right)={2}^{x}$ , then the array of $\rho $ is

$\left[{\rho}_{k}\left(x\right)\right]=\left[\begin{array}{ccc}{2}^{0}& {2}^{9}& {2}^{18}\\ {2}^{1}& {2}^{10}& {2}^{19}\\ {2}^{2}& {2}^{11}& {2}^{20}\\ {2}^{3}& {2}^{12}& {2}^{21}\\ {2}^{4}& {2}^{13}& {2}^{22}\\ {2}^{5}& {2}^{14}& {2}^{23}\end{array}\right]=\left[\begin{array}{cc}1& 8\\ 2& 7\\ 4& 5\\ 8& 1\\ 7& 2\\ 5& 4\end{array}\right]$

Computation of the array of the relation in Example 1 (1.) looks easy, because along columns and rows one just increases the power by one. This is generally true for prime fields.

Lemma 2.2. If R is a prime field, and $\rho \left(x\right)={\alpha}^{x}$ is a relation on R, then the k-th relation of $\rho $ is ${\rho}_{k}\left(x\right)={\alpha}^{x+k}$ .

Proof. We have that $kq\mathrm{mod}N=kq-k+k\mathrm{mod}N=k\left(q-1\right)+k\mathrm{mod}N=k\mathrm{mod}N$ , since $N\mathrm{|}q-1$ . □

Consider the relation $\rho \left(x\right)={\alpha}^{x}$ , where $\alpha \in R$ has order N. Then ${\rho}_{i}\left(x\right)$ has N rows. However, as shown in the example above the number of columns may vary. If certain condition are satisfied, then the number of columns of the array of $\rho $ can easily be obtained.

Theorem 2.3. Let $\alpha $ be a unit in R of order N, and let $\rho \left(x\right)={\alpha}^{x}$ be a relation.

1) If a perfect square is not a factor of q and $\mathrm{gcd}\left(N,q\right)=1$ , then $\left[{\rho}_{i}\left(x\right)\right]$ is an $N\times N$ -array.

2) If $q={p}^{m}$ for a prime p, where m is a positive integer, then there are $gcd\left(N\mathrm{,}p-1\right)$ columns in $\left[{\rho}_{i}\left(x\right)\right]$ .

Proof. Suppose that $\left[{\rho}_{i}\left(x\right)\right]$ is an $s\times t$ -array, and let the a-th row be $\rho \left(a\right)=\left\{{\alpha}^{a},{\alpha}^{a+q},{\alpha}^{a+2q},\cdots ,{\alpha}^{a+\left(t-1\right)q}\right\}$ . Then $\rho \left(a\right)$ is a coset of the subgroup $H=\langle {\rho}^{iq}\rangle $ of ${R}^{\mathrm{*}}$ of order t. One can then observe that for both cases, $s=N$ and $tN$ .

1) Now ${\alpha}^{a}={\alpha}^{a+tq}$ means that $tq=0\mathrm{mod}N$ which is implies that $N\mathrm{|}tq$ . But since N does not divide q, it must divide t. Hence $t=N$ .

2) We have that $H\le \langle \alpha \rangle $ , since H contains power of $\alpha $ . Let K be a subgroup of ${R}^{\mathrm{*}}$ of order $p-1$ . Since $\mathrm{gcd}\left({p}^{n-1},p-1\right)=1$ , then ${R}^{\mathrm{*}}\simeq {\mathbb{Z}}_{{p}^{n-1}}\oplus {\mathbb{Z}}_{p-1}$ , and hence K is unique. From this we infer that if $\beta \in {R}^{\mathrm{*}}$ is such that ${\beta}^{p-1}=1$ , then $\beta \in K$ . Now we have that ${\left({\alpha}^{iq}\right)}^{p-1}={\left({\alpha}^{\varphi \left(q\right)}\right)}^{ip}=1$ for $i=1,\cdots ,t$ , so that $H\le K$ . Hence $t\mathrm{|}N$ and $t\mathrm{|}p-1$ , which implies that $t\le \mathrm{gcd}\left(N,p-1\right)=d$ . If $d<t$ , then ${\alpha}^{dq}={\alpha}^{sNq+r\left(p-1\right)q}=1$ , so that $\left|H\right|<t$ , a contradiction. □

The following corollary gives a sufficient condition for an exponential relation on R to be a function.

Corollary 2.4. Suppose that $\alpha \in R$ is unit of order N.

1) If a perfect square is not a factor of q and $N\mathrm{|}q$ , then the relation $\rho \left(x\right)={\alpha}^{x}$ is a function.

2) If $q={p}^{m}$ for a prime p and $\alpha $ has order ${p}^{i}$ for $i=1,\cdots ,m-1$ , then the relation $\rho \left(x\right)\mathrm{=}{\alpha}^{x}$ is a function.

Proof. 1) For all $a\in R$ and some positive integer t, we have that $\rho \left(a\right)=\left\{{\alpha}^{a},{\alpha}^{a+q},\cdots ,{\alpha}^{a+\left(t-1\right)q}\right\}=\left\{{\alpha}^{a}\right\}$ , since $N\mathrm{|}q$ .

2) Follows from Theorem 2.3, since $\mathrm{gcd}\left({p}^{i},p-1\right)=1$ for $i=1,\cdots ,m-1$ . □

Let $\alpha \in R$ be a unit of order N, and consider the relation $\rho \left(x\right)={\alpha}^{x}$ . Then $\rho $ is periodic of period N. More precisely, for a positive integer s each subset ${S}_{j}=\left\{jN\mathrm{,}jN+\mathrm{1,}\cdots \mathrm{,}\left(j+1\right)N-1\right\}$ of the domain of $\rho $ , where $j=0,1,\cdots ,s-1$ , determines the same image $\rho \left({S}_{j}\right)=\left\{\rho \left(jN\right),\rho \left(jN+1\right),\cdots ,\rho \left(\left(j+1\right)N-1\right)\right\}$ . The subset ${S}_{j}$ is referred to as the j-th steps of $\rho $ . As expected, starting at a point in R, there are only a finite number of steps of $\rho $ before one gets back to the same point.

Proposition 2.5. Let $\alpha \in R$ be a unit of order N, and consider the relation $\rho \left(x\right)={\alpha}^{x}$ . If $\mathrm{gcd}\left(N,q\right)=d$ , then $\rho $ has $q/d$ steps.

Proof. Let $\nu $ be the least positive integer with the property that the set $T=\left\{0,N,2N,\cdots ,\left(\nu -1\right)N\right\}$ taken $modq$ has distinct elements. Observe that find number of steps of $\rho $ is the same as finding the cardinality $\nu $ of T. Also note that $\nu \le q/d$ . If $\nu >q/d$ , then $\left|T\right|<\nu $ , a contradiction. □

Corollary 2.6. Let $\alpha \in R$ be a unit of order N, and consider the relation $\rho \left(x\right)={\alpha}^{x}$ . Then the map $\pi ={\rho}_{|{S}_{j}}:{S}_{j}\to \mathrm{Im}\rho $ is a permutation.

Proof. Only need to show that $\pi $ is 1-1. Suppose that $\pi \left(jN\right)=\pi \left(jN+k\right)$ for $k\ne 0modN$ . Then ${\alpha}^{jN}={\alpha}^{jN+k}$ which is equivalent to $k=0\mathrm{mod}N$ , a contradiction. □

We now define hyperbolic relations over R.

Definition 2.7. Let $\alpha \in R$ be a unit of order $N\ge 3$ . Then

1) The k-th hyperbolic sine and cosine relations to the base $\alpha $ over R, denoted by $cos{h}_{\alpha \mathrm{,}k}\left(x\right)$ and $sin{h}_{\alpha \mathrm{,}k}\left(x\right)$ are respectively

${\mathrm{cosh}}_{\alpha ,k}\left(x\right):=\frac{{\alpha}^{x+kq}+{\alpha}^{-\left(x+kq\right)}}{{x}_{+}-{x}_{-}};\text{\hspace{0.17em}}{\mathrm{sinh}}_{\alpha ,k}\left(x\right):=\frac{{\alpha}^{x+kq}-{\alpha}^{-\left(x+kq\right)}}{{x}_{+}-{x}_{-}}.$ (2)

2) The hyperbolic since and cosine relations to the base $\alpha $ , denoted by $cos{h}_{\alpha}\left(x\right)$ and $sin{h}_{\alpha}\left(x\right)$ are the relations with images the $N\times t$ -arrays made by the columns $cos{h}_{\alpha \mathrm{,}k}\left(x\right)$ and $sin{h}_{\alpha \mathrm{,}k}\left(x\right)$ , respectively, where $t<N$ .

Under certain assumption on R, hyperbolic relations on R behave like those over the real.

Proposition 2.8. Suppose that R has the unity ordering, and let $\alpha \in R$ be a unit of order $N\ge 3$ . Then for $k=0,1,\cdots ,N-1$ :

1) the identity ${\mathrm{cosh}}_{\alpha ,k}^{2}\left(x\right)-{\mathrm{sinh}}_{\alpha ,k}^{2}\left(x\right)={1}_{R}$ holds,

2) $cos{h}_{\alpha \mathrm{,}k}\left(-x\right)=cos{h}_{\alpha \mathrm{,}k}\left(x\right)$ and $sin{h}_{\alpha \mathrm{,}k}\left(-x\right)=-sin{h}_{\alpha \mathrm{,}k}(x)$

Proof. Follows from the definition. □

4. Derivatives and Their Properties

Denote the set of relations from R to R whose image are $s\times t$ -arrays by $Re{l}_{st}\left(R\right)$ , and by $Fun\left(R\right)$ the set of all functions from R to R.

Let q be the order of the ring R and let $x\in R$ . For a positive integer k and a relation $\rho \in Re{l}_{st}\left(R\right)$ , define a map $D{r}_{k}^{\left(1\right)}\mathrm{:}Re{l}_{st}\left(R\right)\to Re{l}_{st}\left(R\right)$ on the k-th relation ${\rho}_{k}$ of $\rho $ by

$D{r}_{k}^{\left(1\right)}\left(\rho \right)\left(x\right)\mathrm{:}=\frac{{\rho}_{k}\left({x}_{+}+kq\right)-{\rho}_{k}\left({x}_{-}+kq\right)}{{x}_{+}-{x}_{-}}\mathrm{.}$ (3)

If the context is clear, then $D{r}_{k}^{\left(1\right)}\left(\rho \right)\left(x\right)$ will be just denoted by ${\rho}_{k}^{\left(1\right)}\left(x\right)$ .

If one looks closely at the this map one will notice that its value at a point $x\in R$ is the slope of the closest secant to the point x along ${\rho}_{k}$ . It can be also interpreted as the average of the two closest slopes to x along ${\rho}_{k}$ . The result below show that the transformation has good properties too.

Theorem 3.1. Let $\rho \mathrm{,}\gamma \in Re{l}_{st}\left(R\right)\mathrm{,}x\in R$ and let $c\in \mathbb{Z}$ . Then

1) the transformation $D{r}_{k}^{\left(1\right)}$ is linear.

2) Product Rule:

${\left({\rho}_{k}{\gamma}_{k}\right)}^{\left(1\right)}\left(x\right)={\rho}_{k}\left({x}_{-}+kq\right){\gamma}_{k}^{\left(1\right)}\left(x\right)+{\gamma}_{k}\left({x}_{+}+kq\right){\rho}_{k}^{\left(1\right)}\left(x\right)$ (4)

$={\rho}_{k}\left({x}_{+}+kq\right){\gamma}_{k}^{\left(1\right)}\left(x\right)+{\gamma}_{k}\left({x}_{-}+kq\right){\rho}_{k}^{\left(1\right)}\left(x\right)\mathrm{.}$ (5)

3) Quotient rule: If ${\gamma}_{k}\left(x\right)\ne 0$ for all $x\in R$ , then

${\left(\frac{{\rho}_{k}}{{\gamma}_{k}}\right)}^{\left(1\right)}=\frac{{\gamma}_{k}\left({x}_{-}+kq\right){\rho}_{k}^{\left(1\right)}\left(x\right)-{\rho}_{k}\left({x}_{-}+kq\right){\gamma}_{k}^{\left(1\right)}\left(x\right)}{\gamma \left({x}_{+}+kq\right){\gamma}_{k}\left({x}_{-}+kq\right)}$ (6)

Proof. 1) Follows easily.

2) We use the elementary + tricks.

${\left({\rho}_{k}{\gamma}_{k}\right)}^{\left(1\right)}\left(x\right)=\frac{\left({\rho}_{k}{\gamma}_{k}\right)\left({x}_{+}+kq\right)-\left({\rho}_{k}{\gamma}_{k}\right)\left({x}_{-}+kq\right)}{{x}_{+}-{x}_{-}}$ (7)

$=\frac{{\rho}_{k}\left({x}_{+}+kq\right){\gamma}_{k}\left({x}_{+}+kq\right)-{\rho}_{k}\left({x}_{-}+kq\right){\gamma}_{k}\left({x}_{-}+kq\right)}{{x}_{+}-{x}_{-}}$ (8)

$={\rho}_{k}\left({x}_{-}+kq\right){\gamma}_{k}^{\left(1\right)}\left(x\right)+{\gamma}_{k}\left({x}_{+}+kq\right){\gamma}_{k}^{\left(1\right)}\left(x\right)$ (9)

3) Exercise. □

Remark 3.2. If R is a prime field, then (3) and its subsequent formulas in Theorem 3.1 become much easier, by the use of Lemma 2.2.

Example 2. Let us look into examples:

1) Let p be an odd prime number and consider the ring ${\mathbb{Z}}_{p}$ with the associated additive cyclic ordering. Let $f\left(x\right)=ax\mathrm{mod}p$ . Then for each $x\in {\mathbb{Z}}_{p},\rho \left(x\right)=1\in {\mathbb{Z}}_{p}$ , so that ${x}_{+}-{x}_{-}=2$ is a unit in ${\mathbb{Z}}_{p}$ . So,

${f}^{\left(1\right)}\left(x\right)=\frac{a\left(x+1\right)-a\left(x-1\right)}{2}=a$ . For $g\left(x\right)=b{x}^{2}\mathrm{mod}p$ , we have that

${g}^{\left(1\right)}\left(x\right)=2bx$ .

2) Let $R={\mathbb{Z}}_{9}$ has the unity ordering, and consider the relation $\rho \in Rel\left(R\right)$ given by $\rho \left(x\right)=2x$ . Then the image of $\rho $ is $6\times 2$ -array with columns ${\rho}_{0}\left(x\right)=\left\{{2}^{0}{\mathrm{,21,2}}^{2}{\mathrm{,2}}^{3}{\mathrm{,2}}^{4}{\mathrm{,2}}^{4}\right\}$ and ${\rho}_{1}\left(x\right)=\left\{{2}^{3}{\mathrm{,2}}^{4}{\mathrm{,2}}^{5}{\mathrm{,2}}^{0}{\mathrm{,2}}^{1}{\mathrm{,2}}^{2}\right\}$ . One can verify that ${\rho}_{0}^{\left(1\right)}\left(x\right)=\left\{\mathrm{3,6,3,6,3,6}\right\}$ and ${\rho}_{1}^{\left(1\right)}\left(x\right)=\left\{\mathrm{6,3,6,3,6,3}\right\}$ for $x\in R$ .

3) Consider the ring ${\mathbb{Z}}_{35}$ , and let $R=5{\mathbb{Z}}_{35}=\left\{\mathrm{0,5,10,15,20,25,30}\right\}$ . Then R is a ring modulo 35 whose unity ${1}_{R}=15$ . If one considers the given cyclic ordering on R, then for each $x\in R$ , $\delta \left(x\right)=\delta =5$ and ${x}_{+}-{x}_{-}=2\delta =10$ which is a unit in R. Consider the relation $\rho \left(x\right)={25}^{5x}\mathrm{mod}35$ on R. Then the image of $\rho $ is a $3\times 3$ -array, and we have that ${\rho}_{0}^{\left(1\right)}\left(x\right)=\left\{25,15,30\right\}$ , ${\rho}_{1}^{\left(1\right)}\left(x\right)=\left\{15,30,25\right\}$ and ${\rho}_{2}^{\left(1\right)}\left(x\right)=\left\{\mathrm{30,25,15}\right\}$ for $x\in R$ .

The computation in Example 2.3 (1) and (2) would not be very clear as far as ${\rho}_{k}^{\left(1\right)}\left(0\right)$ is concerned. But we used the following result.

Lemma 3.3. Suppose $\rho \in R$ is a unit of order $N\ge 3$ , and let $\rho \left(x\right)={\alpha}^{x}$ be a relation on R. Then $\rho \left(k\right)=\rho \left(sN+j\right)$ , for all integers $j\mathrm{,}s$ . In particular, $\rho \left(0\right)=\rho \left(N\right)$ , $\rho \left(-1\right)=\rho \left(N=1\right)$ and $\rho \left(N+1\right)=\rho \left(1\right)$ .

Proof. We have that $\rho \left(j\right)={\alpha}^{j}={\alpha}^{sN+j}=\rho \left(sN+j\right)$ . □

From the above theorem we see that the transformation ${\rho}_{k}^{\left(1\right)}$ looks indeed like a derivative on $Re{l}_{st}\left(R\right)$ . For, when applied to a constant function it vanishes, and when applied to a polynomial of degree two it gives a polynomial of degree one, and so on. Also, when the transformation is applied to an exponential relation over R, it produces the relation times a constant. The above behavior are similar to those seen in the derivative transformation of real functions.

Definition 3.4. Let $\rho $ be a relation on R and let $x\in R$ . If ${\rho}_{k}^{\left(1\right)}\left(x\right)$ is defined, then it will be called the k-th derivative of the relation $\rho $ at x, and will be denoted by ${\rho}_{k}^{\left(1\right)}\left(x\right)$ .

In the real analysis case we are used to very nice derivative formulas for functions. The situation here is the similar, and we have the following result.

Corollary 3.5. Let R has unity ${1}_{R}$ and let $\delta $ be the least length. If $\alpha \in R$ is a unit and n is a nonnegative integer greater than 1, then

${\left({\alpha}^{x}\right)}_{k}^{\left(1\right)}\left(x\right)=\frac{\left({\alpha}^{2\delta}-{1}_{R}\right)}{2\delta {\alpha}^{\delta}}{\alpha}^{x+kq}$ (10)

${\left({x}^{n}\right)}^{\left(1\right)}\left(x\right)={\displaystyle \underset{i=0}{\overset{s}{\sum}}}\left(\begin{array}{c}n\\ 2i+1\end{array}\right){x}^{n-\left(2i+1\right)}{\delta}^{2i}\mathrm{;}\text{\hspace{1em}}s=\{\begin{array}{cc}\frac{n}{2}-1& n\text{\hspace{0.17em}}\text{even}\\ \frac{n-1}{2}& n\text{\hspace{0.17em}}\text{odd}\end{array}$ (11)

${\left(sin{h}_{\alpha \mathrm{,}h}\left(x\right)\right)}^{\left(1\right)}\left(x\right)=\frac{\left({\alpha}^{2\delta}-{1}_{R}\right)}{2\delta {\alpha}^{\delta}}cos{h}_{\alpha \mathrm{,}h}\left(x\right)$ (12)

${\left(cos{h}_{\alpha \mathrm{,}h}\left(x\right)\right)}^{\left(1\right)}\left(x\right)=\frac{\left({\alpha}^{2\delta}-{1}_{R}\right)}{2\delta {\alpha}^{\delta}}sin{h}_{\alpha \mathrm{,}h}\left(x\right)$ (13)

Proof. One just uses the definition of the derivative. □

Remark 3.6. 1) If the ordering of R in Corollary 3.5 is the unity ordering, then $\delta ={1}_{R}$ and the formulas become much simpler.

2) Theorem 3.1 and Corollary 3.5 can be used to find k-th derivatives of all relations which are linear combinations or products of the set of k-th relations $\left\{{x}^{n}\mathrm{,}{\alpha}_{k}^{x}\mathrm{,}sin{h}_{\alpha \mathrm{,}k}\left(x\right)\mathrm{,}cos{h}_{\alpha \mathrm{,}k}\left(x\right)\right\}$ for a unit $\alpha \in R$ .

3) The derivative of a monomial function whose degree is divisible q is not zero in R.

The derivative is a linear transformation on $Re{l}_{st}\left(R\right)$ . So it can be applied on a relation $\rho $ more that once and still preserve the linearity property. The following result, which is a consequence of Theorem 3.1 and Corollary 3.5, gives formulas for computing k-th derivatives of certain relations $\rho $ , t times, which will be called $\left(t\mathrm{,}k\right)$ -th derivative of $\rho $ . If the array of $\rho $ has only one column, then the $\left(t\mathrm{,0}\right)$ -th derivative will be just called t-th derivative.

Corollary 3.7. Let $\alpha \in R$ be a unit, and let $\delta $ is the least length. Then for a nonnegative integer t:

${\left({x}^{n}\right)}^{\left(t\right)}={\displaystyle \underset{i=0}{\overset{s}{\sum}}}\left(\begin{array}{c}2\\ 2i+1\end{array}\right){\left({x}^{n\left(2i+1\right)}\right)}^{\left(t-1\right)}{\delta}^{2i}\mathrm{;}\text{\hspace{1em}}s=(\begin{array}{cc}\frac{n}{2}-1& n\text{\hspace{0.17em}}\text{even}\\ \frac{n-1}{2}& n\text{\hspace{0.17em}}\text{odd}\end{array}$ (14)

${\left({\alpha}^{x}\right)}_{k}^{\left(t\right)}={\left(\frac{{\alpha}^{2\delta}-{1}_{R}}{2\delta {\alpha}^{\delta}}\right)}^{t}{\alpha}^{x+kq}$ (15)

Proof. 1) Follows from (2) and Theorem 3.1.

2) Exercise. □

Over the real the derivative transformation is not necessarily periodic for exponential functions. Over prime fields the derivative transformation on an exponential relation is periodic forall of the bases.

Theorem 3.8. Let $R=GF\left(q\right)$ for a prime number q, and let $\alpha \in R$ be a unit which is not a square root of unity. If $\rho \left(x\right)={\alpha}^{x}$ , then

${\rho}_{h}^{\left(t\right)}\left(x\right)={\rho}_{h}\left(x\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}\text{some}\text{\hspace{0.17em}}\text{positive}\text{\hspace{0.17em}}\text{integer}\text{\hspace{0.17em}}t\mathrm{.}$

Proof. By the assumption ${\alpha}^{2}-1\ne 0\in R$ , so that $\frac{{\alpha}^{2}-1}{2\alpha}\in {R}^{\mathrm{*}}$ , which implies that ${\left(\frac{{\alpha}^{2}-1}{2\alpha}\right)}^{t}=1$ some positive integer t. □

The Exponential Values e

In real analysis the exponential relation $\mathrm{exp}\left(x\right)={e}^{x}$ is characterized by its derivative, in the sense that it is the only relation with derivative equals the relation itself. Given a finite ring with additive cyclically ordering, do we have an analog of the exponential relation with respect the derivative we have defined? The answer is not necessarily! But some rings have indeed got a pair of es. The result below gives a sufficient condition for that to happen.

Theorem 3.9. Let $R=GF\left(q\right)$ , where $q\ge 3$ is prime. If 2 is a quadratic residue in R, then the elements $e=1\pm \sqrt{2}$ has the property that ${\rho}_{k}^{\left(1\right)}\left(x\right)={\rho}_{k}\left(x\right)$ , where ${\rho}_{k}$ is the k-th relation of the relation $\rho \left(x\right)={e}^{x}$ .

Proof. Consider the relation $\rho \left(x\right)={e}^{x}$ , where e is in R. Suppose that $\rho \left(x\right)$ has the property that ${\rho}_{k}^{\left(1\right)}\left(x\right)={\rho}_{k}\left(x\right)$ for all k. Then one has that

${e}^{2}-2e-1=0\in R$ , which means $e=1\pm \sqrt{2}$ . □

5. Finding Directions

Throughout this section $R=GF\left(q\right)$ for an odd prime q, and the ordering of R is the unity ordering. Recall that for a relation $\rho \mathrm{:}R\to R$ , the set of directions of $\rho $ is denoted by $D\left(\rho \right)$ (see (1)). Let us denote the set of all $\left(i\mathrm{,}k\right)$ -th derivatives of $\rho $ by $D{r}_{k}^{\left(i\right)}\left(\rho \right)$ i.e.

$D{r}_{k}^{i}\left(\rho \right)=\left\{{\rho}_{k}^{\left(i\right)}\left(x\right)|x\in R\right\}$ (16)

From the definition of derivative we see that $D{r}_{k}^{\left(i\right)}\left(\rho \right)\subseteq D\left(\rho \right)$ for all $i\mathrm{,}k$ .

For a relation $\rho \mathrm{:}R\to R$ , the bound on the size of $D\left(\rho \right)$ has be well studied. But there are only few relations $\rho $ over R whereby the exact size of $D\left(\rho \right)$ is known. So far these are the known ones: Redei [1] shows that for linear functions $f$ , $\left|D\left(f\right)\right|=1$ , while Ball [8] establihed that functions of the form $f\left(x\right)=x\left(q+1\right)/2$ have $\left|D\left(f\right)\right|=\left(q+3\right)/2$ . We will try to add to this collection. We need the following lemma.

Lemma 4.1. Let $\alpha \in R$ be a unit of order $N\ge 3$ , and consider the relation $\rho \left(x\right)={\alpha}^{x}$ . Then for all $x\in R$ , ${\rho}_{k}^{\left(i\right)}\left(x\right)\ne 0\in R$ for all $i\mathrm{,}k$ .

Proof. For $x\in R$ such that $jN+1\le x\le \left(j+1\right)N-1$ , we have that ${\rho}_{k}^{\left(i\right)}\left(x\right)\ne 0$ for all $j\mathrm{,}k$ , by Corollary 2.6. One can easily verify that ${\rho}_{k}^{\left(i\right)}\left(jN\right)\ne 0$ , for all $i\mathrm{,}j\mathrm{,}k$ . □

Suppose that $\alpha \in R$ is a unit, and let $\rho \left(x\right)={\alpha}^{x}$ be a relation. Then by Theorem 3.9, applying the derivative transformation repeatedly gives back

$\rho \left(x\right)$ . We have two cases for $\beta =\frac{{\alpha}^{2}-1}{2\alpha}$ :

Case 1: If $\beta $ is in $\langle \alpha \rangle $ , then we get a permutation of $\langle \alpha \rangle $ whose order it the order of subgroup generated by $\beta $ .

Case 2: If $\beta $ is not in $\langle \alpha \rangle $ , then the collection $\left\{D{r}_{k}^{\left(i\right)}\left(\rho \right)\right\}$ partitions a bigger subgroup of ${R}^{\mathrm{*}}$ containing $\langle \alpha \rangle $ . If this happens, then we say that $\alpha $ partitions the subgroup.

We have the following result.

Lemma 4.2. Let $\alpha $ be a unit in R, and let $\rho \left(x\right)={\alpha}^{x}$ be a relation. Then the order of $D{r}_{k}^{\left(i\right)}\left(\rho \right)$ divides $q-1$ for all $i\mathrm{,}k$ . In particular, if $\alpha $ is a generator of ${R}^{\mathrm{*}}$ , then $\left|D{r}_{k}^{\left(i\right)}\left(\rho \right)\right|=q-1$ for all $i\mathrm{,}k$ .

Proof. We know that the set $D{r}_{k}^{\left(i\right)}\left(\rho \right)$ is a coset of $\langle \alpha \rangle $ in ${R}^{\mathrm{*}}$ for all $i\mathrm{,}k$ . Then the result follows, since all cosets of a subgroup have the same size. □

Now we have our main result of this section, which establishes a connection between $D\left(\rho \right)$ and $D{r}^{\left(i\right)}\left(\rho \right)$ for exponential relations $\rho \left(x\right)$ .

Theorem 4.3. Suppose that $\alpha $ is a unit in R of order $N3$ , consider the

relation $\rho \left(x\right)={\alpha}^{x}$ , and let s be the order of $\frac{{\alpha}^{2}-1}{2\alpha}$ .

1) If $\alpha $ partitions ${R}^{\mathrm{*}}$ , then for all k

$D\left(\rho \right)=D{r}_{k}^{\left(1\right)}\left(\rho \right)\bigsqcup D{r}_{h}^{\left(2\right)}\left(\rho \right)\bigsqcup \cdots \bigsqcup D{r}_{h}^{\left(s\right)}\bigsqcup \left\{0\right\}$ (17)

2) If $\alpha $ is a generator of ${R}^{\mathrm{*}}$ , then

$D\left(\rho \right)=D{r}_{k}^{\left(1\right)}\left(\rho \right)\bigsqcup \left\{0\right\}$ (18)

Proof. 1) Let $T=D{r}_{k}^{\left(1\right)}\left(\rho \right)\bigsqcup D{r}_{h}^{\left(2\right)}\left(\rho \right)\bigsqcup \cdots \bigsqcup D{r}_{h}^{\left(s\right)}$ . Then $\left|T\right|=q-1$ , since $\alpha $ partitions ${R}^{\mathrm{*}}$ . We also have that 0 is not in $D{r}_{k}^{\left(i\right)}\left(\rho \right)$ for all $i\mathrm{,}k$ , by Lemma 4.1. Since $D{r}_{k}^{\left(i\right)}\left(\rho \right)\subseteq D\left(\rho \right)$ and $\left|D\left(\rho \right)\right|\le q$ for all i, the result follows.

2) By Lemma 4.2 we have that $\left|D{r}_{k}^{\left(i\right)}\left(\rho \right)\right|=q-1$ and $\notin D{r}_{k}^{\left(i\right)}\left(\rho \right)$ by Lemma 4.1, for all $i\mathrm{,}k$ . Since $D{r}_{k}^{\left(i\right)}\left(\rho \right)\subset D\left(\rho \right)$ for all $i\mathrm{,}k$ , and $\left|D\left(\rho \right)\right|\le q$ , the result follows. □

6. Conclusion

The notion of derivatives over certain finite ring is developed and is used to find the number of directions of exponential relations in the sence of Redei [1] . The developed theory is limited to finite rings of the form ${\mathbb{Z}}_{n}$ for an odd integer n. It is an open problem to develop the notion of derivatives to fit other finite algebraic setting.

References

[1] Redei, L. (1973) Luchenhafte Polynome Uber Endkichen Korper. Birkhauser Verlag, Basel.

[2] Hasse, H. (1936) Theorie der Hoheren Differentiale in Einem Algebraischen Funk-tionenkorper mit Vollkommenen Konstantenkorper bei Beliebiger Charakteristik. Journal für die reine und angewandte Mathematik, 175, 50-54.

[3] Massey, J.L., von Seeman, N. and Schoeller, P. (1986) Hasse Derivatives and Repeated-Root Cyclic Codes. IEEE International Symposium on Information Theory, USA.

[4] Frisch, S. (1999) Polynomial Functions on Finite Commutative Rings. Lecture Notes in Pure and Appl. Mathematics, 205, 323-336.

[5] de Souza, M.M.C., de Oliveira, H.M., de Souza, R.M.C. and Vasconcelos, M.M. (2004) The Discrete Cosine Transform over Prime Finite Fields. LNCS, 3124, 37-59.
https://doi.org/10.1007/978-3-540-27824-5_65

[6] Blockhuis, A., Ball, S., Brouwer, A.E., Storme, L. and Szonyi, T. (1999) On the Number of Slopes of the Fraph of a Function Defined on a Finite Field. Journal of Combinatorial Theory, Series A, 86, 187-196.
https://doi.org/10.1006/jcta.1998.2915

[7] Ball, S. (2003) The Number of Directions Determined by a Function over Finite Field. Journal of Combinatorial Theory, Series A, 104, 341-435.
https://doi.org/10.1016/j.jcta.2003.09.006

[8] Ball, S. (2011) Lacunary Polynomials over Finite Fields. Unpublished.

[9] Ball, S. (2007) Functions over Finite Fields That Fetermine Few Directions. Electronic Notes in Discrete Mathematics, 29, 185-188.
https://doi.org/10.1016/j.endm.2007.07.032

[10] Garcia-Colin, N., Montejano, A., Montejano, L. and Oliveros, D. (2017) Transitive Oriented 3-Hypergraphs of Cyclic Orders.
https://arxiv.org/pdf/1210.6828.pdf

[11] Campello de Souza, R.M., de Oliveira, H.M., Kauffman, A.N. and Paschoal, A.J.A. (1998) Trigonometry in Finite Fields and a New Hartley Transform. ISIT, Cambridge. https://doi.org/10.1109/ISIT.1998.708898