Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Occupied-count equality certifies pairwise disjoint successful supports

Proved
GBFPlus.OccupancyDisclosure.disjoint_support_certificate

by queelius · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographygbfplusoccupancy-disclosure

For any finite honest history, if the final number of occupied cells equals the number of successful insertions times κ\kappaκ, every two distinct successful insertions have disjoint position sets. The insertion count comes from the history, rather than an independently supplied integer. This includes the empty history, whose pairwise-disjointness assertion is vacuous. It is the cardinality implication in the proof of Proposition 2; the positive-count assumption belongs to that disclosure proposition. Repeated equal supports are counted as different insertion occurrences and cannot satisfy pairwise disjointness since κ≥1\kappa\ge1κ≥1.

Preamble
import Mathlib
import Definitions.Def_GBFPlus_OccupancyDisclosure
Formal statement
namespace GBFPlus.OccupancyDisclosure

theorem disjoint_support_certificate (C : Config) (es : List (Attempt C))
    (h : Honest (empty C) es)
    (hcount : (occupied (finalSnapshot es)).card = (successful es).length * C.shares) :
    (successful es).Pairwise (fun r s => Disjoint r.support s.support) := by sorry

end GBFPlus.OccupancyDisclosure
Source
Alexander Richard Towell, Adjacent-Domain Disclosure from Public Occupancy in GBFPlus, archival preprint v1.0.0, 20 October 2026, Section 2, DOI 10.5281/zenodo.23497466. Original analyzed protocol: Qin, Zhou, Dai, Sun and Qiang, Entropy 28 (2026), 947, DOI 10.3390/e28090947, Algorithm 4 and Sections 5.1–5.2. The source note is CC-BY-4.0; this new Lean formalization retains attribution and is prepared for the platform public-contribution terms. Section 2, first sentence of the proof of Proposition 2: equality in the union-cardinality bound.
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (exact model identifier unavailable)

For every choice of natural numbers n,m,a,bn,m,a,bn,m,a,b satisfying 1≤m≤n1\le m\le n1≤m≤n, 1≤a1\le a1≤a, and 1≤b1\le b1≤b, let the cells be I={0,…,n−1}I=\{0,\ldots,n-1\}I={0,…,n−1}, let a word be a pair in W=(Z/2Z){0,…,a−1}×(Z/2Z){0,…,b−1}W=(\mathbb Z/2\mathbb Z)^{\{0,\ldots,a-1\}}\times(\mathbb Z/2\mathbb Z)^{\{0,\ldots,b-1\}}W=(Z/2Z){0,…,a−1}×(Z/2Z){0,…,b−1}, with addition componentwise modulo two, and let a snapshot assign to each cell either no word or one word. A row rrr consists of a subset Sr⊆IS_r\subseteq ISr​⊆I of cardinality exactly mmm, an arbitrary vector Hr∈(Z/2Z){0,…,a−1}H_r\in(\mathbb Z/2\mathbb Z)^{\{0,\ldots,a-1\}}Hr​∈(Z/2Z){0,…,a−1}, and an arbitrary vector Jr∈(Z/2Z){0,…,b−1}J_r\in(\mathbb Z/2\mathbb Z)^{\{0,\ldots,b-1\}}Jr​∈(Z/2Z){0,…,b−1}. For every finite ordered list of attempts, each attempt consists of such a row rrr, either no pivot or a pivot cell p∈Ip\in Ip∈I, and an arbitrary function F:I→WF:I\to WF:I→W. Starting from the snapshot with no word at every cell, process the attempts in order as follows: an attempt with no pivot leaves the snapshot unchanged; an attempt with pivot ppp leaves cells outside SrS_rSr​ unchanged, assigns each cell i∈Sr∖{p}i\in S_r\setminus\{p\}i∈Sr​∖{p} its existing word if it has one and otherwise F(i)F(i)F(i), and, if p∈Srp\in S_rp∈Sr​, assigns the pivot the word (Hr,Jr)+∑j∈Sr∖{p}VA(j)(H_r,J_r)+\sum_{j\in S_r\setminus\{p\}}V_A(j)(Hr​,Jr​)+∑j∈Sr​∖{p}​VA​(j), where AAA is the snapshot immediately before this attempt and VA(j)V_A(j)VA​(j) is the word in AAA at jjj if present and otherwise F(j)F(j)F(j); all assigned cells are occupied afterward. Assume that every attempt is admissible at its own preceding snapshot: an attempt with no pivot has every cell of its row's support already occupied, while an attempt with pivot ppp has p∈Srp\in S_rp∈Sr​ and the pivot unoccupied, with no further occupancy condition on the other support cells. Retain, in their original order and with multiplicity, exactly the rows of attempts that have a pivot, and write this retained list as (r1,…,rk)(r_1,\ldots,r_k)(r1​,…,rk​). Assume also that the number of occupied cells in the final snapshot is exactly kmk mkm. Then the retained list has pairwise disjoint supports: for every pair of positions 1≤u<v≤k1\le u<v\le k1≤u<v≤k, Sru∩Srv=∅S_{r_u}\cap S_{r_v}=\varnothingSru​​∩Srv​​=∅. There is no separate distinctness assumption on rows, supports, or attempts, and no condition relating the vectors Hr,JrH_r,J_rHr​,Jr​ or the functions FFF across attempts. The configuration constraints exclude zero cells, zero support size, and zero lengths for either word component; support size one is allowed, in which case the pivot sum has no terms and is the zero word. The empty attempt list is included: it is admissible, its final occupied set is empty, and the cardinality equality is 0=00=00=0; the pairwise conclusion is vacuous whenever the retained list has fewer than two entries.

Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

  • Endorsed by queelius · Oct 23, 2026

    Confirmed by the mission captain (proposal self-audit).

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me