sniffnoy: (Kirby)
[personal profile] sniffnoy
It works! OK, so...

All ordinal arithmetic in this entry will be natural. All addition will be natural addition and all multiplication will be natural multiplication. Basically, for now, I am embedding the ordinals in the surreals. Also, all rings will be commutative.

So you'll recall I came up with notions of "natural multichoose" and "natural choose" (aka "big multichoose" and "big choose") for ordinals. These are defined order-theoretically, remember: ((α multichoose β)) is the largest ordinal extending the partial order of weakly decreasing functions from β to α, and (α choose β) is the same with strictly decreasing functions. (Obviously, this latter is zero unless β is finite.)

So I spent quite a bit of time figuring out how to compute these, but that's a problem I solved a while back. Also you'll recall I figured out some inequalities for them. But just a few weeks ago I realized something -- that while I was looking at inequalities, I had missed at least one straight-up identity!

While the description of how to compute ((α multichoose β)) in general is more complicated (though not that complicated!), the description of how to compute ((α multichoose k)), where k is finite, is quite simpler. Here's one simple way of stating it, in the form of two rules that determine it completely: 1. We'll start with powers of ω; ((ωα multichoose k))=ωαk. 2. Now extend by Vandermonde's convolution. (Vandermonde's identity, while usually stated for choose, is also valid for multichoose, with the same proof.)

Now I had never described it in that form before; and yet, that's plainly what it was. Somehow, until the other week, I never realized that, wait, natural multichoose satisfies Vandermonde's identity! (So, for that matter, does natural choose. The rule for computing natural choose is the same as the rule for computing natural multichoose, except that of course (1 choose k) is 0 instead of 1 for k>1.)

This got me wondering about the possibility of a version of Vandermonde's identity holding even when the thing on the bottom is infinite -- after all, we're using natural addition here, and a given ordinal has only finitely many natural summands. Unfortunately, the obvious analogue doesn't work. For choose it does... but only because if you have something infinite on the bottom, both sides are automatically 0. So that's not interesting. Let's forget about putting infinite things on the bottom; while it's a fruitful subject (that I've written about elsewhere!), for the remainder of this entry, I will only consider choosing or multichoosing whole numbers.

So this got me wondering -- what about further identities? There are various combinatorial identities we could try, and I could go over how I came up with ones to try, but, well, most of them didn't work, so I think I'll just skip that.

However, one thing did appear to work. Let's talk about λ-rings. A λ-ring is a ring equipped with operations λk for each whole number k, which must satisfy certain identities. The quantity λk(x) is meant to be analogous to (x choose k) -- or, more analogously, the k'th exterior power of x. An equivalent description is in terms of operations σk, analogous to ((x multichoose k)), or, more analogously, to the k'th symmetric power of x; these satisfy similar identities but not the same ones. The λk and σk are interdefinable via σk(x)=(-1)kλk(-x).

In fact one simple way of constructing a λ-ring is binomial rings. If you have a ring R with no Z-torsion and where for any x, (x choose n) is in R -- that's (x choose n) in the usual polynomial sense -- then you get a λ-ring this way, with λk(x)=(x choose k) and σk(x)=((x multichoose k)). These are basically the simplest examples of λ-rings. We'll return to these later.

So, the one thing that appeared to work is that natural multichoose appeared to satisfy the identities of a λ-ring! The σ-identities that is, not the λ-identities. (Unfortunately, natural choose does *not* satisfy the identities of a λ-ring. You do of course get operations λk from taking Sk to be natural multichoose, but while I can find an order-theoretic interpretation of these, it's rather artificial.) I haven't listed out what the identities are, but basically, aside from a few trivial ones, there's identities for λk(x+y), for λk(xy), and for λmn(x)). (And of course one can write down analogous identities for σk.) The addition identity is just Vandermonde, and works the same way for σk; the mutliplication and iteration identities are more complicated, and are different for σk; I won't attempt to describe them here.

And actually there's a pretty simple proof that ordinal multichoose satisfies these σ-identities, though it took me a while to realize, and I spent quite a while just wondering. Basically it follows quite easily once you realize that if you have an ordinal α=ωα_1+...+ωα_r (written in "weak Cantor normal form", where there are no coefficients but the exponents are weakly decreasing), then a simple way of describing ((α multichoose k)) is as hkα_1,...,ωα_r), where hk is a complete homogeneous polynomial. (If you replace hk here with ek, the elementary symmetric polynomial, you get the λk corresponding to this σk. Which, remember, is not natural choose.)

So this is pretty good -- natural multichoose satisfies the identities of a λ-ring. There's just one thing lacking, and that's that ordinals don't form a ring. So actually they're a "λ-semiring". Or a "σ-semiring", I guess; I'm a little doubtful that the equivalence works without negatives (even though in this case the λk do take ordinals to ordinals). (EDIT: OK actually it probably works. Whatever.)

So that raises the question -- can we extend these operations, these σk, to differences of ordinals in a sensible manner, and make an actual λ-ring? Or, hell, let's go all the way -- how about we extend them all the way to the surreals? Can we make the surreals into a λ-ring like this, so that when we restrict the σk down to the ordinals, we get back the order-theoretically meaningful natural multichoose?

Note of course that there's already a λ-ring structure on the surreals coming from the fact that, as a characteristic 0, they're certainly a binomial ring. But this would be a different λ-ring structure; as a binomial ring, we'd have σ²(ω)=ω²½+ω½, whereas under this one, we'd have σ²(ω)=ω².

Basically, with ordinals, if we had a "monomial", ωαa, then what we had was σkαa)=ωαk((a multichoose k)), and then you can extend by Vandermonde. (For λ instead of σ, just use choose instead of multichoose.) Well, surreal numbers have something like Cantor normal form -- Conway normal form. The differences are that, firstly, the exponents can be arbitrary surreal numbers rather than just ordinals; secondly, the coefficients can be real numbers rather than just whole numbers; and thirdly, rather than being a finite sum, it can be an arbitrary well-ordered decreasing sum. So this gives us a way of extending it; define σkαa)=ωαk((a multichoose k)), where now α can be surreal and a can be real, and then extend in the obvious fashion. (Or you can do the same with λ instead of σ.) Of course, the question remained: Does this form a λ-ring? Vandermonde (and the trivialities) are easy enough to prove, but the multiplication and iteration identities are nasty and hard to reason about.

