![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoySo, 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)=fn(10). Finally, define h(n)=gn(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⋅2q+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)=an doesn't work; we all know that's periodic mod any m. But what about tetration? f(n)=H4(a,n)?
Well as best I can tell mod any m that's eventually constant! Because, look -- an mod m, that depends on n mod φ(m), right? (At worst.) So if you have, like, aaan, mod m, well that depends on aan mod φ(m), which depends on an 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 m1>m, and its period mod m1 was some m2>m1, 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 gn(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, mi=2⋅3i+1. (Here i starts from 0, with m0=m.) Right, this works because, OK, mod any 3k (here k≥1), 2 is a generator, right? It has order 2⋅3k-1.
So what if we were to artificially slow things down? That function f I described has the property that, for 10|n, f9(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 3k, should have period 2⋅3k+1, because we've taken that 2⋅3k-1 and stretched it out by a factor of 9. (And this should also be the case mod 2⋅3k because e.g. the mod 2 is determined by the mod 10.)
So g does what I want; its period mod 2⋅3k (for k≥1) is 2⋅3k+1, and we get the sequence of mi 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...
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)=fn(10). Finally, define h(n)=gn(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⋅2q+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)=an doesn't work; we all know that's periodic mod any m. But what about tetration? f(n)=H4(a,n)?
Well as best I can tell mod any m that's eventually constant! Because, look -- an mod m, that depends on n mod φ(m), right? (At worst.) So if you have, like, aaan, mod m, well that depends on aan mod φ(m), which depends on an 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 m1>m, and its period mod m1 was some m2>m1, 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 gn(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, mi=2⋅3i+1. (Here i starts from 0, with m0=m.) Right, this works because, OK, mod any 3k (here k≥1), 2 is a generator, right? It has order 2⋅3k-1.
So what if we were to artificially slow things down? That function f I described has the property that, for 10|n, f9(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 3k, should have period 2⋅3k+1, because we've taken that 2⋅3k-1 and stretched it out by a factor of 9. (And this should also be the case mod 2⋅3k because e.g. the mod 2 is determined by the mod 10.)
So g does what I want; its period mod 2⋅3k (for k≥1) is 2⋅3k+1, and we get the sequence of mi 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...
