3
$\begingroup$

Does there exist a lattice in $\mathbb{R}^n$, with an independent generative family $(b_1, \dots, b_{n+1})$ of $(n+1)$ vectors (without any loss of generality I suppose $(b_1, \dots, b_{n})$ is a $\mathbb{R}$-basis), for no generative family of size $n$.

I know:

  • If these vectors are in $\mathbb{Q}^n$, then the answer is NO, because the lattice is included in $\frac{1}{q}\mathbb{Z}^n$ with $q\in \mathbb{N},$ and $\frac{1}{q}\mathbb{Z}^n$ is a free $\mathbb{Z}-$module of rank $n$, (and a sub module of a free module is free with rank lower than the bigger).

  • It exists $(\lambda_1, \lambda_2, \dots, \lambda_n, \lambda_{n+1})\in \mathbb{Z}^{n+1}$, such that $\sum^{n+1}_{i=1} \lambda_i b_i=0.$ (Else, we can create an infinite number of points in the fundamental parallepiped of $(b_1, \dots, b_n).)$

But I do neither know how deduce the existence of a generative family of size $n$, nor to show the existence of base (because a potential family of size $(n+1)$ is clearly not).

$\endgroup$
4
  • $\begingroup$ what do you mean by independent generative family? $\endgroup$
    – Don Freecs
    Jan 17, 2023 at 17:01
  • $\begingroup$ It means for any $i$, $b_i$ is not $\mathbb{Z}$-generated by the others $b_j$'s. $\endgroup$
    – Ievgeni
    Jan 18, 2023 at 10:25
  • 1
    $\begingroup$ No. you can have $\mathbb{R}$-dependancy and $\mathbb{Z}$-independancy. $\endgroup$
    – Ievgeni
    Jan 18, 2023 at 14:04
  • $\begingroup$ oh you are right excuse me $\endgroup$
    – Don Freecs
    Jan 18, 2023 at 14:52

2 Answers 2

1
$\begingroup$

Two things

  • One can always find a generating set of a lattice of size at most the dimension of the ambient space (so you can always find an $n$-dimensional generating set for a lattice in $\mathbb{R}^n$)
  • One can always reduce a generating set of a lattice to a basis (there are standard algorithms, namely for computing what is called the Hermite Normal Form).

Your question does have an interesting component to it though. In particular, many lattice problems (such as the Shortest Independent Vectors Problem) are phrased in terms of sets of independent vectors (that generate a subspace $E$ of a certain rank, but need not be a basis for $L\cap E$). For a particular example, there is an explicit 10-dimensional lattice known such that

  • that lattice is generated by its minimal vectors, but
  • it (provably) has no basis of minimal vectors.

It is known that 10 is the lowest dimension this can occur in. Note that one can bound the gap between the (product of the) norms of elements in a minimal generating set of a lattice, see Hermite vs Minkowski by Martinet.

This has some relevance to cryptography, as certain lattice algorithms (either Babai's nearest planes or Babai rounding, I forget) do not require a basis to function, but only a generating set. I've seen some authors (I believe one of Chris Peikert's papers) use this insight for a particular lattice, I believe $D_n^* = 2\mathbb{Z}^n + (1,1,\dots,1)^t\cdot\mathbb{Z}$, but I would have to check. Specifically, by instantiating the algorithm with a short set of independent vectors (vs a short basis), one can sometimes get better algorithmic performance.

$\endgroup$
4
  • $\begingroup$ Can you argue about the two things (especially the first one). $\endgroup$
    – Ievgeni
    Jan 14, 2023 at 7:55
  • 1
    $\begingroup$ First note that one can reduce to the case of dimension 1 --- let $[b_1,\dots, b_m]$ be a family of independent generators of a lattice $\Lambda$ in $\mathbb{R}^m$. Projecting everything orthogonal to $b_1$ yields a family $[b_2',\dots, b_m']$ of independent generators of a lattice $\Lambda'$ in $\mathbb{R}^{n-1}$. Iterating this yields a family $[b_{n}'',\dots, b_m'']$ generating a 1 dimensional lattice in $\mathbb{R}$. Next, note that any lattice $L$ in $\mathbb{R}$ takes the form $a\mathbb{Z}$ for $a> 0$. Explicitly, the lattice $\lambda_1(L)\mathbb{Z}$ always works. $\endgroup$
    – Mark Schultz-Wu
    Jan 15, 2023 at 3:03
  • 1
    $\begingroup$ Essentially, this will always generate a sublattice at least. But if this sublattice is proper, it is easy to show that this implies that there exists a vector in $L$ shorter than $\lambda_1(L)$, which is clearly silly. Note that the reduction to dimension 1 does require some nuance, namely one needs a good understanding which orthogonal projections preserve the lattice being discrete (not all of them will!). The requirement (it is both sufficient and necessary) for projecting onto a subspace $E$ being discrete is that $L\cap E$ is discrete. So the whole problem reduces to proving this $\endgroup$
    – Mark Schultz-Wu
    Jan 15, 2023 at 3:03
  • 2
    $\begingroup$ characterization. I don't remember it being that bad, so I'll let you try first. Or, if you believe this characterization (it can be found in Proposition 1.1.4 of Martinet's "Perfect lattices in Euclidean Space", though the proof there would be circular in our context, as it relies on what you want to be true to be true), we're done. We could prove it like Martinet does (Theorem 1.1.2), but this punts things over to a general topological fact about closed subgroups of $\mathbb{R}^n$, which might be wrong pedagogically for a cryptographic audience. $\endgroup$
    – Mark Schultz-Wu
    Jan 15, 2023 at 3:09
0
$\begingroup$

You just need to use LLL algorithm for $(b_1, \dots, b_{n+1})$. More specifically, In BGPS21,the Algorithm 1 and Theorem 3.6 gave a more efficient algorithm than LLL.

$\endgroup$
1
  • $\begingroup$ Can you precise your answer? $\endgroup$
    – Ievgeni
    Apr 12, 2023 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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