Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

Gregory Gutin*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

A function f: -1,1n→R is called pseudo-Boolean. It is well-known that each pseudo-Boolean function f can be written as f(x)=∑ I∈Ff̂(I) χI(x), where F⊆I:I⊆[n], [n]=1,2,...,n, χI(x)= ∏ i∈I xi and f̂(I) are non-zero reals. The degree of f is max|I|:I∈F and the width of f is the minimum integer ρ such that every i∈[n] appears in at most ρ sets in F. For i∈[n], let x i be a random variable taking values 1 or -1 uniformly and independently from all other variables x j, j≠i. Let x=(x 1,...,x n). The p-norm of f is || f||p=( E[|f(x)|p])1p for any p<1. It is well-known that || f||q<|| f||p whenever q>p<1. However, the higher norm can be bounded by the lower norm times a coefficient not directly depending on f: if f is of degree d and q>p>1 then || f||q≤( q-1p-1)d2|| f||p. This inequality is called the Hypercontractive Inequality. We show that one can replace d by ρ in the Hypercontractive Inequality for each q>p<2 as follows: || f||q≤( (2r)!ρr-1)1(2r)|| f||p, where r=q2⌉. For the case q=4 and p=2, which is important in many applications, we prove a stronger inequality: || f||4≤( 2ρ+1)14|| f||2.

Original languageEnglish
JournalDiscrete Applied Mathematics
Volume160
Issue number15
Pages (from-to)2323-2328
ISSN0166-218X
DOIs
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Harmonic analysis
  • Hypercontractive inequality
  • MaxLin
  • Pseudoboolean function

Fingerprint

Dive into the research topics of 'Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width'. Together they form a unique fingerprint.

Cite this