# American Mathematical Monthly - MARCH 1998

## MARCH 1998

To Prove and Conjecture: Paul Erdös and his Mathematics
by Béla Bollobás
bollobas@msci.memphis.edu

Paul Erdös, who died on 26th September, 1996, in his 84th year, was one of the most remarkable mathematicians the world has ever seen. The prince of problem solvers and the undisputed monarch of problem posers, he was an outstanding figure in number theory, combinatorics, and set theory, among many other disciplines. He was the most prolific mathematician of all time, having hundreds of collaborators in dozens of countries. Yet this man, who helped to establish many careers, himself had no settled position and cared nothing for material possessions. Instead, he traveled constantly around the world, bringing mathematical news, collaborating with the locals, and inspiring all by his problems.

The author was a friend of Erdös for nigh on forty years and was one of those closest to him. This article gives an insight into the unique man who was Erdös, and describes his mathematical achievements. Eight photographs illustrate the article.

Sorting in Parallel

The design of efficient algorithms for parallel computers is a challenging and exciting area. This paper explores parallel algorithms for one of the most fundamental problems in computer science: the problem of sorting a list of numbers. Several classical algorithms for this problem are described and analyzed for parallel computers employing different interconnection networks. A very elegant proof technique due to Donald Knuth is used to prove the correctness of these algorithms.

Integration Over a Polyhedron: an Application of the Fourier-Motzkin Elimination Method
by Murray Schechter
ms02@lehigh.edu

Integrating a function of two variables over a polygon is a familiar calculus problem. Sometimes this integration requires that the polygon be decomposed into several subpolygons so that the inner limits of integration over each subpolygon are affine functions. Here's an example: if the polygon is the triangle with vertices (0,3), (3,0), and (2,2) then no matter in which order the integration is done, it's necessary to decompose the polygon. This decomposition is readily done by eyeballing a sketch. In three dimensions eyeballing doesn't work so well and in higher dimensions, it's a complete failure. So what does one do in dimensions higher than three, or even in complicated three dimensional cases? This paper produces an algorithm, based on the Fourier-Motzkin elimination method, for finding this decomposition and the limits of integration. While the method is not practical for large problems, it does go a major step beyond eyeballing.

Doing and Proving: The Place of Algorithms and Proofs in School Mathematics
by Kenneth A. Ross
ross@math.uoregon.edu

In the fall of 1996, the NCTM's Commission on the Future of the Standards asked several mathematics organizations to have groups respond to various questions about the Standards posed by the Commission. These groups are called ARGs (Association Review Groups for the NCTM Standards). The ARG for the MAA is the President's Task Force on the NCTM Standards. Every few months the NCTM Commission circulates questions to the various ARGs for their responses. The second set of questions involved the role of algorithms and proofs in school mathematics. In this article, we state the questions and give the essence of our response. We hope this will give readers a feel for the sorts of issues with which we are dealing. For the full response, including illustrative examples, we refer the reader to our website: /internal-archive?url=/past/maa_nctm.html.

NOTES

Legendre Polynomials and Polygon Dissections?
by David Beckwith

Generalized Means and Convexity of Inversion for Positive Operators
by Takyuki Furuta and Masahiro Yanagida
furuta@rs.kagu.sut.ac.jp

The Number of Ring Homomorphisms From Z_m_1 x ... x Z_m_r into Z_k_1 x ...x Z_k_s
by Mohammad Saleh and Hasan Yousef

A Simple Proof of a Theorem of Schur
by M. Mirzakhani
m_khani@rose.ipm.ac.ir

THE EVOLUTION OF...

Function: Part II
by N. Luzin
shenitze@mathstat.yorku.ca

PROBLEMS AND SOLUTIONS

REVIEWS

Évariste Galois. By Laura Toti Rigatelli
Reviewed by Roger Cooke
cooke@uvm-gen.emba.uvm.edu

The Fast Fourier Transform Workshop. By Richard and Sandra McPeak
Reviewed by Jet Wimp
jwimp@mcs.drexel.edu

Which Way Did the Bicycle Go? By Joseph D. E. Knohauser, Dan Velleman, and Stan Wagon
Reviewed by Daniel H. Ullman
dullman@math.gwu.edu

TELEGRAPHIC REVIEWS