Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Write d(c)=y−xd(c)=y-x, pc=q+d(c)p_c=q+d(c) and w(c)=2y−xw(c)=2y-x for a cell c=(x,y)c=(x,y) of SS. Since dd is injective on SS, the ∣S∣|S| primes pcp_c are distinct. Put K=⌊αP⌋K=\lfloor\alpha P\rfloor.

Size of the primes. From ∣x∣,∣y∣≤ω|x|,|y|\le\omega we get ∣d(c)∣≤2ω|d(c)|\le2\omega, so every pcp_c and PP lie in [q−2ω,q+2ω][q-2\omega,q+2\omega]. The hypothesis (4−α)q≥16ω+1(4-\alpha)q\ge16\omega+1 with 4−α≤14-\alpha\le1 gives q≥16ω+1q\ge16\omega+1. Since 3P3P is an integer and 3P≤αP3P\le\alpha P, we have K≥3PK\ge3P. Hence

K ≥ 3q−6ω ≥ 2q+4ω+1,K ≤ α(q+2ω) ≤ 4q−8ω−1.K\ \ge\ 3q-6\omega\ \ge\ 2q+4\omega+1, \qquad K\ \le\ \alpha(q+2\omega)\ \le\ 4q-8\omega-1 .

The first inequality uses q≥10ω+1q\ge10\omega+1. The second is (4−α)q≥(2α+8)ω+1(4-\alpha)q\ge(2\alpha+8)\omega+1, which follows from the hypothesis because 2α+8<162\alpha+8<16.

The layers. By the Chinese remainder theorem choose zz with z≡−x(modpc)z\equiv-x\pmod{p_c} for every c=(x,y)c=(x,y) in SS. The multiples of pcp_c are then exactly the integers

z+x+tpc  =  z+tq+(1−t)x+ty(t∈Z),z+x+tp_c\;=\;z+tq+(1-t)x+ty\qquad(t\in\mathbb Z),

since x+t(y−x)=(1−t)x+tyx+t(y-x)=(1-t)x+ty. Call this the layer-tt multiple of cc. With ∣x∣,∣y∣≤ω|x|,|y|\le\omega its offset from z+tqz+tq is at most (∣1−t∣+∣t∣)ω(|1-t|+|t|)\omega in absolute value. In particular:

  • layer 00 is z+x∈[z−ω,z+ω]z+x\in[z-\omega,z+\omega];
  • layer 11 is z+q+y∈[z+q−ω,z+q+ω]z+q+y\in[z+q-\omega,z+q+\omega];
  • layer 22 is z+2q+w(c)∈[z+2q−3ω,z+2q+3ω]z+2q+w(c)\in[z+2q-3\omega,z+2q+3\omega];
  • every layer t≤−1t\le-1 is at most z−q+3ωz-q+3\omega;
  • every layer t≥3t\ge3 is at least z+3q−5ωz+3q-5\omega.

For the last two, the bound at t=−1t=-1 is z−q+3ωz-q+3\omega and at t=3t=3 it is z+3q−5ωz+3q-5\omega. Moving from tt to t−1t-1 or t+1t+1 changes the position by qq and the offset bound by 2ω<q2\omega<q, so the bounds hold for all t≤−1t\le-1 and all t≥3t\ge3.

The block. Let

L=max⁡(z−q+3ω+1, z+2q+3ω+1−K),J=[L, L+K−1].L=\max\bigl(z-q+3\omega+1,\ z+2q+3\omega+1-K\bigr), \qquad J=[L,\,L+K-1].

We check z−q+3ω+1≤L≤z−ωz-q+3\omega+1\le L\le z-\omega and z+2q+3ω≤L+K−1≤z+3q−5ω−1z+2q+3\omega\le L+K-1\le z+3q-5\omega-1. The two lower bounds hold by the definition of LL. For the two upper bounds, compare each term of the maximum with each upper limit: z−q+3ω+1≤z−ωz-q+3\omega+1\le z-\omega since q≥4ω+1q\ge4\omega+1; z−q+3ω+1≤z+3q−5ω−Kz-q+3\omega+1\le z+3q-5\omega-K since K≤4q−8ω−1K\le4q-8\omega-1; z+2q+3ω+1−K≤z−ωz+2q+3\omega+1-K\le z-\omega since K≥2q+4ω+1K\ge2q+4\omega+1; and z+2q+3ω+1−K≤z+3q−5ω−Kz+2q+3\omega+1-K\le z+3q-5\omega-K since q≥8ω+1q\ge8\omega+1.

Therefore JJ contains every layer 00, 11 and 22 multiple: they lie in [z−ω,z+2q+3ω]⊆J[z-\omega,z+2q+3\omega]\subseteq J. It contains no multiple in a layer t≤−1t\le-1 or t≥3t\ge3, since those lie below LL or above L+K−1L+K-1. So the integers of JJ divisible by some pcp_c are exactly the three sets z+Xz+X, z+q+Yz+q+Y and z+2q+Wz+2q+W.

Counting once. The three sets lie in the disjoint intervals [z−ω,z+ω][z-\omega,z+\omega], [z+q−ω,z+q+ω][z+q-\omega,z+q+\omega] and [z+2q−3ω,z+2q+3ω][z+2q-3\omega,z+2q+3\omega], because q>4ωq>4\omega. Hence JJ contains exactly ∣X∣+∣Y∣+∣W∣|X|+|Y|+|W| integers divisible by at least one pcp_c, each counted once; an integer of JJ divisible by several of the primes is a single element of one of these sets.

Positivity. Replacing zz by z+n∏c∈Spcz+n\prod_{c\in S}p_c preserves every congruence and translates JJ and all layers by the same amount. For nn large, L≥1L\ge1, so JJ is a block of KK consecutive positive integers. This completes the proof.