So my computer has come down with a sudden case of "won't turn on". Not won't boot, not won't POST, but won't turn on. I put it in standby and it wouldn't turn back on. Took out the battery; no use.
I've turned it in to the local repair shop (Beagle Brain). I figure something like this should be pretty straightforward. I assume the hard drive should be fine, but I do have the most important stuff backed up to as of last week.
I don't have access to what I'd started writing of the well-ordering paper, so I can't show Jeff the horrible definition I wrote the other day... oh well, he doesn't seem to be around anyway...
-Harry
and this is what popped into my head:
"You like trees, you say? No. You don't like trees. You like trees that stay within reasonable limits and don't endanger anyone. But there's no such thing as a tree that stays within reasonable limits. Oh, there are trees that happen to stay within reasonable limits, sure, but how can you ensure this beforehand? You can't -- a tree is a mindless thing; it knows nothing of your notion of reasonable limits. And it it did it wouldn't care and you couldn't bargain with it. No matter what you do, it will always threaten to outgrow your reasonable limits, and then what will happen? It'll come down to leaf cutters and chainsaws, that's what. Trees don't understand any language but force. They're barbarians. What would make you think it's a good idea to deal with them?"
...this may be the result of too much time on LW. Or maybe Durkon might say something like that...
-Harry
Yesterday I went with some of the math people (Hunter, Ari, Dave) to trivia at one of the bars around here. I do not like bars but I do like trivia, and the noise level was tolerable so yay.
Hunter had been reading about Dieudonné modules and as an exercise was trying to come up with a nontrivial example of one. He thought he had one but of course we didn't have paper so on the way there we were arguing over whether his construction worked. (It did.)
The point is, when it came time to name our team, someone suggested it would be really funny to name our team "Dieudonné modules" and see if the announcer could pronounce it. I protested that this was kind of mean, but I didn't have anything better and we went with it.
The first round had a number of really easy questions. Now, the format was that the bulk of it consisted of 10 questions, and for each question, you got to pick how many points it would be worth, from 1 to 10; you couldn't repeat them. So when they asked what country Mt. Fuji was in, we immediately wrote down Japan, 10 points. Well, that was stupidly easy. Everybody's going to put down 10 points for that one, aren't they? And hold on wait why is the slip still on the table? Holy crap we never actually turned it in! Ari, run!... nope.
Of course, we just reassigned our 10, meaning we only lost 4 points because of that, but it's still a bit embarassing. (And no, an extra 4 points would not have been enough for a victory.)
More surprising: I encountered Karen Schroeder from high school[0] there, who apparently is at Michigan studying bioengineering now. I had no idea. Neither did she; she recognized me when I turned in an answer and came up to say hi; of course, I pointed out that Dave was also here. I guess she must have been more surprised than we were.
Her team was called "Bob Loblaw's Law Blog", but the announcer didn't have any trouble pronouncing that, unsurprisingly. However our name worked better than expected -- the first time he had to read it, he explicitly said that he couldn't pronounce it, and resorted to spelling it out. Later he came up with a decent approximate pronunciation...
Last question of the second round asked, there are three TV shows that ended their run on top of the Nielsen ratings. Name two of them. Well -- we got the other one wrong anyway, but one of the ones we said was M*A*S*H, and apparently that wasn't one of the answers? Karen's team did the same. I am very confused by this; I think they must have gotten it wrong, not us...
-Harry
[0]I forget, did she do Quiz Bowl back then? I really don't remember yes or no.
(I should probably actually be writing this well-ordering paper, but, eh.)
So I'm getting the idea that most people really do not understand the idea of... competitive gaming, I guess, is the term I'm going for here? You know. What David Sirlin's "Playing to Win" is all about.
What inspired this post was a section in the Wikipedia article on the game Abalone. (Linking to the current version in case that section gets removed later.) Namely, the section on "avoiding draws".
Apparently the game has a problem in that it is far, far easy to defend -- not just easy to turtle for a long time, but to actually defend indefinitely without penalty, preventing the game from ever ending if both players do this. Therefore, says the article, "serious Abalone players tacitly agree to play aggressively."
No! If you do this, you are not a serious player of anything, because you apparently don't even understand what that means. The only correct solution is to fix the rules of the game, not tacitly agree to anything. Fortunately, in this case, there is apparently an easy fix, by just changing just the players' starting positions and not the other rules at all.
Point is, OK, I wouldn't be surprised to learn that many people don't really understand competitive gaming; but a sentence like that stated about serious players of... aaagh.
Let's talk about Bridge. Bridge bugs me.
Recently Bridge seems to have replaced Dominion among my friends in the math department (and just when I'd actually started hanging around there more often, dammit). OK, more recently several people have been writing this puzzle game, which is taking up the time when they would otherwise be playing games, but before that it was Bridge.
(I am glad to finally understand where the whole "5-card majors" convention comes from. I hadn't regularly played Bridge since high school, when I used to play with Chris Howard and his group, and they didn't use that convention which apparently everyone everywhere else does, it seemed really arbitrary to me. Now that I understand that Bridge bidding is largely about making game if you can, it makes sense.)
Anyway I'll play Bridge but... it's kind of a silly game, you know? No, I'm not actively trying to break it, but I feel bad playing even at a low level games that I know don't really work at a high level. Here are some things I am told about Bridge tournaments:
1. You have to register your bidding convention; your opponents can see it. See, Bridge is not a game about communicating encrypted information to your teammates, so your opponents have to know what your bids mean. (And you adhering to your bidding convention is delineated how?)
2. The "forcing pass" convention and other "highly unusual methods" are banned. Again, without a way to delineate whether you're even adhering to your bidding convention, this makes no sense.
3. Because of #1, if your partner makes a bid which does not make sense to you, you are supposed to say "alert", so your opponents know this. I mean... what??
I mean, this is just silly. People can play it all they wan't but I can't accept the legitimacy of such a tournament. Real games have real rules[0].
Of course, #1 is not necessarily such an inherently ridiculous idea... if you don't have humans doing the bidding. How about, instead of having people actually do the bidding themselves, they write beforehand an algorithm to bid for them -- i.e. they write a fully defined bidding convention they are adhering to, and we can see they are adhering to it because they aren't doing the bidding themselves, it's being done automatically via the program they wrote. (Let's assume that after a certain timeout period it's automatically a pass, and that all bids are artificially delayed to this timeout period so no information is conveyed via timing. Also, presumably partners are required to use the same program?) And -- here's the thing that preserves idea #1 -- as inputs this algorithm gets not only your current hand, the bidding so far, vulnerability, etc., but also the source code of your opponent's bidding convention, so you know how to respond to it. (Hm... standardizing a language is blech. Or just use the binary and have your program run tests on it to see what it's doing?) Boom! Idea #1 is now preserved.
(There do exist computer Bridge tournaments, apparently, but I don't know how they work; no idea if they actually use the idea I suggest, or if they do something more usual and iffy. And of course, I'm suggesting computers would only do the bidding, not the actual card play, but that's perhaps the smaller difference...)
With that now made into an actual rule, it may even be possible to make rules that actually discretely delineate what sorts of conventions are and aren't allowed, though the test would have to be a finitary one. Wait, that's no restriction at all -- Bridge is inherently finitary, since the length of bidding is bounded. So this would be possible, if very slow. Alerts, I think, should just be discarded -- you're just adding another information channel to be abused, and anyway, automating it already serves the function alerts would serve.
Anyway. I guess there were multiple points there. I think I'll end this here.
-Harry
[0]In addition to Playing to Win, let me also point out the following articles on Less Wrong, about a different sort of "real rules": Universal Law, No One Can Exempt You From Rationality's Laws. A different sort of thing, but there's a unifying idea here, in that they're all absolute rules. I have to wonder if perhaps many people only know the sort of social and/or leaky rule/law as the only sort of rule, and thus don't quite realize that these are distinct from truly absolute rules, a category which includes not only physical and mathematical laws, but also the rules of a well-defined game. But that level of incomprehension seems impossible; I think most people must at least grasp the absoluteness of mathematical laws. Then again, maybe not -- there seem to be a lot of people who think of mathematics as directly talking about physical things, rather than being something we use to model them, and try to exhibit physical counterexamples, not realizing they're only showing that the model is wrong, not the mathematics. Of course, if you trust your model enough, this sort of thing can be strong evidence for a mathematical claim (e.g., in the extreme case, "How to Convince Me That 2+2=3"), but most people making these sorts of claims don't seem to realize that distinction.
It worked!
Time it took Jānis Iraids to compute ||n|| for n≤1012, and thus verify ||2a||=2a for 1≤a≤39, presumaby with access to a supercomputer: 3 weeks[0]
Time it took me to verify not only that ||2a||=2a for 1≤a≤40, but that ||2a3k||=2a+3k for a≤40 and a+k≥1 on my laptop: 12 minutes.
Hooray for better algorithms!
Of course, none of what I've written here is verifiable until I've posted the code, but first I want to reorganize it, add some additional features, and ideally actually make it readable...
(I'm also going to hold off on more computations till then, as one thing I'd want to do is add an "indefinite" mode where you can just cut it off at any point, so I don't have to decide beforehand how high to compute up to...)
-Harry
[0]Source: I asked him on Twitter. I didn't ask about the computer used.
I am quickly becoming convinced that when it comes to representing quantities whose exact value is not known, the ± way of representing intervals (as opposed to explicitly listing their endpoints) encourages sloppy thinking. It implies that the center point and the radius can be operated on independently, which often they cannot. Obviously it's a natural way that intervals arise, but once you start doing operations on them, it makes less sense.
-Harry
I am bored and waiting for my laundry to dry so here's one from the entries-to-write file.
Everyone by now is familiar with the misuse of "literally" as just another intensifier; lots of people complain about that. I'm going to complain about something different. In these cases, though, I will admit that I don't necessarily have a good substitute to hand, and such abuse of the word "literally" may be the best option.
Annoyance #1: Use of "literally" to mean "etymologically". As if more recent senses of a word were not literal. Actually, in this case it's hard to really draw a line and say "no, this is wrong", for the simple reason that extension by metaphor is one of the basic ways words gain new meanings, so what is now merely "etymologically" really once was "literally". So I'll admit this is not really the most sensible complaint. (I think I've seen cases that really cross the line, but I don't have any to hand.) Actually, I said above I don't have a good substitute, but in this case I think one could use "in the original sense" without losing too much of the impact.
Annoyance #2: This is the bigger one. Use of "literally" to mean "in a particular narrow sense (which need not be the literal or original sense of the word)". Here's an example which particularly irked me, from one of the speakers when I finished undergrad: she spoke of how she came to the US and everything was different; all the electronics were the wrong voltage; she had to adapt -- literally! Now, it's true that converting electricity from one voltage to another is a literal sense of the word "adapt", but it's not a particularly literal sense of the word, it's certainly not the older sense of the word. While "literally" and "etymologically" may not be exactly the same, they're related as mentioned above, and so if you single out as literal a meaning that is already literal, I would say you are definitely implying it is the original sense of the word. Which here it is not, and that really bugs me. In this case I really don't have a good substitute to hand, though.
-Harry
What with the conclusion of writing this first paper (gods willing) -- and the end of classes -- I have some brief time to actually do some *thinking* about integer complexity again before Jeff makes me get started on writing the next one[0]. (I believe much of what I am thinking about has already been solved by Juan Arias de Reyna, but I will read his solutions later; first I want to think on this myself some more.) Sorry, no details right now -- well, unless you think you can infer them from the rest of this post!
In earlier drafts (that included material we definitely did not have time to cover in this first paper) I defined a class of ternary families I called "primary ternary families". I am thinking now this was not such a good name. (Also, people keep telling me "ternary family" is a terrible name, and I assume they're probably right, but since right now I'm just talking about naming things for the purposes of my own thinking, I'm going to ignore that right now.)
Rather I am thinking that would be a better name for a slightly more general class of ternary families. (The old meaning is still important, but slightly less so.) But I've used this name long enough that I would have trouble switching it over in my mind. And perhaps a more suggestive term could be used, anyway.
The intutition is that these "primary" ternary families are somehow bulky or substantial. And with the more restricted meaning, they're even more bulky. I like the idea of calling "bulky" what previously I called "primary". But what about the more general class? "Substantial ternary family" is a bit of a mouthful. "Meaty?" No, that's a little too out there. "Solid?" Unfortunately, we ended up using "solid number" to refer to additively irreducible numbers, so that's out. Though maybe we can still change that back to the term we were using previously -- we called such numbers "chunks". I still like this better. Actually, so did Josh, but Jeff had problems with it and we decided it was more important to get the thing done than to bikeshed about the term. But I suspect Jeff slightly misunderstood how we intended to use the term, so perhaps if that is made clear he will change his mind.
Yeah, I think I'll stick with "substantial". (Anyway, these things might well end up as polynomials, and "substantial polynomial" is not so bad to say.)
-Harry
[0]Also some time to do some more coding on the classifier, which is most of what I've been doing. The core of it has been done for a long time, of course, but it still needs to be changed to use exact arithmetic, and I'd also like to add some additional output capabilities. Like maybe, "enter a real number (in a format I can work with), get back the order type of defects up to that real number". I don't know if I'll actually implement that one. Computing order type is straightforward from the existing core tools, of course; it's the reading in a real number in a potentially quite general format I find daunting. :P But I guess I can always just implement the actual function itself, and then say "open the program up with ghci if you want to use these additional features"...
Here's a revised version of Numbers with Integer Complexity Close to the Lower Bound, resubmitted over the previous version posted here. I guess that one's gone from the internet now, since I uploaded this one to the same URL, but that can hardly be called a loss. Mostly just typos fixed, but also a small gap in the proof of the main theorem. Many thanks to Juan Arias de Reyna for going over the paper so thoroughly.
-Harry
Holy crap! I just went on Kongregate again (was bored) and card challenges are back! So presumably they're actually supporting Kongai again, which means people will be playing it again, which means time for me to start playing it again!
Now what's the likelihood they'll actually fix the Sandstorm bug? :P
-Harry (hoping to get that second General's Insignia... I assume I didn't miss it...)
EDIT: Argh. I forgot Flash in Linux is screwed-up these days (is there any way I could go back to the old, consistently working version?). At least, this is true in Firefox under Ubuntu. (Reinstalling Flash hasn't helped; I've tried repeatedly in pretty much every way.) Crap. I am not going to let that stop me...
EDIT again: Nevermind, just had to uninstall Gnash first. Well, that was silly. Yay, working Flash again...
EDIT yet again: Oh -- apparently this isn't going to be a regular thing. Started in March, it seems, but they're not doing it every week. Oh well, it still might draw in a few new players -- and evidently there must be enough playing it currently that they find it worth their time to do this...
Take a look at my homepage, you'll notice a new category there: "Problem dump". I've taken the two existing "problem dump" entries and reposted them there (with some editing for context). Of course, in order that I would not have to do *too* much editing, I explicitly labeled the section as "informal, bloggy writing" so people would know what to expect...
-Harry
Well, essentially done. We'll have to see what the referee says the second time around. And of course this is only the first of, what, five papers now?
For now I've just put it up at http://www-personal.umich.edu/~halt
So, yeah -- a lot had to be cut out in order to keep it at a reasonable length. In there is Josh's method, computations up to 12δ(2) (did I mention we're denoting defect of n by δ(n) now?), proof that 2213k works, and proof that Ak(x)=Θ((log x)k+1).
Gone are the formulae for Er(k), and long gone is anything related to well-ordering. Those will have to wait. (This is part of why there are so many papers now.)
Now Jeff wants me to get started on writing the well-ordering paper like immediately... oh well...
Addendum: Heh, Jeff has already emailed me with a few typos. Now fixed in this version. We'll see if the referee catches them.
Further addendum: OK, let's not turn this into a "point out the typos" thread. I've found more since then and I've been correcting them as I find them...
-Harry
Karlis Podnieks's groups has finally gotten around to writing up their results!
There's a lot of scattered stuff in there; I haven't read most of it. For those of you who haven't seen any of this before -- well, and who care about this -- I think Kaspars Balodis's upper bound on ||2n-1|| is definitely worth noting.
(As for us -- well, the first paper is, at long last, pretty much done. Now Jeff wants me to get started on writing the next one like immediately... oh well...)
-Harry
Some time ago Nic and I were playing Zendo with MVK as master. It was clear that the rule had to do with orientation and color but we couldn't quite get it.
Nic had an insight: "All pieces of the same orientation (flat, upright, weird) must be the same color," he guessed.
This wasn't right, but it seemed we were pretty close. The same thing, except the distinction was two-way -- upright vs. non-upright? Or flat vs. non-flat? No, groundedness has to do with it too. Perhaps the categories are ungrounded, grounded flat, and grounded upright? (With grounded weird not mattering at all.)
It was clear that the rule had this form, but after more and more counterexamples and more and more ad-hoc dividing the ways the pieces could be grounded and oriented, MVK decided to just tell us: It was that any two pieces that were touching the ground with the same parts had to have the same color. That is to say, if we explicitly enumerate the classes this creates, we get
1. grounded upright;
2. grounded flat;
3. grounded weird, balanced on a base edge;
4. grounded weird, balanced on a long edge;
5. grounded weird, balanced on a base vertex;
6. grounded weird, balanced on its point;
7. ungrounded.
So, y'know, if a master in a game of Zendo ever pulls that on you, now you have the concept available.
-Harry
So it came out the other day the people who hang around Julian's office (Julian, Hunter, Jordan) have a Harry-Nic scale of people. See, I'm one end, and Nic is the other. Intermediates on the scale go Harry-Julian-Hunter-Jordan-Nic. (There was some discussion that Emily Clader might be even more to the Nic side of the scale than Nic himself, but I don't think any consensus was reached there.)
I objected that Nic and I can hardly be considered opposites. Well, I was told, the scale only applies to the ways that you and Nic are different.
The others then attempted to see if they could describe just what it was a scale of, but all their attempts failed (in that they caused reversals of some of the comparisons); eventually they concluded that this was a foolish exercise in verbal overshadowing[0] and left it at "the Harry-Nic scale".
What really bugs me is that in their attempts at verbal descriptions, I'm not sure which end of those scales I was supposed to be on.
-Harry
[0]I introduced this term to Hunter last week. His initial reaction after "that's a really useful term" was along the lines of "Oh no! It's overshadowing my pre-existing verbal-overshadowing-like-concept!". It took me a bit to convince him that this was not a real problem.
It went more or less something like this:
[Zach, Anne, and I are cleaning out the TV room.]
Anne: So much shit builds up here, because people never throw anything out! Look at this cable. Will we ever need this? What is it?
[One end has a standard two-prong plug, and is a little bulky, like it contains an adapter. We can't see the other end at the moment.]
Zach: Well, evidently it's a charger.
Anne: But for what? What sort of device could this plug into?
[She displays the other end. It doesn't look totally unfamiliar, but I certainly have no idea what it might be called or what it might plug into.]
[Beat]
Zach: Oh yeah, that's USC.
[Anne, annoyed, leaves to go do something else. I start giggling.]
So here I am in Chicago.
I've been staying with Colin and Aviva, far to the north of anywhere I ever went when I was in school there. (It feels weird to have downtown be south of me.) Today after two days of doing not much but wandering aroud, internet, talking to Colin and Aviva and playing with Prince Myshkin (their cat) I decided to go down to Hyde Park and wander around there instead. (OK, and sleeping off headaches. Getting a headache two days in a row while here is annoying; I could at least get work done otherwise!)
(Also Colin and I played Twilight Struggle on Tuesday, him as the commies, as usual. I lost quite badly, although the cards and the dice were really against me... if you make that many realignment rolls at -1, you should succeed with more than two of them! I'm leaving Saturday so hopefully we play another game before then... switch sides for once. Also Wai Lee came by briefly but no we did not play Bean Game[5].)
Anyway! Notes from wandering around Hyde Park:
Happened to encounter Jack and Sarah just as I got to Pierce Tower. Well, actually it was Hannah I encountered first. She didn't remember me, actually, though Sasha did. Still, seems Hannah is less shy now, as she was willing to tell me about how she's in 1st grade now and likes to read even so. Also Isaac, being 3 years old now, no longer looks just like Sasha. He's quite friendly, like she was, though.
I think Nikita is the only person I know left in Tufts House (aside from Jack and Sarah and etc.), and of course I only know her from the week I came to visit two years ago, I never actually overlapped with her. Didn't encounter her though. (Well, OK, apparently Isis also still lives there...) I guess next year that'll be it -- I doubt that Jack and Sarah will be staying another year. Only other person I've encountered down in HP that I know at all is I passed by Yola on the street -- took me a bit to even recognize her; I didn't bother hailing her. (And there is a guy sitting here in Grounds who looks vaguely familiar, but that really doesn't count.) I wonder if Watson still lives in Thompson? I didn't think to go up there; I'd come to see Tufts House, after all.
Still, some traces remain, though not what I expected. I had thought Charlie's quoting of me in the study lounge would still be there, seeing as how people had previously put it back after it had been erased[0], but instead over the door is some new graffiti. What does remain, surprisingly, are some quick notes Peter and I made (in pencil!) on the wall of the lounge: a diagram 0→A→B→C→0 marked "this sequence is NOT exact"[3]; the note "y=10-24"; a statement of deMorgan's laws.
I forgot to check whether Kate and Girl Alex's galaxy ("the Girlalexy") is still there on the ceiling.
Glad to see Smash being played again (Melee, specifically). It seems we have 4 TVs now -- I warned them that would happen! Two of them are where the old main upstairs TV used to be, flatscreen and aligned with the wall, making a lot more room there. The old one with the bad connections is finally gone.
The house has a Harry Potter theme this year. Whatever happened to us just being Slytherin, I must wonder?
Someone had illustrated Ceva's Theorem on the study lounge board, which I found amusing. (Recollection: I am telling Youlian about how some of the math I learned on math team I have never had reason to use since, with the obvious example being Ceva's theorem. He doesn't know the statement, so I illustrate it. Peter walks by and sees the drawing -- "Ceva's Theorem? Why are you talking about that?") The lounge blackboard was empty so I left a note about asking "WTF is Ceva's theorem doing on the board?" and saying I was surprised to see Peter and my's notes still on the wall (but perhaps not as surprised as Peter would be to see Ceva's theorem on the board). I signed it just "Harry"; that ought to be enough.
Other notes:
I was thinking as long as I was in Hyde Park I would go see this Clarke's Diner, but I've been walking around enough today and it's not so close. The center of the quad is now closed to cars. The area in the center of the Reynold's Club quad now has little walls around it? Like knee-high, maybe. The robot library is now complete; it's not a separate building, you enter it from the Reg. Maybe I should see if my ID would still be accepted? I didn't think so but I was able to sign onto the network, and I do still have it. I tried taking a picture of Dererrer[4] near some of the ducks at Botany Pond, but there wasn't enough light.
I think that's all for now. I do hope Colin and I will have time for that second game...
-Harry
[0]"The real world is sucks!" That sentence got a little mangled, and I'm not sure why it was quote-worthy, but Charlie insisted on putting it up there just as I'd said it.
[3]The sequence I was originally referring to was exact, of course, Peter just threw that note in for fun.
[4]The duck Heidi made me.
[5]What I call Bohnanza.
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 ab, 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 ab, I wouldn't have a good parallel notation for semi-Jacobsthal exponentiation. In my own writing I've been denoting it by ab 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:
ab+c=abac. 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.
abc=(ab)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 ab+c=abac.
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)=ab×ac. 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.
So over on MathOverflow, Philip Ehrlich confirms that Gonshor's definition is the same as Kruskal's, and that Alling's definition is also the same as this except restricted to infinitesimals. Also, when people talk about surreal exponentiation, this is the definition they're talking about.
Which leaves the question of where the definition currently appearing on Wikipedia ever came from. Tracing through the history, it seems that whole section was added by one Michael K. Edwards. So I'd ask him, but seems he's on wikibreak till November. Well, actually, seems he hasn't been seen on WP since June of 2011... oh well, I'll put it on his talk page anyway... :-/
Addendum: Seeems that wikibreak notice has been up since 2006. Guess it's pretty unlikely he'll show up again. I suppose I'll just go and remove that section later...
-Harry
Navigate: (Previous 20 Entries)
