🔢 mathematics

A Distinct Covering System with Minimum Modulus 7 and Minimal Least Common Multiple 10080

This paper disproves Klein's conjecture by constructing a distinct covering system with minimum modulus 7 and least common multiple 10080, while simultaneously proving that no such system can exist with a smaller least common multiple through a multi-stage filtering argument and computational verification.

Original authors: Jiheng Zhang, Shiliang Zhang

Published 2026-07-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiheng Zhang, Shiliang Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the number line as an endless highway stretching in both directions, populated by every integer from negative infinity to positive infinity. In the world of mathematics, specifically a branch called number theory, there is a fascinating puzzle about how to "cover" this entire highway using nothing but a set of traffic signs. These signs are called arithmetic progressions. Think of a sign that says, "Every 7th car is a red car," or "Every 12th car is a blue car." If you place enough of these signs at different intervals, you might be able to ensure that every single car on the highway is either red or blue (or some other color). When you manage to cover every single integer with a collection of these repeating patterns, you have created a covering system.

The rules of the game get a little stricter when mathematicians ask for a distinct covering system. This means every sign must have a unique interval; you can't have two signs that both say "every 7th car." You must use different numbers for your intervals, like 7, 8, 9, 10, and so on. A natural question arises: How small can the smallest interval be? For a long time, mathematicians wondered if there was a hard limit to how small this "minimum modulus" could get. Recently, it was proven that there is indeed a limit, but the mystery that remained was about efficiency. If you fix the smallest interval (say, 7), what is the smallest possible "biggest number" (the least common multiple) you need to make the whole system work? It's like asking: if your smallest step is 7 paces, how far do you have to walk before your pattern of steps perfectly lines up with every possible position on the road?

This paper tackles that exact question for the specific case where the smallest interval is 7. The authors, Shiliang Zhang and Jiheng Zhang, set out to find the absolute minimum "biggest number" required to build a distinct covering system starting with a step of 7. Before this work, a mathematician named Klein had built a working system with a "biggest number" of 15,120 and guessed that this was the best possible. However, the authors of this paper prove that Klein's guess was too high. They have constructed a new, more efficient system that works with a "biggest number" of only 10,080. Furthermore, they have mathematically proved that it is impossible to do it with any number smaller than 10,080. They didn't just find a better solution; they proved it is the best solution.

The Detective Story of the Number 10,080

To understand how the authors solved this, imagine you are a detective trying to find a specific key in a massive, dusty warehouse. The warehouse contains every possible "biggest number" (least common multiple) that is a multiple of 7 and falls between 5,040 and 10,080. Your goal is to prove that every single number in this range is a "fake key" that won't open the door, while the number 10,080 is the "real key."

The First Filter: The Reciprocal Sum
The authors start by applying a "reciprocal-sum filter." In everyday terms, imagine each possible interval (like 7, 8, 9) contributes a tiny bit of "coverage power" to the system. The rule is that the total power of all your chosen intervals must add up to more than 1 to cover the whole highway. If you add up the "power" of every possible interval available for a specific candidate number and the total is less than 1, that candidate is immediately disqualified. This filter was very effective, instantly throwing out most of the numbers in the warehouse and leaving only 18 suspicious candidates.

