3
$\begingroup$

Let $\mathbb{K}:=\overline{\mathbb{Q}}$ be the field of algebraic numbers. We choose to represent an element of $\mathbb{K}$ as its minimal monic polynomial, which is a vector in some $\mathbb{Q}^n$.

I'm looking for a pointer towards the fastest (in term of arithmetic complexity, say) currently known method to factor a given polynomial $P\in \mathbb{K}[z]$ of degree $d$. More precisely, I'd like to know a reasonable bound on said complexity in terms of $P$ (its degree $d$ and the maximum degree $n$ of the minimal polynomials defining its coefficients).

As an aside I'm also interested in theoretical results regarding complexity of approximate root-finding algorithms in the case of BSS computation model, in terms of the degree of $P\in \mathbb{C}[z]$ and the magnitude of the desired approximation.

Improve this question
$\endgroup$
8
  • $\begingroup$ The question only makes sense for the usual Boolean computational model, and for a particular representation of a particular field by binary strings. You can't compute exact roots by an arithmetic circuit or by a BSS machine, as any value computed in such models is the value of a rational function of the inputs. $\endgroup$
    – Emil Jeřábek
    Commented Mar 29, 2016 at 10:30
  • $\begingroup$ That's true, and that's the aim of my main question with coefficients in $\overline{\mathbb{Q}}$. The side question was to know the complexity in BSS model being given an error bound on the result (like with Newton method, but I guess better methods exist out there, the difficulty being in finding initial conditions in every eventually-attractive bassin. I know people from complex dynamics studied that and proposed algorithms). I'll edit the question to reflect this clarification. $\endgroup$
    – Loïc Teyssier
    Commented Mar 29, 2016 at 12:24
  • $\begingroup$ But the main question is still totally unclear. You write “arithmetic complexity”, but that does not make sense, as arithmetic circuits can’t compute roots exactly. And even if I ignore vague words like “typically” and just assume you mean to ask about $\overline{\mathbb Q}$, you did not specify the representation of the field. The time complexity of computing with algebraic numbers in the isolating interval representation and in the sign-sequence representation may be quite different, for instance. Either way, the task of “exact root finding” over the algebraic numbers will mostly ... $\endgroup$
    – Emil Jeřábek
    Commented Mar 29, 2016 at 13:02
  • $\begingroup$ ... consist of factoring of polynomials in $\mathbb Q[x]$, so it might be clearer if you asked that question. $\endgroup$
    – Emil Jeřábek
    Commented Mar 29, 2016 at 13:03
  • 1
    $\begingroup$ Hopefully an expert will weigh in and answer your question, but the wikipedia page (en.wikipedia.org/wiki/Factorization_of_polynomials) on polynomial factoring seems quite relevant. In particular, your problem easily reduces to factoring over $\mathbb{Q}$ by Trager's method, and then factoring rational polynomials takes only polynomial time. You might ask an expert in Trager's method about the complexity of that algorithm. $\endgroup$
    – Pace Nielsen
    Commented Mar 29, 2016 at 14:25

0

Reset to default

You must log in to answer this question.