Degree bounds for the recursively constructed family
The recursive family satisfies \[ P_{x,x}=1,\qquad P_{x,y}=0\quad(x\not\le y), \] and, for \(x<y\), \[ 2\,\operatorname{natDegree}(P_{x,y})<d(x,y). \] For every pair, with the source's natural rank difference \(\delta(x,y)=\max\{\ell(y)-\ell(x),0\}\), \[ \operatorname{natDegree}(P_{x,y})\le\delta(x,y). \]
Proof
Step 1. Read the two initial branches
For \(x=y\), Bruhat reflexivity selects the diagonal branch of the definition, giving one.
For \(x\not\le y\), the first branch gives zero. These values have natural degree zero.
Step 2. Establish positive rank for a strict interval
If \(x<y\), strict Bruhat comparison gives \(\ell(x)<\ell(y)\). Hence \(d=d(x,y)>0\).
The recursive branch has the form \(P_{x,y}=-\operatorname{low}_dD_{x,y}\). The lower-half degree theorem applies because \(d>0\), and negation preserves natural degree. Therefore \[ 2\,\operatorname{natDegree}(P_{x,y}) =2\,\operatorname{natDegree}(\operatorname{low}_dD_{x,y})<d. \]
Step 3. Deduce the weak bound for all pairs
On a strict comparable pair, the strict inequality implies \(\operatorname{natDegree}(P_{x,y})\le d(x,y)\).
On the diagonal, the natural degree and rank difference are both zero. When \(x\not\le y\), the polynomial is zero, and \(0\le\delta(x,y)\). These cases prove the all-pair weak bound.
The weak bound supplies the degree hypothesis when a later proof reflects a product \(R_{x,z}P_{z,y}\). The strict bound supplies uniqueness.
References
The local source declarations below give the construction and proof.
Lean formalization
OAI.KLInvariance.CanonicalP.polynomial_diagonal: CanonicalKL.lean:86.
OAI.KLInvariance.CanonicalP.polynomial_zero: CanonicalKL.lean:91.
OAI.KLInvariance.CanonicalP.polynomial_strict_degree: CanonicalKL.lean:104.
OAI.KLInvariance.CanonicalP.polynomial_degree: CanonicalKL.lean:113.