AFTD Auto-Formalizing Theoretical Domains

random_deletion_inequality_k_ap

theoremverifiedformalization

Let π’œ and π’ž be families in Finset (Finset (Fin n)) such that π’œ is an up-set, π’ž is a down-set, and for every A ∈ π’œ and C ∈ π’ž, the difference A \ C contains a k-term arithmetic progression in Fin n. For each X : Finset (Fin n), let p X : Finset (Fin n) β†’ ℝ be a probability distribution supported on subsets Z βŠ† X with βˆ‘ Z ∈ X.powerset, p X Z = 1. Define W X = βˆ‘ Z ∈ X.powerset, p X Z * (if X \ Z ∈ π’ž then 1 else 0). If W X > 0 for all X, then ((π’œ.card : ℝ) / 2 ^ n) * ((π’ž.card : ℝ) / 2 ^ n) ≀ (1 / (2 ^ n : ℝ)) * βˆ‘ X : Finset (Fin n), (((π’ž.card : ℝ) / 2 ^ n) / W X) * βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0).

Statement

open scoped BigOperators Classical in
theorem random_deletion_inequality_k_ap
    (n k : β„•)
    (π’œ π’ž : Finset (Finset (Fin n)))
    (hA_upper : IsUpperSet (π’œ : Set (Finset (Fin n))))
    (hC_lower : IsLowerSet (π’ž : Set (Finset (Fin n))))
    (h_cross : βˆ€ A ∈ π’œ, βˆ€ C ∈ π’ž, finset_contains_k_ap n k (A \ C))
    (p : Finset (Fin n) β†’ Finset (Fin n) β†’ ℝ)
    (hp_nonneg : βˆ€ X Z, 0 ≀ p X Z)
    (hp_supp : βˆ€ X Z, p X Z β‰  0 β†’ Z βŠ† X)
    (hp_sum : βˆ€ X, βˆ‘ Z ∈ X.powerset, p X Z = 1)
    (W : Finset (Fin n) β†’ ℝ)
    (hW : βˆ€ X, W X = βˆ‘ Z ∈ X.powerset, p X Z * (if X \ Z ∈ π’ž then 1 else 0))
    (hW_pos : βˆ€ X, 0 < W X) :
    ((π’œ.card : ℝ) / 2 ^ n) * ((π’ž.card : ℝ) / 2 ^ n) ≀
      (1 / (2 ^ n : ℝ)) * βˆ‘ X : Finset (Fin n),
        (((π’ž.card : ℝ) / 2 ^ n) / W X) *
          βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)
Formalizes
arXiv:2610.26243 Lemma 2.2 -- Families that intersect in an arithmetic progression
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • finset_contains_k_apA subset s of Fin n contains a k-term arithmetic progression if there exist a and d with 1 ≀ d such that a + i * d is in s for all 0 ≀ i <…

Read back from the Lean

For any natural numbers $n$ and $k$, let $\mathcal{A}$ and $\mathcal{C}$ be families (finsets) of subsets of $\mathrm{Fin}(n)$. Assume: 1. $\mathcal{A}$ is an upper set under inclusion (if $A \in \mathcal{A}$ and $A \subseteq B \subseteq \mathrm{Fin}(n)$, then $B \in \mathcal{A}$). 2. $\mathcal{C}$ is a lower set under inclusion (if $C \in \mathcal{C}$ and $B \subseteq C$, then $B \in \mathcal{C}$). 3. For every $A \in \mathcal{A}$ and $C \in \mathcal{C}$, the set difference $A \setminus C$ contains a $k$-term arithmetic progression (in the sense of finset_contains_k_ap). 4. $p : \mathcal{P}(\mathrm{Fin}(n)) \to \mathcal{P}(\mathrm{Fin}(n)) \to \mathbb{R}$ is a function such that: - $p(X, Z) \ge 0$ for all $X, Z$, - if $p(X, Z) \neq 0$, then $Z \subseteq X$, - for every $X$, $\sum_{Z \subseteq X} p(X, Z) = 1$. 5. $W : \mathcal{P}(\mathrm{Fin}(n)) \to \mathbb{R}$ satisfies $W(X) = \sum_{Z \subseteq X} p(X, Z) \cdot \mathbf{1}_{X \setminus Z \in \mathcal{C}}$ for all $X$. 6. $W(X) > 0$ for all $X$. Then: $$\frac{|\mathcal{A}|}{2^n} \cdot \frac{|\mathcal{C}|}{2^n} \le \frac{1}{2^n} \sum_{X \subseteq \mathrm{Fin}(n)} \left( \frac{|\mathcal{C}| / 2^n}{W(X)} \sum_{Z \subseteq X} p(X, Z) \cdot \mathbf{1}_{Z \text{ contains a } k\text{-AP}} \right)$$ where $\mathbf{1}_P$ is $1$ if $P$ holds and $0$ otherwise.

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

