Skip to content

[Multi PH computation] Certify finite-grid rank-erosion tests #925

Open

Description

@t-uda

Status and parent contract

Bounded child plan for Package C of #865, under #227. Target ordinary develop; next release undecided. This does not reopen completed #501 or duplicate #760/#770. Under the owner's continuing-next-work instruction, #918 is the current implementation lane and #925 is at design/dependency preparation; #925 implementation has not started. This records scheduling and readiness, not an outstanding Owner approval or a new reapproval checkpoint.

The rank/nullity work previously tracked under #915 is integrated. Reuse its existing matrix-range argument through a separately admitted shared helper; do not start a competing rank backend or change the public homology-dimension interfaces. Preserve the integrated #919 image-semantics consumers.

Shared matrix-rank dependency — design checkpoint, 2026-11-17

Independent read-only inspection at develop 9d868f11a8277fffa8a568065bb198fc18486a67 supports the bounded dependency proposal. No competing public executable rectangular F₂ rank interface was found in the inspected current tree, open Issues and PRs. This read-only checkpoint prepares a separate bounded dependency contract; it starts no implementation, driver or build. #918 remains the current implementation lane. Subsequent admission and scheduling follow the existing project process without an additional Owner approval checkpoint.

  • Extract the existing private image-enumeration/cardinality argument in FiniteInputHomologyDimensions.lean:18–35 into a small lower-level API independent of simplex inputs. For Matrix (Fin m) (Fin n) (ZMod 2), compute the finite set of M.mulVec images of all source vectors and return Nat.log 2 of its cardinality.
  • Prove image membership agrees with LinearMap.range M.mulVecLin, its cardinality is 2 ^ Module.finrank …, and the executed rank equals that finrank. Pinned Mathlib's noncomputable Matrix.rank is a semantic target/interoperability corollary, not the executed definition. Reuse the existing subtype-equivalence argument, Module.card_eq_pow_finrank, ZMod.card and Nat.log_pow; keep classical reasoning proof-side.
  • Intrinsic matrix dimensions require no validation wrapper or positivity/square/injectivity/caller-certificate premise. Cover zero rows, zero columns (the source still has one empty vector), both rectangular orientations, repeated nonzero columns and distinct dependent columns. The cost is 2^n source-vector evaluations plus multiplication and deduplication, not a total O(2^n), Gaussian-elimination or cubic-time claim.
  • Preserve matrix materialization, representative ordering, public theorem statements, validation behavior, sourceLength - rank, and actual homology-map/rank/nullity/image-persistence consumers. Module and declaration names remain ordinary planning choices. No code, build, probe or execution success is claimed by this source audit.

Inputs and two deliverables

Use two actual finite-grid representations over F₂, possibly on different rational coordinate grids of the same dimension n, and a rational ε ≥ 0. An executable representation supplies finite fiber dimensions and matrices for comparable grid-point pairs; validate dimensions, identity and composition equations by finite computation. Invalid representation data must be distinguishable from failed erosion. No caller-supplied ranks, successful test or Kan-extension correctness conclusion is accepted.

  1. Finite criterion. Construct finitely many comparable rational grade pairs and prove their two rank inequalities equivalent to the full existing weak-pair RankErosion ε for the actual real-indexed CoordinateGrid.lan extensions.
  2. Executable certificate. Evaluate those tests with a certified F₂ matrix-rank backend. Return a passing result with a soundness theorem, or a failing direction, comparable grade pair and the two exact ranks witnessing failure. Prove completeness: every valid input returns one of these outcomes and success iff the full predicate holds.

The first proof can be generalized over a field if useful, but an arbitrary-field finite criterion alone does not finish the executable second deliverable.

Finite reduction and reuse

For each coordinate, refine by both grids' original and ε-shifted cuts; include singleton boundary cells, intervening intervals and unbounded tails, or an equivalent proved construction. Choose rational representatives and prove they preserve the floor indices of a, b, a−ε and b+ε and weak comparability. Original grid vertices alone are insufficient. Handle n=0, empty coordinate grids, absent lower points, upper tails, ε=0 and diagonal pairs.

Reuse CoordinateGrid, actual Kan fibers and appIso_structureMap and RankErosion. Transport computed matrix ranks through these actual component/map isomorphisms. No parallel erosion definition or floor-extension proxy without an isomorphism to the actual Lan object.

Acceptance and cost

