Erdős Problem #856

Erdős Problem 856 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

FORMAL RESTATEMENT

Fix an integer $k\ge 3$. For an integer $N\ge 1$, define \[ f_k(N):=\max\Bigl\{\sum_{n\in A}\frac{1}{n}:\ A\subseteq\{1,2,\dots,N\},\ \text{and $A$ contains no subset $S$ of size $k$ with}\ \\ \qquad\qquad\qquad\qquad\qquad \operatorname{lcm}(a,b)=\operatorname{lcm}(a',b')\ \text{for all distinct }a,b,a',b'\in S\Bigr\}. \] Equivalently: there do not exist distinct $n_1,\dots,n_k\in A$ and an integer $L$ such that $\operatorname{lcm}(n_i,n_j)=L$ for all $i\ne j$.

The task is to estimate the growth of $f_k(N)$ as $N\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not import external results beyond what is explicitly stated in the problem file. The file states Erdős' upper bound $f_k(N)\ll \log N/\log\log N$ (with a sketch), and mentions more refined bounds of the form $(\log N)^{b_k-o(1)}\le f_k(N)\le (\log N)^{c_k+o(1)}$ from Tang--Zhang $2025$ and a connection to the sunflower conjecture.

ATTACK PLAN

• Proof-track: Make Erdős' sketch gap-free: prove the key "$<k$ representations" lemma and supply a self-contained lower bound on $\sum_{p\le N} 1/p$.
• Lower bounds: Exhibit large admissible families $A$ giving nontrivial $\sum_{n\in A} 1/n$.
• Reality-check: For small $N$ and $k=3$, compute the exact optimum by brute force to sanity-check the forbidden configuration.

WORK

Lemma 856.1 (Too many $t=ap$ representations create a forbidden $k$-tuple). Let $A\subseteq\{1,\dots,N\}$ satisfy the "no $k$ with constant pairwise lcm" condition. Fix an integer $t$. Consider representations \[ t = a p, \] where $a\in A$ and $p$ is prime. Then the number of such representations is at most $k-1$.

Proof. Suppose for contradiction that there are $k$ distinct representations $t=a_i p_i$ with $a_i\in A$ and $p_i$ prime. If $p_i=p_j$ then $a_i=t/p_i=a_j$, so distinct representations force the primes $p_1,\dots,p_k$ (hence also $a_1,\dots,a_k$) to be pairwise distinct.

Fix $i\ne j$. We claim $\operatorname{lcm}(a_i,a_j)=t$. Write the prime factorization of $t$ as $t=\prod_q q^{e_q}$. For each prime $q$, the exponent of $q$ in $a_i=t/p_i$ is:

• $e_q-1$ if $q=p_i$,
• $e_q$ if $q\ne p_i$.

If $i\ne j$, then for $q=p_i$ we have $q\ne p_j$, so the exponent of $q$ in $a_j$ is $e_q$, while in $a_i$ it is $e_q-1$. Thus the maximum exponent of $q$ across $a_i,a_j$ is $e_q$. Similarly for $q=p_j$. For any other prime $q$, both $a_i$ and $a_j$ have exponent $e_q$. Therefore the lcm, which takes the coordinatewise maximum of prime exponents, equals $\prod_q q^{e_q}=t$.

Hence the $k$ distinct elements $a_1,\dots,a_k\in A$ satisfy that every pair has lcm equal to $t$, contradicting the defining property of $A$. Thus there are at most $k-1$ representations. $\square$

Lemma 856.2 (Elementary lower bound for the prime harmonic sum). For every integer $N\ge 3$, \[ \sum_{p\le N}\frac{1}{p} \ge \log\log(N+1)-1. \]

Proof. Consider the finite Euler product \[ P(N):=\prod_{p\le N}\left(1-\frac{1}{p}\right)^{-1}. \] Expanding $\prod_{p\le N}(1-1/p)^{-1}$ as a product of geometric series gives \[ P(N)=\sum_{m\in\mathbb{N}:\ \text{all prime factors of }m\le N} \frac{1}{m} \ \ge\ \sum_{m=1}^{N} \frac{1}{m}=:H_N. \] Thus $\log P(N)\ge \log H_N$.

Next, for $0<t\le 1/2$ one has the inequality $-\log(1-t)\le t+t^2$ (for example by comparing Taylor series with a remainder bound). For each prime $p\ge 2$ we have $t=1/p\le 1/2$, so \[ \log P(N)=\sum_{p\le N} -\log\left(1-\frac{1}{p}\right) \le \sum_{p\le N}\left(\frac{1}{p}+\frac{1}{p^2}\right) = \sum_{p\le N}\frac{1}{p} + \sum_{p\le N}\frac{1}{p^2}. \] Since $\sum_{p\le N} 1/p^2 \le \sum_{n\ge 2} 1/n^2 < 1$, we obtain \[ \log P(N) \le \sum_{p\le N}\frac{1}{p} + 1. \] Combine with $\log P(N)\ge \log H_N$ to get \[ \sum_{p\le N}\frac{1}{p} \ge \log H_N - 1. \] Finally, the harmonic number satisfies $H_N\ge \int_1^{N+1}\frac{dt}{t}=\log(N+1)$, hence $\log H_N\ge \log\log(N+1)$. This gives the claimed bound. $\square$

Proposition 856.3 (Erdős-type upper bound, fully justified). For every $N\ge 3$ and every $k\ge 3$, \[ f_k(N) \le \frac{k\,H_{N^2}}{\sum_{p\le N} \frac{1}{p}} \ \le\ \frac{k\,(1+2\log N)}{\log\log(N+1)-1}. \] In particular $f_k(N)\ll_k \log N/\log\log N$.

Proof. Let $A\subseteq\{1,\dots,N\}$ be admissible. Consider \[ S := \sum_{a\in A}\frac{1}{a}\sum_{p\le N}\frac{1}{p} =\sum_{a\in A}\sum_{p\le N}\frac{1}{ap}. \] Group terms by $t=ap$: \[ S = \sum_{t\le N^2} \frac{1}{t}\,R(t), \] where $R(t)$ is the number of representations $t=ap$ with $a\in A$ and $p$ prime (necessarily $p\le N$ and $a\le N$). By Lemma 856.1, $R(t)\le k-1<k$ for every $t$, hence \[ S \le k\sum_{t\le N^2}\frac{1}{t} = k H_{N^2}. \] Therefore \[ \sum_{a\in A}\frac{1}{a} \le \frac{kH_{N^2}}{\sum_{p\le N} 1/p}. \] Using $H_{N^2}\le 1+\int_1^{N^2} \frac{dt}{t}=1+2\log N$ and Lemma 856.2 for the denominator gives the explicit bound. Maximizing over admissible $A$ yields the same bound for $f_k(N)$. $\square$

Lemma 856.4 (A simple admissible lower bound from primes). For every $k\ge 3$ and $N\ge 2$, the set $A=\{p\le N: p\text{ prime}\}$ is admissible. Consequently, \[ f_k(N) \ge \sum_{p\le N}\frac{1}{p}. \]

Proof. Take any distinct primes $q_1,\dots,q_k\le N$. For $i\ne j$, $\operatorname{lcm}(q_i,q_j)=q_i q_j$, which depends on the pair $(i,j)$ and is not constant across all pairs because, for instance, $\operatorname{lcm}(q_1,q_2)=q_1q_2\ne q_1q_3=\operatorname{lcm}(q_1,q_3)$ when $q_2\ne q_3$. Thus no subset of $k$ primes has constant pairwise lcm, so the set of primes is admissible. The displayed lower bound follows immediately. $\square$

FAST REALITY CHECK (exact optimization for $k=3$ and small $N$). For $k=3$ and small $N$ I brute-forced all subsets $A\subseteq\{1,\dots,N\}$ and computed the maximum of $\sum_{n\in A}1/n$ subject to the constraint that no triple has constant pairwise lcm.

Exact results found:

N=10: f_3(N)=2.662301587301587
  best A=[1,2,3,4,5,7,8,9]
N=12: f_3(N)=2.753210678210678
  best A=[1,2,3,4,5,7,8,9,11]
N=15: f_3(N)=2.830133755133755
  best A=[1,2,3,4,5,7,8,9,11,13]
N=18: f_3(N)=2.9514572845455196
  best A=[1,2,3,4,5,7,8,9,11,13,16,17]
N=20: f_3(N)=3.004088863492888
  best A=[1,2,3,4,5,7,8,9,11,13,16,17,19]

(Here "best A" is one maximizer found; there can be others.)

VERIFICATION

• Lemma 856.1: The lcm computation is checked prime-by-prime using exponents; it uses only the fact that $a_i=t/p_i$ removes exactly one copy of the prime $p_i$ from $t$.
• Lemma 856.2: The only analytic ingredient is the inequality $-\log(1-t)\le t+t^2$ for $t\le 1/2$, which follows from Taylor expansion with remainder.
• Proposition 856.3: The regrouping by $t=ap$ is exact because every term $1/(ap)$ corresponds to a unique $t$.
• Computation: For $N\le 20$ the brute-force search checks all $2^N$ subsets, so the reported optima are exact.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. For all $k\ge 3$, $f_k(N)\ll_k \log N/\log\log N$ with an explicit bound (Proposition 856.3). Also $f_k(N)\ge \sum_{p\le N} 1/p$ (Lemma 856.4). For $k=3$ and $N\le 20$ the exact values above were computed.
2. (ii) First gap (crisp). Determine the correct asymptotic order of $f_k(N)$ for each fixed $k\ge 3$ (e.g. decide whether $f_k(N)$ grows like $(\log N)^{\alpha_k+o(1)}$ for some explicit exponent $\alpha_k$).
3. (iii) Top 3 next moves.
   1. For $k=3$, classify exactly which triples $(a,b,c)$ have constant pairwise lcm, and use that structure to build larger-weight admissible sets $A$ (potentially via container/entropy methods).
   2. Extend exact computations for $k=3$ to larger $N$ (say $N\le 35$ with branch-and-bound) to guess the growth rate and extremal structure.
   3. For general $k$, translate the condition "constant pairwise lcm" into a set-system/sunflower language on prime-exponent vectors and target improved upper bounds.
4. (iv) Minimal counterexample structure. A near-extremal family $A$ achieving very large $\sum_{n\in A}1/n$ while avoiding constant-pairwise-lcm $k$-tuples would likely concentrate on integers with restricted prime factor patterns (so that many $t=ap$ representations are forced but still kept below $k$ for each $t$).

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

Fix an integer $k\ge 3$. For an integer $N\ge 1$, define \[ f_k(N):=\max\Bigl\{\sum_{n\in A}\frac{1}{n}:\ A\subseteq\{1,2,\dots,N\},\ \text{and $A$ contains no subset $S$ of size $k$ with}\ \\ \qquad\qquad\qquad\qquad\qquad \operatorname{lcm}(a,b)=\operatorname{lcm}(a',b')\ \text{for all distinct }a,b,a',b'\in S\Bigr\}. \] Equivalently: there do not exist distinct $n_1,\dots,n_k\in A$ and an integer $L$ such that $\operatorname{lcm}(n_i,n_j)=L$ for all $i\ne j$.

The task is to estimate the growth of $f_k(N)$ as $N\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not import external results beyond what is explicitly stated in the problem file. The file states Erdős' upper bound $f_k(N)\ll \log N/\log\log N$ (with a sketch), and mentions more refined bounds of the form $(\log N)^{b_k-o(1)}\le f_k(N)\le (\log N)^{c_k+o(1)}$ from Tang--Zhang $2025$ and a connection to the sunflower conjecture.

ATTACK PLAN

• Proof-track: Make Erdős' sketch gap-free: prove the key "$<k$ representations" lemma and supply a self-contained lower bound on $\sum_{p\le N} 1/p$.
• Lower bounds: Exhibit large admissible families $A$ giving nontrivial $\sum_{n\in A} 1/n$.
• Reality-check: For small $N$ and $k=3$, compute the exact optimum by brute force to sanity-check the forbidden configuration.

WORK

Lemma 856.1 (Too many $t=ap$ representations create a forbidden $k$-tuple). Let $A\subseteq\{1,\dots,N\}$ satisfy the "no $k$ with constant pairwise lcm" condition. Fix an integer $t$. Consider representations \[ t = a p, \] where $a\in A$ and $p$ is prime. Then the number of such representations is at most $k-1$.

