Questions tagged [groebner-bases]
The groebner-bases tag has no usage guidance.
93
questions
2
votes
1
answer
103
views
Efficiency of Groebner basis for constraints of the form $(a_i x_i+b_i)(a_j x_j+b_j)$
This is based on numerical experiments in sage.
Let $K$ be a ring and define the ideal where each polynomial
is of the form $(a_i x_i+b_i)(a_j x_j+b_j)$ for constant $a_i,b_i,a_j,b_j$.
Q1 Is it true ...
3
votes
1
answer
176
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 ...
0
votes
0
answers
56
views
Extracting implications in polynomial constraint system from Groebner basis
Given a Groebner basis for a system of polynomial constraints over $\mathbb{Q}$, are there any known methods for extracting the low degree factorable polynomials in the ideal generated by that basis?
...
1
vote
0
answers
63
views
Gorenstein property from initial ideal
My question is:
If $I$ is a homogenous ideal of $S=K[x_1,\dots,x_n]$ and $in_{<}(I)$ is the initial ideal of $I$, with respect to a term order $<$ on $S$, then $S/I$ is Gorenstein if and only if ...
2
votes
0
answers
75
views
Gröbner implicitization with relationships between the variables
I have the following parametric equations, where cost$=\cos t$, cos2t$=\cos 2t$, and $A^2+B^2=1$:
...
0
votes
1
answer
70
views
Ideal membership and change of fields
Let $R=k[x_1,...,x_n]$ be a polynomial ring over a field. Let $f$ be a homogeneous polynomial and $I=(f_1,...,f_m)$ a homogeneous ideal.
With Macaulay2, one can compute the Groebner basis of $I$ when $...
3
votes
1
answer
221
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 $...
0
votes
1
answer
182
views
Are zero dimensional ideals radical?
I have a question about Theorem 3.7.25. of Computational commutative algebra I by M. Kreuzer and L. Robbiano.
Let $K$ be a perfect field, $I \subseteq K[x_1, \ldots, x_n]$, be a zero dimensional ...
0
votes
1
answer
178
views
Compatibility conditions for quadratic equations
In the context of physics, I stumbled over the following problem: I have $N$ equations, all are quadratic in a single scalar, real variable $x$:
\begin{eqnarray}
0 &= A_1x^2 + B_1x + C_1 \\
&...
7
votes
0
answers
161
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 ...
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+...
3
votes
1
answer
306
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 ...
0
votes
1
answer
142
views
Grobner basis of a submodule of a free module over polynomial ring
Let $A=\mathbb{Q} [x_1,\dots,x_n]$ be the ring of polynomials with rational coefficients. Let $T$ be an $m\times n$ matrix with entries from $A$. Consider it as a morphism of $A$-modules $T\colon A^n\...
2
votes
1
answer
132
views
Library/Database of parametric polynomial systems
Could anyone please recommend a known website where I can find a database/library that has systems of polynomial equations with $n$ variables and $m$ parameters?
I need some real examples to test my ...
7
votes
2
answers
799
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 ...
2
votes
1
answer
171
views
Techniques for estimating dimension of algebraic variety without calculating Groebner basis of polynomial constraints?
I have a system of multilinear polynomial constraints that I believe has no solution. Unfortunately, the number of variables and number of constraints is too large to afford direct computation of a ...
4
votes
0
answers
111
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) ...
1
vote
0
answers
208
views
Computer algebra programs that can solve polynomial systems on algebraically closed fields besides MAGMA
I was wondering which computer algebra programs out there can solve polynomial systems on the algebraic closure of $\mathbb{Q}$ analytically and efficiently.
So far, I only found MAGMA with its ...
6
votes
1
answer
240
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 ...
2
votes
1
answer
520
views
Efficiently computing Gröbner basis to prove no solution to polynomial constraints
In a similar vein to these now quite old questions on advice for calculating a Gröbner basis:
Fast computation of a Groebner basis. What is possible?
What is the state of art in Groebner bases
I am ...
1
vote
1
answer
159
views
Sufficient syntactic conditions for zero-dimensionality of polynomial systems
Consider a system $S$ of polynomial equations, $p_1=0,...,p_m=0$, for $p_i\in K[x_1,...,x_n]$, for a field $K$: the system $S$ is zero-dimensional if it has finitely many solutions. It is well-known ...
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 $...
2
votes
0
answers
85
views
Methods for multivariate polynomial equations over large finite fields
I am trying to get a rough overview of the best methods one might use to find solutions of multivariate polynomial equations over large finite fields. We can suppose for simplicity that the given ...
10
votes
0
answers
497
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 ...
5
votes
1
answer
239
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$, ...
0
votes
0
answers
65
views
The minimum number of polynomial equations the components of linearly dependent vectors must satisfy
Context:
Consider $m<n$ vectors $v_1,\dotsc,v_m\in\mathbb{C}^n$ with complex components. We can study if they are linearly dependent by constructing the following matrices. First the $n\times m$ ...
8
votes
2
answers
530
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 ...
0
votes
0
answers
53
views
Dependence of the complexity of solving polynomial sytems on the multidegree
Let $f_1,\ldots,f_n\in \mathbb{Q}[X_1,\ldots,X_n]$ be a system of $n$ polynomials in $n$ indeterminant, which only has finitely many solutions. Supose that the each of the variables $X_i$ appears at ...
0
votes
0
answers
68
views
Low rank approximation
Can we solve low rank approximation problem by using concept of Gröbner basis? I was trying to find it by Macaulay2 but didn't find the answer. I was trying to do by toric ideals as for them Gröbner ...
2
votes
0
answers
67
views
grobner basis of an ideal dependent on some parameter
Suppose $I = \langle f_1, ... , f_l \rangle$ is an ideal generated by polynomials $f \in k[x_1,\dots,x_n]$, where $k$ is a field of rational functions in some parameters $s_1,\dots,s_m$.
What are the ...
1
vote
0
answers
121
views
Groebner basis of a toric ideal
I know about toric ideals that it is a sort of binomial ideal i.e. generated by $x^u - x^v$, where $Au = Av $ ( A is the associated matrix). So by finding all integer solutions of $AX = 0$, can we ...
0
votes
0
answers
108
views
Is the Hilbert series of an ideal related to the Hilbert series of its homogenization?
Suppose we have a field $k$ of characteristic 0, let $I$ be an ideal of $R=k[x_1,...,x_n]$, and let $H$ be the homogenization of $I$ in $S=R[z]$. Is there any relationship between the Hilbert series ...
1
vote
1
answer
210
views
Gröbner basis via integer programming
I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating ...
1
vote
0
answers
106
views
How to obtain a linear basis from a Groebner basis?
Let $A$ be a finite dimensional algebra generated by $x_1, \ldots, x_n$ subject to certain relations $I_1, \ldots, I_m$. Could we obtained a linear basis $B$ consisting of monomials in $x_1, \ldots, ...
8
votes
1
answer
614
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 ...
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 ...
2
votes
0
answers
215
views
Computing the codimension of the variety defined by a system of quadratic forms
Suppose I have an $m \times n$ matrix $L$, where $m \leq n$ and each entry is $L_{i,j}(x_1, ..., x_s)$ which is a linear form over $\mathbb{C}$. Let $\mathbf{y} = (y_1, \ldots, y_n)$. Let us consider ...
4
votes
1
answer
324
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 ...
1
vote
1
answer
280
views
System of polynomial equations with a known root
I have 5 polynomial equations for 5 variables and I know that the set of roots is finite. All coefficients are integers. Ultimately I'd like to find all roots but finding the Groebner basis is ...
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< ...
1
vote
1
answer
107
views
Finding a characteristic for which the zero-locus of an ideal is not empty
I have a set of polynomials $f_1, \dots, f_m \in \mathbb{Z}[x_1, \dots, x_n]$ and I am interested in finding if these polynomials have a common root inside either $\mathbb{C}[x_1, \dots, x_n]$ or $\...
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 $\...
4
votes
0
answers
94
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 ...
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 ...
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 ...
1
vote
0
answers
35
views
Grobner basis of the toric ideal $I_{A_P}$ with respect to $<_{rev}$ consists of those binomials $t_αt_β − t_{α\cap β} t_{α\cup β}$
I try to understand the proof of the Theorem. 10.1.3.(page 185) from ''Monomial Ideals'' by Herzog & Hibi.
The reduced Grobner basis of the toric ideal $I_{A_P}$ with respect
to $<_{rev}$ ...
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
$$
...
2
votes
1
answer
257
views
Memory usage of Gröbner basis computation
I've been calculating some Gröbner bases in preparation for finding non-commutative Hilbert series (and, once I recreate that, characters of group actions). Specifically, I've been using the ...
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$. ...
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 ...