Mobius and primes on the Kummer sets

Mobius and primes on the Kummer sets

Fix a prime p and integers a > b >= 1. The Kummer set K_(a,b) holds the integers k >= 0 with p not dividing C(ak, bk), and K = K_(3,1) is the set of k with p not dividing C(3k, k). Write A_K(x) for the number of 1 <= k <= x in K, M_K(x) for the sum of mu(k) over them and psi_K(x) for the sum of Lambda(k). At (a, b) = (2, 1) the set is the half interval of mobius, the digit design on {0..(p-1)/2}, whose Mobius bound and prime count that page proves from p = 94939. At (3, 1) and every prime p >= 5 the set is no digit design, proved in the first section: the digits of k are read by a finite automaton whose state is a carry, and this page carries the half interval's theorem onto K through a matrix form of its transfer certificate. Past (3, 1) the same is read and not proved: over every 2 <= a <= 6, 1 <= b < a and prime a < p <= 31 the only Kummer set that is a product of its digit sets below p^3 is (2, 1) (Verified, verb family); at p <= a it fails, K_(3,1) at p = 3 being {0}, the design on {0}. Every number below is printed by lab/py/kummer-carry.

The carry automaton

  • The automaton. Proved. Let p >= 5 and read the digits d_0, d_1, .. of k from the lowest, starting in state 0. In state c a digit d is allowed and moves to state 0 when 3d + c <= p - 1, is allowed and moves to state 1 when 2d + c >= p and 3d + c <= 2p - 1, and is refused otherwise. Then k lies in K exactly when every digit is allowed. Proof. By Kummer 1852, v_p(C(m + n, m)) is the number of carries in the addition m + n at base p, and C(3k, k) = C(k + 2k, k). The doubling 2k has digit e_i = 2 d_i + c_i - p c_(i+1) with c_0 = 0 and c_(i+1) = 1 exactly when 2 d_i + c_i >= p, and c_i <= 1 since 2(p - 1) + 1 < 2p; the state is this carry. If no carry of k + 2k arrives at position i, the column there sums d_i + e_i = 3 d_i + c_i - p c_(i+1), which is at most p - 1 exactly under the two allowed cases, 3d + c <= p - 1 forcing 2d + c <= p - 1. Above the top digit 2k holds the single digit c_L <= 1 against a zero of k, a column sum at most 1. So k + 2k carries nowhere exactly when every digit is allowed. The digit 0 is allowed in both states and moves to state 0, so leading zeros change nothing and K below p^L is the set of accepted words of length L. □
  • The digit sets. Proved. Write D_(c c') for the digits read in state c that move to state c'. Solving the inequalities, D_00 = {0..floor((p-1)/3)}, D_01 = {(p+1)/2..floor((2p-1)/3)}, D_10 = {0..floor((p-2)/3)} and D_11 = {(p-1)/2..floor((2p-2)/3)}, four intervals. At p = 1 mod 6 they have (p+2)/3, (p-1)/6, (p-1)/3 and (p+5)/6 digits, D_10 being D_00 less its top digit (p-1)/3 and D_11 being D_01 with (p-1)/2 added; at p = 5 mod 6 they have (p+1)/3, (p+1)/6, (p+1)/3 and (p+1)/6, with D_10 = D_00 and D_11 = D_01 - 1. Either way each state keeps exactly fill = (p+1)/2 digits, and both states keep the consecutive pair {0, 1} inside the kernel to state 0. State 0 keeps the two intervals F* = D_00 u D_01, the low third and the slice from a half to two thirds, the row-0 design of the sections below. At p = 3 state 0 keeps only the digit 0, so K = {0}: 3 divides C(3k, k) at every k >= 1.
  • A width-2 rule and not a digit design. Proved. An allowed digit moves to state 1 exactly when it is at least (p-1)/2, so the state after a digit is a function of that digit and K is the set of k whose word, with one 0 placed below the units digit, has every window of two adjacent digits allowed: a width-2 rule of the memory dial on beneath at base p, read from the units end. It is no product set. Let u = (p+1)/2, which moves state 0 to state 1, and let v be a digit allowed in state 0 and refused in state 1, v = (p-1)/3 at p = 1 mod 6 and v = (2p-1)/3 at p = 5 mod 6. Then u and v p lie in K and u + v p does not, while a digit design holding u and v p holds u + v p. At p = 7 that is 4 = 4_7 and 14 = 20_7 in K and 18 = 24_7 outside it, the sum 24 + 51 of 18 and 36 carrying at position 1.
  • The check. Verified. The automaton against Kummer's carry count (s_p(k) + s_p(2k) - s_p(3k))/(p - 1), s_p the digit sum, with 0 mismatches: at every k < p^5 for p = 5, 7, 11, 13; at every k < 101^3 directly; and at every k < 101^5 = 10510100501 through k = 101^2 q + r, where the digit sums of k, 2k and 3k split exactly over the carries floor(2r/101^2) and floor(3r/101^2), so that the automaton's verdict and the count are compared on all 61 value pairs of the carry classes and so on every k. The four intervals, the row sums and the pair hold at every prime 5..2999, the witness u, v p, u + v p at all 428 of them, and K holds exactly ((p+1)/2)^5 integers below p^5 at all five primes, 345025251 at 101 (verb kummer, under a second).

The mass of every Kummer set

  • The automaton of every pair. Proved. Let a > b >= 1 and let p > a be prime. Since C(ak, bk) = C(bk + (a-b)k, bk), Kummer's theorem makes K_(a,b) the set where bk + (a-b)k carries nowhere. The state is the pair (c_1, c_2) of carries of the multiplications by b and by a - b, with c_1 < b and c_2 < a - b. In state (c_1, c_2) the digit d meets the digits x = (bd + c_1) mod p of bk and y = ((a-b)d + c_2) mod p of (a-b)k; it is allowed when x + y <= p - 1, and it moves to (floor((bd + c_1)/p), floor(((a-b)d + c_2)/p)), again below (b, a - b) since b(p-1) + b - 1 < bp. Above the top digit bk and (a-b)k hold the single digits c_1 and c_2, whose sum is at most a - 2 < p, so the top never carries, and the digit 0 is allowed in every state and moves to (0, 0). At (3, 1), c_1 = 0 and this is the automaton of the section above. The sets of (a, b) and (a, a - b) are one set.
  • Every state keeps (p+1)/2 digits. Proved. In state (c_1, c_2) put z = (ad + c_1 + c_2) mod p. Then x + y = z mod p and 0 <= x + y <= 2p - 2, so x + y - z is 0 or p, and the digit is refused exactly when it is p. As d runs over 0..p-1, each of x, y and z runs over every residue once, since p divides none of b, a - b and a. So the refused digits number (1/p) sum_d (x + y - z) = (p(p-1)/2 + p(p-1)/2 - p(p-1)/2)/p = (p-1)/2, and every state keeps fill = (p+1)/2. □
  • The mass. Proved. At every a > b >= 1 and every prime p > a, K_(a,b) holds exactly ((p+1)/2)^L integers in [0, p^L), since from every state exactly fill digits continue a word; so A(p^L) = fill^L, p^L itself lying in the set, and A(x) grows like x^(alpha_p), alpha_p = log((p+1)/2)/log p, the half interval's exponent, at every pair. In the language of beneath the count matrix M(0), entry (c, c') the number of digits taking c to c', the transform matrix of the next section at frequency 0, has every row summing to fill, so its Perron root is fill exactly with right Perron vector the all-ones vector, and the set's dimension is log_p fill. At (3, 1) the count matrix is [[(p+2)/3, (p-1)/6], [(p-1)/3, (p+5)/6]] at p = 1 mod 6, with second eigenvalue lambda_2 = 1, and [[(p+1)/3, (p+1)/6], [(p+1)/3, (p+1)/6]] at p = 5 mod 6, rank one with lambda_2 = 0; in both M(0) = fill 1 pi + lambda_2 (I - 1 pi) with left Perron vector pi = (2/3, 1/3), so the words of length L ending in state c number exactly fill^L pi_c + lambda_2^L (delta_(0c) - pi_c).
  • The pair. Proved. At every prime p >= 2a - 1 every state keeps {0, 1} inside its kernel to (0, 0): the digit 0 meets x + y = c_1 + c_2 <= a - 2, and the digit 1 meets x = b + c_1 <= 2b - 1 and y = a - b + c_2 <= 2(a - b) - 1, both below p and so carrying nothing out, with x + y <= 2a - 2 <= p - 1. Between a and 2a - 1 the pair can leave a state: (4, 1) at p = 5 in state (0, 1), and (5, 1) at p = 7 in state (0, 2).
  • The check. Verified. The count ((p+1)/2)^L, read off Legendre's digit sums v_p(C(ak, bk)) = (s_p(bk) + s_p((a-b)k) - s_p(ak))/(p - 1) directly, at every 2 <= a <= 7, 1 <= b < a, prime a < p <= 37 and p^L <= 200000, with 0 mismatches; at odd p <= a it can fail, (3, 1) at p = 3 holding 1 integer below 3^11 against 2048 and (4, 1) holding 8997. The row count (p+1)/2 at all 73654 states of every (a, b) with a <= 12 and every prime a < p < 400, 0 off, and the pair present in every state at p >= 2a - 1 (verb family, 4 seconds).

