3
votes
0answers
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
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 ...
8
votes
2answers
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
2answers
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
1answer
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
2answers
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 ...