height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}hc)a+q^{|fa|}((fa\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}g)\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}hc)b$
$\displaystyle\phantom{{}=}+q^{|fa|+|gb|}((fa\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}gb)\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}h)c.$

By induction hypothesis, we get

$\displaystyle(fa\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}gb)\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}hc$
$\displaystyle=(f\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}(gb\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}hc))a+q^{|fa|}(fa\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}(g\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}hc))b$
$\displaystyle\phantom{{}=}+q^{|fa|+|gb|}(fa\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}(gb\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}h))c.$

Now, applying 8 twice, we also get

$\displaystyle fa\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}(gb\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}hc)$
$\displaystyle=fa\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}((g\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}hc)b+q^{|gb|}(gb\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}h)c)$
$\displaystyle=(f\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}(gb\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}hc))a+q^{|fa|}[(fa\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}(g\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}hc))b+q^{|gb|}(fa\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}(gb\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}h))c].$

For the reciprocal relation, one can proceed by straightforward induction on
$|u|+|v|$. Or, it can be seen as a consequence of the previous two Sections
6.1 and 6.1. The $q$-shuffles $u\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}v$ and
$v\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}u$ clearly have the same
support. Let $w$ be a word in this support and consider the specific
factorization $w=u_{1}v_{1}u_{2}v_{2}\cdots u_{n}v_{n}u_{n+1}$ with
$u=u_{1}\cdots u_{n}u_{n+1},\ u_{i}\in A^{*}$ and $v=v_{1}\cdots v_{n},\
v_{i}\in A$. For each $v_{i}$, the contribution to
$u\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}v$ given by Section 6.1
is $q^{|u_{1}\cdots u_{i}|}$ and the one to $v\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}u$ given by Section 6.1
is

$q^{|u_{i+1}\cdots u_{n+1}|}=q^{|u|-|u_{1}\cdots u_{i}|}.$

Finally, with $n=|v|$,

$\prod_{i=1}^{n}q^{|u|-|u_{1}\cdots
u_{i}|}=q^{|u|\,|v|}\prod_{i=1}^{n}\left(\frac{1}{q}\right)^{|u_{1}\cdots
u_{i}|}.$

∎

As a consequence of Theorem 4.1 and Section 6.1, we are now able to prove
Section 6.1.

###### Proof of Section 6.1.

If $u$ is not a subword of $w$, then both sides of 10 are zero. We can now
assume that $u$ appears at least once as a subword of $w$. Let us fix one
particular occurrence of $u=u_{1}\cdots u_{n}$ in $w$:

$w=w_{0}u_{1}w_{1}\cdots w_{n-1}u_{n}w_{n}$

where $u_{i}\in A$ and $w_{i}\in A^{*}$ for all $i$. Let $x=w_{0}w_{1}\cdots
w_{n}$. The word $w$ appears in the support of $u\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}x$. From Section 6.1,
this particular occurrence of $u$ contributes to the coefficients of $w$ in
$u\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}x$ with a monomial

$\prod_{i=1}^{n}q^{|w_{i}\cdots w_{n}|}.$

Now from the combinatorial interpretation of $\binom{w}{u}_{\\!\\!q}$ given by
Theorem 4.1, the set of indices where the letters of $u$ within $w$ occur
(counting from $1$ and from the right, for the occurrence of $u$ fixed since
the beginning) is

$Y=\\{|w_{n}|+1,|w_{n-1}w_{n}|+2,\ldots,|w_{1}\cdots w_{n}|+n\\}$

and therefore, the contribution to $\binom{w}{u}_{\\!\\!q}$ is given by

$q^{s(Y)-\frac{n(n+1)}{2}}=q^{\sum_{i=1}^{n}|w_{i}\cdots w_{n}|}.$

This is enough to conclude with the proof. ∎

In view of Section 6.1, if we permute the factors of the $q$-shuffle, 10
becomes

$\langle A^{*}\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}_{q}u,w\rangle=q^{|u|\cdot(|w|-|u|)}\binom{w}{u}_{\\!\\!q}(1/q),$

where on the right-hand side the $q$-binomial coefficient is evaluated at
$1/q$.

###  6.2 Deformed infiltration

Inspired by [3], where the authors investigate various products defined by a
recurrence relation, one could define several $q$-infiltrations using
recurrences of the form
$u\uparrow_{q}\varepsilon=\varepsilon\uparrow_{q}u=1\cdot u$ and

$ua\uparrow_{q}vb=(u\uparrow_{q}vb)a+q^{|ua|}(ua\uparrow_{q}v)b+q^{\alpha(ua,vb)}\,\delta_{a,b}(u\uparrow_{q}v)a$
(11)

for every choice of a map $\alpha:A^{*}\times A^{*}\to\mathbb{N}$. In [2], the
choice is $\alpha(ua,vb)$ to be the constant function $1$. Roughly speaking,
with such a choice, when building a term $q^{n}w$ of a monomial in the
infiltration product, every application of the third term will increase the
exponent of $q^{n}$ by $1$. So it will only record how many times the third
term was used (see Section 6.2).

As for the $q$-shuffle, we can extend the above definition to the
$q$-infiltration of a word $u\in A^{*}$ and a series
$s\in\mathbb{N}[q]\langle\langle A^{*}\rangle\rangle$ by

$u\uparrow_{q}s=\sum_{v\in A^{*}}\langle
s,v\rangle\,(u\uparrow_{q}v)\quad\text{ and }\quad s\uparrow_{q}u=\sum_{v\in
A^{*}}\langle s,v\rangle\,(v\uparrow_{q}u).$

For two series $s,t\in\mathbb{N}[q]\langle\langle A^{*}\rangle\rangle$, we
define

$s\uparrow_{q}t=\sum_{u,v\in A^{*}}\langle s,u\rangle\,\langle
t,v\rangle\,(u\uparrow_{q}v).$

From this definition, we have

$f\uparrow_{q}(g\uparrow_{q}h)=\sum_{v\in A^{*}}\langle
g\uparrow_{q}h,v\rangle\,(f\uparrow_{q}v).$

As an example,

$aba\uparrow_{q}a=(q^{3}+q^{2})aba^{2}+(q+1)a^{2}ba+(q^{\alpha(aba,a)}+q^{\alpha(a,a)})\,aba$

because, we have

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}aba}\uparrow_{q}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a}=q^{3}\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}aba}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a}+q^{2}\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}ab}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a}+q\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}ba}+1\,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}aba}+q^{\alpha(aba,a)}\,ab{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}a}+q^{\alpha(a,a)}\,{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}a}ba$

where the cyan color is used when letters are merged when using the third term
in 11. The reader may notice on this example, that the $q$-infiltration has
terms of maximal degree equal to the $q$-shuffle. This directly follows from
the definition 11 whose first two terms in the recurrence relation coincide
with the $q$-shuffle. We state this observation for our record.

Let $u,v$ be words. There exists a polynomial $P_{u,v}$ of degree less than
$|u|+|v|$ such that

$u\uparrow_{q}v=u\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}v+P_{u,v}.$

Moreover, $P_{u,v}=0$ if and only if $u$ and $v$ are on disjoint alphabets.

As we wish to recover the terms of $\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}_{q}$ as defined in Section
6.1, we do not have much freedom on the first two terms of the recurrence
relation. Even though this first result seems promising, we start this section
with a negative statement. Whatever the choice made for the function $\alpha$,
the $q$-infiltration product is not associative and the Chen–Fox–Lyndon
relation does not take place. In a second step, we focus on a specific choice
of $\alpha(ua,vb)=|ua|$.

The $q$-infiltration product (11) is not associative.

###### Proof.

Take $h=ab$, $f=ab$, $g=b$. The polynomial coefficients of $ab$ in
$(f\uparrow_{q}g)\uparrow_{q}h$ and $f\uparrow_{q}(g\uparrow_{q}h)$ are
respectively

$q^{\alpha(a,a)+\alpha(ab,b)+\alpha(ab,ab)}\text{ and
}q^{\alpha(a,a)+\alpha(b,ab)+\alpha(ab,ab)}.$

This leads to $\alpha(ab,b)=\alpha(b,ab)$. Now take $h=aba$, $f=ab$, $g=b$.
The coefficients of $aba$ in both products are again monomials and comparing
the exponents leads to the contradiction $\alpha(ab,b)=1+\alpha(b,ab)$. ∎

For classical binomial coefficients of words, resulting of the associativity
of the infiltration product, the following Chen–Fox–Lyndon relation holds true

$\forall f,g,h\in A^{*},\quad\binom{h}{f}\binom{h}{g}=\sum_{w\in A^{*}}\langle
f\uparrow g,w\rangle\binom{h}{w}.$ (12)

There is no such relation for $\uparrow_{q}$ defined by 11. As a counter-
example, take $h=ababa$, $f=aba$, $g=b$. On the one hand, we have

$\binom{h}{f}_{\\!\\!q}\binom{h}{g}_{\\!\\!q}=q^{9}+2q^{7}+2q^{5}+2q^{3}+q$

which only contains odd powers of $q$. On the other hand, we get

$f\uparrow_{q}g=q^{\alpha(ab,b)}aba+baba+(q+q^{2})\,abba+q^{3}\,abab$

and

$\sum_{w\in A^{*}}\langle
f\uparrow_{q}g,w\rangle\binom{h}{w}_{\\!\\!q}=1+q^{3}+q^{4}+q^{7}+q^{\alpha(ab,b)}(1+q^{2}+q^{4}+q^{6})$

which contains consecutive powers of $q$.

We now study the choice $\alpha(ua,vb)=|ua|$ in the definition to record some
more information into the corresponding exponent. Let $u,v$ be two finite
words over an alphabet $A$ and $a,b\in A$. The $q$-infiltration of $u$ and $v$
is defined recursively by

$u\Uparrow_{q}\varepsilon=\varepsilon\Uparrow_{q}u=1\cdot u;\quad
ua\Uparrow_{q}vb=(u\Uparrow_{q}vb)a+q^{|ua|}\left[(ua\Uparrow_{q}v)b+\delta_{a,b}(u\Uparrow_{q}v)a\right].$

We use a specific symbol $\Uparrow_{q}$ to distinguish from the general
situation 11. Reconsidering the same example as above

$aba\Uparrow_{q}a=(q^{3}+q^{2})aba^{2}+(q+1)a^{2}ba+(q^{3}+q)\,aba$

Had we chosen the map $\alpha$ to be the constant $1$, we would obtain $2q$ as
coefficient of $aba$ just meaning that $aba$ can be obtained in two ways
applying once the third term of the recurrence. Here, the exponents $q^{3}$
and $q$ give the information where the merge of letters $a$ occurred.

Recall that the valuation of a series $s\in\mathbb{K}\langle\langle
A^{*}\rangle\rangle$, denoted by $\operatorname{val}(s)$, is the least integer
$n$ such that the support of $s$ contains a monomial of degree $n$; by
convention $\operatorname{val}(0)=+\infty$. In the next statement,
$\binom{u}{v}_{\\!\\!q}\left(q^{-1}\right)$ means that the $q$-binomial
polynomial is evaluated at $1/q$. If we permute the order of the two factors,
the $q$-infiltration being non-symmetric, we may get a simpler expression. One
can compare this result with Section 6.1.

Let $u,v,w$ be words such that $|u|\geq|v|$. There exists a polynomial
$R_{u,v}$ such that $\operatorname{val}(R_{u,v})>|u|$ and

$u\Uparrow_{q}v=q^{1+|v|(|u|-1)-\frac{(|v|-2)(|v|-1)}{2}}\binom{u}{v}_{\\!\\!q}\left(q^{-1}\right)u+R_{u,v}.$

There exists a polynomial $S_{v,u}$ such that
$\operatorname{val}(S_{v,u})>|u|$ and

$v\Uparrow_{q}u=q^{|v|(|v|+1)/2}\binom{u}{v}_{\\!\\!q}u+S_{v,u}$

In particular, if $|u|\geq|v|,|w|$, then

$\langle
w\Uparrow_{q}(v\Uparrow_{q}u),u\rangle=q^{|w|(|w|+1)/2+|v|(|v|+1)/2}\binom{u}{w}_{\\!\\!q}\binom{u}{v}_{\\!\\!q}.$

We essentially follow the proof of [13, Lem. 6.3.16].

###### Proof.

Proceed by induction on $|v|=n$ and then $|u|=m$. If $v=\varepsilon$, the
formula holds for all $u\in A^{*}$. Assume that the formula holds for $n\geq
0$ and all $m\geq n$. To prove that it holds for $n+1$, first it holds for
$m=n+1$ because, in that case $|u|=|v|$, $u\neq v$ if and only if $u$ is not
in the support of $u\Uparrow_{q}v$ and $\binom{u}{v}_{\\!\\!q}=0$. If $u=v$,
then $\binom{u}{v}_{\\!\\!q}=1$ and
$1+|v|(|u|-1)-(|v|-2)(|v|-1)/2=|u|(|u|+1)/2$ which corresponds to merging
$|u|$ times the letters of the two words when computing the $q$-infiltration.

Now assume that the formula holds true for some $m\geq n+1$ and prove it for
$m+1$. Let $a,b\in A$. Recall that

$ua\Uparrow_{q}vb=(u\Uparrow_{q}vb)a+q^{|ua|}\left[(ua\Uparrow_{q}v)b+\delta_{a,b}(u\Uparrow_{q}v)a\right].$

We may apply three times the induction hypothesis and we get

$\displaystyle ua\Uparrow_{q}vb$
$\displaystyle=\left[q^{1+|vb|(|u|-1)-\frac{(|vb|-2)(|vb|-1)}{2}}\binom{u}{vb}_{\\!\\!q}\left(q^{-1}\right)u+R_{u,vb}\right]a$
$\displaystyle\phantom{=}+q^{|ua|}\,\left[q^{|1+|v|(|ua|-1)-\frac{(|v|-2)(|v|-1)}{2}}\binom{ua}{v}_{\\!\\!q}\left(q^{-1}\right)ua+R_{ua,v}\right]b$
$\displaystyle\phantom{=}+q^{|ua|}\,\left[\delta_{a,b}\,q^{1+|v|(|u|-1)-\frac{(|v|-2)(|v|-1)}{2}}\binom{u}{v}_{\\!\\!q}\left(q^{-1}\right)u+R_{u,v}\right]a$

The first exponent occurring in the above expression can be rewritten as

$\displaystyle 1+|vb|(|u|-1)-\tfrac{(|vb|-2)(|vb|-1)}{2}$
$\displaystyle=|ua|+1+|v|(|u|-1)-\tfrac{(|v|-2)(|v|-1)}{2}-|vb|.$

Hence we get that $ua\Uparrow_{q}vb$ is equal to

$q^{|ua|+1+|v|(|u|-1)-\frac{(|v|-2)(|v|-1)}{2}}\left[q^{-|vb|}\binom{u}{vb}_{\\!\\!q}\left(q^{-1}\right)+\delta_{a,b}\binom{u}{v}_{\\!\\!q}\left(q^{-1}\right)\right]ua+Q\\\
=q^{1+|vb|(|ua|-1)-\frac{(|vb|-2)(|vb|-1)}{2}}\binom{ua}{vb}_{\\!\\!q}\left(q^{-1}\right)ua+Q,$

where $\operatorname{val}(Q)>|u|+1$.

The structure of the proof for the second statement is similar to the first
part. We only mention the main argument where one proceeds by induction three
times:

$\displaystyle va\Uparrow_{q}ub$
$\displaystyle=\left[q^{|v|(|v|+1)/2}\binom{ub}{v}_{\\!\\!q}ub+S_{v,ub}\right]a+q^{|va|}\,\left[q^{|va|(|va|+1)/2}\binom{u}{va}_{\\!\\!q}u+S_{va,u}\right]b$
$\displaystyle\phantom{=}+q^{|va|}\,\left[\delta_{a,b}\,q^{|v|(|v|+1)/2}\binom{u}{v}_{\\!\\!q}u+S_{v,u}\right]a$
$\displaystyle=q^{|va|+|va|(|va|+1)/2}\binom{u}{va}_{\\!\\!q}ub+\delta_{a,b}\,q^{|va|+|v|(|v|+1)/2}\binom{u}{v}_{\\!\\!q}ua+Q$
$\displaystyle=q^{|va|(|va|+1)/2}\left[q^{|va|}\binom{u}{va}_{\\!\\!q}ub+\delta_{a,b}\,\binom{u}{v}_{\\!\\!q}ua\right]+Q,$

where $\operatorname{val}(Q)>|u|+1$ and observing that
$|va|+|v|(|v|+1)/2=|va|(|va|+1)/2$. ∎

##  7 Towards $p$-groups

In this section, we introduce what we call the $(u,\mathfrak{M})$-binomial
equivalence relation. In particular, we consider coarsest refinements222Recall
that an equivalence relation $\cong$ is a refinement of
$\sim_{u,\mathfrak{M}}$ if, for all words $w_{1},w_{2}$, $w_{1}\cong w_{2}$
implies $w_{1}\sim_{u,\mathfrak{M}}w_{2}$. We also say that
$\sim_{u,\mathfrak{M}}$ is coarser than $\cong$. $\equiv_{u,\mathfrak{M}}$ of
these relations that are congruences. This way, the quotient
$A^{*}/{\equiv_{u,\mathfrak{M}}}$ is a monoid. We further study this structure
and determine when it is a group. Moreover, we obtain information about its
order. As a corollary, we generalize Eilenberg’s theorem characterizing
$p$-group languages.

Let $M$ be a monoid and $\mu:A^{*}\to M$ be a monoid morphism. The monoid $M$
recognizes the language $L\subseteq A^{*}$ if there exists a subset $S$ of $M$
such that $L=\mu^{-1}(S)$. A language is recognizable if it is recognized by a
finite monoid. It is a well-known result that a language is recognizable if
and only if it is regular, i.e., there exists a _deterministic finite
automaton (DFA)_ that recognizes the language [11, Thm. 10.2.5].

Let $p$ be a prime. A language recognized by a $p$-group is a $p$-group
language. We follow Eilenberg’s classical textbook [7] where it is shown that
a language is a $p$-group language if and only if it is a Boolean combination
of languages of the form

$L_{v,r,p}:=\left\\{u\in A^{*}\mid\binom{u}{v}\equiv r\pmod{p}\right\\}.$ (13)

Let $\mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z}$ be the field of integers modulo
$p$ and let $\mathfrak{M}(q)$ be a non-zero polynomial of degree $d\geq 1$ in
$\mathbb{F}_{p}[q]$. Since $q$-deformed binomial coefficients are polynomials
in $\mathbb{Z}[q]$, their integer coefficients can be reduced modulo $p$ to
get a polynomial in $\mathbb{F}_{p}[q]$. Similarly to 13, we will consider the
languages of the form

$L_{v,\mathfrak{R},\mathfrak{M}}:=\left\\{u\in
A^{*}\mid\binom{u}{v}_{\\!\\!q}\equiv\mathfrak{R}\pmod{\mathfrak{M}}\right\\},$
(14)

where $\mathfrak{R}\in\mathbb{F}_{p}[q]$ is a polynomial of degree less than
$\deg(\mathfrak{M})$.

As a consequence of our treatment, we get a generalization of Eilenberg’s
theorem: a language is a $p$-group language if and only if it is a Boolean
combination of languages of the form 14 where $\mathfrak{M}=a(q-1)^{d}$ for
some integer $d\geq 1$ and non-zero $a\in\mathbb{F}_{p}$.

In order to lighten the proofs of our main results, we gather all required
preliminary definitions and results about polynomial algebra in the next
subsection.

###  7.1 Some polynomial algebra

We let $\mathbb{K}$ denote the finite ring
$\mathbb{F}_{p}[q]/\langle\mathfrak{M}\rangle$ of order $p^{d}$ and we let
$\mathbb{K}^{\star}$ denote the multiplicative group made of the units. Note
that $\mathbb{K}$ is a field if and only if $\mathfrak{M}$ is irreducible over
$\mathbb{F}_{p}$. As $(\mathbb{K},\cdot)$ is a finite semigroup with identity
$1$, for each $\mathfrak{P}\in\mathbb{K}$, two elements of the sequence
$1,\mathfrak{P},\mathfrak{P}^{2},\ldots$ will be equal. Considering the first
repetition, the least positive integers $i\geq 0$ and $k\geq 1$ such that

$\mathfrak{P}^{i}=\mathfrak{P}^{i+k}$
1$\mathfrak{P}$$\mathfrak{P}^{2}$$\cdots$$\mathfrak{P}^{i-1}$$\mathfrak{P}^{i}$$\mathfrak{P}^{i+1}$$\mathfrak{P}^{i+k-1}$$\vdots$

are respectively the _index_ and the _period_ of $\mathfrak{P}$ and are
denoted by $\operatorname{ind}(\mathfrak{P})$ and
$\operatorname{per}(\mathfrak{P})$ (the semigroup $\mathbb{K}$ being clear
from the context). Note that for an arbitrary semigroup (without identity
element), the usual definition of index is to consider an integer $i\geq 1$
because $\mathfrak{P}^{0}$ is not well-defined. For our record, we make the
following trivial observation:

######  Fact 7.1.

For all $m,n\in\operatorname{\mathbb{N}}$, we have
$\mathfrak{P}^{m}=\mathfrak{P}^{n}$ in $\mathbb{K}$ if and only if $m=n$ or
$m\equiv n\pmod{\operatorname{per}(\mathfrak{P})}$ with
$m,n\geq\operatorname{ind}(\mathfrak{P})$.

In our setting, observe that $\operatorname{ind}(\mathfrak{P})=0$ if and only
if $\mathfrak{P}$ is a unit. In particular, the index and period of the
polynomial $q$ will have a central role in our results. The index of $q$ is
directly linked to the polynomial $\mathfrak{M}$, as we shall see in what
follows. We first require a technical lemma establishing a special case.

The polynomial $q$ is a unit in $\mathbb{F}_{p}[q]/\langle\mathfrak{M}\rangle$
if and only if $\mathfrak{M}$ has a non-zero constant term.

###### Proof.

We have that $q$ is invertible modulo $\mathfrak{M}$ if and only if there
exist polynomials $\mathfrak{A},\mathfrak{B}\in\mathbb{F}_{p}[q]$ such that
$\mathfrak{A}(q)\cdot q+\mathfrak{B}(q)\cdot\mathfrak{M}(q)=1$. Since
$\mathbb{F}_{p}$ is a field, this is equivalent to the requirement that the
$\gcd$ of $q$ and $\mathfrak{M}$ is a constant. Clearly, if $\mathfrak{M}$ has
a non-zero constant term, the $\gcd$ is constant. Conversely, if
$\mathfrak{M}$ has constant term $0$, then the $\gcd$ is $q$. ∎

The _valuation_ $\operatorname{val}(\mathfrak{P})$ of a polynomial
$\mathfrak{P}\in\mathbb{F}[q]$, where $\mathbb{F}$ is a field, is the largest
power of $q$ dividing $\mathfrak{P}$, i.e.,
$\operatorname{val}(\mathfrak{P})=\max\\{\ell\colon
q^{\ell}|\mathfrak{P}(q)\\}$. In particular, $\operatorname{val}(0)=+\infty$.

The following result generalizes the previous lemma.

In $\mathbb{F}_{p}[q]/{\langle\mathfrak{M}\rangle}$, we have
$\operatorname{ind}(q)=\operatorname{val}(\mathfrak{M})$.

###### Proof.

If $\mathfrak{M}=aq^{d}$ with $a\neq 0$, then the sequence of powers of $q$
modulo $\mathfrak{M}$ is of the form $1,q,\ldots,q^{d-1},0,0,\ldots$ where the
first $d$ terms are pairwise distinct. Hence
$\operatorname{ind}(q)=d=\operatorname{val}(\mathfrak{M})$.

Assume now that $\mathfrak{M}$ has degree $d\geq 1$ and at least two non-zero
terms. Let us write

$\mathfrak{M}(q)=a_{d}q^{d}+\cdots+a_{1}q+a_{0}.$

and let $j<d$ be the least index such that $a_{j}\neq 0$. We first show that
$\operatorname{ind}(q)\leq j$. Let us define

$\mathfrak{N}(q)=a_{d}q^{d-j}+\cdots+a_{j+1}q+a_{j}.$

In other words, $q^{j}\mathfrak{N}(q)=\mathfrak{M}(q)$. Since $\mathfrak{N}$
has a non-zero constant term, Section 7.1 implies that $q$ is invertible
modulo $\mathfrak{N}$. With the same arguments as above, this means that the
index of $q$ within $\mathbb{F}_{p}[q]/\langle\mathfrak{N}\rangle$ is $0$ and
thus there exists some $i\geq 1$ and some polynomial $\mathfrak{B}$ such that
$q^{i}=1+\mathfrak{B}(q)\mathfrak{N}(q)$. This means that

$q^{i+j}-q^{j}=\mathfrak{B}(q)\mathfrak{N}(q)q^{j}=\mathfrak{B}(q)\mathfrak{M}(q),$

so that $q^{i+j}\equiv q^{j}\pmod{\mathfrak{M}}$.

We now show that $\operatorname{ind}(q)\geq j$. By contradiction, assume that
$\operatorname{ind}(q)<j$. In any case, we have that

$q^{\operatorname{ind}(q)+\operatorname{per}(q)}-q^{\operatorname{ind}(q)}=\mathfrak{B}(q)\mathfrak{M}(q)$

for some polynomial $\mathfrak{B}$. Dividing by $q^{\operatorname{ind}(q)}$,
we get

$q^{\operatorname{per}(q)}-1=\mathfrak{B}(q)\mathfrak{C}(q),$

where
$\mathfrak{C}(q)=\frac{\mathfrak{M}(q)}{q^{\operatorname{ind}(q)}}=a_{d}q^{d-\operatorname{ind}(q)}+\cdots+a_{j}q^{j-\operatorname{ind}(q)}$
is a polynomial whose constant term is vanishing. However, Section 7.1 implies
that $q$ cannot be invertible modulo $\mathfrak{C}$, hence a contradiction. ∎

The following proposition shall be important when discussing $p$-groups in the
following subsection.

The monomial $q$ has $\operatorname{ind}(q)=0$ and
$\operatorname{per}(q)=p^{t}$ for some $t>0$ in
$\mathbb{F}_{p}[q]/\langle\mathfrak{M}\rangle$ if and only if $\mathfrak{M}$
is of the form $a(q-1)^{d}$ for some $a\in\mathbb{F}_{p}^{\star}$ and $d>0$.

###### Proof.

First assume that $\mathfrak{M}(q)=a(q-1)^{d}$ for some positive integer $d$.
Take $n>0$ such that $p^{n}\geq d$. Since the base field is $\mathbb{F}_{p}$,
we have

$q^{p^{n}}-1=(q-1)^{p^{n}}=a^{-1}(q-1)^{p^{n}-d}a(q-1)^{d}=a^{-1}(q-1)^{p^{n}-d}\mathfrak{M}(q),$

so that $q^{p^{n}}\equiv 1\pmod{\mathfrak{M}}$. Therefore
$\operatorname{ind}(q)=0$ and $\operatorname{per}(q)$ divides $p^{n}$.

Now assume that $\operatorname{per}(q)=p^{t}$ for some $t>0$ and
$\operatorname{ind}(q)=0$. There thus exists a polynomial $\mathfrak{A}$ such
that

$q^{p^{t}}=\mathfrak{A}(q)\mathfrak{M}(q)+1.$

Consider an arbitrary monic irreducible factor $\mathfrak{p}$ of
$\mathfrak{M}$. Notice that $\operatorname{ind}(q)=0$ implies that
$\mathfrak{M}$ has a non-zero constant term by Section 7.1, and thus so has
$\mathfrak{p}$. Then $q^{p^{t}}\equiv 1\pmod{\mathfrak{p}}$ as well. Now the
group of units of the field $\mathbb{F}_{p}[q]/\langle\mathfrak{p}\rangle$ has
order $p^{deg(\mathfrak{p})}-1$. Since
$\gcd(p^{t},p^{deg(\mathfrak{p})}-1)=1$, we deduce that $q\equiv
1\pmod{\mathfrak{p}}$ (if $\deg(\mathfrak{p})=1$ we have an isomorphic copy of
$\mathbb{F}_{p}$). But then $q-1=\mathfrak{B}(q)\mathfrak{p}(q)$, which
implies $\mathfrak{p}=q-1$, $\mathfrak{B}(q)=1$, as $q-1$ is irreducible as
well. Since $\mathfrak{p}$ was arbitrary, we conclude that
$\mathfrak{M}=a(q-1)^{d}$ for some $d\geq 1$, $a\neq 0$. ∎

We finish this subsection off with a technical lemma about arithmetics in
$\mathbb{F}_{p}/\langle\mathfrak{M}\rangle$.

Let $\mathfrak{M}$ be a non-constant polynomial. Let
$\mathfrak{P}\in\mathbb{F}_{p}[q]$ be a polynomial such that
$\mathfrak{P}(0)\neq 0$ and

$q^{j}\mathfrak{P}(q)\equiv
q^{j+d\operatorname{per}(q)}\mathfrak{P}(q)\pmod{\mathfrak{M}}$

for some integers $j\geq 0$ and $d>0$. Then $j\geq\operatorname{ind}(q)$.

###### Proof.

There is nothing to prove if $\operatorname{ind}(q)=0$, so consider the case
$\operatorname{val}(\mathfrak{M})=\operatorname{ind}(q)\geq 1$. Assume by
contradiction that $j<\operatorname{ind}(q)$. Let us write

$\mathfrak{P}(q)\equiv c_{n}q^{n}+\cdots+c_{1}q+c_{0}\pmod{\mathfrak{M}},$

with $n<\deg(\mathfrak{M})$ and $c_{0}\neq 0$ (since
$\operatorname{val}(\mathfrak{M})\geq 1$ implies $\mathfrak{M}(0)=0$). The
assumption becomes

$\sum_{i=0}^{n}c_{i}q^{i+j}\equiv\sum_{i=0}^{n}c_{i}q^{i+j+d\operatorname{per}(q)}\pmod{\mathfrak{M}}.$

Since $j<\operatorname{ind}(q)$, there exists some non-negative integer $k$
such that $j+k=\operatorname{ind}(q)-1$. Then, for all
$m\in\\{k+1,\ldots,n\\}$, we have $c_{m}q^{m+j+d\operatorname{per}(q)}\equiv
c_{m}q^{m+j}\pmod{\mathfrak{M}}$, so that

$\sum_{i=0}^{k}c_{i}q^{i+j}\equiv\sum_{i=0}^{k}c_{i}q^{i+j+d\operatorname{per}(q)}\pmod{\mathfrak{M}}.$

In other words, there exists some non-zero polynomial
$\mathfrak{Q}\in\mathbb{F}_{p}[q]$ such that

$\mathfrak{R}(q):=\sum_{i=0}^{k}c_{i}q^{i+j}-\sum_{i=0}^{k}c_{i}q^{i+j+d\operatorname{per}(q)}=\mathfrak{Q}(q)\mathfrak{M}(q).$

However, the assumption $c_{0}\neq 0$ and Section 7.1 imply
$\operatorname{val}(\mathfrak{R})=j<\operatorname{ind}(q)=\operatorname{val}(\mathfrak{M})\leq\operatorname{val}(\mathfrak{Q}\mathfrak{M}),$
a contradiction. ∎

###  7.2 On $q$-binomials and $p$-group languages

We now define an equivalence relation on $A^{*}$ as follows. If the word $w\in
A^{*}$ can be written $pfs$ with $p,f,s\in A^{*}$, then $f$ is a factor of
$w$. The set of factors of $w$ is denoted by $\operatorname{Fac}(w)$.
[$(u,\mathfrak{M})$-binomial equivalence] Let $u\in A^{*}$ and
$\mathfrak{M}\in\mathbb{F}_{p}[q]$. Two finite words $w_{1},w_{2}\in A^{*}$
are $(u,\mathfrak{M})$-binomially equivalent and we write
$w_{1}\sim_{u,\mathfrak{M}}w_{2}$ whenever

$\forall
v\in\operatorname{Fac}(u)\setminus\\{\varepsilon\\}\,:\,\binom{w_{1}}{v}_{\\!\\!q}\equiv\binom{w_{2}}{v}_{\\!\\!q}\pmod{\mathfrak{M}}.$

We stress that one has to consider all factors of $u$ and compute the
corresponding $q$-binomial coefficients reduced modulo $\mathfrak{M}$.
Incidentally, the number of equivalence classes is bounded by
$\\#\mathbb{K}^{(\\#\operatorname{Fac}(u)-1)}$. In particular, the equivalence
relation $\sim_{u,\mathfrak{M}}$ has finite index in $A^{*}$.

It is obvious that if $f$ is a factor of $u$, then
$w_{1}\sim_{u,\mathfrak{M}}w_{2}$ implies $w_{1}\sim_{f,\mathfrak{M}}w_{2}$
because $\operatorname{Fac}(f)\subset\operatorname{Fac}(u)$.

Let $\mathfrak{M}(q)=q^{2}+1\in\mathbb{F}_{2}[q]$ and $u=ab\in\\{a,b\\}^{*}$.
Hence $\mathbb{K}=\\{0,1,q,q+1\\}$ and
$\operatorname{Fac}(u)=\\{\varepsilon,a,b,ab\\}$. By straightforward
computation, we find $4^{3}=64$ equivalence classes—the maximal possible—with
representatives of length at most $8$. For instance, the word $w=aaabbbab$ is
the shortest one such that

$\binom{w}{a}_{\\!\\!q}\equiv q+1,\quad\binom{w}{b}_{\\!\\!q}\equiv
q+1,\quad\binom{w}{ab}_{\\!\\!q}\equiv q\pmod{q^{2}+1}.$

The $(u,\mathfrak{M})$-binomial equivalence relation is not always a
congruence on $A^{*}$ as shown by the next example. Take $p=2$,
$\mathfrak{M}=q^{2}+1$, $A=\\{a,b\\}$ and $u=a$. We have
$a\sim_{a,\mathfrak{M}}ab^{3}a^{2}$ and $b\sim_{a,\mathfrak{M}}b^{2}$ but
$ab\not\sim_{a,\mathfrak{M}}ab^{3}a^{2}b^{2}$. To see this, we simply have to
compute

$\binom{a}{a}_{\\!\\!q}\equiv 1\quad\text{ and
}\quad\binom{ab^{3}a^{2}}{a}_{\\!\\!q}=1+q+q^{5}\equiv 1\pmod{\mathfrak{M}}$

moreover $\binom{b}{a}_{\\!\\!q}=\binom{b^{2}}{a}_{\\!\\!q}=0$ and

$\binom{ab}{a}_{\\!\\!q}\equiv q\quad\text{ but
}\quad\binom{ab^{3}a^{2}b^{2}}{a}_{\\!\\!q}=q^{2}+q^{3}+q^{7}\equiv
1\pmod{\mathfrak{M}}.$

In light of Section 7, we seek for a congruence $\equiv$ on $A^{*}$ (of finite
index) refining the equivalence relation $\sim_{u,\mathfrak{M}}$ so that
$A^{*}/{\equiv}$ is a finite monoid. To this end, we introduce some
intermediate notions whose sense will become clearer in the following results.

[mod-length congruence] Let $\ell\geq 1$ be an integer. We let $\sim_{\ell}$
denote the congruence relation defined by $w_{1}\sim_{\ell}w_{2}$ if and only
if $|w_{1}|\equiv|w_{2}|\pmod{\ell}$.

Let $u\in A^{*}$ and $\mathfrak{M}\in\mathbb{F}_{p}[q]$ (clear from the
context and not repeated in forthcoming notation). Given a word $w\in A^{*}$
and a factor $v$ of $u$ such that $av$ is also a factor of $u$ for some letter
$a$, we define the quantity
$l_{w,v}:=\operatorname{val}\left(\binom{w}{v}_{\\!\\!q}\bmod{\mathfrak{M}}\right)$.
Further, we define

$l_{w}:=\min\left\\{l_{w,v}-|v|\colon\exists a\in A,\
av\in\operatorname{Fac}(u)\right\\}.$

We stress the fact that $l_{w,v}$ is the valuation of the remainder of the
Euclidean division of $\binom{w}{v}_{\\!\\!q}$ by $\mathfrak{M}$. In
particular, $l_{w,v}<\deg(\mathfrak{M})$. The following lemma gives some
necessary conditions for a congruence to refine the
$(u,\mathfrak{M})$-binomial equivalence.

Let $u\in A^{*}$, $\mathfrak{M}\in\mathbb{F}_{p}[q]$ and $\cong$ be any
congruence refining the $(u,\mathfrak{M})$-binomial equivalence
$\sim_{u,\mathfrak{M}}$. Let $w_{1},w_{2}$ be words in $A^{*}$ such that
$w_{1}\cong w_{2}$. Then either $|w_{1}|=|w_{2}|$, or

  * •

$|w_{1}|,|w_{2}|\geq\operatorname{ind}(q)$,

  * •

$w_{1}\sim_{\operatorname{per}(q)}w_{2}$, and

  * •

$\min\\{l_{w_{1}}+|w_{1}|,l_{w_{2}}+|w_{2}|\\}\geq\operatorname{ind}(q)$.

###### Proof.

Let $a$ be a letter occurring in $u$. Assume that $w_{1}\cong w_{2}$, so in
particular
$\binom{w_{1}}{a}_{\\!\\!q}\equiv\binom{w_{2}}{a}_{\\!\\!q}\pmod{\mathfrak{M}}$.
Since we have a congruence, we get $aw_{1}\cong aw_{2}$ and since it is a
refinement of $\sim_{u,\mathfrak{M}}$, this means that

$q^{|w_{1}|}+\binom{w_{1}}{a}_{\\!\\!q}=\binom{aw_{1}}{a}_{\\!\\!q}\equiv\binom{aw_{2}}{a}_{\\!\\!q}=q^{|w_{2}|}+\binom{w_{2}}{a}_{\\!\\!q}\pmod{\mathfrak{M}}$

So that $q^{|w_{1}|}\equiv q^{|w_{2}|}\pmod{\mathfrak{M}}$. Fact 7.1 implies
that either $|w_{1}|=|w_{2}|$ or $|w_{1}|$, $|w_{2}|\geq\operatorname{ind}(q)$
and $w_{1}\sim_{\operatorname{per}(q)}w_{2}$.

It remains to show that
$\min\\{l_{w_{1}}+|w_{1}|,l_{w_{2}}+|w_{2}|\\}\geq\operatorname{ind}(q)$ in
the case $|w_{1}|,|w_{2}|\geq\operatorname{ind}(q)$ and $|w_{1}|\neq|w_{2}|$.
Assume that $|w_{2}|>|w_{1}|$ without loss of generality, in which case
$|w_{2}|=|w_{1}|+d\operatorname{per}(q)$ for some positive integer $d$. Now
$w_{1}\cong w_{2}$ so, for all factors $v$ of $u$, the remainders of the
Euclidean division of $\binom{w_{1}}{v}_{\\!\\!q}$ and
$\binom{w_{2}}{v}_{\\!\\!q}$ by $\mathfrak{M}$ are the same. This implies
$l_{w_{1},v}=l_{w_{2},v}$ for all $v$ for which $av\in\operatorname{Fac}(u)$
for some letter $a$. So we may assume towards a contradiction that
$l_{w_{1},v}+|w_{1}|-|v|<\operatorname{ind}(q)$ for some $v$ such that
$av\in\operatorname{Fac}(u)$; we denote by $R$ the common remainder polynomial
$\binom{w_{1}}{v}_{\\!\\!q},\binom{w_{2}}{v}_{\\!\\!q}\bmod{\mathfrak{M}}$.
Write for short $l:=\operatorname{val}(R)=l_{w_{1},v}=l_{w_{2},v}$. Note that
$l\geq 0$ and if $|w_{1}|-|v|<0$, then $\binom{w_{1}}{v}_{\\!\\!q}=0$ and
$l_{w_{1},v}=+\infty$. So $l+|w_{1}|-|v|$ is always non-negative. By
definition of $R$ and $l$, $R/q^{l}$ is a polynomial.

Take $a\in A$ such that $av\in\operatorname{Fac}(u)$. On the one side, we have

$\displaystyle\binom{aw_{1}}{av}_{q}$
$\displaystyle=\sum_{\begin{subarray}{c}av=v_{1}v_{2}\\\ v_{1},v_{2}\in
A^{*}\end{subarray}}q^{|v_{1}|(|w_{1}|-|v_{2}|)}\binom{a}{v_{1}}_{q}\binom{w_{1}}{v_{2}}_{q}=\binom{w_{1}}{av}_{q}+q^{|w_{1}|-|v|}\binom{w_{1}}{v}_{q}$
$\displaystyle\equiv\binom{w_{1}}{av}_{q}+q^{l+|w_{1}|-|v|}\dfrac{R}{q^{l}}\pmod{\mathfrak{M}},$

Using a similar argument, we have

$\binom{aw_{2}}{av}_{\\!\\!q}\equiv\binom{w_{2}}{av}_{\\!\\!q}+q^{l+|w_{2}|-|v|}\dfrac{R}{q^{l}}\pmod{\mathfrak{M}}.$

Since $\cong$ is a congruence and $av\in\operatorname{Fac}(u)$, we have
$\binom{aw_{1}}{av}_{\\!\\!q}\equiv\binom{aw_{2}}{av}_{\\!\\!q}\pmod{\mathfrak{M}}$.
From the above computations, since
$\binom{w_{1}}{av}_{\\!\\!q}\equiv\binom{w_{2}}{av}_{\\!\\!q}\pmod{\mathfrak{M}}$,
we get

$q^{l+|w_{2}|-|v|}\dfrac{R}{q^{l}}=q^{l+|w_{1}|+d\operatorname{per}(q)-|v|}\dfrac{R}{q^{l}}\equiv
q^{l+|w_{1}|-|v|}\dfrac{R}{q^{l}}\pmod{\mathfrak{M}}.$

Since $l+|w_{1}|-|v|<\operatorname{ind}(q)$, this contradicts Section 7.1. ∎

Recall Section 7.1; we have
$\operatorname{ind}(q)=\operatorname{val}(\mathfrak{M})$. So in particular
$\operatorname{ind}(q)$ is less than or equal to the degree of $\mathfrak{M}$.
This means that in 15 below, the polynomial in the right-hand side has degree
less than $\deg\mathfrak{M}$.

Let $w$ be a word.

  * i)

If $|w|<\operatorname{ind}(q)$, then

$\sum_{a\in A}\binom{w}{a}_{\\!\\!q}\equiv
q^{|w|-1}+\cdots+q+1\pmod{\mathfrak{M}}.$ (15)

  * ii)

If $|w|=\operatorname{ind}(q)+k\cdot\operatorname{per}(q)+r$ for some $k\geq
0$, $r\in\\{0,\ldots,\operatorname{per}(q)-1\\}$, then

$\sum_{a\in
A}\binom{w}{a}_{\\!\\!q}\equiv\sum_{j=\operatorname{ind}(q)+r}^{\operatorname{ind}(q)+\operatorname{per}(q)-1}[k]_{p}q^{j}+\sum_{j=\operatorname{ind}(q)}^{\operatorname{ind}(q)+r-1}[k+1]_{p}q^{j}+\sum_{j=0}^{\operatorname{ind}(q)-1}q^{j}\pmod{\mathfrak{M}}$

where $[\cdot]_{p}$ is the value reduced modulo $p$.

In particular, recalling Section 5 the sequence
$\left(\binom{n}{1}_{\\!\\!q}\pmod{\mathfrak{M}}\right)_{n\geq 0}$ becomes
periodic from index $\operatorname{ind}(q)$ and the integer
$\operatorname{per}(q)\cdot p$ is a multiple of the least period.

###### Proof.

The case $|w|<\operatorname{ind}(q)$ is trivial. As we sum over all letters in
$A$, we will recover the whole word $w$. Note that the polynomial we get is
already reduced modulo $\mathfrak{M}$ because its degree is
$|w|<\operatorname{ind}(q)\leq\deg(\mathfrak{M})$.

Let $a\in A$. Assume that there are $t$ occurrences of $a$ in $w$, given by
the positions (starting from the right) $i_{t}>\cdots>i_{1}\geq 1$, Theorem
4.1 gives $\binom{w}{a}_{\\!\\!q}=\sum_{j=1}^{t}q^{i_{j}-1}$. Since
$q^{\operatorname{ind}(q)+\operatorname{per}(q)}\equiv
q^{\operatorname{ind}(q)}\pmod{\mathfrak{M}}$, we have

$q^{\operatorname{ind}(q)+k\operatorname{per}(q)+r}\equiv
q^{\operatorname{ind}(q)+r}\pmod{\mathfrak{M}}.$ (16)

Therefore,

$\binom{w}{a}_{\\!\\!q}=\sum_{j=ind(q)}^{ind(q)+\operatorname{per}(q)-1}c_{j}q^{j}+\sum_{j=0}^{ind(q)-1}d_{j}q^{j}$

where $c_{i}$ is the number reduced modulo $p$ of letters $a$ occurring in $w$
with positions greater than $\operatorname{ind}(q)$ and congruent to $i+1$
modulo $\operatorname{per}(q)$, and $d_{i}=\delta_{a,w_{i+1}}$. Hence the
result when summing over all the letters in $A$. ∎

As an example, with $p=3$ and reducing modulo $\mathfrak{M}=q^{3}-1$ (i.e.,
$q$ has period $3$ and index $0$ in $\mathbb{K}^{\star}$), we get

$\binom{abaabcabacb}{a}_{\\!\\!q}=q^{10}+q^{8}+q^{7}+q^{4}+q^{2}\equiv
2q^{2}\pmod{\mathfrak{M}}$

because there are $a$’s in positions $\\{3,9\\}$ and $\\{5,8,11\\}$.
Similarly,

$\binom{abaabcabacb}{b}_{\\!\\!q}=q^{9}+q^{6}+q^{3}+1\equiv
1\pmod{\mathfrak{M}}$

because there are four $b$’s in positions all congruent to $1$ modulo $3$.
Finally,

$\binom{abaabcabacb}{c}_{\\!\\!q}=q^{5}+q\equiv q^{2}+q\pmod{\mathfrak{M}}$

because we have one $c$ in position congruent to $2$ (resp. $0$) modulo $3$.
Hence, the word of length $3\cdot 3+2$ gives

$\sum_{\sigma\in A}\binom{abaabcabacb}{\sigma}_{\\!\\!q}\equiv
q+1\pmod{\mathfrak{M}}$

For words of increasing length, the sequence
$\left(\binom{n}{1}_{\\!\\!q}\pmod{\mathfrak{M}}\right)_{n\geq 0}$ is periodic
of period $9$

$0,1,q+1,q^{2}+q+1,q^{2}+q+2,q^{2}+2q+2,2q^{2}+2q+2,2q^{2}+2q,2q^{2},\ldots$

As another example, with $\mathfrak{M}=q^{3}+q^{2}+2q\in\mathbb{F}_{5}[q]$,
$\operatorname{per}(q)=24$ and
$\left(\binom{n}{1}_{\\!\\!q}\pmod{\mathfrak{M}}\right)_{n\geq 0}$ has least
period $24$ (and not $24\cdot 5$).

Let $u\in A^{*}$, $\mathfrak{M}\in\mathbb{F}_{p}[q]$ and $\cong$ be a
congruence that refines $\sim_{u,\mathfrak{M}}$. If $q$ is not a unit of
$\mathbb{K}$, then the monoid $A^{*}/{\cong}$ is a not group. In particular,
no element except for the identity is invertible.

###### Proof.

The class $[\varepsilon]$ for $\cong$ is clearly the identity element of the
monoid. Thanks to Section 7.2, if $\operatorname{ind}(q)\geq 1$, then
$[\varepsilon]$ is a singleton. For any non-empty word $w$ and for all words
$x$, the class $[w]\cdot[x]=[wx]$ differs from $[\varepsilon]$, thus $[w]$ is
not invertible. ∎

Nevertheless, it is interesting look for the coarsest congruence refining
$\sim_{u,\mathfrak{M}}$. The following result, along with Section 7.2, enables
us to state the conditions defining this congruence.

Let $u\in A^{*}$ and $\mathfrak{M}\in\mathbb{F}_{p}[q]$. Define the relation
$\equiv_{u,\mathfrak{M}}$ by $w_{1}\equiv_{u,\mathfrak{M}}w_{2}$ if
$w_{1}\sim_{u,\mathfrak{M}}w_{2}$ and either $|w_{1}|=|w_{2}|$ or

  * •

$|w_{1}|$, $|w_{2}|\geq\operatorname{ind}(q)$,

  * •

$w_{1}\sim_{\operatorname{per}(q)}w_{2}$, and

  * •

$\min\\{l_{w_{1}}+|w_{1}|,l_{w_{2}}+|w_{2}|\\}\geq\operatorname{ind}(q)$.

Then $\equiv_{u,\mathfrak{M}}$ is a congruence. Moreover, it is the coarsest
one refining $\sim_{u,\mathfrak{M}}$.

###### Proof.

Let $w_{1},w_{2},y_{1},y_{2}$ be words such that
$w_{1}\equiv_{u,\mathfrak{M}}w_{2}$ and $y_{1}\equiv_{u,\mathfrak{M}}y_{2}$,
and let $v$ be a factor of $u$. From Section 4,

$\displaystyle\binom{y_{1}w_{1}}{v}_{\\!\\!q}$
$\displaystyle=\sum_{\begin{subarray}{c}v=v_{1}v_{2}\\\ v_{1},v_{2}\in
A^{*}\end{subarray}}q^{|v_{1}|(|w_{1}|-|v_{2}|)}\binom{y_{1}}{v_{1}}_{\\!\\!q}\binom{w_{1}}{v_{2}}_{\\!\\!q}$
$\displaystyle=\binom{w_{1}}{v}_{\\!\\!q}+q^{|v||w_{1}|}\binom{y_{1}}{v}_{\\!\\!q}+\sum_{\begin{subarray}{c}v=v_{1}v_{2}\\\
v_{1},v_{2}\in
A^{+}\end{subarray}}q^{|v_{1}|(|w_{1}|-|v_{2}|)}\binom{y_{1}}{v_{1}}_{\\!\\!q}\binom{w_{1}}{v_{2}}_{\\!\\!q}$

Since333The reader may observe that these relations justify the definition of
the relation $\sim_{u,\mathfrak{M}}$ which is extended to all factors of $u$.
$v_{1}$ and $v_{2}$ are factors of $v\in\operatorname{Fac}(u)$,

$\binom{y_{1}}{v_{1}}_{\\!\\!q}\equiv\binom{y_{2}}{v_{1}}_{\\!\\!q},\quad\binom{w_{1}}{v_{2}}_{\\!\\!q}\equiv\binom{w_{2}}{v_{2}}_{\\!\\!q}\pmod{\mathfrak{M}}.$

Moreover, since either $|w_{1}|=|w_{2}|$ or
$|w_{1}|\equiv|w_{2}|\pmod{\operatorname{per}(q)}$ with
$|w_{1}|,|w_{2}|\geq\operatorname{ind}(q)$, we have

$q^{|v_{1}||w_{1}|}\equiv q^{|v_{1}||w_{2}|}\pmod{\mathfrak{M}},$

which follows from the observation made in 16. Let $R$ be the remainder of the
Euclidean division of $\binom{w_{1}}{v_{2}}_{\\!\\!q}$ by $\mathfrak{M}$, so
that $R/q^{l_{w_{1},v_{2}}}$ is a polynomial. Finally, we have

$\sum_{\begin{subarray}{c}v=v_{1}v_{2}\\\ v_{1},v_{2}\in
A^{+}\end{subarray}}\\!\\!q^{|v_{1}|(|w_{1}|-|v_{2}|)}\binom{y_{1}}{v_{1}}_{\\!\\!q}\binom{w_{1}}{v_{2}}_{\\!\\!q}\\\
\equiv\sum_{\begin{subarray}{c}v=v_{1}v_{2}\\\ v_{1},v_{2}\in
A^{+}\end{subarray}}\\!\\!q^{(|v_{1}|-1)(|w_{1}|-|v_{2}|)+l_{w_{1},v_{2}}+|w_{1}|-|v_{2}|}\binom{y_{1}}{v_{1}}_{\\!\\!q}\frac{R}{q^{l_{w_{1},v_{2}}}}\pmod{\mathfrak{M}}$

and since $l_{w_{1},v_{2}}+|w_{1}|-|v_{2}|\geq\operatorname{ind}(q)$, assuming
$|w_{2}|=|w_{1}|+d\operatorname{per}(q)$, we have

$\displaystyle
q^{(|v_{1}|-1)(|w_{1}|-|v_{2}|)+l_{w_{1},v_{2}}+|w_{1}|-|v_{2}|}$
$\displaystyle\equiv
q^{(|v_{1}|-1)(|w_{1}|-|v_{2}|)+l_{w_{2},v_{2}}+|w_{1}|-|v_{2}|+d|v_{1}|\operatorname{per}(q)}\pmod{\mathfrak{M}}$
$\displaystyle\equiv
q^{|v_{1}|(|w_{2}|-|v_{2}|)+l_{w_{2},v_{2}}}\pmod{\mathfrak{M}},$

with $l_{w_{1},v_{2}}=l_{w_{2},v_{2}}$ coming from
$w_{1}\equiv_{u,\mathfrak{M}}w_{2}$. In the end, we get

$\sum_{\begin{subarray}{c}v=v_{1}v_{2}\\\ v_{1},v_{2}\in
A^{+}\end{subarray}}q^{|v_{1}|(|w_{1}|-|v_{2}|)}\binom{y_{1}}{v_{1}}_{\\!\\!q}\binom{w_{1}}{v_{2}}_{\\!\\!q}\equiv\sum_{\begin{subarray}{c}v=v_{1}v_{2}\\\
v_{1},v_{2}\in
A^{+}\end{subarray}}q^{|v_{1}|(|w_{2}|-|v_{2}|)}\binom{y_{2}}{v_{1}}_{\\!\\!q}\binom{w_{2}}{v_{2}}_{\\!\\!q}\pmod{\mathfrak{M}},$

so that $\binom{y_{1}w_{1}}{v}_{\\!\\!q}\equiv\binom{y_{2}w_{2}}{v}_{\\!\\!q}$
for all factors $v$ of $u$, i.e.
$y_{1}w_{1}\equiv_{u,\mathfrak{M}}y_{2}w_{2}$.

The fact that $\equiv_{u,\mathfrak{M}}$ is the coarsest congruence refining
$\sim_{u,\mathfrak{M}}$ follows from Section 7.2. ∎

We provide two cases where the congruence defined in Section 7.2 has a simpler
expression:

Case 1. The first case is when $q$ is a unit of $\mathbb{K}$. Here
$\operatorname{ind}(q)=0$, so that the conditions

$|w_{1}|,|w_{2}|\geq\operatorname{ind}(q)\quad\text{and}\quad\min\\{l_{w_{1}}+|w_{1}|,l_{w_{2}}+|w_{2}|\\}\geq\operatorname{ind}(q)$

become obvious (since $l_{w}+|w|=l_{w,v}-|v|+|w|\geq 0$ for some
$v\in\operatorname{Fac}(u)$). Consequently

$w_{1}\equiv_{u,\mathfrak{M}}w_{2}\quad\text{if and only if}\quad
w_{1}\sim_{u,\mathfrak{M}}w_{2}\text{ and
}w_{1}\sim_{\operatorname{per}(q)}w_{2}.$

Case 2. The second case is when $u$ contains all letters of $A$. In this case,
as we show next, the equivalence $w_{1}\sim_{u,\mathfrak{M}}w_{2}$ implies the
mod-length congruence $w_{1}\sim_{\operatorname{per}(q)}w_{2}$. As a
consequence, in this case, we have

$\displaystyle w_{1}\equiv_{u,\mathfrak{M}}w_{2}\quad\text{if and only if}$
$\displaystyle\quad w_{1}\sim_{u,\mathfrak{M}}w_{2}\text{ and either
}|w_{1}|=|w_{2}|\text{ or }$
$\displaystyle|w_{1}|,|w_{2}|\geq\operatorname{ind}(q)\text{ and
}\min\\{l_{w_{1}}+|w_{1}|,l_{w_{2}}+|w_{2}|\\}\geq\operatorname{ind}(q).$

Indeed, let $w_{1},w_{2}$ be two words such that

$\binom{w_{1}}{v}_{\\!\\!q}\equiv\binom{w_{2}}{v}_{\\!\\!q}\pmod{\mathfrak{M}},\;\forall
v\in\operatorname{Fac}(u).$

Since every letter of $A$ occurs in $u$, we have
$\binom{w_{1}}{a}_{\\!\\!q}\equiv\binom{w_{2}}{a}_{\\!\\!q}\pmod{\mathfrak{M}},\;\forall
a\in A$, so that

$\sum_{a\in A}\binom{w_{1}}{a}_{\\!\\!q}\equiv\sum_{a\in
A}\binom{w_{2}}{a}_{\\!\\!q}\pmod{\mathfrak{M}}.$ (17)

Assume first that the shorter, say $w_{1}$, has length
$|w_{1}|<\operatorname{ind}(q)$. Then Section 7.2 implies that $\sum_{a\in
A}\binom{w_{1}}{a}_{\\!\\!q}\equiv q^{|w_{1}|-1}+\cdots+1\pmod{\mathfrak{M}}$.
Observe that if $|w_{2}|>|w_{1}|$, then $\sum_{a\in
A}\binom{w_{2}}{a}_{\\!\\!q}$ contains more terms contradicting 17. So in this
case we conclude that $|w_{1}|=|w_{2}|$, and consequently the lengths are
equal modulo $\operatorname{per}(q)$.

Let us second assume that $w_{1}$, $w_{2}$ both have lengths at least
$\operatorname{ind}(q)$, and say $|w_{1}|<|w_{2}|$. There is nothing to prove
if $\operatorname{per}(q)=1$, so assume that $\operatorname{per}(q)\geq 2$.
Assume towards a contradiction that
$|w_{1}|\not\equiv|w_{2}|\pmod{\operatorname{per}(q)}$. We thus have
$|w_{i}|=\operatorname{ind}(q)+k_{i}\cdot\operatorname{per}(q)+r_{i}$,
$i=1,2$, for some $k_{i}\geq 0$, $0\leq r_{i}\leq\operatorname{per}(q)-1$.
Assume that $r_{2}>r_{1}$ (the other case being symmetric). Now Section
7.2(ii) implies that the difference

$\sum_{a\in A}\binom{w_{2}}{a}_{\\!\\!q}-\binom{w_{1}}{a}_{\\!\\!q},$

which is assumed to vanish modulo $\mathfrak{M}$, is equivalent to

$\sum_{j=\operatorname{ind}(q)+r_{2}}^{\operatorname{ind}(q)+\operatorname{per}(q)-1}[k_{2}-k_{1}]_{p}q^{j}+\sum_{j=\operatorname{ind}(q)+r_{1}}^{\operatorname{ind}(q)+r_{2}-1}[k_{2}-k_{1}+1]_{p}q^{j}+\sum_{j=\operatorname{ind}(q)}^{\operatorname{ind}(q)+r_{1}-1}[k_{2}-k_{1}]_{p}q^{j}\pmod{\mathfrak{M}}.$

Consequently,

$0\equiv\sum_{a\in
A}\binom{w_{2}}{a}_{\\!\\!q}-\binom{w_{1}}{a}_{\\!\\!q}\equiv[k_{2}-k_{1}]_{p}\sum_{j=\operatorname{ind}(q)}^{\operatorname{ind}(q)+\operatorname{per}(q)-1}q^{j}+\sum_{j=\operatorname{ind}(q)+r_{1}}^{\operatorname{ind}(q)+r_{2}-1}[1]_{p}q^{j}\pmod{\mathfrak{M}}.$
(18)

Note that with the first sum in the right-hand side, multiplying by $(q-1)$,
we get

$(q-1)\sum_{j=\operatorname{ind}(q)}^{\operatorname{ind}(q)+\operatorname{per}(q)-1}q^{j}=q^{\operatorname{ind}(q)}(q^{\operatorname{per}(q)}-1)=q^{\operatorname{ind}(q)+\operatorname{per}(q)}-q^{\operatorname{ind}(q)}\equiv
0\pmod{\mathfrak{M}}.$ (19)

We consider two cases; $q-1$ is not (resp., is) a factor of $\mathfrak{M}$. As
the first sub-case, assume that $q-1$ is not a factor of $\mathfrak{M}$ (and
is thus invertible modulo $\mathfrak{M}$). From 19 we conclude that
$\sum_{j=\operatorname{ind}(q)}^{\operatorname{ind}(q)+\operatorname{per}(q)-1}q^{j}\equiv
0\pmod{\mathfrak{M}}$ and thus

$\sum_{a\in
A}\binom{w_{2}}{a}_{\\!\\!q}-\binom{w_{1}}{a}_{\\!\\!q}\equiv\sum_{j=\operatorname{ind}(q)+r_{1}}^{\operatorname{ind}(q)+r_{2}-1}q^{j}\pmod{\mathfrak{M}}.$
(20)

