text: ALMOST FLAT MANIFOLDS 5 Lemma 2.2. (i)(cid:102)Let M be a close(cid:102)d manifold with an epimorphism of its fundamental group to a ﬁnite group G. Then M bounds if \ and only if H M bounds where M is the G-cover of M and H is a 2-Sylow subgroup of G. \ (cid:111) (ii) Any infranilmanifold M = Γ L G/G with G a 2-group has a (cid:102) central involution. \ → Proof. (i) Note that H M M is a odd-degree cover, hence the domain and target have the same Stiefel-Whitney numbers; thus one bounds if and only if the other does. \ (ii) Let Σ be the subgroup of Z(N) Z(L) generated by the elements of order 2. Since the 2-group G acts as group automorphisms of the abelian 2-group Σ, there must be at least two orbits of cardinality one, hence there must be a non-trivial element ﬁxed by G. q.e.d. To analyze the ﬁxed point set of a central involution, we need a group theoretic remark. Remark 2.3. Let X be an (H, K)-bi(cid:101)set where both H and(cid:101) K act → \ freely on X. Let q : X H X be the quotient map, let F be the \ − ∈ ﬁxed set of K acting on H X, and let F = q 1F . For x F , there → is a function ϕ : K H so that xk = ϕ (k)x. Since H acts freely, x x this function is uniquely deﬁned, since X is a biset, this function is a homomorphism, and since K acts freely, it is a monomorphism. For a (cid:101) → monomorphism ϕ : K H, let (cid:96) (cid:101) (cid:101) { ∈ | ∀ ∈ (cid:101) (cid:101) } F = x X k K, xk = ϕ(k)x . ϕ (cid:101) (cid:101) → Then F = F . It is easy to see that hF = F ◦ where c : H H ϕ (cid:96) ϕ ch ϕ h is conjuga(cid:101)tion. Thus q(F ) = q(F ◦ ). The group H acts on the set of → ϕ ch ϕ monomorphisms K H by conjugation, let [ϕ] denote an orbit. Let F = q(F ). Then F = F . [ϕ] ϕ [ϕ] × Note that there is a bijection between (H, K)-bisets and left (H K)- − sets, where hxk corresponds to hk 1x. Later we will apply Remark 2.3 to analyze the ﬁxed point set of a → \ central involution τ : M M by setting X = N L, H = G and (cid:104) (cid:105) K = τ . (cid:101) (cid:101) → A v∼ector bundle E B is ﬂat if it has ﬁnite structure group, that × → is, E = B V for some ﬁnite, regular G-cover B B and some G R G-module V . We call such a ﬂat structure a (G, V )-st(cid:101)ructure. Such a × bundle (over a CW-complex) is the pullback of the ﬂat bundle EG → → → G V BG along a map B BG. The regular G-cover B B can also → be speciﬁed by a homotopy class of map B BG or by a G-conjugacy → class of homomorphism π B G. 1 Tangent bundles of infranilmanifolds are ﬂat:

text: ALMOST

text: FLAT

text: MANIFOLDS

text: Lemma

text: M

text: be

text: a

text: manifold

text: with

text: an

text: epimorphism

text: of

text: its

text: fundamental

text: group

text: to

text: a

text: ﬁnite

text: group

text: G.

text: Then

text: M

text: bounds

text: if

text: and

text: only

text: if

text: H

text: M

text: bounds

text: where

text: M

text: is

text: the

text: G-cover

text: of

text: M

text: and

text: H

text: is

text: a

text: subgroup

text: of

text: G.

text: (ii)

text: Any

text: infranilmanifold

text: M

text: Γ

text: L

text: G/G

text: with

text: G

text: a

text: has

text: a

text: central

text: involution.

text: Proof.

text: (i)

text: Note

text: that

text: H

text: M

text: M

text: is

text: a

text: odd-degree

text: cover,

text: hence

text: the

text: domain

text: and

text: target

text: have

text: the

text: same

text: Stiefel-Whitney

text: numbers;

text: thus

text: one

text: bounds

text: if

text: and

text: only

text: if

text: the

text: other

text: does.

text: (ii)

text: Let

text: Σ

text: be

text: the

text: subgroup

text: of

text: Z(N)

text: Z(L)

text: generated

text: by

text: the

text: elements

text: of

text: order

text: Since

text: the

text: G

text: acts

text: as

text: group

text: automorphisms

text: of

text: the

text: abelian

text: Σ,

text: there

text: must

text: be

text: at

text: least

text: two

text: orbits

text: of

text: cardinality

text: one,

text: hence

text: there

text: must

text: be

text: a

text: non-trivial

text: element

text: ﬁxed

text: by

text: G.

text: q.e.d.

text: To

text: analyze

text: the

text: ﬁxed

text: point

text: set

text: of

text: a

text: central

text: involution,

text: we

text: need

text: a

text: group

text: theoretic

text: remark.

text: Remark

text: Let

text: X

text: be

text: an

