Theorem Degree bounds for the recursively constructed family
✓ theorem proved

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.

Used by