/-
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 700
Reference: erdosproblems.com/700
A problem of Erdős and Szekeres [ErSz78].
References:
[ErSz78] Erdős, P. and Szekeres, G., Some number theoretic problems on binomial coefficients, Austral. Math. Soc. Gaz. (1978), 97-99.
Guy, R. K., Unsolved Problems in Number Theory, B31, B33.
@[expose] public sectionnamespace Erdos700open Finset
f n = min_{1 < k ≤ n/2} gcd(n, C(n,k)). (The infimum is 0 when the range is empty, i.e.
n < 4.)
noncomputable def f (n : ℕ) : ℕ :=
sInf {m | ∃ k, 1 < k ∧ k ≤ n / 2 ∧ m = Nat.gcd n (n.choose k)}
P n is the largest prime factor of n (and 0 if n ≤ 1).
noncomputable def P (n : ℕ) : ℕ := n.primeFactors.sup id
$Q(n)$ is the largest prime-power divisor of $n$: the maximum of $p^{v_p(n)}$ over
prime divisors $p$ of $n$. It is 0 when n ≤ 1.
noncomputable def Q (n : ℕ) : ℕ := n.primeFactors.sup (fun p => p ^ n.factorization p)
The set whose infimum defines f.
def fSet (n : ℕ) : Set ℕ := {m | ∃ k, 1 < k ∧ k ≤ n / 2 ∧ m = Nat.gcd n (n.choose k)}
f n unfolds to the infimum of fSet n.
@[category API, AMS 11]
lemma f_eq (n : ℕ) : f n = sInf (fSet n) := rfl
Each gcd(n, C(n,k)) with 1 < k ≤ n/2 belongs to fSet n.
@[category API, AMS 11]
lemma f_mem (n k : ℕ) (h1 : 1 < k) (h2 : k ≤ n / 2) :
Nat.gcd n (n.choose k) ∈ fSet n := ⟨k, h1, h2, rfl⟩
f n is a lower bound: f n ≤ gcd(n, C(n,k)) for every 1 < k ≤ n/2.
@[category API, AMS 11]
lemma f_le (n k : ℕ) (h1 : 1 < k) (h2 : k ≤ n / 2) :
f n ≤ Nat.gcd n (n.choose k) := Nat.sInf_le (f_mem n k h1 h2)def erdos_700.parts.i.answer : Set ℕ := sorryLet $f(n) = \min_{1 < k \le n/2} \gcd(n, \binom{n}{k})$ and let $P(n)$ be the largest prime dividing $n$.
(a) Characterise those composite $n$ such that $f(n) = n/P(n)$.
Erdős–Szekeres [ErSz78] note that $f(n) = n/P(n)$ when $n$ is a product of two primes
(erdos_700.variants.prime_mul), with $n = 30$ a further example. The characterisation itself is
open; we state it as the (unknown) set of all composite n with f n = n / P n.
This follows the largest-prime reading on erdosproblems.com. In [ErSz78, p. 98], the first prose
line below (7) reads: "where $P(n)$ is the greatest prime power which divides $n$."
The paper's reading is stated with $Q(n)$ in erdos_700.variants.prime_power_divisor.
@[category research open, question value, AMS 11]
theorem erdos_700.parts.i :
{n : ℕ | ¬ n.Prime ∧ 1 < n ∧ f n = n / P n} = erdos_700.parts.i.answer := ⊢ {n | ¬Nat.Prime n ∧ 1 < n ∧ f n = n / P n} = i.answer
All goals completed! 🐙def erdos_700.variants.prime_power_divisor.answer : Set ℕ := sorryCharacterise those composite $n$ such that $f(n) = n/Q(n)$, where $Q(n)$ is the largest prime-power divisor of $n$. This is the reading of part (a) in Erdős–Szekeres ErSz78, pp. 98–99.
@[category research open, question value, AMS 11]
theorem erdos_700.variants.prime_power_divisor :
{n : ℕ | ¬ n.Prime ∧ 1 < n ∧ f n = n / Q n} = erdos_700.variants.prime_power_divisor.answer
:= ⊢ {n | ¬Nat.Prime n ∧ 1 < n ∧ f n = n / Q n} = prime_power_divisor.answer
All goals completed! 🐙At $n = 12$, $f(n) = 3 = n/Q(n)$, whereas $n/P(n) = 4$.
refine_2 hne:(fSet 12).Nonemptyk:ℕhk1:1 < khk2:k ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 k)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 k)
interval_cases k refine_2.«2» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 2hk2:2 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 2)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 2)refine_2.«3» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 3hk2:3 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 3)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 3)refine_2.«4» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 4hk2:4 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 4)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 4)refine_2.«5» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 5hk2:5 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 5)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 5)refine_2.«6» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 6hk2:6 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 6)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 6) <;> refine_2.«2» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 2hk2:2 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 2)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 2)refine_2.«3» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 3hk2:3 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 3)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 3)refine_2.«4» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 4hk2:4 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 4)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 4)refine_2.«5» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 5hk2:5 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 5)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 5)refine_2.«6» hne:(fSet 12).Nonemptyk:ℕhk1:1 < 6hk2:6 ≤ 12 / 2hkeq:sInf (fSet 12) = Nat.gcd 12 (Nat.choose 12 6)⊢ 3 ≤ Nat.gcd 12 (Nat.choose 12 6) decide All goals completed! 🐙
· refine_3 ⊢ 12 / P 12 = 4 unfold P refine_3 ⊢ 12 / (Nat.primeFactors 12).sup id = 4
decide +kernel All goals completed! 🐙
· refine_4 ⊢ 12 / Q 12 = 3 unfold Q refine_4 ⊢ (12 / (Nat.primeFactors 12).sup fun p ↦ p ^ (Nat.factorization 12) p) = 3
decide +kernel All goals completed! 🐙Let $f(n) = \min_{1 < k \le n/2} \gcd(n, \binom{n}{k})$.
(b) Are there infinitely many composite $n$ such that $f(n) > n^{1/2}$?
Erdős–Szekeres [ErSz78] could not prove this. (Since $f(n) \ge p(n)$, the least prime factor of
$n$, there are infinitely many $n$ — those of the form $p^2$ — with $f(n) \ge n^{1/2}$; the
question asks for the strict inequality.) Here $f(n) > n^{1/2}$ is written as (f n) ^ 2 > n.
@[category research open, question, AMS 11]
theorem erdos_700.parts.ii :
{n : ℕ | ¬ n.Prime ∧ 1 < n ∧ (f n) ^ 2 > n}.Infinite := by ⊢ {n | ¬Nat.Prime n ∧ 1 < n ∧ f n ^ 2 > n}.Infinite
sorry All goals completed! 🐙Let $f(n) = \min_{1 < k \le n/2} \gcd(n, \binom{n}{k})$.
(c) Is it true that, for every composite $n$, $f(n) \ll_A n/(\log n)^A$ for every $A > 0$?
Erdős–Szekeres [ErSz78] prove the weaker bound $f(n) \le (1 + o(1)) n/\log n$ (the case $A = 1$).
Here $f(n) \ll_A n/(\log n)^A$ is spelled out as: for every A > 0 there is a constant C
(depending on A) with f(n) ≤ C · n/(log n)^A for every composite n.
@[category research open, question, AMS 11]
theorem erdos_700.parts.iii :
(∀ A : ℝ, 0 < A → ∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, ¬ n.Prime → 1 < n →
(f n : ℝ) ≤ C * (n : ℝ) / (Real.log n) ^ A) := by ⊢ ∀ (A : ℝ), 0 < A → ∃ C, 0 < C ∧ ∀ (n : ℕ), ¬Nat.Prime n → 1 < n → ↑(f n) ≤ C * ↑n / Real.log ↑n ^ A
sorry All goals completed! 🐙
Lucas (one step): for prime P ∣ n, if P ∤ C(n,k) then P ∣ k.
@[category API, AMS 11]
lemma prime_dvd_of_not_dvd_choose (P n k : ℕ) (hP : P.Prime) (hPn : P ∣ n)
(h : ¬ P ∣ n.choose k) : P ∣ k := by P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose k⊢ P ∣ k
have := Fact.mk hP P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)⊢ P ∣ k
by_contra hk P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ k⊢ False
apply h P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ k⊢ P ∣ n.choose k
have hmod : n.choose k ≡ (n % P).choose (k % P) * (n / P).choose (k / P) [MOD P] :=
Choose.choose_modEq_choose_mod_mul_choose_div_nat P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ (n % P).choose (k % P) * (n / P).choose (k / P) [MOD P]⊢ P ∣ n.choose k
have hn0 : n % P = 0 := by P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose k⊢ P ∣ k P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ (n % P).choose (k % P) * (n / P).choose (k / P) [MOD P]hn0:n % P = 0⊢ P ∣ n.choose k
have h := (Nat.modEq_zero_iff_dvd).2 hPn P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh✝:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ (n % P).choose (k % P) * (n / P).choose (k / P) [MOD P]h:n ≡ 0 [MOD P]⊢ n % P = 0 P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ (n % P).choose (k % P) * (n / P).choose (k / P) [MOD P]hn0:n % P = 0⊢ P ∣ n.choose k; simpa [Nat.ModEq, Nat.zero_mod] using h P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ (n % P).choose (k % P) * (n / P).choose (k / P) [MOD P]hn0:n % P = 0⊢ P ∣ n.choose k P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ (n % P).choose (k % P) * (n / P).choose (k / P) [MOD P]hn0:n % P = 0⊢ P ∣ n.choose k
have hkP : 0 < k % P := Nat.pos_of_ne_zero (fun hh => hk (Nat.dvd_of_mod_eq_zero hh)) P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ (n % P).choose (k % P) * (n / P).choose (k / P) [MOD P]hn0:n % P = 0hkP:0 < k % P⊢ P ∣ n.choose k
rw [hn0, P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ Nat.choose 0 (k % P) * (n / P).choose (k / P) [MOD P]hn0:n % P = 0hkP:0 < k % P⊢ P ∣ n.choose k P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ 0 [MOD P]hn0:n % P = 0hkP:0 < k % P⊢ P ∣ n.choose k Nat.choose_eq_zero_of_lt hkP, P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ 0 * (n / P).choose (k / P) [MOD P]hn0:n % P = 0hkP:0 < k % P⊢ P ∣ n.choose k P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ 0 [MOD P]hn0:n % P = 0hkP:0 < k % P⊢ P ∣ n.choose k zero_mul P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ 0 [MOD P]hn0:n % P = 0hkP:0 < k % P⊢ P ∣ n.choose k P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ 0 [MOD P]hn0:n % P = 0hkP:0 < k % P⊢ P ∣ n.choose k] at hmod P:ℕn:ℕk:ℕhP:Nat.Prime PhPn:P ∣ nh:¬P ∣ n.choose kthis:Fact (Nat.Prime P)hk:¬P ∣ khmod:n.choose k ≡ 0 [MOD P]hn0:n % P = 0hkP:0 < k % P⊢ P ∣ n.choose k
exact (Nat.modEq_zero_iff_dvd).1 hmod All goals completed! 🐙
f(p^a) = p for a prime p and a ≥ 2 (recorded by Erdős–Szekeres [ErSz78]). In particular,
since (p^a) / P(p^a) = p^{a-1}, the prime power p^a is a "hit" (f(n) = n / P(n)) if and only
if a = 2.