On computer-assisted classi�cation of coupled integrable equations

Mikhail V. Foursov

Universit� e Lille I, LIFL 59655 Villeneuve d’Ascq, France

foursov@li�.fr Marc Moreno Maza

Universit� e Lille I, LIFL 59655 Villeneuve d’Ascq, France

moreno@li�.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.

Keywords. Mathematical Physics. Integrable PDEs. Generalized Symmetries. Polynomial systems. Triangular Decompositions.

1. INTRODUCTION

One of the most powerful methods for solving nonlinear partial differential equations (PDEs) is the inverse scattering method. It allows one to find (albeit implicitly) solutions to the initial value problem. Moreover, the equations solvable by the inverse scattering possess 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 [26].

It is thus interesting to describe the equations that are solvable by the inverse scattering. Unfortunately, no general algorithm exists. However, it was noticed that 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 evolution equations, the most successful one is the method relying on the existence of higher-order generalized symmetries. It was successfully used by many authors (e.g. [18, 24, 28]) and it led to the discovery of numerous new integrable equations.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro�t or commercial advantage, and that copies bear this notice and the full citation on the �rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci�c permission and/or a fee. ISSAC 2001, UWO, Canada

\begin{matrix}c \\ ◯ \end{matrix}2001 ACM 1-58113-218-2/ 00/ 0008 $5.00

Classification of general classes of integrable equations requires solving overdetermined systems of nonlinear PDEs. Solving such systems is an intractable problem in practically all cases of interest (cf. [18]). These systems are particularly complicated when classifying coupled equations. The only attempts to investigate rather general coupled systems were done by Mikhailov, Shabat & Yamilov [19] and Svinolupov [30] who worked with Burgers-type and Schrödinger-type vector equations.

It thus became necessary to consider narrower classes of equations in order to be able do a complete classification thereof. 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 & Wang [28]. They showed that the list of known integrable autonomous homogeneous polynomial scalar evolution equations 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. Many authors have dealt with several different classes of homogeneous equations. We will mention here the works of Gerdt & Zharkov [13], Olver & Sokolov [24, 25] and Foursov [10, 12, 11].

In the present article we will be working with generalizations of the Kaup-Kupershmidt [16] equation

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

and the Sawada-Kotera equation [29]

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 (cf. [27, 21]). Yet there exists no point or contact transformation relating them. An interesting open problem is to find a property that would allow distinguishing these two equations, 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 system of evolution equations. 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 first considered by Zhou, Jiang & Jiang [33]. 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.

The only attempt to classify two-component integrable equations of this type was done by Foursov [10, 12] who considered symmetrically-coupled systems and found another integrable equation, (21) 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 4 we present the complete 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 achieve this task we apply a recent algorithm developed by the first author [11] and summarized in Section 3. This method 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 [20] 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.

2. 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.

Definition 1. A system (4) is called decoupled if it involves either an equation depending only on u or an equation depending only on v.

For a decoupled system, we can first solve the equation depending on only one variable and then use it to reduce the other equation to an x, t-dependent one-component equation. As a consequence, one function has no effect on the other and thus these equations are less interesting for applications. In this paper we will only consider equations that cannot be decoupled by a change of variables.

We observe that there are in fact two more reasons not to consider decouplable equations. First, Fokas’ conjecture [9] is certainly false for them. Second, the number of decouplable equations is extremely large in our situation rendering any thorough investigation of them impossible (in [10, 12] it was shown that there are at least 32 nondecoupled symmetrically-coupled equations, 30 of which can be decoupled by a linear change of variables).

Definition 2. 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 [23].

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

We remark that in general it is impossible to verify this property algorithmically. Fokas [9] conjectured that for an n-component system it suffices to produce n higher symmetries. Since we do not obtain any new equations in our classification (see Theorem 6), 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 different 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.

3. CLASSIFICATION OF HOMOGENEOUS EQUATIONS

For a given PDE, it is straightforward to check the existence of higher-order generalized symmetries. However, if one is interested in finding all equations from a certain class possessing this property, the problem becomes significantly harder. In the 1980s several attempts were made to classify general classes of scalar and coupled integrable equations. Unfortunately, it happened that is in an intractable problem in practically all cases of interest. The only classification that was successfully (and satisfactorily) completed is the case of general second-order evolution equations u_{t} = F (t, x, u, u_{x}, u_{xx}) (see Mikhailov, Shabat & Sokolov [18]).

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 4. 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 [24]. These packages were successfully used to implement several classifications of integrable equations (e.g. Olver & Sokolov [24, 25], Foursov [10, 12, 11]).

The obstruction condition (6) for the existence of symmetries 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 [11], we suggested 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 each 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)

