Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Dimensional labeled representative-rounding data

Definition
BeyondConvexity_APTAS_Supplement_RepresentativeData

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-geometryoperations-researchp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science

Representative data contain selected labels EgrpE_{\rm grp}Egrp​, containment groups with chosen member maxima, and a separate packing of the selected objects. The published group record is reused; the separate packing and all geometric predicates are dimensional. Correctness requires the selected labels together with all group members to be a permutation of the input occurrence labels. Each group lies in one valid level, its maximum belongs to the group and contains a real translate of every member, and each level has at most KKK groups. The rounded supply has one maximum copy per retained occurrence.

The separate packing is feasible, and for every feasible input comparison count mmm,

Packable⁡(I,m)⟹(Packable⁡(S^,m)∧bins⁡(Egrp)≤ηm+δ).\operatorname{Packable}(I,m)\Longrightarrow\bigl(\operatorname{Packable}(\widehat S,m)\land\operatorname{bins}(E_{\rm grp})\le\eta m+\delta\bigr).Packable(I,m)⟹(Packable(S,m)∧bins(Egrp​)≤ηm+δ).

Real data express the analytic service; rational data have an explicit finite encoder and an exact real interpretation. No comparison packing or optimal solution is stored in these data. Defaults on out-of-range labels are irrelevant because correctness requires an exact permutation and maximum membership.

Definition code
import Definitions.Def_BeyondConvexity_APTAS_Supplement_TranslationPacking
import Definitions.Def_BeyondConvexity_APTAS_Supplement_LevelValidity
import Definitions.Def_BeyondConvexity_APTAS_RoundingData

noncomputable section

namespace BeyondConvexity.APTAS.Supplement

/-- Pure output data, reusing the published geometry-independent group record. -/
structure RepresentativeData (d : ℕ) (F : Type) where
  separate : List ℕ
  groups : List ContainmentGroup
  separatePacking : TranslationPacking d F

def selected {d : ℕ} (I : Instance d) (labels : List ℕ) : Instance d :=
  labels.map fun i => I.getD i default

def RepresentativeData.rounded {d : ℕ} {F : Type} (R : RepresentativeData d F)
    (I : Instance d) : Instance d :=
  R.groups.flatMap fun g => g.members.map fun _ => I.getD g.maximum default

def RepresentativeData.Correct {d : ℕ} (R : RepresentativeData d ℝ)
    (I : Instance d) (p : LevelPartition ℝ) (K : ℕ) (η δ : ℝ) : Prop :=
  (R.separate ++ R.groups.flatMap ContainmentGroup.members).Perm (List.range I.length) ∧
  (∀ g ∈ R.groups, g.level ≤ p.J ∧ g.maximum ∈ g.members ∧
    ∀ i ∈ g.members, i < I.length ∧ p.level i = g.level ∧
      (I.getD i default).ContainsTranslate (I.getD g.maximum default)) ∧
  (∀ j ≤ p.J, (R.groups.filter fun g => g.level = j).length ≤ K) ∧
  Feasible (selected I R.separate) R.separatePacking ∧
  ∀ m : ℕ, Packable I m → Packable (R.rounded I) m ∧
    (R.separatePacking.bins : ℝ) ≤ η * m + δ

def RepresentativeData.realize {d : ℕ} (R : RepresentativeData d ℚ) : RepresentativeData d ℝ :=
  ⟨R.separate, R.groups, realizePacking R.separatePacking⟩

open RSListDecodingCapacity.AllRates (encNat encList)

def encRepresentativeData {d : ℕ} (R : RepresentativeData d ℚ) : List Bool :=
  encList encNat R.separate ++ encList encContainmentGroup R.groups ++
    encPacking R.separatePacking

end BeyondConvexity.APTAS.Supplement
Source
Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa, STOC 2027 submission #890 (October 2026), Definition 5, printed p.7 / PDF p.8; Section 7, printed p.16 / PDF p.17

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