Problem 202

Let $n_1<\cdots < n_r\leq N$ with associated $a_i\pmod{n_i}$ such that the congruence classes are disjoint (that is, every integer is $\equiv a_i\pmod{n_i}$ for at most one $1\leq i\leq r$ ). How large can $r$ be in terms of $N$ ?

Source: erdosproblems.com/202

Covering systems

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

SOLVED (LEAN). The answer is known at the sharp logarithmic scale. Put $S(N)=\sqrt{\log N\log\log N}$ for $N>e$ , using natural logarithms. Then

f(N)=N\exp\bigl(-(1+o(1))S(N)\bigr).

Precisely, for every real $\eta>0$ there is $N_0(\eta)$ such that every integer $N\ge N_0(\eta)$ satisfies

N e^{-(1+\eta)S(N)}\le f(N)\le N e^{-(1-\eta)S(N)}.

This identifies the leading coefficient in the exponent. It does not assert $f(N)\sim N e^{-S(N)}$ or an exact formula at every finite $N$ . The ordinary proof is Ho's Theorem 1.1. The public formalization and verification evidence are described below, and the acceptance evidence is recorded on Ho's claim page (2026).

BFV13: de la Bretèche, Régis and Ford, Kevin and Vandehey, Joseph, On non-intersecting arithmetic progressions. Acta Arith. (2013), 381-392.
Ch05: Chen, Yong-Gao, On disjoint arithmetic progressions. Acta Arith. (2005), 143-148.
Cr03b: Croot, III, Ernest S., On non-intersecting arithmetic progressions. Acta Arith. (2003), 233-238.
ErSz68: Erdős, P. and Szemerédi, E., On a problem of P. Erdős and S. Stein. Acta Arith. (1968), 85-90.
PaPh24: Park, Jinyoung and Pham, Huy Tuan, A proof of the Kahn-Kalai conjecture. J. Amer. Math. Soc. (2024), 235-243.
Ho26: Ho, Boon Suan, Non-intersecting arithmetic progressions via spread cores. Author manuscript (2026), selected 3 May PDF.

Problem 202

Status

Proof claims

Discussion