Visualizing the Hindu divisibility test

Prologue
This article continues on the themes covered by the last two (here and here) relating to factorization and the primitive root modulo of a prime number. Early in ones education one learns the divisibility tests for the first few primes: 2, 3, and 5. Of these divisibility by 2 and 5 is trivial. Divisibility by 3 is also easily achieved: e.g. Is 771 divisible by 3? 7+7+1=15; \; 1+5=6. We see that the successive addition of digits reduces the original number to 6 which is divisible by 3; hence, the original number is divisible by 3. Of course, division by 3 is not a big deal; yet, for big numbers this is an easy method for mentally determining divisibility.

Beyond these three simple cases, in our school days we determined the divisibility by other primes using brute force — by dividing the test number by the given prime. When we reached college, a gentleman of great mathematical ability asked us if we could think of a generalization of the divisibility test for 3 for other primes. Seeing that we were unable to do so, he proceeded to tell us of such a method. He then mentioned that he had learned this via Suryanarayana of Vishakhapatnam who possessed enormous mathematical knowledge and capacity. Suryanarayana had further informed him that it was a folk Hindu method that was known in South India. Shortly thereafter, we saw the same method with some tricks for quick implementation in the pre-computer age described by the late Śaṃkarācarya Bhāratī Kṛṣṇa Tīrtha-jī (hereinafter SBKT) of the Govardhana pīṭha in his curious mathematical work with 16 foundational sūtra-s. He called the method veṣṭana, which he rendered in English as osculation, and presented it as an example of his sūtra: “ekādhikeṇa pūrveṇa |

The Hindu divisibility test
The procedure goes thus:
1) Let p be a prime other than 2, 3, 5 for which divisibility is already accounted for. Let the test number be n_0 which is written as n_0=10a_0+b_0.
2) Find the first number (10c-1) \mod p =0, i.e. the first multiple of p which is of the form 10c-1. Thus, this number will necessarily be of the form 10d+9, where c=d+1. That is how it relates to SBKT’s “ekādhikeṇa pūrveṇa |
3) This c is termed the veṣṭaka or ‘osculator’ for the procedure. We then compute n_1=a_0+b_0c.
4) We again write n_1=10a_1+b_1 and repeat this procedure: n_2= a_1+b_1c.
5) If p divides n_0 then this procedure terminates in a small and easily recognized multiple of p. Any further application of the above procedure on that number yields the same number.

Let us illustrate it with an example: Is n_0=3249 divisible by p=19?
For p=19, 2 \times 10 -1=19\; \therefore c=2. Now we use the osculator c=2 for applying the above procedure.
We get 324+9 \times 2=342; \; 34+2\times 2= 38; \; 3+8\times 2=19
We reach 19 indicating that 3249 is divisible by 19. Applying the above procedure to 19 yields 19 again. Indicating that it is a terminal number of the process. In a practical application from the pre-computer age we don’t have to go all the way: we could stop for e.g. at 38, which we recognize as a multiple of 19. Further, for bigger numbers SBKT gives certain tricks which would be useful in such pre-computer applications.

What if a number is not divisible by p? As an example consider the case: Is n_0=178 divisible by 19? Of course, in this case the answer is quite obvious; nevertheless, it allows us to illustrate what happens if we apply the above procedure on it. We get the following sequence of n_j, j=0, 1, 2 ...:
178\rightarrow 33 \rightarrow (9 \rightarrow 18 \rightarrow 17 \rightarrow 15 \rightarrow 11\rightarrow 3 \rightarrow 6 \rightarrow 12 \rightarrow 5 \rightarrow 10 \rightarrow 1\rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 16 \rightarrow 13 \rightarrow 7 \rightarrow14 ) \rightarrow9
We observe that, unlike the divisible n_0 which converges to a single number, the non-divisible n_0 after the first 2 terms enters a repeating cycle of 18 terms. Again, for practical purposes if one just wanted to test divisibility one obtains the answer much earlier.

The basic divisibility graphs
We can do this divisibility procedure for several successive n_0, say for all n_0=1..200 and p=19, and the illustrate the conglomerate results as an ordered graph (Figure 1). The graph’s nodes are the numbers n_j obtained while applying the above divisibility procedure until we hit a cycle or converge. The edges indicate which number leads to which, with the relative thickness indicating the frequency with which they occur for this range of n_0 (scaled by hyperbolic arcsine).

Tirtha_div_Fig1Figure 1

One also notices that all n_0 in this range, which are divisible by 19, directly converge to it. The remaining numbers converge directly or indirectly by different paths to a central directed ring R_1 with components r_1, r_2, r_3.... These are the same as the terms of the cycle obtained in the above example. One also notices that in this example the ring size S(R_1)=18, i.e. number of terms in the ring, corresponds to cycle length of the decimal expansion of \tfrac{1}{19} or j=18 when 10^j \mod 19=1 for the first time. This j, in this case 18, is known as the multiplicative order of 10 (\mod p), which was shown by Carl Gauss to correspond to the cycle of the decimal expansion of \tfrac{1}{p} . The terms of this ring R_1 includes all the number from 1..18. Thus, it is also obvious that the sum of the terms of in ring R_1 is divisible by p:

\displaystyle \left(\sum_{j=1}^{S(R_1)} r_j \right) \mod p =0

To further explore these patterns, we next consider the case of p=13 and plot the same for graph for n_0=1..200 in Figure 2.

Tirtha_div_Fig2Figure 2

We observe that all n_0 divisible by 13 in this range converge to 3 terminal nodes: 13, 26 and 39. The remaining n_0 converge directly or indirectly to one of 6 rings with 6 terms each. i.e. S(R_{1..6})=6. Here again we notice that the size of these rings is the same as the multiplicative order of 10\mod 13 ($j=6$ when 10^j \mod 13=1 for the first time), which is cycle length of the decimal expansion of of \tfrac{1}{13}. Further, together the 6 rings include all numbers from 1..38 barring 13 and 26 which are divisible by 13. It is easy to see that \sum_{j=1}^{38} j-13-26 is divisible by 13. However, we also notice that the sum of the terms of each of the six rings is also divisible by 13:

\displaystyle \left(\sum_{j=1}^{S(R_k)} r_{kj} \right) \mod p =0; \; k=1..6

We next consider the case of p=7 and n_0=1..200 (Figure 3).

Tirtha_div_Fig3Figure 3

In this graph the numbers divisible by 7 converge to 2 endpoints either 7 itself or 49 (when they are multiples of 49). All the remaining numbers directly or indirectly converge to a large ring with 42 terms, which includes all numbers from 1..48 except for 7, 14, 21, 28, 35, 42. Thus, it is easy to see that the sum of the terms of this ring will be divisible by 7. Further, the multiplicative order of 10 \mod 7 is 6. Thus, the number of terms in the ring is multiple of that 42=6 \times 7.

To sum up, we may note the following features of these divisibility graphs:
1) The residue system of p=19 for base 10 (till 10^j \mod p for j=1,2,3... produces 1 as the residue for the first time, i.e. till j is equal to the multiplicative order) is: 10, 5, 12, 6, 3, 11, 15, 17, 18, 9, 14, 7, 13, 16, 8, 4, 2, 1. The base 10 residue system for p=13 is: 10, 9, 12, 3, 4, 1. The base 10 residue system of p=7 is: 3, 2, 6, 4, 5, 1. We observe that the penultimate residue in each case is what SBKT calls the “osculator” c used in the divisibility test.

2) Looking the graphs, it becomes clear that the non-divisible n_0 converge to one or more directed rings, the sizes of which are either the multiplicative order m for base 10 or a multiple of m. A number n is a primitive root of p if the residue system of n^j, j=1,2,3...p-1 contains all numbers from 1..p-1. If 10 is not a primitive root of the p , the divisibility by which we are testing, then we will necessarily have multiple rings. If 10 is a primitive root of p we can in some cases get a single ring with its terms being all numbers from 1..p-1 (e.g. 19). Alternatively, we can get a large single ring whose size can be some multiple of the multiplicative order (e.g. p=7) or multiple rings whose sizes are different multiples of the multiplicative order (e.g. p=17).

Tirtha_div_Fig4Figure 4. Divisibility graph for p=17

3) The terms included in all the rings of convergence taken together for a given p range from 1..10c-2, where c is the penultimate residue of the system and the osculator. Of course, all numbers divisible by p in this range are excluded from the rings as they are nodes of separate components of the graph that converge to single root, an integer divisible by p. Thus, for p=13, the osculator is c=4. So, the integers covered in the rings would be from 1 to 38, with 13 and 26 not being in the rings. For p=7, the osculator c=5; hence, the ring would cover the integers from 1 to 48, with 7, 14, 21, 28, 35, 42 being excluded. When p=17, the osculator is c=12. Thus, the rings will extend from 1 to 118, with 17, 34, 51, 68, 85, 102 being excluded.

4) From the above it is obvious that the sum of the numbers in all the rings taken together would be divisible by p. The less obvious feature is that the sum of the numbers in each individual ring of the convergence graph is also divisible by p. Thus, the numbers are placed in each ring in such a way that two constraints are simultaneously met, namely: 1)that of divisibility of the sum of the numbers in each ring by p and 2) that of each ring size being a multiple of the base 10 multiplicative order modulo the given p. In the case of p=13 placing the numbers in 6 separate rings can satisfy the above constraints for each ring. In the case of p=17 placing them in 3 separate rings can satisfy them, while in the case of p=7 they need to be in a single large ring to meet the constraints.

5) An obvious but structurally distinctive feature of the divisibility graph is that 1 can never be reached directly from any n_0 unless it is a member of the ring to which 1 belongs. From the procedure it is clear that it can be reached only from 10. 10 is the first number in the base 10 residue system for any p>7 and will necessarily be part of the ring. Further, in whichever ring 1 occurs, by the nature of the procedure, it would always lead next to the osculator c as the next node in the ring. c always comes just before it in the residue system for base 10 (e.g. for 13: 10, 9, 12, 3, 4, 1): thus 10\rightarrow 1 \rightarrow c is fixed a motif in the divisibility ring reverse order of their occurrence in the residue system. The longest path of the divisibility graph ending in a ring always passes through this c (However, there could be graphs with multiple equally long paths passing through other ring nodes in certain cases like p=17).

One wonders is an encryption system along the lines of the Diffie-Hellman-Merkle mechanism can be made using these divisibility graphs.

The reduced divisibility graphs
The above-described graphs were based on the simple divisibility method found in folk Hindu mathematics and SBKT’s mathematical exposition. However, for practical purposes SBKT gives an additional step, which he terms the “casting out of the primes”. This goes thus: We again write the test number as n_0=10a_0+b_0. We then obtain n_1= a_0+(b_0c \mod p), where c is the osculator as above. Thus, we first reduce b_0c to its residue modulo the p, the divisibility by which we are testing, before adding it to a_0 to arrive at n_1.