The proof, explained

The proof bounds the product density (|π’œ| / 2^n) * (|π’ž| / 2^n) via a double-counting indicator argument. For any set X and subset Z βŠ† X, whenever X ∈ π’œ and X \ Z ∈ π’ž, the cross-intersection hypothesis implies that Z = X \ (X \ Z) contains a k-term arithmetic progression. Weighting by p X Z, summing over Z βŠ† X, and dividing by W X yields a bound on the indicator 1_{X ∈ π’œ}. Multiplying by |π’ž| / 2^n and summing over all X evaluates the total indicator weight as |π’œ|, after which multiplying by 1 / 2^n produces the final inequality.

  1. For any X and Z βŠ† X, the indicator product satisfies 1_{X ∈ π’œ} Β· (p X Z Β· 1_{X \ Z ∈ π’ž}) ≀ p X Z Β· 1_{finset_contains_k_ap n k Z}.

    Fix X and Z βŠ† X. When X ∈ π’œ and X \ Z ∈ π’ž, the cross-intersection hypothesis `h_cross` guarantees that the set difference X \ (X \ Z) contains a k-term arithmetic progression. Because Z βŠ† X (`Finset.mem_powerset.mp`), the double difference X \ (X \ Z) is equal to Z (`Finset.sdiff_sdiff_eq_self`), so Z contains a k-AP. Thus the product of indicators 1_{X ∈ π’œ} Β· 1_{X \ Z ∈ π’ž} is at most 1_{Z contains a k-AP}. In all other cases, at least one indicator is 0, so the product is 0 and the inequality holds trivially. Multiplying both sides by the non-negative weight p X Z (`mul_le_mul_of_nonneg_left`) yields the pointwise bound.

    lines 20–41

    uses Finset.mem_powerset.mp, Finset.sdiff_sdiff_eq_self, mul_le_mul_of_nonneg_left

      have h_le_Z : βˆ€ (X Z : Finset (Fin n)), Z ∈ X.powerset β†’
          (if X ∈ π’œ then (1 : ℝ) else 0) * (p X Z * (if X \ Z ∈ π’ž then 1 else 0)) ≀
            p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by
        intro X Z hZ
        have hZ_sub : Z βŠ† X := Finset.mem_powerset.mp hZ
        have h_ineq : (if X ∈ π’œ then (1 : ℝ) else 0) * (if X \ Z ∈ π’ž then 1 else 0) ≀
            (if finset_contains_k_ap n k Z then 1 else 0) := by
          by_cases hX : X ∈ π’œ
          Β· by_cases hC : X \ Z ∈ π’ž
            Β· have h_ap : finset_contains_k_ap n k Z := by
                have := h_cross X hX (X \ Z) hC
                rwa [Finset.sdiff_sdiff_eq_self hZ_sub] at this
              simp [hX, hC, h_ap]
            Β· simp only [hX, hC, ↓reduceIte, mul_zero]
              split_ifs <;> linarith
          Β· simp only [hX, ↓reduceIte, zero_mul]
            split_ifs <;> linarith
        have hp := hp_nonneg X Z
        calc
          (if X ∈ π’œ then (1 : ℝ) else 0) * (p X Z * (if X \ Z ∈ π’ž then 1 else 0))
          _ = p X Z * ((if X ∈ π’œ then (1 : ℝ) else 0) * (if X \ Z ∈ π’ž then 1 else 0)) := by ring
          _ ≀ p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := mul_le_mul_of_nonneg_left h_ineq hp
  2. For each X, 1_{X ∈ π’œ} Β· (|π’ž| / 2^n) ≀ ((|π’ž| / 2^n) / W X) * βˆ‘ Z ∈ X.powerset, p X Z * 1_{finset_contains_k_ap n k Z}.

    Summing the pointwise inequality over all Z βŠ† X and distributing the indicator factor (`Finset.mul_sum`, `Finset.sum_le_sum`) gives 1_{X ∈ π’œ} Β· W X ≀ βˆ‘ Z ∈ X.powerset, p X Z * 1_{finset_contains_k_ap n k Z}. Since W X > 0 (`hW_pos`), dividing by W X preserves the inequality (`le_div_iffβ‚€`), isolating 1_{X ∈ π’œ}. Multiplying both sides by the non-negative scalar |π’ž| / 2^n (`mul_le_mul_of_nonneg_right`) and rearranging algebraically yields the desired bound for each X.

    lines 43–64

    uses Finset.mul_sum, Finset.sum_le_sum, le_div_iffβ‚€, mul_le_mul_of_nonneg_right

      have h_le_X : βˆ€ X : Finset (Fin n),
          (if X ∈ π’œ then (1 : ℝ) else 0) * ((π’ž.card : ℝ) / 2 ^ n) ≀
            (((π’ž.card : ℝ) / 2 ^ n) / W X) *
              βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by
        intro X
        have h_sum_le : (if X ∈ π’œ then (1 : ℝ) else 0) * W X ≀
            βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by
          rw [hW X, Finset.mul_sum]
          exact Finset.sum_le_sum (h_le_Z X)
        have hW_pos_X := hW_pos X
        have h_div : (if X ∈ π’œ then (1 : ℝ) else 0) ≀
            (βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)) / W X := by
          rw [le_div_iffβ‚€ hW_pos_X]
          linarith
        have hC_nonneg : 0 ≀ (π’ž.card : ℝ) / 2 ^ n := by positivity
        have := mul_le_mul_of_nonneg_right h_div hC_nonneg
        calc
          (if X ∈ π’œ then (1 : ℝ) else 0) * ((π’ž.card : ℝ) / 2 ^ n)
          _ ≀ ((βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)) / W X) *
                ((π’ž.card : ℝ) / 2 ^ n) := this
          _ = (((π’ž.card : ℝ) / 2 ^ n) / W X) *
                βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by ring
  3. Summing over all X, |π’œ| * (|π’ž| / 2^n) ≀ βˆ‘ X, ((|π’ž| / 2^n) / W X) * βˆ‘ Z ∈ X.powerset, p X Z * 1_{finset_contains_k_ap n k Z}.

    Summing the inequality for each X over all X : Finset (Fin n) (`Finset.sum_le_sum`), the left-hand side is βˆ‘ X, 1_{X ∈ π’œ} * (|π’ž| / 2^n). Factoring out the constant |π’ž| / 2^n (`Finset.sum_mul`) leaves βˆ‘ X, 1_{X ∈ π’œ}, which equals |π’œ| by rewriting the indicator sum as a cardinality sum (`Finset.sum_filter`).

    lines 66–74

    uses Finset.sum_le_sum, Finset.sum_mul, Finset.sum_filter

      have h_sum_all : βˆ‘ X : Finset (Fin n), (if X ∈ π’œ then (1 : ℝ) else 0) * ((π’ž.card : ℝ) / 2 ^ n) ≀
          βˆ‘ X : Finset (Fin n), (((π’ž.card : ℝ) / 2 ^ n) / W X) *
            βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) :=
        Finset.sum_le_sum (fun X _ => h_le_X X)
      rw [← Finset.sum_mul] at h_sum_all
      have h_sum_A : βˆ‘ X : Finset (Fin n), (if X ∈ π’œ then (1 : ℝ) else 0) = (π’œ.card : ℝ) := by
        rw [← Finset.sum_filter]
        simp
      rw [h_sum_A] at h_sum_all
  4. (|π’œ| / 2^n) * (|π’ž| / 2^n) ≀ (1 / 2^n) * βˆ‘ X, ((|π’ž| / 2^n) / W X) * βˆ‘ Z ∈ X.powerset, p X Z * 1_{finset_contains_k_ap n k Z}.

    Since 1 / 2^n β‰₯ 0, multiplying both sides of the summed inequality by 1 / 2^n on the left preserves the inequality (`mul_le_mul_of_nonneg_left`). Ring arithmetic then rewrites (1 / 2^n) * (|π’œ| * (|π’ž| / 2^n)) as (|π’œ| / 2^n) * (|π’ž| / 2^n), matching the theorem conclusion.

    lines 75–82

    uses mul_le_mul_of_nonneg_left

      have h_pow_pos : 0 ≀ (1 : ℝ) / 2 ^ n := by positivity
      have h_final := mul_le_mul_of_nonneg_left h_sum_all h_pow_pos
      calc
        ((π’œ.card : ℝ) / 2 ^ n) * ((π’ž.card : ℝ) / 2 ^ n)
        _ = (1 / (2 ^ n : ℝ)) * ((π’œ.card : ℝ) * ((π’ž.card : ℝ) / 2 ^ n)) := by ring
        _ ≀ (1 / (2 ^ n : ℝ)) * βˆ‘ X : Finset (Fin n),
              (((π’ž.card : ℝ) / 2 ^ n) / W X) *
                βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := h_final
