Erdős problem #432 — wave 9i
Date: 2026-07-28 UTC
This report does not close the asymptotic problem. It gives (i) an elementary reduction and extension lemma, and (ii) a new, independently recomputed exact table for the finite two-row coprime-grid regime through \(x=100\).
Claim labels
- [a] elementary-rigorous: proved below from elementary facts.
- [b] rigorous-modulo-named-theorem: a published theorem is used exactly
as named.
- [c] plausible/structural-unverified: a source makes the claim, but this
report does not certify its complete proof.
- [d] computational-only: established by the exhaustive computation in
runs/erdos432_wave9i_reverify.py, not promoted to a general theorem.
Step 0: authoritative live-page check
I loaded both the problem page and its discussion thread through the Bright Data browser on 2026-07-28:
- <https://www.erdosproblems.com/432>
- <https://www.erdosproblems.com/forum/discuss/432>
- <https://www.erdosproblems.com/latex/432>
The exact current statement, copied verbatim from the page's LaTeX view, is:
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?
The page status was OPEN. It displayed:
0 claimed proofs for this problem;Currently working on this problem None;Interested in collaborating None;- one comment;
This problem looks difficult TerenceTao;- no formalised statement.
Thus neither mandatory stop condition (claimed proof/solved/falsified, or a current worker) was present.
The one comment, by Sungchul Lee at 14:36 on 23 June 2026, links <https://github.com/lsngchl/Erdos432> and describes a manuscript containing the following four claimed partial results:
- \(S_{A,B}(x)\leq\pi(x)\);
- one infinite example with
\(S_{A,B}(x)\gg(\log x/\log\log x)^2\) for every sufficiently large \(x\);
- for every \(F(x)=x^{o(1)}\), an example and \(x_j\to\infty\) with
\(S_{A,B}(x_j)\geq F(x_j)\);
- conditionally on Hardy--Littlewood prime tuples, examples with all sums
prime and \(S_{A,B}(x_j)\geq x_j/(\log x_j)^{\omega(x_j)}\) for arbitrary \(\omega(x)\to\infty\).
The discussion page itself says that comments are the user's responsibility and are not verified. I therefore classify items 2--4 as [c] here. Item 1 is independently proved below as [a].
Primary-source and literature audit
Sources actually inspected
- Original source. Erdős and Graham, *Old and New Problems and Results
in Combinatorial Number Theory* (1980), printed p. 85: <https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf>. The scan really does contain Straus's modification asking how dense \(A+B\) can be under pairwise relative primality. This verifies the attribution and wording independently of the tracker.
- Finite prime-valued sumsets. Pomerance, Sárközy and Stewart,
“On Divisors of Sums of Integers, III,” Pacific J. Math. 133 (1988), 363--379, DOI <https://doi.org/10.2140/pjm.1988.133.363>, author-hosted PDF <https://math.dartmouth.edu/~carlp/PDF/paper68.pdf>. Section 6, Theorem 6 and its following remarks prove [b] that for all sufficiently large \(N\) there are finite \(A,B\subseteq[1,N]\), with both component sizes exceeding \((1-\varepsilon)\log N/\log\log N\), for which every member of \(A+B\) is prime. This is a finite result and does not supply one nested pair of infinite sets. The theorem also does not assert that every ordered pair gives a different sum.
- Partial infinite prime sumsets. Tao and Ziegler, “Infinite Partial
Sumsets in the Primes,” arXiv:2301.10303v4 and J. d'Analyse Math. 151 (2023), 375--389: <https://arxiv.org/abs/2301.10303>. Their abstract/theorem states [b] that there are infinite sequences \(A=\{a_i\}\), \(B=\{b_j\}\) with \(a_i+b_j\) prime whenever \(i<j\). The unrestrained half \(i\geq j\) is absent, so this is not a solution of #432.
- The 2026 sieve citation really exists. Banks and Ford, “Sets of
Integers Satisfying Bateman--Horn Statistics,” arXiv:2605.01155: <https://arxiv.org/abs/2605.01155>. Lemma 2.2 is indeed a fundamental sieve estimate of the form cited in Lee's manuscript, with error \(O_K(e^{-u\log u/2})\). This spot-check validates that particular reference; it is not a certification of the whole manuscript.
- The direct 2026 manuscript. I inspected all 1,555 lines of the
repository's 2026-06-23_Erdos432.tex at commit 37d60fd8142f933f3a5679b072f78696b7d4e013. It contains proofs of the four results summarized in the live-page comment. It is a public, unrefereed manuscript and the live page labels the comment unverified, so I do not silently upgrade its asymptotic conclusions to ground truth.
Exact-phrase searches for the original Straus wording, “pairwise coprime sumsets,” and variants with Ostmann found the 1980 source, the live problem page, and the June 2026 manuscript, but no additional paper directly settling #432. The miss is reported as a search miss, not as proof that no such literature exists.
Retrieved-source fingerprints
These hashes identify the exact files inspected:
0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3 Erdős--Graham 1980 scan
27ddb2c37d7ae1873460f8d682160fa1d859444fe11f3dc1604af18efa28cead Pomerance--Sárközy--Stewart 1988 PDF
f1385cd5c051e8bb6eecbce19242b67ed074f4fa928643c71484f62e7909fe99 Tao--Ziegler arXiv:2301.10303v4 PDF
76385287db4d999c5143f4757d5e38d9478bda727c6ebebe7502b62ce31b0c1e Banks--Ford arXiv:2605.01155 PDF
a9fd456e16bd1d82f31793812f003bb8c1d489db448c6da441e0f9fee2779f04 Lee manuscript TeX
Elementary facts used here
Write
Universal upper bound
[a] Proposition. If the distinct members of \(A+B\) are pairwise coprime, then
Proof. Every sum is at least \(2\). Choose one prime divisor \(p_s\) of each \(s\in(A+B)\cap[1,x]\). Pairwise coprimality makes the chosen primes distinct, and \(p_s\leq s\leq x\). Thus \(s\mapsto p_s\) injects the sums into the primes at most \(x\). \(\square\)
Finite coprime grids extend to infinite ones
Call finite \(G,H\subset\mathbb N\) a coprime grid when all ordered sums
are distinct and pairwise coprime.
[a] Extension lemma. Every finite coprime grid with \(|G|,|H|\geq2\) is contained in an infinite coprime grid \((A,B)\).
Proof.
First, \(H\) omits a residue class modulo every prime \(p\). Otherwise, choose distinct \(g_1,g_2\in G\) and \(h_i\in H\) with \(g_i+h_i\equiv0\pmod p\). Two different grid positions would then give two sums with common divisor \(p\), contrary to the definition. The same argument applies to \(G\).
To append a row, let \(\mathcal P\) be the finite set of primes dividing an old sum \(g+h\), or a nonzero difference \(h-h'\). For each \(p\in\mathcal P\), choose a residue \(r_p\) outside \(\{-h:h\in H\}\pmod p\); this is possible by the preceding paragraph. The Chinese remainder theorem gives arbitrarily large \(u\) satisfying \(u\equiv r_p\pmod p\) for every \(p\in\mathcal P\).
If two new-row entries \(u+h,u+h'\) had a common prime divisor \(q\), then \(q\mid h-h'\), hence \(q\in\mathcal P\), contradicting the choice of \(u\bmod q\). If \(u+h\) and an old entry \(g+h'\) had a common prime divisor \(q\), then \(q\) divides an old sum and the same contradiction results. Thus \(u\) is a compatible new row. Interchanging \(G,H\) gives arbitrarily large compatible columns. Alternating these two extensions makes both coordinate sets infinite. \(\square\)
Choosing the least omitted residue at each prime and then the least CRT solution above the preceding coordinates makes this proof a deterministic recursive construction, not merely a compactness argument.
Exact two-row regime
Define \(T_2(x)\) to be the largest \(n\) for which a finite coprime grid exists with two rows, \(n\) columns, and every sum at most \(x\). Equivalently, it is the largest \(n\) for which there are \(d>0\) and \(V\subseteq[2,x-d]\), \(|V|=n\), such that the \(2n\) integers
are distinct and pairwise coprime.
The equivalence is [a]: for rows \(\{a_0,a_1\}\), take \(d=a_1-a_0\) and \(V=a_0+B\); conversely take
This is a deliberately stronger, injective subclass of the original problem. It is still relevant because the extension lemma embeds every finite witness into actual infinite \(A,B\).
Elementary upper bound in this regime
[a] Lemma. If \(n\geq2\), then
Proof. If \(d\) were odd, every pair \(v,v+d\) would contain an even integer. Two columns would therefore supply two distinct even sums, which cannot be coprime. Hence \(d\) is even. Then an even \(v\) would make both \(v\) and \(v+d\) even, so all \(2n\) entries are odd. Choosing one prime divisor of each entry injects the entries into the odd primes at most \(x\). \(\square\)
Sharp table
Let
[a] The trivial transition is \(L_1=3\). It is omitted below because a one-column core cannot yet invoke the finite-to-infinite extension lemma. The exact nontrivial results are:
| \(n\) | \(L_n\) | gap \(d\) | witness \(V\) | status of optimality | |---:|---:|---:|---|---| | 2 | 11 | 2 | \(5,9\) | [a] | | 3 | 17 | 4 | \(5,7,13\) | [a] | | 4 | 23 | 4 | \(5,7,13,19\) | [a] | | 5 | 31 | 2 | \(7,11,17,23,29\) | [a] | | 6 | 41 | 4 | \(7,13,19,25,27,37\) | [a] | | 7 | 47 | 4 | \(7,13,19,25,27,37,43\) | [a] | | 8 | 67 | 6 | \(11,19,23,31,41,43,53,61\) | [d] | | 9 | 79 | 6 | \(11,23,31,41,43,53,61,65,73\) | [d] | | 10 | 83 | 12 | \(11,13,17,31,37,41,47,61,67,71\) | [d] |
In addition,
so \(L_{11}>100\). This last assertion is [d].
For \(2\leq n\leq7\), the elementary odd-prime bound makes each row optimal: \(L_n\) is the first \(x\) with \(\pi(x)-1\geq2n\), and the listed witness attains it. Thus those six rows do not depend on trusting the search for their upper bound.
The strongest displayed core is
whose 20 sums are
Their pairwise gcds are all \(1\), as recomputed by the checker. By the extension lemma, [a] there are infinite \(A\supseteq A_0\) and \(B\supseteq B_0\) forming a coprime grid, hence an actual #432 example with \(S_{A,B}(83)\geq20\). Each row of the table similarly embeds into an infinite example. These infinite examples may differ with \(n\); this statement does not claim a single pair attaining every row.
Exact computation and independent verification
Complete standalone code:
runs/erdos432_wave9i_reverify.py
It uses no third-party packages or precomputed tables.
Solver 1: gcd graph / maximum clique
For fixed \(x,d\), a vertex is a starting value \(v\) for which \(\gcd(v,v+d)=1\). Two vertices \(v,w\) are adjacent exactly when
are distinct and pairwise coprime. The desired \(V\) is therefore exactly a clique. The program exhausts every \(1\leq d\leq x-2\) and uses an include/exclude maximum-clique recursion. Its greedy coloring is used only as a certified upper bound for pruning: a clique contains at most one vertex of each color.
Solver 2: prime-support set packing
Independently, the program factors every integer by trial division and encodes its distinct prime support as a bit mask. An admissible pair \((v,v+d)\) becomes the union of two disjoint nonempty masks. Several pairs are mutually compatible exactly when these union masks are disjoint. A separate include/exclude set-packing recursion decides the maximum. This solver does not call the gcd graph or maximum-clique code.
For every threshold \(L_n\), both solvers recompute \(T_2(L_n-1)=n-1\) and \(T_2(L_n)=n\). They also independently obtain \(T_2(100)=10\). Every displayed witness is then checked again by direct pairwise gcds and by reconstructing \(A_0+B_0\).
Reproduction command:
python runs/erdos432_wave9i_reverify.py
Observed output:
Exact transition table for T_2(x)
n least_x gap_d starts_V sorted_sums
2 11 2 [5, 9] [5, 7, 9, 11]
3 17 4 [5, 7, 13] [5, 7, 9, 11, 13, 17]
4 23 4 [5, 7, 13, 19] [5, 7, 9, 11, 13, 17, 19, 23]
5 31 2 [7, 11, 17, 23, 29] [7, 9, 11, 13, 17, 19, 23, 25, 29, 31]
6 41 4 [7, 13, 19, 25, 27, 37] [7, 11, 13, 17, 19, 23, 25, 27, 29, 31, 37, 41]
7 47 4 [7, 13, 19, 25, 27, 37, 43] [7, 11, 13, 17, 19, 23, 25, 27, 29, 31, 37, 41, 43, 47]
8 67 6 [11, 19, 23, 31, 41, 43, 53, 61] [11, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67]
9 79 6 [11, 23, 31, 41, 43, 53, 61, 65, 73] [11, 17, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 65, 67, 71, 73, 79]
10 83 12 [11, 13, 17, 31, 37, 41, 47, 61, 67, 71] [11, 13, 17, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83]
T_2(100) = 10; no 2-by-11 coprime grid exists by x=100.
Independent gcd/clique and prime-support/packing computations agree.
sha256=af55c6b587b878c4dcf4febc262ef7bdfbe8c2f76056f209787f0a8869440a29
elapsed_seconds=0.728536
ALL CHECKS PASSED
The elapsed time is machine-dependent; the source hash identifies the run.
What this resolves, and what it does not
- [a+d] The two-row finite coprime-grid problem is exactly reduced to
a finite graph/set-packing problem, and its transition table is settled through \(x=100\).
- [a] Every lower-bound witness is genuinely relevant to the infinite
question because it extends to an infinite coprime grid by CRT.
- The result is not an asymptotic improvement. It concerns the stronger
injective-grid subclass, and optimizing each finite scale separately does not produce one pair with controlled growth at all scales.
- The exact missing asymptotic ingredient is a *quantitative nested
extension lemma*: one must add enough compatible rows and columns while keeping their locations controlled. A CRT extension proves existence but its modulus depends on all old sums and coordinate differences and gives no competitive density. Conversely, the elementary upper bound \(S_{A,B}(x)\leq\pi(x)\) uses none of the additive rectangle relations in \(A+B\); a serious upper-bound advance must exploit those relations.
- The live page therefore remains correctly described as open. The June
2026 manuscript advertises substantial asymptotic lower bounds, but even taking those claims at face value leaves a large gap to the universal upper bound and does not answer “how dense” sharply.
PARTIAL: proved an elementary finite-to-infinite extension and exact two-row thresholds \((L_2,\ldots,L_{10})=(11,17,23,31,41,47,67,79,83)\), with independent exhaustive verification that \(T_2(100)=10\); the asymptotic density problem remains open.