Erdős Problem #887

Erdős Problem 887 --- 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/887.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

For an integer $n\ge 1$ and real $C>0$, define \[ D_C(n) \;:=\; \#\Big\{d\in\mathbb{N}: d\mid n\ \text{and}\ \sqrt n< d < \sqrt n + C\,n^{1/4}\Big\}. \] The question is whether there exists an absolute constant $K\in\mathbb{N}$ such that:

for every real $C>0$ there exists $N(C)\in\mathbb{N}$ with \[ \forall n\ge N(C)\qquad D_C(n)\le K. \]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement cites Erdős--Rosenfeld $1997$ as showing that there are infinitely many $n$ with four divisors in $(\sqrt n,\sqrt n+n^{1/4})$, and asks whether $4$ is best possible. I do not use any external results beyond what is explicitly stated in the problem text.

3) ATTACK PLAN

Proof direction (bounded $D_C(n)$).

• Reparameterize divisors $d$ in the short interval by complementary divisors $e=n/d$ and then by $(m,t)$ with $n=m^2-t^2$ and $t$ of size $\ll n^{1/4}$. Try to bound the number of such representations uniformly.
• Translate the problem to counting integer lattice points on $xy=n$ inside a thin box around $(\sqrt n,\sqrt n)$. Try to show that too many lattice points force algebraic structure that cannot persist as $n\to\infty$.

Disproof direction (unbounded $D_C(n)$).

• Attempt to construct $n$ with many factorizations $n=ab$ where $a,b$ are both within $O(n^{1/4})$ of $\sqrt n$ (equivalently many "almost-square" factorizations). This would amount to producing many solutions of $m^2-t^2=n$ with small $t$.

4) WORK

Lemma 887.1 (location of the complementary divisor). Let $n\ge 1$ and $C>0$. If $d\mid n$ and \[\sqrt n< d < \sqrt n + C\,n^{1/4},\] then the complementary divisor $e:=n/d$ satisfies \[\sqrt n - C\,n^{1/4} < e < \sqrt n.\] More precisely, writing $d=\sqrt n + x$ with $0<x<Cn^{1/4}$, \[ e = \sqrt n - x + \frac{x^2}{\sqrt n + x} \] and hence \[\sqrt n - x < e < \sqrt n - x + C^2.\]

Proof. Since $d>\sqrt n$, we have $e=n/d<\sqrt n$. For the lower bound, set $u:=C n^{-1/4}>0$. Then \[ e \;=\; \frac{n}{d}\;>\; \frac{n}{\sqrt n + Cn^{1/4}} \;=\; \frac{\sqrt n}{1+u}. \] For any $u>0$, one has $\frac{1}{1+u} > 1-u$ because $(1-u)(1+u)=1-u^2<1$. Therefore \[ e > \sqrt n(1-u)=\sqrt n - Cn^{1/4}. \] For the identity, write $d=\sqrt n + x$ and compute \[ \frac{n}{\sqrt n + x} = \frac{(\sqrt n - x)(\sqrt n + x) + x^2}{\sqrt n + x} = \sqrt n - x + \frac{x^2}{\sqrt n + x}. \] Since $0<x<Cn^{1/4}$, we have $0<\frac{x^2}{\sqrt n + x} < \frac{x^2}{\sqrt n} < C^2$, giving the stated bounds.$\square$

Lemma 887.2 (difference-of-squares encoding with a small parameter). Let $n\ge 1$ and let $d>\sqrt n$ be a divisor of $n$. Put $e=n/d$ and define \[ m:=\frac{d+e}{2},\qquad t:=\frac{d-e}{2}. \] Then $m,t\in \tfrac12\mathbb{Z}$, $m>t\ge 0$, and \[ n = m^2 - t^2. \] Moreover, if $d < \sqrt n + Cn^{1/4}$ then $t < C n^{1/4}$.

