A power saving for planar unit distances

Proof. Fix a neighborhood of each original point and choose a rational open rectangle containing that point inside its neighborhood. For variables X_i=(X_{i,1},X_{i,2}), impose membership in these rectangles, the equations

and the strict inequalities

This finite system has rational coefficients and a real solution, namely the original configuration. The transfer principle for real closed fields [17, Theorems 3.1 and 4.1] gives a solution in the field of real algebraic numbers. The equations preserve the required unit pairs, the inequalities preserve distinctness, and the rectangles give the prescribed closeness.□

Proof. Choose an auxiliary horizontal direction before taking the sample. Require that an input point and an intersection point of two original circles have different horizontal coordinates unless they are the same point. Require also that an input point have a horizontal coordinate different from that of a horizontal extremum of an original circle, unless it is that extremum. Only finitely many directions are excluded. For the latter assertion, if c is a circle center and p is a point, an equality with an extremal abscissa has the form e\cdot(p-c)=\pm1 for a unit horizontal direction e, and has at most finitely many solutions in e. This auxiliary direction does not change the coordinates used elsewhere in the proof.

Ignore repetitions among the sampled circles. Express each sampled circle as its upper and lower semicircle graphs on their open horizontal domains. The event points are their horizontal extrema and all their pairwise intersections, including tangencies. Between consecutive event abscissas, the graphs have fixed vertical order; consecutive graphs, with infinite outer boundaries allowed, bound open gaps.

Sweep these gaps from left to right. Continue a gap across an event abscissa precisely when its two boundary graphs and their adjacency continue unchanged and its closed limiting vertical segment contains no event point. Otherwise start a new piece on the right. Each resulting piece is the open region between two fixed semicircle graphs, or infinite boundaries, over an open interval. It contains no part of a sampled circle. In particular, a continued gap has no start, end, tangency or crossing inside it at the abscissa across which it continues. An input point at an event abscissa must, by the choice of direction, itself be an event point and therefore lies on a sampled circle. Thus every point not deleted is in one of the open pieces.

There are O(1+s^2) pieces, including in the presence of multiple intersections or several events with the same abscissa. A new right-hand gap can start only if an event point lies in its closed limiting vertical segment. If c_x distinct sampled circles pass through an event point x, only O(1+c_x) right-hand gaps can have this property, by their vertical ordering. Summing over event points costs O(s+s^2): extrema contribute O(s), and at an intersection with c_x\ge2 one may charge c_x to 2\binom{c_x}{2}, while each pair of circles has at most two intersections. This also covers extrema that coincide with intersections. There is only a constant number of initial unbounded gaps.

Finally, all possible pieces have a description from the full circle set using a bounded number of circles. Each of their two horizontal endpoints is an extremal or intersection abscissa, or infinity; each boundary graph is specified by a circle and a sign, or is infinite. Consequently at most C_0(1+l)^6 candidate regions can occur, with an absolute constant C_0. For any fixed candidate region intersecting more than l/R circles, the probability that no sampled circle intersects it is at most

with the evident interpretation when R=1. An actual open piece avoids every sampled circle. A union bound over the candidate regions, with C sufficiently large, therefore gives the asserted conflict bound with failure probability at most 1/10.□

Proof. Székely’s point–curve incidence theorem [25, Theorem 8] gives the stronger bound I=O(m^{2/3}l^{2/3}+m+l) when distinct curves meet in at most two points and distinct points belong to at most two curves. Distinct unit circles satisfy both hypotheses. If simple curves are taken to be arcs, cut each circle at two points outside the finite input point set; the resulting 2l arcs satisfy the same pair bounds and preserve every incidence. The logarithmically weakened form (2.1) follows, including the empty-set cases.□

Proof. First use Lemma 2.1. Choose a\to0 sufficiently slowly that the initial incidence count is at least t^{4-o(a)} and every fixed power of \log t is t^{o(a)}. In particular a\log t\to\infty. Apply Lemma 2.2 with R=t^{1-a} and s=O(t^{1-a}\log t). There are t^3 points and circles. Incidences on the sampled circles number at most s t^3, and incidences at deleted points with other circles number at most 2s t^3. Thus the deletion costs O(t^{4-a}\log t)=o(t^{4-o(a)}).

Each remaining region meets at most t^{2+a} circles. Further split its assigned point set into sets of size at most 2t^{1+2a}. The total number of resulting pieces is at most the original region count plus O(t^3/t^{1+2a}), hence at most t^{2-2a+o(a)}. Some piece has at least t^{2+2a-o(a)} incidences. Denote its two vertex sets temporarily by P_0,Q_0, and its edge count by e_0. At this stage

where the upper bound follows from (2.1).

Choose b=o(a) so slowly that b\log t\to\infty and b dominates all exponent errors in these estimates and the logarithmic factor in (2.1). Delete point vertices of degree greater than t^{1+b}, and center vertices of degree greater than t^{a+b}, with degrees measured before these deletions. The counts of such vertices are at most

respectively, for all sufficiently large t. Apply (2.1) to the excessive vertices on one side and all vertices on the other. In either case the mixed term is at most t^{2+2a-b/3+o(b)}; the two linear terms are bounded by t^{1+2a+o(b)}+t^{2+a+o(b)}. Their sum is o(e_0). Both deletions therefore retain t^{2+2a+o(a)} edges and give the degree upper bounds t^{1+o(a)}, t^{a+o(a)}. Dividing the retained edge count by these two upper bounds shows that both retained vertex counts attain their stated upper scales within t^{o(a)}. Relabel this trimmed graph as (P_0,Q_0,E_0).

For subsets of these trimmed vertex sets, let u,v be their respective counting fractions and let w be their captured edge fraction. The incidence bound and the maximum-degree bounds give, with one uniform factor T_t=t^{o(a)},

Taking the minimum with the degree bounds separately in the two linear terms, and using \min(x,y)\le\sqrt{xy}, yields

after increasing T_t if necessary. For example, \min(t^{-a}v,u)\le t^{-a/2}\sqrt{uv}; the other linear term uses t^{-1/2}\le t^{-a/2} for large t.

Put \tau=t^{-a/8}. Among all induced rectangles with counting fractions u,v\ge\tau and captured edge fraction w, maximize

We choose \gamma>1/2 so that a bound by (uv)^\gamma improves on \sqrt{uv} for small sets. The inequality \gamma<2/3, where 2/3 is the incidence exponent in (2.6), will ensure that the maximizing rectangle retains the scales (2.2). This is a maximum over a nonempty finite family, and its value is at least one because the full rectangle is feasible. Write U,V for the maximizing counting fractions and W for its captured edge fraction. We claim

Indeed (2.7) gives

By feasibility, UV\ge t^{-a/4}, so the second term on the right is at most 2t^{-49a/100+o(a)}, which tends to zero. If UV\le t^{-ca} along a subsequence for any fixed c>0, the first term tends to zero as well, since 2/3-\gamma=19/150>0. This is impossible. Thus UV\ge t^{-o(a)}, which implies the same for each of U,V, and W\ge(UV)^\gamma gives the claim for W.

Let (P,Q,E) be this maximizing rectangle, retaining precisely its edges from the trimmed graph. The scale estimates (2.2) and the degree upper bounds survive by (2.8). For further subsets with fractions u,v inside P,Q, optimality gives

whenever Uu,Vv\ge\tau. Otherwise uv\le\tau/\min(U,V)=t^{-a/8+o(a)}. Apply (2.7) with the old fractions Uu,Vv and divide by W. Uniformly in all such infeasible subsets, this gives