Now, since Conway normal forms can be added and multiplied in the obvious way, this means that surreal numbers are isomorphic to the field of Hahn series over the real numbers with the value group being the surreal numbers themselves; the isomorphism is given by just replacing ω with T-1. (Yes, the value group is also the surreal numbers; that's the sort of weird thing that happens when you've got surreal numbers.) So the question now becomes -- if we have a λ-ring, and we take a ring of Hahn series over that λ-ring, is it also a λ-ring? Where here, in this more general case, we're defining λk(Tαa) to be Tαkλk(a). (Or the same thing but with σ instead of λ.) Right, in the case we care about, that of the surreals, the base ring is the reals, and we're considering it as a λ-ring by considering it as a binomial ring.

Well, I learned, from Darij Grinberg's text on λ-rings, that in fact this is well-known if, rather than Hahn series, we are just taking polynomials. So, could I extend it? To power series, to Laurent series, to Puiseux series -- to Hahn series?

Well, long story short, yes. At first I had some trouble because Hahn series, unlike power series or Laurent series or Puiseux series, aren't actually the limit of finite sums of their monomials; so when I tried to imitate the proofs Grinberg gives, which work by first doing it for monomials and then extending by Vandermonde, I ran into a problem. I wanted to just do the same thing but extending by Vandermonde and also continuity, and this worked for power series and Laurent series and Puiseux series, but not for Hahn series. I was just going to go ask MathOverflow, honestly. But today I made one last try -- I imitated Grinberg's proofs, but this time, instead of doing it for monomials like he does, I just plugged in the whole damn sum. And it worked! (Note that Grinberg's proof basically offloads the hard part to the verification that for a λ-ring A, Λ(A), which I'm not going to define here, is a λ-ring.) I was able to keep all the infinite sums and products to contexts where they truly made sense and could be manipulated sensibly without having to worry about any sort of convergence (or where such convergence is easily proved, like rings of formal power series).

So that's it then! Hahn series over a λ-ring form a λ-ring; in particular the surreal numbers, considered as Hahn series over the real numbers, form a λ-ring; and when you restrict the σk operations of this λ-ring down to the ordinals, you get natural multichoose, which is order-theoretically meaningful. And therefore (although we knew this already by easier means) the natural multichoose operations also satisfy the identities of the σk in a λ-ring, because they are the σk in a λ-ring.

So, that's one more thing to write up someday...

EDIT: Fixed interdefinition of λk and σk, oops.
EDIT: Found a reference for the equivalence, thanks to Darij Grinberg! Hazewinkel, Gubareni, and Kirichenko's "Algebra, Rings, and Modules" volume 3 goes over it. It uses σ rather than S, so I'm changing that in the entry.



Date: 2016-05-01 08:27 am (UTC)
From: (Anonymous)

Very nice, indeed...
but I am afraid your stack
is a LIFO type one.


Re: Haiku

Date: 2016-05-02 03:57 am (UTC)
From: [identity profile]
Don't worry; when it comes to writing things up, that's more of a queue. The ordinal operations paper got jumped ahead because it was so lightweight. When it comes to research, well, I tend to work on whatever's easiest at the moment. :)

July 2017

16 171819202122
Page generated Jul. 26th, 2017 12:50 pm
Powered by Dreamwidth Studios