promoted from data/fprd-lab/fold-look/bounded-fold-piecewise-isometry.md on 2026-07-28 — status: unverified

Bounded-fold incidence run, theorem memos: the Fold-and-Look incidence normal form and formula-resource inequalities (w_DNF<=D, s_DNF<=S, l_DNF<=P_sites, D<=2^F, F>=ceil(log2 w_DNF)); the piecewise-isometry bound r<=2^k with signed-affine cover sigma<=4^k, proved for all-layers folds only; and the palindrome construction’s optimality in five coordinates. Proved here, pending independent audit.

Bounded-fold piecewise isometry and signed-affine incidence

Status: proved here for all-layers simple folds, pending independent audit. The some-layers case is open and is the declared audit target. Gate C of the bounded-fold incidence run.

1. Statement

Let $\varphi_{\mathcal P}$ be the address map of a program of $k$ perpendicular all-layers simple folds applied to a flat strip.

Theorem 5 (affine-piece bound). $\varphi_{\mathcal P}$ has the form $$\varphi_{\mathcal P}(x)=\varepsilon_j x+c_j,\qquad \varepsilon_j\in\{-1,+1\},$$ on at most $2^{k}$ original-address intervals.

Proof. By Definition 2.4 of Folding and Punching Paper, an all-layers folding step satisfies $f_1=f_{0\to1}\circ f_0$: it acts on the coalesced image, treating the previous folded state as its piece of paper. In one dimension the $k+1$-st step is a simple fold of the current image interval about a point $L$, so

$$\varphi_{k+1}=g_L\circ\varphi_k,\qquad g_L(t)=\begin{cases}t,&t\le L,\\ 2L-t,&t>L.\end{cases}$$

Suppose $\varphi_k$ is affine with slope $\pm1$ on an interval $I$. It is injective there, so $\{x\in I:\varphi_k(x)=L\}$ is at most a single point, and $\{x\in I:\varphi_k(x)>L\}$ is a subinterval. Hence $I$ splits into at most two subintervals, on each of which $\varphi_{k+1}$ is again affine with slope $\pm1$ — either $\varepsilon,c$ unchanged, or $(-\varepsilon,2L-c)$. With $r_0=1$ we get $r_{k+1}\le2r_k$, so $r_k\le2^k$. $\square$

Tight. The accordion — fold repeatedly at the midpoint of the current image — attains $r=2^k$ exactly, verified for $k\le6$ by the checker.

Prior art: Theorem 5 is classical result used. No claim is made to it. The prior-art lane located it. Cardinal, Demaine, Demaine, Imahori, Ito, Kiyomi, Langerman, Uehara, Uno, Algorithmic Folding Complexity, Graphs and Combinatorics 27(3):341–351, 2011, opens §2 (p. 4) with “Every mountain-valley pattern with $n$ creases requires at least $\lceil\lg(n+1)\rceil$ folds, just to get all the creases folded in some direction” — a statement whose only justification is that $k$ folds produce at most $2^k$ coincident pieces — and Lemma 1 (p. 4) uses the matching structure explicitly in the tight case: “If the number of segments between creases, $n+1$, is $2^k$ for an integer $k$, then the folding is the obvious one: fold at the middle crease, $k$ times.” The $\varepsilon x+c$ form itself is definitional (Eppstein, arXiv:2410.07666, §2, p. 2).

More generally the bound is the lap-number submultiplicativity $\ell(f\circ g)\le\ell(f)\,\ell(g)$ of Milnor–Thurston kneading theory: a 1D all-layers simple fold is a 2-lap piecewise-affine map with slopes $\pm1$. (The lab has not located that inequality’s exact statement in the primary Milnor–Thurston text, so this comparator is cited as a concept, not a pinned sentence, and is weaker than the Cardinal et al. one.)

Stating it as an explicit lemma about $\varphi_{\mathcal P}$ is a repackaging. The proof is retained because Theorem 6 and Corollary 7 are stated in terms of the affine pieces and need the count in that form — not because the count is ours.

1.1 Excluding Unfold is load-bearing, not tidiness

The doctrine forbids Unfold. That restriction carries the theorem, and there is a published witness for why.

Cardinal et al., Theorem 1, p. 4, in the all-layers fold, all-unfold model:

“The folding complexity of a uniform string and of a pleat of length $n$ in the all-layers fold, all-unfold model is at most $\tfrac32\lg^2 n$.”

A pleat of length $n$ has $n$ creases. So in a model admitting unfolds, $n$ creases cost only $O(\lg^2 n)$ folds. There is no numerical conflict with Theorem 5 — $2^{O(\lg^2 n)}$ vastly exceeds $n$, so the bound is merely loose there — but the induction is the casualty: an unfold does not compose as $\varphi_{k+1}=g_L\circ\varphi_k$, and the proof above has no force across one.

The prior-art lane raised the adjacent and sharper warning: crease counts do not transfer to fold counts, and the theorem quoted above refutes outright any argument of the shape “this alignment forces $n$ creases, therefore many folds.” Corollary 7 is checked against this and is safe, because it routes through doubling — each affine piece splits in at most two — and not through counting creases and converting. The creases are a consequence of the doubling, not a premise of it.

