Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances

Abstract

We consider vectors from $\{0,1{\}}^n$. The weight of such a vector $v$ is the sum of the coordinates of $v$. The distance ratio of a set $L$ of vectors is $\mathrm{dr}(L):=\max \{\ddot{I}(x,y):x,y\in L\}/\min \{\ddot{I}(x,y):x,y\in L,x\ne y\},$ where $\ddot{I}(x,y)$ is the Hamming distance between $x$ and $y$. We prove that (a) for every constant $\hat{I}»>1$ there are no positive constants $\hat{I}\pm$ and $C$ such that every set $K$ of at least $\hat{I}{»}^p$ vectors with weight $p$ contains a subset $K^{\prime }$ with $|K^{\prime }|\ge |K{|}^{\hat{I}}\pm$ and $\mathrm{dr}(K^{\prime })\le C$, % even when $|K|\ge \hat{I}»$, (b) For a set $K$ of vectors with weight $p$, and a constant $C>2$, there exists $K^{\prime }\subseteq K$ such that $\mathrm{dr}(K^{\prime })\le C$ and $|K^{\prime }|\ge |K{|}^{\hat{I}}\pm$, where $\hat{I}\pm =1/\lceil \log (p/2)/\log (C/2)\rceil$.