FPRD LabShare an approach

← Claims

Theorem

FPRD-T65

Optimal Fold-and-Look presentation of mismatch

Exact statement

For n≥1n\ge1, the prime implicants of MISMATCH⁡2n\operatorname{MISMATCH}_{2n} are exactly the 2n2n essential width-two terms witnessing a disagreeing mirrored pair. Hence every literal-local Fold-and-Look presentation has D≥2D\ge2, S≥2nS\ge2n, Psites≥4nP_{\mathrm{sites}}\ge4n, and F≥1F\ge1; a one-fold construction attains all four bounds.

StatusProved; normal-form dependency rechecked within FPRD Lab
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

MISMATCH⁡2n\operatorname{MISMATCH}_{2n} accepts exactly when some mirrored pair (wi,w2n+1−i)(w_i,w_{2n+1-i}) disagrees. It is the complement of the even-palindrome equality test under the fixed midpoint pairing.

Definitions

  • The 2n2n terms are wi∧¬w2n+1−iw_i\wedge\neg w_{2n+1-i} and ¬wi∧w2n+1−i\neg w_i\wedge w_{2n+1-i} for 1≤i≤n1\le i\le n.

Hypotheses and scope

  • Literal-local Fold-and-Look presentations satisfying FPRD-D29.
  • The resource coordinates are maximum layer depth, effective fibres, potential feature sites, and all-layers folds.

Proof or evidence

Each displayed term forces a mismatching pair and is prime. For every such term there is an assignment satisfying it and no other prime implicant, so all terms are essential. FPRD-T64 yields the lower bounds from the exact DNF measures, and the midpoint fold aligns each mirrored pair in one step using exactly the corresponding sites and fibres.

Mismatch prime implicants and optimal construction →

Verification notes

The prime-implicant calculation and construction were checked in the source note. The dependence on the repaired incidence normal form was separately re-audited. The previously proposed moved-material lower bound was not repaired and remains withdrawn.

Limitations

  • Optimality is proved only in the four named coordinates and within the literal-local doctrine.
  • No lower bound on moved material or total strip length is asserted.
  • Dense layouts can trade material length for geometric precision.

Open work

Give the one-fold construction a compact diagram and keep moved material separate from the four proved optimal coordinates.

Notes

The earlier S=1 counterexample violated (UF) and therefore lies outside D29. Once T63 is repaired and re-audited, T64 reinstates S >= 2n for this nonconstant function. The proposed moved-material bound W >= n remains withdrawn because its proof used an undefined cell convention.