Skip to main content
flip bits, to correspond to modification of question.
Source Link

Here is a simple proof in the case when $K$ has characteristic $2$.

Let $m = \frac{n}{2}$. For $0\le i < m$, and $x\in K^n$, let $p_i(x)=(x_{2i},x_{2i+1})$.

I claim that for any fixed $0\le i < m$, $p_i(x)$ can take only $2$ possible values as $x$ runs through $A\cap \{0,1\}^n$ (this clearly gives the desired bound $|A\cap \{0,1\}^n|\le 2^m$). By assumption, $p_i(x)\ne (1,1)$$p_i(x)\ne (0,0)$. Suppose, for the sake of contradiction, that there exists $x,y,z \in A\cap \{0,1\}^n$ such that

  • $p_i(x)=(0,0)$$p_i(x)=(1,1)$
  • $p_i(y)=(0,1)$
  • $p_i(z)=(1,0)$

Then $y+z-x\in A$ since $A$ is an affine subspace, $y+z-x\in \{0,1\}^n$ since $K$ has characteristic $2$ and $p_i(y+z-x)=p_i(y)+p_i(z)-p_i(x)=(1,1)$$p_i(y+z-x)=p_i(y)+p_i(z)-p_i(x)=(0,0)$, which is a contradiction.

In other characteristics, the argument doesn't quite work since $y+z-x$ doesn't need to be in $\{0,1\}^n$ anymore, but maybe a variation of the idea could work.

Here is a simple proof in the case when $K$ has characteristic $2$.

Let $m = \frac{n}{2}$. For $0\le i < m$, and $x\in K^n$, let $p_i(x)=(x_{2i},x_{2i+1})$.

I claim that for any fixed $0\le i < m$, $p_i(x)$ can take only $2$ possible values as $x$ runs through $A\cap \{0,1\}^n$ (this clearly gives the desired bound $|A\cap \{0,1\}^n|\le 2^m$). By assumption, $p_i(x)\ne (1,1)$. Suppose, for the sake of contradiction, that there exists $x,y,z \in A\cap \{0,1\}^n$ such that

  • $p_i(x)=(0,0)$
  • $p_i(y)=(0,1)$
  • $p_i(z)=(1,0)$

Then $y+z-x\in A$ since $A$ is an affine subspace, $y+z-x\in \{0,1\}^n$ since $K$ has characteristic $2$ and $p_i(y+z-x)=p_i(y)+p_i(z)-p_i(x)=(1,1)$, which is a contradiction.

In other characteristics, the argument doesn't quite work since $y+z-x$ doesn't need to be in $\{0,1\}^n$ anymore, but maybe a variation of the idea could work.

Here is a simple proof in the case when $K$ has characteristic $2$.

Let $m = \frac{n}{2}$. For $0\le i < m$, and $x\in K^n$, let $p_i(x)=(x_{2i},x_{2i+1})$.

I claim that for any fixed $0\le i < m$, $p_i(x)$ can take only $2$ possible values as $x$ runs through $A\cap \{0,1\}^n$ (this clearly gives the desired bound $|A\cap \{0,1\}^n|\le 2^m$). By assumption, $p_i(x)\ne (0,0)$. Suppose, for the sake of contradiction, that there exists $x,y,z \in A\cap \{0,1\}^n$ such that

  • $p_i(x)=(1,1)$
  • $p_i(y)=(0,1)$
  • $p_i(z)=(1,0)$

Then $y+z-x\in A$ since $A$ is an affine subspace, $y+z-x\in \{0,1\}^n$ since $K$ has characteristic $2$ and $p_i(y+z-x)=p_i(y)+p_i(z)-p_i(x)=(0,0)$, which is a contradiction.

In other characteristics, the argument doesn't quite work since $y+z-x$ doesn't need to be in $\{0,1\}^n$ anymore, but maybe a variation of the idea could work.

Bounty Ended with 50 reputation awarded by BD107
Source Link
Antoine Labelle
  • 3.4k
  • 1
  • 8
  • 24

Here is a simple proof in the case when $K$ has characteristic $2$.

Let $m = \frac{n}{2}$. For $0\le i < m$, and $x\in K^n$, let $p_i(x)=(x_{2i},x_{2i+1})$.

I claim that for any fixed $0\le i < m$, $p_i(x)$ can take only $2$ possible values as $x$ runs through $A\cap \{0,1\}^n$ (this clearly gives the desired bound $|A\cap \{0,1\}^n|\le 2^m$). By assumption, $p_i(x)\ne (1,1)$. Suppose, for the sake of contradiction, that there exists $x,y,z \in A\cap \{0,1\}^n$ such that

  • $p_i(x)=(0,0)$
  • $p_i(y)=(0,1)$
  • $p_i(z)=(1,0)$

Then $y+z-x\in A$ since $A$ is an affine subspace, $y+z-x\in \{0,1\}^n$ since $K$ has characteristic $2$ and $p_i(y+z-x)=p_i(y)+p_i(z)-p_i(x)=(1,1)$, which is a contradiction.

In other characteristics, the argument doesn't quite work since $y+z-x$ doesn't need to be in $\{0,1\}^n$ anymore, but maybe a variation of the idea could work.