Erdős Problem #12

Erdős Problem #12 --- Round 4 (Continuation & Gap-Closure Mode)

1) ROUND-4 OBJECTIVE

Path (C): obstruction/correction via reduction to the primitive case.

Round 3 pushed one important primitive construction paradigm (the square-based one) to its natural asymptotic limit. The next unresolved issue is whether nonprimitive behaviour could fundamentally change the problem: perhaps by adjoining carefully chosen larger multiples of existing elements one could obtain denser sets or a divergent reciprocal sum, even if the primitive core remains sparse.

The most promising Round-4 direction is therefore to determine whether the original questions are genuinely more general than their primitive analogues.

I will prove that they are not. More precisely, every infinite set $A$ satisfying $(*)$ has an infinite primitive kernel $K\subseteq A$ satisfying $(*)$ such that: \[ |A\cap[1,N]|\le |K\cap[1,N]|+|K\cap[1,N/2]|\le 2|K\cap[1,N]| \] for every $N$, and \[ \sum_{a\in A}\frac1a\le \frac32\sum_{k\in K}\frac1k, \qquad \sum_{a\in A}\frac1{a\log a}\le \frac32\sum_{k\in K}\frac1{k\log k}. \] Consequently:

• Q1 is exactly equivalent to its restriction to primitive sets;
• Q3 is exactly equivalent to its restriction to primitive sets;
• Q2 is equivalent at the yes/no level to its restriction to primitive sets (the exponent may shrink by an arbitrarily small amount when passing back to general sets).

Thus any eventual counterexample to Q1 or Q3, and any eventual proof of Q1--Q3, may be sought entirely inside the primitive case.

This is a genuine obstruction to further progress by "decorating" existing primitive constructions with larger multiples: such decorations change counting functions by at most a factor $2$ and reciprocal sums by at most a factor $3/2$.

2) ROUND-3 FOUNDATION USED

I rely on the following previously established result.

• Round-2 Corollary 12.1b (part of the vetted earlier foundation). If $A$ satisfies $(*)$ and $a\in A$, then there is at most one element $b\in A$ with $b>a$ and $a\mid b$. In particular, an infinite such $A$ contains neither $1$ nor $2$.

No other earlier lemma is needed in the new proofs below.

3) NEW INSIGHT / TOOL (ROUND-4)

The new tool is the primitive-kernel decomposition.

Given $A$, define its divisibility-minimal kernel \[ K:=\{a\in A:\text{there is no }d\in A\text{ with }d<a\text{ and }d\mid a\}. \] The key observation is that every nonminimal element of $A$ can be assigned to one of its minimal divisors in $K$, and this assignment is automatically injective because Round-2 Corollary 12.1b forbids two distinct larger multiples of the same kernel element.

This converts the whole set $A$ into "one kernel element plus at most one satellite" at each kernel point. That yields the sharp transfer inequalities stated above.

4) ATTACK PLAN (ROUND-4)

Gap left after Round 3. Round 3 analysed a large primitive construction class, but it did not rule out the possibility that the nonprimitive part of a general solution could carry the real difficulty.

Claims to prove now.

1. Construct a canonical primitive subset $K\subseteq A$.
2. Prove that nonkernel elements inject into $K$.
3. Deduce the pointwise counting bound \[ |A\cap[1,N]|\le |K\cap[1,N]|+|K\cap[1,N/2]|. \]
4. Deduce the reciprocal inequalities \[ \sum_{a\in A}\frac1a\le \frac32\sum_{k\in K}\frac1k, \qquad \sum_{a\in A}\frac1{a\log a}\le \frac32\sum_{k\in K}\frac1{k\log k}. \]
5. Use these to reduce Q1--Q3 to primitive sets.
6. As an unconditional bonus, use a theorem on primitive sets to prove \[ \sum_{a\in A}\frac1{a\log a}<2.4 \] for every infinite $A$ satisfying $(*)$.

Why this overcomes the earlier obstacle. It shows that the nonprimitive part of $A$ is never more than a constant-factor perturbation of a primitive set. So the genuinely hard core of the Erdős--Sárközy problem is already present in the primitive case.

5) WORK (ROUND-4)

Notation.

For real $x\ge 1$ write \[ A(x):=|A\cap[1,x]|. \] Given an infinite $A\subseteq\mathbb N$ satisfying $(*)$, define its primitive kernel \[ K:=\{a\in A:\text{there is no }d\in A\text{ with }d<a\text{ and }d\mid a\}. \] Write similarly \[ K(x):=|K\cap[1,x]|. \] Since property $(*)$ is hereditary under passing to subsets, every subset of $A$ also satisfies $(*)$.

Lemma 12.11 (primitive-kernel injection).

Let $A$ be infinite and satisfy $(*)$, and let $K$ be its primitive kernel. Then:

1. (i) $K$ is an infinite primitive subset of $A$, hence also satisfies $(*)$.
2. (ii) For every $n\in A\setminus K$ there exists at least one element $\kappa(n)\in K$ with $\kappa(n)<n$ and $\kappa(n)\mid n$.
3. (iii) Any such choice of $\kappa(n)$ defines an injective map \[ \kappa:A\setminus K\longrightarrow K. \]

Proof. (i) By definition, no element of $K$ is divisible by a smaller element of $A$; in particular no two distinct elements of $K$ divide one another, so $K$ is primitive. Since $K\subseteq A$, it also satisfies $(*)$.

To see that $K$ is infinite, suppose instead that $K$ were finite. By Round-2 Corollary 12.1b, each $k\in K$ has at most one larger multiple in $A$. Hence $A$ would contain at most the elements of $K$ together with at most one further element above each $k\in K$, so \[ |A|\le 2|K|<\infty, \] contradicting that $A$ is infinite. Thus $K$ is infinite.

(ii) Fix $n\in A\setminus K$. Consider the finite set \[ D_n:=\{d\in A:d\mid n\}. \] This set is nonempty because $n\in D_n$. Choose $d_0\in D_n$ minimal with respect to the usual order on $\mathbb N$. Since $n\notin K$, we have $d_0<n$. By minimality of $d_0$ inside $D_n$, there is no element $e\in A$ with $e<d_0$ and $e\mid d_0$. Hence $d_0\in K$. Define $\kappa(n):=d_0$. Then $\kappa(n)\in K$, $\kappa(n)<n$, and $\kappa(n)\mid n$.

(iii) Suppose $n_1,n_2\in A\setminus K$ are distinct and satisfy \[ \kappa(n_1)=\kappa(n_2)=k. \] Then $k\in K$, and $k\mid n_1$, $k\mid n_2$, with both $n_1,n_2>k$. This contradicts Round-2 Corollary 12.1b, which says that a fixed element of $A$ can have at most one larger multiple in $A$. Therefore $\kappa$ is injective. $\square$

Proposition 12.12 (counting and reciprocal transfer to the primitive kernel).

