text:
# 1. Introduction

## 1. Introduction

The theme of this paper is solving nonlinear operator equations of the form:

(1.1)
$$F(x)=0,F:HH,$$

in a real Hilbert space $`H`$. We consider a real Hilbert space for the sake of simplicity: numerical algorithms for solving (1.1) in a complex Hilbert space can be treated similarly. In order to approximate a solution to equation (1.1) we use the idea developed in -, which consists of constructing a dynamical system with the trajectory starting at some initial point $`x_0`$ and converging to a solution of (1.1) as $`t+\mathrm{}`$. This idea, in its simplest form goes back to A.Cauchy (steepest descent) and was proposed in  for solving some optimization problems by a continuous analog of the gradient method. In  a wide class of linear ill-posed problems was studied by the dynamical systems method. In  a continuous Newton’s scheme

(1.2)
$$\dot{x}(t)=[F^{}(x(t))]^1F(x(t)),x(0)=x_0H,$$

was studied and a theorem establishing convergence with the exponential rate was proved. A modified continuous Newton’s method is proposed in :

(1.3)
$$\dot{x}(t)=J(t)F(x(t)),x(0)=x_0H,J(0)L(H),$$

(1.4)
$$\dot{J}(t)=\mu \left[F^{}(x(t))F^{}(x(t))J(t)+J(t)F^{}(x(t))F^{}(x(t))\right]+2\mu F^{}(x(t)),$$

where $`\mu `$ is a positive constant. System (1.3)-(1.4) avoids the inversion of the Fréchet derivative $`F^{}(x)`$, which is numerically difficult in some applications.

The regularized Gauss-Newton’s-type algorithm with simultaneous updates of the operator $`[F^{}(x(t))F^{}(x(t))+\epsilon (t)I]^1`$ was proposed in :

(1.5)
$$\dot{x}(t)=D(t)\left[F^{}(x(t))F(x(t))+\epsilon (t)(x(t)x_0)\right],$$

(1.6)
$$\dot{D}(t)=\left[(F^{}(x(t))F^{}(x(t))+\epsilon (t)I)D(t)I\right],$$

$$x(0)=x_0H,D(0)L(H),0<\epsilon (t)0\text{as}t+\mathrm{}.$$

It is shown that $`x(t)`$ converges to a solution of (1.1) at the rate $`O(\epsilon (t))`$. The convergence theorem is proved without assuming monotonicity of $`F`$ and bounded invertibility of $`F^{}(x)`$.

In  and  a fairly general approach to the analysis of continuous procedures in a Hilbert space was developed. According to this approach one investigates a solution to the Cauchy problem for a nonlinear operator-differential equation by using differential inequalities. In the well-posed case (the Fréchet derivative operator $`F^{}(x)`$ is boundedly invertible in a ball, which contains one of the solutions) one investigates the Cauchy problem for an autonomous equation:

(1.7)
$$\dot{x}(t)=\mathrm{\Phi }(x(t)),x(0)=x_0.$$

The choice of $`\mathrm{\Phi }:HH`$ yields a corresponding continuous process. In the ill-posed case ($`F^{}(x)`$ has a nontrivial null-space at the solution (1.1) or is not boundedly invertible) a regularized continuous procedure is required. For this reason the Cauchy problem for the following equation is to be analyzed:

(1.8)
$$\dot{x}(t)=\mathrm{\Phi }(x(t),t),x(0)=x_0,$$

with $`\mathrm{\Phi }:H\times [0,+\mathrm{})H`$. If one takes

$$\mathrm{\Phi }(h,t):=[F^{}(h)+\epsilon (t)]^1(F(h)+\epsilon (t)(hx_0)),$$

then one arrives at a continuously regularized Newton’s scheme (CRNS). The convergence analysis of CRNS is done in  under the assumption that $`F^{}(x)0`$ as an operator in $`H`$. For

$$\mathrm{\Phi }(h,t):=[F^{}(h)F^{}(h)+\epsilon (t)]^1(F^{}(h)F(h)+\epsilon (t)(hx_0))$$

one obtains continuously regularized Gauss-Newton’s scheme (CRGNS). The convergence theorems for CRGNS (see  and ) do not use any assumption about the location of the spectrum of $`F^{}(x)`$. The absence of such assumption is made possible by source-type conditions.

In section 2 of our paper we study a continuous analog of a modified Newton’s method:

(1.9)
$$\dot{x}(t)=[F^{}(x_0)]^1F(x(t)),x(0)=x_0H,$$

for solving well-posed nonlinear operator equation (1.1). Theorem 2.18 establishes exponential convergence of (1.9) to a solution of (1.1). Process (1.9) can be used in practical computations when calculating and inverting of $`F^{}(x)`$ at each moment of time require a considerable effort. Another continuous algorithm, investigated in section 2:

(1.10)
$$\dot{x}(t)=B(t)F(x(t)),x(0)=x_0H,B(0)=B_0L(H),$$

(1.11)
$$\dot{B}(t)=F^{}(x(t))F^{}(x(t))B(t)+F^{}(x(t)),$$

can also be recommended in the above situation. It allows one to update $`[F^{}(x)]^1`$ continuously for $`t[0,+\mathrm{})`$ without actual inversion of the Fréchet derivative. In Theorem 2.34 the exponential convergence of (1.10)-(1.11) to a solution of (1.1) is proved.

For many important inverse problems of the form (1.1) the operator $`F^{}(x)`$ is not boundedly invertible. For such problems the regularized version of algorithm (1.9) is suggested in section 3

(1.12)
$$\dot{x}(t)=[F^{}(x_0)+\epsilon (t)I]^1(F(x(t))+\epsilon (t)(x(t)x_0)),x(0)=x_0H,\epsilon (t)>0.$$

The convergence analysis of continuous regularized method (1.12) is done in Theorem 3.7 under the following assumption:

(1.13)
$$F^{}(x)=F^{}(x_0)G(x_0,x),$$

where

(1.14)
$$G(x_0,x)IC(G)x_0x,x_0,xU(\rho ,\widehat{x}),$$

and $`\widehat{x}`$ is a solution to (1.1). Assumption (1.13)-(1.14) is similar to condition (8) in . It means that the operator $`F^{}(x)`$ remains in principle the same for all $`x`$ in a neighborhood of a solution up to some modification by a linear operator $`G(x_0,x)`$. The reader may consult  for several examples of nonlinear inverse problems for which condition (1.13)-(1.14) can be verified. As a consequence of Theorem 3.7 we obtain the stability of process (1.12) towards noise in the data and choose an optimal regularization parameter (the stopping time) such that the method converges to a solution of (1.1) when the noise level tends to zero.

Our main motivations for this investigation are:

1) We think that the dsm (dynamical systems method) that we develop in this paper (and in the earlier publications,cited in the references) is not only of theoretical interest, but also provide a powerful numerical tool for solving very wide variety of problems, namely all the problems which can be described by equation (1.1) with the nonlinearity satifying the assumptions of our theorems formulated in Sections 2 and 3.

2) We think that the idea of constructing a method for solving equation (1.1) which does not require inverting $`F^{}(u)`$ (see, for example, equations (2.21) and (2.22) below) is of both theoretical and practical interest even for well-posed problems.

3) The dsm gives a general approach to constructing convergent iterative methods for solving ill-posed nonlinear problems. We do not address this part of the dsm in our present paper, but it has been addressed in detail in .

Finally we note that the dsm was tested numerically (see , ,  for example), but it certainly of interest to study much more the numerical performance of dsm. In this paper, however, the authors deal with the theoretical questions.

## 2. Continuous modified Newton’s schemes for well-posed problems

In this section we solve nonlinear operator equation (1.1) under the assumption that the Fréchet derivative of the operator $`F`$ is boundedly invertible in a ball which contains one of the solutions. Let $`x_0`$ be an initial approximation for a solution to (1.1) and $`x(t)`$ be a trajectory of the autonomous dynamical system

(2.1)
$$\dot{x}(t)=\mathrm{\Phi }(x(t)),0t<+\mathrm{},x(0)=x_0.$$

Lemma 2.6 below (see ) gives simple sufficient conditions on nonlinear operators $`F`$ in (1.1) and $`\mathrm{\Phi }`$ in (2.1) which guarantee that:

(a) initial value problem (2.1) is uniquely solvable for all $`t[0,+\mathrm{})`$;

(b) the solution $`x(t)`$ tends to one of the solutions of (1.1) as $`t+\mathrm{}`$.

###### Lemma 2.1.

Let $`H`$ be a real Hilbert space, $`F,\mathrm{\Phi }:HH`$.

Suppose that there exist some positive numbers $`c_1`$ and $`c_2`$ such that $`F`$ and $`\mathrm{\Phi }`$ are Fréchet differentiable in $`U(r,x_0):=\{xH,xx_0r\}`$, $`r:=\frac{c_2F(x_0)}{c_1}`$ and $`hU(r,x_0)`$ the following conditions hold

(2.2)
$$(F^{}(h)\mathrm{\Phi }(h)),F(h))c_1||F(h)||^2,$$

and

(2.3)
$$\mathrm{\Phi }(h)c_2F(h).$$

Then:

1. there exists a global solution $`x=x(t)`$ to problem (2.1) in the ball $`U(r,x_0)`$;

2. there exists

(2.4)
$$\underset{t+\mathrm{}}{lim}x(t)=\widehat{x},$$

where $`\widehat{x}`$ is a solution to (1.1) in $`U(r,x_0),`$ and

(2.5)
$$x(t)\widehat{x}re^{c_1t},$$

(2.6)
$$F(x(t))F(x_0)e^{c_1t}.$$

Proof. From the Fréchet differentiability of $`\mathrm{\Phi }`$ the local existence of a solution to (2.1) follows, and from (2.1) one gets:

(2.7)
$$\frac{d}{dt}\{F(x(t))\}=F^{}(x(t))\dot{x}(t)=F^{}(x(t))\mathrm{\Phi }(x(t)).$$

Let $`\lambda (t):=F(x(t))`$. Then

(2.8)
$$\dot{\lambda }(t)=F^{}(x(t))\mathrm{\Phi }(x(t)),\lambda (0)=F(x_0).$$

At least for sufficiently small $`t`$, for which $`x(t)U(r,x_0)`$, one can use estimate (2.2) and get:

(2.9)
$$\frac{1}{2}\frac{d}{dt}\lambda (t)^2=(\dot{\lambda }(t),\lambda (t))=(F^{}(x(t))\mathrm{\Phi }(x(t)),F(x(t)))c_1\lambda (t)^2.$$

Thus, at least for sufficiently small $`t0,`$ one gets:

(2.10)
$$\lambda (t)F(x_0)e^{c_1t}.$$

For $`0t_1t_2`$ by (2.3) one has

$$x(t_2)x(t_1)_{t_1}^{t_2}\dot{x}(s)𝑑s_{t_1}^{t_2}\mathrm{\Phi }(x(s))𝑑sc_2_{t_1}^{t_2}\lambda (s)𝑑s$$

(2.11)
$$\frac{c_2F(x_0)}{c_1}\left(e^{c_1t_1}e^{c_1t_2}\right)<\frac{c_2F(x_0)}{c_1}e^{c_1t_1}.$$

Setting $`t_1=0`$ and $`t_2=t`$, one concludes from (2.11) that $`x(t)U(r,x_0)`$ with $`r=\frac{c_2F(x_0)}{c_1}`$ whenever it is defined. Therefore the standard argument yields existence and uniqueness of a solution to (2.1) on $`[0,+\mathrm{})`$. Now let in (2.11) $`t_1=t`$ and $`t_2+\mathrm{}`$ . Then one gets (2.5), and the limit $`\widehat{x}`$ in (2.4) does exist due to (2.11). From (2.10) one concludes that $`\widehat{x}`$ is a solution to (1.1). Inequality (2.6) follows from (2.10). Lemma 2.1 is proved. ∎

###### Remark 2.2.

Assumptions of Theorem 2.18 do not imply uniqueness of a solution to equation (1.1). If (1.1) is not uniquely solvable then $`x(t)`$ converges to one of its solutions in $`U(r,x_0)`$.

In Lemma 2.1 we have assumed that $`c_1`$ and $`c_2`$ are some known constants in the ball $`U(r,x_0)`$, and this assumption allowed us to define $`r`$ explicitly in terms of the ratio $`\frac{c_2}{c_1}`$ and $`F(x_0)`$. One may assume that $`\frac{c_2}{c_1}`$ is not a constant but a function of $`r`$, $`\frac{c_2}{c_1}:=c(r).`$ In this case , in order that the argument of Lemma 2.1 be valid, one has to satisfy the inequality $`c(r)F(x_0)r`$. For example, if $`\frac{c(r)}{r}0`$ as $`r\mathrm{}`$, then there always exists an $`r>0`$ such that the conclusion of Lemma 2.1 holds and the assumptions of this lemma are satisfied in the ball $`U(r,x_0)`$.

Now consider the following continuous modified Newton’s scheme:

(2.12)
$$\dot{x}(t)=[F^{}(x_0)]^1F(x(t)),x(0)=x_0H.$$

Theorem 2.18 below establishes a relation between the asymptotic behavior of a solution $`x(t)`$ to (2.12) and solutions to equation (1.1). It is a consequence of Lemma 2.6.

###### Theorem 2.3.

Let $`H`$ be a real Hilbert space, $`F:HH`$. Assume that $`F`$ is Fréchet differentiable, its Fréchet derivative $`F^{}`$ is Lipschitz-continuous:

(2.13)
$$F^{}(x_1)F^{}(x_2)M_2x_1x_2x_1,x_2U(\stackrel{~}{r},x_0),$$

where

(2.14)
$$U(\stackrel{~}{r},x_0):=\{xH,xx_0\stackrel{~}{r}\},\stackrel{~}{r}:=\frac{1}{2M_2m_1},m_1:=[F^{}(x_0)]^1,$$

and

(2.15)
$$4M_2m_1^2F(x_0)1.$$

Then

1. There exists a unique solution $`x=x(t)`$, $`t[0,+\mathrm{})`$, to problem (2.12).

2. $`x(t)U(\stackrel{~}{r},x_0)t[0,+\mathrm{})`$, and

(2.16)
$$\underset{t+\mathrm{}}{lim}x(t)=\widehat{x},$$

where $`\widehat{x}`$ is a solution to (1.1).

3. The following estimates hold:

(2.17)
$$x(t)\widehat{x}2m_1F(x_0)e^{\frac{t}{2}},$$

(2.18)
$$F(x(t))F(x_0)e^{\frac{t}{2}}.$$

Proof. Take

(2.19)
$$\mathrm{\Phi }(x(t)):=[F^{}(x_0)]^1F(x(t)).$$

Then, under assumptions (2.13) and (2.14) of Theorem 2.18, one gets $`hU(\stackrel{~}{r},x_0)`$

$$(F^{}(h)\mathrm{\Phi }(h),F(h))=(F^{}(h)[F^{}(x_0)]^1F(h),F(h))=F(h)^2$$

$$+(\{IF^{}(h)[F^{}(x_0)]^1\}F(h),F(h))=F(h)^2+(\{F^{}(x_0)F^{}(h)\}[F^{}(x_0)]^1F(h),F(h))$$

(2.20)
$$F(h)^2+M_2m_1\stackrel{~}{r}F(h)^2=\frac{1}{2}F(h)^2.$$

Also one has $`\mathrm{\Phi }(h)m_1F(h)`$. Thus conditions (2.2) and (2.3) of Lemma 2.6 hold for any $`hU(\stackrel{~}{r},x_0)`$ with $`\mathrm{\Phi }`$ defined in (2.19), $`c_1=\frac{1}{2}`$ and $`c_2=m_1`$. Hence $`r:=\frac{c_2F(x_0)}{c_1}=2m_1F(x_0)`$. From (2.14) and (2.15) one has $`\mathrm{\hspace{0.17em}\hspace{0.17em}2}m_1F(x_0)\frac{1}{2M_2m_1}:=\stackrel{~}{r}`$. Therefore (2.2) and (2.3) are satisfied on $`U(r,x_0)`$, $`r:=\frac{c_2F(x_0)}{c_1}`$, $`c_1=\frac{1}{2}`$, $`c_2=m_1`$. Applying Lemma 2.6, one completes the proof. ∎

###### Remark 2.4.

(a) Choosing $`\mathrm{\Phi }(h)=[F^{}(h)]^1F(h)`$ one gets Continuous Newton’s method. In this case $`c_1=1,`$ $`c_2=\mu _1:=sup_{xU(r,x_0)}[F^{}(x)]^1,`$ and Lemma 2.6 yields the convergence theorem for Continuous Newton’s method .

(b) Choosing $`\mathrm{\Phi }(h)=F(h)`$, one gets a simple iteration method, for which condition (2.2) means strict monotonicity of $`F`$: $`F^{}c_1>0,`$ and $`c_2=1`$.

(c) $`\mathrm{\Phi }(h)=[F^{}(h)]^{}F(h)`$ corresponds to the gradient method.

Here $`c_2=M_1:=sup_{xU(r,x_0)}F^{}(x)`$, and $`c_1=\mu _1^1`$.

(d) $`\mathrm{\Phi }(h)=[F^{}(h)F^{}(h)]^1F^{}(h)F(h)`$ yields Continuous Gauss-Newton’s scheme. Here $`c_1=1`$, $`c_2=\mu _1^2M_1`$, where $`\mu _1`$ is the same as in (a) above, and $`M_1`$ is the same as in (c) above.

In order to avoid inversion of the Fréchet derivative $`F^{}(x(t))`$ even at the initial moment $`t=0,`$ one can consider the following algorithm, which is a Cauchy problem for a system of two equations:

(2.21)
$$\dot{x}(t)=B(t)F(x(t)),x(0)=x_0H,B(0)=B_0L(H),$$

(2.22)
$$\dot{B}(t)=F^{}(x(t))F^{}(x(t))B(t)+F^{}(x(t)).$$

Equation (2.22) is similar to equation (1.3) in . To prove Theorem 2.34 below we use the following lemma, which is an operator-theoretical version of the Gronwall inequality:

###### Lemma 2.5.

Let

(2.23)
$$\frac{dV}{dt}+A(t)V(t)=G(t),V(0)=V_0,$$

where $`A(t),`$ $`G(t),`$ $`V(t)L(H),`$ $`L(H)`$ is the set of linear bounded operators on $`H`$, and $`H`$ is a real Hilbert space. If there exists a scalar function $`\zeta (t)>0,\zeta L_{loc}^1(0,\mathrm{}),`$ such that

(2.24)
$$(A(t)h,h)\zeta (t)h^2hH,$$

then

(2.25)
$$V(t)e^{\underset{0}{\overset{t}{}}\zeta (p)𝑑p}\left[\underset{0}{\overset{t}{}}G(s)e^{\underset{0}{\overset{s}{}}\zeta (p)𝑑p}𝑑s+V(0)\right].$$

Proof. (see ) Take any $`hH.`$ Since $`H`$ is a real Hilbert space one has:

$$\frac{1}{2}\frac{d}{dt}V(t)h^2=(\frac{dV}{dt}h,V(t)h)$$

$$=(A(t)V(t)h,V(t)h)+(G(t)h,V(t)h)$$

(2.26)
$$\zeta (t)V(t)h^2+G(t)hV(t)h$$

Denote $`v(t):=V(t)h`$. Inequality (2.26) implies

(2.27)
$$v\dot{v}\zeta (t)v^2+G(t)hv.$$

Divide this inequality by the nonnegative $`v`$ and get a linear first-order differential inequality from which one gets (2.25). Lemma 2.25 is proved. ∎

###### Theorem 2.6.

Let $`H`$ be a real Hilbert space, $`F:HH`$. Assume that:

1. $`U(R,x_0):=\{xH,xx_0R\}`$, the operator $`F`$ is twice Fréchet differentiable, $`F^{}(x)`$ is boundedly invertible, and

(2.28)
$$F^{}(x)M_1,F^{\prime \prime }(x)M_2,[F^{}(x)]^1^2\frac{1}{c}xU(R,x_0),$$

where

(2.29)
$$R:=\frac{\gamma c}{2M_1M_2\sigma ^2},\gamma :=\frac{1F^{}(x_0)B_0I}{2}>0,\sigma :=\frac{M_1}{c}+B_0.$$

2. Equation (1.1) is solvable in $`U(R,x_0)`$ (not necessarily uniquely), and $`\widehat{x}`$ is a solution.

3. $`F(x_0)`$ satisfies the following condition

(2.30)
$$\left\{\frac{2M_1M_2}{c}\sigma ^3F(x_0)\right\}^{1/2}\gamma .$$

Then:

1. there exists a unique solution $`(x(t),B(t))`$, $`t[0,+\mathrm{})`$, to problem (2.21)-(2.22);

2. $`x(t)U(R,x_0)t[0,+\mathrm{})`$;

3. the following estimates hold

(2.31)
$$x(t)\widehat{x}\frac{\sigma F(x_0)}{\gamma }e^{\gamma t},$$

(2.32)
$$F(x(t))F(x_0)e^{\gamma t},$$

(2.33)
$$F^{}(x(t))B(t)I(M_2F(x_0)\sigma ^2t+F^{}(x_0)B_0I)e^{ct},\text{if}c=\gamma ,$$

(2.34)
$$F^{}(x(t))B(t)I\left(\frac{M_2F(x_0)\sigma ^2}{|c\gamma |}+F^{}(x_0)B_0I\right)e^{\mathrm{min}\{\gamma ,c\}t},\text{if}c\gamma .$$

Proof. Under the assumptions of theorem 2.6 there exists a unique solution $`(x(t),B(t))`$ to (2.21)-(2.22) on some interval $`[0,\tau ]`$, and, at least for sufficiently small $`t>0,`$ $`x(t)U(R,x_0)`$. Since $`xU(R,x_0)`$ and $`hH`$

(2.35)
$$(F^{}(x)F^{}(x)h,h)\frac{1}{[F^{}(x)]^1^2}h^2ch^2,$$

by (2.22) and Lemma 2.25 one gets

$$B(t)e^{ct}\left[_0^tF^{}(x(s))e^{cs}𝑑s+B(0)\right].$$

Thus by (2.28) and (2.29)

(2.36)
$$B(t)\frac{M_1}{c}\left(1e^{ct}\right)+B_0e^{ct}\frac{M_1}{c}+B_0:=\sigma .$$

Let us analyze the initial value problem for $`w(t):=F(x(t))`$. One has

$$\dot{w}(t)=F^{}(x(t))\dot{x}(t)=F^{}(x(t))B(t)w(t).$$

Therefore

(2.37)
$$\dot{w}(t)+w(t)+[F^{}(x(t))B(t)I]w(t)=0,w(0)=F(x_0).$$

Denote $`W(t):=F^{}(x(t))B(t)I`$. Then

$$\dot{W}(t)=F^{\prime \prime }(x(t))\dot{x}(t)B(t)+F^{}(x(t))\dot{B}(t)$$

$$=F^{\prime \prime }(x(t))B(t)F(x(t))B(t)+F^{}(x(t))[F^{}(x(t))F^{}(x(t))B(t)+F^{}(x(t))]$$

$$=F^{\prime \prime }(x(t))B(t)F(x(t))B(t)F^{}(x(t))F^{}(x(t))W(t).$$

Consider the problem

(2.38)
$$\dot{W}(t)+F^{}(x(t))F^{}(x(t))W(t)=F^{\prime \prime }(x(t))B(t)F(x(t))B(t),$$

(2.39)
$$W(0)=F^{}(x_0)B(0)I.$$

From (2.35), (2.38)-(2.39) and Lemma 2.25 one obtains the estimate

(2.40)
$$W(t)e^{ct}\left[_0^tF^{\prime \prime }(x(s))B(s)F(x(s))B(s)e^{cs}𝑑s+W(0)\right].$$

Assumptions 1 and 2 of Theorem 2.34 yield

$$F(x(t))F(x(t))F(x_0)+F(x_0)F(\widehat{x})2M_1R$$

for all values of $`t`$ such that $`x(t)U(R,x_0)`$.

Thus:

$$W(t)\frac{2M_1M_2R}{c}\left(\frac{M_1}{c}+B(0)\right)^2+W(0)=\frac{2M_1M_2R\sigma ^2}{c}+W(0)=\gamma +W(0).$$

Hence one gets from (2.29)

(2.41)
$$W(t)\frac{1W(0)}{2}+W(0)=\frac{1+W(0)}{2}.$$

Now one has the following differential inequality

$$\frac{1}{2}\frac{d}{dt}w(t)^2=w(t)^2(W(t)w(t),w(t))\frac{1W(0)}{2}w(t)^2=\gamma w(t)^2.$$

Therefore

(2.42)
$$w(t)w(0)e^{\gamma t}$$

for all values of $`t`$, such that $`x(t)U(R,x_0)`$. If $`0t_1t_2`$, one obtains

$$x(t_2)x(t_1)_{t_1}^{t_2}\dot{x}(s)𝑑s\left(\frac{M_1}{c}+B(0)\right)_{t_1}^{t_2}w(s)𝑑s$$

(2.43)
$$\frac{\sigma F(x_0)}{\gamma }\left(e^{\gamma t_1}e^{\gamma t_2}\right).$$

From (2.43) by conditions (2.29) and (2.30) one gets:

(2.44)
$$x(t_2)x(t_1)\frac{\gamma c}{2M_1M_2\sigma ^2}\frac{2M_1M_2\sigma ^3F(x_0)}{c\gamma ^2}\left(e^{\gamma t_1}e^{\gamma t_2}\right)R\left(e^{\gamma t_1}e^{\gamma t_2}\right).$$

Since $`B(t)`$ is bounded whenever it is defined, estimate (2.44) implies that there exists a unique solution $`(x(t),B(t))`$ to (2.21)-(2.22) on $`[0,+\mathrm{})`$ and $`t[0,+\mathrm{})`$ $`x(t)U(R,x_0)`$. Setting $`t_1=t`$ and $`t_2+\mathrm{}`$ in (2.43) one gets (2.31). Inequality (2.32) now follows from (2.42). Let us go back to (2.40). By (2.42) one has

(2.45)
$$W(t)e^{ct}\left[_0^tF^{\prime \prime }(x(s))B(s)^2F(x_0)e^{(c\gamma )s}𝑑s+W(0)\right].$$

Estimate (2.45) implies (2.33)-(2.34). This completes the proof. ∎

## 3. Ill-posed case. Continuously regularized modified Newton’s scheme

In many important applications the Fréchet derivative operator is not boundedly invertible, i.e. the problem is ill-posed. To overcome this difficulty we suggest a regularized version of algorithm (2.12):

(3.1)
$$\dot{x}(t)=[F^{}(x_0)+\epsilon (t)I]^1(F(x(t))+\epsilon (t)(x(t)x_0)),x(0)=x_0H,0<\epsilon (t),$$

where $`x_0`$ is chosen so that $`(F^{}(x_0)h,h)0`$ $`hH`$. If such a choice is not possible for the original equation $`F(x)=0`$, one may consider an auxiliary problem $`\varphi (x):=F^{}(x_0)F(x)=0`$. If $`F`$ is Fréchet differentiable, one has $`\varphi ^{}(x_0)=F^{}(x_0)F^{}(x_0)`$ and $`(\varphi ^{}(x_0))h,h)0`$ $`hH.`$ The last equation, in general, is not equivalent to (1.1). However every solution to (1.1) solves $`\varphi (x)=0`$. The convergence analysis of (3.1) is done in the following theorem.

###### Theorem 3.1.

Let $`H`$ be a real Hilbert space, $`F:HH`$, equation (1.1) be solvable (not necessarily uniquely), and $`\widehat{x}`$ be a solution to (1.1). Assume that:

1. A positive function $`\epsilon (t)C^1[0,+\mathrm{})`$ converges monotonically to zero as $`t+\mathrm{}`$, $`\frac{\dot{\epsilon }(t)}{\epsilon (t)}`$ is nondecreasing, and $`\epsilon (0)>|\dot{\epsilon }(0)|`$.

2. $`F`$ is Fréchet differentiable, its Fréchet derivative $`F^{}`$ is Lipschitz-continuous:

(3.2)
$$F^{}(x_1)F^{}(x_2)M_2x_1x_2\text{and}F^{}(x)=F^{}(x_0)G(x_0,x),$$

where

(3.3)
$$G(x_0,x)L(H),G(x_0,x)IC(G)x_0x,x_1,x_2,xU(\rho ,\widehat{x}),$$

(3.4)
$$U(\rho ,\widehat{x}):=\{xH:x\widehat{x}\rho \},C(G)>0,\rho :=\frac{\epsilon (0)|\dot{\epsilon }(0)|}{M_2+C(G)\epsilon (0)}.$$

3. $`F^{}(x_0)`$ is non-negative definite:

(3.5)
$$(F^{}(x_0)h,h)0hH,x_0\widehat{x}<\rho .$$

4. There exist $`vH`$ such that $`\widehat{x}x_0=F^{}(x_0)v`$,

(3.6)
$$\epsilon (0)|\dot{\epsilon }(0)|[M_2+C(G)\epsilon (0)]\epsilon (0)\sqrt{\frac{2v}{M_2}}.$$

Then a unique solution $`x=x(t)`$ to problem (3.1) exists for all $`t[0,+\mathrm{})`$ and

(3.7)
$$x(t)\widehat{x}\frac{\epsilon (0)|\dot{\epsilon }(0)|}{\epsilon (0)[M_2+C(G)\epsilon (0)]}\epsilon (t).$$

###### Remark 3.2.

Inequality (3.6) can always be satisfied if
$`\sqrt{2vM_2}<1`$. Indeed, inequality (3.6) is equivalent to

(3.8)
$$1\sqrt{2vM_2}\frac{|\dot{\epsilon }(0)|}{\epsilon (0)}+\epsilon (0)C(G)\sqrt{\frac{2v}{M_2}}.$$

Thus, if $`\sqrt{2vM_2}<1,`$ then inequality (3.8) holds if $`\frac{|\dot{\epsilon }(0)|}{\epsilon (0)}`$ and $`\epsilon (0)`$ are sufficiently small. For $`\epsilon (t)=ae^{bt}`$, $`a,b>0`$, inequality (3.6) holds if the following inequality is valid:

$$b+aC(G)\sqrt{\frac{2v}{M_2}}1\sqrt{2vM_2}.$$

The foregoing inequality holds if $`a`$ and $`b`$ are positive and sufficiently small and $`1>\sqrt{2vM_2}`$. Since a priori $`v`$ is not known, in the numerical applications of the scheme one has to try different functions $`\epsilon (t)`$ for (3.6) to be fulfilled.

###### Remark 3.3.

Consider nonlinear integral equation of the first kind:

(3.9)
$$F(x):=\psi (x)y=0,\psi (x)(t):=_0^1k(t,s)g(s,x(s))𝑑s,t[0,1],$$

where $`k(t,s)L^{\mathrm{}}((0,1)^2)`$ and $`g(s,u)`$ is twice continuously differentiable with respect to $`u`$ on $`0s,t1,\mathrm{}<u<+\mathrm{}`$. Suppose $`F:H^1[0,1]L^2(0,1)`$. Then

$$(F^{}(x)h)(t)=_0^1k(t,s)g_x(s,x(s))h(s)𝑑s.$$

Introduce the nonlinear operator $`\varphi (x):=F^{}(x_0)F(x)`$, $`\varphi :H^1[0,1]H^1[0,1]`$, and solve the equation $`\varphi (x)=0`$. Clearly $`\varphi ^{}(x_0)`$ is non-negative definite, i.e. condition 3 of Theorem 3.7 holds. Under the additional assumptions $`|g_x(s,x_0)|\kappa >0`$ for any $`s(0,1),`$ and $`g(s,u)C^3((0,1)\times (\mathrm{},+\mathrm{})),`$ one can take $`(G(x_0,x)h)(s):=\frac{g_x(s,x(s))}{g_x(s,x_0(s))}h(s)`$ in order to satisfy condition 2 of Theorem 3.7. Indeed,

$$(\varphi ^{}(x)h)(t)=(\varphi ^{}(x_0)G(x_0,x)h)(t),$$

and for any $`hH`$ the following estimates are used in :

$$(G(x_0,x)I)h_{L^2}=\left\{_0^1\left[\frac{_0^1g_{xx}(s,(x_0+\theta (xx_0))(s))𝑑\theta (x(s)x_0(s))h(s)}{g_x(s,x_0(s))}\right]^2𝑑s\right\}^{1/2}$$

$$\frac{g_{xx}_L^{\mathrm{}}}{\kappa }xx_0_L^{\mathrm{}}h_{L^2}.$$

Also $`\frac{d}{ds}(G(x_0,x)I)h_{L^2}`$

$$=\{_0^1[(\frac{_0^1g_{sxx}(s,(x_0+\theta (xx_0))(s))+g_{xxx}(s,(x_0+\theta (xx_0))(s))(x_0^{}+\theta (x^{}x_0^{}))(s)d\theta }{g_x(s,x_0(s))}$$

$$\frac{_0^1g_{xx}(s,(x_0+\theta (xx_0))(s))𝑑\theta (g_{sx}(s,x(s))+g_{xx}(s,x(s))x^{}(s))}{g_x^2(s,x_0(s))})(x(s)x_0(s))h(s)$$

$$+\frac{_0^1g_{xx}(s,(x_0+\theta (xx_0))(s))𝑑\theta }{g_x(s,x_0(s))}((x^{}(s)x_0^{}(s))h(s)+(x(s)x_0(s))h^{}(s))]^2ds\}^{1/2}$$

$$\frac{g_{sxx}_L^{\mathrm{}}}{\kappa }xx_0_L^{\mathrm{}}h_{L^2}+\frac{2g_{xxx}_L^{\mathrm{}}(x^{}_{L^2}+x_0^{}_L^{\mathrm{}})}{3\kappa }xx_0_L^{\mathrm{}}h_L^{\mathrm{}}$$

$$+\frac{g_{xx}_L^{\mathrm{}}g_{sx}_L^{\mathrm{}}}{\kappa ^2}xx_0_L^{\mathrm{}}h_{L^2}+\frac{g_{xx}_L^{\mathrm{}}^2x^{}_{L^2}}{\kappa ^2}xx_0_L^{\mathrm{}}h_L^{\mathrm{}}$$

$$\frac{g_{xx}_L^{\mathrm{}}}{\kappa }(x^{}x_0^{}_{L^2}h_L^{\mathrm{}}+xx_0_L^{\mathrm{}}h^{}_{L^2}).$$

The $`L^{\mathrm{}}(0,1)`$-norms of $`xx_0`$ and $`h`$ can be estimated by their $`H^1[0,1]`$-norms times some constants, due to Sobolev’s embedding theorems.

Thus if one assumes that equation (3.9) is solvable, $`\widehat{x}`$ is its solution, and in a neighborhood of $`\widehat{x}`$ there exists $`x_0`$ such that

$$\widehat{x}x_0=\varphi ^{}(x_0)v,\sqrt{2vM_2}<1,$$

then a unique solution $`x=x(t)`$ to the problem

$$\dot{x}(t)=[\varphi ^{}(x_0)+\epsilon (t)I]^1(\varphi (x(t))+\epsilon (t)(x(t)x_0)),x(0)=x_0H,0<\epsilon (t),$$

exists for all $`t[0,+\mathrm{})`$ and

$$x(t)\widehat{x}=O(\epsilon (t)),$$

provided that the above assumptions on $`k(t,s)`$ and $`g(s,u)`$ are satisfied and the choice of $`\epsilon (t)`$ is made according to (3.8) with $`\frac{\dot{\epsilon }(t)}{\epsilon (t)}`$ being nondecreasing.

Proof of Theorem 3.1 First, from (3.5) one concludes that the operator $`[F^{}(x_0)+\epsilon (t)I]^1`$ is bounded $`t0`$. Let us show that if $`x=x(t)`$ solves (3.1), then $`x(t)U(\rho ,\widehat{x})`$ with $`\rho `$ introduced in (3.4). Assume the converse: there exists $`T>0`$ such that

(3.10)
$$x(t)\widehat{x}<\rho t[0,T)\text{and}x(T)\widehat{x}=\rho .$$

For any $`t[0,T]`$ one has

$$\frac{1}{2}\frac{d}{dt}x(t)\widehat{x}^2=([F^{}(x_0)+\epsilon (t)I]^1[F^{}(\widehat{x})(x(t)\widehat{x})+R_2(x(t),\widehat{x})+\epsilon (t)(x(t)x_0)],x(t)\widehat{x}),$$

where $`R_2(x(t),\widehat{x})\frac{M_2}{2}x(t)\widehat{x}^2.`$ Thus one gets

$$\frac{1}{2}\frac{d}{dt}x(t)\widehat{x}^2x(t)\widehat{x}^2([F^{}(x_0)+\epsilon (t)I]^1(F^{}(\widehat{x})F^{}(x_0))(x(t)\widehat{x}),x(t)\widehat{x})$$

$$\epsilon (t)([F^{}(x_0)+\epsilon (t)I]^1(\widehat{x}x_0),x(t)\widehat{x})+\frac{M_2}{2\epsilon (t)}x(t)\widehat{x}^3.$$

Condition 2 of Theorem 3.7 and the estimate $`[F^{}(x_0)+\epsilon (t)I]^1F^{}(x_0)1`$ yield

$$\frac{1}{2}\frac{d}{dt}x(t)\widehat{x}^2x(t)\widehat{x}^2+G(x_0,\widehat{x})Ix(t)\widehat{x}^2+\epsilon (t)vx(t)\widehat{x}$$

$$+\frac{M_2}{2\epsilon (t)}x(t)\widehat{x}^3(1C(G)\rho )x(t)\widehat{x}^2+\epsilon (t)vx(t)\widehat{x}$$

(3.11)
$$+\frac{M_2}{2\epsilon (t)}x(t)\widehat{x}^3.$$

Introduce the notation $`Q(t):=x(t)\widehat{x}`$. Inequality (3.11) implies

(3.12)
$$\dot{Q}(t)(1C(G)\rho )Q(t)+\epsilon (t)v+\frac{M_2}{2\epsilon (t)}Q^2(t),Q(0)=x_0\widehat{x}.$$

Take $`f(t)=\frac{Q(t)}{\epsilon (t)}`$. By assumption 1 of Theorem 3.7 one obtains:

(3.13)
$$\dot{f}(t)\left(1C(G)\rho \frac{|\dot{\epsilon }(0)|}{\epsilon (0)}\right)f(t)+v+\frac{M_2}{2}f^2(t),f(0)=\frac{x_0\widehat{x}}{\epsilon (0)}.$$

From (3.4) and (3.13) one concludes that

(3.14)
$$\dot{f}(t)\frac{M_2(\epsilon (0)|\dot{\epsilon }(0)|)}{\epsilon (0)[M_2+C(G)\epsilon (0)]}f(t)+v+\frac{M_2}{2}f^2(t),f(0)=\frac{x_0\widehat{x}}{\epsilon (0)}.$$

Let

(3.15)
$$C_1:=\frac{M_2}{2},C_2:=\frac{M_2(\epsilon (0)|\dot{\epsilon }(0)|)}{\epsilon (0)[M_2+C(G)\epsilon (0)]},C_3:=v.$$

If $`g(t)`$ is a solution to the initial value problem

(3.16)
$$\dot{g}(t)=C_1g^2(t)C_2g(t)+C_3,$$

(3.17)
$$g(0)=f(0),$$

then inequality (3.14) yields

(3.18)
$$f(t)g(t),$$

whenever $`g(t)`$ and $`f(t)`$ are both defined. By (3.4), (3.5) and (3.15) one has

