Introduction
Given query access to a symmetric matrix D ∈ R n × n D \in\mathbb{R}^{n \times n} D ∈ R n × n of nonnegative entries with zero diagonal and a prescribed metric family P = { P n } \mathcal{P} = \{\mathcal{P}_n\} P = { P n } , metric property testing asks us to distinguish whether D ∈ P n D \in\mathcal{P}_n D ∈ P n or D D D is ϵ \epsilon ϵ -far from P n \mathcal{P}_n P n . Here, ϵ \epsilon ϵ -far means that more than ϵ n 2 / 2 \epsilon n^2/2 ϵ n 2 /2 unordered off-diagonal pairs must be changed to obtain a member of P n \mathcal{P}_n P n . The goal is to test the P \mathcal{P} P -property using as few queries to the entries of D D D as possible. Classic examples include testing whether D D D satisfies the triangle inequality, is an ultrametric, or can be realized by shortest-path distances in a tree or a Euclidean space of fixed dimension [31 , 27 , 30 , 9 ] . These questions have found numerous applications in metric recognition, completion, and repair [29 , 32 , 12 , 8 , 7 , 21 , 20 , 19 , 13 , 2 ] .
A one-sided ϵ \epsilon ϵ -tester is a randomized algorithm that accepts every member in P n \mathcal{P}_n P n with probability 1 and rejects every ϵ \epsilon ϵ -far input with probability at least 2/3. We call the family P \mathcal{P} P one-sided testable if, for every ϵ > 0 \epsilon> 0 ϵ > 0 , there is such a tester whose query complexity is bounded by q ( ϵ ) q(\epsilon) q ( ϵ ) independently of n n n .
Parnas and Ron [31 ] initiated the study of metric property testing and proved one-sided testability for several families, including ultrametrics and non-injective tree and Euclidean metrics. Krauthgamer and Sasson [27 ] improved the testing bounds for finite dimensional Euclidean realizability. More recently, Bao, Kannan, and Waingarten [9 ] obtained improved bounds for ultrametric testing, studied tree metric testing, and gave a sublinear-query tester for general metrics. They also proved lower bounds for general metric testing, ruling out nonadaptive one-sided testers whose query complexity is polynomial in 1 / ϵ 1/\epsilon 1/ ϵ and independent of n n n . Together, these results raise a structural question:
What structural properties make a metric family one-sided testable?
In fact, one-sided testability already forces locality: ϵ \epsilon ϵ -far inputs must reveal small certificates of non-membership under random sampling. Indeed, for families invariant under relabelling, an adaptation of the canonicalization argument of Goldreich and Trevisan [25 ] simulates a q ( ϵ ) q(\epsilon) q ( ϵ ) -query tester using the induced matrix on a uniformly sampled set of at most 2 q ( ϵ ) 2q(\epsilon) 2 q ( ϵ ) points. Perfect completeness forces the simulation to accept every sampled configuration that occurs in a valid input. Thus, on an ϵ \epsilon ϵ -far input, the sample must contain, with probability at least 2/3, a configuration incompatible with every valid completion on n n n points. Small, detectable obstructions are therefore a necessary consequence of one-sided testability. This perspective also underlies Alon and Shapira’s characterization of oblivious one-sided graph testing through semi-hereditary properties [5 ] .
It is therefore natural to focus on metric families characterizable by a local predicate : a matrix belongs to the family exactly when every k k k -point restriction satisfies the predicate, where k k k depends only on the family. This structure is shared by many families: general metrics and ultrametrics are determined by 3-point conditions, tree realizability by conditions on at most 4 points, and Euclidean realizability in fixed dimension by conditions on a bounded number of points. For these families, the challenge is to understand when being far from membership makes local violations detectable by sampling.
Our main contribution is a unified structural characterization of one-sided testability. Our approach connects two tasks, repairing an input and detecting its violations, through two complementary properties:
To see how these properties work together, delete the pairs covered by a maximal collection of edge-disjoint local violations. Maximality ensures that the remaining partial matrix is locally consistent. If the collection is small, only a few holes are created, and completion stability yields a valid matrix close to the original input. Thus, an input far from the family must contain many edge-disjoint violations, which packing amplification turns into sufficiently many violations for random sampling to detect. We show that these two properties together characterize one-sided testability. Separating these tasks gives a common proof strategy across metric families, yields simplified proofs of several classical testability results, and identifies distinct mechanisms behind the failure of testability.
Our results
Fix a local predicate Φ \Phi Φ on k k k points characterizing a metric family P \mathcal{P} P . A k k k -point restriction that fails Φ \Phi Φ is called a local violation . We introduce two properties, with all bounds uniform in n ≥ k n \ge k n ≥ k .
Packing amplification. For every α > 0 \alpha> 0 α > 0 , there exists δ > 0 \delta> 0 δ > 0 such that any n n n -point matrix containing at least α n 2 \alpha n^2 α n 2 edge-disjoint local violations contains at least δ ( k ) ( n ) \delta^{(n)}_{(k)} δ ( k ) ( n ) local violations in total. Here, edge-disjointness means that no two violations share an unordered pair of indices.
Completion stability. A partial matrix contains unspecified pairs, called holes , and is locally consistent if every fully specified k k k -point restriction satisfies Φ \Phi Φ . For every η > 0 \eta> 0 η > 0 , there exists θ > 0 \theta> 0 θ > 0 such that any locally consistent partial matrix containing at most θ n 2 \theta n^2 θ n 2 holes can be completed to a member of P n \mathcal{P}_n P n after changing at most η n 2 \eta n^2 η n 2 specified pairs (filling the holes incurs no cost).
Theorem 1.1 (Informal). For metric families characterized by a local predicate, one-sided testability is equivalent to packing amplification together with completion stability.
Formal definitions and the precise theorem statement are given in § 3 .
Unified and simplified analysis for one-sided testability. We then apply this characterization to several metric families (see Table 1 ). Our framework recovers the qualitative one-sided testability results of [31 , 27 , 9 ] for ultrametrics, strict ultrametrics, tree pseudometrics, and Euclidean pseudometrics in fixed dimension, with unified and simpler proofs via the packing amplification and the completion stability properties. For ultrametrics, these properties follow from elementary counting and partitioning arguments. For tree pseudometrics, both properties reduce to their ultrametric counterparts. For Euclidean pseudometrics of fixed dimension, both arguments use the rigidity of distances to a small affine anchor set. Therefore, the same testing argument applies across families, and parts of the proofs can be reused. The same framework identifies distinct reasons for non-testability. General metrics and metrics with bounded aspect ratio (entries in [ 1 , C ] [1,C] [ 1 , C ] for fixed C > 2 C > 2 C > 2 ) fail packing amplification. Strict tree and Euclidean metrics retain packing amplification but fail completion stability. Also, as metrics with bounded aspect ratio satisfy completion stability, these examples establish the independence of the two properties.
Table 1. Packing amplification and completion stability for the metric families studied in this paper. The dimension d ≥ 1 d \ge1 d ≥ 1 is a fixed constant. Strictness requires positive distances between distinct labels. For metrics with bounded aspect ratio, off-diagonal entries lie in [ 1 , C ] [1,C] [ 1 , C ] for a fixed C > 2 C > 2 C > 2 .
Quantitative testing bounds. Beyond giving a qualitative classification, our structural framework also gives new quantitative upper and lower bounds. Because our characterization reduces one-sided testability to two combinatorial properties, bounding completion stability and packing amplification yields explicit query upper bounds. For ultrametrics, strict ultrametrics, and tree pseudometrics, combining linear completion stability with quadratic packing amplification yields one-sided O ( ϵ − 2 ) O(\epsilon^{-2}) O ( ϵ − 2 ) -query testers (Corollary 6.1), removing the logarithmic factors from the O ~ ( ϵ − 2 ) \widetilde{O}(\epsilon^{-2}) O ( ϵ − 2 ) bounds of [9 ] . We also provide novel bounds for general n n n -point metrics and metrics with entries in [ 1 , C ] [1,C] [ 1 , C ] . To state the full tradeoff across all proximity regimes, define the rate function
F ( n , ϵ ) = { n 2 , 0 < ϵ ≤ n − 2 , n / ϵ , n − 2 < ϵ ≤ n − 1 , n / ϵ , n − 1 < ϵ ≤ n − 1 / 2 , ( n / ϵ ) 2 / 3 , n − 1 / 2 < ϵ ≤ 1. F(n,\epsilon) =
\begin{cases}
n^2, & 0 < \epsilon\le n^{-2},\\
n/\sqrt{\epsilon}, & n^{-2} < \epsilon\le n^{-1},\\
\sqrt{n}/\epsilon, & n^{-1} < \epsilon\le n^{-1/2},\\
(n/\epsilon)^{2/3}, & n^{-1/2} < \epsilon\le1.
\end{cases} F ( n , ϵ ) = ⎩ ⎨ ⎧ n 2 , n / ϵ , n / ϵ , ( n / ϵ ) 2/3 , 0 < ϵ ≤ n − 2 , n − 2 < ϵ ≤ n − 1 , n − 1 < ϵ ≤ n − 1/2 , n − 1/2 < ϵ ≤ 1.
Theorem 1.2. Fix C > 2 C > 2 C > 2 and ϵ 0 = 1 / 80 \epsilon_0 = 1/80 ϵ 0 = 1/80 . For all sufficiently large n n n and 0 < ϵ ≤ ϵ 0 0 < \epsilon\le\epsilon_0 0 < ϵ ≤ ϵ 0 :
Sharp nonadaptive complexity on [ 1 , C ] [1,C] [ 1 , C ] (Theorem 6.8 ): For inputs with entries in [ 1 , C ] [1,C] [ 1 , C ] , both one-sided and two-sided nonadaptive ϵ \epsilon ϵ -testing of general metrics have query complexity Θ C ( F ( n , ϵ ) ) \Theta_C(F(n,\epsilon)) Θ C ( F ( n , ϵ )) .
Adaptive lower bound on [ 1 , C ] [1,C] [ 1 , C ] (Theorem 6.11 ): Any adaptive two-sided ϵ \epsilon ϵ -tester for general metrics on [ 1 , C ] [1,C] [ 1 , C ] requires Ω C ( n / log n ) \Omega_C(\sqrt{n/\log n}) Ω C ( n / log n ) queries.
Transfer to general and δ \delta δ -hyperbolic metrics: On arbitrary nonnegative inputs, nonadaptive and adaptive two-sided ϵ \epsilon ϵ -testing require Ω ( F ( n , ϵ ) ) \Omega(F(n,\epsilon)) Ω ( F ( n , ϵ )) and Ω ( n / log n ) \Omega(\sqrt{n/\log n}) Ω ( n / log n ) queries, respectively, both for general metrics and pseudometrics (Theorem 6.12 ) and for δ \delta δ -hyperbolic metrics with any fixed δ > 0 \delta> 0 δ > 0 (Remark 4.12).
Previously, Bao, Kannan, and Waingarten [9 ] gave a nonadaptive one-sided query lower bound of Ω ( n 2 / 3 − o ( 1 ) ) \Omega(n^{2/3-o(1)}) Ω ( n 2/3 − o ( 1 ) ) using Behrend graphs that applied only at vanishing proximity ϵ = n − o ( 1 ) \epsilon= n^{-o(1)} ϵ = n − o ( 1 ) . Because our packing obstruction avoids progression-free sets, Theorem 1.2 eliminates the n o ( 1 ) n^{o(1)} n o ( 1 ) loss and establishes hardness at fixed constant ϵ \epsilon ϵ even against two-sided and adaptive testers.
Related work, and comparison with our results
Parnas and Ron [31 ] first introduced metric property testing, giving one-sided testers with O ( ϵ − 6 ) O(\epsilon^{-6}) O ( ϵ − 6 ) queries for tree pseudometrics and ultrametrics, and O ( d 2 log 2 ( d + 1 ) / ϵ 2 ) O(d^2\log^2(d+1)/\epsilon^2) O ( d 2 log 2 ( d + 1 ) / ϵ 2 ) queries for Euclidean pseudometrics in R d \mathbb{R}^d R d . Krauthgamer and Sasson [27 ] improved the latter bound to O ( d 2 / ϵ 2 ) O(d^2/\epsilon^2) O ( d 2 / ϵ 2 ) using O ( d / ϵ ) O(d/\epsilon) O ( d / ϵ ) sampled points. For strict tree metrics and injective Euclidean realizations, Parnas and Ron proved Ω ( n ) \Omega(\sqrt{n}) Ω ( n ) query lower bounds even with two-sided error. Our proofs unify these qualitative results; our Euclidean bound has weaker ϵ \epsilon ϵ -dependence than [27 ] .
Bao, Kannan, and Waingarten [9 ] established a nonadaptive one-sided O ( n 2 / 3 / ϵ 4 / 3 ) O(n^{2/3}/\epsilon^{4/3}) O ( n 2/3 / ϵ 4/3 ) -query tester for general metrics and improved the ultrametric testing bound to O ~ ( ϵ − 2 ) \widetilde{O}(\epsilon^{-2}) O ( ϵ − 2 ) . They also studied tree metric testing. Their Behrend graph lower bound for general metrics applies at ϵ \epsilon ϵ vanishing with n n n . Our obstruction holds at fixed ϵ \epsilon ϵ , even for entries in [ 1 , C ] [1,C] [ 1 , C ] with any fixed C > 2 C > 2 C > 2 . Onak [30 ] studied tree metrics, ultrametrics, and line embeddings in a model measuring distance by point modifications.
For graphs, Goldreich and Trevisan [25 ] canonicalized constant-query testers using uniformly sampled induced subgraphs. Alon and Shapira [5 ] established one-sided testability of every hereditary graph property and characterized oblivious one-sided testability. Austin and Tao [6 ] developed testing and repair results for hereditary graph and hypergraph properties; Alon, Ben-Eliezer, and Fischer [1 ] established testability for hereditary ordered graphs and finite-alphabet matrices. We decompose removability for real-valued matrices into two structural conditions; completion stability concerns existence of close completions and differs from the local repairability in [6 ] .
Metric repair and the metric violation distance problem also aim at minimizing the number of changed entries [21 , 20 ] of an input matrix. Fan, Gilbert, Raichel, Sonthalia, and Van Buskirk [19 ] studied incomplete graphs using nonmetric cycles. Cohen-Addad, Fan, Lee, and de Mesmay [13 ] obtained an O ( log n ) O(\log n) O ( log n ) -approximation for metric violation distance and a constant-factor approximation for ultrametric violation distance. Bandyapadhyay, Lochet, Lokshtanov, Saurabh, Sonar, Surianarayanan, and Xue [10 ] gave a single-exponential fixed-parameter algorithm and a linear kernel for metric repair, and proved fixed-parameter tractability of tree metric repair. Our bounded range completion theorem controls the edits needed to fill sparse holes, including those forced by longer nonmetric cycles. Metric nearness instead minimizes a norm of the numerical perturbation [7 ] .
Organization of the paper
§ 2 introduces the testing model, local predicates, and the metric families considered in the paper. § 3 proves the structural characterization of one-sided testability through removal, packing amplification, and completion stability. § 4 establishes packing amplification for the geometric families and constructs a packing obstruction for general metrics. § 5 proves the corresponding completion results and identifies the obstruction caused by injective realizations. Finally, § 7 derives quantitative testing bounds, including sharp nonadaptive bounds for metrics with bounded aspect ratio and an adaptive lower bound.
Preliminaries
Fix an integer k ≥ 2 k \ge2 k ≥ 2 and a nonempty value set Λ ⊆ R ≥ 0 \Lambda\subseteq\mathbb{R}_{\ge0} Λ ⊆ R ≥ 0 . For n ≥ 1 n \ge1 n ≥ 1 , let D n \mathcal{D}_n D n be the set of symmetric matrices with off-diagonal entries in Λ \Lambda Λ and diagonal entries fixed to 0 0 0 .
For A , B ∈ D n A,B \in\mathcal{D}_n A , B ∈ D n , define the normalized Hamming distance between A , B A,B A , B as
dist n ( A , B ) = 2 n 2 ∣ { e ∈ ( [ n ] 2 ) : A e ≠ B e } ∣ . \operatorname{dist}_n(A,B) = \frac{2}{n^2}\left|\left\{e \in\binom{[n]}{2}: A_e \ne B_e\right\}\right|. dist n ( A , B ) = n 2 2 { e ∈ ( 2 [ n ] ) : A e = B e } .
For a nonempty set Q ⊆ D n \mathcal{Q} \subseteq\mathcal{D}_n Q ⊆ D n , define dist n ( A , Q ) = min B ∈ Q dist n ( A , B ) \operatorname{dist}_n(A,\mathcal{Q}) = \min_{B \in\mathcal{Q}} \operatorname{dist}_n(A,B) dist n ( A , Q ) = min B ∈ Q dist n ( A , B ) .
For probability distributions μ , ν \mu,\nu μ , ν , denote by TV ( μ , ν ) = sup E ∣ μ ( E ) − ν ( E ) ∣ \operatorname{TV}(\mu,\nu) = \sup_E |\mu(E)-\nu(E)| TV ( μ , ν ) = sup E ∣ μ ( E ) − ν ( E ) ∣ the total variation distance between μ , ν \mu,\nu μ , ν , where the supremum is over measurable events.
Local Predicates and Testability
Let Φ ⊆ Λ ( [ k ] 2 ) \Phi\subseteq\Lambda^{\binom{[k]}{2}} Φ ⊆ Λ ( 2 [ k ] ) be a permutation-invariant k k k -point predicate. For S ∈ ( [ n ] k ) S \in\binom{[n]}{k} S ∈ ( k [ n ] ) , membership of D [ S ] D[S] D [ S ] in Φ \Phi Φ is interpreted after pulling D [ S ] D[S] D [ S ] back along any bijection [ k ] → S [k] \to S [ k ] → S .
Define
P n = { D ∈ D n : D [ S ] satisfies Φ for every S ∈ ( [ n ] k ) } . \mathcal{P}_n=\left\{D\in\mathcal{D}_n:D[S]\text{ satisfies }\Phi\text{ for every }S\in\binom{[n]}{k}\right\}. P n = { D ∈ D n : D [ S ] satisfies Φ for every S ∈ ( k [ n ] ) } .
For n < k n<k n < k , P n = D n \mathcal{P}_n=\mathcal{D}_n P n = D n . Unless stated otherwise, we assume P n ≠ ∅ \mathcal{P}_n\ne\varnothing P n = ∅ for every n ≥ k n\ge k n ≥ k .
For D ∈ D n D\in\mathcal{D}_n D ∈ D n with n ≥ k n\ge k n ≥ k , define
V ( D ) = { S ∈ ( [ n ] k ) : D [ S ] violates Φ } , and viol ( D ) = ∣ V ( D ) ∣ ( n k ) . \mathcal{V}(D)=\left\{S\in\binom{[n]}{k}:D[S]\text{ violates }\Phi\right\},\qquad\text{and}\qquad\operatorname{viol}(D)=\frac{|\mathcal{V}(D)|}{\binom{n}{k}}. V ( D ) = { S ∈ ( k [ n ] ) : D [ S ] violates Φ } , and viol ( D ) = ( k n ) ∣ V ( D ) ∣ .
Definition 2.1 (One-sided tester). A one-sided q q q -query ϵ \epsilon ϵ -tester for P = { P n } \mathcal{P}=\{\mathcal{P}_n\} P = { P n } is an information-theoretic randomized adaptive decision tree which queries at most q q q off-diagonal entries and satisfies:
(1) every D ∈ P n D\in\mathcal{P}_n D ∈ P n is accepted with probability 1 1 1 ;
(2) every D D D with dist n ( D , P n ) > ϵ \operatorname{dist}_n(D,\mathcal{P}_n)>\epsilon dist n ( D , P n ) > ϵ is rejected with probability at least 2 / 3 2/3 2/3 .
If the query bound q = q ( ϵ ) q=q(\epsilon) q = q ( ϵ ) in the above definition depends only on P \mathcal{P} P and ϵ \epsilon ϵ but not n n n , then we say that P \mathcal{P} P is one-sided testable.
Definition 2.2 (Two-sided tester). A two-sided q q q -query ϵ \epsilon ϵ -tester for P = { P n } \mathcal{P}=\{\mathcal{P}_n\} P = { P n } is an information-theoretic randomized adaptive decision tree which queries at most q q q off-diagonal entries and satisfies:
(1) every D ∈ P n D\in\mathcal{P}_n D ∈ P n is accepted with probability at least 2 / 3 2/3 2/3 ;
(2) every D D D with dist n ( D , P n ) > ϵ \operatorname{dist}_n(D,\mathcal{P}_n)>\epsilon dist n ( D , P n ) > ϵ is rejected with probability at least 2 / 3 2/3 2/3 .
Metric families and their extendability
Definition 2.3 (Extendability). A family P = { P n } \mathcal{P}=\{\mathcal{P}_n\} P = { P n } is extendable if, for every n ≥ r ≥ k n\ge r\ge k n ≥ r ≥ k and every A ∈ P r A\in\mathcal{P}_r A ∈ P r , there exist B ∈ P n B\in\mathcal{P}_n B ∈ P n and an injection ι : [ r ] ↪ [ n ] \iota:[r]\hookrightarrow[n] ι : [ r ] ↪ [ n ] such that B ι ( a ) ι ( b ) = A a b B_{\iota(a)\iota(b)}=A_{ab} B ι ( a ) ι ( b ) = A ab for every a b ∈ ( [ r ] 2 ) ab\in\binom{[r]}{2} ab ∈ ( 2 [ r ] ) .
We now define the principal metric and geometric families and verify their extendability. To distinguish arbitrary pseudometric realizations from injective realizations, we use a superscript + + + for predicates and families restricted to positive off-diagonal entries Γ = ( 0 , ∞ ) ⊆ R ≥ 0 \Gamma=(0,\infty)\subseteq\mathbb{R}_{\ge0} Γ = ( 0 , ∞ ) ⊆ R ≥ 0 .
The tree and Euclidean symbols below denote local families with the preceding vacuous convention at orders below the predicate arity. Identifications with global geometric realization families are asserted at and above that arity. If global realizability is required at the finitely many smaller orders, those inputs can instead be inspected completely; none of the asymptotic conclusions is affected.
General and bounded aspect ratio metrics
Write M n \mathcal{M}_n M n for the positive-valued metrics on [ n ] [n] [ n ] and M ‾ n \overline{\mathcal{M}}_n M n for the nonnegative-valued pseudometrics on [ n ] [n] [ n ] . For C > 1 C>1 C > 1 , define M n [ 1 , C ] = M n ∩ [ 1 , C ] ( [ n ] 2 ) \mathcal{M}_n[1,C]=\mathcal{M}_n\cap[1,C]^{\binom{[n]}{2}} M n [ 1 , C ] = M n ∩ [ 1 , C ] ( 2 [ n ] ) .
On the ambient value set Λ = [ 1 , C ] \Lambda=[1,C] Λ = [ 1 , C ] with k = 3 k=3 k = 3 , the family M [ 1 , C ] = { M n [ 1 , C ] } \mathcal{M}[1,C]=\{\mathcal{M}_n[1,C]\} M [ 1 , C ] = { M n [ 1 , C ]} is defined by
Φ m e t = { ( a , b , c ) ∈ [ 1 , C ] 3 : a ≤ b + c , b ≤ a + c , c ≤ a + b } . \Phi_{\mathrm{met}}=\left\{(a,b,c)\in[1,C]^3:a\le b+c,\ b\le a+c,\ c\le a+b\right\}. Φ met = { ( a , b , c ) ∈ [ 1 , C ] 3 : a ≤ b + c , b ≤ a + c , c ≤ a + b } .
Metrics with bounded aspect ratio M [ 1 , C ] \mathcal{M}[1,C] M [ 1 , C ] are extendable by assigning distance C C C to every pair involving a new vertex. General metrics M \mathcal{M} M and pseudometrics M ‾ \overline{\mathcal{M}} M are extendable by assigning the common value R = max ( { 1 } ∪ { old entries } ) R=\max\left(\{1\}\cup\{\text{old entries}\}\right) R = max ( { 1 } ∪ { old entries } ) to every pair involving a new vertex.
Ultrametrics
Let k = 3 k=3 k = 3 and define
Φ u l t = { ( a , b , c ) ∈ Λ 3 : max { a , b , c } is attained at least twice } . \Phi_{\mathrm{ult}}=\{(a,b,c)\in\Lambda^3:\max\{a,b,c\}\text{ is attained at least twice}\}. Φ ult = {( a , b , c ) ∈ Λ 3 : max { a , b , c } is attained at least twice } .
Denote by U = { U n } \mathcal{U}=\{U_n\} U = { U n } the family. For Λ = R ≥ 0 \Lambda=\mathbb{R}_{\ge0} Λ = R ≥ 0 , denote Φ u l t + = Φ u l t ∩ ( 0 , ∞ ) 3 \Phi_{\mathrm{ult}}^+=\Phi_{\mathrm{ult}}\cap(0,\infty)^3 Φ ult + = Φ ult ∩ ( 0 , ∞ ) 3 and U + = { U n + } \mathcal{U}^+=\{U_n^+\} U + = { U n + } for the strict ultrametrics.
Lemma 2.4. The family U \mathcal{U} U is extendable over any nonempty value set Λ \Lambda Λ , and U + \mathcal{U}^+ U + is extendable.
Proof. Let n ≥ r ≥ 3 n\ge r\ge3 n ≥ r ≥ 3 and A ∈ U r A\in U_r A ∈ U r . Set R = max e ∈ ( [ r ] 2 ) A e ∈ Λ R=\max_{e\in\binom{[r]}{2}}A_e\in\Lambda R = max e ∈ ( 2 [ r ] ) A e ∈ Λ . For all distinct pairs of indices i , j ≤ r i,j\le r i , j ≤ r , define B i j = A i j B_{ij}=A_{ij} B ij = A ij , otherwise define B i j = R B_{ij}=R B ij = R . Every triangle containing a new vertex has at least two edges of value R R R , and its remaining edge has value at most R R R . Thus B ∈ U n B\in U_n B ∈ U n . If A A A is strict, then R > 0 R>0 R > 0 and B B B is strict as well.
Tree pseudometrics and strict tree metrics
Set k = 4 k=4 k = 4 and Λ = R ≥ 0 \Lambda=\mathbb{R}_{\ge0} Λ = R ≥ 0 . Define Φ t r e e \Phi_{\mathrm{tree}} Φ tree to consist of those symmetric, zero-diagonal matrices D D D on [ 4 ] [4] [ 4 ] for which there exist a weighted tree T = ( V , E ) T=(V,E) T = ( V , E ) , positive edge weights w : E → ( 0 , ∞ ) w:E\to(0,\infty) w : E → ( 0 , ∞ ) , and a not necessarily injective map ϕ : [ 4 ] → V \phi:[4]\to V ϕ : [ 4 ] → V satisfying D i j = dist T ( ϕ ( i ) , ϕ ( j ) ) D_{ij}=\operatorname{dist}_T(\phi(i),\phi(j)) D ij = dist T ( ϕ ( i ) , ϕ ( j )) for all i , j ∈ [ 4 ] i,j\in[4] i , j ∈ [ 4 ] .
Equivalently, by Buneman’s characterization [12 ] , D D D satisfies the four-point condition
D i j + D k l ≤ max { D i k + D j l , D i l + D j k } ( i , j , k , l ∈ [ 4 ] ) , D_{ij}+D_{kl}\le\max\{D_{ik}+D_{jl},D_{il}+D_{jk}\}\qquad(i,j,k,l\in[4]), D ij + D k l ≤ max { D ik + D j l , D i l + D j k } ( i , j , k , l ∈ [ 4 ]) ,
with repeated indices allowed, thereby including triangle inequalities.
Let T = { T n } \mathcal{T}=\{T_n\} T = { T n } be the resulting local family. Define Φ t r e e + = Φ t r e e ∩ ( 0 , ∞ ) ( [ 4 ] 2 ) \Phi_{\mathrm{tree}}^+=\Phi_{\mathrm{tree}}\cap(0,\infty)^{\binom{[4]}{2}} Φ tree + = Φ tree ∩ ( 0 , ∞ ) ( 2 [ 4 ] ) , and let T + = { T n + } \mathcal{T}^+=\{T_n^+\} T + = { T n + } be its local family. The strict predicate characterizes injective realizations in positively weighted trees, allowing labeled internal vertices and additional unlabeled vertices. By the classical local-to-global theorem [12 ] , for n ≥ 4 n\ge4 n ≥ 4 , T n T_n T n and T n + T_n^+ T n + coincide with the matrices globally realized in weighted trees by arbitrary and injective maps, respectively. Edges of length zero in a representation with nonnegative edge weights may be contracted; positivity of all off-diagonal distances prevents distinct labels from being identified in the strict case.
Lemma 2.5. The families T \mathcal{T} T and T + \mathcal{T}^+ T + are extendable.
Proof. Let n ≥ r ≥ 4 n\ge r\ge4 n ≥ r ≥ 4 and A ∈ T r A\in T_r A ∈ T r . Realize A A A by a weighted tree. Attach each new label to the point representing label 1 by a new edge of length 1. Equivalently, define
B i j = { A i j , i , j ∈ [ r ] , A i 1 + 1 , i ∈ [ r ] , j ∉ [ r ] , 2 , i , j ∉ [ r ] , i ≠ j , B_{ij}=
\begin{cases}
A_{ij}, & i,j\in[r],\\
A_{i1}+1, & i\in[r],\ j\notin[r],\\
2, & i,j\notin[r],\ i\ne j,
\end{cases} B ij = ⎩ ⎨ ⎧ A ij , A i 1 + 1 , 2 , i , j ∈ [ r ] , i ∈ [ r ] , j ∈ / [ r ] , i , j ∈ / [ r ] , i = j , and impose symmetry. This is a tree pseudometric preserving all old entries. If the old realization is injective, the new realization is injective as well.
d d d -dimensional Euclidean metrics
Fix an integer d ≥ 1 d \ge1 d ≥ 1 . Denote k = d + 3 k = d + 3 k = d + 3 and Λ = R ≥ 0 \Lambda= \mathbb{R}_{\ge0} Λ = R ≥ 0 . Define Φ E u c ( d ) \Phi_{\mathrm{Euc}}^{(d)} Φ Euc ( d ) as the set of symmetric, zero-diagonal matrices D D D on [ k ] [k] [ k ] for which there exists a (not necessarily injective) mapping ϕ : [ k ] → R d \phi: [k] \to\mathbb{R}^{d} ϕ : [ k ] → R d satisfying D i j = ∥ ϕ ( i ) − ϕ ( j ) ∥ 2 D_{ij} = \lVert\phi(i) - \phi(j)\rVert_2 D ij = ∥ ϕ ( i ) − ϕ ( j ) ∥ 2 for all i , j ∈ [ k ] i,j \in[k] i , j ∈ [ k ] . Let E ( d ) = { E n ( d ) } \mathcal{E}^{(d)} = \{\mathcal{E}^{(d)}_n\} E ( d ) = { E n ( d ) } be the resulting local family. Define Φ E u c ( d ) , + = Φ E u c ( d ) ∩ ( 0 , ∞ ) ( k 2 ) \Phi_{\mathrm{Euc}}^{(d),+} = \Phi_{\mathrm{Euc}}^{(d)} \cap(0,\infty)^{\binom{k}{2}} Φ Euc ( d ) , + = Φ Euc ( d ) ∩ ( 0 , ∞ ) ( 2 k ) , and let E ( d ) , + = { E n ( d ) , + } \mathcal{E}^{(d),+} = \{\mathcal{E}^{(d),+}_n\} E ( d ) , + = { E n ( d ) , + } be its local family.
The affine dimension of a Euclidean distance matrix is well-defined. Indeed, after choosing a label o o o , the Gram matrix G G G where G i j = D o i 2 + D o j 2 − D i j 2 2 G_{ij} = \frac{D_{oi}^{2}+D_{oj}^{2}-D_{ij}^{2}}{2} G ij = 2 D o i 2 + D o j 2 − D ij 2 for all i , j ≠ o i,j \ne o i , j = o is determined by the distances, and its rank is the affine dimension of every realization. By the classical theorem of Schoenberg [32 ] and Young and Householder [35 ] , positive semidefiniteness and rank at most d d d of G G G characterize realization in R d \mathbb{R}^{d} R d . This also gives a rational decision procedure and Borel defining conditions.
Recall that vectors z 0 , … , z s z_0,\ldots,z_s z 0 , … , z s are affinely independent if ∑ i = 0 s α i z i = 0 \sum_{i=0}^{s}\alpha_i z_i = 0 ∑ i = 0 s α i z i = 0 and ∑ i = 0 s α i = 0 \sum_{i=0}^{s}\alpha_i = 0 ∑ i = 0 s α i = 0 imply α 0 = ⋯ = α s = 0 \alpha_0 = \cdots= \alpha_s = 0 α 0 = ⋯ = α s = 0 .
Lemma 2.6. Let vectors z 0 , … , z d ∈ R d z_0,\ldots,z_d \in\mathbb{R}^{d} z 0 , … , z d ∈ R d be affinely independent . If points x , y ∈ R d x,y \in\mathbb{R}^{d} x , y ∈ R d satisfy ∥ x − z i ∥ 2 = ∥ y − z i ∥ 2 \lVert x-z_i\rVert_2 = \lVert y-z_i\rVert_2 ∥ x − z i ∥ 2 = ∥ y − z i ∥ 2 for all i = 0 , … , d i = 0,\ldots,d i = 0 , … , d , then x = y x = y x = y . The same assertion holds inside the affine span of any affinely independent set, including a singleton.
Proof. Subtracting the squared-distance equality for z 0 z_0 z 0 from that for z i z_i z i gives
⟨ x − y , z i − z 0 ⟩ = 0 ( i = 1 , … , d ) . \langle x-y,z_i-z_0\rangle= 0 \qquad(i=1,\ldots,d). ⟨ x − y , z i − z 0 ⟩ = 0 ( i = 1 , … , d ) .
These difference vectors span R d \mathbb{R}^{d} R d , so x − y = 0 x-y = 0 x − y = 0 . The affine-span version is the same argument after identifying the affine span with a Euclidean space; the singleton case is immediate.
We record the finite local characterization of Menger [29 , 11 ] .
Lemma 2.7 (Local characterization of Euclidean metrics). Let n ≥ d + 3 n \ge d+3 n ≥ d + 3 and D ∈ D n D \in\mathcal{D}_n D ∈ D n . Suppose every ( d + 3 ) (d+3) ( d + 3 ) -point principal submatrix of D D D is realized in R d \mathbb{R}^{d} R d . Then D D D is realized in R d \mathbb{R}^{d} R d . If all off-diagonal entries of D D D are positive, the realizing points are pairwise distinct.
Proof. Every principal submatrix of order at most d + 3 d+3 d + 3 is realizable, by extending its label set to a ( d + 3 ) (d+3) ( d + 3 ) -set. Choose a set Z ⊆ [ n ] Z \subseteq[n] Z ⊆ [ n ] of maximum cardinality such that D [ Z ] D[Z] D [ Z ] has an affinely independent realization in R d \mathbb{R}^{d} R d . Write ∣ Z ∣ = s + 1 ≤ d + 1 |Z| = s+1 \le d+1 ∣ Z ∣ = s + 1 ≤ d + 1 , fix a realization V = { v 0 , … , v s } V = \{v_0,\ldots,v_s\} V = { v 0 , … , v s } , and let A A A be its affine span.
For x ∉ Z x \notin Z x ∈ / Z , the matrix D [ Z ∪ { x } ] D[Z \cup\{x\}] D [ Z ∪ { x }] is realizable. Two realizations of the affine basis have the same Gram matrix and can be aligned by a Euclidean isometry. After aligning Z Z Z with V V V , the realization of x x x lies in A A A : otherwise Z ∪ { x } Z \cup\{x\} Z ∪ { x } would be affinely independent, contrary to maximality. Its position in A A A is unique by Lemma 2.6. Denote it by ϕ ( x ) \phi(x) ϕ ( x ) , and use the prescribed points of V V V for labels in Z Z Z .
For distinct x , y ∉ Z x,y \notin Z x , y ∈ / Z , the set Z ∪ { x , y } Z \cup\{x,y\} Z ∪ { x , y } has size at most d + 3 d+3 d + 3 and is realizable. Align its realization on Z Z Z . Maximality again places both remaining points in A A A , and uniqueness identifies them with ϕ ( x ) \phi(x) ϕ ( x ) and ϕ ( y ) \phi(y) ϕ ( y ) . Hence D x y = ∥ ϕ ( x ) − ϕ ( y ) ∥ 2 D_{xy} = \lVert\phi(x)-\phi(y)\rVert_2 D x y = ∥ ϕ ( x ) − ϕ ( y ) ∥ 2 . All other distances are preserved by construction. Positive off-diagonal distances imply injectivity.
Lemma 2.8. The families E ( d ) \mathcal{E}^{(d)} E ( d ) and E ( d ) , + \mathcal{E}^{(d),+} E ( d ) , + are extendable.
Proof. Let n ≥ r ≥ d + 3 n \ge r \ge d+3 n ≥ r ≥ d + 3 and A ∈ E r ( d ) A \in\mathcal{E}^{(d)}_r A ∈ E r ( d ) . By Lemma 2.7, realize A A A by points x 1 , … , x r ∈ R d x_1,\ldots,x_r \in\mathbb{R}^{d} x 1 , … , x r ∈ R d . Choose additional points that are pairwise distinct and distinct from every old point. Their Euclidean distance matrix extends A A A and belongs to E n ( d ) \mathcal{E}^{(d)}_n E n ( d ) . If A A A was strict, all realizing points are distinct, so the extension is strict.
Characterization of one-sided testing: Proof of Theorem 1.1
We characterize constant-query one-sided testability for extendable local matrix properties. We begin by showing that one-sided testability is equivalent to removability via a canonicalization framework (Theorem 3.4 ). We then establish our main structural characterization (Theorem 3.10 ), proving that removability decomposes into two combinatorial conditions: packing amplification and completion stability. Together, these results yield our main equivalence (Corollary 3.11 ) and isolate the two structural obstructions to testability (Corollary 3.12 ).
Canonical testers and removability
To prove Theorem 3.4 , we first reduce arbitrary adaptive one-sided testers to canonical testers that inspect a uniformly random induced submatrix. The lazy permutation coupling in Lemma 3.1 and the resulting canonical reduction in Lemma 3.2 and Theorem 3.4 adapt the canonicalization framework of Goldreich and Trevisan [25 Section 4, cf. Lemma 4.1 and Theorem 4.5] from graph properties to extendable local matrix properties. This connects one-sided testability to removal lemmas for hereditary properties in the spirit of Alon and Shapira [5 ] .
Lemma 3.1. Let n ≥ r n \ge r n ≥ r . Fix an adaptive decision tree whose queries are unordered pairs of labels from [ n ] [n] [ n ] and which touches at most r r r distinct labels. For a fixed input D ∈ D n D \in\mathcal{D}_n D ∈ D n , compare:
choose a uniform permutation σ \sigma σ of [ n ] [n] [ n ] , and answer { i , j } \{i,j\} { i , j } with D σ ( i ) σ ( j ) D_{\sigma(i)\sigma(j)} D σ ( i ) σ ( j ) ;
choose a uniform r r r -set U ⊆ [ n ] U \subseteq[n] U ⊆ [ n ] , assign each newly touched label to a uniformly random unused element of U U U , and answer using the resulting partial injection.
The answer transcripts have the same distribution. Moreover, the experiments can be coupled to have the same sequence of images of newly touched labels.
Proof. Expose newly touched labels in a fixed order when a query introduces two of them. Suppose the exposed images are distinct vertices v 1 , … , v s v_1,\ldots,v_s v 1 , … , v s , where s < r s<r s < r .
In the permutation experiment, the next image is uniform on the unused vertices of [ n ] [n] [ n ] . In the r r r -set experiment, conditional on these assignments, U U U is uniform among the r r r -sets containing { v 1 , … , v s } \{v_1,\ldots,v_s\} { v 1 , … , v s } : for each such U U U , the probability of choosing U U U and making these assignments is ( n − s r − s ) − 1 ( r − s ) ! r ! \binom{n-s}{r-s}^{-1}\frac{(r-s)!}{r!} ( r − s n − s ) − 1 r ! ( r − s )! . Thus the next image is again uniform on the unused vertices of [ n ] [n] [ n ] .
For a fixed input and decision tree, previous answers and subsequent query choices are determined by the exposed images. Conditioning on the complete partial history therefore adds no restriction on the remaining assignments. Induction proves the claim. □ \square □
Lemma 3.2. Assume P \mathcal{P} P is extendable. Let A A A be a one-sided q q q -query ϵ \epsilon ϵ -tester, and put r = max { k , 2 q } r=\max\{k,2q\} r = max { k , 2 q } . For n ≥ r n\ge r n ≥ r , symmetrize A A A by a uniform permutation of [ n ] [n] [ n ] . Let C C C query a uniform r r r -set U U U completely and lazily simulate A A A within U U U . Then
Pr [ C rejects D ] = Pr [ A s y m rejects D ] ≤ Pr U [ D [ U ] ∉ P r ] . \Pr[C\text{ rejects }D]=\Pr[A^{\mathrm{sym}}\text{ rejects }D]\le\Pr_{U}[D[U]\notin\mathcal{P}_r]. Pr [ C rejects D ] = Pr [ A sym rejects D ] ≤ U Pr [ D [ U ] ∈ / P r ] . Proof. The equality follows from Lemma 3.1 , conditional on the internal randomness of A A A .
Fix U U U with D [ U ] ∈ P r D[U]\in\mathcal{P}_r D [ U ] ∈ P r . Extendability gives a valid B ∈ P n B\in\mathcal{P}_n B ∈ P n containing an induced copy of D [ U ] D[U] D [ U ] on some r r r -set W W W . Conditional on sampling U U U in D D D or W W W in B B B , the lazy simulations have the same
transcript law. Since W W W has positive sampling probability, positive conditional rejection probability on W W W would contradict one-sided completeness on B B B . Thus the conditional rejection probability on U U U is zero.
Definition 3.3 (Removal modulus). For ϵ > 0 \epsilon> 0 ϵ > 0 , define
ρ ( ϵ ) = inf n ≥ k , D ∈ D n dist n ( D , P n ) > ϵ viol ( D ) . \rho(\epsilon) = \inf_{\substack{n \ge k,\ D \in\mathcal{D}_n\\ \operatorname{dist}_n(D,\mathcal{P}_n)>\epsilon}} \operatorname{viol}(D). ρ ( ϵ ) = n ≥ k , D ∈ D n dist n ( D , P n ) > ϵ inf viol ( D ) . We say that Φ \Phi Φ is removable if ρ ( ϵ ) > 0 \rho(\epsilon)>0 ρ ( ϵ ) > 0 for every ϵ > 0 \epsilon>0 ϵ > 0 .
Equivalently, for every ϵ > 0 \epsilon>0 ϵ > 0 , there exists δ ( ϵ ) > 0 \delta(\epsilon)>0 δ ( ϵ ) > 0 such that
viol ( D ) < δ ( ϵ ) ⟹ dist n ( D , P n ) ≤ ϵ \operatorname{viol}(D)<\delta(\epsilon) \quad\Longrightarrow\quad\operatorname{dist}_n(D,\mathcal{P}_n)\le\epsilon viol ( D ) < δ ( ϵ ) ⟹ dist n ( D , P n ) ≤ ϵ for all n ≥ k n\ge k n ≥ k and D ∈ D n D\in\mathcal{D}_n D ∈ D n .
Theorem 3.4 (Testing-removal equivalence). Assume Φ \Phi Φ is measurable, and fix ϵ > 0 \epsilon>0 ϵ > 0 . If ρ ( ϵ ) > 0 \rho(\epsilon)>0 ρ ( ϵ ) > 0 , then P \mathcal{P} P has a one-sided ϵ \epsilon ϵ -tester using at most ( k 2 ) ⌈ log 3 ρ ( ϵ ) ⌉ \binom{k}{2}\left\lceil\frac{\log3}{\rho(\epsilon)}\right\rceil ( 2 k ) ⌈ ρ ( ϵ ) l o g 3 ⌉ queries.
Conversely, suppose P \mathcal{P} P is extendable and has a one-sided q q q -query ϵ \epsilon ϵ -tester. Put r = max { k , 2 q } r=\max\{k,2q\} r = max { k , 2 q } . Querying a uniform r r r -submatrix D [ U ] D[U] D [ U ] and rejecting if D [ U ] ∉ P r D[U]\notin\mathcal{P}_r D [ U ] ∈ / P r is a one-sided ϵ \epsilon ϵ -tester using at most ( r 2 ) \binom{r}{2} ( 2 r ) queries; when n < r n<r n < r , query the whole matrix instead. Moreover,
ρ ( ϵ ) ≥ 2 3 ( r k ) . \rho(\epsilon)\ge\frac{2}{3\binom{r}{k}}. ρ ( ϵ ) ≥ 3 ( k r ) 2 . Consequently, under extendability, removability is equivalent to one-sided testability with query complexity independent of n n n .
Proof. For the forward implication, independently sample s = ⌈ log 3 ρ ( ϵ ) ⌉ s=\left\lceil\frac{\log3}{\rho(\epsilon)}\right\rceil s = ⌈ ρ ( ϵ ) l o g 3 ⌉ uniform k k k -sets and reject if one violates Φ \Phi Φ . An ϵ \epsilon ϵ -far input is accepted with probability at most ( 1 − ρ ( ϵ ) ) s ≤ e − ρ ( ϵ ) s ≤ 1 / 3 (1-\rho(\epsilon))^s\le e^{-\rho(\epsilon)s}\le1/3 ( 1 − ρ ( ϵ ) ) s ≤ e − ρ ( ϵ ) s ≤ 1/3 .
For the converse, Lemma 3.2 implies that an ϵ \epsilon ϵ -far input of order n ≥ r n\ge r n ≥ r has an invalid uniform r r r -submatrix with probability at least 2 / 3 2/3 2/3 . Hence
2 3 ≤ ∑ T ∈ V ( D ) Pr [ T ⊆ U ] = ∣ V ( D ) ∣ ( r k ) ( n k ) = ( r k ) viol ( D ) . \frac{2}{3}\le\sum_{T\in\mathcal{V}(D)}\Pr[T\subseteq U]=|\mathcal{V}(D)|\frac{\binom{r}{k}}{\binom{n}{k}}=\binom{r}{k}\operatorname{viol}(D). 3 2 ≤ T ∈ V ( D ) ∑ Pr [ T ⊆ U ] = ∣ V ( D ) ∣ ( k n ) ( k r ) = ( k r ) viol ( D ) .
For k ≤ n < r k\le n<r k ≤ n < r , an ϵ \epsilon ϵ -far input has at least one violation, so viol ( D ) ≥ ( n k ) − 1 ≥ ( r k ) − 1 \operatorname{viol}(D)\ge\binom{n}{k}^{-1}\ge\binom{r}{k}^{-1} viol ( D ) ≥ ( k n ) − 1 ≥ ( k r ) − 1 . Taking the infimum proves the bound. Measurability makes the local membership decisions admissible.
Structural decomposition of removability
We now introduce the two combinatorial properties that govern removability: packing amplification and completion stability.
Definition 3.5 (Packing amplification). A family S ⊆ V ( D ) S\subseteq\mathcal{V}(D) S ⊆ V ( D ) is edge-disjoint if no edge belongs to more than one member. Let ν ( D ) \nu(D) ν ( D ) be its maximum possible size. For α > 0 \alpha>0 α > 0 , define
Δ ( α ) = inf n ≥ k , D ∈ D n ν ( D ) ≥ α n 2 viol ( D ) . \Delta(\alpha)=\inf_{\substack{n\ge k,\ D\in\mathcal{D}_n\\ \nu(D)\ge\alpha n^2}}\operatorname{viol}(D). Δ ( α ) = n ≥ k , D ∈ D n ν ( D ) ≥ α n 2 inf viol ( D ) . We say that Φ \Phi Φ has packing amplification if Δ ( α ) > 0 \Delta(\alpha)>0 Δ ( α ) > 0 for every α > 0 \alpha>0 α > 0 .
Definition 3.6 (Completion stability). A partial matrix A A A on [ n ] [n] [ n ] assigns values in Λ \Lambda Λ to some pairs. Its set of unspecified edges is denoted H ( A ) H(A) H ( A ) ; these edges are called holes. The partial matrix is locally consistent if every fully specified k k k -subset satisfies Φ \Phi Φ . For such a partial matrix with n ≥ k n \ge k n ≥ k , define
cdist ( A ) = 2 n 2 min B ∈ P n ∣ { e ∈ ( [ n ] 2 ) ∖ H ( A ) : B e ≠ A e } ∣ . \operatorname{cdist}(A)=\frac{2}{n^2}\min_{B\in\mathcal{P}_n}\left|\left\{e\in\binom{[n]}{2}\setminus H(A):B_e\ne A_e\right\}\right|. cdist ( A ) = n 2 2 B ∈ P n min { e ∈ ( 2 [ n ] ) ∖ H ( A ) : B e = A e } . For θ ≥ 0 \theta\ge0 θ ≥ 0 , define Γ ( θ ) = sup A cdist ( A ) \Gamma(\theta)=\sup_A\operatorname{cdist}(A) Γ ( θ ) = sup A cdist ( A ) , where the supremum is over locally consistent partial matrices on n ≥ k n\ge k n ≥ k vertices with ∣ H ( A ) ∣ ≤ θ n 2 |H(A)|\le\theta n^2 ∣ H ( A ) ∣ ≤ θ n 2 . The function Γ \Gamma Γ is non-decreasing. We say that Φ \Phi Φ is completion stable if Γ ( θ ) → 0 \Gamma(\theta)\to0 Γ ( θ ) → 0 as θ ↓ 0 \theta\downarrow0 θ ↓ 0 .
Lemma 3.7. For every D ∈ D n D\in\mathcal{D}_n D ∈ D n with n ≥ k n\ge k n ≥ k , we have dist n ( D , P n ) ≥ 2 ν ( D ) / n 2 \operatorname{dist}_n(D,\mathcal{P}_n)\ge2\nu(D)/n^2 dist n ( D , P n ) ≥ 2 ν ( D ) / n 2 . Consequently, Δ ( α ) ≥ ρ ( α ) \Delta(\alpha)\ge\rho(\alpha) Δ ( α ) ≥ ρ ( α ) for all α > 0 \alpha>0 α > 0 .
Proof. A valid repair changes at least one edge in each member of an edge-disjoint family of violations, and these edits are distinct. If ν ( D ) ≥ α n 2 \nu(D)\ge\alpha n^2 ν ( D ) ≥ α n 2 , then dist n ( D , P n ) ≥ 2 α > α \operatorname{dist}_n(D,\mathcal{P}_n)\ge2\alpha>\alpha dist n ( D , P n ) ≥ 2 α > α , so viol ( D ) ≥ ρ ( α ) \operatorname{viol}(D)\ge\rho(\alpha) viol ( D ) ≥ ρ ( α ) . Take the infimum. □ \square □
Lemma 3.8. Let A A A be locally consistent on n ≥ k n\ge k n ≥ k vertices, and let D D D be any completion of A A A . If ∣ H ( A ) ∣ ≤ θ n 2 |H(A)|\le\theta n^2 ∣ H ( A ) ∣ ≤ θ n 2 , then viol ( D ) ≤ 4 ( k 2 ) θ \operatorname{viol}(D)\le4\binom{k}{2}\theta viol ( D ) ≤ 4 ( 2 k ) θ .
Proof. Every violating k k k -set contains a hole, so ∣ V ( D ) ∣ ≤ ∣ H ( A ) ∣ ( n − 2 k − 2 ) |\mathcal{V}(D)|\le|H(A)|\binom{n-2}{k-2} ∣ V ( D ) ∣ ≤ ∣ H ( A ) ∣ ( k − 2 n − 2 ) . Thus viol ( D ) ≤ ∣ H ( A ) ∣ ( k 2 ) / ( n 2 ) ≤ 2 ( k 2 ) θ n n − 1 ≤ 4 ( k 2 ) θ \operatorname{viol}(D)\le|H(A)|\binom{k}{2}/\binom{n}{2}\le2\binom{k}{2}\frac{\theta n}{n-1}\le4\binom{k}{2}\theta viol ( D ) ≤ ∣ H ( A ) ∣ ( 2 k ) / ( 2 n ) ≤ 2 ( 2 k ) n − 1 θ n ≤ 4 ( 2 k ) θ . □ \square □
Proposition 3.9 (Deterministic repair inequality). For every D ∈ D n D\in\mathcal{D}_n D ∈ D n with n ≥ k n\ge k n ≥ k ,
dist n ( D , P n ) ≤ Γ ( ( k 2 ) ν ( D ) n 2 ) + 2 ( k 2 ) ν ( D ) n 2 . \operatorname{dist}_n(D,\mathcal{P}_n)\le\Gamma\left(\frac{\binom{k}{2}\nu(D)}{n^2}\right)+\frac{2\binom{k}{2}\nu(D)}{n^2}. dist n ( D , P n ) ≤ Γ ( n 2 ( 2 k ) ν ( D ) ) + n 2 2 ( 2 k ) ν ( D ) . Proof. Take a maximum edge-disjoint family S \mathcal{S} S of violations and delete all its edges. The resulting hole set has size at most ( k 2 ) ν ( D ) \binom{k}{2}\nu(D) ( 2 k ) ν ( D ) . The remaining partial matrix A A A is locally consistent, since a fully specified violation would be edge-disjoint from S \mathcal{S} S .
A valid matrix attaining cdist ( A ) \operatorname{cdist}(A) cdist ( A ) differs from D D D on specified edges by at most Γ ( ( k 2 ) ν ( D ) / n 2 ) \Gamma(\binom{k}{2}\nu(D)/n^2) Γ ( ( 2 k ) ν ( D ) / n 2 ) and on holes by at most 2 ( k 2 ) ν ( D ) / n 2 2\binom{k}{2}\nu(D)/n^2 2 ( 2 k ) ν ( D ) / n 2 . Adding the two bounds completes the proof. □ \square □
Theorem 3.10 (Structural characterization of removability). The predicate Φ \Phi Φ is removable if and only if it is completion stable and has packing amplification.
Proof. Suppose Φ \Phi Φ is removable. Fill the holes of a locally consistent partial matrix A A A arbitrarily. If its hole density is at most θ \theta θ , Lemma 3.8 implies that the resulting full matrix has violation density at most 4 ( k 2 ) θ 4\binom{k}{2}\theta 4 ( 2 k ) θ . Whenever 4 ( k 2 ) θ < ρ ( ϵ ) 4\binom{k}{2}\theta<\rho(\epsilon) 4 ( 2 k ) θ < ρ ( ϵ ) , it has a valid repair at distance at most ϵ \epsilon ϵ . Restricting discrepancies to the originally specified edges gives cdist ( A ) ≤ ϵ \operatorname{cdist}(A)\le\epsilon cdist ( A ) ≤ ϵ , so Γ ( θ ) → 0 \Gamma(\theta)\to0 Γ ( θ ) → 0 . Packing amplification follows from Lemma 3.7 .
Conversely, choose θ > 0 \theta>0 θ > 0 such that Γ ( θ ) + 2 θ ≤ ϵ \Gamma(\theta)+2\theta\le\epsilon Γ ( θ ) + 2 θ ≤ ϵ . If D D D is ϵ \epsilon ϵ -far, Proposition 3.9 implies ν ( D ) > θ n 2 / ( k 2 ) \nu(D)>\theta n^2/\binom{k}{2} ν ( D ) > θ n 2 / ( 2 k ) . Therefore viol ( D ) ≥ Δ ( θ / ( k 2 ) ) \operatorname{viol}(D)\ge\Delta(\theta/\binom{k}{2}) viol ( D ) ≥ Δ ( θ / ( 2 k ) ) , and taking the infimum gives the same positive lower bound for ρ ( ϵ ) \rho(\epsilon) ρ ( ϵ ) . This remains valid if there are no ϵ \epsilon ϵ -far inputs. □ \square □
Corollary 3.11 (Testing-structure equivalence). If P \mathcal{P} P is extendable and Φ \Phi Φ is measurable, the following are equivalent:
(1) P \mathcal{P} P has a one-sided constant-query ϵ \epsilon ϵ -tester for every ϵ > 0 \epsilon> 0 ϵ > 0 ;
(2) Φ \Phi Φ is removable;
(3) Φ \Phi Φ is completion stable and has packing amplification.
Proof. Apply Theorems 3.4 and 3.10.
Corollary 3.12 (Two obstructions to removal). The predicate Φ \Phi Φ is not removable if and only if at least one of the following exists:
(1) Packing obstruction. There are α > 0 \alpha> 0 α > 0 and matrices A ( j ) A^{(j)} A ( j ) on s j → ∞ s_j \to\infty s j → ∞ vertices such that ν ( A ( j ) ) ≥ α s j 2 \nu(A^{(j)}) \ge\alpha s_j^2 ν ( A ( j ) ) ≥ α s j 2 and viol ( A ( j ) ) → 0 \operatorname{viol}(A^{(j)}) \to0 viol ( A ( j ) ) → 0 .
(2) Completion obstruction. There are γ > 0 \gamma> 0 γ > 0 and locally consistent partial matrices A ( j ) A^{(j)} A ( j ) on s j → ∞ s_j \to\infty s j → ∞ vertices such that ∣ H ( A ( j ) ) ∣ / s j 2 → 0 |H(A^{(j)})|/s_j^2 \to0 ∣ H ( A ( j ) ) ∣/ s j 2 → 0 and cdist ( A ( j ) ) ≥ γ \operatorname{cdist}(A^{(j)}) \ge\gamma cdist ( A ( j ) ) ≥ γ .
Proof. If Δ ( α ) = 0 \Delta(\alpha) = 0 Δ ( α ) = 0 , choose inputs with violation density less than 1 / j 1/j 1/ j . Each has a violation, so viol ( A ( j ) ) ≥ ( s j k ) − 1 \operatorname{viol}(A^{(j)}) \ge\binom{s_j}{k}^{-1} viol ( A ( j ) ) ≥ ( k s j ) − 1 , forcing s j → ∞ s_j \to\infty s j → ∞ .
If completion stability fails, choose γ > 0 \gamma> 0 γ > 0 and θ j ↓ 0 \theta_j \downarrow0 θ j ↓ 0 with Γ ( θ j ) > 2 γ \Gamma(\theta_j) > 2\gamma Γ ( θ j ) > 2 γ , then choose partial matrices of hole density at most θ j \theta_j θ j and completion distance greater than γ \gamma γ . A bounded subsequence of their orders would eventually have no holes, a contradiction.
Conversely, either sequence makes the corresponding structural condition fail. Apply Theorem 3.10.
Packing amplification
We determine which metric and geometric families satisfy packing amplification. We first establish positive packing bounds for ultrametrics (Lemma 4.1) and tree pseudometrics (Lemma 4.4), reducing the tree case to the ultrametric setting via rooted products. Next, we develop an affine anchor repair method for d d d -dimensional Euclidean pseudometrics (Proposition 4.5), yielding both packing amplification (Lemma 4.6) and quantitative removal bounds (Corollary 4.7). After confirming that packing amplification passes to edgewise restrictions, and thus to strict metric families (Corollary 4.9), we construct a robust metric face (Lemma 4.10) to prove that general metrics and metrics with bounded aspect ratio in [ 1 , C ] [1,C] [ 1 , C ] with C > 2 C > 2 C > 2 fail packing amplification and admit no constant-query one-sided testers (Theorem 4.11).
Ultrametrics and tree pseudometrics
Lemma 4.1 (Packing amplification for ultrametrics). For every α > 0 \alpha> 0 α > 0 ,
Δ u l t ( α ) ≥ min { 1 , 3 50 α 2 } . \Delta_{\mathrm{ult}}(\alpha) \ge\min\left\{1,\frac{3}{50}\alpha^2\right\}. Δ ult ( α ) ≥ min { 1 , 50 3 α 2 } .
Proof. Let M ∈ D n M \in\mathcal{D}_n M ∈ D n , and let T \mathcal{T} T be an edge-disjoint family of m = ν ( M ) m = \nu(M) m = ν ( M ) violating triangles. We prove
∣ V ( M ) ∣ ≥ m 2 100 n . |\mathcal{V}(M)| \ge\frac{m^2}{100n}. ∣ V ( M ) ∣ ≥ 100 n m 2 .
Consider distinct T , T ′ ∈ T T,T' \in\mathcal{T} T , T ′ ∈ T sharing a vertex v v v . By edge-disjointness, they share only v v v . Orient the pair so that the unique maximum in T T T is at least the unique maximum in T ′ T' T ′ . Write T = { a , b , c } T = \{a,b,c\} T = { a , b , c } , with unique maximum edge a b ab ab of value R R R . There is w ∈ T ′ ∖ { v } w \in T' \setminus\{v\} w ∈ T ′ ∖ { v } with M v w < R M_{vw} < R M v w < R , since one edge of T ′ T' T ′ incident with v v v is not its unique maximum.
We claim that T ∪ T ′ T \cup T' T ∪ T ′ contains a violating triangle Q ≠ T , T ′ Q \ne T,T' Q = T , T ′ containing an edge of T T T and the vertex w w w . If v = c v = c v = c , either { a , v , w } \{a,v,w\} { a , v , w } or { b , v , w } \{b,v,w\} { b , v , w } violates; otherwise both M a w M_{aw} M a w and M b w M_{bw} M b w are less than R R R , so { a , b , w } \{a,b,w\} { a , b , w } violates. If v = a v = a v = a , either { c , v , w } \{c,v,w\} { c , v , w } or { c , b , w } \{c,b,w\} { c , b , w } violates; otherwise the first gives M c w < R M_{cw} < R M c w < R , the second gives M b w < R M_{bw} < R M b w < R , and { v , b , w } \{v,b,w\} { v , b , w } violates. The case v = b v = b v = b is symmetric.
Let r x = ∣ { T ∈ T : x ∈ T } ∣ r_x = |\{T \in\mathcal{T}: x \in T\}| r x = ∣ { T ∈ T : x ∈ T } ∣ . Using ∑ x r x = 3 m \sum_x r_x = 3m ∑ x r x = 3 m and Cauchy–Schwarz, the number I I I of unordered intersecting pairs is
I = ∑ x ( r x 2 ) ≥ 1 2 ( 9 m 2 n − 3 m ) . I = \sum_x \binom{r_x}{2} \ge\frac{1}{2}\left(\frac{9m^2}{n} - 3m\right). I = x ∑ ( 2 r x ) ≥ 2 1 ( n 9 m 2 − 3 m ) .
If m < n m < n m < n , then ∣ V ( M ) ∣ ≥ m ≥ m 2 / n |\mathcal{V}(M)| \ge m \ge m^2/n ∣ V ( M ) ∣ ≥ m ≥ m 2 / n . If m ≥ n m \ge n m ≥ n , then I ≥ 3 m 2 / n I \ge3m^2/n I ≥ 3 m 2 / n . Choose one mixed violation Q Q Q for every intersecting pair. A fixed Q Q Q is selected at most 27 times: choose its edge belonging to T T T in at most three ways (which determines T T T ), choose v ∈ T v \in T v ∈ T in at most three ways, and choose w ∈ Q w \in Q w ∈ Q in at most three ways (where the edge v w vw v w determines T ′ T' T ′ by edge-disjointness). Hence ∣ V ( M ) ∣ ≥ I / 27 ≥ m 2 / ( 9 n ) |\mathcal{V}(M)| \ge I/27 \ge m^2/(9n) ∣ V ( M ) ∣ ≥ I /27 ≥ m 2 / ( 9 n ) when m ≥ n m \ge n m ≥ n . The claimed bound ∣ V ( M ) ∣ ≥ m 2 / ( 100 n ) |\mathcal{V}(M)| \ge m^2/(100n) ∣ V ( M ) ∣ ≥ m 2 / ( 100 n ) follows in all cases.
If m ≥ α n 2 m \ge\alpha n^2 m ≥ α n 2 , then viol ( M ) ≥ α 2 n 3 / 100 ( n 3 ) ≥ 3 50 α 2 \operatorname{viol}(M) \ge\frac{\alpha^2n^3/100}{\binom{n}{3}} \ge\frac{3}{50}\alpha^2 viol ( M ) ≥ ( 3 n ) α 2 n 3 /100 ≥ 50 3 α 2 .
To extend this argument to tree pseudometrics, we use the classical correspondence between tree metrics and ultrametrics via the rooted Gromov product (or Farris transform) [18 , 24 ] .
Lemma 4.2. Let n ≥ 4 n \ge4 n ≥ 4 and fix o ∈ [ n ] o \in[n] o ∈ [ n ] . For i ≠ o i \ne o i = o , put h i = D o i h_i = D_{oi} h i = D o i , and for distinct i , j ≠ o i,j \ne o i , j = o , put s i j = ( h i + h j − D i j ) / 2 s_{ij} = (h_i + h_j - D_{ij})/2 s ij = ( h i + h j − D ij ) /2 . Then D ∈ T n D \in\mathcal{T}_n D ∈ T n if and only if 0 ≤ s i j ≤ min { h i , h j } 0 \le s_{ij} \le\min\{h_i,h_j\} 0 ≤ s ij ≤ min { h i , h j } for every such pair, and the minimum of s i j , s i k , s j k s_{ij},s_{ik},s_{jk} s ij , s ik , s j k is attained at least twice for every triple of distinct labels outside o o o .
Proof. The triangle inequalities involving o o o are equivalent to the bounds 0 ≤ s i j ≤ min { h i , h j } 0 \le s_{ij} \le\min\{h_i,h_j\} 0 ≤ s ij ≤ min { h i , h j } . The four-point condition on { o , i , j , k } \{o,i,j,k\} { o , i , j , k } is equivalent to the minimum condition, since D i j + D o k = h i + h j + h k − 2 s i j D_{ij} + D_{ok} = h_i + h_j + h_k - 2s_{ij} D ij + D o k = h i + h j + h k − 2 s ij .
Conversely, the bounds give all triangle inequalities involving o o o . For a triangle outside o o o , we have D i j + D i k − D j k = 2 h i + 2 ( s j k − s i j − s i k ) ≥ 2 ( h i − max { s i j , s i k } ) ≥ 0 D_{ij} + D_{ik} - D_{jk} = 2h_i + 2(s_{jk} - s_{ij} - s_{ik}) \ge2(h_i - \max\{s_{ij},s_{ik}\}) \ge0 D ij + D ik − D j k = 2 h i + 2 ( s j k − s ij − s ik ) ≥ 2 ( h i − max { s ij , s ik }) ≥ 0 .
Choose C ≥ max i ≠ j s i j C \ge\max_{i \ne j} s_{ij} C ≥ max i = j s ij and set u i j = C − s i j u_{ij} = C - s_{ij} u ij = C − s ij off the diagonal and u i i = 0 u_{ii} = 0 u ii = 0 . The minimum condition makes u u u a nonnegative ultrametric, which satisfies the four-point condition. To see this directly on four labels, let R R R be their maximum distance and partition them by the relation u i j < R u_{ij} < R u ij < R . For partition types 2 + 2 2+2 2 + 2 , 2 + 1 + 1 2+1+1 2 + 1 + 1 , or 1 + 1 + 1 + 1 1+1+1+1 1 + 1 + 1 + 1 , two opposite-edge sums equal 2 R 2R 2 R and the third is at most 2 R 2R 2 R . For type 3 + 1 3+1 3 + 1 , the three opposite-edge sums are R R R plus the three distances of an ultrametric triple, whose maximum is attained at least twice. The all-zero case is immediate.
For a quartet outside o o o , the opposite-edge sums of D D D are obtained from those of u u u by multiplication by 2 and addition of the common constant h i + h j + h k + h l − 4 C h_i + h_j + h_k + h_l - 4C h i + h j + h k + h l − 4 C . Thus D D D satisfies the four-point condition on these quartets as well. The triangle inequalities handle repeated indices, so Buneman’s characterization applies.
Lemma 4.3. Let X X X have size N ≥ 3 N \ge3 N ≥ 3 , let h i ≥ 0 h_i \ge0 h i ≥ 0 , and let s i j s_{ij} s ij be a symmetric assignment on distinct pairs of X X X . Call a triple rooted-bad if some pair violates 0 ≤ s i j ≤ min { h i , h j } 0 \le s_{ij} \le\min\{h_i,h_j\} 0 ≤ s ij ≤ min { h i , h j } , or if its minimum s s s -value is attained uniquely. If an edge-disjoint family contains at least β N 2 \beta N^2 β N 2 rooted-bad triples, where β > 0 \beta> 0 β > 0 , then the density of rooted-bad triples is at least min { 1 , 3 β 2 / 200 } \min\{1,3\beta^2/200\} min { 1 , 3 β 2 /200 } .
Proof. Let the family have size m ≥ β N 2 m \ge\beta N^2 m ≥ β N 2 . If at least m / 2 m/2 m /2 members contain a bounds violation, choose one such edge from each. These edges are distinct, and counting their incidences with triples gives at least ( m / 2 ) ( N − 2 ) / 3 (m/2)(N-2)/3 ( m /2 ) ( N − 2 ) /3 rooted-bad triples, of density at least m N ( N − 1 ) ≥ β \frac{m}{N(N-1)} \ge\beta N ( N − 1 ) m ≥ β . Otherwise, at least m / 2 m/2 m /2 members satisfy the bounds and have a unique minimum. Choose C ≥ max i ≠ j s i j C \ge\max_{i\ne j} s_{ij} C ≥ max i = j s ij and put u i j = C − s i j u_{ij}=C-s_{ij} u ij = C − s ij . These triples form an edge-disjoint family of ultrametric violations. Lemma 4.1 , in its counting form, gives at least ( m / 2 ) 2 100 N \frac{(m/2)^2}{100N} 100 N ( m /2 ) 2 such violations, of density at least 3 β 2 / 200 3\beta^2/200 3 β 2 /200 . Since a feasible edge-disjoint triple packing has β ≤ 1 / 6 \beta\le1/6 β ≤ 1/6 , the first case also satisfies the stated bound.
Lemma 4.4 (Packing amplification for tree pseudometrics). For every α > 0 \alpha>0 α > 0 ,
Δ t r e e ( α ) ≥ min { 1 1820 , 3 α 2 1600 } . \Delta_{\mathrm{tree}}(\alpha)\ge\min\left\{\frac{1}{1820},\frac{3\alpha^2}{1600}\right\}. Δ tree ( α ) ≥ min { 1820 1 , 1600 3 α 2 } .
Proof. Let M ∈ D n M\in\mathcal{D}_n M ∈ D n , and let Q \mathcal{Q} Q be an edge-disjoint family of m ≥ α n 2 m\ge\alpha n^2 m ≥ α n 2 violating quartets. For a root o o o , let r o = ∣ { Q ∈ Q : o ∈ Q } ∣ r_o=\lvert\{Q\in\mathcal{Q}:o\in Q\}\rvert r o = ∣{ Q ∈ Q : o ∈ Q }∣ . Since ∑ o r o = 4 m \sum_o r_o=4m ∑ o r o = 4 m , at most seven roots have r o > m / 2 r_o>m/2 r o > m /2 . For n ≥ 16 n\ge16 n ≥ 16 , at least n / 2 n/2 n /2 roots are good, meaning r o ≤ m / 2 r_o\le m/2 r o ≤ m /2 .
Fix a good root o o o and form its rooted data. By Lemma 4.2 , every Q ∈ Q Q\in\mathcal{Q} Q ∈ Q not containing o o o contains a rooted-bad triple. Choose one such triple from each Q Q Q . These triples are edge-disjoint and number at least m / 2 m/2 m /2 , so their packing density on N = n − 1 N=n-1 N = n − 1 vertices is at least α / 2 \alpha/2 α /2 . Lemma 4.3 gives a rooted-bad triple density of at least min { 1 , 3 α 2 / 800 } \min\{1,3\alpha^2/800\} min { 1 , 3 α 2 /800 } . Each rooted-bad triple, together with o o o , forms a violating quartet. Summing over good roots and dividing by the maximum multiplicity four gives
viol ( M ) ≥ ( n / 8 ) ( n − 1 3 ) ( n 4 ) min { 1 , 3 α 2 800 } = min { 1 2 , 3 α 2 1600 } . \operatorname{viol}(M)\ge\frac{(n/8)\binom{n-1}{3}}{\binom{n}{4}}\min\left\{1,\frac{3\alpha^2}{800}\right\}=\min\left\{\frac{1}{2},\frac{3\alpha^2}{1600}\right\}. viol ( M ) ≥ ( 4 n ) ( n /8 ) ( 3 n − 1 ) min { 1 , 800 3 α 2 } = min { 2 1 , 1600 3 α 2 } .
For 4 ≤ n < 16 4\le n<16 4 ≤ n < 16 , any violation gives density at least 1 / 1820 1/1820 1/1820 . Taking the infimum completes the proof.
Euclidean pseudometrics and edgewise restrictions
To bound the distance to E n ( d ) \mathcal{E}^{(d)}_n E n ( d ) in terms of ( d + 3 ) (d+3) ( d + 3 ) -point violations, we adapt the affine anchor repair method of Parnas and Ron [31 Section 6] (see also Krauthgamer and Sasson [27 ] and Onak [30 ] ). In their analysis [31 Fact 2 and Lemma 6.1] , given an anchor set U U U realized with affine dimension s ≤ d s\le d s ≤ d , vertices whose distances to U U U admit a realization in the same s s s -dimensional affine span (strongly consistent points ) have uniquely determined coordinates. A global Euclidean pseudometric is then obtained by placing those vertices at their forced coordinates and collapsing the remaining exceptional vertices. Whereas [31 , 27 ] locate a suitable dimension s ≤ d s\le d s ≤ d via adaptive or iterative phases that increment the dimension, we select a dimension level s s s nonadaptively via a pigeonhole threshold on the ( d + 3 ) (d+3) ( d + 3 ) -set dimension densities.
Proposition 4.5 (Euclidean repair and hitting-set bound). Let n ≥ 2 d + 8 n\ge2d+8 n ≥ 2 d + 8 and 0 < viol ( D ) < min { 1 2 , ( 2 d + 2 ) − ( d + 2 ) } 0<\operatorname{viol}(D)<\min\left\{\frac{1}{2},(2d+2)^{-(d+2)}\right\} 0 < viol ( D ) < min { 2 1 , ( 2 d + 2 ) − ( d + 2 ) } with respect to Φ E u c ( d ) \Phi_{\mathrm{Euc}}^{(d)} Φ Euc ( d ) . Put C d = 3 ( d + 1 ) ( d + 5 ) C_d=3(d+1)^{(d+5)} C d = 3 ( d + 1 ) ( d + 5 ) . There exists B ∈ E n ( d ) B\in\mathcal{E}_n^{(d)} B ∈ E n ( d ) differing from D D D on at most 1 2 C d n 2 viol ( D ) 1 / ( d + 2 ) \frac{1}{2}C_dn^2\operatorname{viol}(D)^{1/(d+2)} 2 1 C d n 2 viol ( D ) 1/ ( d + 2 ) edges. In particular,
dist n ( D , E n ( d ) ) ≤ C d viol ( D ) 1 / ( d + 2 ) and 2 v ( D ) n 2 ≤ C d viol ( D ) 1 / ( d + 2 ) . \operatorname{dist}_n(D,\mathcal{E}_n^{(d)})\le C_d\operatorname{viol}(D)^{1/(d+2)}
\qquad\text{and}\qquad
\frac{2\operatorname{v}(D)}{n^2}\le C_d\operatorname{viol}(D)^{1/(d+2)}. dist n ( D , E n ( d ) ) ≤ C d viol ( D ) 1/ ( d + 2 ) and n 2 2 v ( D ) ≤ C d viol ( D ) 1/ ( d + 2 ) .
Proof. Let C j \mathcal{C}_j C j be the family of valid ( d + 3 ) (d+3) ( d + 3 ) -sets of affine dimension j j j , and put p j = ∣ C j ∣ / ( n d + 3 ) p_j=\lvert\mathcal{C}_j\rvert/\binom{n}{d+3} p j = ∣ C j ∣ / ( d + 3 n ) , so that ∑ j = 0 d p j = 1 − viol ( D ) \sum_{j=0}^{d}p_j=1-\operatorname{viol}(D) ∑ j = 0 d p j = 1 − viol ( D ) . By averaging, some p j p_j p j satisfies
p j ≥ 1 − viol ( D ) d + 1 ≥ 1 2 d + 2 > viol ( D ) 1 / ( d + 2 ) ≥ viol ( D ) ( j + 1 ) / ( d + 2 ) . p_j\ge\frac{1-\operatorname{viol}(D)}{d+1}\ge\frac{1}{2d+2}>\operatorname{viol}(D)^{1/(d+2)}\ge\operatorname{viol}(D)^{(j+1)/(d+2)}. p j ≥ d + 1 1 − viol ( D ) ≥ 2 d + 2 1 > viol ( D ) 1/ ( d + 2 ) ≥ viol ( D ) ( j + 1 ) / ( d + 2 ) .
Choose s = max { j : p j ≥ viol ( D ) ( j + 1 ) / ( d + 2 ) } s=\max\{j:p_j\ge\operatorname{viol}(D)^{(j+1)/(d+2)}\} s = max { j : p j ≥ viol ( D ) ( j + 1 ) / ( d + 2 ) } and let F = V ( D ) ∪ ⋃ j > s C j \mathcal{F}=\mathcal{V}(D)\cup\bigcup_{j>s}\mathcal{C}_j F = V ( D ) ∪ ⋃ j > s C j , which has size
∣ F ∣ = ( n d + 3 ) ( viol ( D ) + ∑ j > s p j ) . |\mathcal{F}|=\binom{n}{d+3}\left(\operatorname{viol}(D)+\sum_{j>s}p_j\right). ∣ F ∣ = ( d + 3 n ) ( viol ( D ) + j > s ∑ p j ) .
By the maximality of s s s and the lower bound on p s p_s p s ,
∣ F ∣ ≤ ( n d + 3 ) ( d − s + 1 ) viol ( D ) ( s + 2 ) / ( d + 2 ) ≤ p s ( n d + 3 ) ( d + 1 ) viol ( D ) 1 / ( d + 2 ) . |\mathcal{F}|\le\binom{n}{d+3}(d-s+1)\operatorname{viol}(D)^{(s+2)/(d+2)}
\le p_s\binom{n}{d+3}(d+1)\operatorname{viol}(D)^{1/(d+2)}. ∣ F ∣ ≤ ( d + 3 n ) ( d − s + 1 ) viol ( D ) ( s + 2 ) / ( d + 2 ) ≤ p s ( d + 3 n ) ( d + 1 ) viol ( D ) 1/ ( d + 2 ) .
Choose an ordered ( d + 5 ) (d+5) ( d + 5 ) -tuple of distinct vertices ( c 1 , … , c d + 3 , u , v ) (c_1,\ldots,c_{d+3},u,v) ( c 1 , … , c d + 3 , u , v ) uniformly, write C = { c 1 , … , c d + 3 } C=\{c_1,\ldots,c_{d+3}\} C = { c 1 , … , c d + 3 } , and condition on C ∈ C s C\in\mathcal{C}_s C ∈ C s . Every fixed ( d + 3 ) (d+3) ( d + 3 ) -set of positions is unconditionally uniform among all ( d + 3 ) (d+3) ( d + 3 ) -sets, so its conditional probability of belonging to F \mathcal{F} F is at most ∣ F ∣ / ( p s ( n d + 3 ) ) |\mathcal{F}|/\left(p_s\binom{n}{d+3}\right) ∣ F ∣/ ( p s ( d + 3 n ) ) . A union bound and averaging give a fixed C ∈ C s C\in\mathcal{C}_s C ∈ C s for which the number b b b of bad pairs { u , v } ⊆ [ n ] ∖ C \{u,v\}\subseteq[n]\setminus C { u , v } ⊆ [ n ] ∖ C satisfying ( C ∪ { u , v } d + 3 ) ∩ F ≠ ∅ \binom{C\cup\{u,v\}}{d+3}\cap\mathcal{F}\ne\varnothing ( d + 3 C ∪ { u , v } ) ∩ F = ∅ is at most
b ≤ n 2 2 ∣ F ∣ p s ( n d + 3 ) . b\leq\frac{n^2}{2}\frac{|\mathcal{F}|}{p_s\binom{n}{d+3}}. b ≤ 2 n 2 p s ( d + 3 n ) ∣ F ∣ .
Call the remaining pairs in [ n ] ∖ C [n]\setminus C [ n ] ∖ C good.
Fix a realization z C z_C z C of D [ C ] D[C] D [ C ] , let A A A be its s s s -dimensional affine span, and choose an affine basis from C C C . If { u , v } \{u,v\} { u , v } is good, every ( d + 3 ) (d+3) ( d + 3 ) -subset of C ∪ { u , v } C\cup\{u,v\} C ∪ { u , v } is realizable, so Lemma 2.7 gives a realization of C ∪ { u , v } C\cup\{u,v\} C ∪ { u , v } . After aligning C C C , both new points must lie in A A A ; otherwise an affinely independent subset of dimension greater than s s s , padded to a ( d + 3 ) (d+3) ( d + 3 ) -set, would belong to F \mathcal{F} F . By Lemma 2.6 , their positions in A A A are uniquely determined by the affine basis.
Let X X X be the set of vertices outside C C C incident to at least one good pair. Each u ∈ X u\in X u ∈ X therefore has a well-defined coordinate x u ∈ A x_u\in A x u ∈ A agreeing with all its prescribed distances to C C C , and every good pair satisfies D u v = ∥ x u − x v ∥ 2 D_{uv}=\lVert x_u-x_v\rVert_2 D uv = ∥ x u − x v ∥ 2 . Let I = ( [ n ] ∖ C ) ∖ X I=([n]\setminus C)\setminus X I = ([ n ] ∖ C ) ∖ X . Every pair incident to I I I inside [ n ] ∖ C [n]\setminus C [ n ] ∖ C is bad, so ∣ I ∣ ( n − d − 4 ) ≤ 2 b |I|(n-d-4)\leq2b ∣ I ∣ ( n − d − 4 ) ≤ 2 b . Since n ≥ 2 d + 8 n\geq2d+8 n ≥ 2 d + 8 , this implies ∣ I ∣ ≤ 4 b / n |I|\leq4b/n ∣ I ∣ ≤ 4 b / n .
Assign the points of C C C their fixed realization, assign u ∈ X u\in X u ∈ X to x u x_u x u , and collapse every vertex of I I I to a single fixed basis point. The resulting Euclidean pseudometric B B B differs from D D D only on bad pairs outside C C C and on edges between C C C and I I I , so
∣ { e : B e ≠ D e } ∣ ≤ b + ( d + 3 ) ∣ I ∣ ≤ 3 b ≤ 1 2 C d n 2 viol ( D ) 1 / ( d + 2 ) . |\{e:B_e\ne D_e\}|\leq b+(d+3)|I|\leq3b\leq\frac{1}{2}C_d n^2\operatorname{viol}(D)^{1/(d+2)}. ∣ { e : B e = D e } ∣ ≤ b + ( d + 3 ) ∣ I ∣ ≤ 3 b ≤ 2 1 C d n 2 viol ( D ) 1/ ( d + 2 ) .
The normalized repair bound follows. Since every original violation contains a changed edge, edge-disjoint violations require distinct changed edges, yielding the packing bound.
Lemma 4.6 (Packing amplification for Euclidean pseudometrics). Put C d = 3 ( d + 1 ) ( d + 5 2 ) C_d=3(d+1)\binom{d+5}{2} C d = 3 ( d + 1 ) ( 2 d + 5 ) and δ d = min { 1 2 , ( 2 d + 2 ) − ( d + 2 ) , ( ( 2 d + 7 d + 3 ) ) − 1 } \delta_d=\min\left\{\frac{1}{2},(2d+2)^{-(d+2)},\left(\binom{2d+7}{d+3}\right)^{-1}\right\} δ d = min { 2 1 , ( 2 d + 2 ) − ( d + 2 ) , ( ( d + 3 2 d + 7 ) ) − 1 } . For every α > 0 \alpha>0 α > 0 ,
Δ E u c ( d ) ( α ) ≥ min { δ d , ( 2 α C d ) d + 2 } . \Delta_{\mathrm{Euc}}^{(d)}(\alpha)\geq\min\left\{\delta_d,\left(\frac{2\alpha}{C_d}\right)^{d+2}\right\}. Δ Euc ( d ) ( α ) ≥ min { δ d , ( C d 2 α ) d + 2 } .
Proof. Suppose ν ( D ) ≥ α n 2 \nu(D)\geq\alpha n^2 ν ( D ) ≥ α n 2 . If viol ( D ) ≥ δ d \operatorname{viol}(D)\geq\delta_d viol ( D ) ≥ δ d , there is nothing to prove. Otherwise, positivity of ν ( D ) \nu(D) ν ( D ) gives viol ( D ) ≥ ( n d + 3 ) − 1 \operatorname{viol}(D)\geq\binom{n}{d+3}^{-1} viol ( D ) ≥ ( d + 3 n ) − 1 , and the definition of δ d \delta_d δ d forces n ≥ 2 d + 8 n\geq2d+8 n ≥ 2 d + 8 . Proposition 4.5 then gives 2 α ≤ C d viol ( D ) 1 / ( d + 2 ) 2\alpha\leq C_d\operatorname{viol}(D)^{1/(d+2)} 2 α ≤ C d viol ( D ) 1/ ( d + 2 ) . Taking the infimum completes the proof.
Corollary 4.7 (Quantitative Euclidean removal). For every ϵ > 0 \epsilon>0 ϵ > 0 , with C d C_d C d and δ d \delta_d δ d as in Lemma 4.6 , we have ρ E u c ( d ) ( ϵ ) ≥ min { δ d , ( ϵ / C d ) d + 2 } \rho_{\mathrm{Euc}}^{(d)}(\epsilon)\geq\min\{\delta_d,(\epsilon/C_d)^{d+2}\} ρ Euc ( d ) ( ϵ ) ≥ min { δ d , ( ϵ / C d ) d + 2 } .
Proof. An ϵ \epsilon ϵ -far input has positive violation density. If viol ( D ) < δ d \operatorname{viol}(D)<\delta_d viol ( D ) < δ d , then n ≥ 2 d + 8 n\geq2d+8 n ≥ 2 d + 8 as in Lemma 4.6 , and Proposition 4.5 implies ϵ < C d viol ( D ) 1 / ( d + 2 ) \epsilon<C_d\operatorname{viol}(D)^{1/(d+2)} ϵ < C d viol ( D ) 1/ ( d + 2 ) . Taking the infimum proves the claim.
Proposition 4.8. Let Γ ⊂ Λ \Gamma\subset\Lambda Γ ⊂ Λ and Φ ′ = Φ ∩ Γ ( [ k ] 2 ) \Phi'=\Phi\cap\Gamma^{\binom{[k]}{2}} Φ ′ = Φ ∩ Γ ( 2 [ k ] ) , regarding both predicates on the ambient value set Λ \Lambda Λ . Then for every α > 0 \alpha>0 α > 0 ,
Δ Φ ′ ( α ) ≥ sup 0 < t < 1 min { 2 ( 1 − t ) α , Δ Φ ( t α ) } ≥ min { α , Δ Φ ( α / 2 ) } . \Delta_{\Phi'}(\alpha)\geq\sup_{0<t<1}\min\{2(1-t)\alpha,\Delta_{\Phi}(t\alpha)\}\geq\min\{\alpha,\Delta_{\Phi}(\alpha/2)\}. Δ Φ ′ ( α ) ≥ 0 < t < 1 sup min { 2 ( 1 − t ) α , Δ Φ ( t α )} ≥ min { α , Δ Φ ( α /2 )} .
Thus packing amplification passes to edgewise restrictions. The assertion concerns violation sets and remains meaningful even when a restricted valid family is empty at some orders.
Proof. Fix an edge-disjoint family S S S of Φ ′ \Phi' Φ ′ -violations with ∣ S ∣ ≥ α n 2 |S|\geq\alpha n^2 ∣ S ∣ ≥ α n 2 . For any t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) , either at least t α n 2 t\alpha n^2 t α n 2 members violate Φ \Phi Φ , or at least ( 1 − t ) α n 2 (1-t)\alpha n^2 ( 1 − t ) α n 2 members satisfy Φ \Phi Φ but contain a value outside Γ \Gamma Γ . In the first case, viol Φ ′ ( D ) ≥ viol Φ ( D ) ≥ Δ Φ ( t α ) \operatorname{viol}_{\Phi'}(D) \ge\operatorname{viol}_{\Phi}(D) \ge\Delta_{\Phi}(t\alpha) viol Φ ′ ( D ) ≥ viol Φ ( D ) ≥ Δ Φ ( t α ) . In the second, edge-disjointness gives a set Z Z Z of at least ( 1 − t ) α n 2 (1-t)\alpha n^2 ( 1 − t ) α n 2 distinct edges with values outside Γ \Gamma Γ . Counting incidences gives ∣ V Φ ′ ( D ) ∣ ( n 2 ) ≥ ∣ Z ∣ ( k 2 ) |V_{\Phi'}(D)|\binom{n}{2} \ge|Z|\binom{k}{2} ∣ V Φ ′ ( D ) ∣ ( 2 n ) ≥ ∣ Z ∣ ( 2 k ) , and hence viol Φ ′ ( D ) ≥ 2 ∣ Z ∣ n ( n − 1 ) ≥ 2 ( 1 − t ) α \operatorname{viol}_{\Phi'}(D) \ge\frac{2|Z|}{n(n-1)} \ge2(1-t)\alpha viol Φ ′ ( D ) ≥ n ( n − 1 ) 2∣ Z ∣ ≥ 2 ( 1 − t ) α . Taking the infimum over D D D and the supremum over t t t yields the first inequality; setting t = 1 / 2 t=1/2 t = 1/2 gives the second.
Corollary 4.9 (Packing amplification for strict geometric families). On Λ = R ≥ 0 \Lambda= \mathbb{R}_{\ge0} Λ = R ≥ 0 or Λ = ( 0 , ∞ ) \Lambda= (0,\infty) Λ = ( 0 , ∞ ) , the strict predicates Φ u l t + \Phi_{\mathrm{ult}}^{+} Φ ult + , Φ t r e e + \Phi_{\mathrm{tree}}^{+} Φ tree + , and Φ E u c ( d ) , + \Phi_{\mathrm{Euc}}^{(d),+} Φ Euc ( d ) , + all satisfy packing amplification.
Proof. Apply Proposition 4.8 with Γ = ( 0 , ∞ ) \Gamma= (0,\infty) Γ = ( 0 , ∞ ) to Lemmas 4.1, 4.4, and 4.6. Restricting the infimum to positive inputs can only increase the modulus.
Robust metric faces and the packing obstruction for general metrics
Unlike the geometric families above, general triangle inequalities admit dense edge-disjoint families of tight triangles with every other slack strictly positive. In contrast to tripartite graph constructions for triangle-freeness (such as the Behrend graph construction of [3 Section 5.1] , which also underlies the metric testing lower bound in [9 Section 4] ) that restrict edge steps to a progression-free set and incur an n − o ( 1 ) n^{-o(1)} n − o ( 1 ) density loss, a metric face on a complete graph only requires unselected triangles to have strictly positive slack. The quadratic potential λ ( i + j − k ) 2 \lambda(i+j-k)^2 λ ( i + j − k ) 2 in Lemma 4.10 below (and its midpoint variant in Lemma 6.9) exploits this real-valued margin to achieve full Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) edge-disjoint packing density without progression-free sets; § 7 later combines these same faces with signed noise.
Lemma 4.10 (Robust metric face). Fix C > 2 C > 2 C > 2 . There are a rational C 0 C_0 C 0 with 2 < C 0 < min { C , 3 } 2 < C_0 < \min\{C,3\} 2 < C 0 < min { C , 3 } and an absolute constant β = 1 / 20 \beta= 1/20 β = 1/20 such that, for all sufficiently large n n n , there exist a rational metric A ∈ [ 1 , C 0 ] ( n 2 ) A \in[1,C_0]^{\binom{n}{2}} A ∈ [ 1 , C 0 ] ( 2 n ) and an edge-disjoint family H \mathcal{H} H of at least β n 2 \beta n^2 β n 2 triangles satisfying:
each member of H \mathcal{H} H has one designated tight triangle inequality, and these are the only tight triangle inequalities of A A A ;
every other triangle inequality has slack at least n − 3 n^{-3} n − 3 , and every entry has distance at least n − 3 n^{-3} n − 3 from the endpoints of [ 1 , C 0 ] [1,C_0] [ 1 , C 0 ] ;
every entry has an O C ( log n ) O_C(\log n) O C ( log n ) -bit rational representation.
Proof. Choose a positive rational ρ < min { ( C − 2 ) / 10 , 1 / 100 } \rho< \min\{(C-2)/10,1/100\} ρ < min {( C − 2 ) /10 , 1/100 } , and set C 0 = 2 + 10 ρ C_0 = 2 + 10\rho C 0 = 2 + 10 ρ and b = 1 + 4 ρ b = 1 + 4\rho b = 1 + 4 ρ . First consider 4 m − 1 4m-1 4 m − 1 vertices partitioned into X = { x i : ∣ i ∣ ≤ m − 1 } X = \{x_i : |i| \le m-1\} X = { x i : ∣ i ∣ ≤ m − 1 } , Y = { y j : j ∈ [ m ] } Y = \{y_j : j \in[m]\} Y = { y j : j ∈ [ m ]} , and Z = { z k : k ∈ [ m ] } Z = \{z_k : k \in[m]\} Z = { z k : k ∈ [ m ]} . Put λ = ρ / m 2 \lambda= \rho/m^2 λ = ρ / m 2 , assign value 3 / 2 3/2 3/2 within each part, and set
A ( x i , y j ) = b + λ ( i 2 + 2 i j ) , A ( y j , z k ) = b + λ ( j 2 − 2 j k ) , A ( x i , z k ) = 2 b + λ ( 2 i k − k 2 ) . A(x_i,y_j) = b + \lambda(i^2 + 2ij), \qquad A(y_j,z_k) = b + \lambda(j^2 - 2jk), \qquad A(x_i,z_k) = 2b + \lambda(2ik-k^2). A ( x i , y j ) = b + λ ( i 2 + 2 ij ) , A ( y j , z k ) = b + λ ( j 2 − 2 j k ) , A ( x i , z k ) = 2 b + λ ( 2 ik − k 2 ) .
Since 2 i k − k 2 = i 2 − ( i − k ) 2 < m 2 2ik-k^2 = i^2 - (i-k)^2 < m^2 2 ik − k 2 = i 2 − ( i − k ) 2 < m 2 , the index ranges imply A ( x i , y j ) ∈ [ 1 + 3 ρ , 1 + 7 ρ ] A(x_i,y_j) \in[1+3\rho,1+7\rho] A ( x i , y j ) ∈ [ 1 + 3 ρ , 1 + 7 ρ ] , A ( y j , z k ) ∈ [ 1 + 3 ρ , 1 + 5 ρ ] A(y_j,z_k) \in[1+3\rho,1+5\rho] A ( y j , z k ) ∈ [ 1 + 3 ρ , 1 + 5 ρ ] , and A ( x i , z k ) ∈ [ 2 + 5 ρ , 2 + 9 ρ ] A(x_i,z_k) \in[2+5\rho,2+9\rho] A ( x i , z k ) ∈ [ 2 + 5 ρ , 2 + 9 ρ ] .
For a triangle meeting all three parts, the slack on ( x i , z k ) (x_i,z_k) ( x i , z k ) is
A ( x i , y j ) + A ( y j , z k ) − A ( x i , z k ) = λ ( i + j − k ) 2 . A(x_i,y_j) + A(y_j,z_k) - A(x_i,z_k) = \lambda(i+j-k)^2. A ( x i , y j ) + A ( y j , z k ) − A ( x i , z k ) = λ ( i + j − k ) 2 .
while the other two slacks are at least 2 + ρ 2+\rho 2 + ρ . If two vertices lie in one part, their edge has value 3 / 2 3/2 3/2 and the two cross-part entries differ by at most 4 ρ 4\rho 4 ρ , giving slacks at least 3 / 2 − 4 ρ 3/2-4\rho 3/2 − 4 ρ and 2 ( 1 + 3 ρ ) − 3 / 2 2(1+3\rho)-3/2 2 ( 1 + 3 ρ ) − 3/2 . Triangles within a part are equilateral and hence strict. Thus the tight triangles are precisely H = { { x k − j , y j , z k } : j , k ∈ [ m ] } \mathcal{H} = \{\{x_{k-j}, y_j, z_k\}: j, k \in[m]\} H = {{ x k − j , y j , z k } : j , k ∈ [ m ]} , with designated long edge x k − j z k x_{k-j}z_k x k − j z k . Any two vertices in different parts determine at most one third vertex in H \mathcal{H} H , so H \mathcal{H} H is edge-disjoint and has size m 2 m^2 m 2 .
For arbitrary sufficiently large n n n , take m = ⌊ ( n + 1 ) / 4 ⌋ m = \lfloor(n + 1)/4\rfloor m = ⌊( n + 1 ) /4 ⌋ and add the at most three remaining vertices at distance 3 / 2 3/2 3/2 from every other vertex; any triangle meeting a new vertex and an old edge of value a a a has positive slacks a , a , 3 − a a, a, 3-a a , a , 3 − a . The strict slacks are at least min { ρ / m 2 , 1 / 2 , 3 − C 0 } \min\{\rho/m^2, 1/2, 3-C_0\} min { ρ / m 2 , 1/2 , 3 − C 0 } and the endpoint margins are at least ρ \rho ρ , both exceeding n − 3 n^{-3} n − 3 for large n n n . Finally, m 2 / n 2 → 1 / 16 > β m^2/n^2 \to1/16 > \beta m 2 / n 2 → 1/16 > β , and the entries have logarithmic bit complexity.
Theorem 4.11 (Packing obstruction for general metrics). For Λ = [ 1 , C ] \Lambda= [1,C] Λ = [ 1 , C ] with C > 2 C > 2 C > 2 , the metric predicate admits a packing obstruction: for β = 1 / 20 \beta= 1/20 β = 1/20 ,
Δ ( β ) = 0 and ρ ( ϵ ) = 0 ( 0 < ϵ < 2 β ) . \Delta(\beta) = 0 \qquad\text{and} \qquad\rho(\epsilon) = 0 \qquad(0 < \epsilon< 2\beta). Δ ( β ) = 0 and ρ ( ϵ ) = 0 ( 0 < ϵ < 2 β ) . The same holds for positive-valued general metrics on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) and nonnegative-valued general pseudometrics on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) . Consequently, none of these families has a constant-query one-sided tester.
Proof. Take ( A , H ) (A,\mathcal{H}) ( A , H ) from Lemma 4.10 , with h = ∣ H ∣ ≥ β n 2 h = |\mathcal{H}| \ge\beta n^2 h = ∣ H ∣ ≥ β n 2 , and add η = n − 4 \eta= n^{-4} η = n − 4 to the designated long edge of each member of H \mathcal{H} H . Each selected triangle now has designated slack − η -\eta − η . Every formerly strict slack changes by at most 3 η < n − 3 3\eta< n^{-3} 3 η < n − 3 , and the endpoint margins keep all entries in [ 1 , C 0 ] [1,C_0] [ 1 , C 0 ] . Thus the resulting matrix D D D has V ( D ) = H \mathcal{V}(D) = \mathcal{H} V ( D ) = H , which gives ν ( D ) = h ≥ β n 2 \nu(D) = h \ge\beta n^2 ν ( D ) = h ≥ β n 2 and viol ( D ) = h / ( n 3 ) = O ( n − 1 ) → 0 \operatorname{viol}(D) = h/\binom{n}{3} = O(n^{-1}) \to0 viol ( D ) = h / ( 3 n ) = O ( n − 1 ) → 0 .
Every metric or pseudometric repair changes at least one edge in each member of H \mathcal{H} H , while resetting the h h h long edges restores A A A . Hence dist n ( D , M n [ 1 , C ] ) = dist n ( D , M n ) = dist n ( D , M ‾ n ) = 2 h / n 2 ≥ 2 β \operatorname{dist}_n(D,\mathcal{M}_n[1,C]) = \operatorname{dist}_n(D,\mathcal{M}_n) = \operatorname{dist}_n(D,\overline{\mathcal{M}}_n) = 2h/n^2 \ge2\beta dist n ( D , M n [ 1 , C ]) = dist n ( D , M n ) = dist n ( D , M n ) = 2 h / n 2 ≥ 2 β . The removal claims follow immediately, and Theorem 3.4 together with extendability rules out constant-query one-sided testers.
Completion stability
We establish completion stability for our principal pseudometric and metric families and identify the completion obstructions created by injective geometric realization. We first prove linear completion stability for ultrametrics (Lemma 5.2 ) and tree pseudometrics (Lemma 5.5) via a recursive graph separation scheme, and establish O ( θ ) O(\sqrt{\theta}) O ( θ ) completion stability for d d d -dimensional Euclidean pseudometrics (Lemma 5.7) via affine anchor rigidity. We next analyze metrics with bounded aspect ratio on [ 1 , C ] [1,C] [ 1 , C ] : after showing that C = 3 C = 3 C = 3 is the exact completion threshold (Proposition 5.9 ), we use a cyclic entropy inequality to prove linear completion stability for every fixed C > 1 C > 1 C > 1 (Theorem 5.13), which in turn yields uniform polynomial-time completion repair (Corollary 5.15) and a triangle packing bound for metric repair (Proposition 5.17). Finally, we use a collinear twin construction (Lemma 5.19) to prove that strict tree metrics and strict Euclidean metrics admit completion obstructions and are not constant-query one-sided testable {xref}(Theorem 5.20). Combining our results from {xref}Sections 4 and 5 shows that packing amplification and completion stability are logically independent {xref}(Corollary 5.22)`.
Ultrametrics and tree pseudometrics via recursive separation
Our recursive separation scheme for completing locally consistent partial ultrametrics and tree pseudometrics complements algorithmic work on fitting and repairing ultrametrics and tree metrics under edge disagreements or outlier deletions [33 , 13 , 10 ] . We begin with a structural graph partitioning lemma that bounds the number of F F F -edges cut when separating all R R R -edges in an edge tripartition without forbidden triangles.
Lemma 5.1. Let F F F , R R R , S S S partition E ( V ) = ( V 2 ) E(V) = \binom{V}{2} E ( V ) = ( 2 V ) , and suppose no triangle has two edges in F F F and one in R R R . There exist a partition P \mathcal{P} P of V V V , a set Z ⊆ F Z \subseteq F Z ⊆ F , and a set Q ⊆ S Q \subseteq S Q ⊆ S such that:
no part contains an R R R -edge;
Z Z Z is the set of F F F -edges crossing P \mathcal{P} P ;
every edge of Q Q Q crosses P \mathcal{P} P ;
∣ Z ∣ ≤ 3 ∣ Q ∣ |Z| \le3|Q| ∣ Z ∣ ≤ 3∣ Q ∣ .
Proof. We first verify that if p 0 p 1 p 2 p 3 p_0p_1p_2p_3 p 0 p 1 p 2 p 3 is a shortest path in a graph G G G , then some p i p_i p i satisfies deg G ( p i ) ≤ 3 ∣ N G 2 ( p i ) ∣ \deg_G(p_i) \le3|N^2_G(p_i)| deg G ( p i ) ≤ 3∣ N G 2 ( p i ) ∣ , where N G 2 ( x ) N^2_G(x) N G 2 ( x ) denotes the set of vertices at distance exactly two from x x x . For each vertex x x x , let A x = { i : x p i ∈ E ( G ) } A_x = \{i : xp_i \in E(G)\} A x = { i : x p i ∈ E ( G )} and B x = { i : dist G ( x , p i ) = 2 } B_x = \{i : \operatorname{dist}_G(x,p_i) = 2\} B x = { i : dist G ( x , p i ) = 2 } . Because p 0 p 1 p 2 p 3 p_0p_1p_2p_3 p 0 p 1 p 2 p 3 is a shortest path, no vertex is adjacent to both p 0 p_0 p 0 and p 3 p_3 p 3 , so ∣ A x ∣ ≤ 3 |A_x| \le3 ∣ A x ∣ ≤ 3 . Moreover, if A x ≠ ∅ A_x \ne\varnothing A x = ∅ , then B x ≠ ∅ B_x \ne\varnothing B x = ∅ : for a path vertex this follows from the shortest-path property, and for any other vertex a transition between an adjacent and a nonadjacent consecutive path vertex yields distance two. Thus ∣ A x ∣ ≤ 3 ∣ B x ∣ |A_x| \le3|B_x| ∣ A x ∣ ≤ 3∣ B x ∣ , and summing over x x x proves the claim.
We now work separately in the connected components of ( V , F ) (V,F) ( V , F ) and induct on ∣ V ∣ |V| ∣ V ∣ . If a component contains no internal R R R -edge, take it as a single part. Otherwise, choose a b ∈ R ab \in R ab ∈ R and a shortest F F F -path from a a a to b b b . Its length is at least three, as length one is impossible and length two would form a forbidden triangle. By the initial claim, some vertex v v v among the first four path vertices satisfies deg F ( v ) ≤ 3 ∣ N F 2 ( v ) ∣ \deg_F(v) \le3|N^2_F(v)| deg F ( v ) ≤ 3∣ N F 2 ( v ) ∣ . Set Z 0 = { v w ∈ F : w ∈ V } Z_0 = \{vw \in F : w \in V\} Z 0 = { v w ∈ F : w ∈ V } and Q 0 = { v w : w ∈ N F 2 ( v ) } Q_0 = \{vw : w \in N^2_F(v)\} Q 0 = { v w : w ∈ N F 2 ( v )} . Every edge of Q 0 Q_0 Q 0 lies in S S S , since it is not in F F F and membership in R R R would create a forbidden triangle. Apply the induction hypothesis to the F F F -components of V ∖ { v } V \setminus\{v\} V ∖ { v } , add { v } \{v\} { v } as a singleton part, and adjoin Z 0 Z_0 Z 0 and Q 0 Q_0 Q 0 to the recursive sets. Since the new edges are incident to v v v while the recursive edges are not, the cardinality bounds add and all four properties follow. □ \square □
Lemma 5.2 (Completion stability for ultrametrics). Over any nonempty value set Λ \Lambda Λ , a locally consistent partial ultrametric with h h h holes can be completed to a valid ultrametric by changing at most 3 h 3h 3 h specified entries. Consequently,
Γ u l t ( θ ) ≤ min { 1 , 6 θ } . \Gamma_{\mathrm{ult}}(\theta) \le\min\{1,6\theta\}. Γ ult ( θ ) ≤ min { 1 , 6 θ } . This includes U \mathcal{U} U on R ≥ 0 \mathbb{R}_{\ge0} R ≥ 0 and U + \mathcal{U}^{+} U + on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) .
Proof. Let A : D → Λ A:D\to\Lambda A : D → Λ be the specified assignment on a finite vertex set V V V , and let H = E ( V ) ∖ D H=E(V)\setminus D H = E ( V ) ∖ D be its hole set. We recursively process subsets X ⊆ V X\subseteq V X ⊆ V with a cap β ∈ Λ \beta\in\Lambda β ∈ Λ bounding all specified values inside X X X , initialized to the maximum specified value (or any element of Λ \Lambda Λ if D = ∅ D=\varnothing D = ∅ ).
If no edge inside X X X is specified, assign β \beta β to all edges of E ( X ) E(X) E ( X ) . Otherwise, let λ X = max e ∈ D ∩ E ( X ) A e \lambda_X=\max_{e\in D\cap E(X)}A_e λ X = max e ∈ D ∩ E ( X ) A e and partition E ( X ) E(X) E ( X ) into F X = { e ∈ D ∩ E ( X ) : A e < λ X } F_X=\{e\in D\cap E(X):A_e<\lambda_X\} F X = { e ∈ D ∩ E ( X ) : A e < λ X } , R X = { e ∈ D ∩ E ( X ) : A e = λ X } R_X=\{e\in D\cap E(X):A_e=\lambda_X\} R X = { e ∈ D ∩ E ( X ) : A e = λ X } , and S X = H ∩ E ( X ) S_X=H\cap E(X) S X = H ∩ E ( X ) . Local consistency rules out triangles with two F X F_X F X -edges and one R X R_X R X -edge. Apply Lemma 5.1 , assign λ X \lambda_X λ X to all edges crossing the resulting partition, and recurse on each part with cap λ X \lambda_X λ X .
Because R X ≠ ∅ R_X\ne\varnothing R X = ∅ and no part contains an R X R_X R X -edge, each recursive part is proper and the recursion terminates. Any triangle crossing a partition has at least two edges of value λ X \lambda_X λ X and its third edge at most λ X \lambda_X λ X , while triangles within a part are valid by induction; hence the output is a valid ultrametric in Λ \Lambda Λ . Among specified edges, only the crossing F X F_X F X -edges Z X Z_X Z X are modified, and Lemma 5.1 gives ∣ Z X ∣ ≤ 3 ∣ Q X ∣ |Z_X|\le3|Q_X| ∣ Z X ∣ ≤ 3∣ Q X ∣ for a subset Q X ⊆ H Q_X\subseteq H Q X ⊆ H crossing the partition. The sets Q X Q_X Q X are pairwise disjoint across the recursion tree because every edge of Q X Q_X Q X crosses the partition of X X X , whereas descendants lie within single parts and incomparable nodes occupy disjoint vertex sets. Thus at most 3 ∣ H ∣ 3|H| 3∣ H ∣ specified edges are modified in total, yielding cdist ( A ) ≤ 6 ∣ H ∣ / n 2 \operatorname{cdist}(A)\le6|H|/n^2 cdist ( A ) ≤ 6∣ H ∣/ n 2 for n ≥ 3 n\ge3 n ≥ 3 .
Corollary 5.3. On the ambient value set R ≥ 0 \mathbb{R}_{\ge0} R ≥ 0 , we have Γ u l t + ( θ ) ≤ min { 1 , 10 θ } \Gamma_{\mathrm{ult}+}(\theta)\le\min\{1,10\theta\} Γ ult + ( θ ) ≤ min { 1 , 10 θ } . On the positive ambient value set ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , the bound improves to min { 1 , 6 θ } \min\{1,6\theta\} min { 1 , 6 θ } .
Proof. The bound on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) follows from Lemma 5.2 . On R ≥ 0 \mathbb{R}_{\ge0} R ≥ 0 , let A A A be locally consistent for Φ u l t + \Phi_{\mathrm{ult}}^{+} Φ ult + with h h h holes and z z z specified zero edges. Every triple containing a specified zero edge must contain a hole, so in each triple the number of specified zero edges is at most twice the number of holes. Summing over all triples gives z ( n − 2 ) ≤ 2 h ( n − 2 ) z(n-2)\le2h(n-2) z ( n − 2 ) ≤ 2 h ( n − 2 ) , so z ≤ 2 h z\le2h z ≤ 2 h . Replacing all specified zeros with a positive value leaves every fully specified triple unchanged; applying Lemma 5.2 over ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) then changes at most 3 h 3h 3 h additional specified entries, for at most z + 3 h ≤ 5 h z+3h\le5h z + 3 h ≤ 5 h changes in total.
To extend Lemma 5.2 to tree pseudometrics, we pass to rooted Gromov products as in Lemma 4.2 .
Lemma 5.4. Let X X X be a finite set with heights h i ≥ 0 h_i\ge0 h i ≥ 0 , and let s s s be a partial symmetric assignment on D ⊆ ( X 2 ) D\subseteq\binom{X}{2} D ⊆ ( 2 X ) with hole set H = ( X 2 ) ∖ D H=\binom{X}{2}\setminus D H = ( 2 X ) ∖ D . Suppose 0 ≤ s i j ≤ min { h i , h j } 0\le s_{ij}\le\min\{h_i,h_j\} 0 ≤ s ij ≤ min { h i , h j } for all i j ∈ D ij\in D ij ∈ D , and every fully specified triple has its minimum s s s -value attained at least twice. Then there exists a full assignment s ~ \widetilde{s} s satisfying both conditions everywhere and differing from s s s on at most 3 ∣ H ∣ 3|H| 3∣ H ∣ specified entries.
Proof. Assume X ≠ ∅ X\ne\varnothing X = ∅ , and set H 0 = max ( { 0 } ∪ { h i : i ∈ X } ) H_0=\max(\{0\}\cup\{h_i:i\in X\}) H 0 = max ({ 0 } ∪ { h i : i ∈ X }) and u i j = H 0 − s i j u_{ij}=H_0-s_{ij} u ij = H 0 − s ij for i j ∈ D ij\in D ij ∈ D . The specified u u u -values lie in [ 0 , H 0 ] [0,H_0] [ 0 , H 0 ] and are locally ultrametric, so Lemma 5.2 produces a full ultrametric U U U in [ 0 , H 0 ] [0,H_0] [ 0 , H 0 ] differing from u u u on at most 3 ∣ H ∣ 3|H| 3∣ H ∣ specified entries. For distinct i , j ∈ X i,j\in X i , j ∈ X , put v i j = H 0 − U i j v_{ij}=H_0-U_{ij} v ij = H 0 − U ij and s ~ i j = min { v i j , h i , h j } \widetilde{s}_{ij}=\min\{v_{ij},h_i,h_j\} s ij = min { v ij , h i , h j } . Then s ~ i j \widetilde{s}_{ij} s ij is nonnegative, satisfies the height bounds, and inherits the minimum condition from v i j ≥ min { v i k , v j k } v_{ij}\ge\min\{v_{ik},v_{jk}\} v ij ≥ min { v ik , v j k } via min { s ~ i k , s ~ j k } = min { v i k , v j k , h i , h j , h k } ≤ min { v i j , h i , h j } = s ~ i j \min\{\widetilde{s}_{ik},\widetilde{s}_{jk}\}=\min\{v_{ik},v_{jk},h_i,h_j,h_k\}\le\min\{v_{ij},h_i,h_j\}=\widetilde{s}_{ij} min { s ik , s j k } = min { v ik , v j k , h i , h j , h k } ≤ min { v ij , h i , h j } = s ij . Whenever U i j = u i j U_{ij}=u_{ij} U ij = u ij on a specified pair, we have v i j = s i j ≤ min { h i , h j } v_{ij}=s_{ij}\le\min\{h_i,h_j\} v ij = s ij ≤ min { h i , h j } and hence s ~ i j = s i j \widetilde{s}_{ij}=s_{ij} s ij = s ij , introducing no further discrepancies.
Lemma 5.5 (Completion stability for tree pseudometrics). For every θ ≥ 0 \theta\ge0 θ ≥ 0 ,
Γ t r e e ( θ ) ≤ min { 1 , 26 θ } . \Gamma_{\mathrm{tree}}(\theta)\le\min\{1,26\theta\}. Γ tree ( θ ) ≤ min { 1 , 26 θ } .
Proof. Let A A A be locally consistent on [ n ] [n] [ n ] with n ≥ 4 n\ge4 n ≥ 4 and h = ∣ H ( A ) ∣ h=|H(A)| h = ∣ H ( A ) ∣ . Choose a root o o o of minimum hole degree y = deg H ( o ) ≤ 2 h / n y=\deg_H(o)\le2h/n y = deg H ( o ) ≤ 2 h / n , and set X = { i ≠ o : o i ∉ H ( A ) } X=\{i\ne o:oi\notin H(A)\} X = { i = o : o i ∈ / H ( A )} . If N = ∣ X ∣ ≤ 2 N=|X|\le2 N = ∣ X ∣ ≤ 2 , then y ≥ n − 3 y\ge n-3 y ≥ n − 3 , so h ≥ n ( n − 3 ) / 2 h\ge n(n-3)/2 h ≥ n ( n − 3 ) /2 and cdist ( A ) ≤ 1 ≤ 26 h / n 2 \operatorname{cdist}(A)\le1\le26h/n^2 cdist ( A ) ≤ 1 ≤ 26 h / n 2 . Assume henceforth that N ≥ 3 N\ge3 N ≥ 3 . Let H X = H ( A ) ∩ ( X 2 ) H_X=H(A)\cap\binom{X}{2} H X = H ( A ) ∩ ( 2 X ) and h X = ∣ H X ∣ h_X=|H_X| h X = ∣ H X ∣ . For specified pairs in X X X , set h i = A o i h_i=A_{oi} h i = A o i and s i j = ( h i + h j − A i j ) / 2 s_{ij}=(h_i+h_j-A_{ij})/2 s ij = ( h i + h j − A ij ) /2 , and let E 0 E_0 E 0 be the set of specified pairs in X X X violating 0 ≤ s i j ≤ min { h i , h j } 0\le s_{ij}\le\min\{h_i,h_j\} 0 ≤ s ij ≤ min { h i , h j } , with b = ∣ E 0 ∣ b=|E_0| b = ∣ E 0 ∣ . Any triple T ∈ ( X 3 ) T\in\binom{X}{3} T ∈ ( 3 X ) meeting E 0 E_0 E 0 must contain a hole in H X H_X H X , as otherwise T ∪ { o } T\cup\{o\} T ∪ { o } would be a fully specified quartet violating a triangle inequality. Thus ∣ E 0 ∩ ( T 2 ) ∣ ≤ 2 ∣ H X ∩ ( T 2 ) ∣ |E_0\cap\binom{T}{2}|\le2|H_X\cap\binom{T}{2}| ∣ E 0 ∩ ( 2 T ) ∣ ≤ 2∣ H X ∩ ( 2 T ) ∣ for every T ∈ ( X 3 ) T\in\binom{X}{3} T ∈ ( 3 X ) ; summing over T T T and dividing by n − 2 n-2 n − 2 gives b ≤ 2 h X b\le2h_X b ≤ 2 h X .
Deleting E 0 E_0 E 0 leaves a partial assignment on X X X with h X + b h_X+b h X + b holes that satisfies the hypotheses of Lemma 5.4, since every remaining fully specified triple forms a valid quartet with o o o . Lemma 5.4 yields a completion s ~ \widetilde{s} s on X X X changing at most 3 ( h X + b ) 3(h_X+b) 3 ( h X + b ) remaining specified entries, so at most b + 3 ( h X + b ) ≤ 11 h X b+3(h_X+b)\le11h_X b + 3 ( h X + b ) ≤ 11 h X originally specified entries in X X X are modified. Setting B o i = h i B_{oi}=h_i B o i = h i and B i j = h i + h j − 2 s ~ i j B_{ij}=h_i+h_j-2\widetilde{s}_{ij} B ij = h i + h j − 2 s ij for distinct i , j ∈ X i,j\in X i , j ∈ X defines a tree pseudometric on { o } ∪ X \{o\}\cup X { o } ∪ X by Lemma 4.2 . Identifying each of the y y y vertices outside { o } ∪ X \{o\}\cup X { o } ∪ X with o o o alters at most y n ≤ 2 h yn\le2h y n ≤ 2 h additional specified entries, for a total of at most 11 h X + 2 h ≤ 13 h 11h_X+2h\le13h 11 h X + 2 h ≤ 13 h modified specified entries and cdist ( A ) ≤ 26 h / n 2 \operatorname{cdist}(A)\le26h/n^2 cdist ( A ) ≤ 26 h / n 2 . □
Corollary 5.6. For every θ > 0 \theta>0 θ > 0 , we have θ 1 + 8 θ ≤ Γ t r e e ( θ ) ≤ min { 1 , 26 θ } \frac{\theta}{1+8\theta}\le\Gamma_{\mathrm{tree}}(\theta)\le\min\{1,26\theta\} 1 + 8 θ θ ≤ Γ tree ( θ ) ≤ min { 1 , 26 θ } , and in particular Γ t r e e ( θ ) = Θ ( θ ) \Gamma_{\mathrm{tree}}(\theta)=\Theta(\theta) Γ tree ( θ ) = Θ ( θ ) as θ ↓ 0 \theta\downarrow0 θ ↓ 0 .
Proof. For the lower bound, take m = ⌈ 1 / ( 8 θ ) ⌉ m=\lceil1/(8\theta)\rceil m = ⌈ 1/ ( 8 θ )⌉ disjoint four-vertex gadgets on n = 4 m n=4m n = 4 m vertices. In each gadget, specify a four-cycle with consecutive edge weights 1 , 1 , 1 , 4 1,1,1,4 1 , 1 , 1 , 4 and leave both diagonals as holes; set all cross-gadget distances to 4 4 4 . Since every triple inside a gadget contains a hole, any fully specified quartet meets each gadget in at most two vertices, so two of its opposite-edge sums equal 8 8 8 , the third is at most 8 8 8 , and all triangle inequalities hold. Thus the partial matrix is locally consistent for Φ t r e e \Phi_{\mathrm{tree}} Φ tree , yet every metric repair must edit at least one cycle edge per gadget because 4 > 1 + 1 + 1 4>1+1+1 4 > 1 + 1 + 1 . This gives ∣ H ( A ) ∣ / n 2 = 1 / ( 8 m ) |H(A)|/n^2=1/(8m) ∣ H ( A ) ∣/ n 2 = 1/ ( 8 m ) and cdist ( A ) ≥ 1 / ( 8 m ) \operatorname{cdist}(A)\ge1/(8m) cdist ( A ) ≥ 1/ ( 8 m ) , matching the upper bound of Lemma 5.5. □
Euclidean pseudometrics via affine anchor rigidity
For d d d -dimensional Euclidean pseudometrics, we adapt the affine anchor repair strategy of [31 Lemma 6.1] to partial matrices by selecting a fully specified ( d + 3 ) (d+3) ( d + 3 ) -clique of maximum affine dimension among vertices of low hole degree.
Lemma 5.7 (Completion stability for Euclidean pseudometrics). For every θ ≥ 0 \theta\ge0 θ ≥ 0 ,
Γ E u c ( d ) ( θ ) ≤ min { 1 , 2 ( d + 5 ) θ } . \Gamma_{\mathrm{Euc}}^{(d)}(\theta)\le\min\left\{1,2(d+5)\sqrt{\theta}\right\}. Γ Euc ( d ) ( θ ) ≤ min { 1 , 2 ( d + 5 ) θ } .
Proof. Let A A A be locally consistent on [ n ] [n] [ n ] with n ≥ d + 3 n\ge d+3 n ≥ d + 3 . The bound is trivial if H ( A ) = ∅ H(A)=\varnothing H ( A ) = ∅ or θ ≥ 1 / ( 4 ( d + 5 ) 2 ) \theta\ge1/(4(d+5)^2) θ ≥ 1/ ( 4 ( d + 5 ) 2 ) , so assume 0 < θ < 1 / ( 4 ( d + 5 ) 2 ) 0<\theta<1/(4(d+5)^2) 0 < θ < 1/ ( 4 ( d + 5 ) 2 ) and 1 ≤ ∣ H ( A ) ∣ ≤ θ n 2 1\le|H(A)|\le\theta n^2 1 ≤ ∣ H ( A ) ∣ ≤ θ n 2 ; in particular, n ≥ 1 / θ n\ge1/\sqrt{\theta} n ≥ 1/ θ . Let G G G be the graph of specified pairs and W = { v ∈ [ n ] : deg H ( v ) ≤ θ n } W=\{v\in[n]:\deg_H(v)\le\sqrt{\theta}n\} W = { v ∈ [ n ] : deg H ( v ) ≤ θ n } , so ∣ [ n ] ∖ W ∣ ≤ 2 θ n |[n]\setminus W|\le2\sqrt{\theta}n ∣ [ n ] ∖ W ∣ ≤ 2 θ n by the handshake lemma. A greedy selection from G [ W ] G[W] G [ W ] : after choosing j ≤ d + 2 j\le d+2 j ≤ d + 2 vertices, the number of common neighbors in W W W is at least n ( 1 − ( j + 2 ) θ ) − j ≥ θ − 1 / 2 − 2 ( d + 3 ) > 4 n(1-(j+2)\sqrt{\theta})-j\ge\theta^{-1/2}-2(d+3)>4 n ( 1 − ( j + 2 ) θ ) − j ≥ θ − 1/2 − 2 ( d + 3 ) > 4 .
Choose a ( d + 3 ) (d+3) ( d + 3 ) -clique C C C in G [ W ] G[W] G [ W ] whose realization has maximum affine dimension s s s , fix a realization in R s \mathbb{R}^s R s with affine basis c 0 , … , c s ∈ C c_0,\ldots,c_s\in C c 0 , … , c s ∈ C , and set X = { v ∈ W : v ∉ H ( A ) for all c ∈ C ∖ { v } } X=\{v\in W:v\notin H(A)\text{ for all }c\in C\setminus\{v\}\} X = { v ∈ W : v ∈ / H ( A ) for all c ∈ C ∖ { v }} . Then C ⊂ X C\subset X C ⊂ X and ∣ [ n ] ∖ X ∣ ≤ 2 θ n + θ n |[n]\setminus X|\le2\sqrt{\theta}n+\sqrt{\theta}n ∣ [ n ] ∖ X ∣ ≤ 2 θ n + θ n . For each v ∈ X ∖ C v\in X\setminus C v ∈ X ∖ C , the submatrix on C ∪ { v } C\cup\{v\} C ∪ { v } is fully specified and locally valid, so Lemma 2.7 yields a realization in R d \mathbb{R}^d R d . Its affine dimension cannot exceed s s s , as otherwise padding an affinely independent ( s + 2 ) (s+2) ( s + 2 ) -subset with vertices of C C C would contradict the maximality of s s s . After aligning C C C , the image of v v v lies in R s \mathbb{R}^s R s and is uniquely determined by Lemma 2.6 ; denote it by p v p_v p v .
For any specified pair u v uv uv in X X X , padding { u , v , c 0 , … , c s } \{u,v,c_0,\ldots,c_s\} { u , v , c 0 , … , c s } with vertices of C C C forms a fully specified ( d + 3 ) (d+3) ( d + 3 ) -set in W W W of affine dimension at most s s s , and aligning the affine basis forces A u v = ∥ p u − p v ∥ 2 A_{uv}=\|p_u-p_v\|_2 A uv = ∥ p u − p v ∥ 2 . Assigning every vertex outside X X X to p c 0 p_{c_0} p c 0 produces a global Euclidean pseudometric agreeing with A A A on all specified pairs inside X X X , so cdist ( A ) ≤ 2 n 2 ∣ [ n ] ∖ X ∣ n ≤ 2 ( d + 5 ) θ \operatorname{cdist}(A) \le\frac{2}{n^2}|[n]\setminus X|n \le2(d+5)\sqrt{\theta} cdist ( A ) ≤ n 2 2 ∣ [ n ] ∖ X ∣ n ≤ 2 ( d + 5 ) θ .
Metrics with bounded aspect ratio via cyclic entropy
For a partial matrix A A A with specified values in [ 1 , C ] [1,C] [ 1 , C ] , let G A G_A G A denote its graph of specified edges. A simple cycle in G A G_A G A is nonmetric (also called broken or unbalanced in the metric repair literature [7 , 21 , 20 , 19 ] ) if one edge weight strictly exceeds the sum of the remaining edge weights. We first record the bounded range form of the classical metric completion criterion [26 , 16 ] .
Lemma 5.8. A partial matrix with specified values in [ 1 , C ] [1,C] [ 1 , C ] has a metric completion in [ 1 , C ] [1,C] [ 1 , C ] preserving all specified entries if and only if G A G_A G A contains no nonmetric cycle.
Proof. Necessity is immediate from the triangle inequality along any cycle. Conversely, let d G d_G d G denote shortest-path distance in G A G_A G A (with d G ( u , v ) = + ∞ d_G(u,v)=+\infty d G ( u , v ) = + ∞ between components), and set B u v = min { C , d G ( u , v ) } B_{uv}=\min\{C,d_G(u,v)\} B uv = min { C , d G ( u , v )} for u ≠ v u\ne v u = v and B u u = 0 B_{uu}=0 B uu = 0 . If u v uv uv is specified, a strict inequality d G ( u , v ) < A u v d_G(u,v)<A_{uv} d G ( u , v ) < A uv would yield a shorter simple path in G A G_A G A and hence a nonmetric cycle, so B B B preserves all specified entries. Moreover, every path between distinct vertices has length at least 1 1 1 , and for any distinct u , v , w u,v,w u , v , w , either max { d G ( u , w ) , d G ( w , v ) } ≥ C \max\{d_G(u,w),d_G(w,v)\}\ge C max { d G ( u , w ) , d G ( w , v )} ≥ C gives B u w + B w v ≥ C ≥ B u v B_{uw}+B_{wv}\ge C\ge B_{uv} B u w + B w v ≥ C ≥ B uv , or else B u v ≤ d G ( u , w ) + d G ( w , v ) = B u w + B w v B_{uv}\le d_G(u,w)+d_G(w,v)=B_{uw}+B_{wv} B uv ≤ d G ( u , w ) + d G ( w , v ) = B u w + B w v . Thus B ∈ M n [ 1 , C ] B\in\mathcal{M}_n[1,C] B ∈ M n [ 1 , C ] .
The number of edits to specified edges in cdist ( A ) \operatorname{cdist}(A) cdist ( A ) is the sparse metric repair objective on G A G_A G A normalized by 2 / n 2 2/n^2 2/ n 2 , or equivalently the minimum size of a hitting set of specified edges for all nonmetric cycles [21 , 20 , 19 ] . We now bound this optimum in terms of the hole count under local consistency, beginning with the exact completion threshold at C = 3 C=3 C = 3 (which differs from the trivial threshold C = 2 C=2 C = 2 below which every complete input is already metric).
Proposition 5.9 (Exact completion threshold at C = 3 ) . I f $ 1 < C ≤ 3 C=3). If \$1<C\le3 C = 3 ) . I f $1 < C ≤ 3 , every locally consistent partial matrix in [ 1 , C ] [1,C] [ 1 , C ] has an exact metric completion, so Γ ( θ ) = 0 \Gamma(\theta)=0 Γ ( θ ) = 0 for all θ ≥ 0 \theta\ge0 θ ≥ 0 . Conversely, for every C > 3 C>3 C > 3 , locally consistent partial matrices without exact completions exist, and Γ ( θ ) ≥ θ 1 + 8 θ \Gamma(\theta)\ge\frac{\theta}{1+8\theta} Γ ( θ ) ≥ 1 + 8 θ θ for all θ > 0 \theta>0 θ > 0 .
Proof. Local consistency rules out nonmetric triangles, and when C ≤ 3 C\le3 C ≤ 3 any cycle of length r ≥ 4 r\ge4 r ≥ 4 has maximum edge weight at most 3 ≤ r − 1 3\le r-1 3 ≤ r − 1 , excluding longer nonmetric cycles; Lemma 5.8 then gives an exact completion. For C > 3 C>3 C > 3 , fix L ∈ ( 3 , C ] L\in(3,C] L ∈ ( 3 , C ] and apply the m m m -gadget four-cycle construction of Corollary 5.6 with cycle weights 1 , 1 , 1 , L 1,1,1,L 1 , 1 , 1 , L , diagonal holes, and cross-gadget distances C C C . Every fully specified triangle is valid, each gadget requires at least one specified edit, and changing each weight-L L L edge to 3 3 3 while filling the diagonals with 2 2 2 achieves cdist ( A ) = ∣ H ( A ) ∣ / n 2 = 1 / ( 8 m ) \operatorname{cdist}(A)=|H(A)|/n^2=1/(8m) cdist ( A ) = ∣ H ( A ) ∣/ n 2 = 1/ ( 8 m ) on n = 4 m n=4m n = 4 m vertices. Setting m = ⌈ 1 / ( 8 θ ) ⌉ m=\lceil1/(8\theta)\rceil m = ⌈ 1/ ( 8 θ )⌉ completes the proof.
An entropy inequality on cycles
To bound the hitting number of shortest nonmetric cycles when C > 3 C>3 C > 3 , we establish an entropy inequality for random variables indexed by a cycle (using natural logarithms). The following conditional independence property is a cycle separator form of the global Markov property for maximum entropy graphical models [17 , 28 ] that also allows prescribed marginals with zero entries [15 , 34 ] .
Lemma 5.10. Let X 0 , … , X r − 1 X_0,\ldots,X_{r-1} X 0 , … , X r − 1 be finite-valued random variables on a cycle with a feasible family of prescribed marginals on adjacent pairs. Any entropy-maximizing joint distribution with these
marginals makes the interiors of complementary arcs conditionally independent given their two common endpoints.
Proof. An entropy maximizer μ \mu μ exists by compactness. For separator endpoints S S S and complementary arc interiors A , B A, B A , B , the conditional-product law ν ( A , B , S ) = μ ( S ) μ ( A ∣ S ) μ ( B ∣ S ) \nu(A, B, S) = \mu(S)\mu(A \mid S)\mu(B \mid S) ν ( A , B , S ) = μ ( S ) μ ( A ∣ S ) μ ( B ∣ S ) preserves the marginals on ( A , S ) (A, S) ( A , S ) and ( B , S ) (B, S) ( B , S ) and hence all adjacent-pair marginals, while H ν ( A , B , S ) − H μ ( A , B , S ) = I μ ( A ; B ∣ S ) ≥ 0 H_\nu(A, B, S) - H_\mu(A, B, S) = I_\mu(A; B \mid S) \ge0 H ν ( A , B , S ) − H μ ( A , B , S ) = I μ ( A ; B ∣ S ) ≥ 0 . Maximality forces I μ ( A ; B ∣ S ) = 0 I_\mu(A; B \mid S) = 0 I μ ( A ; B ∣ S ) = 0 .
Lemma 5.11. Let r ≥ 4 r \ge4 r ≥ 4 and suppose finite-valued random variables ( X 0 , … , X r − 1 ) (X_0,\ldots,X_{r-1}) ( X 0 , … , X r − 1 ) satisfy conditional arc independence on the cycle. With cyclic indices, the average pair entropies E d = 1 r ∑ i = 0 r − 1 H ( X i , X i + d ) E_d = \frac{1}{r}\sum_{i=0}^{r-1} H(X_i,X_{i+d}) E d = r 1 ∑ i = 0 r − 1 H ( X i , X i + d ) satisfy E d ≥ E 1 E_d \ge E_1 E d ≥ E 1 for all 2 ≤ d ≤ r − 2 2 \le d \le r-2 2 ≤ d ≤ r − 2 .
Proof. Fix i i i and 2 ≤ d ≤ r − 2 2 \le d \le r-2 2 ≤ d ≤ r − 2 , and write ( A , B , C , D ) = ( X i , X i + 1 , X i + d , X i + d + 1 ) (A,B,C,D) = (X_i,X_{i+1},X_{i+d},X_{i+d+1}) ( A , B , C , D ) = ( X i , X i + 1 , X i + d , X i + d + 1 ) . Conditional arc independence gives A ⊥ C ∣ ( B , D ) A \perp C \mid(B,D) A ⊥ C ∣ ( B , D ) and B ⊥ D ∣ ( A , C ) B \perp D \mid(A,C) B ⊥ D ∣ ( A , C ) , so H ( A , B , D ) + H ( B , C , D ) = H ( A , B , C , D ) + H ( B , D ) H(A,B,D) + H(B,C,D) = H(A,B,C,D) + H(B,D) H ( A , B , D ) + H ( B , C , D ) = H ( A , B , C , D ) + H ( B , D ) and H ( A , B , C ) + H ( A , C , D ) = H ( A , B , C , D ) + H ( A , C ) H(A,B,C) + H(A,C,D) = H(A,B,C,D) + H(A,C) H ( A , B , C ) + H ( A , C , D ) = H ( A , B , C , D ) + H ( A , C ) . Expanding the nonnegative sum I ( A ; B ∣ C , D ) + I ( B ; C ∣ A , D ) + I ( C ; D ∣ A , B ) + I ( D ; A ∣ B , C ) ≥ 0 I(A;B \mid C,D) + I(B;C \mid A,D) + I(C;D \mid A,B) + I(D;A \mid B,C) \ge0 I ( A ; B ∣ C , D ) + I ( B ; C ∣ A , D ) + I ( C ; D ∣ A , B ) + I ( D ; A ∣ B , C ) ≥ 0 therefore yields 2 H ( A , C ) + 2 H ( B , D ) ≥ H ( A , B ) + H ( B , C ) + H ( C , D ) + H ( D , A ) 2H(A,C) + 2H(B,D) \ge H(A,B) + H(B,C) + H(C,D) + H(D,A) 2 H ( A , C ) + 2 H ( B , D ) ≥ H ( A , B ) + H ( B , C ) + H ( C , D ) + H ( D , A ) . Averaging over i i i gives 4 E d ≥ 2 E 1 + E d − 1 + E d + 1 4E_d \ge2E_1 + E_{d-1} + E_{d+1} 4 E d ≥ 2 E 1 + E d − 1 + E d + 1 . Since E r − 1 = E 1 E_{r-1} = E_1 E r − 1 = E 1 , the differences g d = E d − E 1 g_d = E_d - E_1 g d = E d − E 1 satisfy g 1 = g r − 1 = 0 g_1 = g_{r-1} = 0 g 1 = g r − 1 = 0 and 4 g d ≥ g d − 1 + g d + 1 4g_d \ge g_{d-1} + g_{d+1} 4 g d ≥ g d − 1 + g d + 1 , which rules out a negative interior minimum.
Unlike projection inequalities such as Shearer’s inequality [14 ] , Lemma 5.11 compares distinct averages of pair entropies and requires conditional arc independence: on a four-cycle with X 0 = X 2 = U X_0 = X_2 = U X 0 = X 2 = U and X 1 = X 3 = V X_1 = X_3 = V X 1 = X 3 = V for independent fair bits U , V U,V U , V , one has E 1 = 2 log 2 > E 2 = log 2 E_1 = 2\log2 > E_2 = \log2 E 1 = 2 log 2 > E 2 = log 2 .
Lemma 5.12. Let G G G be a positively weighted simple graph on n n n vertices with h = ( n 2 ) − ∣ E ( G ) ∣ h = \binom{n}{2} - |E(G)| h = ( 2 n ) − ∣ E ( G ) ∣ holes. If G G G has no nonmetric cycle of length less than r r r , where r ≥ 4 r \ge4 r ≥ 4 , then there is a set of at most r h rh r h edges meeting every nonmetric r r r -cycle.
Proof. For each cyclic r r r -tuple ω = ( v 0 , … , v r − 1 ) \omega= (v_0,\ldots,v_{r-1}) ω = ( v 0 , … , v r − 1 ) of adjacent vertices in G G G , define the excess s ( ω ) = w ( v r − 1 v 0 ) − ∑ i = 0 r − 2 w ( v i v i + 1 ) s(\omega) = w(v_{r-1}v_0) - \sum_{i=0}^{r-2} w(v_iv_{i+1}) s ( ω ) = w ( v r − 1 v 0 ) − ∑ i = 0 r − 2 w ( v i v i + 1 ) , and let Ω = { ω : s ( ω ) > 0 } \Omega= \{\omega: s(\omega) > 0\} Ω = { ω : s ( ω ) > 0 } . Assume Ω ≠ ∅ \Omega\ne\varnothing Ω = ∅ . Because G G G has no nonmetric cycle of length less than r r r , every ω ∈ Ω \omega\in\Omega ω ∈ Ω is a simple chordless cycle: a repeated vertex would yield a shorter closed subwalk and simple path of weight less than w ( v r − 1 v 0 ) w(v_{r-1}v_0) w ( v r − 1 v 0 ) , and a chord would split ω \omega ω into two shorter cycles at least one of which is nonmetric. In particular, every two-step pair ( v i , v i + 2 ) (v_i,v_{i+2}) ( v i , v i + 2 ) along ω ∈ Ω \omega\in\Omega ω ∈ Ω is a hole, so h > 0 h > 0 h > 0 .
Over the compact feasible polytope { z ∈ R ≥ 0 Ω : ∑ ω : e ∈ E ( ω ) z ω ≤ 1 for all e ∈ E ( G ) } \{z \in\mathbb{R}_{\ge0}^{\Omega} : \sum_{\omega:e\in E(\omega)} z_\omega\le1 \text{ for all } e \in E(G)\} { z ∈ R ≥ 0 Ω : ∑ ω : e ∈ E ( ω ) z ω ≤ 1 for all e ∈ E ( G )} , choose a fractional packing z z z that first maximizes ∑ ω ∈ Ω s ( ω ) z ω > 0 \sum_{\omega\in\Omega}s(\omega)z_\omega> 0 ∑ ω ∈ Ω s ( ω ) z ω > 0 and second minimizes the total mass t = ∑ ω ∈ Ω z ω > 0 t = \sum_{\omega\in\Omega}z_\omega> 0 t = ∑ ω ∈ Ω z ω > 0 . By averaging with cycle reversal ( v 0 , … , v r − 1 ) ↦ ( v r − 1 , … , v 0 ) (v_0,\ldots,v_{r-1}) \mapsto(v_{r-1},\ldots,v_0) ( v 0 , … , v r − 1 ) ↦ ( v r − 1 , … , v 0 ) , we may assume z z z is reversal-invariant. Let F F F be the set of saturated edges; then F F F meets every ω ∈ Ω \omega\in\Omega ω ∈ Ω by score maximality, and
∣ F ∣ ≤ ∑ e ∈ E ( G ) ∑ ω : e ∈ E ( ω ) z ω = r t . |F| \le\sum_{e\in E(G)}\sum_{\omega:e\in E(\omega)} z_\omega= rt. ∣ F ∣ ≤ e ∈ E ( G ) ∑ ω : e ∈ E ( ω ) ∑ z ω = r t .
Normalize μ ( ω ) = z ω / t \mu(\omega) = z_\omega/t μ ( ω ) = z ω / t , and let ν \nu ν be the entropy-maximizing distribution on [ n ] r [n]^r [ n ] r matching the ordered adjacent-pair marginals of μ \mu μ . Then ν \nu ν is supported on closed r r r -walks in G G G , satisfies t ∑ i = 0 r − 1 Pr ν [ ( X i , X i + 1 ) = e ] ≤ 1 t\sum_{i=0}^{r-1}\Pr_\nu[(X_i,X_{i+1}) = e] \le1 t ∑ i = 0 r − 1 Pr ν [( X i , X i + 1 ) = e ] ≤ 1 for every e ∈ E ( G ) e \in E(G) e ∈ E ( G ) , and has expected score t E ν s = ∑ ω ∈ Ω s ( ω ) z ω t\,\mathbb{E}_\nu s = \sum_{\omega\in\Omega}s(\omega)z_\omega t E ν s = ∑ ω ∈ Ω s ( ω ) z ω . Since positive-score walks lie in Ω \Omega Ω and are simple, z ω ′ = t ν ( ω ) z'_\omega= t\nu(\omega) z ω ′ = t ν ( ω ) ( ω ∈ Ω ) (\omega\in\Omega) ( ω ∈ Ω ) defines a feasible packing. If ν \nu ν placed positive mass outside Ω \Omega Ω , restricting to Ω \Omega Ω would either strictly increase the score (if ν ( s < 0 ) > 0 \nu(s < 0) > 0 ν ( s < 0 ) > 0 ) or preserve the optimal score while strictly reducing t t t (if ν ( s = 0 ) > 0 \nu(s = 0) > 0 ν ( s = 0 ) > 0 ), contradicting the choice of z z z . Thus ν \nu ν is supported on Ω \Omega Ω .
By reversal invariance, p i ( u , v ) = Pr ν [ ( X i , X i + 1 ) = ( u , v ) ] p_i(u,v) = \Pr_\nu[(X_i,X_{i+1}) = (u,v)] p i ( u , v ) = Pr ν [( X i , X i + 1 ) = ( u , v )] satisfies p i ( u , v ) = p r − 2 − i ( v , u ) p_i(u,v) = p_{r-2-i}(v,u) p i ( u , v ) = p r − 2 − i ( v , u ) . Because ν \nu ν is supported on simple cycles, u ≠ v u \ne v u = v , so ( X i , X i + 1 ) = ( u , v ) (X_i,X_{i+1}) = (u,v) ( X i , X i + 1 ) = ( u , v ) and ( X r − 2 − i , X r − 1 − i ) = ( v , u ) (X_{r-2-i},X_{r-1-i}) = (v,u) ( X r − 2 − i , X r − 1 − i ) = ( v , u ) are distinct ordered occurrences of the undirected edge { u , v } \{u,v\} { u , v } even when the cyclic indices i i i and r − 2 − i r-2-i r − 2 − i coincide. Hence 2 p i ( u , v ) ≤ ∑ j = 0 r − 1 Pr ν [ { X j , X j + 1 } = { u , v } ] ≤ 1 / t 2p_i(u,v) \le\sum_{j=0}^{r-1} \Pr_\nu[\{X_j,X_{j+1}\}=\{u,v\}] \le1/t 2 p i ( u , v ) ≤ ∑ j = 0 r − 1 Pr ν [{ X j , X j + 1 } = { u , v }] ≤ 1/ t , giving H ( X i , X i + 1 ) ≥ log ( 2 t ) H(X_i,X_{i+1}) \ge\log(2t) H ( X i , X i + 1 ) ≥ log ( 2 t ) . On the other hand, because every ω ∈ Ω \omega\in\Omega ω ∈ Ω is chordless, ( X i , X i + 2 ) (X_i,X_{i+2}) ( X i , X i + 2 ) takes values in the 2 h 2h 2 h ordered holes, so H ( X i , X i + 2 ) ≤ log ( 2 h ) H(X_i,X_{i+2}) \le\log(2h) H ( X i , X i + 2 ) ≤ log ( 2 h ) . Lemmas 5.10 and 5.11 therefore yield log ( 2 t ) ≤ E 1 ≤ E 2 ≤ log ( 2 h ) \log(2t) \le E_1 \le E_2 \le\log(2h) log ( 2 t ) ≤ E 1 ≤ E 2 ≤ log ( 2 h ) , so t ≤ h t \le h t ≤ h and ∣ F ∣ ≤ r h |F| \le rh ∣ F ∣ ≤ r h .
Theorem 5.13 (Completion stability for metrics with bounded aspect ratio). For fixed C > 1 C > 1 C > 1 , define M C = ∏ r = 4 ⌈ C ⌉ ( r + 1 ) M_C = \prod_{r=4}^{\lceil C\rceil}(r+1) M C = ∏ r = 4 ⌈ C ⌉ ( r + 1 ) , where the empty product is 1. Every locally consistent partial matrix in [ 1 , C ] [1,C] [ 1 , C ] with h h h holes becomes metrically completable after deleting at most ( M C − 1 ) h (M_C-1)h ( M C − 1 ) h specified edges. Consequently,
Γ ( θ ) ≤ min { 1 , 2 ( M C − 1 ) θ } , \Gamma(\theta) \le\min\{1,2(M_C-1)\theta\}, Γ ( θ ) ≤ min { 1 , 2 ( M C − 1 ) θ } , and for every fixed C > 3 C > 3 C > 3 , we have Γ ( θ ) = Θ C ( θ ) \Gamma(\theta) = \Theta_C(\theta) Γ ( θ ) = Θ C ( θ ) as θ ↓ 0 \theta\downarrow0 θ ↓ 0 .
Proof. Local consistency excludes nonmetric triangles, and any nonmetric r r r -cycle must satisfy r − 1 < C r-1 < C r − 1 < C , so r ≤ ⌈ C ⌉ r \le\lceil C\rceil r ≤ ⌈ C ⌉ . For r = 4 , … , ⌈ C ⌉ r = 4,\ldots,\lceil C\rceil r = 4 , … , ⌈ C ⌉ in turn, delete a hitting set of specified edges for all nonmetric r r r -cycles. Because edge deletion creates no new cycles, each stage r r r has no nonmetric cycle of length less than r r r ; if h r h_r h r is the current hole count, Lemma 5.12 deletes at most r h r rh_r r h r edges, giving h r + 1 ≤ ( r + 1 ) h r h_{r+1} \le(r+1)h_r h r + 1 ≤ ( r + 1 ) h r . After stage ⌈ C ⌉ \lceil C\rceil ⌈ C ⌉ , the hole count is at most M C h M_Ch M C h , at most ( M C − 1 ) h (M_C-1)h ( M C − 1 ) h specified edges have been deleted, and no nonmetric cycle remains, so Lemma 5.8 provides an exact completion. Normalizing the edit count yields the upper bound, while Proposition 5.9 gives Γ ≡ 0 \Gamma\equiv0 Γ ≡ 0 for C ≤ 3 C \le3 C ≤ 3 and the matching linear lower bound for C > 3 C > 3 C > 3 .
We next show that the hitting sets of Lemma 5.12 and the resulting completions can be computed in polynomial time via linear programming duality.
Lemma 5.14. Under the hypotheses of Lemma 5.12, if the edge weights are rational, a hitting set of size at most r h rh r h can be computed in time polynomial in n n n and the input bit length, with polynomial degree independent of r r r .
Proof. If r > n r > n r > n , return ∅ \varnothing ∅ . Otherwise, consider the dual of the maximum-score packing linear program: minimize ∑ e ∈ E ( G ) y e \sum_{e\in E(G)} y_e ∑ e ∈ E ( G ) y e subject to y e ≥ 0 y_e \ge0 y e ≥ 0 and ∑ e ∈ E ( ω ) y e ≥ s ( ω ) \sum_{e\in E(\omega)} y_e \ge s(\omega) ∑ e ∈ E ( ω ) y e ≥ s ( ω ) for all ω ∈ Ω \omega\in\Omega ω ∈ Ω . For a candidate y ≥ 0 y \ge0 y ≥ 0 and each edge e = u v e=uv e = uv , dynamic programming computes the minimum of ∑ f ∈ P ( w f + y f ) \sum_{f\in P}(w_f+y_f) ∑ f ∈ P ( w f + y f ) over u u u -to-v v v walks P P P of at most r − 1 r-1 r − 1 edges. A constraint with dominant edge e e e is violated if and only if this minimum is strictly less than w e − y e w_e-y_e w e − y e : any violating walk has original weight less than w e w_e w e , and shortcutting repeated vertices preserves the strict inequality (since w f + y f > 0 w_f+y_f > 0 w f + y f > 0 ) and yields a nonmetric simple cycle of length at most r r r , which must have length r r r by hypothesis.
Since y e = w e y_e=w_e y e = w e is feasible, we may restrict the dual to a rational box of polynomial bit complexity and compute an exact optimum y ∗ y^* y ∗ in polynomial time via the ellipsoid method [22 ] . If Ω = ∅ \Omega=\varnothing Ω = ∅ , then y ∗ = 0 y^*=0 y ∗ = 0 and ∅ \varnothing ∅ suffices. Otherwise, let z z z be the maximum-score, minimum-mass primal optimum from the proof of Lemma 5.12. Complementary slackness implies ∑ ω ∋ e z ω = 1 \sum_{\omega\ni e}z_\omega=1 ∑ ω ∋ e z ω = 1 whenever y e ∗ > 0 y_e^*>0 y e ∗ > 0 , so ∣ supp y ∗ ∣ ≤ r ∑ ω ∈ Ω z ω ≤ r h |\operatorname{supp} y^*| \le r\sum_{\omega\in\Omega} z_\omega\le rh ∣ supp y ∗ ∣ ≤ r ∑ ω ∈ Ω z ω ≤ r h , and every ω ∈ Ω \omega\in\Omega ω ∈ Ω meets supp y ∗ \operatorname{supp} y^* supp y ∗ because s ( ω ) > 0 s(\omega)>0 s ( ω ) > 0 .
Corollary 5.15. For every real C > 1 C > 1 C > 1 , a locally consistent partial matrix with rational specified entries in [ 1 , C ] [1,C] [ 1 , C ] and h h h holes admits a rational metric completion in [ 1 , C ] [1,C] [ 1 , C ] after changing at most ( M C − 1 ) h (M_C-1)h ( M C − 1 ) h specified entries, computable in time polynomial in n n n and the input bit length with degree independent of C C C (and without knowledge of C C C ).
Proof. Set R = max { 1 } ∪ { specified entries } ≤ C R = \max\{1\} \cup\{\text{specified entries}\} \le C R = max { 1 } ∪ { specified entries } ≤ C . If R = 1 R = 1 R = 1 , output the all-ones off-diagonal matrix. Otherwise apply Lemma 5.14 for 4 ≤ r ≤ min { n , ⌈ R ⌉ } 4 \le r \le\min\{n,\lceil R\rceil\} 4 ≤ r ≤ min { n , ⌈ R ⌉} and complete the remaining graph via B u v = min { R , d G ( u , v ) } B_{uv} = \min\{R,d_G(u,v)\} B uv = min { R , d G ( u , v )} for u ≠ v u \ne v u = v .
For n ≥ 2 n \ge2 n ≥ 2 and N = ( n 2 ) N = \binom{n}{2} N = ( 2 n ) , write dist H ( D , M n ) = 1 N min d ∈ M n ∣ { e : D e ≠ d e } ∣ = n n − 1 dist n ( D , M n ) \operatorname{dist}_{H}(D,\mathcal{M}_n) = \frac{1}{N}\min_{d\in\mathcal{M}_n}|\{e:D_e \ne d_e\}| = \frac{n}{n-1}\operatorname{dist}_{n}(D,\mathcal{M}_n) dist H ( D , M n ) = N 1 min d ∈ M n ∣ { e : D e = d e } ∣ = n − 1 n dist n ( D , M n ) for the edge-normalized Hamming distance. Clipping an arbitrary pseudometric to [ 1 , C ] [1,C] [ 1 , C ] preserves both the triangle inequality and agreement with entries in [ 1 , C ] [1,C] [ 1 , C ] , yielding the following transfer principle.
Lemma 5.16. For every D ∈ [ 1 , C ] ( n 2 ) D \in[1,C]^{\binom{n}{2}} D ∈ [ 1 , C ] ( 2 n ) , we have dist n ( D , M n [ 1 , C ] ) = dist n ( D , M n ) = dist n ( D , M ‾ n ) \operatorname{dist}_{n}(D,\mathcal{M}_n[1,C]) = \operatorname{dist}_{n}(D,\mathcal{M}_n) = \operatorname{dist}_{n}(D,\overline{\mathcal{M}}_n) dist n ( D , M n [ 1 , C ]) = dist n ( D , M n ) = dist n ( D , M n ) .
Proof. For any d ∈ M n d \in\mathcal{M}_n d ∈ M n , setting d ^ u v = min { C , max { 1 , d u v } } \widehat{d}_{uv} = \min\{C,\max\{1,d_{uv}\}\} d uv = min { C , max { 1 , d uv }} for u ≠ v u \ne v u = v and d ^ u u = 0 \widehat{d}_{uu} = 0 d uu = 0 preserves the triangle inequality (since max { 1 , d u w } + max { 1 , d w v } ≥ max { 2 , d u w + d w v } ≥ max { 1 , d u v } \max\{1,d_{uw}\}+\max\{1,d_{wv}\} \ge\max\{2,d_{uw}+d_{wv}\} \ge\max\{1,d_{uv}\} max { 1 , d u w } + max { 1 , d w v } ≥ max { 2 , d u w + d w v } ≥ max { 1 , d uv } and capping at C C C preserves the triangle inequality as in Lemma 5.8 ) without altering agreement with D ∈ [ 1 , C ] ( n 2 ) D \in[1,C]^{\binom{n}{2}} D ∈ [ 1 , C ] ( 2 n ) .
Combining Theorem 5.13 with Proposition 3.9 and Lemma 5.16 bounds the metric repair distance on [ 1 , C ] [1,C] [ 1 , C ] within a factor of 3 M C 3M_C 3 M C of the maximum size ν ( D ) \nu(D) ν ( D ) of an edge-disjoint packing of violating triangles.
Proposition 5.17 (Triangle packing bound for metric repair). For n ≥ 3 n \ge3 n ≥ 3 and D ∈ [ 1 , C ] ( n 2 ) D \in[1,C]^{\binom{n}{2}} D ∈ [ 1 , C ] ( 2 n ) ,
2 ν ( D ) n 2 ≤ dist n ( D , M n ) = dist n ( D , M n [ 1 , C ] ) ≤ 6 M C ν ( D ) n 2 . \frac{2\nu(D)}{n^2} \le\operatorname{dist}_{n}(D,\mathcal{M}_n) = \operatorname{dist}_{n}(D,\mathcal{M}_n[1,C]) \le\frac{6M_C\nu(D)}{n^2}. n 2 2 ν ( D ) ≤ dist n ( D , M n ) = dist n ( D , M n [ 1 , C ]) ≤ n 2 6 M C ν ( D ) .
Proof. The lower bound is Lemma 3.7 . For the upper bound, deleting all 3 p ≤ 3 ν ( D ) 3p \le3\nu(D) 3 p ≤ 3 ν ( D ) edges of a maximal edge-disjoint family of violating triangles leaves a locally consistent partial matrix, which Theorem 5.13 completes after at most 3 ( M C − 1 ) p 3(M_C-1)p 3 ( M C − 1 ) p further deletions; Lemma 5.16 equates the repair targets.
Remark 5.18 (Support selection and bounded cycle approximation). When C ≤ 3 C \le3 C ≤ 3 , Proposition 5.9 implies that the minimum number of metric repair edits equals the minimum size of an edge set hitting all violating triangles. Selecting an optimal hitting set is nevertheless NP-hard and APX-hard even for weights in { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } [20 ] (see also [10 ] for parameterized kernels). For any fixed C > 2 C > 2 C > 2 , repeatedly deleting the edges of a shortest nonmetric cycle (found via shortest paths and having length at most ⌈ C ⌉ \lceil C\rceil ⌈ C ⌉ ) and completing via Corollary 5.15 recovers the polynomial-time ⌈ C ⌉ \lceil C\rceil ⌈ C ⌉ -approximation specialization of [20 , 19 ] , complementing the range-independent O ( log n ) O(\log n) O ( log n ) -approximation of Cohen-Addad, Fan, Lee, and de Mesmay [13 ] .
Twin rigidity, completion obstructions, and logical independence
Whereas our pseudometric repairs in Lemmas 5.5 and 5.7 may identify distinct vertices, injective realization in trees or R d \mathbb{R}^{d} R d forbids zero off-diagonal distances. We now reformulate the deterministic collinear twin pair construction of Parnas and Ron [31 Section 7] as a locally consistent partial matrix with m m m holes to show that injectivity creates a completion obstruction for T + \mathcal{T}^{+} T + and E ( d ) , + \mathcal{E}^{(d),+} E ( d ) , + .
Lemma 5.19. Let m ≥ 3 m \ge3 m ≥ 3 and y 1 < ⋯ < y m y_1 < \cdots< y_m y 1 < ⋯ < y m . On V = [ m ] × [ 2 ] V = [m] \times[2] V = [ m ] × [ 2 ] , write i a = ( i , a ) i^a = (i,a) i a = ( i , a ) , leave the m m m pairs { i 1 , i 2 } \{i^1,i^2\} { i 1 , i 2 } within each class unspecified as holes, and set A i a , j b = ∣ y i − y j ∣ A_{i^a,j^b} = |y_i-y_j| A i a , j b = ∣ y i − y j ∣ for i ≠ j i \ne j i = j . Every complete matrix B ∈ T 2 m + ∪ E 2 m ( d ) , + B \in\mathcal{T}^{+}_{2m} \cup\mathcal{E}^{(d),+}_{2m} B ∈ T 2 m + ∪ E 2 m ( d ) , + differs from A A A on at least m ( m − 1 ) / 3 m(m-1)/3 m ( m − 1 ) /3 specified edges, and hence satisfies dist ( A ) ≥ m − 1 6 m \operatorname{dist}(A) \ge\frac{m-1}{6m} dist ( A ) ≥ 6 m m − 1 .
Proof. For $1 \le j < i < k \le m$ and a , b ∈ { 1 , 2 } a,b \in\{1,2\} a , b ∈ { 1 , 2 } , consider the four-vertex witness W = { j a , k b , i 1 , i 2 } W = \{j^{a}, k^{b}, i^{1}, i^{2}\} W = { j a , k b , i 1 , i 2 } . If B B B agrees with A A A on all five specified edges of W W W , then B j a , i 1 = B j a , i 2 = y i − y j B_{j^{a},i^{1}} = B_{j^{a},i^{2}} = y_i-y_j B j a , i 1 = B j a , i 2 = y i − y j , B i 1 , k b = B i 2 , k b = y k − y i B_{i^{1},k^{b}} = B_{i^{2},k^{b}} = y_k-y_i B i 1 , k b = B i 2 , k b = y k − y i , and B j a , k b = y k − y j B_{j^{a},k^{b}} = y_k-y_j B j a , k b = y k − y j . In T 2 m \mathcal{T}_{2m} T 2 m , the three opposite-edge sums on W W W are y k − y j + B i 1 , i 2 y_k-y_j+B_{i^{1},i^{2}} y k − y j + B i 1 , i 2 and twice y k − y j y_k-y_j y k − y j , so the four-point condition forces B i 1 , i 2 ≤ 0 B_{i^{1},i^{2}} \le0 B i 1 , i 2 ≤ 0 , a contradiction. In E 2 m ( d ) , + \mathcal{E}^{(d),+}_{2m} E 2 m ( d ) , + , equality in the triangle inequality on { j a , i 1 , k b } \{j^{a},i^{1},k^{b}\} { j a , i 1 , k b } and { j a , i 2 , k b } \{j^{a},i^{2},k^{b}\} { j a , i 2 , k b } places both ϕ ( i 1 ) \phi(i^{1}) ϕ ( i 1 ) and ϕ ( i 2 ) \phi(i^{2}) ϕ ( i 2 ) at the unique point on the segment [ ϕ ( j a ) , ϕ ( k b ) ] [\phi(j^{a}),\phi(k^{b})] [ ϕ ( j a ) , ϕ ( k b )] at distance y i − y j y_i-y_j y i − y j from ϕ ( j a ) \phi(j^{a}) ϕ ( j a ) , forcing B i 1 , i 2 = 0 B_{i^{1},i^{2}}=0 B i 1 , i 2 = 0 , again a contradiction.
Consequently, B B B must differ from A A A on at least one specified edge in each of the 4 ( m 3 ) 4\binom{m}{3} 4 ( 3 m ) witnesses. A specified edge between classes p < q p<q p < q belongs to 2 ( p − 1 ) + 2 ( m − q ) + ( q − p − 1 ) ≤ 2 ( m − 2 ) 2(p-1)+2(m-q)+(q-p-1) \le2(m-2) 2 ( p − 1 ) + 2 ( m − q ) + ( q − p − 1 ) ≤ 2 ( m − 2 ) witnesses, so double counting yields at least 4 ( m 3 ) / ( 2 ( m − 2 ) ) = m ( m − 1 ) / 3 4\binom{m}{3}/(2(m-2)) = m(m-1)/3 4 ( 3 m ) / ( 2 ( m − 2 )) = m ( m − 1 ) /3 specified discrepancies, or cdist ( A ) ≥ ( m − 1 ) / ( 6 m ) \operatorname{cdist}(A) \ge(m-1)/(6m) cdist ( A ) ≥ ( m − 1 ) / ( 6 m ) after normalizing by 2 / ( 2 m ) 2 2/(2m)^2 2/ ( 2 m ) 2 .
Theorem 5.20 (Injective tree and Euclidean completion obstructions). The strict predicates Φ t r e e + \Phi^+_{\mathrm{tree}} Φ tree + and Φ E u c ( d ) , + \Phi^{(d),+}_{\mathrm{Euc}} Φ Euc ( d ) , + admit completion obstructions and are not removable. Consequently, neither T + \mathcal{T}^{+} T + nor E ( d ) , + \mathcal{E}^{(d),+} E ( d ) , + has a constant-query one-sided tester. 3
Proof. Apply Lemma 5.19 with y i = i y_i=i y i = i and m ≥ max { 6 , d + 3 } m \ge\max\{6,d+3\} m ≥ max { 6 , d + 3 } . Every fully specified subset contains at most one vertex per twin class and embeds injectively on a line, while the hole density is m / ( 2 m ) 2 = 1 / ( 4 m ) → 0 m/(2m)^2 = 1/(4m) \to0 m / ( 2 m ) 2 = 1/ ( 4 m ) → 0 and cdist ( A ) ≥ ( m − 1 ) / ( 6 m ) ≥ 1 / 8 \operatorname{cdist}(A) \ge(m-1)/(6m) \ge1/8 cdist ( A ) ≥ ( m − 1 ) / ( 6 m ) ≥ 1/8 . Corollaries 3.12 and 3.11 complete the proof.
Finally, combining our results from Sections 4 and 5 demonstrates that neither structural condition in Theorem 3.10 implies the other.
Corollary 5.22 (Logical independence of the structural conditions). Packing amplification does not imply completion stability, and completion stability does not imply packing amplification.
Proof. For Λ = [ 1 , C ] \Lambda=[1,C] Λ = [ 1 , C ] with C > 2 C>2 C > 2 , the metric predicate Φ m e t \Phi_{\mathrm{met}} Φ met is completion stable by Theorem 5.13 (with Γ = 0 \Gamma=0 Γ = 0 for 2 < C ≤ 3 2<C\le3 2 < C ≤ 3 by Proposition 5.9), but fails packing amplification by Theorem 4.11. Conversely, on Λ = R ≥ 0 \Lambda= \mathbb{R}_{\ge0} Λ = R ≥ 0 or Λ = ( 0 , ∞ ) \Lambda= (0,\infty) Λ = ( 0 , ∞ ) , the strict predicates Φ t r e e + \Phi_{\mathrm{tree}}^{+} Φ tree + and Φ E u c ( d ) , + \Phi_{\mathrm{Euc}}^{(d),+} Φ Euc ( d ) , + satisfy packing amplification by Corollary 4.9, but fail completion stability by Theorem 5.20 .
Quantitative testing bounds
We establish quantitative query complexity bounds for testing our geometric and metric families. We first combine our packing and completion bounds from § 4 and § 5 to obtain explicit constant-query one-sided testers for all four removable geometric families: ultrametrics, strict ultrametrics, tree pseudometrics, and d d d -dimensional Euclidean pseudometrics (Corollary 6.1). Turning to general metrics, for which Bao, Kannan, and Waingarten [9 ] proved a nonadaptive one-sided upper bound of O ( n 2 / 3 / ϵ 4 / 3 ) O(n^{2/3}/\epsilon^{4/3}) O ( n 2/3 / ϵ 4/3 ) and a nonadaptive one-sided lower bound of Ω ( n 2 / 3 − o ( 1 ) ) \Omega(n^{2/3-o(1)}) Ω ( n 2/3 − o ( 1 ) ) at vanishing proximity ϵ = n − o ( 1 ) \epsilon= n^{-o(1)} ϵ = n − o ( 1 ) , we introduce a signed noise perturbation scheme on robust metric faces (Lemmas 6.3 to 6.5 ) and pair it with density sensitive submatrix sampling and asymmetric faces to determine the sharp nonadaptive one-sided and two-sided query complexity Θ C ( F ( n , ϵ ) ) \Theta_C(F(n,\epsilon)) Θ C ( F ( n , ϵ )) on [ 1 , C ] [1,C] [ 1 , C ] for C > 2 C>2 C > 2 across all four proximity regimes of ( n , ϵ ) (n,\epsilon) ( n , ϵ ) (Theorem 6.8 ). Next, we introduce a contextual blow-up of our robust faces that prevents adaptive coordinate recovery, establishing an adaptive two-sided lower bound of Ω C ( n / log n ) \Omega_C(\sqrt{n/\log n}) Ω C ( n / log n ) queries (Theorem 6.11 ). Finally, we apply our clipping equivalence (Lemma 5.16 ) to transfer both the nonadaptive two-sided lower bound Ω ( F ( n , ϵ ) ) \Omega(F(n,\epsilon)) Ω ( F ( n , ϵ )) and the adaptive lower bound Ω ( n / log n ) \Omega(\sqrt{n/\log n}) Ω ( n / log n ) to unrestricted metrics and pseudometrics (Theorem 6.12 ).
Quantitative testing of removable geometric families
Combining Proposition 3.9 and Theorem 3.4 with the bounds of § 4 and § 5 gives explicit query bounds for all four removable geometric families.
Corollary 6.1 (Quantitative geometric testers). For every 0 < ϵ ≤ 1 0 < \epsilon\le1 0 < ϵ ≤ 1 , the removal moduli of U \mathcal{U} U , T \mathcal{T} T , and E ( d ) \mathcal{E}^{(d)} E ( d ) satisfy
ρ u l t ( ϵ ) ≥ ϵ 2 9600 , ρ t r e e ( ϵ ) ≥ min { 1 1820 , 3 1600 ( ϵ 168 ) 2 } , ρ E u c ( d ) ( ϵ ) ≥ min { δ d , ( ϵ C d ) d + 2 } . \rho_{\mathrm{ult}}(\epsilon) \ge\frac{\epsilon^2}{9600}, \qquad\rho_{\mathrm{tree}}(\epsilon) \ge\min\left\{\frac{1}{1820},\frac{3}{1600}\left(\frac{\epsilon}{168}\right)^2\right\}, \qquad\rho_{\mathrm{Euc}}^{(d)}(\epsilon) \ge\min\left\{\delta_d,\left(\frac{\epsilon}{C_d}\right)^{d+2}\right\}. ρ ult ( ϵ ) ≥ 9600 ϵ 2 , ρ tree ( ϵ ) ≥ min { 1820 1 , 1600 3 ( 168 ϵ ) 2 } , ρ Euc ( d ) ( ϵ ) ≥ min { δ d , ( C d ϵ ) d + 2 } . where C d C_d C d and δ d \delta_d δ d are as in Lemma 4.6 ; for strict ultrametrics U + \mathcal{U}^{+} U + , we have ρ u l t + ( ϵ ) ≥ ϵ 2 / 9600 \rho_{\mathrm{ult}+}(\epsilon) \ge\epsilon^2/9600 ρ ult + ( ϵ ) ≥ ϵ 2 /9600 on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) and ρ u l t + ( ϵ ) ≥ ϵ 2 / 86400 \rho_{\mathrm{ult}+}(\epsilon) \ge\epsilon^2/86400 ρ ult + ( ϵ ) ≥ ϵ 2 /86400 on R ≥ 0 \mathbb{R}_{\ge0} R ≥ 0 . Consequently, U \mathcal{U} U , U + \mathcal{U}^{+} U + , and T \mathcal{T} T admit one-sided O ( ϵ − 2 ) O(\epsilon^{-2}) O ( ϵ − 2 ) -query ϵ \epsilon ϵ -testers, and E ( d ) \mathcal{E}^{(d)} E ( d ) admits a one-sided O d ( ϵ − ( d + 2 ) ) O_d(\epsilon^{-(d+2)}) O d ( ϵ − ( d + 2 ) ) -query ϵ \epsilon ϵ -tester.
Proof. By Proposition 3.9 , Lemma 5.2 gives dist n ( D , U n ) ≤ 24 ν ( D ) / n 2 \operatorname{dist}_n(D,\mathcal{U}_n) \le24\nu(D)/n^2 dist n ( D , U n ) ≤ 24 ν ( D ) / n 2 , Corollary 5.3 gives dist n ( D , U n + ) ≤ 36 ν u l t + ( D ) / n 2 \operatorname{dist}_n(D,\mathcal{U}^{+}_n) \le36\nu_{\mathrm{ult}+}(D)/n^2 dist n ( D , U n + ) ≤ 36 ν ult + ( D ) / n 2 on R ≥ 0 \mathbb{R}_{\ge0} R ≥ 0 , and Lemma 5.5 gives dist n ( D , T n ) ≤ 168 ν ( D ) / n 2 \operatorname{dist}_n(D,\mathcal{T}_n) \le168\nu(D)/n^2 dist n ( D , T n ) ≤ 168 ν ( D ) / n 2 . Substituting the resulting packing lower bounds α = ϵ / 24 \alpha= \epsilon/24 α = ϵ /24 , ϵ / 36 \epsilon/36 ϵ /36 , and ϵ / 168 \epsilon/168 ϵ /168 into Lemmas 4.1 and 4.4 and Proposition 4.8 (with Δ u l t + ( α ) ≥ 3 α 2 / 200 \Delta_{\mathrm{ult}+}(\alpha) \ge3\alpha^2/200 Δ ult + ( α ) ≥ 3 α 2 /200 ) yields the stated moduli for U \mathcal{U} U , U + \mathcal{U}^{+} U + , and T \mathcal{T} T , while Corollary 4.7 gives the modulus for E ( d ) \mathcal{E}^{(d)} E ( d ) . Theorem 3.4 converts each removal modulus into the claimed one-sided query bound.
Remark 6.2 (Comparison with prior geometric testing bounds). For ultrametrics and tree pseudometrics, Parnas and Ron [31 ] gave nonadaptive O ( ϵ − 6 ) O(\epsilon^{-6}) O ( ϵ − 6 ) -query testers, which Bao, Kannan, and Waingarten [9 ] improved to O ~ ( ϵ − 2 ) \widetilde{O}(\epsilon^{-2}) O ( ϵ − 2 ) queries on O ~ ( ϵ − 1 ) \widetilde{O}(\epsilon^{-1}) O ( ϵ − 1 ) sampled vertices alongside an Ω ( ϵ − 1 ) \Omega(\epsilon^{-1}) Ω ( ϵ − 1 ) vertex sample lower bound and an Ω ( ϵ − 4 / 3 ) \Omega(\epsilon^{-4/3}) Ω ( ϵ − 4/3 ) two-sided query lower bound. Corollary 6.1 removes the logarithmic factors from the query bound of [9 ] via uniform k k k -set sampling (and applying our linear completion stability bounds to an induced submatrix on O ( ϵ − 1 log ( 1 / ϵ ) ) O(\epsilon^{-1}\log(1/\epsilon)) O ( ϵ − 1 log ( 1/ ϵ )) vertices likewise recovers their single-submatrix sample bound). For d d d -dimensional Euclidean pseudometrics, our O d ( ϵ − ( d + 2 ) ) O_d(\epsilon^{-(d+2)}) O d ( ϵ − ( d + 2 ) ) bound reflects the ( d + 3 ) (d+3) ( d + 3 ) -point proximity-oblivious [23 ] removal modulus; when larger submatrices are queried, better ϵ \epsilon ϵ -dependence is achieved by the O ~ ( d 2 / ϵ 2 ) \widetilde{O}(d^2/\epsilon^2) O ( d 2 / ϵ 2 ) -query tester of [31 ] and the O ( d 2 / ϵ 2 ) O(d^2/\epsilon^2) O ( d 2 / ϵ 2 ) -query tester of Krauthgamer and Sasson [27 ] (see also Onak [30 ] ).
Signed noise on robust metric faces
To convert our edge-disjoint tight-triangle constructions into two-sided testing lower bounds, we introduce a real-valued additive counterpart to the F 2 \mathbb{F}_2 F 2 -parity lifting of Alon, Kaufman, Krivelevich, and Ron [3 Section 6.1] for triangle-freeness. Working directly on weighted matrices without vertex blow-up, we perturb the three edges of each designated tight triangle by correlated uniform shifts ( U , V , U + V ∓ 1 ) η (U,V,U+V\mp1)\eta ( U , V , U + V ∓ 1 ) η over { − M , … , M } η \{-M,\ldots,M\}\eta { − M , … , M } η . Because any two edges of a selected triangle have nearly identical joint distributions under the two signs (an additive analogue of the Independence Observation of [3 ] ), a stopped transcript hybrid argument reduces two-sided distinguishing to the exposure event F A F_{\mathcal{A}} F A of querying all three edges of some selected triangle.
Lemma 6.3. Suppose a rational metric A ∈ [ 1 , C 0 ] ( [ n ] 2 ) A \in[1,C_0]^{\binom{[n]}{2}} A ∈ [ 1 , C 0 ] ( 2 [ n ] ) has an edge-disjoint family H \mathcal{H} H of h h h designated tight triangles, every other triangle inequality has slack at least n − K n^{-K} n − K , every selected edge has endpoint margin at least n − K n^{-K} n − K , and all entries have O C ( log n ) O_C(\log n) O C ( log n ) -bit rational representations for a fixed K K K . Fix an integer J > K + 2 J>K+2 J > K + 2 and set δ = n − J / 1000 \delta=n^{-J}/1000 δ = n − J /1000 , M = n 10 M=n^{10} M = n 10 , and η = δ / M \eta=\delta/M η = δ / M . There exist finite-support distributions μ − \mu_- μ − and μ + \mu_+ μ + , obtained by independent triangle perturbations followed by uniform vertex relabeling, such that:
(1) all entries lie in [ 1 , C 0 ] [1,C_0] [ 1 , C 0 ] and have O C ( log n ) O_C(\log n) O C ( log n ) -bit rational representations (with constants allowed to depend on K , J K,J K , J );
(2) every instance in supp μ − \operatorname{supp}\mu_- supp μ − is metric;
(3) before relabeling, every instance in supp μ + \operatorname{supp}\mu_+ supp μ + violates exactly the designated tight inequalities of H \mathcal{H} H ;
(4) every instance D ∈ supp μ + D\in\operatorname{supp}\mu_+ D ∈ supp μ + satisfies dist n ( D , M n ) = 2 h / n 2 \operatorname{dist}_n(D,\mathcal{M}_n)=2h/n^2 dist n ( D , M n ) = 2 h / n 2 and dist H ( D , M n ) = h / N \operatorname{dist}_{H}(D,\mathcal{M}_n)=h/N dist H ( D , M n ) = h / N .
Proof. For each triangle H ∈ H H\in\mathcal{H} H ∈ H , independently draw U H , V H U_H,V_H U H , V H uniformly from { − M , − M + 1 , … , M } η \{-M,-M+1,\ldots,M\}\eta { − M , − M + 1 , … , M } η , add U H U_H U H and V H V_H V H to the two short edges of H H H , and add U H + V H ∓ η U_H+V_H\mp\eta U H + V H ∓ η to the designated long edge under μ ∓ \mu_{\mp} μ ∓ . Each entry changes by at most 3 δ 3\delta 3 δ and each formerly strict slack changes by at most 9 δ < n − K 9\delta<n^{-K} 9 δ < n − K , while the designated slack on each H ∈ H H\in\mathcal{H} H ∈ H becomes ∓ η \mp\eta ∓ η . Thus μ − \mu_- μ − is supported on metrics and μ + \mu_+ μ + violates precisely the h h h edge-disjoint triangles in H \mathcal{H} H , requiring exactly h h h edge edits (achieved by restoring the h h h long edges under μ − \mu_- μ − ). □
Lemma 6.4. For a single triangle in Lemma 6.3 , any adaptive procedure observing at most two of its edges (even with sign-independent side information) has transcript total variation distance at most 6 / ( 2 M + 1 ) 6/(2M+1) 6/ ( 2 M + 1 ) between μ − \mu_- μ − and μ + \mu_+ μ + . For a fixed projection onto at most two edges, the total variation distance is at most 2 / ( 2 M + 1 ) 2/(2M+1) 2/ ( 2 M + 1 ) .
Proof. After subtracting the baseline entries and dividing by η \eta η , the three triangle coordinates are ( U , V , U + V − 1 ) (U,V,U+V-1) ( U , V , U + V − 1 ) under μ − \mu_- μ − and ( U , V , U + V + 1 ) (U,V,U+V+1) ( U , V , U + V + 1 ) under μ + \mu_+ μ + , where U , V ∈ { − M , … , M } U,V\in\{-M,\ldots,M\} U , V ∈ { − M , … , M } are independent and uniform. The marginal on ( U , V ) (U,V) ( U , V ) is identical under both signs, while conditional on U U U (or on V V V ) the third coordinate is uniform on an interval shifted by 2 2 2 , giving total variation 2 / ( 2 M + 1 ) 2/(2M+1) 2/ ( 2 M + 1 ) . Conditioning on the side information and internal randomness fixes the first queried coordinate, and a union bound over the three possible two-coordinate pairs bounds the adaptive transcript variation by 6 / ( 2 M + 1 ) 6/(2M+1) 6/ ( 2 M + 1 ) .
Lemma 6.5. Let A A A query the distributions of Lemma 6.3 , and let F A F_A F A be the event that A A A queries all three edges of some selected triangle in H \mathcal{H} H . Then
TV ( Π A ( μ − ) , Π A ( μ + ) ) ≤ Pr ( F A ) + Pr ( F A ) + 6 h 2 M + 1 . \operatorname{TV}(\Pi_A(\mu_-),\Pi_A(\mu_+)) \leq\Pr(F_A) + \Pr(F_A) + \frac{6h}{2M+1}. TV ( Π A ( μ − ) , Π A ( μ + )) ≤ Pr ( F A ) + Pr ( F A ) + 2 M + 1 6 h . and the same bound holds when ( A , H ) (A,\mathcal{H}) ( A , H ) is drawn from a sign-independent distribution with ∣ H ∣ = h |\mathcal{H}|=h ∣ H ∣ = h almost surely. If A A A is nonadaptive, then TV ( Π A ( μ − ) , Π A ( μ + ) ) ≤ Pr ( F A ) + 2 h 2 M + 1 \operatorname{TV}(\Pi_A(\mu_-),\Pi_A(\mu_+)) \leq\Pr(F_A) + \frac{2h}{2M+1} TV ( Π A ( μ − ) , Π A ( μ + )) ≤ Pr ( F A ) + 2 M + 1 2 h , where F A F_A F A depends only on the query set, base template, and relabeling.
Proof. Condition on the base template and relabeling, and modify A A A to halt immediately before any query that would reveal the third edge of a triangle in H \mathcal{H} H . Replacing the h h h independent triangle laws one by one changes the stopped transcript distribution by at most 6 / ( 2 M + 1 ) 6/(2M+1) 6/ ( 2 M + 1 ) per triangle by Lemma 6.4 , and the unstopped transcript agrees with the stopped transcript outside F A F_A F A under each sign. For nonadaptive A A A , conditioning on the random seed fixes the queried edges; outside F A F_A F A , each triangle is observed on a fixed set of at most two edges, so the fixed-projection bound of Lemma 6.4 gives 2 h / ( 2 M + 1 ) 2h/(2M+1) 2 h / ( 2 M + 1 ) .
Density-sensitive sampling and asymmetric faces
To match our nonadaptive lower bounds across all proximity regimes, we pair a second-moment submatrix sampling bound on the upper-bound side with asymmetric and single-center robust face constructions on the lower-bound side.
Lemma 6.6. Let S S S be an edge-disjoint family of m ≥ γ n 2 m \geq\gamma n^2 m ≥ γ n 2 triangles on [ n ] [n] [ n ] . For a uniformly random r r r -set U ⊆ [ n ] U \subseteq[n] U ⊆ [ n ] with 6 ≤ r < n 6 \leq r < n 6 ≤ r < n , we have Pr [ ∃ T ∈ S : T ⊆ U ] ≥ ( 8 n 3 γ r 3 + 1 + 12 r min { 1 2 γ , n } ) − 1 \Pr[\exists T \in S : T \subseteq U] \geq\left(\frac{8n^3}{\gamma r^3}+1+\frac{12}{r}\min\left\{\frac{1}{2\gamma},n\right\}\right)^{-1} Pr [ ∃ T ∈ S : T ⊆ U ] ≥ ( γ r 3 8 n 3 + 1 + r 12 min { 2 γ 1 , n } ) − 1 . In particular, this probability is at least 2 / 5 2/5 2/5 whenever 6 ≤ r < n 6 \leq r < n 6 ≤ r < n , r ≥ 2 ( n / γ ) 1 / 3 r \geq2(n/\gamma)^{1/3} r ≥ 2 ( n / γ ) 1/3 , and r ≥ 12 / γ r \geq12/\gamma r ≥ 12/ γ .
Proof. Let X = ∣ { T ∈ S : T ⊆ U } ∣ X = |\{T \in S : T \subseteq U\}| X = ∣ { T ∈ S : T ⊆ U } ∣ and p j = ( r ) j / ( n ) j p_j = (r)_j/(n)_j p j = ( r ) j / ( n ) j , so μ = E X = m p 3 ≥ γ n 2 ( r − 2 ) 3 / n 3 ≥ γ r 3 / ( 8 n ) \mu= \mathbb{E}X = mp_3 \geq\gamma n^2(r-2)^3/n^3 \geq\gamma r^3/(8n) μ = E X = m p 3 ≥ γ n 2 ( r − 2 ) 3 / n 3 ≥ γ r 3 / ( 8 n ) . Each vertex belongs to at most Δ ≤ min { ( n − 1 ) / 2 , m } \Delta\leq\min\{(n-1)/2,m\} Δ ≤ min {( n − 1 ) /2 , m } triangles of S S S , so there are at most 3 m Δ 3m\Delta 3 m Δ ordered pairs of intersecting triangles. Since vertex-disjoint triangles have joint inclusion probability p 6 ≤ p 3 2 p_6 \leq p_3^2 p 6 ≤ p 3 2 , we have E X 2 ≤ μ + μ 2 + 3 m Δ p 5 \mathbb{E}X^2 \leq\mu+\mu^2+3m\Delta p_5 E X 2 ≤ μ + μ 2 + 3 m Δ p 5 . Using p 5 / p 3 2 ≤ 4 n / r p_5/p_3^2 \leq4n/r p 5 / p 3 2 ≤ 4 n / r for n > r ≥ 6 n>r\geq6 n > r ≥ 6 gives
E X 2 μ 2 ≤ 8 n γ r 3 + 1 + 12 Δ n r m ≤ 8 n γ r 3 + 1 + 12 r min { 1 2 γ , n } , \frac{\mathbb{E}X^2}{\mu^2} \leq\frac{8n}{\gamma r^3}+1+\frac{12\Delta n}{rm} \leq\frac{8n}{\gamma r^3}+1+\frac{12}{r}\min\left\{\frac{1}{2\gamma},n\right\}, μ 2 E X 2 ≤ γ r 3 8 n + 1 + r m 12Δ n ≤ γ r 3 8 n + 1 + r 12 min { 2 γ 1 , n } ,
and the Paley–Zygmund inequality Pr [ X > 0 ] ≥ μ 2 / E X 2 \Pr[X>0] \geq\mu^2/\mathbb{E}X^2 Pr [ X > 0 ] ≥ μ 2 / E X 2 gives the result.
Lemma 6.7. Fix C > 2 C>2 C > 2 and let C 0 C_0 C 0 be as in Lemma 4.10 . For sufficiently large n n n , put m = ⌊ n / 4 ⌋ m=\lfloor n/4\rfloor m = ⌊ n /4 ⌋ . Given either (i) 1 ≤ a ≤ m 1\leq a\leq m 1 ≤ a ≤ m and h = a m h=am h = am , or (ii) a = 1 a=1 a = 1 and any 1 ≤ h ≤ ⌊ ( n − 1 ) / 2 ⌋ 1\leq h\leq\lfloor(n-1)/2\rfloor 1 ≤ h ≤ ⌊( n − 1 ) /2 ⌋ , there is a rational metric A ∈ [ 1 , C 0 ] ( n 2 ) A\in[1,C_0]^{\binom{n}{2}} A ∈ [ 1 , C 0 ] ( 2 n ) with an edge-disjoint family H \mathcal{H} H of h h h tight triangles such that:
every T ∈ H T\in\mathcal{H} T ∈ H contains one of a designated centers, and the triangles of H \mathcal{H} H through each center form a matching of size h / a h/a h / a on the remaining vertices;
all other triangle inequalities and endpoint margins of selected edges are at least n − 3 n^{-3} n − 3 , and all entries are O C ( log n ) O_C(\log n) O C ( log n ) -bit rationals.
Proof. For h = a m h=am h = am with 1 ≤ a ≤ m 1\leq a\leq m 1 ≤ a ≤ m , take the construction of Lemma 4.10 on 4 m − 1 4m-1 4 m − 1 vertices, retain a a a vertices of Y Y Y together with all of X X X and Z Z Z , and pad to n n n vertices with distance 3 / 2 3/2 3/2 ; for each retained y j y_j y j , the pairs { x k − j , z k } \{x_{k-j},z_k\} { x k − j , z k } (k ∈ [ m ] k \in[m] k ∈ [ m ] ) form a matching of size m m m . For a single center with 1 ≤ h ≤ ⌊ ( n − 1 ) / 2 ⌋ 1 \le h \le\lfloor(n-1)/2\rfloor 1 ≤ h ≤ ⌊( n − 1 ) /2 ⌋ , set b = 1 + 4 ρ b=1+4\rho b = 1 + 4 ρ and C 0 = 2 + 10 ρ C_0=2+10\rho C 0 = 2 + 10 ρ as in Lemma 4.10 , assign weight b b b to the 2 h 2h 2 h edges from the center to the leaves, weight 2 b 2b 2 b to the h h h edges between matched leaves, and weight 3 / 2 3/2 3/2 to all remaining edges; the h h h matched triangles satisfy b + b = 2 b b+b=2b b + b = 2 b and all other slacks and endpoint margins are bounded below by positive constants depending only on C C C .
The full nonadaptive complexity on a bounded range
Write Q n a ( 1 ) ( n , ϵ ; C ) Q_{\mathrm{na}}^{(1)}(n,\epsilon;C) Q na ( 1 ) ( n , ϵ ; C ) and Q n a ( 2 ) ( n , ϵ ; C ) Q_{\mathrm{na}}^{(2)}(n,\epsilon;C) Q na ( 2 ) ( n , ϵ ; C ) for the nonadaptive one-sided and two-sided query complexities of metric testing on [ 1 , C ] [1,C] [ 1 , C ] . For n ≥ 3 n \ge3 n ≥ 3 and 0 < ϵ ≤ 1 0 < \epsilon\le1 0 < ϵ ≤ 1 , define the rate function
F ( n , ϵ ) = { n 2 , 0 < ϵ ≤ n − 2 , n / ϵ , n − 2 < ϵ ≤ n − 1 , n / ϵ , n − 1 ≤ ϵ ≤ n − 1 / 2 , ( n / ϵ ) 2 / 3 , n − 1 / 2 ≤ ϵ ≤ 1. F(n,\epsilon)=
\begin{cases}
n^2, & 0 < \epsilon\le n^{-2},\\
n/\sqrt{\epsilon}, & n^{-2} < \epsilon\le n^{-1},\\
\sqrt{n/\epsilon}, & n^{-1} \le\epsilon\le n^{-1/2},\\
(n/\epsilon)^{2/3}, & n^{-1/2} \le\epsilon\le1.
\end{cases} F ( n , ϵ ) = ⎩ ⎨ ⎧ n 2 , n / ϵ , n / ϵ , ( n / ϵ ) 2/3 , 0 < ϵ ≤ n − 2 , n − 2 < ϵ ≤ n − 1 , n − 1 ≤ ϵ ≤ n − 1/2 , n − 1/2 ≤ ϵ ≤ 1.
Theorem 6.8 (Sharp nonadaptive complexity on a known bounded range). For every fixed C > 1 C > 1 C > 1 , we have Q n a ( 1 ) ( n , ϵ ; C ) = O C ( F ( n , ϵ ) ) Q_{\mathrm{na}}^{(1)}(n,\epsilon;C)=O_C(F(n,\epsilon)) Q na ( 1 ) ( n , ϵ ; C ) = O C ( F ( n , ϵ )) for all n ≥ 3 n \ge3 n ≥ 3 and 0 < ϵ ≤ 1 0 < \epsilon\le1 0 < ϵ ≤ 1 (and Q n a ( 1 ) ( n , ϵ ; C ) = 0 Q_{\mathrm{na}}^{(1)}(n,\epsilon;C)=0 Q na ( 1 ) ( n , ϵ ; C ) = 0 when C ≤ 2 C \le2 C ≤ 2 ). Conversely, for ϵ 0 = 1 / 80 \epsilon_0=1/80 ϵ 0 = 1/80 and every fixed C > 2 C>2 C > 2 , there exist constants A C > 0 A_C>0 A C > 0 , n 0 ( C ) n_0(C) n 0 ( C ) , and an absolute constant c > 0 c>0 c > 0 such that
c F ( n , ϵ ) ≤ Q n a ( 2 ) ( n , ϵ ; C ) ≤ Q n a ( 1 ) ( n , ϵ ; C ) ≤ A C F ( n , ϵ ) cF(n,\epsilon) \le Q_{\mathrm{na}}^{(2)}(n,\epsilon;C) \le Q_{\mathrm{na}}^{(1)}(n,\epsilon;C) \le A_CF(n,\epsilon) c F ( n , ϵ ) ≤ Q na ( 2 ) ( n , ϵ ; C ) ≤ Q na ( 1 ) ( n , ϵ ; C ) ≤ A C F ( n , ϵ ) for all n ≥ n 0 ( C ) n \ge n_0(C) n ≥ n 0 ( C ) and 0 < ϵ ≤ ϵ 0 0 < \epsilon\le\epsilon_0 0 < ϵ ≤ ϵ 0 . Moreover, the hard instances have O C ( log n ) O_C(\log n) O C ( log n ) -bit rational entries, and the bounds hold whether repairs are restricted to [ 1 , C ] [1,C] [ 1 , C ] or allowed arbitrary positive metric values.
Proof. When C ≤ 2 C \le2 C ≤ 2 , every matrix in [ 1 , C ] [1,C] [ 1 , C ] is metric. For C > 2 C > 2 C > 2 , set a C = 6 M C a_C=6M_C a C = 6 M C and γ = ϵ / a C \gamma=\epsilon/a_C γ = ϵ / a C . By Proposition 5.17, every ϵ \epsilon ϵ -far input has ν ( D ) > γ n 2 \nu(D)>\gamma n^2 ν ( D ) > γ n 2 . By Lemma 6.6 , for 6 ≤ r < n 6 \le r<n 6 ≤ r < n , repeating a uniform r r r -submatrix check O ( 1 + n γ r 3 + 1 r min { γ − 1 , n } ) O\left(1+\frac{n}{\gamma r^3}+\frac{1}{r}\min\{\gamma^{-1},n\}\right) O ( 1 + γ r 3 n + r 1 min { γ − 1 , n } ) times yields a nonadaptive one-sided tester using O ( n γ r + r 2 + r min { γ − 1 , n } ) O\left(\frac{n}{\gamma r}+r^2+r\min\{\gamma^{-1},n\}\right) O ( γ r n + r 2 + r min { γ − 1 , n } ) queries. For n ≥ 36 n \ge36 n ≥ 36 , choosing r r r up to rounding and truncation at n n n (using full inspection whenever n < 36 n<36 n < 36 , rounding reaches n n n , or γ ≤ n − 2 \gamma\le n^{-2} γ ≤ n − 2 ) with r ≍ ( n / γ ) 1 / 3 r\asymp(n/\gamma)^{1/3} r ≍ ( n / γ ) 1/3 for γ ≥ n − 1 / 2 \gamma\ge n^{-1/2} γ ≥ n − 1/2 , r ≍ n r\asymp\sqrt{n} r ≍ n for n − 1 ≤ γ ≤ n − 1 / 2 n^{-1}\le\gamma\le n^{-1/2} n − 1 ≤ γ ≤ n − 1/2 , and r ≍ γ − 1 / 2 r\asymp\gamma^{-1/2} r ≍ γ − 1/2 for n − 2 ≤ γ ≤ n − 1 n^{-2}\le\gamma\le n^{-1} n − 2 ≤ γ ≤ n − 1 gives query complexity O ( F ( n , γ ) ) ≤ O ( a C F ( n , ϵ ) ) O(F(n,\gamma))\le O(a_CF(n,\epsilon)) O ( F ( n , γ )) ≤ O ( a C F ( n , ϵ )) .
For the lower bound, we apply Lemmas 6.3 and 6.5 with K = 3 K=3 K = 3 , J = 6 J=6 J = 6 , and M = n 10 M=n^{10} M = n 10 to three face families, each having h ≥ ϵ n 2 h\ge\epsilon n^2 h ≥ ϵ n 2 selected triangles so that every instance in supp μ + \operatorname{supp}\mu_+ supp μ + is at distance 2 h / n 2 ≥ 2 ϵ > ϵ 2h/n^2\ge2\epsilon>\epsilon 2 h / n 2 ≥ 2 ϵ > ϵ from M n \mathcal{M}_n M n (and from M n [ 1 , C ] \mathcal{M}_n[1,C] M n [ 1 , C ] by Lemma 5.16 ). Fix the random seed of a nonadaptive q q q -query algorithm A A A , let G G G be its query graph of at most q q q edges, and write d v d_v d v and t v ≤ d v 2 / 2 t_v\le d_v^2/2 t v ≤ d v 2 /2 for the degree and triangle count at vertex v v v . By the classical spectral bound [4 ] (used also in [9 Section 4] ), the total number of triangles t ( G ) t(G) t ( G ) in G G G satisfies 6 t ( G ) = tr ( A G 3 ) ≤ ( ∑ i λ i ( A G ) 2 ) 3 / 2 ≤ ( 2 q ) 3 / 2 6t(G)=\operatorname{tr}(A_G^3)\le\left(\sum_i\lambda_i(A_G)^2\right)^{3/2}\le(2q)^{3/2} 6 t ( G ) = tr ( A G 3 ) ≤ ( ∑ i λ i ( A G ) 2 ) 3/2 ≤ ( 2 q ) 3/2 , while ∑ v d v ≤ 2 q \sum_v d_v\le2q ∑ v d v ≤ 2 q .
Case 1: n − 1 / 2 ≤ ϵ ≤ ϵ 0 n^{-1/2}\le\epsilon\le\epsilon_0 n − 1/2 ≤ ϵ ≤ ϵ 0 . With β = 1 / 20 \beta=1/20 β = 1/20 , apply Lemma 4.10 on s = ⌈ n ϵ / β ⌉ ≤ n / 2 + 1 s=\lceil n\sqrt{\epsilon/\beta}\rceil\le n/2+1 s = ⌈ n ϵ / β ⌉ ≤ n /2 + 1 vertices and pad to n n n vertices with distance 3 / 2 3/2 3/2 . Then ϵ n 2 ≤ β s 2 ≤ h ≤ s 2 / 6 ≤ 2 β ϵ n 2 \epsilon n^2\le\beta s^2\le h\le s^2/6\le\frac{2}{\beta}\epsilon n^2 ϵ n 2 ≤ β s 2 ≤ h ≤ s 2 /6 ≤ β 2 ϵ n 2 . Under uniform relabeling, each triangle of G G G hits a selected triangle with probability h / ( n 3 ) h/\binom{n}{3} h / ( 3 n ) , so a union bound gives Pr ( F A ) ≤ t ( G ) h / ( n 3 ) = O ( ϵ q 3 / 2 / n ) = O ( ( q / F ( n , ϵ ) ) 3 / 2 ) \Pr(F_A)\le t(G)h/\binom{n}{3}=O(\epsilon q^{3/2}/n)=O((q/F(n,\epsilon))^{3/2}) Pr ( F A ) ≤ t ( G ) h / ( 3 n ) = O ( ϵ q 3/2 / n ) = O (( q / F ( n , ϵ ) ) 3/2 ) .
Case 2: 1 / ( 4 n ) ≤ ϵ ≤ n − 1 / 2 1/(4n)\le\epsilon\le n^{-1/2} 1/ ( 4 n ) ≤ ϵ ≤ n − 1/2 . Apply Lemma 6.7 with m = ⌊ n / 4 ⌋ m=\lfloor n/4\rfloor m = ⌊ n /4 ⌋ and a = ⌈ 5 ϵ n ⌉ ≤ 9 ϵ n a=\lceil5\epsilon n\rceil\le9\epsilon n a = ⌈ 5 ϵ n ⌉ ≤ 9 ϵ n , so h = a m ≥ ϵ n 2 h=am\ge\epsilon n^2 h = am ≥ ϵ n 2 . Conditional on a designated center mapping to v v v , its m m m selected leaf pairs form a uniform matching on [ n ] ∖ { v } [n] \setminus\{v\} [ n ] ∖ { v } , so the probability that G G G contains a selected triangle through v v v is at most min { 1 , m t v / ( n − 1 2 ) } ≤ min { 1 , d v 2 / n } ≤ d v / n \min\{1,mt_v/\binom{n-1}{2}\} \le\min\{1,d_v^2/n\} \le d_v/\sqrt{n} min { 1 , m t v / ( 2 n − 1 ) } ≤ min { 1 , d v 2 / n } ≤ d v / n . Summing over v v v and the a a a centers gives Pr ( F A ) ≤ a n ∑ v d v n ≤ 18 ϵ q / n ≤ 18 q / F ( n , ϵ ) \Pr(F_A) \le\frac{a}{n}\sum_v \frac{d_v}{n} \le18\epsilon q/\sqrt{n} \le18q/F(n,\epsilon) Pr ( F A ) ≤ n a ∑ v n d v ≤ 18 ϵ q / n ≤ 18 q / F ( n , ϵ ) across both n − 1 ≤ ϵ ≤ n − 1 / 2 n^{-1} \le\epsilon\le n^{-1/2} n − 1 ≤ ϵ ≤ n − 1/2 and 1 / ( 4 n ) ≤ ϵ ≤ n − 1 1/(4n) \le\epsilon\le n^{-1} 1/ ( 4 n ) ≤ ϵ ≤ n − 1 .
Case 3: 0 < ϵ < 1 / ( 4 n ) 0 < \epsilon< 1/(4n) 0 < ϵ < 1/ ( 4 n ) . Apply the single-center case of Lemma 6.7 with h = ⌈ ϵ n 2 ⌉ ≤ 2 max { 1 , ϵ n 2 } h=\lceil\epsilon n^2\rceil\le2\max\{1,\epsilon n^2\} h = ⌈ ϵ n 2 ⌉ ≤ 2 max { 1 , ϵ n 2 } . Conditioning on the center mapping to v v v and bounding the matching intersection probability by min { 1 , h t v / ( n − 1 2 ) } ≤ min { 1 , 4 h d v 2 / n 2 } ≤ 2 h d v / n \min\{1,ht_v/\binom{n-1}{2}\} \le\min\{1,4hd_v^2/n^2\} \le2\sqrt{h}d_v/n min { 1 , h t v / ( 2 n − 1 ) } ≤ min { 1 , 4 h d v 2 / n 2 } ≤ 2 h d v / n gives Pr ( F A ) ≤ 1 n ∑ v 2 h d v n ≤ 4 q h / n 2 = O ( q / F ( n , ϵ ) ) \Pr(F_A) \le\frac{1}{n}\sum_v \frac{2\sqrt{h}d_v}{n} \le4q\sqrt{h}/n^2 = O(q/F(n,\epsilon)) Pr ( F A ) ≤ n 1 ∑ v n 2 h d v ≤ 4 q h / n 2 = O ( q / F ( n , ϵ )) .
In all three regimes, Lemma 6.5 yields TV ( Π A ( μ − ) , Π A ( μ + ) ) ≤ Pr ( F A ) + 2 h / ( 2 n 10 + 1 ) < 1 / 3 \operatorname{TV}(\Pi_A(\mu_-),\Pi_A(\mu_+)) \le\Pr(F_A)+2h/(2n^{10}+1) < 1/3 TV ( Π A ( μ − ) , Π A ( μ + )) ≤ Pr ( F A ) + 2 h / ( 2 n 10 + 1 ) < 1/3 whenever q ≤ c F ( n , ϵ ) q \le cF(n,\epsilon) q ≤ c F ( n , ϵ ) for a sufficiently small absolute constant c > 0 c>0 c > 0 and large n n n , ruling out two-sided testers.
Contextual blow-up and adaptive metric testing lower bounds
Unlike nonadaptive algorithms, an adaptive algorithm can use exact numerical distance answers to infer vertex coordinates and guide subsequent queries. To prevent global coordinate recovery, we blow up each vertex of a coarse robust face into t t t clones and assign independent random coordinate bijections to each coarse tight-triangle context.
Lemma 6.9. Let ( A 0 , H 0 ) (A_0,\mathcal{H}_0) ( A 0 , H 0 ) be a robust face from Lemma 4.10 on s s s vertices with slack and endpoint-margin bound s − K s^{-K} s − K (K ≥ 3 K\ge3 K ≥ 3 ), and fix an integer L > K L>K L > K . Replace each coarse vertex by t ≥ 2 t\ge2 t ≥ 2 clones and pad with distance 3 / 2 3/2 3/2 to n ≥ s t n\ge st n ≥ s t vertices. For sufficiently large n n n , there is a random metric A ∈ [ 1 , C 0 ] ( n 2 ) A\in[1,C_0]^{\binom{n}{2}} A ∈ [ 1 , C 0 ] ( 2 n ) with an edge-disjoint family H \mathcal{H} H of ∣ H ∣ = ∣ H 0 ∣ ⌈ t 2 / 2 ⌉ |\mathcal{H}|=|\mathcal{H}_0|\lceil t^2/2\rceil ∣ H ∣ = ∣ H 0 ∣ ⌈ t 2 /2 ⌉ tight triangles (so ∣ H ∣ ≥ β n 2 / 4 |\mathcal{H}|\ge\beta n^2/4 ∣ H ∣ ≥ β n 2 /4 when s t = n − o ( n ) st=n-o(n) s t = n − o ( n ) ) such that all other triangle slacks and endpoint margins of selected edges are at least n − ( L + 3 ) n^{-(L+3)} n − ( L + 3 ) and all entries are O C ( log n ) O_C(\log n) O C ( log n ) -bit rationals.
Proof. For each incidence of a coarse vertex with a coarse triangle in H 0 \mathcal{H}_0 H 0 , independently choose a uniform bijection from its t t t clones to [ t ] [t] [ t ] . Set τ = 1 / ( 100 s L ) \tau=1/(100s^L) τ = 1/ ( 100 s L ) and α = τ / t 2 \alpha=\tau/t^2 α = τ / t 2 . For each coarse triangle ( x , y , z ) ∈ H 0 (x,y,z)\in\mathcal{H}_0 ( x , y , z ) ∈ H 0 with long edge x z xz x z and local clone coordinates u , v , w ∈ [ t ] u,v,w\in[t] u , v , w ∈ [ t ] , set A X Y ( u , v ) = A 0 ( x , y ) + α ( u − v ) 2 A_{XY}(u,v)=A_0(x,y)+\alpha(u-v)^2 A X Y ( u , v ) = A 0 ( x , y ) + α ( u − v ) 2 , A Y Z ( v , w ) = A 0 ( y , z ) + α ( v − w ) 2 A_{YZ}(v,w)=A_0(y,z)+\alpha(v-w)^2 A Y Z ( v , w ) = A 0 ( y , z ) + α ( v − w ) 2 , and A X Z ( u , w ) = A 0 ( x , z ) + α ( u − w ) 2 A_{XZ}(u,w)=A_0(x,z)+\alpha(u-w)^2 A X Z ( u , w ) = A 0 ( x , z ) + α ( u − w ) 2 ; keep all other cross-cell distances equal to A 0 A_0 A 0 and set within-cell and padding distances to 3 / 2 3/2 3/2 . Edge-disjointness of H 0 \mathcal{H}_0 H 0 ensures that each coarse pair belongs to at most one context.
On ( x , y , z ) ∈ H 0 (x,y,z)\in\mathcal{H}_0 ( x , y , z ) ∈ H 0 , the slack of ( u , v , w ) (u,v,w) ( u , v , w ) is α 2 ( u + w − 2 v ) 2 \frac{\alpha}{2}(u+w-2v)^2 2 α ( u + w − 2 v ) 2 , which vanishes precisely on the ⌈ t 2 / 2 ⌉ \lceil t^2/2\rceil ⌈ t 2 /2 ⌉ midpoint triples u + w = 2 v u+w=2v u + w = 2 v and is at least α / 2 ≥ 1 / ( 200 s L t 2 ) ≥ n − ( L + 3 ) \alpha/2\ge1/(200s^Lt^2)\ge n^{-(L+3)} α /2 ≥ 1/ ( 200 s L t 2 ) ≥ n − ( L + 3 ) otherwise. Because any two coordinates of a midpoint triple determine the third and distinct contexts are disjoint on coarse edges, the resulting fine tight triangles H \mathcal{H} H are edge-disjoint. Every perturbation is in [ 0 , τ ] [0,\tau] [ 0 , τ ] with τ ≤ s − K / 100 \tau\le s^{-K}/100 τ ≤ s − K /100 , preserving all unselected slacks and endpoint margins.
Lemma 6.10. Apply the signed noise perturbation of Lemma 6.3 independently to the fine triangles of Lemma 6.9 and uniformly relabel [ n ] [n] [ n ] . For any adaptive q q q -query algorithm A A A with 2 q ≤ n 2q\le n 2 q ≤ n and any integer 1 ≤ R < t 1\le R<t 1 ≤ R < t , the event F A F_A F A that A A A queries all three edges of some fine triangle in H \mathcal{H} H satisfies Pr ( F A ) ≤ 2 q R 2 t − R + s ( 2 e q t n R ) R \Pr(F_A)\le\frac{2qR^2}{t-R}+s\left(\frac{2eqt}{nR}\right)^R Pr ( F A ) ≤ t − R 2 q R 2 + s ( n R 2 e q t ) R under either sign.
Proof. Generate the signed noise table in abstract coordinate space [ t ] 3 [t]^3 [ t ] 3 for each coarse context before sampling the bijections from clones to coordinates, and strengthen the oracle so that querying any edge in a coarse selected context also reveals the coarse cells of both endpoints and their local context coordinates (disclosing at most two new local coordinates per query). First, conditioning on a fixed full template, the strengthened oracle answers are functions of the template vertex images, so Lemma 3.1 embeds the 2 q 2q 2 q touched vertices into a uniformly random 2 q 2q 2 q -set. By a union bound over the s s s coarse cells, the probability that some cell has at least R R R touched clones is at most s ( 2 q R ) ( t ) R ( n ) R ≤ s ( 2 e q t n R ) R s\binom{2q}{R}\frac{(t)_R}{(n)_R}\le s\left(\frac{2eqt}{nR}\right)^R s ( R 2 q ) ( n ) R ( t ) R ≤ s ( n R 2 e q t ) R .
Second, condition on the random seed, the abstract noise table, and the coarse cell partition of [ n ] [n] [ n ] . Because numerical edge weights in a context are deterministic functions of the disclosed local coordinates and the fixed abstract noise table, the conditional law of the remaining undisclosed coordinates in each incidence between a cell and a context remains uniform over the unused values in [ t ] [t] [ t ] . Stop the process if any cell reaches R R R touched clones. Prior to stopping, each newly disclosed coordinate is uniform over at least t − R t-R t − R unused values, while the other two cells of its coarse context have at most R R R disclosed coordinates each and hence prescribe at most R 2 R^2 R 2 midpoint-completing values. A union bound over the at most 2 q 2q 2 q coordinate disclosures therefore bounds the probability of completing a midpoint triple before stopping by 2 q R 2 / ( t − R ) 2qR^2/(t-R) 2 q R 2 / ( t − R ) . □
Theorem 6.11 (Adaptive lower bound on a bounded range). For every fixed C > 2 C>2 C > 2 , there exist constants c C > 0 c_C>0 c C > 0 and n 1 ( C ) n_1(C) n 1 ( C ) such that for all n ≥ n 1 ( C ) n\ge n_1(C) n ≥ n 1 ( C ) and 0 < ϵ ≤ 1 / 80 0<\epsilon\le1/80 0 < ϵ ≤ 1/80 , any adaptive two-sided ϵ \epsilon ϵ -tester for general metrics on [ 1 , C ] [1,C] [ 1 , C ] requires at least c C n / log n c_C\sqrt{n/\log n} c C n / log n queries. The same lower bound holds for one-sided testers and unrestricted positive metric repairs, on inputs with O ( C ( log n ) ) O(C(\log n)) O ( C ( log n )) -bit rational entries.
Proof. Set ℓ = ⌈ log n ⌉ \ell=\lceil\log n\rceil ℓ = ⌈ log n ⌉ , s = ⌊ n / ℓ 3 ⌋ s=\lfloor\sqrt{n/\ell^3}\rfloor s = ⌊ n / ℓ 3 ⌋ , t = ⌊ n / s ⌋ t=\lfloor n/s\rfloor t = ⌊ n / s ⌋ , and R = 20 ℓ R=20\ell R = 20 ℓ , and apply Lemma 6.9 with K = 3 K=3 K = 3 and L = 4 L=4 L = 4 followed by Lemma 6.3 with J = 10 J=10 J = 10 . For large n n n , we have s t = n − o ( n ) st=n-o(n) s t = n − o ( n ) and h = ∣ H ∣ ≥ β n 2 / 4 h=|\mathcal{H}|\ge\beta n^2/4 h = ∣ H ∣ ≥ β n 2 /4 , so every instance in supp μ + \operatorname{supp}\mu_+ supp μ + is at distance 2 h / n 2 ≥ β / 2 = 1 / 40 > ϵ 2h/n^2\ge\beta/2=1/40>\epsilon 2 h / n 2 ≥ β /2 = 1/40 > ϵ from M n \mathcal{M}_n M n . Moreover, t − R ≥ 1 4 n / ℓ 3 t-R\ge\frac{1}{4}\sqrt{n/\ell^3} t − R ≥ 4 1 n / ℓ 3 and 2 e q t / ( n R ) ≤ e / 5 2eqt/(nR)\le e/5 2 e q t / ( n R ) ≤ e /5 whenever q ≤ n / ℓ q\le\sqrt{n/\ell} q ≤ n / ℓ , so Lemmas 6.10 and 6.5 yield TV ( Π A ( μ − ) , Π A ( μ + ) ) ≤ 6400 q ℓ / n + O ( n − 8 ) < 1 / 3 \operatorname{TV}(\Pi_A(\mu_-),\Pi_A(\mu_+))\le6400q\sqrt{\ell/n}+O(n^{-8})<1/3 TV ( Π A ( μ − ) , Π A ( μ + )) ≤ 6400 q ℓ / n + O ( n − 8 ) < 1/3 for q ≤ c C n / log n q\le c_C\sqrt{n/\log n} q ≤ c C n / log n with c C > 0 c_C>0 c C > 0 sufficiently small. □
Finally, combining Theorems 6.8 and 6.11 for any fixed C > 2 C>2 C > 2 with Lemma 5.16 transfers both our nonadaptive two-sided lower bound across all proximity regimes and our adaptive two-sided lower bound directly to unrestricted metrics and pseudometrics.
Theorem 6.12 (Lower bounds for metric testing). On arbitrary nonnegative symmetric inputs, for all sufficiently large n n n and 0 < ϵ ≤ 1 / 80 0<\epsilon\le1/80 0 < ϵ ≤ 1/80 , nonadaptive two-sided and adaptive two-sided ϵ \epsilon ϵ -testing of general metrics require, respectively,
Ω ( F ( n , ϵ ) ) and Ω ( n log n ) \Omega(F(n,\epsilon)) \qquad\text{and}\qquad\Omega\left(\sqrt{\frac{n}{\log n}}\right) Ω ( F ( n , ϵ )) and Ω ( log n n ) queries. Both lower bounds hold for either positive metric or nonnegative pseudometric repair targets, using hard inputs with O ( log n ) O(\log n) O ( log n ) -bit rational entries.
Proof. Fix C = 3 C=3 C = 3 in Theorems 6.8 and 6.11 . All instances in supp μ − \operatorname{supp}\mu_- supp μ − are positive metrics in [ 1 , 3 ] [1,3] [ 1 , 3 ] , and Lemma 5.16 ensures that every instance in supp μ + \operatorname{supp}\mu_+ supp μ + has the same Hamming distance to M n \mathcal{M}_n M n and M ‾ n \overline{\mathcal{M}}_n M n as to M n [ 1 , 3 ] \mathcal{M}_n[1,3] M n [ 1 , 3 ] . □