Erdős problem 539 · problems.science

For $|A| = n$ , how small can the cofactor set $Q(A) = \{a / \gcd(a,b) : a, b \in A\}$ be? The answer is $h(n) = n^{1/2 + o(1)}$ : a new upper bound $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 statement5 of 8

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

FormalConjectures/ErdosProblems/539.leanErdos539.erdos_539.variants.sq1 lineExact file

1(fun n => ↑(Erdos539.cofactorThreshold n)) =Θ[Filter.atTop] fun n => √↑n

OpenStatement only, no proof

Sources

Search problems.science