mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > carpetpool

Reply
 
Thread Tools
Old 2022-07-24, 18:16   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

33510 Posts
Post Can a generating polynomial of a field extension be written as a composition of two polynomials?

Given two cyclic fields K and L, (K ≠ L), with L being a finite extension of K, is it always possible to come up with two polynomials f(x) and g(x) (both of degree greater than 1), such that f(x) generates a field (isomorphic to) K, and f(g(x)) generates a field isomorphic to L. By "cyclic", I mean that K and L are subfields of some cyclotomic field Q(ζn), where ζn is a primitive n-th root of unity, and Q is the field of rational numbers.

I am more focused on specifically when the extension field L is a cyclotomic field itself, as well as non-trivial compositions.

Some trivial compositions include when f(g(x)) is a cyclotomic polynomial itself, such f(x) = x^2 + 1 = Phi(4,x), g(x) = x^2, and f(g(x)) = x^4 + 1 = Phi(8,x).

Phi(n,x) may not have any trivial compositions, but some polynomial generating a field isomorphic to Q(ζn) may be written as some non-trivial composition.

One example includes the polynomial h = x^4 + 5*x^2 + 5, whose roots are of the form ζ5 - ζ5-1. Adjoining a root of h to Q generates a field isomorphic to Q(ζ5), and h can be written as a composition f(g(x)) where f(x) = x^2 + 5*x + 5, and g(x) = x^2. Adjoining a root of f to Q yields a field isomorphic to the quadratic subfield Q(ζ5 + ζ5-1) of the 5-th cyclotomic field.

My problem can be re-formulated as follows:

Let NL(a,a2,a3,...ad) denote the integer norm of elements of the field L, where d is the degree of L. NL is a homogenous polynomial of degree d in d variables. Let NK denote the integer norm for an element in K.

Since L is an extension of K, every integer s which is a norm of some element in L must also be the norm of some element in K.

More specifically, every polynomial h(x) generating a field isomorphic to L, can be expressed as NK(a,a2,a3,...ak), k being the degree of K, where the ai's are polynomials with intermediate x, and at least one of the ai's is of degree k, and the rest have degree ≤ k.

Is it always possible to find a such set of polynomials a,a2,a3,...ak such that one of the ai's is monic and has degree k, while the rest of the ai's are constant?

As an example, if L is the 5-th cyclotomic field, and K is its corresponding quadratic subfield, then the norm of any element

a + bζ5 + cζ52 + dζ53 can be expressed as the norm of some element u*w + v where w^2 + w - 1 = 0. The corresponding norm is v^2 - u*v - u^2.

The norm of ζ5 - x is Phi(5,x) = x^4 + x^3 + x^2 + x + 1.

Phi(5,x) has the following representation where v = x^2 + x + 1 and u = x:

v^2 - u*v - u^2 = (x^2 + x + 1)^2 - (x^2 + x + 1)*x - x^2 = x^4 + x^3 + x^2 + x + 1.

Since neither u nor v are constant, we conclude that Phi(5,x) does not have a representation as a non-trivial composition of two polynomials. As Phi(5,x) is of degree 4, the only possible non-trivial compositions are where f and g are both of degree 2.

Meanwhile, the previously mentioned polynomial above x^4 + 5*x^2 + 5 = (x^2 + 3)^2 - (x^2 + 3) - 1, and so such a composition exists.


-----


More generally, if the roots of h(x) are of the form ζn - ζn-1 where n is odd, then h(x) is a polynomial whose terms are of even degree, and thus can be written as f(g(x)) where the roots of f(x) are of the form ζn + ζn-1, and g(x) = x^2 + c for some constant c. Thus, a composition (as described) earlier will always exist given the cyclotomic field L = Q(ζn) and its corresponding maximal real subfield K = Q(ζn + ζn-1). These specific compositions can be used to compute the n-th roots of unity in radical form. Namely, these are the primitive divisors of the odd index Lucas polynomials.

It is fairly easy to generate many polynomials of this form: In particular, if the roots of h(x) are sums of cyclotomic integers of the form ζnk - ζn-k, then h(x) is even, and we have a straightforward composition h(x) = f(g(x)) with g(x) = x^2. For example,

h(x) = x^4 + 25*x^2 + 125 has the roots ζ5 + 2*ζ52 - 2*ζ53 - ζn4, and f(x) = x^2 + 25*x + 125.

------

The 7-th and 9-th cyclotomic fields are interesting. For these cyclotomic fields, I was able to find a polynomial (actually, many such polynomials) which can be written as a composition, in two distinct ways:

Consider the polynomial, which generates a field isomorphic to Q(ζ7):

h(x) = x^6 + 14*x^4 + 49*x^2 + 7

h has the roots ζ7 + ζ73 - ζ74 - ζ76.

