13
$\begingroup$

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean inner-product $\langle x-z,y-z\rangle\neq0$. I want to evaluate the maximum cardinality of $\mathcal{C}$. If $\mathcal{C}$ fulfills the above condition, I can prove $|\mathcal{C}|\leq c2^{n/2}$, up to some constant $1<c<2$.

I am wondering whether one can construct such $\mathcal{C}$ with $|\mathcal{C}|\geq 2^{n/2}$ for arbitrary $n$.

For $n=2,3$, the optimal $\mathcal{C}$ has strong geometry structures. But I am not familiar with the stuff in hypercube. Do you have any suggestions?

This problem originally came from coding theory. The condition $\langle x-z,y-z\rangle\neq0$ (Euclidean) implies the Hamming distance $d(x,y)<d(x,z)+d(y,z)$, in other words, the vectors $x,y,z$ are not on a line in Hamming space.

The binary inner product case is also interesting. In this case, one can prove $|\mathcal{C}|\leq2^{\frac{n-1}{2}}$ by linear algebra method.

$\endgroup$
  • 2
    $\begingroup$ link.springer.com/article/10.1007%2FBF02579389 might help (maybe you already used their result). $\endgroup$ – Hao Chen Nov 12 '14 at 12:33
  • 2
    $\begingroup$ Is this binary or Euclidean inner product? Meaning, is it $\ne0$ or $\ne0\bmod 2$? $\endgroup$ – Alex Degtyarev Nov 12 '14 at 12:35
  • $\begingroup$ @HaoChen Thank you. I haven't read the paper yet. $\endgroup$ – SGC Nov 12 '14 at 13:57
  • $\begingroup$ @AlexDegtyarev It is Euclidean inner-product. $\endgroup$ – SGC Nov 12 '14 at 14:00
  • 1
    $\begingroup$ Would you please share your proof of upper bound $c2^{n/2}$, if it is not secret? $\endgroup$ – Fedor Petrov Sep 25 '15 at 8:59
1
$\begingroup$

The condition implies that $\mathcal{C}$ is 2-Sperner : that is, there are no subsets $A,B,C \in \mathcal{C}$ with $A \subseteq B \subseteq C$. For otherwise, $C - B$ is supported on the complement of $B$ and $A - B$ is supported on B, so they are orthogonal.

By a result of Erdős, $|\mathcal{C}|$ is at most the sum of the two largest binomial coefficients of order $n$ i.e. typically much smaller than $2^{n/2}$.

However, there are only one or two 2-Sperner families of this size, and neither of them has the the orthogonal property you want, so while this answers the question of whether there is a family of size $2^{n/2}$, it does not find the largest family.

$\endgroup$
  • 2
    $\begingroup$ The growth of the largest binomial coefficient(s) $n \choose m$ is $\sim 2^n / \sqrt{n}$. How do you get "much smaller than $2^{n/2}$"? $\endgroup$ – Noam D. Elkies Aug 26 '15 at 4:35
  • $\begingroup$ Noam D. Elkies' comment is correct. Also, the statement $A-B$ is supported on $B$ in the answer is incorrect. $\endgroup$ – kodlu Aug 26 '15 at 5:25
  • $\begingroup$ @NoamD.Elkies, I read the problem too hastily. I kept interpreting $2^{n/2}$ as $2^{n - 1}$. With that in mind, my answer is clearly unhelpful. $\endgroup$ – Josh Brown Kramer Aug 26 '15 at 16:47
  • $\begingroup$ @kodlu, the support of $A - B$ is $B \setminus A$, which is a subset of $B$. Maybe it's not right to say it supported on $B$, but at any rate, the fact that $\mathcal{C}$ is 2-Sperner still holds. $\endgroup$ – Josh Brown Kramer Aug 26 '15 at 16:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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