  We study a conjecture called "linear rank conjecture" recently raised in
(Tsang et al., FOCS'13), which asserts that if many linear constraints are
required to lower the degree of a GF(2) polynomial, then the Fourier sparsity
(i.e. number of non-zero Fourier coefficients) of the polynomial must be large.
We notice that the conjecture implies a surprising phenomenon that if the
highest degree monomials of a GF(2) polynomial satisfy a certain condition,
then the Fourier sparsity of the polynomial is large regardless of the
monomials of lower degrees -- whose number is generally much larger than that
of the highest degree monomials. We develop a new technique for proving lower
bound on the Fourier sparsity of GF(2) polynomials, and apply it to certain
special classes of polynomials to showcase the above phenomenon.
