Editing Openai/68ec50da-cf00-8005-b5f6-b683506e5853 (section)

=== Assistant: You’re right to call out the gap: in my previous note I incorrectly jumped from “a fixed positive density δ\deltaδ of b… ===
You’re right to call out the gap: in my previous note I (incorrectly) jumped from “a fixed positive density δ\deltaδ of bbb in a 25‑class makes ab+1ab+1ab+1 squarefree” to the conclusion that two large residue classes cannot both occur. That step needs a uniform covering argument across many different aaa’s. Below I give a careful proof that implements the “only one 25‑class survives” stability idea you suggested, without any hand‑waving.

Throughout write A⊆{1,…,N}A\subseteq\{1,\dots,N\}A⊆{1,…,N} and assume

(⋆)∀ a,b∈A:ab+1 is not squarefree.(\star)\qquad \forall\,a,b\in A:\quad ab+1\ \text{is not squarefree}.(⋆)∀a,b∈A:ab+1 is not squarefree.
Let Sr:={n≤N: n≡r(mod25)}S_r:=\{n\le N:\ n\equiv r\pmod{25}\}Sr:={n≤N: n≡r(mod25)} and Ar:=A∩SrA_r:=A\cap S_rAr:=A∩Sr; set

αr:=∣Ar∣∣Sr∣∈[0,1],∣Sr∣=N25+O(1).\alpha_r:=\frac{|A_r|}{|S_r|}\in[0,1],\qquad |S_r|=\frac{N}{25}+O(1).αr:=∣Sr∣∣Ar∣∈[0,1],∣Sr∣=25N+O(1).
We will prove:

: 

The constant 777 (and 181818) appear because 72≡−1(mod25)7^2\equiv-1\pmod{25}72≡−1(mod25), so whenever a≡b≡7(mod25)a\equiv b\equiv 7\pmod{25}a≡b≡7(mod25) we have 25∣ab+125\mid ab+125∣ab+1, which automatically violates squarefreeness.

==== 1. Single‑prime obstruction sets. Fix a prime ppp and aaa with p∤ap\nmid ap∤a. Then the congruence p2∣ab+1p^2\mid ab+1p2∣ab+1 forces ====

b≡−a−1(modp2).b\equiv -a^{-1}\pmod{p^2}.b≡−a−1(modp2).
Thus, within any fixed 252525-class StS_tSt with gcd⁡(25,p2)=1\gcd(25,p^2)=1gcd(25,p2)=1, the set

Cp(a;t):={b∈St: p2∣ab+1}C_p(a;t):=\{b\in S_t:\ p^2\mid ab+1\}Cp(a;t):={b∈St: p2∣ab+1}
is exactly one residue class modulo p2p^2p2, hence has relative density 1/p21/p^21/p2 inside StS_tSt. (If p∣ap\mid ap∣a then p2∤ab+1p^2\nmid ab+1p2∤ab+1 for all bbb, so Cp(a;t)=∅C_p(a;t)=\varnothingCp(a;t)=∅.)
# Independence across primes (CRT). For any finite set of distinct primes PPP and any choice of residue classes Rp ( mod  p2)R_p\ (\bmod\,p^2)Rp (modp2), the intersection

{b∈St: b≡Rp ( mod  p2) ∀p∈P}\{b\in S_t:\ b\equiv R_p\ (\bmod\,p^2)\ \forall p\in P\}{b∈St: b≡Rp (modp2) ∀p∈P}
has relative density ∏p∈P1p2\prod_{p\in P}\frac{1}{p^2}∏p∈Pp21 inside StS_tSt (up to O(1)O(1)O(1) boundary error). In particular, for a fixed aaa the sets {Cp(a;t)}p∈P\{C_p(a;t)\}_{p\in P}{Cp(a;t)}p∈P lift to pairwise disjoint unions of residue classes modulo ∏p∈Pp2\prod_{p\in P}p^2∏p∈Pp2; hence

∣⋃p∈PCp(a;t)∣∣St∣=∑p∈P1p2(exact for finite P, up to O(1/N)).\frac{\Bigl|\bigcup_{p\in P} C_p(a;t)\Bigr|}{|S_t|}=\sum_{p\in P}\frac{1}{p^2}\qquad\text{(exact for finite \(P\), up to \(O(1/N)\)).}∣St∣⋃p∈PCp(a;t)=p∈P∑p21(exact for finite P, up to O(1/N)).

==== Fix a finite set of primes P⊂{2,3,5,7,… }∖{5}P\subset\{2,3,5,7,\dots\}\setminus\{5\}P⊂{2,3,5,7,…}∖{5} and set ====

SP:=∑p∈P1p2(note SP<1),TP:=∑p∉P, p≠51p2.S_P:=\sum_{p\in P}\frac{1}{p^2}\qquad(\text{note }S_P<1),\qquad
T_P:=\sum_{p\notin P,\ p\ne5}\frac{1}{p^2}.SP:=p∈P∑p21(note SP<1),TP:=p∈/P, p=5∑p21.
Given kkk integers a1,…,aka_1,\dots,a_ka1,…,ak and a 25‑class ttt, define

Ui:=⋃p∈PCp(ai;t)(1≤i≤k).\mathcal U_i:=\bigcup_{p\in P} C_p(a_i;t)\qquad(1\le i\le k).Ui:=p∈P⋃Cp(ai;t)(1≤i≤k).
By Fact 1–2, each Ui\mathcal U_iUi has relative density exactly SPS_PSP inside StS_tSt.

: 

Proof. For each function f:{1,…,k}→Pf:\{1,\dots,k\}\to Pf:{1,…,k}→P, set

Uf:=⋂i=1kCf(i)(ai;t).\mathcal U_f:=\bigcap_{i=1}^k C_{f(i)}(a_i;t).Uf:=i=1⋂kCf(i)(ai;t).
Then ⋂iUi⊆⋃fUf\bigcap_{i}\mathcal U_i\subseteq \bigcup_f \mathcal U_f⋂iUi⊆⋃fUf. For fixed fff and for each prime ppp, the intersection ⋂i: f(i)=pCp(ai;t)\bigcap_{i:\,f(i)=p}C_p(a_i;t)⋂i:f(i)=pCp(ai;t) is either empty (if two different residue classes are demanded) or a single residue class modulo p2p^2p2; in either case its relative density inside StS_tSt is ≤1/p2\le 1/p^2≤1/p2. By CRT these constraints across different ppp multiply, whence

∣Uf∣∣St∣≤∏p∈P(1p2)1f−1(p)≠∅=∏i=1k1(f(i))2.\frac{|\mathcal U_f|}{|S_t|}\le \prod_{p\in P}\left(\frac1{p^2}\right)^{\mathbf 1_{f^{-1}(p)\ne\varnothing}}
=\prod_{i=1}^k \frac1{(f(i))^2}.∣St∣∣Uf∣≤p∈P∏(p21)1f−1(p)=∅=i=1∏k(f(i))21.
Summing over all fff gives

∣⋃fUf∣∣St∣≤∑f∏i=1k1(f(i))2=(∑p∈P1p2)k=(SP)k,\frac{\Bigl|\bigcup_f \mathcal U_f\Bigr|}{|S_t|}
\le \sum_f \prod_{i=1}^k \frac{1}{(f(i))^2}=\left(\sum_{p\in P}\frac{1}{p^2}\right)^k=(S_P)^k,∣St∣⋃fUf≤f∑i=1∏k(f(i))21=p∈P∑p21k=(SP)k,
and the o(1)o(1)o(1) accounts for the O(1)O(1)O(1) boundary error when restricting to [1,N][1,N][1,N]. ∎

The primes outside PPP contribute at most TPT_PTP to the obstruction for each fixed aia_iai. Therefore the set of b∈Stb\in S_tb∈St for which “for every iii the square divisor that certifies (⋆)(\star)(⋆) comes from a prime outside PPP” has relative density at most TPT_PTP (indeed, it is ≤min⁡iTP=TP\le\min_i T_P=T_P≤miniTP=TP). Combining this with (2.1) yields the uniform covering inequality:

: 

Two important remarks.
* We did not assume any randomness; (2.2)(2.2)(2.2) is worst‑case, valid even if the residue classes Cp(ai;t)C_p(a_i;t)Cp(ai;t) line up adversarially.
* We excluded p=5p=5p=5 from PPP because in the cross‑class situations we analyse below the congruence 25∣ab+125\mid ab+125∣ab+1 is impossible; omitting it only makes the upper bound stronger.

Finally, since ∑p≠51/p2<1\sum_{p\ne5}1/p^2<1∑p=51/p2<1, we can make the “tail”
TPT_PTP as small as we please by enlarging PPP, while SP<1S_P<1SP<1 always.

==== For each residue class r(mod25)r\pmod{25}r(mod25), pick any kkk-tuple a1,…,aka_1,\dots,a_ka1,…,ak from ArA_rAr. ====

===== Fix two classes r≠sr\ne sr=s with s≢−r−1 ( mod 25)s\not\equiv -r^{-1}\ (\bmod 25)s≡−r−1 (mod25) (so 25∤ab+125\nmid ab+125∤ab+1 when a≡r, b≡sa\equiv r,\ b\equiv sa≡r, b≡s). Applying (2.2)(2.2)(2.2) with t=st=st=s we get, for any finite PPP, =====

αs ≤ (SP)k+TP+o(1)for every k≤∣Ar∣.\alpha_s\ \le\ (S_P)^k+T_P+o(1)\qquad\text{for every }k\le |A_r|.αs ≤ (SP)k+TP+o(1)for every k≤∣Ar∣.
Let ε>0\varepsilon>0ε>0. Choose PPP so large that TP<εT_P<\varepsilonTP<ε, and then let k→∞k\to\inftyk→∞.
If αr\alpha_rαr has a positive lower limit, then kkk can be taken ≫N\gg N≫N, so (SP)k→0(S_P)^k\to0(SP)k→0. Hence

αs ≤ ε+o(1).\alpha_s\ \le\ \varepsilon+o(1).αs ≤ ε+o(1).
Because ε\varepsilonε was arbitrary, we deduce:

: 

In particular, at most one residue class modulo 252525 can have positive density.

===== Take s=rs=rs=r. If r∉{7,18}r\notin\{7,18\}r∈/{7,18}, then r≢−r−1 ( mod 25)r\not\equiv -r^{-1}\ (\bmod 25)r≡−r−1 (mod25) and Claim A applied with s=rs=rs=r forces αr=o(1)\alpha_r=o(1)αr=o(1). Thus: =====

: 

(Indeed, exactly for these two classes we have r2≡−1(mod25)r^2\equiv-1\pmod{25}r2≡−1(mod25), so the prime 555 alone certifies all within‑class pairs (a,b)(a,b)(a,b).)

===== Finally consider r=7, s=18r=7,\ s=18r=7, s=18. Here ab+1≡2(mod25)ab+1\equiv 2\pmod{25}ab+1≡2(mod25), so p=5p=5p=5 cannot help. Applying Claim A with r=7, s=18r=7,\ s=18r=7, s=18 shows that if α7\alpha_7α7 has a positive lower limit then α18=o(1)\alpha_{18}=o(1)α18=o(1); by symmetry the converse also holds. Therefore: =====

: 

Combining B and C, AAA is, up to o(N)o(N)o(N) elements, contained in one of the two classes r∈{7,18}r\in\{7,18\}r∈{7,18}. This immediately gives

∣A∣ ≤ ∣Sr∣+o(N) = N25+o(N),|A|\ \le\ |S_r|+o(N)\ =\ \frac{N}{25}+o(N),∣A∣ ≤ ∣Sr∣+o(N) = 25N+o(N),
and the extremal examples A=S7A=S_7A=S7 and A=S18A=S_{18}A=S18 (for which 25∣ab+125\mid ab+125∣ab+1 for all pairs) show the bound is sharp. This also proves the claimed structural stability.

==== The proof above used an arbitrary finite set P⊂{p≠5}P\subset\{p\ne5\}P⊂{p=5}; choosing PPP cleverly improves constants inside the argument: ====
* If, say, AAA has many elements ≡7(mod25)\equiv7\pmod{25}≡7(mod25) and the complementary part of AAA misses a residue class modulo 333, then in the covering lemma we may simply forbid p=3p=3p=3 from being used (for those bbb), which strictly decreases the tail TPT_PTP. This is exactly the observation you made.
* Likewise, if you restrict PPP to primes p≡1(mod4)p\equiv1\pmod4p≡1(mod4) (excluding 555), the sum ∑p∈P1p2\sum_{p\in P}\tfrac1{p^2}∑p∈Pp21 is smaller; the price is that the tail TPT_PTP is larger. You can then combine both tricks—exclude a few small p≡3(mod4)p\equiv3\pmod4p≡3(mod4) by a congruence‑class choice (e.g. mod 333), and let PPP contain many 1(mod4)1\pmod 41(mod4) primes—to achieve very small SPS_PSP and very small TPT_PTP. That only strengthens the inequality (2.2)(2.2)(2.2). (Numerically, ∑p≡1(4), p>51/p2\sum_{p\equiv1(4),\,p>5}1/p^2∑p≡1(4),p>51/p2 is indeed quite small; but the proof above never needs any numerical estimate beyond SP<1S_P<1SP<1 and TP→0T_P\to0TP→0.)

==== Previously I used the fact that for a single aaa a positive fraction (δ=∏p≠5(1−1/p2)=25/(4π2)\delta=\prod_{p\ne5}(1-1/p^2)=25/(4\pi^2)δ=∏p=5(1−1/p2)=25/(4π2)) of b∈Stb\in S_tb∈St give ab+1ab+1ab+1 squarefree. That does not by itself control how AsA_sAs could be arranged adversarially (it might live entirely inside the “bad” set for that particular aaa). ====

The new Lemma 2.1 and Corollary 2.2 handle the simultaneous constraints imposed by many different aaa’s: every time we add another aia_iai, the set of bbb that can still satisfy “∃p∈P\exists p\in P∃p∈P with p2∣aib+1p^2\mid a_i b+1p2∣aib+1” shrinks by a multiplicative factor ≤SP\le S_P≤SP, uniformly and without independence assumptions. Since SP<1S_P<1SP<1 and we can take k→∞k\to\inftyk→∞ if one 25‑class contains ≫N\gg N≫N elements, the intersection becomes negligible, forcing all other residue classes to be o(N)o(N)o(N).

===== The inclusion–exclusion you had in mind does yield the full extremal result once we organize it via the uniform covering inequality (2.2): it shows that the only asymptotically extremal sets are a single 252525-class r∈{7,18}r\in\{7,18\}r∈{7,18}, and hence the sharp upper bound is ∣A∣≤N/25+o(N)|A|\le N/25+o(N)∣A∣≤N/25+o(N). =====

If you’d like, I can also write the same argument with explicit, fully effective constants (choose a concrete PPP, say P={2,3,7,11,13,…,P0}P=\{2,3,7,11,13,\dots, P_0\}P={2,3,7,11,13,…,P0}, compute SP,TPS_P,T_PSP,TP and the exact kkk needed); but the qualitative stability—“one 25‑class survives, all others are o(N)o(N)o(N)”—is already proved above.