Analysis of Boolean Functions in Lean

9.3. Single-bit hypercontractivity🔗

Definition9.3.1
Group: Chapter 9: Basics of hypercontractivity (100)
Group member previews
Preview
Theorem 9.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 11
Reverse dependency previews
Preview
Lemma 9.3.2
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Definition 9.13. Let 1\le p\le q\le\infty and 0\le\rho<1. A real random variable X with finite q-norm is (p,q,\rho)-hypercontractive when, for all a,b\in\mathbb R, \|a+\rho bX\|_q\le\|a+bX\|_p.

Lean code for Definition9.3.14 declarations
  • defdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    def FABL.uniformLInfinityNorm.{u_1} {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (f : Ω  ) : 
    def FABL.uniformLInfinityNorm.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (f : Ω  ) : 
    The actual uniform `L∞` norm on a nonempty finite domain. 
  • defdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    def FABL.uniformLpNormENNReal.{u_1} {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (q : ENNReal) (f : Ω  ) : 
    def FABL.uniformLpNormENNReal.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (q : ENNReal) (f : Ω  ) : 
    A finite uniform exponent norm which agrees with the established real-exponent API at every
    finite exponent and uses the maximum at `∞`. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformLpNormENNReal_coe.{u_1} {Ω : Type u_1} [Fintype Ω]
      [Nonempty Ω] (q : NNReal) (f : Ω  ) :
      FABL.uniformLpNormENNReal (↑q) f = FABL.uniformLpNorm (↑q) f
    theorem FABL.uniformLpNormENNReal_coe.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (q : NNReal) (f : Ω  ) :
      FABL.uniformLpNormENNReal (↑q) f =
        FABL.uniformLpNorm (↑q) f
    Compatibility with FABL's existing `uniformLpNorm` at a finite `NNReal` exponent. 
  • defdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    def FABL.IsHypercontractiveRandomVariable.{u_1} {Ω : Type u_1} [Fintype Ω]
      [Nonempty Ω] (p q : ENNReal) (ρ : ) (X : Ω  ) : Prop
    def FABL.IsHypercontractiveRandomVariable.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (p q : ENNReal) (ρ : ) (X : Ω  ) :
      Prop
    O'Donnell, Definition 9.13, on a finite probability space. 
Lemma9.3.2
Group: Chapter 9: Basics of hypercontractivity (100)
Group member previews
Preview
Theorem 9.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 9.3.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 0L∃∀N

Remark 9.14. By homogeneity it is enough to check the defining inequality with a=1 or with b=1. If it holds at \rho, it also holds at every 0\le\rho'\le\rho.

Lean code for Lemma9.3.24 theorems
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformLpNorm_const_mul.{u_1} {Ω : Type u_1} [Fintype Ω] (p c : )
      (f : Ω  ) (hp : 0 < p) :
      (FABL.uniformLpNorm p fun x => c * f x) = |c| * FABL.uniformLpNorm p f
    theorem FABL.uniformLpNorm_const_mul.{u_1}
      {Ω : Type u_1} [Fintype Ω] (p c : )
      (f : Ω  ) (hp : 0 < p) :
      (FABL.uniformLpNorm p fun x =>
          c * f x) =
        |c| * FABL.uniformLpNorm p f
    Positive finite-exponent uniform norms are absolutely homogeneous. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformLInfinityNorm_const_mul.{u_1} {Ω : Type u_1} [Fintype Ω]
      [Nonempty Ω] (c : ) (f : Ω  ) :
      (FABL.uniformLInfinityNorm fun x => c * f x) =
        |c| * FABL.uniformLInfinityNorm f
    theorem FABL.uniformLInfinityNorm_const_mul.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (c : ) (f : Ω  ) :
      (FABL.uniformLInfinityNorm fun x =>
          c * f x) =
        |c| * FABL.uniformLInfinityNorm f
    The actual finite-uniform `L∞` norm is absolutely homogeneous. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformLpNormENNReal_const_mul.{u_1} {Ω : Type u_1} [Fintype Ω]
      [Nonempty Ω] (q : ENNReal) (c : ) (f : Ω  ) (hq : q  0) :
      (FABL.uniformLpNormENNReal q fun x => c * f x) =
        |c| * FABL.uniformLpNormENNReal q f
    theorem FABL.uniformLpNormENNReal_const_mul.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (q : ENNReal) (c : ) (f : Ω  )
      (hq : q  0) :
      (FABL.uniformLpNormENNReal q fun x =>
          c * f x) =
        |c| * FABL.uniformLpNormENNReal q f
    The `ENNReal` finite-uniform interface is absolutely homogeneous at every nonzero exponent,
    including `∞`. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.IsHypercontractiveRandomVariable.of_normalized.{u_1} {Ω : Type u_1}
      [Fintype Ω] [Nonempty Ω] {p q : ENNReal} (hp : p  0) (hq : q  0)
      {ρ : } {X : Ω  }
      (h :
         (a b : ),
          a = 1  b = 1 
            (FABL.uniformLpNormENNReal q fun x => a + ρ * b * X x) 
              FABL.uniformLpNormENNReal p fun x => a + b * X x) :
      FABL.IsHypercontractiveRandomVariable p q ρ X
    theorem FABL.IsHypercontractiveRandomVariable.of_normalized.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      {p q : ENNReal} (hp : p  0)
      (hq : q  0) {ρ : } {X : Ω  }
      (h :
         (a b : ),
          a = 1  b = 1 
            (FABL.uniformLpNormENNReal q
                fun x => a + ρ * b * X x) 
              FABL.uniformLpNormENNReal p
                fun x => a + b * X x) :
      FABL.IsHypercontractiveRandomVariable p
        q ρ X
    Remark 9.14, homogeneity reduction: it is enough to check affine pairs for which one
    coefficient is one. 
Theorem9.3.3
Group: Chapter 9: Basics of hypercontractivity (100)
Group member previews
Preview
Theorem 9.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0XL∃∀N

Proposition 9.15. If independent random variables X and Y are both (p,q,\rho)-hypercontractive, then X+Y is (p,q,\rho)-hypercontractive. The book defers the proof to Exercise 10.2; this node supplies no assumption.

Theorem9.3.4
Group: Chapter 9: Basics of hypercontractivity (100)
Group member previews
Preview
Theorem 9.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 2
Reverse dependency previews
Preview
Theorem 9.3.5
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Proposition 9.16. For a uniform sign x, \|a+\rho bx\|_6\le\|a+bx\|_2 \quad\text{for all }a,b\in\mathbb R if and only if \rho\le\frac1{\sqrt5}.

Lean code for Theorem9.3.44 theorems
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.oneBit_twoSix (a b ρ : ) ( : ρ ^ 2  1 / 5) :
      (FABL.uniformLpNorm 6 fun x => a + ρ * b * FABL.signValue x) 
        FABL.uniformLpNorm 2 fun x => a + b * FABL.signValue x
    theorem FABL.oneBit_twoSix (a b ρ : )
      ( : ρ ^ 2  1 / 5) :
      (FABL.uniformLpNorm 6 fun x =>
          a + ρ * b * FABL.signValue x) 
        FABL.uniformLpNorm 2 fun x =>
          a + b * FABL.signValue x
    O'Donnell, Proposition 9.16, sufficient direction with the full sharp interval
    `0 ≤ ρ ≤ 1/√5`. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.oneBit_twoSix_necessary_sq (ρ : )
      (h :
         (a b : ),
          (FABL.uniformLpNorm 6 fun x => a + ρ * b * FABL.signValue x) 
            FABL.uniformLpNorm 2 fun x => a + b * FABL.signValue x) :
      ρ ^ 2  1 / 5
    theorem FABL.oneBit_twoSix_necessary_sq (ρ : )
      (h :
         (a b : ),
          (FABL.uniformLpNorm 6 fun x =>
              a + ρ * b * FABL.signValue x) 
            FABL.uniformLpNorm 2 fun x =>
              a + b * FABL.signValue x) :
      ρ ^ 2  1 / 5
    The quadratic term in Proposition 9.16 is necessary.  This is the small-`b`
    argument from the book, expressed as a limit along `b = 1/(m+1)`. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.oneBit_twoSix_iff (ρ : ) ( : 0  ρ) :
      (∀ (a b : ),
          (FABL.uniformLpNorm 6 fun x => a + ρ * b * FABL.signValue x) 
            FABL.uniformLpNorm 2 fun x => a + b * FABL.signValue x) 
        ρ  FABL.twoSixNoiseRoot
    theorem FABL.oneBit_twoSix_iff (ρ : )
      ( : 0  ρ) :
      (∀ (a b : ),
          (FABL.uniformLpNorm 6 fun x =>
              a + ρ * b * FABL.signValue x) 
            FABL.uniformLpNorm 2 fun x =>
              a + b * FABL.signValue x) 
        ρ  FABL.twoSixNoiseRoot
    O'Donnell, Proposition 9.16, with its ambient convention `0 ≤ ρ` made explicit. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformSign_twoSixHypercontractive :
      FABL.IsHypercontractiveRandomVariable 2 6 FABL.twoSixNoiseRoot
        FABL.signValue
    theorem FABL.uniformSign_twoSixHypercontractive :
      FABL.IsHypercontractiveRandomVariable 2
        6 FABL.twoSixNoiseRoot FABL.signValue
    O'Donnell, Proposition 9.16, hypercontractive-random-variable form. 
Theorem9.3.5
Group: Chapter 9: Basics of hypercontractivity (100)
Group member previews
Preview
Theorem 9.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 9.3.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 2
Reverse dependency previews
Preview
Theorem 9.1.3
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Theorem 9.17. Let x be a uniform sign and let q\in(2,\infty]. If 0\le\rho\le\frac1{\sqrt{q-1}}, then for all a,b\in\mathbb R, \|a+\rho bx\|_q\le\|a+bx\|_2.

Lean code for Theorem9.3.55 theorems
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.oneBit_twoQ (q a b ρ : ) (hq : 2 < q) (hρ0 : 0  ρ)
      ( : ρ  1 / (q - 1)) :
      (FABL.uniformLpNorm q fun x => a + ρ * b * FABL.signValue x) 
        FABL.uniformLpNorm 2 fun x => a + b * FABL.signValue x
    theorem FABL.oneBit_twoQ (q a b ρ : )
      (hq : 2 < q) (hρ0 : 0  ρ)
      ( : ρ  1 / (q - 1)) :
      (FABL.uniformLpNorm q fun x =>
          a + ρ * b * FABL.signValue x) 
        FABL.uniformLpNorm 2 fun x =>
          a + b * FABL.signValue x
    O'Donnell, Theorem 9.17, for every finite real exponent `q > 2`. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.oneBit_twoQ_sharp (q a b : ) (hq : 2 < q) :
      (FABL.uniformLpNorm q fun x =>
          a + 1 / (q - 1) * b * FABL.signValue x) 
        FABL.uniformLpNorm 2 fun x => a + b * FABL.signValue x
    theorem FABL.oneBit_twoQ_sharp (q a b : )
      (hq : 2 < q) :
      (FABL.uniformLpNorm q fun x =>
          a +
            1 / (q - 1) * b *
              FABL.signValue x) 
        FABL.uniformLpNorm 2 fun x =>
          a + b * FABL.signValue x
    The sharp finite-`q` endpoint of Theorem 9.17. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.oneBit_twoTop (a b : ) :
      (FABL.uniformLInfinityNorm fun x => a + 0 * b * FABL.signValue x) 
        FABL.uniformLpNorm 2 fun x => a + b * FABL.signValue x
    theorem FABL.oneBit_twoTop (a b : ) :
      (FABL.uniformLInfinityNorm fun x =>
          a + 0 * b * FABL.signValue x) 
        FABL.uniformLpNorm 2 fun x =>
          a + b * FABL.signValue x
    The `q = ∞` endpoint of Theorem 9.17.  The sharp correlation is zero. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformSign_twoQHypercontractive (q : NNReal) (hq : 2 < q) :
      FABL.IsHypercontractiveRandomVariable 2 (↑q) (1 / (q - 1))
        FABL.signValue
    theorem FABL.uniformSign_twoQHypercontractive
      (q : NNReal) (hq : 2 < q) :
      FABL.IsHypercontractiveRandomVariable 2
        (↑q) (1 / (q - 1)) FABL.signValue
    The finite-exponent part of Theorem 9.17 in the hypercontractive-random-variable interface. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformSign_twoTopHypercontractive :
      FABL.IsHypercontractiveRandomVariable 2  0 FABL.signValue
    theorem FABL.uniformSign_twoTopHypercontractive :
      FABL.IsHypercontractiveRandomVariable 2
         0 FABL.signValue
    The top-exponent endpoint in Definition 9.13. 
Theorem9.3.6
Group: Chapter 9: Basics of hypercontractivity (100)
Group member previews
Preview
Theorem 9.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 2
Reverse dependency previews
Preview
Theorem 9.1.4
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Theorem 9.18. Let x be a uniform sign and let 1\le p<2. If 0\le\rho\le\sqrt{p-1}, then for all a,b\in\mathbb R, \|a+\rho bx\|_2\le\|a+bx\|_p.

Lean code for Theorem9.3.65 theorems
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.normalized_pTwo_affine (p e : ) (hp1 : 1  p) (hp2 : p  2)
      (he : |e|  1) :
      (1 + (p - 1) * e ^ 2)  (((1 + e) ^ p + (1 - e) ^ p) / 2) ^ p⁻¹
    theorem FABL.normalized_pTwo_affine (p e : )
      (hp1 : 1  p) (hp2 : p  2)
      (he : |e|  1) :
      (1 + (p - 1) * e ^ 2) 
        (((1 + e) ^ p + (1 - e) ^ p) / 2) ^
          p⁻¹
    Normalized two-point form of the `(p,2)` inequality. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.affine_pTwo_hanner (p a b : ) (hp1 : 1  p) (hp2 : p  2) :
      (a ^ 2 + (p - 1) * b ^ 2)  ((|a + b| ^ p + |a - b| ^ p) / 2) ^ p⁻¹
    theorem FABL.affine_pTwo_hanner (p a b : )
      (hp1 : 1  p) (hp2 : p  2) :
      (a ^ 2 + (p - 1) * b ^ 2) 
        ((|a + b| ^ p + |a - b| ^ p) / 2) ^
          p⁻¹
    The sharp scalar two-point Hanner inequality underlying Theorem 9.18. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.oneBit_pTwo (p a b ρ : ) (hp1 : 1  p) (hp2 : p  2) (hρ0 : 0  ρ)
      ( : ρ  (p - 1)) :
      (FABL.uniformLpNorm 2 fun x => a + ρ * b * FABL.signValue x) 
        FABL.uniformLpNorm p fun x => a + b * FABL.signValue x
    theorem FABL.oneBit_pTwo (p a b ρ : )
      (hp1 : 1  p) (hp2 : p  2)
      (hρ0 : 0  ρ) ( : ρ  (p - 1)) :
      (FABL.uniformLpNorm 2 fun x =>
          a + ρ * b * FABL.signValue x) 
        FABL.uniformLpNorm p fun x =>
          a + b * FABL.signValue x
    O'Donnell, Theorem 9.18, including every smaller admissible correlation. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.oneBit_pTwo_sharp (p a b : ) (hp1 : 1  p) (hp2 : p  2) :
      (FABL.uniformLpNorm 2 fun x => a + (p - 1) * b * FABL.signValue x) 
        FABL.uniformLpNorm p fun x => a + b * FABL.signValue x
    theorem FABL.oneBit_pTwo_sharp (p a b : )
      (hp1 : 1  p) (hp2 : p  2) :
      (FABL.uniformLpNorm 2 fun x =>
          a +
            (p - 1) * b * FABL.signValue x) 
        FABL.uniformLpNorm p fun x =>
          a + b * FABL.signValue x
    Endpoint form of Theorem 9.18. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformSign_pTwoHypercontractive (p : NNReal) (hp1 : 1  p)
      (hp2 : p  2) :
      FABL.IsHypercontractiveRandomVariable (↑p) 2 ((p - 1))
        FABL.signValue
    theorem FABL.uniformSign_pTwoHypercontractive
      (p : NNReal) (hp1 : 1  p)
      (hp2 : p  2) :
      FABL.IsHypercontractiveRandomVariable
        (↑p) 2 ((p - 1)) FABL.signValue
    Theorem 9.18 in the hypercontractive-random-variable interface. 
Theorem9.3.7
Group: Chapter 9: Basics of hypercontractivity (100)
Group member previews
Preview
Theorem 9.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0
Used by 3
Reverse dependency previews
Preview
Theorem 9.2.3
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Proposition 9.19. Let T be self-adjoint on L^2(\Omega,\pi). Let p' and q' be the Hölder conjugates of p and q. If \|Tf\|_q\le C\|f\|_p \quad\text{for every }f, then \|Tg\|_{p'}\le C\|g\|_{q'} \quad\text{for every }g.

Lean code for Theorem9.3.73 theorems
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.uniformInner_le_uniformLpNorm_mul.{u_1} {Ω : Type u_1} [Fintype Ω]
      [Nonempty Ω] {p q : } (hpq : p.HolderConjugate q) (f g : Ω  ) :
      FABL.uniformInner f g 
        FABL.uniformLpNorm p f * FABL.uniformLpNorm q g
    theorem FABL.uniformInner_le_uniformLpNorm_mul.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      {p q : } (hpq : p.HolderConjugate q)
      (f g : Ω  ) :
      FABL.uniformInner f g 
        FABL.uniformLpNorm p f *
          FABL.uniformLpNorm q g
    Hölder's inequality for normalized finite-uniform norms at arbitrary finite conjugate
    exponents. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.exists_uniformLpNorm_dual.{u_1} {Ω : Type u_1} [Fintype Ω]
      [Nonempty Ω] (q p : ) (hpq : q.HolderConjugate p) (f : Ω  ) :
       g,
        FABL.uniformLpNorm p g  1 
          FABL.uniformInner f g = FABL.uniformLpNorm q f
    theorem FABL.exists_uniformLpNorm_dual.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (q p : ) (hpq : q.HolderConjugate p)
      (f : Ω  ) :
       g,
        FABL.uniformLpNorm p g  1 
          FABL.uniformInner f g =
            FABL.uniformLpNorm q f
    Sharpness of normalized Hölder on a nonempty finite uniform space: the `L^q` norm has a
    dual witness of `L^p` norm at most one. 
  • theoremdefined in FABL/Chapter09/OneBitHypercontractivity.lean
    complete
    theorem FABL.selfAdjoint_dual_bound.{u_1} {Ω : Type u_1} [Fintype Ω]
      [Nonempty Ω] (p q p' q' C : ) (hp : p.HolderConjugate p')
      (hq : q.HolderConjugate q') (T : (Ω  )  Ω  )
      (hself :
         (f g : Ω  ),
          FABL.uniformInner (T f) g = FABL.uniformInner f (T g))
      (hbound :
         (f : Ω  ),
          FABL.uniformLpNorm q (T f)  C * FABL.uniformLpNorm p f)
      (g : Ω  ) :
      FABL.uniformLpNorm p' (T g)  C * FABL.uniformLpNorm q' g
    theorem FABL.selfAdjoint_dual_bound.{u_1}
      {Ω : Type u_1} [Fintype Ω] [Nonempty Ω]
      (p q p' q' C : )
      (hp : p.HolderConjugate p')
      (hq : q.HolderConjugate q')
      (T : (Ω  )  Ω  )
      (hself :
         (f g : Ω  ),
          FABL.uniformInner (T f) g =
            FABL.uniformInner f (T g))
      (hbound :
         (f : Ω  ),
          FABL.uniformLpNorm q (T f) 
            C * FABL.uniformLpNorm p f)
      (g : Ω  ) :
      FABL.uniformLpNorm p' (T g) 
        C * FABL.uniformLpNorm q' g
    O'Donnell, Proposition 9.19, for a nonempty finite uniform probability space.