This system is decoupled if either a_{2} = a_{4} = a_{5} = a_{6} = 0 or b_{1} = b_{3} = b_{4} = b_{5} = 0.

A two-component equation of type (7) is called nondegenerate if it is an n-th 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 5. 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 1. (Proven in [11]) By a general linear change of variables, an equation of type (7) can be reduced to canonical form, simultaneously with its symmetries.

Corollary 1. There are 17 commuting pairs of canonical matrices from (10) and (11). Thus, without loss of generality, the classifications need only to be done for these 17 commuting pairs of main matrices.

In each of the 17 cases, the obstruction equations take a significantly simpler form. In Sections 6 and 7 we show that the triangularization method [20] of the second author allows one to successfully treat all the above cases.

4. 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 [10, 12] where the author tried to investigate symmetrically-coupled equations of this type. However, using the standard Gröbner basis tools of Maple and Mathematica, it is 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{cases}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{cases}

(12)

We will present the complete list of nondecouplable equations of type (12) that possess a generalized symmetry of order 7. It would also be interesting to implement classifications of equations possessing a symmetry of orders 9 or 11, but the large size of the obtained systems makes it impossible to resolve them so far.

Before starting the main classification, we present the results of classifications of lower-order KdV–like equations. Let us first consider two-component systems of order 2 in the KdV weighting, i.e. systems of type

\begin{cases}u_{t} = αu_{xx} + βv_{xx} + λ_{1}u^{2} + λ_{2}uv + λ_{3}v^{2} \\ v_{t} = γu_{xx} + δv_{xx} + μ_{1}u^{2} + μ_{2}uv + μ_{3}v^{2} \end{cases}  (13)

Using our algorithm for classifying systems of homogeneous equations, we investigate equations of type (13) possessing symmetries of orders 3, 4, 5, 6 and 7. The computations lead to the following two theorems.

Theorem 2. An equation of type (13) possessing a symmetry of order 3 or 6 can be decoupled by a linear change of variables.

Theorem 3. An equation of type (13) 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 following equation:

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

The system (14) is not presented here in canonical form. We prefer this form since we can immediately see that it is equivalent to a one-component equation in u: the Boussinesq equation u_{tt} = −3D_{x}^{2}(u_{xx} + 4u^{2}). Thus, (14) is just another way to write the Boussinesq equation as a system of integrable evolution equations. The equation (14) was first found by Mikhailov, Shabat & Yamilov [19], who established its integrability. We remark that it is not the standard way to represent the Boussinesq equation in evolutionary form. The better known Boussinesq system is

\begin{cases}u_{t} & = & −3v_{x} \\ v_{t} & = & u_{xxx} + 8uu_{x} \end{cases}

Theorem 4. [11] A two-component system of evolution equations, 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{cases}u_{t} & = & u_{xxx} + uu_{x} + vv_{x} \\ v_{t} & = & −2v_{xxx} − uv_{x} \end{cases}  (15)
\begin{cases}u_{t} & = & u_{xxx} + 3uu_{x} + 3vv_{x} \\ v_{t} & = & vu_{x} + uv_{x} \end{cases}  (16)
\begin{cases}u_{t} & = & u_{xxx} + v_{xxx} + 2vu_{x} + 2uv_{x} \\ v_{t} & = & v_{xxx} − 9uu_{x} + 6vu_{x} + 3uv_{x} + 2vv_{x} \end{cases} (17)
\begin{cases}u_{t} & = & u_{xxx} + 2vu_{x} + uv_{x} \\ v_{t} & = & uu_{x} \end{cases}  (18)
\begin{cases}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{cases} (19)

Theorem 5. [11] 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 reduced to a decoupled form 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 7.

Theorem 6. An equation of type (12) possessing a generalized symmetry of order 7 in the KdV weighting can be reduced by a linear change of dependent variables either to a decoupled form, to a symmetry of a lower-order equation ((14)-(19)), or else to

\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} (20)

We remark that (20) is the equation found by Zhou, Jiang & Jiang [33]. Our theorem shows that it is the only nondecouplable equation of type (12) possessing a symmetry of order 7 that does not belong to a hierarchy starting at a lower-order equation.

However, a more interesting case is given by the fifth-order symmetry of the Boussinesq system (14)

\begin{cases}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{cases}

(21)

This equation was first considered by the first author [10, 12], but he did not realize at that time that this equation is a symmetry of a lower-order system. (21) possesses infinitely many symmetries and conservation laws, since it is a symmetry of the integrable equation (14).

