text: known fact may be attributed to Alicki et al. [ARS88]; see [Aud06, equation (36)] for further discussion. We will include a proof for the reader’s convenience. Proposition 2.23. Let ρ be a d-dimensional density matrix with eigenvalues η , η , . . . , η . Then 1 2 d · SWn(λ) = dim(λ) s (η , η , . . . , η ). ρ λ 1 2 d In particular, SWn depends only on the spectrum of ρ. ρ D Remark 2.24. As this is the exact same formula as in Proposition 2.16, we conclude that if is the probability distribution on [d] given by the spectrum of ρ (in any order), then SWn(λ) = Pr [RSK(a) = λ]. ρ ∼D⊗ a n This gives a completely “quantum-free” way of analyzing quantum spectrum testing, as mentioned in Fact 1.6. Nevertheless, we will actually use this fact only occasionally (mainly via Theorem 2.14). As we will see later, interpreting SWn via representation theory proves to be more powerful. ρ ⊗ Proof of Proposition 2.23. By deﬁnition, SWn(λ) = tr(Π ρ n), where Π denotes the operator that ρ λ λ projects onto the subspace corresponding to λ in the Schur basis. It is a basic fact of representation theory (following from orthogonalit(cid:104)y relations, s(cid:105)ee e.g. [CHW07, Equation (7)]) that from the decomposition (5) of P we may deduce · · · · Πλ = dim(λ) π∼ESn χpλ(π) P(π) (cid:2)= dim(λ) π∼ESn [χλ(cid:3)(π) P(π)] . Thus · · ⊗ SWnρ(λ) = dim(λ) ∼E χλ(π) tr(P(π)ρ n) . (cid:32) π Sn(cid:33) To compute the trace, we may ass(cid:88)ume by u(cid:89)nitary invariance that ρ = diag(η , . . . , η ). Thus 1 d n ⊗ | (cid:105) (cid:104) | ρ n = η a , . . . , a a , . . . , a . ai 1 n 1 n words∈ i=1 (cid:81) (a1,...,an) [d]n D D Notice that if we let denote the probability distribution on [d] in which (a) = η , then the η D⊗ η a coeﬃcient n η above is n(a , . . . , a ); i.e., the probability that a random length-n word i=1 Dai (cid:88)η 1 n drawn i.i.d. from η is equal to (a1, . . . , an). From the deﬁnition of P(π) we further deduce ⊗ D⊗ | (cid:105) (cid:104) | P(π)ρ n = η n(a1, . . . , an) aπ−1(1), . . . , aπ−1(n) a1, . . . , an . (a1,...,an) ⊗ WeDim⊗ mediately conclude that tr(P(π)ρ n) is equal to the sum over all π-invariant words (a1, . . . , an) of n(a , . . . , a ). Recalling Deﬁnition 2.7, this is precisely given by the power sum polynomial η 1 n p (η , . . . , η ). Therefore π 1 d · · SWn(λ) = dim(λ) E [χ (π) p (η , . . . , η )] , ρ ∼ λ π 1 d π Sn and the proposition now follows from Theorem 2.20. For the purposes of the testing lower bounds in this paper, the case of greatest interest to us is when ρ = 1I × is the maximally mixed d-dimensional state; i.e., the spectrum of ρ is the uniform d d d distribution Unif = (1, . . . , 1). This is also by far the most well-studied case in the literature: d d d 21 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: known

text: fact

text: may

text: be

text: attributed

text: to

text: Alicki

text: et

text: al.

text: see

text: equation

text: for

text: further

text: discussion.

text: We

text: will

text: include

text: a

text: proof

text: for

text: the

text: reader’s

text: convenience.

text: Proposition

text: Let

text: ρ

text: be

text: a

text: d-dimensional

text: density

text: matrix

text: with

text: eigenvalues

text: η

text: η

text: η

text: Then

text: d

text: SWn(λ)

text: dim(λ)

text: s

text: (η

text: η

text: η

text: ρ

text: λ

text: d

text: In

text: particular,

text: SWn

text: depends

text: only

text: on

text: the

text: spectrum

text: of

text: ρ.

text: ρ

text: D

text: Remark

text: As

text: this

text: is

text: the

text: exact

text: same

text: formula

text: as

text: in

text: Proposition

text: we

text: conclude

text: that

text: if

text: is

text: the

text: probability

text: distribution

text: on

text: [d]

text: given

text: by

text: the

text: spectrum

text: of

text: ρ

text: (in

text: any

text: order),

text: then

text: SWn(λ)

text: Pr

text: [RSK(a)

text: λ].

text: ρ

text: ∼D⊗

text: a

text: n

text: This

text: gives

text: a

text: completely

text: “quantum-free”

text: way

text: of

text: analyzing

text: quantum

text: spectrum

text: testing,

text: as

text: mentioned

text: in

text: Fact

text: Nevertheless,

text: we

text: will

text: actually

text: use

text: this

text: fact

text: only

text: occasionally

text: (mainly

text: via

text: Theorem

text: As

text: we

text: will

text: see

text: later,

text: interpreting

text: SWn

text: via

text: representation

text: theory

text: proves

text: to

text: be

text: more

text: powerful.

text: ρ

text: Proof

text: of

text: Proposition

text: By

text: deﬁnition,

text: SWn(λ)

text: tr(Π

text: ρ

text: n),

text: where

text: Π

text: denotes

text: the

text: operator

text: that

text: ρ

text: λ

text: λ

text: projects

text: onto

text: the

text: subspace

text: corresponding

text: to

text: λ

text: in

text: the

text: Schur

text: basis.

text: It

text: is

text: a

text: basic

text: fact

text: of

text: representation

text: theory

text: (following

text: from

text: relations,

text: e.g.

text: Equation

text: that

text: from

text: the

text: decomposition

text: of

text: P

text: we

text: may

text: deduce

text: Πλ

text: dim(λ)

text: π∼ESn

text: χpλ(π)

text: P(π)

text: dim(λ)

text: π∼ESn

text: P(π)]

text: Thus

text: SWnρ(λ)

text: dim(λ)

text: ∼E

text: χλ(π)

text: tr(P(π)ρ

text: n)

text: π

text: To

text: compute

text: the

text: trace,

text: we

text: may

text: by

text: invariance

text: that

text: ρ

text: diag(η

text: η

text: Thus

text: d

text: n

text: ρ

text: n

text: η

text: a

text: a

text: a

text: a

text: ai

text: n

text: n

text: words∈

text: [d]n

text: D

text: D

text: Notice

text: that

text: if

text: we

text: let

text: denote

text: the

text: probability

text: distribution

text: on

text: [d]

text: in

text: which

text: (a)

text: η

text: then

text: the

text: η

text: D⊗

text: η

text: a

text: coeﬃcient

text: n

text: η

text: above

text: is

text: n(a

text: a

text: i.e.,

text: the

text: probability

text: that

text: a

text: random

text: length-n

text: word

text: Dai

text: n

text: drawn

text: i.i.d.

text: from

text: η

text: is

text: equal

text: to

text: an).

text: From

text: the

text: deﬁnition

text: of

text: P(π)

text: we

text: further

text: deduce

text: D⊗

text: P(π)ρ

text: n

text: η

text: an)

text: an

text: WeDim⊗

text: mediately

text: conclude

text: that

text: tr(P(π)ρ

text: n)

text: is

text: equal

text: to

text: the

text: sum

text: over

text: all

text: π-invariant

text: words

text: an)

text: of

text: n(a

text: a

text: Recalling

text: Deﬁnition

text: this

text: is

text: precisely

text: given

text: by

text: the

text: power

text: sum

text: polynomial

text: η

text: n

text: p

text: (η

text: η

text: Therefore

text: π

text: d

text: SWn(λ)

text: dim(λ)

text: E

text: [χ

text: (π)

text: p

text: (η

text: η

text: ρ

text: λ

text: π

text: d

text: π

text: Sn

text: and

text: the

text: proposition

text: now

text: follows

text: from

text: Theorem

text: For

text: the

text: purposes

text: of

text: the

text: testing

text: lower

text: bounds

text: in

text: this

text: paper,

text: the

text: case

text: of

text: greatest

text: interest

text: to

text: us

text: is

text: when

text: ρ

text: is

text: the

text: maximally

text: mixed

text: d-dimensional

text: state;

text: i.e.,

text: the

text: spectrum

text: of

text: ρ

text: is

text: the

text: uniform

text: d

text: d

text: d

text: distribution

text: Unif

text: This

text: is

text: also

text: by

text: far

text: the

text: most

text: well-studied

text: case

text: in

text: the

text: literature:

text: d

text: d

text: d

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ⊥ the orthogonality relations of representation theory, the innermost sum vanishes unless v and w ⊥ ∈ ∩ 1 are conjugate. Since w1 S(R2\) acts o∅nly on R1 ≥R2, it must have a ﬁxed poi|nt| (and therefore not be conjugate to v) unless R R = . Since r r , this can only happen if µ = r = r = t. 2 1 2 1 | | 1 2 We conclude that the inner expectation can only be nonzero in case µ = r = r = t. In this case we have Ct = r ! and (cid:96)\(w ) = 0, when(cid:104)ce (cid:104) (cid:88) 1 2 (cid:105)(cid:105) r1r2 2 1 ↓ · n r1 · · · ⊥ (21) = 1{ } E χ (w ) E p (x) χ (v)χ (w ) . r2=r1 dr1 w1∼Sr1 µ 1 v∼Sr1 v |ν|=r1 ν ν 1 Once again, the summation is 0 if v and w are not conjugate; otherwise it equals z . Further, 1 − ρ(w1) having chosen w , the probability that v is conjugate to w is precisely z 1 . Thus these factors 1 1 ρ(w1) cancel and we obtain ↓ ↓ · n r1 · · · n r1 · (21) = 1{ } E [χ (w ) p (x)] = 1{ } s (x), r2=r1 dr1 w1∼Sr1 µ 1 w1 r2=r1 dr1 µ completing the proof. − − 4.4 A formula for s (+1, 1, +1, 1, . . . ) µ For this formula we will need to recall the notion of the 2-quotient of a partition. This deﬁnition essentially encodes the ways in which a partition can be tiled by dominoes. Deﬁnition 4.10. Given a partition µ, a 2-hook in [µ] is a hook of length 2; i.e., a domino whose removal from [µ] results in a valid Young diagram. Deﬁnition 4.11. A partition µ is said to be balanced (or to have an empty 2-core) if [µ] can be reduced to the empty diagram by successive removal of 2-hooks. Deﬁnition 4.12. Given a partition µ we write [µ] (respectively, [µ] ) for the set of boxes (cid:3) ∈ (cid:3) even odd [µ] with even (respectively, odd) content c( ). (cid:96) | | Remark 4.13. It’s obvious from Deﬁnition 4.11 that if µ k is balanced then [µ] = k/2. In even fact, the converse also holds (this follows from, e.g., [JK81, Theorem 2.7.41]). 40 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: the

text: orthogonality

text: relations

text: of

text: representation

text: theory,

text: the

text: innermost

text: sum

text: vanishes

text: unless

text: v

text: and

text: w

text: are

text: conjugate.

text: Since

text: acts

text: o∅nly

text: on

font: unknown

text: it

text: must

text: have

text: a

text: ﬁxed

text: poi|nt|

text: (and

text: therefore

text: not

text: be

text: conjugate

text: to

text: v)

text: unless

text: R

text: R

text: Since

text: r

text: r

text: this

text: can

text: only

text: happen

text: if

text: µ

text: r

text: r

text: t.

text: We

text: conclude

text: that

text: the

text: inner

text: expectation

text: can

text: only

text: be

text: nonzero

text: in

text: case

text: µ

text: r

text: r

text: t.

text: In

text: this

text: case

text: we

text: have

text: Ct

text: r

text: and

text: n

text: E

text: χ

text: (w

text: E

text: p

text: (x)

text: χ

text: (v)χ

text: (w

text: µ

text: v

text: ν

text: ν

text: Once

text: again,

text: the

text: summation

text: is

text: if

text: v

text: and

text: w

text: are

text: not

text: conjugate;

text: otherwise

text: it

text: equals

text: z

text: Further,

text: having

text: chosen

text: w

text: the

text: probability

text: that

text: v

text: is

text: conjugate

text: to

text: w

text: is

text: precisely

text: z

text: Thus

text: these

text: factors

text: cancel

text: and

text: we

text: obtain

text: n

text: n

text: E

text: [χ

text: (w

text: p

text: (x)]

text: s

text: (x),

text: µ

text: µ

text: completing

text: the

text: proof.

text: A

text: formula

text: for

text: s

text: µ

text: For

text: this

text: formula

text: we

text: will

text: need

text: to

text: recall

text: the

text: notion

text: of

text: the

text: of

text: a

text: partition.

text: This

text: deﬁnition

text: essentially

text: encodes

text: the

text: ways

text: in

text: which

text: a

text: partition

text: can

text: be

text: tiled

text: by

text: dominoes.

text: Deﬁnition

text: Given

text: a

text: partition

text: µ,

text: a

text: in

text: [µ]

text: is

text: a

text: hook

text: of

text: length

text: i.e.,

text: a

text: domino

text: whose

text: removal

text: from

text: [µ]

text: results

text: in

text: a

text: valid

text: Young

text: diagram.

text: Deﬁnition

text: A

text: partition

text: µ

text: is

text: said

text: to

text: be

text: balanced

text: (or

text: to

text: have

text: an

text: empty

text: if

text: [µ]

text: can

text: be

text: reduced

text: to

text: the

text: empty

text: diagram

text: by

text: successive

text: removal

text: of

text: Deﬁnition

text: Given

text: a

text: partition

text: µ

text: we

text: write

text: [µ]

text: (respectively,

text: [µ]

text: for

text: the

text: set

text: of

text: boxes

text: even

text: odd

text: [µ]

text: with

text: even

text: (respectively,

text: odd)

text: content

text: c(

text: Remark

text: It’s

text: obvious

text: from

text: Deﬁnition

text: that

text: if

text: µ

text: k

text: is

text: balanced

text: then

text: [µ]

text: In

text: even

text: fact,

text: the

text: converse

text: also

text: holds

text: (this

text: follows

text: from,

text: e.g.,

text: Theorem

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: where (µ(0), µ(1)) is the 2-quotient of µ. Thus it suﬃces to show | | · ↑ · χµ(2, 2, . . . , 2) (d [µ]even) s (1, 1, . . . , 1) s (1, 1, . . . , 1) = · (22) µ(0) µ(1) (k/2)! 2k/2 assuming µ is balanced. Applying Proposition 2.11, the left-hand side of (22) is (d↑µ(0)) · (d↑µ(1)) · dim µ(0) · dim µ(1) 2 2| | · | | . µ(0) ! µ(1) ! (cid:18) (cid:19) Next, we appeal to [RZ12, formula (2.2)], which states | | · µ /2 · · χ (2, 2, . . . , 2) = σ | | | | dim µ(0) dim µ(1), µ µ µ(0) , µ(1) ∈ {± } where σ 1 is a certain sign. Thus to verify (22) it remains to show µ ↑ (d↑µ(0)) · (d↑µ(1)) = d [µ]even . (23) 2 2 2k/2 But this follows immediately from Lemma 4.17. 4.5 Wrapping up the lower bound In this section we complete the proof of Theorem 4.2. We begin by applying Corollary 4.5 with − − x = (+2(cid:15), 2(cid:15), +2(cid:15), 2(cid:15), . . . ). Using Theorem 4.18 and the homogeneity of Schur polynomials, we obtain the following after a few manipulations: ≤ ≤ Theorem 4.19. For d even and 0 (cid:15) 1, (cid:88) 2 (cid:16) (cid:88) (cid:17) ↑ ↓ − · 1 · d [µ]even dχ2(SWnP(cid:15)d, SWnd) = n k(2(cid:15))2kd k k!!2 (cid:96) χµ(2, . . . , 2)2 d↑[µ]odd . (24) k=2,4,6,... µ k bala≤nced 0<(cid:96)(µ) d To estimate this quantity we will use the following very crude bound: ∈ (cid:96) ≤ Proposition 4.20. Let d Z+ and let µ k be balanced, with 0 < (cid:96)(µ) d. Then ↑ d [µ]even ≤ ↑ 2k/2. (25) d [µ]odd Proof. Fix any domino-tiling for µ. Each of the k/2 dominoes contains one cell of even content c | − | ≤ e and one cell of odd content c , with c c = 1. Thus each contributes a factor of d+ce 2 = 2 ↑ ↑ o e o d+co 1 to (d [µ]even)/(d [µ]odd). 43 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: where

text: is

text: the

text: of

text: µ.

text: Thus

text: it

text: suﬃces

text: to

text: show

label: equation

text: (d

text: [µ]even)

text: s

text: s

text: assuming

text: µ

text: is

text: balanced.

text: Applying

text: Proposition

text: the

text: left-hand

text: side

text: of

text: is

text: dim

text: dim

text: Next,

text: we

text: appeal

text: to

text: formula

text: which

text: states

text: µ

text: χ

text: σ

text: dim

text: dim

text: µ

text: µ

text: where

text: σ

text: is

text: a

text: certain

text: sign.

text: Thus

text: to

text: verify

text: it

text: remains

text: to

text: show

text: µ

text: d

text: [µ]even

text: But

text: this

text: follows

text: immediately

text: from

text: Lemma

text: Wrapping

text: up

text: the

text: lower

text: bound

text: In

text: this

text: section

text: we

text: complete

text: the

text: proof

text: of

text: Theorem

text: We

text: begin

text: by

text: applying

text: Corollary

text: with

text: x

text: Using

text: Theorem

text: and

text: the

text: homogeneity

text: of

text: Schur

text: polynomials,

text: we

text: obtain

text: the

text: following

text: after

text: a

text: few

text: manipulations:

text: Theorem

text: For

text: d

text: even

text: and

text: d

text: [µ]even

text: SWnd)

text: n

text: k

text: d↑[µ]odd

text: µ

text: k

text: bala≤nced

text: d

text: To

text: estimate

text: this

text: quantity

text: we

text: will

text: use

text: the

text: following

text: very

text: crude

text: bound:

text: Proposition

text: Let

text: d

text: Z+

text: and

text: let

text: µ

text: k

text: be

text: balanced,

text: with

text: d.

text: Then

text: d

text: [µ]even

text: d

text: [µ]odd

text: Proof.

text: Fix

text: any

text: domino-tiling

text: for

text: µ.

text: Each

text: of

text: the

text: dominoes

text: contains

text: one

text: cell

text: of

text: even

text: content

text: c

text: e

text: and

text: one

text: cell

text: of

text: odd

text: content

text: c

text: with

text: c

text: c

text: Thus

text: each

text: contributes

text: a

text: factor

text: of

text: d+ce

text: o

text: e

text: o

text: d+co

text: to

text: (d

text: [µ]even)/(d

text: [µ]odd).

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: | | (cid:54)≥ | ∗ | ≤ Finally, when λ is usual and L (λ)2 1, it follows that necessarily L∞(λ) 2, in light of C≤ Lemma 5.3 and the fact that 201 1. As noted earlier, the r -analogue of Lemma 5.3 holds, and ω3 + hence we may draw the same conclusion concerning L+ (λ)2. C Finally we are ready to complete the proof of Theorem 5.11. We begin with d (SWn, SWn ) ≤ 1 Pr [λ not usual+] + 1 Pr [λ not usual+(cid:88)] (cid:12)(cid:12) (cid:12)(cid:12) TV r r+ 2 λ∼SWn 2 λ∼SWn (cid:12) (cid:12) r r+ 1 − + SWn [λ] SWn[λ] . 2 r+ r usual+ λ We can bound the ﬁrst two terms above using Lemma 5.15. Indeed there is room to spare, as the bound we get is the square of what we can tolerate. Thus it remains to bound the third term by · exp(O(C2.01)) 1 . For it we use (cid:34) (cid:12) (cid:12)(cid:35) ω2(cid:88) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) − (cid:104) · − SWn[λ] (cid:105) SWn [λ] SWn[λ] = E 1{ } 1 r usual+ λ r+ r λ∼SWnr+ λ usual+ SWnr+[λ] · | − | = E 1{ } 1 exp(u(λ)) (54) ∼ λ usual+ λ SWn r+ (cid:32) (cid:33) (cid:18) (cid:19) where SWn[λ] 1 − n ∗ u(λ) = ln r = n ln 1 + + L∞(λ), (55) SWn [λ] r r + 1 r+ 2 the last equality holding from (31) (see also the sentence after (33)) under the assumption that λ is usual (which we can indeed assume, since we’re multiplying against 1{ }). As λ usual+ we noted after (33), the ﬁrst two quantities in (55) sum to a positive quantity not exceeding ≤ n 1 . Furthermore, because of the presence of the usual+-indicator in (54) we may assume 12r3 ω2 | ∗ | ≤ ≤ ≤ i|n −analyzing| ≤(55|) |that L∈∞(−λ) 2. Th(cid:20)us we may u(cid:18)se the bound u(cid:19)(λ(cid:21)) 2 + ω12 2.01. Since 1 exp(u) 4 u for u [ 2.01, 2.01], we may conclude that ≤ · 1 | ∗ | (54) 4 E 1{ } + L∞(λ) . λ∼SWn λ usual+ ω2 r+ Thus to complete the proof of Theorem 5.11 it remains to show | ∗ | ≤ · 1 E [ L∞(λ) ] exp(O(C2.01)) . λ∼SWn ω2 r+ ∗ By the r -analogue of Lemma 5.3, it suﬃces to prove this with L+ (λ) in place of L∞(λ), because (cid:28)+ (cid:2) (cid:3) (cid:114) (cid:2) (cid:3) C 201/ω3 exp(O(C2.01))/ω2. But ﬁnally | | ≤ ≤ · 1 E L+ (λ) E L+ (λ)2 exp(O(C2.01)) , λ∼SWn C λ∼SWn C ω2 r+ r+ using Cauchy–Schwarz and (53). The proof of Theorem 5.11—and hence also the testing lower bound (27)—is therefore complete. 56 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Finally,

text: when

text: λ

text: is

text: usual

text: and

text: L

text: it

text: follows

text: that

text: necessarily

text: L∞(λ)

text: in

text: light

text: of

text: C≤

text: Lemma

text: and

text: the

text: fact

text: that

text: As

text: noted

text: earlier,

text: the

text: r

text: -analogue

text: of

text: Lemma

text: holds,

text: and

text: ω3

text: hence

text: we

text: may

text: draw

text: the

text: same

text: conclusion

text: concerning

text: L+

text: C

text: Finally

text: we

text: are

text: ready

text: to

text: complete

text: the

text: proof

text: of

text: Theorem

text: We

text: begin

text: with

text: d

text: (SWn,

text: SWn

text: Pr

text: [λ

text: not

text: usual+]

text: Pr

text: [λ

text: not

text: TV

text: r

text: r+

text: λ∼SWn

text: λ∼SWn

text: r

text: r+

text: SWn

text: [λ]

text: SWn[λ]

text: r+

text: r

text: usual+

text: λ

text: We

text: can

text: bound

text: the

text: ﬁrst

text: two

text: terms

text: above

text: using

text: Lemma

text: Indeed

text: there

text: is

text: room

text: to

text: spare,

text: as

text: the

text: bound

text: we

text: get

text: is

text: the

text: square

text: of

text: what

text: we

text: can

text: tolerate.

text: Thus

text: it

text: remains

text: to

text: bound

text: the

text: third

text: term

text: by

text: For

text: it

text: we

text: use

text: SWn[λ]

text: SWn

text: [λ]

text: SWn[λ]

text: E

text: r

text: usual+

text: λ

text: r+

text: r

text: λ∼SWnr+

text: λ

text: usual+

text: SWnr+[λ]

text: E

text: exp(u(λ))

text: λ

text: usual+

text: λ

text: SWn

text: r+

text: where

text: SWn[λ]

text: n

text: u(λ)

text: ln

text: r

text: n

text: ln

text: L∞(λ),

text: SWn

text: [λ]

text: r

text: r

text: r+

text: the

text: last

text: equality

text: holding

text: from

text: (see

text: also

text: the

text: sentence

text: after

text: under

text: the

text: assumption

text: that

text: λ

text: is

text: usual

text: (which

text: we

text: can

text: indeed

text: assume,

text: since

text: we’re

text: multiplying

text: against

text: As

text: λ

text: usual+

text: we

text: noted

text: after

text: the

text: ﬁrst

text: two

text: quantities

text: in

text: sum

text: to

text: a

text: positive

text: quantity

text: not

text: exceeding

text: n

text: Furthermore,

text: because

text: of

text: the

text: presence

text: of

text: the

text: usual+-indicator

text: in

text: we

text: may

text: assume

text: ω2

text: i|n

text: −analyzing|

text: |that

text: L∈∞(−λ)

text: we

text: may

text: the

text: bound

text: Since

text: exp(u)

text: u

text: for

text: u

text: we

text: may

text: conclude

text: that

text: E

text: L∞(λ)

text: λ∼SWn

text: λ

text: usual+

text: ω2

text: r+

text: Thus

text: to

text: complete

text: the

text: proof

text: of

text: Theorem

text: it

text: remains

text: to

text: show

text: E

text: L∞(λ)

text: λ∼SWn

text: ω2

text: r+

text: By

text: the

text: r

text: -analogue

text: of

text: Lemma

text: it

text: suﬃces

text: to

text: prove

text: this

text: with

text: L+

text: (λ)

text: in

text: place

text: of

text: L∞(λ),

text: because

text: C

text: But

text: ﬁnally

text: E

text: L+

text: (λ)

text: E

text: L+

text: λ∼SWn

text: C

text: λ∼SWn

text: C

text: ω2

text: r+

text: r+

text: using

text: Cauchy–Schwarz

text: and

text: The

text: proof

text: of

text: Theorem

text: hence

text: also

text: the

text: testing

text: lower

text: bound

text: therefore

text: complete.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 6 Quantum rank testing 6.1 Testers with one-sided error In this section, we prove the ﬁrst part of Theorem 1.11, that Θ(r2/(cid:15)) copies are necessary and suﬃcient to test whether or not a state has rank r with one-sided error. We will show this by analyzing the following algorithm. ⊗ Rank Tester. Given ρ n, ∼ 1. Sample λ SWn. ρ ≤ 2. Accept if (cid:96)(λ) r. Reject otherwise. Our primary tool in analyzing this tester will be the RSK correspondence. Suppose ρ’s nonzero { } D eigenvalues are η = η , . . . , η , and let be the distribution over [d] induced by η. By Re- 1 d ∼ D⊗ mark 2.24, SWn has the same distribution as the process which ﬁrst samples w n and outputs ρ λ = RSK(w). Write LDS(w) for the length of the longest strongly decreasing subsequence in w. By Theorem 2.14, (cid:96)(λ) = LDS(w). The key property we will need of the Rank Tester is the following: Proposition 6.1. The Rank Tester is the optimal algorithm for testing whether or not a state has rank r with one-sided error. ≤ Proof. To show this, we need to show (i) that every λ satisfying (cid:96)(λ) r occurs with nonzero probability in SWn for some ρ of rank r and (ii) that no λ satisfying (cid:96)(λ) > r occurs in SWn for ρ ρ any ρ of rank r. The ﬁrst follows because if ρ has r nonzero eigenvalues, then the word (cid:124) (cid:123)(cid:122) (cid:125) (cid:124) (cid:123)(cid:122) (cid:125) (cid:124) (cid:123)(cid:122) (cid:125) − − w := r, . . . , r, (r 1), . . . , (r 1), . . . , 1, . . . , 1 λr letters λr−1 letters λ1 letters D⊗ occurs in n with nonzero probability. It is easy to check that λ = RSK(w). To show that (ii) holds, if ρ is rank r, then η has at most r nonzero entries. Thus, any word w D⊗ ≤ in the support of n will always satisfy LDS(w) r because w will contain at most r distinct letters. As (cid:96)(λ) = LDS(w), we are done. As a result of Proposition 6.1, Theorem 1.11 follows from the following lemma. Lemma 6.2. The Rank Tester tests whether or not a state has rank r with Θ(r2/(cid:15)) copies. Proof. If ρ is (cid:15)-far from having rank r, then η is (cid:15)-far in TV distance from having support size r. Thus, we can show the lemma by showing the following two facts about probability distributions. D (i) For every probability distribution = (p , . . . , p ) which is (cid:15)-far from having support size r, ∼ D⊗ 1 ≥ d a random word w n satisﬁes LDS(w) r + 1 with probability at least 2/3 for some n = O(r2/(cid:15)). D (ii) There exists an integer d and a probability distribution = (p , . . . , p ) which is (cid:15)-far from ∼ D⊗ 1 d≤ having support size r such that, for a random word w n, LDS(w) r with probability greater than 1/3 whenever n = o(r2/(cid:15)). 57 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: section

text: Quantum

text: rank

text: testing

text: Testers

text: with

text: one-sided

text: error

text: In

text: this

text: section,

text: we

text: prove

text: the

text: ﬁrst

text: part

text: of

text: Theorem

text: that

text: copies

text: are

text: necessary

text: and

text: suﬃcient

text: to

text: test

text: whether

text: or

text: not

text: a

text: state

text: has

text: rank

text: r

text: with

text: one-sided

text: error.

text: We

text: will

text: show

text: this

text: by

text: analyzing

text: the

text: following

text: algorithm.

text: Rank

text: Tester.

text: Given

text: ρ

text: n,

label: list

text: Sample

text: λ

text: SWn.

text: ρ

text: Accept

text: if

text: r.

text: Reject

text: otherwise.

text: Our

text: primary

text: tool

text: in

text: analyzing

text: this

text: tester

text: will

text: be

text: the

text: RSK

text: correspondence.

text: Suppose

text: ρ’s

text: nonzero

text: D

text: eigenvalues

text: are

text: η

text: η

text: η

text: and

text: let

text: be

text: the

text: distribution

text: over

text: [d]

text: induced

text: by

text: η.

text: By

text: Re-

text: d

text: D⊗

text: mark

text: SWn

text: has

text: the

text: same

text: distribution

text: as

text: the

text: process

text: which

text: ﬁrst

text: samples

text: w

text: n

text: and

text: outputs

text: ρ

text: λ

text: RSK(w).

text: Write

text: LDS(w)

text: for

text: the

text: length

text: of

text: the

text: longest

text: strongly

text: decreasing

text: subsequence

text: in

text: w.

text: By

text: Theorem

text: LDS(w).

text: The

text: key

text: property

text: we

text: will

text: need

text: of

text: the

text: Rank

text: Tester

text: is

text: the

text: following:

text: Proposition

text: The

text: Rank

text: Tester

text: is

text: the

text: optimal

text: algorithm

text: for

text: testing

text: whether

text: or

text: not

text: a

text: state

text: has

text: rank

text: r

text: with

text: one-sided

text: error.

text: Proof.

text: To

text: show

text: this,

text: we

text: need

text: to

text: show

text: (i)

text: that

text: every

text: λ

text: satisfying

text: r

text: occurs

text: with

text: nonzero

text: probability

text: in

text: SWn

text: for

text: some

text: ρ

text: of

text: rank

text: r

text: and

text: (ii)

text: that

text: no

text: λ

text: satisfying

text: r

text: occurs

text: in

text: SWn

text: for

text: ρ

text: ρ

text: any

text: ρ

text: of

text: rank

text: r.

text: The

text: ﬁrst

text: follows

text: because

text: if

text: ρ

text: has

text: r

text: nonzero

text: eigenvalues,

text: then

text: the

text: word

text: w

text: r,

text: r,

text: (r

text: (r

text: λr

text: letters

text: λr−1

text: letters

text: λ1

text: letters

text: D⊗

text: occurs

text: in

text: n

text: with

text: nonzero

text: probability.

text: It

text: is

text: easy

text: to

text: check

text: that

text: λ

text: RSK(w).

text: To

text: show

text: that

text: (ii)

text: holds,

text: if

text: ρ

text: is

text: rank

text: r,

text: then

text: η

text: has

text: at

text: most

text: r

text: nonzero

text: entries.

text: Thus,

text: any

text: word

text: w

text: D⊗

text: in

text: the

text: support

text: of

text: n

text: will

text: always

text: satisfy

text: LDS(w)

text: r

text: because

text: w

text: will

text: contain

text: at

text: most

text: r

text: distinct

text: letters.

text: As

text: LDS(w),

text: we

text: are

text: done.

text: As

text: a

text: result

text: of

text: Proposition

text: Theorem

text: follows

text: from

text: the

text: following

text: lemma.

text: Lemma

text: The

text: Rank

text: Tester

text: tests

text: whether

text: or

text: not

text: a

text: state

text: has

text: rank

text: r

text: with

text: copies.

text: Proof.

text: If

text: ρ

text: is

text: from

text: having

text: rank

text: r,

text: then

text: η

text: is

text: in

text: TV

text: distance

text: from

text: having

text: support

text: size

text: r.

text: Thus,

text: we

text: can

text: show

text: the

text: lemma

text: by

text: showing

text: the

text: following

text: two

text: facts

text: about

text: probability

text: distributions.

text: D

text: (i)

text: For

text: every

text: probability

text: distribution

text: (p

text: p

text: which

text: is

text: from

text: having

text: support

text: size

text: r,

text: D⊗

text: d

text: a

text: random

text: word

text: w

text: n

text: satisﬁes

text: LDS(w)

text: r

text: with

text: probability

text: at

text: least

text: for

text: some

text: n

text: D

text: (ii)

text: There

text: exists

text: an

text: integer

text: d

text: and

text: a

text: probability

text: distribution

text: (p

text: p

text: which

text: is

text: from

text: D⊗

text: d≤

text: having

text: support

text: size

text: r

text: such

text: that,

text: for

text: a

text: random

text: word

text: w

text: n,

text: LDS(w)

text: r

text: with

text: probability

text: greater

text: than

text: whenever

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Proof of statement (i): We will need the following concentration bound for sums of geometric random variables. (cid:0) (cid:1) Proposition 6.3 ([Bro]). Write X = X + . . . + X , where the X ’s are iid geometric random 1 n ≤ − i − variables with expectation µ. For any k > 1, Pr[X > knµ] exp 1kn(1 1/k)2 . 2 We note that Proposition 6.3 also holds with the weaker hypothesis that the X ’s are independent i (and not necessarily identically distributed), each with expectation at most µ. ≥ ≥ ≥ We may assume that p . . . p . We will split into two cases, handled below: (1) p (cid:15)/4r 1 d r+1 and (2) p < (cid:15)/4r. r+1 ≥ ∼ (1) Because the probabilities are sorted, p , . . . , p (cid:15)/4r. For the inﬁnite random word w D⊗∞ 1 r+1 , consider the number of letters one has to traverse through before ﬁnding (r+1), r, . . . , 1 as a subsequence. This number is distributed as X = X +. . .+X , where X is a geometric r+1 1 i random variable with success probability p . i ≥ ≤ ∈ By assumption, p (cid:15)/4r, and therefore E X 4r/(cid:15), for each i [r+1]. By Proposition 6.3, i i ∼ D⊗ X is at most 24r2/(cid:15) with probability at least 2/3. Thus, if n = 24r2/(cid:15), then w n has a strictly decreasing subsequence of size r + 1 with high probability. { } (2) Because the probabilities are sorted, p , . . . , p < (cid:15)/4r. Place the letters from r +1, . . . , d r+1 d into buckets as follows: starting from letter (r + 1) and proceeding in order, add each letter to the current bucket until it contains at least (cid:15)/4r weight. At this point, move to the next bucket and repeat this process starting with the current letter until all letters have been bucketed. ≤ Because these letters have weight (cid:15)/4r, each bucket has total weight in the interval [(cid:15)/4r, (cid:15)/2r) (except possibly the ﬁnal bucket). There must be at least 2r + 1 buckets with P nonzero total weight, as otherwise p + . . . + p < (cid:15), contradicting the fact that is (cid:15)-far r+1 d ≥ from having support size r. This gives us at least 2r r + 1 buckets each of which contains at least (cid:15)/4r total weight. Now we can use an argument similar to case (1) to show that when n = 24r2/(cid:15), a random ∼ D⊗ ≥ w n will with probability 2/3 have a strictly decreasing subsequence in which the ﬁrst letter comes from bucket r + 1, the second letter comes from bucket r, and so on (ending in a letter from the ﬁrst bucket). This is a strictly decreasing subsequence of size r + 1. (cid:18) (cid:19) (cid:29) Proof of statement (ii): For d r, deﬁne the probability distribution P − 2(cid:15) 2(cid:15) = 1 2(cid:15), − , . . . , − . (cid:101) d 1 d 1 (cid:29) P ∈ Becau(cid:101)se d r, is (cid:15)-far(cid:101)from having support size r. For a string w [d]n, let w be the substring of w formed by deleting all occurrences of the l(cid:101)etter “1” from w. It is easy to see that ≤ ≤ LDS(w) LDS(cid:101)(w) LDS(w) + 1. ∼ P⊗ For a randomly drawn w n, let us condition on w having a certain ﬁxed length m. The value of LDS(w) is distributed as the length of the longest decreasing subsequence in a uniformly − (cid:48) ∼ random word draw√n from [d 1]m. By Theorem 2.14, this is distributed as λ for λ SWm− . (cid:100) (cid:101) (cid:48) ≥ ≥ 1 (cid:48) d 1 Setting B = 100 m , let us show that Pr[λ B] is small. If B d, then surely λ < B ∼ (cid:18)1 (cid:19) − 1 always, as λ SWm− will always have height at most d 1. On the other hand, if B < d, then by d 1 Proposition 2.31, (cid:48) ≥ ≤ 2e2m B ≤ 2e2 Pr[λ B] . 1 B2 10000 58 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof

text: of

text: statement

text: (i):

text: We

text: will

text: need

text: the

text: following

text: concentration

text: bound

text: for

text: sums

text: of

text: geometric

text: random

text: variables.

text: Proposition

text: ([Bro]).

text: Write

text: X

text: X

text: X

text: where

text: the

text: X

text: ’s

text: are

text: iid

text: geometric

text: random

text: n

text: i

text: variables

text: with

text: expectation

text: µ.

text: For

text: any

text: k

text: Pr[X

text: knµ]

text: exp

text: We

text: note

text: that

text: Proposition

text: also

text: holds

text: with

text: the

text: weaker

text: hypothesis

text: that

text: the

text: X

text: ’s

text: are

text: independent

text: i

text: (and

text: not

text: necessarily

text: identically

text: distributed),

text: each

text: with

text: expectation

text: at

text: most

text: µ.

text: We

text: may

text: assume

text: that

text: p

text: p

text: We

text: will

text: split

text: into

text: two

text: cases,

text: handled

text: below:

text: p

text: d

text: and

text: p

text: Because

text: the

text: probabilities

text: are

text: sorted,

text: p

text: p

text: For

text: the

text: inﬁnite

text: random

text: word

text: w

text: D⊗∞

text: consider

text: the

text: number

text: of

text: letters

text: one

text: has

text: to

text: traverse

text: through

text: before

text: ﬁnding

text: r,

text: as

text: a

text: subsequence.

text: This

text: number

text: is

text: distributed

text: as

text: X

text: X

text: .+X

text: where

text: X

text: is

text: a

text: geometric

text: i

text: random

text: variable

text: with

text: success

text: probability

text: p

text: i

text: By

text: assumption,

text: p

text: and

text: therefore

text: E

text: X

text: for

text: each

text: i

text: By

text: Proposition

text: i

text: i

text: D⊗

text: X

text: is

text: at

text: most

text: with

text: probability

text: at

text: least

text: Thus,

text: if

text: n

text: then

text: w

text: n

text: has

text: a

text: strictly

text: decreasing

text: subsequence

text: of

text: size

text: r

text: with

text: high

text: probability.

text: Because

text: the

text: probabilities

text: are

text: sorted,

text: p

text: p

text: Place

text: the

text: letters

text: from

text: r

text: d

text: d

text: into

text: buckets

text: as

text: follows:

text: starting

text: from

text: letter

text: (r

text: and

text: proceeding

text: in

text: order,

text: add

text: each

text: letter

text: to

text: the

text: current

text: bucket

text: until

text: it

text: contains

text: at

text: least

text: weight.

text: At

text: this

text: point,

text: move

text: to

text: the

text: next

text: bucket

text: and

text: repeat

text: this

text: process

text: starting

text: with

text: the

text: current

text: letter

text: until

text: all

text: letters

text: have

text: been

text: bucketed.

text: Because

text: these

text: letters

text: have

text: weight

text: each

text: bucket

text: has

text: total

text: weight

text: in

text: the

text: interval

text: (except

text: possibly

text: the

text: ﬁnal

text: bucket).

text: There

text: must

text: be

text: at

text: least

text: buckets

text: with

text: P

text: nonzero

text: total

text: weight,

text: as

text: otherwise

text: p

text: p

text: contradicting

text: the

text: fact

text: that

text: is

text: d

text: from

text: having

text: support

text: size

text: r.

text: This

text: gives

text: us

text: at

text: least

text: r

text: buckets

text: each

text: of

text: which

text: contains

text: at

text: least

text: total

text: weight.

text: Now

text: we

text: can

text: use

text: an

text: argument

text: similar

text: to

text: case

text: to

text: show

text: that

text: when

text: n

text: a

text: random

text: D⊗

text: w

text: n

text: will

text: with

text: probability

text: have

text: a

text: strictly

text: decreasing

text: subsequence

text: in

text: which

text: the

text: ﬁrst

text: letter

text: comes

text: from

text: bucket

text: r

text: the

text: second

text: letter

text: comes

text: from

text: bucket

text: r,

text: and

text: so

text: on

text: (ending

text: in

text: a

text: letter

text: from

text: the

text: ﬁrst

text: bucket).

text: This

text: is

text: a

text: strictly

text: decreasing

text: subsequence

text: of

text: size

text: r

text: Proof

text: of

text: statement

text: (ii):

text: For

text: d

text: r,

text: deﬁne

text: the

text: probability

text: distribution

text: P

text: d

text: d

text: P

text: d

text: r,

text: is

text: having

text: support

text: size

text: r.

text: For

text: a

text: string

text: w

text: [d]n,

text: let

text: w

text: be

text: the

text: substring

text: of

text: w

text: formed

text: by

text: deleting

text: all

text: occurrences

text: of

text: the

text: “1”

text: from

text: w.

text: It

text: is

text: easy

text: to

text: see

text: that

text: LDS(w)

text: LDS(w)

text: P⊗

text: For

text: a

text: randomly

text: drawn

text: w

text: n,

text: let

text: us

text: condition

text: on

text: w

text: having

text: a

text: certain

text: ﬁxed

text: length

text: m.

text: The

text: value

text: of

text: LDS(w)

text: is

text: distributed

text: as

text: the

text: length

text: of

text: the

text: longest

text: decreasing

text: subsequence

text: in

text: a

text: uniformly

text: random

text: word

text: draw√n

text: from

text: [d

text: By

text: Theorem

text: this

text: is

text: distributed

text: as

text: λ

text: for

text: λ

text: SWm−

text: d

text: Setting

text: B

text: m

text: let

text: us

text: show

text: that

text: Pr[λ

text: B]

text: is

text: small.

text: If

text: B

text: d,

text: then

text: surely

text: λ

text: B

text: always,

text: as

text: λ

text: SWm−

text: will

text: always

text: have

text: height

text: at

text: most

text: d

text: On

text: the

text: other

text: hand,

text: if

text: B

text: d,

text: then

text: by

text: d

text: Proposition

text: B

text: Pr[λ

text: B]

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: such paradoxes, but still fail to explain some human behavioral patterns. A par- ticularly illustrative example of such behavior is called the decoy eﬀect [13], in which the introduction of a dominated option changes the preference among the undominated ones. While the decoy eﬀect has been investigated in the psychol- ogy [6, 26] and economics literature [3, 22], we are unaware of any axiomatic treatment of it. To address this, we introduce a criterion called safety as the basis for a maximin safety decision rule. 1 Safety serves as a dual to regret that quantiﬁes distance from a worst outcome, much as regret quantiﬁes proximity to a best outcome. Maximin safety also satisﬁes familiar properties common to maximin utility and minimax regret, and hence also resolves the Ellsberg para- dox. Moreover, maximin safety accommodates observed preferences that are incompatible with minimax regret and maximin utility. We demonstrate how safety-seeking behavior can produce the decoy eﬀect, and show how maximin safety can explain it. We also extend Stoye’s [24] axiomatizations of standard decision rules to include maximin safety, thus allowing a comparison between maximin safety and state-of-the-art decision rules. 1.1 Relative Preferences and Regret It is not hard to imagine situations in which performance relative to other possible outcomes is more important than absolute performance. Consider, for example, a group of duck hunters surprised by a hungry bear [5, 4]. The hunters all attempt to escape by running in the same direction while the slowest one despairs: “this is hopeless, we can never outrun the bear.” The hunter in front of him snickers, “I don’t need to outrun the bear, I just need to outrun you.” Whether the prospect is being picked from a group of peers for a date [2], win- ning a gold medal, or obtaining an ‘A’ in a class, success is often measured by relative performance, rather than by an absolute standard. One such preference for relative performance is embodied in the well-known decision theoretical con- cept of regret [20, 17]. While psychological literature on regret focuses on the bad feelings that occur after a choice leads to an inferior outcome, some also considers that anticipation of such negative emotions may inﬂuence the choice itself [22, 16, 19]. In this paper, we assume that uncertainty is captured by a set of possible worlds, one of which is the true state of the world. Regret is a measure of distance between the value of a considered outcome and the value of the best possible outcome, under a given state. This leads to an important property that is always true for regret – the introduction of a dominated option does not change the regrets of the existing options. We will refer to this property as independence of dominated alternatives (IDA). Those who believe in regret avoidance may think that this property is perfectly reasonable. For example, suppose you have a $10 bill and you can either buy a $10 lottery ticket, or two $5 lottery tickets. Most would agree that your choice should not be aﬀected by a dominated third option, “burning the $10 bill”. Other standard decision 1This decision rule has been mentioned in passing, inside a proof by Hayashi [11], where it was referred to as ‘maximin joy’. We use the term ‘safety’ rather than ‘joy’ to avoid confusion with the concept called ‘joy of winning’ in [11]. 2 ##LTLine##

text: such

text: paradoxes,

text: but

text: still

text: fail

text: to

text: explain

text: some

text: human

text: behavioral

text: patterns.

text: A

text: par-

text: ticularly

text: illustrative

text: example

text: of

text: such

text: behavior

text: is

text: called

text: the

text: decoy

text: eﬀect

text: in

text: which

text: the

text: introduction

text: of

text: a

text: dominated

text: option

text: changes

text: the

text: preference

text: among

text: the

text: undominated

text: ones.

text: While

text: the

text: decoy

text: eﬀect

text: has

text: been

text: investigated

text: in

text: the

text: psychol-

text: ogy

text: and

text: economics

text: literature

text: we

text: are

text: unaware

text: of

text: any

text: axiomatic

text: treatment

text: of

text: it.

text: To

text: address

text: this,

text: we

text: introduce

text: a

text: criterion

text: called

text: safety

text: as

text: the

text: basis

text: for

text: a

text: maximin

text: safety

text: decision

text: rule.

text: Safety

text: serves

text: as

text: a

text: dual

text: to

text: regret

text: that

text: quantiﬁes

text: distance

text: from

text: a

text: worst

text: outcome,

text: much

text: as

text: regret

text: quantiﬁes

text: proximity

text: to

text: a

text: best

text: outcome.

text: Maximin

text: safety

text: also

text: satisﬁes

text: familiar

text: properties

text: common

text: to

text: maximin

text: utility

text: and

text: minimax

text: regret,

text: and

text: hence

text: also

text: resolves

text: the

text: Ellsberg

text: para-

text: dox.

text: Moreover,

text: maximin

text: safety

text: accommodates

text: observed

text: preferences

text: that

text: are

text: incompatible

text: with

text: minimax

text: regret

text: and

text: maximin

text: utility.

text: We

text: demonstrate

text: how

text: safety-seeking

text: behavior

text: can

text: produce

text: the

text: decoy

text: eﬀect,

text: and

text: show

text: how

text: maximin

text: safety

text: can

text: explain

text: it.

text: We

text: also

text: extend

text: Stoye’s

text: axiomatizations

text: of

text: standard

text: decision

text: rules

text: to

text: include

text: maximin

text: safety,

text: thus

text: allowing

text: a

text: comparison

text: between

text: maximin

text: safety

text: and

text: state-of-the-art

text: decision

text: rules.

text: Relative

text: Preferences

text: and

text: Regret

text: It

text: is

text: not

text: hard

text: to

text: imagine

text: situations

text: in

text: which

text: performance

text: relative

text: to

text: other

text: possible

text: outcomes

text: is

text: more

text: important

text: than

text: absolute

text: performance.

text: Consider,

text: for

text: example,

text: a

text: group

text: of

text: duck

text: hunters

text: surprised

text: by

text: a

text: hungry

text: bear

text: The

text: hunters

text: all

text: attempt

text: to

text: escape

text: by

text: running

text: in

text: the

text: same

text: direction

text: while

text: the

text: slowest

text: one

text: despairs:

text: “this

text: is

text: hopeless,

text: we

text: can

text: never

text: outrun

text: the

text: bear.”

text: The

text: hunter

text: in

text: front

text: of

text: him

text: snickers,

text: “I

text: don’t

text: need

text: to

text: outrun

text: the

text: bear,

text: I

text: just

text: need

text: to

text: outrun

text: you.”

text: Whether

text: the

text: prospect

text: is

text: being

text: picked

text: from

text: a

text: group

text: of

text: peers

text: for

text: a

text: date

text: win-

text: ning

text: a

text: gold

text: medal,

text: or

text: obtaining

text: an

text: ‘A’

text: in

text: a

text: class,

text: success

text: is

text: often

text: measured

text: by

text: relative

text: performance,

text: rather

text: than

text: by

text: an

text: absolute

text: standard.

text: One

text: such

text: preference

text: for

text: relative

text: performance

text: is

text: embodied

text: in

text: the

text: well-known

text: decision

text: theoretical

text: con-

text: cept

text: of

text: regret

text: While

text: psychological

text: literature

text: on

text: regret

text: focuses

text: on

text: the

text: bad

text: feelings

text: that

text: occur

text: after

text: a

text: choice

text: leads

text: to

text: an

text: inferior

text: outcome,

text: some

text: also

text: considers

text: that

text: anticipation

text: of

text: such

text: negative

text: emotions

text: may

text: inﬂuence

text: the

text: choice

text: itself

text: In

text: this

text: paper,

text: we

text: assume

text: that

text: uncertainty

text: is

text: captured

text: by

text: a

text: set

text: of

text: possible

text: worlds,

text: one

text: of

text: which

text: is

text: the

text: true

text: state

text: of

text: the

text: world.

text: Regret

text: is

text: a

text: measure

text: of

text: distance

text: between

text: the

text: value

text: of

text: a

text: considered

text: outcome

text: and

text: the

text: value

text: of

text: the

text: best

text: possible

text: outcome,

text: under

text: a

text: given

text: state.

text: This

text: leads

text: to

text: an

text: important

text: property

text: that

text: is

text: always

text: true

text: for

text: regret

text: the

text: introduction

text: of

text: a

text: dominated

text: option

text: does

text: not

text: change

text: the

text: regrets

text: of

text: the

text: existing

text: options.

text: We

text: will

text: refer

text: to

text: this

text: property

text: as

text: independence

text: of

text: dominated

text: alternatives

text: (IDA).

text: Those

text: who

text: believe

text: in

text: regret

text: avoidance

text: may

text: think

text: that

text: this

text: property

text: is

text: perfectly

text: reasonable.

text: For

text: example,

text: suppose

text: you

text: have

text: a

text: bill

text: and

text: you

text: can

text: either

text: buy

text: a

text: lottery

text: ticket,

text: or

text: two

text: lottery

text: tickets.

text: Most

text: would

text: agree

text: that

text: your

text: choice

text: should

text: not

text: be

text: aﬀected

text: by

text: a

text: dominated

text: third

text: option,

text: “burning

text: the

text: bill”.

text: Other

text: standard

text: decision

text: decision

text: rule

text: has

text: been

text: mentioned

text: in

text: passing,

text: inside

text: a

text: proof

text: by

text: Hayashi

text: where

text: it

text: was

text: referred

text: to

text: as

text: ‘maximin

text: joy’.

text: We

text: use

text: the

text: term

text: ‘safety’

text: rather

text: than

text: ‘joy’

text: to

text: avoid

text: confusion

text: with

text: the

text: concept

text: called

text: ‘joy

text: of

text: winning’

text: in

text: ##LTLine##


text: (cid:124) (cid:123)(cid:122) (cid:125) (cid:124) (cid:123)(cid:122) (cid:125) A simplicial isometric map of an indeﬁnite metric polyhedron into a Minkowski R − − space p with signature (+, . . . , +, , . . . , ) is a simplicial map such that q p q the bilinear form of every simplex equals to the pull-back of the inner product R of p along this map. In particular, such maps preserve the squared lengths q of edges. Conversely, every simplicial map that preserves squared lengths of edges is isometric, because a bilinear form is completely determined by its values on the edges of a non-degenerate simplex. A simplicial isometric embedding of a metric polyhedron into a Minkowski space is an injective simplicial isometric map. V For an indeﬁnite metric polyhedron, by we denote its vertex set. For every vertex v of this set we deﬁne its degree deg(v) as the number of edges of the simplicial complex containing v. In the sequel we restrict our attention only to ﬁnite or countable indeﬁnite metric polyhedra. The special case of simplicial isometric map of Euclidean polyhedra into a Euclidean space has been studied in details in [1–3, 5]. Note that in general a Euclidean polyhedron does not admit a simplicial isometric map into a Euclidean space. However, every polyhedron can be subdivided in such a way that the resulting polyhedron admits such a map, see, for example, [7]. In contrast, in the pseudo-Euclidean setting one does not need to subdivide the triangulation. In particular, a Euclidean polyhedron (of bounded ver- tex degree) admits a simplicial isometric embedding into a (non-Euclidean) Minkowski space of an appropriate dimension. Now we are ready to cite a theorem from [6]: X Theorem (B. Minemyer, 2012, [6], Theorem 1.1, Corollary 3.4). Let be a V compact n-dimensional indeﬁnite metric polyhedron with vertex set . Then X R (1) There exists a simplicial isometric map of into d, where d = { | ∈ V} d max deg(v) v . X R (2) There exists a simplicial isometric embedding of into q, where { } q q = max d, 2n + 1 . R The dimension of d in the ﬁrst part of the theorem is shown in [6] to d be optimal. The idea is that the 1-skeleton of the standard d-dimensional R simplex cannot be isometrically embedded into p with p < d. q This theorem is followed in [6] by two generalizations. One of them pro- vides an algorithm to explicitly construct such extensions, and the other one applies to non-compact polyhedra. Both of these upgrades result in a sig- niﬁcant increase of the target space dimension. For non-compact polyhedra, R − the target space is p, where p = 2q(d3 d2 + d + 1), and d and q are the p same as in the theorem. 2

text: A

text: simplicial

text: isometric

text: map

text: of

text: an

text: indeﬁnite

text: metric

text: polyhedron

text: into

text: a

text: Minkowski

text: R

text: space

text: p

text: with

text: signature

text: is

text: a

text: simplicial

text: map

text: such

text: that

text: q

text: p

text: q

text: the

text: bilinear

text: form

text: of

text: every

text: simplex

text: equals

text: to

text: the

text: pull-back

text: of

text: the

text: inner

text: product

text: R

text: of

text: p

text: along

text: this

text: map.

text: In

text: particular,

text: such

text: maps

text: preserve

text: the

text: squared

text: lengths

text: q

text: of

text: edges.

text: Conversely,

text: every

text: simplicial

text: map

text: that

text: preserves

text: squared

text: lengths

text: of

text: edges

text: is

text: isometric,

text: because

text: a

text: bilinear

text: form

text: is

text: completely

text: determined

text: by

text: its

text: values

text: on

text: the

text: edges

text: of

text: a

text: non-degenerate

text: simplex.

text: A

text: simplicial

text: isometric

text: embedding

text: of

text: a

text: metric

text: polyhedron

text: into

text: a

text: Minkowski

text: space

text: is

text: an

text: injective

text: simplicial

text: isometric

text: map.

text: V

text: For

text: an

text: indeﬁnite

text: metric

text: polyhedron,

text: by

text: we

text: denote

text: its

text: vertex

text: set.

text: For

text: every

text: vertex

text: v

text: of

text: this

text: set

text: we

text: deﬁne

text: its

text: degree

text: deg(v)

text: as

text: the

text: number

text: of

text: edges

text: of

text: the

text: simplicial

text: complex

text: containing

text: v.

text: In

text: the

text: sequel

text: we

text: restrict

text: our

text: attention

text: only

text: to

text: ﬁnite

text: or

text: countable

text: indeﬁnite

text: metric

text: polyhedra.

text: The

text: special

text: case

text: of

text: simplicial

text: isometric

text: map

text: of

text: Euclidean

text: polyhedra

text: into

text: a

text: Euclidean

text: space

text: has

text: been

text: studied

text: in

text: details

text: in

text: Note

text: that

text: in

text: general

text: a

text: Euclidean

text: polyhedron

text: does

text: not

text: admit

text: a

text: simplicial

text: isometric

text: map

text: into

text: a

text: Euclidean

text: space.

text: However,

text: every

text: polyhedron

text: can

text: be

text: subdivided

text: in

text: such

text: a

text: way

text: that

text: the

text: resulting

text: polyhedron

text: admits

text: such

text: a

text: map,

text: see,

text: for

text: example,

text: In

text: contrast,

text: in

text: the

text: pseudo-Euclidean

text: setting

text: one

text: does

text: not

text: need

text: to

text: subdivide

text: the

text: triangulation.

text: In

text: particular,

text: a

text: Euclidean

text: polyhedron

text: (of

text: bounded

text: ver-

text: tex

text: degree)

text: admits

text: a

text: simplicial

text: isometric

text: embedding

text: into

text: a

text: (non-Euclidean)

text: Minkowski

text: space

text: of

text: an

text: appropriate

text: dimension.

text: Now

text: we

text: are

text: ready

text: to

text: cite

text: a

text: theorem

text: from

text: X

text: Theorem

text: (B.

text: Minemyer,

text: Theorem

text: Corollary

text: Let

text: be

text: a

text: V

text: compact

text: n-dimensional

text: indeﬁnite

text: metric

text: polyhedron

text: with

text: vertex

text: set

text: Then

text: X

text: R

text: There

text: exists

text: a

text: simplicial

text: isometric

text: map

text: of

text: into

text: d,

text: where

text: d

text: V}

text: d

text: max

text: deg(v)

text: v

text: X

text: R

text: There

text: exists

text: a

text: simplicial

text: isometric

text: embedding

text: of

text: into

text: q,

text: where

text: q

text: q

text: max

text: d,

text: R

text: The

text: dimension

text: of

text: d

text: in

text: the

text: ﬁrst

text: part

text: of

text: the

text: theorem

text: is

text: shown

text: in

text: to

text: d

text: be

text: optimal.

text: The

text: idea

text: is

text: that

text: the

text: of

text: the

text: standard

text: d-dimensional

text: R

text: simplex

text: cannot

text: be

text: isometrically

text: embedded

text: into

text: p

text: with

text: p

text: d.

text: q

text: This

text: theorem

text: is

text: followed

text: in

text: by

text: two

text: generalizations.

text: One

text: of

text: them

text: pro-

text: vides

text: an

text: algorithm

text: to

text: explicitly

text: construct

text: such

text: extensions,

text: and

text: the

text: other

text: one

text: applies

text: to

text: non-compact

text: polyhedra.

text: Both

text: of

text: these

text: upgrades

text: result

text: in

text: a

text: sig-

text: niﬁcant

text: increase

text: of

text: the

text: target

text: space

text: dimension.

text: For

text: non-compact

text: polyhedra,

text: R

text: the

text: target

text: space

text: is

text: p,

text: where

text: p

text: d

text: and

text: d

text: and

text: q

text: are

text: the

text: p

text: same

text: as

text: in

text: the

text: theorem.


text: [6] B Minemyer. Simplicial isometric embeddings of indeﬁnite metric polyhedra. arXiv preprint arXiv:1211.0584, 2012. [7] V. A. Zalgaller. Isometric embedding of polyhedra. Dokl. Akad. Nauk SSSR, 123:599– 601, 1958. (Pavel Galashin) Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 02139, United States Email address, Pavel Galashin: galashin@mit.edu (Vladimir Zolotov) Mathematics and Mechanics Faculty, St. Petersburg State University, Universitetsky pr., 28, Stary Peterhof, 198504, Russia. Email address, Vladimir Zolotov: paranuel@mail.ru 9

label: reference

text: B

text: Minemyer.

text: Simplicial

text: isometric

text: embeddings

text: of

text: indeﬁnite

text: metric

text: polyhedra.

text: arXiv

text: preprint

text: V.

text: A.

text: Zalgaller.

text: Isometric

text: embedding

text: of

text: polyhedra.

text: Dokl.

text: Akad.

text: Nauk

text: SSSR,

text: (Pavel

text: Galashin)

text: Department

label: author

text: of

text: Mathematics,

text: Massachusetts

text: Institute

text: of

text: Technology,

text: Cambridge,

text: MA,

text: United

text: States

text: Email

text: address,

text: Pavel

text: Galashin:

text: galashin@mit.edu

label: footer

text: (Vladimir

text: Zolotov)

text: Mathematics

text: and

text: Mechanics

text: Faculty,

text: St.

text: Petersburg

text: State

text: University,

text: Universitetsky

text: pr.,

text: Stary

text: Peterhof,

text: Russia.

text: Email

text: address,

text: Vladimir

text: Zolotov:

text: paranuel@mail.ru


text: 2 D. Kjurkchieva & D. Dimitrov: Light curve solutions of the ultrashort-period Kepler binaries inappropriate for such conﬁgurations. Our preliminary at- tempts to reproduce their data required enormous big third light. This means that KID 8288741 and KID 12350008 are not the true variable stars. It is meaningless to model these data because the obtained parameters would not be reliable. Matuevic et al. (2012) noted that the automated classiﬁca- tion and modeling of Kepler EBs, even with locally lin- ∼ ear embedding, failed for small amplitudes ( 0.001 mag). KID 8288741 and KID 12350008 are such cases but the rea- son to be removed from the further analysis is the discrep- ancy between the light curve shape appropriate for detached eclipsing binary and the negligible amplitude of variability (smaller even than those of ellipsoidal variations). As a result of the selection procedure we gathered sam- ple of six ultrashort-period binaries: KID 4921906, KID 1572353, KID 8108785, KID 6309193, KID 12055255, KID 9532219. More conclusive conﬁrmation of their du- plicity would be spectroscopic data. The objects would re- quire 8m-class telescope due to low brightness and short pe- Fig.1 The light curve of KID 4921906 and our ﬁt (top) and the corresponding residuals (bottom) riod at the same time. Another possibility for proper classiﬁ- cation is the color-period diagram (Duerbeck, 1997) but the presence of third component or close neighbor can alter the color information. So we will use the important criterion for sure classiﬁcation of the targets: the successful reproducing of their light curves by effects of duplicity. Table 1 presents information for our 6 targets from the Kepler EB catalog: Kepler magnitude m ; epoch T of K 0 the primary minimum; orbital period P; mean temperature T ; metallicity [Fe/H]; radius R; log g; reddening E(B-V); m type of conﬁguration; ratio T /T of the temperatures of the 2 1 components; ﬁllout factor FF; crowding (a number between 0 and 1 that speciﬁes the fraction of ﬂux in the optimal pho- tometric aperture due to the target star with respect to the total ﬂux from all sources). More than 50000 points are available for each target in the Kepler archive. The detailed review of these data re- vealed that the shape of the light curves almost did not change during the different observational quarters. However Fig.2 The light curve of KID 1572353 and our ﬁt (top) and the the levels of maxima and minima and the amplitudes of the corresponding residuals (bottom) light curves of the most targets changed considerably during the different quarters causing the big thickness of the total light curves (from all quarters). This effect is probably due was expected for their short orbital periods. The depths of to problems of the satellite steering and automated reduc- the two minima of the most curves are close that means that tion of the data. That is why we assumed that it is reasonable the binaries are almost in thermal contact. The small light to model data from several consecutive quarters rather than amplitudes of some targets point at low orbital inclinations all data simultaneously. Moreover, we established that it is and consequently, considerable contributions of the ellip- more appropriate to use the raw Kepler data and to make soidal variations. own reduction and de-trending (Dimitrov et al. 2012). Taking into account the foregoing considerations we We chose to model the data from quarters Q0 and Q1 carried out modeling of the photometric data by the code for all targets excepting KID 9532219 which observations PHOEBE (Prsa & Zwitter 2005) using the following proce- began later. Their folded light curves are presented in Figs. dure. 1-6. Initially the primary temperature was ﬁxed as T =T . 3 Light curve solutions 1 m The mean target temperatures T (Table 1) have been es- m timated using dedicated pre-launch ground-based optical The shapes of the light curves (Figs. 1-6) implied that multi-color photometry plus Two Micron All Sky Survey our targets are nearly contact or overcontact systems that (2MASS) J, K, and H magnitudes (Skrutskie et al., 2006). (cid:13)c 0000WILEY-VCHVerlagGmbH&Co.KGaA,Weinheim www.an-journal.org ##LTFigure## ##LTFigure## ##LTLine##

text: D.

text: Kjurkchieva

text: D.

text: Dimitrov:

text: Light

text: curve

text: solutions

text: of

text: the

text: ultrashort-period

text: Kepler

text: binaries

text: inappropriate

text: for

text: such

text: conﬁgurations.

text: Our

text: preliminary

text: at-

text: tempts

text: to

text: reproduce

text: their

text: data

text: required

text: enormous

text: big

text: third

text: light.

text: This

text: means

text: that

text: KID

text: and

text: KID

text: are

text: not

text: the

text: true

text: variable

text: stars.

text: It

text: is

text: meaningless

text: to

text: model

text: these

text: data

text: because

text: the

text: obtained

text: parameters

text: would

text: not

text: be

text: reliable.

text: Matuevic

text: et

text: al.

text: noted

text: that

text: the

text: automated

text: classiﬁca-

text: tion

text: and

text: modeling

text: of

text: Kepler

text: EBs,

text: even

text: with

text: locally

text: lin-

text: ear

text: embedding,

text: failed

text: for

text: small

text: amplitudes

text: mag).

text: KID

text: and

text: KID

text: are

text: such

text: cases

text: but

text: the

text: rea-

text: son

text: to

text: be

text: removed

text: from

text: the

text: further

text: analysis

text: is

text: the

text: discrep-

text: ancy

text: between

text: the

text: light

text: curve

text: shape

text: appropriate

text: for

text: detached

text: eclipsing

text: binary

text: and

text: the

text: negligible

text: amplitude

text: of

text: variability

text: (smaller

text: even

text: than

text: those

text: of

text: ellipsoidal

text: variations).

text: As

text: a

text: result

text: of

text: the

text: selection

text: procedure

text: we

text: gathered

text: sam-

text: ple

text: of

text: six

text: ultrashort-period

text: binaries:

text: KID

text: KID

text: KID

text: KID

text: KID

text: KID

text: More

text: conclusive

text: conﬁrmation

text: of

text: their

text: du-

text: plicity

text: would

text: be

text: spectroscopic

text: data.

text: The

text: objects

text: would

text: re-

text: quire

text: telescope

text: due

text: to

text: low

text: brightness

text: and

text: short

text: pe-

text: The

text: light

text: curve

text: of

text: KID

text: and

text: our

text: ﬁt

text: (top)

text: and

text: the

text: corresponding

text: residuals

text: (bottom)

text: riod

text: at

text: the

text: same

text: time.

text: Another

text: possibility

text: for

text: proper

text: classiﬁ-

text: cation

text: is

text: the

text: color-period

text: diagram

text: (Duerbeck,

text: but

text: the

text: presence

text: of

text: third

text: component

text: or

text: close

text: neighbor

text: can

text: alter

text: the

text: color

text: information.

text: So

text: we

text: will

text: use

text: the

text: important

text: criterion

text: for

text: sure

text: classiﬁcation

text: of

text: the

text: targets:

text: the

text: successful

text: reproducing

text: of

text: their

text: light

text: curves

text: by

text: effects

text: of

text: duplicity.

text: Table

text: presents

text: information

text: for

text: our

text: targets

text: from

text: the

text: Kepler

text: EB

text: catalog:

text: Kepler

text: magnitude

text: m

text: epoch

text: T

text: of

text: K

text: the

text: primary

text: minimum;

text: orbital

text: period

text: P;

text: mean

text: temperature

text: T

text: metallicity

text: [Fe/H];

text: radius

text: R;

text: log

text: g;

text: reddening

text: E(B-V);

text: m

text: type

text: of

text: conﬁguration;

text: ratio

text: T

text: /T

text: of

text: the

text: temperatures

text: of

text: the

text: components;

text: ﬁllout

text: factor

text: FF;

text: crowding

text: (a

text: number

text: between

text: and

text: that

text: speciﬁes

text: the

text: fraction

text: of

text: ﬂux

text: in

text: the

text: optimal

text: pho-

text: tometric

text: aperture

text: due

text: to

text: the

text: target

text: star

text: with

text: respect

text: to

text: the

text: total

text: ﬂux

text: from

text: all

text: sources).

text: More

text: than

text: points

text: are

text: available

text: for

text: each

text: target

text: in

text: the

text: Kepler

text: archive.

text: The

text: detailed

text: review

text: of

text: these

text: data

text: re-

text: vealed

text: that

text: the

text: shape

text: of

text: the

text: light

text: curves

text: almost

text: did

text: not

text: change

text: during

text: the

text: different

text: observational

text: quarters.

text: However

text: The

text: light

text: curve

text: of

text: KID

text: and

text: our

text: ﬁt

text: (top)

text: and

text: the

text: the

text: levels

text: of

text: maxima

text: and

text: minima

text: and

text: the

text: amplitudes

text: of

text: the

text: corresponding

text: residuals

text: (bottom)

text: light

text: curves

text: of

text: the

text: most

text: targets

text: changed

text: considerably

text: during

text: the

text: different

text: quarters

text: causing

text: the

text: big

text: thickness

text: of

text: the

text: total

text: light

text: curves

text: (from

text: all

text: quarters).

text: This

text: effect

text: is

text: probably

text: due

text: was

text: expected

text: for

text: their

text: short

text: orbital

text: periods.

text: The

text: depths

text: of

text: to

text: problems

text: of

text: the

text: satellite

text: steering

text: and

text: automated

text: reduc-

text: the

text: two

text: minima

text: of

text: the

text: most

text: curves

text: are

text: close

text: that

text: means

text: that

text: tion

text: of

text: the

text: data.

text: That

text: is

text: why

text: we

text: assumed

text: that

text: it

text: is

text: reasonable

text: the

text: binaries

text: are

text: almost

text: in

text: thermal

text: contact.

text: The

text: small

text: light

text: to

text: model

text: data

text: from

text: several

text: consecutive

text: quarters

text: rather

text: than

text: amplitudes

text: of

text: some

text: targets

text: point

text: at

text: low

text: orbital

text: inclinations

text: all

text: data

text: simultaneously.

text: Moreover,

text: we

text: established

text: that

text: it

text: is

text: and

text: consequently,

text: considerable

text: contributions

text: of

text: the

text: ellip-

text: more

text: appropriate

text: to

text: use

text: the

text: raw

text: Kepler

text: data

text: and

text: to

text: make

text: soidal

text: variations.

text: own

text: reduction

text: and

text: de-trending

text: (Dimitrov

text: et

text: al.

text: Taking

text: into

text: account

text: the

text: foregoing

text: considerations

text: we

text: We

text: chose

text: to

text: model

text: the

text: data

text: from

text: quarters

text: and

text: carried

text: out

text: modeling

text: of

text: the

text: photometric

text: data

text: by

text: the

text: code

text: for

text: all

text: targets

text: excepting

text: KID

text: which

text: observations

text: PHOEBE

text: (Prsa

text: Zwitter

text: using

text: the

text: following

text: proce-

text: began

text: later.

text: Their

text: folded

text: light

text: curves

text: are

text: presented

text: in

text: Figs.

text: dure.

text: Initially

text: the

text: primary

text: temperature

text: was

text: ﬁxed

text: as

text: T

text: =T

text: Light

text: curve

text: solutions

text: m

text: The

text: mean

text: target

text: temperatures

text: T

text: (Table

text: have

text: been

text: es-

text: m

text: timated

text: using

text: dedicated

text: pre-launch

text: ground-based

text: optical

text: The

text: shapes

text: of

text: the

text: light

text: curves

text: (Figs.

text: implied

text: that

text: multi-color

text: photometry

text: plus

text: Two

text: Micron

text: All

text: Sky

text: Survey

text: our

text: targets

text: are

text: nearly

text: contact

text: or

text: overcontact

text: systems

text: that

text: J,

text: K,

text: and

text: H

text: magnitudes

text: (Skrutskie

text: et

text: al.,

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##


text: 4 D. Kjurkchieva & D. Dimitrov: Light curve solutions of the ultrashort-period Kepler binaries We adopted coefﬁcients of gravity brightening 0.32 and (b) Although all light curves exhibit O’Connell effect (Figs. reﬂection effect 0.5 appropriate for late stars. The limb- 1-6) the EBAI method does not take into account the ef- darkening coefﬁcients were chosen according to the tables fect from spots. Then the results of the automated mod- of Van Hamme (1993). elling should be assumed as ﬁrst approximations of the Finally, we varied the component temperatures around ﬁtted parameters. T to search for the best ﬁt. m The derived parameters of the targets corresponding to 4 Analysis of the results our light curve solutions are given in Table 2 while Table 3 presents information about the spot parameters. The for- The analysis of our light curve solutions of the mal PHOEBE errors of the ﬁtted parameters are quite small ultrashort-period binaries from the Kepler data base led to (Tables 2-3) due to the high precision of the Kepler data. several conclusions. It should be noted that the ephemerides from the Kepler (1) The conﬁgurations of all targets are almost the EB catalogue (PRSA11) did not lead to the best ﬁts. For same: 4 of them are contact binaries (KID 4921906, this aim we varied the parameter ”shift” of PHOEBE which KID 1572353, KID 8108785, KID 6309193) and 2 ﬁnal values are given in column 2 of Table 2. are slightly overcontact systems (KID 12055255 and The synthetic curves corresponding to the parameters KID 9532219). of our light curve solutions are shown in Figs. 1-6 as red (2) Two targets, KID 4921906 and KID 6309193, are continuous lines. noneclipsing systems. The registration of their low- The derived photometric mass ratio requires a special at- amplitude ellipsoidal and rotational (due spots) vari- tention. Usually this parameter needs spectral observations. ability is possible due to the high Kepler accuracy. But the spectral mass ratio for short-period binaries with fast There are quite many objects of this type in the Ke- rotation is quite imprecise due to the line blending while the pler EB catalog and hence, it should be called catalog geometrical effects and mass ratio are much more important of photometrically-double stars. in deﬁning the shapes of their light curves and the eclipse (3) To model the data of KID 9532219 we had to assume depths. Hence, the values of the photometric mass ratio for considerable contribution of a third light l . It originates ultrashort-period Kepler binaries should be considered with 3 probably from the close neighbor. We do not exclude high conﬁdence. this fainter star to be the true variable because the size of There are differences between our solutions and those the Kepler pixels projected onto the sky (4 arcsec) cou- obtained by automated ﬁtting cited in the Kepler EB catalog pled with the high star density near the Galactic plane (the values in parentheses in Table 2). lead to a non-negligible likelihood of associating an EB (1) The most orbital inclinations in PRSA11 are bigger than event with the wrong star (PRSA11). ours. (4) The target KID 12055255 is very rare case of ultrashort- (2) The mass ratios in PRSA11 are considerably smaller period binary consisting of two M dwarfs. The system than our values (Table 2). seems to be overcontact. We are not aware of any over- (3) We had to assume a third light l3 only for KID 9532219 contact binary consisting of M dwarfs. (Table 3) while the values of this parameter in PRSA11 (5) Feldmeier et al. (2011) classiﬁed the target were nonzeros for the all six targets. We found a weaker KID 9532219 as a δ Sct variable (from their ground- star close to KID 9532219 (at distance around 6 arcsec) based photometric observations of the Kepler FoV for that could explain the presence of l3 in the light curve the pre-launch survey). The Kepler data and our mod- solution of this target. eling certainly reveal that this target (or its neighbor) is (4) There are no values of the potentials Ω1,2 (and thus of eclipsing binary. the relative radii r1,2 and ﬁllout factors FF1,2) as well (6) Recently KID 6309193 was noted as ”false” in the Ke- as of relative luminosities in PRSA11 that means that pler EB catalog. Our modeling showed that it is not the automated modelling leads to approximate results. eclipsing star but its light curve can be reproduced by There are several explanations for the differences be- ellipsoidal variations of binary. However we do not ex- tween our ”manual” solutions and those of the automated clude the alternative the observed variability to be inher- ﬁtting. ent to some of its two considerably fainter neighbors (at distances around 4.5 arcsec and 7 arcsec). (a) The EBAI method ﬁxes l = 1 - crowding while this 3 (7) The ripples in the residuals of KID 8108785 (Fig. 3) parameter is invoked in our procedure only when a sat- seem to be quasi-sinusoidal with period of 55 min and isfactory ﬁt is impossible for any combination of the pa- amplitude of 0.005 mag. Although this variability is vis- rameters. The bigger value of l requires bigger light 3 ible during all phases, it could be explained by inherent amplitude and correspondingly bigger orbital inclina- changes of some of the components of this system due tion. Moreover, due to the correlation between third to its small orbital inclination. light and mass ratio for partially eclipsing binaries the bigger third light leads to the larger mass ratio for ﬁxed Although all considered light curves reveal O’Connell inclination angle. effect and are reproduced by cool spots we have not stud- (cid:13)c 0000WILEY-VCHVerlagGmbH&Co.KGaA,Weinheim www.an-journal.org ##LTLine##

text: D.

text: Kjurkchieva

text: D.

text: Dimitrov:

text: Light

text: curve

text: solutions

text: of

text: the

text: ultrashort-period

text: Kepler

text: binaries

text: We

text: adopted

text: coefﬁcients

text: of

text: gravity

text: brightening

text: and

text: (b)

text: Although

text: all

text: light

text: curves

text: exhibit

text: O’Connell

text: effect

text: (Figs.

text: reﬂection

text: effect

text: appropriate

text: for

text: late

text: stars.

text: The

text: limb-

text: the

text: EBAI

text: method

text: does

text: not

text: take

text: into

text: account

text: the

text: ef-

text: darkening

text: coefﬁcients

text: were

text: chosen

text: according

text: to

text: the

text: tables

text: fect

text: from

text: spots.

text: Then

text: the

text: results

text: of

text: the

text: automated

text: mod-

text: of

text: Van

text: Hamme

text: elling

text: should

text: be

text: assumed

text: as

text: ﬁrst

text: approximations

text: of

text: the

text: Finally,

text: we

text: varied

text: the

text: component

text: temperatures

text: around

text: ﬁtted

text: parameters.

text: T

text: to

text: search

text: for

text: the

text: best

text: ﬁt.

text: m

text: The

text: derived

text: parameters

text: of

text: the

text: targets

text: corresponding

text: to

text: Analysis

text: of

text: the

text: results

text: our

text: light

text: curve

text: solutions

text: are

text: given

text: in

text: Table

text: while

text: Table

text: presents

text: information

text: about

text: the

text: spot

text: parameters.

text: The

text: for-

text: The

text: analysis

text: of

text: our

text: light

text: curve

text: solutions

text: of

text: the

text: mal

text: PHOEBE

text: errors

text: of

text: the

text: ﬁtted

text: parameters

text: are

text: quite

text: small

text: ultrashort-period

text: binaries

text: from

text: the

text: Kepler

text: data

text: base

text: led

text: to

text: (Tables

text: due

text: to

text: the

text: high

text: precision

text: of

text: the

text: Kepler

text: data.

text: several

text: conclusions.

text: It

text: should

text: be

text: noted

text: that

text: the

text: ephemerides

text: from

text: the

text: Kepler

text: The

text: conﬁgurations

text: of

text: all

text: targets

text: are

text: almost

text: the

text: EB

text: catalogue

text: did

text: not

text: lead

text: to

text: the

text: best

text: ﬁts.

text: For

text: same:

text: of

text: them

text: are

text: contact

text: binaries

text: (KID

text: this

text: aim

text: we

text: varied

text: the

text: parameter

text: ”shift”

text: of

text: PHOEBE

text: which

text: KID

text: KID

text: KID

text: and

text: ﬁnal

text: values

text: are

text: given

text: in

text: column

text: of

text: Table

text: are

text: slightly

text: overcontact

text: systems

text: (KID

text: and

text: The

text: synthetic

text: curves

text: corresponding

text: to

text: the

text: parameters

text: KID

text: of

text: our

text: light

text: curve

text: solutions

text: are

text: shown

text: in

text: Figs.

text: as

text: red

text: Two

text: targets,

text: KID

text: and

text: KID

text: are

text: continuous

text: lines.

text: noneclipsing

text: systems.

text: The

text: registration

text: of

text: their

text: low-

text: The

text: derived

text: photometric

text: mass

text: ratio

text: requires

text: a

text: special

text: at-

text: amplitude

text: ellipsoidal

text: and

text: rotational

text: (due

text: spots)

text: vari-

text: tention.

text: Usually

text: this

text: parameter

text: needs

text: spectral

text: observations.

text: ability

text: is

text: possible

text: due

text: to

text: the

text: high

text: Kepler

text: accuracy.

text: But

text: the

text: spectral

text: mass

text: ratio

text: for

text: short-period

text: binaries

text: with

text: fast

text: There

text: are

text: quite

text: many

text: objects

text: of

text: this

text: type

text: in

text: the

text: Ke-

text: rotation

text: is

text: quite

text: imprecise

text: due

text: to

text: the

text: line

text: blending

text: while

text: the

text: pler

text: EB

text: catalog

text: and

text: hence,

text: it

text: should

text: be

text: called

text: catalog

text: geometrical

text: effects

text: and

text: mass

text: ratio

text: are

text: much

text: more

text: important

text: of

text: photometrically-double

text: stars.

text: in

text: deﬁning

text: the

text: shapes

text: of

text: their

text: light

text: curves

text: and

text: the

text: eclipse

text: To

text: model

text: the

text: data

text: of

text: KID

text: we

text: had

text: to

text: assume

text: depths.

text: Hence,

text: the

text: values

text: of

text: the

text: photometric

text: mass

text: ratio

text: for

text: considerable

text: contribution

text: of

text: a

text: third

text: light

text: l

text: It

text: originates

text: ultrashort-period

text: Kepler

text: binaries

text: should

text: be

text: considered

text: with

text: probably

text: from

text: the

text: close

text: neighbor.

text: We

text: do

text: not

text: exclude

text: high

text: conﬁdence.

text: this

text: fainter

text: star

text: to

text: be

text: the

text: true

text: variable

text: because

text: the

text: size

text: of

text: There

text: are

text: differences

text: between

text: our

text: solutions

text: and

text: those

text: the

text: Kepler

text: pixels

text: projected

text: onto

text: the

text: sky

text: arcsec)

text: cou-

text: obtained

text: by

text: automated

text: ﬁtting

text: cited

text: in

text: the

text: Kepler

text: EB

text: catalog

text: pled

text: with

text: the

text: high

text: star

text: density

text: near

text: the

text: Galactic

text: plane

text: (the

text: values

text: in

text: parentheses

text: in

text: Table

text: lead

text: to

text: a

text: non-negligible

text: likelihood

text: of

text: associating

text: an

text: EB

text: The

text: most

text: orbital

text: inclinations

text: in

text: are

text: bigger

text: than

text: event

text: with

text: the

text: wrong

text: star

text: ours.

text: The

text: target

text: KID

text: is

text: very

text: rare

text: case

text: of

text: ultrashort-

text: The

text: mass

text: ratios

text: in

text: are

text: considerably

text: smaller

text: period

text: binary

text: consisting

text: of

text: two

text: M

text: dwarfs.

text: The

text: system

text: than

text: our

text: values

text: (Table

text: seems

text: to

text: be

text: overcontact.

text: We

text: are

text: not

text: aware

text: of

text: any

text: over-

text: We

text: had

text: to

text: assume

text: a

text: third

text: light

text: only

text: for

text: KID

text: contact

text: binary

text: consisting

text: of

text: M

text: dwarfs.

text: (Table

text: while

text: the

text: values

text: of

text: this

text: parameter

text: in

text: Feldmeier

text: et

text: al.

text: classiﬁed

text: the

text: target

text: were

text: nonzeros

text: for

text: the

text: all

text: six

text: targets.

text: We

text: found

text: a

text: weaker

text: KID

text: as

text: a

text: δ

text: Sct

text: variable

text: (from

text: their

text: ground-

text: star

text: close

text: to

text: KID

text: (at

text: distance

text: around

text: arcsec)

text: based

text: photometric

text: observations

text: of

text: the

text: Kepler

text: FoV

text: for

text: that

text: could

text: explain

text: the

text: presence

text: of

text: in

text: the

text: light

text: curve

text: the

text: pre-launch

text: survey).

text: The

text: Kepler

text: data

text: and

text: our

text: mod-

text: solution

text: of

text: this

text: target.

text: eling

text: certainly

text: reveal

text: that

text: this

text: target

text: (or

text: its

text: neighbor)

text: is

text: There

text: are

text: no

text: values

text: of

text: the

text: potentials

text: (and

text: thus

text: of

text: eclipsing

text: binary.

text: the

text: relative

text: radii

text: and

text: ﬁllout

text: factors

text: as

text: well

text: Recently

text: KID

text: was

text: noted

text: as

text: ”false”

text: in

text: the

text: Ke-

text: as

text: of

text: relative

text: luminosities

text: in

text: that

text: means

text: that

text: pler

text: EB

text: catalog.

text: Our

text: modeling

text: showed

text: that

text: it

text: is

text: not

text: the

text: automated

text: modelling

text: leads

text: to

text: approximate

text: results.

text: eclipsing

text: star

text: but

text: its

text: light

text: curve

text: can

text: be

text: reproduced

text: by

text: There

text: are

text: several

text: explanations

text: for

text: the

text: differences

text: be-

text: ellipsoidal

text: variations

text: of

text: binary.

text: However

text: we

text: do

text: not

text: ex-

text: tween

text: our

text: ”manual”

text: solutions

text: and

text: those

text: of

text: the

text: automated

text: clude

text: the

text: alternative

text: the

text: observed

text: variability

text: to

text: be

text: inher-

text: ﬁtting.

text: ent

text: to

text: some

text: of

text: its

text: two

text: considerably

text: fainter

text: neighbors

text: (at

text: distances

text: around

text: arcsec

text: and

text: arcsec).

text: (a)

text: The

text: EBAI

text: method

text: ﬁxes

text: l

text: crowding

text: while

text: this

text: The

text: ripples

text: in

text: the

text: residuals

text: of

text: KID

text: (Fig.

text: parameter

text: is

text: invoked

text: in

text: our

text: procedure

text: only

text: when

text: a

text: sat-

text: seem

text: to

text: be

text: quasi-sinusoidal

text: with

text: period

text: of

text: min

text: and

text: isfactory

text: ﬁt

text: is

text: impossible

text: for

text: any

text: combination

text: of

text: the

text: pa-

text: amplitude

text: of

text: mag.

text: Although

text: this

text: variability

text: is

text: vis-

text: rameters.

text: The

text: bigger

text: value

text: of

text: l

text: requires

text: bigger

text: light

text: ible

text: during

text: all

text: phases,

text: it

text: could

text: be

text: explained

text: by

text: inherent

text: amplitude

text: and

text: correspondingly

text: bigger

text: orbital

text: inclina-

text: changes

text: of

text: some

text: of

text: the

text: components

text: of

text: this

text: system

text: due

text: tion.

text: Moreover,

text: due

text: to

text: the

text: correlation

text: between

text: third

text: to

text: its

text: small

text: orbital

text: inclination.

text: light

text: and

text: mass

text: ratio

text: for

text: partially

text: eclipsing

text: binaries

text: the

text: bigger

text: third

text: light

text: leads

text: to

text: the

text: larger

text: mass

text: ratio

text: for

text: ﬁxed

text: Although

text: all

text: considered

text: light

text: curves

text: reveal

text: O’Connell

text: inclination

text: angle.

text: effect

text: and

text: are

text: reproduced

text: by

text: cool

text: spots

text: we

text: have

text: not

text: stud-

text: ##LTLine##