MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.


share|cite|improve this question
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 Speyer Oct 5 '10 at 13:17
up vote 3 down vote accepted

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}$.

share|cite|improve this answer

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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.