Erdős Problem #691

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

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Let $A\subseteq\mathbb{N}$. Define the set of multiples of $A$ by \[ M_A:=\{n\ge 1:\ \exists a\in A\text{ with }a\mid n\}. \] We say $A$ is a Behrend sequence if $M_A$ has natural density $1$, i.e. \[ \lim_{x\to\infty}\frac{1}{x}\#(M_A\cap[1,x])=1. \] The problem asks for a necessary and sufficient condition on $A$ for $M_A$ to have density $1$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records:

- If $A$ is a set of primes (or pairwise coprime integers not containing $1$), then $M_A$ has density $1$ iff $\sum_{a\in A}1/a=\infty$.

- For certain “block sequences” built from intervals $(n_k,(1+\eta_k)n_k)$ with lacunary $n_k$, the behavior depends on the parameters and additional growth conditions.

I do not use external references beyond what is explicitly stated; below I prove some general necessary/sufficient conditions but not a full characterization.

3) ATTACK PLAN

Proof track (characterize density $1$): attempt to rewrite $\mathbb{N}\setminus M_A$ as a sifted set and express its density via a sieve/inclusion--exclusion condition on $A$.

Disproof/obstruction track: identify simple necessary obstructions (e.g. common gcd) and broad sufficient conditions (e.g. divergent reciprocal sum on a coprime subfamily).

We give rigorous partial results and then state the remaining gap.

4) WORK

Lemma 691.1 (gcd obstruction). Assume $1\notin A$ and let $g:=\gcd(A)$ (gcd of all elements of $A$). If $g>1$, then $M_A$ has density at most $1/g$ (in particular, strictly less than $1$).

Proof. If $g=\gcd(A)>1$, then every $a\in A$ is divisible by $g$. Hence any multiple of any $a\in A$ is divisible by $g$, so \[ M_A\subseteq \{n\ge 1: g\mid n\}. \] The latter set has natural density $1/g$ (exactly one residue class mod $g$), so the density of $M_A$ (if it exists) is $\le 1/g$, and its upper density is $\le 1/g$ in any case. $\square$

Lemma 691.2 (reduction to a primitive core). Define the subset \[ A^{\min}:=\{a\in A:\ \text{there is no }b\in A\text{ with }b\mid a\text{ and }b<a\}. \] Then $M_A=M_{A^{\min}}$.

Proof. Clearly $M_{A^{\min}}\subseteq M_A$ because $A^{\min}\subseteq A$. For the reverse inclusion, fix $n\in M_A$. Then $n$ is divisible by some $a\in A$. Among all elements of $A$ dividing $n$, choose one of minimal value; call it $a_0$. Such a minimal element exists because the set of positive divisors of $n$ is finite. By construction, no smaller element of $A$ divides $a_0$, hence $a_0\in A^{\min}$. Since $a_0\mid n$, we have $n\in M_{A^{\min}}$. Therefore $M_A\subseteq M_{A^{\min}}$. $\square$

Lemma 691.3 (pairwise-coprime divergent subfamily is sufficient). Assume $A$ contains an infinite subset $B\subseteq A$ such that (i) the elements of $B$ are pairwise coprime, (ii) $1\notin B$, and (iii) $\sum_{b\in B} \frac{1}{b}=\infty$. Then $M_A$ has natural density $1$.