Proof. The identities $d=m+t$ and $e=m-t$ are immediate from the definitions, so \[ m^2-t^2 = (m+t)(m-t)=de=n. \] Since $d,e\in\mathbb{Z}$, the numbers $m,t$ are either both integers or both half-integers, i.e., in $\tfrac12\mathbb{Z}$. Also $d>e>0$ implies $t>0$ and $m>t$. For the upper bound on $t$, write $d=\sqrt n + x$ with $0<x<Cn^{1/4}$, and use the exact formula from Lemma 887.1: \[ d-e = (\sqrt n + x) - \Big(\sqrt n - x + \frac{x^2}{\sqrt n + x}\Big) = 2x - \frac{x^2}{\sqrt n + x}. \] Since $\frac{x^2}{\sqrt n + x}>0$, this gives $d-e<2x$, hence \[ t=\frac{d-e}{2} < x < Cn^{1/4}. \] $\square$

Fast reality check (computation). For $C=1$ I brute-scanned all integers $1\le n\le 2{,}000{,}000$ and counted divisors $d$ with $\sqrt n<d<\sqrt n+n^{1/4}$ by explicitly testing all integers $d$ in the candidate range $(\lfloor\sqrt n\rfloor,\,\lfloor \sqrt n+n^{1/4}\rfloor]$. Result: \[ \max_{1\le n\le 2\cdot 10^6} D_1(n) = 1. \] So in this range no example has even two divisors in the interval (this does not contradict the statement in the problem text that there are infinitely many $n$ with four such divisors; it only means the first examples are beyond $2\cdot 10^6$).

5) VERIFICATION

Lemma 887.1: the only nontrivial inequality used is $\frac1{1+u}>1-u$ for $u>0$, verified by multiplying out. The formula for $e$ is an exact rational identity.

Lemma 887.2: the factorization $m^2-t^2=(m+t)(m-t)$ is exact. The bound $t<Cn^{1/4}$ uses the exact expression for $d-e$ and the strict inequality $x^2/(\sqrt n+x)>0$.

Computation: the divisor count method is correct because every divisor $d>\sqrt n$ with $d<\sqrt n+n^{1/4}$ lies in the scanned integer interval and is detected by the modulus test $n\bmod d=0$.

6) FINAL

UNRESOLVED

1. (i) Strongest proved partial result here. Any divisor $d$ in $(\sqrt n,\sqrt n+Cn^{1/4})$ forces its complementary divisor $e=n/d$ to lie in $(\sqrt n-Cn^{1/4},\sqrt n)$ (Lemma 887.1). Equivalently, such divisors correspond to factorizations $n=de$ with both factors within $O(n^{1/4})$ of $\sqrt n$, and to representations $n=m^2-t^2$ with $t<Cn^{1/4}$ (Lemma 887.2).
2. (ii) First gap (crisp). Prove (or disprove) that the number of factor pairs $(e,d)$ with $ed=n$ and $|d-\sqrt n|<Cn^{1/4}$ is bounded by an absolute constant independent of $n$ (for each fixed $C$, eventually in $n$).
3. (iii) Top 3 next moves.
   • Try to show that having $\ge 5$ such divisors forces two distinct representations $n=m^2-t^2=m'^2-t'^2$ with $t,t'\ll n^{1/4}$ that imply a nontrivial diophantine relation (e.g. a small nonzero value of $(m-m')(m+m')=(t-t')(t+t')$) and then bound the number of solutions.
   • Computationally search for the smallest $n$ with $D_1(n)\ge 2,3,4$ and inspect the factorization pattern; attempt to reverse-engineer a parametric construction that could produce $D_1(n)\ge 5$.
   • Attempt a "repulsion" lemma: if $d_1<d_2<\cdots<d_r$ are divisors in the interval, relate consecutive gaps $d_{j+1}-d_j$ to constraints on $n$ (e.g. via comparing $n/d_j$) to show $r$ must be bounded.
4. (iv) Minimal counterexample structure. A counterexample to the existence of a universal $K$ would be an infinite sequence $n_t\to\infty$ (for some fixed $C$) with many distinct divisors $d_{t,1}<\cdots<d_{t,r_t}$ in $(\sqrt{n_t},\sqrt{n_t}+Cn_t^{1/4})$ and $r_t\to\infty$. Equivalently, many factor pairs $n_t=e_{t,j}d_{t,j}$ with both $e_{t,j},d_{t,j}$ clustered within $O(n_t^{1/4})$ of $\sqrt{n_t}$.

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.

1) FORMAL RESTATEMENT

