Erdős Problem #1062

Erdős Problem 1062 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

FORMAL RESTATEMENT

For $n\ge 1$, let $f(n)$ be the maximum cardinality of a subset $A\subseteq\{1,2,\dots,n\}$ such that there do not exist three distinct elements $a,b,c\in A$ with $a\mid b$ and $a\mid c$. Equivalently: for each $a\in A$, there is at most one element $b\in A\setminus\{a\}$ with $a\mid b$. The problem asks for the size and asymptotics of $f(n)$, and in particular about $\lim f(n)/n$. The statement also records a known estimate (Lebensold): for large $n$, \[ 0.6725\,n\le f(n)\le 0.6736\,n. \]

QUICK LITERATURE/CONTEXT CHECK

The numerical bounds $0.6725n\le f(n)\le 0.6736n$ are stated in the problem text as due to Lebensold. I do not use or claim any other external results.

ATTACK PLAN

Proof-track: (i) derive structural constraints on the divisibility poset induced by $A$; (ii) build explicit large constructions giving lower bounds; (iii) attempt counting/charging arguments for upper bounds. Disproof-track (for the "limit irrational" question): compute $f(n)/n$ for small $n$ to see behavior; but proving irrationality is far beyond small checks.

WORK

FAST REALITY CHECK. I computed $f(n)$ exactly for $n\le 30$ by branch-and-bound search over subsets, using the defining constraint. Exact values:

 n : f(n)
 1 : 1
 2 : 2
 3 : 2
 4 : 3
 5 : 4
 6 : 4
 7 : 5
 8 : 6
 9 : 6
10 : 7
11 : 8
12 : 8
13 : 9
14 : 10
15 : 10
16 : 11
17 : 12
18 : 12
19 : 13
20 : 14
21 : 14
22 : 15
23 : 16
24 : 16
25 : 17
26 : 18
27 : 19
28 : 20
29 : 21
30 : 21

For instance, $f(30)=21$ (ratio $0.7$), while the simple construction below gives $\lceil 2\cdot 30/3\rceil=20$.

Lemma 1062.1 (no 3-term chains). If $A$ satisfies the condition of the problem, then there do not exist $a<b<c$ in $A$ with $a\mid b$ and $b\mid c$.

Proof. If $a\mid b$ and $b\mid c$, then $a\mid c$. Thus $a$ divides both $b$ and $c$ with $b\ne c$, contradicting the defining property of $A$. $\square$

Lemma 1062.2 (elementary $2n/3$ construction). For every $n\ge 1$, \[ f(n)\ge n-\left\lfloor\frac n3\right\rfloor\ \ge\ \left\lceil\frac{2n}{3}\right\rceil. \] One explicit choice is \[ A:=\Big\{\left\lfloor\tfrac n3\right\rfloor+1,\ \left\lfloor\tfrac n3\right\rfloor+2,\ \dots,\ n\Big\}. \]

Proof. Let $m:=\lfloor n/3\rfloor$ and $A=\{m+1,\dots,n\}$. Then $|A|=n-m$. Take any $a\in A$. Since $a\ge m+1>n/3$, we have $3a>n$. Therefore the only possible multiples of $a$ in $\{1,\dots,n\}$ are $a$ itself and possibly $2a$ (since $2a\le n$ may occur, but $3a$ cannot). In particular, within $A$ the element $a$ can divide at most one other distinct element (namely $2a$ if it lies in $A$). Hence there do not exist distinct $b,c\in A$ with $a\mid b$ and $a\mid c$. This verifies that $A$ is admissible, and yields $f(n)\ge |A|=n-\lfloor n/3\rfloor\ge \lceil 2n/3\rceil$. $\square$

VERIFICATION

Lemma 1062.1 is an immediate logical consequence of the definition. Lemma 1062.2 checks the only possible multiples of $a>n/3$ inside $\{1,\dots,n\}$ and uses $3a>n$ to rule out two distinct multiples beyond $a$ itself. The exact small-$n$ values were computed by an explicit search that maintains, for each potential divisor $d$, the count of already-selected multiples of $d$.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. An explicit construction gives $f(n)\ge \lceil 2n/3\rceil$ for all $n$ (Lemma 1062.2). The problem statement records much sharper bounds for large $n$ (Lebensold): $0.6725n\le f(n)\le 0.6736n$. I also computed $f(n)$ exactly for $n\le 30$ (see the table in WORK).
2. (ii) First gap (crisp). Determine the true asymptotic constant $\lim_{n\to\infty} f(n)/n$ (existence, value) and address whether it is irrational.
3. (iii) Top 3 next moves. $1$ Computation: extend exact/near-exact optimization for $f(n)$ to much larger $n$ to better estimate $f(n)/n$ and detect patterns. $2$ Upper bounds: develop a charging/double-counting argument that forces $|A|\le (\alpha+o(1))n$ for some explicit $\alpha<0.6736$. $3$ Constructions: search for structured sets improving the $2/3$ construction and explain the near-$0.673$ density seen in known bounds.
4. (iv) Minimal counterexample structure. A counterexample to convergence of $f(n)/n$ would require large oscillations in the optimal density across $n$; such oscillations would likely correlate with arithmetic structure of $n$ (e.g. primorial-like ranges) affecting how many divisibility relations can be packed.

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.

FORMAL RESTATEMENT

For $n\ge 1$, let $f(n)$ be the maximum cardinality of a subset $A\subseteq\{1,2,\dots,n\}$ such that there do not exist three distinct elements $a,b,c\in A$ with $a\mid b$ and $a\mid c$. Equivalently: for each $a\in A$, there is at most one element $b\in A\setminus\{a\}$ with $a\mid b$. The problem asks for the size and asymptotics of $f(n)$, and in particular about $\lim f(n)/n$. The statement also records a known estimate (Lebensold): for large $n$, \[ 0.6725\,n\le f(n)\le 0.6736\,n. \]

QUICK LITERATURE/CONTEXT CHECK

The numerical bounds $0.6725n\le f(n)\le 0.6736n$ are stated in the problem text as due to Lebensold. I do not use or claim any other external results.

ATTACK PLAN

Proof-track: (i) derive structural constraints on the divisibility poset induced by $A$; (ii) build explicit large constructions giving lower bounds; (iii) attempt counting/charging arguments for upper bounds. Disproof-track (for the "limit irrational" question): compute $f(n)/n$ for small $n$ to see behavior; but proving irrationality is far beyond small checks.

WORK

FAST REALITY CHECK. I computed $f(n)$ exactly for $n\le 30$ by branch-and-bound search over subsets, using the defining constraint. Exact values:

 n : f(n)
 1 : 1
 2 : 2
 3 : 2
 4 : 3
 5 : 4
 6 : 4
 7 : 5
 8 : 6
 9 : 6
10 : 7
11 : 8
12 : 8
13 : 9
14 : 10
15 : 10
16 : 11
17 : 12
18 : 12
19 : 13
20 : 14
21 : 14
22 : 15
23 : 16
24 : 16
25 : 17
26 : 18
27 : 19
28 : 20
29 : 21
30 : 21

For instance, $f(30)=21$ (ratio $0.7$), while the simple construction below gives $\lceil 2\cdot 30/3\rceil=20$.

Lemma 1062.1 (no 3-term chains). If $A$ satisfies the condition of the problem, then there do not exist $a<b<c$ in $A$ with $a\mid b$ and $b\mid c$.

Proof. If $a\mid b$ and $b\mid c$, then $a\mid c$. Thus $a$ divides both $b$ and $c$ with $b\ne c$, contradicting the defining property of $A$. $\square$

Lemma 1062.2 (elementary $2n/3$ construction). For every $n\ge 1$, \[ f(n)\ge n-\left\lfloor\frac n3\right\rfloor\ \ge\ \left\lceil\frac{2n}{3}\right\rceil. \] One explicit choice is \[ A:=\Big\{\left\lfloor\tfrac n3\right\rfloor+1,\ \left\lfloor\tfrac n3\right\rfloor+2,\ \dots,\ n\Big\}. \]

Proof. Let $m:=\lfloor n/3\rfloor$ and $A=\{m+1,\dots,n\}$. Then $|A|=n-m$. Take any $a\in A$. Since $a\ge m+1>n/3$, we have $3a>n$. Therefore the only possible multiples of $a$ in $\{1,\dots,n\}$ are $a$ itself and possibly $2a$ (since $2a\le n$ may occur, but $3a$ cannot). In particular, within $A$ the element $a$ can divide at most one other distinct element (namely $2a$ if it lies in $A$). Hence there do not exist distinct $b,c\in A$ with $a\mid b$ and $a\mid c$. This verifies that $A$ is admissible, and yields $f(n)\ge |A|=n-\lfloor n/3\rfloor\ge \lceil 2n/3\rceil$. $\square$

VERIFICATION

Lemma 1062.1 is an immediate logical consequence of the definition. Lemma 1062.2 checks the only possible multiples of $a>n/3$ inside $\{1,\dots,n\}$ and uses $3a>n$ to rule out two distinct multiples beyond $a$ itself. The exact small-$n$ values were computed by an explicit search that maintains, for each potential divisor $d$, the count of already-selected multiples of $d$.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. An explicit construction gives $f(n)\ge \lceil 2n/3\rceil$ for all $n$ (Lemma 1062.2). The problem statement records much sharper bounds for large $n$ (Lebensold): $0.6725n\le f(n)\le 0.6736n$. I also computed $f(n)$ exactly for $n\le 30$ (see the table in WORK).
2. (ii) First gap (crisp). Determine the true asymptotic constant $\lim_{n\to\infty} f(n)/n$ (existence, value) and address whether it is irrational.
3. (iii) Top 3 next moves. $1$ Computation: extend exact/near-exact optimization for $f(n)$ to much larger $n$ to better estimate $f(n)/n$ and detect patterns. $2$ Upper bounds: develop a charging/double-counting argument that forces $|A|\le (\alpha+o(1))n$ for some explicit $\alpha<0.6736$. $3$ Constructions: search for structured sets improving the $2/3$ construction and explain the near-$0.673$ density seen in known bounds.
4. (iv) Minimal counterexample structure. A counterexample to convergence of $f(n)/n$ would require large oscillations in the optimal density across $n$; such oscillations would likely correlate with arithmetic structure of $n$ (e.g. primorial-like ranges) affecting how many divisibility relations can be packed.