A uniformly discrete counterexample to bounded approximation in Lipschitz-free spaces

1 Introduction

Uniform discreteness keeps distinct points of a metric space a fixed positive distance apart. For its Lipschitz-free space, this separation guarantees the approximation property: the identity can be approximated on each compact set by finite-rank operators. Kalton asked whether the approximating operators can always be chosen with one bound on their norms [12, Proposition 4.4 and following remarks, p. 185]. The question was restated by Godefroy and Ozawa [11, Question 1] and in Godefroy’s survey [9, Problem 6.2]. We construct a countable uniformly discrete space for which no such bound exists.

We work over the real scalars. For a pointed metric space (M,d,o), let \Lip_0(M) be the Banach space of real Lipschitz functions vanishing at o, with the Lipschitz constant as norm. Its Lipschitz-free space is

Thus \delta_o=0 and \norm{\delta_x-\delta_y}=d(x,y). The latter identity follows from the Lipschitz inequality and the test function z\mapsto d(z,y)-d(o,y). The construction originates in the molecular spaces of Arens and Eells [2, §2]; its linearization properties and complemented free subspaces are central to the work of Godefroy and Kalton [10, §2].

A Banach space X has the approximation property (AP) if for every norm-compact set C\subseteq X and every \varepsilon>0 there is a bounded finite-rank linear operator T:X\to X with \sup_{u\in C}\norm{Tu-u}<\varepsilon. For \lambda\ge1, it has \lambda-BAP if these operators can always be chosen with \norm{T}\le\lambda. The bounded approximation property (BAP) means \lambda-BAP for some finite \lambda, and the metric approximation property (MAP) means 1-BAP. In AP the norm may depend on C and \varepsilon; in BAP one bound must work for all of them. A metric space is proper if its closed bounded balls are compact.

The distinction between discrete and uniformly discrete matters here. Smith gives countable complete discrete spaces whose free spaces have AP and fail BAP, without asserting a common positive lower bound on all nonzero distances [16, Theorem 1.3 and the surrounding discussion]. Theorem 1.1 supplies that lower bound. The example is necessarily outside the countable proper case: Dalet proved MAP for free spaces over countable proper metric spaces [7, Theorem 2.6]. Our example contains an infinite separated subset in a bounded ball. Uniform discreteness also imposes strong sequential structure: Cúth and Kalenda prove a quantitative strengthening of the Schur property for these free spaces [6, Theorem 1.1], so weakly convergent sequences converge in norm. Their April 2026 introduction still records the BAP question addressed here.

The same example has a nonlinear consequence. Kalton asked whether every separable Banach space is approximable [13, Problem 1, p. 1260]. For such a space X, this means that there is an equi-uniformly continuous sequence of maps \psi_n:X\to X, each with relatively compact range, such that \psi_n(x)\to x for every x\in X. Equi-uniform continuity means that the choice of \delta for a given \varepsilon in the uniform-continuity condition works for every \psi_n. The space X=\F(M) in Theorem 1.1 is not approximable, although it has AP. Section 2.4 explains the short implication from Kalton’s net theorem that gives this consequence.

1.1 A finite obstruction in each bounded block

The main construction concerns a prescribed operator norm bound p. It produces a bounded metric space and a finite set of points, called anchors, at which every finite-rank operator of norm at most p makes a definite error. The distinction from earlier finite extension obstructions is important. For a finite pointed metric pair A\subseteq N containing the basepoint, a linear extension operator E:\Lip_0(A)\to\Lip_0(N) must satisfy (Ef)|_A=f for every f. Brudnyi and Brudnyi give finite subsets of integer \ell_1 cubes for which the least possible norm of an exact linear extension operator grows without bound [5, preprint Lemma 10.5, pp. 46–47]. Godefroy and Ozawa [11, Proposition 7] obtain arbitrarily large lower bounds for finite metric pairs from a compact free space failing AP. By finite-dimensional duality, an extension operator corresponds, with the same norm, to a projection from \F(N) onto the span of the evaluations from A. These bounds therefore concern projections with a prescribed range. On the finite-dimensional space \F(N), the identity remains a finite-rank operator of norm at most one. Our block is infinite, and its fixed finite anchor set obstructs approximation by every operator of norm at most p whose range is finite-dimensional.