Let us consider scalar reductions of (21) of the form v = f(u). We obtain a scalar PDE for u if and only if f(u) = k u + const, where k = ±1 or k = 0. The reduction v = 0 leads to the Kaup-Kupershmidt equation, while the reduction v = ±u gives us the Sawada-Kotera equation! Therefore, these two equations are closely related via the system (21) and they inherit the properties of (14). We remark that this seems to be the simplest known relationship between the Kaup-Kupershmidt and Sawada-Kotera equations. But what is even most significant, they appear as reductions in the hierarchy of the Boussinesq equation.

5. 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 of values: (3, 5), (3, 7) and (5, 7), the study of the latter case being one of the main contributions of this paper. The cases where b is even are much simpler to solve and do not lead to any nondecouplable integrable equation (see Theorem 5). The system K(a, b) is a system of homogeneous equations of degree 2 with the following numbers n and m of variables and equations.

\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}

In the above table v and t denote respectively the average numbers of variables and terms per equation.

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}, respectively. The last two 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}, it is natural to solve the K(a, b) systems for an ordering of variables such that any variable in C or D is greater in order than any variable in A or B. This will be our choice. Unfortunately, each of the K(a, b) system is too hard to solve for the polynomial system solvers we tried. Among them are the Gröbner engine GB [6, 7, 8] of J.-C. Faugère and the Triade solver, described in Section 6.

The first key step to solve the K(a, b) system is to split it into subcases according to Corollary 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 (d, e) commuting pair. For these systems to provide pairwise disjoint groups of solutions, we observe that one must add a list of inequalities to each system K(a, b, d, e). Following Definition 5, 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 (that are contained only in these polynomials). The former condition implies that a_{2}, a_{4}, a_{5}, a_{6} cannot vanish all together. Similarly, the latter one implies that b_{1}, b_{3}, b_{4}, b_{5} cannot vanish all together.

As we shall see in Section 7, 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)}.

The fact that the variety of each consistent subsystem is not unmixed, together with the large number of variables, renders very difficult the computation of Gröbner bases even modulo a small prime for a degree ordering. Therefore, it is natural 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 remain hard. Using an incremental method such as the method of Lazard [17] allows one to easily distribute the computations (see below). However, a purely incremental method may not deal efficiently with inconsistent polynomial systems. Consider for instance a system of the form {p_{1}, …, p_{m}, q} where p_{1}, …, p_{m} are polynomials and q = p_{1} ⋯ p_{m} − 1. Hence we use an hybrid method (described in the next section) which is incremental in some sense but keeps an eye on the whole system. However solving the consistent subsystems K(a, b, d, e) directly remains hard for (a, b) = (5, 7). We explain in Section 7 how we achieve this task.

6. TRIANGULAR DECOMPOSITIONS

A popular approach for solving a polynomial system whith 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 [20] for computing triangular decompositions of algebraic varieties. We show why this method is well-adapted in 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 [5]. 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 C ı ^{n} defined by polynomials in Q ı [x], where C ı and Q ı 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 Q ı [x]) is irreducible iff there exists a set f of polynomials in Q ı [x] such that f generates a prime ideal I(f) of Q ı [x] and V = V(f). If this holds, then the dimension of V is 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 Q ı [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. If V is an irreducible variety, then there exists a triangular set f such that V = \overline{W(f)}. Moreover, there is a canonical choice for f [22, 3].

We refer to [1] (and the references therein) for proofs and more details about triangular sets and quasi-components. In particular, it is shown in [1] 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 [14] and [32]. 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^{1} 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 ^{2} 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.

It follows from the above discussion that any variety can be decomposed as a finite union of Zariski closures of quasicomponents. In [15] Kalkbrener proposed an algorithm to compute this kind of decompositions, where each quasi-com-ponent is given by a regular chain. But in fact the following stronger result holds: any variety can be decomposed as a finite union of quasi-components. This statement appears in Wu [31] together with an algorithm. After these two major contributions, many variants and improvements have been proposed. We refer to the papers cited in [2].

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)} (22)

In other words, we can approximate the intersection of an hypersurface and a quasi-component by means of quasi-com-ponents. 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, given a polynomial set p = {p_{1}, p_{2}, …}, we can first compute intersect(p_{1}, ∅) = r_{1}, …, r_{ℓ}, then we can compute intersect(p_{2}, r_{1}), …, intersect(p_{2}, r_{ℓ}) and so on. An unproved sketch of such an algorithm appears first in [17] and a complete algorithm together with a proof is given in [20].

As we mentionned in Section 5, computing a triangular decomposition in a purely incremental manner may generate unnecessary computations. In [20] the problem is reduced significantly by considering intersections of varieties and quasi-components rather than intersections of hypersurfaces and quasi-components. Let f be a polynomial set and r 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 is viewed as solved system. 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

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

1In 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. 2The remaining points are contained in a variety whose dimension is less than that of \overline{W(f′)}.

