=== PAGE 1 ===
IMPROVING CONSTANT IN END-POINT POINCAR´E INEQUALITY ON
HAMMING CUBE
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
Abstract. We improve the constant π
2 in L1-Poincar´e inequality on Hamming cube. For Gauss-
ian space the sharp constant in L1 inequality is known, and it is p π
2 . For Hamming cube the
sharp constant is not known, and p π
2 gives an estimate from below for this sharp constant.
On the other hand, L. Ben Efraim and F. Lust-Piquard have shown an estimate from above:
C1 ≤π
2 . There are at least two other independent proofs of the same estimate from above (we
write down them in this note). Since those proofs are very diﬀerent from the proof of Ben Efraim
and Lust-Piquard but gave the same constant, that might have indicated that constant is sharp.
But here we give a better estimate from above, showing that C1 is strictly smaller than π
2 . It is
still not clear whether C1 > p π
2 . We discuss this circle of questions.
1. Introduction
In [1] the following inequality is proved
(1.1)
∥f −Ef∥1 ≤π
2 ∥∇f∥1,
where f is a function on Hamming cube {−1, 1}n. Pisier proved that in Gaussian space the
following Poincar´e inequality holds with the sharp constant
p
π/2:
(1.2)
∥f −Ef∥1 ≤
rπ
2 ∥∇f∥1,
If we denote by C1 the best constant in the Poincar´e inequality in L1({−1, 1}n), then we see that
rπ
2 ≤C1 ≤π
2 .
In this note we improve the right estimate. Let ∆be Laplacian on {−1, 1}n (negative operator).
Let Pt := et∆be a corresponding semi-group.
The proof of (1.1) in [1] is striking. To obtain this estimate the authors adapt Pisier’s proof to
the Hamming cube. For this they lift the problem about functions to non-commutative problem
about matrices. After that they manage to represent operator Pt as a compression of a semi-group
acting on a non-commutative space of 2n × 2n matrices, and then the rest of the argument relies
on the non-commutative Khinthchin inequality. This lifting of a problem about usual functions
to a non-commutative setting is immensely beautiful and enticing, but also a bit mysterious.
There are “commutative” proofs of the estimate from above in L1({−1, 1}n)-Poincar´e inequal-
ity. We present them in Section 7. They give exactly the same constant π/2 (or worse) as in [1]
but they use a sort of “Bellman function” monotonicity idea. We learnt them from the book of
Bakry–Gentil–Ledoux [2], Chapter 8.
This persistence of π/2 constant in three very diﬀerent proofs could have been suggestive. But
here we prove that sharp constant is smaller than π/2. What it is remains enigmatic.
2. Dual problem
We write a dual problem as follows. Let f ∈L1({−1, 1}n) and g ∈L∞({−1, 1}n). Let Ef = 0.
Then
f −Ef = −
Z ∞
0
d
dtPtf dt .
2010 Mathematics Subject Classiﬁcation. 42B20, 42B35, 47A30.
Volberg is partially supported by the NSF DMS-1600065.
1
arXiv:1811.05584v5  [math.PR]  1 Jun 2019

=== PAGE 2 ===
2
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
and hence
(f −Ef, g) = −
Z ∞
0
(∆Ptf, g) dt = −
Z ∞
0
(∆f, Ptg) dt =
−(∆f,
Z ∞
0
Ptg dt) = −(∇f,
Z ∞
0
∇Ptg dt) .
Therefore,
E|f −Ef| ≤∥∇f∥1 ·
sup
∥g∥∞≤1



Z ∞
0
∇Ptg dt



∞≤∥∇f∥1 ·
sup
∥g∥∞≤1
Z ∞
0
∥∇Ptg∥∞dt .
So we will estimate
sup
∥g∥∞≤1
Z ∞
0
∥∇Ptg∥∞dt
by Cdual∥g∥∞. We will prove that Cdual < π
2 . We just showed that C1 ≤Cdual. There is a very
good possibility that C1 < Cdual. We discuss that in this note, where we talk about the Curl
space–see below in Section 13.
3. Integral operator
Let us consider g 7→∇Ptg as an integral operator and let us write down its kernel. Con-
sider independent random variables {y1, . . . , yn}, which are ρ-correlated with standard Bernoulli
independent random variables {x1, . . . , xn}.
If yi = xi with probability
1+ρ
2
and yi = −xi
with probability 1−ρ
2 , then we have them exactly ρ-correlated Eyixi = ρ. Given a ﬁxed string
x ∈{−1, 1}n, we can write
Ey∼Nρ(x)yS = ρ|S|xS,
where S is a multi-index of 0 and 1, xS is a corresponding polynomial, and y ∼Nρ(x) means
distribution ρ-correlated independent random variables.
Putting ρ = e−t we get
Ey∼Nρ(x)g(y) = (Ptg)(x) .
Since
∇Ptg = e−tPt∇g
we can apply this to ∂1g.
(Pt∂1g)(x) = Ey∼Nρ(x)∂1g(y) .
Now we want to ﬁnd ϕ1(y) such that
Ey∼Nρ(x)∂1g(y) = Ey∼Nρ(x)ϕ1(y)g(y) .
But ∂1 eliminates all polynomials that do not have y1 and cross oﬀy1 from other polynomials.
So ϕ1 such that
Ey∼Nρ(x)ϕ1(y)yk = δ1k .
Clearly the following ϕ1 works:
ϕ1(y) = y1 −Ey∼Nρ(x)y1
V ar[y1]
= y1 −ρx1
1 −ρ2
= y1 −e−tx1
1 −e−2t
.
Combining all that we get the integral representation of (Pt∇g)(x):
(3.1)
(Pt∇g)(x) = Ey∼Nρ(x)

(y1 −e−tx1
1 −e−2t , . . . , yn −e−txn
1 −e−2t
)g(y)

.
From (3.1) we get (λ = λ1, . . . , λn) (a unit vector in Rn)
(3.2)
∥(Pt∇g)∥∞≤
1
√
1 −e−2t ∥g∥∞






sup
λ:∥λ∥2=1
Ey∼Nρ(x)

n
X
j=1
λj
yj −e−txj
√
1 −e−2t







∞
To estimate the right hand side without loss of generality we can assume that xj = 1 for all
j = 1, . . . , n. Indeed, this follows from the fact that we are taking supremum over all λ ∈Sn−1,

=== PAGE 3 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
3
and since y −e−txj takes values xj(1 −e−t) and −xj(1 + e−t) we can absorb the signs xj into
the values of λj.
The random variables
yj−e−t
√
1−e−2t are independent, and they have the same distribution as random
variables ξt
i that assume value
q
1−e−t
1+e−t with probability 1+e−t
2
and −
q
1+e−t
1−e−t with probability
1−e−t
2
.
Hence, for ∥g∥∞≤1, we have
(3.3)
∥∇(Ptg)∥∞=
e−t
√
1 −e−2t
sup
λ:∥λ∥2=1


 X
λjξt
j


L1(P) .
Notice that
R
ξt
j dP = 0,
R
(ξt
j)2 dP = 1. Thus, there is a trivial estimate
(3.4)
∥∇(Ptg)∥∞=
e−t
√
1 −e−2t
sup
λ:∥λ∥2=1


 X
λjξt
j


L2(P) ≤
e−t
√
1 −e−2t .
The ﬁrst estimate here is just (3.3), the second one is just a trivial fact that ∥P λjξt
j


2
L2(P) =
λ2
1 + · · · + λ2
n = 1.
Using
R ∞
0
e−t
√
1−e−2t dt =
R 1
0
du
√
1−u2 = π
2 we see (1.1) one more time.
To improve this estimate it is suﬃcient to prove the following theorem.
Theorem 3.1. Let p ∈[1
2, 1

. Consider independent random variables εj, j = 1, . . . , n, having
values
q
1−p
p
with probability p and −
q
p
1−p with probability 1−p. Then supλ∈Rn:∥λ∥2=1 ∥P λjεj∥1 =:
q(p) < 1 for p lying in a small interval around 3/4.
Remark 3.2. In fact, the proof will show that q(p) < 1 for all p ∈(1
2, 1).
In the next two section we prove this theorem.
Acknowledgement. We are grateful to Sergei Bobkov who indicated to us the article [3]. The
proof there, even though it is diﬀerent from the proof below, encouraged us.
4. Maximum λ is separated from 1
Everything is real-valued below. We will need the 8-th moment in the calculation below.
Let ξi, i = 1, . . . , n be our random Bernoulli variables with Eξ = 0, Eξ2 = 1, 1−p, p probability
of values
q
p
1−p, −
q
1−p
p , and independent. Let λ = (λ1, . . . , λn) be a point on the unit sphere.
In this section we consider the case
(4.1)
max |λk|2 ≤0.99 .
We want to prove that independently of n under this assumption above and with a certain
ε > 0, which will depend only on a constant p chosen later in (4.7), we will have
(4.2)
max |λk|2 ≤0.99 ⇒E|
X
λiξi| ≤(1 −ε2)
 E(
X
λiξi)21/2 = 1 −ε2 .
Denote Y := | P λiξi| and notice that if the opposite happens for some λ satisfying (4.1), then
E(Y −EY )2 = 1 −
 EY
2 < 1 −(1 −ε2)2 ≤2ε2 .
So if (4.2) does not hold, then on a large probability Y is close to EY (and EY is close to 1 of
course) for certain λ satisfying (4.1). Hence, for this λ,
with probability
1 −2ε
one has
|
X
λiξi| −1
2 ≤ε + 2ε2 .

=== PAGE 4 ===
4
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
We took here into account that if the opposite to (4.2) happens, then 0 ≤1−EY ≤1−
√
1 −2ε2.
In particular, we obtain
P
|
X
λjξj|2 −1
 ≤
p
ε + 2ε2(1 +
p
ε + 2ε2)

≥1 −2ε
(4.3)
Now let us bring (4.3) (with a certain ε chosen below with the help of constant B from (4.5)
below) to a contradiction if (4.1) holds.
Consider ℓ= P λiξi, then
ℓ2 =
X
λ2
i ξ2
i + 2
X
i<j
λiλjξiξj .
So
ℓ4 =
X
λ4
i ξ4
i + 2
X
i<j
λ2
i λ2
jξ2
i ξ2
j + 4
X
i<j
λ2
i λ2
jξ2
i ξ2
j +
4
X
i<j,k<m,(i,j)̸=(k,m)
λiλjξiξjλkλmξkξm + 4
X
m, i<j
λ2
mξ2
mλiλjξiξj
(4.4)
Of course Eℓ2 = 1. Now calculate V ar[ℓ2]. By (4.4) we have
V ar[ℓ2] = E(ℓ2 −1)2 = Eℓ4 −2Eℓ2 + 1 = Eℓ4 −1 =
Eξ4 X
λ4
i + 6
X
i<j
λ2
i λ2
j −1 ≥
X
λ4
j + 3(1 −
X
λ4
j) −1 =
2(1 −
X
λ4
j) ≥2 · 0.01 = 0.02
Here we have used Eξ4 ≥1 and λ4
j ≤0.99λ2
j for all j = 1, . . . , n.
Let X := |ℓ2 −1|. If
(4.5)
EX4 ≤B(EX2)2,
then the Paley–Zygmund estimate applied to X2 says
P(X ≥t(EX2)1/2) ≥(1 −t2)2 1
B ,
t ∈(0, 1) .
Let us take (4.5) for granted and let us then see what Paley–Zygmund estimate gives us with
t = 1/2. Since we estimated EX2 from below as follows
EX2 ≥0.02
we get
P(|ℓ2 −1| ≥0.07) ≥P(X ≥1
2
√
2
10 ) ≥9
16
1
B .
(4.6)
This contradicts (4.3). Indeed, summing up (4.3) and (4.6) we obtain
(4.7)
P(|ℓ2 −1| ≥0.07) + P
 |ℓ2 −1| ≤
p
ε + 2ε2(1 +
p
ε + 2ε2)

≥
9
16B + 1 −2ε .
Now it remains to take ε suﬃciently small to get a contradiction.
So if we prove (4.5) with B depending on p but independent of n, we would prove that we
have the drop in norm as in (4.2) with ε suﬃciently small depending only on p.
To see (4.5) with B independent of n and independent of λi satisfying (4.1), P λ2
i = 1, let us
recall that X = |ℓ2 −1| and we already estimated EX2 = E(ℓ2 −1)2 ≥0.02 from below, and this
estimate depends only on assumption (4.1).
To prove (4.5) we now just need to estimate EX4 = E(ℓ2 −1)4 from above by C(p) < ∞. For
this we need only to estimate E ℓ8. Looking at (4.4), we square it and integrate. It is clear then
that only sums involving λ2m
k , m = 1, 2, 3, 4, will survive. It is now easy to see that E ℓ8 ≤C(p),
where C(p) is bounded if we do not make p →1. This just because Pn
j=1 λ2m
j
≤1, m = 1, 2, . . . ,
and because of the obvious estimate E |ξi|2m ≤K(p, m, δ) < ∞if p ∈[1
2, 1 −δ

.

=== PAGE 5 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
5
Hence, we have
(4.8)
EX4 ≤B(p)(EX2)2,
B(p) ≤Bδ < ∞, p ∈[1/2, 1 −δ

.
So for p = 3
4 and also for p in a small ﬁxed (independent of n) neighborhood of p = 3
4 we have
a deﬁnite drop in norm. In other words, we have the H¨older inequality with constant strictly
smaller than 1 independently of n and independent of λ satisfying (4.1).
5. Maximum is close to 1
What if the maxk |λk|2 =: λ2
1 is in [0.99, 1]? Here we should think that p ∈(1
2 + δ, 1

. For
example p is in a small ﬁxed interval around 3
4.
Then we write for p = 3
4:
E|
X
λiξi| ≤λ1E|ξ1| + E|
n
X
i=2
λiξi| ≤λ1E|ξ1| +
 E|
n
X
i=2
λiξi|21/2
≤2
p
(1 −p)p +
q
1 −λ2
1 ≤
√
3
2 + 1
10 < 0.87 + 0.1 = 0.97.
Again we have a ﬁxed drop in H¨older inequality independent on n. And the same drop happens
trivially in a small neighborhood of p = 3
4, and this neighborhood does not depend neither on n
nor on λ such that maxk |λk|2 ∈[0.99, 1]
6. Bellman proof of Maurey–Pisier estimate on gaussian space
We want to explain two proofs of L1-Poincar´e inequality on Hamming cube that can be derived
from the literature.
We already mentioned that there are other proofs of the estimate E|f −Ef| via C E|∇f| on
Hamming cube. These can be called “Bellman function proofs”, they also gave C = π
2 . Let us
brieﬂy recall one of them. First we recall how to use “Bellman function approach” to derive the
sharp constant p π
2 in gaussian space.
The proof from [2] below is longer than a very short proof of Maurey–Pisier, but it has the
advantage that it can be somewhat generalized to Hamming cube L1-Poincar e inequality.
Let Φ(x) be the gaussian error function,
Φ(x) =
1
√
2π
Z x
−∞
e−y2/2 dy .
Let us consider the “gaussian isoperimetric proﬁle”:
I = Φ′ ◦Φ−1 : [0, 1] →
h
0,
1
√
2π
i
.
Let us ﬁrst prove Maurey–Pisier estimate by “Bellman function” approach borrowed from [2],
Chapter 8. Another, and more elegant proof, can be found in [12]. But it is very “gaussian” and
diﬃcult to invent a simple way to adapt it to the Hamming cube situation. In a certain sense
paper [1] does such an adaptation but in a very fascinating non-obvious way.
Let Pt = et∆denote the Ornstein–Uhlenbeck semigroup on Rn, ∆is the Ornstein–Uhlenbeck
Laplacian.
Function I2 will play the part of “Bellman function” in the sense that a certain
monotonicity involving the semigroup Pt and function I2 will be crucial. We ﬁrst consider only
f such that 0 ≤f ≤1. Obviously,

I(Ptf)
2 −

Pt(I(f))
2 = −
Z t
0
d
ds

Ps(I(Pt−sf))
2 ds

=== PAGE 6 ===
6
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
Combine this with
−d
ds

Ps(I(Pt−sf))
2 = −2Ps(I(Pt−sf)) · Ps

∆
 I(Pt−sf)

−I′(Pt−sf) · ∆Pt−sf

=
−2Ps(I(Pt−sf)) · Ps

I′′(Pt−sf) · |∇Pt−sf|2

= 2Ps(I(Pt−sf)) · Ps
|∇Pt−sf|2
I(Pt−sf)

≥
2Ps(I(Pt−sf)) ·

Ps|∇Pt−sf|
2
Ps(I(Pt−sf)) =

Ps|∇Pt−sf|
2 .
The third equality here is because I′′ = −1
I . The inequality is just Cauchy-Schwartz inequality:
R A2
B dµ ≥[
R
A dµ]2
R
B dµ . The second equality is the chain rule in this form: for any smooth G and test
function g on Rn
(6.1)
∆G(g) = G′(g)∆g + G′′(g)|∇g|2 .
We warn the reader that only this last simple equality will fail on the cube.
Let us combine the estimate
(6.2)

I(Ptf)
2 −

Pt(I(f))
2 ≥2
Z t
0

Ps|∇Pt−sf|
2 ds,
which has been just obtained, with the following well-known (and easy, see, e. g., [2]) estimate
for the Ornstein-Uhlenbeck semigroup:
(6.3)
|∇Psg| ≤e−sPs|∇g| .
Then we get

I(Ptf)
2 −

Pt(I(f))
2 ≥2
Z t
0
e2s|∇Ptf|2 ds .
Thus
0 ≤f ≤1 ⇒|∇Ptf|2 ≤
1
e2t −1
 
I(Ptf)
2 −

Pt(I(f))
2
≤

I(Ptf)
2
e2t −1
,
and so
0 ≤f ≤1 ⇒|∇Ptf| ≤
I(Ptf)
√
e2t −1
≤
1
√
2π
1
√
e2t −1
,
Hence,
(6.4)
0 ≤f ≤1 ⇒
Z ∞
0
|∇et∆f|dt ≤
1
√
2π
Z ∞
0
1
√
e2t −1
dt =
1
√
2π
π
2 = 1
2
rπ
2 .
Finally, this immediately implies
(6.5)
Z ∞
0
|∇et∆f|dt ≤
rπ
2 ∥f∥∞.
This gives the sharp constant in L1-Poincar´e inequality on gaussian space:
(6.6)
Eg|f −Ef| ≤
rπ
2 Eg|∇f| .
This proof can be somewhat generalized to Hamming cube L1-Poincar e inequality. Since the
simple chain rule (6.1) will not work, the proof should be modiﬁed and the constant jumps:
strangely enough, it becomes π
2 . Here is the reasoning.
It would be nice to have on Hamming cube Cn the variant of our usual relationship (6.1), e.
g., to have it in this form:
I′(g)∆g −∆[I(g)] ≥c[−I′′(g)]|∇g|2
with some constant c, c ≤1. This is how we wish to replace (6.1), which is false on Hamming
cube. On gaussian space this is equality with c = 1 as we saw in (6.1) with G = I

=== PAGE 7 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
7
7. Bellman proofs of Ben Efraim–Lust-Piquard estimate on Hamming cube
On cube this becomes two point inequality
−xj∂jg · I′(g) + xj∂j(I(g)) ≥c[−I′′(g)]|∂jg|2,
where ∂jg = (g(xj = 1) −g(xj = −1))/2. Or, denoting g(xj = 1) =: b, g(xj = −1) =: a:
−(b −a)I′(b) + (I(b) −I(a)) ≥c
2[−I′′(b)](a −b)2 ≥0 .
This is
(7.1)
I(b) −I(a) −I′(b)(b −a) + c
2I′′(b)(a −b)2 ≥0
that suppose to be valid for all pairs a, b in [0, 1]. Fix a and tend b to one of the end points 0 or
1. Let, for example, b →0. Notice that I′′(b) →−∞as −1
b
1
√
log 1/b, and notice that I′(b) →+∞
as
p
log 1/b. Hence (7.1) never can be true for b allowed to tend to end points.
We saw that (7.1) cannot hold for all pairs a, b ∈[0, 1].
So our ﬁrst try to circumvent the lack of the chain rule is not successful.
But we can ask another question: what is the largest possible constant k > 0 such that
I(b) −I(a) −I′(b)(b −a) −k (a −b)2/2 ≥0
∀a, b ∈[0, 1]?
(7.2)
The answer of course is obvious, k =
√
2π. Indeed,
I(b) −I(a) −I′(b)(b −a) + 1
2 max
c∈[0,1][I′′(c)](a −b)2 ≥0,
∀a, b ∈[0, 1],
(7.3)
that is
I(b) −I(a) −I′(b)(b −a) −
√
2π(a −b)2/2 ≥0 .
To check that constant k in (7.2) cannot be bigger than
√
2π just make a and b go to 1/2.
The previous estimate (7.3) gives us
(7.4)
−xj∂jg · I′(g) + xj∂j(I(g)) ≥min[−I′′(g)]|∂jg|2 =
√
2π|∂jg|2,
Or,
(7.5)
I′(g)∆g −∆[I(g)] ≥
√
2π|∇g|2
Let now ∆be the Laplacian on Hamming cube, and Pt = et∆be the corresponding ﬂow on
cube. Then we get the analog of (6.2) (but without squares over [·]):
(7.6)

I(Ptg)

−

Pt(I(g))

≥
√
2π
Z t
0

Ps|∇Pt−sg|2
ds ≥
√
2π
Z t
0

Ps|∇Pt−sg|
2 ≥
√
2π|∇Ptg|2
Z t
0
e2sds,
(7.7)
1
2(e2t −1)
√
2π|∇et∆g|2 ≤I(et∆g) −et∆I(g) ≤I(et∆g) ≤
1
√
2π
Or,
1
2(e2t −1)
√
2π|∇et∆g|2 ≤
1
√
2π
Hence, for 0 ≤g ≤1 we have
(7.8)
|∇et∆g∥∞≤
1
√
2π
√
2
√
e2t −1
Hence for any bounded positive g
∥∇et∆g∥∞≤
1
√
2π
√
2
√
e2t −1
∥g∥∞.

=== PAGE 8 ===
8
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
Now
Z ∞
0
1
√
e2t −1
dt = π
2 .
So for positive g
(7.9)
Z ∞
0
∥∇et∆g∥∞dt ≤π
2 ·
1
√π∥g∥∞.
So for all g,
(7.10)
Z ∞
0
∥∇et∆g∥∞dt ≤√π∥g∥∞.
This is worse than π
2 ∥g∥∞. Looking at the above proof, we immediately see that I = Φ′ ◦Φ−1
being optimal for the estimate in gaussian space might be not optimal on cube. In fact, replacing
∆(I(Pt−sf)

−I′(Pt−sf) · ∆Pt−sf by ∆(B(Pt−sf)

−B′(Pt−sf) · ∆Pt−sf we can see that we
should ﬁnd B : [0, 1] →R+ such that
(7.11)
MB :=
max[0,1] B(x)
min[0,1][−B′′(x)] →min .
If we call this minimum M, we obtain (just by repeating the reasoning of Section 6) the following
estimate:
0 ≤f ≤1 ⇒|∇Ptf| ≤
√
2
√
M
1
√
e2t −1
,
For B = I we have MI =
1
2π. And this implies (7.9), and (7.10).
But the choice B(x) = x(1 −x) gives minimum in (7.11), and it is 1
8. Then
0 ≤f ≤1 ⇒
Z ∞
0
|∇Ptf|dt ≤
√
2 1
2
√
2
π
2 = π
4 .
Hence,
Z ∞
0
|∇Ptf|dt ≤π
2 ∥f∥∞.
And this way we get a commutative proof of Ben Efraim–Lust-Piquard estimate:
E|g −Eg| ≤π
2 E|∇g| .
8. Discussion
8.1. Functions with only two values have constant p π
2 in L1-Poincar´e inequality.
Incidentally, the question of validity of the Gaussian inequality constant p π
2 on the hypercube is
particularly mysterious, for the following reason. In the Gaussian case, the extremizer that attains
the optimal constant is the indicator function of a halfspace of probability 1/2. In particular,
it is a fortiori a function of the form f = 1A. But if we restrict the hypercube L1-Poincar´e
inequality only to indicators f = 1A, then the inequality does hold with the same constant as in
the Gaussian case and this is optimal.
This follows from Bobkov’s inequality on the cube. In fact, it is known that
(8.1)
max
p∈[0,1]
2p(1 −p)
I(p)
=
rπ
2 .
Now notice that any function f having only two values can be made to a function having
values 0, 1 by linear transformation f →af + b. And this transformation does not change the
constant in Poincar´e inequality.Then we can think that 1 is assumed with probability p ∈(0, 1).
Hence Ef = p, E|f −Ef| = 2p(1 −p).
Let B(x, y) :=
p
I2(x) + y2. Here I(x) = Φ′ ◦Φ−1(x), where Φ is the Gaussian error function.
It is called Bobkov’s function and Bobkov [4] proved that for any f : {−1, 1}n →[0, 1] the
following inequality holds:
(8.2)
I(Ef) = B(Ef, 0) ≤E

B(f, |∇f|)

.

=== PAGE 9 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
9
For functions as above having values 0, 1 only, this becomes
(8.3)
I(Ef) ≤E|∇f| .
So we have for function as above (that is having only two values)
I(p)
2p(1 −p)E|f −Ef| = 2p(1 −p)
I(p)
2p(1 −p) = I(p) ≤E|∇f| ,
or
(8.4)
E|f −Ef| ≤max
p∈[0,1]
2p(1 −p)
I(p)
E|∇f| ≤
rπ
2 E|∇f| .
So if the L1−Poincare inequality were to not hold for general functions with the optimal
constant, that begs the question what extremizers could possibly look like: then they cannot
look like indicators, as they do in the Gaussian case.
Of course, in the continuous case one can re-derive the L1-Poincar´e inequality from its set
version, but this does not work in the discrete case as it requires the co-area formula.
8.2. Lipschitz properties in Gaussian setting. In this subsection let 0 ≤f ≤1. In Section 6
we have seen that the following holds in Gaussian setting for the Ornstein–Uhlenbeck semi-group
Pt and Bobkov’s function I = Φ′ ◦Φ−1:
(8.5)
I(Ptf)2 −(PtI(f))2 ≥(e2t −1)|∇Ptf|2.
∇Psf = e−sPs∇f .
For our purposes, we ignore the second term on the left. That is, we are interested in the following
slightly weaker inequality:
(8.6)
I(Ptf)2 ≥(e2t −1)|∇Ptf|2.
As is already remarked by Bakry-Ledoux, this inequality has the following equivalent formulation:
(8.7)
(e2t −1)|∇Φ−1(Ptf)|2 ≤1.
Indeed, this follows immediately from the chain rule. (Note that the equivalence between (8.6)
and (8.7) does not hold on the hypercube where the chain rule does not hold; so not clear which
is more natural.)
In other words, in the Gaussian case, the estimate we seek has a very clean reformulation:
the quantity Φ−1(Ptf) (which is precisely what appears, say, in Ehrhard inequality) is Lipschitz
with universal constant depending only on t. This estimate is very useful, e.g. it was used it in
the characterization of equality cases of Ehrhard inequality [15].
Now we want to give another formulation of (8.7) that is even more basic. We claim that (8.7)
should be viewed as a sort of dual isoperimetric inequality for Gaussian measure.
We have not seen discussion of such inequalities in the literature but it surely seems natural. To
be precise, we claim (8.7) is equivalent to the following extremal statement: among all functions
0 ≤f ≤1, the quantity |∇Φ−1(Ptf)|
is maximized pointwise when f = 1H, where H is a
half-space.
Indeed it suﬃces to note that equality in (8.7) holds pointwise whenever f = 1H is any half-
space.
This shows both that the inequality is sharp and that it has a sort of isoperimetric
interpretation.
It is not at all clear what the analogous considerations might be on the hypercube.
9. Paradoxical experiments
Let us consider again the L1-estimate on the cube: E|f −Ef| ≤C∥∇f∥1. Deﬁne g : R →R
such that g(z) = 1 for z > 0, g(z) = 0 for z = 0 and g(z) = −1 for z < 0. Let fn(x1, · · · , xn) =
g
 Pn
j=1 xj
√n

.
Consider ﬁrst n ≫1 with n being odd.
Obviously Efn = 0 and E|fn| = 1. On the other hand, for each i = 1, · · · , n, easy to check
that |∂ifn| takes value only 0 or 1.

=== PAGE 10 ===
10
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
Furthermore, denoting Zn = Pn
j=1 xj, it is not diﬃcult to check that |∂ifn| = 1 if and only if
either Zn = 1, xi = 1, or Zn = −1, xi = −1.
From this we get |∇fn| =
q
n+1
2
or 0, and the number of vertices where |∇fn|̸ = 0 is precisely
2
  n
n+1
2

. Therefore,
∥∇fn∥1 = 1
2n ·
 n
n+1
2

·
r
n + 1
2
· 2 =
2
√π · (1 + on(1)),
(9.1)
as n tend to inﬁnity.
Now consider n ≫1 with n being even. Then Efn = 0 and E|fn| = 1 −on(1). On the other
hand, now we will be jumping from ±1 values to 0 values while calculating ∂ig, hence:
∥∇fn∥1 = 2−n ·
n
n
2

· √n · 1
2 + 2−n ·

n
n
2 + 1

·
rn
2 + 1 · 1
2 · 2 = 1 +
√
2
√
2π
· (1 + on(1)).
The above two cases show that for 2-valued g one cannot saturate the optimal constant for
the discrete Hamming cube case. For the odd n case we get the constant
Codd,charact.function =
√π
2
<
rπ
2 ,
and for the even n case we get
Ceven,charact.function = √π
√
2
√
2 + 1 <
rπ
2 .
Amusingly, if we take g to be a smooth function, then it is not diﬃcult to check that for
fn = g((Pn
j=1 xj)/√n), one has
|∂jfn| =
1
√n ·
g′Pn
j=1 xj
√n
 + O(n−1
2 )

.
From this one gets
E|fn −Efn|
E|∇fn|
→Eγ|g(z) −Eγg(z)|
Eγ|g′|
,
n →∞,
(9.2)
where Eγ denotes expectation with respect to standard Gaussian measure on R.
In particular, choosing function g to be a smooth approximation to 1R+ and then choosing fn,
fn(x1, · · · , xn) = g
 Pn
j=1 xj
√n

, we conclude that the right hand side of (9.2) is as close to p π
2 as
we wish. Then making n →∞we achieve that the left hand side is also as close to p π
2 as we
wish.
But these fn will have values −1, 1 and many values in between. it is possible to prove that we
cannot achieve the constant p π
2 by testing symmetric functions having values −1, 1 or −1, 0, 1
alone. The constants in L1-Poincar´e inequality for such functions are uniformly in n strictly
smaller than pπ
2 .
10. Symmetric functions
Let us consider functions having only two values, but symmetric. It is convenient to think
now that functions have only values 0, 1, and let us consider balanced functions:
Ef = 1
2 .
Let us now think that xi are independent standard 0, 1 Bernoulli random variables. Function f
has the same value on Rk := {x : x1 + . . . xn = k}. In the previous section we considered the
case, when f had one value on all Rk with k < n
2 and another value on all Rk, k > n
2 (for n odd,
say).

=== PAGE 11 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
11
Now let us consider more general symmetric function. As always, being balanced, it will have
E|f −Ef| = 1
2, so we need to minimize E|∇f|, or, to minimize E|∇1A|, with |A| = 1
2. Clearly,
it is better for us not to allow 1A to oscillate in too many places. One place of oscillation was
considered in the previous section.
Let us show now that by choosing two places of oscillation we can only make |A|/E|∇1A|
smaller by making E|∇1A| bigger.
So choose a = Φ−1(3
4) and put k =
n
2 +a1
2
√n

. Let A be the set where x1 +. . . xn ∈[n−k, k].
Then
E|∇1A| ≈2
h1
2
√
n −k
n
k
 1
2n + 1
2
√
k + 1

n
k + 1
 1
2n
i
.
By de Moivre–Laplace formula
1
2n
n
k

≈
2
√nφ(a) =
2
√nI(3
4) .
Hence, since
√
k ≈
√n
√
2 and
√
n −k ≈
√n
√
2 , we get the following:
E|∇1A| ≈2
√
2 I
 3
4

.
Hence, for f = 1A, with A described above, we have
E|f −Ef| ≤
1
4
√
2 I
  3
4
E|∇f| .
Constant Codd,charact.function =
√π
2 from the previous section is nothing else than
1
2
√
2 I( 1
2 ). Clearly
1
4
√
2 I
  3
4
 =
1
4
√
2 I
  1
4
 <
1
2
√
2 I(1
2),
because 2I
  1
4

> 2I(1
2) by concavity of function I.
The conclusion: the symmetric function in this section gives a smaller constant in L1-Poincar´e
inequality than a simpler characteristic function in the previous section. It is very believable
that among balanced symmetric functions with only two values it is the optimal one, thus,
max E|f −Ef|
E|∇f|
=
√π
2 .
Remark 10.1. Consider this maximum over all functions having two values (without the loss
of generality, just values 0, 1). We saw that it is at most p π
2 in this general setting. But is this
constant attained? For balanced symmetric functions, it is now very believable (by the discussion
in the present section) that maximum above is much smaller, namely
√π
2 .
But even for all
functions with two values (with no symmetries whatsoever) that maximum can be smaller than
p π
2 . In Proposition 3.1 on page 259 of [5] functions f = 1An(a) are considered. Here a ∈R, and
An(a) =
n
x : x1 + · · · + xn −n
2
1
2
√n
≤a
o
,
where xi are standard independent Bernoulli variables with values 0, 1. If a = Φ−1(α), α ∈[0, 1],
then
E|1An(a) −E1An(a)| = 2α(1 −α) .
On the other hand, E|∇1An(a)| is calculated on page 259 of [5]:
E|∇1An(a)| ≈
√
2 φ(a) =
√
2 I(α) .
Whence,
(10.1)
lim
n→∞max
α∈[0,1]
E|1An(a) −E1An(a)|
E|∇1An(a)|
=
1
2
√
2 I(1
2) =
√π
2 ,
a = Φ−1(α), α ∈[0, 1] .

=== PAGE 12 ===
12
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
Remark 10.2. We saw above function a certain f having three values 1, 0, −1, for which the ratio
E|f−Ef|
E|∇f|
is bigger than
√π
2 , namely it is asymptotically
√
2
√
2+1
√π. We also saw that allowing more
values we can saturate the constant pπ
2 . It is not clear whether we can surpass this constant.
11. Kernel representation of operator T
Operator f →
R ∞
0 ∇et∆f dt can be written also as follows:
Tf =
Z ∞
0
e−tet∆∇f dt =
Z ∞
0
∇et∆f dt .
Notice that we cannot loose e−t here, if we drop e−t, the expression will become undeﬁned for,
say, f = x1. We cannot either consider anything like
f →∇
Z ∞
0
et∆f dt = ∇∆−1 f,
because this latter expression is undeﬁned on f = 1.
However, we can remedy this drawback just by introducing the orthogonal projection P0 onto
functions on Hamming cube that have average zero: P0f := f −Ef. Then we can write down T
in the following form
(11.1)
Tf = ∇∆−1P0f .
But for operator T deﬁned above, it is easy to give its matrix (kernel) representation. For that
let us double the cube: C2n = {(x′, x) ∈Cn × Cn} and consider
Π(x′, x) := Πt(x′, x) := Πn
k=1(1 + e−tx′
kxk) .
If dµ(x′) is the uniform measure on the ﬁrst Cn and if x in the second Cn get ﬁxed, we get a
new probability measure
dP(x′) := dPx(x′) := Π(x′, x) dµ(x′) .
It is very easy to see that it is indeed a probability measure for any x.
In these terms it is easy to compute the matrix of operator T. In fact, we have already done
this above: let K(x′, x) be the kernel representing T in the sense that
Tf(x) =
Z
Cn K(x′, x)f(x′) dµ(x′) .
It is a vector kernel, and let Ti corresponds to
R ∞
0 ∂iet∆f dt, where ∂i is the elimination operator
for xi. Let Ki be the kernel of Ti in the just mentioned sense. Then
(11.2)
Ki(x′, x) =
Z ∞
0
e−t
√
1 −e−2t
x′
i −e−txi
√
1 −e−2t Π(x′, x) dt .
This we already had in the third Section essentially. Now let us rewrite it conveniently.
(11.3)
K1(x′, x) =
Z ∞
0
e−t
1 −e−2t (x′
1 −e−tx1) Π(x′, x) dt .
This does not look very nice because of t ≈0 seems like creating a problem. But it does not,
because this expression can be rewritten as follows:
(11.4)
K1(x′, x) =
Z ∞
0
e−t
1 −e−2t x′
1 (1 −e−tx′
1x1)(1 + e−tx′
1x1)Πn
k=2(1 + e−tx′
kxk) dt ,
which is
(11.5)
K1(x′, x) =
Z ∞
0
e−t
1 −e−2t x′
1 (1 −e−2t)Πn
k=2(1 + e−tx′
kxk) dt ,
which is
(11.6)
K1(x′, x) =
Z ∞
0
e−tx′
1 Πn
k=2(1 + e−tx′
kxk) dt ,

=== PAGE 13 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
13
Now the kernel of T is K = (K1, K2, . . . , Kn), where Ki is
(11.7)
Ki(x′, x) =
Z ∞
0
e−tx′
i Πn
k̸=i(1 + e−tx′
kxk) dt ,
i = 1, . . . , n .
Recall the notation Cn = {−1, 1}n. We are interested in the norm of the integral operator
with kernel K = (K1, . . . , Kn) as the operator from L∞(Cn) →L∞(Cn; ℓ2
n).
Given x, y ∈Cn we write z = y · x = (y1x1, . . . , ynxn) ∈Cn.
Kernel Ki(x′, x) can be written down as Ki(x′, x) = xi ˜Ki(x′, x), where
˜Ki(x′, x) :=
Z ∞
0
e−tx′
ixi Πn
k̸=i(1 + e−tx′
kxk) dt,
and we see that this is a kernel of the form ki(x′ · xi), that is, it is a convolution kernel.
We use it with measure dµ(x′) that is invariant, meaning that dµ(x′ · x) is the same measure.
Notice also that the facts that Ki(x′, x) = xi ˜Ki(x′, x), xi = ±1, imply that the norm of operator
with kernel K is the same as the norm of operator with kernel ˜K – we mean here the action from
L∞(Cn) →L∞(Cn; ℓ2
n).
Let us write
(11.8)
mi,z := 2−nKi(z, 1) = 2−n
Z ∞
0
e−tzi Πn
k̸=i(1+e−tzk) dt = 2−n
Z 1
0
zi Πn
k̸=i(1+ρzk) dρ ,
i = 1, . . . , n ,
The reasoning that we have just made implies that the norm of the integral operator K is the
same as the norm of the matrix M := (mi,z)i=1,...,n; z∈{−1,1}n as the matrix acting from ℓ∞
2n to ℓ2
n.
In fact, this is just invariance:
Z
Cn
˜K(x′ · x)f(x′)dµ(x′) =
Z
Cn
˜K(y)fx(y)dµ(y),
fx(y) := f(y · x) .
Since f →fx is an isometry in L∞(Cn), we see that the norm of our operators from L∞(Cn)
to L∞(Cn; ℓ2
n) is the same as the norm of matrix M from ℓ∞
2n to ℓ2
n.
Rewriting again, we get:
Ki(z, 1) =
Z 1
0
zi(1 −ρzi)
1 −ρ2
Πn
k=1(1 + ρzk) dρ =
Z 1
0
zi −ρ
1 −ρ2 Πn
k=1(1 + ρzk) dρ ,
i = 1, . . . , n ,
Let us denote by d(z) = dist(z, 1) in Hamming metric. Then for z ∈{−1, 1}n we have:
Πn
k=1(1 + ρzk) = (1 + ρ)n−d(z)(1 −ρ)d(z) .
Thus,
(11.9)
Ki(z, 1) =
Z 1
0
zi −ρ
1 −ρ2 (1 + ρ)n−d(z)(1 −ρ)d(z) dρ ,
i = 1, . . . , n ,
Let Mρ := (mi,z(ρ))i=1,...,n; z∈{−1,1}n be the matrix acting from ℓ∞
2n to ℓ2
n, whose n × 2n matrix
elements are given by the following formula:
(11.10)
mi,z(ρ) := 2−n zi −ρ
1 −ρ2 (1 + ρ)n−d(z)(1 −ρ)d(z) ,
i = 1, . . . , n, z ∈{−1, 1}n , ρ ∈(0, 1) .
Of course, matrix elements mi,z := 2−nKi(z, 1) are just
R 1
0 mi,z(ρ) dρ, and one may wonder
what to do with integration of 1/(1 −ρ2)? But this is easy: if d(z) > 0 then we cancel this
singularity by (1 −ρ)d(z) factor, and if d(z) = 0, then of course z = 1 and instead of factor
1/(1 −ρ2) we have factors (zi −ρ)/(1 −ρ2) = (1 −ρ)/(1 −ρ2) = 1/(1 + ρ) for all i.
To compute the norm of the matrix M = (mi,z) =
R 1
0 Mρ dρ as the matrix acting from ℓ∞
2n to
ℓ2
n one can try to do two diﬀerent things.

=== PAGE 14 ===
14
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
The ﬁrst attempt. Calculate
(11.11)
max
λ, ∥λ∥ℓ2n≤1 Ez

n
X
i=1
λi
Z 1
0
zi −ρ
1 −ρ2 (1 + ρ)n−d(z)(1 −ρ)d(z) dρ

Or one can try to use a rougher estimate as follows.
The second attempt. Calculate
(11.12)
Z 1
0
max
λ, ∥λ∥ℓ2n≤1 Ez

n
X
i=1
λi
zi −ρ
1 −ρ2
 (1 + ρ)n−d(z)(1 −ρ)d(z) dρ
The second attempt is precisely what we have done in Sections 4 and 5, especially see (3.2).
We were not very careful in estimating the quantity in (11.12), we just proved that it is strictly
smaller than π/2.
However, the integrals in (11.11), namely,
mi,z =
Z 1
0
zi −ρ
1 −ρ2 (1 + ρ)n−d(z)(1 −ρ)d(z) dρ
seems to be treatable, they can be written down as certain combinatorial sums.
For example,
mi,1 =
Z 1
0
(1 + ρ)n−1 dρ,
i = 1, . . . , n .
For z = (1, . . . , 1, −1) we have
mi,z =
Z 1
0
(1 + ρ)n−2(1 −ρ) dρ,
i = 1, . . . , n −1 ,
mn,z = −
Z 1
0
(1 + ρ)n−1 dρ .
12. Computer experiment for finding Cdual
Let us consider the quantity
(12.1)
Cdual,n :=
sup
∥g∥L∞({−1,1}n)≤1
∥
Z ∞
0
∇Ptg dt∥∞,
and let us try to ﬁnd its numerical values for small dimensions n.
For n = 2 the optimizer is
g(x1, x2) = min(x1, x2) = (x1x2 + x1 + x2 −1)/2.
In dimensions n = 3, . . . , 7, the optimal value is the same so one can just take two-dimensional
function like g(x1, . . . , xn) = min(x1, x2). Of course, there may be many other optimizers.
The ﬁrst nontrivial dimension where the 2D case is not optimal is n = 8.
We would like to call the attention of the reader that the graph we get is extremely curious.
It seems up to dimension 7, two-dimensional functions are optimal. Then suddenly in dimension
8 there is enough structure to do better with a truly eight-dimensional function.
The optimal value increases only very slowly. If we assume it grows sort of linearly (no reason
it should, just to assume it to make some guesses), then one would extrapolate from the plot that
Cdual,n would reach
p
π/2 only around dimension n = 60. This means that there is probably
little insight to be gained from the speciﬁc structure of low-dimensional optimizers. Also, it is
very diﬀerent than the usual experience, which is that universality phenomena (like CLT) often
kick in at surprisingly low dimension. For example, for Bernoulli εk one has
E|ε1 + ... + ε9|/
√
9| ≈0.82, E|ε1 + ... + ε13|/
√
13| ≈0.81,

=== PAGE 15 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
15
Figure 1. Growth of dual constant with n.
which is quite close to the Gaussian limit
p
2/π ≈0.80. Here, we are very far from the Gaussian
case and seem to approach it only very slowly.
See Fig. 1 for the growth of the dual constant with n. One can see that it grows very slowly
(and does not grow at all for n = 2, . . . , 7). Then it slowly starts to pick up. Since we work with
matrices of size n × 2n, their size grows too fast. We have already noted that the growth on this
ﬁgure suggests that we come close to
p
π/2 only for n = 60 or 70. This experiment is beyond
the computer reach.

=== PAGE 16 ===
16
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
13. Curl space and Cdual
Let us remind the reader that
(f −Ef, g) = −(∇f,
Z ∞
0
∇Ptg dt) .
Therefore,
E|f −Ef| ≤∥∇f∥1 ·
sup
∥g∥∞≤1



Z ∞
0
∇Ptg dt



L∞/Curl ≤
So we need to estimate
(13.1)
C1 :=
sup
∥g∥∞≤1
inf
h∈Curl ∥h +
Z ∞
0
∇Ptg dt∥∞,
where the “Curl” space is the following:
Curl := {h = (h1, . . . , hn) : E(h · ∇ϕ) = 0 , ∀ϕ} .
Since ∇= (∂1, . . . , ∂n), and ∂k is the elimination of xk operator:
∂kϕ = 1
2(ϕxk→1 −ϕxk→−1) .
Space Curl consists of vector functions h = (h1, . . . , hn), such that
(13.2)
∂∗
1h1 + · · · + ∂∗
nhn = 0 .
Here
∂∗
kϕ = xk
1
2(ϕxk→1 + ϕxk→−1) .
In other words, it is a creation operator, that is
∂∗
kxS =
(
xkxS, if k /∈S,
0,
k ∈S .
Space Curl is very large, as the vector functions h such that ∂∗
khk = 0, k = 1, . . . , n, are in
this space. And for that to hold, it is enough for each hk to be of the following form:
(13.3)
hk = xk∂kHk
with arbitrary Hk, k = 1, . . . , n. In fact, space Curl is much larger than that.
To get the value of C1 is the same as to calculate the quantity in (13.1). In the previous
sections we gave some estimates on a potentially bigger quantity Cdual, which is given by the
following formula:
(13.4)
Cdual :=
sup
∥g∥∞≤1
∥
Z ∞
0
∇Ptg dt∥∞,
13.1. Curl space in gaussian setting does not matter. Consider functions in L1(R1, γ1)
orthogonal to all D := {f′ : f ∈C∞
0 (R1)}. Then
Z
hf′dγ1 = 0,
∀f′ ∈D .
Therefore,
−
Z
h′fdγ +
Z
xhfdγ1 = 0,
∀f ∈C∞
0 .
Hence
h′ = xh,
h = C · e
x2
2 .
This does not belong to L1(γ) unless C = 0. So only zero function is in Curl. So in gaussian
setting the Curl space is zero.

=== PAGE 17 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
17
But in dimension 2 and higher curl space unfortunately exists in gaussian setting. In fact, in
2D this space consists of vector functions h = (h1, h2) ∈L1(R2, γ2) such that
(13.5)
(h1)x1 + (h2)x2 = x1h1 + x2h2 ,
which has a solution h1 = −x2, h2 = x1.
In gaussian space, however, we know that
(13.6)
C1 = Cdual ,
where these constants can be seen in (13.1) and (13.4) correspondingly – where Pt should be
understood as Ornstein–Uhlenbeck semi-group.
For n = 1 this follows from the above mentioned fact that Curl = 0 for 1D gaussian case.
Now let n > 1. Let G be the function of one variable that almost give the supremum in
sup
∥g∥∞≤1
∥
Z ∞
0
∇Ptg dt∥∞
for n = 1. Whence,
∥
Z ∞
0
∇P (1)
t
G dt∥∞= ∥
Z ∞
0
e−tP (1)
t
∇G dt∥∞≈
rπ
2 .
Here P (1)
t
is Ornstein–Uhlenbeck semi-group in L1(R1, γ1). Since function G = G(x1), we can
understand the last inequality also with P (n)
t
is Ornstein–Uhlenbeck semi-group in L1(Rn, γn):
∥
Z ∞
0
∇P (n)
t
G dt∥∞= ∥
Z ∞
0
e−tP (n)
t
∇G dt∥∞≈
rπ
2 .
This is because (P (n)
t
g)(x) = (P (1)
t
g)(x1) for g depending only on x1.
14. Combinatorial formulation of Cdual
Constant Cdual, given by Cdual := sup∥g∥∞≤1 ∥
R ∞
0 ∇Ptg dt∥∞is just
Cdual = ∥T∥L∞→L∞,
where T is, e.g. from (11.1), that is, T = ∇∆−1P0.
The norm ∥T∥L∞→L∞is the smallest constant C in the following inequality:
∥∇∆−1P0f∥∞≤C∥f∥∞,
which can be written down as follows
∥∇∆−1f0∥∞≤C inf
a ∥f0 + a1∥∞,
where f0 runs over all functions on Hamming cube that have zero average. Such functions can
be written down as f0 = ∆F, so we plug this representation into the above formula. Notice that
∆−1∆F = F −EF. So we are looking at the best constant C in
∥∇F∥∞= ∥∇(F −EF)∥∞≤C inf
a ∥∆F + a1∥∞.
Denote Hamming graph as (V, E), where vertices are denoted by i = 1, . . . , 2n.
Then the previous best constant squared, namely, C2 (that, is C2
dual) is the best constant in
the following inequality with arbitrary real numbers {ai}2n
i=1:
(14.1)
sup
i∈V
X
j:(i,j)∈E
(ai −aj)2 ≤C2 inf
a∈R sup
i∈V

a +
X
j:(i,j)∈E
(ai −aj)
2
.
In particular, we have proved that with ε > 0 and independent of n
(14.2)
sup
i∈V
X
j:(i,j)∈E
(ai −aj)2 ≤
π
2 −ε
2
sup
i∈V

X
j:(i,j)∈E
(ai −aj)
2
.

=== PAGE 18 ===
18
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
15. Calculations with matrix M. An example when Curl space is essential
Recall that we introduced in (11.10) the following n×2n matrix Mρ := (mi,z(ρ))i=1,...,n; z∈{−1,1}n:
(15.1)
mi,z(ρ) := 2−n zi −ρ
1 −ρ2 (1 + ρ)n−d(z)(1 −ρ)d(z) ,
i = 1, . . . , n, z ∈{−1, 1}n , ρ ∈(0, 1) .
We considered it as acting from ℓ∞
2n to ℓ2
n.
Of course, matrix elements mi,z := 2−nKi(z, 1) are just
R 1
0 mi,z(ρ) dρ. Again we considered it
as acting from ℓ∞
2n to ℓ2
n, and we know that the sharp dual constant in L1-Poincar´e inequality is
the norm of this matrix as acting from ℓ∞
2n to ℓ2
n.
The norm of the matrix M = (mi,z) =
R 1
0 Mρ dρ as the matrix acting from ℓ∞
2n to ℓ2
n is
(15.2)
max
λ, ∥λ∥ℓ2n≤1 Ez

n
X
i=1
λi
Z 1
0
zi −ρ
1 −ρ2 (1 + ρ)n−d(z)(1 −ρ)d(z) dρ

We know that it is less than π
2 −ε, where ε > 0 does not depend on n.
There is a “sister” problem, where L1-Poincar´e inequality is replaced by L∞one. It cannot
have the form ∥f −Ef∥∞≤C∥∇f∥∞with constant independent of n. This is impossible, e.g.
because inequality a1 + · · · + an ≤C(a2
1 + · · · + a2
n)1/2 is false. However, if one changes the
deﬁnition of the gradient, then the corresponding inequality becomes meaningful and important
(see, e.g., [11] or [18].)
Denote | ˜∇f|(x) = Pn
i=1 |∂if(x)|. Then one can ask, whether the following inequality holds
and with what sharp constant independent of n:
(15.3)
∥f −Ef∥∞≤C∞∥˜∇f∥∞?
This is a combinatorial question about the diameter of Hamming cube with weighted lengths
of edges. Namely, this is equivalent to asking (see [11]) what is the supremum of L∞norms of
functions f having zero average on cube and such that
(15.4)
| ˜∇f(x)| ≤1
∀x ∈{−1, 1}n .
Remark 15.1. Condition (15.4) can be reformulated in purely combinatorial terms as follows
(see [11]): every edge of the graph (=Hamming cube) is provided with its variable “length” ℓ(x, y),
and
X
y∼x
ℓ(x, y) ≤2
∀x ∈{−1, 1}n .
One wants then to know what is the universal sharp estimate on the diameter of the cube?
This becomes the question about independent of n sharp constant C∞such that (15.3) holds.
The reference [11] has a very nice reasoning of F. Petrov that proves the following:
C∞= 2 .
Notice that we can easily translate the estimate (15.3) into a certain fact about our matrix
M = (mi,z) =
R 1
0 Mρ dρ deﬁned in (11.8).
In fact, repeating our reasoning in the previous
sections, we can notice that (15.3) is equivalent to ﬁnding
sup
f:∥f||L1({−1,1}n≤1
inf
h∈Curl ∥h +
Z ∞
0
∇Ptfdt∥L1({−1,1}n;ℓ∞
n ) .
If Curl space would not play any role, that would mean that we are interested in
sup
f:∥f||L1({−1,1}n≤1
∥
Z ∞
0
∇Ptfdt∥L1({−1,1}n;ℓ∞
n ) .
We can calculate this norm now. It is the norm of our familiar operator
f →
Z ∞
0
∇Ptfdt

=== PAGE 19 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
19
as acting from L1({−1, 1}n, dµ) to L1({−1, 1}n, dµ; ℓ∞
n ).
This is the same the norm of operator K = (K1, . . . , Kn) (introduced in Section 11) as act-
ing from L1(Cn, dµ) to L1(Cn, dµ; ℓ∞
n ). Kernel Ki(x′, x) can be written down as Ki(x′, x) =
xi ˜Ki(x′, x), where
˜Ki(x′, x) :=
Z ∞
0
e−tx′
ixi Πn
k̸=i(1 + e−tx′
kxk) dt,
and we see that this is a kernel of the form ki(x′ · xi), that is, it is a convolution kernel.
We use it with measure dµ(x′) that is invariant, meaning that dµ(x′ · x) is the same measure.
Notice also that the facts that Ki(x′, x) = xi ˜Ki(x′, x), xi = ±1, imply that the norm of operator
with kernel K is the same as the norm of operator with kernel ˜K – we mean here the action from
L1(Cn) →L1(Cn; ℓ∞
n ).
The norm of convolution operator from L1 to L1 is just L1 norm of its kernel.
The reasoning that we have just made implies that the norm of the integral operator K
from L1(Cn) →L1(Cn; ℓ∞
n ) is the same as the norm of the matrix M := (mi,z)i=1,...,n; z∈{−1,1}n
considered as the vector function in L1(Cn; ℓ∞
n ), which is
Z
Cn max
i=1,...,n | ˜Ki(z, 1)dµ(z) =
Z
Cn max
i=1,...,n |Ki(z, 1)dµ(z) =
X
z∈Cn
max
i=1,...,n |mi,z| .
Matrix elements mi,z were computed in Section 11, see (11.8). So it is easy to calculate the
latter quantity.
Formula (11.8) gives us the following:
• if d(z) = dist(z, 1) = 0, then for all i we have mi,z(ρ) = 2−n(1 + ρ)n−1,
• if d(z) = dist(z, 1) = 1, then maxi=1,...,n |mi,z| = 2−n R 1
0 (1 + ρ)n−1dρ again,
• if d(z) = dist(z, 1) = 2, then maxi=1,...,n |mi,z| = 2−n R 1
0 (1 + ρ)n−2(1 −ρ)dρ, . . . ,
• if d(z) = dist(z, 1) = n, then maxi=1,...,n |mi,z| = 2−n R 1
0 (1 −ρ)n−1dρ.
Hence
X
z∈Cn
max
i=1,...,n |mi,z| = 2−n
Z 1
0
[(1 + ρ)n−1 + n(1 + ρ)n−1 + n(n −1)
2
(1 + ρ)n−2(1 −ρ)+
· · · + (1 −ρ)n−1] dρ = 2−n
Z 1
0
[n(1 + ρ)n−1 + n(n −1)
2
(1 + ρ)n−2(1 −ρ) + · · · + (1 −ρ)n−1]1 −ρ
1 −ρ dρ+
+ 2−n
Z 1
0
(1 + ρ)n−1dρ =
2−n
Z 1
0
[(1 + ρ)n + n(1 + ρ)n−1(1 −ρ) + n(n−1)
2
(1 + ρ)n−2(1 −ρ)2 + · · · + (1 −ρ)n −(1 + ρ)n]
1 −ρ
dρ+
+ 2−n
Z 1
0
(1 + ρ)n−1dρ =
2−n
Z 1
0
(1 + ρ + 1 −ρ)n −(1 + ρ)n
1 −ρ
dρ + 2−n
Z 1
0
(1 + ρ)n−1dρ =
Z 1
0
1 −(1+ρ
2 )n
1 −ρ
dρ + 2−n
n (2n −1) =
2
Z 1
1/2
1 −xn
2(1 −x) dx + O
  1
n

=
Z 1
1/2
(1 + x + x2 + . . . xn−1) dx + O
  1
n

= 1 + 1
2 + 1
3 + · · · + 1
n + O(1) =
log n + O(1) .
We see that the operator norm supf:∥f||L1({−1,1}n≤1 ∥
R ∞
0 ∇Ptfdt∥L1({−1,1}n;ℓ∞
n ) grows logarith-
mically with n. So Curl space plays major part for the calculation of C∞since we know from
[11], [18] that C∞is bounded independent of n. One cannot forget about Curl space in this
problem.

=== PAGE 20 ===
20
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
16. Some formulas for Cdual
As we know
(16.1)
Cdual = lim
n→∞
sup
∥v∥ℓ2n≤1
Ez

n
X
i=1
vi
Z 1
0
zi −ρ
1 −ρ2 (1 + ρ)n−d(1,z)(1 −ρ)d(1,z) dρ

Let B(a, b) =
R 1
0 ta−1(1 −t)b−1 denote the beta function. For k = d(1, z) integrals
2−n
Z 1
0
zi −ρ
1 −ρ2 (1 + ρ)n−d(1,z)(1 −ρ)d(1,z) dρ =
(R 1/2
0
tk(1 −t)n−k−1dt,
zi = 1
−
R 1/2
0
tk−1(1 −t)n−kdt,
zi = −1
are certain combinatorial quantities called “incomplete beta functions”
=
(
B1/2(k + 1, n −k) = F1/2(n −k −1, n) · B(k + 1, n −k),
if zi = 1,
B1/2(k, n −k + 1) = −F1/2(n −k, n) · B(k, n −k + 1),
if zi = −1 .
This can be written down as
=



B1/2(k + 1, n −k) = F1/2(n −k −1, n)
1
(n−k)(n
k),
if zi = 1,
B1/2(k, n −k + 1) = −F1/2(n −k, n)
1
k(n
k),
if zi = −1 .
Here F1/2(n −k −1, n) is the probability of at least k + 1 successes in Bernoulli scheme with
n trials:
F1/2(n −k −1, n) = 2−n
n
X
r=k+1
n
r

.
Thus, we can rewrite the main part of formula (16.1) for Cdual as follows
Ez

n
X
i=1
vi
Z 1
0
zi −ρ
1 −ρ2 (1 + ρ)n−d(1,z)(1 −ρ)d(1,z) dρ
 =
= 1
2n
n
X
k=0
n
k

E
h
n
X
i=1
vi
1
 n
k

2zi
1 + (1 −2k/n)zi
n
X
r=k+1−1zi=−1
n
r

d(1, z) = k
i
= 1
2n
n
X
k=0
E
h
n
X
i=1
vi
2zi
1 + (1 −2k/n)zi
n
X
r=k+1−1zi=−1
n
r

d(1, z) = k
i
=
1
n2n−1
n−1
X
k=0
n
X
r=k+1
n
r

E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
+ 1
2n
n
X
k=1
1
k
n
k

E
h
X
i: zi=−1
vi

d(1, z) = k
i
But ∥v∥2 ≤1, so E
h P
i: zi=−1 vi

d(1, z) = k
i
≤
√
k. Therefore, the last sum is
≤1
2n
n
X
k=1
1
√
k
n
k

≤
v
u
u
t 1
2n
n
X
k=1
1
k
n
k

≤
2
√n + 1 →0.
Hence, we can rewrite
Ez

n−1
X
i=1
vi
Z 1
0
zi −ρ
1 −ρ2 (1 + ρ)n−d(1,z)(1 −ρ)d(1,z) dρ
 =
1
n2n−1
n
X
k=0
n
X
r=k+1
n
r

E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
+ o(1) .

=== PAGE 21 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
21
Here is the ﬁrst formula for Cdual:
(16.2)
Cdual = lim
n→∞
sup
∥v∥ℓ2n≤1
1
n2n−1
n−1
X
k=0
n
X
r=k+1
n
r

E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
.
We can simplify further this formula. For that, consider
Φn(k) := 1
2n
n
X
r=k+1
n
r

= P[Binom(n, 1
2) > k] .
This implies
Φn(
√n
2 + x√n
2
) →P[N(0, 1) > x] .
Theorem 16.1.
(16.3)
Cdual = lim
n→∞
sup
∥v∥ℓ2n≤1
2
n
n/2
X
k=0
E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
.
Proof. Deﬁne
Xk
i :=
zi
1 + (1 −2k/n)zi
.
By Cauchy–Schwarz we get
(16.4)
E[
n
X
i=1
viXk
i |d(1, z) = k] ≤
n
X
i,j=1
vivjE[Xk
j Xk
i |d(1, z) = k] .
It is easy to see that
E[Xk
i |d(1, z) = k] = 0,
E[(Xk
i )2|d(1, z) = k] =
n2
4k(n −k),
E[Xk
i Xk
j |d(1, z) = k] = −
1
n −1
n2
4k(n −k),
i̸ = j.
Hence, we know the Gramm matrix G := {E[Xk
j Xk
i |d(1, z) = k]}. It is self adjoint rank one
perturbation of the diagonal matrix diag(
n
n−1
n2
4k(n−k)). So it is easy to calculate the norm of G.
It is
q
n
n−1
n2
4k(n−k).
Hence, by (16.4)
(16.5)
E[
n
X
i=1
viXk
i |d(1, z) = k] ≤
s
n
n −1
n2
4k(n −k) .
Let bn = √n log n. By the same spectral estimate for a cut-oﬀmatrix and by the fact that
Φn(k) ≤1, we will get
(16.6)
n/2+bn
X
k=n/2−bn
Φn(k)E[
n
X
i=1
viXk
i |d(1, z) = k] ≤
n/2+bn
X
k=n/2−bn
s
n
n −1
n2
4k(n −k) = O(bn) .
Thus,
(16.7)
1
n2n−1
n/2+bn
X
k=n/2−bn
n
X
r=k+1
n
r

E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
= O
 log n
√n

.

=== PAGE 22 ===
22
PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
Using the spectral estimate for another cut-oﬀmatrix and the fact that
q
n
n−1
n2
4k(n−k) = O(√n),
we get
(16.8)
E[
n
X
i=1
viXk
i |d(1, z) = k] ≤
s
n
n −1
n2
4k(n −k) = O(√n) .
Hence,
n−1
X
k=n/2+bn
Φn(k)E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
= O
√n
n−1
X
k=n/2+bn
Φn(k)

= O(n3/2Φn(n/2 + bn)) = O(n3/2e−log2 n) .
(16.9)
(16.10)
1
n2n−1
n−1
X
k=n/2+bn
n
X
r=k+1
n
r

E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
= O
 n1/2e−log2 n
.
So when we come to the limit with n →∞in (16.2), we are left with
Cdual = lim
n→∞
sup
∥v∥ℓ2n≤1
1
n2n−1
n−1
X
k=n/2−bn
n
X
r=k+1
n
r

E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
=
= lim
n→∞
sup
∥v∥ℓ2n≤1
2
n
n−1
X
k=n/2−bn
Φn(k)E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
=
= lim
n→∞
sup
∥v∥ℓ2n≤1
2
n
n−1
X
k=n/2−bn
E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
,
the last equality being true because in this range of k we have
1 −O(e−log2 n) ≤Φn(k) ≤1 .
Now we can add back
2
n
n/2+bn
X
k=n/2−bn
E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
and
2
n
n−1
X
k=n/2+bn
E
h
n
X
i=1
vi
zi
1 + (1 −2k/n)zi

d(1, z) = k
i
as we already saw that they are O
  log n
√n

and O
 e−log2 n
correspondingly. Theorem is completely
proved.
□
Remark 16.2. From (16.5) and (16.2) one immediately deduces the estimate
(16.11)
Cdual ≤lim
n→∞
n−1
X
k=1
Φn(k)
1
p
k(n −k)
= π
2 .
Of course Theorem 16.1 also immediately gives this estimate. This is one of the numerous re-
proofs of Lust-Piquard–Ben Efraim estimate from [1]. As we can see the reason for their estimate
lies in Cauchy–Schwarz estimate and spectral calculation for the Gramm matrix.
Remark 16.3. What we did in this paper, was that we estimated by funny Khintchine inequality
another (and formally bigger than Cdual) quantity
(16.12)
lim
n→∞
Z 1
0
sup
∥v∥ℓ2n≤1
Ez

n
X
i=1
vi
zi −ρ
1 −ρ2
(1 + ρ)n−d(1,z)(1 −ρ)d(1,z) dρ < π
2 .

=== PAGE 23 ===
POINCAR´E INEQUALITY ON HAMMING CUBE
23
References
[1] L. Ben Efraim, F. Lust-Piquard, Poincar´e type inequalities on the discrete cube and in the CAR algebra,
Probab. Theory Related Fields 141 (2008), no. 3-4, 569–602.
[2] D. Bakry, I. Gentil, M. Ledoux, Analysis and Geometry of Markov Diﬀusion Operator, Grundlehren der
mathematischen Wissenschaften, v. 348, Springer, 2014.
[3] Sergey G. Bobkov, Gennadiy P. Chistyakov, On Concentration Functions of Random Variables, J.
Theor. Probab. DOI 10.1007/s10959-013-0504-1.
[4] S.G. Bobkov, An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric
inequality in Gauss space, The Annals of Probability 1997, Vol. 25, No. 1, 206–214.
[5] S.G. Bobkov, F. Gotze, Exponential integrability and transportation cost related to logarithmic Sobolev
inequalities, J. Funct. Anal. 163 (1) (1999) 1–28.
[6] Dong Li, On a frequency localized Bernstein inequality and some generalized Poincar´e-type inequalities,
Math. Res. Lett. 20 (2013), no. 5, 933–945.
[7] Leonard Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1975), no. 4, 1061–1083. 521 citations.
[8] Paata Ivanisvili, Fedor Nazarov and Alexander Volberg, Square function and the Hamming cube:
Duality, to appear in Discrete Analysis, 2018.
[9] Paata Ivanisvili, Alexander Volberg, Isoperimetric functional inequalities via the maximum principle:
the exterior diﬀerential systems approach, arxiv. 1511.06895, Operator Theory: Advances and Applications,
Vol. 261, 279–303, Birkhauser volume dedicated to V. P. Khavin.
[10] R. O’Donnell, Analysis of Boolean functions, Cambridge University Press, 2014.
[11] P. Ivanisvili, B. Kloeckner, F. Nazarov, F. Petrov, https://mathoverﬂow.net/questions/286329/diameter-
of-a-weighted-hamming-cube/303016-303016
[12] G. Pisier, Probabilistic methods in the geometry of Banach spaces, in: Probability and Analysis, (Varenna,
1985), Lecture Notes in Math. 1206, Springer, Berlin, 1986.
[13] G. Samorodnitsky, M. Taqqu, Stable non-Gaussian Random Processes. Chapman and Hall, New York,
London, 1994, 632 pp.
[14] A. Naor, T. Hyt¨onen, Pisier’s inequality revisited, Studia Mathematica 215 (2013), no. 3, 221–235.
[15] Y. Shenfeld, R. van Handel , The equality cases of the Ehrhard-Borell inequality. Adv. Math. 331 (2018),
339–386.
[16] M. Talagrand, Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph
connectivity theorem, Geometric and Functional Analysis (GAFA), 3 (1993), No. 3, pp. 295–314.
[17] R. van Handel, The Borell–Ehrhard game. Probab. Theory Related Fields 170 (2018), no. 3–4, 555–585.
[18] R. Wagner, Notes on an inequality by Pisier for functions on the discrete cube, Milman, V. D. (ed.) et
al., Geometric aspects of functional analysis. Proceedings of the Israel seminar (GAFA) 1996-2000. Berlin:
Springer. Lect. Notes Math. 1745, 263-268 (2000).
Department of Mathematics, Princeton University
E-mail address: rvan@princeton.edu (Ramon Van Handel)
Department of Mathematics, Princeton University
E-mail address: paata.ivanisvili@princeton.edu (Paata ivanisvili)
Department of Mathematics, Hong Kong University of Science and Technology
E-mail address: madli@ust.hk (Dong Li)
Department of Mathematics, Michigan State University, East Lansing, MI 48823, USA
E-mail address: volberg@math.msu.edu (Alexander Volberg)
