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$
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$ 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$ 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$ 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$ 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$ Aug 11, 2015 at 22:45

1 Answer 1

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$
4
  • $\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$ 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$ 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$
    – Seva
    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$ Aug 13, 2015 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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