1
$\begingroup$

For $N$ integer, it is known (Gilbert-Varshamov) that there exists a subset $S$ of $\{0,1\}^N$ such that $|S|$ is still exponential in $N$ and such that two elements $x, x'$ in $S$ are at least distant $\Omega(N)$ with respect to the Hamming metric.

Does the following result also hold:

Let $N \in \mathbb{N}$ and consider $\{0,1\}^N$ as well as a vector $\mathbf{w} \in \mathbb{R}_+^N$. Define the weighted Hamming metric such that for $\mathbf{x},\mathbf{x}' \in \{0,1\}^N$ we have $d_{\mathbf{w}}(\mathbf{x},\mathbf{x}') = \sum_{i=1}^N \mathbf{w}(i) |\mathbf{x}(i) - \mathbf{x'}(i)|$. Does there exist a subset $S$ of $\{0,1\}^N$ such that

  • $|S| \geq 2^{C_1 \cdot N}$
  • $d_{\mathbf{w}}(\mathbf{x},\mathbf{x}') \geq C_2 \|\mathbf{w}\|_1 N$

where $C_1, C_2$ are universal constants. That is, the selected elements will have disagreeing coordinates preferably where the cost is the highest, such that always a constant proportion of the total weight is captured.

$\endgroup$
  • 2
    $\begingroup$ No: What if $\mathbf w$ has all or almost all of its weight on a single coordinate? $\endgroup$ – Anthony Quas Mar 7 at 13:43
  • $\begingroup$ That's right I have to penalize for this sort of cases. $\endgroup$ – geo.wolfer Mar 7 at 13:58

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.