Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

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