/-
Copyright 2026 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 FormalConjecturesUtilErdős Problem 698
References:
[ErSz78] Erdős, P. and Szekeres, G., Some number theoretic problems on binomial coefficients. Austral. Math. Soc. Gaz. (1978), 97-99.
[Be11] Bergman, George M., On common divisors of multinomial coefficients. Bull. Aust. Math. Soc. (2011), 138--157.
@[expose] public sectionnamespace Erdos698open FilterIs there some $h(n)\to \infty$ such that for all $2\leq i<j\leq n/2$ $$\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq h(n)?$$
This was resolved by Bergman [Be11], who proved that for any $2\leq i<j\leq n/2$ $$\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \gg n^{1/2}\frac{2^i}{i^{3/2}},$$ where the implied constant is absolute.
The linked formal proof (van Doorn and Aristotle, see erdos_698.variants.bergman) gives the
explicit bound $\gcd > \frac{2^i \sqrt n}{4 i \sqrt{i - 1}}$, so $h(n) = \lfloor \sqrt n / 4 \rfloor$
works since $i \sqrt{i - 1} \le 2^i$ for $i \ge 2$.
@[category research solved, question, AMS 5 11, formal_proof using lean4 at
"https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos698.lean#L452"]
theorem erdos_698 :
∃ h : ℕ → ℕ, Tendsto h atTop atTop ∧
∀ n i j : ℕ, 2 ≤ i → i < j → j ≤ n / 2 →
h n ≤ Nat.gcd (n.choose i) (n.choose j) := ⊢ ∃ h, Tendsto h atTop atTop ∧ ∀ (n i j : ℕ), 2 ≤ i → i < j → j ≤ n / 2 → h n ≤ (n.choose i).gcd (n.choose j)
All goals completed! 🐙A problem of Erdős and Szekeres, who observed that $$\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq \frac{\binom{n}{i}}{\binom{j}{i}} \geq 2^i$$ (in particular the greatest common divisor is always $>1$).
right n:ℕi:ℕj:ℕhi:1 ≤ ihij:i < jhj:j ≤ n / 2x✝:1 ≤ ihjn:2 * j ≤ nhcpos:0 < j.choose ihcR:0 < ↑(j.choose i)hid:n.choose j * j.choose i = n.choose i * (n - i).choose (j - i)hdvd:n.choose i ∣ (n.choose i).gcd (n.choose j) * j.choose ihgpos:0 < (n.choose i).gcd (n.choose j)hle:n.choose i ≤ (n.choose i).gcd (n.choose j) * j.choose ihgrow:∀ k ≤ j, 2 ^ k * j.choose k ≤ n.choose k⊢ 2 ^ i * ↑(j.choose i) ≤ ↑(n.choose i)
exact_mod_cast hgrow i hij.le All goals completed! 🐙This inequality is sharp for $i=1$, $j=p$, and $n=2p$.
@[category research solved, AMS 5 11]
theorem erdos_698.variants.erdos_szekeres_sharp (p : ℕ) (hp : p.Prime) (hp2 : 2 < p) :
(Nat.gcd ((2 * p).choose 1) ((2 * p).choose p) : ℝ) =
((2 * p).choose 1 : ℝ) / (p.choose 1 : ℝ) ∧
((2 * p).choose 1 : ℝ) / (p.choose 1 : ℝ) = (2 : ℝ) ^ 1 := by p:ℕhp:Nat.Prime php2:2 < p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have := Fact.mk hp p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have hp0 : 0 < p := hp.pos p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
-- `choose (2p) p ≡ 2 (mod p)` by Lucas' theorem
have hlucas : (2 * p).choose p ≡ 2 [MOD p] := by
have h := Choose.choose_modEq_choose_mod_mul_choose_div_nat (p := p) (n := 2 * p) (k := p) p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have e1 : 2 * p % p = 0 := by p:ℕhp:Nat.Prime php2:2 < p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]e1:2 * p % p = 0⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 simp p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]e1:2 * p % p = 0⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]e1:2 * p % p = 0⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have e2 : p % p = 0 := by p:ℕhp:Nat.Prime php2:2 < p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]e1:2 * p % p = 0e2:p % p = 0⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 simp p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]e1:2 * p % p = 0e2:p % p = 0⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]e1:2 * p % p = 0e2:p % p = 0⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have e3 : 2 * p / p = 2 := Nat.mul_div_cancel _ hp0 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]e1:2 * p % p = 0e2:p % p = 0e3:2 * p / p = 2⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have e4 : p / p = 1 := Nat.div_self hp0 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < ph:(2 * p).choose p ≡ (2 * p % p).choose (p % p) * (2 * p / p).choose (p / p) [MOD p]e1:2 * p % p = 0e2:p % p = 0e3:2 * p / p = 2e4:p / p = 1⊢ (2 * p).choose p ≡ 2 [MOD p] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
simpa [e1, e2, e3, e4, Nat.choose_one_right] using h p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have hpnd : ¬ p ∣ (2 * p).choose p := by
intro hd p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hd:p ∣ (2 * p).choose p⊢ False p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have h0 : (2 * p).choose p ≡ 0 [MOD p] := (Nat.modEq_zero_iff_dvd).2 hd p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hd:p ∣ (2 * p).choose ph0:(2 * p).choose p ≡ 0 [MOD p]⊢ False p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have h2 : 2 ≡ 0 [MOD p] := hlucas.symm.trans h0 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hd:p ∣ (2 * p).choose ph0:(2 * p).choose p ≡ 0 [MOD p]h2:2 ≡ 0 [MOD p]⊢ False p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have : p ∣ 2 := (Nat.modEq_zero_iff_dvd).1 h2 p:ℕhp:Nat.Prime php2:2 < pthis✝:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hd:p ∣ (2 * p).choose ph0:(2 * p).choose p ≡ 0 [MOD p]h2:2 ≡ 0 [MOD p]this:p ∣ 2⊢ False p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have := Nat.le_of_dvd (by p:ℕhp:Nat.Prime php2:2 < pthis✝:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hd:p ∣ (2 * p).choose ph0:(2 * p).choose p ≡ 0 [MOD p]h2:2 ≡ 0 [MOD p]this:p ∣ 2⊢ 0 < 2 p:ℕhp:Nat.Prime php2:2 < pthis✝¹:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hd:p ∣ (2 * p).choose ph0:(2 * p).choose p ≡ 0 [MOD p]h2:2 ≡ 0 [MOD p]this✝:p ∣ 2this:p ≤ 2⊢ False p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 norm_num All goals completed! 🐙 p:ℕhp:Nat.Prime php2:2 < pthis✝¹:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hd:p ∣ (2 * p).choose ph0:(2 * p).choose p ≡ 0 [MOD p]h2:2 ≡ 0 [MOD p]this✝:p ∣ 2this:p ≤ 2⊢ False p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1) this p:ℕhp:Nat.Prime php2:2 < pthis✝¹:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hd:p ∣ (2 * p).choose ph0:(2 * p).choose p ≡ 0 [MOD p]h2:2 ≡ 0 [MOD p]this✝:p ∣ 2this:p ≤ 2⊢ False p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
omega p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have hev : 2 ∣ (2 * p).choose p := by
have := Nat.two_dvd_centralBinom_of_one_le hp0 p:ℕhp:Nat.Prime php2:2 < pthis✝:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose pthis:2 ∣ p.centralBinom⊢ 2 ∣ (2 * p).choose p p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
simpa [Nat.centralBinom, two_mul] using this p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have hg : Nat.gcd ((2 * p).choose 1) ((2 * p).choose p) = 2 := by
rw [Nat.choose_one_right p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ (2 * p).gcd ((2 * p).choose p) = 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ (2 * p).gcd ((2 * p).choose p) = 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ (2 * p).gcd ((2 * p).choose p) = 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
apply Nat.dvd_antisymm a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ 2 ∣ (2 * p).gcd ((2 * p).choose p) p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
· a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 have hg1 : Nat.gcd (2 * p) ((2 * p).choose p) ∣ 2 * p := Nat.gcd_dvd_left _ _ a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have hcop : Nat.Coprime (Nat.gcd (2 * p) ((2 * p).choose p)) p := by p:ℕhp:Nat.Prime php2:2 < p⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * phcop:((2 * p).gcd ((2 * p).choose p)).Coprime p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
apply Nat.Coprime.symm p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * p⊢ p.Coprime ((2 * p).gcd ((2 * p).choose p))a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * phcop:((2 * p).gcd ((2 * p).choose p)).Coprime p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
rw [Nat.Prime.coprime_iff_not_dvd hp p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * p⊢ ¬p ∣ (2 * p).gcd ((2 * p).choose p) p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * p⊢ ¬p ∣ (2 * p).gcd ((2 * p).choose p)a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * phcop:((2 * p).gcd ((2 * p).choose p)).Coprime p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * p⊢ ¬p ∣ (2 * p).gcd ((2 * p).choose p)a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * phcop:((2 * p).gcd ((2 * p).choose p)).Coprime p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
intro hd p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * phd:p ∣ (2 * p).gcd ((2 * p).choose p)⊢ Falsea p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * phcop:((2 * p).gcd ((2 * p).choose p)).Coprime p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
exact hpnd (hd.trans (Nat.gcd_dvd_right _ _))a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * phcop:((2 * p).gcd ((2 * p).choose p)).Coprime p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg1:(2 * p).gcd ((2 * p).choose p) ∣ 2 * phcop:((2 * p).gcd ((2 * p).choose p)).Coprime p⊢ (2 * p).gcd ((2 * p).choose p) ∣ 2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
exact hcop.dvd_of_dvd_mul_right hg1 All goals completed! 🐙 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
· a p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose p⊢ 2 ∣ (2 * p).gcd ((2 * p).choose p) p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 exact Nat.dvd_gcd (Dvd.intro _ rfl) hev p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
have hpR : (p : ℝ) ≠ 0 := by exact_mod_cast hp0.ne' p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ ↑(((2 * p).choose 1).gcd ((2 * p).choose p)) = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧
↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
rw [hg p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ ↑2 = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧ ↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ ↑2 = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧ ↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ ↑2 = ↑((2 * p).choose 1) / ↑(p.choose 1) ∧ ↑((2 * p).choose 1) / ↑(p.choose 1) = 2 ^ 1
simp only [Nat.choose_one_right] p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ ↑2 = ↑(2 * p) / ↑p ∧ ↑(2 * p) / ↑p = 2 ^ 1
push_cast p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ 2 = 2 * ↑p / ↑p ∧ 2 * ↑p / ↑p = 2 ^ 1
refine ⟨?_, ?_⟩ refine_1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ 2 = 2 * ↑p / ↑prefine_2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ 2 * ↑p / ↑p = 2 ^ 1
· refine_1 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ 2 = 2 * ↑p / ↑p field_simp All goals completed! 🐙
· refine_2 p:ℕhp:Nat.Prime php2:2 < pthis:Fact (Nat.Prime p)hp0:0 < phlucas:(2 * p).choose p ≡ 2 [MOD p]hpnd:¬p ∣ (2 * p).choose phev:2 ∣ (2 * p).choose phg:((2 * p).choose 1).gcd ((2 * p).choose p) = 2hpR:↑p ≠ 0⊢ 2 * ↑p / ↑p = 2 ^ 1 field_simp All goals completed! 🐙This was resolved by Bergman [Be11], who proved that for any $2\leq i<j\leq n/2$ $$\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \gg n^{1/2}\frac{2^i}{i^{3/2}},$$ where the implied constant is absolute.
@[category research solved, AMS 5 11, formal_proof using lean4 at "https://github.com/plby/lean-proofs/blob/main/src/v4.29.1/ErdosProblems/Erdos698.lean"]
theorem erdos_698.variants.bergman :
∃ c : ℝ, 0 < c ∧ ∀ n i j : ℕ, 2 ≤ i → i < j → j ≤ n / 2 →
c * (Real.sqrt (n : ℝ) * (2 : ℝ) ^ i / ((i : ℝ) * Real.sqrt (i : ℝ))) ≤
(Nat.gcd (n.choose i) (n.choose j) : ℝ) := by ⊢ ∃ c,
0 < c ∧ ∀ (n i j : ℕ), 2 ≤ i → i < j → j ≤ n / 2 → c * (√↑n * 2 ^ i / (↑i * √↑i)) ≤ ↑((n.choose i).gcd (n.choose j))
sorry All goals completed! 🐙end Erdos698