## April 1, 2013

#### Posted by John Baez

For any permutation $\sigma$ of 3 letters, we can find real polynomials in one variable, say $f_1, f_2, f_3$, such that

$f_1(x) < f_2(x) < f_3(x)$

when $x$ is negative, but

$f_{\sigma(1)}(x) < f_{\sigma(2)}(x) < f_{\sigma(3)}(x)$

when $x$ is positive.

However, Kontsevich noted that the analogous statement for permutations of 4 letters is false. It’s not true that if $\sigma$ is any permutation of 4 letters, we can find real polynomials in one variable $f_1, f_2, f_3, f_4$ such that

$f_1(x) < f_2(x) < f_3(x) < f_4(x)$

when $x$ is negative, but

$f_{\sigma(1)}(x) < f_{\sigma(2)}(x) < f_{\sigma(3)}(x) < f_{\sigma(4)}(x)$

It’s only true for 22 of these 24 permutations.

In general, how many permutations can be achieved by polynomials this way? The answer is given by the Schröder numbers:

$1, 2, 6, 22, 90, 394, 1806, 8558, \dots$

The following article nicely explains what’s going on:

I’m afraid this paper is not free, but you can see a version in French for free here:

One of the lessons here is that when $n > 1$, the $n$th Schröder number is twice the number of planar rooted trees with $n$ leaves such that each node has either no children or at least two.

The number of planar rooted trees with $n$ leaves such that each node has either no children or at least two, is called the $n$th Schröder–Hipparchus number. These numbers go like this:

$1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, \dots$

The Schröder–Hipparchus numbers are similar in flavor to Catalan numbers. For example, you can see the $n$th one as the number of ways of chopping a regular $(n+1)$-gon into polygons by drawing nonintersecting diagonals between corners. Here are the 11 ways to chop up the pentagon:

If we only allowed triangles in our chopped-up polygons, we’d get the Catalan numbers.

The Schröder–Hipparchus numbers also count parenthesizations of a sequence of $n$ symbols, where each pair of parentheses surrounds two or more symbols or parenthesized groups, and without any parentheses surrounding the entire sequence. Here’s how you translate between these parenthesizations and trees:

If we only allowed parentheses that surround exactly two symbols or parenthesized groups, we’d get the Catalan numbers.

Let $b(n)$ be the $n$th Schröder–Hipparchus number, and let $H$ be the generating function for these numbers:

$H(z) = \sum_{n = 1}^\infty b(n) z^n$

Then $H$ obeys the following equation:

$H(z) = z + H(z)^2 + H(z)^3 + \cdots$

and we can use this to solve for $H(t)$, work out the radius of convergence of this power series, and thus work out the asymptotic growth rate of the Schröder–Hipparchus numbers. Again, all this should be familiar if you know and love your Catalan numbers.

The trees I just mentioned remind me of operads: could this be why Kontsevich got interested in this topic? Ghys does not seem to say.

Question: I believe there is an operad whose set of $n$-ary operations has cardinality equal to the $n$th Schröder–Hipparchus number. This should be the free operad generated by one operation of each arity $2, 3, 4, 5, \dots$. Is this correct? Where, if anywhere, does this operad show up in mathematics?

Schröder numbers show up in G. W. Zinbeil’s encyclopedic work on operads, but I don’t quite see an answer to my question there. Perhaps I’m not looking hard enough. (Zinbiel is of course the long-lost brother of Leibniz, who rocketed into superstar status when he emerged from a time-reversing wormhole on January 12, 1946.)

The appearance of Schröder numbers in Uchino’s work on the derived bracket construction for operads looks a bit more promising.

Finally, how did the Schröder–Hipparchus numbers get their name? For some reason the logician Ernst Schröder, famous for the Schröder–Bernstein theorem, published a paper on them in 1870. Why? I don’t know. Can you find out?

But the even more interesting historical puzzle is this: how did the famous ancient Greek mathematician and astronomer Hipparchus get interested in these numbers?

Nobody knows for sure, but we have a big clue. The philosopher Plutarch wrote a book called Table Talk, which records some of the conversations he had with witty and erudite friends. And according to a line in this book, Hipparchus showed that the number of “affirmative compound propositions” that can be made from ten “simple propositions” is 103049.

At least in modern history, nobody had a clue what Plutarch was talking about until 1994. Nobody knew what it meant to build “affirmative compound propositions” from “simple propositions”. Part of the problem is that while Hipparchus is famous for his work on astronomy, back around 100 BC, not much is known about his work on logic.

