Skip to content

Erdős problem 539

Start work

For ∣A∣=n|A| = n, how small can the cofactor set Q(A)={a/gcd⁡(a,b):a,b∈A}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(log⁡n))h(n) \le n^{1/2} \exp(O(\sqrt{\log n})) matches the classical lower bound.

Sources

The source's own material, retained exactly.

9 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

539.lean

Retained formal statement5 of 8

Let h(n)h(n) be maximal such that, for any set A⊆NA\subseteq \mathbb{N} of size nn, the set{a(a,b):a,b∈A}\left\{ \frac{a}{(a,b)}: a,b\in A\right\}has size at least h(n)h(n). Is h(n)=Θ(n)h(n) = \Theta(\sqrt{n})?

FormalConjectures/ErdosProblems/539.leanErdos539.erdos_539.variants.sq1 lineExact file
(fun n => ↑(Erdos539.cofactorThreshold n)) =Θ[Filter.atTop] fun n => √↑n
OpenStatement only, no proof