I bring my apologies for a Russian text quoted below — I promise to try to find an English translation, but so far I failed in my quest. This fable by Roerich came to my mind when I started to think about David Pierce’s induction/recursion opposition in terms of practicalities of “black box” computing in a very big residue ring with modulus of unknown prime decomposition (and this is a VERY practical issue since it is a setup for the RSA cryptosystem). As David Pierce observed, a standard recursion scheme for exponentiation is inconsistent on finite rings like .

What is a black box calculation? I’ll give you a toy example concerned with the RSA setup. Assume that you are given a calculator which has only buttons for digits, two operations , and return . To make it worse, the calculator returns the answers modulo for a very large — and unknown to you — number which is a product of two very large primes which are also unknown to you. On the bright side, you can save any number of intermediate results in the memory and re-use them. To guide yourself through the labyrinth of modular arithmetic, you can do auxiliary calculations with a pencil on paper.

I make a (semi-mathematical) claim that, playing with such a calculator for the rest of your life, you will never notice inconsistency in the recursive definition of exponentiation. Also, if has 100 digits, the calculator will be quite usable for many everyday needs.

My argument is based on a semi-philosophical premise that calculations (no matter how clever they are) with unknown modulus are in effect random manipulations with buttons with known .

But to find a random concrete instance of inconsistency of exponentiation in , that is, natural numbers and such that means getting at least a 1/4 chance to factorise and thus break the RSA scheme based on modulus : this is the probability with which is even and

.

Notice that  we can compute by a square-and-multiply method. Now let us repeat a trick from Simmons’ attack on (a lousy implementation of) RSA:

hence ,

and, computing (with a pencil on paper, using Euclid’s algorithm) the greatest common divisors of and , we easily find and — which exactly means to break the scheme.

I am pleased to say that David Corfield’s quest for instances of when the infinite is simpler is answered in this simple example in a stronger form: sometimes, infinite is not just simpler, it is safer.

What follows is Nicholas Roerich’s fable The Border of Kingdom:

Н.К. Рерих

ГРАНИЦА ЦАРСТВА

В Индии было.

Родился у царя сын. Все сильные волшебницы, как знаете, принесли царевичу свои лучшие дары. Самая добрая волшебница сказала заклятие:

Не увидит царевич границ своего царства.

Все думали, что предсказано царство, границами безмерное.

Но вырос царевич славным и мудрым, а царство его не увеличилось.

Стал царствовать царевич, но не водил войско отодвинуть соседей.

Когда же хотел он осмотреть границу владений, всякий раз туман покрывал граничные горы.

В волнах облачных устилались новые дали. Клубились облака высокими грядами.

Всякий раз тогда возвращался царь силою полный, в земных делах мудрый решением.

Вот три ненавистника старые зашептали:

Мы устрашаемся. Наш царь полон странною силою. У царя нечеловеческий разум. Может быть, течению земных сил этот разум противен. Не должен быть человек выше человеческого.

Мы премудростью отличенные, мы знаем пределы. Мы знаем очарования.

Прекратим волшебные чары. Пусть увидит царь границу свою. Пусть поникнет разум его. И ограничится мудрость его в хороших пределах. Пусть будет он с нами.

Три ненавистника, три старые повели царя на высокую гору. Только перед вечером достигли вершины, и там все трое сказали заклятие. Заклятие о том, как прекратить силу:

Бог пределов человеческих!

Ты измеряешь ум. Ты наполняешь реку разума земным течением.

На черепахе, драконе, змее поплыву. Свое узнаю. На единороге, барсе, слоне поплыву. Свое узнаю. На листе дерева, на листе травы, на цветке лотоса поплыву. Свое узнаю.

Ты откроешь мой берег! Ты укажешь ограничение! Каждый знает, и ты знаешь! Никто больше. Ты больше. Чары сними.

Как сказали заклятие ненавистники, так сразу алою цепью загорелись вершины граничных гор.

Отвратили лицо ненавистники. Поклонились.

Вот, царь, граница твоя.

Но летела уже от богини доброго земного странствия лучшая из волшебниц.

Не успел царь взглянуть, как над вершинами воздвигся нежданный пурпуровый град, за ним устлалась туманом еще невиданная земля.

Полетело над градом огневое воинство. Заиграли знаки самые премудрые.

