Paper 2026/1075

Asymptotically Optimal Distance-Tail Bounds for Large-Field RAA Codes

Abstract

Repeat-accumulate-accumulate (RAA) codes combine a very simple linear-time encoding procedure with strong distance behavior, making them attractive both in classical coding theory and in recent cryptographic applications such as code-based polynomial commitments, zkSNARKs, and pseudorandom correlation generators. Existing concrete analyses of RAA codes are strongest over the binary field, while large-field cryptographic applications require distance guarantees over fields whose size grows with the block length. In this regime, the usual binary-field weight-enumerator and union-bound arguments lose the large-field cancellation gains needed to obtain sharp tails. We give a gap-covering proof of an optimal-tail distance bound for the large-field RAA ensemble \(G=RP_1AP_2A\). For every fixed repetition factor $r\ge9$ and every field size satisfying $q-1\ge(eN)^2$, we prove \[ Pr[d_{\min}(G)\le \delta N]\le \widetilde O_r(N^{1-r}) \] for every fixed $0<\delta<1/2$, where $N$ denotes the code length. We also prove the matching large-field lower bound $\Omega_r(N^{1-r})$, showing that the upper bound is optimal up to polylogarithmic factors. In addition, we prove a binary-field companion lower bound. In particular, for every fixed $0<\delta<1/2$ and even $r$, \[ Pr[d_{\min}(G)\le \delta N] \ge c_{r,\delta}N^{1-r/2}. \] For even $r$, together with the improved binary upper bound in the literature, this identifies the binary tail up to polylogarithmic factors, while our large-field result gives the tight tail $\widetilde\Theta_r(N^{1-r})$. Thus the binary and large-field RAA ensembles have genuinely different low-distance tail exponents: the large-field improvement is an actual polynomial separation, not merely a separation between available proof techniques. We also record two complementary obstructions clarifying the role of the large-field assumptions. If \(q-1=N^\gamma\) with \(0\le\gamma<1\), then weight-one paired cancellations give a lower bound with polynomial exponent strictly larger than \(1-r\), so a sublinear field cannot support an \(N^{1-r}\)-order tail. If the random diagonal scalings are removed, then opposite-valued weight-two messages give low-distance events of order \(\Omega_{r,\delta}(N^{2-r})\), showing that the scalings are essential for the optimal large-field exponent.