# 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 the subspace $A$ of dimension $n/2$.

-
Is the range of f meant to be {0,1} instead of {0,1}^n? Otherwise I think that the answer is trivial (f can be the identity mapping). –  Tsuyoshi Ito Oct 5 '10 at 12:13
Oh, I'm sorry, the range is {0,1}, of course. Fixed. –  Alexander S. Kulikov Oct 5 '10 at 12:47
Because you ask for an explicit construction, I guess that a probabilistic method yields an existential proof. A wild guess: What happens if we identify {0,1}^n with the finite field of order 2^n and let f(x)=1 if and only if x corresponds to a square in the finite field? The set of quadratic residues modudo a prime often looks random, and now we need a set of vectors which looks random, so using the set of squares in a finite field sounds like a natural candidate. (I have not worked this out at all, and this may be way off the mark.) –  Tsuyoshi Ito Oct 5 '10 at 13:05
Cross posted on MO. Please add a link to your question when you are cross posting. –  Kaveh Oct 5 '10 at 13:21
Also note that simultaneous crossposting is discouraged. –  Tsuyoshi Ito Oct 5 '10 at 13:58

The objects you are searching for are called seedless affine dispersers with one output bit. More generally, a seedless disperser with one output bit for a family $\mathcal{F}$ of subsets of $\{0,1\}^n$ is a function $f : \{0,1\}^n \to \{0,1\}$ such that on any subset $S \in \mathcal{F}$, the function $f$ is not constant. Here, you are interested in $\mathcal{F}$ being the family of affine subspaces

Ben-Sasson and Kopparty in "Affine Dispersers from Subspace Polynomials" explicitly construct seedless affine dispersers for subspaces of dimension at least $6n^{4/5}$. The full details of the disperser are a bit too complicated to describe here.

A simpler case also discussed in the paper is when we want an affine disperser for subspaces of dimension $2n/5+10$. Then, their construction views ${\mathbb{F}}_2^n$ as ${\mathbb{F}}_{2^n}$ and specifies the disperser to be $f(x) = Tr(x^7)$, where $Tr: {\mathbb{F}}_{2^n} \to {\mathbb{F}}_2$ denotes the trace map: $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$. A key property of the trace map is that $Tr(x+y) = Tr(x) + Tr(y)$.

-
Thanks a lot, Arnab! It seems that this is exactly what I need, but obviously I need time to go through the paper. =) –  Alexander S. Kulikov Oct 5 '10 at 16:37
A video recording of a talk by Swastik on the paper is here: video.ias.edu/csdm/affinedispersers –  arnab Oct 6 '10 at 1:27
Thanks again, Arnab! I hope the video will help me to understand this paper (after reading the first several pages I see that it is quite complicated). –  Alexander S. Kulikov Oct 7 '10 at 6:58
Great talk! Thanks for the link Arnab. –  Ramprasad Oct 7 '10 at 7:22

A function that that satisfies something similar to (but much weaker than) what you want is the determinant of a matrix over $\mathbb{F}_2$. It can be shown that the determinant of an $n\times n$ matrix is non-constant on any affine subspace of dimension at least $n^2 - n$.

-
Thanks, Ramprasad! This is indeed much weaker than I want. But still, could you please give a link? –  Alexander S. Kulikov Oct 5 '10 at 15:18
I don't know of a place where this is written up but the proof is not hard. To prove the above claim, it is sufficient to show that if you take the determinant of an $n\times n$ matrix with variables in every entry, then the polynomial is non-zero modulo $n-1$ linear functions. Notice that going modulo a linear function is just replace one of the entries by a linear function of the other vars. Hence, we want to show that replacing just $n-1$ entries can't kill the determinant. It should be easy to see that by just permutations, we can move all these $n-1$ entries above the diagonal. [cntd] –  Ramprasad Oct 5 '10 at 18:29
Once all these entries are shifted above the diagonal, it is of course the case that the determinant still remains non-zero (since all the entries below and including the diagonal are independent, we can make the lower diagonal completely zero and the diagonal to be non-zero elements to give a non-zero determinant). The only trick here is that all the $n-1$ entries can be shifted above the diagonal. –  Ramprasad Oct 5 '10 at 18:32
Thank you, Ramprasad! This is indeed not hard to see. –  Alexander S. Kulikov Oct 7 '10 at 6:52