2
votes
0answers
162 views

Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
28
votes
3answers
2k 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
180 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
594 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 ...
8
votes
1answer
356 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
184 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
425 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
822 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
169 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
493 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
461 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
280 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
303 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
366 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
429 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
449 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
841 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 ...