Skip to content

Erdős problem 539

For A=n|A| = n, how small can the cofactor set Q(A)={a/gcd(a,b):a,bA}Q(A) = \{a / \gcd(a,b) : a, b \in A\} be? The answer is h(n)=n1/2+o(1)h(n) = n^{1/2 + o(1)}: a new upper bound h(n)n1/2exp(O(logn))h(n) \le n^{1/2} \exp(O(\sqrt{\log n})) matches the classical lower bound.

Sources

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

9 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

539.lean

Retained formal statement3 of 8

Granville and Roesler [GR99] showed that h(n)n2/3h(n)\ll n^{2/3}.

FormalConjectures/ErdosProblems/539.leanErdos539.erdos_539.variants.isBigO_sq_cube_root1 lineExact file
(fun n => ↑(Erdos539.cofactorThreshold n)) =O[Filter.atTop] fun n => ↑n ^ (2 / 3)
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page