Erdős Problem #432

Erdős Problem 432 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Let $A,B\subseteq \mathbb{N}$ be two infinite sets. How dense can $A+B$ be if all elements of $A+B$ are pairwise relatively prime? Asked by Straus, inspired by a problem of Ostmann (see [431] ).

FORMAL RESTATEMENT

Let $\mathbb N:=\{1,2,3,\dots\}$. Let $A,B\subseteq\mathbb N$ be infinite, and define $S:=A+B=\{a+b:a\in A,\ b\in B\}$. Assume: \[ \forall s\ne t\in S:\ \gcd(s,t)=1. \] Question: how large can $|S\cap[1,x]|$ be as $x\to\infty$ (e.g. what is the maximal possible upper asymptotic density $\overline d(S):=\limsup_{x\to\infty}|S\cap[1,x]|/x$)?

Stress points: (i) $S$ pairwise coprime implies at most one multiple of each prime; (ii) $S$ is a sumset, so $S$ is constrained by additive structure.

QUICK LITERATURE/CONTEXT CHECK

No external results beyond the statement are used here. The problem is motivated by [431].

ATTACK PLAN

Proof track (upper bounds): 1) Use the "one prime per element" principle: in a pairwise coprime set, distinct elements have distinct least prime factors, giving $|S\cap[1,x]|\le \pi(x)+1$. 2) Use parity and small primes to constrain $A,B$ (sumset-specific obstruction).

Construction track (lower bounds): 1) Search for finite examples where $A+B$ is large and pairwise coprime; look for patterns to extend to infinite constructions.

I carry out $1$ and $2$ as rigorous partial bounds and do a small brute force search for (finite) examples.

WORK

FAST REALITY CHECK (finite search). For each $M\le 10$ I brute-forced all nonempty $A,B\subseteq\{1,\dots,M\}$ with $|A|,|B|\ge 2$ and computed $S=A+B$ (with sums up to $2M$). I then required that all elements of $S$ are pairwise coprime, and maximized $|S|$. One best example at $M=10$ is \[A=\{1,3,9\},\quad B=\{4,8,10\},\quad S=\{5,7,9,11,13,17,19\},\] which indeed is pairwise coprime. The maxima found were:

M 6 best|S| 4 |A| 2 |B| 2
M 7 best|S| 5 |A| 2 |B| 3
M 8 best|S| 5 |A| 2 |B| 3
M 9 best|S| 6 |A| 2 |B| 3
M 10 best|S| 7 |A| 3 |B| 3

This suggests nontrivial finite constructions exist, but does not address asymptotic density.

Lemma 432.1 (at most one multiple of each prime). Let $S\subseteq\mathbb N$ be pairwise coprime: $\gcd(s,t)=1$ for all distinct $s,t\in S$. Then for every prime $p$, there is at most one element of $S$ divisible by $p$.

Proof. If there were two distinct $s,t\in S$ with $p\mid s$ and $p\mid t$, then $p\mid\gcd(s,t)$, so $\gcd(s,t)\ge p\ge 2$, contradicting pairwise coprimality. $\Box$

Lemma 432.2 (prime-factor injection bound for $A+B$). Let $A,B\subseteq\mathbb N$ be infinite and let $S:=A+B$. Assume $S$ is pairwise coprime. Then for every $x\ge 1$, \[ |S\cap[1,x]|\le \pi(x)+1, \] where $\pi(x)$ is the number of primes $\le x$.

Proof. Let $T:=S\cap[1,x]$. If $1\notin T$, set aside nothing; if $1\in T$, set it aside as a special case because it has no prime divisor. For each $t\in T\setminus\{1\}$, let $p(t)$ be the smallest prime divisor of $t$.

Claim: the map $t\mapsto p(t)$ is injective on $T\setminus\{1\}$. Indeed, if $t_1\ne t_2$ in $T\setminus\{1\}$ had $p(t_1)=p(t_2)=p$, then $p\mid t_1$ and $p\mid t_2$, implying $\gcd(t_1,t_2)\ge p\ge 2$, contradicting that $T\subseteq S$ is pairwise coprime.

Therefore $|T\setminus\{1\}|\le$ (number of primes that occur as $p(t)$). Since $p(t)\le t\le x$, we have $p(t)\le x$, so there are at most $\pi(x)$ possibilities. Hence $|T\setminus\{1\}|\le \pi(x)$, and adding the possible element $1$ gives $|T|\le \pi(x)+1$. $\Box$

Corollary 432.3 (parity constraint for $A,B$). Under the hypotheses of Lemma 432.2, $S=A+B$ contains at most one even number (by Lemma 432.1 with $p=2$). In particular, all but at most one element of $S$ is odd. Consequently, $A$ and $B$ cannot both contain infinitely many even integers, and cannot both contain infinitely many odd integers.

Proof. The first statement is immediate from Lemma 432.1 with $p=2$. If $A$ and $B$ each contained infinitely many even integers, then $A+B$ would contain infinitely many even sums, contradicting "at most one even element". The odd case is the same. $\Box$

VERIFICATION

- Lemma 432.1 is immediate and cannot fail. - In Lemma 432.2, the only subtlety is handling $1$, which is addressed explicitly. - Corollary 432.3 only uses that if two infinite sets share a parity infinitely often, then their sumset contains infinitely many even numbers; this is correct.

FINAL

UNRESOLVED

(i) Strongest proved partial result: For any infinite $A,B\subseteq\mathbb N$ with $S=A+B$ pairwise coprime, one has the universal counting bound $|S\cap[1,x]|\le \pi(x)+1$ for every $x$ (Lemma 432.2). Also, $S$ contains at most one multiple of any fixed prime (Lemma 432.1), implying strong parity restrictions (Corollary 432.3).

(ii) First gap (crisp): Determine the correct asymptotic order of growth of \[\sup\{|(A+B)\cap[1,x]|: A,B\subseteq\mathbb N\text{ infinite and }A+B\text{ pairwise coprime}\}\] as $x\to\infty$ (or even whether one can achieve $|(A+B)\cap[1,x]|\gg \pi(x)$ infinitely often).

(iii) Top 3 next moves: 1. Construction attempt: build explicit infinite $A,B$ such that $A+B$ consists mostly of primes (or prime powers with distinct primes), while controlling cross-sums to avoid shared prime factors. 2. Upper bound: exploit the sumset structure to improve the generic bound $\pi(x)+1$, e.g. show $|(A+B)\cap[1,x]|$ is $o(\pi(x))$ or even $O(x^\theta)$ for some $\theta<1$. 3. Computation: for larger $M$, optimize $|A+B|$ under the pairwise-coprime constraint and inspect structural patterns (e.g. does $A$ tend to be very small or very structured?).

(iv) What a minimal counterexample would likely look like: an extremal pair $(A,B)$ would have nearly all sums odd, and $A+B$ would have to allocate distinct prime factors to distinct sums in a near-injective way, suggesting that most elements of $A+B$ should be prime (or have a unique large prime factor) and that $A,B$ themselves must be very sparse to prevent producing two sums sharing a small prime.

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.

Let $A,B\subseteq \mathbb{N}$ be two infinite sets. How dense can $A+B$ be if all elements of $A+B$ are pairwise relatively prime? Asked by Straus, inspired by a problem of Ostmann (see [431] ).

FORMAL RESTATEMENT

Let $\mathbb N:=\{1,2,3,\dots\}$. Let $A,B\subseteq\mathbb N$ be infinite, and define $S:=A+B=\{a+b:a\in A,\ b\in B\}$. Assume: \[ \forall s\ne t\in S:\ \gcd(s,t)=1. \] Question: how large can $|S\cap[1,x]|$ be as $x\to\infty$ (e.g. what is the maximal possible upper asymptotic density $\overline d(S):=\limsup_{x\to\infty}|S\cap[1,x]|/x$)?

Stress points: (i) $S$ pairwise coprime implies at most one multiple of each prime; (ii) $S$ is a sumset, so $S$ is constrained by additive structure.

QUICK LITERATURE/CONTEXT CHECK

No external results beyond the statement are used here. The problem is motivated by [431].

ATTACK PLAN

Proof track (upper bounds): 1) Use the "one prime per element" principle: in a pairwise coprime set, distinct elements have distinct least prime factors, giving $|S\cap[1,x]|\le \pi(x)+1$. 2) Use parity and small primes to constrain $A,B$ (sumset-specific obstruction).

Construction track (lower bounds): 1) Search for finite examples where $A+B$ is large and pairwise coprime; look for patterns to extend to infinite constructions.

I carry out $1$ and $2$ as rigorous partial bounds and do a small brute force search for (finite) examples.

WORK

FAST REALITY CHECK (finite search). For each $M\le 10$ I brute-forced all nonempty $A,B\subseteq\{1,\dots,M\}$ with $|A|,|B|\ge 2$ and computed $S=A+B$ (with sums up to $2M$). I then required that all elements of $S$ are pairwise coprime, and maximized $|S|$. One best example at $M=10$ is \[A=\{1,3,9\},\quad B=\{4,8,10\},\quad S=\{5,7,9,11,13,17,19\},\] which indeed is pairwise coprime. The maxima found were:

M 6 best|S| 4 |A| 2 |B| 2
M 7 best|S| 5 |A| 2 |B| 3
M 8 best|S| 5 |A| 2 |B| 3
M 9 best|S| 6 |A| 2 |B| 3
M 10 best|S| 7 |A| 3 |B| 3

This suggests nontrivial finite constructions exist, but does not address asymptotic density.

Lemma 432.1 (at most one multiple of each prime). Let $S\subseteq\mathbb N$ be pairwise coprime: $\gcd(s,t)=1$ for all distinct $s,t\in S$. Then for every prime $p$, there is at most one element of $S$ divisible by $p$.

Proof. If there were two distinct $s,t\in S$ with $p\mid s$ and $p\mid t$, then $p\mid\gcd(s,t)$, so $\gcd(s,t)\ge p\ge 2$, contradicting pairwise coprimality. $\Box$

Lemma 432.2 (prime-factor injection bound for $A+B$). Let $A,B\subseteq\mathbb N$ be infinite and let $S:=A+B$. Assume $S$ is pairwise coprime. Then for every $x\ge 1$, \[ |S\cap[1,x]|\le \pi(x)+1, \] where $\pi(x)$ is the number of primes $\le x$.

Proof. Let $T:=S\cap[1,x]$. If $1\notin T$, set aside nothing; if $1\in T$, set it aside as a special case because it has no prime divisor. For each $t\in T\setminus\{1\}$, let $p(t)$ be the smallest prime divisor of $t$.

Claim: the map $t\mapsto p(t)$ is injective on $T\setminus\{1\}$. Indeed, if $t_1\ne t_2$ in $T\setminus\{1\}$ had $p(t_1)=p(t_2)=p$, then $p\mid t_1$ and $p\mid t_2$, implying $\gcd(t_1,t_2)\ge p\ge 2$, contradicting that $T\subseteq S$ is pairwise coprime.

Therefore $|T\setminus\{1\}|\le$ (number of primes that occur as $p(t)$). Since $p(t)\le t\le x$, we have $p(t)\le x$, so there are at most $\pi(x)$ possibilities. Hence $|T\setminus\{1\}|\le \pi(x)$, and adding the possible element $1$ gives $|T|\le \pi(x)+1$. $\Box$

Corollary 432.3 (parity constraint for $A,B$). Under the hypotheses of Lemma 432.2, $S=A+B$ contains at most one even number (by Lemma 432.1 with $p=2$). In particular, all but at most one element of $S$ is odd. Consequently, $A$ and $B$ cannot both contain infinitely many even integers, and cannot both contain infinitely many odd integers.

Proof. The first statement is immediate from Lemma 432.1 with $p=2$. If $A$ and $B$ each contained infinitely many even integers, then $A+B$ would contain infinitely many even sums, contradicting "at most one even element". The odd case is the same. $\Box$

VERIFICATION

- Lemma 432.1 is immediate and cannot fail. - In Lemma 432.2, the only subtlety is handling $1$, which is addressed explicitly. - Corollary 432.3 only uses that if two infinite sets share a parity infinitely often, then their sumset contains infinitely many even numbers; this is correct.

FINAL

UNRESOLVED

(i) Strongest proved partial result: For any infinite $A,B\subseteq\mathbb N$ with $S=A+B$ pairwise coprime, one has the universal counting bound $|S\cap[1,x]|\le \pi(x)+1$ for every $x$ (Lemma 432.2). Also, $S$ contains at most one multiple of any fixed prime (Lemma 432.1), implying strong parity restrictions (Corollary 432.3).

(ii) First gap (crisp): Determine the correct asymptotic order of growth of \[\sup\{|(A+B)\cap[1,x]|: A,B\subseteq\mathbb N\text{ infinite and }A+B\text{ pairwise coprime}\}\] as $x\to\infty$ (or even whether one can achieve $|(A+B)\cap[1,x]|\gg \pi(x)$ infinitely often).

(iii) Top 3 next moves: 1. Construction attempt: build explicit infinite $A,B$ such that $A+B$ consists mostly of primes (or prime powers with distinct primes), while controlling cross-sums to avoid shared prime factors. 2. Upper bound: exploit the sumset structure to improve the generic bound $\pi(x)+1$, e.g. show $|(A+B)\cap[1,x]|$ is $o(\pi(x))$ or even $O(x^\theta)$ for some $\theta<1$. 3. Computation: for larger $M$, optimize $|A+B|$ under the pairwise-coprime constraint and inspect structural patterns (e.g. does $A$ tend to be very small or very structured?).

(iv) What a minimal counterexample would likely look like: an extremal pair $(A,B)$ would have nearly all sums odd, and $A+B$ would have to allocate distinct prime factors to distinct sums in a near-injective way, suggesting that most elements of $A+B$ should be prime (or have a unique large prime factor) and that $A,B$ themselves must be very sparse to prevent producing two sums sharing a small prime.