AFTD Auto-Formalizing Theoretical Domains

subset_sum_avoiders

def

The collection of all subsets of $\{1, \dots, M\}$ that avoid subset sum $n$.

Statement

noncomputable def subset_sum_avoiders (M n : ℕ) : Finset (Finset ℕ)
Defined in
arXiv:2611.17205 Forbidden subset sums in a linear range: an inverse theorem and the Erdős-Graham irregularity problem, Section 1.1
Verified
14 Nov 2026
Axioms
none listed
Built on 1
  • avoids_subset_sumA finite set of natural numbers $A$ avoids a target integer $n$ if no subset of $A$ has sum equal to $n$, meaning every subset of $A$…
Used by 1
  • max_subset_sum_avoiding_sizeFor positive integers $M$ and $n$, $F(M, n)$ is the maximum cardinality of a subset of $\{1, \dots, M\}$ that avoids subset sum $n$.

Read back from the Lean

subset_sum_avoiders M n is defined as the finite set of all subsets $A$ of the integer range $\{1, \dots, M\}$ such that $A$ avoids the subset sum $n$ (avoids_subset_sum A n), which means that for every subset $B \subseteq A$, if the sum of the elements of $B$ is $n$, then $B = \emptyset$ (i.e., no non-empty subset of $A$ sums to $n$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The collection of all subsets of {1, ..., M} that avoid subset sum n. -/
noncomputable def subset_sum_avoiders (M n : ℕ) : Finset (Finset ℕ) := @Finset.filter (Finset ℕ) (fun A => avoids_subset_sum A n) (Classical.decPred _) (Finset.Icc 1 M).powerset
See it in the graphDiscuss this resultChallenge it