Skip to main content
3 of 3
added 146 characters in body
Gabe Conant
  • 3.3k
  • 3
  • 23
  • 34

We show $|H\cap V|\leq |S|^\ell$. The proof is by induction on $\ell\leq n$ and allows $H$ to be an affine subspace.

If $\ell=0$ then the result is clear. So fix $\ell\geq 1$ and assume the result for $\ell-1$. Fix a finite set $S\subset\mathbb{R}$ and let $V=S^n$. Let $H$ be an affine subspace of $\mathbb{R}^n$ of dimension $\ell$.

For $i\leq n$ and $r\in\mathbb{R}$, let $W^r_i\subseteq\mathbb{R}^n$ be the $(n-1)$-dimensional affine space of vectors whose $i^{\text{th}}$ coordinate is $r$. There is some $i\leq n$ such that for all $r\in\mathbb{R}$, $H$ is not contained in $W^r_i$. (Otherwise, if for all $i\leq n$, there is some $r_i$ such that $H\subseteq W^{r_i}_i$, then $H=\{(r_1,\ldots,r_n)\}$, contradicting $\ell\geq 1$.)

Now, for a contradiction suppose $|H\cap V|\geq |S|^\ell+1$. For $s\in S$, let $H_s=H\cap W^s_i$. Then $\{H_s\cap V\}_{s\in S}$ is a partition of $H\cap V$. So there is some $s\in S$ such that $|H_s\cap V|\geq |S|^{\ell-1}+1$. Since $H$ is not contained in $W^s_i$, it follows that $H_s$ is an affine space of dimension $\ell-1$. This contradicts the induction hypothesis.

Gabe Conant
  • 3.3k
  • 3
  • 23
  • 34