Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Incompressibility counting bound.

Proved
DigitalImmortality.Refined.few_small_codewords

by raver1975 · Sep 11, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogapplications

Incompressibility counting bound. Under any injective encoding of connectomes as natural numbers, at most B connectomes are assigned a codeword whose numerical value is < B.

theorem DigitalImmortality.Refined.few_small_codewords(N B : ℕ) {enc : Connectome N → ℕ}
    (hinj : Function.Injective enc) :
    (Finset.univ.filter (fun c : Connectome N => enc c < B)).card ≤ B := by sorry

Formalization Note Transplanted verbatim from the Aether Catalog source Applications/MindEncodingRefined.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.

Preamble
-- Thm stub generated from Applications/NeuralCoding/MindEncodingRefined.lean
import Mathlib
import Definitions.Def_Applications_NeuralCoding_MindEncodingRefined

/-!
# Digital Immortality, Refined: Merging, Directionality, and Incompressibility

This file extends the information-theoretic model of a neural connectome with
several new, self-contained results.  A connectome on `N` neurons is a Boolean
assignment on the `synapseSlots N = N.choose 2` unordered pairs of neurons
(one flag per potential synapse).

The new theorems are:

* `synapseSlots_add` — **superadditivity of mind-merging**: joining an `M`-neuron
  brain and an `N`-neuron brain creates exactly `M * N` *new* cross-synapse
  slots beyond the two brains' own slots, i.e.
  `synapseSlots (M + N) = synapseSlots M + synapseSlots N + M * N`.
* `connectome_count_mono` — the number of connectomes is monotone in the neuron
  count.
* `directed_eq_two_mul`, `directed_count_sq` — modelling directed synapses
  doubles the slot count, hence *squares* the number of distinguishable minds.
* `card_connectome`, `card_weighted_connectome` — exact state counts for Boolean
  and `w`-valued (weighted) synapses.
* `few_small_codewords` — an incompressibility counting bound: under any
  injective code, at most `B` connectomes receive a codeword of numerical value
  `< B`.
* `most_incompressible` — consequently at least `2 ^ synapseSlots N - B`
  connectomes are *incompressible* below `B` (the overwhelming majority when
  `B ≪ 2 ^ synapseSlots N`).
* `synapseSlots_lower_real`, `neuron_count_bound`, `neuron_count_sqrt_bound` —
  feeding the quadratic slot count into the Bekenstein bound yields an explicit
  upper bound on the number of neurons whose connectome fits in a given physical
  region: `N ≤ 1 + √(2 · Bekenstein capacity)`.
-/

open DigitalImmortality.Refined

open scoped BigOperators
open Real




/-! ### State counts -/



/-! ### Arithmetic of the slot count -/






/-! ### Incompressibility (counting / Kolmogorov flavour) -/
Formal statement
theorem DigitalImmortality.Refined.few_small_codewords(N B : ℕ) {enc : Connectome N → ℕ}
    (hinj : Function.Injective enc) :
    (Finset.univ.filter (fun c : Connectome N => enc c < B)).card ≤ B := by sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/Applications/MindEncodingRefined.lean#L101

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me