Constructive relationships between algebraic thickness and normality

We study the relationship between two measures of Boolean functions; algebraic thickness and normality. For a function f, the algebraic thickness is a variant of the sparsity, the number of nonzero coefficients in the unique F₂ polynomial representing f, and the normality is the largest dimension of an affine subspace on which f is constant. We show that for 0<ϵ<2 , any function with algebraic thickness n^3−ϵ is constant on some affine subspace of dimension Ω(n^ϵ/2) . Furthermore, we give an algorithm for finding such a subspace. We show that this is at most a factor of Θ(√n) from the best guaranteed, and when restricted to the technique used, is at most a factor of Θ(√log n) from the best guaranteed. We also show that a concrete function, majority, has algebraic thickness Ω(2^n1/6) .