text:   where v(k) is a vector inthe lat(cid:88)tice Λk deﬁned by  n  −  n 1 ≡ ∈ Λk 2πR e2nπijk(mj,1 + imj,2), mj,1, mj,2 Z . (2.7) n j=0 (cid:73) (cid:73) These boundary conditions induce the following monodromy conditions (cid:73) (cid:73) dz∂X(t,k)(z) + dz¯∂¯X(t,k) = v(k) a γa γa dz∂X¯(t,k)(z) + dz¯∂¯X¯(t,k) = v¯(k), (2.8) a γa γa where γ ’s are the two cycles of worldsheet torus. In terms of cut diﬀerentials a − | − − − | − − − k − k | ω1(k)(z) = ϑ1(z z1 τ) (1 nk )ϑ1(z z2 τ) nk ϑ1(z (1 n)z1 nz2 τ) − | − − | − − − k − − k | ω2(k)(z) = ϑ1(z z1 τ) nk ϑ1(z z2 τ) (1 nk )ϑ1(z nz1 (1 n)z2 τ), (2.9) the classical solutions can be written as ∂X(t,k) = a(k)ω(k)(z), ∂¯X(t,k) = b(k)ω¯(k)(z¯), 1 2 ∂X¯(t,k) = a˜(k)ω(k)(z), ∂¯X¯(t,k) = ˜b(k)ω¯(k)(z¯). (2.10) 2 1 Solving the monodromy condition, we get − − 2(k) 2(k) 1(k) 1(k) W v W v W v + W v a(k) = 2 1 1 2 , b(k) = 2 1 1 2 , det W (k) det W (k) − − W¯ 1(k)v¯ W¯ 1(k)v¯ W¯ 2(k)v¯ W¯ 2(k)v¯ a˜(k) = 1 2 2 1 , ˜b(k) = 2 1 1 2 , (2.11) det W¯ (k) det W¯ (k) where the W functions are deﬁned to be the integral of the cut diﬀerentials along diﬀerent cycles. The deﬁnition and properties of the W functions could be found in the Appendix. With these results, the classical action for X(t,k) is just 1 1 | | | | | | | | S(k) = 4πnα(cid:48) | 1(k) 2(k) |( v1(k) 2 W22(k) 2 + v2(k) 2 W11(k) 2). (2.12) W W 1 2 The above discussion is the same as the one in [13]. However, in [13], the classical action is further simpliﬁed using the relation between W functions. The relation turns out to be problematic, as shown in [14]. Furthermore, the lattice translation v and v were determined 1 2 in [13] along the way in [9]. But notice that we are considering n-sheeted torus, which is very diﬀerent from the n-sheeted Riemann surface got from two interval complex plane. Actually, the translation vectors are much simpler in the n-sheeted torus case. On this Riemann surface, the spacial cycles and time cycles on n replicas build the canonical cycles, and all of the cycles 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: where

text: v(k)

text: is

text: a

text: vector

text: inthe

text: Λk

text: deﬁned

text: by

text: n

text: n

text: Λk

text: Z

text: n

text: These

text: boundary

text: conditions

text: induce

text: the

text: following

text: monodromy

text: conditions

text: dz∂X(t,k)(z)

text: dz¯∂¯X(t,k)

text: v(k)

text: a

text: γa

text: γa

text: dz∂X¯(t,k)(z)

text: dz¯∂¯X¯(t,k)

text: v¯(k),

text: a

text: γa

text: γa

text: where

text: γ

text: ’s

text: are

text: the

text: two

text: cycles

text: of

text: worldsheet

text: torus.

text: In

text: terms

text: of

text: cut

text: diﬀerentials

text: a

text: k

text: k

text: τ)

text: nk

text: τ)

text: nk

text: τ)

text: k

text: k

text: τ)

text: nk

text: τ)

text: nk

text: τ),

text: the

text: classical

text: solutions

text: can

text: be

text: written

text: as

text: ∂X(t,k)

text: a(k)ω(k)(z),

text: ∂¯X(t,k)

text: b(k)ω¯(k)(z¯),

text: ∂X¯(t,k)

text: a˜(k)ω(k)(z),

text: ∂¯X¯(t,k)

text: ˜b(k)ω¯(k)(z¯).

text: Solving

text: the

text: monodromy

text: condition,

text: we

text: get

text: W

text: v

text: W

text: v

text: W

text: v

text: W

text: v

text: a(k)

text: b(k)

text: det

text: W

text: (k)

text: det

text: W

text: (k)

text: W¯

text: W¯

text: W¯

text: W¯

text: a˜(k)

text: ˜b(k)

text: det

text: W¯

text: (k)

text: det

text: W¯

text: (k)

text: where

text: the

text: W

text: functions

text: are

text: deﬁned

text: to

text: be

text: the

text: integral

text: of

text: the

text: cut

text: diﬀerentials

text: along

text: diﬀerent

text: cycles.

text: The

text: deﬁnition

text: and

text: properties

text: of

text: the

text: W

text: functions

text: could

text: be

text: found

text: in

text: the

text: Appendix.

text: With

text: these

text: results,

text: the

text: classical

text: action

text: for

text: X(t,k)

text: is

text: just

text: S(k)

text: W

text: W

text: The

text: above

text: discussion

text: is

text: the

text: same

text: as

text: the

text: one

text: in

text: However,

text: in

text: the

text: classical

text: action

text: is

text: further

text: simpliﬁed

text: using

text: the

text: relation

text: between

text: W

text: functions.

text: The

text: relation

text: turns

text: out

text: to

text: be

text: problematic,

text: as

text: shown

text: in

text: Furthermore,

text: the

text: lattice

text: translation

text: v

text: and

text: v

text: were

text: determined

text: in

text: along

text: the

text: way

text: in

text: But

text: notice

text: that

text: we

text: are

text: considering

text: n-sheeted

text: torus,

text: which

text: is

text: very

text: diﬀerent

text: from

text: the

text: n-sheeted

text: Riemann

text: surface

text: got

text: from

text: two

text: interval

text: complex

text: plane.

text: Actually,

text: the

text: translation

text: vectors

text: are

text: much

text: simpler

text: in

text: the

text: n-sheeted

text: torus

text: case.

text: On

text: this

text: Riemann

text: surface,

text: the

text: spacial

text: cycles

text: and

text: time

text: cycles

text: on

text: n

text: replicas

text: build

text: the

text: canonical

text: cycles,

text: and

text: all

text: of

text: the

text: cycles

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: Proofs of two conjectures on generalized ∗ Fibonacci cubes † Jianxin Weia,b, Heping Zhang a, a School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu 730000, P. R. China bSchool of Mathematics and Statistics Science, Ludong University, Yantai, Shandong 264025, P. R. China E-mail addresses: wjx0426@163.com, zhanghp@lzu.edu.cn Abstract | | A binary string f is a factor of string u if f appears as a sequence of f consecu- | | tive bits of u, where f denotes the length of f. Generalized Fibonacci cube Q (f) d is the graph obtained from the d-cube Q by removing all vertices that contain a d given binary string f as a factor. A binary string f is called good if Q (f) is an d ≥ isometric subgraph of Q for all d 1, it is called bad otherwise. The index of a d binary string f, denoted by B(f), is the smallest integer d such that Q (f) is not d | | an isometric subgraph of Q . Ili´c, Klavˇzar and Rho conjectured that B(f) < 2 f d for any bad string f. They also conjectured that if Q (f) is an isometric subgraph d of Q , then Q (ff) is an isometric subgraph of Q . We conﬁrm the two conjectures d d d by obtaining a basic result: if there exist p-critical words for Q (f), then p=2 or B(f) p = 3. Key words: Fibonacci cube, Generalized Fibonacci cube, Isometric subgraph, Isometric embedding, Good string 1 Introduction Fibonacci cube Γ was introduced by Hsu [?] as a model for interconnection networks, d which has beneﬁcial properties similar to those of the hypercube. It can be seen as ∗ This work is supported by NSFC (Grant no. 61073046). † Corresponding author. 1 ##LTLine##

text: Proofs

label: title

text: of

text: two

text: conjectures

text: on

text: generalized

text: Fibonacci

text: cubes

label: author

text: Jianxin

text: Weia,b,

text: Heping

text: Zhang

text: a,

text: a

label: paragraph

text: School

text: of

text: Mathematics

text: and

text: Statistics,

text: Lanzhou

text: University,

text: Lanzhou,

text: Gansu

text: P.

text: R.

text: China

text: bSchool

text: of

text: Mathematics

text: and

text: Statistics

text: Science,

text: Ludong

text: University,

text: Yantai,

text: Shandong

text: P.

text: R.

text: China

text: E-mail

text: addresses:

text: zhanghp@lzu.edu.cn

text: Abstract

label: abstract

text: A

text: binary

text: string

text: f

text: is

text: a

text: factor

text: of

text: string

text: u

text: if

text: f

text: appears

text: as

text: a

text: sequence

text: of

text: f

text: consecu-

text: tive

text: bits

text: of

text: u,

text: where

text: f

text: denotes

text: the

text: length

text: of

text: f.

text: Generalized

text: Fibonacci

text: cube

text: Q

text: (f)

text: d

text: is

text: the

text: graph

text: obtained

text: from

text: the

text: d-cube

text: Q

text: by

text: removing

text: all

text: vertices

text: that

text: contain

text: a

text: d

text: given

text: binary

text: string

text: f

text: as

text: a

text: factor.

text: A

text: binary

text: string

text: f

text: is

text: called

text: good

text: if

text: Q

text: (f)

text: is

text: an

text: d

text: isometric

text: subgraph

text: of

text: Q

text: for

text: all

text: d

text: it

text: is

text: called

text: bad

text: otherwise.

text: The

text: index

text: of

text: a

text: d

text: binary

text: string

text: f,

text: denoted

text: by

text: B(f),

text: is

text: the

text: smallest

text: integer

text: d

text: such

text: that

text: Q

text: (f)

text: is

text: not

text: d

text: an

text: isometric

text: subgraph

text: of

text: Q

text: Ili´c,

text: Klavˇzar

text: and

text: Rho

text: conjectured

text: that

text: B(f)

text: f

text: d

text: for

text: any

text: bad

text: string

text: f.

text: They

text: also

text: conjectured

text: that

text: if

text: Q

text: (f)

text: is

text: an

text: isometric

text: subgraph

text: d

text: of

text: Q

text: then

text: Q

text: (ff)

text: is

text: an

text: isometric

text: subgraph

text: of

text: Q

text: We

text: conﬁrm

text: the

text: two

text: conjectures

text: d

text: d

text: d

text: by

text: obtaining

text: a

text: basic

text: result:

text: if

text: there

text: exist

text: p-critical

text: words

text: for

text: Q

text: (f),

text: then

text: or

text: B(f)

text: p

text: Key

text: words:

text: Fibonacci

text: cube,

text: Generalized

text: Fibonacci

text: cube,

text: Isometric

text: subgraph,

text: Isometric

text: embedding,

text: Good

text: string

text: Introduction

text: Fibonacci

text: cube

text: Γ

text: was

text: introduced

text: by

text: Hsu

text: as

text: a

text: model

text: for

text: interconnection

text: networks,

text: d

text: which

text: has

text: beneﬁcial

text: properties

text: similar

text: to

text: those

text: of

text: the

text: hypercube.

text: It

text: can

text: be

text: seen

text: as

text: This

text: work

text: is

text: supported

text: by

text: NSFC

text: (Grant

text: no.

text: Corresponding

text: author.

text: ##LTLine##


text: s +1 r +1 a a a i1 i2 ik f (ui1) a a a i1 i2 ik f (ui2) ai1 ai2 aik f (uik ) (a) r +1 r +1 1 2 a a a i1 i2 ik f (ui1) a a a i1 i2 ik f (uik ) a a a i1 i2 ik f (ui2) (b) r '+1 s +1 a a a i1 i2 ik f (uik ) a a a i1 i2 ik f (ui1) a a a i1 i2 ik f * (c) Fig. 5. Illustration of the Claim 3 of Subcase 1.2. − equations (1) hold for t = i u + 1 and so a = a . It is impossible. Thus there exists 2 i1 i2 i2 no k such that u < u < u . i2 ik i1 ≤ Finally, we show that there exists no k such that u < u i . Otherwise we consider i1 ik 1 ∗ ∗ f(uik), f(ui1) and f , as it is shown in Fig. 5 (c). Recall that f is the factor contained in (cid:48) (cid:48) (cid:48) − (cid:48) α + e + e that starts from the (v )th bit, where v = u + r . Note that i i = r and i1 ij i2 2 1 − equations (1) hold for t = i u + 1, and so a = a by Lemma 2.3. It is impossible. 1 ik i1 i1 This completes the proof of this claim. (cid:50) ≤ (cid:48) Claim 4. There exists k such that i < u i , and for such k, i = i + r , 1 i 2 k 2 k (cid:48) u = u + r and a = a . ik i1 ik i2 ≤ By Claim 3, u > i . Now we show that there exists u i . Otherwise i < u for i 1 i 2 2 i k k k ∈ { · · · } all k 3, , p . If p = 3, then k = 3. So β contains the factor f(ui3), a contradiction. ≥ Hence p 4. Letting µ and ν be the strings that obtained by deleting the factor that − start from the ﬁrst bit to the ith bit of α and β, respectively, µ and ν are (p 2)-critical 2 (cid:48) − words for Q (cid:48)(f), where d = d i . It is a contradiction to d = B(f). Hence there d 0 2 0 ≤ ≤ exists k such that u i . Thus i < u i . i 2 1 i 2 k k ≤ (cid:48) Now we chose any k such that i < u i . First we show i = i + r . Otherwise 1 i 2 k 2 k ∗ we consider f(uik), f(ui1) and f , as shown in Fig. 6 (a). Hence equations (1) hold for − (cid:48) t = i u + 1 and by Lemma 2.3, a = a . obviously it is impossible. Hence i = i + r 2 ik i2 i2 k 2 11 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: s

font: default

text: r

text: a

text: a

text: a

text: ik

text: f

text: a

text: a

text: a

text: ik

text: f

text: aik

text: f

text: (uik

text: (a)

text: r

text: r

text: a

text: a

text: a

text: ik

text: f

text: a

text: a

text: a

text: ik

text: f

text: (uik

text: a

text: a

text: a

text: ik

text: f

text: (b)

text: r

text: s

text: a

text: a

text: a

text: ik

text: f

text: (uik

text: a

text: a

text: a

text: ik

text: f

text: a

text: a

text: a

text: ik

text: f

text: (c)

text: Fig.

text: Illustration

text: of

text: the

text: Claim

text: of

text: Subcase

text: equations

text: hold

text: for

text: t

text: i

text: u

text: and

text: so

text: a

text: a

text: It

text: is

text: impossible.

text: Thus

text: there

text: exists

text: no

text: k

text: such

text: that

text: u

text: u

text: u

text: ik

text: Finally,

text: we

text: show

text: that

text: there

text: exists

text: no

text: k

text: such

text: that

text: u

text: u

text: i

text: Otherwise

text: we

text: consider

text: ik

text: f(uik),

text: and

text: f

text: as

text: it

text: is

text: shown

text: in

text: Fig.

text: (c).

text: Recall

text: that

text: f

text: is

text: the

text: factor

text: contained

text: in

text: α

text: e

text: e

text: that

text: starts

text: from

text: the

text: (v

text: )th

text: bit,

text: where

text: v

text: u

text: r

text: Note

text: that

text: i

text: i

text: r

text: and

text: ij

text: equations

text: hold

text: for

text: t

text: i

text: u

text: and

text: so

text: a

text: a

text: by

text: Lemma

text: It

text: is

text: impossible.

text: ik

text: This

text: completes

text: the

text: proof

text: of

text: this

text: claim.

text: Claim

text: There

text: exists

text: k

text: such

text: that

text: i

text: u

text: i

text: and

text: for

text: such

text: k,

text: i

text: i

text: r

text: i

text: k

text: k

text: u

text: u

text: r

text: and

text: a

text: a

text: ik

text: ik

text: By

text: Claim

text: u

text: i

text: Now

text: we

text: show

text: that

text: there

text: exists

text: u

text: i

text: Otherwise

text: i

text: u

text: for

text: i

text: i

text: i

text: k

text: k

text: k

text: all

text: k

text: p

text: If

text: p

text: then

text: k

text: So

text: β

text: contains

text: the

text: factor

text: a

text: contradiction.

text: Hence

text: p

text: Letting

text: µ

text: and

text: ν

text: be

text: the

text: strings

text: that

text: obtained

text: by

text: deleting

text: the

text: factor

text: that

text: start

text: from

text: the

text: ﬁrst

text: bit

text: to

text: the

text: ith

text: bit

text: of

text: α

text: and

text: β,

text: respectively,

text: µ

text: and

text: ν

text: are

text: (p

text: words

text: for

text: Q

text: where

text: d

text: d

text: i

text: It

text: is

text: a

text: contradiction

text: to

text: d

text: B(f).

text: Hence

text: there

text: d

text: exists

text: k

text: such

text: that

text: u

text: i

text: Thus

text: i

text: u

text: i

text: i

text: i

text: k

text: k

text: Now

text: we

text: chose

text: any

text: k

text: such

text: that

text: i

text: u

text: i

text: First

text: we

text: show

text: i

text: i

text: r

text: Otherwise

text: i

text: k

text: k

text: we

text: consider

text: f(uik),

text: and

text: f

text: as

text: shown

text: in

text: Fig.

text: (a).

text: Hence

text: equations

text: hold

text: for

text: t

text: i

text: u

text: and

text: by

text: Lemma

text: a

text: a

text: obviously

text: it

text: is

text: impossible.

text: Hence

text: i

text: i

text: r

text: ik

text: k

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: r '+1 r '+1 a, a a, l m n f (2r'+1) a, a, a, l m n f (r'+1) a, a, l m f (1) r '+1 r '+1 (a) r +1 r +1 1 2 a, a, m n f (3r'+1) a, a, a, l m n f (v'') a, a, a, l m n f (2r'+1) r '+1 r '+1 (b) (cid:48)(cid:48) Fig. 7. Illustration of the proof of β contains no f as factor. (cid:48)(cid:48) | | (cid:48) (cid:48)(cid:48) are 3-critical words of Q (cid:48)(cid:48)(f), where d = f + 3r . By d = B(f) and α is a factor of d 0 (cid:48)(cid:48) (cid:48)(cid:48) (cid:48)(cid:48) | | (cid:48) α, α = α, β = β and d = d = f + 3r . 0 (cid:54)∈ | | − Case 2. i [u , u + f 1]. j i1 i1 ≥ If p = 2, then β contains the factor f(ui1), a contradiction. Hence p 3 and P = { } \ { } (cid:54) ∅ (cid:54)∈ | | − ∈ 1, 2, . . . , p 1, j = . If i [i + 1, u + f 1] for all k P , then β contains the k 1 i1 ∈ ∈ | |− factor f(ui1), a contradiction. So there must exist k P such that ik [i1+1, ui1 + f 1]. ∈ | | − (cid:54)∈ | | − Since j is the minimal one such that i [u , u + f 1], i [u , u + f 1] for any 1 ij ij 1 ik ik such k. So i < u . 1 i k − − | | (cid:48) (cid:48) · · · (cid:48) Let r = u u and s = u u . Obviously f > r + s. Let α = a a (cid:48) be the ik ij ij i1 1 d | | − (cid:48) | | factor of α that from the uth bit to (u + f 1)th bit of α, where d = f + r. Let − −ij ik (cid:48) (cid:48) (cid:48) m = i u + 1 and n = i u + 1. Then a = a and a = a . Obviously, α contains k ij j ij m ik n ij (cid:48) (cid:48) (cid:48) (cid:48) (cid:48) no factor f. Denote β = α + e + e . If β does not contain factor f, then α and β is m n (cid:48) | | ≤ − 2-critical words for Q (cid:48), where d = f + r d u + 1 < d . But this is a contradiction d ij 0 (cid:48) ≥ to d = B(f). Hence β must contain factor f, and so r 2. Suppose the ﬁrst coordinate 0 ≤ of this copy of f is v, then 1 < v r. Similar to Claim 1 of Subcase 1.2 we can show that (cid:48) (cid:48) (cid:48) (cid:48) − (cid:48) r = 2r is even, n = m + r = r and a = a . This indicate that i i = r , a = a 2 m n j k ik ij (cid:48) (cid:48) | | − and the factor that start from the (u + r )th to the (u + r + f 1)th bit of α + e + e ij ij ik ij (cid:48) (cid:54) is f, and denote it as f(cid:63). Assume that i + r = i . Similar to Claim 4 of Subcase 1.2 we 1 k − − (cid:48) can show that equations (1) hold for t = ik uij r + 1 by considering f(cid:63), f(uij) and (cid:48) f(ui1), and so aik = aik, a contradiction. Hence i1 + r = ik and thus we get aik = ai1. 13 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: r

text: r

text: a,

text: a

text: a,

text: l

text: m

text: n

text: f

text: a,

text: a,

text: a,

text: l

text: m

text: n

text: f

text: a,

text: a,

text: l

text: m

text: f

text: r

text: r

text: (a)

text: r

text: r

text: a,

text: a,

text: m

text: n

text: f

text: a,

text: a,

text: a,

text: l

text: m

text: n

text: f

text: (v'')

text: a,

text: a,

text: a,

text: l

text: m

text: n

text: f

text: r

text: r

text: (b)

text: Fig.

text: Illustration

text: of

text: the

text: proof

text: of

text: β

text: contains

text: no

text: f

text: as

text: factor.

text: are

text: words

text: of

text: Q

text: where

text: d

text: f

text: By

text: d

text: B(f)

text: and

text: α

text: is

text: a

text: factor

text: of

text: d

text: α,

text: α

text: α,

text: β

text: β

text: and

text: d

text: d

text: f

text: Case

text: i

text: [u

text: u

text: f

text: j

text: If

text: p

text: then

text: β

text: contains

text: the

text: factor

text: a

text: contradiction.

text: Hence

text: p

text: and

text: P

text: p

text: j

text: If

text: i

text: [i

text: u

text: f

text: for

text: all

text: k

text: P

text: then

text: β

text: contains

text: the

text: k

text: factor

text: a

text: contradiction.

text: So

text: there

text: must

text: exist

text: k

text: P

text: such

text: that

text: ik

text: f

text: Since

text: j

text: is

text: the

text: minimal

text: one

text: such

text: that

text: i

text: [u

text: u

text: f

text: i

text: [u

text: u

text: f

text: for

text: any

text: ij

text: ij

text: ik

text: ik

text: such

text: k.

text: So

text: i

text: u

text: i

text: k

text: Let

text: r

text: u

text: u

text: and

text: s

text: u

text: u

text: Obviously

text: f

text: r

text: s.

text: Let

text: α

text: a

text: a

text: be

text: the

text: ik

text: ij

text: ij

text: d

text: factor

text: of

text: α

text: that

text: from

text: the

text: uth

text: bit

text: to

text: (u

text: f

text: bit

text: of

text: α,

text: where

text: d

text: f

text: r.

text: Let

text: −ij

text: ik

text: m

text: i

text: u

text: and

text: n

text: i

text: u

text: Then

text: a

text: a

text: and

text: a

text: a

text: Obviously,

text: α

text: contains

text: k

text: ij

text: j

text: ij

text: m

text: ik

text: n

text: ij

text: no

text: factor

text: f.

text: Denote

text: β

text: α

text: e

text: e

text: If

text: β

text: does

text: not

text: contain

text: factor

text: f,

text: then

text: α

text: and

text: β

text: is

text: m

text: n

text: words

text: for

text: Q

text: where

text: d

text: f

text: r

text: d

text: u

text: d

text: But

text: this

text: is

text: a

text: contradiction

text: d

text: ij

text: to

text: d

text: B(f).

text: Hence

text: β

text: must

text: contain

text: factor

text: f,

text: and

text: so

text: r

text: Suppose

text: the

text: ﬁrst

text: coordinate

text: of

text: this

text: copy

text: of

text: f

text: is

text: v,

text: then

text: v

text: r.

text: Similar

text: to

text: Claim

text: of

text: Subcase

text: we

text: can

text: show

text: that

text: r

text: is

text: even,

text: n

text: m

text: r

text: r

text: and

text: a

text: a

text: This

text: indicate

text: that

text: i

text: i

text: r

text: a

text: a

text: m

text: n

text: j

text: k

text: ik

text: ij

text: and

text: the

text: factor

text: that

text: start

text: from

text: the

text: (u

text: r

text: )th

text: to

text: the

text: (u

text: r

text: f

text: bit

text: of

text: α

text: e

text: e

text: ij

text: ij

text: ik

text: ij

text: is

text: f,

text: and

text: denote

text: it

text: as

text: Assume

text: that

text: i

text: r

text: i

text: Similar

text: to

text: Claim

text: of

text: Subcase

text: we

text: k

text: can

text: show

text: that

text: equations

text: hold

text: for

text: t

text: ik

text: uij

text: r

text: by

text: considering

text: f(uij)

text: and

text: and

text: so

text: aik

text: aik,

text: a

text: contradiction.

text: Hence

text: r

text: ik

text: and

text: thus

text: we

text: get

text: aik

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∈ { } \ { } (cid:54) k 1, 2, . . . , d j , then u = u . j k · · · In the lemmas and theorems of this section, we suppose that f = f f f| | is a bad 1 2 f · · · · · · string and d = B(f); α = a a a and β = b b b are p-critical words for Q (f), 0 1 2 d0 1 2 d0 d0 (cid:54) (cid:54)∈ a = b and α = α + e V (Q (f)) for j = 1, 2, . . . , p. ij ij j ij d0 ∈ { } ∈ { } \ { } Lemma 3.1. For any k 1, 2, . . . , p , there exists some one j 1, 2, . . . , p k such ∈ | | − that i [u , u + f 1]. k ij ij ≥ Proof. We distinguish three cases: p = 2, p = 3 and p 4. ∈ | | − ∈ | | − Obviously if p = 2, then i [u , u + f 1] and i [u , u + f 1], otherwise 1 i2 i2 2 i1 i1 β contains the factor f. Let p = 3. On the contrary we distinguish the following three cases: (cid:54)∈ | | − (cid:54)∈ | | − i [u , u + f 1] and i [u , u + f 1], 1 i2 i2 1 i3 i3 (cid:54)∈ | | − (cid:54)∈ | | − i [u , u + f 1] and i [u , u + f 1] and 2 i1 i1 2 i3 i3 (cid:54)∈ | | − (cid:54)∈ | | − i [u , u + f 1] and i [u , u + f 1]. 3 i1 i1 3 i2 i2 We only show that the ﬁrst and second cases do not hold since the third one can be ∈ | |− proved similarly as the ﬁrst one. In the ﬁrst case, we claim that i [u , u + f 1] and 2 i3 i3 ∈ | |− (cid:48) (cid:48) i [u , u + f 1], otherwise β contains f as a factor, a contradiction. Let α and β be 3 i2 i2 (cid:48) the strings obtained by deleting the ﬁrst to ith bit of α and β, respectively. Then α and 1 (cid:48) (cid:48) − β are 2-critical words for Q (cid:48)(f), where d = d i , it is a contradiction to d = B(f). d 0 1 0 | | − In the second case, obviously the factor that starts from the uth to (u + f 1)th bit of i1 i1 β is f, it is a contradiction. ≥ ∈ { } (cid:54)∈ | | − Now we consider p 4. Assume for some one k 1, 2, . . . , p , i [u , u + f 1] k ij ij ∈ { } \ { } | | − ∈ { − } holds for all j 1, 2, . . . , p k . Then u + f 1 < i for all j X = 1, . . . , k 1 ij k ∈ { } ∅ ∅ and u > i for all j Y = k + 1, . . . , p . Note that X = if k = 1, and Y = if ij k ≥ | | | | k = p. Since p 4, at least one of X and Y not less than 2. Without loss of generality, | | ≥ (cid:48) (cid:48) suppose Y 2. Letting α and β be the strings obtained by deleting the ﬁrst bit to (cid:48) (cid:48) (cid:48) the ith bit of α and β respectively, then α and β are p -critical words for Q (cid:48)(f), where k d (cid:48) − (cid:48) − (cid:4) p = p k and d = d i , it is a contradiction to that d = B(f). 0 k 0 Theorem 3.2. If there exist p-critical words for Q (f), then p = 2 or p = 3. d0 ∈ { } ∈ | | − Proof. Letting k = 1, there must exist j 2, . . . , p such that i [u , u + f 1] by 1 ij ij Lemma 3.1. Suppose that j be the smallest one among all such coordinates. According | | − to i belongs to [u , u + f 1] or not, we distinguish two cases. j i1 i1 ∈ | | − Case 1. i [u , u + f 1]. j i1 i1 There are two subcases: u < u or u > u . i1 ij i1 ij 7

text: k

text: d

text: j

text: then

text: u

text: u

text: j

text: k

text: In

text: the

text: lemmas

text: and

text: theorems

text: of

text: this

text: section,

text: we

text: suppose

text: that

text: f

text: f

text: f

text: f|

text: is

text: a

text: bad

text: f

text: string

text: and

text: d

text: B(f);

text: α

text: a

text: a

text: a

text: and

text: β

text: b

text: b

text: b

text: are

text: p-critical

text: words

text: for

text: Q

text: (f),

text: a

text: b

text: and

text: α

text: α

text: e

text: V

text: (Q

text: (f))

text: for

text: j

text: p.

text: ij

text: ij

text: j

text: ij

text: Lemma

text: For

text: any

text: k

text: p

text: there

text: exists

text: some

text: one

text: j

text: p

text: k

text: such

text: that

text: i

text: [u

text: u

text: f

text: k

text: ij

text: ij

text: Proof.

text: We

text: distinguish

text: three

text: cases:

text: p

text: p

text: and

text: p

text: Obviously

text: if

text: p

text: then

text: i

text: [u

text: u

text: f

text: and

text: i

text: [u

text: u

text: f

text: otherwise

text: β

text: contains

text: the

text: factor

text: f.

text: Let

text: p

text: On

text: the

text: contrary

text: we

text: distinguish

text: the

text: following

text: three

text: cases:

text: i

text: [u

text: u

text: f

text: and

text: i

text: [u

text: u

text: f

text: i

text: [u

text: u

text: f

text: and

text: i

text: [u

text: u

text: f

text: and

text: i

text: [u

text: u

text: f

text: and

text: i

text: [u

text: u

text: f

text: We

text: only

text: show

text: that

text: the

text: ﬁrst

text: and

text: second

text: cases

text: do

text: not

text: hold

text: since

text: the

text: third

text: one

text: can

text: be

text: proved

text: similarly

text: as

text: the

text: ﬁrst

text: one.

text: In

text: the

text: ﬁrst

text: case,

text: we

text: claim

text: that

text: i

text: [u

text: u

text: f

text: and

text: i

text: [u

text: u

text: f

text: otherwise

text: β

text: contains

text: f

text: as

text: a

text: factor,

text: a

text: contradiction.

text: Let

text: α

text: and

text: β

text: be

text: the

text: strings

text: obtained

text: by

text: deleting

text: the

text: ﬁrst

text: to

text: ith

text: bit

text: of

text: α

text: and

text: β,

text: respectively.

text: Then

text: α

text: and

text: β

text: are

text: words

text: for

text: Q

text: where

text: d

text: d

text: i

text: it

text: is

text: a

text: contradiction

text: to

text: d

text: B(f).

text: d

text: In

text: the

text: second

text: case,

text: obviously

text: the

text: factor

text: that

text: starts

text: from

text: the

text: uth

text: to

text: (u

text: f

text: bit

text: of

text: β

text: is

text: f,

text: it

text: is

text: a

text: contradiction.

text: Now

text: we

text: consider

text: p

text: Assume

text: for

text: some

text: one

text: k

text: p

text: i

text: [u

text: u

text: f

text: k

text: ij

text: ij

text: holds

text: for

text: all

text: j

text: p

text: k

text: Then

text: u

text: f

text: i

text: for

text: all

text: j

text: X

text: k

text: ij

text: k

text: and

text: u

text: i

text: for

text: all

text: j

text: Y

text: k

text: p

text: Note

text: that

text: X

text: if

text: k

text: and

text: Y

text: if

text: ij

text: k

text: k

text: p.

text: Since

text: p

text: at

text: least

text: one

text: of

text: X

text: and

text: Y

text: not

text: less

text: than

text: Without

text: loss

text: of

text: generality,

text: suppose

text: Y

text: Letting

text: α

text: and

text: β

text: be

text: the

text: strings

text: obtained

text: by

text: deleting

text: the

text: ﬁrst

text: bit

text: to

text: the

text: ith

text: bit

text: of

text: α

text: and

text: β

text: respectively,

text: then

text: α

text: and

text: β

text: are

text: p

text: -critical

text: words

text: for

text: Q

text: where

text: k

text: d

text: p

text: p

text: k

text: and

text: d

text: d

text: i

text: it

text: is

text: a

text: contradiction

text: to

text: that

text: d

text: B(f).

text: k

text: Theorem

text: If

text: there

text: exist

text: p-critical

text: words

text: for

text: Q

text: (f),

text: then

text: p

text: or

text: p

text: Proof.

text: Letting

text: k

text: there

text: must

text: exist

text: j

text: p

text: such

text: that

text: i

text: [u

text: u

text: f

text: by

text: ij

text: ij

text: Lemma

text: Suppose

text: that

text: j

text: be

text: the

text: smallest

text: one

text: among

text: all

text: such

text: coordinates.

text: According

text: to

text: i

text: belongs

text: to

text: [u

text: u

text: f

text: or

text: not,

text: we

text: distinguish

text: two

text: cases.

text: j

text: Case

text: i

text: [u

text: u

text: f

text: j

text: There

text: are

text: two

text: subcases:

text: u

text: u

text: or

text: u

text: u

text: ij

text: ij


text: The number of unit-area triangles in the plane: Theme and variations∗ † ‡ Orit E. Raz Micha Sharir May 27, 2020 Abstract We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n20/9), improving the earlier bound O(n9/4) of Apfelbaum and Sharir [2]. We also consider two special cases of this problem: (i) We show, using a somewhat subtle construction, that if S consists of points on three lines, the number of unit-area triangles that S spans can be Ω(n2), for any triple of lines (it is always O(n2) in this case). (ii) We show that if S is a convex grid of the form A × B, where A, B are convex sets of n1/2 real numbers each (i.e., the sequences of diﬀerences of consecutive elements of A and of B are both strictly increasing), then S determines O(n31/14) unit-area triangles. 1 Introduction In 1967, Oppenheim (see [9]) asked the following question: Given n points in the plane and A > 0, how many triangles spanned by the points can have area A? By applying a scaling transformation, one may assume A = 1 and count the triangles of unit area. Erd˝os √ √ and Purdy [8] showed that a log n × (n/ log n) section of the integer lattice determines Ω(n2 log log n) triangles of the same area. They also showed that the maximum number of such triangles is at most O(n5/2). In 1992, Pach and Sharir [10] improved the bound to O(n7/3), using the Szemer´edi-Trotter theorem [16] (see below) on the number of point-line incidences. More recently, Dumitrescu et al. [4] have further improved the upper bound to O(n44/19) = O(n2.3158), by estimating the number of incidences between the given points and a 4-parameter family of quadratic curves. In a subsequent improvement, Apfelbaum and Sharir [2] have obtained the upper bound O(n9/4+ε), for any ε > 0, which has been slightly improved to O(n9/4) in Apfelbaum [1]. This has been the best known upper bound so far. ∗ Work on this paper by Orit E. Raz and Micha Sharir was supported by Grant 892/13 from the Israel Science Foundation and by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Work by Micha Sharir was also supported by Grant 2012/229 from the U.S.–Israel Binational Science Foundation and by the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University. Part of this research was performed while the authors were visiting the Institute for Pure and Applied Mathematics (IPAM), which is supported by the National Science Foundation. † School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. oritraz@post.tau.ac.il ‡ School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. michas@post.tau.ac.il 1 ##LTLine## ##LTLine## ##LTLine##

text: The

text: number

text: of

text: unit-area

text: triangles

text: in

text: the

text: plane:

text: Theme

text: and

text: variations∗

text: Orit

text: E.

text: Raz

text: Micha

text: Sharir

text: May

text: Abstract

text: We

text: show

text: that

text: the

text: number

text: of

text: unit-area

text: triangles

text: determined

text: by

text: a

text: set

text: S

text: of

text: n

text: points

text: in

text: the

text: plane

text: is

text: improving

text: the

text: earlier

text: bound

text: of

text: Apfelbaum

text: and

text: Sharir

text: We

text: also

text: consider

text: two

text: special

text: cases

text: of

text: this

text: problem:

text: (i)

text: We

text: show,

text: using

text: a

text: somewhat

text: subtle

text: construction,

text: that

text: if

text: S

text: consists

text: of

text: points

text: on

text: three

text: lines,

text: the

text: number

text: of

text: unit-area

text: triangles

text: that

text: S

text: spans

text: can

text: be

text: for

text: any

text: triple

text: of

text: lines

text: (it

text: is

text: always

text: in

text: this

text: case).

text: (ii)

text: We

text: show

text: that

text: if

text: S

text: is

text: a

text: convex

text: grid

text: of

text: the

text: form

text: A

text: B,

text: where

text: A,

text: B

text: are

text: convex

text: sets

text: of

text: real

text: numbers

text: each

text: (i.e.,

text: the

text: sequences

text: of

text: diﬀerences

text: of

text: consecutive

text: elements

text: of

text: A

text: and

text: of

text: B

text: are

text: both

text: strictly

text: increasing),

text: then

text: S

text: determines

text: unit-area

text: triangles.

text: Introduction

text: In

text: Oppenheim

text: (see

text: asked

text: the

text: following

text: question:

text: Given

text: n

text: points

text: in

text: the

text: plane

text: and

text: A

text: how

text: many

text: triangles

text: spanned

text: by

text: the

text: points

text: can

text: have

text: area

text: A?

text: By

text: applying

text: a

text: scaling

text: transformation,

text: one

text: may

text: assume

text: A

text: and

text: count

text: the

text: triangles

text: of

text: unit

text: area.

text: Erd˝os

text: and

text: Purdy

text: showed

text: that

text: a

text: log

text: n

text: (n/

text: log

text: n)

text: section

text: of

text: the

text: integer

text: lattice

text: determines

text: log

text: log

text: n)

text: triangles

text: of

text: the

text: same

text: area.

text: They

text: also

text: showed

text: that

text: the

text: maximum

text: number

text: of

text: such

text: triangles

text: is

text: at

text: most

text: In

text: Pach

text: and

text: Sharir

text: improved

text: the

text: bound

text: to

text: using

text: the

text: Szemer´edi-Trotter

text: theorem

text: (see

text: below)

text: on

text: the

text: number

text: of

text: point-line

text: incidences.

text: More

text: recently,

text: Dumitrescu

text: et

text: al.

text: have

text: further

text: improved

text: the

text: upper

text: bound

text: to

text: by

text: estimating

text: the

text: number

text: of

text: incidences

text: between

text: the

text: given

text: points

text: and

text: a

text: family

text: of

text: quadratic

text: curves.

text: In

text: a

text: subsequent

text: improvement,

text: Apfelbaum

text: and

text: Sharir

text: have

text: obtained

text: the

text: upper

text: bound

text: for

text: any

text: ε

text: which

text: has

text: been

text: slightly

text: improved

text: to

text: in

text: Apfelbaum

text: This

text: has

text: been

text: the

text: best

text: known

text: upper

text: bound

text: so

text: far.

text: Work

text: on

text: this

text: paper

text: by

text: Orit

text: E.

text: Raz

text: and

text: Micha

text: Sharir

text: was

text: supported

text: by

text: Grant

text: from

text: the

text: Israel

text: Science

text: Foundation

text: and

text: by

text: the

text: Israeli

text: Centers

text: of

text: Research

text: Excellence

text: (I-CORE)

text: program

text: (Center

text: No.

text: Work

text: by

text: Micha

text: Sharir

text: was

text: also

text: supported

text: by

text: Grant

text: from

text: the

text: U.S.–Israel

text: Binational

text: Science

text: Foundation

text: and

text: by

text: the

text: Hermann

text: Minkowski-MINERVA

text: Center

text: for

text: Geometry

text: at

text: Tel

text: Aviv

text: University.

text: Part

text: of

text: this

text: research

text: was

text: performed

text: while

text: the

text: authors

text: were

text: visiting

text: the

text: Institute

text: for

text: Pure

text: and

text: Applied

text: Mathematics

text: (IPAM),

text: which

text: is

text: supported

text: by

text: the

text: National

text: Science

text: Foundation.

text: School

text: of

text: Computer

text: Science,

text: Tel

text: Aviv

text: University,

text: Tel

text: Aviv

text: Israel.

text: oritraz@post.tau.ac.il

text: School

text: of

text: Computer

text: Science,

text: Tel

text: Aviv

text: University,

text: Tel

text: Aviv

text: Israel.

text: michas@post.tau.ac.il

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: In this paper we further improve the bound to O(n20/9). Our proof uses a diﬀerent re- duction of the problem to an incidence problem, this time to incidences between points and R two-dimensional algebraic surfaces in 4. A very recent result of Solymosi and De Zeeuw [15] provides a sharp upper bound for the number of such incidences, similar to the Szemer´edi– Trotter bound, provided that the points, surfaces, and incidences satisfy certain fairly restric- tive assumptions. The main novel features of our analysis are thus (a) the reduction of the problem to this speciﬁc type of incidence counting, and (b) showing that the assumptions of [15] are satisﬁed in our context. After establishing this main result, we consider two variations, in which better bounds can be obtained. We ﬁrst consider the case where the input points lie on three arbitrary lines. It is easily checked that in this case there are at most O(n2) unit-area triangles. We show, in Section , that this bound is tight, and can be attained for any triple of lines. Rather than just presenting the construction, we spend some time showing its connection to a more general problem studied by Elekes and R´onyai [6] (see also the recent developments in [7, 11, 12]), involving the zero set of a trivariate polynomial within a triple Cartesian product. Skipping over the details, which are spelled out in Section , it turns out that the case of unit-area triangles determined by points lying on three lines is an exceptional case in the theory of Elekes and R´onyai [6], which then leads to a construction with Θ(n2) unit-area triangles. Another variation that we consider concerns unit-area triangles spanned by points in a convex grid. That is, the input set is of the form A × B, where A and B are convex sets of n1/2 real numbers each; a set of real numbers is called convex if the diﬀerences between consecutive elements form a strictly increasing sequence. We show that in this case A × B determine O(n31/14) unit-area triangles. The main technical tool used in our analysis is a result of Schoen and Shkredov [13] on diﬀerence sets involving convex sets.1 2 Unit-area triangles in the plane Theorem 1. The number of unit-area triangles spanned by n points in the plane is O(n20/9). We ﬁrst recall the Szemer´edi–Trotter theorem [16] on point-line incidences in the plane. Theorem 2 (Szemer´edi and Trotter [16]). (i) The number of incidences between M distinct points and N distinct lines in the plane is O(M2/3N2/3 +M +N). (ii) Given M distinct points in the plane and a parameter k ≤ M, the number of lines incident to at least k of the points is O(M2/k3 + M/k). Both bounds are tight in the worst case. Proof of Theorem 1. Let S be a set of n points in the plane, and let U denote the set of unit-area triangles spanned by S. For any pair of distinct points, p (cid:54)= q ∈ S, let (cid:96) denote the pq line through p and q. The points r for which the triangle pqr has unit area lie on two lines − (cid:48) − (cid:96) , (cid:96)+ parallel to (cid:96) and at distance 2/|pq| from (cid:96) on either side. We let (cid:96) ∈ {(cid:96) , (cid:96)+ } be pq pq pq (cid:88) pq pq pq pq the line that lies to the left of the vector p(cid:126)q. We then have 1 (cid:48) |U| = |(cid:96) ∩ S|. 3 ∈ × (cid:54) pq (p,q) S S, p=q 1Very recently, in work in progress, jointly with I. Shkredov, the bound is further improved in this case. 2 ##LTLine## ##LTLine##

text: In

text: this

text: paper

text: we

text: further

text: improve

text: the

text: bound

text: to

text: Our

text: proof

text: uses

text: a

text: diﬀerent

text: re-

text: duction

text: of

text: the

text: problem

text: to

text: an

text: incidence

text: problem,

text: this

text: time

text: to

text: incidences

text: between

text: points

text: and

text: R

text: two-dimensional

text: algebraic

text: surfaces

text: in

text: A

text: very

text: recent

text: result

text: of

text: Solymosi

text: and

text: De

text: Zeeuw

text: provides

text: a

text: sharp

text: upper

text: bound

text: for

text: the

text: number

text: of

text: such

text: incidences,

text: similar

text: to

text: the

text: Szemer´edi–

text: Trotter

text: bound,

text: provided

text: that

text: the

text: points,

text: surfaces,

text: and

text: incidences

text: satisfy

text: certain

text: fairly

text: restric-

text: tive

text: assumptions.

text: The

text: main

text: novel

text: features

text: of

text: our

text: analysis

text: are

text: thus

text: (a)

text: the

text: reduction

text: of

text: the

text: problem

text: to

text: this

text: speciﬁc

text: type

text: of

text: incidence

text: counting,

text: and

text: (b)

text: showing

text: that

text: the

text: assumptions

text: of

text: are

text: satisﬁed

text: in

text: our

text: context.

text: After

text: establishing

text: this

text: main

text: result,

text: we

text: consider

text: two

text: variations,

text: in

text: which

text: better

text: bounds

text: can

text: be

text: obtained.

text: We

text: ﬁrst

text: consider

text: the

text: case

text: where

text: the

text: input

text: points

text: lie

text: on

text: three

text: arbitrary

text: lines.

text: It

text: is

text: easily

text: checked

text: that

text: in

text: this

text: case

text: there

text: are

text: at

text: most

text: unit-area

text: triangles.

text: We

text: show,

text: in

text: Section

text: that

text: this

text: bound

text: is

text: tight,

text: and

text: can

text: be

text: attained

text: for

text: any

text: triple

text: of

text: lines.

text: Rather

text: than

text: just

text: presenting

text: the

text: construction,

text: we

text: spend

text: some

text: time

text: showing

text: its

text: connection

text: to

text: a

text: more

text: general

text: problem

text: studied

text: by

text: Elekes

text: and

text: R´onyai

text: (see

text: also

text: the

text: recent

text: developments

text: in

text: involving

text: the

text: zero

text: set

text: of

text: a

text: trivariate

text: polynomial

text: within

text: a

text: triple

text: Cartesian

text: product.

text: Skipping

text: over

text: the

text: details,

text: which

text: are

text: spelled

text: out

text: in

text: Section

text: it

text: turns

text: out

text: that

text: the

text: case

text: of

text: unit-area

text: triangles

text: determined

text: by

text: points

text: lying

text: on

text: three

text: lines

text: is

text: an

text: exceptional

text: case

text: in

text: the

text: theory

text: of

text: Elekes

text: and

text: R´onyai

text: which

text: then

text: leads

text: to

text: a

text: construction

text: with

text: unit-area

text: triangles.

text: Another

text: variation

text: that

text: we

text: consider

text: concerns

text: unit-area

text: triangles

text: spanned

text: by

text: points

text: in

text: a

text: convex

text: grid.

text: That

text: is,

text: the

text: input

text: set

text: is

text: of

text: the

text: form

text: A

text: B,

text: where

text: A

text: and

text: B

text: are

text: convex

text: sets

text: of

text: real

text: numbers

text: each;

text: a

text: set

text: of

text: real

text: numbers

text: is

text: called

text: convex

text: if

text: the

text: diﬀerences

text: between

text: consecutive

text: elements

text: form

text: a

text: strictly

text: increasing

text: sequence.

text: We

text: show

text: that

text: in

text: this

text: case

text: A

text: B

text: determine

text: unit-area

text: triangles.

text: The

text: main

text: technical

text: tool

text: used

text: in

text: our

text: analysis

text: is

text: a

text: result

text: of

text: Schoen

text: and

text: Shkredov

text: on

text: diﬀerence

text: sets

text: involving

text: convex

text: Unit-area

text: triangles

text: in

text: the

text: plane

text: Theorem

text: The

text: number

text: of

text: unit-area

text: triangles

text: spanned

text: by

text: n

text: points

text: in

text: the

text: plane

text: is

text: We

text: ﬁrst

text: recall

text: the

text: Szemer´edi–Trotter

text: theorem

text: on

text: point-line

text: incidences

text: in

text: the

text: plane.

text: Theorem

text: (Szemer´edi

text: and

text: Trotter

text: (i)

text: The

text: number

text: of

text: incidences

text: between

text: M

text: distinct

text: points

text: and

text: N

text: distinct

text: lines

text: in

text: the

text: plane

text: is

text: +M

text: +N).

text: (ii)

text: Given

text: M

text: distinct

text: points

text: in

text: the

text: plane

text: and

text: a

text: parameter

text: k

text: M,

text: the

text: number

text: of

text: lines

text: incident

text: to

text: at

text: least

text: k

text: of

text: the

text: points

text: is

text: M/k).

text: Both

text: bounds

text: are

text: tight

text: in

text: the

text: worst

text: case.

text: Proof

text: of

text: Theorem

text: Let

text: S

text: be

text: a

text: set

text: of

text: n

text: points

text: in

text: the

text: plane,

text: and

text: let

text: U

text: denote

text: the

text: set

text: of

text: unit-area

text: triangles

text: spanned

text: by

text: S.

text: For

text: any

text: pair

text: of

text: distinct

text: points,

text: p

text: q

text: S,

text: let

text: denote

text: the

text: pq

text: line

text: through

text: p

text: and

text: q.

text: The

text: points

text: r

text: for

text: which

text: the

text: triangle

text: pqr

text: has

text: unit

text: area

text: lie

text: on

text: two

text: lines

text: parallel

text: to

text: and

text: at

text: distance

text: from

text: on

text: either

text: side.

text: We

text: let

text: be

text: pq

text: pq

text: pq

text: pq

text: pq

text: pq

text: pq

text: the

text: line

text: that

text: lies

text: to

text: the

text: left

text: of

text: the

text: vector

text: We

text: then

text: have

text: |U|

text: S|.

text: pq

text: (p,q)

text: S

text: S,

text: p=q

text: recently,

text: in

text: work

text: in

text: progress,

text: jointly

text: with

text: I.

text: Shkredov,

text: the

text: bound

text: is

text: further

text: improved

text: in

text: this

text: case.

text: ##LTLine##

text: ##LTLine##


text: (cid:16) (cid:17) this number of points of P ); here we do not use the fact that we are interested only in rich-rich triangles. We thus obtain the following lemma. Lemma 14. The number of rich-rich triangles spanned by P is O n7/2 + n2 . k4 Poor-rich and rich-poor triangles. Without loss of generality, it suﬃces to consider only poor-rich triangles. Put − H := {h ∈ H | 2i 1 ≤ w(h) < 2i}, i for i = 1, . . . , log k, and(cid:83) S≥ := {q ∈ B3 | w(q) ≥ k}. k That is, by deﬁnition, H is the collection of k-poor planes of H, and S≥ is the set of k-rich i i − k points of B3. Since each element of H has multiplicity at least 2i 1, we have the trivial bound − i |H | ≤ n3/2/2i 1. i Consider the family of horizontal planes F := {ξ } ∈ , where ξ := {z = z }. Our strategy z z B z0 0 is to restrict S≥ and H , for i = 1, . . . , log k, to the planes ξ ∈ F, and apply the Szemer´edi– k i Trotter incidence bound (see Theorem 2) to the resulting collections of points and intersection lines, on each such ξ. Note that two distinct planes h , h ∈ H restricted to ξ, become two 1 2 distinct lines in ξ. Indeed, each plane of H contains a line parallel to (1, 1, 1), and two such (cid:0) (cid:1) (cid:0) (cid:1) planes, that additionally share a horizontal line within ξ, must be identical. Using the Remark following Lemma 13, we have that the number of rich points (x, y, z ) ∈ S≥ , with z ﬁxed, is 0 k 0 O n3/2/k2 ; that is, |S≥ ∩ ξ | = O n3/2/k2 for every ﬁxed z . k z0 0 The number of incidences between the points of S≥ and the poor planes of H, counted k (cid:88) (cid:88) with multiplicity (of the planes) is at most log k 2i · I(S≥ ∩ ξ , H ), k z iz ∈ z (cid:32)B i=1 (cid:33) (cid:32) (cid:33)  (cid:88) (cid:88) where H := {h ∩ ξ | h ∈ H }. By Theorem 2, this is at most iz z i   log k n3/2 2/3 n3/2 2/3 n3/2 n3/2 2i · O (cid:32) − + + − (cid:33) ∈ (cid:88) k2 (cid:88) 2i 1 (cid:88) k2 2i 1 z B i=1 (cid:32) n2 log k n3/2 log(cid:33)k = (cid:88) O 2i/3 + 2i + n3/2 log k ∈ k4/3 k2 z B i=1 i=1 (cid:32) n2 n3/2 (cid:33) = O + + n3/2 log k ∈ k k z B n5/2 =O + n2 log k . k This bounds the number of poor-rich triangles spanned by P . Clearly, using a symmetric argument, this bound also applies to the number of rich-poor triangles spanned by P . We thus (cid:32) (cid:33) obtain the following lemma. Lemma 15. The number of poor-rich triangles and of rich-poor triangles spanned by P is n5/2 O + n2 log k . k 17 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: this

text: number

text: of

text: points

text: of

text: P

text: here

text: we

text: do

text: not

text: use

text: the

text: fact

text: that

text: we

text: are

text: interested

text: only

text: in

text: rich-rich

text: triangles.

text: We

text: thus

text: obtain

text: the

text: following

text: lemma.

text: Lemma

text: The

text: number

text: of

text: rich-rich

text: triangles

text: spanned

text: by

text: P

text: is

text: O

text: Poor-rich

text: and

text: rich-poor

text: triangles.

text: Without

text: loss

text: of

text: generality,

text: it

text: suﬃces

text: to

text: consider

text: only

text: poor-rich

text: triangles.

text: Put

text: H

text: {h

text: H

text: w(h)

text: i

text: for

text: i

text: log

text: k,

text: S≥

text: {q

text: w(q)

text: k}.

text: k

text: That

text: is,

text: by

text: deﬁnition,

text: H

text: is

text: the

text: collection

text: of

text: k-poor

text: planes

text: of

text: H,

text: and

text: S≥

text: is

text: the

text: set

text: of

text: k-rich

text: i

text: i

text: k

text: points

text: of

text: Since

text: each

text: element

text: of

text: H

text: has

text: multiplicity

text: at

text: least

text: we

text: have

text: the

text: trivial

text: bound

text: i

text: |H

text: i

text: Consider

text: the

text: family

text: of

text: horizontal

text: planes

text: F

text: {ξ

text: where

text: ξ

text: {z

text: z

text: Our

text: strategy

text: z

text: z

text: B

text: is

text: to

text: restrict

text: S≥

text: and

text: H

text: for

text: i

text: log

text: k,

text: to

text: the

text: planes

text: ξ

text: F,

text: and

text: apply

text: the

text: Szemer´edi–

text: k

text: i

text: Trotter

text: incidence

text: bound

text: (see

text: Theorem

text: to

text: the

text: resulting

text: collections

text: of

text: points

text: and

text: intersection

text: lines,

text: on

text: each

text: such

text: ξ.

text: Note

text: that

text: two

text: distinct

text: planes

text: h

text: h

text: H

text: restricted

text: to

text: ξ,

text: become

text: two

text: distinct

text: lines

text: in

text: ξ.

text: Indeed,

text: each

text: plane

text: of

text: H

text: contains

text: a

text: line

text: parallel

text: to

text: and

text: two

text: such

text: planes,

text: that

text: additionally

text: share

text: a

text: horizontal

text: line

text: within

text: ξ,

text: must

text: be

text: identical.

text: Using

text: the

text: Remark

text: following

text: Lemma

text: we

text: have

text: that

text: the

text: number

text: of

text: rich

text: points

text: (x,

text: y,

text: z

text: S≥

text: with

text: z

text: ﬁxed,

text: is

text: k

text: O

text: that

text: is,

text: |S≥

text: ξ

text: O

text: for

text: every

text: ﬁxed

text: z

text: k

text: The

text: number

text: of

text: incidences

text: between

text: the

text: points

text: of

text: S≥

text: and

text: the

text: poor

text: planes

text: of

text: H,

text: counted

text: k

text: with

text: multiplicity

text: (of

text: the

text: planes)

text: is

text: at

text: most

text: log

text: k

text: I(S≥

text: ξ

text: H

text: k

text: z

text: iz

text: z

text: where

text: H

text: {h

text: ξ

text: h

text: H

text: By

text: Theorem

text: this

text: is

text: at

text: most

text: iz

text: z

text: i

text: log

text: k

text: O

text: z

text: B

text: log

text: k

text: O

text: log

text: k

text: z

text: B

text: O

text: log

text: k

text: k

text: k

text: z

text: B

text: =O

text: log

text: k

text: k

text: This

text: bounds

text: the

text: number

text: of

text: poor-rich

text: triangles

text: spanned

text: by

text: P

text: Clearly,

text: using

text: a

text: symmetric

text: argument,

text: this

text: bound

text: also

text: applies

text: to

text: the

text: number

text: of

text: rich-poor

text: triangles

text: spanned

text: by

text: P

text: We

text: thus

text: obtain

text: the

text: following

text: lemma.

text: Lemma

text: The

text: number

text: of

text: poor-rich

text: triangles

text: and

text: of

text: rich-poor

text: triangles

text: spanned

text: by

text: P

text: is

text: O

text: log

text: k

text: k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Poor-poor triangles. Again we are going to use Theorem 2. For i = 1, . . . , log k, put − S := {q ∈ B3 | 2i 1 ≤ w(q) < 2i}, i (cid:48) (cid:48) and let S , H be the respective (orthogonal) projections of S , H to the plane η := {x+y+z = i i (cid:48) i i 1}. Note that H is a collection of lines in η. Moreover, arguing as above, two distinct planes of i (cid:48) H project to two distinct lines of H , and thus the multiplicity of the lines is the same as the i i multiplicity of the original planes of H . Similarly, a point q ∈ S with multiplicity t projects (cid:48) (cid:48) i i to a point q ∈ S with multiplicity t (by construction, there are exactly t points of S that (cid:48) i (cid:48) i − project to q ). These observations allow us to use here too the trivial bounds |S | ≤ n3/2/2i 1, (cid:48) − i |H | ≤ n3/2/2i 1, for i = 1, . . . , log k. i (cid:48) (cid:48) Applying Theorem 2 to the collections S , H in η, for i, j = 1, . . . , log k, taking under i j account the multiplicity of the points and of the lines in these collections, we obtain that the number of incidences between the poor points and the poor planes, countedwith the (cid:32) (cid:33) (cid:32) (cid:33) appropria(cid:88)te multiplicity, is at m(cid:88)ost   log k (cid:48) (cid:48) log k n3/2 2/3 n3/2 2/3 n3/2 n3/2 2i+j · I(S , H ) =  2i+j · O − − + − + − i j (cid:88) 2i 1 (cid:88)2j (cid:0)1 (cid:1) 2i 1 2j 1 i,j=1 i,j=1  log k k = O (cid:16) n2 2(i+j)/3 + n3(cid:17)/2 2i + 2j i,j=1 i,j=1 = O n2k2/3 + n3/2k log k . (cid:0) (cid:1) Thus, we obtain the following lemma. Lemma 16. The number of poor-poor triangles spanned by P is O n2k2/3 + n3/2k log k . (cid:32) (cid:33) In summary, the number of unit-area triangles spanned by P is n7/2 n5/2 O + + n2k2/3 + n3/2k log k . (11) k4 k Setting k = n9/28 makes this bound O(n31/14), and Theorem 11 follows. Acknowledgment. We are grateful to Frank de Zeeuw for several very helpful comments that simpliﬁed some parts of the analysis. References [1] R. Apfelbaum, Geometric Incidences and Repeated Conﬁgurations, Ph.D. Dissertation, School of Computer Science, Tel Aviv University, 2013. [2] R. Apfelbaum and M. Sharir, An improved bound on the number of unit-area triangles, Discrete Comput. Geom. 44 (2010), 753–761. 18 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Poor-poor

text: triangles.

text: Again

text: we

text: are

text: going

text: to

text: use

text: Theorem

text: For

text: i

text: log

text: k,

text: put

text: S

text: {q

text: w(q)

text: i

text: and

text: let

text: S

text: H

text: be

text: the

text: respective

text: (orthogonal)

text: projections

text: of

text: S

text: H

text: to

text: the

text: plane

text: η

text: {x+y+z

text: i

text: i

text: i

text: i

text: Note

text: that

text: H

text: is

text: a

text: collection

text: of

text: lines

text: in

text: η.

text: Moreover,

text: arguing

text: as

text: above,

text: two

text: distinct

text: planes

text: of

text: i

text: H

text: project

text: to

text: two

text: distinct

text: lines

text: of

text: H

text: and

text: thus

text: the

text: multiplicity

text: of

text: the

text: lines

text: is

text: the

text: same

text: as

text: the

text: i

text: i

text: multiplicity

text: of

text: the

text: original

text: planes

text: of

text: H

text: Similarly,

text: a

text: point

text: q

text: S

text: with

text: multiplicity

text: t

text: projects

text: i

text: i

text: to

text: a

text: point

text: q

text: S

text: with

text: multiplicity

text: t

text: (by

text: construction,

text: there

text: are

text: exactly

text: t

text: points

text: of

text: S

text: that

text: i

text: i

text: project

text: to

text: q

text: These

text: observations

text: allow

text: us

text: to

text: use

text: here

text: too

text: the

text: trivial

text: bounds

text: |S

text: i

text: |H

text: for

text: i

text: log

text: k.

text: i

text: Applying

text: Theorem

text: to

text: the

text: collections

text: S

text: H

text: in

text: η,

text: for

text: i,

text: j

text: log

text: k,

text: taking

text: under

text: i

text: j

text: account

text: the

text: multiplicity

text: of

text: the

text: points

text: and

text: of

text: the

text: lines

text: in

text: these

text: collections,

text: we

text: obtain

text: that

text: the

text: number

text: of

text: incidences

text: between

text: the

text: poor

text: points

text: and

text: the

text: poor

text: planes,

text: countedwith

text: the

text: multiplicity,

text: is

text: at

text: log

text: k

text: log

text: k

text: I(S

text: H

text: O

text: i

text: j

text: log

text: k

text: k

text: O

text: O

text: log

text: k

text: Thus,

text: we

text: obtain

text: the

text: following

text: lemma.

text: Lemma

text: The

text: number

text: of

text: poor-poor

text: triangles

text: spanned

text: by

text: P

text: is

text: O

text: log

text: k

text: In

text: summary,

text: the

text: number

text: of

text: unit-area

text: triangles

text: spanned

text: by

text: P

text: is

text: O

text: log

text: k

text: k

text: Setting

text: k

text: makes

text: this

text: bound

text: and

text: Theorem

text: follows.

text: Acknowledgment.

text: We

text: are

text: grateful

text: to

text: Frank

text: de

text: Zeeuw

text: for

text: several

text: very

text: helpful

text: comments

text: that

text: simpliﬁed

text: some

text: parts

text: of

text: the

text: analysis.

text: References

text: R.

text: Apfelbaum,

text: Geometric

text: Incidences

text: and

text: Repeated

text: Conﬁgurations,

text: Ph.D.

text: Dissertation,

text: School

text: of

text: Computer

text: Science,

text: Tel

text: Aviv

text: University,

text: R.

text: Apfelbaum

text: and

text: M.

text: Sharir,

text: An

text: improved

text: bound

text: on

text: the

text: number

text: of

text: unit-area

text: triangles,

text: Discrete

text: Comput.

text: Geom.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: It suﬃces to consider only triangles pqr of U, that have the property that at least one of the three lines (cid:96) , (cid:96) , (cid:96) is incident to at most n1/2 points of S, because the number of pq pr qr triangles in U that do not have this property is O(n3/2). Indeed, by Theorem 2(ii), there exist R at most O(n1/2) lines in 2, such that each contains at least n1/2 points of S. Since every triple of those lines supports (the edges of) at most one triangle (some of the lines might be mutually parallel, and some triples might intersect at points that do not belong to S), these lines support in total at most O(n3/2) triangles, and, in particular, at most O(n3/2) triangles of U. Since this number is subsumed in the asserted bound on |U|, we can therefore ignore such triangles in our analysis. In what follows, U denotes the set of the remaining unit-area triangles. We charge each of the surviving unit-area(cid:88)triangles pqr to one of its sides, say pq, such that (cid:96) contains at most n1/2 points of S. That is, we have pq (cid:48) |U| ≤ |(cid:96) ∩ S|, pq ∈ × ∗ (p,q) (S S) ∗ where (S × S) denotes the subset of pairs (p, q) ∈ S × S, such that p (cid:54)= q, and the line (cid:96) is pq incident to at most n1/2 points of S. (cid:48) A major problem in estimating |U| is that the lines (cid:96) , for p, q ∈ S, are not necessarily pq distinct, and the analysis has to take into account the (possibly large) multiplicity of these lines. (If the lines were distinct then |U| would be bounded by the number of incidences between n(n − 1) lines and n points, which is O(n2) — see Theorem 2(i).) Let L denote the collection (cid:48) ∗ of lines {(cid:96)pq | (p, q) ∈ (S × S) } (without(cid:88)multiplicity). Fo(cid:48)r (cid:96) ∈ L, we deﬁne (S × S)(cid:96) to be the set of all pairs (p, q) ∈ S × S, with p (cid:54)= q, and for which (cid:96) = (cid:96). We then have pq |U| ≤ |(cid:96) ∩ S||(S × S) |. (cid:96) ∈ (cid:96) L Fix some integer parameter k ≤ n1/2, to be set later, and partition L into the sets − L = {(cid:96) ∈ L | |(cid:96) ∩ S| < k}, L+ = {(cid:96) ∈ L | k ≤ |(cid:96) ∩ S| ≤ n/k}, L++ = {(cid:96) ∈ L | |(cid:96) ∩ S| > n/k}. (cid:88) (cid:88) (cid:88) We have |U| ≤ |(cid:96) ∩ S||(cid:80)(S × S) | + |(cid:96) ∩ S||(S × S) | +(cid:80) |(cid:96) ∩ S||(S × S) |. (cid:96) (cid:96) (cid:96) ∈ − ∈ ∈ (cid:96) L (cid:96) L+ (cid:96) L++ The ﬁrst sum is at most k ∈ − |(S × S) | ≤ kn2, because ∈ − |(S × S) | is at most |(S × ∗ (cid:96) L (cid:96) (cid:96) L (cid:96) S) | ≤ |S × S| = n2. The same (asymptotic) bound also holds for the the third sum. Indeed, since n/k ≥ n1/2, the number of lines in L++ is at most O(k), as follows from Theorem 2(ii), and, for each (cid:96) ∈ L++, we have |(cid:96)∩S| ≤ n and |(S ×S) | ≤ n (for any p ∈ S, (cid:96) ∈ L, there exists (cid:48) (cid:96) at most one point q ∈ S, such that (cid:96) = (cid:96)). This yields a total of at most O(n2k) unit-area pq triangles. It therefore remains to bound the second sum, over L+.     Applying the Cauchy-Schwarz in(cid:88)equality to the seco(cid:88)nd sum, it follows that     1/2 1/2 |U| ≤ O(n2k) + |(cid:96) ∩ S|2 |(S × S) |2 . (cid:96) ∈ ∈ (cid:96) L+ (cid:96) L+ 3

text: It

text: suﬃces

text: to

text: consider

text: only

text: triangles

text: pqr

text: of

text: U,

text: that

text: have

text: the

text: property

text: that

text: at

text: least

text: one

text: of

text: the

text: three

text: lines

text: is

text: incident

text: to

text: at

text: most

text: points

text: of

text: S,

text: because

text: the

text: number

text: of

text: pq

text: pr

text: qr

text: triangles

text: in

text: U

text: that

text: do

text: not

text: have

text: this

text: property

text: is

text: Indeed,

text: by

text: Theorem

text: there

text: exist

text: R

text: at

text: most

text: lines

text: in

text: such

text: that

text: each

text: contains

text: at

text: least

text: points

text: of

text: S.

text: Since

text: every

text: triple

text: of

text: those

text: lines

text: supports

text: (the

text: edges

text: of)

text: at

text: most

text: one

text: triangle

text: (some

text: of

text: the

text: lines

text: might

text: be

text: mutually

text: parallel,

text: and

text: some

text: triples

text: might

text: intersect

text: at

text: points

text: that

text: do

text: not

text: belong

text: to

text: S),

text: these

text: lines

text: support

text: in

text: total

text: at

text: most

text: triangles,

text: and,

text: in

text: particular,

text: at

text: most

text: triangles

text: of

text: U.

text: Since

text: this

text: number

text: is

text: subsumed

text: in

text: the

text: asserted

text: bound

text: on

text: |U|,

text: we

text: can

text: therefore

text: ignore

text: such

text: triangles

text: in

text: our

text: analysis.

text: In

text: what

text: follows,

text: U

text: denotes

text: the

text: set

text: of

text: the

text: remaining

text: unit-area

text: triangles.

text: We

text: charge

text: each

text: of

text: the

text: surviving

text: pqr

text: to

text: one

text: of

text: its

text: sides,

text: say

text: pq,

text: such

text: that

text: contains

text: at

text: most

text: points

text: of

text: S.

text: That

text: is,

text: we

text: have

text: pq

text: |U|

text: S|,

text: pq

text: (p,q)

text: (S

text: S)

text: where

text: (S

text: S)

text: denotes

text: the

text: subset

text: of

text: pairs

text: (p,

text: q)

text: S

text: S,

text: such

text: that

text: p

text: q,

text: and

text: the

text: line

text: is

text: pq

text: incident

text: to

text: at

text: most

text: points

text: of

text: S.

text: A

text: major

text: problem

text: in

text: estimating

text: |U|

text: is

text: that

text: the

text: lines

text: for

text: p,

text: q

text: S,

text: are

text: not

text: necessarily

text: pq

text: distinct,

text: and

text: the

text: analysis

text: has

text: to

text: take

text: into

text: account

text: the

text: (possibly

text: large)

text: multiplicity

text: of

text: these

text: lines.

text: (If

text: the

text: lines

text: were

text: distinct

text: then

text: |U|

text: would

text: be

text: bounded

text: by

text: the

text: number

text: of

text: incidences

text: between

text: n(n

text: lines

text: and

text: n

text: points,

text: which

text: is

text: see

text: Theorem

text: Let

text: L

text: denote

text: the

text: collection

text: of

text: lines

text: (p,

text: q)

text: (S

text: S)

text: L,

text: we

text: deﬁne

text: (S

text: to

text: be

text: the

text: set

text: of

text: all

text: pairs

text: (p,

text: q)

text: S

text: S,

text: with

text: p

text: q,

text: and

text: for

text: which

text: We

text: then

text: have

text: pq

text: |U|

text: S||(S

text: S)

text: L

text: Fix

text: some

text: integer

text: parameter

text: k

text: to

text: be

text: set

text: later,

text: and

text: partition

text: L

text: into

text: the

text: sets

text: L

text: L

text: S|

text: k},

text: L+

text: L

text: k

text: S|

text: n/k},

text: L++

text: L

text: S|

text: n/k}.

text: We

text: have

text: |U|

text: S)

text: S||(S

text: S)

text: S||(S

text: S)

text: L

text: L+

text: L++

text: The

text: ﬁrst

text: sum

text: is

text: at

text: most

text: k

text: |(S

text: S)

text: because

text: |(S

text: S)

text: is

text: at

text: most

text: |(S

text: L

text: L

text: S)

text: |S

text: S|

text: The

text: same

text: (asymptotic)

text: bound

text: also

text: holds

text: for

text: the

text: the

text: third

text: sum.

text: Indeed,

text: since

text: n/k

text: the

text: number

text: of

text: lines

text: in

text: L++

text: is

text: at

text: most

text: O(k),

text: as

text: follows

text: from

text: Theorem

text: and,

text: for

text: each

text: L++,

text: we

text: have

text: n

text: and

text: |(S

text: ×S)

text: n

text: (for

text: any

text: p

text: S,

text: L,

text: there

text: exists

text: at

text: most

text: one

text: point

text: q

text: S,

text: such

text: that

text: This

text: yields

text: a

text: total

text: of

text: at

text: most

text: unit-area

text: pq

text: triangles.

text: It

text: therefore

text: remains

text: to

text: bound

text: the

text: second

text: sum,

text: over

text: L+.

text: Applying

text: the

text: Cauchy-Schwarz

text: to

text: the

text: sum,

text: it

text: follows

text: that

text: |U|

text: |(S

text: S)

text: L+

text: L+


text: 2(x − a) z = + c, (3) (b − d)(x − a) + (c − a)(y − b) + 2 2(y − b) w = + d. (b − d)(x − a) + (c − a)(y − b) + 2 R R This expresses σ as the graph of a linear rational function from 2 to 2 (which is pq undeﬁned on the line at which the denominator vanishes). Passing to homogeneous coordinates, replacing (x, y) by (x , x , x ) and (z, w) by (z , z , z ), we can re-interpret σ as the graph of   0 1 2 0 1 2  pq  PR PR a projective transformation T : 2 → 2, given by pq       z ad − bc + 2 b − d c − a x 0 0 z = c(ad − bc) + 2(c − a) c(b − d) + 2 c(c − a) x . 1 1 z d(ad − bc) + 2(d − b) d(b − d) d(c − a) + 2 x 2 2 The representation (3) implies that every (x, y) deﬁnes at most one pair (z, w) such that (x, y, z, w) ∈ σ . By the symmetry of the deﬁnition of σ , every pair (z, w) also determines pq pq R at most one pair (x, y) such that (x, y, z, w) ∈ σ . This shows that, for any p (cid:54)= q ∈ 2, the pq surface σ is slanted, which proves Proposition 7(a). pq For Proposition 7(b), it is equivalent, by the symmetry of the setup, to prove the following dual statement: For any p (cid:54)= q , p (cid:54)= q ∈ S, such that (p , q ) (cid:54)= (p , q ), we have |σ ∩ 1 1 2 2 1 1 2 2 p1q1 σ ∩ I| ≤ 3. p2q2 Let p , q , p , q ∈ S be as above, and assume that |σ ∩ σ ∩ I| ≥ 4. Note that this 1 1 2 2 p1q1 p2q2 means that the two projective transformations T , T agree in at least four distinct points p1q1 p2q2 of the projective plane. We claim that in this case σ and σ , regarded as graphs of p1q1 p2q2 functions on the aﬃne xy-plane, must coincide on some line in that plane. This is certainly the case if σ and σ coincide. (As mentioned earlier, this situation p1q1 p2q2 cannot arise, but we include it since we did not provide a proof of its impossibility.) We may thus assume that these surfaces are distinct, which implies that T and T are distinct p1q1 p2q2 projective transformations. As is well known, two distinct projective transformations of the plane cannot agree at four distinct points so that no three of them are collinear. Hence, out of the four points at which T and T agree, three must be collinear. Denote this triple of points (in the p1q1 p2q2 projective xy-plane) as u , u , u , and their respective images (in the projective zw-plane) as 1 2 3 v = T (u ) = T (u ), for i = 1, 2, 3. Then the line λ that contains u , u , u is mapped i p1q1 i p2q2 i ∗ 1 2 3 by both T and T to a line λ , and both transformations coincide on λ (since they both p1q1 p2q2 map the three distinct points u , u , u to the same three respective points v , v , v ). 1 2 3 1 2 3 ∗ Passing back to the aﬃne setting, let then λ, λ be a pair of lines in the xy-plane and the zw-plane, respectively, such that, for every (x, y) ∈ λ (other than the point at which the ∗ denominator in (3) vanishes) there exists (z, w) ∈ λ , satisfying (x, y, z, w) ∈ σ ∩ σ . We p1q1 p2q2 show that in this case p , q , p , q are all collinear and |p p | = |q q |. 1 1 2 2 1 2 1 2 We ﬁrst observe that (cid:96) (cid:107) (cid:96) . Indeed, if each of λ ∩ (cid:96) and λ ∩ (cid:96) is either p1p2 q1q2 p1p2 q1q2 empty or inﬁnite, then we must have (cid:96) (cid:107) (cid:96) (since both are parallel to λ). Otherwise, p1p2 q1q2 assume without loss of generality that |(cid:96) ∩ λ| = 1, and let ξ denote the unique point in p1p2 7 ##LTLine## ##LTLine##

label: equation

text: a)

text: z

text: c,

text: (b

text: d)(x

text: a)

text: (c

text: a)(y

text: b)

text: b)

text: w

text: d.

text: (b

text: d)(x

text: a)

text: (c

text: a)(y

text: b)

text: R

text: R

text: This

text: expresses

text: σ

text: as

text: the

text: graph

text: of

text: a

text: linear

text: rational

text: function

text: from

text: to

text: (which

text: is

text: pq

text: undeﬁned

text: on

text: the

text: line

text: at

text: which

text: the

text: denominator

text: vanishes).

text: Passing

text: to

text: homogeneous

text: coordinates,

text: replacing

text: (x,

text: y)

text: by

text: (x

text: x

text: x

text: and

text: (z,

text: w)

text: by

text: (z

text: z

text: z

text: we

text: can

text: re-interpret

text: σ

text: as

text: the

text: graph

text: of

text: 0

text: pq

text: PR

text: PR

text: a

text: projective

text: transformation

text: T

text: given

text: by

text: pq

text: z

text: ad

text: bc

text: b

text: d

text: c

text: a

text: x

text: z

text: c(ad

text: bc)

text: a)

text: c(b

text: d)

text: c(c

text: a)

text: x

text: z

text: d(ad

text: bc)

text: b)

text: d(b

text: d)

text: d(c

text: a)

text: x

text: The

text: representation

text: implies

text: that

text: every

text: (x,

text: y)

text: deﬁnes

text: at

text: most

text: one

text: pair

text: (z,

text: w)

text: such

text: that

text: (x,

text: y,

text: z,

text: w)

text: σ

text: By

text: the

text: symmetry

text: of

text: the

text: deﬁnition

text: of

text: σ

text: every

text: pair

text: (z,

text: w)

text: also

text: determines

text: pq

text: pq

text: R

text: at

text: most

text: one

text: pair

text: (x,

text: y)

text: such

text: that

text: (x,

text: y,

text: z,

text: w)

text: σ

text: This

text: shows

text: that,

text: for

text: any

text: p

text: q

text: the

text: pq

text: surface

text: σ

text: is

text: slanted,

text: which

text: proves

text: Proposition

text: pq

text: For

text: Proposition

text: it

text: is

text: equivalent,

text: by

text: the

text: symmetry

text: of

text: the

text: setup,

text: to

text: prove

text: the

text: following

text: dual

text: statement:

text: For

text: any

text: p

text: q

text: p

text: q

text: S,

text: such

text: that

text: (p

text: q

text: (p

text: q

text: we

text: have

text: |σ

text: σ

text: I|

text: Let

text: p

text: q

text: p

text: q

text: S

text: be

text: as

text: above,

text: and

text: assume

text: that

text: |σ

text: σ

text: I|

text: Note

text: that

text: this

text: means

text: that

text: the

text: two

text: projective

text: transformations

text: T

text: T

text: agree

text: in

text: at

text: least

text: four

text: distinct

text: points

text: of

text: the

text: projective

text: plane.

text: We

text: claim

text: that

text: in

text: this

text: case

text: σ

text: and

text: σ

text: regarded

text: as

text: graphs

text: of

text: functions

text: on

text: the

text: aﬃne

text: xy-plane,

text: must

text: coincide

text: on

text: some

text: line

text: in

text: that

text: plane.

text: This

text: is

text: certainly

text: the

text: case

text: if

text: σ

text: and

text: σ

text: coincide.

text: (As

text: mentioned

text: earlier,

text: this

text: situation

text: cannot

text: arise,

text: but

text: we

text: include

text: it

text: since

text: we

text: did

text: not

text: provide

text: a

text: proof

text: of

text: its

text: impossibility.)

text: We

text: may

text: thus

text: assume

text: that

text: these

text: surfaces

text: are

text: distinct,

text: which

text: implies

text: that

text: T

text: and

text: T

text: are

text: distinct

text: projective

text: transformations.

text: As

text: is

text: well

text: known,

text: two

text: distinct

text: projective

text: transformations

text: of

text: the

text: plane

text: cannot

text: agree

text: at

text: four

text: distinct

text: points

text: so

text: that

text: no

text: three

text: of

text: them

text: are

text: collinear.

text: Hence,

text: out

text: of

text: the

text: four

text: points

text: at

text: which

text: T

text: and

text: T

text: agree,

text: three

text: must

text: be

text: collinear.

text: Denote

text: this

text: triple

text: of

text: points

text: (in

text: the

text: projective

text: xy-plane)

text: as

text: u

text: u

text: u

text: and

text: their

text: respective

text: images

text: (in

text: the

text: projective

text: zw-plane)

text: as

text: v

text: T

text: (u

text: T

text: (u

text: for

text: i

text: Then

text: the

text: line

text: λ

text: that

text: contains

text: u

text: u

text: u

text: is

text: mapped

text: i

text: i

text: i

text: by

text: both

text: T

text: and

text: T

text: to

text: a

text: line

text: λ

text: and

text: both

text: transformations

text: coincide

text: on

text: λ

text: (since

text: they

text: both

text: map

text: the

text: three

text: distinct

text: points

text: u

text: u

text: u

text: to

text: the

text: same

text: three

text: respective

text: points

text: v

text: v

text: v

text: Passing

text: back

text: to

text: the

text: aﬃne

text: setting,

text: let

text: then

text: λ,

text: λ

text: be

text: a

text: pair

text: of

text: lines

text: in

text: the

text: xy-plane

text: and

text: the

text: zw-plane,

text: respectively,

text: such

text: that,

text: for

text: every

text: (x,

text: y)

text: λ

text: (other

text: than

text: the

text: point

text: at

text: which

text: the

text: denominator

text: in

text: vanishes)

text: there

text: exists

text: (z,

text: w)

text: λ

text: satisfying

text: (x,

text: y,

text: z,

text: w)

text: σ

text: σ

text: We

text: show

text: that

text: in

text: this

text: case

text: p

text: q

text: p

text: q

text: are

text: all

text: collinear

text: and

text: |p

text: p

text: |q

text: q

text: We

text: ﬁrst

text: observe

text: that

text: Indeed,

text: if

text: each

text: of

text: λ

text: and

text: λ

text: is

text: either

text: empty

text: or

text: inﬁnite,

text: then

text: we

text: must

text: have

text: (since

text: both

text: are

text: parallel

text: to

text: λ).

text: Otherwise,

text: assume

text: without

text: loss

text: of

text: generality

text: that

text: λ|

text: and

text: let

text: ξ

text: denote

text: the

text: unique

text: point

text: in

text: ##LTLine##

text: ##LTLine##


text: On the solvability of relaxed one-sided Lipschitz inclusions in Hilbert spaces Janosch Rieger and Tobias Weth May 27, 2020 Abstract We prove solvability theorems for relaxed one-sided Lipschitz mul- tivalued mappings in Hilbert spaces and for composed mappings in the Gelfand triple setting. From these theorems, we deduce proper- ties of the inverses of such mappings and convergence properties of a numerical scheme for the solution of algebraic inclusions. Key words: relaxed one-sided Lipschitz property, algebraic inclusion, root-ﬁnding method, set-valued analysis. AMS(MOS) subject classiﬁcations: 47H04, 65K10, 49J53. 1 Introduction The relaxed one-sided Lipschitz property (see Deﬁnition ?? below) was ﬁrst considered in [?], where it was identiﬁed as an important stability cri- terion for time-dependent diﬀerential inclusions. The behavior of general multivalued mappings with negative relaxed one-sided Lipschitz constants was later studied in [?, ?]. In particular, surjectivity of the mappings and therefore solvability of the corresponding algebraic inclusions was shown by considering the ﬂow of the diﬀerential inclusions from [?]. However, no in- formation on the localization of the solutions was given in these papers. For relaxed one-sided Lipschitz mappings in ﬁnite-dimensional spaces, the solvability theorem given in [?] speciﬁes a ball in which a solution of the inclusion is contained. The radius of this ball depends on the norm of 1

text: On

text: the

text: solvability

text: of

text: relaxed

text: one-sided

text: Lipschitz

text: inclusions

text: in

text: Hilbert

text: spaces

text: Janosch

text: Rieger

text: and

text: Tobias

text: Weth

text: May

label: date

text: Abstract

text: We

text: prove

text: solvability

text: theorems

text: for

text: relaxed

text: one-sided

text: Lipschitz

text: mul-

text: tivalued

text: mappings

text: in

text: Hilbert

text: spaces

text: and

text: for

text: composed

text: mappings

text: in

text: the

text: Gelfand

text: triple

text: setting.

text: From

text: these

text: theorems,

text: we

text: deduce

text: proper-

text: ties

text: of

text: the

text: inverses

text: of

text: such

text: mappings

text: and

text: convergence

text: properties

text: of

text: a

text: numerical

text: scheme

text: for

text: the

text: solution

text: of

text: algebraic

text: inclusions.

text: Key

text: words:

text: relaxed

text: one-sided

text: Lipschitz

text: property,

text: algebraic

text: inclusion,

text: root-ﬁnding

text: method,

text: set-valued

text: analysis.

text: AMS(MOS)

text: subject

text: classiﬁcations:

label: section

text: Introduction

text: The

text: relaxed

text: one-sided

text: Lipschitz

text: property

text: (see

text: Deﬁnition

text: below)

text: was

text: ﬁrst

text: considered

text: in

text: where

text: it

text: was

text: identiﬁed

text: as

text: an

text: important

text: stability

text: cri-

text: terion

text: for

text: time-dependent

text: diﬀerential

text: inclusions.

text: The

text: behavior

text: of

text: general

text: multivalued

text: mappings

text: with

text: negative

text: relaxed

text: one-sided

text: Lipschitz

text: constants

text: was

text: later

text: studied

text: in

text: In

text: particular,

text: surjectivity

text: of

text: the

text: mappings

text: and

text: therefore

text: solvability

text: of

text: the

text: corresponding

text: algebraic

text: inclusions

text: was

text: shown

text: by

text: considering

text: the

text: ﬂow

text: of

text: the

text: diﬀerential

text: inclusions

text: from

text: However,

text: no

text: in-

text: formation

text: on

text: the

text: localization

text: of

text: the

text: solutions

text: was

text: given

text: in

text: these

text: papers.

text: For

text: relaxed

text: one-sided

text: Lipschitz

text: mappings

text: in

text: ﬁnite-dimensional

text: spaces,

text: the

text: solvability

text: theorem

text: given

text: in

text: speciﬁes

text: a

text: ball

text: in

text: which

text: a

text: solution

text: of

text: the

text: inclusion

text: is

text: contained.

text: The

text: radius

text: of

text: this

text: ball

text: depends

text: on

text: the

text: norm

text: of


text: Without additional structure, it seems diﬃcult to say more about the properties of the inverse. Some multivalued mappings arising in control theory or from uncertainties are explicitly given in parameterized form and allow a more detailed analysis. The existence of such a parametrization implies weak-strong continuity of the multifunction and hence is a substan- tially stronger assumption than the compact upper hemicontinuity required in Theorem ??. → CBC Proposition 15. Let (U, d ) be a metric space, and let F : V (V ) be U × → parameterized by a function f : V U V satisfying ∪ ∈ a) F (x) = ∈ f(x, u) for all x V , u U (cid:55)→ ∈ b) u f(x, u) is continuous for all x V , and (cid:55)→ c) x f(x, u) is continuous from V endowed with the weak topology to V endowed with the norm topology, bounded on bounded sets, and l-one- ∈ sided Lipschitz for all u U in the sense that − (cid:48) − (cid:48) ≤ (cid:107) − (cid:48)(cid:107) ∈ (f(x, u) f(x , u), x x ) l x x 2 for all u U V V with a constant l < 0 that is independent of u. − ⇒ × → Then F 1 : V V is parameterized by a function g : V U V satisfying − ∪ ∈ d) F 1(y) = ∈ g(y, u) for all y V , u U (cid:55)→ ∈ e) u g(y, u) is continuous for all y V , and (cid:55)→ − ∈ f) y g(y, u) is 1-Lipschitz and 0-one-sided Lipschitz for all u U. l − In particular, if U is connected or path connected, the images of F and F 1 inherit these properties. (cid:55)→ ∈ Proof. Applying Theorem ?? to the functions x f(x, u), u U, yields the · ⇒ ∈ existence of inverses g( , u) : V V , u U, given by { ∈ } g(y, u) := x V : f(x, u) = y , − ∈ that are well-deﬁned, 1-Lipschitz and 0-ROSL, so that f) holds. If y V , ∈ (cid:48) ∈ l u U and x, x g(y, u), then − (cid:48) (cid:48) − ≤ (cid:107) − (cid:48)(cid:107) 0 = (f(x, u) f(x , u), x x) l x x 2 , V V 16 ##LTLine## ##LTLine##

text: Without

text: additional

text: structure,

text: it

text: seems

text: diﬃcult

text: to

text: say

text: more

text: about

text: the

text: properties

text: of

text: the

text: inverse.

text: Some

text: multivalued

text: mappings

text: arising

text: in

text: control

text: theory

text: or

text: from

text: uncertainties

text: are

text: explicitly

text: given

text: in

text: parameterized

text: form

text: and

text: allow

text: a

text: more

text: detailed

text: analysis.

text: The

text: existence

text: of

text: such

text: a

text: parametrization

text: implies

text: weak-strong

text: continuity

text: of

text: the

text: multifunction

text: and

text: hence

text: is

text: a

text: substan-

text: tially

text: stronger

text: assumption

text: than

text: the

text: compact

text: upper

text: hemicontinuity

text: required

text: in

text: Theorem

text: CBC

text: Proposition

text: Let

text: (U,

text: d

text: be

text: a

text: metric

text: space,

text: and

text: let

text: F

text: V

text: (V

text: be

text: U

text: parameterized

text: by

text: a

text: function

text: f

text: V

text: U

text: V

text: satisfying

label: list

text: a)

text: F

text: (x)

text: f(x,

text: u)

text: for

text: all

text: x

text: V

text: u

text: U

text: b)

text: u

text: f(x,

text: u)

text: is

text: continuous

text: for

text: all

text: x

text: V

text: and

text: c)

text: x

text: f(x,

text: u)

text: is

text: continuous

text: from

text: V

text: endowed

text: with

text: the

text: weak

text: topology

text: to

text: V

text: endowed

text: with

text: the

text: norm

text: topology,

text: bounded

text: on

text: bounded

text: sets,

text: and

text: l-one-

text: sided

text: Lipschitz

text: for

text: all

text: u

text: U

text: in

text: the

text: sense

text: that

text: (f(x,

text: u)

text: f(x

text: u),

text: x

text: x

text: l

text: x

text: x

text: for

text: all

text: u

text: U

text: V

text: V

text: with

text: a

text: constant

text: l

text: that

text: is

text: independent

text: of

text: u.

text: Then

text: F

text: V

text: V

text: is

text: parameterized

text: by

text: a

text: function

text: g

text: V

text: U

text: V

text: satisfying

text: d)

text: F

text: g(y,

text: u)

text: for

text: all

text: y

text: V

text: u

text: U

text: e)

text: u

text: g(y,

text: u)

text: is

text: continuous

text: for

text: all

text: y

text: V

text: and

text: f)

text: y

text: g(y,

text: u)

text: is

text: and

text: Lipschitz

text: for

text: all

text: u

text: U.

text: l

text: In

text: particular,

text: if

text: U

text: is

text: connected

text: or

text: path

text: connected,

text: the

text: images

text: of

text: F

text: and

text: F

text: inherit

text: these

text: properties.

text: Proof.

text: Applying

text: Theorem

text: to

text: the

text: functions

text: x

text: f(x,

text: u),

text: u

text: U,

text: yields

text: the

text: existence

text: of

text: inverses

text: g(

text: u)

text: V

text: V

text: u

text: U,

text: given

text: by

text: g(y,

text: u)

text: x

text: V

text: f(x,

text: u)

text: y

text: that

text: are

text: well-deﬁned,

text: and

text: so

text: that

text: f)

text: holds.

text: If

text: y

text: V

text: l

text: u

text: U

text: and

text: x,

text: x

text: g(y,

text: u),

text: then

text: (f(x,

text: u)

text: f(x

text: u),

text: x

text: x)

text: l

text: x

text: x

text: V

text: V

text: ##LTLine##

text: ##LTLine##


text: 2 Preliminaries In this section, we collect the necessary deﬁnitions and some elementary (cid:107)·(cid:107) (cid:104)· ·(cid:105) ∗× → facts. Let (X, ) be any real normed vector space, and let , : X X X R denote the dual pairing. ∈ (cid:48) ⊂ Deﬁnition 1. For x X and nonempty subsets M, M X, we set (cid:48) (cid:107) − (cid:48)(cid:107) dist (x, M ) := inf x x , X (cid:48)∈ (cid:48) X x M (cid:48) (cid:48) e (M, M ) := sup dist (x, M ), X ∈ X x M (cid:107) (cid:107) { } M := e (M, 0 ), X X { (cid:48) ∈ (cid:107) − (cid:48)(cid:107) } Proj (x, M) := x M : x x = dist (x, M) , X { ∈ X ≤ }X B (M, R) := y X : dist (y, M) R , X X { ∈ (cid:107) − (cid:107) ≤ } B (x, R) := y V : y x R . X X CBC The nonempty closed, bounded and convex subsets of X are denoted (X), CC and the nonempty convex and compact subsets of X are denoted (X). ∗ ×CBC ∗ → Deﬁnition 2. a) The support function σ : X (X ) R is deﬁned X by ∗ (cid:104) (cid:105) ∀ ∈ ⊂ ∗ σ (x, A) := sup ϕ, x x X, A X . X ∈ ϕ A · · b) If X is a real Hilbert space with scalar product ( , ) , then we deﬁne × CBC → X σ : X (X) R by X ∀ ∈ ⊂ σ (x, A) := sup(y, x) x X, A X. X ∈ y A Deﬁnition 3. Let (M, d) be a metric space and Y a further normed vector space. → CBC ∗ a) A set-valued mapping F : M (Y ) is called upper hemicontinu- ∈ ⊂ → ous (uhc) at x M if for any sequence (x ) ∈ M with x x we k k N k have ∗ ≤ ∗ ∈ lim sup σ (v, F (x )) σ (v, F (x)) for all v Y . (1) →∞ Y k Y k 3

text: Preliminaries

text: In

text: this

text: section,

text: we

text: collect

text: the

text: necessary

text: deﬁnitions

text: and

text: some

text: elementary

text: facts.

text: Let

text: (X,

text: be

text: any

text: real

text: normed

text: vector

text: space,

text: and

text: let

text: X

text: X

text: X

text: R

font: unknown

text: denote

text: the

text: dual

text: pairing.

text: Deﬁnition

text: For

text: x

text: X

text: and

text: nonempty

text: subsets

text: M,

text: M

text: X,

text: we

text: set

text: dist

text: (x,

text: M

text: inf

text: x

text: x

text: X

text: X

text: x

text: M

text: e

text: (M,

text: M

text: sup

text: dist

text: (x,

text: M

text: X

text: X

text: x

text: M

text: M

text: e

text: (M,

text: X

text: X

text: Proj

text: (x,

text: M)

text: x

text: M

text: x

text: x

text: dist

text: (x,

text: M)

text: X

text: X

text: }X

text: B

text: (M,

text: R)

text: y

text: X

text: dist

text: (y,

text: M)

text: R

text: X

text: X

text: B

text: (x,

text: R)

text: y

text: V

text: y

text: x

text: R

text: X

text: X

text: CBC

text: The

text: nonempty

text: closed,

text: bounded

text: and

text: convex

text: subsets

text: of

text: X

text: are

text: denoted

text: (X),

text: CC

text: and

text: the

text: nonempty

text: convex

text: and

text: compact

text: subsets

text: of

text: X

text: are

text: denoted

text: (X).

text: ×CBC

text: Deﬁnition

text: a)

text: The

text: support

text: function

text: σ

text: X

text: (X

text: R

text: is

text: deﬁned

text: X

text: by

text: σ

text: (x,

text: A)

text: sup

text: ϕ,

text: x

text: x

text: X,

text: A

text: X

text: X

text: ϕ

text: A

text: b)

text: If

text: X

text: is

text: a

text: real

text: Hilbert

text: space

text: with

text: scalar

text: product

text: then

text: we

text: deﬁne

text: CBC

text: X

text: σ

text: X

text: (X)

text: R

text: by

text: X

text: σ

text: (x,

text: A)

text: sup(y,

text: x)

text: x

text: X,

text: A

text: X.

text: X

text: y

text: A

text: Deﬁnition

text: Let

text: (M,

text: d)

text: be

text: a

text: metric

text: space

text: and

text: Y

text: a

text: further

text: normed

text: vector

text: space.

text: CBC

text: a)

text: A

text: set-valued

text: mapping

text: F

text: M

text: (Y

text: is

text: called

text: upper

text: hemicontinu-

text: ous

text: (uhc)

text: at

text: x

text: M

text: if

text: for

text: any

text: sequence

text: (x

text: M

text: with

text: x

text: x

text: we

text: k

text: k

text: N

text: k

text: have

text: lim

text: sup

text: σ

text: (v,

text: F

text: (x

text: σ

text: (v,

text: F

text: (x))

text: for

text: all

text: v

text: Y

text: Y

text: k

text: Y

text: k