Reviews Chandler Davis*

TEX

Six Months Later

by William Abikoff In Vol. 8, No. 3 of the Intelligencer, I wrote an introduction/review of some microcomputer implementations of TEX, the technical word processor and typesetter designed by Donald Knuth. In this short update, I hope to correct one grievous error, bring some n e w information to light, and suggest a system, using TEX, for the distribution of preprints.

1. An apology I was u n d e r the misconception, corrected by Dick Palais, that work done under National Science Foundation grant or contract reverts to the public domain. The latter term means that the discoveries or products are not copyrighted or patented and may be used by anyone without paying further fee. While this seems to be a perfectly reasonable policy concerning the o u t p u t of a process paid for by my tax dollars, it simply isn't the case. The only standard requirement on the use of results obtained under U.S. government contract or grant is the government can use the end products without further cost. So I am paying through my taxes a major portion of the cost of people doing private business. I hope the reader will indulge me in my lack of enthusiasm for this policy. N o w to my apology. Don Knuth not only placed TEX in the public domain, he contributes the royalties on his books on computers and typesetting to the TEX Users' Group. This is an act of great generosity which I should have acknowledged. However, my lack of understanding of the policies concerning f u n d e d research led me to conclude that TEX lay in the public domain because of government policy. I offer my sincerest apologies to Professor Knuth. * C o l u m n e d i t o r ' s a d d r e s s : M a t h e m a t i c s D e p a r t m e n t , U n i v e r s i t y of Toronto, O n t a r i o M5S, 1A1, C a n a d a

66

2. A TEX update In my previous review, I compared a prerelease version of MicroTEX to a six-month-old version of PCTEX. I also indicated that I expected that the n e w releases of both would probably be available w h e n the article appeared. This has proven to be the case. Both implement version 1.5 of TEX. A few words of comparison are necessary. In my tests PCTEX ran about 8% faster than MicroTEX. These tests should not be viewed as definitive for several reasons. First, the difference depends somewhat on the type of text being processed since both versions use speedup routines that optimize differently. More important, the computer and the hard or RAM disks being u s e d have a m u c h greater effect on speed than does the choice between the two versions of TEX. The new version of PCTEX c o n t a i n s the c u r r e n t v e r s i o n s of AMS-TEX a n d LATEX. As far as I have been told, only LATEX is currently available from Addison-Wesley. Even when both are available, Addison-Wesley's current printer drivers for dot matrix printers do not have enough fonts for effective use of either macro package. My c o n c l u s i o n - - a n d I stand ready to be corrected if w r o n g - - i s that only people using laser printers can use LATEX or AMS-TEX with a package coming solely from Addison-Wesley. Personal TEX is marketing a nice screen previewer from the Mexican company Colorimetria, S.A. It is fast and may be used on many different displays. My current favorite among the IBM PC implementations of TEX is PCTEX. Aside from the reasons mentioned above, Personal TEX, Inc., is filling out a line of equipment, programs, and data (fonts) that will aid the TEX user. Addison-Wesley is likely to respond to the competition, and I suggest that the prospective purchaser carefully examine the complete line of offerings from both manufacturers before buying. Right now, I am using LATEX almost exclusively. AMS-TEX needs some additional styles to become suitable for anything but preprints of papers and sub-

THE MATHEMATICALINTELLIGENCERVOL. 9, NO. 1 9 1987Springer-VerlagNew York

