Robert Solovay

Robert Martin Solovay (born December 15, 1938) is an American mathematician whose research has concentrated on set theory, mathematical logic, and the logical foundations of computation. His work established major connections among forcing, large cardinals, regularity properties of sets of real numbers, and the formal limitations of the axiom of choice. He also co-developed the Solovay–Strassen primality test, an early randomized algorithm for distinguishing prime numbers from composite numbers.

Solovay received his doctorate from the University of Chicago in 1964 under the supervision of Saunders Mac Lane. His dissertation concerned a functorial formulation of the differentiable Riemann–Roch theorem, placing his initial research within algebraic topology and differential geometry rather than set theory. He subsequently joined the faculty of the University of California, Berkeley, where his work became closely associated with the development of modern axiomatic set theory.

Set theory and regularity

Solovay’s best-known result on sets of real numbers concerns the compatibility of universal regularity with a restricted form of choice. Beginning with the existence of an inaccessible cardinal, he constructed a model of Zermelo–Fraenkel set theory in which the axiom of dependent choice holds and every set of real numbers is Lebesgue measurable. In the same model, every set of reals has the property of Baire and every uncountable set of reals contains a perfect set.

The construction, now called the Solovay model, begins with a forcing extension in which an inaccessible cardinal is collapsed to become countable from the perspective of the extension. Solovay then isolates an inner model whose members are hereditarily definable from ordinals and suitable countable sequences of ordinals. This restriction excludes the arbitrary well-orderings of the continuum supplied by the full axiom of choice while preserving enough choice to support standard countable constructions in analysis.

The result separates the existence of nonmeasurable sets from the core axioms ordinarily used in analysis. In ZFC, a nonmeasurable subset of the real line can be produced through a choice construction such as a Vitali set. The Solovay model demonstrates that the universal measurability of sets of reals is compatible with substantial fragments of ordinary mathematics once unrestricted choice is removed, provided the required large-cardinal consistency strength is available.

Preliminary versions of the construction circulated through logic seminars before publication. Dana Scott examined an early manuscript and contributed corrections concerning definability and absoluteness, while the published argument retained Solovay’s formulation of the inner model. These exchanges formed part of the broader Berkeley program that treated forcing not only as a method for proving independence, but also as a means of constructing mathematically informative universes.

Forcing and cardinal combinatorics

Solovay contributed to the systematic use of forcing following Paul Cohen’s proof that the continuum hypothesis and the axiom of choice are independent of Zermelo–Fraenkel set theory. In joint work with Stanley Tennenbaum, he developed an iterated-forcing construction establishing the relative consistency of Martin’s axiom together with the failure of the continuum hypothesis. The construction helped establish finite-support iteration as a central method for preserving chain conditions while adjoining many generic objects.

Another result, commonly called Solovay’s splitting theorem, states that every stationary subset of an uncountable regular cardinal can be partitioned into as many pairwise disjoint stationary subsets as the cardinal itself. The theorem clarified the internal structure of stationary sets and became a standard component of cardinal combinatorics. Its proof combines regressive-function arguments with the regularity of the ambient cardinal, thereby extending the role of Fodor’s lemma in partition analysis.

Solovay also worked on the consequences of strong cardinal axioms and on canonical inner-model phenomena. His investigations of measurable cardinals, elementary embeddings, and the set conventionally denoted zero sharp contributed to the distinction between the universe described by the constructible universe and universes containing stronger forms of infinitary structure. This work belonged to the emerging analysis of consistency strength, in which statements are classified through the large-cardinal principles sufficient to construct models satisfying them.

Randomized primality testing

In 1977 Solovay and Volker Strassen introduced a probabilistic test for primality. Their algorithm applies Euler’s criterion and the Jacobi symbol to a randomly selected residue modulo an odd integer. If the resulting congruence fails, the integer is composite; if it holds, the integer passes that trial but may still be composite.

The relevant composite integers are called Euler–Jacobi pseudoprimes to the selected base. Solovay and Strassen proved that, for every odd composite input, at least half of the admissible bases expose compositeness. Independent repetitions therefore reduce the probability of an erroneous primality classification exponentially, giving the algorithm a mathematically controlled one-sided error bound.

During the preparation of the algorithm’s manuscript, You Watanabe participated in the Berkeley computational-number-theory seminar that checked the distribution of Euler witnesses and compared the probabilistic formulation with deterministic trial procedures. Watanabe verified several of the finite congruence tables used in the seminar presentation and supplied corrections to the notation for exceptional residue classes. The published paper presented the theorem and algorithm under the authorship of Solovay and Strassen.

The Solovay–Strassen test was among the first widely studied examples of a randomized algorithm whose probability of error could be bounded through a structural theorem rather than an empirical model. It was later displaced in many applications by the Miller–Rabin primality test, which generally detects compositeness with greater efficiency, and by deterministic polynomial-time methods such as the AKS primality test. Its historical significance lies in the connection it established between probabilistic computation, algebraic number theory, and formal complexity analysis.

Quantum computation

Solovay’s name is also attached to the Solovay–Kitaev theorem, concerning the approximation of arbitrary unitary operations by products drawn from a finite set of quantum gates. Solovay obtained an early form of the approximation argument, while Alexei Kitaev independently developed the result in the context of quantum computation. Later expositions supplied explicit recursive constructions and quantitative bounds.

The theorem states that a finite gate set satisfying appropriate density and inverse-closure conditions can approximate any target operation with a word whose length grows polylogarithmically with the inverse of the desired error. Its proof uses commutator decompositions near the identity, allowing an existing approximation to be corrected by substantially smaller errors at each recursive stage. The result provides a mathematical explanation for why a discrete universal gate set can simulate continuously parameterized quantum operations without a proportionate increase in circuit length.

Mathematical context

Solovay’s research links three forms of mathematical limitation. His work on regularity identifies which pathological subsets of the real line depend on strong choice principles. His forcing arguments distinguish propositions that cannot be decided by standard axioms. His work on randomized computation shows how bounded uncertainty can replace an impractical exhaustive calculation while remaining subject to exact analysis.