Prepared strips and one final observation

Fold-and-Look incidence and resource bounds

In a restricted one-dimensional model, input literals control prepared feature sites, an input-independent all-layers fold program aligns them, and one final through-hole observation computes a Boolean function. The geometry extracts a DNF and yields exact resource inequalities. One proposed geometric separation does not survive review: its reflection-line lemma is false, so the associated fold lower bound is withdrawn.

FPRD-D29 · definition

The model is deliberately narrower than paper folding

Begin with a connected strip $P$ carrying finitely many prepared feature sites. A site is controlled by one input literal or by a Boolean constant. The fold sequence is fixed before the input is known, uses all-layers simple folds, and is followed by no cutting, punching, or unfolding. The final observation asks whether some positive-radius aligned punch interval is open through every material layer.

The address map $\varphi:P\to\mathbb R$ sends a material point to its final coordinate, and $\Phi(y)=\varphi^{-1}(y)$ is the complete fibre over $y$ . Five standing conditions are part of the theorem:

site images coincide or are separated by more than twice the punch radius;
no crease crosses a punch interval;
every punch image is strictly inside the final footprint;
the set of affine pieces covering a punch interval is constant throughout it; and
the punch radius is strictly positive.

Dropping uniform overlay or allowing a zero-radius “punch” breaks the point-fibre formula below. The theorem does not describe arbitrary folds, adaptive geometry, or intermediate cutting.

FPRD-T63 · theorem

The final observation is a finite incidence DNF

\operatorname{Look}(w)= \bigvee_{y\in Y_{\mathrm{eff}}} \ \bigwedge_{p\in\Phi(y)}\ell_p(w).

Here $Y_{\mathrm{eff}}$ consists of interior final coordinates whose nonempty fibre contains only feature sites. A fibre is see-through exactly when every covering material point is an open feature site. The final observation is the disjunction over all such locations.

Proof idea. Clean alignment makes distinct punch images disjoint. No-crease and uniform-overlay conditions make the inverse points track the image interval isometrically inside a fixed set of affine pieces. Interiority excludes exposed boundary artefacts. Thus a positive-radius punch is open throughout exactly when all literals in its complete fibre are true. ∎

The OR-over-stacks and AND-over-layers mechanism is already explicit in the fold-and-cut construction of An, Demaine, Demaine, and Ku. This page extracts it in the restricted literal-local model and makes no novelty claim.

FPRD-T64 · theorem

Formula complexity lower-bounds physical resources

Let $D$ be maximum layer depth, $S$ the number of effective variable-bearing fibres, and $P_{\mathrm{sites}}$ the number of potential feature sites. If the presentation realizes $g$ , then

w_{\mathrm{DNF}}(g)\le D, \qquad \ell_{\mathrm{DNF}}(g)\le P_{\mathrm{sites}}, \qquad s_{\mathrm{DNF}}(g)\le S\quad(g\text{ nonconstant}).

The first and third inequalities follow from the incidence DNF. For literal occurrences, each prepared site maps to only one final coordinate and is charged to at most one term; this argument needs clean alignment, no crease through the punch, and interiority, but not uniform overlay. Constants and duplicate literals are removed when a fibre conjunction is reduced.

FPRD-T65 · sharp theorem

Mirrored mismatch attains all four bounds

For $n\ge1$ , define $\operatorname{MISMATCH}_{2n}$ to accept exactly when some mirrored pair disagrees. Its prime implicants are exactly

w_i\wedge\neg w_{2n+1-i} \quad\text{and}\quad \neg w_i\wedge w_{2n+1-i} \qquad(1\le i\le n).

All $2n$ width-two terms are essential. Therefore every presentation has $D\ge2$ , $S\ge2n$ , $P_{\mathrm{sites}}\ge4n$ , and at least one fold. A single midpoint fold aligns the mirrored sites and attains all four bounds. No moved-material lower bound is asserted.

FPRD-T66 · partial theorem and withdrawn argument

The continuation rows survive; the fold separation does not

For a permutation $\pi\in S_n$ , let $L_\pi=\{xy\in\{0,1\}^{2n}:y_{\pi(i)}=x_i\text{ for all }i\}.$ Every prefix $x$ has exactly one accepting suffix, so the $2^n$ prefixes give $2^n$ distinct midpoint rows. This part is proved.

Correction. The former proof that every required width-two fibre joins opposite-orientation affine pieces is false. Consequently the claimed $\lceil\log_4\operatorname{LIS}(\pi)\rceil$ fold lower bound and the resulting reversal-versus-equality separation are not established in this model.

A legal counterexample uses $P=[0,10]$ , folds first at $7$ and then at $3$ , and observes $y=1$ . The maximal affine pieces are $[0,3]$ , $[3,7]$ , and $[7,10]$ , with slopes $+1,-1,+1$ . Their points $1,5,9$ all map to $1$ .

Put literals $x_1$ and $x_2$ at the same-orientation outer sites and the constant TRUE at the intervening site. With punch radius $1/4$ , all five geometric hypotheses hold, while the fibre term reduces from $x_1\wedge\mathrm{TRUE}\wedge x_2$ to the width-two term $x_1\wedge x_2$ . The failed proof treated every third layer as a third surviving literal, contradicting its own convention that constants and duplicates are removed.

Dilworth's decreasing-subsequence cover identity and Koehler's analysis of stamp-folding permutations remain valid classical facts. The unsupported step was the map from a reduced Boolean fibre to a reflection-only geometric edge cover.

FPRD-T67 · proposition and corollary

Material, precision, and folds are coupled

After $F$ all-layers folds, the address map has at most $2^F$ affine pieces. If $\Lambda_{\mathrm{fp}}$ is final-footprint length and $\delta>0$ is minimum within-piece site separation, then

P_{\mathrm{sites}} \le 2^F\left(\frac{\Lambda_{\mathrm{fp}}}{\delta}+1\right).

Parity on $m$ variables has exact DNF literal count $m2^{m-1}$ . Combining that count with the site lower bound gives

\frac{\Lambda_{\mathrm{fp}}}{\delta}+1 \ge m2^{m-1-F}.

The ratio is therefore exponential when, for example, $F=O(\log m)$ . This does not say that material length alone is exponential; fine feature spacing may absorb the cost.

Sources and evidence

Byoungkwon An, Erik D. Demaine, Martin L. Demaine, and Jason S. Ku, Computing 3SAT on a Fold-and-Cut Machine, Proceedings of the 29th Canadian Conference on Computational Geometry, 2017, pp. 208–213. This supplies the fold-and-cut construction and its OR-over-stacks/AND-over-layers mechanism.
Yasuhiko Asao, Erik D. Demaine, Martin L. Demaine, Hideaki Hosaka, Akitoshi Kawamura, Tomohiro Tachi, and Kazune Takahashi, Folding and Punching Paper, Journal of Information Processing 25, 2017, pp. 590–600, DOI 10.2197/ipsjjip.25.590. This is broader folding-and-punching context, not a source for the restricted D29 inequalities.
Robert P. Dilworth, A Decomposition Theorem for Partially Ordered Sets, Annals of Mathematics 51(1), 1950, pp. 161–166. Its chain-cover theorem remains correct but no longer yields the withdrawn fold bound.
John E. Koehler, Folding a Strip of Stamps, Journal of Combinatorial Theory 5(2), 1968, pp. 135–152. This is classical permutation-folding context.

The independent checker confirms the exact matching-row theorem for all 873 permutations through $n=6$ , 21,844 mismatch assignments, the parity counts, 315 packing cases, and the two-fold hostile fibre above.