Let (epsilon_n)_{n >= 0} be independent signs, each equal to +1 or -1 with probability 1/2. For 0 < lambda < 1 the series Y_lambda = sum_{n>=0} epsilon_n lambda^n converges absolutely, since |Y_lambda| <= 1/(1-lambda). The unbiased Bernoulli convolution nu_lambda is the law of Y_lambda. Equivalently, with (u_n) independent fair bits and X_lambda = sum_{n>=0} u_n lambda^n of law mu_lambda, the affine identity Y_lambda = 2 X_lambda - 1/(1-lambda) displays nu_lambda as the image of mu_lambda under x -> 2x - 1/(1-lambda). Singularity and absolute continuity are affine invariants, so nu_lambda and mu_lambda always share their measure type. A Borel probability measure is singular if it assigns full mass to a Borel set of Lebesgue measure zero, and absolutely continuous if it has a density. For every lambda in (0,1) the measure nu_lambda is pure: it is either singular or absolutely continuous, never a proper mixture.
The three regimes are qualitatively different. For lambda < 1/2 the support is covered, for every n, by 2^n intervals of length (1-lambda)^{-1} lambda^n; their total length is (2lambda)^n (1-lambda)^{-1}, which tends to zero, so nu_lambda is singular. At lambda = 1/2 the classic fair binary expansion identifies nu_lambda with the uniform law on [-2,2]. The interval (1/2,1) carries the arithmetic difficulty. Bernoulli convolutions are a special case of Kahane's random series with independent coefficients (Kahane 1971):
https://doi.org/10.24033/msmf.42
The three density classes that have been settled are the following. If lambda^{-1} is a Pisot number -- a real algebraic integer beta > 1 whose remaining conjugates all have modulus less than one -- then nu_lambda is singular, because the Fourier transform nu_lambda_hat(xi) does not tend to zero as |xi| -> infty (Erdos 1939):
./erdos-1939.pdf
If lambda^{-1} is an algebraic integer of absolute norm two whose conjugates all have modulus greater than one, then nu_lambda is absolutely continuous (Garsia 1962):
https://doi.org/10.1090/S0002-9947-1962-0137961-5
Garsia also identified the entropy of finite sums as a diagnostic of singularity (Garsia 1963):
./garsia-1963.pdf
Almost every lambda in (1/2,1) yields an L^2 density (Solomyak 1995):
https://doi.org/10.2307/2118556
The three main theorems settle the measure type at two further arithmetic families and give an exact arithmetic criterion in the remaining case.
The almost-everywhere theory only fixes the Lebesgue-typical behaviour. Combining entropy and inverse theorems for self-similar sets, the set of lambda in (1/2,1) where nu_lambda can be singular has Hausdorff dimension zero (Hochman 2014, Shmerkin 2014):
./hochman-2014.pdf
./shmerkin-2014.pdf
Shmerkin states:
"We prove that the set of exceptional lambda in (1/2, 1) such that the associated Bernoulli convolution is singular has zero Hausdorff dimension, and likewise for biased Bernoulli convolutions, with the exceptional set independent of the bias." - Shmerkin 2014
Transcendental parameters give dimension one and their nu_lambda is absolutely continuous (Varju 2019, transcendental):
./varju-2019-transcendental.pdf
Varju states:
"The Bernoulli convolution nu_lambda with parameter lambda in (0, 1) is the probability measure supported on R that is the law of the random variable sum of +/- lambda^n, where the +/- are independent fair coin-tosses. We prove that dim nu_lambda = 1 for all transcendental lambda in (1/2, 1)." - Varju 2019
The Diophantine obstruction to badly distributed powers of a transcendental appears in Boyd's early study (Boyd 1969):
https://doi.org/10.1090/S0002-9939-1969-0248094-3
Algebraic parameters satisfying a Diophantine condition against the parameter are absolutely continuous (Varju 2019, algebraic):
./varju-2019-abs-continuity.pdf
Breuillard and Varju show that any dimension-deficient parameter sits exponentially close to an algebraic parameter whose convolution is also dimension-deficient (Breuillard-Varju 2019):
./breuillard-varju-2019.pdf
These results do not resolve the measure type at exceptional parameters: full dimension does not imply absolute continuity. The survey of Peres, Schlag, and Solomyak records the historical development and the central role of arithmetic, overlap, and Fourier decay (Peres-Schlag-Solomyak 2000):
https://doi.org/10.1007/978-3-0348-8380-1_2
Fourier nondecay is not necessary for singularity (Salem 1943):
https://doi.org/10.1090/S0002-9947-1943-0008428-8
Salem numbers -- algebraic integers beta > 1 whose remaining conjugates are beta^{-1} together with conjugate pairs on the unit circle -- therefore demand a method that does not rest on Fourier nondecay. Feng and Wang built non-Pisot singular examples by controlling algebraic transversality directly (Feng-Wang 2004):
https://doi.org/10.1016/j.aim.2003.05.002
Spectral measures of substitution systems already show that self-similarity alone can force Fourier decay (Bufetov-Solomyak 2014):
./bufetov-solomyak-2014.pdf
Riesz-product estimates, the model for the multiphase Fourier comparison used in the Salem argument, are developed by Peyriere (Peyriere 1975):
./peyriere-1975.pdf
Recent quantitative decay estimates for substitution-suspension flows apply (Marshall-Maldonado-Solomyak 2026):
./mms-2026.pdf
The existence of singular examples with non-Pisot reciprocal is recorded as open (Baker-Koivusalo-Troscheit-Zhang 2026, Kern-Sterk 2026):
./baker-2026.pdf
./kern-sterk-2026.pdf
The three main theorems close this gap in two ways.
Theorem A (arithmetic criterion). For integers n >= 1 and d >= 2, let R(n,d) be the set of real algebraic units r in (1/2,1) of degree dn whose minimal polynomial has all coefficients in {-1,0,1} and reduces irreducibly modulo 2. Write p_r for the minimal polynomial of such an r, signed so that its constant coefficient is -1, and let pi_n(p_r) = ([t^0] p_r,...,[t^{n-1}] p_r) in {-1,0,1}^n. For r in R(n,d), define W_n(r;d) as the set of vectors pi_n(p_q) with q in R(n,d) and |q - r| <= 4^{-n}, counted without multiplicity. For a bit word u in {0,1}^n let O_u = { w in R^n : (2u_i - 1) w_i >= 0 for all i < n } be the closed orthant with these signs (coordinates equal to zero belong to both sign choices). For integers j >= 1, set R_*(n,d,j) to be the set of r in R(n,d) for which at least 2^n / d bit words u satisfy #(W_n(r;d) cap O_u) >= j (2r)^n. With the parameter set
C = (0,1/2) cup [ (1/2,1) cap union_{d>=2} intersection_{j>=1} limsup_{n->infty} union_{r in R_*(n,d,j)} [r - 4^{-n}, r) ],
the measure nu_lambda is singular for lambda in C and absolutely continuous for lambda in (0,1) \ C. Replacing limsup by liminf in the definition of C leaves it unchanged.
Every set entering C is defined by finite polynomial algebra and finite counting of coefficient vectors, and the construction uses no information about any nu_lambda. Membership in C is an infinite approximation property, not a finite decision procedure; determining membership at a particular real parameter can be difficult even when the arithmetic criterion applies in principle.
Theorem B (quartic Salem numbers). Let beta in (1,2) be a Salem number of degree four. Then nu_{1/beta} is singular with respect to Lebesgue measure. In particular both quartic polynomials P_1(x) = x^4 - x^3 - x^2 - x + 1 and P_2(x) = x^4 - 2x^3 + x^2 - 2x + 1 have a real root beta in (1,2), and nu_{1/beta} is singular at both roots.
Theorem C (a non-Pisot polynomial). Let p(t) = t^{31} - 2t^{30} + sum_{j=0}^{9} (t^{3j+1} - t^{3j}). This polynomial has a unique real root beta in (1.8392,1.8393); beta is not a Pisot number; and nu_{1/beta} is singular. The proof of singularity rests on a rational certificate verified with exact arithmetic.
The proofs of Theorems A, B, C are distinct but share the same reduction of concentration to a packing bound on finitely many cylinder locations. Theorem A converts an arithmetic cluster into a packing bound and back; Theorem B converts an algebraic multiplier into a concentration of Fourier phases; Theorem C converts a trigonometric product into a packing bound. Each proof is independent of the others.
Two facts about nu_lambda are used repeatedly. First, uniqueness of the invariant measure under the iterated-function system x -> i + lambda x (i = 0,1) forces purity. Second, singularity is equivalent to the existence, for every epsilon > 0, of a compact set K with Lebesgue measure below epsilon and mu_lambda-mass above 1 - epsilon. Both are elementary consequences of inner regularity.
Lemma 1 (pure type and baseline). For 0 < lambda < 1, the measure mu_lambda is either singular or absolutely continuous. For lambda < 1/2 it is singular; for lambda = 1/2 it is uniform on [0,2] and nu_{1/2} is uniform on [-2,2] (Jessen-Wintner 1935).
https://doi.org/10.1090/S0002-9947-1935-1501802-5
Proof. Let T_i(x) = i + lambda x for i = 0,1, and let T rho = (1/2)(T_0)_* rho + (1/2)(T_1)_* rho. Iterating from any probability measure rho yields the law of sum_{i<n} u_i lambda^i + lambda^n Z, where Z has law rho and is independent of the bits. Since lambda^n Z -> 0 in probability, these laws converge weakly to mu_lambda, which is therefore the unique invariant probability of T.
The operator T preserves absolute continuity and singularity. By uniqueness of the Lebesgue decomposition, the absolutely continuous and singular parts of any invariant probability are separately invariant. If both were nonzero, normalising them would produce two distinct invariant probabilities, contradicting uniqueness.
For lambda < 1/2, cover the support at level n by 2^n intervals of length (1-lambda)^{-1} lambda^n; the sum of lengths is (2lambda)^n (1-lambda)^{-1} -> 0, so mu_lambda is singular. At lambda = 1/2 the binary expansion sum u_i 2^{-i} = X_{1/2} with independent fair bits gives X_{1/2} uniform on [0,2]; the affine identity displays nu_{1/2} as uniform on [-2,2].
Lemma 2 (compact concentration). A Borel probability measure rho on R is singular if and only if, for every epsilon > 0, some compact set K has Lebesgue measure below epsilon and rho-mass above 1 - epsilon.
Proof. If rho is singular, inner regularity applied to a Borel null set of full rho-mass produces such compact sets. Conversely, take such K_m with epsilon = 2^{-m}. The set limsup_m K_m is Borel, is null because sum_m |K_m| < infty, and has full rho-mass because every union_{m>=M} K_m has rho-mass one. Hence rho assigns full mass to a null set.
Forward direction of Theorem A. Fix lambda in (1/2,1) with lambda in C, and let d witness the defining condition. For each j there are arbitrarily large n and r in R_*(n,d,j) with r - 4^{-n} <= lambda < r. Choose w in W_n(r;d) and a unit q in R(n,d) with pi_n(p_q) = w and |q - r| <= 4^{-n}. Then |q - lambda| <= 2*4^{-n}. The logarithmic derivative of p_q on any compact subinterval of (0,1) containing lambda in its interior satisfies |p_q'(t)| <= sum_{k>=1} k t^{k-1} = (1-t)^{-2}. On the other hand the coefficients of p_q with index at least n contribute at most (1-lambda)^{-1} lambda^n to p_q(lambda) (after dividing by the leading coefficient, which has modulus one). Because 4^{-n} = o(lambda^n), there is B = B(lambda) with, for all sufficiently large n, uniform over d, j, w:
|sum_{i<n} w_i lambda^i| <= B lambda^n. (1)
If w lies in the closed orthant O_u, then v = u - w belongs to {0,1}^n; different w give different v, and sum_i w_i lambda^i = s_u(lambda) - s_v(lambda), where s_t(lambda) = sum_{i<n} t_i lambda^i. Hence at least 2^n / d bit words u have at least j (2r)^n >= j (2 lambda)^n neighbours v satisfying |s_u(lambda) - s_v(lambda)| <= B lambda^n.
Split the line into half-open bins of length lambda^n, assign each word u to the bin containing s_u(lambda), and let I be the set of bins that contain at least one such u. For each I in cal-I choose one such u. Its neighbours lie in the B lambda^n enlargement of I, and each prefix sum s_t(lambda) lies in the enlargement of at most N_B = 2 * ceil(B) + 3 bins. Counting word-bin incidences gives #I * j (2 lambda)^n <= N_B 2^n, hence #I <= N_B lambda^{-n} / j. Enlarge each bin I = [a, a + lambda^n) to [a, a + (1+ (1-lambda)^{-1}) lambda^n], and let E_j be their union. Then
|E_j| <= (1 + (1-lambda)^{-1}) N_B / j, mu_lambda(E_j) >= 1/d. (2)
As j -> infty, (2) says mu_lambda puts mass >= 1/d on sets of arbitrarily small Lebesgue measure, which contradicts absolute continuity of the finite measure mu_lambda. Lemma 1 then gives singularity.
This proves the forward direction of Theorem A in the form that membership in C implies singularity. The uniform-in-d structure of the criterion is not used in this direction: a single witness d suffices. The converse is where the uniformity of the liminf over j and the existence of one d for every j both enter.
Converse direction of Theorem A. Assume nu_lambda singular for a fixed lambda in (1/2,1), and let mu = mu_lambda, X = X_lambda, L = (1-lambda)^{-1}. The converse turns concentration of mu into many close prefix sums with opposite first bits; opposite first-bit vectors give a difference polynomial with constant coefficient -1, which is exactly the coefficient vector the criterion W_n(r;d) registers. Uniform finite-order nonvanishing preserves a sign change across a very short interval; prime polynomials in arithmetic progressions over F_2[t] then supply irreducibility without disturbing the first n coefficients. The result is quantified uniformly in the bit vectors, the crowding parameter, and the degree multiplier.
Define mu_i(A) = P(X in A, u_0 = i) for i = 0,1, subprobability measures whose sum is mu.
Lemma 3 (first-bit overlap). For lambda in (1/2,1) some finite nonzero measure xi satisfies xi <= mu_0 and xi <= mu_1.
Proof. Suppose no such xi exists. Then mu_0 and mu_1 are mutually singular, because otherwise the Lebesgue decomposition would supply a nonzero component of mu_0 absolutely continuous with respect to mu and to mu_1 simultaneously. Mutual singularity makes the conditional entropy of the first n bits, given a lambda^n-quantisation of X, arbitrarily small compared to n, while the quantisation carries only O(lambda^{-n}) cells and therefore cannot hold the full entropy n log 2 of the n bits. Contradiction.
In detail: fix eta in (0,1/2). Inner regularity applied to the mutual singularity of mu_0 and mu_1 supplies disjoint compact sets K_0, K_1 with mu_i(K_i) > 1 - eta for i = 0,1. Let delta = dist(K_0,K_1) > 0 and choose h >= 1 with lambda^h < delta/3. Write Q_n = floor(X / lambda^n). Given Q_n and the first i bits u_0,...,u_{i-1}, the quantity X^{(i)} = (X - sum_{k<i} u_k lambda^k) / lambda^i is approximated to within lambda^{n-i}. The pair (X^{(i)},u_i) has the law of (X,u_0). For n - i >= h the approximation determines an estimator of u_i with error probability at most eta, via nearest compact set. Writing H for Shannon entropy with natural logarithms and h_2(eta) = -eta log eta - (1-eta) log(1-eta), the error-indicator argument gives H(u_i | Q_n, u_0,...,u_{i-1}) <= h_2(eta) for i <= n - h, and the remaining at most h bits contribute at most h log 2. Because X in [0,L], there are at most L lambda^{-n} + 2 values of Q_n. The chain rule yields
n log 2 <= H(Q_n) + H(u_0,...,u_{n-1} | Q_n) <= n log(1/lambda) + n h_2(eta) + O_{lambda,eta}(1).
Choosing eta > 0 with h_2(eta) < log(2 lambda) and letting n -> infty is a contradiction.
Proposition 4 (many close prefixes with opposite first bits). If mu_lambda is singular, there are constants a in (0,L/2) and c > 0, depending only on lambda, such that for every Q > 1 and all sufficiently large n at least c 2^n words u in {0,1}^n with u_0 = 0 each have at least Q (2 lambda)^n distinct neighbours v in {0,1}^n with v_0 = 1 and
|s_u(lambda) - s_v(lambda)| <= (L - a) lambda^n. (3)
Proof. Fix xi as in Lemma 3 and write b = xi(R) > 0. The endpoints 0 and L have mu-mass zero because each forces all the bits to take one prescribed value. Choose a in (0,L/2) so that mu([a, L-a]) > 1 - b/8.
For each n, put X^{(n)} = sum_{k>=0} u_{n+k} lambda^k and restrict the first-bit measures:
mu'_{i,n}(A) = P(X in A, u_0 = i, X^{(n)} in [a, L-a]).
The total mass discarded from mu_0 + mu_1 is less than b/8, since X^{(n)} has law mu.
Fix Q > 1. Compact concentration (Lemma 2) gives a compact K with |K| < epsilon and mu(K) > 1 - epsilon, where epsilon = min(b/8, ab/(8Q)). Then xi(K) > 7b/8. Partition the line into half-open bins of length a lambda^n and let cal-J_n consist of those bins meeting K. Compactness of K gives, for all sufficiently large n,
#cal-J_n <= 2 epsilon / (a lambda^n),
because the union of the bins in cal-J_n is contained in the closed a lambda^n-neighbourhood of K whose Lebesgue measure tends to |K|. Moreover
sum_{J in cal-J_n} min_{i=0,1} mu'_{i,n}(J) >= 3b/4. (4)
Indeed, the same sum with mu_i in place of mu'_{i,n} is at least xi(K), and restricting the two measures discards less than b/8 in total.
For i = 0,1 let U_i(J) be the set of words u of length n with u_0 = i for which the interval s_u(lambda) + lambda^n [a, L-a] meets J. Each word has mass 2^{-n}, so mu'_{i,n}(J) <= 2^{-n} #U_i(J). Discard the bins J for which #U_1(J) < Q (2 lambda)^n. Their total contribution to (4) is at most (2 epsilon / (a lambda^n)) 2^{-n} Q (2 lambda)^n = 2 epsilon Q / a < b/4 by the choice of epsilon. The minima over the retained bins therefore sum to at least b/2.
A fixed interval s_u(lambda) + lambda^n [a, L-a] meets at most C_a = ceil((L - 2a)/a) + 2 of the bins. If cal-U denotes the union of U_0(J) over retained bins, then
b/2 <= 2^{-n} sum_{J retained} #U_0(J) <= 2^{-n} C_a #cal-U,
so #cal-U >= b / (2 C_a). Take c = b/(2 C_a). For each u in cal-U choose one retained bin J with u in U_0(J). All v in U_1(J) satisfy (3): two points in J differ by less than a lambda^n, and two tails in lambda^n [a, L-a] differ by at most (L - 2a) lambda^n, so the total difference is at most (L - a) lambda^n. There are at least Q (2 lambda)^n such v.
Lemma 5 (uniform finite-order nonvanishing). Fix lambda in (0,1). There are an integer M >= 1 and constants c_0, x_0 > 0 such that every real polynomial p(t) = -1 + sum_{k>=1} a_k t^k with |a_k| <= 1 for all k satisfies
sup_{t in [lambda, lambda + x]} |p(t)| >= c_0 x^M (5)
for every 0 < x < x_0.
Proof. There exist M >= 1 and delta > 0 such that for every such polynomial, max_{0 <= k <= M} |p^{(k)}(lambda)/k!| >= delta. Otherwise, for each m one could pick a polynomial whose Taylor coefficients through order m at lambda are less than 1/m. Extend each coefficient sequence by zeros and pass to a coefficientwise convergent subsequence using compactness of [-1,1]^N. The resulting series and its derivatives converge uniformly on compact subsets of the unit disk. The limit is analytic on the disk, vanishes with all derivatives at lambda, and has p(0) = -1, contradicting the identity theorem.
For fixed M, equivalence of norms on polynomials of degree at most M gives kappa_M > 0 with sup_{0 <= t <= 1} |sum_{k=0}^M b_k t^k| >= kappa_M max_{k <= M} |b_k|. Apply this to the Taylor polynomial of p(lambda + xt) at x = 1. For 0 < x <= 1 the maximum Taylor coefficient is at least delta, so the supremum over t in [0,1] of the degree-M truncation is at least kappa_M delta. For 0 < x < x_0 small this contributes at least (kappa_M delta / 2) x^M after rescaling t -> xt, and the remainder of the Taylor series is O_lambda(x^{M+1}), which is negligible compared to x^M for small x_0. Setting c_0 = kappa_M delta / 2 proves (5).
Lemma 6 (irreducibles with prescribed initial coefficients). Fix D >= 2 and d > 2D. For all sufficiently large n, every F in F_2[t] with deg F < Dn and F(0) = 1 admits a monic irreducible completion P in F_2[t] satisfying
deg P = dn, P = F + t^{Dn} mod t^{Dn+1}.
(Gorodetsky-Kovaleva 2024)
./gorodetsky-kovaleva-2024.pdf
Proof. For a monic polynomial f put Lambda(f) = deg P if f = P^k for a monic irreducible P (k >= 1), and Lambda(f) = 0 otherwise. Let chi be a nonprincipal Dirichlet character modulo t^ell, extended by zero to nonunits. The associated L-function is a polynomial of degree at most ell - 1 with inverse roots alpha_j of modulus at most sqrt 2 (this bound includes the trivial factor at 0), so taking the logarithmic derivative of the Euler product gives
|sum_{f monic, deg f = s} Lambda(f) chi(f)| = |sum_j alpha_j^s| <= ell 2^{s/2}.
For the principal character the same sum is 2^s - 1, from the zeta function of F_2[t] after removing the single prime t. Character orthogonality gives, in every invertible residue class A mod t^ell,
sum_{f monic, deg f = s, f = A mod t^ell} Lambda(f) >= (2^s - 1)/2^{ell - 1} - ell 2^{s/2}. (6)
The contribution of the proper prime powers, without even imposing the congruence, is at most sum_{k | s, k >= 2} 2^{s/k} <= s 2^{s/2}. Take ell = Dn + 1, s = dn, and A = F + t^{Dn}. This is invertible because F(0) = 1. The main term in (6) is of order 2^{(d - D)n}; the character error and the proper-power contribution are O(n 2^{dn/2}). Since d > 2D the main term dominates, and at least one irreducible polynomial remains for all sufficiently large n. The choice of ell depends only on n and D, so the estimate is uniform in F.
Proposition 7 (realization of a polynomial prefix). Fix lambda in (1/2,1) and a in (0,L). There is an integer d_0 such that for every integer d >= d_0 and all sufficiently large n the following assertion holds uniformly over all w in {-1,0,1}^n. If
w_0 = -1, |sum_{i<n} w_i lambda^i| <= (L - a) lambda^n, (7)
then some r in R(n,d) satisfies lambda < r <= lambda + 4^{-n}/2 and pi_n(p_r) = w.
Proof. Let M, c_0, x_0 come from Lemma 5. Choose D >= 2 with lambda^D < 4^{-M} and take d_0 = 2D + 1.
Start from the polynomial defined by the given w (of degree < n and with constant coefficient -1) and append coefficients with indices n <= k <= Dn - 1. If the coefficient at index k is next, let e be the negative of the current value at lambda divided by lambda^k. Appending a digit e_0 in {-1,0,1} at that position changes this residual to (e - e_0)/lambda. Choose e_0 as the nearest digit. Once |e| <= 1, the next residual has absolute value at most 1/(2 lambda) < 1, so the bound |e| <= 1 persists. Before that time the residual keeps its sign and |e| -> (|e| - 1)/lambda = L + (|e| - L)/lambda. Because the initial bound is |e| <= L - a, the interval |e| <= 1 is reached within a number of steps depending only on lambda and a. After Dn - n additional steps at worst, so the constructed polynomial p_0 of degree at most Dn - 1 satisfies, for all sufficiently large n,
|p_0(lambda)| <= lambda^{Dn}/(2 lambda). (8)
Put x_n = 4^{-n}/2. Lemma 5 gives a t_n in [lambda, lambda + x_n] with |p_0(t_n)| >= c_0 x_n^M. Every possible appendage with coefficients in {-1,0,1} starting from index Dn and extending to any length has modulus at most (lambda + x_n)^{Dn}/(1 - lambda - x_n) on this interval, which is o(x_n^M) because lambda^D < 4^{-M} and Dn x_n -> 0.
Fix d >= d_0. Apply Lemma 6 to the reduction of p_0 mod 2, which has degree < Dn and constant coefficient 1 (because p_0 has constant coefficient -1). The result is a monic irreducible P in F_2[t] with deg P = dn and P = p_0 + t^{Dn} mod t^{Dn+1}. Represent the coefficients of P at indices Dn <= k <= dn by integers b_k in {0,1}, set T(t) = sum_{Dn <= k <= dn} b_k t^k, and p_pm(t) = p_0(t) +- T(t). The endpoint coefficients b_{Dn} = b_{dn} = 1, so T(lambda) >= lambda^{Dn}. Estimate (8) therefore gives p_-(lambda) < 0 < p_+(lambda). At t_n the negligible appendage gives p_pm(t_n) the same nonzero sign as p_0(t_n). One of the two polynomials therefore vanishes at some r in (lambda, t_n] subset (lambda, lambda + x_n].
Both p_+ and p_- reduce to P mod 2, so both are irreducible over Q. Both have degree dn, leading coefficient +-1, constant coefficient -1, and coefficients in {-1,0,1}. Their roots are therefore algebraic units. For sufficiently large n the root r in (lambda, lambda + x_n] lies in (1/2,1), belongs to R(n,d), and has signed minimal polynomial p_pm whose first n coefficients are the given w. This realizes the prefix.
Assembly of the converse. Suppose mu_lambda is singular. Proposition 4 gives constants a and c. Choose one integer d large enough for Proposition 7 and also satisfying 1/d < c; the choice depends only on lambda. Fix any integer j >= 1 and take Q > 2j. For all sufficiently large n, at least c 2^n words u with u_0 = 0 have at least Q (2 lambda)^n neighbours v supplied by Proposition 4. For each difference w = u - v, Proposition 7 supplies a root r_w in R(n,d) whose signed minimal polynomial projects to w, with lambda < r_w <= lambda + 4^{-n}/2. Let r be any one of these roots. All of them lie within 4^{-n} of r, so their projections belong to W_n(r;d). For fixed u the neighbours v give distinct vectors u - v, each in the orthant O_u. Different neighbours have different differences (v -> u - v is a bijection on {0,1}^n), so the count of distinct vectors in O_u coinciding with W_n(r;d) is at least Q (2 lambda)^n. Because Q > 2j and 1 <= (r/lambda)^n <= (1 + 4^{-n}/(2 lambda))^n -> 1 uniformly in the choice of center r, for all sufficiently large n each of these c 2^n orthants carries at least j (2 r)^n distinct vectors of W_n(r;d). Since c > 1/d, r is in R_*(n,d,j) and lambda is in [r - 4^{-n}, r). Therefore lambda lies in the expression defining C with liminf in place of limsup. Membership with liminf implies membership with limsup, so lambda is in C, completing the proof of Theorem A.
Recovery of the Garsia and Pisot classes. The two classical classes sit inside the criterion exactly as their independent proofs require. The Garsia class lies in the complement of C; the Pisot class lies in C. Neither recovers the criterion, but their union identifies the two cleanest examples.
Proposition 8 (Garsia parameters). Let beta in (1,2) be an algebraic integer of absolute norm 2 whose non-self conjugates all have modulus greater than one. Then 1/beta lies outside C and nu_{1/beta} is absolutely continuous.
Proof. Put lambda = 1/beta. Two distinct vectors w, w' in {-1,0,1}^n lying in the same closed orthant differ in every coordinate sign; set P(t) = sum_{i<n} (w_i - w'_i) t^{n-1-i}, which has coefficients in {-1,0,1} and does not vanish identically. The polynomial P cannot vanish at beta: a nonzero P in this coefficient class vanishing at beta would, after dividing by the largest power of t, have constant coefficient +-1, and this constant would have to be divisible by the norm 2 of beta, which is impossible.
For every conjugate gamma of beta other than beta itself, |P(gamma)| <= |gamma|^n / (|gamma| - 1). The algebraic integer P(beta) is nonzero, so the product of |P(gamma)| over all n+1 conjugates of beta is at least one. Since the product of all conjugate moduli is 2, some constant c_beta > 0 gives
|sum_{i<n} (w_i - w'_i) lambda^i| = beta^{-(n-1)} |P(beta)| >= c_beta 2^{-n}.
For any potential hit of the criterion at sufficiently large n, all projected vectors satisfy the slab bound (1), and within one orthant the spacing between distinct vectors is at least c_beta 2^{-n}. The number of vectors within any interval of length 2 B lambda^n inside one orthant is therefore at most 1 + 2 B lambda^n / (c_beta 2^{-n}) <= C_beta (2 lambda)^n. Take an integer j > C_beta. Since a hit forces r > lambda, no orthant can meet the threshold j (2 r)^n >= j (2 lambda)^n. This excludes all sufficiently large n, so lambda is not in C. Theorem A then gives absolute continuity.
Proposition 9 (reciprocal Pisot parameters). Let beta in (1,2) be a Pisot number. Then 1/beta is in C and nu_{1/beta} is singular.
Proof. Put lambda = 1/beta. Because beta has nonzero integer norm of absolute value below beta < 2, it is a unit: beta^k is an algebraic integer for every integer k. In particular beta^k can never coincide with a half-integer of odd numerator, so all factors cos(pi beta^k) are nonzero. For negative k the quantity beta^k tends to zero exponentially. For positive k its distance to an integer tends to zero exponentially: the trace of beta^k is an integer, and the contributions of the other conjugates of beta (each of modulus below one) decay exponentially. The quadratic behaviour of -log |cos(pi t)| near the integers therefore gives
sum_{k in Z} -log |cos(pi beta^k)| < infty.
Fourier transforms of Y_lambda = sum epsilon_n lambda^n. Independence of the signs yields
E exp(i pi beta^n Y_lambda) = prod_{k <= n} cos(pi beta^k),
whose absolute value is at least prod_{k in Z} |cos(pi beta^k)| > 0 for all n. The Riemann-Lebesgue lemma rules out absolute continuity of nu_lambda, hence by Lemma 1 nu_lambda is singular, and Theorem A gives lambda in C.
Quartic Salem numbers. Theorem B is proved in two stages. The first constructs algebraic multipliers A_m for which the conjugates on the unit circle are tiny compared to the real conjugate beta^m; the trace identity then converts the arithmetic of A_m into a set of nearly independent Fourier phases. The second assembles these phases into a family of sets of full nu_{1/beta}-mass and vanishing Lebesgue measure. Throughout, beta in (1,2) is a degree-four Salem number with conjugates beta^{-1}, z, zbar = z^{-1}, where z = e^{i theta}; theta/pi is irrational because a rational theta/pi would make z a root of unity and hence beta itself a root of unity, impossible for a real number strictly between one and two.
Multipliers with small unit-circle conjugates. For positive integers k_1, k_2, ... to be chosen, set
A_m = prod_{h=1}^m (beta^{k_h} - beta^{-k_h}), b_m = sum_{h=1}^m k_h,
c_m = prod_{h=1}^m (z^{k_h} - z^{-k_h}), delta_m = |c_m|, L_m = log(1/delta_m).
Then 0 < A_m <= beta^{b_m}. For j in Z put u_{m,j} = A_m beta^j. Because beta is a unit, u_{m,j} is an algebraic integer. Its field trace is the integer
T_{m,j} = u_{m,j} + (-1)^m u_{m,-j} + 2 Re(c_m z^j). (9)
The integer-trace approximation is the arithmetic mechanism used in Salem's small-conjugate construction for Pisot and Salem classes (Salem 1963):
Salem, Algebraic Numbers and Fourier Analysis, Heath, 1963, Chapter III, Section 3
The embedding that sends beta to beta^{-1} sends A_m to (-1)^m A_m, giving the first two terms; the conjugate pair z, zbar contributes the remaining real number. The key observation is that u_{m,j} is never a half-integer of odd numerator, because a rational algebraic integer is an integer. Hence every cosine factor below is nonzero, and in particular delta_m > 0 and L_m = log(1/delta_m) is finite.
Lemma 10 (good multipliers). There are positive integers k_m and a constant gamma > 0 such that L_m > 0 and, with
D = 10/log(beta), K_m = ceil(2 b_m + D L_m) (m >= 2),
the sequence satisfies A_m >= 1 for every m and, for all sufficiently large m,
K_m <= k_{m+1} <= exp(1.9 L_m), L_{m+1} >= 1.75 L_m (m >= 2),
log K_m <= 0.75 L_m, L_{m+1} >= 2.1 L_m (m >= 3). (10)
Moreover
|cos(pi u_{m,j})| >= gamma for all m >= 1, j in Z, (11)
and, for m >= 2,
2 delta_m <= gamma/(2 pi), beta^{b_m - k_{m+1}} <= exp(-10 L_m) <= gamma/(2 pi). (12)
Proof. Write ||x||_{R/Z} for the distance to the nearest integer. The pigeonhole principle gives, for every N >= 1, some integer q in [1,N] with ||q theta/pi||_{R/Z} <= 1/N: place the N+1 fractional parts of 0, theta/pi, ..., N theta/pi in N intervals of length 1/N. Since theta/pi is irrational, the integers q achieving ||q theta/pi||_{R/Z} <= 1/q are unbounded as q -> infty.
Choose k_1 with A_1 > 1 and delta_1 < 1/16, and write gamma_m = inf_j |cos(pi u_{m,j})|. At m = 1, gamma_1 > 0: as j -> -infty the quantity u_{1,j} tends to zero; as j -> +infty the trace identity (9) shows that the absolute cosine differs from |cos(pi u_{1,-j})| by at most 2 pi delta_1 < pi/8; the remaining finite set of j has no vanishing cosine because 1/2 is not representable as an algebraic integer of the required form.
Choose k_2 > k_1 from the constructed unbounded sequence, imposing further lower thresholds. Since delta_2 <= 2 pi delta_1 / k_2 and L_2 >= log k_2 - log(2 pi delta_1), both k_2 and L_2 can be made arbitrarily large. In particular log K_2 <= 1.1 L_2 for sufficiently large such k_2, since the inequality bounds k_2 by a fixed multiple of exp(L_2) whereas the contribution D L_2 to K_2 is only linear.
For m >= 2, suppose L_m = L is large and log K_m <= 1.1 L. Take N = floor(exp(1.9 L)) and let q be the pigeonhole integer just obtained. Set
k_{m+1} = q if q >= K_m; k_{m+1} = ceil(K_m / q) q if q < K_m. (13)
Let L' = L_{m+1}. In the first case, delta_{m+1} <= 2 pi delta_m / N so L' >= 2.9 L - O(1) >= 2.8 L, and b_{m+1} <= 2 exp(1.9 L). In the second case, since ceil(K_m/q) <= 2 K_m and K_m <= k_{m+1} < 2 K_m, and using |sin(pi x)| <= pi ||x||_{R/Z}, the estimate delta_{m+1} <= 4 pi delta_m K_m / N follows so L' >= 2.9 L - log K_m - O(1) >= 1.75 L, and b_{m+1} <= 3 exp(1.1 L). In both cases K_m <= k_{m+1} <= exp(1.9 L) for large enough L.
These estimates also give log K_{m+1} <= 0.75 L'. Writing K_{m+1} <= 2 b_{m+1} + D L' + 1, the bound on b_{m+1} makes the first term at most (1/2) exp(0.75 L') for large L when the two cases are checked: 1.9 < 0.75 * 2.8 in the first case, 1.1 < 0.75 * 1.75 in the second. The remaining term satisfies the same bound for large L'. The construction iterates. From m >= 3, the improved log K_m <= 0.75 L_m gives L_{m+1} >= (2.9 - 0.75) L_m - O(1) >= 2.1 L_m in the second case; the first case gives more. This proves (10) after a lower threshold on L_2 depending only on beta.
To build the cosine floor, apply the exact identity
u_{m+1,j} = u_{m,j+k} - u_{m,j-k}, |u_{m,j-k}| <= beta^{b_m - k} beta^j
for j <= 0 and k = k_{m+1}, together with the Lipschitz bound for the cosine: gamma_{m+1} >= gamma_m - pi beta^{b_m - k_{m+1}}. For positive j, reflect to -j using (9) at level m+1. Consequently
gamma_{m+1} >= gamma_m - pi beta^{b_m - k_{m+1}} - 2 pi delta_{m+1}. (14)
For m >= 2, k_{m+1} >= 2 b_m + D L_m gives beta^{b_m - k_{m+1}} <= exp(-10 L_m). Also L_m >= 1.75^{m-2} L_2. The sum of the decrements in (14) is at most
pi beta^{k_1 - k_2} + 2 pi exp(-L_2) + sum_{r>=0} [ pi exp(-10 * 1.75^r L_2) + 2 pi exp(-1.75^{r+1} L_2) ],
which tends to zero as k_2 -> infty along the chosen sequence. Choose k_2 making this sum less than gamma_1 / 10 and also ensuring 2 exp(-L_2) and exp(-10 L_2) are at most gamma_1 / (4 pi). The earlier lower thresholds are compatible. Set gamma = gamma_1 / 2. Equations (11) and (12) follow.
Finally, k_m is increasing and every factor beta^{k_m} - beta^{-k_m} is at least A_1 > 1, so A_m >= 1 for every m.
The loss in the cosine products. Constants C > 0 in this and any later lemma may change from line to line but do not depend on m or on the phase index. Define f(u) = -log|cos(pi u)| for u not a half-integer, and S_m = sum_{j<=0} f(u_{m,j}). Each S_m is finite because u_{m,j} -> 0 as j -> -infty and f(u) = O(u^2) near zero.
Lemma 11 (cosine loss). With the multipliers of Lemma 10, S_m = o(L_m). Furthermore, with eta = 0.01, for every m >= 2 and n >= 0,
sum_{j<=n} f(u_{m,j}) <= (2 + eta) S_m + C n delta_m^2. (15)
Proof. If |cos(pi u)| >= gamma and |v| <= gamma/(2 pi), then
f(u + v) <= (1 + eta) f(u) + C v^2. (16)
Indeed, the absolute cosine is at least gamma/2 on the segment from u to u+v, so |f''| is bounded there. Also |f'(u)| <= (pi/gamma) sqrt(2 f(u)), because 1 - |cos(pi u)|^2 <= 2 f(u). Taylor's formula and |f'(u) v| <= eta f(u) + C v^2 prove (16).
The map f is even and 1-periodic. Reflecting positive indices by the trace identity (9) and using (12) gives
f(u_{m,i}) <= (1 + eta) f(u_{m,-i}) + C delta_m^2 (m >= 2, i >= 1). (17)
Summing this inequality proves (15). To estimate S_{m+1}, apply (16) to the identity u_{m+1,j} = u_{m,j+k} - u_{m,j-k}, at the base point u_{m,j+k} and perturbation v = -u_{m,j-k}, with k = k_{m+1}. The cosine floor (11) holds at the base point, including for positive j. The squared perturbations have a convergent geometric sum, giving
S_{m+1} <= (1 + eta) ( S_m + sum_{i=1}^k f(u_{m,i}) ) + C beta^{2 (b_m - k)},
S_{m+1} <= (1 + eta) (2 + eta) S_m + C (1 + k delta_m^2).
By (10) the term k delta_m^2 is at most exp(-0.1 L_m) <= 1. Therefore S_{m+1} <= r S_m + C with r = (1.01)(2.01) = 2.0301. The already fixed value S_2 is finite, so S_m = O(r^{m-2}). On the other hand L_m >= 2.1^{m-3} L_3 for m >= 3. Since r < 2.1 the ratio S_m / L_m tends to zero.
Independent blocks of Fourier phases. Work on the probability space of independent uniform signs (epsilon_l)_{l >= 0}, write Y = sum_{l >= 0} epsilon_l beta^{-l} of law nu_{1/beta}, and set W_{m,n} = exp(i pi A_m beta^n Y). The support of nu_{1/beta} is I = [-(1 - beta^{-1})^{-1}, (1 - beta^{-1})^{-1}]. Independence followed by passage to the limit in the convergent sign series gives
E W_{m,n} = prod_{j <= n} cos(pi u_{m,j}) (18)
for n >= 0; this product is a nonzero real number because the negative-index tail has a convergent sum of logarithmic losses.
Set J_m = floor(exp(1.5 L_m)), H_m = ceil(b_m + D L_m), and N_m = { H_m + s (2 H_m + 1) : s in Z_{>=0} } cap [0, J_m], with M_m = #N_m. The asymptotic estimates that follow hold as m -> infty. Since H_m <= K_m <= exp(0.75 L_m),
exp(0.7 L_m) <= M_m <= J_m + 1. (19)
Lemma 11 and J_m delta_m^2 <= exp(-0.5 L_m) give
|E W_{m,n}| >= exp(-L_m / 20) for 0 <= n <= J_m. (20)
For n in N_m, retain only the signs whose indices lie in [n - H_m, n + H_m] and define
W~_{m,n} = (-1)^{ sum_{j=H_m+1}^n T_{m,j} } exp( i pi sum_{l = n-H_m}^{n+H_m} u_{m,n-l} epsilon_l ). (21)
The integer sum in the prefactor is empty when n = H_m. The exponent of W_{m,n} expands as pi sum_{j<=n} u_{m,j} epsilon_{n-j}. For j > H_m, replace u_{m,j} by its integer trace T_{m,j}: the resulting factor e^{i pi T_{m,j} epsilon_{n-j}} is the deterministic (-1)^{T_{m,j}}. For j < -H_m, drop the term. The remaining indices are exactly those in (21). The difference between W_{m,n} and W~_{m,n} is a sum of independent mean-zero signs, so |e^{ix} - e^{iy}| <= |x - y| gives
||W_{m,n} - W~_{m,n}||_2^2 <= pi^2 ( sum_{j>H_m, j<=n} |u_{m,j} - T_{m,j}|^2 + sum_{j < -H_m} |u_{m,j}|^2 )
<= C ( beta^{2 (b_m - H_m)} + n delta_m^2 ) <= C exp(-L_m/2). (22)
The first summand is bounded using (9), a geometric tail, and a contribution C n delta_m^2; the second is a geometric tail. The final inequality uses H_m >= b_m + D L_m with D log beta = 10 and n <= J_m. All norms refer to the sign probability space. The windows belonging to consecutive members of N_m are disjoint, so the variables W~_{m,n} are independent.
Proof of Theorem B. For n in N_m let sigma_{m,n} in {-1,1} be the sign of the real expectation (18), and define the continuous function
F_m(y) = (1/M_m) sum_{n in N_m} sigma_{m,n} exp( i pi A_m beta^n y ). (23)
Its mean at Y is real and, by (20), a_m := E F_m(Y) >= exp(-L_m/20). The corresponding average of the independent variables sigma_{m,n} W~_{m,n} has centered L^2 norm at most M_m^{-1/2}, since each has modulus one. By the triangle inequality and (22),
||F_m(Y) - a_m||_2 <= M_m^{-1/2} + C exp(-L_m/4). (24)
The means of the approximation errors contribute at most a factor two, absorbed into C.
In Lebesgue L^2(I) the same average is small. Its frequencies in increasing order xi_1 < ... < xi_{M_m} satisfy xi_{r+1} - xi_r >= pi (beta - 1), since A_m >= 1 and the exponents beta^n are distinct. Hence |xi_r - xi_s| >= pi (beta - 1) |r - s| and
|int_I e^{i (xi_r - xi_s) y} dy| <= 2 / |xi_r - xi_s| (r != s).
Expanding the square and summing by the rank difference yields
int_I |F_m(y)|^2 dy <= C (1 + log M_m)/M_m. (25)
Now let E_m = { y in I : Re F_m(y) >= (1/2) exp(-L_m/20) }. Chebyshev's inequality, (24), and (19) imply
1 - nu_{1/beta}(E_m) <= 4 exp(L_m/10) (M_m^{-1/2} + C exp(-L_m/4))^2 -> 0. (26)
Likewise, with |E_m| denoting Lebesgue measure,
|E_m| <= 4 exp(L_m/10) int_I |F_m(y)|^2 dy <= C exp(L_m/10) (1 + log M_m)/M_m -> 0, (27)
because M_m >= exp(0.7 L_m) and log M_m <= 1.5 L_m + O(1). Choose a subsequence m_r along which sum_r (|E_{m_r}| + 1 - nu_{1/beta}(E_{m_r})) converges. Then E = limsup_r E_{m_r} is Borel, is Lebesgue null because |union_{r>=R} E_{m_r}| <= sum_{r>=R} |E_{m_r}| -> 0, and satisfies nu_{1/beta}(E) = 1 because summable complementary probabilities put almost every point in all sufficiently late E_{m_r}. This proves nu_{1/beta}(E) = 1 and |E| = 0, hence singularity.
Two explicit parameters. Let beta_1 and beta_2 be the real roots greater than one of P_1(x) = x^4 - x^3 - x^2 - x + 1 and P_2(x) = x^4 - 2 x^3 + x^2 - 2 x + 1. Then beta_1, beta_2 in (1,2) and nu_{1/beta_i} is singular for i = 1, 2.
Proof. In the variable y = x + x^{-1} the equation P_i(x)/x^2 = 0 becomes respectively y^2 - y - 3 = 0 for i = 1 and y^2 - 2 y - 1 = 0 for i = 2. Their larger roots are y_1 = (1 + sqrt 13)/2 and y_2 = 1 + sqrt 2, both in the open interval (2, 5/2). For each i the equation x + x^{-1} = y_i has one root beta_i in (1,2) and its reciprocal beta_i^{-1}, and the other root y_i' of the quadratic lies in (-2,2), so the remaining two roots of P_i are a nonreal conjugate pair on the unit circle.
It remains to check that the four roots of P_i are Galois conjugate. The quadratic field Q(y_i) is real, and the discriminant y_i^2 - 4 has negative image (y_i')^2 - 4 under the nontrivial embedding. This discriminant cannot be a perfect square in Q(y_i): the image of a square under a real embedding is nonnegative, yet (y_i')^2 - 4 < 0. Hence x^2 - y_i x + 1 is irreducible over Q(y_i), and [Q(beta_i) : Q] = 4. Both beta_1 and beta_2 are degree-four Salem numbers, and Theorem B applies at both.
A weakly expanding conjugate pair. The final example uses one conjugate pair of a degree-31 polynomial that lies just outside the unit circle. Counting all polynomial values in a way that respects conjugate coordinates slightly overshoots the box volume; the gap is closed by a product of positive trigonometric factors whose integral on the expanding coordinate stays bounded while on typical words it grows exponentially. Throughout this section every terminating decimal denotes the exact rational number with that decimal expansion.
Put p(t) = t^{31} - 2 t^{30} + sum_{j=0}^{9} (t^{3 j + 1} - t^{3 j}). The identity
(t^2 + t + 1) p(t) = t^{33} - t^{32} - t^{31} - t^{30} - 1 (28)
controls the near-cancellations in the trigonometric product.
Proposition 12 (root bounds). Every root of p is simple. Its roots outside the unit circle are beta, alpha, alphabar, where beta is real, Im alpha > 0, and
1.8392 < beta < 1.8393, 1.0002089 < |alpha|^2 < 1.0002094, |alpha|^{-1} < 0.9999. (29)
The remaining fourteen pairs of roots are nonreal conjugates each of modulus below 0.994. The proposition is proved by exact rational root disks in the rational certificate; the rest of the argument uses only (29).
The expanding volume factor is M = prod_{r in D} |r| = beta |alpha|^2 where D = {beta, alpha, alphabar} and I = the remaining roots. Inequality (29) and log(1 + u) < u give
log M < log beta + 0.0002094. (30)
Non-Pisot. The root bounds alone rule out Pisot. If beta were Pisot, then dividing p by its monic minimal polynomial would give a quotient that is monic and integral, whose constant term is +-1, and which contains alpha and alphabar among its roots but not beta. The product of the moduli of the quotient's roots is at least 1.0002089 * 1.0002089 * 0.994 > 1 if the quotient avoids I, and at most 1.0002094 * 0.994 < 1 if it has roots in I. Either way the product contradicts the integrality of the constant term. So beta is not Pisot, and only singularity remains.
Word vectors and characters. For a word a = (a_0,...,a_{N-1}) in {0,1}^N define y_r(a) = sum_{j<N} a_j r^j for r in D cup I, and x_r(a) = r^{-N} y_r(a) for r in D. Vectors indexed by roots are constrained by y_{rbar} = conjugate(y_r), and a conjugate pair counts as one complex coordinate, i.e. two real coordinates. The space of all y-vectors has real dimension 31.
Lemma 13 (lattice). All vectors y(a) for all N and all words a lie in a fixed full lattice of this real vector space, and their contracting coordinates (y_r)_{r in I} and normalised expanding coordinates (x_r)_{r in D} lie in fixed bounded boxes. The change from (x_D,y_I) to (y_D,y_I) has Jacobian determinant of absolute value M^N.
Proof. Reducing sum a_j t^j modulo the monic polynomial p gives an integer vector of length 31. Evaluation at the roots is an invertible real-linear map because a polynomial of degree at most 30 vanishing at all 31 distinct roots is zero. The image of Z^{31} is the required lattice. The coordinate bounds follow from |y_r(a)| <= 1/(1 - |r|) for r in I and |x_r(a)| <= 1/(|r| - 1) for r in D. Multiplication of the real coordinate by beta^N and the complex coordinate by alpha^N has determinant beta^N |alpha|^{2 N} = M^N.
The Fourier coefficients of 1/p. Define the two-sided real sequences C_0 and C_1 by
C_0(m) = sum_{r in I} r^{-1-m}/p'(r) for m < 0; C_0(m) = -sum_{r in D} r^{-1-m}/p'(r) for m >= 0;
C_1(m) = C_0(m + 3) - C_0(m) + C_0(m - 1). (31)
Partial fractions give 1/p(t) = sum_{m in Z} C_0(m) t^m on the annulus max_{r in I} |r| < |t| < min_{r in D} |r|, so C_0 is the two-sided Laurent coefficient sequence of 1/p, and both C_0 and C_1 decay exponentially at both ends. The same inversion by an exponentially decaying two-sided sequence underlies Lind and Schmidt's construction of homoclinic points for algebraic actions (Lind-Schmidt 1999):
https://doi.org/10.1090/S0894-0347-99-00306-9
The explicit roots yield characters adapted to the word vectors.
For arbitrary expanding coordinates x_D with x_beta real and x_alphabar = conjugate(x_alpha), put
Z_i^{(0,N)}(x) = exp( -2 pi i sum_{r in D} x_r r^i / p'(r) ) exp( -pi i sum_{k < N} C_0(k - i) ),
Z_i^{(1,N)}(x) = Z_{i-3}^{(0,N)}(x) * conjugate(Z_i^{(0,N)}(x)) * Z_{i+1}^{(0,N)}(x). (32)
These functions have modulus one.
Lemma 14 (characters at word vectors). If b_k = a_{N-1-k}, then for A in {0,1} and i in Z,
Z_i^{(A,N)}(x(a)) = exp( pi i sum_{k < N} C_A(k - i) (2 b_k - 1) ). (33)
Proof. The reversed word gives x_r(a) = sum_{k < N} b_k r^{-1-k}. For each integer l >= 0, Lagrange interpolation shows that
sum_{r in D cup I} r^l / p'(r)
is the coefficient of t^{30} in the remainder of t^l modulo p, hence is an integer. Consequently, when m < 0, the coefficient -sum_{r in D} r^{-1-m}/p'(r) differs from C_0(m) by an integer; its contribution to the exponent, with coefficient 2 pi i b_k, is unchanged. When m >= 0 the coefficients already agree. The second factor in (32) supplies the centering by -1, proving the formula at A = 0. Multiplication of the three characters gives A = 1.
The stationary model uses independent fair bits (b_k)_{k in Z} and the unit random variables Zhat_i^{(A)} = exp( pi i sum_{k in Z} C_A(k - i) (2 b_k - 1) ), whose series converges absolutely. Independence gives the real moments
P_A = E Zhat_i^{(A)} = prod_{m in Z} cos(pi C_A(m)),
P_{AB}^+(k) = E[Zhat_i^{(A)} Zhat_{i-k}^{(B)}] = prod_m cos(pi (C_A(m) + C_B(m + k))),
P_{AB}^-(k) = E[Zhat_i^{(A)} conjugate(Zhat_{i-k}^{(B)})] = prod_m cos(pi (C_A(m) - C_B(m + k))). (34)
A predictor. The weak expanding pair makes long decaying tails in C_0 that nearly cancel in the shifted products P_{00}^+(k) and P_{00}^-(k). A linear combination of these phases therefore has positive correlation with Zhat_i^{(0)}. For rational weights w_{ks} define
G_i^{(N)}(x) = -0.001 + 0.0055 Z_{i-33}^{(1,N)}(x) + sum_{k=30}^{2000} sum_{s=0}^1 w_{ks} (Z_{i-k}^{(0,N)}(x))^{1-2s},
Ghat_i = -0.001 + 0.0055 Zhat_{i-33}^{(1)} + sum_{k=30}^{2000} sum_{s=0}^1 w_{ks} (Zhat_{i-k}^{(0)})^{1-2s},
L_i = Re( Zhat_i^{(0)} Ghat_i ). (35)
Proposition 15 (predictor estimates). There are weights w_{ks} in 10^{-9} Z, indexed by 30 <= k <= 2000 and s in {0,1}, such that
0.001 + 0.0055 + sum_{k,s} |w_{ks}| = 198442946 / 10^9 < x_* := 0.199 (36)
and, in the stationary model,
E L_i > 0.000210, E|Ghat_i|^2 < 0.000145, |E[(Zhat_i^{(0)})^2 Ghat_i^2]| < 0.000007. (37)
In particular |G_i^{(N)}(x)| <= x_* for every N, i, and x, and |Ghat_i| <= x_* for every bit sequence. The exact rational values of the w_{ks} are specified by the rational certificate, and the moment inequalities are proved by the same finite computation.
Damping. Choose i_0 >= 1 so that 0.1 beta^{i_0} / |p'(beta)| > 1. For a word length N use every complete block B_q = { i_0 + 22 q, ..., i_0 + 22 q + 20 } subset of {0,...,N-1}, and let J_N be their union. Each block has 21 indices and consecutive blocks are separated by one unused index.
The relation (28) dictates which signed digit patterns are retained when a block is integrated. For a pattern (d_i)_{i in B_q} in {-1,0,1}^{B_q}, let b = max B_q and set v_i = beta^{-i} sum_{j=i}^b d_j beta^j, v_{b+1} = 0. Reading from the largest index downward gives v_i = beta v_{i+1} + d_i. At the root beta, relation (28) becomes
beta^3 - beta^2 - beta - 1 = beta^{-30}. (38)
When the digit vector starts [sigma, -sigma, -sigma, -sigma] with sigma in {-1,1}, the normalized remainder is sigma beta^{-30}, i.e. very small. The admissible digit patterns are the words accepted by the following automaton (read from high exponents to low exponents).
initial state 0, permitted terminal states {0, C_+, C_-}, two copies of the nonzero states, one per sign sigma:
transitions: 0 --0--> 0, 0 --sigma--> A_sigma,
A_sigma --(-sigma)--> B_sigma, B_sigma --(-sigma)--> C_sigma,
C_sigma --0--> A_sigma, C_sigma --(-sigma)--> 0.
The state values are: 0; A_sigma = sigma; B_sigma = sigma(beta - 1); C_sigma = sigma(beta^2 - beta - 1). A pattern is admissible if every transition is allowed and its terminal state is one of 0, C_+, C_-.
Let o(d) = #{ i : d_i != 0 }. At a position i of a block, define
eta_i = sum_{ d admissible, d_i != 0 } x_*^{o(d)-2} / o(d). (39)
The same coefficients are repeated in every block. Every admissible nonzero pattern has at least three nonzero digits, so the summands are well defined.
Lemma 16 (cost of admissible patterns). Set
S_* = (1 + 2 x_*^4 / (1 - x_*^2))^{18} (1 + 2 x_*^3 / (1 - x_*^2)) - 1. (40)
Then S_* < 0.081 and
sum_{d admissible, o(d) > 0} x_*^{o(d)} <= S_*, eta_i x_*^2 <= S_*/3,
eta_bar/(1 - S_*/3) < 0.101 where eta_bar = (1/21) sum_{i in B_q} eta_i. (41)
Proof. A completed excursion from 0 to 0 has the digit string [sigma, -sigma, -sigma, (0, -sigma, -sigma)^l, -sigma] with l >= 0, having 4 + 2l nonzero digits, and can begin in at most 18 positions of a block. An optional final excursion ending at C_sigma has the same form without the last digit; its sign and length determine its start. Ignoring compatibility between successive choices overcounts the admissible patterns and gives (40). At x_* = 0.199 the two fractions in (40) are less than 0.00327 and 0.01642. The inequality (1 + a)^{18} <= (1 - 18 a)^{-1}, valid for 0 <= 18 a < 1, proves S_* < 0.081 by rational arithmetic. Since o(d) >= 3 each summand in eta_i x_*^2 is at most x_*^{o(d)}/3. Summing (39) over positions gives sum_i eta_i <= S_*/x_*^2, hence eta_bar/(1 - S_*/3) <= 0.081/(21 * 0.199^2 * (1 - 0.081/3)) < 0.101.
A positive product. Fix N and abbreviate Z_i = Z_i^{(0,N)}, G_i = G_i^{(N)}, x_i = |G_i|. Define
h_i = 1 - eta_i x_i^2, F_i = h_i (1 + (1 - x_i^2)(Z_i G_i + conjugate(Z_i G_i))). (42)
These factors are bounded above and bounded away from zero uniformly in N, i, and x_D: h_i >= 1 - S_*/3 and the other factor is at least 1 - 2 x_* > 0.
Proposition 17 (bounded integral). For every N and every fixed complex coordinate x_alpha,
int_R psi(x_beta) prod_{i in J_N} F_i(x_D) dx_beta <= int_R psi(x_beta) dx_beta, (43)
where psi(v) = (sin(pi v/10)/(pi v/10))^2 and psi(0) = 1.
Proof. Use the Fourier convention e^{2 pi i xi x_beta}. The nonnegative function psi has Fourier transform supported in [-0.1, 0.1], hence in [-1, 1]. After factoring out the common frequency -1/p'(beta), the frequency of Z_i is beta^i, and every phase in G_i has frequency of absolute value at most beta^{i-30}: for the type-1 term this follows from |beta^{i-33}(beta^{-3} - 1 + beta)| <= beta^{i-30}. The predictor frequencies are called slow. Expanding a factor F_i produces monomials with one fast digit d_i in {-1,0,1} corresponding to Z_i^{d_i}, and at most five slow frequencies: two from h_i, two from 1 - |G_i|^2, and one from G_i or its conjugate.
Expand the last block according to its fast digits, keeping all earlier factors for the moment. Any inadmissible pattern gives zero integral, even after multiplication by earlier factors. Expand the earlier factors and all slow pieces into monomials; if the current index is i, the fast sum accumulated from the top of the last block, divided by beta^i, follows the recurrence v -> beta v + d_i. By (38), every allowed transition matches the state values up to injected error beta^{-30}. The propagated error, including at the first forbidden step, is bounded by beta^{-30} beta^{21}/(beta - 1) < 0.005. At a first forbidden step the ideal absolute value is at least beta(beta - 1) for a departure from A_sigma or B_sigma and at least 2 for a departure from C_sigma; after the injected error it is greater than 1.5. All lower fast digits together contribute at most (beta - 1)^{-1} < 1.192 in the same units. If instead all transitions are allowed but the terminal state is A_sigma or B_sigma, the absolute value at the bottom index i is at least beta - 1 - 0.005; the one-index gap then bounds the earlier fast terms by 1/(beta(beta - 1)) < 0.649. In either case, all slow terms (including those from earlier blocks) contribute at most 5 beta^{-30} beta^{21}/(beta - 1) < 0.025 relative to beta^i: sum at most five frequencies of size beta^{j - 30} over indices j no larger than the top of the last block, which is at most i + 20. The full frequency therefore has absolute value greater than 0.1 beta^i / |p'(beta)| > 1 by the definition of i_0, and its integral against psi vanishes.
After removing the vanishing monomials, the last block contributes prod_{i in B_q} h_i times the sum over admissible fast patterns. The zero pattern contributes one. Any nonzero pattern has absolute value at most prod_{d_i != 0} x_i, and the AM-GM inequality gives prod_{d_i != 0} x_i <= x_*^{o(d)-2} (1/o(d)) sum_{d_i != 0} x_i^2. The absolute value of the retained pattern sum is therefore at most 1 + sum_{i in B_q} eta_i x_i^2. Writing t_i = eta_i x_i^2 with 0 <= t_i < 1,
prod_{i in B_q} (1 - t_i) (1 + sum_{i in B_q} t_i) <= 1,
because prod (1 - t_i) <= exp(-sum t_i). Since psi and all earlier factors are nonnegative, removing the last block only increases the upper bound for the integral. Iterating over the preceding blocks gives (43).
Lemma 18 (log inequality). For 0 <= x <= x_* and |u| <= 2 x,
log(1 + (1 - x^2) u) >= u - u^2/2 - C_* x^3, C_* = 2/(3 sqrt(1 - x_*^2)). (44)
Proof. The assertion is immediate for x = 0. Otherwise let D_x(u) = u - u^2/2 - log(1 + (1 - x^2) u). Its derivative is
D_x'(u) = (x^2 - x^2 u - (1 - x^2) u^2) / (1 + (1 - x^2) u).
For u >= 0 this is at most the positive part of x^2 - (1 - x^2) u^2. Integrating that positive part over [0, infty) gives 2 x^3/(3 sqrt(1 - x^2)) <= C_* x^3. On [-2 x, 0] the only possible interior critical point is a minimum, so the maximum is at an endpoint. D_x(0) = 0 and
d/dx D_x(-2 x) = 2 x^2 (1 - 2 x - 4 x^2)/(1 - 2 x + 2 x^3) <= 2 x^2,
hence D_x(-2 x) <= 2 x^3/3 <= C_* x^3.
Typical gain. Evaluate the same factors (42) in the stationary model, replacing Z_i and G_i by Zhat_i^{(0)} and Ghat_i. The damping coefficients are periodic with period 22 and are used at the same 21 positions per period.
Proposition 19 (growth on typical words). For uniformly distributed words a in {0,1}^N,
Pr{ sum_{i in J_N} log F_i(x(a)) > 0.000220 N } -> 1. (45)
Proof. Apply (44) with x = |Ghat_i| and u = 2 L_i. The identity
2 E L_i^2 = E|Ghat_i|^2 + Re E[(Zhat_i^{(0)})^2 Ghat_i^2]
and the bound E|Ghat_i|^3 <= x_* E|Ghat_i|^2 control the second- and third-order terms. Also
log(1 - eta_i |Ghat_i|^2) >= -eta_i |Ghat_i|^2/(1 - S_*/3).
Set gamma = (1/22) sum_{i in B_0} E log Fhat_i, where the division by 22 includes the unused index. Since C_* x_* < 0.136, Proposition 15 and Lemma 16 give
gamma >= (21/22) ( 2 E L_0 - (1 + C_* x_* + eta_bar/(1 - S_*/3)) E|Ghat_0|^2 - |E[(Zhat_0^{(0)})^2 Ghat_0^2]| )
> (21/22) ( 2 * 0.000210 - 1.237 * 0.000145 - 0.000007 ) > 0.000222. (46)
For completeness, passage from this mean to finite words uses truncation. Truncate each sequence C_A to [-H, H] for a fixed integer H. The stationary logarithmic block sums formed from the truncated sequences depend on finitely many bits, are uniformly bounded, have the same mean from block to block, and are independent when their blocks are sufficiently far apart; hence the variance of an average of Q such block sums is O_H(Q^{-1}) and their averages converge in probability to their means. Absolute summability of C_0 and C_1 makes the truncated characters uniformly close to the originals as H -> infty; the predictors are finite sums with bounded total absolute weight, and the factors are uniformly bounded away from zero, so the logarithms also converge uniformly. After H -> infty with N -> infty,
(1/N) sum_{i in J_N} log Fhat_i -> gamma in probability. (47)
Couple the reversed word bits to (b_0,...,b_{N-1}) in a stationary sequence. For fixed H the truncated finite and stationary characters used in a factor agree whenever H + 2000 <= i <= N - 1 - H, so only a number of boundary indices depending on H, not on N, remain. The same uniform approximation gives
(1/N) ( sum_{i in J_N} log F_i(x(a)) - sum_{i in J_N} log Fhat_i ) -> 0
uniformly over the coupled bit sequences. Together with (46) this proves (45).
Lemma 20 (thickening word vectors). There are constants rho > 0 and C_thick < infty, independent of N, such that the radius-rho balls about distinct lattice points of Lemma 13 are disjoint, and whenever y' lies in the ball about y(a),
| sum_{i in J_N} log F_i(x'_D) - sum_{i in J_N} log F_i(x_D(a)) | <= C_thick, (48)
where x'_r = r^{-N} y'_r for r in D.
Proof. Choose rho <= 1 smaller than half the minimal distance between distinct lattice points. A coordinate change of size at most one in y changes the exponent of Z_j^{(0,N)} by at most 2 pi sum_{r in D} |r|^{j - N}/|p'(r)|. Every character occurring in F_i, including those in the type-1 term of the predictor, has index at most i. The logarithm of F_i is uniformly Lipschitz in these unit phases since the coefficient sums and damping coefficients are bounded and F_i is uniformly positive, so its variation is at most a constant times sum_{r in D} |r|^{i - N}. Finally,
sum_{i in J_N} |r|^{i - N} <= sum_{i < N} |r|^{i - N} < 1/(|r| - 1) for r in D,
which gives a bound independent of N.
Proof of Theorem C. The root assertion and the fact that beta is not Pisot were proved with the root bounds. Call a word typical if it satisfies (45), and let cal-Y_N be the set of distinct vectors y(a) obtained from typical words. Typical words have probability tending to one. Lemma 20 implies that, for all sufficiently large N, prod_{i in J_N} F_i > exp(0.000216 N) throughout each of the disjoint balls about cal-Y_N.
All these balls lie in fixed bounded boxes in (x_D, y_I) coordinates, enlarged from those of Lemma 13. In the real coordinate x_beta one may take |x_beta| <= 3. The function psi has a positive minimum on [-3, 3]. Integrating first in x_beta, Proposition 17 bounds the integral of the product over this fixed box by a constant independent of N. The product does not depend on y_I. Changing back to y coordinates contributes the Jacobian M^N. Comparing the integral with the disjoint balls, each of positive volume, gives
#cal-Y_N <= C_count exp( (log M - 0.000216) N ) (49)
for a constant C_count.
Let mu be the law of sum_{k >= 0} b_k beta^{-k} for independent fair bits. By reversal in Lemma 13, its length-N prefix has the distribution of beta x_beta(a). Projecting cal-Y_N to this coordinate cannot increase its cardinality. For each resulting prefix value attach an interval of length beta^{-N}/(1 - 1/beta) that contains all possible remaining tails. The union K_N is compact, mu(K_N) -> 1, and (30) combined with (49) gives
|K_N| <= C_cover exp( (0.0002094 - 0.000216) N ) = C_cover exp(-0.0000066 N). (50)
Choose a subsequence N_j with mu(K_{N_j}) > 1 - 2^{-j}. Then liminf_j K_{N_j} has full mu-measure and zero Lebesgue measure. Hence mu is singular. Finally, sum_{k >= 0} (2 b_k - 1) beta^{-k} = 2 sum_{k >= 0} b_k beta^{-k} - 1/(1 - beta^{-1}), so nu_{1/beta} is an affine image of mu and is singular as well.
The rational certificate. The propositions and lemmas just proved depend on exact rational inputs (predictor weights and bounds, root bounds, moment values) that are not verified in the main argument. The next seven items pin them down. Every step is specified with a concrete rounding rule and a concrete order of operations; all arithmetic is exact rational arithmetic, and only additions, subtractions, multiplications, and floor-toward-negative-infinity appear.
Locating the roots. Recall p(t) = sum_{j=0}^9 (-t^{3j} + t^{3j+1}) - 2 t^{30} + t^{31}. Put E = 10^{40}. The following sixteen rational centers z = (a + i b)/E (each with an implicit conjugate for b != 0) are the centers of 31 disks of radius delta = 10^{-35}:
real numerator imaginary numerator
18392867573155250211326543340571993487329 0
-9741384652837567528189111907762645564212 960611633124778624015947511546714789832
-9390979934023233037686839914141181659013 2848063934279278841200845525848576791934
-8707010393241200595697704637503228167256 4634358961359777463662031763152574795910
-7723118558199735333585947045021501410451 6250214494152701297733561366714273855663
-6480873022754265587670654805348739312397 7617033927823246411701558316834470378693
-3296776282962928450195355562079974291919 9362810613239308448752821856735617305389
-1442513481645415489053007250852371013818 9733039088635544125591234293715446465839
473579005983151143865690217073943282984 9759329295153416086962240697595385836176
2372858204750359429049351486827380431084 9430908396110323024329804770889268443510
4184061662454447896993374181551299054853 8750376307352230997951514116951420713869
5840543823426662247726359012202878127980 7733999914049269380846159864123679516166
7280042164772721585016920411987150804420 6409668313572020921539025901166241650504
8444162922855313595050499086097221186662 4814843758334683329011653039104490553475
9275649862302447872891854755866108397375 2996533501299661135726051235425500195711
9715324892541617145821300300817663390044 1019107767839771580294306582422817927060
The first and sixth centers are z_beta and z_alpha respectively. For a complex number write ||z||_1 = |Re z| + |Im z| and ||z||_infty = max(|Re z|, |Im z|). Exact Horner evaluation at every displayed center gives
|z| < 2, ||p'(z)||_infty > 1, 2 * 10^{35} ||p(z)||_1 < ||p'(z)||_infty. (51)
Integer prescription for these comparisons: for q(t) = sum_{j=0}^d q_j t^j and a Gaussian integer Z = Ez, initialise (V, h) = (q_d, 1) and for j = d-1, d-2,...,0 replace h <- E h and V <- Z V + h q_j. The final value is q(z) = V/h. Apply this to p and p', and clear the positive denominators in (51). Comparing squared distances gives |z - z'| > 0.01 for distinct centers, counting conjugates. Comparing coordinates and squared moduli gives
1.83928 < z_beta < 1.83929, 1.0002090 < |z_alpha|^2 < 1.0002093, |z| < 0.9939 at the other centers. (52)
For |h| = delta, the terms of degree at least two in p(z+h) - p(z) - p'(z) h have total modulus at most delta^2 sum_{j=0}^{31} |p_j| 3^j < 10^{17} delta^2, since |z| < 2 and delta < 1. By (51) the constant term is below |p'(z)| delta/2, whereas the displayed remainder is below |p'(z)| delta/2 as well. Rouché's theorem therefore puts exactly one simple root in each disk. The disks are disjoint and their number equals the degree, so this accounts for all roots. The root in the real-centered disk is real by conjugation; every other disk misses the real axis, so the remaining roots form fifteen nonreal conjugate pairs. The radius delta and the bounds (52) imply Proposition 12, including |alpha|^{-1} < 0.9999.
Rounded coefficient arrays. Let C_0, C_1 be the coefficient sequences (31). The single and paired moments
P_A = prod_{m in Z} cos(pi C_A(m)), P_{AB}^sigma(k) = prod_m cos(pi (C_A(m) + sigma C_B(m + k))) (53)
converge because the coefficients decay geometrically. Use the constants
S = 10^{30}, R = 3000, H = 100, K = 2000, W = 10^9. (54)
For a real rational x set [x] = floor(S x + 1/2)/S; for a complex number round componentwise. Thus if x = u/v in lowest terms with v > 0, its rounded numerator is floor((2 S u + v)/(2 v)). Set
pi' = 3141592653589793238462643383279/S. (55)
That |pi' - pi| < 1/S follows from 30 terms of the alternating series for arctan(1/5) and 10 for arctan(1/239) in Machin's identity pi = 16 arctan(1/5) - 4 arctan(1/239); the total remainder bound is 16/(61 * 5^{61}) + 4/(21 * 239^{21}).
For each representative center z of the root table form r_z = [1/p'(z)], with p'(z) evaluated exactly. Store a base and a coefficient:
(a_z,v_z) = ([z], r_z) for |z| < 1; (a_z,v_z) = ([1/z], -[[1/z] r_z]) for |z| > 1. (56)
For a contracting representative, start v = v_z and add 2 Re v to c_0(-1), then to c_0(-2), c_0(-3),..., replacing v <- [v a_z] after each addition. For an expanding representative do the same on c_0(0), c_0(1),...; the multiplier is 1 for the real root and 2 for the nonreal representative. All arrays start at zero. Compute c_0(m) on -R - K - 5 <= m <= H + K + 5 and define
c_1(m) = c_0(m + 3) - c_0(m) + c_0(m - 1). (57)
The extra endpoint entries ensure every later use of c_1 lies in its defined range.
The following three procedures use only rational arithmetic. First, for a rational input c compute rounded cosine and sine by the ordered Taylor sums
x = [pi' c]; y = [x x]; t = 1; u = x; g = t; h = u;
for j = 1,...,50: t = [-t y/(2 j (2 j - 1))]; u = [-u y/(2 j (2 j + 1))]; g = g + t; h = h + u;
return (g,h). (58)
Write g_A(m) = g(c_A(m)) and h_A(m) = h(c_A(m)).
Second, treat the weak expanding pair alpha, alphabar. Set
a = 1/alpha, u_0 = -a/p'(alpha), u_1 = u_0 (a^3 - 1 + 1/a). (59)
Their contribution to C_A(m) for m >= H is u_A a^m + conjugate(u_A a^m). Let (a', u'_0) be the pair in (56) belonging to z_alpha, and compute
a'_0 = 1, a'_{n+1} = [a' a'_n] (0 <= n < K), u'_1 = [u'_0 (a'_3 - 1 + [1/a'])]. (60)
Third, for a single moment use w = u'_A and k = 0; for a paired moment of types A, B in {0,1}, sign sigma in {1,-1}, and lag 0 <= k <= K, use w = u'_A + sigma [u'_B a'_k]. In either case the following loop returns an approximate moment:
U = [w a'_H];
q_0 = 1; q_i = [q_{i-1} U] (i = 1,...,6);
b_0 = 1; b_i = [b_{i-1} pi'] (i = 1,...,6);
pen = 0;
for d = 2,4,6:
mom = 0;
for j = 0,...,d:
num = [q_j conjugate(q_{d-j})];
den = 1 - [a'_j conjugate(a'_{d-j})];
mom = mom + binomial(d,j) Re([num/den]);
pen = pen + [b_d mom / f_d] where (f_2,f_4,f_6) = (2,12,45);
x = [-pen/32]; t = 1; value = t;
for j = 1,...,40: t = [t x/j]; value = value + t;
repeat five times: value = [value value];
for m = -R-k,...,H-1 in increasing order:
v = g_A(m) for single; v = [g_A(m) g_B(m+k) - sigma h_A(m) h_B(m+k)] for paired;
value = [value v];
return value. (61)
Denote the results by Ptilde_A and Ptilde_{AB}^sigma(k). Only lags 30 <= k <= 2000 are used. Write s = 0 for sigma = 1 and s = 1 for sigma = -1, set r = Ptilde_{00}^sigma(k), and put
w_{ks} = (sgn(r)/W) floor(0.68 W max(0, |r| - 0.00026) + 1/2), 30 <= k <= 2000. (62)
Take sgn(0) = 0 and omit zero weights. The displayed recurrences and this formula define the weight vector w_{ks} without any choices or tolerances.
A uniform error bound. Let P_A, P_{AB}^sigma(k) be as in (53) and Ptilde_A, Ptilde_{AB}^sigma(k) as in (61). Then
|Ptilde_A - P_A| < Delta, |Ptilde_{AB}^sigma(k) - P_{AB}^sigma(k)| < Delta, Delta = 5 * 10^{-6}, (63)
for all types, signs, and lags used in the moment bounds.
Coefficient and trigonometric errors. For |z| < 2.001, termwise differentiation gives |p''(z)| < 4 * 10^{13}, so p' changes by less than 4 * 10^{-22} between a center and its contained root. By (51) and (52) and the reciprocal differentiation r_z = 1/p'(z), the base and coefficient errors in (56) are less than 2/S and 10^{-21}. Squared-modulus comparisons give |a_z| < 1 and |v_z| <= 1 at every stored pair, and the exact coefficients have modulus below 1.001. Hence each recurrence step v <- [v a_z] propagates the error with factor at most 1 and adds less than 4/S. Fewer than 5100 such steps occur in any needed entry, so each coefficient-times-power term has error below 2 * 10^{-21} and
|c_0(m) - C_0(m)| < 7 * 10^{-20}, |c_1(m) - C_1(m)| < 2.1 * 10^{-19}. (64)
Array bounds. The same finite recurrence gives the following exact rational comparisons; use squared moduli for complex entries u'_A:
max_{A,m} |c_A(m)| < 0.847, max_{m >= -20} |c_0(m)| < 0.018,
max_A |u'_A| < 0.0087, 0.8460 < max_{A,m} |c_A(m)| < 0.8462. (65)
Any later trigonometric input is a sum of at most four of these coefficients, counted with multiplicity; its error is below 10^{-18}, and the rounded angle satisfies |x| <= 13, |y| <= 170 with angle error below 4 * 10^{-18}. For the Taylor recurrences in (58) at fixed y, each term-rounding error contributes at most e^{14}/S to the final sum: subsequent factorial denominators bound the amplification by sum_{j>=0} 170^j/(2j)! < e^{14}. Replacing x^2 by y costs at most 100 e^{14}/S. The omitted Taylor tails at |x| <= 13 are below 10^{-30}. Together these give errors below 10^{-20} relative to the computed angle and below 10^{-16} relative to the true cosine and sine. Every single or paired finite factor therefore has error below 10^{-15}. The true factors have modulus at most one, and their approximations at most 1 + 10^{-15}. Telescoping the product of the at most R+K+H = 5100 finite factors, with initial value of modulus at most 2, contributes less than 3 * 10^{-11}.
Terms omitted at the two ends. On the negative side, |C_0(m)| <= 32 (0.994)^{-1-m} for m < 0, obtained by summing the contracting-root terms. Including the three shifts of the type-1 sequence, a coefficient at m < -R - k is bounded by 200 (0.994)^{-4-(m+k)}. Using 1 - cos u <= u^2/2 and telescoping products, the total omitted product is at most
(3.142^2 * 200^2/2) * (0.994)^{5994}/(1 - 0.994^2) < 5 * 10^{-8}. (66)
The rational inequality (0.994)^{2996} < 3 * 10^{-8} already suffices for this estimate. On the positive side, the only coefficients omitted are those from beta: their base is less than 0.545, and the type-0 and type-1 coefficients have modulus at most 4. The cosine Lipschitz bound gives total error 3.142 * 8 * (0.545)^{100}/(1 - 0.545) < 10^{-20}.
The geometric tail and its rounding. Let w_* = u_A in the single case and w_* = u_A + sigma u_B a^k in the paired case, and put U_* = w_* a^H. The exact sums of the even powers of the weak-root tail are
mu_d = sum_{n>=0} (U_* a^n + conjugate(U_* a^n))^d = sum_{j=0}^d binomial(d,j) Re( U_*^j conjugate(U_*)^{d-j}/(1 - a^j conjugate(a)^{d-j}) ) (67)
for d = 2, 4, 6. This follows by the binomial theorem and absolutely convergent geometric series; in particular mu_d >= 0. The power-array errors satisfy |a'_n - a^n| <= 3n/S. Since |a|, |a'| > 0.99, (60) gives errors below 5 * 10^{-21} for both u'_A and |u_A| <= 0.00871. The computed U therefore has error below 10^{-19} and its powers through degree 6 have errors below 10^{-18}. In every quotient in (61), the numerator error is below 3 * 10^{-18} and the denominator error below 10^{-28}. True and computed denominators have modulus above 0.00019: use |1 - a^j conjugate(a)^{d-j}| >= 1 - |a|^d > 1 - 0.9999^2 > 0.00019 and the stated rounding error. Each quotient error is below 2 * 10^{-14}, the error in each computed mu_d below 2 * 10^{-12}, and |mu_d| < 4 * 10^5 by the same denominator bound. The rounded powers of pi' through degree 6 have errors below 10^{-22}. Consequently pen approximates the nonnegative number
P = pi^2 mu_2/2 + pi^4 mu_4/12 + pi^6 mu_6/45 (68)
to within 10^{-9}. For m >= H, the weak coefficient has angle bounded by 3.142 * 4 * 0.00871 * (0.9999)^m < 0.11 * (0.9999)^m. Summing powers gives
P <= 0.11^2/(2 (1 - 0.9999^2)) + 0.11^4/(12 (1 - 0.9999^4)) + 0.11^6/(45 (1 - 0.9999^6)) < 31. (69)
Thus |pen| < 32 and |x| < 1.1 in the exponential calculation. The 40-term exponential recurrence in (61) has Taylor remainder below 10^{-40}; its rounding errors, bounded using e^{1.1}, are negligible compared with 10^{-9}. Each squaring amplifies the existing error by at most 3, since the true intermediate values for the computed penalty are at most e^{10^{-9}}. Including the error in (68), the returned exponential is within 4 * 10^{-9} of e^{-P}.
The analytic remainder of the tail. For real z with |z| <= 0.11,
| -log cos z - z^2/2 - z^4/12 - z^6/45 | <= 0.1 z^8. (70)
To prove (70): set y = z^2, h = 1 - cos z, h_0 = y/2 - y^2/24 + y^3/720. Then 0 <= h <= y/2 and |h - h_0| <= y^4/40320. In -log(1 - h) = h + h^2/2 + h^3/3 + ..., the terms after the third are bounded by h^4/(4(1-h)) < 0.016 y^4. Substituting h_0 in the first three terms costs less than 0.00004 y^4. The terms through degree 3 are y/2 + y^2/12 + y^3/45, and the sum of the absolute values of the remaining coefficients is below 0.03, so their contribution is below 0.03 y^4 for 0 <= y <= 0.0121.
Applying (70) to every weak tail angle gives
| sum_{m>=H} -log cos( pi(w_* a^m + conjugate(w_* a^m)) ) - P | <= 0.1 (0.11)^8/(1 - 0.9999^8) < 3 * 10^{-6}. (71)
Both penalties are nonnegative, so the same bound applies to the difference of their exponentials. Combining this with the rounding error, the finite-factor error, and the two omitted ends proves (63); the sum of the stated errors is below 3.055 * 10^{-6}.
Correlation, variance, and the absolute Gram sum. Abbreviate Z_i = Zhat_i^{(0)} and G_i = Ghat_i, all expectations under the two-sided stationary bit law. Write X = -0.001, Y = 0.0055, and let cal-R be the set of nonzero rows (w_{ks}, k, s) with 30 <= k <= 2000. Put b_A = Ptilde_A, m_{k0} = Ptilde_{00}^+(k), m_{k1} = Ptilde_{00}^-(k), e = Ptilde_{01}^+(33). The approximated correlation is
ctilde = X b_0 + Y e + sum_{(w,k,s) in cal-R} w m_{ks}. (72)
For each lag k, let J_{k0} and J_{k1} be the second (minus) and first (plus) entries of
( Ptilde_{10}^+(k - 33), Ptilde_{10}^-(k - 33) ) if k >= 33,
( Ptilde_{01}^+(33 - k), Ptilde_{01}^-(33 - k) ) if k < 33.
The approximated squared norm and absolute Gram sum are
vtilde = X^2 + Y^2 + 2 X Y b_1 + 2 sum_{(w,k,s) in cal-R} w (X b_0 + Y J_{ks})
+ sum_{(w,k,s),(v,l,t) in cal-R} w v m_{|k-l|, 1_{s=t}}. (73)
Ttilde = sum_{(w,k,s),(v,l,t) in cal-R, k >= 50, l >= 50} |w v m_{|k-l|, 1_{s=t}}|. (74)
The double sums are over ordered pairs. Equal signs require the minus moment in a conjugated phase pair; opposite signs require the plus moment. This explains the index 1_{s=t}, including the diagonal cases.
Exact rational sums give
#cal-R = 753,
|X| + |Y| + sum_{cal-R} |w| = 198442946/W,
|X| + |Y| + sum_{cal-R, k < 50} |w| = 11816095/W,
W S ctilde = 211815537786494774284357596751188225,
W^2 S vtilde = 143920884250294630908494564120361905955993456,
W^2 S Ttilde = 105303788239450118397416374596041413014338334. (75)
These are integer equalities: compute the arrays and products in the coefficient-array step, round the weights by (62), and use the unrounded rational sums (72)-(74). In particular
211810 < 10^9 ctilde < 211820, 143910 < 10^9 vtilde < 143930, 105300 < 10^9 Ttilde < 105310. (76)
This gives |G_i| < 0.199 and |G_i^{(N)}(x)| < 0.199 by the triangle inequality. The total correlation error is at most Delta * 0.199, and the squared-norm error at most Delta * 0.199^2. Thus
E Re(Z_i G_i) > 0.0002108205 > 0.000210, E|G_i|^2 < 0.000144119 < 0.000145. (77)
Small rows. Call the constant row, the type-1 row, and the rows with k < 50 the small rows; the remaining rows are the big rows. A row of weight w_v has phase U_v = exp(pi i sum_m f_v(m) e_m) with e_m = 2 b_{i+m} - 1; its sequence f_v is zero for the constant row, C_1(m + 33) for the type-1 row, and (1 - 2s) C_0(m + k) for a row (w, k, s). Define the true absolute Gram sum
T = sum_{v, v' big} |w_v w_{v'} E U_v conjugate(U_{v'})|. (78)
The error between this sum and (74) is at most Delta * 0.199^2, by ||x| - |y|| <= |x - y|. Hence
T < 0.000116, sqrt T < 0.011. (79)
The total absolute weight of the small rows is below 0.012.
Finite products controlling the remaining moment. The last estimate of Proposition 15 is E(Z_i^2 G_i^2) with |.| < 0.000007. The big rows have small coefficients on the 71 positions -70 <= m <= 0. With t = 0.06, (64) and (65) give
|tan(pi f_v(m))| <= t for v big, -70 <= m <= 0. (80)
Indeed m + k >= -20 for these rows, and the coefficient bound 0.018 together with sin u <= u and cos u >= 1 - u^2/2 is sufficient.
For a real sequence V write c_m = |cos(pi V(m))| and s_m = |sin(pi V(m))|. Let
B_2(V) = prod_{m=-70}^0 min(1, ((1 + t^2) c_m + 2 t s_m)/(1 - t^2)),
B_1(V) = prod_{m=-70}^0 min(1, (c_m + t s_m)/sqrt(1 - t^2)),
B_0(V) = prod_{m=-200}^0 c_m. (81)
Their certified bounds are
B_2(2 C_0) < 0.011, max_{f small} B_1(2 C_0 + f) < 0.015, max_{f, g small} B_0(2 C_0 + f + g) < 0.0032. (82)
The maxima range over the phase sequences of the small rows. Besides the constant row and the type-1 row, the eight nonzero small rows are:
k: 32 36 37 39 40 43 44 47
s: 0 1 0 1 0 0 1 1
Ww: -536932 1265024 331701 47119 1483338 436861 458216 756904 (83)
An upper-rounding calculation verifying (82). For each of the three cases and each indicated choice of small rows, form the approximating sequence V' by replacing C_A with c_A. Initialise v = 1. For increasing m in the relevant interval compute
b = |g(V'(m))| + 10^{-15}, y = |h(V'(m))| + 10^{-15},
F_0 = b,
F_1 = S^{-1} + [1.002 (b + 0.06 y)],
F_2 = S^{-1} + [1.004 (1.0036 b + 0.12 y)],
v <- S^{-1} + [v min(1, F_j)] in case j. (84)
The factors 1.002 and 1.004 bound (1 - t^2)^{-1/2} and (1 - t^2)^{-1}; the added 10^{-15} exceeds the trigonometric error already bounded, and each added S^{-1} compensates for a possibly downward rounding. Thus the calculation gives upper bounds in every case, including B_0 because its true factors are at most one. The maximum final numerators at scale S, in the order B_2, B_1, B_0, are
10861284406435197401851134503,
14731866010915969694738277129,
3155364376927094122833206055. (85)
Scaling them gives the bounds (82).
Walsh expansion. Write G_i = G_small + G_big according to the small/big partition, and fix a subset J subset {-70,...,0}. Expanding the big phases in the independent signs e_m on J gives
G_big = sum_{A subset J} i^{|A|} e_A H_A, e_A = prod_{m in A} e_m, (86)
where
H_A = sum_{v big} w_v U_v^{out} prod_{m in J} cos(pi f_v(m)) prod_{m in A} tan(pi f_v(m)). (87)
The phase U_v^{out} depends only on signs outside J, so each H_A is independent of the signs on J.
Claim:
||H_A||_2 <= sqrt T * t^{|A|} * (1 - t^2)^{-|J|/2}. (88)
For two big rows, independence gives their full Gram entry as the outside Gram entry times
prod_{m in J} cos(pi f_v(m)) cos(pi f_{v'}(m)) (1 + tan(pi f_v(m)) tan(pi f_{v'}(m))). (89)
By (80), each last factor is at least 1 - t^2. In the expansion of ||H_A||_2^2 the extra tangent products have modulus at most t^{2|A|}. Taking absolute values term by term bounds the squared norm by T t^{2|A|} (1 - t^2)^{-|J|}, proving (88).
First consider E(Z_i^2 G_big^2) and set V = 2 C_0. For a pair A, A' subset J in (86), averaging the signs on J contributes a factor of modulus c_m where membership in A and A' agrees and of modulus s_m where it differs. The outside expectation is bounded by ||H_A||_2 * ||H_{A'}||_2, using Cauchy-Schwarz and the unit modulus of the outside part of Z_i^2. Summing over the four membership choices at each site gives
|E(Z_i^2 G_big^2)| <= T prod_{m in J} ((1 + t^2) c_m + 2 t s_m)/(1 - t^2). (90)
Take J to contain precisely those positions whose displayed factor is less than one. This yields
|E(Z_i^2 G_big^2)| <= T B_2(2 C_0). (91)
For a fixed small phase U with sequence f, use the same expansion with V = 2 C_0 + f. There is now a single subset A; summing its two membership choices produces c_m + t s_m. The outside expectation is bounded by ||H_A||_2. Optimising J as before gives
|E(Z_i^2 U G_big)| <= sqrt T * B_1(2 C_0 + f). (92)
For two small phases with sequences f, g, independence directly bounds their full moment by B_0(2 C_0 + f + g): discard the other absolute cosine factors, all of which are at most one.
Summing these bounds with the absolute row weights. Using (79), (82), and the small-weight bound 0.012,
|E(Z_i^2 G_i^2)| <= T * 0.011 + 2 * 0.012 * sqrt T * 0.015 + 0.012^2 * 0.0032
< 0.000116 * 0.011 + 2 * 0.012 * 0.011 * 0.015 + 0.000144 * 0.0032
= 0.0000056968 < 0.000007. (93)
This is the last estimate of Proposition 15. Together with the exact integer bounds (75)-(77) it completes every quantitative input to the proof of Theorem C. Theorems A, B, and C hold.