Erdős Problem #709

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

REUSED SOURCE 1

1) FORMAL RESTATEMENT

For each $n\ge 1$, define $f(n)$ to be the minimal real number with the following property:

For every set $A=\{a_1,\dots,a_n\}\subset\mathbb{N}\cap[2,\infty)$ with $|A|=n$ and $m=\max(A)$, and for every interval $I$ consisting of $\lfloor f(n)m\rfloor$ consecutive integers, there exist distinct integers $x_1,\dots,x_n\in I$ such that $a_i\mid x_i$ for all $i$.

(There is a mild ambiguity in the problem statement about whether the interval length is exactly $f(n)m$ or an integer rounding; for the purposes of rigorous inequalities below I will prove statements for integer multiples, which implies corresponding bounds for any reasonable rounding convention.)

2) QUICK LITERATURE/CONTEXT CHECK

Using only what is stated in the problem text: Erdős--Surányi proved \[(\log n)^c \ll f(n) \ll n^{1/2}\] for some constant $c>0$.

3) ATTACK PLAN

- Prove easy universal lower/upper bounds by extremal examples and matching arguments. - For upper bounds, model the problem as a bipartite matching between divisors $a_i$ and integers in the interval.

4) WORK

Lemma 709.1 (Trivial lower bound $f(n)\ge 1$). For every $n\ge 1$, $f(n)\ge 1$.

Proof. Fix $n\ge 1$. Consider any $A$ with $m=\max(A)$. If an interval $I$ contains fewer than $m$ consecutive integers, then it is possible to choose $I$ to avoid all multiples of $m$ (e.g. $I=\{1,2,\dots,m-1\}$). In such an interval there is no integer divisible by $m$, so we cannot assign a distinct $x_i$ to the element of $A$ equal to $m$. Hence, to guarantee a solution for all intervals, we need interval length at least $m$, i.e. $f(n)\ge 1$. $\square$

Lemma 709.2 (General upper bound $f(n)\le n$). For every $n\ge 1$ and every finite $A\subset\mathbb{N}\cap[2,\infty)$ with $|A|=n$ and $m=\max(A)$, every interval $I$ of $nm$ consecutive integers contains distinct $x_1,\dots,x_n\in I$ with $a_i\mid x_i$ for all $i$. In particular, $f(n)\le n$.

Proof. Let $A=\{a_1,\dots,a_n\}$ and let $I$ be any interval of $nm$ consecutive integers. Construct a bipartite graph $H$ with left vertex set $A$ and right vertex set $I$, where we connect $a\in A$ to $x\in I$ iff $a\mid x$. We seek a matching that covers all left vertices.

By Hall's marriage theorem, it suffices to show that for every subset $S\subseteq A$, its neighborhood \[ N(S)=\{x\in I:\exists a\in S\text{ with }a\mid x\} \] has size at least $|S|$.

Fix a nonempty $S\subseteq A$ and let $d=\min S$. Every multiple of $d$ that lies in $I$ belongs to $N(S)$ (because it is divisible by $d\in S$), so $|N(S)|$ is at least the number of multiples of $d$ in $I$. Write $|I|=nm$. In any block of $nm$ consecutive integers, the number of multiples of $d$ is at least $\lfloor nm/d\rfloor$. Since $d\le m$, we have $nm/d\ge n$, hence $\lfloor nm/d\rfloor\ge n$. Therefore $|N(S)|\ge n$. Finally, because $|S|\le n$, we have $|N(S)|\ge n\ge |S|$, establishing Hall's condition. Thus $H$ contains a matching of size $n$, i.e. distinct $x_1,\dots,x_n\in I$ with $a_i\mid x_i$. $\square$

Lemma 709.3 (Exact value for $n=2$: $f(2)=2$ in the integer-multiple model). If we restrict attention to intervals of integer length $t\,\max(A)$ with $t\in\mathbb{N}$, then $t=1$ does not suffice for $n=2$, while $t=2$ always suffices. Hence in this integer-multiple model, $f(2)=2$.

Proof. Lower bound: $t=1$ fails. Take $A=\{2,3\}$, so $m=3$. Consider the interval $I=\{5,6,7\}$ of length $m$. The only multiple of $3$ in $I$ is $6$, and the only multiple of $2$ in $I$ is also $6$. So there do not exist distinct $x_1,x_2\in I$ with $2\mid x_1$ and $3\mid x_2$. Thus $t=1$ fails.

