Skip to content

Erdős problem 202

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

Sources

Browse retained paths and inspect the exact material available for this Problem.

2 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

202.lean

Retained formal statement1 of 2

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

Let f(N)f(N) be the maximum possible rr, and let L(N)=exp(logNloglogN)L(N)=\exp(\sqrt{\log N\log\log N}).

This was proved by GPT-5.4 Pro (prompted by Ho Boon Suan), using the argument of [BFV13] together with the resolution of the Kahn-Kalai conjecture by Park and Pham [PaPh24], so that f(N)=NL(N)1+o(1).f(N)= N L(N)^{-1+o(1)}.

FormalConjectures/ErdosProblems/202.leanErdos202.erdos_2021 lineExact file
o, o =o[Filter.atTop] 1 ∧ ∀ᶠ (N : ℕ) in Filter.atTop, ↑(Erdos202.f N) = ↑N * scaleL N ^ (-1 + o N)
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Search problems.science

Find a Problem, Result, source, or page