Harry/Sniffnoy/Steve ([info]sniffnoy) wrote,
2010-07-23 18:18:00
  • Previous
  • Memorize
  • Share
  • Next

Entries without even a hint of a story leave a bad taste in my mouth. Let's clear things out.

(So does posting so much. I guess I'll just have to go silent for a while after this. :) )

...with the tale of Harry and Josh and the Quest for the Unspecified Constant!

SO! When we last left our heroes, they were attempting to prove that neither numbers of the form (2*3^m+1)3^n+1, nor those of the form (4*3^m+1)3^n+1, could be large powers of 2; and had just gotten ahold of this ancient scroll paper from 1979 on writing numbers to two different bases simultaneously. Contained therein was a proof that (among many other things - see the paper for generality!) the number 2^m, when written to base 3, has at least (approximately; I'm going to be loose here) (log m)/(log log m + C) nonzero digits... where C was some constant well-known by the ancients but lost to us that the author hadn't bothered to specify.

Well, that's not great, but it didn't seem *too* bad, as long as the constant isn't too large. So I guess I have to comb through the scroll paper to see just what that is.

The trouble is, the scroll paper was writtten in cryptic language a weird way that didn't make it at all clear where the constant even came from. Most of the proof was by contradiction. Eventually I puzzled it out: The proof involved choosing an arbitrary constant, c_1, and then splitting into two cases based on whether or not some constraint based on c_1 was satisfied. If it was, you were done, with C approximately equal to c_1. The "if not" was the rest of the proof; it showed that that case was impossible. But how, when c_1 was arbitrary? Well, it wasn't really arbitrary; it involved defining a bunch more constants, c_2 through c_10, and at one point it used the assumption that c_1>c_7+c_8 - because c_1 was chosen arbitrarily, and none of the other constants depended on it, so we can certainly choose it to be at least that large. So *really* c_1 is not arbitrary, but rather is c_7+c_8+ε.

OK. So now it's just a matter of determining c_7 and c_8, which of course means determining c_2 through c_6 as well... (c_9 and c_10 were irrelevant). Well, I go through all that, and put it all together (though I misread one thing, which turned out to be irrelevant), and it didn't look terrible. It was approximately 1+2C_3, where C_3 (not to be confused with c_3, of course!)... where C_3 was some *again* unspecified constant, pulled in from another ancient text paper.

So, OK. If C_3 is, like, 2, then that's about 5, which isn't great, but is still probably doable, right? As long as C_3 is small.

Go to the library, track it down, open it up... fortunately this one was rather more straightforward about the constant. It was 48600.

...about then I realized that we didn't have to prove that numbers of the forms above couldn't be large powers of 2 in the first place, so a lot of time was wasted but we got the result we wanted. So yay.

(I should note, the proof was based on the theory of linear forms in logarithms; what I had to go to the library to track down was one of Baker's old papers where he set out explicit lower bounds on these. I also took out a more recent book by Baker on transcendental number theory, from about 1990, since it was right near by, in the hope that it would contain a better bound, but no. However, I realize now that I could have saved some time there if I had just looked at Wikipedia - it lists a better, more recent bound from just three years after that book (and links to the paper, too). Unfortunately, it still involves a constant which is in this case 1174136684544*log(6).)

-Harry
Tags: integer complexity

  • Post a new comment

    Error

    switch

    Your IP address will be recorded 

     
    Help
  • 3 comments

[info]joshuazelinsky

July 24 2010, 01:07:49 UTC 1 year ago

1174136684544*log(6) is a lot smaller than 48^600. (Also still trying to again work out the other ugly constant we care about for the upper bound. I'm going to wait announcing a specific number this time until I'm very sure I've actually got the right value.)

[info]sniffnoy

July 24 2010, 05:02:21 UTC 1 year ago

Sure, but for the purposes of the story, it's not much different, as it's still A. way too large and B. ultimately irrelevant.

[info]joshuazelinsky

July 24 2010, 18:18:42 UTC 1 year ago

Yes, I know. Permit me my tiny silliness please.
Create an Account
Forgot your login or password?
Facebook Twitter More login options
English • Español • Deutsch • Русский…