Skip to main content
removed capitals from title
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Intersection of a Lower Dimensional Spacelower dimensional space and a Discrete Setdiscrete set

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

Intersection of a Lower Dimensional Space and a Discrete Set

Let $H\subset \mathbb{R}^n$ with dimension ${\rm dim}(H)=\ell<n$; $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.

Intersection of a lower dimensional space and a discrete set

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.

Removed the deprecated (discrete-mathematics) tag - see the tag info: https://mathoverflow.net/tags/discrete-mathematics/info (if there are some other suitable tags, choose some of them instead)
Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
Source Link
hookah
  • 1.1k
  • 8
  • 14

Intersection of a Lower Dimensional Space and a Discrete Set

Let $H\subset \mathbb{R}^n$ with dimension ${\rm dim}(H)=\ell<n$; $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.