Не вижу границы моей, — сказал царь. Возвратился царь духом возвеличенный. Он наполнил землю свою решениями самыми мудрыми.

1910

The quotations about the universe as an infinite sphere remind me of another kind of sphere that is beyond our usual powers of imagination.
In the one-hundred cantos of the Divine Comedy, Dante travels from the central point of the earth out into the heavens. He passes through the spheres of

1. the moon,
2. Mercury,
3. Venus,
4. the sun,
5. Mars,
6. Jupiter,
7. Saturn,
8. the fixed stars,
9. the Primum Mobile.

In this ninth sphere, he sees another point, surrounded by circles or spheres. These spheres are angels, named from inside to outside:

1. Seraphim,
2. Cherubim,
3. Thrones,
4. Dominions,
5. Virtues,
6. Powers,
7. Principalities,
8. Archangels,
9. Angels.

These are named in Canto XXVIII of the Paradiso, where Dante reports (text from the Princeton Dante Project):

16 I saw a point that flashed a beam of light
17 so sharp the eye on which it burns
18 must close against its piercing brightness.
19 The star that, seen from here below, seems smallest
20 would seem a moon if put beside it,
21 as when one star is set beside another.
22 As near, perhaps, as a halo seems to be
23 when it encircles the light that colors it,
24 where the vapor that forms it is most dense,
25 there whirled about that point a ring of fire
26 so quick it would have easily outsped
27 the swiftest sphere circling the universe.
28 This point was encircled by another ring,
29 and that by the third, the third by the fourth,
30 the fourth by the fifth, and the fifth by the sixth.
31 Higher there followed the seventh, now spread so wide
32 that the messenger of Juno, in full circle,
33 would be unable to contain its size.
34 And so, too, the eighth and ninth,
35 each one revolving with diminished speed
36 the farther it was wheeling from the first.
37 And that one least removed from the blazing point of light
38 possessed the clearest flame, because, I think,
39 it was the one that is the most intruthed by it.
40 My lady, who saw me in grave doubt
41 yet eager to know and comprehend, said:
42 ‘From that point depend the heavens and all nature.
43 ‘Observe that circle nearest it,
44 and understand its motion is so swift
45 because it is spurred on by flaming love.’
46 And I to her: ‘If the universe were arranged
47 in the order I see here among these wheels
48 I would be content with what you’ve set before me.
49 ‘However, in the world of sense we see
50 the farther from the center they revolve
51 the more divinity is in their orbits.

Beatrice then explains that the innermost rings of angels correspond to the outermost heavenly spheres: so n corresponds to 10-n in the lists above.

In a lecture given in Ankara a while back, Piergiorgio Odifreddi suggested (as I recall) that the two spheres or rather balls—of the heavens, and of the angels—should be considered as identified along the 2-spheres that are their boundaries, so that a 3-sphere is obtained, with Lucifer and God as antipodal points.
I note Dante’s description of the latter Point in lines 11–12 of Canto XXX:

1 About six thousand miles away from here
2 the sixth hour burns and even now this world
3 inclines its shadow almost to a level bed,
4 when, deep in intervening air, above us,
5 begins such change that here and there,
6 at our depth, a star is lost to sight.
7 And, as that brightest handmaid of the sun advances,
8 the sky extinguishes its lights,
9 even the most beautiful, one by one.
10 Not otherwise the victory that revels
11 in eternal joy around the point that overcame me
12 and seems enclosed by that which it encloses
13 little by little faded from my sight,
14 so that, compelled by seeing nothing and by love,
15 I turned my eyes to gaze on Beatrice.

As a symbol for a world that cannot be fully comprehended, the three-dimensional surface of a four-dimensional body may serve as well as something infinite in extent.

A paper by  Andrei Rodin, arXiv:math/0509596 [pdf]. Appears to be relevant to our project.

A collection of quotes:

Hermes Trismegistus, “thrice-great Hermes” “God is an infinite sphere, the center of which is everywhere, the circumference nowhere.” Book of the 24 Philosophers.

Alain of Lille “God is an intelligible sphere, whose center is everywhere, and whose circumference is nowhere.”

Pascal: “The whole visible world is only an imperceptible atom in the ample bosom of nature. No idea approaches it. We may enlarge our conceptions beyond all imaginable space; we only produce atoms in comparison with the reality of things. It is an infinite sphere, the center of which is everywhere, the circumference nowhere. In short, it is the greatest sensible mark of the almighty power of God that imagination loses itself in that thought.”

Also apparently, “Let him contemplate all nature in its awful and finished magnificence; let him observe that splendid luminary, set forth as an eternal lamp to enlighten the universe; let him view the earth as a mere speck within the vast circuit described by that luminary; let him think with amazement, that this vast circuit itself is only a minute point , compared with that formed by the revolutions of the stars…All that we see in of the creation, is but an almost imperceptible streak in the vast expanse of the universe. No idea can approximate its immense extent…This is an infinite sphere, the center of which is everywhere, but its circumference nowhere. In short, it is one of the greatest sensible evidences of the almightiness of God, that our imagination is overwhelmed by these reflections.”

In “Pascal’s Sphere,” Borges’ narrator lists dozens of variations of a single image, a circle that stands alternately single image, a circle that stands alternately for God, nature, the universe, infinity. Culminating his enumeration is Pascal’s image for the universe: “an infinite sphere, the center of which is everywhere, the circumference nowhere.” Indeed, Borges himself adds to the list in his story “The Library of Babel,” the Library is described as “a sphere whose exact center is anyone of its hexagons and whose circumference is inaccessible” (Labyrinths 52).

According to Borges, Pascal hated “the universe. He was sorry the firmament could not speak; he compared our lives to those of shipwrecked men on a desert island … and he expressed his fillings [saying nature] is an infinite sphere, the center of which is everywhere, the circumference nowhere.”

[Seems to me from the quotations, especially the second, that Borges had Pascal wrong.--D.C.]

I have been invited to comment here on the distinction between proof by induction and definition by recursion. These have been confused since Guiseppe Peano published (in 1889) what came to be called the Peano Axioms. It might appear that both induction and recursion involve infinite sets; but only recursion necessarily does.

Writing before Peano, Richard Dedekind (1887) was clear about the distinction. He defined a simply infinite system as a system (i.e. set) with a base-element and a transformation (i.e. function) into itself such that:

1. the base-element is not the transform (i.e. image under the transformation) of any element;
2. distinct elements have distinct transforms (in Dedekind’s terminology, the transformation is similar);
3. proof by induction is possible: a subset containing the base-element and closed under the transformation is the whole set.

Peano also wrote down these conditions, but in a new logical symbolism, and they came to be known as the Peano axioms. But unlike Dedekind, Peano apparently thought that these axioms immediately allowed the definition of addition. Indeed, let the base-element be 1, and the transformationbe φ. We define n+1 as φ(n) and, assuming n+m has been defined, we define n+φ(m) as φ(n+m).

This is a recursive definition. Is it justified? If so, which of the three axioms are required, and how?

The definition of addition can be justified by induction alone. Likewise, multiplication. Edmund Landau published the proof (due to Kalmár) in 1929. But Landau did not dwell on the sufficiency of induction, or on what Dedekind had observed: a system that admits proof by induction may be finite, so that not all recursive definitions work.

Finite rings provide examples. In the ring of integers modulo p, or Z/(p), let 0 be taken as the base-element, and let the transformation be addition of the generator 1. No proper subset of the group contains 0 and is closed under the transformation: proof by induction is possible here. From this, addition and multiplication can be recovered.

However, exponentiation as a binary operation cannot be defined on this ring. Superficially, the attempted definition parallels those of addition and multiplication: n⁰ = 1, and if n^m has been defined, then n^m+1 = n^m·n. But this definition fails. Indeed, assuming p is prime and n is not 0, by Fermat’s Theorem we must have n^p-1 = 1; but then n = n^p = n⁰ = 1, which is absurd unless p is 2.

Fermat’s Theorem is that we have exponentiation as a function from Z/(p) × Z/(p-1) into Z/(p); but to prove this, we need more than that the ring Z/(p) and the group Z/(p-1) admit proof by induction.

Though distinguishing between definition and proof, Dedekind spoke of definition by induction rather than definition by recursion. If Ω is a set with distinguished element ω and transformation θ into itself, then, from a simply infinite system as above, into Ω, there is a unique transformation ψ such that ψ(1) = ω and ψφ = θψ. For Dedekind, this is a theorem about simply infinite systems.

