Friedman Receives Waterman Award

Harvey Friedman, professor of mathematics, has been selected as the recipient of the National Science Foundation's ninth annual Alan T. Waterman Award. The award is made to an outstanding young research worker in any field of science, mathematics, or engineering. Selected from among 132 nominees for the award, Dr. Friedman was recognized for his fundamental contributions to virtually all branches of mathematical logic. His studies have already had profound impact in various branches of mathematical logic and are expected to influence significantly both theoretical and applied computer science.

Most notable among Dr. Friedman's contributions has been his discovery of mathematically interesting undecidable mathematical propositions. In the 1930s, the late Kurt Gödel established that in any logical system that is axiomatizable, consistent, and strong enough to contain the theory of the natural numbers, there are statements the truth or falsehood of which cannot be determined within that system. He produced such a mathematical statement. However, it has frequently been dismissed as being artificial and of no use in dealing with problems that really matter.

Over the years other examples have been given. These were still cast in abnormally abstract terms, and progress in reducing the level of abstraction has been slow. Dr. Friedman has recently found surprisingly natural and concrete statements about binary operations on rational numbers and proved that these statements cannot be proved or disproved. He has also found such statements about finite combinatorial graphs, which have more limited independence properties.

These latter statements involve one of the fastest-growing computable functions ever devised. The function counts the number of steps in the proof of the statement for a fixed initial size of graph. The concepts and methods developed by Dr. Friedman are expected to provide the framework for demonstrating that some famous unproved mathematical conjectures of long standing are actually undecidable. They may also contribute significantly to the study of the theory of algorithms and other areas of computer science.

The Waterman award was established by Congress in 1975 to recognize the first Director of the National Science Foundation, Alan T. Waterman. In addition to a medal, the award includes a monetary grant of $50,000 a year for three years of research at the advanced level. Dr. Lewis Branscomb, chairman of the National Science Board, in announcing the award stated, "In an amazingly short period of time, Dr. Friedman has become universally regarded as one of the leading mathematical logicians." Dr. Edward Knapp, Director of the National Science Foundation, said, "Dr. Friedman is known as a most energetic and imaginative young scientist. His work has profoundly changed the direction of contemporary research. In addition he has a deep understanding of the critical role of mathematics in science and of science in contemporary life."

A native of Chicago, Illinois, Dr. Friedman received his Ph.D. degree from the Massachusetts Institute of Technology in 1967 at the age of 18. He has held tenured positions at Stanford University, the University of Wisconsin, and the State University of New York at Buffalo. In 1977 he joined the faculty of the Department of Mathematics at The Ohio State University as full professor. His masterful technical skill and profound abstract conceptual concerns in mathematics have been recognized by the Waterman Award Committee. This technical skill and conceptual interpretation carries over in another area. He is an accomplished pianist. For relaxation at home or at departmental gatherings he is often seated at the keyboard sharing this talent.

The Department of Mathematics takes great pride in this honor and extends sincere congratulations to Dr. Friedman on his selection for the Waterman Award.

In linear algebra, a matrix is a rectangular array of elements. In non-mathematical contexts, the term means "mold" or "form" (as in die casting). We hope that this Matrix serves to form and mold your continuing connection with the Department of Mathematics at the Ohio State University.

We have a very active department with a wide range of responsibilities. During a typical Autumn Quarter, the department teaches about 16,000 students. This represents 51% of all student credit hours taught by the seven departments within the College of Mathematical and Physical Sciences. With two exceptions, every major program offered at Ohio State has some level of content mathematics required.

The department s courses serve major roles in the University's Honors Program. Our courses provide a suitable challenge for these exceptional students. At last year's Honors Awards Banquet, 50% of the students recognized for achievement in the college had taken courses in the mathematics honors program. Each year four or five of our undergraduate majors are elected to Phi Beta Kappa.

The department carries on its 20 year tradition of providing content mathematics courses appropriate for in-service teachers. Each quarter the department gives four or five mathematics courses for teachers at both the elementary and secondary level.

