Is decomposability of polynomials over a field an undecidable problem?

Question

By a decomposition of a polynomial $F(x)$ over a field $K$ we mean writing $F(x)$ as

$$ F(x)=G(H(x)) \quad(G(x), H(x) \in K[x]), $$

which is nontrivial if $\operatorname{deg} G(x)>1$ and $\operatorname{deg} H(x)>1$. The polynomial $F(x)$ is called decomposable over $K$ if it has at least one nontrivial decomposition over $K$; otherwise it is said to be indecomposable.

Motivated by my previous question, I want to know if the decision problem of "Given an arbitrary polynomial $F(x)\in K[x]$, is it decomposable over $K$ or not?" is decidable or undecidable.

I am interested in the above question because of the famous Bilu–Tichy Theorem.

Answer 1

Yes, this problem is decidable. Kozen and Landau gave a polynomial-time algorithm that tests if a polynomial $F$ is decomposable and produces a nontrivial decomposition $F(x) = G(H(x))$ if one exists. Their algorithm requires that $\deg(G)$ has a multiplicative inverse in $K$.

Kozen, Dexter; Landau, Susan, Polynomial decomposition algorithms, J. Symb. Comput. 7, No. 5, 445-456 (1989); errata ibid. 10, No. 5, 529 (1990). ZBL0691.68030.