Stepnumbers: Foreword to the First Edition

Foreword To The First Edition Of 1998

This is a personal note explaining the nature of this publication, outlining the larger design that has animated its writing. I took early retirement as professor of mathematics and subsequently decided that I wanted to dedicate myself to the cause of mathematics education of the blind. I am sighted and have, as most of my colleagues, had virtually no contact during my teaching career with sightless students. But the abstract nature of my discipline has often made me think about the problem how best to educate talented blind children in mathematics and information technology.

It has always been clear to me that the curriculum and the didactic aims of such a program would have to be radically different from its conventional counterpart. It must not be a mere adaptation of traditional material to the special needs of the blind. It ought to contain material the sightless can absorb and manipulate better than the sighted. I also believe that the problem must be approached not only with sensitivity but also with a great deal of humility. This is a case par excellence where the teacher must learn from the student. The sightless are less prone to succumb to what I call “the gravitation of atavistic visual imagery”, the greatest obstacle in the way of the single-minded pursuit of abstraction that permeates all mathematical enterprise. Some of the greatest cultivators of mathematics were blind (the names of Euler, Lefschetz, and Pontryagin readily come to mind) doing inspired work even in the field of geometry where eyesight had been thought to be a paramount prerequisite. It is a great pity that they did not leave reminiscences to posterity on the question whether or how their handicap may have helped them to sharpen their faculty of abstract thinking. Be that as it may, we must deem it possible that the sightless, given the nature of their handicap, may have more than an equal chance to develop their mathematical abilities to the fullest extent, granted ideal conditions. A lot of talent may have been wasted in giving blind children skills in basket weaving and massaging, rather than mathematics.

Early in my academic career I became fascinated with what Nicolas Bourbaki has in the first book of his series Elements of Mathematics, first published in 1937, called quotient sets. In particular I was interested in the ‘weak’ duality between the theory of subsets and the theory of quotient sets. (Duality is discussed in the projected Volume II.) In spite of the great popularity of Bourbaki, the subject has failed to stimulate interest in the mathematical community, nor has the term ‘quotient set’ gained currency since its introduction well over half-a-century ago. Equivalent but misleading terms such as "partitions" preferred by set theorists and "block design" preferred by combinatorists still dominate the literature. Unified notation for the number of quotient sets and quotient set types is still wanting. Deplorable as the lack of uniform terminology and symbolism may be, even more serious is the fact that the theory of quotient set is the Cinderella of mathematics, especially of mathematics education. If textbooks and treatises mention it at all, the effort hardly goes beyond paying lip service. A comprehensive bibliography of the subject is still waiting to be compiled. Its classification shows great inconsistency, even confusion. Authors, among others, Gian Carlo Rota, switch allegiance between competing schools with different terminologies, symbolism, and conceptual outlook, making it difficult for the researcher to follow their output. Editors, referees, and reviewers of learned journals are often ignorant about the central importance of the subject.

They tend to treat submissions trying to rectify the situation in an offhand fashion.

Yet a quotient set is one of the great unifying ideas in all mathematics. It cuts through various disciplines as no imposed structure on the underlying set is assumed. Quotient sets, like subsets, are natural in the sense of not being subject to prior choices such as structures (as do most vii mathematical concepts in the vogue today, causing fragmentation of the discipline). And, above all, set theory is not complete without an explicit recognition of a weak duality between the lattice of subsets and the lattice of quotient sets. We have every reason to believe that, sooner or later, information technology will embrace the concept of quotient sets as a vehicle towards improved information efficiency.

In addition, I find it hard to escape the conclusion that the very concept of a quotient set may furnish the missing link in the mathematics education of the blind. Louis Braille (1809-1852) used the non-trivial subsets of the six-cell MM as raw material for codes out of which he fashioned his system of reading for the blind. Nobody today would dispute the proposition that the adoption of the Braille code was one of the great success stories of the 19th century. Perhaps the abstract nature of the concept of subsets, de-emphasizing as it does the visual aspects of the code, has something to do with it. At any rate, with the development of science there was soon need for more codes to accommodate an increasing list of essential symbols. And it was here that a historical mistake was made by the experts. Encouraged by the success of Braille, they became his epigoni. They slavishly copied a successful idea, but without the inspiration animating the original. The experts replaced the six-cell with an eight-cell, thus increasing the inventory of available codes from 26 − 1 = 63 to 28 – 1 = 255. They failed to realize, however, that the eight-cell covers a larger surface area.

Therefore the blind reader will have to track codes vertically as well where previously horizontal tracking sufficed, with the result that the reading process would be slowed down considerably. The failure of the eight-cell system gave me the impetus to start advocating the use of quotient sets for the purpose of enlarging the inventory of codes. The original six-cell of Braille has 203 quotient sets in addition to the 63 non-trivial subsets already in use. The combined number 203 + 63 = 266 exceeds 255, the size of the inventory of eight-cell codes. Further augmentation of the system is still possible if we include the quotient sets of the three-, four-, and five-cells. Most importantly, none of the new proposed codes has a larger surface area than the original six-cell of Braille, so that there is no reason to believe that the efficiency of an experienced reader would be dulled on account of the increase in the size of the inventory. Horizontal tracking is all that is needed, as before. No vertical tracking — no handicap.

