18

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

Community
  • 1
Alexander S. Kulikov
  • 895
  • 5
  • 11
  • 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 05 '10 at 12:13
  • Oh, I'm sorry, the range is {0,1}, of course. Fixed. – Alexander S. Kulikov Oct 05 '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 05 '10 at 13:05
  • 1
    Cross posted on MO. Please add a link to your question when you are cross posting. – Kaveh Oct 05 '10 at 13:21
  • 1
    Also note that simultaneous crossposting is discouraged. – Tsuyoshi Ito Oct 05 '10 at 13:58
  • How is this question related to the tag [circuit-complexity]? – Tsuyoshi Ito Oct 05 '10 at 14:00
  • I'm sorry, this is my first post on both forums. I've failed to understand where it is better to post this question, so decided to post it two times. Will never do this again. Also, I've just added a cross-post link. – Alexander S. Kulikov Oct 05 '10 at 15:07
  • Tsuyoshi, yes, a random function satisfies this property. Your candidate is really interesting, but I've never thought about such a function. At the moment, it is completely unclear to me what is an affine subspace in such a case (I mean what points it contain). Could you please give me an advice where I can read about such a function? If it looks like random, then maybe there are some lower bounds on its complexity in some computational models?.. – Alexander S. Kulikov Oct 05 '10 at 15:12
  • Concerning the tag circuit complexity, I came up to this function while trying to extend the gate elimination method for proving lower bounds on circuit size. – Alexander S. Kulikov Oct 05 '10 at 15:13
  • @Sasha K.: I personally think it is OK to cross post in some cases, just mention in your question that you are cross posting and add a link to the other one in each of them. – Kaveh Oct 05 '10 at 15:18
  • @Sasha: I guess that your question in a comment is no longer relevant but here is my answer anyway. I am not familiar with finite fields. Quadratic residues are used to construct an example proving that the Ramsey number R(4,4) is at least 18 (Greenwood and Gleason, Canadian Journal of Mathematics 1955 http://scholar.google.com/scholar?cluster=13240399796591062703&hl=en&as_sdt=2000&as_vis=1). I learned it in a class and I do not know good references other than giving a reference to the original paper. – Tsuyoshi Ito Oct 06 '10 at 11:55
  • Thanks, Tsuyoshi! It is not clear whether this idea helps, but this is an interesting candidate at least (and I have only a few of them). – Alexander S. Kulikov Oct 07 '10 at 07:36

2 Answers2

25

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

arnab
  • 7,000
  • 1
  • 38
  • 55
9

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

Ramprasad
  • 2,482
  • 18
  • 18
  • Thanks, Ramprasad! This is indeed much weaker than I want. But still, could you please give a link? – Alexander S. Kulikov Oct 05 '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 05 '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 05 '10 at 18:32
  • Thank you, Ramprasad! This is indeed not hard to see. – Alexander S. Kulikov Oct 07 '10 at 06:52