=== PAGE 1 ===
UC Irvine
UC Irvine Electronic Theses and Dissertations
Title
The Poincaré Inequality on the Hamming Cube for Vector-Valued Functions
Permalink
https://escholarship.org/uc/item/2wv0w7cz
Author
Stone, Yonathan
Publication Date
2025
Copyright Information
This work is made available under the terms of a Creative Commons Attribution License, 
available at https://creativecommons.org/licenses/by/4.0/
 
Peer reviewed|Thesis/dissertation
eScholarship.org
Powered by the California Digital Library
University of California

=== PAGE 2 ===
UNIVERSITY OF CALIFORNIA,
IRVINE
The Poincar´e Inequality on the Hamming Cube for Vector-Valued Functions
DISSERTATION
submitted in partial satisfaction of the requirements
for the degree of
DOCTOR OF PHILOSOPHY
in Mathematics
by
Yonathan Benjamin Edward Stone
Dissertation Committee:
Professor Paata Ivanisvili, Chair
Professor Roman Vershynin
Professor Knut Solna
Professor Hamid Hezari
2025

=== PAGE 3 ===
© 2025 Yonathan Benjamin Edward Stone

=== PAGE 4 ===
DEDICATION
To Nancy, Rae, Sally, Linda, Milena, Robin and Cerberus.
ii

=== PAGE 5 ===
TABLE OF CONTENTS
Page
LIST OF FIGURES
iv
ACKNOWLEDGMENTS
v
VITA
vi
ABSTRACT OF THE DISSERTATION
vii
1
Introduction
1
2
Banach spaces of KKL and Rademacher type
4
2.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.3
Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.3.1
Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.3.2
Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.3.3
Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.4
Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3
Sharpening the Gap between L1 and L2 Norms
21
3.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.1.1
Separating first and second moments . . . . . . . . . . . . . . . . . .
21
3.1.2
An application to exponential sums . . . . . . . . . . . . . . . . . . .
23
3.1.3
An application to L1 Poincar´e inequality on the hypercube . . . . . .
24
3.2
Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.1
The proof of Theorem 4
. . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.2
The proof of C(4, 6) = 1/3 . . . . . . . . . . . . . . . . . . . . . . . .
35
3.2.3
The proof of Corrollary 2 . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.2.4
The proof of Corrollary 3 . . . . . . . . . . . . . . . . . . . . . . . . .
36
4
An Optimization Problem concerning Binomial RVs
38
4.1
Sums of Biased Rademachers
. . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.2
Preliminary computations
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.3
Summary of Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.4
Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
iii

=== PAGE 6 ===
LIST OF FIGURES
Page
4.3.1 Sn(p) for n = 1, 2, 3, 4 and 0 ≤p ≤1
. . . . . . . . . . . . . . . . . . . . . .
42
4.3.2 SNp(p) for 0 ≤p ≤1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
iv

=== PAGE 7 ===
ACKNOWLEDGMENTS
I would like to thank all the friends I’ve made while living in California, both in and outside
of UCI. You all were instrumental to my well-being over the last six years and I will miss
you all dearly once I move to Wisconsin.
I am also extremely grateful towards my family for constantly encouraging to push my
learning further and further, and always being there to support me.
It is also important for me to express my thanks towards all the faculty members in the UCI
math department who have been supportive and helpful throughout the years, but especially
so my advisor. Life has presented a lot of challenges outside of school itself during the last
few years, and I could not have asked for someone more kind, patient and understanding of
this. While the PhD itself is coming to a close, I think I will take Paata’s lessons and advice
about prioritizing myself and my physical and mental health with me for the rest of my life.
v

=== PAGE 8 ===
VITA
Yonathan Benjamin Edward Stone
EDUCATION
Doctor of Philosophy in Mathematics
2025
University of California, Irvine
Irvine, CA
Master of Science in Mathematics
2021
University of California, Irvine
Irvine, CA
Bachelor of Arts in Liberal Arts
2019
New College of Florida
Sarasota, Florida
RESEARCH EXPERIENCE
Graduate Research Assistant
2021-2025
University of California, Irvine
Irvine, California
TEACHING EXPERIENCE
Teaching Assistant
2019-2025
University of California, Irvine
Irvine, CA
Instructor of Record
Summers 2023 and 2024
University of California, Irvine
Irvine, CA
PUBLICATIONS
The KKL inequality and Rademacher type 2
Discrete Analysis 2024:2
Joint work with P. Ivanisvili
Sharpening the Gap Between L1 and L2 norms
arXiv preprint
Joint work with P. Ivanisvili
vi

=== PAGE 9 ===
ABSTRACT OF THE DISSERTATION
The Poincar´e Inequality on the Hamming Cube for Vector-Valued Functions
By
Yonathan Benjamin Edward Stone
Doctor of Philosophy in Mathematics
University of California, Irvine, 2025
Professor Paata Ivanisvili, Chair
We study variations of and improvements to the classical Poincar´e inequality on the Ham-
ming cube. The restriction to the discrete setting of the latter has neccessitated the develop-
ment of many specialized techniques, including heat semigroup methods, hypercontractivity,
and many other probabilistic ideas to address questions initially more rooted in analysis.
This thesis covers a few such improvements including: 1. A complete characterization of Ba-
nach spaces for which a vector-valued variant of the KKL inequality holds, including partial
work towards extending an improvement due to Talagrand to the same setting. 2. Improved
bounds on the ratio and difference of L1 and L2 norms of sums of biased Rademacher random
variables, with applications to various unanswered questions regarding the subject.
vii

=== PAGE 10 ===
Chapter 1
Introduction
Whenever mathematicians explore a new setting in which there is some notion of a metric
and of derivatives, there comes a point in time where they will try to prove some variant of
Poincar´e inequality. Recall that in its most classical formulation, given 1 ≤p < ∞and
Ωa nice bounded domain in Rn, there exists a universal constant C(p, Ω) > 0 such that for
any smooth function u : Ω7→C for which
R
Ωu = 0 it holds that
∥u∥Lp(Ω) ≤C∥∇u∥Lp(Ω).
Beyond this variants of this inequality, requiring perhaps some small modifications, can be
proven in a number of diverse settings. The 3 key results being presented in this thesis all
represent attempts to improve on the Poincar´e inequality specifically of functions u defined
on a discrete hypercube taking values in a Banach space.
Let us first recall what this version of the aforementioned inequality looks like. Let Ω=
{−1, 1}n be the discrete hypercube where a typical element ε = (ε1, ε2, ..., εn) is a string of
1’s and -1’s. Equipping Ωwith the uniform probability measure and considering a function
1

=== PAGE 11 ===
f : Ω7→X, where X is a normed space, we can then define its Lp-norm as
∥f∥p := (E∥f∥p
X)1/p .
and its j-th discrete partial derivative as
Djf(ε) = f(ε1, ..., εj, ..., εn) −f(ε1, ..., −εj, ..., εn)
2
,
that is, Djf(ε) encodes how sensitive the function f is to the j-th bit in ε being changed from
-1 to 1 or vice-versa. For the case where X = C, the classical discrete Poincar´e inequality
can then be formulated as
∥f −Ef∥2 ≤
 n
X
j=1
∥Djf∥2
2
!1/2
.
In Chapter 2, we will explore one such improvement due to Kahn, Kalai, and Linial [8] from
1988, often abbreviated to the KKL inequality, which adds an additional logarithmic factor
to the inequality above. We widen the setting of the functions in question to those taking on
values in Banach spaces and give a full characterization of what it means for a suitable for-
mulation of the KKL inequality to be true for a Banach space using heat semigroup methods.
We also present versions of these results for general Lp norms as well as find assumptions
under which KKL on Banach spaces could be improved even further.
In Chapter 3, we return to the real numbers and move in a slightly different direction, es-
tablishing a sharp upper bound on the ratio between L2 and L1 norms of Borel measurable
random variables X. More specifically, we show that this gap can bounded above by a func-
tion of the gap between the Lp and L2 norms of ξ and the Lq and L2 norms of ξ for any
q > p > 2. We also show applications of this result to Bourgain’s question on exponential
sums [16] as well as the L1 Poincar´e inequality on the hypercube.
2

=== PAGE 12 ===
In Chapter 4, we examine a special case of the weighted sums of Rademacher random vari-
ables highlighted in the applications sections of Chapter 3 and attempt to find a sharp
upper bound on the ratio of L2 to L1 norms of these random variables. While the general
case of arbitrary weights has proven elusive thus far, we do find a sharp constant specif-
ically concerning the subcase of binomial distributions. What is ultimately proven is the
exact number of Bernouilli trials needed to maximize this ratio of norms given a prescribed
success probability p.
3

=== PAGE 13 ===
Chapter 2
Banach spaces of KKL and
Rademacher type
2.1
Introduction
One of the central results in the analysis of Boolean functions is an estimate due to Kahn,
Kalai, and Linial from 1988 [8]. For n ≥1, consider the discrete hypercube {−1, 1}n equipped
with the uniform probability measure. Set ε = (ε1, . . . , εn) ∈{−1, 1}n. For any Boolean
function f : {−1, 1}n →{−1, 1} with variance Var(f) = E|f −Ef|2 = δ > 0 one has
max
1≤j≤n Infj(f) ≥C(δ)log(n)
n
,
(2.1.1)
where Infj(f) := P(f(ε)̸ = f(ε⊕j)), ε⊕j := (ε1, . . . , −εj, . . . , εn), and the positive constant
C(δ) depends only on δ. In fact one can take C(δ) = δ/5. The quantity Infj(f), also called
the influence of the Boolean function f in the j’th coordinate, measures how influential the
4

=== PAGE 14 ===
j’th variable (or j’th voter) is towards the outcome of f. Clearly, if Infj(f) = 0, then f does
not depend on the j’th variable at all.
Perhaps the most striking application of the inequality (2.1) is that for any monotone Boolean
function f, that is, one for which f(ε) ≤f(ε′) whenever εj ≤ε′
j for all j = 1, . . . , n, and for
which Ef ≥−0.99, one can take O (n/ log(n + 1)) variables to be 1, resulting in the average
of f with respect to the remaining variables being larger than 0.99 (see Proposition 9.27 in
[10]). In social choice, this means that in a monotone election between two candidates, if
the first candidate (corresponding to “−1”) wins the election on average, then the second
candidate can bribe O(n/ log(n + 1)) votes to instead win the election on average.
Working with Boolean functions one is likely to fall into the trap of assuming a lot of the
phenomena observed in (2.1) are combinatorial in nature. Notice that the classical Poincar´e
inequality
E|f −Ef|2 ≤
n
X
j=1
E|Djf|2,
(2.1.2)
for all f : {−1, 1}n →R, where Djf(ε) = f(ε)−f(ε⊕j)
2
, implies a weak version of (2.1), i.e.,
for any Boolean f : {−1, 1}n →{−1, 1} there exists j ∈{1, . . . , n} such that Infj(f) =
E|Djf|2 ≥E|f −Ef|2/n.
By all accounts, Talagrand
[24] was the first to discover a more extreme version of this
inequality, which itself implies existence of a universal constant K ∈(0, ∞) such that
E|f −Ef|2 ≤
K
log