The matrix transform

  • The product. Proved. For real u let M(u) be the 2 x 2 matrix with entries M_(c c')(u) = sum_(d in D_(c c')) e(d u), e(x) = exp(2 pi i x). Let K_i^(c) be the k < p^i in K whose word of length i ends in state c, and hat K_i^(c)(u) the sum of e(k u) over them. The digit d_j contributes e(d_j p^j u) to the kernel of the move it makes, so hat K_i^(c)(u) = e_0^T M(u) M(p u) ... M(p^(i-1) u) e_c, and hat K_i = hat K_i^(0) + hat K_i^(1) is the same product against the all-ones vector 1. Every entry is a Dirichlet kernel, abs(M_(c c')(u)) = abs(sin(pi n u)/sin(pi u)) with n = abs(D_(c c')). At (2, 1) there is one state and the product is the level transform hat F_i of mobius.
  • The row-0 basis. Proved. With P = [[1, 0], [1, 1]] put N(u) = P^(-1) M(u) P. Then N_00 = M_00 + M_01 = hat F*, the transform of the row-0 design, N_01 = M_01, N_10 = (M_10 + M_11) - (M_00 + M_01) and N_11 = M_11 - M_01; since P e_0 = 1 and e_0^T P = e_0^T, hat K_i(u) = e_0^T N(u) N(p u) ... N(p^(i-1) u) e_0, and hat K_i^(c) is the same product against P^(-1) e_0 = (1, -1) or P^(-1) e_1 = (0, 1). The second row is small. At p = 1 mod 6, N_10(u) = e((p-1) u/2) - e((p-1) u/3) and N_11(u) = e((p-1) u/2); at p = 5 mod 6, N_10(u) = N_11(u) = e((p-1) u/2) - e((2p-1) u/3); in both, abs(N_10(u)) = 2 abs(sin(pi n_1 u)) with n_1 = abs(D_01), which is (p-1)/6 or (p+1)/6. So the transform of K is that of the digit design F* corrected through a second row of two-term sums.
  • The transfer inequality. Proved. For a nonnegative row vector function psi of period 1 put (T psi)(t) = sum_(r < p) psi((t+r)/p) abs(N((t+r)/p)), abs taken entrywise. For a nonnegative column w and real s let W_i(s; psi) = sum_(a < p^i) psi(u_a) abs(N(u_a)) abs(N(p u_a)) ... abs(N(p^(i-1) u_a)) w with u_a = s + a/p^i. Peeling the lowest digit, a = a' + p^(i-1) r puts u_a = (t + r)/p with t = p s + a'/p^(i-1), and p^j u_a = p^(j-1) t mod 1 at j >= 1, so the higher factors are free of r and W_i(s; psi) = W_(i-1)(p s; T psi); by induction W_i(s; psi) = (T^i psi)(p^i s) w. The triangle inequality gives Sigma_i(s) = sum_(a < p^i) abs(hat K_i(s + a/p^i)) <= W_i(s; e_0^T) with w = e_0, and T is monotone. So if psi >= e_0^T entrywise, psi_0 <= 1 and T psi <= lambda psi everywhere, then Sigma_i(s) <= lambda^i at every i and every real s, and the shifted sums of hat K_i^(c) are at most (psi_0 + psi_1) lambda^i through w = (1, 1). At (2, 1) this is the transfer operator of the half interval; there it is an identity, here the triangle inequality across the two paths through the second row is a loss, read in The true rate.
  • The l^infinity input. Proved. The row of state c in abs(M(u)) sums to at most fill - 2 + 2 abs(cos(pi u)): it carries fill digits, and its kernel to state 0 holds 0 and 1, whose two terms sum to abs(1 + e(u)) = 2 abs(cos(pi u)). So the max-row-sum norm has norm(M(u))_inf <= fill - 2 + 2 abs(cos(pi u)) and abs(hat K_i^(c)(u)) <= prod_(j < i) (fill - 2 + 2 abs(cos(pi p^j u))), which is the per-position bound from which Lemma A and its window and perturbed forms on coprime proceed for a digit set holding a consecutive pair. The rows all sum to fill, so the max-row norm is the Perron-weighted norm, and with the pair in both states it contracts at a good digit in either state, not once per orbit of the automaton.

