Article Submitted to Journal of Symbolic Computation

On computer-assisted classification of coupled integrable equations

Mikhail V. Foursov^{1} and Marc Moreno Maza^{2}

1ENSSAT de Lannion, 6 rue de Kérampont, 22305 Lannion Cedex, France foursov@enssat.fr 2Université Lille 1, LIFL, 59655 Villeneuve d’Ascq France moreno@lifl.fr

Abstract

We show how the triangularization method of the second author can be successfully applied to the problem of classification of homogeneous coupled integrable equations. The classifications rely on the recent algorithm developed by the first author that requires solving 17 systems of polynomial equations. We show that these systems can be completely resolved in the case of coupled Korteweg-de Vries, Sawada-Kotera and Kaup-Kupershmidt–type equations. This article is an improved and updated version of our paper appeared in the proceedings of ISSAC’2001. Mathematical Physics. Integrable PDEs. Generalized Symmetries. Po-

lynomial systems. Triangular Decompositions.

Introduction

One of the most powerful methods for solving nonlinear partial differential equations (PDEs) is the inverse scattering method. The equations solvable by the inverse scattering possess moreover a particularly interesting class of solutions: solitons. The solitons are traveling waves that preserve their shape after a collision with other solitons. This property is used in many applications, e.g. in propagation of light pulses along an optic fiber. An elemetary introduction to the soliton theory can be found in (Palais, 1997). See also Ablowitz and Clarkson (1991), Drazin and Johnson (1989), Novikov et al. (1984).

Foursov and Moreno Maza: On classification of coupled integrable equations 2

It is thus interesting to describe the equations solvable by the inverse scattering. Unfortunately, no general algorithm exists. However, these equations possess many other rare properties in common. Checking one or several of them gives one enough reasons to conjecture the solvability of a given equation. Among many different approaches to the problem of computer–assisted classification of integrable PDEs, one of the most successful is the method relying on the existence of higher-order generalized symmetries. It was used by many authors, e.g. Mikhailov et al. (1991), Olver and Sokolov (1998), Sanders and Wang (1998) and it led to the discovery of numerous new integrable equations.

Classification of general classes of integrable equations requires solving overdetermined systems of nonlinear PDEs, which is an intractable problem in practically all cases of interest (Mikhailov et al., 1991). The systems are particularly complicated when classifying coupled equations. The only attempts to study rather general coupled systems were done by Mikhailov et al. (1987) and Svinolupov (1989) who worked with vector Burgers and Schrödinger equations.

It thus became necessary to consider narrower classes of equations. It was noticed that many important integrable equations are homogeneous as differential polynomials in a certain weighting scheme. The most important result on homogeneous equations was proved by Sanders and Wang (1998) who showed that the list of known integrable autonomous homogeneous polynomial scalar PDEs with linear leading terms is exhaustive.

Two-component systems of evolution equations come up in many physical applications and have often been considered in the literature. We will mention here the classifications of Gerdt and Zharkov (1990), Olver and Sokolov (1998), Foursov (2000a,b), Sokolov and Wolf (1999), among others.

In the present article we will be working with generalizations of the Kaup– Kupershmidt equation (Kaup, 1980)

u_{t} = u_{xxxxx} + 10uu_{xxx} + 25u_{x}u_{xx} + 20u^{2}u_{x}  (1)

and the Sawada–Kotera (Sawada and Kotera, 1974) equation

u_{t} = u_{xxxxx} + 10uu_{xxx} + 10u_{x}u_{xx} + 20u^{2}u_{x}  (2)

These two equations have very similar properties: they possess a biHamiltonian structure, a recursion operator of degree 6 and are associated with third-order scattering problems. See (Rogers and Carillo, 1987) and (Musette and Verhoeven, 2000). Yet there exists no point or contact transformation relating them. An interesting open problem is to find a distinguishing property, a property that one equation has and the other does not. Our computations show that both equations appear as scalar reductions of the same two-component evolutionary system. Even though this does not prove that all their properties are the same, it gives more weight to the conjecture that no distinguishing property exists.

Two-component generalizations of the Kaup-Kupershmidt and Sawada-Kotera equations were considered by Zhou et al. (1990). They showed that the system

\begin{cases}u_{t} & = & u_{xxxxx} − 10uu_{xxx} + 30vv_{xxx} − 25u_{x}u_{xx} \\ & & +45v_{x}v_{xx} + 20u^{2}u_{x} − 30v^{2}u_{x} − 60uvv_{x} \\ v_{t} & = & −9v_{xxxxx} + 10vu_{xxx} + 30uv_{xxx} + 35v_{x}u_{xx} \\ & & +45u_{x}v_{xx} − 20uvu_{x} − 20u^{2}v_{x} − 30v^{2}v_{x} \end{cases}  (3)

possesses a Lax pair and an infinite hierarchy of conservation laws that are connected to the conservation laws of a coupled Zhiber-Shabat-Mikhailov equation.

An attempt to classify two-component integrable equations of this type was done by Foursov (2000b) who considered symmetrically-coupled systems and found another integrable equation: (19) below. In fact, we will show that this system is a part of a hierarchy of symmetries starting at a lower-order equation.

In Section 3 we present the classification of coupled equations of Kaup– Kupershmidt and Sawada–Kotera types possessing a generalized symmetry of order 7. We show that (3) is the only nondecouplable equation that is not a symmetry of a lower-order equation. To prove it, we apply a recent algorithm of the first author (Foursov, 2000a) (summarized in Section 2). It reduces the classification problem for homogeneous coupled integrable equations to solving 17 systems of algebraic equations. Each of them involves more than 500 equations and more than 100 variables. Moreover, the most interesting ones contain components of various dimensions and are hard to solve. In the last three sections of the paper, we show that the triangularization algorithm (Moreno Maza, 2000) developed by the second author is well-adapted to this problem since it allows one to perform the computations in a parallel and incremental manner.

1. Statement of the problem

Let us consider a system of two evolution equations

\begin{cases}u_{t} = F [u, v] \\ v_{t} = G[u, v] \end{cases}  (4)

Here F [u, v] = F (u, v, u_{x}, v_{x}, u_{xx}, …) denotes a differential polynomial function of u and v, i.e. a polynomial function of u, v and their x-derivatives. A system (4) is called decoupled if it involves either an equation depending only on u or an equation depending only on v. A system is decouplable if it can be decoupled by a linear change of dependent variables.

For a decoupled system, one function has no effect on the other and thus these equations are less interesting for applications. Moreover, the number of decouplable equations is extremely large in our situation rendering any thorough investigation of them impossible (Foursov (2000b) found 32 nondecoupled symmetrically-coupled equations, 30 of which can be decoupled). We will thus consider only the equations that cannot be decoupled by a change of variables.

Definition: A second system of t-independent evolution equations

\begin{cases}u_{t} = Q_{1}[u, v] \\ v_{t} = Q_{2}[u, v] \end{cases}  (5)

is said to be a generalized symmetry of (4) if their flows formally commute

D_{K}(Q) − D_{Q}(K) = 0.  (6)

Here Q = (Q_{1}, Q_{2}), K[u, v] = (F [u, v], G[u, v]) and D_{K} denotes the Fréchet derivative of K defined by D_{K}(Q) = \frac{d}{dε}K[u + εQ[u]]|_{ε=0}. For a more detailed explanation of generalized symmetries, see (Olver, 1993).

Definition: The system (4) is called integrable if it possesses infinitely many generalized symmetries.

We remark that while this problem can be solved for a certain class of scalar equations (Sanders and Wang, 1998), for most multi-component systems it is impossible to verify this property algorithmically. Fokas (1987) conjectured that for an n-component system it suffices to produce n higher symmetries. However, since we do not obtain any new equations in our classification (see Theorem 3.5), we will not have to rely on Fokas’ conjecture to establish integrability.

The classification problem: To find all (nondecouplable) equations of a given class that possess a higher order generalized symmetry of a certain specified class. Repeating such classification for several classes of symmetries will provide us the equations possessing several higher-order symmetries. Using Fokas’ conjecture, we can thus conclude that these equations are integrable.

Remark: Since the Fokas’ conjecture is false for decouplable equations, this is an additional reason not to consider them.

2. Classification of homogeneous equations

For a given PDE, it is straightforward to check the existence of higher-order generalized symmetries of a prescribed order. However, it is significantly harder to find all equations from a certain class possessing this property. After several attempts to classify general classes of scalar and coupled integrable equations, it was realized that it is an intractable problem in practically all cases of interest.

It thus became necessary to consider smaller classes in order to be able to investigate them completely. It was noticed that many integrable evolution equations possess a scaling Lie symmetry and are therefore homogeneous as differential polynomials in a certain weighting scheme. Moreover, their symmetries can be split into homogeneous components, each of which is a symmetry itself. Therefore, without loss of generality, we can only search for homogeneous symmetries.

Definition: Let us introduce the following weighting scheme on the space of differential functions. It assigns weight n to the dependent variables u, v and weight 1 to the x-differentiation. The weight of a monomial is the sum of the weights of its factors. When n = 2, we will call this weighting the KdV weighting. Equations homogeneous in the KdV weighting are called KdV–like equations.

To compute the obstruction condition (6), we use a Maple package written by the first author. This package uses the same algorithm as the Mathematica package created by Olver and Sokolov (1998). These packages were successfully used to implement several classifications of integrable equations, e.g. (Olver and Sokolov, 1998) and (Foursov, 2000b,a).

The obstruction condition (6) is a differential polynomial in u and v. A polynomial vanishes if all its coefficients vanish. In the homogeneous case, these coefficients are polynomials in the parameters of the equation and of the symmetry. The obstruction conditions form thus a system of algebraic equations. It is extremely difficult to deal with such systems in complete generality.

In a previous article Foursov (2000a) proposed the following method for attacking this problem. We remarked that general linear changes of dependent variables leave the equation in the same class and preserve its integrability. We can thus split the space of homogeneous equations into several equivalence classes. It would be sufficient to investigate one equation per equivalence class.

A general two-component homogeneous equation of order n is of the form

\begin{cases}u_{t} = αu_{nx} + βv_{nx} + lower order terms \\ v_{t} = γu_{nx} + δv_{nx} + lower order terms \end{cases}  (7)

where u_{nx} and v_{nx} are n-th order derivatives with respect to x. For example, a generic equation of order 3 homogeneous in the KdV weighting is of the form:

\begin{cases}u_{t} = a_{1}u_{xxx} + a_{2}v_{xxx} + a_{3}uu_{x} + a_{4}vu_{x} + a_{5}uv_{x} + a_{6}vv_{x} \\ v_{t} = b_{1}u_{xxx} + b_{2}v_{xxx} + b_{3}uu_{x} + b_{4}vu_{x} + b_{5}uv_{x} + b_{6}vv_{x} \end{cases}  (8)

