Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [groebner-basis]

A Gröbner basis is a type of a generating set of an ideal in a polynomial ring over a field. It is a multivariate non linear generalization of Gaussian elimination and Euclid's algorithm.

0
votes
0answers
22 views

What properties are shown by a Grobner basis of an ideal?

Let I be an ideal $$I=<f(x),g(x)>=<10x^3+12x^2+3,x^2-6x+5>$$ The Grobner basis of I is $G= \{1\}$. GIven that we can deduct some usefull info about the ideal. Here's what I came up with so ...
1
vote
0answers
12 views

Clarification about a proof regarding a sum of polynomials being expressed as a linear combination of S-polynomials

I'm reading this proof from Ideals, Varieties, and Algorithms by David A. Cox, Donal O'Shea, and John Little. You can find an online version here. This is Lemma 5 of Chapter 2, page 85. From my ...
0
votes
0answers
34 views

How to find polynomials satisfying a given ideal of relations

I have come across results/algorithms on how, given a set of polynomials in $k[x_1,\ldots,x_n]$ ($k$ a field) to find the ideal of relations. E.g. $k[a^2,ab,c^2] \cong k[x,y,z]/(xy-z^2)$ I am ...
1
vote
2answers
47 views

Does the vector space spanned by a Gröbner basis depend on the monomial order?

Let $k$ be a field, $n$ a natural number, and $I$ an ideal of $k[x_0,\dots,x_{n-1}]$. Given a monomial order $M$ on $k[x_0,\dots,x_{n-1}]$ let $G_M$ be the Gröbner basis of $I$ with respect to $M$ and ...
0
votes
0answers
12 views

Gröbner basis vs Brute Force Attacks on GF(2) polynomial system of equations?

I'm studying cryptography and I have a question regarding the complexity analysis of algorithms. In AES cryptography, the Gröbner basis algorithm for solving systems of polynomial equations over the ...
4
votes
2answers
99 views

Finite Algebras and Grobner Bases

Background Suppose that $A$ is a finite $\mathbb{R}$-algebra, that is, it is finite-dimensional as an vector space. By a consequence of the Hilbert-basisatz, since $\mathbb{R}$ is Noetherian, then so ...
1
vote
1answer
36 views

Finiteness of an algebraic variety $V(I) \subseteq \mathbb{C}^n$ where $I$ is a zero dimensional ideal of $\mathbb{C}[x_1,\dots,x_n]$

How to demonstrate this?: Let I be an ideal of $\mathbb{C}[x_1,\dots,x_n]$ such that $\frac{\mathbb{C}[x_1,\dots,x_n]}{I}$ has finite dimension ($I$ is a zero dimensional ideal). Then $V(I) \subseteq ...
0
votes
1answer
81 views

Vector space basis for a quotient ring

Given the polynomial ring $\mathbb{F}_2[x,y,z]$ with some ideal $I$, what is the method to find a basis (as a vector space over $\mathbb{F}_2$) for the quotient ring $R/I$? For example, take $$ S = \...
0
votes
0answers
50 views

Can I solve a system of high-degree polynomial equations with the Gröbner basis method?

I have two equations, two unknown (ISP, ch) and one parameter ($n_C$). My aim is to find the values of the unknown according to the parameter. The original rational equations are here : https://...
0
votes
1answer
26 views

Question about the exact definition of a Groebner basis

So the definition I learned is that a set $G = \{g_1,...g_t\}$ is a Groebner basis for an ideal I if $<Lt(g_1),...Lt(g_t)> = <LT(I)>$ However I'm not sure if it also requires the set G ...
1
vote
1answer
50 views

Combining Grobner bases for sum of ideals

