{\huge The Pierce-Birkhoff Conjecture}
A kind of hierarchy collapse \vspace{.25in}
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 entitled, ``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\H{o}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 $latex {(G,\cdot)}&fg=000000$. 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 $latex {(G,\cdot,',e)}&fg=000000$, augmenting our binary $latex {\cdot}&fg=000000$ with a unary operation $latex {'}&fg=000000$ for inverses and treating the constant $latex {e}&fg=000000$ as a 0-ary operation. Then we can write the axioms, including the associative law, with only universal quantifiers that range over all of $latex {G}&fg=000000$. Those quantifiers can be dropped, leaving all the group axioms in the form of equations:
Oddly, fields do not fit the mold because either the quantifier for multiplicative inverses must exclude $latex {0}&fg=000000$, so not be simply universal, or one must add ``$latex {\ldots \vee x = 0}&fg=000000$'' to the axiom, which undoes the simple equational nature. A Boolean $latex {\wedge}&fg=000000$ is OK because one can break its use into separate equations, as above with $latex {e}&fg=000000$ and $latex {'}&fg=000000$ where we really have five equations, but $latex {\vee}&fg=000000$ doesn't work that way.
The Conjecture
The conjecture concerns continuous functions that are piecewise polynomial. In one dimension---that is for functions $latex {f(x)}&fg=000000$ of one real variable---the meaning is easy to visualize: We have a finite collection of closed intervals $latex {I_j}&fg=000000$ that cover $latex {\mathbb{R}}&fg=000000$, and for each $latex {j}&fg=000000$ there is a polynomial $latex {p_j}&fg=000000$ such that $latex {f(x) = p_j(x)}&fg=000000$ for all $latex {x \in I_j}&fg=000000$. For example, we can glue together a cubic and a parabola like so:
\includegraphics[width=3.5in]{CubicQuadratic.jpg}
In higher dimensions $latex {n}&fg=000000$ the pieces are semi-algebraic sets. A basic closed semi-algebraic set $latex {S}&fg=000000$ is defined via a finite set $latex {B}&fg=000000$ of polynomials $latex {p_i}&fg=000000$ as $latex {S = \{x \in \mathbb{R}^n: \wedge_i p_i(x) \geq 0\}}&fg=000000$. Semi-algebraic sets are finite Boolean combinations of algebraic sets. We can make equalities by adding $latex {-p_i}&fg=000000$ to $latex {B}&fg=000000$; if all are equalities then $latex {S}&fg=000000$ is an algebraic set (and sometimes called a ``variety'' when the aforementioned irreducibility condition isn't enforced).
The definition of the ring $latex {\mathcal{PP}}&fg=000000$ of piecewise polynomial functions over $latex {\mathbb{R}^n}&fg=000000$ just makes the ``pieces'' covering $latex {\mathbb{R}^n}&fg=000000$ be semialgebraic sets $latex {S_j}&fg=000000$ in place of intervals $latex {I_j}&fg=000000$. Given $latex {f(x)}&fg=000000$ defined piecewise polynomially on $latex {\mathbb{R}^n}&fg=000000$, the question is:
Can we add some operations so that $latex {f(x)}&fg=000000$ is definable simply universally over $latex {\mathbb{R}^n}&fg=000000$, without breaking the quantification of $latex {x}&fg=000000$ into pieces?
We obviously need operations besides $latex {+,-,\cdot}&fg=000000$. Natural are minimum and maximum over values $latex {p(x)}&fg=000000$ for finite sets of polynomials $latex {p}&fg=000000$. Per the literature we'll write $latex {\inf}&fg=000000$ and $latex {\sup}&fg=000000$ even though their domains will be finite.
If $latex {p}&fg=000000$ and $latex {q}&fg=000000$ are polynomials and $latex {f(x) = \sup\{p(x),q(x)\}}&fg=000000$ for all $latex {x}&fg=000000$, then the domains $latex {S_1 = \{x: p(x) \geq q(x)\}}&fg=000000$ and $latex {S_2 = \{x: p(x) \leq q(x)\}}&fg=000000$, where $latex {f(x) = p(x)}&fg=000000$ and $latex {f(x) = q(x)}&fg=000000$ respectively, are semi-algebraic and cover $latex {\mathbb{R}^n}&fg=000000$. So $latex {f}&fg=000000$ is piecewise polynomial, ditto when $latex {f(x) = \inf\{p(x),q(x)\}}&fg=000000$ instead. The same conclusions hold when $latex {p}&fg=000000$ and $latex {q}&fg=000000$ are merely piecewise polynomial upon intersecting $latex {S_1}&fg=000000$ and $latex {S_2}&fg=000000$ with the other pieces.
Thus $latex {\mathcal{PP}}&fg=000000$ is closed under $latex {\sup}&fg=000000$ and $latex {\inf}&fg=000000$. We can imagine a hierarchy of functions within $latex {\mathcal{PP}}&fg=000000$ defined by alternating $latex {\sup}&fg=000000$ and $latex {\inf}&fg=000000$ 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 $latex {\mathcal{PP}}&fg=000000$:
For every $latex {n}&fg=000000$ and piecewise polynomial function $latex {f}&fg=000000$ on $latex {\mathbb{R}^n}&fg=000000$, there is a finite collection $latex {\{q_{i,j}\}}&fg=000000$ of polynomials such that for all $latex {x \in \mathbb{R}^n}&fg=000000$, $latex \displaystyle f(x) = \sup_i\{\inf_j\{q_{i,j}(x)\}\}. \ \ \ \ \ (1)&fg=000000$
This gives every piecewise polynomial function a simple equational definition over all of $latex {\mathbb{R}^n}&fg=000000$. 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 $latex {\sup}&fg=000000$ and $latex {\inf}&fg=000000$, so this is analogous to a complexity hierarchy collapse to some kind of $latex {\Sigma_2 \cap \Pi_2}&fg=000000$ level.
Why Plausible and Why Hard?
The conjecture was proved for $latex {n = 1}&fg=000000$ and $latex {n = 2}&fg=000000$ in a 1984 paper by Louis Mahé. The first idea in his proof might be considered tantamount to the whole conjecture. Let $latex {S_j}&fg=000000$ be the $latex {m}&fg=000000$-many semi-algebraic pieces of the domain of $latex {f}&fg=000000$, and $latex {p_j}&fg=000000$ the corresponding polynomials.
Suppose for all $latex {i,j \leq m}&fg=000000$, $latex {i \neq j}&fg=000000$, we can find a polynomial $latex {q_{i,j}}&fg=000000$ that majorizes $latex {p_i}&fg=000000$ on $latex {S_i}&fg=000000$ and minorizes $latex {p_j}&fg=000000$ on $latex {S_j}&fg=000000$. Then, also taking $latex {q_{i,i} = p_i}&fg=000000$ for each $latex {i}&fg=000000$, equation (1) follows.
In our example above, we take $latex {q_{1,2}(x) = -10x^5 - 2x}&fg=000000$ and $latex {q_{2,1}(x) = 10x^5 + 2x}&fg=000000$, which satisfy the conditions on $latex {S_1 = \mathbb{R}^{\leq 0}}&fg=000000$ and $latex {S_2 = \mathbb{R}^{\geq 0}}&fg=000000$:
\includegraphics[width=3.5in]{CubicQuadraticSupInf.png}
Next write $latex {q_{1,1} = p_1}&fg=000000$ and $latex {q_{2,2} = p_2}&fg=000000$. Then we can define:
$latex \displaystyle \begin{array}{rcl} h_1(x) &=& \inf\{q_{1,1}(x),q_{1,2}(x)\}\\ h_2(x) &=& \inf\{q_{2,1}(x),q_{2,2}(x)\}. \end{array} &fg=000000$
These two functions are shown heavy-colored in the figure. Then $latex {\sup\{h_1(x),h_2(x)\}}&fg=000000$ reproduces the original piecewise function. As a framework this generalizes straightaway to any $latex {n}&fg=000000$: take $latex {q_{i,i} = p_i}&fg=000000$ and $latex {h_i(x) = \inf_j\{q_{i,j}(x)\}}&fg=000000$ for each $latex {i}&fg=000000$, then $latex {f(x) = \sup_i\{h_i(x)\}}&fg=000000$. So it suffices to prove that for any two ``pieces'' the major-minor and minor-major functions $latex {q_{i,j}}&fg=000000$ and $latex {q_{j,i}}&fg=000000$ can be found.
It is easy to picture this for $latex {n = 1}&fg=000000$: just use higher-degree single-variable polynomials in the manner of the diagram. The argument cares that $latex {q_{2,1}(x) = 10x^5 + 2x}&fg=000000$ stays below $latex {p_1(x) = x(x=1)(x+2)}&fg=000000$ for negative $latex {x}&fg=000000$, but does not care that the parabola and cubic will have another intersection below bottom-left of the figure.
For $latex {n=2}&fg=000000$ the details are more complex but needed only a little case analysis from Mahé. Mahé himself made progress on $latex {n=3}&fg=000000$ but didn't crack it. The issue is how much the complexity in locales where the polynomials $latex {p_i}&fg=000000$ are ``glued'' mushrooms with $latex {n}&fg=000000$. The graph of each $latex {p_i}&fg=000000$ is irreducible---that is to say, a variety---which comes with saying that the polynomial ideal generated by $latex {y_i = p_i(x)}&fg=000000$ in the higher space $latex {\mathbb{R}^{2n}}&fg=000000$ 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 $latex {n=3}&fg=000000$? How about all $latex {n}&fg=000000$? 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 $latex {\sup}&fg=000000$ and $latex {\inf}&fg=000000$ 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?