Theorem The length-difference bound for ordinary R-polynomials
✓ theorem proved

The length-difference bound for ordinary R-polynomials

For every \(x,y\), \[ \operatorname{natDegree}R_{x,y} \le\delta(x,y),\qquad \delta(x,y)=\max\{\ell(y)-\ell(x),0\}. \] Here the difference in the maximum is an integer. Lean's natural-number subtraction gives this \(\delta\), and its \(\operatorname{natDegree}(0)\) is zero. For \(x\le y\), the bound is the ordinary length difference.

Proof

Step 1. Establish the zero and diagonal cases

Induct strongly on \(\ell(y)\), for all \(x\). If \(x\not\le y\), the polynomial is zero, whose natural degree is zero and hence at most \(\delta(x,y)\).

If \(x=y\), the polynomial is one and has degree zero, equal to \(\delta(x,x)\).

Now assume \(x<y\). Put \(d=\ell(y)-\ell(x)\), so \(d\ge1\).

Step 2. Use a left descent of the upper endpoint

Since \(y\ne1\), choose \(s\) with \(sy<y\). Write \(v=sy\), so \(\ell(v)=\ell(y)-1\). All recurrence terms have the smaller upper endpoint \(v\).

If \(sx<x\), both endpoint lengths decrease by one. The recurrence is \(R_{x,y}=R_{sx,v}\), and \[ \delta(sx,v)=\ell(v)-\ell(sx)=d. \] The induction hypothesis proves the bound.

Step 3. Bound the first term in the ascent branch

Suppose \(sx>x\). The recurrence is \[ R_{x,y}=(q-1)R_{x,v}+qR_{sx,v}. \] Since \(d\ge1\), we have \(\delta(x,v)=d-1\). By induction and the product degree inequality, \[ \operatorname{natDegree}\bigl((q-1)R_{x,v}\bigr) \le1+\operatorname{natDegree}R_{x,v} \le1+(d-1)=d. \]

Step 4. Bound the second term, including its support case

If \(sx\not\le v\), then \(R_{sx,v}=0\), so this term has natural degree zero.

If \(sx\le v\), the length inequality gives \[ \ell(x)+1=\ell(sx)\le\ell(v)=\ell(y)-1. \] Thus \(d\ge2\), and \(\delta(sx,v)=d-2\). Induction gives \[ \operatorname{natDegree}(qR_{sx,v}) \le1+(d-2)=d-1\le d. \]

Step 5. Combine the two bounds

The degree of a sum is at most the maximum of the degrees of its summands. Steps 3–4 therefore give \(\operatorname{natDegree}R_{x,y}\le d\), completing the induction.

For \(R_{1,s}=q-1\), the bound is one; for \(R_{1,st}=(q-1)^2\), it is two. These examples have the full allowed degree.

References

The local source declarations below give the construction and proof.

Lean formalization

OAI.KLInvariance.OrdinaryR.polynomial_degree: OrdinaryR.lean:125.

Used by