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

CC BY-SA 2.5
2010-10-05T15:18:06.347Z
Thanks, Ramprasad! This is indeed much weaker than I want. But still, could you please give a link?
Alexander S. Kulikov
CC BY-SA 2.5
2010-10-05T18:29:56.267Z
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
CC BY-SA 2.5
2010-10-05T18:32:02.177Z
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
CC BY-SA 2.5
2010-10-07T06:52:29.750Z
Thank you, Ramprasad! This is indeed not hard to see.
Alexander S. Kulikov
CC BY-SA 2.5
2010-10-05T13:02:20.430Z
2010-10-05T13:02:20.430Z
Ramprasad
<p>The objects you are searching for are called <em>seedless affine dispersers</em> 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</p>

<p><a href="http://web.mit.edu/swastik/www/affine-disperser.pdf">Ben-Sasson and Kopparty in "Affine Dispersers from Subspace Polynomials"</a> 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.  </p>

<p>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 <a href="http://en.wikipedia.org/wiki/Field_trace">trace map</a> is that $Tr(x+y) = Tr(x) + Tr(y)$.  </p>

CC BY-SA 2.5
2010-10-05T16:37:59.147Z
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
CC BY-SA 2.5
2010-10-06T01:27:51.140Z
A video recording of a talk by Swastik on the paper is here: http://video.ias.edu/csdm/affinedispersers
arnab
CC BY-SA 2.5
2010-10-07T06:58:20.017Z
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
CC BY-SA 2.5
2010-10-05T15:43:18.143Z
2010-10-31T03:27:41.493Z
2010-10-31T03:27:41.493Z
arnab
<p>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)$. </p>

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

<p>Cross-post: <a href="https://mathoverflow.net/questions/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen">https://mathoverflow.net/questions/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen</a></p>

CC BY-SA 2.5
2010-10-05T12:13:29.623Z
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
CC BY-SA 2.5
2010-10-05T12:47:46.597Z
Oh, I'm sorry, the range is {0,1}, of course. Fixed.
Alexander S. Kulikov
CC BY-SA 2.5
2010-10-05T13:05:39.943Z
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
CC BY-SA 2.5
2010-10-05T13:21:43.480Z
Cross posted on [MO](http://mathoverflow.net/questions/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen). Please add a link to your question when you are cross posting.
Kaveh
CC BY-SA 2.5
2010-10-05T13:58:50.653Z
Also note that [simultaneous crossposting is discouraged](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-05T14:00:06.683Z
How is this question related to the tag [circuit-complexity]?
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-05T15:07:20.507Z
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
CC BY-SA 2.5
2010-10-05T15:12:01.143Z
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
CC BY-SA 2.5
2010-10-05T15:13:03.483Z
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
CC BY-SA 2.5
2010-10-05T15:18:12.350Z
@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
CC BY-SA 2.5
2010-10-06T11:55:54.133Z
@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
CC BY-SA 2.5
2010-10-07T07:36:21.237Z
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
<cc.complexity-theory><circuit-complexity><derandomization><linear-algebra>
A Boolean function that is not constant on affine subspaces of large enough dimension
Alexander S. Kulikov
# A Boolean function that is not constant on affine subspaces of large enough dimension

(Asked by: username_0 on 2010-10-05)

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>

**Tags:** cc.complexity-theory, circuit-complexity, derandomization, linear-algebra

> **Comments:**
> **username_1**: 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).  
> **username_0**: Oh, I'm sorry, the range is {0,1}, of course. Fixed.  
> **username_1**: 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.)  
> **username_2**: Cross posted on [MO](http://mathoverflow.net/questions/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen). Please add a link to your question when you are cross posting.  
> **username_1**: Also note that [simultaneous crossposting is discouraged](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231).  
> **username_1**: How is this question related to the tag [circuit-complexity]?  
> **username_0**: 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.  
> **username_0**: 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?..  
> **username_0**: 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.  
> **username_2**: @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.  
> **username_1**: @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.  
> **username_0**: 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).  

---

## 2 answers

### Answer by username_4 on 2010-10-05. Score: 25 | Accepted answer

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"](http://web.mit.edu/swastik/www/affine-disperser.pdf) 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](http://en.wikipedia.org/wiki/Field_trace) is that $Tr(x+y) = Tr(x) + Tr(y)$.

> **Comments:**
> **username_0**: Thanks a lot, Arnab! It seems that this is exactly what I need, but obviously I need time to go through the paper. =)  
> **username_4**: A video recording of a talk by Swastik on the paper is here: http://video.ias.edu/csdm/affinedispersers  
> **username_0**: 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).  

---

### Answer by username_3 on 2010-10-05. Score: 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$.

> **Comments:**
> **username_0**: Thanks, username_3! This is indeed much weaker than I want. But still, could you please give a link?  
> **username_3**: 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]  
> **username_3**: 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.  
> **username_0**: Thank you, username_3! This is indeed not hard to see.  

---

