where $\mathbf{x}$ is taken uniformly at random in $\mathbb{F}_2^s \setminus \{C_{\text{aux}}^{\perp} + \mathbf{e}_{\mathscr{P}}\}$. By definition,

$$
\begin{align*}
\mathbb{E}_{C_{\text{aux}}, \mathbf{x}} (N_j (C_{\text{aux}}^{\perp} + \mathbf{x})) &= \sum_{\mathbf{z} \in S_j^s} \mathbb{P}_{C_{\text{aux}}, \mathbf{x}} (\mathbf{z} \in C_{\text{aux}}^{\perp} + \mathbf{x}) \\
&= \sum_{\mathbf{z} \in S_j^s, \mathbf{x}_0 \in \mathbb{F}_2^s} \mathbb{P}_{C_{\text{aux}}} (\mathbf{z} - \mathbf{x}_0 \in C_{\text{aux}}^{\perp}) \mathbb{P}_{\mathbf{x}, C_{\text{aux}}} (\mathbf{x} = \mathbf{x}_0) \\
&\le \sum_{\mathbf{z} \in S_j^s} \left( \sum_{\mathbf{x}_0 \in \mathbb{F}_2^s} \frac{2^{s-k_{\text{aux}}} - 1}{2^s - 1} \mathbb{P}_{\mathbf{x}, C_{\text{aux}}} (\mathbf{x} = \mathbf{x}_0) + \mathbb{P}_{\mathbf{x}, C_{\text{aux}}} (\mathbf{x} = \mathbf{z}) \right) \\
&\le \binom{s}{j} \frac{2^{s-k_{\text{aux}}} - 1}{2^s - 1} + \frac{\binom{s}{j}}{2^s - 2^{k_{\text{aux}}}} \\
&\le \frac{\binom{s}{j}}{2^{k_{\text{aux}}}} 2^{k_{\text{aux}}} \frac{2^{s-k_{\text{aux}}} - 1}{2^s - 1} + \frac{\binom{s}{j}}{2^{k_{\text{aux}}}} \frac{2^{k_{\text{aux}}}}{2^s - 2^{k_{\text{aux}}}} \\
&\le \frac{\binom{s}{j}}{2^{k_{\text{aux}}}} \frac{2^s - 2^{k_{\text{aux}}}}{2^s - 1} + \frac{\binom{s}{j}}{2^{k_{\text{aux}}}} \frac{1}{2^{s-k_{\text{aux}}} - 1} \\
&\le \frac{\binom{s}{j}}{2^{k_{\text{aux}}}} (1 + \mathcal{O}(2^{k_{\text{aux}}-s}))
\end{align*}
$$

which completes the proof.

<figure><img src="image_9.png" /></figure>

We can now show that the expected value of $N_{i,j}$ is the product of the two previously computed quantities:

**Lemma 10.** Under Distribution 1 and when $\mathbf{x}$ is taken uniformly at random in $\mathbb{F}_2^s \setminus \{C_{\text{aux}}^{\perp} + \mathbf{e}_{\mathscr{P}}\}$ we have

$$
\mathbb{E}_{C, C_{\text{aux}}, \mathbf{x}} (N_{i,j}) = \overline{N_j^{(C_{\text{aux}}^{\perp})}} \overline{N_i^{(C_{\mathcal{N}}^{\mathcal{N}})}}
$$

where,

$$
N_{i,j} \stackrel{\text{def}}{=} |\{(\mathbf{r}, \mathbf{c}^{\mathcal{N}}) \in (\mathbf{x} + \mathcal{C}_{\text{aux}}^{\perp}) \times \mathcal{C}^{\mathcal{N}} : |\mathbf{r}| = j \text{ and } |(\mathbf{r} + \mathbf{e}_{\mathscr{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathbf{c}^{\mathcal{N}}| = i\}|$$

and,

$$
\overline{N_j^{(C_{\text{aux}}^{\perp})}} \stackrel{\text{def}}{=} \mathbb{E}_{C, C_{\text{aux}}, \mathbf{x}} (N_j (C_{\text{aux}}^{\perp} + \mathbf{x})) \quad ; \quad \overline{N_i^{(C_{\mathcal{N}}^{\mathcal{N}})}} \stackrel{\text{def}}{=} \mathbb{E}_{C} (N_i (C_{\mathcal{N}}^{\mathcal{N}} + (\mathbf{r} + \mathbf{e}_{\mathscr{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}})).
$$

*Proof.* By definition,

$$
N_{i,j} = \sum_{u=0}^{N_j(C_{\text{aux}}^{\perp} + \mathbf{x})} N_i \left( \left( \mathbf{r}^{(u)} + \mathbf{e}_{\mathscr{P}} \right) \mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}} \right)
$$

where $\mathbf{r}^{(u)}$ is the $u$'th codeword of weight $j$ of $C_{\text{aux}}^{\perp} + \mathbf{x}$ and $N_j(C_{\text{aux}}^{\perp} + \mathbf{x})$ counts the number of elements in $C_{\text{aux}}^{\perp} + \mathbf{x}$ of Hamming weight $j$. Therefore,

$$
\begin{align*}
N_{i,j} &= \sum_{\mathbf{z} \in S_j^s} N_i \left( (\mathbf{z} + \mathbf{e}_{\mathscr{P}}) \mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}} \right) \mathbf{1}_{\text{``}\mathbf{z} \in C_{\text{aux}}^{\perp} + \mathbf{x}''} \\
&= \sum_{\mathbf{z} \in S_j^s, \mathbf{w} \in S_i^{n-s}} \mathbf{1}_{\text{``}\mathbf{w} \in (\mathbf{z} + \mathbf{e}_{\mathscr{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}}''} \mathbf{1}_{\text{``}\mathbf{z} \in C_{\text{aux}}^{\perp} + \mathbf{x}''}
\end{align*}
$$
We deduce that,

$$
\begin{align*}
\mathbb{E}_{\mathcal{C}, \mathcal{C}_{\text{aux}}, \mathbf{x}} (N_{i,j}) &= \sum_{\mathbf{z} \in S_j^s, \mathbf{w} \in S_i^{n-s}} \mathbb{P} (\mathbf{w} \in (\mathbf{z} + \mathbf{e}_{\mathcal{D}}) \mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}}, \mathbf{z} \in \mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}) \\
&= \sum_{\mathbf{z} \in S_j^s, \mathbf{w} \in S_i^{n-s}} \mathbb{P} (\mathbf{w} \in (\mathbf{z} + \mathbf{e}_{\mathcal{D}}) \mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}} \mid \mathbf{z} \in \mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}) \mathbb{P} (\mathbf{z} \in \mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}) \\
&= \sum_{\mathbf{z} \in S_j^s} \left( \sum_{\mathbf{w} \in S_i^{n-s}} \mathbb{P} (\mathbf{w} \in (\mathbf{z} + \mathbf{e}_{\mathcal{D}}) \mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}} \mid \mathbf{z} \in \mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}) \right) \mathbb{P} (\mathbf{z} \in \mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}) \\
&= \sum_{\mathbf{z} \in S_j^s} \overline{N_i^{(\mathcal{C}^{\mathcal{N}})}} \mathbb{P} (\mathbf{z} \in \mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}) \\
&= \overline{N_i^{(\mathcal{C}^{\mathcal{N}})}} \overline{N_j^{(\mathcal{C}_{\text{aux}}^{\perp})}}
\end{align*}
$$

