DIMENSION OF PROJECTIONS IN BOOLEAN FUNCTIONS

A projection is a subset of {0, 1}(n) given by equations of the form x (i) = x(j), x(i) = (x) over bar(j), x(i) = 0, and x(i) = 1, where for 1 less than or equal to i less than or equal to n, x(i) are Boolean g variables and (x) over bar(i) are their complements. We study monochro matic projections in 2-colorings of an n-dimensional Boolean cube. We also study the dimension of the largest projection contained in a set specified by its density. We prove almost matching lower and upper bou nds on the density of a set required to guarantee the existence of a d -dimensional projection. We also prove almost tight upper and lower bo unds on the dimension of monochromatic projections in arbitrary Boolea n functions. We then prove almost tight upper and lower bounds on the dimension of monochromatic projections in Boolean functions represente d by low degree GF(2) polynomials. It follows from these lower bounds that low-degree GF(2) polynomials can define Boolean functions which a re close to being extremal with respect to the property of having no l arge dimensional monochromatic projections.