Erdős Problem #885

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

REUSED SOURCE 1

For integer $n\geq 1$ we define the factor difference set of $n$ by \[D(n) = \{\lvert a-b\rvert : n=ab\}.\] Is it true that, for every $k\geq 1$, there exist integers $N_1<\cdots<N_k$ such that \[\lvert \cap_i D(N_i)\rvert \geq k?\] A question of Erdős and Rosenfeld [ErRo97], who proved this is true for $k=2$. Jiménez-Urroz [Ji99] proved this for $k=3$ and Bremner [Br19] proved this for $k=4$.

1) FORMAL RESTATEMENT

For $n\in\mathbb N$, define \[D(n):=\{ |a-b| : a,b\in\mathbb N,\ ab=n\}. \] (So $0\in D(n)$ iff $n$ is a perfect square.)

Question: For every integer $k\ge 1$, do there exist integers $N_1<\cdots<N_k$ such that \[\big|D(N_1)\cap D(N_2)\cap\cdots\cap D(N_k)\big|\ge k\ ?\]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement itself reports proofs for $k=2,3,4$ (with references). Per the integrity rule, I do not add further literature. I focus on structural lemmas and explicit small-$k$ examples verified directly.

3) ATTACK PLAN

- Rewrite the condition “$d\in D(n)$” in several equivalent arithmetic forms, to expose Diophantine structure. - Provide explicit verified examples for $k=2$ and $k=3$ as a sanity check. - Attempt a small computational search for $k\ge 4$ in a bounded range (not a proof); record the outcome.

4) WORK

Lemma 885.1 (Divisor-pair description). For every $n\ge 1$, \[D(n)=\{\,\tfrac{n}{d}-d\ :\ d\mid n,\ d\le \sqrt n\,\}. \]

Proof. If $ab=n$ with $a\le b$, then $a\mid n$ and $b=n/a$, so $|a-b|=b-a=n/a-a$. Conversely, for any divisor $d\mid n$ with $d\le \sqrt n$, let $b=n/d\ge d$; then $db=n$ and $b-d\in D(n)$. This gives the stated equality of sets. $\square$

Lemma 885.2 (Quadratic form characterization). Let $n\ge 1$ and $d\ge 0$ be integers. Then \[d\in D(n)\ \Longleftrightarrow\ \exists a\in\mathbb N\text{ such that }n=a(a+d). \]

Proof. ($\Rightarrow$) If $d\in D(n)$, there exist $a,b\in\mathbb N$ with $ab=n$ and $|a-b|=d$. Without loss of generality $b\ge a$, so $b=a+d$ and $n=ab=a(a+d)$. ($\Leftarrow$) If $n=a(a+d)$ for some $a\in\mathbb N$, then $n$ has the factor pair $(a,a+d)$ and the difference of the factors is $d$, hence $d\in D(n)$. $\square$

Lemma 885.3 (Square-completion test). Let $n\ge 1$ and $d\ge 0$. Then $d\in D(n)$ if and only if there exists an integer $m$ such that \[m^2=4n+d^2\quad\text{and}\quad m\equiv d\pmod 2. \] In that case one can take $a=(m-d)/2$ in Lemma 885.2.

Proof. By Lemma 885.2, $d\in D(n)$ iff $n=a(a+d)$ for some $a\in\mathbb N$. Compute \[4n+d^2=4a(a+d)+d^2=(2a+d)^2. \] So if $d\in D(n)$, then $m:=2a+d$ satisfies $m^2=4n+d^2$ and clearly $m\equiv d\pmod 2$.

Conversely, if $m^2=4n+d^2$ and $m\equiv d\pmod2$, then $a:=(m-d)/2$ is an integer and \[a(a+d)=\frac{m-d}{2}\cdot\frac{m+d}{2}=\frac{m^2-d^2}{4}=n. \] Thus $d\in D(n)$. $\square$

FAST REALITY CHECK (explicit examples for $k=2$ and $k=3$). The following examples were found and verified by direct factor pairs.

Example for $k=2$: \[N_1=171360,\quad N_2=196560. \] Their common factor differences include $606$ and $1321$: - $196560=234\cdot 840$ and $171360=210\cdot 816$ give difference $606$. - $196560=135\cdot 1456$ and $171360=119\cdot 1440$ give difference $1321$. Hence $|D(N_1)\cap D(N_2)|\ge 2$.

Example for $k=3$: \[N_1=28560,\quad N_2=139440,\quad N_3=185640. \] Their common factor differences include $454,674,1663$: - Difference $454$: $185640=260\cdot 714$, $139440=210\cdot 664$, $28560=56\cdot 510$. - Difference $674$: $185640=210\cdot 884$, $139440=166\cdot 840$, $28560=40\cdot 714$. - Difference $1663$: $185640=105\cdot 1768$, $139440=80\cdot 1743$, $28560=17\cdot 1680$. Thus $|D(N_1)\cap D(N_2)\cap D(N_3)|\ge 3$.

