View source for Dvoretzky problem

''for random covering''

Roughly speaking, random covering is the (attempt at) [[Covering|covering]] a given large body by means of smaller bodies that are randomly distributed.

There is a large amount of literature on random covering. See [[#References|[a1]]] for a general approach; [[#References|[a3]]] for the fractal aspect; [[#References|[a11]]] for the special case of small convex bodies of given shape and size.

The Dvoretzky problem is about the circle <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102501.png" /> of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102502.png" /> and random intervals on it whose lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102503.png" /> are given (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102504.png" />), and whose positions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102505.png" /> are randomly distributed in the usual way. A century ago, E. Borel already knew that when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102506.png" />, any given point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102507.png" /> is covered almost surely. In 1956, A. Dvoretzky observed that this does not imply that the whole circle is covered almost surely [[#References|[a5]]]. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102508.png" />, the uncovered set has [[Lebesgue measure|Lebesgue measure]] zero almost surely. Is it possible to be more precise? Is it possible to get good necessary and sufficient conditions for covering? Is it possible to do the same in several dimensions?

To apply the [[Zero-one law|zero-one law]] (i.e., the probability is either zero or one), it is slightly more convenient to consider infinite coverings, meaning that each point is covered by infinitely many intervals.

After Dvoretzky, the first important systematic study was made by P. Billard [[#References|[a4]]] (see [[Billard method|Billard method]]). Using Billard's method, J.-P. Kahane was able to compute the [[Hausdorff dimension|Hausdorff dimension]] of the uncovered set; for example, this dimension is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d1102509.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025010.png" /> [[#References|[a2]]]. More precise results, involving capacity with respect to a kernel constructed from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025011.png" />, have been obtained later, in [[#References|[a13]]].

A most spectacular result was obtained by L. Shepp in 1972 [[#References|[a15]]]: covering holds if and only if the series

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025012.png" /></td> </tr></table>

diverges; for example, covering holds when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025013.png" />.

The problem was subsequently extended in several ways.

B. Mandelbrot has considered a similar problem on the line, with random cutouts associated with a Poisson measure in a half-plane, and discovered the relation between the uncovered set and the range of the Lévy process [[#References|[a14]]]; this programme was completed by P. Fitzsimmons, B. Fristedt and Shepp in 1985 (see [[Fitzsimmons–Fristedt–Shepp theorem|Fitzsimmons–Fristedt–Shepp theorem]], [[#References|[a9]]]). In this context, the covering condition was established already by Shepp in 1972 [[#References|[a16]]].

M. Wschebor considered coverings or cutouts by random sets, not necessarily intervals. His result: When the measures are given, the best covering is realized by intervals [[#References|[a17]]], [[#References|[a18]]].

J. Hoffmann-Jørgensen has put forth a general framework: random balls in a metric space [[#References|[a10]]]. Y. El Hélou was able to compute the Hausdorff dimension of the uncovered set when random balls of given volumes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025014.png" /> are placed on a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025015.png" />-dimensional torus [[#References|[a2]]]. Fan Ai-hua has given a necessary and sufficient condition for the covering of a given subset of an ultrametric space, a natural question in percolation on trees [[#References|[a7]]].

The Dvoretzky problem for random balls of given volumes on the torus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025016.png" /> is still unsolved. However, there is a natural guess for the necessary and sufficient condition, and the problem for homothetic simplices has been completely solved by Kahane [[#References|[a13]]] (see [[Billard method|Billard method]]).

Another generalization of the Dvoretzky problem: instead of the lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025017.png" />, suppose one is given positive functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025018.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025019.png" />. Consider the series of random translates

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025020.png" /></td> </tr></table>

(with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025021.png" /> independent and Lebesgue distributed). One now asks for the probability that it diverges everywhere. The Dvoretzky problem corresponds to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025022.png" />. The case with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025023.png" /> is investigated in [[#References|[a8]]]; the general case needs new ideas.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Hall,   "Introduction to the theory of coverage processes" , Wiley  (1988)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.-P. Kahane,   "Some random series of functions" , Cambridge Univ. Press  (1985)  (Edition: Second)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  B.B. Mandelbrot,   "The fractal geometry of nature" , Freeman  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P. Billard,   "Séries de Fourier aléatoirement bornées, continues, uniformement convergentes"  ''Ann. Sci. Ecole Norm. Sup.'' , '''82'''  (1965)  pp. 131–179</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Dvoretzky,   "On covering a circle by randomply placed arcs"  ''Proc. Nat. Acad. Sci. USA'' , '''42'''  (1956)  pp. 199–203</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  Y. El Hélou,   "Recouvrement du tore <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110250/d11025024.png" /> par des ouverts aléatoires er dimension de Hausdorff de l'ensemble non recouvert"  ''C.R. Acad. Sci. Paris'' , '''287A'''  (1978)  pp. 815–818</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A.-h. Fan,   "Sur quelques processus de naissance et de mort"  ''C.R. Acad. Sci. Paris'' , '''310'''  (1990)  pp. 441–444</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  A.-h. Fan,   J.-P. Kahane,   "Rareté des intervalles recouvrant un point dans un recouvrement aléatoire"  ''Ann. Inst. H. Poincaré'' , '''20''' :  3  (1993)  pp. 453–466</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  P.J. Fitzsimons,   B. Fristedt,   L.R. Shepp,   "The set of real numbers left uncovered by random covering intervals"  ''Z. Wahrscheinlichkeitsth. verw. Gebiete'' , '''70'''  (1985)  pp. 175–189</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  J. Hoffmann-Jørgensen,   "Coverings of metric spaces with randomly placed balls"  ''Math. Scand.'' , '''32'''  (1973)  pp. 179–186</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  S. Janson,   "Random covering in several dimensions"  ''Acta Math.'' , '''156'''  (1986)  pp. 83–118</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  J.-P. Kahane,   "Sur le recouvrement d'un cercle par des arcs disposés au hasard"  ''C.R. Acad. Sci. Paris'' , '''248'''  (1959)  pp. 184–186</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  J.-P. Kahane,   "Recouvrements aléatoires et théorie du potentiel"  ''Coll. Math.'' , '''60/1'''  (1990)  pp. 387–411</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  B.B. Mandelbrot,   "Renewal sets and random cutouts"  ''Z. Wahrscheinlichkeitsth. verw. Gebiete'' , '''22'''  (1972)  pp. 145–157</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  L.A. Shepp,   "Covering the circle with random arcs"  ''Israel J. Math.'' , '''11'''  (1972)  pp. 328–345</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  L.A. Shepp,   "Covering the line by random intervals"  ''Z. Wahrscheinlichkeitsth. verw. Gebiete'' , '''23'''  (1972)  pp. 163–170</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  M. Wschebor,   "Sur le recouvrement du cercle par des ensembles placés au hasard"  ''Israel J. Math.'' , '''15'''  (1973)  pp. 1–11</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  M. Wschebor,   "Sur un théorème de L. Shepp"  ''Z. Wahrscheinlichkeitsth. verw. Gebiete'' , '''27'''  (1973)  pp. 179–184</TD></TR></table>