1 Introduction↩︎

A lattice \(\mathcal{L}\) in the \(n\)-dimensional Euclidean space \(\mathbb{R}^n\) is the set of all integer linear combinations of \(n\) linearly independent column vectors \({\boldsymbol{v}}_1, \cdots, {\boldsymbol{v}}_n\) in \(\mathbb{Z}^n\). Note that we only consider full rank integral lattices in \(\mathbb{R}^n\), that is, rank \(n\) subgroups of \(\mathbb{Z}^n\). The square matrix \(M =({\boldsymbol{v}}_1, \cdots, {\boldsymbol{v}}_n)\) is called a basis of \(\mathcal{L}\). The lattice \(\mathcal{L}\) generated by \(M\) is defined as \[\mathcal{L} = \mathcal{L}(M): = \{ \sum_{i=1}^n a_i {\boldsymbol{v}}_i: \;a_1, \cdots, a_n \in \mathbb{Z}\}.\]

Lattices are classically studied mathematical objects, which originated from the work of Gauss [1] over \(200\) years ago. They have proved to be invaluable in many computer science applications, including integer programming [2], [3], coding theory [4], cryptanalysis [5]–[7], most notably in lattice based cryptography [8]–[10] which has the potential advantage of resisting quantum attacks. In fact, the security of lattice based cryptography depends on the hardness of computational lattice problems. This is a highly active research area, both in theoretical computer science and in cryptography.

The central algorithmic problem in lattices is the Shortest Vector Problem (SVP): given a lattice basis \(M\) as input, find a shortest non-zero lattice vector in \(\mathcal{L}(M)\). The fundamental question here is whether or not there is a polynomial time algorithm to solve SVP, that is, \({\rm SVP} \in {\boldsymbol{P}}\)? The celebrated LLL algorithm [11] and all subsequent improvements do find a shortest non-zero lattice vector, but their running times are all exponential in \(n\). Alternatively, they can be viewed as a polynomial time algorithm but only find a short lattice vector which may be exponentially longer than a shortest non-zero lattice vector.

From the very beginning, SVP was believed to be computationally intractable for large \(n\). Nevertheless, its precise complexity remains a long standing open problem in theoretical computer science, see [12]–[14] for recent surveys on this subject and its applications in post-quantum cryptography.

This conjecture implies that \({\rm SVP} \not\in {\boldsymbol{P}}\), that is, there is no polynomial time algorithm to solve SVP, under the standard assumption that \({\boldsymbol{N}P} \not= {\boldsymbol{P}}\), thus answering the fundamental algorithmic question on SVP.

Almost twenty years after van Emde Boas’s pioneering work, a major breakthrough was made by Ajtai [16] who proved that SVP is NP-hard under random polynomial time reduction. This implies that \({\rm SVP} \not\in {\boldsymbol{P}}\) under the stronger assumption that \({\boldsymbol{N}P} \not= {\boldsymbol{R}P}\), where we ignore the technical difference between one-sided error and two-sided error, such as BPP and ZPP.

To prove the full conjecture of van Emde Boas, one needs to remove the randomness from Ajtai’s random polynomial time reduction. This has been attempted by several authors over the years. In particular, Micciancio [17] simplified Ajtai’s sophisticated construction and formalized a derandomization approach, assuming a conjectural efficient deterministic construction of a certain combinatorial gadget called a locally dense lattice with an explicit bad center, see [18]. Micciancio proposed two ways to efficiently construct the desired gadget. The first one [17] is via the conjectural distribution of smooth numbers in very short intervals, but this number theoretic conjecture is currently out of reach, even if one assumes the Riemann hypothesis. The second one [19] is the construction of the gadget using a tower of binary BCH codes. It seems difficult to make this work as well. More recently, Bennett-Peikert [20] gave a third method to construct the desired gadget via the lifting of Reed-Solomon codes over large prime finite fields. This new method looks simpler and more amenable for de-randomization, as its coding theory analogue [21] (the construction of a similar coding theory gadget using Reed-Solomon codes over large finite fields) had been de-randomized a decade ago [22] via an application of Weil’s bound for character sums on curves, see also [18], [23] for new simpler proofs. However, as shown in [20], a similar application of the Weil bound does not yield any useful information in the lattice setting. The lattice version of the de-randomization along this line turns out to be much deeper, going far beyond the Weil bound. In this paper, we show that the problem can be solved by appealing to some of the deepest theorems in arithmetic geometry, including the full strength of Deligne’s theorem on the Weil conjectures. Our main result is

This settles Conjecture 1. The same shortest vector problem can be studied in \(\ell_p\) norm for \(1\leq p \leq \infty\), not just the Euclidean norm \(\ell_2\). In addition, the above SVP is a search problem. To prove its hardness, it suffices to prove the hardness of its decision version. As in the literature, we will study the more general \(\gamma\)-approximation decision version in the \(\ell_p\)-norm, called \(\gamma\)-GapSVP\(_p\), where \(1\leq p \leq \infty\) is any fixed real number or \(\infty\), and \(\gamma\geq 1\) is the approximation factor, usually a constant or a function of \(n\). Recall that the \(\ell_p\)-norm in \(\mathbb{R}^n\) is defined by \[\|(x_1,\cdots, x_n)\|_p = (\sum_{i=1}^n |x_i|^p)^{1/p}, \;\;\;\;\|(x_1,\cdots, x_n)\|_{\infty} = \max_{1\leq i\leq n} |x_i|.\] The case \(p=2\) gives the Euclidean norm in \(\mathbb{R}^n\), which is the most important case in applications. One reason to consider the \(p \not= 2\) case is that the problem tends to become more tractable as \(p\) grows. In fact, for \(p=\infty\), van Emde Boas [15] already proved that SVP is NP-hard in \(\ell_{\infty}\)-norm. In addition, one can hope that ideas which are first introduced to handle the large \(p\) case can sometimes be improved to handle the smaller \(p\) case as well.

We now make the approximation version and its \(\ell_p\)-norm analogue more precise for \(1\leq p \leq \infty\). A crucial quantity of a lattice is its minimum distance.

The \(\gamma\)-approximation decision version is the following promise problem. Note that the approximation factor \(\gamma\) is always assumed to satisfy \(\gamma \geq 1\).

For the exact problem, where \(\gamma = 1\), we simply write GapSVP\(_p\). Let \({\rm SVP}_p\) denote the problem of computing a shortest non-zero lattice vector in \(\ell_p\)-norm. Thus, \({\rm SVP}\) is simply \({\rm SVP}_2\). If GapSVP\(_p\) is NP-hard, then \({\rm SVP}_p\) is NP-hard. For \(p=\infty\), van Emde Boas [15] proved that GapSVP\(_{\infty}\) is NP-hard. One expects that van Emde Boas’s conjecture extends from \(p=2\) to all finite \(p\).

This generalized conjecture has been studied extensively in the literature. As mentioned earlier, major progress was made by Ajtai in the classical case \(p=2\).

Ajtai’s randomness result for the exact problem with \(\gamma=1\) has been improved to larger and larger constant \(\gamma\geq 1\), see [17], [19], [24]–[28]. It is now known that for all \(p\geq 1\), \(\gamma\)-GapSVP\(_p\) is NP-hard for any constant \(\gamma \geq 1\), and hard for nearly polynomial factor \(\gamma = O(n^{\Omega(1/\log\log n)})\), all under random reduction. Note that for \(p\geq 2\), \(\gamma\)-GapSVP\(_p\) is unlikely to be NP-hard for \(\gamma \geq c_p\sqrt{n}\), where \(c_p\) is some positive constant depending only on \(p\), see [29]–[31]. On the other hand, the security of lattice based cryptography often depends on the conjectural hardness of \(\gamma\)-GapSVP\(_p\) for even larger factor \(\gamma\), typically polynomial in \(n\). This suggests that it is unlikely to prove any NP-hardness security for most of the lattice based cryptographic systems. In particular, finding a short non-zero lattice vector \(v\) with \(\|v\|_2 \leq \sqrt{n} |\det(M)|^{1/n}\) (the so-called Minkowski-SVP) is expected to be hard, but not NP-hard.