text: (H,

text: where

text: both

text: H

text: K

text: act

text: freely

text: on

text: X.

text: Let

text: q

text: X

text: H

text: X

text: be

text: the

text: quotient

text: map,

text: let

text: F

text: be

text: the

text: ﬁxed

text: set

text: of

text: K

text: acting

text: on

text: H

text: X,

text: and

text: let

text: F

text: q

text: For

text: x

text: F

text: there

text: is

text: a

text: function

text: ϕ

text: K

text: H

text: so

text: that

text: xk

text: ϕ

text: (k)x.

text: Since

text: H

text: acts

text: freely,

text: x

text: x

text: this

text: function

text: is

text: uniquely

text: deﬁned,

text: since

text: X

text: is

text: a

text: biset,

text: this

text: function

text: is

text: a

text: homomorphism,

text: and

text: since

text: K

text: acts

text: freely,

text: it

text: is

text: a

text: monomorphism.

text: For

text: a

text: monomorphism

text: ϕ

text: K

text: H,

text: let

text: F

text: x

text: X

text: k

text: K,

text: xk

text: ϕ(k)x

text: ϕ

text: Then

text: F

text: F

text: It

text: is

text: easy

text: to

text: see

text: that

text: hF

text: F

text: where

text: c

text: H

text: H

text: ϕ

text: ϕ

text: ch

text: ϕ

text: h

text: is

text: Thus

text: q(F

text: q(F

text: The

text: group

text: H

text: acts

text: on

text: the

text: set

text: of

text: ϕ

text: ch

text: ϕ

text: monomorphisms

text: K

text: H

text: by

text: conjugation,

text: let

text: [ϕ]

text: denote

text: an

text: orbit.

text: Let

text: F

text: q(F

text: Then

text: F

text: F

text: [ϕ]

text: ϕ

text: [ϕ]

text: Note

text: that

text: there

text: is

text: a

text: bijection

text: between

text: (H,

text: K)-bisets

text: and

text: left

text: (H

text: K)-

text: sets,

text: where

text: hxk

text: corresponds

text: to

text: hk

text: Later

text: we

text: will

text: apply

text: Remark

text: to

text: analyze

text: the

text: ﬁxed

text: point

text: set

text: of

text: a

text: central

text: involution

text: τ

text: M

text: M

text: by

text: setting

text: X

text: N

text: L,

text: H

text: G

text: and

text: K

text: τ

text: A

text: v∼ector

text: bundle

text: E

text: B

text: is

text: ﬂat

text: if

text: it

text: has

text: ﬁnite

text: structure

text: group,

text: that

text: is,

text: E

text: B

text: V

text: for

text: some

text: ﬁnite,

text: regular

text: G-cover

text: B

text: B

text: and

text: some

text: G

text: R

text: G-module

text: V

text: We

text: call

text: such

text: a

text: ﬂat

text: structure

text: a

text: (G,

text: V

text: Such

text: a

text: bundle

text: (over

text: a

text: CW-complex)

text: is

text: the

text: pullback

text: of

text: the

text: ﬂat

text: bundle

text: EG

text: G

text: V

text: BG

text: along

text: a

text: map

text: B

text: BG.

text: The

text: regular

text: G-cover

text: B

text: B

text: can

text: also

text: be

text: speciﬁed

text: by

text: a

text: homotopy

text: class

text: of

text: map

text: B

text: BG

text: or

text: by

text: a

text: G-conjugacy

text: class

text: of

text: homomorphism

text: π

text: B

text: G.

text: Tangent

text: bundles

text: of

text: infranilmanifolds

text: are

text: ﬂat:


text: ALMOST FLAT MANIFOLDS 7 × Figure 1. M I with M = S1 and τ(z) = z. The disks are the tubular neighborhood N. of dim M, ∗ | ⊕ w (T M)[M] = w (π T M )[P (ν 1)] J J P F ∗ | ⊕ = (π w (T M ))[P (ν 1)] P J F = 0 | | | since w (T M ) = 0 because J = dim M > dim F . Thus all Stiefel- J F Whitney numbers of M vanish, so by Thom’s theorem M bounds. q.e.d. Remark 2.6. One wonders if there could be a direct proof of Lemma 2.5 which avoids the use of Thom’s Theorem. → Note that any involution τ : M M induces the involution dτ : → T M T M, but this involution does not restrict to the identity on | T M . F Theorem 2.7. An almost ﬂat manifold bounds provided that the 2- sylow subgroup of the holonomy group is cyclic or generalized quater- nionic. \ (cid:111) Proof. Let M = Γ L G/G be an infranilmanifold with the 2-sylow subgroup of G cyclic or generalized quaternionic. By Lemma 2.2(i), we can pass to odd degree cover and assume that G is a 2-group. Then ∈ there is a unique element g G of order 2. (In fact, according to a theorem of Burnside, a 2-group has a unique element of order 2 if and only if it is cyclic or generalized quaternionic.) Since the center of a p-group is nontrivial, g is central. ∈ \ By Lemma 2.2(ii), there is a central involution τ Z(N) Z(L). Since → it is G-invariant, it induces a nontrivial involution τ : M M. By \ (cid:104) (cid:105) Remark 2.3, applied with X = N L, H = G, and K = τ , the ﬁxed set of τ is { ∈ | ∈ \ } F = [x] M x N L, τx = gx . ##LTLine## ##LTLine## ##LTLine##

text: ALMOST

label: paragraph

text: FLAT

text: MANIFOLDS

label: caption

text: Figure

text: M

text: I

text: with

text: M

text: and

text: τ(z)

text: z.

text: The

text: disks

text: are

text: the

text: tubular

text: neighborhood

text: N.

text: of

text: dim

text: M,

text: w

text: (T

text: M)[M]

text: w

text: (π

text: T

text: M

text: )[P

text: (ν

text: J

text: J

text: P

text: F

text: (π

text: w

text: (T

text: M

text: ))[P

text: (ν

text: P

text: J

text: F

text: since

text: w

text: (T

text: M

text: because

text: J

text: dim

text: M

text: dim

text: F

text: Thus

text: all

text: Stiefel-

text: J

text: F

text: Whitney

text: numbers

text: of

text: M

text: vanish,

text: so

text: by

text: Thom’s

text: theorem

text: M

text: bounds.

text: q.e.d.

text: Remark

text: One

text: wonders

text: if

text: there

text: could

text: be

text: a

text: direct

text: proof

text: of

text: Lemma

text: which

text: avoids

text: the

text: use

text: of

text: Thom’s

text: Theorem.

text: Note

text: that

text: any

text: involution

text: τ

text: M

text: M

text: induces

text: the

text: involution

text: dτ

text: T

text: M

text: T

text: M,

text: but

text: this

text: involution

text: does

text: not

text: restrict

text: to

text: the

text: identity

text: on

text: T

text: M

text: F

text: Theorem

text: An

text: almost

text: ﬂat

text: manifold

text: bounds

text: provided

text: that

text: the

text: sylow

text: subgroup

text: of

text: the

text: holonomy

text: group

text: is

text: cyclic

text: or

text: generalized

text: quater-

text: nionic.

text: Proof.

text: Let

text: M

text: Γ

text: L

text: G/G

text: be

text: an

text: infranilmanifold

text: with

text: the

text: subgroup

text: of

text: G

text: cyclic

text: or

text: generalized

text: quaternionic.

text: By

text: Lemma

text: we

text: can

text: pass

text: to

text: odd

text: degree

text: cover

text: and

text: assume

text: that

text: G

text: is

text: a

text: Then

text: there

text: is

text: a

text: unique

text: element

text: g

text: G

text: of

text: order

text: (In

text: fact,

text: according

text: to

text: a

text: theorem

text: of

text: Burnside,

text: a

text: has

text: a

text: unique

text: element

text: of

text: order

text: if

text: and

text: only

text: if

text: it

text: is

text: cyclic

text: or

text: generalized

text: quaternionic.)

text: Since

text: the

text: center

text: of

text: a

text: p-group

text: is

text: nontrivial,

text: g

text: is

text: central.

text: By

text: Lemma

text: there

text: is

text: a

text: central

text: involution

text: τ

text: Z(N)

text: Z(L).

text: Since

text: it

text: is

text: G-invariant,

text: it

text: induces

text: a

text: nontrivial

text: involution

text: τ

text: M

text: M.

text: By

text: Remark

text: applied

text: with

text: X

text: N

text: L,

text: H

text: G,

text: and

text: K

text: τ

text: the

text: ﬁxed

text: set

text: of

text: τ

text: is

text: F

text: [x]

text: M

text: x

text: N

text: L,

text: τx

text: gx

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: TOWARDS A SPLITTER THEOREM FOR INTERNALLY 4-CONNECTED BINARY MATROIDS VIII: SMALL MATROIDS CAROLYN CHUN, DILLON MAYHEW, AND JAMES OXLEY Abstract. Our splitter theorem for internally 4-connected binary ma- troids studies pairs of the form (M, N), where M and N are internally (cid:48) 4-connected binary matroids, M has a proper N-minor, and if M is (cid:48) an internally 4-connected matroid such that M has a proper M -minor (cid:48) | | − | (cid:48) | and M has an N-minor, then E(M) E(M ) > 3. The analysis in | | ≥ the splitter theorem requires the constraint that E(M) 16. In this article, we complement that analysis by using an exhaustive computer | | ≤ search to ﬁnd all such pairs for which E(M) 15. 1. Introduction A matroid is internally 4-connected if it is 3-connected and {| | | |} min X , Y = 3 for any 3-separation, (X, Y ). For some time, we have been engaged in a project to develop a splitter theorem for internally 4-con- nected binary matroids [2, 3, 4, 5, 6, 7, 8, 9]. This means that we are concerned with understanding what we refer to here as interesting pairs. If (cid:22) N and M are matroids, we write N M to mean that M has an N-minor, ≺ and N M to mean that M has a proper N-minor. An interesting pair is a pair (M, N), where M and N are internally 4-connected binary matroids such that • | | ≥ E(N) 6; • ≺ N M; • (cid:48) (cid:22) (cid:48) ≺ if M is an internally 4-connected matroid for which N M M, | | − | (cid:48) | then E(M) E(M ) > 3. | |−| | Note that the last condition means that E(M) E(N) > 3. We say that (cid:48) an interesting pair, (M, N), is a fascinating pair if M is isomorphic to N (cid:48) (cid:22) (cid:48) ≺ whenever M is an internally 4-connected matroid satisfying N M M. Thus an interesting pair is fascinating if there is no intermediate internally 4-connected matroid in the minor order. It has been known for some time (see, for example, [11]) that there are | | − | | fascinating pairs with E(M) E(N) arbitrarily large; indeed, this is true even if we insist that M and N are graphic matroids, since we can produce a fascinating pair by setting N to be the graphic matroid of a cubic planar ladder, and letting M be the graphic matroid of a quartic planar ladder on Date: May 27, 2020. 1 ##LTLine##

text: TOWARDS

text: A

text: SPLITTER

text: THEOREM

text: FOR

text: INTERNALLY

text: BINARY

text: MATROIDS

text: VIII:

text: SMALL

text: MATROIDS

text: CAROLYN

text: CHUN,

text: DILLON

text: MAYHEW,

text: AND

text: JAMES

text: OXLEY

text: Abstract.

text: Our

label: abstract

text: splitter

text: theorem

text: for

text: internally

text: binary

text: ma-

text: troids

text: studies

text: pairs

text: of

text: the

text: form

text: (M,

text: N),

text: where

text: M

text: and

text: N

text: are

text: internally

text: binary

text: matroids,

text: M

text: has

text: a

text: proper

text: N-minor,

text: and

text: if

text: M

text: is

text: an

text: internally

text: matroid

text: such

text: that

text: M

text: has

text: a

text: proper

text: M

text: -minor

text: and

text: M

text: has

text: an

text: N-minor,

text: then

text: E(M)

text: E(M

text: The

text: analysis

text: in

text: the

text: splitter

text: theorem

text: requires

text: the

text: constraint

text: that

text: E(M)

text: In

text: this

text: article,

text: we

text: complement

text: that

text: analysis

text: by

text: using

text: an

text: exhaustive

text: computer

text: search

text: to

text: ﬁnd

text: all

text: such

text: pairs

text: for

text: which

text: E(M)

text: Introduction

text: A

text: matroid

text: is

text: internally

text: if

text: it

text: is

text: and

text: min

text: X

text: Y

text: for

text: any

text: (X,

text: Y

text: For

text: some

text: time,

text: we

text: have

text: been

text: engaged

text: in

text: a

text: project

text: to

text: develop

text: a

text: splitter

text: theorem

text: for

text: internally

text: nected

text: binary

text: matroids

text: This

text: means

text: that

text: we

text: are

text: concerned

text: with

text: understanding

text: what

text: we

text: refer

text: to

text: here

text: as

text: interesting

text: pairs.

text: If

text: N

text: and

text: M

text: are

text: matroids,

text: we

text: write

text: N

text: M

text: to

text: mean

text: that

text: M

text: has

text: an

text: N-minor,

text: and

text: N

text: M

text: to

text: mean

text: that

text: M

text: has

text: a

text: proper

text: N-minor.

text: An

text: interesting

text: pair

text: is

text: a

text: pair

text: (M,

text: N),

text: where

text: M

text: and

text: N

text: are

text: internally

text: binary

text: matroids

text: such

text: that

text: E(N)

text: N

text: M;

text: if

text: M

text: is

text: an

text: internally

text: matroid

text: for

text: which

text: N

text: M

text: M,

text: then

text: E(M)

text: E(M

text: Note

text: that

text: the

text: last

text: condition

text: means

text: that

text: E(M)

text: E(N)

text: We

text: say

text: that

text: an

text: interesting

text: pair,

text: (M,

text: N),

text: is

text: a

text: fascinating

text: pair

text: if

text: M

text: is

text: isomorphic

text: to

text: N

text: whenever

text: M

text: is

text: an

text: internally

text: matroid

text: satisfying

text: N

text: M

text: M.

text: Thus

text: an

text: interesting

text: pair

text: is

text: fascinating

text: if

text: there

text: is

text: no

text: intermediate

text: internally

text: matroid

text: in

text: the

text: minor

text: order.

text: It

text: has

text: been

text: known

text: for

text: some

text: time

text: (see,

text: for

text: example,

text: that

text: there

text: are

text: fascinating

text: pairs

text: with

text: E(M)

text: E(N)

text: arbitrarily

text: large;

text: indeed,

text: this

text: is

text: true

text: even

text: if

text: we

text: insist

text: that

text: M

text: and

text: N

text: are

text: graphic

text: matroids,

text: since

text: we

text: can

text: produce

text: a

text: fascinating

text: pair

text: by

text: setting

text: N

text: to

text: be

text: the

text: graphic

text: matroid

text: of

text: a

text: cubic

text: planar

text: ladder,

text: and

text: letting

text: M

text: be

text: the

text: graphic

text: matroid

text: of

text: a

text: quartic

text: planar

text: ladder

text: on

text: Date:

text: May

text: ##LTLine##


text: A SPLITTER THEOREM FOR BINARY MATROIDS 17 4. Proof of the main results We prove Theorem 1.1. Assume that (M, N) is a fascinating pair that contradicts the statement of the theorem. | | ∈ { } 4.1.1. E(N) 10, 11 . | | ≤ | | ≤ Certainly E(N) 11, since E(M) 15, and (M, N) is a fascinating | | − | | | | pair, so E(M) E(N) > 3. Assume that E(N) < 10. First consider | | the case that E(N) = 6, so that N is isomorphic to M(K ). If M has a (cid:48) | | − | (cid:48) | ≤ 4 (cid:48) proper minor, M , such that E(M) E(M ) 3, and M is internally (cid:48) 4-connected, then M has an M(K )-minor [16, Corollary 12.2.13], and hence 4 (M, N) is not a fascinating pair. Therefore M has no such minor, so we can | | ≤ apply our chain theorem [1, Theorem 1.3]. Since E(M) 15, it follows from that theorem that M is the cycle matroid of a planar or M¨obius quartic ladder, or the dual of such a matroid. The only planar quartic ladder with fewer than 16 edges is the octahedron, O, which is the dual graph of Q , 3 the cube. The only M¨obius quartic ladders with fewer than 16 edges have 14 or 10 edges. The former has the latter as a minor, and the latter is isomorphic to K . From this we deduce that, up to duality, (M, N) is 5 (M(Q ), M(K )) or (M(K ), M(K )), and that therefore (M, N) is not a 3 4 5 4 | | counterexample after all. Hence 6 < E(N) < 10. The only internally 4-connected binary matroids satisfying this constraint are F , M(K ), and 7 3,3 their duals. (This fact is [10, Lemma 2.1], and will also be conﬁrmed by the subsequent exhaustive search.) Thus we can assume N is F or M(K ). 7 3,3 From this point, we use almost exactly the same arguments as in [4, | | ≥ Lemma 2.3]. Assume N is F7, so E(M) 11\. ∼We can use [18∼, Co∗rol- lary 1.2] to deduce that M is isomorphic to T12 e = Υ6 or T12/e = Υ6, so (M, N) fails to contradict the theorem. Therefore we assume N is M(K ), | | ≥ 3,3 and hence E(M) 13. Now we can use [10, Lemma 2.3]. This lemma deﬁnes ﬁve graphs, but only four of them have at least 13 edges. Therefore we can deduce that M is isomorphic to one of the graphic matroids M(H ), 1 M(H ), M(H ), or M(QM ). Again this is a contradiction, as it implies 2 3 7 that (M, N) is not a counterexample, so the proof of 4.1.1 is complete. At this point, it is appropriate to verify that the pairs mentioned in the proof of 4.1.1 are indeed fascinating. We do this, and the rest of the search, using the matroid capabilities of sage (Version 6.10). First we want to allow access to certain special functions of the sage matroids package. from sage.matroids.advanced import * We will require a test for internal 4-connectivity. def IsIFC(M): if len(M)<=7: return True elif len(M)==8 or len(M)==9: return all( (M.rank(X)+ M.rank(M.groundset().symmetric_difference(X))- M.rank() > 2) for X in Subsets(M.groundset(),4) )

text: A

text: SPLITTER

text: THEOREM

text: FOR

text: BINARY

text: MATROIDS

label: section

text: Proof

text: of

text: the

text: main

text: results

text: We

text: prove

text: Theorem

text: Assume

text: that

text: (M,

text: N)

text: is

text: a

text: fascinating

text: pair

text: that

text: contradicts

text: the

text: statement

text: of

text: the

text: theorem.

text: E(N)

text: Certainly

text: E(N)

text: since

text: E(M)

text: and

text: (M,

text: N)

text: is

text: a

text: fascinating

text: pair,

text: so

text: E(M)

text: E(N)

text: Assume

text: that

text: E(N)

text: First

text: consider

text: the

text: case

text: that

text: E(N)

text: so

text: that

text: N

text: is

text: isomorphic

text: to

text: M(K

text: If

text: M

text: has

text: a

text: proper

text: minor,

text: M

text: such

text: that

text: E(M)

text: E(M

text: and

text: M

text: is

text: internally

text: then

text: M

text: has

text: an

text: M(K

text: )-minor

text: Corollary

text: and

text: hence

text: (M,

text: N)

text: is

text: not

text: a

text: fascinating

text: pair.

text: Therefore

text: M

text: has

text: no

text: such

text: minor,

text: so

text: we

text: can

text: apply

text: our

text: chain

text: theorem

text: Theorem

text: Since

text: E(M)

text: it

text: follows

text: from

text: that

text: theorem

text: that

text: M

text: is

text: the

text: cycle

text: matroid

text: of

text: a

text: planar

text: or

text: M¨obius

text: quartic

text: ladder,

text: or

text: the

text: dual

text: of

text: such

text: a

text: matroid.

text: The

text: only

text: planar

text: quartic

text: ladder

text: with

text: fewer

text: than

text: edges

text: is

text: the

text: octahedron,

text: O,

text: which

text: is

text: the

text: dual

text: graph

text: of

text: Q

text: the

text: cube.

text: The

text: only

text: M¨obius

text: quartic

text: ladders

text: with

text: fewer

text: than

text: edges

text: have

text: or

text: edges.

text: The

text: former

text: has

text: the

text: latter

text: as

text: a

text: minor,

text: and

text: the

text: latter

text: is

text: isomorphic

text: to

text: K

text: From

text: this

text: we

text: deduce

text: that,

text: up

text: to

text: duality,

text: (M,

text: N)

text: is

text: (M(Q

text: M(K

text: or

text: (M(K

text: M(K

text: and

text: that

text: therefore

text: (M,

text: N)

text: is

text: not

text: a

text: counterexample

text: after

text: all.

text: Hence

text: E(N)

text: The

text: only

text: internally

text: binary

text: matroids

text: satisfying

text: this

text: constraint

text: are

text: F

text: M(K

text: and

text: their

text: duals.

text: (This

text: fact

text: is

text: Lemma

text: and

text: will

text: also

text: be

text: conﬁrmed

text: by

text: the

text: subsequent

text: exhaustive

text: search.)

text: Thus

text: we

text: can

text: assume

text: N

text: is

text: F

text: or

text: M(K

text: From

text: this

text: point,

text: we

text: use

text: almost

text: exactly

text: the

text: same

text: arguments

text: as

text: in

text: Lemma

text: Assume

text: N

text: is

text: so

text: E(M)

text: ∼We

text: can

text: use

text: Co∗rol-

text: lary

text: to

text: deduce

text: that

text: M

text: is

text: isomorphic

text: to

text: e

text: Υ6

text: or

text: so

text: (M,

text: N)

text: fails

text: to

text: contradict

text: the

text: theorem.

text: Therefore

text: we

text: assume

text: N

text: is

text: M(K

text: and

text: hence

text: E(M)

text: Now

text: we

text: can

text: use

text: Lemma

text: This

text: lemma

text: deﬁnes

text: ﬁve

text: graphs,

text: but

text: only

text: four

text: of

text: them

text: have

text: at

text: least

text: edges.

text: Therefore

text: we

text: can

text: deduce

text: that

text: M

text: is

text: isomorphic

text: to

text: one

text: of

text: the

text: graphic

text: matroids

text: M(H

text: M(H

text: M(H

text: or

text: M(QM

text: Again

text: this

text: is

text: a

text: contradiction,

text: as

text: it

text: implies

text: that

text: (M,

text: N)

text: is

text: not

text: a

text: counterexample,

text: so

text: the

text: proof

text: of

text: is

text: complete.

text: At

text: this

text: point,

text: it

text: is

text: appropriate

text: to

text: verify

text: that

text: the

text: pairs

text: mentioned

text: in

text: the

text: proof

text: of

text: are

text: indeed

text: fascinating.

text: We

text: do

text: this,

text: and

text: the

text: rest

text: of

text: the

text: search,

text: using

text: the

text: matroid

text: capabilities

text: of

text: sage

text: (Version

text: First

text: we

text: want

text: to

text: allow

text: access

text: to

text: certain

text: special

text: functions

text: of

text: the

text: sage

text: matroids

text: package.

text: from

text: sage.matroids.advanced

text: import

text: We

text: will

text: require

text: a

text: test

text: for

text: internal

text: def

text: IsIFC(M):

text: if

text: return

text: True

text: elif

text: or

text: return

text: all(

text: (M.rank(X)+

text: M.rank()

text: for

text: X

text: in


text: A SPLITTER THEOREM FOR BINARY MATROIDS 29 [1,0,0,0,1,0], [0,1,0,1,0,0], [0,0,0,1,1,0]]))).dual()) print IFCCatalogue[14][6][1169].is_isomorphic( Matroid(reduced_matrix=A.stack(Matrix(GF(2),[ [1,0,0,0,1,0], [0,1,1,0,1,0], [0,1,0,1,0,1], [0,0,1,1,0,0]]))).dual()) True True True True True The tuples (14, 7, 3291, 0) and (15, 7, 0, 4) correspond to (A , ∆ ) and ∗ ∗ 6 4 (Υ , ∆ ). 8 4 print IFCCatalogue[14][7][3291].is_isomorphic( Matroid(reduced_matrix=A.stack(Matrix(GF(2),[ [1,1,0,0,1,0], [1,0,0,0,1,0], [1,0,0,0,0,0]])).augment(vector(GF(2),[1,1,0,0,0,0,1])))) True Upsilon8=Matroid(reduced_matrix=Matrix(GF(2),[ [1,0,0,0,0,0,1,1], [1,1,0,0,0,0,0,1], [0,1,1,0,0,0,0,1], [0,0,1,1,0,0,0,1], [0,0,0,1,1,0,0,1], [0,0,0,0,1,1,0,1], [0,0,0,0,0,1,1,1]])).dual() IFCCatalogue[15][7][0].is_isomorphic(Upsilon8.dual()) True ∗ Targets[22] is isomorphic to P . B=Matrix(GF(2),[ [1,1,1,0,0,0,1], [1,0,0,1,1,0,1], [0,1,0,1,0,1,1], [0,0,1,0,1,1,1]]) P=Matroid(reduced_matrix=B) Targets[22].is_isomorphic(P.dual()) True The tuples (15, 7, 34466, 22), (15, 7, 34762, 22), (15, 7, 34137, 22), (15, 7, 34693, 22), and (15, 7, 34769, 22) correspond to the fascinating ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ pairs (B , P ), (B , P ), (B , P ), (B , P ), and (B , P ). 1 2 3 4 5 print IFCCatalogue[15][7][34466].is_isomorphic( Matroid(reduced_matrix=B.stack(Matrix(GF(2),[ [1,1,0,0,0,0,1],

text: A

text: SPLITTER

text: THEOREM

text: FOR

text: BINARY

text: MATROIDS

text: print

text: True

text: True

text: True

text: True

text: True

text: The

text: tuples

text: and

text: correspond

text: to

text: (A

text: and

text: (Υ

text: print

text: True

text: True

text: is

text: isomorphic

text: to

text: P

text: True

text: The

text: tuples

text: and

text: correspond

text: to

text: the

text: fascinating

text: pairs

text: (B

text: P

text: (B

text: P

text: (B

text: P

text: (B

text: P

text: and

text: (B

text: P

text: print


text: 4 CHUN, MAYHEW, AND OXLEY Theorem 1.3. Assume G and G are internally 4-connected graphs such | | ≤ 1 2 that E(G ) 15, and G has a proper G -minor. Assume also that if G 1 1 2 is an internally 4-connected graph such that G has a proper G-minor, and | | − | | 1 G has a G -minor, then E(G ) E(G) > 3. Then one of the following 2 1 statements holds. • G is one of K , Q , O, or QM , and G is K ; • 1 5 3 7 2 4 G is one of H , H , H , or QM , and G is K ; • 1 ×1 2 3 7 2 3,3 G is one of Q , Y , QM , or CM , and G is K . 1 3 9 7 10 2 5 In many of the pairs in Theorem 1.1 or Theorem 1.2, we encounter struc- tures that are familiar from the analysis in the rest of the project. These structures lead to operations that we can use to produce a smaller inter- nally 4-connected matroid from a larger one. Four such operations will be documented in ?? . In the following results, we explain exactly when it is possible to perform them on our fascinating and interesting pairs. Theorem 1.4. Let the pair (M, N) be as described in one of the state- ments (1)–(10) in Theorem 1.1. If (M, N) is not one of (M(Q ), M(K )), ∗ 3 4 (M(K ), M(K )), (Υ , F ), (Υ , F ), (M(QM ), M(K )), or (Υ , ∆ ), 5 4 6 7 6 7 ∗ 7 3,3 ∗ 8 4 then N can be obtained from M (or N can be obtained from M ) by one of the following four operations: (1) trimming a ring of bowties; (2) deleting the central cocircuit of a good augmented 4-wheel; (3) a ladder-compression move; or (4) trimming an open rotor chain. The next corollary deals with the three interesting pairs identiﬁed in The- orem 1.2. ∗ Corollary 1.5. Let (M, N) be (M(QM ), M(K )), (Υ , F ), or (Υ , F ). 7 4 8 7 8 7≺ Then there is an internally 4-connected binary matroid, M , such that N ≺ ∗0 M M, and either M can be obtained from M (or M can be obtained 0 ∗ 0 0 from M ) by a ladder-compression move. We note that some of the exceptional pairs in Theorem 1.4 are dealt with by some of the speciﬁc scenarios∼from our main theorem, which appears in [9]. In particular, since ∆3 = F7, we see that if (M, N) is (Υ6, F7) or (Υ , ∆ ), then M is a triadic M¨obius matroid of rank 2r, and N is a 8 4 triangular M¨obius matroid of rank r. If (M, N) is (M(QM ), M(CM )), 7 6 then M is the cycle matroid of a quartic M¨obius ladder, and N is the cycle − matroid of a cubic M¨obius ladder, and r(N) = r(M) 1. Thus the only truly ∗ exceptional pairs are (M(K ), M(K )), (M(Q ), M(K )), and (Υ , F ). 5 4 3 4 6 7 We prove Theorems 1.1 and 1.2 with an exhaustive search, using the ma- troid functionality of the sage mathematics package, (Version 6.10) [17]. All the computations performed in this search were performed on a single desk- top computer, and took a total of approximately 55 hours of computation. The code used in the search is available from http://homepages.ecs.vuw.

text: CHUN,

text: MAYHEW,

text: AND

text: OXLEY

text: Theorem

text: Assume

text: G

text: and

text: G

text: are

text: internally

text: graphs

text: such

text: that

text: E(G

text: and

text: G

text: has

text: a

text: proper

text: G

text: -minor.

text: Assume

text: also

text: that

text: if

text: G

text: is

text: an

text: internally

text: graph

text: such

text: that

text: G

text: has

text: a

text: proper

text: G-minor,

text: and

text: G

text: has

text: a

text: G

text: -minor,

text: then

text: E(G

text: E(G)

text: Then

text: one

text: of

text: the

text: following

text: statements

text: holds.

label: list

text: G

text: is

text: one

text: of

text: K

text: Q

text: O,

text: or

text: QM

text: and

text: G

text: is

text: K

text: G

text: is

text: one

text: of

text: H

text: H

text: H

text: or

text: QM

text: and

text: G

text: is

text: K

text: ×1

text: G

text: is

text: one

text: of

text: Q

text: Y

text: QM

text: or

text: CM

text: and

text: G

text: is

text: K

text: In

text: many

text: of

text: the

text: pairs

text: in

text: Theorem

text: or

text: Theorem

text: we

text: encounter

text: struc-

text: tures

text: that

text: are

text: familiar

text: from

text: the

text: analysis

text: in

text: the

text: rest

text: of

text: the

text: project.

text: These

text: structures

text: lead

text: to

text: operations

text: that

text: we

text: can

text: use

text: to

text: produce

text: a

text: smaller

text: inter-

text: nally

text: matroid

text: from

text: a

text: larger

text: one.

text: Four

text: such

text: operations

text: will

text: be

text: documented

text: in

text: In

text: the

text: following

text: results,

text: we

text: explain

text: exactly

text: when

text: it

text: is

text: possible

text: to

text: perform

text: them

text: on

text: our

text: fascinating

text: and

text: interesting

text: pairs.

text: Theorem

text: Let

text: the

text: pair

text: (M,

text: N)

text: be

text: as

text: described

text: in

text: one

text: of

text: the

text: state-

text: ments

text: in

text: Theorem

text: If

text: (M,

text: N)

text: is

text: not

text: one

text: of

text: (M(Q

text: M(K

text: (M(K

text: M(K

text: (Υ

text: F

text: (Υ

text: F

text: (M(QM

text: M(K

text: or

text: (Υ

text: then

text: N

text: can

text: be

text: obtained

text: from

text: M

text: (or

text: N

text: can

text: be

text: obtained

text: from

text: M

text: by

text: one

text: of

text: the

text: following

text: four

text: operations:

text: trimming

text: a

text: ring

text: of

text: bowties;

text: deleting

text: the

text: central

text: cocircuit

text: of

text: a

text: good

text: augmented

text: a

text: ladder-compression

text: move;

text: or

text: trimming

text: an

text: open

text: rotor

text: chain.

text: The

text: next

text: corollary

text: deals

text: with

text: the

text: three

text: interesting

text: pairs

text: identiﬁed

text: in

text: The-

text: orem

text: Corollary

text: Let

text: (M,

text: N)

text: be

text: (M(QM

text: M(K

text: (Υ

text: F

text: or

text: (Υ

text: F

text: 7≺

text: Then

text: there

text: is

text: an

text: internally

text: binary

text: matroid,

text: M

text: such

text: that

text: N

text: ∗0

text: M

text: M,

text: and

text: either

text: M

text: can

text: be

text: obtained

text: from

text: M

text: (or

text: M

text: can

text: be

text: obtained

text: from

text: M

text: by

text: a

text: ladder-compression

text: move.

text: We

text: note

text: that

text: some

text: of

text: the

text: exceptional

text: pairs

text: in

text: Theorem

text: are

text: dealt

text: with

text: by

text: some

text: of

text: the

text: speciﬁc

text: scenarios∼from

text: our

text: main

text: theorem,

text: which

text: appears

text: in

text: In

text: particular,

text: since

text: ∆3

text: we

text: see

text: that

text: if

text: (M,

text: N)

text: is

text: or

text: (Υ

text: then

text: M

text: is

text: a

text: triadic

text: M¨obius

text: matroid

text: of

text: rank

text: and

text: N

text: is

text: a

text: triangular

text: M¨obius

text: matroid

text: of

text: rank

text: r.

text: If

text: (M,

text: N)

text: is

text: (M(QM

text: M(CM

text: then

text: M

text: is

text: the

text: cycle

text: matroid

text: of

text: a

text: quartic

text: M¨obius

text: ladder,

text: and

text: N

text: is

text: the

text: cycle

text: matroid

text: of

text: a

text: cubic

text: M¨obius

text: ladder,

text: and

text: r(N)

text: r(M)

text: Thus

text: the

text: only

text: truly

text: exceptional

text: pairs

text: are

text: (M(K

text: M(K

text: (M(Q

text: M(K

text: and

text: (Υ

text: F

text: We

text: prove

text: Theorems

text: and

text: with

text: an

text: exhaustive

text: search,

text: using

text: the

text: ma-

text: troid

text: functionality

text: of

text: the

text: sage

text: mathematics

text: package,

text: (Version

text: All

text: the

text: computations

text: performed

text: in

text: this

text: search

text: were

text: performed

text: on

text: a

text: single

text: desk-

text: top

text: computer,

text: and

text: took

text: a

text: total

text: of

text: approximately

text: hours

text: of

text: computation.

text: The

text: code

text: used

text: in

text: the

text: search

text: is

text: available

text: from


text: PROOF OF STEMBRIDGE’S CONJECTURE ON KRONECKER COEFFICIENTS 7 Remark 4.3. From what we have shown, (α, β, γ) is stable if and only if the Krull dimen- sion of B is 1. Since B is a ring of invariants, this property can be determined α,β,γ α,β,γ algorithmically. Although it is probably impractical, there did not seem to be an algorithm (cid:3) previously for determining stability. ⊗ Remark 4.4. Deﬁne Gα,β,γ to be the dimension of the vector space Nλ,µ,ν Frac(B ). λ,µ,ν α,β,γ α,β,γ (Note the swap of superscripts and subscripts.) If (α, β, γ) is stable then Gα,β,γ is equal to λ,µ,ν the limiting value of g . In particular, G(1),(1),(1) is the usual stable Kronecker α+dλ,β+dµ,γ+dν λ,µ,ν coeﬃcient G . It would be interesting if one could say anything about the numbers λ,µ,ν Gα,β,γ in general. For example, there is a well-known relationship between stable Kronecker λ,µ,ν coeﬃcients and Littlewood–Richardson coeﬃcients. Does this generalize in any way to the (cid:3) Gα,β,γ? λ,µ,ν (cid:55)→ Remark 4.5. Since the function d g is given by a quasi-polynomial p (d) for ≥ § dα,dβ,dγ α,β,γ all d 0 (see ), one can ask if the rings B have toric degenerations. This would imply α,β,γ that there is a rational polytope Q(α, β, γ) such that the p (d) is the number of integer ≥ α,β,γ points in the dth dilate of Q for all d 0. Ehrhart reciprocity [Sta, Theorem 4.6.9] implies | − | that p ( d) is the number of integer points in the interior of the dth dilate of Q. So in α,β,γ ≥ | − | (cid:40) particular, p (d) p ( d) . α,β,γ α,β,γ However, from [BOR, Theorem 2.4], this fails for α = (6, 6), β = (7, 5), γ = (6, 4, 2) where (d + 2)/2 if d is even p (d) = − . α,β,γ (d 1)/2 if d is odd − − In particular, p(1) = 0 and p( 1) = 1. So no such polytopes exist in general. We thank (cid:3) Mateusz Micha(cid:32)lek for bringing this example to our attention. ⊗ ⊕ If we replace V W in (2.2) with V W , then we get a version of Theorem 1.4 with Kronecker coeﬃcients replaced by Littlewood–Richardson coeﬃcients cλ (see [SS2, (3.11)]). µ,ν In this case, a diﬀerent construction for the analog of the ring B is given in [DW] and (cid:55)→ the rational singularities property was used to deduce that the function d cdλ is a ≥ dµ,dν polynomial for d 0 [DW, Corollary 3]. This gives the following concrete statement (which can be deduced from previous work, see Remark 4.7): | | | | | | Theorem 4.6. Pick partitions α, β, γ with β + γ = α . The following are equivalent: (a) cα = 1. β,γ (b) cdα = 1 for all d > 0. dβ,dγ | | | | | | (cid:29) (c) For all partitions λ, µ, ν with µ + ν = λ , cλ+dα is constant for d 0. µ+dβ,ν+dγ § Proof. (a) and (b) are equivalent by [KTW, 6.1]. (c) implies (a) and (b) by taking λ = µ = ∅ (cid:55)→ ≥ ∅ ν = and using that d cdα is a polynomial for all d 0 and that c∅ ∅ = 1. dβ,dγ , (cid:3) (b) implies (c) by following the same arguments in this paper.

text: PROOF

text: OF

text: STEMBRIDGE’S

text: CONJECTURE

text: ON

text: KRONECKER

text: COEFFICIENTS

text: Remark

text: From

text: what

text: we

text: have

text: shown,

text: (α,

text: β,

text: γ)

text: is

text: stable

text: if

text: and

text: only

text: if

text: the

text: Krull

text: dimen-

text: sion

text: of

text: B

text: is

text: Since

text: B

text: is

text: a

text: ring

text: of

text: invariants,

text: this

text: property

text: can

text: be

text: determined

text: α,β,γ

text: α,β,γ

text: algorithmically.

text: Although

text: it

text: is

text: probably

text: impractical,

text: there

text: did

text: not

text: seem

text: to

text: be

text: an

text: algorithm

text: previously

text: for

text: determining

text: stability.

text: Remark

text: Deﬁne

text: Gα,β,γ

text: to

text: be

text: the

text: dimension

text: of

text: the

text: vector

text: space

text: Nλ,µ,ν

text: Frac(B

text: λ,µ,ν

text: α,β,γ

text: α,β,γ

text: (Note

text: the

text: swap

text: of

text: superscripts

text: and

text: subscripts.)

text: If

text: (α,

text: β,

text: γ)

text: is

text: stable

text: then

text: Gα,β,γ

text: is

text: equal

text: to

text: λ,µ,ν

text: the

text: limiting

text: value

text: of

text: g

text: In

text: particular,

text: is

text: the

text: usual

text: stable

text: Kronecker

text: α+dλ,β+dµ,γ+dν

text: λ,µ,ν

text: coeﬃcient

text: G

text: It

text: would

text: be

text: interesting

text: if

text: one

text: could

text: say

text: anything

text: about

text: the

text: numbers

text: λ,µ,ν

text: Gα,β,γ

text: in

text: general.

text: For

text: example,

text: there

text: is

text: a

text: well-known

text: relationship

text: between

text: stable

text: Kronecker

text: λ,µ,ν

text: coeﬃcients

text: and

text: Littlewood–Richardson

text: coeﬃcients.

text: Does

text: this

text: generalize

text: in

text: any

text: way

text: to

text: the

text: Gα,β,γ?

text: λ,µ,ν

text: Remark

text: Since

text: the

text: function

text: d

text: g

text: is

text: given

text: by

text: a

text: quasi-polynomial

text: p

text: (d)

text: for

text: dα,dβ,dγ

text: α,β,γ

text: all

text: d

text: (see

text: one

text: can

text: ask

text: if

text: the

text: rings

text: B

text: have

text: toric

text: degenerations.

text: This

text: would

text: imply

text: α,β,γ

text: that

text: there

text: is

text: a

text: rational

text: polytope

text: Q(α,

text: β,

text: γ)

text: such

text: that

text: the

text: p

text: (d)

text: is

text: the

text: number

text: of

text: integer

text: α,β,γ

text: points

text: in

text: the

text: dth

text: dilate

text: of

text: Q

text: for

text: all

text: d

text: Ehrhart

text: reciprocity

text: [Sta,

text: Theorem

text: implies

text: that

text: p

text: d)

text: is

text: the

text: number

text: of

text: integer

text: points

text: in

text: the

text: interior

text: of

text: the

text: dth

text: dilate

text: of

text: Q.

text: So

text: in

text: α,β,γ

text: particular,

text: p

text: (d)

text: p

text: d)

text: α,β,γ

text: α,β,γ

text: However,

text: from

text: [BOR,

text: Theorem

text: this

text: fails

text: for

text: α

text: β

text: γ

text: where

text: (d

text: if

text: d

text: is

text: even

text: p

text: (d)

text: α,β,γ

text: (d

text: if

text: d

text: is

text: odd

text: In

text: particular,

text: and

text: p(

text: So

text: no

text: such

text: polytopes

text: exist

text: in

text: general.

text: We

text: thank

text: Mateusz

text: for

text: bringing

text: this

text: example

text: to

text: our

text: attention.

text: If

text: we

text: replace

text: V

text: W

text: in

text: with

text: V

text: W

text: then

text: we

text: get

text: a

text: version

text: of

text: Theorem

text: with

text: Kronecker

text: coeﬃcients

text: replaced

text: by

text: Littlewood–Richardson

text: coeﬃcients

text: cλ

text: (see

text: µ,ν

text: In

text: this

text: case,

text: a

text: diﬀerent

text: construction

text: for

text: the

text: analog

text: of

text: the

text: ring

text: B

text: is

text: given

text: in

text: [DW]

text: and

text: the

text: rational

text: singularities

text: property

text: was

text: used

text: to

text: deduce

text: that

text: the

text: function

text: d

text: cdλ

text: is

text: a

text: dµ,dν

text: polynomial

text: for

text: d

text: [DW,

text: Corollary

text: This

text: gives

text: the

text: following

text: concrete

text: statement

text: (which

text: can

text: be

text: deduced

text: from

text: previous

text: work,

text: see

text: Remark

text: Theorem

text: Pick

text: partitions

text: α,

text: β,

text: γ

text: with

text: β

text: γ

text: α

text: The

text: following

text: are

text: equivalent:

text: (a)

text: cα

text: β,γ

text: (b)

text: cdα

text: for

text: all

text: d

text: dβ,dγ

text: (c)

text: For

text: all

text: partitions

text: λ,

text: µ,

text: ν

text: with

text: µ

text: ν

text: λ

text: cλ+dα

text: is

text: constant

text: for

text: d

text: µ+dβ,ν+dγ

text: Proof.

text: (a)

text: and

text: (b)

text: are

text: equivalent

text: by

text: [KTW,

text: (c)

text: implies

text: (a)

text: and

text: (b)

text: by

text: taking

text: λ

text: µ

text: ν

text: and

text: using

text: that

text: d

text: cdα

text: is

text: a

text: polynomial

text: for

text: all

text: d

text: and

text: that

text: c∅

text: dβ,dγ

text: (b)

text: implies

text: (c)

text: by

text: following

text: the

text: same

text: arguments

text: in

text: this

text: paper.


text: Maximize the likelihood function pu0 pu1 pu2 pu3 subjected to 0 1 2 3 − p0 + 2p1 + 3p2 4p3 = 0, p0 + p1 + p2 + p3 = 1, p0 > 0, p1 > 0, p2 > 0,and p3 > 0. For some statistical models, the MLE problem can be solved by well known hill climbing algorithms such as the EM-algorithm. However, the hill climbing method can fail if there is more than one local maximum. Fortunately, it is known that the MLE problem can be solved by solving the system of likelihood equations [15, 2]: − − − F0 = p0λ1 + p0λ2 u0 F3 = p3λ1 4p3λ2 u3 − − F1 = p1λ1 + 2p1λ2 u1 F4 = p0 + 2p1 + 3p2 4p3 − − F2 = p2λ1 + 3p2λ2 u2 F5 = p0 + p1 + p2 + p3 1 where λ1 and λ2 are newly introduced indeterminates (Lagrange multipliers) for formulating the like- lihood equations. More speciﬁcally, for given (u , u , u , u ), if (p , p , p , p ) is a critical point of the 0 1 2 3 0 1 2 3 likelihood function, then there exist complex numbers λ1 and λ2 such that (p0, p1, p2, p3, λ1, λ2) is a so- lution of the polynomial system. For randomly chosen data u , the likelihood equations have 3 complex i solutions. However, only solutions with positive coordinates p are statistically meaningful. A solution i with all positive p coordinates is said to be a positive solution. So an important problem is real root i classiﬁcation (RRC): For which u , the polynomial system has 1, 2 and 3 real/positive solutions? i According to the theory of computational (real) algebraic geometry [26, 20], the number of (real/positive) solutions only changes when the data u goes across some “special” values (see Theorem 2). The set i of “special" u is a (projective) variety (see Lemma 4 in [20]) in (3 dimensional complex projective space) i 4-dimensional complex space. The number of real/positive solutions is uniform over each open con- nected component determined by the variety. In other words, the “special” u plays the similar role as i the discriminant for univariate polynomials. The ﬁrst step of RRC is calculating the “special” u , leading i to the discriminant problem: How to effectively compute the “special” u ? i Geometrically, the “special” u is a projection of a variety. So in principle, it can be computed by i elimination ( see Chapter 3, page 115–128 in [6]). For instance, by the command eliminate in Macaulay2 [10], we compute that the “special" u in the illustrative example form a hypersurface deﬁned by a i homogenous polynomial in (u , u , u , u ) (see Example 1). However, for most MLE problems, due to 0 1 2 3 the large size of likelihood equations, the elimination computation is too expensive. In this paper, we discuss the “discriminant" problem for the likelihood equations. The contributions of the paper are listed as follows. • For likelihood equations, we show that the “special" u form a projective variety. We call the i homogenous polynomial that generates the codimension 1 component of the projective variety the data- discriminant. This name distinguishes it from the weight-discriminant for the likelihood equations (which 2

text: Maximize

font: BFVOZW+URWPalladioL-Bold

text: the

text: likelihood

font: YSPVUS+URWPalladioL-BoldItal

text: function

font: NLHKZJ+URWPalladioL-Ital

text: subjected

text: to

font: GZZHXZ+URWPalladioL-Roma

text: For

text: some

text: statistical

text: models,

text: the

text: MLE

text: problem

text: can

text: be

text: solved

text: by

text: well

text: known

text: hill

text: climbing

text: algorithms

text: such

text: as

text: the

text: EM-algorithm.

text: However,

text: the

text: hill

text: climbing

text: method

text: can

text: fail

text: if

text: there

text: is

text: more

text: than

text: one

text: local

text: maximum.

text: Fortunately,

text: it

text: is

text: known

text: that

text: the

text: MLE

text: problem

text: can

text: be

text: solved

text: by

text: solving

text: the

text: system

text: of

text: likelihood

text: equations

text: where

text: λ1

text: and

text: λ2

text: are

text: newly

text: introduced

text: indeterminates

text: (Lagrange

text: multipliers)

text: for

text: formulating

text: the

text: like-

text: lihood

text: equations.

text: More

text: speciﬁcally,

text: for

text: given

text: (u

text: u

text: u

text: u

text: if

text: (p

text: p

text: p

text: p

text: is

text: a

text: critical

text: point

text: of

text: the

text: likelihood

text: function,

text: then

text: there

text: exist

text: complex

text: numbers

text: λ1

text: and

text: λ2

text: such

text: that

text: is

text: a

text: so-

text: lution

text: of

text: the

text: polynomial

text: system.

text: For

text: randomly

text: chosen

text: data

text: u

text: the

text: likelihood

text: equations

text: have

text: complex

text: i

text: solutions.

text: However,

text: only

text: solutions

text: with

text: positive

text: coordinates

text: p

text: are

text: statistically

text: meaningful.

text: A

text: solution

text: i

text: with

text: all

text: positive

text: p

text: coordinates

text: is

text: said

text: to

text: be

text: a

text: positive

text: solution.

text: So

text: an

text: important

text: problem

text: is

text: real

text: root

text: i

text: classiﬁcation

text: (RRC):

text: For

text: which

text: u

text: the

text: polynomial

text: system

text: has

text: and

text: real/positive

text: solutions?

text: i

text: According

text: to

text: the

text: theory

text: of

text: computational

text: (real)

text: algebraic

text: geometry

text: the

text: number

text: of

text: (real/positive)

text: solutions

text: only

text: changes

text: when

text: the

text: data

text: u

text: goes

text: across

text: some

text: “special”

text: values

text: (see

text: Theorem

text: The

text: set

text: i

text: of

text: “special"

text: u

text: is

text: a

text: (projective)

text: variety

text: (see

text: Lemma

text: in

text: in

text: dimensional

text: complex

text: projective

text: space)

text: i

text: complex

text: space.

text: The

text: number

text: of

text: real/positive

text: solutions

text: is

text: uniform

text: over

text: each

text: open

text: con-

text: nected

text: component

text: determined

text: by

text: the

text: variety.

text: In

text: other

text: words,

text: the

text: “special”

text: u

text: plays

text: the

text: similar

text: role

text: as

text: i

text: the

text: discriminant

text: for

text: univariate

text: polynomials.

text: The

text: ﬁrst

text: step

text: of

text: RRC

text: is

text: calculating

text: the

text: “special”

text: u

text: leading

text: i

text: to

text: the

text: discriminant

text: problem:

text: How

text: to

text: effectively

text: compute

text: the

text: “special”

text: u

text: i

text: Geometrically,

text: the

text: “special”

text: u

text: is

text: a

text: projection

text: of

text: a

text: variety.

text: So

text: in

text: principle,

text: it

text: can

text: be

text: computed

text: by

text: i

text: elimination

text: see

text: Chapter

text: page

text: in

text: For

text: instance,

text: by

text: the

text: command

text: eliminate

text: in

text: we

text: compute

text: that

text: the

text: “special"

text: u

text: in

text: the

text: illustrative

text: example

text: form

text: a

text: hypersurface

text: deﬁned

text: by

text: a

text: i

text: homogenous

text: polynomial

text: in

text: (u

text: u

text: u

text: u

text: (see

text: Example

text: However,

text: for

text: most

text: MLE

text: problems,

text: due

text: to

text: the

text: large

text: size

text: of

text: likelihood

text: equations,

text: the

text: elimination

text: computation

text: is

text: too

text: expensive.

text: In

text: this

text: paper,

text: we

text: discuss

text: the

text: “discriminant"

text: problem

text: for

text: the

text: likelihood

text: equations.

text: The

text: contributions

text: of

text: the

text: paper

text: are

text: listed

text: as

text: follows.

text: For

text: likelihood

text: equations,

text: we

text: show

text: that

text: the

text: “special"

text: u

text: form

text: a

text: projective

text: variety.

text: We

text: call

text: the

text: i

text: homogenous

text: polynomial

text: that

text: generates

text: the

text: codimension

text: component

text: of

text: the

text: projective

text: variety

text: the

text: data-

text: discriminant.

text: This

text: name

text: distinguishes

text: it

text: from

text: the

text: weight-discriminant

text: for

text: the

text: likelihood

text: equations

text: (which


text: We show an example to explain the basic idea of the probabilistic algorithm and how the lemmas work in the algorithm. (cid:104) (cid:105) ∩ Example 2 (Toy Example for Interpolation Idea). Suppose the radical of the elimination ideal F, J Q[u] is generated by D(u , u , u ), where F = u p2 + u p + u and J = 2u p + u . We already know 0 1 2 − 0 1 2 0 1 that D is homogenous and equals u2 4u u . Rather than by the standard elimination algorithm, we 1 0 2 compute D by the steps below. • First, we substitute u = t + 11, u = 3t + 2 and u = 5t + 6 into F and J (the integers 1, 11, 3, 2, 5 0 1 2 (cid:104) (cid:105) ∩ and 6 are randomly chosen). We compute the radical of the elimination ideal F(t, p), J(t, p) Q[t] (cid:104) (cid:105) and get 11t2 + 232t + 260 . By Lemma 2, D(t + 11, 3t + 2, 5t + 6) = 11t2 + 232t + 260. By Corollary 1, the total degree of D is 2 (it geometrically means the random line u = t + 11, u = 3t + 2, u = 5t + 6 0 1 2 intersect our desired hypersurface at 2 points in the parameter space and it is exactly the deﬁnition of the degree of hypersurface). Similarly, we compute the degree of D w.r.t u , u and u and get 1, 2 and 0 1 2 1, respectively. So all the possible monomials in D are u2, u u , u u and u u . • 1 0 1 1 2 0 2 Assume D = u2 + (C u + C u )u + C u u . We ﬁrst substitute u = 13 and u = 4 into F and 1 1 0 2 2 1 3 0 2 (cid:104) (cid:105) ∩0 2 (cid:104) − (cid:105) J. We compute the radical of the elimination ideal F(u , p), J(u , p) Q[u ] and get u2 208 . By − 1 1 −1 1 − Corollary 2, D(13, u , 4) equals u2 208. Hence, 13C + 4C = 0 and 52C = 208. Therefore, C = 4. 1 1 1 2 3 3 We need one more evaluation to solve C and C . So we substitute u = 7 and u = 3 into F and J. 1 2 0 − 2 Similarly, we get 7C + 3C = 0 and thus C = C = 0. Therefore, D = u2 4u u (the integers 13, 4, 7, 3 1 2 1 2 1 0 2 are randomly chosen). This example is “nice”. Because the degree of D w.r.t u equals the total degree of D. In general 1 case, if there is no u such that the degree of D w.r.t u equals the total degree, then we should apply the i i linear transformation to change the parameter coordinates before interpolation. Lemma 1 guarantees the linear transformation makes sense. Algorithm 3: Intersect input : DF0,. . ., Fm, J and integers b1,. . .,bn output: XJ(u0,b1,. . .,bn) 1 for i fr∗o←m 1 to n do 2 Fi replace ui in Fk with bi(cid:112) ← (cid:104) ∗ ∗ (cid:105) ∩ 3 A(u0) ← the generator of the elimin(cid:104)ation i(cid:105)deal F0, F1 ,. . ., Fn, Fn+1,. . . Fm, J Q[u0] 4 A(u0) the monic generator of A(u0) 5 return A(u0) D Now we are prepared to introduce the probabilistic algorithm for computing the . We explain XJ the main algorithm (Algorithm 2) and all the sub-algorithms (Algorithms 4–6) below. Algorithm 5 (Degree). The probabilistic algorithm terminates correctly by Corollary 1 and Lemma 2. Algorithm 4 (LinearOperator). The probabilistic algorithm terminates correctly by Lemma 1. Algorithm 3 (Intersect). The probabilistic algorithm terminates correctly by Corollary 2. Algorithm 2 (InterpolationDX-J). D D Lines 1–5. We compute the total degree of and the degrees of w.r.t u , . . . , u : d, d , . . . , d XJ XJ 0 d 0 n 11 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: We

text: show

text: an

text: example

text: to

text: explain

text: the

text: basic

text: idea

text: of

text: the

text: probabilistic

text: algorithm

text: and

text: how

text: the

text: lemmas

text: work

text: in

text: the

text: algorithm.

text: Example

text: (Toy

text: Example

text: for

text: Interpolation

text: Idea).

text: Suppose

text: the

text: radical

text: of

text: the

text: elimination

text: ideal

text: F,

text: J

text: Q[u]

text: is

text: generated

text: by

text: D(u

text: u

text: u

text: where

text: F

text: u

text: u

text: p

text: u

text: and

text: J

text: p

text: u

text: We

text: already

text: know

text: that

text: D

text: is

text: homogenous

text: and

text: equals

text: u

text: Rather

text: than

text: by

text: the

text: standard

text: elimination

text: algorithm,

text: we

text: compute

text: D

text: by

text: the

text: steps

text: below.

text: First,

text: we

text: substitute

text: u

text: t

text: u

text: and

text: u

text: into

text: F

text: and

text: J

text: (the

text: integers

text: and

text: are

text: randomly

text: chosen).

text: We

text: compute

text: the

text: radical

text: of

text: the

text: elimination

text: ideal

text: F(t,

text: p),

text: J(t,

text: p)

text: Q[t]

text: and

text: get

text: By

text: Lemma

text: D(t

text: By

text: Corollary

text: the

text: total

text: degree

text: of

text: D

text: is

text: (it

text: geometrically

text: means

text: the

text: random

text: line

text: u

text: t

text: u

text: u

text: intersect

text: our

text: desired

text: hypersurface

text: at

text: points

text: in

text: the

text: parameter

text: space

text: and

text: it

text: is

text: exactly

text: the

text: deﬁnition

text: of

text: the

text: degree

text: of

text: hypersurface).

text: Similarly,

text: we

text: compute

text: the

text: degree

text: of

text: D

text: w.r.t

text: u

text: u

text: and

text: u

text: and

text: get

text: and

text: respectively.

text: So

text: all

text: the

text: possible

text: monomials

text: in

text: D

text: are

text: u

text: u

text: u

text: u

text: and

text: u

text: u

text: Assume

text: D

text: (C

text: u

text: C

text: u

text: )u

text: C

text: u

text: u

text: We

text: ﬁrst

text: substitute

text: u

text: and

text: u

text: into

text: F

text: and

text: ∩0

text: J.

text: We

text: compute

text: the

text: radical

text: of

text: the

text: elimination

text: ideal

text: F(u

text: p),

text: J(u

text: p)

text: Q[u

text: and

text: get

text: By

text: −1

text: Corollary

text: u

text: equals

text: Hence,

text: and

text: Therefore,

text: C

text: We

text: need

text: one

text: more

text: evaluation

text: to

text: solve

text: C

text: and

text: C

text: So

text: we

text: substitute

text: u

text: and

text: u

text: into

text: F

text: and

text: J.

text: Similarly,

text: we

text: get

text: and

text: thus

text: C

text: C

text: Therefore,

text: D

text: u

text: (the

text: integers

text: are

text: randomly

text: chosen).

text: This

text: example

text: is

text: “nice”.

text: Because

text: the

text: degree

text: of

text: D

text: w.r.t

text: u

text: equals

text: the

text: total

text: degree

text: of

text: D.

text: In

text: general

text: case,

text: if

text: there

text: is

text: no

text: u

text: such

text: that

text: the

text: degree

text: of

text: D

text: w.r.t

text: u

text: equals

text: the

text: total

text: degree,

text: then

text: we

text: should

text: apply

text: the

text: i

text: i

text: linear

text: transformation

text: to

text: change

text: the

text: parameter

text: coordinates

text: before

text: interpolation.

text: Lemma

text: guarantees

text: the

text: linear

text: transformation

text: makes

text: sense.

text: Algorithm

text: Intersect

text: input

text: Fm,

text: J

text: and

text: integers

text: .,bn

text: output:

text: .,bn)

text: for

text: i

text: fr∗o←m

text: to

text: n

text: do

text: Fi

text: replace

text: ui

text: in

text: Fk

text: with

text: the

text: generator

text: of

text: the

text: Fn,

text: Fm,

text: J

text: the

text: monic

text: generator

text: of

text: return

text: D

text: Now

text: we

text: are

text: prepared

text: to

text: introduce

text: the

text: probabilistic

text: algorithm

text: for

text: computing

text: the

text: We

text: explain

text: XJ

text: the

text: main

text: algorithm

text: (Algorithm

text: and

text: all

text: the

text: sub-algorithms

text: (Algorithms

text: below.

text: Algorithm

text: (Degree).

text: The

text: probabilistic

text: algorithm

text: terminates

text: correctly

text: by

text: Corollary

text: and

text: Lemma

text: Algorithm

text: (LinearOperator).

text: The

text: probabilistic

text: algorithm

text: terminates

text: correctly

text: by

text: Lemma

text: Algorithm

text: (Intersect).

text: The

text: probabilistic

text: algorithm

text: terminates

text: correctly

text: by

text: Corollary

text: Algorithm

text: (InterpolationDX-J).

text: D

text: D

text: Lines

text: We

text: compute

text: the

text: total

text: degree

text: of

text: and

text: the

text: degrees

text: of

text: w.r.t

text: u

text: u

text: d,

text: d

text: d

text: XJ

text: XJ

text: d

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: I L ∩ V Proof. By the formulation of the Lagrange likelihood equations, we can prove that (π( X a(J)) is a homogeneous ideal by the two basic facts below, which can be proved by Deﬁnition 2 and basic algebraic geometry arguments. L ∩ V L ∩ V C1. For every ⊂u in π( X a(J)),∈each scalar multiple αu ∈is also in∈π( X Ia(J)). C2. For any S Cn+1, if for any u S and for any scalar α C, αu S, then (S) is a homogeneous ideal in Q[u]. I L ∩ V That means the Lideal V(π(I X L a(∩J)V) is generaVted by ﬁnitely manLy ho\m{o}geneVous polynomia⊂ls D1, . . ., Dm. Therefore, XJ = a( (π( X a(J))) = a(D1, . . . , Dm). So XJ 0 = (D1, . . . , Dm) Pn. (cid:3) D Notation 6. For an algebraic statistical model X, we deﬁne the notation according to the codimension of L \{ } XJ 0 in Pn. XJ• V V If the codimension is 1, then assume (D ), . . . , (D ) are the codimension 1 irreducible components in L \1{ } K (cid:104) (cid:105) (cid:104) (cid:105) D the minimal irreducible decomposition of 0 in Pn and D , . . ., D are radical. denotes the XJ 1 K XJ homogeneous polynomial ΠK D . • j=1 j D If the codimension is greater than 1, then our convention is to take = 1. XJ D L \{ } Similarly, we use the notation X∞ to denote the projective variety XJ 0 . Now we deﬁne the “data-discriminant” of Lagrange likelihood equations. Deﬁnition 5. (Data-Discriminant) For a given algebraic statistics model X, the homogeneous polynomial D · D · D XD∞ XJ Xp is said to be the data-discriminant (DD) of Lagrange likelihood equations of X and denoted by . X Remark 2. Note that DD can be viewed as a generalization of the “discriminant” for univariate polynomials. So it is interesting to compare DD with border polynomial (BP) [26] and discriminant variety (DV) [20]. DV and BP are deﬁned for general parametric polynomial systems. DD is deﬁned for the likelihood equations but can be generalized to any square and generic zero-dimensional system. Generally, for any square and generic zero- V ⊂ ⊂ V dimensional system, a(DD) DV a(BP). Note that due to the special structure of likelihood equations, DD is a homogenous polynomial despite being an afﬁne system of equations. However, generally, DV is not a projective variety and BP is not homogenous. Example 1 (Linear Model). The algebraic statistic model for the four sided die story in Section is given by V − ∩ X = (p + 2p + 3p 4p ) ∆ . 0 1 2 3 3 The Langrange likelihood equations are the F = 0, . . . , F = 0 shown in Section . The Langrange L V 0 ⊂ 5 ∈ lik−elihood corresp∩onLdence is X = a(F0, . . . , F5) C10. If we choose generic (u0, u1, u2, u3) D C4, πD 1(u0, u1D, u2, u3) X = 3, namely the ML-degree is 3. The data-discriminant is the product of X∞, and , where XpD XJ D DX∞ = u0 + u1 + u2 + u3, Xp = u0u1u2u3, and − − XJ = 441u40 + 4998u30u1 + 20041u20u21 + 33320u0u31 + 19600u41 756u30u2 + 20034u20u1u2 + 83370u0u21u2 + 79800u31u2 5346u20u22 + − − − − 55890u0u1u22 +119025u21u22 +4860u0u32 +76950u1u32 +18225u42 1596u30u3 11116u20u1u3 17808u0u21u3 +4480u31u3 +7452u20u2u3 7752u0u1u2u3 + 7

text: I

text: L

text: V

text: Proof.

text: By

text: the

text: formulation

text: of

text: the

text: Lagrange

text: likelihood

text: equations,

text: we

text: can

text: prove

text: that

text: (π(

text: X

text: a(J))

text: is

text: a

text: homogeneous

text: ideal

text: by

text: the

text: two

text: basic

text: facts

text: below,

text: which

text: can

text: be

text: proved

text: by

text: Deﬁnition

text: and

text: basic

text: algebraic

text: geometry

text: arguments.

text: L

text: V

text: L

text: V

text: For

text: every

text: ⊂u

text: in

text: π(

text: X

text: a(J)),∈each

text: scalar

text: multiple

text: αu

text: ∈is

text: also

text: in∈π(

text: X

text: Ia(J)).

text: For

text: any

text: S

text: if

text: for

text: any

text: u

text: S

text: and

text: for

text: any

text: scalar

text: α

text: C,

text: αu

text: S,

text: then

text: (S)

text: is

text: a

text: homogeneous

text: ideal

text: in

text: Q[u].

text: I

text: L

text: V

text: That

text: means

text: the

text: Lideal

text: V(π(I

text: X

text: L

text: a(∩J)V)

text: is

text: generaVted

text: by

text: ﬁnitely

text: manLy

text: ho\m{o}geneVous

text: polynomia⊂ls

text: Dm.

text: Therefore,

text: XJ

text: a(

text: (π(

text: X

text: a(J)))

text: Dm).

text: So

text: XJ

text: Dm)

text: Pn.

text: D

text: Notation

text: For

text: an

text: algebraic

text: statistical

text: model

text: X,

text: we

text: deﬁne

text: the

text: notation

text: according

text: to

text: the

text: codimension

text: of

text: L

text: XJ

text: in

text: Pn.

text: XJ•

text: V

text: V

text: If

text: the

text: codimension

text: is

text: then

text: assume

text: (D

text: (D

text: are

text: the

text: codimension

text: irreducible

text: components

text: in

text: L

text: K

text: D

text: the

text: minimal

text: irreducible

text: decomposition

text: of

text: in

text: Pn

text: and

text: D

text: D

text: are

text: radical.

text: denotes

text: the

text: XJ

text: K

text: XJ

text: homogeneous

text: polynomial

text: ΠK

text: D

text: j

text: D

text: If

text: the

text: codimension

text: is

text: greater

text: than

text: then

text: our

text: convention

text: is

text: to

text: take

text: XJ

text: D

text: L

text: Similarly,

text: we

text: use

text: the

text: notation

text: X∞

text: to

text: denote

text: the

text: projective

text: variety

text: XJ

text: Now

text: we

text: deﬁne

text: the

text: “data-discriminant”

text: of

text: Lagrange

text: likelihood

text: equations.

text: Deﬁnition

text: (Data-Discriminant)

text: For

text: a

text: given

text: algebraic

text: statistics

text: model

text: X,

text: the

text: homogeneous

text: polynomial

text: D

text: D

text: D

text: XD∞

text: XJ

text: Xp

text: is

text: said

text: to

text: be

text: the

text: data-discriminant

text: (DD)

text: of

text: Lagrange

text: likelihood

text: equations

text: of

text: X

text: and

text: denoted

text: by

text: X

text: Remark

text: Note

text: that

text: DD

text: can

text: be

text: viewed

text: as

text: a

text: generalization

text: of

text: the

text: “discriminant”

text: for

text: univariate

text: polynomials.

text: So

text: it

text: is

text: interesting

text: to

text: compare

text: DD

text: with

text: border

text: polynomial

text: (BP)

text: and

text: discriminant

text: variety

text: (DV)

text: DV

text: and

text: BP

text: are

text: deﬁned

text: for

text: general

text: parametric

text: polynomial

text: systems.

text: DD

text: is

text: deﬁned

text: for

text: the

text: likelihood

text: equations

text: but

text: can

text: be

text: generalized

text: to

text: any

text: square

text: and

text: generic

text: zero-dimensional

text: system.

text: Generally,

text: for

text: any

text: square

text: and

text: generic

text: zero-

text: V

text: V

text: dimensional

text: system,

text: a(DD)

text: DV

text: a(BP).

text: Note

text: that

text: due

text: to

text: the

text: special

text: structure

text: of

text: likelihood

text: equations,

text: DD

text: is

text: a

text: homogenous

text: polynomial

text: despite

text: being

text: an

text: afﬁne

text: system

text: of

text: equations.

text: However,

text: generally,

text: DV

text: is

text: not

text: a

text: projective

text: variety

text: and

text: BP

text: is

text: not

text: homogenous.

text: Example

text: (Linear

text: Model).

text: The

text: algebraic

text: statistic

text: model

text: for

text: the

text: four

text: sided

text: die

text: story

text: in

text: Section

text: is

text: given

text: by

text: V

text: X

text: (p

text: The

text: Langrange

text: likelihood

text: equations

text: are

text: the

text: F

text: F

text: shown

text: in

text: Section

text: The

text: Langrange

text: L

text: V

text: lik−elihood

text: corresp∩onLdence

text: is

text: X

text: If

text: we

text: choose

text: generic

text: D

text: πD

text: X

text: namely

text: the

text: ML-degree

text: is

text: The

text: data-discriminant

text: is

text: the

text: product

text: of

text: X∞,

text: and

text: where

text: XpD

text: XJ

text: D

text: DX∞

text: Xp

text: and

text: XJ


text: (cid:48) v(cid:48) r2 y(cid:48) ef f yr1(cid:48) x(cid:48)(cid:48) v(cid:48)(cid:48) v(cid:48) r2 y(cid:48) l e f(cid:48) yr1(cid:48) (cid:48)(cid:48) v(cid:48)(cid:48) e(cid:48) r1 r e(cid:48)(cid:48) r1 rx r1(cid:48) r2(cid:48) f e(cid:48)(cid:48) x (cid:48) e x v v Figure 11: Illustrating a sibling pair r, r(cid:48) originated at Figure 12: Illustrating a sibling pair r, r(cid:48) originated at a critical segment that does not require splitting. a critical segment that does require splitting. successive rays along e is upper bounded by (cid:15)(cid:48) (here, (cid:15)(cid:48) is deﬁned as in Lemma 4.3). Let y be the point located on e at Euclidean distance (cid:107)y(cid:48)v(cid:48)(cid:48)(cid:107)−(cid:15)(cid:48) from y(cid:48) such that y is located 1 1 between y(cid:48) and v(cid:48)(cid:48). Let r and r(cid:48) be two critically reﬂected (parallel) rays (making an angle −θ (f, f(cid:48)) c with →−v ), that originate from points y(cid:48) and y respectively. 1 If both the rays are incident to the same edge, say e(cid:48)(cid:48) of f, we set r, r(cid:48) as a sibling pair and all the rays between r and r(cid:48) that potentially cross the same edge sequence in the future together with r, r(cid:48) is a ray bundle. (See Fig. 11.) Let x (resp. x(cid:48)(cid:48)) be the point at which the ray r (resp. r(cid:48)) is incident onto edge e(cid:48)(cid:48). This sibling pair is traced further across the polygonal domain. If the rays in a sibling pair r, r(cid:48) are incident to distinct edges of f, we need to ﬁnd two rays r(cid:48) , r(cid:48) in R(κ), to respectively pair up with r and r(cid:48), for forming two new sibling pairs which deﬁne 1 2 two corresponding ray bundles. (See Fig. 12.) Further, we also need to store an event point in the event heap that corresponds to the current shortest distance to v if it is via the rays r(cid:48) and r(cid:48) . 1 2 At that stage, a discrete wavefront from v is initiated. The algorithm to split a sibling pair that originates from a critical segment is described in Subsection . 5.2.2 Initiating rays from a critical source There are three cases to consider based on the origin of the sibling pair, r and r , of a bundle 1 2 B that represents the discrete wavefront from the critical source y(cid:48) on an edge e: (i) r , r have originated from some critical segment 1 2 (ii) r , r have originated from some vertex 1 2 (iii) r , r have originated from (possibly distinct) nodes of a tree of rays, say T (w) 1 2 R We ﬁrst rule out case (i) as it cannot occur, since from Proposition 1, a critical point of exit and a critical point of entry cannot occur in succession along a geodesic path. Since case (iii) is a generalization of case (ii), herewith we explain event handling for case (iii). Let u ∈ T (w) be the origin of r . Note that u may be w itself or a distinct critical source in R 1 T (w). Let r, r(cid:48) be successive rays in R(u) such that r is refracted and r(cid:48) is critically reﬂected. R Let y(cid:48) be the point at which r(cid:48) is incident to v(cid:48)v(cid:48)(cid:48). A node corresponding to critical source y(cid:48) is inserted as a child of u in T (w); further, a set R(y(cid:48)) of rays are initiated from y(cid:48). Let θ(cid:48) be the R angle at which r refracts (measured with respect to the vector →−v normal to edge v(cid:48)v(cid:48)(cid:48)). Let v(cid:48)v(cid:48)(cid:48)v(cid:48)(cid:48)(cid:48) be the face f(cid:48) onto which ray r is refracted into. Also, let →−v and →−v be two vectors in face f(cid:48)(cid:48) with 1 2 origin y(cid:48) such that they respectively make π and θ(cid:48) angles with respect to →−v . (See Fig. 4.) The 2 −−→ rays in R(y(cid:48)) are uniformly distributed in the cone C(y(cid:48), y(cid:48)v(cid:48)(cid:48), →−v ). A ray bundle and a sibling pair 2 corresponding to that ray bundle are determined: Let r be the ray in R(y(cid:48)) that subtends the 3 minimum required angle, (cid:15)(cid:48) with edge e. And let r be the ray that originates from y(cid:48) and is parallel 2 16 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine##

font: default

text: ef

text: f

text: l

text: e

text: r

text: rx

text: f

text: x

text: e

text: x

text: v

text: v

text: Figure

text: Illustrating

text: a

text: sibling

text: pair

text: r,

text: originated

text: at

text: Figure

text: Illustrating

text: a

text: sibling

text: pair

text: r,

text: originated

text: at

text: a

text: critical

text: segment

text: that

text: does

text: not

text: require

text: splitting.

text: a

text: critical

text: segment

text: that

text: does

text: require

text: splitting.

text: successive

text: rays

text: along

text: e

text: is

text: upper

text: bounded

text: by

text: (here,

text: is

text: deﬁned

text: as

text: in

text: Lemma

text: Let

text: y

text: be

text: the

text: point

text: located

text: on

text: e

text: at

text: Euclidean

text: distance

text: from

text: such

text: that

text: y

text: is

text: located

text: between

text: and

text: Let

text: r

text: and

text: be

text: two

text: critically

text: reﬂected

text: (parallel)

text: rays

text: (making

text: an

text: angle

text: −θ

text: (f,

text: c

text: with

text: →−v

text: that

text: originate

text: from

text: points

text: and

text: y

text: respectively.

text: If

text: both

text: the

text: rays

text: are

text: incident

text: to

text: the

text: same

text: edge,

text: say

text: of

text: f,

text: we

text: set

text: r,

text: as

text: a

text: sibling

text: pair

text: and

text: all

text: the

text: rays

text: between

text: r

text: and

text: that

text: potentially

text: cross

text: the

text: same

text: edge

text: sequence

text: in

text: the

text: future

text: together

text: with

text: r,

text: is

text: a

text: ray

text: bundle.

text: (See

text: Fig.

text: Let

text: x

text: (resp.

text: be

text: the

text: point

text: at

text: which

text: the

text: ray

text: r

text: (resp.

text: is

text: incident

text: onto

text: edge

text: This

text: sibling

text: pair

text: is

text: traced

text: further

text: across

text: the

text: polygonal

text: domain.

text: If

text: the

text: rays

text: in

text: a

text: sibling

text: pair

text: r,

text: are

text: incident

text: to

text: distinct

text: edges

text: of

text: f,

text: we

text: need

text: to

text: ﬁnd

text: two

text: rays

text: in

text: R(κ),

text: to

text: respectively

text: pair

text: up

text: with

text: r

text: and

text: for

text: forming

text: two

text: new

text: sibling

text: pairs

text: which

text: deﬁne

text: two

text: corresponding

text: ray

text: bundles.

text: (See

text: Fig.

text: Further,

text: we

text: also

text: need

text: to

text: store

text: an

text: event

text: point

text: in

text: the

text: event

text: heap

text: that

text: corresponds

text: to

text: the

text: current

text: shortest

text: distance

text: to

text: v

text: if

text: it

text: is

text: via

text: the

text: rays

text: and

text: At

text: that

text: stage,

text: a

text: discrete

text: wavefront

text: from

text: v

text: is

text: initiated.

text: The

text: algorithm

text: to

text: split

text: a

text: sibling

text: pair

text: that

text: originates

text: from

text: a

text: critical

text: segment

text: is

text: described

text: in

text: Subsection

text: Initiating

text: rays

text: from

text: a

text: critical

text: source

text: There

text: are

text: three

text: cases

text: to

text: consider

text: based

text: on

text: the

text: origin

text: of

text: the

text: sibling

text: pair,

text: r

text: and

text: r

text: of

text: a

text: bundle

text: B

text: that

text: represents

text: the

text: discrete

text: wavefront

text: from

text: the

text: critical

text: source

text: on

text: an

text: edge

text: e:

text: (i)

text: r

text: r

text: have

text: originated

text: from

text: some

text: critical

text: segment

text: (ii)

text: r

text: r

text: have

text: originated

text: from

text: some

text: vertex

text: (iii)

text: r

text: r

text: have

text: originated

text: from

text: (possibly

text: distinct)

text: nodes

text: of

text: a

text: tree

text: of

text: rays,

text: say

text: T

text: (w)

text: R

text: We

text: ﬁrst

text: rule

text: out

text: case

text: (i)

text: as

text: it

text: cannot

text: occur,

text: since

text: from

text: Proposition

text: a

text: critical

text: point

text: of

text: exit

text: and

text: a

text: critical

text: point

text: of

text: entry

text: cannot

text: occur

text: in

text: succession

text: along

text: a

text: geodesic

text: path.

text: Since

text: case

text: (iii)

text: is

text: a

text: generalization

text: of

text: case

text: (ii),

text: herewith

text: we

text: explain

text: event

text: handling

text: for

text: case

text: (iii).

text: Let

text: u

text: T

text: (w)

text: be

text: the

text: origin

text: of

text: r

text: Note

text: that

text: u

text: may

text: be

text: w

text: itself

text: or

text: a

text: distinct

text: critical

text: source

text: in

text: R

text: T

text: (w).

text: Let

text: r,

text: be

text: successive

text: rays

text: in

text: R(u)

text: such

text: that

text: r

text: is

text: refracted

text: and

text: is

text: critically

text: reﬂected.

text: R

text: Let

text: be

text: the

text: point

text: at

text: which

text: is

text: incident

text: to

text: A

text: node

text: corresponding

text: to

text: critical

text: source

text: is

text: inserted

text: as

text: a

text: child

text: of

text: u

text: in

text: T

text: (w);

text: further,

text: a

text: set

text: of

text: rays

text: are

text: initiated

text: from

text: Let

text: be

text: the

text: R

text: angle

text: at

text: which

text: r

text: refracts

text: (measured

text: with

text: respect

text: to

text: the

text: vector

text: →−v

text: normal

text: to

text: edge

text: Let

text: be

text: the

text: face

text: onto

text: which

text: ray

text: r

text: is

text: refracted

text: into.

text: Also,

text: let

text: →−v

text: and

text: →−v

text: be

text: two

text: vectors

text: in

text: face

text: with

text: origin

text: such

text: that

text: they

text: respectively

text: make

text: π

text: and

text: angles

text: with

text: respect

text: to

text: →−v

text: (See

text: Fig.

text: The

text: rays

text: in

text: are

text: uniformly

text: distributed

text: in

text: the

text: cone

text: →−v

text: A

text: ray

text: bundle

text: and

text: a

text: sibling

text: pair

text: corresponding

text: to

text: that

text: ray

text: bundle

text: are

text: determined:

text: Let

text: r

text: be

text: the

text: ray

text: in

text: that

text: subtends

text: the

text: minimum

text: required

text: angle,

text: with

text: edge

text: e.

text: And

text: let

text: r

text: be

text: the

text: ray

text: that

text: originates

text: from

text: and

text: is

text: parallel

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##


text: originate from the same source or the sources of both the rays in a sibling pair belong to a tree of rays, T (v) or (iii) both the rays in a sibling pair originate from the same critical segment. A ray R bundle of the ﬁrst category is denoted as a ray bundle of T (v). R Let r(cid:48), r(cid:48)(cid:48) be a sibling pair of rays in a bundle B in T (v). Let u, w ∈ T (v) be the respective R R origins of r(cid:48) and r(cid:48)(cid:48). Also, let v(cid:48) be the least common ancestor of u and w in T (v). We deﬁne v(cid:48) to R be the root of B. The path P in tree T (v) from v(cid:48) to u comprising of a sequence of critical sources R is the critical ancestor path of r(cid:48) with respect to r(cid:48)(cid:48). Note that the critical ancestor path of a ray is always deﬁned with respect to a sibling pair. Given that rays in the bundle B are successive rays, nodes on the critical ancestor paths from u and w to v(cid:48) in the subtree T (v) provide all the rays in R the bundle B. We next show a property of the rays in a bundle. We deﬁne two rays to be pairwise divergent during traversal of an edge sequence E if they do not intersect each other during the traversal. A bundle of rays is divergent during traversal of E if all rays in the bundle are pairwise divergent during the traversal. Lemma 3.1 Let B be a ray bundle of T (v) and let E be the edge sequence associated with rays in R B. The rays in B are pairwise divergent whey they traverse across the edge sequence E. Proof: Let v(cid:48) be the root of a bundle. The rays in B that start from v(cid:48), termed R(v(cid:48)), clearly diverge during the traversal of the sequence of edges E, since divergence is preserved on refraction. Additionally, consider rays in B that are generated from a critical source, w, termed R(w). Each pair of rays, a steiner ray r originating at w and a ray in R(v(cid:48)), are pairwise divergent, by con- struction. Similarly, every pair of ray in R(w) is pairwise divergent. These rays remain pairwise divergent after refraction during propagation across edges in the sequence E. In general, let R be a bundle of rays that is divergent during traversal of a subsequence of E. These rays are generated from a vertex and/or a set of critical sources. Suppose the rays in the bundle strike an edge e ∈ E j and refract, and also generate a critical source w(cid:48) on e . Then R ∪ R(w(cid:48)), where R(w(cid:48)) is the set j of Steiner rays generated from w(cid:48), is a set of rays with every pair of rays being pairwise divergent during traversal of E since every steiner ray in R(w(cid:48)) is pairwise divergent from each ray in R. Thus these rays will not intersect each other as they strike edges e . . . e . (cid:116)(cid:117) j+1 k The consequence of this Lemma is that rays in a bundle B can be angle ordered. As described later, this ordering and the critical ancestor path of a ray will be useful in eﬃciently splitting a sibling pair of T (v). R 4 Bounding the number of initiated and traced rays Before detailing the algorithm, we bound the number of initiated and traced rays in P. An approximate weighted shortest path from source s to t can be split into sub-paths such that each such sub-path goes between a pair of vertices. Further, each of these sub-paths are classiﬁed into following types: • a Type-I path from one vertex to another vertex that does not use any critical segment in between, and • a Type-II path from one vertex to another vertex that critically reﬂects and uses at least one critical segment in-between. 8

text: originate

text: from

text: the

text: same

text: source

text: or

text: the

text: sources

text: of

text: both

text: the

text: rays

text: in

text: a

text: sibling

text: pair

text: belong

text: to

text: a

text: tree

text: of

text: rays,

text: T

text: (v)

text: or

text: (iii)

text: both

text: the

text: rays

text: in

text: a

text: sibling

text: pair

text: originate

text: from

text: the

text: same

text: critical

text: segment.

text: A

text: ray

text: R

text: bundle

text: of

text: the

text: ﬁrst

text: category

text: is

text: denoted

text: as

text: a

text: ray

text: bundle

text: of

text: T

text: (v).

text: R

text: Let

text: be

text: a

text: sibling

text: pair

text: of

text: rays

text: in

text: a

text: bundle

text: B

text: in

text: T

text: (v).

text: Let

text: u,

text: w

text: T

text: (v)

text: be

text: the

text: respective

text: R

text: R

text: origins

text: of

text: and

text: Also,

text: let

text: be

text: the

text: least

text: common

text: ancestor

text: of

text: u

text: and

text: w

text: in

text: T

text: (v).

text: We

text: deﬁne

text: to

text: R

text: be

text: the

text: root

text: of

text: B.

text: The

text: path

text: P

text: in

text: tree

text: T

text: (v)

text: from

text: to

text: u

text: comprising

text: of

text: a

text: sequence

text: of

text: critical

text: sources

text: R

text: is

text: the

text: critical

text: ancestor

text: path

text: of

text: with

text: respect

text: to

text: Note

text: that

text: the

text: critical

text: ancestor

text: path

text: of

text: a

text: ray

text: is

text: always

text: deﬁned

text: with

text: respect

text: to

text: a

text: sibling

text: pair.

text: Given

text: that

text: rays

text: in

text: the

text: bundle

text: B

text: are

text: successive

text: rays,

text: nodes

text: on

text: the

text: critical

text: ancestor

text: paths

text: from

text: u

text: and

text: w

text: to

text: in

text: the

text: subtree

text: T

text: (v)

text: provide

text: all

text: the

text: rays

text: in

text: R

text: the

text: bundle

text: B.

text: We

text: next

text: show

text: a

text: property

text: of

text: the

text: rays

text: in

text: a

text: bundle.

text: We

text: deﬁne

text: two

text: rays

text: to

text: be

text: pairwise

text: divergent

text: during

text: traversal

text: of

text: an

text: edge

text: sequence

text: E

text: if

text: they

text: do

text: not

text: intersect

text: each

text: other

text: during

text: the

text: traversal.

text: A

text: bundle

text: of

text: rays

text: is

text: divergent

text: during

text: traversal

text: of

text: E

text: if

text: all

text: rays

text: in

text: the

text: bundle

text: are

text: pairwise

text: divergent

text: during

text: the

text: traversal.

text: Lemma

text: Let

text: B

text: be

text: a

text: ray

text: bundle

text: of

text: T

text: (v)

text: and

text: let

text: E

text: be

text: the

text: edge

text: sequence

text: associated

text: with

text: rays

text: in

text: R

text: B.

text: The

text: rays

text: in

text: B

text: are

text: pairwise

text: divergent

text: whey

text: they

text: traverse

text: across

text: the

text: edge

text: sequence

text: E.

text: Proof:

text: Let

text: be

text: the

text: root

text: of

text: a

text: bundle.

text: The

text: rays

text: in

text: B

text: that

text: start

text: from

text: termed

text: clearly

text: diverge

text: during

text: the

text: traversal

text: of

text: the

text: sequence

text: of

text: edges

text: E,

text: since

text: divergence

text: is

text: preserved

text: on

text: refraction.

text: Additionally,

text: consider

text: rays

text: in

text: B

text: that

text: are

text: generated

text: from

text: a

text: critical

text: source,

text: w,

text: termed

text: R(w).

text: Each

text: pair

text: of

text: rays,

text: a

text: steiner

text: ray

text: r

text: originating

text: at

text: w

text: and

text: a

text: ray

text: in

text: are

text: pairwise

text: divergent,

text: by

text: con-

text: struction.

text: Similarly,

text: every

text: pair

text: of

text: ray

text: in

text: R(w)

text: is

text: pairwise

text: divergent.

text: These

text: rays

text: remain

text: pairwise

text: divergent

text: after

text: refraction

text: during

text: propagation

text: across

text: edges

text: in

text: the

text: sequence

text: E.

text: In

text: general,

text: let

text: R

text: be

text: a

text: bundle

text: of

text: rays

text: that

text: is

text: divergent

text: during

text: traversal

text: of

text: a

text: subsequence

text: of

text: E.

text: These

text: rays

text: are

text: generated

text: from

text: a

text: vertex

text: and/or

text: a

text: set

text: of

text: critical

text: sources.

text: Suppose

text: the

text: rays

text: in

text: the

text: bundle

text: strike

text: an

text: edge

text: e

text: E

text: j

text: and

text: refract,

text: and

text: also

text: generate

text: a

text: critical

text: source

text: on

text: e

text: Then

text: R

text: where

text: is

text: the

text: set

text: j

text: of

text: Steiner

text: rays

text: generated

text: from

text: is

text: a

text: set

text: of

text: rays

text: with

text: every

text: pair

text: of

text: rays

text: being

text: pairwise

text: divergent

text: during

text: traversal

text: of

text: E

text: since

text: every

text: steiner

text: ray

text: in

text: is

text: pairwise

text: divergent

text: from

text: each

text: ray

text: in

text: R.

text: Thus

text: these

text: rays

text: will

text: not

text: intersect

text: each

text: other

text: as

text: they

text: strike

text: edges

text: e

text: e

text: k

text: The

text: consequence

text: of

text: this

text: Lemma

text: is

text: that

text: rays

text: in

text: a

text: bundle

text: B

text: can

text: be

text: angle

text: ordered.

text: As

text: described

text: later,

text: this

text: ordering

text: and

text: the

text: critical

text: ancestor

text: path

text: of

text: a

text: ray

text: will

text: be

text: useful

text: in

text: eﬃciently

text: splitting

text: a

text: sibling

text: pair

text: of

text: T

text: (v).

text: R

text: Bounding

text: the

text: number

text: of

text: initiated

text: and

text: traced

text: rays

text: Before

text: detailing

text: the

text: algorithm,

text: we

text: bound

text: the

text: number

text: of

text: initiated

text: and

text: traced

text: rays

text: in

text: P.

text: An

text: approximate

text: weighted

text: shortest

text: path

text: from

text: source

text: s

text: to

text: t

text: can

text: be

text: split

text: into

text: sub-paths

text: such

text: that

text: each

text: such

text: sub-path

text: goes

text: between

text: a

text: pair

text: of

text: vertices.

text: Further,

text: each

text: of

text: these

text: sub-paths

text: are

text: classiﬁed

text: into

text: following

text: types:

text: a

text: Type-I

text: path

text: from

text: one

text: vertex

text: to

text: another

text: vertex

text: that

text: does

text: not

text: use

text: any

text: critical

text: segment

text: in

text: between,

text: and

text: a

text: Type-II

text: path

text: from

text: one

text: vertex

text: to

text: another

text: vertex

text: that

text: critically

text: reﬂects

text: and

text: uses

text: at

text: least

text: one

text: critical

text: segment

text: in-between.


text: 15 Eq. A33 remains the same for the relative uncertainty (cid:115) (cid:20) (cid:16) − (cid:17) (cid:21) 1 + δc δu k = δc+δu (A34) where δu,c stands for ∆xu,c/x, respectively. − 2 2 1 + δc δu δc+δu ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Eq.

text: remains

text: the

text: same

text: for

text: the

text: relative

text: uncertainty

label: equation

text: δc

text: δu

text: k

text: δc+δu

text: where

text: δu,c

text: stands

text: for

text: ∆xu,c/x,

text: respectively.

text: δc

text: δu

text: δc+δu

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##