Questions tagged [groebner-bases]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers
53 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) ...
user avatar
2 votes
1 answer
86 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 ...
user avatar
1 vote
0 answers
117 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 ...
user avatar
  • 11
0 votes
0 answers
55 views

Solving a large system of equations when a large subset factors

I have a large (~1000 equations) overdetermined system of degree 3 polynomials with ~140 variables. I would like to find a complete solution set for this system, however, the Gröbner basis seems to be ...
user avatar
  • 1
0 votes
0 answers
48 views

Is the multivariate polynomial division always not unique?

Given an integer $n\geq 2,$ a monomial order $<,$ a multivariate polynomial $f\in k[x_1,\dots,x_n]$ and a list $F=(f_1,\dots,f_n)$ of multivariate polynomials there are quotients $q_1,\dots,q_n$ ...
user avatar
  • 1
4 votes
0 answers
169 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 $...
user avatar
  • 141
1 vote
1 answer
280 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 ...
user avatar
2 votes
0 answers
61 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 ...
user avatar
  • 21
1 vote
1 answer
116 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 ...
user avatar
  • 183
0 votes
0 answers
56 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$ ...
user avatar
0 votes
0 answers
49 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 ...
user avatar
  • 1
0 votes
0 answers
62 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 ...
user avatar
9 votes
0 answers
320 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 ...
user avatar
  • 2,806
2 votes
0 answers
48 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 ...
user avatar
1 vote
0 answers
90 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 ...
user avatar
0 votes
0 answers
62 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 ...
user avatar
1 vote
1 answer
152 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 ...
user avatar
1 vote
0 answers
100 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, ...
user avatar
  • 5,875
6 votes
1 answer
179 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 ...
user avatar
6 votes
1 answer
423 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 ...
user avatar
2 votes
0 answers
166 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 ...
user avatar
  • 2,473
4 votes
1 answer
199 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 ...
user avatar
  • 153
5 votes
1 answer
223 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$, ...
user avatar
  • 2,806
1 vote
1 answer
195 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 ...
user avatar
12 votes
2 answers
845 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< ...
user avatar
  • 245
1 vote
1 answer
102 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 $\...
user avatar
  • 113
3 votes
1 answer
157 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 $\...
user avatar
  • 404
4 votes
0 answers
86 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 ...
user avatar
1 vote
0 answers
32 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}$ ...
user avatar
4 votes
0 answers
86 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 $$ ...
user avatar
2 votes
1 answer
207 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 ...
user avatar
3 votes
0 answers
78 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 ...
user avatar
  • 7,442
3 votes
1 answer
182 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 ...
user avatar
  • 155
1 vote
0 answers
104 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 ...
user avatar
5 votes
2 answers
667 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#...
user avatar
2 votes
1 answer
435 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 ...
user avatar
  • 337
4 votes
0 answers
72 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$. ...
user avatar
5 votes
0 answers
286 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$ ...
user avatar
1 vote
0 answers
61 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 ...
user avatar
  • 2,921
5 votes
1 answer
249 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 ...
user avatar
5 votes
0 answers
171 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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
1 vote
1 answer
671 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 ...
user avatar
  • 11
4 votes
1 answer
406 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 ...
user avatar
1 vote
0 answers
116 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, ...
user avatar
7 votes
2 answers
430 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^{...
user avatar
  • 149
4 votes
1 answer
218 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, \...
user avatar
  • 141
12 votes
3 answers
812 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$) ...
user avatar
  • 24.5k
16 votes
2 answers
671 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 ...
user avatar
  • 7,371
2 votes
2 answers
183 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, ...
user avatar