Let $A$ and $K$ be as in Lemma 12.11. Then for every $N\ge 1$, \begin{equation} \label{wsref-0-65-71-3a-63-6f-75-6e-74-2d-74-72-61-6e-73-66-65-72} A(N)\le K(N)+K(N/2)\le 2K(N). \end{equation} Moreover, \begin{equation} \label{wsref-0-65-71-3a-72-65-63-69-70-72-6f-63-61-6c-2d-74-72-61-6e-73-66-65-72} \sum_{a\in A}\frac1a\le \frac32\sum_{k\in K}\frac1k, \end{equation} and \begin{equation} \label{wsref-0-65-71-3a-77-65-69-67-68-74-65-64-2d-74-72-61-6e-73-66-65-72} \sum_{a\in A}\frac1{a\log a}\le \frac32\sum_{k\in K}\frac1{k\log k}. \end{equation}

Proof. Split \[ A=K\sqcup B, \qquad B:=A\setminus K. \] By Lemma 12.11 there is an injective map $\kappa:B\to K$ with $\kappa(b)\mid b$ and $\kappa(b)<b$ for every $b\in B$. Since $\kappa(b)$ is a proper divisor of $b$, we have \[ b\ge 2\kappa(b). \]

Now fix $N\ge 1$ and let $b\in B\cap[1,N]$. Then \[ \kappa(b)\le b/2\le N/2. \] Since $\kappa$ is injective, the map $b\mapsto \kappa(b)$ injects $B\cap[1,N]$ into $K\cap[1,N/2]$. Therefore \[ |B\cap[1,N]|\le K(N/2). \] Adding the kernel elements gives \[ A(N)=K(N)+|B\cap[1,N]|\le K(N)+K(N/2)\le 2K(N), \] which proves (eq:count-transfer).

For the unweighted reciprocal sum, use $b\ge 2\kappa(b)$: \[ \sum_{b\in B}\frac1b \le \sum_{b\in B}\frac1{2\kappa(b)} \le \frac12\sum_{k\in K}\frac1k, \] where the last inequality again uses injectivity of $\kappa$. Hence \[ \sum_{a\in A}\frac1a = \sum_{k\in K}\frac1k+\sum_{b\in B}\frac1b \le \frac32\sum_{k\in K}\frac1k, \] proving (eq:reciprocal-transfer).

For the logarithmically weighted sum, note first that $K\subseteq A$ and, by the earlier foundation, $2\notin A$ for infinite sets satisfying $(*)$. Hence every $k\in K$ satisfies $k\ge 3$, so $\log k>0$. Also $b\ge 2\kappa(b)$ implies \[ \log b\ge \log \kappa(b). \] Therefore \[ \frac1{b\log b} \le \frac1{2\kappa(b)\log \kappa(b)}. \] Summing over $b\in B$ and using injectivity of $\kappa$ again yields \[ \sum_{b\in B}\frac1{b\log b} \le \frac12\sum_{k\in K}\frac1{k\log k}. \] Adding the kernel contribution gives (eq:weighted-transfer). $\square$

Theorem 12.13 (reduction of Q1, Q2, Q3 to primitive sets).

Let (Q1$_{\mathrm{prim}}$), (Q2$_{\mathrm{prim}}$), (Q3$_{\mathrm{prim}}$) denote the versions of $Q1$, $Q2$, $Q3$ in which one additionally assumes that $A$ is primitive. Then:

1. (a) $Q1$ is true if and only if (Q1$_{\mathrm{prim}}$) is true.
2. (b) $Q3$ is true if and only if (Q3$_{\mathrm{prim}}$) is true.
3. (c) At the yes/no level, $Q2$ is true if and only if (Q2$_{\mathrm{prim}}$) is true. More precisely: if (Q2$_{\mathrm{prim}}$) holds with some exponent $c>0$, then for every $0<c'<c$, $Q2$ holds with exponent $c'$.

Proof. The implications from the general statements to the primitive statements are immediate, since primitive sets are a special case.

(a) Suppose $Q1$ holds, and let $A$ be an infinite set satisfying $(*)$ with \[ \liminf_{N\to\infty}\frac{A(N)}{\sqrt N}>0. \] Let $K$ be its primitive kernel. By (eq:count-transfer), \[ K(N)\ge \frac12 A(N) \qquad\text{for every }N. \] Hence \[ \liminf_{N\to\infty}\frac{K(N)}{\sqrt N} \ge \frac12 \liminf_{N\to\infty}\frac{A(N)}{\sqrt N}>0. \] Since $K$ is infinite, primitive, and satisfies $(*)$, this proves (Q1$_{\mathrm{prim}}$). The converse is trivial.

(b) If (Q3$_{\mathrm{prim}}$) holds and $A$ is arbitrary satisfying $(*)$, let $K$ be its primitive kernel. Then by (eq:reciprocal-transfer), \[ \sum_{a\in A}\frac1a\le \frac32\sum_{k\in K}\frac1k. \] The right-hand side converges by (Q3$_{\mathrm{prim}}$), so $Q3$ holds. The converse is again trivial because primitive sets are a special case.

(c) First, if $Q2$ holds for all sets, then it certainly holds for primitive ones. Conversely, assume (Q2$_{\mathrm{prim}}$) holds with exponent $c>0$. Fix any $c'$ with $0<c'<c$. Let $A$ be arbitrary satisfying $(*)$, and let $K$ be its primitive kernel. By assumption, there are infinitely many $N$ with \[ K(N)<N^{1-c}. \] For such $N$, Proposition 12.12 gives \[ A(N)\le 2K(N)<2N^{1-c}. \] Since $c-c'>0$, for all sufficiently large $N$ one has $2<N^{c-c'}$, hence \[ 2N^{1-c}<N^{1-c'}. \] Therefore there are infinitely many $N$ such that \[ A(N)<N^{1-c'}. \] Thus $Q2$ holds with exponent $c'$. Since the original question only asks for the existence of some positive exponent, the yes/no status of $Q2$ is unchanged by restricting to primitive sets. $\square$

Corollary 12.13a (unconditional weighted reciprocal theorem).

For every infinite set $A\subseteq\mathbb N$ satisfying $(*)$, \[ \sum_{a\in A}\frac1{a\log a}<2.4. \] In particular, \[ \sum_{a\in A}\frac1{a\log a}<\infty. \]

Proof. Let $K$ be the primitive kernel of $A$. By Proposition 12.12, \[ \sum_{a\in A}\frac1{a\log a} \le \frac32\sum_{k\in K}\frac1{k\log k}. \] Now $K$ is primitive and $2\notin K$ because $K\subseteq A$ and infinite such sets $A$ avoid $2$ by Round-2 Corollary 12.1b. Therefore Theorem 4.4 of Lichtman applies and gives \[ \sum_{k\in K}\frac1{k\log k}<1.60. \] Multiplying by $3/2$ yields \[ \sum_{a\in A}\frac1{a\log a}<2.40. \] $\square$

Interpretation relative to Round 3.

Round 3 showed that a large square-based primitive class cannot reach the target in $Q1$. Round 4 now shows that this is not a defect of having insisted on primitiveness: adding nonprimitive multiples can only change the counting function by a factor at most $2$. Thus any genuine progress on Q1 or Q3 must come from finding a qualitatively new primitive construction, or from proving a theorem for primitive sets.