Let $\{g_1,\dots,g_n\}$, $\{f_1,\dots,f_m\}$ be Grobner bases of polynomial ideals $G,F\subset \mathbb{R}[x_1,\dots,x_k]$, respectively, under some monomial ordering. When is $\{g_1,\dots,g_n,f_1,\...
1
vote
4answers
77 views

How to solve simultaneous linear equations with only two possible values per variable?

I am trying to solve a system of simultaneous linear equations whose unknowns have only two possible values. How do I approach this, or what area of mathematics do I employ inorder to arrive at the ...
4
votes
1answer
701 views

Coefficients such that linear combination lies in an ideal

Let $R$ be a ring, $I$ an ideal, and $\langle g_1, \ldots, g_m \rangle$ a finitely generated ideal. Considering the intersection $I \cap \langle g_1, \ldots, g_m \rangle$, I became interested in the ...
3
votes
1answer
153 views

Skew-symmetric multi-derivations of $k[x_1,\ldots,x_n]/I$

Let $I = \langle f_1, \ldots f_r \rangle$ be an ideal in $R=k[x_1,\ldots,x_n]$ where $k$ is a field, and put $A = R/I$. (If $k$ is algebraically closed and $I$ is radical then $A$ is the coordinate ...
1
vote
0answers
52 views

Groebner base from tdeg order to plex order

I try to solve an equation by using Groebner bases. When I use Maple to find its Groebner basis with plex order, Maple take too long to calculate and the proceed does not terminate. Thus, I try to ...
0
votes
0answers
64 views

How to minimize the following polynomial over a four-dimensional sphere: $(c_0x_0^2+c_1x_1^2+c_2x_2^2+c_3x_3^2)^2+\sum_{nm}c_{nm} x_nx_m $

I need to find the global minimum of the following polynomial over a four-dimensional sphere. $$f(x_0, x_1, x_2, x_3) = \left( \sum\limits_{j=0}^3 c_j x_j^2 \right)^2 + \sum\limits_{n,m=0}^3 c_{nm} ...
1
vote
1answer
84 views

Why doesn't Buchberger's algorithm solve Hilbert's tenth problem?

I've been reading a bit about Buchberger's algorithm and Groebner bases. I'm not really trying to understand the math behind it at this point, just trying to get an idea of how the method could be ...
2
votes
1answer
52 views

Choosing different term orders for Groebner basis calculations in GAP

I am using the QPA and GBNP packages in GAP to analyze path algebra quotients. I use the GBNP package for computing Groebner bases for the ideals in the path algebras, and the term orders for these ...
2
votes
0answers
50 views

Quotienting by the Leading Term Ideal

Somewhat related to this question, I'm looking for sources that give a proof of $$S / I \cong S/\mathrm{LT}(I),$$ where $I \lhd S = k[x_1, ..., x_n]$ for $k$ a field, and the isomorphism is an ...
0
votes
0answers
54 views

Maple Groebner Basis

I am asking for the help dealing with maple to compute groebner basis and to compute the normalf function. When I insert the codes for example: gbasis (.....) normalf (....) and then I press enter the ...
0
votes
0answers
63 views

Groebner base optimal solution with inequalities

I have to solve the following optimization problem using Groebner bases. The objective function is $$x_1+x_2+x_3+x_4$$ with constraints $$x_1+x_2 \ge 1, \qquad x_1+x_2+x_3 \ge 1, \qquad x_2+x_3+x_4 ...
1
vote
1answer
56 views

Solution to polynomial equation

I have the following quite simply looking equation $$ \frac{c_1 d_1}{c_2+c_3}=\frac{c_2 d_2}{c_1+c_3} = \frac{c_3 d_3}{c_2+c_1}$$ and I want to solve it for $c_1, c_2,c_3$. I know that these ...
0
votes
0answers
20 views

Remainder after polynomial division in more than one variable

So I was trying to show that some polynomial $P$ has a specific remainder, let's just call it $r$, if divided by some Gröbner basis $G=(g_1,...,g_m)$ for an ideal $I=(f_1,...,f_n)$ (ie the ideal for ...
2
votes
0answers
24 views

Compute equalizer of map of polynomial rings, perhaps using Gröbner bases?

Suppose that $k$ is a field and I have two ring homomorphisms $f, g: 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
27 views

Question about implization theorem and Gröbner basis

This exercise is in the book Ideals, Varieties, and Algorithms. Exercise. Given a rational parametrization as in (7), there is one case where the naive ideal $I = \langle g_1x_1 − f_1, \dots , ...
1
vote
0answers
52 views

Reduces to $0$ of $S$-polynomial.

It is problem 2.17 in the book Gröbner Bases in Commutative Algebra, by Ene and Herzog. Let $f,g \in S$ such that $\textrm{in}_{<}(f)$ and $\textrm{in}_{<}(g)$ are relatively prime and let $u$...
0
votes
2answers
63 views

Complete generating sets for the following. Groebner basis

Let $I $ denote the ideal in $Q [x,y,z]$ generated by $[x^2+y^2,xz−y,z^3−zy^3,xy+zy^2]$ Compute a generating set for $ I∩Q[y].$ Compute a generating set for $ I∩(y). $ Compute a generating set for $...
0
votes
1answer
31 views

A question about the definition of reduced Gröbner basis

I am reading Professor Sturmfels's article What Is...a Gröbner Basis? In the definition of reduced Gröbner basis, I met a term trailing term of a polynomial. I do ...
1
vote
1answer
54 views

Properties of Groebner bases

Let us consider the polynomial ring $A:=\mathbb{R}[x_1,x_2,\dots]$ and consider the family consisting of the empty set and of all the subsets of polynomials $G$ such that there exists an ideal of $A$ ...
0
votes
0answers
36 views

numerical calculation of principal ideal generator in polynomial ring

I will first state my problem and explain where I am at with the problem. Let $I$ be a principle ideal generated by a single, multivariate polynomial $p \in \mathbb{C}[z_1,z_2,z_3]$. I estimate a ...
5
votes
1answer
116 views

Largest subgroup in which a given polynomial is invariant.

I am trying to solve the following question; Given a polynomial $f\in \mathbb{C}[x_{1},x_{2},\ldots,x_{n}]$, find the largest subgroup $\Gamma\le GL(\mathbb{C}^{n})$ such that $f\in \mathbb{C}[x_{1},...
0
votes
1answer
64 views

How do I compute the reduced Groebner Basis?

I am trying to do a question on Hilbert's Weak Nullenstratz theorem for the 3 colouring of vertices and i know i need to compute the reduced Groebner Basis (GB) for the following Ideal: $$I:= <x_{...
3
votes
2answers
56 views

How do i computed the Groebner Basis for this ideal?

I have the ideal $$\begin{split}I_{k} &= \langle\,\, x_{1}^{3}-1,\\ &\qquad x_{1}^{2}+x_{1}x_{2}+x_{2}^{2},\\ &\qquad x_{1}^{2}+x_{1}x_{3}+x_{3}^{2},\\ &\qquad x_{2}^{3}-1,\\ &\...
0
votes
1answer
53 views

Can a generating set for a polynomial ideal have less elements than a minimal Gröbner base?

Let $\mathbb{K}$ be a field and $I\subset \mathbb{K}[x_1, \dots, x_n]$ an ideal. Then minimal Gröbner bases for $I$ (with respect to same monomial order) have the same number of elements, which is ...
2
votes
1answer
52 views

Gröbner basis of subideals

Let $I$ be an ideal with a Gröbner basis $B_1:=\{ g_1, \dots, g_n\}$. Let $J$ be an ideal containing $I$ with the basis $B_2:=\{ g_1, \dots, g_n, \dots, g_{n+m}\}$, which is not necessarily a Gröbner ...
0
votes
0answers
52 views

Changing basis of indeterminates in polynomial ring

In the polynomial ring $R={\mathbb Q}[a,b,c,d,\beta_0,\beta_1,\beta_2,\beta_3]$, consider the quotient commutative algebra $A=R/I$ where $I$ is the ideal generated by the four polynomials $$ \begin{...
3
votes
0answers
80 views

Universal Gröbner basis for $I = \left<x - y^nz \,\, | \,\, n \in \mathbb{N}\right>$

Earlier today I gave an exam on the theory of Gröbner bases and I could not solve the last bonus question. Here it is: Find the universal Gröbner basis for the ideal $I = \left<x - y^nz \,\, | \...
1
vote
1answer
71 views

compute $ \operatorname{Spec}\mathbb{Z}[x,y]/(x^2+y^2-n) $

In order to study the equation $x^2 + y^2 = n$ I'd like to understand the related commutative ring $$ R = \mathbb{Z}[x,y]/(x^2+y^2-n)$$ I'd like compute the spectrum of this ring. What are the prime ...
0
votes
1answer
59 views

The reduced basis for a binomial ideal is formed by binomials

I was able to prove that a binomial ideal in $K[X_1,\ldots,X_n]$ (generated by $X^\alpha - X^\beta$) has a Gröbner basis formed by binomials by using Buchberger's algorithm. But how can I prove ...
0
votes
0answers
141 views

Finite set of generators of monomial ideal form Gröbner basis

Given a set of monomials $\{G_1,\ldots,G_t\}$ generating a non-null monomial ideal $I \le K[X_1,\ldots,K_n]$ I would like to check that they form a Gröbner basis. This is done by Buchberger's ...
1
vote
1answer
87 views

Grobner basis of an ideal $I$

Let $R = \mathbb{R}[X,Y]$ and let $\succcurlyeq$ be a monomial ordering on $M(X,Y)$. Let $I$ be the ideal $\left<X^3, X^2Y,XY^2,Y^3\right>$. Why can't $I$ have a Grobner basis consisting of $3$ ...
1
vote
0answers
33 views

$ \langle lt(g_1),…, lt(g_t) \rangle = in_<(I) \implies G $ is a Grobner basis for I

Let $I$ be a non-zero ideal of the polynomial ring $S:=K[x_1,...,x_n]$ (where $K$ is a field) , which is equiped with a monomial ordering $<$, and $G:=\{g_1,...,g_t \}\subseteq I$. We want to show ...
0
votes
1answer
52 views

System of nonlinear polynomial/logrational equations

Are there any known methods which can be used to solve system of equations of the form $$ \begin{align} \ln \frac{P_1(x_1,\ldots,x_n)}{Q_1(x_1,\ldots,x_n)} + R_1(x_1,\ldots,x_n) &= 0 \\ &\...
1
vote
0answers
39 views

Linear algebraic methods to compute Gröbner bases?

I know of the famous Buchberger algorithm to find Gröbner bases. However I am curious if it is not somehow possible to compute them using only linear algebra. Own Work: The little I know so far is ...
1
vote
1answer
68 views

Computing lcm with Groebner basis.

I have the instructions to compute the lcm of two multivariate polynomials ideals. My course follows the spirit of "Ideals, Varieties and Algorithms" by Cox et alii. However, my recipe doesn't ...
1
vote
1answer
190 views

Uniqueness of reduced Groebner basis - proof

can you please help me understand something. I defined minimal GB like this: Let $G = \{g1, . . . , gs\}$ be a GB of an ideal $I ⊂ k[x1, . . . , xn]$. Then $G$ is a minimal GB if and only if for ...
1
vote
3answers
54 views

Complete solution for a system of polynomial equations

A research question led to the following system of polynomial equations. \begin{align*} & x^3 - x^2y + x^2z + x^2 - xy + xz + y^2 - yz - y = 0 \\ & x^3z - 3x^2y + 3xy^2 + xz^2 - y^3 + y^2 ...
1
vote
1answer
54 views

$xy_1\in\langle x^2y_1,x^2y_2-xy_1,\dots,x^ny_n-xy_1\rangle$?

Let $k$ be a field; let $n$ be an integer $\ge2$; let $x,y_1,\dots,y_n$ be indeterminates; and let $I$ be the ideal $$ \langle x^2y_1,x^2y_2-xy_1,\dots,x^ny_n-xy_1\rangle $$ in $k[x,y_1,\dots,y_n]$. ...
0
votes
1answer
77 views

Find Hilbert Basis of Magic Square Equations

How to find Hilbert basis of these equations? $x_1 + x_2 + x_3 = x_4 + x_ 5 + x_6 = x_7 + x_8 + x_9 $ $x_1 + x_4 + x_7 = x_2 + x_ 5 + x_8 = x_3 + x_6 + x_9 $
2
votes
2answers
98 views

number of points needed to check if a special polynomial remainder is zero

We know $f(x,y)$ is a polynomial in $x$ and $y$ with integer coefficients and degree of $x$ and $y$ less than or equal to two: $f(x,y)=\sum_{i,j\epsilon \left \{ 0,1,2 \right \}}a_{ij}x^i y^j$ where ...