Quasipolynomial formulas for the Kronecker coefficients indexed by two two-row shapes (extended abstract)

QUASIPOLYNOMIAL FORMULAS FOR THE KRONECKER COEFFICIENTS INDEXED BY TWO TWO–ROW SHAPES (EXTENDED ABSTRACT) EMMANUEL BRIAND, ROSA ORELLANA, AND MERCEDES ROSAS Abstract. We show that the Kronecker coefficients indexed by two two–row shapes are given by quadratic quasipolynomial formulas whose domains are the maximal cells of a fan. Simple calculations provide explicitly the quasipolynomial formulas and a description of the associated fan. These new formulas are obtained from analogous formulas for the corresponding reduced Kronecker coefficients and a formula recovering the Kronecker coefficients from the reduced Kronecker coefficients. As an application, we characterize all the Kronecker coefficients indexed by two two-row shapes that are equal to zero. This allowed us to disprove a conjecture of Mulmuley about the behavior of the stretching functions attached to the Kronecker coefficients. R´esum´e. Nous d´emontrons que les coefficients de Kronecker index´es par deux partitions de longueur au plus 2 sont donn´es par des formules quasipolynomiales quadratiques dont les domaines de validit´e sont les cellules maximales d’un ´eventail. Des calculs simples nous donnent une description explicite des formules quasipolynomiales et de l’´eventail associ´e. Ces nouvelles formulas sont obtenues de formules analogues pour les coefficients de Kronecker r´eduits correspondants et au moyen d’une formule reconstruisant les coefficients de Kronecker `a partir des coefficients de Kronecker r´eduits. Une application est la caract´erisation exacte de tous les coefficients de Kronecker non– nuls index´es par deux partitions de longueur au plus deux. Ceci nous a permis de r´efuter une conjecture de Mulmuley au sujet des fonctions de dilatations associ´ees aux coefficients de Kronecker. Introduction A fundamental problem in algebraic combinatorics is the Clebsch-Gordan problem: given a linearly reductive group G, give a combinatorial description of the coefficients mλ µν in the decomposition into irreducibles of the tensor product of two (finite-dimensional complex) irreducible representation Vµ(G) and Vν(G): Vµ(G)⊗Vν(G)∼ =M λ mλ µν Vλ(G) Key words and phrases. Kronecker coefficients, internal product of symmetric functions, Saturation properties, Representations of the symmetric group. Emmanuel Briand is supported by a Juan de la Cierva Fellowship (MICINN, Spain). Mercedes Rosas is supported by a Ram´on y Cajal Fellowship (MICINN, Spain). Both are also supported by Projects MTM2007– 64509 (MICINN, Spain) and FQM333 (Junta de Andalucia). 1 2 EMMANUEL BRIAND, ROSA ORELLANA, AND MERCEDES ROSAS While this problem has been solved satisfactorily for the general linear group, GL(n), the most elementary linear group, this is not the case for the symmetric group, Sn, the most fundamental finite group. In the case of GL(n), the coefficients mλ µν =cλ µν are the well known Littlewood-Richardson coefficients. There exists several combinatorial descriptions for them. One of these descriptions was given by Berenstein and Zelevinsky (1992) that showed that cλ µν counts the integral points in a well-defined family of polytopes. This initiated a series of works concerning the stretching functions associated to these coefficients that culminated with the proof by Knutson and Tao (1999) of the saturation conjecture. Finally, Rassart (2004) showed that the Littlewood-Richardson coefficients cλ µν are given by polynomial functions of the parts of λ,µand ν, on the maximal cells of a fan. For the symmetric group Sn, the coefficients mλ µν =gλ µν are called the Kronecker coefficients. Amazingly, there is no combinatorial description of these coefficients in general. Particular families have been investigated. In this paper the Kronecker coefficients indexed by two two–row shapes are considered. They are the coefficients gλ µν such that both µand νhave two rows. Formulas for them have already been given by Remmel and Whitehead (1994) and Rosas (2001). Recent works by Luque and Thibon (2003); Garsia et al. (2008); Brown et al. (2008) have revived the interest of obtaining better formulas for the Kronecker coefficients indexed by two two–row shapes as Hilbert series related to these coefficients have been linked to problems in quantum information theory. New problems about the Clebsch–Gordan coefficients have been raised recently by the specialists of computational complexity. Narayanan (2006) showed that the computation of the Littlewood–Richardson coefficients is a #P–complete problem. B¨urgisser and Ikenmeyer (2008) showed that the computation of the Kronecker coefficients is #P–hard. On the other hand, the saturation property implies that the non–vanishing of a Littlewood–Richardson coefficient can be decided in polynomial time (Mulmuley and Sohoni, 2005). Is it also the case for the Kronecker coefficients? This question lies at the heart of a detailed plan, Geometric Complexity Theory, that Mulmuley and Sohoni (2001) elaborated to prove that P6=NP over the complex numbers (an arithmetic, non–uniform version of P6=NP). This lead Mulmuley (2007) to state a series of conjectures about the stretching functions associated to the Kronecker coefficients. The scarce information available about Kronecker coefficients made difficult even the experimental checking of these conjectures. By means of the formulas by Remmel and Whitehead (1994) and Rosas (2001) it was only possible to check them on large samples of Kronecker coefficients indexed by two two–row shapes (see Mulmuley, 2007). The present article obtains a new description for the Kronecker coefficients indexed by two two–row shapes, given by quasi–polynomial functions on the chambers of fans, resembling the description of Rassart (2004) for the Littlewood–Richardson coefficients. It is efficient enough to check Mulmuley’s conjectures for all Kronecker coefficients indexed by two two–row shapes (and, actually, disprove them by providing explicit counter–examples). We start our investigation by looking at Murnaghan’s reduced Kronecker coefficients ¯gγ αβ (Murnaghan, 1938), a related family of coefficients indexed by triples of partitions, which are stable values of stationary sequences of Kronecker coefficients. Our first result expresses the Kronecker coefficients in terms of the reduced Kronecker coefficients (Theorem 3). Exploiting the work of Rosas (2001) we are able to show that the reduced Kronecker polynomials related to the two-row family count integral QUASIPOLYNOMIAL FORMULAS FOR KRONECKER COEFFICIENTS 3 points in a polygon of R2. From this we describe an explicit piecewise quasipolynomial formula for these reduced Kronecker coefficients. The pieces are the 26 maximal cells of a fan. Last, using our formula that recovers the Kronecker coefficients from the reduced Kronecker coefficients, we obtain, with the help of the Maple package convex by Franz (2006), explicit piecewise quasipolynomial formulas for the Kronecker coefficients indexed by two two-row shapes. It is given by 74 quadratic quasipolynomials whose domains are the maximal cells of a fan. As an application, we list all Kronecker coefficients indexed by two two-row shapes that are equal to zero. This made possible the discovery of counter–examples to Mulmuley’s conjectures (Briand et al., 2008). In short, the advantage of our results is that for the first time we can completely study a complete nontrivial family of the Kronecker coefficients. The detailed proofs will be presented in a full version (Briand et al., In preparation) of this extended abstract. 1. Piecewise Quasipolynomials We now give a more detailed description of the main result. A quasipolynomial is a function on Zngiven by polynomial formulas, whose domains are the cosets of a full rank sublattice of Zn. Remarkable examples of (univariate) quasipolynomials are the Ehrhart functions of polytopes of Rkwith rational vertices, that count the integral points in the dilations of the polytope (see Stanley, 1997, chap. 4). We will obtain a description for the Kronecker coefficients indexed by two two–row shapes as a function of the following kind. Definition 1. Avector partition–like function is a function φon Znfulfilling the following: (i) There exists a convex rational polyhedral cone Csuch that φis zero outside C. (ii) Inside C, the function φis given by quasipolynomial formulas whose domains are (the sets of integral points of) the maximal (closed) cells of a fan F. If Cand Fare as above and Qis the family of quasipolynomial formulas, indexed by the maximal cells of F, we say that the triple (C, F, Q)is a presentation of φas a vector partition–like function. Remark 1. A sum of vector partition–like functions φ1,φ2is not necessarily vector partition– like. It is, however, the case when the functions admit presentations (C, F, Q)and (C′,F′, Q′) with the same cone: C=C′. Examples of vector partition–like functions are the vector partition functions, whose corresponding fans are the chamber complexes (see Sturmfels, 1995; Brion and Vergne, 1997). Vector partition–like functions also arise as functions counting integral solutions to some systems of linear inequalities depending on parameters. Precisely, consider a system of inequalities of the form (1) ui(x) + ci(h)≥0, i = 1,...,N where the functions uiand ciare integral, homogeneous linear forms on Rmand Rnrespectively. The unknown is xand the parameter is h. Assume that for any h∈Rnthe set of solutions xof the system is bounded. Let h7→ φ(h) be the function that counts the integral solutions xof the system. This function φis vector partition–like. This follows from the reduction of this function to a vector partition function (see Brion and Vergne, 1997). Here the cone Cin Definition 1 is the set of values of the parameter hmaking the system feasible. 4 EMMANUEL BRIAND, ROSA ORELLANA, AND MERCEDES ROSAS Let ℓbe a positive integer. The function (λ, µ, ν)7→ cλ µ,ν from triples of partitions with at most ℓparts to Littlewood–Richardson coefficients is vector partition–like. This is because this function counts the integral solutions of a system of inequalities depending on parameters (the parts of the partitions) of the form (1). Indeed, such a system can be derived from the Littlewood–Richardson rule (see Mulmuley and Sohoni, 2005). Alternatively, one can use the system defining Knutson and Tao’s Hive polytopes (see the exposition by Buch, 2000). It is natural to ask if similar results also hold for the Kronecker coefficients. Let ℓ1and ℓ2 be positive integers. If µand νare partitions of length at most ℓ1and ℓ2respectively then gλ µ,ν can be nonzero only if λhas at most ℓ1ℓ2parts. The analogous function to consider is thus Gℓ1,ℓ2: (λ, µ, ν)7→ gλ µ,ν defined on triples of partitions with at most ℓ1ℓ2,ℓ1and ℓ2parts respectively. No interpretation of the functions Gℓ1,ℓ2as counting integral solutions to systems of inequalities of the form (1) is known. Nevertheless, very close results were obtained by Mulmuley (2007): (i) The functions Gℓ1,ℓ2fulfill the conditions in Definition 1 with Fa complex of polyhedral cones instead of a fan. (ii) For any λ,µ,ν, the stretching function N∈N7→ gNλ Nµ,Nν is a univariate quasipolynomial. Here Nλ stands for the partitions obtained from λby multiplying all parts by N. Combining these two results, one gets that the functions Gℓ1,ℓ2fulfill the conditions in the definition of vector partition–like with “maximal closed cells” replaced with “open cells” in (ii). The simplest non–trivial case is G2,2, describing the Kronecker coefficients indexed by two two–row shapes. Even this case is somehow difficult. In this work we prove the following: Theorem 1. The function G2,2: (λ1,...,λ4, µ1, µ2, ν1, ν2)∈Z87→ g(λ1,λ2,λ3,λ4) (µ1,µ2)(ν1,ν2) is vector partition–like. Remark 2. A Kronecker coefficient gλ µ,ν can be nonzero only if its three indexing partitions have the same weight. This and the formula g(λ1,λ2,λ3,λ4) (µ1,µ2)(ν1,ν2)=g(λ1−1,λ2−1,λ3−1,λ4−1) (µ1−2,µ2−2)(ν1−2,ν2−2) reduce the study of G2,2to the study of the function (n, γ1, γ2, r, s)7→ g(n−γ1−γ2,γ1,γ2) (n−r,r)(n−s,s) 2. Murnaghan’s Theorem and reduced Kronecker coefficients In this section we introduce Murnaghan’s reduced Kronecker coefficients gγ α,β. They are integers indexed by triples of partitions closely related to the Kronecker coefficients. The Kronecker coefficients indexed by two two–row shapes will be re–obtained from the reduced Kronecker coefficients indexed by two one–row shapes (Section 3) which will be easy to describe (Theorem 4 and Section 4). The Jacobi–Trudi formula expresses the Schur functions as determinants in the complete sums hk. When λhas at most kparts, it asserts that: sλ= det(hj−i+λi)i,j=1,...,k (where hk= 0 when k < 0, h0= 1 and λi= 0 for igreater than the length of λ.) This formula can also be applied in the case when λis not a partition, i.e. is not nondecreasing. The functions sλobtained are either 0, or Schur functions up to a sign. QUASIPOLYNOMIAL FORMULAS FOR KRONECKER COEFFICIENTS 5 Let nbe an integer and λa partition. Then |λ|stands for the sum of the parts of λand for any integer n, we denote with (n− |λ|, λ) the sequence (n− |λ|, λ1, λ2,...). This is a partition if and only if n≥ |λ|+λ1. Last λstands for the partition (λ2, λ3,...), which is obtained by removing the first part of λ. Theorem 2 (Murnaghan (1938, 1955)).There exists a family of nonnegative integers (gγ α,β) indexed by triples of partitions (α, β, γ)such that, for fixed partitions αand β, only finitely many terms gγ α,β are non–zero, and for all n≥0, s(n−|α|,α)∗s(n−|β|,β)=X γ gγ α,βs(n−|γ|,γ) Following Klyachko (2004), we call the coefficients gγ α,β the reduced Kronecker coefficients. They are called extended Littlewood–Richardson numbers in Kirillov (2004) because of the following property, observed first in Murnaghan (1955) and proved in Littlewood (1958): if α,βand γare three partitions such that |γ|=|α|+|β|then gγ αβ =cγ αβ. Remark 3. It follows from Murnaghan’s Theorem that for fixed partitions α,β,γ, the sequence of Kronecker coefficients g(n−|γ|,γ) (n−|α|,α),(n−|β|,β)(nbig enough so that all three indices are partitions) is stationary with limit gγ αβ. 3. From reduced to non–reduced Kronecker coefficients In this section we give a formula that allows us to recover the non-reduced Kronecker coefficients from the reduced Kronecker coefficients, and we apply it for the Kronecker coefficients indexed by two two–row shapes. Theorem 3. Let ℓ1,ℓ2and nbe positive integers. Let λ,µ,νbe partitions of nsuch that µhas length at most ℓ1and νhas length at most ℓ2. If λhas length at most ℓ1ℓ2then (2) gλ µν = ℓ1ℓ2 X i=1 (−1)i+1gλ†i µ,ν where λ†iis the partition obtained from λby incrementing the i−1first parts and removing the i–th part, that is: λ†i= (1 + λ1,1 + λ2,...,1 + λi−1, λi+1, λi+2,...) Formula (2) applies as follows in the case ℓ1=ℓ2= 2 and λwith at most three parts: (3) g(λ1,λ2,λ3) (n−r,r)(n−s,s)=g(λ2,λ3) (r)(s)−g(λ1+1,λ3) (r)(s)+g(λ1+1,λ2+1) (r)(s) where n=|λ|. (One can show that the last expected term, g(λ1+1,λ2+1,λ3+1) (r)(s), is always zero.) The reduced Kronecker coefficients that appear in this formula are all of the form g(γ1,γ2) (r)(s). These coefficients admit the following description, derived in Briand et al. (2008) from the description for the Kronecker coefficients indexed by two two–row shapes provided by Rosas (2001). An equivalent description for the reduced Kronecker coefficients indexed by two one–row shapes is given by Thibon (1991). 6 EMMANUEL BRIAND, ROSA ORELLANA, AND MERCEDES ROSAS Theorem 4 (Briand et al. (2008)).Let r,sand γ1≥γ2be nonnegative integers and h= (r, s, γ1, γ2). The reduced Kronecker coefficient g(γ1,γ2) (r)(s)counts the integral solutions to the system of inequalities ui(X, Y ) + ci(h)≥0for i= 0, ..., 6, where: (4) u0(v) + c0(h) = X−s u1(v) + c1(h) = X−r u2(v) + c2(h) = X+Y−r−s+γ1 u3(v) + c3(h) = Y u4(v) + c4(h) = Y−X+|γ| u5(v) + c5(h) = −X−Y+r+s−γ2 u6(v) + c6(h) = X−Y−γ1 In particular, the function R: (r, s, γ1, γ2)∈Z47→ g(γ1,γ2) (r)(s)is vector partition–like. Theorem 4 and Formula (3) provide a piecewise quasipolynomial description for G2,2(see Remark 2). But the corresponding domains of quasipolynomiality obtained are neither closed, nor cones. The remainder of this work is devoted to correct this and obtain, still from Theorem 4 and Formula (3) a vector partition–like presentation for G2,2. The main tools are the Lemma 1, below, and an explicit vector partition–like presentation for the function R(section 4) showing that the lemma applies. Let F0,F1,F2be the linear maps from R5to R4that send (n, r, s, γ1, γ2) to (r, s, γ1, γ2), (r, s, n −γ1−γ2, γ2), (r, s, n −γ1−γ2, γ1) respectively. Let T1and T2be the translations in R4 of vector v1= (0,0,1,0) and v2= (0,0,1,1) respectively. Let ∆ (resp. ∆′) be the cone of R5(resp. of R4) generated by all (n, r, s, γ1, γ2)∈Z5(resp. all (r, s, γ1, γ2)∈Z4) such that the Kronecker coefficient g(n−γ1−γ2,γ1,γ2) (n−r,r)(n−s,s)(resp. the reduced Kronecker coefficient g(γ1,γ2) (r)(s)) is defined and positive. The explicit description of ∆ is provided by Bravyi (2004) (see also the general approach by Klyachko (2004)). The cone ∆′is the image of ∆ under F0. For x∈Z5set χ∆(x) = 1 if x∈∆ and χ∆(x) = 0 otherwise. Then we can rewrite Formula 3 as follows: G(x) = R◦F0(x)−χ∆(x)·R◦T1◦F1(x) + χ∆(x)·R◦T2◦F2(x) where G(x) = G(n, r, s, γ1, γ2) = g(n−γ1−γ2,γ1,γ2) (n−r,r)(n−s,s)when (n−r, r), (n−s, s), (n−γ1−γ2, γ1, γ2) are partitions, and G(n, r, s, γ1, γ2) = 0 otherwise. After Remark 1, Theorem 1 will be proved if we show that all three vector partition–like functions R◦F0,χ∆·R◦T1◦F1and χ∆·R◦T2◦F2admit presentations with the same cone: (∆,F0, Q0), (∆,F1, Q1) and (∆,F2, Q2). That R◦F0admits a presentation (∆,F0, Q0) is immediate because F−1 0(∆′) = ∆. To show that χ∆·R◦T1◦F1and χ∆·R◦T2◦F2also admit presentations with cone ∆ we will need to apply two times Lemma 1 below, with p= 5, q= 4, C= ∆, C′= ∆′,φ=Rand F=Fi,v=vi for i= 1, 2. Given subsets A,Bof Rqwe denote with A+Bthe set {a+b|a∈A, b ∈B}. Given v∈Rq and Isubset of Rwe denote with I v the set {xv |x∈I}. Lemma 1. Let φbe a vector partition–like function on Zqwith presentation (C′,F′, Q). Let C be a convex rational polyhedral cone of Rpand Fan integral linear map from Rponto Rq. Let v∈Zqand Tbe the translation of Rqof vector v. Let Fbe the fan subdividing C∩F−1(C′), whose cells are all sets of the form C∩F−1(σ′)for σ′cell of F′. QUASIPOLYNOMIAL FORMULAS FOR KRONECKER COEFFICIENTS 7 Assume that the cone C∩F−1(C′)is full–dimensional in Rp. Assume also that: (a) Whenever His a hyperplane separating two adjacent maximal cells σ′ 1,σ′ 2of F′such that F(C)is not included in H+R+v, the following holds: The quasipolynomials Qσ′ 1and Qσ′ 2coincide on the integral points of the strip H+ ]0; 1] v. (b) Whenever His a hyperplane containing a facet of C′, such that R+v+F(C)is not contained in the half–plane H+C′, the following holds: For all maximal cells σ′of F′ having a facet contained in H, the quasipolynomial Qσ′vanishes on the integral points of the strip H+ ]0; 1] v. Then (i) The function φ◦T◦Fis zero on the integral points of the closure of C\F−1(C′). (ii) If C∩F−1(σ′)is a maximal cell of F(where σ′is a maximal cell of F′) then φ◦T◦F and Qσ◦T◦Fcoincide on its integral points. Applying the lemma as indicated requires a precise description of a presentation (∆′,FR, QR) of R. The next section provides such a description. 4. Formulas for the reduced Kronecker coefficients indexed by two one–row shapes Let uiand ci, for i= 0, 1, . . . , 6 be the integral linear forms defined in (4). After Brion and Vergne (1997), the function ψthat associates to y∈Z7the number of integral solutions of the system ui(X, Y )+yi≥0, i= 0, . . . , 6 is a vector partition function. In particular, it admits a very well– described vector partition–like presentation (Cψ,Fψ, Qψ). The corresponding fan is the chamber complex of ψ, see Brion and Vergne (1997); Sturmfels (1995). Remember (Theorem 4) that Ris the function that associates the reduced Kronecker coefficient g(γ1,γ2) (r)(s)to (r, s, γ1, γ2)∈Z4. Then R=ψ◦c, where cis the linear map from R4to R7that maps h= (r, s, γ1, γ2) to (c0(h), c1(h),...,c6(h)). Therefore, one obtains a very explicit vector partition–like presentation (c−1(Cψ),FR, QR) for Rby taking for FRthe inverse image of Fψ under c, and for QRthe family of functions QR,c−1(σ)=Qψ,σ ◦cfor σmaximal cell of Fψ. We present this description. Let h∈R7. Denote with Π(h) the set of real solutions of the system (4). For i= 0, 1, . . . , 6, let Li(h) be the line with equation aiX+biY+ci(h) = 0 where ui(X, Y ) = aiX+biY. For any three elements i,j,kof {0,1,...,6}define: (5) fijk(h) = − aiajak bibjbk ci(h)cj(h)ck(h)  Define also f25 =γ1−γ2and f46 =γ2. The linear form f25 (resp. f46) is proportional to f25kfor all k6= 2,5 (resp.: to f46kfor all k6= 4,6) and its vanishing is the condition for the two parallel lines L2and L5(resp. L4and L6) to coincide. •The cone c−1(Cψ) is equal to the cone ∆′introduced in Section 3. It is defined by the system of linear inequalities: f145 ≤0, f045 ≤0, f356 ≤0, f035 ≤0, f135 ≤0, f25 ≥0, f46 ≥0. 8 EMMANUEL BRIAND, ROSA ORELLANA, AND MERCEDES ROSAS 1245 12456 02456 0245 145 v v v v v v v v v 1456 t t t t t t t t t 0456 t t t t t t t t t 045 v v v v v v v v v 12345 123456 023456 02345 1345 v v v v v v v v v 13456 t t t t t t t t t 3456 03456 t t t t t t t t t 0345 v v v v v v v v v 1235 12356 02356 0235 135 v v v v v v v v v 1356 t t t t t t t t t 356 0356 t t t t t t t t t 035 v v v v v v v v v Figure 1. The graph G. •The fan FR: Let Sbe the locus of parameters hsuch that three lines Li(h), Lj(h), Lk(h) meet in Π(h). The fan FRis the fan whose chambers (maximal open cells) are the connected components of ∆′\S. In each chamber σthe set of indices isuch that Li(h) supports a side of Π(h) is constant. Denote this set with Sides(σ). This set Sides(σ) determines σ. Therefore we denote a chamber σwith σIwhen Sides(σ) = I, e.g. σ1245 for the chamber σsuch that Sides(σ) = {1,2,4,5}. There are 26 chambers σIin FR. The corresponding indices I=Sides(σI) are the vertices of the graph Gin Figure 1. Adjacency in Grepresents adjacency in FR: chambers σIand σJare adjacent (i.e. their closures have a common facet) if and only if Iand Jare adjacent vertices in G. Observe that when σIand σJare adjacent then: –either Iand Jare obtained from each other by exchanging 0 and 1. Then σIand σJare separated by the hyperplane of equation r=s. There is r > s on σIif 1 ∈I. –or one of the sets is obtained from the other by inserting a unique element. Say J=I∪ {j}with j6∈ I. If the elements of Jare p1< p2<··· < ptsay that the successor of pqis pq+1, for q= 1, . . . , t−1, and that the successor of ptis p1. This defines a cyclic order on J. Let iand kbe the predecessor and successor of jin this cyclic order. Then σIand σJare separated by the hyperplane of equation fijk = 0, and fijk >0 on σI. •The quasipolynomial formulas on each maximal cell: For simplicity we set qI= QR,σI. This is the quasipolynomial formula for Rvalid on the cell σI(the topological closure of the chamber σI). Rather than displaying explicit expressions for all quasi– polynomials qI, it is enough to present one of them (we choose q135) and display all differences qI−qJfor σIand σJadjacent. All quasi–polynomials qIcan be recovered QUASIPOLYNOMIAL FORMULAS FOR KRONECKER COEFFICIENTS 9 ijk qI(h)−qJ(h) Values δsuch that qIand qJcoincide on fijk =δ 613,123,134 603,023,034 1 2fijk(h) (fijk(h)−1) 0,1 234 1 4(fijk(h))2+0 if fijk(h)≡0 mod 2 −1/4 else. −1,0,1 345,124,561 024,560 1 4fijk(h) (fijk(h)−2) + 0 if fijk(h)≡0 mod 2 1/4 else 0,1,2 Table 1. The differences qI−qJfor σIand σJadjacent chambers of F. easily from this information by chasing on the graph G(Figure 1), e.g. q1456 = (q1456 −q13456) + (q13456 −q1356) + (q1356−q135) + q135 There is: q135(r, s, γ1, γ2) = 1 2(s−γ2+ 1) (s−γ2+ 2) Let σIand σJbe two adjacent chambers of F. –If Iand Jare obtained from each other by exchanging 0 and 1 then qI=qJ. –If J=I∪ {j}with j6∈ Ithen qI−qJdepend only of jand its predecessor iand successor kin J, and is as indicated in Table 1. If σIand σJare adjacent, the quasi–polynomials qIand qJcoincide not only on the affine hyperplane spanned by the facet σI∩σJbut also on close parallel hyperplanes. Proposition 1. Let σIand σJbe two adjacent chambers of Fsuch that J=I∪ {j}with j6∈ I. Let iand kbe the predecessor and successor, respectively, of jin J. Then qI−qJcoincide on the affine hyperplanes fijk =δfor the values of δgiven by the third column in Table 1. Similarly, if the hyperplane Hsupports a facet of a maximal cell σI, and this facet is contained in the border of ∆′, then qIvanishes on affine hyperplanes close and parallel to H. Proposition 2. Let σIbe a chamber of Fand τan external facet of σI(i.e. a facet contained in the border of ∆′). The hyperplane supporting τadmits as equation f= 0 where fis one of the linear forms f145,f045,f356,f035,f135,f25,f46. The set of values δ∈Zsuch that fvanishes identically on the affine hyperplane of equation f=δis provided by Table 2. It is immediate that R◦F0has a vector partition–like presentations (∆,F0, Q0). Propositions 1 and 2 are used to apply Lemma 1 and show that χ∆·R◦T1◦F1and χ∆·R◦T2◦F2have vector partition–like presentations (∆,F1, Q1) and (∆,F2, Q2). After Remark 1, this proves Theorem 1 and provides a way to compute a vector partition–like presentation for Gand G2,2.