where one may take \xi_t=t^{-a/48+o(a)}\to0, with the exponent error depending only on the chosen rectangle and the previous uniform bounds. Combining the feasible and infeasible cases proves (2.5). Empty subsets satisfy it trivially.

Finally (2.8) implies that removing any single vertex of the maximizing rectangle remains feasible for all sufficiently large t. Optimality with a point p removed gives

the last inequality following from concavity. The center comparison is identical. This proves (2.4), and multiplying by |E| supplies the lower degree bounds in (2.3).□

Proof. Let u_i,v_i be the counting fractions of the two classes with label i, including zero fractions. Sum (2.5) over the matched rectangles. Cauchy–Schwarz gives \sum_i\sqrt{u_iv_i}\le1, and therefore

For sufficiently small fixed s_0 and sufficiently large t, one label a_0 thus has both counting fractions arbitrarily close to one. Apply (2.5) to either complementary class against the whole opposite side. The marginal exception masses

are then as small as any prescribed fixed constant, uniformly over the label maps. This first conclusion need not be proportional to s.

To obtain proportionality, put J=\Prob_E(\ell_P\ne a_0,\ell_Q\ne a_0). By (2.9) and \sqrt{hk}\le(h+k)/2, we may choose the preceding constants so that J\le(h+k)/4. The events on which exactly one endpoint has label a_0 are mismatches, so

This proves the first assertion, including when s=0, with no additive error. Two independent point labels differ with probability at most 2h, giving (2.10) for small s. For s>s_0, the bound follows by increasing C so that Cs_0\ge1. The center assertion is identical.□

Proof. The first two assertions follow directly from (2.9), using hk\le\delta_t in the first case and hk\le\delta_t^2 and \sqrt{hk}\le(h+k)/2 in the second.

For the third, let g(q)=\Prob(p\in F\mid q), so that \E_\kappa g=h and the probability in question is \E_\kappa g^2. There is nothing to prove when h=0. For any d\in(0,1], put G_d=\{q:g(q)>d\}. Markov’s inequality gives \kappa(G_d)\le h/d. Splitting at this threshold,

Choose d=d_t\to0 sufficiently slowly that \delta_t^{2\eta}d_t^{-1/2-\eta}\to0 and \xi_t d_t^{-1/2}\to0. The bracket then tends to zero, independently of F. This proves the uniform assertion and hence its integrated form.□

Proof. For fixed p,r, summing (2.11) gives

There are at most two summands when p\ne r, proving the off-diagonal estimate by (2.2)–(2.3). Summing instead over the diagonal yields

The asymptotics follow from the same estimates and a\log t\to\infty.

For a finite random variable X, write \mathsf H(X)=-\sum_x\Prob(X=x)\log\Prob(X=x), with 0\log0=0. Every off-diagonal atom is at most M_t=2/(|E|d_{\min,Q}). Dropping the nonnegative diagonal entropy contributions therefore gives

On the other hand, \mathsf H(p)=\mathsf H(r)\le\log|P| =(1+o(1))\log t. Expanding the definition of relative entropy gives

as required.□