Upper bound: $t=2$ suffices. Lemma 709.2 with $n=2$ shows that any interval of $2m$ consecutive integers admits such a matching. Therefore $t=2$ suffices for all $A$ with $|A|=2$. $\square$

FAST REALITY CHECK (limited brute force for $n=2$). I brute-forced all $A$ with $|A|=2$, $\max(A)\le 20$, and all interval starts $t\le 500$. Result: $t=1$ fails (e.g. $A=\{2,3\}$ with interval $\{5,6,7\}$), while $t=2$ worked for all tested instances.

5) VERIFICATION

- Lemma 709.2: The key inequality is that any interval of length $nm$ contains at least $\lfloor nm/d\rfloor\ge n$ multiples of $d\le m$. This is correct because multiples of $d$ occur every $d$ integers, so among $nm$ consecutive integers there are at least $\lfloor nm/d\rfloor$ multiples. - Hall is applied correctly: $|N(S)|\ge n\ge |S|$ for all $S$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. I proved the unconditional bounds $1\le f(n)\le n$ (Lemmas 709.1 and 709.2) and, in the integer-multiple model, $f(2)=2$ (Lemma 709.3). I also ran a finite brute-force sanity check for $n=2$ (reported above).

(ii) First gap (crisp). Close the gap between $f(n)\le n$ and the much smaller upper bound $f(n)\ll n^{1/2}$ stated in the problem text, or determine the true asymptotic behavior of $f(n)$.

(iii) Top 3 next moves. 1. Strengthen the Hall lower bound $|N(S)|\ge n$ by using the full divisor structure of $S$ rather than just $\min S$, aiming for shorter intervals. 2. Search for extremal $A$ that make matching difficult (many $a_i$ sharing large common multiples) and try to prove lower bounds from explicit constructions. 3. Implement a computational optimizer for small $n$ to guess the exact $f(n)$ and the structure of extremal sets $A$.

(iv) Minimal counterexample structure. A minimal obstruction to a candidate bound $f(n)\le c$ would be a set $A$ with $m=\max(A)$ and an interval $I$ of $\approx cm$ consecutive integers such that the divisibility bipartite graph fails Hall's condition for some subset $S\subseteq A$; i.e. the union of multiples in $I$ of elements of $S$ has size $<|S|$.

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 each $n\ge 1$, define $f(n)$ to be the minimal real number with the following property:

For every set $A=\{a_1,\dots,a_n\}\subset\mathbb{N}\cap[2,\infty)$ with $|A|=n$ and $m=\max(A)$, and for every interval $I$ consisting of $\lfloor f(n)m\rfloor$ consecutive integers, there exist distinct integers $x_1,\dots,x_n\in I$ such that $a_i\mid x_i$ for all $i$.

(There is a mild ambiguity in the problem statement about whether the interval length is exactly $f(n)m$ or an integer rounding; for the purposes of rigorous inequalities below I will prove statements for integer multiples, which implies corresponding bounds for any reasonable rounding convention.)

2) QUICK LITERATURE/CONTEXT CHECK

Using only what is stated in the problem text: Erdős--Surányi proved \[(\log n)^c \ll f(n) \ll n^{1/2}\] for some constant $c>0$.

3) ATTACK PLAN

- Prove easy universal lower/upper bounds by extremal examples and matching arguments. - For upper bounds, model the problem as a bipartite matching between divisors $a_i$ and integers in the interval.

4) WORK

Lemma 709.1 (Trivial lower bound $f(n)\ge 1$). For every $n\ge 1$, $f(n)\ge 1$.

Proof. Fix $n\ge 1$. Consider any $A$ with $m=\max(A)$. If an interval $I$ contains fewer than $m$ consecutive integers, then it is possible to choose $I$ to avoid all multiples of $m$ (e.g. $I=\{1,2,\dots,m-1\}$). In such an interval there is no integer divisible by $m$, so we cannot assign a distinct $x_i$ to the element of $A$ equal to $m$. Hence, to guarantee a solution for all intervals, we need interval length at least $m$, i.e. $f(n)\ge 1$. $\square$

Lemma 709.2 (General upper bound $f(n)\le n$). For every $n\ge 1$ and every finite $A\subset\mathbb{N}\cap[2,\infty)$ with $|A|=n$ and $m=\max(A)$, every interval $I$ of $nm$ consecutive integers contains distinct $x_1,\dots,x_n\in I$ with $a_i\mid x_i$ for all $i$. In particular, $f(n)\le n$.