The Second Filter: The Integer Programming Test
Next, the authors used a powerful computer tool called "integer programming." Think of this as a super-organized puzzle solver. For each of the 18 remaining candidates, the computer tried to arrange the traffic signs (residue classes) to see if they could cover the entire highway without any gaps. The computer was smart enough to ignore redundant arrangements (like shifting the whole pattern by one step, which doesn't change the result). This filter was ruthless; it eliminated 14 of the 18 candidates, proving that no matter how you arranged the signs for those numbers, you would always leave some cars uncovered.

The Third Filter: The Partial Sum
Four candidates remained: 5,040, 7,560, 8,400, and 9,240. These were the "tough nuts." The authors realized that for some of these numbers, you could cover almost the entire highway, leaving only a tiny fraction of cars uncovered. This made the previous tests tricky. To handle this, they used a "partial sum filter." Instead of assuming the signs cover everything perfectly, they calculated exactly how much of the highway the best possible arrangement of a subset of signs could cover. They found that for 8,400 and 9,240, even the most optimistic arrangement of signs left a gap too large to fill with the remaining signs. These two numbers were ruled out.

The Final Showdown: The Gurobi Computation
This left only two stubborn suspects: 5,040 and 7,560. These numbers were so good at covering the highway that they could cover over 96% and 98% of it, respectively, leaving only a tiny, hard-to-find gap. To solve this, the authors ran massive, exhaustive computer simulations using a software called Gurobi. They didn't just guess; they checked every single possible way to arrange the signs for these two numbers. The computer ran for thousands of seconds, checking millions of possibilities, and finally declared: "Infeasible." This means it is mathematically impossible to cover the highway with a minimum step of 7 using 5,040 or 7,560 as the biggest number.

The Winner: 10,080
With all smaller numbers eliminated, the authors turned their attention to 10,080. They didn't just prove it was possible; they built the actual system. They listed out the specific intervals and starting points (like "every 7th car starting at 6," "every 8th car starting at 7," and so on) that perfectly cover the entire number line. They verified this system works, proving that 10,080 is indeed a working solution.

The Conclusion

The paper concludes with a definitive answer: the smallest possible "biggest number" for a distinct covering system with a minimum step of 7 is exactly 10,080. This improves upon the previous record of 15,120. The authors didn't just find a better number; they proved that no smaller number could ever work. They did this by systematically filtering out every possibility, from simple math checks to complex computer simulations, leaving no stone unturned. The result is a precise, proven fact in the world of number theory, showing that while you can get very close to covering the infinite highway with smaller numbers, you simply cannot do it perfectly until you reach 10,080.

Technical Summary: A Distinct Covering System with Minimum Modulus 7 and Minimal Least Common Multiple 10080

Problem Statement
The paper addresses the problem of determining the minimum possible least common multiple (LCM), denoted $L_{\min}(m)$ , for a distinct covering system with a prescribed minimum modulus $m$ . A distinct covering system is a finite collection of arithmetic progressions $\{a_i \pmod{m_i}\}$ with pairwise distinct moduli $m_i$ that cover all integers. While Hough (2015) proved that the minimum modulus in any distinct covering system is bounded by an absolute constant, the specific values of $L_{\min}(m)$ for small $m$ have been the subject of explicit construction and verification.

Prior to this work, the values for $m \le 6$ were established: $L_{\min}(3)=120$ , $L_{\min}(4)=360$ , $L_{\min}(5)=1440$ , and $L_{\min}(6)=5040$ . For $m=7$ , Klein (2024) constructed a system with $L=15120$ and conjectured this to be minimal. This paper aims to resolve the case $m=7$ by constructing a system with a smaller LCM and proving that no smaller LCM is possible.

Methodology
The authors employ a successive filtering strategy to eliminate candidate values for the LCM $L$ in the range $5040 \le L < 10080$ . The proof relies on the "divisor-completion" principle: if a distinct covering system exists with minimum modulus $m$ and LCM $L$ , one can add arbitrary congruence classes for any missing divisor $d$ of $L$ (where $d \ge m$ ) without destroying the covering property. Thus, to prove non-existence for a specific $L$ , it suffices to show that the "divisor-completed" set of moduli $D_m(L) = \{d : d|L, d \ge m\}$ cannot form a covering system.

The filtering process consists of four stages:

Reciprocal-Sum Filter: Based on the Mirsky–Newman obstruction (Lemma 1), which states that for any distinct covering system, $\sum 1/m_i > 1$ . The authors compute $S_7(L) = \sum_{d|L, d \ge 7} 1/d$ . If $S_7(L) \le 1$ , $L$ is immediately discarded. This reduces the search space from all multiples of 7 in the range to 18 candidates.
Integer Programming (IP) Filter: For the remaining candidates, the authors formulate a binary integer programming feasibility problem. Variables $x_{m,a}$ indicate whether the residue class $a \pmod m$ is selected. Constraints enforce exactly one class per modulus and coverage of all residues modulo $L$ . To reduce symmetry, the authors apply translation invariance and residue-layer swap normalizations (Lemmas 2 and 3) to fix specific congruence classes (e.g., $6 \pmod 7$ , $7 \pmod 8$ ) before solving. This filter eliminates 14 of the 18 candidates.
Partial-Sum Filter: For the remaining difficult cases (specifically 8400 and 9240), the authors refine the reciprocal sum argument. Instead of assuming all selected classes are disjoint, they compute the maximum possible coverage $\alpha_A(L)$ of a subset of moduli $A$ via a smaller IP, then add the theoretical maximum contribution of the remaining moduli $B$ . If $\alpha_A(L) + \sum_{m \in B} 1/m < 1$ , the candidate is ruled out. This eliminates 8400 and 9240.
Complete Gurobi Computation: The final two candidates, $L=5040$ and $L=7560$ , resist the partial-sum filter because they admit "near-covers" (covering >96% and >98% of residues, respectively). These cases are resolved by running full feasibility checks using the Gurobi solver (v13.0.1) on the complete divisor-completed systems.

Key Contributions and Results

Construction: The authors explicitly construct a distinct covering system with minimum modulus 7 and least common multiple 10080. This system consists of 63 distinct moduli, with the smallest being 7.
Minimality Proof: The paper proves that $L_{\min}(7) = 10080$ . By systematically eliminating all $L < 10080$ (specifically the 18 candidates surviving the initial sum filter), the authors demonstrate that no distinct covering system with minimum modulus 7 can have an LCM smaller than 10080.
Refutation of Conjecture: The result disproves Klein's conjecture that 15120 was the minimal LCM for $m=7$ .
Computational Data: The paper provides a comprehensive table of Gurobi runtimes and outcomes for all 18 candidates, including the two hardest cases (5040 and 7560) which required approximately 13,789 and 13,159 seconds, respectively, to prove infeasibility.

Significance
The paper establishes the exact value of $L_{\min}(7)$ , extending the known sequence of minimal LCMs for distinct covering systems. The work demonstrates the efficacy of combining analytic number theory (reciprocal sums) with combinatorial optimization (integer programming and branch-and-bound) to solve existence problems in arithmetic progressions. The authors note that the difficulty encountered with $L=5040$ and $L=7560$ —where systems cover nearly all residues but fail to cover the remainder—suggests that future improvements in proving minimality for higher moduli may require sharper hybrid certificates capable of distinguishing "near-covers" from genuine covering systems without relying solely on full branch-and-bound verification.

The Detective Story of the Number 10,080

The Conclusion

Technical Summary: A Distinct Covering System with Minimum Modulus 7 and Minimal Least Common Multiple 10080

More like this