Proof. Suppose for contradiction that there are $k$ distinct representations $t=a_i p_i$ with $a_i\in A$ and $p_i$ prime. If $p_i=p_j$ then $a_i=t/p_i=a_j$, so distinct representations force the primes $p_1,\dots,p_k$ (hence also $a_1,\dots,a_k$) to be pairwise distinct.

Fix $i\ne j$. We claim $\operatorname{lcm}(a_i,a_j)=t$. Write the prime factorization of $t$ as $t=\prod_q q^{e_q}$. For each prime $q$, the exponent of $q$ in $a_i=t/p_i$ is:

• $e_q-1$ if $q=p_i$,
• $e_q$ if $q\ne p_i$.

If $i\ne j$, then for $q=p_i$ we have $q\ne p_j$, so the exponent of $q$ in $a_j$ is $e_q$, while in $a_i$ it is $e_q-1$. Thus the maximum exponent of $q$ across $a_i,a_j$ is $e_q$. Similarly for $q=p_j$. For any other prime $q$, both $a_i$ and $a_j$ have exponent $e_q$. Therefore the lcm, which takes the coordinatewise maximum of prime exponents, equals $\prod_q q^{e_q}=t$.

Hence the $k$ distinct elements $a_1,\dots,a_k\in A$ satisfy that every pair has lcm equal to $t$, contradicting the defining property of $A$. Thus there are at most $k-1$ representations. $\square$

Lemma 856.2 (Elementary lower bound for the prime harmonic sum). For every integer $N\ge 3$, \[ \sum_{p\le N}\frac{1}{p} \ge \log\log(N+1)-1. \]

Proof. Consider the finite Euler product \[ P(N):=\prod_{p\le N}\left(1-\frac{1}{p}\right)^{-1}. \] Expanding $\prod_{p\le N}(1-1/p)^{-1}$ as a product of geometric series gives \[ P(N)=\sum_{m\in\mathbb{N}:\ \text{all prime factors of }m\le N} \frac{1}{m} \ \ge\ \sum_{m=1}^{N} \frac{1}{m}=:H_N. \] Thus $\log P(N)\ge \log H_N$.

Next, for $0<t\le 1/2$ one has the inequality $-\log(1-t)\le t+t^2$ (for example by comparing Taylor series with a remainder bound). For each prime $p\ge 2$ we have $t=1/p\le 1/2$, so \[ \log P(N)=\sum_{p\le N} -\log\left(1-\frac{1}{p}\right) \le \sum_{p\le N}\left(\frac{1}{p}+\frac{1}{p^2}\right) = \sum_{p\le N}\frac{1}{p} + \sum_{p\le N}\frac{1}{p^2}. \] Since $\sum_{p\le N} 1/p^2 \le \sum_{n\ge 2} 1/n^2 < 1$, we obtain \[ \log P(N) \le \sum_{p\le N}\frac{1}{p} + 1. \] Combine with $\log P(N)\ge \log H_N$ to get \[ \sum_{p\le N}\frac{1}{p} \ge \log H_N - 1. \] Finally, the harmonic number satisfies $H_N\ge \int_1^{N+1}\frac{dt}{t}=\log(N+1)$, hence $\log H_N\ge \log\log(N+1)$. This gives the claimed bound. $\square$

Proposition 856.3 (Erdős-type upper bound, fully justified). For every $N\ge 3$ and every $k\ge 3$, \[ f_k(N) \le \frac{k\,H_{N^2}}{\sum_{p\le N} \frac{1}{p}} \ \le\ \frac{k\,(1+2\log N)}{\log\log(N+1)-1}. \] In particular $f_k(N)\ll_k \log N/\log\log N$.

Proof. Let $A\subseteq\{1,\dots,N\}$ be admissible. Consider \[ S := \sum_{a\in A}\frac{1}{a}\sum_{p\le N}\frac{1}{p} =\sum_{a\in A}\sum_{p\le N}\frac{1}{ap}. \] Group terms by $t=ap$: \[ S = \sum_{t\le N^2} \frac{1}{t}\,R(t), \] where $R(t)$ is the number of representations $t=ap$ with $a\in A$ and $p$ prime (necessarily $p\le N$ and $a\le N$). By Lemma 856.1, $R(t)\le k-1<k$ for every $t$, hence \[ S \le k\sum_{t\le N^2}\frac{1}{t} = k H_{N^2}. \] Therefore \[ \sum_{a\in A}\frac{1}{a} \le \frac{kH_{N^2}}{\sum_{p\le N} 1/p}. \] Using $H_{N^2}\le 1+\int_1^{N^2} \frac{dt}{t}=1+2\log N$ and Lemma 856.2 for the denominator gives the explicit bound. Maximizing over admissible $A$ yields the same bound for $f_k(N)$. $\square$

Lemma 856.4 (A simple admissible lower bound from primes). For every $k\ge 3$ and $N\ge 2$, the set $A=\{p\le N: p\text{ prime}\}$ is admissible. Consequently, \[ f_k(N) \ge \sum_{p\le N}\frac{1}{p}. \]

Proof. Take any distinct primes $q_1,\dots,q_k\le N$. For $i\ne j$, $\operatorname{lcm}(q_i,q_j)=q_i q_j$, which depends on the pair $(i,j)$ and is not constant across all pairs because, for instance, $\operatorname{lcm}(q_1,q_2)=q_1q_2\ne q_1q_3=\operatorname{lcm}(q_1,q_3)$ when $q_2\ne q_3$. Thus no subset of $k$ primes has constant pairwise lcm, so the set of primes is admissible. The displayed lower bound follows immediately. $\square$

FAST REALITY CHECK (exact optimization for $k=3$ and small $N$). For $k=3$ and small $N$ I brute-forced all subsets $A\subseteq\{1,\dots,N\}$ and computed the maximum of $\sum_{n\in A}1/n$ subject to the constraint that no triple has constant pairwise lcm.

Exact results found:

N=10: f_3(N)=2.662301587301587
  best A=[1,2,3,4,5,7,8,9]
N=12: f_3(N)=2.753210678210678
  best A=[1,2,3,4,5,7,8,9,11]
N=15: f_3(N)=2.830133755133755
  best A=[1,2,3,4,5,7,8,9,11,13]
N=18: f_3(N)=2.9514572845455196
  best A=[1,2,3,4,5,7,8,9,11,13,16,17]
N=20: f_3(N)=3.004088863492888
  best A=[1,2,3,4,5,7,8,9,11,13,16,17,19]

(Here "best A" is one maximizer found; there can be others.)

VERIFICATION

• Lemma 856.1: The lcm computation is checked prime-by-prime using exponents; it uses only the fact that $a_i=t/p_i$ removes exactly one copy of the prime $p_i$ from $t$.
• Lemma 856.2: The only analytic ingredient is the inequality $-\log(1-t)\le t+t^2$ for $t\le 1/2$, which follows from Taylor expansion with remainder.
• Proposition 856.3: The regrouping by $t=ap$ is exact because every term $1/(ap)$ corresponds to a unique $t$.
• Computation: For $N\le 20$ the brute-force search checks all $2^N$ subsets, so the reported optima are exact.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. For all $k\ge 3$, $f_k(N)\ll_k \log N/\log\log N$ with an explicit bound (Proposition 856.3). Also $f_k(N)\ge \sum_{p\le N} 1/p$ (Lemma 856.4). For $k=3$ and $N\le 20$ the exact values above were computed.
2. (ii) First gap (crisp). Determine the correct asymptotic order of $f_k(N)$ for each fixed $k\ge 3$ (e.g. decide whether $f_k(N)$ grows like $(\log N)^{\alpha_k+o(1)}$ for some explicit exponent $\alpha_k$).
3. (iii) Top 3 next moves.
   1. For $k=3$, classify exactly which triples $(a,b,c)$ have constant pairwise lcm, and use that structure to build larger-weight admissible sets $A$ (potentially via container/entropy methods).
   2. Extend exact computations for $k=3$ to larger $N$ (say $N\le 35$ with branch-and-bound) to guess the growth rate and extremal structure.
   3. For general $k$, translate the condition "constant pairwise lcm" into a set-system/sunflower language on prime-exponent vectors and target improved upper bounds.
4. (iv) Minimal counterexample structure. A near-extremal family $A$ achieving very large $\sum_{n\in A}1/n$ while avoiding constant-pairwise-lcm $k$-tuples would likely concentrate on integers with restricted prime factor patterns (so that many $t=ap$ representations are forced but still kept below $k$ for each $t$).