Empirically, some large fraction of cubic fields have class# = 1 (i.e., UFD). I don't know their Euclidean status. Except for the sqrt(-N) case, getting large class numbers is hard, and a good fraction of all fields have small class numbers. (empirical) I believe that sqrt14 and maybe sqrt69 have fixed-up norms that provide a Euclidean algorithm. The fixup is something silly but easily computed, like diddling with the power of 2 in the norm. Assuming some version of GRH, every [algebraic?] UFD has a hard-to-compute axiom-of-choice-style norm so that the Euclidean algorithm completes in four steps. [I've got some details wrong here, but you get the flavor.] This might be why the phrase 'Euclidean-for- the-norm' was introduced. 2^(1/5) generates a Euclidean field, with a not-too-hard dimishing norm. The idea is to compute the remainder's standard norm. If that's not smaller than norm(divisor), you adjust the quotient with a choice of ~50 values. Try adding +-1, +-2^1/5, +-4^1/5, etc. At least one will work. [This is my work, based on cutting up the unit cube into 100K boxes.] Maybe, not sure, the bicubic field based on cbrt2 & cbrt5 is a UFD. I've heard that 2^(1/N) is a UFD for N<30, and then later N<50ish. [Hendrik?] Lenstra (in his thesis?) has a way of generating a lot of Euclidean fields. I never understood his trick, but it's not profound. The equations have a generalized Fibonacci look to them -- stuff like x3-x2+1 = 0. If your goal is an infinite class of E.fields, this might be the way to go. Perhaps it's true that x^N - x - 1 generates them. I think you omitted sqrt(-8,-12,-27) from the list of UFDs. Of course the rings are 'incomplete'. No idea about E-ness. I've seen mention of a paper, perhaps <1995, that establishes the superfluity of Euclidean-ness, perhaps by supplying replacements for a GCD algorithm and the other related descents, perhaps by allowing more than two numbers in the descent algorithm. I don't know details, this is my guess about the scheme. Puzzle on adjoining 1^(1/N): I though this was the distinction between regular & irregular primes, and there were about 50% each, empirically. This doesn't match the Masley-Montgomery result. What's my error? What's an example of a totally-complex cubic field? :-)? Rich ________________________________________ From: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] on behalf of Warren Smith [warren.wds@gmail.com] Sent: Thursday, January 05, 2012 9:26 AM To: math-fun@mailman.xmission.com Subject: [EXTERNAL] [math-fun] Unique factorization J.L.Masley & H.M.Montgomery 1975: if the Nth roots of unity (i.e. complex R such that R^N=1) are adjoined to the integers, then we get a ring enjoying "unique factorization into primes" exactly in the following cases: N = 1,3,4,5,7,8,9,11,12,15,16,20,24, 13,17,19,21,25,27,28,32,33,35,36,40,44,45,48,60,84. K.Heegner 1952 & H.Stark 1967: If sqrt(-N) is adjoined to the integers, N>0, then we get a ring enjoying "unique factorization into primes" exactly in the following cases: N = 1,2,3,7,11, 19,43,67,163. In both cases, for the N in the first line there is a known Euclid-like GCD algorithm which proves it. For the N in the second line, the proof is harder. The proof that no other N work is way harder. For example 6 = 2*3 = (1+i*sqrt5)*(1-i*sqrt5) has nonunique factorization for N=5. Exactly for N = 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 and -1,-2,-3,-7,-11, adjoining sqrt(N) to the integers yields a norm-lowering Euclidean algorithm. V.Cioffari 1979: Exactly for N = 2,3,10, adjoining cbrt(N) to the integers yields a norm-lowering Euclidean algorithm. [Also known we get finite sets for 4th roots and 5th roots.] Exactly for (A,B) in the following list, adjoining both sqrt(A) and sqrt(B) to the integers yields a ring with a norm-lowering Euclidean algorithm: (-1, 2), (-1, 3), (-1, 5), (-1, 7), (-2, -3), (-2, 5), (-3, 2), (-3, 5), (-3,-7), (-3, -11), (-3, 17), (-3, -19), (-7, 5) [F.Lemmermeyer 1989-1995] There are only finitely many cubic totally-complex or totally-real-cyclic algebraic number fields with a norm-lowering Euclidean algorithm (H.Davenport 1950; H.Heilbronn 1938). "Totally complex" means none of the roots of the minimal polynomial are real. Totally real means all of them are real. Here "cyclic" means that if you adjoin one root of the minimal polynomial, that is equivalent to adjoining all of them. Almost all cubic real fields are noncyclic. There are only finitely many quartic totally-complex and totally-real algebraic number fields with a norm-lowering Euclidean algorithm (H.Davenport 1950; F.Lemmermeyer 1995, D.A.Clark 1992-6). In all of the above cases, the list of rings was finite. Can we make some such list of N which is INFINITE? Apparently the answer is yes, but I'm not sure anybody has ever proved it in any interesting sense? Adjoining pi to the integers has unique factorization but it is boring/useless because it is nondiscrete and there is no way to multiply to ring elements to get an integer (aside from the obvious). Here are two apparently-infinite lists of N such that adjoining sqrt(N) to the integers yields a ring enjoying unique factorization http://oeis.org/A003172 http://oeis.org/A003655 but in these cases (a) I don't know if anybody ever proved they really are infinite -- I think the question is open -- albeit see H. te Riele & H.Williams: http://www.emis.de/journals/EM/expmath/volumes/12/12.1/pp99_113.pdf for large computations suggesting infinity; (b) even if they are infinite, I think it isn't very interesting/useful unless you have a Euclid algorithm so you can rapidly find GCD, and a notion of norm so we can talk about A being "smaller than" B and thus the "least" factor. These lists if restricted to such cases become finite. So... QUESTION: So what I want, but do not have, is an infinite set of ways to extend the integers into a larger countable ring (but still contained inside the reals or complex numbers or some finite-dimensional -- preferably bounded dimensional -- such space) so that (i) we get unique factorization via norm-based Euclidean algorithm. (ii) we get discreteness, i.e. the number of ring elements in any ball in the complex plane, or anyhow within some finite-dimensional space erected over the integers, is finite. This seems to force us to restrict to ALGEBRAIC number fields. Heilbronn 1938 and/or 1950 conjectured the number of cubic non-cyclic totally-real algebraic number fields with a norm-lowering Euclidean algorithm, was infinite. This conjecture if true would seem to solve my problem. However, I think this conjecture still is open, albeit seems supported by computer evidence, Lemmermeyer: http://www.rzuser.uni-heidelberg.de/~hb3/publ/survey.pdf _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun