0
$\begingroup$

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?

$\endgroup$
6
  • 3
    $\begingroup$ I’m voting to close this question because as asked it's a math question with no motivation $\endgroup$
    – kodlu
    Jan 31, 2023 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$
    – poncho
    Jan 31, 2023 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$ Jan 31, 2023 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$
    – poncho
    Jan 31, 2023 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 S
    Feb 1, 2023 at 9:18

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.