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

==== ### ====

The next step ensures that, for a fixed finite set of primes PPP, we can select many elements of ArA_rAr whose residues modulo p2p^2p2 are all distinct (for each p∈Pp\in Pp∈P). The only input is the size of ArA_rAr; no randomness or distribution assumptions are used.

: 

Proof. Construct aia_iai greedily. Suppose a1,…,ai−1a_1,\dots,a_{i-1}a1,…,ai−1 have been chosen. For each p∈Pp\in Pp∈P there are exactly i−1i-1i−1 “forbidden” residue classes modulo p2p^2p2 (the ones already taken by a1,…,ai−1a_1,\dots,a_{i-1}a1,…,ai−1). By CRT the set of integers in SrS_rSr that hit at least one forbidden residue (for at least one p∈Pp\in Pp∈P) has size

≤∑p∈P(i−1)(∣Sr∣p2+O(1))=(i−1)∣Sr∣SP+O((i−1)∣P∣).\le \sum_{p\in P}(i-1)\Bigl(\frac{|S_r|}{p^2}+O(1)\Bigr)
=(i-1)|S_r|S_P + O\bigl((i-1)|P|\bigr).≤p∈P∑(i−1)(p2∣Sr∣+O(1))=(i−1)∣Sr∣SP+O((i−1)∣P∣).
Hence, provided

∣Ar∣>(i−1)∣Sr∣SP+O((i−1)∣P∣),|A_r|>(i-1)|S_r|S_P + O\bigl((i-1)|P|\bigr),∣Ar∣>(i−1)∣Sr∣SP+O((i−1)∣P∣),
there exists some ai∈Ara_i\in A_rai∈Ar avoiding all forbidden residues, i.e. with residues distinct from the previous choices for every p∈Pp\in Pp∈P. Iterating while this strict inequality holds yields

K ≥ ⌊∣Ar∣∣Sr∣SP+O(∣P∣)⌋.K\ \ge\ \left\lfloor\frac{|A_r|}{|S_r|S_P+O(|P|)}\right\rfloor.K ≥ ⌊∣Sr∣SP+O(∣P∣)∣Ar∣⌋.
Since ∣P∣|P|∣P∣ is fixed while ∣Sr∣≍N|S_r|\asymp N∣Sr∣≍N, the O(∣P∣)O(|P|)O(∣P∣) term is o(∣Sr∣)o(|S_r|)o(∣Sr∣), and (3.1) follows. ∎

===== For a fixed aaa and p∈Pp\in Pp∈P (with p∤ap\nmid ap∤a), let Rp(a;s)R_p(a;s)Rp(a;s) be the unique residue class modulo p2p^2p2 that bbb must occupy for p2∣ab+1p^2\mid ab+1p2∣ab+1 (Lemma 2.1). For KKK integers a1,…,aKa_1,\dots,a_Ka1,…,aK, define =====

BP(a1,…,aK;s):={b∈Ss: ∀i ∃p∈P  s.t.  b≡Rp(ai;s) (mod p2)}.\mathcal B_{P}(a_1,\dots,a_K;s):=\Bigl\{b\in S_s:\ \forall i\ \exists p\in P\ \ \text{s.t.}\ \ b\equiv R_p(a_i;s)\ (\mathrm{mod}\ p^2)\Bigr\}.BP(a1,…,aK;s):={b∈Ss: ∀i ∃p∈P  s.t.  b≡Rp(ai;s) (mod p2)}.
: 

Proof. For each function f:{1,…,K}→Pf:\{1,\dots,K\}\to Pf:{1,…,K}→P, define the intersection

Xf:=⋂i=1K{ b∈Ss: b≡R f(i)(ai;s) (mod f(i)2) }.X_f:=\bigcap_{i=1}^{K}\{\,b\in S_s:\ b\equiv R_{\,f(i)}(a_i;s)\ (\mathrm{mod}\ f(i)^2)\,\}.Xf:=i=1⋂K{b∈Ss: b≡Rf(i)(ai;s) (mod f(i)2)}.
By definition,

BP(a1,…,aK;s)=⋃fXf.\mathcal B_{P}(a_1,\dots,a_K;s)=\bigcup_{f} X_f.BP(a1,…,aK;s)=f⋃Xf.
Fix fff. For a given prime ppp, the congruences

b≡Rp(ai;s) (mod p2)(i∈f−1(p))b\equiv R_p(a_i;s)\ (\mathrm{mod}\ p^2)\qquad (i\in f^{-1}(p))b≡Rp(ai;s) (mod p2)(i∈f−1(p))
have pairwise distinct right–hand sides by assumption; hence if ∣f−1(p)∣≥2|f^{-1}(p)|\ge 2∣f−1(p)∣≥2 the intersection is empty. Thus XfX_fXf is empty unless all values f(1),…,f(K)f(1),\dots,f(K)f(1),…,f(K) are distinct. In that case, CRT implies that XfX_fXf is a single residue class modulo ∏i=1Kf(i)2\prod_{i=1}^K f(i)^2∏i=1Kf(i)2, whence

∣Xf∣∣Ss∣=∏i=1K1f(i)2 + o(1).\frac{|X_f|}{|S_s|}=\prod_{i=1}^K \frac{1}{f(i)^2}\ +\ o(1).∣Ss∣∣Xf∣=i=1∏Kf(i)21 + o(1).
Summing over all injective fff (equivalently, over ordered KKK-tuples of distinct primes p1,…,pK∈Pp_1,\dots,p_K\in Pp1,…,pK∈P) gives

∣BP(a1,…,aK;s)∣∣Ss∣ ≤ ∑(p1,…,pK)∈PKall distinct ∏i=1K1pi2 + o(1).\frac{|\mathcal B_{P}(a_1,\dots,a_K;s)|}{|S_s|}
\ \le\ \sum_{\substack{(p_1,\dots,p_K)\in P^K\\ \text{all distinct}}}\ \prod_{i=1}^K \frac{1}{p_i^{2}}\ +\ o(1).∣Ss∣∣BP(a1,…,aK;s)∣ ≤ (p1,…,pK)∈PKall distinct∑ i=1∏Kpi21 + o(1).
The sum on the right is K! eK({1/p2:p∈P})K!\,e_K\bigl(\{1/p^2: p\in P\}\bigr)K!eK({1/p2:p∈P}), where eKe_KeK is the KKK-th elementary symmetric sum. The standard inequality

K! eK(x1,x2,… ) ≤ (∑jxj)K(3.3)K!\,e_K(x_1,x_2,\dots)\ \le\ \Bigl(\sum_j x_j\Bigr)^K
\tag{3.3}K!eK(x1,x2,…) ≤ (j∑xj)K(3.3)
(“the kkk-term symmetric sum is bounded by the kkk-th power of the 1st symmetric sum”) gives the claim (3.2). ∎

Remark on (3.3). It is immediate from expanding (∑xj)K\bigl(\sum x_j\bigr)^K(∑xj)K and grouping terms: each product of KKK distinct variables appears K!K!K! times; all other terms are nonnegative.