{"id":780,"date":"2014-01-29T22:19:08","date_gmt":"2014-01-30T03:19:08","guid":{"rendered":"http:\/\/www.curtisbright.com\/bln\/?p=780"},"modified":"2014-01-29T22:19:08","modified_gmt":"2014-01-30T03:19:08","slug":"two-characterizations-of-a-lattice","status":"publish","type":"post","link":"http:\/\/localhost\/blog\/index.php\/2014\/01\/29\/two-characterizations-of-a-lattice\/","title":{"rendered":"Two characterizations of a lattice"},"content":{"rendered":"

A lattice<\/a>\u00a0is a discrete additive subgroup of $\\newcommand{\\R}{\\mathbb{R}}\\R^n$; for the purposes of this post we’ll restrict ourselves to\u00a0full rank<\/em>\u00a0lattices, i.e., those which span the entire vector space $\\R^n$. An alternate way of defining a lattice is to consider it as the\u00a0integer span<\/em> of a collection of linearly independent vectors $\\newcommand{\\b}{\\mathbf{b}}\\newcommand{\\c}{{,}~}\\b_1\\c\\dotsc\\c\\b_n\\in\\R^n$, known as a basis<\/em> of $L$. That is, $L$ consists of the collection of points<\/p>\n

\\[ \\newcommand{\\norm}[1]{\\lVert#1\\rVert}\\newcommand{\\x}{\\mathbf{x}}\\newcommand{\\Z}{\\mathbb{Z}} \\biggl\\{\\,\\sum_{i=1}^n x_i\\b_i : x_i\\in\\Z \\,\\biggr\\} . \\]<\/p>\n

The goal of this post is to show that these two ways of defining a lattice are equivalent. It is more or less immediate that a lattice $L$ in the second sense is an additive subgroup which spans $\\R^n$; it is also discrete since one can show that1<\/a><\/sup><\/p>\n

\\[ \\newcommand{\\0}{\\mathbf{0}} \\norm{\\x} \\geq \\min_{1\\leq i\\leq n}\\norm{\\b_i^*} \\]<\/p>\n

for all $\\x\\in L$ and $\\x\\neq\\0$, where $\\b_i^*$ is the Gram–Schmidt orthogonalization<\/a>\u00a0of $\\b_i$. Thus $\\0$ is an isolated point of $L$, and it follows that every point of $L$ must be isolated;\u00a0a nonisolated point would imply (using a suitable translation) that $\\0$ is nonisolated.<\/p>\n

The harder direction is to show that a lattice in the first sense is also a lattice in the second sense; the remainder of the post is devoted to this. Let $L$ be a discrete additive subgroup of $\\R^n$ containing $n$ linearly independent vectors.<\/p>\n

In the case $n:=1$, since $L$ spans $\\R$ it must contain $\\pm a\\neq0$. Since it also contains $0$ and is discrete, there must be a minimal $b>0$ with $b\\in L$. Then as required we have $L= \\{\\, xb : x\\in\\Z \\,\\}$; if there was any point $c=xb\\in L$ for $x\\notin\\Z$ then $c-\\lfloor x\\rfloor b$ would lie in $L$ and $(0,b)$, a contradiction to the minimality of $b$.<\/p>\n

Now suppose the result holds for all lattices in $\\R^{n-1}$; we will show the result holds for $L$ and appeal to induction. We know that $L$ contains $n$ linearly independent vectors; select any $n-1$ of them and let $S$ be the subspace they generate. Let $S’$ be the rotation of $S$ such that every vector in $S’$ has a $0$ in its final coordinate. Crucially, applying the rotation on $L$ to form $L’$ preserves the discrete additive subgroup structure, so we can apply the induction hypothesis to the discrete additive subgroup\u00a0formed by only considering the first $n-1$ coordinates of $S’\\cap L’$. Let $\\b_1\\c\\dotsc\\c\\b_{n-1}$ be a basis of this lattice (which exists by hypothesis), except extended with an extra $0$ coordinate so as to live in $\\R^n$ instead of $\\R^{n-1}$.<\/p>\n

Since $L’$ generates $\\R^n$, it must contain a vector not in $S’$, i.e., with nonzero final coordinate. Furthermore, it must contain a vector with minimal<\/em> positive final coordinate; otherwise there would exist a sequence $\\newcommand{\\N}{\\mathbb{N}}\\{\\x_i\\in L’\\}_{i\\in\\N}$ with $(x_i)_n\\to0$ as $i\\to\\infty$. By translating the $\\x_i$ by suitable multiples of $\\b_1\\c\\dotsc\\c\\b_{n-1}$ we can ensure that they lie in the compact set<\/p>\n

\\[ \\biggl\\{\\, \\sum_{i=1}^{n-1} \\alpha_i \\b_i + (0,\\dotsc,0,\\alpha) : \\alpha_i\\in[0,1]\\c\\lvert \\alpha\\rvert\\leq\\max_{i\\in\\N}\\lvert(x_i)_n\\rvert\u00a0\\,\\biggr\\} , \\]<\/p>\n

and therefore some subsequence of the $\\x_i$ converges to some point in the set. Taking successive differences of this subsequence we get a sequence of points in $L’$ which converge to $\\0\\in L’$, a contradiction to the discreteness of $L’$.<\/p>\n

Let $\\b_n\\in L’$ be a vector with minimal nonzero final coordinate. We claim that $\\b_1\\c\\dotsc\\c\\b_n$ is a basis for $L’$. Let $\\x\\in L’$ be arbitrary, and consider<\/p>\n

\\[ \\x’ := \\x – \\biggl\\lfloor \\frac{x_n}{(b_n)_n} \\biggr\\rfloor \\b_n \\in L’ . \\]<\/p>\n

Its final coordinate is $x_n-\\lfloor x_n\/(b_n)_n\\rfloor(b_n)_n\\in[0,(b_n)_n)$ and therefore by minimality of $(b_n)_n$ it must be $0$, so $\\x’\\in S’\\cap L’$ and therefore can be written as an integer combination of $\\b_1\\c\\dotsc\\c\\b_{n-1}$. Thus $\\x=\\x’+\\lfloor x_n\/(b_n)_n\\rfloor\\b_n$ can be written as an integer linear combination of $\\b_1\\c\\dotsc\\c\\b_n$, and so these vectors form a basis of $L’$. Applying the reverse rotation of $L\\mapsto L’$ to the basis\u00a0$\\b_1\\c\\dotsc\\c\\b_n$ gives us a basis of $L$, as required.<\/p>\n

\n
<\/div>\n
    \n
  1. To see this, write $\\x = \\sum_{i=1}^n x_i \\b_i = \\sum_{i=1}^n x_i^* \\b_i^*$. Let $k$ be the largest $i$ such that $x_i\\neq0$, so $\\DeclareMathOperator{\\sp}{span} \\x \\in x_k \\b_k^* + \\sp(\\b_1,\\dotsc,\\b_{k-1})$ which shows that $x_k^*=x_k\\in\\Z$. Then\n

    \\begin{equation}\\norm{\\x}^2 = \\sum_{i=1}^k (x_i^*)^2 \\norm{\\b_i^*}^2 \\geq (x_k^*)^2 \\norm{\\b_k^*}^2 \\geq \\min_{1\\leq i\\leq n} \\norm{\\b_i^*}^2 , \\end{equation}<\/p>\n

    as required. ↩<\/a><\/span><\/li>\n<\/ol>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

    A lattice\u00a0is a discrete additive subgroup of $\\newcommand{\\R}{\\mathbb{R}}\\R^n$; for the purposes of this post we’ll restrict ourselves to\u00a0full rank\u00a0lattices, i.e., those which span the entire vector space $\\R^n$. An alternate way of defining a lattice is to consider it as … 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\/780"}],"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=780"}],"version-history":[{"count":0,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/780\/revisions"}],"wp:attachment":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=780"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=780"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}