Maximum number of $\pm 1$ valued vectors with pairwise negative inner product

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.