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

1 Answer 1

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$
4
  • 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$ Aug 26, 2015 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, 2015 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$ Aug 26, 2015 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$ Aug 26, 2015 at 16:48

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.