Chronicles of Harry

So!

I should really be working on writing up integer complexity stuff at the moment. But, the other day I noticed these old entries of mine on "ordinal multichoose" and I caught the bug again. Done thinking about this for now, back to real work now, but I wanted to make some notes on what I found.

First off, new notation. The notation I've actually been using can't really go in HTML; I've been denoting these operations α multichoose β, except inbetween the α and the β is a fraction bar, except the fraction bar is an arrow -- pointing rightwards for lexicographic order and leftwards for reverse-lexicographic. (Had to look a few things up to figure out how to typeset that in TeX.) There's also the choose version, though that's 0 if β is infinite.

Anyway. I'll use the notations ((α↑β)), ((α↓β)), (α↑β), and (α↓β).

So, definitions: For ordinals α and β, ((α↑β)) is the set of all weakly decreasing functions from β to α, ordered lexicographically. This is well-ordered. ((α↓β)) is the same, except the order is reverse-lexicographic -- as in, higher places in β matter more, not as in reversing the whole order! This too is (well-defined and) well-ordered. (α↑β) and (α↓β) are the same, but restricting to strictly decreasing functions.

Note that if you try to do something similar with increasing functions, there is just no way you get a well-order.

When I thought about these previously, I think I considered ((α↑β)) to be nicer than ((α↓β)), in particular because it's continuous in α, while ((α↓β)) is continuous in neither variable. But now I don't think of either of them as particularly nicer.

I will use (n|k) to denote ordinary choose, and ((n|k)) to denote ordinary multichoose.

I wrote down some recursions for them last time, but I missed a few. Well -- my goal here isn't to put all my notes up on LJ, that would be pretty boring. Note that some of the recursions only work if an appropriate variable is finite.

Anyway. I had several goals. One was to figure out how to compute these operations on Cantor normal forms. I did not succeed at that in general, because, well, that appears to be really hard. But! There are some particular nice cases. In particular, the ↓ operations when β is finite.

Say α=ω^α_0a₀ + ... + ω^α_ra_r + a, where I'm writing α in Cantor normal form, and separating out the finite part "a" as worthy of special attention. Then we have, for k finite and nonzero,

((α↓k)) = ω^{α_0 k}a₀ + ... + ω^{α_r k} a_r + ((a|k)).

Pretty nice, no? The choose version is the same, except the multichoose at the end becomes a choose. Unfortunately, once k becomes infinite, things become complicated fast.

Also last time I was trying to resolve the question, for k finite, does one always have ((α↑k))≤(α↓k))? (And the same for the choose versions.) I had thought this was true, and spent some time trying to prove it, but now I can report a counterexample: α=ω^ω+1+1, k=2. On the left hand side we get ω^ω2+1+ω^ω+1+1, and on the right hand side we get ω^ω2+1+1. At least, I'm pretty sure I calculated both of those correctly. It's also a counterexample for the choose versions; in that case, we get the same things but without the +1s on each.

So, there's that. But the big thing is... how did I not notice this before? There's a symmetry law! The two operations are very closely related!

With ordinary multichoose, we have ((n+1|k))=((k+1|n)), since both are equal to (n+k|n,k) (I write it that way, rather than (n+k|k), to emphasize the symmetry.) With these ordinal versions of multichoose, we get

((α+1↑β)) = ((β+1↓α))

The proof is pretty simple, too! As in, you can straight-up construct an order isomorphism between these. I feel a little silly for not noticing this, but, this is really cool!

I feel like this also indicates that ((α↓β)) is somehow the "more fundamental" of the two operations. Because, see, ((α↑β)), well, if α=0, we know what it is; if α is a successor ordinal, we can apply the symmetry law to express it in terms of ↓ and if α is a limit ordinal, well, it's continuous in α, so it's a limit of things that can be expressed in terms of ↓. With ((α↓β)), if α=0 we know what it is, and if α is a successor we can switch it around, but if α is a limit ordinal, well, we don't have anything like that. (EDIT next day: Although, ((α↓β)) is pretty easy to compute in the case where α is a limit ordinal -- see below. The successor case is the only actually hard case.)

