Information Contents Of Number Theoretic Functions

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 release: 29/5/97. Update: 29/5,30/5)

Abstract

Measurements are important activities in sciences and commerce and these can only be performed accurately with reference to high precision standards. Therefore when the information content of an algebraic equation or its program is to be measured, one needs a reference standard. In this paper, the global natural number sequence Nat(z) is defined as the information reference standard by which other number theoretic functions are measured. Since most number theoretic sequences have sequence algebraic formulations but this cannot be said of conventional number theoretic formulations, measurements will be done in the sequence algebraic domain. Conversions from the algebraic to the sequence algebraic domain is possible by mapping using the canonical generating function called CGF(z) [6] although this is only used for class 3 sequences. The unit of information content is defined in "godch" where one godch equals 7 ascii characters. Measurements of most well known number theoretic sequences fall within expectations but real insights are obtained from the few exceptions which defy intuitive predictions.

1. Introduction

The work in this paper is not connected with information theory as practised by crypto-analysts [1] or random theorem proofing as described by Chaitin [3]. It is more closely connected with the practice of measurements. Every proven number theoretic function carry a finite amount of information. With the discovery of sequence algebra since 1994 [7], sequence formulations for predicting all primitive number sequences and most derived secondary sequences have been developed [5 to 9]. The aims of of this paper are twofold, viz., to determine implementation procedure for setting up information content calibration and to seek explanations to some unusual results obtained from the calibrations.

a) Implementations

(i) To define Nat(z) = z/(z-1) as the reference standard for information contents of number theoretic functions.

(ii) To calibrate the information contents of well known number theoretic sequences and to interprete the results obtained.

b) Enquiries

(i) To discover whether the null sequence Zero(z) and the random sequence Random(z) have any information content and whether these are measurable.

(ii) To find explanations on why Odd(z) has lower information content than Even(z).

(iii) to find explanations on why Prime(z) has higher information content than Comp(z).

(iv) Is there a plausible relation between equation lengths and information contents of number theoretic functions?

(v) To discover the principle governing the increase of information contents of number theoretic sequences based on results reported in table 1.

2. Classificattions of Sequence Algebraic Expressions

Much real progress has been made in number theory since 1637 but there were also glaring lack of progress in some quarters. The proof of Fermat's Last Theorem by Wiles comes from a discipline outside conventional number theory. Goldbach's conjecture still remains unsolved. Most number theoretic predictions are not written as explicit formulations. For example there are many primality tests but there is no explicit formula for the prime sequence. Neither is there one for the composite sequence. The nearest one could host a number theoretic formula maybe as an iterative algorithm but strictly this is not an explicit formula. Examples of some iterative sequences written in Maple V R 3 syntax are shown below. There is no way these sequences could be translated into closed explicit forms.

Natural numbers: from i = -1 to 10 do n = i + 1; od
...............................................Result:{0,1,2,3,4,5,6,7,8,9,10,11}
Even numbers: from i = 0 to 10 by 2 do n = 2*i; od
...............................................Result:{0,2,4,6,8,10,12,14,16,18,20}
Odd numbers: from i = 0 to 10 by 2 do n = 2*i + 1; od
...............................................Result:{1,3,5,7,9,11,13,15,17,19,21}

In sequence algebra, number sequences are written down holistically and are always explicit. There are three classes of sequence algebraic formulations given in order of complexity as shown below. Sequences which do not have sequence algebraic formulations are temporarily relegated to class 4. The method of counting ascii characters are demonstrated in table 1.

Class 1: Primitive number sequences

In this class, the power index is a fixed value and only arithmetic operators are used.

Nat(z) = z / ( z - 1 )
.............1 2 3 4 5 6 7 = 7 ascii characters.

Even(z) = z ^ 2 / ( z ^ 2 - 1 )
................1 2 3 4 5 6 7 8 9 10 11 = 11 ascii characters.

Odd(z) = z * Even(z) = z / ( z ^ 2 - 1 )
................1 2 (11) 1 2 3 4 5 6 7 8 9 = 9 ascii characters.

There are two formulations for Odd(z) but the second one is shorter and is adopted. Note that by convention we do not include Even( z) as an intrinsic arithmetic function which would have reduced the counts for Even(z) to 6 as shown below:

0 * Even ( z )
1 2 3 4 5 6 = 6 ascii characters

Class 2: Composite number sequences (not to be confused with Comp(z)).

In this class, the Normc ( ) operator has to be introduced which reduces numerator coefficients to unities. This is necessary because sequence products causes the numerator coefficients to increase above unities which will hamper further sequence manipulations.[8,9]

Comp(z) = 1 / ( z ^ i * ( z ^ i - 1 ) )
................1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 = 15 ascii characters.

Prime(z) = Nat ( z ) - Normc ( Comp ( z ) ) - 1 - 1 / z
....................(7) 1 2 (15) 3 4 5 6 7 8 9 = 31 ascii characters.

Oddcomp(z) = Normc ( Comp(z) ) - Even(z)
...........................1 2 (15) 3 4 (11) = 30 ascii characters.

Class 3: Canonical Generating Functions or CGF(z)

This class covers nonlinear sequence algebraic formulations. Both Normc( ) and logical operators are needed in the formulations. A separate paper on CFG(z) [6] can be found in the author's URL site: http://web.singnet.com.sg/~huens/ .

f(i)s are algebraic expressions which will be separately counted.

CGF(z) = 1 / ( z ^ f(i) - 1 ) - 1 / ( z ^ f(i) * ( z ^ f(i) - 1 ) )
................1 2 3 4 5 (k) 6 7 8 9 10 11 12 13 14 (k) 15 16 17 18 (k) 19 20 21 22
.........................................................................................................................= 22+3*k

This is the generalised sequence formulation which is required where intervals in CGF(z) become nonuniform due to the nonlinear f(i) expression. Examples are found in Mersenne and Fermat number sequences. In this class, mixed mode arithmetics is required. Although there is no proof, no formulations using purely arithmetic operations have been found. It is most probably impossible to write down explicit formulations using arithmetic operators alone.

Mersenne Numbers And Mersenne Primes:
f(i) := ( 2 ^ i - 1 )
..........1 2 3 4 5 6 7

Mersennenumb(z):= 1 / ( z ^ f(i) - 1) - 1 / ( z ^ f(i) * ( z ^ f(i) - 1 ) ) ; = 23 +3*7 = 44 ascii characters.

Mersenneprime:=
(AND Normc ( Mersennenumb(z) ) Prime(z) )
1 2 3 4 (44) 5 (31) 6 = 6 + 44 + 31 = 81 ascii characters.

Fermat Numbers And Fermat Primes:
f(i) := ( 2 ^ ( 2 ^ i ) - 1 )
..........1 2 3 4 5 6 7 8 9 10 11 = 11 ascii characters.

Fermatnumb(z):= 1 /(z^f(i) - 1) - 1/(z^f(i)*(z^f(i)-1)); = 23 + 3*11 = 56 ascii characters.

Fermatprime(z):= (AND Normc(Fermatnumb(z)) Prime(z)) = 6 + 56 + 31 = 93 ascii characters.

Perfect Number