6) ADVERSARIAL VERIFICATION

(i) Could a divisibility component have long chains and break the reduction? No. In fact, Round-2 Corollary 12.1b is much stronger: a fixed $a\in A$ has at most one larger multiple in $A$ in total. So chains of length $\ge 3$ are impossible automatically, because if $a\mid b\mid c$ with $a<b<c$, then $a$ would have two larger multiples $b$ and $c$.

(ii) Is the map $\kappa$ well-defined when a nonkernel element has several minimal divisors? Yes. One may choose any minimal divisor in $K$. Injectivity does not depend on uniqueness: if two distinct elements were assigned the same $k\in K$, then $k$ would divide two distinct larger elements of $A$, contradicting Round-2 Corollary 12.1b.

(iii) Could the counting bound fail near the endpoint $N/2$? No. If $b\in A\setminus K$ and $\kappa(b)=k$, then $b\ge 2k$. Hence $b\le N$ implies $k\le N/2$. This is the only place where $N/2$ enters.

(iv) Is there any issue with logarithms at small numbers? No. Infinite sets satisfying $(*)$ contain neither $1$ nor $2$, by the earlier foundation. Hence every $k\in K$ satisfies $k\ge 3$, so $\log k>0$.

(v) Does the reduction really preserve the open questions? For Q1 and Q3, yes exactly: primitive is a special case in one direction, and Proposition 12.12 gives the reverse transfer. For Q2, the exponent may shrink from $c$ to any $c'<c$ when passing from primitive sets back to general sets, but since Q2 only asks whether some positive exponent exists, the yes/no status is preserved.

(vi) Could the primitive kernel $K$ be finite even when $A$ is infinite? No. If $K$ were finite, each $k\in K$ could support at most one larger multiple in $A$, so $A$ would have at most $2|K|$ elements.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

This round does not solve the original Erdős--Sárközy questions outright, but it isolates the true core of the problem.

The three open questions may be reduced to primitive sets. In particular, any eventual counterexample to Q1 or Q3 must already be primitive, and any proof of Q1--Q3 may be carried out after restricting to primitive sets.

This is a strict advance beyond Round 3 because it proves that the nonprimitive part of a set satisfying $(*)$ is asymptotically inessential:

• it can increase counting functions by at most a factor $2$;
• it can increase reciprocal sums by at most a factor $3/2$;
• it yields an unconditional explicit theorem \[ \sum_{a\in A}\frac1{a\log a}<2.4. \]

So the unresolved core has now been sharply reformulated as follows:

Does there exist an infinite primitive set $A$ satisfying $(*)$ with \[ \liminf_{N\to\infty}\frac{|A\cap[1,N]|}{\sqrt N}>0? \] Must every primitive such $A$ satisfy \[ \sum_{a\in A}\frac1a<\infty? \] And does some positive-exponent gap in Q2 already hold in the primitive case?

That primitive reformulation is the minimal corrected statement isolated by this round.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 70%

9) REFERENCES

• T. F. Bloom, Erdős Problem #12, accessed 2026-03-07.
• J. D. Lichtman, A proof of the Erdős primitive set conjecture, Forum of Mathematics, Pi 11 $2023$, e18, 1--21.

10) OUTPUT FORMAT

Here $x=12$, so the requested export filename is \[ \texttt{12\_solutions.tex}. \]

Erdős Problem #12 --- Round 3 (Continuation & Gap-Closure Mode)

1) ROUND-3 OBJECTIVE

Path (C): obstruction/correction inside the Round-2 square-based program.

Round 2 proved that whenever \[ S\subseteq \mathbb N_{\ge 2} \] is primitive and every prime factor of every $s\in S$ is congruent to $3\pmod 4$, the square set \[ A(S):=\{s^2:s\in S\} \] satisfies (*). That opened a natural constructive program: make $S$ as large as possible.

Round 2, however, only supplied fixed-$k$ squarefree $k$-prime examples (Corollary 12.4b and Proposition 12.5), giving \[ |A_k\cap[1,N]|\asymp \frac{\sqrt N}{\log N}(\log\log N)^{k-1}, \] and it only ruled out one special "private prime" strategy.

The most promising Round-3 task is therefore to settle the internal size question for the whole Round-2 square-based class:

How large can a primitive set $S$ supported on primes $3\bmod 4$ actually be?

I will prove a sharp answer (for infinitely many scales): inside this entire class, one can reach \[ \gg \frac{\sqrt N}{\sqrt{\log N}} \] along an infinite sequence of $N$, but one can never do better than \[ \ll \frac{\sqrt N}{\sqrt{\log N}} \] in general. Thus the Round-2 square-based strategy has an intrinsic $\sqrt{\log N}$ barrier and cannot by itself settle $Q1$.

2) ROUND-2 FOUNDATION USED

I rely on the following specific Round 2 results.

• Round-2 Lemma 12.3 / Corollary 12.3a: for $p\equiv 3\pmod 4$, \[ v_p(x^2+y^2)=2\min(v_p(x),v_p(y)), \] hence $p^{2e}\mid (x^2+y^2)$ forces $p^e\mid x,y$.

• Round-2 Theorem 12.4: if $S$ is primitive and every prime divisor of every element of $S$ is congruent to $3\pmod 4$, then \[ A(S)=\{s^2:s\in S\} \] satisfies property (*).

• Round-2 Proposition 12.6: a certain "private prime" subclass cannot achieve $\gg \sqrt N$. Round 3 replaces that by an obstruction for the entire square-based class coming from Theorem 12.4.

3) NEW INSIGHT / TOOL (ROUND-3)

The genuinely new ingredient is a block-antichain construction inside the multiplicative semigroup \[ \mathcal M:=\{n\in\mathbb N:\ p\mid n\Rightarrow p\equiv 3\pmod 4\}. \]

There are two parts.

1. Analytic size of $\mathcal M$. By a standard Selberg--Delange theorem (specialised below), \[ M(x):=|\mathcal M\cap[1,x]|\asymp \frac{x}{\sqrt{\log x}}. \]

2. Primitive extraction by thick blocks. Although $\mathcal M$ itself is not primitive, a subset of one interval $(x/3,x]$ is primitive, because the least nontrivial element of $\mathcal M$ is $3$. By choosing a very sparse sequence of scales $x_j$ and taking many elements of $\mathcal M\cap(x_j/3,x_j]$ that avoid divisibility by earlier chosen elements, one can inductively build an infinite primitive \[ S\subseteq \mathcal M \] with \[ |S\cap[1,x_j]|\gg \frac{x_j}{\sqrt{\log x_j}} \] for infinitely many $j$.

This is a strict strengthening of Round 2's fixed-$k$ families, and it also shows that the entire Round-2 square-based method has a built-in $\sqrt{\log N}$ loss.

4) ATTACK PLAN (ROUND-3)

Exact Round-2 gap. Round 2 showed that some primitive sets $S\subseteq \mathcal M$ work, but did not determine the true order of magnitude obtainable from this paradigm.

Claims to prove now.

1. Prove an analytic counting estimate for $\mathcal M$: \[ M(x)\asymp \frac{x}{\sqrt{\log x}}. \]

2. Deduce an upper bound for the whole Round-2 square-based class: for every primitive $S\subseteq \mathcal M$, \[ |A(S)\cap[1,N]|\ll \frac{\sqrt N}{\sqrt{\log N}}. \] Hence no set produced via Round-2 Theorem 12.4 can answer $Q1$.

3. Construct an infinite primitive $S\subseteq \mathcal M$ with \[ |S\cap[1,x_j]|\gg \frac{x_j}{\sqrt{\log x_j}} \] for infinitely many $x_j$, and then invoke Round-2 Theorem 12.4 to obtain \[ |A(S)\cap[1,N_j]|\gg \frac{\sqrt{N_j}}{\sqrt{\log N_j}} \qquad\text{for infinitely many }N_j=x_j^2. \]

Why this overcomes the previous obstacle. Round 2 used only thin fixed-$k$ layers of $\mathcal M$. The new construction instead uses full local density of $\mathcal M$ on carefully separated scales, while preserving primitivity by:

• taking each block inside an interval of ratio $<3$, and
• excluding multiples of earlier chosen elements.

5) WORK (ROUND-3)

Notation.

Let \[ \mathcal M:=\{n\in\mathbb N:\ p\mid n\Longrightarrow p\equiv 3\pmod 4\}, \qquad M(x):=|\mathcal M\cap[1,x]|. \] Note that $1\in \mathcal M$, and the least element of $\mathcal M\setminus\{1\}$ is $3$.

Proposition 12.7 (analytic counting input for $\mathcal M$).

There exists a constant $C_{\mathcal M}>0$ such that \[ M(x)=C_{\mathcal M}\frac{x}{(\log x)^{1/2}}+O\!\left(\frac{x}{(\log x)^{3/4}}\right) \qquad (x\to\infty). \] Consequently there exist positive constants $c_1,c_2,x_0$ such that for all $x\ge x_0$, \begin{equation} \label{wsref-0-65-71-3a-4d-2d-75-70-70-65-72} M(x)\le c_2\frac{x}{\sqrt{\log x}}, \end{equation} and \begin{equation} \label{wsref-0-65-71-3a-4d-2d-69-6e-74-65-72-76-61-6c} M(x)-M(x/3)\ge c_1\frac{x}{\sqrt{\log x}}. \end{equation}

Proof. Apply the Selberg--Delange asymptotic of Chang--Martin, Theorem 3.4, with modulus $q=4$ and residue class set $B=\{3\}$. Then $N_B$ in their notation is exactly the set $\mathcal M$ above, and their exponent is \[ \beta=\frac{|B|}{\varphi(4)}=\frac12. \] Hence \[ M(x)=\#\{n\le x:\ n\in\mathcal M\} = \frac{G_B(1)}{\Gamma(1/2)}\frac{x}{(\log x)^{1/2}} +O\!\left(\frac{x}{(\log x)^{3/4}}\right), \] which is the asserted formula with \[ C_{\mathcal M}=\frac{G_B(1)}{\Gamma(1/2)}>0. \] The upper bound (eq:M-upper) is immediate.

For (eq:M-interval), subtract the same asymptotic at $x$ and at $x/3$: \[ M(x)-M(x/3) = C_{\mathcal M}\frac{x}{\sqrt{\log x}} - C_{\mathcal M}\frac{x/3}{\sqrt{\log(x/3)}} + O\!\left(\frac{x}{(\log x)^{3/4}}\right). \] Since \[ \frac{\sqrt{\log x}}{\sqrt{\log(x/3)}}\to 1 \qquad (x\to\infty), \] the main term equals \[ \left(\frac23+o(1)\right)C_{\mathcal M}\frac{x}{\sqrt{\log x}}, \] which is positive for all sufficiently large $x$. After reducing $c_1$ if necessary and enlarging $x_0$, (eq:M-interval) follows. $\square$

Proposition 12.8 (upper bound for the entire Round-2 square-based class).

Let $S\subseteq \mathcal M\setminus\{1\}$ be primitive, and set \[ A(S):=\{s^2:\ s\in S\}. \] Then for all large $N$, \[ |A(S)\cap[1,N]| = |S\cap[1,\sqrt N]| \ll \frac{\sqrt N}{\sqrt{\log N}}. \] In particular, \[ \liminf_{N\to\infty}\frac{|A(S)\cap[1,N]|}{\sqrt N}=0. \] So no set obtained from Round-2 Theorem 12.4 can solve $Q1$.

Proof. Because $S\subseteq \mathcal M$, \[ |A(S)\cap[1,N]|=|S\cap[1,\sqrt N]|\le M(\sqrt N). \] Applying (eq:M-upper), \[ M(\sqrt N)\le c_2\frac{\sqrt N}{\sqrt{\log(\sqrt N)}} = \sqrt 2\,c_2\frac{\sqrt N}{\sqrt{\log N}}, \] which proves the claim. $\square$

Theorem 12.9 (block-antichain construction inside $\mathcal M$).

There exists an infinite primitive set \[ S\subseteq \mathcal M\setminus\{1\} \] such that for infinitely many $x$, \[ |S\cap[1,x]|\gg \frac{x}{\sqrt{\log x}}. \]

Proof. Fix constants $c_1,c_2,x_0$ as in Proposition 12.7, and set \[ \eta:=\frac{c_1}{32c_2}. \] We will inductively construct:

• a strictly increasing sequence $x_1<x_2<\cdots$ tending to infinity,
• finite sets $T_j\subseteq \mathcal M\cap (x_j/3,x_j]$,

such that if \[ S_j:=T_1\cup\cdots\cup T_j, \] then

1. (a) $S_j$ is primitive;
2. (b) $\displaystyle \sum_{s\in S_j}\frac1s\le \eta\sum_{i=1}^j 2^{-i}<\eta$;
3. (c) $\displaystyle |T_j|\ge \frac{c_1}{5}\frac{x_j}{\sqrt{\log x_j}}$.

Once this is done, the infinite union \[ S:=\bigcup_{j\ge 1}T_j \] is primitive, and for each $j$ we have \[ |S\cap[1,x_j]|\ge |T_j|\ge \frac{c_1}{5}\frac{x_j}{\sqrt{\log x_j}}, \] which proves the theorem.

Induction step. Suppose $S_{j-1}$ has already been constructed (for $j=1$, take $S_0=\varnothing$). Choose $x_j$ so large that all of the following hold:

1. (i) $x_j\ge x_0$;
2. (ii) $x_j>3x_{j-1}$ (for $j=1$ there is no restriction);
3. (iii) $x_j>(\max S_{j-1})^2$ (vacuous if $S_{j-1}=\varnothing$);
4. (iv) $\displaystyle \frac{3c_1}{4\sqrt{\log x_j}}\le \frac{\eta}{2^j}$;
5. (v) $\displaystyle \frac{c_1}{4}\frac{x_j}{\sqrt{\log x_j}}\ge 1$.

This is possible because $x_j$ may be taken arbitrarily large.

Now consider the interval \[ I_j:=(x_j/3,x_j]. \] By (eq:M-interval), \[ |\mathcal M\cap I_j| = M(x_j)-M(x_j/3) \ge c_1\frac{x_j}{\sqrt{\log x_j}}. \] Let $E_j$ be the set of elements of $\mathcal M\cap I_j$ divisible by at least one element of $S_{j-1}$. Then by the union bound, \[ |E_j| \le \sum_{s\in S_{j-1}}\#\{n\in\mathcal M\cap I_j:\ s\mid n\}. \] If $s\mid n$ and $n\in \mathcal M$, then $n=sm$ with $m\in\mathcal M$. Hence \[ \#\{n\in\mathcal M\cap I_j:\ s\mid n\}\le M(x_j/s). \] Therefore \[ |E_j| \le \sum_{s\in S_{j-1}} M(x_j/s). \] Because $s\le \max S_{j-1}<\sqrt{x_j}$ by (iii), we have $x_j/s>\sqrt{x_j}$ and so \[ \log(x_j/s)\ge \frac12\log x_j. \] Using (eq:M-upper), \[ M(x_j/s)\le c_2\frac{x_j/s}{\sqrt{\log(x_j/s)}} \le \sqrt 2\,c_2\frac{x_j}{s\sqrt{\log x_j}} \le 2c_2\frac{x_j}{s\sqrt{\log x_j}}. \] Summing over $s\in S_{j-1}$ and using the induction hypothesis (b), \[ |E_j| \le 2c_2\frac{x_j}{\sqrt{\log x_j}}\sum_{s\in S_{j-1}}\frac1s < 2c_2\eta\frac{x_j}{\sqrt{\log x_j}} = \frac{c_1}{16}\frac{x_j}{\sqrt{\log x_j}}. \] Thus the set \[ U_j:=(\mathcal M\cap I_j)\setminus E_j \] of admissible new elements satisfies \[ |U_j| \ge \left(c_1-\frac{c_1}{16}\right)\frac{x_j}{\sqrt{\log x_j}} = \frac{15c_1}{16}\frac{x_j}{\sqrt{\log x_j}}. \] Choose any subset \[ T_j\subseteq U_j \] of cardinality \[ m_j:=\left\lfloor \frac{c_1}{4}\frac{x_j}{\sqrt{\log x_j}}\right\rfloor. \] This is possible because $|U_j|>m_j$ for large $x_j$, and by (v) we have $m_j\ge 1$. Moreover \[ m_j\ge \frac{c_1}{5}\frac{x_j}{\sqrt{\log x_j}} \] for all sufficiently large $x_j$, yielding (c).

Next, because every element of $T_j$ is $>x_j/3$, its reciprocal is at most $3/x_j$, so \[ \sum_{t\in T_j}\frac1t \le \frac{3m_j}{x_j} \le \frac{3c_1}{4\sqrt{\log x_j}} \le \frac{\eta}{2^j} \] by (iv). Hence \[ \sum_{s\in S_j}\frac1s = \sum_{s\in S_{j-1}}\frac1s+\sum_{t\in T_j}\frac1t \le \eta\sum_{i=1}^{j-1}2^{-i}+\frac{\eta}{2^j} = \eta\sum_{i=1}^{j}2^{-i}, \] so the induction hypothesis (b) is preserved.

Finally we verify primitivity.

• No old element divides a new element: this is exactly how $U_j$ was defined.
• No new element divides an old element: by (ii), every new element exceeds $x_j/3>x_{j-1}$, while every old element is at most $x_{j-1}$.
• No two distinct new elements divide one another: if $u,v\in T_j$ with $u<v$ and $u\mid v$, then \[ v/u\in \mathcal M\setminus\{1\}, \] so $v/u\ge 3$. But since $u>x_j/3$ and $v\le x_j$, \[ v/u<3, \] a contradiction.

Thus $S_j$ is primitive, completing the induction and the proof. $\square$

Corollary 12.9a (new valid construction for the original divisibility problem).

There exists an infinite set $A\subseteq \mathbb N$ satisfying (*) such that for infinitely many $N$, \[ |A\cap[1,N]|\gg \frac{\sqrt N}{\sqrt{\log N}}. \]

Proof. Let $S$ be as in Theorem 12.9, and define \[ A:=A(S)=\{s^2:\ s\in S\}. \] Since $S$ is primitive and every prime factor of every $s\in S$ is congruent to $3\pmod 4$, Round-2 Theorem 12.4 implies that $A$ satisfies (*).

Now take $N_j:=x_j^2$. Then \[ |A\cap[1,N_j]| = |S\cap[1,x_j]| \gg \frac{x_j}{\sqrt{\log x_j}} = \sqrt 2\,\frac{\sqrt{N_j}}{\sqrt{\log N_j}}. \] Hence the claimed lower bound holds for infinitely many $N=N_j$. $\square$

Theorem 12.10 (sharp size scale inside the Round-2 square-based class).

Among all sets of the form \[ A(S)=\{s^2:\ s\in S\}, \] where $S\subseteq \mathcal M\setminus\{1\}$ is primitive, the correct order of magnitude along infinitely many scales is \[ \frac{\sqrt N}{\sqrt{\log N}}. \] More precisely:

1. every such $A(S)$ satisfies \[ |A(S)\cap[1,N]|\ll \frac{\sqrt N}{\sqrt{\log N}} \qquad (N\to\infty), \] by Proposition 12.8;
2. there exists such an $A(S)$ with \[ |A(S)\cap[1,N_j]|\gg \frac{\sqrt{N_j}}{\sqrt{\log N_j}} \] for infinitely many $N_j$, by Corollary 12.9a.

Thus the full Round-2 square-based construction method has now been pushed to its natural asymptotic limit (up to constants) on an infinite subsequence.

6) ADVERSARIAL VERIFICATION

(i) Does the block construction really preserve primitivity? Yes. Inside one block $(x_j/3,x_j]$, divisibility would force a quotient in $\mathcal M\setminus\{1\}$, hence at least $3$, but every quotient of two numbers in that interval is $<3$. Across different blocks, earlier elements are explicitly forbidden from dividing later ones, and later elements are too large to divide earlier ones.

(ii) Is the estimate for excluded multiples legitimate? Yes. If $s\in S_{j-1}$ divides $n\in\mathcal M$, then $n=sm$ with $m\in\mathcal M$. Thus the number of multiples of $s$ up to $x_j$ is at most $M(x_j/s)$. No independence assumption is used; only the union bound.

(iii) Did the proof accidentally use more than finite reciprocal mass of old elements? No. The key inequality is \[ |E_j|\ll \frac{x_j}{\sqrt{\log x_j}}\sum_{s\in S_{j-1}}\frac1s. \] Only the finite reciprocal sum of the previously chosen blocks enters. The construction deliberately makes the blockwise reciprocal contributions summable.

(iv) Is the analytic input applied correctly? Yes. Chang--Martin Theorem 3.4 counts integers all of whose prime factors lie in a fixed set of reduced residue classes. With $q=4$ and the single class $3\bmod 4$, this is exactly the semigroup $\mathcal M$. The exponent is $\beta=1/\varphi(4)=1/2$, giving the $\sqrt{\log x}$ denominator.

(v) Does Corollary 12.9a settle $Q1$? No. It only yields the lower bound \[ |A\cap[1,N_j]|\gg \frac{\sqrt{N_j}}{\sqrt{\log N_j}} \] for infinitely many $N_j$. This is far from the required \[ \liminf_{N\to\infty}\frac{|A\cap[1,N]|}{\sqrt N}>0. \] So Q1 remains open.

(vi) Does this contradict the density-zero theorem of Erdős--Sárközy? No. Both \[ \frac{x}{\sqrt{\log x}}=o(x) \qquad\text{and}\qquad \frac{\sqrt N}{\sqrt{\log N}}=o(\sqrt N). \] So the new construction is sparse enough to be consistent with all known upper bounds.

(vii) Is the Round-2 theorem being used in exactly the permitted way? Yes. I do not re-prove Round-2 Theorem 12.4; I invoke it exactly once, at the end, after constructing a larger primitive $S$. The new mathematical work is entirely the analytic counting of $\mathcal M$ plus the primitive extraction argument.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 3 does not solve the original Erdős problem in full generality. However, it gives a sharp obstruction/correction for the whole constructive framework introduced in Round 2:

Within the entire square-based class supplied by Round-2 Theorem 12.4, the best possible size scale is \[ |A\cap[1,N]|\asymp \frac{\sqrt N}{\sqrt{\log N}} \] along infinitely many scales, and in particular this class can never realise the target in $Q1$.

This is a substantive advance beyond Round 2 for two reasons:

1. it replaces the fixed-$k$ families by a much denser valid construction, namely \[ |A\cap[1,N_j]|\gg \frac{\sqrt{N_j}}{\sqrt{\log N_j}} \] for infinitely many $N_j$;
2. it proves that no construction obtainable from Round-2 Theorem 12.4 can exceed this order by more than constants.

So the next unresolved gap is now sharply isolated:

Any eventual positive solution to $Q1$ must leave the Round-2 square-based paradigm entirely (or augment it with new structure not covered by primitive subsets of $\mathcal M$).

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

• B. Chang and G. Martin, The smallest invariant factor of the multiplicative group, especially Theorem 3.4, used here with $q=4$ and residue class set $B=\{3\}$ to count integers all of whose prime factors are congruent to $3\pmod 4$.
• T. F. Bloom, Erdős Problem #12, problem statement and current status page, accessed 2026-03-07.
• Round-2 results from the present investigation: Lemma 12.3, Corollary 12.3a, and Theorem 12.4.

10) OUTPUT FORMAT

Here $x=12$, so the requested export filename is \[ \texttt{12\_solutions.tex}. \]

Round 2

1) ROUND-2 OBJECTIVE

I pursue path (C) on the natural square-based class generated by the Round-1 example. More precisely, I prove an exact structural criterion for sets of the form \[ A_S:=\{s^2:s\in S\}, \] where every prime factor of every $s\in S$ is congruent to $3\pmod 4$. This gives two strictly new consequences beyond Round 1:

1. a denser explicit construction than the prime-square family, namely semiprime-squares, with \[ |A\cap[1,N]|\gg \frac{\sqrt N\,\log\log N}{\log N}, \]
2. a fatal obstruction to the Round-1 square strategy for Q1: every set in this entire square-based class has size $o(\sqrt N)$, so no such construction can prove a positive answer to Q1.

Globally, Q1--Q3 remain unresolved.

2) ROUND-1 FOUNDATION USED

I use the following Round-1 ingredients without reproving them.

• Lemma 12.1 (residue-class obstruction). For fixed $a\in A$, among larger elements of $A$ one cannot occupy both residues $r$ and $-r\pmod a$. In particular, in residue class $0\pmod a$, there cannot be two distinct larger multiples of $a$.
• Lemma 12.2 (prime-square example). The proof there uses the key modular fact that for a prime $p\equiv 3\pmod 4$, the congruence $x^2\equiv -1\pmod p$ has no solution.

The new work below strengthens the modular idea from Lemma 12.2 to an exact $p$-adic statement and then converts the residue-$0$ obstruction from Lemma 12.1 into a full characterization of the square-based class.

3) NEW INSIGHT / TOOL (ROUND-2)

The genuinely new tool is the following $p$-adic strengthening of the Round-1 congruence argument.

New tool. If $p\equiv 3\pmod 4$ is prime, then for all integers $x,y$, \[ \nu_p(x^2+y^2)=2\min\left(\nu_p(x),\nu_p(y)\right). \] Equivalently: if $p^{2e}\mid x^2+y^2$, then $p^e\mid x$ and $p^e\mid y$.

This yields an exact reduction for the whole natural class $A_S=\{s^2:s\in S\}$ with all prime factors of $S$ in $3\pmod 4$:

$A_S$ satisfies $(*)$ if and only if every $s\in S$ divides at most one larger element of $S$.

Thus the square-based problem becomes a purely multiplicative divisibility problem on $S$.

4) ATTACK PLAN (ROUND-2)

The main gap after Round 1 was this: the prime-square construction is rigorous but too sparse to address Q1, and Round 1 had no mechanism either to enlarge it substantially or to prove that the whole strategy must fail.

The Round-2 plan is therefore:

1. strengthen the local modular obstruction from primes to exact prime-power divisibility;
2. derive a necessary-and-sufficient criterion for all square families built from $3\pmod 4$ primes;
3. use that criterion in two opposite directions:
   • construct a denser family than prime squares (semiprime-squares), and
   • prove that every construction in this entire square-based class still has cardinality $o(\sqrt N)$, so this line of attack cannot settle Q1 positively.

5) WORK (ROUND-2)

Notation. Let \[ \mathcal P_3:=\{p\text{ prime}: p\equiv 3\pmod 4\}. \] For a set $S\subseteq\mathbb N$, write \[ A_S:=\{s^2:s\in S\}. \]

Lemma 12.3 ($p$-adic valuation of a sum of two squares for $p\equiv 3\pmod 4$). Let $p\in\mathcal P_3$ and let $x,y\in\mathbb Z$. Then \[ \nu_p(x^2+y^2)=2\min\left(\nu_p(x),\nu_p(y)\right). \]

Proof. Set \[ t:=\min\left(\nu_p(x),\nu_p(y)\right). \] Write \[ x=p^t x_1,\qquad y=p^t y_1, \] where at least one of $x_1,y_1$ is not divisible by $p$. Then \[ x^2+y^2=p^{2t}(x_1^2+y_1^2). \] So it suffices to show that $p\nmid x_1^2+y_1^2$.

