Chronicles of Harry

Oops, found one more such book. So now the bottom shelf isn't even clear-but-one anymore, but, still, we're getting there!

(There may actually be more such books, I'll have to ask Geoff, but...)

EDIT: There were. 8 more in fact, yikes. What a setback! So now we're back up to 242... (not 243 because one more got taken)

Edit again: Oops, make that 9 and 243...

So, I don't really do a lot of diary-style entries these days where I just talk about my life. A lot of that has moved into private correspondence, I guess. But I thought maybe it'd be good to say a bit about just what's going on generally.

Anyway, so, I'm not working at ConsenSys anymore -- they shut down Truffle, and, I had no desire to work on anything else there, so, well, I have a lot more time for math now! And other things, I've gotten back into Slay the Spire recently. :P

As for math -- Juan Arias de Reyna and I have uploaded a revised version of our paper together, and resubmitted it, this time to Michigan Math Journal, so we'll see what happens there, hopefully it finally makes it through!

As for WPO stuff... I still need to get back to the questions Andreas posed me back in March, that I was working on then. Problem is first I need to reload all that into my head! I could also finish up the strings paper, but, eh, I dunno, probably I'll get to that later.

As for the tree... hahaha oh my. I still haven't added those sequences to OEIS! But, uh, first... Ophelia came up with a way of extending these trees into the transfinite (although it involves no longer thinking of them as trees). I figured out what happens here when c=1. I haven't yet tried c=2, because, uh, I should really get back to the WPO stuff! But, um, I need to figure this out...

And yeah I still need to write to Steven Miller to ask for help determining what's original, but, eh, I'll get to that later. I also need to update my projects file, but that's not happening till I get through some of the other stuff above.

Anyway yeah I've gotten back into Slay the Spire! Not sure how much longer I want to stick with it, but seeing how far I can push ascension for now though. :) I did give up on going for the heart each time, that was just making it too hard. Currently I'm at Ascension 8 with Ironclad and Silent, at 10 with Watcher, and I just made it to 13 with Defect. We'll see how much further I can go there before I start losing too much and decide this is a waste of time. :P

OBNYC... OBNYC has something of a leadership problem I'm afraid. Itamar is treasurer now at least instead of me, but the group is still too dang reliant on me. My hope back in Spring that we could get more people who would be willing to be captain a bunch has largely not worked out. It's very annoying. Most of our other good leaders have left! Well, still hoping other unexpected people might step up... :-/

I guess people will want to know about the whole giving-away-books project. That lower shelf is now down to just 12 books until it's clear! Well, there's 13 on it, but I'm not counting "You Are Being Lied To", because that one is too big to go anywhere else. This was also true of "Sacred Mirrors", but I successfully gave that one away. :) And once that's clear (other than that one book) my intent is to switch from clearing shelves to unpacking shelves. (Which will be rather less satisfying, but it probably will be the right time to switch regardless...) There are 246 books left total, btw! Of course as before this is counting CDs and DVDs as books as well.

And uh yeah there's more I could say I guess, but I think I'll stop there for now. I dunno how often I'll remember to update here instead of just putting things in my letters to Shuo, but I'll try to occasionally?

-Harry

So the other day I was at the duck pond nearby and I took a picture of a duck, that, evidently feeling cold, had stuck its beak under its wing. I sent this picture to a bunch of people, including my friend Ashley.

Ashley: Post that
Me: The duck understands not
Ashley: Post that photo on your feeds
Me: He's not sure about "post" or "photo" but he's definitely interested in "feeds"

OK, I think I'm finally actually done with the tree stuff for now. I mean, I'm not done, I still have questions. But I think I have reached a point where I can finally rest and get back to other things! I have finall figured out a conjecture for what's going on for higher c. I guess I'll tell you about that here.

(I haven't yet proven it -- maybe it's actually easy, idk, but I am dead tired right now. I do have something of a heuristic explanation for why it should work. It also seems to explain every other phenomenon I've noticed about these trees, except for some ones that are easy to prove by other means.)

(And no I'm not putting this on the tree page. Too complicated and too far away from the original point.)

Anyway! I should actually state this rule. So the way I'm thinking of things, right, is that, we've got our tree, it's 0-rooted, it uses an additive constant of c>=1 (so R(n)=n+L(n)+c), and given n we want to predict L(n) without having to compute the whole tree.

Now, if we define v(n) = S(n+c-1)+3-2c, where S(n) is the Zeckendorf left-shift operation, the idea is that L(n) "ought" to equal v(n), and so what I'm really trying to predict is the difference L-v. (Here, the v function is essentially a sort of stabilized L. So I'm looking at how the real thing differs from the stabilized thing.)

As an example of what this looks like for small c -- for c=1, this difference is always 0. Same for c=2. For c=3, it's 0 unless n=F_k-3, then it's (-1)^k. From there on it gets more complicated.

Oh, one more definition: I'll use T(n) to mean the *dual* Zeckendorf right-shift operation. (Left shift is well-defined for all pseudo-Zeckendorf representations, so it doesn't matter whether you use ordinary Zeckendorf or dual, but this isn't true for right-shift! Here it matters.) This is also equal to ⌊n/φ⌋.

So: Our initial condition is that, for n<T(c-1), L(n)=n+1. Of course this is true rather further out; L(n)=n+1 for all n<c. But we only need it this far out for our initial condition.

(This initial condition is frankly a bit too complicated for my liking, but, I don't see any way to simplify it. Oh well.)

Then, the rule is that for n≥T(c-1), we have

L(n)-v(n) =
|{m<n: L(m)<v(m), S(m+c-1)-c+2+L(m)-v(m)<=n<=(m+c-1)-c+1}| -
|{m<n: L(m)>v(m), S(m+c-1)-c+2<=n<=(m+c-1)-c+1+L(m)-v(m)}|

OK, that probably warrants some explaining. (There's also something misleading about the expression above. I wrote it as a difference, but in fact, one of those two sets will always be empty. You either have all positive contributions or all negative contributions, never cancellation.)

Anyway, the way I'm thinking about it is this. We start with a bunch of positive exceptions (n such that L(n)>v(n)) in our initial condition, with appropriate multiplicities (values of |L(n)-v(n)|).

Then, a positive exception at n results in a negative exception at S(n+c-1)+2-c. If n has multiplicity k, it results in negative exceptions at S(n+c-1)+2-c, S(n+c-1)+3-c, ..., S(n+c-1)+c+L(n)-v(n). And if some m ends up being an exception due to multiple different sources, well, those different sources add up; since each one contributes -1, you just get the negative of the number of them.

Similarly, a negative exception at n results in a positive exception at S(n+c-1)+1-c. And if n has multiplicity k, this time it extends downwards, resulting in positive exceptions at S(n+c-1)+1-c, S(n+c-1)-c, ..., S(n+c-1)+2-c+L(n)-v(n).

OK, actually, that's not quite the way I'm thinking about it. All of this gets much nicer if we adjust all the numbers by adding c-1 to all of them. (So the numbering now starts at c-1 instead of 0, and our additive constant is effectively 1.) So now, positive exceptions generate negative exceptions at S(n)+1, and negative exceptions generate positive exceptions at S(n).

Well, that's still not quite the way I'm thinking about it. Remember I mentioned there's never any cancellation? I think of that initial condition as being an initial "run", a contiguous segment where L(n)-v(n) maintains the same sign or is 0. It's a positive run. This run then generates the next run, which is a negative run; which then in turn generates the next run, which is positive, etc. Runs never overlap; each one comes purely from the previous one.

Anyway this rule explains a lot of things like, why is it that for each c there are only finitely many n st |L(n)-v(n)|>1? And why is it that the behavior of L(F_k-c) depends on whether the smallest Fibonacci number greater than or equal to c has even or odd index? I won't go into that here, but it answers that question! Although as mentioned I haven't actually proven this yet.

There is sort of an intuitive explanation of why this rule should be true. Our initial condition is forced -- all those numbers are positive exceptions because the baseline v value for them is *negative* (or 0, or just too low due to the other positive exceptions in the initial condition) and so they get forced upwards.

Then, well, each positive exception generates a negative exception after it. That is, if some n has L(n) bumped up by 1, then R(n) is also bumped up by 1, which means it's bumped *out* of the spot it would normally occupy; so the later m such that v(m)=R(n) instead takes L(m)=R(n)-1, since that's been left free.

Correspondingly, each negative exception generates a later positive exception; if some L(n) is bumped down by 1, then R(n) is also bumped down by 1, which them of course means that if v(m)=R(n) then L(m) must be bumped *up* by 1.

And if |L(n)-v(n)|>1, well, then, this causes a cascade of sorts. And if multiple of these affect the same number it adds up I guess? Yeah idk -- actually proving it this way sounds annoying. But this is the heuristic explanation of why this rule should work.

Anyway it seems to check out and it explains everything else I'm seeing! Now I'd better get back to other things...

OK I updated the tree page one more time, this time it should actually be the last time. I noted some more empirics regarding what happens for c≥4, and then concluded with an open question about this case.

...and now I really better get back to other things I'm behind on! >_>

Um, meanwhile, we're down to 24 books till next shelf clear (not counting the tall two). And on Saturday I'm going to go see Lizz and bring them two more books, so! :)

EDIT next day: OK, turns out I still wasn't quite done. I refined the conjecture at the end, and added some computations. Now I'm probably done though... unless I go back and compute expicitly what v is when c=3. Which I just might do...

EDIT that night: OK I added explicit formulae. Blech. Now, I think, there is truly nothing to add! I should explore T₄ and up further later, but I think I can finally stop for now.

OK, I'm sure someone else has come up with this before, but I just realized: Werewolf Pack Leader + Shields of Velis Vel (e.g.) + Artificial Evolution + Embiggen.

The result of this, if you don't see where I'm going with this, is that you can get Werewolf Pack Leader's power and toughness to be 5+N/4+N, where N is the number of creature types that exist in the rules. (4 instead of 3 because I used Shields of Velis Vel for this version of the combo. :P )

This is something that Wizards has avoided letting you do easily, (e.g. the "non-Brushwagg" clause on Embiggen, or how Valiant Changeling has its effect capped at 5), presumably partly for power level reasons but largely because an in-game number should never depend upon how many creature types exist in the rules -- something that is not at all a constant -- but you can do it!

-Harry

So, I have answer to the questions from my previous post! No need to ask MathOverflow. :) I'll have to go write this up as a page on my website later. (I mean, notionally it could be a short paper somewhere to the extent these observations are original, but that adds a bunch of work and when it comes to actual math papers I've got higher priorities than this! I just want something that I can cite when I go to update OEIS with this information, an webpage with quick proofs should suffice for that. :P )

OK, so, let's start with the big one: Why is the reading sequence of Beren's tree identical to A232560, the inverse permutation of A232559, the reading sequence of the double-or-increment tree? (Where only even numbers have the option to increment, to prevent redundancy.)

Well, before we answer that, let's make an observation about the shape of this second tree. Beren's tree is Fibonacci based in terms of content, but it's a binary tree in shape. While the double-or-increment tree is based on binary... but in shape, it's Fibonacci. The lengths of the rows are Fibonacci numbers, because it's doing the Fibonacci rabbit thing, where only even-valued nodes (adult rabbits) can have two children, with odd-valued nodes (juvenile rabbits) having only one.

So, we have a Fibonacci binary tree and a binary Fibonacci tree. Less strange now that they're inverse, isn't it?

OK, but that doesn't explain why they actually are. Consider especially -- these trees do have different shapes. If the trees had the same shape, then we could regard these two permutations not as being on the linearly-ordered natural numbers, but rather on the spots of the unlabeled tree of that shape, and show that the permutations were inverse that way, without having to ever involve ourselves with the whole "reading sequence" business. Since that is not the case, however, we can't take that approach, and we will have to involve the reading order at some point.

Anyway, before we go any further, let's subtract 1 from each number in both trees, so we'll now be dealing with permutations of the whole numbers {0, 1, 2, ...} rather than of the positive integers {1, 2, 3, ...}. We do this because, as mentioned, Beren's tree, when you subtract 1 from each number, becomes this dual-Zeckendorf tree.

So: On the one hand, we have our dual Zeckendorf tree. In this tree, 0 is the root (the empty string in dual Zeckendorf), taking the left child corresponds to appending 1 (to the dual-Zeckendorf representation), and taking the right child corresponds to appending 01.

What about our other tree? Well, if we don't subtract 1, then it's a tree of binary representations; 1 is the root; even numbers have two children, with the left child corresponding to changing the final 0 to a 1, and the right child corresponding to appending 0; and odd numbers have one child, corresponding to appending 0.

OK, but what if we do subtract 1? Well, then it's a tree of bijective binary representations! The doubling operation becomes double-and-increment. So now 0 (the empty string) is the root; it's odd numbers that have two children, with the left child meaning you change the final 1 to a 2, and the right child meaning you append a 1; and even numbers have only one child, corresponding to appending a 1.

In order to see that these trees have inverse reading permutations, I want to introduce two auxiliary trees. We have a Fibonacci binary tree and a binary Fibonacci tree, but for comaprison, I'm going to introduce a binary binary tree and a Fibonacci Fibonacci tree.

That is to say -- consider the binary tree that, when read across, simply yields 0, 1, 2, 3, etc. This, if we look at it in bijective binary, can be described as a tree with root 0 (the empty string), where the left child is append a 1, and the right child is append a 2.

We can do the same thing on the other side; we can take a tree as the same shape as our Fibonacci-shaped tree of bijective binary numbers, but one whose reading sequence is simply 0, 1, 2, 3, etc. This similarly has a natural interpretation in terms of dual Zeckendorf; left children mean append a zero, right (or only) children mean you append a 1. Only numbers that are a 1-child can have a 0-child. (The identity of these two descriptions of the tree might not be obvious, but it follows from the fact that to compare two numbers written in dual Zeckendorf, you just do so lexicographically.)

So: Let us consider the permutation that takes our binary binary tree (whose reading sequence is just the whole numbers) to our Fibonacci (dual-Zeckendorf) binary tree (which has the same shape). What does it do to the number at any given spot? Well, what you do to the number is, you write the number in bijective binary; then you change each 2 to a 10 while leaving each 1 as a 1; then you interpret the string as dual Zeckendorf. So that's our permutation one way.

Now, we consider the permutation that takes our Fibonacci Fibonacci tree (whose reading sequence is just the whole numbers) to our binary Fibonacci tree (which has the same shape). What does this do to the number at any given spot? Well, you write the number in bijective binary; then, starting with the empty string, you interpret each 1 as an "append 1" and each 0 as a "change the final 1 to a 2" (because a 0-child must have a parent that is a 1-child, this is well-defined); then you interpret the string as bijective binary. That's our permutation the other way.

And, well, those two operations are inverse to each other, so there you go! Where did we use the reading order? How did we deal with the fact that the two trees are different shapes? By setting up two auxiliary trees which, although they had different shapes from each other, had identical reading sequences. Basically we had a chain of four trees, FB-BB-FF-BF, where the pairs FB-BB and FF-BF have the same shape, while the pairs BB-FF have the same reading sequence.

Now, you may have noticed here that we used dual Zeckendorf and bijective binary, with roots starting from 0. But what if we had used ordinary Zeckendorf, with root starting from 1? Where the left child meant "append 0" and the right child meant "append 01"? Well, in that case, the same proof as above implies that our corresponding "inverse" tree would be a tree based on ordinary binary, with 1 as the root... a tree that is almost the same as our original double-or-increment tree, before we subtracted 1 from everything. The only difference? It'd be flipped left-to-right. That tree had the left child meaning "change the final 0 to a 1" (when there were two children) and the right child meaning "append a 0"; here it would be the other way around.

To summarize, here's a list of the (nontrivial) involved trees and the relations between them. Here, "B" stands for "binary", "Z" stands for "Zeckendorf", "D" stands for "dual Zeckendorf", and "J" stands for "bijective binary". The first letter describes the representation used to make the numbers in the tree, while the second letter represents the shape of the tree (note "J" is not a separate shape from "B"). And Beren's original tree I'm just going to label "TB" because uh I dunno. :P

List of involved trees, excluding trivial trees (those whose reading sequences are just consecutive whole numbers or positive integers):

TB: Beren's original tree. Has 1 as the root.
DB: Dual-Zeckendorf binary tree. Has 0 as the root.
BD: The original double-or-increment tree. Has 1 as the root.
JD: Double-and-increment-or-just-increment tree. Has 0 as the root.
BZ: Double-or-increment tree, but reversed. Has 1 as the root.
ZB: Zeckendorf binary tree. Has 1 as the root.

Relations among involved trees:

TB = DB + 1
BD = JD + 1
BD = flip(BZ)
TB and BD have inverse reading permutations (starting from 1).
DB and JD have inverse reading permutations (starting from 0).
ZB and BZ have inverse reading permutations (starting from 1).

Um, I realize that's likely a bit confusing, but I hope it clears things up somewhat? Here's a diagram:

      inverse
DB(0) ------- JD(0)
 |-1            |-1
 |              |
 |+1  inverse   |+1
TB(1) ------- BD(1)
                |
                |flip
      inverse   |
ZB(1) ------- BZ(1)

...where the left column is binary trees with Fibonacci contents, and the right column is Fibonacci-shaped trees with binary contents.

(One would of course get more relations if one looked at reverse reading permutations, where you read each row right-to-left, but I don't see a need to discuss that... all that is implied from the above.)

Now you'll notice that nowhere above did I discuss bijective Zeckendorf, because, well, it doesn't seem to really fit into the above very well. But I do have something to say about it, that answers my other two questions from last time!

So, one of the things that's special about binary, that doesn't hold for higher bases, is the close relation between ordinary binary and bijective binary. Namely, for n≥1, the bijective binary for n-1, is the same as the binary for n, but with the leading 1 removed and with 1 added to each digit.

Bijective Zeckendorf was frustrating me because I expected there to be a similar relation, but I wasn't seeing one. Except, oops, it's actually really easy, not sure how I missed it! Namely, for n≥2, the bijective Zeckendorf for n-2, is the same as the Zeckendorf for n, but with the leading 10 removed and with 1 added to each digit. This immediately answers both of my questions about bijective Zeckendorf from the previous post! As in the case of binary, one can see this either by examining how sums of Fibonacci works, or by examining how counting works.

So, yay, all three questions answered! Now when I have some time I need to go make a webpage about this...

So I was out in Berkeley for a week a bit ago and I've been meaning to write about it here. Well, OK, there's a lot I could say, but there are a few particular things.

I guess really the main thing I wanted to say about Berkeley is, holy crap the grade. Goddamn the grade is a killer. I mean, it's not that steep most places, as long as you don't start really going up into the hills -- well, OK, I guess that's a tautology, but a lot of places are not up in the hills is my point. (I asked Drake, "What do you call those mountains to the east?", and he was like, you mean the Berkeley Hills? :P )

(Much of campus is starting to get up into the hills, but fortunately it's not like I'm studying there!)

The thing is that Berkeley is pretty spread out. It's really quite suburban -- huge amounts of it are just houses, and laid out in a grid, no less, so it's pretty uninteresting to walk around. And this sparsity of destinations means that the grade really adds up. The thing is that it's consistent. Lower Manhattan has plenty of steeper slopes, but they rarely go on for so long. But in Berkeley, if you're travelling north or east, you're travelling up. The thing I eventually realized is that if you're going somewhere, it's actually easier to go somewhere that's up, because that means that on the way back you're going down, and you're more tired on the way back than on the way out. Hoo boy.

I mean, BART exists, but that's really more for far travel, yeah it's a subway, but like, it's sort of a subway and sort of commuter rail, right? The stations out there have parking lots. It's not much use for getting around Berkeley -- OK, I used it for that purpose once when I was really tired and was travelling multiple stops (by which I mean two), but mostly, you're going on foot and you're facing the grade.

So, walking around Berkeley ended up being less interesting than anticipated. I did go out to the water once but it was fairly barren -- and of course, the way back was up.

One thing that's interesting walking around Berkeley -- when I told Drake I'd been wandering around, he asked if I'd seen any of the plaques. Plaques, I asked? Yeah, that someone point down. I was like... you mean like the Toynbee tiles?? He hadn't heard of the Toynbee tiles, actually, so I got to tell him about those.

But no, not like the Toynbee tiles. Someone has been placing these plaques all over Berkeley commemorating made-up minor events (some with dates in the future), and Drake and various others out there have made a sport of hunting for them and cataloguing them. I assume there must be a big group of people who are doing this together and have a central list of ones they've found, but Drake, and Eric who he also mentioned but who I didn't see while out there, and I assume various others, are instead focusing on doing it individually, deliberately avoiding learning too much about ones they haven't seen yet.

I did eventually while exploring come across one tile; I sent Drake a picture of it before it ever occurred to me maybe he would prefer I not do that. Fortunately, Drake was able to look at it just enough to determine it was one he hadn't seen before, without actually reading the bulk of the text, and, importantly, without reading the part that said what street it was on, which would make hunting for it substantially less interesting. (He did ask for a general clue as to what region of Berkeley it was in, so I told him that.) He hasn't mentioned it since, so I assume he still hasn't found it.

Anyway there's more I could say but that's the main thing I wanted to!

(Meanwhile here in New York: 10 books to next shelf clear...)

Hey! Remember this entry?

Recently Shaked wrote about the same idea, although he allowed artificial canals to count, and also missed a bunch of the ones that I pointed out.

Well, someone pointed out this post by Starkey Comics, which looked at this issue rather more thoroughly! So yeah! Go read it about how distributaries split up North America into pieces!

-Harry

So I told Steph -- out in Michigan -- about the shelves of free books, and she was quite interested to hear that we have lots of books on dreams. :)

So, I sent her pictures of what books we have on that topic, and she was like, "A Grammar of Dreams" looks interesting!

First time giving away a book from the shelves by sending it through the mail. :) But it's sent! Which means only 14 books to next shelf clear (modulo Bit, who it seems intends to show up in the next few days). :)

(You may say, wait, you had 16 left, you gave away one, now you have 14 left? Well, it's a big book, see, so multiple other books could take its spot. This does kind of highlight why *count* of books is a bad measure; really I should add up the total linear *size* of the books. But measuring is more troublesome than counting, so, eh, I use counting as a decent approximation.)

(Also, I noticed one more book I can give to Lizz. But that will have to wait, probably till after my trip to California.)

-Harry