Minimum recurrence length after a new discrepancy ($L^{\prime }\ge r+1-L$)

Suppose a connection polynomial $C$ of degree at most $L$, with recurrence span $L$ gives zero recurrence discrepancies through index $r-1$ but a nonzero discrepancy at $r$. If a polynomial $D$ of span $L^{\prime }$ successfully explains the prefix through $r$ and $L+L^{\prime }\le r$, evaluate the coefficient at $r$ in the convolution $(CD)x$. Applying $D$ first makes it zero. Applying $C$ first leaves its nonzero discrepancy at $r$, because the earlier discrepancies vanish and $D$ has constant coefficient one. This contradiction gives the displayed lower bound. It is the minimality step used by the Berlekamp-Massey algorithm; the algorithm cancels the new discrepancy with a shifted earlier failed polynomial.