The Setting
Fix and and consider the Boolean functions on the cube that are the sign of a real polynomial of degree at most : the polynomial threshold functions of degree . Along an edge of the cube, from a point to a point that differs from it in one coordinate, such a function may change value or not, and its average sensitivity measures how often it does. The question is how large can be in terms of and ; Gotsman and Linial conjectured that it is at most of order .
Threshold Functions on the Cube
A point of the cube is a sequence of signs , and has points.✦ For a point of and a coordinate , the point of is with its -th coordinate reversed.✦
A real polynomial in the variables is multilinear if every monomial occurring in with a nonzero coefficient has degree at most one in each variable; such a polynomial of total degree at most has the form (1)✦ The value of a real polynomial at a point of is the real number obtained by substituting the coordinates of for the variables.✦
The sign function is the function from to given by (2)✦ The polynomial threshold function of a real polynomial in is the function on that takes the value at each point .✦
Average Sensitivity
Let be a real function on and a coordinate. A point of is sensitive for in direction if .✦ The average sensitivity of is the sum, over the directions, of the fraction of points of that are sensitive for in that direction: with a uniform random point of , (3)✦
The Claim
Theorem 1. Let and be integers with , and let be a real multilinear polynomial in of degree at most . Then the polynomial threshold function satisfies (4)✦ More generally, let be any integers and any real multilinear polynomial in of degree at most . Then (5)✦
What Is Checked
The claim is stated over the cube with its coordinate reversals , the real multilinear polynomials of total degree at most read at the points of , the sign function (2) with , the polynomial threshold function , and the average sensitivity (3), counted through the points sensitive in each direction.