Wiki
Wiki

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

bash
uv run --no-sync python library/covering_systems/hough_2015_solution_minimum_modulus_problem_covering_systems/evidence/verify_hough2015.py

It 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 M=1016M=10^{16}, σ=19/100\sigma=19/100, δ=43/50\delta=43/50, qj=(j+1)3−j3q_j=(j+1)^3-j^3 and Sn=∑en<p≤en+1(p−1)−3S_n=\sum_{e^n<p\le e^{n+1}}(p-1)^{-3}. The certificate establishes

M−19/100∏p≤e11(1−p−81/100)−1<8591000,M^{-19/100}\prod_{p\le e^{11}}(1-p^{-81/100})^{-1}<\frac{859}{1000}, 507∏p≤e11∑j≥0qjpj<(36595)3,\frac{50}{7}\prod_{p\le e^{11}}\sum_{j\ge0}\frac{q_j}{p^j} <\left(\frac{3659}{5}\right)^3,

and for the three integers n=11,12,13n=11,12,13,

∏en<p≤en+1(1+2p−1)<65,∏en<p≤en+1(1+2∑j≥1qjpj)<175,Sn<22/252ne2n.\prod_{e^n<p\le e^{n+1}}\left(1+\frac2{p-1}\right)<\frac65, \qquad \prod_{e^n<p\le e^{n+1}}\left(1+2\sum_{j\ge1}\frac{q_j}{p^j}\right)<\frac{17}{5}, \qquad S_n<\frac{22/25}{2ne^{2n}}.

The last bound is stronger than the source's stated Lemma 7 bound. It retains the factor 0.880.88 that Appendix A already proves for n≥14n\ge14. The scalar checks include

2225(65⋅4⋅36595)3<11e22,345<e2,\frac{22}{25}\left(\frac65\cdot4\cdot\frac{3659}{5}\right)^3 <11e^{22},\qquad \frac{34}{5}<e^2,

and every endpoint comparison used in the infinite-tail proof.

Complete proof of the finite certification. Set D=2128D=2^{128}. The checker represents a nonnegative real number by a pair of integers (l,u)(l,u) certifying l/D≤x≤u/Dl/D\le x\le u/D. A rational a/ba/b is enclosed by ⌊aD/b⌋\lfloor aD/b\rfloor and ⌈aD/b⌉\lceil aD/b\rceil. Addition and subtraction use endpoint arithmetic; subtraction rejects any negative lower endpoint. Positive multiplication rounds l1l2/Dl_1l_2/D downward and u1u2/Du_1u_2/D upward. The reciprocal, allowed only when l>0l>0, rounds D2/uD^2/u downward and D2/lD^2/l 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 x≥0x\ge0 rational, the exponential is enclosed using its positive Taylor series. After term xj/j!x^j/j!, the remaining sum is at most

xj+1(j+1)!11−x/(j+2),j+2>x,\frac{x^{j+1}}{(j+1)!}\frac1{1-x/(j+2)},\qquad j+2>x,

because the successive ratios of remaining terms are at most x/(j+2)x/(j+2). Terms and this tail bound are exact fractions. The checker continues until the tail is less than D−2D^{-2}, then rounds the partial sum down and the partial sum plus tail up. For a≥b>0a\ge b>0 it similarly encloses

log⁡(a/b)=2∑j≥0z2j+12j+1,z=a−ba+b∈[0,1),\log(a/b)=2\sum_{j\ge0}\frac{z^{2j+1}}{2j+1},\qquad z=\frac{a-b}{a+b}\in[0,1),

using the first omitted term divided by 1−z21-z^2 as an upper bound on the omitted tail. The identity follows by integrating the geometric series for 1/(1−z2)1/(1-z^2) from 00 to zz.

For a positive integer aa and rational exponent r/s>0r/s>0, the checker forms the integer N=arDsN=a^rD^s and finds its integer ssth root hh, explicitly checking

hs≤N<(h+1)s.h^s\le N<(h+1)^s.

Then h/D≤ar/s<(h+1)/Dh/D\le a^{r/s}<(h+1)/D. The integer root routine begins above the root and applies integer Newton descent

x⟼⌊(s−1)x+⌊N/xs−1⌋s⌋.x\longmapsto \left\lfloor\frac{(s-1)x+\lfloor N/x^{s-1}\rfloor}{s}\right\rfloor.

The inner floor does not change the final floor. The corresponding real Newton expression is at least N1/sN^{1/s} by the arithmetic-geometric mean inequality. Thus the new integer is never below ⌊N1/s⌋\lfloor N^{1/s}\rfloor. Whenever xx exceeds that integer root, N<xsN<x^s 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 p81/100p^{81/100} and M19/100M^{19/100}; 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.

nn⌊en⌋\lfloor e^n\rfloorPrimes in (en,en+1](e^n,e^{n+1}]
11598748864
1216275422216
1344241355989
141202604Outside the finite-band enumeration

The checker sieves every integer through 12026041202604. Starting with all integers at least 22 unmarked, for each unmarked p≤1202604p\le\sqrt{1202604} it marks the multiples p2,p2+p,…p^2,p^2+p,\ldots. 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 9311793117 of them, including 60486048 at most e11e^{11}. The output pins the entire ordered list by a SHA256 hash.

Differentiating the geometric series, or multiplying by (1−z)3(1-z)^3, gives the exact rational identities

∑j≥1qjpj=7p2−2p+1(p−1)3,∑j≥0qjpj=p(p2+4p+1)(p−1)3.\sum_{j\ge1}\frac{q_j}{p^j}= \frac{7p^2-2p+1}{(p-1)^3},\qquad \sum_{j\ge0}\frac{q_j}{p^j}= \frac{p(p^2+4p+1)}{(p-1)^3}.

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 2323 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.