<figure><img src="image_1.png" /></figure>

HAL
open science

# Rank of Subsets in Finite Metric Spaces with Hamming Distance

Jamolidin Abdurakhmanov

► To cite this version:

Jamolidin Abdurakhmanov. Rank of Subsets in Finite Metric Spaces with Hamming Distance. 2025. hal-05103756

HAL Id: hal-05103756

https://hal.science/hal-05103756v1

Preprint submitted on 9 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Rank of Subsets in Finite Metric Spaces with Hamming Distance

Jamolidin K. Abdurakhmanov

Department of Information Technologies

Andijan State University

Andijan, Uzbekistan

jamolidinkamol@gmail.com, abduraxmanov@adu.uz

ORCID: 0009-0008-0067-0553

## Abstract

We introduce a novel concept of rank for subsets of finite metric spaces $E_q^n$ (the set of all $n$-dimensional vectors over an alphabet of size $q$) equipped with the Hamming distance, where the rank $R(A)$ of a subset $A$ is defined as the number of non-constant columns in the matrix formed by the vectors of $A$. This purely combinatorial definition provides a new perspective on the structure of finite metric spaces, distinct from traditional linear-algebraic notions of rank.

We establish tight bounds for $R(A)$ in terms of $D_A$, the sum of Hamming distances between all pairs of elements in $A$. Specifically, we prove that $\frac{2qD_A}{(q-1)|A|^2} \le R(A) \le \frac{D_A}{|A|-1}$ when $|A|/q \ge 1$, with a modified lower bound for the case $|A|/q < 1$. These bounds show that the rank is constrained by the metric properties of the subset.

Furthermore, we introduce the concept of metrically dense subsets, which are subsets that minimize rank among all isometric images. This notion captures an extremal property of subsets that represent their distance structure in the most compact way possible. We prove that subsets with uniform column distribution are metrically dense, and as a special case, establish that when $q$ is a prime power, every linear subspace of $E_q^n$ is metrically dense. This reveals a fundamental connection between the algebraic and metric structures of these spaces.

Our results have potential applications in coding theory, where metrically dense subsets could lead to more efficient error-correcting codes, and in combinatorial optimization, where the rank bounds provide new constraints for discrete optimization problems.

## 1 Introduction

The study of finite metric spaces equipped with the Hamming distance has been central to coding theory and combinatorics since the seminal work of Hamming [1]. The space $E_q^n$, consisting of all $n$-dimensional vectors over an alphabet of size $q$, forms the natural ambient space for error-correcting codes and has been extensively studied from various perspectives [2, 3].

In this paper, we introduce a new notion of rank for subsets of $E_q^n$ that differs fundamentally from existing concepts in the literature. While traditional approaches focus on linear-algebraic rank or rank-metric codes [4], our definition is purely combinatorial: the rank $R(A)$ of a subset $A \subseteq E_q^n$ is the number of columns that vary across the vectors in $A$.

This seemingly simple definition leads to surprisingly rich mathematics. We establish optimal bounds for $R(A)$ in terms of the sum of pairwise Hamming distances within $A$, and introduce the concept of *metrically dense* subsets—those that achieve minimal rank among all isometric images. Our main theoretical contribution shows that when $q$ is a prime power, every linear subspace is metrically dense, revealing an unexpected connection between algebraic and metric properties.
## 1.1 Main Contributions

Our work makes four primary contributions:

1. We introduce the rank $R(A)$ for subsets $A \subseteq E_q^n$, defined as the number of non-constant columns when the elements of $A$ are arranged as rows of a matrix.

2. We prove tight bounds for $R(A)$ based on the sum of Hamming distances $D_A = \sum_{x,y \in A, x \neq y} d_H(x, y)$:

* If $|A|/q \ge 1$: $\frac{2qD_A}{(q-1)|A|^2} \le R(A) \le \frac{D_A}{|A|-1}$

* If $|A|/q < 1$ and $q > 2$: $\frac{2(q-2)D_A}{(|A|^2-2)(q-2)-(|A|-2)^2} \le R(A) \le \frac{D_A}{|A|-1}$

3. We introduce metrically dense subsets as those satisfying $R(A) \le R(B)$ for all $B$ isometric to $A$.

4. We prove that when $q$ is a prime power, every linear subspace of $E_q^n$ is metrically dense, and more generally, any subset with uniform distribution in each varying column is metrically dense.