There is a larger issue here than that of parochial rivalries between the various competing systems to augment the original Braille. Quotient sets furnish the ideal tool for the mathematical education of the blind. They are completely non-visual and, for all we know, a sightless person may have a better chance to grasp their true nature and to manipulate them than a sighted one. Counting quotient sets is a rich source of meaningful exercises that could fill many hours devoted to homework. Quotient sets are also important for the promise they hold out to increase information efficiency when used in coding. The entire corpus of 10,000 Chinese telegraphic codes can be rendered as quotient sets of the nine-cell, with more than 11,000 quotient sets left over and available for other purposes.

While working on the problem to include the quotient sets of the six-cell in order to augment

Braille, I stumbled over a novel number system: that of the stepnumbers. These numbers can deputize for quotient sets in exactly the same way as binary numbers do for subsets. Stepnumbers can be used not only to count the number of quotient sets, but also to calculate their superimposition and amalgamation (lattice operations, dual concepts of the union and intersection of subsets under weak duality). viii

Since the stepnumber system calls for an inventory of infinitely many digits, the problem has arisen how to furnish it in the most efficient way. In searching for a solution I discovered new digits, the so-called rainbow digits obtained by coloring the decimal digits with the standard colors of the rainbow spectrum in the following order: black red brown orange yellow green viridia n blue indigo violet

█

Further colors are derived from the standard ones by passing to their various shades. The first b21 = 474,869,816,156,751 stepnumbers involving black and red decimal digits only will admit the writing of stepnumber expansions of very large numbers already. Apparently, there is no practical need to go to the brown color and beyond, at least for the time being.

The rainbow digits have a mnemotechnical significance: in no way do they tax human memory. Large stepnumbers can be coded in rainbow digits with the same ease as smaller ones can in decimal digits. And they can also be deciphered with the same ease.

Out of these discoveries sprang the work Stepnumbers the reader now beholds. I have chosen an unconventional way to publish it, as part of a new series of occasional papers sponsored by the Mathematics for the Blind Foundation. Contributions from authors to this series are hereby invited.

The Foundation's main purpose is talent-education in the field of mathematics and information technology, aimed at directly benefitting the blind. It has plans to set up a comprehensive library of mathematical texts, monographs, and treatises, making it accessible for the blind world-wide through the internet. Other plans call for the establishment of an international school for talent-education of the blind in the field of mathematics and information technology. The school will probably be located in Budapest, Hungary, the home of my alma mater the Loránt

Eötvös University, where the Department of Information Technology is already doing praiseworthy work in this area.

December 8, 1998.

Antal E. Fekete

Memorial University of Newfoundland

Acknowledgements

I wish to express my gratitude to my friend and colleague, Siegfried Thomeier, for drawing my attention to a 1697 letter of Leibniz and to the design of the medallion therein, now adorning this publication as a frontispiece, as well as for many hours of valuable discussion on the subject matter. I am indebted to Donald E. Knuth for the explicit formula for the factorial coefficients (Chapter 3). I also thank him for telling me that the ‘politically correct’ name for converting stepnumbers into decimals is “ranking algorithm for set partitions”. Armed with this knowledge I have been able to track down some pioneering papers on the subject by George Hutchinson [6] and by S. G. Williamson [7] published in 1976. ix

Foreword To The Second Edition

The binary number system was invented in 1697 by Gottfried Wilhelm Leibniz (1646-1716) who gave expression to his jubilation with his cry eureka: “One has created everything from nothing”, engraved on a medallion of his own design (see Frontispiece).

I invented the stepnumber system 300 years later, in 1997. The reader may forgive my own cry eureka: “Substance perishes, but form lives forever!”. It suggests that the significance of the stepnumber system eclipses that of the binary that epitomizes substance as opposed to form, the latter being the epitomy of stepnumbers.

The significance of the binary number system was not really appreciated before the computer revolution. By this metric, the significance of the stepnumber system may not be recognized for a couple of centuries. The binary system, “the mother tongue of computing”, is far too entrenched. It may appear that the computer revolution has made the enthronement of the binary number system all but irrevocable.

Yet we ought to guard ourselves against making hasty predictions about the future. The binary number system owes its adaptability to three facts from physics. The first is that there are two kinds of magnetic charge: North and South. It is this fact that makes erasable magnetic disks and tapes suitable for recording information in binary code for storage. The second is that there are two possible states of a capacitor: uncharged and charged. It is this fact that makes transmitting information in binary code easy. The third is that there are two possible states in regard to an electric circuit: open and closed. It is this fact that makes retrieving information in binary code possible.

However, with the advent of semiconductors, erasable etching of information on a laser disk, and quantum computers — in particular, the possibility of using the orbit structure of electrons in the atom for coding purposes — one can no longer be certain about the permanent hegemony of a blackand-white binary system. The full spectrum of colors is threatening to displace it. With further advances of technology codes using an unspecified number of digits are conceivable.

