0
$\begingroup$

For two arbitrary finite sequences of naturals $a_1, a_2, \cdots a_n$ and $b_1, b_2, b_3 \cdots b_n$ let

$$c = \sum_{i=1}^n (a_i)^{\frac{1}{b_i}}$$

Is there an algorithm which generates the monic polynomial $p \in \Bbb Z[X] $ of smallest degree such that $p(c) = 0$?

Motivation: I'm interested in generalizing the result in this question.

Edit: The "motivation" has an answer as linked in the comments. My idea was using the rational root theorem instead. Nevertheless, I think this problem is somewhat interesting by itself. Another related problem is this.

$\endgroup$
  • 2
    $\begingroup$ You might be interested in this. This doesn't answer your question, but does answer your motivation. $\endgroup$ – Wojowu Dec 13 '16 at 9:03
0
$\begingroup$

Yes, however I will not claim that it is an efficient algorithm for large $ b_k $.

Consider the number field $ K $ generated over $ \mathbf Q $ by all summands. Since we lack information about how linearly independent this set actually is, we take care and treat it as a spanning set, not a basis. Multiplication by $ c $ induces a $ \mathbf Q $-linear endomorphism of $ K $, which can be put into matrix form with respect to the spanning set containing the summands in $ c $ and their powers. Then, Cayley-Hamilton gives us a monic polynomial $ P \in \mathbf Z[X] $ of degree $ b_1 b_2 \ldots b_n $ such that $ P(c) = 0 $.

Now, it is necessary to factor this polynomial into irreducibles. There are many known algorithms to do this: Zassenhaus, Kronecker, LLL to name a few. Upon factoring, we may test which factor has $ c $ as a root, and conclude that it must be the minimal polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.