For an integer $n\ge 1$ and real $C>0$, define \[ D_C(n) \;:=\; \#\Big\{d\in\mathbb{N}: d\mid n\ \text{and}\ \sqrt n< d < \sqrt n + C\,n^{1/4}\Big\}. \] The question is whether there exists an absolute constant $K\in\mathbb{N}$ such that:

for every real $C>0$ there exists $N(C)\in\mathbb{N}$ with \[ \forall n\ge N(C)\qquad D_C(n)\le K. \]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement cites Erdős--Rosenfeld $1997$ as showing that there are infinitely many $n$ with four divisors in $(\sqrt n,\sqrt n+n^{1/4})$, and asks whether $4$ is best possible. I do not use any external results beyond what is explicitly stated in the problem text.

3) ATTACK PLAN

Proof direction (bounded $D_C(n)$).

• Reparameterize divisors $d$ in the short interval by complementary divisors $e=n/d$ and then by $(m,t)$ with $n=m^2-t^2$ and $t$ of size $\ll n^{1/4}$. Try to bound the number of such representations uniformly.
• Translate the problem to counting integer lattice points on $xy=n$ inside a thin box around $(\sqrt n,\sqrt n)$. Try to show that too many lattice points force algebraic structure that cannot persist as $n\to\infty$.

Disproof direction (unbounded $D_C(n)$).

• Attempt to construct $n$ with many factorizations $n=ab$ where $a,b$ are both within $O(n^{1/4})$ of $\sqrt n$ (equivalently many "almost-square" factorizations). This would amount to producing many solutions of $m^2-t^2=n$ with small $t$.

4) WORK

Lemma 887.1 (location of the complementary divisor). Let $n\ge 1$ and $C>0$. If $d\mid n$ and \[\sqrt n< d < \sqrt n + C\,n^{1/4},\] then the complementary divisor $e:=n/d$ satisfies \[\sqrt n - C\,n^{1/4} < e < \sqrt n.\] More precisely, writing $d=\sqrt n + x$ with $0<x<Cn^{1/4}$, \[ e = \sqrt n - x + \frac{x^2}{\sqrt n + x} \] and hence \[\sqrt n - x < e < \sqrt n - x + C^2.\]

Proof. Since $d>\sqrt n$, we have $e=n/d<\sqrt n$. For the lower bound, set $u:=C n^{-1/4}>0$. Then \[ e \;=\; \frac{n}{d}\;>\; \frac{n}{\sqrt n + Cn^{1/4}} \;=\; \frac{\sqrt n}{1+u}. \] For any $u>0$, one has $\frac{1}{1+u} > 1-u$ because $(1-u)(1+u)=1-u^2<1$. Therefore \[ e > \sqrt n(1-u)=\sqrt n - Cn^{1/4}. \] For the identity, write $d=\sqrt n + x$ and compute \[ \frac{n}{\sqrt n + x} = \frac{(\sqrt n - x)(\sqrt n + x) + x^2}{\sqrt n + x} = \sqrt n - x + \frac{x^2}{\sqrt n + x}. \] Since $0<x<Cn^{1/4}$, we have $0<\frac{x^2}{\sqrt n + x} < \frac{x^2}{\sqrt n} < C^2$, giving the stated bounds.$\square$

Lemma 887.2 (difference-of-squares encoding with a small parameter). Let $n\ge 1$ and let $d>\sqrt n$ be a divisor of $n$. Put $e=n/d$ and define \[ m:=\frac{d+e}{2},\qquad t:=\frac{d-e}{2}. \] Then $m,t\in \tfrac12\mathbb{Z}$, $m>t\ge 0$, and \[ n = m^2 - t^2. \] Moreover, if $d < \sqrt n + Cn^{1/4}$ then $t < C n^{1/4}$.

