sniffnoy | Entries tagged with fibonacci tree

I never properly wrote about this question here -- only obliquely referred to it here with the text "proving it seems annoying" -- but now it has an answer!

This is a question about automatic sets, so I should probably explain what those are, since a lot of you won't know. A b-automatic set is a set of whole numbers which is given by, you have some DFA on the alphabet {0,...,b-1}, you write numbers in base b and run them through the DFA, and the numbers it accepts are the ones it accepts. (And an automatic set is a b-automatic set for some b. There are also automatic sequences, where instead of just accept/reject, the DFA returns some other output. But we'll stick to sets here.)

Now, there's a number of questions you might have here about the details, but the concept is actually quite robust to small modifications and so precisely how you handle the details in your definition is just not going to matter. For instance, do you write numbers little-endian or big-endian? It doesn't matter, because regular languages are closed under reversal.

For the purposes of this question, though, that particular detail will matter: We're going to assume numbers are fed into the machine little-end first.

So let's say we have a b-automatic set, and it's given by a machine M when the numbers are written from the little end. And let's suppose that M has a particular property: That from every state, it is possible to reach a "sink state" -- a state that only ever loops back to itself. In this case, we can meaningfully ask the question, if we feed into M a uniformly random string of digits, with what probability does it accept? Since with probability 1, it will always hit a sink state eventually, and then we can judge acceptance or rejection by that. Let's call this probability p(M).

The question, then, is: Say S is the automatic set determined by M. Is d(S), the natural density of S, equal to p(M)?

It sure seemed like the answer should be yes, because both can be thought of as plugging random digits into M. But I couldn't prove it! And surprisingly, I couldn't find any results on this in the literature, either. Now I'm no expert on automatic sets, so I could have missed something, but still, I couldn't find it. People said the problem sounded easy -- and then produced proofs that were incorrect. No correct ones.

Well, I asked around, I asked on MathOverflow, and now, a year and a half later, I finally got an answer, due to Alex Mennen. Yes it's true, and it turns out it really wasn't that hard after all! I'm just not much of an analyst. :P

(On MathOverflow, after feedback from Jeffrey Shallit, I ended up reformulating the question a bit; but the version I posted is in fact equivalent to my original version, and also, my original version is what Mennen ended up proving.)

But, the problem as stated above wasn't really what I wanted. Let's throw in some complications.

Complication #1: Multidimensional sets. One can define multidimensional b-automatic sets, subsets of N^k, where the alphabet is {0,...,b-1}^k. Does it still work here?

Complication #2: The set I cared about wasn't actually a b-automatic set at all, but a Fibonacci-automatic set, where the input is in Zeckendorf! (So, some parts of the setup above have to be appropriately modified; the distribution on digit strings is no longer uniform, for instance.) Can we get it to work here?

Complication #3: Actually, it was a 2-dimensional Fibonacci-automatic set.

Fortunately I was able to modify Mennen's proof to handle these complications (going to multiple dimensions is easy; handling Fibonacci required slightly more work). So yay, it's true!

But, there's more we could ask about. Like, what about other numeral systems? Yeah, I don't want to go there. (Handling bijective base-b I'm pretty sure should work the same by the same proof. I expect dual Zeckendorf should also work, but I haven't tried. But those are minor variations.)

And the other question I have to wonder about is... what about the big end? If we feed in numbers from the big end, then it's easy to come up with counterexamples; but maybe it would work if instead of natural density we used logarithmic density? (Recall, logarithmic density isn't really a separate quantity from natural density -- it just exists more often.) The failures I've seen in the big-endian case have always been of the form "the natural density doesn't exist", not "the natural density exists but has the wrong value". I'm guessing it's probably true! But again, I don't really want to be the one to do it.

Jeff says I should write this up as a paper along with Alex Mennen, which, yeah, I guess I should. Kind of annoying, because it'll push other things back. But, oh well, one more thing for the backlog I guess. Still, first I think I might ask around a bit more, see if anyone knows of a result like this already out there. If it's just something I can cite, great! But my guess is that even if someone has done it for base b, they probably wouldn't have done it for Fibonacci...

