promoted from data/fprd-lab/fold-look/k-fold-incidence-and-permutations.md on 2026-07-28 — status: unverified

Doctrine separation after repair: matching families L_pi all have exactly 2^n M25 midpoint continuation rows, yet reversal needs one fold and identity has no realization below ceil(log_4 n), conditional on an order-preserving encoder. The earlier position-faithful condition was refuted. The repair is not independently re-audited.

Matching families: equal continuation complexity, unequal folding demand

Status: REPAIRED AFTER AUDIT AND NOT RE-AUDITED. Theorem 12 was broken at (PF) by an independent audit and rebuilt here by the same lane that wrote the broken version — see docs/verify/bounded-fold-incidence-audit.md §0a. That audit file is named for provenance but is not included in this archive. Nothing in this memo may be cited as independently audited. The separation is proved conditional on a stated encoder hypothesis, which is itself the main honesty finding. Gate D of the bounded-fold incidence run.

1. Parity as a non-palindrome load case

For $\mathrm{PAR}_m(w)=\bigoplus_i w_i$:

Lemma 8. Every prime implicant of $\mathrm{PAR}_m$ has width $m$.

Proof. Flipping any single bit flips the value, so no partial assignment leaving a bit free can force the output. Hence the only implicants are full minterms. $\square$

Therefore

$$w_{\mathrm{DNF}}=m,\qquad s_{\mathrm{DNF}}=2^{m-1},\qquad \ell_{\mathrm{DNF}}=m\,2^{m-1},$$

and by Theorems 2–3 and Corollary 4 every $\mathsf{LLFL}$ presentation of parity requires

$$D\ge m,\qquad S\ge2^{m-1},\qquad P_{\mathrm{sites}}\ge m2^{m-1},\qquad F\ge\lceil\log_2 m\rceil .$$

$S\ge2^{m-1}$ is reinstated under the repaired doctrine. It was withdrawn when the original normal-form proof of $s_{\mathrm{DNF}}\le S$ failed. The positive-radius (UF) re-audit repaired that theorem for every nonconstant output function. Parity is nonconstant, so $s_{\mathrm{DNF}}\le S$ applies and gives the displayed lower bound.

$P_{\mathrm{sites}}\ge m2^{m-1}$ HOLDS under (UF), and unconditionally in WFL. It was briefly withdrawn here in error: the audit showed only that parity has no proof independent of Theorem 1, since its prime implicants share literals heavily and the palindrome literal-counting argument does not transfer. That is not the same as the bound being false. Under (UF), $\ell_{\mathrm{DNF}}\le P_{\mathrm{sites}}$ gives it directly. It has no fallback if (UF) is dropped. See docs/verify/fold-resource-accounting-audit.md.

$D\ge m$ and $F\ge\lceil\log_2 m\rceil$ survive throughout.

New, and the strongest parity statement now available: the coupling $P_{\mathrm{sites}}\le2^F(\Lambda_{\mathrm{fp}}/\delta+1)$ turns the $P_{\mathrm{sites}}$ bound into $$\Lambda_{\mathrm{fp}}/\delta+1\ge m\,2^{m-1-F}.$$ Thus parity forces an exponential material-to-precision ratio when, for example, $F=O(\log m)$. With unrestricted fold count the displayed inequality is the claim; no unconditional exponential conclusion follows. This material–precision consequence does not depend on $S$.

These are conditional lower bounds on any realization; no matching construction is claimed to exist. Three separate questions remain open and must not be conflated: (1) whether the abstract fiber model realizes parity with matching resources; (2) whether a connected physical strip does; (3) whether additional folds or feature replication are forced. The point established is only that the doctrine has nontrivial resource complexity beyond palindrome. The repaired doctrine supplies both the reinstated $S$-bound and the $P_{\mathrm{sites}}$ bound; the material–precision coupling is the stronger relation among charged resources.

Machine-checked ($m\le4$): all prime implicants are full-width, count $2^{m-1}$.

2. Matching families

For $\pi\in S_n$ define $L_{\pi,n}$ on $\{0,1\}^{2n}$ by

$$L_{\pi,n}(xy)=1\iff y_{\pi(i)}=x_i\ \text{ for every }i.$$