e/ maxk
E|Dkf|
√
E|Dkf|2

n
X
j=1
E|Djf|2
(2.1.3)
holds for all real-valued functions f : {−1, 1}n →R. We should point out that (2.1.3) is
5

=== PAGE 15 ===
the version of this estimate that is used in all applications we are aware of. It also improves
the Poincar´e inequality (2.1.2) by a logarithmic factor, and can also be used to recover (2.1)
when applied to Boolean functions. The inequality (2.1.3) for Boolean functions, although
never stated in this form, follows from the arguments of the original paper of Kahn–Kalai–
Linial [8], and as such we will henceforth refer to (2.1.3) as the KKL inequality.
The main advantage of the estimate (2.1.3) over the original Boolean corollary (2.1) is that
it can be restated when the target space of the function is taken to be an arbitrary metric
space.
Definition 2.1.1. We say a metric space (X, d) is of KKL type if there exists a universal
constant T ∈(0, ∞) such that the inequality
Ed(f(ε), f(ε′))2 ≤
T 2
log

e/ max
k
Ed(f(ε),f(ε⊕k))
√
Ed(f(ε),f(ε⊕k))2

n
X
j=1
Ed(f(ε), f(ε⊕j))2
(2.1.4)
holds for every n ≥1, and for every function f : {−1, 1}n →X, where ε′ is the independent
copy of ε. The best such T in (2.1.4) is denoted by TKKL(X).
Thus an analogous statement to (2.1) can be formulated without relying on the linear struc-
ture of the target space X one has when working with normed spaces. The translation of
phenomena involving a linear structure to fit spaces endowed only with metrics lies at the
foundation of Ribe program [9] which was inspired by Ribe’s rigidity theorem [11], and was
initiated by Bourgain [4].
This paper seeks to provide a complete description of normed spaces which are of KKL type.
It is straightforward to see that a normed space (X, ∥· ∥) that is of KKL type must also be
of Rademacher type 2 (or just type 2), meaning there exists a constant T ∈(0, ∞) such that
6

=== PAGE 16 ===
for all x1, ..., xn ∈X we have that
E



n
X
j=1
εjxj



2
≤T 2
n
X
j=1
∥xj∥2.
(2.1.5)
The best constant T in (2.1.5) is denoted by T2(X).
A recent paper [7] showed that normed spaces of type 2 must satisfy the Poincar´e inequality
(2.1.2), resolving a long-standing conjecture in Banach space theory due to Enflo. Soon after,
Eskenazis and Cordero-Erausquin showed [6] that for type 2 spaces there was a variant of
the KKL inequality (2.1.3) including an additional doubly logarithmic factor, which meant
that (2.1) could not be recovered from this.
An instructive example, which serves as a
“self-checker” for whether any given new functional inequality bounding the variance of a
function f by its discrete derivatives can ever recover (2.1) is the tribes function ftribe :
{−1, 1}n 7→{−1, 1}, which has the properties: E(Pn
j=1 Infj(f))α ≍logα(n) for any α > 0;
maxj=1,...,n Infj(ftribe) = Inf1(ftribe) ≍log(n)
n
; Var(ftribe) ≍1 (see [3]). Notice that for the
tribes function the right hand side of (2.1.3) is of constant order as n →∞.
In this paper we show that KKL type and Rademacher type 2 coincide.
Theorem 1. For any normed space (X, ∥· ∥), we have
T2(X)/2 ≤TKKL(X) ≤2e
√
2π T2(X).
It will follow from the proof of Theorem 1 that if one manages to obtain bounds ∥Djf∥2 ≤
bj, ∥Djf∥1 ≤aj for some nonnegative numbers aj, bj with aj ≤bj, j = 1, . . . , n, then the
following inequality holds
∥f −Ef∥2 ≤
2e
√
2π T2(X)
log(e/ maxj(aj/bj))
 n
X
k=1
b2
k
!1/2
,
(2.1.6)
7

=== PAGE 17 ===
where T2(X) is the type 2 constant of the normed space X.
The inequality, as written in (2.1.6), applied to real-valued functions was critical (see Chapter
5 in [5]) to obtaining sublinear bounds on the variance in the first passage percolation model
[2].
One may wonder whether there is an analog of Theorem 1 for normed spaces of type p, for
p ∈[1, 2]. Recall that the normed space (X, ∥· ∥) is of type p, p ∈[1, 2], if there exists a
positive constant T such that
E





n
X
j=1
εjxj





p
≤T p
p
n
X
j=1
∥xj∥p
(2.1.7)
holds for all n ≥1, and all x1, . . . , xn ∈X. The best constant T in (2.1.7) is denoted by
Tp(X).
Theorem 2. If a normed space (X, ∥· ∥) is of type p, then we have
∥f −Ef∥p ≤
2e
√
2π Tp(X)
q
log(e/ max(aj
bj ))
 n
X
k=1
bp
k
!1/p
(2.1.8)
for any n ≥1, any f : {−1, 1}n →X, and any nonnegative numbers {aj, bj}n
j=1, bj ≥aj
with ∥Djf∥1 ≤aj, ∥Djf∥p ≤bj, j = 1, . . . , n.
Our third theorem investigates Talagrand’s inequality for normed spaces of type 2. Theorem
1 in [6] says that if X is of type 2 then
∥f −Ef∥2 ≤C
√ε


n
X
j=1
∥Djf∥2
2
log1−ε ∥Djf∥2
∥Djf∥1


1/2
(2.1.9)
holds for all ε ∈(0, 1) and all f : {−1, 1}n 7→X, where C depends only on the type 2
constant of X. It is an open problem whether one can remove ε in the statement of the
8

=== PAGE 18 ===
inequality (2.1.9), i.e., remove the constant
1
√ε and take ε = 0 in the power of the logarithm.
In this direction we make the following improvement.
Theorem 3. Let h ≥0 be nondecreasing with 0 <
R ∞
1 h(t)dt
t2 < ∞and X a normed space
of type 2. Then
∥f −Ef∥2 ≤12 T2(X)
Z ∞
1
h(t)
t2 dt
1/2


n
X
j=1
∥Djf∥2
2
h

log ∥Djf∥2
∥Djf∥1



1/2
(2.1.10)
holds for all f : {−1, 1}n →X and all n ≥1.
The choice h(t) = t1−ε recovers (2.1.9). One can consider more sophisticated examples such
as h(t) =
t
log1+ε(2+t) or h(t) =
t
log(2+t)(log log(10+t))1+ε for any ε > 0.
It is worth noting that if a normed space X satisfies (2.1.10) for some h as above, then by
considering linear functions f(ε) = P
i εixi, we see that X must be of type 2.
2.2
Background
Consider the space of vector-valued functions f : {−1, 1}n →X, defined on the discrete
hypercube, for which (X, ∥· ∥) is a normed space. Define the Lp(X) norm on such functions
as
∥f∥p = (E∥f∥p)1/p =

1
2n
X
ε∈{−1,1}n
∥f(ε)∥p


1/p
.
It is often helpful to think about f in terms of its Fourier-Walsh expansion
f(ε) =
X
S⊂{1,...,n}
aSεS,
9

=== PAGE 19 ===
where
εS : (ε1, ..., εn) 7−→
Y
i∈S
εi,
ε∅≡1,
are called Walsh functions. A straightforward computation yields
aS = EεS · f
for all S ⊆{1, ..., n}.
Much of what we will prove in this paper relies on the rich theory of the heat semigroup on the
discrete hypercube. With the discrete derivative operators Dj defined as in the introduction,
define the discrete Laplacian ∆on functions f : {−1, 1}n →X as follows
∆f(ε) = −
n
X
j=1
Djf(ε).
We then define the heat semigroup Pt = e∆t as
Pt(f)(ε) =
X
S⊂{1,...,n}
aSe−|S|tεS
for all
t ≥0.
An important property satisfied by the heat semigroup is hypercontractivity[1]: for all p, q
satisfying 1 < p ≤q < ∞and e−2t ≤p−1
q−1, we have
∥Ptf∥q ≤∥f∥p.
(2.2.1)
One of the key ingredients in obtaining Theorem 1 is going to be the following pointwise
identity obtained in [7]. For a normed space (X, || · ||) and a function f : {−1, 1}n →X, we
have
−d
dtPtf(ε) =
1
√
e2t −1Eξ
n
X
j=1
δj(t)Djf(εξ(t)),
(2.2.2)
10

=== PAGE 20 ===
where εξ(t) = (ε1ξ1(t), ..., εnξn(t)), and the ξi(t) are i.i.d. random variables with
P{ξi(t) = ±1} = 1 ± e−t
2
,
and δi = ξi(t)−Eξi(t)
√
Var(ξi(t)).
2.3
Proofs
2.3.1
Proof of Theorem 1
The lower bound T2(X)/2 ≤TKKL(X) follows by applying (2.1.4) to linear functions f(ε) =
ε1x1 + . . . + εnxn and using the simple inequality E∥f −Ef∥2 ≤E∥f(ε) −f(ε′)∥2.
To get the upper bound in Theorem 1 we proceed as follows. Without loss of generality we
assume max1≤k≤n E∥Dkf∥> 0 otherwise f is constant and hence there is nothing to verify.
By applying (3.2.5) to the function Pt(f), and using the chain rule, we obtain
−d
dtP2tf(ε) =
2
√
e2t −1Eξ
n
X
j=1
δj(t)DjPtf(εξ(t)).
We then proceed by integrating both sides with respect to t and note that P0f = f, and
limt→∞Ptf = Ef. It follows that
f(ε) −Ef = 2 ·
Z ∞
0
Eξ
n
X
j=1
δj(t)DjPtf(εξ(t))
dt
√
e2t −1.
(2.3.1)
Next, we take L2 norms and apply both the triangle and Jensen’s inequality, which yields
∥f −Ef∥2 ≤2 ·
Z ∞
0

Eξ,ε





n
X
j=1
δj(t)DjPtf(ε · ξ(t))





2

1/2
dt
√
e2t −1.
11

