# Mark some vectors in $\mathbb{R}^n$ in a way that every orthonormal basis has an odd number of marked vectors

Let $$n$$ be a natural number. Is there a set $$S$$ of vectors of norm $$1$$ in $$\mathbb{R}^n$$ such that every orthonormal basis of $$\mathbb{R}^n$$ contains an odd number of vectors from $$S$$?

If $$n$$ is odd, the answer is trivially yes: One can just let $$S$$ be the whole $$\mathbb{R}^n$$.

If $$n=2$$, the answer is also yes: For example, take $$S=\{(x,y)\in\mathbb{R}^2:xy>0\}\cup\{(1,0),(-1,0)\}$$.

What if $$n=4$$?

• @KevinCasto Does the orthant construction generalize to $\mathbb{R}^3$? For instance the vectors (2, 2, -1)/3, (2, -1, 2)/3, and (-1, 2, 2)/3 are an orthonormal basis that breaks the first generalization that comes to my mind. Commented Jul 30 at 13:50
• @MartinM.W. Whoops you're totally right, ignore that! Commented Jul 30 at 15:09
• Commented Jul 31 at 2:29

There is no such set $$S$$ for even $$n\ge4$$. We first handle the case $$n=4$$ by a parity argument: Below we provide a set $$V\subset\mathbb R^4$$ of $$18$$ distinct vectors and a set $$T$$ of $$9$$ orthonormal bases (with vectors from $$V$$) such that each vector from $$V$$ is contained in exactly $$2$$ bases from $$T$$.

Now double count the set $$$$M=\{(v, t)\;|\;v\in V\cap S, v\in t, t\in T\}.$$$$ Given $$v\in V\cap S$$, there are exactly two $$t\in T$$ such that $$(v,t)\in M$$. So $$\lvert M\rvert$$ is even. On the other hand, given one of the $$9$$ possibilities of $$t$$, the number of $$v$$'s such that $$(v,t)\in M$$ is odd by assumption. Thus $$\lvert M\rvert$$ is odd, a contradiction.

For simplicity of notation, in the following example the vectors differ from normed vectors by a positive factor. As a verification by hand might be a little cumbersome, I provide the straightforward Python code which proves the assertion:

from itertools import combinations, chain

T = [[(0, 1, 0, 0), (0, 0, 1, -1), (1, 0, 0, 0), (0, 0, 1, 1)],
[(0, 0, 1, -1), (1, 1, 1, 1), (1, 1, -1, -1), (1, -1, 0, 0)],
[(0, 1, 0, 1), (0, 0, 1, 0), (1, 0, 0, 0), (0, 1, 0, -1)],
[(0, 1, 0, 0), (1, 0, 0, -1), (0, 0, 1, 0), (1, 0, 0, 1)],
[(1, 1, -1, 1), (1, -1, 0, 0), (0, 0, 1, 1), (1, 1, 1, -1)],
[(1, -1, 1, -1), (1, 0, -1, 0), (1, 1, 1, 1), (0, 1, 0, -1)],
[(0, 1, 0, 1), (1, 1, 1, -1), (1, -1, 1, 1), (1, 0, -1, 0)],
[(1, -1, 1, -1), (1, 0, 0, 1), (0, 1, 1, 0), (1, 1, -1, -1)],
[(1, 1, -1, 1), (1, 0, 0, -1), (0, 1, 1, 0), (1, -1, 1, 1)]]

V = list(chain(*T))

def inner_prod(u, v):
return sum(x*y for x, y in zip(u, v))

def is_ortho(t):
return all(inner_prod(u, v) == 0 for u, v in combinations(t, 2))

assert all(is_ortho(t) for t in T)
assert all(V.count(v) == 2 for v in V)


Next we show that if $$\mathbb R^n$$ does not have such a set $$S$$, then neither does $$\mathbb R^{n+2}$$. The argument is inspired by Alex Ravsky's answer, but I believe it is easier to digest:

In order to achieve a contradiction, we assume that $$\mathbb R^{n+2}$$ has such a set $$S$$. Let $$e_1=(1,0,\ldots),\ldots,e_{n+2}=(\ldots,0,1)$$ be the standard basis vectors of $$\mathbb R^{n+2}$$. As $$n+2\ge3$$, there are two of these vectors which either are both in $$S$$ or none of them is in $$S$$. By reordering the coordinates, we may and do assume that this applies to $$e_{n+1}$$ and $$e_{n+2}$$.

For $$v\in\mathbb R^n$$ let $$\hat v\in\mathbb R^{n+2}$$ be $$v$$ extended by $$(0,0)$$. Set $$$$S'=\{v\in\mathbb R^n\;|\;\hat v\in S\}.$$$$ Now let $$v_1,\ldots,v_n$$ be an arbitrary orthonormal basis of $$\mathbb R^n$$. Then $$\hat v_1,\ldots,\hat v_n,e_{n+1},e_{n+2}$$ is an orthonormal basis of $$\mathbb R^{n+2}$$. By assumption, an odd number of them is contained in $$S$$, and this number equals modulo $$2$$ the number of $$v_i$$'s in $$S'$$. So $$S'$$ is an admissible set for $$\mathbb R^n$$, a contradiction.

Remark: I do not know if there is a more conceptual description of the given or similar examples for $$n=4$$. This example has some symmetries: Consider the graph whose vertex set is $$V$$ and two vertices are connected if and only if their vectors are orthogonal. Then this graph is vertex transitive with an automorphism group of order $$72$$. Attempts with smaller vertex transitive graphs were not successful.

