Doc/Articles/Play174
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
27. Erdös Numbers and Pierce and Engel Expansions
. By Eugene McDonnell. First published in Vector, 17, 4, (April 2001), 111-122.
If you wish in the world to advance,
Your merits you’re bound to enhance,
You must stir it and stump it,
And blow your own trumpet,
Or, trust me, you haven’t a chance!
W. S. Gilbert, Ruddigore
Introduction
This paper discusses a way in which mathematicians are connected to each other, much like the six degrees of separation of the play and film of that title by John Guare, or the Bacon numbers associated with the film actor Kevin Bacon. It then discusses a paper written by two of these interconnected mathematicians that gives two ways of representing a rational number that were new to me. The paper also had some personal relevance. In discussing the subject matter of the paper I’ll define a number of adverbs and a conjunction, the first serious use I’ve made of these J possibilities. Finally, I’ll apply the verbs I define in connection with the almost 4000-year old Egyptian mathematics found on the Rhind papyrus.
Erdős Numbers
I heard a talk a few years ago given by the mathematician Ronald Graham, of the Bell Laboratories, in the course of which he discussed Erdős numbers. Graham had been a frequent collaborator with the mathematician Paul Erdős and even had a room set aside in his home for him. This was to facilitate visits by this eccentric nomad, who, in his later life, drifted from one collaborator to another, with only his suitcase and his mind, greeting his next host with the words, “My brain is open!”[1]. The web site:
http://www.oakland.edu/~grossman/erdoshp.html
is devoted to Erdős numbers. The next paragraph is copied from that source:
Most practicing mathematicians are familiar with the definition of one’s Erdős number ... Paul Erdős (1913−1996), the widely-traveled and incredibly prolific Hungarian mathematician of the highest caliber, wrote hundreds of mathematical research papers in many different areas, many in collaboration with others. His Erdős number is 0. Erdős’s co-authors have Erdős number 1. People other than Erdős who have written a joint paper with someone with Erdős number 1 but not with Erdős have Erdős number 2, and so on. If there is no chain of co-authorships connecting someone with Erdős, then that person’s Erdős number is said to be infinite.
Here are some data that I gathered from this web site, giving the number of people known to have each of the first several Erdős numbers (the site is updated periodically so the data will change from time to time):
Erdős number 0 1 2 3 4 5 1st kind 1 502 5713 26422 62136 66158 2nd kind 1 229 1969 8602 22668 36112
The row labelled “2nd kind” refers to a more stringent classification, described in the web site as follows:
The entire discussion so far has been based on linking two mathematicians if they have written a joint paper, whether or not other authors were involved. A purer definition of the collaboration graph (in fact, the one that Paul Erdős himself seemed to favor) would put an edge between two vertices if the mathematicians have a joint paper by themselves, with no other authors ... Let C' denote the collaboration graph under this more restrictive definition, and let us call the associated path lengths “Erdős numbers of the second kind” (and therefore call traditional Erdős numbers “Erdős numbers of the first kind” when we need to make a distinction).
Since those with Erdős number 2 got their numbers from writing with someone with Erdős number 1, we can get the average promiscuity number of the Erdős 1 authors by dividing their total into the total of Erdős 2 authors. The average number of co-authors for those with Erdős number 1 of the 1st kind is 11.4 and for those of the 2nd kind is a more selective 8.6. All sorts of people have Erdős numbers. You may be surprised to learn that Bill Gates has Erdős number 4, that Sir Francis Crick has Erdös number 7 and that his double helix collaborator Jim Watson has Erdős number 8.
This is the background you need in order to make sense of this message I received from Roger Hui about a year ago:
Subj: Erdos Number Date: 12/18/99 6:36:06 AM Pacific Standard Time From: RHui@Interlog.Com (Roger Hui) To: EEMcD@AOL.Com (E.E. McDonnell) CC: KEI@Interlog.Com (Kenneth E. Iverson) Apparently my Erdos number is 2, having co-authored a paper[2] with Shlomo Moran (during my grad school days in the early 1980's), who co-authored a paper with Erdos himself[3]... Neither you nor Ken are in [the] list [of people with Erdős numbers 0, 1, or 2]. Therefore,... both you and Ken have a Erdos number of 3 or less, having co-authored a paper with me.[4]
This was a surprise, since, although I have written a lot of semi-mathematical papers, I am not really a mathematician. Since there were three co-authors of the paper I wrote with Roger, I had an Erdős number 3 of the first kind, but not of the second kind. Similarly Shlomo Moran has an Erdős number 1 of the first kind, but not of the second, since there were three co-authors of his paper with Erdős.
Thus matters stood until a few months ago, when Roger sent me another message on the same subject:
Subj: Erdos Number
Date: 11/15/00 9:57:21 AM Pacific Standard Time
From: rhui@ADAYTUM-CAN.COM (Roger Hui)
To: EEMcD@AOL.Com (E.E. McDonnell)
According to http://www.acs.oakland.edu/~grossman/erdoshp.html Jeffrey Outlaw
Shallit wrote a joint paper[5] with Erdos in 1991. Since you wrote at least one
paper with Shallit ("Extending APL to Infinity")[6], that makes you an Erdos 2.
Since Erdős died in 1996, I had now reached the highest I can get on the Erdős graph. What is more, since my paper with Shallit had just the two of us as authors, and Shallit’s with Erdős had just the two of them, I now had Erdős number 2 of both the 1st and 2nd kind, and Shallit’s Erdős number 1 is also of the 1st and 2nd kind. Among my fellow number twos are such luminaries as Albert Einstein, G. H. Hardy and Donald Knuth. As I chat with my fellow 2’s, I appreciate the rather better class of thinkers they are, and wonder now that I was able at all to tolerate those arriviste 3’s with whom I rubbed shoulders. I know personally only one other number two, and that is my friend Charles Brenner, about whom you may have read in my letter in the Technical Correspondence of the January 2001 Vector, vol. 17, No. 3, p. 112. He is today best known as the forensic mathematician. See his very interesting website at www.dna-view.com. Charles was just sixteen in 1961 when he and his father, the mathematician Joel Lee Brenner, collaborated on a paper[7]. In 1987 the elder Brenner collaborated on a paper with Erdős[8], thereby promoting his son Charles’s Erdős number from infinite to 2. This raises a question. His father’s collaboration with Erdös involved a total of six co-authors, so his father’s Erdős number 1 is of the first kind only. Charles and his father were the only co-authors of their paper. How does this rank Charles? I’d say that the sins of the fathers should not be visited on the sons, so that Charles’s number 2 is, like mine, of the first and second kind. The promiscuity number of Joel Lee Brenner is 37; of Jeffrey Outlaw Shallit is 47; and of Shlomo Moran is 54, all three of them well above average.
I got to know Jeffrey Shallit when he was a young teenager with a gift for mathematics. He was a regular visitor to the IBM Philadelphia Scientific Centre when I worked there. When he went to college at Princeton University, he wrote his bachelor’s paper on the mathematical aspects of my design of the complex floor function[9]. Jeff came to work for me at I. P. Sharp Associates in Palo Alto in the summer of 1979, after graduating from Princeton and just before beginning graduate work at the University of California at Berkeley. It was then that he and I wrote our joint paper on APL and the infinite. I wrote the part on infinite values, and Jeff worked out the details of infinite-sized arrays, including a very nice way of displaying them using a diagonal transformation. Upon getting Roger Hui’s second message I emailed Jeffrey, who is now a full professor at Waterloo University in Ontario, Canada, saying how grateful I was to him for making this possible, but said that I didn’t feel worthy of the honour. He answered:
Subj: Re: thanks for raising my erdos number Date: 11/19/00 5:35:42 AM Pacific Standard Time From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit) To: Eemcd@aol.com Au contraire, it’s I who should be grateful to you. The paper that I wrote with Erdos was on expansions of the form 1/a - 1/(ab) + 1/(abc) - .... which I learned about from you in your APL article on “Spirals and Time”[10]. If I hadn't had the opportunity to learn from you in Philadelphia and later in Palo Alto, I would never have explored this interesting topic! Best, Jeff
This, unlike the essentially shallow glamour of my Erdős number, was something that I felt I could take legitimate pride in. The “Spirals and Time” article was a very early one of my articles. It gives me no little gratification when someone tells me they’ve enjoyed one. This message gave me an exceptionally large boost because Jeff had actually learned from it something useful to him professionally, and may even, as he suggests, have led to his involvement with Erdős. By the way, it had another satisfying repercussion, which I heard about from someone in Denmark who had shown my article to his fiancée. The article noted that the Gregorian calendar intercalation scheme had leap years in a 4 100-400 year cycle, but could be made exactly accurate if it were extended to a 4-100-400-3200-86400 cycle. The fiancée told Henry that on reaching the conclusion, where I noted that 86400 was also the number of seconds in a day, she “had an intellectual orgasm.”
Notice that successive terms in the Gregorian sequence are multiples of the preceding term. That is, 100 is 25*4 and 400 is 4*100. In the extension suggested in my article, 3200 is 8*400 and 86400 is 27*3200. The sequence of multipliers 4 25 4 for the Gregorian sequence and 4 25 4 8 27 can each be used to determine the average length of the year in each system. In the next section I’ll discuss how this may be done. For now, I’ll only point out that the current method of adding leap seconds to a year is sufficient to make it unnecessary to do any extensions to the Gregorian sequence, so discussions (like this) concerning changing or extending the current Gregorian scheme are purely academic.
Pierce and Engel Expansions
That brings us, at last, to the At Play With J part of this paper.
The expansion in Shallit’s message lies behind the design of the Gregorian calendar.
1/a - 1/(ab) + 1/(abc) - ....
In the case of the Gregorian calendar the values a, b, and c are 4, 25, and 4.
'a b c' =: 4 25 4
The product scan (*/\) of this list gives the cumulative products, in this case defining the intervals in years when to intercalate and when not: every fourth year but not every hundredth year unless it is also a four-hundredth year.
] m =: */\ a,b,c 4 100 400
We reciprocate these values:
] n =: % x: m 1r4 1r100 1r400
The alternating sum of this gives the part of a day p which, when added to 365, gives the average length of the year in calendar days in the Gregorian calendar.
] p =: -/ n 97r400
It also gives the number of leap years (97) in the cycle (400). One gets 97 this way:
400 % 4 100 400 100 4 1 -/100 4 1 97
The number of days in 400 years gives the length of the Gregorian cycle in days, which keeps repeating as the millennia roll on.
400 * 365 + 97r400 146097
Shallit’s curriculum vitae lists three papers, each bearing on the topic of Pierce expansions. These are not widely known, but they and the companion Engel expansions are the topics of the rest of this article. What are they? They are algorithms for converting a rational number into a series of integers, which, much like a continued fraction, give a way of representing a rational. The algorithm for Pierce expansions is described by Shallit in his paper on their metric theory as follows:
[Pierce expansion algorithm]: Given a real number x in (0, 1], this algorithm produces the sequence of a,,i,, such that x = {a,,1,,, a,,2,,, …}.
P1. [Initialize]. Set x,,0,, to x, set i to 1.
P2. [Iterate]. Set a,,i,, to floor (1/x,,i-1,,); set x,,i,, to 1 - a,,i,,x,,i-1,,.
P3. [All done?]. If x,,i,, = 0, stop.
Otherwise set i to i + 1 and return to P2.
Jeff points out that if x is a rational p/q, step P2 replaces p by q mod p, that this is less than p, and so eventually x will become 0, and the algorithm will terminate.
Several friends of mine asked if I could find out what Shallit’s joint paper with Erdős was about. It dealt with Pierce expansions, but also with something called Engel expansions. All I could find out about them was that they involved sums of reciprocals, as opposed to alternating sums, but I was unable to work out the details on my own, so asked Jeffrey for help. His reply:
From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit) To: Eemcd@aol.com Do you read Maple? Here is a maple program to compute the engel expansion of x up to the first n terms: engel := proc(x,n) local xp, z, k; xp := x; z := []; k := 0; while ((k <= n) and xp <> 0) do k := k+1; y := ceil(1/xp); z := [op(z),y]; xp := y*xp - 1; od; z; end; Basically you take ceiling of 1/x, and that's the next output. Then you multiply that by your current x and subtract 1.Then continue. Jeff
I’m not familiar with Maple, but I did manage to feel my way through this code. Having digested it, I concluded that the Pierce and Engel expansions were closely related. The Pierce list of integers implies an alternating sum, and the Engel list of integers implies a direct sum. This simplified my work in turning them into J, since one pattern would do for both.
To begin with, I changed Jeff’s approach in two important ways: first, to simplify termination control, I would work only with rational arguments; second, instead of having essentially two main variables, a continually modified rational and a continually lengthening list of integers, I would combine the two, beginning with a scalar rational, and successively modifying this in two ways: first appending a tail, and then modifying the head. The tail extension would be obtained by applying an integer function to the reciprocal of the current head value, and appending this; the floor (<.) for Pierce expansions, and the ceiling (>.) for Engel expansions. The head modification would be obtained by applying a subtracting function to the product of the head and the tail, and replacing the head with this; the one minus (-.) function for Pierce expansions, and the minus one (<:) function for Engel expansions. Similarly, in computing the inverses to these functions, obtaining the rational from a list of integers, the same pattern would be used, with minus (-) for Pierce contractions, and plus (+) for Engel contractions. This is summarized in the following table:
Pierce Engel tail <. >. head -. <: INVERSE - +
First I defined an adverb which would serve for both tail extensions:
BT =: 1 : '(, u @ % @ {. ) y'
where u stands for the appropriate integer function to be used in its place, floor or ceiling. It works by applying the appropriate integer function (u) to the reciprocal (%) of the head ({.), then appending it (,). Here’s how this works with each form of expansion:
<. BT 97r400 97r400 4 >. BT 97r400 97r400 5
Next comes an adverb for both head modifications:
BH =: 1 : '((0 } ~)u @ ({. * {:))y'
This replaces the head (0 } ~) with the appropriate subtracting function (u) applied to the product of the tail and the head ({. * {:). For example:
-. BH <. BT 97r400 3r100 4 <: BH >. BT 97r400 17r80 5
Next, these are combined in a conjunction that will allow a step function to be defined for both expansions:
BS =: 2 : '(u BH)@(v BT)y'
Here the u and v stand for the left and right function arguments to be used. For example:
-. BS <. 97r400 3r100 4 <: BS >. 97r400 17r80 5
A control structure is needed to allow the steps to be applied as often as necessary. This requires a sequence of two uses of the power conjunction; the first to control termination, with a right argument which gives the signum of the head (* @ {.). This will be one for any nonzero head value (I assume the argument is always positive), which allows the function to be applied; when the head eventually becomes zero, as it must since it is continually being reduced, the function will not be applied, and the result will be the same as the argument. The second use of the function power conjunction will cause the steps to be applied to the limit, that is, until two successive results are equal. The convention proposed by Iverson[11] is that positive infinity ( _ ) be used to describe application of a function to the limit. Nicely enough, this proposal was seconded by Shallit and me in our paper on infinities, and it is now part of J.
CS =: 1 : 'u (^:(* @ {.))^: _'
We can use CS with both steps:
(-. BS <.)CS 97r400 0 4 33 100 (<: BS >.)CS 97r400 0 5 5 16
These results show that the head is indeed zero. The zero is extraneous, so now we define two functions that yield just the needed Pierce and Engel expansion from a rational. We only have to behead ( }. ) the results we just got:
PR =: 3 : '}. @((-. BS <.)CS)y' ER =: 3 : '}. @((<: BS >.)CS)y' PR 97r400 4 33 100 ER 97r400 5 5 16
Let’s define the functions inverse to PR and ER and check whether each expansion contracts to 97r400. The method is essentially the same for both, so again we define an adverb that applies the appropriate subtraction function to insert (u /) between the result of reciprocating (%) and product scanning (* / \) our lists of integers:
RB =: 1 : 'u / * / \ % y'
and this makes the inverses easy to define:
RP =: - RB RE =: + RB
So now we use each of them:
RP PR 97r400 97r400 RE ER 97r400 97r400
So the expansions contract properly. We saw above that the list 4 25 4 contracted to 97r400, and now have verified that the list 4 33 100 does as well. In other words, both intercalation schemes will give an exact Gregorian year. The difference is that the cycle for the present Gregorian year is 400 years; for a 4 33 100 calendar the cycle is 13,200 years. For each, the resulting average year length is 365.2425 days.
By the way, the result 97r400 is given rather than the decimal equivalent 0.2425 because the results of PR and ER are both rationals, the same type as their arguments. See what happens if one just types in the numbers:
RP 4 33 100 0.2425 RE 5 5 16 0.2425
The functions PR and ER will work properly only when applied to rational arguments.
Engel Expansions and Gypsy Math
The very ancient document called the Rhind papyrus includes a table of all fractions of the form 2/n from 2/3 through 2/101, and for each gives a list of from two to four unit fractions that sum to it. For example,
2r3 = 1r2 + 1r6 2r61 = 1r40 + 1r244 + 1r488 + 1r610
The Engel expansions of rationals of the form 2/p for the first four odd primes give the same results as those listed in the Rhind papyrus:
BE =: [: % */\ (BE @ ER)"0 [ 2r3 2r5 2r7 2r11 1r2 1r6 1r3 1r15 1r4 1r28 1r6 1r66
This is not generally true, however. For example, the Rhind values for 2r21 are 1r14 and 1r42, whereas the rationals given by the Engel expansion are 1r11 and 1r231. However, I am now in a position to bring some unfinished business to a close, that I’ve left in abeyance since June, 1981. In my last column as Recreational APL editor for APL Quote Quad, in a section called “Gypsy Math” I wrote:
The Rhind papyrus ... shows, for each odd integer from 3 to 101, several integers whose reciprocals sum to 2÷⍵. For example, (2÷17)=+/÷9 153. Write a function F such that, for odd positive argument ⍵,
(2÷⍵)=+/F⍵ 2=⍴F⍵ ~⍵∊F⍵
Thus, F 17 ←→ 9 153.
I’m impressed by the fact that twenty years ago I knew how to give unit fraction results for Rhind fractions such as 2r17 without knowing anything about Engel expansions. However, the Engel expansion is completely general, and will handle any positive rational less than 1. Our Egyptian predecessors probably used a simpler formula which we would write in J notation as:
Egypt =: [: */\ (,~ -:@>:) Egypt"0 [ 3 5 7 11 2 6 3 15 4 28 6 66
Postscript
Erdős, by-the-bye, has a Bacon number of 4. Schechter explains how this came about in his book on Erdős:
A mathematician and sometime actor named Gene Patterson appeared briefly in the 1993 documentary about Erdős, N is a Number. Patterson also had a role in Box of Moonlight with John Turturro, who was in The Color of Money with Tom Cruise, who appeared in A Few Good Men with Kevin Bacon.
And Jeffrey Shallit is the proud possessor, in addition to his Erdős number of 1, of an Elvis number of 3. If you can’t guess what this is, you can read all about it at his web site:
http://www.math.uwaterlooo.ca/~shallit
References
[1] Schechter, Bruce, My Brain Is Open, The Mathematical Journeys Of Paul Erdős. Simon & Schuster, New York, (1998).
[2] Ibarra, O., Moran, S., Hui, R. K. W., A Generalization of the Fast LUP Matrix Decomposition Algorithm and Applications. Journal of Algorithms 3, (1982), 45-56.
[3] Erdős, P., Linial, N., Moran, S., Extremal Problems on permutations under cyclic equivalence, Discrete Math. 64, (1987), 1-11.
[4] Hui, R. K. W., Iverson, K. E., McDonnell, E. E., Whitney, A. T., “APL\?”. APL90 Conf. Proc., 192-200.
[5] Erdős, P., Shallit, J., New bounds on the length of finite Pierce and Engel series. Séminaire de Théorie des Nombres de Bordeaux 3, (1991), 43-53.
[6] McDonnell, E. E., Shallit, J., Extending APL to Infinity. APL80, Noordwijkerhout, 123-132.
[7] Brenner, C. H., Brenner, J. L., The popularity of small integers as primitive roots. Numer. Math. 4, (1962), 336-342.
[8] Brenner, J. L., Beasley, L. P., Erdős, P., Szalay, M., Williamson, A. G., Generation of alternating groups by pairs of conjugates. Period. Math. Hungar. 18, (1987), 259-269.
[9] McDonnell, E. E., Complex Floor. APL Congress 73, Copenhagen.
[10] McDonnell, E. E., Spirals & Time. APL Quote Quad 7, 4, (Winter 1977), 20-22.
[11] Iverson, K. E., Operators and functions, RC 7091, IBM Corp., Yorktown Heights, NY, (1978).