# Monic polynomial of smallest degree whose root is the sum of certain algebraic integers

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.

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

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.