The certificate

  • The certificate. Proved. At every prime p >= 13 put L = log(p/2), n_1 = abs(D_01), and with the constants nu^+ = 1.854292, H^+ = 5.672774, nu_1^+ = 1.287903 and H_1^+ = 3.861981 of the bullet below, A* = fill + (p/(2 pi))(2 nu^+ L + H^+) + (3/2)(p - 1) + (1 - 2/pi) p, B* = n_1 + (p/(2 pi))(2 nu_1^+ L + H_1^+) + (p - 1)/6 + (1 - 2/pi) p/2, C* = 2 csc(pi/(2p)), D* = p at p = 1 mod 6 and D* = C* at p = 5 mod 6, lambda = (A* + D*)/2 + sqrt(((A* - D*)/2)^2 + B* C*) and eta = (lambda - A*)/C*. Then psi = (1, eta) has T psi <= lambda psi, so Sigma_i(s) <= lambda^i at every i and every real s, the shifted sums of each hat K_i^(c) are at most (1 + eta) lambda^i, and K carries a certificate with p^(alpha_1) = lambda/fill. Proof. With delta_r = (t + r)/p, T psi(t) = (G*(t) + eta C(t), G_01(t) + eta D(t)) for the sums over r < p of abs(hat F*(delta_r)), abs(M_01(delta_r)), abs(N_10(delta_r)) and abs(N_11(delta_r)). If they sit under A*, B*, C* and D*, then T psi <= (A* + eta C*, B* + eta D*) = lambda (1, eta), the second entry because eta (lambda - D*) = B* is the characteristic equation (lambda - A*)(lambda - D*) = B* C*. Each sum has period 1 and is even about t = 1/2, since N(-u) is the conjugate of N(u), so take t in [0, 1/2].
    • C and D. abs(N_10(delta)) = abs(e(n_1 delta) - 1), and n_1 r runs over every residue with r since p does not divide n_1, so C(t) = 2 sum_(s < p) sin(pi (sigma + s)/p) with sigma the fractional part of n_1 t, and the geometric sum gives C(t) = 2 cos(pi (sigma - 1/2)/p)/sin(pi/(2p)) <= C*. At p = 1 mod 6, abs(N_11) = 1 and D = p; at p = 5 mod 6, D = C.
    • G*. The points are the low delta = z/p with z = j + t, 0 <= j <= J = (p-1)/2, and the high delta = 1 - z/p with z = j + 1 - t, 0 <= j <= J - 1, all with z <= p/2. With F* = {0..n_0 - 1} u {s_1..s_1 + n_1 - 1}, n_0 = abs(D_00) and s_1 = (p+1)/2, a point carries abs(hat F*) = abs(num_z)/(2 sin(pi z/p)) with num_z = e(n_0 z/p) - 1 + e((s_1 + n_1) z/p) - e(s_1 z/p), the high points giving its conjugate. Here n_0/p = 1/3 + c_0/p, (s_1 + n_1)/p = 2/3 + c_2/p and s_1/p = 1/2 + 1/(2p) with c_0 + c_2 = 1 (2/3 and 1/3 at p = 1 mod 6, 1/3 and 2/3 at p = 5 mod 6), so abs(num_z - num^0(z)) <= 2 pi (c_0 + c_2 + 1/2) z/p = 3 pi z/p for the period-6 function num^0(z) = e(z/3) - 1 + e(2z/3) - e(z/2); write a(z) = abs(num^0(z)). By csc w <= 1/w + (2/pi)(1 - 2/pi) w on (0, pi/2], the chord of the convex csc w - 1/w, and abs(num_z) <= 4, every point with z >= 1/2 carries at most (p/(2 pi)) a(z)/z + 3/2 + 4 (1 - 2/pi) z/p, and the point z = t at most fill. The p - 1 points pay 3/2 each, and their z sum to (p^2 - 1)/4, so the last terms pay at most (1 - 2/pi) p. For the main part group the low j >= 1 by class rho in {1..6} mod 6 and the high j by rho in {0..5}: sum_(q >= 0, rho + 6q <= J) 1/(6q + rho + t) <= 1/(rho + t) + (1/6) log((J + t)/(rho + t)) from 1/(6q + y) <= int_(q-1)^q dx/(6x + y), every class being nonempty at p >= 13, and the same on the high side with J - t in place of J + t. The numerators log(J + t) and log(J - t) are at most L, and a(-z) = a(z) makes the high classes average to the same nu(t) = (1/6) sum_(rho < 6) a(rho + t), so the main part is at most (p/(2 pi))(2 nu(t) L + H(t)) with H(t) = sum_(rho = 1..6) a(rho + t) w(rho + t) + sum_(rho = 0..5) a(rho + 1 - t) w(rho + 1 - t) and w(z) = 1/z - (log z)/6. So G*(t) <= fill + (p/(2 pi))(2 nu(t) L + H(t)) + (3/2)(p - 1) + (1 - 2/pi) p <= A*.
    • G_01. The same with num_z = e(n_1 z/p) - 1, n_1/p = 1/6 - 1/(6p) or 1/6 + 1/(6p), drift pi z/(3p) paying 1/6 a point, abs(num_z) <= 2, a_1(z) = abs(e(z/6) - 1) in place of a, giving nu_1 and H_1, and the point z = t paying at most n_1: G_01(t) <= n_1 + (p/(2 pi))(2 nu_1(t) L + H_1(t)) + (p - 1)/6 + (1 - 2/pi) p/2 <= B*. □
  • The constants. Proved. On a grid of 200001 points of [0, 1/2], nu, H and nu_1 peak at t = 1/2, reading 1.854280049, 5.672677439 and 1.287901102, and H_1 at t = 0, reading 3.861955914; the Lipschitz constants 3 pi for a, pi/3 for a_1, and 76.89 and 19.89 for H and H_1 term by term, w being monotone, bound each maximum by its grid maximum plus half a grid step times the constant, and the printed nu^+, H^+, nu_1^+, H_1^+ round that up at the sixth decimal (verb wall). At t = 0 the row-0 numerator reads a = 0, 1, 3, 2, 3, 1 at z = 0..5, so nu(0) = 5/3, and nu^+/nu(0) = 1.1126: the one-step weight pays 11% of the leading term for reading t = 1/2, against the sqrt 2 the half interval's one-step constant pays.
  • The wall. Proved. alpha_1 = log_p(lambda/fill) < 1/5 at every prime p >= 13567831. The tail: at every prime p >= 13, lambda/fill <= (2 nu^+/pi) log p + c_inf with 2 nu^+/pi <= 1.180479 and c_inf = 4 + 2(1 - 2/pi) + (H^+ - 2 nu^+ log 2)/pi + (8/pi) nu_1^+/nu^+ <= 7.482879. Proof. A*/fill < 1 + (1/pi)(2 nu^+ L + H^+) + 3 + 2(1 - 2/pi) by p/(p + 1) < 1. Next lambda - A* <= B* C*/(A* - D*) by sqrt(X^2 + 4Y) <= X + 2Y/X, and C*/fill < 8/pi by csc w <= 1/w + (2/pi)(1 - 2/pi) w. Scaled by 2 pi/p, B*/(A* - D*) = (2 nu_1^+ L + H_1^+ + beta_1)/(2 nu^+ L + H^+ + beta_0) with beta_1 <= 2 pi (1/3 + (1 - 2/pi)/2) and beta_0 >= 2 pi (3 - 6/pi) - (2 pi/13)(1 + 2(1 - 2/pi)/13), the latter from D* <= C* <= 4p/pi + 2(1 - 2/pi)/p, and (H_1^+ + beta_1) nu^+ < (H^+ + beta_0) nu_1^+ in interval arithmetic, so B*/(A* - D*) <= nu_1^+/nu^+ at every L > 0. The tail gap p^(1/5) - (2 nu^+/pi) log p - c_inf increases wherever p^(1/5) > 10 nu^+/pi, from 7164, and is positive from 14133194, a cell computed with the interval values of 2 nu^+/pi and c_inf and not their six-decimal prints, with which it turns positive at 14133200, no prime lying in 14133195..14133208; the closed form lambda/fill is certified below p^(1/5) at 120 bits at all 34446 primes 13567831..14133194, the least gap 4.8500 * 10^-6 at 13567859, and fails at the prime 13567811, a prime 5 mod 6, gap <= -9.8373 * 10^-6. At P_0 = 13567831, a prime 1 mod 6, 1/5 - alpha_1 >= 7.5864 * 10^-5 and eta <= 0.614465; the least margin over the certified primes is 1/5 - alpha_1 >= 1.1060 * 10^-8, at 13567859. Against 1/4 the same closed form clears at every prime from 227189, certified at all 912 primes 227189..238541 with the tail from 238541, failing at 227177, and 1/4 - alpha_1 >= 2.3452 * 10^-7 at 227189 (verb wall, 7 seconds).
  • The spread, and what sits near the cut. Verified, values of the closed form printed by the generator. The upper ends of alpha_1 at the first prime above 10^e in each class of p mod 12, the class written (p mod 3, p mod 4):
e(1, 1)(2, 1)(1, 3)(2, 3)
31009: 0.39412901013: 0.39446231039: 0.39280431019: 0.3941939
410009: 0.314101110037: 0.314308710039: 0.314020710007: 0.3143893
5100057: 0.2636504100049: 0.2638250100003: 0.2636600100019: 0.2638304
61000033: 0.22869761000037: 0.22881171000003: 0.22869801000151: 0.2288103
710000141: 0.202858210000121: 0.202937610000303: 0.202858010000019: 0.2029377
8100000081: 0.1828764100000037: 0.1829339100000039: 0.1828764100000007: 0.1829339
91000000009: 0.16689901000000097: 0.16694191000000087: 0.16689901000000007: 0.1669419

The class mod 4 does not enter the closed form and the class mod 3 enters only through D*, the p = 2 mod 3 column sitting higher by under 10^-4 from 10^7. Within 0.02 of the cut the certificate is slow: at p = 1 mod 6 it reads alpha_1 > 0.22 at the prime 2025109 and < 0.22 at the next prime of the class, 2025169, and > 0.18 at 146240491 and < 0.18 at 146240557; at p = 5 mod 6 the same crossings sit at 2042657, 2042681 and at 147319097, 147319253. The band abs(alpha_1 - 1/5) < 0.02 spans almost two decades of p, each decade moving the exponent by about 0.02, so a constant shaved off lambda/fill moves the wall by a large factor in p (verb wall).

