Chronicles of Harry

So! I haven't posted here in a while. Several things I mean to post but I've been busy with other stuff. And most recently I've been busy with a return to the Snake problem!

So, at the suggestion of joshuazelinsky, I submitted the Snake problem as a second-year research problem to PROMYS. And the students (unfortunately I don't know their names, aside from one Rakesh Rivera) found that I made some incorrect claims! Here's a big one -- I said that Θ_2,2,k was winnable, but in fact it's only winnable for k=1 and k=2!

So, yeah, I had to reevaluate some things. Was the family that Justin found actually winnable? Yes, it was. OK, but then how does one minimize it? (On here and on the webpage I only described the minimized version, but that's not how he described it to me; see the webpage, which now describes the non-minimized version.)

I haven't thoroughly checked it, but I think I have a corrected answer. My previous answer (again, see the webpage) was correct... when k≤m. For m>k, it's a bit more complicated. This is why Θ_2,2,1 and Θ_2,2,2 are winnable, but Θ_2,2,k is not for k≥3. (In fact, Justin's graph is already minimal when m=2 and k≥3.)

But like I said, I think I've fixed it now!

Now to update more stuff. I'll be back with more posts later...

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

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

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 one Justin Kopinsky managed to find some new minimal winnables, so I've updated the Snake page!

(...and yeah, I still haven't written about Slay the Spire like I meant to, or anything in a while...)

So, a while ago I wrote here about the following open problem: Is there a finite coloring of the positive integers such that, for each (n,m)≠(2,2), n+m always gets a different color from nm? (With the expected answer being no.) In particular I wrote about a weaker variant suggested by joshuazelinsky; if one defines a greedy coloring obeying this latter constraint, can we at least show that this uses infinitely many colors? (Later I copied this entry to my website.)

Anyway, Josh informs me that the original problem is now solved! The paper is here.

I was going to take down the page on my website, but Josh said leave it up because it's not like everything has been resolved about his modified problem. In particular, it's still not clear what the growth rate of the function g is, nor if the interleaving pattern I observed holds up.

Anyway yay that's resolved!

And should hopefully have time to write about Mystery Hunt soon...

Following up to this entry, I want to report: Yes, we can indeed construct a group of order p^p+1 where the fraction of elements of order p is 1-1/p+1/p². Thanks to Hunter and to Julian for figuring out an important part of the construction.

Although, first I should point out David Speyer's construction from the comments, which does achieve the desired fraction but uses a larger order to do so; it has order p^{(p choose 2) + 2}. The group consists of all (p+1)×(p+1) upper-triangular matrices over F_p with 1's on the diagonal such that the first superdiagonal is an arithmetic progression.

But, OK, how can you do it with only p^p+1 elements?

EDIT: Actually Julian came up with an even simpler description; skip to the end if you just want to see that.

Well, I was inspired by the p=3 case. In the p=3 case, there's a unique group of order 81 that achieves the fraction 7/9, and it has the form (C₉×C₃)⋊C₃. And of course for p=2 our group D₈ has the form C₄⋊C₂. So, I decided to try to generalize this. I wondered, can we do it as a group of the form (C_p²×C_p^p-2)⋊C_p?

Let's say A = C_p²×C_p^p-2 and G is our group. We need to specify some automorphism of A of order p. But that's not enough; in order to get it to work, we need that all the elements of G\A have order p, which is not something that happens automatically.

So, what do we actually need here? Let's consider A additively; then our automorphism is given by a matrix M. We can consider this as a matrix over Z, if we want to be lazy, or over Z/(p²), if we want to be slightly less lazy, but really it's a sort of mixed matrix; the first row consists of elements of Z/(p²), while the other rows can be taken to be over Z/(p). Moreover, in the first row, all the off-diagonal elements must be divisible by p. (And also the diagonal element in the first row had better not be divisible by p, but that's not exactly a tough restriction and also it's redundant with the additional requirement I'm about to tack on.)

Now, we said it has to be of order p, right? So we need M^p=1. Except as mentioned above, that's not strong enough; in order to get that all elements of G\A have order p, what we want is the stronger condition 1 + M + M² + ... + M^p-1 = 0. Except, what do I mean by these matrix equations? Equal mod what? Well, they need to be equal mod p² in the first row, and equal mod p in the rest.

So the problem remains to construct such a matrix! Whether considered as a mixed matrix like I described above or as a matrix over Z or whatever. This is the problem as I posed it to various people I know the other day. (Figuring I'd take it to MathOverflow if I didn't get an answer, but I did.)

Hunter came up with a way of doing it first, and his way is definitely more direct conceptually, but I'm going to go with Julian's construction because it's really nice and also easier to carry out; no need to go finding eigenvectors or extending things to free bases. Note that this construction (both Hunter's and Julian's, actually) only work if p>2, but of course we already know how to handle the p=2 case (you take the 1x1 matrix (-1) and get the group D₈).

Julian's construction is as follows: Let's construct the transpose M^T instead. Take the ring Z[ζ_p], where ζ_p is a primitive p'th root of unity. As an abelian group this has a free basis 1, ζ_p-1, (ζ_p-1)², ..., (ζ_p-1)^p-2. Let's reverse that, so (ζ_p-1)^p-2 is the first basis element and 1 is the last. Now consider the additive endomorphism that is multiplication by (1-p)ζ_p. Then the matrix of this, with respect to the basis I just gave, satisfies the transposed version of all the requirements. (It's a matrix over Z of course but you reduce it down.) So you transpose it and you get M.

I'll skip his proof, I don't think it should be too hard to rederive. :) (If you just use the fact that v_p(ζ_p-1) = 1/(p-1).)

So there you go! Take M as above, take the semidirect product, and you've got your group. (Julian also asked an interesting question: Since he found a way to construct M by means of Z[ζ_p], can the group G be naturally expressed in terms of this ring somehow?)

EDIT: Yes it can, at least somewhat. We can write A as Z[ζ_p]/((ζ_p-1)^p), and then our automorphism is just multiplication by ζ_p, and then we construct the semidirect product with that. No need to construct any fancy matrix, hooray! And unlike the other two constructions, this one still works when p=2. :)

Anyway, that question at least is answered: You can achieve 1-1/p+1/p², and you can do it with only p^p+1 elements. Unfortunately that was the easy half, of a watered-down version, of a special case, of my original question! But hey, like I said, I'm not really planning on tackling any of the hard versions, so I'll take it. :)

-Harry

So I've recently been wondering again about this question (yes, this was originally a post here, but I decided it deserved a page on my website). Just mostly idly wondering about it, not seriously studying it; I'm no group theorist, and I don't really have time to think about such a problem what with everything else that needs doing (both in terms of old math that needs getting back to or writing up, and non-math stuff).

Anyway. As mentioned in the linked page, the simplest place to start would be words of the from aⁿ, so we're counting all elements of order dividing n. Or really the simplest place to start would be words of the form a^p, for p prime, so you're just counting elements of order p (together with the identity). (Or maybe prime power order if you want to be a little more general.)

Also as mentioned, for p=2, it's known that there really is a gap between ¾ and 1, with ¾ being achievable as D₈; I'm using the convention here that the dihedral group with 2n elements is D_2n, not D_n.

What I'm wondering is, what's the best known fraction (less than 1) for other p (or maybe other n)? Even if we can't prove a gap, it would still be nice to see how high we can find, to maybe get some idea of what the best might be (assuming that there really is a best like I'm hypothesizing).

Like, sticking to primes first -- for p=2, the best is ¾, that's a theorem. What about for p=3? I can again get ¾ by looking at A₄; I don't know offhand how to do better than that. And for p=5, uh, no clue. Well, I mean, obviously one can get ½ for any n (take C_2n), but I'm considering that baseline -- can we do better?

Since for p=2 you get a good fraction by looking at D₈, i.e., C₄⋊C₂, you might think more generally to try looking at C_p²⋊C_p; however, this doesn't work so well when p≠2 -- you don't get lots of elements of order p like you do when p=2. Like so many other differences between 2 and the other primes, this one once again basically comes down to the fact that 2 is the only prime p for which p does not divide (p choose 2). (I really think this is an underappreciated point, it really does seem to underlie so many of the differences, but I've never seen anyone else point this out!)

If we allow more general n then of course for any even n we can get ¾ by looking at D_4n. But mostly I don't want to look at more general n because this quickly gets kind of silly. I guess powers of primes might be kind of noteworthy? In which case that's how to get ¾ for arbitrary powers of 2? But like let's say you look at powers of 3 -- well then A₄ still does the job, you don't need to change the example at all! This sort of thing is part of why I say more general n is kind of silly. I guess more generally this gets you anything divisible by 3 but not 2, so we've now covered all n divisible by either 2 or 3. And of course in the trivial case of n=1 the best you can do is the baseline ½. But this is kind of why I said more general n is kind of silly.

Anyway, I dunno, that's what I've got. Anyone know anything about this?

ADDENDUM: OK, doing some quick computations with GAP here's what I get for some small primes based on groups of size less than 256 (haven't attempted to determine what groups witness these; also man I really do not know GAP, using it is a pain):

p=2: 3/4 (as we know)
p=3: 7/9
p=5: 9/11
p=7: 7/8
p=11: 21/23
p=13: 1/2
p=17: 1/2
p=19: 1/2

(EDIT: See the comments for some updates here)

Surprising, if you ask me! My offhand suspicion is that those ½'s at the end are spurious, an artifact of me not using large enough groups, but who knows? And it's not at all clear what pattern might be going on in the first few...

FURTHER ADDENDUM: Wow, after plotting the results from above for p=2 on a graph and doing the same for p=3... yeah, I'd totally bet on well-ordering, for this simple case at least. But I don't think I can go further and actually attempt to discern the order type from the graph, as I'd like to.

(Like I said I have no intent of trying to prove this. Maybe I will run some more numerical experiments to gather more empirical evidence, but that's it.)

YET MORE: You know what, just see the comments for more regarding the numbers.

-Harry

So, the past few days I've been thinking again about an old problem from MathOverflow. Or a related problem, anyway, seeing as I answered the original problem.

The original MathOverflow question is this one. Vladimir Reshetnikov asked about this strange way of recursively constructing functions from N to N, and asked if the resulting set of functions is well-ordered or something like that. Now, they might indeed be well-ordered or something like that if we modify his problem in one simple way: We exclude 0 from N (and drop the constant 0 function from our starting set).

But with 0 included... hoo boy. I realized that we could use the old λ-calculus trick of iterating a constant function to distinguish 0 from other numbers. And once you can tell whether a given number is 0, well, then you can start to do some rudimentary programming and completely wreck well-ordering.

In particular I was able to bootstrap this into showing that you can construct any eventually periodic function, and then show that you can, for any k, construct the function n↦max(0,2n-k). (I guess in there I only did it for even k, but obviously odd k is just a simple modification!)

The thing is that the programming you can do is indeed pretty fricking rudimentary. It was good enough for that but it's pretty hard to do a lot of things. Like, you know what would be a nice way of showing that it's not well-ordered? Construct the predecessor function! This class of functions is closed under composition so that would do it right there. As far as I can tell, though, this is impossible. I haven't been able to prove it, though, and I don't expect to be able to. But, my attempts to prove it led to the following question: What sets can we detect? I.e., what functions can we construct whose image is contained in {0,1}?

As mentioned above we can construct any function which is eventually periodic. It's also easy to see we can do basic set operations. But, rather than thinking in terms of sets, let's just think in terms of bounded functions more generally, and ask the question: Can we construct a bounded function which is *not* eventually periodic? Or are (eventual) arithmetic progressions the only sets we can detect?

This is not so easy! Like, there's all sorts of simple aperiodic sequences -- the set of squares, the set of powers of 2, whatever, right? But how do you make those? I don't see any way. In fact for a while last night I thought I could prove that you can indeed only get eventually periodic bounded functions (and my proof would have led if correct to a proof of predecessor being impossible) but my proof was wrong.

But, I think I now have a candidate for an aperiodic bounded function. Or, for a function which is aperiodic mod 3, so you can just mod out by 3 (i.e. compose with the mod-out-by-3 function) and get an aperiodic bounded function. The thing is that it's kind of ridiculous and I have no idea how to prove that it works.

(You'd think the fact that all you have to do is construct a function which is aperiodic modulo *some* m would make it easy, but no, obvious things don't seem to work...)

Here's my candidate: Start by defining f(n) as follows:
f(0)=0
f(n)=2n-8 for 10|n and n>0
f(n)=n+1 otherwise
This is pretty easy to make given the things I constructed above.
(The value of f(0) is irrelevant, as is the value of f(n) for n=1 mod 10, but whatever.)

Now define g(n)=fⁿ(10). Finally, define h(n)=gⁿ(n).

EDIT: The following variant may be very slightly nicer:
f(n)=2n-16 for n=8 (mod 10)
f(n)=n+1 otherwise

This way g(9q+r) (0≤r<9) works out to be 10⋅2^q+r.

I think h(n) should not have any eventual period modulo 3. Well -- it may be more useful to think of this mod 6 rather than mod 3. So, whatever, no eventual period mod 6, that's a weaker statement actually and so maybe a better proof target, although I think all the real action is basically going on mod 3 anyway, so whatever.

The problem is, I have no idea how I would prove this. (Of course maybe I'm wrong and this doesn't work at all and maybe it really all bounded functions you can make must be eventually periodic, who knows.)

Here's why I think this might work, though. Let's start with an example of what doesn't work. Obviously f(n)=aⁿ doesn't work; we all know that's periodic mod any m. But what about tetration? f(n)=H₄(a,n)?

Well as best I can tell mod any m that's eventually constant! Because, look -- aⁿ mod m, that depends on n mod φ(m), right? (At worst.) So if you have, like, a^aan, mod m, well that depends on a^an mod φ(m), which depends on aⁿ mod φ(φ(m)), which depends on n mod φ(φ(φ(m))). After enough φ's you hit 1 at which point your n no longer matters. And then n effectively stays at 0.

So what I concluded, I think, is that so long as for sufficiently large m the period mod m is always at most m, iterating your function will not get you away from periodicity. (The more general argument is more complicated, but the above is a simple case.) But what if we could make a function whose periodicity mod m were larger than m, for arbitrarily large m? What if, more specifically, you had some m such that its period mod m was equal to m₁>m, and its period mod m₁ was some m₂>m₁, and so forth? That's what my function g is. And so the hope is that by iterating it -- while simultaneously varying the starting point, so that there's an actual dependence on that thing all the way on the inside, rather than it stabilizing in some relevant way -- we should be unable to find any period that works.

FURTHER EDIT: Actually, experimentally, it looks like just using gⁿ(0) might work, without having to vary the starting point like I suggested above. That might be easier to analyze, but I still don't see how to prove it.

Specifically, here, m=6, or more generally, m_i=2⋅3ⁱ⁺¹. (Here i starts from 0, with m₀=m.) Right, this works because, OK, mod any 3^k (here k≥1), 2 is a generator, right? It has order 2⋅3^k-1.

So what if we were to artificially slow things down? That function f I described has the property that, for 10|n, f⁹(n)=2n. And since 10 is relatively prime to 3, we don't run into any problems here with the two moduli interfering with one another. So you start with 10, and then the idea is that g(n), mod 3^k, should have period 2⋅3^k+1, because we've taken that 2⋅3^k-1 and stretched it out by a factor of 9. (And this should also be the case mod 2⋅3^k because e.g. the mod 2 is determined by the mod 10.)

So g does what I want; its period mod 2⋅3^k (for k≥1) is 2⋅3^k+1, and we get the sequence of m_i above.

Of course, all this only shows that g does what I want. None of this shows that h does what I want. I don't know how to prove that. But that's why I think it's a good candidate, anyway.

But this is a pretty silly problem, so I'm not really intending to work on this further...

Obviously, I haven't been posting much here lately. Here's another entry for the "problem dump" series -- two math problems I don't really intend to work on (at least not at the moment). I'll probably put this up on my website later.

Actually, I'm a little surprised to find that I haven't written anything about this here earlier. Oh well. Here we go.

Let's consider the game of Snake; except instead of playing it on a grid, we're going to play it on an arbitrary finite [simple] graph. We assume the snake starts at length 1 -- the game begins by the "computer" (who acts adversarially) picking a starting spot for the snake and a starting spot for the fruit. When the snake consumes the fruit (and thereby grows by 1), the computer picks a new spot for the fruit, which cannot be somewhere currently covered by the snake. We'll say the player wins if the snake covers the whole graph. If the game goes on infinitely, I guess that's a draw, but we'll give it to the computer.

(Here are some obvious ones -- if a spanning subgraph of a graph is winnable, then so is the whole thing; any cycle is winnable, so so is any graph with a Hamilton cycle; in order to be winnable, a graph must have a Hamilton path. But like I said, I'm not going to put all my notes here.)

So the general question then is, for which graphs can the player always win? (Hence why I said draws go to the computer.) Now this question is not necessarily that concrete; there might not be any nice characterization. I have bunch of notes about necessary conditions and sufficient conditions for this, but I'm not going to list them all here. I do, however, have two specific questions about this that I'd like to ask.

So -- you'll notice I didn't give a totally formal specification of the rules above, and there's a reason for that. When you formalize the rules, you realize there's the question: Should a snake of length 2 be allowed to turn around? As in, move its head to the current location of the tail. If you write the rules in the obvious manner, this is entirely legal, but it seems kind of unintuitive. So we can have two variants of the game: The weak game, where this is allowed; and the strong game, where it is not. (Note that you could consider graphs with multiple edges, and say that then in the strong game you're allowed to turn around if there's a double edge; but I'm restricting to simple graphs for reasons you'll see shortly.)

There is at least one graph that is weakly winnable but not strongly winnable, namely, a path of length 3. So, question number one: Are there any other such graphs? I suspect the answer is no but have been unable to prove it. Hence the restriction to simple graphs -- if I'm right, then unless the "underlying simple graph" is P₃, adding multiple edges simply won't affect anything. (And it's easy to see how it affects P₃.)

Here's a second question. When I initially mentioned this problem to John, he suggested that whether a graph is winnable or not should depend only on its topology. But this is not so; I have examples of (weakly or strongly) winnable graphs that can be subdivided to be made non-winnable. However, I have been unable to find an example of a (weakly or strongly) non-winnable graph which can be subdivided to be made winnable. So, question number two: If a graph is non-winnable (weakly or strongly), is the same true of any subdivision of it? For this question I don't really have a good idea what the answer should be. My guess would be yes, but I wouldn't be all that surprised if someone found a counterexample.

By the way, someone -- I forget who, unfortunately -- suggested that you could also play Snake on infinite graphs, with the win condition being that you grow arbitrarily large (now it's only a "draw" if the game goes on infinitely but your size stays bounded). But that seems like a pretty different problem, so I'm not going to consider that here.

-Harry