Arithmetic classification and non-Pisot singularity for Bernoulli convolutions

1 Introduction

For 0<\lambda<1, the unbiased Bernoulli convolution \nu_\lambda is the law of

where the signs are independent. The series converges absolutely. We also use the bit form \mu_\lambda, the law of

The relation Y_\lambda=2X_\lambda-(1-\lambda)^{-1} preserves singularity and absolute continuity. A measure is singular if it gives full mass to a Borel set of Lebesgue measure zero. Bernoulli convolutions have pure type: they are either singular or absolutely continuous [8, Theorem 11]. The classification problem asks which of these alternatives holds for each parameter, including exceptional parameters.

For \lambda<1/2, a direct interval cover proves singularity; at \lambda=1/2, \nu_\lambda is uniform on [-2,2]. The interval (1/2,1) presents the arithmetic difficulty. A Pisot number is a real algebraic integer \beta>1 whose other conjugates have modulus less than one. Erdős proved singularity when \lambda^{-1} is Pisot by showing that the Fourier transform does not tend to zero [3]. Garsia subsequently established absolute continuity for a different arithmetic class, including reciprocals of algebraic integers of absolute norm two whose conjugates all have modulus greater than one [4].

The almost-everywhere theory gives a complementary picture. Solomyak proved that \nu_\lambda has an L^2 density for Lebesgue-almost every \lambda\in(1/2,1) [17]. Hochman’s work relates dimension loss to very strong concentration of cylinder positions [7], and Shmerkin proved that the possible singular parameters in this interval form a set of Hausdorff dimension zero [16]. Varjú proved full dimension for every transcendental parameter in this interval [18]. These conclusions leave measure type at exceptional parameters to be resolved; full dimension alone does not imply absolute continuity. The survey [12] describes the classical development and the roles of arithmetic, overlap, and Fourier decay.

Garsia connected singularity with entropy of finite sums [5]. Algebraic approximation also plays a central role in the dimension theory: Breuillard and Varjú showed that a dimension-deficient parameter can be approximated exceptionally closely by algebraic parameters whose Bernoulli convolutions also have dimension less than one [2, Theorem 1]. The criterion below addresses measure type and also records the number and coefficient directions of nearby algebraic targets.

A Salem number is a real algebraic integer \beta>1 whose other conjugates consist of \beta^{-1} and conjugates on the unit circle. In degree four there is a single nonreal conjugate pair. Salem proved that the Fourier transform of \nu_\lambda tends to zero whenever \lambda^{-1} is not Pisot [14]. Thus Fourier nondecay cannot prove singularity for Salem parameters. Marshall-Maldonado and Solomyak recently obtained quantitative decay estimates for these convolutions [11, Appendix B]; those estimates do not decide absolute continuity. The existence of singular examples with non-Pisot reciprocal is explicitly recorded as open in the recent literature [1, 9].

This paper gives an arithmetic criterion for every parameter and proves two classes of non-Pisot singularity results. The criterion in Theorem 2.1 uses finite sets of real algebraic units. Their minimal polynomials have coefficients in \{-1,0,1\}, prescribed degree, and irreducible reduction modulo two. A target unit is retained when nearby units supply sufficiently many distinct initial coefficient vectors in a fixed positive proportion of the coordinate orthants. Singularity is equivalent to one-sided approximation by these retained targets at a fixed geometric rate. All target sets are defined by finite polynomial algebra; their construction uses no information about the type of any Bernoulli convolution. The resulting classification is an approximation property, and need not provide a short test for membership at a given real parameter.

The main step behind the criterion is a realization lemma. Concentration of the measure produces many pairs of finite bit words with nearby sums and different first bits. Their difference vectors can be completed to height-one polynomials having a root strictly above the parameter. A uniform finite-order nonvanishing estimate preserves a sign change, while prime polynomials in arithmetic progressions over \mathbb F_2 supply irreducibility without altering the initial coefficients. This separates the concentration argument from the algebraic realization, and gives a way to translate overlap information into constrained algebraic approximation.

The two non-Pisot results are proved directly; the criterion then yields the corresponding approximation properties. Theorem 5.1 proves singularity for the reciprocal of every quartic Salem number in (1,2). We construct algebraic multipliers whose unit-circle conjugates become small faster than the associated cosine losses accumulate. Trace identities then localize many Fourier phases to disjoint windows of random signs. Their averages concentrate under the Bernoulli convolution while tending to zero in Lebesgue mean square. This yields singularity even though the Fourier transform tends to zero. The construction applies in particular to the two quartic polynomials specified in Corollary 5.4.

