Erdős Problem #280

Erdős Problem #280

Statement and attribution

Suppose $n_1<n_2<\cdots$ and $n_k>(1+\varepsilon)k\log k$ for some $\varepsilon>0$. Must the number of positive integers $m<n_k$ not covered by the first $k$ chosen residue classes fail to be $o(k)$? No. We verify the simple counterexample attributed to Cambie in the current problem discussion. No novelty is claimed.

Work: an exact count of the uncovered integers

Set \[ n_i=2^i,\qquad a_i=2^{i-1}+1\pmod{2^i}. \] For every integer $m\ne1$, the condition $m\equiv a_i\pmod{2^i}$ is equivalent to $v_2(m-1)=i-1$. Consequently, after $k$ classes the uncovered integers are exactly \[ m\equiv1\pmod{2^k}. \] In the range $1\le m<2^k$ the only such integer is $m=1$. Thus the quantity in the question is identically one, which is $o(k)$.

For completeness the growth condition holds even for every $k\ge1$, with natural logarithms and $\varepsilon=1/2$. For $k=1$ it is immediate; $k=2,3$ can be checked directly. For $k\ge4$, $\log k\le k/2$ and $2^k\ge k^2$, so \[ (1+\varepsilon)k\log k\le\frac34k^2<2^k=n_k. \] The bound $2^k\ge k^2$ starts with equality at $k=4$ and follows inductively from $(1+1/k)^2<2$ for $k\ge4$.

Verification and outcome

The single uncovered point remains present at every finite stage. Nevertheless the uncovered count in the particular moving interval $[1,n_k)$ is one. The moduli are strictly increasing and all congruences are well-defined; $a_1=2$ simply represents zero modulo two.

SOLVED: the proposed necessity is false. Both the growth condition and the exact uncovered count have been proved.

Source

Current statement and counterexample attribution: https://www.erdosproblems.com/280.

COMPLETION ESTIMATE

COMPLETION: 100%