A two-component equation of type (7) is called nondegenerate if it is an nth order equation, i.e. if not all of α, β, γ, δ vanish. The matrix A = (\begin{matrix}α & β \\ γ & δ \end{matrix}) of the coefficients of the linear terms is called the main matrix of the equation. In vector notation we will write the system as

u_{t} = Au_{nx} + lower order terms  (9)

where u = (u, v).

Let us make two observations. First, if the system of the form u_{t} = Bu_{kx} +⋯ is a generalized symmetry of u_{t} = Au_{nx} + ⋯, then the two main matrices commute, i.e. [A, B] = 0. Second, by a linear invertible change of dependent variables w = Ku (where K is an invertible matrix) a system of type (9) can be reduced to a system with the main matrix in Jordan canonical form.

Definition: Foursov (2000a) We say that the system of type (7) is in canonical form if its main matrix is of one of the following forms:

(\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) , (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}) , (\begin{matrix}1 & 0 \\ 0 & b_{2} \end{matrix}) , (\begin{matrix}0 & 1 \\ 0 & 0 \end{matrix}) , (\begin{matrix}1 & 0 \\ 0 & 0 \end{matrix})  (10)

where |b_{2}| ≥ 1 and b_{2} ≠ 1. The symmetry of type (7) is in canonical form if its main matrix is of one of the following forms:

(\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) , (\begin{matrix}1 & c_{2} \\ 0 & 1 \end{matrix}) , (\begin{matrix}1 & 0 \\ 0 & d_{2} \end{matrix}) , (\begin{matrix}0 & 1 \\ 0 & 0 \end{matrix}) , (\begin{matrix}0 & 0 \\ 0 & 1 \end{matrix}) ,  (11)

where c_{2} ≠ 0 and d_{2} ≠ 1.

Theorem 2.1: (Foursov, 2000a) By a general linear change of variables, an equation of type (7) can be reduced to canonical form, simultaneously with its symmetries.

Corollary 2.1: Without loss of generality, the classifications need only to be done for 17 commuting pairs of main matrices.

In each of the 17 cases, the obstruction equations take a significantly simpler form. In Sections 5 and 6 we show that the triangularization method (Moreno Maza, 2000) of the second author allows one to successfully treat all the cases.

3. The main results

The main goal of this article is to classify integrable equations that are homogeneous of order 5 in the KdV weighting. This problem was first approached in (Foursov, 2000b) where the author investigated symmetrically-coupled equations of this type. However, using the standard Gröbner basis tools of Mathematica, it was impossible to terminate the classification even in this reduced case.

We will thus be dealing with coupled Kaup-Kupershmidt and Sawada-Kotera– type equations, i.e. with systems of the following form

