Questions tagged [groebner-bases]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
0answers
123 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 $...
0
votes
1answer
114 views

Efficiently computing Groebner basis to prove no solution to polynomial constraints

In a similar vein to these now quite old questions on advice for calculating a Groebner basis: Fast computation of a Groebner basis. What is possible? What is the state of art in Groebner bases I am ...
2
votes
0answers
46 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 ...
1
vote
1answer
108 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 ...
0
votes
0answers
58 views

How to ensure polynomial system of equations remain non redundant after linear transformation?

Assume that $x=(x_1,\dots,x_n)^T$ and we have $r$ non redundant polynomial equations $p_i(x)=0, \ i=1,\dots, r$. My question is, what happens if I make a "transformation" $x = Ay$ with $A$ a ...
0
votes
0answers
46 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$ ...
0
votes
0answers
47 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
0answers
59 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 ...
7
votes
0answers
245 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 ...
2
votes
0answers
43 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
0answers
73 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
0answers
52 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
1answer
137 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
0answers
91 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, ...
4
votes
1answer
124 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
1answer
402 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 ...
2
votes
0answers
148 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
1answer
139 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 ...
5
votes
1answer
216 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$, ...
1
vote
1answer
159 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
2answers
833 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
1answer
98 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
1answer
152 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
0answers
79 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 ...
1
vote
0answers
31 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
0answers
80 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
1answer
186 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 ...
3
votes
0answers
75 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
1answer
173 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 ...
1
vote
0answers
98 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 ...
5
votes
2answers
615 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#...
2
votes
1answer
380 views

Integer programming and Groebner basis

I enjoyed reading different papers about using Groebner basis to solve integer programming. Is there any literature about the complexity and/or comparison with other (more classical) methods like ...
4
votes
0answers
71 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$. ...
5
votes
0answers
268 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$ ...
1
vote
0answers
59 views

Computing intersection of Weyl algebra ideal with certain subring

Let $D=k [x_1,\ldots, x_n, \partial_1,\ldots, \partial_n] $ be the nth Weyl algebra over the characteristic zero field $k $. Set $\theta_i=x_i\partial_i $. Let $I $ be a left ideal in $D $. Is there a ...
5
votes
1answer
221 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
0answers
149 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 ...
1
vote
2answers
2k views

Solving a system of equations using Gröbner basis

In Sage (or any other package) when using Gröbner basis to solve a system of equations (some of which are non-linear equations) does computing the Gröbner basis for the ideal ID generated by the ...
1
vote
1answer
572 views

Solving Non-Linear Equations over a Finite Field of a Large Prime Order

I want to know is there is an efficient way to figure out whether or not a ( underdetermined) system of non-linear equations have a solution over a finite field of large prime order. The equations ...
4
votes
1answer
362 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 ...
1
vote
0answers
105 views

Polynomial constraints triggered by irreducibility [closed]

I've come across an interesting connection between irreducible polynomials and polynomial constraints. For example, consider the basic quadratic: $$af^2 + bf + c = 0$$ If we're working in a ring, ...
6
votes
2answers
419 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^{...
4
votes
1answer
204 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, \...
12
votes
3answers
664 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$) ...
16
votes
2answers
624 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 ...
2
votes
2answers
182 views

Pseudo-decision procedures for first order arithmetic

I was reading this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.2911&rep=rep1&type=pdf in which the author describes an algorithm, based on Groebner basis, ...
1
vote
1answer
411 views

cup-length of the first Chern class of complex grassmannian

Let $G_2(\mathbb{C}^{n+1})$ be the complex grassmannian. Then the cohomology ring $H^*(G_2(\mathbb{C}^{n+1});\mathbb{C})=\mathbb{C}[c_1,c_2]/(f_n,f_{n+1})$, where $f_k=\sum_{i=0}^{[k/2]}(-1)^{k-i}{{...
2
votes
3answers
1k views

ideals of polynomial ring with complex number coefficients

Let $\mathbb{C}[x,y]$ be the polynomial ring with variables $x,y$ and coefficient in $\mathbb{C}$. Let $f,g\in \mathbb{C}[x,y]$. Let $(f,g)$ be the ideal of $\mathbb{C}[x,y]$ generated by $f,g$. ...
0
votes
0answers
108 views

Maximal elements for ideals and subrings ordered by inclusion with fixed number of minimal generating polynomials

Let $R=\mathbb{R}[X_1,\dots,X_n]$, and $$\mathfrak{I}_d=\{ \text{ideals for which there is minimal generating system with $d$ elements} \}\setminus \{\text{ ideals generated by $d$ monomials}\}$$ ...
1
vote
1answer
440 views

Is there a Gröbner basis analogue that exists for vector spaces?

Suppose I have a coordinate system $t_1,\ldots t_N$ with a lexicographical ordering. Let LT denote choosing the lowest term of a polynomial with respect to this ordering. e.g. LT$(t_1 + t_2)=t_2$. ...