# Tagged Questions

**3**

votes

**0**answers

153 views

### Comparing different Euclidean algorithms on a Euclidean domain

I have posted this question at stackexchange (502413), without responses until now.
In the papers by T. Motzkin: The Euclidean Algorithm, Bull. AMS 55, 1949, pp. 1142--1146 and P. Samuel: About ...

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

**8**

votes

**2**answers

203 views

### Ideal Membership without Certificate?

I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...

**5**

votes

**2**answers

766 views

### Solve for $A$ and $B$ in $AXB=Y$

Let $R = \mathbb{Z}[x_{1}, \dots, x_{r}]$.
Let $X$ be $n \times n$ matrix with entries in $R$.
Let $Y$ be $m \times m$ matrix with entries in $R$ formed from $\mathbb{Z}$-linear or $\mathbb{R}$-linear ...

**0**

votes

**0**answers

149 views

### Condition and algorithm for Decomposition of formal power series

$$F(x)= \Sigma_0^{\infty} a_i x^i$$ is formal power series, $a_i\in N\bigcup 0$,N is the set of natural number,under what condition may it be decomposed into a system of equations terms of which are ...

**7**

votes

**1**answer

352 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

**0**answers

122 views

### Efficient algorithm for computing the integral closure of a computable domain

what is known? even talking about efficiency relatively to the complexity of the computation of the domain itself?

**1**

vote

**0**answers

135 views

### Randomized alternative to Buchberger's algorithm

Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra.
Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...

**1**

vote

**1**answer

183 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

419 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?

**5**

votes

**0**answers

243 views

### Testing isomorphism of finitely generated algebras

Let $A=\mathbf{Q}[x_1,\ldots,x_n]$ be the polynomial ring in $n$ variables over the rational numbers. Let $B=\mathbf{Q}[f_1,\ldots,f_r]$ and
$C=\mathbf{Q}[g_1,\ldots,g_s]$ be two finitely generated ...

**3**

votes

**1**answer

439 views

### Efficient Algorithm for Matrix Version of Waring's Problem

Given an $n \times n$ matrix $A$ with entries in a commutative and associative ring with $1$ (say $Z[x_{1},\dots,x_{n^{2}}]$), the following paper guarantees existence of seven $B_{i}$s such that $A = ...

**11**

votes

**1**answer

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

**2**

votes

**1**answer

259 views

### A fast way to decide satisfiability of a set of simple fewnomial inequalities?

Background
Considering a set of points $(x_i, y_i)$ in $\mathbb R^2$ and constraints between some triples of them, which state, whether the three points of the triple are oriented clockwise (R), ...

**6**

votes

**1**answer

348 views

### Can we make Buchberger's algorithm faster for a given ideal if we are allowed to vary the monomial order?

Suppose we have a finite set of generators for an ideal $I \subset R := \Bbbk[x_1,\dotsc, x_n]$, where $\Bbbk$ is a field. If we choose a monomial ordering, then Buchberger's algorithm allows us to ...

**7**

votes

**2**answers

595 views

### An effective way to tell if the saturation of a homogeneous ideal is the irrelevant ideal

Let $\Bbbk$ be an algebraically closed field, let $R$ denote the graded ring $\Bbbk[x_0, \dotsc, x_N]$, and let $f_1, \dotsc, f_n \in R_m$ be nonconstant homogeneous polynomials. Then the common ...

**5**

votes

**2**answers

1k views

### Algorithm for Weierstrass Preparation Theorem for Formal Power Series

The Weierstrass preparation theorem for formal power series rings guarantees that if a given formal series $f(z) = \sum a_k z^k \in R[[z]]$ where $R$ is a complete local ring with maximal ideal $M$ ...

**8**

votes

**1**answer

444 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

**2**answers

784 views

### Ideals in the ring of single-variable Laurent polynomials with integer coefficients

I'm writing some software to automatically compute things like Alexander modules, Alexander ideals, Milnor signatures and Farber-Levine pairings for 1 and 2-knot complements. So among other things ...