Open Access Library Journal
Vol.04 No.12(2017), Article ID:81179,11 pages
10.4236/oalib.1104116
Derivatives over Certain Finite Rings
Soud K. Mohamed
Department of Mathematics, School of Mathematical Sciences, University of Dodoma, Dodoma, Tanzania
Copyright © 2017 by author and Open Access Library Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: November 3, 2017; Accepted: December 17, 2017; Published: December 20, 2017
ABSTRACT
We introduce a derivative of a relation over the ring of integers modulo an odd number which is based on the very fundamental concepts which helped in the evolution of derivative of a function over the real number field, namely slope. Then, for a prime field , we use the derivatives to construct an algorithm that find all the directions, in the sense of Redei [1] , of graphs of certain exponential relations over R.
Subject Areas:
Algebra, Combinatorial Mathematics
Keywords:
Relations, Derivatives, Directions
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 be a polynomial
over R. Then rth-Hasse derivative of is with for . It is well-known that over a finite field K all functions
are polynomial. In fact, if , then there are functions over K. In addition, there is a 1-1 correspondence between a function 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 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 on R in a variable x, which shall be usually denoted by . Then the image of 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 -array. In Section 2 we will look into exponential relations and their arrays over the ring 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 , where n is an odd integer. Given a relation , and a point , what should be the derivative of 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 ). 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 as well as across it. In Section 3 we show that the slope of the closest secant to a point along a column k is the best candidate for the derivative of at x, which shall be denoted by or simply , the k-th derivative of 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 be a finite field with q elements and let be a relation. Define the set of directions of (slopes of secants of the graph of ) by:
(1)
The problem of determining the bound on the size of 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 over R, the size s of the graph is the number of elements in the domain of . 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 directions. The algorithm is as follow: you start at the first point and then find directions, then move to the second point and compute directions, and so on. Since 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 over prime fields, the derivatives of is all one needs to find all the directions of the graph of .
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 will denote the group of units of R. Unless otherwise specified, by order of an element we mean the multiplicative order of a.
Throughout the paper, will denote the set all modulo integers , which is a class containg all integers b such that . The 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 which satisfies the following axioms:
1) Cyclicity: if is in C, then is in C.
2) Asymmetry: if is in C, then is not in C.
3) Transitivity: if and are in C, then is in C.
4) Totality or Completeness: if a, b and c are distinct, then either is in C or is in C.
If C satisfies the first three axioms, then it is called partial cyclic ordering on X, and consequently the pair 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 .
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 . We can use this correspondence to identify positions on X. Now, let X be a finite cyclically ordered set and let be at position i (using the above correspondence), where i is an integer. Then the element in the position will be called an immediate successor of x, and will be denoted by , while that in the position will be called immediate predecessor of x and will be denoted by .
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 , we have the orderings , , and , while for the multiplicative group we have orderings and . 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 with a binary operation. Then G has at least one cyclic ordering, namely the one determined by each generator of G. For , define the length from a to b, denoted by , to be , where is the inverse of a. For example, in the cyclically ordered set , we have that , while for the multiplicative group modulo 5 which is cyclically ordered, we have and .
Now, for our group G above, we have that every element has an immediate predecessor and successor. Then the length will be referred to as the least length of a, and will be denoted by . For example, for multiplicative cyclically ordered group , we have that for all . The following fact can be easily proved.
Fact 1.1. Let R be a ring with unity and isomorphic to the ring .
1) For any additive ordering on R the least length is constant for all .
2) There is an additive ordering on R such that .
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 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 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 are very fundamental, and they can easily be used to define other functions. Over finite ring, the mapping determined by , for a unit , 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 be a unit of order N. Then, the exponential relation is the relation . The image of is an -array with the a-th row, , where . The k-th column of , , where , will be called the k-th exponential relation of .
Example 1. We consider examples:
1) Let and consider the relation . Then the array of is
2) If and our relation is , then the array of is
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 is a relation on R, then the k-th relation of is .
Proof. We have that , since . □
Consider the relation , where has order N. Then 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 can easily be obtained.
Theorem 2.3. Let be a unit in R of order N, and let be a relation.
1) If a perfect square is not a factor of q and , then is an -array.
2) If for a prime p, where m is a positive integer, then there are columns in .
Proof. Suppose that is an -array, and let the a-th row be . Then is a coset of the subgroup of of order t. One can then observe that for both cases, and .
1) Now means that which is implies that . But since N does not divide q, it must divide t. Hence .
2) We have that , since H contains power of . Let K be a subgroup of of order . Since , then , and hence K is unique. From this we infer that if is such that , then . Now we have that for , so that . Hence and , which implies that . If , then , so that , a contradiction. □
The following corollary gives a sufficient condition for an exponential relation on R to be a function.
Corollary 2.4. Suppose that is unit of order N.
1) If a perfect square is not a factor of q and , then the relation is a function.
2) If for a prime p and has order for , then the relation is a function.
Proof. 1) For all and some positive integer t, we have that , since .
2) Follows from Theorem 2.3, since for . □
Let be a unit of order N, and consider the relation . Then is periodic of period N. More precisely, for a positive integer s each subset of the domain of , where , determines the same image . The subset is referred to as the j-th steps of . As expected, starting at a point in R, there are only a finite number of steps of before one gets back to the same point.
Proposition 2.5. Let be a unit of order N, and consider the relation . If , then has steps.
Proof. Let be the least positive integer with the property that the set taken has distinct elements. Observe that find number of steps of is the same as finding the cardinality of T. Also note that . If , then , a contradiction. □
Corollary 2.6. Let be a unit of order N, and consider the relation . Then the map is a permutation.
Proof. Only need to show that is 1-1. Suppose that for . Then which is equivalent to , a contradiction. □
We now define hyperbolic relations over R.
Definition 2.7. Let be a unit of order . Then
1) The k-th hyperbolic sine and cosine relations to the base over R, denoted by and are respectively
(2)
2) The hyperbolic since and cosine relations to the base , denoted by and are the relations with images the -arrays made by the columns and , respectively, where .
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 be a unit of order . Then for :
1) the identity holds,
2) and
Proof. Follows from the definition. □
4. Derivatives and Their Properties
Denote the set of relations from R to R whose image are -arrays by , and by the set of all functions from R to R.
Let q be the order of the ring R and let . For a positive integer k and a relation , define a map on the k-th relation of by
(3)
If the context is clear, then will be just denoted by .
If one looks closely at the this map one will notice that its value at a point is the slope of the closest secant to the point x along . It can be also interpreted as the average of the two closest slopes to x along . The result below show that the transformation has good properties too.
Theorem 3.1. Let and let . Then
1) the transformation is linear.
2) Product Rule:
(4)
(5)
3) Quotient rule: If for all , then
(6)
Proof. 1) Follows easily.
2) We use the elementary + tricks.
(7)
(8)
(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 with the associated additive cyclic ordering. Let . Then for each , so that is a unit in . So,
. For , we have that
.
2) Let has the unity ordering, and consider the relation given by . Then the image of is -array with columns and . One can verify that and for .
3) Consider the ring , and let . Then R is a ring modulo 35 whose unity . If one considers the given cyclic ordering on R, then for each , and which is a unit in R. Consider the relation on R. Then the image of is a -array, and we have that , and for .
The computation in Example 2.3 (1) and (2) would not be very clear as far as is concerned. But we used the following result.
Lemma 3.3. Suppose is a unit of order , and let be a relation on R. Then , for all integers . In particular, , and .
Proof. We have that . □
From the above theorem we see that the transformation looks indeed like a derivative on . 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 be a relation on R and let . If is defined, then it will be called the k-th derivative of the relation at x, and will be denoted by .
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 and let be the least length. If is a unit and n is a nonnegative integer greater than 1, then
(10)
(11)
(12)
(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 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 for a unit .
3) The derivative of a monomial function whose degree is divisible q is not zero in R.
The derivative is a linear transformation on . So it can be applied on a relation 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 , t times, which will be called -th derivative of . If the array of has only one column, then the -th derivative will be just called t-th derivative.
Corollary 3.7. Let be a unit, and let is the least length. Then for a nonnegative integer t:
(14)
(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 for a prime number q, and let be a unit which is not a square root of unity. If , then
Proof. By the assumption , so that , which implies that some positive integer t. □
The Exponential Values e
In real analysis the exponential relation 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 , where is prime. If 2 is a quadratic residue in R, then the elements has the property that , where is the k-th relation of the relation .
Proof. Consider the relation , where e is in R. Suppose that has the property that for all k. Then one has that
, which means . □
5. Finding Directions
Throughout this section for an odd prime q, and the ordering of R is the unity ordering. Recall that for a relation , the set of directions of is denoted by (see (1)). Let us denote the set of all -th derivatives of by i.e.
(16)
From the definition of derivative we see that for all .
For a relation , the bound on the size of has be well studied. But there are only few relations over R whereby the exact size of is known. So far these are the known ones: Redei [1] shows that for linear functions , , while Ball [8] establihed that functions of the form have . We will try to add to this collection. We need the following lemma.
Lemma 4.1. Let be a unit of order , and consider the relation . Then for all , for all .
Proof. For such that , we have that for all , by Corollary 2.6. One can easily verify that , for all . □
Suppose that is a unit, and let be a relation. Then by Theorem 3.9, applying the derivative transformation repeatedly gives back
. We have two cases for :
Case 1: If is in , then we get a permutation of whose order it the order of subgroup generated by .
Case 2: If is not in , then the collection partitions a bigger subgroup of containing . If this happens, then we say that partitions the subgroup.
We have the following result.
Lemma 4.2. Let be a unit in R, and let be a relation. Then the order of divides for all . In particular, if is a generator of , then for all .
Proof. We know that the set is a coset of in for all . 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 and for exponential relations .
Theorem 4.3. Suppose that is a unit in R of order , consider the
relation , and let s be the order of .
1) If partitions , then for all k
(17)
2) If is a generator of , then
(18)
Proof. 1) Let . Then , since partitions . We also have that 0 is not in for all , by Lemma 4.1. Since and for all i, the result follows.
2) By Lemma 4.2 we have that and by Lemma 4.1, for all . Since for all , and , 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 for an odd integer n. It is an open problem to develop the notion of derivatives to fit other finite algebraic setting.
Cite this paper
Mohamed, S.K. (2017) Derivatives over Certain Finite Rings. Open Access Library Journal, 4: e4116. https://doi.org/10.4236/oalib.1104116
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