text: 12 A. BELIAKOVA, C. BLANCHET, AND A.M. GAINUTDINOV ∈ If P A-pmod is not necessarily indecomposable, then it can be realised as a direct summand ⊕ ∈ Z of A m for some ﬁnite m , i.e. we have injective and surjective maps: >0 → ⊕ ⊕ (cid:16) (2.17) j : P (cid:44) A m , p : A m P P P ◦ ◦ ⊕ such that the composition p j is identity on P and j p is an idempotent in End (A m). P P P P A We then get a decomposition of the form (2.6) with (2.18) a˜ : A −a−(k−,→j) A⊕m −p→P P and ˜b : P −j→P A⊕m −b−(k−,→j) A , (k,j) (k,j) while a and b are deﬁned as in (2.9).(cid:0) Then (2.1(cid:1)2) for the choice (2.18) gives the (k,j) (k,j) following expression for t : P (cid:55)→ ⊕ ◦ ◦ (2.19) t : f t m j f p , P P P ⊕ with t m deﬁned in (2.16). For certain proofs below it will be more convenient to use the ◦ decomposition id = p j instead of (2.6) and this expression of t . It is a consequence P P P P of Proposition 2.4 that the map (2.19) does not depend on the choices we made in the construction. Let us prove the equivalence of the diﬀerent notions of non-degeneracy. k ∈ ∗ For a ﬁnite-dimensional algebra A over a ﬁeld , we call a linear form t A non-degenerate (cid:55)→ ∈ if the associated bilinear pairing (x, y) t(xy) is non-degenarate, i.e. t(xy) = 0 for all x A implies y = 0. ∈ ∗ Theorem 2.6. For a ﬁnite-dimensional algebra A with a symmetric linear form t A the following three statements are equivalent: (1) t is non-degenerate. (2) A-pmod is Calabi-Yau with t deﬁned by (2.19). P (3) The pairings (1.13) × → k (cid:55)→ ◦ Hom (M, P ) Hom (P, M) , (f, g) t (f g) A A P ∈ ∈ are non-degenerate for all P A-pmod and M A-mod. Proof. The equivalence of the ﬁrst two statements was proven in [GR, Prop. 5.8]. Since the third statement is the strongest, it is enough to show that it follows from the ﬁrst one. For → → that we need to show that for any f : M P there exists a non-zero map g : P M such ◦ (cid:54) ⊕ that t (f g) = 0. The idea is to use non-degeneracy of the linear form t m. Let us ﬁx P (cid:16) a projective cover P of M with the canonical surjective map π : P M. Since any M M M

text: A.

text: BELIAKOVA,

text: C.

text: BLANCHET,

text: AND

text: A.M.

text: GAINUTDINOV

text: If

text: P

text: A-pmod

text: is

text: not

text: necessarily

text: indecomposable,

text: then

text: it

text: can

text: be

text: realised

text: as

text: a

text: direct

text: summand

text: Z

text: of

text: A

text: m

text: for

text: some

text: ﬁnite

text: m

text: i.e.

text: we

text: have

text: injective

text: and

text: surjective

text: maps:

text: j

text: P

text: A

text: m

text: p

text: A

text: m

text: P

text: P

text: P

text: such

text: that

text: the

text: composition

text: p

text: j

text: is

text: identity

text: on

text: P

text: and

text: j

text: p

text: is

text: an

text: idempotent

text: in

text: End

text: (A

text: m).

text: P

text: P

text: P

text: P

text: A

text: We

text: then

text: get

text: a

text: decomposition

text: of

text: the

text: form

text: with

text: a˜

text: A

text: −a−(k−,→j)

text: A⊕m

text: −p→P

text: P

text: and

text: ˜b

text: P

text: −j→P

text: A⊕m

text: −b−(k−,→j)

text: A

text: (k,j)

text: (k,j)

text: while

text: a

text: and

text: b

text: are

text: deﬁned

text: as

text: in

text: Then

text: for

text: the

text: choice

text: gives

text: the

text: (k,j)

text: (k,j)

text: following

text: expression

text: for

text: t

text: P

text: t

text: f

text: t

text: m

text: j

text: f

text: p

text: P

text: P

text: P

text: with

text: t

text: m

text: deﬁned

text: in

text: For

text: certain

text: proofs

text: below

text: it

text: will

text: be

text: more

text: convenient

text: to

text: use

text: the

text: decomposition

text: id

text: p

text: j

text: instead

text: of

text: and

text: this

text: expression

text: of

text: t

text: It

text: is

text: a

text: consequence

text: P

text: P

text: P

text: P

text: of

text: Proposition

text: that

text: the

text: map

text: does

text: not

text: depend

text: on

text: the

text: choices

text: we

text: made

text: in

text: the

text: construction.

text: Let

text: us

text: prove

text: the

text: equivalence

text: of

text: the

text: diﬀerent

text: notions

text: of

text: non-degeneracy.

text: k

text: For

text: a

text: ﬁnite-dimensional

text: algebra

text: A

text: over

text: a

text: ﬁeld

text: we

text: call

text: a

text: linear

text: form

text: t

text: A

text: non-degenerate

text: if

text: the

text: associated

text: bilinear

text: pairing

text: (x,

text: y)

text: t(xy)

text: is

text: non-degenarate,

text: i.e.

text: t(xy)

text: for

text: all

text: x

text: A

text: implies

text: y

text: Theorem

text: For

text: a

text: ﬁnite-dimensional

text: algebra

text: A

text: with

text: a

text: symmetric

text: linear

text: form

text: t

text: A

text: the

text: following

text: three

text: statements

text: are

text: equivalent:

text: t

text: is

text: non-degenerate.

text: A-pmod

text: is

text: Calabi-Yau

text: with

text: t

text: deﬁned

text: by

text: P

text: The

text: pairings

text: k

text: Hom

