Wiki
Wiki

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

Updated


Source. Equation (2), printed p. 85 (PDF p. 1). The paper attributes the upper bound to its reference [3]: P. Erdős, Számelméleti megjegyzések IV, Matematikai Lapok 13 (1962), 241–243. That original proof is not reconstructed in this source unit.

Imported statement. A disjoint system with k≥1k\ge1 distinct proper moduli 2≤n1<⋯<nk2\le n_1<\cdots<n_k satisfies

∑i=1k1ni≤1−2−k.(1)\sum_{i=1}^k\frac1{n_i}\le1-2^{-k}. \tag{1}

The weak inequality is what the PDF prints. Modulus one must be excluded: its single progression would violate (1).

Sharpness example. For 1≤i≤k1\le i\le k, take the class 2i−1(mod2i)2^{i-1}\pmod{2^i}. A member has exact 2-adic valuation i−1i-1, so these classes are pairwise disjoint. Their distinct proper moduli have reciprocal sum ∑i=1k2−i=1−2−k\sum_{i=1}^k2^{-i}=1-2^{-k}. Thus equality is attained.

This verifies the source's sharpness remark only. It is not a proof of the upper bound for arbitrary systems. Equation (1) is not an input to the complete proof of f(x)=o(x)f(x)=o(x) on Theorem 1. The source's separate cited impossibility of a distinct-modulus disjoint covering is likewise an external historical result.

Bears on. The reciprocal-sum background for Problem 1190. This finite-kk bound is not the later optimized tail estimate in that problem.