Additional bounded search (not exhaustive). A backtracking search among “highly-divisible” numbers $\le 10^6$ did not find a $k=4$ instance within the tested candidate pool (this is not a contradiction to the stated $k=4$ theorem; the first known examples may occur above this range or outside the heuristic pool).

5) VERIFICATION

- Lemma 885.1: verified bijection between factor pairs $(a,b)$ with $a\le b$ and divisors $a\le \sqrt n$. - Lemma 885.3: checked parity condition is necessary so that $a=(m-d)/2$ is integral. - The explicit examples were verified by exhibiting factor pairs for each claimed difference, so membership in each $D(N_i)$ is line-by-line checked.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. - Exact equivalences for membership $d\in D(n)$ were proved (Lemmas 885.1--885.3). - Explicit verified instances exist for $k=2$ and $k=3$ (given above), matching the statements in the problem text.

(ii) First gap (crisp). Give a construction (or disproof) that for every $k$ produces distinct integers $N_1<\cdots<N_k$ and $k$ distinct integers $d_1,\dots,d_k$ such that \[\forall i\in\{1,\dots,k\}\ \forall j\in\{1,\dots,k\}\ \exists a_{i,j}\in\mathbb N\text{ with }N_i=a_{i,j}(a_{i,j}+d_j).\]

(iii) Top 3 next moves. 1. Use Lemma 885.3 to rephrase the problem as finding many $N_i$ for which $4N_i+d^2$ is a square for many common $d$; attempt to build parametric families. 2. Search computationally for a $k=5$ example to guess a pattern of differences and factor pairs, then try to prove the pattern. 3. Explore whether combining solutions of the two-difference equation $a(a+d)=b(b+e)$ (a quadratic Diophantine equation) can be iterated to force many common differences.

(iv) Minimal counterexample structure. If the conjecture fails, let $k_0$ be the smallest $k$ for which no such $N_1<\cdots<N_k$ exist. A minimal counterexample would manifest as: for every choice of $k_0$ integers, the intersection of their $D(\cdot)$ sets has size at most $k_0-1$. Such a failure would likely already appear for $k_0=5$, so computational searches for $k=5$ are structurally informative.

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.

For integer $n\geq 1$ we define the factor difference set of $n$ by \[D(n) = \{\lvert a-b\rvert : n=ab\}.\] Is it true that, for every $k\geq 1$, there exist integers $N_1<\cdots<N_k$ such that \[\lvert \cap_i D(N_i)\rvert \geq k?\] A question of Erdős and Rosenfeld [ErRo97], who proved this is true for $k=2$. Jiménez-Urroz [Ji99] proved this for $k=3$ and Bremner [Br19] proved this for $k=4$.

1) FORMAL RESTATEMENT

For $n\in\mathbb N$, define \[D(n):=\{ |a-b| : a,b\in\mathbb N,\ ab=n\}. \] (So $0\in D(n)$ iff $n$ is a perfect square.)

Question: For every integer $k\ge 1$, do there exist integers $N_1<\cdots<N_k$ such that \[\big|D(N_1)\cap D(N_2)\cap\cdots\cap D(N_k)\big|\ge k\ ?\]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement itself reports proofs for $k=2,3,4$ (with references). Per the integrity rule, I do not add further literature. I focus on structural lemmas and explicit small-$k$ examples verified directly.

3) ATTACK PLAN

- Rewrite the condition “$d\in D(n)$” in several equivalent arithmetic forms, to expose Diophantine structure. - Provide explicit verified examples for $k=2$ and $k=3$ as a sanity check. - Attempt a small computational search for $k\ge 4$ in a bounded range (not a proof); record the outcome.

4) WORK

Lemma 885.1 (Divisor-pair description). For every $n\ge 1$, \[D(n)=\{\,\tfrac{n}{d}-d\ :\ d\mid n,\ d\le \sqrt n\,\}. \]

Proof. If $ab=n$ with $a\le b$, then $a\mid n$ and $b=n/a$, so $|a-b|=b-a=n/a-a$. Conversely, for any divisor $d\mid n$ with $d\le \sqrt n$, let $b=n/d\ge d$; then $db=n$ and $b-d\in D(n)$. This gives the stated equality of sets. $\square$

Lemma 885.2 (Quadratic form characterization). Let $n\ge 1$ and $d\ge 0$ be integers. Then \[d\in D(n)\ \Longleftrightarrow\ \exists a\in\mathbb N\text{ such that }n=a(a+d). \]

