4
$\begingroup$

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$?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You could compute a $\mathbb{Q}$-basis of the splitting field (writing this splitting field as a tower of simple extensions), and write the $\alpha_i$ in terms of this basis. Pari/GP, Sage and Magma can certainly do that, I believe. $\endgroup$
    – François Brunault
    Commented Nov 9, 2020 at 16:45
  • 2
    $\begingroup$ I checked and in fact there is a built-in function 'LinearRelations' in Magma: magma.maths.usyd.edu.au/magma/handbook/text/404#4298 There is a reference to an algorithm by de Graaf and Fieker. $\endgroup$
    – François Brunault
    Commented Nov 9, 2020 at 17:33
  • 1
    $\begingroup$ I read the paper, sadly remark p278 blows it all as complexity is O(n!). Theoretically it should not be better than direct computing the ideal relation I (up to log tems) as it is equivalent to the factorization of a n! degree polynomial. $\endgroup$
    – T. Combot
    Commented Nov 10, 2020 at 9:34
  • 1
    $\begingroup$ I tested x^10+x^8+6*x^7-5*x^6+3*x^5+9*x^4-8*x^3+2*x+3 (a random polynomial) in magma online, it failed (out of memory). Factorizing it in $\mathbb{Q}(\alpha)$ with $\alpha$ a root of x^10+x^8+6*x^7-5*x^6+3*x^5+9*x^4-8*x^3+2*x+3 proves the Galois group is 2-transitive, and thus there are no relations except the trace. $\endgroup$
    – T. Combot
    Commented Nov 10, 2020 at 9:39

0

Reset to default

You must log in to answer this question.