Cyclic Generating Functions In Sequence Algebra

by

Huen Y.K.

CAHRC, P.O.Box 1003, Singapore 911101
http://web.singnet.com.sg/~huens/
email: huens@mbox3.singnet.com.sg

(A short communication - 1st released: 15/6/97.)


Abstract

By definition the linear natural number sequence Nat(z) starts from zero and ends at infinity with uniform unity intervals between successive integers. Other sequences derived from Nat(z) have larger intervals, some even have nonuniform intervals, but these are still holistic number sequences. By using the residue sets generated by modular arithmetic, it is possible to develop cyclic generating functions which generate repeated sequence patterns which are concatenated in closed rings. These residue maps can be visualised either algebraically or graphically. Most number sequences, whether 1-dimensional or multidimensional, are very visual and geometric which explain why sequence algebra is such a powerful tool in this domain. Visual explorations could uncover interesting geometrical properties before one attempts to develop proofs for them. The equation of divisibles was developed by this strategy which gave rise to sequence algebra.


1. Classification Of Holistic Number Sequences

Number sequences can be classified into two main groups according to whether these have linear or nonlinear intervals. For example, Nat(z) is linear whereas Mersennenumb(z) is nonlinear. Some sequences appear to have nonuniform intervals such as Comp(z) but on closer scrutiny it is made up of infinite number of sequences with uniform intervals and so are classified as linear. Less obvious is Prime(z) but it can be proved that the complement of periodic sequences are themselves periodic and so this is also a linear sequence. Fermatprime(z) and Mersenneprime(z) are definitely nonlinear [10 to 12].

Within each group, sequences can further be subdivided according to whether these are open or cyclic sequences. So far, only open sequences have been investigated since these comply with the definition in the original axiom of Nat(z) which specifies that a holistic number set starts from zero and ends at infinity. All number sequences, with the exception of ring sequences, obey this property. Cyclic sequences are those which form repeats of the same finite set, e.g. (1/z^o+1/z^1+z/z^2+1/z^3} repeated a million times. Only the integer set {0,1,2,3} appears in the repeats and so this cannot be called a holistic number set. In sequence algebra, continued expansions will only increase the numerator values without altering the finite integer set. As shown above, only the principal set needs to be represented. The numerator coefficients represent the number of copies or duplicity of the same integer. For example 10/z^7 means that there are ten copies of the integer 7. Similarly 1/z^infinity means that there is one integer with the value of infinity - in other words, there is no end to the particular number sequence [10].


2. Cyclic Generating Functions

Cyclic generating functions are formulated using the residue sets from modular arithmetics to determine the sequence of integers which will be generated in each repeated set. Since residue sets are cyclic, therefore the intervals in the sequence do not grow to infinity but repeat indefinitely following a set sequence pattern. Such intervals can be linear or nonlinear depending on the defined congruence relations. Do cyclic genrating functions break with the original axiom of Nat(z). The answer is that it does since the generating function of Nat(z) = z/(z-1) does not generate repeats. According to the well-ordered principle, each integer is unique and nonrepeating. But in cyclic sequences, the same integer can repeat ad infinitum. In this paper, we are only interested in integers in the principal interval, i.e., the first repeat.

Generating functions can be expressed in either open or closed form. For computational efficiency, we should use open forms since these avoid series expansions. But for dialectic analysis, the closed form is always used even though these formulations are computationally less efficient. Final value theorem must be applied to closed generating functions. This is because this theorem interpretes terms in an expanded series as individual closed forms so that final values will be returned as zeores which are correct but misleading [2,7]. In this paper linear cyclic generating functions are investigated followed by nonlinear cyclic generating functions.


3. Linear Cyclic Generating Functions

Linear cyclic generating functions can have three formulations ranging from the open form to the CGF form [3]. Intervals between integers are determined by the algebraic function f(i) which is equated to the congruence relation based on modular arithmetic. Equation (1) shows the open form or expanded form:

Cyclic(z):= 1/z^(i mod j) ...................................................................(1).

Test example 1:

Cyclic(z):=sum(sum(1/(z^(i mod j )),i=0..3),j=4..4);

...................................................................1......1
................................Cyclic(z) := 1 + 1/z + ---- + ----
......................................................................2.....3
...................................................................z......z

Cyclic(z):=sum(sum(1/(z^(i mod j )),i=0..7),j=4..4);
...................................................................2......2
................................Cyclic(z) := 2 + 2/z + ---- + ----
.....................................................................2......3
...................................................................z......z

Cyclic(z):=sum(sum(1/(z^(i mod j )),i=0..11),j=4..4);
.....................................................................3......3
..................................Cyclic(z) := 3 + 3/z + ---- + ----
.......................................................................2......3
.....................................................................z......z ................................(2)