Multiplying the r.h.s. of 20 by $(q-1)$ gives
$q^{\operatorname{ind}(q)+r_{2}}-q^{\operatorname{ind}(q)+r_{1}}$ which is
non-zero modulo $\mathfrak{M}$ by definition of the period as we assumed
$0\leq r_{1}<r_{2}\leq\operatorname{per}(q)-1$. This however contradicts 18.
Therefore, $w_{1}\sim_{\operatorname{per}(q)}w_{2}$, as was claimed.

As the second sub-case, assume $\mathfrak{M}=(q-1)^{d}\cdot\mathfrak{N}$ for
some polynomial $\mathfrak{N}$ and a maximal integer $d\geq 1$. Note that
$\deg\mathfrak{N}\geq 1$ because otherwise $q\equiv 1\pmod{\mathfrak{M}}$ and
$\operatorname{per}(q)$ would be equal to $1$ (which is not the case). First
the identities 17 and 18 still hold modulo $\mathfrak{N}$. Moreover, from 19,
we deduce that
$\sum_{j=\operatorname{ind}(q)}^{\operatorname{ind}(q)+\operatorname{per}(q)-1}q^{j}$
is congruent to $0$ modulo $\mathfrak{N}$. So 20 holds modulo $\mathfrak{N}$.
The same conclusion as in the first sub-case follows after multiplication by
$(q-1)$.

To conclude this remark, we combine the two above cases, namely, if both $q$
is invertible and $u$ contains all letters of $A$, we find that the congruence
$\equiv_{u,\mathfrak{M}}$ is actually the equivalence relation
$\sim_{u,\mathfrak{M}}$ itself (i.e., there is no proper refinement).

When $q$ is a unit of $\mathbb{K}$, for a congruence $\cong$ that refines
$\sim_{u,\mathfrak{M}}$, we may ask whether or not the monoid $A^{*}/{\cong}$
is a group. It is natural to consider the _coarsest_ congruence refining
$\sim_{u,\mathfrak{M}}$, which is $\equiv_{u,\mathfrak{M}}$ in view of Section
7.2. In particular, since we consider that $q$ is a unit of $\mathbb{K}$,
Section 7.2 shows that this congruence is actually the intersection of
relations $\sim_{u,\mathfrak{M}}\cap\sim_{\operatorname{per}(q)}$ (or just
$\sim_{u,\mathfrak{M}}$ if $u$ contains all letters of $A$). Considering this
particular congruence, the corresponding quotient is indeed a group as seen in
Theorem 7.2.

Continuing Section 7.2, if we take for each equivalence the genealogically
least representative and if the $64$ classes are ordered with respect to these
representatives, we get the multiplication table depicted in Fig. 2. The
element in the upper left corner is $[\varepsilon]$.

Figure 2: The multiplication table for the group
$\\{a,b\\}^{*}/{\sim_{ab,q^{2}+1}}$ with $64$ elements.

######  Theorem 7.2.

Let $u\in A^{*}$, $\mathfrak{M}\in\mathbb{F}_{p}[q]$. If $q$ is a unit in
$\mathbb{K}$, $A^{*}/{\equiv_{u,\mathfrak{M}}}$ is a group whose order divides
$\operatorname{per}(q)\cdot p^{|u|}$.

###### Proof.

We will prove that $[w]^{\operatorname{per}(q)p^{|u|}}=[\varepsilon]$ for each
$w\in A^{*}$, which suffices for the claim. Note that the length of
$w^{\operatorname{per}(q)p^{|u|}}$ is a multiple of $\operatorname{per}(q)$
and thus we trivially have
$w^{\operatorname{per}(q)p^{|u|}}\sim_{\operatorname{per}(q)}\varepsilon$.
Since, for every non-empty factor $v$ of $u$,
$\binom{\varepsilon}{v}_{\\!\\!q}=0$, we have to show that

$\binom{w^{\operatorname{per}(q)p^{|u|}}}{v}_{\\!\\!q}\equiv
0\pmod{\mathfrak{M}}.$

Let $v$ be a non-empty factor of $u$. We prove by induction on $|v|$ that, for
all words $w$ and $j\geq 0$,

$\binom{w^{\operatorname{per}(q)p^{|v|+j}}}{v}_{\\!\\!q}\equiv
0\pmod{\mathfrak{M}}.$

It is enough to prove it for $j=0$. Indeed, replacing $w$ with $w^{p}$,

$(w^{p})^{\operatorname{per}(q)p^{|v|}}=w^{\operatorname{per}(q)p^{|v|}.p}=w^{\operatorname{per}(q)p^{|v|+1}}.$

If $v=a\in A$, we make use of Section 4

$\binom{w^{\operatorname{per}(q)p}}{a}_{\\!\\!q}=\sum_{i=0}^{\operatorname{per}(q)p-1}q^{i|w|}\binom{w}{a}_{\\!\\!q}.$

Using 16 and since $q$ is a unit (i.e., $\operatorname{ind}(q)=0$), we deduce
that

$\sum_{i=0}^{\operatorname{per}(q)p-1}q^{i|w|}=\sum_{i=0}^{\operatorname{per}(q)-1}\sum_{j=0}^{p-1}q^{(\operatorname{per}(q)j+i)|w|}\equiv\sum_{i=0}^{\operatorname{per}(q)-1}p\,q^{i|w|}\equiv
0\pmod{\mathfrak{M}}.$

Assume that the result holds for words of length up to $k\geq 1$ and consider
a word $v$ of length $k+1$. From Section 4, we have

$\binom{w^{\operatorname{per}(q)p^{k+1}}}{v}_{\\!\\!q}=\sum_{\begin{subarray}{c}v=v_{1}\cdots
v_{p}\\\ v_{i}\in
A^{*}\end{subarray}}q^{\sum_{i=1}^{p-1}|v_{i}|((p-i)\operatorname{per}(q)p^{k}|w|-|v_{i+1}\cdots
v_{p}|)}\binom{w^{\operatorname{per}(q)p^{k}}}{v_{1}}_{\\!\\!q}\cdots\binom{w^{\operatorname{per}(q)p^{k}}}{v_{p}}_{\\!\\!q}$

and, by induction hypothesis, if one of the $v_{i}$’s in a factorization of
$v$ has a length such that $1\leq|v_{i}|\leq k$, then

$\binom{w^{\operatorname{per}(q)p^{k}}}{v_{i}}_{\\!\\!q}\equiv
0\pmod{\mathfrak{M}}.$

So the only non-zero terms modulo $\mathfrak{M}$ correspond to factorizations
where all the $v_{i}$’s are $\varepsilon$ except one which is $v$. Hence,
using again 16, we get

$\binom{w^{\operatorname{per}(q)p^{k+1}}}{v}_{\\!\\!q}\equiv\sum_{j=0}^{p-1}q^{j|v|\operatorname{per}(q)p^{k}|w|}\binom{w^{\operatorname{per}(q)p^{k}}}{v}_{\\!\\!q}\equiv
p\binom{w^{\operatorname{per}(q)p^{k}}}{v}_{\\!\\!q}\equiv
0\pmod{\mathfrak{M}}.$

∎

Let $v$ be a word and $\mathfrak{M}=a(q-1)^{d}$ for some integer $d\geq 1$ and
non-zero $a\in\mathbb{F}_{p}$. The language $L_{v,\mathfrak{R},\mathfrak{M}}$
given in 14 is a $p$-group language.

###### Proof.

By Section 7.1, we have $\operatorname{ind}(q)=0$ and
$\operatorname{per}(q)=p^{t}$ for some $t\geq 0$ (and clearly we must have
$p^{t}\geq d$). Thanks to Theorem 7.2, the order of the group
$G=A^{*}/{\equiv_{v,\mathfrak{M}}}$ is divisible by $p^{t+|v|}$, and is thus a
$p$-group.

Consider the projection morphism $\pi:A^{*}\to G$ that maps a word $x$ to its
equivalence class $[x]$. Take $S\subset G$ be the set of classes defined by
$[y]\in S$ if and only if

$\binom{y}{v}_{\\!\\!q}\equiv\mathfrak{R}\pmod{\mathfrak{M}}.$

It is clear that $\pi^{-1}(S)=L_{v,\mathfrak{R},\mathfrak{M}}$. ∎

The DFA $\mathcal{M}$ whose set of states is
$G=A^{*}/{\equiv_{v,\mathfrak{M}}}$, with transition function $\delta\colon
G\times A\to G$ defined by $\delta([y],a)=[ya]$, initial state $[\varepsilon]$
and set of final states $\pi^{-1}(S)$ as in the previous proof, accepts the
language $L_{v,\mathfrak{R},\mathfrak{M}}$. Since $G$ is a group, this DFA is
a permutation automaton (i.e., its transition semigroup is a group). A
quotient of a permutation automaton being a permutation automaton, the minimal
automaton of $L_{v,\mathfrak{R},\mathfrak{M}}$ is a permutation automaton.

Continuing Section 7.2 and applying the procedure described above, the
minimization of the DFA is depicted in Fig. 3. For $\mathfrak{R}$ being $0$,
$1$, $q+1$ or $q$, the structure of the minimal automaton does not change but
one has to choose the four states on the first $\\{1,2,3,4\\}$, resp. second
$\\{5,6,7,8\\}$, third $\\{9,10,11,12\\}$ or fourth layer $\\{13,14,15,16\\}$
to be the final states.

$1$$2$$3$$6$$4$$11$$7$$10$$16$$12$$8$$14$$13$$9$$5$$15$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$
Figure 3: The structure of the minimal automaton of
$L_{ab,\mathfrak{R},q^{2}+1}$.

In Fig. 3, we see how $a$ and $b$ act as permutations of the set of states.
These two permutations may be used as generators of the considered group.

We have a direct generalization of Eilenberg’s theorem characterizing
$p$-group languages.

######  Theorem 7.3.

Let $p$ be a prime and $\mathfrak{M}=a(q-1)^{d}$ with $d\geq 1$ an integer and
a non-zero $a\in\mathbb{F}_{p}$. A language is a $p$-group language if and
only if it is a Boolean combination of languages of the form

$L_{v,\mathfrak{R},\mathfrak{M}}=\left\\{u\in
A^{*}\mid\binom{u}{v}_{\\!\\!q}\equiv\mathfrak{R}\pmod{\mathfrak{M}}\right\\}.$

###### Proof.

Let us first make the following observation. The remainder $\mathfrak{R}(q)$
of the Euclidean division of $\mathfrak{P}(q)$ by $\mathfrak{M}$ and the
polynomial $\mathfrak{P}(q)$ have the same sum of coefficients modulo $p$.
Indeed, we have the Euclidean division

$\mathfrak{P}(q)=\mathfrak{A}(q)\cdot a(q-1)^{d}+\mathfrak{R}(q)$

and the conclusion follows by evaluating both sides at $q=1$,
$\mathfrak{P}(1)=\mathfrak{R}(1)\pmod{p}$.

Consequently, for a classical binomial coefficient of words (whose value is an
integer), we have

$\binom{u}{v}\equiv r\pmod{p}$

if and only if the evaluation at $q=1$ of the polynomial in
$\mathbb{F}_{p}[q]$ given by

$\binom{u}{v}_{\\!\\!q}\bmod{\mathfrak{M}}$

is also congruent to $r$ modulo $p$ (since the ground field is
$\mathbb{F}_{p}$). Indeed, if $\binom{u}{v}_{\\!\\!q}=\mathfrak{P}(q)$, then
the integers $\mathfrak{P}(1)$ and $\binom{u}{v}$ are equal and the conclusion
follows by considering all the coefficients over $\mathbb{F}_{p}$.

This means that every language $L_{v,r,p}:=\\{u\in A^{*}\mid\binom{u}{v}\equiv
r\pmod{p}\\}$ is the disjoint union of languages 14 of the form
$L_{v,\mathfrak{R},\mathfrak{M}}$ for polynomials $\mathfrak{R}$ such that
$\mathfrak{R}(1)=r$ modulo $p$. More precisely, we observe that amongst the
$p^{d}$ polynomials $\mathfrak{R}(q)$ of degree less than $d$ in
$\mathbb{F}_{p}[q]$, exactly $p^{d-1}$ are such that $\mathfrak{R}(1)$ is a
given element in $\mathbb{F}_{p}$; the sum modulo $p$ of the elements in a
$d$-tuple of coefficients in $\mathbb{F}_{p}$ is completely determined by one
of the coefficients when the other $d-1$ ones are fixed.

We may now conclude using Eilenberg’s theorem. If $L$ is a $p$-group language,
it is a Boolean combination of languages of the form $L_{v,r,p}$ which are
themselves finite unions of languages of the form
$L_{v,\mathfrak{R},\mathfrak{M}}$.

The converse comes from Section 7.2. Recall that any Boolean combination of
$p$-group languages is a $p$-group language. ∎

As an example, for $p=2$ and $t=1$, since $q+1$ at $q=1$ evaluates to $0$
modulo $2$

$L_{v,0,2}=\left\\{u\in A^{*}\mid\binom{u}{v}_{\\!\\!q}\equiv
0\pmod{q^{2}-1}\right\\}\cup\left\\{u\in A^{*}\mid\binom{u}{v}_{\\!\\!q}\equiv
q+1\pmod{q^{2}-1}\right\\}$

and since $q$ at $q=1$ evaluates to $1$ modulo $2$

$L_{v,1,2}=\left\\{u\in A^{*}\mid\binom{u}{v}_{\\!\\!q}\equiv
1\pmod{q^{2}-1}\right\\}\cup\left\\{u\in A^{*}\mid\binom{u}{v}_{\\!\\!q}\equiv
q\pmod{q^{2}-1}\right\\}.$

In Fig. 4, we have depicted the minimal automaton for $L_{ab,r,2}$. For $r=0$
(resp. $r=1$), the final states are $\\{1,2\\}$ (resp. $\\{3,4\\}$). This
automaton is a quotient of the one depicted in Fig. 3 where the states
$1,3,9,11$ are mapped to $1$, resp. $2,4,10,12$ to $2$, resp. $6,8,14,16$ to
$3$ and $5,7,13,15$ to $4$.

$1$$2$$3$$4$$a$$b$$b$$a$$b$$a$$a$$b$ Figure 4: The structure of the minimal
automaton of $L_{ab,r,2}$.

##  8 Conclusions

In this paper, we have proposed a $q$-deformation of the binomial coefficients
of words. Our natural definition seems quite reasonable, since it has enabled
us to obtain the analogue of many classical properties or formulas. Moreover,
as shown by Section 5, these $q$-deformations of binomial coefficients of
words contain much richer information than the coefficients obtained for
$q=1$. However, it should be noted that not all classical properties extend in
an obvious way. For example, our proposed family of $q$-deformation of the
infiltration product does not yield an analogue to Chen–Fox–Lyndon relation
12. Finally, it is interesting to note that as an application of our
developments, we obtain a refinement of Eilenberg’s theorem characterizing
$p$-group languages. One also obtains other group languages. It could be
interesting to investigate their properties further.

## Acknowledgments

We thank S. Morier-Genoud and C. Reutenauer for useful references.

## Data availability

Data sharing is not applicable to this article as no datasets were generated
or analyzed.

## Author Contributions

Each of the three authors have equally contributed to the manuscript.

## Conflict of interest statement

The authors declare no conflict of interest.

## References

  * [1] George E. Andrews.  $q$-series: their development and application in analysis, number theory, combinatorics, physics, and computer algebra, volume 66 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1986.
  * [2] Gérard Duchamp, Marianne Flouret, Éric Laugerotte, and Jean-Gabriel Luque.  Direct and dual laws for automata with multiplicities.  Theoret. Comput. Sci., 267(1-2):105–120, 2001.  Implementing automata (Mont-Saint-Aignan, 1998).  doi:10.1016/S0304-3975(00)00298-X.
  * [3] Gérard H. E. Duchamp, Jean-Yves Enjalbert, Vincel Hoang Ngoc Minh, and Christophe Tollu.  The mechanics of shuffle products and their siblings.  Discrete Math., 340(9):2286–2300, 2017.  doi:10.1016/j.disc.2017.03.004.
  * [4] Miroslav Dudík and Leonard J. Schulman.  Reconstruction from subsequences.  J. Combin. Theory Ser. A, 103(2):337–348, 2003.  doi:10.1016/S0097-3165(03)00103-1.
  * [5] Ömer Eğecioğlu.  A q-matrix encoding extending the Parikh matrix mapping.  In Proc. Int. Conf. on Computers and Communications (Oradea, Romania), 2004.
  * [6] Ömer Eğecioğlu and Oscar H. Ibarra.  A matrix $q$-analogue of the Parikh map.  In Exploring new frontiers of theoretical informatics. IFIP 18th world computer congress, TC1 3rd international conference on theoretical computer science (TCS2004), 22–27 August 2004, Toulouse, France., pages 125–138. Boston, MA: Kluwer Academic Publishers, 2004.
  * [7] Samuel Eilenberg.  Automata, languages, and machines. Vol. B.  Pure and Applied Mathematics, Vol. 59. Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976.
  * [8] J. A. Green.  Shuffle algebras, Lie algebras and quantum groups, volume 9 of Textos de Matemática. Série B [Texts in Mathematics. Series B].  Universidade de Coimbra, Departamento de Matemática, Coimbra, 1995\.
  * [9] James Haglund.  The $q,t$-Catalan numbers and the space of diagonal harmonics. With an appendix on the combinatorics of Macdonald polynomials, volume 41 of Univ. Lect. Ser. Providence, RI: American Mathematical Society (AMS), 2008.
  * [10] Victor Kac and Pokman Cheung.  Quantum calculus.  Universitext. Springer-Verlag, New York, 2002.  doi:10.1007/978-1-4613-0071-7.
  * [11] Mark V. Lawson.  Finite automata.  Chapman & Hall/CRC, Boca Raton, FL, 2004.
  * [12] Marie Lejeune, Michel Rigo, and Matthieu Rosenfeld.  The binomial equivalence classes of finite words.  Internat. J. Algebra Comput., 30(7):1375–1397, 2020.  doi:10.1142/S0218196720500459.
  * [13] M. Lothaire.  Combinatorics on Words.  Cambridge Mathematical Library. Cambridge University Press, 1997.  doi:10.1017/CBO9780511566097.
  * [14] John Machacek and Nicholas Ovenhouse.  $q$-rational and $q$-real binomial coefficients, 2023.  arXiv:2301.08185.
  * [15] Bennet Manvel, Aaron D. Meyerowitz, Allen J. Schwenk, Kenneth W. Smith, and Paul K. Stockmeyer.  Reconstruction of sequences.  Discrete Math., 94(3):209–219, 1991.  doi:10.1016/0012-365X(91)90026-X.
  * [16] Sophie Morier-Genoud and Valentin Ovsienko.  $q$-deformed rationals and $q$-continued fractions.  Forum Math. Sigma, 8:Paper No. e13, 55, 2020.  doi:10.1017/fms.2020.9.
  * [17] Sophie Morier-Genoud and Valentin Ovsienko.  On $q$-deformed real numbers.  Exp. Math., 31(2):652–660, 2022.  doi:10.1080/10586458.2019.1671922.
  * [18] Jean-Éric Pin and Christophe Reutenauer.  A noncommutative extension of Mahler’s interpolation theorem.  J. Noncommut. Geom., 16(3):1055–1101, 2022.  doi:10.4171/jncg/480.
  * [19] Jean-Éric Pin and Pedro V. Silva.  On uniformly continuous functions for some profinite topologies.  Theoret. Comput. Sci., 658:246–262, 2017.  doi:10.1016/j.tcs.2016.06.013.
  * [20] Jean-Éric Pin and Xaro Soler-Escrivà.  Languages and formations generated by $D_{4}$ and $Q_{8}$.  Theoret. Comput. Sci., 800:155–172, 2019.  doi:10.1016/j.tcs.2019.10.023.
  * [21] Christophe Reutenauer.  Free Lie algebras.  In Handbook of algebra, Vol. 3, volume 3 of Handb. Algebr., pages 887–903. Elsevier/North-Holland, Amsterdam, 2003.  doi:10.1016/S1570-7954(03)80075-X.
  * [22] Michel Rigo and Pavel Salimov.  Another generalization of abelian equivalence: binomial complexity of infinite words.  Theor. Comput. Sci., 601:47–57, 2015.  doi:10.1016/j.tcs.2015.07.025.
  * [23] Marc Rosso.  Quantum groups and quantum shuffles.  Invent. Math., 133(2):399–416, 1998.  URL: https://doi.org/10.1007/s002220050249.
  * [24] Richard P. Stanley.  Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, second edition, 2012.