f(i)= i / ( z ^ i * ( z ^ i - 1 ) - i / z ^ i
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 == 23 + 3*20 = 83 ascii characters.

Twin Primes

(OR (AND Prime(z)[ z ^ 2 * Prime(z) ] ) ( AND Prime(z) [ z ^ ( - 2 ) * Prime(z) ] )
1 2 3 4 (31) 5 6 7 8 9 (31) 10 11 12 13 (31) 14 15 16 17 18 19 20 21 (31) 32 33 34
..............................................................................= 23 + 4* 31 = 147 ascii characters.

3. Table Of Ascii Counts

Using the method of counting ascii characters, we summarise the length counts in both ascii units and Godch units. Since Nat(z) has 7 ascii characters, it is defined to have a unit of one Godch, i.e. one Godch equals 7 ascii characters. Godch is the acronym derived from Godel and Chaitin.[2,4]

Table 1 - Calibrations Of Information Contents Of Well Known Number Sequences

...sequences........................ascii units...................godch units
Class 1:

Nat(z) as the standard..........7 ascii characters...........1

Odd(z)..........z/(z^2-1)........9...................................1.285714286

Even(z).........z^2/(z^2-1)....11..................................1.571428571

Zero(z) ........0*Nat(z).........9...................................1.285714286

Classs 2:

Comp(z) 1/(z^i*(z^i-1)).................15.........................2.142857143

Prime(z)=Nat(z)-Comp(z)-1-1/z....36.........................5.142857143

Oddcomp(z)=Even(z)-Comp(z).....31.........................4.428571429

Class 3:

Mersennenumber(z).....................44 .........................6.285714286

1/(z^(2^i-1)-1)-1/(z^(2^i)*(z^(2^i-1)-1));

Fermatnumber(z)..........................56...........................8.
1/(z^(2^(2^i))-1)-1/(z^(2^(2^i))*(z^(2^(2^i))-1));

Perfectnumber(z)..........................83..........................11.85714286
f(i)= i/(z^i*(z^i-1)-i/z^i

Mersenneprime(z)........................81..........................11.57142857

Fermatprime(z).............................93..........................13.28571429

Twinprime(z)

(OR (AND Prime(z) [z^2*Prime(z)]) (AND Prime(z) [z^(-2)*Prime(z)])
.....................................................147........................21.

Class 4 (unclassified)

Random(z) no formulation..............?................................?

4. Interpretations Of Results

Class 1:

Why should Even(z) have more information content than Odd(z)?

Explanations: These are not proofs, only conjectures. The world is unsymmetrical. It reaches the present state via symmetry breaking. We have left and right handedness. The two lobes of our brain are different. In the natural number system, there is no symmetry between Even(z) and Odd(z) since the former has a zero but the latter has not. This affects the sequence properties profoundly. Just see what happens when both Even(z) and Odd(z) are squared as shown in equations (2) and (3):

...................................................1.......1......1.........1
...........................Even(z) := 1 + ---- + ---- + ---- + O(----)
......................................................2.....4.......6.........8
...................................................z......z.......z.........z
...................................................1.......1......1.........1
........................... Odd(z) :=1/z+ ---- + ---- + ---- + O(----)
......................................................3.....5.......7.........9
...................................................z......z.......z.........z
expand(Even(z)^2);

.........1...........1...........1............1..........1.........1...........1
1 +2 ---- +3 ---- +4 ---- +3 ---- +2 ---- + ---- + O(----).......(2).
............2.........4..........6.............8...........10...........12
..........z.........z...........z.............z............z............z
expand(Odd(z)^2);

..........1............1............1..........1..........1.........1..........1
..... 1---- +2 ---- +3 ---- +4 ---- +3 ---- +2 ---- +----- O(----)........(3).
.............2.........4..........6...........8..........10..........12.........14
...........z.........z..........z...........z...........z...........z............z
. There is no algebraic proof on why Odd(z) should have less information content than Even(z) but the following observations are relevant. Comparing equation (2) with equation (3), one notes that Even(z)^2 retains the first 1/z^o term whereas in Odd(z)^2 this term is suppressed and the sequence is shifted by one unit interval to the right. As the squaring continues to infinity, the order of Even(z)^n will remain the same but the order of Odd(z)^n approaches asymptotically to Zero(z). Even(z) is said to be an order invariant sequence but Odd(z) is not. Both Even(z) and Odd(z) have more information content than Nat(z). Even Zero(z) has more information than Nat(z). It appears that as the number of finite terms decreases, the information content increases. Why should Zero(z) have any information? In sequence algebra 0 is complement to 1 and it is not nothingness. The absence of integers in a number sequence is itself an information just like 1 and 0 in binary strings contribute to information.

Class 2:

It is probably reasonable to expect that Prime(z) and Oddcomp(z) to have more information than Comp(z). There are much fewer primes than composites. From previous observations in class 1, as the number of terms decreases, the information content increases. The difference between Prime(z) and Oddcomp(z) is probably insignificant. Most probably the number of primes is about the same as the number of Oddcomp(z).

Class 3:

Information contents of class 3 sequences increase rapidly as these are usually mixed mode expressions involving functions of more than one primitive sequences. The sequence with the most information in the list is Twinprime(z). The number of terms in these sequences are even fewer than those found in class 2. This again supports the observations that the fewer the number of terms, the more the information contents. Note that this relation is nonlinear. Otherwise one would expect Zero(z) to have infinite information content but it does not. Using Nat(z) and Zero(z) as a guide, the number sequence with the greatest information content must lie somewhere between the two extremes. Right now we do not know what it is but it is most probably Random(z) which is unclassifiable since there is no sequence formulation for it.

Class 4 (unclassified)

At this moment there is only one sequence in this category and that is Random(z). In information theory, random(z) is considered to have maximum entropy[1]. If randome(z) has n bits, then the formula description of it cannot be less than n-bits [2,3]. We do not have a formulation for Random(z). This must be a nonrepeating sequence and all random terms must have equal probability. Therefore you cannot derive it from Prime(z) or Comp(z) even though past workers assumed these to be random. Since these two sequences can be predicted deterministically and globally, these cannot be random. Another way of describing a Random(z) is to used a CGF with f(i) = Random generator. At least this method allows a way of measuring the information content of this sequence but there are many variations of pseudo-random generators which will affect the ascii counts. The measurements become very subjective. Right now, we assume that Random(z) to have the highest information content but we do not know its exact value. To evaluate Random(z) via CGF(z) we need an explicit expression for a random number generator. This is not available.

So far the results obtained seem to fall within expectations with few surprises. If an explicit compact sequence formulation can be found for Random(z), it would imply that the information content of this sequence is not infinite. Measurements must be done with explicit formulations. The method based on Nat(z) as a standard seems to give reasonable predictions.

Information contents do increase with decreasing number of finite terms appearing in the sequence. Information contents increase rapidly with nonlinear intervals contributed by f(i). If this is not the case then we would expect Nat(z) to have the greatest amount of information but it has the lowest information content. Prime(z) to have more information than Comp(z) seems reasonable since it is quite easy to derive the Comp(z) formula but not the Prime(z) formula.

5. Conclusions

The adoption of Nat(z) as a reference standard gives the opportunities to calibrate the information contents of some well known number theoretic sequences. No rigorous proof are found to prove why information contents are ordered in the way shown in table 1 but it seems that this is directly linked to the decreasing number of terms in the sequences. In other words, the principle that information contents increase with decreasing number of finite terms in the sequence is probably true although this is nonlinear. This information might be contradictory to what is known in information theory but here we are talking about holistic number sequences. In information transmission one never uses a message with infinite length as a reference standard but in holistic number theory we do. Until an explicit formulation is found for a random number generator, the information content of a random sequence cannot be computed. This finding is not reported in past literatures.

4. References

1. Schneier Bruce: Applied Cryptography, Protocols, Algorithms, and Source Code in C, chapter 11, pp 233 to 239, Wiley (2nd ed.), 1996

2. Chaitin G.J.: Godel's Theorem and Information, Interantional Journal of Theoretical Physics 22 (1982), pp 941-954.

3. Chaitin G.J. : How to Run Algorithmic Information theory on a Computer, Complexity 2:1 (1996), pp.?-?.

4. Silver L.C. : From Symbolic Logic ... To Mathematical Logic, WCB Publishers, 1994, Chapter 11 Godel's Theorems, pp321 to 360.

5. Huen Y.K.: A Simple Introduction To Sequence Algebra, a free downloadable paper available from the author's URL site: http://web.singnet.com.sg/~huens/,

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

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

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

9. 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=====================