# The Combinatorial Rank of Subsets: Metric Density in Finite Hamming Spaces

Source: [The Combinatorial Rank of Subsets: Metric Density in Finite Hamming Spaces](<https://www.sota2.com/research/paper/68fa5da71e209131ce9dbec2>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T18:22:10.439Z

Authors: Jamolidin K. Abdurakhmanov

Published: 2025-06-16T03:58:20.000Z

## Abstract

We introduce a novel concept of rank for subsets of finite metric spaces E^n\_q (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 2qD\_A/((q-1)\|A\|^2) \<= R(A) \<= D\_A/(\|A\|-1) when \|A\|/q \>= 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^n\_q is metrically dense. This reveals a fundamental connection between the algebraic and metric structures of these spaces.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2506.13081>)

[PDF](<https://arxiv.org/pdf/2506.13081.pdf>)
