Questions tagged [groebner-bases]
The groebner-bases tag has no usage guidance.
93
questions
28
votes
4
answers
3k
views
Can Gröbner bases be used to compute solutions to large, real-world problems?
In particular, suppose I have an affine algebraic variety over $\mathbb{R}^n$ described by generators of a radical ideal $I$ and I want to find (perhaps not all of the) points in the variety. Several ...
21
votes
5
answers
6k
views
Fast computation of a Groebner basis. What is possible?
I need to compute a Groebner basis of 18 polynomials in 19 variables the terms of which have degree at most 3. My aim is to exploit a symmetry in a PDE problem and I am not an expert in algebra or ...
16
votes
2
answers
710
views
From polynomial ideal over $\mathbb{Q}$ to polynomial ideal over $\mathbb{Z}$
Is there an algorithm to compute, given a polynomial ideal $I\subset \mathbb{Q}[x_1,\dotsc,x_n]$, the ideal $I\cap \mathbb{Z}[x_1,\dotsc,x_n]$ in $\mathbb{Z}[x_1,\dotsc,x_n]$?
The input and output ...
14
votes
1
answer
2k
views
Gröbner basis for Sudoku
I'm trying to write a program that solves Sudokus using Gröbner bases. I introduced $81$ variables, $x_1$ to $x_{81}$, this is a linearisation of the Sudoku board.
The space of valid Sudokus is ...
13
votes
3
answers
917
views
Polynomials vanishing modulo some integer $n$
It is well-known that a polynomial $q \in \mathbb Z[t]$ vanishes modulo $p$ only if it lies in the ideal $J_p$ generated by $p$ and $t^p-t$. This means that either the degree is large (at least $p$) ...
12
votes
2
answers
875
views
Residues of $\frac{1}{\prod_{i=1}^n (x-P_i)^{e_i}}$
This is a problem occurring in my research about deformations of $\mathbb{Z}/p^n$-covers over a ring of power series. Given an algebraically closed field $k$ of characteristic $p>0$, suppose $1< ...
12
votes
1
answer
2k
views
Ways to show a system of polynomial equations has no solution
I came across the following system of polynomial equations on $X_1,\dots,X_{m-2}$:
$$
\begin{cases}
2X_{2s}+\sum\limits_{t=1}^{2s-1}(-1)^tX_tX_{2s-t}=0,\quad s=1,\dots,\frac{m}{2}-1,\\
X_sX_{m-s}+(-1)^...
11
votes
1
answer
1k
views
PBW theorem over a Q-algebra, without freeness or flatness
Let $k$ be a commutative ring with $1$. Let $L$ be a $k$-Lie algebra, which is not necessarily free as a $k$-module. Let $S\left(L\right)$ denote the symmetric algebra of $L$ (over $k$), constructed ...
10
votes
2
answers
512
views
Monomial orderings in noncommutative setting
An ordering of monomials in the free associative algebra $k\langle x_1,\ldots,x_n\rangle$ is called a monomial ordering (EDIT: it seems that an equally common term used in this context is "term ...
10
votes
0
answers
504
views
How general are Gröbner degenerations?
While working with flat degenerations of flag varieties and Schubert varieties I've noticed that among the numerous known constructions there doesn't seem to be a single one that doesn't turn out to ...
8
votes
2
answers
536
views
Solving the field membership problem using Grobner bases
Is there an easy way to determine whether a set of elements in a field generates the whole field or only a subfield?
Specifically, I have a subfield of $k(x,y)$ described in terms of a canonical set ...
8
votes
1
answer
617
views
Given a zero-dimensional ideal $(f_1,...,f_n)$, is the ideal $(f_1-\alpha_1,...,f_n-\alpha_n)$ also zero-dimensional?
Suppose you have a zero-dimensional ideal $I=(f_1,...,f_n)$ in a polynomial ring $R=k[x_1,...,x_n]$ over a field $k$, so that $\dim_k(R/I)<\infty$. Take indeterminates $\alpha_1,...,\alpha_n$ and ...
8
votes
1
answer
709
views
Reasonable implementation of finding Gröbner bases over non-field coefficient rings
Gröbner bases are usually considered in the ring of polynomials over a field. However, there are useful definitions and algorithms for Gröbner bases over other coefficient rings; see, for instance, ...
7
votes
2
answers
469
views
Free $k[x_1, \dots, x_n]^{S_n}$-module?
Let $\text{char}\,k = 0$ and $n \ge 2$. What is the easiest way to see that $k[x_1, \dots, x_n]$ is a free $k[x_1, \dots, x_n]^{S_n}$-module with basis$$x_2^{m_2}x_3^{m_3} \dots x_{n-1}^{m_{n-1}} x_n^{...
7
votes
2
answers
838
views
Dimension of a homogeneous polynomial system
Let $m\geq4$ be an even integer, $V\subset\mathbb{C}^{m-1}$ be the solution set of the following polynomial equations:
\begin{cases}
&\sum\limits_{s=1}^{2t-1}z_sz_{2t-s}+\sum\limits_{s=2t+1}^{m-1}...
7
votes
1
answer
693
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
3
answers
841
views
Groebner bases for power series rings (reference request)
Hello,
Could you help me with a reference to elementary properties of Groebner bases in rings of formal power series over a field? I am especially interested in generic initial ideals.
Thank you in ...
7
votes
2
answers
800
views
Differential ideal membership problem
We know that in the ordinary algebra ideal case, the ideal membership problem can be solved by the Grobner Base theory, then, is there a counterpart theory in the differential ideal case?
To be ...
7
votes
0
answers
163
views
How can Gröbner bases be generalized to differential algebra?
I'm aware of the Rosenfeld-Gröbner algorithm "for computing a regular decomposition of a radical differential ideal generated by a set of polynomial differential equations, ordinary or with ...
6
votes
1
answer
242
views
Groebner Bases for submodule over polynomial ring with integer coefficients
It is well-known that there exist Groebner bases for ideals in polynomial ring $\mathbb Q[x]$ which can be found algorithmically Moreover, I don't think it is hard to show that there exist Groebner ...
6
votes
0
answers
315
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 $\...
5
votes
3
answers
1k
views
How to speed up the process for calculating the Groebner basis?
I am currently trying to get the Groebner basis for 9 equations with 12 variables:
$
a_1^2+b_1^2+c_1^2+d_1^2-48.73=0\\
a_2^2+b_2^2+c_2^2+d_2^2-50.53=0\\
a_3^2+b_3^2+c_3^2+d_3^2-40.69=0\\
a_1a_2+b_1b_2+...
5
votes
1
answer
3k
views
Existence of a real-valued solution to system of multivariate polynomial equations
Given a system of multivariate, polynomial equations, is there a way to determine if it has a solution in a given field (for instance the set of all reals). I don't care what the solution is, I just ...
5
votes
2
answers
890
views
Automatic proof in Euclidean Geometry using Theory of Groebner Bases
I've done the same question in math.stackexchange here "https://math.stackexchange.com/questions/1938261/automatic-proof-in-euclidean-geometry-using-theory-of-groebner-bases?noredirect=1#...
5
votes
1
answer
240
views
Infinitely many initial ideals for non-Artinian monomial orders?
Consider the polynomial ring $R=\mathbb Z[x_1,\ldots,x_n]$ and an ideal $I\subset R$. Let $<$ be a monomial order, i.e. a total order on the set of monomials in $R$ such that for any monomials $a$, ...
5
votes
1
answer
299
views
Groebner bases for differential operators with field coefficients (reference request)
Let $K$ be a field, $\partial_i$ be commuting derivations on $K$, and consider the ring $R=K[\partial_1\ldots \partial_n]$ (it is implicitly assumed that the derivations do not commute with elements ...
5
votes
0
answers
315
views
Weyl algebra acting on a polynomial ring
Let $\mathbb K$ be a characteristic-$0$ field, $R=\mathbb K[x_1,\ldots,
x_n]$ be a polynomial ring, and $W=\mathbb K[x_1,\ldots,x_n,\partial_1,\ldots \partial_n]$ be the Weyl
algebra. As usual $W$ ...
5
votes
0
answers
191
views
Computations in Weyl algebra with rational function coefficients
I am looking for a software to perform calculations with modules over the algebra $R_n=\mathbb{C}(x_1\ldots x_n)\langle \partial_1\ldots\partial_n\rangle$ of differential operators with rational ...
4
votes
4
answers
428
views
Lower bounds on the degrees of representatives of $u^n$ as $n \to \infty$
Let $k$ be an algebraically closed field and $A$ a finitely generated $k$-algebra, together with a specified surjective morphism $\phi \colon k[x_1, \dotsc, x_n] \to A$. For $f \in A$, define $\...
4
votes
2
answers
3k
views
Numerical solution for a system of multivariate polynomial equations
Hi all,
I have a system of 6th-order polynomial equations in 4 variables $q_1, q_2, q_3, q_4$ (i.e. polynomials with all the terms such as $q_1^6, q_2^6, q_2^4 q_3^2$):
$P_k(q_1, q_2, q_3, q_4) = 0$ ...
4
votes
4
answers
1k
views
Systems of polynomial equations
Hi all,
I'm an engineer assigned to determine some parameters of a manipulator (ie., calibration). It has a number of parameters, but after some manipulations of its dynamic equations, I can have the ...
4
votes
1
answer
328
views
Can a minimal generating set for an ideal always be made into a Groebner basis?
Let $I\subseteq k[x_0,\ldots,x_n]$ be an ideal, generated by some polynomials $F_1,\ldots,F_r$, all homogeneous and of the same degree. Suppose $r$ is the smallest number of generators that will ...
4
votes
1
answer
229
views
Solving over-determined system of polynomials
I am trying to solve the following over determined system of polynomials
\begin{align}
& p_1(x_1,x_2,\ldots,x_n)=0, \\
& p_2(x_1,x_2,\ldots,x_n)=0, \\
& \vdots \\
& p_m(x_1,x_2, \...
4
votes
1
answer
522
views
How can I include irreducibility in a Groebner basis calculation?
I'm trying to prove impossibility of certain systems of differential/polynomial equations using Groebner basis techniques.
For example, consider the equation $qn = mf$, where each of the variables ...
4
votes
1
answer
174
views
Algorithm to detect if an element of a (commutative) ring is in a subring?
For rings finitely-generated over a field, the theory of Groebner bases gives us quite an efficient algorithm for determining whether an element of the ring is in a given ideal of the ring.
Is there ...
4
votes
0
answers
112
views
Recommendations for distributed calculations of Groebner Bases
There are many computer algebra systems available which can compute a Groebner basis, including:
Mathematica
Singular
Macaulay2
Magma
Maple
CoCoA
However (please correct me if I've missed something) ...
4
votes
0
answers
192
views
Buchberger's criterion for Gröbner bases in $k$-algebras with multiplicative basis and admissible order
Let $R$ be an associative $k$-algebra with multiplicative basis $\mathcal B$ with an admissible order on $\mathcal B$.
Let $G \subseteq R$ be a subset.
A multiplicative basis $\mathcal B$ means that $...
4
votes
0
answers
95
views
Compute equalizer of maps of polynomial rings, perhaps using Gröbner bases
Suppose that $k$ is a field and I have two ring homomorphisms
$$
\phi, \psi :k[x_1,...,x_m] \to k[y_1,...,y_n].
$$
How can I use Gröbner bases (or other computational tools) to compute the subring of ...
4
votes
0
answers
99
views
Gröbner bases of resultants and their monomial ideals
$\newcommand{QQ}{\mathbb{Q}}$
Consider the ring $R = \QQ[x, a_1,\ldots,a_m]$ for a certain integer $m$ and the homogeneous polynomial
$$
f = x^{m+1} + \sum_{i=1}^m a_i^i x^{m+1 - i}
$$
Now let
$$
...
4
votes
0
answers
79
views
Does a polynomial system with precisely e solutions have a Groebner basis of degree bounded by e?
Let $k$ be a field and let $R=k[X_1,...,X_n]$ be a polynomial ring. Let $F \subset R$ be a finite subset generating a radical ideal $I$ with precisely $e$ solutions over an algebraic closure of $k$. ...
4
votes
0
answers
167
views
Bound for the height of equations defining the singular locus of a variety
Fix positive integers $m, n, d$.
In what follows, the height of an algebraic number will mean the absolute multiplicative height.
Let $V \subset \bar{\mathbb{Q}}^n$ be an affine algebraic variety ...
4
votes
0
answers
453
views
Bounding the degrees in a Bézout relation for integer polynomials
Let $A$ and $B$ be two polynomials in $\mathbf Z[X]$ which generate $\mathbf Z[X]$, that is assume that there exist polynomials $U$ and $V$ in $\mathbf Z[X]$ such that
$$
A \cdot U + B \cdot V=1.
$$
...
3
votes
1
answer
308
views
Groebner basis with parameters
I need to compute a Groebner basis of a polynomial system with parameters.
The only recent results I found is Groebner cover:
https://www.sciencedirect.com/science/article/pii/S0747717110000970
Are ...
3
votes
1
answer
395
views
Is the first part of Eisenbud's Proposition 15.15's proof o.k?
In the chapter on Gröbner bases from Eisenbud's "Commutative Algebra" the following statement appears as Proposition 15.15 (page 344):
Let $F$ be a free $S$ module with basis and monomial order ...
3
votes
1
answer
229
views
Resultants and elimination theory
Consider an ideal $I = \langle f_1,\dotsc,f_n\rangle$ in the ring $k[x_1,\dotsc,x_m]$.
Define the $i$-th elimination ideal to be $I_i = I \cap k[x_{i+1},\dotsc,x_m]$.
For any two polynomials $f$ and $...
3
votes
1
answer
178
views
Size of the Groebner basis and change of coordinates
Given an ideal $I$ of $k[x,y]$, the size of the Groebner basis depends on the monomial ordering. For example, if
$$
I = \langle x^3y^4 , x^2 + y^2 \rangle,
$$
then the Groebner basis with the ...
3
votes
1
answer
167
views
Solving system of multivariable algebraic equations over $\mathbb Q$ by reducing over $\mathbb F_p$
I try to solve the finite system of multivariable algebraic equations with coefficients from $\mathbb Q$. It would be sufficient for me to prove that there is only finite number of solutions over $\...
3
votes
1
answer
207
views
Geometric significance of Anick's resolution
Given an augmented graded associative $K$ -algebra $A$, we can construct a free resolution of $K$ given by $K_A$ modules which gives nice combinatorial informations about the homology classes of the ...
3
votes
0
answers
84
views
$\mathbb Z$-torsion for some quadratically presented Lie rings
$\newcommand{\Z}{\mathbb{Z}}$
I asked this question on MSE but no answer so far, so I'm also asking it here.
Let $L$ be a Lie ring (a Lie algebra over $\Z$) with generators $x_1,\dots,x_n$ and ...
2
votes
2
answers
591
views
Nonstandard monomial orders?
Are there any articles/books/examples where a non-standard monomial order is used?
What are the applications of these monomial orders? In particular, uses in groebner bases and variable elimination.
(...