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.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communitySuppose 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.
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.