\{ \begin{matrix}u_{t} = & a_{1}u_{xxxxx} + a_{2}v_{xxxxx} + a_{3}uu_{xxx} + a_{4}vu_{xxx} + a_{5}uv_{xxx} + a_{6}vv_{xxx} \\ & + a_{7}u_{x}u_{xx} + a_{8}v_{x}u_{xx} + a_{9}u_{x}v_{xx} + a_{10}v_{x}v_{xx} \\ & + a_{11}u^{2}u_{x} + a_{12}uvu_{x} + a_{13}v^{2}u_{x} + a_{14}u^{2}v_{x} + a_{15}uvv_{x} + a_{16}v^{2}v_{x} \\ v_{t} = & b_{1}u_{xxxxx} + b_{2}v_{xxxxx} + b_{3}uu_{xxx} + b_{4}vu_{xxx} + b_{5}uv_{xxx} + b_{6}vv_{xxx} \\ & + b_{7}u_{x}u_{xx} + b_{8}v_{x}u_{xx} + b_{9}u_{x}v_{xx} + b_{10}v_{x}v_{xx} \\ & + b_{11}u^{2}u_{x} + b_{12}uvu_{x} + b_{13}v^{2}u_{x} + b_{14}u^{2}v_{x} + b_{15}uvv_{x} + b_{16}v^{2}v_{x} \end{matrix} (12)

We will present the complete list of nondecouplable equations of type (12) that possess a generalized symmetry of order 7. As to the symmetrieso of higher order, the large size of the obtained systems makes it impossible to resolve them so far.

Let us first recall the results of classification of lower-order KdV–like equations.

Theorem 3.1: An two-component evolutionary system, homogeneous of order 2 in the KdV weighting, possessing a symmetry of order 3 or 6 can be decoupled by a linear change of variables.

Theorem 3.2: An two-component evolutionary system, homogeneous of order 2 in the KdV weighting, possessing a symmetry of order 4, 5 or 7 can be reduced by a linear change of variables either to a decoupled form, or to the equation:

\{ \begin{matrix}u_{t} = & − 3v_{xx} \\ v_{t} = & u_{xx} + 4u^{2} \end{matrix}  (13)

We prefer to give this equation not in its canonical form, since we can immediately see that it is equivalent to the Boussinesq equation u_{tt} = −3D_{x}^{2}(u_{xx} + 4u^{2}). This nonstandard way to represent the Boussinesq equation in evolutionary form was first found by Mikhailov et al. (1987), who established its integrability.

Theorem 3.3: (Foursov, 2000a) A two-component evolutionary system, homogeneous of order 3 in the KdV weighting, that possesses a symmetry of order 5, 7 or 9, can be reduced by a linear change of dependent variables either to a decoupled form, or to one of the following:

\{ \begin{matrix}u_{t} = & u_{xxx} + uu_{x} + vv_{x} \\ v_{t} = & − 2v_{xxx} − uv_{x} \end{matrix}  (14)

\{ \begin{matrix}u_{t} = & u_{xxx} + 3uu_{x} + 3vv_{x} \\ v_{t} = & vu_{x} + uv_{x} \end{matrix}  (15)

\{ \begin{matrix}u_{t} = & u_{xxx} + v_{xxx} + 2vu_{x} + 2uv_{x} \\ v_{t} = & v_{xxx} − 9uu_{x} + 6vu_{x} + 3uv_{x} + 2vv_{x} \end{matrix}  (16)

\{ \begin{matrix}u_{t} = & u_{xxx} + 2vu_{x} + uv_{x} \\ v_{t} = & uu_{x} \end{matrix}  (17)

\{ \begin{matrix}u_{t} = & 4u_{xxx} + 3v_{xxx} + 4uu_{x} + vu_{x} + 2uv_{x} \\ v_{t} = & 3u_{xxx} + v_{xxx} − 4vu_{x} − 2uv_{x} − 2vv_{x} \end{matrix}  (18)

Theorem 3.4: (Foursov, 2000a) A two-component evolutionary system, homogeneous of order 3 in the KdV weighting, that possesses a symmetry of order 4, 6 or 8, can be decoupled by a linear change of dependent variables.

Now we can state the key result of this paper. The techniques that lead to the proof will be described in Section 6.

Theorem 3.5: An nondecouplable equation of type (12) possessing a generalized symmetry of order 7 can be reduced by a linear change of variables to a symmetry of a lower-order equation ((13)-(18)), or to the Zhou-Jiang-Jiang equation (3).

However, there is another maybe even more interesting case is given by the fifth-order symmetry of the Boussinesq system (13)

\{ \begin{matrix}u_{t} = & u_{xxxxx} + 10uu_{xxx} + 25u_{x}u_{xx} − 15v_{x}v_{xx} + 20u^{2}u_{x} \\ v_{t} = & v_{xxxxx} + 10uv_{xxx} + 5v_{x}u_{xx} + 5u_{x}v_{xx} + 20u^{2}v_{x} \end{matrix}  (19)

This equation was first considered by (Foursov, 2000b), who did not notice at that time that this equation is a symmetry of a lower-order integrable system.

Let us consider scalar reductions of (19). We obtain a scalar PDE for u if and only if v = k u + const, where k = ±1 or k = 0. The reduction v = 0 leads to the Kaup-Kupershmidt equation, while v = ±u gives the Sawada-Kotera equation! Therefore, these two equations are closely related via the system (19) and they inherit its properties. This seems to be the simplest known relationship between them. And even most significantly, they appear as reductions in the hierarchy of the Boussinesq equation. This also explains why it was more difficult to obtain explicit solutions for the Kaup–Kupershmidt equation than for the Sawada– Kotera equation. For more details, see Foursov and Moreno Maza (2001b).

4. The obstruction system

Let us consider a generic equation E_{a} of type (7) and order a, together with a generalized symmetry S_{b} of type (7) and order b > a, both homogeneous in the KdV weighting. Let us denote by K(a, b) the system of algebraic equations obtained from the obstruction condition (6). We consider for (a, b) the following couples: (3, 5), (3, 7) and (5, 7), the study of the last case being a main contributions of this paper. The cases where b is even are much simpler and do not lead to any nondecouplable integrable system (Theorem 3.4). The system K(a, b) is a system of degree 2 homogeneous equations with n variables, m equations, and with average numbers of variables and terms per equation v and t.

Table 1: Some data on the obstruction systems

\begin{matrix}(a, b) & (3,5) & (3,7) & (5,7) \\ (m, n) & (110,44) & (255,92) & (543,112) \\ (v, t) & (14,9) & (17,12) & (29,23) \end{matrix}

Each of these systems involves four groups of variables A, B, C and D. The first two correspond to the coefficients of the first and the second components of E_{a}. For instance, the groups of variables A and B in the system (12) are given by the a_{i} and the b_{j} respectively. The groups C and D correspond to the coefficients of the first and the second components of S_{b}, respectively. Since we are mainly interested in the equation E_{a}, we choose to solve the K(a, b) systems for an ordering of variables such that any variable in C or D is greater than any variable in A or B. Unfortunately, each system K(a, b) is too hard to solve for the polynomial system solvers such as the Gröbner engine GB by Faugère (1994, 1998, 1999) and the Triade solver written in Aldor (Bronstein et al., 2001) by the second author and whose underlying algorithm is described in Section 5.

The first key step in solving the K(a, b) system is to split it into subcases according to Corollary 2.1. For the d-th matrix in (10) and the e-th matrix in (11), the following 17 couples (d, e) give the commuting pairs of main matrices:

\begin{matrix}(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 4), \\ (3, 1), (3, 3), (3, 5), (4, 1), (4, 2), (4, 4), (5, 1), (5, 3), (5, 5). \end{matrix}

We denote by K(a, b, d, e) the subcase of K(a, b) corresponding to the commuting pair (d, e). In order to obtain pairwise disjoint groups of solutions, one must add a list of inequalities to each system K(a, b, d, e). Following Definition 2.2, we add the inequality c_{2} ≠ 0 for e = 2, the inequality d_{2} ≠ 1 for e = 3 and the inequalities b_{2} ≠ 1 and b_{2} ≠ 0 for d = 3. Moreover we add inequalities to specify that we are not interested in decoupled systems of PDEs. For instance for a = 3 we add to K(a, b, d, e) the equations a_{2}x_{2} + a_{4}x_{4} + a_{5}x_{5} + a_{6}x_{6} + 1 = 0 and b_{1}y_{1} + b_{3}y_{3} + b_{4}y_{4} + b_{5}y_{5} + 1 = 0, where x_{2}, x_{4}, x_{5}, x_{6}, y_{1}, y_{3}, y_{4}, y_{5} are new auxilliary variables (appearing only in these polynomials). The former condition implies that a_{2}, a_{4}, a_{5}, a_{6} do not vanish at the same time. The latter implies that b_{1}, b_{3}, b_{4}, b_{5} do not vanish at the same time.

As we shall see in Section 6, each system K(a, b, d, e) either is inconsistent (over the complex numbers) or its algebraic variety contains components of various dimensions. In the latter case, solving such a system is hard. This happens for (e, d) ∈ {(1, 1), (2, 2), (3, 3), (3, 5), (5, 3)}.

Since the variety of each consistent subsystem is not unmixed, and the number of variables is large, it is very difficult to compute the Gröbner bases for a degree ordering, even modulo a small prime. It is thus reasonable to use a method decomposing the variety of each consistent subsystem into unmixed components.

Each consistent subsystem splits into only a few irreducible components. Hence computing each component may be still hard. Using an incremental method such as the method of Lazard (1991) allows one to easily distribute the computations. However, a purely incremental method may perform many superfluous computations. We use an hybrid method which is incremental in some sense but “keeps an eye” on the whole system. Solving the consistent subsystems K(a, b, d, e) directly is still hard when (a, b) = (5, 7). We explain below how we achieve it.

5. Triangular Decompositions

A popular approach for solving a polynomial system with components of various dimensions is to compute a triangular decomposition. However, this computation is sometimes difficult since many redundant components may be generated during the decomposition process. This is especially true for large systems with components of high dimensions such as the K(a, b) systems.

We give here the principles of a method presented in (Moreno Maza, 2000) for computing triangular decompositions of algebraic varieties. We show why this method is well-adapted to our context. We assume that the reader is familiar with the elementary theory of polynomial ideals, especially with the notions of prime ideal and dimension. For both varieties and polynomial ideals we refer to (Cox et al., 1992). We start by reviewing some notions related to varieties.

Let x_{1} < ⋯ < x_{n} be n ordered variables. We will simply denote the tuple (x_{1}, …, x_{n}) by x. Since this is sufficient for our needs, we restrict our attention to algebraic varieties of the affine space ℂ^{n} defined by polynomials in ℚ[x], where ℂ and ℚ denote respectively the fields of complex and rational numbers. Recall that the union and the intersection of two varieties is a variety. A variety V is called irreducible if whenever V can be written as V = V_{1} ∪ V_{2}, where V_{1} and V_{2} are varieties, then either V = V_{1} or V = V_{2}. We have the following property: the variety V (defined by polynomials in ℚ[x]) is irreducible if and only if there exists a set f of polynomials in ℚ[x] such that f generates a prime ideal I(f) of ℚ[x] and V = V(f). If this holds, then the dimension of V is the same as that of I(f). We have the following theorem: there exists a finite set of irreducible varieties V_{1}, …, V_{d} such that V = V_{1} ∪ ⋯ ∪ V_{d} holds. Moreover, if none of the varieties V_{1}, …, V_{d} is contained in another one, this set is unique. The varieties V_{1}, …, V_{d} are called the irreducible components of V and the variety is unmixed if all its irreducible components have the same dimension.

A set f = {f_{1}, …, f_{s}} of non-constant polynomials in ℚ[x] is triangular if for every variable x_{i} there is at most one polynomial f_{j} in f whose greatest variable is x_{i}. Regarding each polynomial f_{j} in f as univariate w.r.t. its greatest variable, the leading coefficient of f_{j} is called the initial of f_{j}. If f is triangular, then the quasi-component associated with f is the set W(f) of the points of the variety V(f) that do not cancel any initial of a polynomial in f.

The quasi-component W(f) may not be a variety. For instance, if n = 2, s = 1 and h_{1} = x_{1}x_{2} then W(f) is the x_{1}-axis minus the origin. However W(f) is very close to a variety with good properties. This variety is simply the intersection of all varieties that contain W(f), it is denoted by \overline{W(f)} and called the Zariski closure of W(f). We can state now two important properties of quasi-components. If W(f) is not empty, then \overline{W(f)} is unmixed of dimension n − s (Boulier et al., 2001b). If V is an irreducible variety, then there exists a triangular set f such that V = \overline{W(f)} (Aubry et al., 1999). Moreover, there is a canonical choice for f (Ollivier, 1990; Boulier and Lemaire, 2000).

We refer to (Aubry et al., 1999) (and the references therein) for proofs and more details about triangular sets and quasi-components. In this paper, it is shown in (Aubry et al., 1999) that the notion of a triangular set needs to be strengthened in order to obtain good properties, especially from an algorithmic point of view. This leads to the notion of a regular chain originally introduced in (Kalkbrener, 1991) and (Yang and Zhang, 1991). Let p be a non-constant polynomial with greatest variable x_{i} and let f′ be a triangular set whose variables are all smaller than x_{i}. Then the triangular set f = f′ ∪ {p} is a regular chain if either f′ is empty or f′ is a regular chain and the initial of p is regular^{∗} w.r.t. the ideal of the polynomials that vanish on \overline{W(f′)}. Roughly speaking, if f′ ∪\{p\} is a regular chain, then almost all points^{†} of W(f′) extend to a point of W(f′∪{p}). In particular, if f is a regular chain, then W(f) is not empty.

Any variety can thus be decomposed as a finite union of Zariski closures of

∗In a polynomial ring, an element p is regular w.r.t. an ideal I if it does not belong to any prime ideal associated with I.

†The remaining points are contained in a variety whose dimension is less than that of \overline{W(f′)}.

quasi-components. Kalkbrener (1993) proposed an algorithm to compute such decompositions, where each quasi-component is given by a regular chain. In fact, the following stronger result holds: any variety can be decomposed as a finite union of quasi-components. This was proven by Wu (Wu, 1987) who proposed an algorithm. After these two major contributions, many variants and improvements were proposed. See (Aubry and Moreno Maza, 1999) and references therein.

Decompositions in the sense of Wu can be obtained as follows. Let p be a polynomial and r a regular chain. There exists an algorithm called intersect which computes regular chains r_{1}, …, r_{ℓ} such that we have:

V(p) ∩ W(r) ⊆ W(r_{1}) ∪ ⋯ ∪ W(r_{ℓ}) ⊆ \overline{V(p) ∩ W(r)}  (20)

In other words, we can approximate the intersection of a hypersurface and a quasi-component by means of quasi-components. By using the algorithm intersect, it is straightforward to design an incremental procedure for decomposing any variety into quasi-components (given by regular chains). Indeed, consider a polynomial set f = {f_{1}, f_{2}, …}. We first compute intersect(f_{1}, ∅) = r_{1}, …, r_{ℓ}. Then we compute intersect(f_{2}, r_{1}), …, intersect(f_{2}, r_{ℓ}) and rename r_{1}, …, r_{ℓ} all the computed regular chains. Continuing on in this way with f_{3} instead of f_{2}, then f_{4} instead of f_{3}, and so on, we obtain regular chains r_{1}, …, r_{ℓ} such that

V(f) = W(r_{1}) ∪ ⋯ ∪ W(r_{ℓ}).  (21)

An unproved sketch of such an algorithm appears first in (Lazard, 1991) and a complete algorithm together with a proof is given in (Moreno Maza, 2000).

As we mentionned in Section 4, this purely incremental procedure may generate unnecessary computations. Consider for instance a system of the form {f_{1}, …, f_{m}, g} where f_{1}, …, f_{m} are polynomials whose product equals g + 1 and such that the variety associated to the subsystem {f_{1}, …, f_{m}} is not empty. In order to quickly discover that the input system is inconsistent, the purely incremental procedure must process g at an early stage of the computation. More generally, a purely incremental procedure may generate intermediate quasicomponents that will be contained in one of the quasi-components of the final output. To overcome this difficulty Lazard (1991) suggested to produce the intermediate quasi-components by decreasing order of dimension such that superfluous quasi-components could be detected at an early stage of the computations.

In (Moreno Maza, 2000) this problem is solved by considering intersections of varieties and quasi-components rather than intersections of hypersurfaces and quasi-components. Let f be a polynomial set and r be a regular chain. We denote by Z(f, r) the intersection of the variety V(f) and the quasi-component W(r). We call the couple (f, r) a task. There exists a Noetherian decreasing ordering on the tasks (f, r) such that the minimal tasks are those satisfying f = ∅. Every mininal task (∅, r) is viewed as a solved system whose solution is r. Then there exists an algorithm called decompose which computes polynomial sets f_{1}, …, f_{ℓ} and regular chains r_{1}, …, r_{ℓ} such that every task (f_{i}, r_{i}) has a smaller rank than the task (f, r) and such that we have:

Z(f, r) ⊆ Z(f_{1}, r_{1}) ∪ ⋯ ∪ Z(f_{ℓ}, r_{ℓ}) ⊆ V(f) ∩ \overline{W(r)}  (22)

We state now a key point of this approach. For any input polynomial system f, the operation decompose(f, r) returns tasks (f_{i}, r_{i}) satisfying the following: the task (f_{i}, r_{i}) is minimal (i.e. solved) if and only if the number of elements of r_{i} is equal to that of r. This implies that the dimension of Z(f_{i}, r_{i}) is equal to that of Z(f, r). Roughly speaking, this means that decompose(f, r) returns a minimal task provided that it corresponds to a major component (a component with maximal dimension) of Z(f, r). Thus the computation of the other components (which are potentially redundant) is delayed until it is proved to be needed. We detail this last point now.

For any input polynomial system f, computing a decomposition of the variety V(f) in the form (21) is achieved^{‡} by repeated calls to decompose as follows. During the computations, we manage a list T of tasks (f_{1}, r_{1}), (f_{2}, r_{2}), … (f_{d}, r_{d}). At the beginning this list is reduced to (f, ∅) where f is the input system and the computations stop when every f_{i} is empty. Before that, for every call to decompose an optimal task (f_{i}, r_{i}) is chosen among those tasks of T that are not minimal. By optimal we mean a task (f_{i}, r_{i}) such that the dimension of Z(f_{i}, r_{i}) is a priori maximal. (Such an estimate of this dimension is obtained by means of the above key point.) By advancing the computations mainly for the major components of Z(f_{i}, r_{i}), the chosen task (f_{i}, r_{i}) is replaced by a list of new tasks T′. Then the list T and T′ are merged into a list that replaces T. This is during this step of merging that the unnecessary calculations (i.e. redundant tasks) can be discovered. Finally, we observe that this task processing can be improved by storing in each task (f_{i}, r_{i}) the additional information discovered during the computation, such as inequalities.

6. Solving the obstruction system

One of the main difficulties for solving the obstruction system K(a, b) by the method described in Section 5 is the large number of equations. Indeed, during the step of merging, the tasks need to be compared. This comparison depends obviously on the number of polynomials in each task.

Splitting this system K(a, b) into subcases as described in Section 4 does not reduce the number of equations and variables per system significantly. However, it renders efficient the following strategy for solving most systems.

Let S be one of the systems K(a, b, d, e). We compute a new ordering of variables, a triangular set T (w.r.t. this ordering) and a polynomial set R such that:

‡Since the closure in Condition (22) does not cover the whole intersection, this condition is weaker than (20). However, additional technical conditions ensure the correction of the method.

1. V(S) = W(T) ∪ V(R),

2. for every polynomial p ∈ T, the greatest variable of p is greater than any element of the variable set z of R,

3. for every zero of V(R ∩ ℚ[z]) the triangular set T specializes to a regular chain.

This computation reduces the triangular decomposition of S to that of R.

To compute T and R we use the following fact. Some equations in S are of the form hv + q where v is a variable and q, h polynomials not involving v such that h does not vanish at any zero of S due to inequalities. Then we can eliminate the variable v from S and add hv + q to T. Even though these substitutions increase the size of the polynomials, the key point of this elimination process is to find the eliminating polynomials hv + q that will limit the swell of S.

For the simplest systems S, the triangularization of R is easy. This is the case for (a, b) ∈ {(3, 5), (3, 7)} and (d, e) ∉ {(2, 2), (3, 3)}. We observe that a triangular decomposition of S for the original ordering can be obtained from that of T ∪ R by means of the PALGIE algorithm (Boulier et al., 2001a).

For some of the remaining systems, we use the following additional facts.

• Without loss of generality, for (a, b, d, e) = (5, 7, 1, 1) one can put b_{3} = 0 in (12) by applying an additional linear change of dependent variables.

• For d = 3, exchanging u, v and rescaling t ↦ t/b_{2} leads to a new system with the main matrix (\begin{matrix}1 & 0 \\ 0 & 1/b_{2} \end{matrix}). This new system possesses a generalized symmetry if and only if the original system does. Moreover, the main matrices of both systems are of the same form. This provides new relations.

• For (d, e) = (2, 2) we split the system into two cases c_{2} = b/a and c_{2} ≠ b/a, since we observed that this trick provided a significant speed-up.

For the hardest systems S, we use the following strategy. We consider the system S_{i} consisting of the coefficients of the monomials of order i in the obstruction equations (6). For instance, for (a, b) = (5, 7) we have S = S_{2} ∪ S_{3} ∪ S_{4} ∪ S_{5}. Then we solve S incrementally using all the tricks above.

Once every system S is solved, the last task is to remove the solutions that leads to decouplable equations. This is done by applying the general linear change of dependent variables. Without loss of generality, the determinant of the matrix can be put to 1, and thus there are 3 parameters we can vary. The coefficients of terms involving v in the first equation and involving u in the second equation are then equated to zero. The system can be decoupled if and only if this new system of polynomial equations in 3 variables has a solution.

For (a, b) ∈ {(3, 5), (3, 7), (5, 7)} and for (d, e) ∈ {(1, 1), (2, 2), (3, 3), (5, 3)} we give the following results about K(a, b, d, e):

1. The list of dimensions of the irreducible components. When the sequence of dimensions is too complicated, we only give their ranges.

2. The list of degrees (in the sense (Aubry and Moreno Maza, 1999)) with a similar convention about the dimensions.

3. The computation time in seconds on a 733MHz Pentium III PC. When the computation is not the result of a single call to a binary (but required several calls), we give an estimated time.

4. The obtained coupled integrable equations. Numbers refer to the results of Section 3. We point out that the systems obtained in the cases K(3, 5) and K(3, 7) are the same as the systems obtained by Foursov (2000a).

Table 2: The K(3, 5) case

K(3, 5) (1,1) (2,2) (3,3) (5,3)
dim. 7,6,6,6 7,6,6 6,6  6,6
deg. 1,1,1,1 2,1,1 1,1  1,1
time  2  7  10  3
coupled  no  (16) (14) (15,17)

Table 3: The K(3, 7) case

(1,1) (2,2)  (3,3)  (5,3)
dim. 7,6,6,6 7,6,6,6  6,6  6,6
deg. 1,1,1,1 2,1,1,1  2,1  1,1
time  10  93  294  25
coupled  no  (16) (14,18) (15,17)

Table 4: The K(5, 7) case

(1,1)  (2,2)  (3,3)  (5,3)
dim. 12^{4}, 11^{19}, 10^{2}  12 ⋯ 0  12, 12, 10  12^{8}
deg.  1^{25}  2^{27}1^{9}  2, 2, 1  1^{8}
time  ≃ 5200  ≃ 1000  ≃ 5000  320
coupled sym. of (13) sym. of (16) sym. of (14), sym. of (17), (3) sym. of (15)

7. Conclusions

We showed that the methods of Mathematical Physics and Computer Algebra can be efficiently combined together to help to solve problems that could not be solved by any other approach. These techniques led to the discovery of new integrable systems of coupled evolution equations and of a relation between the Sawada-Kotera and Kaup-Kupershmidt equations. We think that the algebraic processing presented in this paper can still be improved in order to implement more difficult classification problems.

References

M.J. Ablowitz and P.A. Clarkson. Solitons, Nonlinear Evolution Equations and Inverse Scattering. Cambridge University Press, Cambridge, 1991.

P. Aubry, D. Lazard, and M. Moreno Maza. On the theories of triangular sets. J. Symb. Comp., 28:105–124, 1999.

P. Aubry and M. Moreno Maza. Triangular sets for solving polynomial systems: A comparative implementation of four methods. J. Symb. Comp., 28:125–154, 1999.

F. Boulier and F. Lemaire. Computing canonical representatives of regular differential ideals. In proceedings of ISSAC 2000, pages 37–46, 2000.

F. Boulier, F. Lemaire, and M. Moreno Maza. PARDI ! In proceedings of ISSAC 2001, pages 38–47, 2001a.

F. Boulier, L. Lemaire, and M. Moreno Maza. Well-known theorems on triangular systems. Tech. report LIFL 2001–08, 2001b.

M. Bronstein, M. Moreno Maza, and S.M. Watt. Aldor User Guide. University of Western Ontario, 2001. http://www.aldor.org/AldorUserGuide/.

D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms. Spinger-Verlag, 1992.

P.G. Drazin and R.S. Johnson. Solitons : an introduction. Cambridge University Press, 1989.

J.-C. Faugère. Résolution des systèmes d’équations algébriques. PhD thesis, Université de Paris-VI, 1994.

J.-C. Faugère. A new efficient algorithm for computing Gröbner bases. In Proceedings of MEGA’98, 1998.

J.-C. Faugère. GB. ftp://calfor.lip6.fr//pub/softwares/GB, 1999.

A.S. Fokas. Symmetries and integrability. Stud. Appl. Math., 77:253–299, 1987.

M.V. Foursov. Complete classification of coupled integrable equations. I: example of KdV-type systems. Tech. Report LIFL 2000-09, 2000a, (submitted).

M.V. Foursov. On integrable coupled KdV-type systems. Inverse Problems, 16: 259–274, 2000b.

M.V. Foursov and M. Moreno Maza. On computer-assisted classification of coupled integrable equations. In proceedings of ISSAC 2001, pages 129–136, 2001a.

M.V. Foursov and M. Moreno Maza. On the relationship between the Kaup-Kupershmidt and Sawada-Kotera equations.Tech.Report LIFL2001-04, 2001b.

V.P. Gerdt and A.Y. Zharkov. Computer classification of integrable coupled KdV-like systems. J. Symb. Comp., 10:203–207, 1990.

M. Kalkbrener. Three contributions to elimination theory. PhD thesis, Johannes Kepler University, Linz, 1991.

M. Kalkbrener. A generalized euclidean algorithm for computing triangular representations of algebraic varieties. J. Symb. Comp., 15:143–167, 1993.

D.J. Kaup. On the inverse scattering problem for cubic eigenvalue problems of the class ψ_{xxx} + 6qψ_{x} + 6rψ = λψ. Stud. Appl. Math., 62:189–216, 1980.

D. Lazard. A new method for solving algebraic systems of positive dimension. Discr. App. Math, 33:147–160, 1991.

A.V. Mikhailov, A.B. Shabat, and V.V. Sokolov. The symmetry approach to classification of integrable equations. In V.E. Zakharov, editor, in “What is integrability?”, pages 115–184. Springer-Verlag, 1991.

A.V. Mikhailov, A.B. Shabat, and R.I. Yamilov. The symmetry approach to the classification of nonlinear equations. Complete lists of integrable systems. Russ. Math. Surveys, 42:1–63, 1987.

M. Moreno Maza. On Triangular Decompositions of Algebraic Varieties. Tech. report, NAG, 2000. (presented at the MEGA2000 conference).

M. Musette and C. Verhoeven. Nonlinear superposition formula for the Kaup-Kupershmidt partial differential equation. Physica D, 144:211–220, 2000.

S.P. Novikov, S.V. Manakov, L.P. Pitaevskii, and V.E. Zakharov. Theory of Solitons : The Inverse Scattering Method. Kluwer Academic Publishers, 1984.

F. Ollivier. Le problème de l’identifiabilité structurelle globale : approche théorique, méthodes effectives et bornes de complexité. PhD thesis, École Polytechnique, 1990.

P.J. Olver. Applications of Lie groups to differential equations. Springer–Verlag, Second edition, 1993.

P.J. Olver and V.V. Sokolov. Integrable evolution equations on associative algebras. Comm. Math. Phys., 193:245–268, 1998.

R. Palais. The symmetry of solitons. Bull. Amer. Math. Soc., 34:339–403, 1997.

C. Rogers and S. Carillo. On reciprocal properties of the Caudrey-Dodd-Gibbon and Kaup-Kupershmidt hierarchies. Phys. Scr., 36:865–869, 1987.

J.A. Sanders and P.J. Wang. On the integrability of homogeneous scalar evolution equations. J. Diff. Eq., 147:410–434, 1998.

K. Sawada and T. Kotera. A method for finding N-soliton solutions of the KdV equation and of KdV-like equations. Prog. Theor. Phys., 51:1355–1367, 1974.

V.V. Sokolov and T. Wolf. A symmetry test for quasilinear coupled systems. Inverse Problems, 15:L5–L11, 1999.

S.I. Svinolupov. On the analogues of the Burgers equation. Phys. Lett. A, 135: 32–36, 1989.

W. T. Wu. A zero structure theorem for polynomial equations solving. MM Research Preprints, 1:2–12, 1987.

L. Yang and J. Zhang. Searching dependency between algebraic equations: an algorithm applied to automated reasoning. Tech. Report IC/89/263, International Atomic Energy Agency, Miramare, Trieste, Italy, 1991.

H.Q. Zhou, L.J. Jiang, and Q. Jiang. Connection between infinite conservation laws of a coupled Zhiber-Shabat-Mikhailov equation and a coupled Kaup-Kupershmidt equation. Phys. Lett. A, 143:288–292, 1990.