Hence, decomposing the variety V(f) is achieved^{3} by repeated calls to decompose starting with the unsolved task (f, ∅).

We state now a key point of this approach. If f consists of a single polynomial p, then decompose({p}, r) returns tasks (f_{i}, r_{i}) satisfying the following: the task (f_{i}, r_{i}) is minimal (i.e. solved) iff the number of elements of r_{i} is not greater than that of r. This implies that the dimension of Z(f_{i}, r_{i}) is not less than that of Z(f, r). Roughly speaking, this means that decompose({p}, 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 those that may be redundant) is delayed until it is proved to be needed.

The main loop in the operation decompose proceeds as follows. First an optimal task (f_{i}, r_{i}) is chosen among those 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 the above key point. Then, 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 new tasks. When the list of new tasks is obtained, the algorithm merges it with the list of tasks that are already known. It 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.

7. SOLVING THE OBSTRUCTION SYSTEM

One of the main difficulties for solving the obstruction system K(a, b) by the method described in Section 6 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 5 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 our systems K(a, b, d, e). We compute a new ordering of variables, a triangular set T (w.r.t. this new ordering) and a polynomial set R such that:

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 ∩ Q ı [z]) the triangular set T specializes to a regular chain.

It follows immediately that this computation reduces the triangular decomposition of S to that of R.

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

To compute T and R we use the following facts.

• Some equations in S are not homogeneous and have a form hv + q where h is a constant, q is polynomial and v is variable which does not appear in q.

• Other equations in S have the form hv +q where v is a variable and q, h are polynomials that do not involve v and such that there exists an inequality which implies that h does not vanish at any zero of S.

In both cases we can eliminate the variable v from S and add hv + q to T. Obviously, these substitutions increase the size of the polynomials remaining in S. The key point in 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 [4].

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 the dependent variables u, v and rescaling the time by t ⟼ t/b_{2} leads to a new system of coupled equations whose main matrix is

(\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 have the same form. This provides new relations.

• For (d, e) = (2, 2) we split the system into two cases c_{2} = e/d and c_{2} ≠ e/d, 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 differential polynomial given in (6). For instance for (a, b) = (5, 7) we have S = S_{2}∪S_{3}∪S_{4}∪ S_{5}. Then we solve S incrementally by solving successively S_{2}, S_{3}, S_{4}, S_{5} and by using all the tricks above.

Once every system S is solved, the last task is to remove the solutions that leads to two-component equations that can be decoupled. This task is straightforward and we do not detail this point here.

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 they are many of them, an obvious notation is used. When the sequence of dimensions is too complicated, we only give their ranges.

2. The list of degrees (in the sense [2]) 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 4. 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 [11].

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  (17) (15) (16,18)

K(3, 7) (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  (17) (15,19) (16,18)

K(5, 7)  (1,1)  (2,2)
dim  12^{4}, 11^{19}, 10^{2}  12 ⋯ 0
deg.  1^{25}  2^{27}1^{9}
time  ≃ 5200  ≃ 1000
coupled sym. of (14) sym. of (17)

K(5, 7)  (3,3)  (5,3)
dim  12, 12, 10  12^{8}
deg.  2, 2, 1  1^{8}
time  ≃ 5000  320
coupled sym. of (15), sym. of (18), (20) sym. of (16)

8. 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.

9. REFERENCES

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

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

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

[4] F. Boulier, F. Lemaire, and M. Moreno Maza. PARDI! Technical Report LIFL 2001–01, Université Lille I, LIFL, 2001. In proceedings of ISSAC 2001.

[5] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms. Springer-Verlag, 1992.

[6] J.-C. Faugère. GB. ftp.lip6.fr//pub/softwares/GB.

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

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

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

[10] M.V. Foursov. On integrable evolution equations in commutative and noncommutative variables. PhD thesis, University of Minnesota, Minneapolis, 1999.

[11] M.V. Foursov. Complete classification of coupled integrable equations. I: Example of the KdV-type systems. Technical Report LIFL 2000-09, Université Lille-I, LIFL, 2000. Submitted to Nonlinearity.

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

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

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

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

[16] 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.

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

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

[19] 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.

[20] M. Moreno Maza. On triangular decompositions of algebraic varieties. Tech. Report, 1999. Presented at MEGA 2000.

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

[22] 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.

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

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

[25] P.J. Olver and V.V. Sokolov. Non-abelian integrable systems of the derivative nonlinear Schrödinger type. Inverse Problems, 14:L5–L8, 1998.

[26] R. Palais. The symmetries of solitons. Bull. Amer. Math. Soc., 34:339–403, 1997.

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

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

[29] 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.

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

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

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

[33] 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.