Concatenation testing enforces the same decoded prefix

Define $J_j(r)$ by the stated coordinate insertion. Then $w\cdot J_j(r)={\sum }_{k=1}^n{w}_{j(k)}{r}_k=(w{\mathrm{\mid }}_j)\cdot r$ for every $r\in {\mathbb{F}}_2^n$. All query locations below are determined by $j$ and the sampled masks and offsets before any table answer is read.

Fix any mask $r$. In the short-table correction, each of $y$ and $y+r$ is uniform on ${\mathbb{F}}_2^n$. Each queried value therefore differs from its corresponding codeword value with probability exactly ${\delta }_1$. A union bound shows that the corrected short value differs from $a\cdot r$ with probability at most $2{\delta }_1$. Likewise $Y$ and $Y+J_j(r)$ are each uniform on ${\mathbb{F}}_2^N$, so the corrected long value differs from $w\cdot J_j(r)$ with probability at most $2{\delta }_2$. These bounds hold conditional on every fixed $r$ and require no independence between the two errors within either correction.

On the exact tables, the two queried bits are $a\cdot r$ and $(w{\mathrm{\mid }}_j)\cdot r$ by [F2] and step 1.1. Their sum is $(a+w{\mathrm{\mid }}_j)\cdot r$. If $a=w{\mathrm{\mid }}_j$, this is zero for every mask, so every raw check accepts. If $a\mathrm{\ne }w{\mathrm{\mid }}_j$, their sum vector is nonzero and [F3] gives probability exactly $1\mathrm{/}2$ that the two bits differ; hence exactly half the masks reject. This proves both directions of the asserted “accepts every mask iff” statement.

Suppose $a\mathrm{\ne }w{\mathrm{\mid }}_j$. By [F3] and step 1.1, the ideal corrected values $a\cdot r$ and $w\cdot J_j(r)$ differ with probability exactly $1\mathrm{/}2$. Conditional on each $r$, the probability that at least one corrected value is wrong is at most $2{\delta }_1+2{\delta }_2$ by step 1.2. Whenever the ideal values differ and neither correction errs, the actual test rejects. Subtracting the possible error event from the ideal disagreement event gives $\mathrm{Pr}[\text{reject}]\ge \frac{1}{2}-2{\delta }_1-2{\delta }_2\mathrm{.}$ This remains a valid lower bound if its right side is negative.

The raw test samples $n$ mask bits. The corrected test samples $r,y$ using $2n$ bits and $Y$ using $N$ bits, then makes the four queries listed in [F1]. Repeated query locations still count as calls, so the bounds hold for $n=0$ and for any coordinate coincidences. Since every query location is fixed before answers are obtained, both procedures are nonadaptive.

If $n=0$, both messages are the unique empty vector, $J_j(0)=0$, and $a=w{\mathrm{\mid }}_j$ necessarily; the differing-slice case cannot occur. The raw exact tables both have value $0$ at their zero mask. The self-corrected short value is $\pi (0)+\pi (0)=0$, so the definition still makes sense with the singleton mask and table. If also $N=0$, the long correction is likewise a repeated query at the singleton coordinate. No positive-dimension assumption is needed.

Steps 2.1 and 2.2 prove the exact and noisy rejection claims; step 2.3 proves the query, randomness, and nonadaptivity bounds, including repeated locations; step 3.1 handles the zero-dimensional slice. Therefore the raw check accepts every mask exactly when the decoded slices agree and otherwise rejects on half the masks, while the corrected check has the stated rejection lower bound whenever they differ.