According to Saunders Mac Lane in Mathematics, form and function (1986), Lawvere first “made explicit” that this Recursion Theorem implies the three Peano Axioms listed above. The equivalence of the Theorem and the Axioms is also discussed in the first edition of Mac Lane and Birkhoff’s Algebra (1967). Nonetheless, although that text introduces the natural numbers (starting with 0) as satisfying the Peano axioms, the writers then immediately use the natural numbers to index iterations of an operation f on a set: f ⁰ is the identity, and f ⁿ⁺¹ is f f ⁿ. This is a recursive definition, so one might expect it to be justified to the reader by means of the Recursion Theorem. But this theorem is stated about 40 pages later, as the Peano–Lawvere Axiom, from which the Peano Axioms are shown to follow; the converse is only to be found in “many [other] texts on foundations”.

Indeed, Stoll’s Set theory and logic (1963) is one such text. However, other texts continue to give the impression that “definition by induction” is permitted by the possibility of proof by induction. Other confusions are found in elementary texts, such as the suggestion that “strong induction” or the “well-ordering principle” are equivalent to (ordinary) induction. To me, it is important to get these things straight, if only because the attentive student might be confused (as I once was). Landau confessed to having been mistaken about what was possible with induction. Who has noted since how it is possible to go astray?

References:

1. Richard Dedekind, Essays on the theory of numbers (Dover, 1963)
2. Edmund Landau, Foundations of analysis (Chelsea, 1966)
3. Saunders Mac Lane, Mathematics, form and function (Springer, 1986)
4. Saunders Mac Lane and Garrett Birkhoff, Algebra (Macmillan, 1967)
5. Robert R. Stoll, Set theory and logic (Dover, 1979)
6. Jean van Heijenoort, editor, From Frege to Gödel, a source book in mathematical logic 1879–1931 (Harvard, 1967)

I’d like to open a discussion of cases in mathematics where one resorts to the infinite just because things work out simpler there. A classic case of this is the free ring, , the integers. Any ring is somehow more ‘confused’, a condition has been applied to identify elements.

Now, consider the spaces , the set of straight lines through the origin in , or projective real -space. Each is covered by its corresponding -sphere. The fibre over a point has two points — forming a bundle. But none is quite as simple as it could be. We need to embed each in the next higher space and take a suitable limit to form . The bundle over it with total space the infinite dimensional sphere is ‘universal’ among all -bundles.

So, often the infinite shows up in some universal object. John Baez uses the term walking such and suches to cover many of these.

Attempts to look at the concept of infinity in wider culturological aspects could be a dangerous occupation. A Google image search via keyword “eternity” leads to results which have to be seen to be believed. Eternity is the Kingdom of Kitsch. Why? And what is kitsch? Google Scholar helped me identify an old paper by Abraham Kaplan The Aesthetics of the Popular Arts, The Journal of Aesthetics and Art Criticism, Vol. 24, No. 3. (Spring, 1966), pp. 351-364 (available at JSTOR, if you have access). The opening of the paper is very promising:

Most aestheticians, I think, are Platonists at least in this respect: they analyze the realm of value by looking chiefly to its ideal embodiments. Disvalues are left to implicit negation: if artistic excellence is this, what is not this specifies the inferior product. The vulgar and tasteless, the derivative and academic, brummagem, borax, and kitch-such as these are left to purely tacit and inferential analysis. Are there, after all, Ideas of hair, mud, dirt? The time will come, says Parmenides, when philosophy will not despise even the meanest things, even those of which the mention may provoke a smile.

(BTW, what is “bad mathematics”?) Unfortunately, Kaplan does not give a satisfactory answer to my question. My quest continues, and I would appreciate help from my readers. To emphasise the urgency of the matter, I place here two random images from Google, one comes from search for “eternity”, another for “infinity”:

Eternity

Why? What are deeper reasons for infinity and eternity being appropriated by the most horrendous kitsch?

Edge still has not revealed its New Year’s Eve Annual Question 2008, but, due to a leak to The Independent, I know that it is i wonderful:

What have you changed your mind about? Why?

Indeed, what have you changed your mind about in 2007?

Something we won’t be ignoring is relevant discussion on other blogs, and here’s some of that going on at Richard Borcherds’ blog. They’re wondering why so little of the power of set theory gets used in the vast majority of mathematics.