Skip to content

Erdős problem 535

Let r3r \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/loglogNf_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 r3r \geq 3.

Sources

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

7 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

535.lean

Retained formal statement7 of 7

Erdős [Er73] records that Abbott pointed out the ordinary sunflower conjecture does not seem to suffice here. The stronger auxiliary conjecture uses Ω(n)=kΩ(n)=k, i.e. prime factors counted with multiplicity; this stronger statement would imply the conjectured upper bound for fr(N)f_r(N).

FormalConjectures/ErdosProblems/535.leanErdos535.erdos_535.variants.sunflower_strong5 linesExact file
∀ {r : ℕ},  3 ≤ rc_r > 0,      ∀ (k : ℕ) (A : Finset ℕ),        Erdos535.AllBigOmega k AErdos535.NoConstantPairwiseGcdCoprimeSubsets r A → ↑A.cardc_r ^ k
OpenStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page