18
$\begingroup$

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

Improve this question
$\endgroup$
12
  • $\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$
    – Tsuyoshi Ito
    Oct 5, 2010 at 12:13
  • $\begingroup$ Oh, I'm sorry, the range is {0,1}, of course. Fixed. $\endgroup$
    – Alexander S. Kulikov
    Oct 5, 2010 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$
    – Tsuyoshi Ito
    Oct 5, 2010 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, 2010 at 13:21
  • 1
    $\begingroup$ Also note that simultaneous crossposting is discouraged. $\endgroup$
    – Tsuyoshi Ito
    Oct 5, 2010 at 13:58

2 Answers 2

Reset to default
25
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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$
    – Alexander S. Kulikov
    Oct 5, 2010 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, 2010 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$
    – Alexander S. Kulikov
    Oct 7, 2010 at 6:58
9
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, Ramprasad! This is indeed much weaker than I want. But still, could you please give a link? $\endgroup$
    – Alexander S. Kulikov
    Oct 5, 2010 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, 2010 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, 2010 at 18:32
  • $\begingroup$ Thank you, Ramprasad! This is indeed not hard to see. $\endgroup$
    – Alexander S. Kulikov
    Oct 7, 2010 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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