Skip to content

Erdős problem 535

Start work

Let r≥3r \geq 3, and let fr(N)f_r(N) denote the size of the largest subset of {1,…,N}\{1,\ldots,N\} such that no subset of size rr has the same pairwise greatest common divisor between all elements. Erdős [Er64] proved that f3(N)>Nc/log⁡log⁡Nf_3(N) > N^{c/\log\log N} for some constant c>0c > 0, and conjectured this should also be an upper bound; here we state the conjectural upper bound for all r≥3r \geq 3.

Sources

The source's own material, retained exactly.

7 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

535.lean

Retained formal statement6 of 7

For the stronger Ω(n)=kΩ(n)=k variant above, the Erdős–Rado method gives the weaker bound crk⋅k!c_r^k \cdot k!; see Erdős [Er73].

FormalConjectures/ErdosProblems/535.leanErdos535.erdos_535.variants.sunflower_erdos_rado5 linesExact file
∀ {r : ℕ},  3 ≤ r →    ∃ c_r > 0,      ∀ (k : ℕ) (A : Finset ℕ),        Erdos535.AllBigOmega k A → Erdos535.NoConstantPairwiseGcdCoprimeSubsets r A → ↑A.card ≤ c_r ^ k * ↑k.factorial
SolvedStatement only, no proof