                                            IMPROVING CONSTANT IN END-POINT POINCARÉ INEQUALITY ON
                                                                HAMMING CUBE

                                                      PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG


                                                  Abstract. We improve the constant π2 in L1 -Poincaré 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
                                                                                      pπ
                                                  sharp constant is not known, and       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 different 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
arXiv:1811.05584v5 [math.PR] 1 Jun 2019




                                                  still not clear whether C1 > π2 . We discuss this circle of questions.
                                                                               p




                                                                                       1. Introduction
                                            In [1] the following inequality is proved
                                                                                             π
                                          (1.1)                                                k∇f k1 ,
                                                                                     kf − Ef k1 ≤
                                                                                             2
                                          where f is a function on Hamming cube {−1, 1}n . Pisier p       proved that in Gaussian space the
                                          following Poincaré inequality holds with the sharp constant π/2:
                                                                                            r
                                                                                              π
                                          (1.2)                                kf − Ef k1 ≤      k∇f k1 ,
                                                                                               2
                                          If we denote by C1 the best constant in the Poincaré inequality in L1 ({−1, 1}n ), then we see that
                                                                                     r
                                                                                        π           π
                                                                                          ≤ C1 ≤ .
                                                                                        2           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 )-Poincaré 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 different 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                                          Z ∞
                                                                                             d
                                                                            f − Ef = −          Pt f dt .
                                                                                         0   dt
                                             2010 Mathematics Subject Classification. 42B20, 42B35, 47A30.
                                             Volberg is partially supported by the NSF DMS-1600065.
                                                                                                  1
2                PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG

and hence
                                           Z ∞                        Z ∞
                       (f − Ef, g) = −      (∆Pt f, g) dt = −     (∆f, Pt g) dt =
                                         0                     0
                               Z ∞                   Z ∞
                        − (∆f,     Pt g dt) = −(∇f,       ∇Pt g dt) .
                                  0                          0
    Therefore,
                                            Z ∞                                       Z ∞
        E|f − Ef | ≤ k∇f k1 · sup                 ∇Pt g dt        ≤ k∇f k1 · sup            k∇Pt gk∞ dt .
                                 kgk∞ ≤1     0               ∞                kgk∞ ≤1 0

    So we will estimate                            Z ∞
                                      sup        k∇Pt gk∞ dt
                                    kgk∞ ≤1 0
by Cdual kgk∞ . 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→ ∇Pt g 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
                  1−ρ
with probability 2 , then we have them exactly ρ-correlated Eyi xi = ρ. Given a fixed 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) = (Pt g)(x) .
Since
                                         ∇Pt g = e−t Pt ∇g
we can apply this to ∂1 g.
                                 (Pt ∂1 g)(x) = Ey∼Nρ (x) ∂1 g(y) .
Now we want to find ϕ1 (y) such that
                                 Ey∼Nρ (x) ∂1 g(y) = Ey∼Nρ (x) ϕ1 (y)g(y) .
But ∂1 eliminates all polynomials that do not have y1 and cross off y1 from other polynomials.
So ϕ1 such that
                                    Ey∼Nρ (x) ϕ1 (y)yk = δ1k .
Clearly the following ϕ1 works:
                               y1 − Ey∼Nρ (x) y1    y1 − ρx1   y1 − e−t x1
                      ϕ1 (y) =                    =          =             .
                                   V ar[y1 ]         1 − ρ2     1 − e−2t
Combining all that we get the integral representation of (Pt ∇g)(x):
                                              y − e−t x               yn − e−t xn       
                                                  1        1
(3.1)            (Pt ∇g)(x) = Ey∼Nρ (x) (                    , . . . ,             )g(y)   .
                                                  1 − e−2t              1 − e−2t
From (3.1) we get (λ = λ1 , . . . , λn ) (a unit vector in Rn )
                                                                             n
                                    1                                        X      yj − e−t xj
(3.2)          k(Pt ∇g)k∞ ≤ √              kgk∞       sup        Ey∼Nρ (x)       λj √
                                  1 − e−2t          λ:kλk2 =1                j=1
                                                                                      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 ,
                               POINCARÉ INEQUALITY ON HAMMING CUBE                                                 3

and since y − e−t xj takes values xj (1 − e−t ) and −xj (1 + e−t ) we can absorb the signs xj into
the values of λj .
                           j y −e−t
  The random variables √1−e   −2t
                                  are independent, and they have the same distribution as random
                                 q                                     q
                                    1−e−t                  1+e−t          1+e−t
variables ξit that assume value     1+e−t with probability   2   and  −   1−e−t
                                                                                 with probability
1−e−t
  2 .
  Hence, for kgk∞ ≤ 1, we have
                                              e−t               X
(3.3)                      k∇(Pt g)k∞ = √                sup      λj ξjt L1 (P) .
                                             1−e  −2t
                                                      λ:kλk2 =1



                    ξjt dP = 0, (ξjt )2 dP = 1. Thus, there is a trivial estimate
                R              R
  Notice that
                                        e−t              X                     e−t
(3.4)               k∇(Pt g)k∞ = √                sup      λj ξjt L2 (P) ≤ √          .
                                      1 − e−2t λ:kλk2 =1                     1 − e−2t
                                                                                                             2
                                                                                                       λj ξjt L2 (P) =
                                                                                                   P
The first estimate here is just (3.3), the second one is just a trivial fact that k
λ21 + · · · + λ2n = 1.
            R ∞ e−t          R 1 du
   Using 0 √1−e      −2t
                         dt = 0 √1−u2
                                      = π2 we see (1.1) one more time.

  To improve this estimate it is sufficient to prove the following theorem.
