Erdős Problem 402
Statement and status.
For every nonempty finite set $A$ of positive integers, must there be $a,b\in A$ with $a/\gcd(a,b)\geq |A|$? The answer is known to be yes, by Balasubramanian and Soundararajan. The general sharp inequality is unresolved in this attempt; the argument below gives a weaker universal bound, exact special cases, and a useful duality.
A universal elementary bound.
Put $n=|A|$, $m=\min A$, and \[
M=\max_{a,b\in A}\frac{a}{\gcd(a,b)}.
\] Reduce each fraction $a/m$ to $p/q$. Then \[
1\leq q\leq p\leq M,\qquad \gcd(p,q)=1.
\] The upper bound on $p$ follows from the pair $(a,m)$, and distinct members of $A$ give distinct fractions. With $\varphi(1)=1$, this gives \[
n\leq\sum_{p=1}^{M}\varphi(p)
\leq1+\frac{M(M-1)}2.
\] Therefore \[
M\geq
\left\lceil\frac{1+\sqrt{8n-7}}2\right\rceil .
\tag{1}
\] This is a genuine pairwise gcd conclusion, but its order $\sqrt n$ does not reach the required $n$.
Sharp special cases.
If $\min A$ divides every element of $A$, divide by it. The normalized set contains $1$ and has $n$ distinct positive elements, so its maximum is at least $n$. The pair consisting of this maximum and $1$ proves $M\geq n$. In particular, this covers every divisibility chain. For a pairwise coprime set with $n\geq2$, pair its largest element with any other member to obtain the same conclusion. The case $n=1$ has $M=1$.
Reciprocal duality.
Let $L=\operatorname{lcm}(A)$ and $A^*=\{L/a:a\in A\}$. For $a,b\in A$, \[
\gcd(L/a,L/b)=\frac{L}{\operatorname{lcm}(a,b)},\qquad
\frac{L/a}{\gcd(L/a,L/b)}=\frac{b}{\gcd(a,b)}.
\] Thus $|A^*|=|A|$ and $M(A^*)=M(A)$. Every proved special case therefore transfers to its reciprocal dual. The sets $\{1,\ldots,n\}$ have $M=n$, since no numerator can exceed $n$ and the pair $(n,1)$ attains it. Their reciprocal duals are also sharp.
Remaining gap and sources.
The missing step is to replace the quadratic counting estimate for reduced fractions by the sharp bound $|A|\leq M$ for arbitrary $A$. The known solution is R. Balasubramanian and K. Soundararajan,
On a conjecture of R. L. Graham, Acta Arithmetica 75 $1996$, 1--38,
https://eudml.org/doc/206861. Current statement:
https://www.erdosproblems.com/402, checked 24 September 2026. Its full theorem is not used as a substitute for the missing proof here.
Completion estimate.
The universal weaker bound and sharp families are proved; the general sharp step is missing.
COMPLETION: 30%