The three program lines shown in equation group (2) have different ranges for the difference i but the same value for divisor j and yet the same output sequence is generated. This property has already been predicted in classical number theory and will not be elaborated here [1].
Equation (3) shows the closed form algebraic structure which is adopted by sequences with uniform intervals such as Nat(z), Odd(z) and Even(z). The reason for introducing a unity value in the exponent is to avoid divisions by zero which could occur if i mod j = 0. The sequence will be shifted by one unit interval to the right and this is compensated by introducing a z in the numerator to restore the whole sequence one interval to the left. Note that the number of terms generated is identical to the previous open form but the numerator coefficients are no more unity. To restore unity values, it will be necessary to apply Normc( ) to the output sequence as shown in equation (5).

Cyclic(z):= z/(z^(i mod j + 1) - 1) .......................................................(3).

Test example 2:

Cyclic(z):=series(sum(sum(z/(z^(i mod j+1 )-1),i=0..3),j=4..4),z=infinity,4);

...............................................................2.........3...........1
............................Cyclic(z) := 1 + 2/z + ---- + ---- + O(----) .........................(4).
.................................................................2.........3...........4
...............................................................z.........z...........z

After normalising, one gets equation (2) which is identical to the first line in equation group (2).

..........................................................................1.........1............1
..........................Normc(Cyclic(z)) := 1 + 1/z + ---- + ---- + O(----) ................(5).
............................................................................2.........3............4
..........................................................................z.........z............z

Equation (6) shows the cyclic generating function based on CGF(z) which is normally reserved for nonlinear number sequences such as Mersennenumb(z) and Fermatnumb(z) [3]. This form is computationally inefficient but it is necessary when intervals are nonlinear.

f(i) := i mod j

Cyclic(z):=1/(z^f(i)-1) - 1/(z^f(i)*(z^f(i)-1)) ........................................................(6).

Test example 3:

From equation (7), it can be seen that the output sequence is identical to the previous findings.

f(i) := i mod j;

Cyclic(z):=1/(z^f(i)-1) - 1/(z^f(i)*(z^f(i)-1));

............................................1.......................................1
...............Cyclic(z) := --------------- - --------------------------------
.....................................(i mod j).................(i mod j).....(i mod j)
...................................z.............-1............z...............(z..............-1)


Cyclic(z):=series(sum(sum(1/(z^(f(i)+1)-1) -1/(z^(f(i)+1)*(z^(f(i)+1)-1)),i=0..3),j=4..4),z=infinity,4);

............................................................1.........1...........1
..............................Cyclic(z) := 1/z + ---- + ---- + O(----)
..............................................................2.........3...........4
............................................................z.........z...........z ..................................................(7).


4. Nonlinear Cyclic Generating Functions

The f(i) functions in this type are nonlinear. One can either choose the open form or the CGF- form. Note that the principal values are confined to within the first 45 degree wedge in the matrix map.

d=i^2..............................................Residue sets
100.......... 0......... 0......... 1......... 0......... 0......... 4......... 2......... 4......... 1......... 0
81 ........... 0......... 1......... 0......... 1......... 1......... 3......... 4......... 1......... 0......... 1
64 ........... 0......... 0......... 1......... 0......... 4......... 4......... 1......... 0......... 1......... 4
49 ........... 0......... 1......... 1......... 1......... 4......... 1......... 0......... 1......... 4......... 9
36 ........... 0......... 0......... 0......... 0......... 1......... 0......... 1......... 4......... 0......... 6
25 ........... 0......... 1......... 1......... 1......... 0......... 1......... 4......... 1......... 7......... 5
16 ........... 0......... 0......... 1......... 0......... 1......... 4......... 2......... 0......... 7......... 6
9... .......... 0......... 1......... 0......... 1......... 4......... 3......... 2......... 1......... 0......... 9
4... .......... 0......... 0......... 1......... 0......... 4......... 4......... 4......... 4......... 4......... 4
1... .......... 0......... 1......... 1......... 1......... 1......... 1......... 1......... 1......... 1......... 1
0... .......... 0......... 0......... 0......... 0......... 0......... 0......... 0......... 0......... 0......... 0
--------------------------------------------------------------------------------------------------------------------------
... ........... 1......... 2......... 3......... 4......... 5......... 6......... 7......... 8......... 9......... 10 n = j
............Figure 1 - Residue map of nonlinear cyclic generating function f = i^2 mod j


Test example 4:

Modular function: f = i^2 mod j

General open form: Cyclic(z):=sort(sum(sum(1/z^f,i=0..n),j=n+1..n+1));

The computed results in equation (9) and (10) are as predicted in figure 1 above. Note that it is not immediately apparent that the output sequences are in palindromic repeats. Traditionally there are product palindromes and summation palindromes but this is the first report of residue palindromes from modular arithmetic. No further exploration of residue maps for higher powers than 2 are investigated. This will be left to readers to explore.

f:=i^2 mod j;

....................................................2
...........................................f := (i...mod..j) ............................................(8).

Cyclic(z):=sort(sum(sum(1/z^f,i=0..10),j=11..11));

.......................................................2.......2......2.......2
.......................Cyclic(z) := 2/z + ---- + ---- + ---- + ---- + 1 ........................(9).
.........................................................3.......4......5.......9
.......................................................z.......z......z.......z

Cyclic(z):=sort(sum(sum(1/z^f,i=0..5),j=6..6));