Proof. Let $A=\{a_1,\dots,a_n\}$ and let $I$ be any interval of $nm$ consecutive integers. Construct a bipartite graph $H$ with left vertex set $A$ and right vertex set $I$, where we connect $a\in A$ to $x\in I$ iff $a\mid x$. We seek a matching that covers all left vertices.

By Hall's marriage theorem, it suffices to show that for every subset $S\subseteq A$, its neighborhood \[ N(S)=\{x\in I:\exists a\in S\text{ with }a\mid x\} \] has size at least $|S|$.

Fix a nonempty $S\subseteq A$ and let $d=\min S$. Every multiple of $d$ that lies in $I$ belongs to $N(S)$ (because it is divisible by $d\in S$), so $|N(S)|$ is at least the number of multiples of $d$ in $I$. Write $|I|=nm$. In any block of $nm$ consecutive integers, the number of multiples of $d$ is at least $\lfloor nm/d\rfloor$. Since $d\le m$, we have $nm/d\ge n$, hence $\lfloor nm/d\rfloor\ge n$. Therefore $|N(S)|\ge n$. Finally, because $|S|\le n$, we have $|N(S)|\ge n\ge |S|$, establishing Hall's condition. Thus $H$ contains a matching of size $n$, i.e. distinct $x_1,\dots,x_n\in I$ with $a_i\mid x_i$. $\square$

Lemma 709.3 (Exact value for $n=2$: $f(2)=2$ in the integer-multiple model). If we restrict attention to intervals of integer length $t\,\max(A)$ with $t\in\mathbb{N}$, then $t=1$ does not suffice for $n=2$, while $t=2$ always suffices. Hence in this integer-multiple model, $f(2)=2$.

Proof. Lower bound: $t=1$ fails. Take $A=\{2,3\}$, so $m=3$. Consider the interval $I=\{5,6,7\}$ of length $m$. The only multiple of $3$ in $I$ is $6$, and the only multiple of $2$ in $I$ is also $6$. So there do not exist distinct $x_1,x_2\in I$ with $2\mid x_1$ and $3\mid x_2$. Thus $t=1$ fails.

Upper bound: $t=2$ suffices. Lemma 709.2 with $n=2$ shows that any interval of $2m$ consecutive integers admits such a matching. Therefore $t=2$ suffices for all $A$ with $|A|=2$. $\square$

FAST REALITY CHECK (limited brute force for $n=2$). I brute-forced all $A$ with $|A|=2$, $\max(A)\le 20$, and all interval starts $t\le 500$. Result: $t=1$ fails (e.g. $A=\{2,3\}$ with interval $\{5,6,7\}$), while $t=2$ worked for all tested instances.

5) VERIFICATION

- Lemma 709.2: The key inequality is that any interval of length $nm$ contains at least $\lfloor nm/d\rfloor\ge n$ multiples of $d\le m$. This is correct because multiples of $d$ occur every $d$ integers, so among $nm$ consecutive integers there are at least $\lfloor nm/d\rfloor$ multiples. - Hall is applied correctly: $|N(S)|\ge n\ge |S|$ for all $S$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. I proved the unconditional bounds $1\le f(n)\le n$ (Lemmas 709.1 and 709.2) and, in the integer-multiple model, $f(2)=2$ (Lemma 709.3). I also ran a finite brute-force sanity check for $n=2$ (reported above).

(ii) First gap (crisp). Close the gap between $f(n)\le n$ and the much smaller upper bound $f(n)\ll n^{1/2}$ stated in the problem text, or determine the true asymptotic behavior of $f(n)$.

(iii) Top 3 next moves. 1. Strengthen the Hall lower bound $|N(S)|\ge n$ by using the full divisor structure of $S$ rather than just $\min S$, aiming for shorter intervals. 2. Search for extremal $A$ that make matching difficult (many $a_i$ sharing large common multiples) and try to prove lower bounds from explicit constructions. 3. Implement a computational optimizer for small $n$ to guess the exact $f(n)$ and the structure of extremal sets $A$.

(iv) Minimal counterexample structure. A minimal obstruction to a candidate bound $f(n)\le c$ would be a set $A$ with $m=\max(A)$ and an interval $I$ of $\approx cm$ consecutive integers such that the divisibility bipartite graph fails Hall's condition for some subset $S\subseteq A$; i.e. the union of multiples in $I$ of elements of $S$ has size $<|S|$.