## 3 A Faster Provable Sieving Algorithm in \(\ell_{p}\) Norm
### Linear Sieve
: This follows from Lemma 5 in Section 3.1. Claim 1: _The following two invariants are maintained in Algorithm 1_:  
1. \(\forall(\mathbf{e},\mathbf{y})\in S,\quad\mathbf{y}-\mathbf{e}\in\mathcal{L}\) 2. \(\forall(\mathbf{e},\mathbf{y})\in S,\quad\|\mathbf{y}\|_{p}\leq R\). Proof. :
1. The first invariant is maintained at the beginning of the sieving iterations in Algorithm 1 due to the choice of \(\mathbf{y}\) at step 4 of Algorithm 1. Since each center pair \((\mathbf{e}_{\mathbf{c}},\mathbf{c})\) once belonged to \(S\), \(\mathbf{c}-\mathbf{e}_{\mathbf{c}}\in\mathcal{L}\). Thus, at step 15 of the sieving procedure (Algorithm 2), we have \((\mathbf{e}-\mathbf{y})+(\mathbf{c}-\mathbf{e}_{\mathbf{c}})\in\mathcal{L}\). 2. The second invariant is maintained in steps 2-6 of Algorithm 1 because \(\mathbf{y}\in\mathcal{P}(\mathbf{B})\) and hence \(\|\mathbf{y}\|_{p}\leq\sum_{i=1}^{n}\|\mathbf{b}_{i}\|_{p}\leq n\max_{i}\| \mathbf{b}_{i}\|_{p}=R\). We claim that this invariant is also maintained in each iteration of the sieving procedure. Consider a pair \((\mathbf{e},\mathbf{y})\in S\) and let \(I_{\mathbf{y}}\) be its index-tuple. Let \((\mathbf{e}_{\mathbf{c}},\mathbf{c})\) be its associated center pair. By Algorithm 2, we have \(I_{\mathbf{y}}=I_{\mathbf{c}}\); i.e., \(\|\mathbf{y}-\mathbf{c}\|_{p}^{p}=\sum_{i=1}^{n}|y_{i}-c_{i}|^{p}\leq\sum_{i= 1}^{n}\frac{\gamma^{p}R^{p}}{n}\leq\gamma^{p}R\). Thus, \(\|\mathbf{y}-\mathbf{c}\|_{p}\leq\gamma R\) and hence \(\|\mathbf{y}-\mathbf{c}+\mathbf{e}_{\mathbf{c}}\|_{p}\leq\|\mathbf{y}- \mathbf{c}\|_{p}+\|\mathbf{e}_{\mathbf{c}}\|_{p}\leq\gamma R+\xi\lambda\). The claim follows by the re-assignment of variable \(R\) at step 10 in Algorithm 1. In the following lemma, we bound the length of the remaining lattice vectors after all the sieving iterations are over. The proof is similar to that given in [49], so we write it briefly. Lemma 7: _At the end of \(k\) iterations in Algorithm 1, the length of lattice vectors \(\|\mathbf{y}-\mathbf{e}\|_{p}\leq\frac{\xi(2-\gamma)\lambda}{1-\gamma}+\frac{ \gamma\xi}{n(1-\gamma)}=:R^{\prime}\)._  
Proof. : Let \(R_{k}\) be the value of \(R\) after \(k\) iterations, where  
\(\log_{\gamma}\left(\frac{\xi}{nR(1-\gamma)}\right)\leq k\leq\log_{\gamma} \left(\frac{\xi}{nR(1-\gamma)}\right)+1\). Then,  
\[R_{k} = \gamma^{k}R+\sum_{i=1}^{k}\gamma^{k-1}\xi\lambda\leq\frac{\xi \gamma}{n(1-\gamma)}+\frac{\xi\lambda}{1-\gamma}\Big{[}1-\frac{\xi}{nR(1- \gamma)}\Big{]}\]  
Thus, after \(k\) iterations, \(\|\mathbf{y}\|_{p}\leq R_{k}\), and hence after \(k\) iterations,  
\[\|\mathbf{y}-\mathbf{e}\|_{p} \leq \|\mathbf{y}\|_{p}+(\|-\mathbf{e}\|_{p})\leq R_{k}+\xi\lambda\] \[= \frac{(2-\gamma)\xi\lambda}{1-\gamma}+\frac{\gamma\xi}{n(1-\gamma)}\]  
Using Corollary 1 and assuming \(\lambda\approx\lambda_{1}^{(p)}\), we obtain an upper bound on the number of lattice vectors of a length of at most \(R^{\prime}\); i.e.,  
\(|B_{n}^{(p)}(R^{\prime})\cap\mathcal{L}|\leq 2^{c_{b}n+o(n)}\), where \(c_{b}=\log\Bigl{(}1+\frac{2\zeta(2-\gamma)}{1-\gamma}\Bigr{)}\). The above lemma along with the invariants implies that at the beginning of step 12 in Algorithm 1, we have \"short\" lattice vectors; i.e., vectors with a norm bounded by \(R^{\prime}\). We want to start with a \"sufficient number\" of vector pairs so that we do not end up with all zero vectors at the end of the sieving iterations. For this, we work with the following conceptual modification proposed by [PERSON] [67]. Let \(\mathbf{u}\in\mathcal{L}\) such that \(\|\mathbf{u}\|_{p}=\lambda_{1}^{(p)}(\mathcal{L})\approx\lambda\) (where \(2<\lambda_{1}^{(p)}(\mathcal{L})\leq 3\)), \(D_{1}=B_{n}^{(p)}(\xi\lambda)\cap B_{n}^{(p)}(-\mathbf{u},\xi\lambda)\) and \(D_{2}=B_{n}^{(p)}(\xi\lambda)\cap B_{n}^{(p)}(\mathbf{u},\xi\lambda)\). Define a bijection \(\sigma\) on \(B_{n}^{(p)}(\xi\lambda)\) that maps \(D_{1}\) to \(D_{2}\), \(D_{2}\) to \(D_{1}\) and \(B_{n}^{(p)}(\xi\lambda)\setminus(D_{1}\cup D_{2})\) to itself :  
\[\sigma(\mathbf{e})=