[proofplan] We use the definition of Bruhat order in terms of reduced subwords of some reduced expression for the upper element, and prove that the resulting set of elements is independent of the chosen reduced expression for $w$. By Matsumoto's theorem, any two reduced expressions for $w$ are connected by braid moves, so it is enough to verify invariance under one braid move. The local verification reduces to the rank-two Coxeter subgroup generated by the two simple reflections appearing in the braid move, where the reduced subwords of the two alternating words give exactly the same elements. Chaining these one-move invariances transfers the subword condition to the fixed reduced expression $s_1\cdots s_r$. [/proofplan] [step:Define the reduced-subword set associated to a word] Let $(W,S)$ be the Coxeter system from the statement, let $(m_{st})_{s,t\in S}$ be its Coxeter matrix, and let $\ell:W\to\mathbb N\cup\{0\}$ denote its length function. Let $a=(a_1,\dots,a_m)$ be a finite word in the alphabet $S$. Define \begin{align*} E(a):=\{a_{j_1}\cdots a_{j_p}\in W:0\le p\le m,\ 1\le j_1<\cdots<j_p\le m,\ \ell(a_{j_1}\cdots a_{j_p})=p\}. \end{align*} For $p=0$, the product is the identity element $1_W$, and the corresponding empty expression is reduced. We use the reduced-expression characterization of the Bruhat order on a Coxeter group: for $y,w\in W$, one has $y\le w$ if and only if $y\in E(a)$ for some reduced expression $a$ of $w$. Thus the theorem will follow once we prove that $E(a)$ is the same for all reduced expressions $a$ of the fixed element $w$. [/step] [step:Reduce independence of the expression to invariance under one braid move] Let $a=(a_1,\dots,a_r)$ and $a'=(a'_1,\dots,a'_r)$ be two reduced expressions for the same element $w\in W$. By Matsumoto's theorem for Coxeter systems, there exists a finite sequence of reduced expressions \begin{align*} a=a_0,a_1,\dots,a_N=a' \end{align*} for $w$ such that each $a_{q+1}$ is obtained from $a_q$ by replacing one alternating braid block \begin{align*} sts\cdots \end{align*} of length $m_{st}$ by the other alternating braid block \begin{align*} tst\cdots \end{align*} of the same length, where $s,t\in S$ and $m_{st}<\infty$. Therefore it is enough to prove that $E(a_q)=E(a_{q+1})$ for a single braid move. Equality along the whole sequence then gives $E(a)=E(a')$. [/step] [step:Verify reduced-subword invariance inside one rank-two braid block] Fix distinct $s,t\in S$ with finite Coxeter exponent $m=m_{st}$. Let \begin{align*} b_s=(s,t,s,t,\dots) \end{align*} be the alternating word of length $m$ beginning with $s$, and let \begin{align*} b_t=(t,s,t,s,\dots) \end{align*} be the alternating word of length $m$ beginning with $t$. We prove that \begin{align*} E(b_s)=E(b_t). \end{align*} Let $W_{\{s,t\}}\le W$ denote the standard parabolic subgroup generated by $\{s,t\}$. The Coxeter relations for this subgroup are \begin{align*} s^2=t^2=1_W,\qquad (st)^m=1_W. \end{align*} The rank-two Coxeter subgroup $W_{\{s,t\}}$ is the finite dihedral Coxeter group with Coxeter exponent $m$. Its reduced elements are exactly $1_W$, the two alternating products of each length $1\le q<m$, and the unique longest element of length $m$, represented both by $b_s$ and by $b_t$; this is the standard normal form for the finite dihedral Coxeter system generated by $s$ and $t$. Indeed, the only defining reductions in the alphabet $\{s,t\}$ are deletion of adjacent equal letters and replacement of an alternating block of length $m$ by the other alternating block of length $m$, so an alternating word of length below $m$ is reduced, while an alternating word of length $m$ represents the unique longest element of the finite dihedral subgroup. Every reduced subword of $b_s$ is an element of this list, because it is a reduced word in the alphabet $\{s,t\}$ of length at most $m$. Conversely, every element in the list occurs as a reduced subword of $b_s$: the alternating product of length $q<m$ beginning with $s$ is obtained from the first $q$ positions of $b_s$, the alternating product of length $q<m$ beginning with $t$ is obtained from positions $2,\dots,q+1$, and the longest element is obtained from the full word. Every reduced subword of $b_t$ is also an element of the same finite dihedral normal-form list. Conversely, every element in the list occurs as a reduced subword of $b_t$: the identity comes from the empty subword, the alternating product of length $q<m$ beginning with $t$ is obtained from the first $q$ positions of $b_t$, the alternating product of length $q<m$ beginning with $s$ is obtained from positions $2,\dots,q+1$, and the longest element is obtained from the full word. Hence $E(b_s)=E(b_t)$. [guided] The braid move is local, so we isolate the subgroup where it happens. Let $W_{\{s,t\}}\le W$ be the subgroup generated by the two simple reflections $s$ and $t$. Since the braid move has finite length $m=m_{st}$, the defining rank-two Coxeter relations in this subgroup are \begin{align*} s^2=t^2=1_W,\qquad (st)^m=1_W. \end{align*} The relevant rank-two fact is the standard normal form for the finite dihedral Coxeter system generated by $s$ and $t$: the reduced elements of $W_{\{s,t\}}$ are exactly the identity $1_W$, the two alternating products of each length $q$ with $1\le q<m$, and the unique element of length $m$. The length-$m$ element has two reduced expressions, namely the alternating word beginning with $s$ and the alternating word beginning with $t$. Thus the two full braid blocks \begin{align*} b_s=(s,t,s,t,\dots) \end{align*} and \begin{align*} b_t=(t,s,t,s,\dots) \end{align*} represent the same element of $W_{\{s,t\}}$. Now we compare their reduced subwords. First consider $b_s$. Any reduced subword of $b_s$ is a reduced word in the alphabet $\{s,t\}$ and has length at most $m$, so it must be one of the elements listed above. Conversely, every element in the list is actually obtained from $b_s$. The identity comes from the empty subword. For $1\le q<m$, the alternating word of length $q$ beginning with $s$ is obtained by selecting the first $q$ positions of $b_s$. The alternating word of length $q$ beginning with $t$ is obtained by selecting positions $2,\dots,q+1$; this is allowed because $q<m$, so $q+1\le m$. Finally, the length-$m$ element is obtained by selecting every position of $b_s$. Now consider $b_t$ directly. Any reduced subword of $b_t$ is a reduced word in the alphabet $\{s,t\}$ of length at most $m$, so it appears in the same finite dihedral normal-form list. The identity comes from the empty subword. For $1\le q<m$, the alternating word of length $q$ beginning with $t$ is obtained by selecting the first $q$ positions of $b_t$, and the alternating word of length $q$ beginning with $s$ is obtained by selecting positions $2,\dots,q+1$; again $q<m$ gives $q+1\le m$. The length-$m$ element is obtained by selecting every position of $b_t$. Therefore $b_s$ and $b_t$ have exactly the same elements represented by reduced subwords: \begin{align*} E(b_s)=E(b_t). \end{align*} This is the only local fact needed for braid moves: the two sides of the braid relation may look different as words, but their reduced subwords represent the same rank-two elements. [/guided] [/step] [step:Lift the rank-two comparison through an arbitrary braid move] Suppose a reduced expression $a$ is obtained by concatenating three words \begin{align*} a=u\,b_s\,v, \end{align*} where $u$ and $v$ are finite words in $S$, and suppose $a'$ is obtained by the corresponding braid replacement \begin{align*} a'=u\,b_t\,v. \end{align*} Here $b_s$ and $b_t$ are the alternating rank-two blocks from the previous step. We prove $E(a)\subseteq E(a')$. Let $x\in E(a)$. Then $x$ is represented by a reduced subword of $a$. Split this chosen subword according to the three blocks $u$, $b_s$, and $v$. Let $u_0\in W$ be the product of the chosen letters from $u$, let $z\in W_{\{s,t\}}$ be the product of the chosen letters from $b_s$, and let $v_0\in W$ be the product of the chosen letters from $v$, preserving their original orders. Then \begin{align*} x=u_0zv_0. \end{align*} Because the entire chosen subword is reduced, the chosen subword inside $b_s$ is reduced as well; otherwise replacing it by a shorter expression for the same element would shorten the entire chosen expression for $x$. By the rank-two comparison, $z$ is represented by a reduced subword of $b_t$. Keeping the same selected letters from $u$ and $v$, and replacing only the selected subword inside $b_s$ by this reduced subword inside $b_t$, gives a subword of $a'$ whose product is again $u_0zv_0=x$. Since the word length of $x$ is the length of the original reduced chosen subword, this new expression for $x$ is also reduced. Hence $x\in E(a')$. To prove $E(a')\subseteq E(a)$, let $x\in E(a')$ and choose a reduced subword of $a'=u\,b_t\,v$ representing $x$. Split the chosen letters across $u$, $b_t$, and $v$, giving products $u_0\in W$, $z\in W_{\{s,t\}}$, and $v_0\in W$ with $x=u_0zv_0$. The selected subword inside $b_t$ is reduced, since otherwise replacing that part by a shorter expression for the same element would shorten the chosen reduced expression for $x$. By $E(b_s)=E(b_t)$, the element $z$ is represented by a reduced subword of $b_s$. Keeping the selected letters from $u$ and $v$ and replacing only the selected subword inside $b_t$ by this reduced subword inside $b_s$ gives a reduced subword of $a$ with product $x$. Hence $x\in E(a)$. Therefore \begin{align*} E(a)=E(a'). \end{align*} [/step] [step:Transfer the subword condition to the fixed reduced expression] Let \begin{align*} w=s_1s_2\cdots s_r \end{align*} be the fixed reduced expression from the statement, and let $a=(s_1,\dots,s_r)$. By the previous steps, $E(a)$ agrees with $E(a')$ for every reduced expression $a'$ of $w$. If $y\le w$, then by the definition of Bruhat order there exists some reduced expression $a'$ of $w$ such that $y\in E(a')$. Since $E(a')=E(a)$, there are indices \begin{align*} 1\le i_1<\cdots<i_k\le r \end{align*} with $0\le k\le r$ such that \begin{align*} y=s_{i_1}\cdots s_{i_k} \end{align*} and this expression is reduced. Conversely, if such a reduced subword of the fixed expression exists, then $y\in E(a)$. Since $a$ is itself a reduced expression for $w$, the definition of the Bruhat order gives $y\le w$. This proves both implications and completes the proof. [/step]