-Harry

So, not about the tree anymore per se, but more about Zeckendorf! Well -- this question arose out of the study of the tree, obviously. You see (to use briefly the terminology I was using to discuss the trees so I can state the original motivation), the v function has an oddness center (i.e. a point (h,k) st v(h+x)+v(h-x)=2k), but it also has a bunch of "pseudo-oddness centers", points (h,k) st v(h+x)+v(h-x) is usually 2k but not always. And whether it is or not is governed by the equation S(n+x)=S(n)+S(x).

Here by S I mean the Zeckendorf left-shift operation -- although, as you may recall from previous entries, it's actually well-defined even if you allow pseudo-Zeckendorf representations without consecutivity restrictions. (And thus in particular it also works for dual Zeckendorf.)

Anyway, so we have the question: When is S(n+m)=S(n)+S(m)? More generally, how can we determine S(n)+S(m)-S(n+m), without actually doing the addition? (We can also ask the same for S(n-m)+S(m)-S(n).) And, given n, what is the natural density of {m: S(n+m)≠S(n)+S(m)}?

Well, I have answers to all these questions! Likely this is already known, but I figured it out the other night and I thought it was neat.

Note that the difference S(n)+S(m)-S(n+m) is always one of 0, 1, or -1. Now, my actual rule for how to compute this quantity is a little complicated, so I'm going to hold off on stating it for a moment. But, the resulting rule for d({m: S(n+m)≠S(n)+S(m)}) is actually quite simple!

Namely, write n in Zeckendorf; let's say n = Σ_iF_{k_i} for i≥2, k_i increasing (so k₀ is the smallest), and the usual consecutivity restriction.

Then, the natural density that we're looking for is simply Σ_i(-1)^k_i-k₀φ^-k_i.

