Cosmology Domain Coarsening2 D Of

What the theorem proves

In a two-dimensional grid, imagine coloring each cell by its charge, then grouping adjacent cells of the same color into regions. The theorem in question proves a precise accounting identity for a simplified version of this grouping, where each row of the grid is processed independently. For any grid with nonempty rows, the total number of groups produced equals the total number of horizontal color-boundaries plus the number of rows. Written in symbols, rowCost = rowInterface + rows.length, where rowCost counts groups and rowInterface counts horizontal boundaries. This identity holds exactly, with no dependence on the widths of the rows, meaning the area of the grid plays no role in the count.

The identity generalizes a one-dimensional law. On a line, a sequence of colored cells splits into runs, and the number of runs always equals the number of internal boundaries plus one. Summing that law across rows gives the two-dimensional version, and the machine-checked library of formal theorems proves it as rowwise_cost_eq. The proof is a theorem in the strongest sense: it is verified by a computer, with no unproved assumptions beyond the standard logical axioms. This means the statement is not a heuristic or an approximation; it is a derived fact about the formal model of rows and boundaries.

What the declaration does not claim is equally important. It does not prove the analogous identity for true two-dimensional connected regions, where vertical merges also occur. In that case, the exact equality becomes an inequality: the number of connected components is at most the number of bichromatic edges plus one. The theorem proves this upper bound, not an equality. It also does not claim anything about the physical speed of light or any empirical constant. The result is purely combinatorial, about the cost of a specific coarsening procedure on a grid, and its significance is that the cost scales with the perimeter of regions, not their area, which is a useful property for any system that tracks boundaries.

/-- **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

/-- **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

What this page does not claim

The theorem does not prove an exact equality for true 2D connected components, only an upper bound. The theorem does not derive any physical constant or empirical value. The theorem does not claim the 2D diamond lattice instance is fully wired into the graph-theoretic lemma.

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: