Erdős Problem #708

Erdős Problem 708 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/708

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/708.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/708.tex.

1) FORMAL RESTATEMENT

As written: For each $n\in\mathbb{N}$, define $g(n)$ to be the minimal integer such that for every set $A\subset\mathbb{N}\cap[2,\infty)$ with $|A|=n$, and every set $I$ of $\max(A)$ consecutive integers, there exists $B\subseteq I$ with $|B|=g(n)$ such that \[ \prod_{a\in A} a\ \big|\ \prod_{b\in B} b. \] Question: is $g(n)\le (2+o(1))n$? perhaps even $g(n)\le 2n$?

Ambiguity/misstatement. The "$|B|=g(n)$" clause is incompatible with the subsequent discussion in the problem text. Indeed, because $B\subseteq I$ we always have $|B|\le |I|=\max(A)$. But for fixed $n$, we may choose $A=\{2,3,\dots,n+1\}$, for which $\max(A)=n+1$. If the definition required existence of a subset $B$ of exactly size $g(n)$ for every such $A$, then necessarily $g(n)\le n+1$, which would make an asymptotic bound like $g(n)\le (2+o(1))n$ vacuous.

Minimal corrected statement (standard convention). Define $g(n)$ as the minimal integer such that for every $A$ and $I$ as above, there exists $B\subseteq I$ with \[ |B|\le g(n)\quad\text{and}\quad \prod_{a\in A} a\mid \prod_{b\in B} b. \] This "$\le g(n)$" formulation is monotone: if a set $B$ works, any superset also works. I interpret the problem under this corrected definition.

2) QUICK LITERATURE/CONTEXT CHECK

I will only use what is explicitly stated in the problem text. It states that Erdős--Surányi proved $g(n)\ge (2-o(1))n$ and $g(3)=4$, and that Gallai observed $g(2)=2$.

3) ATTACK PLAN

- First, resolve the ambiguity (done above). - Prove exact values for small $n$ and derive any unconditional general inequalities. - Attempt either (a) a constructive upper bound $g(n)\le 2n$ (or $\le (2+o(1))n$), or (b) a construction forcing $g(n)>2n$.

I do not obtain (a) or (b) here; I record rigorous small-$n$ results and structural equivalences.

4) WORK

Lemma 708.1 (Literal "$|B|=g(n)$" forces $g(n)\le n+1$). If one insists on the literal definition with "$|B|=g(n)$" for all $A$, then necessarily $g(n)\le n+1$ for every $n\ge 1$.

Proof. Assume the literal definition. Fix $n\ge 1$ and choose $A_0=\{2,3,\dots,n+1\}$, so $|A_0|=n$ and $\max(A_0)=n+1$. For any interval $I$ of $\max(A_0)=n+1$ consecutive integers, any subset $B\subseteq I$ satisfies $|B|\le |I|=n+1$. But the definition requires existence of a subset $B\subseteq I$ with $|B|=g(n)$. Therefore $g(n)\le n+1$. $\square$

Lemma 708.2 ($p$-adic valuation reformulation). Let $A,B\subset\mathbb{N}$ be finite. Then \[ \prod_{a\in A} a\mid \prod_{b\in B} b \] if and only if for every prime $p$, \[ \sum_{a\in A} v_p(a)\le \sum_{b\in B} v_p(b), \] where $v_p(x)$ is the exponent of $p$ in the prime factorization of $x$.

Proof. Write the prime factorizations \[ \prod_{a\in A} a=\prod_p p^{\alpha_p},\qquad \prod_{b\in B} b=\prod_p p^{\beta_p}, \] where the products are over all primes and all but finitely many exponents are $0$. Then $\alpha_p=\sum_{a\in A} v_p(a)$ and $\beta_p=\sum_{b\in B} v_p(b)$. The divisibility condition is equivalent to $\alpha_p\le \beta_p$ for every prime $p$. $\square$

Lemma 708.3 (Exact values $g(1)=1$ and $g(2)=2$ under the corrected definition). Under the corrected "$|B|\le g(n)$" definition: \[ g(1)=1,\qquad g(2)=2. \]

Proof. Case $n=1$. Let $A=\{a\}$ with $a\ge 2$ and let $I$ be any set of $a$ consecutive integers. Among any $a$ consecutive integers, there is exactly one multiple of $a$ (because residues mod $a$ are all represented exactly once). Choose $B$ to be that singleton $\{b\}$; then $a\mid b$, so $\prod_{a\in A}a=a$ divides $b=\prod_{b\in B}b$. Thus $g(1)\le 1$ and clearly $g(1)\ge 1$, hence $g(1)=1$.

Case $n=2$. Let $A=\{a_1,a_2\}$ with $2\le a_1<a_2$ and put $m=a_2=\max(A)$. Let $I$ be any set of $m$ consecutive integers. As above, $I$ contains some $x$ divisible by $m$. Also, because $m\ge a_1$, the set $I$ contains at least $\lfloor m/a_1\rfloor\ge 1$ multiples of $a_1$; let $y$ be one such multiple. If $x\ne y$, then with $B=\{x,y\}$ we have $a_1a_2\mid xy$. If $x=y$, then $x$ is a multiple of $m$ and of $a_1$, hence in particular a multiple of $a_1$; but $I$ contains at least two multiples of $a_1$ whenever $m\ge 2a_1$. If instead $m<2a_1$, then $a_1>m/2$ and so $a_1$ cannot divide $m$ (since $m=ka_1$ would force $k=1$), implying the unique multiple of $m$ in $I$ is not a multiple of $a_1$; so the collision $x=y$ cannot occur. Therefore in all cases we can choose two distinct multiples $x$ of $a_2$ and $y$ of $a_1$ in $I$, giving $a_1a_2\mid xy$. So $g(2)\le 2$. On the other hand, take $A=\{2,3\}$ and $I=\{5,6,7\}$ (three consecutive integers). The only multiple of $3$ in $I$ is $6$, and the only multiple of $2$ in $I$ is also $6$, so no singleton $B$ works. Hence $g(2)\ge 2$. Thus $g(2)=2$. $\square$

FAST REALITY CHECK (limited brute force). I ran an exhaustive search for the corrected definition over all $A\subseteq\{2,\dots,\max A\}$ with $|A|=n$, with $\max(A)\le 10$, and all interval starts $t\le 200$ (so $I=\{t+1,\dots,t+\max(A)\}$). The worst minimal $|B|$ found in this limited search was:

 n=1: worst minimal |B| = 1
 n=2: worst minimal |B| = 2
 n=3: worst minimal |B| = 3   (no instance requiring 4 was found in this search window)

This does not contradict the stated fact $g(3)=4$, because my search only covered $\max(A)\le 10$ and starts $t\le 200$.

5) VERIFICATION

- Lemma 708.1 is a pure cardinality obstruction and is correct under the literal reading. - Lemma 708.2 is a standard equivalence and follows directly from unique prime factorization. - Lemma 708.3: the only delicate point is the collision case $x=y$ for $n=2$; the proof splits into $m\ge 2a_1$ (guaranteeing at least two multiples of $a_1$ in $I$) and $m<2a_1$ (where collision is impossible). - Computation: I explicitly state the finite search domain.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. I resolved a definitional ambiguity: the literal "$|B|=g(n)$" reading forces $g(n)\le n+1$ (Lemma 708.1) and makes the asymptotic question trivial, so the meaningful formulation is "$|B|\le g(n)$". Under the corrected formulation I proved $g(1)=1$ and $g(2)=2$ (Lemma 708.3) and gave a valuation reformulation (Lemma 708.2). I also performed a limited brute-force sanity check (reported above).

(ii) First gap (crisp). Under the corrected definition, prove or disprove the upper bound $g(n)\le 2n$ for all $n$ (or at least establish $g(n)\le (2+o(1))n$).

(iii) Top 3 next moves. 1. Reproduce (from scratch) the Erdős--Surányi lower bound construction mentioned in the text and isolate the exact mechanism forcing $\approx 2n$. 2. Build an explicit algorithm selecting $B$ from any interval of length $\max(A)$ and attempt to prove it always uses at most $2n$ numbers; the natural invariant is prime-exponent coverage (Lemma 708.2). 3. Computationally search for an explicit $(n=3)$ instance requiring $4$ elements (to understand the obstruction pattern), then try to generalize the obstruction.

(iv) Minimal counterexample structure. A minimal counterexample to $g(n)\le 2n$ (if it exists) would consist of a set $A$ of $n$ integers with $m=\max(A)$ and an interval $I$ of $m$ consecutive integers such that every subset $B\subseteq I$ with $|B|\le 2n$ fails the prime-exponent inequalities in Lemma 708.2. One expects such a counterexample to force many distinct primes (or repeated prime powers) across $A$ while $I$ is arranged so that high powers of those primes are scarce.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

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

As written: For each $n\in\mathbb{N}$, define $g(n)$ to be the minimal integer such that for every set $A\subset\mathbb{N}\cap[2,\infty)$ with $|A|=n$, and every set $I$ of $\max(A)$ consecutive integers, there exists $B\subseteq I$ with $|B|=g(n)$ such that \[ \prod_{a\in A} a\ \big|\ \prod_{b\in B} b. \] Question: is $g(n)\le (2+o(1))n$? perhaps even $g(n)\le 2n$?

Ambiguity/misstatement. The "$|B|=g(n)$" clause is incompatible with the subsequent discussion in the problem text. Indeed, because $B\subseteq I$ we always have $|B|\le |I|=\max(A)$. But for fixed $n$, we may choose $A=\{2,3,\dots,n+1\}$, for which $\max(A)=n+1$. If the definition required existence of a subset $B$ of exactly size $g(n)$ for every such $A$, then necessarily $g(n)\le n+1$, which would make an asymptotic bound like $g(n)\le (2+o(1))n$ vacuous.

Minimal corrected statement (standard convention). Define $g(n)$ as the minimal integer such that for every $A$ and $I$ as above, there exists $B\subseteq I$ with \[ |B|\le g(n)\quad\text{and}\quad \prod_{a\in A} a\mid \prod_{b\in B} b. \] This "$\le g(n)$" formulation is monotone: if a set $B$ works, any superset also works. I interpret the problem under this corrected definition.

2) QUICK LITERATURE/CONTEXT CHECK

I will only use what is explicitly stated in the problem text. It states that Erdős--Surányi proved $g(n)\ge (2-o(1))n$ and $g(3)=4$, and that Gallai observed $g(2)=2$.

3) ATTACK PLAN

- First, resolve the ambiguity (done above). - Prove exact values for small $n$ and derive any unconditional general inequalities. - Attempt either (a) a constructive upper bound $g(n)\le 2n$ (or $\le (2+o(1))n$), or (b) a construction forcing $g(n)>2n$.

I do not obtain (a) or (b) here; I record rigorous small-$n$ results and structural equivalences.

4) WORK

Lemma 708.1 (Literal "$|B|=g(n)$" forces $g(n)\le n+1$). If one insists on the literal definition with "$|B|=g(n)$" for all $A$, then necessarily $g(n)\le n+1$ for every $n\ge 1$.

Proof. Assume the literal definition. Fix $n\ge 1$ and choose $A_0=\{2,3,\dots,n+1\}$, so $|A_0|=n$ and $\max(A_0)=n+1$. For any interval $I$ of $\max(A_0)=n+1$ consecutive integers, any subset $B\subseteq I$ satisfies $|B|\le |I|=n+1$. But the definition requires existence of a subset $B\subseteq I$ with $|B|=g(n)$. Therefore $g(n)\le n+1$. $\square$

Lemma 708.2 ($p$-adic valuation reformulation). Let $A,B\subset\mathbb{N}$ be finite. Then \[ \prod_{a\in A} a\mid \prod_{b\in B} b \] if and only if for every prime $p$, \[ \sum_{a\in A} v_p(a)\le \sum_{b\in B} v_p(b), \] where $v_p(x)$ is the exponent of $p$ in the prime factorization of $x$.

Proof. Write the prime factorizations \[ \prod_{a\in A} a=\prod_p p^{\alpha_p},\qquad \prod_{b\in B} b=\prod_p p^{\beta_p}, \] where the products are over all primes and all but finitely many exponents are $0$. Then $\alpha_p=\sum_{a\in A} v_p(a)$ and $\beta_p=\sum_{b\in B} v_p(b)$. The divisibility condition is equivalent to $\alpha_p\le \beta_p$ for every prime $p$. $\square$

Lemma 708.3 (Exact values $g(1)=1$ and $g(2)=2$ under the corrected definition). Under the corrected "$|B|\le g(n)$" definition: \[ g(1)=1,\qquad g(2)=2. \]

Proof. Case $n=1$. Let $A=\{a\}$ with $a\ge 2$ and let $I$ be any set of $a$ consecutive integers. Among any $a$ consecutive integers, there is exactly one multiple of $a$ (because residues mod $a$ are all represented exactly once). Choose $B$ to be that singleton $\{b\}$; then $a\mid b$, so $\prod_{a\in A}a=a$ divides $b=\prod_{b\in B}b$. Thus $g(1)\le 1$ and clearly $g(1)\ge 1$, hence $g(1)=1$.

