The exact asymptotic constant in the metric dimension of Jaccard space

Abstract

Let $X$ be a finite set with $|X|=n$ and let $\mathrm{Jac}(a,b)=|a△b|/|a\cup b|$ be the Jaccard distance on the power set $2^X$. Lladser and Paradise recently proved that the metric dimension of $(2^X,\mathrm{Jac})$ is $\Theta (n/\ln n)$, with the constant left open; their bounds are $(\ln 2)n/\ln n\lesssim \beta (2^X,\mathrm{Jac})\lesssim 2\ln (2e)n/\ln n$. We determine the constant: \[ β(2^X,\mathrm{Jac})=\frac{2n}{\log_2 n}\,(1+o(1))=(2\ln 2)\,\frac{n}{\ln n}\,(1+o(1)). \] The proof identifies the problem, on each ``slice'' of subsets of fixed cardinality, with the Erdős--Rényi coin-weighing problem for a spring scale (the problem of \emph{detecting matrices}). The lower bound is the Erdős--Rényi entropy argument applied to the middle slice; the upper bound follows from the explicit detecting families of Lindström and of Cantor and Mills, augmented by a single extra landmark that reveals cardinality.