text: This is non–trivial, and uses the fact that R(z) satisﬁes the Yang–Baxter equation. A stronger ⊗ statement holds as well: if P+ denotes the projection from V l onto the sub–representation V , then 1 l ⊗ − · · · − ⊗ ⊗ − · · · − (P+ id)R (zq1 l) R (zql 1)(P+ id) = (P+ id)R (zq1 l) R (zql 1) (22) 1,l+1 l,l+1 1,l+1 l,l+1 ⊗ − · · · − ⊗ − · · · − ⊗ = (P+ id)R (zql 1) R (zq1 l)(P+ id) = R (zql 1) R (zq1 l)(P+ id) 1,l+1 l,l+1 1,l+1 l,l+1 ⊗ as operators from V l to V . See equations (16)–(18) of [KuReSk81]. 1 l 2.6 Relationship to previous results 2.6.1 The [CGRS15] framework In [CGRS15], the authors lay out a framework for constructing interacting particle systems with U ∈ U duality functions from a quantum group (g) and a central element C (g). There is some overlap q q between the argument here: for example, the construction of the duality function is identical. Despite these similarities, there are still two diﬀerences worth noting. In [CGRS15], the relevant ∈ U information about the central element C is that its co–product commutes with ∆(u) for any u (g): q ∆(C)∆(u) = ∆(u)∆(C). By comparing with (3), one can think of Rˇ(z) as taking the role of ∆(C). However, in (3), the maps ⊗ permute the order of V V , which was not the case before in [CGRS15]. l m Another diﬀerence occurs through (5). In [CGRS15], it is assumed that ∆(C) is self–adjoint. In − [Kuan16], this assumption is weakened so that B 1∆(C)B is self–adjoint for some diagonal matrix B. In the situation here, R(z) needs to be conjugated by a non–diagonal matrix, the charge reversal matrix, to obtain a self–adjoint operator. Note that a formula similar to (5) appears as (34) in [PovPri06]. Indeed, (5) can be interpreted as charge–time symmetry, and is used as such in [BCPS15]. 2.6.2 Single–species stochastic vertex model from [BorPet16, CorPet16] The stochastic matrices S˚ from [CorPet16] have the expression (after substituting q with q2) − 1 + αq2g − α(1 q2g) S˚ (g, 0; g, 0) = , S˚ (g, 0; g 1, 1) = (23) α 1 + α α 1 + α − 1 µ2q2g α + µ2q2g S˚ (g, 1; g + 1, 0) = , S˚ (g, 1; g, 1) = α 1 + α α 1 + α Here, g is the number of particles at a lattice site, with either 0 or 1 particles entering in the auxiliary − − space. These are also the expressions from [BorPet16] with α = su and µ = s. For µ = q m, S˚ can ⊗ α be viewed as a stochastic operator from V V to itself. In general, it can be viewed as a stochastic ⊗ 1 m operator from V V¯∞ to itself. 1 The fusio{n pr}ocedure from [CorPet16] is {writt(cid:40)en }in the following way. Deﬁne the matrix Ξ, with rows indexed by 0, 1 l and columns indexed by 0, . . . , l , which has entries 1, h = h + . . . + h , Ξ((h , . . . , h ), h) = (cid:54) 1 l 1 l 0, h = h + . . . + h . 1 l { } It is immediate that{Ξ is}a stochastic matrix. Deﬁ(cid:89)ne the matrix Λ, with rows indexed by 0, . . . , l and columns indexed by 0, 1 l, which has entries4 Z−1 q−2y, h = h + . . . + h , h 1 l Λ(h, (h1, . . . , hl)) = y:hy=1 (cid:54) 0, h = h + . . . + h . (cid:81) 1 l (cid:81) ⊗ ⊗ 4In [CorPet16], the auxiliary space is written on the righ−t, in the sense that the operators act on Vm Vl instead of Vl Vm. Reversing the order of the tensor products results in q 2y in the deﬁnition of Λ, instead of q2y. It also results in the reversal of the operators S˚ in (24). 16 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: This

text: is

text: non–trivial,

text: and

text: uses

text: the

text: fact

text: that

text: R(z)

text: satisﬁes

text: the

text: Yang–Baxter

text: equation.

text: A

text: stronger

text: statement

text: holds

text: as

text: well:

text: if

text: P+

text: denotes

text: the

text: projection

text: from

text: V

text: l

text: onto

text: the

text: sub–representation

text: V

text: then

text: l

text: (P+

text: id)R

text: l)

text: R

text: (zql

text: id)

text: (P+

text: id)R

text: l)

text: R