(3.19)
$$f(0)=\frac{x_0\widehat{x}}{\epsilon (0)}<\frac{\rho }{\epsilon (0)}=\frac{\epsilon (0)|\dot{\epsilon }(0)|}{\epsilon (0)[M_2+C(G)\epsilon (0)]}=\frac{C_2}{2C_1}.$$

By (3.6) the equation $`C_1g^2C_2g+C_3=0`$ has at least one real root. If there are two roots, the smaller root is a stable equilibrium for problem (3.16), which implies $`g(t)g(0)=f(0)<\frac{C_2}{2C_1}`$. Otherwise $`\stackrel{~}{g}:=\frac{C_2}{2C_1}`$ is a solution to (3.16), and $`g(t)<\frac{C_2}{2C_1}`$ since $`g(0)<\frac{C_2}{2C_1}`$. Therefore from (3.18) and (3.19) one derives:

$$f(t)g(t)<\frac{\rho }{\epsilon (0)}.$$

Hence inequality (3.14) and conditions (3.4) and (3.6) yield:

(3.20)
$$f(t)<\frac{\epsilon (0)|\dot{\epsilon }(0)|}{\epsilon (0)[M_2+C(G)\epsilon (0)]}=\frac{\rho }{\epsilon (0)}.$$

Thus

(3.21)
$$x(t)\widehat{x}<\frac{\rho }{\epsilon (0)}\epsilon (t)\rho t[0,T],$$

which contradicts (3.10). Therefore $`x(t)U(\widehat{x},\rho )`$ for any $`t`$, and by the standard argument one concludes that $`x(t)`$ is defined on $`[0,+\mathrm{})`$. Inequality (3.7) follows from (3.4) and (3.21). ∎

###### Corollary 3.4.

In this corollary it is shown that if the data are noisy, then the stopping time can be chosen so that the solution to the Cauchy problem with noisy data approximates a solution to (1.1) stably, i.e. with the error going to zero as the noise level goes to zero. Let the operator $`F`$ in (1.1) have the following form

(3.22)
$$F(x):=\psi (x)y.$$

Assume that $`\psi `$ is given exactly and in place of $`y`$ we know a $`\delta `$-approximation $`y_\delta `$, satisfying the inequality

(3.23)
$$yy_\delta \delta .$$

Then

$$\frac{1}{2}\frac{d}{dt}x(t)\widehat{x}^2(1C(G)\rho )x(t)\widehat{x}^2+\left(\epsilon (t)v+\frac{\delta }{\epsilon (t)}\right)x(t)\widehat{x}$$

(3.24)
$$+\frac{M_2}{2\epsilon (t)}x(t)\widehat{x}^3.$$

Take $`\tau _\delta `$ such that $`\epsilon (\tau _\delta )=\left(\frac{\delta }{v}\right)^{\frac{1}{2}}`$. For $`t=\tau _\delta `$ we get $`\frac{\delta }{\epsilon ^2(\tau _\delta )}=v`$ and therefore $`t[0,\tau _\delta ]`$

(3.25)
$$\dot{f}(t)\left(1C(G)\rho \frac{|\dot{\epsilon }(0)|}{\epsilon (0)}\right)f(t)+2v+\frac{M_2}{2}f^2(t),f(0)=\frac{x_0\widehat{x}}{\epsilon (0)}.$$

Thus one gets

(3.26)
$$x(\tau _\delta )\widehat{x}\frac{\rho }{\epsilon (0)v^{\frac{1}{2}}}\delta ^{\frac{1}{2}},$$

provided that conditions 1, 2, 3 of Theorem 3.7 and inequality

(3.27)
$$\epsilon (0)|\dot{\epsilon }(0)|2[M_2+C(G)\epsilon (0)]\epsilon (0)\sqrt{\frac{v}{M_2}}$$

hold.


format: text

text:
# From monomials to words to graphs

## 1 Introduction

An important structural difference between commutative and noncommutative free monoids is that in a finitely generated free commutative monoid all ideals are finitely generated (Dickson’s Lemma), while this is not the case for free monoids (for instance, the ideal generated by $`\{xy^nxn0\}`$). We will consider questions about whether some ideals of the free monoid are finitely generated. Those ideals will be described starting with an ideal in a free commutative monoid.

Let $`X`$ be a finite alphabet (of *letters*). Denote by $`[X]`$ the free commutative monoid on $`X`$ and by $`X^{}`$ the free monoid on $`X`$; we call the members of $`[X]`$ *monomials*, and the members of $`X^{}`$ *words*. When convenient, we assume $`X=\{x_1,x_2,\mathrm{},x_n\}`$, so a monomial can be written multiplicatively as $`x_1^{i_1}x_2^{i_2}\mathrm{}x_n^{i_n}`$. We denote by $`\pi `$ the canonical monoid epimorphism $`X^{}[X]`$.

The most natural relation between ideals of $`[X]`$ and $`X^{}`$ is given by the canonical map, so the first question is:

###### Problem 1

Given an ideal $`I`$ of $`[X]`$, is $`\pi ^1(I)`$ finitely-generated?

This first question, while quite natural, seems to be of limited interest, as ideals are not such big players in the structure theory of monoids.

The next questions were motivated by the study of noncommutative presentations of affine algebras and their Gröbner bases. In fact, the problems studied in this paper were motivated by a question posed by Bernd Sturmfels on the finite generation of monomial ideals. We postpone the discussion until Section 2, as the questions can be completely understood within the context of monoids.

For each ordering $``$ of the letters, we define a section $`\sigma _{}`$ of $`\pi `$ as follows. We say that a word is *sorted* if its letters occur in it in increasing order; if $`x_1x_2\mathrm{}x_n`$, such a word can be uniquely written as $`x_1^{i_1}x_2^{i_2}\mathrm{}x_n^{i_n}`$. Let $`\sigma _{}:[X]X^{}`$ be the function mapping each monomial $`m`$ to the unique sorted word in $`\pi ^1\left(m\right)`$. So, $`\pi \sigma _{}`$ is the identity map on $`[X]`$, and we define the *sorting map* $`S_{}`$ on $`X^{}`$ by $`S_{}=\sigma _{}\pi `$. The subscript $``$ will be omitted when implicitly understood.

We will mainly be concerned with ideals of form $`_{}(I)=\sigma _{}(I)`$, that is, the ideal generated by sorted words corresponding to a commutative ideal.

###### Problem 2

Given an ideal $`I`$ of $`[X]`$ and an ordering $``$ of $`X`$, is $`_{}(I)`$ finitely-generated?

While it is convenient to assume an ordering on the letters so that one can write monomials, that ordering is not part of $`[X]`$. So, we also consider

###### Problem 3

Given an ideal $`I`$ of $`[X]`$, is there an ordering $``$ of $`X`$ so that $`_{}(I)`$ is finitely-generated?

These problems are very loosely posed, as it is not specified how each ideal is given. We are interested in specification by finite data, so that it makes sense to look for an algorithmic answer to each of the problems. We consider three forms of specifying an ideal of $`[X]`$: by a finite generating set, as the inverse image of an ideal under a morphism from $`[X]`$, and as the initial ideal of a polynomial ideal given by its generators. The latter is explained in Section 2; our main results relate to the other two.

Most of this paper will be concerned with a finite set of monomials and the ideal it generates. Let us denote by $`M`$ the monoid ideal generated by a set $`M`$. So, $`M=M[X]`$ if $`M[X]`$, and $`M=X^{}MX^{}`$ if $`MX^{}`$. From now on, except where explicitly stated, in each of the problems above, given an ideal $`I`$ is reinterpreted as given a finite set $`M`$ of monomials, let $`I=M`$. That is the first of the three forms mentioned above.

It is not clear a priori that either problem is even decidable. Section 3 shows that standard methods of Automata Theory suffice to decide each instance of the problems, when the ideal is given by generators. However, this is unsatisfying both mathematically and computationally. From a purely mathematical viewpoint, the automata decision process is so far removed from the initial data that one learns very little about the underlying structure. From the computational viewpoint, what goes wrong is the exponential complexity of the algorithms thus obtained. We heed the fact that a monomial can be given as a vector of exponents, so the run-time of algorithms for the corresponding decision problems should be measured relative to the bit size of the exponents. With that in mind, we summarize the main results:

Problem 1 is solved completely in Section 7. The characterization we obtain yields a polynomial algorithm.

Problem 2 is the central one here, and also has a definite answer. To describe it we need more notation. We suppose an ordering of $`X`$ is given. For $`w`$ in $`[X]`$, say that a letter is *extremal* in $`w`$ if it is the smallest or the largest letter with a positive exponent there and say that a letter is *internal* to $`w`$ if it lies strictly between the extremal letters. Notice that an internal letter is not required to occur in $`w`$; for instance, using the ordering implied by the indices, the internal letters of $`x_2^3x_3x_5^2x_7`$ are $`x_3`$, $`x_4`$, $`x_5`$, and $`x_6`$. Also denote by $`w\backslash x`$ the monomial resulting of evaluating $`x`$ to $`1`$ in the monomial $`w`$. In particular, $`x^m\backslash x=1`$. A collection of monomials is an *antichain* if no one divides another; clearly, the (unique) minimal generating set of an ideal of $`[X]`$ is an antichain. Dickson’s Lemma, quoted earlier, is equivalent to the statement that every antichain of monomials is finite. For convenience, we will shorten $`(M)`$ to $`(M)`$ when $`M`$ is an arbitrary set of monomials.

###### Theorem 1

Let $`M`$ be an antichain in $`[X]`$. Then, $`(M)`$ is finitely generated if and only if, for every $`w`$ in $`M`$ and $`x`$ in $`X`$, there exists $`s`$ in $`M`$ such that $`x`$ is extremal in $`s`$ and $`s\backslash x`$ divides $`w`$.

A proof is found in Section 4. The above result immediately yields a polynomial-time decision algorithm for Problem 2. It also implies that Problem 3 is in NP.

When $`M`$ is square free, Problem 3 can be decided in polynomial time. And that is the end of good news. Problem 3 is shown in Section 6 to be NP-complete even when $`M`$ consists only of quadratic monomials. So, while the automata-theoretic algorithms where unacceptable for Problems 1 and 2 because of high exponents in the data, NP-completeness of Problem 3 is not related to the possibility of writing numbers succinctly.

In Section 8, using a slightly homological flavor, we turn to another way of presenting an ideal of $`[X]`$: fix a homomorphism from $`[X]`$ to another free commutative monoid, and an ideal $`J`$ in the target, and take the pre-image of that ideal. The homomorphism can be described by a matrix, and when $`J`$ is given by its minimal generators the ideal of $`[X]`$ is described as a finite union of integer polyhedra, each one of them an ideal. The theory developed for handling generators is enough to show that Problems 1 and 2 become coNP-complete with this data, while Problem 3 is shown to be NP-hard.

## 2 Connections with Gröbner bases

Problems 2 and 3 stem from a connection between the commutative and noncommutative Gröbner bases theories. Let $`K`$ denote a field, $`K[X]`$ the commutative polynomial ring on the finite set $`X`$, and $`KX`$ the free associative algebra on the same set (we adhere to the terminology of the first section, and talk about *letters* instead of variables). The linear extension of the monoid morphism $`\pi `$ is a ring morphism $`KXK[X]`$, still denoted by $`\pi `$; its kernel is generated by the commutation relations $`𝒞=\{xyyxx,yX\}`$. Also, given an ordering of $`X`$, the linear extension of the maps $`\sigma `$ and $`S`$ will be denoted by the same symbols.

Throughout this section, $`I`$ is an ideal of $`K[X]`$ and $`J=\pi ^1\left(I\right)`$. It is occasionally useful to lift a commutative ring presentation $`K[X]/I`$ to a noncommutative presentation $`KX/J`$ through $`\pi `$. This has been used in  for homological computations.

###### Proposition 2

Let $`AX`$ be a set of noncommutative polynomials. The following are equivalent:

* $`𝒞A`$ generates $`J`$.
* $`\pi (A)`$ generates $`I`$.
* For some ordering $``$ of $`X`$, $`𝒞S_{}(A)`$ generates $`J`$.
* For any ordering $``$ of $`X`$, $`𝒞S_{}(A)`$ generates $`J`$.

In particular, for any ordering $``$ of $`X`$, $`𝒞\sigma _{}(I)`$ generates $`J`$.

Proof: Suppose that $`𝒞A`$ generates $`J`$. Then, $`\pi (A)=\pi (𝒞A)=\pi 𝒞A=\pi (J)=I`$. Conversely, suppose that $`\pi (A)`$ generates $`I`$. Since $`\mathrm{ker}\pi 𝒞A\pi ^1\left(I\right)`$ and $`\pi 𝒞A=I`$, it follows that $`𝒞A=J`$.

The equivalence of conditions (iii) and (iv) to the previous ones follows from the observation that $`\pi S_{}(A)=\pi (A)`$. The last observation is immediate, as $`\pi \sigma _{}(I)=I`$. $`\mathrm{}`$

In many applications, one wants to describe a Gröbner basis for $`J`$, preferably related to a Gröbner basis for $`I`$. Let us recall quickly what those bases are (see  for an introduction to the subject). We will say *term* to mean either “word” or “monomial”, so we can treat commutative and noncommutative polynomials simultaneously.

A necessary ingredient for a Gröbner bases theory is to fix a *term order*: a total order on the terms, compatible with multiplication and with $`1`$ as minimum, and with no infinite descending chains. In this case, every polynomial has an *initial term*, the maximum term in its support, and to every ideal $`I`$ one associates its *initial ideal* $`\mathrm{𝐼𝑛}(I)`$, the set of all leading terms of polynomials in $`I`$. The initial ideal is an ideal of the monoid of terms. A *Gröbner basis* for $`I`$ is a subset $`B`$ of $`I`$ such that the initial terms of the members of $`B`$ generate $`\mathrm{𝐼𝑛}(I)`$.

Eisenbud, Peeva and Sturmfels  took the following approach to relate Gröbner bases for commutative polynomial ideals and their pre-images in the free algebra. Start with a term order $``$ on $`[X]`$, and define its *lexicographic extension*, still denoted here by $``$, to $`X^{}`$ by: $`uv`$ if $`\pi (u)\pi (v)`$ or $`\pi (u)=\pi (v)`$ and $`u`$ precedes $`v`$ lexicographically, according to the $``$ ordering on $`X`$.

###### Proposition 3

The initial ideal $`\mathrm{𝐼𝑛}(J)`$ is generated by

$$\{xyx,yX,xy\}\sigma (\mathrm{𝐼𝑛}(I)).$$

Proof: Since the noncommutative order extends the commutative one, if $`pK[X]`$, the initial term of $`\sigma (p)`$ is $`\sigma (m)`$, where $`m`$ is the initial term of $`p`$. Also, from the lexicography, if $`xy`$ are letters, $`xy`$ is the initial term of $`xyyx`$. The result now follows from Proposition 2. $`\mathrm{}`$

It follows from Dickson’s Theorem that every ideal of $`[X]`$ is finitely generated, hence every ideal of $`K[X]`$ has a finite Gröbner basis. In contrast, not every ideal of $`X^{}`$ is finitely generated, so it is generally interesting to detect whether a given ideal of $`KX`$ has a finite Gröbner basis. The preceding proposition implies that $`J`$ has a finite Gröbner basis with respect to $``$ if and only if $`(\mathrm{𝐼𝑛}(I))`$ is finitely generated. This gives rise to Problem 2.

A word in an ideal of $`X^{}`$ is a minimal generator of that ideal if and only if the words obtained by erasing either the first or the last letter are not in the ideal. Combining it with Proposition 2, we get the next result; it is Theorem 2.1 of , stripped of the ring theoretic context (which is handled by Proposition 3):

###### Theorem 4

If $`M`$ is a multiplicative antichain of monomials, then the minimal generating set of $`(M)`$ is

$$\begin{array}{c}\{\sigma (mu)mM,u[X]\text{ is generated by letters internal to }m\text{,}\hfill \\ \hfill \text{ and is such that, for each letter }x\text{ extremal to }m\text{}mux^1M\}.\end{array}$$

There seems to be no immediate characterization from the above for when $`J`$ has a finite Gröbner basis. A sufficient condition is provided in , and then the question is finessed: it is shown that, if $`K`$ is infinite, then, for any $`I`$ and $``$, $`J`$ will have a finite Gröbner basis after a generic change of variables,

This is of limited computational use if high degree polynomials are being handled, since the supports can grow explosively after generic changes. So, it is still of some interest to detect whether $`\pi ^1\left(I\right)`$ has a finite Gröbner basis when $`I`$ is still expressed in the given coordinates.

If $`I`$ is generated by a set $`M`$ of monomials (this is called a *monomial ideal* of $`K[X]`$), then $`\mathrm{𝐼𝑛}(I)`$ = $`M`$, irrespective of the term order $``$. It follows from Proposition 3 that:

###### Proposition 5

Let $`M[X]`$ and let $`I`$ be the monomial ideal it generates. Then $`J`$ has a finite Gröbner basis with respect to the lexicographic extension of a term order of $`[X]`$ if and only if, for the same ordering of $`X`$, $`(M)`$ is finitely generated.

This gives rise to Problem 3.

A similar looking question is, in the notation above, what conditions must $`M`$ satisfy, so that $`J`$ has a finite Gröbner basis with respect to the lexicographic extension of any term order of $`[X]`$? Proposition 5 translates it to a problem of monomials and words, and the answer is in section 5, Theorem 16.

As a final note, we point out that within this context another way of specifying an ideal of $`[X]`$ is relevant to Problems 2 and 3. Namely, suppose a term order is given on $`[X]`$; given a finite set $`M`$ of polynomials, consider the initial ideal $`I`$ of the polynomial ideal generated by $`M`$. That is the actual motivation for those problems, after all! The usual process of going from $`M`$ to $`I`$ is Buchberger’s algorithm and its variants. These are all of high complexity, so the question remains whether Problem 2 can be solved efficiently from this data.

## 3 Using automata

It is not clear from the outset that either of the problems mentioned in the introduction is decidable. This can be shown to be the case by means of the traditional machinery of automata theory (we follow the notation and terminology of ). We do it here, mostly for completeness and to underline some of the complexity issues. This section can be skipped, with no loss in understanding of the remaining text.

Suppose $`J`$ is an ideal of the free monoid $`X^{}`$; then its unique minimal generating set is $`T=J\backslash (XJJX)`$. Hence, if $`J`$ is a regular language, so is $`T`$. The problem of deciding whether $`T`$ is finite, given a regular expression for $`J`$, can be whimsically, although not very accurately, related to two well-known Unix utility programs: given a pattern for a grep search, decide whether the same search can be made by fgrep.

Problems 1 and 2 refer to ideals that are regular languages. Consider Problem 1. It is a well-known (although nonconstructive) consequence of Higman’s Theorem  that, for every subset $`A`$ of $`[X]`$, $`\pi ^1\left(A\right)`$ is regular. For $`\pi ^1M`$, one can construct a deterministic automaton directly: have $`n`$ parallel counters, one for each letter and counting up to its maximum degree in $`M`$. Each state of the automaton corresponds to an $`n`$-tuple of values for the counters, and processing a word $`x`$ leads to a state whose counters correspond to the exponent vector of $`\pi (x)`$. The final states are those that show that $`\pi (x)M`$, and they can be colluded into a single state that is never left after being reached.

For Problem 2, we can write a simple regular expression for $`\pi ^1M`$. If $`w=x_1^{i_1}x_2^{i_2}\mathrm{}x_{n1}^{i_{n1}}x_n^{i_n}[X]`$, then $`(w)=X^{}x_1^{i_1}x_2^{i_2}x_2^{}\mathrm{}x_{n1}^{i_{n1}}x_{n1}^{}x_n^{i_n}X^{}`$, and $`(M)=_{wM}(w)`$, so $`(M)`$ is a regular language. A deterministic automaton recognizing $`(M)`$ can also be constructed using parallel bounded counters, although the description would be more complicated than the previous one.

In both cases, there is only one final state, from which no transition leaves. This makes it easy to construct a deterministic automaton for the minimal generating set of each ideal, with direct products of three very similar automata. Then finiteness can be easily checked by a graph search. This approach shows now that Problem 2 is decidable.

From a complexity viewpoint, this does not work. Even though we have scrupulously avoided using nondeterministic automata, there remains a source of exponential complexity: in either case, the automaton described for each ideal has a number of states that is roughly the product $`N`$ of the maximum degrees of letters in $`M`$. This is too large; since a monomial can be represented as a vector of exponents, a reasonable encoding for $`M`$ would have only $`O(n\mathrm{log}N)`$ bits, where $`n=|X|`$. So, the automaton for the minimal generating set has exponentially many states, and the graph search is linear in the number of states.

The solutions we present in the following sections could perhaps be retrofitted into an automata-theoretical framework. Actually, thinking of automata helped in the discovery of those results: the Pumping Lemma (see \[12, Sec. 2.4\]) was a starting point.

There is a rich literature on ideals of the free monoid, from the viewpoint of language theory, with a twist. Instead of concentrating on the ideal, the focus is on its complement. The complement of an ideal is said to be *factorial languages*, and the minimal generators of the ideal appear as *forbidden subwords* in this context. There are many algorithms for problems involving factorial languages (see ), but they usually take a deterministic automaton like the large ones we described as input, so they are of no use here.

## 4 When $`(M)`$ is finitely generated

We assume a fixed ordering $``$ on the alphabet $`X`$. The *support* of a monomial $`w`$, denoted $`\underset{¯}{w}`$, is the set of letters with nonzero exponent in $`w`$. So, $`\mathrm{min}(\underset{¯}{w})`$ and $`\mathrm{max}(\underset{¯}{w})`$ are the *extremal* letters of $`w`$, while the letters $`x`$ such that $`\mathrm{min}(\underset{¯}{w})x\mathrm{max}(\underset{¯}{w})`$ are *internal* to $`w`$. We will use the notation $`uv`$ meaning *$`u`$ divides $`v`$*, both in $`[X]`$ and $`X^{}`$. So, for monomials $`u=x_1^{i_1}\mathrm{}x_n^{i_n}`$, $`v=x_1^{j_1}\mathrm{}x_n^{j_n}`$, $`uv`$ means that $`i_1j_1,\mathrm{},i_nj_n`$; for words $`u`$, $`v`$, $`uv`$ means that there exist words $`w`$, $`z`$ such that $`v=wuz`$.

Example 1:Take $`X=\{a,b,c,\mathrm{}\}`$ with the usual ordering. Then, for $`w=b^2df`$, $`\mathrm{min}(\underset{¯}{w})=b`$, $`\mathrm{max}(\underset{¯}{w})=f`$, and the internal letters are $`c`$, $`d`$, and $`e`$.

###### Lemma 6

If $`u`$ and $`v`$ are sorted words such that $`uv`$, then for any $`x`$ in $`X`$, either $`uS(vx)`$ or $`S(ux)S(vx)`$.

Proof: The first case occurs if $`x\mathrm{min}(\underset{¯}{u})`$ or $`x\mathrm{max}(\underset{¯}{u})`$, and the second case occurs if $`\mathrm{min}(\underset{¯}{u})x\mathrm{max}(\underset{¯}{u})`$. $`\mathrm{}`$

###### Lemma 7

Let $`T`$ be a set of sorted words. If, for every $`t`$ in $`T`$ and $`x`$ in $`X`$, $`S(tx)`$ has a factor in $`T`$, then there exists an ideal $`I`$ of $`[X]`$ such that $`T\sigma (I)`$ and $`T=(I)`$.

Proof: Let $`M=\pi (T)`$ and $`I=M`$; clearly $`T\sigma (I)`$, and we will show that $`T=(I)`$.

Since $`T(I)`$ is clear, it is enough to show that $`\sigma (I)T`$. Since any monomial in $`I`$ can be written as $`su`$, with $`sM`$, $`u[X]`$, we will show that $`\sigma (su)`$ has a factor in $`T`$ (so, it is in $`T`$) by induction in the total degree of $`u`$.

There is nothing to prove if the degree is zero. So, we can write $`u=vx`$, with $`v[X]`$, $`xX`$. By the induction hypothesis, $`t\sigma (sv)`$ for some $`tT`$. By hypothesis, $`S(tx)`$ has a factor $`yT`$. Noticing that $`S(\sigma (sv)x)=\sigma (svx)=\sigma (su)`$, Lemma 6 implies that either $`t\sigma (su)`$, or $`S(tx)\sigma (su)`$, in which case, $`y\sigma (su)`$. In either case, the result follows. $`\mathrm{}`$

From this, it easily follows:

###### Corollary 8

Let $`M`$ be a set of monomials. A sufficient condition for a set $`T`$ of words to be such that $`T=(M)`$ is that $`\sigma (M)T\sigma M`$ and for every $`t`$ in $`T`$ and $`x`$ in $`X`$, $`S(tx)`$ has a factor in $`T`$.

For the proof, we restate Theorem 1 with some additional precision. First, we recall and introduce some notation.

If $`w`$ is a monomial and $`xX`$, $`w\backslash x`$ denotes the monomial obtained from $`w`$ by erasing the occurrences of $`x`$. We denote by $`\iota (w)`$ the set of internal letters of $`w`$, and by $`_xw`$ the degree of $`x`$ in $`w`$. Given a set $`M`$ of monomials, let $`r_x(M)`$ denote the maximum degree $`x`$ occurs with as an extremal letter in $`M`$. To avoid misunderstandings, $`[\iota (w)]`$ is simply the submonoid of $`[X]`$ generated by $`\iota (w)`$.

Example 2:Continuing the earlier example, $`w\backslash b=df`$ and $`w\backslash f=b^2d`$. If $`M=\{c^3,a^2c^5f^2,cf^3g,a^2b^2c^2\}`$, then $`r_c(M)=3`$ and $`r_f(M)=2`$.

###### Theorem 9

Let $`M`$ be an antichain in $`[X]`$. The following are equivalent:

* $`(M)`$ is finitely generated.
* For every $`w`$ in $`M`$ and $`x`$ in $`\iota (w)`$, there exists $`s`$ in $`M`$ such that $`x`$ is extremal in $`s`$, and $`s\backslash x`$ divides $`w`$.
* $`(M)`$ is generated by $`\sigma \left({\displaystyle \underset{wM}{}}\{uw[\iota (w)]x\iota (w),_xu<r_x(M)\}\right).`$

Proof: Let $`T`$ be the minimal generating set of $`(M)`$, and suppose it is finite. We shall prove condition (ii). Note that $`\sigma (M)T`$. Indeed, if $`wM,\sigma (w)`$ has a factor in $`T`$, and this has the form $`\sigma (su)`$, for some $`sM`$ and $`u[X]`$. So, $`\sigma (su)\sigma (w)`$, and this clearly implies $`suw`$. So, $`sw`$ and, since $`M`$ is an antichain and $`sM`$, it follows that $`s=w,u=1`$, hence $`\sigma (w)T`$.

Let $`wM`$ and let $`x`$ be an internal letter to $`w`$. We can uniquely write $`\sigma (w)=ux^rv`$, with $`u,v`$ sorted, $`\mathrm{max}(\underset{¯}{u})x\mathrm{min}(\underset{¯}{v})`$. Hence, all words $`ux^nv`$, with $`nr`$, are in $`(M)`$, so each has a factor in $`T`$; it follows that some $`tT`$ is a factor of infinitely many such words. If $`x`$ is not in the support of $`t`$, it must happen that $`t`$ is a factor of $`u`$ or of $`v`$, hence a proper factor of $`\sigma (w)`$, but $`\sigma (w)T`$, so this cannot occur. Therefore, $`x`$ is in the support of $`t`$, and necessarily is extremal. Without loss of generality, let us assume that $`x=\mathrm{min}(\underset{¯}{t})`$; so $`t=x^kz`$ with $`x\mathrm{min}(\underset{¯}{z})`$, and note that $`z`$ is a factor of $`\sigma (w)`$, so $`\pi (z)w`$. Now, $`t=\sigma (sy)`$ for some $`sM`$ and $`y[X]`$. If $`x\underset{¯}{s}`$, we would have $`s\pi (z)`$, hence $`sw`$, a contradiction. Hence $`x=\mathrm{min}(\underset{¯}{s})`$, so $`s\backslash x`$ is a factor of $`w`$.

Now, suppose that condition (ii) holds and let us prove (iii). Call $`T`$ the generating set in that statement. Clearly $`\sigma (M)T\sigma M`$. Now, let $`tT`$ and $`xX`$, and let us find a factor of $`S(tx)`$ in $`T`$ as required by Corollary 8. Write $`t=\sigma (wz)`$, with $`wM`$ and $`z[\iota (w)]`$.

If $`x\iota (w)=\iota (\pi (t))`$, it follows immediately that $`tS(tx)`$. There remains the case where $`x\iota (w)`$ and $`S(tx)T`$ (since the case $`S(tx)T`$ is trivial).

Now, $`\sigma (wz)T`$, but $`\sigma (wzx)T`$, hence $`_xwz=r_x(M)1`$. We can write uniquely $`wz=ux^{r_x(M)1}v`$, with $`\mathrm{max}(\underset{¯}{u})x\mathrm{min}(\underset{¯}{v})`$. By hypothesis, there exists $`sM`$, with $`x`$ extremal in $`s`$ (without loss, $`x=\mathrm{max}(\underset{¯}{s})`$) such that $`s\backslash x`$ divides $`w`$. Since $`_xsr_x(M)`$, $`swzx`$, and by maximality of $`x`$ in $`\underset{¯}{s}`$, $`sux^{r_x(M)}`$. Let $`p`$ result from raising the degree of each internal letter of $`s`$ to its exponent in $`u`$. Then, $`ps[\iota (s)]`$ and its internal letters have small degree, so $`\sigma (p)T`$, and it is the factor of $`S(tx)`$ we sought after.

Clearly (iii) implies (i), and the theorem is proved. $`\mathrm{}`$

Example 3:Consider the set $`M=\{ab^2c,a^3b\}`$. The ordering $`abc`$ does not satisfy the conditions above, since $`b`$ is internal to $`ab^2c`$, and extremal only in $`a^3b`$, but $`a^3b\backslash b=a^3`$ does not divide $`ab^2c`$; indeed, $`\sigma M`$ comprises all words $`a^ib^{j+2}c^k`$ and $`a^{i+3}b^j`$ with $`i,j,k0`$, and the set $`\{ab^{j+2}cj0\}`$ cannot be generated as multiples of finitely many of those. Similarly, $`acb`$ fails, since $`c`$ is internal to $`a^3b`$, and extremal in none. However, $`bac`$ is good: $`a`$ is internal to $`b^2ac`$ only, and $`ba^3\backslash a=b`$ divides $`b^2ac`$. In this case, $`(M)`$ is generated by $`\{b^2ac,b^2a^2c,ba^3\}`$.

Condition (iii) above is a fairly precise description of the minimal generating set of $`(M)`$. One gets a quick and dirty estimate for its size by forgetting most parameters:

###### Corollary 10

Let $`M`$ be a finite set of monomials in $`[X]`$. Then, if $`(M)`$ is finitely generated, it can be generated by a set of at most

$$|M^{}|\underset{x\iota (M)}{}r_x(M)+|M||M^{}|$$

elements, where $`M^{}=\{wM\iota (w)\mathrm{}\}`$ and $`\iota (M)=_{wM}\iota (w)`$.

Even though it is a rough estimate, the result above is best possible. To see this, suppose $`X=\{x_1,x_2,\mathrm{},x_n\}`$, ordered according to the indices. Choose positive integers $`m,r_2,r_3,\mathrm{},r_{n1}`$, and let $`M=\{x_1^{i+1}x_n^{mi}0i<m\}\{x_i^{r_i}i=2,\mathrm{},n1\}`$. Then, the minimal generating set for $`(M)`$ is precisely that described in Theorem 9 (iii) and has size $`mr_i+n2`$.

If we are given $`M`$ as a collection of integer vectors, divisibility is just componentwise comparison, so it can be tested rapidly. A naive check of the condition on Theorem 1 would need at most $`|M|^2|X|`$ such comparisons, so Problem 2 can be solved by a polynomial-time algorithm.

We end this section with some constructions that will be useful later and some unexpected consequences of the theorem.

Given a collection $`M`$ of monomials and an integer $`k`$, $`M_k`$ will denote the subset of $`M`$ consisting of monomials whose support has size at most $`k`$.

###### Proposition 11

If an antichain $`M`$ of monomials is such that $`(M)`$ is finitely generated, so is $`(M_k)`$ for each integer $`k`$.

Proof: Let us show that $`M_k`$ satisfies condition (ii) of Theorem 9. If $`wM_k`$, and $`x`$ is internal to $`w`$, we know, since $`(M)`$ is finitely generated, that for some monomial $`uM`$, $`x`$ is extremal in $`u`$ and $`u\backslash x`$ is a factor of $`w`$. Since $`x`$ is internal to $`w`$ and extremal in $`u`$, the support of $`u\backslash x`$ is a proper subset of the support of $`w`$, so $`|\underset{¯}{u}|k`$; that is, $`uM_k`$. $`\mathrm{}`$

###### Proposition 12

Let $`w\widehat{w}`$ be a bijection between sets $`M`$ and $`\widehat{M}`$ of monomials, such that:

* For every $`w`$ in $`M`$, $`w`$ and $`\widehat{w}`$ have the same extremal letters.
* For every $`u,v`$ in $`M`$ and $`x`$ in $`X`$, if $`_xu_xv`$, then $`_x\widehat{u}_x\widehat{v}`$.

If $`\widehat{M}`$ is an antichain, and $`(M)`$ is finitely generated, then so is $`(\widehat{M})`$.

Proof: First notice that, from condition (ii), $`uv`$ implies $`\widehat{u}\widehat{v}`$, so $`M`$ is an antichain. Thus, it must satisfy Theorem 9 (ii). Let $`\widehat{w}\widehat{M}`$, and $`xX`$ be internal to $`\widehat{w}`$. From condition (i), $`x`$ is internal to $`w`$, so there exists $`uM`$ such that $`x`$ is extremal in $`u`$ and $`u\backslash xw`$. Again from (i), $`x`$ is extremal in $`\widehat{u}`$, and from condition (ii), $`\widehat{u}\backslash x\widehat{w}`$. $`\mathrm{}`$

## 5 Cool orders

Given an antichain $`M`$ of monomials in $`[X]`$, we say that an ordering of $`X`$ is *cool* for $`M`$ if, for every $`w`$ in $`M`$ and letter $`x`$ internal to $`w`$, there exists $`s`$ in $`M`$ such that $`x`$ is extremal in $`s`$ and $`s\backslash x`$ divides $`w`$.

As we will see in the next section, no good algorithm is forthcoming to decide whether a cool ordering exists. Before giving substance to this, we try to get a better understanding of such orderings. We begin with an immediate consequence of Propositions 11 and 12:

###### Proposition 13

Let $`M`$ be an antichain of monomials. Then, any cool ordering for $`M`$ is also a cool ordering for:

1. $`M_k`$, for any integer $`k`$.
2. Any $`\widehat{M}`$, obtained from $`M`$ by changing each $`w`$ to $`\widehat{w}`$, so that:

1. $`w`$ and $`\widehat{w}`$ have the same support, and
    2. For every $`u,v`$ in $`M`$ and $`x`$ in $`X`$, if $`_xu_xv`$, then $`_x\widehat{u}_x\widehat{v}`$.

This gives some necessary conditions for existence of cool orderings. We also get a kind of equivalence between sets of monomials:

###### Proposition 14

Let $`w\widehat{w}`$ be a bijection between set $`M`$ and $`\widehat{M}`$ of monomials, such that:

* For every $`w`$ in $`M`$, $`\underset{¯}{w}=\underset{¯}{\overset{^}{w}}`$, and
* For every $`u,v`$ in $`M`$ and $`x`$ in $`X`$, $`_xu<_xv`$ if and only if $`_x\widehat{u}<_x\widehat{v}`$.

Then, an ordering of $`X`$ is cool for $`M`$ if and only if it is so for $`\widehat{M}`$.

Proof: It is easily checked that $`uv`$ if and only if $`\widehat{u}\widehat{v}`$. So, the bijection maps minimal monomials to minimal monomials, antichains to antichains, and so on. It is just a matter of applying part 2 of Proposition 13 in both directions. $`\mathrm{}`$

From now to the end of the article, an ordering of the letters will not be given at the outset, and the following concept will be useful for the search of cool orderings. A monomial $`w`$ is said to *help* a monomial $`m`$ *with* the letter $`x`$ if $`x\underset{¯}{w}`$, $`w\backslash xm`$ and $`\underset{¯}{w\backslash x}\underset{¯}{m\backslash x}`$.

If $``$ is a cool ordering for a set $`M`$ and, for some $`YX`$, every monomial in $`M`$ has support included in $`Y`$ or disjoint from $`Y`$, then $``$ is a cool ordering for those monomials with support included in $`Y`$. This can be extended to the following easily verified fact:

###### Proposition 15

A cool ordering for $`M`$ is also cool for any $`NM`$ such that all members on $`M`$ that help some member of $`N`$ (with some letter) are in $`N`$.

Next section will consider the problem of finding a cool ordering, given $`M`$. We close the section considering a question that is a sort of opposite of that: how must $`M`$ look like if *every* ordering of $`X`$ is cool? The answer is surprisingly simple.

###### Theorem 16

Let $`M`$ be an antichain of monomials over $`X`$. Then, every ordering of $`X`$ is cool for $`M`$ if and only if, for every $`m`$ in $`M`$ and $`x`$ in $`X`$ such that $`|\underset{¯}{m\backslash x}|2`$, there exists a $`u`$ in $`M_2`$ such that $`u\backslash xm`$.

Proof: Suppose that every ordering of $`X`$ is cool for $`M`$. Let $`m`$ and $`x`$ be given as in the statement. Then, there exists an ordering $``$ on $`X`$ such that $`x`$ is internal to $`m`$. Since $``$ is cool, there is a $`u`$ in $`M`$ that helps $`m`$ with $`x`$. Choose $`u`$ with minimal support, and let us show that $`\underset{¯}{u}`$ has size at most $`2`$. If $`|\underset{¯}{u}|>2`$, there is another ordering of $`X`$ that makes $`x`$ internal to $`u`$. Again by Theorem 9, there exists a $`v`$ in $`M`$ that helps $`u`$ with $`x`$; clearly, $`v`$ also helps $`m`$ with $`x`$. Since $`x\underset{¯}{u}\underset{¯}{v}`$, it follows that $`\underset{¯}{v}\underset{¯}{u}`$, so we have contradicted the minimality of $`\underset{¯}{u}`$.

Conversely, suppose the divisibility condition holds, and consider an arbitrary ordering of $`X`$. Pick an $`mM`$ and let $`x\iota (m)`$. Choose $`u`$ in $`M_2`$ such that $`u\backslash xm`$; clearly $`x`$ is extremal in $`u`$. It follows that the ordering is cool. $`\mathrm{}`$

## 6 Finding cool orders is hard

Monoids generated by square-free monomials appear frequently in algebraic combinatorics (related to Stanley-Reisner rings of simplicial complexes), and have been studied in the current context by Peeva and Sturmfels, together with Eisenbud  and Reiner . Propositions 18 and 20 tell the same as \[5, Prop. 3.2\] and \[15, Lemma 3.1\], although the different jargon may obscure this. After that we move to another direction.

###### Proposition 17

Suppose that $`M`$ is an antichain and the degree of the letter $`x`$ in $`wM`$ is the largest degree it has in all monomials in $`M`$. Then, in any cool ordering for $`M`$, $`x`$ cannot be internal to $`w`$.

Proof: If there is a cool ordering for $`M`$ where $`x`$ is internal to $`w`$, there exists a $`tM`$ such that $`t\backslash xw`$. But since $`_xw_xt`$, it follows that $`tw`$, a contradiction, as $`M`$ is an antichain. $`\mathrm{}`$

The following is an immediate corollary:

###### Proposition 18

If $`M`$ consists only of square-free monomials and affords a cool ordering, then its monomials have total degree at most 2.

Degree 1 monomials are trivially handled here, so the square-free sets $`M`$ of interest consist only of quadratic monomials. Polynomial ideals whose initial ideals are generated by quadratic monomials (mostly square-free) were extensively studied in .

We leave now the square-free condition, and consider the case when $`M`$ consists exclusively of quadratic monomials, that is, we allow monomials of form $`x^2`$. This seemingly trivial extension has deep consequences:

###### Proposition 19

The problem of deciding, given a set of quadratic monomials $`M`$, whether there exists a cool ordering for $`M`$ is:

* Solvable in polynomial time, if $`M`$ is square-free.
* NP-complete, in general.

Proof: Part (a) follows from Proposition 20 and part (b) from Proposition 21. $`\mathrm{}`$

With quadratic monomials, irrespective of the order of the letters, each letter is extremal in each monomial it occurs, so, an ordering $``$ on $`X`$ is cool for $`M`$ if and only if whenever $`xyz`$ and $`xz`$ is in $`M`$, then at least one of $`y^2,xy,yz`$ is in $`M`$.

At this point, it becomes convenient to encode the data and the problem by means of graphs, and it turns out to be convenient to use the complement of what comes naturally. The graph $`G(M)`$ will have the letters as vertices, $`xy`$ is an edge if $`xy`$ is not in $`M`$. Let $`T_M`$ denote the set of letters whose square is *not* in $`M`$.

An orientation of a graph is said to be *transitive* at a vertex $`y`$ if, whenever oriented edges $`xy`$ and $`yz`$ exist, then the edge $`xz`$ must also exist. A graph is a *comparability graph* if it admits an orientation that is transitive at all its vertices; such an orientation is always acyclic. Comparability graphs have been widely studied, and have efficient recognition algorithms  (or ), , .

###### Proposition 20

A set $`M`$ of quadratic monomials admits a cool order if and only if $`G(M)`$ admits an acyclic orientation that is transitive at all vertices of $`T_M`$. In particular, if $`M`$ is square-free, it admits a cool order if and only if $`G(M)`$ is a comparability graph.

Proof: Suppose $`M`$ has a cool ordering. Direct all edges of $`G(M)`$ from the smallest to the largest vertex. This orientation is trivially acyclic. If $`yT_M`$, and edges $`xy`$ and $`yz`$ exist, then the monomials $`y^2`$, $`xy`$ and $`yz`$ are not in $`M`$. By coolness, $`xzM`$, so the edge $`xz`$ is in $`G(M)`$, and is correctly oriented.

Conversely, suppose that $`G(M)`$ admits an acyclic orientation that is transitive at all vertices of $`T_M`$. With a “topological sort” order its vertices so that all directed edges point from the smaller to the bigger end. One readily verifies that this ordering is cool for $`M`$.

When $`M`$ is square-free, $`T_M`$ comprises all vertices, so an acyclic orientation that is transitive at all vertices of $`T_M`$ says that $`G(M)`$ is a comparability graph. $`\mathrm{}`$

We refer the reader to the already classic text  as a general reference for NP-completeness, good algorithms and satisfiability. Since good algorithms for recognition of comparability graphs are known, one would expect that testing the condition of Proposition 20 would also be feasible.

###### Proposition 21

The problem:

> *given a graph $`G`$ and a set $`TVG`$, is there an acyclic orientation of $`G`$ that is transitive at all vertices in $`T`$?*

is NP-complete.

Proof: Let us shorten “orientation transitive at $`T`$” to *$`T`$-orientation*. The proof will be by a reduction from not-all-equal-3sat . The basic gadget is the graph in Figure 1, where the vertices in $`T`$ are black (and labeled $`a`$, $`\overline{a}`$, $`c`$).

Fact 1: There is only one $`T`$-orientation of this graph where the edge $`a\overline{a}`$ is oriented $`a\overline{a}`$. In that orientation, $`a`$ is a source, $`\overline{a}`$ is a sink, and the bottom edge is directed from $`r`$ to $`l`$.

To see this, notice that since the edge $`s\overline{a}`$ does not exist, $`sa`$ must be oriented as $`as`$, because of transitivity at $`a`$. By a similar argument we check that all edges with an end in $`T`$ can have only one orientation. Finally, since the orientations $`rc`$ and $`cl`$ are forced, $`rl`$ is forced by transitivity at $`c`$.

Now we construct the main gadget by gluing three copies of the top hat, identifying cyclically each $`t`$ with the next $`s`$ and each $`r`$ with the next $`l`$. The result is in Figure 2, where only important vertices are labeled.

Fact 2: *Consider an orientation of the edges $`a_1\overline{a}_1`$, $`a_2\overline{a}_2`$ and $`a_3\overline{a}_3`$. It extends to an acyclic $`T`$-orientation of the gadget if and only if they are not all directed the same way along the external cycle.*

Indeed, by looking at the top hats we see that any orientation of these edges extends uniquely to a $`T`$-orientation of the gadget. If they are all oriented the same way, the inner triangle becomes a directed cycle. Conversely, if they are not all the same way (by symmetry, there is only one case to check), the orientation of the gadget is acyclic.

Now we proceed to the reduction. A typical instance of not-all-equal-3sat consists of a set $`X`$ of variables and a set $`C`$ of clauses over $`X`$, where each clause has three literals, each of form $`x`$ or $`\overline{x}`$, for some $`xX`$. The question is whether there exists a truth assignment to $`X`$, so that for each clause one literal gets value *true* and one gets value *false*.

For each clause, take a copy of the gadget and replace the labels $`a_1`$, $`a_2`$ and $`a_3`$ by the literals, and $`\overline{a}_1`$, $`\overline{a}_2`$ and $`\overline{a}_3`$ by the complements of the literals in the clause. Add to that a vertex $`v_x`$ for each variable $`x`$, and join it to all vertices labeled $`x`$. Call the resulting graph $`G`$, and let $`T`$ be formed by all $`v_x`$ together with the union of all black vertices from the gadgets.

We will show a 1-1 correspondence between truth assignments for $`V`$ that solve $`C`$ and acyclic $`T`$-orientations of $`G`$. Start with a truth assignment. For each edge labeled $`x\overline{x}`$, orient it from $`x`$ if $`x`$ is assigned *true* and towards $`x`$ otherwise. Consider a clause and its respective gadget. The three literals in the clause are not all *true* and not all *false*, so the three special edges are not all directed the same way. It follows from Fact 2 that one can orient (uniquely) all gadgets extending these orientations. In this orientation, all vertices labeled with the same literal are sources in their gadgets if that literal is *true*, and sinks otherwise. This $`T`$-orientation can now be extended to the whole $`G`$, directing all edges incident to $`v_x`$ towards it if $`x`$ is *true* and the opposite otherwise.

Conversely, suppose a $`T`$-orientation of $`G`$ is given. Since all neighbors of $`v_x`$ are pairwise non-adjacent, $`v_x`$ is either a source or a sink. Assign $`x`$ *true* if $`v_x`$ is a sink, *false* otherwise. The fact that each gadget is acyclically $`T`$-oriented shows that in the corresponding clause the not-all-equal condition is satisfied. $`\mathrm{}`$

Since simple powers have originated the problem in Proposition 19, we tried to look at another extension of its first part, namely, allow only monomials with support size exactly 2. This was short lived, though:

###### Proposition 22

The problem:

> *given a collection $`M`$ of monomials, each with support of size 2, does there exist a cool ordering for $`M`$?*

is NP-complete.

Proof: We reduce the quadratic case to this. Suppose that $`M`$ is a collection of quadratic monomials, and let $`M^{}=\{xyxyM\}\{x^2yx^2M\text{ and }xyM\}`$. It is easy to check that $`M`$ and $`M^{}`$ have precisely the same cool orderings. $`\mathrm{}`$

There is a lot of leeway in the reduction in the proof of Proposition 21. For instance, the $`v_i`$ could be eliminated, and similarly labeled vertices could be merged. One could add irrelevant vertices of both types and show that existence of acyclic $`T`$-orientations is NP-complete even if $`|T|=\frac{1}{2}|VG|`$ (any constant between $`0`$ and $`1`$ would do). On the extremes, the problem can be solved:

When $`T=VG`$, that is recognition of comparability graphs. When $`T`$ induces a bipartite graph, any acyclic orientation in which one side of $`T`$ consists only of sources and the other (if it exists) only of sinks is a $`T`$-orientation. This takes care of $`|T|2`$; actually, for any fixed $`k`$, if $`|T|k`$, one can restrict the search for a $`T`$-orientation to a polynomial number of acyclic orientations that can be systematically enumerated.

## 7 Lifting the ideal

Here we present the solution to Problem 1.

###### Theorem 23

Given an antichain of monomials $`M[X]`$, the following are equivalent:

* $`\pi ^1M`$ is a finitely generated ideal of $`X^{}`$.
* For every $`m`$ in $`M`$ and any letters $`xzy`$ such that $`xym`$, there exists a monomial $`w`$ in $`M`$ such that $`w\backslash z`$ divides either $`mx^1`$ or $`my^1`$. (Note that $`x=y`$ is included.)
* For every $`m`$ in $`M`$ and any letter $`z`$ such that no power of it is in $`M`$, if $`m\backslash z`$ has degree $`2`$, there exists a monomial $`z^rt`$ in $`M_2`$,such that $`t\underset{¯}{m}`$.
* $`\pi ^1M`$ is generated by the inverse images of the monomials $`mM`$ such that, for every letter $`x`$, $`_xm\mathrm{max}_{uM_2}_xu`$.

Proof: (i) implies (ii): Given $`m`$, $`x`$, $`y`$, and $`z`$, choose $`u=xz^rvy\pi ^1\left(m\right)`$, where $`r0`$. Now, for every $`sr`$, $`xz^svy\pi ^1M`$, and since $`\pi ^1M`$ is finitely generated, some minimal generator $`g`$ divides infinitely many of these. This is only possible if $`g`$ divides some $`xz^s`$ or some $`z^svy`$. So, $`\pi (g)\backslash z`$ divides either $`my^1`$ or $`mx^1`$. The result follows by taking any $`w`$ in $`M`$ that divides $`\pi (g)`$.

(ii) implies (iii): Given $`m`$ and $`z`$, choose letters $`x`$ and $`y`$ such that $`xym\backslash z`$. Let $`w`$ be given by condition (ii), with minimal support. Since $`M`$ is an antichain, $`z\underset{¯}{w}`$. Suppose, by contradiction, that $`w\backslash z`$ has degree $`2`$. We apply condition (ii) to $`w`$, obtaining a $`w^{}`$; that new monomial could also play the role of $`w`$ with respect to $`m`$, so, by minimality of $`w`$, it cannot exist. Since no power of $`z`$ is in $`M`$, $`w=z^rt`$ for some letter $`tz`$. As $`w\backslash z`$ divides either $`mx^1`$ or $`my^1`$, it follows that $`t\underset{¯}{m}`$.

(iii) implies (iv): Let $`W`$ be the set claimed to generate $`\pi ^1M`$. If this is false, then $`W\pi ^1M`$, since $`W\pi ^1M`$. So, there must exist a $`w\pi ^1M`$, of minimum length, with no factor in $`W`$. So, for some letter $`z`$, $`_z\pi (w)>r=max_{uM_2}_zu`$.

Suppose that $`z^rM`$. Clearly $`w`$ has a proper factor $`u`$ such that $`z^r\pi (u)`$, so $`u\pi ^1M`$. By minimality of $`w`$, $`u`$ has a factor in $`W`$; then, so does $`w`$, a contradiction. So, $`z^rM`$, and by the choice of $`r`$ and as $`M`$ is an antichain, no power of $`z`$ lies in $`M`$. Now, let $`mM`$ be such that $`m\pi (w)`$. By (iii), there exists a $`z^stM`$ such that $`t\underset{¯}{m}`$. Since $`sr`$, $`w`$ has a proper factor $`u`$ such that $`z^st\pi (u)`$. We get a contradiction again, that finishes the proof.

(iv) implies (i): We deserve the rest. $`\mathrm{}`$

We briefly relate this result to the preceding ones. It is easy to check from the definitions that if $`\pi ^1M`$ is finitely generated, then every ordering of $`X`$ is cool for $`M`$. This can also be seen from the fact that if $`M`$ satisfies the condition in Theorem 23 (iii), then it also satisfies the condition of Theorem 16. The converse is not true; the simplest example is $`M=\{a^2,bc\}`$ — here, every ordering is cool, but $`\pi ^1M`$ is not finitely generated. Actually, if one starts with any $`M`$ for which every ordering is cool and substitutes each letter for its square, this property is preserved. But now, $`\pi ^1M`$ is not finitely generated.

The similarity between Theorems 23 and 9 may suggest that perhaps a restricted form of 9 (ii) involving $`M_2`$ would hold. That is not likely, as suggested by $`M=\{x_1x_2^2,x_1x_2x_3^2,x_1x_2x_3x_4^2,\mathrm{}\}`$; the natural ordering of $`x_1,x_2,\mathrm{},x_n`$ is cool for $`M`$, for any $`n`$, even though $`M_2`$ is quite skimpy.

## 8 Commutative ideals given by inequalities

Another way of giving an ideal of $`[X]`$ is as the pre-image of an ideal under a morphism from $`[X]`$ to another free commutative monoid. This is useful only if there is a nice way of describing the morphisms and the ideals of the target. We will consider morphisms between commutative monoids and lift ideals given by generators.

In this setting, it will be convenient to switch to an additive notation for $`[X]`$. We number the letters of $`X`$ as $`x_1,x_2,\mathrm{},x_n`$, and identify $`[X]`$ with $`^n`$ by the isomorphism given by $`x_1^{i_1}x_2^{i_2}\mathrm{}x_n^{i_n}𝐱=(i_1,i_2,\mathrm{},i_n)`$. In this notation, a set $`I^n`$ is an ideal if $`𝐱𝐲I`$ implies $`𝐱I`$ (as usual, $`𝐱𝐲`$ means $`𝐱_i𝐲_i`$ for every $`i`$). Other terms require translation: monomials become vectors, letters become indices or coordinates of vectors, and so on.

Consider a morphism $`\phi :[X][Y]`$, where an isomorphism $`[Y]^m`$ is already fixed. If $`\phi (x_j)=_iy_i^{a_{ij}}`$, then $`\phi `$ is the linear map $`^n^m`$ given by the matrix $`A=(a_{ij})`$, where each $`a_{ij}`$ is a nonnegative integer. If $`J`$ is an ideal of $`^m`$, then $`I=\{𝐱^nA𝐱J\}`$ is an ideal of $`[X]`$; moreover, if $`J`$ is generated by the finite set $`W`$, then that same ideal $`I`$ can be described as:

$$I(A,W)=\{𝐱^nA𝐱w\text{for some}wW\}.$$

When $`w`$ is a vector in $`^m`$, we write $`I(A,w)`$ for $`I(A,\{w\})`$. Also, we stress that we only consider $`I(A,W)`$ when $`A`$ is nonnegative.

Given a generating set $`M`$ of an ideal of $`[X]`$, one can write down a description $`M=I(I_n,M)`$, simply using $`Y=X`$ and the identity morphism as $`\phi `$. From the complexity viewpoint, we notice that the new description has size bounded by a polynomial on the size of $`M`$; one interesting feature of the new type of description is that it can be much more compact. Just to give a trivial example, consider, for each $`k`$ in $``$, the ideal $`\{𝐱^2x_1+x_2k\}`$. The size of this description is $`O(\mathrm{log}k)`$, while clearly it has $`k+1`$ minimal generators.

Clearly, $`I(A,W)=_{wW}I(A,w)`$, and this suggests the following definition: we say that an ideal of $`[X]`$ is *convex* if it is of form $`I(A,w)`$ for some integer matrix $`A`$ and vector $`w`$. The name is motivated by the following fact, that follows from standard results in the theory of polyhedra (see  for terminology and facts about polyhedra that we use).

###### Proposition 24

Let $`I=M`$ be an ideal of $`[X]=^n`$, with $`M`$ finite. The following are equivalent:

* $`I`$ is convex.
* $`I`$ is the intersection of $`^n`$ with a convex set in $`^n`$.
* $`I=^n(\mathrm{conv}(M)+_+^n)`$ ($`\mathrm{conv}(M)`$ is the convex hull of $`M`$).

So, $`I(A,W)`$ is a union of convex ideals. It turns out that any union of convex ideals can be expressed as an $`I(A,W)`$. As we see below, this can be done without wasting much space, so we can switch descriptions without penalty in the coarse complexity of the problems we will talk about.

###### Lemma 25

Let $`I_1=I(A^{(1)},w^{(1)}),I_2=I(A^{(2)},w^{(2)}),\mathrm{},I_r=I(A^{(r)},w^{(r)})`$ be ideals of $`[X]`$. Then there exist a matrix $`A`$ and a set $`W`$ of vectors, with total size polynomial in the total size of the descriptions $`I(A^{(i)},w^{(i)})`$, such that $`_iI_i=I(A,w)`$.

Proof: Let $`A`$ result from piling up the matrices $`A^{(i)}`$ on top of each other. For each $`i`$, let $`w^i`$ result from extending $`w^{(i)}`$ with null entries corresponding to the inequalities of the other systems; so, $`I(A,w^i)=I_i`$. Finally, let $`W=\{w^1,w^2,\mathrm{},w^r\}`$.

For those of a more categorical persuasion, the proof is simply the substitution of a family of morphisms by its direct product. $`\mathrm{}`$

Now we consider what happens to the three guiding problems of the introduction when $`I`$ is given in the form $`I(A,W)`$. Problem 3 is sort of hopeless: since a description $`M`$ can be converted into a description $`I(A,W)`$ of size polynomial in the size of $`M`$, and Problem 3 is NP-complete when $`M`$ is the given data. It follows that this problem with $`I`$ given as $`I(A,W)`$ is NP-hard; to make things worse, we cannot even assert that it is in NP. At this point, we refer the reader again to  for a refresher on NP-completeness concepts, and, in particular, to the satisfiability problem, that will play an important role in the remainder of this section.

For the other two problems, our results are similarly bad and more definite. They will be shown to be coNP-complete. Indeed, we will add a new problem to the pack, that is completely trivial if the ideal is given by generators:

###### Problem 4

Given an ideal $`I`$ of $`[X]`$, is it generated by monomials with support of size at most $`2`$? That is, is there a set $`M`$ such that $`M=M_2`$ and $`M=I`$?

We register two basic algorithms pertaining to these problems.

###### Lemma 26

Given an ideal $`I=I(A,W)`$ and a vector $`𝐱`$, it can be decided in polynomial time whether $`𝐱I`$ and whether $`𝐱`$ is a minimal generator of $`I`$.

Proof: Computing $`A𝐱`$ and comparing the result with each member of $`W`$, we quickly decide membership in $`I`$. To decide whether an $`𝐱I`$ is minimal, it is enough to verify that each vector obtained from $`𝐱`$ by subtracting $`1`$ from a positive coordinate is not in $`I`$. $`\mathrm{}`$

In what follows, the proofs will be a bit sketchy, with some bare statements; filling in the details is routine handiwork.

###### Proposition 27

Problems 1, 2 and 4 are in coNP, when the ideal is given as $`I(A,W)`$.

Proof: For each problem, when the answer to an instance is no, we will present a short certificate, verifiable in polynomial time. That will be a minimal generator of the ideal, and some additional information. Notice that any minimal generator has coordinates bounded by the maximum of all coordinates in members of $`W`$, so it can be part of a short certificate.

For Problem 4, a certificate is simply a minimal generator with support of size at least $`3`$.

For Problem 1, a certificate is a minimal generator $`𝐦`$ and an index $`z`$ such that item (iii) of Theorem 23 is violated. That amounts to the following:

* There is no vector in $`I`$ whose support is $`\{z\}`$ (no power of $`z`$ is in $`M`$). This happens if and only if, for each $`wW`$, there is an index $`i`$ such that $`w_i>0`$ and $`a_{iz}=0`$.
* $`_{iz}m_i2`$ ($`m\backslash z`$ has degree $`2`$).
* There is no $`𝐱I`$ and index $`tz`$ such that $`m_t>0`$, $`x_t=1`$ and $`x_i=0`$ for every $`it,z`$. This is true, for each candidate $`t`$, if and only if for every $`wW`$ there exists an $`i`$ such that $`w_i>a_{it}`$ and $`a_{iz}=0`$.

For Problem 2, we assume, without loss of generality, that the ordering on the letters is that of the indexing. Now, a certificate consists of a minimal generator $`𝐦`$ and an index $`x`$, interior to $`𝐦`$ satisfying the condition: there is no minimal generator $`𝐬`$ whose first or last positive entry is in position $`x`$, and such that if $`𝐬^{}`$ results from $`𝐬`$ by turning the $`x`$-component to $`0`$, then $`𝐬^{}𝐦`$. This condition can be checked as follows. Let $`𝐦_{}`$ ($`𝐦_{}`$) result from $`𝐦`$ by changing to zero all components with index bigger (smaller) than $`x`$. Let also $`A^{}`$, $`W^{}`$ result from eliminating all rows $`i`$ such that $`a_{ix}>0`$. Then, $`x`$ satisfies the required condition if and only if neither $`𝐦_{}`$ nor $`𝐦_{}`$ is in $`I(A^{},W^{})`$. $`\mathrm{}`$

###### Proposition 28

Problems 1, 2 and 4 are coNP-complete, when the ideal is given as $`I(A,W)`$.

Proof: We will reduce directly from Sat to the negative of each problem. The reductions will have a lot in common. From each instance of Sat, we will produce a family of convex ideals $`I_i`$, like in Lemma 25; instead of presenting them in matrix form, we write them as systems of linear inequalities.

Given an instance $`S`$ of Sat on variables $`x_1,x_2,\mathrm{},x_n`$, (we assume $`n3`$) our inequalities will involve the variables $`x_1,\overline{x}_1,x_2,\overline{x}_2\mathrm{},x_n,\overline{x}_n`$, in obvious correspondence to the literals. For each clause, the corresponding *clause inequality* is

$$\text{sum of the literals in the clause}1.$$

Let $`I_0`$ be defined by the clause inequalities, together with the *boolean inequalities* $`x_i+\overline{x}_i1`$ for $`i=1,2,\mathrm{},n`$. The specific use of $`I_0`$ is the following: $`𝐱`$ is a solution of $`I_0`$ in nonnegative integers such that each boolean inequality is satisfied as equality if and only if $`𝐱`$ is a boolean assignment satisfying $`S`$.

We also define, for each $`i=1,2,\mathrm{},n`$, the ideal $`I_i`$ given by the single inequality $`x_i+\overline{x}_i2`$. Notice that $`I_i`$ has three minimal generators: two with single support ($`x_i=2`$ or $`\overline{x}_i=2`$), the other with two-element support ($`x_i=\overline{x}_i=1`$).

*Reduction to Problem 4:* The instance $`P`$ of Problem 4 consists precisely of the systems $`I_0,I_1,\mathrm{},I_n`$.

Suppose that $`S`$ is satisfiable, and let $`𝐱`$ be a boolean assignment satisfying $`S`$. Since for each $`i`$, exactly one of $`x_i`$ or $`\overline{x}_i`$ equals $`1`$, the support of $`𝐱`$ has size $`n3`$, and $`𝐱`$ is not in any $`I_i`$, $`i1`$. On the other hand, clearly $`𝐱`$ is in $`I_0`$. Also, $`𝐱`$ is minimal, since zeroing any variable would violate the corresponding boolean inequality. So, $`P`$ has a negative answer if $`S`$ is satisfiable.

Conversely, suppose $`P`$ has a negative answer, that is, the corresponding ideal has a minimal generator $`𝐱`$ whose support has size $`3`$. Clearly it cannot be in any $`I_i`$ with $`i1`$, so it is in $`I_0`$, and $`x_i+\overline{x}_i=1`$ for each $`i`$. Hence, $`S`$ is satisfiable.

*Reduction to Problem 2:* We introduce two new variables, $`y`$ and $`z`$, besides the ones we already have. The instance $`P`$ of Problem 2 consists of the systems $`I_1,\mathrm{},I_n`$, together with $`I_0^{}`$, which is $`I_0`$ with the addition of the inequality $`y1`$. The variables of $`P`$ will be ordered increasingly as $`y,z,x_1,\overline{x}_1,x_2,\overline{x}_2,\mathrm{},x_n,\overline{x}_n`$.

Suppose that $`S`$ is satisfiable, define $`𝐱`$ as before, and extend it by setting $`y=1`$ and $`z=0`$. Then this is a minimal generator and is only in $`I_0^{}`$. Now, $`z`$ is internal to this vector, but no minimal generator of the ideal has $`z`$ in its support (let alone, as an extreme entry), so condition (ii) of Theorem 9 is violated, and $`P`$ has a negative answer.

Conversely, if $`P`$ has a negative answer, there exists a minimal generator and an internal variable such that condition (ii) of Theorem 9 is violated. This minimal generator cannot be in any of the $`I_i`$, $`i1`$, since those have no internal letters. So it is in $`I_0^{}`$, and must have $`y=1`$, $`z=0`$, and the other variables must be a boolean assignment that satisfies $`S`$. The problematic internal variable must be $`z`$, but who cares?

*Reduction to Problem 1:* We use just one new variable $`y`$. The instance $`P`$ of Problem 1 consists of $`I_0`$, a new system $`I_{}`$, with the single inequality $`y2`$, systems $`I_i^{}`$, each obtained from $`I_i`$ by the addition of the inequality $`y1`$. By arguments similar to the preceding ones and the help of Theorem 23 (iii), it can be shown that $`S`$ is satisfiable if and only if $`P`$ has a negative answer. $`\mathrm{}`$

Proposition 24 (iii) says that a convex ideal is the set of integer points of a *blocking polyhedron*. Such polyhedra, and mostly their integer points, have been the subject of a lot of attention in the context of combinatorial and integer programming. This, and perhaps sheer curiosity, justify asking what happens to Problems 14 if one restricts the questions to convex ideals (given in the form $`I(A,w)`$). No one of the definite results we presented so far applies to convex ideals; in particular, the proof of Theorem 19 constructs ideals that are not convex, so even Problem 3’s status is undecided.