Suppose you are given an algebraic number $\alpha$ . It is represented by $(p(x),(a,b),r)$ where $p(x)$ is its minimal polynomial. $a+ ib$ is an approximation of $\alpha$ such that there is no other root of $p(x)$ than $\alpha$ in $r$-radius of $a+ib$ i.e. $ B(a+ib,r)$ only contains one root of p(x) and that is $\alpha$ itself. Is there any algorithm to generate a polynomial randomly which has one root in $\mathbb{Q}(\alpha)$ ? If so what is the complexity of finding its representation also along with generating the polynomial itself?
3
-
1$\begingroup$ Take a basis of $\mathbb{Q}(\alpha)/\mathbb{Q}$ (say $1,\alpha,...$), choose rationals $a_0,a_1,...$ randomly somehow, and return the minimal polynomial of $a_0+a_1\alpha+...$. This polynomial will have a root in $\mathbb{Q}(\alpha)$. Note that it might have more than one root, depending, for example, on the galois group of $\mathbb{Q}(\alpha)/\mathbb{Q}$. $\endgroup$– Dror SpeiserCommented Apr 10, 2016 at 21:28
-
1$\begingroup$ The polynomial $x-17$ has exactly one root in the specified field, and while the polynomial may not be random, its root is (see, e.g., prasoondiwakar.com/wordpress/trivia/17-is-the-random-number). $\endgroup$– Gerry MyersonCommented Apr 11, 2016 at 0:35
-
$\begingroup$ There is one problem. First of all we want to generate it 'randomly'. In order to that that if we take $a_0,..,a_n$ and take minimal poly of $a_0 \alpha + ..$ complexity of finding the minimal poly will increase very much (because the degree and coeffs will be much larger) . $\endgroup$– Pranjal DuttaCommented Apr 11, 2016 at 12:37
Add a comment
|