Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

Cross-post: http://mathoverflow.net/questions/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

share|improve this question
    
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
1  
Cross posted on MO. Please add a link to your question when you are cross posting. –  Kaveh Oct 5 '10 at 13:21
1  
Also note that simultaneous crossposting is discouraged. –  Tsuyoshi Ito Oct 5 '10 at 13:58

2 Answers 2

up vote 23 down vote accepted

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

share|improve this answer
    
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
1  
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$.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

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.