The binary system may indeed become obsolete for most applications involving extremely large numbers which are not yet but may well become the staple of science in the future. Clearly, it is wasteful, inefficient, and uneconomic. We have to find the optimal number system employing more than two digits. It may appear that cultivators of mathematics have been tardy in preparing the stage for the next phase of the computer revolution. We don't seem to have a clear idea how to go about increasing information efficiency and economy by increasing the base of a number system, or where to stop. Can we admit infinitely many digits without losing the advantage of positional value, which is the mainstay of the economy and efficiency of a number system? Clearly, a new idea is needed before we can make further headway with the problem of improving information efficiency by graduating to a more versatile number system.

The stepnumber system is the dual of the binary number system. It furnishes the missing number system at the far-end of the spectrum: the number system with base n, as n → ∞. The stepnumber system compares to the binary as color TV does to the black-and-white. We may assume x that in the quantum computer of the future the fundamental unit of information will not be the bit of the binary system: the binary digits with their rigidly fixed positional value. It will probably be the new bit of the stepnumber system: the rainbow digits

0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789… with their variable positional value.

The binary and the stepnumber systems are the only natural number systems in the sense that neither does depend on arbitrary choices such as that of the base number n. In fact, there exist natural isomorphisms, one peculiar to each. The binary number system is naturally isomorphic to the graded lattice of finite subsets; the stepnumber system to the graded lattice of finite quotient sets.

These natural isomorphisms reveal that both the binary numbers and the stepnumbers are in fact characteristic functions. Binary numbers are characteristic functions of finite subsets; stepnumbers are characteristic functions of finite quotient sets. This fact further reveals that the two number systems have a common genesis. It also indicates that the stepnumber system is a genuine piece of mathematics waiting to be discovered, even though the waiting has taken 300 years after the original discovery of Leibniz. In the opinion of the author quotient sets are still sadly neglected in mathematical education and in the epistemology of mathematics. This is perhaps the real reason for the unusual delay of three centuries between the two discoveries.

Digital information technology is usually thought of as a great improvement over the analog.

Yet rumors of the demise of the latter are ‘grossly exaggerated’. Nature still uses form, rather than substance, for encoding purposes when it comes to genetics. If it is true that the substance making up the human body is changed every seven years through metabolism, then our brain should not be thought of as an aggregate of molecules, but an arrangement of aggregates. In fact quotient sets may be the appropriate tool to investigate the structure and operation of the mind. What we are, our memory, our emotions, our psyche, are not encoded through the agency of substance. They are encoded through the agency of form. Substance is incidental and transient, and it can be substituted without changing the information content. More permanent than substance is form. To the extent it is, analog information technology will never be obsolete. Quotient sets along with stepnumbers will likely find a role in encoding and carrying analog messages efficiently, just as subsets along with binary numbers are already carriers of digital messages.

The same way as the lattice of subsets is weak dual to the lattice of quotient sets in the sense that every property of the latter has a dual property in the former (but not the other way round), the binary number system is weak dual to the stepnumber system.

The first edition of this work, published ten years ago, was intended as a textbook for pupils who were born blind. Although the project to test this material in a classroom setting was abandoned early on for lack of interest on the part of the educational establishment for the blind, I left the didactic features in the second edition of the book unchanged. This explains the copious in-text worked examples and end-of-chapter exercises which may be of little interest to readers who want to get acquainted with stepnumbers as quickly as possible. xi

I have relegated a large number of heuristic proofs (also known as ‘behold-type proofs’ or, sometimes, ‘proof without words’) to the Exercises, even though they would have deserved a more prominent place in the main text. Among these are the generalizations of the Little Theorem of

Fermat, Wilson’s Formula, as well as Touchard’s Congruence. My search of the literature has failed to turn up evidence that these generalizations are already in the public domain. I state them here as results that are presumably new:

The Generalized Little Theorem of Fermat a p −1 ≡ 1 (mod p), p prime, p does not divide a n

The Generalized Wilson’s Formula

⎡ p n +1 + k ⎤ n+1

⎢ n

⎥ + 1 ≡ 0 (mod p), p prime, k = 0, 1, 2,…, p – 1

⎣ p +k ⎦

⎡n ⎤ where ⎢ ⎥ denotes the kth entry in the nth of the Pascal triangle for the Stirling numbers of the first ⎣k ⎦ kind (the number of k-orbit permutations of n).

The Generalized Touchard’s Conrguence bpn + k ≡ bk + bpn −1 + k (mod p) and its consequence bpn + k ≡ nbk + bk +1 (mod p), p prime, k ≥ 0 arbitrary where n = 1, 2, 3, … The classical results are obtained as a special case for n = 1.

The proofs are heuristic. They involve counting non-zero entries in the rows of Sierpinski’s triangle (mod p) for the binomial coefficients, and for the Stirling numbers of the first and second kind. I leave the task of fully exploiting this method to a younger generation of mathematicians along with my strong suggestion that Sierpinski’s triangles have not yielded all their secrets yet.

By preserving the original flavor of the book I hope to appeal to the taste of both the educators and the philosophically oriented computer scientists.

Dear critic, lower your gun; the book is not for you.

December 8, 2009.