This diversity of teaching activity, to be done well with a limited staff, requires a dedicated faculty. Adequate space is also needed to carry out these tasks. Currently we lack such space, but in the new capital funding from the legislature the department has priority for a new addition to the present building.

Of the many research areas represented in the department, particularly strong are the areas of combinatorics, functional analysis, number theory, and algebraic topology. More than 35 faculty have outside research funding. During 1983 approximately $900,000 in grants was awarded to these investigators. This research reputation yields a constant pool of high quality graduate students. On the average, six Ph.D.'s graduate from the department each year. Currently 87 students are enrolled and pursuing the Ph.D. There is also an active Master's program. The department gives two degrees at this level: the MS, geared toward industrial employment, and the MA program option for secondary teachers of mathematics.

The national need for more individuals trained in the mathematical sciences is having an effect locally. The number of students electing mathematics as a major is growing. This reverses a long-term decline. It should be noted that student quality is improving as well. We feel this is due in part to the efforts of our faculty working with schools throughout the state (see the related article on page 6).

At times we are overwhelmed with the immediate tasks that need to be done. But we are engaged in exciting activity and want to communicate that excitement to our students, our alumni, our colleagues, and friends. We hope that Math Matrix will serve that role.

Alan Woods Chairman

Actuarial Sciences at OSU

The Department of Mathematics offers undergraduate opportunities in addition to the traditional mathematics major. Professor Robert B. Brown, who oversees the program, describes the major in actuarial science.

In Winter Quarter 1979, OSU offered its first actuarial course. A year later after an infusion of funds from the Griffith Foundation, an undergraduate major program in actuarial science was in place. There were four students in the major. Now there are almost 25, not counting continuing education students from the Columbus area and a few interested graduate students. The number of courses offered this year is at an all-time high, too-six. During the winter we offered an experimental review course specifically aimed at the first actuarial exam. Mr. Raj Arockiaswamy, a many-talented actuary with several degrees from OSU, taught the course to 10 enthusiastic professionals from the Columbus area. We are currently discussing when to repeat the course and whether or not to offer a review for the second exam.

The slow but steady growth in the program shows no signs of abating. As the program has grown so has the number of its graduates. These graduates have been very well received by the actuarial profession in the U.S., and actuaries are now looking to OSU as a supplier of new actuarial talent. This is a fortunate time for our students because demand for this talent is high and because the number of students attracted nationally into the profession is currently about 25% below normal. Starting salaries are almost at the level enjoyed by engineering graduates, and the opportunities for advancement in actuarial science are excellent.

Wanted

Anecdotes concerning the department or the individuals who have lived and worked here in years past and present are requested We invite you to share your stories with us -- no exaggerations please, truthful accounts From the returns received our editorial panel will select those it finds most interesting or amusing for publication in future issues of Math Matrix.

Honors Report

Mark Hovey and Maxim Goldberg Rugalev, undergraduate mathematics honors students completing their degrees this year, have both received NSF Fellowships for their beginning graduate study. The 1983 OSU mathematics team finished in the top 10% of schools competing in the annual Putman inter-collegiate mathematics competition. Of the 26 students from the College of Mathematical and Physical Sciences honored at the President's Scholarship dinner, 13 were mathematics majors. A large majority of the students from the College of Engineering at the Scholarship dinner had also taken honors courses in their mathematics program. In short, students taking honors mathematics courses are very special! While many of them have selected primary majors in engineering or the physical sciences, these students often continue with enough mathematics to earn a second major or minor in the department. They also challenge each other (and the faculty as well) in weekly problem solving seminars each autumn quarter.

The Mathematics Honors Program at OSU maintains a high standard of excellence. Students from many disciplines, the arts and humanities, as well as the sciences and engineering, find a suitable challenge in the courses offered.

To meet the evolving needs of students in our complex world of technology, the program has expanded in recent years. Currently the department offers freshman sequences dealing with single and several variable calculus at three levels. One of these includes an introduction to numerical analysis using pocket-size computers or programmable calculators. At the upper division level, honors offerings in differential geometry, discrete applied mathematics, and continuous applied mathematics will soon be in place.