Another thing worth noting, btw, is that for each n, the only nonzero value taken on by S(n)+S(m)-S(n+m) will be (-1)^k, where k is the number of zeroes on the end of the Zeckendorf representation of n. Now you may say here, wait, just n? What about m? This function is symmetric, surely m must also have an effect? Well, that's the thing! The value can only be nonzero when this zero count has the same parity for both numbers! If they disagree, it's necessarily 0. (And of course it's always 0 when n=0, for which the count is undefined.)

Btw, a neat little thing about this parity: Did you know that the parity of the number of 0s on the end of the Zeckendorf representation of n, is always the opposite of the last digit of the dual Zeckendorf representation of n? Similarly, if you look at the parity of the number of 1s on the end of the dual Zeckendorf representation of n, this is always the same as the last digit of the Zeckendorf representation of n.

So, we could also say that you can only get a nonzero result if n and m have the same last digit in dual Zeckendorf, in which case the potential nonzero value is (-1)^1+d (d being the digit), although I don't actually think that's a good way to think about this.

OK, so, what's the actual rule? Well, this is a little annoying to state properly. Heh, I realized the other day that it can be given as a finite state machine, but I'm not going to subject you to that.

I think the easiest way I've come up with to state it is: First, write n and m in Zeckendorf, and then take the digit-wise sum -- just add them up straight, yes you'll get 2s, you'll get consecutive 1s, it doesn't matter. Then, find the largest k such that there is a suffix of the form (2(01)^*00)^k2(01)^*0^ℓ≤1 (if there even is such a k, which there may not be). (Note: The exponents on the 01 may be different between the different copies of 2(01)^*00, they don't need to all match or anything like that, otherwise it wouldn't be finite-state.) If there is no such k, or if k is odd, then S(n)+S(m)-S(n+m)=0. If k is even, then S(n)+S(m)-S(n+m)=(-1)^ℓ.

So yay, an answer!

EDIT next day: I guess we could write this as -- assuming no leading zeroes and valid input -- it's an exception iff the digit-wise sum satisfies the regex

/^(.*(1(10)*0|0(01)*00))?((2(01)*00){2})*2(01)*0?$/

but hoo boy personally I find that less clear than the above description.

Now, what about subtraction? Well, first off, let's dispense with the natural density question. If we fix n and look at {k: S(k-n)≠S(k)-S(n)}, well, this is just a translation of the set {k: S(k+n)≠S(k)+S(n)}, so we already know the answer to that. And if on the other hand we look at {k: S(n-k)≠S(n)-S(k)}, well, then we're just looking at finite sets, so this question is uninteresting.

But, we can still ask about a rule for determining S(n-m)+S(m)-S(n), where want to determine this without actually performing the subtraction. And, this too has an answer! It's very similar to the above, except that, while we write m in Zeckendorf as before, we have to write n in dual Zeckendorf.

Then, we perform the subtraction to get a string of 1s, 0s, and -1s. If we simply subtract each of these digits from 1, to get 0s, 1s, and 2s, we can then apply the same algorithm as before.

So, in order to get a nonzero value, it must be the case that the parity of the number of 0s on the end of m in Zeckendorf, must be the same as the parity of the number of 1s on the end of n in dual Zeckendorf. Or -- for a less useful rephrasing -- the last digit of m in dual Zeckendorf must be opposite the last digit of n in Zeckendorf. Hm.

So anyway yeah that's neat!

Now, where does this addition rule even come from, anyway? Why does it work? This is going to be the handwavy explanation I used to originally come up with it; I can prove it, too, although not from scratch, but I can if I make use of this paper. But I don't want to get into formalism here.

Anyway, fundamentally it comes down to, if you were to actually carry out the addition in Zeckendorf, is there any part that would not commute with left-shift? And the answer is yes. Simply performing the addition of digits with no transformations is obviously no problem. And we already know that handling consecutive 1s commutes with left-shift, that's why left-shift is well-defined on pseudo-Zeckendorf representations. But what about handling of 2s? In most places, 0200 becomes 1001; that commutes with left-shift. But what doesn't is how it works in the 2s place and the 1s place. 20 is equal to 101, and 2 is equal to 10. The former gives you a difference of -1, the latter gives you a difference of 1.

So, to get S(n+m)≠S(n)+S(m), you must either have both with a 1 in the 1s place, or both with a 1 in the 2s place, right? Not so fast! Remember, adding two 1s in most places yields not only a carry upwards of 1, but also a carry of 1 downwards two places. This means that it's possible to get one of these problematic additions by adding, say, 101 (4) and 100 (3). The carry in the 3s place yields a problematic addition in the 1s place. Or imagine you add 10100 (11) and 10001 (9); the carry in the 8s place causes a carry in the 3s place, which cascades into a problematic carry in the 1s place.

Of course, these chains can get longer than that! But as long as you have 2(01)^*, you get an exception with a value of 1, or if you have 2(01)^*0, you get an exception with a value of -1.

Except, not so fast! What if something else up above could nullify that 2? Well, that can happen! Look at what happens if you add 1001 (6) to itself. That 2 in the 1s place should generate an exception... except, that the 2 in the 5s place results in a downward carry to put a 1 in the 2s place. The consecutivity drains a 1 away from the 1s place, up to the 3s place, leaving nothing that can generate an exception in the 1s place. So, we get an exception to the exception -- a value of 0 after all.

And just as with our chains of 1s that can generate an exception, we can have longer chains here too; for instance, if you were to add 101001 (19) and 100001 (14), the carry in the 13s place would generate a carry in the 5s place, into the 2s place, which would still prevent the problematic carry in the 1s place.

But wait! If an offset chain up above can drain away a 1 from a problematic carry... then a further offset chain even higher can drain away a 1 from the carry that would prevent the problematic carry, resulting in an exception after all! An exception to the exception to the exception. For instance, if you were to add 1001001 (27) to itself, the carry from the 21s place into the 8s place would prevent the carry in the 5s place, allowing the carry in the 1s place to happen after all, yielding a value of 1. You see?

And so forth; one can have more and more such offset chains, each of which deactivates the one coming after it. So whether you get an exception or not is determined by the parity of the count of them. And whether you get 1 or -1 is determined by whether the problematic carry, if it occurs, ultimately occurs in the 1s place or the 2s place. So that's why this is the correct rule; and that's not a proof, exactly, but using the paper linked above it can be turned into one.

Josh says Steven Miller might be a good person to talk to determine whether any of this is original and where I can find references for whatever might need citing... well, I'm not going to even think about writing a paper on this until various other papers are out of the way!

EDIT much later: Btw, if we want the overall natural two-dimensional natural density for the different possibilities -- well, actually proving it seems annoying, but for a difference of 0, it ought to be 2φ-5/2 (i.e. √5-3/2), for a difference of 1 it should be 1-φ/2, and for -1 it should be 5/2-3φ/2. (And for 1 or -1, it should be 7/2-2φ, or 5/2-√5.)

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.

I updated the tree page to talk about what happens when you increase the additive constant!

By that I mean, what if, instead of n+L(n)=R(n), we did n+L(n)+c=R(n)? Actually, that's how I'll do things for the 0-rooted case; for the 1-rooted case I'll adjust things by one, say n+L(n)+(c-1)=R(n), so that it's just the 0-rooted version plus one.

Then c=1 is what we started with -- the 0-rooted version is the dual Zeckendorf tree, while the 1-rooted version is Beren's original tree, the Zeckendorf parity tree.

Meanwhile c=2 yields the other variants I discussed; the 0-rooted version is the dual Zeckendorf parity tree, while the 1-rooted version is the plain old Zeckendorf tree.

But what about c=3, and higher? Well, for c=3 I have a description, see the page. (Well, I have a fairly nice description for the 0-rooted version, not so much for the 1-rooted version; I'm going to stick to the 0-rooted versions for c≥3, I think.) But for c≥4... it's a mess. I tried c=4 and c=5 and don't see any nice description for either of them.

That said, despite this fact, these trees still appear to be full of Fibonacci patterns! Hopefully someone can figure out what's up with that, but I think I need to put this problem down for now -- I'm still so behind on other things...

1. The description in terms of even/odd number of zeroes doesn't have to be proven via dual Zeckendorf; it can also be proven directly by Ophelia's cold/hot argument, rephrased for this purpose.

2. Speaking of which -- one could define an analogous tree for dual Zeckendorf starting from the empty string. I don't know of any way to relate that to any of these other trees, though, nor am I aware of its reading permutation or its inverse being anything interesting.

(There's one almost-match for the inverse on OEIS, namely A303765, but it doesn't match. Not unless I've seriously messed up.)

3. I put up a page about it on my website!

EDIT: Ugh, the tree totally does relate after all. Gonna need to go back and edit this page...

EDIT: OK, did a quick edit to account for the new stuff... go just read about it there, I guess! (There's a new parity-based tree. :P )

EDIT again next day: OMG there's 8 more trees I missed. Well now they're in there too, which meant some rewriting. Geez. Yay, more ASCII art.

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...

OK so Beren Gunsolus came up with this really cool tree of numbers that is full of Fibonacci patterns and he and I and some others (Astra Kolomatskaia, Ophelia) have been spending much of the past few days looking at it.

Now, originally I had started writing a long post where I gave Beren's definition of the tree, as well as a long list of (often Fibonacci-related) patterns we had found in it, not all of which we had proved. Yesterday, though, I figured out a much nicer description of the tree than Beren's original one (but which we can prove is equivalent), and with this nicer description, a lot of the patterns that we'd found become easy to show.

I'm not going to bother listing these easy patterns; you can go looking for them yourself, and proving them yourself -- there are quite a few to find. Not all of what we spotted is so trivial, though! We've still got some big questions about this tree.

[EDIT August 17th: These questions now have answers! I've written about them here. I've left the rest of the entry unchanged, note.]

Anyway, to get to the point quickly, I'll start by giving this new definition of the tree and a big question it raises; after that I'll give Beren's original definition of the tree and some of the other questions about it (or just inspired by it) that I don't have an answer to (as well as a third description of the tree, and a conjectural fourth one). Some of these later questions are probably solved in the existing literature, I haven't searched.

So: You've heard of Zeckendorf representation, right? Well it turns out there's such a thing as dual Zeckendorf, which is like Zeckendorf representation, except that instead of the restriction being that you can't have two 1's in a row, the restriction is that you can't have two 0's in a row (the implicit 0's before the initial 1 don't count).

One can build up the dual Zeckendorf representation for any whole number, then, by concatenating together some combination of the strings "1" and "10". (Remember, if it's not empty, it has to start with a 1.) This naturally puts the whole numbers into a tree; 0 is the root with dual Zeckendorf representation being the emptpy string, and to get the left child of a node you append a 0, and to get the right child of a node you append 10. I'll call this the "dual Zeckendorf tree".

Beren's tree was this, with 1 added to all the nodes, covering the positive integers instead of the nonnegative integers. I'll call this the "adjusted dual Zeckendorf tree". I'll use here the convention that m is a number in the dual Zeckendorf tree, while n is a number in the adjusted dual Zeckendorf tree, so n=m+1.

If you read across the rows of this tree, from left to right, you get the sequence

1, 2, 3, 4, 6, 5, 8, 7, 11, 10, 16, 9, 14, 13, 21...

This appears to be OEIS sequence A232560, which is defined as the inverse permutation of A232559, which is in turn obtained from reading across a different tree. This other tree that ours is "inverse" to is not based on anything Fibonacci or Zeckendorf, but instead is based on doubling and adding 1. Why would these two permutations be inverse to one another? I have no idea!

So, question number one: Is this sequence actually A232560, and why?

OK. That's the big question; I'm guessing there's no currently known answer to this one, or else it'd be listed in OEIS. (I might post it to MathOverflow, if Beren doesn't, which I doubt he will.) But it's not the only question.

Anyway, before I get to the other questions, let me give Beren's original definition of the tree.

Beren's original definition was based on constructing it a little bit at a time, starting from the root, which is the number 1.

Then, at each step, we will look for the lowest number in the tree that so far has no children (as the tree has no repeats, this will be well-defined), and we'll give it two children. The left child will be the smallest number not yet in the tree, and the right child will be the sum of the parent and the left child.

Now, as mentioned above, I've sinced proved the equivalence of this original definition, and the more explicit definition above in terms of dual Zeckendorf. But my proof is actually just a slight adaptation of one devised by Ophelia of something very slightly different (well, arguably it's the same, but, one thing at a time).

See, before we thought to look at dual Zeckendorf, we were looking at Zeckendorf, because, I mean, that's much better known. And what Ophelia proved is that, if we let Z(n) be the left-shift operator on Zeckendorf representations, then the left child of n is Z(n-1)+2, which means the right child is Z(Z(n-1))+3.

Now you'll notice that, once you write things in terms of m instead of n, this is almost the same description that I gave above; the only difference is that we're using this Z operation, left-shift on Zeckendorf, instead of, call it Z', left-shift on dual Zeckendorf (although the output of that won't be a well-formed dual Zeckendorf representation). Except actually these are the same thing!

More generally, given finite sets S,T⊆{2,3,4,...}, if Σ_i∈SF_i=Σ_i∈TF_i, then Σ_i∈SF_i+1=Σ_i∈TF_i+1. So left shift is in general well-defined on these "pseudo-Zeckendorf" representations. (I'm assuming this is known, though I haven't checked and it wasn't previously known to me. But I'm pretty sure I can prove it.)

That means that Ophelia's description, and my description, are in fact the same.

Now, Ophelia's coming up with this started with the two of us observing that whenever n is a left child in the tree, n-2(= m-1) ends in a 0 in Zeckendorf, while when n is a right child, n-2(= m-1) ends in a 1 in Zeckendorf.

Of course, by my reformulation above, we can could also say that n is a left child when n-1(= m) ends in a 1 in dual Zeckendorf, and n is a right child when n-1(= m) ends in a 0 in dual Zeckendorf.

So that's interesting -- the last digit of k in Zeckendorf, and of k+1 in dual Zeckendorf, are always opposite. Of course, going through Beren's tree definition is a pretty roundabout way to see this... actually, this is easy to prove from the fact I stated above about the well-definedness of left-shift. (Again, I assume this has to be known.)

But here's a question, not involving the tree, but inspired by the tree. We've talked about Zeckendorf and dual Zeckendorf, but there's also bijective Zeckendorf, using 1s and 2s instead of 0s and 1s, with consecutive 2's prohibited. This isn't something I've seen anywhere before, but it's kind of obvious so I assume it has to be known. (Note there's no such thing as dual bijective Zeckendorf... such a system would have no way to represent the number 3, for instance.)

(Btw: Seems that the well-definedness of left-shift works just as well for "pseudo-bijective-Zeckendorf" representations, using an arbitrary mix of 1's and 2's with no restrictions; however, it doesn't work if you allow all three of 0's, 1's, and 2's in the inputs. E.g., 2_Fib=10_Fib=2, but 4=20_Fib≠100_Fib=3.)

Anyway, here's something a bit odd. It appears that given r>2, the last digit of r-2 in bijective Zeckendorf is one plus the last digit of r in Zeckendorf. Why's that? Well, OK... this seems like the sort of thing that would probably be known, and my guess is that it's probably not too had to do it by showing these sequences of final digits are identical because both form the Fibonacci word (although the bijective one has some of the beginning cut off), although I'm having some trouble carrying that out right now, due to not knowing the Fibonacci word well enough... still, I feel like that's kind of a disappointing way to go about it.

OK, that question didn't actually involve the tree, but let's ask one more question that does.

As noted above, the tree has a nice representation if you write m in dual Zeckendorf. But let's say we look at Beren's original tree, the adjusted dual Zeckendorf tree, and write n in ordinary Zeckendorf.

Then in fact, the tree ends up having a pretty nice description in ordinary Zeckendorf! And this isn't too hard to show based on the description above.

We put 1 at the root. Then, for each n in the tree, count how many 0s its Zeckendorf representation ends in (since we've excluded 0, this is well-defined). If it ends in an even number of 0s, then its left child will be formed by appending a 0, and its right child will be formed by appending 00. Whereas if it ends in an odd number of 0s, then its left child is formed by appending a 1, and its right child is formed by appending 01.

You can check that this description in terms of the Zeckendorf representation of n is equivalent to the description in terms of the dual Zeckendorf representation of m.

Now, here's where it gets a bit weird. Suppose we again turn to bijective Zeckendorf; we'll form a tree where we write down the bijective Zeckendorf representation of n-2(= m-1). So now we've taken our dual Zeckendorf tree and adjusted it in the other direction, subtracting 1 instead of adding 1; let's introduce the convention t=m-1=n-2. Anyway, we look at this new tree, and we write each number tree in bijective Zeckendorf.

Then, it appears that the left and right (respectively) children of t can be formed by either appending 1 and 11 (respectively) or 2 and 12 (respectively), depending on the (ordinary) Zeckendorf representation of n(= t+2), in the same way as above (former case is even zeroes case, latter case is odd zeroes case). Why is this, and can we come up with a description of the case breakdown that looks just at the bijective Zeckendorf representation of t, rather than passing through t+2? This, well, maybe it's known, but it wouldn't surprise me if it wasn't.

So yeah! That's Beren's tree, and three (or four) descriptions of it. We've figured out a lot going on with it, but there's still quite a bit we haven't!

-Harry