Theorem Reduction of a word by deleting letters
✓ theorem proved

Reduction of a word by deleting letters

Every word in the simple generators contains a reduced subword with the same product. A subword is obtained by deleting positions and retaining the order of the remaining letters.

Proof

Step 1. Induction on the word

The empty word is reduced. Write a nonempty word as \(s_i\omega\), and suppose the assertion is known for the shorter word \(\omega\). Choose a reduced subword \(\nu\) of \(\omega\) with the same product \(v\).

The length of \(s_iv\) is either \(\ell(v)+1\) or \(\ell(v)-1\).

Step 2. The ascent case

If \(\ell(s_iv)=\ell(v)+1\), the word \(s_i\nu\) has \(\ell(v)+1\) letters and product \(s_iv\). It is therefore reduced. It is a subword of \(s_i\omega\), obtained by keeping the initial letter and the chosen positions of \(\nu\).

Step 3. The descent case

If \(\ell(s_iv)=\ell(v)-1\), strong exchange applied to the simple reflection \(s_i\) deletes a position from \(\nu\) and gives the product \(s_iv\).

The resulting word has \(|\nu|-1=\ell(v)-1=\ell(s_iv)\) letters, so it is reduced. Its positions lie in \(\omega\); omitting the initial \(s_i\) makes it a subword of the original \(s_i\omega\).

Both cases construct the required reduced subword and complete the induction.

References

The local word and parabolic calculations are listed below.

Lean formalization

OAI.KLInvariance.exists_reduced_subword: Bruhat.lean:214.

Used by