h can be written as f(g(x)) where f(x) = x^3 + 14*x^2 + 49*x + 7, and g(x) = x^2: (x^2)^3 + 14*(x^2)^2 + 49*(x^2) + 7

It can also be written as a composition where f(x) = x^2 + 7, and g(x) = x^3 + 7*x: (x^3 + 7*x)^2 + 7


Similarly, consider the polynomial, which generates a field isomorphic to Q(ζ9):

h(x) = x^6 + 6*x^4 + 9*x^2 + 3

h has the roots ζ9 - ζ98

h can be written as f(g(x)) where f(x) = x^3 + 6*x^2 + 9*x + 3, and g(x) = x^2: (x^2)^3 + 6*(x^2)^2 + 9*(x^2) + 3

It can also be written as a composition where f(x) = x^2 + 3, and g(x) = x^3 + 3*x: (x^3 + 3*x)^2 + 3

In fact, there are many polynomials generating such fields, where f(x) is a quadratic polynomial, and g(x) is a cubic polynomial.

------

For the 11-th cyclotomic field, there is the previously mentioned composition of h(x) = x^10 + 11*x^8 + 44*x^6 + 77*x^4 + 55*x^2 + 11 with

f(x) = x^5 + 11*x^4 + 44*x^3 + 77*x^2 + 55*x + 11 and g(x) = x^2.

The only other non-trivial decomposition would be where f(x) is a quadratic polynomial (generating a field isomorphic to the quadratic subfield of Q(ζ11)) and g(x) is a quintic polynomial.

I had executed a search within the 11th cyclotomic integers to write the corresponding minimal polynomials as v^2 - u*v + 3*u^2 where v is a monic polynomial of degree 5 and u is an integer.
I was unable to find such a polynomial. The closest candidate I had found was

u = x^5 + 3*x^4 + 8*x^3 + 7*x^2 + 13*x + 5
v = 2*x - 3

and

h(x) = (x^5 + 3*x^4 + 8*x^3 + 7*x^2 + 13*x + 5)^2 - (x^5 + 3*x^4 + 8*x^3 + 7*x^2 + 13*x + 5)*(2*x - 3) + 3*(2*x - 3)^2 =

x^10 + 6*x^9 + 25*x^8 + 62*x^7 + 130*x^6 + 197*x^5 + 280*x^4 + 272*x^3 + 246*x^2 + 123*x + 67

Code:
(10:47) gp > h = x^10 + 6*x^9 + 25*x^8 + 62*x^7 + 130*x^6 + 197*x^5 + 280*x^4 + 272*x^3 + 246*x^2 + 123*x + 67
%25 = x^10 + 6*x^9 + 25*x^8 + 62*x^7 + 130*x^6 + 197*x^5 + 280*x^4 + 272*x^3 + 246*x^2 + 123*x + 67
(10:47) gp > nfisisom(h, polcyclo(11))
%26 = [-x^7 - x^5 - x^3 - x^2 - 1, -x^7 - x^5 - x^2 - x - 1, -x^8 - x^7 - x^5 - x - 1, x^8 + x^7 + x^5 + x^3 + x^2 + x, -x^9 - x^8 - x^7 - x - 1, -x^9 - x^8 - x^6 - x^4 - 1, -x^9 - x^8 - x^6 - x - 1, x^9 + x^8 + x^7 + x^5 + x^2 + x, x^9 + x^8 + x^7 + x^6 + x^4 + x, x^9 + x^8 + x^7 + x^6 + x^5 + x]
This does not mean such a polynomial doesn't exist, although it is very likely it doesn't exist.

------

For the 13-th cyclotomic field, there are many possible was to compose h(x) (since h has degree 12). As the divisors of 12 are [1,2,3,4,6,12], the possible compositions are where the product of the degrees of f(x) and g(x) are 12. Apart from f(x) being a sextic polynomial (degree 6), and g(x) being a quadratic polynomial, I was unable to find any other decompositions.

Interestingly enough, if we revert to the general problem of L not being a cyclotomic field, then I was able to find a many quadratic polynomials f(x) generating the cyclic quadratic subfield of Q(ζ13), quadratic polynomials g(x) such that f(g(x)) generated the quartic subfield of Q(ζ13), and cubic polynomials g(x) such that f(g(x)) generates the sextic maximal real subfield of Q(ζ13).

As an example, if

f(x) = x^2 + 3*x - 27 and g(x) = x^2 + 5, then h(x) = f(g(x)) = (x^2 + 5)^2 + 3*(x^2 + 5) - 27 = x^4 + 13*x^2 + 13 generates the corresponding quartic subfield of Q(ζ13), and if

G(x) = x^3 - 52*x + 31, then H(x) = f(g(x)) = (x^3 - 52*x + 31)^2 + 3*(x^3 - 52*x + 31) - 27 = x^6 - 104*x^4 + 65*x^3 + 2704*x^2 - 3380*x + 1027 generates the corresponding maximal real subfield of Q(ζ13).

