From: victor@ccr-p.ida.org (Victor S. Miller) Newsgroups: sci.math.research Subject: Re: Integers than cannot be generators Date: 09 Jul 1998 08:44:54 -0400 >>>>> "Anthony" == "Anthony F Badalamenti" writes: Anthony> Any integer that is a square cannot be a generator for Zq Anthony> because 2 divides q-1 for every prime q >2. Anthony> Are there any other results stating that certain kinds of Anthony> integers cannot be generators for any primes > 2? Anthony> Many thanks -- Tony Badalamenti What you're looking for is Artin's conjecture. In it's weak form it says that for any integer not 0, +/- 1 or a square is a primitive root for infinitely many primes. A refined version of the conjecture gives a formula for the relative density of such primes (always positive for the allowed integers). This conjectures has been proven subject to the Extended Riemann Hypothesis for a collection of L-functions. Unconditional results are much harder to come by. The best result is a result of Murthy and Murthy who show that among the above allowed integers, there are at most 3 exceptions, but we don't know what they are! Presumably there are no exceptions but at present it can't be prove without assuming the ERH. -- Victor S. Miller | " ... Meanwhile, those of us who can compute can hardly victor@ccr-p.ida.org | be expected to keep writing papers saying 'I can do the CCR, Princeton, NJ | following useless calculation in 2 seconds', and indeed 08540 USA | what editor would publish them?" -- Oliver Atkin ============================================================================== From: jarweinst@aol.com (JarWeinst) Newsgroups: sci.math Subject: Re: Artin Conjecture Date: 20 Aug 1998 03:55:21 GMT Near-layperson terms? You got it. May I assume you're familiar with modular arithmetic? For instance, the integers modulo 5 (notated Z/5Z) can be represented by the set {0,1,2,3,4}; they are inherited with the natural operations of multiplication and addition, but in doing these operations the product/sum shall be "reduced mod 5," meaning replaced by the remainder upon division by 5. In Z/5Z, 2+3=0, 2+4=1, 3*3=4, etc. All in all a very natural concept, if you think about it. Artin's conjecture deals with the _multiplicative_ structure of Z/pZ for integral primes p, with particular emphasis on modular exponentiation. Note that when we list the powers of 2 mod 5, we have 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 3. So each of the nonzero elements of Z/5Z are some power of 2. When this happens, (that is, when every nonzero element of Z/pZ is a power of a simgle element g), we say 2 is a primitive root mod 5 (or, in general, that g is a primitive root mod p). Examples: 3 is also a primitive root mod 5, and 2 is a primitive root mod 11. It is known (for instance, Ireland and Rosen, _A Classical Intro to Modern Number Theory_, that there exists a primitive root g mod p for every prime p. Artin's conjecture is the heuristic dual: for every integer g, will there always exist a prime p for which g is a primitive root? Will there be an infinite number of such p? (Well, certain conditions must be placed on g; g must not be unity, or -1, or a square; such things rule out the possibility of g being a primitive root immediately.) When g = 10, the question goes back to Gauss, who noticed that the decimal expansions of certain fractions (say, 1/7) have "maximal length:" 1/7 has maximal length because 1/7 = .142857142857...., and the repeating part has 6 = 7-1 digits. Gauss asked if there were infinitely many p for which the repeating part of 1/p has (p-1) digits. This condition turns out to be the same as 10 being a primitive root mod p. It's a tough question. It seems to have parallels in elementary number theory: one may ask whether for an integer q do there exist infinitely many primes p for which q is a _square_ mod p, and the Quadratic Reciprocity Law (Gauss again) takes care of this; the answer is yes, about half of the primes will satisfy the requirement. Gauss also worked out "cubic" and "biquadratic" reciprocity laws to handle the question for cubes and fourth powers respectively. But no such generalization seems to exist for primitive roots. The question is tantamount to asking whether for a given g are there an infinite amount of prime cyclotomic fields in which g splits completely into prime ideals. Such questions in math are generally nearly impossible to ask. I believe, though, it has been proven that there exists one integer g (I don't know which one!) for which there exists an infinite number of primes p mod which (hah!) g is primitive. ============================================================================== From: nikl+sm000315@pchelwig1.mathematik.tu-muenchen.de (Gerhard Niklasch) Newsgroups: sci.math Subject: Re: Artin Conjecture Date: 20 Aug 1998 13:09:07 GMT In article <35DB34F7.324B@watson.ibm.com>, Cliff writes: |> Can anyone explain, in near-layperson terms, what the "Artin Conjecture" |> is? If that is not possible, can anyone explain what this is at |> all? It is said to be one of the most important unsolved |> mathematical problems today. There's more than one statement going by this name. For a very readable introduction to the Artin Conjecture about primitive roots, see H.W.Lenstra Jr., `Euclidean Fields' (3 parts), in The Mathe- matical Intelligencer 2 #1 (1979), 6--15, 2 #2 (1980), 73--77 and 99--103. This Artin Conjecture can be stated as saying that for a given positive integer g, not a square, infinitely many primes p have the property that g^k for 0 < k < p covers all the p-1 nonzero residue classes mod p. (It can also be phrased in the rather more fancy language of class field theory, and then becomes a statement about the splitting behaviour of primes in abelian extensions of the field Q of rationals.) This `conjeture' was proved by Hooley in 1967 assuming certain generalized Riemann hypotheses. So zeta functions (of number fields) have something to do with the matter. However, there is a far deeper Artin Conjecture involving zeta functions of not necessarily abelian Galois extensions of Q and their decomposition as a product of Riemann's zeta function and certain L functions attached to representations of the Galois group involved (`Artin L functions'). One consequence of the general conjecture can be explained in terms of zeros of zeta functions in the critical strip (i.e., if all those generalized Riemann hypotheses are true, on the line `Re z = 1/2'); namely, when K is a subfield of the field L which is Galois over Q and when the function \zeta_K vanishes at the point s in the critical strip, then so does \zeta_L (and one can even say something about the orders of vanishing). It is quite feasible and quite amusing to check this experimentally on the first several zeros, say for a field of degree 6, normal closure of a non-cyclic cubic field, e.g. using PARI-GP. Enjoy, Gerhard -- * Gerhard Niklasch * spam totally unwelcome * http://hasse.mathematik.tu-muenchen.de/~nikl/ ******* all browsers welcome * This .signature now fits into 3 lines and 77 columns * newsreaders welcome