Suppose we have the additive subgroup of reals generated by $\sqrt{3}$ and $\sqrt{5}$. How would you show you that this subgroup does not form a lattice?
$\begingroup$
$\endgroup$
6
-
3$\begingroup$ I’m voting to close this question because as asked it's a math question with no motivation $\endgroup$– kodluJan 31 at 20:43
-
$\begingroup$ "How would you show you that this subgroup does not form a lattice?"; are you sure it's not? Isn't the group $\{a\sqrt{3} + b\sqrt{5}\}$ trivially isomorphic to $\mathbb{Z}^2$? Isn't the latter a lattice? $\endgroup$– ponchoJan 31 at 21:00
-
$\begingroup$ @poncho Okay but it should be discrete (this is the definition). More precisely it should contain a shortest vector. I think, without a proof, one can find arbitrarily small vectors in this group. $\endgroup$– Ali Haktan GermanJan 31 at 21:05
-
3$\begingroup$ "More precisely it should contain a shortest vector"; the meaning of 'shortest' depends on the metric; for the traditional metric on $\mathbb{R}$ ($dist(A, B) = |A-B|$), it's straightforward to show there are arbitrary short vectors. For another metric, say, $dist( A\sqrt{3}+B\sqrt{5}, C\sqrt{3}+D\sqrt{5}) = |A-C| + |B-D|$, there is a shortest nonzero vector $\endgroup$– ponchoJan 31 at 21:15
-
$\begingroup$ There’s a frustrating divergence between the mathematics and cryptography communities around the meaning of “lattice”. Cryptographers talk about lattices using the Euclidean metric, rather than the more general mathematical definition. $\endgroup$– Daniel SFeb 1 at 9:18
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
It suffices to show that there exists a sequence of arbitrarily short vectors, i.e. integer sequences $a_n, b_n$, such that
$$|a_n\sqrt{3}+b_n\sqrt{5}| \to 0$$
For this explicit example, note that an obvious choice of $a_n$, $b_n$ is
$$a_n\sqrt{3} = -b_n\sqrt{5}\iff -\frac{a_n}{b_n} = \sqrt{5/3}.$$
One can't exactly choose $a_n, b_n$ to satisfy this inequality ($\sqrt{5/3}$ is irrational). Instead, we choose sequences $a_n/b_n$ of increasingly good rational approximations of $-\sqrt{5/3}$. One can do this explicitly via continued fractions. For example, wolfram alpha states the relevant continued fraction is $[1, 3, 2, 3, 2,\dots]$, meaning $1 + \frac{1}{3 + \frac{1}{2+\frac{1}{3+\dots}}}$.
Anyway, the various finite truncations of this continued fraction will be a sequence of increasingly good rational approximations to $\sqrt{5/3}$. As the continued fraction is infinite, we can keep repeating this process, leading to $a_n, b_n$ such that $|a_n\sqrt{3}+b_n\sqrt{5}|\to 0$.
If $-\sqrt{5/3}$ were rational, its continued fraction would be finite, and the above argument would eventually fail. Note that this means that something like the subgroup generated by $\sqrt{3}$ and $5\sqrt{3}$ is a lattice --- it is the lattice $\sqrt{3}\mathbb{Z}$. It is important that we didn't consider the subgroup generated by $\sqrt{3}, 5\sqrt{3}$ and 1 here --- this is no longer a lattice, by (roughly) the same argument.
