Algorithm for checking linear independence of algebraic numbers

Question

Is there any if and only if condition for checking $\mathbb{Q}$-linear independence of given a set of numbers say $\alpha_i$ ? More precisely how to check linear independence of given $n$ algebraic numbers (algebraic numbers are given by an interval and its irreducible polynomial such that that interval does not contain any other root of that polynomial ) ? Is there any known algorithm for it?

PS : Def : $\alpha_i$ are $\mathbb{Q}$-linearly dependent iff $ \exists c_i \in \mathbb{Q} $ not all zero such that $\sum c_i\alpha_i=0$

Answer 1

I had the same question, so I figure I might as well spell it out explicitly for the next person who comes across this post.

For convenience, here is a link to the book WhatsUp mentioned in the comments above. One starts by solving the primitive element problem, discussed on page 181, for one's set of numbers. When testing whether $\alpha_1\in\mathbb{Q}(k_1\alpha_1+\alpha_2)$ using one of the field membership algorithms, on success one gets a polynomial $P_1(x)\in\mathbb{Q}[x]$ such that $\alpha_1=P_1(k_1\alpha_1+\alpha_2)$. Let $\beta_2=k_1\alpha_1+\alpha_2$. Then for $Q_1(x)=x-k_1P_1(x)$, $\alpha_2=Q_1(\beta_2)$. One then similarly finds $P_i(x)$ and $k_i$ such that $\beta_i=P_i(\beta_{i+1})$ where $\beta_{i+1}=k_i\beta_i+\alpha_{i+1}$ and $Q_i(x)$ such that $\alpha_{i+1}=Q_i(\beta_{i+1})$ for each $i$. For $k<i$ one has $\beta_k=P_k(P_{k+1}(...P_{i-1}(P_i(\beta_i))...))$, and substituting this into $Q_{k-1}(x)$, one can get a polynomial for every $a_k$ in terms of the final $b_i$. The matrix whose rows are the coefficients of these polynomials is the relevant one. I don't think it's guaranteed to be square in general, but row reducing and examining the pivots should suffice.

Answer 2

Addendum to Alex's answer, feel free to turn it into a comment: you can compute the primitive element as follows. By Theorem 4.6 of "Computing primitive elements of extension fields" by Yokoyama et al., $\mathbb{Q}(\alpha_1, \ldots, \alpha_n)$ has a primitive element of the form $\theta = \alpha_1 + t_2\alpha_2 + \ldots + t_n\alpha_n$, where $1 \le t_i \le [\mathbb{Q}(\alpha_1, \ldots, \alpha_i) : \mathbb{Q}]$. Enumerating all such $\theta$'s, it remains to check whether $\alpha_i \in \mathbb{Q}(\theta)$. This can be done by factoring the minimal polynomial of $\alpha_i$ over $\mathbb{Q}$ into irreducibles in $\mathbb{Q}(\theta)$, and checking whether the factorisation contains a linear factor. Factorisation in a number field can be done in polynomial time, see "Factoring polynomials over algebraic number fields" by A.K.Lenstra.

There is also the paper by "Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers" by Hastad et al that might be useful.