Proof. Since $M_B\subseteq M_A$, it suffices to show $M_B$ has density $1$. Let $B_N:=\{b_1,\dots,b_N\}$ be any finite subset of $B$. Because the $b_i$ are pairwise coprime, the complement \[ C_N:=\{n\ge 1: b_i\nmid n\ \text{for all }1\le i\le N\} \] is periodic modulo $\prod_{i=1}^N b_i$, and by the Chinese remainder theorem its density exists and equals \[ \mathbf{d}(C_N)=\prod_{i=1}^N \Big(1-\frac{1}{b_i}\Big). \] Now let \[ C:=\mathbb{N}\setminus M_B=\{n\ge 1: b\nmid n\ \text{for all }b\in B\}. \] Then $C\subseteq C_N$ for each $N$, hence the upper density satisfies \[ \overline{\mathbf{d}}(C)\le \mathbf{d}(C_N)=\prod_{i=1}^N \Big(1-\frac{1}{b_i}\Big) \quad\text{for all }N. \] Using $\log(1-t)\le -t$ for $t\in(0,1)$, we get \[ \log\Big(\prod_{i=1}^N (1-1/b_i)\Big)=\sum_{i=1}^N \log(1-1/b_i)\le -\sum_{i=1}^N \frac{1}{b_i}. \] Since $\sum_{i=1}^N 1/b_i\to\infty$, the right-hand side tends to $-\infty$, so the product tends to $0$. Therefore $\overline{\mathbf{d}}(C)=0$.

Finally, for any set $S\subseteq\mathbb{N}$, $\underline{\mathbf{d}}(S)=1-\overline{\mathbf{d}}(\mathbb{N}\setminus S)$. Applying this to $S=M_B$ gives \[ \underline{\mathbf{d}}(M_B)=1-\overline{\mathbf{d}}(C)=1. \] Since $\overline{\mathbf{d}}(M_B)\le 1$, we conclude $M_B$ (hence $M_A$) has natural density $1$. $\square$

FAST REALITY CHECK (examples).

- If $1\in A$, then $M_A=\mathbb{N}$ and the density is $1$.

- If $A=\{2^j:j\ge 1\}$, then $M_A$ equals the even integers (every multiple of a power of $2$ is even, and every even integer is a multiple of $2$), so the density is $1/2$, not $1$.

- If $A$ is the set of all primes, then the complement $\mathbb{N}\setminus M_A=\{1\}$ has density $0$, hence $M_A$ has density $1$.

5) VERIFICATION

- Lemma 691.1 is a strict obstruction: if $\gcd(A)>1$ (and $1\notin A$), then density $1$ is impossible.

- Lemma 691.3 is consistent with the special case quoted in the problem statement (pairwise coprime $A$): it recovers “divergent reciprocal sum implies density $1$” without needing any further structure.

- All density computations used only periodicity/CRT for finite sets.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. If $\gcd(A)>1$ and $1\notin A$ then $\mathbf{d}(M_A)\le 1/\gcd(A)<1$ (Lemma 691.1). If $A$ contains a pairwise coprime subfamily $B$ with $\sum_{b\in B}1/b=\infty$, then $\mathbf{d}(M_A)=1$ (Lemma 691.3). Also $M_A$ depends only on the “minimal-by-divisibility” core $A^{\min}$ (Lemma 691.2).

(ii) First gap (crisp). Give a necessary and sufficient condition on an arbitrary $A\subseteq\mathbb{N}$ (with no coprimality assumptions) for $\mathbf{d}(M_A)=1$.

(iii) Top 3 next moves. 1. Prove (or refute) that one may always reduce to a primitive set (no element divides another) and then characterize Behrend-ness by a single divergent series/condition on that primitive set. 2. Develop a sieve/inclusion--exclusion criterion for $\mathbf{d}(\mathbb{N}\setminus M_A)=0$ in terms of finite truncations $A\cap[1,y]$, aiming for a checkable “$\lim_{y\to\infty}$” condition. 3. For structured families (e.g. block sequences), compute the density of the complement by an explicit upper bound on numbers avoiding all blocks, and identify sharp thresholds.

(iv) Minimal counterexample structure. A minimal obstruction to any simple “$\sum 1/a$ diverges” criterion would likely be a set $A$ with heavy overlaps (many shared prime factors) so that $\sum_{a\in A}1/a$ diverges but $\mathbb{N}\setminus M_A$ still has positive density; the block-sequence constructions mentioned in the statement are candidate models for such behavior.

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

Let $A\subseteq\mathbb{N}$. Define the set of multiples of $A$ by \[ M_A:=\{n\ge 1:\ \exists a\in A\text{ with }a\mid n\}. \] We say $A$ is a Behrend sequence if $M_A$ has natural density $1$, i.e. \[ \lim_{x\to\infty}\frac{1}{x}\#(M_A\cap[1,x])=1. \] The problem asks for a necessary and sufficient condition on $A$ for $M_A$ to have density $1$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records:

- If $A$ is a set of primes (or pairwise coprime integers not containing $1$), then $M_A$ has density $1$ iff $\sum_{a\in A}1/a=\infty$.

- For certain “block sequences” built from intervals $(n_k,(1+\eta_k)n_k)$ with lacunary $n_k$, the behavior depends on the parameters and additional growth conditions.

I do not use external references beyond what is explicitly stated; below I prove some general necessary/sufficient conditions but not a full characterization.

3) ATTACK PLAN

Proof track (characterize density $1$): attempt to rewrite $\mathbb{N}\setminus M_A$ as a sifted set and express its density via a sieve/inclusion--exclusion condition on $A$.

Disproof/obstruction track: identify simple necessary obstructions (e.g. common gcd) and broad sufficient conditions (e.g. divergent reciprocal sum on a coprime subfamily).

We give rigorous partial results and then state the remaining gap.

4) WORK

Lemma 691.1 (gcd obstruction). Assume $1\notin A$ and let $g:=\gcd(A)$ (gcd of all elements of $A$). If $g>1$, then $M_A$ has density at most $1/g$ (in particular, strictly less than $1$).

Proof. If $g=\gcd(A)>1$, then every $a\in A$ is divisible by $g$. Hence any multiple of any $a\in A$ is divisible by $g$, so \[ M_A\subseteq \{n\ge 1: g\mid n\}. \] The latter set has natural density $1/g$ (exactly one residue class mod $g$), so the density of $M_A$ (if it exists) is $\le 1/g$, and its upper density is $\le 1/g$ in any case. $\square$

Lemma 691.2 (reduction to a primitive core). Define the subset \[ A^{\min}:=\{a\in A:\ \text{there is no }b\in A\text{ with }b\mid a\text{ and }b<a\}. \] Then $M_A=M_{A^{\min}}$.

Proof. Clearly $M_{A^{\min}}\subseteq M_A$ because $A^{\min}\subseteq A$. For the reverse inclusion, fix $n\in M_A$. Then $n$ is divisible by some $a\in A$. Among all elements of $A$ dividing $n$, choose one of minimal value; call it $a_0$. Such a minimal element exists because the set of positive divisors of $n$ is finite. By construction, no smaller element of $A$ divides $a_0$, hence $a_0\in A^{\min}$. Since $a_0\mid n$, we have $n\in M_{A^{\min}}$. Therefore $M_A\subseteq M_{A^{\min}}$. $\square$

Lemma 691.3 (pairwise-coprime divergent subfamily is sufficient). Assume $A$ contains an infinite subset $B\subseteq A$ such that (i) the elements of $B$ are pairwise coprime, (ii) $1\notin B$, and (iii) $\sum_{b\in B} \frac{1}{b}=\infty$. Then $M_A$ has natural density $1$.

Proof. Since $M_B\subseteq M_A$, it suffices to show $M_B$ has density $1$. Let $B_N:=\{b_1,\dots,b_N\}$ be any finite subset of $B$. Because the $b_i$ are pairwise coprime, the complement \[ C_N:=\{n\ge 1: b_i\nmid n\ \text{for all }1\le i\le N\} \] is periodic modulo $\prod_{i=1}^N b_i$, and by the Chinese remainder theorem its density exists and equals \[ \mathbf{d}(C_N)=\prod_{i=1}^N \Big(1-\frac{1}{b_i}\Big). \] Now let \[ C:=\mathbb{N}\setminus M_B=\{n\ge 1: b\nmid n\ \text{for all }b\in B\}. \] Then $C\subseteq C_N$ for each $N$, hence the upper density satisfies \[ \overline{\mathbf{d}}(C)\le \mathbf{d}(C_N)=\prod_{i=1}^N \Big(1-\frac{1}{b_i}\Big) \quad\text{for all }N. \] Using $\log(1-t)\le -t$ for $t\in(0,1)$, we get \[ \log\Big(\prod_{i=1}^N (1-1/b_i)\Big)=\sum_{i=1}^N \log(1-1/b_i)\le -\sum_{i=1}^N \frac{1}{b_i}. \] Since $\sum_{i=1}^N 1/b_i\to\infty$, the right-hand side tends to $-\infty$, so the product tends to $0$. Therefore $\overline{\mathbf{d}}(C)=0$.

Finally, for any set $S\subseteq\mathbb{N}$, $\underline{\mathbf{d}}(S)=1-\overline{\mathbf{d}}(\mathbb{N}\setminus S)$. Applying this to $S=M_B$ gives \[ \underline{\mathbf{d}}(M_B)=1-\overline{\mathbf{d}}(C)=1. \] Since $\overline{\mathbf{d}}(M_B)\le 1$, we conclude $M_B$ (hence $M_A$) has natural density $1$. $\square$

FAST REALITY CHECK (examples).

- If $1\in A$, then $M_A=\mathbb{N}$ and the density is $1$.

- If $A=\{2^j:j\ge 1\}$, then $M_A$ equals the even integers (every multiple of a power of $2$ is even, and every even integer is a multiple of $2$), so the density is $1/2$, not $1$.

- If $A$ is the set of all primes, then the complement $\mathbb{N}\setminus M_A=\{1\}$ has density $0$, hence $M_A$ has density $1$.

5) VERIFICATION

- Lemma 691.1 is a strict obstruction: if $\gcd(A)>1$ (and $1\notin A$), then density $1$ is impossible.

- Lemma 691.3 is consistent with the special case quoted in the problem statement (pairwise coprime $A$): it recovers “divergent reciprocal sum implies density $1$” without needing any further structure.

- All density computations used only periodicity/CRT for finite sets.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. If $\gcd(A)>1$ and $1\notin A$ then $\mathbf{d}(M_A)\le 1/\gcd(A)<1$ (Lemma 691.1). If $A$ contains a pairwise coprime subfamily $B$ with $\sum_{b\in B}1/b=\infty$, then $\mathbf{d}(M_A)=1$ (Lemma 691.3). Also $M_A$ depends only on the “minimal-by-divisibility” core $A^{\min}$ (Lemma 691.2).

(ii) First gap (crisp). Give a necessary and sufficient condition on an arbitrary $A\subseteq\mathbb{N}$ (with no coprimality assumptions) for $\mathbf{d}(M_A)=1$.

(iii) Top 3 next moves. 1. Prove (or refute) that one may always reduce to a primitive set (no element divides another) and then characterize Behrend-ness by a single divergent series/condition on that primitive set. 2. Develop a sieve/inclusion--exclusion criterion for $\mathbf{d}(\mathbb{N}\setminus M_A)=0$ in terms of finite truncations $A\cap[1,y]$, aiming for a checkable “$\lim_{y\to\infty}$” condition. 3. For structured families (e.g. block sequences), compute the density of the complement by an explicit upper bound on numbers avoiding all blocks, and identify sharp thresholds.

(iv) Minimal counterexample structure. A minimal obstruction to any simple “$\sum 1/a$ diverges” criterion would likely be a set $A$ with heavy overlaps (many shared prime factors) so that $\sum_{a\in A}1/a$ diverges but $\mathbb{N}\setminus M_A$ still has positive density; the block-sequence constructions mentioned in the statement are candidate models for such behavior.