# Gilbert-Varshamov with weight condition

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.

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