Lemma 9. For every $\pi$, $L_{\pi,n}$ has exactly $2^n$ distinct midpoint continuation rows.

Proof. After reading $x$, the unique accepted suffix is $y$ with $y_{\pi(i)}=x_i$, which determines $y$ since $\pi$ is a bijection. Distinct $x$ give distinct required $y$, hence distinct rows; there are $2^n$ prefixes. $\square$

So the M25 Boolean continuation cost is identical for all $\pi$: exactly $2^n$ exact future rows at the midpoint cut, for every permutation.

3. Two realizations that must be kept apart

The brief’s warning is the crux of this section and is restated as a definition.

• Address realization — placing $x_i$ and $y_{\pi(i)}$ into a common fiber. This is a property of $E$ and is what $\sigma$ measures.
• Boolean realization — obtaining the equality (or mismatch) predicate through the fixed local channel encoding, once the addresses meet.

The rejection predicate is $\bigvee_i[x_i\ne y_{\pi(i)}]$, whose prime implicants are, by the argument of the frontier memo applied pairwise, exactly the $2n$ width-two terms $(x_i=b)\wedge(y_{\pi(i)}=1-b)$. So the required incidences are genuinely forced: every exact realization must bring $x_i$ and $y_{\pi(i)}$ into a common fiber, for every $i$. Address realization is not an artifact of one construction.

3.1 The encoder hypothesis, stated rather than hidden

$\sigma$ is computed on original addresses. If the encoder may place the site for $x_i$ at an arbitrary address of its choosing, it can apply $\pi$ itself at encoding time, and then $E$ is the reversal relation for every $\pi$, with $\sigma=1$. The permutation would have been smuggled into the encoder without being charged.

(PF) Position-faithful encoder. The sites controlled by $x_i$ lie in cell $i$, and those controlled by $y_j$ lie in cell $n+j$.

(PF) IS NOT SUFFICIENT, and the audit broke the first version of this section on exactly that point. (PF) fixes which cell a site occupies, but not where inside the cell it sits, how wide cells are, or that they are uniformly spaced. Identifying “cell $i$” with “address $i$” was an unstated extra hypothesis, and it was load-bearing: with cell widths free — the encoder never consulting $\pi$, only choosing widths — the shuffle’s edges can be placed on two translation lines, giving $\sigma=2$ for every $n$ and collapsing the bound to $F\ge1$, the same as reversal.

The correct hypothesis is weaker and is supplied by the doctrine itself:

(OP) Order-preserving encoder. The sites for $x_1,\dots,x_n$ occur in increasing address order, then those for $y_1,\dots,y_n$ in increasing address order.

(OP) is implied by the locality already required of $\operatorname{Enc}_n$ — a left-to-right encoder writes in order — so it is not an added assumption in the way (PF) was. Everything below uses (OP), and §4.2 shows why the translation-line escape is unavailable under it.

All separations below are stated under (OP), not (PF). This is not a technicality to be waved past; it is the substance:

Finding. Folding demand is a property of the encoder-and-program pair, not of the predicate alone. Without a charge on placement, every matching family collapses to one fold and no separation exists. (PF) looked like such a charge and was not one; (OP) is, and is weaker.

4. Signed-affine cover of the four families

Scope of this section: superseded by §4.2. Everything here is computed at fixed unit addresses, writing the required relation as $E_\pi=\{(i,\;n+\pi(i))\}$. That identification of “cell $i$” with “address $i$” is precisely what the audit refuted as an unstated hypothesis, so the numbers below are correct only for that fixed embedding and are not the general cover numbers. They are retained because Lemma 16 and §4.2 were derived against them and because the identity entry is an instructive error.

Lemma 10 (superseded by Theorem 19; scope corrected after audit). At fixed unit addresses, every signed-affine line $x'=\pm x+c$ contains at most two edges of the even–odd shuffle $$\pi(i)=\begin{cases}2i,&1\le i\le n/2,\\ 2(i-n/2)-1,&n/2<i\le n.\end{cases}$$

