Wikipedia:Reference desk/Archives/Mathematics/2017 January 9

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.

January 9

Computing the minimal polynomial of an algebraic number

Given an algebraic number of the form $n=\sum _{i=0}^{k}{\sqrt {a_{i}}}$, with $a_{i}$ positive integers, is there an algorithm to compute the coefficients of its minimal polynomial? DTLHS (talk) 18:36, 9 January 2017 (UTC)

By analogy with the Swinnerton-Dyer polynomials, a not-necessarily-minimal polynomial with integer coefficients is

$\prod _{m=0}^{2^{k+1}-1}\left(x-\sum _{j=0}^{k}(-1)^{{\mathrm {bit} }_{j}(m)}{\sqrt {{a}_{j}}}\right)$

(that is the product over all possible combinations of signs for the square roots). For example for $\scriptstyle {k=2}$, it is

$(x-{\sqrt {{a}_{0}}}-{\sqrt {{a}_{1}}}-{\sqrt {{a}_{2}}})(x+{\sqrt {{a}_{0}}}-{\sqrt {{a}_{1}}}-{\sqrt {{a}_{2}}})(x-{\sqrt {{a}_{0}}}+{\sqrt {{a}_{1}}}-{\sqrt {{a}_{2}}})(x+{\sqrt {{a}_{0}}}+{\sqrt {{a}_{1}}}-{\sqrt {{a}_{2}}})(x-{\sqrt {{a}_{0}}}-{\sqrt {{a}_{1}}}+{\sqrt {{a}_{2}}})(x+{\sqrt {{a}_{0}}}-{\sqrt {{a}_{1}}}+{\sqrt {{a}_{2}}})(x-{\sqrt {{a}_{0}}}+{\sqrt {{a}_{1}}}+{\sqrt {{a}_{2}}})(x+{\sqrt {{a}_{0}}}+{\sqrt {{a}_{1}}}+{\sqrt {{a}_{2}}})$

which multiplied out is

$x^{8}-4x^{6}{a}_{0}-4x^{6}{a}_{1}-4x^{6}{a}_{2}+6x^{4}{a}_{0}^{2}+4x^{4}{a}_{0}{a}_{1}+4x^{4}{a}_{0}{a}_{2}+6x^{4}{a}_{1}^{2}+4x^{4}{a}_{1}{a}_{2}+6x^{4}{a}_{2}^{2}-4x^{2}{a}_{0}^{3}+4x^{2}{a}_{0}^{2}{a}_{1}+4x^{2}{a}_{0}^{2}{a}_{2}-40x^{2}{a}_{0}{a}_{2}{a}_{1}+4x^{2}{a}_{0}{a}_{2}^{2}+4x^{2}{a}_{1}^{2}{a}_{0}-4x^{2}{a}_{1}^{3}+4x^{2}{a}_{1}^{2}{a}_{2}+4x^{2}{a}_{1}{a}_{2}^{2}-4x^{2}{a}_{2}^{3}+{a}_{0}^{4}-4{a}_{0}^{3}{a}_{1}-4{a}_{0}^{3}{a}_{2}+6{a}_{0}^{2}{a}_{1}^{2}+4{a}_{0}^{2}{a}_{1}{a}_{2}+6{a}_{0}^{2}{a}_{2}^{2}-4{a}_{0}{a}_{1}^{3}+4{a}_{0}{a}_{1}^{2}{a}_{2}+4{a}_{0}{a}_{1}{a}_{2}^{2}-4{a}_{0}{a}_{2}^{3}+{a}_{1}^{4}-4{a}_{1}^{3}{a}_{2}+6{a}_{1}^{2}{a}_{2}^{2}-4{a}_{1}{a}_{2}^{3}+{a}_{2}^{4}$

Then, for a more specific example, choosing $\scriptstyle {{a}_{0}=3}$, $\scriptstyle {{a}_{1}=4}$ and $\scriptstyle {{a}_{2}=11}$, the polynomial is

$x^{8}-72x^{6}+1232x^{4}-6144x^{2}+1024$

This can be factored by the Berlekamp–Zassenhaus algorithm to give candidate minimal polynomials

$(x^{4}-8x^{3}-4x^{2}+80x-32)(x^{4}+8x^{3}-4x^{2}-80x-32)$