If exactly one of $x_1,y_1$ is divisible by $p$, then clearly $x_1^2+y_1^2\not\equiv 0\pmod p$. Thus the only remaining case is $p\nmid x_1y_1$ and \[ x_1^2+y_1^2\equiv 0\pmod p. \] Then \[ (x_1y_1^{-1})^2\equiv -1\pmod p, \] which is impossible because $p\equiv 3\pmod 4$ and hence $-1$ is not a quadratic residue modulo $p$. Therefore $p\nmid x_1^2+y_1^2$, and so \[ \nu_p(x^2+y^2)=2t=2\min\left(\nu_p(x),\nu_p(y)\right). \] $\square$

Corollary 12.4 (divisibility forced by square-divisibility). Let $u,v,w\in\mathbb N$, and assume every prime divisor of $u$ lies in $\mathcal P_3$. If \[ u^2\mid (v^2+w^2), \] then \[ u\mid v\qquad\text{and}\qquad u\mid w. \]

Proof. Write \[ u=\prod_{i=1}^r p_i^{e_i} \] with each $p_i\equiv 3\pmod 4$. From $u^2\mid v^2+w^2$ we obtain \[ \nu_{p_i}(v^2+w^2)\ge 2e_i \qquad (1\le i\le r). \] By Lemma 12.3, \[ 2\min\left(\nu_{p_i}(v),\nu_{p_i}(w)\right)=\nu_{p_i}(v^2+w^2)\ge 2e_i, \] so \[ \min\left(\nu_{p_i}(v),\nu_{p_i}(w)\right)\ge e_i. \] Hence $p_i^{e_i}\mid v$ and $p_i^{e_i}\mid w$ for every $i$, therefore $u\mid v$ and $u\mid w$. $\square$

Theorem 12.5 (exact criterion for the $3\pmod 4$ square family). Let $S\subseteq\mathbb N$, and assume every prime divisor of every $s\in S$ lies in $\mathcal P_3$. Then the set \[ A_S=\{s^2:s\in S\} \] satisfies property $(*)$ if and only if every $s\in S$ divides at most one larger element of $S$.

Proof.

Necessity. Assume $A_S$ satisfies $(*)$. Suppose, toward contradiction, that some $s\in S$ divides two distinct larger elements $t,u\in S$ with $t>s$ and $u>s$. Then in $A_S$ the three elements \[ a=s^2,\qquad b=t^2,\qquad c=u^2 \] are distinct, satisfy $b>a$ and $c>a$, and also \[ a=s^2\mid t^2+u^2=b+c, \] contradicting $(*)$. Hence each $s\in S$ divides at most one larger element of $S$.

Sufficiency. Assume now that each $s\in S$ divides at most one larger element of $S$. Suppose, toward contradiction, that $A_S$ fails $(*)$. Then there exist distinct $a,b,c\in A_S$ with $b>a$, $c>a$, and \[ a\mid (b+c). \] Write \[ a=s^2,\qquad b=t^2,\qquad c=u^2 \] with $s,t,u\in S$. Since $b>a$ and $c>a$, we have $t>s$ and $u>s$. Also \[ s^2=a\mid (b+c)=t^2+u^2. \] By Corollary 12.4, this implies $s\mid t$ and $s\mid u$. Thus $s$ divides two distinct larger elements of $S$, contradicting the hypothesis on $S$. Therefore $A_S$ satisfies $(*)$. $\square$

Corollary 12.6 (primitive-basis corollary). Let $S\subseteq\mathbb N$ be primitive (that is, no element of $S$ divides another distinct element of $S$), and assume every prime divisor of every $s\in S$ is congruent to $3\pmod 4$. Then $A_S=\{s^2:s\in S\}$ satisfies $(*)$.

Proof. In a primitive set, no $s\in S$ divides any larger element of $S$, so certainly no $s\in S$ divides two larger elements. Apply Theorem 12.5. $\square$

Proposition 12.7 (a denser explicit construction than prime squares). Define \[ S_2:=\{pq: p<q,\ p,q\in\mathcal P_3\} \] and \[ A_2:=A_{S_2}=\{(pq)^2: p<q,\ p,q\in\mathcal P_3\}. \] Then $A_2$ satisfies $(*)$.

Proof. Every element of $S_2$ is squarefree with exactly two prime factors. Hence if $m,n\in S_2$ and $m\mid n$, then $m=n$ by unique factorization. So $S_2$ is primitive. Now apply Corollary 12.6. $\square$

Proposition 12.8 (quantitative size of the semiprime-square family). There exists $c>0$ such that for all sufficiently large $x$, \[ |S_2\cap[1,x]|\ge c\,\frac{x\log\log x}{\log x}. \] Consequently, there exists $c'>0$ such that for all sufficiently large $N$, \[ |A_2\cap[1,N]|\ge c'\,\frac{\sqrt N\,\log\log N}{\log N}. \]

Proof. Let \[ \pi_3(y):=|\{p\le y: p\in\mathcal P_3\}|. \] By the prime number theorem in the progression $3\pmod 4$, there exist constants $c_0,C_0>0$ and $y_0$ such that for all $y\ge y_0$, \[ c_0\frac{y}{\log y}\le \pi_3(y)\le C_0\frac{y}{\log y}. \]

Fix $x$ large. For every prime $p\in\mathcal P_3$ with $p\le x^{1/3}$ and every prime $q\in\mathcal P_3$ with \[ x^{1/3}<q\le \frac{x}{p}, \] we have $p<q$ and $pq\le x$, so $pq\in S_2\cap[1,x]$. Moreover, because $q>x^{1/3}\ge p$, each such semiprime is counted exactly once by its smaller prime $p$. Therefore \[ |S_2\cap[1,x]| \ge \sum_{\substack{p\le x^{1/3}\\ p\in\mathcal P_3}} \left(\pi_3(x/p)-\pi_3(x^{1/3})\right). \] For $p\le x^{1/3}$ we have $x/p\ge x^{2/3}$, so for large $x$, \[ \pi_3(x/p)\ge c_0\frac{x/p}{\log(x/p)}\ge c_0\frac{x}{p\log x}. \] Also, \[ \pi_3(x^{1/3})\le C_1\frac{x^{1/3}}{\log x} \] for some absolute $C_1$. Hence \[ |S_2\cap[1,x]| \ge c_0\frac{x}{\log x} \sum_{\substack{p\le x^{1/3}\\ p\in\mathcal P_3}}\frac1p - C_1\frac{x^{1/3}}{\log x}\,\pi_3(x^{1/3}). \] Using again $\pi_3(x^{1/3})\ll x^{1/3}/\log x$, the error term is \[ \ll \frac{x^{2/3}}{(\log x)^2}. \] So it remains to lower-bound the reciprocal prime sum. By partial summation, \[ \sum_{\substack{p\le y\\ p\in\mathcal P_3}}\frac1p = \frac{\pi_3(y)}{y}+ \int_{2}^{y}\frac{\pi_3(t)}{t^2}\,dt. \] Applying the lower bound $\pi_3(t)\ge c_0 t/\log t$ for $t\ge y_0$ gives, for large $y$, \[ \sum_{\substack{p\le y\\ p\in\mathcal P_3}}\frac1p \ge c_2\log\log y \] for some $c_2>0$. Taking $y=x^{1/3}$, we obtain \[ \sum_{\substack{p\le x^{1/3}\\ p\in\mathcal P_3}}\frac1p \ge c_3\log\log x \] for large $x$ (since $\log\log x^{1/3}=\log\log x+O(1)$). Substituting into the previous estimate yields \[ |S_2\cap[1,x]| \ge c\,\frac{x\log\log x}{\log x} \] for all sufficiently large $x$.

Finally, \[ |A_2\cap[1,N]|=|S_2\cap[1,\sqrt N]| \ge c'\,\frac{\sqrt N\,\log\log N}{\log N} \] for all sufficiently large $N$, after adjusting constants. $\square$

Proposition 12.9 (fatal obstruction to the Round-1 square strategy for Q1). Let \[ \mathcal T:=\{n\in\mathbb N: \text{every prime divisor of $n$ is congruent to }3\pmod 4\}. \] Then \[ |\mathcal T\cap[1,x]|=o(x). \] Consequently, for every set $S\subseteq\mathcal T$ one has \[ |A_S\cap[1,N]|=o(\sqrt N). \] In particular, no construction of the form $A_S=\{s^2:s\in S\}$ with all prime factors of $S$ lying in $3\pmod 4$ can answer Q1 positively.

Proof. Fix $Y\ge 3$, and define \[ M_Y:=2\prod_{\substack{p\le Y\\ p\equiv 1\, (4)}}p. \] Every $n\in\mathcal T$ is coprime to $M_Y$. Hence modulo $M_Y$, such an $n$ can lie only in residue classes that are nonzero modulo $2$ and nonzero modulo every prime $p\le Y$ with $p\equiv 1\pmod 4$. Therefore the number of admissible residue classes modulo $M_Y$ is exactly \[ R_Y:=\prod_{\substack{p\le Y\\ p\equiv 1\, (4)}}(p-1), \] since modulo $2$ there is just one admissible class, namely $1$. Thus, for every $x$, \[ |\mathcal T\cap[1,x]| \le R_Y\left(\frac{x}{M_Y}+1\right) = \frac{R_Y}{M_Y}x+R_Y. \] Now \[ \frac{R_Y}{M_Y} = \frac12\prod_{\substack{p\le Y\\ p\equiv 1\, (4)}}\left(1-\frac1p\right). \] By the prime number theorem in the progression $1\pmod 4$, the reciprocal sum \[ \sum_{\substack{p\equiv 1\, (4)}}\frac1p \] diverges. Hence \[ \prod_{\substack{p\le Y\\ p\equiv 1\, (4)}}\left(1-\frac1p\right)\longrightarrow 0 \qquad (Y\to\infty). \] So given $\varepsilon>0$, we may choose $Y$ so large that \[ \frac{R_Y}{M_Y}<\varepsilon. \] Then for this fixed $Y$, \[ \frac{|\mathcal T\cap[1,x]|}{x} \le \varepsilon+\frac{R_Y}{x}. \] Letting $x\to\infty$ gives \[ \limsup_{x\to\infty}\frac{|\mathcal T\cap[1,x]|}{x}\le \varepsilon. \] Since $\varepsilon>0$ was arbitrary, $|\mathcal T\cap[1,x]|=o(x)$.

Now if $S\subseteq\mathcal T$, then \[ |A_S\cap[1,N]|=|\{s\in S:s^2\le N\}|=|S\cap[1,\sqrt N]|\le |\mathcal T\cap[1,\sqrt N]|=o(\sqrt N). \] This proves the obstruction claim. $\square$

6) ADVERSARIAL VERIFICATION

I now check the new work against the main failure modes.

• Prime-power issue. The Round-1 argument only worked modulo $p$ for prime squares. Lemma 12.3 fixes the exact missing point: it controls prime powers $p^{2e}$, so Corollary 12.4 applies to arbitrary $u$ whose prime factors all lie in $3\pmod 4$, not just to primes.

• Necessity versus sufficiency in Theorem 12.5. Necessity is immediate from the residue-$0$ case of Round-1 Lemma 12.1: if $s$ divides two larger elements $t,u$, then $s^2\mid t^2+u^2$. The nontrivial direction is sufficiency; this is exactly what Corollary 12.4 supplies. So the criterion is genuinely biconditional.

• Distinctness of the semiprimes. In Proposition 12.7, $S_2$ is primitive because every element is squarefree with exactly two prime factors. Thus divisibility between distinct elements is impossible by unique factorization; there is no hidden repeated-prime pathology.

• Double counting in Proposition 12.8. The lower bound counts semiprimes $pq$ by the smaller prime $p$ under the extra restriction $q>x^{1/3}$. Since $p\le x^{1/3}<q$, each semiprime is counted exactly once. So the lower bound is rigorous.

• Scope of the obstruction in Proposition 12.9. The conclusion $|A_S\cap[1,N]|=o(\sqrt N)$ is proved only for the restricted class $A_S=\{s^2:s\in S\}$ with all prime factors of $S$ in $3\pmod 4$. This is not a disproof of Q1. It is a disproof only of the natural Round-1 strategy class generated by the prime-square example.

• Interaction with Round-1 results. There is no contradiction with Lemma 12.2. Prime squares correspond to the special case $S=\mathcal P_3$, where indeed each element divides no larger element. Thus Theorem 12.5 strictly extends Round 1 rather than replacing it.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

The global questions Q1--Q3 remain open in this round, but the investigation has advanced in two mathematically substantive ways beyond Round 1.

1. Exact structural reduction of the whole Round-1 square strategy. For sets of the form $A_S=\{s^2:s\in S\}$ with all prime factors of $S$ in $3\pmod 4$, property $(*)$ is equivalent to the purely multiplicative condition that each $s\in S$ divides at most one larger element of $S$ (Theorem 12.5). This is a complete characterization inside that natural class.

2. A denser explicit family and a barrier. The semiprime-square family \[ A_2=\{(pq)^2: p<q,\ p\equiv q\equiv 3\pmod 4\} \] satisfies $(*)$ and obeys \[ |A_2\cap[1,N]|\gg \frac{\sqrt N\,\log\log N}{\log N}, \] which is a strict improvement on the prime-square example from Round 1. At the same time, Proposition 12.9 proves that every construction in this entire $3\pmod 4$ square class has size $o(\sqrt N)$, so this strategy can never yield a positive answer to Q1.

The sharp remaining gap is therefore clearer than after Round 1: any eventual positive answer to Q1 must come from a construction outside the whole natural class \[ A=\{s^2:s\in S,\ \text{all prime factors of $s$ are }3\pmod 4\}, \] and any negative answer must rule out such completely different constructions.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

1. H. Davenport, Multiplicative Number Theory, 3rd ed., revised by H. L. Montgomery, Graduate Texts in Mathematics 74, Springer, 2000. Used for the prime number theorem in arithmetic progressions and its standard corollaries (including divergence of reciprocal primes in a fixed reduced residue class).