Chronicles of Harry

So, here's something that had bugged me for a long time. Jacobsthal multiplication is associative, but the proof of this is unsatisfying. Normally the way you prove an operation is associative is that you show that a multiary version of it makes sense; you don't just literally show that a(bc)=(ab)c, you show that abc makes sense on its own as a ternary thing (or with even more operands) and that a(bc) and (ab)c are both equal to this.

But for Jacobsthal multiplication, the only proof I knew of its associativity was to show that a×(b×c) was equal to (a×b)×c; I wasn't able to find an interpretation of a×b×c on its own.

Now, some years ago, Paolo Lipparini found an order-theoretic interpretation of the Jacobsthal product, but it wasn't one that led to an immediate proof of associativity. But based on an observation of Isa Vialard, I think I finally have one! It's a little awkward, but of course it is; it's Jacobsthal multiplication, after all.

Let's say A and B are WPOs, and let's consider the lexicographic product A·B (note: B here is the coordinate that's compared first). Then o(A)o(B) ≤ o(A·B) ≤ o(A)×o(B).

But, actually, we can say more. Suppose B has k maximal elements, so that o(B) has finite part greater than or equal to k. Then, Vialard noted, we have o(A·B) = o(A)·(o(B)-k) + o(B)×k.

In particular, if o(B) has finite part equal to its number of maximal elements, then o(A·B)=o(A)×o(B). (In fact, as long as A has multiple distinct powers of ω in its Cantor normal form, the converse also holds.)

Btw, the finite part of o(B) is equal to the number of elements of B that have only finitely many elements above them. We could call such elements "almost maximal". So B satisfies this condition iff every almost maximal element is maximal.

Anyway, let's call a WPO that satisfies this condition "flat-topped". Note that flat-topped WPOs are closed under disjoint union, under Cartesian product, and, yes, under lexicographic product! So we can interpret α×β as the type of A·B for any flat-topped A,B with o(A)=α and o(B)=β; and we can do similarly with α×β×γ, etc. So this does it! We've interpreted multiary × and proved associativity nicely. Hooray!

EDIT 5/5: Actually, on writing to Lipparini about this, he pointed out to me that another observation of Vialard provides an even easier answer, namely, without needing the flat-topped condition, one has w(A·B)=w(A)×w(B), where w is width. I hadn't noticed this because, well, I've never really paid a lot of attention to widths, tbh.

You can go read it here: https://arxiv.org/abs/2409.03199

I'm not going to bother trying to summarize this one, you can go read it. Hopefully soon Alakh writes his follow-up that will cover the case of strings of length less than ω^ω, rather than just strings of length less than ω^k, like I did here?

(Back in March of last year when I was in Belgium, and he told me how he did it, I was like, how did I miss it! It's so simple! But I did miss it, so, I'm doing ω^k and he's taking ω^ω.)

Next paper in the pipeline will probably be the one on Zeckendorf addition, I've been convinced I need to get that out quickly, although I still haven't heard back from Sophie MacDonald, hm, I guess I didn't write about that here, but, uh, there's a thing she says she has a proof of which it would be very helpful to me if she actually does!

After that... oy, too much to write, too little time to write it in... well, I'll figure something out... (I also should, like, start looking for a new job soon probably...)

(Um, unrelatedly, we're down to just 179 books left to give away!)

There's some other stuff I've been meaning to write about, but, uh, I'll get to that some other time...

(EDIT: Added more specific numbers.)

So, let me talk about some math I did while I disappeared from this site for a while. Or, um, attempted to do. You'll see.

Now, as I think I've said before, I've basically closed down my whole ordinal-operations project, seeing as I've gone as far as I think can go with it. While I haven't had a lot of time to get math done recently, my intent was to finally return to integer complexity and addition chains.

...but, one last WPOs problem popped up to distract me. The problem was this: Given ordinals α and γ, what's the largest possible value for o(γ×X), where o(X)=α? (Assuming there is a largest one, anyway; if not, that would be quite notable itself!)

I'll skip discussing for now why I wanted an answer to this particular, odd-looking problem; there were several reasons but I don't really want to take the time to go into them. Point was, I wanted an answer to this question, and it seemed doable.

Now I'd already attempted this twice before and given up -- basically because it was too tedious. Why was it so tedious? Well, so, I thought I actually had most of an answer already, actually! I thought I had a recursion that would yield the correct answer. I hadn't proven it would, but I'd proven it was an upper bound, and I figured I'd save proving that it was also a lower bound for later, as that would likely be tricky. First, I wanted to solve the recursion. Because after all that's what I wanted to do -- I wasn't going to be satisfied with a recursion for the answer, I wanted a more explicit finite rule! That's what's I do!

How do you solve a complicated transfinite recursion? You grind out values -- by hand -- until you see the pattern, that's how. I'd done this before, tedious as it could get, and I could do it again. But it had never been quite this bad.

Consider the previous times I'd done this. When I was computing "right multichoose", I had one transfinite variable (α) and one finite variable (k). This meant I could do it one value of k at a time and get a handle on things. While when I was doing this for D(α₁×...×α_m), there were multiple transfinite variables, but they were all symmetric with each other, and the resulting answer wasn't that complicated (in the recursive case, anyway, which is what we're concerned with here), so it didn't take a lot of grinding out hand computations to figure it out.

Here, we had two variables, both transfinite, with no symmetry between them, and a nasty, complicated answer. What could I do? This is why I gave up the first two times -- it's way harder to make a transfinite-by-transfinite table, than to merely make a transfinite-by-infinite table! And staring at what tables I did have, the whole thing just looked nasty, with some regularity to it but also full of exceptions.

But for this third attempt, I had a plan: I'd take it one value of γ at a time, going row-by-row, similarly to how I worked with "right multichoose" earlier. (I later transposed the table so it was column-by-column.) Since each row was transfinite rather than merely infinite, this meant every individual row would itself take substantial work to solve, but, well... it worked. The plan of attack worked and before long I was making substantial progress, progressively figuring out the answer for higher and higher values of γ.

Occasionally I'd find I made a mistake and had to go back and redo things. This can easily happen with this sort of thing unfortunately -- you think you've found the pattern when you haven't yet. But I found the mistakes and I fixed them, however much apparent progress it undid.

So I spent weeks grinding out these hand computations. And then, on a flight to Seattle for work, while grinding out a few more, I noticed an answer that looked, just... too big. The parameters here were γ=ω^ω+12, α=ω^ω2. The answer I got was ω^ωω³. Just way too large, right?

I must have made a mistake, I figured. But being on the plane, well, it was a bit hard to go back and recheck all my previous work right there! So I figured, OK, first I can at least check that I have made a mistake -- I can check it against the naïve bound, 2^γ×α. If it's larger, clearly I messed up. And indeed, it was larger! The naïve bound was a mere ω^ωω3+12. So I'd messed up somewhere.

Except... now that I'd bothered to actually compute the naïve bound, I noticed something: Lots of my answers were too big! Even ones way, way earlier! Clearly I couldn't have messed them all up -- the early ones I'd checked and rechecked. (I'd eventually find that the first of the answers that was too big occurred at γ=ω+1, α=ω. (Naïve bound: ω^ω+1. My answer: ω^ω2.) Yes, all the way back at ω+1. Hoo boy. And for γ≤ω, my answers were just equal to the naïve bound.)

So what was the problem here? I didn't think I'd messed up that far back. Could I have gotten the recursion wrong? I rechecked how I'd derived it, and, no, I'd gotten it right.

Eventually I came to the only conclusion not eliminated: I'd correctly proved that the recursion yielded an upper bound, but my hypothesis that it would yield the exact answer, which I'd never even attempted to verify? Yeah, that just wasn't true at all. All I'd done was come up with a hard-to-describe bound that was, frequently, worse than the naïve bound. Welp.

So yeah, lacking any other approach to the problem, I chose to give up for a third time. Man, that's a lot of time I could've saved if I'd just done this basic sanity check -- checking against the naïve bound -- earlier! Oh well. Just going to have to be satisfied with the naïve bound here.

Anyway, yeah, time to finally get back to integer complexity and addition chains, like I said; once I have some free time to do math again, anyway...

So, as a special case of the theorems in Diana Schmidt's habilitation thesis, one gets that the maximum extending ordinal of the set of finite plane trees is at most the small Veblen ordinal.

It turns out that in 2005, Herman Jervell published a paper describing an order on the set of finite plane trees, extending the partial order, and with order type the small Veblen ordinal.

Therefore, the maximum extending ordinal of the set of finite plane trees is equal to the small Veblen ordinal.

What's annoying, though, is that Jervell didn't state his result in that form -- presumably because he wasn't aware of the theory of maximum extending ordinals. This is really annoying, because it means that the result stated in that form probably won't appear in the literature for quite some time. It's such an immediate consequence of Schmidt's upper bound and Jervell's implicit lower bound that it's not remotely separately publishable. Blargh.

Well, I wanted to publicize this fact here, at least. :P The maximum extending ordinal of the set of finite plane trees is equal to the small Veblen ordinal.

Edit: I guess actually there is a well-known connection between Kruskal's tree theorem and the small Veblen ordinal, the latter being the proof-theoretic ordinal of the former. Are these statements equivalent, meaning actually this has long been known in a different formalism? Um. I have no idea! I just care about order, I don't care about proof theory. But if maximum extending ordinals are actually the same as proof-theoretic ordinals of well-quasi-ordering statements, then I guess there's more of them out there than I thought? IDK, I am a bit skeptical of this. But logic -- like, proper logic, as opposed to order theory like I like to think about -- makes my head hurt... I'll probably just not look into this for now...

Edit again: Hold on, shouldn't the proof-theoretic ordinal be *greater* than the maximum extending ordinal? Apparently not, but... blargh. I'm going to ask math.SE about this.

Edit a third time:: Ha! So one of the people who proved the proof-theory statement mentioned above was... Andreas Weiermann! He's certainly familiar with the theory of maximum extending ordinals. The paper even cites Schmidt! It *doesn't* mention a connection between the two notions, though, leading me to suspect that none is known (although it's from 1993).

You know what? I'll skip asking math.SE (or really, MathOverflow, this is seeming more suited to there) for now; I'll just ask Weiermann himself in July...

So, OK, before I get to other things, I want to post a retraction here. (Not sure that I'm going to go back to relevant earlier entries and edit them.)

Previously here I've claimed to have proven the inequality that, for any ordinal α and any WPO X, one has o(Rev(α,X))≤o(Rev(α,o(X))). (And if X has an initial element, one has o(Rev₀(α,X))≤o(Rev₀(α;o(X))) -- it's really this latter claim I'm going to focus on.)

My claimed proof of this was wrong. I have not thus far been able to fix it. I still think it is true.

Note that none of this affects my formula for Rev₀(α;β) for α and β ordinals and multidimesional generalizations (and other variants) of such; these proofs (which I finally recently got around to writing up properly) are unaffected.

I have been able to recover the inequality in a number of special cases. It's easily seen to be true when α and X are both finite. My original proof basically still works if α is finite; and if α=ω, I can prove it as a corollary of Andreas Weiermann's work on the WPO of finite multisets of a given WPO. Meanwhile, a different proof works if instead X is finite, and I think I can extend it also to the case where o(X)=ω. In fact I think I can possibly go further and get it to work when o(X)<ω2. There are other special cases I've managed to recover too -- generally requiring that we take α<ω² and then putting conditions on the form o(X) takes -- but I'm not going to go listing them all here. Still, in general, I have not been able to recover it thus far.

One other special case I wanted to mention that I can recover is -- well, remember, the original reason I wanted to prove this inequality was to prove the following two inequalites, where ((α multichoose β)) is to be interpreted as o(Rev(β,α)):

((α⊗β multichoose γ)) ≥ ((α multichoose γ)) ⊗ ((β multichoose γ))

((α multichoose β⊗γ)) ≤ (( ((α multichoose β)) multichoose γ))

(These are companion to a third inequality, namely,
((α multichoose β⊕γ)) ≤ ((α multichoose β)) ⊗ ((α multichoose γ)),
but this one can be proven pretty easily without my conjectured inequality.)

Anyway, I can report at least that the two inequalities above are definitely true -- I proved it the stupid way, by computing both sides via my formula and then comparing. Still, this is definitely an unsatisfying proof, compared to the proof we'd obtain with a proof of my conjectural inequality above.

Well, at least the formula in the total case (especially in multiple dimensions) is quite noteworthy and will make a good paper on its own, assuming I can't recover the more general partial case!

EDIT 8/3: One tiny correction, see struck out portion below. Also, pretty sure I really have proved this now.

So!

OK, so it turns out that despite my big "EDIT: This entry is wrong" warning on my last entry, almost everything it is correct. Just, not quite for the reasons I thought.

My formula for "multidimensional natural multichoose", in the case of powers of ω, was indeed correct. What was not correct was the part I didn't write down -- what if the inputs are not powers of ω? In this entry I will describe the correct formula for this.

...OK, I say "correct" but in reality I haven't actually sat down and fully proved it. I'm pretty certain this has to be correct, though. If somehow I'm wrong, well, I'll put a big edit on this later. :P

So. Recall, we're given ordinals α₁ through α_n, and we want to compute the maximum extending ordinal of the poset of lower sets of α₁×...×α_n that are "strictly bounded in each dimension", i.e., none of the projections onto any of the α_i are surjective. (To ignore some stupid stuff, I'm going to assume all α_i are nonzero. You can rephrase the below so it's still correct even if one of them is zero, but I don't want to have to phrase it that way here.)

Here is what we do. First, we write out each ordinal in Cantor normal form; we're going to use the "weak" Cantor normal form, where exponents can be repeated but there are no coefficients. Each ordinal can be broken down into "segments" corresponding to the Cantor normal form, each of length a power of ω. Now, we're looking at the product of these ordinals, so this breaks up the product into finitely many "boxes"; again, the dimensions of these boxes are all powers of ω.

For ease of talking about it, I am going to place these boxes on a grid. Suppose that α_i has r_i segments. We will associate each box to an element of {1,...,r₁}×...×{1,...,r_n}.

Now, as per ancient mathematical tradition, we are going to take a (natural) sum of (natural) products (I'll omit the "natural" from here on out). (Indeed, if we were in 2 dimensions -- the case I'd solved earlier -- it would even be a sum over paths, with the value of each path being a product based on what it passed through. A wonderful mathematical tradition! Unfortunately, things don't quite work out that way in the general case.) The set we are going to be summing over is the set of lower sets of {1,...,r₁-1}×...×{1,...,r_n-1}. That's right -- we only want lower sets that don't use the highest possible coordinate in any dimension. Not unlike the problem we're trying to solve.

So for each such lower set, we need to get a value. What we're going to do is take the "frontier" of the lower set; to define that, let me introduce some notation. I'll use ε to denote the vector (1,...,1). A point p will be on the frontier of S if it is not in S, but p-ε is; or if p is along one of the lower boundaries (p has 1 among its coordinates), so that p-ε is "out of bounds".

So, are we going to take the product of values associated to the boxes on the frontier of S? Not quite. There's an additional restriction. For each point p, I'll define ε(p) to be the vector which is 1 in each dimension where the corresponding box is finite (i.e. has length 1), and 0 in each dimension where it's infinite. The box associated to the point p will only be included in the product if both p and p-ε(p) are on the frontier. (Note that if the box is infinite in all dimensions -- if it's "full-dimensional" -- then p-ε(p) is just p again.)

So now we can associate a value to each box included in our product. How do we do that? Well, write down the box's dimensions; let's drop all of them that are finite (i.e. 1), so we'll be looking at a box, possibly lower-dimensional, all of whose dimensions are infinite.

If the box has dimension 0, its value is 1. If the box has dimension 1, its value is equal to its length.

If the box has dimension 2 or more, its value is given according to the formula I stated earlier; if its dimensions are ω^β_1×...×ω^β_k, then its value is ω^{ω^g(β_1,...,β_k)}, where g(β_1,...,β_k) is given as follows:
1. If at least two of the β_i are infinite, or at least one of them is of the form ε+k where ε is an ε-number and k is finite, then g(β_1,...,β_k) is the natural sum of the β_i.
2. Otherwise, it is the natural sum minus 1. (And it is guaranteed in this case that the natural sum will be a successor, so you will be able to subtract 1.)

(Note how different the rule is in dimension 2 or higher from in dimension 1! In dimension 2 or higher, the value of the box always has the form ω^{ω^γ}; this is not true at all in dimension 1.)

(Isn't the rule about the value of a box of dimension 0 unnecessary, seeing as such a box can never be included in the product anyway? Yes... unless you're in dimension 0 in the first place. I'm a believer in including trivial cases. Yes. You could actually leave the value undefined; I decided not to, but whatever, it's arbitrary.)

So, to summarize: You sum over lower sets of the set of boxes, excluding the outer boundaries; for each lower set S you multiply over boxes p on the frontier of S such that p-ε(p) is also on on the frontier of S; and the value of a box is given by the formula above. Not too bad, really. Much simpler than the general rule for "right-multichoose", certainly!

---

Now that that's out of the way, let's talk about inequalities. Specifically, the inequality o(Rev(A,B))≤o(Rev(A,o(B))), where A and B are WPOs, and we assume that Rev(A,B) and Rev(A,o(B)) are also WPOs.

Previously, I had proved this inequality when A is total, by mimicking the proof of the 2-dimensional case of the above. I then claimed (in the entry below) that by iterating this, one could prove it more generally when A is a product of ordinals, rather than just an ordinal.

That iterative proof does not work. Fortunately, now that I know how to handle the multidimensional case, indeed I can say that it is true when A is a product of ordinals, by mimicking the proof of the multidimensional case.

But I've been able to prove some other nice special cases of this inequality as well -- ones dependent only on the values of o(A) and o(B). Unfortunately, the methods used here are seriously unlikely to extend to other cases. Still, a month or two ago I would have been surprised to make basically any progress at all on the case where A might not be total.

So, first recall that, for trivial reasons, it works if A and B are both finite. Also, using the stuff above, it's not too hard to see that it works if A is finite, and o(B) is a power of ω (although somehow I apparently missed this earlier).

But I've also got it working now if we assume that B is finite... and that o(A) is an initial ordinal. Yeah, that's a pretty restrictive condition. Oh well. It'll have to do for now. (Note that a WPO A with o(A) initial is in some sense "close to total". Though maybe not too close; you can have A with o(A)=ω₁ but Rev(A,2) not a WPO.)

In fact I've also got it working if o(B)=ω and o(A) is an initial ordinal. Or if we reverse it -- if o(A)=ω and o(B) is an initial ordinal. Unfortunately, I have not been able to "complete the rectangle" and get it working when o(A) and o(B) are both initial ordinals (unless one of them is ω, obviously).

Still, considerable progress! Maybe this inequality really is true in general. Or maybe I just haven't been clever enough in trying to come up with a counterexample. Well, we'll see -- hopefully, anyway.

-Harry

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 S^k 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 λ^m(λⁿ(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 h_k(ω^α_1,...,ω^α_r), where h_k is a complete homogeneous polynomial. (If you replace h_k here with e_k, 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.

-Harry

Well, it's time for me to declare a big "oops".

My paper Transfinitely iterated natural multiplication of ordinal numbers was recently rejected from the Notre Dame Journal of Formal Logic, and for good reason.

The mathematical assertions aren't wrong. But contrary to what I said, it's actually quite easy to prove Jacobsthal's distributivity law by transfinite induction, and I entirely missed this. My thanks to the anonymous referee for pointing this out. The referee also claimed this is true of my theorem that a^⊗(b⊕c)=a^⊗b⊗a^⊗c, which I haven't yet checked, but is presumably also true.

EDIT Nov 12: OK, now I'm confused. I've tried to check it today, and... all I could get was an inequality. I'm not sure what to make of this.
EDIT Nov 13: OK, I figured out the mistake, disregard the above.

This cuts out a lot of what I said; I'll have to rewrite a lot! It also turns it into, well, more of an expository paper. I mean, I think it's some good exposition; I would still really like to see it published somewhere, because it summarizes and connects up some things that haven't been connected up elsewhere. But I'm going to need to find somewhere else to publish it, that's for sure.

Mind you, there still is the problem of finding an order-theoretic proof of these laws. Of course, that first requires an order-theoretic interpretation of a×b (Jacobsthal's multiplication) and a^⊗b (super-Jacobsthal exponentiation).

But the former of those now does in fact exist! Take a look at this paper: Some iterated natural sums, by Paolo Lipparini. It gives an order-theoretic interpretation of the infinitary natural sum, and therefore, implicitly, Jacobsthal multiplication.

This order-theoretic interpretation does not make it immediately obvious that a×(b⊕c)=(a×b)⊕(a×c), nor that a×(b×c)=(a×b)×c; but just having an interpretation at all is a huge start. I have written to Lipparini and he agrees the problem is interesting.

One thing worth noting about this order-theoretic characterization of a×b is that while it makes it obvious that ab≤a×b, it doesn't make it obvious that a×b≤a⊗b. Of course, what Lipparini did wasn't meant specifically as an interpretation of a×b at all, but the generic infinitary natural sum, where you can't assume that all the summands are the same. It's possible that for the specific case of a×b, one might be able to find a reformulation of his characterization that does make this obvious. Of course, proving that this reformulation is the same might be far from easy! Who knows.

So, that's the state of things. Guess I've got quite a bit of work to do... (Well, I guess that's true regardless. In fact I might want to put off fixing this for now to get more writing up of integer complexity done.)

-Harry

So I have a number of neat things to report about ordinals! In order from least to most exciting:

#1: I can now compute big multichoose, in general

At least, I'm pretty sure I can prove it. More on this in a moment.

(Unfortunately, this means I have no "easy math" I can work on right now -- I need to get back to the hard math, y'know.)

Hm -- I just looked and saw I never defined "big multichoose" here. In short: If α and β are ordinals, we can consider the poset of all weakly decreasing functiosn from β to α; this is a WPO, so we can take the largest ordinal extending it. This is what I mean by "α multichoose β", which I will denote here as ((α|β)) because what else am I going to do.

Point is, I've been puzzling over it for a while, working out special cases, because for obvious reasons this is quite a bit harder to compute than left and right multichoose from earlier.

#2: There really, really, is no natural exponentiation

In appendix B of my ordinal arithmetic paper, I showed that there's no operation satisfying several desiderata that we'd expect of a "natural exponentiation". However, one of the desiderata was a bit less, uh, to be desired than the others. But I've now managed to eliminate the dependence on that hypothesis! Best of all, the new proof is only a slight modification of the existing one. The super short version is, instead of defining f(n) = deg e(n,ω), you define f(n) to be the "leading coefficient" of deg e(n,ω).

I'll update the paper shortly -- I'll also need to notify the journal I submitted it to about the update...

#3: Big multichoose is related to the surreal exponential!

Don't ask me why -- I don't actually understand the surreal exponential at all. But it totally is! The thing is, this doesn't actually depend on any of the new stuff in #1; what's related to the surreal exponential is the rule for computing ((ω|α)), or rather ((ω|α))₀. (I'm using the subscript 0 to mean that I'm restricting to functions which are eventually 0.) It turns out for α a limit ordinal,

((ω|α))₀ = exp(α)

where exp is the surreal exponential.

Again, I don't have any idea why this is so, I just noticed that the rules for computing them are the same. I didn't notice it before because I hadn't written the rule for computing the former in a way that made it obvious.

So let me go into more detail about #1 now -- the final piece of the puzzle was figuring out how to compute ((ω^α|ω^β))₀ for α,β>0. What I eventually figured out was that this is equal to ω^{ω^G(α,β)} for a certain function G. Specifically, G(α,β) is equal to α⊕β if either α or β is of the form ε_γ+k for some ordinal γ and some finite k, or if both are infinite. Otherwise -- if one is finite and the other is not of the form ε_γ+k -- then instead you get (α⊕β)-1, which necessarily makes sense since one of them is finite and nonzero.

Now, Harry Gonshor, in his book "An Introduction to the Theory of Surreal Numbers" -- where he defined the surreal exponential in the first place -- showed that there's a function g such that for a surreal number α>0, exp(ω^α)=ω^{ω^g(α)}, and showed how to compute g. Of course, we only care about the case where α is an ordinal, not just any surreal. And in that case, g(α) is equal to α+1 if α is of the form ε_γ+k, and is equal to α otherwise.

See the similarity? G(1,β) is exactly equal to g(β). And from this follows the equation above.

Now as I said this only requires knowing how to compute G(1,β), i.e., how to compute ((ω|β))₀, which I already knew how to do. But I didn't notice the similarity until I wrote it in this form depending on G. And I wouldn't have written it that way if I weren't trying to determine ((α|β)) more generally. So there is that bit of relation there. I determined the form of G, and then noticed that G(1,β) reminded me of the rule for g(β); and I ran to the library to look it up, and indeed it was the same.

So yay! That's finally solved. Now back to harder math, I guess...

-Harry

So!

I just learned from a discussion on Wikipedia that Jacobsthal multiplication was rediscovered in the 1980s by Conway. Possibly because they didn't have Wikipedia back then, he didn't know it was originally due to Jacobsthal. As far as I can tell, this rediscovery resulted in only two papers: One by Harry Gonshor, and one by John Hickman, both of which explored the arithmetic of this multiplication.

I think I'm going to go edit references to these into my own paper on the subject now. The history deserves to be connected up!

-Harry