Skip to main content

All Questions

Filter by
Sorted by
Tagged with
6 votes
1 answer
641 views

Is decomposability of polynomials over a field an undecidable problem?

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 $\...
2 votes
0 answers
65 views

Decidability of the solvability of quadratic systems

Let a finite collection of (complex) unknowns $\{x_1,\ldots,x_n\}$ be given, as well as an affine system $AX=B$ in the quadratic variables $X:=[x_i x_j : i\leq j]$, with entries in a computable ...
15 votes
2 answers
1k views

Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem?

There are a number of criteria for determining whether a polynomial $\in \mathbb{Z} [X]$ is irreducible over $\mathbb{Q}$ (the traditional ones being Eisenstein criterion and irreducibility over a ...