Maximal Number of Pairs of Orthogonal vectors in a set of $n$ vectors in $\mathbb{R}^3$

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.

• Definitely it is superlinear. Take all vectors with integer coordinates in a large ball $x^2+y^2+z^2<R^2$. – Fedor Petrov Aug 11 '15 at 19:48
• It's possible to get $n^{3/2}$. Just take $(k,0,0)$, and $(0,m,0)$ for $k,m=1,...,\sqrt{n}$. – Oleg Eroshkin Aug 11 '15 at 20:27
• 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:) – Fedor Petrov Aug 11 '15 at 20:43
• 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. – Sean Eberhard Aug 11 '15 at 21:54
• @OlegEroshkin: You're getting $n^3/9$ pairs from $n$ vectors? I don't think so. – Robert Israel Aug 11 '15 at 22:45

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

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