Question 1: Let (W,S,M) be a Coxeter system, let w be the reduced word of an FC element, and let s\in S. Under what conditions is sw still the reduced word of an FC element?
We'll split Question 1 into two questions. First, under what conditions is sw still reduced. This is easy, and the answer is 'if and only if s is not a left descent of w', which can be detected easily by our descent test. Second, if sw is still reduced, under what conditions does sw still represent an FC element? Throughout the rest of the summer, when we call a factorization w=xy 'reduced', we mean we have l(w)=l(x)+l(y) where l is the Coxeter length.
To answer the second question, let's set up some notation. Let w_1 be the beginning segment of w where all letters commute with s. For example, in our usual setup for type A, if s=3 and w= 1564732, then w_1=156. Note that we can easily obtain w_1 from w via a slicing operation, namely, w_1= w[:i] where i it the minimum index for which m(w[i],s) != 2.
Let's also recall that a convex chain in a poset P is an chain of elements x_1,x_2,...,x_k such that
(i) [the 'chain' condition] x_i < x_{i+1} for all i\in {1,...,k-1};
(ii)[the 'convex' condition] if some two elements x_i, x_j from the chain and some element x from the poset P satisfies x_i < x < x_j in the partial order, then x is itself in the chain, i.e., x \in {x_1,...,x_k}.
Finally, let's recall Lemma 4.1 from Stembridge's paper and use a left-side analog of that lemma, which says that if sw is still reduced but no longer represents an FC element, then there is a unique t\in S such that m(s,t)>2 and the heap H(w) of w contains a convex chain
(*) t_1 < s_1 < t_2 < s_2 <...
which has m(s,t)-1 elements in it, where for s_1 stands for the first (=leftmost) (occurrence of) t in the word w, s_1 is the first s in w, t_2 is the second t in w, etc. In fact the proof of the lemma says a bit more, namely, in the heap H(sw) of sw, the 'new' s, which we'll call s_0, must form a convex chain
(**) s_0 < (t_1 < s_1 < t_2 < s_2 <...)
with the chain in (*).
Proposition: Let w be the reduced word of an element and let s\in S. Suppose sw is still reduced. Let w_1 be as defined before, and let u_1 be the remaining part of w, so that w=w_1u_1. Let t be the first letter of u_1 (so m(s,t)\ge 3 by the definition of w_1). Then sw no longer represents an FC element if and only if the following conditions simultaneously hold:
(1) t is a left descent of u_1.
(2) s is a left descent of the result of removing the t of Step (1) from u_1; we'll call this result u_2. For example, if u_1 = 4732 and t=4, then u_2=732. By our setup, in this case the t from 1 would be the very first letter in u_1.
(3) t is a left descent of the result of removing the s of Step (2) from u_2; we'll call this result u_3.
...
(m-1) the appropriate element x from {s,t} (the thing we'd naturally get when alternating in s and t in these m-1 steps, depending on parity of m) is a left descent of the result of removing the descent in of Step (m-2) from u_{m-2}; we'll call this result u_{m-1}.
Proof: We've explained how the 'if' direction is easy, for if (1)--(m-1) all hold we can move the new s to the right until it's immediately left to the t from (1), then use (1)--(m-1) to successively move the left descents in steps (2)--(m-1) to the left to form a convex chain stst..., which implies that sw no longer expresses an FC element.
So it remains to prove the 'only if' direction. To do so we invoke Stembridge's lemma. If sw no longer represents an FC element, then we can find the convex chain t_1<s_1<t_2... as in the lemma. Let's rename the chain x_1, x_2,..., x_{m-2}, x_{m-1}, so that x_1 is t_1, x_2 is s_1, ... . We claim that
(a) if y is a letter which appears in the word w between x_1 and x_{m-2}, then y commutes with s and also with t;
(b) if y is a letter which appears in the word w between x_{m-2} and x_{m-1}, then y commutes with x_{m-1}.
Note that the claim certainly implies (1)--(m-1), with x_i sufficing as the left descent desired in Step (i) for each i.
The observation is easy to prove, too. If m(s,t)=3, (a) is vacuously true and we just need to show (b), i.e., that between x_1=t_1 and x_2=s_1 every letter y commutes with x_2, which is an s. If this is not the case, y would be an element in H(w) outside the chain s_0<t_1<s_1 with the property that s_0<x<s_1, contradicting convexity of the chain (**). Now assume m(s,t)>4. Then to check (a), note that there must be at least one s from the chain (**), say s_i, which appears before y in w and at least one s from (**), say s_j, which appears after y in w, so y must commute with s, for otherwise we'd get the same violation of convexity with the chain s_i-y-s_j. Similarly, there's at least one t from (**) before y and after y, so y must commute with t, proving (a). Finally, to prove (b), note that if y doesn't commute with x_{m-1} then it also doesn't commute with x_{m-3}, whence the chain x_{m-3}-y-x_{m-1} would violate the convexity of (**), contradiction. The proof is now complete (though you can probably simplify this last paragraph a bit).
TODO: Write a function still_reduced_fc(s,w,M) to test if sw is still reduced using the criteria from the above discussion.