## 1.2 Related Work

The notion of rank in coding theory typically refers to the rank of matrices over finite fields, as studied extensively in rank-metric codes [5, 4]. The Hamming distance has been fundamental since [1], with classical bounds including the Plotkin bound [6] and sphere-packing bounds [2].

Recent work on extremal problems in Hamming spaces [7, 8] has focused on the maximum size of subsets with prescribed distance sets. Our approach differs by considering the metric properties of subsets through their rank, providing a new lens for understanding finite metric spaces.

The connection between linear codes and metric properties has been explored through weight enumerators and MacWilliams identities [9]. Our result that linear subspaces are metrically dense adds a new dimension to this relationship.

## 1.3 Paper Organization

Section 2 establishes notation and presents our key definitions. Section 3 develops the bounds for $R(A)$ through careful analysis of column contributions. Section 4 introduces metrically dense subsets and proves our main theorem about linear subspaces. Section 5 discusses open problems and potential applications.

# 2 Preliminaries and Definitions

For natural numbers $n, q \ge 2$, we define:

$$E_q = \{0, 1, 2, \dots, q-1\}, \quad E_q^n = \{(x_1, x_2, \dots, x_n) \mid x_i \in E_q, i = 1, 2, \dots, n\}.$$

The set $E_q^n$ forms a metric space under the Hamming distance $d_H$, where for $x = (x_1, \dots, x_n)$ and $y = (y_1, \dots, y_n)$ in $E_q^n$:

$$d_H(x, y) = |\{i : x_i \neq y_i\}|.$$

When $q$ is a prime power, $E_q$ can be identified with a finite field, making $E_q^n$ an $n$-dimensional vector space over $E_q$.
## 2.1 Faces and Rank

A $k$-dimensional face of $E_q^n$ is the set of all vectors where exactly $k$ coordinates vary freely while the remaining $n-k$ coordinates are fixed. The number of $k$-dimensional faces is $\binom{n}{k}q^{n-k}$.

**Definition 2.1 (Rank of a Subset).** For any subset $A \subseteq E_q^n$, the rank of $A$, denoted $R(A)$, is the dimension of the smallest face containing $A$.

Equivalently, $R(A)$ can be computed by forming the matrix $M_A$ whose rows are the vectors in $A$:

$$M_A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix},$$

where $m = |A|$ and each row is a vector in $A$. A column is *constant* if all its entries are equal. Then $R(A)$ equals the number of non-constant columns in $M_A$.

**Remark 2.2.** When $E_q^n$ is a linear space, the rank $R(L)$ of a linear subspace $L$ differs from its dimension $\dim L$. For example, if $L$ is a $k$-dimensional subspace contained in a hyperplane $\{x : x_i = 0\}$, then $\dim L = k$ but $R(L) \le n - 1$.

## 2.2 Isometry and Distance Sum

Two subsets $A, B \subseteq E_q^n$ are *isometric* if there exists a bijection $\phi : A \to B$ preserving Hamming distance: $d_H(\phi(x), \phi(y)) = d_H(x, y)$ for all $x, y \in A$.

**Example 2.3.** Let $n = 4, q = 2$, and consider:

$$A = \{(0, 0, 0, 0), (0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 0)\}, \quad (1)$$

$$B = \{(0, 0, 0, 0), (0, 0, 1, 1), (0, 1, 0, 1), (1, 0, 0, 1)\}. \quad (2)$$

Both sets have pairwise distances all equal to 2, making them isometric. However, $R(A) = 3$ while $R(B) = 4$, showing that rank is not preserved under isometry.

For any subset $A \subseteq E_q^n$ with $|A| = m \ge 2$, we define:

$$D_A = \sum_{\substack{x,y \in A \\ x \neq y}} d_H(x, y),$$

the sum of all pairwise Hamming distances in $A$.

# 3 Bounds for Rank

Our main technical result establishes tight bounds for $R(A)$ in terms of $D_A$ and $|A|$.

**Theorem 3.1 (Main Bounds).** For any subset $A \subseteq E_q^n$ with $m = |A| \ge 2$:

1. If $m/q \ge 1$ and $q \ge 2$:

$$\frac{2qD_A}{(q-1)m^2} \le R(A) \le \frac{D_A}{m-1}.$$

