Proof. If for some \(j \in \{1, \ldots, m-1\}\), we have \[\label{eq:coro-keneser-2} |(S_1 + \cdots + S_j) \bmod \Gamma| + |S_{j+1} \bmod \Gamma| \geq |(S_1 + \cdots + S_{j+1}) \bmod \Gamma| + 2,\tag{1}\] then by Theorem 6, \(\mathrm{Sym}_{\Gamma}(S_1 + \cdots + S_{j+1})\) contains a non-zero vector \(\vb*{h}\), so does \(\mathrm{Sym}_{\Gamma}(S_1 + \cdots + S_{m})\) since \(\vb*{h}\) also belongs to it.

Suppose that 1 does not hold for any \(j\). Then, by summing the reverse inequality of 1 over all \(j \in \{1, \ldots, m-1\}\), we have \[|(S_1 + \cdots + S_{m}) \bmod \Gamma| \geq \sum_{i=1}^m|S_i \bmod \Gamma| - (m-1).\] But this contradicts the condition stated in the lemma. ◻

Proof. We first prove (i). Since \(P\) is symmetric about the origin, we have that for any \(\vb*{p} \in P\) and any \(\vb*{v} \in \mathbb{R}^d\), \(|\vb*{p} \cdot \vb*{v}| \leq f_P(\vb*{v}).\) Now consider \(\vb*{p} + \vb*{p}'\). For any \(\vb*{v} \in \mathbb{R}^d\), we have \[(\vb*{p} + \vb*{p}')\cdot \vb*{v} \leq |\vb*{p} \cdot \vb*{v}| + |\vb*{p}' \cdot \vb*{v}| \leq (\varepsilon + \varepsilon')f_P(\vb*{v}).\] By Lemma 2, we have \(\vb*{p} + \vb*{p}' \in (\varepsilon + \varepsilon')P\). Similarly, we can show \(\vb*{p} - \vb*{p}' \in (\varepsilon + \varepsilon')P\).

(ii) follows straightforwardly by (i).

We prove (iii). Fix an arbitrary \(\vb*{v} \in \mathbb{R}^d\). Since \(Q + \varepsilon P \supseteq P\), by Lemma 2, we have \[f_Q(\vb*{v}) + \varepsilon f_P(\vb*{v}) \geq f_P(\vb*{v}),\] or in equivalent form, \[(1 - \varepsilon)f_P(\vb*{v}) \leq f_Q(\vb*{v}).\] Again by Lemma 2, we have \((1 - \varepsilon)P \subseteq Q\). ◻

Proof. We shall iteratively generate \(\vb*{b}_j\) for \(j = 1, \ldots, d\) using Lemma [lem:hd-es-petals]. Initially, \(j := 1\) and \(\vb*{o}_1 := \vb*{e}_1\) and \(R_1 := A\). Basically, \(\vb*{o}_j\) is a unit length vector that is orthogonal to \(\vb*{b}_1, \ldots, \vb*{b}_{j-1}\), and \(R_j\) is a subset of elements in \(A\) that can be used to generate \(\vb*{b}_j\). In iteration \(j\), we select \(\lfloor \frac{\delta\tau}{2d}\rfloor\) vectors from \(R_j\) that have the longest projection onto \(\vb*{o}_j\), and denote them by \(R^*_j\). (Recall that \(\delta\tau \geq 2d\) and that \(N\) is sufficiently large.) At least half of the vectors in \(R^*_j\) have the same direction when projected onto \(\vb*{o}_j\), and applying Lemma [lem:hd-es-petals] to them yields at least \[m \geq \frac{\delta\tau}{4d} \cdot \frac{1}{(d\log N)^{3d}} \geq \frac{\delta\tau}{(d\log N)^{4d}}\] non-empty disjoint subsets \(A_{j,1}, \ldots, A_{j, m}\) of cardinality at most \((d\log N)^{2d}\) and \(\sigma(A_{j,1}) = \ldots = \sigma(A_{j, m})\). Let \(\vb*{b}_j := \sigma(A_{j,1})\). If \(j = d\), then we stop. Otherwise, let \(\vb*{o}_{j+1}\) be a unit-length vector that is orthogonal to \(\vb*{b}_1, \ldots, \vb*{b}_{j}\), let \(R_{j+1} := R_j \setminus R^*_j\), and then proceed with the next iteration.

We first show that \(\vb*{b}_1, \ldots, \vb*{b}_d\) are linearly independent. Consider an arbitrary iteration \(j\). Since we remove at most \(\frac{\delta\tau}{2d}\) elements of \(A\) in each iteration, we have \(|R_j| \geq |A| - \frac{\delta\tau}{2}\). Recall that \(A\) is \(\delta\)-nondegenerate. \(A\) must have at least \(\delta\tau\) elements that are not orthogonal to \(\vb*{o}_j\), and therefore, \(R_j\) has at least \(\delta\tau/2\) elements that are not orthogonal to \(\vb*{o}_j\). By the construction of \(R^*_j\), all vectors in \(R^*_j\) must have non-zero projection onto \(\vb*{o}_j\). This implies that the projection of vectors in \(A_{j,1}\) onto \(\vb*{o}_j\) is either all positive or all negative. Therefore, \(\vb*{b}_j \cdot \vb*{o}_j \neq 0\). On the other hand, we have that \(\vb*{o}_j \cdot \vb*{b}_{j'} = 0\) for \(j' \in \{1, \ldots, j-1\}\). It follows that \(\vb*{b}_j\) cannot be a linear combination of \(\vb*{b}_1, \ldots, \vb*{b}_{j-1}\). This holds for all \(j \in \{1, \ldots, d\}\), so \(\vb*{b}_1, \ldots, \vb*{b}_d\) are linearly independent.

Property (i) follows straightforwardly. Next we prove property (ii). Let \(R_{d+1} := R_d/R^*_d\). Since \(|R^*_j| \leq \frac{\delta\tau}{2d}\) for all \(j\), we have \(|R_{d+1}| \geq n - \frac{\delta\tau}{2}\). To prove property (ii), it suffices to show that \[\label{eq:hd-ap-3} R_{d+1} \subseteq \{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d: |x_j| \leq 2^{d-1}\}.\tag{2}\] For \(j \in \{1, \ldots, d\}\), let \(n_j = |A_{j,1}|\). That is, \(\vb*{b}_j\) is the sum of \(n_j\) vectors in \(A\).

Now we are ready to prove 2 . Let \(\vb*{a}\) be an arbitrary vector in \(R_{d+1}\). Since \(\vb*{b}_1, \ldots, \vb*{b}_d\) are linearly independent, \(\vb*{a}\) can be represented as a linear combination of them. That is, for some \(x_1, \ldots, x_d\), \[\vb*{a} = x_1\vb*{b}_1 + \cdots + x_d \vb*{b}_d.\] We shall show that \(|x_j| \leq \frac{2^{(d-j)}}{n_j}\) for all \(j \in \{1, \ldots, d\}\), which immediately implies 2 . When \(j = d\), the inequality holds since \[\frac{1}{n_d} \cdot |\vb*{b}_d \cdot \vb*{o}_d| \geq |\vb*{a} \cdot \vb*{o}_d| = |x_d| |\vb*{b}_d \cdot \vb*{o}_d|.\] The first inequality is due to Claim 7 and the second is due to our choice of \(\vb*{o}_j\). Now suppose that the inequality holds for \(x_{j+1}, \ldots , x_d\). We show it also holds for \(x_j\). Consider \(\vb*{a} \cdot \vb*{o}_{j}\). By the choice of \(\vb*{o}_j\), we have \[\label{eq:hd-ap-4} \vb*{a} \cdot \vb*{o}_{j} = x_j \vb*{b}_j \cdot \vb*{o}_j + x_{j+1} \vb*{b}_{j+1} \cdot \vb*{o}_j + \cdots + x_d\vb*{b}_d \cdot \vb*{o}_j\tag{3}\] For \(j' > j\), we have \(\vb*{b}_{j'}\) is the sum of \(n_{j'}\) vectors in \(R^*_{j'} \subsetneq R_{j'} \subsetneq R_{j+1}\). By Claim 7, \[|\vb*{b}_{j'} \cdot \vb*{o}_j| \leq \frac{n_{j'}}{n_j} \cdot |\vb*{b}_j \cdot \vb*{o}_j|.\] By the inductive hypothesis, \[|x_{j'} \vb*{b}_{j'} \cdot \vb*{o}_j| \leq \frac{2^{(d-{j'})}}{n_{j'}} \cdot \frac{n_{j'}}{n_j} \cdot |\vb*{b}_j \cdot \vb*{o}_j| = \frac{2^{(d-{j'})}}{n_j}\cdot |\vb*{b}_j \cdot \vb*{o}_j|.\] In view of 3 , we have \[\label{eq:hd-ap-5} |\vb*{a} \cdot \vb*{o}_{j}| \geq \left(|x_j| - \frac{2^{d - j} - 1}{n_j}\right) \cdot |\vb*{b}_j \cdot \vb*{o}_j|\tag{4}\] Since \(\vb*{a} \in R_{d+1} \subseteq R_{j+1}\), Claim 7 implies that \(|\vb*{a} \cdot \vb*{o}_{j}| \leq \frac{1}{n_j} \cdot |\vb*{b}_j \cdot \vb*{o}_j|\). In view of 4 , we have \[|x_j| \leq \frac{2^{d-j}}{n_j}.\]

It remains to prove property (iii). By property (i), we have \(\vb*{b}_j \in [(d\log N)^{2d}N]^d\) for all \(j\), which implies \[\frac{\mathrm{det}(\Gamma)}{\mathrm{det}(Z)} \leq \frac{(d(d\log N)^{2d}N)^d}{\mathrm{det}(Z)} \leq (d\log N)^{3d^2}\tau^2.\] Let \[A' = A \cap \{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d: |x_j| \leq 2^{d-1}\}.\] Property (ii) implies that \[\mu: = \mu(A', \Gamma) \leq (2^d + 1)^d.\] Then we have \[\frac{\mathrm{det}(\Gamma)}{\mathrm{det}(Z)} \geq |A' \bmod \Gamma| \geq \frac{|A'|}{\mu} \geq \frac{n - \delta\tau/2}{(2^d + 1)^d} = \frac{n}{2(2^d + 1)^d} \geq \frac{n}{2^{3d^2}}. \qedhere\] ◻

Proof. Let \(P := \{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d: |x_j| \leq 1\}\). We have \[\mathrm{vol}(P) = 2^d\mathrm{det}(\Gamma).\] Note that \(P\) is a parallelepiped, and its facets are defined by the following formula. For each \(k\in[d]\), \[\begin{align} F^+_k &:= \{\text{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d : x_k = 1 and |x_{j}| \leq 1 for j \neq k}\},\\ F^-_k &:= \{\text{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d : x_k = -1 and |x_{j}|\leq 1 for j \neq k}\}. \end{align}\] Note that \(F^+_k\) and \(F^-_k\) are parallel, and have \((d-1)\)-dimensional volume at most \((2\sqrt{d}N)^{d-1}\) (since \(\|\vb*{b}_i\|_2 \leq \sqrt{d}N\) for all \(i\)). Let \(h_k\) be the distance between them. We have \[h_k \ge \frac{\mathrm{vol}(P)}{(2\sqrt{d}N)^{d-1}} = \frac{2\mathrm{det}(\Gamma)}{d^{(d-1)/2}N^{d-1}} \geq 2\sqrt{d} \cdot \frac{\mathrm{det}(\Gamma)}{d^{d}N^{d-1}}.\] Therefore, \(P\) contains a ball centered at the origin of radius at least \(\sqrt{d} \cdot \frac{\mathrm{det}(\Gamma)}{d^{d}N^{d-1}}\), which implies \[\left\{x_1\vb*{e}_1 + \cdots + x_d\vb*{e}_d : |x_j| \leq \frac{\mathrm{det}(\Gamma)}{d^{d}N^{d-1}}\right\}\subseteq P. \qedhere\] ◻

Proof. Let \(\vb*{b}_1, \ldots, \vb*{b}_d\) be given as in Lemma 4. By Lemma 4(i), we have that \[\mathcal{S}(A) \supseteq \{z_1\vb*{b}_1 + \cdots + z_d \vb*{b}_d: |z_j| \leq m, z_j \in \mathbb{Z}\} \quad\text{and}\quad m \geq \frac{\delta\tau}{(d\log N)^{4d}}.\] Since \(\mathcal{S}(A) \subseteq 2\mathcal{P}(A)\), we have \[\label{eq:large-inradius} \mathcal{P}(A) \supseteq \{x_1\vb*{b}_1 + \cdots + x_d \vb*{b}_d: |x_j| \leq \frac{\delta\tau}{2(d\log N)^{4d}}\}.\tag{5}\] By Lemma 4(i), \(\vb*{b}_j \in [(d\log N)^{2d}N]^d\) for all \(j\) . By Lemma 5, we have \[\mathcal{P}(A) \supseteq \{x_1\vb*{e}_1 + \cdots + x_d \vb*{e}_d: |x_j| \leq L\},\] where \[\begin{align} L &\geq \frac{\delta\tau}{2(d\log N)^{4d}} \cdot \frac{\mathrm{det}(\Gamma)}{d^d (d\log N)^{2d^2} N^{d-1}}\\ &\geq \frac{\delta\tau}{2(d\log N)^{4d}} \cdot \frac{1}{d^d (d\log N)^{2d^2} N^{d-1}} \cdot \frac{\rho\tau\mathrm{det}(Z)}{2^{3d^2}}\\ &\geq \frac{\rho\delta N}{(d\log N)^{7d^2}}\cdot \frac{\tau^2 \mathrm{det}(Z)}{N^d}\\ & = \frac{\rho\delta N}{(d\log N)^{7d^2}}. \end{align}\] The second inequality is due to Lemma 4(iii). ◻

Proof. Let \(\tau: = \sqrt{N^d/\mathrm{det}(Z)}\). The hypercube \([N]^d\) can contain at most \(2^d\tau^2\) vectors from \(Z\). Therefore, \(\rho\tau \leq 2^d\tau^2,\) or equivalently, \[\label{eq:all-lattice-pts-rou-tau} \rho \leq 2^d\tau.\tag{7}\] Since \(\rho\delta \geq (d\log N)^{12d^2}\) and \(N\) is sufficiently large, we have \[\label{eq:all-lattice-pts-bound-gamma-tau} \delta\tau \geq \frac{\rho\delta}{2^d} \geq \frac{(d\log N)^{12d^2}}{2^d} \geq (d\log N)^{11d^2}.\tag{8}\] So Lemma 4 is applicable to \(A\). Let \(\vb*{b}_1, \ldots, \vb*{b}_d\) be the \(d\) linearly independent vectors given by Lemma 4. We have that \(\vb*{b}_j \in [(d\log N)^{2d}N]^d\) for all \(j\). Let \(\Gamma := \mathcal{L}(\vb*{b}_1, \ldots, \vb*{b}_d)\). Clearly, \(\Gamma \subseteq Z\) since each \(\vb*{b}_j\) is a subset sum of \(A\). Let \[\label{eq:all-lattice-pts-4} A' = A \cap \{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d: |x_j| \leq 2^{d-1}\}.\tag{9}\] Lemma 4(ii) guarantees that \[\label{eq:all-lattice-pts-bound-mu} |A'| \geq \frac{\rho\tau}{2}\quad\text{and}\quad \mu: = \mu(A', \Gamma) \leq (2^d + 1)^d.\tag{10}\] Let \(\ell := \mathrm{det}(\Gamma)/\mathrm{det}(Z)\). Lemma 4(iii) guarantees that \[\label{eq:all-lattice-pts-bound-ell} \frac{\rho\tau}{2^{3d^2}} \leq \ell \leq (d\log N)^{3d^2}\tau^2.\tag{11}\]

Let \(m\) be defined as in Lemma 4(i). We have \[\label{eq:all-lattice-pts-bound-m} m \geq \frac{\delta\tau}{(d\log N)^{4d}} \geq \frac{\tau}{\rho}(d\log N)^{9d^2} \geq 4.\tag{13}\] The second inequality is due to ?? and the last is due to 7 . Lemma 4(i) also gives \(md\) disjoint subsets \(\{A_{j,k} : 1 \leq j \leq d, 1\leq k \leq m\}\) of \(A\). Let \(G := \bigcup_{j,k} A_{j,k}\) be the union of these subsets.

Given Claim [clm:all-latt-pts-2], to prove the Theorem, it suffices to show that \[P := \{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d: 0\leq x_j \leq \frac{m}{4}\}\] contains a hypercube of length at least \(\frac{\rho\delta N}{(d\log N)^{7d^2}} + N\). This can be shown using exactly the same argument as that in Corollary 4. We omit the details. ◻

Proof. Let \(B = (\vb*{b}_1, \ldots, \vb*{b}_d)\) be the basis of \(Z\). Without loss of generality, we assume that \(\mathrm{det}(B) > 0\), since otherwise, we can pick an arbitrary column \(\vb*{b}_j\) and set \(\vb*{b}_j:= -\vb*{b}_j\). Let \(B^*\) be the adjugate matrix of \(B\), then \(B^*\) is also an integer matrix, and \(BB^*=\mathrm{det}(B) I\), where \(I\) is the identity matrix. Let \(\vb*{q}_j\) be the \(j\)-th column of \(B^*\), then we have \[B\vb*{q}_j =\mathrm{det}(B)\vb*{e}_j.\] Note that \(B\vb*{q}_j = q_{1j}\vb*{b}_1 + \cdots + q_{dj}\vb*{b}_d\). Therefore, \(\mathrm{det}(B)\vb*{e}_j \in Z\), which implies \(z_j\mathrm{det}(B)\vb*{e}_j \in P \cap Z\) for any integer \(z_j\) with \(0\leq z_j \leq N_j\). Since this holds for all \(j\), we have \[P \cap Z \supseteq \{z_1\mathrm{det}(Z)\vb*{e}_1 + \cdots + z_d\mathrm{det}(Z)\vb*{e}_d : 0 \leq z_1 \leq N_j\}. \qedhere\] ◻

Proof. Let \(\vb*{a}_1, \ldots, \vb*{a}_n\) be the vectors in \(A\). Take an arbitrary \(\vb*{t} \in \mathcal{P}(A) + \frac{\sigma(A)}{2}\). Consider the polytope \[K := \{(y_1, \ldots, y_n) : y_1\vb*{a}_1 + \cdots + y_n\vb*{a}_n = \vb*{t}, 0 \leq y_j \leq 1 \}.\] \(K\) has \(n\) variables and \(d + 2n\) constraints. Also \(K\) is non-empty since \(\vb*{t} \in \mathcal{P}(A) + \frac{\sigma(A)}{2}\). We take an arbitrary vertex \((y_1, \ldots, y_n)\) of \(K\). Classic integer programming theory implies that all but at most \(d\) variables of \((y_1, \ldots, y_n)\) must be integral [56]. Without loss of generality, assume that only variables \(y_1, \ldots, y_{d}\) may be non-integral. Let \[\vb*{t}' := y_{d+1} \vb*{a}_{d+1} + \cdots + y_{n}\vb*{a}_n.\] Since \(y_{d+1}, \ldots, y_{n} \in \{0,1\}\), we have \(\vb*{t}' \in \mathcal{S}(A)\). Note \(\vb*{t} - \vb*{t'} = y_1\vb*{a}_1 + \cdots + y_{d}\vb*{a}_{d}.\) It is easy to verify that \(\vb*{t} - \vb*{t}' \in \{x_1\vb*{e}_1 + \cdots + x_d\vb*{e}_d: 0 \leq x_i \leq dN\}.\) ◻

Proof. We first show that \[\label{eq:frac2int-2} \mathcal{S}(A) \supseteq Z \cap \left(\mathcal{P}(A\setminus A^*) + \vb*{v}_0 - \frac{\sigma(A^*)}{2} + \frac{\sigma(A)}{2}\right).\tag{15}\] Take an arbitrary \(\vb*{t}\) from the set on the right-hand side of 15 . We have \[\vb*{t} - \vb*{v}_0 \in \mathcal{P}(A\setminus A^*) - \frac{\sigma(A^*)}{2} + \frac{\sigma(A)}{2} = \mathcal{P}(A\setminus A^*) + \frac{\sigma(A \setminus A^*)}{2}.\] By Lemma 8, there exists \(\vb*{t}' \in \mathcal{S}(A\setminus A^*)\) such that \[\vb*{t} - \vb*{v}_0 - \vb*{t'}\in \{x_1\vb*{e}_1 + \cdots + x_d\vb*{e}_d: 0 \leq x_j \leq dN\},\] or in equivalent form, \[\vb*{t} - \vb*{t'} \in \vb*{v}_0 + \{x_1\vb*{e}_1 + \cdots + x_d\vb*{e}_d: 0 \leq x_j \leq dN\},\] Also note that \(\vb*{t} - \vb*{t'} \in Z\). In view of ?? , we have \(\vb*{t} - \vb*{t}' \in \mathcal{S}(A^*)\). Therefore, \(\vb*{t} \in \mathcal{S}(A)\).

In view of 15 , to prove the lemma, it suffices to show that \[\label{eq:frac2int-3} (1-4\varepsilon)\mathcal{P}(A) \subseteq \mathcal{P}(A\setminus A^*) + \vb*{v}_0 - \frac{\sigma(A^*)}{2}.\tag{16}\] Take an arbitrary \(\vb*{v} \in (1-4\varepsilon)\mathcal{P}(A)\). Note that \(\vb*{v}_0 \in \mathcal{S}(A^*) \subseteq 2\mathcal{P}(A^*) \subseteq 2\varepsilon \mathcal{P}(A)\) and that \(\frac{\sigma(A^*)}{2} \in \mathcal{P}(A^*) \subseteq \varepsilon \mathcal{P}(A)\). By Lemma 3(i), \[\label{eq:frac2int-4} \vb*{v} - \vb*{v}_0 + \frac{\sigma(A^*)}{2} \in (1 - \varepsilon)\mathcal{P}(A).\tag{17}\] Recall that \(\mathcal{P}(A^*) \subseteq \varepsilon\mathcal{P}(A)\). Also note that \(\mathcal{P}(A \setminus A^*) + \mathcal{P}(A^*) = \mathcal{P}(A)\). By Lemma 3(iii), \[(1 - \varepsilon)\mathcal{P}(A) \subseteq \mathcal{P}(A \setminus A^*).\] In view of 17 , \[\vb*{v} - \vb*{v}_0 + \frac{\sigma(A^*)}{2} \in \mathcal{P}(A \setminus A^*),\] or, in equivalent form, \[\vb*{v} \in \mathcal{P}(A \setminus A^*) + \vb*{v}_0 - \frac{\sigma(A^*)}{2}.\] Therefore, 16 holds. ◻

Proof. Let \(\tau : = \sqrt{N^d/\mathrm{det}(Z)}\). Using exactly the same argument as that in the proof of Lemma 6, one can show that Lemma 4 is applicable to \(A\). Let \(\vb*{b}_1, \ldots, \vb*{b}_d\) and \(\{A_{j,k}: 1\leq j \leq d, 1 \leq k \leq m\}\) be the linearly independent vectors and disjoint subsets of \(A\) returned by Lemma 4. We have \(|A_{j,k}| \leq (d\log N)^{2d}\) and \(m \geq \frac{\delta\tau}{(d\log N)^{4d}}\). Let \(\ell := \mathrm{det}(\Gamma)/\mathrm{det}(Z)\). Lemma 4(iii) guarantees that \[\label{eq:small-set-small-region-3} \frac{\rho\tau}{2^{3d^2}} \leq \ell \leq (d\log N)^{3d^2}\tau^2.\tag{18}\]

Let \(p = \frac{2(d\log N)^{13d^2}}{\rho\delta}\). We randomly sample the subsets \(\{A_{j,k}: 1\leq j \leq d, 1 \leq k \leq m\}\) with probability \(p\), and let \(G\) be the union of the sampled subsets.

Then using exactly the same argument (Claim 8 and 9) as that in Lemma 6, one can show that \(A\) contains a subset \(R\) of at most \(\frac{\tau}{8\rho}(d\log N)^{9d^2}\) vectors such that \(\mathcal{S}_{\Gamma}(R) = Z \bmod \Gamma\) and \[\label{eq:small-set-small-region-1} \mathcal{P}(R) \subseteq \{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d: |x_j| \leq \frac{\tau}{8\rho}(d\log N)^{9d^2}\},\tag{19}\] and \[\label{eq:small-set-small-region-2} \mathcal{S}(G \cup R) \supseteq Z \cap (\vb*{b}_0 + \{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d: 0\leq x_j \leq \frac{m'}{4}\}),\tag{20}\] where \(\vb*{b}_0 := \frac{m'}{4}(\vb*{b}_1 + \cdots + \vb*{b}_d)\).

We shall show that \(A^*:= G \cup R\) satisfies all the stated properties.

In view of 20 , we have \[\mathcal{S}(G \cup R) \supseteq Z \cap (\vb*{v}_0 + \{z_1\vb*{e}_1 + \cdots + z_d\vb*{e}_d : 0 \leq z_j \leq dN, z_j\in \mathbb{Z}\}),\] where \(\vb*{v}_0 \in Z\), since using exactly the same argument as that in Corollary 4, the polytope \(\{x_1\vb*{b}_1 + \cdots + x_d\vb*{b}_d: 0\leq x_j \leq \frac{m'}{4}\}\) contains a hypercube of length at least \(dN + N\). We omit the details.

It remains to bound \(\mathcal{P}(G \cup R)\) in terms of \(\mathcal{P}(A)\). It suffices to bound \(\mathcal{P}(R)\) and \(\mathcal{P}(G)\) separately.

We first show that \(\mathcal{P}(A)\) is large. Note that \(\mathcal{S}(A) \subseteq 2\mathcal{P}(A)\). Lemma 4(i) implies that \[\label{eq:small-set-small-region-4} \mathcal{P}(A) \supseteq \left\{x_1\vb*{b}_1 + \cdots + x_d \vb*{b}_d: |x_j| \leq \frac{\delta\tau}{2(d\log N)^{4d}}\right\}.\tag{21}\] By Corollary 4, we have \[\label{eq:small-set-small-region-5} \mathcal{P}(A) \supseteq \left\{x_1\vb*{e}_1 + \cdots + x_d \vb*{e}_d: |x_j| \leq \frac{\rho\delta N}{(d\log N)^{7d^2}}\right\}.\tag{22}\]

Now we can bound \(\mathcal{P}(R)\). In view of 19 and 21 , we have that \[\mathcal{P}(R) \subseteq \varepsilon_R\mathcal{P}(A),\] where \[\varepsilon_R \leq \frac{(d\log N)^{13d^2}}{4\rho\delta}.\]

Next we show that \(\mathcal{P}(G) \subseteq 2p \mathcal{P}(A)\), which will immediately imply that \[\mathcal{P}(G \cup R) \subseteq \mathcal{P}(G) + \mathcal{P}(R) \subseteq (\varepsilon_R + 2p) \mathcal{P}(A) \subseteq \frac{5(d\log N)^{13d^2}}{\rho\delta}.\] By Corollary 3, \(\mathcal{P}(G) \subseteq 2p \mathcal{P}(A)\) if and only if \(f_{P'}(\vb*{v}) \leq 2pf_{P}(\vb*{v})\), where \(P' := \mathcal{P}(G)\) and \(P := \mathcal{P}(A)\), for all facet normals \(\vb*{v}\) of \(\mathcal{P}(A)\). Below we show that this happens with error probability at most \(N^{-d}\). This will finish the proof, since the total error probability of the construction of \(G\) and \(R\) is at most \(2N^{-d} < 1\), which implies the existence of the target \(G\) and \(R\).

Fix an arbitrary vector \(\vb*{v} \in \mathbb{R}^d\) with \(\|\vb*{v}\|_2 = 1\). By definition, it is easy to observe that \(f_{P'}(\vb*{v}) = \frac{1}{2}\sum_{\vb*{a} \in A'}|\vb*{a} \cdot \vb*{v}|\). For each \(A_i\), let \(f_i(\vb*{v}) = \frac{1}{2}\sum_{\vb*{a} \in A_i}|\vb*{a} \cdot \vb*{v}|\). Then \(f_{P'}(\vb*{v})\) can be viewed as the sum of a set of reals that are sampled with probability \(p\) from \(\{f_1(\vb*{v}), \ldots, f_m(\vb*{v})\}\), and therefore, we have \[\begin{align} \mathbf{E}[f_{P'}(\vb*{v})] &= \sum_{i}p f_{i}(\vb*{v}) = \frac{p}{2}\sum_{i}\sum_{\vb*{a} \in A_{i}}|\vb*{a} \cdot \vb*{v}| \leq \frac{p}{2}\sum_{\vb*{a} \in A}|\vb*{a} \cdot \vb*{v}| = p\cdot f_P(\vb*{v})\\ \mathbf{Var}[f_{P'}(\vb*{v})] &= p(1-p)\sum_{i}f_{i}(\vb*{v})^2 \leq p \cdot \max_{i}f_{i}(\vb*{v}) \cdot \sum_{i}f_{i}(\vb*{v}) \leq p \cdot \max_{i}f_{i}(\vb*{v}) \cdot f_P(\vb*{v}). \end{align}\] Let \(\eta = p f_P(\vb*{v})\). By Bernstein’s inequality, we have \[\begin{align} \mathbf{Pr}[f_{P'}(\vb*{v}) \geq 2p \cdot f_P(\vb*{v})] \leq & \mathrm{exp}\left(-\frac{\eta^2}{2\mathbf{Var}[f_{P'}(\vb*{v})] + \frac{2}{3}\eta\max_{i} f_{i}(\vb*{v})}\right) \nonumber\\ \leq & \mathrm{exp}\left(- \min\left\{\frac{\eta^2}{4\mathbf{Var}[f_{P'}(\vb*{v})]}, \frac{\eta}{2\max_{i} f_{i}(\vb*{v})}\right\}\right)\\ \leq & \mathrm{exp}\left(- \min\left\{ \frac{\eta}{4\max_{i} f_{i}(\vb*{v})}, \frac{\eta}{2\max_{i} f_{i}(\vb*{v})}\right\}\right) \\ \leq& \mathrm{exp}\left(-\frac{pf_P(\vb*{v})}{4\max_{i} f_{i}(\vb*{v})}\right).\\ \end{align}\] In view of 22 , we have \[f_p(\vb*{v}) \geq \frac{\rho\delta N}{(d\log N)^{7d^2}}.\] Since \(|A_i| \leq (d\log N)^{2d}\) and \(\vb*{a} \in [N]^d\) for all \(\vb*{a} \in A_i\), we have \[f_i(\vb*{v}) \leq \frac{1}{2} \cdot (d\log N)^{2d} \cdot \sqrt{d}{N} \leq \frac{\sqrt{d}N}{2}(d\log N)^{2d}.\] Therefore, we have \[\begin{align} &\mathbf{Pr}[f_{P'}(\vb*{v}) \geq 2p \cdot f_P(\vb*{v})]\\ \leq &\exp(- \frac{2(d\log N)^{12d^2}}{\rho\delta} \cdot \frac{\rho\delta N}{(d\log N)^{7d^2}} \cdot \frac{2}{\sqrt{d}(d\log N)^{2d} N}) \leq N^{-2d^2}\\ \end{align}\] Note that \(\mathcal{P}(A)\) can have at most \(|A|^d \leq N^{d^2}\) facets, therefore, by union bound, we have \[\mathbf{Pr}[\text{f_{P'}(\vb*{v}) \geq 2p\cdot f_{P}(\vb*{v}) for some facet normal of \mathcal{P}(A)} ] \leq N^{-2d^2} \cdot N^{d^2} \leq N^{-d}. \qedhere\] ◻

Proof. Note that if some integers have a common divisor greater than \(1\), then they must have a prime common divisor. We first use Theorem 13 to compute the prime factorization of all integers in \(A\) in \(\widetilde{O}(n + \sqrt{N})\) time. Then for each prime \(p\), we can determine the number of integers in \(A\) that are divisible by \(p\). If some \(p\) divides at least \(k\) integers in \(A\), then we return \(p\). Otherwise, no \(k\) elements of \(A\) have a common divisor greater than \(1\). ◻

Proof. Since \(A \subseteq \Gamma\), the lattice generated by \(\vb*{a}_1, \ldots, \vb*{a}_d\) must be a sublattice of \(\Gamma\). Therefore, \(\mathrm{det}(\Gamma)\) divides \(\mathrm{det}(\vb*{a}_1, \ldots, \vb*{a}_d)\). ◻

Proof. When \(k = 1\), the lemma holds trivially since \(|A \setminus \Gamma| \geq 1\) for any proper sublattice \(\Gamma \subsetneq \mathcal{L}(A)\). Assume that \(k \geq 2\).

For \(j \in \{1, \ldots, d\}\), let \(A_j\) be the projection of \(A\) onto the \(j\)-dimensional space spanned by \(\vb*{e}_1, \ldots, \vb*{e}_j\). (Note that \(A_j\) can be a multiset.) Let \(Z_j := \mathcal{L}(A_j)\). Note that \(Z_j\) must be full-dimensional. Let \(k_j := k\cdot (d\log N)^{2(d-j)}\). We say that \(A_j\) is bad if \(|A_j \setminus \Gamma_j| \leq k_j\) for some proper sublattice \(\Gamma_j \subsetneq Z_j\), and good otherwise. We shall iteratively determine whether \(A_j\) is good or bad for \(j \in \{1, \ldots, d\}\). If some \(\Gamma_j\) certifies that \(A_j\) is bad, then by lifting \(\Gamma_j\) to \(d\)-dimension, we can obtain a proper sublattice \(\Gamma \subsetneq Z\) such that \[|A \setminus \Gamma| \leq k_j \leq k\cdot (d\log N)^{2d};\] Otherwise, we will have \(A_d\) is good. (Note that \(A_d = A\) and \(k_d = k\).) This implies \(|A \setminus \Gamma| \geq k\) for any \(\Gamma \subsetneq Z\).

Consider the base case where \(j = 1\). Note that \(A_1\) is a multiset of integers from \([N]\) and they are all multiples of \(\mathrm{det}(Z_1)\). Let \(A'_1\) be obtained by dividing each element of \(A_1\) by \(\mathrm{det}(Z_1)\). To determine whether \(A_1\) is bad or not, it suffices to check whether \(n - k_1\) integers in \(A'_1\) have a common divisor greater than \(1\), and find such a divisor if it exists. This can be done by Lemma 11 in \(\widetilde{O}(n + \sqrt{N})\) time.

If \(A_{j-1}\) is bad, then we are done. Suppose that \(A_{j-1}\) is good. We need to check whether \(A_j\) is bad or not. We shall show that if \(A_j\) is bad, then in \(\widetilde{O}((n + \sqrt{N}) \cdot \mathrm{poly}(j))\) time and with error probability at most \(\frac{1}{8}\), we can obtain a lattice \(\Gamma^*_j \subsetneq Z_j\) certifying that \(A_j\) is bad. By repeating the procedure for \(O(d\log N)\) times, we can reduce the error probability to \(N^{-\Omega(d)}\). The lemma follows straightforwardly by simply iterating over \(j \in \{1, \ldots, d\}\).

Suppose that \(A_j\) is bad. That is, \(|A_j \setminus \Gamma_j| \leq k_j\) for some \(\Gamma_j \subsetneq Z_j\). We sample the elements of \(A_j\) with probability \(\frac{1}{k_j}\), and let \(S\) be the set of sampled elements. Let \(S'\) be the projection of \(S\) onto the \((j-1)\)-dimensional space spanned by \(\vb*{e}_1, \ldots, \vb*{e}_{j-1}\).

One can verify that the total time cost of the construction is \(\widetilde{O}((n + \sqrt{N}) \cdot \mathrm{poly}(d))\). We briefly explain how to reduce it to \(\widetilde{O}((n + d^d\tau) \cdot \mathrm{poly}(d))\). Basically, using a linear map \(B^{-1}\), where \(B\) represents a Mahler’s basis of \(Z\), one can map \(A\) to a set \(A'\) of integer vectors in \([-N' ,N']^d\), where \[N' = d^{2d}\cdot \frac{N^d}{\mathrm{det}(Z)} = (d^d\tau)^2.\] Then we apply the above procedure to \(A'\). The Mahler’s basis \(B\) can be computed in \(O(d^3n\log N)\) time and applying the above procedure to \(A'\) takes time \[\widetilde{O}((n + \sqrt{N'})\cdot \mathrm{poly}(d)) = \widetilde{O}((n + d^d\tau)\cdot \mathrm{poly}(d)). \qedhere\] ◻

Proof. Let \(k := \gamma \cdot \sqrt{N^d/\mathrm{det}(Z)}\). We shall construct a sequence \(A_0 \supsetneq A_1 \supsetneq \cdots \supsetneq A_r\) until \(Z_r := \mathcal{L}(A_r)\) is not full-dimensional or \(|A_r \setminus \Gamma| \geq k\) for any \(\Gamma \subsetneq Z_r\). Initially, \(i := 0\) and \(A_0 := A\). Given \(A_i\), we can check whether \(Z_i := \mathcal{L}(A_i)\) is full-dimensional or not in \(\widetilde{O}(d^3n\log N)\) time via Lemma 1. If not, then we stop and set \(r := i\). Suppose that \(Z_i\) is full-dimensional. Then we invoke Lemma 12 on \(A_i\) and \(k\), which takes \(\widetilde{O}((n + d^d\cdot \tau)\cdot \mathrm{poly}(d))\) time. If it asserts that \(|A_i \setminus \Gamma| \geq k\) for any \(\Gamma \subsetneq Z_i\), then we stop and set \(r := i\). Otherwise, it returns a \(\Gamma_i \subsetneq Z\) such that \[|A_i \setminus \Gamma_i| \leq k\cdot (d\log N)^{2d}.\] We set \(A_{i+1} := A_i \cap \Gamma_i\), and then proceed with \(i := i+1\).

We first show that \(r \leq 1 + d\log (dN)\). Suppose not. Note that \(Z_{r-1}\) must be full-dimensional. Observing that \(Z_{i} \subsetneq Z_{i-1}\) for all \(i\), we have \[\mathrm{det}(Z_{r-1}) \geq 2^{r-1} \cdot \mathrm{det}(Z_0) > (dN)^{d}.\] But this is impossible since \(Z_{r-1} = \mathcal{L}(A_{r-1})\) and the vectors in \(A_{r-1}\) have \(\ell_2\)-norm at most \(\sqrt{d} N\).

Note that \(|A_{i}| - |A_{i+1}| \leq k\cdot (d\log N)^{2d}\). We have \[|A_r| \geq |A| - rk\cdot (d\log N)^{2d} \geq |A| - k\cdot (d\log N)^{4d}.\] \(Z_r\) must be full-dimensional since \(A\) is \(\delta\)-nondegenerate and \(\delta > 2(d\log N)^{4d}\cdot \gamma\). By the stopping condition, it must be that \(|A_r \setminus \Gamma| \geq k\) for any \(\Gamma \subsetneq Z_r\). Note that \[k = \gamma \cdot \sqrt{N^d/\mathrm{det}(Z)} = \gamma \sqrt{\frac{\mathrm{det}(Z_r)}{\mathrm{det}(Z)}} \cdot \sqrt{\frac{N^d}{\mathrm{det}(Z_r)}}.\] So \(A_r\) is \(\gamma\sqrt{\frac{\mathrm{det}(Z_r)}{\mathrm{det}(Z)}}\)-spread. Also \(A_r\) is \(\frac{\rho}{2}\sqrt{\frac{\mathrm{det}(Z_r)}{\mathrm{det}(Z)}}\)-dense and \(\frac{\delta}{2}\sqrt{\frac{\mathrm{det}(Z_r)}{\mathrm{det}(Z)}}\)-nondegenerate, since \(A_r\) loses at most \(\frac{\delta}{2} \cdot \sqrt{N^d/ \mathrm{det}{Z}}\) elements when comparing to \(A\).

It is easy to verify that the total running time is \(\widetilde{O}((n + d^d\tau)\cdot \mathrm{poly}(d))\) time and the total error probability is at most \(N^{-\Omega(d)}\). ◻

Proof. We shall derive a sequence of lattices \(\Gamma_0 \subsetneq \Gamma_1 \subsetneq \cdots \subsetneq \Gamma_r \subseteq Z\) as follows. Initially, \(i = 0\) and \(\Gamma_0 := Z^*\). Given \(\Gamma_i\), let \(\ell_i := \mathrm{det}(\Gamma_i)/\mathrm{det}(Z)\). If \(|A \setminus \Gamma_i| < \ell_i\), then we stop, let \(A_i := A \setminus \Gamma_i\), and let \(r := i\). Otherwise, \(A\) has at least \(\ell_i\) elements not in \(\Gamma_i\). Let them be \(\{\vb*{a}_1, \ldots, \vb*{a}_{\ell_i}\} =: A_i\). Note that \[|\{0, \vb*{a}_1\}| + \cdots + |\{0, \vb*{a}_{\ell_i}\}| \geq 2\ell_i.\] Also note that \(|\mathcal{S}_{\Gamma_i}(A_i)| \leq |Z \bmod \Gamma_i| \leq \mathrm{det}(\Gamma_i)/\mathrm{det}(Z) \leq \ell_i\). So by Corollary 2, there is a vector \(\vb*{h}_i \notin \Gamma_i\) such that \[\label{eq:fill-lattice} \vb*{h}_i + \mathcal{S}(A_i) \equiv \mathcal{S}(A_i) \pmod {\Gamma_i}.\tag{25}\] We set \(\Gamma_{i+1} := \Gamma_i + \mathcal{L}(\vb*{h}_i)\), and repeat the procedure with \(i := i+1\).

We first show that \(\Gamma_0 \subsetneq \Gamma_1 \subsetneq \cdots \subsetneq \Gamma_r \subseteq Z\). Since \(\vb*{h}_{i} \notin \Gamma_i\), by the construction of \(\Gamma_{i+1}\), it is easy to see that \(\Gamma_i \subsetneq \Gamma_{i+1}\). It remains to prove that \(\Gamma_i \subseteq Z\) for all \(i\). We prove this by induction on \(i\). The base case is trivial since \(\Gamma_0 = Z^* \subseteq Z\). Assume that \(\Gamma_i \subseteq Z\). We show that \(\Gamma_{i+1} \subseteq Z\). Since \(\vb*{0} \in \mathcal{S}(A_i)\), in view of 25 , \(\vb*{h}_i \in \mathcal{S}(A_i) + \Gamma_i\). Note that \(A_i \subseteq A \subseteq Z\), so \(\vb*{h}_i\in Z\), which implies \(\Gamma_{i+1} \subseteq Z\).

Since \(\mathrm{det}(\Gamma_i) \geq 2\mathrm{det}(\Gamma_{i-1})\) for all \(i \geq 1\), we have that \[r \leq \log \frac{\mathrm{det}(Z^*)}{\mathrm{det}(Z)} = \log \ell.\]

Let \(R := A_0 \cup \cdots \cup A_r\) and let \(\Gamma := \Gamma_r\). We show that \(R\) and \(\Gamma\) satisfy the stated property in the lemma. By construction, we have \(|A_i| \leq \mathrm{det}(\Gamma_i)/\mathrm{det}(Z)\). So \[|R| \leq (\mathrm{det}(\Gamma_0) + \cdots + \mathrm{det}(\Gamma_r))/\mathrm{det}(Z) \leq 2\mathrm{det}(Z^*)/\mathrm{det}(Z) = 2\ell.\] Also since \(A_r = A \setminus \Gamma_r\), we have \(A \setminus R \subseteq \Gamma_r\). Property (i) is satisfied.

It remains to show property (ii). We claim that \[\label{eq:reduce-1-key} \Gamma + \mathcal{S}(R) = \mathcal{S}(R) + Z^*.\tag{26}\] Suppose that the claim holds. Pick an arbitrary \(\vb*{t} \bmod \Gamma \in \mathcal{S}_{\Gamma}(A)\). Since \(G \subseteq \Gamma\), we have that \(\vb*{t} \bmod \Gamma \in \mathcal{S}_{\Gamma}(R)\). In other words, \(\vb*{t} \in \Gamma + \mathcal{S}(R)\). In view of 26 , we have \(\vb*{t} \in \mathcal{S}(R) + Z^*\), or equivalently, \(\vb*{t} \bmod Z^* \in \mathcal{S}_{Z^*}(R)\). So property (ii) holds.

Now we prove 26 . We shall prove, by induction on \(i\), that \(\Gamma_i + \mathcal{S}(R) = \mathcal{S}(R) + Z^*\) for all \(i = 0, \ldots, r\). The base case holds trivially, since \(\Gamma_0 = Z^*\). Suppose the equation holds for some \(i\). We show it also holds for \(i+1\). Recall that \(\Gamma_{i+1} = \Gamma_i + \mathcal{L}(\vb*{h}_i)\), where \(\vb*{h}_i\) satisfies \[\vb*{h}_i + \mathcal{S}(A_i) \equiv \mathcal{S}(A_i) \pmod {\Gamma_i},\] or in equivalent form, \[\vb*{h}_i + \Gamma_i + \mathcal{S}(A_i) = \mathcal{S}(A_i) + \Gamma_i.\] Therefore, \[\Gamma_{i+1} + \mathcal{S}(A_i) = \mathcal{S}(A_i) + \Gamma_i.\] Adding \(\mathcal{S}(R \setminus A_i)\) to both sides gives \[\Gamma_{i+1} + \mathcal{S}(R) = \mathcal{S}(R) + \Gamma_i.\] By the inductive hypothesis, we have \[\Gamma_{i+1} + \mathcal{S}(R) = \mathcal{S}(R) + Z^*.\]

We bound the time cost of the construction. There are at most \(\log \ell\) iterations. In the \(i\)-th iteration, we need to do the following.

• Select elements of \(A\) that do not belong to \(\Gamma_i\), which takes \(O(d^2n)\) time via Lemma [lem:compute-rem](i).

• Compute a non-zero \(\vb*{h}_i \in \mathrm{Sym}_{\Gamma}(\mathcal{S}(A_i))\), which takes \(\widetilde{O}((n + 2^d\ell) \cdot \mathrm{poly}(d))\) via Lemma [lem:faster-modular-ss].

• Compute \(\Gamma_{i+1} := \Gamma_i + \mathcal{L}(\vb*{h}_i)\) via Lemma [lem:compute-rem](iii), which takes \(O(d^2\log \ell')\) time. Note that \(\ell' = \mathrm{det}(\Gamma_i) \leq \ell \mathrm{det}(Z) \leq \ell N^d\).

Therefore, the total time cost is \(\widetilde{O}((n + 2^d\ell) \cdot \mathrm{poly}(d))\). ◻

Proof. We first apply Lemma 14 to \(A\) and \(Z^*\). It gives a lattice \(\Gamma\) with \(Z^* \subseteq \Gamma \subseteq Z\) and a partition \(R \cup G\) of \(A\) such that

1. \(|R| \leq 2\ell\) and \(G \subseteq \Gamma\)

2. for any \(\vb*{t}\) with \(\vb*{t} \bmod \Gamma \in \mathcal{S}_{\Gamma}(A)\), we have \(\vb*{t} \bmod Z^* \in \mathcal{S}_{Z^*}(R)\).

Note that \(\Gamma\) can be obtained in \(\widetilde{O}((n + 2^d \ell) \cdot \mathrm{poly}(d))\) time via Lemma 14. We shall show that \(\Gamma\) satisfies the stated property.

Let \(R^* := R \setminus A^*\) and \(G^* := G \setminus A^*\). Then \(A^* \cup R^* \cup G^*\) forms a partition of \(A\). Since \(A^* \subseteq Z^*\), it is easy to see that \(R^*\) and \(G^*\) also satisfy property (i) and (ii) of \(R\) and \(G\).

Let \(\varepsilon' := \frac{(d\log N)^{14d^2}}{\rho\delta}\).

Note that \(5\varepsilon' \leq \varepsilon\). Given Claim 19, to prove the theorem, it suffices to show that \[(1 - 5\varepsilon')\mathcal{P}(A) + \frac{\sigma(A)}{2} \subseteq (1 - 3\varepsilon')\mathcal{P}(A^* \cup G^*) + \frac{\sigma(A^* \cup G^*)}{2},\] or equivalently, \[\label{eq:struct-4-1} (1 - 5\varepsilon')\mathcal{P}(A) + \frac{\sigma(R^*)}{2} \subseteq (1 - 3\varepsilon')\mathcal{P}(A^* \cup G^*).\tag{30}\] Recall Claim 17. Since \(\frac{\sigma(R^*)}{2} \in \mathcal{P}(R^*) \subseteq \varepsilon' \mathcal{P}(A^*) \subseteq \varepsilon' \mathcal{P}(A)\), by Lemma 3(ii), we have \[(1 - 5\varepsilon')\mathcal{P}(A) + \frac{\sigma(R^*)}{2} \subseteq (1 - 4\varepsilon')\mathcal{P}(A).\] Note that \((1 - 4\varepsilon')\mathcal{P}(A) = (1 - 4\varepsilon')P(A^* \cup G^*) + (1 - 4\varepsilon')\mathcal{P}(R^*)\) and that \(\mathcal{P}(R^*) \subseteq \varepsilon \mathcal{P}(A^*)\subseteq \varepsilon \mathcal{P}(A^* \cup G)\). Again, by Lemma 3(ii), we have \[(1 - 4\varepsilon')\mathcal{P}(A) \subseteq (1 - 3\varepsilon')P(A^* \cup G^*).\] So Inequality 30 follows. ◻

Proof. Let \(Z := \mathcal{L}(A)\). Let \(\tau := \sqrt{N^d/\mathrm{det}(Z)}\). Since \(A\) is \(\rho\)-dense, we have that \(n \geq \rho\tau\).

Let \(\gamma : = (d\log N)^{4d^2}/\rho\). By Lemma 13, in \(\widetilde{O}((n + d^d \tau)\cdot \mathrm{poly}(d))\) time, with error probability at most \(N^{-\Omega(d)}\), we can obtain a subset \(A^*\) that is \(\frac{\rho}{2}\sqrt{\ell}\)-dense and \(\gamma \sqrt{\ell}\)-spread, and \(\frac{\delta}{2}\sqrt{\ell}\)-nondegenerate, where \(\ell :=\frac{\mathrm{det}(Z^*)}{\mathrm{det}(Z)}\) and \(Z^* := \mathcal{L}(A^*)\).

Then we apply Lemma 15 to obtain a lattice \(\Gamma\) such that for every \(\vb*{t} \in (1- \varepsilon)\mathcal{P}(A) + \frac{\sigma(A)}{2},\) \[\vb*{t} \in \mathcal{S}(A) \text{ if and only if } \vb*{t} \bmod \Gamma \in \mathcal{S}_{\Gamma}(A),\] where \[\varepsilon = \frac{4(d\log N)^{15d^2} \ell}{\rho\delta \ell} \leq \frac{(d\log N)^{16d^2}}{\rho\delta}.\] The time cost of Lemma 15 is \(O((n + 2^d \ell) \cdot \mathrm{poly}(d)).\) Note that \(|A^*| \geq |A|/2 \geq \sqrt{N^d/\mathrm{det}(Z)}\). Therefore, \[\mathrm{det}(Z^*) \leq \frac{2^d N^d}{|A^*|} \leq 2^d\sqrt{N^d\cdot \mathrm{det}(Z)},\] which implies \(\ell \leq 2^d n\). So the time cost of this step is \(\widetilde{O}(n\cdot 2^{2d}\cdot \mathrm{poly}(d))\).

Then to decide whether \(\vb*{t} \in \mathcal{S}(A)\), it suffices to decide whether \(\vb*{t} \bmod \Gamma \in \mathcal{S}_{\Gamma}(A)\), this can be done in \(\widetilde{O}((n + 2^d\ell') \cdot \mathrm{poly}(d))\) time via Lemma [lem:faster-modular-ss], where \(\ell' := \mathrm{det}(\Gamma)/\mathrm{det}(Z)\). Note that \(\mathrm{det}(\Gamma) \leq \mathrm{det}(Z^*)\) since \(Z^* \subseteq \Gamma\). So \(\ell' \leq \ell \leq 2^d n\). The running time of this step is bounded by \(\widetilde{O}(n\cdot d^{d}\cdot \mathrm{poly}(d))\). ◻

Proof. We prove the lemma by induction on \(d\). When \(d = 1\), the lemma holds by Theorem 24. Now assume that the lemma holds for all sets \(A \subseteq [N]^{d}\). We show that it also holds for all sets \(A \subseteq [N]^{d+1}\).

Let \(A\) be a multiset of vectors from \([N]^{d+1}\). We ignore the \((d+1)\)-th dimension, regard the vectors in \(A\) as \(d\)-dimensional vectors, and apply the inductive hypothesis. This gives at least \(|A|/(d\log N)^{3d}\) disjoint subsets \(A_1, \ldots, A_{g}\) of \(A\) such that \(\sigma(A_1), \ldots, \sigma(A_{g})\) have the same \(j\)-th coordinates for each \(j \in \{1, \ldots, d\}\) and that \(1 \leq |A_1| = \cdots = |A_g| \leq h\), where \(h := (d\log N)^{2d}\).

Let \(\vb*{b}_i = \sigma(A_i)\) for \(i \in \{1, \ldots, g\}\). Let \(B = \{\vb*{b}_1, \ldots, \vb*{b}_{g}\}\). Note that the vectors in \(B\) only differ in the \((d+1)\)-th coordinate, and their \((d+1)\)-th coordinates are in \([0, hN]\). Consider only the \((d+1)\)-th coordinate of \(B\) and apply Theorem 24. We can obtain at least \(\frac{|B|}{18(\log hN)^2}\) subsets \(B_1, \ldots, B_{g'}\) such that the \((d+1)\)-th coordinates of \(\sigma(B_1), \ldots, \sigma(B_{g'})\) are the same and that \(1 \leq |B_1| = \cdots = |B_{g'}| \leq h'\), where \(h' := \log(hN)\).

Since \(|B_1| = \cdots = |B_{g'}|\) and the vectors in \(B\) have the same \(j\)-th coordinate \(j \in \{1, \ldots, d\}\), we have that \(\sigma(B_1), \ldots, \sigma(B_{g'})\) also have the same \(j\)-th-coordinate for \(j \in \{1, \ldots, d\}\). Therefore, \[\sigma(B_1) = \cdots = \sigma(B_{g'}).\] It is easy to see that \(B_1, \ldots, B_{g'}\) corresponds to \(g'\) disjoint subsets of \(A\) which have the same sum and the same cardinality. Moreover, the cardinality of these subsets of \(A\) is at most \(hh'\). It remains to bound \(hh'\) and \(g'\). Since \(N\) is sufficiently large, we have \[\log(hN) = (2d\log d + 2d\log\log N + \log N) \leq (d\log N)^{1.1}.\] Then we have \[\begin{align} hh' &= h \log (hN) \leq (d\log N)^{2d} \cdot (d\log N)^{1.1} \leq ((d+1)\log N)^{2d+2}. \end{align}\] The last inequality is due to that \(N\) is sufficiently large. We also have that \[g' \geq \frac{g}{18(\log hN)^2} \geq \frac{|A|}{(d\log N)^{3d}}\cdot \frac{1}{18(d\log N)^{2.2}} \geq \frac{|A|}{((d+1)\log N)^{3d+3}}.\] This completes the inductive step. ◻

Proof. Since \(\vb*{h} + \mathcal{S}(A) \equiv \mathcal{S}(A) \pmod \Gamma\), we have \[\mathcal{L}(\vb*{h}) + \mathcal{S}(A) \equiv \mathcal{S}(A) \pmod \Gamma,\] or in equivalent form, \[\Gamma + \mathcal{L}(\vb*{h}) + \mathcal{S}(A) \equiv \mathcal{S}(A) \pmod \Gamma.\] Note that \(\Gamma + \mathcal{L}(\vb*{h}) = \Gamma'\) and that \(\Gamma' + \mathcal{S}_{\Gamma'}(A) = \Gamma' + \mathcal{S}(A)\). Therefore, \[\Gamma' + \mathcal{S}_{\Gamma'}(A) \equiv \mathcal{S}(A) \pmod \Gamma. \qedhere\] ◻

Proof. Note that \(\ell\) must be a positive integer since \(\Gamma \subseteq Z\) and \(\Gamma\) is full-dimensional. We prove by induction on \(\ell\). When \(\ell = 1\), we have that \(\Gamma = Z\), and the lemma holds trivially. Suppose that the lemma holds for all \(\ell\) with \(\ell \leq k\) for some \(k \geq 1\). We show that it also holds when \(\ell = k+1\).

Since \(\ell = k+1 > 1\), it must be that \(\Gamma \subsetneq Z\). Therefore, \(A\) contains at least \(\ell\) vectors not belonging to \(\Gamma\). Let \(R_1 = \{\vb*{a}_1, \ldots, \vb*{a}_{\ell}\}\) be a set of \(\ell\) such vectors. It is easy to see that \[|\{0, \vb*{a}_1\}| + \cdots + |\{0, \vb*{a}_{\ell}\}| = 2\ell \geq |\mathcal{S}_{\Gamma}(R_1)| + \ell.\] The last inequality is due to that \(|\mathcal{S}_{\Gamma}(R_1)| \leq |Z \bmod \Gamma| = \ell\). By Corollary 2, there is a vector \(\vb*{h} \notin \Gamma\) such that \[\label{eq:gen-rem-std-1} \vb*{h} + \mathcal{S}(R_1) \equiv \mathcal{S}(R_1) \pmod {\Gamma}.\tag{31}\]

Let \(\Gamma' := \Gamma + \mathcal{L}(\vb*{h})\) and \(\ell' := \mathrm{det}(\Gamma')/\mathrm{det}(Z)\). We show that the inductive hypothesis is applicable to \(\Gamma'\). Since \(\vb*{0} \in \mathcal{S}(R_1)\), Equation 31 implies that \(\vb*{h} \in \mathcal{S}(R_1) + \Gamma\). Since \(R_1 \subseteq Z\) and \(\Gamma \subseteq Z\), we have \(\vb*{h} \in Z\), and therefore, \(\Gamma' \subseteq Z\). Since \(\vb*{h} \notin \Gamma\), we have \(\Gamma \subsetneq \Gamma'\). So \(\ell' \leq \ell/2 \leq k\). Also, for any \(\Lambda\) with \(\Gamma' \subseteq \Lambda \subsetneq Z\), we have \(\Gamma \subseteq \Lambda\), and therefore, \[|A \setminus \Lambda| \geq \ell > \ell'.\] By the inductive hypothesis, \(A\) contains a subset \(R_2\) of at most \(2\ell' \leq \ell\) vectors such that \[\label{eq:gen-rem-std-2} \mathcal{S}_{\Gamma'}(R_2) = Z \bmod \Gamma'.\tag{32}\]

Let \(R = R_1 \cup R_2\). Clearly, \(|R| \leq |R_1| + |R_2| \leq 2\ell\). It remains to show that \(\mathcal{S}_{\Gamma}(R) = Z \bmod \Gamma\). Equation 31 implies that \(\vb*{h} + \mathcal{S}(R) \equiv \mathcal{S}(R) \pmod {\Gamma},\) and Equation 32 implies that \(\mathcal{S}_{\Gamma'}(R) = Z \bmod \Gamma'\). By Lemma 16, we have \(\mathcal{S}_{\Gamma}(R) = Z \bmod \Gamma\). ◻

Proof. By Lemma 18, \(A\) contains a subset \(A'\) of at most \(20 \log |A|\) vectors such that \(|\mathcal{S}(A')| > |A|\). To prove the lemma, it suffices to show that \[|\mathcal{S}_{\Gamma}(A')| \geq \frac{|\mathcal{S}(A')|}{20^{d}(\log |A|)^d}.\] Let \(k := \lfloor 20\log |A| \rfloor\). Since \(A' \subseteq A \subseteq \mathbb{Z}^d_\Gamma\) and \(|A'| \leq k\), we have that \(\mathcal{S}(A') \subseteq k\mathbb{Z}^d_{\Gamma}.\) Therefore, each congruent class (modulo \(\Gamma\)) of \(\mathcal{S}(A')\) contains at most \(k^d\) vectors from \(\mathcal{S}(A')\). This implies that \[|\mathcal{S}_{\Gamma}(A')| \geq \frac{|\mathcal{S}(A')|}{k^d} \geq \frac{|\mathcal{S}(A')|}{20^{d}(\log |A|)^d}. \qedhere\] ◻

Proof. We iteratively extract subsets \(A_1, \ldots, A_m\) from \(A\) as follows. Initially, \(m := 0\) and every vector in \(A\) is unmarked. If \(A\) contains fewer than \(|A|/2\) unmarked vectors or ?? is satisfied, then we stop. Otherwise, we pick any \(|A|/2\) unmarked vectors, apply Lemma 19 to them, and let \(A_{m+1}\) be the resulting subset. Then we mark all the vectors in \(A_{m+1}\) and repeat with \(m := m+1\).

It is easy to see that \(A_1, \ldots, A_m\) are disjoint. It remains to bound their total size and show that ?? holds. By Lemma 19, we have \[\label{eq:lemdensify-1} |A_i| \leq 20 \log (|A|/2) \leq 20 \log |A|\tag{33}\] and \[\label{eq:lemdensify-2} |\mathcal{S}(A_i)| \geq \frac{|A|}{2 \cdot 20^d (\log |A|)^d} \geq \frac{80|A|}{(\log |A|)^{2d}} + 1.\tag{34}\] The last inequality is due to that \(|A|\) is sufficiently large. In view of 34 , when the construction of \(A_1, \ldots, A_m\) terminates, we have \[\label{eq:lemdensify-3} m \leq \left\lceil \frac{\ell}{80|A|}(\log |A|)^{2d} \right\rceil \leq \frac{\ell}{40|A|}(\log |A|)^{2d}.\tag{35}\] In view of 33 and 35 , we have \[\label{eq:lemdensify-4} \sum_{i=1}^m |A_i| \leq 20 \log |A| \cdot \frac{\ell}{40|A|}(\log |A|)^{2d} = \frac{\ell}{2|A|}(\log |A|)^{3d}.\tag{36}\] Recall that \(\ell \leq |A|^2/(\log |A|)^{3d}\). Inequality 36 implies that \(|A|\) always has at least \(|A|/2\) unmarked elements during the construction of \(A_1, \ldots, A_m\). Therefore, ?? must hold when the construction terminates. ◻

Proof. We prove a stronger lemma in which the bound on \(|R|\) is replaced by \(\frac{c\mu\ell}{|A'|}(\log (\mu\ell))^{3d}\log \ell\).

Let \(c\) be a sufficiently large constant. Note that \(\ell\) must be a positive integer since \(\Gamma \subseteq Z\) and \(\Gamma\) is full-dimensional. We prove by induction on \(\ell\). When \(\ell = 1\), we have that \(\Gamma = Z\), and the lemma holds trivially. Suppose that the lemma holds for all \(\ell\) with \(\ell \leq k\) for some \(k \geq 1\). We show that it also holds when \(\ell = k+1\).

If \(c \mu > |A'|\), the lemma follows straightforwardly by Lemma 17. Assume that \(c\mu \leq |A'|\).

Let \(\Gamma' = \Gamma + \mathcal{L}(\vb*{h})\) and \(\ell' := \mathrm{det}(\Gamma')/\mathrm{det}(Z)\) and \(\mu' := \mu(A', \Gamma')\). We show that the inductive hypothesis in applicable to \(\Gamma'\). Since \(\vb*{0} \in \mathcal{S}(R_1)\), Equation 31 implies that \(\vb*{h} \in \mathcal{S}(R_1) + \Gamma\). Since \(R_1 \subseteq Z\) and \(\Gamma \subseteq Z\), we have \(\vb*{h} \in Z\), and therefore, \(\Gamma' \subseteq Z\). Since \(\vb*{h} \notin \Gamma\), we have \(\Gamma \subsetneq \Gamma'\). So \(\ell' \leq \ell/2 \leq k\). We also have that \[\frac{\mu'}{\mu} \leq \frac{\mathrm{det}(\Gamma)}{\mathrm{det}(\Gamma')} = \frac{\ell}{\ell'},\] which implies \(\ell'\mu'\leq \ell \mu \leq n^2/(\log n)^{3d}\). For any \(\Lambda\) with \(\Gamma' \subseteq \Lambda \subsetneq Z\), we have \(\Gamma \subseteq \Lambda\), and therefore, \[|A \setminus \Lambda| \geq c\mu\ell/n \geq c\mu'\ell'/n.\] By the inductive hypothesis, \(A\) contains a subset \(R_2\) of at most \(\frac{c\mu'\ell'}{n} (\log (\mu'\ell'))^{3d} \log \ell'\) vectors such that \[\label{eq:gen-rem-dense-2} \mathcal{S}_{\Gamma'}(R_2) = Z \bmod \Gamma'.\tag{37}\] Let \(R = R_1 \cup R_2\). We have \[\begin{align} |R| \leq |R_1| + |R_2| &= \frac{16\mu\ell}{n} (\log (\mu\ell))^{3d} + \frac{c\mu'\ell'}{n} (\log (\mu'\ell'))^{3d} \log \ell' \\ & \leq \frac{c\mu\ell}{n} (\log (\mu\ell))^{3d} (1 + \log \ell') \leq \frac{c\mu\ell}{n} (\log (\mu\ell))^{3d}\log \ell. \end{align}\] Equation ?? implies that \(\vb*{h} + \mathcal{S}(R) \equiv \mathcal{S}(R) \pmod {\Gamma},\) and Equation 37 implies that \(\mathcal{S}_{\Gamma'}(R) = Z \bmod \Gamma'\). By Lemma 16, we have \(\mathcal{S}_{\Gamma}(R) = Z \bmod \Gamma\). ◻

Proof. Recall that \(S_1, S_2 \subseteq [b_{11}] \times \cdots \times [b_{dd}]\), where \(b_{11}, \ldots, b_{dd}\) are the diagonal elements of the basis of \(\Gamma\) in Hermite normal form. Note that \(\prod_{i=1}^d b_{ii} = \ell.\) It follows that \[S_1+S_2\subseteq [2b_{11}] \times \cdots \times [2b_{dd}].\] Each residue class modulo \(\Gamma\) contains at most \(2^d\) vectors in \([2b_{11}] \times \cdots \times [2b_{dd}]\). Therefore, \[|S_1+S_2|\leq 2^d |S|.\]

Each vector in \([2b_{11}] \times \cdots \times [2b_{dd}]\) can be mapped to a unique integer on \(\mathbb{Z}\) in the range \([\prod_{i=1}^{d} 2b_{ii}] = [2^d\ell]\). Then we can compute \(S_1 + S_2\) using algorithms for sparse convolution [57] in time \[O(|S_1 + S_2| \cdot \mathrm{polylog}(2^d \ell) = O(2^d |S| \cdot \mathrm{polylog}(2^d \ell).\] Given \(S_1 + S_2\), we can obtain \(S\) in \(O(|S_1 + S_2| d^2)=O(2^d |S|\cdot d^2)\) time via Lemma [lem:compute-rem](i). One can verify that the total time cost is bounded by \(O(2^d |S| \cdot \mathrm{polylog}(2^d\ell)).\) ◻

Proof. Let \(H:=\mathrm{Sym}_{\Gamma}(S)\). For simplicity of notation, in this proof, all the operations \(+\) and \(-\) are modulo \(\Gamma\). That is, they are the group operation of the additive group \(\mathbb{Z}^d_{\Gamma}\). We first show that \(H \subseteq S - S\). For any \(\vb*{h} \in H\), by definition, we have \(\vb*{h} + S = S.\) Therefore, there exists \(\vb*{s}_1,\vb*{s}_2 \in S\) such that \(\vb*{h} + \vb*{s}_1 = \vb*{s}_2.\) This implies \(\vb*{h} \in S - S.\) Therefore, we have \(H \subseteq S - S\).

Let \(X := (S - S) \setminus H\).

Note that \(H = (S - S)\setminus X\). Claim 26 and Claim 27 imply that \[(S - S)\setminus X \equiv (S - S)\setminus ((X + S) \setminus S) - S) = (S - S) \setminus (((S - S) + S) \setminus S - S). \qedhere\] ◻

Proof. For simplicity of notation, in this proof, all the operations \(+\) and \(-\) are modulo \(\Gamma\). That is, they are the group operation of the additive group \(\mathbb{Z}^d_{\Gamma}\). We also assume that \(m\) is a power of \(2\). This can be done by adding dummy sets of the form \(\{\vb*{0}\}\).

We shall invoke Algorithm 1. Basically, Algorithm 1 computes \(S_1 + \cdots + S_m\) recursively as follows. It computes \(S'_j = S_{2j-1} + S_{2j}\) via Lemma 21 for \(j \in \{1, \ldots, m/2\}\), and then recursively computes \(S'_1 + \cdots + S'_{m/2}\). The trick is that when \(|S'_1| + \cdots + |S'_j| \geq \ell + m/2\) for some \(j\), it stops computing the remaining sets (because \(\mathrm{Sym}_\Gamma(S'_1 + \cdots + S'_j)\) already contains a non-zero vector), and immediately starts recursion on \(S'_1, \ldots, S'_j\).

Let \(S\) be the result of Algorithm 1. Note that \(S\subseteq S_1 + \cdots + S_m\). We can compute \(\mathrm{Sym}_{\Gamma}(S)\) in \(O(2^d \ell\cdot \log(2^d\ell))\) time via Lemma 23. Suppose \(\mathrm{Sym}_{\Gamma}(S)\) contains a non-zero vector \(\vb*{h}\). Recall that if \(\vb*{h}\in \mathrm{Sym}_{\Gamma}(S)\), then \(\vb*{h}\in \mathrm{Sym(S_1 + \dots + S_m)}\). In this case, we are done. Otherwise, if we obtain no such vector, then by Claim 28, \(S = S_1 + \cdots + S_m\).

The recursion tree of Algorithm 1 has at most \(\log m\) levels. Note that \(|S'_j| \leq \mathbb{|}Z^d_{\Gamma}|= \ell\). In each level \(i\), when the criterion \(t < \ell + m/2^i\) is violated, the total cardinality (that is, \(t\)) is bounded by \(\ell + m/2^i + \ell\). Therefore, the total time cost of applying Algorithm 1 and Lemma 23 is \[\begin{align} &O(n) + O(2^d\ell\log(2^d\ell)) + \sum_{i = 1}^{\log m} O\left( 2^d (2\ell + \frac{m}{2^i}) \cdot \mathrm{polylog}(2^d \ell)\right)\nonumber\\ = &O\left( n+ 2^d(m + \ell\log m)\cdot \mathrm{polylog}(2^d \ell)\right).\label{eq:sumset-or-stablizer-1} \end{align}\tag{38}\]

Next, we show that this running time can be reduced to \(O(n + 2^d \ell\cdot \mathrm{polylog}(2^d \ell))\) by dealing with the sets of cardinality \(1\) separately. Suppose that \(|S_i| \geq 2\) for all \(i \leq m'\) and that \(|S_i| = 1\) for all \(i > m'\).

Suppose that \(m' \leq \ell\). We can apply Algorithm 1 to \(S_1, \ldots, S_{m'}\) and then Lemma 23 to the result of Algorithm 1. The total time cost of Algorithm 1 and Lemma 23 is bounded by (38 ) with \(m\) replaced by \(\ell\), which is \[\label{eq:sumset-or-stablizer-2} O\left(n + 2^d \ell\cdot \mathrm{polylog}(2^d\ell)\right).\tag{39}\] If we obtain a non-zero vector \(\vb*{h}\in \mathrm{Sym}(S_1+\dots+S_m)\), then the time cost is bounded by (39 ). Otherwise, we obtain \(S = S_1 + \cdots + S_{m'}\). Since \(|S_i| = 1\) for all \(i > m'\), we can compute \(S' = S_{m'+1} + \cdots + S_{m}\) trivially in \(O(n + d^2)\) time by Lemma [lem:compute-rem]. Then we compute \(S + S'\), which takes \(O(d^2 \ell)\) time since \(|S|\leq \ell\) and \(|S'| = 1\).

Now consider the case where \(m' \geq \ell\). We have that \[\sum_{i=1}^{\ell} |S_i| \geq 2\ell\ge |S_1+\dots+S_{\ell}|+\ell.\] By Corollary 1, there exists a non-zero vector \(\vb*{h}\in\mathrm{Sym}(S_1 + \cdots + S_{\ell})\). Therefore, applying Algorithm 1 to \(S_1, \ldots, S_{\ell}\) and then Lemma 23 to the result of Algorithm 1 will give us the non-zero vector \(\vb*{h}\), which is also in the symmetry set of \(S_1 + \cdots + S_m\). The total time cost is bounded by \(O\left(2^d \ell\cdot \mathrm{polylog}(2^d \ell)\right).\) ◻

Proof. We use Algorithm 2. The correctness follows by Lemma 16.

Let \(T(\ell)\) be the running time of the algorithm.

Line 3 takes \(O(n + 2^d \ell\cdot \mathrm{polylog}(2^d \ell))\) time. Line 8 takes \(O(d^2 + d\log \ell)\) time by Lemma [lem:compute-rem](iii). Lines 9-10 take \(O(d^2n)\) time by Lemma [lem:compute-rem](i). Since \(\vb*{h}\in \mathrm{Sym}(S_1 + \cdots + S_m)\) is non-zero, we have \(\Gamma' \supsetneq \Gamma\), and therefore \(\mathrm{det}(\Gamma') \leq \mathrm{det}(\Gamma)/2\). By recursion, line 11 takes at most \(T(\ell/2)\) time. Computing \((\Lambda \bmod \Gamma)\) takes \(O(\ell d^3)\) time by Lemma [lem:compute-rem](ii). So line 12 takes \(O(2^d \ell\cdot \mathrm{polylog} (2^d \ell))\) time. In summary, we have \(T(1) = O(1)\) and \[T(\ell) \leq T(\frac{\ell}{2}) + O(d^2n + 2^d \ell\cdot \mathrm{polylog}(2^d \ell)).\] Solving the recurrence, we have \(T(\ell) = O(d^2n \log \ell + 2^d \ell \cdot \mathrm{polylog}(2^d \ell))\). ◻

Proof. Let \(B = (\vb*{b}_1, \ldots, \vb*{b}_d)\) be the basis of \(Z\) in Hermite normal form. Note that \(B^{-1}B = I\), where \(I\) is the identity matrix. Computing \(B^{-1}\) takes only \(\mathrm{poly}(d)\) time. \(B^{-1}\) can be viewed as a linear transformation that maps \(Z\) to \(\mathbb{Z}^d\). Let \(A' = B^{-1}A\). Let \(\Gamma' = B^{-1}\Gamma\). It takes \(O(d^2n)\) time to compute \(A'\), and \(\mathrm{poly}(d)\) time to compute (the basis of) \(\Gamma'\). We have that \(\mathrm{det}(\Gamma') = \mathrm{det}(\Gamma)/\mathrm{det}(Z) = \ell\).

We can compute \(\mathcal{S}_{\Gamma'}(A')\) via Theorem 29 in \(O(d^2 n\log \ell + 2^d \ell\cdot \mathrm{polylog}(2^d \ell))\). Given \(\mathcal{S}_{\Gamma'}(A')\), we can compute \(\mathrm{Sym}_{\Gamma'}(\mathcal{S}(A'))\) via Lemma 23 in \(O(d^2 n\log \ell + 2^d \ell\cdot \mathrm{polylog}(2^d \ell))\).

We can obtain \(\mathcal{S}_{\Gamma}(A)\) and \(\mathrm{Sym}_{\Gamma}(\mathcal{S}(A))\) from \(\mathcal{S}_{\Gamma'}(A')\) and \(\mathrm{Sym}_{\Gamma'}(\mathcal{S}(A'))\) by left multiplying them by \(B\), which takes \(O(d^2\ell)\) time.

One can verify that the total time cost is \(\widetilde{O}((n + 2^d\ell) \cdot \mathrm{poly}(d))\). ◻

Proof. Let \(p_1, \ldots, p_d\) be distinct primes in \([\sqrt{N_i}, \sqrt{N_i} + N_i^{0.3}],\) which exist due to [58]. Define \[A = \bigl\{(x_1 p_1 + 1, x_2 p_2 + 1, \dots, x_d p_d + 1) : 0 \leq x_i \leq \left\lfloor \frac{N_i}{p_i} \right\rfloor, \, x_i \in \mathbb{Z} \bigr\}.\] One can verify that \(|A \setminus \Gamma| \geq |A|/4\) for any full-dimensional lattice \(\Gamma \subsetneq \mathbb{Z}^d\) and that \(|A| \leq (1-o(1))\sqrt{\Phi}.\)

Let \(\Gamma \subseteq \mathbb{Z}^d\) be the lattice generated by \(\{p_i \vb*{e}_i : 1 \leq i \leq d\}\). Note that \(\mathrm{det}(\Gamma) = \prod_{i=1}^{d} p_i\). We also have that \(A \pmod{\Gamma} = \{\vb*{1}\}.\) Hence, \(\mathcal{S}_\Gamma(A)\) contains at most \[|A| \leq \frac{\prod_{i=1}^{d} N_i}{\prod_{i=1}^{d} p_i}\leq (1-o(1)) \prod_{i=1}^{d} p_i = (1-o(1))\mathrm{det}(\Gamma)\] distinct residue classes of \(\mathbb{Z}^d_\Gamma\).

Suppose, for contradiction, that there exists a convex body \(K\) such that \[K \cap \mathbb{Z}^d \subseteq \mathcal{S}(A) \quad \text{and} \quad |K \cap \mathbb{Z}^d| = (1- o(1)) |\mathcal{S}(A)|.\] One can verify that the convex hull of \(\mathcal{S}(A)\) contains a large hyperrectangle with edge length \(N_1, \ldots, N_d\). Therefore, \(K\) must also contain a large hyperrectangle. More precisely, there exists a vector \(\vb*{a} \in \mathbb{Z}^d\) such that \((a+[0,p_1-1]\times \cdots \times [0,p_d-1])\subseteq K\) for some \(\vb*{a} \in \mathbb{Z}^d\). This contradicts the fact that \(\mathcal{S}_\Gamma(A)\) contains at most \((1-o(1))\mathrm{det}(\Gamma)\) distinct residue classes of \(\mathbb{Z}^d_\Gamma\). ◻

Proof. By Lemma 1, in \(\widetilde{O}(d^3n\log N)\) time, we can obtain \(Z := \mathcal{L}(A)\). If \(Z\) is not full-dimensional, then we can immediately conclude that \(A\) is not \(\delta\cdot (d\log N)^{3d}\)-nondegenerate. Assume that \(Z\) is full-dimensional.

Let \(k := \delta \cdot \sqrt{N^d/\mathrm{det}(Z)}\). We shall construct a sequence \(A_0 \supsetneq A_1 \supsetneq \cdots \supsetneq A_r\) until \(Z_r := \mathcal{L}(A_r)\) is not full-dimensional or \(|A_r \setminus \Gamma| \geq k\) for any \(\Gamma \subsetneq Z_r\). Initially, \(i := 0\) and \(A_0 := A\). Given \(A_i\), we can check whether \(Z_i := \mathcal{L}(A_i)\) is full-dimensional or not in \(\widetilde{O}(d^3n\log N)\) time via Lemma 1. If not, then we stop and set \(r := i\). Suppose that \(Z_i\) is full-dimensional. Then we invoke Lemma 12 on \(A_i\) and \(k\), which takes \(\widetilde{O}((n + \sqrt{N})\cdot \mathrm{poly}(d))\) time. If it asserts that \(|A_i \setminus \Gamma| \geq k\) for any \(\Gamma \subsetneq Z_i\), then we stop and set \(r := i\). Otherwise, it returns a \(\Gamma_i \subsetneq Z\) such that \[|A_i \setminus \Gamma_i| \leq k\cdot (d\log N)^{2d}.\] We set \(A_{i+1} := A_i \cap \Gamma_i\), and then proceed with \(i := i+1\).

We first show that \(r \leq 1 + d\log N\). Suppose not. Note that \(Z_{r-1}\) must be full-dimensional. Observing that \(Z_{i} \subsetneq Z_{i-1}\) for all \(i\), we have \[\mathrm{det}(Z_{r-1}) \geq 2^{r-1} \cdot \mathrm{det}(Z_0) > N^d.\] But this is impossible since \(Z_{r-1} = \mathcal{L}(A_{r-1})\) and \(A_{r-1} \subseteq [N]^d\).

Note that \(|A_{i}| - |A_{i+1}| \leq k\cdot (d\log N)^{2d}\). We have \[|A_r| \geq |A| - rk\cdot (d\log N)^{2d} \geq |A| - k\cdot (d\log N)^{4d}.\] Therefore, if the construction ends with \(Z_r\) not full-dimensional, then we can assert that \(A\) is not \(\delta\cdot (d\log N)^{4d}\)-nondegenerate. Otherwise, it ends with \(|A_r \setminus \Gamma| \geq k\) for any \(\Gamma \subsetneq Z_r\). This implies that \(A_r\) is \(\delta\)-nondegenerate, so is \(A\).

It is easy to verify that the total running time is \(\widetilde{O}((n + \sqrt{N})\cdot \mathrm{poly}(d))\) time and the total error probability is at most \(N^{-\Omega(d)}\). ◻

Proof. Suppose \(\sum_i | \vb*{a}_i\cdot\vb*{y}|\le 1\). Then for arbitrary \(z\in P\), \(\vb*{p}\cdot\vb*{y}=\vb*{y}\cdot \sum_{i}\vb*{a}_ix_i=\sum_i (\vb*{y}\cdot\vb*{a}_i)x_i\le \sum_i |\vb*{y}\cdot \vb*{a}_i|\le 1\).

Suppose \(\vb*{p}\cdot\vb*{y}\le 1\) for all \(\vb*{p}\in P\). Suppose on the contrary that \(\sum_i |\vb*{y}\cdot \vb*{a}_i|> 1\). Let \(x_i^*=1\) if \(\vb*{y}\cdot \vb*{a}_i\ge 0\), and \(x_i^*=-1\) otherwise. Then it is clear that \(\vb*{p}^*=\sum_i\vb*{a}_ix_i^*\in P\), and \(\vb*{y}\cdot\vb*{p}^*=\sum_i |\vb*{y}\cdot \vb*{a}_i|>1\), which is a contradiction. ◻

Proof. We first prove (i). Let \(B\) be the basis of \(\Gamma\) in Hermite Normal Form. By Definition 1, \(B\) is a lower-triangular matrix. Hence, \(\vb*{v} \bmod \Gamma\) can be computed as follows. For each \(j \in \{1, 2, \dots, d\}\), compute \(x_j = \left\lfloor \frac{v_j }{b_{jj}} \right\rfloor,\) and update \(\vb*{v} := \vb*{v} - x_j \vb*{b}_j.\) The total time cost is \(O(d^2)\).

Next, we prove (ii). Let \(B\) and \(B'\) be the basis of \(\Gamma\) and \(\Gamma'\) in Hermite normal form, respectively. Let \(s_j : = b_{jj}/b'_{jj}\) for \(j \in [d]\). By Fact 4, \(s_j\) is an integer. To compute the representatives of \(\Gamma' \pmod \Gamma\), it suffices to consider the remainders (modulo \(\Gamma\)) of the vectors of the form \[\vb*{v} = \sum_{j=1}^d z_j \vb*{b}'_j,\] where \(0 \leq z_j < s_j, z_j \in \mathbb{Z}\), since the number of such vectors is exactly \(\prod_{i=1}^d s_i = \frac{\mathrm{det}(\Gamma)}{\mathrm{det}(\Gamma')} = |\Gamma' \bmod \Gamma|\), and one can also verify that no two such vectors are congruent modulo \(\Gamma\). By (i), it takes \(\mathcal{O}(d^2)\) time to compute \(\vb*{v} \bmod \Gamma\) for each \(\vb*{v}\). Therefore, the total time cost is \(O(\frac{|\mathrm{det}(\Gamma)|}{|\mathrm{det}(\Gamma')|}\cdot d^2)\).

Next we prove (iii). Let \(B\in \mathbb{Z}^{d\times d}\) be the basis of \(\Gamma\) in Hermite Normal Form. We can first update \(\vb*{h} := \vb*{h} \bmod \Gamma\) in \(O(d^2)\) time by (i). Let \(h_1,\dots,h_d\) be the entries of vector \(\vb*h\). For \(i \in \{1, \ldots, d\}\) from \(1\) to \(d\), we iteratively update \(\vb*b_i\) and \(\vb*h\) to make \(h_i=0\) while keeping the lattice generated by \(\vb*b_1,\dots,\vb*b_d,\vb*h\) unchanged.

We use the extended Euclidean algorithm to compute \(g_i=\gcd(b_{ii},h_i)\) and integers \(x,y\) such that \[xb_{ii}+yh_i=g_i.\] This step takes \(O(\log(\max\{b_{ii},h_i\}))=O(\log \ell)\) time. We then update \(\vb*{b}_i\) and \(\vb*{h}\) as follows \[\vb*b_i'=x\vb*b_i+y\vb*{h}, \qquad \vb*h'=-\frac{h_i}{g_i}\vb*b_i+\frac{b_{ii}}{g_i}\vb*h.\] By updating \(\vb*b_i := \vb*b_i'\) and \(\vb*h := \vb*h'\), we have \(B_{ii}=g_i\) and \(h_i=0\), and the lattice generated by \(\vb*b_i\) and \(\vb*h\) is unchanged. Each such update uses \(O(d)\) arithmetic operations.

Repeating this for \(i=1,\dots,d\) yields a basis in Hermite normal form for \(\Gamma'\), and the total number of arithmetic operations is \(O(d(d+\log \ell))\). ◻