# Tagged Questions

**2**

votes

**0**answers

161 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

**3**answers

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

**1**answer

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

**2**answers

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 ...

**7**

votes

**1**answer

354 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

**1**answer

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

**3**answers

424 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

**2**answers

819 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

**2**answers

168 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

**1**answer

492 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

**2**answers

459 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

**1**answer

279 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

**0**answers

301 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

**3**answers

364 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

**3**answers

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

**1**answer

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

**1**answer

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

**3**answers

837 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 ...