{'fraction_non_alphanumeric': 0.06495401205201395, 'fraction_numerical': 0.022074215033301616, 'mean_word_length': 3.6755634638196915, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An algebraic method of classification of S-integrable discrete models

A method of classification of integrable equations on quad-graphs is discussed based on algebraic ideas. We assign a Lie ring to the equation and study the function describing the dimensions of linear spaces spanned by multiple commutators of the ring generators. For the generic case this function grows exponentially. Examples show that for integrable equations it grows slower. We propose a classification scheme based on this observation.


Introduction
Nowadays discrete models (quad-graph equations) of the form are intensively studied due to their applications in physics, geometry, biology etc. Let us explain the notations in (1). Here the unknown is a function of two independent discrete variables u = u(m, n). The subindices and bar stand for the shifts of the arguments: u k = u(m + k, n), u k = u(m, n + k), u 1,1 = u(m + 1, n + 1). Function f is supposed to be locally analytic, it depends essentially on all three arguments. In other words equation (1) can be rewritten in any of the following forms At present various approaches are known for studying integrable discrete phenomena. The property of consistency around cube [1], has been proposed as the integrability criterion for quadrilateral difference equations [2], [3], [4]. Symmetry approach to the classification of integrable systems is adopted to discrete case [5], [6], [7], [8], [9]. Another characteristic property of an integrable equation is the vanishing of its algebraic entropy [10]. Alternative methods are used in [11], [12], [13]. In this article we suggest a new classification scheme for integrable discrete models.
About twenty years ago it was observed that characteristic Lie algebras, introduced in [14], in case of integrable hyperbolic type PDE's like sine-Gordon and Zhiber-Shabat equations have a very specific property. The dimensions of the linear spaces spanned by multiple commutators of the generators grow essentially slower than in generic case [15]. In [16] the problem of rigorous formalization of the notion of "slow growth" has been discussed. A conjecture was suggested and tested by applying to classify integrable equations of the form u x,y = f (u, u x ).
Here we consider another formalization of this property of the characteristic vector fields and test it by taking as a touchstone a particular case of quad-graph equation (1).
The article is organized as follows. In section 2 we introduce characteristic vector-fields and define the test Lie ring. A connection between integrability and the test ring is conjectured. In section 3 description of the test ring for discrete potential KdV equation is presented. The classification problem for the model of the form u 1,1 − u = g(u 1 −ū −1 ) is investigated in section 4. The result of classification is summarized in Theorem 5.

Characteristic vector fields and classification scheme
Let us define characteristic vector fields for the equation (1). We begin with a very particular case when the equation admits an n-integral i.e. a function I = I(u −j , u −j+1 , ...u k ) such that the equation holdsDI = I, whereD is the shift operator:Dh(m, n) = h(m, n + 1). This means that for any solution u = u(m, n) of equation (1) the value of the function I does not depend on the variable n. In the coordinate representation conditionDI = I means where r = f −1,1 (u, u −1 ,ū 1 ). Evidently the right hand side in (5) does not depend onū 1 hence the condition holds ∂ ∂ū 1D −1 I = 0 as well as Y I = 0 where Y :=D −1 ∂ ∂ū 1D . Due to the formula ∂r ∂ū 1 = 1/D −1 ( ∂f ∂ū 1 ) where D is the shift with respect to m, Dh(m, n) = h(m + 1, n), one finds (see also [17]) We call Y characteristic vector field. Now turn back to the general case and define characteristic vector field Y for chain (1) as a formal series given by formula (6).
Denote through T the set of vector fields obtained by taking all possible multiple commutators and linear combinations of the operators X := ∂ ∂ū −1 and Y with coefficients depending on a finite number of the dynamical variablesū −1 , u, u ±1 , u ±2 , ... . Evidently the set T has a structure of the Lie ring. We call it test ring of the equation (1) in the direction of n. In a similar way one can define the test ringT in the direction of m.
Notice that for Darboux integrable equations of the form (1) both rings T andT are of finite dimension. Actually the test ring is a subset of the characteristic Lie ring [17].
Denote through V j the linear space over the field of locally analytic functions spanned by X, Y and all multiple commutators of X and Y of order less than or equal to j such that: The following conjecture is approved by numerous examples.
Conjecture (algebraic test). Any integrable model of the form (1) satisfies the following condition: there is a sequence of natural numbers {t k } ∞ k=1 such that ∆(t k ) ≤ 1. Ring T admits an automorphism, generated by the shift operator D, which plays crucial role in our further considerations. It is important that X and Y considered as operators on the set of functions depending on the variablesū −1 , u, u ±1 , u ±2 , ... satisfy the following conjugation relations Indeed, specify the coefficients of the operator DXD −1 = a i ∂ ∂u i + p ∂ ∂ū −1 by applying it to the dynamical variables and find that a i = DXD −1 u i = 0 for any integer i.
. In a similar way one can prove the second formula. Really apply the ∂u j ∈ T satisfies the following two conditions: 1)

