I have a collection $\{v\_1,...,v\_k\}$ of vectors in $\{\pm 1\}^n$ with the property that for all $i\neq j$ we have $\langle v\_i, v\_j \rangle \le c\log\_2(n)$. I am looking for an upper bound on $k$ in terms of $n$.


I am aware that given instead unit vectors $v\_i$ in $\mathbb{R}^n$, and the bound $\langle v\_i, v\_j\rangle \le c$ (for some $c$ independent of $n$), then $k$ can be exponentially large. So I expect the upper bound in my case to be polynomial, but I'd like the best bound I can get!


I'm finding it hard to get a reference for this although it must be well known. I have found upper bounds for the related problem where we instead have $|\langle v\_i, v\_j \rangle | \le \epsilon(n)$ (the 'almost orthogonal' case), but I haven't had any luck with this variant. Apologies if I'm missing an obvious reference.


**Edit:**


Kodlu helped me realise the connection with coding theory: letting $v\_i=2u\_i-1$ then we have a collection of binary vectors $u\_i$, and since $\langle v\_i,v\_j\rangle = n-2d(u\_i,u\_j)$ (where $d$ is the Hamming distance), the upper bound
$$\langle v\_i, v\_j \rangle \le c\log n$$
implies that
$$ d(u\_i,u\_j) \ge n/2 - c\log(n)/2.$$
So my question is equivalent to asking for upper bounds on the size of a binary code of length $n$ with minimum distance $n/2 - c\log(n)/2.$



Maximum number of vectors with upper bound on pairwise inner products
This is an interesting twist on the usual question.


Relevant results are due to Welch, Kabatianski, Levenshtein, Sidelnikov. Welch's applies to arbitrary vectors, real or complex. The others apply to vectors constructed from complex roots of unity of some finite order.
Welch's bound states (I will apply it to $\pm 1$ valued vectors).


Let $e\geq 1$ be an integer and let $a\_1,\ldots,a\_k$ be distinct vectors in $\mathbb{C}^n.$ Then the following inequalities hold (assuming $k\geq n$):
$$
\sum\_{i=1}^k \sum\_{j=1}^k \left| \langle a\_i, a\_j \rangle \right|^{2e} \geq \frac{\left(\sum\_{i=1}^k \lVert a\_i \rVert^{2e}\right)^2}{\binom{n+e-1}{e}},
$$


In this case $e=1,$ gives the nontrivial bound. Substituting $\langle a\_i,a\_j \rangle=c \log n$ for distinct pairs yields


$$
k n^2 + \binom{k}{2} (c \log n)^2 \geq \frac{k^2 n^2}{n} = k^2n
$$
or
$$
k n^2 + c'(k^2-k)(\log n)^2 \geq k^2n
$$


eventually giving the inequality $k\leq n+c' \log^2 n.$


**Edit:** As in the apt comment by @JukkaKohonen, one can double the number of vectors if the original bound is not on the absolute value. Thanks for all the other comments as well and sorry for the typos.


**References:**


V.M. Sidelnikov, On mutual correlation of sequences, Soviet Math Dokl. 12:197-201, 1971.


V.M. Sidelnikov, Cross correlation of sequences, Problemy Kybernitiki, 24:15-42, 1971 (in Russian)


Welch, L.R. Lower Bounds on the Maximum Cross Correlation of Signals. IEEE Transactions on Information Theory. 20 (3): 397–399, 1974.


Kabatianskii, G. A.; Levenshtein, V. I. Bounds for packings on the sphere and in space. (Russian) Problemy Peredači Informacii 14 (1978), no. 1, 3–25. (A version of this might be available in English translation, in Problems of Information Transmission)


