12
$\begingroup$

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.

$\endgroup$
  • 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 Petrov Aug 11 '15 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 Eroshkin Aug 11 '15 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 Petrov Aug 11 '15 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 Eberhard Aug 11 '15 at 21:54
  • 2
    $\begingroup$ @OlegEroshkin: You're getting $n^3/9$ pairs from $n$ vectors? I don't think so. $\endgroup$ – Robert Israel Aug 11 '15 at 22:45
12
$\begingroup$

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.

http://www.renyi.hu/~p_erdos/1989-02.pdf

$\endgroup$
  • $\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$ – Yoav Kallus Aug 13 '15 at 14:20
  • $\begingroup$ @YoavKallus Construct different sets of points $x$ and $y$. As you say, it only affects the constant. $\endgroup$ – Sean Eberhard Aug 13 '15 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$ – Seva Aug 13 '15 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$ – Sean Eberhard Aug 13 '15 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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