.................................................................1.......2
.................................Cyclic(z) := 2/z + ---- + ---- + 1 .................................(10).
..................................................................3.......4
.................................................................z.......z

5. Product of Ring Sequences

The product of two identical ring sequences with n elements each will remain a ring sequence after multiplications but the number of elements will increase to 2n-1. With multiple squaring, eventually the number of elements in a ring will approach infinity but it still remains as a ring. Although a ring sequence is distinct from a linear sequence, it is not immediately obvious whether a finite sequence is a ring or an ordinary linear sequence. However, one must remember that ring sequences are truly finite whereas finite linear sequences are just portions of holistic sequences which can only be shown correctly by their closed forms. Therefore, unless closed form generating functions are available, it is not possible to determine whether a finite sequence is a ring or linear sequence. By ring theory, all sequences are rings, but the use of this term here only refers to those generated by modular arithmetics. If ring is not an appropriate term, then it is suggested that we should us the term loop sequence. All ring sequences show symmetries in the the symmetry diagrams shown below but this property is not unique just to ring sequences. The acid test therefore should be based on scrutinising closed form generating functions. If this is not feasible, then authors should specify in context whether the finite sequence is a linear or a ring sequence.

Test Example 5:

Starting with the first ring sequence given by Cyclic(z), this is successively squared resulting in almost doubling the number of terms after each opertion. A symmetry diagram is attached to each output sequence showing symmetries each ring as shown in equation group (11).


.................................................................1.......1
............................Cyclic(z) := 1 + 1/z + ---- + ----
...................................................................2......3
.................................................................z......z

Symmetry diagram of numerator coefficients:

..............................{1 ------>1-,
..............................{1<-------1-'


...........................................................3.......4.......3........2........1
.......................Cyclic(z)^2 := 2/z + ---- + ---- + ---- + ---- + ---- + 1
.............................................................2.......3.......4........5........6
...........................................................z.......z.......z........z........z

Symmetry diagram of numerator coefficients:

..............................{1------>2------->3------->4
..............................{1<------2<-------3<--------'


.......................................10.....20.....31......40......44......40......31......20......10.......4......1
......Cyclic(z)^4:=4/z + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + --- + --- + --- + 1
..........................................2.......3.......4........5.........6........7.........8........9.......10.....11....12
........................................z.......z.......z........z.........z.........z.........z........z.........z........z.......z

Symmetry diagram of numerator coefficients:

..............................{1----->4------->10-------> 20-------> 31--------> 40--------> 44
..............................{1<-----4<-------10<--------20<--------31<---------40------------'
....................................................................................................................(11).


6. Conclusions
This paper shows that it is possible to develop ring or loop sequences where intervals are controlled by the residue sets generated by congruence relations based on modular arithmetic. Many phenomena in the real world are based on closed loops rather than infinite strings. For example, some DNA sequences exist in closed loops. In string theory, there are closed strings and open strings. Time itself may be cyclic rather than 1-dimensional. The Big-Bang theory does suggest cyclical dynamics of the universe. The development of the theory of ring or loop sequences is just at its infancy. Number theorists need not bother about real world applications but the development of its theory should help applied scientists to find use for them.

Unexplored at this moment are the following problems. This does not imply that these are not solveable.

(1) How to predict whether the residue set will display normal repeats or palindromic repeats.

(2) Are repeat sequences always determined by the finite sequences located within the first 45 degree wedge in the residue map?


7. References

1. Burton M. Burton: Elementary Number Theory, Third Edition, WCB publishers, 1994, 17 to 48 to 50.

2. Huen Y.K.: A Simple Introduction To Sequence Algebra, URL site: http://web.singnet.com.sg/~huens/

3. Huen Y.K.: The Canonical Generating Function or CGF(z) - a Swiss-knife function. URL site: http://web.singnet.com.sg/~huens/ .

4. Huen Y.K.:Information Contents Of Number Theoretic Functions. URL site: http://web.singnet.com.sg/~huens/ .

5. Huen Y.K.: In Search Of Exotic Arithmetic Operators, URL site: http://web.singnet.com.sg /~huens/ .

6. Huen Y.K.: Visual Solutions Of Number Theoretic Functions in Multidimensional Sequence Space, URL site: http://web.singnet.com.sg /~huens/ .

7. Huen Y.K.: Final Value Theorems Applied To Number Sequences -- its strengths and weaknesses, URL site: http://web.singnet.com.sg /~huens/ .

8. Huen Y.K.: Unsolved Problems In Sequence Algebra, URL site: http://web.singnet.com.sg /~huens/ .

9. Huen Y.K.: Explicit Formulation For Modular Arithmetic In Sequence Algebra, URL site: http://web.singnet.com.sg /~huens/ .

10. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci. Technol., 1994, VOL. 25, NO.6, pp 913-920.

11. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ. Sci. Technol., 1996, VOL.27, NO. 5, 685-691.

12. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,1996, VOL.??, NO.?, ???-??? (In the press as proof paper mes 100421).


=====================END OF PAPER ======================