As a numerical example let us consider testing the divisibility of 99 by 7. The osculator for 7 is c=5. Thus 9 \times 5=45. We now take 45 \mod 7= 3 and use it in place of 45. Thus, we get n_1=12 which allows us to decide on the matter of divisibility right away. However, we could continue the procedure to convergence, as we did above, in order to compute the convergence graphs for different p. In this case we observe the following:
1) If 10 is a primitive root of p then we get a bipartite graph: One component derived from all the non-divisible n_0 has a central ring, which has as its terms all numbers from 1..p-1. The other component is a tree graph converging to p which includes all the n_0 divisible by p. Examples of this are the graphs for p=7 or p=17

Tirtha_div_Fig5Figure 5. The convergence graph for p=7

Tirtha_div_Fig6Figure 6. The convergence graph for p=17

2) If 10 is not a primitive root of p then we get a multipartite graph. One component, as above, is a tree graph converging on p and includes all the n_0 divisible by p. The remaining components have central rings whose size is the multiplicative order m of 10 \mod p. The number of these ring components is \tfrac{p-1}{m}. Here again, the sum of the numbers in each ring is divisible by p. Together they include all integers from 1..p-1. Examples of this are the graphs for p=13 and p=41.

Tirtha_div_Fig7Figure 7. The convergence graph for p=13. Here m=6 for base 10; thus we get \tfrac{13-1}{6}=2 components with central rings.

Tirtha_div_Fig8Figure 8. The convergence graph for p=41. Here m=5 for base 10; thus we get \tfrac{41-1}{5}=8 components with central rings.

In these graphs too the longest path terminating in a ring passes through the osculator c, which is reached from 1 on the ring. Here again, 1 is reached from 10, the first residue of the residue system for base 10 \mod p for all primes p>7. However, given that 10 \mod 7 =3, for p=7, 1 is reached from 3 in the ring. In conclusion, this version of the divisibility graph makes apparent the close relationship it has to the period of the decimal form of the fraction \tfrac{1}{p}, which we considered in the previous article.

Posted in Scientific ramblings | Tagged , , , , , ,

Fermat’s little theorem and the periods of the reciprocals of primes

From the genetic code to the proof of Fermat’s little theorem
Nucleic acids encode the 20 amino acids found in the sequence of a protein using just 4 bases: A, G, T, C in DNA. Thus, the 4-symbol nucleic acid alphabet encodes a 20-symbol protein alphabet. This is achieved by having 3 letters in the nucleic acid language (a codon) code for one letter in the protein language or for the stop sign to terminate the protein sequence. This is the famed genetic code. When we first learned of it at age 10, we became fascinated with the process of encoding and while playing around with codons, we learned not just the foundations of biology but also some of the basics of combinatorics. That was perhaps the reason why some years later in college we were quite agile with elementary combinatorics despite not having any special mathematical spark.

The first and the most obvious thing we observed was that the total number of codons in the genetic code was the total number permutations with replacements that could achieved in 3-letter words using a 4-symbol alphabet: 4\times 4\times 4 = 64. A closer look then revealed that these 3-letter words, i.e. codons, could be classified into groups by arranging them as ring graphs (Figure 1). Since nucleic acids have a polarity imparted by the (deoxy) ribose ring of the sugar, i.e. 5'\rightarrow 3', each of these ring graphs are directed: they take the form of an uroboros. Thus, we get into 24 distinct groups

Figure 1

Of these, 4 rings are homopolymeric, i.e. AAA, GGG, TTT and CCC. Any circular permutation of them will yield the same codon again. Each of the remaining 20 rings is heteropolymeric. Hence, when circularly permuted, each will always yield 3 different codons. For example, the first ring in the second row (Figure 1) will yield AGA, GAA and AAG. Thus, we get the total number of permutations possible in the 3-letter words with a 4-symbol alphabet as: 20 \times 3 +4 =64. This reveals a more important truth of combinatorics: If you have any word of prime number length then by definition, other than for homotypic words (equivalent to a homopolymeric codon), it will always have same prime number of circular permutations when the letters are arranged on a directed ring graph as in Figure 1. 3 is the prime number in the case of the genetic code; hence; the circular permutations of the heteropolymeric rings yield 3 codons each. We can express this as a generalization thus: Let a be the number of symbols in the alphabet. Let p be a prime which is the length of the word in that alphabet. We also insist that a is not divisible by p. Then the total number of p-letter words will be n=a^p. Of these the homotypic words will amount to a. Thus, the remainder will be a^p-a words. Now, these remaining words, by the above principle of arranging on directed ring graphs, can be grouped into k sets each of p words. Thus, a^p-a= kp; therefore it will be divisible by p. Alternatively,

(a^p-a) \mod p =0; \; \therefore (a^{p-1}-1) \mod p=0; \; \therefore a^{p-1} \mod p =1

This is the famous Fermat’s little theorem of arithmetic. Fermat had proposed it without a proof but it was subsequently proven by Liebniz. Euler published a proof more than 50 years later, apparently unaware of Liebniz’s manuscript which is believed to have not been formally published. He then provided its general form, the theorem of Euler regarding the totient function \varphi(n), which we had encountered in the previous note. The above proof which we presented is the proof by combinatorics. It was apparently first published by the mathematician Golomb and is a variant of Euler’s original proof.

The periods of the reciprocals of prime numbers
Early tetrapods showed a wide range of finger-counts in their limbs: Acanthostega had an 8-fingered limb; Ichthyostega showed a 7-fingered hind-limb; Tulerpeton had 6 fingers. Some time thereafter, perhaps in a form like Crassigyrinus, the number 5 got fixed. While there are frequent deviations from this in particular lineages, like amphibians losing a finger in the forelimb, the 5-fingered state continued to be the common baseline in most surviving tetrapod clades. Thus, we got our 5-fingered hands. This combined with our bilateral symmetry gave us a number system based on the product of 2 primes: 10=2 \times 5; i.e., the decimal system. While some islanders of Papua have apparently opted for the smaller senary system based on 6=2\times3, the former system came to be the dominant usage of the world.

The peculiarities of the decimal system caught our fancy when our father began teaching us decimal fractions as a kid. We were fascinated by the observation that some decimal fractions terminated: \tfrac{1}{8}=0.125, whereas others just fell into a cycle: \tfrac{1}{11}=0.090909.... We asked our father why this was so? He told us to focus on: 1) reciprocals, i.e. fractions of the type \tfrac{1}{a} because all other fractions are integer multiples of such and 2) to look out for primes. Then thinking it would be good for us to get some practice with division, he let us keep to dividing 1 by various numbers.

If one were to do this arithmetic operation, sooner or later, one realizes the following:
1) Only fractions of the form \tfrac{1}{2^m 5^n} or their multiple terminate. The number of decimal places after which they terminate is \max(m,n). This is easily understood. One needs to divide as many units as the maximum number of times 2 or 5 appear in the denominator; hence, the decimal fraction terminates after that many digits after the point.

2) If the fraction is of the form \tfrac{1}{2^m 5^n p_1^a p_2^b...}, where p_1, p_2... are the primes other than 2 and 5 then it always cycles after an initial run of numbers whose length again depends of the 2^m 5^n part of the denominator as in the first case.

3) To better understand the cycles let us restrict ourselves to the basic situation where the fraction is of the form \tfrac{1}{p}, where p is any prime other than 2 or 5. Such fractions are always pure cycles in the decimal form. We define cycle-length l as the length of the repeating pattern of digits. Since, \tfrac{1}{2} and \tfrac{1}{5} terminate we can take their l=0. For other primes we see l take various values as below:

\dfrac{1}{3}=0.\overline{3}; l=1

\dfrac{1}{7}= 0.\overline{142857}; l=6

\dfrac{1}{11}=0.\overline{09}; l=2

\dfrac{1}{13}=0.\overline{076923}; l=6

\dfrac{1}{17}=0.\overline{ 0588235294117647}; l=16

\dfrac{1}{19}=0.\overline{ 052631578947368421}; l=18

What determines the length of the cycle for a given prime? We observe that the cycle is determined by when a multiple of the denominator p becomes 1 less than a power of 10 for the first time. Thus we have: 3\times 3= 9. Hence, the cycle for \tfrac{1}{3}=0.\overline{3}. Similarly, 7\times 142857= 999999. Hence, the cycle for \tfrac{1}{7}=0.\overline{142857}. Another example: 11\times 09= 99. Hence, the cycle for \tfrac{1}{11}=0.\overline{09}. This can be formally expressed thus: When 10^n \mod p = 1 then the length of the decimal cycle of \tfrac{1}{p} is l=n. The pattern of repetition is then given by \tfrac{10^n-1}{p} with the appropriate padding 0s.

With this in place, one can now show that for a given prime p, the maximum length of a cycle can be p-1. By Fermat’s little theorem (see above), 10^{p-1} \mod p =1. Thus, we will reach a number 1 less than a power of 10, which is also divisible by p, latest by 10^{p-1}-1; therefore, in these cases l=p-1. In the above examples we see this for 7, 17 and 19. An examination of the distribution of the digits from 0..9 for fractions with long cycles shows that they are all present in equal frequency.

This now leads us to an interesting sequence f such that f[n] is defined as the length of the decimal cycle of the reciprocal of the n^{th} prime, i.e. l(\tfrac{1}{p_n}). The Englishman W. Shanks was the first to compute this sequence in the pre-computer era for every p<20000, i.e., the first 2262 primes and triumphantly presented his results before the Royal Society of England. Unlike Shanks, in our first attempt at this in our childhood we quickly ran out of steam but we had at least obtained some basic picture of the “lay of the land” of the sequence f. Hence, we wondered how Shanks reached his goal: was it by brute force or by some trick which the late Śaṃkarācarya of the Govardhana-maṭha used. In any case, as time passed my father had grown richer and procured a computer for me. As a result, I revisited this problem and could now reach where old Shanks had gone. f runs thus:
0, 1, 0, 6, 2, 6, 16, 18, 22, 28, 15, 3, 5, 21, 46, 13, 58, 60, 33, 35…
One notices that sometimes f[n] is even and other times odd. If it is even the corresponding \tfrac{1}{p_n} has a curious property, which we illustrate with few examples:

f[4]=6 \equiv \dfrac{1}{7} \equiv 0.142 | 857

f[7]=16 \equiv \dfrac{1}{17} \equiv 0.05882352 | 94117647

Thus, we see that for fractions with an even cycle the sum of each of the digits in the first \tfrac{l}{2} digits with the corresponding digit in the final \tfrac{l}{2} digits is 9; e.g. in the case of p_n=7: 1+8=4+5=2+7=9. Likewise, for p_n=17: 0+9=5+4=8+1=8+1=2+7=3+6=5+5=2+7=9. This knowledge halves the calculation as long as you know you have reached the midpoint of the cycle. But this leads to the question: what is the distribution of cycle lengths? A good way to approach this question is by plotting f[n] against the corresponding p_n. This is shown in Figure 2.

Figure 2. f[n] are plotted as both points and heights against p_n for the first 1229 primes. Every 5 successive f[n] are plotted as heights of a different color.