Proof. Edges from the first half are $(i,n+2i)$. On $x'=x+c$ this forces $c=n+i$; on $x'=-x+c$ it forces $c=n+3i$. Both are strictly monotone in $i$, so a given line meets the first half in at most one edge. Edges from the second half are $(i,\,n+2(i-n/2)-1)=(i,\,2i-1)$; on $x'=x+c$, $c=i-1$, and on $x'=-x+c$, $c=3i-1$, again strictly monotone. $\square$

Corollary 11. $\sigma(E_\pi)\ge n/2=\Omega(n)$ for the even–odd shuffle. Hence, at fixed unit addresses and conditional on Corollary 7, $$F=\Omega(\log n).$$

By contrast the reversal $\pi(i)=n+1-i$ gives $E_\pi\subseteq\{x'=-x+(2n+1)\}$, a single signed-affine line: $\sigma=1$, and one fold suffices — which is precisely the palindrome construction, and precisely the sense in which one reflection carries $n$ pairs at once.

Machine-checked $\sigma$ values (exact branch-and-bound over the induced line set):

The shuffle row is not monotone — at $n=8$ three reflection lines happen to carry two edges each, giving 5 rather than 8. This does not disturb Corollary 11, which asserts only $\sigma\ge n/2$.

Corrected cause (the first explanation given here was wrong). Collisions among the $-x+c$ lines occur iff $i+\pi(i)$ repeats, i.e. iff $3\mid(n+1)$ — not $n\bmod4$, which was the original claim. Verified: $n=8$ gives $n+1=9$, three collisions, $\sigma=8-3=5$; $n=4,6,10,12$ give none and $\sigma=n$; $n=14$ gives five. The error was caught by the independent audit lane.

Scope of Lemma 10, also corrected. The bound of two holds at fixed unit addresses. If cell widths are the encoder’s to choose, the constant depends on a convention: with sites strictly interior to their cells the maximum is still two, but if sites may sit on cell boundaries three edges fit one line (witness $i\in\{1,2,3\}$ at $c=14$, $n=12$). Both are recorded because neither reading is wrong, only unstated.

None of this affects Theorem 19, which counts using only the order of the sites and never their positions. It is therefore immune to cell width, in-cell placement, and the boundary convention alike — which is the main reason it is the form worth keeping.

4.1 Orientation forcing

The prior-art lane extracted a necessary condition from the 1D fold-and-cut literature that survives the weakening from single-target alignment to partial coincidence. In the source’s notation (orthofoldcut Lemma 2.2, p. 5), with $f$ the location map:

“Aligning the cut points requires $f(a)=f(b)$. That both cut points have positive sign requires that $f$ is increasing at both $a$ and $b$. In particular, for some $\varepsilon>0$, we have $f(b-\varepsilon)<f(b)=f(a)<f(a+\varepsilon)$ and $a+\varepsilon<b-\varepsilon$. The Intermediate Value Theorem implies that there is a point $c$ with $a<c<b$ and $f(c)=f(a)$.”

The lane’s observation is that the conclusion of the paper’s lemma depends on single-target exclusivity, but this step does not. Stripped of it: a coincident pair at which $\varphi$ has the same orientation forces a third coincident point strictly between. Combining that with the normal form gives something the geometry alone does not:

Lemma 16 (orientation forcing). In $\mathsf{LLFL}$ with all-layers folds, let $p\ne q$ be sites whose common fiber must carry a width-two term of the realized DNF. Then $\varphi$ has opposite orientations at $p$ and $q$: $\varepsilon_p=-\varepsilon_q$.

Proof. A flat folding of a connected strip is continuous, and by (NC) each site lies in the interior of an affine piece, so $\varphi$ is locally monotone at $p$ and at $q$ with slope $\varepsilon_p,\varepsilon_q$. Suppose $\varepsilon_p=\varepsilon_q$, without loss of generality both $+1$, with $p<q$ and $\varphi(p)=\varphi(q)=y$. The displayed argument gives $c\in(p,q)$ with $\varphi(c)=y$, so $|\Phi(y)|\ge3$.

Now apply Theorem 1. If $c$ is not a site, it is solid paper, so $y\notin Y_{\mathrm{eff}}$ and $y$ contributes no term at all. If $c$ is a site, the term at $y$ is an AND over at least three layers and has width $\ge3$. Either way $y$ does not carry a width-two term. $\square$

Corollary 17. Every required pair of a width-two-term family lies on a reflection-type line $x'=-x+c$. Translation-type lines $x'=x+c$ cannot carry any required pair.

Proof. By Theorem 6 a pair in pieces $i,j$ lies on $x'=\varepsilon_i\varepsilon_j x+c$; Lemma 16 forces $\varepsilon_i\varepsilon_j=-1$. $\square$

This explains structurally why reversal is the special case. All $n$ reversal pairs lie on the single reflection-type line $x'=-x+(2n+1)$ — and a single all-layers fold is precisely an $\varepsilon=-1$ identification. The palindrome construction is not a lucky encoding; it is the unique shape a one-fold width-two family can have.

Verified on the construction: for $n=1,\dots,5$ every one of the $2n$ fibers is opposite-orientation and none is same-orientation, as Lemma 16 requires.

Lemma 16 also sharpens the counting: $\sigma$ need only be minimized over reflection-type lines, which is at most $r^2/2$ rather than $r^2$. That is a constant-factor gain in Corollary 7 and does not change any asymptotic statement, so it is recorded but not relied upon.

4.2 The cover number is the longest increasing subsequence

Under (OP) the addresses are free but ordered. Lemma 16 restricts required pairs to reflection lines, and that is what makes the counting work.

Lemma 18. Under (OP), the edges of $E_\pi$ carried by a single reflection line $x'=-x+c$ form a decreasing subsequence of $\pi$.

Proof. An edge $(p_i,q_{\pi(i)})$ lies on $x'=-x+c$ iff $p_i+q_{\pi(i)}=c$. By (OP) $p_i$ increases with $i$ and $q_j$ increases with $j$; constancy of the sum forces $q_{\pi(i)}$ to decrease as $i$ increases, hence $\pi(i)$ to decrease. $\square$

Theorem 19. Under (OP) and Lemma 16, $$\sigma_{\mathrm{refl}}(E_\pi)\ \ge\ \mathrm{LIS}(\pi), \qquad\text{hence}\qquad F\ \ge\ \bigl\lceil\log_4 \mathrm{LIS}(\pi)\bigr\rceil .$$

Proof. By Lemma 16 only reflection lines carry required pairs, and by Lemma 18 each carries a decreasing subsequence. The minimum number of decreasing subsequences covering a permutation equals the length of its longest increasing subsequence (Dilworth/Mirsky: an increasing subsequence meets each decreasing class at most once, and patience sorting attains the bound). Corollary 7, restricted to reflection-type piece pairs, gives $\sigma_{\mathrm{refl}}(E_{\mathcal P})\le r^2/2\le4^k/2$. $\square$

Computed $\mathrm{LIS}$, exhaustively verified equal to the minimum decreasing cover for $n\le32$:

This supersedes the $\sigma$ table of §4. That table minimized over lines of both signs, which Lemma 16 shows is the wrong quantity: it credited translation lines that cannot carry a required pair. Its identity entry ($\sigma=1$) was the clearest symptom — under the correct measure the identity is the hardest of the four families, not the easiest.

5. The doctrine-separation theorem

Theorem 12 (separation). Assume (OP) and the standing hypotheses of the normal-form memo including (UF), with all-layers folds. Then for every $\pi\in S_n$, $L_{\pi,n}$ has exactly $2^n$ M25 midpoint continuation rows, while its folding demand is $F\ge\lceil\log_4\mathrm{LIS}(\pi)\rceil$. In particular:

• palindrome $L_{\mathrm{rev},n}$ admits a one-fold presentation;
• equality of the two halves $L_{\mathrm{id},n}$, i.e. $y_i=x_i\ \forall i$, admits none below $\Omega(\log n)$ folds, and may admit none at all.

Proof. Lemma 9 gives equal continuation complexity for every $\pi$. The reversal realization is the palindrome construction, $F=1$, consistent with $\mathrm{LIS}(\mathrm{rev})=1$. For the general bound, §3 forces the incidences and Theorem 19 applies. For the identity, $\mathrm{LIS}(\mathrm{id})=n$. $\square$

Why this is the right pair to state. The separation is now between two of the most standard predicates in the subject — palindrome and equality — rather than between palindrome and a constructed shuffle. And the mechanism is structural rather than incidental:

A fold is a reflection, so it natively compares mirror-image positions. Comparing same-order positions is what costs. Palindrome asks for exactly the comparison a fold performs; equality asks for the one it cannot.

The even–odd shuffle remains a valid witness ($\mathrm{LIS}=n/2$) but is no longer needed: the identity is both more natural and asymptotically harder.

5.1 Why the conclusion is phrased disjunctively

An earlier draft read “requires $\Omega(\log n)$ folds”, which presupposes the shuffle is realizable at some fold count. That presupposition is not proved and is now in doubt, so the statement was weakened.

The prior-art lane found that which permutations of a strip’s cells are realizable by folding is the classical stamp-folding problem, with a complete characterization: Koehler, Folding a strip of stamps, J. Combin. Theory 5 (1968) 135–152, via Legendre, Foldings and meanders, Australas. J. Combin. 58(2) (2014) 275–291, Lemma 2.1, p. 276. Reversal, complement and cyclic shift are named, studied, foldable objects there (Legendre §2–3, pp. 277–279). The lane implemented Koehler’s criterion, validated it against OEIS A000136 for $n\le8$, and found the even–odd shuffle is not a folding for any $n\ge4$ tested through $n=16$, smallest crossing witness at $(i,j)=(1,3)$.

That result does not refute Corollary 11, because it is about a strictly stronger requirement, and the distinction must be kept:

• the classical object is the stacking order of a completely folded strip — all cells at one location, totally ordered;
• $E_\pi$ requires only that specified pairs coincide, at up to $n/2$ distinct final locations, with the rest of the strip free to remain spread out.

A partial-coincidence requirement is weaker than a total stacking order, so unrealizability of the latter implies nothing about the former. But it is enough to remove any entitlement to the word “requires”, and the disjunctive form above is true under either resolution.

The separation survives either way, which is why it is worth stating: reversal is realizable at $F=1$; the shuffle is realizable at no fold count below $\Omega(\log n)$, and possibly at none. Both branches separate it from reversal, and both leave Lemma 9’s equality of continuation complexity untouched. Determining which branch holds is referred to the prior-art lane (is partial alignment a named object with known fold counts?) and, failing that, to a construction attempt.

Consequence. Boolean continuation complexity does not determine folding demand. Two families indistinguishable to M25 at the midpoint cut have different proved folding lower bounds: reversal is realized with one fold, while equality has no realization below $\lceil\log_4n\rceil$ folds. No matching upper bound for equality is claimed.

6. Dependencies and what would break this

The theorem is conditional on three things, each of which is a live risk:

1. Corollary 7 ($\sigma\le4^k$), hence Theorem 5, hence the all-layers restriction. If some-layers folds break Theorem 5, the upper envelope changes and the $\Omega(\log n)$ bound weakens or fails.
2. (OP). Without a charge on encoder placement there is no separation at all.
3. The lower bound is on the abstract incidence relation. No claim is made that equality or the shuffle is realizable at $O(\log n)$ folds; only that neither is realizable below its stated lower bound. A matching upper-bound construction has not been proved.

7. Status

Proved here: Lemmas 8, 9, 10; Corollary 11; Theorem 12 under its stated hypotheses. Machine-checked: parity prime implicants ($m\le4$); all four $\sigma$ tables; reversal $\sigma=1$.

Prior art, as returned by the targeted lane:

• classical result used — the characterization of foldable permutations (Koehler 1968 via Legendre 2014, Lemma 2.1, p. 276), and reversal / complement / cyclic shift as studied fold permutations (Legendre §2–3). This was the predicted hit and it landed.
• not yet found to be prior — any statement about the number of folds needed to realize a given permutation. The stamp-folding literature counts folded states; it has no fold-count dimension at all.
• not yet found to be prior — the S5 pattern of argument itself: equal continuation or communication complexity set against unequal folding demand. The nearest comparator found (Cardinal et al., Thm 1 vs Thm 3) separates within a single measure, not across two doctrines.

Open and referred out: whether the partial coincidence relation $E_\pi$, as opposed to a total stacking order, is a named object with known fold bounds. The natural comparator is the fold-and-punch alignment literature rather than stamp folding, and that comparison has been commissioned.