Proof. ($\Rightarrow$) If $d\in D(n)$, there exist $a,b\in\mathbb N$ with $ab=n$ and $|a-b|=d$. Without loss of generality $b\ge a$, so $b=a+d$ and $n=ab=a(a+d)$. ($\Leftarrow$) If $n=a(a+d)$ for some $a\in\mathbb N$, then $n$ has the factor pair $(a,a+d)$ and the difference of the factors is $d$, hence $d\in D(n)$. $\square$

Lemma 885.3 (Square-completion test). Let $n\ge 1$ and $d\ge 0$. Then $d\in D(n)$ if and only if there exists an integer $m$ such that \[m^2=4n+d^2\quad\text{and}\quad m\equiv d\pmod 2. \] In that case one can take $a=(m-d)/2$ in Lemma 885.2.

Proof. By Lemma 885.2, $d\in D(n)$ iff $n=a(a+d)$ for some $a\in\mathbb N$. Compute \[4n+d^2=4a(a+d)+d^2=(2a+d)^2. \] So if $d\in D(n)$, then $m:=2a+d$ satisfies $m^2=4n+d^2$ and clearly $m\equiv d\pmod 2$.

Conversely, if $m^2=4n+d^2$ and $m\equiv d\pmod2$, then $a:=(m-d)/2$ is an integer and \[a(a+d)=\frac{m-d}{2}\cdot\frac{m+d}{2}=\frac{m^2-d^2}{4}=n. \] Thus $d\in D(n)$. $\square$

FAST REALITY CHECK (explicit examples for $k=2$ and $k=3$). The following examples were found and verified by direct factor pairs.

Example for $k=2$: \[N_1=171360,\quad N_2=196560. \] Their common factor differences include $606$ and $1321$: - $196560=234\cdot 840$ and $171360=210\cdot 816$ give difference $606$. - $196560=135\cdot 1456$ and $171360=119\cdot 1440$ give difference $1321$. Hence $|D(N_1)\cap D(N_2)|\ge 2$.

Example for $k=3$: \[N_1=28560,\quad N_2=139440,\quad N_3=185640. \] Their common factor differences include $454,674,1663$: - Difference $454$: $185640=260\cdot 714$, $139440=210\cdot 664$, $28560=56\cdot 510$. - Difference $674$: $185640=210\cdot 884$, $139440=166\cdot 840$, $28560=40\cdot 714$. - Difference $1663$: $185640=105\cdot 1768$, $139440=80\cdot 1743$, $28560=17\cdot 1680$. Thus $|D(N_1)\cap D(N_2)\cap D(N_3)|\ge 3$.

Additional bounded search (not exhaustive). A backtracking search among “highly-divisible” numbers $\le 10^6$ did not find a $k=4$ instance within the tested candidate pool (this is not a contradiction to the stated $k=4$ theorem; the first known examples may occur above this range or outside the heuristic pool).

5) VERIFICATION

- Lemma 885.1: verified bijection between factor pairs $(a,b)$ with $a\le b$ and divisors $a\le \sqrt n$. - Lemma 885.3: checked parity condition is necessary so that $a=(m-d)/2$ is integral. - The explicit examples were verified by exhibiting factor pairs for each claimed difference, so membership in each $D(N_i)$ is line-by-line checked.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. - Exact equivalences for membership $d\in D(n)$ were proved (Lemmas 885.1--885.3). - Explicit verified instances exist for $k=2$ and $k=3$ (given above), matching the statements in the problem text.

(ii) First gap (crisp). Give a construction (or disproof) that for every $k$ produces distinct integers $N_1<\cdots<N_k$ and $k$ distinct integers $d_1,\dots,d_k$ such that \[\forall i\in\{1,\dots,k\}\ \forall j\in\{1,\dots,k\}\ \exists a_{i,j}\in\mathbb N\text{ with }N_i=a_{i,j}(a_{i,j}+d_j).\]

(iii) Top 3 next moves. 1. Use Lemma 885.3 to rephrase the problem as finding many $N_i$ for which $4N_i+d^2$ is a square for many common $d$; attempt to build parametric families. 2. Search computationally for a $k=5$ example to guess a pattern of differences and factor pairs, then try to prove the pattern. 3. Explore whether combining solutions of the two-difference equation $a(a+d)=b(b+e)$ (a quadratic Diophantine equation) can be iterated to force many common differences.

(iv) Minimal counterexample structure. If the conjecture fails, let $k_0$ be the smallest $k$ for which no such $N_1<\cdots<N_k$ exist. A minimal counterexample would manifest as: for every choice of $k_0$ integers, the intersection of their $D(\cdot)$ sets has size at most $k_0-1$. Such a failure would likely already appear for $k_0=5$, so computational searches for $k=5$ are structurally informative.