Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source and certificate. Hough's numerical calculations occur on printed pp. 377–379 of the published paper. The source reports PARI/GP calculations. This compilation supplies a separate standard-library checker, verify_hough2015.py. No downloaded program is executed and no floating-point value decides a check. From the repository root, run
uv run --no-sync python library/covering_systems/hough_2015_solution_minimum_modulus_problem_covering_systems/evidence/verify_hough2015.pyIt prints one line per named obligation and a summary line before the JSON
certificate, whose exit_code equals the process exit status; any failed
comparison exits nonzero, including under python -O. The interval
arithmetic uses only the Python standard library; the check harness comes
from the root tools package of the repository environment. Expected
runtime is about ten seconds.
Statement. Put , , , and . The certificate establishes
and for the three integers ,
The last bound is stronger than the source's stated Lemma 7 bound. It retains the factor that Appendix A already proves for . The scalar checks include
and every endpoint comparison used in the infinite-tail proof.
Complete proof of the finite certification. Set . The checker represents a nonnegative real number by a pair of integers certifying . A rational is enclosed by and . Addition and subtraction use endpoint arithmetic; subtraction rejects any negative lower endpoint. Positive multiplication rounds downward and upward. The reciprocal, allowed only when , rounds downward and upward. These follow from monotonicity on the nonnegative real line. A claimed strict inequality is accepted only when the left upper numerator is strictly smaller than the right lower numerator. Meeting or overlapping endpoints cause failure.
For rational, the exponential is enclosed using its positive Taylor series. After term , the remaining sum is at most
because the successive ratios of remaining terms are at most . Terms and this tail bound are exact fractions. The checker continues until the tail is less than , then rounds the partial sum down and the partial sum plus tail up. For it similarly encloses
using the first omitted term divided by as an upper bound on the omitted tail. The identity follows by integrating the geometric series for from to .
For a positive integer and rational exponent , the checker forms the integer and finds its integer th root , explicitly checking
Then . The integer root routine begins above the root and applies integer Newton descent
The inner floor does not change the final floor. The corresponding real Newton expression is at least by the arithmetic-geometric mean inequality. Thus the new integer is never below . Whenever exceeds that integer root, forces a strict integer decrease. It terminates at the root, and the direct endpoint check is mandatory in any case. This provides the enclosures of and ; inversion gives the negative powers in the Rankin product.
The exponential enclosures certify the following exact prime cutoffs. The lower and upper endpoints have the same integer part in each case.
| Primes in | ||
|---|---|---|
| 11 | 59874 | 8864 |
| 12 | 162754 | 22216 |
| 13 | 442413 | 55989 |
| 14 | 1202604 | Outside the finite-band enumeration |
The checker sieves every integer through . Starting with all integers at least unmarked, for each unmarked it marks the multiples . A marked number is composite. Conversely every composite has a least prime divisor at most its square root, and is marked when that prime is reached; no prime is marked. The unmarked list is therefore exactly all the primes through the cutoff. There are of them, including at most . The output pins the entire ordered list by a SHA256 hash.
Differentiating the geometric series, or multiplying by , gives the exact rational identities
Thus all finite products except the explicitly enclosed fractional powers use rational factors. The checker multiplies or sums every required prime factor with the outward operations above. It checks both the original and strengthened cubic-tail bounds for all three bands, and all initial and scalar inequalities. The checker passes all strict comparisons. Its JSON result contains the actual integer endpoints and positive margins, so the conclusion does not rest on rounded decimal displays or on the source's reported PARI run.
Proof scope. This is an ordinary finite computational certificate with an accompanying correctness proof, not a Lean or kernel check. The infinite prime bands are proved analytically in Lemma 7 relative to the exact Rosser–Schoenfeld input. The numerical checker pins the precise parameters; it does not read the paper and does not purport to verify the entire article by execution.
Bears on. Problem 2.