mission of manuscripts to the American Mathematical Society. Adding specific styles is the smaller part of the task of writing a macro package so I assume that they will come soon. Addison-Wesley is demonstrating a PC implementation of METAFONT which is the h a n d i w o r k of David Fuchs. This certainly is not meant for the casual TEX user, but could come in h a n d y as a way of incorporating figures into TEX documents. Additionally it will be practical for people to design logos and new mathematical symbols. 1 Textset has announced an implementation of TEX for the Sun workstation. In this version, as the source file is entered, it is "TEXed" on-line and displayed on a screen. Since TEX optimizes a page at a time, this program must constantly reprocess data. It is probably too complex to install on any PC, except one with a 68020 accelerator board and a fancy display. Its features come close to my vision of the ultimate TEX machine for the knowledgeable user. I've experimented some with programs--in Pascal, if that is of interest to a n y o n e - - w h o s e output is a TEX source file and consists of an interactive question and answer session. With the exception of mathematical documents, the paperwork produced in a mathematical department office--or for that matter a dentist's office--consists of filling in forms with standard answers. TEX has the possibility of doing this in a very classy way. This is a good place to mention that Personal TEX is marketing some stylized fonts produced by the Metafoundry. For me, writing a mathematics manuscript which will look like a medieval illuminated manuscript has much a l l u r e - - a n d probably no audience. Time to return to the real world. Mike Spivak disagreed with my suggestion of the AT&T 6300 computer as a good choice of machine for running either version of TEX for the IBM PC and its clones. His argument is that off-brand versions of fast AT's can be bought for less or about the same cost and are faster and/or better. Faster and better aren't yet significant advances for the 80286 in the AT as compared with the 8086 in the AT&T. The 80286 has possibilities, not yet implemented, that could result in advantages over the 8086. My hesitation really lies in the fear that off-brand manufacturers can come and go with the sun. The buyers of their equipment are left to their own devices. 2 Since IBM PC's are now being heavily 1 Too m a n y symbols could result in incredible confusion. 2 Please forgive this unavoidable p u n . 3 See the July, 1986 issue of Byte magazine for a sample of the speed attainable with a $1000 accelerator board.

discounted, I think that a good choice in the near future will be the PC with an accelerator board using the 68020 chip. 3 Unfortunately I know of no one who has installed any version of TEX that can run on such a board. Addison-Wesley has announced the availability of TEX for the Macintosh.

