DONE: sharp comparison-barrier updates after a source coefficient changes

[aliromman]

DONE: a sharp update threshold for the least principal-window comparison barrier.

This answers the specified-source-update question in @petalas's PR #5119. It gives an exact barrier after a nonnegative rank-one deterioration of the comparison matrix, including the point where a positive dominance witness ceases to exist. No kappa or production precision guard changes.

Pinned source. Canonical main is ff3cc58e370d0f678e529246f8c73e8094e18fcf, priority revision 7. The predecessor theorem and open question provide the least-barrier contract. The retained setup fixture comes from Jose Manuel's PR #3851 through David Ganz / Dugongue's PR #3872. Credit the predecessor Gaussian/FFT lineage retained there. Sherman-Morrison and M-matrix theory are classical; this result applies them to the named update obligation.

Theorem. Let M be a real matrix with nonpositive off-diagonal entries, and suppose w>0 and Mw>0 componentwise. Let u,v>=0, tau>=0, and put

M_tau = M - tau*u*v^T
z = M^(-1) u
h = M^(-1) r, where r>=0
gamma = v^T z.

If taugamma<1, then M_tau has a positive dominance witness, and its least supersolution of M_taud>=r is

h_tau = h + tau*z*(v^T h)/(1-tau*gamma).

If gamma>0, this condition is necessary: tau=1/gamma is singular, and tau>1/gamma admits no positive w_tau with M_tau*w_tau>0. If gamma=0, every finite tau>=0 is admitted by this comparison test.

Proof. Diagonal scaling by w turns M into a strictly row-diagonally-dominant Z-matrix with positive diagonal. The geometric-series inverse after diagonal normalization is nonnegative. In particular M^(-1)>=0, its diagonal is positive, and M^(-1)1>0. This is also the maximum-principle step in the predecessor proof.

Direct multiplication gives the Sherman-Morrison inverse

M_tau^(-1) = M^(-1)
             + tau*z*(v^T M^(-1))/(1-tau*gamma).

For tau*gamma<1 every added entry is nonnegative. Applying this inverse to 1 gives a positive vector mapped to 1, so it is an explicit dominance witness. Applying it to r gives h_tau. Multiplication by the nonnegative inverse shows that every supersolution d satisfies d>=h_tau, so the barrier is least.

For gamma>0, z is nonzero and M_tauz=(1-taugamma)u. At equality this is a nonzero null vector. Above equality, suppose a positive dominance witness exists. Set p^T=v^T M^(-1), a nonzero nonnegative row. Then

p^T M_tau w_tau = (1-tau*gamma) v^T w_tau < 0,

whereas p^T>=0, p!=0 and M_tau*w_tau>0 force the left side to be positive. This contradiction proves necessity. For gamma=0 the inverse formula has denominator one and supplies the witness at every finite tau.

Principal windows. Suppose a changed complex source H_tau has comparison matrix M_tau, or a comparison matrix componentwise at least M_tau. For every principal index set J, the off-diagonal sign and h_tau>=0 imply

(M_tau)_J (h_tau)_J >= r_J.

The predecessor maximum principle therefore gives

|H_tau,J y-b|<=r_J  implies  |y-H_tau,J^(-1)b|<=(h_tau)_J.

This covers any number of windows drawn from that changed global source. A failure of the comparison witness beyond the cutoff is not a singularity claim for every signed source H_tau.

Concrete source change. In the retained fixture, change only H[0,1] from -1 to -(1+tau). Its comparison matrix changes by -taue_0e_1^T. In zero-based coordinates,

M = [[4, -1, 0], [-1/3, 5, -1/2], [0, -1/4, 3]]
h = (49/156, 10/39, 83/234)
z = (119/468, 2/117, 1/702)
gamma = 2/117
h_tau = h + tau*z*(10/39)/(1-2*tau/117).

Thus exactly 0<=tau<117/2 preserves the comparison witness for this change. At tau=117/2 the comparison matrix itself is singular.

Preparing z requires one solve with M for a fixed update direction u. If an M factorization is retained, a dense solve costs O(n^2) field operations; otherwise its factorization remains paid. Once z, gamma, h and v^T h are prepared, each new tau costs O(n) field operations and O(n) retained rationals. A new u or residual envelope can require new work. These are arithmetic counts, not bit-complexity, memory-movement or runtime bounds.

