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

• do we consider $x\neq y$ because $x\cdot x$ always positive. And so in this case there are solutions for $n=1$ which seems excluded by $n/2$ ?
– zwim
Aug 8, 2022 at 12:10
• Mapping $0\to +1$, $1\to -1$, you are looking for a code of length $n$ and minimum distance $d>n/2$. Your bound is very similar to the so called Plotkin bound. In the annoying case of even $n=2m$ and $d=m+1$ the denominator in the Plotkn bound is $2$ or $3$ depending on parity of $d$. Aug 8, 2022 at 16:06
• @JyrkiLahtonen Do you know, is the Plotkin bound attainable in the case $d=\lfloor n/2\rfloor+1$? Looking at table of small optimal codes, it seems it always is. If so, OP's question could be completely answered. Aug 8, 2022 at 16:57
• @MikeEarnest I consulted colleagues, and Iiro Honkala promptly recalled a construction due to Levenshtein stating that the Plotkin bound is tight assuming that certain Hadamard matrices exist. The smallest case when the existence of a Hadamard matrix is still in doubt is rather high, which explains that the tables you found are on the bound. Aug 8, 2022 at 19:32
• The construction is explained in Chapter 2, Theorem 8 in MacWilliams & Sloane. It's only half a page, but I don't have the time to delve into it right now. Aug 8, 2022 at 19:34

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

• In "If $n\equiv 4\mod 12$,...", one cannot take $b$ rows of $H_a'$ since $b>a$. Aug 9, 2022 at 7:10
• @TamshinDion Thank you for checking in such detail, should be fixed now. Aug 9, 2022 at 14:36

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

• Ill check my proof later. Thanks. Aug 8, 2022 at 13:08

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.