Number of arithmetic progressions in dense random subsets of $\mathbb{Z}/n\mathbb{Z}$
Ross Berkowitz Ashwin Sah Mehtaab Sawhney
math.CO




We examine the behavior of the number of k-term arithmetic progressions in a random subset of ℤ/nℤ.  We prove that if a set is chosen by including each element of ℤ/nℤ independently with constant probability p, then the resulting distribution of k-term arithmetic progressions in that set, while obeying a central limit theorem, does not obey a local central limit theorem. The methods involve decomposing the random variable into homogeneous degree d polynomials with respect to the Walsh/Fourier basis. Proving a suitable multivariate central limit theorem for each component of the expansion gives the desired result.


Momentum-Net: Fast and convergent 
 
iterative neural network for inverse problems

    Il Yong Chun, Member, IEEE, Zhengyu Huang^∗, Hongki Lim^∗, Student Member, IEEE, 
 and Jeffrey A. Fessler, Fellow, IEEE





The authors indicated by asterisks (^∗) contributed equally to this work.
This work is supported in part by the Keck Foundation, NIH U01 EB018753, NIH R01 EB023618, NIH R01 EB022075, and NSF IIS 1838179.
Il Yong Chun was with the Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MI 48019 USA,
and is now with the Department of Electrical Engineering, the University of Hawai'i at Mānoa, Honolulu, HI 96822 USA (email: iychun@hawaii.edu).
Zhengyu Huang, Hongki Lim, and Jeffrey A. Fessler are with the Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MI 48019 USA (email: 
zyhuang@umich.edu; hongki@umich.edu; fessler@umich.edu).
This paper has appendices. The prefix “A” indicate the numbers in section, theorem, equation, figure, table, and footnote in the appendices.
This paper was presented in part at the Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, in Oct. 2018.


    
===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================





§ INTRODUCTION


Understanding the asymptotic behavior of sums of dependent random variables is a fundamental question in probability theory and combinatorics.  One particular random variable that has received attention is the number of arithmetic progressions in a random subset of ℤ/nℤ.  For any subset S⊆ℤ/nℤ we define (S) to count the number of k-term arithmetic progressions contained entirely in the set S. The probability space is constructed by choosing a random set S by including each element of ℤ/nℤ independently at random with probability p∈ (0,1), where p is a fixed constant not depending on n.  The natural question therefore is to understand the distribution of (S) as n grows.


It is not hard to show that (S) obeys a central limit theorem.

That is, if we set μ_n=[(S)] and σ_n^2=((S)), where S is chosen as before, then for any fixed a, b

    [a≤(S)-μ_n/σ_n≤ b]=1/√(2π)∫_a^bexp(-t^2/2)dx+o_n,p(1).


Given this Gaussian macroscopic behavior it is natural to guess that the distribution of  is “smooth” and therefore nearby integers are approximately as likely as one another. In particular, one may conjecture  that a local limit theorem estimating pointwise probabilities of (S) that for any integer x


    [(S)=x]?=1/σ_n√(2π)exp(-(x-μ_n)^2/2σ_n^2)+o(1/σ_n).


However the purpose of this note is to prove that this local limit theorem is in fact false and the distribution of (S) oscillates wildly.


Fix p∈ (0,1) and k≥ 3. Then for all sufficiently large n relatively prime to (k-1)! there is a point x such that 
    |ℙ[(S) = x] - 1/σ_n√(2π)exp(-(x-μ_n)^2/2σ_n^2)| = Ω(1/σ_n),

where μ_n and σ_n in the statement are the expectation and standard deviation of (S) and S is constructed by choosing each element of /n independently at random with probability p.


This failure of the local central limit likely extends to (n,(k-1)!)≠ 1, however the proof details become more technical and therefore we restrict our attention to this case.


The first author discovered this failure of the local central limit theorem by sampling uniformly random subsets of ℤ/101ℤ and counting the number of length 3 arithmetic progressions.  This histogram of results may be found in Figure <ref>.  Interestingly, it should be noted that subsequently and independently a study of Cai, Chen, Heller, and Tsegaye <cit.> also conjectured that such a local limit theorem failed, but did not have a proof.





 §.§ Related Work


Significant attention has been given to understanding the large deviation probability of (S), particularly in the sparse set regime where p→ 0. For example, recently Warnke <cit.>, Bhattacharya, Ganguly, Shao, and Zhao <cit.>, and Harel, Mousset, and Samotij <cit.> found precise upper tail bounds for (S) in the sparse regime, while Janson and Warnke <cit.> proved lower tail bounds. Additionally, Barhoumi-Andréani, Koch, and Liu <cit.> proved a bivariate central limit theorem for (mAP(S), nAP(S)), understanding the joint distribution of the number of length m and n arithmetic progressions in sparse random sets.

Significant attention has also been focused on understanding local limit theorems in the analogous setting of G(n,p). In particular work of Gilmer and Kopparty <cit.> proves a local central theorem for triangle counts, with Berkowitz giving improved bounds in the case of triangles <cit.> and then proving the analogous theorem for cliques in <cit.>. Furthermore for general connected subgraph counts in G(n,p) almost optimal anti-concentration results are known due to the work of Fox, Kwan, and Sauermann <cit.>. Our work points to a certain degree of separation between a local central limit theorem and anti-concentration for polynomial functions of Bernoulli random variables as already suggested by Fox, Kwan, and Sauermann <cit.>. In particular, the random variable (S) experimentally appears to satisfy anti-concentration (at the optimal scale with each point probability being at most O(1/n^3/2)) but as we will prove it does not satisfy a local central limit theorem.



 §.§ Outline of Paper

In <ref> we compute the expansion of the  in the p-biased Fourier basis.  We then use this expansion to give a high level overview of our arguments. Sections <ref>-<ref> contain the main technical work of analyzing the asymptotic behavior of , and a more detailed overview of the argument can be found at the end of <ref>.  The proof of the nonexistence of a local central limit theorem is in <ref>. Finally, we end with some outstanding questions left by our work in <ref>.




§ EXPANSION OF K-AP FUNCTION INTO P-BIASED BASIS AND OUTLINE OF THE ARGUMENT
 
We first expand the counting function of the number of k-APs into a p-biased Fourier basis. In order to do so define x_i to be indicator if the element i is in the subset of /n which we are examining. Then we use the change of variables

    y_i = x_i -p/√(p(1-p))

and note that [y_i] = 0 and [y_i] = 1. Now the k-AP counting function is

    (x)    = ∑_a∈/n∑_d∈ [n/2]∏_i=0^k-1x_a+id
       =∑_a∈/n∑_d∈ [n/2]∏_i=0^k-1(y_a+id√(p(1-p)) + p)
       =∑_a∈/n∑_d∈ [n/2]∑_ℓ=0^k∑_S∈[k]ℓ p^k - |S|∏_i ∈ S (y_a+id√(p(1-p)))
       =∑_ℓ=0^k∑_a∈/n∑_d∈ [n/2]∑_S∈[k]ℓ p^k - |S|/2(1-p)^|S|/2∏_i ∈ S y_a+id.

Furthermore define 

    ^ℓ(y) = ∑_a∈/n∑_d∈ [n/2]∑_S∈[k]ℓ p^k - ℓ/2(1-p)^ℓ/2∏_i ∈ S y_a+id.

The key idea is to note that ^ℓ for ℓ = 1 versus all higher values of ℓ live on different scales. Our main lemma will be to prove a quantitative convergence of these components to k appropriately scaled multivariate Gaussian and then using this analysis we will subsequently prove the desired failure of a local central limit theorem. For the sake of simplicity we also define 

    ^ℓ(y) = 1/σ_ℓ∑_a∈/n∑_d∈ [n/2]∑_S∈[k]ℓ∏_i ∈ S y_a+id

where σ_ℓ is chosen so that [^ℓ(z)] = 1, if z is a vector of independent standard normals. In particular note σ_ℓ is independent of p. Note that these multivariate functions will be the central object of study and proving a sufficient strong result regarding their joint distribution will give the desired failure of a local central limit theorem. Finally define σ to be the variance of (z).

Note that all the different functions defined here are multilinear, since (n,(k-1)!) = 1.



 §.§ Asymptotics of σ_ℓ
 We note that σ_ℓ = Θ_k(n) is easily computed for ℓ≠ 1 and that 
σ_1 = Θ_k(n^3/2). This follows immediately from the fact that any two elements of /n lie in O_k(1) k-term arithmetic progressions jointly.



 §.§ Overview of the Main Arguments
 
Given the above expansion we are now in position to give a general overview of the proof. The argument is centered on demonstrating that the functions ^1 and the remaining ^ℓ fluctuate independently and on differing scales and then use this to deduce a failure of the local central limit theorem. The key claim is that {^ℓ}_ℓ=1, 3≤ℓ≤ k, suitably normalized, approaches in distribution a set of independent Gaussian (along with quantitative bounds). In particular we prove the following result.

For g∈ C^3(^k-1), we have

    | g(^1(y),^3(y),…,^k(y)) -  g(Z)|≲_kM_2(g)+M_3(g)/n^1/2,

where Z is a standard Gaussian random vector in ^k-1.

In the notation above M_2(g) and M_3(g) are the maximal operator norms of the second and third order derivative tensors of g; more informally these quantities simply measure the fluctuations in g. In order to prove the desired CLT result we first use a version of the Gaussian Invariance Principle which allows one to replace scaled Bernoulli's with Gaussians; this reduction appears in <ref>. This reduction, while not strictly necessary, simplifies the argument. Then we use the theory of exchangeable pairs to deduce the necessary central limit theorem, which constitutes <ref>. Roughly, the exchangeable pairs argument proceeds by using analyzing a single draw of Gaussian y's for vector (^1(y),^3(y),…,^k(y)) and analyzes what occurs if precisely one of the y at random is resampled. The method of exchangeable pairs allows one to deduce a quantitative central limit theorem from this perturbative analysis; however, a significant amount of effort is expended in verifying the necessary moment estimates. In particular, one consequence of the above analysis is that 

    ∑_a∈/n∑_d∈ [n/2] z_az_a+dz_a+2d/√(n2)d⟶𝒩(0,1)

if z_i are independent standard normals, since this corresponds to ^3 for k = 3. Specializing the analysis to this case may be useful for some readers. Note here that if z_i were not centered then the standard deviation jumps from Θ(n) to Θ(n^3/2), and the corresponding central limit theorem is a easy consequence of the method of dependency graphs as demonstrated in <cit.>.

We next convert these results into a bound on Kolmogorov distance and then deduce the failure of a local central limit theorem using a sampling argument in <ref>. Ultimately the failure of the local central theorem is derived essentially from the fact that ^1 takes on values which are separated by Θ_k,p(n) from one another and the smearing which occurs due to the remaining components also lives on the scale of Θ_k,p(n). Thus it is not able to flatten this effect out. These two sections give one way of implementing this intuition.




§ REDUCTION TO GAUSSIAN ESTIMATE

We first use an invariance principle for multilinear polynomials. In order to do so we need to define the influence of a variable for a Boolean function and whether a random variable is hypercontractive. This step is not strictly speaking necessary, but does not weaken our bounds and allows us to establish the rest of the argument in a slightly cleaner form.

The influence of a variable x_i in a boolean function F(x_1,…,x_n) = ∑_S⊆ [n] a_S∏_i∈ S x_i is 

    Inf_t[F] = ∑_t∈ S⊆ [n] a_S^2.



A random variable X is (p,q,ρ)-hypercontractive (1≤ p≤ q ≤∞ and 0≤ρ < 1) if for all constants a,b∈ we have 

    ||a + ρ b X||_q≤ ||a+bX||_p.


Finally we need that the p-biased bit is hypercontractive with the appropriate constants. This follows from the following result in <cit.>.

 If X is a mean zero, symmetric, discrete random variable with
 
    λ = min_x∈Range(X)[X = x].
 Then X is (2,3,ρ)-hypercontractive for ρ = 1/√(q-1)·λ^1/2-1/q.

We are now ready to define a version of the multifunction invariance principle; this version appears in <cit.>. 

Let F^(1),…, F^(d) be formal
n-variate multilinear polynomials each of degree at most k∈. Let
x_1,…,x_n and y_1,…,y_n be independent ℝ-valued random variables
such that [x_t]=[y_t]=0 and [x_t^2]=[y_t^2]=1.
Assume each random variable x_t and y_t is (2,3,ρ)-
hypercontractive. Then for any C^3 function ψ:^d→
satisfying ||∂^βψ||_∞≤ C for all |β| = 3,

    |[ψ(F(x))-ψ(F(y))]|
    ≤Cd^2/3ρ^3k∑_t=1^n∑_j=1^dInf_t[F^(j)]^3/2


For our application this will amount to the following theorem on the distribution of (y) against test functions. 

Let y_i be defined as before and y_i' be standard normal random variables. Then for any C^3 function ψ:^k-1→
satisfying ||∂^βψ||_∞≤ C for all |β| = 3,

    | 𝔼[ψ(^1(y'), ^3(y'),…,^k(y'))-ψ(^1(y), ^3(y),…,^k(y))]|
    ≤C_k,p/n^1/2

where the constant C_k,p is linearly proportional to C.

Here we used that Inf_t[F^(j)] = O_k,p(1/n), which easily follows from the asymptotics of σ_ℓ along with the symmetry among the variables.




§ EXCHANGEABLE PAIRS

We now consider the joint distribution of {^ℓ(y_i)}_1, 3≤ℓ≤ k where the y_i are now independent standard normals. We prove a quantitative result regarding its convergence to a multivariate normal using an application of exchangeable pairs. In order to state the version of exchange pairs, we will need we will first define a set of notations. Define for a real matrix 

    ⟨ A, B⟩ = (A^TB)

and 

    A_HS = √((A^TA)) = √(⟨ A, A⟩).

Furthermore define

    A_op = sup_|v|=1,|w|=1|⟨ Av, w⟩|

for matrices and similar for k-order forms 

    A_op = sup_|v_i|=1|A(v_1,v_2,…,v_k)|.
 Given this define the k^th derivative (tensor) operators for f∈ C^k(ℝ^n) as 

    ⟨ D^kf(x),(u_1,…,u_k)⟩ = ∑_i_1,i_2,…,i_k∈ [n]∂^k f/∂ x_i_1…∂ x_i_k(u_1)_i_1…(u_k)_i_k

for vectors u_1,…,u_k∈^n. Finally define

    M_r(g) = sup_x∈ℝ^nD^rg(x)_op.

The last notion we need is that of exchangeable random variables. 

X' and X are exchangeable random variables if (X',X) and (X,X') have the same distribution.

The key probability theoretic statement we will use is a multivariate version of exchangeable random variables for proving convergence to a Gaussian which in this form is due to Meckes <cit.>.

Let (X,X') be an exchangeable pair of random vectors in ^d.  Suppose that
there is an invertible matrix Λ, and a 
random matrix E' such that


  * [X'-X|X]=-Λ X

  * [(X'-X)(X'-X)^T|X]=2Λ+[E'|X
].

Then for g∈ C^3(^d),

    | g(X)- g(Z)|≤Λ^-1_op[
     √(d)/4M_2(g)
    E'_HS
    +1/9M_3(g)|X'-X|^3]

where Z is a standard Gaussian random vector in ^d.

Note this is a simplification of the statement which appears in <cit.> which is sufficient for our purposes. We now apply this to our setting where we set 
y = (y_1,…,y_n) and y' = (y_1,…, y_I',…, y_n) where I is a uniformly random coordinate in [n] and y_i, y_I' are independent standard normals. It obvious by definition that 

    W = {^ℓ(y)}_ℓ=1, 3≤ℓ≤ k, W' = {^ℓ(y')}_ℓ=1, 3≤ℓ≤ k

are exchangeable random variables. We stress that the ℓ = 2 term is missing. Furthermore, our normalization of σ_ℓ has made it so that each coordinate of W has variance 1. Also, [W] = 0 since ^ℓ(y) is multi-linear as we have (n,(k-1)!) = 1. We first compute the matrix Λ in the case of (W,W').

Let W, W' be defined as above. Then 

    [W'-W|W] = -𝐝𝐢𝐚𝐠(i/n)_i=1, 3≤ i≤ k W.



Note that the ℓ^th coordinate of [W'-W|y] is 

    1/n∑_m=1^n   [^ℓ(y_1,…,y_m',y_m+1,…)-^ℓ(y)|y]
       = 1/n∑_m=1^n[^ℓ(y_1,…,0,y_m+1,…)-^ℓ(y)|y]
       = -1/n[∑_m=1^n1/σ_ℓ∑_a∈/n∑_d∈ [n/2]∑_S∈[k]ℓ]∏_i ∈ S, m∈ a + dS y_a+id|y]
       = -1/n([ℓ(^ℓ(y))|y]) = -ℓ/n(^ℓ(y))

and the proposition follows upon taking a conditional expectation with respect to W. The first equality follows because, conditional on the index I = m which was removed, y_m' is independent from everything else and has mean zero and ^ℓ is multilinear.

Now to apply <ref> we will simply take

    E' = [(W'-W)(W'-W)^T-2Λ|y],

which clearly satisfies the necessary hypothesis. To apply <ref> to W, W', we now see it suffices to bound [E'_HS] and |W'-W|^3. Noting that Λ^-1_op = n, we will want bounds of the form O_k(n^-3/2) for each of these two quantities.

It is worth studying the diagonal terms more carefully. We have

    [(W_ℓ'-W_ℓ)^2]    = [2W_ℓ^2-2W_ℓ W_ℓ'] = [2W_ℓ[W_ℓ-W_ℓ'|W_ℓ]] = 2ℓ/n[W_ℓ^2] = 2ℓ/n

by exchangeability, conditional expectations, <ref>, and the normalization of W_ℓ. Therefore

    (E')_ℓ,ℓ   = [(W_ℓ'-W_ℓ)^2|y] - [(W_ℓ'-W_ℓ)^2]

for 1≤ℓ≤ k and ℓ≠ 2.



 §.§ Computing E'

We begin by simply computing E' entry by entry. For this we define the further refinement

    ^ℓ,t(y) = 1/y_tσ_ℓ∑_a∈/n∑_d∈ [n/2]∑_S∈[k]ℓ∏_i ∈ S, t∈ a + d S y_a+id.

Note that the above in theory is not defined when y_t is 0, but really we are simply removing the term y_t from all products in the summation so this can be extended in the obvious way. Less formally this is the sum ^ℓ with all the terms containing the term y_t with y_t factored out. Using this notation it follows easily that the nondiagonal entries are  

    (E')_i,j = 1/n∑_s∈ [n]^i,s(y) ^j,s(y)(y_s^2 + 1)

and the diagonal entries are 

    (E')_i,i = -2i/n +  1/n∑_s∈ [n] (y_s^2 + 1)^i,s(y)^2.

Here we used that each random variable y_i has mean zero and variance one, and same for its replacement y_I'. In fact, the normalization of σ_ℓ implies that [(E')_i,i] = 0, although this is not obvious by direct computation. We can see this from cross-comparison with the earlier expression for (E')_ℓ,ℓ.

We now proceed further into the computational abyss and consider 

    (E'E'^T) = ∑_i,j (E')_i,j^2.

We will need a bound on 

    [√((E'E'^T))]≤√([(E'E'^T)])

which has decay properties of the form O_k(n^-3/2). Thus it suffices to prove a bound of the form O_k(n^-3) for

    [∑_i,j (E')_i,j^2].

Note that it suffices to prove such a bound for each individual summands as there are k^2 such summands and the result will follow.



§ BOUNDING E'



 §.§ Non-diagonal terms

We will first consider the case where i≠ j. Without loss of generality let i < j. Thus, since i≥ 1 and j≠ 2, we have j≥ 3.

We first define an even further refinement of our polynomials,

    ^ℓ,t,S(y) = 1/y_tσ_ℓ∑_a∈/n∑_d∈ [n/2]∏_i ∈ S, t∈ a + d S y_a+id.

Note that

    (E')_i,j = 1/n∑_S∈[k]i, T∈[k]j∑_v∈ [n]^i,v,S(y)^j,v,T(y)(y_v^2+1)

and thus it suffices to prove that for all S∈[k]i and T∈[k]j we have

    [(1/n∑_v∈ [n]^i,v,S(y)^j,v,T(y)(y_v^2+1)))^2] = O_k(n^-3)

by Cauchy-Schwarz. Using Cauchy-Schwarz again, it suffices to instead prove that

    [(∑_v∈ [n]^i,v,S(y)^j,v,T(y))^2+
    (∑_v∈ [n]^i,v,S(y)^j,v,T(y)y_v^2)^2] = O_k(n^-1).

The key idea is that when expanded as a polynomial in the y's, the inside of the expectation will have most terms contain an odd power of some y_i, which leads to a zero contribution as y_i is a standard normal. Every nonzero term contributes an amount bounded by O_k(1)·(σ_iσ_j)^-2 as the exponents are bounded. Note that the parities of the exponents are unchanged between the first and second terms, so we use the second out of convenience.

A term of the second, when expanded out, amounts to choosing v_1, v_2∈ [n] and then a_11,a_12,a_21,a_22∈/n and d_11,d_12,d_21,d_22∈ [n/2] such that v_c∈ a_c1+d_c1S and v_c∈ a_c2+d_c2T for c∈{1,2}. Let A_ct for k,t∈{1,2} be the sets thus formed (there are no self-intersections since (n,(k-1)!) = 1). Let the multiset A equal the union, with repetition, of all A_ct. Note |A_c1| = i and |A_c2| = j, so that |A| = 2(i+j).


Given an initial choice of three of the (a_ct,d_ct), there are O_k(1) ways to choose the remaining pair so as to be compliant with the condition that every element in A appears with even parity.


After canceling we can see what parities the remaining set must have at each value of /n, which precisely determines it. (Recall that each is a set rather than a multiset because (n,(k-1)!) = 1.) Then there are O_k(1) ways to choose the (a_ct,d_ct) given what the set must be.


First consider the case where A_11,A_12 do not intersect at a place other than v_1. This means they together hit i+j-2 distinct values once, and v_1 twice. We see this immediately implies that A_21 and A_22, after removing v_2 from each, must hit precisely these i+j-2 distinct values. Since j≥ 3, this means that the value of v_2 is determined up to O_k(1) choices by looking at the possible ways A_22 hits these i+j-2 values in j-1≥ 2 places. Therefore we see there are O_k(1) choices of a_21,d_21,a_22,d_22 after selecting v_1,d_11,d_12, which means we have O(n)^3· O_k(1) total choices (as there are O_k(1) choices of a_11,a_12 given that information).

The analysis is similar if A_21,A_22 do not intersect other than at v_2. So now we consider the case where A_11,A_12 intersect at a place other than v_1 and same for A_21,A_22. After choosing v_1,v_2 with O(n^2) choices, we claim there are O_k(1) ways to finish choosing. First note that A_11,A_12 have O_k(n) possibilities together, and after that there are O_k(1) choices for whichever of A_21,A_22 intersects A_11∪ A_12 (which must happen as these sets A_11, A_12 cannot cancel each other out, being of differing size). And by <ref> there are O_k(1) ways to choose the last one. This gives O_k(n^3) once more.

In total, we have O_k(n^3) terms that are not zero in the expectation. This yields a total contribution of O_k(n^3)· (σ_iσ_j)^-2 = O_k(n^-1), as desired.



 §.§ Diagonal terms

Now we consider the diagonal terms (E_ℓ,ℓ)'. From <ref>, we have

    [(E')_ℓ,ℓ^2] = [([(W_ℓ'-W_ℓ)^2|y]-[(W_ℓ'-W_ℓ)^2])^2] = ([(W_ℓ'-W_ℓ)^2|y]),

where the variance in the final line is over the randomness of the standard normals y. Now

    [(W_ℓ'-W_ℓ)^2|y] = _I,y'[(y_I'-y_I)^2^ℓ,I(y)^2] = 1/n∑_i=1^n(1+y_i^2)^ℓ,i(y)^2.

If ℓ = 1, ^ℓ,i(y) is a constant of size Θ_k(n^-1/2). We end up with a bound of quality O_k(n^-3) trivially. Now let ℓ≥ 3, recalling ℓ≠ 2. We have

    [(E')_ℓ,ℓ^2] = 1/n^2σ_ℓ^4∑_1≤ i,j≤ n[(1+y_i^2)(σ_ℓ^ℓ,i(y))^2,(1+y_j^2)(σ_ℓ^ℓ,j(y))^2].


We first deal with the i = j terms. They are bounded by [(1+y_i^2)^2(σ_ℓ^ℓ,i(y))^4]. Note that this value is independent of i, so we let i = 0 (which is the same as i = n). We adopt a similar method as before. It suffices to show that there are O_k(n^2) terms of this i = 0 value that, when expanded, yield a nonzero expectation value. This is since there are n such terms and as σ_ℓ = Θ_k(n), which would lead to an overall contribution of the desired size O_k(n^-3) to [(E')_ℓℓ^2].

We use the ^ℓ,i,S refinement from before. By Hölder's inequality, it suffices to bound each [(1+y_0^2)^2(σ_ℓ^ℓ,0,S(y))^4]. We also can choose an exponent of y_0 from the initial term, but it does not affect parities of exponents and is of constant order so we ignore this and assume we have the y_0^4 term for simplicity.

Each term within this sum is chosen via d_1,…,d_4∈ [n/2] and offsets (e.g. which term equals the y_0 term that is being divided in ^ℓ,0,S), each of which contributes terms of the form y_d_jS_j, where S_j is one of O_k(1) many shifts of S that contains 0.  Now for any valid tuple (d_1,…,d_6), make a graph on vertex set {1,…,6}, with i,j connected if d_iS_i and d_jS_j intersect other than at 0.

Given such a graph, we claim that there are O_k(n) ways to choose the ds associated to a connected component of this graph in a manner compatible with the graph. Indeed, we find that, for example, if d_1,d_2,d_3 are connected, then choosing d_1 will fix the value say of cd_2 for some c∈ [k], which yields O_k(1) possible values of d_2, and then O_k(1) possible values of d_3 similarly.

Furthermore, in a graph associated to a valid tuple (d_1,…,d_6), i.e., one with even powers of the ys, we must have no disconnected vertices. Indeed, since the vertex is disconnected, the associated value of d_i must give rise to a multiset d_iSn which must cancel out all of its contributions to the ys. This is impossible as (n,(k-1)!) = 1.

Finally, we have at most 4/2 = 2 connected components of non-isolated vertices, each of which have O_k(n) ways to choose the ds. This yields an upper bound of O_k(n^2), as desired.

Now we consider i≠ j. Again, by translation invariance we see the value only depends on j - i. Therefore it suffices to show for i≠ 0 that

    [(1+y_0^2)(σ_ℓ^ℓ,0(y))^2,(1+y_i^2)(σ_ℓ^ℓ,i(y))^2] = O_k(n)

since there are around n^2 total terms. We will show that

    [(σ_ℓ y_0^ℓ,0(y))^2,(σ_ℓ y_i^ℓ,i(y))^2] = O_k(n).

Again, the other four cases that need to be verified will be essentially identical, since we are just removing even exponent terms. Consider

    [(σ_ℓ y_0^ℓ,0(y))^2(σ_ℓ y_i^ℓ,i(y))^2]    = ∑_S,T∈[k]ℓ^2∑_a,b∈(/n)^2∑_d,e∈[n/2]^2
    0∈ a_j+d_jS_j
    i∈ b_j+e_jT_j[∏_j=1^2∏_s_j∈ S_j y_a_j+d_js_j∏_t_j∈ T_jy_b_j+e_jT_j].


We claim that the amount of nonzero terms other than those with a_1+d_1S_1=a_2+d_2S_2 = A and b_1+e_1T_1=b_2+e_2T_2 = B and A∩ B = ∅ is O_k(n). Indeed, this is a similar argument as in the non-diagonal term case. The analogue of <ref> immediately follows, and similar arguments to earlier deal with the case that a_1+d_1S_1,a_2+d_2S_2 intersect only at 0. Indeed, if so, then they must hit 2ℓ-2 distinct values once and 0 twice. Then b_1+e_1T_1,b_2+e_2T_2, after removing j from each, must precisely hit those 2ℓ-2 values, each hitting ℓ-1 of them. As ℓ≥ 3, we see that this pins down what b_1,e_1,b_2,e_2 are up to O_k(1) possibilities, as linear combinations of the d_i (say after fixing which positions of a_i+d_iS_i equal 0). Furthermore, we can compute j as a linear combination of the d_i. Since j≠ 0, it must be a nonzero linear combination. This pins down (d_1,d_2) to O_k(n) possible values. Thus we have O_k(n)· O_k(1) = O_k(n) total possibilities. Furthermore, we have a similar analysis for the case where b_1+e_1T_1,b_2+e_2T_2 intersect only at j.

Now we consider the case where a_1+d_1S_1,a_2+d_2S_2 intersect other than at 0, and similar for b_i+e_iT_i. Then there are O_k(n) choices for (a_1,d_1), and then O_k(1) choices for (a_2,d_2), and if we are assuming a_1+d_1S_1≠ a_2+d_2S_2, the terms b_i+e_iT_i must hit one of these. There are thus O_k(1) possibilities for the value of the set that does hit these values, and then O_k(1) possibilities for the other set. Thus we have O_k(n) choices once more, under the hypothesis that a_1+d_1S_1≠ a_2+d_2S_2. Similar analysis holds if instead we assume b_1+e_1T_1≠ b_2+e_2T_2. In the case where neither holds, so that a_1+d_1S_1 = a_2+d_2S_2 = A and b_1+e_1T_1 = b_2+e_2T_2 = B, if we assume that A∩ B≠∅ then again we have a bound of O_k(n),

The only remaining terms are those that have a_1+d_1S_1 = a_2+d_2S_2 = A and b_1+e_1T_1 = b_2+e_2T_2 = B and A∩ B = ∅, as desired.

Now we consider

    [(σ_ℓ y_0^ℓ,0(y))^2] = [(σ_ℓ y_i^ℓ,i(y))^2] = ∑_S∈[k]ℓ^2∑_a∈(/n)^2∑_d∈[n/2]^2
    0∈ a_j+d_jS_j[∏_j=1^2∏_s_j∈ S_jy_a_j+d_js_j].

We claim that the only nonzero terms are those with a_1+d_1S_1=a_2+d_2S_2. Indeed, they are both sets as (n,(k-1)!) = 1, and if they are not equal then there is some element with an odd exponent.

Now, putting it all together, we see that

    [(1+y_0^2)(σ_ℓ^ℓ,0(y))^2,(1+y_i^2)(σ_ℓ^ℓ,i(y))^2]

has a contribution of O_k(n) terms in its [XY] portion which we bound by O_k(n). Otherwise it only has terms corresponding to a_1+d_1S_1=a_2+d_2S_2=A and b_1+e_1T_1=b_2+e_2T_2=B and A∩ B = ∅. Thus the expectations factor into a product of [∏_a∈ Ay_a^2] and [∏_b∈ By_b^2]. This is canceled by the terms described by

    [(σ_ℓ y_0^ℓ,0(y))^2][(σ_ℓ y_i^ℓ,i(y))^2].

There is one catch: the terms in this latter product of expectations [∏_a∈ Ay_a^2][∏_b∈ By_b^2] which have A∩ B≠∅ are not canceled in the [XY] term. However, we see that there are O_k(n)· O_k(1) of them, for after choosing whichever of O_k(n) values for A that we want, we have O_k(1) choices of B that both go through j and intersect A (unless A goes through j, but then it only has O_k(1) choices and B has O_k(n) choices in this case).

So, overall, the covariance is indeed O_k(n), as desired.



§ BOUNDING MOMENTS

For the second part we need to prove that 𝔼[|W-W'|^3] is of size O_k(n^-3/2) which is the same as

    [(∑_ℓ=1, 3≤ℓ≤ k|W^(ℓ)-W'^(ℓ)|^2)^3/2] = O_k(n^-3/2).

Therefore it in fact suffices to prove that 

    [|W^(ℓ)-W'^(ℓ)|^3]= O_k(n^-3/2),

using Hölder's inequality. For ℓ = 1 this is trivial, using σ_1 = Θ_k(n^3/2). Now let ℓ > 1 and note that 

    [(|W^(ℓ)-W'^(ℓ)|)^3]    = [|^ℓ(y)-^ℓ(y')|^3]
       = _t∈/n[|y_t-y_t'|^3|^ℓ,t(y)|^3]
       = [|y_0-y_0'|^3|^ℓ,0(y)|^3]
       ≤[|y_0-y_0'|^6]^1/2[|^ℓ,0(y)|^6]^1/2
       = √(120)[^ℓ,0(y)^6]^1/2.

We now use the ^ℓ,t,S(y) refinement as in <ref>. Using Hölder's inequality again, it suffices to prove that

    [^ℓ,0,S(y)^6] = O_k(n^-3).

We adopt a similar method to <ref>. Since σ_ℓ = Θ_k(n), it amounts to showing there are O_k(n^3) terms of [^ℓ,0,S(y)^6] which have a nonzero contribution, i.e., even exponents of the y's.

Each term within this sum is chosen via d_1,…,d_6∈ [n/2], each of which contributes the terms y_d_jS. Now for any valid tuple (d_1,…,d_6), make a graph on vertex set {1,…,6}, with i,j connected if d_iS and d_jS intersect.

Each term within this sum is chosen via d_1,…,d_6∈ [n/2] and offsets (e.g. which term equals the y_0 term that is being divided in ^ℓ,0,S), each of which contributes terms of the form y_d_jT_j, where S_j is a set which is one of O_k(1) many shifts of S that contain 0, and T_j = S_j-{0}. Now for any valid tuple (d_1,…,d_6), make a graph on vertex set {1,…,6}, with i,j connected if d_iT_i and d_jT_j intersect.

Given such a graph, we claim that there are O_k(n) ways to choose the ds associated to a connected component of this graph in a manner compatible with the graph. Indeed, we find that, for example, if d_1,d_2,d_3 are connected, then choosing d_1 will fix the value say of cd_2 for some c∈ [k], which yields O_k(1) possible values of d_2, and then O_k(1) possible values of d_3 similarly.

Furthermore, in a graph associated to a valid tuple (d_1,…,d_6), i.e., one with even powers of the ys, we must have no disconnected vertices. Indeed, since the vertex is disconnected, the associated value of d_i must give rise to a multiset d_iSn which must cancel out all of its contributions to the y's. This is impossible as (n,(k-1)!) = 1.

Finally, we have at most 6/2 = 3 connected components of non-isolated vertices, each of which have O_k(n) ways to choose the d's. This yields an upper bound of O_k(n^3), as desired.



 §.§ Conclusion

Putting the various estimates together we have proved the following result, which is a restatement of <ref>.

For g∈ C^3(^k-1), we have

    | g(W) -  g(Z)|≲_kM_2(g)+M_3(g)/n^1/2,

where Z is a standard Gaussian random vector in ^k-1.




§ CONVERSION TO BOUND IN KOLMOGOROV DISTANCE

We now convert this test function bound into a bound on the cumulative distribution function.

For any a, b we have that 

    ℙ[^1(y)<a,∑_i=3^kσ_ip^k-i/2(1-p)^i/2^i(y)/√(∑_i=3^kσ_i^2p^2k-i(1-p)^i)<b] = 1/2π∫_-∞^a∫_-∞^be^-(x^2+y^2)/2 dx dy + O_k,p(n^-1/8).



The key idea is to take ϕ_ℓ which is a smooth function which is 1 on (-∞, ℓ], 0 on [ℓ + ϵ,∞), has second derivative bounded by O(ϵ^-2), and third derivative bounded by O(ϵ^-3). Furthermore let ϕ_ℓ be in [0,1] over the entire domain. Given this define γ_a,b(x,y) = ϕ_a(x)ϕ_b(y). It follows from σ_i = Θ_k(n) for all 3≤ i≤ k that

    Ψ_a,b(y_1,y_3,…,y_k) = 
    γ_a,b(y_1,∑_i=3^kσ_i p^k-i/2(1-p)^i/2y_i/√(∑_i=3^kσ_i^2p^2k-i(1-p)^i))

has M_2(Ψ_a,b) = Θ_k,p(ϵ^-2), M_3(Ψ_a,b) = Θ_k,p(ϵ^-3), and 
∂^βΨ_a,b = Θ_k,p(ϵ^-3) for all |β| = 3. The key point of course is that for standard Gaussians z_i we have 

    𝔼[Ψ_a,b(z_1,z_3,…,z_k)] = 1/2π∫_-∞^a∫_-∞^be^-(x^2+y^2)/2 dx dy + O_k(ϵ)

and by <ref> it follows that

    𝔼[Ψ_a,b( ^1(y),^3(y),…,^k(y))] = 𝔼[Ψ_a,b(z_1,z_3,…,z_k)] + O_k,p(ϵ^-2+ϵ^-3/n^1/2).
 Choosing ϵ = n^-1/8, we obtain the desired right side as an upper bound, noting that Ψ_a,b dominates the desired indicator function. A lower bound is obtained in an analogous manner and the result then follows.





§ PROOF OF THE FAILURE OF LOCAL CENTRAL LIMIT THEOREM

In this section we prove that  does not obey a local central limit theorem.  Specifically:
thm:local-clt-failure
Fix p∈ (0,1) and k≥ 3. Then for all sufficiently large n relatively prime to (k-1)! there is a point x such that 
    |ℙ[(z) = x] - 1/σ_n√(2π)exp(-(x-μ_n)^2/2σ_n^2)| = Ω(1/σ_n),

where μ_n and σ_n in the statement are the expectation and standard deviation of (z) and z is sampled i.i.d. with probability p.

We first give a high level overview of the proof.  The proof proceeds by building two sets  L_α and L_β of equal size both close enough to the mean of  so that were there to be a local limit theorem for  we would necessarily have

    [∈ L_α]≈[∈ L_β]≈|L_α|/σ_n√(2π).

However, as a result of Lemma <ref> we will be able to compute
[∈ L_α]∝ f_δ(α), and [∈ L_β]∝ f_δ(β), where f_δ is as defined in Lemma <ref> below.

The rough idea in building L_α and L_β is to note that ^1+^2 takes values very near to a lattice Gℤ where G=Θ(n).  Meanwhile ^>2 has standard deviation Θ(n).  L_α (and L_β) will roughly correspond to the event that ≈α G  G (≈β G  G respectively), and we can use our joint central limit theorem for ^1 and ^>2 to show that [≈α G  G]∝ f_δ(α) for some choice of δ.  But since f_δ(α)≠ f_δ(β) we will conclude that (L_α)≠(L_β) disproving any chance that  obeys a local central limit theorem.

Before beginning our proof, we define f_δ and prove it is nonconstant.



The function 

    f_δ(x) = ∑_λ∈ℤ e^-(x-λ)^2/δ

is not the constant function for any value δ > 0.  Furthermore for any C>0 there is a constant D>0 so that if δ<C then for some pair α,β∈ (0,1) we have f_δ(α)-f_δ(β)≥ D.



Let us calculate the Fourier transform of f=f_δ as 1-periodic function. Note that 

    f̂(n)    = ∫_[0,1] e^-2π inx f(x) dx = ∫_[0,1] e^-2π inx∑_λ∈ℤ e^-(x-λ)^2/δ dx
       = ∫_ℝ e^-2π inx  e^-x^2/δ dx = √(πδ)e^-π^2n^2δ,

and therefore the function is not constant. Furthermore, by Parseval we have that

    ∫_[0,1] (f(x)-f̂(0))^2 dx   =∑_n=1^∞f̂^2(n)=∑_n=1^∞πδ e^-2π n^2δ≥π∫_δ^∞ e^-2πx^2/δdx

and so the variance of f is bounded below whenever δ is bounded, proving the result.

We now prove our main result, the failure of a local central limit theorem for constant p and k.
thm:local-clt-failure
Fix p∈ (0,1) and k≥ 3. Then for all sufficiently large n relatively prime to (k-1)! there is a point x such that 
    |ℙ[(z) = x] - 1/σ_n√(2π)exp(-(x-μ_n)^2/2σ_n^2)| = Ω(1/σ_n),

where μ_n and σ_n in the statement are the expectation and standard deviation of (z) and z is sampled i.i.d. with probability p.



Throughout this section we use x_i to denote the 0,1 indicator of whether i is in our random set, and y_i to denote the normalized Bernoulli random variables y_i:=(x_i-p)/√(p(1-p)).  We additionally use the shorthand ℓ=∑_i=1^n y_i and ℓ̃:=∑_i=1^n x_i and q:=1-p.

First we need exact formulae for ^1 and ^2 in terms of ℓ, which are


    ^1   =∑_i=1^n k(n-1)/2p^k-1/2q^1/2 y_i= k(n-1)/2p^k-1/2q^1/2ℓ
    ^2   =k 2p^k-1q∑_|S|=2y_S=k 2p^k-1q/2(ℓ^2-∑_i=1^n y_i^2)=k 2p^k-1q/2(ℓ^2-n-1-2p/√(pq)ℓ)

where y_S = ∏_i∈ Sy_i. And so we find that we can express ^1+^2=C_0+C_1ℓ+C_2ℓ^2:=Q(ℓ) where

    C_0:   =-nk(k-1)/4p^k-1q
    
    C_1:   =k(n-1)/2p^k-1/2q^1/2-(1-2p)k(k-1)/4p^k-3/2q^1/2
    
    C_2:   =k(k-1)/4p^k-1q


So to understand ^1+^2 it is enough to understand ℓ.  We note that ℓ is valued on the lattice -n√(p/q)+ℤ/√(pq).  The most commonly taken value for ℓ occurs when ℓ̃=∑_i=1^n x_i=[pn].  When this occurs we see that ℓ takes the value 

    a_0:=ℓ̃-pn/√(pq)=[pn]-pn/√(pq)

and hence ^1+^2 takes the value

    x_0:=^1+^2=Q( a_0)=C_0+C_1a_0+C_2a_0^2

Now we can define X=^1(y)+^2(y)-x_0 and Y=^≥ 3(y).  So X+Y=-μ-x_0, and the most likely value taken by X is 0.


Let  …,A_-2, A_-1, A_0=0, A_1,… be the values taken by X when |ℓ|≲_k,p n, listed in order. In general we see that X takes the value A_t whenever ℓ̃=[pn]+t and so ℓ =a_0+t/√(pq) when |ℓ|≲_k,p n (as Q'(ℓ) > 0 in such a range). Therefore we can compute for any t that

    A_t   =Q(a_0+t/√(pq))-Q(a_0)=C_2(2ta_0/√(pq)+t^2/pq)+C_1t/√(pq)

To alleviate notation we define a constant G for the dominant increment  G:=C_1/√(pq). 
It will commonly be helpful to have the bound

    |A_t-tG|=|C_2(2ta_0/√(pq)+t^2/pq)|≤ C_2t^2+2t/pq.

Now we are in a position to define the events we look at.  Fix α∈ [0,1], and  i,B∈ℝ.  Then we define the intervals I_α(i,B) and families of intervals L_α(B,s) by  setting

    I_α(i,B)   :=[G(i+α)-B, G(i+α)+B]
    
    L_α(B,s)   :=⋃_i=-s^s I_α(i,B)



Note that if α=0 then the intervals I_0(i,B) are just intervals of length 2B centered around that lattice points in C_1ℤ/√(pq).  These intervals are disjoint so long as we ensure |B|<G/2.  As α moves between 0 and 1, the interval slides between neighboring lattice points in Gℤ. L_α(B,s) collects the most central 2s+1 intervals in the collection.

Our goal becomes to show that for some pair B,s=o(n) there exist distinct values α,β∈ (0,1) so that [X+Y∈ L_α(B,s)] and [X+Y∈ L_β(B,s)] are far. This will contradict the existence of a local limit theorem, thus finishing our proof of <ref>.


We first choose η so that [|Y|≥η C_1/√(pq)]≤ n^-100.  By hypercontractivity concentration bounds (see e.g. <cit.>) we see that we may take η = Θ_p,k((log n)^k/2).

We may use Lemma <ref> and some work to compute [X+Y∈ L_α(B,s)]. We state our result and postpone the calculation to <ref>.


Assume that 0<B<n^1-1/36 and η<s<n^1/2-1/24.  Let σ_Y denote the standard deviation of Y (and as such σ_Y=Θ(n)). Then 

    [X+Y∈ L_α(B,s)] =2sB√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8)

for some uniformly bounded δ = δ(n, k, p).


In fact, as n→∞ this function tends towards a limit; we do not bother replacing δ(n, k, p) with its limit δ(k, p) as this will be inconsequential to our arguments.






Additionally, were  to obey a local limit theorem, then we could compute [X+Y∈ L_α(B,s)] in a different way.




Assume that Z is a random variable with mean μ_Z and standard deviation σ_Z which for all m∈ℕ satisfies 

    [Z=m]=1/√(2π)σ_Zexp((m-μ_Z)^2/2σ_Z^2)+o(σ_Z^-1)

Then for any set S⊂ℤ∩ [μ-T, μ+T] with T≤σ_Z we have 

    (Z∈ S)=|S|/√(2π)σ_Z+o(|S|/σ_Z)+O(|S|T/σ_Z^2).



This follows from simply noting that |1-exp((m-μ)^2/2σ_Z^2)|≲ (m-μ)/σ_Z in this range, and summing over ∑_m∈ S(Z=m).




We now have all of the tools to prove <ref>.


Choose δ = δ(k, p), which is constant. We know from <ref> that there are α≠β∈ (0,1) so that f_δ(α)-f_δ(β) =Ω(1).  If we set B=⌊ n^1-1/36⌋ and s=⌊ n^1/2-1/24⌋ then by <ref> we have

    [X+Y∈ L_α(B,s)] =2sB√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8)

and likewise for L_β(B,s).  Crucially, note that the main term has size n^-5/72 and so dominates the error term.  
Applying the same reasoning to L_β(B,s) and taking differences yields

    [X+Y∈ L_α(B,s)]   -[X+Y∈ L_β(B,s)]=2sB√(2)/σ_Y√(π npq)[f_δ(α)-f_δ(β)]+O(η n^-1/8)
       =Ω(n^-5/72)


However if we assume that  obeys a local central limit theorem, then so does X+Y. Note that L_α(B,s) consists of elements of size at most Gs+B=O(n^3/2-1/24), and |L_α(B,s)|=Θ(n^3/2-5/72). So by <ref> we see that

    [X+Y∈ L_α(B,s)]-[X+Y∈ L_β(B,s)]=o(n^-5/72)
    +O(n^-1/9)

This is a direct contradiction.





§ CONCLUSION

We conclude by pointing out various open questions regarding the failure of the local central limit theorem. First, note that there is a gap between the theorems we proved and a total explanation of the behavior exhibited in Figure <ref>. An ideal theorem would prove more precisely that the distribution of (S) tends to the convolution of two discrete Gaussians seemingly exhibited in the figure. Such a precise theorem would prove that (S), conditional on the size of S, satisfies a local central limit theorem. Failing this precise local limit theorem, at least one could hope to understand how wildly the distribution oscillates in the following precise sense:

Fix ϵ = 1/100. Let S be a subset of /n where each element is chosen independently with probability 1/2 and set μ_n = [(S)]. What is the largest constant C such that for infinitely many n there exist integers x_n,y_n such that |x-μ_n|,|y-μ_n| ≤ n^3/2-ϵ which satisfy 
    [(S)=x_n]/[(S)=y_n]≥ C?


We argue in the subsection below that C≈ 4.745 works, however our method does suggest that in fact that C cannot be taken arbitrarily large. To be more precise, the largest constant C coming from our method is sup(f(x))/inf(f(x)) where f(x) = ∑_λ∈ e^-9(x-λ)^2. This is in fact the optimal constant if one can prove a sufficiently strong local limit theorem in the style of our above results. Furthermore, proving that C cannot be taken to be unbounded, along with the central limit theorem in the paper, would immediately show anti-concentration for the random variable (S) at the correct level.



 §.§ Computing C

Here we compute the value of C coming out of <ref> by computing the resulting value of λ in the case k = 3, p = 1/2. It is easy to show that

    8·(y) = n(n-1)/2+3/2(n-1)∑_a∈/ny_a+3∑_0≤ a<b<ny_ay_b+∑_a∈/n∑_d∈[n/2]y_ay_a+dy_a+2d,

hence ^1(y) has steps of size 3n (since y_a∈{-1,1}) while ^3(y) has mean zero and variance n(n-1)/2. Hence the associated normal has standard deviation of size n/√(2). If we normalize ^1(y) to have steps of size 1, then ^3(y) will be normalized to have standard deviation √(2)/6 hence density proportional to e^-9x^2. Therefore we find value δ = 1/9, and the claimed ratio as above. It can further be shown that the minimum is attained at 1/2+ and the maximum at , hence we can prove a ratio of

    C = ∑_x∈e^-9x^2/∑_x∈e^-9(x-1/2)^2≈ 4.745.


alpha




§ PROOF OF LEMMA <REF>


We use all the same terminology and notation as in <ref>, including C_0, C_1, C_2. First we need a lemma relating the probability that X+Y∈ L_α(B,s) to a bound on the the joint distribution of X and Y.


 
Assume that s>η and B-C_2s^2+s/pq≥ 0.  Then

    [X+Y∈ L_α(B,s)] ≥[|X|≤ A_s-η,   Y∈ L_α(η, B-C_2s^2+s/pq)]



We show that, in fact, the event on the left hand side contains the event on the right.  Let X=A_t where |t|≤ s-η and assume that Y=G(i+α)+b where |i|≤η and b≤  B-C_2s^2+s/pq.  Then we note that

    |X+Y-G(t+i+α)|   =|(tG+C_2(2ta_0/√(pq)+t^2/pq)+G(i+α)+b)-G(t+i+α)|
    
       ≤ C_2s(s+1)/pq+b≤ B

As (t+i)≤ s it follows that if the event on the right hand side occurs, then X+Y∈ L_α(B,s).

 
Assume that |B|<G/2 and C_2(s+η+2)(s+η+3)/pq<G/2.  Then

    [X+Y∈ L_α(B,s)] ≤[|X|≤ A_s+η+1,   Y∈ L_α(η, B+C_2(s+η)(s+η+1)/pq)]+O(n^-100)





First we note that

    (X+Y∈ L_α(B,S))≤(X+Y∈ L_α(B,S) |Y|≤η G)+O(n^-100).

So we will throughout condition on the event that |Y|≤η G. In that event, we show that the event on the left hand side implies that the event on the right hand side occurs. First, we can simply upper bound |X| by 

    |X|≤ |X+Y|+|Y|≤ |(s+α)G+B|+η G.

But we know that 

    A_s+η+2≥ (s+η+2)G- C_2(s+η+2)(s+η+3)/pq> (s+η)G+α G+B.

And so we have that X=A_t where |t|≤ s+η+1.

For Y we note that X+Y∈ L_α(B,s) implies that X+Y=(r+α)G+b where |r|≤ s and |b|≤ B.  By the argument above we know that X=A_t for t≤ s+η+1.  And so we can bound

    |Y-(r-t+α)G|   =|X+Y-X-(r-t+α)G|=|(r+α)G+b-A_t-(r-t+α)G|
       ≤ B+|C_2(s+η+1)(s+η+2)/pq|.

The last thing we need to do to show that Y∈ L_α(η, B+C_2(s+η)(s+η+1)/pq) is to show that |r-t|≤η, but were it otherwise the above equation implies that |Y|> (η+1)G-G, contradicting our assumption that |Y|≤η G. Therefore it must follow that
Y∈ L_α(η, B+C_2(s+η)(s+η+1)/pq).


The main upshot here is that for well chosen values of B and s, the probability bounds furnished by the above lemmas will be indistinguishable up to a margin of error. The last ingredient we need is an estimate for the probability the events |X|≤ A_s and Y∈ L_α(B,s).

For any interval of the form (T-B, T+B) we have

    ∫_T-B^T+B e^-t^2/2dt=2Be^-T^2/2+O(B^3)


  This is just the midpoint rule combined with the observation that |d^2/dt^2 e^-t^2/2|≤ 1. 



Assume that B<n^1-1/36, s<n^1/2-1/24, and η≥log(n).  Let f_δ be as defined in <ref>.  Then

    [|X|≤ A_s,  Y∈ L_α(η, B)]=2sB√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8)
,

where δ = pqσ_Y^2/C_1^2.

First, we note that |X|≤ A_s is equivalent to saying that ^1∈ [a_0/√(n)-s/√(npq), a_0/√(n)+s/√(npq)].
First we note that by Lemma <ref> for each interval I_α(i,B) we have

    (|X|≤ A_s,  Y∈ I_α(i,B))=(1/√(2π)∫_a_0/√(n)-s/√(npq)^a_0/√(n)+s/√(npq)e^-t^2/2dt)(1/√(2π)∫_I_α(i,B)/σ_Ye^-t^2/2dt)+O(n^-1/8)


By Lemma <ref> we can estimate both of these integrals. The first is

    1/√(2π)∫_a_0/√(n) -s/√(npq)^a_0/√(n)+s/√(npq)e^-t^2/2dt=(2s/√(npq))1/√(2π)e^-a_0^2/2σ_1^2+O(s^3/(npq)^3/2)=s√(2)/√(π npq)+O(s^3/n^3/2+1/n^3)

and the second estimate is

    1/√(2π)∫_I_α(i,B)σ_Ye^-t^2/2dt   =1/√(2π)∫_C_1(i+α)/√(pq)σ_Y-B/σ_Y^C_1(i+α)/√(pq)σ_Y+B/σ_Ye^-t^2/2dt=2B/σ_Ye^-C_1^2(i+α)^2/pqσ_Y^2+O(B^3/n^3).

So, defining δ:=pqσ_Y^2/C_1^2=Θ(1) and combining all of these estimates, we find that

    [|X|≤ A_s,  Y∈ I_α(i,B)]   =(s√(2)/√(π npq)+O(s^3/n^3/2+1/n^3))(2B/σ_Ye^-(i+α)^2/δ+O(B^3/n^3))+O(n^-1/8)
       =2sB√(2)/σ_Y√(π npq)e^-(i+α)^2/δ+O(s^3/n^3/2+B^3s/n^3.5+n^-1/8)
       =2sB√(2)/σ_Y√(π npq)e^-(i+α)^2/δ+O(n^-1/8).

Thus taking a union yields

    [|X|≤ A_s,  Y∈ L_α(η, B)]   =∑_i=-η^η2sB√(2)/σ_Y√(π npq)e^-(i+α)^2/δ+O(η n^-1/8)
       =∑_i=-∞^∞2sB√(2)/σ_Y√(π npq)e^-(i+α)^2/δ+O(η n^-1/8+e^-η^2/δ)
       =2sB√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8).


LAlphaEstimator2
Assume that |B|<n^1-1/36, s<n^1/2-1/24 and η<s.  Let σ_Y denote the standard deviation of Y (and as such σ_Y=Θ(n)). Then 

    [X+Y∈ L_α(B,s)] =2sB√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8).




First we use <ref> to upper bound

    [X+Y∈ L_α(B,s)]    ≤[|X|≤ A_s+η+1,   Y∈ L_α(η, B+C_2(s+η)(s+η+1)/pq)]+O(n^-100)
       =s(B+C_2(s+η)(s+η+1)/pq)2√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8)
       = 2sB√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8+s^3/n^1.5).

Next we use <ref> to lower bound

    [X+Y∈ L_α(B,s)]   ≥[|X|≤ A_s-η,   Y∈ L_α(η, B-C_2s^2+s/pq)]
       =(s-η)(B-C_2s^2+s/pq)2√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8)
       =2sB√(2)/σ_Y√(π npq)f_δ(α)+O(η n^-1/8+s^3/n^1.5+η B/n^1.5).

By our hypotheses on B,s, and η the η n^-1/8 term dominates in both inequalities.


