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: https://mathoverflow.net/questions/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

  • $\begingroup$ 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). $\endgroup$ Oct 5 '10 at 12:13
  • $\begingroup$ Oh, I'm sorry, the range is {0,1}, of course. Fixed. $\endgroup$ Oct 5 '10 at 12:47
  • $\begingroup$ 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.) $\endgroup$ Oct 5 '10 at 13:05
  • 1
    $\begingroup$ Cross posted on MO. Please add a link to your question when you are cross posting. $\endgroup$
    – Kaveh
    Oct 5 '10 at 13:21
  • 1
    $\begingroup$ Also note that simultaneous crossposting is discouraged. $\endgroup$ 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)$.

  • $\begingroup$ Thanks a lot, Arnab! It seems that this is exactly what I need, but obviously I need time to go through the paper. =) $\endgroup$ Oct 5 '10 at 16:37
  • 1
    $\begingroup$ A video recording of a talk by Swastik on the paper is here: video.ias.edu/csdm/affinedispersers $\endgroup$
    – arnab
    Oct 6 '10 at 1:27
  • $\begingroup$ 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). $\endgroup$ Oct 7 '10 at 6:58

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

  • $\begingroup$ Thanks, Ramprasad! This is indeed much weaker than I want. But still, could you please give a link? $\endgroup$ Oct 5 '10 at 15:18
  • 1
    $\begingroup$ 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] $\endgroup$
    – Ramprasad
    Oct 5 '10 at 18:29
  • $\begingroup$ 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. $\endgroup$
    – Ramprasad
    Oct 5 '10 at 18:32
  • $\begingroup$ Thank you, Ramprasad! This is indeed not hard to see. $\endgroup$ Oct 7 '10 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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