Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $U$ be the set of all non-null $n \times 1$ vectors $\mathbf{\mathrm{u}}$, where $u_i \in \lbrace-1, 0, 1\rbrace$. Let $\mathbf{\mathrm{x}}$ be an $n \times 1$ vector in $\mathbf{R}^n$. Let $\mathbf{\mathrm{u_x}}$ be the element of $U$ that is closest in angle to $\mathbf{\mathrm{x}}$. Then for any $\mathbf{\mathrm{x}}$, the maximum possible angle between $\mathbf{\mathrm{u_x}}$ and $\mathbf{\mathrm{x}}$ is ...

For $n = 2$, I get $\pi / 8$, obviously, but what is the general expression for larger $n$? I tried to think of this as a nearest-lattice-point problem on the (hyper-)sphere with a latitude-longitude lattice, but didn't get very far.

Thanks.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Given your initial answer for $\mathbf R^2,$ to move to $\mathbf R^3$ consider the vectors $(x,y,z)$ such that $x,y,z \geq 0$ that are equiangular between the plane vectors $(1,0,0)$ and $(1,1,0).$ These make up the plane $$ y = (\sqrt 2 - 1) x $$ with arbitrary $z \geq 0.$ In order to get the same angle with $(1,0,1)$ we get the ray $$ (\sqrt 2 - 1) x = y = z. $$ In order to get the same angle with $(1,1,1)$ we get the ray $$ y = (\sqrt 2 - 1) x, \; \; z = (\sqrt 3 - \sqrt 2) x. $$ Note that $ (\sqrt 2 - 1) = 0.4142... $ while $ (\sqrt 3 - \sqrt 2) = 0.317837...$ So in $\mathbf R^3$ the latter comes first while increasing $z,$, and best vector is $(1, \; \;\sqrt 2 - 1, \; \; \sqrt 3 - \sqrt 2) $ where you can work out the angle.

The same process gets you from $\mathbf R^3$ to $\mathbf R^4,$ take this answer for $\mathbf R^3$ and increase the fourth coordinate until you have an equal angle with $(1,1,1,1).$

And so on.

EDIT: I get it. In $\mathbf R^n$ the optimal vector is $$ V = (1, \; \;\sqrt 2 - 1, \; \; \sqrt 3 - \sqrt 2, \ldots, \sqrt n - \sqrt {n-1})$$ with equal angles to $A_1 = (1,0,\ldots,0),$ $A_2 = (1,1,0,\ldots,0),$ $A_3 = (1,1,1,0,\ldots,0), \ldots,$ $A_n = (1,1,1,\ldots,1).$

EDIT 2: Note that the entries of $V$ are strictly decreasing. As a result, if instead we consider $B_k$ with $k$ entries set to $1$ and the other $n-k$ set to $0,$ then $$ | A_k | \; = \; | B_k | $$ but $$ V \cdot A_k > V \cdot B_k .$$ Therefore the angle between $V$ and $B_k$ is larger than the angle between $V$ and $A_k,$ and the angle we actually constructed is the best we can get away with.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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