AFTD Auto-Formalizing Theoretical Domains

linear_max_subset_sum_avoiding_size

def

For a real number $c > 0$ and integer $n \ge 1$, $f_c(n)$ is the maximum cardinality of a subset of $\{1, \dots, \lfloor cn \rfloor\}$ avoiding subset sum $n$.

Statement

noncomputable def linear_max_subset_sum_avoiding_size (c : ℝ) (n : ℕ) : ℕ
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
  • 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

The declaration defines a function linear_max_subset_sum_avoiding_size that takes a real number c and a natural number n, and returns a natural number: the maximum cardinality among all subsets A of $\{1, \dots, \lfloor c \cdot n \rfloor_+\}$ such that every subset B ⊆ A with sum n is empty (i.e., no subset of A has sum n, with the empty set being the only possible subset with sum n when n = 0).

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 maximum size f_c(n) of a subset of {1, ..., floor(cn)} avoiding subset sum n. -/
noncomputable def linear_max_subset_sum_avoiding_size (c : ℝ) (n : ℕ) : ℕ := max_subset_sum_avoiding_size ⌊c * (n : ℝ)⌋₊ n
See it in the graphDiscuss this resultChallenge it