A further investigation on covering systems with odd moduli

Technical Summary: A Further Investigation on Covering Systems with Odd Moduli

Problem Statement
The paper addresses the "odd covering problem," a central open question in number theory introduced by Paul Erdős in 1950. An odd covering system is defined as a finite collection of congruences where every integer satisfies at least one congruence, and all moduli are distinct odd integers greater than 1. The existence of such a system remains unproven.

Recent research has focused on variations of this problem, specifically investigating how many times a specific odd integer $k$ can be repeated as a modulus while all other moduli remain distinct odd integers greater than 1. Let $t_k$ denote the smallest nonnegative integer such that there exists a covering system where $k$ appears as a modulus in $t_k$ congruences, and all other moduli are distinct odd integers $>1$. If an odd covering system exists, then $t_k \le 1$ for all odd $k$. Previous work by Harrington, Sun, and Wong established upper bounds for $t_p$ where $p$ is a prime (e.g., $t_p \le p-4$ for $11 \le p \le 19$).

Methodology
The authors employ a combination of constructive combinatorics and modular arithmetic to improve existing bounds on $t_k$.

1. Recursive Construction (Theorem 2.2): The paper introduces a method to generate covering systems with repeated moduli based on existing systems. If a system exists where modulus $k$ is repeated $t$ times, the authors demonstrate how to construct a system where the modulus $km$ is repeated at most $m(t-1)+1$ times (or $(m-1)(t-1)+1$ times if $\gcd(k,m)=1$). This allows the extension of bounds from primes to composite numbers.
2. Tree Diagram Notation: To present complex covering systems, the authors utilize and refine the tree diagram notation established by Harrington, Sun, and Wong. This notation systematically lists moduli as products of subsets of a base set of primes, sorted in a specific order to ensure coverage.
3. Direct Construction: For specific composite numbers ($9, 15, 21, 25$) and large primes ($p \ge 17$), the authors provide explicit constructions of covering systems using tree diagrams. These constructions rely on selecting specific primes $q$ (where $q$ is sufficiently large) to generate the necessary congruences.
4. Subset Covering Application: The paper applies the concept of repeated moduli to derive odd coverings for specific subsets of integers. By constructing a covering system with repeated moduli $k$ at specific residues, the authors show that the complement of these residues can be covered by distinct odd moduli.

Key Contributions and Results
The primary contribution of the paper is the improvement of known upper bounds for $t_k$ for various odd integers $k$. The results are summarized as follows:

• Composite Numbers:
  • $t_9 \le 3$ (Theorem 2.5)
  • $t_{15} \le 4$ (Theorem 2.6)
  • $t_{21} \le 5$ (Theorem 2.7)
  • $t_{25} \le 8$ (Theorem 2.8)
  • For $k=p^2$ where $11 \le p \le 13$, $t_k \le p(p-5)$ (Corollary 2.3).
  • For $k=p^2$ where $p \ge 17$, $t_k \le p(p-6)$ (Theorems 2.2 and 2.4).
• Large Primes:
  • For any prime $p \ge 17$, $t_p \le p-5$ (Theorem 2.4). This improves upon the previous bound of $p-4$ for this range.
  • Crucially, the constructions for $p \ge 17$ do not use $p^2$ as a modulus, allowing for the recursive application of Theorem 2.2.

Applications to Integer Subsets
A significant application of these results is the demonstration that the union of several specific subsets of integers possesses an odd covering. By utilizing the covering system for $t_9 \le 3$ (specifically the residues $0, 3, 6 \pmod 9$), the authors prove that any subset of integers with only finitely many terms outside the set $S = \{a \in \mathbb{Z} : \text{if } 3|a \text{ then } 9|a\}$ has an odd covering.

Consequently, the paper establishes that the following sets (and their unions) have odd coverings:

• Sums of two squares
• Sums of two cubes
• Powerful numbers
• Primes and powers of primes
• Numbers of derangements
• Fermat numbers
• Perfect numbers

Significance and Limitations
The paper claims significance in tightening the bounds on the "repeated modulus" variation of the odd covering problem, moving closer to the threshold where $t_k=1$ for all $k$. The explicit constructions for $t_9 \le 3$ are particularly notable as they enable the covering of complex combinatorial sequences like derangements and sums of cubes.

The authors remain modest regarding the ultimate resolution of the odd covering problem. They note that while their results cover many subsets, they do not yet prove the existence of an odd covering system for the entire set of integers. Furthermore, they highlight open directions, such as whether $t_9$ can be reduced to 2 (which would cover Bell numbers) or whether covering systems exist for other specific residue configurations (e.g., sums of three cubes). The work is presented as a step forward in understanding the structural constraints of covering systems with odd moduli.