27
votes
3answers
1k views

Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$, decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective, respectively, injective? -- And ...
2
votes
1answer
177 views

Algorithm for representing a polynomial as a composition of lower degree polynomials

Let $q$ be a large prime and $e$ an integer such that $GCD(e,q-1)=1$. Let $p(x)$ be a polynomial of degree $e^n$ with coefficients in $\mathbb Z_q$ such that there exists a progression of polynomials ...
9
votes
2answers
584 views

When polynomial f(x^2) can be factored as g(x)·g(-x) ?

In relation to my question Expression for the sum of square roots of zeros of a polynomial How to characterize polynomials $f(x)$ with rational coefficients such that $f(x^2)=g(x)\cdot g(-x)$ where ...
7
votes
1answer
345 views

Constructive proof of “Projective implies proper”

For every ring $A$, the structural morphism of schemes $\pi_A : {\bf P}^n_{A} \to {\rm Spec}{A}$ is a closed map. The usual proof of this fact is not constructive : given equations of a closed subset ...
1
vote
1answer
181 views

Special case of testing integer polynomials for irreducibility

How much easier is testing polynomials of the form x^n + ax + b for irreducibility (in Z[x]) than testing polynomials in general? I am especially interested in the case where n is prime, which may be ...
3
votes
3answers
405 views

Are there any neat algorithm to factor a homogenous polynomial, given we know this polynomial factors into linear forms?

Are there any neat algorithm to factor a multivariable (more than 2 variables) homogenous polynomial, given we know this polynomial factors into linear forms?
3
votes
2answers
790 views

Fast algorithms for addition and multiplication of Zhegalkin polynomials

Hello to all, I'm interested in fast algorithms for addition and multiplication of Zhegalkin polynomials. For example, let $f_1(x_1, x_2, x_3) = 1+x_1+x_2x_3$ $f_2(x_1, x_2, x_3) = x_1+x_3$ I'd ...
5
votes
2answers
159 views

Fast (subquadratic) evaluation of a class of N degree polynomials over N points

Let $(x_1 \ldots ,x_n) \in \mathbb{R}^n$ and $f_i = \Pi_{j=1, j \neq i }^n ( x_i - x_j )$ I'm trying to evaluate $(f_1, \ldots, f_n)$. A trivial algorithm runs in $\mathcal{O}(n^2)$ but given the ...
11
votes
1answer
485 views

The word problem in the ring of polynomials

This question must be well known but I cannot find it in the literature. Question: What is the computational complexity of the word problem in a subring of the ring of polynomials in $n\ge 1$ ...
4
votes
2answers
437 views

Simplifying a polynomial

Let $f(x_1,\ldots, x_n)\in\Bbbk [x_1,\ldots,x_n]$ be a given polynomial (assume $\Bbbk$ algebraically closed if you want). Suppose that we are given $n$ polynomials $v_1,\ldots v_n ...
1
vote
1answer
269 views

Computation for composition of polynomials

Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ ...
0
votes
0answers
288 views

Value of coefficient in estimation of computational complexity of polynomial division algorithm

Do you know value of coefficient $C$ at $C*n*log(n)$ in $O(n*log(n))$ estimation of complexity of polynomial division algorithm? It would be great if you give me links to paper with information about ...
2
votes
3answers
362 views

On special type polynomial inequalities over integers

A special monomial is a monomial of the form $C\cdot x_{i_1} \cdot \ldots \cdot x_{i_n}$, where C is an integer and no variable is repeated more than once in the monomial. For instance, $x\cdot y\cdot ...
9
votes
3answers
426 views

Effective algorithm to test positivity

Let $f(x_1,\ldots, x_n)$ be a real polynomial in several variables. Is there an effective algorithm to test whether $f$ is positive (or nonnegative) on the whole of ${\mathbb{R}}^n$?
8
votes
1answer
437 views

Reconstructing a polynomial from resultants

I am trying to compute a monic polynomial $f(x)$ with integer coefficients and known degree $d$. I am given $n$ pairwise coprime polynomials $g_1(x),\ldots,g_n(x)$, also with integer coefficients, ...
5
votes
1answer
1k views

Finding unknown integer-valued polynomials using inequalities

I've come across this interesting inequalities problem recently, which seemed straight-forward at first glance but has proven interesting enough to ask about it here. Suppose you are given the ...
6
votes
3answers
818 views

Polynomials that are sums of squares

Is any algorithm known for determining whether or not a multivariate polynomial with integer coefficients can be written as a sum of squares of such polynomials? By way of background, if we one ...