Finite-Degree GV Certification Scripts and Constants

Certification Scripts

The certification of the 56 triples in \(T_{\mathrm{GV}}\) is produced by the following Python scripts.

• certify_finite_gv_triples.py: main rigorous computer-assisted proof script based on interval arithmetic and adaptive subdivision.
• build_full_finite_gv_tables.py: builds the full 56-row CSV and TeX tables from the certification results.
• export_finite_gv_proof_tables.py: exports the shorter paper tables from the certificate data.

Full 56-Row Constant Tables

The certified set \(T_{\mathrm{GV}}\) contains 56 triples in the scanned window. The full HA-side and MN-side constant tables for those 56 triples are rendered below from the downloadable CSV files.

The downloadable CSV files use machine-readable column names such as j_z and j_x, while the tables below display the notation used in the paper.

HA-Side Table

Columns: \((j_Z,j_X,k)\), \(j_Z\), \(j_X\), \(k\), \(\beta_Z\), \(\bar{\delta}\), \(\lambda_Z\), \(\varepsilon_Z\).

MN-Side Table

Columns: \((j_Z,j_X,k)\), \(j_Z\), \(j_X\), \(k\), \(\beta_X\), \(B_X\), \(\varepsilon_X\).

Downloads

How These Files Relate to the Paper

• The representative tables printed in Appendices D and E show sample certified rows only.
• This HTML page shows the full 56-row HA-side and MN-side tables for the certified set \(T_{\mathrm{GV}}\).
• This HTML page also provides the exact scripts used to certify those 56 triples and to generate the tables.
• The HA-side and MN-side CSV files still contain the full machine-readable data for all 56 certified triples in \(T_{\mathrm{GV}}\).
• The HA-side CSV records beta_z, delta_bar, lambda_z, and epsilon_z.
• The MN-side CSV records beta_x, B_x, and epsilon_x.
• The scan-status CSV records which triples in the search window are numerical GV matches and which ones are currently certified on the HA and MN sides.

Theory Behind the Constants

The constants in the two 56-row tables are not ad hoc numerical outputs. For each triple in \(T_{\mathrm{GV}}\), they are the certified parameters that remain after the analytic first-moment reductions in the paper.

The basic probabilistic framework is the first-moment method followed by Markov's inequality: for a target relative distance \(\delta<\delta_{\mathrm{GV}}\), one bounds the expected number of codewords or witnesses of weight at most \(\delta n\), and then shows that this expectation tends to zero. In the present paper, this reduction is carried out for the HA side in Section 3 and Appendix D, and for the MN side in Section 4 and Appendix E of arXiv:2603.24588.

HA-Side Constants

The HA-side constants \(\beta_Z\), \(\bar{\delta}\), \(\lambda_Z\), and \(\varepsilon_Z\) come from two different parts of the proof.

• The pair \((\beta_Z,\lambda_Z)\) controls the small-input region by a geometric bound on the outer enumerator. This is the finite-degree analogue of the HA weight-distribution analysis.
• The pair \((\bar{\delta},\varepsilon_Z)\) controls the compact strip after the visible exponent is reduced to the one-variable function \[ G_{Z,\delta}(\tau) = h(\tau)-\alpha_Z+\alpha_Z\log_2(1+(1-2\tau)^k) -D\!\left(\delta \middle\| \frac{1-(1-2\tau)^k}{2}\right). \] The certified inequality is \[ \sup_{\beta_Z/k \le \tau \le 0.49} G_{Z,\bar{\delta}}(\tau) \le -\varepsilon_Z. \]

MN-Side Constants

The MN-side constants \(\beta_X\), \(B_X\), and \(\varepsilon_X\) come from the low-weight decomposition of the refined witness enumerator.

• The pair \((\beta_X,B_X)\) controls the low-weight small-support regime through a geometric bound obtained from the pairing argument and Stirling/Vandermonde reductions.
• The margin \(\varepsilon_X\) controls the low-weight large-support regime after the trial exponent is reduced to \[ \Phi_{\mathrm{MN}}(a,b,\omega) = \alpha_Z h(a)+\alpha_{\Delta} h(b)+h(\omega)-1 +\log_2\!\bigl(1+\mu\,y_1^{j_Z}y_{\Delta}^{j_{\Delta}}\bigr), \] where \(y_1=|1-2a|\), \(y_{\Delta}=|1-2b|\), and \(\mu=|1-2\omega|^k\). The certified inequality is \[ \sup_{\substack{ 0 \le \omega \le \omega_*(k),\, 0 \le a,b \le 1/2\\ \max\{a,b\} \ge \beta_X/k }} \Phi_{\mathrm{MN}}(a,b,\omega) \le -\varepsilon_X. \]

Role of Validated Numerics

After the analytic reductions, the remaining task is to prove that the exponents above are uniformly negative on compact domains. This is done by validated numerics, more specifically interval arithmetic with adaptive subdivision. The domain is partitioned into finitely many boxes, an outward-rounded upper bound is computed on each box, and the worst box upper bound is shown to be negative. The numbers \(\varepsilon_Z\) and \(\varepsilon_X\) are exactly the certified negative margins obtained in this way.

References

• K. Kasai, “Finite-Degree Quantum LDPC Codes Reaching the Gilbert--Varshamov Bound,” arXiv:2603.24588. This is the paper to which the present tables correspond; see Sections 3--4 and Appendices D--E.
• C.-H. Hsu and A. Anastasopoulos, “Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels,” arXiv:cs/0509062. This is the original HA/LDPC-GM weight-distribution framework behind the HA-side exponent analysis.
• R. E. Moore, R. B. Kearfott, and M. J. Cloud, Introduction to Interval Analysis (2009), Google Books entry. Standard reference for interval arithmetic and validated bounds.
• W. Tucker, Validated Numerics: A Short Introduction to Rigorous Computations (2011), DOI link. Short introduction to rigorous computer-assisted proof via validated numerics.

Certified Constants and Inequalities

The scripts do not merely export tables; they certify the finite-domain inequalities that remain after the analytic first-moment reductions. The exported constants are the parameters appearing in those certified inequalities.

HA Side

The HA-side CSV finite_gv_ha_constants.csv records the columns beta_z, delta_bar, lambda_z, and epsilon_z.

For each certified triple, these constants are used to establish:

Here

In the proof, \(\lambda_Z < 1\) controls the small-input region, while \(\varepsilon_Z > 0\) provides a certified negative margin on the compact strip.

MN Side

The MN-side CSV finite_gv_mn_constants.csv records the columns beta_x, B_x, and epsilon_x.

For each certified triple, these constants are used to establish:

Here

In the proof, \(B_X < 1\) controls the low-weight small-support regime, while \(\varepsilon_X > 0\) provides a certified negative margin on the low-weight large-support regime.

Minimal Reproduction

From the repository root, the core workflow is:

python3 scripts/certify_finite_gv_triples.py
python3 scripts/build_full_finite_gv_tables.py

The proof scripts require mpmath. The minimal dependency list is provided in requirements-proof.txt.