Sumsets Containing Composites

A Composite Number in a Sumset

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

The ambient sets consist of positive integers. A composite number is an integer greater than one that is not prime. The question is asymptotic in $N$: must two sets of the indicated size have $a+b$ composite for some $a\in A,b\in B$? Integer-valued cardinalities at the threshold $N^{0.49}$ require rounding; the standard threshold reading is $|A|,|B|\geq\lceil N^{0.49}\rceil$. [S1] [S2]

Statement recorded in the supplied source.

Suppose $A, B \subset \{1, \dots, N\}$ both have size $N^{0.49}$. Does $A + B$ contain a composite number? [S1]

Scope and interpretation.

The real-valued cardinality in the supplied statement is shorthand for an asymptotic size threshold. Its rounding convention is made explicit rather than treated as a literal integer equality. [S1]

Short English statement

Can two moderately large sets of integers have all their cross-sums prime, or must at least one cross-sum be composite?

Research attempt

Provenance and scope.

This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.

Formal target and context.

Assume $A,B\subset[N]$ have at least $N^{0.49}$ elements, up to harmless integer rounding. We want a composite in $A+B$. Every cross-sum is at least two. The maintained problem list places this question in the inverse-sieve setting; we do not assume an inverse theorem capable of resolving it. The present attack derives all local residue exclusions exactly, controls the exceptional possibility that a divisible sum is itself the small prime, and measures the strength of a direct Chinese-remainder argument.

Parity is already rigid.

Suppose all cross-sums are prime and both sets have at least two elements. If $A$ contains both an even and an odd integer, then for any $b\in B$ exactly one of those two sums is even. A prime even sum must be two. This forces $b=1$ and the matching element of $A$ also to be one; the condition cannot hold for two distinct $b$. Thus $A$ has a single parity, and by symmetry so does $B$. Their parities must be opposite: if they agree, every cross-sum is even and all must equal two, which is impossible for sets of size at least two. Hence the prime-only scenario already forces opposite parity classes.

Removing the small-prime exception before sieving.

Choose an integer $z<N^{0.49}/2$ and put $A'=A\cap(z,N]$, $B'=B\cap(z,N]$. At most $z$ elements are discarded from each set. Every sum in $A'+B'$ exceeds $2z$. Therefore for any prime $q\leq z$, a congruence $a+b\equiv0\pmod q$ would make the sum a multiple of $q$ strictly greater than $q$, hence composite. Under the prime-only assumption it cannot occur.

Let $R_q$ and $S_q$ be the supports of $A'$ and $B'$ modulo $q$, of sizes $r_q,s_q$. Then $R_q\cap(-S_q)=\varnothing$, giving \[ r_q+s_q\leq q,\qquad r_qs_q\leq q^2/4. \] These inequalities do not require equidistribution within the occupied residue classes. They merely constrain which classes occur. The trimming step matters: without it, one cannot exclude a residue collision that represents the prime $q$ itself.

The direct Chinese-remainder bound.

Take distinct primes $q_1,\ldots,q_k\leq z$ and set $Q=\prod q_i$. The Chinese remainder theorem identifies residues modulo $Q$ with tuples of residues modulo the $q_i$. Thus $A'$ occupies at most $\prod r_{q_i}$ classes modulo $Q$, and $B'$ at most $\prod s_{q_i}$. Each class contains at most $N/Q+1$ integers in $[N]$. Multiplying the resulting estimates proves \[ |A'||B'|\leq(N/Q+1)^2\prod_i r_{q_i}s_{q_i} \leq\frac{(N+Q)^2}{4^k}. \] This is a completely rigorous finite upper bound from the local exclusions. It applies to every chosen prime set and gives a useful exact test of any proposed sieve optimisation.

Why this bound does not reach the required exponent.

Restricting to $Q\leq N$ makes the numerator at most $4N^2$. To contradict two sets of size about $N^{0.49}$ through this formula alone would require $4^k$ to exceed order $N^{1.02}$, hence $k$ of order $\log N$. But the product of $k$ distinct primes is at least $(k+1)!$, simply because the $i$th distinct prime is at least $i+1$. Therefore $Q\leq N$ implies $k\log k=O(\log N)$, and in particular $k=O(\log N/\log\log N)$. The resulting saving $4^k$ is only $N^{o(1)}$. Allowing $Q$ far above $N$ makes the $(N+Q)^2$ term costly and is not justified as an improvement. Thus the direct residue-support multiplication does not come close to the needed square-root barrier.

This calculation also exposes a logical trap: having $r_q+s_q\leq q$ for every small prime does not mean one fixed set occupies at most half the residues for every prime. The smaller support may alternate between $A'$ and $B'$. Any inverse argument must preserve that joint dependence.

Verification and remaining gap.

All divisibility deductions concern positive integers greater than the relevant prime, so neither one nor the prime itself is mistakenly called composite. The cardinality loss from trimming is explicitly smaller than half the target size. The CRT estimate is valid without probabilistic assumptions. The attempt yields exact necessary parity and residue conditions and a quantitative demonstration of the failure of the naive sieve. It leaves unresolved the structural inverse-sieve statement needed to rule out two sets of the specified size satisfying all those joint local restrictions.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 119 (GREEN-031), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 B. Green, 100 Open Problems, Problem 58, version. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf. The author-hosted document was inspected on 27 September 2026; the archive’s local code is not a problem-number locator in this paper.