Proximity Prize for Smooth Reed-Solomon Domains

This repository is a working research package for settling the smooth-domain Reed--Solomon mutual correlated agreement (MCA) and proximity-list questions that arise in the Proximity Prize program.

See the related IACR ePrint paper.

The central theme is simple:

Smooth multiplicative Reed--Solomon domains do not appear to have a clean “up to capacity with negligible error” theorem. They have a corrected reserve theory. Any near-capacity theorem must clear explicit entropy, quotient, field-accounting, list-size, and MCA/line-decoding floors.

The repo is meant for people and AI agents who want to help turn that corrected theory into proofs, counterexamples, parameter certificates, and eventually protocol-grade statements.

Repository contents

The core repo consists of four papers and two guide files. .tex versions are in tex folder, .pdf are in the root folder and Python scripts for heuristics are in scripts folder.

File	Short name	Role
RS_disproof_v3.tex	Paper A: no-slack obstruction	Refutes the unslacked, support-wise line-MCA reading of “up to capacity” for smooth multiplicative RS domains. Provides explicit lower-bound mechanisms and deployed-field obstructions.
slackMCA_v3.tex	Paper B: slack / quotient / entropy theory	Main theory paper. Builds the corrected reserve framework: locator fibers, generated-field entropy, quotient cores, slack bad-slope calculus, failure ladders, quotient floors, and final local-limit conjectures.
cs25_cap_v4.tex	Paper D: universal cap	Extracts and sharpens the cap result: conditional on the imported list-to-agreement conversion, gives a field-size-universal ceiling on the MCA challenge threshold.
snarks_v4.tex	Paper C: SNARK ledger	Turns the corrected theory into a protocol-facing certificate: field-separated ledgers, list-over-field budgets, MCA/line-decoding assumptions, dimension hygiene, and fallback modes.
README.md	Repo overview	Explains what the papers do, how they depend on each other, and what the project is trying to prove.
AGENTS.md	Research-agent guide	Gives AI agents and new contributors a prioritized list of proof targets, toy cases, scripts, and “do not confuse these” rules.

The paper-letter order follows the internal blueprint: A = no-slack, B = slack theory, C = SNARK ledger, D = universal cap. The logical reading order is usually A → B → D → C.

The problem we are trying to settle

Let C = RS[F, D, k], where D is a smooth multiplicative domain, usually a subgroup or multiplicative coset of power-of-two order n, and rho = k/n is one of

rho in {1/2, 1/4, 1/8, 1/16}.

The Proximity Prize regime asks for sharp thresholds near capacity, especially for target error

epsilon* = 2^-128,
k <= 2^40,
|F| < 2^256.

There are two linked threshold problems.

1. MCA / correlated-agreement threshold. Determine how close the radius delta can get to 1 - rho while the MCA error remains negligible.
2. Interleaved-list threshold. Determine how close delta can get to 1 - rho while the relevant interleaved list size is at most a negligible fraction of the challenge field.

These are protocol-relevant because many proximity/SNARK reductions have a soundness term schematically like

MCA_error(C, delta) + |interleaved_list(C, delta)| / |challenge field| + query_error.

A list theorem alone is not enough unless it is connected to the exact MCA, CA, line-decoding, or curve-MCA quantity used by the protocol.

Current picture

The old hoped-for statement was roughly:

Smooth-domain Reed--Solomon codes should behave well all the way up to capacity, provided the field is large enough.

The corrected picture is:

Smooth-domain Reed--Solomon codes have explicit near-capacity obstruction floors. A positive theorem must work at radius 1 - rho - eta, where eta clears every known floor and every protocol ledger.

The ledgers that must be separated are:

1. Generated-field entropy. The list/locator entropy denominator is the field generated by the domain and the received word, not automatically the large extension challenge field.
2. Quotient-core obstructions. Smooth domains have quotient fibers. If k and n align with large quotient scales, large lists or bad slopes can appear.
3. Locator-fiber list size. Base-code locator fibers must be bounded before they can be used in a protocol list budget.
4. Interleaved list size. The protocol often consumes |Lambda(Int(C, mu), delta)|, not merely the base-code list size.
5. Challenge-field division. The list term is divided by the field in which the verifier samples the relevant challenge. Do not silently replace this by a larger or smaller field.
6. MCA / CA / line-decoding / curve-MCA. These are related but not interchangeable without a theorem.
7. Known failure ladders and universal caps. Some gaps are ruled out by explicit lower bounds or by the universal cap.

How the papers fit together

Paper A: no-slack obstruction
        |
        v
Paper B: slack / entropy / quotient-core theory
        |\
        | \__ Paper D: universal cap via list-to-agreement conversion
        |
        v
Paper C: SNARK/protocol ledger consuming B and D

Paper A: no-slack obstruction

RS_disproof_v3.tex is the base lower-bound paper.

It shows that the no-slack, support-wise line-MCA version of the up-to-capacity conjecture is false for smooth multiplicative RS domains. The organizing mechanism is the quotient locator identity: restricted sums in a smooth quotient subgroup produce many bad slopes for lines of the form

x^(k+a) + z x^k.

The paper gives explicit consequences over common smooth prime fields such as BabyBear, KoalaBear, 3*2^30+1, and Fermat-prime examples. Its role in the repo is to be the lower-bound oracle: if a proposed theorem contradicts Paper A’s obstruction intervals, the theorem is false or missing a reserve hypothesis.

Paper B: slack / quotient / entropy theory

slackMCA_v3.tex is the main theory paper.

It generalizes the obstruction into a corrected positive/negative theory. It separates:

• generated-field entropy floors,
• quotient-core list obstructions,
• characteristic-zero rigidity and finite-field collision sieves,
• exact slack bad-slope calculus,
• dyadic descent and failure ladders,
• tangent and quotient-periodic MCA floors,
• residue-line normal forms,
• local-limit conjectures for list decoding and MCA.

Paper B is where most new mathematics should land. It contains the theorem/conjecture shape for a corrected reserve theorem: not “up to capacity,” but “up to capacity minus every explicit floor.”

Paper D: universal field-size cap

cs25_cap_v4.tex is a short cap paper.

It composes locator-fiber lower bounds with the imported Crites--Stewart list-to-agreement conversion. Conditional on that import, it proves a field-size-universal cap for the MCA challenge:

delta*_C(2^-128) <= 1 - rho - 2^-9      for rho in {1/2, 1/4, 1/8},
delta*_C(2^-128) <= 1 - rho - 2^-10     for rho = 1/16,

throughout the challenge range |F| < 2^256, with the stated smoothness/divisibility hypotheses. It gives error > 2^-86 uniformly and improves to > 2^-42 when |F| >= 2n.

Paper D supersedes the older internal cap in Paper B for final constants. Paper B keeps its native quotient-core cap because it explains the mechanism; Paper D owns the sharp field-size-universal statement.

Paper C: SNARK ledger

snarks_v4.tex turns the corrected theory into a protocol-facing reserve certificate.

Its purpose is not to prove all missing MCA/list theorems. Its purpose is to prevent protocol analyses from mixing ledgers. In particular, it insists on distinguishing:

• base field vs generated field vs extension challenge field,
• implementation interleaving vs protocol list arity,
• base-code lists vs interleaved lists,
• CA vs MCA vs line-decoding vs curve-MCA,
• theorem-backed mode vs conjectural aggressive mode vs obstruction-audit mode.

Paper C is the bridge from theory to systems. Once the missing local-limit and line/MCA statements are proved, Paper C should become a compiler from a code/domain tuple to a soundness certificate.

What is proved, conditional, and open

A rough status map:

Topic	Current status
No-slack smooth-domain MCA obstruction	Proved in Paper A.
Explicit deployed-field lower-bound floors	Proved in Paper A/B for the stated regimes.
Quotient-core list obstructions	Proved in Paper B.
Exact slack calculus and many failure ladders	Proved in Paper B.
Universal field-size cap	Conditional on the imported list-to-agreement conversion; Paper D is the clean reference.
Generated-field locator local limit above all floors	Open. Main list-side positive theorem target.
Corrected MCA / residue-line local limit above all floors	Open. Main MCA-side positive theorem target.
Line-decoding formulation of corrected MCA	Open. Important for protocols.
Extension-line MCA transfer	Open: prove a clean lift or find counterexamples.
Sharp interleaved-list constants near capacity	Open. Important for protocol soundness budgets.
Protocol-level FRI/WHIR ledger rewrites	Open engineering/proof task.
Certificate scanner	To be implemented.

How to contribute

Good first contributions include:

1. Proof audits. Verify individual lemmas and theorem dependencies in the four papers. Flag any hidden field-size, divisibility, monotonicity, or support-wise assumptions.
2. Scripted certificates. Implement scanners for entropy reserve, quotient profiles, restricted sums, interleaved-list budgets, and challenge-field accounting.
3. Toy-case exploration. Exhaust small fields/domains to discover or refute local-limit behavior.
4. External-import audit. Check the exact hypotheses and constants of the Crites--Stewart list-to-agreement conversion used by Paper D.
5. New bounds. Attack the local-limit conjectures, interleaved-list constants, extension-line MCA, or domain-shattering alternatives.
6. Protocol rewrites. Rewrite FRI, WHIR, or other proximity reductions in the exact ledger format of Paper C.

See AGENTS.md for a prioritized task list and suggested toy cases.

Script layer

The first heuristic script is scripts/run_frontier.py, an EXPERIMENTAL Paper B frontier scanner. For each prime p passed on the command line, intended with 32 | p-1, it builds the order-32 multiplicative subgroup of F_p, uses a meet-in-the-middle subset enumeration at fixed l = 18, and records which elementary-symmetric fingerprints (e1, e2) are realized by l subgroup elements. Its coverage line measures how much of F_p^2 this restricted quotient-locator map hits and appends the result to frontier_results.txt; full coverage is evidence about quotient/restricted-sum frontier behavior, not a proof by itself. The script currently requires numpy and sympy.

The broader intended script layer is:

scripts/
  run_frontier.py            # EXPERIMENTAL psi_2 restricted-subset frontier scan
  entropy_margin.py          # generated-field entropy reserve
  quotient_profile.py        # active quotient scales at actual (n, k, a)
  restricted_sum_dp.py       # restricted-sum / DSH verification certificates
  locator_fiber_scan.py      # small-field locator-fiber experiments
  mca_slope_scan.py          # small-field bad-slope / residue-line experiments
  interleaved_budget.py      # base/interleaved list-to-field soundness budget
  certificate_emit.py        # JSON + TeX certificate tables for Paper C

A useful script should emit both human-readable output and a machine-checkable certificate. Hand-computed tables should eventually be replaced by script output.

Conventions

Use these conventions when adding results:

• rho = k/n is the rate.
• delta = 1 - rho - eta is the proximity radius.
• eta is the reserve/gap from capacity.
• q_gen is the field generated by the domain/received-word data.
• q_line is the field from which line or CA/MCA challenges are sampled.
• q_chal is the verifier challenge field; it may or may not equal q_line.
• mu is protocol list arity.
• nu is implementation interleaving.
• Qprof is the quotient-profile obstruction ledger.

When in doubt, keep the fields separate. Most false near-capacity claims come from giving the same field-size credit to two different ledgers.

Citation and release hygiene

When editing the papers:

• Cite companion results with theorem/proposition numbers, not just “the companion proves.”
• Mark every result as proved, conditional, conjectural, experimental, or audit-only.
• Do not cite the universal cap as unconditional until the imported conversion is fully audited.
• Do not state an error-one result from Paper D’s cap; Paper D caps the threshold and gives a small certified failure probability, but the error-one-in-the-band problem remains open.
• Keep Paper D as the canonical reference for the final universal-cap constants.
• Keep Paper C as the canonical reference for protocol ledgers and field-accounting rules.

Project goal

The goal is to settle the Proximity Prize MCA/list questions for smooth-domain Reed--Solomon codes in a way that is useful for proof systems.

A positive outcome would be a theorem-backed reserve certificate: given a domain, rate, field, interleaving, and protocol reduction, the repo can certify a near-capacity radius and soundness budget.

A negative outcome is also valuable: every obstruction becomes a new floor, a warning for protocol designers, or a reason to switch to folded/subspace-design codes, random/punctured domains, or domain-shattered constructions.

Either way, the aim is to replace folklore “near-capacity RS should work” claims with exact, checkable mathematics.

The current work was done with GPT-5.5 Pro and Claude Fable 5 and still needs proper revision. Human input is welcome.