We observe that in this plot the terms of f[n] fall on lines of the form y=\tfrac{x-1}{k}, where k=1, 2, 3, 4.... Those where the cycle length is of the form l=p_n-1 will fall on y=x-1. Those for which l=\tfrac{p_n-1}{2}, e.g. p_n=13, will fall on y=\tfrac{x-1}{2} and so on. Since all primes other than 2 are odd, p_n-1 will be even. Thus, \tfrac{p_n-1}{2} might be even or odd. Further, \tfrac{p_n-1}{3} will be even. Thus, given that only when k is even we can get odd-length cycles, the number of primes with odd-length cycles will be less than the number of primes with even-length cycles. The ratio of the number of odd-length cycles to even-length cycles for the first 2262 primes it is 0.487. While it close to \tfrac{1}{2}, it is not clear if it converges to a particular value.

Figure 3. Primes with even-length cycles are colored blue and those with odd-length cycles are colored red. The first 2262 primes are arranged from left to right 58 per row in 39 rows.

In Figure 3 we depict the first 2262 primes colored according to whether they have an even- or odd-length cycle. There is no obviously discernible pattern. Yet, there could be a subtle one which we are unable to describe: whether such a pattern exists remains an open question to us.

The f[n] and the corresponding p_n can be classified into different families depending on which line of the form y=\tfrac{x-1}{k} they fall on (Figure 2). Thus, for k=1, we have the cycle 1 family; for k=2 we have the cycle 2 family and so on. The frequency of the cycle$k$ families for k=1..50 in the first 2262 primes is shown in figure 4.

Figure 4.

We observe that the cycle 1 primes are the most common: 7, 17, 19, 23, 29, 47, 59, 61, 97, 109…
Then cycle 2 primes: 3, 13, 31, 43, 67, 71, 83, 89, 107, 151…
Thereafter the cycles become rarer rapidly. Cycle 3: 103, 127, 139, 331, 349, 421, 457, 463, 607, 661…
cycle 4: 53, 173, 277, 317, 397, 769, 773, 797, 809, 853…
cycle 5 is anomalously rarer than the flanking even k cycles: 11, 251, 1061, 1451, 1901, 1931, 2381, 3181, 3491, 3851…
This anomalous rarity continues for at least few subsequent odd k=7, 9, 11, 13, 15... relative to the flanking even k. The frequencies of the primes belonging to each cycle appear to converge to particular values. Whether there is some systematic way for accounting for this distribution remains an open question to us.

We can also look at the first prime in each cycle: The first prime to show cycle 1 is 7; the first to show cycle 2 is 3; then we get a dramatic jump with the first to show cycle 3 being 103 and so on. Thus we can define a sequence which is the first prime in each cycle: 7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641. Figure 5 shows a plot of this sequence.

Figure 5. The first prime in each cycle is plotted as both a height and a point. The cycles which were not attained in the first 2262 primes are shown as red empty circles.

This plot leave us with many unanswered questions: 1) Is there someway to decide a priori what will be the first prime to have a certain k cycle? 2) Is there some pattern to the plot in Figure 5? 3) We observed that from k=29 onward there are several k for which the cycle is not initiated within the range of the first 2262 primes we used in this plot. Are there are any k for which a cycle is never initiated?

Finally, we could ask the question: what is the count of the primes of cycle k \le n, i.e., the counting function for cycle k primes. This is shown for cycle 1 primes in Figure 6.

Figure 6. The heights in blue are the number of cycle 1 primes \le n. The curves in red are \textrm{Li}(x) and 0.3824\textrm{Li}(x) respectively.

We observe that this count can be described by a fraction of the prime counting function or its asymptotic equivalent. In the above case, we use the logarithmic integral \textrm{Li}(x). The fraction is the convergent frequency of the cycle k, which in the case of cycle 1 can be computed to be approximately 0.3824 using the first 2262 primes. This again brings us to the issue of whether one can obtain a closed form description for these frequencies.

Posted in Life, Scientific ramblings | Tagged , , , , , , ,

A layman’s overview of the arithmetic of encryption

Life as an encryption-decryption cycle
Encryption is a concept as old as life itself. The sequence of proteins, the primary purveyors of function in life as we know it, is encrypted within nucleic acids. It is decrypted by this remarkable machine known as the ribosome along with tRNAs, whose origin lie close to the origin of life itself. The encryption itself is relatively simple with a 4 symbol nucleic acid alphabet encoding a (usually) 20 symbol protein alphabet. This is done by having three letter words in the nucleic acid alphabet specify 1 letter in the protein alphabet. Thus, with a four letter alphabet one has 4 \times 4 \times 4 =64 words with 3 letters in the nucleic acid alphabet to specific just 20 letters in the protein alphabet. Thus, this encoding system necessarily has degeneracy, meaning multiple 3-letter words in the nucleic acid alphabet encode the same letter in the protein alphabet, e.g. (TTT, TTC) \rightarrow F; (CGT, CGC, CGA, CGG, AGA, AGG) \rightarrow R. In addition, some of these 3-letter nucleic acid words encode a stop of the protein-word, i.e. the end of the protein sequence: usually (UAA, UAG, UGA) \rightarrow STOP.

Encryption by humans
In terms of human language, encrypting messages is probably as old as human language itself. The rest of this note is about how one of the most important modern forms of human encryption and decryption is carried out. What we are going to talk about in here is nothing original or new. One can find accounts of it in books dealing with higher arithmetic (like I first did) or on the internet. However, when we first learned of it in our youth, at least in our circles, it was not very well-known. We were so charmed by it then that we eagerly demonstrated it to a friend and acquaintances who suffered the outpourings of our meditations. About 28 years since that time, a gentleman asked me why prime numbers had any value at all and I explained this encryption mechanism to him. Hence, I thought I would record it, as I often record private teaching devices I might have used. Again, I must reiterate, this is not an area of my expertise. I am simply recording the beautiful mathematical device it uses in simplified form and in lay language without much of the jargon specific to this subject.

Encryption, however complex, has depended on using some form of key. This key was quite literally like the “Rosetta Stone”, which had allowed the decoding of the old Egyptian writing. With complex encodings, if the key is lost then decoding of the encrypted message can be difficult. The Harappan script is one such example, which has no such Rosetta Stone, and it is likely that the language which it encoded is largely lost; hence, we cannot make sense of what is encoded in its strings of symbols. In any case, the idea of the key can be simply illustrated. Say we take the key to be k=13, the language to be English, the script to be standard Roman and the basic numerical encoding to be of the form a \equiv 1; b \equiv 2; c \equiv 3 ... z\equiv 26. Let us say we want to use our key to encode the message “kill tonight”. Then we first write the numerical equivalent of “kill tonight” without space between the words: 11 9 12 12 20 15 14 9 7 8 20. Then we multiply each letter by the key k=13 to get: 143 117 156 156 260 195 182 117 91 104 260. This is our encrypted message. Anyone with the key can decode this message by reversing the procedure i.e. by division. The general version of technique gūḍha-yojya in Hindu cryptographic tradition. Of course this is a simple encryption. In addition to anyone who gets the key by some means, it might also be broken quite easily by an amateur code-breaker.

One can also imagine a slightly more complex encryption such as this:

1) The message to be encrypted is the same: “kill tonight” written without spaces as “killtonight”.

2) We choose a keyword, let us say “mrtyu” and repeat it as many times as to cover the message to encode:

killtonight
mrtyumrtyum

This latter word is the transformer.

3) We then convert “killtonight” to its direct numeric equivalent as described in the earlier example: 11 9 12 12 20 15 14 9 7 8 20. Likewise, we convert the transformer into its numeric equivalent: 13 18 20 25 21 13 18 20 25 21 13.

4) We then add the each number of the message to be encoded to the corresponding number in the transformer to get the coding: 24 27 32 37 41 28 32 29 32 29 33.

5) We then subtract 26 from all those numbers in this coding that are greater than 26. Thus we get: 24 1 6 11 15 2 6 3 6 3 7.

6) We then convert it back to letters to get our encrypted message: “xafkobfcfcg”.

This is a more serious encoding and would need more effort to break unless one gets hold of the keyword by some means. Then one can use the keyword to reverse the procedure and get the original message.

Diffie, Hellman and Merkle
While the above two examples differ considerably in their complexity and difficulty in terms of being broken by a code-breaker, they still share a common feature, namely symmetry: both the sender of the encrypted message and its intended receiver need to have same key and keyword. That they have to somehow share this secret is the primary problem of this form of encryption. If the key is intercepted while being shared then the interceptor can read all the messages between the sender and the intended receiver. This would mean that the key should be changed from time to time but multiple changes only mean multiple key transfers which could result in further susceptibility to interception. Further, if there are multiple people in the network of encrypted information sharing it might increase the vulnerability of the key to being intercepted or it would impose the problem of managing the sharing of a large number of distinct keys. This remained the situation from the beginning of human encryption until the mid-1970s when Diffie, Hellman and Merkle showed that in principle it was possible to use a mathematical trick for two or more communicating parties to arrive at a common encryption key without having to share it. Thus, the sender and the receiver need not transmit a shared secret key. All they have to do is to share a public key, which by itself does not reveal to the interceptor the secret key they use to encrypt or decrypt message. The secret key used for encryption is not transmitted but is independently derived on either side from the information shared by the interlocutors and an asymmetric private key that is never shared with anyone.

The basic idea of Diffie, Hellman and Merkle depends on an arithmetic concept known as the primitive root modulo of a prime number p: for an integer g<p if one obtains every integer from n=1, 2,3 ... p-1 when one takes the modulo to p of all g^m, where m=0,1,2...p-1, then g is the primitive root modulo p. As an example consider p=11 and g=2, then we have:
2^0 \mod 11 = 2^{10} \mod 11=1; 2^1 \mod 11=2; 2^2 \mod 11= 4; 2^3 \mod 11=8; 2^4 \mod 11= 5; 2^5 \mod 11= 10; 2^6 \mod 11= 9; 2^7 \mod 11= 7; 2^8 \mod 11= 3; 2^9 \mod 11= 6.
Thus, we get all the numbers n=1, 2, 3...10 for the operation 2^m \mod 11 for m=0, 1, 2...10. Hence, 2 is a primitive root modulo 11.

To use this to derive an encryption key, without directly transmitting it, the following operation is performed. Let us call the two men who wish to exchange encrypted messages as K and C.

1) First K and C share a public key in the form of prime number say p=37 and one of its primitive roots g=5.

2) Then K selects a secret integer say a=7 and transmits A=g^a \mod p, i.e. A=5^7 \mod 37 = 18 to C.

3) Likewise C selects a secret integer say b=3 and transmits B=g^b \mod p, i.e. B=5^3 \mod 37=14 to K .

