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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ link.springer.com/article/10.1007%2FBF02579389 might help (maybe you already used their result). $\endgroup$
    – Hao Chen
    Commented Nov 12, 2014 at 12:33
  • 2
    $\begingroup$ Is this binary or Euclidean inner product? Meaning, is it $\ne0$ or $\ne0\bmod 2$? $\endgroup$
    – Alex Degtyarev
    Commented Nov 12, 2014 at 12:35
  • $\begingroup$ @HaoChen Thank you. I haven't read the paper yet. $\endgroup$
    – SGC
    Commented Nov 12, 2014 at 13:57
  • $\begingroup$ @AlexDegtyarev It is Euclidean inner-product. $\endgroup$
    – SGC
    Commented 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$
    – Fedor Petrov
    Commented Sep 25, 2015 at 8:59

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Noam D. Elkies
    Commented 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
    Commented 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$
    – Josh Brown Kramer
    Commented 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$
    – Josh Brown Kramer
    Commented Aug 26, 2015 at 16:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .