5
$\begingroup$

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

$\endgroup$

2 Answers 2

4
$\begingroup$

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)

$\endgroup$
5
  • $\begingroup$ There's one more small twist in the original question: The upper bound is on the inner products, not on their absolute values. I'm not sure if this intended, but this probably would not make much difference i.e. you cannot fit many more vectors this way, even if you allow some pairs to have large negative inner products. $\endgroup$ Jan 28, 2021 at 8:05
  • $\begingroup$ (Depending, of course, on what is "many" more. If you allow large negative inner products, you can double the number of vectors by including every vector's opposite.) $\endgroup$ Jan 28, 2021 at 9:15
  • $\begingroup$ absolutely right, I was going to write that but forgot. $\endgroup$
    – kodlu
    Jan 28, 2021 at 9:38
  • 1
    $\begingroup$ Thanks very much for this answer. Am I correct that there's a typo in the algebra? It looks to me like the second displayed equation should start $kn^2$ rather than $kn$? If so then working through the algebra gives me an upper bound of more like $k\le n+c'\log^2 n$. This makes a bit more sense to me since I would expect the answer to be larger than $n$. $\endgroup$
    – DPL
    Jan 28, 2021 at 11:28
  • $\begingroup$ One other thing: my bound is on the inner products rather than their absolute value. Is there an easy way to see that you can't do much better than doubling the number of vectors in this case? @JukkaKohonen says that you cannot fit many more vectors this way, and I get that intuitively but I don't see how to prove it... $\endgroup$
    – DPL
    Jan 28, 2021 at 11:31
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ We have that $\langle v_i, v_j \rangle = n-2d(u_i,u_j)$ (where $d$ here is the Hamming distance). So if $\langle v_i, v_j \rangle \le \log n$ then $d(u_i,u_j) \ge n/2 - \log_2(n)/2$ which is a lower bound on the minimum distance. $\endgroup$
    – DPL
    Jan 29, 2021 at 10:05
  • $\begingroup$ interesting, and this result also has the absolute value constraint. so if I understand correctly this bound of $O(n \log \log n)$ being an upper bound is weaker than the one in my answer? $\endgroup$
    – kodlu
    Jan 30, 2021 at 0:32
  • 1
    $\begingroup$ Sorry, that was a bad typo. The $O(n\log\log n)$ one is without the absolute values, hence why it gives a weaker upper bound. $\endgroup$
    – DPL
    Jan 31, 2021 at 1:07
  • $\begingroup$ thanks for the clarification. $\endgroup$
    – kodlu
    Jan 31, 2021 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.