This Spring Quarter, Battelle Memorial Institute hosted a reception and tour of its Columbus facilities for students participating in the honors mathematics program.

An Honors Undergraduate Mathematics Resource Center is in the planning stages. The concept includes a lounge area as well as a scientific library and computation facility. The center will provide an opportunity for informal interchange of ideas among faculty and students. It will also be an important resource facility for independent research projects and sophisticated mathematical scientific computation.

In Memoriam

Within the last three years, the Department of Mathematics has lost the valuable contributions of three key persons.

Dan Eustice, associate professor, died August 5, 1981. Dan was a complex analyst and worked with honors students and honors programs. He served as problems editor for Mathematics Magazine

John Riner, professor, died January 24, 1982. John was a topologist and served as vice-chairman for the department for many years. He was a leader and innovator in all aspects of undergraduate education.

Norman Levine, professor, died December 28, 1983. Norm worked in point set topology and was always concerned about providing the best possible instruction for students. He coordinated several of the freshman-level courses and served as chair of the instruction and evaluation committee in the department.

In Case You Haven't Heard . . .

2²⁵¹ - 1 = (503) X (54217) X (178230287214063289511) X (61676882198695257501367) X (12070396178249893039969681)

The factorization of this 76 digit number was recently achieved by scientists at Sandia National Laboratories (TIME 13 February 1984). They employed a new type of algorithm especially suited to the internal working of the Cray-1 computer. The factoring process was completed in 32 hours and 12 minutes. Because of the time necessary to do the factoring, there is reason to reconsider one of the more recent approaches to encoding information-the so called RSA method of public-key cryptography. The following slightly abridged article provides a simple introduction to that method. It was written by Patrick J. Costello and appeared in the November, 1983, newsletter of Eastern Kentucky University. Professor Costello received his Ph.D. at Ohio State in 1982. His dissertation, "Classification and construction of Positive Definite Integral forms over "   was directed by John Hsia.

Public-Key Cryptography

Cryptography is the science of writing messages that no one except the intended receiver can read. In this article the basic idea behind an "unbreakable" method for encoding and decoding messages that was developed fairly recently will be described. However, the key fact that makes it all work is a theorem discovered over 300 years ago by the French mathematician, Pierre de Fermat.

The full-blown version of the RSA method (the term comes from the discoverers names-Rivest, Shamir, and Adleman) is very easy to describe, but requires a fairly fast and powerful computer to implement the procedure. We will look at a greatly modified version that uses the same basic idea, but can be implemented fairly easily on a slower, less efficient computer or even a pocket calculator.

We need first a general description of public-key cryptography. Everyone who is a legal participant is assigned two "keys" that are used to encode ("lock") and decode ("unlock") secret messages. Each person P has an E_P key that is placed in a public directory and is used by other people to encode the written message that is to be sent to P. Each person P also has a second key, D_P that P keeps secret and uses to decode any encoded message that is received. Hopefully, even though E_P is publicly revealed, there is no easy way for an outsider to determine D_P

Before we describe the particulars of our public-key cryptosystem, we mention one mathematical notation. When we say n mod m, we are referring to the remainder when n is divided by m. For example, 10 mod 3 is 1 since 10 divided by 3 leaves a remainder of 1.

Here now are the steps involved in determining encoding keys and also the steps to encode a message. First, assign numbers to the letters of the alphabet. For instance, A = 02, B = 03, C = 04, ..., Z = 27. (In a moment we shall see why you shouldn't choose A = 01.) Next, pick a prime number q bigger that 27 and an integer e between 1 and q-1 with the property that e and q-1 have no common factor greater than 1. For instance, choose q = 29 and e = 3. The e that you have chosen is your public encoding key. To transmit a message the sender would take the alphabetic message and convert it to number code by replacing each letter by the number assigned to it in the first step. For instance, CAT would become 04 02 21. The sender now calculates n^e mod q for each two digit number n. Hence, if q = 29 and e = 3, this computation gives:

(04)³ mod 29 is 06,

(02)³ mod 29 is 08,

(21)³ mod 29 is 10.

To an outsider who happened somehow on the set of numbers that represents the encoded message, the content of the message will be very difficult to interpret. On the other hand, you can unlock its message very easily. Your decoding key consists of a number d between 1 and q-1 with the property that ed mod q-1 is 1. (That such a number d exists is taught in a college course in abstract algebra or number theory.) Remember that this key is your private key and hopefully no one else knows it. In the example that we have been using, we let q = 29 and e = 3. For this choice, the number 19 is your d key because 3.19 mod 28 is 1.

Here are the steps involved in the decoding process. First, calculate n^d mod q for each two digit number n received. In our ongoing example, when we receive the set of numbers 06 08 10, we carry out the following calculations:

(06)¹⁹ mod 29 is 04,

(08)¹⁹ mod 29 is 02,

(10)¹⁹ mod 29 is 10.

In the cryptosystem that we have just outlined, the privacy of someone's d key rests upon preventing outsiders from learning the value of q. For if an outsider knows the value of q and e (e is already public), a fairly easy computation will produce the value of d. In the "real" version of the RSA scheme, q is replaced by a product of two enormous primes (50 digits each, for instance). In the scheme, the product is made public but not its two factors. For an outsider to determine someone's decoding key would require factoring the public product into its two factors. But when the two factors are 50 digits each, it would take a fast, powerful computer about 74 years to find them!!

RECOGNITIONS

Timothy Carlson, assistant professor, has been selected as a Sloan Research Fellow. Selection under this program, sponsored by the Alfred P. Sloan Foundation, follows a well-developed procedure designed to identify young scholars who show great promise for doing original work in their field. The Sloan Research Fellowship program was begun in 1955 as a means of encouraging basic research. Over the years, the winners of these awards have made major contributions in their disciplines. Professor Carison is a new member of the Department of Mathematics and specializes in the areas of logic and set theory. He has published several papers in this area and currently his research deals with fundamental questions related to infinite combinatorics.

Jeffry Kahn was also one of this year's group of 90 Sloan Research Fellows. Dr. Kahn, an associate professor of mathematics at Rutgers University, received his doctoral degree from the Department of Mathematics in June, 1979. His dissertation, "Locally projectiveplanar lattices which satisfy the bundle theorem," was directed by Dijen Ray-Chaudhuri.

Nicholas Ercolani, assistant professor, was awarded a Mathematical Sciences Postdoctoral Research Fellowship from the National Science Foundation. Approximately 30 such awards were made by the NSF this year. The young investigators choose a research environment for study that will have a strong impact on their future scientific development. Among the criteria for earning the NSF award are scientific ability as evidenced by past research accomplishments and the projected quality of the research likely to emerge from the tenure of postdoctoral study. Professor Ercolani's research deals with the geometry and perturbation theory of completely integrable nonlinear differential equations and, in particular, soliton wave equations. Under the terms of the NSF award, he plans additional study while on leave at the University of Arizona.

Dhanajay Hajela, lecturer, has accepted a position in the research division of the reorganized Bell Labs (Murray Hill). He was also awarded a Mathematical Sciences Postdoctoral Research Fellowship as well as research fellowships at several distinguished institutions. In addition he had an invitation to become a member of the Institute for Advanced Studies at Princeton. He expects to spend some time at the Institute in conjunction with his current position. Dr. Hajela received his Ph.D. in spring, 1983. His dissertation, "On additive sequences, counting points in hypercubes, and A(p) sets", was directed by William P. Johnson.

These individuals join other faculty in the Department of Mathematics who have received recognitions in the recent past:

• Eiichi Bannai, OSU Distinguished Research Award, 1979
• Harvey Friedman, OSU Distinguished Research Award, 1982; NSF Waterman Award, 1984
• Joan Leitzel, OSU Distinguished Teaching Award, 1982
• Paul Nevai, OSU Distinguished Research Award, 1981
• DiJen Ray-Chaudhuri, OSU Distinguished Research Award, 1983
• Arnold Ross, OSU Distinguished Service Award, 1981
• Paul Seymour, Sloan Research Fellowship, 1983
• Hans Zassenhaus, OSU Distinguished Research Award, 1981

Undergraduates Selected for Phi Beta Kappa

An invitation to become a member of Phi Beta kappa recognizes outstanding academic performance in a demanding undergraduate program. Students must maintain a high grade average while demonstrating a broad base of knowledge in the liberal arts. Programs of typical students exhibit strength in the major and include honors or upper division courses in fields outside the major area of study, two or more foreign languages, and frequently some form of independent research project.

Of the 62 students selected for membership this year, special congratulations are extended to the following Mathematics and Computer and Information Sciences majors:

• Louis Steven Biafore, senior, computer and information science
• Matthew DeJongh, junior, computer and information science
• Daniel Albert DiSanto, senior, mathematics
• Maxim J. Goldberg-Rugalev, junior, mathematics
• Mark Alan Hovey, senior, mathematics
• Lisa Jolene Klempay, BS, 1983, computer and information science
• Paul Scott Leonard, senior, computer and information science
• Gary Edward MacPhee, BS, 1983, computer and information science
• Kathy Sue Noe, senior, computer and information science
• Kathy Anne Price, senior, computer and information science
• Carolyn Sue Reichert, senior, mathematics
• Gerard Michael Williger, senior, astronomy and mathematics

Math Department Works with Ohio Schools

During the 1970s the mathematics preparation of freshman entering Ohio State experienced a sharp decline. In 1965, eight percent of the freshmen students demonstrated no skills in elementary algebra on the mathematics placement tests. This number increased to 26% in 1975. During the same period the average rank in high school of the freshmen improved.

In 1977 the University sent a report to each Ohio high school on the mathematics and English preparation of the Ohio State students from that school in the period 1974 to 1977. In response to those data, Westland High School near Columbus asked the Department of Mathematics to test its college-intending juniors. The high school felt these students should be appraised of their mathematics levels with respect to University expectations before registering for senior year courses. This invitation was the beginning of the Ohio Early Mathematics Placement Testing Program. This program has grown each year since 1977. In 1983-84, more than 60,000 juniors in 614 Ohio high schools wrote the early placement test. The program is now funded within the state budget of Ohio. All of the state universities participate, and a student's test performance is interpreted in terms of the curriculum at the university he or she designates. Professor Bert Waits is the program director. Among the positive results of the Early Testing Program has been an average 40% increase in senior year mathematics enrollments in the high schools participating.

A curricular problem became evident through the Early Testing Program; the traditional college preparatory program has not provided an appropriate senior year course for low-achieving students in mathematics. In 1981-82 Professor Frank Demana and Professor Joan Leitzel (together with Professors F. Joe Crosswhite and Alan Osborne of the faculty of Mathematics Education at OSU and two high school mathematics teachers) piloted a new course for college-intending high school seniors who, as juniors, showed essentially no skills in algebra. This project was funded by the Battelle Memorial Foundation. The results have been very promising. More than 80% of the students improved their mathematics placement levels and almost 70% reached an accepted level for university entrance. The same group of faculty, with a grant from SOHIO, is now working with seventh and eighth grade students on a project to improve the transition from arithmetic to algebra. In Autumn Quarter, 1984, freshmen for the first time will be conditionally enrolled if they have not taken a full college preparatory program in high school. The data on applicants indicate that all but 7.4% have taken at least three years of college preparatory mathematics This is a marked improvement over previous years and hopefully will mean that Ohio State freshmen are now even better prepared to begin the mathematics required in their University programs.

Another part of the department's efforts in working with the schools has been the development of a full program of mathematics courses for in-service elementary and secondary teachers. These courses draw enrollments of more than 250 students each year. In addition, the Department of Mathematics has defined a Master's degree option especially for teachers. The program began during the summer of 1981. Presently there are 40 students pursuing this degree option. Of these, 25 are full-time students, serving as teaching associates in the department.

Through all of these cooperative efforts with schools and special programs for teachers, the department is recognizing that mathematics teaching is a task of primary importance in today's scientific and technological society.