Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.
Given an algebraic number of the form , with positive integers, is there an algorithm to compute the coefficients of its minimal polynomial? DTLHS (talk) 18:36, 9 January 2017 (UTC)[reply]
By analogy with the Swinnerton-Dyer polynomials, a not-necessarily-minimal polynomial with integer coefficients is
(that is the product over all possible combinations of signs for the square roots). For example for , it is
which multiplied out is
Then, for a more specific example, choosing , and , the polynomial is
Testing each factor in turn by substituting , the first one is found to be the minimal polynomial sought. You may have hoped for an algorithm that went straight to the minimal polynomial without the factoring step, but the question did not stipulate that as a requirement. --catslash (talk) 00:20, 10 January 2017 (UTC)[reply]
The Swinnerton-Dyer polynomials mentioned above cannot be factored over the integers, but they do make the Berlekamp–Zassenhaus factoring algorithm grind very slowly in the attempt. Consequently, the approach described may be inefficient. However, simply skipping alternating the signs of the radicals of those which happen to be squares ( in the above example), gives a polynomial with integer coefficients which is unlikely to have proper factors. Revisiting the example, the initial polynomial becomes
Thanks, that's very helpful. What if I just wanted the degree of the minimal polynomial and didn't care about the actual coefficients? DTLHS (talk) 01:10, 10 January 2017 (UTC)[reply]
I don't think there is a simple answer. Q[n] is a subfield of Q[√a1,...,√ak] so the degree is a power of 2 ≤ 2k+1. At first I thought the exponent would be the number of distinct primes in the factorizations of the square-free parts of the ai's. So the degrees of √2+√3 and √2+√3+√6 are both 4. But the degree of √6+√10+√15 is also 4 so the idea doesn't work all the time. It looks like if you need to find the rank r (over Z2) of the matrix formed by the exponents when you factor the ai's. Then I think the answer would be 2r. Looks messy to prove this assuming it's true, the case where the ai's are distinct primes is much easier though.--RDBury (talk) 20:41, 10 January 2017 (UTC)[reply]
Hm, that seems to work in almost every case. I found some exceptions bruteforcing random values: (6,10,15) gives a matrix of <(1,1,0), (1,0,1), (0,1,1)>, which has rank 3 when it should be 2. Similarly (6,15,40) gives a matrix of <(1,1,0), (0,1,1), (1,0,1)> which also has rank 3 when the degree of the minimal polynomial is 4. Any idea why it works in most cases but not all? DTLHS (talk) 06:02, 11 January 2017 (UTC)[reply]
The matrix <(1,1,0), (1,0,1), (0,1,1)> is rank 2 over Z2 which is what I meant. I'd be surprised if someone hasn't already determined the Galois group of Q[√a1,...,√ak] over Q given the ai are relatively prime, and it seems to me that would be very useful here. --RDBury (talk) 09:59, 14 January 2017 (UTC)[reply]
From the article: "In mathematical group theory, a formation is a class of groups closed under taking images and such that if G/M and G/N are in the formation then so is G/M∩N...", and somewhat later in the article: "A Melnikov formation is closed under taking quotients, normal subgroups and group extensions...". My question is: Isn't being closed under taking quotients the same thing as being closed under taking images,since an image is isomorphic to a quotient under the first isomorphism theorem? Thanks144.35.45.77 (talk) 18:43, 9 January 2017 (UTC)[reply]
The supremum is defined as the smallest upper bound.
is the supremeum of , that is, the smallest upper bound of . This means there is no smaller upper bound for . so cannot be an upper bound of . Since is not an upper bound of , there must be some element of such that . But is an upper bound of , so from it follows that . Therefore and this also means that .
In the previous step we've shown that if then . It follows that and in particular . Also so by the definition of A we have and therefore . This means that , which concludes the proof of this step.
Well, what you've written isn't correct. It's not guaranteed that . What we do have is that and also .
Likewise, it's not sufficient that , you need that . You do have (which is quite different from ), from which it follows that .
Also, from it doesn't follow directly that as you have implied, since we're not given that is strictly increasing. It is true anyway (since and , so and , so ). But you don't have to use this fact, you can simply follow the proof you've given in the question. In part one you've proven that and in the second part you've proven that , putting this together you have for every , which means that . -- Meni Rosenfeld (talk) 10:49, 10 January 2017 (UTC)[reply]
@יהודה שמחה ולדמן: By the way, the property that the supremum exists for every bounded subset is actually the least upper bound property, which is not the same thing as the reals forming a complete metric space. I strongly suggest reading up on the former concept, which is absolutely fundamental to real analysis.
Note that according to the page you've linked, "completeness" is one of the names of the least upper bound property. It appears (I don't remember all the nuances) that this is a special case of completeness in order theory, which is distinct from (though probably related to) completeness of metric spaces. -- Meni Rosenfeld (talk) 10:53, 10 January 2017 (UTC)[reply]