The Setting
Take a real multilinear polynomial of degree at most in variables and the polynomial threshold function it defines on the cube , where is for and for . The polynomial may vanish on the cube: is zero at every point with , and takes the value there. Can be replaced by a multilinear polynomial of degree at most that defines the same and vanishes nowhere on ? And once has no zero on , how large can the average sensitivity of be, that is, the expected number of coordinates for which reversing the -th coordinate of a uniform random point changes the value of ?
Polynomials on the Cube
The Boolean cube is the set of points whose coordinates are the real numbers or ; it has points.✦ For a point of and an index between and , the point of is with its -th coordinate reversed and the others unchanged.✦
A real polynomial in variables is multilinear when every monomial with a nonzero coefficient in has each variable to the power at most one.✦ For a subset of , the character of is the function on ; a multilinear polynomial is a real combination of these characters, one for each subset of , (1) The degree of a multilinear polynomial is the largest with .
The threshold sign is the function on the real numbers given by (2)✦ The polynomial threshold function of a real polynomial is the function on that sends each point to .✦
Average Sensitivity
For a real-valued function on and an index between and , the sensitive vertices of in direction are the points of with .✦ The average sensitivity of a real-valued function on is the sum over the directions of the number of sensitive vertices of in direction , divided by : (3)✦ with uniform on .
The Claim
Theorem 1. Let be a real multilinear polynomial in variables of degree at most .
There is a real multilinear polynomial of degree at most with (4)✦
If has no zero on , then (5)✦
What Is Checked
The claims (4) and (5) are stated over real multilinear polynomials (1) of degree at most and their values at the points of , the threshold sign (2) and the polynomial threshold functions it defines, and the average sensitivity (3), built from the reversed points and the sensitive vertices.