Two obvious observations
Dec. 27th, 2011 04:08 pmA good way to phrase some of the questions about the overall growth rate of integer complexity ||n|| is, what's limsup (||n||/log n)? (We know liminf ||n||/log n = 3/log 3).
So, e.g., we have the obvious bounds that it's at least 3/log 3 (>2.73) and at most 3/log 2 (<4.33). I'd like it if we could show that it's strictly greater than 3/log 3 (show that ||n|| is not asymptotic to 3log3n), but that doesn't look like it's actually going to work. If ||2^n||=2n for all n>0, then it has to be at least 2/log 2 (>2.88). Josh showed that it's at most 27/log 1260 (<3.79), and has suggested based on the numerical data that it ought to be at most 2/log 2. (<2.89), which might make it exactly 2/log 2. (Of course, others have suggested that, contrary to what Josh and I have tried to show, that it ought to be exactly 3/log 3 after all; I'll admit to not having stared too closely at the numerical data on this myself, so if you actually care about that you should probably look up what other people have written on the matter...)
Of course, some of these statements are a bit stronger -- Josh showed that ||n||≤27log1260n for all n, not just sufficiently large n, and to say that there are actually infinitely many n satisfying ||n||=2log2n exactly[0] is a bit stronger than just saying that the limsup is at least 2/log 2, but it's pretty close and it's a nice way of summing it up.
Why is this worth noting even though it's obvious? Because somehow Josh and I managed to talk about 2/log 2 being the limsup without ever using that term (i.e. writing out the statement explicitly). A bit embarassing to accidentally reinvent standard concepts without noticing...
[0]Note that this would actually force ||2^k||=2k for k>0, since 2log2n can only even be an integer if n is a power of 2; and if it holds for some k, it holds for all smaller k.
Something that started bothering me a bit ago is the curvature of space and the asymmetry of non-Euclidean geometry. In physics, lengths are dimensioned quantities, and areas are lengths squared, etc. But in a space of constant non-zero curvature, the scaling symmetry doesn't work, and you get relations based not on squaring but on trigonometric and hyperbolic functions (which don't even work with dimensioned quantities); I assume with varying curvature it can be even worse. How then do the facts that A. physical space isn't perfectly Euclidean and B. physical length is very definitely not dimensionless fit together? Duh, curvature (Edit: more generally the metric tensor or whatever) is a dimensioned quantity, and mediates the conversions. Kind of obvious, but somehow I missed that and this was really bugging me for a while...
(Yes, I would never have made that mistake if I had ever actually learned any differential geometry. But I haven't.)
-Harry
So, e.g., we have the obvious bounds that it's at least 3/log 3 (>2.73) and at most 3/log 2 (<4.33). I'd like it if we could show that it's strictly greater than 3/log 3 (show that ||n|| is not asymptotic to 3log3n), but that doesn't look like it's actually going to work. If ||2^n||=2n for all n>0, then it has to be at least 2/log 2 (>2.88). Josh showed that it's at most 27/log 1260 (<3.79), and has suggested based on the numerical data that it ought to be at most 2/log 2. (<2.89), which might make it exactly 2/log 2. (Of course, others have suggested that, contrary to what Josh and I have tried to show, that it ought to be exactly 3/log 3 after all; I'll admit to not having stared too closely at the numerical data on this myself, so if you actually care about that you should probably look up what other people have written on the matter...)
Of course, some of these statements are a bit stronger -- Josh showed that ||n||≤27log1260n for all n, not just sufficiently large n, and to say that there are actually infinitely many n satisfying ||n||=2log2n exactly[0] is a bit stronger than just saying that the limsup is at least 2/log 2, but it's pretty close and it's a nice way of summing it up.
Why is this worth noting even though it's obvious? Because somehow Josh and I managed to talk about 2/log 2 being the limsup without ever using that term (i.e. writing out the statement explicitly). A bit embarassing to accidentally reinvent standard concepts without noticing...
[0]Note that this would actually force ||2^k||=2k for k>0, since 2log2n can only even be an integer if n is a power of 2; and if it holds for some k, it holds for all smaller k.
Something that started bothering me a bit ago is the curvature of space and the asymmetry of non-Euclidean geometry. In physics, lengths are dimensioned quantities, and areas are lengths squared, etc. But in a space of constant non-zero curvature, the scaling symmetry doesn't work, and you get relations based not on squaring but on trigonometric and hyperbolic functions (which don't even work with dimensioned quantities); I assume with varying curvature it can be even worse. How then do the facts that A. physical space isn't perfectly Euclidean and B. physical length is very definitely not dimensionless fit together? Duh, curvature (Edit: more generally the metric tensor or whatever) is a dimensioned quantity, and mediates the conversions. Kind of obvious, but somehow I missed that and this was really bugging me for a while...
(Yes, I would never have made that mistake if I had ever actually learned any differential geometry. But I haven't.)
-Harry
