Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $v_1,\ldots,v_m \in (\mathbb{Z}/2\mathbb{Z})^n$ be nonzero vectors. Is it always possible to choose a linear map $f : (\mathbb{Z}/2\mathbb{Z})^n \rightarrow \mathbb{Z}/2\mathbb{Z}$ such that $f$ is nonzero on at least half of the $v_i$, i.e. such that

$$|\{\text{$i$ $|$ $1 \leq i \leq m$ and $f(v_i) \neq 0$}\}| \geq \frac{1}{2}m?$$

My guess is that the answer is yes; at the very least, it is true for $m=1$ and when the $v_i$ enumerate all of the nonzero vectors.

share|improve this question
2  
Why don't you write in words what you want in the body of the question? Desciphering an equation when a perfectly good English sentence might be considerably easier to understand is silly! –  Mariano Suárez-Alvarez May 10 '13 at 3:45
2  
@MarianoSuárez-Alvarez : Sure thing. But isn't that a little pedantic? The equation isn't all that complicated... –  Monica May 10 '13 at 3:47
2  
I don't disagree with @Mariano's comment, but let me just add that this is a very nice question. Where did it come from? –  Pete L. Clark May 10 '13 at 13:33
2  
And I am someone who generally finds contest type problems quite boring (which is not to say that I know how to solve them). Looking back at the comments, Monica got a less warm welcome than she should have: $\mathbb{Z}/2$ could only mean one thing (unlike $\mathbb{Z}_2$!) and upon reflection I do disagree with Mariano's comment. I'm glad it turned out well in the end. –  Pete L. Clark May 10 '13 at 17:10
1  
@PeteL.Clark : Thanks! This experience definitely provides me another data point concerning using gendered names on the internet (I usually don't). It also appears that one can order the Babai book from U of C; see cs.uchicago.edu/research/publications/combinatorics –  Monica May 10 '13 at 17:25

2 Answers 2

up vote 6 down vote accepted

The statement is true and let us prove it by induction on $n$.

Denote $\mathbb{Z}/2\mathbb{Z}:=\mathbb{Z}_2:=\{0,1\}$. When $n=1$, the statement is clearly true. Now assume that when $n\le n_0$, the statement is true for every $m\ge 1$, and let us show the statement is true for $n:=n_0+1$ and every $m\ge 1$.

Consider $(\mathbb{Z}_2)^n$ as $(\mathbb{Z}_2)^{n-1}\times\mathbb{Z}_2$ and denote by $P$ and $Q$ the projections of $(\mathbb{Z}_2)^n$ to its first $n-1$ coordinates and its last coordinate respectively, i.e. $$P: (\mathbb{Z}_2)^n\mapsto (\mathbb{Z}_2)^{n-1},\quad(a_1,\dots,a_{n-1},a_n)\mapsto (a_1,\dots,a_{n-1}),$$ and $$Q: (\mathbb{Z}_2)^n\mapsto \mathbb{Z}_2,\quad(a_1,\dots,a_n)\mapsto a_n.$$

Up to a rearrangement of $v_1,\dots,v_m$, we may assume that there exists $0\le m'\le m$, such that $Qv_i\ne 0$ if and only if $m'<i\le m$. If $m'=0$, simply choose $f=Q$ and we are done, so let us assume that $m'\ge 1$. By definition, $Pv_1,\dots,Pv_{m'}\ne 0$. By the induction assumption on $n$, there exists a linear function $g:(\mathbb{Z}_2)^{n-1}\to \mathbb{Z}_2$, such that $$|\{ 1\le i\le m' \mid g(P v_i) \neq 0\}| \ge \frac{1}{2}m'.\tag{1}$$ For $j=0,1$, define $$f_j:(\mathbb{Z}_2)^n\to \mathbb{Z}_2,\quad v\mapsto g(Pv)+j\cdot Qv.\tag{2}$$ By definition, for $j=0,1$, $f_j$ is linear and $f_j(v_i)=g(P v_i)$ when $1\le m\le m'$. Then by $(1)$, for both $j=0$ and $j=1$, $$|\{ 1\le i\le m' \mid f_j(v_i) \neq 0\}| \ge \frac{1}{2}m'.\tag{3}$$ If $m'=m$, then we are done. Otherwise, note that by $(2)$ and the choice of $m'$, for $j=0,1$, $$f_j(v_i)=0 \iff g(Pv_i)=1-j\iff f_{1-j}(v_i)=1,\quad \forall\, m'<i\le m.$$ It follows that $$|\{ m'< i\le m \mid f_0(v_i) \neq 0\}|+|\{ m'< i\le m \mid f_1(v_i) \neq 0\}|=m-m'.\tag{4}$$ Combining $(3)$ and $(4)$, we can conclude that the statement is true for either $f=f_0$ or $f=f_1$, which completes the proof.


Remark: Thanks to PeteL.Clark's nice question in the comment, I realized that the conclusion can be generalized to arbitrary finite field with the same argument as above.

Claim: Let $\mathbb{F}_q$ be the finite field of $q$ elements and let $v_1,\dots,v_m$ be nonzero vectors in $(\mathbb{F}_q)^n$. Then there exists a linear function $f:(\mathbb{F}_q)^n\to\mathbb{F}_q$, such that $$|\{1\le i\le m\mid f(v_i)\ne 0\}|\ge\frac{(q-1)m}{q}.\tag{5}$$

Sketch of Proof: Define projections $P:(\mathbb{F}_q)^n\to (\mathbb{F}_q)^{n-1}$, $Q:(\mathbb{F}_q)^n\to\mathbb{F}_q$ similarly. Define $m'$ and rearrange $v_1,\dots,v_m$ similarly. By induction, we may assume that there exists a linear function $g:(\mathbb{F}_q)^{n-1}\to\mathbb{F}_q$, such that for $f_j=g\circ P+j\cdot Q$, $0\le j<q$, $$|\{1\le i\le m'\mid f_j(v_i)\ne 0\}|\ge\frac{(q-1)m'}{q}.\tag{6}$$ By definition of $m'$ and $f_j$, for every $m'<i\le m$, $f_0(v_i),\dots, f_{q-1}(v_i)$ are pairwise different, so one and only one of them is $0$. It follows that for some $0\le j<q$, $$|\{m'< i\le m\mid f_j(v_i)\ne 0\}|\ge\frac{(q-1)(m-m')}{q}.\tag{7}$$ $(5)$ follows from $(6)$ and $(7)$ for $f=f_j$.

share|improve this answer
1  
This is just lovely. –  Kevin Carlson May 10 '13 at 9:00
    
@KevinCarlson: Thank you! The question itself is lovely. –  23rd May 10 '13 at 9:08
    
How does this generalize to other finite fields, I wonder? –  Pete L. Clark May 10 '13 at 13:34
    
@PeteL.Clark: A simple observation based on this argument could show that for finite field $\mathbb{F}_q$, a lower bound is $\frac{(q-1)m}{q}$. Sketch of proof: we can define $f_j$, $0\le j\le q-1$ similarly as in $(2)$. By induction, we can assume that $(3)$ holds when $\frac{m'}{2}$ is replaced by $\frac{(q-1)m'}{q}$. When $i>m'$, $f_j(v_i)$ are pairwise different, so exactly only one of them is $0$. Then we can conclude that there exists $0\le j\le q-1$, such that $|\{m'<i\le m:f_j(v_i)\ne 0\}|\ge\frac{(q-1)(m-m')}{q}$, which completes the induction. –  23rd May 10 '13 at 14:01
    
@PeteL.Clark: Sorry, please ignore my first reply and see the current one. –  23rd May 10 '13 at 14:04

My coauthors and I needed this result recently (to prove something about pseudo-Anosov dilatations), and I was googling to see if it was known. I'm amazed that it was asked here so recently!

I'm answering now to record a short alternative proof that we found. I'll prove the same more general result that Landscape proved, namely:

Claim : Let $\vec{v}_1,\ldots,\vec{v}_m \in \mathbb{F}_q^n$ be nonzero vectors (not necessarily distinct). Then there exists a linear map $f : \mathbb{F}_q^n \rightarrow \mathbb{F}_q$ such that $f(\vec{v}_i) = 1$ for at least $\frac{q-1}{q}$ of the $\vec{v}_i$, i.e. such that $\{\text{$i$ $|$ $1 \leq i \leq m$, $f(\vec{v}_i) \neq 0$}\}$ has cardinality at least $\frac{q-1}{q}m$.

Proof : Let $\Omega$ be the probability space consisting of all linear maps from $\mathbb{F}_q^n \rightarrow \mathbb{F}_q$, each given equal probability. Let $\mathcal{X} : \Omega \rightarrow \mathbb{R}$ be the random variable that takes $f \in \Omega$ to the cardinality of the set $\{\text{$i$ $|$ $1 \leq i \leq m$, $f(\vec{v}_i) \neq 0$}\}$. We will prove that the expected value $E(\mathcal{X})$ of $\mathcal{X}$ is $\frac{q-1}{q} m$, which clearly implies that there exists some element $f \in \Omega$ such that $\mathcal{X}(f) \geq \frac{q-1}{q} m$.

To prove the desired claim, for $1 \leq i \leq m$ let $\mathcal{X}_i : \Omega \rightarrow \mathbb{R}$ be the random variable that takes $f \in \Omega$ to $1$ if $f(\vec{v}_i) \neq 0$ and to $0$ if $f(\vec{v}_i) = 0$. Viewing $\vec{v}_i$ as an element of the double dual $(\mathbb{F}_q^n)^{\ast \ast}$, the kernel of $\vec{v}_i$ consists of exactly $\frac{1}{q}$ of the elements of $(\mathbb{F}_q^n)^{\ast}$. This implies $E(\mathcal{X}_i) = \frac{q-1}{q}$. Using linearity of expectation (which recall does not require that the random variables be independent), we get that $$E(\mathcal{X}) = E(\sum_{i=1}^m \mathcal{X}_i) = \sum_{i=1}^m E(\mathcal{X}_i) = \sum_{i=1}^m \frac{q-1}{q} = \frac{q-1}{q} m,$$ as desired.

share|improve this answer

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.