2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.