# Throwing darts at a barn and putting a bullseye around them in higher dimensions

Let $X \in \mathbb R^d$ be a large domain (a ball of radius $r$ for $r$ large should suffice)

Let $B$ be a ball of radius $1$.

Consider the ratio

$$\frac{ \left| \left\{ x_1,\dots,x_n \in X \mid x_1,\dots,x_n \textrm{ lie in some translate of } B \right\} \right| }{|X| |B|^{n-1} n^d}$$

I can show this ratio is bounded above and below by a constant depending on $d$. Presumably, it converges to some limit as $n$ goes to $\infty$ (we can send $r$ to $\infty$ too). But how does this limit depend on $d$? Does it grow, shrink, or remain constant?

My upper bound is exponential growth and my lower bound is superexponential decline. So there is quite a lot of give between these two.

I also know that if we replace $B$ with a cube, the limit is $1$, as we may separate the different coordinates and thus reduce to the case $d=1$, and then it's very easy to check that the answer is $1$.

This question came up when I was working on lower bounds for my previous question

Upper bound proof:

If $x_1,\dots,x_n$ lie in a translate $y+B$ of $B$, then they lie in $y'+(1+\epsilon)B$ for all $y$ in a ball of radius $\epsilon$.

Hence:

$$\left| \left\{ x_1,\dots,x_n \in X \mid x_1,\dots,x_n \textrm{ lie in some translate of } B \right\} \right| \leq \frac{\int_{y \in X}\left| \left\{ x_1,\dots,x_n \in X \mid x_1,\dots,x_n \textrm{ lie in } y+ (1+\epsilon)B \right\} \right|}{ \epsilon^d |B|} \leq \frac{ \int_{y \in X} (1+\epsilon)^{nd} |B|^n } { \epsilon^d |B|} = \frac{(1 + \epsilon)^{nd}}{\epsilon^d} |X| |B|^{n-1} \leq e^d n^d |X| |B|^{n-1}$$

if $\epsilon =1/n$.

Lower bound proof

By Cauchy-Schwartz

$$\left| \left\{ x_1,\dots,x_n \in X \mid x_1,\dots,x_n \textrm{ lie in some translate of } B \right\} \right| \leq \frac{ \left(\int_{x_1,\dots,x_n \in X} \left| \left\{ y \mid x_1, \dots, x_n \textrm{ lie in } y +B\right\}\right|\right)^2 }{ \int_{x_1,\dots,x_n \in X} \left| \left\{ y \mid x_1, \dots, x_n \textrm{ lie in } y +B\right\}\right|^2}$$

The numerator is the square of

$$\int_{y \in X} \left| \left\{ x_1,\dots,x_n \mid x_1, \dots, x_n \textrm{ lie in } y +B\right\}\right|= |X| |B|^n$$

and the denominator is

$$\int_{y_1,y_2 \in X} \left| \left\{ x_1,\dots,x_n \mid x_1, \dots, x_n \textrm{ lie in } y_1 +B \cap y_2+B \right\}\right| = \int_{y_1,y_2 \in X} V(||y_1 -y_2||_2)^n$$ $$\approx \int_{y_1 \in X} \int_{z \in \mathbb R^d} V(||z||_2)^n = |X| \int_{z \in \mathbb R^d} V(||z||_2)^n$$

where $V(r)$ is the intersection of two copies of $B$ whose centers are a distance $r$ apart.

Now

$$\int_{z \in \mathbb R^d} V(||z||_2)^n = n^{-d} \int_{z \in \mathbb R^d} V(||z||_2/n)^n \approx n^{-d} \int_{z \in \mathbb R^d} |B|^n e^{- \operatorname{dlog} V (0) z } = n^{-d} |B|^{n+1} d! / (\operatorname{dlog} V(0))^d$$

for a lower bound of $|X| |B|^{n-1} n^d (\operatorname{dlog} V(0))^d / d!$. Now the derivative of $V$ at $0$ is just the volume of a $d-1$-dimensional ball of radius $1$ because moving the ball $\epsilon$ along one axis and intersecting removes a slice of thickness $\epsilon$ in that direction from the ball. So the logarithmic derivative is the ratio of the volumes of the $d-1$ and $d$-dimensional balls, hence of size around $\sqrt{d}$. So the lower bound is roguhly $d^{-d/2}$.

• For the sake of clarity bordering on tedium (as opposed to uncertainty bordering on madness) I ask that you indicate that $|-|$ (the absolute value sign) is being used as volume or Riemann or Lesbesgue measure of (presumably open) subsets of the reals to various powers, or something to that effect. That saves my brain (and perhaps others) the work of wondering whether vector norm or cardinality is meant. Gerhard "Abuse Notation But Not Communication" Paseman, 2016.04.04. – Gerhard Paseman Apr 4 '16 at 17:35
• Also, suppose B is the union of two cubes. Can you show a result in that case? Gerhard "Might Reduce To Measure Theory" Paseman, 2016.04.04. – Gerhard Paseman Apr 4 '16 at 17:40
• @GerhardPaseman It means Lebesgue measure except when applied to a single vector a couple times in the lower bound arguments. Let me clarify that with a slightly different notation. – Will Sawin Apr 4 '16 at 17:43
• @GerhardPaseman Where are the cubes in relation to each other? – Will Sawin Apr 4 '16 at 17:43
• I think you need to handle both disjoint and nondisjoint cases. Since you are still exploring, make it easy: start with them adjacent cubes in a hypercube grid, and for the next case "kick" the top one an epsilon amount in some direction. Gerhard "Make It A Gentle Kick" Paseman, 2016.04.04. – Gerhard Paseman Apr 4 '16 at 17:47