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 ${(G,\cdot)}$. Usually we treat the identity axiom as an exists-forall statement and the axiom of inverses as a forall-exists statement:

• ${(\exists e)(\forall x): x\cdot e = e\cdot x = x}$

• ${(\forall x)(\exists x'): x\cdot x' = x'\cdot x = e.}$

Suppose we instead write the group as ${(G,\cdot,\,',e)}$, augmenting our binary ${\cdot}$ with a unary operation ${'}$ for inverses and treating the constant ${e}$ as a ${0}$-ary operation. Then we can write the axioms, including the associative law, with only universal quantifiers that range over all of ${G}$. Those quantifiers can be dropped, leaving all the group axioms in the form of equations:

• ${x\cdot(y\cdot z) = (x\cdot y)\cdot z}$

• ${x\cdot e = e\cdot x = x}$

• ${x\cdot x' = x'\cdot x = e.}$

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 ${0}$, so not be simply universal, or one must add “${\ldots \vee x = 0}$” to the axiom, which undoes the simple equational nature. A Boolean ${\wedge}$ is OK because one can break its use into separate equations, as above with ${e}$ and ${'}$ where we really have five equations, but ${\vee}$ 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 ${f(x)}$ of one real variable—the meaning is easy to visualize: We have a finite collection of closed intervals ${I_j}$ that cover ${\mathbb{R}}$, and for each ${j}$ there is a polynomial ${p_j}$ such that ${f(x) = p_j(x)}$ for all ${x \in I_j}$. For example, we can glue together a cubic and a parabola like so:

In higher dimensions ${n}$ the pieces are semi-algebraic sets. A basic closed semi-algebraic set ${S}$ is defined via a finite set ${B}$ of polynomials ${p_i}$ as ${S = \{x \in \mathbb{R}^n: \wedge_i\; p_i(x) \geq 0\}}$. Semi-algebraic sets are finite Boolean combinations of algebraic sets. We can make equalities by adding ${-p_i}$ to ${B}$; if all are equalities then ${S}$ is an algebraic set (and sometimes called a “variety” when the aforementioned irreducibility condition isn’t enforced).

The definition of the ring ${\mathcal{PP}}$ of piecewise polynomial functions over ${\mathbb{R}^n}$ just makes the “pieces” covering ${\mathbb{R}^n}$ be semialgebraic sets ${S_j}$ in place of intervals ${I_j}$. Given ${f(x)}$ defined piecewise polynomially on ${\mathbb{R}^n}$, the question is:

Can we add some operations so that ${f(x)}$ is definable simply universally over ${\mathbb{R}^n}$, without breaking the quantification of ${x}$ into pieces?

We obviously need operations besides ${+}$ and ${\cdot}$ to form ${f}$. Natural are minimum and maximum over values ${p(x)}$ for finite sets of polynomials ${p}$. Per the literature we’ll write ${\inf}$ and ${\sup}$ even though their domains will be finite.

If ${p}$ and ${q}$ are polynomials and ${f(x) = \sup\{p(x),q(x)\}}$ for all ${x}$, then the domains ${S_1 = \{x: p(x) \geq q(x)\}}$ and ${S_2 = \{x: p(x) \leq q(x)\}}$, where ${f(x) = p(x)}$ and ${f(x) = q(x)}$ respectively, are semi-algebraic and cover ${\mathbb{R}^n}$. So ${f}$ is piecewise polynomial, ditto when ${f(x) = \inf\{p(x),q(x)\}}$ instead. The same conclusions hold when ${p}$ and ${q}$ are themselves piecewise polynomial, upon intersecting ${S_1}$ and ${S_2}$ with the other pieces.

Thus ${\mathcal{PP}}$ is closed under ${\sup}$ and ${\inf}$. We can imagine a hierarchy of functions within ${\mathcal{PP}}$ defined by alternating ${\sup}$ and ${\inf}$ 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 ${\mathcal{PP}}$:

Conjecture. For every ${n}$ and piecewise polynomial function ${f}$ from ${\mathbb{R}^n}$ to ${\mathbb{R}}$, there is a finite collection ${\{q_{i,j}\}}$ of polynomials such that for all ${x \in \mathbb{R}^n}$,

$\displaystyle f(x) = \sup_i\{\inf_j\{q_{i,j}(x)\}\}. \ \ \ \ \ (1)$

This gives every piecewise polynomial function a simple equational definition over all of ${\mathbb{R}^n}$. 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 ${\sup}$ and ${\inf}$, so this is analogous to a complexity hierarchy collapse to some kind of ${\Sigma_2 \cap \Pi_2}$ level.

Why Plausible and Why Hard?

The conjecture was proved for ${n = 1}$ and ${n = 2}$ in a 1984 paper by Louis Mahé. The first idea in his proof might be considered tantamount to the whole conjecture. Let ${S_j}$ be the ${m}$-many semi-algebraic pieces of the domain of ${f}$, and ${p_j}$ the corresponding polynomials.

Suppose for all ${i,j \leq m}$, ${i \neq j}$, we can find a polynomial ${q_{i,j}}$ that majorizes ${p_i}$ on ${S_i}$ and minorizes ${p_j}$ on ${S_j}$. Then, also taking ${q_{i,i} = p_i}$ for each ${i}$, equation (1) follows.

In our example above, we take ${q_{1,2}(x) = -10x^5 - 2x}$ and ${q_{2,1}(x) = 10x^5 + 2x}$, which satisfy the conditions on ${S_1 = \mathbb{R}^{\leq 0}}$ and ${S_2 = \mathbb{R}^{\geq 0}}$:

Next write ${q_{1,1} = p_1}$ and ${q_{2,2} = p_2}$. Then we can define:

$\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}$

These two functions are shown heavy-colored in the figure. Then ${\sup\{h_1(x),h_2(x)\}}$ reproduces the original piecewise function. As a framework this generalizes straightaway to any ${n}$: take ${q_{i,i} = p_i}$ and ${h_i(x) = \inf_j\{q_{i,j}(x)\}}$ for each ${i}$, then ${f(x) = \sup_i\{h_i(x)\}}$. So it suffices to prove that for any two “pieces” the major-minor and minor-major functions ${q_{i,j}}$ and ${q_{j,i}}$ can be found.

It is easy to picture this for ${n = 1}$: just use higher-degree single-variable polynomials in the manner of the diagram. The argument cares that ${q_{2,1}(x) = 10x^5 + 2x}$ stays below ${p_1(x) = x(x+1)(x+2)}$ for negative ${x}$, but does not care, for instance, that the parabola and cubic will have another intersection below bottom-left of the figure.

For ${n=2}$ the details are more complex but needed only a little case analysis from Mahé. Mahé himself made progress on ${n=3}$ but didn’t crack it. The issue is how much the complexity in locales where the polynomials ${p_i}$ are “glued” mushrooms with ${n}$. The graph of each ${p_i}$ is irreducible—that is to say, a variety—which comes with saying that the polynomial ideal generated by ${y_i = p_i(x)}$ in the higher space ${\mathbb{R}^{2n}}$ 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 ${n=3}$? How about all ${n}$? 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 ${\sup}$ and ${\inf}$ 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?

March 2, 2016 5:06 am

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?

2. March 2, 2016 12:21 pm

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 ${\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?