# A Boolean function that is not constant on affine subspaces of large enough dimension

I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of this subspace is $o(n)$.

It is not difficult to show that a symmetric function does not satisfy this property by considering a subspace $A=\{x \in \{0,1\}^n \mid x_1 \oplus x_2=1, x_3 \oplus x_4=1, \dots, x_{n-1} \oplus x_n=1\}$. Any $x \in A$ has exactly $n/2$ $1$'s and hence $f$ is constant on the subspace $A$ of dimension $n/2$.

-
I don't understand. If $f$ is the identity, $f(x)=x$ for all $x$, then $f$ isn't constant on any set of more than 1 element. Have you got the codomain wrong? –  Gerry Myerson Oct 5 '10 at 11:46
From your use of $o(n)$ notation, it seems like you are asking for an explicit family of functions $f_n$ for infinitely many integers $n$. Is it standard to call it one function? –  S. Carnahan Oct 5 '10 at 11:52
Maybe the target is supposed to be {0,1}. –  Greg Kuperberg Oct 5 '10 at 12:15
Just to make the obvious observation, a random function has this property. The probability of a random function being constant is $2*2^{-2^d}$, and the number of $d$-dimensional subspaces is $\approx 2^{d(n-d)}$, so the expected number of constant subspaces is less then $1$ as soon as $d$ is large enough that $2^d > d(n-d)$. (continued) –  David Speyer Oct 5 '10 at 13:17
Cross posted on cstheory –  Kaveh Oct 5 '10 at 13:22

Unless I am misreading it, the paper Affine dispersers from subspace polynomials by Ben-Sasson and Kopparty gives an explicit construction which is nonconstant on any affine subspace of dimension less than $6 n^{4/5}$.

-

You can use the explicit affine extractor construction by Bourgain (GAFA 2007). It is almost unbiased on any linear dimension affine subspace of $\{0,1\} ^n$

-