FPRD LabShare an approach

← Claims

Partial theorem and failed lower-bound argument

FPRD-T66

Matching languages: exact residual complexity and an unresolved fold separation

Exact statement

For every permutation π∈Sn\pi\in S_n, the matching language LπL_\pi has exactly 2n2^n midpoint continuation rows. The former reflection-line/LIS fold lower bound is withdrawn: within FPRD-D29 a three-layer fibre may have same-orientation outer feature sites and an intervening TRUE or duplicate site, yet reduce to a width-two term. Whether equality of two halves requires Ω(log⁡n)\Omega(\log n) folds in this model remains unresolved.

StatusExact row theorem proved; geometric separation withdrawn after counterexample
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

Every matching permutation has the same exact midpoint continuation complexity. A proposed further separation by fold count relied on an orientation-forcing lemma that is false in the declared literal-local model.

Definitions

  • Lπ={xy∈{0,1}2n:yπ(i)=xi for every i}L_\pi=\{xy\in\{0,1\}^{2n}: y_{\pi(i)}=x_i\text{ for every }i\}.
  • LIS⁡(π)\operatorname{LIS}(\pi) is the length of a longest increasing subsequence of the pairing permutation.
  • For the counterexample, fold [0,10][0,10] at 7 and then at 3. The points 1, 5, and 9 all map to 1, with affine-piece slopes +1,−1,+1+1,-1,+1.

Hypotheses and scope

  • The exact row theorem uses only the definition of the matching language.
  • The hostile geometric example satisfies the all-layers literal-local doctrine of FPRD-D29 with punch radius 1/4.
  • Constants and duplicate literals are removed when determining the reduced DNF width of a fibre term.

Proof or evidence

After the first half is read, each prefix has one accepting suffix, giving one distinct row per prefix and exactly 2^n rows. The independent checker confirms all 873 permutations through n=6. In the two-fold hostile fibre, the outer sites at 1 and 9 have the same orientation, the intervening site at 5 is controlled by TRUE, and the conjunction reduces to x1 AND x2. This directly refutes the orientation-forcing lemma used to obtain the reflection-line cover.

Matching rows and reflection-line counterexample →

Verification notes

The source proof was reconstructed through its local orientation lemma rather than accepted from its summary. The new counterexample satisfies clean alignment, no-crease, interiority, uniform overlay, and positive radius. It invalidates the proof but does not by itself refute the claimed asymptotic fold lower bound, which is therefore recorded as unresolved rather than false.

Limitations

  • No Fold-and-Look lower bound follows from this record beyond the exact row theorem's ordinary deterministic information bound.
  • Dilworth's chain-cover theorem and classical stamp-folding results remain correct; their proposed geometric interface was the failed step.
  • The ordinary continuation-row count does not determine Fold-and-Look resources.

Open work

Either prove a lower bound using complete reduced fibres, including constants and duplicate literals, or construct a sublogarithmic equality presentation.

Notes

The orientation-forcing step derives from an intermediate-value argument in the 1D fold-and-cut literature whose stated conclusion depends on single-target exclusivity but whose core step does not. An earlier form of the separation was BROKEN by independent audit at a position-faithful encoder hypothesis, which fixed cells but not cell widths; it was rebuilt on the weaker order-preserving hypothesis. The rebuild is NOT independently audited. The affine-piece and cover bounds it routes through are classical (Cardinal et al.; lap-number submultiplicativity).