text: (M,

text: P

text: Hom

text: (P,

text: M)

text: (f,

text: g)

text: t

text: (f

text: g)

text: A

text: A

text: P

text: are

text: non-degenerate

text: for

text: all

text: P

text: A-pmod

text: and

text: M

text: A-mod.

text: Proof.

text: The

text: equivalence

text: of

text: the

text: ﬁrst

text: two

text: statements

text: was

text: proven

text: in

text: [GR,

text: Prop.

text: Since

text: the

text: third

text: statement

text: is

text: the

text: strongest,

text: it

text: is

text: enough

text: to

text: show

text: that

text: it

text: follows

text: from

text: the

text: ﬁrst

text: one.

text: For

text: that

text: we

text: need

text: to

text: show

text: that

text: for

text: any

text: f

text: M

text: P

text: there

text: exists

text: a

text: non-zero

text: map

text: g

text: P

text: M

text: such

text: that

text: t

text: (f

text: g)

text: The

text: idea

text: is

text: to

text: use

text: non-degeneracy

text: of

text: the

text: linear

text: form

text: t

text: m.

text: Let

text: us

text: ﬁx

text: P

text: a

text: projective

text: cover

text: P

text: of

text: M

text: with

text: the

text: canonical

text: surjective

text: map

text: π

text: P

text: M.

text: Since

text: any

text: M

text: M

text: M


text: 14 A. BELIAKOVA, C. BLANCHET, AND A.M. GAINUTDINOV ∗ V V (3.2) ev = , coev = , V V ∗ (cid:101) V V (cid:103) ∗ V V ev = , coev = . V V ∗ V V We recall the deﬁnition of the right and left partial traces in (1.7). They have the following property. C ∈ C Lemma 3.1. Let be a pivotal category and Q, P , we have then the equality ∗ ∗ P P ∗∗ (3.3) f P = f P Q Q ∈ ⊗ ∗ for any f EndC(Q P ), and similarly for the left partial trace of f. ◦ − Proof. We factorise id ∗∗ = δ δ 1 using pivotal isomorphisms and use (3.1) to reverse P P P (cid:3) arrows. C C We call an abelian category ﬁnite pivotal if is a ﬁnite tensor category in the sense C of [EGNO], i.e. (1) if is ﬁnite as an abelian category, (2) if it is a rigid monoidal category k with -bilinear and bi-exact tensor product functor, and (3) if its tensor unit is simple; and C if has a pivotal structure. Let us prove Reduction Lemma mentioned in Introduction, which says that to verify the right or left partial trace property, it is enough to check it on a projective generator. Below is the exact statement, recall also Proposition 2.4. C ∈ C Lemma 3.2. Given a ﬁnite pivotal category and a projective generator G , a symmetric ∈ ∗ C linear form t A , where A := E(cid:0)ndC(G)(cid:1), extends to a right modiﬁed trace on Proj( ) if and only if ∈ ⊗ (3.4) t ⊗ (f) = t trr (f) , for all f EndC(G G). G G G(cid:0) G (cid:1) C Analogously, t extends to a left modiﬁed trace on Proj( ) if and only if ∈ ⊗ (3.5) t ⊗ (f) = t trl (f) , for all f EndC(G G). G G G G ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: A.

text: BELIAKOVA,

text: C.

text: BLANCHET,

text: AND

text: A.M.

text: GAINUTDINOV

label: equation

text: V

text: V

text: ev

text: coev

text: V

text: V

text: V

text: V

text: V

text: V

text: ev

text: coev

text: V

text: V

text: V

text: V

text: We

text: recall

text: the

text: deﬁnition

text: of

text: the

text: right

text: and

text: left

text: partial

text: traces

text: in

text: They

text: have

text: the

text: following

text: property.

text: C

text: C

text: Lemma

text: Let

text: be

text: a

text: pivotal

text: category

text: and

text: Q,

text: P

text: we

text: have

text: then

text: the

text: equality

text: P

text: P

text: f

text: P

text: f

text: P

text: Q

text: Q

text: for

text: any

text: f

text: EndC(Q

text: P

text: and

text: similarly

text: for

text: the

text: left

text: partial

text: trace

text: of

text: f.

text: Proof.

text: We

text: factorise

text: id

text: δ

text: δ

text: using

text: pivotal

text: isomorphisms

text: and

text: use

text: to

text: reverse

text: P

text: P

text: P

text: arrows.

text: C

text: C

text: We

text: call

text: an

text: abelian

text: category

text: ﬁnite

text: pivotal

text: if

text: is

text: a

text: ﬁnite

text: tensor

text: category

text: in

text: the

text: sense

text: C

text: of

text: [EGNO],

text: i.e.

text: if

text: is

text: ﬁnite

text: as

text: an

text: abelian

text: category,

text: if

text: it

text: is

text: a

text: rigid

text: monoidal

text: category

text: k

text: with

text: -bilinear

text: and

text: bi-exact

text: tensor

text: product

text: functor,

text: and

text: if

text: its

text: tensor

text: unit

text: is

text: simple;

text: and

text: C

text: if

text: has

text: a

text: pivotal

text: structure.

text: Let

text: us

text: prove

text: Reduction

text: Lemma

text: mentioned

text: in

text: Introduction,

text: which

text: says

text: that

text: to

text: verify

text: the

text: right

text: or

text: left

text: partial

text: trace

text: property,

text: it

text: is

text: enough

text: to

text: check

text: it

text: on

text: a

text: projective

text: generator.

text: Below

text: is

text: the

text: exact

text: statement,

text: recall

text: also

text: Proposition

text: C

text: C

text: Lemma

text: Given

text: a

text: ﬁnite

text: pivotal

text: category

text: and

text: a

text: projective

text: generator

text: G

text: a

text: symmetric

text: C

text: linear

text: form

text: t

text: A

text: where

text: A

text: extends

text: to

text: a

text: right

text: modiﬁed

text: trace

text: on

text: Proj(

text: if

text: and

text: only

text: if

text: t

text: (f)

text: t

text: trr

text: (f)

text: for

text: all

text: f

text: EndC(G

text: G).

text: G

text: G

text: G

text: C

text: Analogously,

text: t

text: extends

text: to

text: a

text: left

text: modiﬁed

text: trace

text: on

text: Proj(

text: if

text: and

text: only

text: if

text: t

text: (f)

text: t

text: trl

text: (f)

text: for

text: all

text: f

text: EndC(G

text: G).

text: G

text: G

text: G

text: G

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: MODIFIED TRACE IS A SYMMETRISED INTEGRAL 17 C k C Theorem 3.3. Let be a -linear ﬁnite pivotal category. A Calabi-Yau structure on Proj( ) is compatible with duality on the right (left) if and only if the corresponding trace maps are non-degenerate and have the right (left) partial trace property. Proof. We prove the right case only, the left one is similar. The one direction is an easy check. C ∈ ⊗ (cid:0) (cid:1) Indeed, assume t is a non-degenerate right modiﬁed trace on Proj( ), and a HomC(U V, W ) ∈ ⊗ ∈ C and b HomC(W, U V ), for U, V, W Proj( ), then the top-right side of diagram (1.17) ◦ ◦ gives t ⊗ (b a) while the left-bottom part gives t trr (b a) . Then using (1.11) we conclude U V D C U V that diagram (1.17) commutes for = Proj( ). { | ∈ C } It remains to show the necessary condition. Let t P Proj( ) be CY structure on C P Proj( ) compatible with duality on the right. We need to establish the right partial trace property (1.11). By Reduction Lemma 3.2, it is enough to consider the case where U = V = G ⊗ (cid:0) (cid:1) for G a projective generator. Let us also ﬁx W = G G and choose b = id ⊗ and any ∈ ⊗ G G a EndC(G G). Then by the assumption and using the previous calculation, commutativity of the diagram (1.17) gives the equality t ⊗ (a) = t trr (a) which by Reduction Lemma 3.2 G G G G (cid:3) implies that t is a right modiﬁed trace. 4. Pivotal Hopf algebras In this section, we ﬁrst recall standard facts from theory of ﬁnite-dimensional Hopf alge- bras which will be needed later and then prove Proposition 1.2. The main reference is the k book [Ra]. In what follows, H will be a ﬁnite-dimensional Hopf algebra over a ﬁeld with the unit 1, multiplication µ, counit (cid:15), coproduct ∆, and antipode S. In this case, the antipode is invertible [IR]. In addition, we show that if H is a unimodular pivotal Hopf algebra, then H -pmod admits a non-degenerate and unique up-to-scalar right modiﬁed trace, or equiva- lently a Calabi-Yau structure compatible with duality on the right, and a similar statement for the left property. ∈ ⊗ We will say that an element g H is group-like if ∆(g) = g g. It follows [Ka, Prop. III.3.7] − that g is invertible, S(g) = g 1 and (cid:15)(g) = 1. ∈ Deﬁnition 4.1. A group-like element g H is called a pivot if − ∈ (4.1) S2(x) = gxg 1, for all x H. The pair (H, g) of a Hopf algebra H and a pivot g is called a pivotal Hopf algebra.

text: MODIFIED

text: TRACE

text: IS

text: A

text: SYMMETRISED

text: INTEGRAL

text: C

text: k

text: C

text: Theorem

text: Let

text: be

text: a

text: -linear

text: ﬁnite

text: pivotal

text: category.

text: A

text: Calabi-Yau

text: structure

text: on

text: Proj(

text: is

text: compatible

text: with

text: duality

text: on

text: the

text: right

text: (left)

text: if

text: and

text: only

text: if

text: the

text: corresponding

text: trace

text: maps

text: are

text: non-degenerate

text: and

text: have

text: the

text: right

text: (left)

text: partial

text: trace

text: property.

text: Proof.

text: We

text: prove

text: the

text: right

text: case

text: only,

text: the

text: left

text: one

text: is

text: similar.

text: The

text: one

text: direction

text: is

text: an

text: easy

text: check.

text: C

text: Indeed,

text: assume

text: t

text: is

text: a

text: non-degenerate

text: right

text: modiﬁed

text: trace

text: on

text: Proj(

text: and

text: a

text: HomC(U

text: V,

text: W

text: C

text: and

text: b

text: HomC(W,

text: U

text: V

text: for

text: U,

text: V,

text: W

text: Proj(

text: then

text: the

text: top-right

text: side

text: of

text: diagram

text: gives

text: t

text: (b

text: a)

text: while

text: the

text: left-bottom

text: part

text: gives

text: t

text: trr

text: (b

text: a)

text: Then

text: using

text: we

text: conclude

text: U

text: V

text: D

text: C

text: U

text: V

text: that

text: diagram

text: commutes

text: for

text: Proj(

text: C

text: It

text: remains

text: to

text: show

text: the

text: necessary

text: condition.

text: Let

text: t

text: P

text: Proj(

text: be

text: CY

text: structure

text: on

text: C

text: P

text: Proj(

text: compatible

text: with

text: duality

text: on

text: the

text: right.

text: We

text: need

text: to

text: establish

text: the

text: right

text: partial

text: trace

text: property

text: By

text: Reduction

text: Lemma

text: it

text: is

text: enough

text: to

text: consider

text: the

text: case

text: where

text: U

text: V

text: G

text: for

text: G

text: a

text: projective

text: generator.

text: Let

text: us

text: also

text: ﬁx

text: W

text: G

text: G

text: and

text: choose

text: b

text: id

text: and

text: any

text: G

text: G

text: a

text: EndC(G

text: G).

text: Then

text: by

text: the

text: assumption

text: and

text: using

text: the

text: previous

text: calculation,

text: commutativity

text: of

text: the

text: diagram

text: gives

text: the

text: equality

text: t

text: (a)

text: t

text: trr

text: (a)

text: which

text: by

text: Reduction

text: Lemma

text: G

text: G

text: G

text: G

text: implies

text: that

text: t

text: is

text: a

text: right

text: modiﬁed

text: trace.

text: Pivotal

text: Hopf

text: algebras

text: In

text: this

text: section,

text: we

text: ﬁrst

text: recall

text: standard

text: facts

text: from

text: theory

text: of

text: ﬁnite-dimensional

text: Hopf

text: alge-

text: bras

text: which

text: will

text: be

text: needed

text: later

text: and

text: then

text: prove

text: Proposition

text: The

text: main

text: reference

text: is

text: the

text: k

text: book

text: [Ra].

text: In

text: what

text: follows,

text: H

text: will

text: be

text: a

text: ﬁnite-dimensional

text: Hopf

text: algebra

text: over

text: a

text: ﬁeld

text: with

text: the

text: unit

text: multiplication

text: µ,

text: counit

text: coproduct

text: and

text: antipode

text: S.

text: In

text: this

text: case,

text: the

text: antipode

text: is

text: invertible

text: [IR].

text: In

text: addition,

text: we

text: show

text: that

text: if

text: H

text: is

text: a

text: unimodular

text: pivotal

text: Hopf

text: algebra,

text: then

text: H

text: -pmod

text: admits

text: a

text: non-degenerate

text: and

text: unique

text: up-to-scalar

text: right

text: modiﬁed

text: trace,

text: or

text: equiva-

text: lently

text: a

text: Calabi-Yau

text: structure

text: compatible

text: with

text: duality

text: on

text: the

text: right,

text: and

text: a

text: similar

text: statement

text: for

text: the

text: left

text: property.

text: We

text: will

text: say

text: that

text: an

text: element

text: g

text: H

text: is

text: group-like

text: if

text: ∆(g)

text: g

text: g.

text: It

text: follows

text: [Ka,

text: Prop.

text: that

text: g

text: is

text: invertible,

text: S(g)

text: g

text: and

text: Deﬁnition

text: A

text: group-like

text: element

text: g

text: H

text: is

text: called

text: a

text: pivot

text: if

text: gxg

text: for

text: all

text: x

text: H.

text: The

text: pair

text: (H,

text: g)

text: of

text: a

text: Hopf

text: algebra

text: H

text: and

text: a

text: pivot

text: g

text: is

text: called

text: a

text: pivotal

text: Hopf

text: algebra.


text: MODIFIED TRACE IS A SYMMETRISED INTEGRAL 25 5. Decomposition of tensor powers of the regular representation In this section for any ﬁnite-dimensional Hopf algebra H, we decompose tensor powers of ⊗ the regular representation and describe the centralizer algebras End (H k) explicitly. Then ∈ H we generalise these results to End ⊗ for any W H -mod. We will need these endomorphism H W algebras to prove our main theorem in next Section . We will use the following diagrams for the structural maps corresponding to the Hopf algebra data: H H H H H (5.1) µ = , ∆ = , η = , (cid:15) = , S = . H H H H H k We note that these are maps in the category vectk of ﬁnite-dimensional vector spaces over . Here is a list of graphical identities corresponding to the Hopf algebra axioms we use exten- sively below: H H H H H (5.2) = , = H H H where the ﬁrst is for coassociativity, the second says that ∆ is an algebra map, and the antipode axioms (here, we skip labels H for brevity) (5.3) = , = = , = where the ﬁrst and third say that S is an anti-algebra and anti-coalgebra map, respectively. The axioms involving unit and counit are rather clear and we omit them. Let us denote by H the vector space underlying H equipped with the trivial action of ∈ (cid:15) ∈ H, i.e. for m H and h H we have hm = (cid:15)(h)m. As a H-module, H is isomorphic (cid:15) (cid:15) to dim H copies of the trivial representation. We use Sweedler’s notation with implicit sum: (cid:48) ⊗ (cid:48)(cid:48) ∆(h) = h h . ∈ ∈ Theorem 5.1. We have for all h H and m H (cid:15) ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: MODIFIED

text: TRACE

text: IS

text: A

text: SYMMETRISED

text: INTEGRAL

label: section

text: Decomposition

text: of

text: tensor

text: powers

text: of

text: the

text: regular

text: representation

text: In

text: this

text: section

text: for

text: any

text: ﬁnite-dimensional

text: Hopf

text: algebra

text: H,

text: we

text: decompose

text: tensor

text: powers

text: of

text: the

text: regular

text: representation

text: and

text: describe

text: the

text: centralizer

text: algebras

text: End

text: (H

text: k)

text: explicitly.

text: Then

text: H

text: we

text: generalise

text: these

text: results

text: to

text: End

text: for

text: any

text: W

text: H

text: -mod.

text: We

text: will

text: need

text: these

text: endomorphism

text: H

text: W

text: algebras

text: to

text: prove

text: our

text: main

text: theorem

text: in

text: next

text: Section

text: We

text: will

text: use

text: the

text: following

text: diagrams

text: for

text: the

text: structural

text: maps

text: corresponding

text: to

text: the

text: Hopf

text: algebra

text: data:

text: H

text: H

text: H

text: H

text: H

text: µ

text: η

text: S

text: H

text: H

text: H

text: H

text: H

text: k

text: We

text: note

text: that

text: these

text: are

text: maps

text: in

text: the

text: category

text: vectk

text: of

text: ﬁnite-dimensional

text: vector

text: spaces

text: over

text: Here

text: is

text: a

text: list

text: of

text: graphical

text: identities

text: corresponding

text: to

text: the

text: Hopf

text: algebra

text: axioms

text: we

text: use

text: exten-

text: sively

text: below:

text: H

text: H

text: H

text: H

text: H

text: H

text: H

text: H

text: where

text: the

text: ﬁrst

text: is

text: for

text: coassociativity,

text: the

text: second

text: says

text: that

text: is

text: an

text: algebra

text: map,

text: and

text: the

text: antipode

text: axioms

text: (here,

text: we

text: skip

text: labels

text: H

text: for

text: brevity)

text: where

text: the

text: ﬁrst

text: and

text: third

text: say

text: that

text: S

text: is

text: an

text: anti-algebra

text: and

text: anti-coalgebra

text: map,

text: respectively.

text: The

text: axioms

text: involving

text: unit

text: and

text: counit

text: are

text: rather

text: clear

text: and

text: we

text: omit

text: them.

text: Let

text: us

text: denote

text: by

text: H

text: the

text: vector

text: space

text: underlying

text: H

text: equipped

text: with

text: the

text: trivial

text: action

text: of

text: H,

text: i.e.

text: for

text: m

text: H

text: and

text: h

text: H

text: we

text: have

text: hm

text: As

text: a

text: H-module,

text: H

text: is

text: isomorphic

text: to

text: dim

text: H

text: copies

text: of

text: the

text: trivial

text: representation.

text: We

text: use

text: Sweedler’s

text: notation

text: with

text: implicit

text: sum:

text: ∆(h)

text: h

text: h

text: Theorem

text: We

text: have

text: for

text: all

text: h

text: H

text: and

text: m

text: H

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 32 A. BELIAKOVA, C. BLANCHET, AND A.M. GAINUTDINOV Corollary 6.1. Given a unimodular pivotal Hopf algebra (H, g), a symmetric linear function ∈ ∗ ∈ ⊗ t H extends to a right modiﬁed trace on H -pmod if and only if for all f End (H H) H (cid:0) (cid:1) (6.1) t ⊗ (f) = t trr (f) . H H H H Analogously, t extends to a left modiﬁed trace on H -pmod if and only if (cid:0) (cid:1) ∈ ⊗ (6.2) t ⊗ (f) = t trl (f) , for all f End (H H) . H H H H H Corollary 6.1 allows us to restrict the analysis to the regular module and its tensor powers, and therefore we can use the results of the previous section. The proof of Theorem 1 is divided into three steps. Step 1: µ provides right modiﬁed trace. We ﬁrst show that the symmetrised right g integral µ provides the right modiﬁed trace. By Proposition 4.4 and by the assumption that g H is unimodular, µ is a symmetric form on H. g By Corollary 6.1 it is enough to check t ⊗ (f) = t (trr (f)) with t (f) = µ (f(1)) for ∈ H H H H H g any f End (H). Let us rewrite LHS of the last equation as H (cid:88) (cid:88) ◦ ◦ ◦ (6.3) t ⊗ (f) = t ⊗ (f e ) = t (π f ι ) , H H H H y H y y ∈ ∈ y B y B where B is a basis in H. Here, we ﬁrst inserted the identity (5.18), then used Corollary 5.2 and cyclicity of t . Therefore the equation we have to check is (cid:88) (cid:0) H (cid:1) (cid:16) (cid:0) (cid:1) (cid:17) ◦ ◦ ∈ ∈ ∈ ∗ (6.4) µ π f(h, v, γ) ι (1) = µ trr f(h, v, γ) (1) , h H, v B, γ H . g y y g H ∈ y B ∈ ⊗ Recall that by Corollary 5.3 any element f End (H H) is of the form f(h, v, γ) deﬁned H◦ ◦ − in (5.20). From Corollary 5.2, we have that ι = φ g (h), π = f ψ, ψ = φ 1 and (cid:88) (cid:0) y (cid:1) (cid:88)y y (cid:0) y (cid:1) ◦ ◦ ⊗ LHS of (6.4) = µ f f(h, v, γ) g (1) = γ(y)µ f (h v) = γ(v)µ (h) , g y y g y g ∈ ∈ y B y B

text: A.

text: BELIAKOVA,

text: C.

text: BLANCHET,

text: AND

text: A.M.

text: GAINUTDINOV

text: Corollary

text: Given

text: a

text: unimodular

text: pivotal

text: Hopf

text: algebra

text: (H,

text: g),

text: a

text: symmetric

text: linear

text: function

text: t

text: H

text: extends

text: to

text: a

text: right

text: modiﬁed

text: trace

text: on

text: H

text: -pmod

text: if

text: and

text: only

text: if

text: for

text: all

text: f

text: End

text: (H

text: H)

text: H

text: t

text: (f)

text: t

text: trr

text: (f)

text: H

text: H

text: H

text: H

text: Analogously,

text: t

text: extends

text: to

text: a

text: left

text: modiﬁed

text: trace

text: on

text: H

text: -pmod

text: if

text: and

text: only

text: if

text: t

text: (f)

text: t

text: trl

text: (f)

text: for

text: all

text: f

text: End

text: (H

text: H)

text: H

text: H

text: H

text: H

text: H

text: Corollary

text: allows

text: us

text: to

text: restrict

text: the

text: analysis

text: to

text: the

text: regular

text: module

text: and

text: its

text: tensor

text: powers,

text: and

text: therefore

text: we

text: can

text: use

text: the

text: results

text: of

text: the

text: previous

text: section.

text: The

text: proof

text: of

text: Theorem

text: is

text: divided

text: into

text: three

text: steps.

text: Step

text: µ

text: provides

text: right

text: modiﬁed

text: trace.

text: We

text: ﬁrst

text: show

text: that

text: the

text: symmetrised

text: right

text: g

text: integral

text: µ

text: provides

text: the

text: right

text: modiﬁed

text: trace.

text: By

text: Proposition

text: and

text: by

text: the

text: assumption

text: that

text: g

text: H

text: is

text: unimodular,

text: µ

text: is

text: a

text: symmetric

text: form

text: on

text: H.

text: g

text: By

text: Corollary

text: it

text: is

text: enough

text: to

text: check

text: t

text: (f)

text: t

text: (trr

text: (f))

text: with

text: t

text: (f)

text: µ

text: for

text: H

text: H

text: H

text: H

text: H

text: g

text: any

text: f

text: End

text: (H).

text: Let

text: us

text: rewrite

text: LHS

text: of

text: the

text: last

text: equation

text: as

text: H

text: t

text: (f)

text: t

text: (f

text: e

text: t

text: (π

text: f

text: ι

text: H

text: H

text: H

text: H

text: y

text: H

text: y

text: y

text: y

text: B

text: y

text: B

text: where

text: B

text: is

text: a

text: basis

text: in

text: H.

text: Here,

text: we

text: ﬁrst

text: inserted

text: the

text: identity

text: then

text: used

text: Corollary

text: and

text: cyclicity

text: of

text: t

text: Therefore

text: the

text: equation

text: we

text: have

text: to

text: check

text: is

text: H

text: µ

text: π

text: f(h,

text: v,

text: γ)

text: ι

text: µ

text: trr

text: f(h,

text: v,

text: γ)

text: h

text: H,

text: v

text: B,

text: γ

text: H

text: g

text: y

text: y

text: g

text: H

text: y

text: B

text: Recall

text: that

text: by

text: Corollary

text: any

text: element

text: f

text: End

text: (H

text: H)

text: is

text: of

text: the

text: form

text: f(h,

text: v,

text: γ)

text: deﬁned

text: H◦

text: in

text: From

text: Corollary

text: we

text: have

text: that

text: ι

text: φ

text: g

text: (h),

text: π

text: f

text: ψ,

text: ψ

text: φ

text: and

text: y

text: y

text: y

text: LHS

text: of

text: µ

text: f

text: f(h,

text: v,

text: γ)

text: g

text: γ(y)µ

text: f

text: (h

text: v)

text: γ(v)µ

text: (h)

text: g

text: y

text: y

text: g

text: y

text: g

text: y

text: B

text: y

text: B


text: MODIFIED TRACE IS A SYMMETRISED INTEGRAL 35 Clearly, whenever H is unibalanced, left and right symmetrised integrals can be properly ◦ normalised such that they agree, e.g. by choosing µl = µ S. Therefore, the corresponding left and right modiﬁed traces agree too. This ﬁnishes the proof of Theorem 1. 7. Quantum Groups of types ADE In this section we study ﬁnite-dimensional quantum groups at roots of unity as deﬁned in [L1, Sec. 5]5 in the simply laced case. We compute their right and left integrals and cointegrals, check that they are unibalanced and give a formula for the modiﬁed trace on the ∈ k regular representation. Here, the quantum parameter q is a root of 1, whose square has ≥ order p 2. ≥ For n 1, let A = (a ) be an indecomposable positive deﬁnite symmetric Cartan matrix ij of type A , D or E , and g denote the corresponding Lie algebra, with associated pairing n · |n· n ≤ ≤ ∈ { − } ≤ ≤ denoted by ( ). In particular a = 2 for 1 i n, and a = a 0, 1 for 1 i < j k ii ± ≤ ij ≤ ji n. The -algebra U g is generated by K 1, E and F , 1 i n, with relations, for all i, j: q i i i − − K K 1 = K 1K = 1, K K = K K , i i i i i j j i − − − (7.1) K E K 1 = qaijE , K F K 1 = q aijF , i j i j i j i j − − K K 1 [Ei, Fj] = δij qi − q−i1 , E E = E E , F F = F F , if a = 0, i j j i i j j i ij − − − E2E (q + q 1)E E E + E E2 = 0, if a = 1, i j i j i j i ij − − − F 2F (q + q 1)F F F + F F 2 = 0, if a = 1, i j i j i j i ij Ep = F p = 0, K2p = 1 . i i i The algebra U g is a Hopf algebra where the coproduct, counit and antipode are deﬁned q as ⊗ ⊗ − − (7.2) ∆(E ) = 1 E + E K , ε(E ) = 0, S(E ) = E K 1, i i i i i i i i − ⊗ ⊗ − ∆(F ) = K 1 F + F 1, ε(F ) = 0, S(F ) = K F , i i i i i i i i ⊗ − ∆(K ) = K K , ε(K ) = 1, S(K ) = K 1. i i i i i i 5We use the opposite coproduct compared to the one in [L1]. ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: MODIFIED

text: TRACE

text: IS

text: A

text: SYMMETRISED

text: INTEGRAL

text: Clearly,

text: whenever

text: H

text: is

text: unibalanced,

text: left

text: and

text: right

text: symmetrised

text: integrals

text: can

text: be

text: properly

text: normalised

text: such

text: that

text: they

text: agree,

text: e.g.

text: by

text: choosing

text: µl

text: µ

text: S.

text: Therefore,

text: the

text: corresponding

text: left

text: and

text: right

text: modiﬁed

text: traces

text: agree

text: too.

text: This

text: ﬁnishes

text: the

text: proof

text: of

text: Theorem

text: Quantum

text: Groups

text: of

text: types

text: ADE

text: In

text: this

text: section

text: we

text: study

text: ﬁnite-dimensional

text: quantum

text: groups

text: at

text: roots

text: of

text: unity

text: as

text: deﬁned

text: in

text: Sec.

text: in

text: the

text: simply

text: laced

text: case.

text: We

text: compute

text: their

text: right

text: and

text: left

text: integrals

text: and

text: cointegrals,

text: check

text: that

text: they

text: are

text: unibalanced

text: and

text: give

text: a

text: formula

text: for

text: the

text: modiﬁed

text: trace

text: on

text: the

text: k

text: regular

text: representation.

text: Here,

text: the

text: quantum

text: parameter

text: q

text: is

text: a

text: root

text: of

text: whose

text: square

text: has

text: order

text: p

text: For

text: n

text: let

text: A

text: (a

text: be

text: an

text: indecomposable

text: positive

text: deﬁnite

text: symmetric

text: Cartan

text: matrix

text: ij

text: of

text: type

text: A

text: D

text: or

text: E

text: and

text: g

text: denote

text: the

text: corresponding

text: Lie

text: algebra,

text: with

text: associated

text: pairing

text: n

text: |n·

text: n

text: denoted

text: by

text: In

text: particular

text: a

text: for

text: i

text: n,

text: and

text: a

text: a

text: for

text: i

text: j

text: k

text: ii

text: ij

text: ji

text: n.

text: The

text: -algebra

text: U

text: g

text: is

text: generated

text: by

text: K

text: E

text: and

text: F

text: i

text: n,

text: with

text: relations,

text: for

text: all

text: i,

text: j:

text: q

text: i

text: i

text: i

text: K

text: K

text: K

text: K

text: K

text: K

text: K

text: i

text: i

text: i

text: i

text: i

text: j

text: j

text: i

text: K

text: E

text: K

text: qaijE

text: K

text: F

text: K

text: q

text: aijF

text: i

text: j

text: i

text: j

text: i

text: j

text: i

text: j

text: K

text: K

text: [Ei,

text: Fj]

text: δij

text: qi

text: E

text: E

text: E

text: E

text: F

text: F

text: F

text: F

text: if

text: a

text: i

text: j

text: j

text: i

text: i

text: j

text: j

text: i

text: ij

text: (q

text: q

text: E

text: E

text: E

text: if

text: a

text: i

text: j

text: i

text: j

text: i

text: j

text: i

text: ij

text: F

text: (q

text: q

text: F

text: F

text: F

text: F

text: if

text: a

text: i

text: j

text: i

text: j

text: i

text: j

text: i

text: ij

text: Ep

text: F

text: p

text: i

text: i

text: i

text: The

text: algebra

text: U

text: g

text: is

text: a

text: Hopf

text: algebra

text: where

text: the

text: coproduct,

text: counit

text: and

text: antipode

text: are

text: deﬁned

text: q

text: as

text: ∆(E

text: E

text: E

text: K

text: ε(E

text: S(E

text: E

text: K

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: ∆(F

text: K

text: F

text: F

text: ε(F

text: S(F

text: K

text: F

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: i

text: ∆(K

text: K

text: K

text: ε(K

text: S(K

text: K

text: i

text: i

text: i

text: i

text: i

text: i

text: use

text: the

text: opposite

text: coproduct

text: compared

text: to

text: the

text: one

text: in

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: MODIFIED TRACE IS A SYMMETRISED INTEGRAL 37 C Example. For A = sl(3, ) there are two reduced decompositions of the longest element 2 w = s s s and w = s s s . The corresponding sequences of positive root vectors are 0 1 2 1 0 2 1 2 − − E , T (E ) = E E + q 1E E , T T (E ) = E 1 1 2 1 2 2 1 1 2 1 2 and − − E , T (E ) = E E + q 1E E , T T (E ) = E . 2 2 1 2 1 1 2 2 1 2 1 The algebra automorphisms T satisfy the braid relations i ◦ ◦ (7.7) T T = T T if a = 0 , i j j i ij ◦ ◦ ◦ ◦ − T T T = T T T if a = 1 . i j i j i j ij ∈ W For a given w and a reduced decomposition w = s . . . s there is an algebra ◦ · · · ◦ j1 jm automorphism T = T T . The relations (7.7) assert that T depends only on the w j1 jm w element w and not on its decomposition. The algebra U g has L-grading denoted by wt and deﬁned on generators by wt(E ) = α , − q i i wt(F ) = α and wt(K ) = 0. We also deﬁne wt(E E ) = α + α , etc. This makes the i i i i j i j algebra graded, because relations are homogeneous. We will use the following lemma. Lemma 7.1. For any root β, the root vectors E and F have L-grading wt(E ) = β and − β β β wt(F ) = β, respectively. β When q is not a root of unity this known lemma can be established using the adjoint action of the Cartan elements [KS, Ch. 6, Prop. 23]. For completeness we give in Appendix a proof of the stronger statement in the next lemma for all non-zero values of q. (cid:0) (cid:1) ∈ W ≤ ≤ (cid:0) (cid:1) Lemma 7.2. Assume that for a pair (w, i), with w and 1 i n, we have l(ws ) = ∈ i l(w) + 1. Then w(α ) ∆ and T (E ) has L-grading wt T (E ) = w(α ). And similarly, − i + w i w i i wt T (F ) = w(α ). w i i Recall that the root vectors are obtained from a reduced decomposition of the longest ≤ ≤ word (7.3). Lemma 7.1 is obtained by applying Lemma 7.2 to (s . . . s , i ), 1 k N, i1 ik−1 k and using (7.4). { − } { − } Introducing I = 0, 1, . . . , 2p 1 , J = 0, 1, . . . , p 1 , we can now construct a PBW (cid:89) (cid:89) (cid:89) basis of U g [L1, Section 5.8] q − n (7.8) B − = F mβ Kmi Em+β m ,m,m+ β i β ∈ ∈ β ∆+ i=1 β ∆+ ##LTLine## ##LTLine##

text: MODIFIED

text: TRACE

text: IS

text: A

text: SYMMETRISED

text: INTEGRAL

text: C

text: Example.

text: For

text: A

text: there

text: are

text: two

text: reduced

text: decompositions

text: of

text: the

text: longest

text: element

text: w

text: s

text: s

text: s

text: and

text: w

text: s

text: s

text: s

text: The

text: corresponding

text: sequences

text: of

text: positive

text: root

text: vectors

text: are

text: E

text: T

text: (E

text: E

text: E

text: q

text: E

text: T

text: T

text: (E

text: E

text: and

text: E

text: T

text: (E

text: E

text: E

text: q

text: E

text: T

text: T

text: (E

text: E

text: The

text: algebra

text: automorphisms

text: T

text: satisfy

text: the

text: braid

text: relations

text: i

text: T

text: T

text: T

text: T

text: if

text: a

text: i

text: j

text: j

text: i

text: ij

text: T

text: T

text: T

text: T

text: T

text: T

text: if

text: a

text: i

text: j

text: i

text: j

text: i

text: j

text: ij

text: W

text: For

text: a

text: given

text: w

text: and

text: a

text: reduced

text: decomposition

text: w

text: s

text: s

text: there

text: is

text: an

text: algebra

text: jm

text: automorphism

text: T

text: T

text: T

text: The

text: relations

text: assert

text: that

text: T

text: depends

text: only

text: on

text: the

text: w

text: jm

text: w

text: element

text: w

text: and

text: not

text: on

text: its

text: decomposition.

text: The

text: algebra

text: U

text: g

text: has

text: L-grading

text: denoted

text: by

text: wt

text: and

text: deﬁned

text: on

text: generators

text: by

text: wt(E

text: α

text: q

text: i

text: i

text: wt(F

text: α

text: and

text: wt(K

text: We

text: also

text: deﬁne

text: wt(E

text: E

text: α

text: α

text: etc.

text: This

text: makes

text: the

text: i

text: i

text: i

text: i

text: j

text: i

text: j

text: algebra

text: graded,

text: because

text: relations

text: are

text: homogeneous.

text: We

text: will

text: use

text: the

text: following

text: lemma.

text: Lemma

text: For

text: any

text: root

text: β,

text: the

text: root

text: vectors

text: E

text: and

text: F

text: have

text: L-grading

text: wt(E

text: β

text: and

text: β

text: β

text: β

text: wt(F

text: β,

text: respectively.

text: β

text: When

text: q

text: is

text: not

text: a

text: root

text: of

text: unity

text: this

text: known

text: lemma

text: can

text: be

text: established

text: using

text: the

text: adjoint

text: action

text: of

text: the

text: Cartan

text: elements

text: [KS,

text: Ch.

text: Prop.

text: For

text: completeness

text: we

text: give

text: in

text: Appendix

text: a

text: proof

text: of

text: the

text: stronger

text: statement

text: in

text: the

text: next

text: lemma

text: for

text: all

text: non-zero

text: values

text: of

text: q.

text: W

text: Lemma

text: Assume

text: that

text: for

text: a

text: pair

text: (w,

text: i),

text: with

text: w

text: and

text: i

text: n,

text: we

text: have

text: l(ws

text: i

text: l(w)

text: Then

text: w(α

text: and

text: T

text: (E

text: has

text: L-grading

text: wt

text: T

text: (E

text: w(α

text: And

text: similarly,

text: i

text: w

text: i

text: w

text: i

text: i

text: wt

text: T

text: (F

text: w(α

text: w

text: i

text: i

text: Recall

text: that

text: the

text: root

text: vectors

text: are

text: obtained

text: from

text: a

text: reduced

text: decomposition

text: of

text: the

text: longest

text: word

text: Lemma

text: is

text: obtained

text: by

text: applying

text: Lemma

text: to

text: (s

text: s

text: i

text: k

text: N,

text: k

text: and

text: using

text: Introducing

text: I

text: J

text: p

text: we

text: can

text: now

text: construct

text: a

text: PBW

text: basis

text: of

text: U

text: g

text: Section

text: q

text: n

text: B

text: F

text: mβ

text: Kmi

text: Em+β

text: m

text: ,m,m+

text: β

text: i

text: β

text: β

text: β

text: ##LTLine##

text: ##LTLine##


text: MODIFIED TRACE IS A SYMMETRISED INTEGRAL 41 where the ﬁrst equality is due to the relation (7.1) and we used explicit expression (7.9), for the second and third equalities we ﬁrst used (7.18) and then the fact that the modulus α vanishes on E and F because α is group-like and Ep = F p = 0. We have thus shown that c i i i i is a two-sided cointegral which implies unimodularity of U . q Now we prove part b). To verify the deﬁning relation for the right integral µ we will need (cid:89) (cid:88) a formula for coproduct of PBW basis elements. Let n K = Kni for β = n α . β i i i i=1 ∈ For the root vectors E , for β ∆ , the coproduct can be written as follows [Ja, Sec. 4.12] β + (cid:88) ⊗ ⊗ ⊗ (7.26) ∆(E ) = E K + 1 E + x y β β β β ν ν ν ∈ + where x and y are PBW elements B U with non-zero m+ and such that wt(x )+ ν ν 0,m,m+ q ν wt(y ) = β. We similarly have ν (cid:88) ⊗ − ⊗ ⊗ (7.27) ∆(F ) = F 1 + K 1 F + x y β β β β ν ν ν ∈ − − where x and y are now PBW elements B − U with non-zero m and such that ν ν− m ,m,0 q wt(x ) + wt(y ) = β. More generally, for the coproduct of a PBW basis element (7.8), we ν ν have (cid:89) ⊗ n (7.28) ∆(B − ) =B − K(cid:89) Kmi (cid:88) m ,m,m+ m ,m,m+ wt(B0,0,m+) i i=1 n ⊗ ⊗ + Kwt(B − ) Kimi Bm−,m,m+ + xν yν m ,0,0 i=1 ν − where x and y are in the span of PBW elements B − where all components of m˜ ν ν m˜ ,m˜ ,m˜ + − (resp. m˜ +) a(cid:0)re lo(cid:1)wer or equal to those of m (resp. m+), and at least one of them is strictly lower. (cid:88) (cid:88) Let M := Mi 1≤i≤n be the coordinates of the sum of positive roots in basis of simple roots: n 2ρ = β(cid:81)= M α . i i ∈ β ∆+ i=1 The corresponding Cartan element is K = n KMi. 2ρ i=1 i ##LTLine## ##LTLine## ##LTLine##

text: MODIFIED

text: TRACE

text: IS

text: A

text: SYMMETRISED

text: INTEGRAL

text: where

text: the

text: ﬁrst

text: equality

text: is

text: due

text: to

text: the

text: relation

text: and

text: we

text: used

text: explicit

text: expression

text: for

text: the

text: second

text: and

text: third

text: equalities

text: we

text: ﬁrst

text: used

text: and

text: then

text: the

text: fact

text: that

text: the

text: modulus

text: α

text: vanishes

text: on

text: E

text: and

text: F

text: because

text: α

text: is

text: group-like

text: and

text: Ep

text: F

text: p

text: We

text: have

text: thus

text: shown

text: that

text: c

text: i

text: i

text: i

text: i

text: is

text: a

text: two-sided

text: cointegral

text: which

text: implies

text: unimodularity

text: of

text: U

text: q

text: Now

text: we

text: prove

text: part

text: b).

text: To

text: verify

text: the

text: deﬁning

text: relation

text: for

text: the

text: right

text: integral

text: µ

text: we

text: will

text: need

text: a

text: formula

text: for

text: coproduct

text: of

text: PBW

text: basis

text: elements.

text: Let

text: n

text: K

text: Kni

text: for

text: β

text: n

text: α

text: β

text: i

text: i

text: i

text: For

text: the

text: root

text: vectors

text: E

text: for

text: β

text: the

text: coproduct

text: can

text: be

text: written

text: as

text: follows

text: [Ja,

text: Sec.

text: β

text: ∆(E

text: E

text: K

text: E

text: x

text: y

text: β

text: β

text: β

text: β

text: ν

text: ν

text: ν

text: where

text: x

text: and

text: y

text: are

text: PBW

text: elements

text: B

text: U

text: with

text: non-zero

text: m+

text: and

text: such

text: that

text: wt(x

text: ν

text: ν

text: q

text: ν

text: wt(y

text: β.

text: We

text: similarly

text: have

text: ν

text: ∆(F

text: F

text: K

text: F

text: x

text: y

text: β

text: β

text: β

text: β

text: ν

text: ν

text: ν

text: where

text: x

text: and

text: y

text: are

text: now

text: PBW

text: elements

text: B

text: U

text: with

text: non-zero

text: m

text: and

text: such

text: that

text: ν

text: ν−

text: m

text: q

text: wt(x

text: wt(y

text: β.

text: More

text: generally,

text: for

text: the

text: coproduct

text: of

text: a

text: PBW

text: basis

text: element

text: we

text: ν

text: ν

text: have

text: n

text: ∆(B

text: =B

text: Kmi

text: m

text: ,m,m+

text: m

text: ,m,m+

text: i

text: n

text: Kwt(B

text: Kimi

text: Bm−,m,m+

text: xν

text: yν

text: m

text: ν

text: where

text: x

text: and

text: y

text: are

text: in

text: the

text: span

text: of

text: PBW

text: elements

text: B

text: where

text: all

text: components

text: of

text: m˜

text: ν

text: ν

text: m˜

text: ,m˜

text: ,m˜

text: (resp.

text: m˜

text: or

text: equal

text: to

text: those

text: of

text: m

text: (resp.

text: m+),

text: and

text: at

text: least

text: one

text: of

text: them

text: is

text: strictly

text: lower.

text: Let

text: M

text: Mi

text: be

text: the

text: coordinates

text: of

text: the

text: sum

text: of

text: positive

text: roots

text: in

text: basis

text: of

text: simple

text: roots:

text: n

text: 2ρ

text: M

text: α

text: i

text: i

text: β

text: The

text: corresponding

text: Cartan

text: element

text: is

text: K

text: n

text: KMi.

text: 2ρ

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 46 A. BELIAKOVA, C. BLANCHET, AND A.M. GAINUTDINOV Appendix A. Proof of Proposition 2.3 (cid:55)→ From the deﬁnitions of HH (A) and HH (A-pmod) the map x r induces a linear map → 0 0 x Φ: HH (A) HH (A-pmod) on the corresponding classes. We need to construct its inverse. 0 0 ∈ (cid:88) By Lemma 2.2, for P A-pmod we have a decomposition: k ◦ ◦ → → (A.1) id = a id b , with b : P A, a : A P . P i A i i i i=1 (cid:88) → Let us deﬁne a map ψ : End (P ) HH (A) by P A 0 ◦ ◦ (A.2) ψ (f) := [(b f a )(1)] . P i i i We will check that the map −→∼ (A.3) Ψ: HH (A-pmod) HH (A) 0 0 (cid:55)→ [P, f] ψ (f) P is well-deﬁned, i.e. it does not depend on the cho(cid:80)ice of the decomposition (A.1) and descends on the class of f in HH (A-pmod). 0 (cid:88) (cid:48) ◦ ◦ (cid:48) Assume we have another decomposition id = (cid:48) a (cid:48) id b (cid:48), with the associated map P i i A i (cid:48) (cid:48) ◦ ◦ (cid:48) ψ (f) = [(b (cid:48) f a (cid:48))(1)] . P i i (cid:48) i Inserting the identity (A.1), we have (cid:88) (cid:48) (cid:88) (cid:48) ◦ ◦ ◦ ◦ (cid:48) (A.4) ψ (f) = [(b (cid:48) f a b a (cid:48))(1)] P i i i i (cid:48) i,i ◦ (cid:48) (cid:48) ◦ ◦ = [(b a (cid:48))(1) (b (cid:48) f a )(1)] i i i i (cid:48) i,i where we applied the algebra isomorphism from Lemma 2.1 to the composition of A-endo- (cid:48) ◦ ◦ ◦ (cid:48) morphisms (b (cid:48) f a ) and (b a (cid:48)). Similarly, i i i i (cid:88) (cid:88) ◦ (cid:48) ◦ (cid:48) ◦ ◦ (A.5) ψ (f) = [(b a (cid:48) b (cid:48) f a )(1)] P i i i i (cid:48) i,i (cid:48) ◦ ◦ ◦ (cid:48) = [(b (cid:48) f a )(1) (b a (cid:48))(1)] i i i i (cid:48) i,i

text: A.

text: BELIAKOVA,

text: C.

text: BLANCHET,

text: AND

text: A.M.

text: GAINUTDINOV

text: Appendix

text: A.

text: Proof

text: of

text: Proposition

text: From

text: the

text: deﬁnitions

text: of

text: HH

text: (A)

text: and

text: HH

text: (A-pmod)

text: the

text: map

text: x

text: r

text: induces

text: a

text: linear

text: map

text: x

text: Φ:

text: HH

text: (A)

text: HH

text: (A-pmod)

text: on

text: the

text: corresponding

text: classes.

text: We

text: need

text: to

text: construct

text: its

text: inverse.

text: By

text: Lemma

text: for

text: P

text: A-pmod

text: we

text: have

text: a

text: decomposition:

text: k

text: id

text: a

text: id

text: b

text: with

text: b

text: P

text: A,

text: a

text: A

text: P

text: P

text: i

text: A

text: i

text: i

text: i

text: Let

text: us

text: deﬁne

text: a

text: map

text: ψ

text: End

text: (P

text: HH

text: (A)

text: by

text: P

text: A

text: ψ

text: (f)

text: [(b

text: f

text: a

text: P

text: i

text: i

text: i

text: We

text: will

text: check

text: that

text: the

text: map

text: Ψ:

text: HH

text: (A-pmod)

text: HH

text: (A)

text: [P,

text: f]

text: ψ

text: (f)

text: P

text: is

text: well-deﬁned,

text: i.e.

text: it

text: does

text: not

text: depend

text: on

text: the

text: of

text: the

text: decomposition

text: and

text: descends

text: on

text: the

text: class

text: of

text: f

text: in

text: HH

text: (A-pmod).

text: Assume

text: we

text: have

text: another

text: decomposition

text: id

text: a

text: id

text: b

text: with

text: the

text: associated

text: map

text: P

text: i

text: i

text: A

text: i

text: ψ

text: (f)

text: [(b

text: f

text: a

text: P

text: i

text: i

text: i

text: Inserting

text: the

text: identity

text: we

text: have

text: ψ

text: (f)

text: [(b

text: f

text: a

text: b

text: a

text: P

text: i

text: i

text: i

text: i

text: i,i

text: [(b

text: a

text: (b

text: f

text: a

text: i

text: i

text: i

text: i

text: i,i

text: where

text: we

text: applied

text: the

text: algebra

text: isomorphism

text: from

text: Lemma

text: to

text: the

text: composition

text: of

text: A-endo-

text: morphisms

text: (b

text: f

text: a

text: and

text: (b

text: a

text: Similarly,

text: i

text: i

text: i

text: i

text: ψ

text: (f)

text: [(b

text: a

text: b

text: f

text: a

text: P

text: i

text: i

text: i

text: i

text: i,i

text: [(b

text: f

text: a

text: (b

text: a

text: i

text: i

text: i

text: i

text: i,i


text: XI his business partner in Seville. The artifact is the text, that subtasks are the translation and the email. The user additionally gives restrictions, for example, that the translation must be done for free. In a ﬁrst step, a function is ﬁndBestServiceProvider () is called. This function is used to ﬁnd die service provider with the minimum total costs (as described in section 1). In a second step, the function callServiceProvider() is called. The function calls a service provider with the artifact (in our example, the English text) and the results (e.g. the translation) are returned. With the result, the next service is called, until the workﬂow is completed. In a last step, the ﬁnal solution will be returned to the user. 4.3 Service Finder and Update Controller The Service Finder component is used to communicate with web services. There exists a bunch of diﬀerent approaches how this communication-process can be performed. In [10], the authors argue, that in an RPC-style architec- ture, every service has its one interface and if a client wants to communicate with it, he needs to know about its semantic. Therefore, they prefer a REST- based approach, especially because of better scalability. However, the communi- cation process is not the main topic of this work, we therefore use just a simple method for client-server communications. To transfer data, the telnet protocol is used, the services are autonomous programs that are located within the Seat- tleGENI network [11]. SeattleGENI is an open source network testbed similar to PlanetLab. Due to the developers, the Seattle software is currently running on about 1000 machines worldwide. Users can upload their programs written in a constrained programming language called ”Repy” (coinage of ”restricted” and ”python”) and running them in a sandbox called ”vessel”. Each vessel controls the allocation of the hardware resources to the program. In our approach, we conﬁgured 10 vessels (10 is the maximal number of concurrently running vessels in the free version) to return a random ﬂoat number between 0 and 1. This vessel represents a web service, the random number represents an oﬀer of this service. Since our Blackboard has diﬀerent regions, we have to ﬁnd suitable services for each region. So for example, if our workﬂow consists of converting a video and uploading it, we have to ﬁnd services which will accomplish the converting part and (in parallel) ﬁnd services which give us the opportunity to upload it. We assign IDs to each part of the workﬂow and search for web services with the same ID. Of course, this implicates that our ID is well known by the service. In other words, a standardized directory service like the UDDI would be helpful as a ﬁrst contact point to ﬁnd a speciﬁc service. However, we assume in our approach that we have a list of services as starting point to solve our task. An example of a possible service description is given below: [IP=131.12.10.1, PORT=63150, TASK ID=25376, METRIC =0, PAR LIST = [PRICE, BANDWITH, DISKSIZE], PRO ID=10] A tuple consisting of IP and PORT is used to contact the service (URI), the TASK ID is needed to identify which task the service will fulﬁll, the METRIC represents the availability of the service (0 means, the service is currently not available, a value between 0 and 1 represents the quality of the availability. A ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: XI

text: his

text: business

text: partner

text: in

text: Seville.

text: The

text: artifact

text: is

text: the

text: text,

text: that

text: subtasks

text: are

text: the

text: translation

text: and

text: the

text: email.

text: The

text: user

text: additionally

text: gives

text: restrictions,

text: for

text: example,

text: that

text: the

text: translation

text: must

text: be

text: done

text: for

text: free.

text: In

text: a

text: ﬁrst

text: step,

text: a

text: function

text: is

text: ﬁndBestServiceProvider

text: is

text: called.

text: This

text: function

text: is

text: used

text: to

text: ﬁnd

text: die

text: service

text: provider

text: with

text: the

text: minimum

text: total

text: costs

text: (as

text: described

text: in

text: section

text: In

text: a

text: second

text: step,

text: the

text: function

text: callServiceProvider()

text: is

text: called.

text: The

text: function

text: calls

text: a

text: service

text: provider

text: with

text: the

text: artifact

text: (in

text: our

text: example,

text: the

text: English

text: text)

text: and

text: the

text: results

text: (e.g.

text: the

text: translation)

text: are

text: returned.

text: With

text: the

text: result,

text: the

text: next

text: service

text: is

text: called,

text: until

text: the

text: workﬂow

text: is

text: completed.

text: In

text: a

text: last

text: step,

text: the

text: ﬁnal

text: solution

text: will

text: be

text: returned

text: to

text: the

text: user.

text: Service

text: Finder

text: and

text: Update

text: Controller

text: The

text: Service

text: Finder

text: component

text: is

text: used

text: to

text: communicate

text: with

text: web

text: services.

text: There

text: exists

text: a

text: bunch

text: of

text: diﬀerent

text: approaches

text: how

text: this

text: communication-process

text: can

text: be

text: performed.

text: In

text: the

text: authors

text: argue,

text: that

text: in

text: an

text: RPC-style

text: architec-

text: ture,

text: every

text: service

text: has

text: its

text: one

text: interface

text: and

text: if

text: a

text: client

text: wants

text: to

text: communicate

text: with

text: it,

text: he

text: needs

text: to

text: know

text: about

text: its

text: semantic.

text: Therefore,

text: they

text: prefer

text: a

text: REST-

text: based

text: approach,

text: especially

text: because

text: of

text: better

text: scalability.

text: However,

text: the

text: communi-

text: cation

text: process

text: is

text: not

text: the

text: main

text: topic

text: of

text: this

text: work,

text: we

text: therefore

text: use

text: just

text: a

text: simple

text: method

text: for

text: client-server

text: communications.

text: To

text: transfer

text: data,

text: the

text: telnet

text: protocol

text: is

text: used,

text: the

text: services

text: are

text: autonomous

text: programs

text: that

text: are

text: located

text: within

text: the

text: Seat-

text: tleGENI

text: network

text: SeattleGENI

text: is

text: an

text: open

text: source

text: network

text: testbed

text: similar

text: to

text: PlanetLab.

text: Due

text: to

text: the

text: developers,

text: the

text: Seattle

text: software

text: is

text: currently

text: running

text: on

text: about

text: machines

text: worldwide.

text: Users

text: can

text: upload

text: their

text: programs

text: written

text: in

text: a

text: constrained

text: programming

text: language

text: called

text: ”Repy”

text: (coinage

text: of

text: ”restricted”

text: and

text: ”python”)

text: and

text: running

text: them

text: in

text: a

text: sandbox

text: called

text: ”vessel”.

text: Each

text: vessel

text: controls

text: the

text: allocation

text: of

text: the

text: hardware

text: resources

text: to

text: the

text: program.

text: In

text: our

text: approach,

text: we

text: conﬁgured

text: vessels

text: is

text: the

text: maximal

text: number

text: of

text: concurrently

text: running

text: vessels

text: in

text: the

text: free

text: version)

text: to

text: return

text: a

text: random

text: ﬂoat

text: number

text: between

text: and

text: This

text: vessel

text: represents

text: a

text: web

text: service,

text: the

text: random

text: number

text: represents

text: an

text: oﬀer

text: of

text: this

text: service.

text: Since

text: our

text: Blackboard

text: has

text: diﬀerent

text: regions,

text: we

text: have

text: to

text: ﬁnd

text: suitable

text: services

text: for

text: each

text: region.

text: So

text: for

text: example,

text: if

text: our

text: workﬂow

text: consists

text: of

text: converting

text: a

text: video

text: and

text: uploading

text: it,

text: we

text: have

text: to

text: ﬁnd

text: services

text: which

text: will

text: accomplish

text: the

text: converting

text: part

text: and

text: (in

text: parallel)

text: ﬁnd

text: services

text: which

text: give

text: us

text: the

text: opportunity

text: to

text: upload

text: it.

text: We

text: assign

text: IDs

text: to

text: each

text: part

text: of

text: the

text: workﬂow

text: and

text: search

text: for

text: web

text: services

text: with

text: the

text: same

text: ID.

text: Of

text: course,

text: this

text: implicates

text: that

text: our

text: ID

text: is

text: well

text: known

text: by

text: the

text: service.

text: In

text: other

text: words,

text: a

text: standardized

text: directory

text: service

text: like

text: the

text: UDDI

text: would

text: be

text: helpful

text: as

text: a

text: ﬁrst

text: contact

text: point

text: to

text: ﬁnd

text: a

text: speciﬁc

text: service.

text: However,

text: we

text: assume

text: in

text: our

text: approach

text: that

text: we

text: have

text: a

text: list

text: of

text: services

text: as

text: starting

text: point

text: to

text: solve

text: our

text: task.

text: An

text: example

text: of

text: a

text: possible

text: service

text: description

text: is

text: given

text: below:

text: TASK

text: METRIC

text: PAR

text: LIST

text: [PRICE,

text: BANDWITH,

text: DISKSIZE],

text: PRO

text: A

text: tuple

text: consisting

text: of

text: IP

text: and

text: PORT

text: is

text: used

text: to

text: contact

text: the

text: service

text: (URI),

text: the

text: TASK

text: ID

text: is

text: needed

text: to

text: identify

text: which

text: task

text: the

text: service

text: will

text: fulﬁll,

text: the

text: METRIC

text: represents

text: the

text: availability

text: of

text: the

text: service

text: means,

text: the

text: service

text: is

text: currently

text: not

text: available,

text: a

text: value

text: between

text: and

text: represents

text: the

text: quality

text: of

text: the

text: availability.

text: A

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: XVI objects of a service-class but it would be easy to adopt the code to call external sources. SeattleGENI-vessels can be used to simulate working services, spread on servers all over the world. Unfortunately, due to security restrictions, it is not allowed to open sockets within the Google App Engine, therefore it is not possible to contact the external SeattleGENI-”services” in the web engine. Sure enough, such a scenario can be performed local. Measuring call- and response- time on a realistic environment with a large dataset to check, if users can work eﬃciently with our approach, is the next step to evaluate the approach. 6 Conclusion and Future Work This paper gives an overview about how complex problems can be solved by dividing them into subtasks and search for web services with the best oﬀer for the user. Due to the dynamic environment, it is necessary to consider dynamic changes of services. These changes make partial recalculations of optimal solu- tions necessary. However, it is a challenging task to limit these recalculations to a minimum. Therefore, suggestions are given, how to deal with these incidental events. The focus of this paper is on the description of the architectural framework of the Blackboard approach and its components. Suggestions were made, based on the ideas of [4], how single optimization-processes can be outsourced to external parts. An important cognition of this analysis is, that for external-optimization, not many modiﬁcations have to be made. This leads to the conclusion that it is possible to split the entire Blackboard, outsource all branches and just collect and evaluate the partial solutions locally. In the future, it should be possible for the user to specify a complete workﬂow and the computer will automatically ﬁnd the subtasks which are contained. For example, it should be possible to ﬁlter the subtasks from the phrase ”Check, if I can play tennis tomorrow afternoon at 3pm in Santa Barbara”. In this example, a web service that checks if the tennis court is free or reserved should be called, a web service can check the weather and a web service checks if the user should drive away from home earlier because a lot of traﬃc is expected. Summing up, we presented and implemented a framework for optimization of the service selection problem of workﬂows. The novelty of our approach is mapping the service selection problem to a graph representation and to apply a combination of Dijkstra’s algorithm and Blackboard method for optimization. The practical feasibility is shown by a use case implementation. References 1. Wanek, H., Schikuta, E.: Using Blackboards to Optimize Grid Workﬂows with Re- spect to Quality Constraints. In Fifth International Conference Grid and Coopera- tive Computing Workshops,. GCCW 2006, pp. 290-295 (2006) 2. Wanek, H., Schikuta, E., Haq, I.U.: Grid Workﬂow Optimization Regarding Dy- namically Changing Resources and Conditions. In Sixth International Conference Grid and Cooperative Computing, GCC 2007, pp. 757-763 (2007)

text: XVI

text: objects

text: of

text: a

text: service-class

text: but

text: it

text: would

text: be

text: easy

text: to

text: adopt

text: the

text: code

text: to

text: call

text: external

text: sources.

text: SeattleGENI-vessels

text: can

text: be

text: used

text: to

text: simulate

text: working

text: services,

text: spread

text: on

text: servers

text: all

text: over

text: the

text: world.

text: Unfortunately,

text: due

text: to

text: security

text: restrictions,

text: it

text: is

text: not

text: allowed

text: to

text: open

text: sockets

text: within

text: the

text: Google

text: App

text: Engine,

text: therefore

text: it

text: is

text: not

text: possible

text: to

text: contact

text: the

text: external

text: SeattleGENI-”services”

text: in

text: the

text: web

text: engine.

text: Sure

text: enough,

text: such

text: a

text: scenario

text: can

text: be

text: performed

text: local.

text: Measuring

text: call-

text: and

text: response-

text: time

text: on

text: a

text: realistic

text: environment

text: with

text: a

text: large

text: dataset

text: to

text: check,

text: if

text: users

text: can

text: work

text: eﬃciently

text: with

text: our

text: approach,

text: is

text: the

text: next

text: step

text: to

text: evaluate

text: the

text: approach.

text: Conclusion

text: and

text: Future

text: Work

text: This

text: paper

text: gives

text: an

text: overview

text: about

text: how

text: complex

text: problems

text: can

text: be

text: solved

text: by

text: dividing

text: them

text: into

text: subtasks

text: and

text: search

text: for

text: web

text: services

text: with

text: the

text: best

text: oﬀer

text: for

text: the

text: user.

text: Due

text: to

text: the

text: dynamic

text: environment,

text: it

text: is

text: necessary

text: to

text: consider

text: dynamic

text: changes

text: of

text: services.

text: These

text: changes

text: make

text: partial

text: recalculations

text: of

text: optimal

text: solu-

text: tions

text: necessary.

text: However,

text: it

text: is

text: a

text: challenging

text: task

text: to

text: limit

text: these

text: recalculations

text: to

text: a

text: minimum.

text: Therefore,

text: suggestions

text: are

text: given,

text: how

text: to

text: deal

text: with

text: these

text: incidental

text: events.

text: The

text: focus

text: of

text: this

text: paper

text: is

text: on

text: the

text: description

text: of

text: the

text: architectural

text: framework

text: of

text: the

text: Blackboard

text: approach

text: and

text: its

text: components.

text: Suggestions

text: were

text: made,

text: based

text: on

text: the

text: ideas

text: of

text: how

text: single

text: optimization-processes

text: can

text: be

text: outsourced

text: to

text: external

text: parts.

text: An

text: important

text: cognition

text: of

text: this

text: analysis

text: is,

text: that

text: for

text: external-optimization,

text: not

text: many

text: modiﬁcations

text: have

text: to

text: be

text: made.

text: This

text: leads

text: to

text: the

text: conclusion

text: that

text: it

text: is

text: possible

text: to

text: split

text: the

text: entire

text: Blackboard,

text: outsource

text: all

text: branches

text: and

text: just

text: collect

text: and

text: evaluate

text: the

text: partial

text: solutions

text: locally.

text: In

text: the

text: future,

text: it

text: should

text: be

text: possible

text: for

text: the

text: user

text: to

text: specify

text: a

text: complete

text: workﬂow

text: and

text: the

text: computer

text: will

text: automatically

text: ﬁnd

text: the

text: subtasks

text: which

text: are

text: contained.

text: For

text: example,

text: it

text: should

text: be

text: possible

text: to

text: ﬁlter

text: the

text: subtasks

text: from

text: the

text: phrase

text: ”Check,

text: if

text: I

text: can

text: play

text: tennis

text: tomorrow

text: afternoon

text: at

text: in

text: Santa

text: Barbara”.

text: In

text: this

text: example,

text: a

text: web

text: service

text: that

text: checks

text: if

text: the

text: tennis

text: court

text: is

text: free

text: or

text: reserved

text: should

text: be

text: called,

text: a

text: web

text: service

text: can

text: check

text: the

text: weather

text: and

text: a

text: web

text: service

text: checks

text: if

text: the

text: user

text: should

text: drive

text: away

text: from

text: home

text: earlier

text: because

text: a

text: lot

text: of

text: traﬃc

text: is

text: expected.

text: Summing

text: up,

text: we

text: presented

text: and

text: implemented

text: a

text: framework

text: for

text: optimization

text: of

text: the

text: service

text: selection

text: problem

text: of

text: workﬂows.

text: The

text: novelty

text: of

text: our

text: approach

text: is

text: mapping

text: the

text: service

text: selection

text: problem

text: to

text: a

text: graph

text: representation

text: and

text: to

text: apply

text: a

text: combination

text: of

text: Dijkstra’s

text: algorithm

text: and

text: Blackboard

text: method

text: for

text: optimization.

text: The

text: practical

text: feasibility

text: is

text: shown

text: by

text: a

text: use

text: case

text: implementation.

text: References

text: Wanek,

text: H.,

text: Schikuta,

text: E.:

text: Using

text: Blackboards

text: to

text: Optimize

text: Grid

text: Workﬂows

text: with

text: Re-

text: spect

text: to

text: Quality

text: Constraints.

text: In

text: Fifth

text: International

text: Conference

text: Grid

text: and

text: Coopera-

text: tive

text: Computing

text: Workshops,.

text: GCCW

text: pp.

text: Wanek,

text: H.,

text: Schikuta,

text: E.,

text: Haq,

text: I.U.:

text: Grid

text: Workﬂow

text: Optimization

text: Regarding

text: Dy-

text: namically

text: Changing

text: Resources

text: and

text: Conditions.

text: In

text: Sixth

text: International

text: Conference

text: Grid

text: and

text: Cooperative

text: Computing,

text: GCC

text: pp.


text: LIU, HU, QIAN, YU AND QIAN Some open-source packages of derivative-free optimization approaches have been available, includ- ing individual algorithms such as CMA-ES2 (Hansen et al., 2003), SMAC3 (Hutter et al., 2011), IMGPO4 (Kawaguchi et al., 2015), and RACOS5 (Yu et al., 2016); packages of a kind of algorithms such as DEAP6 (Fortin et al., 2012), BayesOpt7 (Martinez-Cantin, 2014), and Spearmint8 (Snoek et al., 2011); and those particularly designed for hyper-parameter optimization with machine learn- ing frameworks, such as Scikit-Optimize9 and Hyperopt10 (Bergstra et al., 2011). These packages either provide general-purpose tools, or tools for a speciﬁc task (i.e., hyper-parameter tuning) in learning. The design of the ZOOpt aims at building a ready-to-use tool for solving more generic op- timization problems in machine learning, which require high efﬁciency, scaling-up, noise-handling, etc. 2. Methods in ZOOpt With the aim of supporting machine learning tasks, ZOOpt includes a set of methods that are efﬁ- cient and performance-guaranteed, with add-ons handling noise and high-dimensionality. Optimization in continuous space. We implement SRACOS (Hu et al., 2017) as the default opti- mization method for continuous space, which has shown high efﬁciency in a range of learning tasks. Optional method is RACOS (Yu et al., 2016), a batch version of SRACOS. A routine is in place to setup the default parameters of the two methods, while users can override them. Optimization in discrete space. Both SRACOS and RACOS can also be applied to discrete space. However, if the optimization task is in a binary vector space with constraints, such as the subset selection problem, POSS (Qian et al., 2015) is the default optimization method, which has been proven with the best-so-far approximation quality on these problems. Noise handling. Noise has a great impact on the performance of derivative-free optimization. Re- sampling is the most straightforward method to handle noise, which evaluates one sample several times to obtain a stable mean value. Besides resampling, more efﬁcient methods including value suppression (Wang et al., 2018) and threshold selection (Qian et al., 2017) are implemented. High-dimensionality handling. Increase of the search space dimensionality badly injures the per- formance of derivative-free optimization. When a high dimensional search space has a low effective- dimension, random embedding (Wang et al., 2016) is an effective way to improve the efﬁciency. Also, the sequential random embeddings (Qian et al., 2016) can be used when there is no clear low effective-dimension. 3. Structure of ZOOpt Single-thread optimization. ZOOpt single-thread version is implemented purely in Python, which provides easy integrality with other machine learning frameworks in Python. ZOOpt itself is an independent package and can also be installed from PyPI using pip. In ZOOpt, an optimization problem is abstracted in several components: Objective, Dimension, Parameter, and Solution, where each is a Python class. An Objective object is initialized 2. https://www.lri.fr/˜hansen/cmaes_inmatlab.html 3. http://www.cs.ubc.ca/labs/beta/Projects/SMAC/ 4. http://lis.csail.mit.edu/code/imgpo.html 5. https://github.com/eyounx/RACOS 6. https://github.com/deap/deap 7. https://bitbucket.org/rmcantin/bayesopt/ 8. https://github.com/JasperSnoek/spearmint 9. https://github.com/scikit-optimize/scikit-optimize 10. http://jaberg.github.io/hyperopt/ 2 ##LTLine##

text: LIU,

text: HU,

text: QIAN,

text: YU

text: AND

text: QIAN

text: Some

text: open-source

text: packages

text: of

text: derivative-free

text: optimization

text: approaches

text: have

text: been

text: available,

text: includ-

text: ing

text: individual

text: algorithms

text: such

text: as

text: (Hansen

text: et

text: al.,

text: (Hutter

text: et

text: al.,

text: (Kawaguchi

text: et

text: al.,

text: and

text: (Yu

text: et

text: al.,

text: packages

text: of

text: a

text: kind

text: of

text: algorithms

text: such

text: as

text: (Fortin

text: et

text: al.,

text: (Martinez-Cantin,

text: and

text: (Snoek

text: et

text: al.,

text: and

text: those

text: particularly

text: designed

text: for

text: hyper-parameter

text: optimization

text: with

text: machine

text: learn-

text: ing

text: frameworks,

text: such

text: as

text: and

text: (Bergstra

text: et

text: al.,

text: These

text: packages

text: either

text: provide

text: general-purpose

text: tools,

text: or

text: tools

text: for

text: a

text: speciﬁc

text: task

text: (i.e.,

text: hyper-parameter

text: tuning)

text: in

text: learning.

text: The

text: design

text: of

text: the

text: ZOOpt

text: aims

text: at

text: building

text: a

text: ready-to-use

text: tool

text: for

text: solving

text: more

text: generic

text: op-

text: timization

text: problems

text: in

text: machine

text: learning,

text: which

text: require

text: high

text: efﬁciency,

text: scaling-up,

text: noise-handling,

text: etc.

text: Methods

text: in

text: ZOOpt

text: With

text: the

text: aim

text: of

text: supporting

text: machine

text: learning

text: tasks,

text: ZOOpt

text: includes

text: a

text: set

text: of

text: methods

text: that

text: are

text: efﬁ-

text: cient

text: and

text: performance-guaranteed,

text: with

text: add-ons

text: handling

text: noise

text: and

text: high-dimensionality.

text: Optimization

text: in

text: continuous

text: space.

text: We

text: implement

text: SRACOS

text: (Hu

text: et

text: al.,

text: as

text: the

text: default

text: opti-

text: mization

text: method

text: for

text: continuous

text: space,

text: which

text: has

text: shown

text: high

text: efﬁciency

text: in

text: a

text: range

text: of

text: learning

text: tasks.

text: Optional

text: method

text: is

text: RACOS

text: (Yu

text: et

text: al.,

text: a

text: batch

text: version

text: of

text: SRACOS.

text: A

text: routine

text: is

text: in

text: place

text: to

text: setup

text: the

text: default

text: parameters

text: of

text: the

text: two

text: methods,

text: while

text: users

text: can

text: override

text: them.

text: Optimization

text: in

text: discrete

text: space.

text: Both

text: SRACOS

text: and

text: RACOS

text: can

text: also

text: be

text: applied

text: to

text: discrete

text: space.

text: However,

text: if

text: the

text: optimization

text: task

text: is

text: in

text: a

text: binary

text: vector

text: space

text: with

text: constraints,

text: such

text: as

text: the

text: subset

text: selection

text: problem,

text: POSS

text: (Qian

text: et

text: al.,

text: is

text: the

text: default

text: optimization

text: method,

text: which

text: has

text: been

text: proven

text: with

text: the

text: best-so-far

text: approximation

text: quality

text: on

text: these

text: problems.

text: Noise

text: handling.

text: Noise

text: has

text: a

text: great

text: impact

text: on

text: the

text: performance

text: of

text: derivative-free

text: optimization.

text: Re-

text: sampling

text: is

text: the

text: most

text: straightforward

text: method

text: to

text: handle

text: noise,

text: which

text: evaluates

text: one

text: sample

text: several

text: times

text: to

text: obtain

text: a

text: stable

text: mean

text: value.

text: Besides

text: resampling,

text: more

text: efﬁcient

text: methods

text: including

text: value

text: suppression

text: (Wang

text: et

text: al.,

text: and

text: threshold

text: selection

text: (Qian

text: et

text: al.,

text: are

text: implemented.

text: High-dimensionality

text: handling.

text: Increase

text: of

text: the

text: search

text: space

text: dimensionality

text: badly

text: injures

text: the

text: per-

text: formance

text: of

text: derivative-free

text: optimization.

text: When

text: a

text: high

text: dimensional

text: search

text: space

text: has

text: a

text: low

text: effective-

text: dimension,

text: random

text: embedding

text: (Wang

text: et

text: al.,

text: is

text: an

text: effective

text: way

text: to

text: improve

text: the

text: efﬁciency.

text: Also,

text: the

text: sequential

text: random

text: embeddings

text: (Qian

text: et

text: al.,

text: can

text: be

text: used

text: when

text: there

text: is

text: no

text: clear

text: low

text: effective-dimension.

text: Structure

text: of

text: ZOOpt

text: Single-thread

text: optimization.

text: ZOOpt

text: single-thread

text: version

text: is

text: implemented

text: purely

text: in

text: Python,

text: which

text: provides

text: easy

text: integrality

text: with

text: other

text: machine

text: learning

text: frameworks

text: in

text: Python.

text: ZOOpt

text: itself

text: is

text: an

text: independent

text: package

text: and

text: can

text: also

text: be

text: installed

text: from

text: PyPI

text: using

text: pip.

text: In

text: ZOOpt,

text: an

text: optimization

text: problem

text: is

text: abstracted

text: in

text: several

text: components:

text: Objective,

text: Dimension,

text: Parameter,

text: and

text: Solution,

text: where

text: each

text: is

text: a

text: Python

text: class.

text: An

text: Objective

text: object

text: is

text: initialized

text: ##LTLine##


text: (cid:16) (cid:17) (cid:82) | (cid:39) A → B ⊗ R(cid:104) (cid:105) → B ⊕ C with g A hf by a homotopy H : t, dt . Then the map O : V n+1 n given by 1 O(v) = f(dv), g(v) + H(dv) 0 ∈ B → C A(cid:104) (cid:105) → B deﬁnes an obstruction class [O] Hn+1(h : ; V ) to producing an extension f˜ : V of (cid:39) ◦ f with g h f˜ via a homotopy H˜ . → B When the obstruction vanishes, there are maps (b, c) : V n such that d(b, c) = O, i.e. (cid:82) db(v) = f(dv) ◦ − − 1 dc(v) = h b(v) g(v) H(dv). 0 ∈ Then for v V we can set f˜(v) = b(v) and (cid:82) ⊗ (3.4) H˜ (v) = g(v) + t H(dv) + d(c(v) t). 0 This gives a speciﬁc formula for the extension. This lemma has a relative analogue which is also quite useful. A(cid:104) (cid:105) Proposition 3.5 (10.5 in [GrMo]). Let V be an n-dimensional elementary extension of a DGA A . Suppose we have a diagram of DGAs A f B µ D (cid:127) (cid:95) (cid:47)(cid:47) (cid:47)(cid:47) (cid:63)(cid:63) ν h A(cid:104)(cid:15)(cid:15) (cid:105) g C(cid:15)(cid:15) V (cid:47)(cid:47) where | (cid:39) A → B ⊗ R(cid:104) (cid:105) (1) g A hf by a homotopy H : t, dt , (2) ν is surjective, ◦ (3) ν h = µ on the nose, and ◦ ◦ | (4) µ f = ν g A on the nose. (cid:16) (cid:82) (cid:17) → B ⊕ C Then the map O : V n+1 n given by 1 O(v) = f(dv), g(v) + H(dv) 0 ∈ B → C A(cid:104) (cid:105) → B deﬁnes an obstruction class [O] Hn+1(h : ; V ) to producing an extension f˜ : V of (cid:39) ◦ ◦ ◦ ◦ ⊗ f with g h f˜ via a homotopy H˜ where µ H˜ is constant (i.e. µ H˜ = (µ f) 1.) ◦ ◦ | In eﬀect, this says that in this case we can deﬁne b and c as above so that µ b = µ g and ◦ V µ c = 0. Finally, we give the DGA version of the exact sequence of groups. A(cid:104) (cid:105) Proposition 3.6 (14.4 in [GrMo]). Let V be an n-dimensional elementary extension of a DGA A B A → B . Then for any DGA and map ϕ : , there is an exact sequence of groups (and a torsor) A(cid:104) (cid:105) B ⊗ Q(cid:104) (cid:105) → A B ⊗ R(cid:104) (cid:105) −O→ B → { } → [ V , e(1) ] [ , e(1) ] Hn( ; V ) extensions of ϕ 0, ϕ˜ ϕ where ϕ˜ is any extension of ϕ, the group structure on the ﬁrst two sets is given by ⊗ (cid:1) ⊗ ⊗ (ϕ + η e) (ϕ + η e) = ϕ + (η + η ) e, 1 2 1 2 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: A

text: B

text: B

text: C

text: with

text: g

text: A

text: hf

text: by

text: a

text: homotopy

text: H

text: t,

text: dt

text: Then

text: the

text: map

text: O

text: V

text: n

text: given

text: by

text: O(v)

text: f(dv),

text: g(v)

text: H(dv)

text: B

text: C

text: B

text: deﬁnes

text: an

text: obstruction

text: class

text: [O]

text: V

text: to

text: producing

text: an

text: extension

text: f˜

text: V

text: of

text: f

text: with

text: g

text: h

text: f˜

text: via

text: a

text: homotopy

text: H˜

text: B

text: When

text: the

text: obstruction

text: vanishes,

text: there

text: are

text: maps

text: (b,

text: c)

text: V

text: n

text: such

text: that

text: d(b,

text: c)

text: O,

text: i.e.

text: db(v)

text: f(dv)

text: dc(v)

text: h

text: b(v)

text: g(v)

text: H(dv).

text: Then

text: for

text: v

text: V

text: we

text: can

text: set

text: f˜(v)

text: b(v)

text: and

text: H˜

text: (v)

text: g(v)

text: t

text: H(dv)

text: d(c(v)

text: t).

text: This

text: gives

text: a

text: speciﬁc

text: formula

text: for

text: the

text: extension.

text: This

text: lemma

text: has

text: a

text: relative

text: analogue

text: which

text: is

text: also

text: quite

text: useful.

text: Proposition

text: in

text: [GrMo]).

text: Let

text: V

text: be

text: an

text: n-dimensional

text: elementary

text: extension

text: of

text: a

text: DGA

text: A

text: Suppose

text: we

text: have

text: a

text: diagram

text: of

text: DGAs

text: A

text: f

text: B

text: µ

text: D

text: ν

text: h

text: g

text: V

text: where

text: A

text: B

text: g

text: A

text: hf

text: by

text: a

text: homotopy

text: H

text: t,

text: dt

text: ν

text: is

text: surjective,

text: ν

text: h

text: µ

text: on

text: the

text: nose,

text: and

text: µ

text: f

text: ν

text: g

text: A

text: on

text: the

text: nose.

text: B

text: C

text: Then

text: the

text: map

text: O

text: V

text: n

text: given

text: by

text: O(v)

text: f(dv),

text: g(v)

text: H(dv)

text: B

text: C

text: B

text: deﬁnes

text: an

text: obstruction

text: class

text: [O]

text: V

text: to

text: producing

text: an

text: extension

text: f˜

text: V

text: of

text: f

text: with

text: g

text: h

text: f˜

text: via

text: a

text: homotopy

text: H˜

text: where

text: µ

text: H˜

text: is

text: constant

text: (i.e.

text: µ

text: H˜

text: (µ

text: f)

text: In

text: eﬀect,

text: this

text: says

text: that

text: in

text: this

text: case

text: we

text: can

text: deﬁne

text: b

text: and

text: c

text: as

text: above

text: so

text: that

text: µ

text: b

text: µ

text: g

text: and

text: V

text: µ

text: c

text: Finally,

text: we

text: give

text: the

text: DGA

text: version

text: of

text: the

text: exact

text: sequence

text: of

text: groups.

text: Proposition

text: in

text: [GrMo]).

text: Let

text: V

text: be

text: an

text: n-dimensional

text: elementary

text: extension

text: of

text: a

text: DGA

text: A

text: B

text: A

text: B

text: Then

text: for

text: any

text: DGA

text: and

text: map

text: ϕ

text: there

text: is

text: an

text: exact

text: sequence

text: of

text: groups

text: (and

text: a

text: torsor)

text: B

text: A

text: B

text: −O→

text: B

text: V

text: Hn(

text: V

text: extensions

text: of

text: ϕ

text: ϕ˜

text: ϕ

text: where

text: ϕ˜

text: is

text: any

text: extension

text: of

text: ϕ,

text: the

text: group

text: structure

text: on

text: the

text: ﬁrst

text: two

text: sets

text: is

text: given

text: by

text: (ϕ

text: η

text: e)

text: (ϕ

text: η

text: e)

text: ϕ

text: (η

text: η

text: e,

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 4. The shadowing principle Theorem 4.1 (The shadowing principle). Let (X, A) be an n-dimensional simplicial pair with the standard metric on simplices and Y a simply connected compact Riemannian manifold with bound- M∗ → ∗ ary which has a minimal model m : Ω Y . Fix norms on the spaces V of k-dimensional M∗ Y→ Y M∗ → ∗ k indecomposables of . Let f : X Y be a map and ϕ : Ω X a homomorphism such that ∗ | | Y Y M∗ → ∗ (1) f m = ϕ (i.e. the homomorphisms restrict to the same homomorphism Ω A.) ∗ Y A A Y (2) f m and ϕ are homotopic rel A (i.e. via a homotopy whose restriction to A is constant.) | Y (3) f is L-Lipschitz. A ≤ (4) Dil(ϕ) L. → ∗ (cid:39) Then f is homotopic rel A to a C(L + 1)-Lipschitz map g : X Y such that g m ϕ via a Y homotopy M∗ → ∗ ⊗ (cid:104) (cid:105) Φ : Ω (X) t, dt Y ≤ whose restriction to A is constant, such that Dil (Φ) C(L + 1). The constant C depends on Y , 1/L m , and the norms on indecomposables, as well as n (but not anything else about X.) Y As stated in the introduction, we wMan∗t to∗s(cid:8)ay that this mea(cid:9)ns that pullbacks of genuine maps have reasonably high density in Hom( , Ω X) when it is endowed with a metric of the form Y (cid:39) Φ d(ϕ, ψ) = inf size(Φ) : ϕ ψ , for some notion of size. However, there is some diﬃculty in deﬁning an appropriate such notion— that is, we would like the size of a constant homotopy to be zero and the notion of distance to be nondegenerate, and this is already nontrivial. One(cid:0)n(cid:82)otio(cid:1)n that does the job (its nondegeneracy follows from (3.2)) is the formal length, given by 1 length(Φ) = Dil Φ . 0 Under this metric, the theorem states that there is a pullback of a genuine map within distance O(L) of any homomorphism with dilatation L which lies in the homotopy class of the pullback of a genuine map. Put this way, this is a nontrivial statement since the set of all homomorphisms with ≤ dilatation L has diameter which is in general some polynomial in L; this polynomial is linear only when Y has ﬁnite homotopy groups up to dimension n. Unfortunately, the formal length does not correspond well to the length of a genuine homotopy, or, as far as I can tell, any geometric invariant of genuine maps. In particular, as shown in [CaSi] and again in this paper in Theorem 5.4, when the space Map(X, Y ) is equipped with the metric given by the optimal length of a homotopy, it actually has ﬁnite diameter. Proof. By subdividing (X, A) at scale 1/L and rescaling so that simplices are unit size, we may assume L = 1; here we implicitly use the uniformity of the result with respect to the large-scale geometry of X. At the cost of increasing the Lipschitz constant again to some C = C (n, Y ), we may also | ⊂ 0 0 ∗ assume that f is mosaic with respect to a ﬁxed shard complex Z ∆Y with Z(1) = . To reduce A to this case, we modify both f and ϕ on the star st(A), which we equip with a facewise linear deformation retraction to A, × → π : st(A) [0, 1] st(A), → (cid:55)→ (cid:55)→ × → and a simplexwise linear map τ : st(A) [0, 1] sending A 0 and lk(A) 1. Let H : A [0, 1] Y be a C(n, Y )-Lipschitz homotopy to a C(n, Y )-Lipschitz mosaic map on some chosen shard complex. (Such a homotopy can be constructed by simplicially approximating on a complex which 19

text: The

text: shadowing

text: principle

text: Theorem

text: (The

text: shadowing

text: principle).

text: Let

text: (X,

text: A)

text: be

text: an

text: n-dimensional

text: simplicial

text: pair

text: with

text: the

text: standard

text: metric

text: on

text: simplices

text: and

text: Y

text: a

text: simply

text: connected

text: compact

text: Riemannian

text: manifold

text: with

text: bound-

text: M∗

text: ary

text: which

text: has

text: a

text: minimal

text: model

text: m

text: Ω

text: Y

text: Fix

text: norms

text: on

text: the

text: spaces

text: V

text: of

text: k-dimensional

text: M∗

text: Y→

text: Y

text: M∗

text: k

text: indecomposables

text: of

text: Let

text: f

text: X

text: Y

text: be

text: a

text: map

text: and

text: ϕ

text: Ω

text: X

text: a

text: homomorphism

text: such

text: that

label: list

text: Y

text: Y

text: M∗

text: f

text: m

text: ϕ

text: (i.e.

text: the

text: homomorphisms

text: restrict

text: to

text: the

text: same

text: homomorphism

text: Ω

text: A.)

text: Y

text: A

text: A

text: Y

text: f

text: m

text: and

text: ϕ

text: are

text: homotopic

text: rel

text: A

text: (i.e.

text: via

text: a

text: homotopy

text: whose

text: restriction

text: to

text: A

text: is

text: constant.)

text: Y

text: f

text: is

text: L-Lipschitz.

text: A

text: Dil(ϕ)

text: L.

text: Then

text: f

text: is

text: homotopic

text: rel

text: A

text: to

text: a

text: C(L

text: map

text: g

text: X

text: Y

text: such

text: that

text: g

text: m

text: ϕ

text: via

text: a

text: Y

text: homotopy

text: M∗

text: Φ

text: Ω

text: (X)

text: t,

text: dt

text: Y

text: whose

text: restriction

text: to

text: A

text: is

text: constant,

text: such

text: that

text: Dil

text: (Φ)

text: C(L

text: The

text: constant

text: C

text: depends

text: on

text: Y

text: m

text: and

text: the

text: norms

text: on

text: indecomposables,

text: as

text: well

text: as

text: n

text: (but

text: not

text: anything

text: else

text: about

text: X.)

text: Y

text: As

text: stated

text: in

text: the

text: introduction,

text: we

text: wMan∗t

text: that

text: this

text: that

text: pullbacks

text: of

text: genuine

text: maps

text: have

text: reasonably

text: high

text: density

text: in

text: Hom(

text: Ω

text: X)

text: when

text: it

text: is

text: endowed

text: with

text: a

text: metric

text: of

text: the

text: form

text: Y

text: Φ

text: d(ϕ,

text: ψ)

text: inf

text: size(Φ)

text: ϕ

text: ψ

text: for

text: some

text: notion

text: of

text: size.

text: However,

text: there

text: is

text: some

text: diﬃculty

text: in

text: deﬁning

text: an

text: appropriate

text: such

text: notion—

text: that

text: is,

text: we

text: would

text: like

text: the

text: size

text: of

text: a

text: constant

text: homotopy

text: to

text: be

text: zero

text: and

text: the

text: notion

text: of

text: distance

text: to

text: be

text: nondegenerate,

text: and

text: this

text: is

text: already

text: nontrivial.

text: that

text: does

text: the

text: job

text: (its

text: nondegeneracy

text: follows

text: from

text: is

text: the

text: formal

text: length,

text: given

text: by

text: length(Φ)

text: Dil

text: Φ

text: Under

text: this

text: metric,

text: the

text: theorem

text: states

text: that

text: there

text: is

text: a

text: pullback

text: of

text: a

text: genuine

text: map

text: within

text: distance

text: O(L)

text: of

text: any

text: homomorphism

text: with

text: dilatation

text: L

text: which

text: lies

text: in

text: the

text: homotopy

text: class

text: of

text: the

text: pullback

text: of

text: a

text: genuine

text: map.

text: Put

text: this

text: way,

text: this

text: is

text: a

text: nontrivial

text: statement

text: since

text: the

text: set

text: of

text: all

text: homomorphisms

text: with

text: dilatation

text: L

text: has

text: diameter

text: which

text: is

text: in

text: general

text: some

text: polynomial

text: in

text: L;

text: this

text: polynomial

text: is

text: linear

text: only

text: when

text: Y

text: has

text: ﬁnite

text: homotopy

text: groups

text: up

text: to

text: dimension

text: n.

text: Unfortunately,

text: the

text: formal

text: length

text: does

text: not

text: correspond

text: well

text: to

text: the

text: length

text: of

text: a

text: genuine

text: homotopy,

text: or,

text: as

text: far

text: as

text: I

text: can

text: tell,

text: any

text: geometric

text: invariant

text: of

text: genuine

text: maps.

text: In

text: particular,

text: as

text: shown

text: in

text: [CaSi]

text: and

text: again

text: in

text: this

text: paper

text: in

text: Theorem

text: when

text: the

text: space

text: Map(X,

text: Y

text: is

text: equipped

text: with

text: the

text: metric

text: given

text: by

text: the

text: optimal

text: length

text: of

text: a

text: homotopy,

text: it

text: actually

text: has

text: ﬁnite

text: diameter.

text: Proof.

text: By

text: subdividing

text: (X,

text: A)

text: at

text: scale

text: and

text: rescaling

text: so

text: that

text: simplices

text: are

text: unit

text: size,

text: we

text: may

text: assume

text: L

text: here

text: we

text: implicitly

text: use

text: the

text: uniformity

text: of

text: the

text: result

text: with

text: respect

text: to

text: the

text: large-scale

text: geometry

text: of

text: X.

text: At

text: the

text: cost

text: of

text: increasing

text: the

text: Lipschitz

text: constant

text: again

text: to

text: some

text: C

text: C

text: (n,

text: Y

text: we

text: may

text: also

text: assume

text: that

text: f

text: is

text: mosaic

text: with

text: respect

text: to

text: a

text: ﬁxed

text: shard

text: complex

text: Z

text: ∆Y

text: with

text: To

text: reduce

text: A

text: to

text: this

text: case,

text: we

text: modify

text: both

text: f

text: and

text: ϕ

text: on

text: the

text: star

text: st(A),

text: which

text: we

text: equip

text: with

text: a

text: facewise

text: linear

text: deformation

text: retraction

text: to

text: A,

text: π

text: st(A)

text: st(A),

text: and

text: a

text: simplexwise

text: linear

text: map

text: τ

text: st(A)

text: sending

text: A

text: and

text: lk(A)

text: Let

text: H

text: A

text: Y

text: be

text: a

text: C(n,

text: Y

text: )-Lipschitz

text: homotopy

text: to

text: a

text: C(n,

text: Y

text: )-Lipschitz

text: mosaic

text: map

text: on

text: some

text: chosen

text: shard

text: complex.

text: (Such

text: a

text: homotopy

text: can

text: be

text: constructed

text: by

text: simplicially

text: approximating

text: on

text: a

text: complex

text: which