Testing each factor in turn by substituting $\scriptstyle {x={\sqrt {3}}+2+{\sqrt {11}}}$, the first one $\scriptstyle {x^{4}-8x^{3}-4x^{2}+80x-32}$ 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)

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 $\scriptstyle {{a}_{j}}$ which happen to be squares ($\scriptstyle {{a}_{1}}$ in the above example), gives a polynomial with integer coefficients which is unlikely to have proper factors. Revisiting the example, the initial polynomial becomes

$(x-{\sqrt {{a}_{0}}}-{\sqrt {{a}_{1}}}-{\sqrt {{a}_{2}}})(x+{\sqrt {{a}_{0}}}-{\sqrt {{a}_{1}}}-{\sqrt {{a}_{2}}})(x-{\sqrt {{a}_{0}}}-{\sqrt {{a}_{1}}}+{\sqrt {{a}_{2}}})(x+{\sqrt {{a}_{0}}}-{\sqrt {{a}_{1}}}+{\sqrt {{a}_{2}}})$

which multiplied out is

$x^{4}-4x^{3}{\sqrt {{a}_{1}}}-2x^{2}{a}_{0}+6x^{2}{a}_{1}-2x^{2}{a}_{2}+4x{\sqrt {{a}_{1}}}{a}_{0}-4x{a}_{1}^{\frac {3}{2}}+4x{a}_{2}{\sqrt {{a}_{1}}}+{a}_{0}^{2}-2{a}_{0}{a}_{1}-2{a}_{0}{a}_{2}+{a}_{1}^{2}-2{a}_{1}{a}_{2}+{a}_{2}^{2}$

and putting $\scriptstyle {{a}_{0}=3}$, $\scriptstyle {{a}_{1}=4}$ and $\scriptstyle {{a}_{2}=11}$ gives

$x^{4}-8x^{3}-4x^{2}+80x-32$

immediately (the wanted minimal polynomial with no factoring). --catslash (talk) 01:32, 10 January 2017 (UTC)

Alternatively, you could use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (see the second paragraph of the Applications section --catslash (talk) 00:30, 10 January 2017 (UTC)

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)

I don't think there is a simple answer. Q[n] is a subfield of Q[√a₁,...,√a_k] so the degree is a power of 2 ≤ 2^k+1. At first I thought the exponent would be the number of distinct primes in the factorizations of the square-free parts of the a_i'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 Z₂) of the matrix formed by the exponents when you factor the a_i's. Then I think the answer would be 2^r. Looks messy to prove this assuming it's true, the case where the a_i's are distinct primes is much easier though.--RDBury (talk) 20:41, 10 January 2017 (UTC)

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)

The matrix <(1,1,0), (1,0,1), (0,1,1)> is rank 2 over Z₂ which is what I meant. I'd be surprised if someone hasn't already determined the Galois group of Q[√a₁,...,√a_k] over Q given the a_i are relatively prime, and it seems to me that would be very useful here. --RDBury (talk) 09:59, 14 January 2017 (UTC)

formations question(group theory)

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)

Seems like it to me; just different ways of phrasing the same property. --RDBury (talk) 20:48, 10 January 2017 (UTC)

Intermediate value theorem

I'm missing something about the proof:

We shall prove the first case, $f(a)<y<f(b)$. The second case is similar.

Let $A=\{x\in [a,b]:f(x)<y\}$ . Then $S$ is non-empty since $a\in A$ , and $A$ is bounded above by $b$ . Hence, by completeness, the supremum $c=\sup A$ exists. We claim that $f(c)=y$ .

Fix some $\varepsilon >0$ . Since $f$ is continuous, there is a $\delta >0$ such that ${\Big |}f(x)-f(c){\Big |}<\varepsilon$ whenever $|x-c|<\delta$ . This means that

$f(x)-\varepsilon <f(c)<f(x)+\varepsilon$

for all $x\in (c-\delta ,c+\delta )$ . By the properties of the supremum, there exist $a^{*}\in (c-\delta ,c]$ that is contained in $A$ , so that for that $a^{*}$

$f(c)<f(a^{*})+\varepsilon <y+\varepsilon$ (Why is this true?)