Theorem 6.1 treats a root of an explicit degree-31 polynomial with a complex-conjugate pair outside the unit circle. Here word evaluations lie in a lattice whose box volume grows slightly faster than the reciprocal parameter to the word length. A product of positive trigonometric factors has bounded Lebesgue integral but grows exponentially on typical word evaluations. The resulting saving outweighs the extra volume growth. A finite-state description of nearly cancelling frequencies controls the integral; an explicit rational calculation verifies the required moment inequalities. Appendix A provides the root enclosures, finite recurrences, and analytic error bounds for that calculation.

Sections 2–4 prove the classification and recover the basic Pisot and Garsia cases. Sections 5 and 6 establish the two non-Pisot results. All logarithms are natural unless a base is specified, and all decimal constants used in estimates denote exact rational numbers.

2 An arithmetic criterion for the measure type

The criterion in this section is expressed through finite sets of algebraic units and the coefficient vectors of their minimal polynomials. Its proof has two parts. A sufficiently large cluster of coefficient vectors forces concentration of the Bernoulli convolution. Conversely, concentration produces many short polynomial prefixes, each of which can be completed to an irreducible polynomial with a root just above the parameter.

For integers n\geq 1 and d\geq 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 is irreducible modulo 2. An algebraic unit here means an algebraic integer with algebraic-integer inverse. Write p_r for the minimal polynomial with its sign chosen so that its constant coefficient is -1, and set

For r\in R(n,d), define the finite set

This is a set of vectors: repeated projections, including those arising from conjugate roots of one polynomial, are counted only once.

For a bit word u=(u_0,\ldots,u_{n-1})\in\{0,1\}^n, let

be the associated closed orthant. A vector with a zero coordinate belongs to both choices of sign in that coordinate. For j\geq1, put

All comparisons in this definition involve algebraic numbers and finite sets. In particular, R(n,d) and R_*(n,d,j) can be obtained by finite enumeration of integer polynomials and exact algebraic comparisons.

Thus the degree multiplier d may be fixed before the crowding level j is chosen. For a singular parameter in (1/2,1), each level j is attained at every sufficiently large n, with the threshold in n allowed to depend on j. The predicate uses only polynomial arithmetic, one-sided approximation, and counts of coefficient vectors. Determining membership for a particular parameter can nevertheless be difficult; the theorem does not supply a finite decision procedure for arbitrary real inputs.

2.1 Measure-theoretic preliminaries

We use the bit form

with law \mu_\lambda, and write L=(1-\lambda)^{-1}. The affine identity Y_\lambda=2X_\lambda-L shows that \mu_\lambda and \nu_\lambda have the same measure type. For a word u\in\{0,1\}^n, put

Conditioned on this prefix, X_\lambda lies in s_u(\lambda)+\lambda^n[0,L].

We shall also use the following elementary formulation of concentration. It isolates the measure-theoretic input needed to establish membership in (2.3).

2.2 Algebraic clusters imply singularity

Suppose \lambda\in(1/2,1) satisfies the condition in (2.3), and fix a degree multiplier d witnessing it. For each j, there are arbitrarily large n and r\in R_*(n,d,j) such that

If w\in W_n(r;d), choose a polynomial p_q giving this projection. Its root q satisfies |q-\lambda|\leq2\cdot4^{-n}. On any fixed compact subinterval of (0,1) containing \lambda in its interior,

The coefficients of index at least n contribute at most L\lambda^n at \lambda. Thus there is a constant B=B(\lambda), independent of n,d,j,w, such that for all sufficiently large n,

Here we used 4^{-n}=o(\lambda^n).

If w\in\mathcal O_u\cap\{-1,0,1\}^n, then v=u-w belongs to \{0,1\}^n. Different w give different v. By (2.2), at least 2^n/d words u consequently have at least j(2r)^n\geq j(2\lambda)^n neighbors v satisfying

Partition the line into half-open bins of length \lambda^n, and let \mathcal I be the bins containing at least one of these words u, where a word occupies the bin containing its prefix sum. For each J\in\mathcal I, choose one such word. Its neighbors lie in the B\lambda^n-enlargement of J. Each prefix sum can belong to the enlargements of at most N_B=2\lceil B\rceil+3 bins. Counting word–bin incidences yields

Enlarge each bin J=[a,a+\lambda^n) to [a,a+(1+L)\lambda^n], and denote their union by E_j. The tail bound following (2.4) gives

Absolute continuity of a finite measure makes its mass uniformly small on sets of sufficiently small Lebesgue measure. Therefore (2.6), as j\to\infty, rules out absolute continuity. Lemma 2.2 proves singularity.

3 Constructing the algebraic approximants

We now prove the converse in Theorem 2.1. Throughout this section, \lambda\in(1/2,1) is fixed, and we abbreviate \mu=\mu_\lambda, X=X_\lambda, and s_u=s_u(\lambda). The first step is to turn concentration of \mu into many close prefix sums with opposite first bits. Opposite first bits ensure that their difference polynomial has constant coefficient -1, as required by the algebraic criterion.

3.1 Overlap of the first-bit measures

Define subprobability measures

Their sum is \mu. The following fact uses only \lambda>1/2, not singularity.

3.2 Completion to irreducible polynomials

For every pair in Proposition 3.2, the difference w=u-v has w_0=-1 and |\sum_{i<n}w_i\lambda^i|\leq(L-a)\lambda^n. We next extend any such coefficient vector to a polynomial whose root lies in (\lambda,\lambda+4^{-n}/2]. The first lemma ensures that a bounded-coefficient polynomial cannot remain too flat throughout this short interval.

To impose irreducibility without disturbing the prescribed coefficients, we use the prime-polynomial theorem in arithmetic progressions. We include the deduction needed here from the function-field Riemann hypothesis; its character-sum formulation is recalled in [6, Theorem 3.2 and Lemma 3.3].

3.3 Proof of the converse and the quantifiers

Suppose \mu_\lambda is singular. Proposition 3.2 gives constants a,c>0. Choose one integer d large enough for Proposition 3.5 and also satisfying 1/d<c. This choice depends on \lambda alone.

Fix any integer j\geq1 and choose Q>2j. For all sufficiently large n, each of at least c2^n words u has at least Q(2\lambda)^n neighbors v supplied by Proposition 3.2. For each difference w=u-v, Proposition 3.5 supplies a root r_w\in R(n,d) with signed minimal polynomial projecting to w, and

Choose any one of these roots as a center r. All of them lie within 4^{-n} of r, so all their projected vectors belong to W_n(r;d). For fixed u, its different neighbors give distinct vectors u-v, each in \mathcal O_u. Furthermore,

uniformly in the choice of center. Hence, for all sufficiently large n, each of these c2^n orthants contains at least j(2r)^n distinct vectors of W_n(r;d). Since c>1/d, we have r\in R_*(n,d,j) and \lambda\in[r-4^{-n},r).

We have proved that a single d works for every j, at every sufficiently large n. This proves membership in the expression (2.3) with \liminf. Membership in that expression implies membership with \limsup, which implies singularity by Section 2.2. Lemma 2.2 handles \lambda\leq1/2 and supplies the absolute continuity of every remaining parameter. This completes the proof of Theorem 2.1.

4 Recovery of classical parameter classes

The arithmetic criterion is compatible with the classical norm separation argument for Garsia parameters and the Fourier argument for Pisot parameters. The first example directly bounds the crowding in (2.2); the second establishes singularity and then uses Theorem 2.1 to obtain the approximation property.

5 Degree-four Salem parameters

For a degree-four Salem number \beta, the two conjugates on the unit circle form a single complex-conjugate pair. We use simultaneous control of this pair to construct many Fourier phases with appreciable expectation. After removing integer trace terms, widely separated phases depend, up to a small error, on disjoint blocks of the Bernoulli signs. Their averages therefore distinguish the Bernoulli convolution from Lebesgue measure.

The proof has two quantitative requirements. The Fourier products must lose little mass before the algebraic trace becomes an accurate integer approximation; the remaining trace errors must then stay small over many disjoint blocks. The multiplier construction below supplies both requirements. The trace approximation is the familiar arithmetic ingredient in the Fourier analysis of Pisot and Salem parameters [3]; see in particular Salem’s small-conjugate construction [15, Chapter III, Section 3, Theorem III, pp. 28–29]. The estimates here also control the losses accumulated while the multiplier changes.

5.1 Multipliers with small unit-circle conjugates

Fix \beta as in Theorem 5.1, and write its conjugates as \beta^{-1},z,\bar z, where z=e^{i\theta}. The number \beta is a unit: the product of its four conjugates is 1. Moreover, \theta/\pi is irrational, since otherwise z, and hence its conjugate \beta, would be a root of unity.

For positive integers k_1,k_2,\ldots, to be chosen, define

Here and throughout this section logarithms are natural. Irrationality ensures \delta_m>0, and 0<A_m\le\beta^{b_m}. For j\in\Z, put u_{m,j}=A_m\beta^j. All these numbers are algebraic integers, because \beta is a unit. Their field traces are the integers

Indeed, the embedding taking \beta to \beta^{-1} takes A_m to (-1)^mA_m. Also u_{m,j}\notin\Z+\tfrac12, since a rational algebraic integer is an integer. Thus none of the cosine factors used below vanishes.

The construction below balances the decrease of \delta_m against the cosine losses generated by A_m. Eventually L_m grows by a factor greater than two while k_{m+1}\delta_m^2 tends to zero; these are the margins used in the loss estimate below. It also keeps b_m small compared with \delta_m^{-1}, leaving room for many separated blocks of signs. A uniform lower bound on the cosines will permit a quadratic estimate for perturbations of their logarithms.

5.2 The loss in the cosine products

Fix the sequence furnished by Lemma 5.2. Constants denoted by C below may change from line to line, but are independent of m and of the phase index. Define

Each S_m is finite: its terms have a geometrically decaying tail because u_{m,j}\to0 as j\to-\infty and f(u)=O(u^2) near zero. The next estimate controls the entire negative-power contribution even though A_m becomes large.

5.3 Independent blocks of Fourier phases

We now turn the product estimates into sets of almost full \nu_{1/\beta}-measure and vanishing Lebesgue measure. The comparison of phase averages under two measures is analogous to the separation argument for Riesz products in [13, Section 1.1, Theorem 1.2]. Here the needed estimates follow from the independent signs, as we now show. Work on the probability space of independent uniform signs (\epsilon_\ell)_{\ell\ge0}, and write

The law of Y is \nu_{1/\beta}, supported on I=[-(1-\beta^{-1})^{-1},(1-\beta^{-1})^{-1}]. Independence, followed by passage to the limit in the convergent sign series, gives

This is a nonzero real number; the negative-index tail has a convergent sum of logarithmic losses.

Set

and let M_m=|\mathcal N_m|. All subsequent estimates concern sufficiently large m. Since H_m\le K_m\le e^{.75L_m},

Lemma 5.3 and J_m\delta_m^2\le e^{-.5L_m} show that

For n\in\mathcal N_m, retain only the signs whose indices lie in [n-H_m,n+H_m], and define

The integer sum in the prefactor is empty when n=H_m. To explain this approximation, expand the exponent of W_{m,n} as \pi\sum_{j\le 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 is deterministic because e^{i\pi T_{m,j}\epsilon_{n-j}}=(-1)^{T_{m,j}}. For j<-H_m, drop the term. The remaining indices are exactly those in (5.17).

The difference of the two phase angles, after these replacements, is a sum of independent mean-zero signs. The inequality |e^{ix}-e^{iy}|\le|x-y| therefore gives

Here (5.2) bounds the first summand by a geometric tail and a contribution C n\delta_m^2; the other sum is itself a geometric tail. Finally, D\log\beta=10 and n\le J_m give the last inequality. All norms in (5.18) refer to the sign probability space. The windows belonging to consecutive members of \mathcal N_m are disjoint, so the variables \widetilde W_{m,n} are independent.

5.4 Two explicit parameters

6 A polynomial with a weakly expanding conjugate pair

The final example uses a polynomial with one conjugate pair just outside the unit circle. We will prove singularity directly by counting typical prefixes. Counting all polynomial values in their conjugate coordinates therefore gives slightly too many possible prefixes. We obtain the required improvement by a product of positive trigonometric factors: its integral in the expanding coordinates stays bounded, whereas it grows exponentially on a set of words whose probability tends to one.

Throughout this section, every terminating decimal denotes the corresponding exact rational number. Put

The identity

will control the near-cancellations in the trigonometric product.

We first record the root bounds needed in the proof. The proposition is proved by rational root disks in Section A.1.

Write D=\{\beta,\alpha,\overline\alpha\} and let I be the set of remaining roots. The expanding volume factor is

The last inequality uses \log(1+u)<u for u>0.

The root bounds already show that \beta is not Pisot. Indeed, suppose \beta were Pisot, and divide p by its monic minimal polynomial. The quotient is monic and integral, has constant term of absolute value one, and contains \alpha,\overline\alpha among its roots but not \beta. The product of the moduli of its roots is greater than one if it has no roots in I, and otherwise is at most 1.0002094\cdot0.994<1. Both conclusions contradict the constant term. It remains to prove singularity.

6.1 Word vectors and characters

For a word a=(a_0,\ldots,a_{N-1})\in\{0,1\}^N, define

Vectors indexed by roots are always constrained by y_{\overline r}=\overline{y_r}, and a conjugate pair counts as one complex coordinate, or two real coordinates. In particular, the space of all y-vectors has real dimension 31.

To distinguish the word vectors from typical points of these boxes, define the real sequences

Partial fractions give

Thus C_0 is the bilateral Laurent coefficient sequence of 1/p, and both C_0,C_1 decay exponentially at both ends. The same inversion by an exponentially decaying two-sided sequence is used by Lind and Schmidt [10, Lemma 4.5 and Example 4.7] to construct homoclinic points for algebraic actions. Here the explicit root formula will give characters adapted to the word vectors.

For arbitrary expanding coordinates x_D, with x_\beta\in\R and x_{\overline\alpha}=\overline{x_\alpha}, put

These functions have modulus one.

The corresponding stationary model uses independent fair bits (b_k)_{k\in\Z} and the unit random variables

The series converges absolutely. Independence gives the real moments

6.2 A predictor with a positive mean gain

The weakly expanding pair produces long decaying tails in C_0. Some shifted tails nearly cancel in the signed products P_{00}^{\pm}(k). A linear combination of the corresponding phases will use these correlations. For rational weights w_{ks}, define

We fix weights supplied by Proposition 6.5. Their exact rational construction is given in Section A.2, and the moment bounds are proved in Section A.4.

The next two subsections construct a positive product whose logarithm has a positive mean under this stationary model and whose integral is bounded in the expanding coordinates. These two estimates will remove an exponential proportion of the lattice points allowed by Lemma 6.3.

6.3 Damping the possible frequency cancellations

Choose a fixed integer i_0\ge1 so that

For a word length N, use every complete block

and write J_N for their union. Thus each block has 21 indices and consecutive blocks are separated by one unused index.

The near-relation (6.2) dictates which signed digit patterns need to be retained when integrating a block. For a pattern (d_i)_{i\in B_q}\in\{-1,0,1\}^{B_q}, let b=\max B_q and set

Reading from the largest index downwards gives v_i=\beta v_{i+1}+d_i. At the root \beta, (6.2) becomes

In particular, the four digits [\sigma,-\sigma,-\sigma,-\sigma] leave the small normalized remainder \sigma\beta^{-30}. We encode these approximate returns by the transitions in Figure 1. The initial state is 0, and the permitted terminal states are 0,C_+,C_-. For each sign \sigma\in\{-1,1\}, the numerical values assigned to the states are

A pattern is called admissible if every transition is allowed and its terminal state is permitted.

Let o(d)=\#\{i:d_i\ne0\}. At a position i of a block, define

The same coefficients are repeated in every block. An admissible nonzero pattern has at least three nonzero digits, so all summands are well defined.

For the moment fix N, and abbreviate Z_i=Z_i^{(0,N)}, G_i=G_i^{(N)}, and x_i=|G_i|. Define

These factors are bounded above and bounded away from zero uniformly in N,i,x_D. Indeed, h_i\ge1-S_*/3, and the other factor is at least 1-2x_*>0.

6.4 A typical exponential gain

We now evaluate the same factors in the stationary model, replacing Z_i,G_i in (6.20) by \mathcal Z_i^{(0)},\mathcal G_i; denote the resulting factors by \mathcal F_i. The damping coefficients remain periodic with period 22, and are used at the same 21 positions per period.

6.5 Counting typical vectors and proving singularity

The integral bound applies to continuous coordinates, whereas Proposition 6.9 concerns lattice points. The remaining step is to thicken each such point by a fixed radius. Normalization in the expanding directions makes the resulting change in the whole logarithmic product bounded independently of the word length.

A A rational certificate for the degree-31 example

This appendix proves the root bounds in Proposition 6.2 and the predictor estimates in Proposition 6.5. The root calculation uses exact rational arithmetic. The moment calculation combines finite rational products with an analytic estimate for their infinite tails. We specify the rounding and the order of operations so that the rational weights in (A.7) are completely determined. The accompanying script verification/verify_degree31.py implements these instructions using only Python integers and rational fractions; the recurrences below give the complete certificate independently of that implementation. Every terminating decimal in this appendix denotes its exact rational value.

A.1 Locating all the roots

Recall the polynomial

Put E=10^{40}. The entries in Table 1 are the real and imaginary numerators of centers z=(a+\mathrm i b)/E. Include the conjugate of each nonreal center. Thus the table specifies 31 disks, all of radius \delta=10^{-35}. Denote its first and sixth centers by 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 gives, at every displayed center,

Here is an integer prescription for these comparisons. For q(t)=\sum_{j=0}^d q_jt^j and the Gaussian integer Z=Ez, initialize (V,h)=(q_d,1) and, for j=d-1,d-2,\ldots,0, replace

The final value is q(z)=V/h. Apply this to p and p', and clear the positive denominators in (A.1). Comparisons of squared distances give |z-z'|>.01 for distinct centers, including conjugates. Comparisons of coordinates and squared moduli also give

For |h|=\delta, the terms of degree at least two in p(z+h)-p(z)-p'(z)h have total modulus at most

Indeed, |z|<2 and \delta<1, so the binomial expansion gives this bound term by term. By (A.1), the constant term is less than |p'(z)|\delta/2, whereas the displayed remainder is less than |p'(z)|\delta/2. Rouché’s theorem therefore puts exactly one root, counted with multiplicity, in each disk. The disks are disjoint and their number is the degree, so these are all the roots and all are simple. 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 10^{-35} and (A.2) imply every bound in Proposition 6.2, including |1/\alpha|<.9999.

A.2 Rounded coefficient arrays and finite products

The numerical inputs are the sequences C_0,C_1 defined in the main text in (6.6). We approximate their single and paired moments

where A,B\in\{0,1\}, \sigma\in\{1,-1\}, and k\ge0. Both products converge by exponential decay of the coefficients. The sign notation + and - means \sigma=1 and \sigma=-1.

We now specify the approximations used to define the weights. Use

For a real rational x set

and round complex numbers componentwise. Thus, if x=u/v with integers u,v and v>0, its rounded numerator is \lfloor(2Su+v)/(2v)\rfloor. Additions, subtractions, conjugation, and multiplication by an integer are exact unless brackets are explicitly displayed. Set

The inequality |\pi'-\pi|<1/S follows by using 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

In particular this verification, too, uses rational arithmetic only.

The contracting and expanding roots are denoted by I and D, as in the main text. For each representative center z first form r_z=[1/p'(z)], with p'(z) evaluated exactly. Store a base and a coefficient as follows:

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),\ldots, replacing v\leftarrow[va_z] after each addition. For an expanding representative do the same on c_0(0),c_0(1),\ldots; the multiplier is 1 for the real root and 2 for the nonreal representative. All arrays start at zero. Compute c_0(m) on

and define, wherever these three entries are present,

These extra endpoint entries ensure that every subsequent use of c_1 lies in its defined range. The arrays approximate the sequences C_0,C_1 in the main text.

For a rational input c let g(c),h(c) be the following rounded cosine and sine values. The displayed loop fixes the order of the summation.

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)

Write g_A(m)=g(c_A(m)) and h_A(m)=h(c_A(m)).

The only expanding root close to the unit circle is \alpha and its conjugate. To treat their long tail, set

Their contribution to C_A(m) for m\ge H is u_Aa^m+\overline{u_Aa^m}. Let (a',u'_0) be the pair in (A.4) belonging to z_\alpha. Compute

The subscript in a'_n is a power-array index.

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\le k\le K, use w=u'_A+\sigma[u'_Ba'_k]. In either case the following calculation returns an approximate moment. It retains the finite factors -R-k\le m<H, omits the rapidly convergent negative tail, and treats the positive tail by summing the degree-2, 4, and 6 terms of -\log\cos through geometric series. Their sum is the variable pen; the divisors 2,12,45 are the corresponding Taylor denominators. To compute e^{-\texttt{pen}}, the algorithm first approximates e^{-\texttt{pen}/32} and then squares five times. This tail value is computed first, and the finite factors are then multiplied in increasing order of m. Section A.3 bounds all omissions and rounding errors.

U = [w*a'_H]
q_0 = 1;  q_i = [q_{i-1}*U]       for i = 1,...,6
b_0 = 1;  b_i = [b_{i-1}*pi']     for i = 1,...,6
pen = 0
for d = 2,4,6:
    mom = 0
    for j = 0,...,d:
        num = [q_j*conj(q_{d-j})]
        den = 1-[a'_j*conj(a'_{d-j})]
        mom = mom+binomial(d,j)*Re([num/den])
    pen = pen+[b_d*mom/f_d]       (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)                               (single)
    v = [g_A(m)*g_B(m+k)-sigma*h_A(m)*h_B(m+k)] (pair)
    value = [value*v]
return value

Denote the outputs by \widetilde P_A and \widetilde P_{AB}^{\sigma}(k), respectively.

We use only lags 30\le k\le2000. With s=0 for \sigma=1 and s=1 for \sigma=-1, put r=\widetilde P_{00}^{\sigma}(k) and set

Take \operatorname{sgn}(0)=0 and omit zero weights from subsequent sums. The recurrences above and this formula define the weights without any choices or numerical tolerances.

A.3 A uniform error bound for the moment calculation

We prove

for all types, signs, and lags used above. The important issue is the weakly contracting base a=1/\alpha: truncating its powers at H=100 would not be accurate. The geometric sums in the tail calculation retain all of these powers.

Coefficient and trigonometric errors. For |z|<2.001, termwise differentiation gives

Hence p' changes by less than 4\cdot10^{-22} between a center and its root. By (A.1), reciprocal differentiation and rounding in (A.4) give base errors less than 2/S and coefficient errors less than 10^{-21}. Direct squared modulus comparisons give |a_z|<1 and |v_z|\le1 for every stored pair. The corresponding exact coefficients have modulus less than 1.001. Thus each recurrence step v\leftarrow[va_z] propagates the existing error with factor at most 1 and adds less than 4/S. There are fewer than 5100 such steps in any needed entry. Each coefficient-times-power term consequently has error less than 2\cdot10^{-21}, and

The finite recurrence also gives the following rational comparisons:

The maxima here range over the computed entries; use squared moduli for the complex coefficients u'_A. To reproduce them, perform the coefficient recurrences in (A.4), the additions in (A.5), and the displayed definition of u'_1. These comparisons require neither evaluation of trigonometric functions nor a root-finding routine.

Every later trigonometric input is a sum of at most four of these coefficients, counted with multiplicity. Its error is less than 10^{-18}, and its rounded angle satisfies |x|\le13 and |y|\le170. The angle error is less than 4\cdot10^{-18}. For the Taylor recurrences at a fixed value of y, each term-rounding error contributes at most e^{14}/S to the final sum: the subsequent factorial denominators bound the amplification by \sum_{j\ge0}170^j/(2j)!<e^{14}. Replacing x^2 by y costs at most 100e^{14}/S, by differentiating the absolute term sums. The omitted Taylor tails at |x|\le13 are less than 10^{-30}. Together these effects give errors below 10^{-20} relative to the computed angle, and below 10^{-16} relative to the true cosine and sine. In particular every single or paired finite factor has error less than 10^{-15}.

There are at most R+K+H=5100 finite factors. The true factors have modulus at most 1, and their approximations have modulus at most 1+10^{-15}. Telescoping the product, including its roundings, shows that with an initial value of modulus at most 2 these errors contribute less than 3\cdot10^{-11}.

Terms omitted at the two ends. On the negative side, |C_0(m)|\le32(.994)^{-1-m} for m<0, by summing the contracting-root terms. Including the three shifts for type 1, a single or paired coefficient at m<-R-k is bounded by

Using 1-\cos u\le u^2/2 and telescoping products, the total omitted product costs at most

For example, the rational inequality (.994)^{2996}<3\cdot10^{-8} already suffices for this estimate. On the positive side the only terms omitted from the coefficients are those from \beta. Their bases are less than .545, and their type-0 and type-1 coefficients have modulus at most 4. The cosine Lipschitz bound therefore gives a total error at most 3.142\cdot8\cdot(.545)^{100}/(1-.545)<10^{-20}.

The geometric tail and its rounding. Let w_*=u_A in the single case and w_*=u_A+\sigma u_Ba^k in the paired case. Put U_*=w_*a^H. The exact sums of the even powers of the weak-root tail are

The equality follows by the binomial theorem and absolutely convergent geometric series. In particular \mu_d\ge0.

The power-array errors satisfy |a'_n-a^n|\le3n/S. Because |a|,|a'|>.99, the formula for u'_1 gives errors below 5\cdot10^{-21} for both u'_A, and |u_A|\le.00871. It follows that the computed U has error below 10^{-19}; its powers through degree 6 have errors below 10^{-18}. In each quotient in the algorithm, the numerator error is below 3\cdot10^{-18} and the denominator error is below 10^{-28}. The true and computed denominators have modulus greater than .00019: use

and the stated rounding error. Hence each quotient error is below 2\cdot10^{-14}, the error in each computed \mu_d is below 2\cdot10^{-12}, and |\mu_d|<4\cdot10^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

to within 10^{-9}.

For m\ge H, the weak coefficient has angle bounded by

Summing the powers of this bound gives

Thus |\texttt{pen}|<32 and |x|<1.1 in the exponential calculation. The 40-term exponential recurrence has Taylor remainder less than 10^{-40}. Its rounding errors, bounded using e^{1.1}, are negligible compared with 10^{-9}. Each squaring amplifies its 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 (A.12), the returned exponential is within 4\cdot10^{-9} of e^{-P}.

The analytic remainder of the tail. For real z with |z|\le.11 one has

Here are elementary bounds proving the stated constant. Set y=z^2, h=1-\cos z, and h_0=y/2-y^2/24+y^3/720. Then 0\le h\le y/2 and |h-h_0|\le y^4/40320. In -\log(1-h)=h+h^2/2+h^3/3+\cdots, the terms after the third are bounded by h^4/(4(1-h))<.016y^4. Substitution of h_0 in the first three terms costs less than .00004y^4. The terms through degree 3 are y/2+y^2/12+y^3/45; the sum of the absolute values of the remaining coefficients is less than .03, so their contribution is less than .03y^4 for 0\le y\le.0121. These bounds imply (A.13).

Applying (A.13) to all weak tail angles gives

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 (A.8); indeed the sum of the stated errors is below 3.055\cdot10^{-6}.

A.4 Correlation, variance, and the absolute Gram sum

For the rest of the appendix, abbreviate Z_i=\mathcal Z_i^{(0)} and G_i=\mathcal G_i from (6.9) and (6.11). All expectations are under the stationary law of the two-sided independent bits.

The preceding calculation defines exact rational weights and bounds each moment error uniformly. We next sum those moments to prove the first three estimates of Proposition 6.5. A final finite-product estimate will prove the fourth.

Write X=-.001, Y=.0055, and let \mathcal R be the nonzero rows (w_{ks},k,s) with 30\le k\le2000. Define

The approximated correlation is

For each lag k, let J_{k0} and J_{k1} be respectively the second (minus) and first (plus) entries of the following pair:

The approximated squared norm and absolute Gram sum are

Both 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 \mathbf1_{s=t}, including the diagonal cases.

The exact finite calculations give

These are integer equalities: compute the arrays and products in Section A.2, round the weights by (A.7), and use the unrounded rational sums (A.14)–(A.16). In particular

This gives |G_i|<.199 and |G_i^{(N)}(x)|<.199 by the triangle inequality. The total correlation error is at most \Delta\cdot.199, and the squared-norm error is at most \Delta\cdot.199^2. Thus

To prepare for the last estimate, 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\mathrm i\sum_m f_v(m)e_m), where e_m=2b_{i+m}-1. Its sequence f_v is zero for the constant, 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

The error between this sum and (A.16) is at most \Delta\cdot.199^2, by ||x|-|y||\le|x-y|. Hence

The total absolute weight of the small rows is less than .012.

A.5 Finite products controlling the remaining moment

We now bound \mathbb E(Z_i^2G_i^2). The big rows have small coefficients on the 71 positions -70\le m\le0. More precisely, with t=.06, (A.9) and (A.10) give

Indeed m+k\ge-20 for these rows, and the coefficient bound .018, together with \sin u\le u and \cos u\ge1-u^2/2, is sufficient.

For any real sequence V put c_m=|\cos(\pi V(m))| and s_m=|\sin(\pi V(m))|. The finite products needed below are

Their bounds are

Here the maxima range over the actual phase sequences of the small rows. Besides the constant and the type-1 row, their eight nonzero rows are as follows:

For completeness, the following upper-rounding calculation verifies all of (A.22). For each of its three cases and each indicated choice of small rows, form the approximate sequence V' by replacing C_A by c_A. Initialize v=1. For increasing m in the relevant interval, compute

The factors 1.002 and 1.004 bound (1-t^2)^{-1/2} and (1-t^2)^{-1}, respectively. The added 10^{-15} exceeds the trigonometric error proved above, and each added S^{-1} compensates for a possibly downward rounding. Thus this calculation gives upper bounds, including for B_0 because its true factors are at most 1. The maximum final numerators at scale S, in the order B_2,B_1,B_0, are

