we-solve (beta)

Math-5628 · mathematics · Mathematics

Erdős Problem #402

Status Solved · erdosproblems.comLLM status Solved from source status

Statement

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.

Restatement from Math-5628-A1 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-5628-A1 · No claim recorded · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Math-5628

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%

Go to contribution →