which completes the proof.

<figure><img src="image_10.png" /></figure>

Proof of Lemma 7. We prove our result by using Fact 5, then Lemmas 9 and 10.

<figure><img src="image_11.png" /></figure>

APPENDIX F. PROOF OF PROPOSITION 6

F.1. **A more minimalistic conjecture.** The goal of this section is to devise a more minimalistic but stronger conjecture which implies Conjecture 1 (in the sense that it involves only concentration bound of the weight enumerator of some random linear codes). Furthermore, the aforementioned implication is a key step of the proof of Proposition 6 which shows that the experimental model implies Conjecture 1.

**Conjecture 2.** For any $(i, j) \in [0, n-s] \times [0, s]$ and any $v \in [0, \overline{V}_j + n^{1.1} \max(\sqrt{\overline{V}_j}, 1)]$, we have under Distribution 1,

$$
\mathbb{P}_{\mathcal{C}_{\text{aux}}, \mathbf{x}} \left( |V_j - \overline{V}_j| > n^{1.1} \max \left( \sqrt{\overline{V}_j}, 1 \right) \right) = \tilde{\mathcal{O}}(2^{-n}), \quad (71)
$$

$$
\mathbb{P}_{\mathcal{C}, \mathcal{C}_{\text{aux}}, \mathbf{x}} \left( |N_{i,j} - v \overline{N_i}| > n^{1.1} \max \left( \sqrt{v \overline{N_i}}, 1 \right) \mid N_j = v \right) = \tilde{\mathcal{O}}(2^{-n}). \quad (72)
$$

where

$$
V_j \stackrel{\text{def}}{=} N_j (\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x})
$$

and

$$
\overline{N_i} \stackrel{\text{def}}{=} \frac{\binom{n-s}{i}}{2^{n-k}}, \quad \overline{V_j} \stackrel{\text{def}}{=} \frac{\binom{s}{j}}{2^{k_{\text{aux}}}}. \qquad (73)
$$

**Remark 6.** Recall that $N_{i,j} \stackrel{\text{def}}{=} \sum_{u=1}^{V_j} N_i^{(u)}$ where $N_i^{(u)} \stackrel{\text{def}}{=} N_i ((\mathbf{r}^{(u)} + \mathbf{e}_{\mathcal{D}}) \mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}})$ and $\mathbf{r}^{(u)}$ is the $u$'th codeword of weight $j$ of $\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}$. From this and using Lemma 9 it is readily seen that we have that

$$
\mathbb{E}_{\mathcal{C}, \mathcal{C}_{\text{aux}}, \mathbf{x}} (N_{i,j} | V_j = v) = v \overline{N_i} (1 + o(1)).
$$

As such, Equation (72) in the previous Conjecture can also really be seen as a concentration inequality.

**Proposition 12.** *Conjecture 2 implies Conjecture 1.*

The following lemmas will be useful to prove this proposition.

**Lemma 11** (Centering Lemma.). We have,

$$
\sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} = \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) (N_{i,j} - V_j \overline{N_i}).
$$
*Proof.* From the orthogonality of Krawtchouk polynomials relatively to the measure $\mu(i) = \binom{n-s}{i}$ [MS86, Ch. 5. §7. Theorem 16] we have:

$$ \sum_{i=0}^{n-s} \binom{n-s}{i} K_w^{(n-s)}(i) = 0. $$

By using the definition of $\overline{N}_i$ in Equation (73), we get,

$$ \begin{aligned} 0 &= \sum_{j=0}^{s} V_j K_{t_{\text{aux}}}^{(s)}(j) \sum_{i=0}^{n-s} K_{w}^{(n-s)}(i) \overline{N_i} \\ &= \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{w}^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j) V_j \overline{N_i}. \end{aligned} $$

Therefore,

$$ \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} = \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) (N_{i,j} - V_j \overline{N_i}) $$

which completes the proof.

□

**Corollary 2.** We have,

$$ \mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) \right) = \\ \tilde{\mathcal{O}} \left( \max_{(i,j) \in [0, n-s] \times [0, s]} \mathbb{P} \left( |N_{i,j} - V_j \overline{N_i}| \ge \frac{1}{2(n+1)^2} \left| \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)} \right| \right) \right) $$

*Proof.* The event

$$ \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{n-s}(i) (N_{i,j} - V_j \overline{N_i}) \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) $$

implies that it exists $j \in [0, s]$ and $i \in [0, n-s]$ such that

$$ K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{n-s}(i) (N_{i,j} - V_j \overline{N_i}) \ge \frac{K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{2(n-s+1)(s+1)}. \quad (74) $$

Therefore,

$$ \begin{aligned} & \mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) \right) \\ &= \mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{n-s}(i) (N_{i,j} - V_j \overline{N_i}) \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) \right) \quad (\text{Lemma 11}) \\ & \le \mathbb{P}_{C, c_{\text{aux}}} \left( \bigvee_{j=0}^{s} \bigvee_{i=0}^{n-s} \left( K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{n-s}(i) (N_{i,j} - V_j \overline{N_i}) \ge \frac{K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{2(n-s+1)(s+1)} \right) \right) \quad (\text{using (74)}) \\ & \le \sum_{j=0}^{s} \sum_{i=0}^{n-s} \mathbb{P} \left( K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{n-s}(i) (N_{i,j} - V_j \overline{N_i}) \ge \frac{K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{2(n-s+1)(s+1)} \right) \quad (\text{union bound}) \\ &= \mathcal{O}(n^2) \max_{\substack{i=0 \dots n-s \\ j=0 \dots s}} \mathbb{P} \left( |N_{i,j} - V_j \overline{N_i}| \ge \frac{1}{2(n+1)^2} \left| \frac{K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{K_{w}^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)} \right| \right) \end{aligned} $$

which completes the proof.

□
**Lemma 12.** Under Parameters constraint 1 we have that

$$ \left( \frac{K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{aux}}^{(s)}(j)} \right)^2 = \omega(n^{\alpha+8}) \overline{N}_i \max \left( \overline{V}_j, \frac{1}{\mathcal{O}(n^\alpha)} \right) $$

*Proof.* First, we simplify $(K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u))^2$ by using Constraint (i) of Parameters constraint 1 which we recall is given by:

$$ \frac{\binom{n-s}{w} \binom{s}{t_{aux}}}{2^{k-k_{aux}}} = \frac{\omega(n^{\alpha+8})}{\delta^2}, \quad \text{where} \quad \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u)}{\binom{n-s}{w} \binom{s}{t_{aux}}} $$

By reordering the terms in the previous equation we get:

$$ (K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u))^2 = 2^{k-k_{aux}} \binom{s}{t_{aux}} \binom{n-s}{w} \omega(n^{\alpha+8}). $$

Now, to show the lemma we only have to show that

$$ \frac{2^{k-k_{aux}} \binom{s}{t_{aux}} \binom{n-s}{w}}{(K_w^{(n-s)}(i) K_{t_{aux}}^{(s)}(j))^2} \ge \overline{N}_i \max \left( \overline{V}_j, \frac{1}{\mathcal{O}(n^\alpha)} \right). \quad (75) $$

First, let us lower bound $\frac{1}{(K_w^{(n-s)}(i))^2}$. From the orthonormality relations of the Krawtchouk polynomials [MS86, Ch. 5, §7. Theorem 16] with the measure $\mu_1(v) = \frac{\binom{n-s}{v}}{2^{n-s}}$ we have that

$$ \sum_{v=0}^{n-s} \binom{n-s}{v} (K_w^{(n-s)}(v))^2 = \binom{n-s}{w} 2^{n-s}, $$

and thus, as the previous sum is composed of positive terms, we have that

$$ \frac{1}{(K_w^{(n-s)}(i))^2} \ge \frac{\binom{n-s}{i}}{\binom{n-s}{w} 2^{n-s}}. \quad (76) $$

Now, let us lower-bound $\frac{1}{(K_{t_{aux}}^{(s)}(j))^2}$. Using the same orthonormality argument relatively to the measure $\mu_2(v) = \frac{s}{2^s}$ we get

$$ \frac{1}{(K_{t_{aux}}^{(s)}(j))^2} \ge \frac{\binom{s}{j}}{\binom{s}{t_{aux}} 2^s}. $$

Furthermore, from Fact 1 we can also deduce the following inequality

$$ (K_{t_{aux}}^{(s)}(j))^2 \le \binom{s}{t_{aux}}^2. $$

Combining the last two equations we get that

$$ \frac{1}{(K_{t_{aux}}^{(s)}(j))^2} \ge \min \left( \frac{\binom{s}{j}}{\binom{s}{t_{aux}} 2^s}, \frac{1}{\binom{s}{t_{aux}}} \right). \quad (77) $$
Finally let us show Equation (75) by using Equation (76) and (77) :

$$
\begin{align*}
\frac{2^{k-k_{\text{aux}}} \binom{s}{t_{\text{aux}}} \binom{n-s}{w}}{(K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j))^2} &\ge 2^{k-k_{\text{aux}}} \binom{s}{t_{\text{aux}}} \binom{n-s}{w} \frac{\binom{n-s}{i}}{\binom{n-s}{w} 2^{n-s}} \min \left( \frac{\binom{s}{j}}{(t_{\text{aux}}) 2^s}, \frac{1}{\binom{s}{t_{\text{aux}}}}^2 \right) \\
&= \frac{\binom{n-s}{i}}{2^{n-k}} \min \left( \frac{\binom{s}{j}}{2^{k_{\text{aux}}}}, \frac{2^{s-k_{\text{aux}}}}{\binom{s}{t_{\text{aux}}}} \right) \\
&= \frac{\binom{n-s}{i}}{2^{n-k}} \min \left( \frac{\binom{s}{j}}{2^{k_{\text{aux}}}}, \frac{1}{\mathcal{O}(n^\alpha)} \right) \quad \text{(Constraint (iii) of Eq. (15))} \\
&= \bar{N}_i \min \left( \bar{V}_j, \frac{1}{\mathcal{O}(n^\alpha)} \right).
\end{align*}
$$

This completes the proof.

<figure><img src="image_12.png" /></figure>

Proof of Proposition 12. Let us suppose that the Parameter constraint 1 is verified and that Con-
jecture 2 is true. We want to show Conjecture 1 holds, namely that

$$
\mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) \right) \\
= \tilde{\mathcal{O}} \left( \max_{(i,j) \in \mathcal{A}} \mathbb{P} (N_{i,j} \ne 0) + 2^{-n} \right).
$$

Using Corollary 2, we only have to show that for any $(i,j) \in [0, n-s] \times [0, s]$ we have

$$
\mathbb{P} \left( |N_{i,j} - V_j \bar{N}_i| \ge \frac{1}{2(n+1)^2} \left| \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)} \right| \right) = \tilde{\mathcal{O}} \left( \max_{(i^*,j^*) \in \mathcal{A}} \mathbb{P} (N_{i^*,j^*} \ne 0) + 2^{-n} \right).
$$

To ease up the notations let us denote by

$$
R_{i,j} \stackrel{\text{def}}{=} \frac{1}{2(n+1)^2} \left| \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)} \right|. \qquad (78)
$$

Thus, we only have to show that

$$
\mathbb{P} \left( |N_{i,j} - V_j \bar{N}_i| \ge R_{i,j} \right) = \tilde{\mathcal{O}} \left( \max_{(i^*,j^*) \in \mathcal{A}} \mathbb{P} (N_{i^*,j^*} \ne 0) + 2^{-n} \right). \quad (79)
$$

We prove the previous equality for each cases: $(i,j) \in \mathcal{A}$ or $(i,j) \notin \mathcal{A}$, where recall that

$$
\mathcal{A} \stackrel{\text{def}}{=} \left\{ (i,j) \in [0, n-s] \times [0, s], \left| \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)} \right| \le n^{3.2} \right\}.
$$

Cases 1: Here we suppose that (i, j) ∈ 𝒜. Let us prove Equation (79). Using the law of total probability we have that

$$
\mathbb{P}(|N_{i,j} - V_j \bar{N}_i| \ge R_{i,j}) \le \mathbb{P}(N_{i,j} \ne 0) + \mathbb{P}(|N_{i,j} - V_j \bar{N}_i| \ge R_{i,j}, N_{i,j} = 0).
$$

As $(i,j) \in \mathcal{A}$,

$$
\mathbb{P}(N_{i,j} \neq 0) = \tilde{\mathcal{O}} \left( \max_{(i^*,j^*) \in \mathcal{A}} \mathbb{P}(N_{i^*,j^*} \neq 0) \right)
$$

we only have left to show that:

$$
\mathbb{P} \left( |N_{i,j} - V_j \bar{N}_i| \ge R_{i,j}, N_{i,j} = 0 \right) = \tilde{\mathcal{O}} \left( \max_{(i^*,j^*) \in \mathcal{A}} \mathbb{P} \left( N_{i^*,j^*} \neq 0 \right) + 2^{-n} \right).
$$

We now show the previous equation, by proving that,

$$
\mathbb{P}(|N_{i,j} - V_j \bar{N}_i| \ge R_{i,j}, N_{i,j} = 0) = \tilde{\mathcal{O}}(2^{-n}). \quad (80)
$$
We have:

$$
\begin{align*}
\mathbb{P}(|N_{i,j} - V_j \overline{N_i}| \ge R_{i,j}, N_{i,j} = 0) &= \mathbb{P}(V_j \overline{N_i} \ge R_{i,j}) \quad (\text{we used that } V_j, \overline{N_i} > 0) \\
&= \mathbb{P}\left(V_j \ge \frac{R_{i,j}}{\overline{N_i}}\right) \\
&= \mathbb{P}\left(V_j - \overline{V}_j \ge \frac{R_{i,j}}{\overline{N_i}} - \overline{V}_j\right) \\
&\le \mathbb{P}\left(|V_j - \overline{V}_j| \ge \frac{R_{i,j}}{\overline{N_i}} - \overline{V}_j\right).
\end{align*}
$$

Recall that from Equation (71) of Conjecture 2 we have that

$$
\mathbb{P}_{C_{\text{aux}}, \mathbf{x}} \left( |V_j - \bar{V}_j| > n^{1.1} \max \left( \sqrt{\bar{V}_j}, 1 \right) \right) = \tilde{O}(2^{-n}).
$$

Therefore, we only have to show that for *n* big enough we have

$$
\frac{R_{i,j}}{\overline{N_i}} - \overline{V_j} \ge n^{1.1} \max \left( \sqrt{\overline{V_j}}, 1 \right) \quad (81)
$$

to prove Equation (80). Let us prove Equation (81). By definition of $R_{i,j}$ in Equation (78) and using Lemma 12 we have that

$$
\begin{align}
R_{i,j}^2 &= \frac{1}{4(n+1)^4} \left( \frac{K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{aux}}^{(s)}(j)} \right)^2 \nonumber \\
&= \frac{1}{4(n+1)^4} \omega(n^{\alpha+8}) \overline{N}_i \max \left( \overline{V}_j, \frac{1}{\mathcal{O}(n^\alpha)} \right) \nonumber \\
&= f(n) \max \left( \overline{N}_i \overline{V}_j, n^{-\alpha} \overline{N}_i \right) \tag{82}
\end{align}
$$

where $f(n) = \omega(n^{\alpha+4})$. Therefore,

$$
\begin{align*}
\frac{R_{i,j}^2}{\overline{N_i}^2} \frac{1}{n^{2.4} \max(\overline{V}_j^2, 1)} &= \frac{f(n) \max(\overline{N_i} \overline{V}_j, n^{-\alpha} \overline{N_i})}{n^{2.4} \overline{N_i}^2 \max(\overline{V}_j^2, 1)} \\
&= \frac{f(n) \max\left(\frac{\overline{V}_i}{\overline{N_i}}, \frac{n^{-\alpha}}{\overline{N_i}}\right)}{n^{2.4} \max(\overline{V}_j^2, 1)} \\
&= \begin{cases} \frac{1}{n^{2.4}} f(n) \max\left(\frac{1}{\overline{N_i} \overline{V}_j}, \frac{n^{-\alpha}}{\overline{N_i} \overline{V}_j^2}\right) & \text{if } \overline{V}_j > 1 \\ \frac{1}{n^{2.4}} f(n) \max\left(\frac{\overline{V}_j}{\overline{N_i}}, \frac{n^{-\alpha}}{\overline{N_i}}\right) & \text{if } \overline{V}_j \le 1 \end{cases} \\
&\ge \frac{1}{n^{2.4}} f(n) \min\left(\frac{1}{\overline{N_i} \overline{V}_j}, \frac{n^{-\alpha}}{\overline{N_i}}\right) \\
&\ge \frac{n^{-2\alpha}}{n^{2.4}} f(n) \min\left(\frac{1}{\overline{N_i} \overline{V}_j}, \frac{1}{n^{-\alpha} \overline{N_i}}\right) \\
&= \frac{n^{-2\alpha}}{n^{2.4}} \frac{f(n)}{\max(\overline{N_i} \overline{V}_j, n^{-\alpha} \overline{N_i})} \\
&= \frac{n^{-2\alpha}}{n^{2.4}} \frac{f(n)^2}{R_{i,j}^2} \quad \text{(By Equation (82))} \\
&= \frac{\omega(n^{5.6})}{R_{i,j}^2} \quad (f(n) = \omega(n^{\alpha+4})) \\
&= \omega(1) \tag{83}
\end{align*}
$$
where in the last line we used the fact that $(i,j) \in \mathcal{A}$: by definition,

$$R_{i,j} = \frac{1}{2(n+1)^2} \left| \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)} \right| \le \frac{1}{2(n+1)^2} n^{3.2}$$

and thus

$$\frac{1}{R_{i,j}^2} \ge \frac{2 (n+1)^2}{n^{3.2}}.$$

Finally, Equation (83) shows that for $n$ big enough

$$\frac{R_{i,j}}{\overline{N_i}} \ge n^{1.2} \max(\overline{V_j}, 1)$$

And as such, for $n$ big enough

$$\frac{R_{i,j}}{\overline{N_i}} - \overline{V_j} \ge n^{1.1} \max(\overline{V_j}, 1) \\ \ge n^{1.1} \max(\sqrt{\overline{V_j}}, 1)$$

which proves Equation (81). Therefore we have just proved Equation (79) in the case where $(i,j) \in \mathcal{A}$.

**Case 2:** Here we suppose that $(i,j) \notin \mathcal{A}$. Let us prove Equation (79). We only have to prove that:

$$\mathbb{P}(|N_{i,j} - V_j \overline{N_i}| \ge R_{i,j}) = \tilde{\mathcal{O}}(2^{-n}).$$

Let $M$ be defined as

$$M \stackrel{\text{def}}{=} \overline{V_j} + n^{1.1} \max \left( \sqrt{\overline{V_j}}, 1 \right). \qquad (84)$$

By the law of total probability we have that

$$\mathbb{P}_{C, C_{\text{aux}}, \mathbf{x}}(|N_{i,j} - V_j \overline{N_i}| > R_{i,j}) = \mathbb{P}(|N_{i,j} - V_j \overline{N_i}| > R_{i,j} | V_j > M) \mathbb{P}(V_j > M) + \sum_{v=0}^{M} \mathbb{P}(|N_{i,j} - V_j \overline{N_i}| > R_{i,j} | V_j = v) \mathbb{P}(V_j = v).$$

Which we can upper bound by

$$\mathbb{P}_{C, C_{\text{aux}}, \mathbf{x}}(|N_{i,j} - V_j \overline{N_i}| > R_{i,j}) \le \mathbb{P}(V_j > M) + \max_{v=0 \dots M} \mathbb{P}(|N_{i,j} - v \overline{N_i}| > R_{i,j} | V_j = v).$$

By definition of $M$ in Equation (84) and using Equation (71) of Conjecture 2 we get that

$$\mathbb{P}(V_j > M) = \tilde{\mathcal{O}}(2^{-n}).$$

Now, we only have left to prove that for any $v \in [0, M]$ we have

$$\mathbb{P}(|N_{i,j} - v \overline{N_i}| > R_{i,j} | V_j = v) = \tilde{\mathcal{O}}(2^{-n}).$$

Let us consider $v \in [0, M]$. Let us first show that for $n$ big enough we have that

$$n^{1.1} \max \left( \sqrt{v \overline{N_i}}, 1 \right) \le R_{i,j}. \qquad (85)$$

We have

$$\begin{align*}
n^{2.2} \max(v \overline{N_i}, 1) &\le n^{2.2} \max(M \overline{N_i}, 1) \\
&\le n^{2.2} \max\left(\overline{V_j} \overline{N_i} + n^{1.1} \overline{N_i} \max\left(\sqrt{\overline{V_j}}, 1\right), 1\right) \quad (\text{Using Equation (84)}) \\
&\le \max\left(2 n^{2.2} \overline{V_j} \overline{N_i}, 2 n^{3.3} \overline{N_i} \sqrt{\overline{V_j}}, 2 n^{3.3} \overline{N_i}, n^{2.2}\right)
\end{align*}$$
To show Equation (85), ne only have left to prove that, for $n$ big enough, each term in the previous maximum is smaller than $R_{i,j}^2$. First let us recall that by definition of $R_{i,j}$ in Equation (78) and from Lemma 12,

$$R_{i,j}^2 = \max(\omega(n^{\alpha+4}) \overline{N_i} \overline{V_j}, \omega(n^4) \overline{N_i}).$$

For $n$ big enough we have that:

$$2 n^{2.2} \overline{V_j} \overline{N_i} \le n^{\alpha+4} \overline{N_i} \overline{V_j} \le R_{i,j}^2,$$

$$2 n^{3.3} \overline{N_i} \sqrt{\overline{V_j}} \le \begin{cases} n^4 \overline{N_i} \le R_{i,j}^2 & \text{when } \overline{V_j} \le 1 \\ n^{\alpha+4} \overline{N_i} \overline{V_j} \le R_{i,j}^2 & \text{when } \overline{V_j} > 1 \end{cases},$$

$$2 n^{3.3} \overline{N_i} \le n^4 \overline{N_i} \le R_{i,j}^2,$$

$$n^{2.2} \le R_{i,j}^2.$$

Where in the last equation we used the fact that $(i, j) \notin \mathcal{A}$, thus $R_{i,j} \ge \frac{n^{3.2}}{2(n+1)^2}$ and thus $R_{i,j}^2 \ge n^{2.3}$ for $n$ big enough. We have shown that

$$n^{2.2} \max(v \overline{N_i}, 1) \le R_{i,j}^2$$

and thus we have shown Equation (85). Finally we have

$$\mathbb{P}(|N_{i,j} - V_j \overline{N_i}| > R_{i,j} | V_j = v) = \mathcal{O}\left(\mathbb{P}\left(|N_{i,j} - V_j \overline{N_i}| > n^{1.1} \max\left(\sqrt{v \overline{N_i}}, 1\right) | V_j = v\right)\right) \\ = \tilde{\mathcal{O}}(2^{-n})$$

where in the last line we used Equation (72) of Conjecture 2. This concludes the proof. $\square$

**Lemma 13.** *The Poisson Model 1 imply Conjecture 2.*

*Proof.* Let $M$ be defined as

$$M \stackrel{\text{def}}{=} \overline{V_j} + n^{1.1} \max\left(\sqrt{\overline{V_j}}, 1\right) \qquad (86)$$

Recall that to show Conjecture 2 we only have to show that

$$\mathbb{P}_{C_{\text{aux}}, \mathbf{x}}\left( |V_j - \overline{V_j}| \ge n^{1.1} \max\left(\sqrt{\overline{V_j}}, 1\right) \right) = \tilde{\mathcal{O}}(2^{-n}), \quad (87)$$

$$\forall v \in [0, M], \quad \mathbb{P}_{C, C_{\text{aux}}, \mathbf{x}}\left( |N_{i,j} - v \overline{N_i}| > n^{1.1} \max\left(\sqrt{v \overline{N_i}}, 1\right) \mid N_j = v \right) = \tilde{\mathcal{O}}(2^{-n}) \quad (88)$$

Under the Poisson Model 1 we have that

$$N_{i,j} \sim \text{Poisson}(V_j \overline{N_i}), \quad V_j \sim \text{Poisson}(\overline{V_j}).$$

We will use the following fact: when $\mathbf{X}$ follows a Poisson distribution of parameter $\lambda$ and $g(n) = \omega(n)$, then we have that

$$\mathbb{P}(|\mathbf{X} - \lambda| > g(n) \max(\sqrt{\lambda}, 1)) = 2^{-\omega(n)}. \qquad (89)$$

Let us prove this claim. It is known [Gol17, Prop 11.15] that we have the following exponential tail bound for $\mathbf{X}$:

$$\mathbb{P}(|\mathbf{X} - \lambda| > r) \le 2 e^{\frac{-r^2}{2(\lambda+r)}}.$$

Thus,

$$\mathbb{P}(|\mathbf{X} - \lambda| > g(n) \max(\sqrt{\lambda}, 1)) \le 2 e^{\frac{-g(n)^2 \max(\lambda, 1)}{2(\lambda + g(n) \max(\sqrt{\lambda}, 1))}} \\ \le 2 e^{\frac{-g(n)}{2 \left( \frac{\lambda + g(n) \max(\sqrt{\lambda}, 1)}{g(n) \max(\lambda, 1)} \right)}}.$$

We only have left to show that

$$\frac{\lambda + g(n) \max(\sqrt{\lambda}, 1)}{g(n) \max(\lambda, 1)} = \mathcal{O}(1).$$
First it is readily seen that we have that $(g(n) = \omega(n))$

$$ \frac{\lambda}{g(n) \max(\lambda, 1)} = \mathcal{O}(1), $$

and second,

$$ \frac{g(n) \max(\sqrt{\lambda}, 1)}{g(n) \max(\lambda, 1)} = \begin{cases} 1 = \mathcal{O}(1) & \text{if } \lambda \le 1 \\ \frac{1}{\sqrt{\lambda}} = \mathcal{O}(1) & \text{if } \lambda > 1. \end{cases} $$

which concludes the proof of Equation (89). Equation (87) directly follows from Equation (89). Equation (88) also directly follows from Equation (89) by noticing that $N_{i,j} = v \sim \text{Poisson}(v N_i)$ when $V_j = v$. $\square$

*Proof of Proposition 6.* Apply successively Lemma 13 and Proposition 12. $\square$

## APPENDIX G. INSTANTIATING THE AUXILIARY CODE $C_{\text{aux}}$ WITH AN EFFICIENT DECODER

We use here notation from §7. In particular, we suppose the auxiliary code $C_{\text{aux}}$ is a product of $b$ small random codes where

$$ b = \Theta(\log n). \qquad (90) $$

We have to show that for such $b$, the analyses from Propositions 2 and 5 still hold. Indeed, these analyses were done as if $C_{\text{aux}}$ were a random code equipped with genie aided decoders. Here we compute $\mathcal{H}$ as a subset of

$$ \tilde{\mathcal{H}} \subseteq \{ (\mathbf{h}, \mathbf{c}_{\text{aux}}) \in \mathcal{C}^{\perp} \times \mathcal{C}_{\text{aux}} : \forall i \in [1, b], |\mathbf{h}_{\mathcal{N}}(i)| = \frac{w}{b} \text{ and } |\mathbf{h}_{\mathcal{P}}(i) + \mathbf{c}_i| = \frac{t_{\text{aux}}}{b} \} $$

by decoding each parity-check performing an exhaustive search on each block. We have therefore to show that in this case,

i. the bias

$$ \text{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{s}{\leftarrow} \mathcal{H}} \left( \langle \mathbf{c}_{\text{aux}} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \right) $$

is of the same order as that given by Proposition 2,

ii. and the number of candidates to test

$$ \mathbb{E}_{\mathcal{C}, \mathcal{C}_{\text{aux}}}(|\mathcal{S}|) $$

is of the same order as that given by Proposition 5.

To prove item i., we first suppose that $\mathbf{e}_{\mathcal{P}}$ and $\mathbf{e}_{\mathcal{N}}$ have a weight which is fairly distributed, that is:

$$ \forall i \in [1, b], |\mathbf{e}_{\mathcal{P}}(i)| = \frac{t-u}{b} \text{ and } |\mathbf{e}_{\mathcal{N}}(i)| = \frac{u}{b}. \qquad (91) $$

This happens with a probability:

$$ \mathbb{P}_{\text{succ}} = \frac{\binom{s/b}{(t-u)/b} \binom{b}{u/b} \binom{(n-s)/b}{u/b}}{\binom{s}{t-u} \binom{n-s}{u}} = \Omega\left(n \left(\frac{b}{cn}\right)^b\right) \qquad (92) $$

where $c$ is constant in $n$. So we only need to iterate the whole double-RLPN algorithm a sub-exponential number of times, namely at most $\frac{1}{\mathbb{P}_{\text{succ}}}$ times. Note that (91) is not a necessary condition to achieve our decoding so this overcost is overestimated.

Now, assuming Condition (91), then we can see the bias above as the product of $b$ independent biases involving smaller vectors. More formally, we have

$$ \text{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{s}{\leftarrow} \mathcal{H}} \left( \langle \mathbf{c}_{\text{aux}} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \right) = \prod_{i=1}^{b} \text{bias}_{(\mathbf{h}(i), \mathbf{c}_{\text{aux}}(i)) \stackrel{s}{\leftarrow} \tilde{\mathcal{H}}_i} \left( \langle \mathbf{c}_{\text{aux}}(i) + \mathbf{h}_{\mathcal{P}}(i), \mathbf{e}_{\mathcal{P}}(i) \rangle + \langle \mathbf{e}_{\mathcal{N}}(i), \mathbf{h}_{\mathcal{N}}(i) \rangle \right) \qquad (93) $$

where

$$ \tilde{\mathcal{H}}_i^{\text{def}} = \left\{ (\mathbf{h}_{\mathcal{P}}(i), \mathbf{h}_{\mathcal{N}}(i), \mathbf{c}_{\text{aux}}(i)) \in (\mathcal{C}_{\mathcal{P}(i) \cup \mathcal{N}(i)})^{\perp} \times \mathcal{C}_i : |\mathbf{h}_{\mathcal{N}}(i)| = \frac{w}{b} \text{ and } |\mathbf{h}_{\mathcal{P}}(i) + \mathbf{c}_i| = \frac{t_{\text{aux}}}{b} \right\} \qquad (94) $$
Moreover, let us degrade the Constraints (7) of Proposition 2 by replacing the polynomial factor $n^\alpha$ by a super-polynomial

$$A \stackrel{\text{def}}{=} \frac{n^{\alpha-1+\log(c)+\log(n)}}{\log(n)^{\log(n)}}. \qquad (95)$$

On the one hand, this super-polynomial factor is multiplied to the final complexity, but on the other hand the new constraint (with the original one (8)) induces:

$$\frac{\binom{(n-s)/b}{w/b} \binom{s/b}{t_{\text{aux}}/b}}{2^{k-k_{\text{aux}}}/b} = \omega\left(\frac{n^{\alpha/\log(n)}}{\delta^{2/\log(n)}}\right) \qquad (96)$$

and

$$\frac{\binom{(n-s)/b}{w/b} \binom{s/b}{t_{\text{aux}}/b}}{2^{k/b}} = \mathcal{O}\left(n^{\alpha/\log(n)}\right) \quad \text{and} \quad \frac{\binom{s/b}{t_{\text{aux}}/b}}{2^{(s-k_{\text{aux}})/b}} = \mathcal{O}\left(n^{\alpha/\log(n)}\right). \qquad (97)$$

Which allows us to say, using Proposition 2, that for all $i \in [1, b]$ and for a proportion $1-o(1)$ of codes $C_i$ and $C_{\mathcal{P}(i) \cup \mathcal{N}(i)}$:

$$\text{bias}_{(\mathbf{h}(i), \mathbf{c}_{\text{aux}}(i)) \stackrel{\$}{\leftarrow} \mathcal{H}_i} \left( \langle \mathbf{c}_{\text{aux}}(i) + \mathbf{h}_{\mathcal{P}}(i), \mathbf{e}_{\mathcal{P}}(i) \rangle + \langle \mathbf{e}_{\mathcal{N}}(i), \mathbf{h}_{\mathcal{N}}(i) \rangle \right) = \delta^{1/\log(n)}(1-o(1)). \qquad (98)$$

By specifying the values of both $o(1)$ (see proof of Proposition 2 in Appendix A), we can deduce that i. is verified.

To verify item ii., we can adapt Section D to show that

$$\mathbb{E}_{C, \mathcal{C}_{\text{aux}}}(|\mathcal{S}|) = \tilde{\mathcal{O}}\left(\max_{(i,j) \in \mathcal{A}} \frac{\binom{s/b}{j}^b \binom{(n-s)/b}{i}}{2^{n-k}}\right) + 1 \qquad (99)$$

where

$$\mathcal{A} \stackrel{\text{def}}{=} \left\{ (i, j) \in [0, \frac{n-s}{b}] \times [0, \frac{s}{b}] , \frac{K_{w/b}^{((n-s)/b)}(u/b) K_{t_{\text{aux}}/b}^{(s/b)}((t-u)/b)}{K_{w/b}^{((n-s)/b)}(i) K_{t_{\text{aux}}/b}^{(s/b)}(j)} \le n^{2/b} \right\}, \qquad (100)$$

$$\mathcal{S} \stackrel{\text{def}}{=} \{ \mathbf{s} \in \mathbb{F}_2^{k_{\text{aux}}} : f_{\mathbf{y}, \tilde{\mathcal{H}}, \mathcal{G}_{\text{aux}}} (\mathbf{s}) \ge \frac{\delta}{2} \tilde{H} \}, \qquad (101)$$

and

$$\tilde{H} \stackrel{\text{def}}{=} \frac{\binom{(n-s)/b}{w/b} \binom{s/b}{t_{\text{aux}}/b}^b}{2^{k-k_{\text{aux}}}}. \qquad (102)$$

Finally, up to a sub-exponential factor, the above expectation is of the same order as in Proposition 5.

# APPENDIX H. PROOFS OF THE STATEMENTS MADE IN SECTION 8

## Proof of Proposition 7

**Proposition 7.** Consider a lattice $\Lambda \subseteq \mathbb{R}^n$ and consider some word $\mathbf{y} = \mathbf{x} + \mathbf{e} \in \mathbb{R}^n$ where $\mathbf{x}$ is in $\Lambda$. Let $\tilde{\mathcal{W}}$ be the set of dual lattice vectors of Euclidean weights in $(w - \varepsilon, w + \varepsilon)$ in $\Lambda^\vee$ and let $f_{\tilde{\mathcal{W}}}(\mathbf{y}) \stackrel{\text{def}}{=} \sum_{\mathbf{w} \in \tilde{\mathcal{W}}} \cos(2\pi \langle \mathbf{x}, \mathbf{y} \rangle)$. We have

$$f_{\tilde{\mathcal{W}}}(\mathbf{y}) = \frac{1}{|\Lambda^\vee|} \sum_{j \ge 0} \frac{N_j}{j^n (2\pi)^{n/2}} \left( (2\pi(w+\varepsilon)j)^{n/2} J_{n/2}(2\pi(w+\varepsilon)j) - (2\pi(w-\varepsilon)j)^{n/2} J_{n/2}(2\pi(w-\varepsilon)j) \right) \qquad (17)$$

where $N_j$ is the number of words of Euclidean norm $j$ in $\Lambda + \mathbf{e}$ and $J_\nu$ is the Bessel function of the first kind of order$^4 \nu$.

<footnote>$^4$Here the $j$'s belong to the discrete set of all possible norms in the lattice and should not be viewed as an integer value.</footnote>
It is helpful to notice before the following link between the Bessel functions and the Fourier transform of the indicator function $1_{\le w}$ of the words of Euclidean norm $\le w$ in $\mathbb{R}^n$ (see [DDRT23, Fact 4.11])

**Lemma 14.** We have for any positive integer $n$, any $w \ge 0$, any $\mathbf{x}$ in $\mathbb{R}^n$

$$ \widehat{1_{\le w}}(\mathbf{x}) = \left( \frac{w}{\|\mathbf{x}\|_2} \right)^{n/2} J_{n/2} (2\pi w \|\mathbf{x}\|_2) $$

where $\widehat{f}(\mathbf{x}) = \int_{\mathbb{R}^n} f(\mathbf{x})e^{-2i\pi\langle\mathbf{x},\mathbf{y}\rangle} d\mathbf{y}$ for $f: \mathbb{R}^n \to \mathbb{C}$.

*Proof of Proposition 7.* First, notice that,

$$ \begin{aligned} f_{\tilde{\mathcal{W}}}(\mathbf{y}) &= \frac{1}{2} \sum_{\mathbf{w} \in \tilde{\mathcal{W}}} \left( e^{2i\pi\langle\mathbf{w}, \mathbf{y}\rangle} + e^{-2i\pi\langle\mathbf{x}, \mathbf{y}\rangle} \right) \\ &= \sum_{\mathbf{w} \in \tilde{\mathcal{W}}} e^{-2i\pi\langle\mathbf{w}, \mathbf{y}\rangle} \quad (\mathbf{w} \mapsto -\mathbf{w} \text{ is a bijection in } \tilde{\mathcal{W}}) \\ &= \sum_{\mathbf{w} \in \Lambda^{\vee}} (1_{\le w+\varepsilon}(\mathbf{w}) - 1_{\le w-\varepsilon}(\mathbf{w})) e^{-2i\pi\langle\mathbf{w}, \mathbf{y}\rangle} \end{aligned} \quad (103) $$

Recall now the Poisson summation formula, for any $\mathbf{y} \in \Lambda + \mathbf{e}$ and sufficiently regular function $f$,