3. A proposal for the distribution of preliminary versions of manuscripts and course notes Up to this point I have stressed m y happiness that TEX has reintroduced, into the world of mathematical publication, a sensitivity to the aesthetic pleasure of a beautifully produced manuscript. In this regard there are competing systems, although I view none as serious competition. TEX, however, as a standard vehicle for dissemination of mathematical documents, has amazing possibilities. I will speak about one possible system and hope that some readers are as excited as I and will come up with other (probably more sophisticated) approaches. In attempting to get TEX installed as widely as possible on the University of Connecticut campus, I spoke to knowledgeable people in our c o m p u t e r center. Much of the technical content of the following material comes from Rick Ellis. In my original article I mentioned that co-authors could collaborate by transmitting versions of a manuscript on BITnet. BITnet has far greater capabilities. For example, I could create a file, open to a n y o n e on BITnet, that contains short abstracts of my current preprints and those of my lecture notes that have been TEXed. In addition, files containing these preprints could be open for READing by people on BITnet. In the best of all possible worlds, this is an easy way to distribute documents that avoids the current backlog at the journals and even permits access to a variety of preliminary versions. Of course it can also lead to priority fights, so dialing up some central clearing house for the access code to a particular d o c u m e n t is p r o b a b l y n e c e s s a r y . (I d o n ' t k n o w whether BITnet can yet handle access codes for individual files.) Access can be in the form of TEX source code or DVI files--the latter are preferable for speed while the former, as ASCII encoded files, seem to be more readily transmitted. I was told by one mathematician-engineer that he used a network to send his lecture notes to various people teaching the same course. The manuscript circulated for several years--people added problems and suggested changes to "repay" the original author. I believe that the manuscript will eventually be published in book form. Certainly at the monograph level, THE MATHEMATICAL1NTELLIGENCERVOL. 9, NO. 1, 1987 67

where royalties are an issue only in one's wildest fantasies, our goal is to offer the most readable of documents. On-line access to course material can also make available to diverse groups the material previously restricted to a select audience. I think that we should seriously explore the installation of preprints and lecture notes in on-line data bases. These data bases should be accessible to any serious mathematician--the price should be negligible and some respectable agency should keep track of access codes so that priorities can be established with the current amount of success. I am beginning to believe that TEX, and the standardization that it offers, may have a far greater impact on scientific disciplines than simply the (eminently worthwhile) production of beautiful manuscripts.

Department of Mathematics University of Connecticut Storrs, CT 06268

Elements of Psychophysical Theory by Jean-Claude Falmagne Published by Oxford University Press, 1985

Reviewed by Margaret B. Cozzens Mathematics, as the language of science, can be used in the social sciences to carefully formulate problems, give insight into the nature of these problems, and provide techniques and approaches for the solutions of these problems. Problems in the social sciences have also given rise to new mathematics, yet the dissemination of this n e w mathematics in the wider mathematical community has been slow. Mathematicians expect to see m a t h e m a t i c s arising out of problems in physics and engineering, and they look for these new results, but psychology is not considered a main line source of new mathematics. It is for this reason that it gives me pleasure to tell you about a book in mathematical psychology that acquaints both mathematicians and psychologists with new and old mathematics arising out of the need to solve problems in psychology. This book is Elements of Psychophysical Theory by Jean-Claude Falmagne. Psychophysics is the discipline that studies various psychological sensations such as loudness, brightness, apparent length, apparent duration, and their relations to physical stimuli. It attempts to scale or measure psychological sensations on the basis of corres p o n d i n g physical stimuli. The s t u d y of psychophysics is important for society in such areas as the 68

THE MATHEMATICAL INTELLIGENCER VOL. 9, NO. I, 1987

measure of noise pollution (the disturbing effect of loudness), signal detection, studies in learning, etc. This book is intended to be a self-contained graduate text for a two-semester course discussing the basic concepts of measurement and psychophysics for graduate students in experimental psychology. It could equally well be used as a text for mathematics graduate students interested in learning about mathematics as it occurs in other areas, in this case in mathematical psychology. Indeed, the mathematical maturity of psychology graduate students would have to be fairly high to permit them to understand all of the material in the book. As Falmagne points out in his preliminary section, contemporary psychophysicists attempt to answer the question, " H o w is physical intensity coded by a particular sensory system?" Answers to this question are arrived at through the use of models and new techniques to handle the data presented. First, however, this book discusses the classical approaches to psychophysics, largely originating with the research of G. T. Fechner (1860), and attempting to relate psychophysical scales to physical scales. Even though there is substantial controversy regarding the Fechnerian approach, F a l m a g n e successfully d e m o n s t r a t e s the values of classical psychophysics from a modern viewpoint. He also presents contemporary developments along classical lines, such as that of Levine and Falmagne on parallel and subtractive families of psychometric functions. To give a bit of the flavor of the mathematics, let's look at parallel and subtractive families of psychometric functions more closely. Intuitively, a psychometric function is given by pb(a) where b is a fixed stimulus, and pb(a) is the probability that stimulus a is judged as exceeding b from the viewpoint of some sensory attribute, such as loudness or brightness. Since typically the psychophysicist wishes to investigate how a psychometric function is affected by variation in background (standard) the following more precise definition is given of a psychometric function Pb: Let I be a set of backgrounds. For each b e I, let CDeR and Pb be a real valued function on C b, such that the following are satisfied for some b e I: (i.)

C b is an open interval

(ii.) O < Pb < 1 (iii.) F: x ~ Pb (x) is continuous and strictly increasing If I is uncountable and for all a, b e I there exists a finite sequence of elements of I, a = a 1, a 2, a 3. . . . .

a n = b such that cain Cac § 1 ~ O, 1 ~< i ~< n, then {Pb : b 9 I} is a psychometric family of functions. Even t h o u g h p s y c h o m e t r i c functions resemble distribution functions in statistics, sup Pb (X) = 1 and x9

b

inf Pb (x) = 0 are not required. XeCb A particular psychometric function provides precise but highly local information regarding the discriminability of the stimulus in the neighborhood of a stimulus scale, and the family criterion insures that this local information can be pieced together to get a global picture of the subject sensitivity. A psychometric family 9 = {Pa : a 9 I} is parallel if for all Pa, Pb 9 Pa(Pa-l(Tr) + 8) = pb(Pb-l('a") + 8) for all vr9 and 8 9 Intuitively a psychometric family is parallel if any two psychometric functions can be made to coincide by a horizontal "rigid" shift of one towards the other. When a psychometric family is not parallel then one asks the question: Under what conditions does there exist a transformation of the stimulus scale that will render the psychometric family parallel? When this can be accomplished we say that the family of psychometric functions is subtractive. Stated more precisely, a psychometric family 9 = {Pa : a 9 I} is subtractive if there exist real valued functions g, u, and f such that both u and f are strictly increasing and continuous, and Pa (X) = f(u(x) -- g(a)) for all a 9 I and x 9 C a. The bridge from classical to modern psychophysical theory is crossed slowly in the middle section of the book, Chapters 4-9, since much of the classical theory is evaluated and extended from a modern viewpoint. The last five chapters could be aptly grouped together under the title Applications, as they present material at the forefront of research into the use of mathematical models in a measurement approach to psychophysical problems. Chapter 10 looks at the problem that psychophysical tasks h a v e cognitive c o m p o n e n t s such as bias, guessing strategy, etc., and models this problem using game theory, in particular an area of game theory called signal detection theory. When several variables, several sensory outputs (called channels), are involved the single variable models are extended and n e w models are developed. The theory of additive conjoint measurement is developed based on the theory that when a subject is confronted with a multidimensional stimulus, the subject may perform a simple operation akin to one in arithmetic. The second-to-last chapter presents a collection of models, procedures, and empirical analysis that provide a representation of data in terms of one or more

numerical scales, called "scaling." This is an area of active current research, but is still in its earliest theoretical development. A mathematician wishing to find an area to which he can apply his mathematical background, and contribute to the growth of a whole mathematical theory, will find this chapter particularly appealing and thought provoking. The style of this chapter is discursive rather than definitiont h e o r e m - p r o o f as much of the earlier part of the book is. The debate within the psychophysical community about scaling of sensory magnitudes is interesting and clearly delineates the difference between scales used in physics and scales used in psychophysics. In the last chapter, the author argues that "meaningfulness" is a reasonable requirement for models or laws describing empirical data. By "meaningful" he means that an equation must remain invariant under admissible transformations of the variables. A scale must carry with it a description of its admissible transformations. In conclusion, Elements of Psychophysical Elements js an interesting book for both mathematicians ~infl psychologists. A great deal can be learned from even a cursory reading of the book, and the person who explores it in depth will find himself amply rewarded for his efforts.

Associate Professorof Mathematics Northeastern University Boston, MA 02339

Prime Numbers and Computer Methods for Factorization by Hans Riesel Copyright 1985 by Birkhauser Boston, Inc. pp. v-464. Reviewed by H. C. Williams In reviewing this fine and timely work by Hans Riesel, I think it important to describe the audience for whom it is intended. According to the author's preface, he is writing for the mathematically inclined layman and the more a d v a n c e d student. It is this reviewer's opinion that an even wider audience would enjoy and benefit from reading this book. It is an excellent introduction to a subject that, up to now, has been without an introduction. The main topics covered in this text are: the number of primes b e l o w a given limit, the approximate number of primes of different types, the recognition of primes, and the factorization of large integers. It may seem a simple task to expound upon these four topics; however, a great deal of supplementary material is THE MATHEMATICAL INTELLIGENCER VOL. 9, NO. 1, 1987

69

needed. This is given in nine appendices to the main text. Even with the inclusion of these extra sections, it was not always possible to present complete proofs for all the statements given in this work. In these cases, references are provided to the relevant items in the bibliography at the end of each chapter. These bibliographies are not as extensive as they might be, but they will certainly provide a sufficient n u m b e r of pointers into the ever-increasing literature. Riesel has made a valiant (but, regretfully, not always successful) effort to include the latest results in this book. But, such is the current level of activity in his subject, that this is simply not possible. What is remarkable is the a m o u n t of material that he does manage to include. Nevertheless, it is a pity that Lenstra's beautiful elliptic curve method of factorization could not be covered (or even mentioned) in this work. The book is a much enlarged and updated version of the author's earlier En Bok am Primtal, which is available only in Swedish. It is certainly written by a man who loves his subject, a fact that is made clear by the m a n y fascinating details which he provides and the inclusion of lots and lots of numbers and numerical examples. Riesel has also included computer programs, written in Pascal, for many of the algorithms which are presented. Taken together, these features manage to convey some of the feeling that only those who actually implement algorithms experience--the delight of watching an algorithm work. I turn now to the individual chapters. There are six main chapters which, because they are designed to be i n d e p e n d e n t of one another, may be read in any order. The first chapter contains a description of various computational m e t h o d s for determining ~r(x), the number of primes up to x. The methods described include the Sieve of Eratosthenes, Meissel's formula, Lehmer's formula, Mapes' Method, and the more recent work of Lagarias, Miller, and Odlyzko. Computer, programs are presented for all of these techniques except the last and a table of values of ~(x) for x = 10n (n = 3, 4 . . . . . 16) is also given. The chapter concludes with a table which compares the computation time and storage space required by each method. Chapter 2 is made up of a collection of various results concerning the global distribution of primes. It begins with a discussion of w h y no polynomial can produce only primes and then describes some formulas which will yield all primes. The formulas of Gauss and Legendre for "rr(x) are given and the Prime Number Theorem is mentioned. A brief discussion is provided concerning the Riemann Zeta-function and the influence of its complex zeros on ~r(x). Other topics 70

THE MATHEMATICAL INTELLIGENCER VOL. 9, NO. 1, 1987

i n c l u d e : the s i g n of fi(x) - ~r(x), effective inequalities for "rr(x) and the nth prime, and the number of primes in an arithmetic progression. In the next chapter several subtle aspects of the distribution of primes are described. The conjecture on the distribution of twin primes (pairs of primes that differ by 2) is discussed and the largest known pair of twin primes is given as 1639494(24423 - 1) + 1. Recently, Harvey Dubner has found the larger pair 107570463.10225o _+ 1. The author generalizes this discussion by defining an admissible constellation to be a collection of integers of the form t + al, t + a2, . . . , t + ak, where the values of the ai's permit each t + ai(i = 1, 2, 3. . . . . k) to be a prime. He then goes on to describe h o w admissible constellations may be constructed and the prime k-tuple conjecture: any admissible constellation occurs infinitely often with all its members primes, and the asymptotic number of its occurrences ~ x is fl((x/1ogx)k). Further remarks are made about the conjecture (no longer believed) that ~r(x + y) ~ ~r(x) + ~(x) for all x,y. An interesting section, illustrated with several graphs, describes some observations on the relationship between the distribution of primes of the form 4n + 1 and the distribution of primes of the form 4n + 3. The problem of testing large integers for primality is discussed in C h a p t e r 4. The a u t h o r carefully (and properly) distinguishes between a primality test and a compositeness test. A primality test, performed on a given N, must prove rigorously that N is either prime or composite. A compositeness test can only establish rigorously that a given N is composite. For example, it is well k n o w n that if p is a prime, then the congruence aP-1 ~ 1 (mod p) must hold for any a that p does not divide. Thus, if we evaluate F ~ a N-1 (mod N) for some a such that the greatest common divisor of N and a (written gcd(N,a)) is 1 and find that F ~ 1 (mod N), then we know, without factoring N, that N is composite. However, if F ~ 1 (mod N), we do not know that N is a prime; such values of N are called base-a probable primes. If N is a composite and a base-a probable prime (e.g. N = 341, a = 2), then N is called a base-a pseudoprime; if N is a base-a pseudoprime for all

a such that gcd(N,a) = 1 (e.g. N = 1729), then N is called a Carmichael number. This is a lengthy chapter which discusses, among other things, how primality tests can be established, the distribution of p s e u d o p r i m e s and Carmichael numbers; the search for primitive roots, and the properties of the Lucas functions. The author begins by describing how primality tests can be developed for N when enough prime factors of N - 1 are known. He then goes on to show (in the case where not enough factors of N - 1 are known) how primality tests can be devised when a sufficient number of prime factors of N - 1 and N + 1, taken together, are known. These ideas can also be extended to the use of prime factors of N __+ 1, N 2 + 1, N 2 + N + 1. The chapter concludes with a brief description of Cohen and Lenstra's modification to the important primality test of Adelman, Pomerance, and Rumely. This primality test eliminates the need for a preliminary factorization of some numbers (or number) which depend(s) on N. It also executes very rapidly, requiring about a minute (in one implementation) to test numbers of 100 digits. The amount of time increases by a factor of just under 10 for each additional 100 digits in N. Incidentally, the number given in this chapter as the largest known prime is 2132~ Slowinski has since discovered the larger prime 2 2 1 6 0 9 1 - - 1. The next chapter, also quite lengthy, describes a large number of different methods for attacking the integer factoring problem. These techniques include trial division, difference of squares methods, the p - 1 method, the p + 1 method, Pollard's p-method, the Brent-Pollard method, Shanks' SQUFOF, the continued fraction method, the quadratic sieve method, and the Schnorr-Lenstra method. Most of these algorithms, such as SQUFOF, are illustrated by accompanying examples and computer programs. In fact, although it is by no means a complete discussion, the only easily available description of SQUFOF is contained in this chapter. (Perhaps this may cause the not usually reticent inventor of this pretty scheme to finally describe it fully; it's a hope, anyway.) The author also includes much information about the expected number and size of the prime factors of large integers. Running time estimates for the various algorithms are also provided. It is explained that some of these methods are special purpose techniques (they work well only when the number to be factored possesses some special property) and that others are general purpose methods. He also supplies a strategy for determining the order in which these methods should be applied to a given number. The chapter concludes with some speculative remarks on how fast a factorization algorithm can be.

The final chapter contains the n o w obligatory remarks on applications of primality testing and factorization to cryptographic work, specifically the RSA public-key cryptosystem. This is a short chapter which discusses the notion of a public-key cryptosystem, and then gives a more detailed account of the RSA scheme, including methods of key selection and a discussion of the security of the system. The second half of this book is made up of the 9 appendices referred to earlier and a set of 34 tables. Some idea of what is contained in the appendices can be obtained from their titles: "Basic Concepts in Higher Algebra," "Basic Concepts in Higher Arithmetic," "Quadratic Residues," "The Arithmetic of Quadratic Fields," "Continued Fractions," "Algebraic Factors [of certain polynomials]," "Multiple-Precision Arithmetic" (lots of programs given here), "Fast Multiplication of Large Integers," "The Stieltjes Integral." The tables include several tables of primes, factors of 2n _+ 1, 10n ___ 1, and factors of many numbers of the form a n - b n with 2 ~< a,b ~ 10. This is a well-written book, which is marred by very few errors or misprints. There are some incorrect references, such as two references concerning SQUFOF to papers which either do not mention the technique at all, or mention it only in passing, and sometimes an important or useful reference has not been included; however, these are very minor matters. In fact, the most serious error that was brought to the attention of this reviewer, is the omission of his name from the index, an oversight which, it is to be hoped, will be rectified in later printings. In his preface Riesel wishes us "a pleasant reading." This is precisely what the reader will experience. The mathematically inclined layman, the advanced student, and even the specialist will gain considerable information and delight from this book. Department of Computer Science University of Manitoba Winnipeg R3T 2N2 Manitoba, CANADA

THE MATHEMATICAL INTELLIGENCER VOL. 9, NO. I, 1987

71