2. If $m/q < 1$ and $q > 2$:

$$\frac{2(q-2)D_A}{(m^2-2)(q-2)-(m-2)^2} \le R(A) \le \frac{D_A}{m-1}.$$
Proof. Let $r = R(A)$ be the number of non-constant columns in $M_A$, labeled $\bar{u}_1, \dots, \bar{u}_r$. Each column $\bar{u}_i$ contributes some amount $d_i$ to $D_A$, with:

$$D_A = \sum_{i=1}^{r} d_i.$$

For column $\bar{u}_i$, let $y_j$ denote the number of occurrences of symbol $j \in E_q$. Then:

$$\sum_{j=0}^{q-1} y_j = m.$$

The contribution of column $\bar{u}_i$ to $D_A$ is:

$$d_i = \sum_{0 \le k < j \le q-1} y_k y_j = \frac{1}{2} \left( m^2 - \sum_{j=0}^{q-1} y_j^2 \right).$$

Since $\bar{u}_i$ is non-constant, at least two $y_j$ values are positive. Without loss of generality, assume $y_0 \ge 1$ and $y_1 \ge 1$.

**Upper bound:** To minimize $d_i$, we maximize $\sum_{j=0}^{q-1} y_j^2$. Subject to $y_0 \ge 1, y_1 \ge 1$, this is maximized when $y_0 = m-1, y_1 = 1$, and $y_j = 0$ for $j \ge 2$. Thus:

$$d_i \ge \frac{1}{2}(m^2 - ((m-1)^2 + 1)) = m-1.$$

Therefore $D_A \ge r(m-1)$, giving $R(A) \le D_A/(m-1)$.

**Lower bound:** To maximize $d_i$, we minimize $\sum_{j=0}^{q-1} y_j^2$.

If $m \ge q$: The minimum occurs when $y_j = m/q$ for all $j$, giving:

$$d_i \le \frac{1}{2} \left( m^2 - q \cdot \frac{m^2}{q^2} \right) = \frac{(q-1)m^2}{2q}.$$

If $m < q$: Using Lagrange multipliers, the minimum occurs when $y_0 = y_1 = 1$ and $y_j = (m-2)/(q-2)$ for $j \ge 2$, giving:

$$d_i \le \frac{(m^2 - 2)(q - 2) - (m - 2)^2}{2(q - 2)}.$$

The lower bounds follow from $D_A \le r \cdot \max(d_i)$. $\square$

The bounds in Theorem 3.1 are tight:

**Example 3.2 (Tightness of bounds).** 1. For $A = \{(0,0,0,0), (0,1,1,1)\} \subseteq E_2^4$: We have $|A| = 2, R(A) = 3, D_A = 3$. Both bounds give $R(A) = 3$.

2. For $A = \{(0,0,0), (0,2,2)\} \subseteq E_3^3$: We have $|A| = 2, R(A) = 2, D_A = 2$. Both bounds give $R(A) = 2$.

# 4 Metrically Dense Subsets

**Definition 4.1 (Metrically Dense).** A subset $A \subseteq E_q^n$ is metrically dense if $R(A) \le R(B)$ for every subset $B \subseteq E_q^n$ isometric to $A$.

In other words, metrically dense subsets achieve minimal rank among all their isometric images. This concept captures an extremal property: such subsets represent their distance structure in the most compact way possible.
**Definition 4.2** (Uniform Column Distribution). A subset $A \subseteq E_q^n$ has uniform column distribution if, for each non-constant column of the matrix $M_A$, each value $b \in E_q$ appears exactly $|A|/q$ times (assuming $q$ divides $|A|$).

**Theorem 4.3** (Uniform Distribution Implies Dense). If $A \subseteq E_q^n$ has uniform column distribution and $q$ divides $|A|$, then $A$ is metrically dense.

*Proof.* Let $m = |A|$ with $q | m$. For each non-constant column in $M_A$, each value $b \in E_q$ appears exactly $m/q$ times. The contribution of such a column to $D_A$ is:

$$ \binom{q}{2} \cdot \left(\frac{m}{q}\right)^2 = \frac{(q-1)q}{2} \cdot \frac{m^2}{q^2} = \frac{(q-1)m^2}{2q}. $$

Since there are $R(A)$ such columns:

