gpt pro 5.2 attempt on Math-5493

Erdős Problem #202

1. FORMAL RESTATEMENT

Let $n_1<\cdots<n_r\le N$ be distinct integers and let $a_i\in\{0,1,\dots,n_i-1\}$. Consider the congruence classes (infinite arithmetic progressions) \[ \mathcal{C}_i \;:=\; \{x\in\mathbb{Z}:\ x\equiv a_i\pmod{n_i}\}. \] We say the classes are pairwise disjoint if $\mathcal{C}_i\cap\mathcal{C}_j=\emptyset$ for all $i\ne j$. Define \[ f(N) := \max\left\{r:\ \exists\ (n_i,a_i)_{i=1}^r\text{ with }2\le n_1<\cdots<n_r\le N\text{ and }\mathcal{C}_i\text{ pairwise disjoint}\right\}. \] The problem asks for the asymptotic growth of $f(N)$ as $N\to\infty$.

2. PHASE 1 --- FAST REALITY CHECK

• Sanity about feasibility. If $\gcd(m,n)=1$, then for any residues $a\pmod m$, $b\pmod n$ the system $x\equiv a\pmod m$, $x\equiv b\pmod n$ has a solution (CRT), hence cannot be disjoint. Thus all chosen moduli must be pairwise non-coprime.

• Exact values for small $N$ (computed by brute force backtracking). The following values were computed exactly: \[ \begin{array}{c|cccccccccccccccccccc} N &2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21\\\hline f(N) &1&1&2&2&2&2&3&3&3&3&4&4&4&4&5&5&6&6&6&6 \end{array} \] and additionally $f(22)=6$, $f(23)=6$, $f(24)=7$, $f(25)=7$, $f(26)=7$.

• Example achieving $f(18)=6$. One optimal system for $N=18$ is \[ (18,0),\ (16,1),\ (12,2),\ (8,5),\ (6,4),\ (4,3), \] meaning the six classes $x\equiv 0\ (18)$, $x\equiv 1\ (16)$, $x\equiv 2\ (12)$, $x\equiv 5\ (8)$, $x\equiv 4\ (6)$, $x\equiv 3\ (4)$.

3. KEY DEFINITIONS / LEMMAS

1. Intersection criterion. Two classes $x\equiv a\pmod m$ and $x\equiv b\pmod n$ intersect iff \[ a\equiv b\pmod{\gcd(m,n)}. \] Equivalently, they are disjoint iff $a\not\equiv b\pmod{\gcd(m,n)}$.

2. Density bound. If $\mathcal{C}_1,\dots,\mathcal{C}_r$ are pairwise disjoint, then \[ \sum_{i=1}^r \frac{1}{n_i}\le 1. \] (Each class has natural density $1/n_i$ and disjoint unions add densities.)

3. A simple explicit lower bound. For every $t\ge 1$, the following $t$ classes are pairwise disjoint: \[ x\equiv a_i \pmod{2^i},\qquad a_i:=2^{i-1}-2\ \ (\text{reduced mod }2^i),\qquad i=1,2,\dots,t. \] Hence $f(N)\ge \lfloor\log_2 N\rfloor$.

4. WORK (Main proof or counterexample)

Lemma 3.1 (intersection criterion).

Claim. The congruences $x\equiv a\pmod m$ and $x\equiv b\pmod n$ have a simultaneous solution iff $a\equiv b\pmod{g}$ where $g=\gcd(m,n)$.

Proof. If $x\equiv a\pmod m$ and $x\equiv b\pmod n$, then $x-a$ is a multiple of $m$ and $x-b$ is a multiple of $n$, hence $(x-a)-(x-b)=b-a$ is a multiple of $g$, i.e. $a\equiv b\pmod g$. Conversely, if $a\equiv b\pmod g$, write $m=gm'$, $n=gn'$ with $\gcd(m',n')=1$. Then $a=b+gt$ for some $t$, and solving \[ b+gt\equiv a\equiv x\pmod{gm'}\quad\text{and}\quad x\equiv b\pmod{gn'} \] reduces to a standard CRT instance modulo $gm'n'$ because the congruences are compatible mod $g$ and coprime after factoring out $g$. Thus a solution exists. $\square$

Lemma 3.2 (density bound).

Claim. If the classes $\mathcal{C}_i = a_i\pmod{n_i}$ are pairwise disjoint, then $\sum_i 1/n_i\le 1$.

Proof. Fix $M\in\mathbb{N}$ and consider the interval $[1,M]$. Each class $\mathcal{C}_i$ hits $[1,M]$ in either $\lfloor M/n_i\rfloor$ or $\lceil M/n_i\rceil$ points, hence in at least $M/n_i-1$ points. Since the classes are disjoint, \[ M \ge \sum_{i=1}^r \left|\mathcal{C}_i\cap[1,M]\right| \ge \sum_{i=1}^r \left(\frac{M}{n_i}-1\right)= M\sum_{i=1}^r\frac{1}{n_i}-r. \] Rearranging gives $\sum_i 1/n_i \le 1 + r/M$. Letting $M\to\infty$ yields $\sum_i 1/n_i\le 1$. $\square$

Lemma 3.3 (explicit construction giving $f(N)\ge\lfloor\log_2 N\rfloor$).

Claim. For each $t\ge 1$, the $t$ classes \[ \mathcal{C}_i:\ x\equiv a_i\pmod{2^i},\qquad a_i:=2^{i-1}-2\pmod{2^i},\quad (i=1,\dots,t) \] are pairwise disjoint.

Proof. Take $1\le i<j\le t$. By Lemma 3.1, $\mathcal{C}_i$ and $\mathcal{C}_j$ are disjoint iff $a_i\not\equiv a_j\pmod{2^i}$ (since $\gcd(2^i,2^j)=2^i$). Compute $a_j=2^{j-1}-2\equiv -2\pmod{2^i}$ because $j-1\ge i$ makes $2^{j-1}$ divisible by $2^i$. Meanwhile $a_i\equiv 2^{i-1}-2\pmod{2^i}$. Thus \[ a_i-(-2)\equiv 2^{i-1}\not\equiv 0\pmod{2^i}, \] so $a_i\not\equiv a_j\pmod{2^i}$. Hence every pair is disjoint. If $2^t\le N$, this yields $t$ disjoint classes with moduli $\le N$, so $f(N)\ge t=\lfloor\log_2 N\rfloor$. $\square$

5. SANITY CHECK

• For $t=3$ the construction gives $1\ (2)$, $0\ (4)$, $2\ (8)$, which are easily checked to be pairwise disjoint.
• The density bound is consistent with the construction: $\sum_{i=1}^t 1/2^i = 1-2^{-t}<1$.
• The computed optimum $f(8)=3$ matches the construction with $t=3$.

6. FINAL

UNRESOLVED.

• (i) Best partial results proved here. We proved:
  1. A necessary and sufficient disjointness condition: $a_i\not\equiv a_j\pmod{\gcd(n_i,n_j)}$.
  2. A general upper bound from densities: $\sum_i 1/n_i\le 1$, implying the trivial $f(N)\le N$.
  3. An explicit infinite family giving $f(N)\ge \lfloor\log_2 N\rfloor$.
  4. Exact values of $f(N)$ for $2\le N\le 26$ by brute force computation.
  In the literature (quoted in the problem statement), substantially stronger bounds are known, of the shape $\frac{N}{L(N)^{1+o(1)}}< f(N) < \frac{N}{L(N)^{\sqrt{3}/2+o(1)}}$ with $L(N)=\exp(\sqrt{\log N\log\log N})$.

• (ii) First gap/obstruction to a full solution. The problem is asking for the true asymptotic order of $f(N)$, i.e. to close (or significantly narrow) the gap between the best known lower and upper bounds. The methods proved above (density, elementary CRT constructions) do not approach the $N/L(N)^{\Theta(1)}$ scale.

• (iii) What would be needed next. To go beyond the elementary bounds one needs the deep connection with sunflower/$\Delta$-system phenomena and the analytic-number-theory constructions used in the known results (Erdős--Szemerédi, Croot, Chen, de la Bretèche--Ford--Vandehey, etc.). A full solution would either (a) prove an essentially matching upper bound to the known construction (the conjectured lower bound), or (b) improve the construction to meet the best upper bound.

7. OPTIONAL: SHARPENING / DISCUSSION

• The disjointness condition forces strong gcd-structure: if $\gcd(n_i,n_j)=1$ for some pair then disjointness is impossible. Thus any near-optimal family must consist of integers with many shared prime factors, which is where sunflower-type structure enters.
• The small-$N$ data suggest $f(N)$ can be noticeably larger than $\lfloor\log_2 N\rfloor$ even for modest $N$ (e.g. $f(18)=6$).