/- Copyright 2025 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 730

References:

    erdosproblems.com/730

    A129515

    PALOMAR-2026-08-22-000001: a Lean 4 proof that there are infinitely many such pairs, checked by Comparator against the statement S.Infinite below and registered with the Palomar registry. The proof follows an argument posted on the erdosproblems.com forum (Liam Price, 24 June 2026), which shows that there are infinitely many consecutive pairs $(n, n+1)$.

@[expose] public sectionnamespace Erdos730abbrev S := {(n, m) : ℕ × ℕ | n < m ∧ n.centralBinom.primeFactors = m.centralBinom.primeFactors}

Are there infinitely many pairs of integers $n < m$ such that $\binom{2n}{n}$ and $\binom{2m}{m}$ have the same set of prime divisors?

Yes: there are infinitely many consecutive pairs $(n, n+1)$. The formal proof registered as [PALOMAR-2026-08-22-000001] proves S.Infinite for this S.

@[category research solved, question, AMS 11, formal_proof using lean4 at "https://github.com/williamjblair/lean-proofs/blob/03729c9cbb0b602f5a828bb850c85e84c5a6d460/ErdosProblems/Erdos730/FullDensityTheorem.lean#L40"] theorem erdos_730 : S.Infinite := ⊢ S.Infinite All goals completed! 🐙

For example, $(87,88)$ and $(607,608)$ are such pairs.

@[category textbook, AMS 11] theorem erdos_730.variants.explicit_pairs : {(87, 88), (607, 608)} ⊆ S := ⊢ {(87, 88), (607, 608)} ⊆ S ⊢ (87, 88) ∈ S⊢ (607, 608) ∈ S ⊢ (87, 88) ∈ S⊢ (607, 608) ∈ S refine ⟨⊢ 607 < 608 All goals completed! 🐙, ?_⟩ all_goals ⊢ ((2 * 607).descFactorial 607 / Nat.factorial 607).primeFactors = ((2 * 608).descFactorial 608 / Nat.factorial 608).primeFactors All goals completed! 🐙

There are examples where $(n, m) ∈ S$ with $m ≠ n + 1$.

(Found by AlphaProof, although it was implicit already in [A129515])

@[category research solved, AMS 11] theorem erdos_730.variants.delta_ne_one : ∃ (n m : ℕ), (n, m) ∈ S ∧ m ≠ n + 1 := ⊢ ∃ n m, (n, m) ∈ S ∧ m ≠ n + 1 ⊢ ∃ n m, (n < m ∧ n.centralBinom.primeFactors = m.centralBinom.primeFactors) ∧ ¬m = n + 1 ⊢ ∃ m, (10003 < m ∧ (Nat.centralBinom 10003).primeFactors = m.centralBinom.primeFactors) ∧ ¬m = 10003 + 1 ⊢ (10003 < 10005 ∧ (Nat.centralBinom 10003).primeFactors = (Nat.centralBinom 10005).primeFactors) ∧ ¬10005 = 10003 + 1 ⊢ ∀ (a : ℕ), Nat.Prime a → (a ∣ Nat.choose 20006 10003 ↔ a ∣ Nat.choose 20010 10005) simp_rw ⊢ ∀ (a : ℕ), Nat.Prime a → (a ∣ Nat.choose 20006 10003 ↔ a ∣ Nat.choose 20010 10005)⊢ ∀ (a : ℕ), Nat.Prime a → (a ∣ Nat.descFactorial 20006 10003 / Nat.factorial 10003 ↔ a ∣ Nat.descFactorial 20010 10005 / Nat.factorial 10005)] p:ℕhp:Nat.Prime p⊢ p ∣ Nat.descFactorial 20006 10003 / Nat.factorial 10003 ↔ p ∣ Nat.descFactorial 20010 10005 / Nat.factorial 10005 p:ℕhp:Nat.Prime p⊢ p ∣ Nat.descFactorial 20006 10003 / Nat.factorial 10003 → p ∣ Nat.descFactorial 20010 10005 / Nat.factorial 10005p:ℕhp:Nat.Prime p⊢ p ∣ Nat.descFactorial 20010 10005 / Nat.factorial 10005 → p ∣ Nat.descFactorial 20006 10003 / Nat.factorial 10003 all_goals exact fun h' => or_self_iff.1 (hp.dvd_mul.1 ( h'.trans (p:ℕhp:Nat.Prime ph':p ∣ Nat.descFactorial 20010 10005 / Nat.factorial 10005⊢ Nat.descFactorial 20010 10005 / Nat.factorial 10005 ∣ Nat.descFactorial 20006 10003 / Nat.factorial 10003 * (Nat.descFactorial 20006 10003 / Nat.factorial 10003) refine' of_decide_eq_true (p:ℕhp:Nat.Prime ph':p ∣ Nat.descFactorial 20010 10005 / Nat.factorial 10005⊢ decide (Nat.descFactorial 20010 10005 / Nat.factorial 10005 ∣ Nat.descFactorial 20006 10003 / Nat.factorial 10003 * (Nat.descFactorial 20006 10003 / Nat.factorial 10003)) = ?m.96 All goals completed! 🐙 : _ = ↑_))))end Erdos730