"""Real-arithmetic implications for the Erdős–Graham bounds. Requires z3-solver.""" from z3 import And, Not, Or, Q, Reals, SolverFor, sat, unsat def check(label, assumptions, conclusion): solver = SolverFor("QF_NRA") solver.add(*assumptions) if solver.check() != sat: raise ValueError(f"{label}: assumptions not verified satisfiable") solver.add(Not(conclusion)) if solver.check() != unsat: raise ValueError(f"{label}: implication not verified") print(f"{label}: consistent assumptions, no counterexample") def check_arithmetic(): # 01 Range of the parameter at the threshold B = 9797000000000000000 check( "01 Range of the parameter at the threshold", [ ], And( B * B < 96000000000000000000000000000000000000, 512 * 656 * 656 * 10000000000000 < 225 * B, 2 * B > 3 * 10000000000000, ), ) # 02 Chebyshev on the larger-factor interval N, d, L, b = Reals("N d L b") check( "02 Chebyshev on the larger-factor interval", [ N > 0, d > 0, L > 0, b >= 0, 9 * b * d * d * N * N <= 192 * d * N * N * L * L, ], 3 * d * b <= 64 * L * L, ) # 03 Chebyshev on the smaller-factor interval N, d, L, b = Reals("N d L b") check( "03 Chebyshev on the smaller-factor interval", [ N > 0, d > 0, L > 0, b >= 0, b * (d * N / 4) * (d * N / 4) <= 3 * d * (2 * N / 3) * (2 * N / 3) * L * L, ], 3 * d * b <= 64 * L * L, ) # 04 Reciprocal image and inverse Jacobian N, t, u = Reals("N t u") check( "04 Reciprocal image and inverse Jacobian", [ N > 0, 2 * t >= 3 * N, t <= 2 * N, t * u == N * N, ], And( 2 * u >= N, 3 * u <= 2 * N, N * N <= 4 * u * u, ), ) # 05 Simultaneously good starts N, d, L, bI, bJ, g = Reals("N d L bI bJ g") check( "05 Simultaneously good starts", [ d > 0, L > 0, N > 0, d * N == 512 * L * L, bI >= 0, bJ >= 0, 3 * d * bI <= 64 * L * L, 3 * d * bJ <= 64 * L * L, g >= N / 2 - bI - 4 * bJ, ], And( 24 * g >= 7 * N, 4 * g > N, ), ) # 06 Count at a pair of good starts L, M, d, t, u, N, a, b = Reals("L M d t u N a b") check( "06 Count at a pair of good starts", [ L > 0, M > 0, M <= 2 * L, N > 0, d > 0, t > 0, t * u == N * N, 2 * M * a >= d * t, 2 * M * b >= d * u, ], 16 * L * L * a * b >= d * d * N * N, ) # 07 Opposite factor ranges, product strip and time per pair N, t, u, p, q, d = Reals("N t u p q d") check( "07 Opposite factor ranges, product strip and time per pair", [ N > 0, d > 0, 2 * d < 1, 2 * t >= 3 * N, t <= 2 * N, t * u == N * N, p > t, p <= (1 + d) * t, q > u, q <= (1 + d) * u, ], And( p > N, p < 3 * N, 2 * q > N, q < N, p * q > N * N, p * q <= (1 + d) * (1 + d) * N * N, d * p <= 2 * d * N * (1 + d), ), ) # 08 Lower bound for the incidence integral N, d, L, g, m, integral = Reals("N d L g m integral") check( "08 Lower bound for the incidence integral", [ N > 0, d > 0, L > 0, 24 * g >= 7 * N, 16 * L * L * m >= d * d * N * N, integral >= g * m, ], 384 * L * L * integral >= 7 * d * d * N * N * N, ) # 09 Distinct pair count and weighted mass N, d, L, count, mass, integral = Reals("N d L count mass integral") check( "09 Distinct pair count and weighted mass", [ N > 0, d > 0, L > 0, d * N == 512 * L * L, 384 * L * L * integral >= 7 * d * d * N * N * N, integral <= 2 * d * N * count, 3 * N * mass >= count, ], And( 3 * count >= 14 * N, 9 * mass >= 14, ), ) # 10 Interval endpoint in the original scale N, d, L = Reals("N d L") check( "10 Interval endpoint in the original scale", [ N > 0, d > 0, d < 1, L > 0, d * N == 512 * L * L, ], And( (1 + d) * (1 + d) * N * N < N * N + 3 * d * N * N, 3 * d * N * N == 384 * N * (2 * L) * (2 * L), ), ) # 11 Exceptional measure in the fixed-length proof N, K, D, bI, bJ = Reals("N K D bI bJ") check( "11 Exceptional measure in the fixed-length proof", [ N > 0, D > 0, K >= 192 * D, bI >= 0, bJ >= 0, K * bI <= 8 * D * N, K * bJ <= 4 * D * N, ], 8 * (bI + 4 * bJ) <= N, ) # 12 Constant for the 2023 preprint of Cully-Hugill and Dudek check( "12 Constant for the 2023 preprint of Cully-Hugill and Dudek", [ ], And( Q(1, 2) - Q(320 * 808, 9 * 131072) > Q(1, 4), Q(3 * 131072, 4) == 98304, Q(131072, 128) == 1024, 131072 * 63 * 63 * 100000000 < 1000000000000000000000, ), ) # 13 Second-moment polynomial and the dyadic bound ell, j, h, X, S = Reals("ell j h X S") check( "13 Second-moment polynomial and the dyadic bound", [ ell > 0, ell <= j, j <= 2 * h, X > 0, X <= 3 * S, ], X * (ell * ell + 2 * j * ell + 8 * j * j) <= 132 * S * h * h, ) # 14 Positive density after Cauchy-Schwarz S, u, g, total, outside, moment = Reals("S u g total outside moment") check( "14 Positive density after Cauchy-Schwarz", [ S > 0, u > 0, g >= 0, total >= S * u / 2, outside <= S * u / 4, outside >= 0, moment >= 0, moment <= 132 * S * u * u, (total - outside) * (total - outside) <= g * moment, ], And( 2112 * g >= S, 2500 * g >= S, ), ) # 15 Arbitrary prescribed C and the reciprocal exceptional set C, b, r, N, L, d, T, S, bad = Reals("C b r N L d T S bad") check( "15 Arbitrary prescribed C and the reciprocal exceptional set", [ C > 0, b > 0, r > 0, N > 0, L > 0, d > 0, S > 0, T == r * N, d * N == C * L * L, r * b * C >= 192, bad >= 0, bad * T * d <= 96 * S * L * L, ], 2 * bad <= b * S, ) # 16 Arbitrary C pair count and total weight C, b, r, N, L, d, T, S, pairs, mass = Reals("C b r N L d T S pairs mass") check( "16 Arbitrary C pair count and total weight", [ C > 0, b > 0, r > 0, N > 0, L > 0, d > 0, S > 0, T == r * N, d * N == C * L * L, 2 * S * T == N * N, 32 * L * L * pairs >= b * S * d * T, 3 * T * mass >= pairs, ], And( 64 * pairs >= b * C * N, 192 * r * mass >= b * C, ), ) # 17 Every pair in the upper-bound strip gives enough starts X, S, d, t, v, p, q = Reals("X S d t v p q") check( "17 Every pair in the upper-bound strip gives enough starts", [ X > 0, S > 0, d > 0, d < 1, p > S, p <= 2 * S, p * q >= X, p * q <= (1 + d) * X, (1 + d) * t > p, t < p, (1 + d) * t * v == X, ], And( 2 * t > S, t < 2 * S, p > t, p < (1 + d) * t, q > v, q < (1 + d) * (1 + d) * v, 2 * d * p >= d * S * (1 + d), ), ) # 18 Upper bound partner interval and inverse Jacobian S, T, d, t, v = Reals("S T d t v") check( "18 Upper bound partner interval and inverse Jacobian", [ S > 0, T > 0, d > 0, d < 1, 2 * t >= S, t <= 2 * S, S * T == (1 + d) * t * v, ], And( 4 * v >= T, v <= 2 * T, ((1 + d) * (1 + d) - 1) * v <= 6 * d * T, T * T <= 16 * (1 + d) * v * v, ), ) # 19 From the two Selberg moment bounds to the stated mass k, bigBad, smallBad, good, products, weight = Reals("k bigBad smallBad good products weight") check( "19 From the two Selberg moment bounds to the stated mass", [ k == 512, bigBad >= 0, smallBad >= 0, bigBad * k * Q(9, 16) <= 12, smallBad * k * Q(1, 16) <= Q(4, 3), good >= Q(1, 2) - bigBad - 4 * smallBad, 32 * products >= k * good, 3 * weight >= products, ], And( good >= Q(7, 24), products >= Q(14, 3), weight >= Q(14, 9), products >= 4, weight >= Q(4, 3), ), ) # 20 Exact membership of the reciprocal pair kernel, including endpoints t, p, q, u, X = Reals("t p q u X") check( "20 Exact membership of the reciprocal pair kernel, including endpoints", [ t > 0, p > 0, q > 0, u > 1, X > 0, ], And(t < p, p <= u * t, X / t < q, q <= u * X / t) == And(p / u <= t, t < p, X / q < t, t <= u * X / q), ) # 21 Larger-prime intervals at different grid points are disjoint N, d, s, t, p = Reals("N d s t p") check( "21 Larger-prime intervals at different grid points are disjoint", [ N > 0, d > 0, s > 0, s <= 2 * N, t >= s + 2 * d * N, p > s, p <= (1 + d) * s, ], p <= t, ) # 22 Mixed factor intervals for an arbitrary fixed coefficient S, T, N, s, v, d, p, q, h = Reals("S T N s v d p q h") check( "22 Mixed factor intervals for an arbitrary fixed coefficient", [ S > 0, T > 0, N > 0, 4 * S <= N, T >= 2 * N, 2 * S * T == N * N, s >= S, s <= 2 * S, s * v == N * N, d > 0, d <= Q(1, 4), h == d * S, q > s, q <= s + h, p > v, p <= (1 + d) * v, ], And( q - h <= s, s < q, q > S, q < N, p > N, p < 3 * T, p * q > N * N, p * q <= (1 + 3 * d) * N * N, ), ) # 23 Fixed interval lengths satisfy the moment lemma on all dyadic pieces S, T, d, C, L, U, ell, h = Reals("S T d C L U ell h") check( "23 Fixed interval lengths satisfy the moment lemma on all dyadic pieces", [ S > 0, T > 0, d > 0, 96 * d <= 1, C > 0, L > 0, 3 * C * L >= 1, d * S >= 4 * L, d * T >= 2 * C * L * L, ell > 0, ell <= 2 * L, Or(And(Or(U == S / 2, U == S), h == 2 * d * S), And(Or(U == T / 4, U == T / 2, U == T), h == 6 * d * T)), ], And( h >= 2 * ell, 4 * h <= U, ), ) # 24 Cauchy-Schwarz and the lower covering length in an upper-bound band a, b, K, j, n = Reals("a b K j n") check( "24 Cauchy-Schwarz and the lower covering length in an upper-bound band", [ K >= 0, a >= 0, b >= 0, a <= K, b <= K, j >= 0, n >= 0, j * j <= a * b, n <= 2 * j, ], n <= 2 * K, )