Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

April 1, 2013

The Hipparchus Operad

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 3f_1, f_2, f_3, such that

f 1(x)<f 2(x)<f 3(x)f_1(x) &lt; f_2(x) &lt; f_3(x)

when xx is negative, but

f σ(1)(x)<f σ(2)(x)<f σ(3)(x)f_{\sigma(1)}(x) &lt; f_{\sigma(2)}(x) &lt; f_{\sigma(3)}(x)

when xx 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 4f_1, f_2, f_3, f_4 such that

f 1(x)<f 2(x)<f 3(x)<f 4(x)f_1(x) &lt; f_2(x) &lt; f_3(x) &lt; f_4(x)

when xx is negative, but

f σ(1)(x)<f σ(2)(x)<f σ(3)(x)<f σ(4)(x)f_{\sigma(1)}(x) &lt; f_{\sigma(2)}(x) &lt; f_{\sigma(3)}(x) &lt; 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, 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>1n &gt; 1, the nnth Schröder number is twice the number of planar rooted trees with nn leaves such that each node has either no children or at least two.

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

1,1,3,11,45,197,903,4279,20793,103049, 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 nnth one as the number of ways of chopping a regular (n+1)(n+1)-gon into polygons by drawing nonintersecting diagonals between corners. Here are the 11 ways to chop up the pentagon:

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

The Schröder–Hipparchus numbers also count parenthesizations of a sequence of nn 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 allowed only parentheses that surround exactly two symbols or parenthesized groups, we’d get the Catalan numbers.

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

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

Then HH obeys the following equation:

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

and we can use this to solve for H(t)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 nn-ary operations has cardinality equal to the nnth Schröder–Hipparchus number. This should be the free operad generated by one operation of each arity 2,3,4,5,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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2607

19 Comments & 0 Trackbacks

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

Hey, I think you’re right!

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

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

There’s a natural partial order on the faces here, where efe \le f if ee is a face of ff. 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 nn-ary operations in an A A_\infty operad.

So, I guess the Hipparchus operad, which I was thinking of as having a set of nn-operations for each nn, really has a poset of nn-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

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

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.

Posted by: Vladimir Dotsenko on April 3, 2013 8:30 AM | Permalink | Reply to this

Re: The Hipparchus Operad

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???

Posted by: Vladimir Dotsenko on April 4, 2013 8:29 PM | Permalink | Reply to this

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

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:

Associahedra, Tamari Lattices and Related Structures.

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

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

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.

Posted by: Vladimir Dotsenko on April 3, 2013 8:16 AM | Permalink | Reply to this

Re: The Hipparchus Operad

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.

Posted by: Vladimir Dotsenko on April 3, 2013 8:36 AM | Permalink | Reply to this

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

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.

Posted by: Vladimir Dotsenko on April 4, 2013 8:27 PM | Permalink | Reply to this

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

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

Re: The Hipparchus Operad

I’ve been revisiting the large (OEIS A006318) and small (A001003) Schröder numbers. The large ones pop up in free probability theory as the sum of the unsigned coefficients of the free moment partition polynomials ( FMPs) of A350499 giving the free cumulants in terms of the free moments, which is intimately related to compositional inversion (and, therefore, Koszul duality of quadratic operads ). This ties together the combinatorics of the associahedra and the noncrossing partitions with combinatorial models refining the large and small S numbers. There are more combinatorial models of these numbers than I can shake a stick at, but the ones that interest me the most are models that can be refined to model the coefficients of the FMPS. I’ve listed some in the associated MathOverflow question, but other contributions would be welcome.

Posted by: Tom Copeland on February 23, 2022 8:16 PM | Permalink | Reply to this

Re: The Hipparchus Operad

I posted a brief set of notes on Schröder’s varied interests at On Ernst Schröder.

Posted by: Tom Copeland on March 28, 2022 6:43 AM | Permalink | Reply to this

Re: The Hipparchus Operad

Cool! That’s a nice note. May I suggest one little change? These days a lot of people are likely to read “ML” as “machine learning” rather than “mathematical logic”, and be surprised that Schröder worked on machine learning.

Posted by: John Baez on March 28, 2022 6:21 PM | Permalink | Reply to this

Post a New Comment