From barryrsmith@gmail.com Thu Feb 16 19:19:22 2006 Return-Path: Received: from mailbox3.ucsd.edu (mailbox3.ucsd.edu [132.239.1.55]) by euclid.ucsd.edu (8.11.7p1+Sun/8.11.6) with ESMTP id k1H3JRo16575 for ; Thu, 16 Feb 2006 19:19:27 -0800 (PST) Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.192]) by mailbox3.ucsd.edu (8.13.5/8.13.5) with ESMTP id k1H3JN8B046488 for ; Thu, 16 Feb 2006 19:19:23 -0800 (PST) Received: by zproxy.gmail.com with SMTP id 9so324993nzo for ; Thu, 16 Feb 2006 19:19:23 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:references; b=AsUzcUnW+F1q9ysUi/Iwe8gzCNYVXi/Ar7GGRffx5fulDAPjwQuusjtUwMcgg9UWgev9gssl2jswtycRyc69PTr71Kw5/x4miv+B4uPljWdUrk0n0wpwjeyy0ikzBBM9a5ITYxUyfnfxggt2PCZckneQ9GGiinffbZR5P9/T+Vs= Received: by 10.65.124.15 with SMTP id b15mr662094qbn; Thu, 16 Feb 2006 19:19:22 -0800 (PST) Received: by 10.65.145.7 with HTTP; Thu, 16 Feb 2006 19:19:22 -0800 (PST) Message-ID: <5850a51c0602161919x6d1afc56uf5a7d23134a01225@mail.gmail.com> Date: Thu, 16 Feb 2006 19:19:22 -0800 From: Barry Smith To: William Stein Subject: Re: bernfrac In-Reply-To: <200602161704.01083.wstein@ucsd.edu> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_301_222994.1140146362892" References: <200601082158.34196.wstein@ucsd.edu> <5850a51c0602161614p322616f4rc531cbf4be749296@mail.gmail.com> <200602161704.01083.wstein@ucsd.edu> X-Greylisting: NO DELAY (Qualified relay host); processed by UCSD_GL-v2.1 on mailbox3.ucsd.edu; Thu, 16 February 2006 19:19:24 -0800 (PST) X-Spam-Level: Level X-Spamscanner: mailbox3.ucsd.edu (v1.6 Aug 4 2005 15:27:38, -2.5/5.0 3.0.4) X-MailScanner: PASSED (v1.2.8 30263 k1H3JN8B046488 mailbox3.ucsd.edu) X-UIDL: 362c5beaf91a5a30761f6a80adeeae20 X-Bogosity: Unsure, tests=bogofilter, spamicity=0.520000, version=0.95.2 X-UID: Status: RO X-Status: RC X-KMail-EncryptionState: N X-KMail-SignatureState: N X-KMail-MDN-Sent: ------=_Part_301_222994.1140146362892 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Unfortunately, Daniel Shanks extensively studied fields corresponding to primes of the first type, and published a table of the class numbers of the first hundred such fields, which includes primes up to 169339. To compute this high with the method I suggested would require computing Bernoulli numbers up to B_112892. Furthermore, Gunter Lettl published a table of the class numbers of the first 50 fields corresponding to primes of the second type, which includes primes up to 990151. In these fields, they get enough control over the regulator to apply the analytic class number formula and calculate the class number. However, given a specific prime of one of thes= e two forms, only two Bernoulli numbers need to be calculated mod p to determine the class number, so most of the Bernoulli numbers are not needed. Perhaps Joe Buhler's algorithm could do this quickly. Also, I hop= e to extend these results someday to give congruences for class numbers of fields of higher degree than 3. This is a good excuse to commence work on that project. By the way, I was wondering on the way home how efficient it would be to calculate B_{n} by interpolating the sums of the nth powers of the first k natural numbers for k=3D1 to n+1 with an n+1 degree polynomial and read of = the constant coefficient. I suppose these sums might involve too many computations. Barry On 2/16/06, William Stein < wstein@ucsd.edu> wrote: > > On Thursday 16 February 2006 16:14, you wrote: > > Thanks for your previous e-mail about bernfrac. I found your talk > > today very interesting. I have a couple of results whereby I can > > calculate class numbers of cyclic cubic fields of prime conductor p > > for primes p of the form p =3D (a^2 + 27)/4 and of the form p =3D (1 + > > 27*b^2)/4 if I can compute a couple of Bernoulli numbers. In > > particular, in the first case, the class number h is characterized by > > the congruence > > > > h \equiv -3/2 B_{r}/r B_{2*r}/(2*r) mod p where r is (p-1)/3 > > > > and in the second case, > > > > h \equiv -1/18 B_{r}/r B_{2*r}/(2*r) mod p where r is (p-1)/3. > > > > I have been toying with the idea of making a big table of class > > numbers, but I am not very tech savvy and I have a lot to work on as > > it is. > > Cool. This is exactly the sort of thing I hoped you'd get interested > in when I saw your talks. We can do something together, since it > might be a nice application of the table of B_k for all k < 10^5 that > I'm computing right now (and which will be done in a day, since the > computer is computing above 95000 right now). > > > Also, I have been wondering if calculating the inverses of numbers mod > > p would be any faster than the usual algorithm using the following > > algorithm: > > if you want the inverse of a mod p, run the Euclidean algorithm with > > a*p + 1 and p^2 as your starting values instead of a and p. The first > > remainder you get that is less than p is the inverse of a mod p. It > > saves you the trouble of having to backtrack once you find that the > > GCD of a,p is 1, but on the other hand, you have to make a comparison > > of the remainder with p at each step. The number of steps to reach > > the inverse in my method can be shown to be the same as the number of > > steps to reach the GCD when running the Euclidean algorithm with a and > > p. Of course, the original algorithm is so fast that I don't suppose > > it matters. I just think mine is charming, and a little mysterious. > > I don't know. It would be fun to implement just to watch it run. > There are also supposedly subquadratic asymptotically fast (x)gcd > algorithms, which might be relevant to the above. I just don't > know. Explaining your algorithm would be a really good idea for > the graduate student research seminar. I'm trying to find some students > to talk so I can start it up again. (I didn't do it in January since > I was busy preparing for SAGE days.) > > William > ------=_Part_301_222994.1140146362892 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Unfortunately, Daniel Shanks extensively studied fields corresponding to primes of the first type, and published a table of the class numbers of the first hundred such fields, which includes primes up to 169339.  To compute this high with the method I suggested would require computing Bernoulli numbers up to B_112892.  Furthermore, Gunter Lettl published a table of the class numbers of the first 50 fields corresponding to primes of the second type, which includes primes up to 990151.  In these fields, they get enough control over the regulator to apply the analytic class number formula and calculate the class number.  However, given a specific prime of one of these two forms, only two Bernoulli numbers need to be calculated mod p to determine the class number, so most of the Bernoulli numbers are not needed.  Perhaps Joe Buhler's algorithm could do this quickly.  Also, I hope to extend these results someday to give congruences for class numbers of fields of higher degree than 3.  This is a good excuse to commence work on that project.

