Estimate $h(n)$: fewest distinct ratios $a/\gcd(a,b)$ forced by an $n$-element set (Erdős #539)
Statement
For a finite set $A\subseteq\mathbb{N}$, write $(a,b)=\gcd(a,b)$ and consider the set of ratios $$\left\{\frac{a}{(a,b)}:a,b\in A\right\}.$$ Let $h(n)$ be the largest integer such that every $A$ with $\lvert A\rvert=n$ produces at least $h(n)$ distinct such ratios. Estimate the growth of $h(n)$ as $n\to\infty$.
Acceptance. FULLY RESOLVES: determine the exact order of $h(n)$ — a complete proof fixing the true growth up to constant factors (for example proving $h(n)\asymp n^{1/2}$, or identifying the precise correction factor), thereby closing the subpolynomial gap left by $n^{1/2}\leq h(n)\leq e^{O(\sqrt{\log n})}n^{1/2}$. ADVANCES: strictly improve one side of that gap with a full proof — an upper bound provably smaller than the current best $e^{O(\sqrt{\log n})}n^{1/2}$, or a lower bound provably larger than $n^{1/2}$ by a factor tending to infinity; or, via the Granville–Roesler reformulation, extend the certified fixed-dimension lower bounds to a new dimension $d$ or a new record constant, with reproducible computation. Deliver the proof and/or the improved bound with certification. State in words the bound you improve on.
Background
Posed by Erdős [Er73, p.125]; listed as open on erdosproblems.com/539 (fetched 2026-07-21, status 'open'). Erdős and Szemerédi proved $n^{1/2}\ll h(n)\ll n^{1-c}$ for some $c>0$; Freiman and Lev improved the upper bound to $h(n)\ll n^{2/3}$, with a proof of both bounds given by Granville and Roesler [GrRo99]. Granville and Roesler also recast the problem in combinatorial geometry: for $A\subseteq\mathbb{Z}^d$ of size $n$, minimise the size of $\{\delta(\mathbf a,\mathbf b):\mathbf a,\mathbf b\in A\}$, where $\delta(\mathbf a,\mathbf b)$ has $i$-th coordinate $\max(0,a_i-b_i)$; this viewpoint yielded improved lower bounds in each fixed small dimension $d$. Using that reformulation, a recent automated proof effort (ProofCouncil) established $h(n)\leq e^{O(\sqrt{\log n})}n^{1/2}$, which together with the lower bound gives $h(n)=n^{1/2+o(1)}$ — so the exponent is now pinned. What remains open is the exact order inside the subpolynomial factor: whether $h(n)\asymp n^{1/2}$, or grows with a genuine $e^{\Theta(\sqrt{\log n})}$ or logarithmic-power correction. The attacker's tool: the Granville–Roesler lattice reformulation, sharpened by additive-combinatorial arguments for the upper bound and by exhaustive small-dimension computer search for matching lower-bound configurations.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #539 (T. F. Bloom) | website |
| REF-02 | ProofCouncil proof note establishing $h(n)=n^{1/2+o(1)}$ | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.