262 Boolean Analysis — Low Degree

262.1 Overview

Cube hypercontractivity controls moment growth and concentration for functions of bounded Fourier degree. Both one-sided and two-sided anticoncentration estimates accompany properties of the stable-cube probability graph.

262.2 Declarations

Lemma 262.1 Squared first-to-second norm comparison

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube of Fourier degree at most \(k\in \mathbb N\). Then \(e^{-2k}\mathbb Ef^2\le (\mathbb E|f|)^2\).

Theorem 262.2 Stable-cube probability graph

✓

Let \(n\in \mathbb N\) and \(-1\le \rho \le 1\), and put \(W(x,y)=2^{-n}\prod _{i=0}^{n-1}[(1+\rho (-1)^{x_i+y_i})/2]\) for cube points \(x,y\). Then \(W(x,y)\ge 0\), \(W(x,y)=W(y,x)\), \(\sum _yW(x,y)=2^{-n}\) for every \(x\), and \(\sum _{x,y}W(x,y)=1\).

Theorem 262.3 Bounded-degree two-sided anticoncentration

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube of Fourier degree at most \(k\in \mathbb N\) with variance \(V\gt 0\). Then \(9/(16\cdot 9^k)\le \Pr (|f-\mathbb Ef|\gt \sqrt V/2)\).

Theorem 262.4 Higher norms of cube polynomials

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube of Fourier degree at most \(k\in \mathbb N\), and let \(q\ge 2\). Then \(\| f\| _q\le (\sqrt{q-1})^k\| f\| _2\).

Lemma 262.5 Interpolated lower-moment degree estimate

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube of Fourier degree at most \(k\in \mathbb N\), and let \(0\lt p\lt 2\lt q\). Then \(\| f\| _2\le \exp (kq(2-p)/(2p))\| f\| _p\).

Theorem 262.6 Lower norms of cube polynomials

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube of Fourier degree at most \(k\in \mathbb N\), and let \(1\le p\le 2\). Then \(\| f\| _2\le \exp ((2/p-1)k)\| f\| _p\).

Lemma 262.7 Admissible cube concentration exponent

✓

Let \(k\gt 0\) be an integer and \(t\ge (\sqrt{2e})^k\). Then \(t\gt 0\) and \(t^{2/k}/e\ge 2\).

Lemma 262.8 Optimized cube concentration moment

✓

Let \(k\gt 0\) be an integer and \(t\gt 0\), and put \(q=t^{2/k}/e\). Then \(((\sqrt q)^k/t)^q=\exp (-kt^{2/k}/(2e))\).

Theorem 262.9 Bounded-degree cube concentration

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube of Fourier degree at most a positive integer \(k\), with \(\| f\| _2\gt 0\). For \(t\ge (\sqrt{2e})^k\), \(\Pr (|f|\ge t\| f\| _2)\le \exp (-kt^{2/k}/(2e))\).

Theorem 262.10 Bounded-degree one-sided anticoncentration

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube of Fourier degree at most \(k\in \mathbb N\), with positive variance. Then \(e^{-2k}/4\le \Pr (\mathbb Ef\lt f)\).