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

Question

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$?

Answer 1

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 \begin{equation} M=\{(v, t)\;|\;v\in V\cap S, v\in t, t\in T\}. \end{equation} 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 \begin{equation} S'=\{v\in\mathbb R^n\;|\;\hat v\in S\}. \end{equation} 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.

Answer 2

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.

Answer 3

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.