Skip to main content
5 of 5
edited body
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

I'm going to show that, for any $x>2^{-d}$, this is $O(x^{n})$. By Ricardo's lower bound, this is tight.

Given a set of $n$ points of diameter at most $1$, take all the points you get from those points by rounding the coordinates up or down to multiples of $\epsilon$. This new set of points will contain the old set of points in its convex hull, and since the new set of points will be of a distance no more than $\sqrt{d}\epsilon$ from the old set of points, will have a diameter at most $1+2\sqrt{d}\epsilon$. Thus each configuration of points of diameter at most $1$ in a sphere of radius $1$ is contained in the convex hull of some configuration of $\epsilon$-lattice points of diameter at most $1+2\sqrt{d}\epsilon$ in a sphere of radius $1+\sqrt{d}\epsilon$. Let $N$ be the (finite) number of such configurations of lattice points. Then since the sphere has the greatest volume of any convex body with a given diameter, the convex hulls each take up at most $(1+2\sqrt{d} \epsilon)^d/2^d$ of the volume of the sphere, so landing in any hull has probability

\[ N \left(\frac{ 1 + 2 \sqrt{d} \epsilon}{2}\right)^{dn} \]

If we let $\epsilon$ go to $0$ we have the desired result.

To be more specific, we can set $\epsilon = n^{-1/(d+1)}$, and get the upper bound

\[\ln \left(2^{nd} \chi(n)\right) = O\left( n^{d/(d+1)} \right) \]

using the trivial upper bound $N < 2^{O(\epsilon^{-d} )}$

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563