Proof. The identities $d=m+t$ and $e=m-t$ are immediate from the definitions, so \[ m^2-t^2 = (m+t)(m-t)=de=n. \] Since $d,e\in\mathbb{Z}$, the numbers $m,t$ are either both integers or both half-integers, i.e., in $\tfrac12\mathbb{Z}$. Also $d>e>0$ implies $t>0$ and $m>t$. For the upper bound on $t$, write $d=\sqrt n + x$ with $0<x<Cn^{1/4}$, and use the exact formula from Lemma 887.1: \[ d-e = (\sqrt n + x) - \Big(\sqrt n - x + \frac{x^2}{\sqrt n + x}\Big) = 2x - \frac{x^2}{\sqrt n + x}. \] Since $\frac{x^2}{\sqrt n + x}>0$, this gives $d-e<2x$, hence \[ t=\frac{d-e}{2} < x < Cn^{1/4}. \] $\square$

Fast reality check (computation). For $C=1$ I brute-scanned all integers $1\le n\le 2{,}000{,}000$ and counted divisors $d$ with $\sqrt n<d<\sqrt n+n^{1/4}$ by explicitly testing all integers $d$ in the candidate range $(\lfloor\sqrt n\rfloor,\,\lfloor \sqrt n+n^{1/4}\rfloor]$. Result: \[ \max_{1\le n\le 2\cdot 10^6} D_1(n) = 1. \] So in this range no example has even two divisors in the interval (this does not contradict the statement in the problem text that there are infinitely many $n$ with four such divisors; it only means the first examples are beyond $2\cdot 10^6$).

5) VERIFICATION

Lemma 887.1: the only nontrivial inequality used is $\frac1{1+u}>1-u$ for $u>0$, verified by multiplying out. The formula for $e$ is an exact rational identity.

Lemma 887.2: the factorization $m^2-t^2=(m+t)(m-t)$ is exact. The bound $t<Cn^{1/4}$ uses the exact expression for $d-e$ and the strict inequality $x^2/(\sqrt n+x)>0$.

Computation: the divisor count method is correct because every divisor $d>\sqrt n$ with $d<\sqrt n+n^{1/4}$ lies in the scanned integer interval and is detected by the modulus test $n\bmod d=0$.

6) FINAL

UNRESOLVED

1. (i) Strongest proved partial result here. Any divisor $d$ in $(\sqrt n,\sqrt n+Cn^{1/4})$ forces its complementary divisor $e=n/d$ to lie in $(\sqrt n-Cn^{1/4},\sqrt n)$ (Lemma 887.1). Equivalently, such divisors correspond to factorizations $n=de$ with both factors within $O(n^{1/4})$ of $\sqrt n$, and to representations $n=m^2-t^2$ with $t<Cn^{1/4}$ (Lemma 887.2).
2. (ii) First gap (crisp). Prove (or disprove) that the number of factor pairs $(e,d)$ with $ed=n$ and $|d-\sqrt n|<Cn^{1/4}$ is bounded by an absolute constant independent of $n$ (for each fixed $C$, eventually in $n$).
3. (iii) Top 3 next moves.
   • Try to show that having $\ge 5$ such divisors forces two distinct representations $n=m^2-t^2=m'^2-t'^2$ with $t,t'\ll n^{1/4}$ that imply a nontrivial diophantine relation (e.g. a small nonzero value of $(m-m')(m+m')=(t-t')(t+t')$) and then bound the number of solutions.
   • Computationally search for the smallest $n$ with $D_1(n)\ge 2,3,4$ and inspect the factorization pattern; attempt to reverse-engineer a parametric construction that could produce $D_1(n)\ge 5$.
   • Attempt a "repulsion" lemma: if $d_1<d_2<\cdots<d_r$ are divisors in the interval, relate consecutive gaps $d_{j+1}-d_j$ to constraints on $n$ (e.g. via comparing $n/d_j$) to show $r$ must be bounded.
4. (iv) Minimal counterexample structure. A counterexample to the existence of a universal $K$ would be an infinite sequence $n_t\to\infty$ (for some fixed $C$) with many distinct divisors $d_{t,1}<\cdots<d_{t,r_t}$ in $(\sqrt{n_t},\sqrt{n_t}+Cn_t^{1/4})$ and $r_t\to\infty$. Equivalently, many factor pairs $n_t=e_{t,j}d_{t,j}$ with both $e_{t,j},d_{t,j}$ clustered within $O(n_t^{1/4})$ of $\sqrt{n_t}$.