Infinitely many intersections of the polynomials x^3 - 52*x + 31 and x^2 + 5 would yield a polynomial generating the 13-th cyclotomic field: the prime powers dividing H(x) are all congruent to 1 or -1 mod 13, while the prime powers dividing h(x) are all congruent to 1, 3, or 9 modulo 13. If these polynomials intersect at some value x = a, then all prime dividing the polynomials are restricted to 1 mod 13, and as all primes splitting in Q(ζ13) are congruent to 1 mod 13, infinitely many intersections would yield such a polynomial.

However, I was not able to find even a single intersection x^3 - 52*x + 31 - (y^2 + 5) = 0.

I found found many such polynomials with these properties, and again, I wasn't able to find any intersections amongst them.

------

Proving the solutions of certain Diophantine equations may show that specific polynomial compositions (and chains of compositions) are limited or not possible for given degrees and cyclotomic fields.

From searches, it seems very likely that non-trivial composition polynomials fail to exist whenever g(x) has degree greater than 2 and h(x) or Q(ζn) has degree greater than 6, as illustrated with examples involving the 11th and 13th cyclotomic fields.

Last fiddled with by carpetpool on 2022-07-24 at 18:19
carpetpool is offline   Reply With Quote
Old 2022-07-27, 02:32   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·43·71 Posts
Default

Quote:
Originally Posted by carpetpool View Post
Given two cyclic fields K and L, (K ≠ L), with L being a finite extension of K, is it always possible to come up with two polynomials f(x) and g(x) (both of degree greater than 1), such that f(x) generates a field (isomorphic to) K, and f(g(x)) generates a field isomorphic to L. By "cyclic", I mean that K and L are subfields of some cyclotomic field Q(ζn), where ζn is a primitive n-th root of unity, and Q is the field of rational numbers.
<snip>
Stop. Your terminology is horrific. There is a standard term "cyclic extension" in field theory. An extension L/K is cyclic if it is a Galois extension, and the Galois group of L/K is a cyclic group.

Second, it is well known (Kronecker-Weber Theorem) that every finite Abelian extension of the field of rational numbers (that is, a finite Galois extension of the field of rational numbers with an Abelian Galois group) is contained in some cyclotomic field Q(ζn).

Third, it is not clear to me what coefficients you are allowing in your polynomials. Do they all have to be rational?


EDIT: It seems to me that your polynomial composition problem makes sense whenever K/Q and L/K are normal extensions. In your setup, L/Q is also normal, which is an even stronger condition.

The polynomial composition idea can also apply when K/Q and L/K are normal, but L/Q is not a normal extension.

A simple example is x^4 - x^2 - 1. This is (x^2)^2 - (x^2) - 1, so the composition idea carries through.

Now x^2 - x - 1 is a quadratic polynomial, and x^2 - x - 1 = 0 has one positive root and one negative root. Thus, x^4 - x^2 - 1 = 0 has two real roots (the square roots of the positive root of x^2 - x - 1 = 0) and two imaginary roots (the two square roots of the negative root of the quadratic). The polynomial x^4 - x^2 - 1 has Galois group of order 8 (dihedral group). The extension K = Q[x] (modulo x^4 - x^2 - 1) is a non-normal degree-4 extension of Q.

Having L/K and L/Q normal extensions makes things easier. What you would need is a defining element r for K/Q with f(r) = 0, where f(x) is an irreducible polynomial of degree [K:Q] with rational (or, better, integer) coefficients. Then (the hard part) r would also have to be such that there is a polynomial g(x) with rational (or integer) coefficients of degree [L:K] and a primitive element s for L/Q such that g(s) = r. Then f(g(s)) is the kind of composition you have in mind.

The hard part about finding g(x) is that in general, you can only assume that the coefficients of g(x) are in K.

Last fiddled with by Dr Sardonicus on 2022-07-28 at 12:51 Reason: As indicated
Dr Sardonicus is offline   Reply With Quote
Old 2022-07-30, 02:22   #3
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

1010011112 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Stop. Your terminology is horrific. There is a standard term "cyclic extension" in field theory. An extension L/K is cyclic if it is a Galois extension, and the Galois group of L/K is a cyclic group.

Second, it is well known (Kronecker-Weber Theorem) that every finite Abelian extension of the field of rational numbers (that is, a finite Galois extension of the field of rational numbers with an Abelian Galois group) is contained in some cyclotomic field Q(ζn).

Third, it is not clear to me what coefficients you are allowing in your polynomials. Do they all have to be rational?