Discrete potential Korteweg-de Vries equation
In this section we give a complete description of the test Lie ring T for the discrete potential KdV equation [18] Theorem 1. The sequence X, Y, R 1 , P 1 , Q 1 , R 2 , P 2 , Q 2 , ... constitutes a basis of the characteristic ring T of equation (9).
Proof. It is easily checked that where y := D −1 x = x −1 . By using the relations DXD −1 = xX and D(yY )D −1 = Y , one can find the following equations A similar formula for R 2 is as follows For P 2 and Q 2 we have One can prove by induction that for any j > 1 and then [X, Give a matrix representation of the Lie algebra generated by the same operators X, Y . Let It can easily be checked that for equation (9) function ∆ = ∆(k) is periodic with period 2: ∆(2k) = 1, ∆(2k + 1) = 2.
4 Equations of the form u 1,1 = u + g(u 1 −ū 1 ) Apply the Conjecture to the following particular class of discrete model (1) Here g is a function to be determined. Classification scheme. Study separately the following four different cases of equation (20): (2) and ∆(k) ≤ 1 for some k > 2.
Where ∆ max (k) stands for the greatest value of ∆(k) for equation (1) when f (u, u 1 ,ū 1 ) ranges the class of arbitrary functions.
It is surprising that for equation (20) investigation of the first three particular cases i)-iii) allows one to extract a very short list of equations which are expected to be integrable. This list is exhaustive because the case iv) is never realized (see below Corollaries of Theorems 2 and 3).
Introduce vector fields Using these vector fields we can span in addition to V 0 and V 1 two more linear spaces: In order to evaluate ∆(k) we will use the automorphism (7). At first specify the factors x and p in formula (8) for the case (20): is the inverse to the function α = g(β). Inversely, knowing x = x(u 1 −ū −1 )) one can recover g(β) by using the equation Let us specify the action of the operators X and Y on the variable x. Evidently, Xx = −x ′ , Y x = xx ′ . It is found by direct calculation that x , Study the set G of all multiple commutators of X and Y . Lemma 2. The coefficients of any operator in G are functions of a finite number of the variables x, x ±1 , x ±2 , ... .
Proof. Since x = x(u 1 −ū −1 ) then evidently one can write x ′ = φ(x) for some function φ. Then X(x) = −φ(x) and Y (x) = xφ(x) =: ψ(x). By using the conjugation relations satisfies the statement of the lemma. Due to the formulas R 1 (x) = X(x)x ′ and DR 1 ..x j ). Obviously proof of the Lemma 2 can be completed by using induction.
Theorem 2. If a chain of the form (20) satisfies one of the conditions i) − iii) of the Classification scheme then function x = x(α) solves the following ordinary differential equation with γ, ν being constant. Proof of the theorem 2. Begin with the case i), suppose that ∆(0) = 0, then we have R 1 = λX + µY . It is evident that R 1 = X(x) ∂ ∂u 1 + ... and hence λ = µ = 0, therefore R 1 = 0. By applying the automorphism above to both sides of the last equation one finds Since X and Y are linearly independent we get equation x ′ = 0 which is a particular case of (23). Evidently its solution is x = c and due to (21) it can be found that β = g −1 (α) = − 1 c α + c 1 . Thus our equation α = g(β) (see (20)) is linear u 1,1 − u = −c(u 1 −ū 1 + c 1 ). For this case dim T = 2 so that ∆(k) = 0 for k ≥ 0. In a similar way one checks that condition ii) leads to (23). Indeed suppose that ∆(0) = 1 and ∆(1) < 2 then we have Here due to Lemma 2 functions ν and ǫ might depend only on x, x ±1 , x ±2 . . .. Apply the automorphism (7) to both sides of (24) then simplify due to equations (22): Comparison of the coefficients before linearly independent operators gives rise to the conditions By analyzing these equalities one concludes that equation (24) holds if and only if the following three conditions valid: ν = 0, ǫ = const, x ′ = ǫ(1 − x). Indeed under these conditions the last two equations above are satisfied automatically. Similarly one can check that Q 1 = νP 1 − ǫR 1 is equivalent to the same three conditions. Hence if ∆(1) < 2 then ∆(1) = 0 and therefore ∆(k) = 0 for any natural k ≥ 1. In this case dim T = 3. Suppose now that ∆(0) = 1, ∆(1) = 2 and ∆(2) ≤ 2 which corresponds to the case iii). Start with the case when Z is linearly expressed through the other vector fields in V 3 : Evidently α = β = 0, since X = ∂ ∂ū −1 and Y = ∂ ∂u + x ∂ ∂u 1 + ... and Z does not contain the terms ∂ ∂ū −1 and ∂ ∂u . By applying the automorphism to both sides of (25) and comparing the coefficients before linearly independent operators we find Since x = x(u 1 −ū −1 ) we have ψ = 0, φ = 0, ǫ = 0, δ = 0, γ = const. Comparison of the coefficients of X and Y gives one more equation xq = γx ′ . Finally we get two ordinary differential equations for x: The consistency condition of these equations is equivalent to equation (23). In this case Z = γR 1 . It is remarkable that x solves equation (23) if and only if W is linearly expressed through the other elelments of V 3 and then W = γR 1 . And the last possibility is when R 2 is linearly expressed through X, Y , R 1 , P 1 , Q 1 , W , Z. In this case x solves the equation x ′ = 0. The proof of the theorem is completed. In order to find x = x(α) evaluate the integral The answer is given by the formula Now find x by solving the equatin H(x) = α − α 0 .
In order to get the corresponding quad-graph equation (20) integrate again: Then the equation searched is given by the formula (20). Our conjecture is that equation (20) with g found from (26)-(28) is S-integrable. Calculating the integral (28) we find the list of equations desired. Corollary of Theorem 2. If for chain (20) one of the conditions i) − iii) is satisfied then the chain is of one of the form: where a, b, c, α 0 , β 0 are constants. The third equation is nothing else but the well-known dpkdv equation (9). Equations ii) and iii2) are reduced to one another by a simple change of independent variables m ↔ n. By changing the variables u = 1 √ γ ln v we reduce the last two equations to a bilinear form , recently it was proved that this equation admits infinite series of higher symmetries [19]. Equation iii3 ′ ) is a particular case of the Hietarinta-Viallet equation [20]: with c 5 = 0. Recently it was proved that equation (29) passes the symmetry test [22]. Study the set G consisting of X, Y and their all multiple commutators. Define the order of an element Z ∈ G as a number of its factors X and Y minus one. For instance ord[X, Y ] = 1, ord[X, [X, Y ]] = 2 and so on. Define the degree deg(Z) of Z as the exponent k in the conjugation relation DZD −1 = x k Z + ..., where the tail is a linear combination of the elements with orders less than ord(Z). Denote through G i,j a subset of G containing elements with the order i and the degree j. Let G i = j G i,j be the union of G i,j . Evidently the set G i,i−1 (as well as G i,−i+1 ) contains the only element Z i,i−1 = ad i X (Y ) up to the factor −1 (correspondingly, the only element Z i,−i+1 = ad i Y (X) up to the factor −1). Here the operator ad is defined as follows Theorem 3. Suppose that Z k,k−1 (or Z k,−k+1 ) is in the basis of the linear space V k ⊃ G k for any k: 3 ≤ k < N, but Z N,N −1 (respectively Z N,−N +1 ) is linearly expressed through the other operators in V N then function x = x(u 1 −ū −1 ) solves an equation of the form x ′ = ǫ(x − 1) with a constant coefficient ǫ.
Lemma 3. For any k ≥ 3 we have where c k > 0 and the tail contains a linear combination of the operators with the order less than k. Prove the Lemma 3 by method of mathematical induction. From the list of equations (22) one gets for Z = Z 3,2 and R 1 = Z 1,0 the following representation showing that the statement is true for the case k = 3. Suppose now that DZ k,k−1 where Z ν and Z µ range the basis of V N and the tail contains a linear combination of the operators of less order. Apply the automorphism D · D −1 (see (7) above) to both sides of (32): Compare the coefficients before Z ν and get Due to Lemma 2 functions a ν and b µ depend on x and its shifts. Moreover it follows from (33) that a ν cannot depend on x, x ±1 , x ±2 , . . . at all. Therefore the only possibility is a ν = 0. Compare now the coefficients before Z N −1,N −2 and find: where b is the coefficient of Z N −1,N −2 in the expansion (32). A simple analysis of equation (34) shows that b is constant. Thus (34) is equivalent to the equation Corollary of Theorem 3. The case iv) of the Classification scheme is never realized.
Proof. Suppose in contrary that such a case is realized. Then at least one of the vector fields Z k,k−1 or Z k,−k+1 should be linearly expressed through other elements of V k , otherwise ∆(k) ≥ 2. Therefore due to the Theorem 3 we have x ′ = ǫ(x − 1) which corresponds to the case ii) ∆(0) = 1, ∆(1) < 2. The contradiction shows that our assumption is not true. The proof is completed.
Study in details test rings T andT for equation iii1) from the list in Corollary of Theorem 2. It was mentioned earlier that the equation is reduced to ii) just by changing the independent variables m ↔ n. As it was shown above for ii) dimension of the ring T equals 3. This implies immediately that for the equation iii2) dimT = 3. Now concentrate on the ring T for this equation. Without loss of generality we take γ = 1 and get We have already proved that for (35) function x = x(α) solves the equation x ′ = x + 1. The characteristic vector fields X and Y act on the variables x, y = D −1 x as follows: Xx = −x ′ = −x − 1, Xy = −yy ′ = −y 2 − y, Y x = xx ′ = x 2 + x, Y y = y + 1. Scheme of the proof. Begin with the conjugation relations for multiple commutators. For instance, D(R 1 − Y + X)D −1 = R 1 + Y − X. It can easily be proved by induction that for k ≥ 1 D(P k − R k )D −1 = x(P k + R k ),

Conclusions.
A new classification scheme for quad-graph equations is suggested based on distributions of characteristic vector fields (see, for instance [21]). An exhaustive list of equations of the form u 1,1 − u = g(u 1 −ū −1 ) passing the suggested integrability test is obtained. It is important that all the equations found are known to be integrable. The Conjecture is approved to provide an effective classification tool for integrable quad-graph equations.