Case $n=2$. Let $A=\{a_1,a_2\}$ with $2\le a_1<a_2$ and put $m=a_2=\max(A)$. Let $I$ be any set of $m$ consecutive integers. As above, $I$ contains some $x$ divisible by $m$. Also, because $m\ge a_1$, the set $I$ contains at least $\lfloor m/a_1\rfloor\ge 1$ multiples of $a_1$; let $y$ be one such multiple. If $x\ne y$, then with $B=\{x,y\}$ we have $a_1a_2\mid xy$. If $x=y$, then $x$ is a multiple of $m$ and of $a_1$, hence in particular a multiple of $a_1$; but $I$ contains at least two multiples of $a_1$ whenever $m\ge 2a_1$. If instead $m<2a_1$, then $a_1>m/2$ and so $a_1$ cannot divide $m$ (since $m=ka_1$ would force $k=1$), implying the unique multiple of $m$ in $I$ is not a multiple of $a_1$; so the collision $x=y$ cannot occur. Therefore in all cases we can choose two distinct multiples $x$ of $a_2$ and $y$ of $a_1$ in $I$, giving $a_1a_2\mid xy$. So $g(2)\le 2$. On the other hand, take $A=\{2,3\}$ and $I=\{5,6,7\}$ (three consecutive integers). The only multiple of $3$ in $I$ is $6$, and the only multiple of $2$ in $I$ is also $6$, so no singleton $B$ works. Hence $g(2)\ge 2$. Thus $g(2)=2$. $\square$

FAST REALITY CHECK (limited brute force). I ran an exhaustive search for the corrected definition over all $A\subseteq\{2,\dots,\max A\}$ with $|A|=n$, with $\max(A)\le 10$, and all interval starts $t\le 200$ (so $I=\{t+1,\dots,t+\max(A)\}$). The worst minimal $|B|$ found in this limited search was:

 n=1: worst minimal |B| = 1
 n=2: worst minimal |B| = 2
 n=3: worst minimal |B| = 3   (no instance requiring 4 was found in this search window)

This does not contradict the stated fact $g(3)=4$, because my search only covered $\max(A)\le 10$ and starts $t\le 200$.

5) VERIFICATION

- Lemma 708.1 is a pure cardinality obstruction and is correct under the literal reading. - Lemma 708.2 is a standard equivalence and follows directly from unique prime factorization. - Lemma 708.3: the only delicate point is the collision case $x=y$ for $n=2$; the proof splits into $m\ge 2a_1$ (guaranteeing at least two multiples of $a_1$ in $I$) and $m<2a_1$ (where collision is impossible). - Computation: I explicitly state the finite search domain.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. I resolved a definitional ambiguity: the literal "$|B|=g(n)$" reading forces $g(n)\le n+1$ (Lemma 708.1) and makes the asymptotic question trivial, so the meaningful formulation is "$|B|\le g(n)$". Under the corrected formulation I proved $g(1)=1$ and $g(2)=2$ (Lemma 708.3) and gave a valuation reformulation (Lemma 708.2). I also performed a limited brute-force sanity check (reported above).

(ii) First gap (crisp). Under the corrected definition, prove or disprove the upper bound $g(n)\le 2n$ for all $n$ (or at least establish $g(n)\le (2+o(1))n$).

(iii) Top 3 next moves. 1. Reproduce (from scratch) the Erdős--Surányi lower bound construction mentioned in the text and isolate the exact mechanism forcing $\approx 2n$. 2. Build an explicit algorithm selecting $B$ from any interval of length $\max(A)$ and attempt to prove it always uses at most $2n$ numbers; the natural invariant is prime-exponent coverage (Lemma 708.2). 3. Computationally search for an explicit $(n=3)$ instance requiring $4$ elements (to understand the obstruction pattern), then try to generalize the obstruction.

(iv) Minimal counterexample structure. A minimal counterexample to $g(n)\le 2n$ (if it exists) would consist of a set $A$ of $n$ integers with $m=\max(A)$ and an interval $I$ of $m$ consecutive integers such that every subset $B\subseteq I$ with $|B|\le 2n$ fails the prime-exponent inequalities in Lemma 708.2. One expects such a counterexample to force many distinct primes (or repeated prime powers) across $A$ while $I$ is arranged so that high powers of those primes are scarce.