Introduction
Markoff’s study of indefinite binary quadratic forms led to the equation
x 2 + y 2 + z 2 = 3 x y z . x^2 + y^2 + z^2 = 3xyz. x 2 + y 2 + z 2 = 3 x y z .
The positive integral solutions are generated from ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) by permutations and Vieta involutions, such as z ↦ 3 x y − z z \mapsto3xy-z z ↦ 3 x y − z . In the theory of indefinite forms, the largest entry of a triple determines the corresponding normalized minimum above 1 / 3 1/3 1/3 [9 , 12 ] . Hurwitz extended the descent to equations in arbitrarily many variables [8 ] . For the equation ∑ i = 1 n x i 2 = a ∏ i = 1 n x i \sum_{i=1}^{n} x_i^2 = a\prod_{i=1}^{n} x_i ∑ i = 1 n x i 2 = a ∏ i = 1 n x i , the involution in slot i i i replaces x i x_i x i by a ∏ j ≠ i x j − x i a\prod_{j\ne i}x_j-x_i a ∏ j = i x j − x i . The coefficient a = n a=n a = n gives the all-one solution. We study the associated rational recurrence, the multiplicity of the largest entry among integral solutions, and the graph of solutions over prime fields.
Laurent coefficients
With indeterminate initial coordinates, replacing one root by the other can be written as a division. For the pure equation the numerator is the sum of the squares of the other coordinates. A succession of such divisions can introduce intermediate denominators that are sums of monomials. Fomin and Zelevinsky proved that the final denominators are Laurent monomials, for this recurrence and more generally for a quadratic form with cross terms [6 Theorem 1.10] . Guéritaud obtained the Laurent property for a family with arbitrary square-free terms in the exchange polynomials and conjectured positivity of the Laurent coefficients [16 Proposition 11 and Conjecture 12] . His Theorem 1 proves the specialization with three variables and zero extra coefficients. Theorem 1 gives this specialization in every dimension. Its proof tracks matchings between factors of a conserved Laurent polynomial and subwords of the mutation sequence.
Multiplicity of the largest entry
Frobenius asked whether a positive Markoff triple, up to permutation, is determined by its largest entry [7 ] . Zagier proved an asymptotic of order ( log B ) 2 (\log B)^2 ( log B ) 2 for the number of sorted triples with largest entry at most B B B [12 ] . This counts triples with their multiplicities over a largest entry. Chen’s density-one theorem shows that the repeated largest entries account for a vanishing proportion in the classical equation [5 ] . Tang extended the density statement to the symmetric three-variable equation with a nonnegative integral coefficient of the three pairwise products [18 ] .
For pure Hurwitz equations, Baragar studied the growth of the number of solutions by height and established the growth exponent [2 , 3 ] . Gamburd, Magee, and Ronan subsequently obtained a counting asymptotic in the nonexceptional orbits of the Markoff–Hurwitz varieties by comparing the dynamics in logarithmic coordinates with a linear renewal problem [15 ] . The analogous density-one statement for the pure equation with coefficient n n n was published as a preprint in [10 ] . Theorem 2 proves density-one uniqueness in the family with a common nonnegative integral coefficient k k k on the products omitting one variable. The proof reduces equal maxima to collisions on rational graphs of integer labels, then to common continuations of Vieta moves from two fixed seeds.
Prime-field graphs
Baragar asked whether the graph of nonzero Markoff triples over a prime field is connected [1 ] . Bourgain, Gamburd, and Sarnak showed that for large primes all but a small number of vertices lie in a single orbit [4 ] . Chen’s divisibility theorem rules out small orbits for the classical equation outside a finite set of primes [13 ] . Martin subsequently gave a proof of the needed divisibility using a weight whose values cancel under the three Vieta involutions [17 ] .
In higher dimension Vyugin constructed a large component using cubic sections and an action allowing coordinate permutations and paired sign changes [11 ] . With only Vieta involutions as edges, a solution with two or more zero coordinates can only undergo sign changes. Such solutions obstruct connectivity on all nonzero points. Theorem 3 proves connectivity for fixed n ≥ 4 n \ge4 n ≥ 4 and all sufficiently large prime fields on the solutions having at most one zero coordinate. The argument joins the large orbits in the cubic sections, bounds the number of residual points independently of the dimension in the exponent of the prime, and applies a higher-dimensional version of Martin’s weighted congruence to rule out any residual orbit.
Laurent positivity for pure mutations
Theorem 1. Let n ≥ 3 n \ge3 n ≥ 3 and let x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n be algebraically independent. Starting with X i = x i X_i=x_i X i = x i , apply any finite sequence of replacements
X i ⟼ ∑ j ≠ i X j 2 X i , X_i \longmapsto\frac{\sum_{j\ne i}X_j^2}{X_i}, X i ⟼ X i ∑ j = i X j 2 , each of which fixes the other coordinates. Every resulting coordinate belongs to Z ≥ 0 [ x 1 ± 1 , … , x n ± 1 ] \mathbb{Z}_{\ge0}[x_1^{\pm1},\ldots,x_n^{\pm1}] Z ≥ 0 [ x 1 ± 1 , … , x n ± 1 ] .
Proof. The replacements are involutions, so we work with words whose consecutive directions are distinct. Set w i = x i 2 w_i=x_i^2 w i = x i 2 , L i = X i / x i L_i=X_i/x_i L i = X i / x i , and c i = ( ∑ j w j ) / w i c_i=(\sum_j w_j)/w_i c i = ( ∑ j w j ) / w i . The invariant is the quotient of the sum of squares by the product of the coordinates. In fact, if X i ′ = ( ∑ j ≠ i X j 2 ) / X i X_i'=(\sum_{j\ne i}X_j^2)/X_i X i ′ = ( ∑ j = i X j 2 ) / X i , then
X i 2 + ∑ j ≠ i X j 2 ∏ j X j = X i + X i ′ ∏ j ≠ i X j = ( X i ′ ) 2 + ∑ j ≠ i X j 2 X i ′ ∏ j ≠ i X j . \frac{X_i^2+\sum_{j\ne i}X_j^2}{\prod_j X_j}
=
\frac{X_i+X_i'}{\prod_{j\ne i}X_j}
=
\frac{(X_i')^2+\sum_{j\ne i}X_j^2}{X_i'\prod_{j\ne i}X_j}. ∏ j X j X i 2 + ∑ j = i X j 2 = ∏ j = i X j X i + X i ′ = X i ′ ∏ j = i X j ( X i ′ ) 2 + ∑ j = i X j 2 .
Equating this quotient with its value at the initial seed and dividing the resulting identity for X i + X i ′ X_i+X_i' X i + X i ′ by x i x_i x i gives
L i ′ = c i ∏ j ≠ i L j − L i . (1) L_i'=c_i\prod_{j\ne i}L_j-L_i. \tag*{(1)} L i ′ = c i j = i ∏ L j − L i . (1)
In particular, the coordinates are integral Laurent polynomials in every seed, since the same recurrence can be started at any seed and the inverse replacements are of the same form. Each replacement and its inverse are rational, so the coordinates in every seed are algebraically independent and generate the initial rational function field.
Records and their words. Attach to each coordinate a record of rows, initially empty. Each row has a color in { 1 , … , n } \{1,\ldots,n\} { 1 , … , n } and carries an interval ending at that row. At a replacement in direction i i i , concatenate the other records in decreasing order of length, keeping their colors and intervals at the copied positions, and append a row of color i i i . The interval ending at this row starts immediately after the end of the old i i i -record. The current records form a chain of prefixes, because the new record extends the previous longest record, which belongs to a direction different from i i i . The latest record is uniquely longest. If its length is d h d_h d h , then the sum of all current lengths is 2 d h − 1 2d_h-1 2 d h − 1 : the new longest length is the sum of the unchanged lengths plus one. Thus at the next replacement in direction i i i the appended interval has length 2 ( d h − d i ) 2(d_h-d_i) 2 ( d h − d i ) , where d i d_i d i is the old length in direction i i i .
We assign to each interval a word with the same color multiplicities as the rows of the interval. Call a family coherent if the assigned words of any intersecting intervals differ somewhere in their intersection. A word on a record is allowed if it does not equal any assigned word on its interval. The normalized weight of a word on rows of colors a 1 , … , a m a_1,\ldots,a_m a 1 , … , a m is ∏ v = 1 m w u v / w a v \prod_{v=1}^{m} w_{u_v}/w_{a_v} ∏ v = 1 m w u v / w a v , where u v u_v u v is its letter in row v v v . A word is balanced if its normalized weight is 1 1 1 . Empty words have weight 1 1 1 .
A coherent assignment gives L i L_i L i as the sum of the weights of the allowed words. Indeed, the sum before imposing the newest interval restriction, called the raw sum, is c i ∏ j ≠ i L j c_i\prod_{j\ne i}L_j c i ∏ j = i L j , since the appended row can carry any letter. If the new pattern is q q q , the excluded words are precisely the allowed old i i i -words followed by q q q : coherence guarantees avoidance of each interval that meets q q q , and the restrictions entirely in the prefix are exactly those of the old i i i -record. Their sum is L i L_i L i , by balance. This proves the claim by (1) . The same deletion rule applies to a suffix of a record when one retains only intervals contained in the suffix. If the new interval starts before the cut there is no deletion. We will construct the assignments inductively.
First activation. For a Laurent polynomial, its Newton polytope is the convex hull of its exponent vectors with nonzero coefficient. For weights on the seed coordinates, its support function is the maximum scalar product of a weight vector with an exponent vector. A subtraction-free expression for a nonzero Laurent polynomial has tropical evaluation equal to this support function, where multiplication adds weights, division subtracts them, and addition takes their maximum. Indeed, write the expression as P / Q P/Q P / Q with P , Q P,Q P , Q positive Laurent polynomials, and use the Minkowski sum identity for the Newton polytope of a product on P = ( P / Q ) Q P=(P/Q)Q P = ( P / Q ) Q . The identity follows because the leading parts in every weight have nonzero product.
A changed coordinate cannot contain any initial coordinate as a monomial in its support. Otherwise the support function of the initial coordinate is bounded by that of the changed one for every seed weight. This inequality transports to the chart containing the changed coordinate, by tropical evaluation of the subtraction-free coordinate changes. In that chart the changed coordinate has singleton Newton polytope, so the initial coordinate is an integer multiple of it. In the initial chart the reciprocal multiple is also integral, and positivity on the positive torus makes both multiples 1 1 1 . To see that the coordinates are distinct, evaluate the sequence at the all-one initial point. The first replacement gives n − 1 > 1 n-1>1 n − 1 > 1 . Every subsequent replacement changes a coordinate strictly smaller than the unique largest one, say X h X_h X h . The new value is at least X h 2 / X i > X h X_h^2/X_i>X_h X h 2 / X i > X h , so it becomes strictly largest. Each coordinate that has been replaced therefore has value greater than 1 1 1 .
When i i i is first activated, the raw sum is 1 + L i ′ 1+L'_i 1 + L i ′ , whose constant coefficient is 1 1 1 by the preceding support argument applied to the initial monomial x i x_i x i in X i ′ X'_i X i ′ . Thus there is exactly one balanced allowed word on the raw record. The new interval is the entire record, so assigning that word gives coherence.
A fresh letter and the first crossing of a cut. In a coherent history, add one coordinate of a new color a a a and leave it unchanged throughout the history. In dimension n + 1 n+1 n + 1 the additional record remains empty. Thus the records and patterns in the other directions are unchanged, while allowed words may now use the new letter. The old patterns are coherent on this larger alphabet, and the first-activation argument shows that the concatenation of the current records and a free last letter has a unique balanced allowed word when the last row has color a a a . The count is independent of the order of the blocks. Write Z r Z_r Z r for the part in record r r r . The word contains exactly one a a a .
Under a known coherent replacement in direction j j j , with new pattern q j q_j q j , let H H H be the old fresh word with its Z j Z_j Z j block removed and the other blocks arranged in the order used in the new j j j -record. The last free letter stays at the end. Then H H H is allowed in the new record. In fact, if H = U q j H=Uq_j H = U q j with U U U an allowed old j j j -word, then Z j U q j Z_jUq_j Z j U q j and U Z j q j UZ_jq_j U Z j q j both occur in the old fresh language arranged with the j j j -block first. They have the same content and are distinct because exactly one of Z j Z_j Z j , U U U contains a a a . This also rules out the case of empty Z j Z_j Z j . Hence H Z j q j HZ_jq_j H Z j q j is the new fresh word, by balance and uniqueness. After the first replacement it begins with a a a , and thereafter H H H begins with the preceding longest block. Inductively only the latest block contains a a a , at its first position. In particular a first-activation pattern begins with its own new color.
We record the behavior of the ordinary blocks Z r Z_r Z r . By the r r r -ray in a current seed we mean X r = t X_r=t X r = t and the other coordinates equal to 1 1 1 , with t t t tending to infinity. Equivalently, its tropical weights are 1 1 1 at r r r and 0 0 0 elsewhere. The weight of a word is the exponent of t t t in the leading term of its normalized weight after pulling the ray back to the initial seed. On the fresh ray the raw first-activation sum is 1 + ( n / t 2 ) 1+(n/t^2) 1 + ( n / t 2 ) in dimension n + 1 n+1 n + 1 . Its top term 1 1 1 is represented by the unique balanced word, so each Z r Z_r Z r is the unique leading word of its block.
In any open cone with a unique dominant coordinate, a reverse replacement at a different coordinate of degree R R R , when the maximum degree is M M M , gives degree 2 M − R > M 2M-R>M 2 M − R > M . Thus on a strict dominant cone a reduced reverse sequence whose first direction is different from the dominant coordinate has fixed max selectors and is invertible linear in the weights. A positive word sum whose support function is linear on the image of such an open cone has a single leading exponent throughout it. The reverse evaluations have leading coefficient 1 1 1 because each exchange has a unique largest summand. Hence in an allowed-word sum the leading exponent is represented by a single word. Dividing an actual coordinate by its initial variable shifts every weight by the same amount.
Let h h h be the latest direction and j ≠ h j\ne h j = h the next one. Undoing h h h on either the fresh ray or the old j j j -ray puts the weights in the same strict h h h -dominant cone. For all r ≠ h r\ne h r = h the coordinate is unchanged in this step. The inverse cone argument shows that Z r Z_r Z r is the unique leading word of its record on the old j j j -ray. On undoing j j j from the new fresh ray, the old j j j -weight is 2 2 2 , the fresh weight is 1 1 1 , and the other weights are 0 0 0 . This lies in the same strict j j j -dominant cone as the old j j j -ray, so for r ≠ j r\ne j r = j the new fresh block is the old j j j -ray leading word. Consequently the blocks Z r Z_r Z r with r ∉ { h , j } r\notin\{h,j\} r ∈ / { h , j } are unchanged by the replacement. The new block Z h Z_h Z h is the unique leading word of the old longest record on the old j j j -ray. From H Z j q j HZ_jq_j H Z j q j it is the prefix of length d h d_h d h of Z j q j Z_jq_j Z j q j .
Fix a current nonempty record in direction i i i from its most recent birth until its next replacement. An interval crosses its cut if it starts in the record and ends beyond it. Its head is the part of its pattern before the cut and its tail is the part after the cut. Every later longest record starts with the preceding longest record. Thus all crossing intervals are created by the successive appended rows in these longest records. The first crossing occurs in the direction j j j replaced immediately after the birth of the fixed record. Its tail, denoted by T T T , has length d i − d j d_i-d_j d i − d j , where d j d_j d j is the length just before the crossing. The old j j j -block followed by q j q_j q j equals Z j T Z_jT Z j T , by the transport formula. In particular the head of this first crossing matches Z i Z_i Z i .
Every later crossing tail starts with T T T . To prove this, label each nonlatest direction by a different original color, initially its own color after the first replacement. For a nonempty nonlatest record the label is the first letter of Z r Z_r Z r . At a replacement, the label of the replaced direction transfers to the previous latest direction by the formula Z j q j Z_jq_j Z j q j for its new prefix; when the old j j j -block is empty, q j q_j q j starts with j j j . Other labels stay in place by block stability. At a later crossing in direction r r r , the new block of the previous latest record starts with the old label of r r r , different from that of i i i . In this leading old r r r -ray word replace its prefix of length d i d_i d i by Z i Z_i Z i . The weight increases strictly, since Z i Z_i Z i is the unique leading word of that prefix. The resulting word must match some old forbidden interval, as it cannot be an allowed word of the previous latest record. The matched interval crosses the cut, since both parts separately avoid intervals contained in them. Its tail is a prefix of the new tail: after the cut the original leading word agrees up to its end with the corresponding part of q r q_r q r . By induction that old tail starts with T T T . This proves the assertion.
Thus a suffix is compatible with every allowed prefix of the fixed record exactly when it avoids the intervals internal to the suffix and does not start with T T T . Necessity follows by taking prefix Z i Z_i Z i for the first crossing. Sufficiency follows since every crossing tail starts with T T T . Write A = L i A=L_i A = L i for the fixed value, C = L j C=L_j C = L j just before the first crossing, and z , c z,c z , c for the normalized weights of Z i Z_i Z i after the crossing and the old Z j Z_j Z j , respectively. Balance of q j q_j q j gives the weight μ = c / z \mu=c/z μ = c / z of T T T . In addition,
A μ ≥ C ≥ c (2) A\mu\ge C \ge c \tag*{(2)} A μ ≥ C ≥ c (2)
where coefficientwise comparison means comparison at each Laurent monomial. Indeed, adjoining the head of q j q_j q j to any allowed old j j j -word gives an allowed word of the fixed record, by coherence. The head has weight μ − 1 \mu^{-1} μ − 1 , and the map is injective. The second inequality holds since the old Z j Z_j Z j contains no fresh letter.
A conserved quantity at the cut. For a current record extending beyond the cut, let E r E_r E r and F r F_r F r be the allowed-word sums on its suffixes after the cut and after the endpoint of the first crossing, respectively, imposing only the intervals contained in the indicated suffix. Then K r = E r − μ F r K_r=E_r-\mu F_r K r = E r − μ F r counts the suffixes compatible with every prefix. To check this, a word counted by E r E_r E r starting with T T T is exactly T T T followed by a word counted by F r F_r F r . Intervals internal to the first suffix that meet T T T conflict with its letters by coherence with the first crossing. Conversely, no other intervals constrain the remaining letters.
For shorter records set K r = 0 K_r=0 K r = 0 , and set K i = 1 K_i=1 K i = 1 . Put D r = L r − A K r D_r=L_r-AK_r D r = L r − A K r . After the first crossing these are positive word sums for the complements, including the zero sum. In particular ρ r = D r / L r \rho_r=D_r/L_r ρ r = D r / L r satisfies 0 ≤ ρ r ≤ 1 0\le\rho_r\le1 0 ≤ ρ r ≤ 1 on the positive torus and ρ i = 0 \rho_i=0 ρ i = 0 . For a replacement in direction r r r with latest direction h h h , set a r h = c r ∏ ℓ ≠ r , h L ℓ a_{rh}=c_r\prod_{\ell\ne r,h}L_\ell a r h = c r ∏ ℓ = r , h L ℓ . The suffix deletion rule gives
K r ′ = a r h K h − K r , D r ′ = a r h D h − D r . K'_r=a_{rh}K_h-K_r,\qquad D'_r=a_{rh}D_h-D_r. K r ′ = a r h K h − K r , D r ′ = a r h D h − D r .
For clarity, for both suffix cuts the raw sum comes from appending the other blocks and the free letter to the suffix of the latest record. The deleted sum comes from the suffix of the old r r r -record when its endpoint lies at or beyond the cut; if it lies before the cut the new interval is not internal and there is no deletion. After the first crossing, each endpoint other than the fixed one is either shorter than the fixed cut or at least as long as the endpoint of that crossing. Thus the rule applies at both cuts with the prescribed values. At the first crossing itself the recurrence holds if, only at its source, one takes K j = μ K_j=\mu K j = μ and D j = C − A μ D_j=C-A\mu D j = C − A μ : the compatible suffix sum is a j i − μ a_{ji}-\mu a j i − μ , since its only crossing tail ends at the appended row. All other source values have the usual definitions.
From (1) the ratio L r / ( L r + L r ′ ) L_r/(L_r+L'_r) L r / ( L r + L r ′ ) is X r 2 / ∑ s X s 2 X_r^2/\sum_s X_s^2 X r 2 / ∑ s X s 2 . Dividing the defect recurrence gives
( ∑ s ≠ r X s 2 ) ( ρ h − ρ r ′ ) = X r 2 ( ρ r − ρ h ) . \left(\sum_{s\ne r}X_s^2\right)(\rho_h-\rho'_r)=X_r^2(\rho_r-\rho_h). s = r ∑ X s 2 ( ρ h − ρ r ′ ) = X r 2 ( ρ r − ρ h ) .
It follows that
I = ∑ r X r 2 ρ r − ( ∑ r X r 2 ) ρ h I=\sum_r X_r^2\rho_r-\left(\sum_r X_r^2\right)\rho_h I = r ∑ X r 2 ρ r − ( r ∑ X r 2 ) ρ h
is invariant through the intervening replacements. Indeed, the new expression is ∑ s ≠ r X s 2 ( ρ s − ρ r ′ ) \sum_{s\ne r}X_s^2(\rho_s-\rho'_r) ∑ s = r X s 2 ( ρ s − ρ r ′ ) , and subtracting the old one gives zero by the preceding identity. At the source just before the first crossing, h = i h=i h = i and all ρ s \rho_s ρ s for s ≠ i s\ne i s = i equal 1 1 1 except ρ j = 1 − μ A / C \rho_j=1-\mu A/C ρ j = 1 − μ A / C . If Y Y Y denotes the physical coordinates immediately before the birth of the fixed record, then ∑ s ≠ i X s 2 = Y i x i A \sum_{s\ne i}X_s^2=Y_ix_iA ∑ s = i X s 2 = Y i x i A at the source by the birth exchange, and X j = Y j = x j C X_j=Y_j=x_jC X j = Y j = x j C . Therefore
I = x i A ( Y i − ( x j / x i ) μ Y j ) . (3) I=x_iA\left(Y_i-\left(x_j/x_i\right)\mu Y_j\right). \tag*{(3)} I = x i A ( Y i − ( x j / x i ) μ Y j ) . (3)
Decay on the revisit ray. At the target just before revisiting i i i , take the i i i -ray and pull it back through the known history. Degrees are degrees at infinity of the rational functions of t t t . Every reverse step gives a new unique maximum and preserves leading coefficient 1. The degree in direction i i i is odd and the other degrees are even. After undoing the intervening segment up to the birth of the fixed record, direction j j j has even degree D ≥ 2 D \ge2 D ≥ 2 . Direction i i i still has degree 1, and all other directions have degree at most D − 2 D - 2 D − 2 . Undoing the birth gives
deg Y i = 2 D − 1 , deg Y j = D , deg Y s ≤ D − 2 ( s ≠ i , j ) . \deg Y_i = 2D - 1,\qquad\deg Y_j = D,\qquad\deg Y_s \le D - 2\quad(s \ne i,j). deg Y i = 2 D − 1 , deg Y j = D , deg Y s ≤ D − 2 ( s = i , j ) .
At a further reverse replacement in direction r r r with dominant coordinate h h h , its exact exchange has the factor 1 + ∑ s ≠ r , h ( X s / X h ) 2 1+\sum_{s\ne r,h}(X_s/X_h)^2 1 + ∑ s = r , h ( X s / X h ) 2 multiplying X h 2 / X r X_h^2/X_r X h 2 / X r . Transporting a Laurent monomial from the state before the reverse step into the state after it replaces the exponent v r v_r v r by − v r -v_r − v r , increases v h v_h v h by 2 v r 2v_r 2 v r , and contributes this factor to the power v r v_r v r . The X s X_s X s in the factor are the unchanged coordinates, so it has the same value on either side.
Start with Y i / Y j Y_i/Y_j Y i / Y j . While the reverse directions stay in { i , j } \{i,j\} { i , j } , they alternate and the exponent vector is always ± ( e i − e j ) \pm(e_i-e_j) ± ( e i − e j ) , where e s e_s e s is the s s s -th unit vector. The error terms in the factors involve only coordinates of degree at most D − 2 D-2 D − 2 divided by a coordinate of degree at least 2 D − 1 2D-1 2 D − 1 , and therefore are O ( t − 2 D − 2 ) O(t^{-2D-2}) O ( t − 2 D − 2 ) . At the first direction outside { i , j } \{i,j\} { i , j } the exponent is zero. That step makes the gap between the two largest degrees at least D + 1 D+1 D + 1 . This gap cannot decrease: if the previous two largest degrees were M > L M>L M > L and the changed degree was R ≤ L R\le L R ≤ L , the new gap is M − R ≥ M − L M-R\ge M-L M − R ≥ M − L . All subsequent errors are again O ( t − 2 D − 2 ) O(t^{-2D-2}) O ( t − 2 D − 2 ) . Consequently
Y i / Y j = q ( x ) ( 1 + O ( t − 2 D − 2 ) ) . Y_i/Y_j=q(x)\left(1+O(t^{-2D-2})\right). Y i / Y j = q ( x ) ( 1 + O ( t − 2 D − 2 ) ) .
for the initial Laurent monomial q ( x ) q(x) q ( x ) obtained by the exponent transport. This includes the case of an empty reverse prefix.
We identify q ( x ) q(x) q ( x ) as a monomial in the initial variables, using the full exponent vectors. Every known coordinate has a unique leading Laurent monomial on the pulled-back ray: its positive expansion and the leading coefficient 1 preclude a second term of the same degree. In each reverse exchange the product of the leading monomials in the changed coordinate before and after the exchange equals the square of the dominant leading monomial. Thus the exponent transport for q ( x ) q(x) q ( x ) is precisely the transport of the quotient of the two leading monomials in Y i / Y j Y_i/Y_j Y i / Y j . By uniqueness of the leading word Z i Z_i Z i , A / z → 1 A/z\to1 A / z → 1 ; by (2) , 1 ≤ C / c ≤ A / z 1\le C/c\le A/z 1 ≤ C / c ≤ A / z . Hence the leading monomials in x i A x_iA x i A and Y j Y_j Y j are x i z x_i z x i z and x j c x_j c x j c . The birth exchange now gives q ( x ) = ( x j / x i ) c / z = ( x j / x i ) μ q(x)=(x_j/x_i)c/z=(x_j/x_i)\mu q ( x ) = ( x j / x i ) c / z = ( x j / x i ) μ . Since x i A = t x_iA=t x i A = t , (3) yields I = O ( t − 2 ) I=O(t^{-2}) I = O ( t − 2 ) .
Completion of the induction. At the target the conserved expression reads
I = ∑ r ≠ i , h ρ r − ( t 2 + n − 2 ) ρ h . I=\sum_{r\ne i,h}\rho_r-(t^2+n-2)\rho_h. I = r = i , h ∑ ρ r − ( t 2 + n − 2 ) ρ h .
Hence ρ h = O ( t − 2 ) \rho_h=O(t^{-2}) ρ h = O ( t − 2 ) . For the raw next i i i -record let B B B be its raw word sum and let K K K be the sum of the weights of its compatible suffixes. Raw concatenation gives K = a i h K h = ( B / A ) ( 1 − ρ h ) K=a_{ih}K_h=(B/A)(1-\rho_h) K = a ih K h = ( B / A ) ( 1 − ρ h ) . The physical exchange gives B / A = 1 + ( n − 1 ) / t 2 B/A=1+(n-1)/t^2 B / A = 1 + ( n − 1 ) / t 2 , so K → 1 K\to1 K → 1 . Since K K K has nonnegative integer coefficients, and each initial variable has leading coefficient 1, this means K K K has a unique top monomial of weight zero, with coefficient 1. Moreover A K ≤ B AK\le B A K ≤ B coefficientwise by concatenating each allowed prefix with each compatible suffix. Block stability identifies x i x_i x i with the weight of the current fresh i i i -block. The top monomial of B B B is z z z , with coefficient 1, since B = A + L i ′ B=A+L'_i B = A + L i ′ and the actual old and new i i i -coordinates have degrees 1 and − 1 -1 − 1 on this ray. The top monomial of A K AK A K must therefore equal z z z , forcing the top monomial of K K K to be 1. The resulting balanced suffix does not start with T T T , whereas every old pattern crossing the cut has a tail starting with T T T . It therefore differs from each crossing pattern on the overlap. It also avoids all forbidden intervals contained in the suffix, by the definition of K K K . Assigning this suffix to the new interval preserves coherence. Induction completes the proof. ∎
Density-one uniqueness of the maximum
Fix integers n ≥ 3 n \ge3 n ≥ 3 and k ≥ 0 k \ge0 k ≥ 0 . For B ≥ 1 B \ge1 B ≥ 1 , let T ( B ) T(B) T ( B ) count the sorted positive integral solutions of
∑ i = 1 n x i 2 + k ∑ i = 1 n ∏ j ≠ i x j = n ( k + 1 ) ∏ i = 1 n x i , x 1 ≤ ⋯ ≤ x n , \sum_{i=1}^{n}x_i^2+k\sum_{i=1}^{n}\prod_{j\ne i}x_j=n(k+1)\prod_{i=1}^{n}x_i,\qquad x_1\le\cdots\le x_n, i = 1 ∑ n x i 2 + k i = 1 ∑ n j = i ∏ x j = n ( k + 1 ) i = 1 ∏ n x i , x 1 ≤ ⋯ ≤ x n ,
with x n ≤ B x_n\le B x n ≤ B , and let D ( B ) D(B) D ( B ) count the distinct values of their last coordinate.
Theorem 2. For each fixed n ≥ 3 n \ge3 n ≥ 3 and k ≥ 0 k \ge0 k ≥ 0 ,
T ( B ) − D ( B ) = o ( T ( B ) ) ( B → ∞ ) . T(B)-D(B)=o(T(B))\qquad(B\to\infty). T ( B ) − D ( B ) = o ( T ( B )) ( B → ∞ ) .
The case n = 3 n=3 n = 3 follows from [18 Theorem 1.1] . We prove the result for n ≥ 4 n\ge4 n ≥ 4 and every k ≥ 0 k\ge0 k ≥ 0 . The higher-dimensional case k = 0 k=0 k = 0 also appears in [10 Theorem 1] .
A maximum attained by m m m solutions contributes m − 1 m-1 m − 1 to T ( B ) − D ( B ) T(B)-D(B) T ( B ) − D ( B ) . Since m ≤ 2 ( m − 1 ) m\le2(m-1) m ≤ 2 ( m − 1 ) for m ≥ 2 m\ge2 m ≥ 2 , the limit gives density-one uniqueness among both the solutions and their distinct maxima.
Descent and labels
For 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n , the Vieta involution replaces x i x_i x i by
n ( k + 1 ) ∏ j ≠ i x j − k ∑ ℓ ≠ i ∏ j ∉ { i , ℓ } x j − x i . n(k+1)\prod_{j\ne i}x_j-k\sum_{\ell\ne i}\prod_{j\notin\{i,\ell\}}x_j-x_i. n ( k + 1 ) j = i ∏ x j − k ℓ = i ∑ j ∈ / { i , ℓ } ∏ x j − x i .
Here and below the product over an empty set is one. This formula is the sum of the two roots minus the original root, so the new coordinate is integral. The product of the roots is ∑ j ≠ i x j 2 + k ∏ j ≠ i x j > 0 \sum_{j\ne i}x_j^2+k\prod_{j\ne i}x_j>0 ∑ j = i x j 2 + k ∏ j = i x j > 0 , so the new coordinate is positive.
For a sorted solution write its first n − 2 n-2 n − 2 entries as a 1 , … , a n − 2 a_1,\ldots,a_{n-2} a 1 , … , a n − 2 and its last two entries as b , c b,c b , c . Let f ( t ) f(t) f ( t ) be the monic quadratic obtained by replacing c c c by t t t and subtracting the right-hand side of the equation from the left. Then
f ( b ) = ∑ i = 1 n − 2 a i 2 + 2 b 2 − n b 2 ∏ i = 1 n − 2 a i + k b ( ∏ i = 1 n − 2 a i ) ( 2 + b ∑ i = 1 n − 2 a i − 1 − n b ) . f(b)=\sum_{i=1}^{n-2}a_i^2+2b^2-nb^2\prod_{i=1}^{n-2}a_i+kb\left(\prod_{i=1}^{n-2}a_i\right)\left(2+b\sum_{i=1}^{n-2}a_i^{-1}-nb\right). f ( b ) = i = 1 ∑ n − 2 a i 2 + 2 b 2 − n b 2 i = 1 ∏ n − 2 a i + k b ( i = 1 ∏ n − 2 a i ) ( 2 + b i = 1 ∑ n − 2 a i − 1 − nb ) .
The first three terms are at most n b 2 ( 1 − ∏ i = 1 n − 2 a i ) nb^2(1-\prod_{i=1}^{n-2}a_i) n b 2 ( 1 − ∏ i = 1 n − 2 a i ) , and they vanish only if all a i = b = 1 a_i=b=1 a i = b = 1 . The last term is at most 2 k b ( 1 − b ) ∏ i = 1 n − 2 a i ≤ 0 2kb(1-b)\prod_{i=1}^{n-2}a_i\le0 2 k b ( 1 − b ) ∏ i = 1 n − 2 a i ≤ 0 . Thus, unless all the first n − 1 n-1 n − 1 entries are one, f ( b ) < 0 f(b)<0 f ( b ) < 0 . The roots then lie on opposite sides of b b b , and the root c c c lies above b b b . If the first n − 1 n-1 n − 1 entries are one, the roots are 1 1 1 and n + k − 1 n+k-1 n + k − 1 , since their sum is n + k n+k n + k and one is a root. Consequently mutating the maximum of a nonconstant solution strictly decreases it, and repeating gives the all-one solution.
For a solution with a unique maximum, every mutation in a nonmaximum slot produces a new strict maximum. Indeed, if the old entries in that slot and in the maximum slot are x i < x n x_i<x_n x i < x n , the product of the two Vieta roots exceeds x n 2 x_n^2 x n 2 , since n ≥ 3 n\ge3 n ≥ 3 and an additional square occurs. The new root therefore exceeds x n x_n x n .
Put d = n − 1 d=n-1 d = n − 1 . Starting from ( 1 , … , 1 , n + k − 1 ) (1,\ldots,1,n+k-1) ( 1 , … , 1 , n + k − 1 ) , the ascending move with index i ∈ { 1 , … , d } i\in\{1,\ldots,d\} i ∈ { 1 , … , d } mutates slot i i i and then exchanges slots i i i and n n n , so the last slot holds the new maximum. Reversing the descending sequence constructs such a word for each sorted solution other than the all-one solution: at each step the coordinate to be increased is among the first d d d entries, and the permutation of those entries is recorded by the choice of its slot. If several words represent the same sorted solution, use the lexicographically first of minimum length, with the order 1 < ⋯ < d 1<\cdots<d 1 < ⋯ < d . The all-one solution contributes at most one to the counts and can be omitted from the estimates below.
For a word w = i 1 ⋯ i m w=i_1\cdots i_m w = i 1 ⋯ i m , let
A i = I + ( 1 − e i ) e i T , C A ( w ) = A i 1 ⋯ A i m , v ( w ) = C A ( w ) 1. A_i=I+(1-e_i)e_i^{\mathsf T},\qquad C_A(w)=A_{i_1}\cdots A_{i_m},\qquad v(w)=C_A(w)\mathbf{1}. A i = I + ( 1 − e i ) e i T , C A ( w ) = A i 1 ⋯ A i m , v ( w ) = C A ( w ) 1 .
Here I I I is the d d d -dimensional identity, e i e_i e i is its i i i -th column, and 1 \mathbf{1} 1 has all entries one. The product for the empty word is I I I . This is chronological matrix order. Each label is primitive, meaning that its integer entries have greatest common divisor one, because each A i A_i A i is integral with determinant one. The unique minimum of a nonempty label identifies its first letter, and subtracting this minimum from the other entries recovers the remaining label. The label of a solution x x x , denoted by v ( x ) v(x) v ( x ) , is the label of its chosen word. Distinct solutions have distinct labels.
Reduction to quantitative estimates
The counting bounds follow from Lemmas [6 ] and [7 ] and Proposition [11 ] . The partitions by prefixes and their error bounds are proved in Appendix § 6 , in particular (9) .
Write L = log B L=\log B L = log B , and use Euclidean and induced operator norms. The counting estimates give T ( B ) ≍ L β T(B)\asymp L^\beta T ( B ) ≍ L β , where β > 1 \beta>1 β > 1 is fixed, and ∥ v ( x ) ∥ = O ( L ) \lVert v(x)\rVert=O(L) ∥ v ( x )∥ = O ( L ) for each solution counted. For some fixed η > 0 \eta>0 η > 0 , the proportion of labels in a strip
∣ ℓ ( v ) ∣ ≤ t ∥ ℓ ∥ ∥ v ∥ |\ell(v)|\le t\|\ell\|\|v\| ∣ ℓ ( v ) ∣ ≤ t ∥ ℓ ∥∥ v ∥
is O ( t η + L − η ) O(t^\eta+L^{-\eta}) O ( t η + L − η ) , uniformly in nonzero linear forms ℓ \ell ℓ and 0 < t < 1 0<t<1 0 < t < 1 . In particular, proper subspaces contain O ( T ( B ) L − η ) O(T(B)L^{-\eta}) O ( T ( B ) L − η ) labels. For G ∈ GL d ( Q ) G\in\operatorname{GL}_d(\mathbb{Q}) G ∈ GL d ( Q ) , define
D G = [ Z d : { v ∈ Z d : G v ∈ Z d } ] , D_G=[\mathbb{Z}^d:\{v\in\mathbb{Z}^d:Gv\in\mathbb{Z}^d\}], D G = [ Z d : { v ∈ Z d : G v ∈ Z d }] ,
K ( G ) = max ( 2 , D G , ∥ G ∥ , ∥ G − 1 ∥ ) . K(G)=\max(2,D_G,\|G\|,\|G^{-1}\|). K ( G ) = max ( 2 , D G , ∥ G ∥ , ∥ G − 1 ∥ ) .
The number of pairs with v ( y ) = G v ( x ) v(y)=Gv(x) v ( y ) = G v ( x ) , both counted by T ( B ) T(B) T ( B ) , is
O ( T ( B ) ( K ( G ) − η + L − η ) ) . O\bigl(T(B)(K(G)^{-\eta}+L^{-\eta})\bigr). O ( T ( B ) ( K ( G ) − η + L − η ) ) .
If G G G is determined by d d d independent such pairs, Cramer’s rule gives K ( G ) = O ( L d ) K(G)=O(L^d) K ( G ) = O ( L d ) . By decreasing η \eta η the pair bound then becomes
O ( T ( B ) K ( G ) − η ) . O\bigl(T(B)K(G)^{-\eta}\bigr). O ( T ( B ) K ( G ) − η ) .
For a solution x x x , put
h ( x ) = log ( ( n ( k + 1 ) ) 1 / ( n − 2 ) ( x n − k n ( k + 1 ) ) ) . h(x)=\log\left((n(k+1))^{1/(n-2)}\left(x_n-\frac{k}{n(k+1)}\right)\right). h ( x ) = log ( ( n ( k + 1 ) ) 1/ ( n − 2 ) ( x n − n ( k + 1 ) k ) ) .
The excision estimates give finite partitions by ascending prefixes after deleting exceptional vertices. Each part p p p has a linear form λ p \lambda_p λ p . For an integer-vector norm cutoff M > 0 M>0 M > 0 , the constants τ , δ > 0 \tau,\delta>0 τ , δ > 0 are common to the parts and satisfy
∣ λ p ( b ) ∣ > τ ( 0 < ∥ b ∥ ≤ M , b ∈ Z d ) , ∣ h ( x ) − λ p ( v ( x ) ) ∣ ≤ δ ∥ v ( x ) ∥ . |\lambda_p(b)|>\tau\quad(0<\|b\|\le M,\ b\in\mathbb{Z}^d),\qquad|h(x)-\lambda_p(v(x))|\le\delta\|v(x)\|. ∣ λ p ( b ) ∣ > τ ( 0 < ∥ b ∥ ≤ M , b ∈ Z d ) , ∣ h ( x ) − λ p ( v ( x )) ∣ ≤ δ ∥ v ( x ) ∥.
For any fixed exponent A A A one may take δ ≤ τ / ( 100 M A ) \delta\le\tau/(100M^A) δ ≤ τ / ( 100 M A ) . With M M M a sufficiently large fixed multiple of L d + 1 L^{d+1} L d + 1 , the number of parts is L o ( 1 ) L^{o(1)} L o ( 1 ) and the deleted proportion is O ( ϵ ) + o ( 1 ) O(\epsilon)+o(1) O ( ϵ ) + o ( 1 ) for any fixed $\epsilon>0. There are also partitions for integer bands j j j with M = exp ( κ j ) M=\exp(\kappa j) M = exp ( κj ) , for any fixed κ > 0 \kappa>0 κ > 0 . They have P j = exp ( o ( j ) ) P_j=\exp(o(j)) P j = exp ( o ( j )) parts and deletion proportion O ( ( j + 1 ) − 2 + L − η 0 ) O((j+1)^{-2}+L^{-\eta_0}) O (( j + 1 ) − 2 + L − η 0 ) for some η 0 > 0 \eta_0>0 η 0 > 0 , uniformly up to j ≤ a log 2 L j\le a\log_2 L j ≤ a log 2 L for fixed small a > 0 a>0 a > 0 . These estimates use a fixed cutoff on initial cusp runs. The relative count omitted by this cutoff tends to zero as the cutoff tends to infinity.
Fixed graphs
For each fixed G ∈ GL d ( Q ) G\in\operatorname{GL}_d(\mathbb{Q}) G ∈ GL d ( Q ) , the number of off-diagonal equal-maximum pairs on its graph is o ( T ( B ) ) o(T(B)) o ( T ( B )) . To see the passage from the boundary theorem to the finite claim, let B i = A i T B_i=A_i^T B i = A i T , let J J J be the all-one matrix, and put U = J − I U=J-I U = J − I . Direct multiplication gives A i = B i = U − 1 J U C B ( w ) A_i=B_i=U^{-1}JUC_B(w) A i = B i = U − 1 J U C B ( w ) by replacing each A i A_i A i in C A ( w ) C_A(w) C A ( w ) by B i B_i B i . The graph in the new coordinates is given by U − 1 G U U^{-1}GU U − 1 G U .
The accelerated coding groups consecutive copies of one letter into runs and records the ordering of the first d d d labels. We first fix a cutoff on the initial run excluded from the accelerated alphabet. Among retained words, condition on each of the finitely many initial runs and initial orderings at the two endpoints. For respective initial words w 0 , u 0 w_0,u_0 w 0 , u 0 , the rational graph for the continuing directions is C B ( u 0 ) − 1 U − 1 G U C B ( w 0 ) C_B(u_0)^{-1}U^{-1}GUC_B(w_0) C B ( u 0 ) − 1 U − 1 G U C B ( w 0 ) . The boundary and prefix estimates then apply from the corresponding starting states. At the end the cutoff tends to infinity, using the initial-run estimate in Appendix § 5 . The prefix estimate bounds the normalized count of finite words having their first q q q runs in any measurable prefix event by a constant times its Gibbs probability, with the constant independent of q q q . For fixed q q q , words shorter than q q q runs have normalized count tending to zero. The Gibbs transitions have a uniform summable tail in the run exponent. Represent the direction of a finite word w w w by C B ( w ) 1 / ∥ C B ( w ) ∥ C_B(w)1/\lVert C_B(w)\rVert C B ( w ) 1/ ∥ C B ( w )∥ . Directions sharing q q q fixed runs differ by O ( ρ q − 1 ) O(\rho^{q-1}) O ( ρ q − 1 ) for some ρ < 1 \rho< 1 ρ < 1 . Indeed, evaluate their products from right to left, starting from the two tails after the shared runs. After applying the last shared run, their simplex representatives both have its index as a largest coordinate. Their joining segment has that property as well. Each of the remaining shared runs chooses a different label from its predecessor and therefore uses a nonlast slot. Subdivide the segment according to the order of its coordinates, breaking ties by a fixed order that places the active largest coordinate last. On each piece the sequence of ordered branches is fixed, because each switch moves the selected label to the end. The uniform contraction from Appendix § 5 gives the bound on each piece and hence on the entire segment. This proves uniform convergence and continuity of the boundary directions in the run coordinates.
Suppose the normalized collision count stays bounded below along a subsequence. Extend both words in each pair with legal runs of exponent one and give each pair mass 1 / T ( B ) 1/T(B) 1/ T ( B ) . The two marginals satisfy the prefix count because a fixed invertible graph has at most one partner at either endpoint. For each position select a finite set containing the exponent-one alphabet so that the probability of its complement is at most ϵ 2 − q \epsilon2^{-q} ϵ 2 − q at position q q q . A word outside that set at position q q q must have originally had at least q q q runs. The prefix bound therefore shows tightness on the product of these finite sets, at both endpoints. Pass to a nonzero joint weak limit. On each fixed cylinder the finite extensions from shorter words have negligible mass. Hence each marginal is dominated by a constant times the corresponding Gibbs law, first on cylinders and then on Borel sets. The finite set of initial orderings can be handled separately.
In the joint limit the two boundary directions obey the positively oriented graph equality. Indeed, for fixed q q q the short words at either endpoint have vanishing mass, and on the remaining pairs both directions are uniformly approximated by the finite directions, with error tending to zero as q → ∞ q \to\infty q → ∞ . Theorem 13 now gives, almost everywhere, an input prefix p p p , an output word u u u , a permutation matrix P P P , and c > 0 c > 0 c > 0 satisfying
( U − 1 G U ) C B ( p ) = c C B ( u ) P . (U^{-1}GU)C_B(p)=cC_B(u)P. ( U − 1 G U ) C B ( p ) = c C B ( u ) P .
Here p , u p,u p , u include their fixed initial words, restored by multiplying the terminal relation for the continuing graph on the left by C B ( u 0 ) C_B(u_0) C B ( u 0 ) . Since U U U commutes with P P P , this is G C A ( p ) = c C A ( u ) P GC_A(p)=cC_A(u)P G C A ( p ) = c C A ( u ) P . For an input word with prefix p p p and finite continuation t t t , the output label is c C A ( u ) C A ( P ( t ) ) 1 cC_A(u)C_A(P(t))1 c C A ( u ) C A ( P ( t )) 1 , where P ( t ) P(t) P ( t ) permutes the letters of t t t . Both unscaled label vectors are primitive. An integral linear combination of the coordinates of the output before scaling is one, so c c c is integral. The scaled output is primitive as well, giving c = 1 c=1 c = 1 . Decoding gives output word u P ( t ) uP(t) u P ( t ) . Permuting the first d d d coordinates of the output seed by P − 1 P^{-1} P − 1 makes the continuation identical at both ends. Equal aligned seeds produce identical sorted solutions. For a fixed distinct pair of aligned seeds, Proposition 14 gives o ( T ( B ) ) o(T(B)) o ( T ( B )) equal-maximum pairs. A fixed raw prefix is a clopen condition in run coordinates, since it is decided by finitely many run lengths and letters. Thus every terminal input cylinder has zero limiting mass. The countably many terminal cylinders cover almost all the limiting mass by boundary termination, a contradiction.
Summing the graph estimates
Proof of Theorem 2 . It remains to sum over varying graphs. To count the excess, order each collision class and pair each solution with its successor in that class. This gives exactly one fewer pair than there are solutions in the class, and there is at most one occurrence of each solution in each projection. Apply the graph estimates to this chosen collection throughout. Use the coarse partition above. In each ordered pair of parts take the span of the paired labels of the equal-maximum solutions. Both coordinate projections of this span are injective. Otherwise a basis of one projection and an extra independent pair give, by integer Cramer’s rule, a nonzero integral combination with first block zero and second block b ≠ 0 b \ne0 b = 0 . Its coefficients are O ( L d ) O(L^d) O ( L d ) , so ∥ b ∥ = O ( L d + 1 ) \lVert b\rVert= O(L^{d+1}) ∥ b ∥ = O ( L d + 1 ) . Summing the equal-height relations with the same coefficients gives ∣ λ q ( b ) ∣ = O ( δ L d + 1 ) |\lambda_q(b)| = O(\delta L^{d+1}) ∣ λ q ( b ) ∣ = O ( δ L d + 1 ) in the second part q q q , contradicting the excision inequality. The other projection is handled by interchanging the parts.
If the span has dimension below d d d , discard the input labels in its proper projected subspace. The total discarded count is o ( T ( B ) ) o(T(B)) o ( T ( B )) by the strip bound and the subpower bound for the number of parts. Otherwise the span is the graph of a rational invertible matrix determined by d d d actual pairs. In particular there are at most L o ( 1 ) L^{o(1)} L o ( 1 ) graphs, and those with K ( G ) ≥ L a K(G) \ge L^a K ( G ) ≥ L a contain altogether o ( T ( B ) ) o(T(B)) o ( T ( B )) pairs for any fixed a > 0 a > 0 a > 0 .
For the remaining graphs use the band partitions. For a fixed starting band, delete the union of all exceptional vertex sets for the bands from that starting band up to the cutoff. This makes the band estimates apply at both endpoints of every retained pair. The number of matrices with K ( G ) < 2 j + 1 K(G) < 2^{j+1} K ( G ) < 2 j + 1 is O ( 2 ( 2 d 2 + 1 ) j ) O(2^{(2d^2+1)j}) O ( 2 ( 2 d 2 + 1 ) j ) , since D G G D_GG D G G is integral with entries O ( 2 2 j ) O(2^{2j}) O ( 2 2 j ) . Fix H > 2 d 2 + 3 H > 2d^2 + 3 H > 2 d 2 + 3 . Call an incidence between a graph in [ 2 j , 2 j + 1 ) [2^j,2^{j+1}) [ 2 j , 2 j + 1 ) and an ordered pair of parts large if it contains at least 2 − H j T ( B ) 2^{-Hj}T(B) 2 − H j T ( B ) collision pairs. For parts p , q p,q p , q , every such pair satisfies
∣ ( λ p − λ q G ) ( v ) ∣ ≪ δ 2 j ∥ v ∥ . |(\lambda_p-\lambda_qG)(v)| \ll\delta2^j \lVert v\rVert. ∣ ( λ p − λ q G ) ( v ) ∣ ≪ δ 2 j ∥ v ∥ .
The strip estimate for a large incidence gives ∥ λ p − λ q G ∥ ≪ δ 2 ( 1 + H / η ) j \lVert\lambda_p-\lambda_qG\rVert\ll\delta2^{(1+H/\eta)j} ∥ λ p − λ q G ∥ ≪ δ 2 ( 1 + H / η ) j , taking a H < η / 2 aH < \eta/2 a H < η /2 to absorb the finite-size error. If two distinct graphs G 1 , G 2 G_1,G_2 G 1 , G 2 were large for those parts, some column b b b of D G 1 D G 2 ( G 1 − G 2 ) D_{G_1}D_{G_2}(G_1-G_2) D G 1 D G 2 ( G 1 − G 2 ) would be nonzero integral, with norm O ( 2 3 j ) O(2^{3j}) O ( 2 3 j ) and ∣ λ q ( b ) ∣ ≪ δ 2 ( 3 + H / η ) j |\lambda_q(b)| \ll\delta2^{(3+H/\eta)j} ∣ λ q ( b ) ∣ ≪ δ 2 ( 3 + H / η ) j . Choose κ > 3 log 2 \kappa> 3\log2 κ > 3 log 2 and the flatness exponent A A A sufficiently large. The excision inequalities exclude such a column for all sufficiently large j j j .
Thus the large incidences in band j j j contribute O ( P j 2 2 − η j T ( B ) ) O(P_j^2 2^{-\eta j}T(B)) O ( P j 2 2 − η j T ( B )) pairs by the graph estimate. The other incidences contribute
O ( P j 2 2 − ( H − 2 d 2 − 1 ) j T ( B ) ) . O(P_j^2 2^{-(H-2d^2-1)j}T(B)). O ( P j 2 2 − ( H − 2 d 2 − 1 ) j T ( B )) .
Both bounds are summable in j j j after division by T ( B ) T(B) T ( B ) . The band deletions above any fixed starting band also have summable relative cost, up to O ( L − η 0 log L ) O(L^{-\eta_0}\log L) O ( L − η 0 log L ) . Each deleted vertex removes at most two of the chosen pairs.
Below the starting band there are only finitely many rational matrices, so the fixed-graph result applies. For any error tolerance, first choose the initial cusp cutoff, then the coarse deletion budget and the starting band to make the three deletion and tail bounds smaller than that tolerance. Letting B B B tend to infinity gives T ( B ) − D ( B ) = o ( T ( B ) ) T(B)-D(B)=o(T(B)) T ( B ) − D ( B ) = o ( T ( B )) .
Connectivity over prime fields
Theorem 3. Fix an integer n ≥ 4 n \ge4 n ≥ 4 . For all sufficiently large primes p p p , the graph on the solutions of
∑ i = 1 n x i 2 = n ∏ i = 1 n x i in F p n \sum_{i=1}^{n}x_i^2 = n\prod_{i=1}^{n}x_i \quad\text{in } \mathbb{F}_p^n i = 1 ∑ n x i 2 = n i = 1 ∏ n x i in F p n having at most one zero coordinate is connected. The edges are the labelled Vieta moves, which replace x i x_i x i by n ∏ j ≠ i x j − x i n\prod_{j\ne i}x_j-x_i n ∏ j = i x j − x i and leave the other coordinates fixed.
A uniform orbit on cubic sections
For K ∈ F p K \in\mathbb{F}_p K ∈ F p , let M K M_K M K be the cubic surface x 2 + y 2 + z 2 − x y z = K x^2+y^2+z^2-xyz=K x 2 + y 2 + z 2 − x y z = K . We use the group generated by its Vieta involutions and coordinate permutations. A point is called an axis point if at least two of its coordinates vanish. At such a point, a Vieta involution acts by changing the sign of the active coordinate, since the product of the other two coordinates vanishes. Thus the set of axis points is invariant under the entire group. For a trace x ∈ F p x \in\mathbb{F}_p x ∈ F p with x ≠ ± 2 x \ne\pm2 x = ± 2 , define its order to be the multiplicative order of either root of U 2 − x U + 1 U^2-xU+1 U 2 − xU + 1 . The two roots are inverse to each other, and the order divides p − 1 p-1 p − 1 or p + 1 p+1 p + 1 . The traces ± 2 \pm2 ± 2 are called parabolic and are assigned order p p p .
Lemma 4. Fix 0 < δ < 1 / 4 0<\delta<1/4 0 < δ < 1/4 . For all sufficiently large primes p p p , uniformly in K ≠ 4 K\ne4 K = 4 , one orbit on M K ( F p ) M_K(\mathbb{F}_p) M K ( F p ) contains every nonaxis point with a coordinate of order at least p δ p^\delta p δ . Its complement has at most 6 + 2 ( p δ + 1 ) 4 6+2(p^\delta+1)^4 6 + 2 ( p δ + 1 ) 4 points.
Proof. Fix x ≠ ± 2 x\ne\pm2 x = ± 2 and choose λ \lambda λ with x = λ + λ − 1 x=\lambda+\lambda^{-1} x = λ + λ − 1 . The linear coordinates
y = a + b , z = λ a + λ − 1 b y=a+b,\qquad z=\lambda a+\lambda^{-1}b y = a + b , z = λa + λ − 1 b
are unique, and the cubic equation becomes a b = ( x 2 − K ) / ( x 2 − 4 ) ab=(x^2-K)/(x^2-4) ab = ( x 2 − K ) / ( x 2 − 4 ) . The rotation ( y , z ) ↦ ( z , x z − y ) (y,z)\mapsto(z,xz-y) ( y , z ) ↦ ( z , x z − y ) is a Vieta move followed or preceded by a transposition, and sends ( a , b ) (a,b) ( a , b ) to ( λ a , λ − 1 b ) (\lambda a,\lambda^{-1}b) ( λa , λ − 1 b ) . At a nonaxis point at least one of a , b a,b a , b is nonzero. Therefore the m m m th iterate fixes the point exactly when λ m = 1 \lambda^m=1 λ m = 1 , and the orbit has length r = ord ( λ ) r=\operatorname{ord}(\lambda) r = ord ( λ ) . The values of y y y in this orbit are a t + b / t at+b/t a t + b / t for t ∈ ⟨ λ ⟩ t\in\langle\lambda\rangle t ∈ ⟨ λ ⟩ . If λ \lambda λ is split, a , b a,b a , b belong to F p \mathbb{F}_p F p and the ambient group of parameters t t t is F p × \mathbb{F}_p^\times F p × . Otherwise b = a p b=a^p b = a p and the ambient group is the group of norm-one elements of F p 2 × \mathbb{F}_{p^2}^\times F p 2 × . We view the latter as the rational points of the norm-one torus over F p \mathbb{F}_p F p . In its split coordinates the descent exchanges a a a and b b b and inverts t t t , so a t + b / t at+b/t a t + b / t is a map over F p \mathbb{F}_p F p .
To compare orders on rotation orbits, apply Corvaja–Zannier’s bound [14 Corollary 2] to
a t + b / t = s + s − 1 . at+b/t=s+s^{-1}. a t + b / t = s + s − 1 .
In the two-dimensional torus this curve is geometrically irreducible and is not a translate of a subtorus. Indeed, when a b ≠ 0 ab\ne0 ab = 0 the discriminant in s s s , after multiplication by t 2 t^2 t 2 , is a 2 t 4 + ( 2 a b − 4 ) t 2 + b 2 a^2t^4+(2ab-4)t^2+b^2 a 2 t 4 + ( 2 ab − 4 ) t 2 + b 2 . Comparing coefficients of a polynomial square shows that it can be a square only if a b = 1 ab=1 ab = 1 , which would imply K = 4 K=4 K = 4 . If exactly one of a , b a,b a , b vanishes, the equation is linear in t t t or t − 1 t^{-1} t − 1 after writing it as a Laurent polynomial. In all cases the irreducible Laurent equation has at least three monomials. Its bidegree in the two projective coordinates is at most ( 2 , 2 ) (2,2) ( 2 , 2 ) , so the normalization has genus at most one and at most eight points where a coordinate has a zero or pole. Both coordinate maps have degree at most two and are separable in odd characteristic. Thus the bound for pairs with t r = s m = 1 t^r=s^m=1 t r = s m = 1 is
O ( ( r m ) 1 / 3 + r m / p ) . O\left((rm)^{1/3}+rm/p\right). O ( ( r m ) 1/3 + r m / p ) .
with an absolute constant. The estimate uses characteristic p p p and applies to the curve over the algebraic closure, including the nonsplit case.
Suppose the largest coordinate order of a point is r ∈ [ p δ , p 3 / 4 ] r\in[p^\delta,p^{3/4}] r ∈ [ p δ , p 3/4 ] . Use that coordinate for x x x . For each m ≤ r m\le r m ≤ r dividing p − 1 p-1 p − 1 or p + 1 p+1 p + 1 , one has r m / p ≤ ( r m ) 1 / 3 rm/p\le(rm)^{1/3} r m / p ≤ ( r m ) 1/3 . Hence the number of rotation parameters whose output y y y is nonparabolic and has order at most r r r is
O ( r 2 / 3 ( τ ( p − 1 ) + τ ( p + 1 ) ) ) = o ( r ) , O\left(r^{2/3}\bigl(\tau(p-1)+\tau(p+1)\bigr)\right)=o(r), O ( r 2/3 ( τ ( p − 1 ) + τ ( p + 1 ) ) ) = o ( r ) ,
where τ \tau τ counts positive divisors and τ ( N ) = N o ( 1 ) \tau(N)=N^{o(1)} τ ( N ) = N o ( 1 ) . The estimate is uniform because r ≥ p δ r\ge p^\delta r ≥ p δ . A rotation therefore produces a coordinate of order larger than the previous maximum. Iteration reaches a parabolic coordinate or an order at least p 3 / 4 p^{3/4} p 3/4 .
Call a trace regular primitive if it has the form s + s − 1 s+s^{-1} s + s − 1 with s s s a generator of F p × \mathbb{F}_p^\times F p × and its square differs from K K K . We show that the large-order points can reach such a trace. First assume a b ≠ 0 ab\ne0 ab = 0 . Write e e e for the index of ⟨ λ ⟩ \langle\lambda\rangle ⟨ λ ⟩ in its ambient group, and let d d d divide p − 1 p-1 p − 1 . Consider the curve
a u e + b u − e = v d + v − d , au^e+bu^{-e}=v^d+v^{-d}, a u e + b u − e = v d + v − d ,
with u u u in the same torus as t t t and v v v in the split torus. Over the algebraic closure the two maps to the common value are tame Galois covers of degrees 2 e 2e 2 e and 2 d 2d 2 d . The first has deck transformations generated by u ↦ ζ u u \mapsto\zeta u u ↦ ζ u for ζ e = 1 \zeta^e = 1 ζ e = 1 and u ↦ β / u u \mapsto\beta/u u ↦ β / u for β e = b / a \beta^e = b/a β e = b / a . Its two finite branch values are ± 2 a b \pm2\sqrt{ab} ± 2 ab , with inertia order two, and its inertia order at infinity is e e e . The second has finite branch values ± 2 \pm2 ± 2 and inertia order d d d at infinity. The finite branch sets are disjoint since a b ≠ 1 ab \ne1 ab = 1 . The intersection of the two Galois function fields can ramify only at infinity and is tame. A degree q > 1 q>1 q > 1 extension with that property would have 2 g − 2 ≤ − 2 q + ( q − 1 ) < − 2 2g-2 \le-2q+(q-1)<-2 2 g − 2 ≤ − 2 q + ( q − 1 ) < − 2 by Riemann–Hurwitz. The fields are therefore linearly disjoint.
The composite cover has degree 4 e d 4ed 4 e d and four finite branch values with inertia order two. The tame inertia order at infinity is lcm ( e , d ) \operatorname{lcm}(e,d) lcm ( e , d ) , since the local extensions over an algebraically closed residue field are tame cyclic extensions. Riemann–Hurwitz gives genus 2 e d − 2 gcd ( e , d ) + 1 2ed-2\gcd(e,d)+1 2 e d − 2 g cd( e , d ) + 1 . The affine fiber product is smooth because above any finite value at least one of the two covering maps is unramified. Locally the fiber product is then étale over the source of the other map. Its projective normalization adds at most 4 e d 4ed 4 e d points, so Hasse–Weil gives p + O ( e d p ) p+O(ed\sqrt{p}) p + O ( e d p ) rational points on the affine curve. The maps u ↦ u e u\mapsto u^e u ↦ u e and v ↦ v d v\mapsto v^d v ↦ v d on rational points have fibers of sizes e e e and d d d and images ⟨ λ ⟩ \langle\lambda\rangle ⟨ λ ⟩ and ( F p × ) d (\mathbb{F}_p^\times)^d ( F p × ) d . Thus the number of pairs ( t , s ) (t,s) ( t , s ) on the rotation curve with s ∈ ( F p × ) d s\in(\mathbb{F}_p^\times)^d s ∈ ( F p × ) d is p / ( e d ) + O ( p ) p/(ed)+O(\sqrt{p}) p / ( e d ) + O ( p ) .
For a cyclic group of order p − 1 p-1 p − 1 , the generator indicator at s s s is
∑ d ∣ p − 1 s ∈ ( F p × ) d μ ( d ) , \sum_{\substack{d\mid p-1\\s\in(\mathbb{F}_p^\times)^d}}\mu(d), d ∣ p − 1 s ∈ ( F p × ) d ∑ μ ( d ) ,
where μ \mu μ is the Möbius function. Consequently the number of pairs with s s s primitive is
p φ ( p − 1 ) e ( p − 1 ) + O ( τ ( p − 1 ) p ) , \frac{p\varphi(p-1)}{e(p-1)}+O(\tau(p-1)\sqrt{p}), e ( p − 1 ) pφ ( p − 1 ) + O ( τ ( p − 1 ) p ) ,
where φ \varphi φ is Euler’s totient. As p / e ≍ r p/e\asymp r p / e ≍ r and φ ( N ) / N ≥ 1 / τ ( N ) \varphi(N)/N\ge1/\tau(N) φ ( N ) / N ≥ 1/ τ ( N ) , this count tends to infinity whenever r ≥ p 5 / 8 r\ge p^{5/8} r ≥ p 5/8 . Each forbidden value y 2 = K y^2=K y 2 = K accounts for at most four pairs, since each of the two maps t ↦ a t + b / t t\mapsto at+b/t t ↦ a t + b / t and s ↦ s + s − 1 s\mapsto s+s^{-1} s ↦ s + s − 1 has degree at most two.
When a b = 0 ab=0 ab = 0 and r ≥ p 3 / 4 r\ge p^{3/4} r ≥ p 3/4 , the rotation gives r r r distinct output traces, since exactly one of a , b a,b a , b is nonzero. The number of nonparabolic traces of order at most p 5 / 8 p^{5/8} p 5/8 is at most p 5 / 8 ( τ ( p − 1 ) + τ ( p + 1 ) ) p^{5/8}(\tau(p-1)+\tau(p+1)) p 5/8 ( τ ( p − 1 ) + τ ( p + 1 )) . One can therefore reach a nonparabolic trace of order greater than p 5 / 8 p^{5/8} p 5/8 whose square differs from K K K , and then apply the preceding count on its fiber. If x = ± 2 x=\pm2 x = ± 2 , the fiber satisfies ( y ∓ z ) 2 = K − 4 (y\mp z)^2=K-4 ( y ∓ z ) 2 = K − 4 . Each rational point belongs to a line y ∓ z = c y\mp z=c y ∓ z = c with c ≠ 0 c\ne0 c = 0 and the square of the rotation preserves that line. Its first coordinate is x z − y xz-y x z − y , equal to y − 2 c y-2c y − 2 c for either x = 2 x=2 x = 2 or x = − 2 x=-2 x = − 2 . Its orbit gives every value of y y y , including regular primitive traces for large p p p .
It remains to connect the regular primitive fibers. For each such x x x , its rotation is transitive on the fiber, since a b = ( x 2 − K ) / ( x 2 − 4 ) ab=(x^2-K)/(x^2-4) ab = ( x 2 − K ) / ( x 2 − 4 ) is nonzero and the split rotation group is all of F p × \mathbb{F}_p^\times F p × . Take regular primitive x , x ′ x,x' x , x ′ with x 2 ≠ ( x ′ ) 2 x^2\ne(x')^2 x 2 = ( x ′ ) 2 , and let κ , κ ′ \kappa,\kappa' κ , κ ′ be their respective values of ( x 2 − K ) / ( x 2 − 4 ) (x^2-K)/(x^2-4) ( x 2 − K ) / ( x 2 − 4 ) . They are distinct since K ≠ 4 K\ne4 K = 4 , and neither is 0 0 0 or 1 1 1 . The fibers admit a common coordinate y y y if the equations v 2 = y 2 − 4 κ v^2=y^2-4\kappa v 2 = y 2 − 4 κ and w 2 = y 2 − 4 κ ′ w^2=y^2-4\kappa' w 2 = y 2 − 4 κ ′ both have rational solutions. Indeed, on the first split fiber y = a + b y=a+b y = a + b and a b = κ ab=\kappa ab = κ , so a , b a,b a , b are roots of T 2 − y T + κ T^2-yT+\kappa T 2 − y T + κ . They exist over F p \mathbb{F}_p F p precisely when y 2 − 4 κ y^2-4\kappa y 2 − 4 κ is a square, with zero allowed. The same argument applies to κ ′ \kappa' κ ′ . Impose also y = s d + s − d y=s^d+s^{-d} y = s d + s − d for d ∣ p − 1 d\mid p-1 d ∣ p − 1 . These three covers of the y y y -line are Galois and have pairwise disjoint finite branch sets. The same argument at infinity, applied first to the two quadratic covers and then to their composite and the third cover, gives geometric irreducibility. The degree is 8 d 8d 8 d , with six finite inertia orders two and infinity inertia order d d d . The genus is 8 d − 3 8d-3 8 d − 3 . Hasse–Weil gives p + O ( d p ) p+O(d\sqrt{p}) p + O ( d p ) rational points on the affine fiber product. Dividing by d d d and applying the generator indicator gives
p φ ( p − 1 ) p − 1 + O ( τ ( p − 1 ) p ) \frac{p\varphi(p-1)}{p-1}+O(\tau(p-1)\sqrt{p}) p − 1 pφ ( p − 1 ) + O ( τ ( p − 1 ) p )
solutions with y = s + s − 1 y=s+s^{-1} y = s + s − 1 for a generator s s s . The count tends to infinity, so we can exclude y 2 = K y^2=K y 2 = K , whose values yield at most eight solutions each after the power map. The two fibers connect through this regular primitive y y y -fiber, by permuting coordinates as needed. If x 2 = ( x ′ ) 2 x^2=(x')^2 x 2 = ( x ′ ) 2 , insert a third regular primitive trace with a different square. There are φ ( p − 1 ) / 2 \varphi(p-1)/2 φ ( p − 1 ) /2 primitive split traces for large p p p , so the bounded exclusions permit this choice.
The estimates are uniform in K ≠ 4 K\ne4 K = 4 . Axis points form an invariant set of size at most six. Outside the orbit just found, every nonaxis point has three coordinates of order less than p δ p^\delta p δ . There are at most ( p δ + 1 ) 2 (p^\delta+1)^2 ( p δ + 1 ) 2 such traces, by summing the number of roots of U m = 1 U^m=1 U m = 1 over positive m < p δ m<p^\delta m < p δ . After two coordinates are fixed, the third satisfies a monic quadratic. This gives the stated bound. □
Gluing cubic sections
Proof of Theorem 3 . Write X ∘ X^\circ X ∘ for the vertex set in the theorem, H H H for its group of Vieta involutions R i R_i R i , and G G G for the group obtained by adjoining coordinate permutations. Each R i R_i R i preserves X ∘ X^\circ X ∘ : at a point with a zero in another coordinate it acts on x i x_i x i by negation, and elsewhere at most the updated coordinate can become zero.
First, extend Martin’s weight argument [17 ] to all n n n coordinates. For x ∈ X ∘ x\in X^\circ x ∈ X ∘ and 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n define
f i ( x ) = { x i n ∏ j ≠ i x j , ∏ j ≠ i x j ≠ 0 , 1 2 , ∏ j ≠ i x j = 0. f_i(x)=
\begin{cases}
\dfrac{x_i}{n\prod_{j\ne i}x_j}, & \prod_{j\ne i}x_j\ne0,\\
\dfrac{1}{2}, & \prod_{j\ne i}x_j=0.
\end{cases} f i ( x ) = ⎩ ⎨ ⎧ n ∏ j = i x j x i , 2 1 , ∏ j = i x j = 0 , ∏ j = i x j = 0.
Here and throughout take p p p odd and p ∤ n p\nmid n p ∤ n . Then f i ( x ) + f i ( R i x ) = 1 f_i(x)+f_i(R_i x)=1 f i ( x ) + f i ( R i x ) = 1 . In the nonzero-denominator case this follows from the sum of the two Vieta roots, and in the zero-denominator case both terms are 1 / 2 1/2 1/2 . For a nonempty H H H -invariant subset C C C of X ∘ X^\circ X ∘ , summation over C C C gives ∑ x ∈ C f i ( x ) = ∣ C ∣ / 2 \sum_{x\in C}f_i(x)=|C|/2 ∑ x ∈ C f i ( x ) = ∣ C ∣/2 in F p \mathbb{F}_p F p . At a point with no zero coordinate ∑ i f i ( x ) = 1 \sum_i f_i(x)=1 ∑ i f i ( x ) = 1 by the defining equation, and at a point with one zero coordinate it is ( n − 1 ) / 2 (n-1)/2 ( n − 1 ) /2 . If T T T and Z Z Z count the two kinds of points in C C C , respectively, it follows that p ∣ ( n − 2 ) T + Z p\mid(n-2)T+Z p ∣ ( n − 2 ) T + Z . This is a positive integer at most ( n − 2 ) ∣ C ∣ (n-2)|C| ( n − 2 ) ∣ C ∣ , and therefore
∣ C ∣ ≥ p / ( n − 2 ) . |C|\ge p/(n-2). ∣ C ∣ ≥ p / ( n − 2 ) .
Fix δ = 1 / ( 8 n ) \delta=1/(8n) δ = 1/ ( 8 n ) and set B = 6 + 2 ( p δ + 1 ) 4 B=6+2(p^\delta+1)^4 B = 6 + 2 ( p δ + 1 ) 4 , the bound in Lemma 4 . For a fixed triple of active coordinates, freeze all others at nonzero values. Multiplying the three active coordinates by c = n ∏ x j c=n\prod x_j c = n ∏ x j , where the product is over frozen coordinates, identifies the slice with M K M_K M K for K = − c 2 ∑ x j 2 K=-c^2\sum x_j^2 K = − c 2 ∑ x j 2 , with the same frozen indices in the sum. The map conjugates each active Vieta involution and commutes with active coordinate permutations. If K ≠ 4 K\ne4 K = 4 , the orbit from Lemma 4 lies in X ∘ X^\circ X ∘ because the cubic axis points form an invariant set and the orbit contains a nonaxis point.
To compare slices in a block of four coordinates, freeze the rest at nonzero values. The resulting equation has the form
z 1 2 + z 2 2 + z 3 2 + z 4 2 − A z 1 z 2 z 3 z 4 = b . z_1^2+z_2^2+z_3^2+z_4^2-Az_1z_2z_3z_4=b. z 1 2 + z 2 2 + z 3 2 + z 4 2 − A z 1 z 2 z 3 z 4 = b .
where A A A is n n n times the product of the fixed coordinates and b b b is minus the sum of their squares. The empty product and sum are 1 and 0. On fixing two distinct coordinates at values s , t ≠ 0 s,t\ne0 s , t = 0 , the other two, u , v u,v u , v , satisfy
( 2 u − A s t v ) 2 − ( ( A s t ) 2 − 4 ) v 2 = 4 ( b − s 2 − t 2 ) . (2u-Astv)^2-\bigl((Ast)^2-4\bigr)v^2=4(b-s^2-t^2). ( 2 u − A s t v ) 2 − ( ( A s t ) 2 − 4 ) v 2 = 4 ( b − s 2 − t 2 ) .
If both b − s 2 − t 2 b-s^2-t^2 b − s 2 − t 2 and ( A s t ) 2 − 4 (Ast)^2-4 ( A s t ) 2 − 4 are nonzero, the conic has p − 1 p-1 p − 1 or p + 1 p+1 p + 1 points according as ( A s t ) 2 − 4 (Ast)^2-4 ( A s t ) 2 − 4 is a square or a nonsquare. This follows from the product equation in the split case and from the norm map of F p 2 \mathbb{F}_{p^2} F p 2 in the nonsplit case. Removing at most four points with u v = 0 uv=0 uv = 0 and at most 2 B 2B 2 B points outside the two cubic orbits still leaves a point for large p p p . Thus the two orbits lie in the same G G G -orbit whenever both cubic slices are non-Cayley, meaning their levels differ from 4, and the conic meets these conditions.
For any two non-Cayley cubic slices in this four-coordinate block, choose a coordinate fixed by neither of them and freeze it at a nonzero value w w w . The new slice is non-Cayley unless A 2 w 2 ( b − w 2 ) = 4 A^{2}w^{2}(b-w^{2})=4 A 2 w 2 ( b − w 2 ) = 4 . If one original slice freezes a value s s s , the conditions on its conic with the new slice exclude the roots of ( A s w ) 2 − 4 (Asw)^{2}-4 ( A s w ) 2 − 4 and b − s 2 − w 2 b-s^{2}-w^{2} b − s 2 − w 2 . The second original slice excludes at most four further values in the same way. These exclusions are bounded independently of p p p , so the third slice connects the first two through the conic intersections.
For a fixed active triple, admissible frozen vectors are the elements of ( F p × ) n − 3 (\mathbb{F}_{p}^{\times})^{n-3} ( F p × ) n − 3 with level K ≠ 4 K\ne4 K = 4 . With all other entries fixed, the equation
n 2 ( ∏ j x j ) 2 ∑ j x j 2 + 4 = 0 n^{2}\left(\prod_{j}x_{j}\right)^{2}\sum_{j}x_{j}^{2}+4=0 n 2 ( j ∏ x j ) 2 j ∑ x j 2 + 4 = 0
for a forbidden vector is a quartic in the remaining entry with nonzero leading coefficient. Given two admissible vectors, choose a uniformly random intermediate vector in ( F p × ) n − 3 (\mathbb{F}_{p}^{\times})^{n-3} ( F p × ) n − 3 . Replace the entries one at a time to pass from the first vector to the intermediate vector and then to the second. Each state other than the endpoints contains at least one independent uniformly random entry of the intermediate vector, so it is inadmissible with probability at most 4 / ( p − 1 ) 4/(p-1) 4/ ( p − 1 ) . There are at most 2 ( n − 3 ) 2(n-3) 2 ( n − 3 ) such states. For large p p p there is a choice with no inadmissible state. Consecutive slices lie in a common four-coordinate block and hence their cubic orbits belong to the same G G G -orbit.
The all-one frozen vector has level − n 2 ( n − 3 ) ≠ 4 -n^{2}(n-3)\ne4 − n 2 ( n − 3 ) = 4 for sufficiently large p p p , since n 2 ( n − 3 ) + 4 = ( n − 2 ) 2 ( n + 1 ) n^{2}(n-3)+4=(n-2)^{2}(n+1) n 2 ( n − 3 ) + 4 = ( n − 2 ) 2 ( n + 1 ) . Permutations identify these reference slices for all choices of active triple. Therefore there is a single G G G -orbit O \mathcal{O} O containing the cubic orbits for all non-Cayley slices.
For an all-nonzero point x ∈ X ∘ ∖ O x\in X^{\circ}\setminus\mathcal{O} x ∈ X ∘ ∖ O , define the product trace M i j = n ∏ ℓ ≠ i , j x ℓ M_{ij}=n\prod_{\ell\ne i,j}x_{\ell} M ij = n ∏ ℓ = i , j x ℓ for distinct i , j i,j i , j . For any k ∉ { i , j } k\notin\{i,j\} k ∈ / { i , j } this is the rescaled k k k th coordinate of the active triple { i , j , k } \{i,j,k\} { i , j , k } . If its order is at least p δ p^{\delta} p δ , then every one of these triples has level 4 4 4 , by Lemma 4. In terms of the frozen coordinates these conditions say
M i j 2 ∑ ℓ ≠ i , j x ℓ 2 = ( M i j 2 − 4 ) x k 2 ( k ≠ i , j ) . M_{ij}^{2}\sum_{\ell\ne i,j}x_{\ell}^{2}=(M_{ij}^{2}-4)x_{k}^{2}\qquad(k\ne i,j). M ij 2 ℓ = i , j ∑ x ℓ 2 = ( M ij 2 − 4 ) x k 2 ( k = i , j ) .
If M i j 2 ≠ 4 M_{ij}^{2}\ne4 M ij 2 = 4 , all the squares x k 2 x_{k}^{2} x k 2 on the right are equal and nonzero, giving ( n − 3 ) M i j 2 = − 4 (n-3)M_{ij}^{2}=-4 ( n − 3 ) M ij 2 = − 4 . Thus each M i j M_{ij} M ij belongs to a set of at most ( p δ + 1 ) 2 + 4 (p^{\delta}+1)^{2}+4 ( p δ + 1 ) 2 + 4 traces, consisting of low orders and roots of the two exceptional quadratic equations.
The n n n values M 12 , M 13 , M 23 , M 24 , … , M 2 n M_{12},M_{13},M_{23},M_{24},\ldots,M_{2n} M 12 , M 13 , M 23 , M 24 , … , M 2 n determine all coordinate ratios to x 1 x_{1} x 1 , by x 2 / x 1 = M 13 / M 23 x_{2}/x_{1}=M_{13}/M_{23} x 2 / x 1 = M 13 / M 23 and x j / x 1 = M 12 / M 2 j x_{j}/x_{1}=M_{12}/M_{2j} x j / x 1 = M 12 / M 2 j for 3 ≤ j ≤ n 3\le j\le n 3 ≤ j ≤ n . Substitution into M 12 = n ∏ j = 3 n x j M_{12}=n\prod_{j=3}^{n}x_{j} M 12 = n ∏ j = 3 n x j fixes x 1 n − 2 x_{1}^{n-2} x 1 n − 2 , so at most n − 2 n-2 n − 2 points realize any given list of these traces. The all-nonzero part of the complement has size at most ( n − 2 ) ( ( p δ + 1 ) 2 + 4 ) n (n-2)((p^{\delta}+1)^{2}+4)^{n} ( n − 2 ) (( p δ + 1 ) 2 + 4 ) n . For each fixed i i i , the involution R i R_{i} R i injects the part with x i = 0 x_{i}=0 x i = 0 into the all-nonzero part of the complement. The entire complement thus has size O n ( p n δ / 4 ) O_{n}(p^{n\delta/4}) O n ( p n δ /4 ) . It is H H H -invariant, so the weight bound forces it to be empty for sufficiently large p p p .
Finally, coordinate permutations normalize H H H because conjugation by σ \sigma σ sends R i R_{i} R i to R σ ( i ) R_{\sigma(i)} R σ ( i ) . The all-one vector belongs to X ∘ X^{\circ} X ∘ and is fixed by every permutation. Its G G G -orbit is consequently its H H H -orbit. Since the former is all of X ∘ X^{\circ} X ∘ , the labelled graph is connected.
Proposition 5. For every integer n ≥ 4 n\ge4 n ≥ 4 and prime p ≡ 1 ( m o d 4 ) p\equiv1\pmod4 p ≡ 1 ( mod 4 ) , the pure Vieta graph on all nonzero solutions of
∑ i = 1 n x i 2 = n ∏ i = 1 n x i in F p n \sum_{i=1}^{n}x_{i}^{2}=n\prod_{i=1}^{n}x_{i}\quad\text{in }\mathbb{F}_{p}^{n} i = 1 ∑ n x i 2 = n i = 1 ∏ n x i in F p n is disconnected. Here a nonzero solution is any solution other than the zero vector.
Proof. Since 4 ∣ p − 1 4\mid p-1 4 ∣ p − 1 , the cyclic group F p × \mathbb{F}_{p}^{\times} F p × contains an element ι \iota ι of order four. Its square is − 1 -1 − 1 , so ( 1 , ι , 0 , … , 0 ) (1,\iota,0,\ldots,0) ( 1 , ι , 0 , … , 0 ) is a nonzero solution. If a solution has at least two zero coordinates, then ∏ j ≠ i x j = 0 \prod_{j\ne i} x_j=0 ∏ j = i x j = 0 for every i i i . Each Vieta move therefore only changes a coordinate’s sign and preserves the set of zero coordinates. The all-one solution lies outside the orbit of ( 1 , ι , 0 , … , 0 ) (1,\iota,0,\ldots,0) ( 1 , ι , 0 , … , 0 ) . □ \square □
Counting and arithmetic estimates
Fix integers n ≥ 4 n\ge4 n ≥ 4 and k ≥ 0 k\ge0 k ≥ 0 , and put d = n − 1 d=n-1 d = n − 1 . Use the ascending words and matrices A i = I + ( 1 − e i ) e i T A_i=I+(1-e_i)e_i^{\mathsf T} A i = I + ( 1 − e i ) e i T of the density section. For a finite word w = i 1 ⋯ i m w=i_1\cdots i_m w = i 1 ⋯ i m , set C ( w ) = A i 1 ⋯ A i m C(w)=A_{i_1}\cdots A_{i_m} C ( w ) = A i 1 ⋯ A i m and denote its scalar size by N ( w ) = 1 T C ( w ) 1 N(w)=\mathbf{1}^{\mathsf T}C(w)\mathbf{1} N ( w ) = 1 T C ( w ) 1 . All norms on vectors below are Euclidean unless the sum of coordinates is explicitly used.
Lemma 6. Let x ( w ) x(w) x ( w ) be the solution obtained by applying the ascending word w w w to ( 1 , … , 1 , n + k − 1 ) (1,\ldots,1,n+k-1) ( 1 , … , 1 , n + k − 1 ) . Then
log ( n + k − 1 ) n − 2 ( N ( w ) − 1 ) ≤ log x n ( w ) ≤ log ( n ( k + 1 ) ) n − 2 ( N ( w ) − 1 ) . \frac{\log(n+k-1)}{n-2}(N(w)-1)\le\log x_n(w)\le\frac{\log(n(k+1))}{n-2}(N(w)-1). n − 2 log ( n + k − 1 ) ( N ( w ) − 1 ) ≤ log x n ( w ) ≤ n − 2 log ( n ( k + 1 )) ( N ( w ) − 1 ) . Each sorted solution other than the all-one solution occurs from at least one and at most d ! d! d ! ascending words.
Proof. In an ascending move let P P P be the product of the retained coordinates and let x i x_i x i be the replaced coordinate. The new entry is
( n ( k + 1 ) − k ∑ j ≠ i x j − 1 ) P − x i . \left(n(k+1)-k\sum_{j\ne i}x_j^{-1}\right)P-x_i. n ( k + 1 ) − k j = i ∑ x j − 1 P − x i .
The sum is at most n − 1 n-1 n − 1 , and x i ≤ x n ≤ P x_i\le x_n\le P x i ≤ x n ≤ P , so the new entry is between ( n + k − 1 ) P (n+k-1)P ( n + k − 1 ) P and n ( k + 1 ) P n(k+1)P n ( k + 1 ) P . Thus at each forward vertex log x n \log x_n log x n lies between the sum of the first d d d logarithms plus log ( n + k − 1 ) \log(n+k-1) log ( n + k − 1 ) and the same sum plus log ( n ( k + 1 ) ) \log(n(k+1)) log ( n ( k + 1 )) . The inequalities hold also at the starting seed.
For the lower bound add log ( n + k − 1 ) / ( n − 2 ) \log(n+k-1)/(n-2) log ( n + k − 1 ) / ( n − 2 ) to each of the first d d d logarithms. In move i i i , the shifted entry in slot i i i becomes the shifted old maximum, which is at least the sum of the old shifted entries. The other slots stay fixed. Hence the new column is at least A i T A_i^{\mathsf T} A i T times the old column, coordinate by coordinate. All matrix entries are nonnegative, so the word bounds that column below by C ( w ) T 1 C(w)^{\mathsf T}\mathbf{1} C ( w ) T 1 times the initial shift. The shifted maximum is at least the sum of the shifted parent entries. This gives the lower bound. With the upper shift the same inequalities reverse, giving the upper bound. Descent determines the chain of sorted parents. Every forward step creates a new strict maximum, so the only repetitions of entries come from unused initial ones. Choosing among these equal entries multiplies the word count by at most d ( d − 1 ) ⋯ 1 d(d-1)\cdots1 d ( d − 1 ) ⋯ 1 . □ \square □
Accelerated words and height counts
An accelerated letter consists of a nonlast slot of the current ordered parent column and a positive run length a a a . At each run, the chosen slot is moved to the end of the ordering. The ordered state is w = ( w 1 , … , w d ) w=(w_1,\ldots,w_d) w = ( w 1 , … , w d ) , with 0 ≤ w 1 ≤ ⋯ ≤ w d 0\le w_1\le\cdots\le w_d 0 ≤ w 1 ≤ ⋯ ≤ w d and ∑ i w i = 1 \sum_i w_i=1 ∑ i w i = 1 . Keep a permutation of the fixed parent labels as part of the state to recover the corresponding index i i i of A i A_i A i . For an accelerated letter choosing position j < d j<d j < d , its state map first replaces w j w_j w j by w j + a ( 1 − w j ) w_j+a(1-w_j) w j + a ( 1 − w j ) , moves it to the end, and divides all entries by 1 + a ( 1 − w j ) 1+a(1-w_j) 1 + a ( 1 − w j ) . Its roof is τ = log ( 1 + a ( 1 − w j ) ) \tau=\log(1+a(1-w_j)) τ = log ( 1 + a ( 1 − w j )) , the logarithm of that factor. A word’s total roof S m S_m S m is the sum of the roofs along its first m m m successive state updates, with S 0 = 0 S_0=0 S 0 = 0 .
Gamburd, Magee, and Ronan [15 Theorem 39, Proposition 43, Proposition 45 and Section 4.3] give β > 1 \beta>1 β > 1 , a positive C 1 C^1 C 1 eigenfunction h h h of the roof transfer operator at eigenvalue one, and constants D > 0 D>0 D > 0 and 0 < ρ < 1 0<\rho<1 0 < ρ < 1 such that every composition of m m m normalized maps has Lipschitz constant at most D ρ m D\rho^m D ρ m . The probability of choosing letter a , j a,j a , j from state w w w is
e − β τ ( w ) h ( f ( w ) ) h ( w ) , e^{-\beta\tau(w)}\frac{h(f(w))}{h(w)}, e − β τ ( w ) h ( w ) h ( f ( w )) ,
where f f f is its normalized map. The eigenfunction equation gives total probability one. Compactness gives positive upper and lower bounds on h h h . Since w j ≤ 1 / 2 w_j \le1/2 w j ≤ 1/2 , every roof is at least log ( 3 / 2 ) \log(3/2) log ( 3/2 ) , and the conditional expectation of e ϰ t e^{\varkappa t} e ϰ t is bounded uniformly for 0 < ϰ < β − 1 0 < \varkappa< \beta- 1 0 < ϰ < β − 1 , by comparison with ∑ a ≥ 1 a − β + ϰ \sum_{a\ge1}a^{-\beta+\varkappa} ∑ a ≥ 1 a − β + ϰ .
Lemma 7. The number of accelerated words of total roof at most t t t lies between c e β t ce^{\beta t} c e β t and C e β t Ce^{\beta t} C e β t for t ≥ 0 t \ge0 t ≥ 0 , uniformly in the initial state. If a set of length-q q q prefixes has probability at most ε \varepsilon ε , the number of words of total roof at most t t t beginning with such prefixes is at most C ε e β t C\varepsilon e^{\beta t} C ε e β t , with C C C independent of q q q . Words of run length less than q q q number at most C s e s t K s q C_s e^{st}K_s^q C s e s t K s q for fixed 1 < s < β 1 < s < \beta 1 < s < β and suitable K s > 1 K_s > 1 K s > 1 .
Proof. The probability of a word of length m m m telescopes to e − β S m h ( w m ) / h ( w 0 ) e^{-\beta S_m}h(w_m)/h(w_0) e − β S m h ( w m ) / h ( w 0 ) . Thus the normalized count e − β t e^{-\beta t} e − β t times the number of words is the expected sum over m m m with S m ≤ t S_m \le t S m ≤ t of
e − β ( t − S m ) h ( w 0 ) / h ( w m ) . e^{-\beta(t-S_m)}h(w_0)/h(w_m). e − β ( t − S m ) h ( w 0 ) / h ( w m ) .
For any b > 0 b>0 b > 0 , the sum of e − b ( t − S m ) e^{-b(t-S_m)} e − b ( t − S m ) over these times is bounded by ( 1 − e − b log ( 3 / 2 ) ) − 1 (1-e^{-b\log(3/2)})^{-1} ( 1 − e − b l o g ( 3/2 ) ) − 1 on every path. This proves the upper bound. For the lower bound cross t − M t-M t − M at the first time J J J with S J ≥ t − M S_J \ge t-M S J ≥ t − M , where M M M is fixed and t ≥ M t \ge M t ≥ M . A crossing from time j j j with S j < t − M S_j < t-M S j < t − M overshoots t t t only if the next increment exceeds M + ( t − M − S j ) M+(t-M-S_j) M + ( t − M − S j ) . The conditional exponential moment and the preceding geometric bound show that P ( S J > t ) ≤ C e − ϰ M \mathbb{P}(S_J>t) \le Ce^{-\varkappa M} P ( S J > t ) ≤ C e − ϰ M . Choose M M M with this upper bound at most 1 / 2 1/2 1/2 . The contribution at J J J on S J ≤ t S_J \le t S J ≤ t is at least a fixed positive constant. For t < M t<M t < M the empty word suffices. To count words in a prefix event, sum the uniform upper tail count after each eligible prefix p p p , weighted by e − β S ( p ) e^{-\beta S(p)} e − β S ( p ) . The cylinder probability formula bounds that sum of weights by C ε C\varepsilon C ε . Finally the sum of e − s τ e^{-s\tau} e − s τ over the single letters is uniformly bounded. Iterating this bound and summing lengths below q q q gives the stated short-word bound. □ \square □
At the barycenter 1 / d 1/d 1/ d the total roof of an accelerated word satisfies e S m = N ( w ) / d e^{S_m}=N(w)/d e S m = N ( w ) / d : the unnormalized parent dynamics multiply successively by A i T A_i^{\mathsf T} A i T , and the product of the normalization factors is its final coordinate sum. An unaccelerated word decomposes into a possible initial run of the initially last label followed by accelerated letters. An initial run of length A ≥ 0 A\ge0 A ≥ 0 at the barycenter gives factor 1 + A ( d − 1 ) / d 1+A(d-1)/d 1 + A ( d − 1 ) / d . The sum of these factors to power − s -s − s is finite for every s > 1 s>1 s > 1 . Lemmas 6 and 7 therefore give T ( B ) ≍ ( log B ) β T(B)\asymp(\log B)^\beta T ( B ) ≍ ( log B ) β , and normalized bad-prefix estimates O ( ε + e − c t ) O(\varepsilon+e^{-ct}) O ( ε + e − c t ) for q ≤ c ′ t q\le c't q ≤ c ′ t , with t = log log B t=\log\log B t = log log B and positive constants c , c ′ c,c' c , c ′ . Here the short-word bound in Lemma 7 is summed with the initial-run weights at s < β s<\beta s < β . The relative count lost by cutting the initial runs at A = R A=R A = R is at most C ∑ A > R ( 1 + A ( d − 1 ) / d ) − β C\sum_{A>R}(1+A(d-1)/d)^{-\beta} C ∑ A > R ( 1 + A ( d − 1 ) / d ) − β . For any fixed initial run, the proof of prefix domination gives the same bound with its resulting initial state, up to a fixed constant after normalization by T ( B ) T(B) T ( B ) .
Escape from matrix subspaces
A.2. Escape from matrix subspaces. Write U = J − I U=J-I U = J − I , where J J J is the all-one d × d d\times d d × d matrix. We first prove that the group Γ \Gamma Γ generated by the A i A_i A i is of finite index in SL d ( Z ) \operatorname{SL}_d(\mathbb{Z}) SL d ( Z ) . Put u i = 1 − e i u_i=\mathbf{1}-e_i u i = 1 − e i . For distinct i , j , l i,j,l i , j , l , direct multiplication gives
A l A j A l − 1 = I + ( u l + u j ) ( e j − e l ) T . A_lA_jA_l^{-1}=I+(u_l+u_j)(e_j-e_l)^{\mathsf T}. A l A j A l − 1 = I + ( u l + u j ) ( e j − e l ) T .
The right-hand matrix fixes u i u_i u i , and right multiplication of e i T e_i^{\mathsf T} e i T by its inverse changes that row by − 2 ( e j − e l ) T -2(e_j-e_l)^{\mathsf T} − 2 ( e j − e l ) T . Its commutator with A i A_i A i is therefore I − 2 u i ( e j − e l ) T I-2u_i(e_j-e_l)^{\mathsf T} I − 2 u i ( e j − e l ) T . This and A i 2 A_i^2 A i 2 give I + 2 u i f T I+2u_if^{\mathsf T} I + 2 u i f T for every integral row f f f annihilating u i u_i u i , since the rows e l T e_l^{\mathsf T} e l T and ( e j − e l ) T (e_j-e_l)^{\mathsf T} ( e j − e l ) T with j , l ≠ i j,l\ne i j , l = i generate the annihilator. For i ≠ j i\ne j i = j take f = 1 T − ( d − 1 ) e j T f=\mathbf{1}^{\mathsf T}-(d-1)e_j^{\mathsf T} f = 1 T − ( d − 1 ) e j T . Then f U = ( d − 1 ) e j T fU=(d-1)e_j^{\mathsf T} f U = ( d − 1 ) e j T and U e i = u i Ue_i=u_i U e i = u i , so U − 1 T U U^{-1}TU U − 1 T U contains I + 2 ( d − 1 ) e i e j T I+2(d-1)e_ie_j^{\mathsf T} I + 2 ( d − 1 ) e i e j T . It lies in SL d ( Z ) \operatorname{SL}_d(\mathbb{Z}) SL d ( Z ) because U − 1 A i U = A i T U^{-1}A_iU=A_i^{\mathsf T} U − 1 A i U = A i T . The elementary level subgroup has finite index by the Tits–Vaserstein theorem [19 Proposition 3.18] . Rational conjugation yields commensurable integral groups, so Γ \Gamma Γ has finite index as well. In particular it is Zariski dense and has property ( T ) (\mathrm{T}) ( T ) [20 ] .
Lemma 8. For every proper real linear subspace W W W of the matrix space, the probability that the product of m m m accelerated letters is in W W W is at most C e − c m Ce^{-cm} C e − c m , uniformly in the initial state and W W W . This holds for the chronological matrix product and for its reversal.
Proof. The derivative of the one-letter log probability is uniformly bounded: the derivative of log ( 1 + a ( 1 − w j ) ) \log(1+a(1-w_j)) log ( 1 + a ( 1 − w j )) is bounded independently of a a a , and the eigenfunction ratios have uniformly bounded derivatives by the one-step contraction bound and the positive minimum of h h h . Summing the variations under successive contraction gives
∣ log P x ( p ) − log P y ( p ) ∣ ≤ C ∥ x − y ∥ \lvert\log\mathbb{P}_x(p)-\log\mathbb{P}_y(p)\rvert\le C\lVert x-y\rVert ∣ log P x ( p ) − log P y ( p )∣ ≤ C ∥ x − y ∥
for any word p p p and starting columns x , y x,y x , y with the same ordering.
In the finite permutation graph, every state reaches every other because the move-to-last cycles of the final two through the final d d d positions generate the symmetric group. There are loops of lengths two and three at every state, obtained by repeating the move at the second-last and third-last position, respectively. Hence there is a fixed core length ℓ \ell ℓ such that for each pair of states a connecting core of length ℓ \ell ℓ can finish with one move of each label in a prescribed order giving the terminal state. To see this, first connect to any state whose last label differs from the first prescribed label, pad by combinations of lengths two and three, then apply the prescribed sequence. Use exponent one throughout, and form d d d alternatives by increasing one exponent of the final sequence from one to two. The matrix product of the base core cancels the initial connector in taking right differences with its alternatives. For a final sequence i 1 , … , i d i_1,\ldots,i_d i 1 , … , i d , those differences are the conjugates of A i j A_{i_j} A i j by A i j + 1 ⋯ A i d A_{i_{j+1}}\cdots A_{i_d} A i j + 1 ⋯ A i d , with inverse on the left. Starting at the last position and successively stripping known conjugators shows that the differences generate Γ \Gamma Γ .
Split the word into cores of length ℓ \ell ℓ , each followed by a buffer of a length b b b to be fixed, and one bounded final remainder. Condition on all buffers, all core endpoint states, and the final remainder. The allowed cores form a Cartesian product. For each core after the first, approximate its input by applying the preceding fixed buffer to a fixed reference column with the correct ordering. The distortion estimate bounds the log probability error of the whole following core and buffer by O ( ρ b ) O(\rho^b) O ( ρ b ) . Use the actual initial column for the first core. The final remainder incurs at most a fixed additional distortion factor. Normalizing the conditional weights therefore dominates the conditional law by independent core laws times C exp ( C m 0 ρ b ) C\exp(Cm_0\rho^b) C exp ( C m 0 ρ b ) , where m 0 m_0 m 0 is the number of cores. Each witness core has probability at least a fixed positive constant in its reference law. Indeed the probability of each fixed witness from any start has a uniform positive lower bound. The weights of the following buffer from the different admissible end columns have bounded ratios by the word distortion estimate. Their common scale cancels in normalization, leaving a witness lower bound independent of b b b .
Property (T) gives a uniform upper bound θ < 1 \theta<1 θ < 1 on the operator norm of the average of the reference core matrices in any unitary representation with no invariant vectors. In fact the difference between the squared norm of a vector and the squared norm of its average is one half the weighted sum of the squared distances between its translates by two possible cores. Restrict to pairs consisting of the base core and one of its alternatives. The witness lower bound and the Kazhdan constant for their difference give a fixed lower bound times the squared norm of the vector. There are only finitely many possible witness sets. Multiplication by fixed buffers on either side and inversion preserve the operator bound.
For a proper complex algebraic subgroup H H H of S L d \mathrm{SL}_d SL d , its intersection with Γ \Gamma Γ has infinite index by Zariski density and the irreducibility of S L d \mathrm{SL}_d SL d . Hence the representation on square-summable functions on the cosets has no invariant vectors. Taking matrix coefficients of the product of independent averages gives a bound θ m 0 \theta^{m_0} θ m 0 for hitting a coset of H H H , with fixed initial or final factors allowed. For an irreducible proper subvariety V V V , split the independent product as X Y XY X Y into nearly equal halves. Cauchy–Schwarz, applied before averaging over X X X , gives
P ( X Y ∈ V ) 2 ≤ P ( V Y − 1 = V ( Y ′ ) − 1 ) + sup y , y ′ ; V y − 1 ≠ V ( y ′ ) − 1 P ( X ∈ V y − 1 ∩ V ( y ′ ) − 1 ) . \mathbb{P}(XY \in V)^2 \le\mathbb{P}(VY^{-1}=V(Y')^{-1})+\sup_{\substack{y,y';\,Vy^{-1}\ne V(y')^{-1}}}\mathbb{P}(X\in Vy^{-1}\cap V(y')^{-1}). P ( X Y ∈ V ) 2 ≤ P ( V Y − 1 = V ( Y ′ ) − 1 ) + y , y ′ ; V y − 1 = V ( y ′ ) − 1 sup P ( X ∈ V y − 1 ∩ V ( y ′ ) − 1 ) .
where Y ′ Y' Y ′ is an independent copy of Y Y Y . The first term is a right-stabilizer hitting probability for the product Y − 1 Y ′ Y^{-1}Y' Y − 1 Y ′ , and the stabilizer is proper. Each intersection in the second term has dimension strictly below dim V \dim V dim V and degree at most deg ( V ) 2 \deg(V)^2 deg ( V ) 2 . The second term is omitted when all pairs of translates coincide. Induction on dimension gives a bound 2 deg ( V ) e − c j m 0 2\deg(V)e^{-c_jm_0} 2 deg ( V ) e − c j m 0 for dimension at most j j j , allowing c j c_j c j to decrease at each step. For dimension zero one applies the coset bound to each point. For the induction one can use c j ≤ c j − 1 / 6 c_j\le c_{j-1}/6 c j ≤ c j − 1 /6 , since both half lengths are at least m 0 / 3 m_0/3 m 0 /3 for m 0 ≥ 2 m_0\ge2 m 0 ≥ 2 , and sum over components using the degree bound. The cases of zero or one factors are covered by decreasing constants. The complex span of S L d \mathrm{SL}_d SL d is all matrix space. Subtracting the identity from elementary matrices gives the off-diagonal matrix units. Multiplying I + e i e j T I+e_ie_j^{\mathsf T} I + e i e j T by I + e j e i T I+e_je_i^{\mathsf T} I + e j e i T and subtracting the identity and the two off-diagonal units gives the diagonal unit in slot i i i . Thus the complexification of a proper real matrix subspace intersects S L d \mathrm{SL}_d SL d in a proper variety of bounded degree, and the independent estimate applies. Choose b b b so that the exponential comparison loss is less than half the escape rate per core. Now m 0 m_0 m 0 is proportional to the full run length up to a bounded error. The same proof for the reverse product conditions chronologically and multiplies the independent factors in the opposite order. □
Lattices, strips, and rational graphs
Lemma 9. Let M m M_m M m be the chronological or reverse product of m m m accelerated letters. For a primitive integer column v v v and a subgroup Λ \Lambda Λ of Z d \mathbb{Z}^d Z d of finite index D Λ D_\Lambda D Λ ,
P ( M m v ∈ Λ ) ≤ C exp [ − c min ( m , log ( 2 + D Λ ) ) ] . \mathbb{P}(M_m v\in\Lambda)\le C\exp[-c\min(m,\log(2+D_\Lambda))]. P ( M m v ∈ Λ ) ≤ C exp [ − c min ( m , log ( 2 + D Λ ))] . For the reverse product, any nonzero real column v v v , and any real linear form ℓ ≠ 0 \ell\ne0 ℓ = 0 , one has
P ( ∣ ℓ ( M m v ) ∣ ≤ ϵ ∥ ℓ ∥ ∥ M m v ∥ ) ≤ C exp [ − c min ( m , log ( 1 / ϵ ) ) ] ( 0 < ϵ < 1 / 2 ) . \mathbb{P}(|\ell(M_m v)|\le\epsilon\|\ell\|\|M_m v\|)\le C\exp[-c\min(m,\log(1/\epsilon))]\qquad(0<\epsilon<1/2). P ( ∣ ℓ ( M m v ) ∣ ≤ ϵ ∥ ℓ ∥∥ M m v ∥ ) ≤ C exp [ − c min ( m , log ( 1/ ϵ ))] ( 0 < ϵ < 1/2 ) . The constants are uniform in the initial state and the objects in these events.
Proof. The maximum row sum of A i a A_i^a A i a equals 1 + a ≤ 2 e τ 1+a\le2e^\tau 1 + a ≤ 2 e τ . Hence the absolute entries of a product of m m m letters are bounded by 2 m e S m 2^m e^{S_m} 2 m e S m . Iterating the conditional moment bound gives E e χ S m ≤ M χ m \mathbb{E}e^{\chi S_m}\le M_\chi^m E e χ S m ≤ M χ m for a constant M χ M_\chi M χ . Markov’s inequality gives probability at most e − m e^{-m} e − m that some entry exceeds e K m e^{Km} e K m , for large fixed K K K .
If the integral matrices of entry size at most R R R sending v v v into Λ \Lambda Λ span matrix space, select d 2 d^2 d 2 independent ones. The matrix of their vectorizations has nonzero integer determinant b b b with ∣ b ∣ ≤ ( d R ) d 2 |b|\le(dR)^{d^2} ∣ b ∣ ≤ ( d R ) d 2 by the row-norm determinant bound. Its adjugate shows that their integer span contains b b b times every integer matrix. A primitive column has coordinates of gcd one, so integer matrices send it onto all of Z d \mathbb{Z}^d Z d . Thus b Z d ⊆ Λ b\mathbb{Z}^d\subseteq\Lambda b Z d ⊆ Λ , giving D Λ ≤ ( d R ) d 3 D_\Lambda\le(dR)^{d^3} D Λ ≤ ( d R ) d 3 . For R = e K m R=e^{Km} R = e K m and larger D Λ D_\Lambda D Λ , the truncated hitting matrices lie in a proper subspace and Lemma 8 applies.
For the strip, normalize the matrix linear functional g ↦ ℓ ( g v ) g\mapsto\ell(gv) g ↦ ℓ ( g v ) to coefficient norm one by dividing by ∥ ℓ ∥ ∥ v ∥ \|\ell\|\|v\| ∥ ℓ ∥∥ v ∥ . On hitting matrices of entry size at most R R R , its values have magnitude at most d R e dRe d R e . If the matrices span, solve for the coefficients of the functional by inverting the square vectorization matrix of d 2 d^2 d 2 independent ones. Every cofactor is bounded by C d R d 2 − 1 C_dR^{d^2-1} C d R d 2 − 1 and the determinant has absolute value at least one. The coefficient norm forces 1 ≤ C d e R d 2 1\le C_d eR^{d^2} 1 ≤ C d e R d 2 . For smaller ϵ \epsilon ϵ , the truncated hitting matrices again lie in a proper subspace.
For a word of arbitrary length m m m , condition before its final block of length m ′ ≤ m m'\le m m ′ ≤ m . In the chronological product, the fixed prefix replaces the target lattice by its inverse image under an integral unimodular matrix, preserving index. In the reverse product it replaces the input by another primitive column. For a strip in the reverse product it replaces only the nonzero input. Choose m ′ m' m ′ comparable to the minimum in the appropriate assertion with a sufficiently small proportionality constant, so the preceding thresholds apply. Bounded minima are absorbed by increasing C C C .
Lemma 10. The number of accelerated words of total roof at most t t t satisfying the lattice event in Lemma 9 is at most
C e β t exp [ − c min ( t , log ( 2 + D Λ ) ) ] C e^{\beta t}\exp[-c\min(t,\log(2+D_{\Lambda}))] C e β t exp [ − c min ( t , log ( 2 + D Λ ))] For the strip event with the reverse product the same conclusion holds with log ( 1 / ϵ ) \log(1/\epsilon) log ( 1/ ϵ ) replacing log ( 2 + D Λ ) \log(2+D_{\Lambda}) log ( 2 + D Λ ) .
Proof. Let Q Q Q denote the corresponding logarithm. Choose an integer N N N proportional to min ( t , Q ) \min(t,Q) min ( t , Q ) and put u = L 0 N u=L_0N u = L 0 N , with L 0 L_0 L 0 large and the constant in N N N small enough that t ≥ 2 u t \ge2u t ≥ 2 u . Bounded N N N are covered by Lemma 7 . The normalized word count is bounded by a constant times the expected sum of e − β ( t − S m ) e^{-\beta(t-S_m)} e − β ( t − S m ) at eligible endpoints S m ≤ t S_m \le t S m ≤ t . Let J J J be the first time with S J ≥ t − u S_J \ge t-u S J ≥ t − u . Earlier endpoints contribute O ( e − β u ) O(e^{-\beta u}) O ( e − β u ) by the geometric occupation estimate. After J J J there are at most 1 + u / log ( 3 / 2 ) 1+u/\log(3/2) 1 + u / log ( 3/2 ) feasible offsets. For each offset at least N N N , condition at J J J and apply Lemma 9 to the continuation, obtaining O ( e − c N ) O(e^{-cN}) O ( e − c N ) .
An overshoot with S J > t − u / 2 S_J > t-u/2 S J > t − u /2 has probability at most C e − κ u / 2 C e^{-\kappa u/2} C e − κ u /2 , by summing the one-increment overshoot bound against the geometric occupation estimate below t − u t-u t − u . The probability that S J + N − S J > u / 4 S_{J+N}-S_J > u/4 S J + N − S J > u /4 is at most M N − κ u / 4 M N^{-\kappa u/4} M N − κ u /4 by conditioning at J J J . On the complement of both events, the offsets less than N N N have S m ≤ t − u / 4 S_m \le t-u/4 S m ≤ t − u /4 , hence discount at most e − β u / 4 e^{-\beta u/4} e − β u /4 . Multiplying by O ( 1 + u ) O(1+u) O ( 1 + u ) , choosing L 0 L_0 L 0 large, and decreasing c c c gives the asserted bound.
Proposition 11. Choose one ascending word for each sorted nonroot solution and let v ( x ) = C ( w ) 1 v(x)=C(w)1 v ( x ) = C ( w ) 1 be its label. With L = log B L=\log B L = log B for B ≥ 2 B\ge2 B ≥ 2 , there is η > 0 \eta>0 η > 0 such that, uniformly in the target,
# { x : x n ≤ B , v ( x ) ∈ Λ } T ( B ) ≪ D Λ − η + L − η \frac{\#\{x:x_n\le B,\ v(x)\in\Lambda\}}{T(B)}\ll D_{\Lambda}^{-\eta}+L^{-\eta} T ( B ) # { x : x n ≤ B , v ( x ) ∈ Λ } ≪ D Λ − η + L − η # { x : x n ≤ B , ∣ ℓ ( v ( x ) ) ∣ ≤ ϵ ∥ ℓ ∥ ∥ v ( x ) ∥ } T ( B ) ≪ ϵ η + L − η \frac{\#\{x:x_n\le B,\ |\ell(v(x))|\le\epsilon\|\ell\|\|v(x)\|\}}{T(B)}\ll\epsilon^{\eta}+L^{-\eta} T ( B ) # { x : x n ≤ B , ∣ ℓ ( v ( x )) ∣ ≤ ϵ ∥ ℓ ∥∥ v ( x ) ∥ } ≪ ϵ η + L − η Here Λ \Lambda Λ is any subgroup of Z d \mathbb{Z}^d Z d of finite index D Λ D_{\Lambda} D Λ , ℓ \ell ℓ is a nonzero linear form, and 0 < ϵ < 1 / 2 0<\epsilon<1/2 0 < ϵ < 1/2 . In particular a proper real subspace contains O ( T ( B ) L − η ) O(T(B)L^{-\eta}) O ( T ( B ) L − η ) labels.
For G ∈ GL d ( Q ) G\in\operatorname{GL}_d(\mathbb{Q}) G ∈ GL d ( Q ) put D G = [ Z d : { v ∈ Z d : G v ∈ Z d } ] D_G=[\mathbb{Z}^d:\{v\in\mathbb{Z}^d:Gv\in\mathbb{Z}^d\}] D G = [ Z d : { v ∈ Z d : G v ∈ Z d }] and K ( G ) = max ( 2 , D G , ∥ G ∥ , ∥ G − 1 ∥ ) K(G)=\max(2,D_G,\|G\|,\|G^{-1}\|) K ( G ) = max ( 2 , D G , ∥ G ∥ , ∥ G − 1 ∥ ) . The number of pairs of solutions with both maxima at most B B B and v ( y ) = G v ( x ) v(y)=Gv(x) v ( y ) = G v ( x ) , divided by T ( B ) T(B) T ( B ) , is O ( K ( G ) − η + L − η ) O(K(G)^{-\eta}+L^{-\eta}) O ( K ( G ) − η + L − η ) . If G G G is determined by d d d independent pairs of such labels, this is O ( K ( G ) − η ′ ) O(K(G)^{-\eta'}) O ( K ( G ) − η ′ ) for a fixed η ′ > 0 \eta'>0 η ′ > 0 .
Proof. For lattices split an unaccelerated word into the initial run and accelerated part. The initial prefix preserves the index of the inverse-image lattice. If its roof is at most half the total cutoff t t t , Lemma 10 gives a common exponential saving in min ( t , log ( 2 + D Λ ) ) \min(t,\log(2+D_{\Lambda})) min ( t , log ( 2 + D Λ )) , and the initial-run weights sum to a bounded factor. Larger initial runs contribute at most C e β t e − ( β − 1 ) t / 2 C e^{\beta t}e^{-(\beta-1)t/2} C e β t e − ( β − 1 ) t /2 , since the factors are linear in the initial run length and their inverse β \beta β -powers sum to that tail bound. Apply the nonlinear comparison and T ( B ) ≍ L β T(B)\asymp L^\beta T ( B ) ≍ L β with t = log L + O ( 1 ) t=\log L+O(1) t = log L + O ( 1 ) .
For strips, reverse each finite word. If C C C is its chronological product and C ′ C' C ′ the reverse product, the identity U − 1 A i U = A i T U^{-1}A_iU=A_i^{\mathsf T} U − 1 A i U = A i T gives C ′ = U C T U − 1 C'=UC^{\mathsf T}U^{-1} C ′ = U C T U − 1 . Because the row and column sums of U U U equal d − 1 d-1 d − 1 , the scalar size is unchanged by reversal. The old chronological vector is the reverse-product vector of the newly indexed word. For each nonempty reversed run word choose an initial ordering in which its first label is nonlast. These finitely many orderings cover all words. At the barycenter the scalar roof remains log ( N ( w ) / d ) \log(N(w)/d) log ( N ( w ) / d ) for each word. Apply the reverse-product strip bound of Lemma 10 to the reindexed upper count; the empty word is absorbed by decreasing η \eta η . Letting ϵ \epsilon ϵ tend to zero gives the hyperplane estimate, and any proper subspace is contained in a hyperplane.
For the graph estimate, input and output each determine the other by label injectivity and invertibility. Apply the lattice estimate with index D G D_G D G . Every label has norm at most C L CL C L by Lemma 6 . For ∥ G ∥ ≥ 2 \lVert G\rVert\ge2 ∥ G ∥ ≥ 2 , the inputs of norm at most C L ∥ G ∥ − 1 / 2 CL\lVert G\rVert^{-1/2} C L ∥ G ∥ − 1/2 number at most C ′ ( L β ∥ G ∥ − β / 2 + 1 ) C'(L^\beta\lVert G\rVert^{-\beta/2}+1) C ′ ( L β ∥ G ∥ − β /2 + 1 ) by the scalar word bound, since their positive coordinate sums are comparable to their norms. For the other inputs, take a row of G G G of norm at least ∥ G ∥ / d \lVert G\rVert/\sqrt{d} ∥ G ∥ / d . Its value on the input has absolute size at most C L CL C L , so these inputs lie in a strip of relative width O ( ∥ G ∥ − 1 / 2 ) O(\lVert G\rVert^{-1/2}) O (∥ G ∥ − 1/2 ) . This gives the bound in ∥ G ∥ \lVert G\rVert ∥ G ∥ , and switching endpoints gives that in ∥ G − 1 ∥ \lVert G^{-1}\rVert ∥ G − 1 ∥ . Use the strongest of the three bounds. Finally let X , Y X,Y X , Y be matrices with the independent input and output labels as columns, so G = Y X − 1 G=YX^{-1} G = Y X − 1 . The input lattice contains X Z d X\mathbb{Z}^{d} X Z d and hence D G ≤ ∣ det X ∣ ≪ L d D_G\leq\lvert\det X\rvert\ll L^d D G ≤ ∣ det X ∣ ≪ L d . The cofactor formulas and the nonzero integer determinants give ∥ Y X − 1 ∥ + ∥ X Y − 1 ∥ ≪ L d \lVert YX^{-1}\rVert+\lVert XY^{-1}\rVert\ll L^d ∥ Y X − 1 ∥ + ∥ X Y − 1 ∥ ≪ L d . Thus the time error L − η L^{-\eta} L − η is absorbed after decreasing the exponent. □
Appendix B. Quantitative separation of integer normals
Fix the integers n ≥ 4 n\geq4 n ≥ 4 and k ≥ 0 k\geq0 k ≥ 0 of the density problem and put d = n − 1 d=n-1 d = n − 1 and C = n ( k + 1 ) C=n(k+1) C = n ( k + 1 ) . This section works with sorted tuples. Start from a fixed nonroot positive integral solution. In a forward move j ≤ d j\leq d j ≤ d , mutate the j j j th entry, remove it from its old position, and place the new maximum last. A block ( A , j ) (A,j) ( A , j ) , where A ≥ 0 A\geq0 A ≥ 0 and j < d j<d j < d , consists of this move followed by A A A moves in position d d d . Under the Gibbs law in Appendix § 5 , after any finite history,
c ∗ ( A + 1 ) − β ≤ Pr ( ( A , j ) ∣ history ) ≤ C ∗ ( A + 1 ) − β , β > 1 , (4) c_*(A+1)^{-\beta}\leq\Pr((A,j)\mid\text{history})\leq C_*(A+1)^{-\beta},\qquad\beta>1, \tag*{(4)} c ∗ ( A + 1 ) − β ≤ Pr (( A , j ) ∣ history ) ≤ C ∗ ( A + 1 ) − β , β > 1 , (4)
where c ∗ , C ∗ > 0 c_*,C_*>0 c ∗ , C ∗ > 0 are fixed. In the notation of Lemma 7 , this block has run length a = A + 1 a=A+1 a = A + 1 . Its active label is the label currently in sorted position j j j . The GMR transition probabilities give (4) , and Lemma 7 transfers finite prefix probabilities to height counts.
Height approximation on a prefix
Put t = k / C t=k/C t = k / C , s = C 1 / ( n − 2 ) s=C^{1/(n-2)} s = C 1/ ( n − 2 ) , and z i = s ( x i − t ) z_i=s(x_i-t) z i = s ( x i − t ) for every entry of a tuple. Each z i > 1 z_i>1 z i > 1 : indeed t < 1 / n t<1/n t < 1/ n and s ≥ n 1 / ( n − 2 ) s\geq n^{1/(n-2)} s ≥ n 1/ ( n − 2 ) , while ( n / ( n − 1 ) ) n − 2 < e < n (n/(n-1))^{n-2}<e<n ( n / ( n − 1 ) ) n − 2 < e < n . Write e r ( z ) e_r(z) e r ( z ) for the sum of the products of r r r distinct entries, with e 0 = 1 e_0=1 e 0 = 1 . The equation becomes
∏ i = 1 n z i = ∑ i = 1 n z i 2 + ∑ r = 0 n − 2 a r e r ( z ) , a r ≥ 0. \prod_{i=1}^{n}z_i=\sum_{i=1}^{n}z_i^2+\sum_{r=0}^{n-2}a_r e_r(z),\qquad a_r\geq0. i = 1 ∏ n z i = i = 1 ∑ n z i 2 + r = 0 ∑ n − 2 a r e r ( z ) , a r ≥ 0.
In fact, in the variables y i = x i − t y_i=x_i-t y i = x i − t , the coefficient of e r ( y ) e_r(y) e r ( y ) from the product terms is k ( n − r ) t n − 1 − r − C t n − r = k ( n − r − 1 ) t n − 1 − r k(n-r)t^{n-1-r}-Ct^{n-r}=k(n-r-1)t^{n-1-r} k ( n − r ) t n − 1 − r − C t n − r = k ( n − r − 1 ) t n − 1 − r for 0 ≤ r ≤ n − 1 0\leq r\leq n-1 0 ≤ r ≤ n − 1 . It vanishes for r = n − 1 r=n-1 r = n − 1 . The square terms add n t 2 nt^2 n t 2 and 2 t 2t 2 t to the constant and linear terms, respectively. Substituting y i = z i / s y_i=z_i/s y i = z i / s and multiplying by s 2 s^2 s 2 gives the displayed identity.
For the quadratic in z n z_n z n , write P = ∏ i = 1 d z i P=\prod_{i=1}^{d}z_i P = ∏ i = 1 d z i ,
E = ∑ r = 1 n − 2 a r e r − 1 ( z 1 , … , z d ) , Q = ∑ i = 1 d z i 2 + ∑ r = 0 n − 2 a r e r ( z 1 , … , z d ) . E=\sum_{r=1}^{n-2}a_r e_{r-1}(z_1,\ldots,z_d),\qquad Q=\sum_{i=1}^{d}z_i^2+\sum_{r=0}^{n-2}a_r e_r(z_1,\ldots,z_d). E = r = 1 ∑ n − 2 a r e r − 1 ( z 1 , … , z d ) , Q = i = 1 ∑ d z i 2 + r = 0 ∑ n − 2 a r e r ( z 1 , … , z d ) .
At every nonroot sorted solution z n z_n z n is the larger root of Z 2 − ( P − E ) Z + Q = 0 Z^2-(P-E)Z+Q=0 Z 2 − ( P − E ) Z + Q = 0 , by descent. Put
u ( x ) = ( log z 1 , … , log z d ) T , h ( x ) = log z n , Δ ( x ) = ∑ i = 1 d log z i − h ( x ) . u(x)=(\log z_1,\ldots,\log z_d)^{\mathsf T},\qquad h(x)=\log z_n,\qquad\Delta(x)=\sum_{i=1}^{d}\log z_i-h(x). u ( x ) = ( log z 1 , … , log z d ) T , h ( x ) = log z n , Δ ( x ) = i = 1 ∑ d log z i − h ( x ) .
The larger-root formula gives
Δ ( x ) = − log ( 1 − E / P ) − log ( 1 + 1 − 4 ( Q / P 2 ) / ( 1 − E / P ) 2 2 ) . \Delta(x)=-\log(1-E/P)-\log\left(\frac{1+\sqrt{1-4(Q/P^2)/(1-E/P)^2}}{2}\right). Δ ( x ) = − log ( 1 − E / P ) − log ( 2 1 + 1 − 4 ( Q / P 2 ) / ( 1 − E / P ) 2 ) .
This is nonnegative and increasing in each of E / P E/P E / P and Q / P 2 Q/P^2 Q / P 2 on the larger-root domain. Every monomial in these two ratios has nonpositive exponents. Forward moves increase the entries of the sorted tuple coordinatewise, so Δ \Delta Δ never increases. If min i x i ≥ Y \min_i x_i \ge Y min i x i ≥ Y , both ratios are O ( Y − 2 ) O(Y^{-2}) O ( Y − 2 ) : a monomial of E / P E/P E / P omits at least two slots and the terms z i 2 / P 2 z_i^2/P^2 z i 2 / P 2 each have at least two inverse factors. The terms e r / P 2 e_r/P^2 e r / P 2 satisfy the same bound. For Y Y Y sufficiently large the root formula thus gives Δ = O ( Y − 2 ) \Delta= O(Y^{-2}) Δ = O ( Y − 2 ) .
Let
M j u = ( u 1 , … , u ^ j , … , u d , ∑ i = 1 d u i ) T . M_j u = (u_1,\ldots,\hat{u}_j,\ldots,u_d,\sum_{i=1}^{d}u_i)^{\mathsf T}. M j u = ( u 1 , … , u ^ j , … , u d , i = 1 ∑ d u i ) T .
Here a hat denotes omission. The exact log recurrence is u ( x ′ ) = M j u ( x ) − Δ ( x ) e d u(x') = M_j u(x) - \Delta(x)e_d u ( x ′ ) = M j u ( x ) − Δ ( x ) e d , where e d e_d e d is the last standard vector. The matrix of a chronological sequence w = j 1 ⋯ j m w = j_1\cdots j_m w = j 1 ⋯ j m is M w = M j m ⋯ M j 1 M_w = M_{j_m}\cdots M_{j_1} M w = M j m ⋯ M j 1 , with empty product the identity. Write v w = M w T 1 v_w = M_w^{\mathsf T}\mathbf{1} v w = M w T 1 , with 1 \mathbf{1} 1 the all-one column. For b = ( 0 , … , 0 , 1 , 1 ) T b = (0,\ldots,0,1,1)^{\mathsf T} b = ( 0 , … , 0 , 1 , 1 ) T , inspection gives M j b − b ≥ e d M_jb-b \ge e_d M j b − b ≥ e d coordinatewise. Along a tail W W W from x p x_p x p , nonnegativity of the matrices and monotonicity of the defect give by induction
M W ( u ( x p ) − Δ ( x p ) b ) + Δ ( x p ) b ≤ u ( x p W ) ≤ M W u ( x p ) . M_W\bigl(u(x_p)-\Delta(x_p)b\bigr)+\Delta(x_p)b \le u(x_pW)\le M_Wu(x_p). M W ( u ( x p ) − Δ ( x p ) b ) + Δ ( x p ) b ≤ u ( x p W ) ≤ M W u ( x p ) .
Summing and subtracting the terminal defect gives an error between zero and Δ ( x p ) 1 T M W b \Delta(x_p)\mathbf{1}^{\mathsf T}M_Wb Δ ( x p ) 1 T M W b . Thus with λ p = M p − 1 u ( x p ) \lambda_p=M_p^{-1}u(x_p) λ p = M p − 1 u ( x p ) ,
∣ h ( x p W ) − λ p ⋅ v p W ∣ ≤ 2 Δ ( x p ) ∥ M p − 1 ∥ ∥ v p W ∥ . (5) \left|h(x_pW)-\lambda_p\cdot v_{pW}\right|\le\sqrt{2}\,\Delta(x_p)\lVert M_p^{-1}\rVert\lVert v_{pW}\rVert. \tag*{(5)} ∣ h ( x p W ) − λ p ⋅ v p W ∣ ≤ 2 Δ ( x p ) ∥ M p − 1 ∥ ∥ v p W ∥ . (5)
All norms hereafter are Euclidean or induced operator norms. In the slot convention the first d d d entries are kept in place except that the previous maximum is inserted in the mutated slot. The corresponding forward log matrix is I + e i ( 1 − e i ) T I+e_i(1-e_i)^{\mathsf T} I + e i ( 1 − e i ) T in slot i i i . If P w P_w P w is the permutation carrying the first-slot order to the sorted order after w w w , each sorted matrix is the corresponding slot matrix multiplied on the left by the new permutation and on the right by the inverse of the preceding one. Thus the sorted product is P w P_w P w times the slot product times P ∅ − 1 P_{\varnothing}^{-1} P ∅ − 1 . Taking transposes and applying to 1 \mathbf{1} 1 cancels P w P_w P w and leaves the fixed initial permutation P ∅ P_{\varnothing} P ∅ .
Almost-sure limits of pulled-back logs
A move j < d j<d j < d gives a new maximum at least ( n + k − 1 ) (n+k-1) ( n + k − 1 ) times the product of the two largest entries before that move. Indeed the retained product includes both entries, the coefficient of that product in Vieta’s formula is at least n + k n+k n + k , and the removed entry is at most the retained product. At the end of a block the second-largest entry is at least the preceding block’s maximum. The logarithms of successive block maxima therefore satisfy a Fibonacci lower bound. In particular, if φ = ( 1 + 5 ) / 2 \varphi=(1+\sqrt{5})/2 φ = ( 1 + 5 ) /2 , the log maximum at depth q q q is at least c φ q c\varphi^q c φ q . If the initial minimum is Y Y Y sufficiently large, this bound holds with c log Y c\log Y c log Y in place of c c c , for a constant c > 0 c>0 c > 0 independent of the seed. A complete block of d d d consecutive ( 0 , 1 ) (0,1) ( 0 , 1 ) moves raises the minimum to at least the maximum at its start. If one occurs in the last half of the first q q q blocks, then Δ ( x q ) ≤ C 1 exp ( − c 1 q 1 2 ) \Delta(x_q)\le C_1\exp(-c_1q^{\frac12}) Δ ( x q ) ≤ C 1 exp ( − c 1 q 2 1 ) , with an additional factor log Y \log Y log Y in the exponent in the thick-seed case.
The norm of one block matrix and of its inverse is at most C 2 ( A + 1 ) C_2(A+1) C 2 ( A + 1 ) , since M d = I + e d ( 1 − e d ) T M_d=I+e_d(1-e_d)^{\mathsf T} M d = I + e d ( 1 − e d ) T and the added matrix squares to zero. The log increment across a block, before pullback, is bounded by C 3 ( A + 1 ) Δ ( x q ) C_3(A+1)\Delta(x_q) C 3 ( A + 1 ) Δ ( x q ) . To see this, use the coordinatewise sandwich with block matrix M d A M j M_d^A M_j M d A M j and bound its norm. Pulling back multiplies this error by at most the accumulated inverse norm. By (4) , large runs with log ( A q + 1 ) > a q \log(A_q+1)>aq log ( A q + 1 ) > a q have summable probabilities for any a > 0 a>0 a > 0 . Also, failure of a complete block in the last half at depth q q q has probability O ( e − c 1 q ) O(e^{-c_1q}) O ( e − c 1 q ) , by testing disjoint windows, each with conditional success probability at least c ∗ d c_*^d c ∗ d . Consequently, almost surely the pulled-back logs converge to a vector Λ x \Lambda_x Λ x . The convergence follows from summing errors of size exp ( O ( q 2 ) − c φ q / 2 ) \exp(O(q^2)-c\varphi^{q/2}) exp ( O ( q 2 ) − c φ q /2 ) . If p p p is a prefix and ω \omega ω a continuation, then
Λ x ( p ω ) = M p − 1 Λ x p ( ω ) . (6) \Lambda_x(p\omega)=M_p^{-1}\Lambda_{x_p}(\omega). \tag*{(6)} Λ x ( p ω ) = M p − 1 Λ x p ( ω ) . (6)
The same limit is obtained by using the vector u ∘ ( x ) = ( log x i + log s ) i = 1 d u^\circ(x)=(\log x_i+\log s)_{i=1}^{d} u ∘ ( x ) = ( log x i + log s ) i = 1 d . Their difference is O ( 1 / min i x i ) O(1/\min_i x_i) O ( 1/ min i x i ) , which vanishes after pullback along the same regular paths by the complete-block bound.
For a seed of minimum at least Y Y Y sufficiently large we will use the uniform estimate
Pr ( ∥ Λ x − u 0 ( x ) ∥ > K / Y ) ≤ K Y − ν (7) \Pr(\lVert\Lambda x-u^{0}(x)\rVert>K/Y)\leq KY^{-\nu} \tag*{(7)} Pr (∥ Λ x − u 0 ( x )∥ > K / Y ) ≤ K Y − ν (7)
with K , ν > 0 K,\nu>0 K , ν > 0 independent of the seed. For any fixed 0 < θ < β − 1 0<\theta<\beta-1 0 < θ < β − 1 , the conditional θ \theta θ -moment of C 2 ( A + 1 ) C_{2}(A+1) C 2 ( A + 1 ) is bounded. Iterating conditional expectations and summing Markov bounds over q ≥ 1 q\geq1 q ≥ 1 gives accumulated matrix and inverse norms at most e D q Y b e^{Dq}Y^{b} e D q Y b outside an event of size O ( Y − θ b ) O(Y^{-\theta b}) O ( Y − θ b ) , for fixed large D D D and any fixed b > 0 b>0 b > 0 . The same bounds can be imposed on the products of the individual norm upper bounds. For q q q below R = ⌊ a log Y ⌋ R=\lfloor a\log Y\rfloor R = ⌊ a log Y ⌋ , defect monotonicity bounds the error sum by O ( Y − 2 Y 2 b ∑ q ≤ R e 2 D ( q + 1 ) ) = O ( Y − 3 / 2 ) O(Y^{-2}Y^{2b}\sum_{q\leq R}e^{2D(q+1)})=O(Y^{-3/2}) O ( Y − 2 Y 2 b ∑ q ≤ R e 2 D ( q + 1 ) ) = O ( Y − 3/2 ) on taking a , b a,b a , b sufficiently small. For every q ≥ R q\geq R q ≥ R require a complete block in its last half, at total cost O ( e − c R ) O(e^{-cR}) O ( e − c R ) . The error sum from these depths is bounded using Δ ( x q ) ≤ C 1 exp ( − c 1 ( log Y ) φ q / 2 ) \Delta(x_q)\leq C_1\exp(-c_1(\log Y)^{\varphi^{q/2}}) Δ ( x q ) ≤ C 1 exp ( − c 1 ( log Y ) φ q /2 ) and is O ( Y − 3 / 2 ) O(Y^{-3/2}) O ( Y − 3/2 ) . The difference u − u 0 u-u^{0} u − u 0 at the initial state is O ( Y − 1 ) O(Y^{-1}) O ( Y − 1 ) , proving (7) .
Uniform avoidance of a prescribed hyperplane
Write X = x n X=x_n X = x n . Fix i < d i<d i < d , freeze the entries with indices in S = { 1 , … , d } ∖ { i } S=\{1,\ldots,d\}\setminus\{i\} S = { 1 , … , d } ∖ { i } , and let P i P_i P i be their product. For T ⊆ S T\subseteq S T ⊆ S put
E T = C − k ∑ j ∈ T x j − 1 , D T = log ( C / E T ) , A i = P i E S . E_T=C-k\sum_{j\in T}x_j^{-1},\qquad D_T=\log(C/E_T),\qquad A_i=P_iE_S. E T = C − k j ∈ T ∑ x j − 1 , D T = log ( C / E T ) , A i = P i E S .
In the two active slots, b 0 = x i , b 1 = X b_0=x_i,b_1=X b 0 = x i , b 1 = X and b m + 1 = A i b m − k P i − b m − 1 b_{m+1}=A_ib_m-kP_i-b_{m-1} b m + 1 = A i b m − k P i − b m − 1 . If λ > 1 \lambda>1 λ > 1 is the root of λ + λ − 1 = A i \lambda+\lambda^{-1}=A_i λ + λ − 1 = A i and q = k P i / ( A i − 2 ) q=kP_i/(A_i-2) q = k P i / ( A i − 2 ) , then b m = q + a λ m + b λ − m b_m=q+a\lambda^m+b\lambda^{-m} b m = q + a λ m + b λ − m . Here A i ≥ ( n + 2 k ) P i A_i\geq(n+2k)P_i A i ≥ ( n + 2 k ) P i , so q < 1 / 2 q<1/2 q < 1/2 .
To compute a b ab ab , the active conic is
b m 2 + b m + 1 2 − A i b m b m + 1 + k P i ( b m + b m + 1 ) + ∑ j ∈ S x j 2 = 0. b_m^2+b_{m+1}^2-A_ib_mb_{m+1}+kP_i(b_m+b_{m+1})+\sum_{j\in S}x_j^2=0. b m 2 + b m + 1 2 − A i b m b m + 1 + k P i ( b m + b m + 1 ) + j ∈ S ∑ x j 2 = 0.
After shifting each active entry by q q q , the constant term is ∑ j ∈ S x j 2 + ( k P i ) 2 / ( A i − 2 ) \sum_{j\in S}x_j^2+(kP_i)^2/(A_i-2) ∑ j ∈ S x j 2 + ( k P i ) 2 / ( A i − 2 ) . Substituting the two powers of λ \lambda λ leaves the mixed term − ( A i 2 − 4 ) a b -(A_i^2-4)ab − ( A i 2 − 4 ) ab . Hence a b > 0 ab>0 ab > 0 and is bounded uniformly, as the frozen squares sum to at most ( n − 2 ) P i 2 (n-2)P_i^2 ( n − 2 ) P i 2 . Since X X X is the larger root when x i x_i x i is retained, X − q ≥ A i ( x i − q ) / 2 X-q\geq A_i(x_i-q)/2 X − q ≥ A i ( x i − q ) /2 , so a ≥ b > 0 a\geq b>0 a ≥ b > 0 and a ≥ x i / 4 a\geq x_i/4 a ≥ x i /4 . Also x i 2 ≤ ∏ j = 1 d x j x_i^2\leq\prod_{j=1}^{d}x_j x i 2 ≤ ∏ j = 1 d x j since i < d i<d i < d . The upper Vieta bound X ≤ C ∏ j = 1 d x j X\leq C\prod_{j=1}^{d}x_j X ≤ C ∏ j = 1 d x j then gives X ≤ K 1 λ 2 X\leq K_1\lambda^2 X ≤ K 1 λ 2 . The lower Vieta bound X ≥ ( n + k − 1 ) ∏ j = 1 d x j X\geq(n+k-1)\prod_{j=1}^{d}x_j X ≥ ( n + k − 1 ) ∏ j = 1 d x j gives A i ≤ K 2 X A_i\leq K_2X A i ≤ K 2 X . Constants here and below may depend on n , k n,k n , k and (4) .
Make m m m moves in the active pair and then clear the frozen slots in some order j 1 , … , j d − 1 j_1,\ldots,j_{d-1} j 1 , … , j d − 1 . The first move is noncusp and the next m − 1 m-1 m − 1 are cusp moves. Every clearing is noncusp because an active entry greater than each frozen entry now precedes the maximum. Thus this specifies exactly d d d blocks, with first exponent m − 1 m-1 m − 1 and all other exponents zero.
Write g = log ( A i / λ ) g=\log(A_i/\lambda) g = log ( A i / λ ) , and let S l S_l S l be the frozen set left after l l l clearings, so S 0 = S S_0=S S 0 = S . In initial slot coordinates, the pulled-back vector using u 0 u^0 u 0 approaches
ξ = u 0 ( x ) − log ( x i / a ) e i − g e j 1 − ∑ l = 1 d − 1 ( D S l − 1 − D S l ) e j l . (8) \xi=u^0(x)-\log(x_i/a)e_i-ge_{j_1}-\sum_{l=1}^{d-1}(D_{S_{l-1}}-D_{S_l})e_{j_l}. \tag*{(8)} ξ = u 0 ( x ) − log ( x i / a ) e i − g e j 1 − l = 1 ∑ d − 1 ( D S l − 1 − D S l ) e j l . (8)
Here is the computation. In the slot convention, the active move has matrix I + e i ( 1 − e i ) T I+e_i(1-e_i)^{\mathsf T} I + e i ( 1 − e i ) T . The total of the frozen normalized logs is log ( C P i ) = log λ + g + D S \log(CP_i)=\log\lambda+g+D_S log ( C P i ) = log λ + g + D S . Since log b m = m log λ + log a + O ( λ − m ) \log b_m=m\log\lambda+\log a+O(\lambda^{-m}) log b m = m log λ + log a + O ( λ − m ) , before the first clearing the pulled-back vector equals u 0 ( x ) − log ( x i / a ) e i − m ( g + D S ) e i + O ( λ − m ) u^0(x)-\log(x_i/a)e_i-m(g+D_S)e_i+O(\lambda^{-m}) u 0 ( x ) − log ( x i / a ) e i − m ( g + D S ) e i + O ( λ − m ) . The raw defect at that time is log ( C P i / b m + 1 ) = g + D S + O ( λ − m ) \log(CP_i/b_{m+1})=g+D_S+O(\lambda^{-m}) log ( C P i / b m + 1 ) = g + D S + O ( λ − m ) . When the first clearing acts, the inverse of the previous matrix product sends its error direction to e j 1 − m e i e_{j_1}-me_i e j 1 − m e i . This cancels the linear term in m m m . For clearing l ≥ 2 l\geq2 l ≥ 2 , the newest inverse subtracts e j l − 1 e_{j_{l-1}} e j l − 1 from e j l e_{j_l} e j l . All earlier inverses preserve that difference because its sum is zero and its support excludes their slots. The raw defect before this clearing is D S l − 1 + O ( 1 / b m + X / b m 2 ) D_{S_{l-1}}+O(1/b_m+X/b_m^2) D S l − 1 + O ( 1/ b m + X / b m 2 ) . Indeed the current maximum arose from multiplying the other entries by E S l − 1 E_{S_{l-1}} E S l − 1 with a relative error of that size: the large reciprocal terms cost O ( 1 / b m ) O(1/b_m) O ( 1/ b m ) , the removed entry was at most X X X , and the product includes both large active entries. Summing the error directions telescopes to (8) . The inverse norm for the whole prescribed word is O ( m + 1 ) O(m+1) O ( m + 1 ) , so the finite error in this computation is
O ( ( m + 1 ) ( λ − m + X λ − 2 m ) ) . O\bigl((m+1)(\lambda^{-m}+X\lambda^{-2m})\bigr). O ( ( m + 1 ) ( λ − m + X λ − 2 m ) ) .
After the clearings the minimum is at least b m ≥ λ m / 4 b_m\geq\lambda^m/4 b m ≥ λ m /4 . By (7) , the random continuation adds O ( ( m + 1 ) λ − m ) O((m+1)\lambda^{-m}) O (( m + 1 ) λ − m ) to the pulled-back error except with conditional probability O ( λ − ν m ) O(\lambda^{-\nu m}) O ( λ − ν m ) . Both error estimates divided by X − 2 X^{-2} X − 2 tend to zero uniformly, using X ≪ λ 2 X\ll\lambda^2 X ≪ λ 2 and the fixed lower bound on λ > 1 \lambda>1 λ > 1 .
For two orders that interchange the first two slots j , j ′ j,j' j , j ′ , subtracting (8) gives e j ′ − e j e_{j'}-e_j e j ′ − e j times
g + log ( E S + k / x j ) ( E S + k / x j ′ ) E S ( E S + k / x j + k / x j ′ ) . g+\log\frac{(E_S+k/x_j)(E_S+k/x_{j'})}{E_S(E_S+k/x_j+k/x_{j'})}. g + log E S ( E S + k / x j + k / x j ′ ) ( E S + k / x j ) ( E S + k / x j ′ ) .
The logarithm is nonnegative, and g = log ( 1 + λ − 2 ) ≥ c A i − 2 ≥ c ′ X − 2 g=\log(1+\lambda^{-2})\geq cA_i^{-2}\geq c'X^{-2} g = log ( 1 + λ − 2 ) ≥ c A i − 2 ≥ c ′ X − 2 . For a vector v v v , let m ( v ) m(v) m ( v ) be the largest absolute pairing with the finitely many candidates (8) , ranging over all i < d i<d i < d and all orders. For any j , j ′ j,j' j , j ′ not equal to some i < d i<d i < d , the difference of the corresponding coordinates of v v v is O ( X 2 m ( v ) ) O(X^2m(v)) O ( X 2 m ( v )) . These edges form a connected graph on the slots: with d ≥ 3 d\geq3 d ≥ 3 , the stars through the slot d d d obtained using the other available omitted indices suffice. All coordinates therefore differ from their average by O ( X 2 m ( v ) ) O(X^2m(v)) O ( X 2 m ( v )) . Each candidate has norm O ( 1 + log X ) O(1+\log X) O ( 1 + log X ) and coordinate sum log ( λ a ) + log s ≫ 1 + log X \log(\lambda a)+\log s\gg1+\log X log ( λa ) + log s ≫ 1 + log X . The latter follows from X = q + λ a + λ − 1 b X=q+\lambda a+\lambda^{-1}b X = q + λa + λ − 1 b , q < 1 / 2 q<1/2 q < 1/2 , and b ≤ a b\leq a b ≤ a . Pairing with any one candidate now bounds the average by O ( X 2 m ( v ) ) O(X^2m(v)) O ( X 2 m ( v )) as well. Thus m ( v ) ≥ c X − 2 ∥ v ∥ m(v)\geq cX^{-2}\lVert v\rVert m ( v ) ≥ c X − 2 ∥ v ∥ .
Lemma 12. For every 0 < ϵ < 1 / 4 0<\epsilon<1/4 0 < ϵ < 1/4 , there is B ϵ ≤ exp ( C 4 [ log ( 2 / ϵ ) ] β + 2 ) B_\epsilon\leq\exp(C_4[\log(2/\epsilon)]^{\beta+2}) B ϵ ≤ exp ( C 4 [ log ( 2/ ϵ ) ] β + 2 ) such that, uniformly in the nonroot seed x x x , the law satisfying (4) , and v ≠ 0 v\ne0 v = 0 ,
Pr ( ∣ v ⋅ Λ x ∣ ≤ X − B ϵ ∥ v ∥ ) ≤ ϵ . \Pr\bigl(|v\cdot\Lambda_x|\leq X^{-B_\epsilon}\lVert v\rVert\bigr)\leq\epsilon. Pr ( ∣ v ⋅ Λ x ∣ ≤ X − B ϵ ∥ v ∥ ) ≤ ϵ .
Proof. Choose m = O ( log ( 2 / ϵ ) ) m=O(\log(2/\epsilon)) m = O ( log ( 2/ ϵ )) sufficiently large. A candidate for which the pairing is maximal specifies a cylinder of d d d blocks. Except on a conditional set of probability at most ϵ / 4 \epsilon/4 ϵ /4 , the pairing there is at least c X − 2 ∥ v ∥ cX^{-2}\lVert v\rVert c X − 2 ∥ v ∥ by the error estimates. By (4) its probability is at least c ′ ( m + 1 ) − β c'(m+1)^{-\beta} c ′ ( m + 1 ) − β . Remove that cylinder, and repeat the construction at every surviving prefix of the next depth divisible by d d d , using the transported normal M p − T v M_p^{-T}v M p − T v . After R = O ( [ log ( 2 / ϵ ) ] β + 1 ) R=O([\log(2/\epsilon)]^{\beta+1}) R = O ([ log ( 2/ ϵ ) ] β + 1 ) rounds the remaining probability is at most ϵ / 4 \epsilon/4 ϵ /4 . The selected cylinders are disjoint, so their bad conditional fractions total at most ϵ / 4 \epsilon/4 ϵ /4 . Choose a cutoff J J J with log ( J + 1 ) = O ( log ( 2 / ϵ ) ) \log(J+1)=O(\log(2/\epsilon)) log ( J + 1 ) = O ( log ( 2/ ϵ )) such that the probability of any run beyond J J J in the first d R dR d R blocks is at most ϵ / 4 \epsilon/4 ϵ /4 . This follows directly by summing the transition tails. At every selected prefix obeying the cutoff, ∥ M p ∥ \lVert M_p\rVert ∥ M p ∥ is at most [ C 2 ( J + 1 ) ] d R [C_2(J+1)]^{dR} [ C 2 ( J + 1 ) ] d R and the log of the current maximum is at most a constant times [ C 2 ( J + 1 ) ] d R ( 1 + log X ) [C_2(J+1)]^{dR}(1+\log X) [ C 2 ( J + 1 ) ] d R ( 1 + log X ) , by iterating Vieta’s upper bound, or the log sandwich. The transported normal has norm at least ∥ v ∥ / ∥ M p ∥ \lVert v\rVert/\lVert M_p\rVert ∥ v ∥ / ∥ M p ∥ . Thus (6) gives the claimed threshold on choosing B ϵ B_\epsilon B ϵ to dominate a fixed multiple of [ C 2 ( J + 1 ) ] d R [C_2(J+1)]^{dR} [ C 2 ( J + 1 ) ] d R . The three exceptional probabilities sum to at most 3 ϵ / 4 3\epsilon/4 3 ϵ /4 .
Finite prefix partitions
Fix a > 0 a>0 a > 0 and a requested exponent A 0 > 0 A_0>0 A 0 > 0 . For a large normal cutoff M M M put K = ( log M ) a K=(\log M)^a K = ( log M ) a and z = log log M z=\log\log M z = log log M . At depth q 0 = ⌈ C 0 z ⌉ q_0=\lceil C_0z\rceil q 0 = ⌈ C 0 z ⌉ , take C 0 C_0 C 0 sufficiently large in terms of a , n , k , A 0 a,n,k,A_0 a , n , k , A 0 and the law bounds. For estimates on the probability of finite events, use the reference event that the run at position l l l satisfies A l + 1 ≤ K exp ( l ) A_l+1\leq K\exp(l) A l + 1 ≤ K exp ( l ) for all l l l , and that there is a complete block in the last half of each depth q ≥ q 0 q\geq q_0 q ≥ q 0 . Its complementary probability is
O ( K 1 − β + e − c q 0 ) O\bigl(K^{1-\beta}+e^{-cq_0}\bigr) O ( K 1 − β + e − c q 0 )
by summing the tail and complete-block failure estimates. The accumulated matrix and inverse norms on this event are bounded by exp ( O ( q log ( K + 2 ) + q 2 ) ) \exp(O(q\log(K+2)+q^2)) exp ( O ( q log ( K + 2 ) + q 2 )) . For a small fixed c 1 > 0 c_1>0 c 1 > 0 put e q = exp ( − c 1 φ q / 2 ) e_q=\exp(-c_1\varphi^{q/2}) e q = exp ( − c 1 φ q /2 ) . Since φ q 0 / 2 \varphi^{q_0/2} φ q 0 /2 dominates q 0 log ( K + 2 ) + q 0 2 q_0\log(K+2)+q_0^2 q 0 log ( K + 2 ) + q 0 2 when C 0 C_0 C 0 is large, the bound on pulled-back errors proves
∥ Λ x − λ p ∥ ≤ e q \lVert\Lambda_x-\lambda_p\rVert\le e_q ∥ Λ x − λ p ∥ ≤ e q
on the reference event for the depth-q q q prefix p p p , simultaneously for q ≥ q 0 q\ge q_0 q ≥ q 0 . Independently of this reference event, every finite prefix of depth q ≥ q 0 q\ge q_0 q ≥ q 0 with runs at most K K K and a complete block in its last half has the all-tail error (5) with coefficient at most e q e_q e q .
For the finite construction, keep only prefixes with runs at most K K K and a complete block in the last half of every tested depth. For any such prefix at depth q q q the matrix and inverse norms are at most R ( q ) = [ C 2 ( K + 2 ) ] q R(q)=[C_2(K+2)]^q R ( q ) = [ C 2 ( K + 2 ) ] q and log X p ≤ H ( q ) \log X_p\le H(q) log X p ≤ H ( q ) , where H ( q ) H(q) H ( q ) is a constant times R ( q ) R(q) R ( q ) by the log recurrence for the fixed starting seed. At depth q 0 q_0 q 0 retain as candidates the integer normals b b b with 0 < ∥ b ∥ ≤ M 0<\lVert b\rVert\le M 0 < ∥ b ∥ ≤ M and ∣ λ p ⋅ b ∣ ≤ 10 M e q 0 |\lambda_p\cdot b|\le10Me_{q_0} ∣ λ p ⋅ b ∣ ≤ 10 M e q 0 . Their span has dimension at most d − 1 d-1 d − 1 . In fact, d d d independent candidates form an integer column matrix of determinant of absolute value at least one. Its cofactors give ∥ λ p ∥ = O ( M d e q 0 ) \lVert\lambda_p\rVert=O(M^d e_{q_0}) ∥ λ p ∥ = O ( M d e q 0 ) , whereas ∥ λ p ∥ ≥ ∥ u ( x p ) ∥ / R ( q 0 ) ≫ R ( q 0 ) − 1 \lVert\lambda_p\rVert\ge\lVert u(x_p)\rVert/R(q_0)\gg R(q_0)^{-1} ∥ λ p ∥ ≥ ∥ u ( x p )∥ / R ( q 0 ) ≫ R ( q 0 ) − 1 . These bounds contradict each other for large M M M on increasing C 0 C_0 C 0 .
Fix 0 < ϵ < 1 / 4 0<\epsilon<1/4 0 < ϵ < 1/4 , and use B ϵ B_\epsilon B ϵ from Lemma 12 . At a retained prefix of depth q s q_s q s with nonempty candidate set, designate one candidate b 0 b_0 b 0 . By (6) and Lemma 12 , the conditional probability that
∣ Λ x ⋅ b 0 ∣ ≤ σ s ∥ b 0 ∥ , σ s = exp ( − B ϵ H ( q s ) ) / R ( q s ) , |\Lambda_x\cdot b_0|\le\sigma_s\lVert b_0\rVert,\qquad\sigma_s=\exp(-B_\epsilon H(q_s))/R(q_s), ∣ Λ x ⋅ b 0 ∣ ≤ σ s ∥ b 0 ∥ , σ s = exp ( − B ϵ H ( q s )) / R ( q s ) ,
is at most ϵ \epsilon ϵ . Indeed ∥ M p − T b 0 ∥ ≥ ∥ b 0 ∥ / R ( q s ) \lVert M_p^{-T}b_0\rVert\ge\lVert b_0\rVert/R(q_s) ∥ M p − T b 0 ∥ ≥ ∥ b 0 ∥ / R ( q s ) . Refine every current prefix to the least common depth q s + 1 > q s q_{s+1}>q_s q s + 1 > q s with e q s + 1 ≤ σ s / ( C 5 M d ) e_{q_{s+1}}\le\sigma_s/(C_5M^d) e q s + 1 ≤ σ s / ( C 5 M d ) , for a sufficiently large fixed C 5 C_5 C 5 . For each child at that depth require that its center differ from its center at each previous tested depth q t q_t q t by at most 2 e q t 2e_{q_t} 2 e q t , and, when b 0 b_0 b 0 was designated, require its pairing to exceed σ s ∥ b 0 ∥ / 2 \sigma_s\lVert b_0\rVert/2 σ s ∥ b 0 ∥ /2 in absolute value. On the reference event the center comparisons always pass. On that same event the last test fails on a subset of the conditional exceptional event of size at most ϵ \epsilon ϵ . Summation over parents costs at most ϵ \epsilon ϵ , since their cylinders are disjoint.
The child’s candidate set is the intersection of the parent’s candidates with the set pairing with its center by at most 10 M e q s + 1 10Me_{q_{s+1}} 10 M e q s + 1 . If the rank is still the parent’s positive rank r r r , write b 0 b_0 b 0 as a linear combination of r r r independent child candidates. By choosing an invertible integer coordinate minor, Cramer’s rule bounds each coefficient by O ( ∥ b 0 ∥ M r − 1 ) O(\lVert b_0\rVert M^{r-1}) O (∥ b 0 ∥ M r − 1 ) . Thus the child’s pairing with b 0 b_0 b 0 is at most O ( ∥ b 0 ∥ M r e q s + 1 ) O(\lVert b_0\rVert M^r e_{q_{s+1}}) O (∥ b 0 ∥ M r e q s + 1 ) , smaller than σ s ∥ b 0 ∥ / 2 \sigma_s\lVert b_0\rVert/2 σ s ∥ b 0 ∥ /2 by the choice of C 5 C_5 C 5 . This contradicts retention. After d − 1 d-1 d − 1 refinements all candidate sets are empty.
Write Q = q d − 1 Q=q_{d-1} Q = q d − 1 . If a normal of length at most M M M paired with the depth-Q Q Q center by at most 5 M e Q 5Me_Q 5 M e Q , its pairing with each earlier tested center would be at most 5 M e Q + 2 M e q t ≤ 7 M e q t 5Me_Q+2Me_{q_t}\le7Me_{q_t} 5 M e Q + 2 M e q t ≤ 7 M e q t . It would have survived every candidate intersection. Thus all pairings of nonzero such normals at depth Q Q Q exceed 5 M e Q 5Me_Q 5 M e Q . Refine once more to the least depth q ∗ > Q q_*>Q q ∗ > Q with e q ∗ ≤ 2 M e Q / ( 100 M A 0 ) e_{q_*}\le2Me_Q/(100M^{A_0}) e q ∗ ≤ 2 M e Q / ( 100 M A 0 ) and keep the finite tests for runs, complete blocks, and center comparisons, including the comparison with depth Q Q Q . Then for every retained prefix p p p and every finite descendant,
∣ λ p ⋅ b ∣ > τ ( 0 < ∥ b ∥ ≤ M , b ∈ Z d ) , ∣ h ( x p W ) − λ p ⋅ v p W ∣ ≤ δ ∥ v p W ∥ , δ ≤ τ / ( 100 M A 0 ) , (9) \begin{aligned}
|\lambda_p\cdot b|&>\tau&&(0<\lVert b\rVert\le M,\ b\in\mathbb{Z}^d),\\
|h(x_{pW})-\lambda_p\cdot v_{pW}|&\le\delta\lVert v_{pW}\rVert, &&\delta\le\tau/(100M^{A_0}), \tag*{(9)}
\end{aligned} ∣ λ p ⋅ b ∣ ∣ h ( x p W ) − λ p ⋅ v p W ∣ > τ ≤ δ ∥ v p W ∥ , ( 0 < ∥ b ∥ ≤ M , b ∈ Z d ) , δ ≤ τ / ( 100 M A 0 ) , (9)
where τ = 2 M e Q \tau=2Me_Q τ = 2 M e Q and δ = e q ∗ \delta=e_{q_*} δ = e q ∗ .
Taking logarithms twice in the minimal depth inequality gives
q s + 1 ≪ log ( 2 + B ϵ ) + q s log ( K + 2 ) + log log M . q_{s+1}\ll\log(2+B_\epsilon)+q_s\log(K+2)+\log\log M. q s + 1 ≪ log ( 2 + B ϵ ) + q s log ( K + 2 ) + log log M .
The last refinement can be made at Q + 1 Q+1 Q + 1 for large M M M , since e Q + 1 / e Q e_{Q+1}/e_Q e Q + 1 / e Q is smaller than any prescribed power of M − 1 M^{-1} M − 1 . Therefore q ∗ ≪ ( z + log ( 2 + B ϵ ) ) z d − 1 q_*\ll(z+\log(2+B_\epsilon))z^{d-1} q ∗ ≪ ( z + log ( 2 + B ϵ )) z d − 1 , and the log of the number of retained prefixes is at most a constant times ( z + log ( 2 + B ϵ ) ) z d (z+\log(2+B_\epsilon))z^d ( z + log ( 2 + B ϵ )) z d , by counting at most ( d − 1 ) ( [ K ] + 1 ) (d-1)([K]+1) ( d − 1 ) ([ K ] + 1 ) choices at each depth. The exceptional probability is at most
( d − 1 ) ϵ + O ( q ∗ K 1 − β + e − c q 0 ) . (d-1)\epsilon+O(q_*K^{1-\beta}+e^{-cq_0}). ( d − 1 ) ϵ + O ( q ∗ K 1 − β + e − c q 0 ) .
This charges the reference failure once, the run failures by their union bound, and the selected normal failures once per depth. The retained partition uses only finite prefixes and (9) holds for every tail.
Transfer to height counts
Let L = log B L=\log B L = log B for a maximum cutoff B B B . The counting estimates give a total comparable to L β L^\beta L β , and the number of words through an event at depth q q q is at most a constant times L β L^\beta L β times its Gibbs probability, uniformly in q q q . Words of depth below q q q are bounded in count by O ( L s 0 C s 0 q ) O(L^{s_0}C_{s_0}^{q}) O ( L s 0 C s 0 q ) for some fixed 1 < s 0 < β 1<s_0<\beta 1 < s 0 < β and constant C s 0 C_{s_0} C s 0 . In particular for q = o ( log L ) q=o(\log L) q = o ( log L ) their normalized count is at most O ( L − η 0 ) O(L^{-\eta_0}) O ( L − η 0 ) for some η 0 > 0 \eta_0>0 η 0 > 0 . These statements also hold for each of the finitely many initial seeds obtained on imposing a fixed cutoff on the initial cusp run. The discarded proportion for that initial cutoff tends to zero as the cutoff increases. If a fixed initial word has matrix M 0 M_0 M 0 , a local label v v v becomes M 0 T v M_0^{\mathsf T}v M 0 T v and a local center λ \lambda λ becomes M 0 − 1 λ M_0^{-1}\lambda M 0 − 1 λ . A global integer normal b b b of length at most M M M gives the local integer normal M 0 − T b M_0^{-\mathsf T}b M 0 − T b of length at most ∥ M 0 − 1 ∥ M \lVert M_0^{-1}\rVert M ∥ M 0 − 1 ∥ M , since M 0 M_0 M 0 is unimodular. The flatness coefficient is multiplied by at most ∥ M 0 − 1 ∥ \lVert M_0^{-1}\rVert ∥ M 0 − 1 ∥ . A fixed larger local cutoff and fixed stronger flatness ratio therefore give the same assertions in the global labels. Take the maximum of the height and matrix bounds over the finitely many initial seeds before choosing any of the tested depths. All constructions then have the same tested depths and hence common separation and flatness thresholds.
For M M M a fixed multiple of L d + 1 L^{d+1} L d + 1 and ϵ \epsilon ϵ fixed, the depth is a fixed power of log log L \log\log L log log L and the number of parts is L o ( 1 ) L^{o(1)} L o ( 1 ) . The normalized count discarded after the initial cusp cutoff is O ( ϵ ) + o ( 1 ) O(\epsilon)+o(1) O ( ϵ ) + o ( 1 ) . For integer bands j ≥ 2 j\ge2 j ≥ 2 , take M = exp ( κ j ) M=\exp(\kappa j) M = exp ( κj ) and ϵ = ( j + 1 ) − 2 \epsilon=(j+1)^{-2} ϵ = ( j + 1 ) − 2 , with fixed κ > 0 \kappa>0 κ > 0 . Now log ( 2 + B ϵ ) = O ( ( log ( j + 1 ) ) β + 2 ) \log(2+B_\epsilon)=O((\log(j+1))^{\beta+2}) log ( 2 + B ϵ ) = O (( log ( j + 1 ) ) β + 2 ) , so the depth and log of the number of parts are fixed powers of log ( j + 1 ) \log(j+1) log ( j + 1 ) , with the number of parts exp ( o ( j ) ) \exp(o(j)) exp ( o ( j )) . Choose a ( β − 1 ) > 4 a(\beta-1)>4 a ( β − 1 ) > 4 and enlarge C 0 C_0 C 0 so the complete-block error is O ( j − 4 ) O(j^{-4}) O ( j − 4 ) . For all sufficiently large j j j the exceptional symbolic mass is O ( ( j + 1 ) − 2 ) O((j+1)^{-2}) O (( j + 1 ) − 2 ) . Uniformly for j j j up to any fixed multiple of log L \log L log L the depths are o ( log L ) o(\log L) o ( log L ) . The normalized integer loss in band j j j is therefore O ( ( j + 1 ) − 2 + L − η 0 ) O((j+1)^{-2}+L^{-\eta_0}) O (( j + 1 ) − 2 + L − η 0 ) , with the separation and flatness in (9) .
Termination of rational overlaps
Fix an integer r ≥ 3 r\ge3 r ≥ 3 . All vectors are columns except covectors, which are rows. Let 1 \mathbf{1} 1 denote the all-one column, e i e_i e i the i i i -th standard column, J = 11 T J=\mathbf{1}\mathbf{1}^{\mathsf T} J = 1 1 T , and
B i = I + e i ( 1 − e i ) T ( 1 ≤ i ≤ r ) . B_i=I+e_i(\mathbf{1}-e_i)^{\mathsf T}\qquad(1\le i\le r). B i = I + e i ( 1 − e i ) T ( 1 ≤ i ≤ r ) .
For a finite word w = i 1 ⋯ i m w=i_1\cdots i_m w = i 1 ⋯ i m , write B w = B i 1 ⋯ B i m B_w=B_{i_1}\cdots B_{i_m} B w = B i 1 ⋯ B i m , with the identity for the empty word. We use Euclidean vector, covector, and induced operator norms unless otherwise indicated. The simplex Δ r \Delta_r Δ r consists of nonnegative vectors with coordinate sum one. We represent a nonnegative projective direction by its representative in Δ r \Delta_r Δ r . The Rauzy gasket R \mathcal{R} R is the intersection, over m ≥ 0 m\ge0 m ≥ 0 , of the unions of the projective simplices B w Δ r B_w\Delta_r B w Δ r for all words of length m m m .
The law of the input word
The ordered state space is the part of Δ r \Delta_r Δ r where x 1 ≤ ⋯ ≤ x r x_1\le\cdots\le x_r x 1 ≤ ⋯ ≤ x r . Let Q j Q_j Q j be the permutation matrix moving position j j j to the end and preserving the order of the others. The accelerated letter ( a , j ) (a,j) ( a , j ) , with a ≥ 1 a\ge1 a ≥ 1 and 1 ≤ j ≤ r 1\le j\le r 1 ≤ j ≤ r , has matrix γ a , j = Q j B j a = B r a Q j \gamma_{a,j}=Q_jB_j^a=B_r^aQ_j γ a , j = Q j B j a = B r a Q j and projective map f a , j f_{a,j} f a , j . Let h h h be the positive C 1 C^1 C 1 eigenfunction for the critical exponent β > 1 \beta>1 β > 1 of the Gamburd–Magee–Ronan operator, normalized so that its transition probabilities are
p a , j ( x ) = ( 1 + a ( 1 − x j ) ) − β h ( f a , j ( x ) ) h ( x ) . p_{a,j}(x)=(1+a(1-x_j))^{-\beta}\frac{h(f_{a,j}(x))}{h(x)}. p a , j ( x ) = ( 1 + a ( 1 − x j ) ) − β h ( x ) h ( f a , j ( x )) .
We use the existence of this eigenfunction and the uniform exponential shrinking of ordered compositions from [15 ] , Theorems 10, 13, and 39 and Proposition 43. Thus there are D > 0 D>0 D > 0 and 0 < ρ < 1 0<\rho<1 0 < ρ < 1 such that each ordered composition of m m m letters has image diameter at most D ρ m D\rho^m D ρ m . The probabilities sum to one. Their logarithms are uniformly Lipschitz: the logarithmic derivative of 1 + a ( 1 − x j ) 1+a(1-x_j) 1 + a ( 1 − x j ) is bounded because x j ≤ 1 / 2 x_j\le1/2 x j ≤ 1/2 , and the projective maps have uniformly bounded derivatives on the ordered simplex. The latter follows by differentiating B j a x / ( 1 + a ( 1 − x j ) ) B_j^a x/(1+a(1-x_j)) B j a x / ( 1 + a ( 1 − x j )) , whose numerator and derivative are O r ( 1 + a ) O_r(1+a) O r ( 1 + a ) . Also p a , j ( x ) ≤ C r a − β p_{a,j}(x)\le C_r a^{-\beta} p a , j ( x ) ≤ C r a − β , and max ( ∥ γ a , j ∥ , ∥ γ a , j − 1 ∥ ) = O r ( 1 + a ) \max(\lVert\gamma_{a,j}\rVert,\lVert\gamma_{a,j}^{-1}\rVert)=O_r(1+a) max (∥ γ a , j ∥ , ∥ γ a , j − 1 ∥) = O r ( 1 + a ) . Consequently the cost
ℓ ( a , j ) = 1 + log max ( ∥ γ a , j ∥ , ∥ γ a , j − 1 ∥ ) \ell(a,j)=1+\log\max(\lVert\gamma_{a,j}\rVert,\lVert\gamma_{a,j}^{-1}\rVert) ℓ ( a , j ) = 1 + log max (∥ γ a , j ∥ , ∥ γ a , j − 1 ∥)
has a uniform conditional exponential moment. Throughout, C r C_r C r denotes a positive constant depending only on r r r , whose value can change.
Write P t P_t P t for the permutation taking the actual coordinate order to the ordered positions after t t t runs. An actual run uses the actual index i = P t − 1 ( j ) i=P_t^{-1}(j) i = P t − 1 ( j ) for the exponent a a a , then changes P t P_t P t to Q j P t Q_jP_t Q j P t . Thus the next index can be any index other than the one in the final position. If C m C_m C m is the ordered-in-time product of the actual B B B -matrices after m m m runs and L m L_m L m is the corresponding ordered-in-time product of γ a , j \gamma_{a,j} γ a , j , multiplication and transposition give
C m = P 0 − 1 ( J − I ) − 1 L m ( J − I ) P m . C_m=P_0^{-1}(J-I)^{-1}L_m(J-I)P_m. C m = P 0 − 1 ( J − I ) − 1 L m ( J − I ) P m .
Indeed, the forward product of the γ a , j \gamma_{a,j} γ a , j , latest factor on the left, is P m P_m P m times the corresponding latest-first product of actual B B B -matrices times P 0 − 1 P_0^{-1} P 0 − 1 . Its transpose reverses the order and turns B i B_i B i into ( J − I ) B i ( J − I ) − 1 (J-I)B_i(J-I)^{-1} ( J − I ) B i ( J − I ) − 1 . This also proves the formula for continuations from every current state.
We establish a probabilistic input needed below. For a chronological suffix w w w of m m m ordered letters define f w f_w f w by applying them in chronological order and set
q m ( b ∣ w ) = inf x p b ( f w ( x ) ) , α m = inf ∣ w ∣ = m ∑ b q m ( b ∣ w ) . q_m(b\mid w)=\inf_x p_b(f_w(x)),\qquad\alpha_m=\inf_{|w|=m}\sum_b q_m(b\mid w). q m ( b ∣ w ) = x inf p b ( f w ( x )) , α m = ∣ w ∣ = m inf b ∑ q m ( b ∣ w ) .
At depth zero take f w = I f_w=I f w = I . A longer suffix gives a smaller possible state set, so the envelopes increase when another letter is supplied on the left. In particular α m \alpha_m α m is nondecreasing. Uniform logarithmic distortion gives α m ≥ e − L D ρ m \alpha_m\ge e^{-LD\rho^m} α m ≥ e − L D ρ m , where L L L is a common Lipschitz constant. For each letter partition a uniform random variable’s interval into the successive envelope increments and the residual at the current finite history. The ordering of the intervals is by depth and then by a fixed enumeration of letters. Their lengths telescope to the original probabilities. If the uniform variable is smaller than α m \alpha_m α m , the selected letter depends only on the last m m m letters.
Let U 0 , U 1 , … U_0,U_1,\ldots U 0 , U 1 , … be the independent uniforms used for this construction. Call t t t a cut when U t + s < α s U_{t+s}<\alpha_s U t + s < α s for every s ≥ 0 s\ge0 s ≥ 0 . Its probability is b = ∏ m α m > 0 b=\prod_m\alpha_m>0 b = ∏ m α m > 0 . On a cut at t t t , the condition that an earlier j < t j<t j < t be a cut reduces to its uniform restrictions before t t t , because α m \alpha_m α m is nondecreasing. Therefore the event of the first cut at t t t factors into an event in the uniforms before t t t and the event of a cut at t t t . Across consecutive cut intervals the same factorization shows that the cut-to-cut marked words are independent and identically distributed under conditioning on a cut at their initial time. The words are marks of the intervals because the update within each interval depends on no earlier letters. The initial word is independent of the sequence of marked words, whose law is independent of the initial state.
Here is an exponential tail justification. Under the cut law, the probability of another cut at time m m m is u m = ∏ j = 0 m − 1 α j u_m=\prod_{j=0}^{m-1}\alpha_j u m = ∏ j = 0 m − 1 α j , with u 0 = 1 u_0=1 u 0 = 1 . For m ≥ 1 m\ge1 m ≥ 1 put f m = u m − 1 − u m f_m=u_{m-1}-u_m f m = u m − 1 − u m . Its generating function F ( z ) = ∑ m ≥ 1 f m z m F(z)=\sum_{m\ge1}f_mz^m F ( z ) = ∑ m ≥ 1 f m z m has radius of convergence greater than one and F ( 1 ) = 1 − b < 1 F(1)=1-b<1 F ( 1 ) = 1 − b < 1 . The renewal generating function ∑ m ≥ 0 u m z m \sum_{m\ge0}u_mz^m ∑ m ≥ 0 u m z m equals ( 1 − F ( z ) ) / ( 1 − z ) (1-F(z))/(1-z) ( 1 − F ( z )) / ( 1 − z ) . Its gap distribution therefore has generating function 1 − ( 1 − z ) / ( 1 − F ( z ) ) 1-(1-z)/(1-F(z)) 1 − ( 1 − z ) / ( 1 − F ( z )) , analytic on a disk of radius greater than one. The cut set may also be constructed with uniforms indexed by all integers. It is a stationary renewal set, of intensity b b b , and the first forward waiting time has the residual gap tail, which is exponential. These identities are also the renewal construction of [22 ] , Corollary 4.18 and §8]. The log-cost of the initial word and an ordinary marked word has an exponential tail. To prove this, split according to whether the word is longer than [ δ s ] [\delta s] [ δ s ] , for a small fixed δ > 0 \delta>0 δ > 0 , and on the other event use the exponential moment of the accumulated costs of that many letters and Markov’s inequality at cost s s s . The Palm conditioning costs at most 1 / b 1/b 1/ b . The iteration of the conditional exponential moments is at a deterministic time. No cut is used as a stopping time for the input filtration.
Let μ \mu μ be the law of the products of transposed ordered matrices of one marked word. Every ordered branch occurs in this support: fixing the level-zero interval for a branch at time zero and a cut at time one has conditional probability q 0 ( b ) > 0 q_0(b)>0 q 0 ( b ) > 0 given a cut at zero. The quotients γ 2 , j γ 1 , j − 1 = B r \gamma_{2,j}\gamma_{1,j}^{-1}=B_r γ 2 , j γ 1 , j − 1 = B r recover B r B_r B r , and then each Q j Q_j Q j . The first and last Q j Q_j Q j generate all permutations, so conjugation gives all B i B_i B i . For clarity, the group generated by all B i B_i B i is Zariski dense in S L r \mathrm{SL}_r SL r . To see this by transposing, let u i = 1 − e i u_i=1-e_i u i = 1 − e i , M i j = u i e j T M_{ij}=u_i e_j^{\mathsf{T}} M ij = u i e j T , and N i = M i i N_i=M_{ii} N i = M ii . The powers of I + N i I+N_i I + N i give N i N_i N i in the Lie algebra, and
[ N i , N j ] = M i j − M j i , [ N k , [ N i , N j ] ] = M k j + M j k − M k i − M i k [N_i,N_j]=M_{ij}-M_{ji},\qquad[N_k,[N_i,N_j]]=M_{kj}+M_{jk}-M_{ki}-M_{ik} [ N i , N j ] = M ij − M j i , [ N k , [ N i , N j ]] = M k j + M j k − M k i − M ik
for distinct indices. Since J − I J-I J − I is invertible, the M i j M_{ij} M ij form a basis of matrices. These brackets, together with the N i N_i N i , span all trace-zero matrices: the second set spans the differences of symmetric off-diagonal pairs by connectivity of the graph of pairs sharing an index. This proves the claim. The transposed branch law has the same Zariski-density conclusion. The standard and second exterior representations are strongly irreducible because their restrictions to connected S L r \mathrm{SL}_r SL r are irreducible. A product using all actual indices is strictly positive, and supplies a proximal matrix in the standard representation after absorbing its final permutation by taking a repeated complete ordered pattern with trivial final permutation.
The projective stationary measure of μ \mu μ satisfies a uniform power bound on hyperplane strips. In applying [23 Proposition 2.56] , one can pass to the product at the first return of the determinant sign to + 1 +1 + 1 . The sign-return time has exponential tail, and its product has an exponential log-cost moment by the same length splitting argument. Its support generates the determinant-one kernel: a positive atom, a pair of negative atoms, and a pair of negative atoms enclosing a positive atom generate the index-two kernel by the usual two-coset rewriting. The stationary measure is unchanged, since successive returns group the same infinite independent products. The right-product limit under consideration exists: a strictly positive finite product recurrently contracts Hilbert distance, and the other nonnegative matrices are nonexpanding. The uniqueness of the stationary law is part of the strongly irreducible proximal theorem used in [23 ] . The original future-direction law is a mixture of pushforwards by the independent initial word, a starting permutation, and the fixed conjugacy above. For strip width s ∈ ( 0 , 1 ) s\in(0,1) s ∈ ( 0 , 1 ) , restrict the condition number of the initial matrix to have both norms at most s − 1 / 4 s^{-1/4} s − 1/4 . The strip then pulls back to width O r ( s 1 / 2 ) O_r(s^{1/2}) O r ( s 1/2 ) , and the exceptional cost is a positive power of s s s . This proves a bound C s c Cs^c C s c , with C , c > 0 C,c>0 C , c > 0 uniform over the actual current state and every hyperplane through zero.
We will also use log-norm estimates for actual deterministic run counts. Let λ 1 > λ 2 \lambda_1>\lambda_2 λ 1 > λ 2 be the two largest exponents of the marked block matrix law, and let t ˉ \bar t t ˉ be the expected block length. The largest exponent is simple by standard proximal and strong irreducibility. Set Λ i = λ i / t ˉ \Lambda_i=\lambda_i/\bar t Λ i = λ i / t ˉ for i = 1 , 2 i=1,2 i = 1 , 2 . Uniformly in the current state and every nonzero covector v v v ,
E log ∥ v C m ∥ ∥ v ∥ = m Λ 1 + o ( m ) , E log ∥ Λ 2 C m ∥ ≤ m ( Λ 1 + Λ 2 ) + o ( m ) . (10) \mathbb{E}\log\frac{\lVert vC_m\rVert}{\lVert v\rVert}=m\Lambda_1+o(m),\qquad\mathbb{E}\log\lVert\Lambda^2 C_m\| \le m(\Lambda_1+\Lambda_2)+o(m). \tag*{(10)} E log ∥ v ∥ ∥ v C m ∥ = m Λ 1 + o ( m ) , E log ∥ Λ 2 C m ∥ ≤ m ( Λ 1 + Λ 2 ) + o ( m ) . (10)
Indeed, [21 Theorem 3.1] gives exponential large deviations for the vector norm on the transposed standard representation and the operator norm on the exterior-square representation. The latter has top exponent λ 1 + λ 2 \lambda_1+\lambda_2 λ 1 + λ 2 by the singular value formula. Fix a small positive loss ϵ \epsilon ϵ . By the exponential length tail and Chernoff’s inequality, the number of full marked blocks in m m m runs lies within O ( ϵ m ) O(\epsilon m) O ( ϵ m ) of m / t ˉ m/\bar t m / t ˉ , except with exponentially small probability. Apply the large-deviation inequalities for every deterministic count in that interval and take their union. The initial and final partial costs exceed ϵ m \epsilon m ϵ m with exponentially small probability: the final cost is at most the largest cost of the first m + 1 m+1 m + 1 marked blocks. Condition on the independent initial word before using the uniform vector estimate. The conjugacy and the initial and final partial weights change logarithmic norms by only O ( ϵ m + 1 ) O(\epsilon m+1) O ( ϵ m + 1 ) . Finally the total raw log-cost has second moment O ( m 2 ) O(m^2) O ( m 2 ) , so Cauchy–Schwarz bounds the expectation on the exceptional event by o ( m ) o(m) o ( m ) . Letting ϵ \epsilon ϵ decrease proves (10) .
Cylinders and reduced matrices
The first projective simplex for letter i i i is the set whose i i i -th coordinate is at least 1 / 2 1/2 1/2 . Two distinct first simplices meet only at their edge midpoint. The projective map of B i B_i B i is x i ↦ 1 / ( 2 − x i ) x_i \mapsto1/(2-x_i) x i ↦ 1/ ( 2 − x i ) , x j ↦ x j / ( 2 − x i ) x_j \mapsto x_j/(2-x_i) x j ↦ x j / ( 2 − x i ) for j ≠ i j \ne i j = i . Its derivative on the simplex has ℓ 1 \ell^1 ℓ 1 -norm at most 1 / ( 2 − x i ) 1/(2-x_i) 1/ ( 2 − x i ) : it suffices to test the extremal tangent vectors ( e j − e k ) / 2 (e_j-e_k)/2 ( e j − e k ) /2 . For j , k ≠ i j,k \ne i j , k = i the ratio is 1 / ( 2 − x i ) 1/(2-x_i) 1/ ( 2 − x i ) ; for indices i , j i,j i , j it is ( 2 − x i − x j ) / ( 2 − x i ) 2 (2-x_i-x_j)/(2-x_i)^2 ( 2 − x i − x j ) / ( 2 − x i ) 2 . Hence the maps are nonexpanding, and inside a different first simplex the factor is at most 2 / 3 2/3 2/3 . A constant run of length a a a has diameter 2 / ( a + 1 ) 2/(a+1) 2/ ( a + 1 ) , by its simplex vertices. Thus cylinders shrink uniformly as raw word length grows, and their diameters decrease exponentially in run count. The gasket meets a first simplex in the corresponding image of the gasket. This follows from the first-level union and the shared midpoints, which are images of vertices from both cells. Iteration gives the analogous cylinder identity. The entire edge between any two vertices belongs to the gasket, since the two corresponding first maps split that edge into its two halves. Strictly positive points are dense in the gasket: each finite cylinder contains such a point by following it with a complete positive word.
We need the following classification. Suppose a nonzero nonnegative matrix acts projectively on every positive point of R \mathcal R R and maps it into R \mathcal R R . The map extends to every point with nonzero image by continuity. Each pair of nonzero column directions joins by a segment in the gasket. Any segment not contained in a first simplex crosses between two first simplices through their common midpoint. Since all coordinates are nonnegative, each coordinate zero at such an interior point vanishes on the entire segment. Thus the segment lies on the original supporting edge. Stripping common first simplices and using uniform cylinder shrinking shows that every nondegenerate segment in the gasket lies on an edge of some finite cylinder.
If a triple of noncollinear points has its three sides in the gasket, either the three points lie in one first simplex, they are three original vertices, or they are three pairwise contact midpoints. To verify this, associate to each point its set of one or two incident first simplices. If all pairs intersect but the total intersection is empty, the three sets must be { i , j } \{i,j\} { i , j } , { j , k } \{j,k\} { j , k } , { i , k } \{i,k\} { i , k } . Otherwise a pair with disjoint sets lies on an original edge. A nonvertex point on that edge cannot connect to a point off the edge in a different first simplex. A point off the edge connecting to both endpoints of the chosen pair would then have to be in both their first simplices, impossible off the edge. Thus both members of that pair are vertices; connecting an off-edge point to the two vertices now requires that it too be a vertex.
For rank at least three, strip common first simplices as long as possible. This means applying B i − 1 B_i^{-1} B i − 1 on the left, preserving nonnegativity and the gasket mapping by the cylinder identity. Uniform shrinking ensures that the stripping terminates. If the remaining column directions all have pairwise intersecting membership sets, three contact midpoints must occur, since the total intersection is empty. The relative interior of their triangle is in the first-level hole, whereas a positive point in the corresponding input three-coordinate gasket face maps into this relative interior. The gasket on a coordinate face is the gasket for its supported indices, directly from the first-level formula; such positive points exist there. Otherwise choose a disjoint-membership pair and a third direction off its line. The three directions are original vertices, and every other nonzero column must also point along a vertex by applying the same triangle fact with a noncollinear pair of these vertices. The multipliers of any three distinct coordinate images must agree. Indeed, if a ≤ b , c a \le b,c a ≤ b , c with at least one strict inequality, the point ( 1 / 2 , c / ( 2 ( b + c ) ) , b / ( 2 ( b + c ) ) ) (1/2,c/(2(b+c)),b/(2(b+c))) ( 1/2 , c / ( 2 ( b + c )) , b / ( 2 ( b + c ))) lies on an edge of the first simplex for coordinate one, and its image under diag ( a , b , c ) \operatorname{diag}(a,b,c) diag ( a , b , c ) lies in the hole since 2 b c > a ( b + c ) 2bc>a(b+c) 2 b c > a ( b + c ) . Thus all nonzero columns have a common multiplier. After dividing by it, duplicate columns e p e_p e p in positions a , d a,d a , d , together with columns e q , e s e_q,e_s e q , e s in positions b , c b,c b , c of distinct images, give the columns 3 e p , 3 e p + e q , 3 e p + e s 3e_p,3e_p+e_q,3e_p+e_s 3 e p , 3 e p + e q , 3 e p + e s in positions a , b , c a,b,c a , b , c after right multiplication by B a B d B_aB_d B a B d . On that face stripping B p 3 B_p^3 B p 3 contradicts diagonal rigidity. A zero column at d d d becomes a duplicate at d d d after right multiplication by B a B_a B a , where column a a a is e p e_p e p , and then left multiplication by B p − 1 B_p^{-1} B p − 1 . The classification now gives a scalar permutation preceded by the stripped word, hence full rank. At rank two the entire image is the segment joining two extreme column directions and is contained in a finite-cylinder edge. At rank one the image point belongs to R \mathcal{R} R .
For a nonnegative invertible matrix H H H with rational entries, an output letter is legal if B i − 1 H ≥ 0 B_i^{-1}H \ge0 B i − 1 H ≥ 0 entrywise. Two different letters cannot be legal simultaneously because every column would then belong to the intersection of two first cones, giving rank at most one. Full stripping terminates because each legal letter decreases the entry sum by at least the reciprocal of a fixed common denominator. A matrix with no legal letter is called reduced. If a reduced H H H is not a positive scalar permutation, no further finite input and output can make it one. In fact, the i i i -th column of H B i HB_i H B i is its unique componentwise least column: every other column is the sum of that column and a nonzero column of H H H . Thus an equality H B v = c B u P HB_v=cB_uP H B v = c B u P with a positive scalar c c c and a permutation P P P can be right-cancelled after moving P P P to the left of the input word by conjugation. The rightmost letters agree successively. The right side cannot run out first because a permutation has no componentwise least column. It follows that H H H was a scalar word-permutation; reducedness forces the word to be empty.
Starting at a nonnegative remainder H H H , at every run append the actual input on the right and strip all legal outputs on the left. Let H m H_m H m denote the remainders, and let E E E be the event that the initial matrix sends the future boundary direction into the gasket with positive orientation. Write p m p_m p m for the conditional probability of E E E at the current input time. The cylinder identity shows that this is the probability the current remainder sends the original, unconditioned future direction into the gasket. Thus p m → 1 p_m \to1 p m → 1 almost surely on E E E . If a nonterminal reduced remainder preserved an entire permitted first corner of the gasket, the classification applied to H B i HB_i H B i would give a scalar word-permutation, in contradiction with right cancellation. The allowed initial run index excludes only the last active index, and all run lengths at that allowed index, and all allowed continuations, have positive probability. Consequently an open hole inside a permitted corner gives an escaping finite cylinder of uniformly positive probability over the ordered state. Since bounded rational remainders with a fixed denominator form finite sets, nonterminal survival implies that their entry sums tend to infinity. Their determinants are fixed and nonzero, so normalized limits are singular. The same cylinder argument shows that along a subsequence with fixed finite ordering, every normalized limit preserves each allowed first corner. Apply the classification after right multiplication by an allowed B i B_i B i , which does not change rank or range. Such a limit has rank one with image point in the gasket, or rank two with range a finite-cylinder edge line.
Deterministic area estimates
For a nonnegative matrix H H H , let N ( H ) N(H) N ( H ) be its entry sum and A ( H ) A(H) A ( H ) the sum of the absolute values of its two-by-two minors. Put R ( H ) = A ( H ) / N ( H ) 2 R(H)=A(H)/N(H)^2 R ( H ) = A ( H ) / N ( H ) 2 and Q ( H ) = − log R ( H ) Q(H)=-\log R(H) Q ( H ) = − log R ( H ) for invertible H H H . The bound on each row wedge by the product of the row masses gives Q ( H ) ≥ log 2 Q(H) \ge\log2 Q ( H ) ≥ log 2 . For an invertible matrix C C C write K ( C ) = max ( 1 , ∥ C ∥ , ∥ C − 1 ∥ ) K(C)=\max(1,\lVert C\rVert,\lVert C^{-1}\rVert) K ( C ) = max ( 1 , ∥ C ∥ , ∥ C − 1 ∥) . Comparison with the operator norms of H H H and Λ 2 H \Lambda^2H Λ 2 H shows that a right input changes Q Q Q by at most C r + 4 log K ( C ) C_r+4\log K(C) C r + 4 log K ( C ) in absolute value.
Adding a nonnegative multiple of the sum of the inactive rows to the active row does not decrease A A A . To prove this, restrict to a pair of columns. If the active row becomes a + q b a+qb a + q b , where b = ∑ j b j b=\sum_j b_j b = ∑ j b j is the sum of the other rows, the contribution involving it is ∑ j ∣ det ( a + q b , b j ) ∣ \sum_j\lvert\det(a+qb,b_j)\rvert ∑ j ∣ det ( a + q b , b j )∣ . Order the directions of the b j b_j b j 's in the positive quadrant. The slopes in q q q of the determinants switch sign at the direction of b b b and sum to zero. The determinants themselves switch sign at the direction of a + q b a+qb a + q b . Hence on at least one entire side of the direction of b b b , the slopes agree in sign with the determinants, contributing the sum of their absolute values to the derivative. This sum is as large as the sum of the absolute values of the opposite slopes, which bounds any negative contribution on the other side. The derivative is thus nonnegative wherever it exists, and zero rows follow by continuity. Sum over the column pairs.
For probability rows p p p , q q q , the kernel
1 − ∑ i < j ∣ p i q j − p j q i ∣ = ∑ i p i q i + 2 ∑ i < j min ( p i q j , p j q i ) 1-\sum_{i<j}|p_iq_j-p_jq_i|=\sum_i p_iq_i+2\sum_{i<j}\min(p_iq_j,p_jq_i) 1 − i < j ∑ ∣ p i q j − p j q i ∣ = i ∑ p i q i + 2 i < j ∑ min ( p i q j , p j q i )
is positive semidefinite. The minimum term is the integral over t ≥ 0 t\geq0 t ≥ 0 of the product of p j 1 t ≤ p i / p j p_j1_{t\leq p_i/p_j} p j 1 t ≤ p i / p j and q j 1 t ≤ q i / q j q_j1_{t\leq q_i/q_j} q j 1 t ≤ q i / q j , with boundary values by continuity. Its unit Hilbert feature vectors realize the determinant distance as half their squared distance. For two independent draws of common law their expected squared distance is at most twice the expected squared distance from a fixed feature vector, by expansion about the mean. Weight the normalized inactive rows by their masses. If the active row has mass a a a and the others total mass b b b , their area A 0 A_0 A 0 and the area A i A_i A i involving the active row satisfy A i ≥ ( a / b ) A 0 A_i\geq(a/b)A_0 A i ≥ ( a / b ) A 0 . For H = B i q H ′ H=B_i^qH' H = B i q H ′ let u u u be the inactive mass fraction of H ′ H' H ′ . The wedge triangle inequality gives A ( H ) ≤ A ( H ′ ) + 2 q A 0 A(H)\leq A(H')+2qA_0 A ( H ) ≤ A ( H ′ ) + 2 q A 0 , and N ( H ) = ( 1 + q u ) N ( H ′ ) N(H)=(1+qu)N(H') N ( H ) = ( 1 + q u ) N ( H ′ ) , so
R ( H ) R ( H ′ ) ≤ 1 + 2 q u ( 1 + q u ) 2 ≤ 1. \frac{R(H)}{R(H')}\leq\frac{1+2qu}{(1+qu)^2}\leq1. R ( H ′ ) R ( H ) ≤ ( 1 + q u ) 2 1 + 2 q u ≤ 1.
If the run is followed by a different legal output, that row dominates the sum of all remaining rows, so u ≥ 1 / 2 u\geq1/2 u ≥ 1/2 . Each such completed run increases R R R by at least 9 / 8 9/8 9/8 . A run with mass ratio e d e^d e d increases log R \log R log R by at least 2 d − log ( 2 e d − 1 ) 2d-\log(2e^d-1) 2 d − log ( 2 e d − 1 ) , which is at least d / 5 d/5 d /5 for d ≥ log ( 3 / 2 ) d\geq\log(3/2) d ≥ log ( 3/2 ) by its derivative and its value at the endpoint. The final run gives at least d / 5 − log ( 3 / 2 ) / 5 d/5-\log(3/2)/5 d /5 − log ( 3/2 ) /5 . Therefore, for any legal sequence D D D with H = D H ′ H=DH' H = D H ′ ,
log ( N ( H ) / N ( H ′ ) ) ≤ 5 ( Q ( H ) − Q ( H ′ ) ) + log ( 3 / 2 ) . \log\bigl(N(H)/N(H')\bigr)\leq5\bigl(Q(H)-Q(H')\bigr)+\log(3/2). log ( N ( H ) / N ( H ′ ) ) ≤ 5 ( Q ( H ) − Q ( H ′ ) ) + log ( 3/2 ) .
The column-sum vector of D D D belongs to ( J − I ) R ≥ 0 r (J-I)\mathbb{R}_{\geq0}^r ( J − I ) R ≥ 0 r , invariant under the transposed generators, so all but at most one of its coordinates are at least half their maximum. The mass of H ′ H' H ′ outside any row is at least R ( H ′ ) N ( H ′ ) R(H')N(H') R ( H ′ ) N ( H ′ ) , by summing the wedge bound by row masses. Thus N ( H ) N(H) N ( H ) is at least half the maximum column sum of D D D times R ( H ′ ) N ( H ′ ) R(H')N(H') R ( H ′ ) N ( H ′ ) . Since det D = 1 \det D=1 det D = 1 , the inverse norm is bounded by a constant times ∥ D ∥ r − 1 \lVert D\rVert^{r-1} ∥ D ∥ r − 1 . Consequently log K ( D ) ≤ C r ( 1 + Q ( H ) ) \log K(D)\leq C_r(1+Q(H)) log K ( D ) ≤ C r ( 1 + Q ( H )) . During an excursion from depth at most Q 0 Q_0 Q 0 with accumulated input cost S S S , move all the already read input factors to the right before stripping all the already performed outputs. Each intermediate output remains legal by entrywise nonnegativity of the later inputs. The last bound gives log K ( D ) ≤ C r ( 1 + Q 0 + S ) \log K(D)\leq C_r(1+Q_0+S) log K ( D ) ≤ C r ( 1 + Q 0 + S ) also in the middle of a run, and the input distortion bound gives Q ≤ Q 0 + C r ( 1 + S ) Q\leq Q_0+C_r(1+S) Q ≤ Q 0 + C r ( 1 + S ) .
Rank-one drift
There is an absolute second singular value bound σ 2 ( C m ) ≤ C e − c m \sigma_2(C_m)\leq Ce^{-cm} σ 2 ( C m ) ≤ C e − c m for an input of m m m runs outside an event of probability C e − c m Ce^{-cm} C e − c m , uniformly in the initial state. Here is a direct proof. Write A i = B i T A_i=B_i^{\mathsf T} A i = B i T . On the cone ( J − I ) R ≥ 0 r (J-I)\mathbb{R}_{\geq0}^r ( J − I ) R ≥ 0 r , a vector scales as v = 1 − ξ v=1-\xi v = 1 − ξ with ξ ∈ Δ r \xi\in\Delta_r ξ ∈ Δ r . For v T z = 0 v^{\mathsf T}z=0 v T z = 0 , the map A i T A_i^{\mathsf T} A i T replaces coordinate i i i of z z z by 1 T z = ξ T z 1^{\mathsf T}z=\xi^{\mathsf T}z 1 T z = ξ T z , a convex combination, and maps the annihilator of v v v into that of A i − 1 v A_i^{-1}v A i − 1 v . Start with v v v in the image of the cone under a word of A i A_i A i 's. In two consecutive cycles each using every index once with exponent one, the future complete cycle ensures that every ξ \xi ξ -coordinate in the first cycle is uniformly positive, since a product of the corresponding B i B_i B i 's is strictly positive. Every row gets updated, so the product of the stochastic updates has strictly positive entries uniformly in these choices. On the unit sup-norm sphere in the annihilator, its norm is strictly less than one, since the initial v v v is uniformly positive and a convex average with positive weights can have absolute value one only when all coordinates equal the same signed unit. Compactness gives a uniform contraction factor. All other steps are nonexpanding. Multiplying along the word and using min–max yields an absolute second singular value bound by a dimension constant times a fixed power less than one per disjoint good cycle. Transpose and reverse the finite word to get the bound for B i B_i B i 's, since reversed double cycles have the same property. At each block of 2 r 2r 2 r runs one such admissible witness with exponents one has conditional probability at least p > 0 p > 0 p > 0 , uniformly. For its indicator X j X_j X j , E ( e − X j ∣ past ) ≤ 1 − p ( 1 − e − 1 ) \mathbb{E}(e^{-X_j} \mid\text{past}) \le1-p(1-e^{-1}) E ( e − X j ∣ past ) ≤ 1 − p ( 1 − e − 1 ) . Iterating and applying Markov’s inequality gives exponentially small probability of fewer than p q / 2 pq/2 pq /2 witnesses in q q q blocks, proving the claim.
Suppose H / N ( H ) H/N(H) H / N ( H ) has small inactive mass fraction δ \delta δ outside an active row a a a , and let b b b be the sum of the other rows. For a strictly positive input C C C , put B = ∥ b C ∥ 1 B = \lVert bC\rVert_1 B = ∥ b C ∥ 1 , W = ∥ a C ∧ b C ∥ 1 W = \lVert aC \wedge bC\rVert_1 W = ∥ a C ∧ b C ∥ 1 , and κ = B / min j ( b C ) j \kappa= B/\min_j (bC)_j κ = B / min j ( b C ) j , where the exterior ℓ 1 \ell^1 ℓ 1 -norm sums absolute coordinates. The maximal legal active run has length q = ⌊ min j ( a C ) j / ( b C ) j ⌋ q = \lfloor\min_j (aC)_j/(bC)_j \rfloor q = ⌊ min j ( a C ) j / ( b C ) j ⌋ . If j 0 j_0 j 0 attains this minimum and f f f is its fractional part, the new active entry at j j j is
( a C ) j ( b C ) j 0 − ( a C ) j 0 ( b C ) j ( b C ) j 0 + f ( b C ) j . \frac{(aC)_j(bC)_{j_0} - (aC)_{j_0}(bC)_j}{(bC)_{j_0}} + f(bC)_j. ( b C ) j 0 ( a C ) j ( b C ) j 0 − ( a C ) j 0 ( b C ) j + f ( b C ) j .
The resulting matrix H ′ H' H ′ satisfies N ( H ′ ) ≤ κ W / B + 2 B N(H') \le\kappa W/B+2B N ( H ′ ) ≤ κW / B + 2 B and A ( H ′ ) ≥ W A(H') \ge W A ( H ′ ) ≥ W , the latter by summing the active-row wedges before taking absolute values. Also A ( H C ) ≤ ( 1 + 2 q ) A ( H ′ ) A(HC) \le(1+2q)A(H') A ( H C ) ≤ ( 1 + 2 q ) A ( H ′ ) by the wedge triangle inequality for the reverse operation, and q ≤ N ( H C ) / B q \le N(HC)/B q ≤ N ( H C ) / B . Thus A ( H ′ ) ≥ B A ( H C ) / ( 3 N ( H C ) ) A(H') \ge BA(HC)/(3N(HC)) A ( H ′ ) ≥ B A ( H C ) / ( 3 N ( H C )) .
If W ≥ B 2 W \ge B^2 W ≥ B 2 , combine N ( H ′ ) ≤ ( κ + 2 ) W / B N(H') \le(\kappa+2)W/B N ( H ′ ) ≤ ( κ + 2 ) W / B with the bounds B ≥ m ( C ) ∥ b ∥ 1 B \ge m(C)\lVert b\rVert_1 B ≥ m ( C ) ∥ b ∥ 1 , W ≤ ∥ ∧ 2 C ∥ 1 N ( H ) ∥ b ∥ 1 W \le\lVert\wedge^2 C\rVert_1N(H)\lVert b\rVert_1 W ≤ ∥ ∧ 2 C ∥ 1 N ( H ) ∥ b ∥ 1 , and R ( H ) ≤ ∥ b ∥ 1 / N ( H ) R(H) \le\lVert b\rVert_1/N(H) R ( H ) ≤ ∥ b ∥ 1 / N ( H ) , where m ( C ) = min i ∑ j C i j m(C) = \min_i \sum_j C_{ij} m ( C ) = min i ∑ j C ij . This gives
R ( H ′ ) / R ( H ) ≥ m ( C ) 2 / ( ( κ + 2 ) 2 ∥ ∧ 2 C ∥ 1 ) . R(H')/R(H) \ge m(C)^2/((\kappa+2)^2\lVert\wedge^2 C\rVert_1). R ( H ′ ) / R ( H ) ≥ m ( C ) 2 / (( κ + 2 ) 2 ∥ ∧ 2 C ∥ 1 ) .
If W < B 2 W < B^2 W < B 2 , the estimate N ( H ′ ) ≤ ( κ + 2 ) B N(H') \le(\kappa+2)B N ( H ′ ) ≤ ( κ + 2 ) B gives
R ( H ′ ) / R ( H C ) ≥ ( 3 ( κ + 2 ) 2 B / N ( H C ) ) − 1 . R(H')/R(HC) \ge\left(3(\kappa+2)^2B/N(HC)\right)^{-1}. R ( H ′ ) / R ( H C ) ≥ ( 3 ( κ + 2 ) 2 B / N ( H C ) ) − 1 .
Use buffers of ⌊ ζ m ⌋ \lfloor\zeta m\rfloor ⌊ ζ m ⌋ runs at each end, for small fixed ζ > 0 \zeta> 0 ζ > 0 . Their products L L L , L ′ L' L ′ are strictly positive except with exponentially small probability by the witness estimate, and have entry sums at most exp ( K 0 ζ m ) \exp(K_0\zeta m) exp ( K 0 ζ m ) except with exponentially small probability by the conditional cost moment, for large fixed K 0 K_0 K 0 . In C = L M L ′ C = LML' C = L M L ′ , positivity of integer entries gives m ( C ) ≥ N ( C ) / N ( L ) m(C) \ge N(C)/N(L) m ( C ) ≥ N ( C ) / N ( L ) and κ ≤ N ( L ′ ) \kappa\le N(L') κ ≤ N ( L ′ ) . Indeed each row of L M L ′ LML' L M L ′ has mass at least N ( M L ′ ) N(ML') N ( M L ′ ) and each coordinate of b L M L ′ bLML' b L M L ′ is at least ∥ b L M ∥ 1 \lVert bLM\rVert_1 ∥ b L M ∥ 1 . Since ∥ ∧ 2 C ∥ 1 ≤ C r N ( C ) σ 2 ( C ) \lVert\wedge^2 C\rVert_1 \le C_rN(C)\sigma_2(C) ∥ ∧ 2 C ∥ 1 ≤ C r N ( C ) σ 2 ( C ) , the first case gives exponential gain when 4 K 0 ζ < c 4K_0\zeta< c 4 K 0 ζ < c . In the second, B / N ( H C ) ≤ N ( C ) δ B/N(HC) \le N(C)\delta B / N ( H C ) ≤ N ( C ) δ by C ≥ I C \ge I C ≥ I , and R ( H C ) / R ( H ) ≥ c r κ ( C ) − 4 R(HC)/R(H) \ge c_r\kappa(C)^{-4} R ( H C ) / R ( H ) ≥ c r κ ( C ) − 4 . The gain is thus at least c r e − K 1 m / δ c_r e^{-K_1m}/\delta c r e − K 1 m / δ outside exponentially small probability. Further stripping only increases R R R . For gain g > 1 g > 1 g > 1 and failure tolerance ϵ > 0 \epsilon> 0 ϵ > 0 , a fixed time m = O ( 1 + log g + log ( 1 / ϵ ) ) m = O(1+\log g+\log(1/\epsilon)) m = O ( 1 + log g + log ( 1/ ϵ )) therefore gives the gain uniformly for sufficiently small δ \delta δ , after choosing the threshold for δ \delta δ at that time.
To extend the vertex estimate, first note that a gasket point has a unique address until it meets a first-cell intersection after stripping a common prefix. At such an intersection it has exactly two addresses, because the inverse maps in the two cells send it to vertices, each with a unique constant address. At any fixed finite depth a neighborhood of the point within the gasket is contained in the union of its address cylinders at this depth: the other cylinders form a finite compact union excluding it. Accordingly a point with infinitely many runs in its address has a unique arbitrarily long prefix, while a point with an eventually constant address has one or two prefixes sending it to a vertex.
A uniform sign test allows a proposed output prefix to be made legal. For a fixed matrix M M M , if M θ ≥ 0 M\theta\ge0 M θ ≥ 0 at the future direction θ \theta θ but M C m MC_m M C m has a negative entry, then a nonzero row has opposite signs on θ \theta θ and one of the normalized columns of C m C_m C m . Both directions lie in the same cylinder, of diameter exponentially small in m m m . Its probability is therefore at most C ρ 0 m C\rho_0^m C ρ 0 m , for a fixed 0 < ρ 0 < 1 0 < \rho_0 < 1 0 < ρ 0 < 1 , by hyperplane regularity and a union over rows. Apply this with M = B − 1 H M = B^{-1}H M = B − 1 H for a fixed proposed output w w w . If all columns are nonnegative after the full proposed strip, each earlier strip is legal by multiplying by its nonnegative suffix. Hyperplane regularity applied to each coordinate also places θ \theta θ in a fixed positive compact subset of the simplex outside probability O ( ϵ ) O(\epsilon) O ( ϵ ) .
Fix g > 1 g > 1 g > 1 and ϵ > 0 \epsilon> 0 ϵ > 0 . Use a first block of m 1 = O ( 1 + log ( 1 / ϵ ) ) m_1 = O(1 + \log(1/\epsilon)) m 1 = O ( 1 + log ( 1/ ϵ )) runs for the sign test, with K ( C m 1 ) ≤ L 1 K(C_{m_1}) \le L_1 K ( C m 1 ) ≤ L 1 outside probability O ( ϵ ) O(\epsilon) O ( ϵ ) and log L 1 = O ( 1 + log ( 1 / ϵ ) ) \log L_1 = O(1 + \log(1/\epsilon)) log L 1 = O ( 1 + log ( 1/ ϵ )) . Use a second block of m 2 = O ( 1 + log g + log ( 1 / ϵ ) ) m_2 = O(1 + \log g + \log(1/\epsilon)) m 2 = O ( 1 + log g + log ( 1/ ϵ )) runs for the vertex estimate with gain g L 1 4 / c r gL_1^4/c_r g L 1 4 / c r . Its condition bound L 2 L_2 L 2 can be chosen with logarithm of the same order and probability of failure O ( ϵ ) O(\epsilon) O ( ϵ ) . Let a normalized nonnegative rank-one map have image u ∈ R u \in\mathbb{R} u ∈ R . If u u u has infinitely many runs, take a fixed prefix with enough completed runs that their factor 9 / 8 9/8 9/8 compensates the worst distortions of both input blocks and leaves gain g g g . By shrinking the matrix neighborhood, on survival and the positive compact core the output direction lies in that prefix cylinder. Indeed its image is uniformly close to u u u on the core and the other cylinders are separated from u u u . The sign test makes that prefix legal after the first block with the prescribed exception probability. Its completed runs provide the claimed gain, and further stripping helps. If u u u has an eventually constant address, use the one or two prefixes sending it to a vertex. One of these applies on survival in a sufficiently small matrix neighborhood. Use the sign test for both, then select a legal candidate from the first-block matrices alone. After stripping it and before any other output, the result is uniformly close, in relative row masses, to a vertex matrix. In fact the limiting matrix is sent to a vertex by this fixed prefix, and first-block multiplication has bounded norm and does not decrease the limiting mass because its matrix is entrywise at least I I I . Thus the neighborhood can be shrunk to meet the vertex threshold. The second block now has its original conditional law and supplies the gain. Extra outputs can be deferred until after the next right input, since their legality persists under right multiplication and the full stripping is unique. Crucially the two block lengths were fixed before shrinking the neighborhoods. Compactness gives a neighborhood U U U of the rank-one preserving stratum with a single time M = m 1 + m 2 M = m_1 + m_2 M = m 1 + m 2 and bound
P { E ∩ { R ( H M ) < g R ( H 0 ) } } ≤ C ϵ if H 0 / N ( H 0 ) ∈ U . \mathbb{P}\{E \cap\{R(H_M) < gR(H_0)\}\} \le C\epsilon\quad\text{if } H_0/N(H_0) \in U. P { E ∩ { R ( H M ) < g R ( H 0 )}} ≤ C ϵ if H 0 / N ( H 0 ) ∈ U .
Use g = 2 g = 2 g = 2 . When the current conditional probability of E E E is at least 1 − ϵ 1 - \epsilon 1 − ϵ , the conditional gain failure probability in the original law is O ( ϵ ) O(\epsilon) O ( ϵ ) . The positive change in Q Q Q is bounded by C r + 4 log K ( C M ) C_r + 4\log K(C_M) C r + 4 log K ( C M ) , which has conditional second moment O ( M 2 ) O(M^2) O ( M 2 ) . A variable dominating the depth change, equal to − log 2 -\log2 − log 2 on gain and this bound on failure, has uniformly negative mean for small fixed ϵ \epsilon ϵ , by Cauchy–Schwarz and M = O ( 1 + log ( 1 / ϵ ) ) M = O(1 + \log(1/\epsilon)) M = O ( 1 + log ( 1/ ϵ )) . It also has uniform exponential moments at this fixed M M M . Taylor expansion and Hölder’s inequality give s , ϑ > 0 s,\vartheta> 0 s , ϑ > 0 and q ∗ < 1 q_* < 1 q ∗ < 1 such that
E exp { s S M + ϑ ( Q ( H M ) − Q ( H 0 ) ) } ≤ q ∗ , (11) \mathbb{E}\exp\{sS_M+\vartheta(Q(H_M)-Q(H_0))\}\le q_*, \tag*{(11)} E exp { s S M + ϑ ( Q ( H M ) − Q ( H 0 ))} ≤ q ∗ , (11)
where S M S_M S M is the total input cost in the block. The estimate holds in the original conditional law at each actual time in this neighborhood with survival probability at least 1 − ϵ 1-\epsilon 1 − ϵ .
Rational planes and carrier transport
A rational two-dimensional subspace P P P is positive if its intersection with the nonnegative cone spans it. Its height is the exterior ℓ 1 \ell^1 ℓ 1 -norm of a primitive integer generator of ∧ 2 P \wedge^2P ∧ 2 P . If B i − 1 P B_i^{-1}P B i − 1 P is positive, its height is at most that of P P P . Choose two independent nonnegative vectors in the inverse plane and form the matrix of these columns. The area monotonicity already proved applies to this rectangular matrix. Applying B i B_i B i maps its exterior product to one with the same scalar factor relative to the primitive vector of the target, because the exterior map is unimodular. Cancelling this scalar proves the height comparison. Thus any finite family of positive rational planes can be enlarged to a finite family closed forward under all inverse outputs that preserve positivity, by taking all positive planes up to the maximum of its heights.
Every directed cycle in this family acts trivially on the annihilator. To see this, let a positive word matrix D D D preserve P P P . On the active indices, those that occur in the word, its induced block is strictly positive if there are at least two active indices. Its second eigenvalue in absolute value is less than one. In fact the transpose is a word of A i A_i A i 's in reverse order, and its Perron vector belongs to the cone ( J − I ) R ≥ 0 l (J-I)\mathbb{R}_{\ge0}^{l} ( J − I ) R ≥ 0 l in the active dimension l l l , by cone invariance and positivity. The moving annihilator argument above gives strict contraction on that Perron vector’s annihilator under one period: every stochastic replacement has all coefficients positive because its Perron continuation lies in the interior of the cone. For each cyclic continuation the Perron vector lies in the interior of that cone: by conjugation with J − I J-I J − I , it is the image of the strictly positive Perron vector for the corresponding complete cyclic product of the B i B_i B i . This includes l = 2 l=2 l = 2 , where J − I J-I J − I is the swap. The active block has determinant one. Each monic integral factor of its characteristic polynomial omitting the Perron root would have nonzero constant term of absolute value less than one, by this contraction. Hence the polynomial is irreducible over Q \mathbb{Q} Q . The full matrix has the same expanding Perron eigenvalue and a left Perron vector positive on every coordinate: on the inactive coordinates the full matrix has an upper coupling block with a positive entry in each column, since every active row update adds all other rows. Any nonzero nonnegative vector in P P P has nonzero Perron projection, so invariance puts the Perron eigenvector in P P P by iterating and scaling. Since P P P is rational and two-dimensional, the Perron eigenvalue has degree at most two. It follows that l = 2 l=2 l = 2 and P P P is the active plane, obtained as the rational invariant span supporting that irreducible quadratic. More explicitly the full quotient by the active plane is the identity, so the quadratic factor annihilates P P P and its value at one is nonzero, forcing the quotient image of P P P to vanish. If only index i i i is active, applying D − I D-I D − I to a nonnegative vector of P P P with nonzero mass outside i i i gives a nonzero multiple of e i e_i e i . Such a vector exists because P P P is positive and two-dimensional. In both cases the annihilator action by right multiplication is the identity. Removing cycles from paths therefore gives, for each plane P P P in the finite family, a finite set N P \mathcal{N}_P N P spanning its annihilator, closed under the forward rule q ↦ q B i q\mapsto qB_i q ↦ q B i to the inverse-image plane. Start with bases and transport along all simple paths to obtain these sets.
For a plane in this family define
d P ( H ) = max q ∈ N P ∥ q H ∥ , f P ( H ) = log A ( H ) d P ( H ) . d_P(H)=\max_{q\in\mathcal{N}_P}\lVert qH\rVert,\qquad f_P(H)=\log\frac{\sqrt{A(H)}}{d_P(H)}. d P ( H ) = q ∈ N P max ∥ q H ∥ , f P ( H ) = log d P ( H ) A ( H ) .
The denominator is comparable to the Frobenius norm of the projections of the columns normal to P P P , uniformly over this finite family. If two distinct planes P , T P,T P , T are in the family, then
σ 2 ( H ) ≤ C ( d P ( H ) + d T ( H ) ) . (12) \sigma_2(H)\le C\bigl(d_P(H)+d_T(H)\bigr). \tag*{(12)} σ 2 ( H ) ≤ C ( d P ( H ) + d T ( H ) ) . (12)
Indeed, the map to the pair of normal projections is injective on the orthogonal complement of P ∩ T P\cap T P ∩ T , giving a uniform distance bound to their intersection. Projecting the matrix into that intersection gives a rank-at-most-one approximation. For the finitely many possible first failed planes P ′ = B i − 1 P P'=B_i^{-1}P P ′ = B i − 1 P which are not positive, the cone P ′ ∩ R ≥ 0 l P'\cap\mathbb{R}_{\ge0}^{l} P ′ ∩ R ≥ 0 l has dimension at most one. Hoffman’s error bound [25 ] applied to the system of nonnegativity inequalities and normal equalities of P ′ P' P ′ bounds the distance of a nonnegative column to this cone by a constant times its distance to P ′ P' P ′ . Thus σ 2 ( H ) \sigma_2(H) σ 2 ( H ) is bounded by a constant times the projected Frobenius norm for the failed plane as well.
Write T i n T_{\mathrm{in}} T in for the one-run input-only expectation operator, acting on both the matrix and the current input state. For any fixed P P P , choose a maximizing initial covector in d P ( H ) d_P(H) d P ( H ) . Submultiplicativity of the exterior norm and use of this one covector after a right input give, up to a fixed dimensional additive constant,
f P ( H C m ) − f P ( H ) ≤ 1 2 log ∥ Λ 2 C m ∥ − log ∥ q H C m ∥ ∥ q H ∥ . f_P(HC_m)-f_P(H)\le\frac{1}{2}\log\lVert\Lambda^2 C_m\rVert-\log\frac{\lVert qHC_m\rVert}{\lVert qH\rVert}. f P ( H C m ) − f P ( H ) ≤ 2 1 log ∥ Λ 2 C m ∥ − log ∥ q H ∥ ∥ q H C m ∥ .
The mean bounds (10) give T i n m f P − f P ≤ − c m T_{\mathrm{in}}^m f_P-f_P\le-cm T in m f P − f P ≤ − c m for one fixed large m m m and c > 0 c>0 c > 0 , uniformly. Set
ψ P = 1 m ∑ j = 0 m − 1 T i n j f P . \psi_P=\frac{1}{m}\sum_{j=0}^{m-1}T_{\mathrm{in}}^j f_P. ψ P = m 1 j = 0 ∑ m − 1 T in j f P .
The absolute input distortion of f P f_P f P is at most C r + 2 log K ( C ) C_r+2\log K(C) C r + 2 log K ( C ) , by operator and inverse norm bounds. Therefore ψ P − f P \psi_P-f_P ψ P − f P is uniformly bounded and T i n ψ P − ψ P ≤ − c T_{\mathrm{in}}\psi_P-\psi_P\le-c T in ψ P − ψ P ≤ − c by telescoping. Its one-step change has a uniform exponential moment. A small positive exponential power gives constants δ > 0 \delta>0 δ > 0 , ρ < 1 \rho<1 ρ < 1 for which exp ( δ ψ P ) \exp(\delta\psi_P) exp ( δ ψ P ) contracts by factor ρ \rho ρ in one input expectation. If stripping D D D sends P P P to T = D − 1 P T=D^{-1}P T = D − 1 P and all intervening planes are positive, the forward normal sets give d T ( D − 1 H ) ≥ d P ( H ) d_T(D^{-1}H)\ge d_P(H) d T ( D − 1 H ) ≥ d P ( H ) and area decreases. The same comparison holds after any future right inputs, which do not change the legality of D D D or the future law when only the left matrix is changed. Hence ψ T ( D − 1 H ) ≤ ψ P ( H ) \psi_T(D^{-1}H)\le\psi_P(H) ψ T ( D − 1 H ) ≤ ψ P ( H ) . A tracked plane transported along outputs thus has a contracting nonnegative exponential supermartingale, killed at zero on first plane loss.
Returns at bounded depth
Choose Q 0 Q_0 Q 0 so large that every singular preserving matrix of entry sum one with area at most 2 e − Q 0 2e^{-Q_0} 2 e − Q 0 belongs to U \mathcal{U} U . Here preservation may mean preservation of one allowed initial corner. The finite union of these preservation sets is compact: the condition that M B i θ MB_i\theta M B i θ belongs projectively to the gasket is closed for every positive gasket point θ \theta θ , since the image is nonzero for every nonnegative entry-sum-one M M M . The zero-area part is rank one with image in the gasket. Compactness proves the choice. On nonterminal survival all sufficiently late states at multiples of M M M runs consequently lie in the domain
p ≥ 1 − ϵ , Q ≤ Q 0 or H / N ( H ) ∈ U , p\ge1-\epsilon,\qquad Q\le Q_0\quad\text{or}\quad H/N(H)\in\mathcal{U}, p ≥ 1 − ϵ , Q ≤ Q 0 or H / N ( H ) ∈ U ,
where the probability condition is required in both cases. Kill the process when it exits this domain or becomes terminal. Starting at Q ≤ Q 0 Q\le Q_0 Q ≤ Q 0 , end an excursion at the next such sampled time with Q ≤ Q 0 Q\le Q_0 Q ≤ Q 0 , or at killing. After its first block, (11) makes exp ( s S + ϑ Q ) \exp(sS+\vartheta Q) exp ( s S + ϑQ ) a supermartingale while the process is at high depth in the domain. The first block has a uniform cost moment and its depth increase is bounded by C r + 4 log K ( C M ) C_r+4\log K(C_M) C r + 4 log K ( C M ) . Decrease s , ϑ s,\vartheta s , ϑ by a common factor if needed, using Hölder’s inequality in (11) , to bound the first-block expectation uniformly. As Q ≥ log 2 Q\ge\log2 Q ≥ log 2 , Fatou’s lemma gives a uniform exponential moment of excursion cost, in particular a finite excursion time. Starting at any finite depth gives a finite first entrance to bounded depth or killing by the same argument, with a bound depending on that depth.
Every preserving normalized limit with Q ≤ Q 0 Q\le Q_0 Q ≤ Q 0 has rank two and image interval of diameter bounded below in terms of Q 0 Q_0 Q 0 , also after composition with one permitted B i B_i B i . Indeed its normalized second singular value is bounded below by a dimensional multiple of the area, and each of the finitely many right factors changes singular values by bounded factors. If the image diameters tended to zero, compactness would yield a rank-one limit. Each interval lies on a cylinder edge, so uniform cylinder shrinking bounds the raw depth of its cylinder. Its plane is spanned by two columns of that integral cylinder matrix and is positive. Thus all limiting planes lie in one finite base family, enlarged by primitive height as above.
At each bounded-depth return set V = max P exp ( δ ψ P ) V=\max_P\exp(\delta\psi_P) V = max P exp ( δ ψ P ) over this enlarged family, and track one maximizing plane. During its excursion, the cumulative input and output matrices C , D C,D C , D satisfy log K ( C ) + log K ( D ) ≤ C 0 ( 1 + Q 0 + S ) \log K(C)+\log K(D)\le C_0(1+Q_0+S) log K ( C ) + log K ( D ) ≤ C 0 ( 1 + Q 0 + S ) by the output budget. At an intermediate positive plane, a target normal q ′ q' q ′ pulls back to q ′ D − 1 q'D^{-1} q ′ D − 1 , a source normal of size at most K ( D ) ∥ q ′ ∥ K(D)\lVert q'\rVert K ( D ) ∥ q ′ ∥ . Its coefficients in a fixed source basis are bounded by a constant times this size. Since the matrix has become D − 1 H C D^{-1}HC D − 1 H C , its denominator is at most a constant times the starting denominator times K ( D ) K ( C ) K(D)K(C) K ( D ) K ( C ) . This also holds at first plane loss using a fixed basis of the failed plane, because there are only finitely many first failed planes. The area is bounded below by its initial value divided by the exterior norm distortion of C , D C,D C , D . The tracked f f f is therefore at least its starting value minus C 1 ( 1 + Q 0 + S ) C_1(1+Q_0+S) C 1 ( 1 + Q 0 + S ) even at first plane loss.
At first loss, Hoffman’s bound gives denominator at least c 2 ( H ) c_2(H) c 2 ( H ) , hence f ≤ Q / 2 + C 2 f\le Q/2+C_2 f ≤ Q /2 + C 2 , by A ( H ) ≍ N ( H ) σ 2 ( H ) A(H)\asymp N(H)\sigma_2(H) A ( H ) ≍ N ( H ) σ 2 ( H ) . Here Q ≤ Q 0 + C 3 ( 1 + S ) Q\le Q_0+C_3(1+S) Q ≤ Q 0 + C 3 ( 1 + S ) by the input distortion bound. If the tracked plane stays positive but a different plane maximizes at the next return, (12) gives f ≤ Q / 2 + C 4 f\le Q/2+C_4 f ≤ Q /2 + C 4 for the tracked plane there: the competitor’s f f f is at least the tracked f f f minus the bounded corrector error, so both denominators cannot be small compared with σ 2 ( H ) \sigma_2(H) σ 2 ( H ) . Either failure thus requires excursion cost at least c log V − C 5 c\log V-C_5 c log V − C 5 . The exponential cost moment bounds the conditional probability of such a bad reset by C 6 V − η C_6V^{-\eta} C 6 V − η for some η > 0 \eta>0 η > 0 . On good returns the actual height equals the tracked height, and optional stopping gives E ( V n e x t 1 g o o d ∣ p a s t ) ≤ ρ V \mathbb{E}(V_{\mathrm{next}}\mathbf{1}_{\mathrm{good}}\mid\mathrm{past})\leq\rho V E ( V next 1 good ∣ past ) ≤ ρ V . Apply the strict one-step contraction before optional stopping because the return takes at least one input. At killing set height zero and mark the transition good.
These inequalities yield recurrence even with arbitrary reset amplitudes. For a large threshold R ∗ > 0 R_*>0 R ∗ > 0 , kill visits to V ≤ R ∗ V\leq R_* V ≤ R ∗ at zero and mark them good. Above R ∗ R_* R ∗ , normalize the good kernel by its mass. This conditional good chain contracts expected height by ρ ′ ≤ ρ / ( 1 − C 6 R ∗ − η ) < 1 \rho'\leq\rho/(1-C_6R_*^{-\eta})<1 ρ ′ ≤ ρ / ( 1 − C 6 R ∗ − η ) < 1 and therefore reaches the threshold almost surely. In the band [ 2 j R ∗ , 2 j + 1 R ∗ ) [2^jR_*,2^{j+1}R_*) [ 2 j R ∗ , 2 j + 1 R ∗ ) its expected number of visits is at most 2 / ( 1 − ρ ′ ) 2/(1-\rho') 2/ ( 1 − ρ ′ ) : wait for the first entry below the band’s upper end and bound the expected total subsequent killed height by 2 j + 1 R ∗ / ( 1 − ρ ′ ) 2^{j+1}R_*/(1-\rho') 2 j + 1 R ∗ / ( 1 − ρ ′ ) . Couple the original chain to this good chain until the first bad transition. The conditional bad-step probabilities have expected sum at most
2 C 6 1 − ρ ′ ∑ j ≥ 0 ( 2 j R ∗ ) − η < 1 \frac{2C_6}{1-\rho'}\sum_{j\geq0}(2^jR_*)^{-\eta}<1 1 − ρ ′ 2 C 6 j ≥ 0 ∑ ( 2 j R ∗ ) − η < 1
for large R ∗ R_* R ∗ , uniformly over initial heights. Restart after each bad reset at its actual finite height. The probability of avoiding a threshold hit through arbitrarily many bad resets is zero by the resulting geometric bound. With finitely many resets the last good chain hits almost surely. Restart upon each exit from the bounded-height set. These arguments apply to the conditional laws here by carrying the full past in the state, and exclude a surviving return chain whose heights tend to infinity.
Theorem 13. Let G G G be an invertible rational r r r -by-r r r matrix. For the future input direction θ \theta θ under the ordered law, almost surely on the event that G θ G\theta Gθ lies with positive orientation in R \mathcal{R} R , there are an input prefix v v v , a finite output word u u u , a permutation matrix P P P , and c > 0 c>0 c > 0 such that
G B v = c B u P . GB_v=cB_uP. G B v = c B u P . Proof. Start at a nonnegative reduced remainder. On nonterminal survival its size tends to infinity and it eventually stays in the sampled domain. From any deterministic sampled start, the entrance and return bounds show that a path staying in the domain has infinitely many bounded-depth returns. All their normalized limits have rank two with range in the finite family. Along a subsequence converging to such a limit the normalized area stays bounded below and the normal residual of that plane divided by N ( H ) N(H) N ( H ) tends to zero. Hence the corresponding ψ P \psi_P ψ P tends to infinity. The maximized height tends to infinity along all bounded-depth returns, since otherwise a bounded-height subsequence would admit a normalized convergent further subsequence. This contradicts recurrence. The countable union over deterministic sampled starts covers eventual residence.
For arbitrary G G G , the sign test and summability show that almost surely on survival, G B v GB_v G B v is eventually nonnegative for finite input prefixes v v v . At each such prefix strip to a reduced remainder. Conditional on any fixed prefix the future law is the original law at that state. Applying the preceding argument at each of the countably many prefixes yields terminal scalar permutation remainder almost surely on survival. Multiplying by the stripped output words proves the formula. □
Collisions along a common suffix
Proposition 14. For the density equation in § 3 , let n ≥ 4 n\geq4 n ≥ 4 . Fix two distinct labelled positive integral solutions reached by ascending words, allowing a permutation of their first d = n − 1 d=n-1 d = n − 1 slots. The number of common ascending words for which the resulting last coordinates agree and are at most B B B is O ( ( log B ) β ) O((\log B)^\beta) O (( log B ) β ) , with β \beta β the linear counting exponent.
Observability on a finite-index orbit
Let F i F_i F i be the ascending move in slot i ≤ d i \le d i ≤ d , regarded as a polynomial automorphism of the ambient space over Z \mathbb{Z} Z . Its inverse reverses the swap and the Vieta operation. Both preserve positive integral solutions. Write H H H for the group generated by these maps, acting diagonally on pairs. In a run of F i F_i F i , put P = ∏ j ∉ { i , n } x j P = \prod_{j\notin\{i,n\}} x_j P = ∏ j ∈ / { i , n } x j and
a = n ( k + 1 ) P − k ∑ j ∉ { i , n } P x j . a = n(k+1)P-k\sum_{j\notin\{i,n\}}\frac{P}{x_j}. a = n ( k + 1 ) P − k j ∈ / { i , n } ∑ x j P .
Each quotient is the product omitting the given frozen slot. On the two changing coordinates ( u , v ) = ( x i , x n ) (u,v)=(x_i,x_n) ( u , v ) = ( x i , x n ) , the move is ( u , v ) ↦ ( v , a v − u − k P ) (u,v)\mapsto(v,av-u-kP) ( u , v ) ↦ ( v , a v − u − k P ) . The frozen coordinates are positive, so a ≥ ( n + 2 k ) P > 2 a\ge(n+2k)P>2 a ≥ ( n + 2 k ) P > 2 and 0 ≤ k P / ( a − 2 ) < 1 / 2 0\le kP/(a-2)<1/2 0 ≤ k P / ( a − 2 ) < 1/2 . With λ > 1 \lambda>1 λ > 1 the larger root of t 2 − a t + 1 t^2-at+1 t 2 − a t + 1 , the last coordinate after t ∈ Z t\in\mathbb{Z} t ∈ Z moves is
k P a − 2 + c + λ t + c − λ − t . \frac{kP}{a-2}+c_+\lambda^t+c_-\lambda^{-t}. a − 2 k P + c + λ t + c − λ − t .
Both coefficients are positive. A negative coefficient is incompatible with positivity at the growing end, and a vanishing coefficient gives a limit below 1 / 2 1/2 1/2 at that end, incompatible with positive integrality. If two sequences agree at all nonnegative multiples of a positive integer m m m , consecutive ratios identify λ m \lambda^m λ m , hence λ \lambda λ , and linear independence of the constant and two exponential sequences identifies the remaining coefficients. The values at times 0 0 0 and − 1 -1 − 1 give equality in slots n n n and i i i . Every finite-index subgroup of H H H contains a positive power of every F i F_i F i . Consequently, on the orbit of a distinct pair under such a subgroup, the difference of the last coordinates cannot vanish identically.
Congruence collision probabilities
Let H 9 H_9 H 9 be the kernel of the action of H H H on ( Z / 9 Z ) n (\mathbb{Z}/9\mathbb{Z})^n ( Z /9 Z ) n . At every residue representative b b b and for g ∈ H 9 g\in H_9 g ∈ H 9 , the evaluations at b b b and at b + 3 e j b+3e_j b + 3 e j for each standard basis vector e j e_j e j of Z n \mathbb{Z}^n Z n show that the derivative of g g g at b b b is the identity modulo 3 3 3 . Thus in coordinates x = b + 3 z x=b+3z x = b + 3 z on the corresponding 3 3 3 -adic ball, ( g ( b + 3 z ) − b ) / 3 (g(b+3z)-b)/3 ( g ( b + 3 z ) − b ) /3 is the identity modulo 3 3 3 coefficientwise. Indeed the constant displacement is divisible by 9 9 9 , and the terms of degree at least two retain a factor 3 3 3 after division. Poonen’s interpolation theorem [24 Theorem 1] therefore gives an analytic family of iterates with time in Z 3 \mathbb{Z}_3 Z 3 , since the coefficient valuation is at least 1 > 1 / ( 3 − 1 ) 1>1/(3-1) 1 > 1/ ( 3 − 1 ) . This applies on each ball, also for the diagonal action.
On the closure of an H 9 H_9 H 9 -orbit of a pair, take the probability measure obtained by inverse limit of the uniform measures on its finite congruence orbits. It has full support. Each finite orbit is transitive, and the conditional expectations of an invariant function on these finite levels are constant. Their convergence to the function proves ergodicity. The analytic time maps preserve this measure by approximation with nonnegative integer powers, using joint continuity on a compact polydisk. For each pair, its last-coordinate difference along an analytic flow is identically zero or has finitely many zeros by Strassmann’s theorem. If E E E is the set where the difference vanishes, the integral over t ∈ Z 3 t\in\mathbb{Z}_3 t ∈ Z 3 of the absolute difference of its indicators at times t t t and t + 1 t+1 t + 1 is zero. By Fubini and invariance under the time maps, the indicator is invariant almost everywhere under g g g . This holds for each g ∈ H 9 g\in H_9 g ∈ H 9 . Ergodicity makes the measure of E E E zero or one. Measure one, together with closedness and full support, contradicts observability on the orbit of a distinct pair.
For q = 3 a q=3^a q = 3 a with a ≥ 1 a\ge1 a ≥ 1 , let Ω q \Omega_q Ω q be the diagonal H H H -orbit of the two seeds modulo q q q . Its inverse-limit measure is the uniform average of the translates of the H 9 H_9 H 9 -orbit measure by coset representatives. The conclusion on every translate and continuity from above imply
lim a → ∞ # { ( x , y ) ∈ Ω 3 a : x n = y n } # Ω 3 a = 0 , \lim_{a\to\infty}\frac{\#\{(x,y)\in\Omega_{3^a}:x_n=y_n\}}{\#\Omega_{3^a}}=0, a → ∞ lim # Ω 3 a # {( x , y ) ∈ Ω 3 a : x n = y n } = 0 ,
where equality in the numerator is in Z / 3 a Z \mathbb{Z}/3^a\mathbb{Z} Z / 3 a Z .
Renewal with a finite permutation action
Use the accelerated linear system of Gamburd, Magee, and Ronan [15 Sections 4–5] . In its ordered coordinates the base consists of
0 ≤ w 1 ≤ ⋯ ≤ w d , ∑ i = 1 d w i = 1. 0 \le w_1 \le\cdots\le w_d,\qquad\sum_{i=1}^{d} w_i = 1. 0 ≤ w 1 ≤ ⋯ ≤ w d , i = 1 ∑ d w i = 1.
A branch indexed by ( a , j ) (a,j) ( a , j ) with a ≥ 1 a \ge1 a ≥ 1 , 1 ≤ j < d 1 \le j < d 1 ≤ j < d , deletes coordinate w j w_j w j , appends 1 + ( a − 1 ) ( 1 − w j ) 1+(a-1)(1-w_j) 1 + ( a − 1 ) ( 1 − w j ) , and divides each of the resulting d d d entries by 1 + a ( 1 − w j ) 1+a(1-w_j) 1 + a ( 1 − w j ) . Denote this map by f a , j f_{a,j} f a , j and its roof by τ a , j ( w ) = log ( 1 + a ( 1 − w j ) ) \tau_{a,j}(w)=\log(1+a(1-w_j)) τ a , j ( w ) = log ( 1 + a ( 1 − w j )) . A word’s roof is the sum of consecutive roofs evaluated at the consecutive states. The scalar transfer operator is the sum over branches of e − s τ a , j e^{-s\tau_{a,j}} e − s τ a , j times composition by f a , j f_{a,j} f a , j . We use its positive C 1 C^1 C 1 eigenfunction h β h_\beta h β , eigenvalue 1 1 1 at s = β > 1 s=\beta>1 s = β > 1 , and the uniform exponential contraction of branch compositions from [15 Sections 4.2–4.4 and Proposition 45] .
For fixed q q q , the finite state consists of a permutation of the d d d labels and a point in Ω q \Omega_q Ω q . A branch ( a , j ) (a,j) ( a , j ) moves the j j j -th label to the last position and applies F i a F_i^a F i a to the residue pair for that label i i i . This operation is a permutation: the last label identifies the moved slot and the residue operation has an inverse. Let m m m be a common multiple of all residue orders of F i F_i F i . Runs of length m m m change only the ordering, and these move-to-last permutations generate the ordering group. One can move any label to a nonlast slot, apply a positive power realizing any desired residue power, and restore the order. It follows that the branches generate a transitive group on the joint finite state.
Consider the operator with the same base weights and branch maps on this finite state. Divide by h β h_\beta h β so that the weights at s = β s=\beta s = β sum to one. At s = β + i t s=\beta+it s = β + i t , t ∈ R t\in\mathbb{R} t ∈ R , the weights differ by phases. In the Euclidean norm on the finite-state vector the branch permutations are isometries. The normalized operator is power bounded in the supremum norm. Each differentiated iterate is bounded by a constant times the supremum norm plus O ( ρ m ) O(\rho^m) O ( ρ m ) times the derivative norm after m m m steps, for some ρ < 1 \rho<1 ρ < 1 . To see this, the derivative of the argument is bounded by the uniform contraction estimate, and the derivative of the total roof is bounded by the sum of a geometric series: each one-branch roof has bounded derivative because w j ≤ 1 / 2 w_j\le1/2 w j ≤ 1/2 . The bounded derivative of the logarithm of h β h_\beta h β gives the same bound for the normalized weights. Compact inclusion of C 1 C^1 C 1 in C 0 C^0 C 0 gives essential spectral radius less than one as in [15 Lemmas 38 and 46] . The defining series is locally holomorphic for ℜ ( s ) > 1 \Re(s)>1 ℜ ( s ) > 1 ; its C 1 C^1 C 1 bound follows by summing O ( ( 1 + a / 2 ) − ℜ ( s ) ) O((1+a/2)^{-\Re(s)}) O (( 1 + a /2 ) − ℜ ( s ) ) with the logarithmic factors from parameter derivatives.
A peripheral eigenfunction at β + i t \beta+it β + i t has maximal Euclidean norm on the common attractor of the branches. More precisely, equality in the triangle inequality at a point of maximum norm implies equality at each of its word images. The closure of these images contains the limit of every growing sequence of nested branch cylinders, because the diameter of a depth-m m m cylinder is O ( ρ m ) O(\rho^m) O ( ρ m ) . In particular equality holds at every branch fixed point and along each of its images. If the eigenvalue is e i θ e^{i\theta} e i θ , at the fixed point of branch ( a , d − 1 ) (a,d-1) ( a , d − 1 ) it follows that
M ( θ + t log a + a 2 + 4 2 ) ∈ 2 π Z , M\left(\theta+t\log\frac{a+\sqrt{a^2+4}}{2}\right)\in2\pi\mathbb{Z}, M ( θ + t log 2 a + a 2 + 4 ) ∈ 2 π Z ,
where M M M is a common multiple of the finite-state permutation orders. In fact, the earlier coordinates of this fixed point are zero, because they are unchanged before division by a factor greater than one. The unnormalized update of the last two is ( x , y ) ↦ ( y , x + a y ) (x,y)\mapsto(y,x+ay) ( x , y ) ↦ ( y , x + a y ) , giving the indicated roof. For t ≠ 0 t\ne0 t = 0 , the consecutive differences of the displayed logarithms are nonzero and tend to zero. This excludes peripheral eigenvalues. At t = 0 t=0 t = 0 and eigenvalue one, apply the equality relation to a common branch word from two attractor points. The same permutation occurs at both points, so contraction and continuity imply equality of the eigenfunction values. The resulting constant vector is invariant under the transitive finite action. Iteration extends this constant to all base points, since trajectories approach the attractor uniformly. Power boundedness excludes a Jordan block. The spectral projection at one is therefore the scalar projection on the uniform fiber average, because fiber averaging commutes with the scalar transfer.
For threshold u u u , the number of words with roof at most u u u and terminal state in a subset E E E has Laplace transform obtained by applying s − 1 ( I − L s ) − 1 s^{-1}(I-L_s)^{-1} s − 1 ( I − L s ) − 1 to its indicator, where L s L_s L s is the unnormalized finite-state operator. The argument above gives a simple pole at β \beta β with residue equal to the scalar residue times the uniform fraction of E E E , and local holomorphy at every other point of the critical line. The renewal argument of [15 Section 4.3] consequently gives, at the fixed initial barycenter and for any initial ordering, an asymptotic of the form
c β h β ( 1 / d ) # E d ! # Ω q e β u c\beta h_\beta(1/d)\frac{\#E}{d!\,\#\Omega_q}e^{\beta u} c β h β ( 1/ d ) d ! # Ω q # E e β u
Here the scalar coefficient is independent of q q q , and the error is taken with q q q fixed. The conclusion for an empty E E E is the identically zero count.
Passage to actual heights
Proof of Proposition 14. Lemma 6 supplies an upper bound O ( log B ) O(\log B) O ( log B ) on 1 T C A ( s ) 1 \mathbf{1}^{\mathsf{T}}C_A(s)\mathbf{1} 1 T C A ( s ) 1 for a continuation s s s from either of the two fixed seeds, where C A ( s ) C_A(s) C A ( s ) is the chronological product defined in § 3 , with final maximum at most B B B . Indeed the full label height of the associated word from the base seed is at least this linear height since the prefix matrix is entrywise at least the identity. A permutation of the parent slots preserves the scalar linear height. At the barycenter the exponential of the total linear roof along s s s is exactly 1 T C A ( s ) 1 / d \mathbf{1}^{\mathsf{T}}C_A(s)\mathbf{1}/d 1 T C A ( s ) 1 / d , by telescoping the normalizations of the successive transposed matrices. The finitely many initial orderings cover all run words. Apply the finite-state count at a fixed modulus q q q , with E E E the pairs of equal last coordinates and all orderings. An exact collision is counted by this congruence condition. The upper limit of the number of exact collisions divided by ( log B ) β (\log B)^\beta ( log B ) β is bounded by a constant independent of q q q times the collision fraction in Ω q \Omega_q Ω q . Letting q = 3 a q=3^a q = 3 a tend to infinity proves Proposition 14. □
AI contribution
AI agents assisted in developing and checking the arguments in the research materials. OpenAI Codex and its subagents assisted in reconstructing the proofs, auditing their scope, and preparing the manuscript. Zhili College, Tsinghua University, Beijing 100084, China
Email address: tangqy24@mails.tsinghua.edu.cn