But in 1994 David Hough, a graduate student at George Washington University, cleared up the mystery. He observed that there are precisely 103049 ways of inserting parentheses into a list of ten things, obeying the rules I’ve described. In other words, as we now say, 103049 is the tenth Schröder–Hipparchus number!

For more, see:

Given all this, I’m willing to speculate that the ways of building “affirmative compound propositions” from “simple propositions” are precisely the ways I described above for parenthesizing a list of symbols.

In other words, they are just the operations in the operad I’m speculating about!

So if I’m not making a mistake, this operad deserves to be called the Hipparchus operad.

And I believe that this operad deserves to have some application, even if only a small one, to logic. After all, Schröder was a logician… and Hipparchus was studying logic when he ran into this operad.

Were they working on the same problem?

Posted at April 1, 2013 6:45 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2607

Perhaps I am missing something but the operad you are describing seems like the a-infinity operad in vector spaces if you do not care about the differential. If so, it is definitively a very important operad!

Posted by: Kaj on April 1, 2013 10:26 PM | Permalink | Reply to this

Hey, I think you’re right!

Here’s the way I like to think about this. Each face in the $(n-2)$-dimensional associahedron corresponds to a rooted planar tree with $n$ leaves such that each node has either no daughters or at least two. For $n = 4$ it looks like this picture from Tom Leinster’s book:

So, the number of faces should be the $n$th Schröder–Hipparchus number! Here you see $b(4) = 11$ faces. For some reason I never counted them before.

There’s a natural partial order on the faces here, where $e \le f$ if $e$ is a face of $f$. This partial order is indicated by the arrows in Tom’s picture. When we take this face poset and turn it into a chain complex in the obvious way, we get the chain complex of $n$-ary operations in an $A_\infty$ operad.

So, I guess the Hipparchus operad, which I was thinking of as having a set of $n$-operations for each $n$, really has a poset of $n$-ary operations.

And yes, this is a very important operad (if I’m not making a mistake somewhere).

Posted by: John Baez on April 1, 2013 10:58 PM | Permalink | Reply to this

Yes, that is a nice observation! I think that the construction of the poset/chain complex works for almost any operad (and is the cobar construction?).

I also want to mention that there is an operad consisting of “chopped up polygons” quotiented by the dihedral group; the mosaic operad which has intimate connection with the real points on the moduli space of punctured Riemann spheres (see Tessellations of moduli spaces and the mosaic operad).

Posted by: Kaj on April 2, 2013 12:38 AM | Permalink | Reply to this

By the way, that story progressed a lot since the paper of Devadoss, see, e.g. The cohomology ring of the real locus of the moduli space of stable curves of genus 0 with marked points.

How did that happen? I posted an arXiv link to a paper of Pavel Etingof, Andre Henrquies, Joel Kamnitzer, and Eric Rains, and someone created a pretty link with the name of another arXiv paper???

Sorry. I try to make the links clickable, but I screwed up. I hope it’s fixed now.

Posted by: John Baez on April 4, 2013 8:39 PM | Permalink | Reply to this

Yes, indeed. Tom’s picture of course persists to the associahedron so the Hipparchus operad is the operad for graded A algebras without differential, e.g.the homology of a dga. The count is right if by face you mean of arbitrary codim as opposed to ‘facets’.

For many more beautiful pictures in color, see:

Posted by: jim stasheff on April 2, 2013 8:21 PM | Permalink | Reply to this

Some of this was goofy enough that I suspected the date! But the references were convincing.

Is it reasonable to think that the right operad also has a 1-ary operation, and that what you’re seeing is something like the derivative of that one?

When I see a free object with a generator of every degree (or arity, here), I think of (a) the ring of symmetric functions, which is a polynomial ring on infinitely many generators, one of each degree and (b) the complex cobordism of a point, which is (rationally) the polynomial ring on the complex projective spaces. Not that I know how to operad-ize those.

Posted by: Allen Knutson on April 2, 2013 2:45 AM | Permalink | Reply to this

Allen wrote:

Some of this was goofy enough that I suspected the date! But the references were convincing.

If I ever come up with a plausible Theory of Everything, I’ll post it to the arXiv so it shows up on April 1st. This is the best I could do now.

I hope you know who Zinbiel, the time-reversed Leibniz, actually is.

I’ll give a more serious reply later… Lisa just got back from San Francisco!

