lim sup ap, lim inf ap, lim ap
May. 18th, 2021 10:56 pmSo, upper bounds on integer complexity. We know that (for n>1) we have ||n||≤3log3n, and ![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
joshuazelinsky has managed to improve this although he still hasn't published it.
So there are several questions here. The first is, what is the maximum value of ||n||/(log n)? This appears to occur when n=1439, and is about 3.58; however, it never recurs, no other number yields a value that high, so that's probably not what we're really looking for, is it?
A better question would be, what is the limsup of ||n||/(log n)? This is of course a hard question to which we don't know the answer. We know the liminf is 3/(log 3) [about 2.73]; some people have speculated that perhaps this could be the limsup as well, with ||n|| ~ 3log3n. But if ||2^k||=2k for k≥1, then this can't happen, as the limsup must be at least 2/(log 2) [about 2.88].
Josh has previously speculated that the correct value might in fact be equal to 2/(log 2). But really it's hard to get a good read on it; recently I tried graphing it for some pretty large n and I gotta say if I had to guess based on that alone I'd say it's more like 3.2 or so. But who knows? Some other calculations I did recently, which I won't go into here, seem compatible with Josh's idea that it's 2/(log 2)... or maybe it's just 3. We can't really say.
But famously we can do better if we only want to find c such that ||n||≤c log n for almost all n, in the sense that the set of exceptions has natural density 0. So one might ask, what is the infimum of such c? The best known bound on this currently are due to Cordwell et al, and it's about 3.29, so, better than the conjectured value for the maximum!
But here's another question one might ask -- what does one call this value? This may sound like a silly question, but, y'know, this is a useful concept, and it deserves to have a name.
So, more formally: Say (an) is a real-valued sequence. We want to take the infimum (alternatively, supremum) of all c such that {n∈N: an≥c} (respectively, ≤c) has natural density 0. So it's like a limsup (respectively, liminf), but based on natural density. Notably, it can be lower than the limsup (respectively, higher than the liminf), and the two could agree, producing a limit of sorts, even if no actual limit exists.
Fortunately, there seems to be a pre-existing name for, if not this concept, then a very similar one! It turns out that there's a notion of "approximate limsup" and "approximate liminf" (and, when they agree, "approximate limit"); these are denoted "lim sup ap", "lim inf ap", and "lim ap". Now, these are defined in a somewhat different setting, where you're looking at taking a limit of a function f:Rd→R and taking a limit as you approach some point x0, and is based on Lebesgue measure... but the definition is clearly analogous.
So, I'm choosing to reuse that term for this definition. So, Cordwell et al provide our best upper bounds on limsupap ||n||/(log n). :)
Because the thing is that once you name a concept, it makes it easier to think about, and ask more questions about it. Like: What about the liminf? What is liminfap ||n||/(log n)?
I only first thought to ask this question a few days ago. And I realize that I don't really have any idea! It seems kind of like it ought to be 3/(log 3), same as the liminf, but, well, why should it be? I don't see any reason it couldn't be higher! Maybe there is an easy proof, but if so I'm missing it. If it truly is higher, that'd be pretty crazy! Or imagine if the limit didn't exist, but the approximate limit did...
Anyway yeah. Yay for having good names for things.
joshuazelinsky has managed to improve this although he still hasn't published it.So there are several questions here. The first is, what is the maximum value of ||n||/(log n)? This appears to occur when n=1439, and is about 3.58; however, it never recurs, no other number yields a value that high, so that's probably not what we're really looking for, is it?
A better question would be, what is the limsup of ||n||/(log n)? This is of course a hard question to which we don't know the answer. We know the liminf is 3/(log 3) [about 2.73]; some people have speculated that perhaps this could be the limsup as well, with ||n|| ~ 3log3n. But if ||2^k||=2k for k≥1, then this can't happen, as the limsup must be at least 2/(log 2) [about 2.88].
Josh has previously speculated that the correct value might in fact be equal to 2/(log 2). But really it's hard to get a good read on it; recently I tried graphing it for some pretty large n and I gotta say if I had to guess based on that alone I'd say it's more like 3.2 or so. But who knows? Some other calculations I did recently, which I won't go into here, seem compatible with Josh's idea that it's 2/(log 2)... or maybe it's just 3. We can't really say.
But famously we can do better if we only want to find c such that ||n||≤c log n for almost all n, in the sense that the set of exceptions has natural density 0. So one might ask, what is the infimum of such c? The best known bound on this currently are due to Cordwell et al, and it's about 3.29, so, better than the conjectured value for the maximum!
But here's another question one might ask -- what does one call this value? This may sound like a silly question, but, y'know, this is a useful concept, and it deserves to have a name.
So, more formally: Say (an) is a real-valued sequence. We want to take the infimum (alternatively, supremum) of all c such that {n∈N: an≥c} (respectively, ≤c) has natural density 0. So it's like a limsup (respectively, liminf), but based on natural density. Notably, it can be lower than the limsup (respectively, higher than the liminf), and the two could agree, producing a limit of sorts, even if no actual limit exists.
Fortunately, there seems to be a pre-existing name for, if not this concept, then a very similar one! It turns out that there's a notion of "approximate limsup" and "approximate liminf" (and, when they agree, "approximate limit"); these are denoted "lim sup ap", "lim inf ap", and "lim ap". Now, these are defined in a somewhat different setting, where you're looking at taking a limit of a function f:Rd→R and taking a limit as you approach some point x0, and is based on Lebesgue measure... but the definition is clearly analogous.
So, I'm choosing to reuse that term for this definition. So, Cordwell et al provide our best upper bounds on limsupap ||n||/(log n). :)
Because the thing is that once you name a concept, it makes it easier to think about, and ask more questions about it. Like: What about the liminf? What is liminfap ||n||/(log n)?
I only first thought to ask this question a few days ago. And I realize that I don't really have any idea! It seems kind of like it ought to be 3/(log 3), same as the liminf, but, well, why should it be? I don't see any reason it couldn't be higher! Maybe there is an easy proof, but if so I'm missing it. If it truly is higher, that'd be pretty crazy! Or imagine if the limit didn't exist, but the approximate limit did...
Anyway yeah. Yay for having good names for things.
