Maximum number of $\pm 1$ valued vectors with pairwise negative inner product Let $S$ be a subset of $\{\pm 1\}^n$ such that $\forall x,y\in S$ ($x\neq y$), $x\cdot y<0$. Determine the upper bound of $|S|$ as precise as possible.

(Thanks to the example from @kodlu, the proof is revised.) What I have already proved is $\mathrm{sup}|S|\leq n$ for odd $n$, $\mathrm{sup}|S|\leq n/2$ for even $n$, via probabilistic methods:

 For any possible $S$, $m:=|S|$. Let $X_i=1$ whenever the chosen pair differs in the $i$ -th entry, $X_i=0$ otherwise. The expectation of pairs in $S$ different in the $i$ -th entry is
 $$\mathbb E X_i=\dfrac{m_i(m-m_i)}{\binom{m}{2}}\leq \dfrac{m^2}{4\cdot m(m-1)/2}=\dfrac{m}{2(m-1)}.$$
 Here $m_i$ is the number of $v\in S$ taking value $1$ in the $i$ -th entry. Since $\sum_{i=1}^n X_i$ is the total number of entries where pairs taking different values, we shall exclude those $m$ such that

 $$\mathbb E\sum_{i=1}^n X_i\leq\dfrac{mn}{2(m-1)}<\dfrac{n+1}{2}\quad \text{when } n \text{ is odd},$$
$$\mathbb E\sum_{i=1}^n X_i\leq\dfrac{mn}{2(m-1)}<\dfrac{n}{2}+1\quad \text{when } n \text{ is even}.$$
 Therefore, $\mathrm{sup}|S|\leq n+1$ for odd $n$, $\mathrm{sup}|S|\leq n/2$ for even $n$. There is no contradiction to the example from @kodlu.

The theorey of Plotkin bound is exactly what I'm looking for. See the answer by @Mike Earnest.
 A: I hope I did not misunderstand your question.
If you take a maximal length sequence Wikipedia entry here, all its inner products with its proper cyclic shifts are $-1$. These exist for all $n=2^d-1,$ since a primitive polynomial over $GF(2)$ exists for all degrees $d.$ There are more complicated designs of $\pm 1$ valued vectors which have the same property as well. To avoid trivialities let $d\geq 2.$
Note that the sequence is generated by a recurrence modulo 2 and then mapped to $\pm 1$ or you could generate it by multiplication if you start with $\pm 1.$
In addition if you also include the all 1's vector in this collection you can meet the modified upper bound of $n+1$ in the question, since the maximal length sequence derived vector will always have $2^{k-1}$ coordinates which are $-1$'s and $2^{k-1}-1$ coordinates which are $+1$'s. Thus it is not possible to obtain a tighter (smaller) upper bound for general $n.$
Example: Take $(1,1,-1,-1,-1,1,-1)$ and all its cyclic shifts. This is generated by starting with any
$$(s_0,s_1,s_2)\in \{\pm 1\}^3 \setminus \{(1,1,1)\}$$
and using the recursion $s_k=s_{k-1} s_{k-3}$ for $k\geq 3.$
So at least for $n$ one less than a power of 2, there are counterexamples to your claim that $|S|\leq \frac{n}{2}.$
For example  $(1,1,-1,-1,-1,1,-1)$ and its cyclic shifts can be used for $n=7.$ Explicitly we have the collection of 8 vectors which have inner products equal to $-1$ for any distinct pair.
$$
(+1,+1,-1,-1,-1,+1,-1)\\
(+1,-1,-1,-1,+1,-1,+1)\\
(-1,-1,-1,+1,-1,+1,+1)\\
(-1,-1,+1,-1,+1,+1,-1)\\
(-1,+1,-1,+1,+1,-1,-1)\\
(+1,-1,+1,+1,-1,-1,-1)\\
(-1,+1,+1,-1,-1,-1,+1)\\
(+1,+1,+1,+1,+1,+1,+1)
$$
A: The condition $x\cdot y<0$ for $\pm1$ vectors is equivalent to the Hamming distance between $x$ and $y$ being least $(n+1)/2$ when $n$ is odd, and at least $n/2+1$ when $n$ is even. Therefore, your question can be rephrased in the language of coding theory:

What is the largest binary code with length $n$ and distance $\lfloor n/2\rfloor +1$?

The Plotkin bound implies the following:

*

