FPRD LabShare an approach

← Claims

Theorem

FPRD-T64

DNF bounds from layers, fibres, and sites

Exact statement

If a Fold-and-Look presentation realizes a Boolean function gg, then its maximum layer depth DD bounds the minimum DNF term width, and its number of potential feature sites PsitesP_{\mathrm{sites}} bounds the minimum total literal occurrences. If gg is nonconstant, the number SS of effective variable-bearing fibres also bounds the minimum DNF term count.

StatusProved and rechecked within FPRD Lab
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The incidence normal form produces one explicit DNF. Minimizing over all exact DNFs can only decrease its width, term count, and number of literal occurrences.

Definitions

  • wDNF(g)w_{\mathrm{DNF}}(g), sDNF(g)s_{\mathrm{DNF}}(g), and ℓDNF(g)\ell_{\mathrm{DNF}}(g) denote minimum maximum term width, minimum term count, and minimum total literal occurrences over exact DNFs for gg.

Hypotheses and scope

  • The width and nonconstant term-count bounds use the full FPRD-D29 doctrine through FPRD-T63.
  • The literal-occurrence bound in fact needs only clean alignment, no crease through a punch, and interiority; it does not require uniform overlay.
  • The term-count statement excludes constant functions.

Proof or evidence

A term uses at most one distinct literal for each layer above its location, giving the width bound. Effective nonconstant terms are counted by effective fibres. For literal occurrences, the address map sends each feature site to one final location, so sites partition among the terms and no site is charged twice.

Formula-resource inequalities →

Verification notes

The original unrestricted term-count statement was refuted by a constant-function example and repaired by adding the nonconstant hypothesis. The internal re-audit proved the literal-occurrence inequality under weaker assumptions and explained why nonuniform pieces may shrink a live region but do not split one site among multiple terms.

Limitations

  • These are one-way lower bounds on presentation resources, not matching upper bounds for arbitrary Boolean functions.
  • The final Look operation has unbounded fan-in and its cost is not charged here.
  • No external or specialist review is documented.

Open work

Clarify which inequalities remain valid for some-layers folds and for nonuniform punch images.

Notes

Independent re-audit established that the literal-occurrence bound is provable from (GP), (NC), (IN) ALONE, without (UF), via a corrected normal form restricted to pieces full over each punch image; so it rests on weaker hypotheses than first claimed. The unrestricted term-count statement was REFUTED by a constant-g degeneracy. For nonconstant g, however, the repaired and independently re-audited incidence normal form supplies the displayed DNF and proves the stated bound under D29. D <= 2^F is classical, being the folklore doubling count used inside Cardinal et al., Algorithmic Folding Complexity; no priority is claimed for it.