# 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
• Ooops, I'm sorry, the range is {0,1}, of course. Fixed. Yes, as far as I know, it is standard to say function instead of an infinite sequence of functions, one for each n. It is usually done in circuit complexity, for example. – Alexander S. Kulikov Oct 5 '10 at 12:50
• 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 E Speyer Oct 5 '10 at 13:17

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$