Proof. First freeze all K tests. Apply their complete transcript map to both coordinates of the pair (p,r). The actual transcript law is the image of \pi; the reference law is the image of \mu\otimes\mu. Data processing bounds their relative entropy by D. For j\in[K], write H_j for the transcript strictly before step j. Conditional on prefixes (h,h'), the reference next-code law is exactly

Here \mu_h is formed with H_j. Let a_{j,h,h'} denote the actual conditional law of the next two codes. All prefix pairs of positive actual probability have positive reference probability. Iterating (3.3) therefore gives

Consequently, by (3.4) and Cauchy–Schwarz,

For this fixed test sequence and step j, subtract the prediction belonging to each point’s own prefix:

The norm is at most 2B. Under each reference conditional product, both residuals are centered and independent, so the conditional expectation of \ip{U_j(p)}{U_j(r)} is zero. This inner product has absolute value at most 4B^2. Thus (3.5) and (3.9) imply

Each summand is nonnegative, for conditional independence in the wedge law gives the exact identity

It follows, by Cauchy–Schwarz first over q and then over the tests and step, that the average absolute discrepancy is at most

Everything proved so far holds after averaging the initially frozen tests. The residual at step j uses only T_1,\ldots,T_j. Since the tests are independent and identically distributed, its joint law with the strict prefix is unchanged when T_j is replaced by a fresh test after that prefix. This proves (3.7). Finally average over the strict prefixes and choose one attaining at most the average. There are at most M^{j-1}\le M^{K-1} possible histories for a prefix of length j-1.□

Proof. Use f_T(c)=e_c\in\R^M, of norm one, and use the acceptance indicator vector as g_T(q), of norm at most \sqrt M. Actual and predicted failure probabilities differ by the negative of their acceptance probabilities. Averaging (3.7) and then fixing a strict prefix proves the assertion.□

Proof. Augment each test by two fresh independent random maps from its attained coordinate labels into [L], assigning independent uniform values to distinct labels. Numbering attained labels by their first occurrence in a fixed vertex order makes this construction measurable. Use the same map on both vertex sets for each coordinate, and use independent maps for the two coordinates and for different tests. The point code is its two hashed coordinates, so the alphabet has size M=L^2. For a code (a,b)\in[L]^2, use the feature

For the hashed center state (a_q,b_q), use

Their inner product is \mathbf1_{\{a=a_q\}}+\mathbf1_{\{b=b_q\}} -2\mathbf1_{\{(a,b)=(a_q,b_q)\}}, exactly the indicator of the hashed strict-cross relation. Therefore Lemma 3.1 compares its actual and predicted probabilities with error at most 4\sqrt{18}(D/K)^{1/4}, averaged over strict prefixes and the fresh augmented test.

For any two fixed true states, hashing preserves an equality, and creates an equality between two unequal coordinate labels with probability 1/L. Thus a true strict-cross indicator differs from its hashed indicator with probability at most 2/L. This applies both to the actual state pair and to the predicted pair: conditional on the earlier prefix, the fresh true test and the chosen vertices, the current hashes are still independent uniform maps. In particular the predicted point is sampled by (3.6) using no current hash. Comparing actual true, actual hashed, predicted hashed, and predicted true failures gives, in that order, total extra error at most 4/L+4\sqrt{18}(D/K)^{1/4}. Average the current test and current hashes before fixing a prefix, and use 4\sqrt{18}<18. The resulting true-state expression no longer involves the current hashes. Its history has at most (L^2)^{K-1}\le L^{2K} values.□

Proof. Use the classification of number-field places and the product formula [19, Theorems 7.14–7.15]. At a finite place \mathfrak p above a rational prime \ell, normalize the genuine absolute value by |\ell|_{\mathfrak p}=\ell^{-1}, and put n_{\mathfrak p}=[\mathcal N_{\mathfrak p}:\Q_\ell], where \mathcal N_{\mathfrak p} is the completion. Use n_{\mathfrak p} copies of this absolute value, each of weight 1/d_{\mathcal N}. Milne’s local normalization formula [19, Lemma 8.6] converts his finite-place value to |\cdot|_{\mathfrak p}^{n_{\mathfrak p}}. His complex-place value is squared modulus, so we instead use ordinary modulus once for each embedding, counting conjugate embeddings separately. Taking logarithms of the product formula and dividing by d_{\mathcal N} proves (4.2). There are exactly d_{\mathcal N} embeddings, giving archimedean weight one. Finally, the principal fractional ideal of any nonzero u has finitely many prime factors [19, Theorem 3.20]; at every other finite place |u|_v=1.□

Proof. For a finite extension L/\mathcal N, the decomposition into completions [19, Proposition 8.2] gives \sum_{\mathfrak q\mid\mathfrak p}[L_{\mathfrak q}:\mathcal N_{\mathfrak p}] =[L:\mathcal N]. Hence

The extended absolute values restrict to the chosen normalization on \mathcal N, so the finite-place contribution of any u\in\mathcal N is unchanged. Each embedding of \mathcal N has [L:\mathcal N] extensions, giving the same conclusion at infinity. A common finite normal overfield compares any two field choices. The place list includes all normalized extensions with their local-degree multiplicities, so their enumeration involves no further choice. This proves height independence; h(0)=0 is fixed.

The product formula equates the sums of positive and negative logarithms, giving (4.3). Multiplication gives the first height inequality termwise. The triangle inequality contributes at most \log2 at an archimedean entry and no constant at a nonarchimedean entry; the total archimedean weight is one. This proves the second inequality, including zero summands by the stated convention. For the tail estimates, the average positive logarithm over embeddings is at most h(X). For X\ne0, its average negative logarithm is at most h(X^{-1})=h(X). Markov’s inequality proves both assertions.□

Proof. Fix an entry v and s\ge0. At a nonarchimedean entry give two vertices the same label if their U-coordinates differ by at most e^s in absolute value. The strong triangle inequality makes this an equivalence relation. At an archimedean entry, use the cell of a square grid in \C of side e^s, shifted by a uniformly random fractional vector. Only the labels occurring on the finite vertex set matter.

For complex numbers whose distance is a, the probability of different grid cells is at most

Indeed a mismatch in either real coordinate has probability at most its coordinate distance divided by the side length, and the two coordinate distances sum to at most \sqrt2 a. Its integral over s\ge0 is at most C(1+\log^+ a). At a nonarchimedean entry the integral of mismatch is exactly \log^+|U_p-U_q|_v, with value zero for a zero difference. Thus the integrated edge mismatch, averaged over shifts at infinity, is at most C(\E_{(p,q)\sim\omega}h(U_p-U_q)+1).

Apply the assumed label inequality at each fixed level and shift. For a point pair at a nonarchimedean entry, mismatch is exactly the event |U_p-U_{p'}|_v>e^s. At infinity, distance greater than \sqrt2 e^s forces mismatch for every shift. Integration of these tail events bounds the point-pair height, with an additional \log\sqrt2 from the total archimedean weight. This proves the result.□

Proof. Suppose S\le S_0 on a subsequence. All constants in this proof may depend on the fixed S_0. By (4.9), there is an edge value d_0 such that

Temporarily replace the two coordinates by z/d_0 and d_0w. Their edge jumps are D_e=d_e/d_0 and D_e^{-1}, whose mean heights are at most S_0. Lemma 2.5 supplies the label hypothesis of Lemma 4.3. Applying it to both coordinates bounds the sum of the two mean point-pair difference heights. Averaging over the second point then chooses p_0\in P such that the translated coordinates

satisfy a fixed bound on \E_\mu(h(Z_p)+h(W_p)). Since Z_q=Z_p-D_{pq} and W_q=W_p-D_{pq}^{-1} on an edge, Lemma 4.2 also bounds the center means. Thus there is a fixed C_h<\infty with

The edge identity is still (Z_p-Z_q)(W_p-W_q)=1.

We next give the selection argument, keeping the embedding independent of the points it tests. For any fixed finite history map H on P, use the joint law

and independently choose a uniformly random embedding \sigma. Both p and \widehat p have marginal \mu; each q_j has marginal \kappa; and each (p,q_j) has the original edge law. In particular, the three jumps D_j=D_{pq_j} have the correct individual edge marginals. No assertion of mutual independence of these jumps is needed. The height inequality bounds \E h(Z_{\widehat p}-Z_p) and each \E h(D_j-D_l) using only (4.10). These bounds are uniform in H.

Choose a fixed B\ge2 so large that, by (4.5), the probability that any of

has embedded absolute value greater than B is less than 1/100. Then choose a fixed 0<r<1 so small that (4.6) makes the probability of any of

less than 1/100 in total. The equalities have deliberately been excluded from these small-difference events. These estimates hold for every H because they were integrated over a fresh independent embedding using only the fixed marginal bounds.

Choose now

At an embedding, encode each point by quantizing the real and imaginary parts of both Z_p,W_p in [-B-1,B+1], in half-open intervals of length at most \tau. Add an overflow code for points outside this box, using an endpoint convention to make a partition. This is a finite alphabet of size M=M(B,\tau) independent of t and of the field degree. An acceptance test at q asks whether the point code is attained by some actual neighbor of q. The actual point on an edge always passes.

By Lemma 2.7, D=o(\log t). Choose K\to\infty with K=o(\log t) and D/K\to0. Apply Corollary 3.2 to independent uniform embeddings as tests. It gives a fixed strict-prefix history map with at most M^{K-1}=t^{o(1)} values for which the predicted acceptance failure at a fresh embedding is o(1). The choice of history is made after averaging the prediction failure over that fresh embedding; the embedding itself is not fixed. The geometric error bounds just proved remain valid for this selected history.

Use this H in (4.11), with one common prediction \widehat p and three independently sampled neighbors of p. Each pair (\widehat p,q_j) has the prediction law in the acceptance estimate, so all three tests pass outside probability o(1) by a union bound. Moreover

For j\ne l, the conditional uniform neighbor law gives \Prob(q_j=q_l)\le1/\min_p d(p)=o(1). Distinct centers have distinct Z-coordinates, so q_j\ne q_l implies D_j\ne D_l. The degree and atom estimates used here follow from Proposition 2.4. Combining all these estimates gives positive probability that all three tests pass, all displayed quantities are bounded by B, and

Fix such an outcome and suppress \sigma from the notation. Successful acceptance provides, for each j, a genuine neighbor of q_j in the same code as \widehat p. Since the latter has coordinates bounded by B, this is a nonoverflow code, and the two complex coordinate errors are at most \sqrt2\tau. Comparing with that neighbor’s exact edge equation gives

Set \Delta Z=Z_{\widehat p}-Z_p and \Delta W=W_{\widehat p}-W_p. Subtracting the exact equation for (p,q_j) yields

Subtract the equation with j=1 from those with j=2,3. The coefficient matrix for (\Delta Z,\Delta W) has determinant

Its absolute value is at least r^3/B^3 by (4.14). Each matrix entry is at most 2B, and each right-hand side is at most 16B\tau. Cramer’s rule therefore gives

contradicting (4.14). This excludes every bounded subsequence of S and proves the proposition.□

Proof. At a nonarchimedean entry, n_e>s means |d_e|_v<e^{-s} and |d_e^{-1}|_v>e^s, so exactly A agrees. For n_e<s the two conclusions reverse. Only s=n_e is excluded, a null set for the level measure.

At infinity, put r=|s-n_e|. The smaller coordinate jump divided by its grid scale is e^{-r}, so its mismatch probability under a uniform shift is at most \sqrt2e^{-r}. The larger jump divided by its scale is e^r; it cannot lie in the same cell once r\ge\log\sqrt2, by the diameter of a half-open square. Consequently the expected inconsistency indicator is at most

Its integral over the full real line is bounded by an absolute constant, and hence so is its integral over I_v. Sum over entries using total archimedean weight one, then average over edges. There are only finitely many archimedean shifts to choose at each index, so averaging fixes shifts satisfying (4.18).

The match implications follow directly from the equivalence classes and the square diameter. For measurability, label nonarchimedean classes by the first vertex in a fixed ordering of P\cup Q, and use integer cell indices at infinity. All class comparisons are threshold comparisons and all cell indices are measurable functions of s.□

Proof. The incidence estimates give D=o(\log t) and d_{Q,\min}\to\infty. For example, first take K=\lceil\sqrt{(D+1)\log t}\rceil and then choose L\to\infty with \log L\sim\sqrt{\log t/K}. These choices give (5.1). Both K\log L/\log t and the parenthesized expression in (5.2) tend to zero. Choosing k\to\infty sufficiently slowly gives (5.2). Its stated consequences follow directly; in particular k=o(\log t) since K\log L\to\infty.□

Proof. The first inequality was just proved, and its right side is uniformly O(\epsilon+1/k)=o(1). If both endpoints have the dominant label, a consistent edge has the majority bit. Every minority-bit edge therefore has an exceptional endpoint or is inconsistent, proving the second inequality. Integrating and using \int m=O(1) proves (5.5) because S\to\infty.

For the joint errors, apply Lemma 2.6 with the uniform marginal bound a_t=C(\epsilon+k^{-1})\to0 from (5.4). Its edge estimate gives \Prob_E(I_p=I_q=1)=o(1)(h_P+h_Q), and its ordinary-wedge estimate gives \Prob(I_p=I_r=1)=o(1)h_P. These are exactly the edge and wedge laws used here. Both multipliers are uniform over all levels in \mathcal G, so they can be taken outside the integrals. Equation (5.5) then gives (5.6).□

Proof. The first assertion is immediate for ordinary stars. For the third, the (p,q) marginal of (5.9) is the edge law since \sum_\theta a(q,\theta)=1; sampling a conditional slot preserves this marginal. More explicitly, a slice of positive probability w_\theta=\sum_{p,q}\omega(p,q,\theta) has one-edge law \omega(p,q,\theta)/w_\theta and must be averaged with weight w_\theta. One can also attach a template independently at a Q base: conditional on (q,\theta) its two point neighbors still have their original law, and its single-slot law in each slice is the same as for P\theta.

Fix p and put a_p(\theta)=\Prob(\theta\mid p). For a_p(\theta)>0,

Its collision probability is at most its largest atom. Multiplying by a_p(\theta) and summing over at most M positive-mass templates gives the asserted bound pointwise in p.□

Proof. The left side of (5.11) is [2\lambda(a-T)]_+. For it to be positive both intersections must have positive length, since either has length at most T. As J is an interval, this puts both b,b' in its open interior, also when b=b'. Moreover a\le2T and a\le|J|, since I_- and I_+ have disjoint interiors. Hence 2(a-T)\le a\le|J|. For (5.12), take u<v in the interior. Then

Exhausting the open interior by such intervals proves the claim. The empty-interior case is immediate. This proof makes no assumption about atoms at either endpoint of J.□

Proof. First fix a base and two distinct opposite endpoints, and write d,d' for their incident jumps. Distinct real endpoints have distinct z coordinates, so d\ne d'. At a place v let

The two opposite-endpoint coordinate differences are d-d' and 1/d-1/d' up to signs. Therefore

All thresholds lie within the chosen level interval, so the integrated bit-difference charge at this place is exactly b'-b.

Let c_v=\log2 at archimedean entries and c_v=0 otherwise. The triangle inequality gives \alpha\ge-c_v, hence T_v:=\alpha+c_v\ge0. Equality of a grid label at infinity bounds the corresponding difference by \sqrt2 times the grid scale; at a finite place a matching label bounds it by the scale itself. If both bits are 1, a positive charge requires s<b and a B_1 match, which gives

If both bits are 0, the analogous A match gives s\ge b' and s\le b+\alpha+c_v\le b'+T_v. Thus all positive charges lie in

Enlarging to these full intervals is legitimate even if part of them lies outside the chosen level interval.

Suppose a rare positive is counted with minority bit 1 at a threshold s_0. Then s_0<b and \Prob_E(n_e(v)>s_0)<\epsilon. By monotonicity every common level and every level with minority bit 0 lies below s_0; none can produce a positive charge in I_+. All minority-1 positive charges lie in I_- by definition. The case of a rare positive with minority bit 0 is symmetric. Thus, if any rare positive is counted, all positive charges are on one side, their coefficients are at most 2, and their total is at most 2T_v.

Otherwise only common positives remain. For this fixed base put

This is an interval because the conditional edge law is fixed across levels and both restrictions are intervals. Extend the coefficient 1-\lambda across both full intervals in (5.15), increasing it by 2\lambda on J_v. Lemma 5.4 bounds the excess over 2T_v by

This expression is also a valid excess bound in the rare-positive case, when no excess is needed. Combining it with the negative charge and (5.14), then summing over places, cancels the logarithm by the product formula for the fixed nonzero element (d-d')(1/d-1/d'). The additive allowance is 2\sum_v^*c_v=2\log2. Places of zero level width can be included in this sum: their positive and negative charges vanish and the same upper bound still holds.

Now average this bound over the fixed-base independent pair law, restricting to distinct pairs. Dropping that restriction only in the nonnegative excess term, (5.12) bounds its expectation by 4\delta^2\lambda|J_v|. Boundary atoms are not counted; distinct jumps with equal thresholds cause no exception to this argument. On J_v, 2\rho(1-\rho)\ge2(1/4-\delta^2). Averaging over bases and places therefore bounds the distinct-pair contribution by

It remains to bound equal endpoints, to which the product formula was not applied. Their positive score is at most 2(W_c+H_x^*) for a base vertex x, and their negative score is zero. The ordinary collision probabilities are 1/d(q) and 1/d(p). For templated stars Lemma 5.3 gives the bound M/d(p) pointwise in p. Consequently their total contributions are at most, respectively,

Each is o(S) by Lemmas 5.1 and 5.2, (5.8), and d_{P,\min}=t^{1+o(a)}. In particular multiplication by an unbounded H_p^* requires only its first moment, since the collision estimate holds for every p. Finally O(1)=o(S).□

Proof. At a good rare level denote the inconsistency indicator in slot j by M_j. If I_x=1, both other endpoints are normal, and both edges are consistent, their dominant-coordinate labels match each other but differ from the base’s. Both bits must therefore be the minority bit and the required nonshared coordinate matches. The positive score is consequently at least

If both opposite endpoints are normal and both edges consistent, their bits agree regardless of whether the base is exceptional. Hence the negative charge is at most I_{y_1}+I_{y_2}+M_1+M_2. Average these two pointwise bounds. Each slot has the original edge marginal by Lemma 5.3, even with templates. The integrals of the joint terms I_xI_{y_j} are o(S) by (5.6); the inconsistency integrals are O(1). This gives (5.16) on \mathcal G. On \mathcal B there are no positives and the negative score is at least -1, whose total cost is W_b=o(S).□

Proof. Adjoin independent samples X_{k+1},\ldots,X_{2k}. If the first k samples admit a cross as in the event, select one by a fixed ordering. For this selected cross, the number of misses among the new samples has mean k\beta, where \beta=\nu(R_y^c)>\alpha, and variance at most k\beta. Thus the probability of fewer than k\alpha/2 misses is at most 4/(k\beta)\le1/2. It suffices to bound twice the probability that some cross contains the first half and misses at least k\alpha/2 of the second half.

Condition on the pooled 2k samples and split their indices uniformly into two halves. A cross induces at most (2k+1)^2 different subsets of these indices: its first coordinate can agree with one of at most 2k observed coordinates, or none, and the same holds for its second coordinate. If a pattern has m misses, the probability that they all fall in the second half is zero for m>k, and otherwise is

The union bound proves the first assertion. Repeated sampled states cause no problem, since the argument concerns the indexed samples.

For the second assertion, after sampling the histories independently given q, independently sample a state from each corresponding \nu_{h_j}. Before the histories are revealed these states are independent with law \widetilde\nu_q. If a candidate violating the required conclusion exists, select one as a function of the template. Conditional on that template, all the synthetic states lie in its cross with probability at least 1-k\cdot k^{-2}=1-1/k. Apply the first assertion with \alpha=k^{-1/4} and divide by 1-1/k.□

Proof. Conditional on (q,\theta), the history of the actual point has its ordinary conditional law given q, because the template is independent of the point given q. Hence on G,

The event that this support has \nu_{H(p)}-mass less than 1-\eta therefore has probability at most 3\eta.

For each history h, define three exceptional sets using only \nu_h. If a row has mass at least 1-\eta, it is unique, and the first exceptional set is its complement. If no such row exists, the first exceptional set is empty. Define the second set in the same way for columns. Their masses are at most \eta each.

If a set of at most two states has mass at least 1-\eta, put

and take M_h^c as the third exceptional set. Every set U of at most two states and mass at least 1-\eta contains M_h: omitting an atom of mass greater than \eta would violate that mass bound. Choosing one such U also gives

If no such U exists, the third exceptional set is empty. The union of the three exceptional sets thus has mass at most 5\eta.

The actual point has marginal law \mu, under which its state conditional on H=h has distribution exactly \nu_h. Consequently the probability of this union of exceptional sets is at most 5\eta under the entire edge–template law. Outside it and the earlier nonconcentration event, the actual state belongs to whichever permitted support was selected. Adding the two error bounds proves the result.□

Proof. Fix a common level. For each template of positive probability, let \pi_\theta=\Prob(\theta) and b_\theta=\Prob(\text{bad edge}\mid\theta), with both probabilities taken under the joint law in Lemma 6.2. In the center-star experiment, condition on \theta and then sample q by its actual conditional law. The two points are still independent with their ordinary law given q. In the point–template-star experiment, sample p conditional on \theta, then two independent centers given (p,\theta). Each slot in either experiment has the same conditional single-edge law \Prob(p,q\mid\theta). Therefore a pair with at least one bad slot has probability at most 2b_\theta in either experiment.

Write V_Q(\theta) and V_{P\theta}(\theta) for the corresponding averages of 2\rho(1-\rho) over bases in this slice, and write d_Q(\theta),d_{P\theta}(\theta) for its two common-level expected scores. Each V is at most 1/2, and either score is at least the negative of its variation. We prove

with an absolute constant C. All coefficients in a common score are bounded by 1+\lambda, so charging a pair with a bad slot always costs at most an absolute multiple of its probability.

An empty candidate set. Every edge is bad, so b_\theta=1, and the boundedness of the scores proves (6.10) on increasing C.

One candidate state. At a fixed point–template base, two good edges have the same center state. Consistency forces their bits to agree, and the nonshared coordinate of their center states matches. Thus this star score is at least 1-\lambda-O(b_\theta) after averaging over its bases. The center-star score is at least -1/2. Their sum is at least 1/2-\lambda-O(b_\theta), which implies (6.10) because the two variations sum to at most one.

Two candidates sharing a coordinate, and all candidates in that row or column. The transfer using (6.4) places every good point in the same row or column. If it is a row, every good edge has matching A-coordinates and hence bit 1, by consistency; in the column case every good edge has bit 0. A bit difference in either pair experiment therefore requires a bad slot. This gives V_Q(\theta)+V_{P\theta}(\theta)\le4b_\theta. The lower score bound d_i\ge-V_i now proves (6.10).

Two candidates sharing a coordinate, and a third outside that row or column. The three witness crosses intersect in at most one state. If the intersection is empty, all edges are bad. Otherwise all good point states equal that one state. At a center base, two good edges consequently have equal bits and the required nonshared-coordinate match. Its score is at least 1-\lambda-O(b_\theta), and the other score is at least -1/2. The same estimate as in the singleton case applies.

No coordinate shared by distinct candidates. If there are at least three candidates, their common cross is empty and all edges are bad. Otherwise there are exactly two candidates. The good point states lie in their two opposite corners from (6.5). At either type of base, a good edge’s bit determines the state at the other endpoint. Thus two good edges with equal bits have the required collision. For the full conditional probability \rho at that base, their expected score is at least the left side of (6.7), less an absolute multiple of the probability of a bad slot. After averaging bases, each score is at least \lambda/2-O(b_\theta), which proves (6.10).

This completes the classification. Multiply (6.10) by its actual slice weight \pi_\theta, sum, and integrate over common levels. The error is C\int_{\mathcal C}\sum_\theta\pi_\theta b_\theta=o(S) by (6.6). This argument allows individual b_\theta to be large; no inverse slice weight or number of templates enters. The common contributions to D_Q+D_{P\theta} are therefore at least

The lower bounds in Proposition 5.6 outside common levels cancel their main terms, because the two star vertices are on opposite sides. Hence

where the last inequality is Proposition 5.5. Since 10\delta^2<1/4, this proves (6.8).

Finally the common contribution to D_Q is at least -C_Q. Proposition 5.6 and Proposition 5.5 therefore give

Use C_Q=o(S) to obtain (6.9).□

Proof. Choose a history with its marginal probability, then two independent points p',p'' from \mu conditional on that history. This is one fixed coupling throughout all levels, and each point marginal is \mu. At a level, the expected value of

is the integrand in (6.11).

For a distinct pair put Z=z_{p'}-z_{p''} and W=w_{p'}-w_{p''}, both nonzero. At a place with level interval [l,u], the endpoint conditions from (4.7) say l\le-\log|Z|_v and u\ge\log|W|_v. The A-match can hold only for s\le-\log|Z|_v+O_v(1), and the B_1-match only for s\ge\log|W|_v-O_v(1). Here the constants vanish at nonarchimedean places and are absolute at infinity. Therefore

The product formula, and total archimedean weight one, show that the integral over all levels is at most an absolute constant.

At a good rare level where neither point is exceptional, their dominant coordinate labels match, so F\ge0. In general at such a level

The contribution on damaged levels is at least -W_b. Removing all noncommon levels from the full integral consequently gives, for each distinct pair,

On the diagonal the common-level integral is exactly W_c. Its probability under the selected coupling is

Here |H(P)|\le L^{2K}=t^{o(1)} and the marginal degree bounds were proved in Section 2. Since W_c\le k^{1/16}S and k=t^{o(1)}, its contribution is o(S). Average the bound for distinct pairs, using the two marginals \mu, W_b=o(S), and S\to\infty. This proves T\le2\E_\mu H_p^*+o(S)=o(S).□

Proof. If the conclusion fails, restrict to a subsequence on which \E_\mu H_p^*=o(S). By (6.9), also \E_\kappa H_q^*=o(S), and Lemma 6.4 gives T\le o(S).

At a common level declare an ordinary edge bad if its test is inconsistent or if \nu_{H(p)}(R_{y_q})<1-k^{-2}. Its integrated probability is o(S), because Markov’s inequality bounds the second contribution by k^2\int_{\mathcal C}\E_E[1-\nu_{H(p)}(R_{y_q})]=o(S). Fix a point p and this level. Write b_p for its conditional bad-edge probability, \nu=\nu_{H(p)}, \zeta=k^{-2}, and

Let \mathcal Y_p be the states of its good neighbors. Every such state has \nu(R_y)\ge1-\zeta, and the actual point state belongs to each R_y, by consistency. Let d_P(p) be the common-level score at this ordinary point star, using its full bit probability \rho_p. We claim

As before, a pair with a bad slot costs only O(b_p); its probability is at most 2b_p. The strict-cross classification proves the claim as follows.

If \mathcal Y_p is empty, b_p=1, while d_P(p)\ge-1/2 and \tau(\nu)\ge-1, so the claim holds for an absolute C.

If \mathcal Y_p=\set{(a,b)}, put r=\nu_A(a), s=\nu_{B_1}(b). Since r+s\ge\nu(R_{(a,b)})\ge1-\zeta,

Two good neighbors have the same state and bit, so d_P(p)\ge1-\lambda-O(b_p). Their sum has the positive lower bound needed for (6.13).

If two states share a row, their common cross is in that row, of \nu-mass at least 1-2\zeta. Thus \tau(\nu)\ge(1-2\zeta)^2-1\ge-4\zeta. If every state is in that row, the actual point lies there too, since it belongs to the crosses of both distinct states. All good edges consequently have bit 1. Their full-law variation is at most 2b_p, and d_P(p)\ge-2b_p, proving the claim in this case. Columns give bit 0 and the same estimates. If there is a third state outside the row or column, the three crosses have intersection of size at most one and mass at least 1-3\zeta. It must be a singleton for large k. Both marginals then have an atom of at least that mass, giving

Together with d_P(p)\ge-1/2, this is more than sufficient.

Finally suppose no coordinate is shared by distinct states in \mathcal Y_p. Three such states are impossible, since the actual point belongs to all their crosses and their intersection is empty. In the remaining case there are two states differing in both coordinates. The two opposite corners carry \nu-mass at least 1-2\zeta. Each coordinate marginal therefore has at least that mass on a set of size two, so

The actual point is one of those corners. Its bit determines the good neighbor state; hence (6.7) gives d_P(p)\ge\lambda/2-O(b_p). This completes the proof of (6.13).

Average (6.13) over p and integrate on common levels. The bad-edge integral is o(S), and \zeta W_c\le k^{-31/16}S=o(S). The result is

The noncommon contribution to D_P is at least -o(S) by Proposition 5.6, under the present assumptions on both exception means. Therefore

and again 10\delta^2<1/4 yields C_P=o(S).

To finish, let V_P,V_Q be the ordinary star variations at any fixed level. Assign to each vertex its conditional majority bit, breaking ties in a fixed way. The probability that the bit on an incident edge differs from this label is at most the corresponding average variation, because \min(\rho,1-\rho)\le2\rho(1-\rho). Thus the two endpoint labels disagree on an edge with probability at most V_P+V_Q. When that sum is small, the matching-label consequence of expansion in Lemma 2.5 gives one bit label with total marginal exception probability O(V_P+V_Q). The edge bit differs from it with probability O(V_P+V_Q) as well. When the sum is not small the same bound follows from f\le1/2, with a larger absolute constant. Consequently

uniformly for all sufficiently large t. Integrating on common levels gives \int_{\mathcal C}f\le C(C_P+C_Q)=o(S).

On good rare levels, the minority-bit probability is bounded by the two marginal exception probabilities and the inconsistency probability, as in Lemma 5.2. Its integral is o(S) under the present assumptions. Damaged levels contribute at most W_b/2=o(S). Thus S=\int f=o(S), a contradiction. This proves (6.12).□

Proof. At a good rare level, let X,U,V be the exception indicators of p,q,q', and let I,I' be the inconsistency indicators of the two edges. Write P_+ for the rare positive charge in the point-star score: it equals two when p is exceptional, both bits are minority bits, and the two neighbors have matching nonshared coordinates; otherwise it is zero. Write N=\abs{Y_{pq}-Y_{pq'}}. If U=V=I=I'=0, the two bits are the same function of X: they are both majority bits for X=0, and both minority bits for X=1. In the latter case the nonshared coordinate of both neighbors has the dominant label, so P_+=2. Consequently, pointwise,

and hence

In particular, a simultaneous exception at p and at a neighbor is charged directly to the neighbor indicator.

For completeness, the upper bound for this rare-only score is also pointwise. Put d=z_p-z_q, d'=z_p-z_{q'}. These jumps are distinct and nonzero. At a place v, sort their thresholds as b\le b', and set

The triangle inequality makes T_v\ge0. Matching coordinates in a square cell of side length r gives distance at most \sqrt2 r, and matching nonarchimedean labels gives distance at most r. Thus positive charges with both bits one lie within [b-T_v,b], and positive charges with both bits zero lie within [b',b'+T_v].

Only one of these two intervals can contain a rare positive charge. Indeed every level where zero is the minority bit precedes every level where one is the minority bit. A zero-bit rare positive would require a threshold at least b', while a one-bit rare positive would require a later threshold strictly less than b, which is impossible. The total rare positive charge at this place is therefore at most 2T_v. The all-level negative charge is b'-b, because the level interval contains both thresholds. Moreover,

Summing over places, the product formula cancels this last expression. The archimedean weights sum to one, so the rare positives minus the all-level negative charge total at most 2\log2.

Integrating (7.3) gives a lower bound for that same score. Outside the good rare levels there are no positive terms, and the negative charge is at most W_c+W_b. Comparing the lower and upper bounds proves (7.2).□

Proof. Choose an absolute C_0 for which each of the two exception expectations in (7.1) is at most C_0S, for all sufficiently large indices. Put

On T, the deterministic last three terms of (7.2) have sum at most H_p^*, eventually, since

After absorbing them, we may cap each neighbor height at H_p^*:

for distinct q,q'. If a cap changes a term, that capped term already equals H_p^* and suffices for this inequality; otherwise the preceding inequality is unchanged.

Sample p with law \mu and two neighbors independently and uniformly given p. Restrict the left side to distinct neighbors. The exact conditional probability of distinctness is 1-1/d(p). On the nonnegative right side we can drop this restriction. Thus

where C_m is an absolute upper bound for 6\E_E m_{pq}. This calculation uses the distinctness probability at each individual point, so it remains valid even when its exception mass is very large.

We estimate the capped expectation by layer cake. For u\ge0 let

and write h_P(u)=\mu(F_u), h_Q(u)=\kappa(G_u). The marginal version of the expansion estimate from Section 2, with \eta=\gamma-1/2>0, is

Because h_P(u)\le C_0/R_0 and h_Q(u)\le1, the same multiplier

works at every threshold u, including thresholds where the center set has full measure. Tonelli’s theorem and Cauchy–Schwarz now give

The first integral equals the unknown tail first moment A_t, including its contribution below the threshold R_0S. Since d_{P,\min}\to\infty, (7.6) implies eventually

The last step is Young’s inequality. Consequently

as required.□

Proof. Let \mathcal G denote the good rare levels, and let I_{pq} be the levelwise inconsistency indicator. At a level in \mathcal G, write b\in\{0,1\} for the majority bit. Consistency gives

unless both endpoints are exceptional or the edge is inconsistent. In all cases the absolute residual in this identity is at most 2(X_pX_q+I_{pq}). Subtracting the identities for the two edges cancels the center contribution. At each place,

since both bits are single thresholds inside the level interval. It follows that (7.8) holds with

Its mean is o(S): the first term averages to C_Q=o(S), the joint edge exceptions have integrated expectation o(S), and the remaining bounds are in (7.1).

There is also the exact identity

On a good rare level with exactly one exceptional point endpoint, a normal center, and two consistent edges, the bits differ. More explicitly, at every good rare level,

If none of the terms subtracted is present, this is the preceding observation; if any is present, the right side is nonpositive. Integrating proves (7.9) with

The integrated joint point exceptions on a wedge and joint edge exceptions are o(S), by Lemma 5.2. Thus \E E_2=o(S) as well.□

Proof. Set W=H_p^*+H_r^* and Z=E_1+E_2. By Proposition 6.5, choose c_0>0, independent of t along the fixed sequence, such that \E W\ge4c_0S eventually. Choose \delta_t\to0 sufficiently slowly that \E Z/\delta_t=o(S). Before selecting any band, discard wedges with Z>\delta_tW. Their lost weight is at most

Also discard W<c_0S, losing at most c_0S. If W>2R_0S, its larger summand exceeds R_0S and is at least W/2. Thus Lemma 7.2 gives

The surviving weighted mass is at least 2c_0S, whereas every surviving wedge has W\le2R_0S. Its probability is therefore at least c_0/R_0.

Partition [c_0S,2R_0S] into at most 1+\lceil\log_2(2R_0/c_0)\rceil=O(\log(2R_0)) dyadic bands, using half-open endpoints except at the final endpoint. One band has the probability in (7.10); if J is its lower endpoint, then J\ge c_0S\to\infty, and (7.11) holds. The parameter hierarchy gives k=t^{o(1)}, so the lower bound in (7.10) is indeed t^{-o(1)}. Finally, if p=r, the left side of (7.9) is zero, whereas its right side is at least (1-\delta_t)W>0 for all sufficiently large indices. Such a wedge cannot survive.□

Proof. Write M for the number of popular circles. Every pair of distinct real points lies on at most two unit circles. Counting pairs on popular circles therefore gives

using \abs P=t^{1+o(1)}. The set P_{\rm mult} of points on at least two popular circles has size at most 2\binom M2\le t^{2/5+o(1)}, because distinct circles intersect in at most two points. The degree bounds give

Consequently wedges hitting P_{\rm mult} at either point endpoint have probability at most t^{-3/5+o(1)}. Centers in Q whose own unit circle is popular number at most M; wedges with such a center have probability at most t^{-9/5+o(1)}.

To bound the remaining bad wedges, fix p\notin P_{\rm mult} and a center q whose own circle is not popular, in the original sampling law. The point p belongs to at most one popular circle. If there is one, it differs from the unit circle centered at q, since the latter is not popular. Their intersection has at most two points. In this original law, r is a uniform neighbor of q, so the probability that it shares a popular circle with p is at most 2/d(q), even before requiring r\notin P_{\rm mult}. This proves (7.12).

For the comparison with the selected band, recall R_0=k^{1/8}, k=t^{o(1)}, and the explicit requirement k^{20}/\min_qd(q)\to0 in Lemma 5.1. The first two terms of (7.12), multiplied by R_0\log(2R_0), tend to zero by a fixed power of t. For the third term,

This establishes the required relative loss bound.□

Proof. Take the band from Lemma 7.4, and remove the wedges excluded by Lemma 7.5. Its probability remains at least c/(R_0\log(2R_0))=t^{-o(1)}, and all its endpoint pairs are distinct. For any fixed off-diagonal pair (p,r), its ordinary wedge probability is

Here the sum has at most two terms, since two distinct real points have at most two unit-circle centers. The retained wedges therefore contain at least

distinct ordered endpoint pairs, using \abs E=t^{2+2a+o(a)} and \min_qd(q)=t^{a+o(a)}. These pairs form \mathcal E. Choose one surviving witnessing center for each pair.

For its two jumps d=z_p-z_q, d'=z_r-z_q, the exact unit equations give w_p-w_q=1/d and w_r-w_q=1/d'. Hence

proving (7.13). The product formula gives

so (7.14) holds for all sufficiently large indices.

Finally, put

By (7.8) and (7.11), \norm{b_{pr}}_1\le2\delta_tJ, uniformly on all retained edges. On a complete rectangle, the unary profiles cancel, leaving

Its weighted absolute sum is at most 8\delta_tJ. Another use of the product formula bounds its height by 4\delta_tJ, proving (7.15) with \omega_t=4\delta_t. The popular-circle exclusion holds by construction.□

Proof. The height inequalities

prove the field assertion, since J_n\to\infty. These statements do not depend on representatives, and h(0)=0.

Suppose that u\in F satisfies u^m+a_{m-1}u^{m-1}+\cdots+a_0=0 with a_r\in k_0 and fixed m\ge1. At each finite index where the equation holds, the nonarchimedean triangle inequality gives \lvert u\rvert_v\le\max(1,\max_r\lvert a_r\rvert_v). At infinity the same estimate holds with the additional factor m: if \lvert u\rvert_v>1, divide the equation by \lvert u\rvert_v^{m-1}. Since the total weight of the infinite places is one,

This estimate holds on a large set of indices. Its right side is o(J_n), proving the claim.□

Proof. First, on a side whose locus is the plane, for each fixed degree bound D there is a b_D>0 such that every nonzero polynomial of degree at most D, even with coefficients depending on n, vanishes at at most t_n^{1-b_D} pruned vertices on a large set of indices. If this failed, choose at each index a polynomial maximizing its number of zeros among the finite vertex set. A maximum is attained because there are only finitely many subsets of that set. Failure of every fixed saving means that its zero count is t_n^{1-o(1)} along \mathfrak u. One of at most D irreducible factors then contains t_n^{1-o(1)} vertices. Their minimum degree supplies t_n^{2-o(1)} edges after restricting this side to a bounded-degree curve, contradicting minimality. This proves the uniform assertion. On a curve side, a nonzero polynomial of degree D in the selected z-coordinate has at most D zeros among the vertices, since real points have distinct z=x+iy.

Let the two pruned set sizes be m,n' and their edge density be \delta. Independent uniform vertices p_1,\ldots,p_N have a common-neighbor fraction X on the other side. Averaging degrees there and applying Jensen gives \E X\ge\delta^N. Therefore the number of ordered complete grids, initially allowing repetitions, is

Consider a fixed nonzero polynomial in the selected coordinates with coefficients in B_0. Choose representatives of its coefficients. Its vanishing among all ordered vertex tuples, before requiring edges, has a power saving:

on a large set, for some b>0 depending on the test. Here is an induction that also handles moving coefficients. View the polynomial as a polynomial in the last point block, and select one nonzero coefficient polynomial in the earlier blocks. The earlier tuples annihilating this coefficient have a power saving by induction. At every other earlier tuple, the remaining polynomial is nonzero, with a fixed degree bound. The uniform plane estimate, or the bounded root count for a curve block, bounds its zeros. Multiply by the upper bounds t_n^{1+o(1)} for the other block sizes and slightly decrease the saving. The starting case is exactly the one-block estimates. The finitely many coefficient identities and nonzero denominators involved hold on a large set.

There are countably many nonzero polynomial tests over B_0. Enumerate them as T_1,T_2,\ldots. For each fixed s, (8.6) and (8.7), with a finite union bound, show that on a large set some grid avoids all the first s tests. At index n, choose the largest feasible prefix length s_n\le n, and choose a grid avoiding that prefix. Include the validity of all representatives and denominators of a prefix in its feasibility requirement. If no prefix is feasible, use arbitrary number-field coordinates at that index. For every fixed s, the set where n\ge s and the first s tests are feasible is large; hence s_n\ge s on a large set. Each fixed polynomial test is therefore nonzero in the limiting grid. Only finite intersections of large sets were used.

For a curve equation f(z,w)=0, its positive w-degree and the transcendence of z show that w is algebraic over B_0(z). This proves all the transcendence assertions. The vertices and the assigned ratios at each chosen finite grid lie in F_n, so their classes lie in F.□

Proof. A derivation is an additive map satisfying the product rule; being a k_0-derivation means that it vanishes on k_0. Each \lambda_{i\ell} is transcendental over k_0 by Lemma 8.2. Put it in a transcendence basis of F/k_0, prescribe its derivative to be one and those of the other basis elements to be zero, and extend by the quotient rule to the rational function field. Since the characteristic is zero, this derivation extends uniquely over the algebraic extension to F [7, Theorems 1.5 and 4.1]. For an infinite algebraic extension, take the compatible extensions to its finite subextensions; uniqueness makes them agree on overlaps [7, Section 5].

We have thus obtained a witness derivation nonzero on each chosen ratio. The derivations form an F-vector space. A linear combination of the finitely many witnesses is nonzero on all ratios provided its coefficients avoid the zeros of a product of finitely many nonzero linear forms. This product is a nonzero polynomial over the infinite field F, so such coefficients exist.□

Proof. Over B_0(r_1,\ldots,r_j), all the left positions jointly have transcendence degree Nd_1, by (8.5). The right velocities and scalars consist of at most 3j elements. Adjoining them and then taking algebraic closure can reduce that transcendence degree by at most 3j. Therefore

If no individual point had degree d_1, subadditivity would bound the left side by N(d_1-1). This contradicts N>3j. The function-field assertion is the evaluation argument following Lemma 8.3, with \mathcal B=K_0.□

Proof. An odd valuation detects a nonsquare because the valuation of a square is even. We construct the stated valuations over K_0 in each possible locus case. All noncoincidences used in the constructions will first be proved from the original joint genericity over B_0.

The left locus is the plane. The polynomial

is irreducible in K_0[z,w]. It is primitive as a polynomial in w, because its leading coefficient z-z_{r_\ell} is coprime to its constant coefficient, and is linear over K_0(z). The polynomials Q_\ell are distinct, as comparison of the coefficients of z and w recovers their centers. None divides any L_m=(z-z_{r_m})(w-w_{r_m}). The exponent of Q_\ell in a rational function is therefore the required valuation.

The left locus is a curve, and either the loci differ or its z-projection has degree at least two. Let f(z,w) be its irreducible equation and set a=z_{r_\ell}. The coordinate a is transcendental over B_0. Consequently the leading coefficient of f in w does not vanish at a, and f(a,w) has simple roots: the coprimality of f,f_w over B_0(z), after clearing denominators, excludes multiple roots at this transcendental abscissa.

If V_2\ne V_1, the anchor r_\ell is not on V_1. Indeed it is generic on V_2, which is either the plane or a different irreducible curve. Choose any root b of f(a,w). Then b\ne w_{r_\ell}. If V_2=V_1 and the projection degree is at least two, choose a root other than w_{r_\ell}, again obtaining b\ne w_{r_\ell}. In both cases

The ordinate b is algebraic over B_0(a). Since K_0 contains a and is algebraically closed, b\in K_0.

For m\ne\ell, original joint genericity implies that r_m remains generic on V_2 over B_0(s_\ell). Adjoining the sheet ordinate is an algebraic extension of adjoining a, so it does not reduce the transcendence degree of this independent anchor. Neither coordinate of r_m equals the corresponding coordinate of s_\ell: both projections of a curve are nonconstant, and the assertion for a plane is immediate. Thus L_m(s_\ell)\ne0. Also L_m(s_\ell)\ne4. Otherwise generic evaluation would force V_2 to lie in

The plane cannot do so. If V_2 is a curve, this irreducible circle equation must be proportional to its defining equation. Normalize the coefficient of zw to one. The coefficient of w then recovers -a from coefficients in B_0, contradicting the transcendence of a over B_0. These are nonvanishing statements in \mathcal U; placing more of their entries in K_0 cannot change them.

To obtain the valuation over K_0, introduce an indeterminate T and solve

recursively in K_0[[T]]. At each step the coefficient of the new unknown is f_w(a,b)\ne0, so the solution exists uniquely. This gives an embedding K_0(V_1)\hookrightarrow K_0((T)). Indeed z maps to the transcendental element a+T, and irreducibility of f over K_0(z) shows that its only polynomial kernel is (f). Now

has order one, while L_\ell-4 and all L_m(L_m-4), m\ne\ell, have nonzero constant terms. The order in T is the required valuation.

Both loci are the same curve with projection degree one. The symmetry of this curve shows that the other projection has degree one as well. Its irreducible equation therefore has degree one in each variable. Solving for w gives either

or

The constants here belong to B_0. To see the classification directly, write the equation as azw+cz+dw+e_0=0. If a=0, both linear coefficients are nonzero. If a\ne0, complete the product; its constant is nonzero by irreducibility. In (8.14), b\ne1, by the exact unit-circle exclusion (8.4).

In the line case, writing a_\ell=z_{r_\ell},

Thus L_\ell-4 has two distinct simple zeros. Choose one, say z=a_\ell+c with c^2=4/e, and let s_\ell be the corresponding point on the line. Its coordinates are algebraic over B_0(a_\ell). For an independent anchor r_m, the conditions L_m(s_\ell)=0 or 4 would make a_m one of finitely many elements algebraic over this field. This contradicts the joint genericity. Since L_\ell=4 at the chosen zero, order at that abscissa in the rational function field K_0(z) gives the required valuation.

In the fractional-linear case, put \zeta=(z-u)/(a_\ell-u), where a_\ell-u\ne0. Direct substitution gives

The equation L_\ell-4=0 is equivalent to

Its discriminant is 16(1-b)\ne0, and its two roots are nonzero because b\ne0. Hence they give simple zeros of L_\ell-4 at finite points with z\ne u. The corresponding point s_\ell is algebraic over B_0(a_\ell). As a function of the other anchor abscissa a_m, its squared distance to that anchor is

This is a nonconstant rational function: its numerator has degree two and its denominator degree one, and z_{s_\ell}\ne u. Its values cannot be zero or four at the transcendental a_m over B_0(s_\ell). Thus the simple zero is shared by no other radicand, and order at its abscissa again gives the valuation over K_0(z).

These cases exhaust the possibilities. In each, a nonempty product \prod_{\ell\in I}D_\ell has valuation one at any v_\ell with \ell\in I, and therefore is not a square.□

Proof of Theorem 1.1. If no absolute power saving existed, the sequence reduction in Section 2 would give configurations with t^{4-o(1)} ordered unit pairs. Specialization and restriction would give the incidence pieces used throughout the proof. Their height scales S have a bounded subsequence or a subsequence tending to infinity. The bounded alternative is excluded by Proposition 4.4. In the unbounded alternative, Proposition 7.6 supplies the graphs, scales J, edge ratios, uniform height bounds and popular-circle deletion required by Proposition 8.1. That proposition excludes the other alternative. Hence some fixed exponent below 4/3 admits a uniform bound. Increasing the exponent to at least one preserves this bound and keeps it below 4/3. Enlarging the positive constant covers the finitely many remaining sizes n\ge2, and passing from ordered to unordered pairs only changes the constant. The cases n=0,1 are immediate. This proves the theorem.□