# A direction that is far from any n directions of the vertices of a hypercube

$$C_n \stackrel{\text{def}}{=} \left\{\pm \frac{1}{\sqrt{n}} \right\}^n$$

Question:
Is the following true?

For all $$K>0$$, $$n$$ large enough and $$r_1,..,r_n \in C_n$$, there exists a unit vector $$c \in \mathbb{R}^n$$ such that $$|c\cdot r_i| \leq \frac{1}{K\sqrt{n}}$$ for all $$i \in [n]$$.

Discussion:
Since any $$(n-1)$$-subset of $$\mathbb{R}^n$$ is not a spanning set, it can be shown that:

For any $$r_1,..,r_{n-1} \in C_n$$, there exists a unit vector $$c \in \mathbb{R}^n$$ such that $$|c\cdot r_i| = 0 \left( \text{hence }\leq \frac{1}{K\sqrt{n}} \right)$$ for all $$i \in [n-1]$$.

For the $$n$$-subsets of $$C_n$$ that I checked manually (and with Mathematica), the conjecture is true.

• Have you tried a volume argument? Each point knocks out a certain amount of surface area of the hyper sphere which, I think for big $n$ might approach 0 fast enough.
– Eric
Commented Apr 29, 2023 at 14:09
• @AnneBauval, the problem is for $n$ "large enough", as mentioned in the statement. That is, for all $K>0$, there exists and $n_0$ such that for all $n \geq n_0$, [conjecture statement]. Commented Apr 29, 2023 at 14:24
• @Eric, each pair of caps that is knocked out by a single $r \in C_n$ contains a constant fraction of the volume of the sphere. See this answer for an "empirical proof" for this. Hence, the approach you suggested will not work. Commented Apr 29, 2023 at 14:47
• Check Khintchine inequality in Wkipedia. Commented Apr 29, 2023 at 18:39

This is false if $$K>1$$ and $$n$$ is a power of 2.

This is true for $$K=1$$ for all $$n$$.

Let’s give the counterexample when $$K>1$$ and $$n$$ is a power of 2 first.

When n is a power of 2, you can use the columns of the Hadamard matrix of size $$n$$ to get $$n$$ orthogonal vectors from within $$C_n$$.

Since the vectors $$r_i$$ form an orthogonal basis and $$c$$ is a unit vector, we have that:

$$1=\sum_i |c \cdot r_i|^2$$

Since the average value of $$|c_i \cdot r_i|^2$$ is $$1/n$$, at least one component must be at least as much, so there is no vector $$c$$ all of whom’s components $$|c \cdot r_i|$$ are less than $$1/\sqrt{n}$$.

—————-

If we fix $$K=1$$, then such a $$c$$ always exists.

Given some $$r_i$$, let’s show it. Note that if the $$r_i$$ are linearly dependent, we can just choose an orthogonal vector, so let’s assume they’re independent.

If you think of the $$r_i$$ as a basis and $$R$$ as the corresponding matrix, then $$C:=R^{-1}$$ gives the n $$c_i$$ vectors for which $$r_i \cdot c_j=\delta_{i,j}$$. Since the $$r_i$$ are unit vectors, $$|c_i| \geq c_i\cdot r_i / |r_i| =1$$.

Let’s loop through the list adding or subtract $$c_i$$ depending on whether $$c_i$$ has a positive dot product with the sum so far. Precisely, let $$s_0$$ be the zero vector. Let $$f$$ be the sign function (negative to -1, positive to 1, and let use 1 to break ties at 0). Then, for $$i\geq 0$$, let $$s_{i+1}=s_{i}+f(s_i \cdot c_{i+1})c_{i+1}$$.

Then by induction we have that $$|s_i|^2 \geq i$$ since $$|s_0|=0$$ and $$|s_{i+1}|^2=|s_{i}|^2+2f(s_i \cdot c_{i+1})s_i \cdot c_{i+1} + |c_{i+1}|^2 \geq i +0+1$$.

Also, as the sum or difference of all the $$c_i$$ we have that $$s\cdot r_i=\sum_{j=1}^{n} f(s_{j-1}\cdot c_j)c_j \cdot r_i=\sum_{j=1}^{n} f(s_{j-1}\cdot c_j)\delta_{i,j}= f(s_{i-1} \cdot c_i)=\pm 1$$.

Normalizing $$s$$ gives a vector with all the desired properties. It would be a unit vector for with $$|(s/|s|) \cdot r_i|=1/|s| \leq 1/\sqrt{n}$$ for all $$i$$ as desired.