{"id":848,"date":"2014-02-05T14:14:05","date_gmt":"2014-02-05T19:14:05","guid":{"rendered":"http:\/\/www.curtisbright.com\/bln\/?p=848"},"modified":"2014-02-05T14:14:05","modified_gmt":"2014-02-05T19:14:05","slug":"blichfeldts-theorem","status":"publish","type":"post","link":"http:\/\/localhost\/blog\/index.php\/2014\/02\/05\/blichfeldts-theorem\/","title":{"rendered":"Blichfeldt’s Theorem"},"content":{"rendered":"

The following theorem was proven by Blichfeldt1<\/a><\/sup>\u00a0in 1914:<\/p>\n

Let $P$ be a set of points in $\\newcommand{\\R}{\\mathbb{R}}\\R^n$ which are invariant under translation by vectors in $\\newcommand{\\Z}{\\mathbb{Z}}\\Z^n$, and say that $[0,1)^n$ contains $N$ points of $P$. If $S$ is a set in $\\R^n$ with volume $V(S)$ then there is some translation $\\newcommand{\\x}{\\mathbf{x}}S+\\x$ which contains at least $N\\cdot V(S)$ points of $P$. Additionally, if $S$ is compact then there is some translation of $S$ which contains more than $N\\cdot V(S)$ points of $P$.<\/p>\n

To show this, let $\\newcommand{\\p}{\\mathbf{p}}\\newcommand{\\c}{{,}~}\\p_1\\c\\dotsc\\c\\p_N$ be the points of $P$ contained in $[0,1)^n$. Since $P$ is invariant under translation by $\\Z^n$, every $\\p\\in P$ is equivalent to some $\\p_i$ modulo $\\Z^n$. Let $\\nu_i(S)$ denote the number of points in $P\\cap S$ congruent to $\\p_i$, so<\/p>\n

\\[ \\newcommand{\\y}{\\mathbf{y}}\\nu_i(S) = \\sum_{\\y\\in\\Z^n}\\chi_S(\\p_i+\\y) \\]<\/p>\n

where $\\chi_S$ is the characteristic function<\/a> of $S$. Then<\/p>\n

\\begin{align*}\\newcommand{\\d}{\\,\\mathrm{d}}
\n\\int_{[0,1)^n}\\nu_i(S+\\x)\\d\\x &= \\int_{[0,1)^n}\\sum_{\\y\\in\\Z^n}\\chi_{S+\\x}(\\p_i+\\y)\\d\\x \\\\
\n&= \\int_{[0,1)^n}\\sum_{\\y\\in\\Z^n}\\chi_S(\\p_i+\\y-\\x)\\d\\x \\\\
\n&= \\int_{(-1,0]^n}\\sum_{\\y\\in\\Z^n}\\chi_S(\\p_i+\\y+\\x)\\d\\x \\\\
\n&= \\sum_{\\y\\in\\Z^n}\\int_{(-1,0]^n+\\p_i+\\y}\\chi_S(\\x)\\d\\x \\\\
\n&= \\int_{\\R^n}\\chi_S(\\x)\\d\\x \\\\
\n&= V(S)
\n\\end{align*}<\/p>\n

where the penultimate step follows since taking the set $(-1,0]^n+\\p_i+\\y$ for each $\\y\\in\\Z^n$ will produce a tiling of all of $\\R^n$ with no overlap.<\/p>\n

Letting $\\nu(S):=\\lvert P\\cap S\\rvert=\\sum_{i=1}^N\\nu_i(S)$ and summing the above over $1\\leq i\\leq N$, we find that<\/p>\n

\\[ \\int_{[0,1)^n}\\nu(S+\\x)\\d\\x = N\\cdot V(S) . \\]<\/p>\n

By an averaging argument, there must be some $\\x\\in[0,1)^n$ such that $\\nu(S+\\x)\/V([0,1)^n)\\geq N\\cdot V(S)$, i.e., the translation $S+\\x$ contains at least $N\\cdot V(S)$ points of $P$, as required.<\/p>\n

Next, we consider the case where $S$ is compact (i.e., closed and bounded<\/a>). Since $\\nu(S+\\x)$ is an integer, if $N\\cdot V(S)$ is not an integer then it immediately follows that $\\nu(S+\\x)>N\\cdot V(S)$. So suppose that $h:=N\\cdot V(S)$ is an integer. Let $S_k:=(1+\\frac{1}{k})S$, so that applying the above result on $S_k$ for each $k\\geq1$ we have that there exists some $\\x_k\\in[0,1)^n$ such that $\\nu(S_k+\\x_k)\\geq N\\cdot V(S_k)>h$.<\/p>\n

Since the $\\x_k$ lie in $[0,1]^n$ which is compact, there must be some subsequence $\\x_{k_j}$ which converges to a point $\\x\\in[0,1]^n$. By construction, each $S_{k_j}+\\x_{k_j}$ contains at least $h+1$ points of $P$. Since $\\bigcup_j S_{k_j}+\\x_{k_j}$ is bounded, it contains a finite number of points of $P$. In particular, there are a finite number of ways of choosing $h+1$ points of $P$ from\u00a0$\\bigcup_j S_{k_j}+\\x_{k_j}$. By the pigeonhole principle, there must be some choice $\\p_1\\c\\dotsc\\c\\p_{h+1}\\in P$\u00a0which appear infinitely often in the sets $S_{k_j}+\\x_{k_j}$. Let $k’_j$ index a subsequence of these sets so that $\\p_i\\in S_{k’_j}+\\x_{k’_j}$ for all $i$ and $j$.<\/p>\n

The points $\\p_i$ must in fact appear in $S+\\x$; otherwise there would be some $\\p_i$ with positive distance to $S+\\x$, but\u00a0the distance of the farthest point of $S_{k’_j}+\\x_{k’_j}$ to $S+\\x$ goes to $0$ as $j\\to\\infty$, contradicting the supposed positive distance that\u00a0$\\p_i\\in S_{k’_j}+\\x_{k’_j}$ is away from $S+\\x$. As required, we have found some translation $S+\\x$ which contains more than $h=N\\cdot V(S)$ points of $P$.
\n<\/a><\/p>\n

Alternate statement<\/h2>\n

Sometimes Blichfeldt’s theorem is stated in the following form:<\/p>\n

Let $S$ be a set in $\\R^n$ with volume $V(S)>m$ for some $m\\in\\Z$ (if $S$ is compact we only require $V(S)\\geq m$). Then $S$ contains $\\x_1\\c\\dotsc\\c\\x_{m+1}$ distinct points whose differences $\\x_i-\\x_j$ all lie in $\\Z^n$.<\/p>\n

This is a simple corollary of what we’ve already shown. Take $P:=\\Z^n$, so that $N=1$. The theorem tells us there is some $\\x$ such that $S+\\x$ contains at least $V(S)\\geq m+1$ (or if $S$ is compact, more than $V(S)\\geq m$) points of $P$. Thus we have there exist $\\p_i\\in P$ and\u00a0$\\x_i\\in S$ with\u00a0$\\p_i=\\x_i+\\x$ for $1\\leq i\\leq m+1$. Then<\/p>\n

\\[ \\x_i-\\x_j = \\p_i-\\p_j \\in \\Z^n , \\]<\/p>\n

as required.<\/p>\n

Generalization<\/h2>\n

Finally, Blichfeldt’s theorem can be generalized to apply to arbitrary lattice points, instead of just $\\Z^n$. One possible way of stating it would be:<\/p>\n

Let $L$ be a lattice in $\\R^n$ with volume $\\det(L)$, and $S$ be a set in $\\R^n$ with volume $V(S)>m\\det(L)$ for some $m\\in\\Z$ (if $S$ is compact we only require $V(S)\\geq m\\det(L)$). Then $S$ contains $\\x_1\\c\\dotsc\\c\\x_{m+1}$ distinct points whose differences $\\x_i-\\x_j$ all lie in $L$.<\/p>\n

The same argumentation as above suffices to show this, except that we replace $[0,1)^n$ (a fundamental region<\/a>\u00a0for $\\Z^n$) in the argument with a fundamental region for $L$.<\/p>\n

\n
<\/div>\n
    \n
  1. A New Principle in the Geometry of Numbers, with Some Applications<\/em><\/a> ↩<\/a><\/span><\/li>\n<\/ol>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

    The following theorem was proven by Blichfeldt1\u00a0in 1914: Let $P$ be a set of points in $\\newcommand{\\R}{\\mathbb{R}}\\R^n$ which are invariant under translation by vectors in $\\newcommand{\\Z}{\\mathbb{Z}}\\Z^n$, and say that $[0,1)^n$ contains $N$ points of $P$. If $S$ is a set … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"_links":{"self":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/848"}],"collection":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=848"}],"version-history":[{"count":0,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/848\/revisions"}],"wp:attachment":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=848"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=848"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=848"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}