Maximum number of vectors with upper bound on pairwise inner products 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.$
 A: 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)
A: Whilst kodlu gave a highly informative response to my question, I don't think it quite provided a direct answer, but following the references that were provided did, so I have accepted the answer.
The problem is that my bound is on the inner products $\langle v_i, v_j \rangle$ rather than their absolute values. While it does not seem like this should make a big difference (as Jukka said, this "probably would not make much difference"), it's not clear to me how to prove it. In fact, it does seem to make a bit of a difference to the best known bounds.
Kodlu proved that with the condition $|\langle v_i, v_j\rangle|\le \log n$ then we have the bound $$k\le n+c'\log^2 n.$$
But as far as I can tell, the best known bound with the condition $\langle v_i, v_j\rangle\le \log n$ is given by results of Krasikov and Litsyn on the maximum size of binary codes with a given minimum distance. Theorem 1 of their paper implies that $$k\le (1+o(1))n\log\log n$$ unless I'm misunderstanding. Kraskiov and Litsyn improve similar bounds due to Tietavainen and McEliece.
I'd be happy to know if I'm missing something obvious since I'd rather an upper bound of $O(n)$.
References:
I. Krasikov and S. Litsyn,  Linear  Programming  Bounds  for  Codes  of  Small  Size, Europ .  J .  Combinatorics  (1997)  18 ,  647 – 656
A.    Tietavainen ,    Bounds  for  binary  codes  just  outside  the  Plotkin  range ,   Inform .   Control ,  47  (1980) , 85 – 93
R .   J .    McEliece  and  H .   Rumsey ,   Jr .,    Sphere-packing  in  the  Hamming  metric ,   J .  Combin .  Theory ,  Ser .  A , (1973) ,   32 – 34
