Erdős Problem #202

Erdős Problem #202

1. FORMAL RESTATEMENT

Let $f(x)$ be the maximum number of pairwise disjoint residue classes $a_q\pmod q$ with distinct positive integer moduli $q\le x$. Determine the asymptotic size of $f(x)$.

2. LITERATURE AND DECLARED INPUTS

The current resolution, recorded on the problem page and written up by Boon Suan Ho with disclosed GPT-5.4 Pro assistance, is \[ f(x)=x\exp\left(-(1+o(1))\sqrt{\log x\log\log x}\right). \] We reconstruct the spread-core improvement of the de la Bretèche--Ford--Vandehey (BFV) descending-chain proof. The older local versions contain elementary lower bounds, not this resolution. This document makes no novelty claim.

The following established inputs remain external: (i) BFV's matching lower bound, (ii) BFV Lemma 3.2 controlling large prime-power exponent products, and (iii) Park--Pham's expectation-threshold theorem. All reductions from these inputs, including the uniform error calculation, are supplied below.

Put $X=\log x$, $Y=\log\log x$, $M=\sqrt{X/Y}$, $Z=\sqrt{XY}$, and $L(\alpha,x)=e^{\alpha Z}$. Write $h(n)=\prod_{p^\nu\parallel n}\nu$ and $\omega(n)=\#\{p:p\mid n\}$. The BFV inputs have the precise forms \[ f(x)\ge x e^{-(1+o(1))Z},\qquad \#\{n\le x:h(n)>e^{\sqrt X}\}\le x\exp(-\tfrac15\sqrt X\,Y) \tag{1} \] for sufficiently large $x$. In the second exponent $Y$ is outside the square root; this makes the discarded set negligible on the $e^{-Z}$ scale.

3. UNIFORM COUNTING AND PRUNING

Uniformly for $0\le\alpha\le3$ and $2\le y\le x$, \[ \#\{n\le y:\omega(n)\ge\alpha M\} \le y\exp\left((-\alpha/2+o(1))Z\right). \tag{2} \] Here is the Rankin argument. With $s=1+1/X$ and $z=\sqrt X/Y\ge1$, \[ \#\{n\le y:\omega(n)\ge\alpha M\} \le ey z^{-\alpha M}\sum_{n\ge1}\frac{z^{\omega(n)}}{n^s} \le ey z^{-\alpha M}\zeta(s)^z \le ey z^{-\alpha M}(2X)^z. \] The Euler-factor inequality used is $1+z/(p^s-1)\le(1-p^{-s})^{-z}$ for $z\ge1$. Since $\log z=Y/2-\log Y$, the exponent after $y$ is $-\alpha Z/2+O(M\log Y+\sqrt X)=(-\alpha/2+o(1))Z$, uniformly as stated.

Start with an extremal family $Q$ of size $S=f(x)$. Discard $q<xe^{-2Z}$, then those with $\omega(q)>3M$, and those with $h(q)>e^{\sqrt X}$. Equations $1$--$2$ show that each discarded number is $o(S)$. Pigeonhole a common value $\omega(q)=K$, $1\le K\le3M$. Finally retain one modulus for each squarefree kernel. For any given kernel with $K$ primes, the number of exponent choices with product at most $H=e^{\sqrt X}$ is at most \[ \sum_{\nu_1,\ldots,\nu_K\ge1} \frac{H^2}{(\nu_1\cdots\nu_K)^2} =H^2\zeta(2)^K=e^{o(Z)}. \] We obtain $Q'$ of size $S'\ge S e^{-o(Z)}$, with distinct kernels, all $q\ge xe^{-2Z}$, all $h(q)\le e^{\sqrt X}$, and all $\omega(q)=K$. Write $K=dM$, $0<d\le3$.

One consequence of $2$, uniform for integers $0\le W\le K$ and $1\le y\le x$, is \[ \#\{m\le y:\omega(m)=K-W\} \le y e^{(-d/2+o(1))Z}X^{W/2}. \tag{3} \] For $K>W$ apply $2$ with $\alpha=(K-W)/M$; for $K=W$, only $m=1$ is possible and the right side is at least $y$ if the error term is chosen nonnegative. Cases $y<2$ are immediate. This verifies the uniformity needed in the chain rather than assuming a pointwise estimate can be multiplied many times.

4. THE SPREAD-CORE LEMMA

For a family $\mathcal F$ of distinct $k$-element subsets of a finite ground set, write $\mathcal F_T=\{F\in\mathcal F:T\subseteq F\}$. Call it $\kappa$-spread if $|\mathcal F_T|\le|\mathcal F|\kappa^{-|T|}$ for every nonempty $T$.

Park--Pham's theorem says that for a nontrivial increasing family $\mathcal U$, its probability-$1/2$ threshold obeys $p_c(\mathcal U)\le C q(\mathcal U)\log\ell$, where $\ell$ is the maximum of two and the largest minimal-set size. The expectation threshold $q(\mathcal U)$ is the largest $p$ admitting a cover $\mathcal G$ with $\sum_{G\in\mathcal G}p^{|G|}\le1/2$.

For the upward closure of a $\kappa$-spread family, any such cover satisfies \[ |\mathcal F|\le\sum_{G\in\mathcal G}|\mathcal F_G| \le|\mathcal F|\sum_{G\in\mathcal G}\kappa^{-|G|}. \] An empty cover set already has cost one. Hence $q(\mathcal U)\le1/\kappa$, and $p_c(\mathcal U)\le C\log(ek)/\kappa$. If $\kappa=C_0\log(eK)$ with $C_0$ sufficiently large and $k\le K$, a random four-way partition of the ground set has each part containing a member with probability at least $1/2$. The expected number of successful parts is at least two, so some partition contains two disjoint members.

Consequently every nonempty intersecting $k$-uniform family, $1\le k\le K$, has a nonempty set $T$ with \[ |\mathcal F_T|>|\mathcal F|(C_0\log(eK))^{-|T|}. \tag{4} \] Otherwise it would be spread and could not be intersecting.

5. THE EXACT PRIME-POWER CHAIN

Initially let $D_0=1$, $Q'_0=Q'$. At a stage we have a nonempty subfamily $Q'_{r-1}$ whose moduli contain the same exact prime-power product $D_{r-1}$, no prime of $D_{r-1}$ divides their quotients, and their residues agree modulo $D_{r-1}$.

If primes remain in the quotients, their supports form a uniform family of distinct nonempty sets, because the original squarefree kernels were distinct. They are intersecting: disjoint remaining supports would make the gcd of two moduli divide $D_{r-1}$; their equal residues there would force their residue classes to intersect by CRT.

Choose a core of $w_r\ge1$ primes by $4$. Group the surviving moduli by their exact prime-power product on this core. Weight a possible product $P$ by $h(P)^{-2}$. The sum of all these weights is $\zeta(2)^{w_r}$. Weighted pigeonholing therefore yields an attained product $P_r$ and a family $Q_r$ with \[ |Q_r|>\frac{|Q'_{r-1}|}{\Lambda^{w_r}h(P_r)^2},\qquad \Lambda=\zeta(2)C_0\log(eK). \] Keep a most frequent residue modulo $P_r$ to obtain $Q'_r$ of size at least $|Q_r|/P_r$, and set $D_r=D_{r-1}P_r$. The products $P_r$ are pairwise coprime, with their complete prime powers removed at each stage, so all invariants persist. Writing $W_r=\sum_{j\le r}w_j$, after $R\le K$ stages we have $W_R=K$ and a single surviving modulus $D_R\ge xe^{-2Z}$.

Iterating the losses, and using $h(D_r)\le e^{\sqrt X}$, gives \[ |Q_r|>\frac{S'}{D_{r-1}\Lambda^{W_r}h(D_r)^2}. \] On the other hand each modulus in $Q_r$ equals $D_rm$ with $\omega(m)=K-W_r$ and $m\le x/D_r$. Equation $3$ gives \[ |Q_r|\le\frac{x}{D_r}e^{(-d/2+o(1))Z}X^{W_r/2}. \] Comparison yields, uniformly in $r$, \[ P_r\le\frac{x}{S'}e^{(-d/2+o(1))Z} X^{W_r/2}\Lambda^{W_r}e^{2\sqrt X}. \tag{5} \]

6. OPTIMISATION

Write $S'=xe^{-\sigma Z}$ with $\sigma\ge0$, and $R=cM$ with $0<c\le d\le3$. Set $T=\sum_{r=1}^R W_r$. Since each $w_r\ge1$ and their total is $K$, \[ T=\sum_{j=1}^R(R-j+1)w_j\le RK-\frac{R^2}2+\frac R2. \tag{6} \] Multiply $5$, use $D_R\ge xe^{-2Z}$, take logarithms and divide by $X=MZ=M^2Y$. The cumulative errors are $Ro(Z)=o(X)$ by uniformity. Also $T=O(M^2)$, $\log\Lambda=O(\log Y)=o(Y)$, and $R\sqrt X=o(X)$. Therefore $6$ gives \[ 1+o(1)\le c(\sigma-d/2)+cd/2-c^2/4+o(1) =c\sigma-c^2/4+o(1)\le\sigma^2+o(1). \] Thus $\sigma\ge1-o(1)$, so $S'\le xe^{-(1-o(1))Z}$, and the pruning loss gives the same upper bound for $f(x)$. Combining with $1$ proves the claimed asymptotic.

7. FINAL AND VERIFICATION

SOLVED: reconstruction of the known asymptotic, relative to the three declared external inputs. The prime-power weights, distinct-kernel condition, residue losses and repeated uniform errors are all retained. The proof does not assume squarefree moduli and does not substitute a fixed-parameter sunflower assertion for a growing-parameter estimate. BFV's lower construction and exceptional-exponent estimate, and Park--Pham's theorem, remain cited inputs rather than proofs supplied here.

8. SOURCES

Current statement: https://www.erdosproblems.com/202. B. S. Ho, Non-intersecting arithmetic progressions via spread cores, https://boonsuan.github.io/erdos202.pdf. R. de la Bretèche, K. Ford and J. Vandehey, On non-intersecting arithmetic progressions, Acta Arithmetica 157 $2013$, 381--392, https://www.ford126.web.illinois.edu/wwwpapers/NAP.pdf, Theorem 1, Lemmas 3.1--3.3 and Section 4.1. J. Park and H. T. Pham, A proof of the Kahn--Kalai conjecture, https://arxiv.org/abs/2203.17207, Theorem 1.1.

COMPLETION ESTIMATE

COMPLETION: 100%

Erdős Problem #202

1) ROUND-2 OBJECTIVE

Path pursued: (C)-style obstruction sharpening / strict advance without a full resolution.

Round 1 already identified that the main gap is the true asymptotic order of \[ f(N):=\max\{r:\text{ there exist pairwise disjoint congruence classes }a_i \pmod{n_i},\ 2\le n_1<\cdots<n_r\le N\}. \] The most promising Round 2 move is therefore not to restart the global asymptotic problem, but to prove a new unconditional theorem that is substantially stronger than the Round 1 elementary lower bound, and then place it against the current best-known asymptotic bounds from the literature.

The concrete target in this round is to improve the Round 1 elementary lower bound \[ f(N)\ge \lfloor \log_2 N\rfloor \] to the polynomial lower bound \[ f(N)\ge \lfloor \sqrt{N}\rfloor, \] with a completely self-contained proof.

2) Round-1 FOUNDATION USED

I use only the following Round 1 items.

• The formal definition of $f(N)$.
• The disjointness criterion: two classes $a \pmod m$ and $b \pmod n$ are disjoint if and only if \[ a\not\equiv b \pmod{\gcd(m,n)}. \]
• The Round 1 status: the full asymptotic problem remained unresolved.

I do not reuse the Round 1 proof of the logarithmic lower bound, except as a benchmark to improve upon.

3) NEW INSIGHT / TOOL (ROUND-2)

The new observation is that there is a very simple "ladder" construction with a common scale $M$: \[ 1 \pmod M,\qquad 2 \pmod{2M},\qquad 3 \pmod{3M},\qquad \ldots,\qquad r \pmod{rM}. \] If $r\le M$, then any two residues differ by a number strictly between $0$ and $M$, while the gcd of the corresponding moduli is always a multiple of $M$. This immediately forces disjointness.

Optimizing the choice of $M$ gives $r\asymp \sqrt{N}$.

4) ATTACK PLAN (ROUND-2)

The exact remaining gap after Round 1 was that the only fully proved lower bound in the write-up was logarithmic, while the actual problem asks for asymptotic growth much closer to linear.

In this round I will prove the following two statements.

1. For integers $M\ge 2$ and $1\le r\le M$, the congruence classes \[ x\equiv j \pmod{Mj}\qquad (1\le j\le r) \] are pairwise disjoint.

2. As a corollary, for every $N\ge 2$, \[ f(N)\ge \lfloor \sqrt N\rfloor. \]

This overcomes the specific Round 1 weakness that the only fully proved lower bound was logarithmic.

5) WORK (ROUND-2)

Theorem 5.1.

Let $M\ge 2$ and let $1\le r\le M$. Then the congruence classes \[ \mathcal{C}_j:=\{x\in \mathbf{Z}: x\equiv j \pmod{Mj}\}\qquad (1\le j\le r) \] are pairwise disjoint.

Proof.

Take $1\le i<j\le r$. By the Round 1 disjointness criterion, it is enough to show that \[ i\not\equiv j \pmod{\gcd(Mi,Mj)}. \] Now \[ \gcd(Mi,Mj)=M\gcd(i,j). \] So if the two classes intersected, we would have \[ M\gcd(i,j)\mid (j-i). \] But since $1\le i<j\le r\le M$, we have \[ 0<j-i<M. \] On the other hand, \[ M\gcd(i,j)\ge M. \] A positive integer strictly smaller than $M$ cannot be divisible by an integer at least $M$, so \[ M\gcd(i,j)\nmid (j-i). \] Hence \[ i\not\equiv j \pmod{\gcd(Mi,Mj)}, \] and therefore $\mathcal{C}_i\cap \mathcal{C}_j=\emptyset$.

Since this holds for every pair $i<j$, the family $\mathcal{C}_1,\dots,\mathcal{C}_r$ is pairwise disjoint. $\square$

Corollary 5.2.

For every $N\ge 4$, \[ f(N)\ge \lfloor \sqrt N\rfloor. \]

Proof.

Let \[ M:=\lfloor \sqrt N\rfloor. \] Then $M\ge 2$ and $M^2\le N$. Apply Theorem 5.1 with $r=M$. The resulting moduli are \[ M,\,2M,\,3M,\,\dots,\,M^2, \] which are distinct and all at most $N$. Therefore there are at least $M$ pairwise disjoint congruence classes with distinct moduli not exceeding $N$, so \[ f(N)\ge M=\lfloor \sqrt N\rfloor. \] $\square$

Small-$N$ completion.

For $N=2,3$ one has $f(N)=1$, so the same inequality \[ f(N)\ge \lfloor \sqrt N\rfloor \] also holds there. Thus the bound is valid for every $N\ge 2$.

Concrete example.

For $N=100$, taking $M=10$ yields the ten pairwise disjoint classes \[ 1 \pmod{10},\ 2 \pmod{20},\ 3 \pmod{30},\ \dots,\ 10 \pmod{100}. \] Hence \[ f(100)\ge 10. \]

Placement against the best current asymptotic bounds.

The present theorem is not competitive with the best known asymptotic lower bound. The currently recorded best bounds are \[ \frac{N}{L(N)^{1+o(1)}}<f(N)<\frac{N}{L(N)^{\sqrt 3/2+o(1)}}, \qquad L(N):=\exp\!\big(\sqrt{\log N\log\log N}\big), \] due to de la Bretèche, Ford, and Vandehey, refining earlier work of Croot and Chen.

I am using this only as a checked external benchmark; the new theorem proved above is independent of those deep results.

6) ADVERSARIAL VERIFICATION

I now try to break the new argument.

(i) Are the moduli distinct?

Yes. They are $M,2M,\dots,rM$, and these are strictly increasing because $1,2,\dots,r$ are.

(ii) Are the residues legitimate representatives?

Yes. For each $j\ge 1$, \[ 0<j<Mj, \] so $j$ is a valid residue modulo $Mj$.

(iii) Is the use of the disjointness criterion correct?

Yes. The criterion is exactly the Round 1 lemma: \[ a \pmod m \text{ and } b \pmod n \text{ intersect } \Longleftrightarrow a\equiv b \pmod{\gcd(m,n)}. \] I used it with $(a,m)=(i,Mi)$ and $(b,n)=(j,Mj)$.

(iv) Is the inequality $0<j-i<M$ really guaranteed?

Yes, because the construction is only claimed for $r\le M$. This restriction is essential. If one tried to continue past $r=M$, the difference $j-i$ could become divisible by $M$, and the argument would fail.

(v) Does the corollary really keep every modulus $\le N$?

Yes. The largest modulus is $M^2$, and $M=\lfloor \sqrt N\rfloor$ implies $M^2\le N$.

(vi) Does this solve the original asymptotic problem?

No. It only gives a self-contained polynomial lower bound. The asymptotic order of $f(N)$ remains open.

No hidden quantifier issue remains in the proof above.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advance over Round 1 is the new unconditional theorem \[ f(N)\ge \lfloor \sqrt N\rfloor \qquad (N\ge 2), \] proved here from scratch. This is much stronger than the Round 1 elementary bound $f(N)\ge \lfloor \log_2 N\rfloor$.

The global asymptotic problem remains open. The currently recorded best asymptotic bounds are \[ \frac{N}{L(N)^{1+o(1)}}<f(N)<\frac{N}{L(N)^{\sqrt 3/2+o(1)}}. \]

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #202, erdosproblems.com, accessed 2026-03-07.
2. R. de la Bretèche, K. Ford, and J. Vandehey, On non-intersecting arithmetic progressions, Acta Arith. 157 $2013$, 381--392.

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$).