$$ \sum_{\mathbf{x} \in \Lambda^{\vee}} f(\mathbf{x}) e^{-2i\pi \langle \mathbf{x}, \mathbf{y} \rangle} = \frac{1}{|\Lambda^{\vee}|} \sum_{\mathbf{x} \in \Lambda + \mathbf{e}} \hat{f}(\mathbf{x}) $$

Plugging this formula into Equation (103) yields to,

$$ \begin{aligned} f_{\tilde{\mathcal{W}}}(\mathbf{y}) &= \frac{1}{|\Lambda^{\vee}|} \sum_{\mathbf{x} \in \Lambda + \mathbf{e}} \left( \widehat{1_{\le w+\varepsilon}}(\mathbf{x}) - \widehat{1_{\le w-\varepsilon}}(\mathbf{x}) \right) \\ &= \frac{1}{|\Lambda^{\vee}|} \sum_{j \ge 0} \frac{N_j}{j^{n/2}} \left( (w+\varepsilon)^{n/2} J_{n/2}(2\pi(w+\varepsilon)j) - (w-\varepsilon)^{n/2} J_{n/2}(2\pi(w-\varepsilon)j) \right) \\ &= \frac{1}{|\Lambda^{\vee}|} \sum_{j \ge 0} \frac{N_j}{(2\pi)^{n/2} j^n} \left( (2\pi(w+\varepsilon)j)^{n/2} J_{n/2}(2\pi(w+\varepsilon)j) \right. \\ & \qquad \left. - (2\pi(w-\varepsilon)j)^{n/2} J_{n/2}(2\pi(w-\varepsilon)j) \right) \end{aligned} \quad (104) $$

which concludes the proof. $\square$

**An Approximation.** We have also an approximate form for $f_{\tilde{\mathcal{W}}}(\mathbf{y})$ which is given by

$$ f_{\tilde{\mathcal{W}}}(\mathbf{y}) \approx \frac{4\pi\varepsilon}{|\Lambda^{\vee}|} \sum_{j \ge 0} j N_j \left( \frac{w}{j} \right)^{n/2} J_{n/2-1}(2\pi w j). \quad (105) $$

This follows from the fact that

$$ \frac{d}{dx} \left( x^{n/2} J_{n/2}(x) \right) = x^{n/2} J_{n/2-1}(x). \quad (106) $$

Let,

$$ X \stackrel{\text{def}}{=} 2\pi w j \quad \text{and} \quad h \stackrel{\text{def}}{=} 2\pi \varepsilon j $$

Notice that,

$$ \begin{aligned} & \left( (2\pi(w+\varepsilon)j)^{n/2} J_{n/2}(2\pi(w+\varepsilon)j) - (2\pi(w-\varepsilon)j)^{n/2} J_{n/2}(2\pi(w-\varepsilon)j) \right) \\ & = (X+h)^{n/2} J_{n/2}(X+h) - (X-h)^{n/2} J_{n/2}(X-h) \end{aligned} $$
From Equation (106),

$$
\begin{align*}
(X+h)^{n/2} J_{n/2}(X+h) - (X-h)^{n/2} J_{n/2}(X-h) &\approx 2h \frac{d}{dX} (X^{n/2} J_{n/2}(X)) \\
&= 2h X^{n/2} J_{n/2-1}(X) \\
&= (4\pi\epsilon j) (2\pi wj)^{n/2} J_{n/2-1}(2\pi wj)
\end{align*}
$$

Plugging this into Equation (104) yields (105).

We also recall that we make the approximation

$$
f_{\mathcal{W}}(\mathbf{y}) \approx \frac{N}{|\tilde{\mathcal{W}}|} f_{\tilde{\mathcal{W}}}(\mathbf{y}) \qquad (107)
$$

The number $N_{\le x}^{\vee}$ of dual vectors of length $\le x$ can be approximated using the Gaussian heuristic:

$$
N_{\le x}^{\vee} \approx \frac{x^n}{\sqrt{n\pi} \left(\frac{n}{2\pi e}\right)^{n/2}} \frac{1}{|\Lambda^{\vee}|}
$$

Thus we have:

$$
|\tilde{\mathcal{W}}| = N_{\le w+\epsilon}^{\vee} - N_{\le w-\epsilon}^{\vee} \approx \frac{(w+\epsilon)^n - (w-\epsilon)^n}{\sqrt{\frac{n}{2\pi e}} \cdot \sqrt{\pi n} \cdot |\Lambda^{\vee}|} \approx \frac{2n\epsilon w^{n-1}}{\sqrt{\frac{n}{2\pi e}} \sqrt{\pi n} |\Lambda^{\vee}|}
$$

Putting this into Equation (107) shows,

$$
f_{\mathcal{W}}(\mathbf{y}) \approx N \frac{|\Lambda^{\vee}| \sqrt{n\pi} \left(\frac{n}{2\pi e}\right)^{n/2}}{2n\epsilon w^{n-1}} f_{\tilde{\mathcal{W}}}(\mathbf{y})
$$

and after some further computation

$$
\begin{align*}
f_{\mathcal{W}}(\mathbf{y}) &\approx N \left|\Lambda^{\vee}\right| \frac{\sqrt{n\pi} \left(\frac{n}{2\pi e}\right)^{n/2}}{2n\epsilon w^{n-1}} \frac{4\pi\epsilon}{\left|\Lambda^{\vee}\right|} \sum_{j \ge 0} j N_j \left(\frac{w}{j}\right)^{n/2} J_{n/2-1}(2\pi w j) \\
&= N \frac{\sqrt{n\pi}}{2nw^{n-1}} \left(\frac{n}{2\pi e}\right)^{n/2} 4\pi \sum_{j \ge 0} j N_j \left(\frac{w}{j}\right)^{n/2} J_{n/2-1}(2\pi w j) \\
&= N \frac{\sqrt{n} n^{n/2}}{n} \frac{1}{w^{n-1}} \frac{\sqrt{\pi} \pi}{\pi^{n/2}} \frac{4}{2 2^{n/2}} \frac{1}{e^{n/2}} \sum_{j \ge 0} N_j w^{n/2} \frac{1}{j^{n/2-1}} J_{n/2-1}(2\pi w j) \\
&= N \sqrt{n} \sqrt{\pi} e^{-1} n^{n/2-1} \pi^{-(n/2-1)} 2^{-(n/2-1)} e^{-(n/2-1)} \sum_{j \ge 0} N_j \left(\frac{1}{wj}\right)^{n/2-1} J_{n/2-1}(2\pi w j) \\
&= N \frac{\sqrt{n\pi}}{e} \sum_{j \ge 0} N_j \left(\frac{n}{2\pi ewj}\right)^{n/2-1} J_{n/2-1}(2\pi w j)
\end{align*}
$$