Skip to content

Erdős problem 698

Is there some h(n)→∞h(n)\to \infty such that for all 2≤i<j≤n/22\leq i<j\leq n/2 gcd((ni),(nj))≥h(n)?\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq h(n)?

Sources

The source's own material, retained exactly.

4 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

698.lean

Retained formal statement3 of 4

A problem of Erdős and Szekeres, who observed that gcd((ni),(nj))≥(ni)(ji)≥2i\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>1).

FormalConjectures/ErdosProblems/698.leanErdos698.erdos_698.variants.erdos_szekeres5 linesExact file
∀ (n i j : ℕ),  1 ≤ i →    i < j →      j ≤ n / 2 →        ↑(n.choose i) / ↑(j.choose i) ≤ ↑((n.choose i).gcd (n.choose j)) ∧ 2 ^ i ≤ ↑(n.choose i) / ↑(j.choose i)
SolvedStatement only, no proof