$$ D_A = R(A) \cdot \frac{(q-1)m^2}{2q}. $$

This gives:

$$ R(A) = \frac{2qD_A}{(q-1)m^2}, $$

which equals the lower bound in Theorem 3.1. Since no isometric image can have smaller rank, $A$ is metrically dense. $\square$

As a corollary, we obtain our previous result about linear subspaces:

**Theorem 4.4** (Linear Subspaces are Dense). When $q$ is a prime power, every linear subspace $L \subseteq E_q^n$ with $|L| > 1$ is metrically dense.

*Proof.* Let $L$ be a $k$-dimensional linear subspace, so $|L| = q^k$. Consider any column $j$ of $M_L$ containing at least one nonzero entry. For each $b \in E_q$, define:

$$ L_b = \{x \in L : x_j = b\}. $$

Since $L$ is a subspace, $L_0 = \{x \in L : x_j = 0\}$ is also a subspace of dimension $k-1$. For any $b \neq 0$, there exists $z \in L$ with $z_j \neq 0$. The map $y \mapsto y + (b/z_j)z$ establishes a bijection between $L_0$ and $L_b$. Therefore, each value $b \in E_q$ appears exactly $q^{k-1} = |L|/q$ times in column $j$.

Thus $L$ has uniform column distribution, and by Theorem 4.3, $L$ is metrically dense. $\square$

**Remark 4.5.** Theorem 4.3 shows that the property of being metrically dense is not exclusive to linear subspaces. Any subset with uniform column distribution achieves the lower bound in Theorem 3.1 and is therefore metrically dense. This includes many non-linear structures, such as certain combinatorial designs and regular graphs embedded in $E_q^n$.

**Question 4.6.** Does every metrically dense subset have uniform column distribution? Equivalently, if $A$ is metrically dense with $q | |A|$, must each value appear exactly $|A|/q$ times in each non-constant column of $M_A$?

# 5 Conclusions and Open Problems

We have introduced a new notion of rank for subsets of finite metric spaces with Hamming distance, established optimal bounds relating rank to distance structure, and proved that subsets with uniform column distribution achieve minimal rank among isometric images.

Several questions remain open:
1. **Characterization:** Can we characterize all metrically dense subsets of $E_q^n$? Are they precisely those with uniform column distribution?

2. **Non-divisibility case:** When $q$ does not divide $|A|$, which subsets are metrically dense? Can we extend the notion of uniform distribution to this case?

3. **Computational complexity:** Given a subset $A \subseteq E_q^n$, what is the complexity of determining whether $A$ is metrically dense?

4. **Applications:** Can metrically dense subsets be used to construct optimal codes or combinatorial designs?

5. **Generalizations:** Can these results be extended to other finite metric spaces or distance measures?

Our results suggest that the rank function $R(\cdot)$ captures fundamental metric properties of finite spaces, with potential applications in coding theory, distributed storage, and combinatorial optimization. The characterization of metrically dense subsets through uniform column distribution provides a new perspective on the interplay between combinatorial and metric structures in finite spaces.

## References

[1] R. W. Hamming. Error detecting and error correcting codes. *The Bell System Technical Journal*, 29(2):147-160, 1950.

[2] F. J. MacWilliams and N. J. A. Sloane. *The Theory of Error-Correcting Codes*. Elsevier, 1977.

[3] J. H. Van Lint. *Introduction to Coding Theory*. Springer, 1999.

[4] E. M. Gabidulin. Theory of codes with maximum rank distance. *Problemy peredachi informatsii*, 21(1):3-16, 1985.

[5] P. Delsarte. Bilinear forms over a finite field, with applications to coding theory. *Journal of Combinatorial Theory, Series A*, 25(3):226-241, 1978.

[6] M. Plotkin. Binary codes with specified minimum distance. *IRE Transactions on Information Theory*, 6(4):445-450, 1960.

[7] R. Ahlswede and L. H. Khachatrian. *Contributions to the Theory of Extremal Problems in Hamming Spaces*. Springer, 1997.

[8] P. Frankl and V. Rödl. Extremal problems concerning the Hamming distance. *Journal of Combinatorial Theory, Series A*, 72(2):226-243, 1995.

[9] F. J. MacWilliams. A theorem on the distribution of weights in a systematic code. *The Bell System Technical Journal*, 42(1):79-84, 1962.