Tables for the finite Rosser--Schoenfeld certificate
DefinitionTaoFivePrimes_theta_cert_tablesanalytic-number-theorychebyshev-thetanumber-theorynumerical-certificate
Data tables used by a machine-checked certificate for Rosser--Schoenfeld's finite-range lower bound on (Theorem 19, 1962). The table clbZ stores, for each prime , the value (and off the primes); plist is the explicit finet of primes , presented as the union of four consecutive chunks plist1--plist4; and blocks is the explicit interval cover of by 71 intervals (in four consecutive chunks blk1--blk4) on which the lower bound is checked.
Definition code
import Mathlib.Data.Finset.Basic
import Mathlib.Order.Interval.Finset.Nat
/-!
# Tables for the finite Rosser--Schoenfeld theta certificate
Data used by the machine-checked certificate for
`t - 2*sqrt t < theta t` on `255 <= t <= 1420`
(Rosser--Schoenfeld 1962, Theorem 19, finite window):
* `clbZ p` -- the 4-decimal floor of `log p` scaled by `10^4`, for primes `p <= 1420`;
* `plist` -- the primes `<= 1420`, split into four consecutive chunks
`plist1, plist2, plist3, plist4`;
* `blocks` -- the interval cover of `[255, 1420]` used by the certificate,
split into four consecutive chunks `blk1, blk2, blk3, blk4`.
-/
namespace TaoFivePrimes
open Finset
/-- Integer 4-decimal lower bounds for `log p`: `clbZ p = floor(log p * 10^4)`
for primes `p <= 1420` and `clbZ p = 0` otherwise. -/
def clbZ : ℕ → ℕ
| 2 => 6931
| 3 => 10986
| 5 => 16094
| 7 => 19459
| 11 => 23978
| 13 => 25649
| 17 => 28332
| 19 => 29444
| 23 => 31354
| 29 => 33672
| 31 => 34339
| 37 => 36109
| 41 => 37135
| 43 => 37612
| 47 => 38501
| 53 => 39702
| 59 => 40775
| 61 => 41108
| 67 => 42046
| 71 => 42626
| 73 => 42904
| 79 => 43694
| 83 => 44188
| 89 => 44886
| 97 => 45747
| 101 => 46151
| 103 => 46347
| 107 => 46728
| 109 => 46913
| 113 => 47273
| 127 => 48441
| 131 => 48751
| 137 => 49199
| 139 => 49344
| 149 => 50039
| 151 => 50172
| 157 => 50562
| 163 => 50937
| 167 => 51179
| 173 => 51532
| 179 => 51873
| 181 => 51984
| 191 => 52522
| 193 => 52626
| 197 => 52832
| 199 => 52933
| 211 => 53518
| 223 => 54071
| 227 => 54249
| 229 => 54337
| 233 => 54510
| 239 => 54764
| 241 => 54847
| 251 => 55254
| 257 => 55490
| 263 => 55721
| 269 => 55947
| 271 => 56021
| 277 => 56240
| 281 => 56383
| 283 => 56454
| 293 => 56801
| 307 => 57268
| 311 => 57397
| 313 => 57462
| 317 => 57589
| 331 => 58021
| 337 => 58200
| 347 => 58493
| 349 => 58550
| 353 => 58664
| 359 => 58833
| 367 => 59053
| 373 => 59215
| 379 => 59375
| 383 => 59480
| 389 => 59635
| 397 => 59839
| 401 => 59939
| 409 => 60137
| 419 => 60378
| 421 => 60426
| 431 => 60661
| 433 => 60707
| 439 => 60844
| 443 => 60935
| 449 => 61070
| 457 => 61246
| 461 => 61333
| 463 => 61377
| 467 => 61463
| 479 => 61717
| 487 => 61882
| 491 => 61964
| 499 => 62126
| 503 => 62205
| 509 => 62324
| 521 => 62557
| 523 => 62595
| 541 => 62934
| 547 => 63044
| 557 => 63225
| 563 => 63332
| 569 => 63438
| 571 => 63473
| 577 => 63578
| 587 => 63750
| 593 => 63851
| 599 => 63952
| 601 => 63985
| 607 => 64085
| 613 => 64183
| 617 => 64248
| 619 => 64281
| 631 => 64473
| 641 => 64630
| 643 => 64661
| 647 => 64723
| 653 => 64815
| 659 => 64907
| 661 => 64937
| 673 => 65117
| 677 => 65176
| 683 => 65264
| 691 => 65381
| 701 => 65525
| 709 => 65638
| 719 => 65778
| 727 => 65889
| 733 => 65971
| 739 => 66052
| 743 => 66106
| 751 => 66214
| 757 => 66293
| 761 => 66346
| 769 => 66450
| 773 => 66502
| 787 => 66682
| 797 => 66808
| 809 => 66957
| 811 => 66982
| 821 => 67105
| 823 => 67129
| 827 => 67178
| 829 => 67202
| 839 => 67322
| 853 => 67487
| 857 => 67534
| 859 => 67557
| 863 => 67604
| 877 => 67765
| 881 => 67810
| 883 => 67833
| 887 => 67878
| 907 => 68101
| 911 => 68145
| 919 => 68232
| 929 => 68341
| 937 => 68426
| 941 => 68469
| 947 => 68532
| 953 => 68596
| 967 => 68741
| 971 => 68783
| 977 => 68844
| 983 => 68906
| 991 => 68987
| 997 => 69047
| 1009 => 69167
| 1013 => 69206
| 1019 => 69265
| 1021 => 69285
| 1031 => 69382
| 1033 => 69402
| 1039 => 69460
| 1049 => 69555
| 1051 => 69574
| 1061 => 69669
| 1063 => 69688
| 1069 => 69744
| 1087 => 69911
| 1091 => 69948
| 1093 => 69966
| 1097 => 70003
| 1103 => 70057
| 1109 => 70112
| 1117 => 70184
| 1123 => 70237
| 1129 => 70290
| 1151 => 70483
| 1153 => 70501
| 1163 => 70587
| 1171 => 70656
| 1181 => 70741
| 1187 => 70791
| 1193 => 70842
| 1201 => 70909
| 1213 => 71008
| 1217 => 71041
| 1223 => 71090
| 1229 => 71139
| 1231 => 71155
| 1237 => 71204
| 1249 => 71300
| 1259 => 71380
| 1277 => 71522
| 1279 => 71538
| 1283 => 71569
| 1289 => 71616
| 1291 => 71631
| 1297 => 71678
| 1301 => 71708
| 1303 => 71724
| 1307 => 71754
| 1319 => 71846
| 1321 => 71861
| 1327 => 71906
| 1361 => 72159
| 1367 => 72203
| 1373 => 72247
| 1381 => 72305
| 1399 => 72435
| 1409 => 72506
| _ => 0
def plist1 : Finset ℕ := {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257}
def plist2 : Finset ℕ := {263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601}
def plist3 : Finset ℕ := {607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977}
def plist4 : Finset ℕ := {983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409}
/-- The primes `<= 1420` as an explicit finset. -/
def plist : Finset ℕ := plist1 ∪ plist2 ∪ plist3 ∪ plist4
def blk1 : List (ℕ × ℕ) := [(255, 263), (264, 275), (276, 286), (287, 304), (305, 311), (312, 323), (324, 334), (335, 340), (341, 347), (348, 353), (354, 366), (367, 377), (378, 384), (385, 396), (397, 409), (410, 422), (423, 434)]
def blk2 : List (ℕ × ℕ) := [(435, 447), (448, 460), (461, 479), (480, 498), (499, 518), (519, 532), (533, 544), (545, 550), (551, 558), (559, 564), (565, 570), (571, 584), (585, 590), (591, 597), (598, 604), (605, 617), (618, 637), (638, 651)]
def blk3 : List (ℕ × ℕ) := [(652, 670), (671, 691), (692, 718), (719, 739), (740, 759), (760, 779), (780, 800), (801, 815), (816, 828), (829, 856), (857, 877), (878, 897), (898, 919), (920, 940), (941, 962), (963, 975), (976, 989), (990, 1004)]
def blk4 : List (ℕ × ℕ) := [(1005, 1018), (1019, 1040), (1041, 1068), (1069, 1104), (1105, 1140), (1141, 1169), (1170, 1191), (1192, 1213), (1214, 1235), (1236, 1264), (1265, 1286), (1287, 1308), (1309, 1352), (1353, 1375), (1376, 1396), (1397, 1404), (1405, 1412), (1413, 1420)]
/-- Blocks `(a, b)`: on `[a,b]`, `theta a` dominates the target at `b`. -/
def blocks : List (ℕ × ℕ) := [(255, 263), (264, 275), (276, 286), (287, 304), (305, 311), (312, 323), (324, 334), (335, 340), (341, 347), (348, 353), (354, 366), (367, 377), (378, 384), (385, 396), (397, 409), (410, 422), (423, 434), (435, 447), (448, 460), (461, 479), (480, 498), (499, 518), (519, 532), (533, 544), (545, 550), (551, 558), (559, 564), (565, 570), (571, 584), (585, 590), (591, 597), (598, 604), (605, 617), (618, 637), (638, 651), (652, 670), (671, 691), (692, 718), (719, 739), (740, 759), (760, 779), (780, 800), (801, 815), (816, 828), (829, 856), (857, 877), (878, 897), (898, 919), (920, 940), (941, 962), (963, 975), (976, 989), (990, 1004), (1005, 1018), (1019, 1040), (1041, 1068), (1069, 1104), (1105, 1140), (1141, 1169), (1170, 1191), (1192, 1213), (1214, 1235), (1236, 1264), (1265, 1286), (1287, 1308), (1309, 1352), (1353, 1375), (1376, 1396), (1397, 1404), (1405, 1412), (1413, 1420)]
end TaoFivePrimes
Source
J.B. Rosser, L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94; p. 82, Theorem 19 (finite window), used in the '288' chain of the Lemma 15 proof, p. 89. https://doi.org/10.1215/ijm/1255631807