Intersection of a lower dimensional space and a discrete set

Question

Let $H\subset \mathbb{R}^n$ with dimension ${\rm dim}(H)=\ell<n$; let $S$ be a finite subset of reals.

My question is the following. Is it correct to say, $$ {\rm card}(H \cap V)\leqslant |S|^\ell $$ where $V$ is $n$-dimensional vectors with entries from $S$, that is, $V=\{v\in\mathbb{R}^n: v_i\in S,\forall i\}$.

I know this is related to several old results by Andrew Odlyzko. My reasoning is that, if ${\rm dim}(H)=\ell$, there exists $\ell$ determining coordinates $n_1,\dots,n_\ell$, such that once we fix $v_{n_1},\dots,v_{n_\ell}$, the rest is uniquely determined. There are precisely $|S|^\ell$ such vectors.

Remark: This is connected to the study of the singularity probability of random $n\times n$ binary matrices, initiated by Komlos, then enriched by the works of Komlos, Kahn-Komlos-Szemeredi, Tao-Vu, Bourgain et al, and finally, by Tikhomirov.

Answer 1

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.