![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoySo I don't know if I'd mentioned this before. Suppose you take n, and you know that the only powers of 2 with defect less than nd(2) are those that are less than 2^n. Then you can conclude that ||2^a*3^b||=2a+3b for all a≤n+9. (Barring a=b=0, as always.)
Now I'd classified all numbers of defect less than 21d(2), so we should be able to prove this for a≤30, right?
Thing is - well, it's easy to check an individual number is not a power of 2, but how about an infinite family? (Just that it contains no *large* powers of 2, of course.) Say it's numbers of the form c*3^m+1 (c fixed). Well, one thing you can do is to note that c has to be 5 or 7 mod 8, which eliminates lots of things right off the bat. But then for what remains, you can note, if c*3^m+1=2^k, well, 2 is a generator mod every power of 3, so 2*3^(m-1) | k, in particular 2*3^(m-1)≤k, and so you've got exponential≥super-exponential, so you can get some pretty strict bounds on a and m (so for given c, you only need check finitely many m, and vice versa).
OK, that was simple. But once you get to 19d(2), you have to deal with a more general sort of infinite family, (3^n+1)3^m+1. Well, that's not a problem, that doesn't work mod 8. Or even mod 2, for that matter. OK, let's go to 20d(2). Now you have to deal with (2*3^n+1)3^m+1. (Also 2(3^n+1)3^m+1, but mod 2 takes care of that.) This is a bit more problematic - mod 8 doesn't cause a problem, and indeed, this *can* equal a small power of 2 (n=1, m=2 gets you 64), so no sort of modular arithmetic will suffice on its own. OK, how about the above trick? But here c=2*3^n+1 can be arbitrarily large, so that no longer suffices.
Hm. OK, let's set that aside for now. Go on to 21d(2). Aside from stuff that doesn't work mod 2, we also have (4*3^n+1)3^m+1. Same problem as before. Now here we don't know any examples where this is a power of 2, so maybe some sort of modular arithmetic can prove this one? It's certainly not obvious.
So here we should have had this true for a≤30, but instead only had it true for a≤28. Josh comes up with some more modular arithmetic constraints, and then I do a computer search of some more, but they don't resolve the problem. I feel like there has to be some approach we're missing.
I think, you know what would be convenient? If there were some lower bound on the number of nonzero digits that had to appear in ternary expansions of powers of 2. That would provide a nice quick solution. Josh says he thinks he's seen something like this in Unsolved Problems in Number Theory, but it turns out to not be quite relevant[0]. (There's a conjecture that every sufficiently large power of 2 must contain a 0 when written in ternary, but that's kind of the opposite of what we're looking for!) Searching internet turns up a preprint of Lagarias actually titled "Ternary expansions of powers of 2", but again it doesn't talk about this problem. (Apparently Erdös conjectured that every sufficiently large power of 2 contains a 2 when written in ternary, and it concerns a generalization of this.) Couldn't find anything else quite relevant.
So I decided to ask on MathOverflow. I thought perhaps I would generalize the question, to nonzero digits of powers of a, written to base b (assuming no power of a is a power of b), but decided against it, on the basis that it seemed these sorts of problems were hard even in specific cases. Well, I mentioned the generalization in the question, but the actual question itself was just about the specific case.
Well, within a day, two people pointed me to this paper, which does indeed prove it in generality! In quite a bit more generality than I had even thought of, really. (To recover what I wanted, just plug in, uh, what I called "a" for a, and 0 for α.)
The bound's kind of small, so we may have to check quite a few cases, but that should be easy, and hey! It's a bound! It should be doable! And it also means that if we wanted to continue further, past 21d(2), this could, in principle, handle whatever cases arose (though possibly with exponential difficulty).
So, yay.
...assuming we can figure out how to compute that constant, anyway. The paper doesn't seem to make that immediately clear, and with the small numbers we're working with, it'll probably be relevant...
EDIT 2 hours later: Yeah, we're now seriously considering the possibility that this is going to be too small to actually be able to use effectively. Still, unless we come up with some other ideas, we have to check it out...
-Harry
[0]Of course, it must seem a bit odd to be discouraged that what you're looking for doesn't appear in Unsolved Problems in Number Theory. After all, there's a good chance that just means the problem is solved.
Now I'd classified all numbers of defect less than 21d(2), so we should be able to prove this for a≤30, right?
Thing is - well, it's easy to check an individual number is not a power of 2, but how about an infinite family? (Just that it contains no *large* powers of 2, of course.) Say it's numbers of the form c*3^m+1 (c fixed). Well, one thing you can do is to note that c has to be 5 or 7 mod 8, which eliminates lots of things right off the bat. But then for what remains, you can note, if c*3^m+1=2^k, well, 2 is a generator mod every power of 3, so 2*3^(m-1) | k, in particular 2*3^(m-1)≤k, and so you've got exponential≥super-exponential, so you can get some pretty strict bounds on a and m (so for given c, you only need check finitely many m, and vice versa).
OK, that was simple. But once you get to 19d(2), you have to deal with a more general sort of infinite family, (3^n+1)3^m+1. Well, that's not a problem, that doesn't work mod 8. Or even mod 2, for that matter. OK, let's go to 20d(2). Now you have to deal with (2*3^n+1)3^m+1. (Also 2(3^n+1)3^m+1, but mod 2 takes care of that.) This is a bit more problematic - mod 8 doesn't cause a problem, and indeed, this *can* equal a small power of 2 (n=1, m=2 gets you 64), so no sort of modular arithmetic will suffice on its own. OK, how about the above trick? But here c=2*3^n+1 can be arbitrarily large, so that no longer suffices.
Hm. OK, let's set that aside for now. Go on to 21d(2). Aside from stuff that doesn't work mod 2, we also have (4*3^n+1)3^m+1. Same problem as before. Now here we don't know any examples where this is a power of 2, so maybe some sort of modular arithmetic can prove this one? It's certainly not obvious.
So here we should have had this true for a≤30, but instead only had it true for a≤28. Josh comes up with some more modular arithmetic constraints, and then I do a computer search of some more, but they don't resolve the problem. I feel like there has to be some approach we're missing.
I think, you know what would be convenient? If there were some lower bound on the number of nonzero digits that had to appear in ternary expansions of powers of 2. That would provide a nice quick solution. Josh says he thinks he's seen something like this in Unsolved Problems in Number Theory, but it turns out to not be quite relevant[0]. (There's a conjecture that every sufficiently large power of 2 must contain a 0 when written in ternary, but that's kind of the opposite of what we're looking for!) Searching internet turns up a preprint of Lagarias actually titled "Ternary expansions of powers of 2", but again it doesn't talk about this problem. (Apparently Erdös conjectured that every sufficiently large power of 2 contains a 2 when written in ternary, and it concerns a generalization of this.) Couldn't find anything else quite relevant.
So I decided to ask on MathOverflow. I thought perhaps I would generalize the question, to nonzero digits of powers of a, written to base b (assuming no power of a is a power of b), but decided against it, on the basis that it seemed these sorts of problems were hard even in specific cases. Well, I mentioned the generalization in the question, but the actual question itself was just about the specific case.
Well, within a day, two people pointed me to this paper, which does indeed prove it in generality! In quite a bit more generality than I had even thought of, really. (To recover what I wanted, just plug in, uh, what I called "a" for a, and 0 for α.)
The bound's kind of small, so we may have to check quite a few cases, but that should be easy, and hey! It's a bound! It should be doable! And it also means that if we wanted to continue further, past 21d(2), this could, in principle, handle whatever cases arose (though possibly with exponential difficulty).
So, yay.
...assuming we can figure out how to compute that constant, anyway. The paper doesn't seem to make that immediately clear, and with the small numbers we're working with, it'll probably be relevant...
EDIT 2 hours later: Yeah, we're now seriously considering the possibility that this is going to be too small to actually be able to use effectively. Still, unless we come up with some other ideas, we have to check it out...
-Harry
[0]Of course, it must seem a bit odd to be discouraged that what you're looking for doesn't appear in Unsolved Problems in Number Theory. After all, there's a good chance that just means the problem is solved.
