Loading ...
Sorry, an error occurred while loading the content.

Titanic irregular primes

Expand Messages
  • d.broadhurst@open.ac.uk
    Titanic irregular primes: proposal for a Caldwell top-20 In 1847 Gabriel Lame (1795-1870) gave a talk to l Academie des Sciences in Paris, in which he claimed
    Message 1 of 5 , Nov 29, 2001
    • 0 Attachment
      Titanic irregular primes: proposal for a Caldwell top-20

      In 1847 Gabriel Lame (1795-1870) gave a talk to l'Academie
      des Sciences in Paris, in which he claimed to have proved
      Fermat's last theorem.

      Joseph Liouville (1809-1882) rose to his feet to object.
      He pointed out that Lame had wrongly assumed unique
      factorization in the ring of p-cyclotomic integers,
      generated by exp(2*pi*i/p) with prime p.

      Yet from this contretemps came something of real value.
      Ernst Eduard Kummer (1810-1893) had already studied
      the failure of unique factorization in cyclotomic fields
      and soon formulated a theory of ideals, which was later
      developed by Julius Wilhelm Richard Dedekind (1831-1916).

      Kummer was able to prove Fermat's last theorem for all prime
      exponents that are "regular".

      A regular prime is (clearly) one that is not irregular.

      A prime p is irregular if and only if p divides the class
      number of the cyclotomic field generated by exp(2*pi*i/p).

      Equivalently, but more conveniently, an odd prime p is
      irregular if and only if p divides the numerator of a
      Bernoulli number B(2*n) with 2*n+1 < p.

      Bernoulli numbers are obtained from Taylor coefficients of

      x/(exp(x)-1) = sum_{k>=0} B(k) x^k / k!

      from which it follows that B(2*n+1)=0 for n>0.

      The first Bernoulli number B(2*n) with a non-trivial
      numerator greater than n is B(12)=-691/2730,
      from which it follows that 691 is an irregular prime.

      The smallest irregular prime is 37, which divides
      the numerator of B(32)=-7709321041217/510.

      By analyzing all the Bernoulli numbers up to B(2*n),
      one may find all the irregular primes up to 2*n+3.

      By 1874, Kummer was able to prove Fermat's last theorem
      for all odd prime exponents less than 165, save for the
      8 irregular primes

      p = 37, 59, 67, 101, 103, 131, 149, 157

      which divide the numerators of B(n), with

      n = 32, 44, 58, 68, 24, 22, 130, 62

      respectively. Moreover 157 divides the numerator of
      B(110), as well as that of B(62), and hence is assigned
      an irregularity index of 2. Note that to determine
      divisibility we need not compute the large numerators of
      these Bernoulli numbers; modular arithmetic suffices.

      In 1857, Kummer was awarded a 3000 FF prize, in a
      competition for which he had not entered. L'Academie des
      Sciences had been holding this prize in reserve, hoping
      for a full proof of Fermat's last theorem. One may surmise
      that Kummer's analysis showed them that their challenge
      was too hard and that in consequence they chose his work
      as the next best thing.

      Kummer hoped that the number of irregular primes might be
      finite. This was disproved by Jensen, in 1915. A simple
      proof that the irregular primes are infinite in number, by
      contradiction of the converse, was given in [Carlitz_1954].
      Ironically, it is not known whether the number of regular
      primes is infinite, though there is both an heuristic
      argument [Siegel_1964] and also extensive empirical evidence
      [Wagstaff_1978] to support the conjecture that regular
      primes comprise an asymptotic proportion exp(-1/2) = 60.65%
      of all primes, with 39.35% being consequently irregular.

      Irregular primes have been enumerated, up to increasing
      limits, in [Johnson_1974], [Johnson_1975], [Wagstaff_1978],
      [Tanner_Wagstaff_1987], [Buhler_at_al_1992],
      [Buhler_at_al_1993], [Buhler_at_al_2000], with
      increasing efficiency of the modular arithmetic.

      The most recent of these works determined all the
      irregular primes less than 12,000,000.

      Samuel Wagstaff has identified a variety of larger irregular
      primes, by factorizing some of the Bernoulli numbers up to
      B(300). For example, one finds in

      http://www.loria.fr/~zimmerma/records/wagstaff

      the 322-digit irregular prime

      2*3*B(298)/(149*26113*223529*371472263795653589766634977803).

      Recently, I began to look for titanic irregular primes,
      with at least 1000 decimal digits, and soon found the
      following 8 instances:

      2*3*B(674)/337

      -2*3*5*17*173*B(688)/(43*33617*1323797*465776197109)

      2*3*B(734)/(157*367*6547*75401119*170508089)

      2*3*59*B(754)/(13*29*883462452530494157)

      2*3*23*B(814)/(11*37*69803353*335055893*351085907\
      *520460183*30348030379*17043083582983)

      -2*3*5*17*107*B(848)/(53*1789*4519*5051145078213134269)

      -2*3*5*1229*B(1228)/(307*3399696012787)

      -2*3*5*7*13*619*1237*B(1236)/(103*939551962476779\
      *157517441360851951)

      all of which were proven prime by Marcel Martin's Primo.
      The largest has 2276 decimal digits.

      Bouk de Water and I have continued ECM factorization
      attempts on the numerators of Bernoulli numbers up
      to B(2000), finding the titanic irregular prime

      -2*3*5*23*B(748)/(11*17*3853*138192830377045750339532383)

      and the following 4 probable primes,

      2*3*107*B(1802)/(17*53*17448089)

      -2*3*5*7*13*19*37*103*109*307*613*919*B(1836)/(17*3517\
      *3927024469727)
      2*3*11*23*1871*B(1870)/(5*17)

      -2*3*5*7*13*B(1884)/(157*3697*173981)

      The smallest of these PrPs has 3641 digits; the largest has
      3844 digits. All 4 are feasible targets for proof ECPP.

      I thank Richard Crandall for advice. Historical information
      was gleaned from a wide variety of websites.
      Paulo Ribenboim's excellent account in "The new book of
      prime number records" provided most of the appended
      references. I have been able to read all but the second
      and last of these 9 papers.

      In view of the quality and quantity of these published
      works, Bouk and I hope that Chris Caldwell will initiate
      a top-20 of titanic irregular primes, beginning with
      our modest 9, under codes shared with Marcel Martin.
      The Cert_Val confirmations of these 9 are lodged in

      http://groups.yahoo.com/group/primeform/files/Irreg/

      If any ECPP enthusiast fancies proving any of our four
      12-kilobit irregular PrPs, Bouk and I would be most
      grateful for the cycles, in exchange for shared credit.

      David Broadhurst
      29 November 2001

      References:

      [Carlitz_1954]
      L.Carlitz,
      Note on irregular primes,
      Proc. Amer. Math. Soc. 5, 1954, 329-331.

      [Siegel_1964]
      C.L.Siegel,
      Zu zwei Bemerkungken Kummers,
      Nachr. Akad. d. Wiss. Goettingen, Math. Phys. KI., II, 1964, 51-62.

      [Johnson_74]
      W.Johnson,
      Irregular prime divisors of the Bernoulli Numbers,
      Math. Comp. 28, 1974, 653-657.

      [Johnson_1975]
      W.Johnson,
      Irregular primes and cyclotomic invariants,
      Math. Comp. 29, 1975, 113-120.

      [Wagstaff_1978],
      S.S.Wagstaff Jr,
      The irregular primes to 125000,
      Math. Comp. 32, 1978, 583-591.

      [Tanner_Wagstaff_1987]
      J.W.Tanner and S.S.Wagstaff Jr,
      New congruences for the Bernoulli numbers,
      Math. Comp. 48, 1987, 341-350.

      [Buhler_at_al_1992],
      J.P.Buhler, R.E.Crandall and R.W.Sompolski,
      Irregular primes to one million,
      Math. Comp. 59, 1992, 717-722.

      [Buhler_at_al_1993]
      J.Buhler, R.Crandall, R.Ernvall and T.Metsankyla,
      Irregular primes and cyclotomic invariants to four million,
      Math. Comp. 61, 1993, 151-153.

      [Buhler_at_al_2000]
      J.Buhler, R.Crandall, R.Ernvall, T.Metsankyla and M.Shokrollahi,
      Irregular primes and cyclotomic invariants to 12 million,
      J. Symbolic. Comput. 11, 2000, 1-8.
    • Phil Carmody
      ... [SNIP] ... My guess would be that Irregular primes are thus as archivable as Sophie Germains. Phil Don t be fooled, CRC Press are _not_ the good guys.
      Message 2 of 5 , Nov 30, 2001
      • 0 Attachment
        On Thu, 29 November 2001, d.broadhurst@... wrote:
        > Titanic irregular primes: proposal for a Caldwell top-20
        [SNIP]
        > Kummer was able to prove Fermat's last theorem for all prime
        > exponents that are "regular".

        My guess would be that Irregular primes are thus as archivable as Sophie Germains.

        Phil


        Don't be fooled, CRC Press are _not_ the good guys.
        They've taken Wolfram's money - _don't_ give them yours.
        http://mathworld.wolfram.com/erics_commentary.html


        Find the best deals on the web at AltaVista Shopping!
        http://www.shopping.altavista.com
      • Chris Caldwell
        Ironies seem to abound in mathematics. It is so easy to show that almost all numbers are transcendental, but to determine if a given number is transcendental
        Message 3 of 5 , Nov 30, 2001
        • 0 Attachment
          Ironies seem to abound in mathematics. It is so easy to show
          that almost all numbers are transcendental, but to determine if a
          given number is transcendental can be very difficult.

          I will indeed grant the request for the "top 20" category irregular
          primes, which are both so common (in theory) and so rare (in
          lists of proven titanics).

          Thank you David for

          1. Knowing the criteria, and giving the explicit references.

          2. Writing a fine note which I hope I can use (with credit of course)
          on the top-20 page and in the glossary

          3. Showing there is effort involved in finding them.

          The last criteria is never stated explicitly, but consider the category
          "odd primes" or
          "primes congruent to 7 mod 8." There would be no trouble finding
          references for these
          (use the dozens of sum of squares articles... for the latter), but surely
          they do not
          deserve a comment. They are too easy to recognize.

          To make your request perfect, all you need to add is one thing: a quick way
          for the
          parser to estimate the size... they had a nice Fourier expansion don't
          they? I need
          to get my books out--but right now back to class!

          Chris.
        • d.broadhurst@open.ac.uk
          Chris Caldwell asked for ... zeta(2*n) = 1 + 1/2^(2*n) + 1/3^(2*n) + .... so you will (almost) always get the number digits of a titanic irregular prime from
          Message 4 of 5 , Nov 30, 2001
          • 0 Attachment
            Chris Caldwell asked for

            > a quick way for the parser to estimate the size...

            Oh that one is easy:

            |B(2*n)|=2*(2*n)!*zeta(2*n)/(2*pi)^(2*n)

            zeta(2*n) = 1 + 1/2^(2*n) + 1/3^(2*n) + ....

            so you will (almost) always get the number digits of
            a titanic irregular prime from setting the zeta to 1.
            and taking logs. Your parser can handle log factorial,
            so you only need to tell it log(2*pi).

            Best

            David
          • Phil Carmody
            ... The top 25 hits on google between them yield nothing better than: numbers.computation.free.fr/Constants/Miscellaneous/bernoulli.html
            Message 5 of 5 , Nov 30, 2001
            • 0 Attachment
              On Fri, 30 November 2001, Chris Caldwell wrote:
              > To make your request perfect, all you need to add is one thing: a quick way
              > for the
              > parser to estimate the size... they had a nice Fourier expansion don't
              > they? I need
              > to get my books out--but right now back to class!
              >

              The top 25 hits on google between them yield nothing better than:

              numbers.computation.free.fr/Constants/Miscellaneous/bernoulli.html
              <<<
              log|N_2k| = 2klog(k)+O(k).
              >>>
              However, there's no indication of the size of the error term, so this approximation might be useless.

              On the same page there are also approximations for the Bernoulli numbers themselves, so as long as submitters factor the denominator back in, you should be OK.

              (Don't bother trying to look at that page unless you use a graphical browser and a MS operating system - it's a MS-Frottage-generated non-conformant mess.)

              Phil

              Don't be fooled, CRC Press are _not_ the good guys.
              They've taken Wolfram's money - _don't_ give them yours.
              http://mathworld.wolfram.com/erics_commentary.html


              Find the best deals on the web at AltaVista Shopping!
              http://www.shopping.altavista.com
            Your message has been successfully submitted and would be delivered to recipients shortly.