Choosing a linear map $(\mathbb{Z}/2\mathbb{Z})^n \rightarrow \mathbb{Z}/2\mathbb{Z}$ which is nonzero on half of a sequence of vectors

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.

Solution 1:

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

Solution 2:

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.