...
Sorry about my initial terminology (I'm not too familiar with concepts beyond basic ring theory).

To address your remarks, you are correct about f and g having only rational coefficients (Q). At least that is what I had in mind.
Secondly, by "cyclic extension" (I won't use that term anymore), I was referring to the fields L and K being extensions of Q such that they are formed by adjoining a sum of n-th roots of unity to Q (i.e. the elements are Gaussian Periods). Thus, all roots of f(x) and f(g(x)) are essentially sums of n-th roots of unity for some n.

Thus, L/K is a normal extension as you pointed out: every polynomial which has a root in L must have roots that are sums of n-th roots of unity.

You seem to be addressing a more general problem where the extension need not be normal and any defining element need not be a sum of n-th roots of unity, or the extension L need not to be normal.

As with your example, the only subfields of K = Q(x) [mod x^4 - x^2 - 1] are Q, itself, and the field Q(x) [mod x^2 - x - 1].


I am not sure if there is a general relationship between what kind of extensions can be formed from using only compositions of primitive elements. It seems many of them not normal.

The fact that x^4 - x^2 - 1 has two imaginary and two real roots can be deducted from the fact that the square root of the golden ratio (1 + sqrt(5))/2 is real, while the square root of its conjugate is not.

---

Reverting to K and L/K being normal, more specifically abelian extensions of Q, I would think that requiring the roots of f(x) and f(g(x)) to be sums of primitive n-th roots of unity make the composition problem easier. In particular, it may not be possible to write the roots of f(x) by only using a linear combination of the roots f(g(x)) with integer coefficients, thus the coefficients of f and g should be rational.

For instance, if we choose our defining element for L to be u, where u^4 - u^3 + 2*u^2 + u + 1 = 0, then, u = ζ15 + ζ154 is a sum of (15-th) primitive roots of unity as required. If we choose v to be a primitive element of the base field K, where v = ζ5 + ζ5-1, then we have (-u^3 + 2*u^2 - 2*u + 1)/2 = v.


All primes which split in L are congruent to either 1 or 4 mod 15, while all primes that split in K are congruent to 1 or 4 mod 5.

Let f(x) = x^2 + x - 1, and h(x) = x^4 - x^3 + 2*x^2 + x + 1, and we want to find g(x) such that f(g(x)) = h(x). Consequently, g(x) must be a quadratic polynomial.

h(x) - 1 = x*(x - 1)^2*(x - 2) mod 3, so h(x) has no integer roots mod 3. In fact, h(x) = 1 mod 3 for all integers x.

On the other hand f(x)-1 = x^2 + x - 2 = (x - 1)^2 mod 3, so f(x) = 1 mod 3 if and only if x = 1 mod 3. Thus, g(x) must be a monic, quadratic polynomial such that g(x) = 1 mod 3 for all x. But any quadratic polynomial can only have at most 2 roots, but g(x) would need to have 3, which is a contradiction.

Thus, no composition would be possible. This holds even when h is the minimal polynomial of another primitive element of L.

So in some cases, we can't form the desired composition.

---

If we restrict L and K to be subfields of some cyclotomic field Q(ζp) where p is a prime, then we get quite a few interesting compositions:

If p = a^2 + 4 is prime, then u^2 + p*u + p = 0 generates a primitive element for the quadratic subfield K of Q(ζp), while u^4 + p*u^2 + p = 0 generates a primitive element for the quartic subfield L of Q(ζp). It is easy to verify that L is an extension of K as required. We have f(x) = x^2 + p*x + p and g(x) = x^2.

If p = a^2 + 3*a + 9 is prime, then u^3 + p*u^2 + 2*p*u + p = 0 generates a primitive element for the cubic subfield K of Q(ζp), while u^6 + p*u^4 + 2*p*u^2 + p = 0 generates a primitive element for the sextic subfield L of Q(ζp) if p = 3 mod 4.

When p = 1 mod 4, u^6 - p*u^4 + 2*p*u^2 - p = 0 generates a primitive element for the sextic subfield L of Q(ζp).


This suggests that compositions involving abelian extensions K and L/K of Q, it may be able to find defining polynomials for these fields of low degrees which are compositions of each other, but not for higher degrees.


More searching (when L/K is the 11th and 13th cyclotomic fields) fails to produce any composition polynomials where g is of degree 3 or greater.
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Access extension field in GP PARI in library syntax sanjay PARI/GP 0 2022-01-17 09:30
Error generating or reading NFS polynomials Brownfox Msieve 7 2018-04-06 16:24
Polynomials defining the same field as cyclotomic polynomial order 5 carpetpool carpetpool 0 2017-04-19 20:33
Prime generating polynomials that stop? Orgasmic Troll Math 61 2017-04-05 19:28
Prime-generating polynomials Orgasmic Troll Math 28 2004-12-02 16:37

All times are UTC. The time now is 08:21.


Fri Dec 9 08:21:35 UTC 2022 up 113 days, 5:50, 0 users, load averages: 1.47, 1.01, 0.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