Erdős problem 402 · problems.science

Prove that, for any finite set $A\subset\mathbb{N}$ , there exist $a, b\in A$ such that $\gcd(a, b)\leq a/|A|.$

Sources

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

FormalConjectures/ErdosProblems/

402.lean

Retained formal statement2 of 3

A conjecture of Graham [Gr70], who also conjectured that (assuming $A$ itself has no common divisor) the only cases where equality is achieved are when $A = \{1, \dots, n\}$ or $A = \{L/1, \dots, L/n\}$ (where $L = \operatorname{lcm}(1, \dots, n)$ ) or $A = \{2, 3, 4, 6\}$ . Note: The source [BaSo96] mentioned on the Erdős page makes it clear what quantifiers to use for "where equality is achieved". See Theorem 1.1 there.

TODO(firsching): Consider if we should have the other direction here as well or an iff statement.

FormalConjectures/ErdosProblems/402.leanErdos402.erdos_402.variants.equality7 linesExact file

1∀ (A : Finset ℕ),2  0 ∉ A →3    A.Nonempty →4      A.gcd id = 1 →5        (∀ a ∈ A, ∀ b ∈ A, ↑a / ↑A.card ≤ ↑(a.gcd b)) →6          A = Finset.Icc 1 A.card ∨7            A = Finset.image (fun x => (Finset.Icc 1 A.card).lcm id / x) (Finset.Icc 1 A.card) ∨ A = {2, 3, 4, 6}

SolvedStatement only, no proof

Sources

Search problems.science