4) Thus, one notices that K and C have not exchanged the same information beyond the public key. However they can use the numbers they have exchanged for the following computation on either side: K computes k=B^a \mod p, i.e. k=14^7 \mod 37=105413504 \mod 37 =23. Similarly, C computes k=A^b \mod p, i.e. k=18^3 \mod 37 = 5832 \mod 37 = 23. Thus, now both K and C are in possession of a common key k=23, which they can use for encryption by some means without ever having shared it directly. The logic behind this is simple: The computation they perform on their respective sides results in k=g^{ab} \mod p = g^{ba} \mod p.

Now, a snoop (let us call him R) will be in possession of the public key p and g used by K and C. R will also be able to intercept the numbers A and B that K and C exchanged just as any worthy snoop would do. With these numbers would R be able to determine a or b, which is what he would need to get hold of the encryption key? Given the prime p, g^x \mod p can assume a value 1..p-1, one of which will A or B. In our example with p=37 it can assume a value 1..36. R will have to find out plugging in which x in the operation g^x \mod p would yield A. That x will be a, which was secretly used by K. Likewise for b. This problem is known as the discrete logarithm problem. In our example, since there are only 36 values to check, R could simply figure out a or b through brute force and nearly instantaneously on a modern computer. However, note the following: The sequence of 5^{0..36} \mod 37 is plotted in the first panel of Figure 1. In the second panel we plot 5^{0..107} \mod 107 where p=107 is a safe prime. Similarly, we also plot the sequences of one of their respective primitive roots g raised to all n=0..p-1 modulo p=113 a Sophie Germain prime and modulo p=127 a Mersenne prime.

RSA_Fig1_primroot_pow_modpFigure 1.

We observe that the sequences of g^n \mod p for each of the primes has a great deal of irregularity and appears to be mostly random. Thus, there is no pattern to where the A derived from a given a might be found be found. This illustrates nature of the discrete logarithm problem: there is currently no effective method to solve it and it is not even known if any effective method can be devised in principle. As such, one essentially needs to search much of the space of g^n \mod p for a prime p to find a solution. Thus, rather than p=37 if one were to use an enormous prime then there is no effective method to solve the problem of finding a, given A, g, p in sufficient time. For example, 512 bit. i.e. 154..155 digit decimal base primes were widely used. However, it was recently shown that by precomputing and storing all g^n \mod p for some widely reused primes (an expensive and time-consuming operation) encryption based on them might be compromised. It is also believed that given the resources of the 5-eyes mleccha-s together with the prathamonmatta-s, their praṇidhi-s have similarly broken through the even stronger commonly used 1024 bit i.e. 308..309 digit primes through expensive pre-computation.

Just for the feel of it here is a 155 digit number that is probably a prime just to give you a sense of how many values one would need to search to break encryption based on such a p:
10000000000000000369475456880582265409809179829842688451922778552150543659
347219597216513109705408327446511753687232667314337003349573404171046192448274699

Rivest, Shamir and Adleman
In the year following Diffie and Hellman’s publication, Rivest, Shamir and Adleman published their asymmetric public private key system, which again uses a clever mathematical device. We outline below with a mock example the idea behind what is now famous as the RSA system:

1) As usual consider the two interlocutors K and C. One of them, say K, selects two primes p_1 and p_2. In our mock example we shall take p_1=37 and p_2=47. K multiplies the two to get p_k=p_1p_2=1739.

2) K then calculates p_l=(p_1-1)(p_2-1)=1656. He then chooses a number which is mutually prime with 1656, let us say q=5. He then shares p_k, q as the public key with C.

3) C can now use this information to encrypt a number k (for example a key to be shared for future communication) and send it to K. For our example we will take k=24. What C does is to compute a= k^q \mod p_k= 24^5 \mod 1739=1482 and send a to K. a=1482 is the encrypted information sent by C to K

4) To decrypt a, K has to do the following computation. He has to first find a number d such that qd \mod p_l= 1. This means we have to find some integer n such that we get an integer solution d=\tfrac{np_l+1}{q}. In our case K has to solve 5l \mod 1656 =1. Since 1656 ends in 6 if he multiplies it by 4 and adds 1 to the result he will get a number divisible by q=5. Thus he gets d=1325.

5) Next K has to compute a^d \mod p_k to decode the encrypted number C has sent him. In our example that will be 1482^{1325} \mod 1739. This looks like a daunting thing to do but it can be broken by the following trick. First one writes d=1325 in terms of powers of 2:

1325=1024 + 256 + 32 + 8 + 4 + 1\\[10pt]  \therefore 1482^{1325} =1482^{1024 + 256 + 32 + 8 + 4 + 1} = 1482^{1024} \times 1482^{256}\times 1482^{32} \times 1482^{8} \times 1482^{4} \times 1482^{1}

Since modulo is multiplicative we then take modulo by parts:

1482 \mod 1739 =1482\\  1482^4 \mod 1739 =1089\\  1482^8=1482^4 \times 1482^4 \mod 1739 =(1089 \times 1089) \mod 1739 = 1662\\  1482^{32}= (1482^8)^4 \mod 1739 = 1662^4 \mod 1739 = 895\\  1482^{256}=(1482^{32})^8 \mod 1739 = (895^4 \times 895^4 ) \mod 1739 =(1661 \times 1661) \mod 1739=867\\  1482^{1024} \mod 1739 = 867^4 \mod 1739= 1452\\  \therefore 1482^{1325} \mod 1739 = (1482 \times 1089 \times 1662) \mod 1739 \times (895 \times 867 \times 1452) \mod 1739 = (533 \times 1341) \mod 1739 =24

Thus, at the end of this calculation, which can be easily achieved with a computer, K decodes the number C sent him without ever having exchanged a symmetric secret key. The reason this trick works is because of an arithmetic function discovered by Leonhard Euler known as Euler’s totient function \varphi(n) and a theorem proved by him in that regard. Apparently, Rivest, the discoverer of the RSA method got the clue for this method of encryption while reading about modular arithmetic in a book. We will not attempt to go into the higher arithmetic concerning the proof of Euler regarding \varphi(n) but merely demonstrate how it applies to the RSA encryption.

Euler’s \varphi(n) is defined as the number of integers 1 \le m \le n, which are relatively prime (coprime) with n i.e. GCD(n,m)=1. Thus, \varphi(8)= \#(1,3,5,7)=4. For a prime p it is easy to see that the value of \varphi(p)=p-1 for every other number below it will be relatively prime to it by definition. Thus, \varphi(p_k)=\varphi(p_1\cdot p_2)=(p_1-1)(p_2-1). This is the number p_l used in calculating the second number q of the public key. Thus, from the above account one can see that the decoding calculation is essentially: k^{dq} \mod p_k. From step 4 of above we have dq=np_l+1=n\varphi(p_1p_2)+1 =n\varphi(p_k)+1. Therefore, the decoding operation is (k^{n\varphi(p_k)+1}) \mod p_k=(k\cdot k^{n\varphi(p_k)}) \mod p_k= k (\cdot k^{n\varphi(p_k)} \mod p_k). By Euler’s theorem k^{\varphi(p_k)} \mod p_k=1. Thus, our expression evaluates to k.

Now, the snooper R would have in his possession the public key p_k, q and would obtain a by intercepting the exchange between C and K. Hence, to decode a he would need to have p_l=(p_1-1)(p_2-1). The only way he can get that is by factorizing p_k to obtain p_1 and p_2. In our example p_k=1739 can be factorized by a modern computer in a jiffy. However, in practice p_1 and p_2 are chosen to be giant numbers like 155 digits each. For example here are two probable prime numbers of 155 digits each:

p_1= 10000000000000000369475456880582265409809179829842688451922778552150543659
347219597216513109705408327446511753687232667314337003349573404171046192448274699

p_2= 10000000000000000369475456880582265409809179829842688451922778552150543659
347219597216513109705408327446511753687232667314337003349573404171046192448275667

I can multiply them on any ordinary laptop nearly instantaneously to get a 309 digit behemoth:

p_k= 10000000000000000738950913761164544470829683371185866006812890654888707392
10920108053653415662434024612881790955097216386704787165762913381353272856133610
92747866891044947194561369772249369066504008239030777919045965752486653372812632
286420484529615670829121768709047243844587015197251118254241456911693449233

However, if we were to give a behemoth number of that magnitude for factorization, without telling you how we generated it, then it would not be possible with the realm of our current computation to factorize it. When we last checked the biggest product of two primes which was factorized was a 232 digit number and it was no quick or easy task. Nobody in the public domain knows to date knows if there is any efficient algorithm to factorize big numbers or whether it is even possible to device one. It is on this premise the RSA encryption hangs. Finally, it should be noted that both DHM and RSA are not really efficient methods for direct encryption of a large amount of information. Instead they are used to encrypt a key which can then be used to encrypt the actual message.

Posted in Scientific ramblings | Tagged , , , , , , ,

Division-multiplication parabolas, triplications, and quadratic residues

Introduction

Many strands of our investigations on conic-generating integer sequences, word fractals and cellular automaton models for pattern formation came together in an unexpected manner while investigating a simple integer sequence. While some of these connections have have been known before, others are to our knowledge unreported. We present our investigations in this regard below.

The division-multiplication parabola sequence and other associated sequences

Consider the following sequence f:

f[1]=1; thereafter if,

n < f[n-1], f[n]=\left\lfloor\dfrac{f[n-1]}{n}\right\rfloor;

else, n > f[n-1] and f[n]= n\cdot f[n-1]

Following our initial investigation, a search of OEIS revealed that this sequence was reported therein by Amarnath Murthy (A076039). The first few terms of f are: 1, 2, 6, 1, 5, 30, 4, 32, 3, 30, 2, 24, 1, 14… A more detailed view of f for increasing values of maximum n is shown in Figure 1.

Div_mult_parabola_Fig1Figure 1

An examination of the sequence and its plot in Figure 1 reveals the following features:

1) The action of division and multiplication by n takes place alternately. Hence, the sequence alternately bounces between high and low values.

2) However, on the larger scale it becomes apparent that the sequence shows cycles, each with the same overall pattern but of increasing magnitude (Figure 1).

3) A closer examination of these cycles shows that within each cycle the high values climb to a maximum and then fall off to reach a value which is 1 more than the first low value of the next cycle. In contrast, within each cycle the low values keep linearly decreasing until reaching 1. Then they start again with a new starting value in the next cycle.

4) Each new cycle starts with a large jump in magnitude relative the previous cycle. We can define the start of each new cycle objectively as after when f[n]=n. We find that f[n]=n when n takes the values: 1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, 265721, 797162, 2391485, 7174454… This sequence m can be described by the formula:

m[n+1]=\dfrac{3^n+1}{2}, where n=0,1,2,3...

We may also recursively define it as m[n]=3\cdot m[n-1]-1, from n=2 onward after defining the first term m[1]=1. We will show below that this sequence m, which appears in the context of the cycles of f, also appears in several other seemingly unrelated mathematical structures with interesting properties. It is also numerologically interesting that the 7th cycle corresponds to the approximate length of the earth year in days: 365.

5) The determination of the sequence m allow us to trivially prove that the length of each cycle is:

3^n=1, 3, 9, 27, 81, 243..., where n=0, 1, 2, 3, 4, 5.... Thus, the expansion of the sequence is by the powers of 3.

6) The maximum value of each cycle is reached at the midpoint of each cycle and is attained when n is 1, 2, 3, 8, 21, 62, 183, 548, 1641, 4922, 14763, 44288, 132861, 398582, 1195743, 3587228… This novel sequence termed m_p can be described by the below formula:

m_p[n]=\left \lfloor\dfrac{m[n]+2}{2}\right\rfloor = \left \lfloor\dfrac{3^n+5}{4}\right\rfloor

7) The maximum value of each cycle is given by the novel sequence m_x: 1, 2, 6, 32, 231, 1922, 16836, 150152, 1347261, 12113042, 108980466, 980713472, 8826089091… m_x can be obtained by the formula:

m_x= \left \lfloor\dfrac{3^n+5}{4}\right\rfloor \cdot \left \lfloor \dfrac{3^n+ 9}{8} \right \rfloor where n=0, 1, 2, 3, ...

8) Thus, the ratio \tfrac{m_x}{m_p} is the sequence 1, 1, 2, 4, 11, 31, 92, 274, 821, 2461, 7382… defined by the formula:

\dfrac{m_x}{m_p}[n]=\left \lfloor \dfrac{3^n+ 9}{8} \right \rfloor

This sequence can also be generated from m_p by the formula:

\dfrac{m_x}{m_p}[n]=\left \lceil \dfrac{m_p[n]}{2} \right \rceil

We will see below that this sequence remarkably also emerges in another area of higher arithmetic.

9) Whereas the low values of f decrease linearly from their starting point in a cycle till they reach 1, the high values which they alternate with appear to be defined by successively larger parabolic arcs (Figure 2). We determined these parabolic arcs to have the general equation of the form:

y= \dfrac{x}{2} \left(3 m[n-1]+1-x\right)

Here, n=2,3,4... and each successive arc spans the high values in the range x= m[n-1]+1 to x= m[n]. Hence, we term sequence f the division-multiplication-parabola sequence (DMPS). Thus, in a sense our sequence is a “triessential” sequence with the number 3 being fundamentally linked to it in many ways.

Div_mult_parabola_Fig2Figure 2.

The idea of this type of parabola first came to us over 23 years ago in the context of trying to understand if natural selection might tend to select oligo-functional proteins over both purely mono-functional ones and those that perform a large number of distinct functions. The idea is each new function gained by a protein results in an increased cost for the other functions it performs; however, there could be a net fitness gain from the compounding of the capacity to now perform multiple functions. This would result in an optimal point after which the performance in each function will deteriorate too much to have net fitness gain despite the compounding. The result would be a parabolic arc similar to that obtained in the DMPS.

In the remainder of this article we shall discuss the connections we have found between the sequences associated with the DMPS and other mathematical objects.

The Mephisto-Waltz words

A Mephisto-Waltz word is a word in a two-symbol alphabet that is generated by a triplicative substitution system with the rules 0 \rightarrow 001, 1 \rightarrow 110. The growth is initiated with MW[1]=0. Thus, we get the following words:

0; 001; 001001110; 001001110001001110110110001 and so on. This can be graphically represented as the triplicative growth of circular cells with differentiation (Figure 3).

Div_mult_parabola_Fig3_MWFigure 3.

The Mephisto-Waltz words can also be used to generate another kind of pattern in the form of a square using Cantor’s pairing function. Cantor’s pairing function maps every ordered pair of non-negative integers (j,k) to a single unique integer n:

n=j+\dfrac{(j+k)(j+k+1)}{2}

Now, if we pair every ‘letter’ in the Mephisto-Waltz word with every other ‘letter’ in it with the above Cantor function then get the square pattern shown in Figure 4. Since there are four distinct pairings possible between 0 and 1, i.e. (0,0), (0,1), (1,0) and (1,1), under the the Cantor function each cell of the ensuing square matrix can have one of four values, each shown in a different color.

Div_mult_parabola_Fig4_MW_CantorFigure 4.

We can also apply a form of “epigenetic” information to the genetic encoding of a folding instruction in the two symbol Mephisto-Waltz word. It goes thus: We start out drawing a line segment in a certain direction. If we encounter a 0 we draw a line segment of fixed length in the same direction as we are currently oriented in. If we encounter 1 and it is in an even position (epigenetic information) then we turn by an angle of \tfrac{\pi}{2} and draw a line segment of the same fixed length in the new orientation. If we encounter 1 in an odd position in then we do the same but turning by -\tfrac{\pi}{2}. This results in the fractal “wave” illustrated in Figure 5.

Div_mult_parabola_Fig5_MW_fractalFigure 5.

Mephisto-Waltz words show an intimate connection to sequences emerging from the DMPS: First, given that they have a triplicative growth pattern their length grows as 3^n, which is the same as the length of the cycles of the DMPS. Second, the numbers of zeros in the Mephisto-Waltz words grow as the sequence m=1, 2, 5, 14, 41, 122, 365, which defines the points of transition to the next cycle of the DMPS. The numbers of 1s in these words grow as m-1. Thus in a sense the sequence m captures the ‘median’ growth of these words.

Standard order words in a 3-symbol alphabet

Consider an alphabet with 3 symbols. We can denote those 3 alphabets by the numbers 1, 2, 3. Then we write the following words in the this alphabet:

1, 12, 12123, 12123123123123, 12123123123123123123123123123123123123123 …

One observes that the process goes thus: we first write 1, then 12, which form the first two words. Then from the 3rd word onward we add 3^n letters (where n=1, 2, 3,...) in the form of repeats of 123. Thus, the length of these words grows as 1, 2, 5, 14, 41, 122… which is the same as the sequence m defining the transitions to the next cycle in the DMPS.

Standard order means that a later symbol of the alphabet cannot appear in the word unless the symbol earlier to it has already appeared in the word. Thus, 2 cannot appear in the word unless 1 has already appeared. Likewise, 3 cannot appear in a word unless 1 and 2 have already appeared. Thus, if traverse through the above-generated 3-symbol words from the one to the next we can create n-letter words with a maximum of 3-symbols in standard order:

For 1-letter words we can only have: 1
For 2-letter words we can only get: 11, 12
For 3-letter words we get: 111, 112, 121, 122, 123
For 4-letter words we get: 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233
So on (OEIS: A278985). Thus, the number of n-letter standard order words we can get in a 3-symbol alphabet is the same as the sequence m=1, 2, 5, 14, 41, 122....

The number of quadratic residues of 3^n

Quadratic residues were extensively studied by Carl Gauss in his celebrated Disquisitiones Arithmeticae. The quadratic residues for a number n are determined by considering all 0 \le a < n. Then q= a^2 \mod n. Further, given that \left((n-a)^2 \right) \mod n= a^2 \mod n, we only need to compute the residues for 0 \le a < \left \lfloor \dfrac{n}{2} \right \rfloor.

For example, if we take n=9, then we have the residues: 0=(0^2) \mod 9; 1=(1^2) \mod 9; 4= (2^2) \mod 9; 0=(3^2) \mod 9; 7= (4^2) \mod 9. Thus, for n=9, the numbers 0, 1, 4, 7 are its quadratic residues. We observe that of the numbers from 0 to (9-1=8) the following are not represented: 2, 3, 5, 6, 8. These are the quadratic non-residues of 9.

Let us now consider the quadratic residues of the powers of 3 and count how many of them are there for each power:

3^0: 0; n=1 \\ 3^1: 0, 1; n=2\\ 3^2: 0, 1, 4, 7; n=4\\ 3^3: 0, 1, 4, 7, 9, 10, 13, 16, 19, 22, 25; n=11\\ 3^4: 0, 1, 4, 7, 9, 10, 13, 16, 19, 22, 25, 28, 31, 34, 36, 37, 40, 43, 46, 49, 52, 55, 58, 61, 63, 64, 67, 70, 73, 76, 79; n=31
So on…

We see than the number of quadratic residues for the powers of 3 specify the sequence \tfrac{m_x}{m_p} [n] starting from the second term. This is the ratio of the maximum value to the midpoint of the cycle of the DMPS where it is attained.

We also noted that a sequence closely related to \tfrac{m_x}{m_p} [n] turns up in the graph theory. While \tfrac{m_x}{m_p}[n]=\left \lceil \tfrac{m_p[n]}{2} \right \rceil this sequence is defined as:

\rho'[n]=\left \lfloor \dfrac{m_p[n]}{2} \right \rfloor

In graph theory a circuit is defined as graph in which by passing through adjacent vertices one can reach the same vertex. Now, if we specify that adjacent vertices should be colored using different colors, then we need a minimum of 4 colors to color all vertices of any circuit graph. The number of distinct configurations that a circuit graph with n vertices can be colored with 4 colors was shown to be \rho'[n] by Bernhart (OEIS: A006342). This sequence goes as: 0, 1, 1, 4, 10, 31, 91, 274, 820, 2461, 7381, 22144, 66430, 199291, 597871, 1793614 … One can see that it differs from \tfrac{m_x}{m_p} [n] by 1 at every odd n, i.e. n=2k+1.

Thus, rather notably, a simple arithmetic procedure generates the DMPS, with associated sequences bearing connections to other seemingly unrelated mathematical objects pointing to the pervasiveness of certain combinatoric numbers.

Posted in Scientific ramblings | Tagged , , , , , , , , , , ,

A brief overview of the last campaign of Chingiz Khan and the issue of succession in the Mongol empire

Succession is always an important issue in history. The legacy of a mighty ruler and/or founder of an empire might quickly unravel if the issue of succession is left unresolved. In Hindu history the Gupta-s were marked with glory because following Candragupta-I they managed to maintain a line of highly successful rulers with relatively smooth succession: Samudragupta-> Candragupta-II Vikramāditya-> Kumāragupta-> Skandagupta->Budhagupta. Before them, the Maurya-s had several succession problems but managed to put out a line three mighty rulers. However, sometime during the reign of Aśoka things started going bad and they never able to produce one within their own line who could restore their power. In the case of the house of Śivajī, many of the troubles for the fledgling neo-Hindu empire came as a result of problems with succession. Among the Hindus, primogeniture meant that Śivajī’s eldest son Śambhu would ascend the throne. However, he had shown bad behavior and betrayed the cause of svarājya about a couple of years before the great rajan’s death. Hence, he had been kept under detention at the Panhala fort and some of Śivajī’s veteran ministers Moro Piṇgaḷe and Aāji Datto had turned against him. His stepmother was trying to place her young son Rājārāma on the throne. The ensuing conflict seriously damaged svarājya at a critical juncture in the struggle of the Hindus against the Mohammedans. Chingiz Khan faced a parallel situation of indiscipline and possible disloyalty from this eldest son. His eldest son Jochi was born shortly after he recovered his wife Börte who in captivity of his enemies for few months. A conflict broke out between Jochi and his brother Chagadai and given the timing of his birth his legitimacy as the son of Chingiz was called into question. A council was called and Chingiz and his generals like Chormagun Noyan worked on patching up the issue between his sons. While his father declared him to be a legitimate son to the rest of his sons, the tensions persisted and towards the end of his life he remained away in own ulus disobeying his father’s orders when called to meet him. It appears that the great Khan might have sent his sons Chagadai and Ögödei to bring Jochi to him to be disciplined. The tensions ensuing from this could have affected the succession issue but two factors played a role in resolving it. First, among Altaic peoples ultimogeniture was the generally accepted rule unless it was overruled by some clause of the previous Khan. Second, Jochi died shortly before Chagadai and Ögödei set out to bring him to the Khan, thus taking him out of the contention for succession. But that aside, the success of the Mongol empire was in part how the succession to Chingiz Khan was handled.

In 1223 CE, shortly after Jebe and Sübe’edei had crushed the combined army of the Russians and Qipchak Khanate on the Kalka River, Chingiz Khan in a council of senior Mongol commanders and officials declared that Ögödei would succeed him as the great Khan. In making his choice he considered the following: His first son Jochi was a competent general who had distinguished himself early in his career in the Siberian conquests, in the annexation of the Kirghiz horde, and later during the attack on the Mohammedans while seizing the fortified settlements of Signakhi, Yanikand (the capital of Oghuz Turks) and Jand. However, during the siege of Urgench, his strategy and pace of the campaign were criticized by his brothers Chagadai and Ögödei. Finally, it was Ögödei who stormed the city though it was promised already by the great Khan to Jochi. This was followed by his conflict with Chagadai during which his legitimacy as the son of the Khan was doubted. He restored his military credentials by aiding Sübe’edei after the death of Jebe. However, after this, he disobeyed his father and retired to his ulus and never met him again. Thus, he was ruled out. Chagadai, the next son, was also a competent warrior; however, his quarrels with Jochi, his temper, and recklessness in the quriltai-s did not please the Khan. Hence, he too was passed over for being the great Khan.

The next son Ögödei was seen as a man of balanced temper but at the same time a fierce warrior who proved himself in the thick of battle. When in his early years Chingiz fought the alliance of Jamuqa and Toghrul Wang Khan of the Kerait Turks, Ögödei, still in his teens, was seriously injured by an arrow that hit his neck. He was then saved by Chingiz’s foster-brother Boroqul. Surviving this injury, he led the Mongol forces again the Jin (Jürchen) to conquer the city of Ordos in Inner Mongolia. In the campaign against the Mohammedans of Khwarizm, he along with Chagadai seized the fortified city of Utrar and then took Urgench. In Afghanistan, he smashed the Mohammedans of Ghazni and massacred them (truly their karma was being paid). Thus, Chingiz Khan chose Ögödei as his preferred successor to the post of the great Khan of the unified empire. At the same time, the other sons were to get their own ulus-es. They were to hold a quriltai to confirm if Ögödei was competent and if members from each of the lines elected him then he could ascend as the great Khan, with all of them pledging their solidarity to him. In the interim, the default state of Altaic ultimogeniture was to come into play with Chingiz’s last son Tolui serving as acting Khan until the quriltai could be called. This tradition of ultimogeniture appears to have been adopted by the Altaic peoples from the steppe Iranians who were the lords of the land before them. Keeping with the old tradition of ultimogeniture the Khan’s youngest son Tolui was awarded the biggest share in the Khan’s personal inheritance. This also included the largest share of the military which eventually allowed the ascendancy of his lineage.

To take a look at the succession as it happened we shall briefly revisit the final years of Chingiz Khan. When Chingiz Khan left to campaign against the Mohammedans, his Chinese campaign had to proceed at a slow pace as most of his forces were deployed in the west. He had left his friend from youth and able general Muqali to conduct this campaign against the Jin. Muqali with his limited forces managed to preserve to Mongol conquests in China and also keep the Jin on their feet with regular raids into their territory. Then he conducted an audacious campaign with his small Mongol forces by launching an invasion of the Wei River valley at the southern bend of the Yellow River. Thus, he kept the pressure on the Jin till his death in 1223 CE. Then his son Boro and grandson Tash continued the campaign against the Jin. They expanded the campaigns to attack the Han Chinese empire of the Song who came to aid the Jin. However, with their limited army, they could in no way conquer these vast domains completely. In 1225 CE, having smashed the Mohammedans of Khwarizm, Chingiz Khan returned to Mongolia to review the Chinese situation.

Around the time of Muqali’s death, the Tangut of Xixia empire got a new aggressive emperor Li Dewang. He decided to launch a massive attack on his old enemies, the Mongols. For this, he formed an alliance with the Jin and also mobilized the Yellow Uighurs against the Mongols. The Mongol generals Boro and Tash staved off the immediate attacks till Chingiz Khan returned. The Khan strategized that to conquer the vast realm of China he had to first outflank the two Eastern Chinese empires from the west by destroying the smaller western empire of the Xixia. The Tangut expected him to stiffen Muqali’s successors by marching from the east but the Khan surprised them by assembling a large Mongol force to the west and attacking them from Gansu corridor in 1225 CE. The great Khan marched with close to 120000 men with the largest division of several tümen-s (~80000) personally led by him, with the rest led by his brother Qasar whose health was declining due to gout, the ace general Sübe’edei baghatur, and the general Chaga’an. Sübe’edei first crushed the Yellow Uighurs and took them out of their way. Chingiz Khan directed him to systematically conquer the western towns of the empire and facilitate the penetration by Chingiz and Qasar deep into the Xixia territory. Taking their old capital, Qara-Qoto, the Khan steadily advanced eastwards and by August of 1226 CE despite fierce resistance from the Tangut aided by the Jin from the East the Khan forced their second largest city, Wuwei to surrender.

At this point, Li Dewang died and Li Xian ascended the throne as the emperor. Li Xian claimed he was the Buddha of the Age but that did not seem to help much. Advancing further Chingiz Khan then besieged the fort of Lingwu which was just a short distance from the capital Yinchuan. Li Xian sent a massive army of 300000 Tanguts hoping that he could comprehensively overwhelm the Mongol army. But in the battle fought on the banks of the Yellow River the outnumbered Mongol forces under the inspired leadership of the great Khan nearly completely annihilated this Tangut army in November of 1226 CE. In 1227 CE the Mongol army besieged Yinchuan the capital of the Tangut. The Jin tried to help the Xixia empire survive by sending aid from the east. But Chingiz Khan sent his mobile squadrons to punish them. One rapidly moving Mongol force launched an audacious assault deep into Jin territory to strike their capital Kaifeng and return. Shaken by this attack, the Jin asked for peace but Chingiz turned down the offer and already prepared an invasionary force to next deal with the Jin. However, as the siege of Yinchuan was drawing to a close the Khan fell from his horse evidently during a hunt and probably sustained an injury that resulted in an infection. Others believe that he might have contracted some infection independently of a fall. He was taken in a closed bullock cart to a secret hideout the Mongols set up in the forests of the Liupan mountains. He realized he was on his deathbed and called his clansmen and generals around him. He gave them a final lecture in which he laid out the lines of action to expand the Mongol empire he had founded both to the east and west. He then stressed the issue of unity between the different lines of his clansmen with the famous example of the single arrow and bundle of arrows. He asked his people to follow his plan regard his successor and told them: “Let not my end disarm you, and on no account weep or long for me.” Before dying he also seems to have made his long-term succession plans clear. The status of the great Khan was not to remain with the house of Ögödei forever. He said that his grandson through Tolui, the wise Qubilai, would someday adorn his throne. Then he died aged something between 65 to 70 on either on 18th or 25th August 1227 CE as per different reckonings.

The Mongols kept the news secret and his youngest son Tolui became the acting Khan to allow the campaign to proceed. In September 1227 CE Li Xian unable to hold the capital surrendered to the Mongols. They had is name changed from the Buddha of the Age to Shidurgu – the one who has been made a vassal. Thus, having stripped him of his divinity they immediately executed him as a treacherous vassal. Then they erased the city of Yinchuan with its citizens except for the bauddha teachers of the Karma Kagyu tradition and their monastery. The Mongols demolished and dug up all the graves of the Tangut emperors and dispersed their remains. The Tangut had ties with the Pāla and Sena dynasties of Vaṇga before the devastation of their land by the Mohammedans. Thus, several of Li Xian’s surviving relatives fled towards Vaṇga but with the ongoing Mohammedan depredations throughout the region, they settled in the more inaccessible domain of Sikkim.

Over the year 1228 CE, Tolui assembled members of all the branches of the house of Chingiz for a quriltai. Before they joined in Mongolia, a quick campaign was conducted in the west beyond the banks of the Volga pulverize and subjugate the Volga Bulgars who had staved off the earlier raid of the Mongols during their attack on the Russians and the Qipchak Khanate. The quriltai met at Köde’e Island on the Kerülen River in Mongolia. There the majority of the lines voted in favor of Ögödei becoming the next great Khan and his brother Tolui dutifully handed over the throne to him. Jochi’s most prominent son Batu also pledged complete solidarity to his uncle. Thus, the unity of the Mongol empire was retained under Ögödei and he ascended the throne taking on the title of Dalai-yin Khan. This title was likely semantically equivalent to Chingiz Khan and means the oceanic ruler. A derivative of it was later also conferred by the Mongols to the chief Lama – the Dalai-lama. It is likely that this event was marked by the production of the famous seal bearing the words:
Möngke Tengri-yin Küchün-tür Yeke Monggol Ulus-un Dalai-yin Khan-u jarligh il bulqa irgen- tür kürbesü büsiretügüi ayutughai
By the Power of great god of heaven, the Edict of the oceanic Khan of the Great Mongol ulus. If this reaches a pacified or a rebellious people, it must respect [it] [and] it must fear (Text and Translation from Igor de Rachwiltz).

He immediately commissioned what become the core of the Secret History based on the records kept by Shigi-qutuqu, the adopted son of Chingiz Khan. It is not entirely clear if Shigi-qutuku also wrote the core of the Secret History. The phrase “khan ecige minu” meaning “khan, father of mine” is seen occasionally in the text suggesting that it might have been him. However, some historians think that in general Chingiz was referred to as the father of the Mongol nation at some point during the redaction of the text (Today there is evidence for some biological basis for that).

Ögödei immediately got around to stabilizing the newly won empire. As per the wishes of his brother Tolui he appointed Sübe’edei Baghatur as the supreme military adviser of the Mongol empire. This brilliant general had campaigned across the whole of Eurasia and was beyond doubt one of the greatest military leaders of all times. Tolui was given the title Yeke-noyan (some say the yeke was added after his death) meaning the great lord and advised the great Khan on all matters. Chormagun noyan was appointed to lead a Mongol army to finish off immediate unsettled issues in the west like the destruction of Jalal-al din and conquering Armenia, Georgia, Chechnya, and Azerbaijan. Shigi-qutuqu was appointed to handle the implementation of the yasa of Chingiz Khan and set up the administrative structure for the whole empire. The gigantic Khitan (an earlier branch of Mongolic people) scholar Yelü Chucai had been brought out from his early retirement as a Zen bauddha monk by Chingiz Khan and appointed to his advisory council, especially for his meteorological knowledge. He was left back by the Mongols after the campaigns in the West to organize their rule there. It was then that Yelü Chucai obtained an Indian rhinoceros and showed it to the Mongols (The śākya buddha had in a former birth seen a rhinoceros directly attain buddhatva). The Mongols declared that the animal was a sign of the great god Möngke Tengri and that India should not be invaded as it was the holy land graced by this divine animal. This gave him a great aura of respectability and he was called by the great Khan to help him with the administration in the last year of his life. Tolui while the acting Khan asked Yelü Chucai settle the major religious conflicts which were taking place between bauddha-s and Taoists in Mongol China. He also actively participated in getting everyone to agree on electing Ögödei and was accordingly rewarded by Ögödei with an appointment as the supreme official of the revenue department of the Mongol empire.

An important point that is often not stated is the role of Ögödei in stabilizing the Mongol empire. At Chingiz Khan’s death treasury was in precarious condition. The Khan had put everything into the Xixia campaign. Temporarily the situation was stable from the enormous booty obtained with the destruction of Xixia empire and the raids on the Jin. However, Ögödei needed to quickly stabilize things for the long term before further major campaigns could be undertaken. Hence, he constituted a senior council drawn from the keshikten (the Khan’s inner guard) along with Yelü Chucai to develop a comprehensive taxation system across all conquered territories with revenues assessed as per the nature of productivity of each territory. A whole series of Mongol and local officials were raised and the system put in place throughout the vast empire within a matter of four to five years. This went hand-in-hand with a courier system to allow communications throughout the empire. This administrative achievement pulled off by Ögödei is probably the most underrated but important facet of the development of the Mongol empire. Beyond that, he also was proactive in his diplomacy to get the houses of all his brothers to stand firmly with him and cooperate as part of the unified Mongol empire for future campaigns.

Thus, key aspects of the success of the Mongol Empire were Chingiz Khan’s clear succession plans, their orderly and quick enactment, and finally the successor Ögödei’s effective administrative action. He first settled and firmed up fiscal and organizational issues of the empire in great detail before launching the next major phase of distant military activity. As this was under way he commissioned the campaigns under Chormagun Noyan to create the strategic base for big distant ones which were to follow. Only thereafter the great invasion of the lands of the White Christians in Europe and the mopping up of the Jin empire in China were launched. It is in comparison to this that the Maraṭhā succession was rather poorly executed. Though Śambhu took power rather quickly, it came at the cost of the brutal execution of senior ministers like Annājī Datto. He also was hardly effective in terms attending to fiscal, administrative and strategic issues. While his early campaigns were well-executed were not followed up with the vigor and swiftness his father showed. When Ögödei was facing doubts in how the Chinese campaign should proceed his senior strategist Sübe’edei showed the way forward and led them to spectacular victories. Śambhu however showed little interest in supporting his astute military adviser Hambirrāv Mohite‘s plans at a critical juncture. These considerably strained the Maraṭhā-s and they eventually survived only due to Śivajī’s farsighted plans and ministers like Rāmacandra amātya.

Posted in History | Tagged , , , , , , , , ,

The mean hyperbola and other mean functions

Let a, b be two numbers such that,
0\le a \le b
We use a, b to construct a specific rectangular hyperbola using one of the following methods:
Method-I (Figure 1: this is based on an approach we described earlier)

hyperbola_constr_mean2Figure 1

1) Mark point C (-a, a), which will be the center of the hyperbola to be constructed.
2) Draw two perpendicular lines through C respectively parallel to the x- and y-axes. These two lines are the asymptotes of the hyperbola.
3) Bisect the angle between these asymptotes to construct a line with slope m=1 passing through C.
4) On this line mark the two foci of the hyperbola F_1, F_2, such that they are are equidistant from C and separated from each other by a distance of 4\sqrt{ab-a^2}.
5) With F_1 as center draw a circle with radius equal to 2\sqrt{2(ab-a^2)}. This will be equal to the distance between the two vertices of the hyperbola.
6) Let Q be a point on the above circle. Draw lines \overleftrightarrow{F_1Q}, \overleftrightarrow{F_2Q}.
7) Draw the perpendicular bisector line of \overline{QF_2}. It cuts \overleftrightarrow{F_1Q} at point P.
8) The locus of P as Q moves on its circle gives you the required rectangular hyperbola (red in Figure 1).

Method-II (Figure 2)

hyperbola_constr_mean

Figure 2

1) Mark point C (-a, a), which will be the center of the hyperbola to be constructed.
2) Draw two perpendicular lines through C respectively parallel to the x- and y-axes. These two lines are the asymptotes of the hyperbola.
3) Bisect the angle between these asymptotes to construct two perpendicular lines with slope m= \pm 1 passing through C.
4) On the line with slope m=1 mark the two foci of the hyperbola F_1, F_2, such that they are are equidistant from C and separated from each other by a distance of 4\sqrt{ab-a^2}.
5) On the line with slope m=-1 mark a sequence of points and draw a sequence of coaxial circles, which will pass through each of those points on this line and also the two foci F_1, F_2.
6) Each of these circles will cut the two asymptotes on total of 4 points. On each side separately draw segments joining the respective points of intersection of each circle on the two asymptotes (Figure 2).
7) The envelope of these segments is the desired hyperbola.

The said hyperbola has the equation:
y=\dfrac{a(x+b)}{x+a}

hyperbola_meanFigure 3

One observes that its upper branch cuts the y-axis at (0,b) and by construction it is asymptotic to x=-a, y=a (Green curve in Figure 3). But what else notable about this specific hyperbola? Note the intersections of the following lines with the hyperbola (Figure 3):
The line x=a intersects the hyperbola at y=\mu_A, the arithmetic mean of a,b.
The line x=b intersects the hyperbola at y=\mu_H, the harmonic mean of a,b.
The line x=y intersects the hyperbola at y=\mu_G, the geometric mean of a,b.

Thus, this hyperbola can be considered a mean-generating curve where the means of the two numbers a,b can be easily obtained by plugging certain nice values of x. It also furnishes the proof for the fact that the three primary means of two numbers lie on a single hyperbola between the point where the hyperbola cuts the y-axis, point B(0,b) and the asymptotic line passing through A(0,a). One notices that the \mu_A cuts the segment \overline{AB} in half. The geometric mean \mu_G cuts \overline{AB} below \mu_A and the harmonic mean \mu_H cuts it below \mu_G. This geometry allows one to define two further means, which are inversions (reflections) of \mu_G and \mu_H respectively on the \mu_A line. We define these inversive means as \mu_{Gi} and \mu_{Hi}. We discover that the intersection of the line x=\tfrac{a^{3/2}}{\sqrt{b}} with the hyperbola generates y= \mu_{Gi} = \tfrac{a^{3/2}+b^{3/2}}{\sqrt{a}+\sqrt{b}}. Likewise, the intersection of x=\tfrac{a^2}{b} with the hyperbola generates y=\mu_{Hi}=\tfrac{a^2+b^2}{a+b}. Thus, we have 5 means with the arithmetic mean as the central mean bisecting the segment \overline{AB} with two means above it and two means below it (Figure 3).
In trying to understand these additional means coming from our hyperbola we learned of the work in this regard by Derrick Lehmer-II. He defined two mean generating functions. The first of them is (orange in Figure 3):

y=\dfrac{a^{x+1}+b^{x+1}}{a^x+b^x}

We notice that this function is a sigmoid curve having y=a and y=b as its asymptotes (Figure 3). We realized that this function of Lehmer generates the same means as the above-constructed hyperbola. When x=0 we get \mu_A; when x=-\tfrac{1}{2} we get \mu_G; when x=-1 we get \mu_H. The two other means \mu_{Gi} and \mu_{Hi} respectively emerge at x=\tfrac{1}{2} and x=1. Thus, the same symmetry as the with the hyperbola is recapitulated by this function (Figure 3).

Lehmer’s second mean-generating function is (red curve in Figure 3):

y= \left(\dfrac{a^x+b^x}{2}\right)^{\frac{1}{x}}

We observe that this curve is also bounded by the same asymptotes y=a and y=b; however, it converges to them at very different rate. At x=1 it generates \mu_A; at x=-1 we get \mu_H and it intersects the first mean-generating curve (Figure 3). At x=2 we get the \mu_Q, i.e. the quadratic mean or the root mean squared (RMS). This mean cannot be obtained by a nice value of x in either the first mean-generating function or the mean hyperbola. What about the value of the second mean-generating curve at x=0? To get that we need to do is to evaluate the below limit:

\displaystyle \lim_{x \to 0} \left(\dfrac{a^x+b^x}{2}\right)^{\frac{1}{x}}

At first sight, it would seem that it is indeterminate because we get an ugly division by zero making it impossible to evaluate directly. Hence, this cannot be done and we have to take recourse to Johann Bernoulli’s method (commonly called L’Hospital’s method).

We first take the logarithm of the above expression to get:
\dfrac{\log\left(\dfrac{ (a^x + b^x)}{2}\right)}{x}

Then we differentiate the numerator and the denominator. The denominator is reduced as \tfrac{d}{dx}x=1. For the numerator we get:

\dfrac{d}{dx}\left(\log\left(\dfrac{ (a^x + b^x)}{2}\right)\right) = \dfrac{a^x \log(a) + b^x \log(b)}{a^x + b^x}.

We next take the \lim {x \to 0} to get \log\left( \sqrt{ab}\right). We then reverse the logarithm operation by exponentiation and evaluate the limit of the second mean-generating function at x=0 to be \sqrt{ab}. Thus, Lehmer’s second mean-generating function yields the geometric mean at x=0. Lehmer showed that there are thus two families of means of which one includes the inversions of the geometric and harmonic means on the arithmetic mean and the other which includes the quadratic mean or RMS. The only means that are common to both families are \mu_A, \mu_G, \mu_H and the two mean generating curves intersect at y=\mu_H (Figure 3). Thus, these 3 are the only fundamental means.

While these two families of means do not come together is there an operation where combining a fundamental and family-specific mean gives an interesting result:

Let a_0=1, b_0=1 and n \in \mathbb{N},
a_{i+1}=(\mu_Q(a_i, b_i\cdot \sqrt{n}))^2
b_{i+1}=(\mu_G(a_i, b_i))^2

Then \dfrac{a_{i+1}}{b_{i+1}} \to \sqrt{n}
This gives us a means of obtaining rational convergents for a given irrational square root. For example if we use n=6 in the above procedure we get:

\dfrac{7}{2}, \dfrac{73}{28}, \dfrac{10033}{4088}, \dfrac{200931553}{82029808}, \dfrac{2523338293565406}{1030148544608239}

The last of these yields \sqrt{6} correct to 11 places after the decimal point.

Also see:
1) Means and conics
2) The Hindu square root method

Posted in Scientific ramblings | Tagged , , , , , , , , , , , , ,

A Political roundup August 15 2018

As I remarked to a friend, much of the stuff in (geo)politics which is relevant to us is what we have predicted before based on the relatively straightforward model of mleccha-marūnmattābhisaṃdhi i.e. the anti-heathen coalition of those infected by Abrahamistic meme-plexes and their secular mutations. What remains is just too uncertain to predict with our limited knowledge and ability. This might be the more interesting and perhaps the more dangerous part of our existence, but for most part we simply have to watch it unfold. That is part of the reason why we are not too motivated to write a lot about this on these pages. Nevertheless, we felt it might be appropriate to provide review of for another Independence Day has dawned and given that the elections are scheduled for next year.

So let us take a panoramic view by traveling back in time. The great demolition at Ayodhya on 6 December 1992 was a landmark even that hinted that the Hindus were no longer going to take things lying down. hence, we call upon fellow Hindus to observe a moment of remembrance for the men who gave up their lives to bring down that symbol of marūnmatta tyranny. This event and its aftermath created the first notable post-Independence ferment among the Hindus to gain political power and come out of the eclipse of the Gandhi-Nehru dynasty. Overseeing the demolition through benign inaction was the Prime Minister PV Narasimha Rao, an unassuming man of intelligence and a deep and enormous linguistic capacity from the Andhra country (notable was his facility in picking new human and computer languages). But PVNR’s main contribution was his reform of the Indian economy, which for the first time allowed Indians to experience the real middle class life. This boosted the growing confidence of Hindus and after a period of uncertainty culminated in the first NDA government under AB Vajapayee.

While as an adherent of the śruti I found his keeping of the hallowed title of Vajapayee without truly living up to it grating, he was a man of importance for the survival of the Hindu polity. His most important achievement was the conducting of the nuclear weapons tests totally surprising the mleccha and cīna enemies – this was a kind of boldness which had not been exhibited before. Next, he was able shepherd the nation through the economic blockade imposed by the evil mleccha-s and show that the economic platform, which PVNR had laid the foundations for, was indeed robust. In this period he had to handle the jihad of the marūnmatta-s in the Kargil war. The secularized Hindu army carried the day and showed that despite the mleccha attempts to curb them with sanctions they Hindus were not to be taken as walkovers. The mleccha-marūnmattābhisaṃdhi was at this point flummoxed by both the military victories and economic resilience of the Hindu nation and resorted to their usual trick of deploying the internal marūnmatta bomb – the legacy bequeathed on the Hindus by the faux Mahātman and Nehru. The most prominent among these attacks was the arson in Lāṭānarta, where emboldened marūnmatta-s burned down a train carrying Hindus killing many. The man who came to the fore in this dire situation was not ABV but his future successor the Lāṭeśvara from the tailakāra-jāti. It was due to him that the Hindus were able to show to the rākṣasa-like marūnmatta-s that they could not get away with their usual crimes. This was instrumental in bringing peace to the state and teaching a lesson to the marūnmatta in the only language he understands.

But then Hindus are renowned for dropping the axe on their own foot. Thus, lulled by the relatively good times the benign rule of ABV had brought, deciding not to take a long term vision, they instead facilitated the return of the Gandhi-Nehru dynasty via UPA-I. This government was led in proxy by the Helena of India who was a windfall for the mleccha-s, and she ably served as their agent in undermining the Hindu nation. To keep the Hindus in check, the marūnmatta-s were unleashed on a routine basis and this reached a culmination in the invasion of Mumbai on Nov 26 2008 by a mere band of 10 ghazi-s bringing back memories of Ikhtiyar al-Din Bakhtiyar Khalji, the hero of Bangladesh. As the UPA kept facilitating anti-heathen action, the NDA was unable to even put up a proper fight – ABV faded away into a vegetative state and his lieutenant, the aging saindhava LKA lost the plot in many ways (Note his egregious appointment of Kulkarni as an adviser). This only consolidated the grip of the Abrahamistic convergence against the Hindus. To worsen matters, it looked as though the cīna-s might launch a decisive strike on the enfeebled secularized Hindu army – things almost looked lost for the Hindu nation.

It was in such dire circumstances that the Lāṭeśvara became Dillīśvara in 2014. The mleccha-s having known his capacity from his restoring of the Lāṭānarta country greatly feared him. For 12 years they had kept him out their countries because they hated him as the symbol of what they hated most – the unconquered heathens of Hindustan who were the last great bulwark of that old and brilliant Indo-European heathenism, which they had either ground to dust or placed in museum closets. This heathenism was a rival worldview to all that the counter-religions of Abrahamism represented in their essence. Its very presence was a negation of the narratives of Abrahamism and it had to be exterminated. If there was one leader among the Indian masses who could give it a lifeline it was the Lāṭeśvara. Hence, they summoned all they could could in the form of their first responders to prevent his acquisition of power. They raised fake leaders like the broom-wielding koṭvāl of Delhi and the hazardous perpetuator of Gandhian blunders. But none of this worked in the long-run and the Lāṭeśvara took power.

Among the failures of the ABV-LKA duo was their inability to protect the homeland security of Bhārata from marūnmatta-s, śavasādhaka-s and other kaṇṭhaka-s. We had: the hijacking followed by the humiliating release of demonic ghazi-s; the train attack; the ghazwat on the Parliament. Further ABV was hobbled by the machinations of the possibly crypto-preta president KR Narayanan. This is where the Lāṭeśvara NM focused. Despite his inadequacies on the ideological front, his lieutenant Dobhal was able to be quite effective in curbing the violence of the marūnmatta-s. He also dented their ability to finance such operations by the secretive demonetization maneuver. His other lieutenant Rajnath Singh, again, despite his inadequacies, has done a reasonable job in prosecuting a vigorous assault against the secularized mutation of Abrahamism, namely the socialist terrorists of internal India. On the external front the he handled the confrontation with the belligerent Han by tackling the Doklam conflict really well. He also sent a message to the ghazi-s by directing the secularized Hindu army to launch “surgical strikes” against them. This had a psychological effect more than anything else – perhaps the Hindus were doing it for the first time since the Maratha punches delivered in their heydays.

On the economic front things are less clear, in part because I am not qualified to assess the matters too precisely. The general trends point to some success in this regard, especially in terms of curbing and to a degree reversing the damage caused by the UPA misrule. However, the demonetization and the goods and services tax, while done with good intentions and with long-term benefits in mind, might have affected many adversely; however, this is perhaps a matter of perception. On the external front, while NM’s foreign policy has been clearly more robust than that managed by the flaky Jaswant Singh under ABV, its success is not entirely clear. The handling of the Nuclear Suppliers Group matter does look like a failure to us. Finally, like a good Hindu king ought to do, NM has paid much attention to the issue of jana-kṣema and made major strides in this direction. He himself has led the svaccha-Bhārata-abhiyāna from front in attempt the impart the much-need civic sense to the undisciplined Hindus. The ground connectivity progress managed by Gadkari and railways by Prabhu/Goyal seem to be bright spots too. However, specific Hindu issues relating to temple administration, temple rights, animal husbandry and ground level prevention of the infection spread by dayi-s and evangelists have not been satisfactorily addressed.

That last point in the above discussion brings us to proverbial “elephant in the room”. During the UPA rule the mleccha-marūnmattābhisaṃdhi had systematically infiltrated the judiciary and the civil service with pro-Abrahamistic elements. As India is ruled by a democratic form of government, NM and his lieutenants are having a difficult time undoing the evil of this infiltration. This in part is the basis of their inability to do much for certain specific Hindu issues. Going forward, this could result in enormous damage to the Hindus. One only hopes that NM is doing his best to uproot these plants of the enemies completely revamp the affiliation of the administrative machinery. Beyond this, our enemies are certainly rattled by this Julian-like come back of the H under NM. But will he prove to be just that – a Julian?

The mleccha-s and the marūnmatta-s would definitely want it to end that way and NM is going to have to fight hard to keep the saffron flag fluttering. Among other things they would continue their strategy of raising false leaders, like the man of the broom, in various local settings to create a general ferment. The idea here is not to create a rival for NM but to damage the impact of his janakṣema. The śava-s would be used to harry the polity – e.g. the Sterlite Copper agitation in the Tamil country. They would also be tempted to deploy the sword arm of the marūnmatta to attempt something big and bloody. Their new agent in TSP Imran Khan might also be deployed for exerting pressure from western Mohammedan fragment of India. The agent of the Eastern Mohammedan fragment, the white-shrouded evil daughter of Bakhtiyar would be used to expand violence against the Hindus in the east. A political alliance would created around the Kangress and the dredges of the old UPA to attack the NDA like the various enemies of Sudāsa ganging against him. The cīna-s might try to fish in these troubled waters too but we suspect that Trump’s trade-war might come to the aid of the Hindus here. The mleccha deep-state itself is having problems due to the unexpected triumph of Trump. This might keep them busy and Hindus should exploit that. However, the techniques developed against Trump are and will be deployed against NM and the Hindus in India. Finally, the mleccha-s know that if they incite something big and bloody too early or too late it could end up consolidating the Hindus. Hence, we tend to think that the path they would prefer is that of a “million mutinies”. The malcontents from the depressed classes and other groups will be cultivated and deployed. The purchased “news traders”, much like the Piṇḍāri purchase by the English, would be used to amplify these disturbances. Reinforcements would be sent to the socialist terrorists. The idea would be to simultaneously take the sheen of the vikās and break up the unity among the Hindus. If NM returns to power then the stage would be set for bigger and more gory confrontations whose exact unfolding would depend on other geopolitical events of the future.

As a tailpiece we should mention that within hours of completing the body of this text the news reached us that one of the protagonists of the above story, ABV, has passed away after a long life — the last of those were hardly worth living. We have been critical of him on these pages on more than one occasion but now that he belongs the realm of the manes we have to acknowledge his historic role with gratitude. He certainly built the platform that Hindus can use to move forward and the one that the Lāṭeśvara is using. His end brings down the curtain on this turn in the meandering of the Hindu nation. Many Hindus have been spending the last four years doing nothing but bitching about NM. They are nothing but armchair activists who have not participated in electoral contests or organized protective services on the ground. One thing we can tell such folks is do your own little bit for the dharma at the grassroots level. Do not expect the prime minister or mahānta yogī Ādityanātha to be a quantum entity who is at multiple places at the same time performing bābāistic miracles. Also remember that certain parts of the country are seriously compromised with the infections and batting for them would not save them unless they are willing to chip in too. Finally, this period has also seen the death of the Dravidianist leader, the hater of brahma, and the corpulent woman who attempted to destroy the Kumbhaghoṇa maṭha. The Hindu leadership needs to act quickly in this window of opportunity to eradicate the evil of Dravidianism.

Posted in Politics | Tagged , , , ,