Require nonzero passing and failing maps, a failure missed by sampling only original grid vertices, a diagonal test at ε=0, negative rational cuts, different grids, zero fibers, n=0 and both directions of failure. Kernel-check full-predicate consumers, not only the finite Boolean output.

If refined cell count is P, at most P² candidate weak pairs suffice for this baseline before comparable-pair filtering. State matrix validation and rank costs separately. #915's current plan enumerates source F₂ vectors and is exponential in source dimension; this issue cannot inherit a cubic elimination bound. Grid products can themselves grow exponentially with n.

A failed test proves failure at ε. A strict lower-distance certificate ε < dE ≤ dI additionally needs #865 Package A's attained-threshold theorem in its applicable original finite-presentation scope; it is not assumed here. No exact distance minimization, optimal radius list, classification, Gaussian elimination, arbitrary-field execution or multigraded PH input generator. The latter is a later Package D consumer.

Admission and completion

This is a library-derived planning contract, not an implementation pickup, agent:ready grant or new primary-paper comparison. Before admission, independently check the statements and concrete reuse at the current develop head. Preserve existing public APIs; executable definitions must avoid Classical choice and noncomputable real comparisons on their runtime path, while semantic adapters may remain noncomputable.

Implementation uses the normal draft-develop-PR workflow, owning imports and append-only public theorem pins, meaningful executed fixtures plus kernel-checked semantic consumers, guarded local checks/live axiom coverage, independent final-head mathematical/API and exposition review, exact-head regular review and successful hosted check. No dependency/toolchain, credential, protection, runner, main/release/tag or Pages change.

