
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 >= 5and read the digitsd_0, d_1, ..ofkfrom the lowest, starting in state0. In stateca digitdis allowed and moves to state0when3d + c <= p - 1, is allowed and moves to state1when2d + c >= pand3d + c <= 2p - 1, and is refused otherwise. Thenklies inKexactly when every digit is allowed. Proof. By Kummer 1852,v_p(C(m + n, m))is the number of carries in the additionm + nat basep, andC(3k, k) = C(k + 2k, k). The doubling2khas digite_i = 2 d_i + c_i - p c_(i+1)withc_0 = 0andc_(i+1) = 1exactly when2 d_i + c_i >= p, andc_i <= 1since2(p - 1) + 1 < 2p; the state is this carry. If no carry ofk + 2karrives at positioni, the column there sumsd_i + e_i = 3 d_i + c_i - p c_(i+1), which is at mostp - 1exactly under the two allowed cases,3d + c <= p - 1forcing2d + c <= p - 1. Above the top digit2kholds the single digitc_L <= 1against a zero ofk, a column sum at most1. Sok + 2kcarries nowhere exactly when every digit is allowed. The digit0is allowed in both states and moves to state0, so leading zeros change nothing andKbelowp^Lis the set of accepted words of lengthL. □ - The digit sets. Proved. Write
D_(c c')for the digits read in statecthat move to statec'. 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)}andD_11 = {(p-1)/2..floor((2p-2)/3)}, four intervals. Atp = 1 mod 6they have(p+2)/3,(p-1)/6,(p-1)/3and(p+5)/6digits,D_10beingD_00less its top digit(p-1)/3andD_11beingD_01with(p-1)/2added; atp = 5 mod 6they have(p+1)/3,(p+1)/6,(p+1)/3and(p+1)/6, withD_10 = D_00andD_11 = D_01 - 1. Either way each state keeps exactlyfill = (p+1)/2digits, and both states keep the consecutive pair{0, 1}inside the kernel to state0. State0keeps the two intervalsF* = 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. Atp = 3state0keeps only the digit0, soK = {0}:3dividesC(3k, k)at everyk >= 1. - A width-2 rule and not a digit design. Proved. An allowed digit moves to state
1exactly when it is at least(p-1)/2, so the state after a digit is a function of that digit andKis the set ofkwhose word, with one0placed below the units digit, has every window of two adjacent digits allowed: a width-2 rule of the memory dial on beneath at basep, read from the units end. It is no product set. Letu = (p+1)/2, which moves state0to state1, and letvbe a digit allowed in state0and refused in state1,v = (p-1)/3atp = 1 mod 6andv = (2p-1)/3atp = 5 mod 6. Thenuandv plie inKandu + v pdoes not, while a digit design holdinguandv pholdsu + v p. Atp = 7that is4 = 4_7and14 = 20_7inKand18 = 24_7outside it, the sum24 + 51of18and36carrying at position1. - The check. Verified. The automaton against Kummer's carry count
(s_p(k) + s_p(2k) - s_p(3k))/(p - 1),s_pthe digit sum, with0mismatches: at everyk < p^5forp = 5, 7, 11, 13; at everyk < 101^3directly; and at everyk < 101^5 = 10510100501throughk = 101^2 q + r, where the digit sums ofk,2kand3ksplit exactly over the carriesfloor(2r/101^2)andfloor(3r/101^2), so that the automaton's verdict and the count are compared on all61value pairs of the carry classes and so on everyk. The four intervals, the row sums and the pair hold at every prime5..2999, the witnessu, v p, u + v pat all428of them, andKholds exactly((p+1)/2)^5integers belowp^5at all five primes,345025251at101(verbkummer, under a second).
The mass of every Kummer set
- The automaton of every pair. Proved. Let
a > b >= 1and letp > abe prime. SinceC(ak, bk) = C(bk + (a-b)k, bk), Kummer's theorem makesK_(a,b)the set wherebk + (a-b)kcarries nowhere. The state is the pair(c_1, c_2)of carries of the multiplications byband bya - b, withc_1 < bandc_2 < a - b. In state(c_1, c_2)the digitdmeets the digitsx = (bd + c_1) mod pofbkandy = ((a-b)d + c_2) mod pof(a-b)k; it is allowed whenx + y <= p - 1, and it moves to(floor((bd + c_1)/p), floor(((a-b)d + c_2)/p)), again below(b, a - b)sinceb(p-1) + b - 1 < bp. Above the top digitbkand(a-b)khold the single digitsc_1andc_2, whose sum is at mosta - 2 < p, so the top never carries, and the digit0is allowed in every state and moves to(0, 0). At(3, 1),c_1 = 0and 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)/2digits. Proved. In state(c_1, c_2)putz = (ad + c_1 + c_2) mod p. Thenx + y = z mod pand0 <= x + y <= 2p - 2, sox + y - zis0orp, and the digit is refused exactly when it isp. Asdruns over0..p-1, each ofx,yandzruns over every residue once, sincepdivides none ofb,a - banda. 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 keepsfill = (p+1)/2. □ - The mass. Proved. At every
a > b >= 1and every primep > a,K_(a,b)holds exactly((p+1)/2)^Lintegers in[0, p^L), since from every state exactlyfilldigits continue a word; soA(p^L) = fill^L,p^Litself lying in the set, andA(x)grows likex^(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 matrixM(0), entry(c, c')the number of digits takingctoc', the transform matrix of the next section at frequency0, has every row summing tofill, so its Perron root isfillexactly with right Perron vector the all-ones vector, and the set's dimension islog_p fill. At(3, 1)the count matrix is[[(p+2)/3, (p-1)/6], [(p-1)/3, (p+5)/6]]atp = 1 mod 6, with second eigenvaluelambda_2 = 1, and[[(p+1)/3, (p+1)/6], [(p+1)/3, (p+1)/6]]atp = 5 mod 6, rank one withlambda_2 = 0; in bothM(0) = fill 1 pi + lambda_2 (I - 1 pi)with left Perron vectorpi = (2/3, 1/3), so the words of lengthLending in statecnumber exactlyfill^L pi_c + lambda_2^L (delta_(0c) - pi_c). - The pair. Proved. At every prime
p >= 2a - 1every state keeps{0, 1}inside its kernel to(0, 0): the digit0meetsx + y = c_1 + c_2 <= a - 2, and the digit1meetsx = b + c_1 <= 2b - 1andy = a - b + c_2 <= 2(a - b) - 1, both belowpand so carrying nothing out, withx + y <= 2a - 2 <= p - 1. Betweenaand2a - 1the pair can leave a state:(4, 1)atp = 5in state(0, 1), and(5, 1)atp = 7in state(0, 2). - The check. Verified. The count
((p+1)/2)^L, read off Legendre's digit sumsv_p(C(ak, bk)) = (s_p(bk) + s_p((a-b)k) - s_p(ak))/(p - 1)directly, at every2 <= a <= 7,1 <= b < a, primea < p <= 37andp^L <= 200000, with0mismatches; at oddp <= ait can fail,(3, 1)atp = 3holding1integer below3^11against2048and(4, 1)holding8997. The row count(p+1)/2at all73654states of every(a, b)witha <= 12and every primea < p < 400,0off, and the pair present in every state atp >= 2a - 1(verbfamily, 4 seconds).
The matrix transform
- The product. Proved. For real
uletM(u)be the2 x 2matrix with entriesM_(c c')(u) = sum_(d in D_(c c')) e(d u),e(x) = exp(2 pi i x). LetK_i^(c)be thek < p^iinKwhose word of lengthiends in statec, andhat K_i^(c)(u)the sum ofe(k u)over them. The digitd_jcontributese(d_j p^j u)to the kernel of the move it makes, sohat K_i^(c)(u) = e_0^T M(u) M(p u) ... M(p^(i-1) u) e_c, andhat K_i = hat K_i^(0) + hat K_i^(1)is the same product against the all-ones vector1. Every entry is a Dirichlet kernel,abs(M_(c c')(u)) = abs(sin(pi n u)/sin(pi u))withn = abs(D_(c c')). At(2, 1)there is one state and the product is the level transformhat F_iof mobius. - The row-0 basis. Proved. With
P = [[1, 0], [1, 1]]putN(u) = P^(-1) M(u) P. ThenN_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)andN_11 = M_11 - M_01; sinceP e_0 = 1ande_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, andhat K_i^(c)is the same product againstP^(-1) e_0 = (1, -1)orP^(-1) e_1 = (0, 1). The second row is small. Atp = 1 mod 6,N_10(u) = e((p-1) u/2) - e((p-1) u/3)andN_11(u) = e((p-1) u/2); atp = 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))withn_1 = abs(D_01), which is(p-1)/6or(p+1)/6. So the transform ofKis that of the digit designF*corrected through a second row of two-term sums. - The transfer inequality. Proved. For a nonnegative row vector function
psiof period1put(T psi)(t) = sum_(r < p) psi((t+r)/p) abs(N((t+r)/p)),abstaken entrywise. For a nonnegative columnwand realsletW_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)) wwithu_a = s + a/p^i. Peeling the lowest digit,a = a' + p^(i-1) rputsu_a = (t + r)/pwitht = p s + a'/p^(i-1), andp^j u_a = p^(j-1) tmod1atj >= 1, so the higher factors are free ofrandW_i(s; psi) = W_(i-1)(p s; T psi); by inductionW_i(s; psi) = (T^i psi)(p^i s) w. The triangle inequality givesSigma_i(s) = sum_(a < p^i) abs(hat K_i(s + a/p^i)) <= W_i(s; e_0^T)withw = e_0, andTis monotone. So ifpsi >= e_0^Tentrywise,psi_0 <= 1andT psi <= lambda psieverywhere, thenSigma_i(s) <= lambda^iat everyiand every reals, and the shifted sums ofhat K_i^(c)are at most(psi_0 + psi_1) lambda^ithroughw = (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^infinityinput. Proved. The row of statecinabs(M(u))sums to at mostfill - 2 + 2 abs(cos(pi u)): it carriesfilldigits, and its kernel to state0holds0and1, whose two terms sum toabs(1 + e(u)) = 2 abs(cos(pi u)). So the max-row-sum norm hasnorm(M(u))_inf <= fill - 2 + 2 abs(cos(pi u))andabs(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 tofill, 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 >= 13putL = log(p/2),n_1 = abs(D_01), and with the constantsnu^+ = 1.854292,H^+ = 5.672774,nu_1^+ = 1.287903andH_1^+ = 3.861981of 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* = patp = 1 mod 6andD* = C*atp = 5 mod 6,lambda = (A* + D*)/2 + sqrt(((A* - D*)/2)^2 + B* C*)andeta = (lambda - A*)/C*. Thenpsi = (1, eta)hasT psi <= lambda psi, soSigma_i(s) <= lambda^iat everyiand every reals, the shifted sums of eachhat K_i^(c)are at most(1 + eta) lambda^i, andKcarries a certificate withp^(alpha_1) = lambda/fill. Proof. Withdelta_r = (t + r)/p,T psi(t) = (G*(t) + eta C(t), G_01(t) + eta D(t))for the sums overr < pofabs(hat F*(delta_r)),abs(M_01(delta_r)),abs(N_10(delta_r))andabs(N_11(delta_r)). If they sit underA*,B*,C*andD*, thenT psi <= (A* + eta C*, B* + eta D*) = lambda (1, eta), the second entry becauseeta (lambda - D*) = B*is the characteristic equation(lambda - A*)(lambda - D*) = B* C*. Each sum has period1and is even aboutt = 1/2, sinceN(-u)is the conjugate ofN(u), so taketin[0, 1/2].CandD.abs(N_10(delta)) = abs(e(n_1 delta) - 1), andn_1 rruns over every residue withrsincepdoes not dividen_1, soC(t) = 2 sum_(s < p) sin(pi (sigma + s)/p)withsigmathe fractional part ofn_1 t, and the geometric sum givesC(t) = 2 cos(pi (sigma - 1/2)/p)/sin(pi/(2p)) <= C*. Atp = 1 mod 6,abs(N_11) = 1andD = p; atp = 5 mod 6,D = C.G*. The points are the lowdelta = z/pwithz = j + t,0 <= j <= J = (p-1)/2, and the highdelta = 1 - z/pwithz = j + 1 - t,0 <= j <= J - 1, all withz <= p/2. WithF* = {0..n_0 - 1} u {s_1..s_1 + n_1 - 1},n_0 = abs(D_00)ands_1 = (p+1)/2, a point carriesabs(hat F*) = abs(num_z)/(2 sin(pi z/p))withnum_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. Heren_0/p = 1/3 + c_0/p,(s_1 + n_1)/p = 2/3 + c_2/pands_1/p = 1/2 + 1/(2p)withc_0 + c_2 = 1(2/3and1/3atp = 1 mod 6,1/3and2/3atp = 5 mod 6), soabs(num_z - num^0(z)) <= 2 pi (c_0 + c_2 + 1/2) z/p = 3 pi z/pfor the period-6 functionnum^0(z) = e(z/3) - 1 + e(2z/3) - e(z/2); writea(z) = abs(num^0(z)). Bycsc w <= 1/w + (2/pi)(1 - 2/pi) won(0, pi/2], the chord of the convexcsc w - 1/w, andabs(num_z) <= 4, every point withz >= 1/2carries at most(p/(2 pi)) a(z)/z + 3/2 + 4 (1 - 2/pi) z/p, and the pointz = tat mostfill. Thep - 1points pay3/2each, and theirzsum to(p^2 - 1)/4, so the last terms pay at most(1 - 2/pi) p. For the main part group the lowj >= 1by classrhoin{1..6}mod6and the highjbyrhoin{0..5}:sum_(q >= 0, rho + 6q <= J) 1/(6q + rho + t) <= 1/(rho + t) + (1/6) log((J + t)/(rho + t))from1/(6q + y) <= int_(q-1)^q dx/(6x + y), every class being nonempty atp >= 13, and the same on the high side withJ - tin place ofJ + t. The numeratorslog(J + t)andlog(J - t)are at mostL, anda(-z) = a(z)makes the high classes average to the samenu(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))withH(t) = sum_(rho = 1..6) a(rho + t) w(rho + t) + sum_(rho = 0..5) a(rho + 1 - t) w(rho + 1 - t)andw(z) = 1/z - (log z)/6. SoG*(t) <= fill + (p/(2 pi))(2 nu(t) L + H(t)) + (3/2)(p - 1) + (1 - 2/pi) p <= A*.G_01. The same withnum_z = e(n_1 z/p) - 1,n_1/p = 1/6 - 1/(6p)or1/6 + 1/(6p), driftpi z/(3p)paying1/6a point,abs(num_z) <= 2,a_1(z) = abs(e(z/6) - 1)in place ofa, givingnu_1andH_1, and the pointz = tpaying at mostn_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
200001points of[0, 1/2],nu,Handnu_1peak att = 1/2, reading1.854280049,5.672677439and1.287901102, andH_1att = 0, reading3.861955914; the Lipschitz constants3 pifora,pi/3fora_1, and76.89and19.89forHandH_1term by term,wbeing monotone, bound each maximum by its grid maximum plus half a grid step times the constant, and the printednu^+,H^+,nu_1^+,H_1^+round that up at the sixth decimal (verbwall). Att = 0the row-0 numerator readsa = 0, 1, 3, 2, 3, 1atz = 0..5, sonu(0) = 5/3, andnu^+/nu(0) = 1.1126: the one-step weight pays11%of the leading term for readingt = 1/2, against thesqrt 2the half interval's one-step constant pays. - The wall. Proved.
alpha_1 = log_p(lambda/fill) < 1/5at every primep >= 13567831. The tail: at every primep >= 13,lambda/fill <= (2 nu^+/pi) log p + c_infwith2 nu^+/pi <= 1.180479andc_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)byp/(p + 1) < 1. Nextlambda - A* <= B* C*/(A* - D*)bysqrt(X^2 + 4Y) <= X + 2Y/X, andC*/fill < 8/pibycsc w <= 1/w + (2/pi)(1 - 2/pi) w. Scaled by2 pi/p,B*/(A* - D*) = (2 nu_1^+ L + H_1^+ + beta_1)/(2 nu^+ L + H^+ + beta_0)withbeta_1 <= 2 pi (1/3 + (1 - 2/pi)/2)andbeta_0 >= 2 pi (3 - 6/pi) - (2 pi/13)(1 + 2(1 - 2/pi)/13), the latter fromD* <= C* <= 4p/pi + 2(1 - 2/pi)/p, and(H_1^+ + beta_1) nu^+ < (H^+ + beta_0) nu_1^+in interval arithmetic, soB*/(A* - D*) <= nu_1^+/nu^+at everyL > 0. The tail gapp^(1/5) - (2 nu^+/pi) log p - c_infincreases whereverp^(1/5) > 10 nu^+/pi, from7164, and is positive from14133194, a cell computed with the interval values of2 nu^+/piandc_infand not their six-decimal prints, with which it turns positive at14133200, no prime lying in14133195..14133208; the closed formlambda/fillis certified belowp^(1/5)at 120 bits at all34446primes13567831..14133194, the least gap4.8500 * 10^-6at13567859, and fails at the prime13567811, a prime5 mod 6, gap<= -9.8373 * 10^-6. AtP_0 = 13567831, a prime1 mod 6,1/5 - alpha_1 >= 7.5864 * 10^-5andeta <= 0.614465; the least margin over the certified primes is1/5 - alpha_1 >= 1.1060 * 10^-8, at13567859. Against1/4the same closed form clears at every prime from227189, certified at all912primes227189..238541with the tail from238541, failing at227177, and1/4 - alpha_1 >= 2.3452 * 10^-7at227189(verbwall, 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_1at the first prime above10^ein each class ofp mod 12, the class written(p mod 3, p mod 4):
e | (1, 1) | (2, 1) | (1, 3) | (2, 3) |
|---|---|---|---|---|
| 3 | 1009: 0.3941290 | 1013: 0.3944623 | 1039: 0.3928043 | 1019: 0.3941939 |
| 4 | 10009: 0.3141011 | 10037: 0.3143087 | 10039: 0.3140207 | 10007: 0.3143893 |
| 5 | 100057: 0.2636504 | 100049: 0.2638250 | 100003: 0.2636600 | 100019: 0.2638304 |
| 6 | 1000033: 0.2286976 | 1000037: 0.2288117 | 1000003: 0.2286980 | 1000151: 0.2288103 |
| 7 | 10000141: 0.2028582 | 10000121: 0.2029376 | 10000303: 0.2028580 | 10000019: 0.2029377 |
| 8 | 100000081: 0.1828764 | 100000037: 0.1829339 | 100000039: 0.1828764 | 100000007: 0.1829339 |
| 9 | 1000000009: 0.1668990 | 1000000097: 0.1669419 | 1000000087: 0.1668990 | 1000000007: 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 >= 13567831there areC, c > 0computable frompalone withabs(M_K(x)) <= C A_K(x) exp(-c sqrt(log x))andabs(psi_K(x) - (p/(p+1)) A_K(x)) <= C A_K(x) exp(-c sqrt(log x))at everyx >= 2,Kthe set ofkwithpnot dividingC(3k, k): the Mobius function cancels onKagainst its own mass, and the primes ofKup toxare 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
xhaveLdigitsx_j. An elementk < xofKwithLdigits first falls belowxat a positionjwhere its digitfis belowx_j, sok = P p^j + twitht < p^jandPthe digits ofxabovejfollowed byf. Thenklies inKexactly whentlies inK_j^(c)for the statecthattends in and the digits ofPare accepted read from statec. SoKbelowxsplits into blocksP p^j + K_j^(c), at mostfillper state and scale sincefmust be allowed in statec, the shorter elementsK_(L-1)^(0) u K_(L-1)^(1)less0, andxitself: at most2 fill + 2blocks per scale. A block's sum ofmuisy^(-1) sum_(a mod y) hat K_j^(c)(a/y) S_P(-a/y)withy = p^j, by orthogonality mody, as in the blocks bullet there, andA_K(x) >= A_K(p^(L-1)) = fill^(L-1)by the mass, so the scales belowL - Kweigh 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 hybridl^1bound writehat K_k^(c)(t) = e_0^T Pi_1(t) Pi_2(V_1 t) Pi_3(y t/V_2) e_cwithPi_1,Pi_2,Pi_3the products ofMover the lowesti_1, the middle and the topi_2positions.abs(u^T B w) <= norm(u)_1 norm(B)_inf norm(w)_infandnorm(M)_inf <= fillgiveabs(hat K_k^(c)(t)) <= f(t) fill^(k - i_1 - i_2) g(y t/V_2)withf(t) = norm(e_0^T Pi_1(t))_1, the sum overc'ofabs(hat K_(i_1)^(c')(t)), andg(v) = norm(Pi_3(v) e_c)_inf. The top factor at residues distinct modV_2pays at mostsum_(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 mostmax(2, 1/eta)(1 + eta) lambda^(i_2). The bottom factor enters through4 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 mostp(p-1)/2, the matrices above the differentiated one payfilleach bynorm(v C)_1 <= norm(v)_1 norm(C)_infand those below pay the integratedl^1norm, sonorm(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), usinglambda >= 2 fill. So a classR(D, H)pays at mostC_p fill^k (V_1 V_2)^(alpha_1)withC_pfrompalone, the shape of the hybrid bound there, and region B, which asksalpha_1 < 1/4, runs verbatim. - Regions C1 and C2. Proved. At a C1 point
l/d + eta'thel^infinityinput supplies the per-position bound with the pair{0, 1}of difference1, which is all the perturbed Lemma A' on coprime reads at each position besides the orbit ofp^l (l/d + eta'); soabs(hat K_k^(c)(a/y)) <= fill^k c'^(floor(2k/(3 m_d)))withc' = 1 - (2/fill)(1 - cos(pi/(4p))), as there. Region C2 reads the transform only throughabs(hat K_k^(c)) <= abs(K_k^(c)) <= fill^k. The assembly runs verbatim atfill = (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 oft. A word ofK_k^(c)is divisible bypexactly when its units digit is0, which keeps state0, so those numberabs(K_(k-1)^(c)), and by the mass sectionabs(K_k^(c)) - abs(K_(k-1)^(c)) = fill^(k-1)(fill - 1) pi_catk >= 2, sincelambda_2^k = lambda_2^(k-1)whenlambda_2is0or1. 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 constantp/(p+1)of the half interval at a prime, up to at most1a block and(2 fill + 2) Lin all, far inside the error. - What the theorem reads off
K. The certificate below1/5ats = 0for region A and at every shift for the bottom factor of the hybrid bound,alpha_1 < 1/4for region B, the per-position bound with the pair for C1, and the countsabs(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 to10^7reads0.834,0.993and0.583atp = 101,1009and10007, andpsi_K/((p/(p+1)) A_K)reads1.0033,1.0024and0.9999, sanity prints that are evidence for nothing (verbmeter, 2 seconds). At the smallest primes, up to10^8,psi_K/((p/(p+1)) A_K)with prime powers reads1.0032,1.0041,1.0010and1.0051atp = 5,7,11and13,A_K(10^8)counted exactly through the blocks by state: the shapep/(p+1)holds far below the wall, a falsification line and no evidence for the theorem (verbsmall, 3 seconds).
Every pair (a, b)
- The theorem on a certificate. Proved. Let
a > b >= 1and letp >= 2a - 1be prime. IfK_(a,b)carries a matrix certificate below1/5, an invertiblePwithP e_0 = 1and a weightpsi, bounded and bounded away from0in every entry, withpsi >= abs(e_0^T P)entrywise andT psi <= lambda psifor the operator ofN = P^(-1) M Pon itsb(a - b)states andlambda/fill < p^(1/5), then the theorem above holds onK_(a,b)with the constantp/(p+1). The four bullets of the section above transfer: the blocks are indexed by the states, at mostb(a - b)(fill + 1)per scale; the max-row bound holds since every row sums tofilland every state keeps the pair{0, 1}into(0, 0); region C2 reads only the counts. For the main term, a units digit0sends every state to(0, 0), so the words ofK_k^(c)divisible bypnumberabs(K_(k-1)^(c)); on the states reachable from(0, 0)the count matrix is primitive, every state returning to(0, 0)on the digit0and(0, 0)keeping that loop, soabs(K_k^(c)) = fill^k pi_c + O(k^S abs(lambda_2)^k)withabs(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 offill^kat the scales the dissection keeps. - The row-0 constant is
3 - 4 gcd(a, b)/a. Proved. Row(0, 0)keeps thedwith{bd/p} + {(a-b)d/p} < 1, and aspgrows these fill, up toO(a)digits, the unionF*_(a,b)of the intervals where{b theta} + {(a-b) theta} < 1in[0, 1), of measure1/2. Its numerator at an integerz, the sum ofe(beta z) - e(alpha z)over its intervals[alpha, beta), is2 pi i ztimes the Fourier coefficient of the indicator, and the indicator is1 - {b theta} - {(a-b) theta} + {a theta}, whose term{c theta}contributes atz != 0only whencdividesz, with coefficient of modulusc/(2 pi abs(z)). So the numerator has modulusabs(V(z)),V(z) = b [b | z] + (a - b) [(a-b) | z] - a [a | z]. Whenadividesz,V(z) <= b + (a - b) - a = 0, soabs(V) = V - 2 V [a | z]; over a periodVaverages1 + 1 - 1 = 1andV [a | z]averagesb/lcm(a, b) + (a - b)/lcm(a, a - b) - 1 = 2g/a - 1withg = gcd(a, b) = gcd(a, a - b). So the row-0 numerator att = 0averagesnu_(a,b)(0) = 3 - 4g/a:1at(2, 1),5/3at(3, 1),2at(4, 1),11/5at every(5, b), rising to3. (Verified: the limit design and its average are recomputed from the breakpoints for everya <= 7,(2/pi) nu_(a,b)(0)reading0.636620,1.061033,1.273240,1.400563,1.485446,1.546077ata = 2..7withb = 1, and atp = 10007row(0, 0)misses the limit design, and every other row misses row(0, 0)with its moves, by at most2a - 4digits,10ata = 7; verbfamily.) - What stays open. Conjecture. For every
a > b >= 1the row-0 operator ofK_(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 below1/5and the Mobius bound and prime count from some primeP_0(a, b); the rate is read only at(3, 1), and ata <= 7only the limit constant and the row deviations atp = 10007are computed (verbsrateandfamily). The row-0 basis asks only that the rows differ inO(a)digits, which the bullet above reads atp = 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))Zand with a second block ofb(a - b) - 1rows. Unconditionally the theorem stands at(2, 1)from94939and at(3, 1)and(3, 2)from13567831. Atg > 1the constant drops:nu_(4,2)(0) = 1, the half interval's, andK_(4,2)is the set ofkwith2kin 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 operatorTon100cells with linear interpolation readslambda_T/fillat10.5899,10.7000,10.6220and10.7064at1009,1013,1039and1019, at13.0797,13.1686,13.0829and13.1654at10009,10037,10039and10007, and at15.5549at100003. Above(10/(3 pi)) log pthat is3.251and3.252atp = 1 mod 3against3.357atp = 2 mod 3near10^3, and3.306against3.392near10^4: the class mod3moves the offset by about0.09, throughD, and the class mod4by under0.001. In the class1 mod 3the offsets climb3.251,3.306,3.339at1009,10009,100003, about0.019per unit oflog p, as consistent with a leading coefficient near1.08as with10/(3 pi) = 1.0610, and the run at100003uses60cells and15iterations against100and25: the readings do not single out the constant. The leading term(10/(3 pi)) log p = (2/pi) nu(0) log pis the row-0 design's, the minimum ofnuatt = 0and not its maximum, as at the half interval. The certificate reads15.27at1009and18.05at10009,4.7and5.0aboveT: the one-step weight pays(2/pi)(nu^+ - 5/3) log p, and the drift and chord terms of the proof the rest (verbrate). - The rate of
Kitself. Verified, as readings. The exact unshifted sumsSigma_L(0), by FFT, giveSigma_L/Sigma_(L-1)/fillat6.2920,6.3321,6.3570and6.3957at101,103,107and109at level3, and at8.8244,8.8237,8.8301and8.8684at1009,1013,1019and1051at level2, from1.395to1.486above(10/(3 pi)) log p, while the row-0 designF*alone reads0.036to0.065lower at the same primes. So thel^1mass ofKis that ofF*up to a few hundredths, and the triangle inequality across the second row, whichTpays at every digit, costs about1.8againstfillatpnear10^3. Carried to the bar, the offset3.339ofTat100003meetsp^(1/5)near2.44 * 10^6and the offset1.486ofKnear1.15 * 10^6: the wall13567831is the certificate's and not the route's, and a certificate reading the two paths of the second row together, or the weight1 + beta abs(sin(pi t))of the half interval, moves it down; neither is written here (verbrate, 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, soM_K(x) = o(x)with no rate; sinceA_K(x)grows likex^(alpha_p)withalpha_p < 1, that bound is weaker than the trivialabs(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; onK, a set of density0, that density is0, and nothing is said at the scaleA_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, andKis 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 lengthnthat are not synchronizing atO(k^(n(1 - eta)))in basek.K's automaton completed with a refusing sink is synchronizing, the digitp - 1being refused in both states, andKlies 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 digit0, and the sink breaks strong connection. - What the certificate route adds. On the Kummer set
K = K_(3,1)at every primep >= 13567831: a Mobius bound against the set's own mass and a prime count with the constantp/(p+1), both with a saving of zero-free-region shape and constants computable fromp, and an explicit least prime; on everyK_(a,b), the exact count((p+1)/2)^L, the pair, the row-0 constant and the theorem wherever a matrix certificate below1/5exists.
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)^Lover the pairs(a, b), the row count, the pair, the product-set test belowp^3, the row-0 limit designs and their constant3 - 4 gcd(a, b)/a.wall: the constantsnu^+,H^+,nu_1^+,H_1^+, the closed form oflambdaat 120 bits, the walls at1/5and1/4with the tail, the spread by class and the band near the cut.check: the four sums against their bounds and closed forms at every prime13..401and six larger primes on201shifts, the transfer identity at level3, and the shifted grid sums againstlambda^i.rate: the readings of the last section.meterandsmall: the sanity meter and the prime count at the smallest primes. - The Kummer sets demo runs the automaton of every
K_(a,b)witha <= 9at every odd primep <= 101through the cratemrlyrs::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 belowp^Lagainst((p+1)/2)^Land where it fails atp <= a, the witnessu,v p,u + v p, and onekread column by column besidev_p(C(a k, b k))by Legendre's digit sums. - The falsification. Verified. At every prime
13..401and at1009,1013,10007,10009,100003and100019, on201shifts of[0, 1/2],G*stays under its pointwise bound, at most0.765814of it,G_01at most0.897928,CandDmeet their closed forms, andT psistays underlambda psi, at most0.775433and0.905536of it in the two entries; the product formula and the row-0 basis meet the direct transform at level3atp = 13and31to4.0 * 10^-10; and the shifted sumsSigma_i(s)at nine primes13..43, four shifts and every level withp^i <= 2 * 10^6stay underlambda^i, at most0.480589of it (verbcheck, 10 seconds).