By the way, I was wondering on the way home how efficient it would be to calculate B_{n} by interpolating the sums of the nth powers of the first k natural numbers for k=3D1 to n+1 with an n+1 degree polynomial and read of the constant coefficient.  I suppose these sums might involve too many computations.

Barry

On 2/16/06, William Stein < wstein@ucsd.edu> wrote: On Thursday 16 February 2006 16:14, you wrote:
> Thanks for your previous e-mail about bernfrac.  I found= your talk
> today very interesting.  I have a couple of re= sults whereby I can
> calculate class numbers of cyclic cubic fields = of prime conductor p
> for primes p of the form p =3D (a^2 + 27)/4 and of the form p =3D = (1 +
> 27*b^2)/4 if I can compute a couple of Bernoulli numbers. = ; In
> particular, in the first case, the class number h is char= acterized by
> the congruence
>
> h \equiv -3/2 B_{r}/r B_{2*r}/(2*r)= mod p where r is (p-1)/3
>
> and in the second case,
>> h \equiv -1/18 B_{r}/r B_{2*r}/(2*r) mod p where r is (p-1)/3.
>
> I have been toying with the idea of making a big table of clas= s
> numbers, but I am not very tech savvy and I have a lot to work on= as
> it is.

Cool.  This is exactly the sort of thin= g I hoped you'd get interested
in when I saw your talks.  We can do something together, sinc= e it
might be a nice application of the table of B_k for all k < 10^5= that
I'm computing right now (and which will be done in a day, since th= e
computer is computing above 95000 right now).

> Also, I have been wondering if calculating the inverses of num= bers mod
> p would be any faster than the usual algorithm using the f= ollowing
> algorithm:
> if you want the inverse of a mod p, run= the Euclidean algorithm with
> a*p + 1 and p^2 as your starting values instead of a and p. &= nbsp;The first
> remainder you get that is less than p is the inverse= of a mod p.  It
> saves you the trouble of having to backt= rack once you find that the
> GCD of a,p is 1, but on the other hand, you have to make a compari= son
> of the remainder with p at each step.  The number of = steps to reach
> the inverse in my method can be shown to be the same= as the number of
> steps to reach the GCD when running the Euclidean algorithm with a= and
> p.  Of course, the original algorithm is so fast tha= t I don't suppose
> it matters.  I just think mine is charm= ing, and a little mysterious.

I don't know.  It would be fun to implement just to watch= it run.
There are also supposedly subquadratic asymptotically fast (x)g= cd
algorithms, which might be relevant to the above.  I just d= on't
know.  Explaining your algorithm would be a really good i= dea for
the graduate student research seminar.  I'm trying to find so= me students
to talk so I can start it up again.  (I didn't do = it in January since
I was busy preparing for SAGE days.)

William<= br>

------=_Part_301_222994.1140146362892--