# Maximum distance to nearest-lattice-point on (hyper-)sphere with unit lat-lon lattice.

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.

-

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).$
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.