• How did you find these bases? Commented Jul 30 at 17:07
• @DanielWeber I tried to find a counterexample among the vectors $v_i$ with entries $0,-1$, and $1$. Translate the condition to the system of linear equations over $\mathbb F_2$ with variables $x_i$ such that $\sum_{i\in I}x_i=1$ where the sets $I$ have the property that $\{v_i|i\in I\}$ is an orthogonal basis. It turned out that the system is not solvable. Commented Jul 30 at 17:47
• All of your vectors are (up to scalar multiple) roots in the $F_4$ root system. I put in a little time trying to find a symmetric presentation of this solution using the $F_4$ reflection group, but failed. Commented Aug 1 at 13:04
• @DavidESpeyer Interesting observation. But I do not see what distinguishes these $18$ vectors from the $48$ vectors of the $F_4$ root system. I believe your observation comes from that I looked for vectors with small entries, and it turned out that for small examples one doesn't need vectors of Hamming weight $3$. Commented Aug 1 at 13:47
• Nice. I had started looking for a nice counterexample based on on the "usual suspect" $E_8$, which would of course have produced a negative answer only for $n=8$. Commented Aug 6 at 15:48

Peter Mueller provided a negative answer for $$n=4$$. Based on it, we show that the answer is negative for any even $$n\ge 4$$.

Indeed, suppose for a contradiction that the space $$V=\mathbb R^n$$ admits a required coloring.

We start from the following simple observation. Let $$V'$$ be any subspace of $$V$$ and $$V''$$ be the orthogonal complement of the space $$V'$$, that is, $$V''=\{v\in V: (v,v')=0\mbox{ for any }v'\in V'\}.$$ Let $$B'$$ and $$B^*$$ be any orthonormal bases of the space $$V'$$ and $$B''$$ be any orthonormal basis of the space $$V''$$. Then both $$B'\cup B''$$ and $$B^*\cup B''$$ are the orthonormal bases for the space $$V$$, so they contain an odd number of vectors from $$S$$ each. So the parity of number of vectors from $$S$$ is the same for $$B'$$ and for $$B^*$$. Put $$p(V')=\bar 0$$, if this parity is even, and $$p(V')=\bar 1$$, otherwise, where $$\bar 0$$ and $$\bar 1$$ belong to the field $$\mathbb Z_2=\mathbb Z/2\mathbb Z$$ of residues modulo $$2$$. It is easy to see that $$p(V')=p(V^*)+p(V^{**})$$ for any splitting of $$V$$ into a sum of its orthogonal subspaces $$V^*$$ and $$V^{**}$$.

Peter Mueller's answer implies that $$p(V')$$ is even for any $$4$$-dimensional subspace $$V'$$ of $$V$$. Moreover, if the dimension of a subspace $$V'$$ of $$V$$ is divisible by $$4$$ then $$V'$$ splits into a direct sum of pairwise orthogonal $$4$$-dimensional subspaces, so $$p(V')=\bar 0$$. In particular, if $$n\equiv 0\pmod 4$$ then $$p(V)=\bar 0$$, a contradiction. So suppose that $$n\equiv 2\pmod 4$$. If there exists a $$2$$-dimensional subspace $$V'$$ of $$V$$ such that $$p(V')=\bar 0$$ then $$V$$ splits into a sum of $$V'$$ and its orthogonal complement $$V''$$, so $$p(V)=p(V')+p(V'')=\bar 0+\bar 0=\bar 0$$, a contradiction. Thus $$p(V')=\bar 1$$ for any $$2$$-dimensional subspace $$V'$$ of $$V$$. Now pick any vector $$v\in S$$ and any $$2$$-dimensional subspace $$V^*$$ of $$V$$, orthogonal to $$v$$. Since $$p(V^*)=\bar 1$$, there exists a vector $$u\in S\cap V^*$$. Let $$V'$$ be the subspace of $$V$$ spanned by its orthogonal basis $$\{v,u\}$$. Since both $$v$$ and $$u$$ belong to $$S$$, we have $$p(V')=\bar 0$$, a contradiction.

• If I understand your proof correctly, if there exists a 2D subspace V' of V such that p(V)=0 should read p(V \prime )=0. Commented Aug 1 at 18:08
• @ALG Thanks for your attention and sorry for the misprint. I fixed it. Commented Aug 1 at 18:44

A perhaps simpler(?) argument for @AlexRavsky's argument for the case of even $$n>4$$:

Claim. If $$n\ge3$$ and there is a red-blue-coloring of $$\mathbb R^n$$ such that every ON-basis has an odd number of red elements, then there is such a coloring also for $$\mathbb R^{n-2}$$.

Proof. The standard base $$e_1, \ldots, e_n$$ of $$\mathbb R^n$$ has two members of equal color, so wlog. $$e_{n-1}$$ and $$e_n$$ have the same color (are both red or both blue). Identify $$\mathbb R^{n-2}$$ with the span of $$e_1,\ldots, e_{n-2}$$. Then with the coloring inherited from $$\mathbb R^n$$, every ON-basis $$B$$ of $$\mathbb R^{n-2}$$ can be extended to an ON-basis $$B'$$ of $$\mathbb R^n$$ by adding $$e_{n-1}$$ and $$e_n$$. The number of red elements in $$B'$$ is odd and is also either the same or two more than the number of red elements in $$B$$. Hence the number of red elements in $$B'$$ is odd. $$\square$$

Then with @PeterMueller's negative result for $$n=4$$, the negative answer for all even $$n\ge4$$ follows by induction.

• Isn't this essentially the same argument as the second part of my answer (handling even $n\ge4$)? Btw, nice to see you here :-) Commented Aug 6 at 17:00