mersenneforum.org (https://www.mersenneforum.org/index.php)
-   carpetpool (https://www.mersenneforum.org/forumdisplay.php?f=145)
-   -   Prime numbers norms of modulo cyclotomic polynomials (https://www.mersenneforum.org/showthread.php?t=22584)

 carpetpool 2017-09-17 04:10

Prime numbers norms of modulo cyclotomic polynomials

For any given prime n > 19, and a random prime p = 2*k*n+1, what is the probability there will exist n-1 elements (polynomials) u such that norm(Mod(u,polycylo(n)) = p? (Here polycyclo(n) is the nth cyclotomic polynomial)

For example, in polycyclo(n), n = 23, p = 599, we see that there exists elements u with norm(Mod(u,polcyclo(23)) = 599, but for prime p = 967 (which is of the form 2*k*23+1), there does not exist any elements u with norm(Mod(u,polcyclo(23)) = 967. Of the primes p = 1 (mod 2*23), for which there does exist elements with norm(Mod(u,polcyclo(23)) = p, they are seemingly random, as there is no special / additional arithmetical or modular condition on them besides having p = 1 (mod 2*23).

The same is true with polcyclo(29), except there being fewer primes p = 1 (mod 2*29) for which there are elements u such that norm(Mod(u,polcyclo(29)) = p. As p = 4931 this is true for but not p = 5279 (both primes of the form 2*29*k+1).

There is a similar concept for all polcyclo(n) with class number > 1, (although this question is for prime n) where some primes p = 1 (mod n), there will exist elements u and norm(Mod(u,polcyclo(n)) = p, while others will not. Are the primes 'randomly' split up somehow? Is there, and what is the general probability for a prime p = 1 (mod n) that there will be norm solutions in the field polycyclo(n), given polycyclo(n) has class number c?

For instance, what is the probablity (for each of the corresponding cyclotomic fields below), that there will be an element u with norm(Mod(u,polcyclo(n)) = p, and prime p = k*n+1 (2*k*n+1 since all of these n are odd primes).

p = 45520819, and norm(Mod(u,polcyclo(23)) = p
p = 2913344873, and norm(Mod(u,polcyclo(29)) = p
p = 11661616457, and norm(Mod(u,polcyclo(31)) = p
p = 746726311549, and norm(Mod(u,polcyclo(37)) = p
...

I would like to apply this for all polcyclo(n), if possible. Thanks for help.

 Dr Sardonicus 2017-09-17 13:58

In the field of n-th roots of unity K = Q(\zeta_{n}), the prime numbers p congruent to 1 (mod n) are precisely those which are norms of ideals in the ring of integers [b]O[/b][sub]K[/sub]. Invoking the "assumption of ignorance" that no ideal class is favored over any other, the "obvious" answer is that 1/h of these primes are norms of [i]principal[/i] ideals (that is, are norms of algebraic integers in K), where h is the class number (standard notation).

And in fact this is correct. It may be viewed as a generalization of the equal distribution of primes in arithmetic progressions. See [url=https://core.ac.uk/download/pdf/81969104.pdf]THE ASYMPTOTIC DISTRIBUTION OF PRIME IDEALS IN IDEAL CLASSES[/url]

For the field k = Q(\zeta[sub]23[/sub]) with h = 3 (constructed in advance with bnfinit()), I ran a script to get the actual count for primes up to 100,000. As you can see, it's pretty close to 1/3 of all primes congruent to 1 mod 46.

? v=[];w=[];j=0;l=0;forprime(p=29,100000,if(p%46==1,j++;if(#bnfisintnorm(k,p)>0,l++;w=[p];v=concat(v,w))));print("Up to 100000 there are ",j," primes congruent to 1 mod 46 and ",l," are norms of principal ideals")
Up to 100000 there are 429 primes congruent to 1 mod 46 and 141 are norms of principal ideals

 carpetpool 2017-09-18 05:21

Thanks, Dr Sardonicus. I found a similar result with K = Q(\zeta_{29}), and the program returned this: (note I made an additional script file for this):

parinorm.txt:

normU(k,n,m) =
{
bnf = bnfinit(polcyclo(k));
v=[];
w=[];
j=0;
l=0;
forprime(p=n,m,
if(p%k==1,j++;
if(#bnfisintnorm(bnf,p)>0,l++;w=[p];v=concat(v,w))));
print("Up to 100000 there are ",j," primes congruent to 1 mod k and ",l," are norms of principal ideals")

---

(21:45) gp > read( "parinorm.txt" );
(21:47) gp > normU(29,31,100000)
Up to 100000 there are 345 primes congruent to 1 mod k and 46 are norms of principal ideals
(21:56) gp > print(v)

345/46 = 7.5, which is close to 8, the class number of field K = Q(\zeta_{29}). I would expect the same for larger n in K = Q(\zeta_{n}).

What I am curious about is how are primes p = 1 (mod n) which are NOT norms of algebraic integers in field K = Q(\zeta_{n}), represented as norms of ANY type of integer u, belonging to field.

For instance, take K = Q(\zeta_{29}), and prime p = 13457 = 1 (mod 29). There exists an ideal with norm 13457 in Q(\zeta_{29}), and in addition to that, there also exists an element u such that norm(Mod(u,polcyclo(29))) = 13457. This can be generalized to other cyclotomic fields by replacing 29 with n, and we have norm(Mod(u,polcyclo(n)). Better yet, norm(Mod(u,(x^n-1)/(x-1))) = U(n) is a cyclotomic-like divisiblity sequence with term U(29) = 13457. These are true for ideals, which are also principal.

How about primes p, which the ideals are NOT principal. Take K = Q(\zeta_{29}), and prime p = 22621 = 1 (mod 29). There are ideals with norm p = 22621 in K = Q(\zeta_{29}), however none of these ideals are principal and we do not have an algebraic integer, or element u such that norm(Mod(u,polcyclo(29)) = 22621. Is there a way to generalize the non-principal unique ideals which correspond to norm 22621 in K = Q(\zeta_{29}), to K = Q(\zeta_{n}). In other words, is it possible to come up with a sequence of non-principal ideals, and a cyclotomic divisiblity sequence with the 29th term, U(29) = 22621?

I do belive there is a way to do this, using other types of non-algebraic integers.

Any further thoughts, comments concerns? Thanks.

 Dr Sardonicus 2017-09-18 16:22

If K is a number field, K/Q is a normal (Galois) extension, [b]O[/b][sub]K[/sub] its ring of algebraic integers, p is a prime number, and p[b]O[/b][sub]K[/sub] is the product of distinct prime ideals of norm p, then either all of these ideals are principal, or they are all non-principal. If they are non-principal, then there are no [i]integers[/i] of norm p. In this case, let P be a prime ideal of norm p, and let c be its class in the class group. If there is a fractional ideal X of norm 1 whose class is c[sup]-1[/sup], then XP will be a principal ideal of norm p, but its principal generators will be non-integer fractions in K.

If Q is a prime ideal in the "numerator" of X, there has to be a corresponding Q' conjugate to Q in the "denominator" (this uses the assumption that K/Q is a normal extension).

Thus, any fractional ideal of norm 1 is a product of factors of the form Q/Q' where Q is a prime ideal in [b]O[/b][sub]K[/sub].

I don't know in general how to determine whether such a product can be in any given ideal class, but I do know one case where it is [i]not[/i] possible. If K has class number h = 2, then in the fractional ideal Q/Q', either Q and Q' are both principal, or they are both in the sole non-principal class, so that Q/Q' is principal. So in this case, all fractional ideals with norm 1 are a product of principal ideals, and are therefore principal.

So if K/Q is normal with class number h = 2, and p a prime number with p[b]O[/b][sub]K[/sub] the product of non-principal prime ideals of norm p, then there is no element of K having norm p.

The smallest cyclotomic example appears to be K = Q(\zeta_{39}) and p = 79.

 carpetpool 2017-09-20 03:12

Thanks, I will look further into these properties, I did additional tests on the fields K = Q(\zeta_{n}), for n = 31, 37, 41, 43 and found

(22:23) gp > normU(31,37,100000)
Up to 100000 there are 320 primes congruent to 1 mod k and 40 are norms of principal ideals

For n = 31, 37 they are checked up to all primes <= 100000, n = 41, 43 they are checked up to all primes <= 300000,

One question I came up with is for each prime n, what is the smallest prime which is a norm of a principal ideal in the cyclotomic field K = Q(\zeta_{n})?

Let a(n) be the smallest prime that is a norm principal ideal in the cyclotomic field K = Q(\zeta_{P(n)}) and P(n) is the nth prime,

The terms are a(n) = 3, 7, 11, 29, 23, 53, 103, 191, 599, 4931, 5953, 32783, 101107, 178021,...

For example, the a(3) = 11, because 5 is the third prime, and the smallest prime p that is a norm of a principal ideal in the cyclotomic field K = Q(\zeta_{5}) is 11.

Is there an easy method or formula for finding these terms? If someone is willing to explore further and a(15) through a(25) (the smallest primes p that are norms of principal ideals in the cyclotomic fields K = Q(\zeta_{n}), for n = 47, 53, 59, 61, 67, 73, 79, 83, 89, 97)

I considered adding an [URL="https://oeis.org/A292579"]OEIS[/URL] to it, I am not sure if this is of any additional interest however.

Thanks for help.

 carpetpool 2017-10-02 03:15

Cyclotomic Splitting Fields

Another idea on the cyclotomic fields with class number > 1 is that K = Q(\zeta_{n}) is split into some number of separate fields. Each prime p = 1 (mod n) falls into the category of one of these splitting fields (ideal classes), and can be expressed as the norm of a "principal ideal" in that splitting field.

In K23 = Q(\zeta_{23}) the primes p = 1 (mod 23) are split into two different ideal classes depending on weather p or 47*p is a norm of a principal ideal.

In K29 = Q(\zeta_{29}) the primes p = 1 (mod 29) are split into two different ideal classes depending on weather p or 59*p is a norm of a principal ideal.

In K31 = Q(\zeta_{31}) the primes p = 1 (mod 31) are split into three different ideal classes depending on weather p, 311*p, or 1117*p is a norm of a principal ideal.

In K37 = Q(\zeta_{37}) the primes p = 1 (mod 37) are split into two different ideal classes depending on weather p, or 149*p is a norm of a principal ideal.

What are the cases for Kn = Q(\zeta_{n}) (primes n = 41, 43, 47)?

Are my assertions correct for Kn (n = 23, 29, 31, 37)?

Thanks for help.

 Dr Sardonicus 2017-10-02 13:43

Determining the least prime in an arithmetic progression is already known to be a [i]very[/i] hard problem. The classic result is due to Kulik. In a sense it is satisfying (given the difficulty of the problem), but it is far from what is suspected.

What might be more interesting here, is, for a given n, noting the class number h = h(n) for the field of n-th roots of unity, and the number k of primes congruent to 1 (mod n) you have to go through until you find one that is the norm of [i]principal[/i] ideal. My guess is, k will not be terribly larger than h, but it could be much smaller.

BTW, if n is a prime power q[sup]f[/sup], then 1 - \zeta_{n} is a principal generator of the (unique) prime ideal of norm q.

 carpetpool 2017-10-03 02:00

[QUOTE=Dr Sardonicus;469017]Determining the least prime in an arithmetic progression is already known to be a [i]very[/i] hard problem. The classic result is due to Kulik. In a sense it is satisfying (given the difficulty of the problem), but it is far from what is suspected.

What might be more interesting here, is, for a given n, noting the class number h = h(n) for the field of n-th roots of unity, and the number k of primes congruent to 1 (mod n) you have to go through until you find one that is the norm of [i]principal[/i] ideal. My guess is, k will not be terribly larger than h, but it could be much smaller.

BTW, if n is a prime power q[sup]f[/sup], then 1 - \zeta_{n} is a principal generator of the (unique) prime ideal of norm q.[/QUOTE]

Yes Dr. Sardonicus, and this would make for a very interesting problem.

Given the cyclotomic field Kn = Q(\zeta_{n}), the smallest prime p > n which is a norm of principal ideal are:

3, 7, 5, 11, 7, 29, 17, 19, 11, 23, 13, 53, 29, 31, 17, 103, 19, 191, 41, 43, 23, 599, 73, 101, 53, 109, 29, 4931, 31, 5953, 97, 67, 103, 71, 73, 32783, 191, 157, 41, 101107, 43, 178021, 89, 181, 599,...

The one for K47 and larger n in Kn is unknown.

I am unable to find the next terms to this sequence. Do you care to help with it further?

 Dr Sardonicus 2017-10-03 04:34

[QUOTE=carpetpool;469082]

The one for K47 and larger n in Kn is unknown.

I am unable to find the next terms to this sequence. Do you care to help with it further?[/QUOTE]No thanks. The computations are simply too appalling. The class numbers for the primes 3 to 163 are given at [url=https://oeis.org/A055513]OEIS A055513[/url]. For 47, it's already 695. After that, the class number grows with frightening speed...

 carpetpool 2017-10-03 06:16

[QUOTE=Dr Sardonicus;467944]In the field of n-th roots of unity K = Q(\zeta_{n}), the prime numbers p congruent to 1 (mod n) are precisely those which are norms of ideals in the ring of integers [b]O[/b][sub]K[/sub]. Invoking the "assumption of ignorance" that no ideal class is favored over any other, the "obvious" answer is that 1/h of these primes are norms of [i]principal[/i] ideals (that is, are norms of algebraic integers in K), where h is the class number (standard notation).

And in fact this is correct. It may be viewed as a generalization of the equal distribution of primes in arithmetic progressions. See [url=https://core.ac.uk/download/pdf/81969104.pdf]THE ASYMPTOTIC DISTRIBUTION OF PRIME IDEALS IN IDEAL CLASSES[/url]

For the field k = Q(\zeta[sub]23[/sub]) with h = 3 (constructed in advance with bnfinit()), I ran a script to get the actual count for primes up to 100,000. As you can see, it's pretty close to 1/3 of all primes congruent to 1 mod 46.
[/QUOTE]

I would like to announce one result involving the field K = Q(\zeta_{23}).

**Conjecture/Observation**

For a prime p = 1 (mod 23), p is a norm of a principal ideal if and only if there are 3 solutions to x^3-x-1 = 0 (mod p).

To see this is the same list as the one quoted in Dr. Sardonicus's first post, I modified a PARI/GP script which includes a bnf construction of any number field, and k.

normU(k,w,n,m) =
{
bnf = bnfinit(w);
v=[];
w=[];
j=0;
l=0;
forprime(p=n,m,
if(p%k==1,j++;
if(#bnfisintnorm(bnf,p)>0,l++;w=[p];v=concat(v,w))));
print("Up to 100000 there are ",j," primes congruent to 1 mod k and ",l," are norms of principal ideals")

here w is any polynomial, and the script finds primes n < p < m, and p = 1 (mod k) such that p is the norm of a principal ideal in the field that w defines.

The list above is the same as the one Dr. Sardonicus's first post, and also the primes p = 1 (mod 23) which satisfy x^3-x-1 = 0 (mod p).

In the field K = Q(\zeta_{29}), what is the polynomial w for which if p = 1 (mod 29), and p is the norm of a principal ideal, then p satisfies w = 0 (mod p), if it is not principal, then p does not satisfy w = 0 (mod p)?

Update: For K23, this works for any polynomial w having a discriminant D of -23. In fact replacing x^3-x-1 with x^2+x+6, x^2+3*x+8, x^3+3*x^2+2*x-1,... would all give the same result.

Thanks for help.

 Dr Sardonicus 2017-10-03 14:19

[QUOTE=carpetpool;469111]I would like to announce one result involving the field K = Q(\zeta_{23}).

**Conjecture/Observation**

For a prime p = 1 (mod 23), p is a norm of a principal ideal if and only if there are 3 solutions to x^3-x-1 = 0 (mod p). [/QUOTE]
Let K be the field of n-th roots of unity. Let Cl(K) be the ideal class group of K, h its order. What you seek is a defining polynomial for the Hilbert Class Field of K. This will have degree h over K. Among the many fascinating properties of L/K, if P is a prime ideal of K, then P[b]O[/b][sub]L[/sub] splits into h distinct ideals (so [apart from possible extraneous factors of the polynomial discriminant] the polynomial splits into distinct linear factors over [b]O[/b][sub]K[/sub]/P precisely when P is principal.

For n = 23, it turns out that the quadratic subfield k = Q(sqrt(-23)) already has class number 3, and (fortuitously) the class number does not increase when you extend up to K.

It is well known that the cubic polynomial f = x^3 - x - 1 defines the Hilbert Class Field L of k. Accordingly, by Class Field Theory, everything you would want to be true about factorizations of f mod p, is true. The prime ideal P in [b]O[/b][sub]k[/sub] is principal if and only if f splits completely in the residue field [b]O[/b][sub]k[/sub]/P. If -23 is a quadratic non-residue (mod p), then f has one linear and one quadratic factor (mod p); P = p[b]O[/b][sub]k[/sub] is prime, and [b]O[/b][sub]k[/sub]/P is the field of p^2 elements.

If -23 is a quadratic residue (mod p), then p[b]O[/b][sub]k[/sub] = PP' where P and P' are of degree 1; the residue fields [b]O[/b][sub]k[/sub]/P and [b]O[/b][sub]k[/sub]/P' both have p elements. In this case, f (mod p) remains irreducible if P and P' are non-principal, but splits into linear factors (mod p) if P and P' are principal.

If w^2 - w + 6 = 0, then P is principal when P = x + y*w for integers x and y; or p = x^2 + x*y + 6*y^2, or (simple argument) p = X^2 + 23*Y^2 for integers X and Y.

Fortuitously, K has the same class number as K, and the join KL has degree 3 over K, so f serves as a defining polynomial for the Hilbert Class Field of K as well as of k.

Unfortunately, this approach doesn't work when K is the field of 29th roots of unity. In this case, all the proper subfields of K have class number 1. But K itself has class number 8, so a defining polynomial for its Hilbert Class Field L has degree 8 over K. The class group is "elementary Abelian," the direct product of 3 cyclic groups of order 2. It is therefore possible (in theory) to determine L/K as the join of quadratic extensions of K, which could be done using Pari's rnfkummer(). Alas, I'm too lazy to try to work out the necessary subgroups of the class group
;-D

In general, determining the Hilbert Class Field of a cyclotomic field is... difficult.

All times are UTC. The time now is 01:06.