Theorem 3.1. Let p ∈ [ 12 , 1 . Consider independent random variables εj , j = 1, . . . , n, having
                             
      q                              q
values 1−p                               p                                                P
         p with  probability p and −    1−p with probability 1−p. Then supλ∈Rn :kλk2 =1 k    λj εj k1 =:
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 ∈ ( 12 , 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 different 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.
                         , n be our random Bernoulli variables with Eξ = 0, Eξ 2 = 1, 1−p, p probability
   Let ξi , iq= 1, . . . q
                p
of values 1−p      , − 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
                                     X                         X          1/2
(4.2)         max |λk |2 ≤ 0.99 ⇒ E|     λi ξi | ≤ (1 − ε2 ) E(  λi ξi )2      = 1 − ε2 .
                 P
   Denote Y := | λi ξi | and notice that if the opposite happens for some λ satisfying (4.1), then
                                                     2
                           E(Y − EY )2 = 1 − EY           < 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 λ,
                                                                                 2
                                                              X
                    with probability    1 − 2ε one has |          λ i ξi | − 1       ≤ ε + 2ε2 .
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
                       X                 p              p         
(4.3)              P |      λj ξj |2 − 1 ≤ ε + 2ε2 (1 + ε + 2ε2 ) ≥ 1 − 2ε

  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.
                P
  Consider ` = λi ξi , then
                                       X              X
                                  `2 =    λ2i ξi2 + 2   λi λj ξi ξj .
                                                                      i<j
So
                            X                  X                           X
                    `4 =         λ4i ξi4 + 2         λ2i λ2j ξi2 ξj2 + 4         λ2i λ2j ξi2 ξj2 +
                                               i<j                         i<j
                                X                                                      X
(4.4)               4                           λi λj ξi ξj λk λm ξk ξm + 4                    λ2m ξm
                                                                                                    2
                                                                                                      λi λj ξi ξj
                        i<j,k<m,(i,j)6=(k,m)                                          m, i<j

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 =
                             X            X               X             X
                        Eξ 4      λ4i + 6   λ2i λ2j − 1 ≥   λ4j + 3(1 −   λ4j ) − 1 =
                                          i<j
                                X
                        2(1 −       λ4j ) ≥ 2 · 0.01 = 0.02
Here we have used Eξ 4 ≥ 1 and λ4j ≤ 0.99λ2j for all j = 1, . . . , n.
     Let X := |`2 − 1|. If
(4.5)                                                EX 4 ≤ B(EX 2 )2 ,
then the Paley–Zygmund estimate applied to X 2 says
                                                       1
                                P(X ≥ t(EX 2 )1/2 ) ≥ (1 − t2 )2
                                                         , t ∈ (0, 1) .
                                                      B
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 EX 2 from below as follows
                                                         EX 2 ≥ 0.02
we get
                                                        √
                                      2               1 2      9 1
(4.6)                      P(|` − 1| ≥ 0.07) ≥ P(X ≥       )≥       .
                                                      2 10    16 B
This contradicts (4.3). Indeed, summing up (4.3) and (4.6) we obtain
                                           p            p                                                9
         P(|`2 − 1| ≥ 0.07) + P |`2 − 1| ≤ ε + 2ε2 (1 + ε + 2ε2 ) ≥
                                                                  
(4.7)                                                                                                       + 1 − 2ε .
                                                                                                        16B
Now it remains to take ε sufficiently 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 ε sufficiently small depending only on p.
                                                                                     P 2
   To see (4.5) with B independent of n and independent of λi satisfying (4.1),        λi = 1, let us
                  2                                     2        2    2
recall that X = |` − 1| and we already estimated EX = E(` − 1) ≥ 0.02 from below, and this
estimate depends only on assumption (4.1).
   To prove (4.5) we now just need to estimate EX 4 = 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
                                                                       Pn to 2msee that E `8 ≤ C(p),
where C(p) is bounded if we do not make p → 1. This just because j=1 λj ≤ 1, m = 1, 2, . . . ,
and because of the obvious estimate E |ξi |2m ≤ K(p, m, δ) < ∞ if p ∈ [ 12 , 1 − δ .
                                                                                  
                               POINCARÉ INEQUALITY ON HAMMING CUBE                                            5

  Hence, we have

                     EX 4 ≤ B(p)(EX 2 )2 ,
                                                                                  
(4.8)                                               B(p) ≤ Bδ < ∞, p ∈ [1/2, 1 − δ .

  So for p = 43 and also for p in a small fixed (independent of n) neighborhood of p = 34 we have
a definite drop in norm. In other words, we have the Hölder 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 =: λ21 is in [0.99, 1]? Here we should think that p ∈ ( 12 + δ, 1 . For
                                                                                           

example p is in a small fixed interval around 43 .
  Then we write for p = 34 :
                                                    n                                n
                     X                              X                                X                  1/2
                E|       λi ξi | ≤ λ1 E|ξ1 | + E|         λi ξi | ≤ λ1 E|ξ1 | + E|         λ i ξi | 2
                                                    i=2                              i=2
                                                      √
                                                           3   1
                    p          q
                 ≤ 2 (1 − p)p + 1 − λ21 ≤                    +    < 0.87 + 0.1 = 0.97.
                                                          2    10
Again we have a fixed drop in Hölder inequality independent on n. And the same drop happens
trivially in a small neighborhood of p = 34 , 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 -Poincaré 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
briefly recall onepof them. First we recall how to use “Bellman function approach” to derive the
sharp constant π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,
                                                 Z x
                                              1          2
                                   Φ(x) = √           e−y /2 dy .
                                              2π −∞
Let us consider the “gaussian isoperimetric profile”:
                                                           h    1 i
                                    I = Φ0 ◦ Φ−1 : [0, 1] → 0, √    .
                                                                 2π
   Let us first 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
difficult 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 I 2 will play the part of “Bellman function” in the sense that a certain
monotonicity involving the semigroup Pt and function I 2 will be crucial. We first consider only
f such that 0 ≤ f ≤ 1. Obviously,
                                                   Z t
                                2          2       d                2
                         I(Pt f ) − Pt (I(f )) = −        Ps (I(Pt−s f )) ds
                                                    0 ds
6              PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG

Combine this with
                                                                                            
        d                  2                                         0
     −     Ps (I(Pt−s f )) = −2Ps (I(Pt−s f )) · Ps ∆ I(Pt−s f ) − I (Pt−s f ) · ∆Pt−s f =
       ds
                                                                                |∇Pt−s f |2
                                                                                         
                                00                   2
     − 2Ps (I(Pt−s f )) · Ps I (Pt−s f ) · |∇Pt−s f | = 2Ps (I(Pt−s f )) · Ps                 ≥
                                                                                 I(Pt−s f )
                                      2
                         Ps |∇Pt−s f |                  2
    2Ps (I(Pt−s f )) ·                    = Ps |∇Pt−s f | .
                        Ps (I(Pt−s f ))
  The thirdR equality here is because I 00 = − I1 . The inequality is just Cauchy-Schwartz inequality:
R A2       [ R A dµ]2
  B dµ ≥       B dµ
                      . The second equality is the chain rule in this form: for any smooth G and test
function g on R    n

(6.1)                            ∆G(g) = G0 (g)∆g + G00 (g)|∇g|2 .
We warn the reader that only this last simple equality will fail on the cube.
   Let us combine the estimate
                                                   Z t
                               2          2                      2
(6.2)                   I(Pt f ) − Pt (I(f )) ≥ 2        Ps |∇Pt−s f | ds,
                                                            0
which has been just obtained, with the following well-known (and easy, see, e. g., [2]) estimate
for the Ornstein-Uhlenbeck semigroup:
(6.3)                                      |∇Ps g| ≤ e−s Ps |∇g| .
Then we get
                                                            Z t
                                   2          2
                                                                    e2s |∇Pt f |2 ds .
                          
                           I(Pt f ) − Pt (I(f )) ≥ 2
                                                                0
Thus
                                                                                2
                                  2     1          2          2    I(Pt f )
              0 ≤ f ≤ 1 ⇒ |∇Pt f | ≤ 2t     I(Pt f ) − Pt (I(f ))     ≤ 2t          ,
                                    e −1                                 e −1
and so
                                                I(Pt f )   1    1
                        0 ≤ f ≤ 1 ⇒ |∇Pt f | ≤ √         ≤√ √       ,
                                                  2t
                                                 e −1          2t
                                                           2π e − 1
Hence,
                          Z ∞                         Z ∞                                r
                                      t∆     1                      1    1 π     1           π
(6.4)       0≤f ≤1⇒             |∇e f |dt ≤ √               √      dt = √      =               .
                            0                 2π        0
                                                               2t
                                                              e −1        2π 2   2           2
Finally, this immediately implies
                                      Z ∞                   r
                                                t∆              π
(6.5)                                       |∇e f |dt ≤           kf k∞ .
                                       0                        2
   This gives the sharp constant in L1 -Poincaré inequality on gaussian space:
                                                   r
                                                     π
(6.6)                              Eg |f − Ef | ≤      Eg |∇f | .
                                                     2
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 modified and the constant jumps:
strangely enough, it becomes π2 . Here is the reasoning.
   It would be nice to have on Hamming cube C n the variant of our usual relationship (6.1), e.
g., to have it in this form:
                                I 0 (g)∆g − ∆[I(g)] ≥ c[−I 00 (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
                             POINCARÉ 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 ∂j g · I 0 (g) + xj ∂j (I(g)) ≥ c[−I 00 (g)]|∂j g|2 ,
where ∂j g = (g(xj = 1) − g(xj = −1))/2. Or, denoting g(xj = 1) =: b, g(xj = −1) =: a:
                                                          c
                     −(b − a)I 0 (b) + (I(b) − I(a)) ≥ [−I 00 (b)](a − b)2 ≥ 0 .
                                                         2
This is
                                                          c
(7.1)                    I(b) − I(a) − I 0 (b)(b − a) + I 00 (b)(a − b)2 ≥ 0
                                                          2
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 00 (b) → −∞ as − 1b √ 1 , and notice that I 0 (b) → +∞
                                                                  log 1/b
   p
as 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 first 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

(7.2)             I(b) − I(a) − I 0 (b)(b − a) − k (a − b)2 /2 ≥ 0 ∀a, b ∈ [0, 1]?
                                          √
   The answer of course is obvious, k = 2π. Indeed,
                                            1
(7.3)       I(b) − I(a) − I 0 (b)(b − a) + max [I 00 (c)](a − b)2 ≥ 0, ∀a, b ∈ [0, 1],
                                            2 c∈[0,1]
                                                      √
            that is I(b) − I(a) − I 0 (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 ∂j g · I 0 (g) + xj ∂j (I(g)) ≥ min[−I 00 (g)]|∂j g|2 =       2π|∂j g|2 ,
Or,
                                                              √
(7.5)                                I 0 (g)∆g − ∆[I(g)] ≥        2π|∇g|2
   Let now ∆ be the Laplacian on Hamming cube, and Pt = et∆ be the corresponding flow on
cube. Then we get the analog of (6.2) (but without squares over [·]):
(7.6)
                     √                           √ Z t               2 √
                          Z t                                                        Z t
                                Ps |∇Pt−s g|2 ds ≥ 2π      Ps |∇Pt−s g| ≥ 2π|∇Pt g|2     e2s ds,
                                         
 I(Pt g) − Pt (I(g)) ≥ 2π
                                0                                  0                                0

                 1 2t     √                                                1
(7.7)              (e − 1) 2π|∇et∆ g|2 ≤ I(et∆ g) − et∆ I(g) ≤ I(et∆ g) ≤ √
                 2                                                          2π
Or,
                                     1 2t     √               1
                                       (e − 1) 2π|∇et∆ g|2 ≤ √
                                     2                         2π
Hence, for 0 ≤ g ≤ 1 we have
                                                      √
                                            t∆    1      2
(7.8)                                  |∇e gk∞ ≤ √ √
                                                      2t
                                                  2π e − 1
Hence for any bounded positive g
                                                   √
                                       t∆      1     2
                                    k∇e gk∞ ≤ √ √         kgk∞ .
                                               2π e2t − 1
8               PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG

Now                                       Z ∞
                                                     1               π
                                                √             dt =     .
                                           0        e2t − 1          2
So for positive g
                                Z ∞
                                                              π 1
(7.9)                                    k∇et∆ gk∞ dt ≤         · √ kgk∞ .
                                 0                            2    π
So for all g,
                                  Z ∞
                                                                √
(7.10)                                    k∇et∆ gk∞ dt ≤             πkgk∞ .
                                     0
  This is worse than π2 kgk∞ . Looking at the above proof, we immediately see that I = Φ0 ◦ Φ−1
being optimal
             for the estimate in gaussian space might be not optimal on cube. In fact, replacing
∆(I(Pt−s f ) − I 0 (Pt−s f ) · ∆Pt−s f by ∆(B(Pt−s f ) − B 0 (Pt−s f ) · ∆Pt−s f we can see that we
should find B : [0, 1] → R+ such that
                                             max[0,1] B(x)
(7.11)                          MB :=                            → min .
                                            min[0,1] [−B 00 (x)]
If we call this minimum M , we obtain (just by repeating the reasoning of Section 6) the following
estimate:
                                                     √ √        1
                            0 ≤ f ≤ 1 ⇒ |∇Pt f | ≤ 2 M √            ,
                                                               2t
                                                              e −1
                          1
For B = I we have MI = 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 81 . Then
                                       Z ∞               √ 1 π       π
                         0≤f ≤1⇒            |∇Pt f |dt ≤ 2 √       = .
                                        0                  2 2   2   4
Hence,                             Z ∞
                                                      π
                                         |∇Pt f |dt ≤ kf k∞ .
                                     0                 2
And this way we get a commutative proof of Ben Efraim–Lust-Piquard estimate:
                                                    π
                                      E|g − Eg| ≤ E|∇g| .
                                                    2
                                               8. Discussion
                                                                 pπ       1
8.1. Functions with only two values have constant                 2 in L -Poincaré    inequality.
Incidentally, the question of validity of the Gaussian inequality constant π2 on the hypercube is
                                                                            p
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 -Poincaré
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
                                                           r
                                               2p(1 − p)     π
(8.1)                                   max              =     .
                                       p∈[0,1]   I(p)        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 Poincaré inequality.Then we can think that 1 is assumed with probability p ∈ (0, 1).
Hence Ef = p, E|f p− Ef | = 2p(1 − p).
   Let B(x, y) := I 2 (x) + y 2 . Here I(x) = Φ0 ◦ Φ−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 |) .
                              POINCARÉ 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)                             I(p)
                               E|f − Ef | = 2p(1 − p)           = I(p) ≤ E|∇f | ,
                     2p(1 − p)                        2p(1 − p)
or
                                                                     r
                                              2p(1 − p)                  π
(8.4)                    E|f − Ef | ≤ max               E|∇f | ≤           E|∇f | .
                                      p∈[0,1]   I(p)                     2
   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 -Poincaré 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 = Φ0 ◦ Φ−1 :
(8.5)               I(Pt f )2 − (Pt I(f ))2 ≥ (e2t − 1)|∇Pt f |2 . ∇Ps f = e−s Ps ∇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(Pt f )2 ≥ (e2t − 1)|∇Pt f |2 .
As is already remarked by Bakry-Ledoux, this inequality has the following equivalent formulation:
(8.7)                                 (e2t − 1)|∇Φ−1 (Pt f )|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 (Pt f ) (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 (Pt f )| is maximized pointwise when f = 1H , where H is a
half-space.
   Indeed it suffices 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 | ≤ Ck∇f k1 . Define g : R → R
  P that g(z) = 1 for z > 0, g(z) = 0 for z = 0 and g(z) = −1 for z < 0. Let fn (x1 , · · · , xn ) =
such
       n
       j=1 xj
g       √
            n
                .
  Consider first 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 |∂i fn | takes value only 0 or 1.
10             PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG

   Furthermore, denoting Zn = nj=1 xj , it is not difficult to check that |∂i fn | = 1 if and only if
                               P
                             = −1, xi = −1.
either Zn = 1, xi = 1, or Zn q
                                  n+1
  From this we get |∇fn | =        2 or 0, and the number of vertices where |∇fn | =
                                                                                   6 0 is precisely
   n
      
2 n+1   . Therefore,
     2
                                              r
                                1          n      n+1        2
(9.1)                 k∇fn k1 = n ·        n+1 ·      · 2 = √ · (1 + on (1)),
                               2            2      2          π
as n tend to infinity.
  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 ∂i g, hence:
                                                                         √
                          √ 1
                                             r
               −n     n            −n      n         n      1       1+ 2
    k∇fn k1 = 2 · n · n · + 2 · n                ·     +1· ·2= √             · (1 + on (1)).
                      2        2         2 +1        2      2           2π

  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
                                                      √     r
                                                        π     π
                             Codd,charact.f unction =     <     ,
                                                       2      2
and for the even n case we get
                                                                √
                                                       √
                                                               r
                                                          2        π
                            Ceven,charact.f unction =      π√<       .
                                                         2+1       2
  Amusingly,  if we√ take g to be a smooth function, then it is not difficult to check that for
fn = g(( nj=1 xj )/ n), one has
        P
                                                   Pn
                                       1  0  j=1 xj           1
                                                                    
                           |∂j fn | = √ · g          √    + O(n− 2 ) .
                                        n              n
From this one gets
                            E|fn − Efn |   Eγ |g(z) − Eγ g(z)|
(9.2)                                    →                     ,     n → ∞,
                              E|∇fn |             Eγ |g 0 |
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 ,
                           Pn x 
                             j=1 j
                                                                                                    pπ
fn (x1 , · · · , xn ) = g    √      , we conclude  that the right hand side of (9.2) is as close to     as
                               n
                                                                                                 pπ 2
we wish. Then making n → ∞ we achieve that the left hand side is also as close to                  2 as we
wish.
   But these fn will have values     p −1, 1 and many values in between. it is possible to prove that we
cannot achieve the constant π2 by testing symmetric functions having values −1, 1 or −1, 0, 1
alone. The constants
                   pπ         in L1 -Poincaré inequality for such functions are uniformly in n strictly
smaller than 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:
                                                   1
                                            Ef = .
                                                   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 < n2 and another value on all Rk , k > n2 (for n odd,
say).
                             POINCARÉ INEQUALITY ON HAMMING CUBE                                      11

   Now let us consider more general symmetric function. As always, being balanced, it will have
E|f − Ef | = 21 , so we need to minimize E|∇f |, or, to minimize E|∇1A |, with |A| = 12 . 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 ( 34 ) and put k = n2 + a 12 n . Let A be the set where x1 + . . . xn ∈ [n − k, k].
   Then
                                   h1√        
                                                n 1      1√
                                                                 
                                                                    n
                                                                         i
                                                                          1
                      E|∇1A | ≈ 2       n−k          n
                                                       +    k+1              .
                                     2           k 2     2        k + 1 2n
   By de Moivre–Laplace formula
                                        
                                    1 n          2         2   3
                                    n
                                           ≈ √ φ(a) = √ I( ) .
                                   2 k            n         n 4
                 √      √        √         √
   Hence, since k ≈ √n2 and n − k ≈ √n2 , we get the following:
                                                √    3
                                     E|∇1A | ≈ 2 2 I    .
                                                     4
Hence, for f = 1A , with A described above, we have
                                                       1
                                        E|f − Ef | ≤ √        E|∇f | .
                                                    4 2 I 34
                                    √
                                     π                                                √ 1
Constant Codd,charact.f unction =   2 from the previous section is nothing else than 2 2 I( 1 ) . Clearly
                                                                                              2

                                   1        1        1
                                    √3
                                       = √   1
                                                < √          ,
                                4 2I 4   4 2I 4   2 2 I( 12 )
because 2I 14 > 2I( 12 ) by concavity of function I.
             

   The conclusion: the symmetric function in this section gives a smaller constant in L1 -Poincaré
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,
                                                        √
                                           E|f − Ef |     π
                                     max              =     .
                                             E|∇f |      2
Remark 10.1. Consider this maximum over all functions         p having two values (without the loss
of generality, just values 0, 1). We saw that it is at most π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
pπ         with two values (with no symmetries whatsoever ) that maximum can be smaller than
   2 . In Proposition 3.1 on page 259 of [5] functions f = 1An (a) are considered. Here a ∈ R, and
                                        n    x1 + · · · + xn − n2     o
                                An (a) = x :         1 √          ≤ a  ,
                                                     2 n

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,
                                                                √
                          E|1An (a) − E1An (a) |      1           π
(10.1)         lim max                           =  √     1
                                                              =     ,     a = Φ−1 (α), α ∈ [0, 1] .
              n→∞ α∈[0,1]     E|∇1An (a) |         2 2 I( 2 )    2
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 |               π                                   2  √
 E|∇f | is bigger than 2 , namely it is asymptotically 2+1 π. We also saw that allowing more
                                                          √
                                     pπ
values we can saturate the constant     2 . It is not clear whether we can surpass this constant.

                           11. Kernel representation of operator T
                    R∞
     Operator f →   0    ∇et∆ f dt can be written also as follows:
                                     Z ∞                  Z ∞
                                          −t t∆
                               Tf =      e e ∇f dt =           ∇et∆ f dt .
                                0                   0
                             −t                 −t
Notice that we cannot loose e here, if we drop e , the expression will become undefined for,
say, f = x1 . We cannot either consider anything like
                                        Z ∞
                                 f →∇       et∆ f dt = ∇∆−1 f,
                                                   0
because this latter expression is undefined 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: P0 f := f − Ef . Then we can write down T
in the following form
(11.1)                                          T f = ∇∆−1 P0 f .

   But for operator T defined above, it is easy to give its matrix (kernel) representation. For that
let us double the cube: C 2n = {(x0 , x) ∈ C n × C n } and consider
                               Π(x0 , x) := Πt (x0 , x) := Πnk=1 (1 + e−t x0k xk ) .
   If dµ(x0 ) is the uniform measure on the first C n and if x in the second C n get fixed, we get a
new probability measure
                                 dP(x0 ) := dPx (x0 ) := Π(x0 , x) dµ(x0 ) .
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(x0 , x) be the kernel representing T in the sense that
                                            Z
                                  T f (x) =      K(x0 , x)f (x0 ) dµ(x0 ) .
                                                   Cn
                                                  R∞
It is a vector kernel, and let Ti corresponds to 0 ∂i et∆ f dt, where ∂i is the elimination operator
for xi . Let Ki be the kernel of Ti in the just mentioned sense. Then
                                       Z ∞
                               0               e−t       x0i − e−t xi
(11.2)                    Ki (x , x) =     √             √            Π(x0 , x) dt .
                                             1 −   e −2t    1 − e−2t
                                        0
   This we already had in the third Section essentially. Now let us rewrite it conveniently.
                                       Z ∞
                                             e−t
(11.3)                   K1 (x0 , x) =            −2t
                                                      (x01 − e−t x1 ) Π(x0 , x) dt .
                                        0  1 −  e
  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:
                         Z ∞
                 0             e−t
(11.4)      K1 (x , x) =             x0 (1 − e−t x01 x1 )(1 + e−t x01 x1 )Πnk=2 (1 + e−t x0k xk ) dt ,
                          0  1 − e−2t 1
which is
                                    Z ∞
                           0                e−t
(11.5)              K1 (x , x) =                  x0 (1 − e−2t )Πnk=2 (1 + e−t x0k xk ) dt ,
                                     0    1 − e−2t 1
which is
                                               Z ∞
(11.6)                         K1 (x0 , x) =           e−t x01 Πnk=2 (1 + e−t x0k xk ) dt ,
                                               0
                                 POINCARÉ INEQUALITY ON HAMMING CUBE                                                       13

  Now the kernel of T is K = (K1 , K2 , . . . , Kn ), where Ki is
                              Z ∞
                      0
(11.7)           Ki (x , x) =     e−t x0i Πnk6=i (1 + e−t x0k xk ) dt ,        i = 1, . . . , n .
                                       0


  Recall the notation C n = {−1, 1}n . We are interested in the norm of the integral operator
with kernel K = (K1 , . . . , Kn ) as the operator from L∞ (C n ) → L∞ (C n ; `2n ).
  Given x, y ∈ C n we write z = y · x = (y1 x1 , . . . , yn xn ) ∈ C n .

  Kernel Ki (x0 , x) can be written down as Ki (x0 , x) = xi K̃i (x0 , x), where
                                          Z ∞
                          K̃i (x0 , x) :=     e−t x0i xi Πnk6=i (1 + e−t x0k xk ) dt,
                                               0
and we see that this is a kernel of the form ki (x0 · xi ), that is, it is a convolution kernel.
  We use it with measure dµ(x0 ) that is invariant, meaning that dµ(x0 · x) is the same measure.
Notice also that the facts that Ki (x0 , x) = xi K̃i (x0 , 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∞ (C n ) → L∞ (C n ; `2n ).
  Let us write
(11.8)
                               Z ∞                                    Z 1
          −n                −n      −t    n        −t              −n
mi,z := 2 Ki (z, 1) = 2            e zi Πk6=i (1+e zk ) dt = 2            zi Πnk6=i (1+ρzk ) dρ , i = 1, . . . , n ,
                                 0                                       0
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 `∞      2
                                                                                           2n to `n .
In fact, this is just invariance:
                Z                               Z
                     K̃(x0 · x)f (x0 )dµ(x0 ) =   K̃(y)fx (y)dµ(y), fx (y) := f (y · x) .
                  Cn                               Cn
   Since f → fx is an isometry in L∞ (C n ), we see that the norm of our operators from L∞ (C n )
to L∞ (C n ; `2n ) is the same as the norm of matrix M from `∞      2
                                                             2n to `n .

  Rewriting again, we get:
              Z 1                                   Z 1
                  zi (1 − ρzi ) n                       zi − ρ n
  Ki (z, 1) =              2
                               Πk=1 (1 + ρzk ) dρ =           Π (1 + ρzk ) dρ ,
                                                             2 k=1
                                                                                                       i = 1, . . . , n ,
               0     1−ρ                             0 1−ρ
  Let us denote by d(z) = dist(z, 1) in Hamming metric. Then for z ∈ {−1, 1}n we have:
                                 Πnk=1 (1 + ρzk ) = (1 + ρ)n−d(z) (1 − ρ)d(z) .
  Thus,
                                 Z 1
                                       zi − ρ
(11.9)             Ki (z, 1) =                (1 + ρ)n−d(z) (1 − ρ)d(z) dρ ,      i = 1, . . . , n ,
                                  0    1 − ρ2
   Let Mρ := (mi,z (ρ))i=1,...,n; z∈{−1,1}n be the matrix acting from `∞            2               n
                                                                             2n to `n , whose n × 2 matrix
elements are given by the following formula:
                         zi − ρ
(11.10) mi,z (ρ) := 2−n            (1 + ρ)n−d(z) (1 − ρ)d(z) , i = 1, . . . , n, z ∈ {−1, 1}n , ρ ∈ (0, 1) .
                         1 − ρ2

                                                               R1
   Of course, matrix elements mi,z := 2−n Ki (z, 1) are just 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.
                                                        R1
   To compute the norm of the matrix M = (mi,z ) = 0 Mρ dρ as the matrix acting from `∞   2n to
 2
`n one can try to do two different things.
14               PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG



The first attempt. Calculate
                                          n          Z 1
                                          X                zi − ρ
(11.11)                   max        Ez         λi                (1 + ρ)n−d(z) (1 − ρ)d(z) dρ
                       λ, kλk`2 ≤1                    0    1 − ρ2
                             n            i=1
     Or one can try to use a rougher estimate as follows.

The second attempt. Calculate
                Z 1             n
                                X    zi − ρ
(11.12)                max Ez     λi      2
                                            (1 + ρ)n−d(z) (1 − ρ)d(z) dρ
                 0  λ, kλk 2
                          `n
                             ≤1      1 − ρ
                                                i=1
  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,
                                    Z 1
                                         zi − ρ
                             mi,z =           2
                                                (1 + ρ)n−d(z) (1 − ρ)d(z) dρ
                                      0  1 − ρ
seems to be treatable, they can be written down as certain combinatorial sums.

     For example,
                                            Z 1
                                 mi,1 =              (1 + ρ)n−1 dρ,        i = 1, . . . , n .
                                                0
For z = (1, . . . , 1, −1) we have
                                  Z 1
                           mi,z =     (1 + ρ)n−2 (1 − ρ) dρ,                  i = 1, . . . , n − 1 ,
                                      0
                                                            Z 1
                                           mn,z = −               (1 + ρ)n−1 dρ .
                                                             0

                          12. Computer experiment for finding Cdual
     Let us consider the quantity
                                                                          Z ∞
(12.1)                        Cdual,n :=                  sup         k         ∇Pt g dtk∞ ,
                                                kgkL∞ ({−1,1}n ) ≤1       0

and let us try to find its numerical values for small dimensions n.
     For n = 2 the optimizer is
                           g(x1 , x2 ) = min(x1 , x2 ) = (x1 x2 + 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 first 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 assumep it to make some guesses), then one would extrapolate from the plot that
Cdual,n would reach π/2 only around dimension n = 60. This means that there is probably
little insight to be gained from the specific structure of low-dimensional optimizers. Also, it is
very different 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,
                            POINCARÉ INEQUALITY ON HAMMING CUBE                                   15




                           Figure 1. Growth of dual constant with n.



                                          p
which is quite close to the Gaussian limit 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 growsptoo fast. We have already noted that the growth on this
figure suggests that we come close to π/2 only for n = 60 or 70. This experiment is beyond
the computer reach.
16                PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG

                                             13. Curl space and Cdual
     Let us remind the reader that
                                                                     Z ∞
                                    (f − Ef, g) = −(∇f,                       ∇Pt g dt) .
                                                                      0
     Therefore,
                                                                     Z ∞
                         E|f − Ef | ≤ k∇f k1 · sup                            ∇Pt g dt              ≤
                                                       kgk∞ ≤1       0                   L∞ /Curl

     So we need to estimate
                                                                     Z ∞
(13.1)                          C1 := sup              inf kh +                ∇Pt g dtk∞ ,
                                         kgk∞ ≤1 h∈Curl                   0

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:
                                                  1
                                          ∂k ϕ = (ϕxk →1 − ϕxk →−1 ) .
                                                  2
     Space Curl consists of vector functions h = (h1 , . . . , hn ), such that
(13.2)                                        ∂1∗ h1 + · · · + ∂n∗ hn = 0 .
     Here
                                             1
                                  ∂k∗ ϕ = xk (ϕxk →1 + ϕxk →−1 ) .
                                             2
In other words, it is a creation operator, that is
                                             (
                                               xk xS , if k ∈
                                                            / S,
                                    ∂k∗ xS =
                                               0,     k ∈S.
   Space Curl is very large, as the vector functions h such that ∂k∗ hk = 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 ∂k Hk
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:
                                               Z ∞
(13.4)                         Cdual := sup k      ∇Pt g dtk∞ ,
                                                  kgk∞ ≤1        0



13.1. Curl space in gaussian setting does not matter. Consider functions in L1 (R1 , γ1 )
orthogonal to all D := {f 0 : f ∈ C0∞ (R1 )}. Then
                                     Z
                                        hf 0 dγ1 = 0, ∀f 0 ∈ D .

Therefore,                          Z              Z
                                         0
                                −       h f dγ +        xhf dγ1 = 0,               ∀f ∈ C0∞ .
Hence
                                                                              x2
                                    h0 = xh, h = C · e 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.
                               POINCARÉ 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 = x1 h1 + x2 h2 ,
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
                                           Z ∞
                                    sup k       ∇Pt g dtk∞
                                          kgk∞ ≤1    0
for n = 1. Whence,
                         Z ∞                        Z ∞                              r
                                 (1)                          −t    (1)                  π
                     k         ∇Pt G dtk∞ = k             e        Pt ∇G dtk∞ ≈            .
                           0                         0                                   2
       (1)
Here Pt is Ornstein–Uhlenbeck semi-group in L1 (R1 , γ1 ). Since function G = G(x1 ), we can
                                          (n)
understand the last inequality also with Pt is Ornstein–Uhlenbeck semi-group in L1 (Rn , γn ):
                         Z ∞                        Z ∞                              r
                                 (n)                          −t    (n)                  π
                     k         ∇Pt G dtk∞ = k             e        Pt ∇G dtk∞ ≈            .
                          0                          0                                   2
                  (n)         (1)
This is because (Pt g)(x) = (Pt g)(x1 ) for g depending only on x1 .

                         14. Combinatorial formulation of Cdual
                                                 R∞
  Constant Cdual , given by Cdual := supkgk∞ ≤1 k 0 ∇Pt g dtk∞ is just
                                           Cdual = kT kL∞ →L∞ ,
where T is, e.g. from (11.1), that is, T = ∇∆−1 P0 .
  The norm kT kL∞ →L∞ is the smallest constant C in the following inequality:
                                         k∇∆−1 P0 f k∞ ≤ Ckf k∞ ,
which can be written down as follows
                                     k∇∆−1 f0 k∞ ≤ C inf kf0 + a1k∞ ,
                                                          a
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

                          k∇F k∞ = k∇(F − EF )k∞ ≤ C inf k∆F + a1k∞ .
                                                                     a
  Denote Hamming graph as (V, E), where vertices are denoted by i = 1, . . . , 2n .
  Then the previous best constant squared, namely, C 2 (that, is Cdual
                                                                    2 ) is the best constant in
                                                            n
the following inequality with arbitrary real numbers {ai }2i=1 :
                         X                                    X           2
(14.1)             sup        (ai − aj )2 ≤ C 2 inf sup a +      (ai − aj ) .
                   i∈V                              a∈R i∈V
                         j:(i,j)∈E                                       j:(i,j)∈E

  In particular, we have proved that with ε > 0 and independent of n
                        X                  π    2      X              2
(14.2)             sup       (ai − aj )2 ≤    − ε sup          (ai − aj ) .
                   i∈V                      2       i∈V
                         j:(i,j)∈E                                       j:(i,j)∈E
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 :
                             zi − ρ
(15.1)     mi,z (ρ) := 2−n          (1 + ρ)n−d(z) (1 − ρ)d(z) ,     i = 1, . . . , n, z ∈ {−1, 1}n , ρ ∈ (0, 1) .
                             1 − ρ2
     We considered it as acting from `∞      2
                                      2n to `n .
                                                             R1
   Of course, matrix elements mi,z := 2−n Ki (z, 1) are just 0 mi,z (ρ) dρ. Again we considered it
as acting from `∞       2                                                     1
                2n to `n , and we know that the sharp dual constant in L -Poincaré inequality is
                                         ∞      2
the norm of this matrix as acting from `2n to `n .
                                           R1
   The norm of the matrix M = (mi,z ) = 0 Mρ dρ as the matrix acting from `∞            2
                                                                                 2n to `n is
                                   n    Z 1
                                  X         zi − ρ
(15.2)                  max Ez       λi           2
                                                    (1 + ρ)n−d(z) (1 − ρ)d(z) dρ
                     λ, kλk`2 ≤1         0  1 − ρ
                            n       i=1
                                  π
     We know that it is less than 2 − ε, where ε > 0 does not depend on n.

   There is a “sister” problem, where L1 -Poincaré inequality is replaced by L∞ one. It cannot
have the form kf − Ef k∞ ≤ Ck∇f k∞ with constant independent of n. This is impossible, e.g.
because inequality a1 + · · · + an ≤ C(a21 + · · · + a2n )1/2 is false. However, if one changes the
definition of the gradient, then the corresponding inequality becomes meaningful and important
(see, e.g., [11] or [18].)
   Denote |∇f ˜ |(x) = Pn |∂i f (x)|. Then one can ask, whether the following inequality holds
                           i=1
and with what sharp constant independent of n:
(15.3)                              kf − Ef k∞ ≤ C∞ k∇f   ˜ k∞ ?
   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)                             ˜ (x)| ≤ 1 ∀x ∈ {−1, 1}n .
                                  |∇f
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
                                      `(x, y) ≤ 2 ∀x ∈ {−1, 1}n .
                                        y∼x
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
                 R1
M = (mi,z ) = 0 Mρ dρ defined in (11.8). In fact, repeating our reasoning in the previous
sections, we can notice that (15.3) is equivalent to finding
                                                  Z ∞
                           sup          inf kh +       ∇Pt f dtkL1 ({−1,1}n ;`∞
                                                                              n )
                                                                                  .
                        f :kf ||L1 ({−1,1}n ≤1 h∈Curl           0

     If Curl space would not play any role, that would mean that we are interested in
                                              Z ∞
                                 sup        k     ∇Pt f dtkL1 ({−1,1}n ;`∞
                                                                         n )
                                                                             .
                               f :kf ||L1 ({−1,1}n ≤1   0

     We can calculate this norm now. It is the norm of our familiar operator
                                              Z ∞
                                         f→       ∇Pt f dt
                                                            0
                                              POINCARÉ 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 (C n , dµ) to L1 (C n , dµ; `∞                      0                           0
                                         n ). Kernel Ki (x , x) can be written down as Ki (x , x) =
xi K̃i (x0 , x), where
                                          Z ∞
                                0
                          K̃i (x , x) :=      e−t x0i xi Πnk6=i (1 + e−t x0k xk ) dt,
                                                           0

and we see that this is a kernel of the form ki (x0 · xi ), that is, it is a convolution kernel.
   We use it with measure dµ(x0 ) that is invariant, meaning that dµ(x0 · x) is the same measure.
Notice also that the facts that Ki (x0 , x) = xi K̃i (x0 , 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 (C n ) → L1 (C n ; `∞
                       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 (C n ) → L1 (C n ; `∞
                            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 (C n ; `∞n ), which is
            Z                             Z                                 X
                 max |K̃i (z, 1)dµ(z) =         max |Ki (z, 1)dµ(z) =            max |mi,z | .
                    C n i=1,...,n                              C n i=1,...,n                z∈C n
                                                                                                    i=1,...,n


   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 ,
                                                                   R1
        • if d(z) = dist(z, 1) = 1, then maxi=1,...,n |mi,z | = 2−n 0 (1 + ρ)n−1 dρ again,
                                                                   R1
        • if d(z) = dist(z, 1) = 2, then maxi=1,...,n |mi,z | = 2−n 0 (1 + ρ)n−2 (1 − ρ)dρ, . . . ,
                                                                   R1
        • if d(z) = dist(z, 1) = n, then maxi=1,...,n |mi,z | = 2−n 0 (1 − ρ)n−1 dρ.
  Hence
                                         Z 1
 X
                                    −n                                           n(n − 1)
         max |mi,z | = 2                       [(1 + ρ)n−1 + n(1 + ρ)n−1 +                (1 + ρ)n−2 (1 − ρ)+
      n
        i=1,...,n                         0                                         2
z∈C
                                          Z 1
                     n−1             −n                               n(n − 1)                                           1−ρ
· · · + (1 − ρ)    ] dρ = 2                        [n(1 + ρ)n−1 +              (1 + ρ)n−2 (1 − ρ) + · · · + (1 − ρ)n−1 ]     dρ+
                                               0                         2                                               1−ρ
         Z 1
+ 2−n        (1 + ρ)n−1 dρ =
            0
       [(1 + ρ)n + n(1 + ρ)n−1 (1 − ρ) + n(n−1) (1 + ρ)n−2 (1 − ρ)2 + · · · + (1 − ρ)n − (1 + ρ)n ]
      Z 1
 −n                                         2
2                                                                                                   dρ+
    0                                            1−ρ
      Z 1
   −n
+2        (1 + ρ)n−1 dρ =
            0
                                                                          1 − ( 1+ρ  n
                                                                                            2−n n
      Z 1                                        Z 1                  Z 1
 −n      (1 + ρ + 1 − ρ)n − (1 + ρ)n          −n             n−1                 2 )
2                                      dρ + 2        (1 + ρ)     dρ =                  dρ +    (2 − 1) =
      0             1−ρ                           0                    0     1−ρ             n
  Z 1                          Z 1
        1 − xn           1                                            1         1 1           1
2               dx + O      =       (1 + x + x2 + . . . xn−1 ) dx + O     = 1 + + + · · · + + O(1) =
   1/2 2(1 − x)          n      1/2                                    n          2    3        n
log n + O(1) .
                                                            R∞
   We see that the operator norm supf :kf ||L1 ({−1,1}n ≤1 k 0 ∇Pt f dtkL1 ({−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.
20               PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG

                                              16. Some formulas for Cdual
     As we know
                                                  n          Z 1
                                                  X                zi − ρ
(16.1)           Cdual = lim            sup Ez          vi                (1 + ρ)n−d(1,z) (1 − ρ)d(1,z) dρ
                             n→∞ kvk         ≤1               0    1 − ρ2
                                        `2
                                         n        i=1

                     R1
     Let B(a, b) = 0 ta−1 (1 − t)b−1 denote the beta function. For k = d(1, z) integrals
                                                            (R
            Z 1                                                1/2 k
         −n      z i − ρ        n−d(1,z)        d(1,z)        0    t (1 − t)n−k−1 dt, zi = 1
        2              2
                         (1 + ρ)         (1 − ρ)       dρ =       1/2
             0 1−ρ                                           − 0 tk−1 (1 − t)n−k dt, zi = −1
                                                                R

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
                                                                     , if zi = 1,
                                                                  k)
              =
                 B1/2 (k, n − k + 1) = −F1/2 (n − k, n) 1n , if zi = −1 .
                                                         k(k )

  Here F1/2 (n − k − 1, n) is the probability of at least k + 1 successes in Bernoulli scheme with
n trials:
                                                            n   
                                                          X      n
                               F1/2 (n − k − 1, n) = 2−n            .
                                                                 r
                                                                           r=k+1
     Thus, we can rewrite the main part of formula (16.1) for Cdual as follows
                 n     Z 1
               X           zi − ρ
            Ez      vi          2
                                  (1 + ρ)n−d(1,z) (1 − ρ)d(1,z) dρ =
                        0  1 − ρ
                i=1
                    n           n                                n   
                1 X n h X               1          2zi             X    n                i
            = n              E       vi n                                   d(1, z) = k
               2         k              k
                                           1 + (1 − 2k/n)zi             r
                      k=0               i=1                                r=k+1−1zi =−1
                      n        n                                       n            
               1      X      h X                2zi                    X            n              i
             = n            E    vi                                                    d(1, z) = k
              2                          1 + (1 − 2k/n)zi                           r
                      k=0         i=1                              r=k+1−1zi =−1
                            n−1    n           n
                                           h X
                   1        X      X      n                zi                    i
             =                              E    vi                  d(1, z) = k
                 n2n−1                    r         1 + (1 − 2k/n)zi
                            k=0 r=k+1              i=1
                      n
                     
             1     1 n h X
                      X                                 i
          + n             E              vi d(1, z) = k
            2      k k
               k=1             i: zi =−1
                  h P                             i √
But kvk2 ≤ 1, so E   i: zi =−1  v i   d(1, z) = k   ≤ k. Therefore, the last sum is
                                               v
                             n
                                               u1 n 1 n
                                         u X             
                        1 X 1 n                                     2
                    ≤ n          √          ≤  t
                                                   n
                                                              ≤√         → 0.
                      2              k k          2      k k      n+1
                            k=1                      k=1

Hence, we can rewrite
                      n−1         Z 1
                      X      zi − ρ
                 Ez          vi     (1 + ρ)n−d(1,z) (1 − ρ)d(1,z) dρ =
                          0  1 − ρ2
                    i=1
                        n   n           n
                   1 X X n h X                          zi                      i
                                     E       v i                    d(1, z) = k   + o(1) .
                 n2n−1            r              1 + (1 − 2k/n)zi
                            k=0 r=k+1              i=1
                                 POINCARÉ INEQUALITY ON HAMMING CUBE                                    21

  Here is the first formula for Cdual :
                                                n−1     n          n
                                                               h X
                              1 X X                           n                zi                   i
(16.2)    Cdual = lim sup                                       E    vi                  d(1, z) = k .
                 n→∞ kvk ≤1 n2n−1                             r         1 + (1 − 2k/n)zi
                        2       `n              k=0 r=k+1               i=1



  We can simplify further this formula. For that, consider
                                       n   
                                   1 X n                   1
                       Φn (k) := n             = P[Binom(n, ) > k] .
                                  2         r              2
                                                r=k+1

This implies
                                            √   √
                                             n x n
                                       Φn (   +    ) → P[N (0, 1) > x] .
                                            2   2
Theorem 16.1.
                                     n/2   n
                                   2X h X              zi                   i
(16.3)           Cdual = lim sup         E   vi                  d(1, z) = k .
                        n→∞ kvk ≤1 n
                               2
                                                1 + (1 − 2k/n)zi
                                       `n       k=0         i=1

Proof. Define
                                                              zi
                                            Xik :=                      .
                                                       1 + (1 − 2k/n)zi
By Cauchy–Schwarz we get
                        Xn                       n
                                                 X
                               k
(16.4)                E[   vi Xi |d(1, z) = k] ≤   vi vj E[Xjk Xik |d(1, z) = k] .
                          i=1                                i,j=1

It is easy to see that
                          E[Xik |d(1, z) = k] = 0,
                                                       n2
                          E[(Xik )2 |d(1, z) = k] =           ,
                                                    4k(n − k)
                                                        1       n2
                          E[Xik Xjk |d(1, z) = k] = −                 ,          i 6= j.
                                                      n − 1 4k(n − k)
Hence, we know the Gramm matrix G := {E[Xjk Xik |d(1, z) = k]}. It is self adjoint rank one
                                                n     n           2
perturbation of the diagonal matrix diag( n−1      4k(n−k) ). So it is easy to calculate the norm of G.
     q
         n     n2
It is n−1   4k(n−k) .
   Hence, by (16.4)
                                                        s
                              n
                             X                                 n       n2
(16.5)                    E[     vi Xik |d(1, z) = k] ≤                       .
                                                            n − 1 4k(n − k)
                             i=1
             √
   Let bn = n log n. By the same spectral estimate for a cut-off matrix and by the fact that
Φn (k) ≤ 1, we will get
               n/2+bn                                        n/2+bn
                                                                     s
                                n
                X              X                              X           n      n2
(16.6)                Φn (k)E[     vi Xik |d(1, z) = k] ≤                                = O(bn ) .
                                                                        n − 1 4k(n − k)
               k=n/2−bn               i=1                             k=n/2−bn

Thus,
                     n/2+bn          n       n
                                         h X
              1           X          X  n                zi                   i    log n 
(16.7)                                    E    vi                  d(1, z) = k = O √       .
            n2n−1                       r         1 + (1 − 2k/n)zi                    n
                    k=n/2−bn r=k+1                    i=1
22              PAATA IVANISVILI, DONG LI, RAMON VAN HANDEL, ALEXANDER VOLBERG
                                                                        q
                                                                             n    n2       √
Using the spectral estimate for another cut-off matrix and the fact that n−1   4k(n−k) = O( n),
we get
                                                 s
                        n
                       X                             n      n2         √
(16.8)               E[   vi Xik |d(1, z) = k] ≤                   = O( n) .
                                                   n − 1 4k(n − k)
                              i=1
Hence,
                n−1               n                                              √               n−1
                X               h X                     zi                   i                    X                 
                         Φn (k)E    vi                            d(1, z) = k = O n                        Φn (k)
                                                 1 + (1 − 2k/n)zi
              k=n/2+bn                    i=1                                                   k=n/2+bn
                                                                        2
(16.9)        = O(n3/2 Φn (n/2 + bn )) = O(n3/2 e− log n ) .
                      n−1         n       n
                                      h X
          1           X           X  n                zi                   i               2 
(16.10)                                E    vi                  d(1, z) = k = O n1/2 e− log n .
        n2n−1                        r         1 + (1 − 2k/n)zi
                  k=n/2+bn r=k+1                        i=1

So when we come to the limit with n → ∞ in (16.2), we are left with
                                n−1    n    h X   n
                         1      X     X     n                     zi                    i
   Cdual = lim sup                             E       v i                  d(1, z) = k   =
          n→∞ kvk ≤1 n2n−1                  r              1 + (1 − 2k/n)zi
                  2      `n                k=n/2−bn r=k+1                   i=1
                              n−1                        n
                    2         X                        h X                 zi                   i
      = lim     sup                       Φn (k)E              vi                    d(1, z) = k =
         n→∞ kvk ≤1 n
                2
                                                                    1 + (1 − 2k/n)zi
                 `n       k=n/2−bn                       i=1
                              n−1            n
                    2         X            h X                 zi                   i
      = lim     sup                       E    vi                        d(1, z) = k ,
         n→∞ kvk ≤1 n
                2
                                                        1 + (1 − 2k/n)zi
                 `n       k=n/2−bn              i=1

the last equality being true because in this range of k we have
                                                                    2
                                                1 − O(e− log n ) ≤ Φn (k) ≤ 1 .
     Now we can add back
                                    n/2+bn         n
                              2      X           h X                  zi                    i
                                                E    vi                         d(1, z) = k
                              n                                1 + (1 − 2k/n)zi
                                  k=n/2−bn             i=1

and
                                     n−1           n
                              2      X            zi
                                                 h X                    i
                                                E    vi     d(1, z) = k
                              n            1 + (1 − 2k/n)zi
                         k=n/2+bn      i=1
                                                     2 
as we already saw that they are O log
                                   √ n and O e− log n correspondingly. Theorem is completely
                                        
                                     n
proved.                                                                                   
Remark 16.2. From (16.5) and (16.2) one immediately deduces the estimate
                                                             n−1
                                                             X      1       π
(16.11)                                  Cdual ≤ lim      Φn (k) p         = .
                                                  n→∞             k(n − k)  2
                                                      k=1
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
                   Z 1            n
                                 X     zi − ρ                                    π
(16.12)        lim      sup Ez      vi       2
                                               (1 + ρ)n−d(1,z) (1 − ρ)d(1,z) dρ < .
              n→∞ 0 kvk ≤1
                          2
                                       1−ρ                                       2
                                    `n           i=1
                             POINCARÉ INEQUALITY ON HAMMING CUBE                                         23

                                             References
 [1] L. Ben Efraim, F. Lust-Piquard, Poincaré 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 Diffusion 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 Poincaré-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 differential 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://mathoverflow.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. Hytönen, 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)