De-randomization of the above randomness results are long-standing open problems. Historically, the only de-randomization approach is the construction of locally dense lattices as formulated by Micciancio. Very recently, there are other approaches based on PCP and the subset sum problems that also become fruitful. For \(p>2\), strong deterministic hardness results are obtained in several recent papers. Most notably, Hair-Sahai [32] shows that for any \(p>2\) and any \(\epsilon>0\), \(\gamma\)-\({\rm GapSVP}_p\) is \({\boldsymbol{N}P}\)-hard for \(1\leq \gamma < 2^{\log^{1-\epsilon}n}\). This proves the deterministic \({\rm NP}\)-hardness of \({\rm SVP}_p\) for all \(p>2\) and hence settles Conjecture 5 for all \(p>2\). The approach in [32] via PCP so far cannot handle the case \(1\leq p \leq 2\), including the most important \(p=2\) case. In Hecht-Safra [33], again via PCP techniques, it is shown that for every constant \(p>2\), any constant \(1\leq \gamma < \sqrt{2}\), \(\gamma\)-\({\rm GapSVP}_p \not\in {\boldsymbol{P}}\), unless \({\boldsymbol{3}SAT} \in {\boldsymbol{D}TIME}(2^{O(n^{2/3}\log n})\). This proves deterministic hardness results, but only under sub-exponential time reduction (not polynomial time reduction) and so far applies only to \(p>2\). Hittmeir [34] proved a fine grained deterministic hardness result for \(\gamma\)-\({\rm GapSVP}_p\), where \(p\) is the parameter. The proof is via reduction to a variant of the subset sum problem. All these new approaches so far cannot handle the deterministic \({\boldsymbol{N}P}\)-hardness for \(1\leq p \leq 2\), most notably the case \(p=2\). In a new preprint, Hair-Sahai [35] independently made a breakthrough and proved deterministic hardness result for all \(1\leq p < \infty\) via PCP approach, although so far only under sub-exponential time reduction and thus does not prove the deterministic \({\boldsymbol{N}P}\)-hardness for \(1\leq p \leq 2\).

We now return to earlier locally dense lattice developments with more details, as this is the direction we shall follow. Classically, the de-randomization of Ajtai’s result (for \(p=2\)) has been studied by a different approach, namely, via a reduction to CVP, the closest vector problem which is long known to be \({\rm NP}\)-hard [15]. In [17], [19], this de-randomization is reduced to the construction of a certain combinatorial gadget. Roughly speaking, this gadget consists of a locally dense lattice \(\mathcal{L}\) together with an explicit shift (coset) \(s+\mathcal{L}\) which contains subexponentially many short vectors with norm at most a fraction of the minimum distance. In particular, list decoding is not feasible for the bad center \(s\) with this error radius. Usually, the construction of such a locally dense lattice \(\mathcal{L}\) is not very difficult. A random choice of \(s\) would give a bad center with high probability. This leads to a probabilistic polynomial time reduction. To derandomize the algorithm, one must give an efficient deterministic construction of the bad center \(s\), which can usually be guessed. The difficulty is to prove that the guessed bad center is indeed a bad center. It is here that one needs to prove a mathematical theorem.

In [Mic98], Micciancio proposed a number theoretic approach to deterministically construct a locally dense lattice \(\mathcal{L}\) and a bad center \(s\). For this to work, one needs to assume the conjecture that for any \(\epsilon>0\), there is a positive number \(d>0\) such that the short interval \([n, n+ n^{\epsilon}]\) contains an odd squarefree \(\log^d n\)-smooth integer for all large \(n\). This number theoretic conjecture is currently out of reach, even assuming the Riemann hypothesis. In [Mic12], a more sophisticated method is proposed based on a tower of binary BCH codes. This has the advantage of introducing probabilistic reduction with only one-sided error, not two-sided errors as with the reductions in [25], [28]. Thus, the work in [19] partially derandomizes the reductions in [25], [28], and suggests that this could be a viable approach to a full derandomization. Although this binary BCH code connection sounds more plausible, the binary finite field \(\mathbb{F}_2\) is too small to apply any deep tool from arithmetic geometry.

A few years ago, Bennett and Peikert [BP23] introduced a third approach to construct the desired lattice gadget via the lifting of Reed-Solomon codes over large prime finite fields, in particular giving a much simpler new proof of Ajtai’s randomness result. This Reed-Solomon lattice approach, although still random, looks more de-randomizable. This is because the analogous gadget in coding theory, called a locally dense code, is deterministically constructed in [CW09] based on an application of Weil’s bound for character sums. As a consequence, this establishes the deterministic \({\boldsymbol{N}P}\)-hardness of approximating the minimum distance of a linear code, and hence derandomizes the main result in [21] via the connection to Reed-Solomon codes. To de-randomize the lattice result in [BP23], one needs to show that the suggested bad center of the locally dense Reed-Solomon lattice (which is a lifting of a Reed-Solomon code, but not a code itself) is indeed a bad center. This turns out to be much harder, as attempted in [BP23], the Weil bound is not strong enough to deduce any useful information. In this work, we show that the much deeper Deligne bound for higher dimensional varieties can be fruitfully applied to prove that the suggested bad center is indeed a bad center with the required projection property, thereby proving [18] on efficient deterministic constructions of locally dense lattices. As a consequence, we obtain

This theorem de-randomizes the main result in [BP23]. Taking \(\gamma=1\), it proves the conjecture of van Emde Boas stated earlier. An interesting problem is to find an elementary proof of the above theorem. Another problem is to extend this theorem to any constant \(\gamma \geq 1\), possibly via some sort of tensor approach to amplify the constant. For \(p>2\), this is already known by [32], even for much larger \(\gamma\), via the PCP approach. It would be interesting to see if the PCP techniques in [32] [33] and the subset sum approach in [34] can be adapted to handle the small \(p\) case, perhaps with an application of Deligne’s theorem.

The content of the paper is organized as follows. In section \(2\), we review the definition of locally dense lattices and its connection to de-randomization of SVP, following [[19]][20]. In section \(3\), we review the definition of Reed-Solomon lattices and its connection to the construction of locally dense lattices, following [20]. This reduces the problem to the study of \(\mathbb{F}_q\)-rational points on various algebraic varieties over the finite field \(\mathbb{F}_q\) of \(q\) elements, where \(q\) is a large prime number. In section \(4\), the geometry of these varieties is studied. It is shown that these varieties are complete intersections with mild singularities. In section \(5\), Deligne’s theorem on Riemann hypothesis and the total Betti number bound in [37] are applied to give a sharp estimate for the number of \(\mathbb{F}_q\)-rational points on these varieties. In section \(6\), an inclusion-exclusion sieving is used to prove that the Reed-Solomon lattice is indeed a locally dense lattice in a weaker sense without projection. In section \(7\), a further sieving is applied to show that the Reed-Solomon lattice is a locally dense lattice in the strong sense with projection, thus completing the proof of de-randomization.

Acknowledgements: I would like to thank Qi Cheng and Hendrik Lenstra for helpful discussions on this and related topics over the years. My initial interest in lattices started with my visit to Institute for Advanced Study at Tsinghua University many years ago. It is a pleasure to thank Xiaoyun Wang for her hospitality and for arranging my visit to her group at the institute.

2 Locally dense lattices↩︎

Locally dense lattices as introduced by Micciancio are fundamental in proving complexity results and in de-randomization. They are also of independent interest as a basic object of study in mathematics and theoretical computer science. In this section, we review the notion of locally dense lattices, beginning with a description of a simplified version.

Roughly speaking, a lattice \(\mathcal{L}\) in \(\mathbb{R}^n\) is called locally dense if for some \(\alpha \in (0, 1)\), there is \(x \in \mathbb{Z}^n\) such that the shift \(x + \mathcal{L}\) contains at least \(2^{n^{\epsilon}}\) elements of \(\ell_p\)-norm at most \(\alpha \lambda^{(p)}(\mathcal{L})\) for some \(\epsilon >0\). That is, the ball \(B(0, \alpha \lambda^{(p)}(\mathcal{L}))\) centered at \(0\) with \(\ell_p\)-radius \(\alpha \lambda^{(p)}(\mathcal{L}) < \lambda^{(p)}(\mathcal{L})\) contains subexponentially many vectors in \(x+\mathcal{L}\). Namely, \[|B(0, \alpha \lambda^{(p)}(\mathcal{L})) \cap (x + \mathcal{L})| \geq 2^{n^{\epsilon}}.\] Clearly, \(\alpha \geq 1/2\) for the ball to contain more than one vector in \(x+\mathcal{L}\). Furthermore, \(\alpha> 2^{-1/p}\) for the ball to contain more than a polynomial number of vectors in \(x+\mathcal{L}\), at least in the \(\ell_2\)-norm case, see [9]. Thus, we can and will assume that \(\alpha \in (2^{-1/p}, 1)\). The center \(x\) is called a bad center of the lattice \(\mathcal{L}\). Locally dense lattices are not efficiently list decodable, even combinatorially, to within the distance \(\alpha \lambda^{(p)}(\mathcal{L})\) around the bad center \(x\). Locally dense lattices are crucial in proving complexity results for lattices [19]. A locally dense lattice usually has many bad centers, which can often be proved by an average argument. A suitable sampling would then find a bad center with non-trivial probability. This leads to hardness results with random polynomial time reduction. To obtain a deterministic reduction, one needs to construct one bad center in deterministic polynomial time. This is the key in the de-randomization.

We now recall the formal definition of locally dense lattices following [19] and [20]. The formal definition is a little more complicated than the above simplified intuitive description.

In applications, one wants to take \(n\) to be a polynomial in \(r\), or more precisely \(r \sim n^{\epsilon}\) for some \(\epsilon>0\). Part (1) implies that the \(\ell_p\)-minimum distance of the lattice is large. Part (2) implies that not just \(V\), but also its image \(A(V)\) under the linear map \(A\) contains at least \(2^r \sim 2^{n^{\epsilon}}\) elements. In particular, the number of elements in these two sets is at least subexponential in \(n\).

In our de-randomization, we will take \(A\) to be the projection map of \(V\) to the first \(r\) coordinates, that is, \(A(z_1,\cdots, z_n)^T =(z_1,\cdots, z_r)^T\). Namely, \(A = (I_r, 0_{r, n-r})\), where \(I_r\) is the \(r\times r\) identity matrix, and \(0_{r, n-r}\) denotes the \(r\times (n-r)\) zero matrix. If in the definition, we only require part (1) and the weaker assumption that \(V\) has subexponentially many elements (without the projection part \(A(V)\)), then \(\mathcal{L}\) is called a locally dense lattice in the weaker sense. If we require both part (1) and part (2) as in the definition, then \(\mathcal{L}\) is a locally dense lattice as defined above, also called a locally dense lattice in the strong sense, to distinguish it from the weaker sense. Usually, a locally dense lattice in the weaker sense can be proved to be a locally dense lattice in the strong sense, with some extra work. So, the most crucial starting part is to construct a locally dense lattice in the weaker sense.

The following reduction is [BP23, Corollary 2.11], see also [Mic12, Theorem 5.1].

In the literature, there are several ways to construct locally dense lattices, but none of them is deterministic. The main idea in [20] is to construct the desired locally dense lattices via the lifting of Reed-Solomon codes. This is the approach that we build on. We recall its construction in next section.

3 Reed-Solomon lattices↩︎

Let \(q\) be a prime, and \(\mathbb{F}_q = \mathbb{Z}/q\mathbb{Z}\) be the prime finite field of \(q\) elements. Write \(\mathbb{F}_q =\{ a_1, \cdots, a_q\}\). This ordering of the elements in \(\mathbb{F}_q\) will be fixed. For positive integer \(1< k < q\), let \[H =H_q(k): = \begin{pmatrix} 1 & 1 & \cdots & 1 \\ a_1 & a_2 & \cdots & a_q \\ \vdots & \vdots & \ddots & \vdots \\ a_1^{k-1} & a_2^{k-1} & \cdots & a_q^{k-1} \end{pmatrix}.\] The transposes of the \(k\) row vectors of \(H_q(k)\) generate the \(k\)-dimensional Reed-Solomon code \(RS_q(k)\) in \(\mathbb{F}_q^q\). We shall work with the dual code of \(RS_q(k)\), which is the \((q-k)\)-dimensional Reed-Solomon code \(RS_q(q-k)\) in \(\mathbb{F}_q^q\). Thus, the \(k\times q\)-matrix \(H_q(k)\) is the parity-check matrix of \(RS_q(q-k)\) in \(\mathbb{F}_q^q\). That is, \[RS_q(q-k) = \{ x \in \mathbb{F}_q^q: H_q(k)x = 0\}.\] It is a \((q-k)\)-dimensional MDS code in \(\mathbb{F}_q^q\), and hence has minimum distance \(q-(q-k)+1 = k+1\).

By definition, a column vector \({\boldsymbol{v}} \in \mathbb{Z}^q\) is in \(\mathcal{L}_{q,k}\) if and only if its reduction \({\boldsymbol{v}}\mod q\) is in \(RS_q(q-k)\). It is clear that \(\mathcal{L}_{q,k}\) is a full rank lattice in \(\mathbb{Z}^q\) as it contains \(q\mathbb{Z}^q\). One checks that the determinant of \(\mathcal{L}_{q,k}\) is given by \[\det(\mathcal{L}_{q,k}) = |\mathbb{Z}^q/\mathcal{L}_{q,k}| = |\mathbb{F}_q^q/\mathbb{F}_q^{q-k}| = q^k.\] Since the minimum Hamming distance of \(RS_q(q-k)\) is \(k+1\), it follows that the \(\ell_p\)-minimun distance of \(\mathcal{L}_{q,k}\) satisfies \[\lambda^{(p)}(\mathcal{L}_{q,k}) \geq (k+1)^{1/p}.\] An important observation in [BP23] is the following improvement.

We would like to show that \(\mathcal{L}_{q,k}\) is a \((p, \alpha, \lfloor q^{\epsilon}\rfloor, q)\)-locally dense lattice in \(\mathbb{Z}^q\) for each constant \(\alpha \in (2^{-1/p}, 1)\) and for suitable choices of \(1\leq k < q/2\) and \(0<\epsilon<1\). Most importantly we need to construct and prove an explicit bad center.

Let \(1\leq h \leq q/2\) be an integer. We take \(y\) to be any binary vector in \(\mathbb{Z}^q\) with Hamming weight \(h\). For explicitness, in this paper, we will just take \[y = (1, \cdots, 1, 0, \cdots, 0)^T \in \mathbb{Z}^q\] with the first \(h\) coordinates being \(1\) and the last \(q-h\) coordinates being \(0\). Write \[u: = H_q(k) y = (h, h_1, \cdots, h_{k-1})^T \in \mathbb{F}_q^k.\] Clearly the first coordinate of \(u\) is \(h\), as the first row of \(H_q(k)\) is \((1, 1, \cdots, 1)\). By definition, one checks that we have

We shall prove that this explicit vector \(y\) is a bad center of the locally dense Reed-Solomon lattice \(\mathcal{L}_{q,k}\) for suitable choices of \(k\) and \(h=\lfloor (1+\epsilon)k\rfloor \leq q/2\). To show that the coset \(y+\mathcal{L}_{q,k}\) contains many short vectors, it is enough to show that it contains many binary short vectors. For this purpose, we introduce the following subset \(S_2(y, h)\), where the subscript \(2\) means that we only consider binary vectors.

Every vector \(x\) in \(S_2(y, h)\) is a binary vector of Hamming weight \(h\) and thus its \(\ell_p\)-norm is bounded by \[\| x\|_p = h^{1/p} \leq \alpha \cdot (2k)^{1/p} \leq \alpha \cdot \lambda^{(p)}(\mathcal{L}_{q,k}).\] This gives the following

In order to show that \(V\) satisfies condition (2) in Definition 10, it is sufficient to show that the linear projection to the first \(r\) coordinates, when restricted to the subset \(S_2(y,h)\), is already surjective onto \(\{0, 1\}^r\). That is, we want to show that \[\{0, 1\}^r \subseteq A(S_2(y, h)).\] To do that, we first treat the simpler case of estimating \(|S_2(y, h)|\), showing that it is at least subexponential in \(n=q\). The stronger version with linear projection will be handled in the final section.

As mentioned, our first goal is to show that the cardinality of the set \(S_2(y, h)\) is at least subexponential in \(q\), that is, \(|S_2(y, h)| \geq q^{\delta k}\) for some \(\delta > 0\), \(h= \lfloor(1+\epsilon)\cdot k \rfloor\) and \(k =\lfloor q^{\epsilon_1}\rfloor\) with \(0< \epsilon_1<1\). To do so, we relate the number \(|S_2(y, h)|\) to the number of \(\mathbb{F}_q\)-rational points on some quasi-projective algebraic variety over \(\mathbb{F}_q\), and then apply results from arithmetic geometry such as Deligne’s theorem on the Weil conjectures.

Recall that \(\mathbb{F}_q =\{a_1, \cdots, a_q\}\) with a fixed ordering. Let \(x =(x_1, \cdots, x_q)^T \in S_2(y, h)\). It is a binary vector with exactly \(h\) coordinates to be \(1\) and other entries to be \(0\). We can assume that \(x_{i_j}=1\) for \(j=1, \cdots, h\), where \(1\leq i_1< \cdots < i_h \leq q\). These indices \(\{ i_1,\cdots, i_h \}\) uniquely determine the elements \(\{ a_{i_1}, \cdots, a_{i_h} \}\) in \(\mathbb{F}_q\). By definition of the matrix \(H_q(k)\), one computes \[H_q(k)x = (h, \sum_{j=1}^h a_{i_j}, \sum_{j=1}^h a_{i_j}^{2}, \cdots, \sum_{j=1}^h a_{i_j}^{k-1})^T.\] The first coordinate on both sides is equal to \(h\). Thus, the syndrome equation \[H_q(k)x = u= \begin{pmatrix} h \\ h_1 \\ \vdots \\ h_{k-1} \end{pmatrix}\] becomes the following system of equations \[\sum_{j=1}^h a_{i_j} =h_1,\; \sum_{j=1}^h a_{i_j}^{2} =h_2, \cdots, \;\sum_{j=1}^h a_{i_j}^{k-1} = h_{k-1}.\]

Each vector \(x \in S_2(y, h)\) gives a solution \((w_{i_1}, \cdots, w_{i_h}) \in W^h\) in \(\mathcal{N}_h^*(q)\), where \[w_{i_j} = \begin{pmatrix} 1 \\ a_{i_j} \\ \vdots \\ a_{i_j}^{k-1}\end{pmatrix} \in W, \;\;1\leq j \leq h.\] Since \(i_1<\cdots <i_h\), this solution under permutation of \(\{i_1, \cdots, i_h\}\) gives \(h!\) solutions \((w_{1}, \cdots, w_{h})\) in \(\mathcal{N}_h^*(q)\). Different \(x \in S_2(y, h)\) will give different solutions in \(\mathcal{N}_h^*(q)\) as different \(x\) gives different subset \(\{ a_{i_1}, \cdots, a_{i_h}\}\) of \(\mathbb{F}_q\). Thus, each vector \(x \in S_2(y, h)\) contributes exactly \(h!\) in \(N_h^*(q)\). This gives

We need to prove a large lower bound for \(N_h^*(q)\). Clearly, \[N_h^*(q) \leq N_h(q).\] Thus, a weaker version is to first prove a large lower bound for \(N_h(q)\).

This affine variety \(X_{k,h, u}\) is defined by \(k-1\) equations in \(h\) variables. Since we will take \(h=\lfloor (1+\epsilon)k\rfloor\) to be significantly larger than \(k\), one can expect that the system has many \(\mathbb{F}_q\)-rational solutions for large \(q\), roughly \[q^{h-(k-1)} = q^{\lfloor \epsilon k -1\rfloor}\] \(\mathbb{F}_q\)-rational solutions, which is subexponential in \(q\) for \(k = \lfloor q^{\epsilon_1}\rfloor\).

By definition, one checks that \(N_h(q)\) is the same as the number of \(\mathbb{F}_q\)-rational points on \(X_{k,h, u}\). Similarly, \(N_h^*(q)\) is the same as the number of \(\mathbb{F}_q\)-rational points on \(X_{k,h, u}^*\). In summary, we have established the following relations:

These numbers have been studied in the literature using Weil’s bound for character sums, see [38] and [20]. But the results obtained in this way only give non-trivial information when \(\epsilon>1\). They are too weak to deduce any useful information for our purpose here, where we need \(0<\epsilon < 1\). We shall study these numbers using Deligne’s theorem on the Weil conjectures. For this purpose, one first needs to understand the geometry of the affine variety \(X_{k, h, u}\) and its compatification, which turns out to be quite nice. These varieties are complete intersections in affine and projective spaces, with few singularities. Thus, Deligne’s theorem can be applied. The more complicated variety \(X_{k,h, u}^*\) will be handled by inclusion-exclusion sieving and combinatorial arguments.

4 geometry of the variety \(X_{k, h, u}\)↩︎

The variety \(\overline{X}_{k,h, u}\) is just the projective closure of the affine variety \(X_{k,h, u}\) in \(\mathbb{P}^h\), and \(\overline{X}_{k,h}\) is the infinite part of \(X_{k,h, u}\). So, we have the relation \[X_{k,h, u} = \overline{X}_{k,h, u} \setminus \overline{X}_{k,h}.\] This reduces to estimating the number of \(\mathbb{F}_q\)-rational points on the two projective varieties \(\overline{X}_{k,h, u}\) and \(\overline{X}_{k,h}\): \[N_h(q) = |X_{k,h, u}(\mathbb{F}_q)| = |\overline{X}_{k,h, u}(\mathbb{F}_q)| - |\overline{X}_{k,h}(\mathbb{F}_q)|.\] To understand the last two terms, we need to understand the geometry of the two projective varieties \(\overline{X}_{k,h, u}\) and \(\overline{X}_{k,h}\).

Proof. Each time we cut a projective variety by a homogenous equation, the dimension drops at most by \(1\). Since \(\overline{X}_{k,h, u}\) is cut out by \((k-1)\) homogenous equations in \(\mathbb{P}^h\), we have the inequality \[\dim (\overline{X}_{k,h, u}) \geq h - (k-1) = h-k+1.\] By definition, the equality holds if and only if \(\overline{X}_{k,h, u}\) is a complete intersection. We need to prove the upper bound \[\dim (\overline{X}_{k,h, u}) \leq h-k+1.\] The same argument shows that we also have the inequalities \[\dim (\overline{X}_{h+1,h, u}) \geq\dim (\overline{X}_{h,h, u})-1 \geq \cdots \geq \dim (\overline{X}_{k,h, u}) -(h-k+1).\] It suffices to prove that the left side is zero, that is, the variety \(\overline{X}_{h+1,h, u}\) in \(\mathbb{P}^h\) defined by the system \[\sum_{i=1}^h x_i^j = h_jx_{h+1}^j, \;1\leq j \leq h\] is a zero-dimensional projective variety. But this is obvious, as Newton’s formula implies that for any point \((x_1, \cdots, x_{h+1})\) on \(\overline{X}_{h+1,h, u}\), the first \(h\) coordinates \((x_1, \cdots, x_h)\) are uniquely determined by the last coordinate \(x_{h+1}\) because \(h<q\) and we are working in fields of characteristic \(q\). Since we are working in projective space, this actually proves that \(\overline{X}_{k,h, u}\) has exactly one point, corresponding to the case \(x_{h+1}=1\). The case \(x_{h+1}=0\) implies all coordinates \(x_i=0\), giving no points in the projective space. The proof for the variety \(\overline{X}_{k,h}\) is the same. 0◻

For a variety \(X\), we let \({\rm Sing}(X)\) to denote the singular locus of \(X\). If \(X\) is smooth, then \({\rm Sing}(X)\) is empty and \(\dim {\rm Sing}(X)=-1\) by convention.

Proof. The inequality \[\dim {\rm Sing}(X\cap Z) \leq \dim {\rm Sing}(X) +1\] is called Zak’s lemma. A proof can be found in Katz’s appendix in [39]. The other inequality \[\dim {\rm Sing}(X) \leq \dim {\rm Sing}(X\cap Z) +1\] is the content of [40]. 0◻

Proof. For \(k=1\), \(\overline{X}_{1,h}=\mathbb{P}^{h-1}\) is trivially smooth. We assume that \(2\leq k\leq h\). Let \((x_1, \cdots, x_h)\) be a singular point on the projective variety \(\overline{X}_{k,h}\). This means that its \((k-1)\times h\) Jacobian matrix \[J: = \begin{pmatrix} 1 & 1 & \cdots & 1 \\ 2x_1 & 2x_2 & \cdots & 2x_h \\ \vdots & \vdots & \ddots & \vdots \\ (k-1)x_1^{k-2} & (k-1)x_2^{k-2} & \cdots & (k-1)x_h^{k-2} \end{pmatrix}\] has rank less than \(k-1\). Since \(k\leq h < q\), the Vandermonde determinant shows that the set \(\{x_1, \cdots, x_h\}\) contains at most \(k-2\) distinct elements, and at least one of them is non-zero since we are working in the projective space. Let \(\{ z_1, \cdots, z_e\}\) be the distinct non-zero elements in \(\{x_1, \cdots, x_h\}\) with positive multiplicities \(\{m_1, \cdots, m_e\}\). Then, \(1\leq m_1 +\cdots +m_e \leq h <q\) and \(e\leq k-2\). As \((x_1, \cdots, x_h)\) is a point on \(\overline{X}_{k,h}\), we have \[\sum_{i=1}^e m_iz_i^j = 0, \;\;1\leq j \leq k-1.\] Since the \(z_i\)’s are distinct and non-zero, applying the Vandermonde determinant to the first \(e\) equatons, we deduce that all the coefficients \(m_i\)’s are zero in \(\mathbb{F}_q\). This contradict with our assumption \(1\leq m_i\leq h <q\). It follows that the projective variety \(\overline{X}_{k,h}\) has no singular point.

Now, \(\overline{X}_{k,h}\) is the hyperplane section \(\{ x_{h+1}=0\}\) of \(\overline{X}_{k,h, u}\). They are complete intersections of dimension \(h-k\) and \(h-k+1\) respectively in \(\mathbb{P}^h\). By Lemma 25, \(\dim {\rm Sing} \overline{X}_{k,h, u}\) differs from \(\dim {\rm Sing} \overline{X}_{k,h}\) by at most \(1\). The latter dimension is \(-1\) (smooth), and thus the former dimension is at most \(0\). That is, \(\overline{X}_{k,h, u}\) has only finitely many isolated singular points. 0◻

5 Rational points on the variety \({X}_{k,h, u}\)↩︎

We need the following fundamental result on the number of \(\mathbb{F}_q\)-rational points on a singular complete intersection \(X\) defined over a finite field.

In the smooth case \(s=-1\), this result is a direct consequence of Deligne’s theorem [41] on the Weil conjecture. The general singular case can also be derived from Deligne’s theorem and properties of \(\ell\)-adic cohomology, as noted by Hooley and Katz [39]. If \(s \geq m-1\), the estimate is trivial. If \(s\leq m-2\) (the interesting case), \(X\) is non-singular in codimension \(1\), and hence a normal variety as \(X\) is a complete intersection. As \(m=\dim(X)\geq 1\), the variety \(X\) is connected, hence the normal variety \(X\) is geometrically irreducible.

The above constant \(C\) can be explicitly bounded in term of \(n\) and the multi-degrees of the defining equations for \(X\). We do not give the projective bound here. Instead, we will give and use the simpler affine bound later.

Now, we are ready to estimate the number \(N_h(q)\) of \(\mathbb{F}_q\)-rational points on \({X}_{k,h, u}\).

Proof. We give a self-contained proof using Proposition 27 as a blackbox and the total Betti number estimate in [37].

The variety \({X}_{k,h}\) is a smooth projective complete intersection of dimension \(h-k>0\) in \(\mathbb{P}^{h-1}\). Proposition 27 with \(s=-1\) yields the estimate \[\left| |\overline{X}_{k,h}(\mathbb{F}_q)| - \frac{q^{h-k+1}-1}{q-1}\right| \leq C_1q^{\frac{h-k}{2}},\] where the constant \(C_1\) is independent of \(q\).

The variety \(\overline{X}_{k,h, u}\) is a projective complete intersection of dimension \(h-k+1 \geq 2\) in \(\mathbb{P}^h\) with at most isolated singularity. Proposition 27 with \(s=0\) yields the estimate \[\left| |\overline{X}_{k,h, u}(\mathbb{F}_q)| - \frac{q^{h-k+2}-1}{q-1}\right| \leq C_2q^{\frac{h-k+2}{2}},\] where the constant \(C_2\) is independent of \(q\). These estimates are true over every finite finite extension \(\mathbb{F}_{q^e}\) of the finite field \(\mathbb{F}_q\), that is, the same estimates are true if we replace \(q\) by \(q^e\).

Since \(|{X}_{k,h, u}(\mathbb{F}_{q^e})| = |\overline{X}_{k,h, u}(\mathbb{F}_{q^e})| - |\overline{X}_{k,h}(\mathbb{F}_{q^e}) |\), we conclude that for all positive integer \(e\), \[\label{bound} \left| |{X}_{k,h, u}(\mathbb{F}_{q^e})|- q^{e(h-k+1)}\right| \leq (C_1+C_2)q^{\frac{e(h-k+2)}{2}}.\tag{1}\] Write the rational zeta function of \({X}_{k,h, u}\) over \(\mathbb{F}_q\) in reduced form \[Z({X}_{k,h, u}, T): = \exp(\sum_{e=1}^{\infty} \frac{|{X}_{k,h, u}(\mathbb{F}_{q^e})|}{e}T^e) =\frac{1}{(1-q^{h-k+1}T)}\frac{\prod_{i=1}^{d_1}(1-\alpha_iT)}{\prod_{j=1}^{d_2}(1-\beta_jT)}.\] Equivalently, for every positive integer \(e\), we have \[|{X}_{k,h, u}(\mathbb{F}_{q^e})|- q^{e(h-k+1)} = \sum_{j=1}^{d_2} \beta_j^e -\sum_{i=1}^{d_1} \alpha_i^e.\] The bound in (1 ) for all \(e\) implies that the following rational function \[\sum_{e=0}^{\infty} (\sum_{j=1}^{d_2} \beta_j^e -\sum_{i=1}^{d_1} \alpha_i^e)T^e = \sum_{j=1}^{d_1}\frac{1}{1-\beta_jT} -\sum_{i=1}^{d_1}\frac{1}{1-\alpha_iT}\] is analytic (no poles) in the open disk \(|T|< q^{\frac{-(h-k+2)}{2}}\). It follows that \[|\alpha_i| \leq q^{\frac{h-k+2}{2}}, \;\; |\beta_j| \leq q^{\frac{h-k+2}{2}}, \;1\leq i\leq d_1, \;1\leq j \leq d_2.\] This implies that for all positive integers \(e\), \[\left| |{X}_{k,h, u}(\mathbb{F}_{q^e})|- q^{e(h-k+1)} \right| \leq \sum_{j=1}^{d_2} |\beta_j|^e + \sum_{i=1}^{d_1} |\alpha_i|^e \leq (d_1+d_2)q^{\frac{e(h-k+2)}{2}},\] where \(d_1+d_2\) is bounded by the total degree \(d_1+d_2+1\) of \(Z({X}_{k,h}, T)\). Now, the affine variety \(X_{k,h,u}\) in \(\mathbb{A}^h\) is defined by the vanishing of \(k-1\) equations with degrees at most \(k-1\). Bombieri’s total degree bound [42] for an affine variety gives \[d_1 + d_2 +1 \leq (4(k-1)+9)^{h+k-1} = (4k+5)^{h+k-1}.\]

This total degree bound can be improved via cohomological methods. For a prime \(\ell \not = q\), let \(\mathbb{Q}_{\ell}\) denote the field of \(\ell\)-adic rational numbers. The \(\ell\)-adic cohomological trace formula says that \[Z({X}_{k, h, u}, T) = \prod_{i=0}^{2(h-k+1)} \det (I - \sigma_q T | H_c^i( {X}_{k, h, u} \otimes \bar{\mathbb{F}}_q, \mathbb{Q}_{\ell}))^{(-1)^{i-1}},\] where \(H_c^i( {X}_{k, h, u} \otimes \bar{\mathbb{F}}_q, \mathbb{Q}_{\ell})\) denotes the \(\ell\)-adic cohomology with compact support, which is a finite dimensional vector space over \(\mathbb{Q}_{\ell}\), and \(\sigma_q\) is the geometric Frobenius which induces an invertible linear map on the \(\mathbb{Q}_{\ell}\)-vector space \(H_c^i( {X}_{k, h, u} \otimes \bar{\mathbb{F}}_q, \mathbb{Q}_{\ell})\). From the trace formula, one deduces the inequality \[d_1 + d_2 + 1 \leq B_c({X}_{k, h, u}): = \sum_{i=0}^{2(h-k+1)} \dim_{\mathbb{Q}_{\ell}} H_c^i( {X}_{k, h, u} \otimes \bar{\mathbb{F}}_q, \mathbb{Q}_{\ell}).\] The number \(B_c({X}_{k, h, u})\) is called the total Betti number, whose conjectural independence on the choice of the auxiliary prime \(\ell\) is a major open problem in arithmetic geometry. In any case, a good upper bound for the total Betti number leads to a good upper bound for the total degree, but not vice versa, because of possible cancellation. For example, Katz’s estimate [43] for the total \(\ell\)-adic Betti number gives \[d_1+d_2+1 \leq B_c({X}_{k, h, u}) \leq 3(2+k-1)^{h+k-1} = 3(k+1)^{h+k-1}.\] Improved total Betti number bounds are studied systematically in [37]. Since \(X_{k,h,u}\) is an affine complete intersection in \(\mathbb{A}^h\), we can use the following proposition [37] which gives an asymptotically optimal total \(\ell\)-adic Betti number bound. This bound yields the estimate \[d_1+d_2+1 \leq B_c({X}_{k, h, u}) \leq {h-1\choose k-2} k^h < 2^{h-1}k^h = \frac{1}{2}(2k)^h.\] The proposition is proved. 0◻

6 Inclusion-exclusion sieving↩︎

To handle the number \(N_h^*(q)\) of solutions with distinct coordinates, namely, the number of \(\mathbb{F}_q\)-rational points on \({X}_{k,h, u}^*\), we need to remove those \(\mathbb{F}_q\)-rational points on \(X_{k,h, u}\) with two coordinates being the same. For this purpose, we introduce the following hyperplane section.

By symmetry, for any \(1\leq i < j \leq h\), we have \[|Y_{k,h, u}(\mathbb{F}_q)| = |X_{k,h, u} \cap \{x_1 = x_2\}(\mathbb{F}_q)|= |X_{k,h, u} \cap \{x_i = x_j\}(\mathbb{F}_q)|.\] Clearly, \[X_{k,h, u}^*(\mathbb{F}_q) = X_{k,h, u} (\mathbb{F}_q) \setminus \bigcup_{1\leq i< j \leq h}(X_{k,h, u} \cap \{x_i = x_j\}(\mathbb{F}_q)).\] Applying the inclusion-exclusion sieving as done in [44], we obtain the inequality \[\label{equation} N_h^*(q) =|X_{k,h, u}^*(\mathbb{F}_q)| \geq N_h(q) - {h \choose 2} |Y_{k,h, u}(\mathbb{F}_q)|.\tag{2}\] This is a crude sieving, but enough for our current purpose. Presumably, the full distinct coordinate sieving in [45] could be applied which would lead to a sharp asymptotic formula for \(N_h^*(q)\). We do not pursue this refinement here.

The number \(N_h(q)\) is already estimated in Proposition 28. The number \(|Y_{k,h, u}(\mathbb{F}_q)|\) can be estimated in the same way. We have

Proof. Note that \[Y_{k,h, u} = \overline{X}_{k,h, u} \cap \{x_1 = x_2\} \setminus \overline{X}_{k,h} \cap \{x_1 = x_2\}.\] The projective variety \(\overline{X}_{k,h, u} \cap \{x_1 = x_2\}\) in \(\mathbb{P}^{h-1}: =\mathbb{P}^h \cap \{x_1 = x_2\}\) is defined by \(k-1\) homogeneous equations. It follows that \[\dim(\overline{X}_{k,h, u} \cap \{x_1 = x_2\}) \geq h-1-(k-1) = h-k.\] By Proposition 24, its hyperplane section \[\overline{X}_{k,h, u} \cap \{x_1 = x_2\}\cap \{ x_2=0\} \cong \overline{X}_{k,h-2, u}\] is a complete intersection of dimension \(h-k-1\) in \(\mathbb{P}^{h-2}\). It follows that \[\dim(\overline{X}_{k,h, u} \cap \{x_1 = x_2\}) \leq (h-k-1)+1 = h-k.\] We deduce that \[\dim(\overline{X}_{k,h, u} \cap \{x_1 = x_2\}) = h-k.\] This proves that \(\overline{X}_{k,h, u} \cap \{x_1 = x_2\}\) is a projective complete intersection of dimension \(h-k\geq 2\) in \(\mathbb{P}^{h-1}\). By Proposition 26, the singular locus of \(\overline{X}_{k,h, u}\) has dimension bounded by \(0\). By Lemma 25, the singular locus of \(\overline{X}_{k,h, u} \cap \{x_1 = x_2\}\) has dimension bounded by \(1\). Similarly, \(\overline{X}_{k,h} \cap \{x_1 = x_2\}\) is a projective complete intersection of dimension \(h-k-1\geq 1\) in \(\mathbb{P}^{h-1}\) whose singular locus has dimension bounded by \(0\) (isolated singularities).

Proposition 27 with \(s=1\) yields the estimate \[\left| |(\overline{X}_{k,h, u}\cap \{x_1 = x_2\})(\mathbb{F}_q)| - \frac{q^{h-k+1}-1}{q-1}\right| \leq C_3q^{\frac{h-k+2}{2}},\] where the constant \(C_3\) is independent of \(q\). Similarly, Proposition 27 with \(s=0\) yields the estimate \[\left| |(\overline{X}_{k,h}\cap \{x_1 = x_2\})(\mathbb{F}_q)| - \frac{q^{h-k}-1}{q-1}\right| \leq C_4q^{\frac{h-k}{2}},\] where the constant \(C_4\) is independent of \(q\). The difference of these two asymptotic formulas gives the estimate \[\left| |Y_{k, h, u}(\mathbb{F}_q)| - q^{h-k}\right| \leq C_5q^{\frac{h-k+2}{2}},\] where \(C_5\) is the total degree of the zeta function of \(Y_{k, h, u}\). Since the affine variety \(Y_{k, h, u}\) in \(\mathbb{A}^{h-1}\) is a complete intersection defined by \(k-1\) equations of degrees at most \(k-1\), the total Betti number estimate in Proposition 29 yields the estimate \[C_5 \leq {h-2\choose k-2} k^{h-1} \leq 2^{h-2} k^{h-1} =\frac{1}{2}(2k)^{h-1}.\] The proposition is proved. 0◻

Now, we are ready to prove the following theorem on locally dense lattices in the weaker sense.

This theorem proves that the explicitly constructed lattice \(\mathcal{L}_{q,k}\) in \(\mathbb{R}^q\) with the explicit center \(y\) is the desired locally dense lattice we look for, except that we have not considered the linear projection yet. To finish the full proof, we need to show that the projection of \(S_2(y, h)\) to the first \(r\) coordinates is surjective onto \(\{ 0, 1\}^r\) for suitable choices of \(r\). This is completed in next section.

The above theorem already has an interesting application in coding theory. By Theorem 32 with \(p=1\) and [20], we obtain

Proof. Recall that \(\mathbb{F}_q =\{ a_1, \cdots, a_q\}\) with a fixed ordering. For every binary vector \(x=(x_1,\cdots, x_q)^T \in S_2(y, h)\), define the monic squarefree polynomial \[f_x(t) = \prod_{i=1}^q (t -a_i)^{x_i} \in \mathbb{F}_q[t],\] of degree \(h\) with \(h\) distinct roots in \(\mathbb{F}_q\). Since \(H_q(k)x = H_q(k)y\), the \(j\)-th power symmetric function of the roots of \(f_x(t)\) is equal to the \(j\)-th power symmetric function of the roots of \(f_y(t)\) for every \(1\leq j \leq k-1\). By Newton’s formula, the \(j\)-th elementary symmetric function of the roots of \(f_x(t)\) is equal to the \(j\)-th elementary symmetric function of the roots of \(f_y(t)\) for every \(1\leq j \leq k-1\). This means that the coeffcient of \(t^{h-j}\) in \(f_x(t)\) is equal to the coefficient of \(t^{h-j}\) in \(f_y(t)\) for every \(0\leq j \leq k-1\). It follows that \(f_y(t)-f_x(t) \in \mathbb{F}_q[t]\) is a polynomial of degree at most \(h-k< q\), which uniquely represents a codeword in the Reed-Solomon code \(RS_q(h-k+1)\) via the evaluation at the set \(\mathbb{F}_q\). Different \(x\) gives different \(f_x(t)\) and hence different codeword \(f_y(t)-f_x(t)\) in the Reed-Solomon code \(RS_q(h-k+1)\). The explicit center \({\boldsymbol{v}}\) is the word represented by \(f_y(t)\). It clearly agrees with the codeword \(f_y(t)-f_x(t)\) at all the \(h\) roots of \(f_x(t)\) for every \(x \in S_2(y, h)\). Thus, their Hamming distance is at most \(q-h\). By Theorem 32, we conclude that \[M_q({\boldsymbol{v}}, k, h) \geq |S_2(y, h)| >q^{\epsilon_1(1+\epsilon)k}.\]0◻

7 Linear Projections↩︎

In this final section, we assume that we are in the situation of Theorem 32. To finish the full de-randomization, we now consider the linear projection to the first \(r\)-coordinates: \[A: (x_1,\cdots, x_q)^T \in S_2(h, q) \longrightarrow (x_1, \cdots, x_r)^T \in \{0,1\}^r.\] Note that the map \(A\) is now restricted to the finite subset \(S_2(h, q)\) of \(\mathbb{Z}^q\). We need to show that this projection map is surjective for \[r= \lfloor q^{\delta} \rfloor < h -k =\lfloor \epsilon k\rfloor\] for some constant \(0< \delta< 1\) and all sufficiently large prime \(q\). Then, its image contains \(2^r = 2^{q^{\delta}}\) many elements, which is subexponential in \(q\). The proof of the surjection is similar to the proof of Theorem 32, but notationally and combinatorially somewhat more complicated. Here we give the details.

Fix \(x=(x_1, \cdots, x_r)^T \in \{0,1\}^r\). Let \(t\) be the Hamming weight of \(x\), that is, the number of non-zero entries in \(x\). Then, \(0\leq t\leq r\). The fibre \(A^{-1}(x_1,\cdots, x_r)^T\) in \(S_2(y, h)\) consists of all binary vectors \((x_1,. \cdots, x_r, x_{r+1}, \cdots, x_q)^T\) of Hamming weight \(h\) satisfying the following system of equations \[\sum_{i=1}^q a_i^jx_i = h_j, \;1\leq j \leq k-1.\] Since the first \(r\)-coordinates \((x_1, \cdots, x_r)\) are fixed, the fibre \(A^{-1}(x_1,\cdots, x_r)^T\) in \(S_2(y, h)\) can be identified with its last \((q-r)\)-coordinates, which consist of binary vector \((x_{r+1}, \cdots, x_q)^T\) of Hamming weight \(h-t\) satisfying the following system of equations \[\sum_{i=r+1}^q a_i^jx_i = h_j - \sum_{i=1}^r a_i^jx_i, \;1\leq j \leq k-1.\] Let the non-zero coordinates in \((x_{r+1}, \cdots, x_q)\) be \(x_{e_1}=\cdots =x_{e_{h-t}}=1\), where \[r+1\leq e_1<\cdots <e_{h-t}\leq q.\] Then, we have \[\sum_{i=1}^{h-t} a_{e_i}^j= h_j - \sum_{i=1}^r a_i^jx_i, \;1\leq j \leq k-1.\]

Recall that \(\mathbb{F}_q = \{a_1, \cdots, a_q\}\) with a fixed ordering. For any \(\mathbb{F}_q\)-rational point \((z_1, \cdots, z_{h-t})\) on \(Z_x^{**}\) with distinct coordinates, since \(z_i \not\in\{a_1, \cdots, a_r\}\), we can write uniquely \[z_1 = a_{e_1}, \cdots, z_{{h-t}} = a_{e_{h-t}},\] where \(\{ e_1, \cdots, e_{h-t}\}\) are distinct elements of \(\{ r+1, \cdots, q\}\). For \(r+1 \leq j \leq q\), define \(x_j=1\) if \(j= e_i\) for some \(i\), and \(x_j=0\) otherwise. Then, \[(x_1, \cdots, x_r, x_{r+1}, \cdots, x_q)^T \in S_2(y, q)\] with the projection property that \[A (x_1, \cdots, x_r, x_{r+1}, \cdots, x_q)^T = (x_1, \cdots, x_r)^T \in \{0, 1\}^r.\] Two \(\mathbb{F}_q\)-rational points \((z_1, \cdots, z_{h-t})\) and \((z'_1, \cdots, z'_{h-t})\) on \(Z_x^{**}\) give the same element in \(S_2(y, q)\) if and only if as a set, \[\{z_1, \cdots, z_{h-t}\} =\{z'_1, \cdots, z'_{h-t}\}.\] This is true if and only if \((z_1, \cdots, z_{h-t})\) and \((z'_1, \cdots, z'_{h-t})\) are permutations of each other. This proves

We need to show that the left side is positive. For this purpose, it is enough to show that the number \(|Z_x^{**}(\mathbb{F}_q)|\) of \(\mathbb{F}_q\)-rational points on the variety \(Z_x^{**}\) is positive. Just as in Theorem 32, we shall show that the number \(|Z_x^{**}(\mathbb{F}_q)|\) is at least subexponential in \(q\) with suitable choices of parameters.

For \(1\leq i\leq h-t\) and \(1\leq e\leq r\), let \[Z_{x, i, e}^*: = Z_x^* \cap \{ x_i = a_e\}, \;Z_{x, i, e}: = Z_x \cap \{ x_i = a_e\}.\] By inclusion-exclusion sieving, we have \[\label{ineq42} |Z_x^{**}(\mathbb{F}_q)| \geq |Z_x^*(\mathbb{F}_q)| - \sum_{1\leq i\leq h-t, 1\leq e\leq r}|Z_{x, i, e}^*(\mathbb{F}_q)|.\tag{5}\] The variety \(Z_x^*\) is just some \(X_{k, h-t, u}^*\) in the affine space \(\mathbb{A}^{h-t}\) defined before with \(\dim(Z_x^*) = h-t-k+1\). Similarly, the variety \(Z_{x, i, e}^*\) is just some \(X_{k, h-1-t, u}^*\) in the affine space \(\mathbb{A}^{h-1-t}\) with \(\dim(Z_{x, i, e}^*) = h-t-k\), and the variety \(Z_{x, i, e}\) is just some \(X_{k, h-1-t, u}\) in the affine space \(\mathbb{A}^{h-1-t}\) with \(\dim(Z_{x, i, e}) = h-t-k\).

By our choice of \(r\) with \(r < h-k\), we have \(k < h -r \leq h-t < q-2\). We can apply inequality (3 ) and Proposition 28 to deduce \[|Z_x^*(\mathbb{F}_q)|> q^{h-t-k}(q -{h-t\choose 2}) - {h-t\choose 2}(2k)^{h-t} q^{\frac{h-t-k+2}{2}},\] \[|Z_{x, i, e}^*(\mathbb{F}_q)| \leq |Z_{x, i, e}(\mathbb{F}_q)| \leq q^{{h-t-k}} + (2k)^{h-1-t}q^{\frac{h-t-k+1}{2}}.\] These and inequality (5 ) together imply that \[|Z_x^{**}(\mathbb{F}_q)| \geq q^{h-t-k}(q -{h\choose 2}-rh) - ({h\choose 2}+rh)(2k)^{h-t}q^{\frac{h-t-k+2}{2}}.\] Now, take \[\label{eq3} h =\lfloor (1+\epsilon)k \rfloor < \frac{1}{2}\sqrt{q}, \;\;r < h-k \leq (h-2)/2.\tag{6}\] The last inequality holds for large \(q\) because \(\epsilon < (1+\epsilon)/2\) for \(0< \epsilon < 1\). This implies that \[q > 4h^2 > 4{h\choose 2} \geq 2\left({h\choose 2} +rh\right).\] We deduce that \[\begin{align} |Z_x^{**}(\mathbb{F}_q)| &\geq ({h\choose 2}+rh)\left( q^{h-t-k}- (2k)^{h-t}q^{\frac{h-t-k+2}{2}}\right)& \\ &= ({h\choose 2}+rh)q^{\frac{\lfloor \epsilon k\rfloor-t+2}{2}} \left( q^{\frac{\lfloor \epsilon k\rfloor-t-2}{2}}- (2k)^{\lfloor(1+\epsilon)k\rfloor-t}\right).& \end{align}\] Take \[2k = \lfloor q^{\epsilon_1}\rfloor, \;\;0< \epsilon_1 < \frac{\epsilon}{2(1+\epsilon)} < \frac{1}{4},\] and \[\label{eq4} r =\lfloor q^{\delta} \rfloor < \min\left(2 \left( \frac{\epsilon}{2} -\epsilon_1(1+\epsilon)\right)k -5, \frac{\epsilon_1(1+\epsilon)}{4}k -1\right) .\tag{7}\] In particular, the rightmost number shows that \[r < \frac{\epsilon_1(1+\epsilon)}{4}k -1 < \frac{\epsilon}{8} k < \lfloor \epsilon k \rfloor = h-k.\] Such a choice of \(r\) with \(0< \delta<\epsilon_1\) is clearly possible for large \(q\). Recall that \(0\leq t\leq r\), we deduce \[\frac{\lfloor \epsilon k \rfloor-t-2}{2} -\epsilon_1 (\lfloor(1+\epsilon)k\rfloor -t) \geq \left( \frac{\epsilon}{2} -\epsilon_1(1+\epsilon)\right)k-\frac{r+3}{2} \geq 1.\] It follows that for large \(q\), \[\begin{align} \frac{1}{2}q^{\frac{\lfloor \epsilon k\rfloor -t-2}{2}} -(2k)^{\lfloor (1+\epsilon)k\rfloor-t} & \geq q^{\epsilon_1 (\lfloor (1+\epsilon)k\rfloor -t)}( \frac{1}{2}q^{\frac{\lfloor \epsilon k \rfloor -t-2}{2} -\epsilon_1 (\lfloor (1+\epsilon)k\rfloor-t)} -1)& \\ &\geq q^{\epsilon_1 (\lfloor (1+\epsilon)k\rfloor-r)} (\frac{1}{2}q -1)\geq q^{\epsilon_1 (\lfloor(1+\epsilon)k\rfloor-\lfloor \epsilon k\rfloor)} \geq 1.& \end{align}\] Thus, for large \(q\), \[|Z_x^{**}(\mathbb{F}_q)| \geq q^{\frac{\lfloor \epsilon k \rfloor-t+2}{2}}({h\choose 2}+rh)\frac{1}{2}q^{\frac{\lfloor \epsilon k\rfloor-t-2}{2}} \geq q^{\lfloor \epsilon k\rfloor -t} \geq q^{\epsilon k -r-1}.\] Since \(h-t \leq h \leq 2k\), \(2k \leq q^{\epsilon_1}\) and \(r < \frac{\epsilon_1(1+\epsilon)}{4}k -1\), we conclude that for large \(q\), \[\begin{align} |A^{-1}(x_1,\cdots, x_r)^T| &\geq \frac{1}{(h-t)!} |Z_x^{**}(\mathbb{F}_q)| \geq \frac{q^{\epsilon k -r-1}}{(2k)^h} & \\ &\geq q^{\epsilon k -r-1-\epsilon_1 h}\geq q^{(\epsilon -\epsilon_1(1+\epsilon))k -r-1}& \\ & \geq q^{\epsilon_1(1+\epsilon)k-r-1} \geq q^{\epsilon_1(1+\epsilon)k-\frac{\epsilon_1(1+\epsilon)}{4}k} &\\ &= q^{\frac{3}{4}\epsilon_1(1+\epsilon)k}. \end{align}\] This is subexponential in \(q\), as \(q\) is a polynomial in \(k\). In particular, the projection map \(A: S_2(h, q) \longrightarrow \{ 0, 1\}^r\) is surjective with the above choices of \(h = \lfloor(1+\epsilon)k\rfloor\), \(r = \lfloor q^{\delta}\rfloor\) and \(2k = \lfloor q^{\epsilon_1}\rfloor\) as in equations (6 ) and (7 ).

In summary, we have proved the following theorem on locally dense lattices.

The above locally dense lattice \(\mathcal{L}_{q,k}\) in \(\mathbb{R}^q\) is constructed deterministically in \({\rm poly}(q)={\rm poly}(r)\) time. Since \(\alpha = (\frac{1+\epsilon}{2})^{1/p}\) and we can take \(\epsilon\) to be arbitrarily close to zero, by Theorem 11, we deduce

References↩︎