{'fraction_non_alphanumeric': 0.053311595679641326, 'fraction_numerical': 0.01247197880578765, 'mean_word_length': 4.014510525240139, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Noise stability on the Boolean hypercube via a renormalized Brownian motion

We consider a variant of the classical notion of noise on the Boolean hypercube which gives rise to a new approach to inequalities regarding noise stability. We use this approach to give a new proof of the Majority is Stablest theorem by Mossel, O'Donnell, and Oleszkiewicz, improving the dependence of the bound on the maximal influence of the function from logarithmic to polynomial. We also show that a variant of the conjecture by Courtade and Kumar regarding the most informative Boolean function, where the classical noise is replaced by our notion, holds true. Our approach is based on a stochastic construction that we call the renormalized Brownian motion, which facilitates the use of inequalities in Gaussian space in the analysis of Boolean functions.


Introduction
Consider the discrete hypercube C n = {−1, 1} n equipped with the uniform measure µ n . Numerous inequalities concerning functions f : C n → R involve the noise operator, defined as follows: For each x ∈ C n and ρ ∈ [0, 1] let N ρ,x be the unique random variable taking values in C n whose coordinates are independent and such that E[N ρ,x ] = ρx. We define the noise operator T ρ by the equation The quadratic form associated with this operator is sometimes called the noise stability of f , denoted by We will mainly be interested in Boolean functions, f : C n → {0, 1}. If f is a Boolean function which satisfies E[f ] = 1 2 , we will say that f is balanced. For Booelan functions, noise stability is a canonical notion with far-reaching applications in social choice theory and theoretical computer science.
It is easy to check that the operator T ρ is diagonal with respect to the basis of characteristic functions of the form χ A (x) := i∈A x i and attains its spectral gap on functions of the form x → 1{x i > 0}, called dictator functions. This immediately implies the following fact. In this paper we are concerned with two important variants of the above fact. The first one is a deep theorem by Mossel, O'Donnell, and Oleszkiewicz [13], called the majority is stablest theorem. It concerns the case that the function f has small influences. Define It is also not hard to verify that MaxInf(Maj n ) n→∞ − −− → 0. With this in mind, the majority is stablest theorem reads: Theorem 2. (Majority is stablest, [13]) For every ρ ∈ [0, 1] and δ > 0 there exists τ > 0 such that for every balanced Boolean function g : C n → {0, 1} satisfying MaxInf(g) ≤ τ , one has Stab ρ (g) ≤ 1 4 + 1 2π arcsin(ρ) + δ.

A new notion of noise
Our main contribution in this paper is the introduction of an alternative notion of noise, which is, on one hand, slightly different from the one given by the operator T ρ , but on the other hand, can be used in order to derive bounds on the (usual) noise stability. We use this new notion of noise towards two main results: • We give a new proof of the Majority is stablest theorem for the standard notion of noise. Our proof yields an improved error bound in that it is polynomial in the maximal influence rather than logarithmic.
• We show that the variant of the Courtade-Kumar conjecture, which is obtained by replacing the classical notion of noise with ours, holds true. In fact, a more general statement holds where the Shannon (logarithmic) entropy can be replaced by an entropy with respect to any convex function.
Our notion of noise will be constructed as a martingale solution to a stochastic differential equation (SDE), driven by a Brownian motion. The main benefit of this approach is that it allows us to apply tools and techniques from stochastic analysis to analyze the process as a continuous function of the noise level. In particular, we perform a path-wise analysis of the process, which allows for finer manipulations than the analysis of the expectations in (4).
Recently, similar techniques have proven to be quite useful in related settings. The paper [5] used a Brownian motion, constrained to the cube, to study large deviations, and [6] as well as [7] constructed martingales to prove new concentration inequalities. In parallel to this work and relevant to the present setting, [8] employed a discrete process to prove a sharp version of the "it ain't over till it's over" theorem. Our technique is, in some sense, a continuation of these works, and we expand the use of stochastic analytic tools in the Boolean hypercube.

Multilinear extensions and classical noise
To better understand our generalization of the notion of noise, let us first consider a slightly different point of view on the classical noise operator T ρ . We first want to consider the multilinear extension of a function f : C n → R. It is well-known that every such function f can be uniquely written in the form where χ A (x) := i∈A x i , and the coefficients are obtained by the formulaf (A) = f χ A dµ n . This form suggests that there is a natural way to extend the function f from the discrete hypercube {−1, 1} n to the continuous hypercube [−1, 1] n , simply by evaluating the above expression for x i taking values in [−1, 1]. In what comes next, given a function f : C n → R, we will allow ourselves to also use the notation f for the corresponding function defined on the continuous cube C n := [−1, 1] n . Given this definition, it is now straightforward to check the identity In other words, we can replace the random point N x,ρ (which we think of as a noisy version of the point x) with the deterministic point ρx.
In light of this, we define µ n ρ to be the uniform measure on the set {− √ ρ, √ ρ} n = √ ρC n .
Using this definition, we observe that Moreover, observe that where is the negative of the binary entropy function. This implies that Conjecture 3 is equivalent to the fact that the quantity h(f (x))dµ n ρ (x) − h f (x)dµ n ρ (x) is maximized by dictator functions.

Generalization of the notion of noise
This point of view, and in particular equation (2), leads to the following generalization of the notion of noise: Given a symmetric probability measure ν on [−1, 1], we consider its n-fold tensor power, ν n , a measure on C n , and define so that, by (2), we have Stab ρ (f ) = Stab µ n ρ (f ). With this definition, we also get that Due to this identity, inequalities regarding the classical noise stability can be alternatively proven for the quantity Stab ν (f ) as long as ν is chosen with the correct variance. Next, we consider a more general notion of noise stability as follows: Let ϕ : [0, 1] → R be convex and define Using this definition, Fact 1 is equivalent to the fact that S x→x 2 ,µ n ρ is maximized for the dictator function, and Conjecture 3 is equivalent to the statement that S h,µ n ρ is maximized for the dictator function, when h is the binary entropy function.

Our results
In this work, we will construct a family of measures ν t for which extremality of the dictator and majority functions seems to arise naturally. We will first show the following variant of Conjecture 3: Theorem 4. Let ϕ : [0, 1] → R be convex and t ∈ (0, ∞). Among all Boolean functions f : C n → {0, 1}, the function which maximizes the quantity S ϕ,νt is the dictator function.
Let us emphasize that Theorem 4 does not imply Conjecture 3, since, in line with the above discussion and as will become immediately apparent, ν t = µ n ρ , for any t ∈ (0, ∞) and ρ ∈ (0, 1). Moreover, the fact that Theorem 4 deals with a different noise model has one striking consequence, it holds for arbitrary convex functions. The analogous result, in the setting of Conjecture 3, is known to be false. For example (see [15]), if ϕ(x) = x k for some k ≫ 2 n , and f is the dictator function, then S x→x k ,µ n p (Maj n ) > S x→x k ,µ n p (f ). In this regard, the measures ν t can be viewed as a natural family of measures for which dictators maximize all generalized notions of noise stability simultaneously. This property is reminiscent of results in Gaussian space, proven in [11]. In particular, [11,Theorem 5.1] is another variant of Conjecture 3, with respect to standard Gaussian and the Ornstein-Uhlenbeck semigroup, and which holds for arbitrary convex functions.
While ν t is an alternative noise model, as discussed above, identity (4) allows transferring noise stability bounds, with respect to ν t , to the classical noise model, which leads us to our next result. Our second goal in this work will be to give an upper bound for Stab νt (g) given an upper bound on MaxInf(g). This will imply a quantitative strengthening of Theorem 2. We prove our result for non-balanced functions. In this case, the quantity 1 4 + 1 2π arcsin(ρ) in Theorem 2 should be replaced by the Gaussian noise stability Λ ρ (E [g]). This function is defined by, where With the above definition, we show: The original proof of Theorem 2, in [13], gave the quantitative bound Another proof, based on induction over the dimension, appears in [2], with a similar logarithmic dependency. Thus Theorem 5 should be seen as a quantitative improvement of Theorem 2, which affords polynomial bounds. There are also several generalizations of the majority is stablest theorem which appear in the literature, such as [3], [9] and [12]. It would be interesting to see if our technique is also applicable in those settings.
Acknowledgements: Work on this paper was initiated at the Simons institute's "Probability, Geometry, and Computation in High Dimensions" program. We thank the institute for its hospitality and the program's participants for contributing ideas to the polymath project from which this work eventually developed. We owe a special debt of gratitude to Joe Neeman, for many discussions and for taking an active part in the early stages of this work.

Stochastic constructions
At the center of this work is a stochastic process to sample bits. To motivate the construction, let us begin with the standard Brownian motion. Suppose we would like to sample a uniformly random bit X ∈ {−1, +1} in a continuous incremental fashion. One approach would be to run a Brownian motion starting at 0 and output whichever of {−1, +1} the Brownian motion reaches first. Specifically, if we define a stochastic process, for standard Brownian motion B(t) on R, stopping the walk when it reaches {−1, +1}. This stochastic construction has the property that the expected variance of the output bit drops linearly with time. Specifically, the variance of the output bit, namely X(∞), satisfies the following stochastic differential equation, In other words, Var[X(∞)|X(t)] has a constant drift dt along with a martingale term. Intuitively, the process leaks variance at a constant rate. The stochastic process we consider is obtained by requiring that it leaks information (as measured by Shannon entropy) at a constant rate. Formally, consider the following stochastic differential equation: If H(X(∞)|X(t)) denotes entropy, then it satisfies the stochastic differential equation with a constant drift, namely, and the information leaks at a constant rate. It is not difficult to see that the above stochastic process is the unique martingale for which the entropy leaks at a constant rate. In higher dimensions, the natural generalization is to use an independent copy of the process for each coordinate. Formally, let B(t) be a standard Brownian motion in R n , and consider the martingale defined by the following stochastic differential equation: where σ t is the diagonal matrix with We call the process X t a renormalized Brownian motion for reasons that will become more apparent later on. We note at this point that which means that each coordinate is moving at a speed proportional to its remaining variance. As we will see later on, the behavior of f (X(t)) will be related to moments of the law of X i (∞)|X i (t), pushed forward by the map σ −1 t . The choice of σ t ensures that this measure is isotropic, which will play a key role in our proof.
This measure will correspond to our main notion of noise in view of equations (4) and (6). A calculation gives the following, Lemma 6. One has, for all t ≥ 0, Proof. By Itô's formula, we have dX Fix a function f : C n → [0, 1] (which later on will be a Boolean function). At the center of our analysis is the process This process is associated with noise stability via the relation which, using (8), gives Moreover, we have, by definition, These two identities will allow us to analyze noise stability and its generalization through the analysis of this process. An important property of the process is the following: Proof. Note that N t is a multilinear function of the martingale X 1 (t), ..., X n (t). Since those are independent martingales, every product of a subset of these processes is a martingale.
In section 7 we detail some further properties of the process X(t), which shall prove useful in the proofs to come.
Let us now introduce the main idea of our approach. In brief, our technique relies on comparing the evolution of the martingale N t to another martingale M t , a so-called model process. The process M t will be constructed in a problem-dependent way, a process corresponding to the dictator function in the proof of Theorem 4 and a process in Gaussian space for Theorem 5. At the heart of our proof is a coupling between the processes, used in [4], whose existence is ensured by the following proposition. Proposition 8. Let (M t ) t≥0 and (N t ) t≥0 be continuous martingales (defined on different probability spaces) such that M 0 = N 0 . Then, these two processes can be defined over the same probability space, along with a process (W τ ) τ ≥0 such that W τ is a standard Brownian motion with starting condition W 0 = M 0 and such that, almost surely, Proof. By invoking the Dambis / Dubins-Schwartz theorem, one may define a Brownian motion (W τ ) τ ≥0 over the same probability space as M t , which satisfies M t = W [M ]t for all t ≥ 0. The same can be done for the process N t yielding a Brownian motionW t . Finally, the four processes can be defined over one probability space in a way that W τ =W τ almost surely by invoking [4, Theorem 10].

A variant of the Courtade-Kumar conjecture
In this section we prove Theorem 4. We begin by defining a model process M t and establishing a comparison principle.
Comparison with dictators: Let f (x) = 1{x i > 0} be the dictator function and let g : C n → {0, 1} be a balanced Boolean function. That is, gdµ n = 1 2 . Consider the martingales N t = f (X(t)), M t = g(X(t)), whereX(t) denotes a process having the same distribution as that of X(t) but which lives on a different probability space.
The proof of Theorem 4 will proceed by comparing the evolution of the processes N t and M t . The next claim will be our main vehicle for the comparison.
The inequality is a consequence of the following version of Parseval's inequality, which we shall prove below: Rearranging the terms in (12) gives: which is the desired claim when x =X(t). To prove (12) note that, as g is multilinear extension and since X t is a martingale, and Y := X(∞)|X(0) = x is supported on {−1, 1} with P (Y = 1) = 1+x 2 , as in Lemma 16. For A ⊂ [n], define the biased characters,

The set {χ A } A⊂[n] is orthonormal with respect to the law of Y and induces the Fourier decom-
Thus, from orthonormality we deduce the following identity, Similarly, by rewriting ∂ i g in terms of the Fourier coefficients, e.g. as in [14, Equation (8.7)], Combining the last two identities, noting that E [g(Y ) 2 ] = E [g(Y )] = g(x), and applying Parsevel's inequality, we obtain (12).
We are finally ready to prove the variant of the Courtade-Kumar conjecture.
Proof of Theorem 4. Apply Proposition 8 to the processes M t and N t defined in the previous section, so that Let T 1 (·), T 2 (·) be the inverse of the non-decreasing functions t → [M] t and t → [N] t respectively. Consider the stopping time, Then for all 0 ≤ τ ≤ τ max , we have by (13) that

An application of Claim 9 gives
By integrating this inequality, we have T 1 (τ ) ≤ T 2 (τ ), almost surely, for all 0 ≤ τ ≤ τ max . Now for a fixed t 0 ≥ 0 set T 1 = [M] t 0 , T 2 = [N] t 0 . By the above, we have almost surely that T 1 ≥ T 2 . If ϕ is convex, by Jensen's inequality we have, This completes the proof.

Majority is stablest
In this section we prove Theorem 5. The proof relies on the same kind of coupling as the one used in the previous section, but the process M t will be different -it will correspond to the majority function rather than to dictator. In fact, in light of the central limit theorem, we may define M t in a way that mimics a corresponding one-dimensional version of the process on Gaussian space. In what comes next, we work with the processes X(t) and N t , defined as in section 2.

The model process
Denote by Φ : R → R the standard Gaussian cumulative distribution function (CDF), with Φ −1 its inverse and Φ ′ the standard Gaussian density. Define the Gaussian isoperimetric profile. Define the process N t to be the unique martingale satisfying, This process was introduced in [4], to study Gaussian noise stability, as defined in (7). We use the following identity, which connects between the quadratic variation of N t and Gaussian noise stability (see [4, Section 2.3] for the derivation).
The representation in Lemma 10 allows to deduce Lipschitz bounds on Λ.

Level-1 inequality
The next ingredient in the proof will be an analogue of Claim 9. In other words, we would like to show that, in a sense, the process N t moves faster than the process M t , thus accumulating more quadratic variation. However, in this case, the situation is substantially more involved, as we know that the process assigned with the dictator function actually moves faster than the process associated with the majority function (this is essentially the content of Claim 9).
It turns out that as long as the condition ∇f (X(t)) ∞ = o(1) holds, the majority function has the largest quadratic variation. This is the content of the following theorem.
Using Itô's formula, we have which immediately implies the bound In order to be able to apply this theorem, we will have to somehow argue that the process κ t (defined in its formulation) is small enough. For this, we will need a variant of the hypercontractivity inequality that holds for our notion of noise. We will use it to prove the following bound, for a noisy version of g.
The two above bounds will be proven in Sections 5 and 6, respectively.

Proof of Theorem 5
We now have all the ingredients we need in order to obtain the improvement of the majority is stablest theorem. We first fix ε > 0 to be some small number, and consider the noisy function g ε := T e −ε g. Note that E µ n [g ε ] = E µ n [g] and that MaxInf(g ε ) ≤ MaxInf(g). Thus, with a slight abuse of notation, we consider the process with respect to the noisy function N t := g ε (X(t)). We shall deduce noisy stability bounds for g ε , which, in turn, will imply a similar inequality for g.
We apply Proposition 8 in order to define the processes M t and N t on the same probability space, along with a Brownian motion (W τ ) τ ≥0 , such that Equations (14) and (16) give where κ t is defined as in (15). Our objective is to integrate those two inequalities while applying Lemma 13 to ensure that κ t is small. Let β > 0 be a constant whose value will be chosen later. Consider the stopping times Let T (t) be the inverse of the monotone increasing function t → [M] t . Then, by the chain rule, we have for all t ≤ τ ′ ∧ τ , where we used the fact that I(·) ≤ 1 and κ t ≤ 1 almost surely. It follows that, whenever t ≤ τ ∧ τ ′ , Moreover, note that where we use the fact that I(s) ≥ s(1 − s). Combining the two last displays gives To bound P(t > τ ), we apply Lemma 13 with α = κ 1 β , and choose β = 4e −t +5 4e −t , so that, Coupled with the previous computation, we obtain, Now, by Definition of g ε , and since T · is a self-adjoint semigroup, we have, Thus, since the above is true for any ρ and ε, from the relation (9), we see provided that e 2ε ρ < 1. This observation, along with Lemma 10, then gives, where the second inequality is the Lipschitz bound from Lemma 11. Choose now ε = κ 1 12β and assume ε ≤ 1 8 ln( 1 ρ ) to get for some universal constant C > 0. Finally, since t = log 1 1−ρ , and since we have made the choice β = 4e −t +5 4e −t = 9−4ρ 4−4ρ , we have, which finishes the proof.

Level-1 inequalities
Our goal in this section is to prove Theorem 12. To this end, we will first prove a level-1 inequality for isotropic product measures.

Moreover,
Before delving into the proof of Theorem 14, let us first begin with a technical Lemma.
Lemma 15. Let η be a measure on R n and let m : R n → [0, 1]. Fix θ ∈ R n and let α ∈ R be such that when α ≥ 0, and, Proof. Observe that with the above choice of α, which completes the proof.
We are now ready to show our level-1 inequality for isotropic product measures.
Proof of Theorem 14 (1). By Lemma 15, we have, where ν denotes the push-forward ofξ t under the map x → x, θ and α satisfies: when α ≥ 0, and the reverse inequality when α < 0. We continue the proof assuming α ≥ 0.
The proof when α < 0 is analogous, and there is no loss of generality.
We denote the CDF of ν by F ν (t) := ν ({x|x ≥ t}) and its quantile function by Q ν (t) := sup {x ∈ R|t ≥ F ν (x)}. Now, let T := Q ν • Φ. It is readily verified that T is non-decreasing and that T (z) has the law ν if z is a Gaussian.
Moreover, if x ∈ R is such that T (x) ≥ α, then x ≥ Φ −1 (vol(S)). Indeed, by the definition of Q ν , we have, where the second implication is (17). So, with a change of variables, where the equality uses integration by parts. Thus, to finish the proof, we need to bound Observe that since T is monotone, it is a derivative of a convex function. Hence, by [18,Theorem 9.4], T is the optimal-transport map from γ to ν. In other words, where W 2 stands for the quadratic Wasserstein distance (see [18] for further details on optimal transport). To bound W 2 , we shall invoke known results about the central limit theorem.
Substituting in (18), we conclude that, θ, y S(y)dξ(y) ≤ I(vol(S)) + C max Proof of Theorem 14 (2). Fix w = y · S(y)dξ(y) and let θ = w/ w 2 . Then using (21), If w 2 ≤ I(vol(S)) then the claim is obvious. Without loss of generality, assume w 2 ≥ I(vol(S)), which implies that, Now we are finally ready to wrap up the proof of Theorem 12.
Proof of Theorem 12. Let ξ t be the law of X(∞)|X(t) and letξ t be the push forward of ξ t under the linear map L(x) = σ −1 t (x − X(t)). By Lemma 16ξ t is isotropic, it is centered and its covariance matrix is the identity. The martingale property of X(t) also implies that for i = 1, . . . , n, Thus, a straightforward calculation shows, where S = g •L −1 . We will now apply the level-1 inequality (Theorem 14) for isotropic product measures on the distributionξ t . To this end, we begin by calculating the fourth moment of the coordinates of Y ∼ξ t .
Now using Theorem 14 on the distributionξ t and the function S = g • L −1 , we get the desired claim.
6 Influences remain small This section aims to show that influences remain small, with high probability, over the paths of X(t). Recall that we are dealing with g ε , a noisy version of g. In particular, g ε has the following Fourier expansion, Proof of Lemma 13. From the representation in (22) it is readily seen, where the inequality follows since x 2 e −2x ≤ 1.
The first inequality is hypercontractivity, Lemma 17, applied to T e −ε g. Hence, by first applying a union bound and then Doob's maximal inequality to the submartingales |∂ i g ε (X s )| 2+ e −t 2 , P max s∈[0,t],i∈[n]

Further properties of the noise process
This section records several useful properties of the process X(t). Recall that the process satisfies the following SDE: where B t is a standard Brownian motion in R n and σ t is the diagonal matrix with (σ t ) i,i := (1 + X i (t))(1 − X i (t))1 |X i (t)|≤1 .
Let us prove an immediate consequence of the definition, which shall also explain the choice of matrix σ t .
The first inequality uses the induction hypothesis on the uni-variate affine function, X n (t)f ′ (X(t))+ f ′′ (X(t)), whenX(t) is fixed. Similarly, the third inequality is the induction hypothesis applied to the multi-linear function X n (∞)f ′ (X(t)) + f ′′ (X(t)), when X n (∞) is fixed. The second inequality is Minkowski's integral inequality.
The second inequality holds since g is non-negative and the last inequality follows from the fact that X(∞) ∈ {−1, 1} almost surely.