The theorem on the Kummer set

  • The theorem. Proved. At every prime p >= 13567831 there are C, c > 0 computable from p alone with abs(M_K(x)) <= C A_K(x) exp(-c sqrt(log x)) and abs(psi_K(x) - (p/(p+1)) A_K(x)) <= C A_K(x) exp(-c sqrt(log x)) at every x >= 2, K the set of k with p not dividing C(3k, k): the Mobius function cancels on K against its own mass, and the primes of K up to x are counted. The proof is the unconditional dissection of mobius and its von Mangoldt form on coprime, section The dissection for the von Mangoldt function, run on the certificate above with the replacements of the four bullets below; every step they do not name reads neither a digit set nor the set and runs verbatim.
  • The blocks, indexed by state. Proved. Let x have L digits x_j. An element k < x of K with L digits first falls below x at a position j where its digit f is below x_j, so k = P p^j + t with t < p^j and P the digits of x above j followed by f. Then k lies in K exactly when t lies in K_j^(c) for the state c that t ends in and the digits of P are accepted read from state c. So K below x splits into blocks P p^j + K_j^(c), at most fill per state and scale since f must be allowed in state c, the shorter elements K_(L-1)^(0) u K_(L-1)^(1) less 0, and x itself: at most 2 fill + 2 blocks per scale. A block's sum of mu is y^(-1) sum_(a mod y) hat K_j^(c)(a/y) S_P(-a/y) with y = p^j, by orthogonality mod y, as in the blocks bullet there, and A_K(x) >= A_K(p^(L-1)) = fill^(L-1) by the mass, so the scales below L - K weigh at most ((2 fill + 2)/(fill - 1)) fill^(L-K) <= C fill^(1-K) A_K(x).
  • Region A and the hybrid bound. Proved. Region A reads the unshifted sum of hat K_k^(c), at most (1 + eta) lambda^k = (1 + eta) fill^k y^(alpha_1). For the hybrid l^1 bound write hat K_k^(c)(t) = e_0^T Pi_1(t) Pi_2(V_1 t) Pi_3(y t/V_2) e_c with Pi_1, Pi_2, Pi_3 the products of M over the lowest i_1, the middle and the top i_2 positions. abs(u^T B w) <= norm(u)_1 norm(B)_inf norm(w)_inf and norm(M)_inf <= fill give abs(hat K_k^(c)(t)) <= f(t) fill^(k - i_1 - i_2) g(y t/V_2) with f(t) = norm(e_0^T Pi_1(t))_1, the sum over c' of abs(hat K_(i_1)^(c')(t)), and g(v) = norm(Pi_3(v) e_c)_inf. The top factor at residues distinct mod V_2 pays at most sum_(a < V_2) sum_(c') abs(e_(c')^T Pi_3(a/V_2) e_c), the transfer inequality from the start row (e_0 + e_1)^T P = (2, 1), so at most max(2, 1/eta)(1 + eta) lambda^(i_2). The bottom factor enters through 4 D^2 norm(f)_1 + norm(f')_1: norm(f)_1 <= V_1^(-1) (1 + 2 eta) lambda^(i_1), the shifted sums integrated over the shift; differentiating the product one matrix at a time, norm(M'(v))_inf <= pi p (p - 1) since a row's digits sum to at most p(p-1)/2, the matrices above the differentiated one pay fill each by norm(v C)_1 <= norm(v)_1 norm(C)_inf and those below pay the integrated l^1 norm, so norm(f')_1 <= pi p (p - 1)(1 + 2 eta) sum_(j < i_1) lambda^j fill^(i_1 - 1 - j) <= 2 pi p (1 + 2 eta) lambda^(i_1), using lambda >= 2 fill. So a class R(D, H) pays at most C_p fill^k (V_1 V_2)^(alpha_1) with C_p from p alone, the shape of the hybrid bound there, and region B, which asks alpha_1 < 1/4, runs verbatim.
  • Regions C1 and C2. Proved. At a C1 point l/d + eta' the l^infinity input supplies the per-position bound with the pair {0, 1} of difference 1, which is all the perturbed Lemma A' on coprime reads at each position besides the orbit of p^l (l/d + eta'); so abs(hat K_k^(c)(a/y)) <= fill^k c'^(floor(2k/(3 m_d))) with c' = 1 - (2/fill)(1 - cos(pi/(4p))), as there. Region C2 reads the transform only through abs(hat K_k^(c)) <= abs(K_k^(c)) <= fill^k. The assembly runs verbatim at fill = (p+1)/2.
  • The main term is p/(p+1). Proved. In the von Mangoldt form the principal characters of C2 give a block the main term (p/(p-1)) #{t in K_k^(c) : p does not divide t}, by the identity of coprime, which holds over any finite set of t. A word of K_k^(c) is divisible by p exactly when its units digit is 0, which keeps state 0, so those number abs(K_(k-1)^(c)), and by the mass section abs(K_k^(c)) - abs(K_(k-1)^(c)) = fill^(k-1)(fill - 1) pi_c at k >= 2, since lambda_2^k = lambda_2^(k-1) when lambda_2 is 0 or 1. The main term is (p/(p-1))((fill - 1)/fill) fill^k pi_c = (p/(p+1))(abs(K_k^(c)) - lambda_2^k (delta_(0c) - pi_c)): the constant p/(p+1) of the half interval at a prime, up to at most 1 a block and (2 fill + 2) L in all, far inside the error.
  • What the theorem reads off K. The certificate below 1/5 at s = 0 for region A and at every shift for the bottom factor of the hybrid bound, alpha_1 < 1/4 for region B, the per-position bound with the pair for C1, and the counts abs(K_k^(c)) for C2, the mass floor and the main term. A carry automaton enters through nothing else.
  • The meter. Verified. Far below the wall, max abs(M_K)/A_K^(1/2) up to 10^7 reads 0.834, 0.993 and 0.583 at p = 101, 1009 and 10007, and psi_K/((p/(p+1)) A_K) reads 1.0033, 1.0024 and 0.9999, sanity prints that are evidence for nothing (verb meter, 2 seconds). At the smallest primes, up to 10^8, psi_K/((p/(p+1)) A_K) with prime powers reads 1.0032, 1.0041, 1.0010 and 1.0051 at p = 5, 7, 11 and 13, A_K(10^8) counted exactly through the blocks by state: the shape p/(p+1) holds far below the wall, a falsification line and no evidence for the theorem (verb small, 3 seconds).

Every pair (a, b)

  • The theorem on a certificate. Proved. Let a > b >= 1 and let p >= 2a - 1 be prime. If K_(a,b) carries a matrix certificate below 1/5, an invertible P with P e_0 = 1 and a weight psi, bounded and bounded away from 0 in every entry, with psi >= abs(e_0^T P) entrywise and T psi <= lambda psi for the operator of N = P^(-1) M P on its b(a - b) states and lambda/fill < p^(1/5), then the theorem above holds on K_(a,b) with the constant p/(p+1). The four bullets of the section above transfer: the blocks are indexed by the states, at most b(a - b)(fill + 1) per scale; the max-row bound holds since every row sums to fill and every state keeps the pair {0, 1} into (0, 0); region C2 reads only the counts. For the main term, a units digit 0 sends every state to (0, 0), so the words of K_k^(c) divisible by p number abs(K_(k-1)^(c)); on the states reachable from (0, 0) the count matrix is primitive, every state returning to (0, 0) on the digit 0 and (0, 0) keeping that loop, so abs(K_k^(c)) = fill^k pi_c + O(k^S abs(lambda_2)^k) with abs(lambda_2) < fill, S = b(a - b), and the main term is (p/(p+1)) abs(K_k^(c)) up to an error that saves a power of fill^k at the scales the dissection keeps.
  • The row-0 constant is 3 - 4 gcd(a, b)/a. Proved. Row (0, 0) keeps the d with {bd/p} + {(a-b)d/p} < 1, and as p grows these fill, up to O(a) digits, the union F*_(a,b) of the intervals where {b theta} + {(a-b) theta} < 1 in [0, 1), of measure 1/2. Its numerator at an integer z, the sum of e(beta z) - e(alpha z) over its intervals [alpha, beta), is 2 pi i z times the Fourier coefficient of the indicator, and the indicator is 1 - {b theta} - {(a-b) theta} + {a theta}, whose term {c theta} contributes at z != 0 only when c divides z, with coefficient of modulus c/(2 pi abs(z)). So the numerator has modulus abs(V(z)), V(z) = b [b | z] + (a - b) [(a-b) | z] - a [a | z]. When a divides z, V(z) <= b + (a - b) - a = 0, so abs(V) = V - 2 V [a | z]; over a period V averages 1 + 1 - 1 = 1 and V [a | z] averages b/lcm(a, b) + (a - b)/lcm(a, a - b) - 1 = 2g/a - 1 with g = gcd(a, b) = gcd(a, a - b). So the row-0 numerator at t = 0 averages nu_(a,b)(0) = 3 - 4g/a: 1 at (2, 1), 5/3 at (3, 1), 2 at (4, 1), 11/5 at every (5, b), rising to 3. (Verified: the limit design and its average are recomputed from the breakpoints for every a <= 7, (2/pi) nu_(a,b)(0) reading 0.636620, 1.061033, 1.273240, 1.400563, 1.485446, 1.546077 at a = 2..7 with b = 1, and at p = 10007 row (0, 0) misses the limit design, and every other row misses row (0, 0) with its moves, by at most 2a - 4 digits, 10 at a = 7; verb family.)
  • What stays open. Conjecture. For every a > b >= 1 the row-0 operator of K_(a,b) has rate (2/pi)(3 - 4 gcd(a, b)/a) log p + O_a(1) against (p+1)/2, so the set carries a certificate below 1/5 and the Mobius bound and prime count from some prime P_0(a, b); the rate is read only at (3, 1), and at a <= 7 only the limit constant and the row deviations at p = 10007 are computed (verbs rate and family). The row-0 basis asks only that the rows differ in O(a) digits, which the bullet above reads at p = 10007; the step not written is the analytic bound of the certificate section at a general union of intervals with breakpoints in (1/a)Z u (1/b)Z u (1/(a-b))Z and with a second block of b(a - b) - 1 rows. Unconditionally the theorem stands at (2, 1) from 94939 and at (3, 1) and (3, 2) from 13567831. At g > 1 the constant drops: nu_(4,2)(0) = 1, the half interval's, and K_(4,2) is the set of k with 2k in the half interval, read by a carry automaton of its own.

The true rate

  • The rate of T. Verified, as readings that bound nothing. Power iteration of the row-0 operator T on 100 cells with linear interpolation reads lambda_T/fill at 10.5899, 10.7000, 10.6220 and 10.7064 at 1009, 1013, 1039 and 1019, at 13.0797, 13.1686, 13.0829 and 13.1654 at 10009, 10037, 10039 and 10007, and at 15.5549 at 100003. Above (10/(3 pi)) log p that is 3.251 and 3.252 at p = 1 mod 3 against 3.357 at p = 2 mod 3 near 10^3, and 3.306 against 3.392 near 10^4: the class mod 3 moves the offset by about 0.09, through D, and the class mod 4 by under 0.001. In the class 1 mod 3 the offsets climb 3.251, 3.306, 3.339 at 1009, 10009, 100003, about 0.019 per unit of log p, as consistent with a leading coefficient near 1.08 as with 10/(3 pi) = 1.0610, and the run at 100003 uses 60 cells and 15 iterations against 100 and 25: the readings do not single out the constant. The leading term (10/(3 pi)) log p = (2/pi) nu(0) log p is the row-0 design's, the minimum of nu at t = 0 and not its maximum, as at the half interval. The certificate reads 15.27 at 1009 and 18.05 at 10009, 4.7 and 5.0 above T: the one-step weight pays (2/pi)(nu^+ - 5/3) log p, and the drift and chord terms of the proof the rest (verb rate).
  • The rate of K itself. Verified, as readings. The exact unshifted sums Sigma_L(0), by FFT, give Sigma_L/Sigma_(L-1)/fill at 6.2920, 6.3321, 6.3570 and 6.3957 at 101, 103, 107 and 109 at level 3, and at 8.8244, 8.8237, 8.8301 and 8.8684 at 1009, 1013, 1019 and 1051 at level 2, from 1.395 to 1.486 above (10/(3 pi)) log p, while the row-0 design F* alone reads 0.036 to 0.065 lower at the same primes. So the l^1 mass of K is that of F* up to a few hundredths, and the triangle inequality across the second row, which T pays at every digit, costs about 1.8 against fill at p near 10^3. Carried to the bar, the offset 3.339 of T at 100003 meets p^(1/5) near 2.44 * 10^6 and the offset 1.486 of K near 1.15 * 10^6: the wall 13567831 is the certificate's and not the route's, and a certificate reading the two paths of the second row together, or the weight 1 + beta abs(sin(pi t)) of the half interval, moves it down; neither is written here (verb rate, 22 seconds).

What is in print

  • Read at source. Verified. The indicator of every Kummer set is p-automatic, read by the carry automaton above. Mullner 2017 proves that automatic sequences fulfil the Sarnak conjecture, so M_K(x) = o(x) with no rate; since A_K(x) grows like x^(alpha_p) with alpha_p < 1, that bound is weaker than the trivial abs(M_K(x)) <= A_K(x), as mobius records for the digit designs. Adamczewski, Drmota and Mullner 2022, read in its arXiv abstract, prove that the logarithmic densities of every automatic sequence along the primes exist and are computable; on K, a set of density 0, that density is 0, and nothing is said at the scale A_K(x)/log x. The prime theorems of Maynard 2019 and Maynard 2022, as restated at source on mobius and coprime, are stated for digit designs, every digit restricted on its own, and K is not one by the witness of the first section; at (2, 1) they carry the prime asymptotic on the half interval at sufficiently large base. Han, Rahimi and Yang 2026, read in its abstract, verify a localized Fourier criterion for prime pairs whose difference has restricted digits by a transfer-operator argument, again on digit designs. Deshouillers, Drmota and Mullner 2015, read at the authors' text, prove in Theorem 1.2 that every automatic sequence of a synchronizing automaton read from the most significant digit fulfils the Sarnak conjecture, o(N) with no rate, the units-first reading being the case of their Section 3, and their Lemma 2.2 puts the words of length n that are not synchronizing at O(k^(n(1 - eta))) in base k. K's automaton completed with a refusing sink is synchronizing, the digit p - 1 being refused in both states, and K lies among the words that never reach the sink, a sparse support of that kind; neither the abstract nor Theorem 1.2 carries a rate. The prime number theorem in the abstract of Mullner 2017 asks a strongly connected automaton whose initial state is fixed by the digit 0, and the sink breaks strong connection.
  • What the certificate route adds. On the Kummer set K = K_(3,1) at every prime p >= 13567831: a Mobius bound against the set's own mass and a prime count with the constant p/(p+1), both with a saving of zero-free-region shape and constants computable from p, and an explicit least prime; on every K_(a,b), the exact count ((p+1)/2)^L, the pair, the row-0 constant and the theorem wherever a matrix certificate below 1/5 exists.

Generators

  • lab/py/kummer-carry, one file, seven verbs. kummer: the automaton against Kummer's count, the digit sets, the witness against a digit design. family: the count ((p+1)/2)^L over the pairs (a, b), the row count, the pair, the product-set test below p^3, the row-0 limit designs and their constant 3 - 4 gcd(a, b)/a. wall: the constants nu^+, H^+, nu_1^+, H_1^+, the closed form of lambda at 120 bits, the walls at 1/5 and 1/4 with the tail, the spread by class and the band near the cut. check: the four sums against their bounds and closed forms at every prime 13..401 and six larger primes on 201 shifts, the transfer identity at level 3, and the shifted grid sums against lambda^i. rate: the readings of the last section. meter and small: the sanity meter and the prime count at the smallest primes.
  • The Kummer sets demo runs the automaton of every K_(a,b) with a <= 9 at every odd prime p <= 101 through the crate mrlyrs::num::kummer: the board level by level, each cell inked by the carry state its word ends in, the digits each state keeps and where it sends the carry, the count below p^L against ((p+1)/2)^L and where it fails at p <= a, the witness u, v p, u + v p, and one k read column by column beside v_p(C(a k, b k)) by Legendre's digit sums.
  • The falsification. Verified. At every prime 13..401 and at 1009, 1013, 10007, 10009, 100003 and 100019, on 201 shifts of [0, 1/2], G* stays under its pointwise bound, at most 0.765814 of it, G_01 at most 0.897928, C and D meet their closed forms, and T psi stays under lambda psi, at most 0.775433 and 0.905536 of it in the two entries; the product formula and the row-0 basis meet the direct transform at level 3 at p = 13 and 31 to 4.0 * 10^-10; and the shifted sums Sigma_i(s) at nine primes 13..43, four shifts and every level with p^i <= 2 * 10^6 stay under lambda^i, at most 0.480589 of it (verb check, 10 seconds).