Harry goes to the library
Jun. 11th, 2010 09:52 pmOK, I've reached the final stages of my tedious classification of numbers n with d(n)<21d(2). (And, FWIW, I misremembered earlier - d(2049) and d(321) are in fact less than 21d(2).) But instead of working on that, I decided to do something else I've been putting off instead - actually looking up the earlier papers on this that I hadn't already read.
Of course, there hasn't exactly been a lot done on this problem in the first place, but of what little there is, I hadn't actually bothered to read much of it. What there mostly didn't tell us much we didn't already know, but there was still a few relevant papers I hadn't bothered to look at, so today I went and did that. (Hooray for working on a problem so little-studied that it's pretty easy to go and read *all* of the literature on it.) Two of them were just tidbits in what was apparently a recurring feature in AMM by Guy on news on unsolved problems; nothing new there.
The other two I couldn't find online so I went down to the library and found the actual paper copies. One was a short 3-page thing by Daniel Rawsthorne, the other was the original Dutch paper by Mahler and Popken that people keep citing has having introduced the problem.
The Rawsthorne paper told me nothing new, but it was very helpful in another way that it gives a proof[0] (by induction, of course) of g_2(n)=(8/9)g(n) for n>=6, which means that when we write everything up, we won't have to redo that. As I mentioned earlier, we don't want to bring in my earlier classification of numbers n with D(n)=0, because the methods are entirely different from everything else we're doing, and it takes a huge amount of space to explain. (Hm, perhaps sometime I should go back and rewrite that thing from a more informed point of view; right now I find the way I wrote it to be kind of silly.) Which means we need that statement to serve as the base case for our "induction".
I did find it kind of amusing that he asks the question of whether, when f(a+b)=f(a)+f(b), you necessarily have a=1 or b=1, but without enough computing power to find the first counterexample (126483083=6+126483077), he can only answer, yup, it's true for a+b<=3^10. Well, that's how math goes...
The Mahler and Popken paper... I decided to ignore. Because while it may be credited with the idea, it really didn't look relevant. And, you know, it was in Dutch. (Though the abstract was in English, interestingly enough.) And it was 15 pages long and I didn't want to photocopy it all.
The paper is called "A Maximum Problem in Arithmetic" for a reason - that's what it's about. What's the largest number you can make with addition, multiplication, and a supply of n x's? Of course, we're just concerned with what happens when x=1, in which case, this is a much easier question than the inverse notion, integer complexity. OK, it's in Dutch, so I didn't exactly *read* it as such, but I couldn't find anything resembling integer complexity. Maybe they came up with the idea and mentioned it, but I doubt they did anything with it. If really necessary, I can look it up again later.
(It's worth noting that that paper was published in 1953, but no other work on integer complexity seems to appear until Guy started writing about it in the 1980s. Well, in the section in Unsolved Problems in Number Theory on it, Guy also cites a 1962 paper of Conway's, "π in four 4's", but from the title that didn't sound to relevant so I didn't bother to look it up.)
Observation: I'm still surprised at not having seen anywhere else the observation that f(2^a*3^b)=2a+3b for a≤10, despite the fact that this is quite easy. And Rawsthorne even proves that g_2(n)=(8/9)g(n) for n≥6, from which it's possible to infer that f(2^a*3^b)=2a+3b for a≤13, but he doesn't do that either! Everyone else just seems to state it's true for a≤2. It seems ridiculous that I could have been the first one to notice this but it really seems so. (Of course, Arias said he had done a bunch that he hadn't published, so strictly speaking even though I don't see it in his paper, there's a good chance he realized the connection considerably before Josh and I ever started working on this.)
OK. Seriously need to get around to sitting down and reading Arias's paper sometime. He actually does look at a bunch of the same things we're looking at, and he made conjectures pretty similar to ours. It doesn't look like he proved what we have (and Josh's upper bound stuff is definitely new, no doubt about that), but I really need to sit down some time and examine it...
-Harry
[0]Well, actually, he credits that proof to Selfridge. EDIT June 23: The previous content of this footnote was false.
Of course, there hasn't exactly been a lot done on this problem in the first place, but of what little there is, I hadn't actually bothered to read much of it. What there mostly didn't tell us much we didn't already know, but there was still a few relevant papers I hadn't bothered to look at, so today I went and did that. (Hooray for working on a problem so little-studied that it's pretty easy to go and read *all* of the literature on it.) Two of them were just tidbits in what was apparently a recurring feature in AMM by Guy on news on unsolved problems; nothing new there.
The other two I couldn't find online so I went down to the library and found the actual paper copies. One was a short 3-page thing by Daniel Rawsthorne, the other was the original Dutch paper by Mahler and Popken that people keep citing has having introduced the problem.
The Rawsthorne paper told me nothing new, but it was very helpful in another way that it gives a proof[0] (by induction, of course) of g_2(n)=(8/9)g(n) for n>=6, which means that when we write everything up, we won't have to redo that. As I mentioned earlier, we don't want to bring in my earlier classification of numbers n with D(n)=0, because the methods are entirely different from everything else we're doing, and it takes a huge amount of space to explain. (Hm, perhaps sometime I should go back and rewrite that thing from a more informed point of view; right now I find the way I wrote it to be kind of silly.) Which means we need that statement to serve as the base case for our "induction".
I did find it kind of amusing that he asks the question of whether, when f(a+b)=f(a)+f(b), you necessarily have a=1 or b=1, but without enough computing power to find the first counterexample (126483083=6+126483077), he can only answer, yup, it's true for a+b<=3^10. Well, that's how math goes...
The Mahler and Popken paper... I decided to ignore. Because while it may be credited with the idea, it really didn't look relevant. And, you know, it was in Dutch. (Though the abstract was in English, interestingly enough.) And it was 15 pages long and I didn't want to photocopy it all.
The paper is called "A Maximum Problem in Arithmetic" for a reason - that's what it's about. What's the largest number you can make with addition, multiplication, and a supply of n x's? Of course, we're just concerned with what happens when x=1, in which case, this is a much easier question than the inverse notion, integer complexity. OK, it's in Dutch, so I didn't exactly *read* it as such, but I couldn't find anything resembling integer complexity. Maybe they came up with the idea and mentioned it, but I doubt they did anything with it. If really necessary, I can look it up again later.
(It's worth noting that that paper was published in 1953, but no other work on integer complexity seems to appear until Guy started writing about it in the 1980s. Well, in the section in Unsolved Problems in Number Theory on it, Guy also cites a 1962 paper of Conway's, "π in four 4's", but from the title that didn't sound to relevant so I didn't bother to look it up.)
Observation: I'm still surprised at not having seen anywhere else the observation that f(2^a*3^b)=2a+3b for a≤10, despite the fact that this is quite easy. And Rawsthorne even proves that g_2(n)=(8/9)g(n) for n≥6, from which it's possible to infer that f(2^a*3^b)=2a+3b for a≤13, but he doesn't do that either! Everyone else just seems to state it's true for a≤2. It seems ridiculous that I could have been the first one to notice this but it really seems so. (Of course, Arias said he had done a bunch that he hadn't published, so strictly speaking even though I don't see it in his paper, there's a good chance he realized the connection considerably before Josh and I ever started working on this.)
OK. Seriously need to get around to sitting down and reading Arias's paper sometime. He actually does look at a bunch of the same things we're looking at, and he made conjectures pretty similar to ours. It doesn't look like he proved what we have (and Josh's upper bound stuff is definitely new, no doubt about that), but I really need to sit down some time and examine it...
-Harry
[0]
