# The Pierce-Birkhoff Conjecture

* A kind of hierarchy collapse? *

Cropped from father-son bio source |

Garrett Birkhoff was a mathematician who is best known for his research on lattices, and also his work on teaching of abstract algebra. He was at Harvard almost his whole career.

Today we wish to discuss a conjecture that he made with Richard Pierce that remains open today.

We will state the Pierce-Birkhoff conjecture in a moment, but it was John Isbell, in work with Melvin Henriksen, who made the question precise. Moreover, Isbell is believed to have named the conjecture. He popularized it in the 1980s by discussing it with those interested in real algebraic geometry.

## Isbell

Dick once had Isbell as a professor at Case Western. In an earlier post discussing Isbell’s role in another conjecture about coloring the plane, Dick told the story of taking an elementary course from Isbell on projective geometry and almost failing it. The story reveals that Isbell could be a “character.” See this 2006 memorial by Henriksen and 1996 interview for further stories about Isbell.

Isbell enjoyed using the pseudonym “John Rainwater” and two other fictitious names. Rainwater had been invented by graduate students at the University of Washington in 1952. Isbell published the first paper by Rainwater, which then led other mathematicians to both write papers under the same name or to sometimes acknowledge Rainwater for kindly assistance.

We are a bit surprised to see that pseudonyms are not uncommon. See this discussion for some examples of famous mathematicians using pseudonyms. Our own Noga Alon has used the name “A. Nilli” for over a dozen papers. Also see this at Wikipedia:

Peck first appeared as the official author of a 1979 paper titled, “Maximum antichains of rectangular arrays.” The name “G.W. Peck” is derived from the initials of the actual writers of this paper: Ronald Graham, Douglas West, George Purdy, Paul Erdős, Fan Chung, and Daniel Kleitman. The paper initially listed Peck’s affiliation as Xanadu, but the editor of the journal objected, so Ron Graham gave him a job at Bell Labs.

## Universal Algebra

Birkhoff is most associated with *universal algebra*, whose basic idea furnishes an analogy to our topic. Consider how to define groups . Usually we treat the identity axiom as an exists-forall statement and the axiom of inverses as a forall-exists statement:

Suppose we instead write the group as , augmenting our binary with a unary operation for inverses and treating the constant as a -ary operation. Then we can write the axioms, including the associative law, with only universal quantifiers that range over all of . Those quantifiers can be dropped, leaving all the group axioms in the form of *equations*:

These are simple equations—indeed almost polynomial equations. The solution set of finitely many polynomial equations is called a *variety* when it meets a certain irreducibility condition. Birkhoff applied the term *variety* to kinds of mathematical structures that are definable in the above manner like groups. He proved a key theorem characterizing those kinds by closure properties.

Oddly, fields do not fit the mold because either the quantifier for multiplicative inverses must exclude , so not be simply universal, or one must add “” to the axiom, which undoes the simple equational nature. A Boolean is OK because one can break its use into separate equations, as above with and where we really have five equations, but doesn’t work that way.

## The Conjecture

The conjecture concerns continuous functions that are *piecewise polynomial*. An important class of examples are splines and their derivatives. In one dimension—that is for functions of one real variable—the meaning is easy to visualize: We have a finite collection of closed intervals that cover , and for each there is a polynomial such that for all . For example, we can glue together a cubic and a parabola like so:

In higher dimensions the pieces are *semi-algebraic sets*. A basic closed semi-algebraic set is defined via a finite set of polynomials as . Semi-algebraic sets are finite Boolean combinations of algebraic sets. We can make equalities by adding to ; if all are equalities then is an *algebraic set* (and sometimes called a “variety” when the aforementioned irreducibility condition isn’t enforced).

The definition of the ring of *piecewise polynomial* functions over just makes the “pieces” covering be semialgebraic sets in place of intervals . Given defined piecewise polynomially on , the question is:

Can we add some operations so that is definable simply universally over , without breaking the quantification of into pieces?

We obviously need operations besides and to form . Natural are *minimum* and *maximum* over values for finite sets of polynomials . Per the literature we’ll write and even though their domains will be finite.

If and are polynomials and for all , then the domains and , where and respectively, are semi-algebraic and cover . So is piecewise polynomial, ditto when instead. The same conclusions hold when and are themselves piecewise polynomial, upon intersecting and with the other pieces.

Thus is closed under and . We can imagine a hierarchy of functions within defined by alternating and over polynomials, and that some piecewise-polynomial functions might not belong to this hierarchy. However, in the crisp form supplied by Isbell and Henriksen, the Pierce-Birkhoff conjecture says the hierarchy collapses to a low level that captures all of :

