Consider an irreducible polynomial $P\in\mathbb{Q}[x]$ of degree $n$ whose second leading coefficient is $0$ and $\alpha_1,\dots,\alpha_n$ its $n$ distincts roots. I am interested on the problem of computing all linear relations $a_1\alpha_1+\dots + a_n\alpha_n=0$ with $a_i\in\mathbb{Z}$.

A brutal method consists in computing the ideal generated by all polynomial relations on the $\alpha_i$, and then compute elements of degree $1$ of this ideal. However, the field $\mathbb{Q}(\alpha_1,\dots,\alpha_n)$ is typically of degree $n!$, which renders this approach unfeasible.

A more subtile approach is to compute the trace of the $\alpha_i$ over a subfield $\mathbb{K}$ of $\mathbb{Q}(\alpha_1,\dots,\alpha_n)$, which constraints the possible relations. However, it is not clear how large $\mathbb{K}$ has to be to detect all linear relations.

Is it possible to find all linear relations among the roots in polynomial time in $n$?