Activity

  1. t-uda commented on Nov 17, 2026

    @t-uda
    ContributorAuthor

    Design and dependency preparation for the next intake, checked against develop 9d868f11a8277fffa8a568065bb198fc18486a67. #918 is the current implementation unit; this comment dispatches no #925 implementation.

    The old active-driver dependency on #915 is historical: its rank/nullity work is integrated. The remaining API gap is concrete: FiniteInputHomologyDimensions.lean keeps coordinateImages, its membership law and image-cardinality proof private; the public dimension API accepts simplex inputs rather than arbitrary matrices.

    Recommended bounded dependency: extract that existing enumeration argument into a public finite F₂ matrix API, with an executable rank for Matrix (Fin m) (Fin n) (ZMod 2) and a theorem equating it to Module.finrank (ZMod 2) (LinearMap.range M.mulVecLin). Preserve the existing homology-dimension interfaces and ordered outputs by consuming the shared result. Cover rectangular matrices, zero maps, repeated/dependent columns, zero rows and zero columns. Reuse Module.card_eq_pow_finrank and Nat.log_pow; this remains enumeration of 2^n source vectors, not Gaussian elimination or a cubic-time claim. Admission and independent statement review of that small shared dependency precede implementation.

    The main #925 contract then has three concrete layers:

    1. Validate finite rational-grid F₂ matrix representations (dimensions, identities and composition), returning invalid-input separately from failed erosion.
    2. Refine each coordinate using both grids' cuts and their ±ε shifts. Keep boundary points, intervening cells and both tails; prove a monotone rational representative selection preserving the relevant floor indices for a, b, a−ε and b+ε. Include weak/diagonal pairs and n=0.
    3. Transport each computed matrix rank through the existing actual Kan-fiber/map laws CoordinateGrid.appIso_structureMap and isZero_obj_of_not_hasLowerPoint, then prove success iff the existing RankErosion ε, or return a direction, comparable grade pair and exact ranks witnessing failure.

    Package A of #865 is required only for the additional strict lower-distance conclusion ε < dE ≤ dI; it is not a prerequisite for #925's fixed-radius predicate decision. The finite-criterion proof and executed certificate must both be delivered. No #865 B/D expansion, new elimination backend, pin/dependency change or duplicate general-PH evaluator is introduced. Shared Persistence imports/pins/docs will be integrated serially after the current unit.

  2. t-uda commented on Nov 19, 2026

    @t-uda
    ContributorAuthor

    The shared matrix-rank dependency of the 2026-11-17 design checkpoint is integrated: #992 / PR #994, develop b52a553d05a767c4ad6ac6b03401f6077e6a2a53. TDA.Persistence.Reduction.F2Matrix.rank is the public executable rank of Matrix (Fin m) (Fin n) (ZMod 2), with rank_eq_finrank_range, rank_eq_matrixRank, rank_toMatrix', rank–nullity and the two shape bounds; the homology-dimension interfaces consume it with unchanged statements. This completes only that dependency. #925's finite criterion and executable certificate are not started, and this comment dispatches nothing.


    Generated by Claude Code

  3. t-uda commented on Nov 20, 2026

    @t-uda
    ContributorAuthor

    Part 1 of this Issue is integrated: #997 / PR #998, develop 122de80cd8ed5f9d5548a5330d48aa3cb0560038. CoordinateGrid.rankErosion_lan_iff_of_subset proves that RankErosion ε of the actual Kan extensions of modules on two finite grids is equivalent to its inequalities at the comparable pairs of points of any finite grid containing both grids' values and their ±ε shifts, for an arbitrary field and without a finite-dimensionality hypothesis; rankOfStructureMap_lan and its zero form read the ranks on the grid. The test grades are real, and nothing is executable.

    Still open here, as recorded in #997: an executable F₂ matrix representation on a rational grid with its validation and the grid module it defines (ranks through F2Matrix.rank, #992); and the executable test with its pass / failing-direction-and-pair certificate, soundness and completeness, and this Issue's acceptance fixtures. Neither is specified as an Issue or dispatched by this comment.


    Generated by Claude Code

  4. t-uda commented on Nov 20, 2026

    @t-uda
    ContributorAuthor

    Part 2 of this Issue is integrated: #999 / PR #1000, develop fa2a89275280ee905b2bdb30b734c14d2d53c21c. F2GridRep is the executable representation (rational grid values, fiber dimensions, F₂ matrices) with the decidable Valid; F2GridRep.toModule is the actual grid module of a valid representation; and the executable F2GridRep.rankAt at rational grades equals the rank of the actual Kan extension (rankAt_eq, rankAt_eq_of_eq). RatGrid carries the rational grid, its real image and the executable floor without a module.

    Still open here: the executable erosion test with its pass / failing-direction-and-pair certificate, the rational breakpoint grid and its containment of the real breakpoints, soundness and completeness through #997's criterion, and this Issue's acceptance fixtures. It is not specified as an Issue or dispatched by this comment.


    Generated by Claude Code

  5. t-uda commented on Nov 20, 2026

    @t-uda
    ContributorAuthor

    Part 3 of this Issue is integrated: #1001 / PR #1002, develop 1b6c2d9d5906993aae4a7c33e87c010d1f1109dd. With #992 (rank backend), #997 (finite criterion) and #999 (executable representations), all units recorded for this Issue are now on develop.

    What is delivered against this Issue's two deliverables:

    • Finite criterion. CoordinateGrid.rankErosion_lan_iff_of_subset: RankErosion ε of the actual CoordinateGrid.lan extensions is equivalent to its two inequalities at the comparable pairs of points of any finite grid containing both grids' values and their ±ε shifts. The rational form is RatGrid.grid_erosionBreakpoints: the real image of the rational breakpoint grid is that breakpoint grid. This replaces the cell-representative construction sketched in the body by an equivalent proved one (floors in the test grid).
    • Executable certificate. F2GridRep.runErosion R S e returns invalid, pass, or fail w with the direction, the comparable pair of breakpoint grades and the two ranks. runErosion_eq_invalid_iff, runErosion_eq_pass_iff and runErosion_eq_fail characterise the three outcomes for the actual Kan extensions; pass holds exactly when the input is valid and the full weak-pair predicate holds. Ranks are computed by F2Matrix.rank through F2GridRep.rankAt.
    • Fixtures (F2GridErosionExamples): a failure missed by sampling only original grid values, both directions of failure, radius 0 on the diagonal, negative rational values, different grids, zero-dimensional fibers, an empty value list, n = 0, two parameters, invalid inputs, and kernel-checked conclusions about RankErosion in both the passing and the failing case.

    Not delivered, as excluded in the body: the strict certificate ε < dE ≤ dI (#865 Package A), distance minimisation, Gaussian elimination, other fields, an input generator (#865 Package D). Costs are exponential in the fiber dimensions and in the number of coordinates.

    The independent final-head review of PR #1002 judged this Issue's mathematical and implementation requirements discharged by the three units. Closing this Issue, and updating #865 and #227, is left to the owner or orchestrator; this comment does not close it.


    Generated by Claude Code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions