On Metric Dimension of Nonbinary Hamming Spaces

Resumo

For q-ary Hamming spaces we address the problem of the minimum number of points such that any point of the space is uniquely determined by its (Hamming) distances to them. It is conjectured that for a fixed q and growing dimension n of the Hamming space this number asymptotically behaves as 2n/ log_qn. We prove this conjecture for q = 3 and q = 4; for q = 2 its validity has been known for half a century.