Cosmology Domain Coarsening2 D Row Interface

The row interface

In image processing and physics, coarsening means grouping neighboring cells that share a property into larger regions. A simple way to do this on a two-dimensional grid is to coarsen each horizontal row independently, then count the resulting regions. The declaration rowInterface is the part of that count that comes from the boundaries: it sums, over every row, the number of places where the property changes as you move left to right. Think of a striped flag; the row interface is the total number of color changes across all stripes, not the number of stripes themselves.

The framework's machine-checked library of formal theorems proves an exact identity for this separable coarsening. For any grid whose rows are all nonempty, the total number of regions produced by coarsening row by row equals the row interface plus the number of rows. In symbols, rowCost rows = rowInterface rows + rows.length. This is the two-dimensional analogue of the one-dimensional law that a line of cells coarsens into (its boundaries) plus one region. The theorem is dimension-free in its core argument, and it holds for any grid, regardless of how wide the rows are.

The practical consequence is that the cost of this coarsening depends on the perimeter of the regions, not on the area they cover. A large grid with few internal boundaries costs little to coarsen; a small grid with many boundaries costs more. This sub-extensive behavior is what makes the result useful: it shows that the recognition engine's state and work, in this two-dimensional model, scale with the interface that separates domains rather than with the total number of cells. The true two-dimensional coarsening, which also merges vertically, is never worse than this row-wise bound, so the theorem provides a clean upper limit on the cost.

What the declaration does not claim is just as important. It does not describe the full two-dimensional component coarsening, which merges regions vertically as well as horizontally; that exact count can be smaller than the row-wise cost. It also does not claim that a two-dimensional interface is always a simple curve. In two dimensions an interface can be multiply connected, which is why the exact one-dimensional identity becomes an inequality in the full two-dimensional case. The row interface is a building block, not the whole story, and the theorem's value is in the clean bound it provides.

/-- **The separable coarsening cost = horizontal interface + number of rows.** For any 2D grid whose rows are
all nonempty, coarsening each row independently carries exactly (the total horizontal interface) plus (the
number of rows) super-regions. This is the exact per-axis generalization of the 1D law `runs = boundaries + 1`
summed over rows, and it depends only on the interface and the row count, never on the row widths (the area).
The true 2D component coarsening merges vertically as well, so it carries at most this many super-regions. -/
theorem rowwise_cost_eq (rows : List (List α)) (h : ∀ r ∈ rows, r ≠ []) :
    rowCost rows = rowInterface rows + rows.length := by
  induction rows with
  | nil => simp
  | cons r rs ih =>
    rw [rowCost_cons, rowInterface_cons, runs_eq_of_ne_nil r (h r (List.mem_cons.mpr (Or.inl rfl)))]
    rw [ih (fun row hrow => h row (List.mem_cons.mpr (Or.inr hrow)))]
    simp [List.length_cons]
    ring

/-- The carried cost is bounded by the interface, not the area: the separable coarsening cost is
`rowInterface + rows.length`, with no dependence on the row widths. -/
theorem rowwise_cost_independent_of_width (rows : List (List α)) (h : ∀ r ∈ rows, r ≠ []) :
    rowCost rows = rowInterface rows + rows.length :=
  rowwise_cost_eq rows h

What this page does not claim

The full two-dimensional component coarsening cost, which can be smaller than the row-wise bound because it merges vertically. That a two-dimensional interface is always a simple curve; it can be multiply connected. A claim about the physical recognition-to-linking bridge, which remains open.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Cosmology/DomainCoarsening2D.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: