Research · Papers · What rank-one constraints can express · MF-013
A degree bound for determined coordinates in odd-multiplicity F₂-R1CS systems
In any unique-witness (or odd-multiplicity) F₂-R1CS system, every determined coordinate has degree ≤ 2m - a + 1
Published 2026-08-29
For everyone
Plain summary
This entry records a proposed limit on how complex a fixed 0-or-1 variable can get inside a system of quadratic equations over bits. In an F_2-R1CS system, equations equate products of two linear expressions to zero or another linear expression. When each input has either exactly one valid internal solution or an odd number of them, the conjecture states that any output variable whose value is fixed by the system cannot exceed degree 2m - a + 1 in the inputs. The register does not define what m and a stand for. Only a narrow subcase—where every input has the same nonzero summary value, called a fibre trace—has been proved. The general rule remains an open conjecture with no prior art recorded.
Result
The parity–degree conjecture states:
> In any unique-witness (or odd-multiplicity) F_2-R1CS system, every determined coordinate has degree <= 2m - a + 1.
The register notes that ripple carry sits exactly on this degree boundary. The only conjectured escape route is even witness multiplicity, whose minimal two-witness instance is eliminated by MF-003. The parameters m and a are not defined in the entry.
A written proof covers only the subcase where witness fibres have constant nonzero trace. The general parity–degree law remains CONJECTURE.
Setting and definitions
The system is defined over F_2. A witness fibre is the set of witness assignments matching a given input. Unique multiplicity means each input admits one witness; odd multiplicity means each admits an odd number of witnesses. A determined coordinate is a variable whose value is uniquely fixed by the system constraints. Coordinate degree is its degree as a Boolean polynomial. Fibre trace is an invariant assigned to each witness fibre. The register defines neither the trace map nor the parameters m and a appearing in the bound 2m - a + 1.
Method
The conjecture was evaluated under the evaluation protocol. A verified proof for the constant nonzero fibre-trace subcase and an associated verification map are documented in this paper's downloadable evidence pack.
Neither replay batch establishes the general bound. The positive-pin and state-slice results are strictly narrower and do not warrant an upgrade. The register retains CONJECTURE.
Discussion
The verified argument covers only constant nonzero fibre trace. Varying trace, trace-zero fibres, even-multiplicity fibres, and mixed parities remain unproved.
Structurally, ripple carry attains the conjectured degree bound. Even witness multiplicity remains the only proposed mechanism for exceeding it; MF-003 rules out the two-witness case, leaving higher even multiplicities uncharacterized. Positive-pin and state-slice obstructions provide local barriers but do not yield the general bound. The register records no prior-art search or attribution.
For everyone — the takeaway
What this means
If true, this conjecture caps the algebraic complexity of any bit uniquely determined by quadratic constraints over F_2. Standard ripple carry addition hits this ceiling exactly. Proving the rule would explain why carry bits cannot be compressed into lower-degree formulas under unique or odd witness assignments. For now, the bound is proved only when all input fibres share a constant nonzero trace summary. Systems with varying or zero trace, or with even numbers of witnesses per input, remain open.
Register references
Entry: MF-013.
Receipts: BRIEF B.5 (probe 08); CONT batch_a_replay_receipt.json; CONT batch_b_replay_receipt.json; zkgolf-transfer-studies/01-r1cs-gadget-theory/REPORT.md section 7 (SHA-256 f795ee05a5ffa56dc76ab8e13d015d8cf95aad761db98b271c847eaf600f1f72); CONT lens_l3b_verification_report.md.
Prior art: the register does not record this.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 4 of 4 receipt files bundled (20 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-13The general result remains a conjecture. A verified proof covers constant nonzero fibre trace only, while varying trace, trace-zero/even fibres, proper-mixed parity, and the general parity-degree law remain unproved.
- 2026-08-29Published on this site.