Finset.mem_powerset.mp
An element belongs to the power set of X if and only if it is a subset of X.
Finset.sdiff_sdiff_eq_self
For a subset t βŠ† s, the double relative complement s \ (s \ t) equals t.
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality b ≀ c on the left by a non-negative element a β‰₯ 0 preserves the inequality: a * b ≀ a * c.
Finset.mul_sum
Multiplication on the left distributes over a finite sum: a * βˆ‘ i ∈ s, f i = βˆ‘ i ∈ s, a * f i.
Finset.sum_le_sum
If f i ≀ g i for all i in a finite set s, then βˆ‘ i ∈ s, f i ≀ βˆ‘ i ∈ s, g i.
le_div_iffβ‚€
For c > 0, the inequality a ≀ b / c is equivalent to a * c ≀ b.
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality b ≀ c on the right by a non-negative element a β‰₯ 0 preserves the inequality: b * a ≀ c * a.
Finset.sum_mul
Multiplication on the right distributes over a finite sum: (βˆ‘ i ∈ s, f i) * a = βˆ‘ i ∈ s, (f i * a).
Finset.sum_filter
Summing f a over elements satisfying predicate p equals summing the indicator term `if p a then f a else 0` over the whole set.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open scoped BigOperators Classical in/-- Random-deletion inequality for the product density of k-AP cross-intersecting families (arXiv:2610.26243, Lemma 2.2). -/theorem random_deletion_inequality_k_ap    (n k : β„•)    (π’œ π’ž : Finset (Finset (Fin n)))    (hA_upper : IsUpperSet (π’œ : Set (Finset (Fin n))))    (hC_lower : IsLowerSet (π’ž : Set (Finset (Fin n))))    (h_cross : βˆ€ A ∈ π’œ, βˆ€ C ∈ π’ž, finset_contains_k_ap n k (A \ C))    (p : Finset (Fin n) β†’ Finset (Fin n) β†’ ℝ)    (hp_nonneg : βˆ€ X Z, 0 ≀ p X Z)    (hp_supp : βˆ€ X Z, p X Z β‰  0 β†’ Z βŠ† X)    (hp_sum : βˆ€ X, βˆ‘ Z ∈ X.powerset, p X Z = 1)    (W : Finset (Fin n) β†’ ℝ)    (hW : βˆ€ X, W X = βˆ‘ Z ∈ X.powerset, p X Z * (if X \ Z ∈ π’ž then 1 else 0))    (hW_pos : βˆ€ X, 0 < W X) :    ((π’œ.card : ℝ) / 2 ^ n) * ((π’ž.card : ℝ) / 2 ^ n) ≀      (1 / (2 ^ n : ℝ)) * βˆ‘ X : Finset (Fin n),        (((π’ž.card : ℝ) / 2 ^ n) / W X) *          βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by  have h_le_Z : βˆ€ (X Z : Finset (Fin n)), Z ∈ X.powerset β†’      (if X ∈ π’œ then (1 : ℝ) else 0) * (p X Z * (if X \ Z ∈ π’ž then 1 else 0)) ≀        p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by    intro X Z hZ    have hZ_sub : Z βŠ† X := Finset.mem_powerset.mp hZ    have h_ineq : (if X ∈ π’œ then (1 : ℝ) else 0) * (if X \ Z ∈ π’ž then 1 else 0) ≀        (if finset_contains_k_ap n k Z then 1 else 0) := by      by_cases hX : X ∈ π’œ      Β· by_cases hC : X \ Z ∈ π’ž        Β· have h_ap : finset_contains_k_ap n k Z := by            have := h_cross X hX (X \ Z) hC            rwa [Finset.sdiff_sdiff_eq_self hZ_sub] at this          simp [hX, hC, h_ap]        Β· simp only [hX, hC, ↓reduceIte, mul_zero]          split_ifs <;> linarith      Β· simp only [hX, ↓reduceIte, zero_mul]        split_ifs <;> linarith    have hp := hp_nonneg X Z    calc      (if X ∈ π’œ then (1 : ℝ) else 0) * (p X Z * (if X \ Z ∈ π’ž then 1 else 0))      _ = p X Z * ((if X ∈ π’œ then (1 : ℝ) else 0) * (if X \ Z ∈ π’ž then 1 else 0)) := by ring      _ ≀ p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := mul_le_mul_of_nonneg_left h_ineq hp  have h_le_X : βˆ€ X : Finset (Fin n),      (if X ∈ π’œ then (1 : ℝ) else 0) * ((π’ž.card : ℝ) / 2 ^ n) ≀        (((π’ž.card : ℝ) / 2 ^ n) / W X) *          βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by    intro X    have h_sum_le : (if X ∈ π’œ then (1 : ℝ) else 0) * W X ≀        βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by      rw [hW X, Finset.mul_sum]      exact Finset.sum_le_sum (h_le_Z X)    have hW_pos_X := hW_pos X    have h_div : (if X ∈ π’œ then (1 : ℝ) else 0) ≀        (βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)) / W X := by      rw [le_div_iffβ‚€ hW_pos_X]      linarith    have hC_nonneg : 0 ≀ (π’ž.card : ℝ) / 2 ^ n := by positivity    have := mul_le_mul_of_nonneg_right h_div hC_nonneg    calc      (if X ∈ π’œ then (1 : ℝ) else 0) * ((π’ž.card : ℝ) / 2 ^ n)      _ ≀ ((βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)) / W X) *            ((π’ž.card : ℝ) / 2 ^ n) := this      _ = (((π’ž.card : ℝ) / 2 ^ n) / W X) *            βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by ring  have h_sum_all : βˆ‘ X : Finset (Fin n), (if X ∈ π’œ then (1 : ℝ) else 0) * ((π’ž.card : ℝ) / 2 ^ n) ≀      βˆ‘ X : Finset (Fin n), (((π’ž.card : ℝ) / 2 ^ n) / W X) *        βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) :=    Finset.sum_le_sum (fun X _ => h_le_X X)  rw [← Finset.sum_mul] at h_sum_all  have h_sum_A : βˆ‘ X : Finset (Fin n), (if X ∈ π’œ then (1 : ℝ) else 0) = (π’œ.card : ℝ) := by    rw [← Finset.sum_filter]    simp  rw [h_sum_A] at h_sum_all  have h_pow_pos : 0 ≀ (1 : ℝ) / 2 ^ n := by positivity  have h_final := mul_le_mul_of_nonneg_left h_sum_all h_pow_pos  calc    ((π’œ.card : ℝ) / 2 ^ n) * ((π’ž.card : ℝ) / 2 ^ n)    _ = (1 / (2 ^ n : ℝ)) * ((π’œ.card : ℝ) * ((π’ž.card : ℝ) / 2 ^ n)) := by ring    _ ≀ (1 / (2 ^ n : ℝ)) * βˆ‘ X : Finset (Fin n),          (((π’ž.card : ℝ) / 2 ^ n) / W X) *            βˆ‘ Z ∈ X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := h_final
See it in the graphDiscuss this resultChallenge it