=== PAGE 21 ===
Since (E∥f(ε) −f(ε′)∥2)1/2 ≤2∥f −Ef∥2, we will shift to exclusively obtaining upper
bounds on the right hand side (RHS) of the inequality above. Notice that (δ, ξε) has the
same distribution as (δ, ε). We thus replace ξε with ε via a change of variables, i.e.
∥f −Ef∥2 ≤RHS := 2 ·
Z ∞
0

Eξ,ε





n
X
j=1
δj(t)DjPtf(ε)





2

1/2
dt
√
e2t −1.
In addition, a symmetrization argument using Eδi(t) = 0 yields the following inequality
RHS ≤2 ·
Z ∞
0

Eξ,ξ′,ε,ε′





n
X
j=1
ε′
j(δj(t) −δ′
j(t))DjPtf(ε)





2

1/2
dt
√
e2t −1,
where δ′
j is a copy of δj depending on ξ′, which is an independent copy of ξ, and ε′ ∈{−1, 1}n
is an independent copy of ε. Since our normed space X is of type 2, applying the definition
to the average over ε′ we obtain
RHS ≤2T2(X) ·
Z ∞
0
 
Eξ,ξ′,ε
n
X
j=1
(δj(t) −δ′
j(t))2 · ∥DjPtf(ε)∥2
!1/2
dt
√
e2t −1.
(2.3.2)
Next, we have Eξ′,ξ(δj(t)−δ′
j(t))2 = 2, which we can plug into (2.3.2) to obtain the following
estimate
RHS ≤23/2 · T2(X) ·
Z ∞
0
 n
X
j=1
∥DjPtf∥2
2
!1/2
dt
√
e2t −1.
Moreover, the commutativity DjPt = PtDj along with hypercontractivity gives us
∥DjPtf∥2
2 ≤∥Djf∥2
1+e−2t.
It thus follows that
RHS ≤23/2 · T2(X) ·
Z ∞
0
 n
X
j=1
∥Djf∥2
1+e−2t
!1/2
dt
√
e2t −1.
12

=== PAGE 22 ===
By H¨older’s inequality, we have
∥Djf∥2
1+e−2t ≤∥Djf∥2θ
1 · ∥Djf∥2(1−θ)
2
≤∥Djf∥2
2 ·

max
k
∥Dkf∥1
∥Dkf∥2
2θ
,
(2.3.3)
where θ = 1−e−2t
1+e−2t. We have therefore obtained the following inequality
∥f −Ef∥2 ≤23/2 · T2(X) ·
 n
X
j=1
∥Djf∥2
2
!1/2
·
Z ∞
0

max
k
∥Dkf∥1
∥Dkf∥2
 1−e−2t
1+e−2t
dt
√
e2t −1. (2.3.4)
Let a := maxk
∥Dkf∥1
∥Dkf∥2 ∈(0, 1]. Since
1+e−t
1+e−2t ≥1 and
1
√
1+e−t ≤1, we have
Z ∞
0
a
1−e−2t
1+e−2t
dt
√
e2t −1 ≤
Z ∞
0
a1−e−t
e−tdt
√
1 −e−t ≤e ·
Z ∞
0
(a/e)1−e−t
e−tdt
√
1 −e−t,
Performing the substitution s =
p
(1 −e−t) log(e/a) then gives us
e ·
Z ∞
0
(a/e)1−e−t
e−tdt
√
1 −e−t =
2e
p
log(e/a)
Z √
log(e/a)
0
e−s2ds ≤
e√π
p
log(e/a)
,
whence the desired result follows immediately.
2.3.2
Proof of Theorem 2
The proof of Theorem 2 proceeds in the same way as the proof of Theorem 1, therefore, to
avoid repetitions we briefly sketch the argument. We take Lp norms in both sides of (2.3.1),
and apply the triangle and Jensen’s inequality, as well as the same symmetrization arguments.
By Cauchy–Schwarz, we have E|δj(t) −δ′
j(t)|p ≤2p/2. Then, using hypercontractivity and
H¨older’s inequality we obtain
∥DjPtf∥p
p ≤∥Djf∥p
1+(p−1)e−2t ≤bp
j

max
k
ak
bk
pθ
,
where
θ =
1 −e−2t
1 + (p −1)e−2t.
13

=== PAGE 23 ===
Finally notice that for any a ∈(0, 1] we have
Z ∞
0
a
1−e−2t
1+(p−1)e−2t
dt
√
e2t −1 ≤
Z ∞
0
a1−e−t
e−tdt
√
1 −e−t,
whence the rest of the proof proceeds verbatim as in Section 2.3.1.
Let us remark that the converse implication to Theorem 2 also holds true: if (X, ∥· ∥) is
an arbitrary normed space, and the inequality (2.1.8) holds with 2e
√
2π Tp(X) replaced by
some universal constant, then the normed space X must be of type p. Indeed, the conclusion
follows by choosing f = P
j εjxj and aj = bj = ∥xj∥.
2.3.3
Proof of Theorem 3
The first steps of the proof proceed along the same lines as in Theorem 1, except that we do
not take the maximum over k in (2.3.3). We thus end up with the following inequality:
∥f −Ef∥2 ≤
(2.3.5)
23/2 · T2(X) ·
Z ∞
0


n
X
j=1
∥Djf∥2
2 ·
∥Djf∥2
1
∥Djf∥2
2
 1−e−2t
1+e−2t


1/2
dt
√
e2t −1.
We then note that since 1−e−2t
1+e−2t ≥1 −e−t and ∥Djf∥1
∥Djf∥2 ≤1, as well as the fact that
1
√
e2t−1 ≤
e−t
√
1−e−t, we can bound the right hand side in (2.3.5) by
Z ∞
0
 n
X
j=1
∥Djf∥2
2 ·
∥Djf∥1
∥Djf∥2
1−e−t!1/2
e−tdt
√
1 −e−t.
14

=== PAGE 24 ===
Using this estimate, we can perform the substitution s =
√
1 −e−t, which allows us to
rewrite the integral above as
1
2
Z 1
0
 n
X
j=1
∥Djf∥2
2 ·
∥Djf∥1
∥Djf∥2
s2!1/2
ds.
Let us denote g(√s) = h(s). Note that our theorem is satisfied if we can show
Z 1
0
 X
j
∥Djf∥2
2 ·
∥Djf∥1
∥Djf∥2
s2!1/2
ds ≤
12
√
2
Z ∞
1
g(s)
s3 ds
1/2


n
X
j=1
∥Djf∥2
g

log1/2 ∥Djf∥2
∥Djf∥1.



1/2
.
(2.3.6)
Next, denote cj =
∥Djf∥2
2
g

log1/2 ∥Djf∥2
∥Djf∥1
, and Xj = ∥Djf∥1
∥Djf∥2 for all j = 1, . . . .n. Then, dividing both
sides of (2.3.6) by
 
nP
j=1
cj
!1/2
gives us the following:
Z 1
0




n
X
j=1




cj
nP
k=1
ck



· Xs2
j g(log1/2(1/Xj))




1/2
ds ≤12
√
2
Z ∞
1
g(s)
s3 ds
1/2
.
Viewing the
cj
n
P
k=1
ck
as probabilities, we can obtain the result above, and thus prove Theorem 3
immediately by proving the following:
Lemma 2.3.1. For all g ≥0 with
R ∞
1
g(t)
t3 dt < ∞, we have that
Z 1
0

E Xs2g(log1/2(1/X))
1/2
ds ≤(
√
2 + 8√π)
Z ∞
1
g(s)
s3 ds
1/2
(2.3.7)
for all random variables 0 ≤X ≤1.
To prove this, rewrite X = e−Y 2, where Y is a non-negative random variable. We thus have
15

=== PAGE 25 ===
that
Z 1
0

E Xs2g(log1/2(1/X))
1/2
ds =
Z 1
0

E e−(sY )2g(Y )
1/2
ds.
Now write pk = P(2k ≤Y < 2k+1) and use the fact that t 7→e−t2 is decreasing and t 7→g(t)
is nondecreasing for t ≥0, we get
Z 1
0

E e−(sY )2g(Y )
1/2
ds ≤
Z 1
0
 
g(1) +
∞
X
k=0
e−(s2k)2g(2k+1)pk
!1/2
ds.
Next, we partition the interval we are integrating over into intervals of the form (2−j, 2−j+1]
to get the following estimate
Z 1
0
 
g(1) +
∞
X
k=0
e−(s2k)2g(2k+1)pk
!1/2
ds ≤
∞
X
j=1
 
g(1) +
∞
X
k=0
e−22(k−j)g(2k+1)pk
!1/2
2−j.
Next, using subadditivity of the map t 7→
√
t and interchanging the sums we obtain
∞
X
j=1
 
g(1) +
∞
X
k=0
e−22(k−j)g(2k+1)pk
!1/2
2−j ≤
p
g(1) +
∞
X
k=0
p
g(2k+1)√pk
∞
X
j=1
e−22(k−j)
2
2−j.
(2.3.8)
Next, notice that
∞
X
j=1
e−22(k−j)
2
2−j ≤
∞
X
j=1
Z 2−j+1
2−j
e−(2kx)2
8
dx =
Z 1
0
e
−(2kx)2
8
dx = 2−k
Z 2k
0
e−y2/8dy,
16

=== PAGE 26 ===
where the estimate
R 2k
0 e−y2/8dy ≤
√
2π gives us that
∞
X
j=1
e−22(k−j)
2
2−j ≤
√
2π · 2−k,
for all k. Using this estimate on (2.3.8) gives us
p
g(1) +
∞
X
k=0
p
g(2k+1)√pk
∞
X
j=1
e−22(k−j)
2
2−j ≤
p
g(1) +
√
2π ·
∞
X
k=0
p
g(2k+1)2−k√pk.
However, notice that
∞
X
k=0
g(2k+1)2−2k ≤8
∞
X
k=0
Z 2k+1
2k
g(2t)
t3
dt = 32
Z ∞
2
g(s)
s3 ds,
and g(1) ≤2
R ∞
1
g(s)
s3 ds. We thus have by Cauchy-Schwarz that
p
g(1) +
√
2π ·
∞
X
k=0
p
g(2k+1)2−k√pk ≤(
√
2 + 8√π)
Z ∞
1
g(s)
s3 ds
1/2
.
which completes the proof of the lemma, and thus also the theorem.
2.4
Concluding remarks
One may wonder how sharp the bound obtained in Lemma 3.2.1 is. We can show that the
inequality (2.3.7) is sharp up to a multiplicative constant
Proposition 2.4.1. For any g ≥0 with
R ∞
1
g(t)
t3 dt < ∞there exists a random variable X,
17

