Digital images with small white components: an improved lower bound at k=10

Abstract

For α ∈ {4,8} and k ∈ ℕ, let Φ_α(k) be the supremal white pixel density of a colouring of ℤ² all of whose white α-connected components have at most k cells. Fridberg determined Φ₈ completely and Φ₄ on a set of k of natural density 1/2, and identified a set U of density 1/4 on which Φ₄(k) is strictly below his upper bound F₄(k) but is not computed; k=10 and k=11 are the first two cells of U beyond the two he evaluates by hand. We exhibit a colouring of ℤ², periodic with respect to a sublattice of index 59, whose white 4-components have at most 10 cells and whose density is 40/59. Hence Φ₄(10) ≥ 40/59, which improves the bound 61/90 printed in that paper; the cell stays open, since neither that paper nor this one proves any explicit upper bound on Φ₄(10) smaller than F₄(10)=20/29. We also give a machine-checked reproduction of the published data: the nine values of Φ₄(k) for k ≤ 9 and the twelve values of Φ₈(k) for k ≤ 12 are each matched from below by a witness found here by exhaustive search, not transcribed from the source's figures (the matching upper bounds are Fridberg's and are not reproved), the exact cells Φ₄(1)=Φ₄(2)=1/2, Φ₈(1)=1/4 and Φ_α(0)=0 are proved from both sides, and a general averaging bound gives Φ_α(k) ≤ k/(k+1) and Φ₈(k) ≤ k/4. All statements are formally verified in Lean 4; the component bounds are proved for ℤ² and never for a quotient torus, and the densities are the liminf of the original definition.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   a5d286c61402d95b9aab800acc773c69b7bc6a69fa00f70e256729a3e2cff647