Hunter, Cauchy rabbit, and optimal Kakeya sets

Medientyp: E-Artikel

Titel: Hunter, Cauchy rabbit, and optimal Kakeya sets

Beteiligte: Babichenko, Yakov; Peres, Yuval; Peretz, Ron; Sousi, Perla; Winkler, Peter

Erschienen: American Mathematical Society (AMS), 2014

Sprache: Englisch

DOI: 10.1090/s0002-9947-2014-06226-0

ISSN: 0002-9947; 1088-6850

Schlagwörter: Applied Mathematics ; General Mathematics

Entstehung:

Anmerkungen:

Beschreibung: <p>A planar set that contains a unit segment in every direction is called a Kakeya set. We relate these sets to a game of pursuit on a cycle <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z Subscript n"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\mathbb {Z}_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. A hunter and a rabbit move on the nodes of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z Subscript n"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\mathbb {Z}_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> without seeing each other. At each step, the hunter moves to a neighbouring vertex or stays in place, while the rabbit is free to jump to any node. Adler et al. (2003) provide strategies for hunter and rabbit that are optimal up to constant factors and achieve probability of capture in the first <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> steps of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 slash log n"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">1/\log n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We show these strategies yield a Kakeya set consisting of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="4 n"> <mml:semantics> <mml:mrow> <mml:mn>4</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">4n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> triangles with minimal area (up to constant), namely <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Theta left-parenthesis 1 slash log n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">Θ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\Theta (1/\log n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. As far as we know, this is the first non-iterative construction of a boundary-optimal Kakeya set. Considering the continuum analog of the game yields a construction of a random Kakeya set from two independent standard Brownian motions <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet upper B left-parenthesis s right-parenthesis colon s greater-than-or-equal-to 0 EndSet"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mi>B</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>s</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>:</mml:mo> <mml:mi>s</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\{B(s): s \ge 0\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet upper W left-parenthesis s right-parenthesis colon s greater-than-or-equal-to 0 EndSet"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mi>W</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>s</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>:</mml:mo> <mml:mi>s</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\{W(s): s \ge 0\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="tau Subscript t Baseline colon equals min left-brace right-brace colon greater-than-or-equal-to greater-than-or-equal-to s 0 colon equals equals of BB left-parenthesis right-parenthesis st"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>τ</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo>:=</mml:mo> <mml:mo movablelimits="true" form="prefix">min</mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mi>s</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> <mml:mo>:</mml:mo> <mml:mi>B</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>s</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>t</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\tau _t:=\min \{s \ge 0: B(s)=t\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X Subscript t Baseline equals upper W left-parenthesis tau Subscript t Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>W</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>τ</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">X_t=W(\tau _t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a Cauchy process and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K colon equals left-brace left-parenthesis a comma upper X Subscript t Baseline plus a t right-parenthesis colon a comma t element-of left-bracket 0 comma 1 right-bracket right-brace"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>:=</mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>a</mml:mi> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:mi>a</mml:mi> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>:</mml:mo> <mml:mi>a</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> <mml:mo>∈</mml:mo> <mml:mo stretchy="false">[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">]</mml:mo> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">K:=\{(a,X_t+at) : a,t \in [0,1]\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a Kakeya set of zero area. The area of the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon"> <mml:semantics> <mml:mi>ε</mml:mi> <mml:annotation encoding="application/x-tex">\varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-neighbourhood of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is as small as possible, i.e., almost surely of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Theta left-parenthesis 1 slash StartAbsoluteValue log epsilon EndAbsoluteValue right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">Θ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>ε</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\Theta (1/|\log \varepsilon |)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.</p>

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: