extfieldsofstudy:
Computer Science
Mathematics

text:
Proving Termination of Normalization Functions for Conditional Expressions

Boyer and Moore have discussed a recursive function that puts conditional expressions into normal form [1]. It is difficult to prove that this function terminates on all inputs. Three termination proofs are compared: (1) using a measure function, (2) in domain theory using LCF, (3) showing that its recursion relation, defined by the pattern of recursive calls, is well-founded. The last two proofs are essentially the same though conducted in markedly different logical frameworks. An obviously total variant of the normalize function is presented as the `computational meaning' of those two proofs. A related function makes nested recursive calls. The three termination proofs become more complex: termination and correctness must be proved simultaneously. The recursion relation approach seems flexible enough to handle subtle termination proofs where previously domain theory seemed essential.

A normalization function
Boyer and Moore have published a machine-assisted proof of the correctness of a tautology checker for propositional logic [1]. Propositions are represented as conditional expressions (henceforth expressions). An expression is either an atom At(a) for some symbol a, or else has the form If (x, y, z) where x, y, z are themselves expressions. An atom represents a propositional letter, while If (x, y, z) is equal to y if x is true, and equal to z otherwise.
The tautology checker includes a function for putting expressions into normal form. An expression is in normal form if it has no tested Ifs: subexpressions of the form If (If (u, v, w), y, z). Replacing this by If (u, If (v, y, z), If (w, y, z)) preserves the value of the entire expression and removes one tested If. However new tested Ifs are created whenever v or w begin with If.
The following program, written in Standard ML [6], defines the data structure exp and the normalize function norm. If its argument is a tested If then norm replaces it as above and calls itself recursively. For any other argument norm makes recursive calls on the subexpressions. The ML code should fill in the details: It is far from obvious that norm terminates. In the If-If case it calls itself with a larger expression than it was given. One way of proving termination is to find a well-founded relation under which the argument 'goes down' in every recursive call [1,5]. Classically, a relation ≺ is well-founded if and only if it has no infinite descending chains · · · ≺ x 2 ≺ x 1 ≺ x 0 . The less-than relation < on the set N of natural numbers is well-founded. Less-than is not well-founded on certain other sets: for the integers, · · · < −2 < −1 < 0, and for the rationals, · · · < .01 < .1 < 1.
A common way of defining a well-founded relation on a set A uses a measure function f :

A proof using a measure function
In Boyer and Moore's logic all functions are total. Their theorem prover only accepts a recursive definition if it can show that the function terminates on all arguments. For this purpose it uses well-founded relations consisting of lexicographic combinations of inverse images. Boyer and Moore present a well-founded relation for norm involving two measures on expressions. Boyer has also sent me a simpler proof, credited to R. Shostak, using a single measure function: To show that this measure goes down in each of norm's recursive calls is a tedious exercise of expanding and collecting terms. It is important to check the easy If-At case, because a clever measure that goes down in the hard If-If case may not go down in the easy case. Note that m(x) is positive for all x.
and the original argument has measure Cancelling common terms, this case terminates because UY + UZ > 0.

A proof in the Logic of Computable Functions
Jacek Leszczy lowski [4] has proved the termination of norm using the theorem prover Edinburgh LCF [3]. LCF's logic, a formalization of domain theory, allows reasoning about partial functions. Leszczy lowski's proof uses a lemma that the termination of norm in particular cases implies termination in other cases. Each domain contains an 'undefined' element ⊥, representing the result of a divergent computation. There is a weak equality predicate ≡ such that x ≡ y iff x and y are both undefined, or both defined and equal. Since quantifiers often range over defined values only, let ∀ D x. P (x) abbreviate ∀x. x ≡ ⊥ ⇒ P (x). The statement 'norm is total' is expressed as ∀ D x.norm(x) ≡ ⊥. The domain of expressions is flat to avoid having infinite expressions [9]. The constructor functions At and If are total: This rule is often stated with the additional premise P (⊥). Then the conclusion is ∀x. P (x).
The function norm is expressed as three equations in LCF: The termination proof involves a lemma that if norm(y) and norm(z) terminate, then norm(If (x, y, z)) terminates.
which follows because If and At are total.
The If case reduces to showing assuming that u, v, w, y, z are all defined and with induction hypotheses for u, v, and w: Instantiate the induction hypothesis for u with y → If (v, y, z) and z → If (w, y, z), Q.E.D.
Termination of norm on all inputs follows by induction in ∀ D x.norm(x) ≡ ⊥.

Proving the recursion relation is well-founded
The first termination proof defines a well-founded relation using a measure function, and shows that norm's recursive calls obey that relation. A dual approach is to define a relation ≺ in terms of norm's recursive calls, then show that ≺ is wellfounded. Define x ≺ y to be true whenever evaluating norm(x) requires a recursive call norm(y), and to be false otherwise. (It should be false whenever possible, since additional relationships between elements could prevent ≺ from being well-founded.) I call ≺ the recursion relation of norm.
Case analysis of norm defines its recursion relation: To show the termination of norm it suffices to show that the relation ≺ is wellfounded. This proof will have a remarkable similarity to the LCF proof, which was conducted in domain theory. This section uses a simple mathematical framework with no partial elements. It uses constructive mathematics because this paper is an outgrowth of my study of well-founded relations [10] in Martin-Löf's Constructive Type Theory [8].
Showing that a relation is well-founded requires showing the soundness of its rule of well-founded induction for an arbitrary predicate P : In constructive reasoning, showing that ≺ has no infinite descending chains is insufficient to verify the rule. The rule is verified directly, proving its conclusion from its premise. For the rest of this section assume the induction step: Termination follows from proving ∀x.P (x); a lemma is helpful.
which follows from (1) and the definition of ≺. Recall that If (At(a), y, z) has only two predecessors, y and z.
By (1) it is enough to show Assume P (y) and P (z). The induction hypotheses for v and w imply P (If (v, y, z)) and P (If (w, y, z)). Instantiate the induction hypothesis for u with The previous proof can be translated into this one by replacing norm(x) ≡ ⊥ by P (x). Each unfolding of norm becomes an appeal to the induction step (1). Perhaps domains and partial objects are not essential even for difficult proofs of termination.
As a sample proof in his higher-order theory of constructions, Thierry Coquand has proved the termination of normalization [2] (pages 46-48). He defines a predicate N (x) to mean 'x can be put into normal form,' and proves ∀x. N (x). Translated from his formalism, the axioms are The connection between N (x) and norm(x) ≡ ⊥ is obvious. Coquand builds a proof object resembling my Constructive Type theory one, using a similar Lemma.

An obviously total normalize function
Constructive Type Theory provides a formal interpretation of propositions as types. One consequence is that every proof by induction involves constructing a proof object by recursion. My Type Theory proof that ≺ is well-founded suggests another way of writing the normalize function: normif (v, y, z), normif (w, y, z)); fun norm 1 (At(a)) = At(a) | norm 1 (If (x, y, z)) = normif (x, norm 1 (y), norm 1 (z)); The function normif is obviously total because it is structural recursive in its first argument, a sort of 'higher type' recursion. Although normif makes nested recursive calls in its second and third arguments, these have no effect on termination. (Ackermann's function is another example where termination is obvious despite nested recursive calls.) Note the similarity between normif's recursive calls and the appeals to the induction hypotheses in the proof of the lemma.
Proving in LCF that ∀ D x. norm(x) ≡ norm 1 (x) constitutes yet another termination proof for norm. Our familiar lemma now takes the form with essentially the same proof as before.
There is a pleasing concreteness about the first termination proof. But the measure function offers little intuition. The second and third proofs convey something of what norm is actually doing, for they give us the function normif.

A normalize function with nested recursion
If we modify the If-If case of norm to make nested recursive calls, proving termination becomes trickier still. Call the new function norm 2 : fun norm 2 (At(a)) = At(a) | norm 2 (If (At(a), y, z)) = If (At(a), norm 2 (y), norm 2 (z)) | norm 2 (If (If (u, v, w), y, z)) = norm 2 (If (u, norm 2 (If (v, y, z)), norm 2 (If (w, y, z)))); I sent this function as a challenge to Boyer and Moore. The version of the theorem prover described in their book [1] cannot handle this nested recursion. It could not admit norm 2 as a function unless, for some measure m 2 (x), it could prove m 2 (If (u, norm 2 (If (v, y, z)), norm 2 (If (w, y, z)))) < m 2 (If (If (u, v, w), y, z)) .

Yet this very statement involves norm 2 .
Moore informs me that the theorem prover has since been extended. A nested recursive function definition can be admitted by showing that it is equivalent to some already accepted definition. In this case replace norm 2 by norm in the recursion equations and show that the new equations hold. Thus they have at least one solution: norm. Then show that some measure decreases for each recursive call of norm in the new equations. Thus the solution is unique: by well-founded induction on the measure, norm(x) = norm 2 (x) for all x. Reasoning about norm is possible because it is already known to be a total function. Moore describes this principle of definition in his paper on the termination of Takeuchi's function [7].
Moore's proof of norm 2 has several stages: • norm(norm(x)) = norm(x) is proved by induction on the measure m(x). The result is used in the At case of the next stage.
• ∀yz. norm(If (x, norm(y), norm(z))) = norm (If (x, y, z)) is proved, like the Lemma, by structural induction on x. The theorem prover does not allow quantified induction schemes, but any instance of one can be specified.
• Therefore norm is a solution to the equations for norm 2 .
• A function to count the number of tested Ifs in an expression is defined. This differs from the function IF.DEPTH of the original proof [1], which counts the nesting of tested Ifs.
• norm(x) is indeed normal: it contains no tested Ifs. Proved by induction on m(x).
• The measure for proving uniqueness is the lexicographic combination of the number of tested Ifs and the size of an expression.

The LCF proof revisited
In domain theory the termination of norm 2 can be proved without any mention of norm. Termination and partial correctness must be proved simultaneously. Showing termination of the If-If case requires showing that the nested calls yield normal expressions. Define the predicate ISN (x) to hold whenever x is in normal form. ISN is a recursive predicate but the recursion is trivially well-founded: (If (u, v, w), y, z)) ⇐⇒ false The element ⊥ is not in normal form under this definition; ∀ D x.ISN (norm 2 (x)) states that norm 2 is a total function whose result is always normal. This is not a complete statement of correctness; it mentions no relationship between x and norm 2 (x).
The proof resembles that of section 3, replacing each occurrence of norm(x) ≡ ⊥ by ISN (norm 2 (x)). Fact. If the argument of norm 2 is normal then so is its result: Proof. By structural induction on x. The ⊥ and At cases are easy. For If consider two cases. Since If (If (u, v, w), y, z) is not normal the result holds vacuously. The If (At(a), y, z) case is (At(a), y, z))) which simplifies to which follows from the induction hypotheses. Now we have the usual Lemma. ∀ D xyz. ISN (norm 2 (y)) ∧ ISN (norm 2 (z)) ⇒ ISN (norm 2 (If (x, y, z))) Proof. By structural induction on x. The At case reduces to the clearly true The If case reduces to showing, under induction hypotheses, ISN (norm 2 (y)) ∧ ISN (norm 2 (z)) ⇒ ISN (norm 2 (If (u, If (v, y, z), If (w, y, z)))) .
Again the overall proof for norm 2 is an easy induction using the Lemma. Proving ∀ D x.ISN (norm 2 (x)) rather than ∀ D x.norm 2 (x) ≡ ⊥ is a classic example of strengthening the goal in order to strengthen the induction hypotheses. The Lemma is essentially the inductive step. Its proof requires the Fact (2). Proving ∀ D x.norm 2 (x) ≡ ⊥ would require a Lemma of the form ∀ D xyz. norm 2 (y) ≡ ⊥ ∧ norm 2 (z) ≡ ⊥ ⇒ norm 2 (If (x, y, z)) ≡ ⊥ and a Fact of the form ∀x.x ≡ ⊥ ⇒ norm 2 (x) ≡ ⊥. We are going in circles! It would suffice to prove a weaker version of the Fact: An attempted proof of this resembles that of (2) except that the If-If case is no longer trivial.

The recursion relation proof revisited
The recursion relation proof of section 4 can similarly be adapted to norm 2 . I continue to use the predicate ISN for reasoning about normal expressions, though in this section there is no element ⊥. The recursion relation ≺ 2 is defined like ≺, except that the If-If case has three recursive calls instead of one. The outer call involves the results of the inner calls, expressed as existentially quantified variables. The results are assumed to be in normal form: ⇐⇒ false It will be necessary to show inductively that the equations for norm 2 produce normal expressions. First let us show that ≺ 2 is well-founded. Assume the induction step for an arbitrary P : Fact. The induction step (3) implies P (x) for all x in normal form. The Lemma is stated just like in section 4: Lemma. ∀xyz. P (y) ∧ P (z) ⇒ P (If (x, y, z)) Proof. By structural induction on x. The At case is proved as before. The If case is ∀yz. P (y) ∧ P (z) ⇒ P (If (If (u, v, w), y, z)) .
By (3) it is enough to show that P (y) and P (z) imply each of The induction hypotheses for v and w imply P (If (v, y, z)) and P (If (w, y, z)). It suffices to show P (If (u, v , w )) for arbitrary normal expressions v and w . The Fact (4) implies P (v ) and P (w ). Instantiate the induction hypothesis for u with y → v and z → w . Q.E.D.
The translation from the domain theory proof replaces ISN (norm 2 (x)) by P (x). The connection between the proofs is weaker that it was for norm. Domain theory allows explicit mention of norm 2 's recursive calls when instantiating u's induction hypothesis; the recursion relation hides the calls via quantifiers.
The justification of norm 2 still requires simultaneous proofs that it terminates yielding a normal expression. The proof is by well-founded induction on ≺ 2 : • Given At(a) it makes no recursive calls and returns an atom, which is always normal.
• Given If (At(a), y, z) it makes recursive calls on the predecessors y and z. By induction hypotheses these calls return normal expressions so the final result is normal.
• Given If (If (u, v, w), y, z) it makes recursive calls on predecessors If (v, y, z) and If (w, y, z). By induction hypotheses these return normal expressions v and w . So If (u, v , w ) is a predecessor, justifying the final recursive call. By induction hypothesis this returns a normal expression.
This reasoning about the various cases of norm 2 can be formalized in my setting of well-founded recursion operators in Constructive Type Theory [10]. A function application has type y∈exp ISN (y). It returns a pair of results: a normal expression y and a proof object of type ISN (y). Each recursive call on an argument z must be justified by exhibiting a proof object of type z ≺ 2 x. This is passed as an additional argument. In the If-If case, the outer call passes a proof object for If (u, v , w ) ≺ 2 If (If (u, v, w), y, z), constructed from proof objects ISN (u ) and ISN (v ) from the inner calls.
After performing this elaborate construction of a well-founded recursion, the equations for norm 2 can be proved as usual in the approach [10].

Conclusions
Domain theory allows reasoning about recursion in a most flexible way, but at a heavy cost of complexity. The ideas can be difficult to grasp and introduce theoretical and practical obstacles. LCF is the only major theorem proving project that uses domain theory; even LCF users sometimes prefer to do without domains. The recursion relation proofs of norm and norm 2 suggest that domains are not essential for reasoning about many programs. Domain theory still has a vital role to play: there is no alternative for reasoning about compilers and continuously running processes.
Constructive Type Theory is concerned with terminating computations. Domain theory cannot be patched onto it; partial functions are completely antithetical to its view of computation. Using recursion relations it can express termination proofs of norm and norm 2 , thereby deriving the function normif.
It is especially hard to prove the termination of functions involving nested recursion, since the termination of an outer recursive call may depend on a property of the results of the inner calls. The example norm 2 shows that this can be done without domains. Manna and Waldinger have studied a much more interesting nested recursive function, UNIFY, which performs unification [5]. They define a well-founded relation involving the structure of the expressions being unified and the number of distinct variables in those expressions. Under this relation, UNIFY's outer recursive call can be justified only if its inner call returns a most-general, idempotent unifier of its arguments.
I formalized their work using the theorem prover Cambridge LCF, proving the total correctness of UNIFY [12]. The proof used a predicate BEST UNIFY TRY in a role analogous to that of ISN in the proof of norm 2 : to allow the simultaneous proof of termination and correctness. It appears possible to verify UNIFY in Constructive Type Theory. Manna and Waldinger's well-founded relation is appropriate; there is no need to consider the recursion relation. UNIFY would return a substitution paired with a proof that this substitution had the necessary properties.
An axiom, previously created by struct axm, is bound to the ML identifier EXP DEFINED. The structural induction tactic is instantiated to handle expressions and bound to the ML identifier EXP TAC. The Lemma is proved by induction followed by rewriting via the equations for norm and the totality of the constructors At and If. I have tweaked the statement of the Lemma to circumvent an annoyance involving admissibility of induction [3]. The proof that norm is total resembles the proof of the Lemma.


extfieldsofstudy:
Computer Science
Physics
Mathematics

text:
Quantum error-correcting codes associated with graphs

We present a construction scheme for quantum error correcting codes. The basic ingredients are a graph and a finite abelian group, from which the code can explicitly be obtained. We prove necessary and sufficient conditions for the graph such that the resulting code corrects a certain number of errors. This allows a simple verification of the 1-error correcting property of fivefold codes in any dimension. As new examples we construct a large class of codes saturating the singleton bound, as well as a tenfold code detecting 3 errors.

I. INTRODUCTION
From the beginning of Quantum Information Theory it was recognized that error correcting codes play a crucial role. On the one hand it was clear that without error correction decoherence effects could easily annihilate the gain in computing time promised by the new fast quantum algorithms. On the other hand, the no-cloning theorem [1] seemed to forbid at least the most naive approach to classical error correction for noisy channels, e.g., sending each bit three times and taking a majority vote at the output of the channel. Clearly, this simple scheme reduces classical errors with small probability of order ε to order ε 2 . The cloning required for sending "the same bit" three times rules out direct quantum analogues of this scheme. It was therefore an important step to realize [2] that quantum mechanics had other, more subtle ways of "distributing" quantum information over several channels to stabilize against errors. One problem with the known schemes of quantum error correction (e.g. [3,4]), however, is that they tend to be subtle indeed, and the verification of their error correcting capabilities often requires a lengthy computation. It is therefore desirable to find new, perhaps simpler ways of constructing error correcting codes, on which more direct intuitions might be built.
In this paper we propose a new scheme for constructing quantum error correcting codes, which has some of these advantages. The ingredients of our construction are a graph and a finite abelian group. The order of the group determines the type of systems for which errors are corrected so that, e.g., the two-element group corresponds to the qubit case (Compare [5][6][7][8] for other constructions of non-binary codes). The number of vertices of the graph determines how many input systems are coded into how many output systems. From the edges of the graph one can then read off an explicit expression for the code. However, not every graph corresponds to a good code, and we will discuss the condition for the code to correct a certain number of errors. In the simplest case, the fivefold code [9][10][11] (for qubits as well as higher dimensional systems), it can be verified in a few lines that any two errors are corrected. We also give an example of a more complex tenfold code detecting 3 errors.
As we are going to discuss in a following paper in more detail, it turns out that the codes which can be achieved by our method are stabilizer codes. There are various efficient methods for constructing stabilizer codes [3,4,[12][13][14][15][16]. However, we think that, compared to previous stabilizer constructions, our technique has some interesting new features.
• Often the condition for error correction can be proved for many groups simultaneously, so that one gets code families for systems of variable sizes.
• The geometric intuitions about graphs may become helpful for finding new constructions.
• Our codes have the property that in their natural basis all matrix elements of the coding operator have the same modulus (Hadamard form). This is prima facie opposite to the usual goal of getting as few non-zero matrix elements as possible. However, the latter can be achieved for our codes by a discrete Fourier transform applied to some channels. Moreover, the Hadamard form appears to be an interesting normal form for the codes which can be written in both ways.
• For some codes it is possible to exchange some input vertices with some output vertices, while retaining the error correction property. This kind of symmetry is much harder to see in the usual stabilizer constructions, and may prove to be helpful in coding problems with additional inputs and outputs, such as the internal state of the codig device in convolutional codes.
The paper is organized as follows: We begin by describing the general construction of the coding operator within Section II. In Section III we recapitulate the Knill-Laflamme condition for error correction and adapt it to our particular type of codes, resulting in a necessary and sufficient condition for a graph to generate a quantum error detecting code. The remaining sections contain examples of codes constructed in this way. In Section IV we show that it becomes simple indeed to verify the fivefold quantum codes. In Section V we demonstrate that for a given number e of errors and number k of inputs, there is a graph generating an infinite code family using 4e + k output systems, i.e., a family of codes saturating the singleton bound. Finally, in Section VI we construct a code with 1 input and 10 outputs, detecting 3 errors for arbitrary system size.

II. BASIC CONSTRUCTION
Every code we construct is completely determined by the follow ingredients: • An undirected graph Γ with two kinds of vertices.
We distinguish the set X of input vertices and the set Y of output vertices. The links of the graph are given by the coincidence matrix of the graph, which we will denote by Γ for short. Its matrix element Γ(z 1 , z 2 ) is 1 iff the vertices z 1 , z 2 ∈ (X ∪ Y ) are linked, and 0 otherwise. More generally, we allow weighted graphs, whose incidence matrices have arbitrary integer entries, apart from the constraints Γ(z 1 , z 2 ) = Γ(z 2 , z 1 ) and Γ(z, z) = 0.
• A finite abelian group G with a non-degenerate symmetric bicharacter.
By definition, a bicharacter is a function χ : G × G → C such that χ(g + h, g ′ ) = χ(g, g ′ )χ(h, g ′ ) and a similar condition holds for the second argument, which is also implied by the assumed symmetry χ(g, g ′ ) = χ(g ′ , g).
We also assume non-degeneracy in the sense that g χ(g, g ′ ) = |G| δ(g ′ ) ≡ |G| for g ′ = 0 0 for g ′ = 0 (1) Note that since every g ∈ G has finite order, χ(g, g ′ ) is always a root of unity, and χ(g, g ′ ) = χ(−g, g ′ ). For G = Z p , the cyclic group of order p, the standard bicharacter is given by where g, h are integers representing their class modulo p. Since every finite abelian group is a direct product of cyclic groups, this also shows the existence of bicharacters for any such group. The input and output systems of the code are labeled by X and Y . They are all of the same type, i.e., they are described by the same Hilbert space H = L 2 (G). This is the space of all functions ψ : G → C with scalar product φ, ψ = |G| −1 g φ(g)ψ(g). For compactness of notation we write such normalized sums as integrals. Hence the scalar product becomes dg φ(g)ψ(g). The combined input system is thus described in the |X|-fold tensor product H ⊗X = L 2 (G X ). Vectors in this space are functions of |X| variables, one variable g z for every z ∈ X. The entire collection of variables will be denoted by g X . The error correcting code will be an isometry where v Γ under the integral denotes the integral kernel of the operator v Γ . This kernel depends on both input and output variables, which are combined into a collection of variables g z , one for each vertex z ∈ X ∪ Y of the graph. The core of our construction is an explicit expression for this integral kernel: apart from an overall normalization factor, it will simply be a product of phases, with each factor corresponding to a link of the graph: where the product is over all 2 element subsets {z, z ′ } ⊂ (X ∪ Y ). Thus for an ordinary graph (Γ(z, z ′ ) = 0, 1), this is the product of all χ(g z , g z ′ ), for which z and z ′ are linked. The remarkable property of such codes is that apart from the normalization factor the kernel is everywhere of modulus 1. When G = Z p is cyclic, and χ is given by Equation (2), we can write the phase in more compact form as where "·" denotes the product of integer valued matrices and vectors. Note that every term in the sum g X∪Y · Γ · g X∪Y occurs twice, which we compensated by a factor 1/2. This completes the construction of the operator v from the defining ingredients listed at the beginning of this section. Of course, in general this will not be an error correcting code nor even an isometry. The conditions for this will be studied in the following section.

III. THE CONDITION FOR ERROR CORRECTION
A general characterization of quantum error-correcting codes has first been worked out by E. Knill and R. Laflamme [17]. We briefly review here the main aspects, and adapt the condition the particular case of codes constructed as in the previous section. In this theory a quantum code is an isometry v : H → K from the "input Hilbert space" H to the "output Hilbert space" K. Thus an input density operator is transformed by coding into vρv * , which is a density operator on K. The output of the coding is then passed through a noisy channel. The noise is described by a certain class of errors, which are represented by a linear subspace E of operators on K.
The channel is thus represented by a completely positive linear map of the form where F α ∈ E. and are chosen such that the output is always normalized. The isometry v is said to be an error correcting code for E, if there is a completely positive "recovery operator" R such that for all density operators on H. By the theory of Knill and Laflamme [17] this is equivalent to the factorization condition where ω(F α , F β ) is a factor independent of the arbitrary vectors ψ 1 , ψ 2 . As in much of the literature on codes we will consider here a specific type of errors, namely errors happening only on a small number of outputs of the code. Thus the tensor product structure , which are the tensor product of an arbitrary operator on H ⊗E with the identity on H ⊗Y \E . We say that a code corrects e errors, if F α , F β in (9) may be chosen arbitrarily in the linear span of |E|≤e A(E). Note that the operators F * α F β appearing in the scalar product (9) can then be localized on arbitrary sets of 2e elements and any operator with such localization may be written as a linear combination of such F * α F β . It is therefore convenient to introduce the following terminology: we say that the code v detects the error configuration E ⊂ Y , if for all F ∈ A(E). Then a code corrects e errors, iff it detects all error configurations E ⊂ Y with |E| ≤ 2e.
We will now adapt these conditions to operators v Γ of the special form (3). Consider a fixed error configuration E ⊂ Y , and let This must be a multiple of the identity for every choice of F . Choosing, in particular, a rank one operator F = |g E h E | we find that error detection for the configuration E is equivalent to the property that the correlation function factorizes in the following manner where δ(g X ) is defined to be 1 if g x = 0 for all x ∈ X, and zero otherwise, and C(g E , h E ) is a factor independent of the input variables g X , h X . For two subsets K, L of X ∪ Y we denote by Γ K L the group homomorphism from G L to G K which can be derived from the corresponding submatrix of the incidence matrix Γ by the prescription and the following condition is necessary and sufficient for quantum error detection: Theorem III.1 Given a finite abelian group G and a weighted graph Γ as in the basic construction. Then an error configuration E ⊂ Y is detected by the quantum code v Γ iff the system of equations The proof of Theorem III.1 is given in Appendix A and, in view of this result, we discuss some examples.

IV. EXAMPLE: THE FIVEFOLD WAY
The first example of an optimal quantum error correcting code correcting all one bit errors was the famous five qubit code by [10]. The original code is not easy to verify, so it is gratifying to see that our construction produces such a code, which can be verified in a few lines. Moreover, our construction works simultaneously for all groups G, and is hence not restricted to qubits. Fivefold codes for higher dimensional systems have been constructed before [11], and if we believe a recent result by Rains [18], the qubit code is essentially unique anyway. Hence this section has mainly illustrative character.
Consider the graph in Figure 1 where the central vertex "0" is the input vertex, and the remaining five are the output vertices. We will verify the condition of Theorem III.1 in a particularly strong form. Namely we will show that, for every 2-element error configuration E, The error configuration is a 2-element subset of the output vertices 1, ..., 4, and for the purpose of verifying criterion (17) the input vertex 0 plays exactly the same role as an error. It is clear by symmetry that only the two configurations for X ∪E shown by filled dots in Figure 1 need to be considered. Now the condition Γ I X∪E d X∪E = 0 is a set of equations, one for each "integration vertex" y ∈ I: For each vertex y we have to sum the d x for all vertices of x ∈ X ∪ E connected to y, and equate to zero. (In a weighted graph, we would have to sum with coefficients given by the matrix Γ). The following is a table of equations arising in this way for the first error configuration, X ∪ E = {0, 1, 2}: Clearly, this implies d 0 = d 1 = d 2 = 0 in any abelian group. Similarly, for the second error configuration X ∪ E = {0, 1, 3}we get the equations Vertex y Equation which once again implies d 0 = d 1 = d 2 = 0. This concludes the verification that the code associated with the graph in Figure 1, and an arbitrary finite abelian group G, detects any two errors, hence corrects one error. In fact, we proved a little bit more than that. The essential part of the proof was to look at certain 3 × 3submatrices of the 6 × 6-matrix Γ, namely those corresponding to an off-diagonal block in the partition of the vertices {0, 1, . . . , 5} into two disjoint subsets X ∪ E and I, and to show that each such submatrix is non-singular. Regarded in this way, it becomes irrelevant to which of the two sets in the partition the input vertex "0" belongs, so we showed that any vertex, even a peripheral one, may be taken as input vertex, and we still get a 1-error correcting code.
This may seem like a rather strong property of the graph we chose. However, there is (exactly) one other graph with six vertices, which produces in the same way a 1-error correcting code for arbitrary choice of input vertex and abelian group G. This is shown in Figure2.

V. CODES SATURATING THE SINGLETON BOUND
In this Section we briefly discuss one natural generalization of the idea emerging in the previous section. For definiteness, let us fix G as a cyclic group of prime order d, so Z d is a field, and choose an integer m. We then ask for symmetric 2m × 2m-matrices Γ with integer entries (or, equivalently, entries in Z d ) with the following property: for any m-element subset I ⊂ {1, . . . , 2m} the m × m-submatrix Γ ij with i ∈ I, j / ∈ I is invertible in the field Z d . For the purpose of this section, let us call such a matrix strongly error correcting for the prime number d.
What codes can we get from such matrices? Just as in the previous section, let us specify any set X of k < m vertices as input vertices, and call the remaining n = (2m−k) ones output vertices. Then for any configuration of e = m − k errors, the set X ∪ E and its complement I will have exactly m elements. By assumption, the strong form of the error correcting condition (17) is satisfied, hence the code detects e errors. These parameters satisfy n = 2e + k , (18) i.e., the general inequality n ≤ 2e + k, known as the singleton bound [17] is satisfied with equality for any such code.
How can one get strongly error correcting matrices Γ in a practical way? Here is a procedure, we found easy to work with for small m, using a symbolic algebra program. First, we introduce variables for each matrix element Γ ij with i > j, and compute the determinants of all offdiagonal m × m-submatrices as symbolic expressions in these variables. As we go along fixing integer values for these Γ ij , the determinant expressions become simpler, and in some cases factorize. Each of these factors has to be kept non-zero by the next choice of a Γ ij -value. Finally, we end up with an integer matrix, whose offdiagonal m × m-submatrices all have non-zero integer determinant. Then, for any prime d, which does not divide any of these integers, we have solved the problem.
It is natural to begin this process by setting as many weights as possible equal to zero. It is easy to see that Theorem III.1 does not allow too many Γ(k, l) = 0 because an entire row of zeros in the matrix Γ I X∪E leaves one of the difference variables unconstrained. Similarly, in the condition for strong error correction it is clear that no off-diagonal submatrix should have a row of zeros, i.e., each one of the 2m vertices must be connected to at least m other vertices. The graph in Figure 3 is as sparse as possible under these constraints (m = 4), and was the starting point for a search for non-zero weights, as described above, resulting in the matrix This matrix can either be used to get codes detecting three errors on an arbitrarily chosen single input vertex, or as a code detecting two errors (or correcting 1) on two arbitrarily chosen inputs. The set of determinants is {−11, −8, −5, −4, −2, −1, 1, 2, 4, 5, 8, 9}, so this will work for any prime d not in in the set {2, 3, 5, 11}. By fixing the choice of the input vertices, we may restrict to a smaller set of partitions (the input vertices always belong to the same set), hence we get fewer constraints. For example, the code with input vertices {1, 2} has no relevant subdeterminant containing a factor 3, so the resulting code corrects one error on arbitrary pairs of 3-level systems.
Within the above example, the number of matrix elements set to zero is maximal, namely ν i = 4 for each row i = 1, · · · , 8. Looking at the corresponding graph, ν i = 4 is just the number of lines meeting a particular vertex as one can see from Figure 3. Strongly error correcting matrices exist in any dimension, so the code parameters saturating the singleton bound (18) can be chosen arbitrarily, if the dimension d of the one-site system is taken to avoid a certain finite set of primes (Compare also [5]). The argument is quite simple: consider the m × m-subdeterminants of symmetric 2m × 2m-matrices as a family of polynomials f α , α = 1, · · · , 2n n in 2n 2 variables. None of these vanishes identically and since Z is an integral domain, which in contrast is wrong for finite fields, the product polynomial α f α = 0 is non zero [19, p. 106]. This implies that there exists an integer tuple Γ of arguments that α f α (Γ) = 0. Thus we have shown the following statement: Proposition V.1 For each number e of errors, there exists a prime d and a weighted graph Γ such that the quantum code, associated with the weighted graph Γ, is a quantum error correcting code, which encodes k d-level systems into 4e + k p-level systems, and which corrects e errors.

VI. A 10-FOLD QUANTUM ERROR-DETECTING CODE
In this section we present more complex example for a graph, which yields for every finite abelian group G a 10-bit code, detecting 3 errors is given by Figure 4. At the first look, this graph looks rather complicated, but it can be described in a simple fashion, by looking at the graph for the fivefold code in Figure 1. Namely, the graph, given by Figure 4, can be obtained as follows: The output vertices {1, 2, 3, 4, 5} of the graph in Figure 1 are replaced by pairs: 1 → {1, 2}, 2 → {3, 4}, . . . , 5 → {9, 10}. Each output vertex is connected with the following vertices: The central input vertex 0, the vertex belonging the same pair, and all output vertices belonging to neighbored pairs.
The symmetry of this graph can efficiently be used to check that each error configuration with 3 errors can be detected. As it is depicted by Figure 5, there are only four 3-error configurations to distinguish: Proposition VI.1 For each finite abelian group G, the quantum code, which is associated with the graph given by Figure 5, is a quantum error-detecting code, encoding 1 input system into 10 output systems and detecting 3 errors.
Proof: Suppose that each error occurs in different pairs and all these pairs are neighbored (first graph in Figure  5), e.g. the error configuration {1, 3, 5}. Then we proceed as in the example for the fivefold code to obtain the system of equation (15): Analogously, one checks that each error configuration, where each error occurs in a different pair and only two of these pairs are neighbored (second graph in Figure 5) is also detected.
We now consider an error configuration, where one pair {1, 2} is totally corrupted and the remaining error vertex, e.g. 5, is contained within a non-neighbored pair (third graph in Figure 5). We obtain for the system of equations (15): and we conclude again that d 0 = 0 and d 1 + d 2 + d 5 = 0 is true. The equations (16) are fulfilled which implies that the corresponding error configuration is also detected. Finally, it is a bit more straightforward as in the previous case to show that an error configuration, where two errors occur within one pair and the remaining error within a neighbored pair (4th graph in Figure 5) is detected.

VII. CONCLUSION AND OUTLOOK
In this paper we had to limit the exploration of our construction scheme to a few examples. A more systematic investigation is, of course, under way. Some of the issues in this investigation are the following.
• We already mentioned that all codes constructed from graphs are stabilizer codes. This is verified by explicitly constructing a group of unitaries, composed out of shifts and multiplication by characters, leaving all vectors in the code space invariant. The converse of this statement is not so clear, i.e., how to embed the usual stabilizer code constructions into our scheme, and to characterize the subset of codes for which this is possible.
• We have seen in Sec. IV that different graphs generate 5-qubit codes, although such codes are presumably unique up to local transformations. It would be helpful to characterize the local unitary transformations taking one graph code into another, and to study the relationships between the resulting graphs. The Rains invariants [20][21][22] for graph codes can be computed relatively easily, and should help to decide such isomorphism issues.
• From Sec. V it is clear that the singleton bound becomes easier and easier to satisfy as the dimension d of the single system Hilbert space increases. This suggests the search for bounds describing the resource limitations in coding more adequately, perhaps by taking into account more detailed features of the error syndromes than just the maximal number of errors. Our construction could be helpful for developing and testing such bounds.
• Non-stabilizer quantum codes can be constructed from families of stabilizer codes by taking their union [23], where one has to require that the protected subspaces, corresponding to the codes within the family, are mutually orthogonal and that this property remains valid after error operations. Examples of such non-stabilizer codes are given in [24,25]. In view of our construction scheme, it would be desirable to find sufficient conditions for a family of graphs such that the union of their corresponding graph codes yields a (possibly more efficient) non-stabilizer code.
From now on we assume, as we may, that Γ I X∪E (d X∪E ) = 0 implies d X = 0. Then the dependence of (A6) on the input variables g X and h X can be simplified. The δ-function can be written as because the two expressions are equal for h X = g X , and for h X = g X they both vanish by assumption.
To simplify the bicharacter quotient in (A6), we use Eq. (A1) to write With a similar decomposition of χ Γ (g X∪E , g X∪E ) we use the condition that, wherever the δ-function in (A6) is non-zero, we have g X = h X . Hence the X − X factors cancel, and we can write the quotient of the X − E-terms as For (A6) to be of the desired form (A7) with C(g E , h E ) independent of the X-variables, this expression must be independent of all h j , j ∈ X, whenever δ Γ I E (h E − g E ) = 0. But (A10) is independent of h j if and only if i Γ ji (h i − g i ) = 0. Hence we must have that Γ I E (h E − g E ) = 0 implies Γ X E (h E − g E ) = 0. This is the second condition from Theorem III.1, which we have thus shown to be necessary. Conversely, it is sufficient to ensure that (A10) is equal to 1, and (A6) has the desired form (A7) with This concludes the proof.


Stripes ordering in self-stratification experiments of binary and ternary granular mixtures

The self-stratification of binary and ternary granular mixtures has been experimentally investigated. Ternary mixtures lead to a particular ordering of the strates which was not accounted for in former explanations. Bouncing grains are found to have an important effect on strate formation. A complementary mechanism for self-stratification of binary and ternary granular mixtures is proposed.

The self-stratification of binary and ternary granular mixtures has been experimentally investigated. Ternary mixtures lead to a particular ordering of the strates which was not accounted for in former explanations. Bouncing grains are found to have an important effect on strate formation. A complementary mechanism for self-stratification of binary and ternary granular mixtures is proposed. 45.70.Mg,81.05.Rm,64.75.+g A recent experiment which has received much attention [1] from the scientific community is the following. When a binary mixture of grains differing in size is poured between two vertical slabs, there is a global tendency for large and small grains to segregate in different regions of the pile [1,2]. Additionally, a self-stratification of the mixture in alternating layers of small and large grains is observed if large grains have a larger angle of repose than the small ones. It has been also shown [3] that the phase segregation takes also place when grains of same size but with different shapes are mixed together. Strates might also appear in those conditions [4].
For describing the self-stratification phenomenon, both continuous [5,6] and discrete models [6][7][8] have been proposed up to now for binary mixtures. These models are able to reproduce the alternating layers of the different granular species. The more elaborated models consider phenomenological continuous equations which account mainly for the angles of repose of the various species, the percolation of grains in the rolling phase, and the kink formation on the pile surface. A challenge for physicists is the generalization of both experiments and models to the case of a continuous distribution of grain sizes.
The first motivation of the present work was the experimental investigation of ternary mixtures which did not receive much attention in earlier works. As described below, the structures of the phase segregations in ternary mixtures raise new questions about the self-stratification mechanisms.
A vertical Hele-Shaw (HS) cell was specially built for our purpose. The distance e separating the vertical planes of the HS could be continuously adjusted. Various granular species have been used: sand, wheat semolina, poppy seeds, Fe filings. We controlled the granulometry of each species by a preliminary sifting. Important properties of each type of grains are given in Table I. Granular mixtures contained an equal volume of each species. They were poured in the HS cell with a funnel. A CCD camera with a lens 12/120mm F5.6 was placed perpendicular to the HS cell for examining the physical processes involved at the grain scale. Top views have also been taken. They allowed us to observe the dynamics and composition of the upper surface during the flow. Precise video imaging is necessary for studying the evolution of granular piles. Our results are reproducible.
First, let us consider the case of ternary mixtures being composed of small (S), medium (M ) and large (L) grains. Fig.1 presents three pictures of ternary piles in the HS cell. Two different mixtures were used. In each case, size segregation is clearly observed. Indeed, small grains have a global tendency to locate in the center of the pile while large grains are located in the tail. The medium-sized grains are dispersed in between the center and the tail. In addition, the self-stratification phenomenon is present. Three different patterns are obtained. In the first pile, a ...SM LSM LSM L... ordering is displayed as found in [1]. The second pile is characterised by a ...SM LM SM LM... ordering. The third pile is quite similar to the first, as far as wide stripes are concerned. However, the ordering seems to be more complex, especially in the tail: a thin stripe of small grains is visible in the center of wide stripes made of large grains. These different orderings require special attention and the presence of the thin stripe cannot be explained with conventional models for selfstratification. Another important observation is that for some mixtures, a difference in inclinaison angle appears between the different stripes ( Fig.1b). This difference of stripe angles, the particular ordering and the occurrence of a thin additional stripe indicates that quite different mechanisms are present during the heap formation.
In the case of binary mixtures, Koeppe et al.
[9] have reported some anomalous stripe pattern that they called "pairing". Indeed, stripes of the same grains seemed to be formed by pairs in particular experimental conditions. We made careful experiments with binary mixtures and we observed again the above-mentioned thin stripes (see Fig.2). We suggest that thin stripes can be at the origin of the previously reported "pairing". Similarily to ternary mixtures, the successive stripes may have different angles.
Self-stratification for binary mixtures of grains differing in size has been explained [1,10] by the combination of two main processes. They are illustrated in Fig.3. The first process is the size segregation mechanism. There is a global tendency of large grains to roll farther downhill than the small ones due to their larger mass/inertia. This effect is strongly increased by the percolation of small grains through the gap between large grains in the flow. Large grains will be on the top of small grains, in the upper part of the moving layer. Small grains form a relatively smooth surface, on which large grains roll easily. Thus the moving layer is characterized by a strong velocity gradient such that the upper large grains are the fastest. As a result, large grains also locate in the front of the avalanche while small grains are confined in the lower part of the tail of the moving layer. Large grains will travel farther than small grains. The second process coming into play is the so-called kink mechanism. When the head of an avalanche reaches the end of the pile, grains will stop moving due to the horizontal slope of the basis. If the flux is not too important down the slope, grains in the tail of the avalanche will come to rest on the wall just formed by preceding grains. This wall is the kink and it moves up the slope as more grains arrive on it. This process is similar to the formation and backing of traffic jams. A pair of layers is formed through the kink mechanism with the small grains in the lower layer and the large grains in the top layer, starting at the basis of the pile. Since small grains were located in the tail of the avalanche, the wide stripe of small grains does not extend to the basis of the pile. The resulting surface involves an efficient capture for small grains during the next avalanche.
This explanation can be extended to ternary mixtures.
It accounts for patterns in Fig.1ab. The ...SM LM SM LM... ordering reflects the dynamics and composition of the lower layer of the avalanche: large grains in the head, followed by medium sized grains, themselves followed by small grains.
So when an avalanche flow down on top of the surface formed by the preceeding kink, after the head of large grains has passed, medium grains will pass and some will be captured before small grains pass. A very close examination of the heap displayed in Fig.1a reveals that there are indeed some medium sized grains caught below the stripes of small grains in the lower part of the heap. On the other hand, in the upper part of the heap, the ...SM LSM LSM L... ordering is visible because there was not enough time for medium grains to move in front of small grains in the lower part of the moving layer. Thus, small grains were the first to be captured during the avalanche in the upper part of the pile. These dynamical processes depend strongly on the incoming flux of grains and the relative velocities of different granular species. However, the above mechanism for self-stratification cannot explain the thin layers of small grains observed in Fig.1c and in Fig.2.
The complementary mechanism we propose is illustrated in Fig.3. Considering again a binary mixture, the first steps are identical to previous explanation. The kink, however, does not catch all moving grains. Indeed, in any granular flow, various transport mechanisms take place. From bottom to top in the moving layer, one en-counters: combined movement of grains, motion of individual grains with friction and collisions, and above the rolling-slipping phase, a layer with boucing grains. Typically, the thickness of the rolling-slipping phase is about five to ten large grain diameters in our mixtures. The bouncing grains layer is characterised by a higher velocity and a much smaller density. Indeed grains does not touch each other permanently like in the rolling-slipping phase. We found that bouncing grains can jump as far as 2 cm and then rebounce or be captured. We stress that most bouncing grains found at the bottom of the pile have bounce all their way down. Both kinds of grains can bounce. The efficiency of this mechanism depends on resilience of the grains. We observed that a non-negligible amount of those bouncing grains can flow down the slope over the kink (see Fig.4). We stress that bouncing grains are those involved in the formation of the additional thin stripe observed in the center of the wide stripe made of large grains. Fig.5 shows also the evolution of a binary pile. The first picture was taken as the kink was moving up. The thickness of the kink is about the same that the thickness of the rolling layer. As a consequence, the kink moves fast upward. The second picture shows the pile just after the kink has passed. The third picture was taken just before the next avalanche comes down, and the last picture shows the pile as the avalanche is flowing.
It is clearly visible that the thin stripe of small grains appears mainly during the time interval separating pictures b and d, that is between the passage of the kink and the next avalanche. In addition, a close examination shows that this thin stripe is composed of both kinds of grains, in opposition to wider stripes where the granular species are quasi-pure. In the case of pile 1c, close look reveals that small, medium and large sized grains are involved in the thin stripes.
The reason these strates are thiner is that there are much less grains involved -only those that are not immediatelly stopped by the kink. When a small boucing grain is captured by the pile, it will fall through the gaps left by the large grains forming the static surface. This is why the stripes are formed of both kinds of grains. This also explains the fact that the thin stripe is observed to form below the static surface, about one large grain deep. Thin stripes have the same inclinaison angle as the surface left by the kink. The difference in angle for thin stripes and wide stripes is observed in Figure 2b (∆θ ≈ 3 • ). It indicates that the kink builds at a greater angle than the angle of the avalanche (avalanches erode mainly the upper part of the pile). This can be related to another observation we made when pouring granular materials through the funnel. We noticed that the jamming limit diameter was lower in the case of mixture made of large and small grains than in the case of large grains only. Thus the presence of small grains seems to reduce the arching properties of large grains. We do not know if this is a general feature.
Several causes can inhibe or hide the phenomena of thin stripe formation. In the case of Fig.1 a and c, the only difference is the funnel used for pouring the grains. As a consequence, not only the flux of grains was lower in the case of pile a but also, and this is related, the initial velocity of grains seemed to be lower in a. The main effect is a lowering of the number of bouncing grains. The kink may become perfectly efficient, i.e. it may completely stop all moving grains it encounters. Then the thin layer will not form. Indeed we observed no boucing grains flowing over the kink during heap formation of a. Next, if the avalanches are important, they can erase by erosion the very thin layer that forms the top of the pile. All the mixtures we used are characterised by a large aspect ratio (> 2, up to 10) and by a larger density for small grains. Koeppe et al.
[9] used a mixture of sand and sugar that corresponds to these characteristics when they obtained their "pairing". The difference in size causes percolation to be efficient and might favorise an important velocity gradient in the moving layer. These make self-stratification particularly pronounced. High velocity in the top of the rolling-slipping layer favorise the transport of bouncing grains. The large density of small grains allows them to bounce as far as large grains do. Indeed, in the case of grains all of the same density, small grains are much lighter than large grains. They would have much less kinetic energy and so they would travel less far than large grains.
The number of grains involved in the thin stripe, depending on the position along the slope, could be computed from the time interval between the passage of the kink and next avalanche, and the number of bouncing grains at that point, given that one knows the probability of capture by unit lenght for those grains by the pile. We observed that the thin stripe of small grains do not always presents the same profile, in particular, for some mixtures with narrower density difference between small and large grains, thin stripes do not extend to the basis of the pile. Taking the problem backward, this could provide an efficient way to study the transport properties of bouncing mechanism.
In summary, we have investigated both ternary and binary granular mixtures in vertical HS cells and have found particular patterns. We observed the formation of an additional thin stripe which we relate to the previously reported "pairing" [9]. This cannot be fully explained by former self-stratification models. We have proposed a complementary mechanism which is compatible with observations of binary/ternary patterns. The mechanism is based on the presence of bouncing grains on top of the rolling-slipping layer. Size ratio and denstity difference between small and large grains seems to be decisive properties of mixtures for thin stripe forming. In particular, denser small grains can bounce as far as large grains. Two important experimental parameters were incoming flux and initial velocity of grains. More work on the subject is needed.
NV thanks the FNRS (Brussels, Belgium) for financial support. This work is also supported by the Bel-gian Royal Academy of Sciences through the Ochs-Lefebvre prize. Valuable discussion with M.Ausloos, J.Rajchenbach, E.Clément, S.Galam are acknowledged.
FIG. 2. Additional stripe of small grains in binary mixtures with e = 6 mm plate separation. (a) A binary granular mixtures of sand 3 (S) and poppy seeds (L) gives rise to pairs of L strates. Another way to describe the pattern is to say that a thin S stripe is in the center of each L stripe. (b) Sand 1 (S) and wheat semolina (L). Notice the difference in angle between the wide S layers in the upper part of the pile and the thin S layers of the lower part.


extfieldsofstudy: Mathematics Physics

text:
The Discrete and Continuous Painleve VI Hierarchy and the Garnier Systems

We present a general scheme to derive higher-order members of the Painleve VI (PVI) hierarchy of ODE's as well as their difference analogues. The derivation is based on a discrete structure that sits on the background of the PVI equation and that consists of a system of partial difference equations on a multidimensional lattice. The connection with the isomonodromic Garnier systems is discussed.

Introduction
In recent years there has been a growing interest in discrete analogues of the famous Painlevé equations, i.e. nonlinear nonautonomous ordinary difference equations tending to the continuous Painlevé equations in a well-defined limit and which are integrable in their own right, cf. [1]. Even though the qualitative features of the solutions of these systems are not yet fully understood, nonetheless in most of the known examples the main ingredients of their integrability have been exhibited. Recently, a classification of continuous as well as discrete Painlevé equations in terms of the root systems associated with affine Weyl groups, has been proposed on the basis of the singularities of the rational surfaces of their initial conditions and their blowings-up, cf. [2].
In a recent paper, [3], we established a connection between the continuous Painlevé VI (P VI ) equation and a non-autonomous ordinary difference equation depending on four arbitrary parameters. This novel example of a discrete Painlevé equation arises on the one hand as the nonlinear addition formula for the P VI transcendents, in fact what is effectively a superposition formula for its Bäcklund-Schlesinger transforms, on the other hand from the similarity reduction on the lattice (cf. [4,5]), of a system of partial difference equations associated with the lattice KdV family. In subsequent papers, [6,7], some more results on these systems were established, namely the existence of the Miura chain and the discovery of a novel Schwarzian PDE generating the entire (Schwarzian) KdV hierarchy of nonlinear evolution equations and whose similarity reduction is exactly the P VI equation, this being the first example of an integrable scalar PDE that reduces to full P VI with arbitrary parameters.
In the present note we extend these results to multi-dimensional systems associated with higher-order generalisations of the P VI equation. Already in [3] we noted that the similarity reduction of the lattice KdV system could be generalised in a natural way to higher-order differential and difference equations, without, however, clarifying in detail the nature of such equations. What we will argue here is that, in fact, such equations constitute what one could call the Painlevé VI hierarchy and its discrete counterpart. Whilst the idea of constructing hierarchies of Painlevé equations by exploiting the similarity reductions of hierarchies of nonlinear evolution equations of KdV type is at least two decades old, cf. [8], the issue has gained renewed interest in recent years, cf. e.g. [9]- [13], because of the hypothetical possibility that these hierarchies of higher-order Painlevé equations yield new transcendents. Evidence to that effect might be given by the asymptotic analysis of the higher-order equations, since they seem to be governed by hyper-elliptic functions rather than elliptic ones as is the case for the original Painlevé equations, [14].  [3,6,7] we are now well-equipped to tackle this problem, and in the present paper we outline the basic construction of the equations in the discrete as well as continuous P VI hierarchy. In fact, we shall demonstrate that the lattice KdV system can be naturally embedded in a multidimensional lattice system achieving the higher-order reductions by including more terms in the relevant similarity constraint which provokes the coupling between the various lattice directions.

Most
It should be noted that in a sense higher-order P VI systems already were constructed by R. Garnier in his celebrated paper of 1912, [15], extending the original approach of R.
Fuchs who was the first in [16] to find P VI arising from the isomonodromic deformation of a second-order linear differential equation. We will conclude our paper with a discussion of these Garnier systems, which in view of the recent interest in algebraic solutions of P VI , cf. e.g. [17]- [20], deserve in our opinion some renewed attention.

The Discrete PVI Hierarchy
In [3], following earlier work e.g. [4,5], cf. also [1], a coherent framework was developed in which the similarity reduction of both discrete as well as continuous equations associated with the lattice KdV family were treated. Surprisingly, from these reductions the full P VI equation for arbitrary parameters emerged together with a four-parameter discrete equation, i.e. a discrete Painlevé equation. From the treatment of [3] it was evident how to to extend the lattice system of partial difference equations and their similarity constraints leading to the reductions to P VI . Here we describe explicitely this higher-dimensional lattice system and discuss their explicit reductions.
The lattice KdV family of equations contains many related equations such as the lattice Schwarzian KdV, the lattice modified KdV (mKdV) and the actual lattice KdV equations. We concentrate here on one member of this family only, namely the lattice mKdV equation: cf. e.g. [21], with discrete independent variables n, m and depending on additional parameters of the equation p, q, i.e. the lattice parameters. As was pointed out earlier, cf.
[21], the lattice equation (2.1) actually represents a compatible parameter-family of partial difference equations: namely, we can embed the equation (2.1) into a multidimensional lattice by imposing a copy of (2.1) with different parameters on any two-dimensional sublattice, identifying each lattice direction with a corresponding lattice parameter p i ∈ C in which direction the sites are labelled by discrete variables n i (noting that these are not necessarily integers, but shift by units, i.e. n i ∈ θ i + Z, θ i ∈ C). Thus, combining two different lattice directions, labelled by (i, j) we can write the lattice equation (2.1) on the corresponding sublattice as in which we use the right superscripts i, j to denote the shifts in the corresponding directions, whereas we will use left subscripts i, j denote shifts in the reverse direction, 2)) the special property that these three different ways of calculating this point actually lead to one and the same value. It is indeed at this point that the consistency of the embedding of the lattice MKdV into the multidimensional lattice is tested. In fact, by a straightforward calculation we find that this value is given (which is clearly invariant for any permutation of the labels ijk), independent of the way in which we calculate this value! Thus, the equation ( As a consequence of this compatibility we will call the system (2.2) a holonomic system of partial difference equations. Now, we turn to the issue of the symmetry reduction of the multidimensional lattice in the sense of [5]. It follows from the general framework of [3] that the similarity constraint for the multidimensional lattice MKdV system is as follows:

3)
µ and λ being constants, and in which the variables a i are given by The sum in (2.3) is over all the i labelling the lattice directions, the choice of which decides the order of the reduction. To analyse the reduction we need a number of relations for the objects a i which follow from (2.2), namely in terms of the following variables: (2.8) The variables x ij = x ji and X ij = 1/X ji are not independent, but related via: as well as We note that since the left-hand side of (2.6) depends only on the label i but not on j, for fixed i this represents a set of N − 2 coupled first-order ordinary difference equations with respect to the shift in the discrete variable n i between the N − 1 variables X ij , j = i.
Furthermore, the relations (2.5), for the same fixed label i, provide us with a set of N − 1 first-order relations between the variables a j , j = i, and thus together with the similarity constraint (2.3) where a i is substituted by (2.6) we obtain a set of 2(N − 1) first-order nonlinear ordinary difference equations for the 2(N − 1) variables X ij , a j , j = i, which together form our higher-order discrete system. In the next section we will explicitely disentangle this coupled system in the cases N = 2 and N = 3.
The continuous equation for the PVI hierarchy derive from the differential equations with respect to the lattice parameters p i , which read: It can be shown that the differential relations (2.11) are actually compatible not only amongst themselves, but also with the the discrete equations on the lattice (2.2), i.e. the discrete and continuous flows are commuting: This can actually be demonstrated by explicit calculation exploiting the discrete relations (2.5), but we will not give the details here (which follow closely the pattern of calculations of [3]). Thus, we have a coherent framework of a large multidimensional system of equations with discrete (in terms of the variables n i ) as well as continuous (in terms of the parameters p i ) commuting flows, in terms of which compatible equations of three different types (partial difference, differential-difference and partial differential) figure in one and the same framework: the partial difference equations are precisely the lattice equations (2.2), the differential-difference equations are the relations (2.11), whilst for the partial differential equations in the scheme we refer to our recent paper [7]. Here we will focus now on the reductions under the symmetry constraint (2.3) in order to derive closed-from ODE's in terms of the lattice parameter p i . To make this reduction explicit we use (2.11) in combination with (2.5)-(2.10) to obtain differential relations for the a i , namely as well as the following relations for the reduced variables X ij in which we have abbreviated (2.14) Using (2.12) in conjunction with (2.13) and using the similarity constraint (2.3) to eliminate the a i , we obtain a coupled first-order system of differential equations w.r.t. the independent variable t i = p 2 i in terms of the 2N − 2 variables a k , X ik , (k = i). Solving the variables a k from the linear system given by the equations (2.13) and inserting them into (2.12) we obtain a coupled set of second-order nonlinear differential equations for the variables X ik .

Special Cases: N=2, N=3
We will now analyse the basic relations of the general framework presented in the previous section in the cases N = 2, 3 only in order to arrive at slightly more explicit equations, demonstrating that the reduction leads to ordinary difference equations (in the discrete case) or to ordinary differential equations (in the continuous case).

N=2:
We will be very brief about the two-dimensional case N = 2 which was the main subject of study in the earlier paper [3]. There the compatibility of the similarity constraint and the lattice equation was stated, and the various relations resulting from (2.5) were already written down. Using in this case the slightly simpler notation: a 1 = a , a 2 = b , x 12 = x , X 12 = X and using the discrete independent variables n 1 = n, n 2 = m, as well as the lattice parameters p 1 = p, p 2 = q, we derived the second order nonlinear non-autonomous difference equation: 2(n + 1) 1 − y n+1 y n + 2n 1 − y n y n−1 = µ + λ(−1) n + 2n + 1 + + (µ − λ(−1) n )(r 2 − 1)y n + r(1 − y 2 n ) (n + 1 2 ) − (m + 1 2 )(−1) n (r + y n )(1 + ry n ) , (3.1) (using a slightly different notation from the one of [3]), where r = p/q and where the variables y n are related to the X and x by the prescription: y 2n = x(2n) for the even sites, whilst y 2n+1 = −1/X(2n + 1) for the odd lattice sites (the latter choice being mainly motivated by the wish to cast the equation into a convenient shape). It was pointed out in [3] that whilst a continuum limit of (3.1) yields the P V equation, its general solution can be expressed in terms of P VI transcendents (noting its dependence on four arbitrary parameters, µ, λ, r and m).
The continuous equation for the variable X in terms of the lattice parameter p as independent variable in this case reads: and it is not difficult to show that this is actually the P VI equation through the identification w(t) = pX(p), where t = p 2 , and setting q = 1, leading to with the identification of the parameters α,β,γ,δ as follows: Eq. (3.2) is interesting in its own right since it provides us with a covariant way of writing P VI , noting its invariance under the transformations: n ↔ m , p ↔ q , X ↔ 1/X .

N=3:
This first higher-order case deals with the first genuinely multidimensional situation of three two-dimensional sublattices, on each of which a copy of the lattice MKdV equation 2) is defined. In addition there is also the similarity constraint (2.3) which couples the three lattice directions. Thus, for the three-dimensional case we have a coupled system of equations whose symbolical representation is shown in figure 2.
In the previous section we have already demonstrated the consistency of the three copies This has been carried out for this three-dimensional case using MAPLE. Obviously, the iteration involves too many steps and the expressions soon become too large to reproduce here. In order to analyse the explicit reduction in this case, we redefine the following objects a 1 = a , a 2 = b , a 3 = c X 12 = X , X 13 = Y , X 12 = X , X 13 = Y using also n 1 = n, n 2 = m, n 3 = h, as well as p 1 = p, p 2 = q and p 3 = r to simplify the notation. To start with the continuous equations, fixing the independent variable to be p we obtain the following linear system for the quantities b and c from eq. (2.13)  where we have used the similarity constraint to elininate the quantity a. Furthermore, from (2.12) we obtain the differential relations (3.5b) Solving b and c from the linear system (3.4), and substituting the results in the differential relations (3.5a) and (3.5b), we obtain two coupled second-order nonlinear ODE's depending effectively on six free parameters, namely µ, ν, n, m, h and q/r.
Alternatively, we can derive a system of second-order ordinary difference equations by fixing one of the discrete variables, say n = n 1 , and using the relations (2.5) to obtain the where the tilde denotes the shift in the lattice direction associated with the variable n.
Using the similarity constraint to eliminate the variables c, we obtain the following linear system in terms ofb and b  where the a andã can be expressed in terms of X and Y by (where the undertilde denotes the backward shift with respect to the discrete variable).
The system of equations (3.6), (3.7) and (3.9) -or, equivalently, (3.8) together with (3.9) leads in principle to a fourth order ordinary difference equation in one variable. In fact, solving b andb from (3.8) and then eliminating b altogether by a shift in the independent variable n we get a coupled system containing one equation in terms of X,X,X, X and Y , and the equation (3.9) which is first order in the both X and Y with respect to the shift in the variable n. This system of equations depends effectively on six free parameters, namely µ, ν, m, h, q/p and r/p.

Isomonodromic Deformation Problem
The isomonodromic deformation problem for the multidimensional lattice system is of Schlesinger type, [22]. In the two-dimensional case it was already presented in [4] for special values of the parameters µ, ν, cf. also [3] for the general parameter case. The extension from the two-dimensional to the multidimensional lattice is immediate: one only needs to introduce additional terms of similar form for each additional lattice direction.
Thus, the Lax representation consists on the one hand of the linear shifts on the lattice of the form in which κ is a spectral parameter, and where the Lax matrices L i are given by leading to the Lax equations which lead to a copy of the lattice MKdV equation on each two-dimensional sublattice labelled by the indices (i, j). On the other hand we have the linear differential equation for ψ(κ) with respect to its dependence on the spectral variable κ the compatibility of which with (4.1) leads to the similarity constraint (2.3). In addition, we have differential equations for ψ in terms of its dependence on the lattice parameters p i which are of the form for each of the variable p i . It is the variables t i = p 2 i that play the role as independent variables in the continuous PVI hierarchy.
The elimination of the back-shifted vectors T −1 i ψ by using the inverse of the Lax relations (4.1) lead to the following linear differential equation for ψ thus leading to the problem in the Schlesinger form, with regular singularities at 0, ∞, {t i }.
The matrices A 0 and A i are given by The continuous isomonodromic deformation is provided by the linear differential equations in terms of the lattice parameters, namely where Eq. (4.7) is not quite in standard form, and we need to apply a gauge transformation of the form to remove the term with P i , where the auxiliary variable U obeys an interesting set of equations by itself (in fact this is the object obeying the lattice KdV system of equations) , cf. [3], but we will not give any details here. With this gauge, the continuous isomonodromic deformation (4.7) adopts the standard form whilst the discrete isomonodromic is readily obtained from the Lax representation of (4.1).
is completely integrable 1 , and that it degenerates (under the autonomous limit) to a system living on the Jacobian of a hypereliptic curve, ii) that the symmetric combinations of the dependent variables of the system, as functions of each one of the essential singularities Subsequent work on the Garnier systems was done mostly by K. Okamoto and his school, cf. e.g. [23,24]. However, it seems that in most of these works these systems were treated rather as an underdetermined system of PDE's rather than (as Garnier himself clearly had in mind) as a consist system of ODE's. Although it is not easy to find the explicit transformation of the lattice system exposed in sections 2 and 3 to the systems that Garnier wrote down, in particular to find the explicit relation between the above system (5.1) and the system consisting of (3.4) and (3.5), it is to be expected that such a mapping exist. The identification is probably easiest to obtain via the transformation of the corresponding Schlesinger type of system as given in section 4 and the linear system that Garnier exploited in [15]. However, the search for such an identification will be left to a future study.
Let us finish with some remarks on the relevance of these results for work that is been done in recent years. One of the most exciting developments is the way in which the issue of algebraic solutions of P VI have arisen in recent years, e.g. in connection with WDVV equations, Frobenius manifolds and quantum cohomology, cf. e.g. the review [25]. Such algebraic solutions were already known to Picard, Painlevé and Chazy. In fact, in his early paper [16] R. Fuchs obtained a realisation of P VI in terms of an elliptic integral, and this realisation was subsequently used by Painlevé in [26], to derive an elliptic form for the P VI equation, a form of the equation that was recently recovered by Manin in [18] 3 . The assertions of Garnier in [15] on his generalisation of the Fuchs' approach might form a starting point for extending this elliptic connection to the Garnier systems, in which case we would expect to be able to find a realisation of those systems in terms of hyperelliptic integrals rather than elliptic ones. This might eventually lead to the construction of algebraic solutions of those systems, possibly in the spirit of the recent papers [27,28]. It would be of interest to further investigate the role of the discrete systems in connection with the Garnier systems: we expect them to constitute the superposition formulae for the underlying higher root systems of the corresponding affine Weyl groups. Thus, eventually, a geometric interpretation of the Garnier systems and their discrete analogues in the sense of the blowings-up of the corresponding rational surfaces of their initial conditions, along the lines of the recent paper [2], might be anticipated.