Posted by: John Baez on April 2, 2013 4:53 AM | Permalink | Reply to this

For some reason the logician Ernst Schröder, famous for the Schröder-Bernstein theorem

Famous for it, and not quite deservedly so. From R. M. Dudley’s textbook Real Analysis and Probability (page 22):

The equivalence theorem came up as an open problem in Cantor’s seminar in 1897. It was solved by Felix Bernstein, then a 19-year-old student. Bernstein’s proof was given in the book of Borel (1898). Meanwhile, E. Schröder published another proof. The equivalence theorem has often been called the Schröder–Bernstein theorem. Korselt (1911), however, pointed out an error in Schröder’s argument. In a letter quoted in Korselt’s paper, Schröder gives full credit for the theorem to Bernstein.

So Schröder goofed, but was a gent.

Posted by: Tom Leinster on April 2, 2013 3:03 AM | Permalink | Reply to this

There are two nonsymmetric Koszul operads generated by binary operations that have the same dimensions of components. One is the operad of Hochschild 2-cocycles (Hochschild two-cocycles and the good triple (As,Hoch,Mag), and the other one is the free product of two copies of the associative operad, that is two associative products, no relations between them (don’t know how to attribute this, I noticed that a few years ago but surely someone knew it before). It should be the case that the appearance of these and of A-infinity mentioned in the comments above simultaneously is not at all coincidental.

Sorry, that was only half-correct. The two operads I described have Schroder numbers as dimensions of components. Each of them has a natural structure of a left module over the associative operad (since they both contain an associative suboperad), in each cases the respective module is free, and the space of generators has the dimensions equal to Schroder–Hipparchus number.

Interesting! Since the Schröder numbers are (usually) twice the Schröder–Hipparchus numbers, some sort of ‘doubling’ seems to be going on for the two operads you describe. Is there a way to find a basis of operations that you can group into pairs, such that each pair corresponds to a tree of the sort I described?

Posted by: John Baez on April 3, 2013 3:30 PM | Permalink | Reply to this

For the free product As * As, there definitely is such a way, and it is very transparent. The operad P=As * As is I+P1+P2, where I is the unit, P1 consists of operations where the top level operation is the first product, and P2 is the same for the second product. Clearly, as vector spaces P1 is identified with P2. Each of the Pi has the top level chunk of operations of the same type, which we can encode with a k-leaf corolla (if there are k-1 copies of the top level operation used), and it has smaller elements of P grafted at the leaves, which clearly leads to an inductive definition of a basis identical to the basis of A-infinity.

Your comment does suggest an alternative: Bowlin–Brin’s Coloring planar graphs via colored paths in the associahedra considers matched pairs of rooted planar trees where the pairing matches the leaves.

Posted by: jim stasheff on April 4, 2013 1:43 PM | Permalink | Reply to this

I just found this post … Here is a late comment.

Related to your questions on the Schröder—Hipparchus numbers, I am sure that you would be interested in reading what we wrote with Jean-Louis at Section 13.11.13 of our book on algebraic operads, which is downloadable freely here: http://math.unice.fr/~brunov/Operads.pdf (Section 13.11.7 in the published version).

It deals with the magmatic-infinity operad, that is the free non-symmetric operad on one generator per arity, the one you mention with a question mark in your text. You are of course right to say that its generating series, which counts the dimensions of its components, is equal to the Schröder—Hipparchus series. But you are asking « Where, if anywhere, does this operad show up in mathematics? ». Here is one answer.

One nice property that the Schröder—Hipparchus numbers satisfy is that they give the coefficients of the inverse series with respect to the composition, see Proposition 13.11.14. And, even more interesting: one way to prove this formula uses the Koszul duality of operads. The original series f(x)=x+a1 x^2+a2 x^3+… is the generating series associated to the nilpotent operad generated by a1 binary operations, a2 ternary operations, etc. Its Koszul dual operad is the free operad generated by a1 binary operations, a2 ternary operations, etc. Since these two operads are (obviously) Koszul, their Koszul complex is acyclic and one concludes with the Euler—Poincaré characteristic that the generating series associated to this free operad is the inverse of the original series. And its coefficients are given by the number of planar trees, that is the Schröder—Hipparchus numbers!

Notice that this is « not » related to the operad A_\infty since one does not consider any differential on the magmatic-infinity operad.

Posted by: Bruno Vallette on January 15, 2014 11:43 AM | Permalink | Reply to this

Post a New Comment