On a problem concerning congruence systems
The celebrated theorem of \textit{N. P. Romanov} [Math. Ann. 109, 668--678 (1934; Zbl 0009.00801; JFM 60.0131.03)] that the positive integers expressible in the form \(2^k+p\), \(p\) an odd prime, have positive density, motivated him to ask P. Erdős whether every sufficiently large odd number is of this form. Erdős immediately proved the contrary, that there is an infinite arithmetic sequence of odd positive integers none of which can be represented in this form. Essential ingredient of his proof was the construction of a finite system of congruences (1) \(a_i\pmod{n_i}\), \(i=1,2,\ldots,k\), such that every (positive) integer satisfies at least one of them. Such a system is nowadays called a covering system. The proof employed Bang's theorem about the primitive prime divisor, and from that reason the moduli \(n_i\) are required to be \(\neq 6\) and distinct in the proof (for the several lines essence of the proof consult \textit{P. Erdős}' paper [Summa Brasil. Math. 2, 113--123 (1950; Zbl 0041.36808)]). He also observed that if it is possible to find a covering system with distinct moduli and arbitrarily large minimal modulus (the so-called Erdős conjecture; see also the reviewer's booklet [``Results and problems on covering systems of residue classes, Mitt. Math. Semin. Gießen 150 (1981; Zbl 0479.10032)]), then for every positive \(r\geq 1\) there is an infinite arithmetic sequence of odd positive integers of the form \(2^k+a_r\), where \(a_r\) has \(\leq r\) prime divisors. Erdős' conjecture was proved by \textit{B. Hough} [Ann. Math. (2) 181, No.1, 361--382 (2015; Zbl 1344.11015)]. \N\NIn the paper there is also the (analytical) proof given independently by Mirsky, Newman, Davenport and Radó that in a disjoint (also called exactly) covering system we have at least two congruences with respect the same modulus (the proof gives that these are maximal ones in the magnitude). For the idea of the proof and the extension of this result to an arbitrary system of congruences and to the so-called divmax moduli see the reviewer's papers [Acta Arith. 26, 223--231 (1975; Zbl 0268.10044)] and with \textit{Y. Chen} [Acta Arith. 71, No. 1, 1--10 (1995; Zbl 0823.11003)] and the paper cited there; for an elementary proof the papers by \textit{M. A. Berger} et al. [Combinatorica 6, 235--243 (1986; Zbl 0608.10006); Discrete Math. 65, 23--46 (1987; Zbl 0623.10003)]. This result implies that if (1) is a covering system with distinct moduli then \(\displaystyle\sum_{i=1}^k n^{-1}_i>1\), what does not hold when (1) is an infinite system. In the finite case the sum of reciprocals of moduli can be arbitrarily close to 1. The author mentions a Davenport opinion that perhaps when the smallest modulus is \(>2\) one can improve the right hand side of this inequality. \N\NFinally the author introduces the notion of a minimal (finite) covering system (in the paper called primitive) as a covering system in which no congruences can be deleted without violating the covering property. He proves that there is only a finite number of minimal covering system of size \(k\), without giving an explicit upper bound for the number. Actually the proof gives a double exponential bound. For improvements see the papers by \textit{P. Balister}et al. [J. Eur. Math. Soc. (JEMS) 26, No. 1, 75--109 (2024; Zbl 1544.11009)] and \textit{J. Klein} et al. [Int. J. Number Theory 20, No. 2, 471--479 (2024; Zbl 1544.11010)].
This page was built for publication: On a problem concerning congruence systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7009843)