Each individual block nevertheless has BAP. The coefficient identification for bounded uniformly discrete spaces appears in [1, Theorem 4.14], with the bounds used here in [6, Lemma 3.4]. Our proof in Proposition 2.1 identifies \F(M_p) with \ell_1(M_p\setminus\{o\}), and coordinate truncations give 2B_p-BAP alongside the obstruction at p. Transporting the free-space norm to real \ell_1 gives the following quantitative consequence. It also answers a separate question: does every equivalent norm on real \ell_1 have MAP? Kalton observed that a positive answer would imply BAP for every uniformly discrete free space [13, p. 1260]. The case p=1 below gives a direct negative answer.

To pass from the blocks to Theorem 1.1, identify their basepoints and put

Each block then has a pointed 1-Lipschitz retraction from the resulting metric wedge. On free spaces, inclusion and retraction induce contractions whose composite is the identity. Thus a BAP bound for the wedge would be a bound for every block, contradicting Theorem 1.2.

The same decomposition proves AP directly. First retain finitely many blocks by a contractive projection that approximates the chosen compact set. Then approximate its images in those blocks, using their individual BAPs. Only finitely many operator norms occur at this stage, so the resulting operator is bounded. The bound is allowed to grow as more blocks are retained.

1.2 The obstruction: signed measures and opposing tests

The block itself consists of two kinds of points: vertices of finite source graphs and anchors that join those graphs into a bounded metric space. After a finite-rank operator is given, we choose a finite subset S of these same points to support the range of a nearby operator. Thus S may contain source vertices or anchors and may depend on the operator.

The source graphs have a fixed large degree. For every fixed radius, the frequencies of their colored neighborhoods approach the corresponding probabilities in a regular tree of that degree with independent uniform vertex colors. A vertex is labeled by its capped distances to the color classes. These labels vary by at most one across an edge, and each label has only a bounded number of coordinates below the cap. Vertices with the same label attach to the same anchor by a long edge. There are only finitely many possible labels, hence finitely many anchors. Joining the anchors makes the whole block bounded, while sufficiently small metric balls remain inside a single source graph and contain a uniformly bounded number of points.

Suppose a finite-rank operator of small norm approximates the anchor evaluations. An arbitrarily small perturbation gives an operator T with \norm{T}\le2p whose range has a common finite support S\subset M_p. Adding a coefficient at the basepoint allows us to write its values as signed measures \mu_x on S, each of mass one and uniformly bounded total variation. For the height L=10p, a nonnegative bump b_x:M_p\to[0,L] detects support points whose labels are close to the label of x. It takes its maximum L at the anchor a(x) attached to x and has a small Lipschitz constant, in particular at most one. The operator norm controls the comparison from x to a(x), while the anchor approximation controls the value there. The small slope of b_x makes their combined loss from the anchor value at most L/4. The affine representation therefore gives

No positivity of \mu_x is assumed.

A source walk is nonbacktracking if it never immediately reverses an edge incidence. The color structure makes it rare for a source vertex to start a long nonbacktracking walk that can be tracked by nearby support points with compatible labels. Such a walk is matched if one can choose a support point at each step with a compatible label, while consecutive support points stay within distance 2L. For a prescribed support point, compatibility allows only a small set of source colors. A bound on small metric balls limits the possible next support points. On the limiting tree, the source colors along a nonbacktracking walk are independent. Choosing many colors therefore makes long matched walks rare.

Call a vertex good if no matched walk of the chosen long length starts there, and bad otherwise. At a good vertex, record the longest matched walk beginning in each outgoing direction, for each fixed initial support point. Declare a direction exceptional only when its record is strictly larger than every other record. There is at most one such direction per support point. If nearby support points match the two ends of an edge whose endpoints are good, at least one of the two directions along that edge must be exceptional: otherwise prepending the edge to a longest walk in another direction would force each of two finite records to be larger than the other.

For an oriented incidence e:x\to y, let E_e be the support points for which e is exceptional at x; at a bad vertex we put every support point in E_e. We prescribe b_x on S\setminus E_e and -b_y on S\setminus E_{\bar e}, where \bar e is the reverse incidence. Within each set the prescribed values satisfy the Lipschitz inequality because the bumps do. For a cross pair j\in S\setminus E_e and j'\in S\setminus E_{\bar e}, the record argument shows that if d_p(j,j')<2L, then both b_x(j) and b_y(j') vanish. If the distance is at least 2L, their sum is bounded by that distance. Thus all the prescribed values together are 1-Lipschitz. Scalar extension followed by clipping gives a 1-Lipschitz test f_e:M_p\to[-L,L]. Its pairing satisfies

Here |\mu_x|(E_e) is the sum of the absolute values of the coefficients of \mu_x on E_e. Each support point belongs to at most one exceptional set at a good vertex. Averaging over all oriented incidences therefore divides the corresponding variation loss by the graph degree; the small fraction of bad vertices controls the remaining loss. Since source-edge endpoints have d_p-distance at most one, the affine pairing bounds each test pairing in absolute value by \norm{T}\le2p. The averaged lower bound contradicts this upper bound.

The order of choices is essential. The entire deterministic graph sequence, metric block, and anchors are fixed before the operator and its support S. We then choose the walk length and one sufficiently large source graph. Local convergence applies to every finite colored event, including the event specified by this already fixed support. There is no assumption that the operator was chosen independently of the graph sequence.

1.3 Methods and organization

For the graph construction we use the independent-permutation model described by Friedman [8] and prove the local convergence we need directly. The empirical rooted-neighborhood viewpoint is that of Benjamini and Schramm [4]. The scalar extension step is an instance of McShane’s classical extension principle [14]; we give the needed formula for finite data and its proof. A related comparison of nonbacktracking continuation lengths is used to select parent directions in the graph algorithm of Ben-David, Childs, Gilyén, Kretschmer, Podder, and Wang [3, §6.1.2]. Our continuation records also depend on the support state and are used to construct the scalar tests.

Section 2 proves the coefficient estimate, the renorming corollary, and the wedge reduction, assuming Theorem 1.2, and derives the nonlinear consequence from Kalton’s theorem. Section 3 constructs the colored graphs and bounded block. Sections 4, 5 and 6 prove Theorem 1.2: they pass from an arbitrary finite-rank operator to signed measures, bound matched walks, and derive the contradiction by scalar tests and incidence averaging.

2 From bounded blocks to AP without BAP

The following sections will construct the blocks of Theorem 1.2. Here we assume that theorem, prove the renorming and wedge results, and derive the nonlinear consequence from Kalton’s theorem. A bounded space with separation at least one has a coefficient description by \ell_1, with an approximation bound controlled by its diameter. Joining the blocks preserves each of their obstructions, while retractions onto finitely many blocks provide the approximations required for AP.

2.1 The coefficient estimate

The coefficient identification below appears in [1, Theorem 4.14]; the coefficient bounds are stated in [6, Lemma 3.4]. We include the proof and derive the stated approximation bound from coordinate truncations.

2.2 The metric wedge and its retractions

Take disjoint copies of the spaces M_p and identify only their basepoints. Thus, as a set,

Keep the distance d_p within each block, and for nonbasepoint points in distinct blocks set

These rules define a metric. Symmetry and positivity are immediate. For the triangle inequality, if the endpoints lie in one block, a detour through a point z in another block has length d_p(x,o)+2d_q(z,o)+d_p(y,o)\ge d_p(x,y). If the endpoints lie in different blocks and the third point lies in one of those blocks, that block’s triangle inequality gives the required bound. A third point in a third block adds twice its distance to o, and a third point equal to o gives equality. The remaining case is the triangle inequality within a single block.

The space M is countable. Within a block, distinct points remain at distance at least one; in distinct blocks, nonbasepoint points are at distance at least two. It is also unbounded. To see this using only Theorem 1.2, suppose that M had finite diameter C_0. Then C_0\ge1, and every M_p would have diameter at most C_0. Proposition 2.1 would give 2C_0-BAP on every \F(M_p). Choose an integer p\ge\max\{1,2C_0\}. Applying that property to \{\delta_a:a\in A_p\} with accuracy 1/2 would produce a finite-rank operator of norm at most 2C_0\le p whose error is less than 1/2 at every anchor, contrary to Theorem 1.2.

Finally, the closed ball about o of radius B_1 contains the countably infinite 1-separated set M_1. If this ball were compact, its cover by open balls of radius 1/3 would admit a finite subcover. Each such ball contains at most one point of M_1, which is impossible. Thus M is nonproper.

For each p, let i_p:M_p\to M be inclusion and let r_p:M\to M_p fix M_p and send all other blocks to o. Both are pointed 1-Lipschitz maps. Inclusion preserves distances. For the retraction, the only case that needs an inequality has x\in M_p and y\in M_q\setminus\{o\} for q\ne p; then

If both points are outside M_p, their images coincide, and if both are in M_p, their distance is preserved.

We use the elementary linearization property of free spaces; its role in Banach-space geometry is developed in [10, §2]. If u:N\to N' is pointed and 1-Lipschitz, define on finite evaluation combinations

Pullback of pointed scalar tests gives

This inequality makes the definition independent of the representation of the evaluation combination, and it gives a unique continuous linear extension \widehat u:\F(N)\to\F(N') of norm at most one. Applying it to i_p and r_p gives contractions

Their composite P_pI_p fixes every evaluation, so it is the identity on \F(M_p). In particular, for every v\in\F(M_p),

thus I_p is an isometry.

2.3 The approximation properties of the wedge

Suppose that \F(M) had \lambda-BAP for some finite \lambda\ge1. Choose an integer p\ge\lambda and apply that property with accuracy 1/2 to the finite, hence compact, set \{I_p\delta_a:a\in A_p\}. Let U be the resulting operator. The compression P_pUI_p has finite rank and norm at most \lambda\le p, while for every a\in A_p,

This contradicts Theorem 1.2. All blocks and their anchor sets were fixed before \lambda and U were chosen.

It remains to prove AP. Kalton’s general theorem [12, Proposition 4.4] gives AP for free spaces over uniformly discrete metric spaces; the wedge structure provides a direct proof here. For N\ge1, define r_{\le N}:M\to M to retain the first N blocks and send every other block to o. It is pointed and 1-Lipschitz: distances in the retained part are unchanged, distances in the collapsed part become zero, and (2.2) bounds the image distance for a retained point and a collapsed point. Its linearization is a contractive projection

The equality follows on each evaluation \delta_x: the sum retains it when x is in one of the first N blocks and sends it to zero otherwise. The same check gives R_N^2=R_N. Continuity gives both identities on \F(M).

Every finite linear combination of evaluations is fixed by R_N for all sufficiently large N. These combinations are dense, and \norm{\Id-R_N}\le2. Thus R_Nu\to u for every u\in\F(M): given a finite evaluation combination v fixed by R_N, one has \norm{R_Nu-u}\le2\norm{u-v}. The finite-net argument in the proof of Proposition 2.1, applied now with \norm{\Id-R_N}\le2, makes this convergence uniform on every norm-compact set.

Now fix a nonempty norm-compact C\subseteq\F(M) and \varepsilon>0. First choose N\ge1 such that

For each 1\le p\le N, the image P_p(C) is compact. By Proposition 2.1, choose a finite-rank operator T_p:\F(M_p)\to\F(M_p) with \norm{T_p}\le2B_p and

The operator

has finite rank and is bounded, with \norm{T}\le\sum_{p=1}^N2B_p<\infty. By (2.3), for every u\in C,

We first chose N so that the contractive projection R_N approximated the whole compact set, and then chose the finitely many block operators. Their combined norm may depend on C and \varepsilon, as AP permits. This proves AP, and the metric properties and the preceding obstruction prove Theorem 1.1 under Theorem 1.2.

2.4 Failure of nonlinear approximability

We verify the nonlinear consequence stated in the introduction using Kalton’s characterization by nets [13, Theorem 4.4 and p. 1260]. Let X=\F(M) for the wedge just constructed. It is separable because M is countable, and \{\delta_x:x\in M\} is 1-separated in X. Extend this set to a maximal 1-separated set N_X\subseteq X. Every point of X is then within distance one of N_X, so N_X is a net: a separated set within a fixed distance of every point of X. If X were approximable, Kalton’s theorem would give one Lipschitz bound \Lambda\ge1 for maps g:N_X\to N_X with relatively compact range that approximate any prescribed finite subset as closely as desired. Separation makes each such range finite and turns approximation within distance less than one into exact fixing. For a finite F\subseteq M containing o, choose g fixing every \delta_x with x\in F. The restriction x\mapsto g(\delta_x) is then a pointed \Lambda-Lipschitz map from M into X. The Banach-valued linearization property of free spaces [12, Lemma 3.2] gives a finite-rank operator T_F:X\to X of norm at most \Lambda satisfying T_F\delta_x=g(\delta_x) for all x\in M. To approximate a compact set, approximate a finite net in it by finite evaluation combinations and put all their supports in F. The operator T_F fixes those combinations, and \norm{T_F-\Id}\le\Lambda+1 controls the remaining errors. Thus these operators give BAP, contrary to the preceding obstruction. Hence X is not approximable.

It remains to construct the blocks of Theorem 1.2.

3 Colored graphs and the bounded block

We now construct the metric space and anchors in Theorem 1.2. The graphs below supply independently colored tree patterns in the empirical limit. We join their disjoint union through finitely many anchors, making the resulting space bounded while keeping the small balls used to count support transitions inside the source graphs. The lower bound for finite-rank operators will use this local limit together with the properties in Lemma 3.2.

We first fix the graph conventions. Multiple edges are distinct edge instances. Each instance has two oriented incidences e,\bar e, exchanged by reversal, even when the edge is a loop. Thus a loop contributes two to the degree. Write e:x\to y when x and y are the initial and terminal vertices, and let \mathcal D(x) be the set of outgoing incidences at x. A walk is nonbacktracking if it never immediately takes the reverse incidence of its preceding step. It may revisit vertices or take the same loop incidence again. Graph distance uses unit edge lengths. A rooted radius-r ball is the induced multigraph on vertices at graph distance at most r from the root; its isomorphism type retains the colors, loops, and edge multiplicities. Throughout the construction, only vertices are points of the metric spaces: edge interiors are not included.

3.1 A deterministic sequence with a colored tree limit

We use the independent-permutation multigraph model described by Friedman [8, §1, p. 2], in the empirical rooted-neighborhood viewpoint of Benjamini and Schramm [4, §1.2]. The precise colored limit and deterministic selection needed here follow from the elementary exploration argument below; no spectral estimate is used.

3.2 Labels, anchors, and the metric

Fix an integer p\ge1. We choose the metric scales to meet two requirements of the obstruction. Scalar tests taking values in [-L,L] automatically satisfy the Lipschitz inequality for opposing values at points separated by at least 2L. We make the source-to-anchor attachment length R larger than 2L, so paths short enough to require further control cannot cross an attachment edge. The later operator comparison across an attachment has norm error at most 2pR+1. Testing that comparison against a label bump with Lipschitz constant at most L/K incurs a loss of at most L(2pR+1)/K, which must be small compared with its height L. Set

Substitution gives B=300p^2+150p+5=B_p. These metric scales satisfy R>2L, (2pR+1)/K\le1/5, and K+2L+1=D-4<D. The label coordinates will be capped at D. The last inequality leaves room for a label distance below K, one source-edge step, and one support step of length at most 2L, while still keeping the relevant coordinate below the cap.

The degree and the number of colors serve different purposes. The signed-measure argument will bound total variation by V=1+4pB; choosing a large degree dilutes the loss from at most one exceptional direction per support point. Choose an even integer \Delta\ge4 with V/\Delta<1/20, and put

The geometry below gives at most Q nearby successors for a support point and at most H label coordinates below the cap, which will bound the possible source colors for that point. A source walk itself has at most \Delta choices at each step. Thus larger degree helps the averaging argument but also increases the number of walks in the matching estimate. After fixing \Delta, choose an integer k>2\Delta QH, so that the combined matching factor \Delta QH/k is less than 1/2. All these choices are possible because the preceding quantities are finite. Fix a deterministic sequence (G_m)_{m\ge1} from Lemma 3.1 for this \Delta and k. All constants and the entire sequence are now fixed, before any operator is considered.

Take disjoint copies of the graphs G_m, whose vertices we call source vertices. For a source vertex x\in G_m, define h(x)\in\{0,\ldots,D\}^k by

The distance is +\infty if no vertex of color i lies in the component of x, so the corresponding coordinate is D. These labels are defined using the unit graph distances, before the metric space below is formed.

Let \mathcal H\subseteq\{0,\ldots,D\}^k be the set of labels realized by all source vertices. For each v\in\mathcal H, add one new vertex a_v, called an anchor, with label h(a_v)=v. Set A_p=\{a_v:v\in\mathcal H\} and a(x)=a_{h(x)}. Join each source vertex x to a(x) by an edge of length R. Join distinct anchors a_v,a_w by an edge of length 2R+\norm{v-w}_\infty. Retain every source graph edge with length one. Let M_p be the set of all source vertices and anchors, and let d_p(u,v) be the infimum of lengths of finite paths joining u to v in this weighted graph, allowing the zero-edge path when u=v. Choose any anchor o as basepoint; an anchor exists because every G_m is nonempty. Figure 1 shows how vertices sharing a label use one anchor.

Part (iii) also gives a direct geometric proof that the wedge in Section 2 is unbounded. Each block contains a source vertex, and the wedge preserves its distance from the common basepoint, which is at least R_p=30p.

The construction has now fixed M_p, its finite anchor set, and the entire graph sequence independently of any operator. The ball bound gives at most Q nearby successors for any point in any eventual finite support. The label bound gives a second restriction: if a source vertex x has color i and \norm{h(x)-h(t)}_\infty<D, then h_i(t)<D because h_i(x)=0. For each fixed t, proximity of labels therefore permits at most H source colors. Both restrictions hold for every possible support, including one containing anchors or vertices from several source graphs.

4 Finite-rank operators and signed measures

Fix an integer p\ge1 and the block (M_p,d_p,o) constructed in Lemma 3.2, with its anchors A_p, label map h, and parameters from (3.1). We now begin the proof of Theorem 1.2. An operator that approximates the anchors will give a signed measure at each graph vertex. The measure will have bounded total variation and a large integral against a bump determined by that vertex’s label. These two estimates are the inputs for the graph argument.

4.1 A common finite support

Finite rank does not imply that the range is supported on finitely many evaluations. The following perturbation supplies such a support while retaining the bounds needed later.

4.2 Measures detected by label bumps

For a source vertex x, define a function on all of M_p by

The label map is 1-Lipschitz by Lemma 3.2. Hence b_x takes values in [0,L], has Lipschitz constant at most L/K\le1, and equals L at the anchor a(x), whose label is h(x). The small Lipschitz constant will let us compare T\delta_x with the nearby anchor evaluation even when \norm{T} is as large as 2p.

For a signed measure \nu on a finite set S, write

The measures may have coefficients of either sign. Their common total mass means that \mu_x-\mu_y annihilates constants, so a scalar test can be centered at o without changing its pairing with this difference. Signed representations also occur in Lipschitz almost extension; [15, Proposition 6 and Remark 7] distinguishes them from the restrictions imposed by probability measures. Here the total-variation bound is what permits arbitrary signs in T.

5 Rare matched walks and continuation records

Fix a finite set S\subseteq M_p containing o. Its points will serve as states, and its labels and metric distances remain fixed throughout the following argument. The set may be the support obtained from an operator in Lemma 4.1; its points may lie in any of the graphs or among the anchors. We will select a graph only after S has been fixed.

Recall the incidence convention from Section 3. Each edge instance has two distinct oriented incidences e,\bar e, exchanged by reversal, including when the edge is a loop. A loop therefore counts twice toward degree. Write e:x\to y and let \mathcal D(x) be the set of \Delta outgoing incidences at x. A walk is nonbacktracking if it never immediately takes the reverse incidence of its preceding step.

In the application to Lemma 4.2, we will compare the measures at the ends of an incidence e:x\to y using a 1-Lipschitz function that agrees with b_x on one subset of S and with -b_y on another. This section supplies the combinatorial rule for choosing those subsets from the fixed graph sequence and the labels and distances on S.

A graph vertex x and a state j\in S are compatible when

A nonbacktracking walk x_0,e_1,x_1,\ldots,e_t,x_t in one graph G_m is matched if there are states j_0,\ldots,j_t\in S such that (x_s,j_s) is compatible for every s and

Both the states and the source vertices may repeat. For example, a return along a different parallel edge is allowed; only the reverse of the preceding incidence is forbidden.

The compatibility threshold allows for a label distance below K where a bump is positive, one source-edge step of length at most one, and one state step of length at most 2L. The inequality K+2L+1<D will also restrict the possible source colors.

5.1 A long match is rare

Each state has at most Q possible successors, by the radius-2L ball bound in Lemma 3.2, while a graph walk encounters many possible colors. We use this disparity to bound the fraction of roots from which a long matched walk starts.

5.2 At most one exceptional direction per state

Fix n\ge2 and one graph G=G_m. Call a vertex bad if a matched walk of length n starts there, and good otherwise. The next argument is deterministic. At a good vertex it uses the absence of long matched walks to select at most one direction for each state.

A related comparison of nonbacktracking continuation lengths appears in Ben-David, Childs, Gilyén, Kretschmer, Podder, and Wang [3, §6.1.2, Algorithm 6.1 and Lemma 6.3]. Their probabilistic graph algorithm uses such lengths to select parent directions, and their consistency lemma excludes an incompatible pair of choices by symmetric length inequalities. Here the records are deterministic and indexed by support states; the incidence formulation also includes loops and parallel edges. The argument below is self-contained.

For a good vertex x, an incidence e\in\mathcal D(x), and a state j\in S, let \mathcal L_x(e,j) be the set of positive integer lengths of matched walks starting through e with initial state j. Define

A matched walk of length at least n has a matched prefix of length n, so \mathcal L_x(e,j)\subseteq\{1,\ldots,n-1\}. Thus the maximum is well-defined. The value zero means only that no positive-length walk exists; it makes no assertion about compatibility of (x,j).

Declare e exceptional at (x,j) if its record is strictly greater than every other outgoing record at (x,j). There is at most one such incidence; if largest records are tied, there is none. At a bad vertex, declare all outgoing incidences exceptional at every state. For an incidence e:x\to y, set

The proof uses incidence identities, so it also applies to loops and parallel edges. It allows repeated states and vertex revisits, and using the edge by itself covers zero records. The conclusion will let us prescribe opposite scalar values at the two endpoints: whenever nearby states could receive opposing nonzero values, at least one of their prescriptions must be discarded.

6 Scalar tests and incidence averaging

Keep the finite state set S, the integer n\ge2, and the graph G=G_m from the continuation construction in Section 5. For an incidence e:x\to y, we will prescribe the bump b_x on states outside E_e and the negative bump -b_y on states outside E_{\bar e}. The bump bounds handle pairs within one set and cross pairs at distance at least 2L. The exceptional-direction lemma handles closer cross pairs, making the combined prescribed values 1-Lipschitz.

6.1 The finite anchor obstruction

Each test compares the signed measures at the ends of its incidence. The comparison loses variation only on exceptional states. At a good vertex each state is exceptional in at most one of the \Delta directions, so averaging these losses will give a bound independent of the cardinality of S.

Theorem 1.2 now supplies the hypothesis used in Section 2. The wedge construction there therefore proves Theorem 1.1, and the coefficient identification proves Corollary 1.3. Section 2.4 then gives failure of nonlinear approximability for the same space \F(M).