*When $n=4k$, there are at most $2\lfloor \frac{2k+2}{3}\rfloor$ vectors in $S$.


*When $n=4k+1$, there are at most $2k+2$ vectors in $S$.


*When $n=4k+2$, there are at most $2k+2$ vectors in $S$.


*When $n=4k+3$, there are at most $4k+4$ vectors in $S$.
Levenshtein showed that the Plotkin bound is attainable provided certain Hadamard matrices exist. Here are the details of the construction which apply to your problem, which I got from Theory of Error Correcting Codes by MacWilliams and Sloane. First, some notation.

*

*Let $H_m$ be an $m\times m$ Hadamard matrix, with entries in $\{\pm 1\}$, normalized so the first row and column are all $+1$.


*Let $H_m'$ be the $m\times (m-1)$ matrix given by removing the first column of $H_m$.


*Let $H_m''$ be the $(m/2)\times (m-2)$ matrix given by deleting all rows from $H_m'$ whose first entry is $-1$, then deleting the first column of what is left.
Now, onto the construction.

*

*When $n=4k+3$, you can let $S$ be the set of rows of $H_{n+1}'$.


*When $n=4k+2$, let $S$ be the set of rows of $H_{n+2}''$.


*When $n=4k+1$, let $S$ be the set of rows of $H_{n+3}''$, with one column deleted.
The $n=4k$ case is the trickiest. We will construct a matrix in each sub-case, then $S$ is the set of rows of that matrix.

*

*If $n\equiv 0\pmod {12}$, let $a=n/3$, and let $b=2n/3+4$. Take the first $a$ rows of $H_b''$, concatenate them horizontally with $H_a'$, and delete any column.


*If $n\equiv 4 \pmod {12}$, let $a=(n+8)/3$, and let $b=2(n+2)/3$. Take the first $b/2$ rows of $H_a'$, concatenate them horizontally with $H_b''$, and delete any column.


*If $n\equiv 8 \pmod{12}$, let $m=(n+4)/3$. Take three copies of $H_m'$, concatenate them horizontally, and delete any column.

V. I. Levenshtein, The application of Hadamard matrices to a
problem in coding, Problems of Cybernetics, vol. 5, pp. 166-184,
1964
MacWilliams, F. Jessie and N. J. A. Sloane. “The Theory of Error-Correcting Codes.” (1977).

A: A direct and simple answer for the upper bound
The answer by Mike Earnest has addressed the existence of codes and the exact number of possible codewords. It is interesting that a very simple and direct answer on the upper bound can be obtained from the Welch Bound in a few lines and yields a very accurate answer, which is exact when $n=4k+3,$ i.e., one out of every 4 values of $n.$
Given the Gram matrix formed by the inner products of $M$ (your  $|S|$) vectors of length $n,$ and entries in $\pm 1,$
$$
G=[\langle x_i,x_j\rangle]_{M\times M}
$$
the Welch bound can be written as
$$
\sum_{1\leq i,j\leq M} |\langle x_i,x_j\rangle|^2 \geq \frac{\mathbb{tr}(G)^2}{n}
$$
which becomes
$$
\sum_{i} \langle x_i,x_j \rangle^2+
\sum_{i\neq j} |\langle x_i, x_j \rangle|^2 \geq 
\frac{(\sum_{i} \langle x_i, x_i \rangle)^2}{n}
$$
or
$$
Mn^2+\sum_{i\neq j} |\langle x_i, x_j \rangle|^2 \geq 
\frac{M^2n^2}{n}.
$$
For your problem, the smallest negative inner product would take on the value $-1$ which then gives
$$
\sum_{i\neq j} |-1|^2 = M(M-1) \geq M^2 n-Mn^2
$$
and division by $M$ now yields
$$
M - 1 \geq Mn -n^2 \Longrightarrow n^2 - 1 \geq M(n-1)\Longrightarrow \frac{n^2-1}{n-1} \geq M,
$$
or $M\leq n+1.$
In addition this bound can be used for arbitrary vectors as well in great generality, e.g., codes over any finite alphabet, say $\mathbb{Z}_4,$ which can be expressed as real or complex vectors. For example your alphabet may even be something like $\{\pm 3, \pm 1\}$ which Plotkin cannot address. Information theorists who are interested in the rate (logarithm of the number of codewords) of codes and bounds on code performance as $n,M$ go to infinity, use this bound regularly.
This is why I wrote this up as an independent answer.
