Erdős Problem #539

Erdős Problem 539 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/539.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT. For a finite set $A\subseteq\mathbb N$, define \[ S(A):=\left\{\frac{a}{\gcd(a,b)}: a,b\in A\right\}. \] Define $h(n)$ to be the largest function such that for every $A\subseteq\mathbb N$ with $|A|=n$ we have $|S(A)|\ge h(n)$. Equivalently, \[ h(n)=\min_{A\subseteq\mathbb N,\ |A|=n} |S(A)|. \] Estimate the growth of $h(n)$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement reports that Erdős--Szemerédi proved $n^{1/2}\ll h(n)\ll n^{1-c}$ for some $c>0$. Below I give a self-contained proof of the elementary lower bound $h(n)\ge \lceil\sqrt n\rceil$ and the trivial upper bound $h(n)\le n$.

ATTACK PLAN. 1) Find an intrinsic reformulation of $S(A)$ in terms of reduced fractions. 2) Prove universal lower bounds by injecting a large set (e.g. the ratio set) into $S(A)\times S(A)$. 3) Give explicit constructions for upper bounds and compute small $n$ by brute force.

WORK. Fast reality check (small $n$ search). I searched all $n$-element subsets $A\subseteq\{1,2,\dots,20\}$ for $n\le 8$ and computed the minimum size of $S(A)$ among those. The best values found (as upper bounds on $h(n)$) were: \[ \begin{array}{c|cccccccc} n&1&2&3&4&5&6&7&8\\\hline \min_{A\subseteq[20],|A|=n} |S(A)| & 1&2&3&4&5&6&6&7 \end{array} \] One achieving set for $n=7$ is $A=\{2,3,4,6,9,12,18\}$, where $|S(A)|=6$.

Lemma 539.1 (ratio-set injection gives $|S(A)|\ge \sqrt{|A|}$). Let $A\subseteq\mathbb N$ be finite with $|A|=n$. Let \[ R(A):=\left\{\frac{a}{b}: a,b\in A\right\}\subseteq\mathbb Q. \] Then $|R(A)|\le |S(A)|^2$. In particular $|S(A)|\ge \lceil\sqrt n\rceil$, hence $h(n)\ge \lceil\sqrt n\rceil$.

Proof. Fix $a,b\in A$ and let $g=\gcd(a,b)$. Then \[ \frac{a}{b}=\frac{a/g}{b/g}. \] The numerator $a/g$ belongs to $S(A)$ by definition. The denominator $b/g$ also belongs to $S(A)$ because $ b/g = b/\gcd(b,a) $ and $a\in A$. Moreover, the fraction $(a/g)/(b/g)$ is in lowest terms because $\gcd(a/g,b/g)=1$. Thus every ratio $a/b\in R(A)$ has a unique reduced representation $x/y$ with $x,y\in S(A)$ and $\gcd(x,y)=1$. Therefore the map $R(A)\to S(A)\times S(A)$ sending $a/b$ to its reduced pair $(x,y)$ is injective, and $|R(A)|\le |S(A)|^2$.

Finally, fix any $b_0\in A$. The map $a\mapsto a/b_0$ is injective as a map $A\to\mathbb Q$, so $|R(A)|\ge n$. Combining, $n\le |R(A)|\le |S(A)|^2$, hence $|S(A)|\ge \sqrt n$ and the stated ceiling bound follows. $\square$

Lemma 539.2 (trivial upper bound $h(n)\le n$). For every $n\ge 1$, $h(n)\le n$.

Proof. Take $A=\{1,2,\dots,n\}$. For any $a,b\in A$, $\gcd(a,b)\ge 1$, so $ a/\gcd(a,b)\le a\le n. $ Thus $S(A)\subseteq\{1,2,\dots,n\}$. On the other hand, for each $a\in A$ we have $a/\gcd(a,1)=a$, so $\{1,2,\dots,n\}\subseteq S(A)$. Therefore $|S(A)|=n$, showing $h(n)\le n$. $\square$

VERIFICATION. Lemma 539.1 hinges on uniqueness of reduced fraction representation: if $a/b=x/y$ in lowest terms then $(x,y)$ is unique. Since both numerator and denominator come from the same construction $t/\gcd(t,\cdot)$, both lie in $S(A)$.

FINAL.\;UNRESOLVED.

• (i) Strongest proved partial result. For all $n$, \[\lceil\sqrt n\rceil\le h(n)\le n.\] Also, brute force in $[1,20]$ shows $h(7)\le 6$ and $h(8)\le 7$ (upper bounds).
• (ii) First gap (crisp statement). Improve either side toward the reported nontrivial upper bound $h(n)\ll n^{1-c}$ or sharpen the lower bound beyond $\sqrt n$, without invoking results outside the provided problem statement.
• (iii) Top 3 next moves.
  • Seek explicit structured families $A$ (e.g. multiplicative grids, divisor sets with constraints) for which $|S(A)|$ provably grows like $n^\theta$ for some $\theta<1$.
  • Strengthen Lemma 539.1 by lower bounding $|R(A)|$ by more than $n$ in terms of $n$ for every $A$ (a sum-product style statement), which would improve the $\sqrt n$ bound.
  • Computationally: perform heuristic search for $n=9,10,\dots$ with larger ambient range to guess the true minimal $|S(A)|$ and infer candidate constructions.
• (iv) Minimal counterexample structure to look for. A set $A$ with very small $|S(A)|$ must have a very small ratio set $R(A)$ as well (since $|R(A)|\le |S(A)|^2$). Thus any extremal construction should make many ratios $a/b$ coincide after reduction, meaning heavy multiplicative structure and repeated gcd patterns across many pairs.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT. For a finite set $A\subseteq\mathbb N$, define \[ S(A):=\left\{\frac{a}{\gcd(a,b)}: a,b\in A\right\}. \] Define $h(n)$ to be the largest function such that for every $A\subseteq\mathbb N$ with $|A|=n$ we have $|S(A)|\ge h(n)$. Equivalently, \[ h(n)=\min_{A\subseteq\mathbb N,\ |A|=n} |S(A)|. \] Estimate the growth of $h(n)$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement reports that Erdős--Szemerédi proved $n^{1/2}\ll h(n)\ll n^{1-c}$ for some $c>0$. Below I give a self-contained proof of the elementary lower bound $h(n)\ge \lceil\sqrt n\rceil$ and the trivial upper bound $h(n)\le n$.

ATTACK PLAN. 1) Find an intrinsic reformulation of $S(A)$ in terms of reduced fractions. 2) Prove universal lower bounds by injecting a large set (e.g. the ratio set) into $S(A)\times S(A)$. 3) Give explicit constructions for upper bounds and compute small $n$ by brute force.

WORK. Fast reality check (small $n$ search). I searched all $n$-element subsets $A\subseteq\{1,2,\dots,20\}$ for $n\le 8$ and computed the minimum size of $S(A)$ among those. The best values found (as upper bounds on $h(n)$) were: \[ \begin{array}{c|cccccccc} n&1&2&3&4&5&6&7&8\\\hline \min_{A\subseteq[20],|A|=n} |S(A)| & 1&2&3&4&5&6&6&7 \end{array} \] One achieving set for $n=7$ is $A=\{2,3,4,6,9,12,18\}$, where $|S(A)|=6$.

Lemma 539.1 (ratio-set injection gives $|S(A)|\ge \sqrt{|A|}$). Let $A\subseteq\mathbb N$ be finite with $|A|=n$. Let \[ R(A):=\left\{\frac{a}{b}: a,b\in A\right\}\subseteq\mathbb Q. \] Then $|R(A)|\le |S(A)|^2$. In particular $|S(A)|\ge \lceil\sqrt n\rceil$, hence $h(n)\ge \lceil\sqrt n\rceil$.

Proof. Fix $a,b\in A$ and let $g=\gcd(a,b)$. Then \[ \frac{a}{b}=\frac{a/g}{b/g}. \] The numerator $a/g$ belongs to $S(A)$ by definition. The denominator $b/g$ also belongs to $S(A)$ because $ b/g = b/\gcd(b,a) $ and $a\in A$. Moreover, the fraction $(a/g)/(b/g)$ is in lowest terms because $\gcd(a/g,b/g)=1$. Thus every ratio $a/b\in R(A)$ has a unique reduced representation $x/y$ with $x,y\in S(A)$ and $\gcd(x,y)=1$. Therefore the map $R(A)\to S(A)\times S(A)$ sending $a/b$ to its reduced pair $(x,y)$ is injective, and $|R(A)|\le |S(A)|^2$.

Finally, fix any $b_0\in A$. The map $a\mapsto a/b_0$ is injective as a map $A\to\mathbb Q$, so $|R(A)|\ge n$. Combining, $n\le |R(A)|\le |S(A)|^2$, hence $|S(A)|\ge \sqrt n$ and the stated ceiling bound follows. $\square$

Lemma 539.2 (trivial upper bound $h(n)\le n$). For every $n\ge 1$, $h(n)\le n$.

Proof. Take $A=\{1,2,\dots,n\}$. For any $a,b\in A$, $\gcd(a,b)\ge 1$, so $ a/\gcd(a,b)\le a\le n. $ Thus $S(A)\subseteq\{1,2,\dots,n\}$. On the other hand, for each $a\in A$ we have $a/\gcd(a,1)=a$, so $\{1,2,\dots,n\}\subseteq S(A)$. Therefore $|S(A)|=n$, showing $h(n)\le n$. $\square$

VERIFICATION. Lemma 539.1 hinges on uniqueness of reduced fraction representation: if $a/b=x/y$ in lowest terms then $(x,y)$ is unique. Since both numerator and denominator come from the same construction $t/\gcd(t,\cdot)$, both lie in $S(A)$.

FINAL.\;UNRESOLVED.

• (i) Strongest proved partial result. For all $n$, \[\lceil\sqrt n\rceil\le h(n)\le n.\] Also, brute force in $[1,20]$ shows $h(7)\le 6$ and $h(8)\le 7$ (upper bounds).
• (ii) First gap (crisp statement). Improve either side toward the reported nontrivial upper bound $h(n)\ll n^{1-c}$ or sharpen the lower bound beyond $\sqrt n$, without invoking results outside the provided problem statement.
• (iii) Top 3 next moves.
  • Seek explicit structured families $A$ (e.g. multiplicative grids, divisor sets with constraints) for which $|S(A)|$ provably grows like $n^\theta$ for some $\theta<1$.
  • Strengthen Lemma 539.1 by lower bounding $|R(A)|$ by more than $n$ in terms of $n$ for every $A$ (a sum-product style statement), which would improve the $\sqrt n$ bound.
  • Computationally: perform heuristic search for $n=9,10,\dots$ with larger ambient range to guess the true minimal $|S(A)|$ and infer candidate constructions.
• (iv) Minimal counterexample structure to look for. A set $A$ with very small $|S(A)|$ must have a very small ratio set $R(A)$ as well (since $|R(A)|\le |S(A)|^2$). Thus any extremal construction should make many ratios $a/b$ coincide after reduction, meaning heavy multiplicative structure and repeated gcd patterns across many pairs.