Recorded as a live boundary: admitting Unfold is the most likely single change that would break Theorem 5, Corollary 7, and Theorem 12 together.

1.2 The some-layers case is closed — proved, not refuted

This memo originally left some-layers folds open, on the grounds that the moving cluster $C_1$ is selected in the original paper, so $\varphi_{k+1}$ is not a function of $\varphi_k(x)$ alone and the composition argument has no force. That reasoning was right about the argument and wrong about the conclusion. The enumerator lane proved both bounds directly, without composition:

Theorem A. $\varphi_{k+1}=\varphi_k$ on $C_0$ and $2\ell-\varphi_k$ on $C_1$, so $\varphi_{k+1}$ is affine on the common refinement of the affine-piece partition and $\{C_0,C_1\}$. Interior cluster boundaries lie in $\varphi_k^{-1}(\ell)$, and each affine piece is injective, so contributes at most one preimage of $\ell$. Hence at most $A_k$ new breakpoints and $A_{k+1}\le2A_k$.

Theorem B. $\varphi_{k+1}^{-1}(y)=\bigl(C_0\cap\varphi_k^{-1}(y)\bigr)\sqcup\bigl(C_1\cap\varphi_k^{-1}(2\ell-y)\bigr)$, a disjoint union since $C_0,C_1$ partition the paper. Hence $D_{k+1}\le2D_k$.

Neither proof uses (S2), (S3), one-sidedness, connectedness of clusters, or layer order. Consequently both bounds hold for arbitrary flat folding steps of complexity 1 in one dimension, and generalize: a step of complexity $c$ gives $D_k\le(c+1)^k$.

The union-versus-disjoint-union distinction is precisely where a some-layers counterexample would have had to live, and it does not: the two sets lie in $C_0$ and $C_1$, so the bound is if anything tighter than in the all-layers case. Zero violations over the exact enumerator for $N\le8$, $k\le4$, with the bound assertions re-run to $N\le12$.

Correction of emphasis, accepted. The all-layers derivation needs the injectivity of each affine piece; it does not need $\varphi_{k+1}=g\circ\varphi_k$. Dropping that step is what yields the more general theorems.

$\sigma(E_{\mathcal P})\le4^k$ is true but trivially so. It is $A^2$ with $A\le2^k$; $A^2-A+1$ is already strictly better. Corollary 7 is therefore sound but weak, and any fold lower bound derived from it should be read as loose.

How loose, measured. The enumerator’s search reached $n=21$ at $k=4$, where the maximum observed $\sigma$ is $41=2n-1$. That is material-limited, not fold-limited: the binding constraint is the number of cells, while $4^k=256$ is nowhere near active. Two honest qualifications. The value is observed, not a proved maximum, and the search was not exhaustive at that size. And the integer crease grid under-tests the bound, because every line offset then lies in a window of width $O(n)$; a finer grid could admit larger $\sigma$. So “$\sigma$ grows linearly, not exponentially, in $k$” is a plausible reading of the data and is not claimed as a theorem — the measurement constrains only what the grid can express.

The practical consequence is that $F\ge\lceil\log_4\sigma(E)\rceil$ is a sound but weak instrument, and a target needing $\Omega(n)$ reflection lines yields only $\Omega(\log n)$ folds through it. Whether that gap is the bound’s slack or the truth is open.

2. Signed-affine incidence

Define the coincidence relation

$$E_{\mathcal P}=\{(x,x'):\varphi_{\mathcal P}(x)=\varphi_{\mathcal P}(x')\}.$$

Theorem 6 (cover). If $\varphi_{\mathcal P}$ has $r$ affine pieces then $E_{\mathcal P}$ is covered by at most $r^2$ interval-restricted signed-affine graphs $x'=\pm x+c$.

Proof. Fix pieces $i,j$. For $x\in I_i$ and $x'\in I_j$, $\varphi(x)=\varphi(x')$ reads $\varepsilon_i x+c_i=\varepsilon_j x'+c_j$, i.e. $x'=\varepsilon_j\varepsilon_i x+\varepsilon_j(c_i-c_j)$, using $\varepsilon_j^{-1}=\varepsilon_j$. This is one signed-affine graph restricted to $I_i\times I_j$. There are $r^2$ ordered pairs. $\square$

Define the signed-affine interval cover number $\sigma(E)$ as the minimum number of such restricted graphs needed to cover a required address relation $E$. Combining Theorems 5 and 6:

Corollary 7. $\sigma(E_{\mathcal P})\le4^{k}$, hence any program realizing a required incidence relation $E$ satisfies $$k\ \ge\ \bigl\lceil\log_4\sigma(E)\bigr\rceil.$$

3. What is not claimed

No converse, in any of the following forms:

• small $\sigma(E)$ does not imply that $E$ is fold-realizable — the cover number ignores layer order, collision-freeness (S2), and connectivity;
• $2^k$ affine pieces need not be attainable simultaneously with a prescribed incidence structure;
• fold count does not bound the number of aligned pairs — one reflection can align linearly many pairs, which is exactly the correction carried from the palindrome probe;
• $\sigma$ is a lower-bound instrument only. A large $\sigma$ forbids few folds; a small $\sigma$ permits nothing.