So, yeah. Now to put that away (for now, anyway) and get back to work...

EDIT next day: Actually, let me say a bit more about the computation of ((α↓β)) that I left out at first. Say we write α=α'+a, where α' is either 0 or a limit ordinal, and a is finite. Then in fact this breaks down into ((α'↓β))+((a↓β)). And the first of these is easy -- if β=0 we know it; if β is positive and finite it's given above (just multiply all the exponents in the Cantor normal form on the right by β); and if β is infinite, it's also easy (multiply by β+1 instead of β). Problem is the ((a↓β)) part! That seems to be complicated. Well, by the symmetry rule above, figuring out ((n↓β)) is equivalent to figuring out ((α↑k)), but, well, you'll notice I didn't give a formula for that -- that seems complicated in general. It might be doable, though. (Note that for any given β, since ((α↓β)) is strictly increasing in α, one has ((n↓β))<((ω↓β)) which does at least mean that when you compute ((α↓β)), the purely infinite part and the finite part do not interfere with one another.)

-Harry

So, do you remember this old entry? Well, Jeff is having me turn it into an actual paper. We'll see if it's new; I think it is, but I should actually, y'know, ask a set theorist.

(At this point you may be asking: Wait, why is Jeff relevant? Didn't you, y'know, finish your degree? Yes, but he's continuing to help me out for the time being. Ordinarily he'd have me forge ahead with complexity-related stuff, but I said I could get this done super-quick, so he's OK with it.)

Anyway, in my previous exploration of the subject, I mentioned that continuing past exponentiation into tetration and general hyper is pretty stupid for ordinals, but I never explained why. I thought I'd do that here.

I could actually go into quite a bit of detail on this, because I spent quite a bit of time thinking about it a few days ago, but I expect people would find it mind-numbing so I'll keep this short.

(Note: I am not claiming anything in this entry is new, except the second-to-last parenthetical. And while that's new, it's also kind of stupid. :P )

So what's wrong with ordinal hyper?

Let's start with ordinal addition. This is built up from the successor operation. To compute a+b, you apply the successor operation b times to a. Note that the resulting operation is continuous in b, by definition.

OK, that was pretty simple. How about ordinal multiplication? To compute ab, you add a to itself b times. Now here we have a choice; when we say "add a to itself b times", what we really mean is "start with 0, then add a to it b times". But are we adding a on the left or on the right? It makes a difference!

The correct choice is to add a on the right. As long as b is finite, of course, this makes no difference. But addition, recall, is continuous in the right summand. Which would mean that if we were to take aω under this weird modified mutliplication, we would get a fixed point of left-addition by a. Multiplying by any higher ordinal would still get you aω. That isn't what we want at all.

Thus we have to add on the right. Similarly, when it comes to defining exponentiation, we have to multiply on the right. But what about tetration?

For natural numbers, we define tetration by doing our exponentiation on the left, and there's a good reason for this. (x^x)^x is the same as x^(x*x), which makes doing it on the right a bit silly. Addition and multiplication don't have this problem. They're associative, sure, but associativity of, say, multiplication, doesn't involve any operations simpler/smaller than multiplication. By contrast, this relation turns two exponeniations into an exponentiation and a multiplication, and in general (if you keep putting more exponents on the right) turns n exponentations into 1 exponentiation and n-1 multiplications. So this is not very good.

Thus when we try to generalize to ordinals, we have a conflict of which way things need to go in order to be nonstupid. If we continue to do things on the right, we run into the same problem we do for finite numbers. If, on the other hand, we break that convention and switch to the left, we run into the problem of continuity and stabilization. (We can't have "been on the left all along", or we'd have run into that problem even sooner!)

Now the reader may point out here that "left" and "right" are just directions, without any particular meaning, but in fact they have been used here with a consistent meaning: Left is what's getting iterated, right is the number of iterations. So this is indeed a real problem.

And so -- assuming we do switch to the left, because we want finite things to work -- we run into the continuity problem and things become stupid pretty quickly. Tetration is pretty stupid; hyper-n for 5≤n<ω is very stupid; and for n≥ω is maximally stupid.

(There is also the problem that H₄(0,ω) is undefined, but oh well.)

(Note, by the way, that if you're defining hyper so that things are done on the right, you should define H₀(a,b)=Sa, not Sb.)

(Also of note is the fact that while "ordinary tetration", "Jacobsthal tetration", and "semi-Jacobsthal tetration" all remain distinct, once you go to hyper-5, they all become the same.)

(Tangentially -- the other day I had the idea: while trying to define "natural exponentiation" using surreal exponentials doesn't work... what if you just rounded up to the next ordinal? Turns out, this is a pretty bad idea. No algebraic relations there that I can see.)

-Harry

Edit: Added a new paragraph pointing out that the two "coincidences" are in fact related (the first is used in the proof of the second). Later: Added the mostly-irrelevant footnote.

Edit next day: Fixed typos (natural mult is ⊗ not ⊕!); added clarifying footnote about 0 and 1.

So! Once again, let's review ordinal arithmetic. Ordinals have the successor operation; if we transfinitely iterate this, we get ordinal addition. If we transfinitely iterate this, we get ordinal multiplication; and if we transfinitely iterate that, we get ordinal exponentiation. One could keep going and get ordinal hyper but hyper has no nice algebraic properties so we won't be concerned with it here.

The ordinals also have the operation known as natural addition, denoted ⊕ (or sometimes #) which is defined by a different recursion. It is commutative and associative. Jacobsthal in 1907 defined a new multiplication by transfinitely iterating natural addition instead of ordinary addition; I'll call this "Jacobsthal multiplication" and denote it ×, as he did. He then defined an exponentiation by transfinitely iterating ×, which I'll call "Jacobsthal exponentiation", he denoted a^b, but I'll denote a^×b because... well, you'll see.

Finally there is natural multiplication, denoted ⊗ (or sometimes by a weird 16-pointed asterisk?), which is defined in terms of ⊕ by a different recursion. It is commutative, associative, and distributes over natural addition. We can, of course, transfinitely iterate this to get yet a third notion of exponentiation; I'll call this "semi-Jacobsthal exponentiation", and denote it a^⊗b. (Hence why I'm using the notation a^×b above -- if I called it a^b, I wouldn't have a good parallel notation for semi-Jacobsthal exponentiation. In my own writing I've been denoting it by a^b with a bar over the b instead of under it, but while that's easy in TeX I can't do that in HTML (unless I'm going to start pulling out the Unicode combining characters, and that wouldn't look right anyway if the exponent was more than one character long, as it frequently will be).)

(And yes, all these operations really are different. I'll leave finding examples to you.)

You could continue on to get additional notions of hyper, but again, this does not seem very interesting. (Sudden thought: I have not tested whether continuing on to tetration causes some of these operations to collapse. I should test that[0].)

So what algebraic relations do these satisfy? Of course for the ordinary and natural operations these are well-known, but let's do this from scratch regardless. I won't be giving any proofs (most of them are straightforward), just sort of heuristic reasons.

I'm going to leave out relations about how 1 and 0 behave as these are all obvious and exactly what you expect[3]. 0 and 1 are never problematic.

Ordinary addition:

a+(b+c)=(a+b)+c. + is just S iterated transfinitely; to start with a and apply S b+c many times, is to start with A, apply S b many times, and then apply S c many times.

Ordinary multiplication:

a(b+c)=ab+ac. · is just + iterated transfinitely; to add together b+c copies of a, is to add together b copies of a, and add to that the sum of c copies of a. Note this requires the associativity of ordinary addition, and the fact that ordinary addition -- being a transfinite iteration -- is continuous on the right.

a(bc)=(ab)c. To add together bc copies of a, is to add together b copies of a, and then add together c copies of the result. Note this requires a(b+c)=ab+ac.

Ordinary exponentiation:

a^b+c=a^ba^c. To multiply together b+c copies of a, is to multiply together b copies of a, and multiply that by the product of c copies of a. Note this requires the associativity of ordinary multiplication.

a^bc=(a^b)^c. To multiply together bc copies of a, is to multiply together b copies of a, and then multiply together c copies of the result. Note this requires a^b+c=a^ba^c.

Again, both these require the fact that ordinary addition and ordinary multiplication, being transfinite iterations, are both continuous on the right.

OK. So far so standard. Now for the next series.

Natural addition:

a⊕(b⊕c)=(a⊕b)⊕c, a⊕b=b⊕a. I'm just going to take the properties of natural addition and natural multiplication as given; I'm not going to try to explain them.

Jacobsthal multiplication:

This is where things get weird. One might be tempted to write down relations about a×(b+c) and a×(bc) like those above. However, while ⊕ is associative, and even commutative, it is not continuous on the right, which prevents such things from working.

That's not the weird part. The weird part is that, as Jacobsthal discovered, we can get a relation involving this multiplication anyway:
a×(b⊕c)=(a×b)⊕(a×c)

Yes, it's algebraically nice -- but what does it *mean*? Why should this be true? What does it mean to add something together b⊕c times? Unfortunately, I can give no really satisfying answer. Jacobsthal proved it by figuring out how to compute × on Cantor normal forms; this is pretty easy, and once you have that, it's a straightforward verification. But it seems very much like a mathematical coincidence, and that bugs me. If there's a better reason for it, I don't know it. (Of course, it's been 100 years since he discovered this, so there's a good chance this has since been resolved, but if there's a good reason it's certainly not obvious.)

Now, once we have this, it is pretty easy to get the relation:
a×(b×c)=(a×b)×c. What a strange operation to be associative! But it's a straightforward consequence of the relation above.

Jacobsthal exponentiation:

Continuing on, Jacobsthal found relations involving his exponentiation. These are straightforward consequences of the above:

a^×(b+c)=a^b×a^c. To multiply together b+c copies of a, is to multiply together b copies of a, and multiply that by the product of c copies of a.

a^×(bc)=(a^×b)^×c. To multiply together bc copies of a, is to multiply together b copies of a, and then multiply together c copies of the result. This requires the above relation.

So these are some pretty natural-looking relations... except for the fact that the first one, and therefore both of them, relies on the fact that × is associative! Notice neither of my heuristic justifications makes any sense if × is not associative. And × being associative rests on the apparent mathematical coincidence of it distributing over natural addition (on one side, anyway). (They also rely on +, ·, and × all being transfinite iterations and therefore continuous on the right, but that's not surprising.)

So. Let's take a look at the third series.

Natural multiplication:
a⊗(b⊕c)=(a⊗b)⊕(a⊗c), (a⊕b)⊗c=(a⊗c)⊕(b⊗c), a⊗(b⊗c)=(a⊗b)⊗c, a⊗b=b⊗a. Again, I'm just going to take these as givens.

Semi-Jacobsthal exponentiation:

This is where things get even weirder. Again, it's tempting to try to state a relation about a^⊗(b+c) or a^⊗(bc), but because ⊗ is not continuous on the right, this won't work.

But playing around a bit reveals the following surprising relation:
a^⊗(b⊕c)=a^⊗b⊗a^⊗c

Once again, algebraically nice, but leaving the question -- why should this be true? What does it mean to multiply a together b⊕c times? Once again, I can't give a really satisfying answer. I proved this by coming up with a rule to compute a^⊗b on Cantor normal forms, and then it's a straightforward verification. (I assume this is not original to me, but I was not working from anything else; I've only ever seen Jacobsthal's operations in that one paper of his, and I've never seen this operation anywhere.)

And not only that, but the earlier surprising coincidence is used in the proof of this one! Not in some sort of induction, because it wasn't done by induction, but because Jacobsthal product appears in the rule for computing a^⊗b on Cantor normal forms. (Because × is iterated natural addition, and when one performs a natural multiplication, the exponents of the ω's undergo natural addition.)

Let's continue on. From this we can then deduce
a^⊗(b×c)=(a^⊗b)^⊗c. Yes, that's Jacobsthal multiplication, not ordinary or natural multiplication! Because that's what you get when you iterate natural addition. This relies on the above relation (and the continuity of × on the right).

So these strange hybrid operations end up having some nice relations... but, it would seem, based on two mathematical coincidences. Two related and very similar mathematical coincidences. One alone would be a bit suspect; two would already be suggestive; these practically scream that there must be something going on here, some better reason for this that I don't know.

But I've no idea how I might investigate that (other than ask on the internet and see if anyone knows -- I'm certainly not going to study it myself). Back to writing this integer complexity paper...

-Harry

[0]Mostly irrelevant footnote: They all remain distinct at tetration, but I suspect they do collapse at the next level. I hadn't realized before that ordinal hyper actually is kind of silly for infinite ordinals due to continuity on the right. Lower hyper I suppose does not have this problem, if you wanted to look at that. Also I didn't realize that you have to exclude 0 as the left argument at tetration at above if you want the right argument to be infinite because it alternates between 0 and 1? Also it occurs to me I don't know whether, when both the level and the right argument are infinite, which limit to apply first, if it matters? Well, all this is really irrelevant to the main point.

[3]Well, except perhaps how 1 behaves wrt ordinary addition. While a+1=Sa, this doesn't work for 1+a. Rather, a+1=Sa if a is finite, and a+1=a if a is infinite. However it works fine with natural addition; a⊕1=1⊕a=Sa.

Oops next day: Not ordinary exponentiation. See below.

I've posted this whole mess as a question to MathOverflow. After all, I don't even really know surreals, I'm clearly not equipped to answer it! Nor do I have the time; I still have to finish revising the first of these integer complexity papers, except of course not till Tuesday because first I have a problem set for Schubert calculus.

But for those too lazy to click through the link... things are bad.

Note: To avoid confusion between ω^x in the usual sense and ω^x in the sense of the exponentiation under discussion, I'll write the former as ω^x and reserve superscripts for the latter.

Recall that Wikipedia's definition (I still have no idea where it's taken from, so WP will just have to take the credit for now) can be extended in one of two ways: By replacing "2" with other numbers, or by doing the usual thing with logs. These don't agree! And of course you could replace 2 with another number and *then* do the usual thing with logs, in your new base, to get an *entirely different definition*. Hooray!

(Why don't these agree? Well, as an example, consider that if we try to generalize by replacing the base, we still get 3^ω=ω, while if we try using logs, we get 3^ω>ω.)

In fact, the "replace the base" definition seems pretty suspect for another reason: it looks like if we plug in two ordinals, it agrees with ordinary ordinal exponentiation. Now I don't know, maybe ordinary ordinal exponentiation actually works really well with natural addition and natural multiplication. I haven't checked, after all, because I only just noticed this problem. But it doesn't seem very likely.

Oops: Not ordinary exponentation, but rather the analogue of that based on natural multiplication. The exponentiation without a name that Jacobsthal didn't consider...

In fact if we use Gonshor's definition, ω^ω actually won't be an ordinal at all. Disappointing, but perhaps to be expected -- if surreal exponentiation really did yield a "natural" ordinal exponentiation, I think someone would have noticed in the past 30 years. If we apply Gonshor's definition, and the various theorems he proves about it, we find ω^ω=exp(ωlogω)=exp(ω*ω^(1/ω))=exp(ω^(1+1/ω))=ω^(ω^(1+1/ω)).

So that's a strike against the idea of "natural exponentiation", unless of course ordinary exponentiation turns out to be suitably "natural". There is Jacobsthal's definition -- or you could do the equivalent but working from natural multiplication rather than his weird multiplication -- but, blech.

I mean, let's say you wanted to try to define it. If you try to define it recursively, powers of 0 will be a problem. If you try to define it "computationally" -- well, you can't raise polynomials to transfinite powers! That leaves the "constructive" approach, which, I don't know, maybe it's possible -- but part of what makes the other operations nice in the first place is the fact that there's multiple ways to think about them, not just the one.

In short, I'm leaving standing the question on MathOverflow (because really guys, why is this a big mess, this should not be a big mess, this should be answered), but there is probably no such thing as "natural exponentiation" (I don't count Jacobsthal's definition).

-Harry

So in the previous entry I asked the question, what the hell is natural exponentation, and does it agree with surreal exponentiation? This of course assumes that there is such a thing as "surreal exponentiation". After all, the surreals are always described as a place where crazy expressions like (ω+3)^√π make sense, so everyone has to agree what surreal exponentiation means, right?

Well, now I'm not so certain. There's a definition due to Kruskal and a definition due to Gonshor and I have no idea if these are actually the same. They both have the required properties. (Note these are definitions of exp, not of ^, but since both have exp being onto the positive surreals one can therefore easily turn this into a definition of ^.) There may also be one due to Alling? Oy... though that one at least seems to be similar to Gonshor's...

Then Wikipedia -- not citing any source -- lists a recursive definition of 2^x, which, I suppose, could be generalized to a^x by just replacing "2" by "a". Does this agree with the others? Again, no idea.

Let's note here something that doesn't fit in -- the function ω^x, commonly used in studying surreals, is *not* part of what I'm looking for. It agrees with the ordinary ω^x when x is an ordinal, and is not supposed to fit in with any more general notion of exponentiation; the above definitions of exponentiation actually do not agree with it. Wikipedia's definition of 2^x seems rather similar to the recursive definition of ω^x so maybe it agrees with *that* and ordinary ordinal exponentiation instead? :-/ But that would be a surprise -- though there have been some extensions of ordinary ordinal operations to surreals, but these are not actually well-defined on all surreals.

And then on top of that we still have the question of whether any of these agree with "natural exponentiation" -- whatever the hell that is!

Guess I can try reading the original German for an answer to that latter question, anyway. Well, once the people at the library get SpringerLink working here again...

-Harry

Edit: Argh missed some obvious things -- (α|k) and ((α|β))' aren't so terrible after all; I can indeed write down recursions for them. Entry now updated to reflect this.

Note: Last entry has been substantially revised since it was written.

OK. So last entry I introduced α^↓β and α^↵β, which are analogous to multichoose. I expect these have standard names, but I'm going to hold off on looking them up until I've worked out some more basics myself. We can also consider (α choose k), as well as the reverse-lexicographic version of that, which for some reason I didn't consider.

Also I want to use some different names because the above are too unwieldy for writing here in HTML. So I'll abbreviate (n choose m) as (n|m), and (n multichoose m) as ((n|m)). So I'll write ((α|β)) instead of α^↓β, and, uh, ((α|β))' instead of α^↵β; similarly (α|β) instead of (α choose β), and (α|β)' for the reverse version,. (I think α^↓β is a nicer operation than α^↵β, so the latter will get the prime. Similarly with why (α|β)' gets the prime.)

Anyway. Let's state some properties of these. Most are just copied over from last entry (with some variable names changed), but some are new:

( Properties! )

Notice how (α|k), and ((α|β)), can be expressed recursively via the above properties; we know the case α=0, the case of α+1 is given by the analogues of Pascal's Identity, and finally, both these operations are continuous in α, handling the limit ordinal case. I do not know of a similar recursion for (α|k)' and ((α|β))'; this, along with their discontinuity, is why I consider them less nice. Although ((α|β))' does have better monotonicity/cancellation properties than ((α|β)). Still, these I have had to come up with "tricks" for computing each time.

Addendum: Oops -- now included above are ways for computing these as well (more "Pascal's Identities"); they're not nearly as bad as I thought, even though they lack continuity. Thing is that you have to primarily recurse on β (or k), rather than on α. Of course, really both involve recursing on both...

Examples up to ω, as last time, but now actually correct (I hope):
( Examples! )

Questions I still have: Is (α|k)≤(α|k)'? For α infinite and k≥2, is this strict? Can an inequality between ((α|β)) and ((α|β))' be obtained if conditions are placed on the sizes of α and β? (Probably not.)

OK, probably about time I stop thinking about this and just look it up (i.e. ask math.SE...)

Addendum: But not before checking whether I can perhaps prove this via the above recursions, now that I have them...

-Harry