=== PAGE 27 ===
0 ≤X ≤1, such that
Z 1
0

EXs2g(log1/2(1/X))
1/2
ds ≥e−8
2
Z ∞
1
g(s)
s3 ds

.
Proof. Let X = e−Y 2 and choose Y ≥0 so that pk = P(2k ≤Y < 2k+1) =
g(2k)2−2k
P∞
j=1 g(2j)2−2j for
all k ≥1. We have
Z 1
0

EXs2g(log1/2(1/X))
1/2
ds =
Z 1
0

Ee−(sY )2g(Y )
1/2
ds ≥
∞
X
j=1
Z 2−j+1
2−j
 ∞
X
k=0
e−(s2k+1)2g(2k)pk
!1/2
ds ≥
∞
X
j=1
 ∞
X
k=0
e−(2−j+k+2)2g(2k)pk
!1/2
2−j ≥
∞
X
j=1
e−8q
g(2j)pj 2−j = e−8
 ∞
X
j=1
g(2j)2−2j
!1/2
,
where we established the final inequality by considering only the k = j terms. On the other
hand
∞
X
j=1
g(2j)2−2j ≥
∞
X
j=1
Z 2j+1
2j
g(t/2)
t3
dt = 1
4
Z ∞
1
g(s)
s3 ds.
This finishes the proof of the proposition.
One may also wonder whether we can prove the following inequality.
Z ∞
0


n
X
j=1
∥Djf∥2
2 ·
∥Djf∥2
1
∥Djf∥2
2
 1−e−2t
1+e−2t


1/2
dt
√
e2t −1 ≤C


n
X
j=1
∥Djf∥2
2
log ∥Djf∥2
∥Djf∥1


1/2
(2.4.1)
with some universal finite constant C > 0. Notice that (2.4.1) combined with (2.3.5) would
solve the open problem regarding setting ε = 0 in (2.1.9). If the inequality (2.4.1) does not
18

=== PAGE 28 ===
hold then this would mean that one needs to come up with a different approach to prove or
disprove the inequality (2.1.9) without ε.
It was noted by the referee in [6] that if we treat bj := ∥Djf∥2
2, aj = ∥Djf∥2
1 as arbitrary
nonnegative numbers satisfying bj ≥aj ≥0, then the inequality (2.4.1) does not hold in
such generality. However, in general the numbers bj and aj may not be arbitrary, i.e., there
could be some relations between ∥Djf∥1 and ∥Djf∥2. For instance, for a Boolean function
f : {−1, 1}n →{−1, 1} we have bj = ∥Djf∥2
2 = ∥Djf∥1 = √aj for all j = 1, . . . , n.
Therefore, it is interesting to ask whether the inequality (2.4.1) holds in the “Boolean case”:
Z ∞
0
 n
X
j=1
b
1+ 1−e−2t
1+e−2t
j
!1/2
dt
√
e2t −1 ≤C′
 n
X
j=1
bj
log(1/bj)
!1/2
(2.4.2)
for all n ≥1 and all bj ∈[0, 1]. It turns out that:
Proposition 2.4.2. There is no finite universal constant C′ > 0 for which the inequality
(2.4.2) holds for all b1, . . . , bn ∈[0, 1] and all n ≥1.
Proof. Towards a contradiction, assume that (2.4.2) holds true.
We have b
1+ 1−e−2t
1+e−2t
j
≥
b1+2(1−e−t)
j
. Performing the substitution s =
√
1 −e−t the inequality (2.4.2) implies
Z 1
0
 n
X
j=1
b1+2s2
j
!1/2
ds ≤C
 n
X
j=1
bj
log(1/bj)
!1/2
.
(2.4.3)
It follows from homogeneity that for all Borel measurable random variable Y ≥0 we have
Z 1
0

Ee−Y 2−2(Y s)21/2
ds ≤C
 
Ee−Y 2
Y 2
!1/2
.
(2.4.4)
Next, choose Y so that it takes only the values 2k, k ∈Z with probabilities pk, i.e., P
k∈Z pk =
19

=== PAGE 29 ===
1. Also set pk = 0 for k ≤0. Then the right hand side in (2.4.4) takes the form
C
 X
k≥1
2−2ke−22kpk
!1/2
.
The left hand side in (2.4.4) we can lower bound as
∞
X
j=1
Z 2−j+1
2−j
 X
k≥1
e−22k−2(2ks)2pk
!1/2
ds ≥
∞
X
j=1
 X
k≥1
e−22k−2(2k−j+1)2pk
!1/2
2−j ≥e−4 X
j≥1

e−22jpj
1/2
2−j.
Denoting qj =

e−22jpj
1/2
2−j, j ≥1, we see that (2.4.4) implies the inequality P
j≥1 qj ≤
e4C(P
j≥1 q2
j)1/2, which by homogeneity (and slightly abusing notation) must hold for all
qj ≥0, resulting in the desired contradiction.
20

=== PAGE 30 ===
Chapter 3
Sharpening the Gap between L1 and
L2 Norms
3.1
Introduction
3.1.1
Separating first and second moments
Let F be a family of Borel measurable random variables.
For p > 0 denote ∥X∥p :=
(E|X|p)1/p. Assume ∥X∥2 = 1 for any X ∈F. Then the Cauchy–Schwarz inequality tells us
that ∥X∥1 ≤1. In this chapter our goal is to understand under what conditions on X there
exists ε > 0 such that
∥X∥1 ≤1 −ε
(3.1.1)
holds for all X ∈F.
The conditions on X should be such that one can easily verify them. There are two typical
21

=== PAGE 31 ===
examples we keep in mind when F = {Pn
j=1 e2πj2iθ, n ≥2} with θ ∼unif([0, 1]), and
F = {Pn
j=1 ajξj, n ≥1, aj ∈R}, where ξj are i.i.d.
random variables.
Notice that if
∥X∥1 ≤1 −ε then it follows from H¨older’s inequality that 1 ≤∥X∥θ
1∥X∥1−θ
p
for any p > 2
where θ =
p−2
2(p−1), and hence we arrive at a necessary condition ∥X∥p ≥1 + C(p)ε for some
positive constant C(p) > 0 which on a practice can be verified for some specific powers p.
However, random variables X taking two values show that such necessary condition is not
sufficient for (3.1.1).
The main result in this paper shows that if the necessary condition holds for some p > 2 and
we also have a good control on a growth of ∥X∥q for some q > p then we get (3.1.1).
Theorem 4. Let q > p > 2 be finite. Then there exists a constant C = C(p, q) > 0 such
that
∥X∥1 ≤1 −C

∥X∥p
p −1
 q−2
q−p

∥X∥q
q −1
 p−2
q−p
holds for any Borel measurable random variable X with ∥X∥2 = 1 and ∥X∥p < ∞.
Remark 3.1.1. We will see from the proof that
C(p, q) =
inf
a,c∈(0,1)
(cq−2(aq −1) + cq(a2 −aq) + 1 −a2)
p−2
q−p
(cp−2(ap −1) + cp(a2 −ap) + 1 −a2)
q−2
q−p · (1 −c)(1 −a)(1 −ac),
and this result is sharp, i.e., the random variables taking on two values verify the sharpness
of the constant C(p, q). Our proof will show
C(p, q) ≥(min{1, q −2})
p−2
q−p
p
2(q−2)
q−p
> 0
however, sometimes the constant C(p, q) can be explicitly computed for given powers p, q.
For example, we will see that C(4, 6) = 1/3.
22

=== PAGE 32 ===
Remark 3.1.2. One could use arguments from the classical moment problem, specifically
the nonnegativity of a matrix whose entries are the moments of X chosen in a particular way
(see page 781 in [15]), to prove Theorem 4 when p and q are integers. This approach seems
feasible for small integers p and q, such as p = 4 and q = 6. However, the computational
complexity may increase with larger values of p and q. Our method is different and does not
require p and q to be integers.
3.1.2
An application to exponential sums
In [16] Bourgain asked the following question: does there exist ε > 0 such that for any finite
subset S ⊂Z of distinct integers with |S| > 1 we have
Z 1
0

1
p
|S|
X
j∈S
e2πijθ
 dθ ≤1 −ε.
(3.1.2)
It was proved in [14] that if such ε > 0 exists then it must be at most 1 −
√π
2 . Denote
XS =
1
p
|S|
X
j∈S
e2πijθ,
where θ ∼unif[0, 1]. The best result in (3.1.2) is due to Bourgain [16], who showed existence
of a constant c > 0 such that
∥XS∥1 ≤1 −clog(|S|)
|S|
.
The question of Bourgain is already nontrivial for squares of integers, i.e.,
Q := {j2 | j = 1, . . . , m},
23

=== PAGE 33 ===
and to the best of our knowledges the inequality (3.1.2) is open in this case. In this case
Bourgain [17] showed that for any q > 4 we have
∥XQ∥q ≤C(q)|Q|
1
2 −2
q
for some
C(q) < ∞,
(3.1.3)
∥XQ∥4 ≥C log1/4(|Q|)
with some positive C > 0.
(3.1.4)
Combining the estimates (3.1.3) and (3.1.4) together with Theorem 4 applied with p = 4 we
obtain
∥XQ∥1 ≤1 −C′(q)log
q−2
q−4(|Q|)
|Q|
holds with some constant C′(q) > 0. Given any N > 1 we can choose q > 4 so that q−2
q−4 = N,
thus we obtain
Corollary 1. For any N > 0 there exists a constant c(N) > 0 such that
∥XQ∥1 ≤1 −c(N)logN(|Q|)
|Q|
.
3.1.3
An application to L1 Poincar´e inequality on the hypercube
Fix p ∈(0, 1), and let ξ1, . . . , ξn be i.i.d. Bernoulli random variables such that
ξ1 =







q
1−p
p
with probability
p,
−
q
p
1−p
with probability
1 −p.
(3.1.5)
Clearly Eξ1 = 0, and E|ξ1|2 = 1. The following theorem was proved in [21].
24

=== PAGE 34 ===
Theorem 5. There exists ε > 0 such that
sup
n≥1
sup
a2
1+...+a2n=1
E

n
X
j=1
ajξj
 < 1
holds for any p ∈(3/4 −ε, 3/4 + ε).
Notice that the conclusion of the theorem does not hold for p = 1/2. The theorem was one
of the technical steps in proving existence of a small constant δ > 0 such that
E|f(x) −Ef(x)| ≤(π
2 −δ)E|∇f|(x)
(3.1.6)
holds for any f : {−1, 1}n 7→R, all n ≥1, where x = (x1, . . . , xn) ∼{−1, 1}n,
|∇f|(x) =
 n