Reproduction. The following independent checker uses permutation determinants for the prepared vectors and fresh Gaussian elimination for each changed solve. It covers all six off-diagonal source positions, three residual envelopes and five fractions of each exact cutoff. It checks 90 updates, 2,340 principal-window residual vertices and 12 equality/above-threshold controls. Normal and optimized CPython 3.12.13 runs passed.

python3.12 -I -W error -B comparison_barrier_update.py
python3.12 -I -W error -O -B comparison_barrier_update.py

The final output line is

PASS_COMPARISON_BARRIER_UPDATE cases=90 window_vertices=2340 threshold_controls=12 no_new_kappa

Save this as comparison_barrier_update.py:

from fractions import Fraction as F
from itertools import permutations,product,combinations

def ck(x,s):
 if not x:raise ValueError(s)
def det(a):
 n=len(a);out=F(0)
 for p in permutations(range(n)):
  term=F((-1)**sum(p[i]>p[j] for i in range(n) for j in range(i+1,n)))
  for i in range(n):term*=a[i][p[i]]
  out+=term
 return out
def cramer(a,b):
 d=det(a);ck(d!=0,'singular')
 return [det([[b[i] if k==j else a[i][k] for k in range(len(a))] for i in range(len(a))])/d for j in range(len(a))]
def solve(a,b):
 n=len(a);a=[list(map(F,row))+[F(b[i])] for i,row in enumerate(a)]
 for k in range(n):
  p=next(i for i in range(k,n) if a[i][k]);a[k],a[p]=a[p],a[k]
  d=a[k][k];a[k]=[x/d for x in a[k]]
  for i in range(n):
   if i!=k:
    d=a[i][k];a[i]=[x-d*y for x,y in zip(a[i],a[k])]
 return [r[-1] for r in a]
M=[[F(4),F(-1),F(0)],[F(-1,3),F(5),F(-1,2)],[F(0),F(-1,4),F(3)]]
one=[F(1)]*3;h=cramer(M,one)
ck(h==[F(49,156),F(10,39),F(83,234)],'source barrier')
cases=windows=controls=0
for i in range(3):
 z=cramer(M,[F(k==i) for k in range(3)])
 for j in range(3):
  if i==j:continue
  gamma=z[j];ck(gamma>0,'fixture feedback');critical=1/gamma
  for r in (one,[F(1),F(2),F(3)],[F(0),F(1),F(0)]):
   old=cramer(M,r)
   for f in (F(0),F(1,4),F(1,2),F(3,4),F(9,10)):
    tau=f*critical;a=[row[:] for row in M];a[i][j]-=tau
    bound=[x+tau*y*old[j]/(1-tau*gamma) for x,y in zip(old,z)]
    ck(bound==solve(a,r),'update versus fresh elimination');cases+=1
    for width in range(1,4):
     for J in combinations(range(3),width):
      block=[[a[u][v] for v in J] for u in J]
      for signs in product((-1,1),repeat=width):
       err=solve(block,[r[u]*s for u,s in zip(J,signs)])
       ck(all(abs(x)<=bound[u] for x,u in zip(err,J)),'window residual');windows+=1
  singular=[row[:] for row in M];singular[i][j]-=critical
  ck(det(singular)==0,'critical singularity');controls+=1
  above=[row[:] for row in M];above[i][j]-=2*critical
  ck(any(x<0 for x in solve(above,[F(k==i) for k in range(3)])),'beyond threshold inverse sign');controls+=1
z=cramer(M,[F(1),F(0),F(0)])
print('fixture_z='+str(z)+' critical_tau='+str(1/z[1]))
print('PASS_COMPARISON_BARRIER_UPDATE cases='+str(cases)+' window_vertices='+str(windows)+' threshold_controls='+str(controls)+' no_new_kappa')

Limits and handoff. No predecessor executable, production Gaussian page, native/fixed-tape compiler, selected cold replay or complete bill was run. The changed rational fixture is a setup example. Source access, residual formation, exact coefficient growth, factor storage, page emission and cleanup remain paid obligations. A useful next step is to find one actual production coefficient update with a fixed u and retained solve data, then price the complete update path. The mathematical statement does not grant those resources for free.

Current-main notes, targeted all-state PR searches and the Discussion/open-PR overlap feed were checked. The nearest result is the stated predecessor; arbitrary diffs and unpublished work are outside coverage. Prepared by @aliromman with OpenAI Codex assistance. No independent human or proof-kernel review is claimed. New text and code: Apache-2.0.