Conjecture.For every and piecewise polynomial function from to , there is a finite collection of polynomials such that for all ,

This gives every piecewise polynomial function a simple equational definition over all of . Birkhoff and Pierce had contemplated a more abstract version of this idea, but Isbell and Henriksen brought it down to the interest of real functional analysts. There is a similar statement swapping and , so this is analogous to a complexity hierarchy collapse to some kind of level.

## Why Plausible and Why Hard?

The conjecture was proved for and in a 1984 paper by Louis Mahé. The first idea in his proof might be considered tantamount to the whole conjecture. Let be the -many semi-algebraic pieces of the domain of , and the corresponding polynomials.

Suppose for all , , we can find a polynomial that

majorizeson andminorizeson . Then, also taking for each , equation (1) follows.

In our example above, we take and , which satisfy the conditions on and :

Next write and . Then we can define:

These two functions are shown heavy-colored in the figure. Then reproduces the original piecewise function. As a framework this generalizes straightaway to any : take and for each , then . So it suffices to prove that for any two “pieces” the major-minor and minor-major functions and can be found.

It is easy to picture this for : just use higher-degree single-variable polynomials in the manner of the diagram. The argument cares that stays below for negative , but does not care, for instance, that the parabola and cubic will have another intersection below bottom-left of the figure.

For the details are more complex but needed only a little case analysis from Mahé. Mahé himself made progress on but didn’t crack it. The issue is how much the complexity in locales where the polynomials are “glued” mushrooms with . The graph of each is irreducible—that is to say, a variety—which comes with saying that the *polynomial ideal* generated by in the higher space is *prime*. Efforts to analyze these intersection points have moved from the geometric to the algebraic side via the theory of local rings and ideals, as represented by this 2007 paper and this 2012 paper.

## Open Problems

Does the conjecture hold for ? How about all ? Also is there so way to connect the conjecture with complexity theory? One way might be to use approximation tools we have developed, for instance approximating finite and by rational functions. It seems that the ability to place a piecewise polynomial function into a kind of normal form should be related to complexity theory. Can we possibly solve the conjecture by leveraging some complexity tools?

I would guess that the statement in the conjecture is equivalent to the same one using $\mathbb{Z}, \mathbb{Z}^n, \mathbb{Z}[x]$ instead of the “real” statements (moving from reals to rationals by continuity, and then easily moving from rationals to integers). Is it known where this is equivalent?

Look this problem:

A succinct representation of a set of (distinct) b-bits positive integers is a Boolean circuit C with b input gates. The set represented by C, denoted S_{C}, is defined as follows: Every possible integer of S_{C} should be between 0 and (2^{b} – 1). And j is an element of S_{C} if and only if C accepts the binary representations of the b-bits integer j as input. The problem SUCCINCT MAXIMUM is now this: Given the succinct representation C of a set S_{C} and a b-bits integer x, where C is a Boolean circuit with b input gates, is x the maximum in S_{C}?

It is very easy to show this problem is not in P, because we should need n comparisons to know whether x is the maximum in a set of n (distinct) positive integers when the set is arbitrary. And this number of comparisons will be optimal. This would mean we cannot always accept every instance (C; x) of SUCCINCT MAXIMUM in polynomial-time, because we must use at least n = |S_{C}| comparisons for infinite amount of cases, where |S_{C}| is the cardinality of S_{C}. However, n could be exponentially more large than the size of (C; x).

But, at the same time, it is so easy to show this problem is in coNP. Certainly, given a b-bits integer y, we can check whether C accepts the binary representation of y (which means that y is an element of S_{C}) and x < y in polynomial-time, and thus, we could verify whether (C; x) is a "no" instance SUCCINCT MAXIMUM in polynomial-time.

However, the existence of a problem in coNP and not in P is sufficient to show that P is not equal to NP, because if P would be equal to NP, then P = coNP.

Basically is this, but you could see more in

https://hal.archives-ouvertes.fr/hal-01281254/document

I would guess that the statement in the Pierce-Birkhoff conjecture is equivalent to the same one using , , instead of the “real” statements (moving from reals to rationals by continuity, and then easily moving from rationals to integers). Is it known where this is equivalent?

I don’t know for sure, but I suspect not—for one, the notion of “continuous” for a discrete function would have to use a different topology, and also I don’t know if there’s enough “wiggle room” near glue points that way. As far as I know on the algebraic side of the coin, the notion of a real field is important, and the issue in higher dimensions is how complicated the intersections can be locally. I chose the diagrams to put across the idea that things could get pretty tight near the gluepoints—the quintic just manages to fit in there. I stopped short of trying to say more about local rings and “intersection theory” and spectra/generic-points because the little I know is on the complex (algebraically closed) side.