##
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**

by Ran Libeskind-Hadas

hadas@cs.hmc.edu

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

mohammad@math.birzeit.edu, hasan@math.birzeit.edu

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