text: 7 are shown in Fig. 8a. We see that quantum delocaliza- 8 tion indeed takes place at critical t . As illustrated in Fig. 1 8b, the phase-space trajectories at t = tc and E = Ec 1 1 are not perfect squares. This is the reﬂection of the ab- 4 sence of x-p duality. This duality is respected only near the crossing points, like (x, p) = (0, π/2), but it is these points that are responsible for transport. 0 ± Energies Ec correspond to delocalization within indi- vidual branches. Most nontrivial scenario emerges when both branches are involved in transport. We will demon- - 4 strate that, for a certain relation between t , V , and ∆ 1 - 4 0 4 8 there is an anomaly in the behavior of the localization length with energy inside the insulator regime. This re- lation is established from the condition that the energy distance between the branches is equal to 2V and has the FIG. 6: (Color online) Schematic illustration of the spin-orbit form (cid:0) (cid:1) facilitated delocalization. The phase-space trajectories for a given energy E < ∆ include the contours corresponding to two diﬀerent branches, see Eq. (12). They are shown with 4 t˜c 2 ∆2 black and red lines. Coupling between two black contours is 1 + = 1. (21) V 2 V 2 determined either by tunneling (green arrow) or by two virtual transitions from black to red and back (blue arrows). These transitions are accompanied by change of the momentum by Firstly, at this t1, the phase-space trajectories corre- π, so that the corresponding spinors are not orthogonal, see sponding to both branches coexist. They are shown by Eq. (16). Moreover, the amplitudes of these transitions are blue and red lines in Fig. 9. The value t = t˜c is distin- 1 1 proportional to t1 but do not contain tunneling exponent. guished by the fact that the restructuring of the phase- Thus, already at very small t1, these transitions dominate the space trajectories corresponding to E = 0 takes place at coupling. As a result, L(E) drops dramatically, as shown in this t . Note that the restructuring at t = t˜c does not Fig. 5. The contours in the ﬁgure are shown for parameters: 1 1 1 involve percolation, as it is illustrated in Fig. 9. ∆ = V , t = 0.5V (as in Fig. 5), and for E = 0.5V . The restructuring of the phase-space trajectories af- fects the transport for the following reason. As seen in 0.5 Fig. 9b, for t > t˜c, the transport is exclusively due 1 1 E) to tunneling between blue and red trajectories. On the L(0.4 contrary, for t < t˜c the transport requires both: inter- 1 1 branch tunneling between blue and red trajectories as 0.3 well as intra-branch tunneling between blue trajectories and between red trajectories. This is because for t < t˜c 0.2 1 1 additional classically forbidden regions appear, see Fig. 0.1 9c. Restructuring of the trajectories at t = t˜c leads to 1 1 0 the anomaly in the energy dependence of the Lyapunov -3 -2 -1 0 1 2 3 E exponent. Namely, L(E) exhibits a V -shape behavior, as shown in Fig. 10. The origin of this behavior is the FIG. 7: (Color online) Scaling of the plateau in L(E) with following. The minimal value, L(0), is determined by spin-orbit strength, t1. The plateau height| calculate|d for the inter-branch tunneling. For positive E, transport re- three t -values drops, upon increasing t , as ln (t /t) . Pa- 1 1 1 quires additional tunneling between the red trajectories. rameters ∆, t and the period, β, are the same as in Fig. 5. For negative E, transport requires additional tunneling between the blue trajectories. This additional tunneling takes place at p = π/2. The “price” of additional tunnel- ing is proportional to E, as we have established above, Upon solving the above system, we ﬁnd the critical see Eq. (7). Thus, the behavior of L(E) at small E has value of t and percolation energy, Ec, 1 (cid:34) (cid:35) the form | | 1/2 | | − ∝ | | tc ∆ ± Ec ∆ (L(E) L(0)) E . (22) 1 = + 1 , = + 1. (20) V V V V Note that the tunneling between red and blue trajec- The Lyapunov exponent, L(E), calculated for critical tories is “forbidden”, in the sense, that the initial and value, t = tc, and for one value of t below the transition ﬁnal states are both at p = 0. Thus, the corresponding 1 1 1 ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: are

text: shown

text: in

text: Fig.

text: We

text: see

text: that

text: quantum

text: delocaliza-

text: tion

text: indeed

text: takes

text: place

text: at

text: critical

text: t

text: As

text: illustrated

text: in

text: Fig.

text: the

text: phase-space

text: trajectories

text: at

text: t

text: tc

text: and

text: E

text: Ec

text: are

text: not

text: perfect

text: squares.

text: This

text: is

text: the

text: reﬂection

text: of

text: the

text: ab-

text: sence

text: of

text: x-p

text: duality.

text: This

text: duality

text: is

text: respected

text: only

text: near

text: the

text: crossing

text: points,

text: like

text: (x,

text: p)

text: but

text: it

text: is

text: these

text: points

text: that

text: are

text: responsible

text: for

text: transport.

text: Energies

text: Ec

text: correspond

text: to

text: delocalization

text: within

text: indi-

text: vidual

text: branches.

text: Most

text: nontrivial

text: scenario

text: emerges

text: when

text: both

text: branches

text: are

text: involved

text: in

text: transport.

text: We

text: will

text: demon-

text: strate

text: that,

text: for

text: a

text: certain

text: relation

text: between

text: t

text: V

text: and

text: there

text: is

text: an

text: anomaly

text: in

text: the

text: behavior

text: of

text: the

text: localization

text: length

text: with

text: energy

text: inside

text: the

text: insulator

text: regime.

text: This

text: re-

text: lation

text: is

text: established

text: from

text: the

text: condition

text: that

text: the

text: energy

text: distance

text: between

text: the

text: branches

text: is

text: equal

text: to

text: and

text: has

text: the

text: FIG.

text: (Color

text: online)

text: Schematic

text: illustration

text: of

text: the

text: spin-orbit

text: form

text: facilitated

text: delocalization.

text: The

text: phase-space

text: trajectories

text: for

text: a

text: given

text: energy

text: E

text: include

text: the

text: contours

text: corresponding

text: to

text: two

text: diﬀerent

text: branches,

text: see

text: Eq.

text: They

text: are

text: shown

text: with

text: t˜c

text: ∆2

text: black

text: and

text: red

text: lines.

text: Coupling

text: between

text: two

text: black

text: contours

text: is

text: V

text: V

text: determined

text: either

text: by

text: tunneling

text: (green

text: arrow)

text: or

text: by

text: two

text: virtual

text: transitions

text: from

text: black

text: to

text: red

text: and

text: back

text: (blue

text: arrows).

text: These

text: transitions

text: are

text: accompanied

text: by

text: change

text: of

text: the

text: momentum

text: by

text: Firstly,

text: at

text: this

text: the

text: phase-space

text: trajectories

text: corre-

text: π,

text: so

text: that

text: the

text: corresponding

text: spinors

text: are

text: not

text: orthogonal,

text: see

text: sponding

text: to

text: both

text: branches

text: coexist.

text: They

text: are

text: shown

text: by

text: Eq.

text: Moreover,

text: the

text: amplitudes

text: of

text: these

text: transitions

text: are

text: blue

text: and

text: red

text: lines

text: in

text: Fig.

text: The

text: value

text: t

text: t˜c

text: is

text: distin-

text: proportional

text: to

text: but

text: do

text: not

text: contain

text: tunneling

text: exponent.

text: guished

text: by

text: the

text: fact

text: that

text: the

text: restructuring

text: of

text: the

text: phase-

text: Thus,

text: already

text: at

text: very

text: small

text: these

text: transitions

text: dominate

text: the

text: space

text: trajectories

text: corresponding

text: to

text: E

text: takes

text: place

text: at

text: coupling.

text: As

text: a

text: result,

text: L(E)

text: drops

text: dramatically,

text: as

text: shown

text: in

text: this

text: t

text: Note

text: that

text: the

text: restructuring

text: at

text: t

text: t˜c

text: does

text: not

text: Fig.

text: The

text: contours

text: in

text: the

text: ﬁgure

text: are

text: shown

text: for

text: parameters:

text: involve

text: percolation,

text: as

text: it

text: is

text: illustrated

text: in

text: Fig.

text: V

text: t

text: (as

text: in

text: Fig.

text: and

text: for

text: E

text: The

text: restructuring

text: of

text: the

text: phase-space

text: trajectories

text: af-

text: fects

text: the

text: transport

text: for

text: the

text: following

text: reason.

text: As

text: seen

text: in

text: Fig.

text: for

text: t

text: t˜c,

text: the

text: transport

text: is

text: exclusively

text: due

text: E)

text: to

text: tunneling

text: between

text: blue

text: and

text: red

text: trajectories.

text: On

text: the

text: contrary,

text: for

text: t

text: t˜c

text: the

text: transport

text: requires

text: both:

text: inter-

text: branch

text: tunneling

text: between

text: blue

text: and

text: red

text: trajectories

text: as

text: well

text: as

text: intra-branch

text: tunneling

text: between

text: blue

text: trajectories

text: and

text: between

text: red

text: trajectories.

text: This

text: is

text: because

text: for

text: t

text: t˜c

text: additional

text: classically

text: forbidden

text: regions

text: appear,

text: see

text: Fig.

text: Restructuring

text: of

text: the

text: trajectories

text: at

text: t

text: t˜c

text: leads

text: to

text: the

text: anomaly

text: in

text: the

text: energy

text: dependence

text: of

text: the

text: Lyapunov

text: E

text: exponent.

text: Namely,

text: L(E)

text: exhibits

text: a

text: V

text: -shape

text: behavior,

text: as

text: shown

text: in

text: Fig.

text: The

text: origin

text: of

text: this

text: behavior

text: is

text: the

text: FIG.

text: (Color

text: online)

text: Scaling

text: of

text: the

text: plateau

text: in

text: L(E)

text: with

text: following.

text: The

text: minimal

text: value,

text: is

text: determined

text: by

text: spin-orbit

text: strength,

text: The

text: plateau

text: height|

text: calculate|d

text: for

text: the

text: inter-branch

text: tunneling.

text: For

text: positive

text: E,

text: transport

text: re-

text: three

text: t

text: -values

text: drops,

text: upon

text: increasing

text: t

text: as

text: ln

text: (t

text: /t)

text: Pa-

text: quires

text: additional

text: tunneling

text: between

text: the

text: red

text: trajectories.

text: rameters

text: t

text: and

text: the

text: period,

text: β,

text: are

text: the

text: same

text: as

text: in

text: Fig.

text: For

text: negative

text: E,

text: transport

text: requires

text: additional

text: tunneling

text: between

text: the

text: blue

text: trajectories.

text: This

text: additional

text: tunneling

text: takes

text: place

text: at

text: p

text: The

text: “price”

text: of

text: additional

text: tunnel-

text: ing

text: is

text: proportional

text: to

text: E,

text: as

text: we

text: have

text: established

text: above,

text: Upon

text: solving

text: the

text: above

text: system,

text: we

text: ﬁnd

text: the

text: critical

text: see

text: Eq.

text: Thus,

text: the

text: behavior

text: of

text: L(E)

text: at

text: small

text: E

text: has

text: value

text: of

text: t

text: and

text: percolation

text: energy,

text: Ec,

text: the

text: form

text: tc

text: Ec

text: (L(E)

text: E

text: V

text: V

text: V

text: V

text: Note

text: that

text: the

text: tunneling

text: between

text: red

text: and

text: blue

text: trajec-

text: The

text: Lyapunov

text: exponent,

text: L(E),

text: calculated

text: for

text: critical

text: tories

text: is

text: “forbidden”,

text: in

text: the

text: sense,

text: that

text: the

text: initial

text: and

text: value,

text: t

text: tc,

text: and

text: for

text: one

text: value

text: of

text: t

text: below

text: the

text: transition

text: ﬁnal

text: states

text: are

text: both

text: at

text: p

text: Thus,

text: the

text: corresponding

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8 5.2.3 Man-in-Middle Attack Resistance An adversary is unable to act as a middle man in between a reader and a tag because it is infeasible for the adversary to intercepts any transmitted message without knowing the secret key, unique identiﬁcation number, and knowledge about the cyclic group. The probability of guessing or calcu- lating these values from the transmitted message is negligible because a fresh nonce is used in each transmitted message. 6 Performance Analysis In this section, we present eﬃciency of our proposed scheme in terms of tag computation, server computation, and storage, as described in Table 3. The proposed scheme’s search complexity is O(γ) which is same as in Avione et al. [1] but better than Rahman et al. [16]. During the authentication phase, the scheme performs only bit-wise XOR operation whereas schemes of Avoine et al. and Rahman et al. perform symmetric key encryption and decryption. Also, the proposed scheme does not use any pseudo number generator function for generating nonce on the tag-side. It uses nonce generated by the reader. We assume that all the parameters used in the proposed scheme are L-bits long. On the tag side, our scheme keeps ﬁve items. Thus the storage cost is 5L bits. The proposed scheme also provides mutual authentication among a reader and tags. When we compare with [1] and [16] in terms of computation, the proposed scheme performs very less computation which is optimal for the real world tiny powered tags. Protocol Entity Avoine Rahman Proposed protocol [1] [16] × Symmetric encryption/ T 2 2 × decryption R 2 2 | | Search complexity R O(γ) O(γ + π ) O(γ) × No. of PRNG T 1 1 Required memory T 3L (m + 2)L 5L × × (cid:88) Mutual authentication γ- Total number of groups in the system. | | π - Total number of secret keys of a tag associated with the identiﬁer IDx. m - Number of identiﬁer is assigned to each tag. Table 3 Computation cost performance comparison 7 Measurement of Privacy In this section, we analyze the privacy level of our proposed scheme in terms of anonymity set and data leakage in bits. For the anonymity sets, we use privacy metric introdued by [3]. Also, we use another metric says information leakage for data leakage proposed by shannon [17] and used in [14] [16] to measure the information (in bits) disclosed by the proposed scheme when some tags are compromised. Both the metric use disjoint partition sets of tags for observation. When some tags are compromised, the set of all tags are partitioned in such a way so that the adversary can not distinguish the tags that belong to the same partition but she can distinguish the tags belong to diﬀerent partitions. | | | | Here, P denotes the size of such partition P and Pi is the probability that a randomly chosen i i N tag belongs to partition P . i 7.1 Level of privacy based on anonymity set ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

label: section

text: Man-in-Middle

text: Attack

text: Resistance

text: An

text: adversary

text: is

text: unable

text: to

text: act

text: as

text: a

text: middle

text: man

text: in

text: between

text: a

text: reader

text: and

text: a

text: tag

text: because

text: it

text: is

text: infeasible

text: for

text: the

text: adversary

text: to

text: intercepts

text: any

text: transmitted

text: message

text: without

text: knowing

text: the

text: secret

text: key,

text: unique

text: identiﬁcation

text: number,

text: and

text: knowledge

text: about

text: the

text: cyclic

text: group.

text: The

text: probability

text: of

text: guessing

text: or

text: calcu-

text: lating

text: these

text: values

text: from

text: the

text: transmitted

text: message

text: is

text: negligible

text: because

text: a

text: fresh

text: nonce

text: is

text: used

text: in

text: each

text: transmitted

text: message.

text: Performance

text: Analysis

text: In

text: this

text: section,

text: we

text: present

text: eﬃciency

text: of

text: our

text: proposed

text: scheme

text: in

text: terms

text: of

text: tag

text: computation,

text: server

text: computation,

text: and

text: storage,

text: as

text: described

text: in

text: Table

text: The

text: proposed

text: scheme’s

text: search

text: complexity

text: is

text: O(γ)

text: which

text: is

text: same

text: as

text: in

text: Avione

text: et

text: al.

text: but

text: better

text: than

text: Rahman

text: et

text: al.

text: During

text: the

text: authentication

text: phase,

text: the

text: scheme

text: performs

text: only

text: bit-wise

text: XOR

text: operation

text: whereas

text: schemes

text: of

text: Avoine

text: et

text: al.

text: and

text: Rahman

text: et

text: al.

text: perform

text: symmetric

text: key

text: encryption

text: and

text: decryption.

text: Also,

text: the

text: proposed

text: scheme

text: does

text: not

text: use

text: any

text: pseudo

text: number

text: generator

text: function

text: for

text: generating

text: nonce

text: on

text: the

text: tag-side.

text: It

text: uses

text: nonce

text: generated

text: by

text: the

text: reader.

text: We

text: assume

text: that

text: all

text: the

text: parameters

text: used

text: in

text: the

text: proposed

text: scheme

text: are

text: L-bits

text: long.

text: On

text: the

text: tag

text: side,

text: our

text: scheme

text: keeps

text: ﬁve

text: items.

text: Thus

text: the

text: storage

text: cost

text: is

text: bits.

text: The

text: proposed

text: scheme

text: also

text: provides

text: mutual

text: authentication

text: among

text: a

text: reader

text: and

text: tags.

text: When

text: we

text: compare

text: with

text: and

text: in

text: terms

text: of

text: computation,

text: the

text: proposed

text: scheme

text: performs

text: very

text: less

text: computation

text: which

text: is

text: optimal

text: for

text: the

text: real

text: world

text: tiny

text: powered

text: tags.

text: Protocol

text: Entity

text: Avoine

text: Rahman

text: Proposed

text: protocol

text: Symmetric

text: encryption/

text: T

text: decryption

text: R

text: Search

text: complexity

text: R

text: O(γ)

text: O(γ

text: π

text: O(γ)

text: No.

text: of

text: PRNG

text: T

text: Required

text: memory

text: T

text: (m

text: Mutual

text: authentication

text: γ-

text: Total

text: number

text: of

text: groups

text: in

text: the

text: system.

text: π

text: Total

text: number

text: of

text: secret

text: keys

text: of

text: a

text: tag

text: associated

text: with

text: the

text: identiﬁer

text: IDx.

text: m

text: Number

text: of

text: identiﬁer

text: is

text: assigned

text: to

text: each

text: tag.

text: Table

text: Computation

text: cost

text: performance

text: comparison

text: Measurement

text: of

text: Privacy

text: In

text: this

text: section,

text: we

text: analyze

text: the

text: privacy

text: level

text: of

text: our

text: proposed

text: scheme

text: in

text: terms

text: of

text: anonymity

text: set

text: and

text: data

text: leakage

text: in

text: bits.

text: For

text: the

text: anonymity

text: sets,

text: we

text: use

text: privacy

text: metric

text: introdued

text: by

text: Also,

text: we

text: use

text: another

text: metric

text: says

text: information

text: leakage

text: for

text: data

text: leakage

text: proposed

text: by

text: shannon

text: and

text: used

text: in

text: to

text: measure

text: the

text: information

text: (in

text: bits)

text: disclosed

text: by

text: the

text: proposed

text: scheme

text: when

text: some

text: tags

text: are

text: compromised.

text: Both

text: the

text: metric

text: use

text: disjoint

text: partition

text: sets

text: of

text: tags

text: for

text: observation.

text: When

text: some

text: tags

text: are

text: compromised,

text: the

text: set

text: of

text: all

text: tags

text: are

text: partitioned

text: in

text: such

text: a

text: way

text: so

text: that

text: the

text: adversary

text: can

text: not

text: distinguish

text: the

text: tags

text: that

text: belong

text: to

text: the

text: same

text: partition

text: but

text: she

text: can

text: distinguish

text: the

text: tags

text: belong

text: to

text: diﬀerent

text: partitions.

text: Here,

text: P

text: denotes

text: the

text: size

text: of

text: such

text: partition

text: P

text: and

text: Pi

text: is

text: the

text: probability

text: that

text: a

text: randomly

text: chosen

text: i

text: i

text: N

text: tag

text: belongs

text: to

text: partition

text: P

text: i

text: Level

text: of

text: privacy

text: based

text: on

text: anonymity

text: set

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##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: ∈ \ { } ≤ exists a path P in G from v to a node u U of node weight c(V (P) u ) · ε OPT. Lemma 1. Consider an optimum solution T and an ε > 0. Then there exists ⊆ a set W V (T) of size at most 1/ε such that each node in T is ε-distant to ∪ { } W r . Proof. Consider T as a tree rooted at r. For any node u in this tree let T denote u the subtree hanging from u. A subtree T is called good if for any node in T u u the node weight (including the weight of the end nodes) of the unique path from · this node to u within T is at most ε OPT. u We traverse T in a bottom-up fashion starting with the leaves. We maintain the invariant (by removing subtrees) that for all nodes u visited so far and still being in T, the subtree T is good. To this end, when we encounter a node u such u that T is good we just continue with the traversal. If T is bad, however, then u u ≥ · there must be a path P within T ending in u of node weight c(P) ε OPT. u We include u into W and assign P as a witness to u. Because of our invariant for all (if any) children v of u we have that T is good. This means in particular v that for all nodes z in T the node weight (excluding the weight of u) of the path u · from z to u is at most ε OPT. Finally, remove T from T and continue with u the traversal. We stop when we reach the root r at which point we remove the remaining tree (for the sake of analysis). First, note that the set W has cardinality at most 1/ε because we assigned to · each node in W a witness path of weight at least ε OPT and because the witness paths are pairwise node-disjoint. Second, observe that whenever we removed a node z from T as part of a subtree T , the node weight (excluding the weight u · of u) of the path from z to u was at most ε OPT. Hence, for every node in T ∪ { } there exists such a path to a node in W r at the end of the tree traversal (cid:116)(cid:117) since every node was removed. In the sequel, we will call such a set W whose existence is provided by the above lemma an ε-skeleton. O ⊆ In a pre-preprocessing, we iterate over all n (1/ε) many sets W V with | | ≤ W 1/ε and thereby guessing the ε-skeleton W whose existence is guaranteed by the above lemma. Moreover, we prune all nodes u from the instance that are ∪ { } not ε-distant to W r . 3 The (4 + ε)-Approximation Algorithm In Chapter 3 of [17] Sadeghian describe a O(log n) approximation for Node- Weighted Quota Steiner Tree Problem. His result is established using a frame- work of [6], repeated also in [16] where a primal-dual LMP approximation al- gorithm for the prize-collecting Steiner tree problem can be used along with the Lagrangian relaxation method to obtain an approximation algorithm for the

text: exists

text: a

text: path

text: P

text: in

text: G

text: from

text: v

text: to

text: a

text: node

text: u

text: U

text: of

text: node

text: weight

text: c(V

text: (P)

text: u

text: ε

text: OPT.

text: Lemma

text: Consider

text: an

text: optimum

text: solution

text: T

text: and

text: an

text: ε

text: Then

text: there

text: exists

text: a

text: set

text: W

text: V

text: (T)

text: of

text: size

text: at

text: most

text: such

text: that

text: each

text: node

text: in

text: T

text: is

text: ε-distant

text: to

text: W

text: r

text: Proof.

text: Consider

text: T

text: as

text: a

text: tree

text: rooted

text: at

text: r.

text: For

text: any

text: node

text: u

text: in

text: this

text: tree

text: let

text: T

text: denote

text: u

text: the

text: subtree

text: hanging

text: from

text: u.

text: A

text: subtree

text: T

text: is

text: called

text: good

text: if

text: for

text: any

text: node

text: in

text: T

text: u

text: u

text: the

text: node

text: weight

text: (including

text: the

text: weight

text: of

text: the

text: end

text: nodes)

text: of

text: the

text: unique

text: path

text: from

text: this

text: node

text: to

text: u

text: within

text: T

text: is

text: at

text: most

text: ε

text: OPT.

text: u

text: We

text: traverse

text: T

text: in

text: a

text: bottom-up

text: fashion

text: starting

text: with

text: the

text: leaves.

text: We

text: maintain

text: the

text: invariant

text: (by

text: removing

text: subtrees)

text: that

text: for

text: all

text: nodes

text: u

text: visited

text: so

text: far

text: and

text: still

text: being

text: in

text: T,

text: the

text: subtree

text: T

text: is

text: good.

text: To

text: this

text: end,

text: when

text: we

text: encounter

text: a

text: node

text: u

text: such

text: u

text: that

text: T

text: is

text: good

text: we

text: just

text: continue

text: with

text: the

text: traversal.

text: If

text: T

text: is

text: bad,

text: however,

text: then

text: u

text: u

text: there

text: must

text: be

text: a

text: path

text: P

text: within

text: T

text: ending

text: in

text: u

text: of

text: node

text: weight

text: c(P)

text: ε

text: OPT.

text: u

text: We

text: include

text: u

text: into

text: W

text: and

text: assign

text: P

text: as

text: a

text: witness

text: to

text: u.

text: Because

text: of

text: our

text: invariant

text: for

text: all

text: (if

text: any)

text: children

text: v

text: of

text: u

text: we

text: have

text: that

text: T

text: is

text: good.

text: This

text: means

text: in

text: particular

text: v

text: that

text: for

text: all

text: nodes

text: z

text: in

text: T

text: the

text: node

text: weight

text: (excluding

text: the

text: weight

text: of

text: u)

text: of

text: the

text: path

text: u

text: from

text: z

text: to

text: u

text: is

text: at

text: most

text: ε

text: OPT.

text: Finally,

text: remove

text: T

text: from

text: T

text: and

text: continue

text: with

text: u

text: the

text: traversal.

text: We

text: stop

text: when

text: we

text: reach

text: the

text: root

text: r

text: at

text: which

text: point

text: we

text: remove

text: the

text: remaining

text: tree

text: (for

text: the

text: sake

text: of

text: analysis).

text: First,

text: note

text: that

text: the

text: set

text: W

text: has

text: cardinality

text: at

text: most

text: because

text: we

text: assigned

text: to

text: each

text: node

text: in

text: W

text: a

text: witness

text: path

text: of

text: weight

text: at

text: least

text: ε

text: OPT

text: and

text: because

text: the

text: witness

text: paths

text: are

text: pairwise

text: node-disjoint.

text: Second,

text: observe

text: that

text: whenever

text: we

text: removed

text: a

text: node

text: z

text: from

text: T

text: as

text: part

text: of

text: a

text: subtree

text: T

text: the

text: node

text: weight

text: (excluding

text: the

text: weight

text: u

text: of

text: u)

text: of

text: the

text: path

text: from

text: z

text: to

text: u

text: was

text: at

text: most

text: ε

text: OPT.

text: Hence,

text: for

text: every

text: node

text: in

text: T

text: there

text: exists

text: such

text: a

text: path

text: to

text: a

text: node

text: in

text: W

text: r

text: at

text: the

text: end

text: of

text: the

text: tree

text: traversal

text: since

text: every

text: node

text: was

text: removed.

text: In

text: the

text: sequel,

text: we

text: will

text: call

text: such

text: a

text: set

text: W

text: whose

text: existence

text: is

text: provided

text: by

text: the

text: above

text: lemma

text: an

text: ε-skeleton.

text: O

text: In

text: a

text: pre-preprocessing,

text: we

text: iterate

text: over

text: all

text: n

text: many

text: sets

text: W

text: V

text: with

text: W

text: and

text: thereby

text: guessing

text: the

text: ε-skeleton

text: W

text: whose

text: existence

text: is

text: guaranteed

text: by

text: the

text: above

text: lemma.

text: Moreover,

text: we

text: prune

text: all

text: nodes

text: u

text: from

text: the

text: instance

text: that

text: are

text: not

text: ε-distant

text: to

text: W

text: r

text: The

text: ε)-Approximation

text: Algorithm

text: In

text: Chapter

text: of

text: Sadeghian

text: describe

text: a

text: O(log

text: n)

text: approximation

text: for

text: Node-

text: Weighted

text: Quota

text: Steiner

text: Tree

text: Problem.

text: His

text: result

text: is

text: established

text: using

text: a

text: frame-

text: work

text: of

text: repeated

text: also

text: in

text: where

text: a

text: primal-dual

text: LMP

text: approximation

text: al-

text: gorithm

text: for

text: the

text: prize-collecting

text: Steiner

text: tree

text: problem

text: can

text: be

text: used

text: along

text: with

text: the

text: Lagrangian

text: relaxation

text: method

text: to

text: obtain

text: an

text: approximation

text: algorithm

text: for

text: the


text: 10 distinct classes of data, and determine which machine each other. learning architectures have an inductive bias [10] suited to each class. IX. ACKNOWLEDGEMENTS Appendix B: Representing a Linear Classiﬁer as an MPS We thank David J. Schwab for an especially careful reading of the paper and many helpful comments. We One can write a model of the form Eq. (9) with the also thank Glen Evenbly, William Huggins, Matthew weights in MPS form such that the output of the model Fishman, Steven White, John Terilla and Yiannis Vlas- is guaranteed to be the same as a linear classiﬁer with sopoulos for helpful comments and discussions. weights V , assuming local feature maps of the form Appendix A: Tensor Diagram Notation Eq. (22) namely φ(x) = [1, x]. This mapping was ﬁrst discussed in Ref. 5. Tensor diagram notation is a simple, graphical nota- Say we want to make our model output equivalent to tion for representing networks of contractions of high- a linear classiﬁer with parameters V order tensors. The main rules of this notation are: • A tensor with n indices (an order n tensor) is rep- (cid:88)N resented as a shape with n lines coming out of it. f (x) = V · x = V xj . (B1) lin j Each line represents a speciﬁc index but indices do n=1 not have to be labeled or named when they can be distinguished by context. First, assume the weights of our model Eq. (9) are in MPS form, meaning • Connecting index lines between a pair of ten- sors indicates that these indices are contracted, (cid:88) or summed over. Ws1s2s3···sN = Asα11Asα22α3Asα33α4AsαNN−1 . (B2) Other informal conventions may be used by speciﬁc au- α thors, such as choosing special shapes or decorations of tensors to denote special properties. For example, in Now deﬁne each MPS tensor Asαjj−1αj for each ﬁxed this work a triangular shape indicates an isometric ten- value of sj as follows: sor. Unless otherwise speciﬁed, the only information that matters is the connectivity of the network, with no ﬁxed (cid:20) (cid:21) 1 0 meaning given to the orientation or ordering of the index A(αsjj−=11α)j = 0 1 (B3) lines. Furthermore, no special properties of the tensors (cid:20) (cid:21) are assumed such as symmetries or transformation prop- 0 0 erties, unless speciﬁcally stated. A(αsjj−=12α)j = Vj 0 . (B4) We emphasize that tensor diagram notation is com- pletely rigorous, and just a way of notating complicated For the ﬁrst A tensor one only takes the second row sums. Unlike similar-looking neural network diagrams, of each matrix and for the last A tensor one only takes every element of a tensor diagram is a purely linear trans- the ﬁrst column of each matrix. To include a constant formation (of the vector spaces whose basis elements are shift, either add a ﬁctitious input component x0 = 1 to labeled by the indices). the deﬁnition of x or suitably adjust the ﬁrst “A” tensor. The main advantage of tensor diagram notation is that This mapping from a linear classiﬁer can also be extended it frees one from having to assign names to every index, to more general local feature maps φs(x) of dimension d which can be cumbersome for complicated tensor net- by suitably deﬁning an “extended linear classiﬁer” model works. The notation also makes it easier to compactly express sophisticated algorithms and to visually under- stand diﬀerent families of tensor networks. Various oper- (cid:88)N (cid:88)d ations such as traces, outer products, transposes, or ma- f (x) = V φs(x ) (B5) ext-lin. ns n tricization can be expressed implicitly in diagrammatic n=1 s=1 form without requiring additional notation or symbols. For example, the diagrammatic expression of an outer and lifting this model to an MPS in a similar manner product is simply the placement of two tensors nearby (the resulting MPS has bond dimension d + 1). ∗ [2] Hanie Sedghi and Anima Anandkumar, “Training input-output recurrent neural networks through spectral methods,” [1] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakaadrxe,iv:1a6n0d3.M00a9t5u4s T(2el0g1a6r)s.ky, “Tensor decompositions for learning latent variable models,” Journal of Machine Learning[3R] eAselaexrcahnd1e5r, 2N7o7v3i–k2o8v3,2 (D2m01i4tr)y. Podoprikhin, Anton Osokin, and Dmitry Vetrov, “Tensorizing neural networks,” ##LTLine## ##LTLine## ##LTLine##

text: distinct

text: classes

text: of

text: data,

text: and

text: determine

text: which

text: machine

text: each

text: other.

text: learning

text: architectures

text: have

text: an

text: inductive

text: bias

text: suited

text: to

text: each

text: class.

text: IX.

text: ACKNOWLEDGEMENTS

text: Appendix

text: B:

text: Representing

text: a

text: Linear

text: Classiﬁer

text: as

text: an

text: MPS

text: We

text: thank

text: David

text: J.

text: Schwab

text: for

text: an

text: especially

text: careful

text: reading

text: of

text: the

text: paper

text: and

text: many

text: helpful

text: comments.

text: We

text: One

text: can

text: write

text: a

text: model

text: of

text: the

text: form

text: Eq.

text: with

text: the

text: also

text: thank

text: Glen

text: Evenbly,

text: William

text: Huggins,

text: Matthew

text: weights

text: in

text: MPS

text: form

text: such

text: that

text: the

text: output

text: of

text: the

text: model

text: Fishman,

text: Steven

text: White,

text: John

text: Terilla

text: and

text: Yiannis

text: Vlas-

text: is

text: guaranteed

text: to

text: be

text: the

text: same

text: as

text: a

text: linear

text: classiﬁer

text: with

text: sopoulos

text: for

text: helpful

text: comments

text: and

text: discussions.

text: weights

text: V

text: assuming

text: local

text: feature

text: maps

text: of

text: the

text: form

text: Appendix

text: A:

text: Tensor

text: Diagram

text: Notation

text: Eq.

text: namely

text: φ(x)

text: x].

text: This

text: mapping

text: was

text: ﬁrst

text: discussed

text: in

text: Ref.

text: Tensor

text: diagram

text: notation

text: is

text: a

text: simple,

text: graphical

text: nota-

text: Say

text: we

text: want

text: to

text: make

text: our

text: model

text: output

text: equivalent

text: to

text: tion

text: for

text: representing

text: networks

text: of

text: contractions

text: of

text: high-

text: a

text: linear

text: classiﬁer

text: with

text: parameters

text: V

text: order

text: tensors.

text: The

text: main

text: rules

text: of

text: this

text: notation

text: are:

text: A

text: tensor

text: with

text: n

text: indices

text: (an

text: order

text: n

text: tensor)

text: is

text: rep-

text: resented

text: as

text: a

text: shape

text: with

text: n

text: lines

text: coming

text: out

text: of

text: it.

text: f

text: (x)

text: V

text: x

text: V

text: xj

text: lin

text: j

text: Each

text: line

text: represents

text: a

text: speciﬁc

text: index

text: but

text: indices

text: do

text: not

text: have

text: to

text: be

text: labeled

text: or

text: named

text: when

text: they

text: can

text: be

text: distinguished

text: by

text: context.

text: First,

text: assume

text: the

text: weights

text: of

text: our

text: model

text: Eq.

text: are

text: in

text: MPS

text: form,

text: meaning

text: Connecting

text: index

text: lines

text: between

text: a

text: pair

text: of

text: ten-

text: sors

text: indicates

text: that

text: these

text: indices

text: are

text: contracted,

text: or

text: summed

text: over.

text: Other

text: informal

text: conventions

text: may

text: be

text: used

text: by

text: speciﬁc

text: au-

text: α

text: thors,

text: such

text: as

text: choosing

text: special

text: shapes

text: or

text: decorations

text: of

text: tensors

text: to

text: denote

text: special

text: properties.

text: For

text: example,

text: in

text: Now

text: deﬁne

text: each

text: MPS

text: tensor

text: for

text: each

text: ﬁxed

text: this

text: work

text: a

text: triangular

text: shape

text: indicates

text: an

text: isometric

text: ten-

text: value

text: of

text: sj

text: as

text: follows:

text: sor.

text: Unless

text: otherwise

text: speciﬁed,

text: the

text: only

text: information

text: that

text: matters

text: is

text: the

text: connectivity

text: of

text: the

text: network,

text: with

text: no

text: ﬁxed

text: meaning

text: given

text: to

text: the

text: orientation

text: or

text: ordering

text: of

text: the

text: index

text: lines.

text: Furthermore,

text: no

text: special

text: properties

text: of

text: the

text: tensors

text: are

text: assumed

text: such

text: as

text: symmetries

text: or

text: transformation

text: prop-

text: erties,

text: unless

text: speciﬁcally

text: stated.

text: Vj

text: We

text: emphasize

text: that

text: tensor

text: diagram

text: notation

text: is

text: com-

text: pletely

text: rigorous,

text: and

text: just

text: a

text: way

text: of

text: notating

text: complicated

text: For

text: the

text: ﬁrst

text: A

text: tensor

text: one

text: only

text: takes

text: the

text: second

text: row

text: sums.

text: Unlike

text: similar-looking

text: neural

text: network

text: diagrams,

text: of

text: each

text: matrix

text: and

text: for

text: the

text: last

text: A

text: tensor

text: one

text: only

text: takes

text: every

text: element

text: of

text: a

text: tensor

text: diagram

text: is

text: a

text: purely

text: linear

text: trans-

text: the

text: ﬁrst

text: column

text: of

text: each

text: matrix.

text: To

text: include

text: a

text: constant

text: formation

text: (of

text: the

text: vector

text: spaces

text: whose

text: basis

text: elements

text: are

text: shift,

text: either

text: add

text: a

text: ﬁctitious

text: input

text: component

text: to

text: labeled

text: by

text: the

text: indices).

text: the

text: deﬁnition

text: of

text: x

text: or

text: suitably

text: adjust

text: the

text: ﬁrst

text: “A”

text: tensor.

text: The

text: main

text: advantage

text: of

text: tensor

text: diagram

text: notation

text: is

text: that

text: This

text: mapping

text: from

text: a

text: linear

text: classiﬁer

text: can

text: also

text: be

text: extended

text: it

text: frees

text: one

text: from

text: having

text: to

text: assign

text: names

text: to

text: every

text: index,

text: to

text: more

text: general

text: local

text: feature

text: maps

text: φs(x)

text: of

text: dimension

text: d

text: which

text: can

text: be

text: cumbersome

text: for

text: complicated

text: tensor

text: net-

text: by

text: suitably

text: deﬁning

text: an

text: “extended

text: linear

text: classiﬁer”

text: model

text: works.

text: The

text: notation

text: also

text: makes

text: it

text: easier

text: to

text: compactly

text: express

text: sophisticated

text: algorithms

text: and

text: to

text: visually

text: under-

text: stand

text: diﬀerent

text: families

text: of

text: tensor

text: networks.

text: Various

text: oper-

text: ations

text: such

text: as

text: traces,

text: outer

text: products,

text: transposes,

text: or

text: ma-

text: f

text: (x)

text: V

text: φs(x

text: ext-lin.

text: ns

text: n

text: tricization

text: can

text: be

text: expressed

text: implicitly

text: in

text: diagrammatic

text: form

text: without

text: requiring

text: additional

text: notation

text: or

text: symbols.

text: For

text: example,

text: the

text: diagrammatic

text: expression

text: of

text: an

text: outer

text: and

text: lifting

text: this

text: model

text: to

text: an

text: MPS

text: in

text: a

text: similar

text: manner

text: product

text: is

text: simply

text: the

text: placement

text: of

text: two

text: tensors

text: nearby

text: (the

text: resulting

text: MPS

text: has

text: bond

text: dimension

text: d

text: Hanie

text: Sedghi

text: and

text: Anima

text: Anandkumar,

text: “Training

text: input-output

text: recurrent

text: neural

text: networks

text: through

text: spectral

text: methods,”

text: Animashree

text: Anandkumar,

text: Rong

text: Ge,

text: Daniel

text: Hsu,

text: Sham

text: M.

text: “Tensor

text: decompositions

text: for

text: learning

text: latent

text: variable

text: models,”

text: Journal

text: of

text: Machine

text: Podoprikhin,

text: Anton

text: Osokin,

text: and

text: Dmitry

text: Vetrov,

text: “Tensorizing

text: neural

text: networks,”

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: accepted if α > µ; otherwise, the proposed candidate is rejected. 0 The Metropolis-within-Gibbs sampler described above is computationally eﬃcient. In terms of computational cost, sampling from the full conditional distributions of b, τ2, σ2, 1 ∗ σ2, w , w , and w requires O(m3 + m2n + n3 + n3 + n(n + n )) ﬂops. Sampling from 2 1 2 1 2 1 2 full conditional distributions for θ and θ requires O(m3 + m2n + n3 + n3 + n(n + n )) 1 2 1 2 1 2 ﬂops. Therefore, the overall computational cost for each MCMC iteration is O(m2n + n3 + n3 + n(n + n )). Note that m, n , and n are all smaller than n, which makes 1 2 1 2 1 2 this inference procedure much more eﬃcient than dealing with marginalized joint density by integrating random eﬀects. It is worth mentioning that if either n or n is large, it 1 2 is desirable or even necessary to further reduce computational complexity of the current Bayesian inference procedure, and we discuss in Section 5 on how to extend AAGP and the Metropolis-within-Gibbs sampler for very large data with large n or n . Moreover, 1 2 although we sample the n-dimensional vectors w and w in the Gibbs sampler, it is worth 1 2 noting that there is no need to store all samples of these two high-dimensional vectors (cid:82) (cid:82) | from all MCMC iterations, because they can always be recovered easily through [w Z] = 1 | | { } | | | { } [w σ2, θ ][σ2, θ Z] d σ2, θ and [w Z] = [w σ2, θ ][σ2, θ Z] d σ2, θ . Therefore, 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 the overall memory cost for each MCMC iteration is roughly O(mn + n2 + n2). 1 2 ∗ To further improve computational eﬃciency, the random vector w and parameter σ2 1 | · ≡ | ∗ can be integrated out when sampling from p(θ ) p(θ w , w , σ2). That is, we 1 1 1 1 ∗ | ∗ seek the joint conditional distribution p(θ , w , σ2 w ), and then integrate out w , σ2 to 1 1 1 1 obtain the conditional distribution of θ given w . Similar eﬃciency can be achieved to 1 1 | · ≡ | obtain samples of θ from p(θ ) p(θ w , σ2). That is, we seek the joint conditional 2 2 2 2 2 | distribution p(θ , σ2 w ), and then integrate out σ2. 2 2 2 2 3.2 Prediction for Y (x ) 0 ∈ X For any design location x = (s , u ) , our interest is to make prediction for Y (x ), 0 0 0 0 which is further written as Y (x ) = h(x )T b + w (x ) + w (x ). (3.8) 0 0 1 0 2 0 13

text: accepted

text: if

text: α

text: µ;

text: otherwise,

text: the

text: proposed

text: candidate

text: is

text: rejected.

text: The

text: Metropolis-within-Gibbs

text: sampler

text: described

text: above

text: is

text: computationally

text: eﬃcient.

text: In

text: terms

text: of

text: computational

text: cost,

text: sampling

text: from

text: the

text: full

text: conditional

text: distributions

text: of

text: b,

text: w

text: w

text: and

text: w

text: requires

text: n(n

text: n

text: ﬂops.

text: Sampling

text: from

text: full

text: conditional

text: distributions

text: for

text: θ

text: and

text: θ

text: requires

text: n(n

text: n

text: ﬂops.

text: Therefore,

text: the

text: overall

text: computational

text: cost

text: for

text: each

text: MCMC

text: iteration

text: is

text: n(n

text: n

text: Note

text: that

text: m,

text: n

text: and

text: n

text: are

text: all

text: smaller

text: than

text: n,

text: which

text: makes

text: this

text: inference

text: procedure

text: much

text: more

text: eﬃcient

text: than

text: dealing

text: with

text: marginalized

text: joint

text: density

text: by

text: integrating

text: random

text: eﬀects.

text: It

text: is

text: worth

text: mentioning

text: that

text: if

text: either

text: n

text: or

text: n

text: is

text: large,

text: it

text: is

text: desirable

text: or

text: even

text: necessary

text: to

text: further

text: reduce

text: computational

text: complexity

text: of

text: the

text: current

text: Bayesian

text: inference

text: procedure,

text: and

text: we

text: discuss

text: in

text: Section

text: on

text: how

text: to

text: extend

text: AAGP

text: and

text: the

text: Metropolis-within-Gibbs

text: sampler

text: for

text: very

text: large

text: data

text: with

text: large

text: n

text: or

text: n

text: Moreover,

text: although

text: we

text: sample

text: the

text: n-dimensional

text: vectors

text: w

text: and

text: w

text: in

text: the

text: Gibbs

text: sampler,

text: it

text: is

text: worth

text: noting

text: that

text: there

text: is

text: no

text: need

text: to

text: store

text: all

text: samples

text: of

text: these

text: two

text: high-dimensional

text: vectors

text: from

text: all

text: MCMC

text: iterations,

text: because

text: they

text: can

text: always

text: be

text: recovered

text: easily

text: through

text: [w

text: Z]

text: [w

text: θ

text: θ

text: Z]

text: d

text: θ

text: and

text: [w

text: Z]

text: [w

text: θ

text: θ

text: Z]

text: d

text: θ

text: Therefore,

text: the

text: overall

text: memory

text: cost

text: for

text: each

text: MCMC

text: iteration

text: is

text: roughly

text: O(mn

text: To

text: further

text: improve

text: computational

text: eﬃciency,

text: the

text: random

text: vector

text: w

text: and

text: parameter

text: σ2

text: can

text: be

text: integrated

text: out

text: when

text: sampling

text: from

text: p(θ

text: p(θ

text: w

text: w

text: That

text: is,

text: we

text: seek

text: the

text: joint

text: conditional

text: distribution

text: p(θ

text: w

text: σ2

text: w

text: and

text: then

text: integrate

text: out

text: w

text: σ2

text: to

text: obtain

text: the

text: conditional

text: distribution

text: of

text: θ

text: given

text: w

text: Similar

text: eﬃciency

text: can

text: be

text: achieved

text: to

text: obtain

text: samples

text: of

text: θ

text: from

text: p(θ

text: p(θ

text: w

text: That

text: is,

text: we

text: seek

text: the

text: joint

text: conditional

text: distribution

text: p(θ

text: σ2

text: w

text: and

text: then

text: integrate

text: out

text: Prediction

text: for

text: Y

text: (x

text: X

text: For

text: any

text: design

text: location

text: x

text: (s

text: u

text: our

text: interest

text: is

text: to

text: make

text: prediction

text: for

text: Y

text: (x

text: which

text: is

text: further

text: written

text: as

text: Y

text: (x

text: h(x

text: )T

text: b

text: w

text: (x

text: w

text: (x


text: (ALCI) for predictive values, to assess model adequacy and predictive accuracy. · First Scenario The latent true process Y ( ) is assumed to have a Gneiting’s space- time covaraince function in Eq. (B.1) with variance σ2 = 1, spatial parameter c = 5, time 1 parameter a = 1, nugget variance τ2 = 0.2, interaction parameter β = 0.8, and smoothness parameter α = 0.5. The linear components are b = (1, 0.5)T . We compare the results of AAGP with the space-time MPP and the full Gaussian process. The full Gaussian process based on true covariance function is used to serve as a benchmark. The prior distributions are assigned as described above. Table 2. Simulation results under Gneiting’s space-time correlation function First Scenario Parameters True value Full GP MPP AAGP b 1 0.989(0.980, 0.998) 0.990(0.981, 1.000) 0.981(0.959, 1.007) 1 b 0.5 0.503(0.473, 0.533) 0.503(0.491, 0.516) 0.507(0.468, 0.534) 2 σ2 1 0.978(0.869, 1.096) 1.419(1.236, 1.645) 0.869(0.787, 1.038) 1 β 0.8 0.841(0.425, 0.994) 0.935(0.710, 0.999) 0.928(0.631, 0.997) a 1 0.991(0.754, 1.255) 2.070(1.613, 2.659) 2.805(2.054, 3.872) c 5 4.768(4.022, 5.710) 5.465(4.503, 6.560) 5.542(4.685, 6.750) σ2 0.303(0.221, 0.341) 2 φ 0.244(0.035, 0.488) s φ 1.370(1.344, 1.417) t τ2 0.2 0.182(0.146, 0.221) 0.130(0.049, 0.208) 0.060(0.021, 0.130) MSPE 0.23 0.51 0.33 ALCI 1.92 3.24 2.97 Time (h) 21.2 3.94 5.01 Table 2 shows the results obtained from three diﬀerent methods. The true values for parameters b, σ2, β, a, c, σ2, φ , φ , τ2 are listed in the second column of table 2. AAGP gives 1 2 s t better prediction results than MPP, since the MSPE in AAGP is 30% smaller than that in MPP, and is close to MSPE in the full GP. This conﬁrms that the separable component of the AAGP can model part of the unexplained variability from the MPP. The spread of predictive distribution is very similar for both MPP and AAGP, which suggests that MPP and AAGP can quantify uncertainties in predictions very well, but the predictive distribution for AAGP is slightly accurate than that for MPP. In AAGP, the regression coeﬃcients b , b are estimated very well in comparison to the full GP results. The mean 1 2 of the posterior for the variance parameters σ2 = 0.869 and σ2 = 0.303. The AAGP shows 1 2 19 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (ALCI)

text: for

text: predictive

text: values,

text: to

text: assess

text: model

text: adequacy

text: and

text: predictive

text: accuracy.

text: First

text: Scenario

text: The

text: latent

text: true

text: process

text: Y

text: is

text: assumed

text: to

text: have

text: a

text: Gneiting’s

text: space-

text: time

text: covaraince

text: function

text: in

text: Eq.

text: with

text: variance

text: σ2

text: spatial

text: parameter

text: c

text: time

text: parameter

text: a

text: nugget

text: variance

text: τ2

text: interaction

text: parameter

text: β

text: and

text: smoothness

text: parameter

text: α

text: The

text: linear

text: components

text: are

text: b

text: We

text: compare

text: the

text: results

text: of

text: AAGP

text: with

text: the

text: space-time

text: MPP

text: and

text: the

text: full

text: Gaussian

text: process.

text: The

text: full

text: Gaussian

text: process

text: based

text: on

text: true

text: covariance

text: function

text: is

text: used

text: to

text: serve

text: as

text: a

text: benchmark.

text: The

text: prior

text: distributions

text: are

text: assigned

text: as

text: described

text: above.

text: Table

text: Simulation

text: results

text: under

text: Gneiting’s

text: space-time

text: correlation

text: function

text: First

text: Scenario

text: Parameters

text: True

text: value

text: Full

text: GP

text: MPP

text: AAGP

text: b

text: b

text: σ2

text: β

text: a

text: c

text: σ2

text: φ

text: s

text: φ

text: t

text: τ2

text: MSPE

text: ALCI

text: Time

text: (h)

text: Table

text: shows

text: the

text: results

text: obtained

text: from

text: three

text: diﬀerent

text: methods.

text: The

text: true

text: values

text: for

text: parameters

text: b,

text: β,

text: a,

text: c,

text: φ

text: φ

text: τ2

text: are

text: listed

text: in

text: the

text: second

text: column

text: of

text: table

text: AAGP

text: gives

text: s

text: t

text: better

text: prediction

text: results

text: than

text: MPP,

text: since

text: the

text: MSPE

text: in

text: AAGP

text: is

text: smaller

text: than

text: that

text: in

text: MPP,

text: and

text: is

text: close

text: to

text: MSPE

text: in

text: the

text: full

text: GP.

text: This

text: conﬁrms

text: that

text: the

text: separable

text: component

text: of

text: the

text: AAGP

text: can

text: model

text: part

text: of

text: the

text: unexplained

text: variability

text: from

text: the

text: MPP.

text: The

text: spread

text: of

text: predictive

text: distribution

text: is

text: very

text: similar

text: for

text: both

text: MPP

text: and

text: AAGP,

text: which

text: suggests

text: that

text: MPP

text: and

text: AAGP

text: can

text: quantify

text: uncertainties

text: in

text: predictions

text: very

text: well,

text: but

text: the

text: predictive

text: distribution

text: for

text: AAGP

text: is

text: slightly

text: accurate

text: than

text: that

text: for

text: MPP.

text: In

text: AAGP,

text: the

text: regression

text: coeﬃcients

text: b

text: b

text: are

text: estimated

text: very

text: well

text: in

text: comparison

text: to

text: the

text: full

text: GP

text: results.

text: The

text: mean

text: of

text: the

text: posterior

text: for

text: the

text: variance

text: parameters

text: σ2

text: and

text: σ2

text: The

text: AAGP

text: shows

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: a clear preference for the Gneiting’s nonseparable covariance function in this case. The proposed model seems to be able to automatically assign the variation missed by MPP to the separable model and the nugget. Despite the fact that the nugget is under-estimated and the overall variance σ2 + σ2 overestimated, the prediction performance of the proposed 1 2 method is better. One possible explanation of the above value is that the sum of estimated σ2 and τ2 both together plays a role as “nugget eﬀect”. It is worth noting that the space- 2 time interaction parameter β has very wide credible interval in full GP, which indicates that this parameter cannot be estimated accurately even under the true model. · Second Scenario The latent true process Y ( ) is assumed to have a squared expo- nential covariance functions in space and time with variance σ2 = 1, spatial correlation 2 parameter φ = 5, time correlation parameter φ = 1, and nugget variance τ2 = 0.2. The s t linear components are deﬁned as b = (1, 0.5)T . As previously, we compare AAGP and the space-time MPP and use the full GP based on true covariance function as a benchmark. In the MPP, the parent correlation function is assumed to be Gneiting’s space-time correlation function. The prior distributions are speciﬁed as above. Table 3. Simulation results under separable correlation function Second Scenario Parameters True value Full GP MPP AAGP b 1 0.989(0.975, 1.004) 1.003(0.973, 1.033) 0.989(0.974, 1.003) 1 b 0.5 0.503(0.483, 0.522) 0.498(0.455, 0.542) 0.503(0.484, 0.522) 2 σ2 0.083(0.045, 0.163) 0.030(0.012, 0.060) 1 β 0.737(0.104, 0.987) 0.554(0.027, 0.982) a 0.768(0.378, 1.564) 9.425(2.390, 20.00) c 17.81(9.540, 20.00) 0.198(0.023, 0.835) σ2 1 0.953(0.752, 1.195) 0.997(0.830, 1.187) 2 φ 5 4.968(4.646, 5.213) 5.169(4.922, 5.262) s φ 1 0.990(0.918, 1.067) 1.005(0.940, 1.083) t τ2 0.2 0.188(0.179, 0.196) 0.950(0.992, 1.037) 0.187(0.178, 0.196) MSPE 0.02 0.87 0.02 ALCI 0.58 0.98 0.69 Time (h) 40.9 1.39 2.78 Simulation results in Table 3 suggest that MPP fails to detect the separability of the true ﬁeld with Gneiting’s space-time correlation function, since β has 95% credible interval spreading out almost its entire support [0, 1]. Compared to MPP, AAGP can detect the 20 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: a

text: clear

text: preference

text: for

text: the

text: Gneiting’s

text: nonseparable

text: covariance

text: function

text: in

text: this

text: case.

text: The

text: proposed

text: model

text: seems

text: to

text: be

text: able

text: to

text: automatically

text: assign

text: the

text: variation

text: missed

text: by

text: MPP

text: to

text: the

text: separable

text: model

text: and

text: the

text: nugget.

text: Despite

text: the

text: fact

text: that

text: the

text: nugget

text: is

text: under-estimated

text: and

text: the

text: overall

text: variance

text: σ2

text: σ2

text: overestimated,

text: the

text: prediction

text: performance

text: of

text: the

text: proposed

text: method

text: is

text: better.

text: One

text: possible

text: explanation

text: of

text: the

text: above

text: value

text: is

text: that

text: the

text: sum

text: of

text: estimated

text: σ2

text: and

text: τ2

text: both

text: together

text: plays

text: a

text: role

text: as

text: “nugget

text: eﬀect”.

text: It

text: is

text: worth

text: noting

text: that

text: the

text: space-

text: time

text: interaction

text: parameter

text: β

text: has

text: very

text: wide

text: credible

text: interval

text: in

text: full

text: GP,

text: which

text: indicates

text: that

text: this

text: parameter

text: cannot

text: be

text: estimated

text: accurately

text: even

text: under

text: the

text: true

text: model.

text: Second

text: Scenario

text: The

text: latent

text: true

text: process

text: Y

text: is

text: assumed

text: to

text: have

text: a

text: squared

text: expo-

text: nential

text: covariance

text: functions

text: in

text: space

text: and

text: time

text: with

text: variance

text: σ2

text: spatial

text: correlation

text: parameter

text: φ

text: time

text: correlation

text: parameter

text: φ

text: and

text: nugget

text: variance

text: τ2

text: The

text: s

text: t

text: linear

text: components

text: are

text: deﬁned

text: as

text: b

text: As

text: previously,

text: we

text: compare

text: AAGP

text: and

text: the

text: space-time

text: MPP

text: and

text: use

text: the

text: full

text: GP

text: based

text: on

text: true

text: covariance

text: function

text: as

text: a

text: benchmark.

text: In

text: the

text: MPP,

text: the

text: parent

text: correlation

text: function

text: is

text: assumed

text: to

text: be

text: Gneiting’s

text: space-time

text: correlation

text: function.

text: The

text: prior

text: distributions

text: are

text: speciﬁed

text: as

text: above.

text: Table

text: Simulation

text: results

text: under

text: separable

text: correlation

text: function

text: Second

text: Scenario

text: Parameters

text: True

text: value

text: Full

text: GP

text: MPP

text: AAGP

text: b

text: b

text: σ2

text: β

text: a

text: c

text: σ2

text: φ

text: s

text: φ

text: t

text: τ2

text: MSPE

text: ALCI

text: Time

text: (h)

text: Simulation

text: results

text: in

text: Table

text: suggest

text: that

text: MPP

text: fails

text: to

text: detect

text: the

text: separability

text: of

text: the

text: true

text: ﬁeld

text: with

text: Gneiting’s

text: space-time

text: correlation

text: function,

text: since

text: β

text: has

text: credible

text: interval

text: spreading

text: out

text: almost

text: its

text: entire

text: support

text: Compared

text: to

text: MPP,

text: AAGP

text: can

text: detect

text: the

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: IMMERSED MO¨BIUS BANDS IN KNOT COMPLEMENTS MARK C. HUGHES AND SEUNGWON KIM Abstract. We study the immersed crosscap number of a knot, which is a nonorientable analogue of the immersed Seifert genus. Unlike the orientable case, we show that the immersed crosscap number can diﬀer from the em- bedded crosscap number by arbitrarily large amounts, and that it is neither bounded below nor above by the 4-dimensional crosscap number. We then study knots with immersed crosscap number 1, and show that a knot has im- mersed crosscap number 1 if and only if it is a nonntrivial (2p,q)-torus or (2p,q)-cable knot. 1. Introduction ⊂ One method to deﬁne a measure of the complexity of a knot K S3 is by de- scribing the minimal topological complexity of a compact surface F whose boundary is equal to K. When F is required to be orientable and embedded in S3 this gives the classical Seifert genus g (K) of K; when the requirement that F be embedded 3 in S3 is weakened, and we allow embedded surfaces in B4 we obtain the slice genus g (K) of K. Here we are thinking of S3 as the boundary of B4. 4 Loosening the requirement that F be embedded in S3 in another direction, we can instead consider surfaces F which are merely immersed in S3. While it is easy to verify that every knot K is the boundary of an immersed disk in S3, if we consider only immersed surfaces which are embedded along a neighborhood of their boundaries we obtain immersed Seifert surfaces for K. The minimal genus of any immersed Seifert surface for K is called the immersed Seifert genus of K, and is denoted g (K). While g indeed takes nontrivial values on knots in S3, using I I foliations Gabai [5] proved that the resulting knot invariant is always equal to the Seifert genus. Both invariants are in turn bounded below by the slice genus. Dropping the requirement that F be orientable, we can instead consider nonori- entable immersed spanning surfaces, deﬁned in a similar way as above. This gives rise to a nonorientable analogue of the immersed Seifert genus, called the immersed crosscap number γ (K) of the knot K. Our main result involves knots with im- I mersed crosscap number 1, i.e. knots which bound immersed M¨obius bands that are embedded along their boundaries. ⊂ Theorem 1. A knot K S3 has γ (K) = 1 if and only if K is a nontrivial I (2p, q)-torus or (2p, q)-cable knot. | | ≥ For p 2, we say that K is a (p, q)-cable knot if it can be isotoped to lie on ⊂ the bounda·ry of a· solid torus V∼ Z ⊕S3Zwhose core is knotted, where it represents the class q m + p l in π (∂V ) = . Here m and l are the homotopy classes of 1 the meridian and the Seifert-framed longitude of ∂V respectively. In a similar way, we can also deﬁne the 3-dimensional (embedded) crosscap num- ber γ (K) and 4-dimensional (embedded) crosscap number γ (K) of a knot, which 3 4 1

text: IMMERSED

text: MO¨BIUS

text: BANDS

text: IN

text: KNOT

text: COMPLEMENTS

text: MARK

text: C.

text: HUGHES

text: AND

text: SEUNGWON

text: KIM

text: Abstract.

text: We

label: abstract

text: study

text: the

text: immersed

text: crosscap

text: number

text: of

text: a

text: knot,

text: which

text: is

text: a

text: nonorientable

text: analogue

text: of

text: the

text: immersed

text: Seifert

text: genus.

text: Unlike

text: the

text: orientable

text: case,

text: we

text: show

text: that

text: the

text: immersed

text: crosscap

text: number

text: can

text: diﬀer

text: from

text: the

text: em-

text: bedded

text: crosscap

text: number

text: by

text: arbitrarily

text: large

text: amounts,

text: and

text: that

text: it

text: is

text: neither

text: bounded

text: below

text: nor

text: above

text: by

text: the

text: crosscap

text: number.

text: We

text: then

text: study

text: knots

text: with

text: immersed

text: crosscap

text: number

text: and

text: show

text: that

text: a

text: knot

text: has

text: im-

text: mersed

text: crosscap

text: number

text: if

text: and

text: only

text: if

text: it

text: is

text: a

text: nonntrivial

text: or

text: knot.

text: Introduction

text: One

text: method

text: to

text: deﬁne

text: a

text: measure

text: of

text: the

text: complexity

text: of

text: a

text: knot

text: K

text: is

text: by

text: de-

text: scribing

text: the

text: minimal

text: topological

text: complexity

text: of

text: a

text: compact

text: surface

text: F

text: whose

text: boundary

text: is

text: equal

text: to

text: K.

text: When

text: F

text: is

text: required

text: to

text: be

text: orientable

text: and

text: embedded

text: in

text: this

text: gives

text: the

text: classical

text: Seifert

text: genus

text: g

text: (K)

text: of

text: K;

text: when

text: the

text: requirement

text: that

text: F

text: be

text: embedded

text: in

text: is

text: weakened,

text: and

text: we

text: allow

text: embedded

text: surfaces

text: in

text: we

text: obtain

text: the

text: slice

text: genus

text: g

text: (K)

text: of

text: K.

text: Here

text: we

text: are

text: thinking

text: of

text: as

text: the

text: boundary

text: of

text: Loosening

text: the

text: requirement

text: that

text: F

text: be

text: embedded

text: in

text: in

text: another

text: direction,

text: we

text: can

text: instead

text: consider

text: surfaces

text: F

text: which

text: are

text: merely

text: immersed

text: in

text: While

text: it

text: is

text: easy

text: to

text: verify

text: that

text: every

text: knot

text: K

text: is

text: the

text: boundary

text: of

text: an

text: immersed

text: disk

text: in

text: if

text: we

text: consider

text: only

text: immersed

text: surfaces

text: which

text: are

text: embedded

text: along

text: a

text: neighborhood

text: of

text: their

text: boundaries

text: we

text: obtain

text: immersed

text: Seifert

text: surfaces

text: for

text: K.

text: The

text: minimal

text: genus

text: of

text: any

text: immersed

text: Seifert

text: surface

text: for

text: K

text: is

text: called

text: the

text: immersed

text: Seifert

text: genus

text: of

text: K,

text: and

text: is

text: denoted

text: g

text: (K).

text: While

text: g

text: indeed

text: takes

text: nontrivial

text: values

text: on

text: knots

text: in

text: using

text: I

text: I

text: foliations

text: Gabai

text: proved

text: that

text: the

text: resulting

text: knot

text: invariant

text: is

text: always

text: equal

text: to

text: the

text: Seifert

text: genus.

text: Both

text: invariants

text: are

text: in

text: turn

text: bounded

text: below

text: by

text: the

text: slice

text: genus.

text: Dropping

text: the

text: requirement

text: that

text: F

text: be

text: orientable,

text: we

text: can

text: instead

text: consider

text: nonori-

text: entable

text: immersed

text: spanning

text: surfaces,

text: deﬁned

text: in

text: a

text: similar

text: way

text: as

text: above.

text: This

text: gives

text: rise

text: to

text: a

text: nonorientable

text: analogue

text: of

text: the

text: immersed

text: Seifert

text: genus,

text: called

text: the

text: immersed

text: crosscap

text: number

text: γ

text: (K)

text: of

text: the

text: knot

text: K.

text: Our

text: main

text: result

text: involves

text: knots

text: with

text: im-

text: I

text: mersed

text: crosscap

text: number

text: i.e.

text: knots

text: which

text: bound

text: immersed

text: M¨obius

text: bands

text: that

text: are

text: embedded

text: along

text: their

text: boundaries.

text: Theorem

text: A

text: knot

text: K

text: has

text: γ

text: (K)

text: if

text: and

text: only

text: if

text: K

text: is

text: a

text: nontrivial

text: I

text: q)-torus

text: or

text: q)-cable

text: knot.

text: For

text: p

text: we

text: say

text: that

text: K

text: is

text: a

text: (p,

text: q)-cable

text: knot

text: if

text: it

text: can

text: be

text: isotoped

text: to

text: lie

text: on

text: the

text: bounda·ry

text: of

text: a·

text: solid

text: torus

text: V∼

text: Z

text: core

text: is

text: knotted,

text: where

text: it

text: represents

text: the

text: class

text: q

text: m

text: p

text: l

text: in

text: π

text: (∂V

text: Here

text: m

text: and

text: l

text: are

text: the

text: homotopy

text: classes

text: of

text: the

text: meridian

text: and

text: the

text: Seifert-framed

text: longitude

text: of

text: ∂V

text: respectively.

text: In

text: a

text: similar

text: way,

text: we

text: can

text: also

text: deﬁne

text: the

text: (embedded)

text: crosscap

text: num-

text: ber

text: γ

text: (K)

text: and

text: (embedded)

text: crosscap

text: number

text: γ

text: (K)

text: of

text: a

text: knot,

text: which


text: IMMERSED MO¨BIUS BANDS IN KNOT COMPLEMENTS 7 annulus from the proof of Lemma 6, and let V be one of the solid tori bounded by T. Recall that π (E(K)) can be presented as 1 (cid:104) | (cid:105) π (E(K)) = x, y xp = yq , 1 \ where x and y are the homotopy classes of the cores of the two solid tori in S3 T. Suppose, without loss of generality, that x is the homotopy class of the core of V . ∩ Note that T E(K) is the cabling annulus obtained in the proof of Lemma 6. ∩ Furthermore, we can homotope h(∂M) so that it sits on ∂E(K) int V . Pushing h(∂M) oﬀ of ∂E(K) towards the core of V , we see that it is homotopic to xp. Pushing ∂M inside M towards its core c and tracking its image under h, we see that h(∂M) is also freely homotopic to h(c)2, and hence h(c)2 is conjugate to xp in π (E(K)). Note, however, that the only relation the in the above group 1 presentation does not change the parity of the algebraic length of any of the words in π (E(K)). Hence any representation of h(c)2 as a word in the generators x and 1 y will always have even length, and any word representing a conjugate of xp will (cid:3) have odd length, a contradiction. Thus either p or q must be even. We now state and prove Proposition 9, which will serve to complete the proof of Theorem 1. Proposition 9. If K has γ (K) = 1 and is a (p, q)-cable knot, then p must be I even. We will break the proof of Proposition 9 into several lemmas. In what follows, suppose that K is a knot with γ (K) = 1, which is a (p, q)-cable knot. Furthermore, I suppose that K lies on the boundary T of a solid torus V , this time knotted in S3, ∩ where T E(K) is the cabling annulus A obtained from the proof of Lemma 6. Let \ W be the closure of S3 V . Again, h(∂M) is parallel to the components of ∂A in ∂E(K), but this time we homotope h(∂M) so that it is embedded and lies on the ∩ outside of V , in ∂E(K) W. ∩ Lemma 10. Suppose that h(M) can be homotoped so that it lies entirely in E(K) W. Then p must be even. ∩ \ Proof. Note that E(K) W is homeomorphic to E(V ) = S3 V , which can be viewed as the exterior of the knotted core of V . Then h(∂M) represents the class · · q m + p l in π (∂E(V )), where as usual m and l are the homotopy classes in 1 π (∂E(V )) of the meridian and Seifert-framed longitude respectively. Note that 1 | | ≥ since K is a cable (and hence a satellite knot) we must have p 2. If p is even, then we are done. Assume therefore, that p is odd. → By Theorem 4 the map h : M E(V ) is essential, and hence we can ﬁnd an → essential embedding f : Σ E(V ), where Σ is either an annulus or M¨obius band, and where f(∂Σ) is parallel to h(∂M) in both cases. Furthermore, f(∂Σ) will · · · · represent either (q m+p l) or (2q m+2p l) in π (∂E(V )), depending on whether 1 Σ is a M¨obius band or annulus respectively. Suppose ﬁrst that Σ = M. Then the boundary of a tubular neighborhood of (cid:48) ⊂ N(f(M)) will be an embedded, essential annulus A E(V ), whose boundary · · (cid:48) represents (2q m + 2p l) in π (∂E(V )). Then A must be a cabling annulus for 1

text: IMMERSED

text: MO¨BIUS

text: BANDS

text: IN

text: KNOT

text: COMPLEMENTS

text: annulus

text: from

text: the

text: proof

text: of

text: Lemma

text: and

text: let

text: V

text: be

text: one

text: of

text: the

text: solid

text: tori

text: bounded

text: by

text: T.

text: Recall

text: that

text: π

text: (E(K))

text: can

text: be

text: presented

text: as

text: π

text: (E(K))

text: x,

text: y

text: xp

text: yq

text: where

text: x

text: and

text: y

text: are

text: the

text: homotopy

text: classes

text: of

text: the

text: cores

text: of

text: the

text: two

text: solid

text: tori

text: in

text: T.

text: Suppose,

text: without

text: loss

text: of

text: generality,

text: that

text: x

text: is

text: the

text: homotopy

text: class

text: of

text: the

text: core

text: of

text: V

text: Note

text: that

text: T

text: E(K)

text: is

text: the

text: cabling

text: annulus

text: obtained

text: in

text: the

text: proof

text: of

text: Lemma

text: Furthermore,

text: we

text: can

text: homotope

text: h(∂M)

text: so

text: that

text: it

text: sits

text: on

text: ∂E(K)

text: int

text: V

text: Pushing

text: h(∂M)

text: oﬀ

text: of

text: ∂E(K)

text: towards

text: the

text: core

text: of

text: V

text: we

text: see

text: that

text: it

text: is

text: homotopic

text: to

text: xp.

text: Pushing

text: ∂M

text: inside

text: M

text: towards

text: its

text: core

text: c

text: and

text: tracking

text: its

text: image

text: under

text: h,

text: we

text: see

text: that

text: h(∂M)

text: is

text: also

text: freely

text: homotopic

text: to

text: and

text: hence

text: is

text: conjugate

text: to

text: xp

text: in

text: π

text: (E(K)).

text: Note,

text: however,

text: that

text: the

text: only

text: relation

text: the

text: in

text: the

text: above

text: group

text: presentation

text: does

text: not

text: change

text: the

text: parity

text: of

text: the

text: algebraic

text: length

text: of

text: any

text: of

text: the

text: words

text: in

text: π

text: (E(K)).

text: Hence

text: any

text: representation

text: of

text: as

text: a

text: word

text: in

text: the

text: generators

text: x

text: and

text: y

text: will

text: always

text: have

text: even

text: length,

text: and

text: any

text: word

text: representing

text: a

text: conjugate

text: of

text: xp

text: will

text: have

text: odd

text: length,

text: a

text: contradiction.

text: Thus

text: either

text: p

text: or

text: q

text: must

text: be

text: even.

text: We

text: now

text: state

text: and

text: prove

text: Proposition

text: which

text: will

text: serve

text: to

text: complete

text: the

text: proof

text: of

text: Theorem

text: Proposition

text: If

text: K

text: has

text: γ

text: (K)

text: and

text: is

text: a

text: (p,

text: q)-cable

text: knot,

text: then

text: p

text: must

text: be

text: I

text: even.

text: We

text: will

text: break

text: the

text: proof

text: of

text: Proposition

text: into

text: several

text: lemmas.

text: In

text: what

text: follows,

text: suppose

text: that

text: K

text: is

text: a

text: knot

text: with

text: γ

text: (K)

text: which

text: is

text: a

text: (p,

text: q)-cable

text: knot.

text: Furthermore,

text: I

text: suppose

text: that

text: K

text: lies

text: on

text: the

text: boundary

text: T

text: of

text: a

text: solid

text: torus

text: V

text: this

text: time

text: knotted

text: in

text: where

text: T

text: E(K)

text: is

text: the

text: cabling

text: annulus

text: A

text: obtained

text: from

text: the

text: proof

text: of

text: Lemma

text: Let

text: W

text: be

text: the

text: closure

text: of

text: V

text: Again,

text: h(∂M)

text: is

text: parallel

text: to

text: the

text: components

text: of

text: ∂A

text: in

text: ∂E(K),

text: but

text: this

text: time

text: we

text: homotope

text: h(∂M)

text: so

text: that

text: it

text: is

text: embedded

text: and

text: lies

text: on

text: the

text: outside

text: of

text: V

text: in

text: ∂E(K)

text: W.

text: Lemma

text: Suppose

text: that

text: h(M)

text: can

text: be

text: homotoped

text: so

text: that

text: it

text: lies

text: entirely

text: in

text: E(K)

text: W.

text: Then

text: p

text: must

text: be

text: even.

text: Proof.

text: Note

text: that

text: E(K)

text: W

text: is

text: homeomorphic

text: to

text: E(V

text: V

text: which

text: can

text: be

text: viewed

text: as

text: the

text: exterior

text: of

text: the

text: knotted

text: core

text: of

text: V

text: Then

text: h(∂M)

text: represents

text: the

text: class

text: q

text: m

text: p

text: l

text: in

text: π

text: (∂E(V

text: where

text: as

text: usual

text: m

text: and

text: l

text: are

text: the

text: homotopy

text: classes

text: in

text: π

text: (∂E(V

text: of

text: the

text: meridian

text: and

text: Seifert-framed

text: longitude

text: respectively.

text: Note

text: that

text: since

text: K

text: is

text: a

text: cable

text: (and

text: hence

text: a

text: satellite

text: knot)

text: we

text: must

text: have

text: p

text: If

text: p

text: is

text: even,

text: then

text: we

text: are

text: done.

text: Assume

text: therefore,

text: that

text: p

text: is

text: odd.

text: By

text: Theorem

text: the

text: map

text: h

text: M

text: E(V

text: is

text: essential,

text: and

text: hence

text: we

text: can

text: ﬁnd

text: an

text: essential

text: embedding

text: f

text: Σ

text: E(V

text: where

text: Σ

text: is

text: either

text: an

text: annulus

text: or

text: M¨obius

text: band,

text: and

text: where

text: f(∂Σ)

text: is

text: parallel

text: to

text: h(∂M)

text: in

text: both

text: cases.

text: Furthermore,

text: f(∂Σ)

text: will

text: represent

text: either

text: (q

text: m+p

text: l)

text: or

text: l)

text: in

text: π

text: (∂E(V

text: depending

text: on

text: whether

text: Σ

text: is

text: a

text: M¨obius

text: band

text: or

text: annulus

text: respectively.

text: Suppose

text: ﬁrst

text: that

text: Σ

text: M.

text: Then

text: the

text: boundary

text: of

text: a

text: tubular

text: neighborhood

text: of

text: N(f(M))

text: will

text: be

text: an

text: embedded,

text: essential

text: annulus

text: A

text: E(V

text: whose

text: boundary

text: represents

text: m

text: l)

text: in

text: π

text: (∂E(V

text: Then

text: A

text: must

text: be

text: a

text: cabling

text: annulus

text: for


text: 10 MARK C. HUGHES AND SEUNGWON KIM (cid:54) pq = 0. Hence we see that [h(∂M)] = [κ] is nonzero in H (E(K)). Thus b = 1, 1 (cid:3) which completes the proof. Proof of Proposition 9. Let M denote the subsurface of M bounded by µ , which 0 → 0 will also be a M¨obius band. Let h : M E(K) denote the restriction of h to 0 0 M . Note that h (∂M ) will be an immersed curve in the cabling annulus A which 0 0 0 − is homotopic to the core κ. Furthermore, as µ was the innermost curve in h 1(A), 0 ∩ ∩ h (M ) will be contained entirely inside either E(K) V or E(K) W. 0 0 Choose a homotopy of h which is supported in a small neighborhood of ∂M , 0 0 and which ﬁrst straightens out h (∂M ) to the embedded core κ, and then pushes 0 0 it along A towards one of its boundary components, and ﬁnally onto ∂E(K). If ⊂ ∩ ∩ ⊂ h (M ) E(K) V , then we push h (∂M ) onto ∂E(K) int V , while if h (M ) 0 0∩ 0 0 ∩ 0 0 E(K) W then we push h (∂M ) onto ∂E(K) int W. 0 0 → In the latter case, we obtain a proper map h : M E(K) whose image is ∩ 0 0 contained entirely outside of E(K) V . Moreover, h is essential by Theorem 4, 0 and hence by Lemma 10 it foll⊂ows that∩p must be even. ∩ ∼ Suppose then that h (M ) E(K) V . Take the solid torus E(K) V = V , 0 0 and perform an inverse satellite operation, embedding it in S3 as the standardly (cid:48) embedded solid torus V . In doing so we chose this embedding so that the longitude coming from the Seifert framing on V is identiﬁed with the longitude from the Seifert (cid:48) framing on V , though this will not be necessary. Using this choice of identiﬁcation (cid:48) → (cid:48) (cid:48) (cid:48) we obtain a map h : M V , with h (∂M ) embedded on ∂V as a (p, q)-torus (cid:48) 0 (cid:48) 0 (cid:48) (cid:48) knot K . Thinking instead of h as a map to E(K ), it follows immediately that h is essential. (cid:48) Now, suppose that p is odd. If we cut the torus V and apply k twists before (cid:48) (cid:48) regluing, we obtain the solid torus V again, while the knot K is transformed into (cid:48)(cid:48) (cid:48) a (p, q + kp)-torus knot K lying on ∂V . As p is odd, we can choose k so that (cid:48) (cid:48) q + kp is also odd. However, since the the image of h is contained entirely in V , (cid:48) (cid:48)(cid:48) → (cid:48)(cid:48) we can twist the map h as well to obtain a new essential map h : M E(K ), (cid:48)(cid:48) (cid:48)(cid:48) 0 with h (∂M ) a longitude on ∂E(K ). By Lemma 8 then either p or q + kp must 0 (cid:3) be even, which is a contradiction. Hence p must be even. References [1] Joshua Batson. Nonorientable four-ball genus can be arbitrarily large. arXiv preprint arXiv:1204.1985, 2012. [2] James W Cannon and Charles D Feustel. Essential embeddings of annuli and M¨obius bands in 3-manifolds. Transactions of the American Mathematical Society, 215:219–239, 1976. [3] J Scott Carter and Masahico Saito. Surfaces in 3-space that do not lift to embeddings in 4-space. Banach Center Publications, 42:29–47, 1998. [4] Bradd Evans Clark. Crosscaps and knotes. International Journal of Mathematics and Math- ematical Sciences, 1(1):113–123, 1978. [5] David Gabai. Foliations and the topology of 3-manifolds. J. Diﬀerential Geom., 18(3):445–503, 1983. [6] Makoto Ozawa. Knots and surfaces. arXiv preprint arXiv:1603.09039, 2016. [7] Jonathan Simon. An algebraic classiﬁcation of knots in S3. Annals of Mathematics, pages 1–13, 1973.

text: MARK

text: C.

text: HUGHES

text: AND

text: SEUNGWON

text: KIM

font: default

text: pq

text: Hence

text: we

text: see

text: that

text: [h(∂M)]

text: [κ]

text: is

text: nonzero

text: in

text: H

text: (E(K)).

text: Thus

text: b

text: which

text: completes

text: the

text: proof.

text: Proof

text: of

text: Proposition

text: Let

text: M

text: denote

text: the

text: subsurface

text: of

text: M

text: bounded

text: by

text: µ

text: which

text: will

text: also

text: be

text: a

text: M¨obius

text: band.

text: Let

text: h

text: M

text: E(K)

text: denote

text: the

text: restriction

text: of

text: h

text: to

text: M

text: Note

text: that

text: h

text: (∂M

text: will

text: be

text: an

text: immersed

text: curve

text: in

text: the

text: cabling

text: annulus

text: A

text: which

text: is

text: homotopic

text: to

text: the

text: core

text: κ.

text: Furthermore,

text: as

text: µ

text: was

text: the

text: innermost

text: curve

text: in

text: h

text: h

text: (M

text: will

text: be

text: contained

text: entirely

text: inside

text: either

text: E(K)

text: V

text: or

text: E(K)

text: W.

text: Choose

text: a

text: homotopy

text: of

text: h

text: which

text: is

text: supported

text: in

text: a

text: small

text: neighborhood

text: of

text: ∂M

text: and

text: which

text: ﬁrst

text: straightens

text: out

text: h

text: (∂M

text: to

text: the

text: embedded

text: core

text: κ,

text: and

text: then

text: pushes

text: it

text: along

text: A

text: towards

text: one

text: of

text: its

text: boundary

text: components,

text: and

text: ﬁnally

text: onto

text: ∂E(K).

text: If

text: h

text: (M

text: E(K)

text: V

text: then

text: we

text: push

text: h

text: (∂M

text: onto

text: ∂E(K)

text: int

text: V

text: while

text: if

text: h

text: (M

text: 0∩

text: E(K)

text: W

text: then

text: we

text: push

text: h

text: (∂M

text: onto

text: ∂E(K)

text: int

text: W.

text: In

text: the

text: latter

text: case,

text: we

text: obtain

text: a

text: proper

text: map

text: h

text: M

text: E(K)

text: whose

text: image

text: is

text: contained

text: entirely

text: outside

text: of

text: E(K)

text: V

text: Moreover,

text: h

text: is

text: essential

text: by

text: Theorem

text: and

text: hence

text: by

text: Lemma

text: it

text: foll⊂ows

text: that∩p

text: must

text: be

text: even.

text: Suppose

text: then

text: that

text: h

text: (M

text: E(K)

text: V

text: Take

text: the

text: solid

text: torus

text: E(K)

text: V

text: V

text: and

text: perform

text: an

text: inverse

text: satellite

text: operation,

text: embedding

text: it

text: in

text: as

text: the

text: standardly

text: embedded

text: solid

text: torus

text: V

text: In

text: doing

text: so

text: we

text: chose

text: this

text: embedding

text: so

text: that

text: the

text: longitude

text: coming

text: from

text: the

text: Seifert

text: framing

text: on

text: V

text: is

text: identiﬁed

text: with

text: the

text: longitude

text: from

text: the

text: Seifert

text: framing

text: on

text: V

text: though

text: this

text: will

text: not

text: be

text: necessary.

text: Using

text: this

text: choice

text: of

text: identiﬁcation

text: we

text: obtain

text: a

text: map

text: h

text: M

text: V

text: with

text: h

text: (∂M

text: embedded

text: on

text: ∂V

text: as

text: a

text: (p,

text: q)-torus

text: knot

text: K

text: Thinking

text: instead

text: of

text: h

text: as

text: a

text: map

text: to

text: E(K

text: it

text: follows

text: immediately

text: that

text: h

text: is

text: essential.

text: Now,

text: suppose

text: that

text: p

text: is

text: odd.

text: If

text: we

text: cut

text: the

text: torus

text: V

text: and

text: apply

text: k

text: twists

text: before

text: regluing,

text: we

text: obtain

text: the

text: solid

text: torus

text: V

text: again,

text: while

text: the

text: knot

text: K

text: is

text: transformed

text: into

text: a

text: (p,

text: q

text: kp)-torus

text: knot

text: K

text: lying

text: on

text: ∂V

text: As

text: p

text: is

text: odd,

text: we

text: can

text: choose

text: k

text: so

text: that

text: q

text: kp

text: is

text: also

text: odd.

text: However,

text: since

text: the

text: the

text: image

text: of

text: h

text: is

text: contained

text: entirely

text: in

text: V

text: we

text: can

text: twist

text: the

text: map

text: h

text: as

text: well

text: to

text: obtain

text: a

text: new

text: essential

text: map

text: h

text: M

text: E(K

text: with

text: h

text: (∂M

text: a

text: longitude

text: on

text: ∂E(K

text: By

text: Lemma

text: then

text: either

text: p

text: or

text: q

text: kp

text: must

text: be

text: even,

text: which

text: is

text: a

text: contradiction.

text: Hence

text: p

text: must

text: be

text: even.

text: References

text: Joshua

text: Batson.

text: Nonorientable

text: four-ball

text: genus

text: can

text: be

text: arbitrarily

text: large.

text: arXiv

text: preprint

text: James

text: W

text: Cannon

text: and

text: Charles

text: D

text: Feustel.

text: Essential

text: embeddings

text: of

text: annuli

text: and

text: M¨obius

text: bands

text: in

text: Transactions

text: of

text: the

text: American

text: Mathematical

text: Society,

text: J

text: Scott

text: Carter

text: and

text: Masahico

text: Saito.

text: Surfaces

text: in

text: that

text: do

text: not

text: lift

text: to

text: embeddings

text: in

text: Banach

text: Center

text: Publications,

text: Bradd

text: Evans

text: Clark.

text: Crosscaps

text: and

text: knotes.

text: International

text: Journal

text: of

text: Mathematics

text: and

text: Math-

text: ematical

text: Sciences,

text: David

text: Gabai.

text: Foliations

text: and

text: the

text: topology

text: of

text: J.

text: Diﬀerential

text: Geom.,

text: Makoto

text: Ozawa.

text: Knots

text: and

text: surfaces.

text: arXiv

text: preprint

text: Jonathan

text: Simon.

text: An

text: algebraic

text: classiﬁcation

text: of

text: knots

text: in

text: Annals

text: of

text: Mathematics,

text: pages


text: MODIFIED TRACE IS A SYMMETRISED INTEGRAL 11 Proposition 2.4. A symmetric linear form t on a ﬁnite-dimensional algebra A extends (cid:88) (cid:0){ (cid:1)→ k} uniquely to a family of trace maps t : End (P ) ∈ where P A P A-pmod k ◦ ◦ ∈ (2.12) t (f) = t (b f a )(1) , f End (P ) , P i i A i=1 for a given decomposition of id as in (2.6). In particular, we have P ∈ (2.13) t (r ) = t(x) , x A . A x Proof. We ﬁrst note that there is a bijection between linear forms on HH (A-pmod) and { → k} 0 families of trace maps t : End (P ) ∈ such that t (f) = l([P, f]) for a linear P A → k P A-pmod P form l. A symmetric linear form t: A provide(cid:0)s a(cid:1)linear form on HH (A) which we also 0 denote by t. By Proposition 2.3, this deﬁnes a linear form on HH (A-pmod) by the formula 0 ◦ (2.14) t (f) = t Ψ [f] P ∈ for any f End (P ) and Ψ given in (2.11). Since Ψ is an isomorphism and it does not A depend on the choice of the decomposition of id , we have the existence and uniqueness of P (cid:3) the extension. Finally, the equality (2.13) is straightforward after using (2.10). We remark that a result similar to Proposition 2.4 was also proven in [GR, proof of Prop. 5.8 (1)] (however in the case of non-degenerate traces). ⊕ Example. We assume here that P = A m and demonstrate the use of the formula (2.12). ⊕ The algebra of A-invariant endomorphisms of A m can be rewritten as a matrix algebra: ∼ ⊕ (2.15) EndA(A m) = Matm,m(Aop) (cid:80) × where Mat is the m m matrix algebra and we used Lemma 2.1. With notation as in (2.9), m,m ⊗ (cid:55)→ ⊗ the isomorphism (2.15) sends a matrix (h ) to the endomorphism x e m xh e . ij j r=1 rj r Let us choose a and b as in (2.9). From (2.12), we then obtain the unique extension t ⊕ of i i (cid:88) A m the symmetric form t ⊕ m ∈ ⊕ (2.16) t m(h) := t ⊕ (h) = t(h ) , h End (A m) , A m ii A i=1 where we used cyclicity of t and on RHS we identiﬁed h with the corresponding element in Mat (Aop) under the isomorphism in (2.15). m,m Remark 2.5. For an indecomposable projective A-module P , we can reformulate Proposi- → (cid:16) tion 2.4 in the following way. Let us ﬁx an injection j : P (cid:44) A and projection p: A P such ◦ ◦ ∈ that p j = id – this identity provides a decomposition as in (2.6). Then j p End (A) P A is right multiplication by a primitive idempotent π, and so t (id ) = t(π). P P

text: MODIFIED

text: TRACE

text: IS

text: A

text: SYMMETRISED

text: INTEGRAL

text: Proposition

text: A

text: symmetric

text: linear

text: form

text: t

text: on

text: a

text: ﬁnite-dimensional

text: algebra

text: A

text: extends

text: k}

text: uniquely

text: to

text: a

text: family

text: of

text: trace

text: maps

text: t

text: End

text: (P

text: where

text: P

text: A

text: P

text: A-pmod

text: k

text: t

text: (f)

text: t

text: (b

text: f

text: a

text: f

text: End

text: (P

text: P

text: i

text: i

text: A

text: for

text: a

text: given

text: decomposition

text: of

text: id

text: as

text: in

text: In

text: particular,

text: we

text: have

text: P

text: t

text: (r

text: t(x)

text: x

text: A

text: A

text: x

text: Proof.

text: We

text: ﬁrst

text: note

text: that

text: there

text: is

text: a

text: bijection

text: between

text: linear

text: forms

text: on

text: HH

text: (A-pmod)

text: and

text: k}

text: families

text: of

text: trace

text: maps

text: t

text: End

text: (P

text: such

text: that

text: t

text: (f)

text: l([P,

text: f])

text: for

text: a

text: linear

text: P

text: A

text: k

text: P

text: A-pmod

text: P

text: form

text: l.

text: A

text: symmetric

text: linear

text: form

text: t:

text: A

text: form

text: on

text: HH

text: (A)

text: which

text: we

text: also

text: denote

text: by

text: t.

text: By

text: Proposition

text: this

text: deﬁnes

text: a

text: linear

text: form

text: on

text: HH

text: (A-pmod)

text: by

text: the

text: formula

text: t

text: (f)

text: t

text: Ψ

text: [f]

text: P

text: for

text: any

text: f

text: End

text: (P

text: and

text: Ψ

text: given

text: in

text: Since

text: Ψ

text: is

text: an

text: isomorphism

text: and

text: it

text: does

text: not

text: A

text: depend

text: on

text: the

text: choice

text: of

text: the

text: decomposition

text: of

text: id

text: we

text: have

text: the

text: existence

text: and

text: uniqueness

text: of

text: P

text: the

text: extension.

text: Finally,

text: the

text: equality

text: is

text: straightforward

text: after

text: using

text: We

text: remark

text: that

text: a

text: result

text: similar

text: to

text: Proposition

text: was

text: also

text: proven

text: in

text: [GR,

text: proof

text: of

text: Prop.

text: (however

text: in

text: the

text: case

text: of

text: non-degenerate

text: traces).

text: Example.

text: We

text: assume

text: here

text: that

text: P

text: A

text: m

text: and

text: demonstrate

text: the

text: use

text: of

text: the

text: formula

text: The

text: algebra

text: of

text: A-invariant

text: endomorphisms

text: of

text: A

text: m

text: can

text: be

text: rewritten

text: as

text: a

text: matrix

text: algebra:

text: EndA(A

text: m)

text: Matm,m(Aop)

text: where

text: Mat

text: is

text: the

text: m

text: m

text: matrix

text: algebra

text: and

text: we

text: used

text: Lemma

text: With

text: notation

text: as

text: in

text: m,m

text: the

text: isomorphism

text: sends

text: a

text: matrix

text: (h

text: to

text: the

text: endomorphism

text: x

text: e

text: m

text: xh

text: e

text: ij

text: j

text: rj

text: r

text: Let

text: us

text: choose

text: a

text: and

text: b

text: as

text: in

text: From

text: we

text: then

text: obtain

text: the

text: unique

text: extension

text: t

text: of

text: i

text: i

text: A

text: m

text: the

text: symmetric

text: form

text: t

text: m

text: t

text: m(h)

text: t

text: (h)

text: t(h

text: h

text: End

text: (A

text: m)

text: A

text: m

text: ii

text: A

text: where

text: we

text: used

text: cyclicity

text: of

text: t

text: and

text: on

text: RHS

text: we

text: identiﬁed

text: h

text: with

text: the

text: corresponding

text: element

text: in

text: Mat

text: (Aop)

text: under

text: the

text: isomorphism

text: in

text: m,m

text: Remark

text: For

text: an

text: indecomposable

text: projective

text: A-module

text: P

text: we

text: can

text: reformulate

text: Proposi-

text: tion

text: in

text: the

text: following

text: way.

text: Let

text: us

text: ﬁx

text: an

text: injection

text: j

text: P

text: A

text: and

text: projection

text: p:

text: A

text: P

text: such

text: that

text: p

text: j

text: id

text: this

text: identity

text: provides

text: a

text: decomposition

text: as

text: in

text: Then

text: j

text: p

text: End

text: (A)

text: P

text: A

text: is

text: right

text: multiplication

text: by

text: a

text: primitive

text: idempotent

text: π,

text: and

text: so

text: t

text: (id

text: t(π).

text: P

text: P