text: (zql

text: (P+

text: id)R

text: (zql

text: R

text: l)(P+

text: id)

text: R

text: (zql

text: R

text: l)(P+

text: id)

text: as

text: operators

text: from

text: V

text: l

text: to

text: V

text: See

text: equations

text: of

text: l

text: Relationship

text: to

text: previous

text: results

text: The

text: framework

text: In

text: the

text: authors

text: lay

text: out

text: a

text: framework

text: for

text: constructing

text: interacting

text: particle

text: systems

text: with

text: U

text: U

text: duality

text: functions

text: from

text: a

text: quantum

text: group

text: (g)

text: and

text: a

text: central

text: element

text: C

text: (g).

text: There

text: is

text: some

text: overlap

text: q

text: q

text: between

text: the

text: argument

text: here:

text: for

text: example,

text: the

text: construction

text: of

text: the

text: duality

text: function

text: is

text: identical.

text: Despite

text: these

text: similarities,

text: there

text: are

text: still

text: two

text: diﬀerences

text: worth

text: noting.

text: In

text: the

text: relevant

text: U

text: information

text: about

text: the

text: central

text: element

text: C

text: is

text: that

text: its

text: co–product

text: commutes

text: with

text: ∆(u)

text: for

text: any

text: u

text: (g):

text: q

text: ∆(C)∆(u)

text: ∆(u)∆(C).

text: By

text: comparing

text: with

text: one

text: can

text: think

text: of

text: Rˇ(z)

text: as

text: taking

text: the

text: role

text: of

text: ∆(C).

text: However,

text: in

text: the

text: maps

text: permute

text: the

text: order

text: of

text: V

text: V

text: which

text: was

text: not

text: the

text: case

text: before

text: in

text: l

text: m

text: Another

text: diﬀerence

text: occurs

text: through

text: In

text: it

text: is

text: assumed

text: that

text: ∆(C)

text: is

text: self–adjoint.

text: In

text: this

text: assumption

text: is

text: weakened

text: so

text: that

text: B

text: is

text: self–adjoint

text: for

text: some

text: diagonal

text: matrix

text: B.

text: In

text: the

text: situation

text: here,

text: R(z)

text: needs

text: to

text: be

text: conjugated

text: by

text: a

text: non–diagonal

text: matrix,

text: the

text: charge

text: reversal

text: matrix,

text: to

text: obtain

text: a

text: self–adjoint

text: operator.

text: Note

text: that

text: a

text: formula

text: similar

text: to

text: appears

text: as

text: in

text: Indeed,

text: can

text: be

text: interpreted

text: as

text: charge–time

text: symmetry,

text: and

text: is

text: used

text: as

text: such

text: in

text: Single–species

text: stochastic

text: vertex

text: model

text: from

text: The

text: stochastic

text: matrices

text: S˚

text: from

text: have

text: the

text: expression

text: (after

text: substituting

text: q

text: with

text: S˚

text: (g,

text: g,

text: S˚

text: (g,

text: g

text: α

text: α

text: α

text: α

text: α

text: S˚

text: (g,

text: g

text: S˚

text: (g,

text: g,

text: α

text: α

text: α

text: α

text: Here,

text: g

text: is

text: the

text: number

text: of

text: particles

text: at

text: a

text: lattice

text: site,

text: with

text: either

text: or

text: particles

text: entering

text: in

text: the

text: auxiliary

text: space.

text: These

text: are

text: also

text: the

text: expressions

text: from

text: with

text: α

text: su

text: and

text: µ

text: s.

text: For

text: µ

text: q

text: m,

text: S˚

text: can

text: α

text: be

text: viewed

text: as

text: a

text: stochastic

text: operator

text: from

text: V

text: V

text: to

text: itself.

text: In

text: general,

text: it

text: can

text: be

text: viewed

text: as

text: a

text: stochastic

text: m

text: operator

text: from

text: V

text: V¯∞

text: to

text: itself.

text: The

text: fusio{n

text: pr}ocedure

text: from

text: is

text: }in

text: the

text: following

text: way.

text: Deﬁne

text: the

text: matrix

text: Ξ,

text: with

text: rows

text: indexed

text: by

text: l

text: and

text: columns

text: indexed

text: by

text: l

text: which

text: has

text: entries

text: h

text: h

text: h

text: Ξ((h

text: h

text: h)

text: l

text: l

text: h

text: h

text: h

text: l

text: It

text: is

text: immediate

text: that{Ξ

text: is}a

text: stochastic

text: matrix.

text: the

text: matrix

text: Λ,

text: with

text: rows

text: indexed

text: by

text: l

text: and

text: columns

text: indexed

text: by

text: l,

text: which

text: has

text: Z−1

text: h

text: h

text: h

text: h

text: l

text: Λ(h,

text: hl))

text: h

text: h

text: h

text: l

text: the

text: auxiliary

text: space

text: is

text: written

text: on

text: the

text: righ−t,

text: in

text: the

text: sense

text: that

text: the

text: operators

text: act

text: on

text: Vm

text: Vl

text: instead

text: of

text: Vl

text: Vm.

text: Reversing

text: the

text: order

text: of

text: the

text: tensor

text: products

text: results

text: in

text: q

text: in

text: the

text: deﬁnition

text: of

text: Λ,

text: instead

text: of

text: It

text: also

text: results

text: in

text: the

text: reversal

text: of

text: the

text: operators

text: S˚

text: in

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:40) Furthermore, assuming q > 1, then 1, if k = n + 1, lim S(0)(cid:15)k,δ = m→∞ (cid:15)j,β 0, if k < n + 1. Theorem 3.2 will show that these two items are true for general values of l. • → − → − (cid:0) (cid:1) Also, under the inversions z (cid:12) z 1, q  q 1 and charge reversal, (cid:12) (cid:0) (cid:1) (cid:12) q2β[1,n+2−k]−m+1 1(cid:0)− q−2βn+2−k+(cid:1)m−1z , if k = j, − − (cid:48) (cid:48) − − (qm+1 z)S(z 1)(cid:15)(cid:15)k(cid:48)j,,βδ(cid:48) q→q−1 = −qq22ββ[[11,,nn++11−−kk]]−zm1+1 q12−βn+q22β−nk+2,−k , iiff kk <> jj,, which are similar expressions to the entries of S(z). See Theorem 3.7 for a precise statement which holds for general values of l. • → ∞ (cid:40) If the m limit is taken ﬁrst, then (assuming q > 1 and z is ﬁnite) 1, if k = n + 1, S(z)(cid:15)k,δ = (cid:15)j,β 0, if k < n + 1. → ∞ If q < 1, then in the m limit, the result is no longer stochastic. 3.1.2 At m = 1 ≥  Now ﬁx m = 1 and let l 0. By(10) and the gau−ge t−ransfo−rmation, ql−2α[1,k−1]+1 1 q 2α−k+l 1z , if k = j S(z)γα,,(cid:15)(cid:15)kj = −q2l−2α[1,k] z(q1l−+−1qq−l+2α1zk),z if k > j, − − 1 q2αk ql 2α[1,k]+1 − , if k < j. ql+1 z In order for−parallel update to be possible, these expressions cannot depend on j, which only happens when z = q l+1. This can be rewritten as  − − − − 1 q 2αk+l 1z, if k = j S(z)γα,,(cid:15)(cid:15)kj = ql q2lα+[11,k−−1z]+1 × ql−−1z(−1 − q−2αk), if k > j, (1 q 2αk), if k < j. As→in∞the previous section, there are a fewinteresting degenerations. If 0 < q < 1, then in the limit z , the resulting stochastic matrix hasentries − q2l 2α[1,k], if k = j − − zl→im∞ S(z)γα,,(cid:15)(cid:15)kj = q2l 2α[1,k](1 q2αk), if k > j, 0, if k < j. (cid:40) If l is then taken to inﬁnity, the limit is 1 if k = n + 1 lim lim S(z)γ,(cid:15)k = l→∞ z→∞ α,(cid:15)j 0, if k < n + 1.  If z = 0, then − q 2α[1,k−1], if k = j S(0)γ,(cid:15)k = 0, if k > j, α,(cid:15)j − − − q 2α[1,k−1](1 q 2αk), if k < j. 18 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: list

text: Furthermore,

text: assuming

text: q

text: then

text: if

text: k

text: n

text: lim

text: m→∞

text: if

text: k

text: n

text: Theorem

text: will

text: show

text: that

text: these

text: two

text: items

text: are

text: true

text: for

text: general

text: values

text: of

text: l.

text: Also,

text: under

text: the

text: inversions

text: z

text: z

text: q

text: q

text: and

text: charge

text: reversal,

text: if

text: k

text: j,

text: z)S(z

text: iiff

text: kk

text: jj,,

text: which

text: are

text: similar

text: expressions

text: to

text: the

text: entries

text: of

text: S(z).

text: See

text: Theorem

text: for

text: a

text: precise

text: statement

text: which

text: holds

text: for

text: general

text: values

text: of

text: l.

text: If

text: the

text: m

text: limit

text: is

text: taken

text: ﬁrst,

text: then

text: (assuming

text: q

text: and

text: z

text: is

text: ﬁnite)

text: if

text: k

text: n

text: if

text: k

text: n

text: If

text: q

text: then

text: in

text: the

text: m

text: limit,

text: the

text: result

text: is

text: no

text: longer

text: stochastic.

text: At

text: m

text: Now

text: ﬁx

text: m

text: and

text: let

text: l

text: By(10)

text: and

text: the

text: gau−ge

text: t−ransfo−rmation,

text: q

text: if

text: k

text: j

text: −q2l−2α[1,k]

text: if

text: k

text: j,

text: ql

text: if

text: k

text: j.

text: z

text: In

text: order

text: for−parallel

text: update

text: to

text: be

text: possible,

text: these

text: expressions

text: cannot

text: depend

text: on

text: j,

text: which

text: only

text: happens

text: when

text: z

text: q

text: This

text: can

text: be

text: rewritten

text: as

text: 1

text: q

text: if

text: k

text: j

text: ql

text: if

text: k

text: j,

text: q

text: if

text: k

text: j.

text: As→in∞the

text: previous

text: section,

text: there

text: are

text: a

text: fewinteresting

text: degenerations.

text: If

text: q

text: then

text: in

text: the

text: limit

text: z

text: the

text: resulting

text: stochastic

text: matrix

text: hasentries

text: if

text: k

text: j

text: zl→im∞

text: if

text: k

text: j,

text: if

text: k

text: j.

text: If

text: l

text: is

text: then

text: taken

text: to

text: inﬁnity,

text: the

text: limit

text: is

text: if

text: k

text: n

text: lim

text: lim

text: l→∞

text: z→∞

text: if

text: k

text: n

text: If

text: z

text: then

text: q

text: if

text: k

text: j

text: if

text: k

text: j,

text: q

text: q

text: if

text: k

text: j.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Y Y Y∗ − Y − Because and are stochastic, the operators ( Id) and ( Id) satisfy the property that rev rev the oﬀ–diagonal entries are non–negative and the columns sum to 0. Therefore, they are generators for { − } a continuous–time process on particle conﬁgurations on the lattice 2, . . . , L 1 . Because they can be written as a sum of local generators, the process is a zero–range process. Theorem 3.2(b) establishes that L if w = 0 in the deﬁnition of x, the process is nontrivial. Indeed, it will be seen below that for l = 1, x the process is the multi-species q–Boson process of [Take15]. Remark 4.15. The use of subtracting the identity matrix to obtain a continuous–time process with duality from a discrete–time process with duality is not new: see e.g. section 5.2 of [Sch97]. Remark 4.16. A continuous–time zero–range process must allow an arbitrary number of particles to occupy a lattice site. Indeed, the jump rates for a particle jump from lattice site x to x+1 cannot depend on the occupancy at the site x + 1, which implies that there can not be a constraint on the number of particles allowed to occupy site x + 1. 5 Descriptions of processes U This section describes the processes that can be deﬁned from the stochastic (A(1)) vertex model. q n See Figure 2. − 5.1 At z = ql m (cid:0) (cid:1) − ⊗ − − At z = ql m, the operator S(z) acting on V V is meromorphic in λ = q l and µ = q m. l m ⊂ Z ⊗∞ Then Theorem 4.10 can be viewed as an identity holding on W n≥ which depends on the { } 0 parameters l, m ∈Z. In particular, both sides of the equation are also meromorphic functions in the x x− − ≥ complex variables λ 1 = ql, µ 1 = qmx. Since the equality holds for all l, m 0, it holds on the set { } x x q, q2, q3, . . . , which as 0 as a limit point. Therefore, the equality holds for all values of λ and µ . x Theorem 5.1. The n–species discrete–time q–Hahn Boson process satisﬁes space–reversed self–duality (cid:20) (cid:21) with respect to t(cid:89)he function D in (14), given(cid:89)explicitly by µ (cid:80) − − (cid:104)ξ|Dµ(u0)|η(cid:105) = x∈Z[η1x]!q · · · [ηnx]!q[mx − η[x1,n]]!q i=n1 mx ηη[x1nx,+n−1−i]i ξ[x1,i] q q−ξix( z>x 2η[z1,n+1−i]+η[x1,n+1−i]), − where m is deﬁned by q mx = µ . Here, η evolves to the left and ξ evolves to the right. x x This theorem implies dualities for two degenerations: Corollary 5.2. The n–species continuous–time q–Hahn Boson process satisﬁes space–reversed self– duality with respect to D . µ Proof. Observe that the duality D does n(cid:88)ot depend (cid:88)on λ and only on µ. Therefore if we take Theorem 5.1 and diﬀerentiate with respect to λ, then L∗ L D = D x x rev x x The next corollary was previously shown in Theorem 2.5(b) of [Kuan16]. Corollary 5.3. The n–species q–TAZRP of [Take15] is dual to its space–reversed version with respect (cid:89) (cid:89) to the duality function D0 deﬁned by (cid:16)(cid:80) (cid:17) (cid:104)ξ|D0|η(cid:105) = n qξix y≤x 2η[y1,n+1−i] . ∈Z x i=1 Here, the η process evolves to the left and the ξ process evolves to the right. 40 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Y

label: paragraph

text: Y

text: Y∗

text: Y

text: Because

text: and

text: are

text: stochastic,

text: the

text: operators

text: Id)

text: and

text: Id)

text: satisfy

text: the

text: property

text: that

text: rev

text: rev

text: the

text: oﬀ–diagonal

text: entries

text: are

text: non–negative

text: and

text: the

text: columns

text: sum

text: to

text: Therefore,

text: they

text: are

text: generators

text: for

text: a

text: continuous–time

text: process

text: on

text: particle

text: conﬁgurations

text: on

text: the

text: lattice

text: L

text: Because

text: they

text: can

text: be

text: written

text: as

text: a

text: sum

text: of

text: local

text: generators,

text: the

text: process

text: is

text: a

text: zero–range

text: process.

text: Theorem

text: establishes

text: that

text: L

text: if

text: w

text: in

text: the

text: deﬁnition

text: of

text: x,

text: the

text: process

text: is

text: nontrivial.

text: Indeed,

text: it

text: will

text: be

text: seen

text: below

text: that

text: for

text: l

text: x

text: the

text: process

text: is

text: the

text: multi-species

text: q–Boson

text: process

text: of

text: Remark

text: The

text: use

text: of

text: subtracting

text: the

text: identity

text: matrix

text: to

text: obtain

text: a

text: continuous–time

text: process

text: with

text: duality

text: from

text: a

text: discrete–time

text: process

text: with

text: duality

text: is

text: not

text: new:

text: see

text: e.g.

text: section

text: of

text: Remark

text: A

text: continuous–time

text: zero–range

text: process

text: must

text: allow

text: an

text: arbitrary

text: number

text: of

text: particles

text: to

text: occupy

text: a

text: lattice

text: site.

text: Indeed,

text: the

text: jump

text: rates

text: for

text: a

text: particle

text: jump

text: from

text: lattice

text: site

text: x

text: to

text: cannot

text: depend

text: on

text: the

text: occupancy

text: at

text: the

text: site

text: x

text: which

text: implies

text: that

text: there

text: can

text: not

text: be

text: a

text: constraint

text: on

text: the

text: number

text: of

text: particles

text: allowed

text: to

text: occupy

text: site

text: x

text: Descriptions

text: of

text: processes

text: U

text: This

text: section

text: describes

text: the

text: processes

text: that

text: can

text: be

text: deﬁned

text: from

text: the

text: stochastic

text: vertex

text: model.

text: q

text: n

text: See

text: Figure

text: At

text: z

text: ql

text: m

text: At

text: z

text: ql

text: m,

text: the

text: operator

text: S(z)

text: acting

text: on

text: V

text: V

text: is

text: meromorphic

text: in

text: λ

text: q

text: l

text: and

text: µ

text: q

text: m.

text: l

text: m

text: Z

text: Then

text: Theorem

text: can

text: be

text: viewed

text: as

text: an

text: identity

text: holding

text: on

text: W

text: n≥

text: which

text: depends

text: on

text: the

text: parameters

text: l,

text: m

text: ∈Z.

text: In

text: particular,

text: both

text: sides

text: of

text: the

text: equation

text: are

text: also

text: meromorphic

text: functions

text: in

text: the

text: x

text: x−

text: complex

text: variables

text: λ

text: ql,

text: µ

text: qmx.

text: Since

text: the

text: equality

text: holds

text: for

text: all

text: l,

text: m

text: it

text: holds

text: on

text: the

text: set

text: x

text: x

text: q,

text: which

text: as

text: as

text: a

text: limit

text: point.

text: Therefore,

text: the

text: equality

text: holds

text: for

text: all

text: values

text: of

text: λ

text: and

text: µ

text: x

text: Theorem

text: The

text: n–species

text: discrete–time

text: q–Hahn

text: Boson

text: process

text: satisﬁes

text: space–reversed

text: self–duality

text: with

text: respect

text: to

text: function

text: D

text: in

text: by

text: µ

text: [ηnx]!q[mx

text: mx

text: q

text: q−ξix(

text: z>x

text: where

text: m

text: is

text: deﬁned

text: by

text: q

text: mx

text: µ

text: Here,

text: η

text: evolves

text: to

text: the

text: left

text: and

text: ξ

text: evolves

text: to

text: the

text: right.

text: x

text: x

text: This

text: theorem

text: implies

text: dualities

text: for

text: two

text: degenerations:

text: Corollary

text: The

text: n–species

text: continuous–time

text: q–Hahn

text: Boson

text: process

text: satisﬁes

text: space–reversed

text: self–

text: duality

text: with

text: respect

text: to

text: D

text: µ

text: Proof.

text: Observe

text: that

text: the

text: duality

text: D

text: does

text: depend

text: λ

text: and

text: only

text: on

text: µ.

text: Therefore

text: if

text: we

text: take

text: Theorem

text: and

text: diﬀerentiate

text: with

text: respect

text: to

text: λ,

text: then

text: L∗

text: L

text: D

text: D

text: x

text: x

text: rev

text: x

text: x

text: The

text: next

text: corollary

text: was

text: previously

text: shown

text: in

text: Theorem

text: of

text: Corollary

text: The

text: n–species

text: q–TAZRP

text: of

text: is

text: dual

text: to

text: its

text: space–reversed

text: version

text: with

text: respect

text: to

text: the

text: duality

text: function

text: deﬁned

text: by

text: n

text: qξix

text: y≤x

text: ∈Z

text: x

text: Here,

text: the

text: η

text: process

text: evolves

text: to

text: the

text: left

text: and

text: the

text: ξ

text: process

text: evolves

text: to

text: the

text: right.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text:  By section , the entries of S(z) when m = 1 are − − − ql−2α[1,k−1]+1 1 q 2α−k+l 1z , if k = j S(z)γα,,(cid:15)(cid:15)kj = 1{α+(cid:15)j=δ+(cid:15)k} × −q2l−2α[1,k] z(q1l−+−1qq−l+2α1zk),z if k > j, − − 1 q2αk ql 2α[1,k]+1 − , if k < j. ql+1 z  → ∞ Consider the same degenerations as in the l = 1 case of the previous section. In the limit z , − q2l 2α[1,k], if k = j × − − zl→im∞ S(z)γα,,(cid:15)(cid:15)kj = 1{(cid:15)j+β=(cid:15)k+δ} q2l 2α[1,k](1 q2αk), if k > j, 0, if k < j.  When z = 0, then  − q 2α[1,k−1], if k = j × S(0)γ,(cid:15)k = 1{ } 0, if k > j, α,(cid:15)j (cid:15)j+β=(cid:15)k+δ − − − q 2α[1,k−1](1 q 2αk), if k < j. 5.4 Conjecture for general l, m, z For generic values of l, m and z, we know that a well–deﬁned process exists in both discrete and continuous–time, and that duality holds on both the inﬁnite line and for closed boundary conditions. Each lattice site can hold up to m particles, and up to l particles may jump at a time. Furthermore, for → ∞ − z = 0 and z , the strong blocking phenomenon occurs again, due to Theorem 3.2(a). At z = ql m, parallel updates occur, as shown in [KMMO16]. Due to the degeneration of multi–species ASEP(q, j) to the multi–species q–Boson shown in [Kuan16], it is not unreasonable to conjecture that a generalization must hold for all values of l. Namely, for each ≥ U l 1, there should exist a central element C of (gl ) such that the framework of [CGRS15] produces l q n+1 a continuous–time asymmetric exclusion process in which up to 2j particles may occupy a site and up → ∞ to l particles may jump simultaneously. In the limit j , the process should degenerate to the same totally asymmetric continuous–time zero range process produced by Section . Duality results should hold for both the asymmetric exclusion process and the totally asymmetric zero range process. 6 “Direct” results for multi–species q–Hahn Boson Theorem 5.1 shows that the multi–species q–Hahn Boson process satisﬁes space–reversed self–duality → with respect to D . Taking the limit µ 0 degenerates the multi–species q–Hahn Boson process to µ the multi–species q–Boson process, and shows that the latter process satisﬁes space–reversed self–duality with respect to D . 0 It turns out that the multi–species q–Hahn Boson process is also dual with respect to D , even before 0 taking the degenerations in the process. This statement will be proved in this section through direct means, as it is unclear how to prove it using algebraic machinery. First, start with some identities. 6.1 Identities ∈ Z | (cid:88)| ≤ ≤ Given β, γ n, recall the notation that β = β + . . . + β , write γ β to mean γ β for ≤ ≤ 1 n i i 1 i n, and that − χ = (β γ )γ , β,γ i i j ≤ ≤ 1 i<j n 43 ##LTLine## ##LTLine## ##LTLine##

text: By

text: section

text: the

text: entries

text: of

text: S(z)

text: when

text: m

text: are

text: q

text: if

text: k

text: j

text: −q2l−2α[1,k]

text: if

text: k

text: j,

text: ql

text: if

text: k

text: j.

text: z

text: Consider

text: the

text: same

text: degenerations

text: as

text: in

text: the

text: l

text: case

text: of

text: the

text: previous

text: section.

text: In

text: the

text: limit

text: z

text: if

text: k

text: j

text: zl→im∞

text: if

text: k

text: j,

text: if

text: k

text: j.

text: When

text: z

text: then

text: q

text: if

text: k

text: j

text: if

text: k

text: j,

text: q

text: q

text: if

text: k

text: j.

text: Conjecture

text: for

text: general

text: l,

text: m,

text: z

text: For

text: generic

text: values

text: of

text: l,

text: m

text: and

text: z,

text: we

text: know

text: that

text: a

text: well–deﬁned

text: process

text: exists

text: in

text: both

text: discrete

text: and

text: continuous–time,

text: and

text: that

text: duality

text: holds

text: on

text: both

text: the

text: inﬁnite

text: line

text: and

text: for

text: closed

text: boundary

text: conditions.

text: Each

text: lattice

text: site

text: can

text: hold

text: up

text: to

text: m

text: particles,

text: and

text: up

text: to

text: l

text: particles

text: may

text: jump

text: at

text: a

text: time.

text: Furthermore,

text: for

text: z

text: and

text: z

text: the

text: strong

text: blocking

text: phenomenon

text: occurs

text: again,

text: due

text: to

text: Theorem

text: At

text: z

text: ql

text: m,

text: parallel

text: updates

text: occur,

text: as

text: shown

text: in

text: Due

text: to

text: the

text: degeneration

text: of

text: multi–species

text: ASEP(q,

text: j)

text: to

text: the

text: multi–species

text: q–Boson

text: shown

text: in

text: it

text: is

text: not

text: unreasonable

text: to

text: conjecture

text: that

text: a

text: generalization

text: must

text: hold

text: for

text: all

text: values

text: of

text: l.

text: Namely,

text: for

text: each

text: U

text: l

text: there

text: should

text: exist

text: a

text: central

text: element

text: C

text: of

text: (gl

text: such

text: that

text: the

text: framework

text: of

text: produces

text: l

text: q

text: a

text: continuous–time

text: asymmetric

text: exclusion

text: process

text: in

text: which

text: up

text: to

text: particles

text: may

text: occupy

text: a

text: site

text: and

text: up

text: to

text: l

text: particles

text: may

text: jump

text: simultaneously.

text: In

text: the

text: limit

text: j

text: the

text: process

text: should

text: degenerate

text: to

text: the

text: same

text: totally

text: asymmetric

text: continuous–time

text: zero

text: range

text: process

text: produced

text: by

text: Section

text: Duality

text: results

text: should

text: hold

text: for

text: both

text: the

text: asymmetric

text: exclusion

text: process

text: and

text: the

text: totally

text: asymmetric

text: zero

text: range

text: process.

text: “Direct”

text: results

text: for

text: multi–species

text: q–Hahn

text: Boson

text: Theorem

text: shows

text: that

text: the

text: multi–species

text: q–Hahn

text: Boson

text: process

text: satisﬁes

text: space–reversed

text: self–duality

text: with

text: respect

text: to

text: D

text: Taking

text: the

text: limit

text: µ

text: degenerates

text: the

text: multi–species

text: q–Hahn

text: Boson

text: process

text: to

text: µ

text: the

text: multi–species

text: q–Boson

text: process,

text: and

text: shows

text: that

text: the

text: latter

text: process

text: satisﬁes

text: space–reversed

text: self–duality

text: with

text: respect

text: to

text: D

text: It

text: turns

text: out

text: that

text: the

text: multi–species

text: q–Hahn

text: Boson

text: process

text: is

text: also

text: dual

text: with

text: respect

text: to

text: D

text: even

text: before

text: taking

text: the

text: degenerations

text: in

text: the

text: process.

text: This

text: statement

text: will

text: be

text: proved

text: in

text: this

text: section

text: through

text: direct

text: means,

text: as

text: it

text: is

text: unclear

text: how

text: to

text: prove

text: it

text: using

text: algebraic

text: machinery.

text: First,

text: start

text: with

text: some

text: identities.

text: Identities

text: Z

text: Given

text: β,

text: γ

text: n,

text: recall

text: the

text: notation

text: that

text: β

text: β

text: β

text: write

text: γ

text: β

text: to

text: mean

text: γ

text: β

text: for

text: n

text: i

text: i

text: i

text: n,

text: and

text: that

text: χ

text: (β

text: γ

text: )γ

text: β,γ

text: i

text: i

text: j

text: i<j

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Note that one can also check that − − ⊗ ⊗ − ⊗ (z q2)(Rˇ(q 2) Id )(Id R(z))(Rˇ(q 2) Id ) 2 2 2 → has rank 2 at z q2, and that the resulting matrix satisﬁes − 1 q6 Q2 = Q. 1 + q2 A.2 S(z) for l = m = 2, n = 1 − For l = m = 2 and n = 1 the action of R(z) is given by (replacing z = αq4) | (cid:105) ⊗ | (cid:105) | (cid:105) ⊗ | (cid:105) | (cid:105) ⊗ | (cid:105) | (cid:105) ⊗ | (cid:105) R(z)( 02 02 ) = 02 02 , R(z)( 20 20 ) = 20 20 , − − | (cid:105) ⊗ | (cid:105) q 2(1 + αq4)| (cid:105) ⊗ | (cid:105) (1 q4)α| (cid:105) ⊗ | (cid:105) R(z)( 02 11 ) = 02 11 + 11 02 , 1 + α 1 + α − − | (cid:105) ⊗ | (cid:105) − (1 + αq4)(1 + αq6)| (cid:105) ⊗ | (cid:105) q 1(1 + q2)(1 q4)(1 + αq4)α| (cid:105) ⊗ | (cid:105) R(z)( 02 20 ) = q 4 02 20 + 11 11 (1 + αq2)(1 + α) (1 + αq2)(1 + α) − − (1 q2)(1 q4)q2α2 | (cid:105) ⊗ | (cid:105) + 20 02 , (1 + αq2)(1 + α) − − | (cid:105) ⊗ | (cid:105) α(1 q4)| (cid:105) ⊗ | (cid:105) q 2(1 + αq4)| (cid:105) ⊗ | (cid:105) R(z)( 11 20 ) = 20 11 + 11 20 , 1 + α 1 + α − − − − | (cid:105) ⊗ | (cid:105) −q 5(1 q2)(1 + αq4)| (cid:105) ⊗ | (cid:105) q6z 2q4z + q4 + q2z2 2q2z + z | (cid:105) ⊗ | (cid:105) R(z)( 11 11 ) = 02 20 + 11 11 (1 + αq2)(1 + α) (q2(1 + αq2))(q4(1 + α)) − − q 1(1 q2)(1 + αq4)α| (cid:105) ⊗ | (cid:105) + 20 02 , (1 + αq2)(1 + α) − | (cid:105) ⊗ | (cid:105) q2(1 + αq4)| (cid:105) ⊗ | (cid:105) − 1 q4 | (cid:105) ⊗ | (cid:105) R(z)( 11 02 ) = 11 02 02 11 , q4(1 + α) q4(1 + α) − − − | (cid:105) ⊗ | (cid:105) q 4(1 + αq4)(1 + αq6)| (cid:105) ⊗ | (cid:105) − q 5(1 + q2)(1 q4)(1 + αq4)| (cid:105) ⊗ | (cid:105) R(z)( 20 02 ) = 20 02 11 11 (1 + αq2)(1 + α) (1 + αq2)(1 + α) − − − (1 q2)(1 q4) | (cid:105) ⊗ | (cid:105) + q 6 02 20 , (1 + αq2)(1 + α) − − | (cid:105) ⊗ | (cid:105) q 2(1 + αq4)| (cid:105) ⊗ | (cid:105) − 1 q4 | (cid:105) ⊗ | (cid:105) R(z)( 20 11 ) = 20 11 11 20 , 1 + α q4(1 + α) | (cid:105) | (cid:105) where α with α = (α , α ) is denoted by α α . No(cid:102)w since 1 2 1 2 Ga(|α α (cid:105) ⊗ |β β (cid:105)) = q−α1β2|α α (cid:105) ⊗ |β β (cid:105), Ga−1(|α α (cid:105) ⊗ |β β (cid:105)) = qα2β1|α α (cid:105) ⊗ |β β (cid:105), 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 52 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Note

text: that

text: one

text: can

text: also

text: check

text: that

text: (z

text: Id

text: )(Id

text: R(z))(Rˇ(q

text: Id

text: has

text: rank

text: at

text: z

text: and

text: that

text: the

text: resulting

text: matrix

text: satisﬁes

text: Q.

label: section

text: S(z)

text: for

text: l

text: m

text: n

text: For

text: l

text: m

text: and

text: n

text: the

text: action

text: of

text: R(z)

text: is

text: given

text: by

text: (replacing

text: z

text: R(z)(

text: R(z)(

text: q

text: R(z)(

text: α

text: α

text: q

text: R(z)(

text: q

text: α)

text: α)

text: α)

text: q

text: R(z)(

text: α

text: α

text: −q

text: z

text: R(z)(

text: α)

text: α))

text: q

text: α)

text: R(z)(

text: α)

text: α)

text: q

text: q

text: R(z)(

text: α)

text: α)

text: q

text: α)

text: q

text: R(z)(

text: α

text: α)

text: where

text: α

text: with

text: α

text: (α

text: α

text: is

text: denoted

text: by

text: α

text: α

text: since

text: Ga(|α

text: α

text: |β

text: β

text: q−α1β2|α

text: α

text: |β

text: β

text: α

text: |β

text: β

text: α

text: |β

text: β

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: then the action of S(z) is | (cid:105) ⊗ | (cid:105) | (cid:105) ⊗ | (cid:105) | (cid:105) ⊗ | (cid:105) | (cid:105) ⊗ | (cid:105) S(z)( 02 02 ) = 02 02 , S(z)( 20 20 ) = 20 20 , − | (cid:105) ⊗ | (cid:105) 1 + αq4 | (cid:105) ⊗ | (cid:105) (1 q4)α| (cid:105) ⊗ | (cid:105) S(z)( 02 11 ) = 02 11 + 11 02 , 1 + α 1 + α − | (cid:105) ⊗ | (cid:105) (1 + αq4)(1 + αq6)| (cid:105) ⊗ | (cid:105) (1 + q2)(1 q4)(1 + αq4)α| (cid:105) ⊗ | (cid:105) S(z)( 02 20 ) = 02 20 + 11 11 (1 + αq2)(1 + α) (1 + αq2)(1 + α) − − (q2 q4)(1 q4)α2 | (cid:105) ⊗ | (cid:105) + 20 02 , (1 + αq2)(1 + α) − | (cid:105) ⊗ | (cid:105) α(1 q4)| (cid:105) ⊗ | (cid:105) 1 + αq4 | (cid:105) ⊗ | (cid:105) S(z)( 11 20 ) = 20 11 + 11 20 , 1 + α 1 + α − − − − | (cid:105) ⊗ | (cid:105) (1 q 2)(1 + αq4)| (cid:105) ⊗ | (cid:105) q6z 2q4z + q4 + q2z2 2q2z + z | (cid:105) ⊗ | (cid:105) S(z)( 11 11 ) = 02 20 + 11 11 (1 + αq2)(1 + α) q5(1 + αq2)(1 + α) − − (1 q2)(q 2 + αq2)α| (cid:105) ⊗ | (cid:105) + 20 02 , (1 + αq2)(1 + α) − − | (cid:105) ⊗ | (cid:105) 1 + αq4 | (cid:105) ⊗ | (cid:105) 1 q 4 | (cid:105) ⊗ | (cid:105) S(z)( 11 02 ) = 11 02 + 02 11 , q4(1 + α) 1 + α − − − − − | (cid:105) ⊗ | (cid:105) (q 4 + α)(q 4 + αq2)| (cid:105) ⊗ | (cid:105) (1 + q2)(1 q 4)(q 4 + α)| (cid:105) ⊗ | (cid:105) S(z)( 20 02 ) = 20 02 + 11 11 (1 + αq2)(1 + α) (1 + αq2)(1 + α) − − − − (1 q 2)(1 q 4)| (cid:105) ⊗ | (cid:105) + 02 20 , (1 + αq2)(1 + α) − − − | (cid:105) ⊗ | (cid:105) q 4 + α| (cid:105) ⊗ | (cid:105) 1 q 4 | (cid:105) ⊗ | (cid:105) S(z)( 20 11 ) = 20 11 + 11 20 , 1 + α 1 + α → − Up to q q1/2, with ν = q 2, these are the same weights as in Appendix B.2 of [CorPet16]. References [AnAsRo] G. E. Andrews, R. Askey, and R. Roy, Special Functions, vol. 71, Cambridge University Press, 2001. [Bar14] G. Barraquand, A short proof of a symmetry identity for the q–Hahn distribution, Electron. Commun. Probab. 19 (2014), no. 50, 1–3. DOI:10.1214/ECP.v19-3674 [BarCor16] G. Barraquand, I. Corwin, The q–Hahn asymmetric exclusion process, Ann. Appl. Probab, Vol. 26, No. 4 (2016), 2304–2356. [BelSch15] V. Belitsky, G.M. Schu¨tz, Self-Duality for the Two-Component Asymmetric Simple Exclusion Process, J. Math. Phys., 56, 083302 (2015), DOI: 10.1063/1.4929663 [BelSch15-2] V. Belitsky, G.M. Schu¨tz, Quantum algebra symmetry and reversible measures for the ASEP with second-class particles, J. Stat. Phys., November 2015, Volume 161, Issue 4, pp 821–842, DOI: 10.1007/s10955-015-1363-1 [BelSch16] V. Belitsky, G.M. Schu¨tz, Self-duality and shock dynamics in the n-component priority ASEP, arXiv:1606.04587v1 [BorCor13] A. Borodin, I. Corwin, Discrete time q–TASEPs. Int. Math. Res. Not. (rnt206), 05 2013. DOI:10.1093/imrn/rnt206 [BorCorGor16] A. Borodin, I. Corwin, V. Gorin, Stochastic six-vertex model, Duke Math. J. 165, no. 3 (2016), 563–624. DOI:10.1215/00127094-3166843 [BorCorSa14] A. Borodin, I. Corwin, T. Sasamoto, From duality to determinants for q–TASEP and ASEP, Ann. Probab. 2014, Vol. 42, No. 6, 2314–2382, DOI: 10.1214/13-AOP868 [BCPS15] A. Borodin, I. Corwin, L. Petrov, T. Sasamoto. Spectral theory for the q-Boson particle system. Compositio Mathematica, 151:1–67 (2015). [BorPet16] A. Borodin and L. Petrov. Higher spin six vertex model and symmetric rational functions, arXiv:1601.05770v1 53 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: then

text: the

text: action

text: of

text: S(z)

text: is

text: S(z)(

text: S(z)(

text: S(z)(

text: α

text: α

text: S(z)(

text: α)

text: α)

text: α)

text: S(z)(

text: α

text: α

text: q

text: z

text: S(z)(

text: α)

text: α)

text: α)

text: q

text: S(z)(

text: α)

text: α

text: (q

text: α)(q

text: q

text: α)|

text: S(z)(

text: α)

text: α)

text: q

text: q

text: α)

text: q

text: α|

text: q

text: S(z)(

text: α

text: α

text: Up

text: to

text: q

text: with

text: ν

text: q

text: these

text: are

text: the

text: same

text: weights

text: as

text: in

text: Appendix

text: of

text: References

text: [AnAsRo]

text: G.

text: E.

text: Andrews,

text: R.

text: Askey,

text: and

text: R.

text: Roy,

text: Special

text: Functions,

text: vol.

text: Cambridge

text: University

text: Press,

text: G.

text: Barraquand,

text: A

text: short

text: proof

text: of

text: a

text: symmetry

text: identity

text: for

text: the

text: q–Hahn

text: distribution,

text: Electron.

text: Commun.

text: Probab.

text: no.

text: G.

text: Barraquand,

text: I.

text: Corwin,

text: The

text: q–Hahn

text: asymmetric

text: exclusion

text: process,

text: Ann.

text: Appl.

text: Probab,

text: Vol.

text: No.

text: V.

text: Belitsky,

text: G.M.

text: Schu¨tz,

text: Self-Duality

text: for

text: the

text: Two-Component

text: Asymmetric

text: Simple

text: Exclusion

text: Process,

text: J.

text: Math.

text: Phys.,

text: DOI:

text: V.

text: Belitsky,

text: G.M.

text: Schu¨tz,

text: Quantum

text: algebra

text: symmetry

text: and

text: reversible

text: measures

text: for

text: the

text: ASEP

text: with

text: second-class

text: particles,

text: J.

text: Stat.

text: Phys.,

text: November

text: Volume

text: Issue

text: pp

text: DOI:

text: V.

text: Belitsky,

text: G.M.

text: Schu¨tz,

text: Self-duality

text: and

text: shock

text: dynamics

text: in

text: the

text: n-component

text: priority

text: ASEP,

text: A.

text: Borodin,

text: I.

text: Corwin,

text: Discrete

text: time

text: q–TASEPs.

text: Int.

text: Math.

text: Res.

text: Not.

text: A.

text: Borodin,

text: I.

text: Corwin,

text: V.

text: Gorin,

text: Stochastic

text: six-vertex

text: model,

text: Duke

text: Math.

text: J.

text: no.

text: A.

text: Borodin,

text: I.

text: Corwin,

text: T.

text: Sasamoto,

text: From

text: duality

text: to

text: determinants

text: for

text: q–TASEP

text: and

text: ASEP,

text: Ann.

text: Probab.

text: Vol.

text: No.

text: DOI:

text: A.

text: Borodin,

text: I.

text: Corwin,

text: L.

text: Petrov,

text: T.

text: Sasamoto.

text: Spectral

text: theory

text: for

text: the

text: q-Boson

text: particle

text: system.

text: Compositio

text: Mathematica,

text: A.

text: Borodin

text: and

text: L.

text: Petrov.

text: Higher

text: spin

text: six

text: vertex

text: model

text: and

text: symmetric

text: rational

text: functions,

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: (cid:48) ∈ P P × P whenever x , x are in the same block p(j) . Deﬁne the matrix T¯ by setting T¯ (p(j), p(i)) 0 0 0 0 0 1 0 0 0 1 to be the quantity above. × The composition o(cid:88)f lumpable matrices is a(cid:88)gain lu(cid:88)mpable. To see this, If T is a X X matrix which P P ∈ 1 1 2 is lumpable with respect to and , then for x p(k), 1 2 0 0 (T0T1)(x2, x0) = (cid:88) (cid:88) T0((cid:88)x2, x1)T1(x1, x0) x2∈p(2i) x2∈p(2i) x1∈X1 = (cid:88) (cid:88) T0(x2, x1)T1(x1, x0) p(1j)∈P1 x1∈p(1j) x2∈p(2i) = (cid:88) T¯0(p(2i), p(1j))T1(x1, x0) p(1j)∈P1 x1∈p(1j) = T¯ (p(i), p(j))T¯ (p(j), p(k)) 0 2 1 1 1 0 p(1j)∈P1 = T¯ T¯ (p(i), p(k)). 0 1 2 0 This does not depend on the choice of x in p(k), so T T is lumpable with T T = T¯ T¯ . 0 0 0 1 0 1 0 1 This is a generalization of a lumped Markov process introduced in [KeSn76]. The condition that a Markov process is lumpable is simply the condition that a projection of a Markov process is still Markov. There are more general conditions of interest: for example, [PitRog81] gives an intertwining condition in × which the projection is random. In particular, if T is a stochastic X X matrix, and Ξ is a stochastic × × 0 0 × 0 X X matrix, Λ is a stochastic X X matrix, then deﬁne the X X matrix 0 1 1 0 1 1 T = ΛT Ξ. 1 0 If ΛΞ is the identity matrix on X , and T , T satisfy the intertwining relation 1 0 1 ΛT = T Λ, 0 1 then Λ maps the Markov chain deﬁned by T to a well–deﬁned Markov chain deﬁned by T . 0 1 It is not hard to see that the Pitman–Rogers relation is a generalization of lumpability. if X is a P ∈ ∈ P 1 partition of X , pick an arbitrary element x(p) p for each p . Then deﬁne Ξ and Λ by 0 0 0 Ξ(x, p) = 1x=x(p), Λ(p, x(cid:88)) = 1x∈p. P P It is immediate that ΛΞ is the identity matrix on . If T is lumpable with respect to , then 0 0 0 T (p , p ) = (ΛT Ξ)(p , p ) = T (x, x(p )) 1 1 2 0 1 2 0 2 ∈ x p1 does not depend on the choic(cid:88)e of x(p), and(cid:88)is the transition matrix of the lumped Markov chain. Fur- ∈ thermore, the lumpability implies that for x q, ΛT (p, x) = T (y, x) = T (y, x(q)) = ΛT ΞΛ(p, x) = T Λ(p, x). 0 0 0 0 1 ∈ ∈ y p y p Remark 2.4. One example of a lumpable Markov process is n–species ASEP. In this process, there are n species of particles, and at most one particle may occupy a lattice site. One can think of each species as having a diﬀerent mass. If a particle attempts to jump to a site occupied with a heavier particle, then the jump is blocked. If a particle attempts to jump to a site occupied with a lighter particle, then the two particles switch places. All left jumps occur with the same rate (independent of the species), and likewise all the right jumps occur with the same rate (independent of the species). It is not hard to see that the projection onto the ﬁrst k species results in k–species ASEP, since each particle treats lighter particles the same as holes. This model was ﬁrst introduced in [Ligg76]. A more general model would allow the jump rates to depend on the species of the particles. In this case, the projection onto the ﬁrst k species is no longer a k–species ASEP. See [Ka99, Kuan15] for examples of multi–species ASEP which have jump rates depending on the species. With open boundary conditions, several models (see. e.g. [Can15, CFRV16, CGGW16, CoMaWi15, Man15, ManVie15, Uch08]) have jump rates at the boundaries which depend on the species, with jump rates in the bulk that are independent of the species. See also [CGW16, PEM09] for multi–species ASEP on a ring, with jump rates independent of the species. 9 ##LTLine##

text: P

text: P

text: P

text: whenever

text: x

text: x

text: are

text: in

text: the

text: same

text: block

text: p(j)

text: Deﬁne

text: the

text: matrix

text: T¯

text: by

text: setting

text: T¯

text: (p(j),

text: p(i))

text: to

text: be

text: the

text: quantity

text: above.

text: The

text: composition

text: lumpable

text: matrices

text: is

text: To

text: see

text: this,

text: If

text: T

text: is

text: a

text: X

text: X

text: matrix

text: which

text: P

text: P

text: is

text: lumpable

text: with

text: respect

text: to

text: and

text: then

text: for

text: x

text: p(k),

text: T¯

text: (p(i),

text: p(j))T¯

text: (p(j),

text: p(k))

text: T¯

text: T¯

text: (p(i),

text: p(k)).

text: This

text: does

text: not

text: depend

text: on

text: the

text: choice

text: of

text: x

text: in

text: p(k),

text: so

text: T

text: T

text: is

text: lumpable

text: with

text: T

text: T

text: T¯

text: T¯

text: This

text: is

text: a

text: generalization

text: of

text: a

text: lumped

text: Markov

text: process

text: introduced

text: in

text: The

text: condition

text: that

text: a

text: Markov

text: process

text: is

text: lumpable

text: is

text: simply

text: the

text: condition

text: that

text: a

text: projection

text: of

text: a

text: Markov

text: process

text: is

text: still

text: Markov.

text: There

text: are

text: more

text: general

text: conditions

text: of

text: interest:

text: for

text: example,

text: gives

text: an

text: intertwining

text: condition

text: in

text: which

text: the

text: projection

text: is

text: random.

text: In

text: particular,

text: if

text: T

text: is

text: a

text: stochastic

text: X

text: X

text: matrix,

text: and

text: Ξ

text: is

text: a

text: stochastic

text: X

text: X

text: matrix,

text: Λ

text: is

text: a

text: stochastic

text: X

text: X

text: matrix,

text: then

text: deﬁne

text: the

text: X

text: X

text: matrix

text: T

text: ΛT

text: Ξ.

text: If

text: ΛΞ

text: is

text: the

text: identity

text: matrix

text: on

text: X

text: and

text: T

text: T

text: satisfy

text: the

text: intertwining

text: relation

text: ΛT

text: T

text: Λ,

text: then

text: Λ

text: maps

text: the

text: Markov

text: chain

text: deﬁned

text: by

text: T

text: to

text: a

text: well–deﬁned

text: Markov

text: chain

text: deﬁned

text: by

text: T

text: It

text: is

text: not

text: hard

text: to

text: see

text: that

text: the

text: Pitman–Rogers

text: relation

text: is

text: a

text: generalization

text: of

text: lumpability.

text: if

text: X

text: is

text: a

text: P

text: P

text: partition

text: of

text: X

text: pick

text: an

text: arbitrary

text: element

text: x(p)

text: p

text: for

text: each

text: p

text: Then

text: deﬁne

text: Ξ

text: and

text: Λ

text: by

text: Ξ(x,

text: p)

text: Λ(p,

text: P

text: P

text: It

text: is

text: immediate

text: that

text: ΛΞ

text: is

text: the

text: identity

text: matrix

text: on

text: If

text: T

text: is

text: lumpable

text: with

text: respect

text: to

text: then

text: T

text: (p

text: p

text: (ΛT

text: Ξ)(p

text: p

text: T

text: (x,

text: x(p

text: x

text: does

text: not

text: depend

text: on

text: the

text: of

text: x(p),

text: the

text: transition

text: matrix

text: of

text: the

text: lumped

text: Markov

text: chain.

text: Fur-

text: thermore,

text: the

text: lumpability

text: implies

text: that

text: for

text: x

text: q,

text: ΛT

text: (p,

text: x)

text: T

text: (y,

text: x)

text: T

text: (y,

text: x(q))

text: ΛT

text: ΞΛ(p,

text: x)

text: T

text: Λ(p,

text: x).

text: y

text: p

text: y

text: p

text: Remark

text: One

text: example

text: of

text: a

text: lumpable

text: Markov

text: process

text: is

text: n–species

text: ASEP.

text: In

text: this

text: process,

text: there

text: are

text: n

text: species

text: of

text: particles,

text: and

text: at

text: most

text: one

text: particle

text: may

text: occupy

text: a

text: lattice

text: site.

text: One

text: can

text: think

text: of

text: each

text: species

text: as

text: having

text: a

text: diﬀerent

text: mass.

text: If

text: a

text: particle

text: attempts

text: to

text: jump

text: to

text: a

text: site

text: occupied

text: with

text: a

text: heavier

text: particle,

text: then

text: the

text: jump

text: is

text: blocked.

text: If

text: a

text: particle

text: attempts

text: to

text: jump

text: to

text: a

text: site

text: occupied

text: with

text: a

text: lighter

text: particle,

text: then

text: the

text: two

text: particles

text: switch

text: places.

text: All

text: left

text: jumps

text: occur

text: with

text: the

text: same

text: rate

text: (independent

text: of

text: the

text: species),

text: and

text: likewise

text: all

text: the

text: right

text: jumps

text: occur

text: with

text: the

text: same

text: rate

text: (independent

text: of

text: the

text: species).

text: It

text: is

text: not

text: hard

text: to

text: see

text: that

text: the

text: projection

text: onto

text: the

text: ﬁrst

text: k

text: species

text: results

text: in

text: k–species

text: ASEP,

text: since

text: each

text: particle

text: treats

text: lighter

text: particles

text: the

text: same

text: as

text: holes.

text: This

text: model

text: was

text: ﬁrst

text: introduced

text: in

text: A

text: more

text: general

text: model

text: would

text: allow

text: the

text: jump

text: rates

text: to

text: depend

text: on

text: the

text: species

text: of

text: the

text: particles.

text: In

text: this

text: case,

text: the

text: projection

text: onto

text: the

text: ﬁrst

text: k

text: species

text: is

text: no

text: longer

text: a

text: k–species

text: ASEP.

text: See

text: for

text: examples

text: of

text: multi–species

text: ASEP

text: which

text: have

text: jump

text: rates

text: depending

text: on

text: the

text: species.

text: With

text: open

text: boundary

text: conditions,

text: several

text: models

text: (see.

text: e.g.

text: have

text: jump

text: rates

text: at

text: the

text: boundaries

text: which

text: depend

text: on

text: the

text: species,

text: with

text: jump

text: rates

text: in

text: the

text: bulk

text: that

text: are

text: independent

text: of

text: the

text: species.

text: See

text: also

text: for

text: multi–species

text: ASEP

text: on

text: a

text: ring,

text: with

text: jump

text: rates

text: independent

text: of

text: the

text: species.

text: ##LTLine##


text: The role of cosmology in modern physics 9 Weinberg D. H., Mortonson M. J., Eisenstein D. J., Hirata C., Riess A. G., Rozo E., 2013, Physics Reports, 530, 87 Wiltshire D. L., 2007, New Journal of Physics, 9, 377 Woodard R. P., 2015, arXiv/1506.02210 This paper has been typeset from a TEX/LATEX ﬁle prepared by the author. MNRAS 000, 1–8 (2017)

text: The

text: role

text: of

text: cosmology

text: in

text: modern

text: physics

text: Weinberg

label: reference

text: D.

text: H.,

text: Mortonson

text: M.

text: J.,

text: Eisenstein

text: D.

text: J.,

text: Hirata

text: C.,

text: Riess

text: A.

text: G.,

text: Rozo

text: E.,

text: Physics

text: Reports,

text: Wiltshire

text: D.

text: L.,

text: New

text: Journal

text: of

text: Physics,

text: Woodard

text: R.

text: P.,

text: This

text: paper

text: has

text: been

text: typeset

text: from

text: a

text: TEX/LATEX

text: ﬁle

text: prepared

text: by

text: the

text: author.

text: MNRAS


text: Universal Construction of Cheater-Identiﬁable Secret Sharing Against Rushing Cheaters without Honest Majority Masahito Hayashi Takeshi Koshiba Graduate School of Mathematics, Nagoya Univeristy Graduate School of Science and Engineering Centre for Quantum Technologies, National University of Singapore Saitama University Email: masahito@math.nagoya-u.ac.jp Email: koshiba@mail.saitama-u.ac.jp Abstract— For conventional secret sharing, if cheaters can sharing (CDSS) [3] and cheater-identiﬁable secret sharing submit possibly forged shares after observing shares of the (CISS) [4] have been proposed. A protocol is called a (t, (cid:15))- honest users in the reconstruction phase then they cannot only cheater-detectable secret sharing (CDSS) when it detects the disturb the protocol but also only they may reconstruct the existence of cheaters among players involved in reconstruction true secret. To overcome the problem, secret sharing scheme − with properties of cheater-identiﬁcation have been proposed. with probability 1 (cid:15) under the condition that the number of Existing protocols for cheater-identiﬁable secret sharing assumed cheaters is not greater than t. A protocol is called a (t, (cid:15))- non-rushing cheaters or honest majority. In this paper, we cheater-identiﬁable secret sharing (CISS) when it identiﬁes remove both conditions simultaneously, and give its universal − who submitted incorrect shares with probability 1 (cid:15) under construction from any secret sharing scheme. To resolve this the condition that the number of cheaters is not greater than end, we propose the concepts of “individual identiﬁcation” and “agreed identiﬁcation”. t. Index Terms—secret sharing, universal construction, rushing However, cheaters may submit their shares after observing cheater, cheater-identiﬁcation, without honest majority shares of honest players. Such cheaters is called rushing cheaters. The papers [8], [9], [10], [6] proposed CISS protocols I. INTRODUCTION to properly works against such rushing cheaters. To achieve Secret sharing is a basic primitive for secure information this task, their sharing phase is composed of two rounds. transmission [1]. It involves a dealer who has a secret S in the Unfortunately, these protocols cannot identify the cheaters S secret set and a set of players. The dealer divides the secret when the number of cheaters is more than the half of players S into n shares and distributes shares to n players such that if involved in reconstruction. In this situation, only the protocol a set of players is qualiﬁed then all the players in the set can in [6] can detect the existence of cheaters without identifying reconstruct the secret and if the set of players is not qualiﬁed them. Ishai et al [5] proposed another CISS protocol identi- then any player in the set cannot obtain any information about fying them even when the number of cheaters is more than the secret. In case of (k, n)-threshold scheme, any set of k the half of players involved in reconstruction. To achieve this A players can be qualiﬁed. Generally, a family of subsets of task, they propose a locally-identiﬁable secret sharing (LISS), { } 1, . . . , n is the access structure of a secret sharing protocol in which a server identiﬁes the cheaters instead of each player, A when any subsets in can reconstruct the secret S and others but their LISS is not robust against rushing cheaters. In their A can learn nothing about it. It is known that when a family of protocol, the players submit their shares to the server, and the subset is closed with respect to the union, there exists a secret server recovers the secret and identiﬁes the cheaters for each A sharing protocol whose access structure is when the message player. While the server sends each player an information to size and the share size are sufﬁciently large [2]. Further, when identify the cheaters, this information depends on the player. a non-qualiﬁed set of players obtains a part of information, That is, this information is correct only when the player is the protocol is called a ramp scheme secret sharing protocol honest. cheaters. Hence, their identiﬁcations do not agree in [11]. this protocol. For conventional secret sharing protocols, it is assumed that In a real scenario, it is not easy to prepare the server. everyone involved in the protocols is honest or semi-honest. Therefore, it is strongly required to propose a protocol to However, in a real scenario, some participants may maliciously identify the rushing cheaters even when more than half of the behave in the execution of the protocol. In particular, a part of players involved in reconstruction are cheaters. In this paper, to players may submit incorrect shares so as to yield an incorrect resolve this problem, we propose the concepts of “individual secret in the reconstruction phase. To overcome the problem, identiﬁcation” and “agreed identiﬁcation”. A CISS protocol additional properties to conventional secret sharing have been with individual identiﬁcation privately identiﬁes the cheaters considered and new schemes such as cheater-detectable secret so that the identiﬁcation depends on individual players. A

text: Universal

label: title

text: Construction

text: of

text: Cheater-Identiﬁable

text: Secret

text: Sharing

text: Against

text: Rushing

text: Cheaters

text: without

text: Honest

text: Majority

text: Masahito

label: author

text: Hayashi

text: Takeshi

text: Koshiba

text: Graduate

text: School

text: of

text: Mathematics,

text: Nagoya

text: Univeristy

text: Graduate

text: School

text: of

text: Science

text: and

text: Engineering

text: Centre

text: for

text: Quantum

text: Technologies,

text: National

text: University

text: of

text: Singapore

text: Saitama

text: University

text: Email:

text: masahito@math.nagoya-u.ac.jp

text: Email:

text: koshiba@mail.saitama-u.ac.jp

text: Abstract—

text: For

label: abstract

text: conventional

text: secret

text: sharing,

text: if

text: cheaters

text: can

text: sharing

text: (CDSS)

text: and

text: cheater-identiﬁable

text: secret

text: sharing

text: submit

text: possibly

text: forged

text: shares

text: after

text: observing

text: shares

text: of

text: the

text: (CISS)

text: have

text: been

text: proposed.

text: A

text: protocol

text: is

text: called

text: a

text: (t,

text: honest

text: users

text: in

text: the

text: reconstruction

text: phase

text: then

text: they

text: cannot

text: only

text: cheater-detectable

text: secret

text: sharing

text: (CDSS)

text: when

text: it

text: detects

text: the

text: disturb

text: the

text: protocol

text: but

text: also

text: only

text: they

text: may

text: reconstruct

text: the

text: existence

text: of

text: cheaters

text: among

text: players

text: involved

text: in

text: reconstruction

text: true

text: secret.

text: To

text: overcome

text: the

text: problem,

text: secret

text: sharing

text: scheme

text: with

text: properties

text: of

text: cheater-identiﬁcation

text: have

text: been

text: proposed.

text: with

text: probability

text: under

text: the

text: condition

text: that

text: the

text: number

text: of

text: Existing

text: protocols

text: for

text: cheater-identiﬁable

text: secret

text: sharing

text: assumed

text: cheaters

text: is

text: not

text: greater

text: than

text: t.

text: A

text: protocol

text: is

text: called

text: a

text: (t,

text: non-rushing

text: cheaters

text: or

text: honest

text: majority.

text: In

text: this

text: paper,

text: we

text: cheater-identiﬁable

text: secret

text: sharing

text: (CISS)

text: when

text: it

text: identiﬁes

text: remove

text: both

text: conditions

text: simultaneously,

text: and

text: give

text: its

text: universal

text: who

text: submitted

text: incorrect

text: shares

text: with

text: probability

text: under

text: construction

text: from

text: any

text: secret

text: sharing

text: scheme.

text: To

text: resolve

text: this

text: the

text: condition

text: that

text: the

text: number

text: of

text: cheaters

text: is

text: not

text: greater

text: than

text: end,

text: we

text: propose

text: the

text: concepts

text: of

text: “individual

text: identiﬁcation”

text: and

text: “agreed

text: identiﬁcation”.

text: t.

text: Index

text: Terms—secret

text: sharing,

text: universal

text: construction,

text: rushing

text: However,

text: cheaters

text: may

text: submit

text: their

text: shares

text: after

text: observing

text: cheater,

text: cheater-identiﬁcation,

text: without

text: honest

text: majority

text: shares

text: of

text: honest

text: players.

text: Such

text: cheaters

text: is

text: called

text: rushing

text: cheaters.

text: The

text: papers

text: proposed

text: CISS

text: protocols

text: I.

text: INTRODUCTION

text: to

text: properly

text: works

text: against

text: such

text: rushing

text: cheaters.

text: To

text: achieve

text: Secret

text: sharing

text: is

text: a

text: basic

text: primitive

text: for

text: secure

text: information

text: this

text: task,

text: their

text: sharing

text: phase

text: is

text: composed

text: of

text: two

text: rounds.

text: transmission

text: It

text: involves

text: a

text: dealer

text: who

text: has

text: a

text: secret

text: S

text: in

text: the

text: Unfortunately,

text: these

text: protocols

text: cannot

text: identify

text: the

text: cheaters

text: S

text: secret

text: set

text: and

text: a

text: set

text: of

text: players.

text: The

text: dealer

text: divides

text: the

text: secret

text: when

text: the

text: number

text: of

text: cheaters

text: is

text: more

text: than

text: the

text: half

text: of

text: players

text: S

text: into

text: n

text: shares

text: and

text: distributes

text: shares

text: to

text: n

text: players

text: such

text: that

text: if

text: involved

text: in

text: reconstruction.

text: In

text: this

text: situation,

text: only

text: the

text: protocol

text: a

text: set

text: of

text: players

text: is

text: qualiﬁed

text: then

text: all

text: the

text: players

text: in

text: the

text: set

text: can

text: in

text: can

text: detect

text: the

text: existence

text: of

text: cheaters

text: without

text: identifying

text: reconstruct

text: the

text: secret

text: and

text: if

text: the

text: set

text: of

text: players

text: is

text: not

text: qualiﬁed

text: them.

text: Ishai

text: et

text: al

text: proposed

text: another

text: CISS

text: protocol

text: identi-

text: then

text: any

text: player

text: in

text: the

text: set

text: cannot

text: obtain

text: any

text: information

text: about

text: fying

text: them

text: even

text: when

text: the

text: number

text: of

text: cheaters

text: is

text: more

text: than

text: the

text: secret.

text: In

text: case

text: of

text: (k,

text: n)-threshold

text: scheme,

text: any

text: set

text: of

text: k

text: the

text: half

text: of

text: players

text: involved

text: in

text: reconstruction.

text: To

text: achieve

text: this

text: A

text: players

text: can

text: be

text: qualiﬁed.

text: Generally,

text: a

text: family

text: of

text: subsets

text: of

text: task,

text: they

text: propose

text: a

text: locally-identiﬁable

text: secret

text: sharing

text: (LISS),

text: n

text: is

text: the

text: access

text: structure

text: of

text: a

text: secret

text: sharing

text: protocol

text: in

text: which

text: a

text: server

text: identiﬁes

text: the

text: cheaters

text: instead

text: of

text: each

text: player,

text: A

text: when

text: any

text: subsets

text: in

text: can

text: reconstruct

text: the

text: secret

text: S

text: and

text: others

text: but

text: their

text: LISS

text: is

text: not

text: robust

text: against

text: rushing

text: cheaters.

text: In

text: their

text: A

text: can

text: learn

text: nothing

text: about

text: it.

text: It

text: is

text: known

text: that

text: when

text: a

text: family

text: of

text: protocol,

text: the

text: players

text: submit

text: their

text: shares

text: to

text: the

text: server,

text: and

text: the

text: subset

text: is

text: closed

text: with

text: respect

text: to

text: the

text: union,

text: there

text: exists

text: a

text: secret

text: server

text: recovers

text: the

text: secret

text: and

text: identiﬁes

text: the

text: cheaters

text: for

text: each

text: A

text: sharing

text: protocol

text: whose

text: access

text: structure

text: is

text: when

text: the

text: message

text: player.

text: While

text: the

text: server

text: sends

text: each

text: player

text: an

text: information

text: to

text: size

text: and

text: the

text: share

text: size

text: are

text: sufﬁciently

text: large

text: Further,

text: when

text: identify

text: the

text: cheaters,

text: this

text: information

text: depends

text: on

text: the

text: player.

text: a

text: non-qualiﬁed

text: set

text: of

text: players

text: obtains

text: a

text: part

text: of

text: information,

text: That

text: is,

text: this

text: information

text: is

text: correct

text: only

text: when

text: the

text: player

text: is

text: the

text: protocol

text: is

text: called

text: a

text: ramp

text: scheme

text: secret

text: sharing

text: protocol

text: honest.

text: cheaters.

text: Hence,

text: their

text: identiﬁcations

text: do

text: not

text: agree

text: in

text: this

text: protocol.

text: For

text: conventional

text: secret

text: sharing

text: protocols,

text: it

text: is

text: assumed

text: that

text: In

text: a

text: real

text: scenario,

text: it

text: is

text: not

text: easy

text: to

text: prepare

text: the

text: server.

text: everyone

text: involved

text: in

text: the

text: protocols

text: is

text: honest

text: or

text: semi-honest.

text: Therefore,

text: it

text: is

text: strongly

text: required

text: to

text: propose

text: a

text: protocol

text: to

text: However,

text: in

text: a

text: real

text: scenario,

text: some

text: participants

text: may

text: maliciously

text: identify

text: the

text: rushing

text: cheaters

text: even

text: when

text: more

text: than

text: half

text: of

text: the

text: behave

text: in

text: the

text: execution

text: of

text: the

text: protocol.

text: In

text: particular,

text: a

text: part

text: of

text: players

text: involved

text: in

text: reconstruction

text: are

text: cheaters.

text: In

text: this

text: paper,

text: to

text: players

text: may

text: submit

text: incorrect

text: shares

text: so

text: as

text: to

text: yield

text: an

text: incorrect

text: resolve

text: this

text: problem,

text: we

text: propose

text: the

text: concepts

text: of

text: “individual

text: secret

text: in

text: the

text: reconstruction

text: phase.

text: To

text: overcome

text: the

text: problem,

text: identiﬁcation”

text: and

text: “agreed

text: identiﬁcation”.

text: A

text: CISS

text: protocol

text: additional

text: properties

text: to

text: conventional

text: secret

text: sharing

text: have

text: been

text: with

text: individual

text: identiﬁcation

text: privately

text: identiﬁes

text: the

text: cheaters

text: considered

text: and

text: new

text: schemes

text: such

text: as

text: cheater-detectable

text: secret

text: so

text: that

text: the

text: identiﬁcation

text: depends

text: on

text: individual

text: players.

text: A


text: CISS for CDSS Individual Identification P identifies P and P They consider there exists 1 2 3 as cheaters. at least one cheater. CISS for Agreed Identification They identify P as cheater if P and P collude together. 1 2 3 Fig. 1. A Case of majority cheaters. A blue circle expresses a honest player and red circles express cheaters. Let (Sh, Rc) be a secret sharing protocol realizing access Also, even though several players collude together, they A S → structure with Sh : V n, where V is an m-dimensional cannot obtain any information for the shares by other players F F vector space m over a ﬁnite ﬁled . To present our CISS as follows. To see this fact, we assume that the j -th player, q q 1 protocol for individual identiﬁcation based on the protocol the j -th player, . . ., the j -th player collude together. We 2 a (Sh, Rc), we make preparation as follows. For the secret S, we focus on the information X shared by the i-th player. Since i deﬁne the random number X := Sh (S) as the share of the Z is independent and uniform, Y , Y , . . . , Y are i i (cid:54) j,i j1,i j2,i ja,i j-th player, which is sent by the dealer. For i = j, the dealer independent of T X , T X , . . . , T X . Since they obtain − j1 i j1 i ja i independently generates n(n 1) random numbers Z taking no information for T X , T X , . . . , T X , they obtain no F (cid:48) j,i (cid:48) × j1 i j1 i ja i values in (cid:96) . Also, the dealer independently generates (cid:96) m information X . q i Toeplitz matrix T . Then, the dealer calculates the random Thus, if the original protocol with share X works as secret j i number Y := T X + Z . Now, we give our CISS protocol sharing well, our protocol also works as secret sharing well. j,i j i j,i for individual identiﬁcation as Protocol 1. From Protocol 1, In summary, we have the following theorem. (cid:48) (cid:48) − − (cid:48) we ﬁnd that its calculation complexity is O((cid:96) log (cid:96) ). Theorem 1: Protocol 1 is an (n 1, q (cid:96) )-CISS protocol A S realizing access structure with secret space and share Protocol 1 CISS protocol fo(cid:81)r individual identiﬁcation space S = F(2n−1)(cid:96)(cid:48)+2m−1. (cid:81) i q STEP 1: [Dealing] The dealer sends the j-th player the pub- lishable information (X , (cid:54) Z ) and the identiﬁcation- IV. PROTOCOL FOR AGREED IDENTIFICATION j i=j j,i information (T , (cid:54) Y ). Now, we can give our CISS protocol for agreed identiﬁca- j i=j j,i STEP 2: [Sharing] The players wishing to open the informa- tion as Protocol 2. tion send their publishable information. STEP 3: [Reconstruction] The players reconstruct the origi- Protocol 2 CISS protocol fo(cid:81)r agreed identiﬁcation nal information from the collection of X(cid:48). STEP 1: [Dealing](cid:81)The dealer sends the j-th player the pub- i STEP 4: [Identiﬁcation] The j-th player checks whether the lishable information (Xj, i(cid:54)=j Zj,i) and the identiﬁcation- relation information (T , (cid:54) Y ). j i=j j,i STEP 2: [Sharing (Round 1)] The players wishing to open (cid:48) (cid:48) the information send their ﬁrst part information. Yj,i = TjXi + Zj,i (1) STEP 3: [Sharing (Round 2)] The players wishing to open (cid:81) the information send their second part information. holds when the information received from the i-th player is STEP 4: [Reconstruction] The players reconstruct the origi- (Xj(cid:48), i(cid:54)=j Zj(cid:48),i). STnEaPl in5f:or[mIdaetniotinﬁcfarotimon]thWe ceoellmecptliooyn othfeXmi(cid:48).ajority voting of the results of respective individual identiﬁcation. III. SECURITY ANALYSIS (cid:55)→ Since the function (X , Z ) T X +Z is a universal2 Since the majority voting of the results of respective indi- i j,i j i j,i hash function with the randomly chosen Toeplitz matrix T , the vidual veriﬁcations identiﬁes who makes cheating if more than − (cid:48) j relation (1) holds with probability smaller than q l if the j-th half of the players wishing the reconstruction are honest, we player makes a cheat. Therefore, even though all of players have the following theorem. (cid:100) − (cid:101) − (cid:48) except for the i-th player makes cheating even with collusion, Theorem 2: Protocol 2 is a ( (k 1)/2 , q (cid:96) )-CISS proto- A S the i-th player can identify who makes cheating with high col realizing access structure with secret space and share probability as Fig. 1. space S = F(2n−1)(cid:96)(cid:48)+2m−1. i q ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: CISS

font: default

text: for

text: CDSS

text: Individual

text: Identification

text: P

text: identifies

text: P

text: and

text: P

text: They

text: consider

text: there

text: exists

text: as

text: cheaters.

text: at

text: least

text: one

text: cheater.

text: CISS

text: for

text: Agreed

text: Identification

text: They

text: identify

text: P

text: as

text: cheater

text: if

text: P

text: and

text: P

text: collude

text: together.

text: Fig.

text: A

label: caption

text: Case

text: of

text: majority

text: cheaters.

text: A

text: blue

text: circle

text: expresses

text: a

text: honest

text: player

text: and

text: red

text: circles

text: express

text: cheaters.

text: Let

text: (Sh,

text: Rc)

text: be

text: a

text: secret

text: sharing

text: protocol

text: realizing

text: access

text: Also,

text: even

text: though

text: several

text: players

text: collude

text: together,

text: they

text: A

text: S

text: structure

text: with

text: Sh

text: V

text: n,

text: where

text: V

text: is

text: an

text: m-dimensional

text: cannot

text: obtain

text: any

text: information

text: for

text: the

text: shares

text: by

text: other

text: players

text: F

text: F

text: vector

text: space

text: m

text: over

text: a

text: ﬁnite

text: ﬁled

text: To

text: present

text: our

text: CISS

text: as

text: follows.

text: To

text: see

text: this

text: fact,

text: we

text: assume

text: that

text: the

text: j

text: -th

text: player,

text: q

text: q

text: protocol

text: for

text: individual

text: identiﬁcation

text: based

text: on

text: the

text: protocol

text: the

text: j

text: -th

text: player,

text: the

text: j

text: -th

text: player

text: collude

text: together.

text: We

text: a

text: (Sh,

text: Rc),

text: we

text: make

text: preparation

text: as

text: follows.

text: For

text: the

text: secret

text: S,

text: we

text: focus

text: on

text: the

text: information

text: X

text: shared

text: by

text: the

text: i-th

text: player.

text: Since

text: i

text: deﬁne

text: the

text: random

text: number

text: X

text: Sh

text: (S)

text: as

text: the

text: share

text: of

text: the

text: Z

text: is

text: independent

text: and

text: uniform,

text: Y

text: Y

text: Y

text: are

text: i

text: i

text: j,i

text: ja,i

text: j-th

text: player,

text: which

text: is

text: sent

text: by

text: the

text: dealer.

text: For

text: i

text: j,

text: the

text: dealer

text: independent

text: of

text: T

text: X

text: T

text: X

text: T

text: X

text: Since

text: they

text: obtain

text: i

text: i

text: ja

text: i

text: independently

text: generates

text: n(n

text: random

text: numbers

text: Z

text: taking

text: no

text: information

text: for

text: T

text: X

text: T

text: X

text: T

text: X

text: they

text: obtain

text: no

text: F

text: j,i

text: i

text: i

text: ja

text: i

text: values

text: in

text: Also,

text: the

text: dealer

text: independently

text: generates

text: m

text: information

text: X

text: q

text: i

text: Toeplitz

text: matrix

text: T

text: Then,

text: the

text: dealer

text: calculates

text: the

text: random

text: Thus,

text: if

text: the

text: original

text: protocol

text: with

text: share

text: X

text: works

text: as

text: secret

text: j

text: i

text: number

text: Y

text: T

text: X

text: Z

text: Now,

text: we

text: give

text: our

text: CISS

text: protocol

text: sharing

text: well,

text: our

text: protocol

text: also

text: works

text: as

text: secret

text: sharing

text: well.

text: j,i

text: j

text: i

text: j,i

text: for

text: individual

text: identiﬁcation

text: as

text: Protocol

text: From

text: Protocol

text: In

text: summary,

text: we

text: have

text: the

text: following

text: theorem.

text: we

text: ﬁnd

text: that

text: its

text: calculation

text: complexity

text: is

text: log

text: Theorem

text: Protocol

text: is

text: an

text: (n

text: q

text: )-CISS

text: protocol

text: A

text: S

text: realizing

text: access

text: structure

text: with

text: secret

text: space

text: and

text: share

text: Protocol

text: CISS

text: protocol

text: individual

text: identiﬁcation

text: space

text: S

text: i

text: q

text: STEP

text: [Dealing]

text: The

text: dealer

text: sends

text: the

text: j-th

text: player

text: the

text: pub-

text: lishable

text: information

text: (X

text: Z

text: and

text: the

text: identiﬁcation-

text: IV.

text: PROTOCOL

text: FOR

text: AGREED

text: IDENTIFICATION

text: j

text: i=j

text: j,i

text: information

text: (T

text: Y

text: Now,

text: we

text: can

text: give

text: our

text: CISS

text: protocol

text: for

text: agreed

text: identiﬁca-

text: j

text: i=j

text: j,i

text: STEP

text: [Sharing]

text: The

text: players

text: wishing

text: to

text: open

text: the

text: informa-

text: tion

text: as

text: Protocol

text: tion

text: send

text: their

text: publishable

text: information.

text: STEP

text: [Reconstruction]

text: The

text: players

text: reconstruct

text: the

text: origi-

text: Protocol

text: CISS

text: protocol

text: agreed

text: identiﬁcation

text: nal

text: information

text: from

text: the

text: collection

text: of

text: STEP

text: dealer

text: sends

text: the

text: j-th

text: player

text: the

text: pub-

text: i

text: STEP

text: [Identiﬁcation]

text: The

text: j-th

text: player

text: checks

text: whether

text: the

text: lishable

text: information

text: (Xj,

text: Zj,i)

text: and

text: the

text: identiﬁcation-

text: relation

text: information

text: (T

text: Y

text: j

text: i=j

text: j,i

text: STEP

text: [Sharing

text: (Round

text: The

text: players

text: wishing

text: to

text: open

text: the

text: information

text: send

text: their

text: ﬁrst

text: part

text: information.

text: Yj,i

text: TjXi

text: Zj,i

text: STEP

text: [Sharing

text: (Round

text: The

text: players

text: wishing

text: to

text: open

text: the

text: information

text: send

text: their

text: second

text: part

text: information.

text: holds

text: when

text: the

text: information

text: received

text: from

text: the

text: i-th

text: player

text: is

text: STEP

text: [Reconstruction]

text: The

text: players

text: reconstruct

text: the

text: origi-

text: STnEaPl

text: ceoellmecptliooyn

text: voting

text: of

text: the

text: results

text: of

text: respective

text: individual

text: identiﬁcation.

text: III.

text: SECURITY

text: ANALYSIS

text: Since

text: the

text: function

text: (X

text: Z

text: T

text: X

text: +Z

text: is

text: a

text: Since

text: the

text: majority

text: voting

text: of

text: the

text: results

text: of

text: respective

text: indi-

text: i

text: j,i

text: j

text: i

text: j,i

text: hash

text: function

text: with

text: the

text: randomly

text: chosen

text: Toeplitz

text: matrix

text: T

text: the

text: vidual

text: veriﬁcations

text: identiﬁes

text: who

text: makes

text: cheating

text: if

text: more

text: than

text: j

text: relation

text: holds

text: with

text: probability

text: smaller

text: than

text: q

text: l

text: if

text: the

text: j-th

text: half

text: of

text: the

text: players

text: wishing

text: the

text: reconstruction

text: are

text: honest,

text: we

text: player

text: makes

text: a

text: cheat.

text: Therefore,

text: even

text: though

text: all

text: of

text: players

text: have

text: the

text: following

text: theorem.

text: except

text: for

text: the

text: i-th

text: player

text: makes

text: cheating

text: even

text: with

text: collusion,

text: Theorem

text: Protocol

text: is

text: a

text: (k

text: q

text: )-CISS

text: proto-

text: A

text: S

text: the

text: i-th

text: player

text: can

text: identify

text: who

text: makes

text: cheating

text: with

text: high

text: col

text: realizing

text: access

text: structure

text: with

text: secret

text: space

text: and

text: share

text: probability

text: as

text: Fig.

text: space

text: S

text: i

text: q

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Discrete-Time Quantum Walks and Graph Structures ∗ Chris Godsil, Hanmeng Zhan May 29, 2020 Abstract We formulate three current models of discrete-time quantum walks in a combinatorial way. These walks are shown to be closely related to rotation systems and 1-factorizations of graphs. For two of the mod- els, we compute the traces and total entropies of the average mixing matrices for some cubic graphs. The trace captures how likely a quan- tum walk is to revisit the state it started with, and the total entropy measures how close the limiting distribution is to uniform. Our numer- ical results indicate three relations between quantum walks and graph structures: for the ﬁrst model, rotation systems with higher genera give lower traces and higher entropies, and for the second model, the symmetric 1-factorizations always give the highest trace. 1 Introduction There are at least three diﬀerent models of discrete-time quantum walks in current research. Some of them are equivalent to quantum search algorithms [18], and some are shown to exhibit desired properties such as periodicity and perfect state transfer [5, 6]. Most of the existing studies focus on a speciﬁc model or a restricted family of graphs. In this paper, we analyze the dependence of these models on diﬀerent combinatorial structures. To be more speciﬁc, we reformulate all three models in graph-theoretic language, ∗ Research supported by NSERC 1 ##LTLine##

text: Discrete-Time

text: Quantum

text: Walks

text: and

text: Graph

text: Structures

text: Chris

text: Godsil,

text: Hanmeng

text: Zhan

text: May

text: Abstract

text: We

text: formulate

text: three

text: current

text: models

text: of

text: discrete-time

text: quantum

text: walks

text: in

text: a

text: combinatorial

text: way.

text: These

text: walks

text: are

text: shown

text: to

text: be

text: closely

text: related

text: to

text: rotation

text: systems

text: and

text: of

text: graphs.

text: For

text: two

text: of

text: the

text: mod-

text: els,

text: we

text: compute

text: the

text: traces

text: and

text: total

text: entropies

text: of

text: the

text: average

text: mixing

text: matrices

text: for

text: some

text: cubic

text: graphs.

text: The

text: trace

text: captures

text: how

text: likely

text: a

text: quan-

text: tum

text: walk

text: is

text: to

text: revisit

text: the

text: state

text: it

text: started

text: with,

text: and

text: the

text: total

text: entropy

text: measures

text: how

text: close

text: the

text: limiting

text: distribution

text: is

text: to

text: uniform.

text: Our

text: numer-

text: ical

text: results

text: indicate

text: three

text: relations

text: between

text: quantum

text: walks

text: and

text: graph

text: structures:

text: for

text: the

text: ﬁrst

text: model,

text: rotation

text: systems

text: with

text: higher

text: genera

text: give

text: lower

text: traces

text: and

text: higher

text: entropies,

text: and

text: for

text: the

text: second

text: model,

text: the

text: symmetric

text: always

text: give

text: the

text: highest

text: trace.

text: Introduction

text: There

text: are

text: at

text: least

text: three

text: diﬀerent

text: models

text: of

text: discrete-time

text: quantum

text: walks

text: in

text: current

text: research.

text: Some

text: of

text: them

text: are

text: equivalent

text: to

text: quantum

text: search

text: algorithms

text: and

text: some

text: are

text: shown

text: to

text: exhibit

text: desired

text: properties

text: such

text: as

text: periodicity

text: and

text: perfect

text: state

text: transfer

text: Most

text: of

text: the

text: existing

text: studies

text: focus

text: on

text: a

text: speciﬁc

text: model

text: or

text: a

text: restricted

text: family

text: of

text: graphs.

text: In

text: this

text: paper,

text: we

text: analyze

text: the

text: dependence

text: of

text: these

text: models

text: on

text: diﬀerent

text: combinatorial

text: structures.

text: To

text: be

text: more

text: speciﬁc,

text: we

text: reformulate

text: all

text: three

text: models

text: in

text: graph-theoretic

text: language,

text: Research

text: supported

text: by

text: NSERC

text: ##LTLine##


text: and experiment on diﬀerent classes of graphs to see how the properties of a graph aﬀect the properties of a walk. Unlike the continuous-time quantum walks, the discrete ones require more than just a graph to build. The extra inputs might include a selection of coins, a set of linear orders of the neighbors of vertices, a 1-factorization of the bipartite double cover, or a Markov chain on the graph. According to how the walks are constructed from these building blocks, we will name them the arc-reversal model, the shunt-decomposition model and the two-reﬂection model. In the arc-reversal model, the walk alternatively ﬂips a unitary coin and reverses the arcs of the graph. We show that if the coins are circulants with simple eigenvalues, then for each rotation system of the graph, we can construct a unique arc-reversal walk. In the shunt-decomposition model, the walk alternatively ﬂips a unitary coin and hops between outgoing arcs in the same class. Each such class, or “shunt”, determines a perfect matching of the bipartite double cover of the graph. Thus every shunt-decomposition walk inherits the properties of some 1-factorization. The two-reﬂection model is coinless, and the walk alternatively applies two involutions with respect to two weighted partitions of the arcs. These partitions usually arise from a classical Markov chain. After introducing diﬀerent models, we review some asymptotic properties of a general quantum walk. It is well-known that the probability distribution of a quantum walk does not converge. However, the average probabilities over time converge to a limit, which we call the average mixing matrix. In Section 7, we develop some theory of the average mixing matrix. Two parameters of the average mixing matrix are of our interest—the trace, which captures how likely a walk is to stay at home in the limit, and the total entropy, which captures how far the limiting distributions are from being uniform. We then present some computational results indicating sensitivity of walk properties to details of the model. For each cubic graph on up to 12 vertices, we enumerate all its rotation systems and shunt-decompositions, compute the associated average mixing matrices for the arc-reversal model and the shunt- decomposition model, and compared their traces and total entropies. Our numerical results on the traces indicate two relations. For the ﬁrst model, as the genus of the embedding increases, the trace of the average mixing matrix decreases, with only few exceptions for some cubic graphs on 12 ver- tices. For the second model, the trace distinguishes non-isomorphic shunt- decompositions, and the symmetric shunts, if any, always give the highest 2

text: and

text: experiment

text: on

text: diﬀerent

text: classes

text: of

text: graphs

text: to

text: see

text: how

text: the

text: properties

text: of

text: a

text: graph

text: aﬀect

text: the

text: properties

text: of

text: a

text: walk.

text: Unlike

text: the

text: continuous-time

text: quantum

text: walks,

text: the

text: discrete

text: ones

text: require

text: more

text: than

text: just

text: a

text: graph

text: to

text: build.

text: The

text: extra

text: inputs

text: might

text: include

text: a

text: selection

text: of

text: coins,

text: a

text: set

text: of

text: linear

text: orders

text: of

text: the

text: neighbors

text: of

text: vertices,

text: a

text: of

text: the

text: bipartite

text: double

text: cover,

text: or

text: a

text: Markov

text: chain

text: on

text: the

text: graph.

text: According

text: to

text: how

text: the

text: walks

text: are

text: constructed

text: from

text: these

text: building

text: blocks,

text: we

text: will

text: name

text: them

text: the

text: arc-reversal

text: model,

text: the

text: shunt-decomposition

text: model

text: and

text: the

text: two-reﬂection

text: model.

text: In

text: the

text: arc-reversal

text: model,

text: the

text: walk

text: alternatively

text: ﬂips

text: a

text: unitary

text: coin

text: and

text: reverses

text: the

text: arcs

text: of

text: the

text: graph.

text: We

text: show

text: that

text: if

text: the

text: coins

text: are

text: circulants

text: with

text: simple

text: eigenvalues,

text: then

text: for

text: each

text: rotation

text: system

text: of

text: the

text: graph,

text: we

text: can

text: construct

text: a

text: unique

text: arc-reversal

text: walk.

text: In

text: the

text: shunt-decomposition

text: model,

text: the

text: walk

text: alternatively

text: ﬂips

text: a

text: unitary

text: coin

text: and

text: hops

text: between

text: outgoing

text: arcs

text: in

text: the

text: same

text: class.

text: Each

text: such

text: class,

text: or

text: “shunt”,

text: determines

text: a

text: perfect

text: matching

text: of

text: the

text: bipartite

text: double

text: cover

text: of

text: the

text: graph.

text: Thus

text: every

text: shunt-decomposition

text: walk

text: inherits

text: the

text: properties

text: of

text: some

text: The

text: two-reﬂection

text: model

text: is

text: coinless,

text: and

text: the

text: walk

text: alternatively

text: applies

text: two

text: involutions

text: with

text: respect

text: to

text: two

text: weighted

text: partitions

text: of

text: the

text: arcs.

text: These

text: partitions

text: usually

text: arise

text: from

text: a

text: classical

text: Markov

text: chain.

text: After

text: introducing

text: diﬀerent

text: models,

text: we

text: review

text: some

text: asymptotic

text: properties

text: of

text: a

text: general

text: quantum

text: walk.

text: It

text: is

text: well-known

text: that

text: the

text: probability

text: distribution

text: of

text: a

text: quantum

text: walk

text: does

text: not

text: converge.

text: However,

text: the

text: average

text: probabilities

text: over

text: time

text: converge

text: to

text: a

text: limit,

text: which

text: we

text: call

text: the

text: average

text: mixing

text: matrix.

text: In

text: Section

text: we

text: develop

text: some

text: theory

text: of

text: the

text: average

text: mixing

text: matrix.

text: Two

text: parameters

text: of

text: the

text: average

text: mixing

text: matrix

text: are

text: of

text: our

text: interest—the

text: trace,

text: which

text: captures

text: how

text: likely

text: a

text: walk

text: is

text: to

text: stay

text: at

text: home

text: in

text: the

text: limit,

text: and

text: the

text: total

text: entropy,

text: which

text: captures

text: how

text: far

text: the

text: limiting

text: distributions

text: are

text: from

text: being

text: uniform.

text: We

text: then

text: present

text: some

text: computational

text: results

text: indicating

text: sensitivity

text: of

text: walk

text: properties

text: to

text: details

text: of

text: the

text: model.

text: For

text: each

text: cubic

text: graph

text: on

text: up

text: to

text: vertices,

text: we

text: enumerate

text: all

text: its

text: rotation

text: systems

text: and

text: shunt-decompositions,

text: compute

text: the

text: associated

text: average

text: mixing

text: matrices

text: for

text: the

text: arc-reversal

text: model

text: and

text: the

text: shunt-

text: decomposition

text: model,

text: and

text: compared

text: their

text: traces

text: and

text: total

text: entropies.

text: Our

text: numerical

text: results

text: on

text: the

text: traces

text: indicate

text: two

text: relations.

text: For

text: the

text: ﬁrst

text: model,

text: as

text: the

text: genus

text: of

text: the

text: embedding

text: increases,

text: the

text: trace

text: of

text: the

text: average

text: mixing

text: matrix

text: decreases,

text: with

text: only

text: few

text: exceptions

text: for

text: some

text: cubic

text: graphs

text: on

text: ver-

text: tices.

text: For

text: the

text: second

text: model,

text: the

text: trace

text: distinguishes

text: non-isomorphic

text: shunt-

text: decompositions,

text: and

text: the

text: symmetric

text: shunts,

text: if

text: any,

text: always

text: give

text: the

text: highest


text: 5 Rotation Systems { ∈ In either of the coined models, we need a set of linear orders f : u } u V (X) of the neighbors to implement the coin operator. If we convert these linear orders into cyclic permutations, we obtain a rotation system, which determines an orientable embedding of X. We introduce some basic concepts about rotation systems. For more background, see Gross and Tucker [11]. { ∈ } Formally, a rotation system is a set π : u V (X) where each π is u u a cyclic permutation on the neighbors of the vertex u. For any arc (u , u ), 1 2 consider the walk · · · · · · (u , u ), (u , u ), (u , u ), , (u − , u ), 1 2 2 3 3 4 k 1 k where u = π (u − ). j+1 uj j 1 Since the graph is ﬁnite, eventually the walk will meet an arc that is already taken. Moreover, the ﬁrst arc that is used twice must be (u , u ), as the − 1 2 preimage π 1(v) is uniquely determined for each u. We will call the closed u walk · · · (u , u ), (u , u ), (u , u ), , (u , u ) 1 2 2 3 3 4 k 1 a facial walk. The facial walks partition the arcs of X. Clearly, each edge occurs either once in two facial walks, or twice in the same facial walk. On the other hand, a facial walk can use a vertex many times without using an arc twice. The following three embeddings illustrate the diﬀerence. In Figure 8, every face is bounded by a cycle. In Figure 9, the outer face uses the pendent edge twice. In Figure 10, the outer face uses the central vertex four times but no edge twice. Figure 8 Figure 9 Figure 10 Given a facial walk of length k, we associate it with a polygon with k sides, labeled by the arcs in the same order as they appear in the facial walk. 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Rotation

text: Systems

text: In

text: either

text: of

text: the

text: coined

text: models,

text: we

text: need

text: a

text: set

text: of

text: linear

text: orders

text: f

text: u

text: u

text: V

text: (X)

text: of

text: the

text: neighbors

text: to

text: implement

text: the

text: coin

text: operator.

text: If

text: we

text: convert

text: these

text: linear

text: orders

text: into

text: cyclic

text: permutations,

text: we

text: obtain

text: a

text: rotation

text: system,

text: which

text: determines

text: an

text: orientable

text: embedding

text: of

text: X.

text: We

text: introduce

text: some

text: basic

text: concepts

text: about

text: rotation

text: systems.

text: For

text: more

text: background,

text: see

text: Gross

text: and

text: Tucker

text: Formally,

text: a

text: rotation

text: system

text: is

text: a

text: set

text: π

text: u

text: V

text: (X)

text: where

text: each

text: π

text: is

text: u

text: u

text: a

text: cyclic

text: permutation

text: on

text: the

text: neighbors

text: of

text: the

text: vertex

text: u.

text: For

text: any

text: arc

text: (u

text: u

text: consider

text: the

text: walk

text: (u

text: u

text: (u

text: u

text: (u

text: u

text: (u

text: u

text: k

text: k

text: where

text: u

text: π

text: (u

text: uj

text: j

text: Since

text: the

text: graph

text: is

text: ﬁnite,

text: eventually

text: the

text: walk

text: will

text: meet

text: an

text: arc

text: that

text: is

text: already

text: taken.

text: Moreover,

text: the

text: ﬁrst

text: arc

text: that

text: is

text: used

text: twice

text: must

text: be

text: (u

text: u

text: as

text: the

text: preimage

text: π

text: is

text: uniquely

text: determined

text: for

text: each

text: u.

text: We

text: will

text: call

text: the

text: closed

text: u

text: walk

text: (u

text: u

text: (u

text: u

text: (u

text: u

text: (u

text: u

text: k

text: a

text: facial

text: walk.

text: The

text: facial

text: walks

text: partition

text: the

text: arcs

text: of

text: X.

text: Clearly,

text: each

text: edge

text: occurs

text: either

text: once

text: in

text: two

text: facial

text: walks,

text: or

text: twice

text: in

text: the

text: same

text: facial

text: walk.

text: On

text: the

text: other

text: hand,

text: a

text: facial

text: walk

text: can

text: use

text: a

text: vertex

text: many

text: times

text: without

text: using

text: an

text: arc

text: twice.

text: The

text: following

text: three

text: embeddings

text: illustrate

text: the

text: diﬀerence.

text: In

text: Figure

text: every

text: face

text: is

text: bounded

text: by

text: a

text: cycle.

text: In

text: Figure

text: the

text: outer

text: face

text: uses

text: the

text: pendent

text: edge

text: twice.

text: In

text: Figure

text: the

text: outer

text: face

text: uses

text: the

text: central

text: vertex

text: four

text: times

text: but

text: no

text: edge

text: twice.

text: Figure

text: Figure

text: Figure

text: Given

text: a

text: facial

text: walk

text: of

text: length

text: k,

text: we

text: associate

text: it

text: with

text: a

text: polygon

text: with

text: k

text: sides,

text: labeled

text: by

text: the

text: arcs

text: in

text: the

text: same

text: order

text: as

text: they

text: appear

text: in

text: the

text: facial

text: walk.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##