Suppose you are given a set of $n$ non-zero vectors in $\mathbb{R}^3$. What is the maximum number of pairs of them that are orthogonal? The current guess is $\le 2n$.
EDIT: I forgot to add that no two vectors should be colinear.
$\begingroup$
$\endgroup$
14
-
2$\begingroup$ Definitely it is superlinear. Take all vectors with integer coordinates in a large ball $x^2+y^2+z^2<R^2$. $\endgroup$– Fedor PetrovCommented Aug 11, 2015 at 19:48
-
1$\begingroup$ It's possible to get $n^{3/2}$. Just take $(k,0,0)$, and $(0,m,0)$ for $k,m=1,...,\sqrt{n}$. $\endgroup$– Oleg EroshkinCommented Aug 11, 2015 at 20:27
-
1$\begingroup$ Oleg, if $k,m$ vary up to $n/2$ we get even as many as $n^2/4$ pairs, but this is probably not permitted:) $\endgroup$– Fedor PetrovCommented Aug 11, 2015 at 20:43
-
5$\begingroup$ Still better, take $n/3$ nonzero points on each coordinate axis to get $(2/3)n^2$ pairs. Since there are no four points pairwise orthogonal the story is completed by Turan's theorem. Perhaps a more interesting question was intended though. $\endgroup$– Sean EberhardCommented Aug 11, 2015 at 21:54
-
2$\begingroup$ @OlegEroshkin: You're getting $n^3/9$ pairs from $n$ vectors? I don't think so. $\endgroup$– Robert IsraelCommented Aug 11, 2015 at 22:45
|
Show 9 more comments
1 Answer
$\begingroup$
$\endgroup$
4
The maximum is $cn^{4/3}$ for some constant $c$.
We may as well assume all our points are on the unit sphere $S$. Let $P$ be some plane not containing the origin, which we might think of as being far away. For each point $x\in S$ in our collection let $p_x$ be the intersection of the line through $0$ and $x$ with $P$ and let $\ell_x$ be the intersection of the hyperplane orthogonal to $x$ with $P$. Unless $P$ was chosen by your enemies then all these things are well defined. Note that $p_x\in\ell_y$ iff $x$ and $y$ are orthogonal, so orthogonality in our original collection becomes incidence in our new collection, and by the Szemeredi-Trotter theorem there are at most $O(n^{4/3})$ incidences.
To see that there is a construction with this many orthogonal pairs, take some example which shows that Szemeredi-Trotter is tight, and such that there are about as many points as lines, and read the above paragraph backwards. If $P$ is far away then this example will consist of two collections of about $n/2$ points carefully clustered around some two orthogonal points of $S$.
I read this construction in the following paper of Erdos, Hickerson, and Pach, which also contains references to many other things. See Theorem 2(ii) for this problem.
-
$\begingroup$ When we read the paragraph backwards, are we to construct different sets of points $x$ and $y$ on $S$ for the points $p_x$ and lines $l_y$ on $P$? Or is there some way of ensuring that every point $p_x$ agrees with some line $l_x$ on the resulting point $x$? Either way, you would still get $\sim n^{4/3}$, but I couldn't understand what "read the paragraph backwards" meant. $\endgroup$ Commented Aug 13, 2015 at 14:20
-
$\begingroup$ @YoavKallus Construct different sets of points $x$ and $y$. As you say, it only affects the constant. $\endgroup$ Commented Aug 13, 2015 at 15:22
-
$\begingroup$ I wonder whether this correspondence works for the finite vector space ${\mathbb F}_q^r$. Assuming we have a system of $n$ points and $l$ lines in ${\mathbb F}_q^r$ that determines $I$ incidences, how many points we get in ${\rm PG}(r,q)$ and how many pairs of them will be orthogonal? $\endgroup$– SevaCommented Aug 13, 2015 at 17:39
-
1$\begingroup$ @Seva I think most of it carries over, assuming "line" means $(r-1)$-dimensional hyperplane. Realize our copy of $\mathbb{F}_q^r$ as an affine hyperplane $P$ of $\mathbb{F}_q^{r+1}$. For each point in our collection we get a point in $\text{PG}(r,q)$ by projection, and for each "line" in our collection we get an $r$-dimensional hyperplane in $\mathbb{F}_q^{r+1}$ and hence a point in $\text{PG}(r,q)$ by duality. As before incidence corresponds to orthogonality. The number of points we get is between $\max(n,l)$ and $n+l$ and the number of orthogonal pairs is at least the number of incidences. $\endgroup$ Commented Aug 13, 2015 at 17:58