Multiplication by 10^6/S bounds them respectively by 10862, 14732, and 3156, proving (A.22).

A.6 From the finite products to the anisotropy bound

The estimates just obtained concern individual coefficients and finite products. We finish by showing how they control the full sum of phases without expanding every three-phase moment. Write G_i=G_{\rm small}+G_{\rm big} according to the preceding partition, and fix any subset J\subset\{-70,\ldots,0\}. Expanding the big phases in the independent signs e_m on J gives

where

The phase U_v^{\rm out} depends only on signs outside J, so each H_A is independent of the signs on J.

We claim that

For two big rows, independence gives their full Gram entry as the outside Gram entry times

By (A.20), 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 therefore bounds the squared norm by Tt^{2|A|}(1-t^2)^{-|J|}, proving (A.25).

First consider \mathbb E(Z_i^2G_{\rm big}^2) and set V=2C_0. For a pair A,A'\subset J in (A.24), averaging the signs on J contributes a factor of modulus c_m where membership in A,A' agrees, and a factor 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

Choose J to contain precisely those positions whose displayed factor is less than 1. This yields

For a fixed small phase U with sequence f, use the same expansion with V=2C_0+f. There is now one subset A; summing its two membership choices produces c_m+ts_m. The outside expectation is bounded by \|H_A\|_2. Optimizing J as before gives

For two small phases with sequences f,g, independence directly bounds their full moment by B_0(2C_0+f+g): discard all the other absolute cosine factors, which are at most 1.

Finally sum these bounds with the absolute row weights. Using (A.19), (A.22), and the small-weight bound .012, we obtain

This proves the remaining estimate of Proposition 6.5.