Choose $a^{**}\in [c,c+\delta )$ that will obviously not be contained in $A$ , so we have

$f(c)>f(a^{**})-\varepsilon \geq y-\varepsilon$ (Why is this true?)

Both inequalities

$y-\varepsilon <f(c)<y+\varepsilon$

are valid for all $\varepsilon >0$ , from which we deduce $f(c)=y$ as the only possible value, as stated.

I need help from the first question and on. יהודה שמחה ולדמן (talk) 21:43, 9 January 2017 (UTC)

The supremum is defined as the smallest upper bound.

$c$ is the supremeum of $A$, that is, the smallest upper bound of $A$. This means there is no smaller upper bound for $A$. $c-\delta <c$ so $c-\delta$ cannot be an upper bound of $A$. Since $c-\delta$ is not an upper bound of $A$, there must be some element $a^{*}$ of $A$ such that $a^{*}>c-\delta$. But $c$ is an upper bound of $A$, so from $a^{*}\in A$ it follows that $a^{*}\leq c$. Therefore $a^{*}\in (c-\delta ,c]$ and this also means that $a^{*}\in (c-\delta ,c+\delta )$.

In the previous step we've shown that if $x\in (c-\delta ,c+\delta )$ then $f(x)-\varepsilon <f(c)<f(x)+\varepsilon$. It follows that $f(a^{*})-\varepsilon <f(c)<f(a^{*})+\varepsilon$ and in particular $f(c)<f(a^{*})+\varepsilon$. Also $a^{*}\in A$ so by the definition of A we have $f(a^{*})<y$ and therefore $f(a^{*})+\varepsilon <y+\varepsilon$. This means that $f(c)<f(a^{*})+\varepsilon <y+\varepsilon$, which concludes the proof of this step.

The second part is proven similarly.

-- Meni Rosenfeld (talk) 22:53, 9 January 2017 (UTC)

So you're saying this?

$a^{*}\in (c-\delta ,c]\subseteq A\quad \implies \quad f(a^{*})-\varepsilon <f(c)<f(a^{*})+\varepsilon <y+\varepsilon$

$a^{**}\in [c,c+\delta )\nsubseteq A\quad \implies \quad y-\varepsilon <f(a^{**})-\varepsilon <f(c)<f(a^{**})+\varepsilon$

$\Downarrow$

$a^{*}<a^{**}\quad \implies \quad f(a^{*})<f(a^{**})$

$\Downarrow$

$f(a^{*})-\varepsilon <{\color {red}y-\varepsilon }<f(a^{**})-\varepsilon \ {\color {red}<f(c)<}\ f(a^{*})+\varepsilon <{\color {red}y+\varepsilon }<f(a^{**})+\varepsilon$

יהודה שמחה ולדמן (talk) 00:45, 10 January 2017 (UTC)

Well, what you've written isn't correct. It's not guaranteed that $(c-\delta ,c]\subseteq A$. What we do have is that $a^{*}\in (c-\delta ,c]$ and also $a^{*}\in A$.

Likewise, it's not sufficient that $[c,c+\delta )\not \subseteq A$, you need that $a^{**}\not \in A$. You do have $(c,c+\delta )\cap A=\emptyset$ (which is quite different from $(c,c+\delta )\not \subseteq A$), from which it follows that $a^{**}\not \in A$.

Also, from $a^{*}<a^{**}$ it doesn't follow directly that $f(a^{*})<f(a^{**})$ as you have implied, since we're not given that $f$ is strictly increasing. It is true anyway (since $a^{*}\in A$ and $a^{**}\not \in A$, so $f(a^{*})<y$ and $f(a^{**})\geq y$, so $f(a^{*})<f(a^{**})$). 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 $f(c)<y+\varepsilon$ and in the second part you've proven that $f(c)>y-\varepsilon$, putting this together you have $y-\varepsilon <f(c)<y+\varepsilon$ for every $\varepsilon >0$, which means that $f(c)=y$. -- Meni Rosenfeld (talk) 10:49, 10 January 2017 (UTC)

@יהודה שמחה ולדמן: 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.

By the way, as Jenny Harrison once advised me, writing your whole comment in just symbols makes it hard to follow - write it out in words.--Jasper Deng (talk) 05:48, 10 January 2017 (UTC)

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)