# 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 refers to a polynomial in some ring, say $\mathbb{Q}[x]$. If I know that $f$ is irreducible, and that $f$ is coprime to both $q$ and $n$, then the equation is unsolvable. I can introduce the coprimality without too much trouble, and get a system of equations:

$$qn = mf$$ $$an+bf = 1$$ $$cq+df = 1$$

Yet this system can still be solved. If $f=1$ and $m=qn$, for example. $a=1$, $b=1-n$, $c=1$, $d=1-q$ and $q$ and $n$ can be any polynomials at all. How can I restrict $f$ to be an irreducible polynomial?

This is a simple example; I'm looking for a general technique akin to Groebner bases.

I realize that the Groebner basis calculation is done in $\mathbb{Q}[q,n,m,f,a,b,c,d]$, but these variables map into another ring, $\mathbb{Q}[x]$, so the perspective should be that of algebraic geometry.

In short: Given a system of polynomial equations mapping into some ring, with some of them restricted to be prime elements, how can I determine if there is no solution?

• Two comments: 1) This depends very much on the field you want your solutions from. Real root finding for instance is a branch of real algebraic geometry. 2) Gröbner bases can't help you since you can't use them to decide if a single polynomial is irreducible. You need factorization algorithms and then 1) comes into play. – Thomas Kahle Sep 4 '15 at 7:34
• And 3) The irreducibility is hard to model in this framework, but over an algebraically closed field there is of course the Nullstellensatz which can give infeasibility certificates. – Thomas Kahle Sep 4 '15 at 7:35
• I've thought of this: Since $f$ is irreducible and thus prime, I can mod out by $f$ and still have an integral domain. Then my system becomes $qn=0$, $an=1$, and $cq=1$, which is impossible without zero divisors. I think I can still come up with systems where mod'ing by $f$ doesn't produce an obviously inconsistent system, but it's a start. – Brent Baccala Sep 4 '15 at 20:12
• Is it not feasible to solve the problem without irreducibility constraints, and then look for the solutions that happen to be irreducible? – user13113 Sep 5 '15 at 0:20
• @Hurkyl Not in the more complex cases. For example, if we're looking for solutions to the heat equation $\Psi_{xx}=\Psi_t$ in the function field $\mathbb{C}(x,t)$, then considering an irreducible factor in the denominator and realizing that it's impossible reduces the solution space to the polynomial ring $\mathbb{C}[x,t]$. There are other ways (the Weyl closure of the singular locus) to handle this example, but I've got more complex cases still where the singular locus doesn't help. Right now, I'm trying to make irreducibility a big criterion for throwing out impossible cases in my theory. – Brent Baccala Sep 7 '15 at 6:42

Look at it like this. We have a ring $R=K[x_1,\ldots,x_n]$ and a ring $S=K[y]$. We want to treat the $x_i$s as polynomials in $y$, so we're looking for a mapping $f:R\to S$ that sends each $x_i$ to a polynomial in $y$ and satisfies a system of polynomial equations $P$ in the $x_i$. In other words, we want $f$ to be a ring homomorphism that sends $I(P)$ to 0. $f$, the map from $R$ to $S$, is the solution we seek.

Now we want to impose an additional condition: a subset $x_1,\ldots,x_i$ must map to irreducible elements $y_1,\ldots,y_i$ in $S$. Since $y_1,\ldots,y_i$ are irreducible, they are prime (in $S$), so we quotient with respect to their ideal $I$ and get a quotient ring $S/I$ that is an integral domain. We can also quotient $R$ by the ideal generated by $x_1,\ldots,x_i$ (call it $J$), and get $R/J$. $f$ can be similarly restricted, and now we have a homomorphism $\hat{f}: R/J \to S/I$. We can construct a Gröbner basis for $R/J$ by appending the $x_i$ that must be irreducible to the original system $P$, and reducing $P \cup \{x_1,\ldots,x_i\}$ to a Gröbner basis. This new Gröbner basis gives relationships satisfied by the equivalence classes in $S/I$. "Equal to zero" in this quotient system means "equal to zero or a multiple of an irreducible element" in the original system. However, if the quotient system is inconsistent, then the original system is also inconsistent, at least subject to the restriction that $x_1,\ldots,x_i$ must map to irreducibles.

Can we find additional relationships? Surprisingly, yes! We run this calculation with each irreducible individually. Pick one $x_1,\ldots,x_i$, call it $x_j$, compute a quotient Gröbner basis for $P \cup \{x_j\}$, take each polynomial in the quotient system's Gröbner basis and test to see if it's in the original system. If so, then it's really equal to zero. Otherwise, it's a multiple of $x_j$ and we can add that polynomial to the original system, equating it a term of the form $m x_j$, with $m$ a new indeterminate.

The augmented system will have extraneous zeros, at least if we require the irreducible polynomials to be non-zero. We can handle this by computing a primary decomposition and throwing away any primary components that include an irreducible element among their zeros. This is the ideal-theoretic equivalent of factoring a polynomial that must be equal to zero and throwing away factors that we know are non-zero. We can keep repeating these two processes (quotient ring basis and primary decomposition) until our ideal stabilizes.

Example

Consider the equation $af^2+bf+c=0$, with $f$ restricted to be irreducible.

Step 1: Form the system $\{af^2+bf+c, f\}$ and reduce to the Gröbner basis $\{f,c\}$. Of course $f$ is here; our interest is $c$. Since it isn't in the original ideal, it must be a multiple of $f$, so we add $c-mf$ our ideal to obtain

$$(af^2+bf+c, c-mf)$$

Step 2: A primary decomposition of this ideal gives two primary ideals, one of which is $(f,c)$. Since $f$ can't be zero, we throw it away and continue with the other primary ideal:

$$(af+b+m, ac+bm+m^2, c-mf)$$

Step 3: Back to the quotient calculation. Now our system is

$$\{af+b+m, ac+bm+m^2, c-mf, f\}$$

and we compute the Gröbner basis $\{f, c, b+m\}$. This implies that $b+m$ must also be a multiple of $f$, so we add $b+m-nf$ to our ideal, obtaining

$$(af+b+m, ac+bm+m^2, c-mf, b+m-nf)$$

Step 4: Another primary decomposition gives another extraneous ideal $(f,c,b+m)$. Throwing this away, we have

$$(a+n, fn-b-m, fm-c, bm+m^2-cn)$$

Step 5: A final quotient calculation, with the system

$$\{a+n, fn-b-m, fm-c, bm+m^2-cn, f\}$$

gives $\{f,c,b+m,a+n\}$, of which the only new element, $a+n$, reduces to zero.

So we've stabilized on

$$(a+n, fn-b-m, fm-c, bm+m^2-cn)$$

This ideal encodes all of the information I was able to extract in Polynomial constraints triggered by irreducibility