X
j=1
|Djf(x)|2
!1/2
,
and
Djf(x) := f(x) −f(Sj(x))
2
,
here
Sj(x) = (x1, . . . , xj−1, −xj, xj+1, . . . , xn).
The estimate (3.1.6) was particularly surprising due to the variety of proofs leading to the
same bound E|f(x) −Ef(x)| ≤π
2E|∇f|(x). Notably, one of these proofs employed a non-
commutative approach by L. Ben-Efraim and F. Lust-Piquard [18]. The consistent appear-
ance of the constant π/2 across these proofs suggested that the Cheeger constant in the L1
Poincar´e inequality might be π/2. However, this conjecture was refuted in [21] through the
establishment of (3.1.6).
25

=== PAGE 35 ===
Recently R. van Handel [20] obtained more quantitative bound on δ by showing
∥X∥1 ≤
s
1 −(∥X∥4
4 −1)2
32∥X∥6
6
hold for all random variables X with ∥X∥2 = 1, and ∥X∥4 < ∞, which allowed him to obtain
sup
n≥1
sup
a2
1+...+a2n=1
E

n
X
j=1
ajξj
 ≤
r
1 −min {4p3(1 −p)3, (2p −1)4p(1 −p)}
480
.
(3.1.7)
The inequality (3.1.7) combined together with techniques from [22] gives δ ≈0.000006....
As an immediate application of Theorem 4 we will show the following
Corollary 2. We have
sup
n≥1
sup
a2
1+...+a2n=1
E

n
X
j=1
ajξj
 ≤1 −min {4p3(1 −p)3, (2p −1)4p(1 −p)}
45 −3(p(1 −p))3
(3.1.8)
holds for all p ∈[0, 1].
The corollary combined with arguments from [22] gives the following
Corollary 3. For any f : {−1, 1}n 7→R we have
E|f(x) −Ef(x)| ≤
π
2 −δ

E|∇f|(x)
(3.1.9)
holds with δ ≈0.00013...
Remark 3.1.3. It seems to us that the best δ one can choose in (3.1.9) is
π
2 −p π
2 ≈
0.31748..., at least this is the case in an analogous question in Gauss space, however, to
prove such a statement one needs to come up with techniques different from Section 3.2.4.
Indeed, let X = Pn
j=1 ajξj be a biased Rademacher sum. Let R = R(p) ∈(0, 1) be the best
26

=== PAGE 36 ===
constant, for each p ∈(0, 1), such that ∥X∥1/∥X∥2 ≤R(p). In [25] it was proved that
sup
n≥1, a2
j=aj
∥X∥1
∥X∥2
= 2
p
N(p∗)p∗(1 −p∗)N(p∗)−1,
(3.1.10)
where N(p) = ⌊
1
1−(1−p)2⌋, and p∗= min(p, 1 −p). Therefore, the best δ one may hope to get
in (3.1.9) using the argument in Section 3.2.4, assuming R(p) equals to the right hand side
of (3.1.10), is π
2 −
R 1
1/2 2
p
N((1 −p))(1 −p)pN(1−p)−1
dp
√
p(1−p) ≈0.149... which is still far from
π/2 −
p
π/2 ≈0.31748....
3.2
Proofs
3.2.1
The proof of Theorem 4
By rescaling we can rewrite the claimed inequality in the theorem as follows
∥X∥2 −∥X∥1 ≥C(p, q)
∥X∥2
·

∥X∥p
p −∥X∥p
2
 q−2
q−p

∥X∥q
q −∥X∥q
2
 p−2
q−p ,
(3.2.1)
which holds for all Borel random variables X with ∥X∥p < ∞. If ∥X∥q = ∞there is nothing
to prove, so in what follows we consider random variables X such that ∥X∥q < ∞. Without
loss of generality, we will first assume that ∥X∥∞< ∞since by the Dominated Convergence
Theorem, we can take XN = min{|X|, N} and note that XN ≤|X| and
XN →|X|
a.e..
Furthermore, by homogeneity of (3.2.1), assume for now that 0 ≤X ≤1. Note that since
we take absolute values in all Lp norms that it suffices to prove (3.2.1) when X ≥0. As
27

=== PAGE 37 ===
for the assumption that X ≤1, we will briefly need this assumption, but note that we will
soon replace it with a more useful stipulation. We now consider the following optimization
problem:
Φ(x, y, z) = sup
0≤X≤1
{EX,
EX2 = x,
EXp = y,
EXq = z}.
We will note that fortunately for us the space curve γ(t) = (t2, tp, tq, −t),
t ∈[0, 1] has
totally positive torsion. We recall that this means that the leading principal minors of the
4 × 4 matrix (γ(1)(t), γ(2)(t), γ(3)(t), γ(4)(t)) are positive for all t ∈(0, 1). For the sake of
completeness, we will check total positivity here. First of all, the matrix is given by


γ(1)(t)
γ(2)(t)
γ(3)(t)
γ(4)(t)


=


2t
ptp−1
qtq−1
−1
2
p(p −1)tp−2
q(q −1)tq−2
0
0
p(p −1)(p −2)tp−3
q(q −1)(q −2)tq−3
0
0
p(p −1)(p −2)(p −3)tp−4
q(q −1)(q −2)(q −3)tq−4
0


and that the i-th leading principal minors Aii are each respectively given by
A11 = 2t,
A22 = tp−12p(p −1),
A33 = 2pq(p −2)(q −2)(q −p)tp+q−4,
A44 = 2p(p −1)(p −2)q(q −1)(q −2)(q −p)tp+q−7,
where positivity follows from the fact that t > 0 and that 2 < p < q. We can thus invoke
Theorem 2.3, case 1 in [19], which tells us that the supremum in Φ(x, y, z) is achieved by a
random variable X taking on at most two values. To that end, we will assume in the sequel
that
P{X = a} = 1 −P{X = b} = r.
28

=== PAGE 38 ===
As we no longer need it, we will drop the assumption X ≤1 at this point and by homogeneity
instead replace it with the assumption that ∥X∥2 = 1. Note that since
∥X∥2
2 = a2r + b2(1 −r),
our new normalization assumption implies that
r = b2 −1
b2 −a2.
Taking this into account, we obtain that
∥X∥1 = 1 + ab
a + b ,
meaning the desired inequality can now be expressed as
(1 −a)(b −1)
a + b
≥C(p, q)

ap(b2−1)+bp(1−a2)
b2−a2
−1
θ

aq(b2−1)+bq(1−a2)
b2−a2
−1
θ−1,
where θ = q−2
q−p, and we may furthermore assume without loss of generality that 0 < a < 1 <
b < ∞, otherwise arbitrary. We next note that we can further simplify this as

aq(b2−1)+bq(1−a2)+a2−b2
(1−a)(b−1)(b−a)
θ−1
≥C(p, q)

ap(b2−1)+bp(1−a2)+a2−b2
(1−a)(b−1)(b−a)
θ
.
(3.2.2)
After a change of a variables b = 1/c, where c ∈(0, 1), the inequality (3.2.2) rewrites and
simplifies as
cq−2(aq −1) + cq(a2 −aq) + 1 −a2
(1 −c)(1 −a)(1 −ac)
θ−1
≥
C(p, q)
cp−2(ap −1) + cp(a2 −ap) + 1 −a2
(1 −c)(1 −a)(1 −ac)
θ
.
29

=== PAGE 39 ===
Next, by defining
B(a, c, q) := cq−2(aq −1) + cq(a2 −aq) + 1 −a2
(1 −c)(1 −a)(1 −ac)
,
we can take
C(p, q) =
inf
a,c∈(0,1)
B(a, c, q)θ−1
B(a, c, p)θ .
(3.2.3)
To show C(p, q) > 0 we claim that we can find constants c1(p), c2(p) > 0 such that
c1(p) ≤B(a, c, p) ≤c2(p),
Then the equality (3.2.3) will imply
C(p, q) > c1(q)θ−1
c2(p)θ .
We will thus move on to finding upper and lower bounds on the function B(a, c, p), where
2 ≤p < ∞and (a, c) ∈[0, 1] × [0, 1].
Lemma 3.2.1. We have B(a, c, p) ≥min{1, p −2} for all a, c ∈(0, 1) and all p > 2.
Proof. Let L := p−2
p , and for each c ∈(0, 1) consider the family of functions f(a) = f(a; c)
defined as
f(a) := cp−2(ap −1) + cp(a2 −ap) + 1 −a2 −L(1 −c)(1 −a)(1 −ac).
Clearly the lemma is the same as f(a) ≥0 for all a, c ∈(0, 1). To verify f(a) ≥0 we will
argue as follows: we will show that
(1) f(0) ≥0.
30

=== PAGE 40 ===
(2) f(1) = 0.
(3) f ′(1) ≤0.
(4) f ′′(0) < 0.
(5) f ′′ changes sign at most once from −to +.
It then follows that f(a) ≥0 on [0, 1]. Indeed, if f ′′ ≤0 on [0, 1] then we are done because
of (1) and (2). If f ′′ changes sign from −to + at point k ∈[0, 1), then (2) and (3) imply
that f ≥0 on [k, 1]. In particular f(k) ≥0. Thus f ≥0 on [0, k] because f ′′ ≤0 on [0, k],
and this finishes the proof of Lemma 3.2.1.
To verify (1), we have
f(0) = −cp−2 + 1 −L(1 −c).
Since φ(c) = −cp−2 + 1 −L(1 −c) has the properties φ(0) = 1 −L ≥0, φ(1) = 0, and
φ′(c) = −(p −2)cp−3 + L changes sign at most once from + to −if p > 3, and φ′ ≤0 if
p ∈(2, 3] it follows that φ(c) ≥0 on [0, 1).
The verification of (2) is trivial, so we move to verifying (3). We have
f ′(a) = pcp−2ap−1 + 2cpa −pcpap−1 −2a + L(1 −c)(1 −ac) + Lc(1 −c)(1 −a).
f ′(1) = pcp−2 + cp(2 −p) −2 + L(1 −c)2.
Let ψ(c) = pcp−2 + cp(2 −p) −2 + L(1 −c)2. We have ψ(1) = ψ′(1) = 0. If p > 3 then we
see the coefficients of the pseudo-polynomial
ψ(c) = cp(2 −p) + pcp−2 + Lc2 −2Lc + L −2
31

=== PAGE 41 ===
when arranged according to decreasing order of powers c have the signs −+ + −−. Here,
we do not know if p −2 ≥2 or p −2 < 2 but nevertheless there will be always two sign
changes in the coefficients. Therefore by Descartes rule of signs for pseudo-polynomials (see
example #77 on page 46 in [23]) we obtain that ψ(c) has at most two roots, therefore, ψ(c)
does not have roots on (0, 1). Since ψ(0) = L −2 < 0 we get ψ(c) ≤0 on [0, 1). If 2 < p ≤3
we have
ψ′(c) = p(2 −p)cp−1 + p(p −2)cp−3 + 2Lc −2L
= p(p −2)cp−3(1 −c2) −2L(1 −c)
= (1 −c)(p(p −2)cp−3(1 + c) −2L)
> (1 −c)(p(p −2) −2L) ≥0,
which implies that ψ(c) ≤0 on [0, 1).
Next we verify (4). We have
f ′′(a) = p(p −1)cp−2ap−2 + 2cp −p(p −1)cpap−2 −2 −2Lc(1 −c)
= ap−2p(p −1)cp−2(1 −c2) −2(1 −cp) −2Lc(1 −c).
(3.2.4)
Therefore f ′′(0) = −2(1 −cp) −2Lc(1 −c) < 0 since c ∈(0, 1).
Finally we verify (5). If follows from (3.2.4) that a 7→f ′′(a) is increasing, and f ′′(0) < 0.
Therefore f ′′ can change sign at most once from −to + on (0, 1].
Lemma 3.2.2. We have B(a, c, p) ≤p2 for all a, c ∈(0, 1) and all p ≥2.
Proof. Let M = p2, and consider
g(a) = cp−2(ap −1) + cp(a2 −ap) + 1 −a2 −M(1 −c)(1 −a)(1 −ac).
32

=== PAGE 42 ===
It suffices to show that g is concave, g(1) = 0 and g′(1) ≥0. The claim g(1) = 0 is trivial.
To verify g′(1) ≥0 we have
g′(1) = cp(2 −p) + pcp−2 + Mc2 −2Mc −2 + M.
Let h(c) = cp(2−p)+pcp−2+Mc2−2Mc−2+M. We have h(0) = M−2 ≥0, h(1) = h′(1) = 0.
Also h′′(1) = 2(M −(p2 −2p)) > 0. Since the coefficient in front of cp is negative then there
must exist k > 1 such that h(k) = 0. The coefficients of h(c) have at most 3 sign changes,
therefore by Descartes rule of signs for pseudo-polynomials h cannot have roots in (0, 1), so
h(c) ≥0, and hence g′(1) ≥0 on [0, 1].
To verify concavity of g we have
g′′(a) = ap−2p(p −1)cp−2(1 −c2) −2(1 −cp) −2Mc(1 −c).
Since a 7→g′′(a) is increasing in a, it suffices to show that g′′(1) ≤0. We have
g′′(1) = −cp(p + 1)(p −2) + cp−2p(p −1) + 2Mc2 −2Mc −2.
If p > 3 then pseudo-polynomial v(c) = −cp(p + 1)(p −2) + cp−2p(p −1) + 2Mc2 −2Lc −2
has at most two sign changes in its coefficients, hence at most two roots (counting with
multiplicities) on [0, ∞). On the other hand v(1) = v′(1) = 0, and v′′(1) = −4p(p −2)2 < 0,
therefore v(c) ≤0 on [0, 1]. Assume 2 < p ≤3. Consider w(c) = v(c)/c. We have w(1) = 0.
Let us show that w′(c) ≥0 on (0, 1). Indeed
w′(c) = p(p −1)(p −3)cp−4 −(p2 −1)(p −2)cp−2 + 2M + 2
c2
≥p(p −1)(p −3)cp−4 −(p2 −1)(p −2) + 2M + 2
c2 := N(c).
The expression N(c) satisfies N(0) = +∞and N(1) = −2p(p −2) + 2M > 0. Also Notice
33

=== PAGE 43 ===
that N ′(c) = (p −4)(p −3)(p −1)pcp−5 −4
c3 = 0 if and only if
c = c0(p) =

4
(4 −p)(3 −p)p(p −1)
1/(p−2)
.
On the other hand we have
c2
0N(c0) =
4(p −3)p(p −1)
(4 −p)(3 −p)p(p −1) + c2(2M −(p2 −1)(p −2)) + 2
= −2(p −2)
4 −p
+ c2
0(2M −(p2 −1)(p −2)).
Since M = p2 ≥2(p −1)(p −2) for p ∈[2, 3], we have
−2(p −2)
4 −p
+ c2
0(2M −(p2 −1)(p −2)) ≥
−2(p −2)
4 −p
+ c2
0(4(p −1)(p −2) −(p2 −1)(p −2)) =
−2(p −2)
4 −p
+

4
(4 −p)(3 −p)p(p −1)
2/(p−2)
(p −1)(p −2)(3 −p) =
2t
2 −t
"
−1 +

24−t
(2 −t)2−t(1 −t)2−t(2 + t)2(1 + t)2−t
1/t#
,
where p = 2 + t for t ∈[0, 1]. Consider
f(t) = log

24−t
(2 −t)2−t(1 −t)2−t(2 + t)2(1 + t)2−t

.
We have f(0) = f ′(0) = 0. To show f(t) ≥0 on [0, 1] it suffices to verify that f ′′(t) ≥0 on
[0, 1]. A direct computation shows
f ′′(t) = −3t6 −14t5 + 8t4 + 52t3 −t2 −38t + 32
(2 −t)(1 −t)2(t + 2)2(1 + t)2
.
34

=== PAGE 44 ===
Notice that
−3t6 −14t5 + 8t4 + 52t3 −t2 −38t + 32 ≥
−3t4 −14t4 + 8t4 + 52t3 −t2 −38t + 32 =
−9t4 + 52t3 −t2 −38t + 32 ≥43t3 −39t + 32.
On the other hand 43t3−39t+32 ≥40t3−40t+30 = 10(4t3−4t+3). The map t 7→4t3−4t+3
is positive at t = 0 and t = 1. It has a critical point at t = 1/
√
3 where its value is 3−8
√
3
9
> 0.
Thus f ′′ ≥0 on [0, 1].
3.2.2
The proof of C(4, 6) = 1/3
Let p = 4 and q = 6. We have
(cq−2(aq −1) + cq(a2 −aq) + 1 −a2)
p−2
q−p
(cp−2(ap −1) + cp(a2 −ap) + 1 −a2)
q−2
q−p · (1 −c)(1 −a)(1 −ac) −1
3
= c(2c −1)a2 −(c + 1)2a + 3c2 −c + 2
3(1 + c)(1 + a)(1 + ac)
.
It suffices to show infa,c∈(0,1) c(2c −1)a2 −(c + 1)2a + 3c2 −c + 2 = 0. Indeed, the map
r(a) = c(2c −1)a2 −(c + 1)2a + 3c2 −c + 2 is decreasing in a because the linear function
r′(a) = 2c(2c−1)a−(c+1)2 satisfies r′(0) < 0 and r′(1) = 2c(2c−1)−(c+1)2 = 3c2−4c−1 =
−3c(1 −c) −c −1 < 0. On the other hand r(1) = (2c −1)2 ≥0 and it becomes equality at
c = 1/2.
35

=== PAGE 45 ===
3.2.3
The proof of Corrollary 2
Let X = | Pn
j=1 ajξj|, where ξi, i = 1, . . . , n, are i.i.d. random variables defined as in (3.1.5),
and Pn
j=1 a2
j = 1. We have ∥X∥2 = 1, and
E|X|4 = 3 + (Eξ4
1 −3)
n
X
j=1
a4
j ≥min{3, Eξ4
1} = 1 + min

2, (2p −1)2
p(1 −p)

.
On the other hand if ξ′
j is independent copy of ξj, j = 1, . . . , n, and εj, j = 1, . . . , n, are i.i.d.
symmetric ±1 Rademacher random variables we have b a symmetrization argument
E|X|6 = E|
n
X
j=1
ajξj|6 ≤E|
n
X
j=1
aj(ξj −ξ′
j)|6 = Eξ,ξ′Eε|
n
X
j=1
ajεj(ξj −ξ′
j)|6
≤Eξ,ξ′
 n
X
j=1
a2
j(ξj −ξ′
j)2
!3
≤
15
p3(1 −p)3,
where we used the Khinchin’s inequality E| P εibi|6 ≤15 (P b2
i )3 with the sharp constant
15. Thus Theorem 4 applied with constant C(4, 6) = 1/3 gives
∥X∥1 ≤1 −min {4p3(1 −p)3, (2p −1)4p(1 −p)}
45 −3(p(1 −p))3
.
3.2.4
The proof of Corrollary 3
We need the following identity obtained in [22]. For any f : {−1, 1}n →R, we have
f(x) −Ef(x) =
Z ∞
0
1
√
e2t −1Eζ
n
X
j=1
δj(t)Djf(xζ(t))dt,
(3.2.5)
where xζ(t) = (x1ζ1(t), ..., xnζn(t)), and the ζi(t) are i.i.d. random variables with
P{ζi(t) = ±1} = 1 ± e−t
2
,
36

=== PAGE 46 ===
and δi = ζi(t)−Eζi(t)
√
Var(ζi(t)). We have
E|f(x) −Ef(x)| ≤
Z ∞
0
E

n
X
j=1
δj(t)Djf(xζ(t))

dt
√
e2t −1
=
Z ∞
0
E

n
X
j=1
δj(t)Djf(x)

dt
√
e2t −1
(p= 1+e−t
2
)
=
Z 1
1/2
E

n
X
j=1
ξjDjf(x)

dp
p
p(1 −p)
(3.1.8)
≤
E|∇f|
Z 1
1/2

1 −min {4p3(1 −p)3, (2p −1)4p(1 −p)}
45 −3(p(1 −p))3

dp
p
p(1 −p)
≈
π
2 −δ

E|∇f|,
where
δ =
Z 1
1/2
min {4p3(1 −p)3, (2p −1)4p(1 −p)}
45 −3(p(1 −p))3
dp
p
p(1 −p)
≈0.00013...
37

=== PAGE 47 ===
Chapter 4
An Optimization Problem concerning
Binomial RVs
4.1
Sums of Biased Rademachers
Given p ∈(0, 1), let ξ1(p), ..., ξn(p) be i.i.d. p-biased Rademacher random variables defined
as follows:
P

ξi(p) =
r1 −p
p

= 1 −P

ξi(p) = −
r
p
1 −p

= p.
We are interested in following question: given a1, ..., an ∈R, can we find a universal constant
C(p) depending only on p̸ = 1/2 such that
E|a1ξ1(p) + ... + anξn(p)|
a2
1 + ... + a2
n
≤C(p) < 1.
When p = 1/2, the answer to this question is a clear no (consider n = 1) which is why
we exclude this case. Observe that without loss of generality we can make the assumption
nP
i=1
a2
i = 1, and by the symmetry ξi(1 −p)
d= −ξi(p) only consider the case p ∈(0, 1/2) in
38

=== PAGE 48 ===
which case, we are asking whether
sup
n
P
i=1
a2
i =1
E|a1ξ1(p) + ... + anξn(p)| ≤C(p) < 1.
Another helpful way to think about this problem that will be useful to reference later is
by letting X1(p), ..., Xn(p) be a sequence of i.i.d. Bernouilli random variables with success
probability p, where given a = (a1, ..., an) such that a2
1 + ... + a2
n = 1, if we define Sn(p, a) =
a1X1 + ... + anXn, is it true that
sup
|a|=1
E|Sn(p, a) −ESn(p, a)|
np(1 −p)
≤C(p) < 1?
We will be interesting in finding sharp C(p).
4.2
Preliminary computations
Since there is a particularly nice formula, we will first answer this question in the case n = 2.
We thus compute:
1
p
p(1 −p)
E|a1ξ1 + a2ξ2| = |a1 + a2| + |a1 −p(a1 + a2)| + |a2 −p(a1 + a2)|
We next note that by applying the formula |x −y| + |x −z| = max(|y −z|, |2x −y −z|), we
obtain that
|a1 −p(a1 + a2)| + |a2 −p(a1 + a2)| = max (|a1 −a2|, |(1 −2p)(a1 + a2)|) ,
we thus have that since
1 + |1 −2p| = 2 max(p, (1 −p))
39

=== PAGE 49 ===
and
|a1 + a2| + |a1 −a2| = 2 max(|a1|, |a2|)
it follows that when p < 1/2
1
p
p(1 −p)
E|a1ξ1 + a2ξ2| = 2 max(|a1|, |a2|, (1 −p)|a1 + a2|)
we can thus see that by either setting one of the variables equal to 1 and the other to
0, or setting both equal to one another that E|a1ξ1 + a2ξ2| is maximized when the linear
combination of r.v.s in question is a centered and normalized binomial (n, p) distribution
with n = 1, 2.
Unfortunately, as we increase the number of Rademacher variables the
computation becomes exponentially more difficult and you do not end up with formulas
nearly as nice as in this simplest non-trivial case we just solved.
On the other end of the spectrum, by considering far more than 2 random variables and
assuming that a2
i = ai, the central limit theorem tells us that as n approaches infinity, we
have the limit
1
√nE|ξ1 + ... + ξn| →
r
2
π.
This might make us think that
q
2
π is the best we do as p approaches 0 or 1. It turns out
that we can do a little bit better than that, which we will summarize below.
4.3
Summary of Main Result
For the remainder of this chapter, we will specialize to the binomial case where all non-zero
coefficients ai are set equal to one another. We summarize this as follows:
Theorem 4.3.1. Let p ∈(0, 1/2] and Xn(p) =
1
√n
nP
i=1
ξi(p), with the ξi(p) defined as above.
40

=== PAGE 50 ===
Then
Sn(p) := E|Xn(p)| ≤SNp(p) = 2
s
pNp
1 −p(1 −p)Np,
(4.3.1)
where Np =
j
1
1−(1−p)2
k
Equivalently, we have that
sup
n∈N
Sn(p) = SN(p)
if and only if







p ∈
h
1 −
1
√
2, 1
2
i
when N = 1
p ∈
h
1 −
q
N
N+1, 1 −
q
N−1
N
i
otherwise.
A few things about this result are worth pointing out. The first is that restricting ourselves
to the front half of the unit interval is for the sake of making the bounds more readable
and the results can be reformulated for p ∈[1/2, 1) by interchanging every instance of p
with 1 −p, since the quantity E|Sn(p)| is symmetric in p about 1/2. The second is that for
every value of p, N =
j
1
1−(1−p)2
k
if and only if p ∈

1 −
q
N
N+1, 1 −
q
N−1
N
i
. Note: For an
application of this result see Section 4.1.3 below.
The reader is also invited to check that the quantity 2
q
pNp
1−p(1 −p)Np converges to
q
2
e as
p approaches 0 or 1. This number will be of great relevance later in this chapter, but it is
interesting insofar that it is actually larger than the asymptotic limit of
q
2
π given to us by
CLT.1
In [26], the authors also considered the mean absolute deviation, or MAD, of binomial
random variables and found sharp asymptotic bounds for Sn(p) (Dn(p) in their paper) as p
is sufficiently close to either 0 or 1. We proceed in a slightly different direction and instead
1As we will see below,
p
2/e will suffice as a constant upper bound on Sn(p) so long as n is sufficiently
large and p ∈[1/n, 1 −1/n].
41

=== PAGE 51 ===
find a universal bound independent of n as a function p ∈[0, 1]. See the figures below for
visualizations of Sn(p) for a few values of n as well as a graph of the upper bound in Theorem
(4.3.1)
Figure 4.3.1: Sn(p) for n = 1, 2, 3, 4 and 0 ≤p ≤1
Figure 4.3.2: SNp(p) for 0 ≤p ≤1
42

=== PAGE 52 ===
4.4
Proofs
In what follows, we will make extensive use of the following closed form expression. For ξi
as defined above:
1
√nE

n
X
i=1
ξi(p)
 = 2
r np
1 −p
n −1
⌊np⌋

(1 −p)n−⌊np⌋p⌊np⌋,
Letting Yn be a binomial random variable with parameters n and p and noting that
1
√n
nP
i=11
ξi
is equal in distribution to a centered and normalized Yn, we may equivalently state that
E |Yn −EYn| = 2n
n −1
⌊np⌋

(1 −p)n−⌊np⌋p⌊np⌋+1 = 2Var(Yn)P{Yn−1 = ⌊np⌋}.
(4.4.1)
The closed form expression for the mean absolute deviation of a binomial random variable
in (4.4.1) is generally attributed to work from 1730 by Abraham De Moivre (see [13]). For
the sake of completeness, we will prove the formula here:
Proof. Notice that EYn = np, meaning Yn > EYn if and only if Yn > np.
Since Yn is
integer-valued we can split the summation in the following way
E |Yn −EYn| =
n
X
k=0
|k −np|
n
k

pk(1 −p)n−k
=
⌊np⌋
X
k=0
(np −k)
n
k

pk(1 −p)n−k +
n
X
k=⌊np⌋+1
(k −np)
n
k

pk(1 −p)n−k.
Next, we observe that
n
X
k=⌊np⌋+1
(k −np)
n
k

pk(1 −p)n−k = −
⌊np⌋
X
k=0
(k −np)
n
k

pk(1 −p)n−k,
43

=== PAGE 53 ===
which we can plug into the calculation above to obtain that
E |Yn −EYn| = 2
⌊np⌋
X
k=0
(np −k)
n
k

pk(1 −p)n−k.
All that’s left to show is that
m
X
k=0
(np −k)
n
k

pk(1 −p)n−k = n
n −1
m

(1 −p)n−mpm+1
for any m ≤n. We will do this via an induction over m. For m = 0, this identity is trivial.
Thus assume the inductive hypothesis and that the identity holds true for some m < n.
Then
m+1
X
k=0
(np −k)
n
k

pk(1 −p)n−k
= (np −(m + 1))

n
m + 1

pm+1(1 −p)n−(m+1) + n
n −1
m

(1 −p)n−mpm+1
=
 n2p
m + 1 −n + n(1 −p)
 n −1
m

pm+1(1 −p)n−(m+1)
= n
n −m −1
m + 1
 n −1
m

pm+2(1 −p)n−(m+1)
= n
n −1
m + 1

pm+2(1 −p)n−(m+1),
which yields the desired induction, therefore completing the proof.
We will start by proving Theorem 4.3.1 for the special case where ⌊np⌋= 0.
Proposition 4.4.1. (4.3.1) holds when ⌊np⌋= 0.
Proof. Fix p ∈(0, 1/2] and let n ∈N be such that ⌊np⌋= 0
Sn(p) = 2
r np
1 −p(1 −p)n.
(4.4.2)
44

=== PAGE 54 ===
Letting n vary amongst all n for which p < 1
n, we see that Sn(p) always has the common
factor 2
q
p
(1−p). Thus, it suffices to find the maximum of the function
F(n) = √n(1 −p)n,
over the positive integers2. To start, we treat n as a continuous parameter, and differentiate:
∂
∂nF(n) = (1 −p)n
2√n
(2n log(1 −p) + 1) .
We make the following observation: First, F(n) has a unique critical point at n =
1
log

1
(1−p)2
,
and since the sign of
∂
∂nF(n) changes from positive to negative at this critical point we have
that n =
1
log

1
(1−p)2
 gives the global maximum of F for n ∈R+. Next, we apply the inequality
1 −1
x ≤log(x) ≤x −1 to this critical point, which yields
1
1 −(1 −p)2 −1 ≤
1
log

1
(1−p)2
 ≤
1
1 −(1 −p)2.
Writing N =
j
1
1−(1−p)2
k
, we note that we may be agnostic towards whether
1
log

1
(1−p)2
 ≤N
holds true and simply consider N−1, N, and N+1 as the only candidates for the maximum of
F(n) when restricted to the positive integers. Next, notice that when ⌊(n+1)p⌋= ⌊np⌋= 0,
we have that
F(n + 1)
F(n)
=
r
n + 1
n
(1 −p),
meaning F(n + 1) ≤F(n) if and only if 1 −p
n
n+1 ≤p. It follows that F(N) is the integer
maximum over F if and only if 1 −
q
N
N+1 ≤p ≤1 −
q
N−1
N , which is true by the definition
that Np =
j
1
1−(1−p)2
k
, yielding the desired result in the case ⌊np⌋= 0.
We now proceed to the more general case, which we split into a handful of lemmas:
2One might wonder whether assuming n < 1/p is neccessary here but this turns out to not be the case.
45

=== PAGE 55 ===
Lemma 4.4.2. (4.3.1) holds when n = 3.
Proof. Suppose p ∈(0, 1/2]. If p ∈(0, 1/3), there is nothing left to prove by Prop. 4.4.1.
Thus suppose p ∈[1/3, 1/2]. The reader is invited to check that N =
j
1
1−(1−p)2
k
= 1 on this
interval3. Thus consider that
S3(p)
S1(p) = 2
√
3p(1 −p) ≤
√
3
2 < 1,
which proves the lemma.
The next two lemmas, when combined, will take care of the remaining cases. The first of
these gives us a upper bound for (4.3.1):
Lemma 4.4.3. When n ≥4, we have that
Sn(p) ≤
r
2
e
for all p ∈[1/n, 1/2)
Proof. Suppose p ∈[1/n, 1/2] and let k = ⌊np⌋and note that 1 ≤k ≤n
2. We thus have that
Sn(p) = 2
r np
1 −p
n −1
k

(1 −p)n−kpk.
Note that by some elementary calculus we have (for fixed k) that Sn(p) is maximized at
p =
k+ 1
2
n . We therefore write
F(k, n) = Sn
k + 1
2
n

= 2√n
n −1
k
 n −k −1/2
n
n−k−1/2 k + 1/2
n
k+1/2
.
3One way to see this is to note that N is non-increasing in p and that this assertion holds at both
endpoints.
46

=== PAGE 56 ===
We claim that when n is fixed, F(k, n) decreases in k over the integers for k ≤n
2. To that
end, consider the ratio
G(k, n) =
F(k, n)
F(k −1, n) = k + 1/2
k
k + 1/2
k −1/2
k−1/2
n −k
n −k + 1/2
n −k −1/2
n −k + 1/2
n−k−1/2
,
and consider separately the two functions
G1(k) = k + 1/2
k
k + 1/2
k −1/2
k−1/2
and
G2(k, n) =
n −k
n −k + 1/2
n −k −1/2
n −k + 1/2
n−k−1/2
.
Treating k as a continuous parameter and taking the logarithmic derivative of G1 with respect
to k, we get
∂
∂k log G1 = log
k + 1/2
k −1/2

−1
k
and in addition
∂2
∂k2 log G1 = −
1
4k2(k + 1/2)(k −1/2) < 0,
which along with the observation that
lim
k→∞
∂
∂k log G1 = 0
implies that
∂
∂k log G1 ≥0 for all k. Then, since
G2(k, n) =
1
G1(n −k),
we have that
∂
∂k log(G) = ∂
∂x log G1(x)

x=k
+ ∂
∂x log G1(x)

x=n−k
≥0
by the chain rule and our previous observations. Since G has a non-negative logarithmic
47

=== PAGE 57 ===
derivative we thus conclude that the ratio G(k, n) is increasing in k. Since we are only
considering 1 ≤k ≤n
2 in this proof, we thus check
G
n
2, n

= G1(n/2)
1
G1(n/2) = 1,
which by the established monotonicity implies that G(k, n) ≤1, i.e. F(k, n) ≤F(k −1, n),
as claimed. We thus check for k = 1 that
F(1, n) = 2√n(n −1)

1 −3/2
n
n 
3/2
n −3/2
3/2
.
We again take logarithmic derivatives obtaining
∂
∂n log(F(1, n)) =
1
(n −1) + 1
2n + log

1 −3/2
n

and
∂2
∂n2 log(F(1, n)) =
n2 −2n + 3
2(n −1)2n2(2n −3) ≥0.
Using this, we observe that since
lim
n→∞
∂
∂n log(F(1, n)) = 0,
it follows that
∂
∂n log(F(1, n)) ≤0
for all n. Since we have assumed n ≥4, we check that
F(1, 4) =
r
2
e
225
p
15e/2
1024
≤
r
2
e,
which completes the proof of the lemma.
48

=== PAGE 58 ===
We proceed to our next lemma, which gives a universal lower bound on the right hand side
of (4.3.1):
Lemma 4.4.4. Let p ∈(0, 1/2] and write Np =
j
1
1−(1−p)2
k
, we then have that
r
2
e ≤SNp(p).
Proof. First suppose Np = 1. We know from earlier that this means that p ∈

1 −
1
√
2, 1
2

.
We thus see that
S1(p) = 2
p
p(1 −p) ≥23/4
s
1 −
r
1
2 > .9 >
p
2/e.
We thus move on to when Np = N > 1, which we know from above occurs whenever
p ∈

1 −
q
N
N+1, 1 −
q
N−1
N
i
. Since we know that
SN(p) = 2
s
Np
1 −p(1 −p)N
has a maximum at p =
1
2N , we also check that
1 −

1 −1
2N
2
= 1
N −
1
4N 2 ∈

1
N + 1, 1
N

,
which is true since
1
N −
1
4N 2 −
1
N + 1 =
3N −1
4N 2(N + 1) > 0.
This observation tells us that the maximizer p =
1
2N ∈

1 −
q
N
N+1, 1 −
q
N−1
N
i
. Given the
behavior of the function p 7→pJ(1 −p)K, we know that the minimum of SN(p) on this
interval is thus achieved at one of the endpoints. Since we have previously observed that
SN(p) = SN+1(p) when p = 1 −
q
N
N+1, it suffices to only check if the inequality holds for
49

=== PAGE 59 ===
SN(p) at the right endpoint p = 1 −
q
N−1
N . To that end, we write
SNp(p) ≥H(N, p) := SNp
 
1 −
r
N −1
N
!
= 2
√
N
sr
N
N −1 −1
N −1
N
N/2
.
Similar to what we did above, consider the ratio
H(N + 1, p)
H(N, p)
2
=

N −
√
N 2 −N
√
N 2 −1 −
√
N 2 −N
 N −1
N
N
.
We next observe that
H(N + 1, p)
H(N, p)
2
≤2 −
√
2
√
3 −
√
2e−1 ≤1
since
  N−1
N
N ≤e−1 and
N−
√
N2−N
√
N2−1−
√
N2−N is decreasing for all N, and we have assumed N ≥2.
We thus have that H(N + 1, p) ≤H(N, p) for all N ≥2. We thus observe that since
lim
N→∞
N 3/2 −N
√
N −1
√
N −1
= lim
N→∞2 −3(N −
√
N 2 −N) = 1/2
and
lim
N→∞
N −1
N
N/2
= 1
√e
that
lim
N→∞H(N, p) =
r
2
e,
from which the desired result follows immediately.
We now have everything we need to prove Theorem 4.3.1:
Proof of Theorem 4.3.1. Let p ∈(0, 1/2] and suppose n ∈N. If np < 1, we obtain the
desired bound by Prop 4.4.1. Note that there is now nothing left to show if n = 1, 2 (in
the n = 2 case the only possibility left is if p = 1/2, which we have established in the
introduction as a trivial case), and that we have also already accounted for the case n = 3
50

=== PAGE 60 ===
in Lemma 4.4.2. Thus suppose n ≥4 and np ≥1, we thus have by Lemmas 4.4.3 and 4.4.4
respectively that
Sn(p) ≤
r
2
e ≤SNp(p),
which completes the proof.
51

=== PAGE 61 ===
Bibliography
[1] Beckner, W, Inequalities in Fourier Analysis. Annals Of Mathematics. 102, 159-182
(1975)
[2] I. Benjamini, G. Kalai, O. Schramm, First passage percolation has sublinear
distance variance. Ann. Probab. 31(4) 1970–1978 (2003)
[3] M. Ben-Naor, N. Linial, Collective Coin Flipping. In Randomness and Computa-
tion S. Micali ed. Academic press, new York, 1990
[4] J. Bourgain, The metrical interpretation of superreflexivity in banach spaces. Israel
Journal of Mathematics, 56, pp 222 – 230 (1986)
[5] S. Chatterjee, Superconcentration and Related Topics. Springer, 2014
[6] A. Eskenazis, D. Cordero-Erausquin, Talagrand’s influence inequality revisited.
to appear Analysis & PDE (2022)
[7] P. Ivanisvili, R. van Handel, A. Volberg, Rademacher type and Enflo type
coincide. Ann. of Math. (2) 192(2): pp. 665–678 (2020)
[8] J. Kahn, G. Kalai, N. Linial, The influence of variables on Boolean functions.
29th Annual Symposium on Foundations of Computer Science. pp. 68 – 80 (1988)
[9] A. Naor, An introduction to the Ribe program. Japanese Journal of Mathematics, 7,
pp 167-233 (2012)
52

=== PAGE 62 ===
[10] R. O’Donnell, Analysis of Boolean Functions. arXiv: 2105.10386
[11] M. Ribe, On uniformly homeomorphic normed spaces, Ark. Mat. 14, pp. 237–244,
(1976).
[12] M. Talagrand, On Russo’s Approximate Zero-One Law. The Annals of Probability,
No. 3, pp. 1576 – 1587 (1994)
[13] P. Diaconis, S. Zabell, Closed Form Summation for Classical Distributions: Varia-
tions on a Theme of De Moivre. Statistical Science, Statist. Sci. 6(3), 284-302, (August,
1991)
[14] C. Aistleitner On a problem of Bourgain concerning the L1-norm of exponential
sums. Math. Z, 275, 681–688 (2013)
[15] D. Bartsimas, I. Popescu, Optimal Inequalities in Probability Theory: A Convex
Optimization Approach. SIAM Journal on OptimizationVol. 15, Iss. 3 (2005)
[16] J. Bourgain On the spectral type Ornstein’s class one transformations. Israel Journal
of Mathematics, vol. 84, pages 53–63 (1993)
[17] J. Bourgain On Λp subsets of squares. Israel Journal of Mathematics, vol. 67, no. 3,
pages 291–311 (1989)
[18] L. Ben Efraim, F. Lust-Piquard Poincar´e type inequalities on the discrete cube
and in the CAR algebra. Prob. Theory Related Fields 141 (2008), no. 3-4, 569–602.
[19] J. de Dios Pont, P. Ivanisvili, J. Madrid A new proof of the description of the
convex hull of space curves with totally positive torsion. arXiv:2201.12932
[20] R. van Handel Private communication.
[21] P. Ivanisvili, R. van Handel, A. Volberg Improving constant in end-point
Poincar´e inequality on Hamming cube. arXiv:1811.05584
53

=== PAGE 63 ===
[22] P. Ivanisvili, R. van Handel, A. Volberg Rademacher type and Enflo type
coincide. Annals of Mathematics, vol. 192, Issue 2, pages 665-678.
[23] G. P´olya, G. Szeg¨o, Problems and Theorems in Analysis. Vol. II, Springer-Verlag,
New York, 1976
[24] M. Talagrand Isoperimetry, logarithmic Sobolev inequalities on the discrete cube,
and Margulis graph connectivity theorem. Geom. Funct. Anal. 3 (1993). no. 3, 275-285
[25] Y. Stone L1 −L2 comparison results for biased Rademacher sums to appear.
[26] D. Berend, A. Kontorovich A sharp estimate of the binomial mean absolute de-
viation with applications. Statistics & Probability Letters. 83 pp. 1254-1259 (2013,4)
54
