Introduction
For any non-empty set A A A , we denote by A ∙ A^{\bullet} A ∙ the disjoint union { ∅ } ⊔ ⋃ k = 1 ∞ A k \{\emptyset\}\sqcup\bigcup_{k=1}^{\infty}A^k { ∅ } ⊔ ⋃ k = 1 ∞ A k . Let Z + \mathbb{Z}_{+} Z + be the set of positive integers, and denote by I \mathcal{I} I the set Z + ∙ \mathbb{Z}_{+}^{\bullet} Z + ∙ . The elements in I \mathcal{I} I are called tuples . For any tuple s = ( s 1 , … , s r ) ∈ I \mathfrak{s}=(s_{1},\ldots,s_{r})\in\mathcal{I} s = ( s 1 , … , s r ) ∈ I , the depth dep ( s ) \operatorname{dep}(\mathfrak{s}) dep ( s ) and weight wt ( s ) \operatorname{wt}(\mathfrak{s}) wt ( s ) are defined by dep ( s ) = r \operatorname{dep}(\mathfrak{s})=r dep ( s ) = r and wt ( s ) = ∑ i = 1 r s i \operatorname{wt}(\mathfrak{s})=\sum_{i=1}^{r}s_{i} wt ( s ) = ∑ i = 1 r s i , with the convention dep ( ∅ ) = 0 \operatorname{dep}(\emptyset)=0 dep ( ∅ ) = 0 and wt ( ∅ ) = 0 \operatorname{wt}(\emptyset)=0 wt ( ∅ ) = 0 . For a tuple s = ( s 1 , … , s l ) \mathfrak{s}=(s_{1},\ldots,s_{l}) s = ( s 1 , … , s l ) , we set s = ( s 1 , s T ) = ( s H , s l ) \mathfrak{s}=(s_{1},\mathfrak{s}^{T})=(\mathfrak{s}^{H},s_{l}) s = ( s 1 , s T ) = ( s H , s l ) (possibly s H , s T = ∅ \mathfrak{s}^{H},\mathfrak{s}^{T}=\emptyset s H , s T = ∅ ). For any n ∈ Z + n\in\mathbb{Z}_{+} n ∈ Z + , we set n + s = ( s 1 + n , s T ) n+\mathfrak{s}=(s_{1}+n,\mathfrak{s}^{T}) n + s = ( s 1 + n , s T ) and s + n = ( s H , s l + n ) \mathfrak{s}+n=(\mathfrak{s}^{H},s_{l}+n) s + n = ( s H , s l + n ) .
Define I w = { s ∈ I ∣ wt ( s ) = w } \mathcal{I}_{w}=\{\mathfrak{s}\in\mathcal{I}\mid\operatorname{wt}(\mathfrak{s})=w\} I w = { s ∈ I ∣ wt ( s ) = w } for any weight w ≥ 0 w\geq0 w ≥ 0 , and define I > 0 = I ∖ { ∅ } \mathcal{I}_{>0}=\mathcal{I}\setminus\{\emptyset\} I > 0 = I ∖ { ∅ } . For w ∈ Z + w\in\mathbb{Z}_{+} w ∈ Z + and a field F F F , we denote the F F F -linear formal sum space of tuples of weight w w w by S w ( F ) = ⨁ s ∈ I w F s \mathcal{S}_{w}^{(F)}=\bigoplus_{\mathfrak{s}\in\mathcal{I}_{w}}F\mathfrak{s} S w ( F ) = ⨁ s ∈ I w F s , and S ( F ) = ⨁ s ∈ I F s \mathcal{S}^{(F)}=\bigoplus_{\mathfrak{s}\in\mathcal{I}}F\mathfrak{s} S ( F ) = ⨁ s ∈ I F s . As usual, [ n ] [n] [ n ] denotes the set { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n } for any n ∈ Z + n\in\mathbb{Z}_{+} n ∈ Z + , and [ 0 ] = ∅ [0]=\emptyset [ 0 ] = ∅ .
Thakur’s multiple zeta values and Carlitz multiple polylogarithm values
Let A = F q [ θ ] A=\mathbb{F}_{q}[\theta] A = F q [ θ ] be the polynomial ring in one variable θ \theta θ over a finite field F q \mathbb{F}_{q} F q of characteristic p p p , and let A + A_{+} A + be the set of monic polynomials in A A A . Let K = F q ( θ ) K=\mathbb{F}_{q}(\theta) K = F q ( θ ) be its fraction field, and K ∞ = F q ( ( θ − 1 ) ) K_{\infty}=\mathbb{F}_{q}((\theta^{-1})) K ∞ = F q (( θ − 1 )) be the completion of K K K at ∞ \infty ∞ .
For a tuple s = ( s 1 , … , s r ) ∈ I > 0 \mathfrak{s}=(s_{1},\ldots,s_{r})\in\mathcal{I}_{>0} s = ( s 1 , … , s r ) ∈ I > 0 and d ∈ Z ≥ 0 d\in\mathbb{Z}_{\geq0} d ∈ Z ≥ 0 , define the power sum S d ( s ) S_{d}(\mathfrak{s}) S d ( s ) as
S d ( s ) = ∑ a 1 , … , a r ∈ A + d = deg a 1 > ⋯ > deg a r 1 a 1 s 1 ⋯ a r s r ∈ K . S_{d}(\mathfrak{s})=\sum_{\substack{a_{1},\ldots,a_{r}\in A_{+}\\ d=\deg a_{1}>\cdots>\deg a_{r}}}\frac{1}{a_{1}^{s_{1}}\cdots a_{r}^{s_{r}}}\in K. S d ( s ) = a 1 , … , a r ∈ A + d = d e g a 1 > ⋯ > d e g a r ∑ a 1 s 1 ⋯ a r s r 1 ∈ K .
For convenience, we set S − 1 ( ∅ ) = 1 S_{-1}(\emptyset)=1 S − 1 ( ∅ ) = 1 , S d ( ∅ ) = 0 S_{d}(\emptyset)=0 S d ( ∅ ) = 0 for d ∈ Z ∖ { − 1 } d\in\mathbb{Z}\setminus\{-1\} d ∈ Z ∖ { − 1 } , and S d ( s ) = 0 S_{d}(\mathfrak{s})=0 S d ( s ) = 0 for d < dep ( s ) − 1 d<\operatorname{dep}(\mathfrak{s})-1 d < dep ( s ) − 1 . We further define
S < d ( s ) = ∑ k < d S k ( s ) . S_{<d}(\mathfrak{s})=\sum_{k<d}S_{k}(\mathfrak{s}). S < d ( s ) = k < d ∑ S k ( s ) .
then
S d ( s ) = S d ( s 1 ) S < d ( s T ) . S_{d}(\mathfrak{s})=S_{d}(s_{1})S_{<d}(\mathfrak{s}^{T}). S d ( s ) = S d ( s 1 ) S < d ( s T ) .
Now we define the multiple zeta values in positive characteristic (abbreviated as MZV) introduced by Thakur [6 ] as follows:
ζ ( s ) = ∑ d ≥ 0 S d ( s ) ∈ K ∞ . \zeta(\mathfrak{s})=\sum_{d\geq0}S_{d}(\mathfrak{s})\in K_{\infty}. ζ ( s ) = d ≥ 0 ∑ S d ( s ) ∈ K ∞ .
For S d ( s ) S_{d}(\mathfrak{s}) S d ( s ) , S < d ( s ) S_{<d}(\mathfrak{s}) S < d ( s ) and ζ ( s ) \zeta(\mathfrak{s}) ζ ( s ) , we call dep ( s ) \operatorname{dep}(\mathfrak{s}) dep ( s ) and wt ( s ) \operatorname{wt}(\mathfrak{s}) wt ( s ) the depth and weight of them. The other object closely associated with MZVs is Carlitz multiple polylogarithm values. Set l 0 = 1 l_{0}=1 l 0 = 1 and l d = ∏ k = 1 d ( θ − θ q k ) l_{d}=\prod_{k=1}^{d}(\theta-\theta^{q^{k}}) l d = ∏ k = 1 d ( θ − θ q k ) for d ∈ Z + d\in\mathbb{Z}_{+} d ∈ Z + , for a tuple s = ( s 1 , … , s r ) ∈ I w \mathfrak{s}=(s_{1},\ldots,s_{r})\in\mathcal{I}_{w} s = ( s 1 , … , s r ) ∈ I w , we introduce analogues of power sums, which we called Carlitz power sum here
S i , d ( s ) = ∑ d = k 1 > ⋯ > k r ≥ 0 1 l k 1 s 1 ⋯ l k r s r ∈ K ∞ , S_{i,d}(\mathfrak{s})=\sum_{\substack{d=k_{1}>\cdots>k_{r}\geq0}}\frac{1}{l_{k_{1}}^{s_{1}}\cdots l_{k_{r}}^{s_{r}}}\in K_{\infty}, S i , d ( s ) = d = k 1 > ⋯ > k r ≥ 0 ∑ l k 1 s 1 ⋯ l k r s r 1 ∈ K ∞ ,
Similarly, we set S i , − 1 ( ∅ ) = 1 S_{i,-1}(\emptyset)=1 S i , − 1 ( ∅ ) = 1 , S i , d ( ∅ ) = 0 S_{i,d}(\emptyset)=0 S i , d ( ∅ ) = 0 for d ∈ Z ∖ { − 1 } d\in\mathbb{Z}\setminus\{-1\} d ∈ Z ∖ { − 1 } , and S i , d ( s ) = 0 S_{i,d}(\mathfrak{s})=0 S i , d ( s ) = 0 for d < dep ( s ) − 1 d<\operatorname{dep}(\mathfrak{s})-1 d < dep ( s ) − 1 . Further define
S i , < d ( s ) = ∑ k < d S i , k ( s ) ∈ K ∞ . S_{i,<d}(\mathfrak{s})=\sum_{k<d}S_{i,k}(\mathfrak{s})\in K_{\infty}. S i , < d ( s ) = k < d ∑ S i , k ( s ) ∈ K ∞ .
Similarly, we have
Si d ( s ) = Si d ( s 1 ) Si < d ( s T ) . \operatorname{Si}_{d}(\mathfrak{s})=\operatorname{Si}_{d}(s_1)\operatorname{Si}_{<d}(\mathfrak{s}^{T}). Si d ( s ) = Si d ( s 1 ) Si < d ( s T ) .
The Carlitz multiple polylogarithm values (abbreviated as CMPLVs) are defined by
Li ( s ) = ∑ d ≥ 0 Si d ( s ) ∈ K ∞ . \operatorname{Li}(\mathfrak{s})=\sum_{d\geq0}\operatorname{Si}_{d}(\mathfrak{s})\in K_{\infty}. Li ( s ) = d ≥ 0 ∑ Si d ( s ) ∈ K ∞ .
For Si d ( s ) \operatorname{Si}_{d}(\mathfrak{s}) Si d ( s ) , Si < d ( s ) \operatorname{Si}_{<d}(\mathfrak{s}) Si < d ( s ) and Li ( s ) \operatorname{Li}(\mathfrak{s}) Li ( s ) , we still call dep ( s ) \operatorname{dep}(\mathfrak{s}) dep ( s ) and wt ( s ) \operatorname{wt}(\mathfrak{s}) wt ( s ) the depth and weight of them.
For MZVs, we are interested in their linear relations, over K K K or over F q \mathbb{F}_{q} F q . However, the linear relations among CMPLVs are the objects which are easier to treat in general. [3 ] explains that studying the linear relations among MZVs is equivalent to studying the ones among CMPLVs. More precisely, we have the following theorem.
Theorem 1.1 (Hu [3 ] ). Define ζ \zeta ζ and Li \operatorname{Li} Li as the F F F -linear maps from S ( F ) \mathcal{S}^{(F)} S ( F ) to K ∞ K_{\infty} K ∞ by linear extension for F = K F=K F = K or F q \mathbb{F}_{q} F q . Then there is a canonical linear automorphism T T T of S ( F ) \mathcal{S}^{(F)} S ( F ) , such that ζ ∘ T = Li \zeta\circ T=\operatorname{Li} ζ ∘ T = Li .
Here “canonical” means T T T preserves some additional algebraic structures, but we will not use this property in this paper.
Note that the kernels of ζ \zeta ζ and Li \operatorname{Li} Li are actually the F F F -linear relation space of MZVs and CMPLVs, so Theorem 1.1 enables us to focus on the linear relations among CMPLVs.
For the K K K -linear relations, Todd and Thakur predicted an explicit basis and dimension for the K K K -span of CMPLVs, which is now a theorem, independently due to Chang–Chen–Mishiba [1 ] and Im–Kim–Le–Ngo Dac–Pham [5 ] .
Define Z w ( K ) \mathcal{Z}_{w}^{(K)} Z w ( K ) the K K K -linear subspace of K ∞ K_{\infty} K ∞ spanned by CMPLVs Li ( s ) \operatorname{Li}(\mathfrak{s}) Li ( s ) of weight w w w .
Theorem 1.2 (Chang–Chen–Mishiba [1 ] , independently Im–Kim–Le–Ngo Dac–Pham [5 ] ). For any weight w ≥ 1 w\geq1 w ≥ 1 , we have dim K Z w ( K ) = d w ( K ) \dim_{K}\mathcal{Z}_{w}^{(K)}=d_{w}^{(K)} dim K Z w ( K ) = d w ( K ) , where the sequence { d w ( K ) } w ≥ 1 \{d_{w}^{(K)}\}_{w\geq1} { d w ( K ) } w ≥ 1 is defined by the generating function
∑ w = 1 ∞ d w ( K ) x w = x ( 1 − x q − 1 ) 1 − 2 x + x q + 1 . \sum_{w=1}^{\infty}d_{w}^{(K)}x^{w}=\frac{x(1-x^{q-1})}{1-2x+x^{q+1}}. w = 1 ∑ ∞ d w ( K ) x w = 1 − 2 x + x q + 1 x ( 1 − x q − 1 ) . Moreover, { Li ( s ) ∣ s ∈ B w ( T T ) } \{\operatorname{Li}(\mathfrak{s})\mid\mathfrak{s}\in\mathcal{B}_{w}^{(\mathrm{TT})}\} { Li ( s ) ∣ s ∈ B w ( TT ) } is a K K K -basis of Z w ( K ) \mathcal{Z}_{w}^{(K)} Z w ( K ) , where
B w ( T T ) = { ( h , z ) ∈ I w ∣ h ∈ [ q ] ∙ , z ∈ [ q − 1 ] } . \mathcal{B}_{w}^{(\mathrm{TT})}=\{(h,z)\in I_{w}\mid h\in[q]^{\bullet},\ z\in[q-1]\}. B w ( TT ) = {( h , z ) ∈ I w ∣ h ∈ [ q ] ∙ , z ∈ [ q − 1 ]} .
Todd also formulated a conjecture about how to obtain K K K -linear relations, which is the idea the author called “operator generation”. He claimed all of K K K -linear relations are generated by lifting the binary relations from applying the B \mathcal{B} B , B ∗ \mathcal{B}^{*} B ∗ and C \mathcal{C} C operators to the fundamental relation, which we will introduce later. This conjecture is also a theorem now, due to Chang–Chen–Mishiba [1 ] and the author [3 ] .
We first define binary relations.
Definition 1.3. (i) A binary relation R R R of CMPLVs of weight w w w is given by a collection of elements a i , b j a_i,b_j a i , b j of K K K such that for all d ∈ Z d\in\mathbb{Z} d ∈ Z
∑ i a i Si d ( s i ) + ∑ j b j Si d + 1 ( t j ) = 0 , \sum_i a_i\operatorname{Si}_{d}(\mathfrak{s}_i)+\sum_j b_j\operatorname{Si}_{d+1}(\mathfrak{t}_j)=0, i ∑ a i Si d ( s i ) + j ∑ b j Si d + 1 ( t j ) = 0 , where the sum runs through tuples s i \mathfrak{s}_i s i and t j \mathfrak{t}_j t j of weight w w w . We denote the above equality by R ( d ) R(d) R ( d ) . And we may denote R R R by [ P ; Q ] [P;Q] [ P ; Q ] where P = ∑ i a i s i P=\sum_i a_i\mathfrak{s}_i P = ∑ i a i s i and Q = ∑ j b j t j Q=\sum_j b_j\mathfrak{t}_j Q = ∑ j b j t j .
(ii) A binary relation is called a fixed relation if b j = 0 b_j=0 b j = 0 for all j j j .
We denote the set of all binary relations of S i \mathrm{Si} Si of weight w w w by B R w \mathcal{BR}_w B R w . The simplest binary relation, in the sense of owning the lowest weight, is the one we called the fundamental relation, denoted by R 1 R_1 R 1 (see [7 ] , §3.4.6):
S i d ( q ) + D 1 S i d + 1 ( 1 , q − 1 ) = 0 , where D 1 = θ q − θ . \mathrm{Si}_d(q)+D_1\mathrm{Si}_{d+1}(1,q-1)=0,\quad\text{where }D_1=\theta^q-\theta. Si d ( q ) + D 1 Si d + 1 ( 1 , q − 1 ) = 0 , where D 1 = θ q − θ .
Then we introduce the B \mathcal{B} B , B ∗ \mathcal{B}^* B ∗ and C \mathcal{C} C operators.
Definition 1.4. Given a tuple W = ( w 1 , … , w r ) ∈ I k W=(w_1,\ldots,w_r)\in\mathcal{I}_k W = ( w 1 , … , w r ) ∈ I k .
(i) The operator B W : B R w → B R w + k \mathcal{B}_W:\mathcal{BR}_w\to\mathcal{BR}_{w+k} B W : B R w → B R w + k is a linear map defined by
B W ( R ) : B W ( R ) ( d ) = S i d ( W ) ∑ j < d R ( j ) for any R ∈ B R w . \mathcal{B}_W(R):\quad\mathcal{B}_W(R)(d)=\mathrm{Si}_d(W)\sum_{j<d}R(j)\quad\text{for any }R\in\mathcal{BR}_w. B W ( R ) : B W ( R ) ( d ) = Si d ( W ) j < d ∑ R ( j ) for any R ∈ B R w . (ii) The operator B W ∗ : B R w → B R w + k \mathcal{B}^*_W:\mathcal{BR}_w\to\mathcal{BR}_{w+k} B W ∗ : B R w → B R w + k is a linear map defined by
B W ∗ = B ( w 1 ) ∘ ⋯ ∘ B ( w r ) . \mathcal{B}^*_W=\mathcal{B}_{(w_1)}\circ\cdots\circ\mathcal{B}_{(w_r)}. B W ∗ = B ( w 1 ) ∘ ⋯ ∘ B ( w r ) . (iii) The operator C W : B R w → B R w + k \mathcal{C}_W:\mathcal{BR}_w\to\mathcal{BR}_{w+k} C W : B R w → B R w + k is a linear map defined by
C W ( R ) : C W ( R ) ( d ) = R ( d ) S i < d + 1 ( W ) for any R ∈ B R w . \mathcal{C}_W(R):\quad\mathcal{C}_W(R)(d)=R(d)\mathrm{Si}_{<d+1}(W)\quad\text{for any }R\in\mathcal{BR}_w. C W ( R ) : C W ( R ) ( d ) = R ( d ) Si < d + 1 ( W ) for any R ∈ B R w .
For W = ∅ W=\varnothing W = ∅ , we set all these operators to be the identity.
Defining the product maps ∗ \ast ∗ , ◃ \triangleleft ◃ and ⋄ \diamond ⋄ would help us understand B \mathcal{B} B , B ∗ \mathcal{B}^* B ∗ and C \mathcal{C} C better.
s ∗ t = ( s 1 , s T ∗ t ) + ( t 1 , s ∗ t T ) + ( s 1 + t 1 , s T ∗ t T ) ; (1) \mathfrak{s}\ast\mathfrak{t}=(s_1,\mathfrak{s}^{T}\ast\mathfrak{t})+(t_1,\mathfrak{s}\ast\mathfrak{t}^{T})+(s_1+t_1,\mathfrak{s}^{T}\ast\mathfrak{t}^{T}); \tag*{(1)} s ∗ t = ( s 1 , s T ∗ t ) + ( t 1 , s ∗ t T ) + ( s 1 + t 1 , s T ∗ t T ) ; (1)
s ◃ t = ( s 1 , s T ∗ t ) ; (2) \mathfrak{s}\triangleleft\mathfrak{t}=(s_1,\mathfrak{s}^{T}\ast\mathfrak{t}); \tag*{(2)} s ◃ t = ( s 1 , s T ∗ t ) ; (2)
s ⋄ t = ( s 1 + t 1 , s T ∗ t T ) . (3) \mathfrak{s}\diamond\mathfrak{t}=(s_1+t_1,\mathfrak{s}^{T}\ast\mathfrak{t}^{T}). \tag*{(3)} s ⋄ t = ( s 1 + t 1 , s T ∗ t T ) . (3)
where s ∗ ∅ = ∅ ∗ s = s \mathfrak{s}\ast\varnothing=\varnothing\ast\mathfrak{s}=\mathfrak{s} s ∗ ∅ = ∅ ∗ s = s , s ⋄ ∅ = ∅ ⋄ s = 0 t \mathfrak{s}\diamond\varnothing=\varnothing\diamond\mathfrak{s}=0\mathfrak{t} s ⋄ ∅ = ∅ ⋄ s = 0 t and s ◃ ∅ = s \mathfrak{s}\triangleleft\varnothing=\mathfrak{s} s ◃ ∅ = s . And ∗ \ast ∗ and ⋄ \diamond ⋄ are both commutative and associative. For multiple ◃ \triangleleft ◃ -products, we always evaluate from right to left.
Theorem 1.5. For any s , t ∈ I \mathfrak{s},\mathfrak{t}\in\mathcal{I} s , t ∈ I , and d ∈ Z ≥ 0 d\in\mathbb{Z}_{\geq0} d ∈ Z ≥ 0 ,
S i < d ( s ) S i < d ( t ) = S i < d ( s ∗ t ) ; \mathrm{Si}_{<d}(\mathfrak{s})\mathrm{Si}_{<d}(\mathfrak{t})=\mathrm{Si}_{<d}(\mathfrak{s}\ast\mathfrak{t}); Si < d ( s ) Si < d ( t ) = Si < d ( s ∗ t ) ; S i d ( s ) S i d ( t ) = S i d ( s ⋄ t ) ; \mathrm{Si}_d(\mathfrak{s})\mathrm{Si}_d(\mathfrak{t})=\mathrm{Si}_d(\mathfrak{s}\diamond\mathfrak{t}); Si d ( s ) Si d ( t ) = Si d ( s ⋄ t ) ; S i d ( s ) S i < d ( t ) = S i d ( s ◃ t ) , \mathrm{Si}_d(\mathfrak{s})\mathrm{Si}_{<d}(\mathfrak{t})=\mathrm{Si}_d(\mathfrak{s}\triangleleft\mathfrak{t}), Si d ( s ) Si < d ( t ) = Si d ( s ◃ t ) ,
Proof. Verify directly by definition
Then the B , B ∗ , C \mathcal{B},\mathcal{B}^*,\mathcal{C} B , B ∗ , C can be rewritten as
B W [ P ; Q ] = [ W ◃ P + W ⋄ Q + W ◃ Q ; 0 ] ; \mathcal{B}_W[P;Q]=[W\triangleleft P+W\diamond Q+W\triangleleft Q;0]; B W [ P ; Q ] = [ W ◃ P + W ⋄ Q + W ◃ Q ; 0 ] ;
B W ∗ [ P ; Q ] = [ ( w 1 ) ◃ ( w 2 ) ◃ ⋯ ◃ ( w r ) ◃ P + ( w r ) ⋄ Q + ( w r ) ◃ Q ; 0 ] ; \mathcal{B}^*_W[P;Q]=[(w_1)\triangleleft(w_2)\triangleleft\cdots\triangleleft(w_r)\triangleleft P+(w_r)\diamond Q+(w_r)\triangleleft Q;0]; B W ∗ [ P ; Q ] = [( w 1 ) ◃ ( w 2 ) ◃ ⋯ ◃ ( w r ) ◃ P + ( w r ) ⋄ Q + ( w r ) ◃ Q ; 0 ] ;
C W [ P ; Q ] = [ P ⋄ W + P ◃ W ; Q ◃ W ] . \mathcal{C}_W[P;Q]=[P\diamond W+P\triangleleft W;Q\triangleleft W]. C W [ P ; Q ] = [ P ⋄ W + P ◃ W ; Q ◃ W ] .
Finally, we need to explain what is the lift of a binary relation. Given a binary relation R = [ P ; Q ] R=[P;Q] R = [ P ; Q ] , it is
Si d ( P ) + Si d + 1 ( Q ) = 0 , \operatorname{Si}_{d}(P)+\operatorname{Si}_{d+1}(Q)=0, Si d ( P ) + Si d + 1 ( Q ) = 0 ,
summing over all d, we obtain a relation among CMPLVs,
Li ( P ) + Li ( Q ) = 0. (4) \operatorname{Li}(P)+\operatorname{Li}(Q)=0. \tag*{(4)} Li ( P ) + Li ( Q ) = 0. (4)
We denote P + Q P+Q P + Q by R ‾ \overline{R} R or [ P ; Q ] ‾ \overline{[P;Q]} [ P ; Q ] , call it the lift of R R R . Then Equation (4) is actually Li ( R ‾ ) = 0 \operatorname{Li}(\overline{R})=0 Li ( R ) = 0 . Now we can state Todd’s relation conjecture.
Theorem 1.6 (Chang–Chen–Mishiba [1 ] , and Hu [3 ] ). For n ∈ Z + n\in\mathbb{Z}_{+} n ∈ Z + , the K K K -linear relation space among CMPLVs of weight q + n q+n q + n is spanned by
{ B ‾ U ( R ‾ 1 ) : U ∈ I n } ∪ { C ‾ V ( R ‾ 1 ) : V ∈ I n } ∪ { B ‾ U ∘ C ‾ V ( R ‾ 1 ) : U ∈ I l , V ∈ I m , l + m = n } . (5) \{\overline{B}_{U}(\overline{R}_{1}):U\in\mathcal{I}_{n}\}\cup\{\overline{C}_{V}(\overline{R}_{1}):V\in\mathcal{I}_{n}\}\cup\{\overline{B}_{U}\circ\overline{C}_{V}(\overline{R}_{1}):U\in\mathcal{I}_{l},V\in\mathcal{I}_{m},l+m=n\}. \tag*{(5)} { B U ( R 1 ) : U ∈ I n } ∪ { C V ( R 1 ) : V ∈ I n } ∪ { B U ∘ C V ( R 1 ) : U ∈ I l , V ∈ I m , l + m = n } . (5) It is also spanned when every B B B in (5) is replaced by B ∗ B^{*} B ∗ .
Remark 1.7. Theorem 1.6 was originally formulated for MZVs. The B \mathcal{B} B -parts of this theorem are equivalent for MZVs and CMPLVs. But B ∗ \mathcal{B}^{*} B ∗ -parts need to be treated separately. See [3 ] for more details.
Main results in this paper
Now we turn to the F q \mathbb{F}_{q} F q -linear relation among CMPLVs. Huang, Lai, Li and the author have obtained a complete description in [2 ] . Before introducing the detailed results, we introduce the quadruple-carry relations constructed by them.
Lemma 1.8. For any h , m , t ∈ I \mathfrak{h},\mathfrak{m},\mathfrak{t}\in\mathcal{I} h , m , t ∈ I , r 1 ∈ Z + r_{1}\in\mathbb{Z}_{+} r 1 ∈ Z + , and r 2 ∈ Z ≥ 0 r_{2}\in\mathbb{Z}_{\geq0} r 2 ∈ Z ≥ 0 satisfying either r 2 > 0 r_{2}>0 r 2 > 0 , or r 2 = 0 r_{2}=0 r 2 = 0 and t = ∅ \mathfrak{t}=\varnothing t = ∅ (with the convention that, in the latter case, ( r 2 , t ) = ( 0 , ∅ ) (r_{2},\mathfrak{t})=(0,\varnothing) ( r 2 , t ) = ( 0 , ∅ ) is identified with ∅ \varnothing ∅ ), define the following formal sum of tuples:
Q ( h , [ q + r 1 ] , m , [ q + r 2 ] , t ) : = ( h , ( q + r 1 , m ) + 1 , ( q − 1 ) ∗ ( r 2 , t ) ) + ( h , q + r 1 , m , 1 , ( q − 1 ) ∗ ( r 2 , t ) ) + ( h , q , ( r 1 , m ) + 1 , ( q − 1 ) ∗ ( r 2 , t ) ) + ( h , q , r 1 , m , 1 , ( q − 1 ) ∗ ( r 2 , t ) ) − 1 h ≠ ∅ ⋅ ( h + 1 , ( q − 1 ) ∗ ( r 1 , m , q + r 2 , t ) ) − ( h , 1 , ( q − 1 ) ∗ ( r 1 , m , q + r 2 , t ) ) − 1 h ≠ ∅ , r 2 ≠ 0 ⋅ ( h + 1 , ( q − 1 ) ∗ ( r 1 , m , q , r 2 , t ) ) − 1 r 2 ≠ 0 ⋅ ( h , 1 , ( q − 1 ) ∗ ( r 1 , m , q , r 2 , t ) ) . \begin{aligned}
\boldsymbol{Q}\left(\mathfrak{h},\left[q+r_{1}\right],\mathfrak{m},\left[q+r_{2}\right],\mathfrak{t}\right)
:={}&\left(\mathfrak{h},(q+r_{1},\mathfrak{m})^{+1},(q-1)*(r_{2},\mathfrak{t})\right)+\left(\mathfrak{h},q+r_{1},\mathfrak{m},1,(q-1)*(r_{2},\mathfrak{t})\right)\\
&+\left(\mathfrak{h},q,(r_{1},\mathfrak{m})^{+1},(q-1)*(r_{2},\mathfrak{t})\right)+\left(\mathfrak{h},q,r_{1},\mathfrak{m},1,(q-1)*(r_{2},\mathfrak{t})\right)\\
&-\mathbf{1}_{\mathfrak{h}\ne\varnothing}\cdot\left(\mathfrak{h}^{+1},(q-1)*(r_{1},\mathfrak{m},q+r_{2},\mathfrak{t})\right)-\left(\mathfrak{h},1,(q-1)*(r_{1},\mathfrak{m},q+r_{2},\mathfrak{t})\right)\\
&-\mathbf{1}_{\mathfrak{h}\ne\varnothing,r_{2}\ne0}\cdot\left(\mathfrak{h}^{+1},(q-1)*(r_{1},\mathfrak{m},q,r_{2},\mathfrak{t})\right)-\mathbf{1}_{r_{2}\ne0}\cdot\left(\mathfrak{h},1,(q-1)*(r_{1},\mathfrak{m},q,r_{2},\mathfrak{t})\right).
\end{aligned} Q ( h , [ q + r 1 ] , m , [ q + r 2 ] , t ) := ( h , ( q + r 1 , m ) + 1 , ( q − 1 ) ∗ ( r 2 , t ) ) + ( h , q + r 1 , m , 1 , ( q − 1 ) ∗ ( r 2 , t ) ) + ( h , q , ( r 1 , m ) + 1 , ( q − 1 ) ∗ ( r 2 , t ) ) + ( h , q , r 1 , m , 1 , ( q − 1 ) ∗ ( r 2 , t ) ) − 1 h = ∅ ⋅ ( h + 1 , ( q − 1 ) ∗ ( r 1 , m , q + r 2 , t ) ) − ( h , 1 , ( q − 1 ) ∗ ( r 1 , m , q + r 2 , t ) ) − 1 h = ∅ , r 2 = 0 ⋅ ( h + 1 , ( q − 1 ) ∗ ( r 1 , m , q , r 2 , t ) ) − 1 r 2 = 0 ⋅ ( h , 1 , ( q − 1 ) ∗ ( r 1 , m , q , r 2 , t ) ) . Then
Li ( Q ( h , [ q + r 1 ] , m , [ q + r 2 ] , t ) ) = 0. \operatorname{Li}\left(\boldsymbol{Q}\left(\mathfrak{h},[q+r_{1}],\mathfrak{m},[q+r_{2}],\mathfrak{t}\right)\right)=0. Li ( Q ( h , [ q + r 1 ] , m , [ q + r 2 ] , t ) ) = 0. We call the above equation a quadruple-carry relation.
Proof. See [2 ] , Lemma 2.5.
The following is the main result in [2 ] .
Theorem 1.9 (Hu–Huang–Lai–Li [2 ] ). Define Z w \mathcal{Z}_w Z w the F q \mathbb{F}_q F q -linear subspace of K ∞ K_\infty K ∞ spanned by CMPLVs of weight w w w , and R w \mathcal{R}_w R w the F q \mathbb{F}_q F q -linear subspace of S w ( F q ) \mathcal{S}^{(\mathbb{F}_q)}_w S w ( F q ) spanned by the F q \mathbb{F}_q F q -linear relations among CMPLVs of weight w w w (i.e. the intersection of Ker Li \operatorname{Ker}\operatorname{Li} Ker Li and S w ( F q ) \mathcal{S}^{(\mathbb{F}_q)}_w S w ( F q ) ). For any weight w ≥ 1 w \ge1 w ≥ 1 ,
(i) dim F q Z w = d w \dim_{\mathbb{F}_q}\mathcal{Z}_w=d_w dim F q Z w = d w , where the sequence { d w } w ≥ 1 \{d_w\}_{w\ge1} { d w } w ≥ 1 is defined by the generating function
∑ w = 1 ∞ d w x w = x ( 1 − x q ) ( 1 − 2 x + x q ) ( 1 − 2 x + x q + 1 ) 2 . \sum_{w=1}^{\infty}d_wx^w=\frac{x(1-x^q)(1-2x+x^q)}{(1-2x+x^{q+1})^2}. w = 1 ∑ ∞ d w x w = ( 1 − 2 x + x q + 1 ) 2 x ( 1 − x q ) ( 1 − 2 x + x q ) . (ii) { Li ⋆ ( s ) ∣ s ∈ B w } \left\{\operatorname{Li}^{\star}(\mathfrak{s})\mid\mathfrak{s}\in\mathcal{B}_w\right\} { Li ⋆ ( s ) ∣ s ∈ B w } is an F q \mathbb{F}_q F q -basis of Z w \mathcal{Z}_w Z w , where B w = B ∩ I w \mathcal{B}_w=\mathcal{B}\cap\mathcal{I}_w B w = B ∩ I w ,
B = [ q ] ∙ ∪ { ( h , m , t ) ∈ I ∣ h , t ∈ [ q ] ∙ , m ∈ [ 2 q ] ∖ [ q ] } , \mathcal{B}=[q]^{\bullet}\cup\left\{(h,m,t)\in\mathcal{I}\mid h,t\in[q]^{\bullet},\ m\in[2q]\setminus[q]\right\}, B = [ q ] ∙ ∪ { ( h , m , t ) ∈ I ∣ h , t ∈ [ q ] ∙ , m ∈ [ 2 q ] ∖ [ q ] } , and
Li ⋆ ( s ) = ∑ n 1 ≥ n 2 ≥ ⋯ ≥ n k n 1 , n 2 , … , n k ∈ Z ≥ 0 1 ℓ n 1 s 1 ℓ n 2 s 2 ⋯ ℓ n k s k . \operatorname{Li}^{\star}(\mathfrak{s})=\sum_{\substack{n_1\ge n_2\ge\cdots\ge n_k\\n_1,n_2,\ldots,n_k\in\mathbb{Z}_{\ge0}}}\frac{1}{\ell_{n_1}^{s_1}\ell_{n_2}^{s_2}\cdots\ell_{n_k}^{s_k}}. Li ⋆ ( s ) = n 1 ≥ n 2 ≥ ⋯ ≥ n k n 1 , n 2 , … , n k ∈ Z ≥ 0 ∑ ℓ n 1 s 1 ℓ n 2 s 2 ⋯ ℓ n k s k 1 . (iii) R w \mathcal{R}_w R w is the F q \mathbb{F}_q F q -span of all quadruple-carry relations of weight w w w .
The key point of [2 ] is actually Theorem 1.9 (iii), which completely describes F q \mathbb{F}_q F q -linear relation space R w \mathcal{R}_w R w . However, this is not the unique way to understand R w \mathcal{R}_w R w .
While developing the work [2 ] , inspired by Theorem 1.6, the author wanted to use the similar operator generation method to study R w \mathcal{R}_w R w . Later, Im, Kim and Ngo Dac formulated a similar idea in [4 ] . Using the terminology of [4 ] , we first introduce the so-called P \mathcal{P} P operator.
For any s = ( s 1 , ⋯ , s l ) ∈ I ∖ { ∅ } \mathfrak{s}=(s_1,\cdots,s_l)\in\mathcal{I}\setminus\{\varnothing\} s = ( s 1 , ⋯ , s l ) ∈ I ∖ { ∅ } , define the F q \mathbb{F}_q F q -linear operator P : S w ( F q ) → S w + 2 q ( F q ) ⊕ S w ( F q ) \mathcal{P}:\mathcal{S}^{(\mathbb{F}_q)}_w\to\mathcal{S}^{(\mathbb{F}_q)}_{w+2q}\oplus\mathcal{S}^{(\mathbb{F}_q)}_w P : S w ( F q ) → S w + 2 q ( F q ) ⊕ S w ( F q ) by
P ( s ) = [ ( q ) ( ◃ + ⋄ ) ( s + 1 + ( s , 1 ) , q − 1 ) ; − ( 1 , ( q − 1 ) ∗ ( s , q ) ) ] . \mathcal{P}(\mathfrak{s})=\left[(q)(\triangleleft+\diamond)\left(\mathfrak{s}^{+1}+(\mathfrak{s},1),q-1\right);-(1,(q-1)\ast(\mathfrak{s},q))\right]. P ( s ) = [ ( q ) ( ◃ + ⋄ ) ( s + 1 + ( s , 1 ) , q − 1 ) ; − ( 1 , ( q − 1 ) ∗ ( s , q )) ] .
where s ( ◃ + ⋄ ) t = s ◃ t + s ⋄ t \mathfrak{s}(\triangleleft+\diamond)t=\mathfrak{s}\triangleleft t+\mathfrak{s}\diamond t s ( ◃ + ⋄ ) t = s ◃ t + s ⋄ t .
The first result in this paper shows that B ∗ , C , P \mathcal{B}^{\ast},\mathcal{C},\mathcal{P} B ∗ , C , P operators can generate all F q \mathbb{F}_q F q -linear relations. We will prove it in two different ways in Section 2 and § 4 respectively.
Theorem 1.10. R w = Span F q { B u ∗ ∘ C v ∘ P ( s ) ∣ wt ( u ) + wt ( v ) + wt ( s ) + 2 q = w } \mathcal{R}_w=\operatorname{Span}_{\mathbb{F}_q}\{\mathcal{B}^{\ast}_u\circ\mathcal{C}_v\circ\mathcal{P}(\mathfrak{s})\mid\operatorname{wt}(u)+\operatorname{wt}(v)+\operatorname{wt}(\mathfrak{s})+2q=w\} R w = Span F q { B u ∗ ∘ C v ∘ P ( s ) ∣ wt ( u ) + wt ( v ) + wt ( s ) + 2 q = w }
We will use B C P w \mathcal{BCP}_w BC P w to denote the RHS of the above equation.
Remark 1.11. Similarly, we can use B \mathcal{B} B to replace B ∗ \mathcal{B}^{\ast} B ∗ . See [3 ] , Theorem 3.3.
We will also calculate dim F q R w \dim_{\mathbb{F}_q}\mathcal{R}_w dim F q R w based on Theorem 1.10 in Section 3.
Theorem 1.12. Let dim F q R w = r w \dim_{\mathbb{F}_q}\mathcal{R}_w=r_w dim F q R w = r w , we have
∑ w = 1 ∞ r w x w = x 2 q + 1 ( 1 − x ) 2 ( 1 − 2 x ) ( 1 − 2 x + x q + 1 ) 2 . \sum_{w=1}^{\infty}r_wx^w=\frac{x^{2q+1}(1-x)^2}{(1-2x)(1-2x+x^{q+1})^2}. w = 1 ∑ ∞ r w x w = ( 1 − 2 x ) ( 1 − 2 x + x q + 1 ) 2 x 2 q + 1 ( 1 − x ) 2 .
List of notations
Some of notations in this paper are unnecessary in fact, but we still use them for convenience. Here we list main notations that may be used repeatedly in different subsections.
∣ A ∣ = the cardinality of a set A ; |A|=\text{the cardinality of a set }A; ∣ A ∣ = the cardinality of a set A ;
A ∙ = { ∅ } ⊔ ⋃ k = 1 ∞ A k ; A^{\bullet}=\{\varnothing\}\sqcup\bigcup_{k=1}^{\infty}A^k; A ∙ = { ∅ } ⊔ k = 1 ⋃ ∞ A k ;
I = Z + ; \mathcal{I}=\mathbb{Z}_{+}; I = Z + ;
[ n ] = { 1 , 2 , ⋯ , n } ; [n]=\{1,2,\cdots,n\}; [ n ] = { 1 , 2 , ⋯ , n } ;
K = F q ( θ ) = the rational function field over the finite field F q ; K=\mathbb{F}_q(\theta)=\text{the rational function field over the finite field }\mathbb{F}_q; K = F q ( θ ) = the rational function field over the finite field F q ;
D 1 = θ q − θ ; D_1=\theta^q-\theta; D 1 = θ q − θ ;
K ∞ = F q ( ( θ − 1 ) ) = the completion of K at infinite place ; K_{\infty}=\mathbb{F}_q((\theta^{-1}))=\text{the completion of }K\text{ at infinite place}; K ∞ = F q (( θ − 1 )) = the completion of K at infinite place ;
For a s = ( s 1 , ⋯ , s l ) ∈ I \boldsymbol{s}=(s_1,\cdots,s_l)\in\mathcal{I} s = ( s 1 , ⋯ , s l ) ∈ I :
dep ( s ) = l ; \operatorname{dep}(\boldsymbol{s})=l; dep ( s ) = l ;
wt ( s ) = ∑ i = 1 l s i ; \operatorname{wt}(\boldsymbol{s})=\sum_{i=1}^{l}s_i; wt ( s ) = i = 1 ∑ l s i ;
n + s = ( n + s 1 , ⋯ , s l ) ; {}^{n+}\boldsymbol{s}=(n+s_1,\cdots,s_l); n + s = ( n + s 1 , ⋯ , s l ) ;
s + n = ( s 1 , ⋯ , s l + n ) ; \boldsymbol{s}^{+n}=(s_1,\cdots,s_l+n); s + n = ( s 1 , ⋯ , s l + n ) ;
s H = ( s 1 , ⋯ , s l − 1 ) ; \boldsymbol{s}^{H}=(s_1,\cdots,s_{l-1}); s H = ( s 1 , ⋯ , s l − 1 ) ;
s T = ( s 2 , ⋯ , s l ) ; \boldsymbol{s}^{T}=(s_2,\cdots,s_l); s T = ( s 2 , ⋯ , s l ) ;
I w = { s ∈ I ∣ wt ( s ) = w } ; \mathcal{I}_w=\{\boldsymbol{s}\in\mathcal{I}\mid\operatorname{wt}(\boldsymbol{s})=w\}; I w = { s ∈ I ∣ wt ( s ) = w } ;
S w ( F ) = ⨁ s ∈ I w F s for a field F ; \mathcal{S}^{(F)}_w=\bigoplus_{\boldsymbol{s}\in\mathcal{I}_w}F\boldsymbol{s}\quad\text{for a field }F; S w ( F ) = s ∈ I w ⨁ F s for a field F ;
S ( F ) = ⨁ w ≥ 0 F S w ( F ) for a field F ; \mathcal{S}^{(F)}=\bigoplus_{w\geq0}F\mathcal{S}^{(F)}_w\quad\text{for a field }F; S ( F ) = w ≥ 0 ⨁ F S w ( F ) for a field F ;
S d ( s ) = the power sum of s ; S_d(\boldsymbol{s})=\text{the power sum of }\boldsymbol{s}; S d ( s ) = the power sum of s ;
S < d ( s ) = ∑ k < d S k ( s ) ; S_{<d}(\boldsymbol{s})=\sum_{k<d}S_k(\boldsymbol{s}); S < d ( s ) = k < d ∑ S k ( s ) ;
ζ s = the Thakur’s multiple zeta value of s ; \zeta_{\boldsymbol{s}}=\text{the Thakur’s multiple zeta value of }\boldsymbol{s}; ζ s = the Thakur’s multiple zeta value of s ;
Si d ( s ) = the Carlitz power sum of s ; \operatorname{Si}_d(\boldsymbol{s})=\text{the Carlitz power sum of }\boldsymbol{s}; Si d ( s ) = the Carlitz power sum of s ;
Si < d ( s ) = ∑ k < d Si k ( s ) ; \operatorname{Si}_{<d}(\boldsymbol{s})=\sum_{k<d}\operatorname{Si}_k(\boldsymbol{s}); Si < d ( s ) = k < d ∑ Si k ( s ) ;
Li ( s ) = the Carlitz multiple polylogarithm value of s ; \operatorname{Li}(\boldsymbol{s})=\text{the Carlitz multiple polylogarithm value of }\boldsymbol{s}; Li ( s ) = the Carlitz multiple polylogarithm value of s ;
B w ( T T ) = { ( h , z ) ∈ I w ∣ h ∈ [ q ] ∙ , z ∈ [ q − 1 ] } ; \mathcal{B}^{(\mathrm{TT})}_w=\{(h,z)\in\mathcal{I}_w\mid h\in[q]^{\bullet},z\in[q-1]\}; B w ( TT ) = {( h , z ) ∈ I w ∣ h ∈ [ q ] ∙ , z ∈ [ q − 1 ]} ;
d w ( K ) = ∣ B w ( T T ) ∣ ; d^{(K)}_w=|\mathcal{B}^{(\mathrm{TT})}_w|; d w ( K ) = ∣ B w ( TT ) ∣ ;
B R w = the set of binary relations with weight w = { [ P ; Q ] ∣ P , Q ∈ S w ( K ) , Si d ( P ) + Si d + 1 ( Q ) = 0 for all d } ; \begin{aligned}
\mathcal{BR}_w=\text{the set of binary relations with weight }w \\
&=\{[P;Q]\mid P,Q\in\mathcal{S}^{(K)}_w,\operatorname{Si}_d(P)+\operatorname{Si}_{d+1}(Q)=0\text{ for all }d\};
\end{aligned} B R w = the set of binary relations with weight w = {[ P ; Q ] ∣ P , Q ∈ S w ( K ) , Si d ( P ) + Si d + 1 ( Q ) = 0 for all d } ;
R 1 = fundamental relation = [ ( q ) ; D 1 ( 1 , q − 1 ) ] ; R_1=\text{fundamental relation}=[(q);D_1(1,q-1)]; R 1 = fundamental relation = [( q ) ; D 1 ( 1 , q − 1 )] ;
The ∗ * ∗ , ◃ \triangleleft ◃ , ⋄ \diamond ⋄ products:
S ∗ t = ( s 1 , S T ∗ t ) + ( t 1 , S ∗ t T ) + ( s 1 + t 1 , S T ∗ t T ) ; \mathcal{S} * t = (s_{1},\mathcal{S}^{T} * t) + (t_{1},\mathcal{S} * t^{T}) + (s_{1}+t_{1},\mathcal{S}^{T} * t^{T}); S ∗ t = ( s 1 , S T ∗ t ) + ( t 1 , S ∗ t T ) + ( s 1 + t 1 , S T ∗ t T ) ;
S ◃ t = ( s 1 , S T ∗ t ) ; \mathcal{S} \triangleleft t = (s_{1},\mathcal{S}^{T} * t); S ◃ t = ( s 1 , S T ∗ t ) ;
S ⋄ t = ( s 1 + t 1 , S T ∗ t T ) . \mathcal{S} \diamond t = (s_{1}+t_{1},\mathcal{S}^{T} * t^{T}). S ⋄ t = ( s 1 + t 1 , S T ∗ t T ) .
The B , B ∗ , C \mathcal{B},\mathcal{B}^{*},C B , B ∗ , C operators:
B W [ P ; Q ] = [ W ◃ P + W ⋄ Q + W ◃ Q ; 0 ] ; \mathcal{B}_{W}[P;Q] = [W \triangleleft P + W \diamond Q + W \triangleleft Q;0]; B W [ P ; Q ] = [ W ◃ P + W ⋄ Q + W ◃ Q ; 0 ] ;
B W ∗ [ P ; Q ] = [ ( w 1 ) ◃ ( w 2 ) ◃ ⋯ ◃ ( ( w r ) ◃ P + ( w r ) ⋄ Q + ( w r ) ◃ Q ) ; 0 ] ; \mathcal{B}^{*}_{W}[P;Q] = [(w_{1}) \triangleleft(w_{2}) \triangleleft\cdots\triangleleft((w_{r}) \triangleleft P + (w_{r}) \diamond Q + (w_{r}) \triangleleft Q);0]; B W ∗ [ P ; Q ] = [( w 1 ) ◃ ( w 2 ) ◃ ⋯ ◃ (( w r ) ◃ P + ( w r ) ⋄ Q + ( w r ) ◃ Q ) ; 0 ] ;
C W [ P ; Q ] = [ P ⋄ W + P ◃ W ; Q ◃ W ] ; C_{W}[P;Q] = [P \diamond W + P \triangleleft W;Q \triangleleft W]; C W [ P ; Q ] = [ P ⋄ W + P ◃ W ; Q ◃ W ] ;
[ P ; Q ] = P + Q the lift of [ P ; Q ] ; [P;Q] = P+Q \quad\text{the lift of } [P;Q]; [ P ; Q ] = P + Q the lift of [ P ; Q ] ;
R w = { P ∈ S w ( F q ) ∣ Li ( P ) = 0 } ; \mathcal{R}_{w} = \{P \in\mathcal{S}_{w}^{(\mathbb{F}_{q})} \mid\operatorname{Li}(P)=0\}; R w = { P ∈ S w ( F q ) ∣ Li ( P ) = 0 } ;
P ( S ) = [ ( q ) ( ◃ + ⋄ ) ( S + 1 + ( S , 1 ) , q − 1 ) ; − ( 1 , ( q − 1 ) ∗ ( S , q ) ) ] ; \mathcal{P}(\mathcal{S}) =
\left[
(q)(\triangleleft+\diamond)\left(\mathcal{S}^{+1}+(\mathcal{S},1),q-1\right);
-(1,(q-1)*(\mathcal{S},q))
\right]; P ( S ) = [ ( q ) ( ◃ + ⋄ ) ( S + 1 + ( S , 1 ) , q − 1 ) ; − ( 1 , ( q − 1 ) ∗ ( S , q )) ] ;
B C P w = Span F q { B u ∗ ∘ C v ∘ P ( S ) ∣ wt ( u ) + wt ( v ) + wt ( S ) + 2 q = w } ; BCP_{w} = \operatorname{Span}_{\mathbb{F}_{q}}\{\mathcal{B}^{*}_{u}\circ C_{v}\circ\mathcal{P}(\mathcal{S}) \mid\operatorname{wt}(u)+\operatorname{wt}(v)+\operatorname{wt}(\mathcal{S})+2q=w\}; B C P w = Span F q { B u ∗ ∘ C v ∘ P ( S ) ∣ wt ( u ) + wt ( v ) + wt ( S ) + 2 q = w } ;
r w = dim F q R w ; r_{w}=\dim_{\mathbb{F}_{q}}\mathcal{R}_{w}; r w = dim F q R w ;
D 0 , D 1 \mathcal{D}_{0},\mathcal{D}_{1} D 0 , D 1 : D 0 , D 1 \mathcal{D}_{0},\mathcal{D}_{1} D 0 , D 1 operators, see Theorem 2.1;
The L , H \mathcal{L},\mathcal{H} L , H operators:
L [ s ; t ] = ( s , q + t ) + 1 t ≠ ∅ ( s , q , t ) ; \mathcal{L}[s;t]=(s,q+t)+\mathbb{1}_{t\ne\varnothing}(s,q,t); L [ s ; t ] = ( s , q + t ) + 1 t = ∅ ( s , q , t ) ;
H [ s ; t ] = 1 s ≠ ∅ ( s + 1 , ( q − 1 ) ∗ t ) + ( s , 1 , ( q − 1 ) ∗ t ) ; \mathcal{H}[s;t]=\mathbb{1}_{s\ne\varnothing}(s^{+1},(q-1)*t)+(s,1,(q-1)*t); H [ s ; t ] = 1 s = ∅ ( s + 1 , ( q − 1 ) ∗ t ) + ( s , 1 , ( q − 1 ) ∗ t ) ;
L w = Span F q { L [ h ; s ] ∣ h ∈ [ q ] ∘ , wt ( h ) + wt ( s ) + q = w } ; \mathcal{L}_{w}=\operatorname{Span}_{\mathbb{F}_{q}}\{\mathcal{L}[h;s]\mid h\in[q]^{\circ},\operatorname{wt}(h)+\operatorname{wt}(s)+q=w\}; L w = Span F q { L [ h ; s ] ∣ h ∈ [ q ] ∘ , wt ( h ) + wt ( s ) + q = w } ;
Ind ( L [ s ; t ] ) = H [ s ; t ] ; \operatorname{Ind}(\mathcal{L}[s;t])=\mathcal{H}[s;t]; Ind ( L [ s ; t ]) = H [ s ; t ] ;
s i s^{i} s i , s c a n o s^{cano} s c an o , E i ( s ) E_{i}(s) E i ( s ) , E ( s ) E(s) E ( s ) : see § 2.3 ;
P [ s ; t ] = [ ( q ) ( ◃ + ⋄ ) ( s + 1 + ( s , 1 ) , ( q − 1 ) ∗ t ) ; − ( 1 , ( q − 1 ) ∗ ( s , ( q ) ( ◃ + ⋄ ) t ) ) ] ; \mathcal{P}[s;t]=
\left[
(q)(\triangleleft+\diamond)\left(s^{+1}+(s,1),(q-1)*t\right);
-(1,(q-1)*(s,(q)(\triangleleft+\diamond)t))
\right]; P [ s ; t ] = [ ( q ) ( ◃ + ⋄ ) ( s + 1 + ( s , 1 ) , ( q − 1 ) ∗ t ) ; − ( 1 , ( q − 1 ) ∗ ( s , ( q ) ( ◃ + ⋄ ) t )) ] ;
C = Span F q { [ h ; t ] ∣ h ≠ ∅ } ; \mathcal{C}=\operatorname{Span}_{\mathbb{F}_{q}}\{[h;t]\mid h\ne\varnothing\}; C = Span F q {[ h ; t ] ∣ h = ∅ } ;
H + = Span F q { ( s , ( a + 1 ) ) + ( a , 1 ) , ( q − 1 ) ∗ t ∣ s , t ∈ I , a ∈ Z + } ; H_{+}=\operatorname{Span}_{\mathbb{F}_{q}}\{(s,(a+1))+(a,1),(q-1)*t\mid s,t\in\mathcal{I},a\in\mathbb{Z}_{+}\}; H + = Span F q {( s , ( a + 1 )) + ( a , 1 ) , ( q − 1 ) ∗ t ∣ s , t ∈ I , a ∈ Z + } ;
ρ n \rho_{n} ρ n : the extraction operator, see the proof of Theorem 2.15;
Λ [ s ; t ] = [ ( q − 1 ) ∗ s ; t ] + [ s ; ( q − 1 ) ∗ t ] ; \Lambda[s;t]=[(q-1)*s;t]+[s;(q-1)*t]; Λ [ s ; t ] = [( q − 1 ) ∗ s ; t ] + [ s ; ( q − 1 ) ∗ t ] ;
U w = { P + D 1 Q ∣ P , Q ∈ S w ( F q ) , Li ( P + D 1 Q ) = 0 } ; U_{w}=\{P+D_{1}Q\mid P,Q\in\mathcal{S}_{w}^{(\mathbb{F}_{q})},\operatorname{Li}(P+D_{1}Q)=0\}; U w = { P + D 1 Q ∣ P , Q ∈ S w ( F q ) , Li ( P + D 1 Q ) = 0 } ;
V w F i x = { P ∈ V w ∣ [ P ; 0 ] ∈ B R w } . V_{w}^{\mathrm{Fix}}=\{P\in V_{w}\mid[P;0]\in\mathcal{B}\mathcal{R}_{w}\}. V w Fix = { P ∈ V w ∣ [ P ; 0 ] ∈ B R w } .
Completeness of the BCP relations
In this section, we prove Theorem 1.10 . The core idea is very similar to the one of [2 ] , with detailed techniques differing a lot.
The image of P \mathcal{P} P lies in B R w + 2 q \mathcal{BR}_{w+2q} B R w + 2 q
First step is proving that the image of P \mathcal{P} P lies in B R w + 2 q \mathcal{BR}_{w+2q} B R w + 2 q . We first construct the D 0 \mathcal{D}_0 D 0 and D 1 \mathcal{D}_1 D 1 operator.
Lemma 2.1. For any binary relation R R R of the form [ ( q ) ( ⟨ + ⋄ ⟩ ) P ; − ( 1 , ( q − 1 ) ∗ Q ) ] \left[(q)(\langle+\diamond\rangle)P;-(1,(q-1)*Q)\right] [ ( q ) (⟨ + ⋄ ⟩) P ; − ( 1 , ( q − 1 ) ∗ Q ) ] , there are the following two binary relations, denoted by D 0 ( R ) \mathcal{D}_0(R) D 0 ( R ) and D 1 ( R ) \mathcal{D}_1(R) D 1 ( R ) .
D 0 ( R ) = [ ( q ) ( ⟨ + ⋄ ⟩ ) ( 1 , P ) ; − ( 1 , ( q − 1 ) ∗ ( 1 , Q ) ) ] ; (6) \mathcal{D}_0(R)=\left[(q)(\langle+\diamond\rangle)(1,P);-(1,(q-1)*(1,Q))\right]; \tag*{(6)} D 0 ( R ) = [ ( q ) (⟨ + ⋄ ⟩) ( 1 , P ) ; − ( 1 , ( q − 1 ) ∗ ( 1 , Q )) ] ; (6)
D 1 ( R ) = [ ( q ) ( ⟨ + ⋄ ⟩ ) 1 + P ; − ( 1 , ( q − 1 ) ∗ 1 + Q ) ] ; (7) \mathcal{D}_1(R)=\left[(q)(\langle+\diamond\rangle)^{1+}P;-(1,(q-1)*{}^{1+}Q)\right]; \tag*{(7)} D 1 ( R ) = [ ( q ) (⟨ + ⋄ ⟩ ) 1 + P ; − ( 1 , ( q − 1 ) ∗ 1 + Q ) ] ; (7)
where ( 1 , P ) = ∑ i a i ( 1 , s i ) (1,P)=\sum_i a_i(1,\mathfrak{s}_i) ( 1 , P ) = ∑ i a i ( 1 , s i ) and 1 + P = ∑ i a i 1 + s i {}^{1+}P=\sum_i a_i{}^{1+}\mathfrak{s}_i 1 + P = ∑ i a i 1 + s i for any P = ∑ i a i s i P=\sum_i a_i\mathfrak{s}_i P = ∑ i a i s i .
Proof. To prove Equation (6) , we have
Si d ( q ) Si < d + 1 ( 1 , P ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 , P ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 ) Si < n ( P ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 ) Si n − 1 − 1 ( q ) Si n − 1 ( ( q ) ( ⟨ + ⋄ ⟩ ) P ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 ) Si n − 1 − 1 ( q ) Si n ( 1 , ( q − 1 ) ∗ Q ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 ) Si n − 1 − 1 ( q ) Si n ( 1 , ( q − 1 ) ) Si < n ( Q ) = − D 1 − 1 Si d ( q ) ∑ n < d + 1 Si n ( 1 ) Si < n ( Q ) = Si d + 1 ( 1 , q − 1 ) Si < d + 1 ( 1 , Q ) = Si d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q ) ) . \begin{aligned}
\operatorname{Si}_d(q)\operatorname{Si}_{<d+1}(1,P)
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1,P)\\
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1)\operatorname{Si}_{<n}(P)\\
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1)\operatorname{Si}_{n-1}^{-1}(q)\operatorname{Si}_{n-1}\bigl((q)(\langle+\diamond\rangle)P\bigr)\\
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1)\operatorname{Si}_{n-1}^{-1}(q)\operatorname{Si}_n\bigl(1,(q-1)*Q\bigr)\\
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1)\operatorname{Si}_{n-1}^{-1}(q)\operatorname{Si}_n(1,(q-1))\operatorname{Si}_{<n}(Q)\\
&=-D_1^{-1}\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1)\operatorname{Si}_{<n}(Q)\\
&=\operatorname{Si}_{d+1}(1,q-1)\operatorname{Si}_{<d+1}(1,Q)\\
&=\operatorname{Si}_{d+1}\bigl(1,(q-1)*(1,Q)\bigr).
\end{aligned} Si d ( q ) Si < d + 1 ( 1 , P ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 , P ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 ) Si < n ( P ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 ) Si n − 1 − 1 ( q ) Si n − 1 ( ( q ) (⟨ + ⋄ ⟩) P ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 ) Si n − 1 − 1 ( q ) Si n ( 1 , ( q − 1 ) ∗ Q ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 ) Si n − 1 − 1 ( q ) Si n ( 1 , ( q − 1 )) Si < n ( Q ) = − D 1 − 1 Si d ( q ) n < d + 1 ∑ Si n ( 1 ) Si < n ( Q ) = Si d + 1 ( 1 , q − 1 ) Si < d + 1 ( 1 , Q ) = Si d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q ) ) .
To prove Equation (7) , we have
Si d ( q ) Si < d + 1 ( 1 + P ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 + P ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 ) Si n ( P ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 ) ( Si < n + 1 ( P ) − Si < n ( P ) ) = Si d ( q ) ∑ n < d + 1 Si n ( 1 ) Si n ( q ) − 1 Si n + 1 ( ( 1 , ( q − 1 ) ∗ Q ) ) − Si d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q ) ) = − D 1 − 1 S i d ( q ) ∑ n < d + 1 S i n ( 1 ) S i < n + 1 ( Q ) − S i d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q ) ) = S i d + 1 ( 1 , q − 1 ) ∑ n < d + 1 S i n ( 1 ) S i < n + 1 ( Q ) − S i d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q ) ) = S i d + 1 ( 1 , q − 1 ) ( S i < d + 1 ( 1 + Q ) + S i < d + 1 ( 1 , Q ) ) − S i d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q ) ) = S i d + 1 ( 1 , ( q − 1 ) ∗ 1 + Q ) . \begin{aligned}
\operatorname{Si}_d(q)\operatorname{Si}_{<d+1}({}^{1+}P)
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n({}^{1+}P)\\
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1)\operatorname{Si}_n(P)\\
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1)\left(\operatorname{Si}_{<n+1}(P)-\operatorname{Si}_{<n}(P)\right)\\
&=\operatorname{Si}_d(q)\sum_{n<d+1}\operatorname{Si}_n(1)\operatorname{Si}_n(q)^{-1}\operatorname{Si}_{n+1}\left((1,(q-1)*Q)\right)-\operatorname{Si}_{d+1}\left(1,(q-1)*(1,Q)\right) \\
&=-D_1^{-1}S_{id}(q)\sum_{n<d+1}S_{in}(1)S_{i<n+1}(Q)-S_{id+1}(1,(q-1)*(1,Q)) \\
&=S_{id+1}(1,q-1)\sum_{n<d+1}S_{in}(1)S_{i<n+1}(Q)-S_{id+1}(1,(q-1)*(1,Q)) \\
&=S_{id+1}(1,q-1)\left(S_{i<d+1}(1+Q)+S_{i<d+1}(1,Q)\right)-S_{id+1}(1,(q-1)*(1,Q)) \\
&=S_{id+1}(1,(q-1)*{}^{1+}Q).
\end{aligned} Si d ( q ) Si < d + 1 ( 1 + P ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 + P ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 ) Si n ( P ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 ) ( Si < n + 1 ( P ) − Si < n ( P ) ) = Si d ( q ) n < d + 1 ∑ Si n ( 1 ) Si n ( q ) − 1 Si n + 1 ( ( 1 , ( q − 1 ) ∗ Q ) ) − Si d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q ) ) = − D 1 − 1 S i d ( q ) n < d + 1 ∑ S in ( 1 ) S i < n + 1 ( Q ) − S i d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q )) = S i d + 1 ( 1 , q − 1 ) n < d + 1 ∑ S in ( 1 ) S i < n + 1 ( Q ) − S i d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q )) = S i d + 1 ( 1 , q − 1 ) ( S i < d + 1 ( 1 + Q ) + S i < d + 1 ( 1 , Q ) ) − S i d + 1 ( 1 , ( q − 1 ) ∗ ( 1 , Q )) = S i d + 1 ( 1 , ( q − 1 ) ∗ 1 + Q ) .
Theorem 2.2. The image of P \mathcal{P} P lies in B R w + 2 q \mathcal{BR}_{w+2q} B R w + 2 q .
Proof. By [4 ] Proposition 6.1, we have binary relation
[ ( q ) ( ◃ + ⋄ ) ( ( 2 , q − 1 ) + ( 1 , 1 , q − 1 ) ) ; − ( 1 , ( q − 1 ) ∗ ( 1 , q ) ) ] , (8) \left[(q)(\triangleleft+\diamond)((2,q-1)+(1,1,q-1));-(1,(q-1)*(1,q))\right], \tag*{(8)} [ ( q ) ( ◃ + ⋄ ) (( 2 , q − 1 ) + ( 1 , 1 , q − 1 )) ; − ( 1 , ( q − 1 ) ∗ ( 1 , q )) ] , (8)
which is actually P ( ( 1 ) ) \mathcal{P}((1)) P (( 1 )) . In Theorem 2.1, set P = ( 2 , q − 1 ) + ( 1 , 1 , q − 1 ) P=(2,q-1)+(1,1,q-1) P = ( 2 , q − 1 ) + ( 1 , 1 , q − 1 ) and Q = ( 1 , q ) Q=(1,q) Q = ( 1 , q ) , then R = P ( ( 1 ) ) R=\mathcal{P}((1)) R = P (( 1 )) . Repeatedly apply D 0 \mathcal{D}_0 D 0 and D 1 \mathcal{D}_1 D 1 operators, note that D 0 ( P ( s ) ) = P ( ( 1 , s ) ) \mathcal{D}_0(\mathcal{P}(s))=\mathcal{P}((1,s)) D 0 ( P ( s )) = P (( 1 , s )) and D 1 ( P ( s ) ) = P ( ( 1 + s ) ) \mathcal{D}_1(\mathcal{P}(s))=\mathcal{P}((1+s)) D 1 ( P ( s )) = P (( 1 + s )) , which implies our desired result.
Decomposition of S w ( F q ) \mathcal{S}^{(\mathbb{F}_q)}_w S w ( F q ) and Ind operator
For any w ≥ q w\ge q w ≥ q , and s = ( s 1 , ⋯ , s l ) ∈ I w ∖ B w ( T T ) \mathfrak{s}=(s_1,\cdots,s_l)\in\mathcal{I}_w\setminus\mathcal{B}^{(\mathrm{TT})}_w s = ( s 1 , ⋯ , s l ) ∈ I w ∖ B w ( TT ) , write s = ( h , q + r , t ) \mathfrak{s}=(\mathfrak{h},q+r,\mathfrak{t}) s = ( h , q + r , t ) , where h = ( s 1 , ⋯ , s k − 1 ) ∈ [ q ] ∙ \mathfrak{h}=(s_1,\cdots,s_{k-1})\in[q]^\bullet h = ( s 1 , ⋯ , s k − 1 ) ∈ [ q ] ∙ ; either r > 0 r>0 r > 0 , or r = 0 r=0 r = 0 and t = ∅ \mathfrak{t}=\emptyset t = ∅ (in this case we set ( r , t ) = ∅ (r,\mathfrak{t})=\emptyset ( r , t ) = ∅ ). Set
L [ h ; ( r , t ) ] = ( h , q + r , t ) + 1 r ≠ 0 ( h , q , r , t ) \mathcal{L}[\mathfrak{h};(r,\mathfrak{t})]=(\mathfrak{h},q+r,\mathfrak{t})+\mathbb{1}_{r\ne0}(\mathfrak{h},q,r,\mathfrak{t}) L [ h ; ( r , t )] = ( h , q + r , t ) + 1 r = 0 ( h , q , r , t )
and
H [ h ; ( r , t ) ] = 1 h ≠ ∅ ( h + 1 , ( q − 1 ) ∗ ( r , t ) ) + ( h , 1 , ( q − 1 ) ∗ ( r , t ) ) . \mathcal{H}[\mathfrak{h};(r,\mathfrak{t})]=\mathbb{1}_{\mathfrak{h}\ne\emptyset}(\mathfrak{h}^{+1},(q-1)*(r,\mathfrak{t}))+(\mathfrak{h},1,(q-1)*(r,\mathfrak{t})). H [ h ; ( r , t )] = 1 h = ∅ ( h + 1 , ( q − 1 ) ∗ ( r , t )) + ( h , 1 , ( q − 1 ) ∗ ( r , t )) .
We may directly write L [ h ; s ] \mathcal{L}[\mathfrak{h};\mathfrak{s}] L [ h ; s ] to denote L [ h ; ( s 1 , s ′ ) ] \mathcal{L}[\mathfrak{h};(s_1,\mathfrak{s}') ] L [ h ; ( s 1 , s ′ )] , so does H \mathcal{H} H . We view L , H \mathcal{L},\mathcal{H} L , H as the linear maps from Span F q { [ s ; t ] } \operatorname{Span}_{\mathbb{F}_q}\{[\mathfrak{s};\mathfrak{t}]\} Span F q {[ s ; t ]} to S ( F q ) \mathcal{S}^{(\mathbb{F}_q)} S ( F q ) by linear extension.
Im, Kim and Ngo Dac constructed the following binary relation (See [4 ] , Section 4.2):
{ [ L [ h ; t ] ; D 1 H [ h ; t ] ] , if h = ∅ ; [ L [ h ; t ] + D 1 H [ h ; t ] ; 0 ] , if h ≠ ∅ . \begin{cases}
[\mathcal{L}[\mathfrak{h};\mathfrak{t}];\mathcal{D}_1\mathcal{H}[\mathfrak{h};\mathfrak{t}]], & \text{if }\mathfrak{h}=\emptyset;\\
[\mathcal{L}[\mathfrak{h};\mathfrak{t}]+\mathcal{D}_1\mathcal{H}[\mathfrak{h};\mathfrak{t}];0], & \text{if }\mathfrak{h}\ne\emptyset.
\end{cases} { [ L [ h ; t ] ; D 1 H [ h ; t ]] , [ L [ h ; t ] + D 1 H [ h ; t ] ; 0 ] , if h = ∅ ; if h = ∅.
To give a direct sum decomposition of S w ( F q ) \mathcal{S}^{(\mathbb{F}_q)}_w S w ( F q ) , we first introduce the (depth, lex)-order which will be repeatedly used.
Definition 2.3. The (depth, lex)-order ≺ \prec ≺ on I \mathcal{I} I is defined as follows. For any two tuples s , t ∈ I w \mathfrak{s},\mathfrak{t}\in\mathcal{I}_w s , t ∈ I w , define s ≺ t \mathfrak{s}\prec\mathfrak{t} s ≺ t if and only if
either dep ( s ) < dep ( t ) \operatorname{dep}(\mathfrak{s})<\operatorname{dep}(\mathfrak{t}) dep ( s ) < dep ( t ) ,
or dep ( s ) = dep ( t ) \operatorname{dep}(\mathfrak{s})=\operatorname{dep}(\mathfrak{t}) dep ( s ) = dep ( t ) and s \mathfrak{s} s is lexicographically smaller than t \mathfrak{t} t .
Lemma 2.4. Set L w = Span F q { L [ h ; s ] ∣ h ∈ [ q ] ∙ , wt ( h ) + wt ( s ) + q = w } \mathcal{L}_w=\operatorname{Span}_{\mathbb{F}_q}\{\mathcal{L}[\mathfrak{h};\mathfrak{s}]\mid\mathfrak{h}\in[q]^\bullet,\ \operatorname{wt}(\mathfrak{h})+\operatorname{wt}(\mathfrak{s})+q=w\} L w = Span F q { L [ h ; s ] ∣ h ∈ [ q ] ∙ , wt ( h ) + wt ( s ) + q = w } . Then
S w ( F q ) = L w ⊕ Span F q B w ( T T ) . \mathcal{S}^{(\mathbb{F}_q)}_w=\mathcal{L}_w\oplus\operatorname{Span}_{\mathbb{F}_q}\mathcal{B}^{(\mathrm{TT})}_w. S w ( F q ) = L w ⊕ Span F q B w ( TT ) . Moreover, R w \mathcal{R}_w R w is a subspace of L w \mathcal{L}_w L w .
Proof. For the direct sum decomposition, note that for any s = ( h , q + r , t ) ∈ I w ∖ B w ( T T ) \mathfrak{s}=(\mathfrak{h},q+\mathfrak{r},\mathfrak{t})\in I_w\setminus B_w^{(\mathrm{TT})} s = ( h , q + r , t ) ∈ I w ∖ B w ( TT ) , s \mathfrak{s} s is exactly the smallest term among the tuples of L [ h ; ( r , t ) ] \mathcal{L}[\mathfrak{h};(\mathfrak{r},\mathfrak{t})] L [ h ; ( r , t )] in the (depth, lex)-order. By comparing the smallest term, we obtain the direct composition.
To prove R w ⊆ L w \mathcal{R}_w\subseteq\mathcal{L}_w R w ⊆ L w , for any R ∈ R w R\in\mathcal{R}_w R ∈ R w , write R = L + T R=L+T R = L + T with L = ∑ a i L [ h i ; s i ] ∈ L w L=\sum a_i\mathcal{L}[\mathfrak{h}_i;\mathfrak{s}_i]\in\mathcal{L}_w L = ∑ a i L [ h i ; s i ] ∈ L w and T ∈ Span F q B w ( T T ) T\in\operatorname{Span}_{\mathbb{F}_q}B_w^{(\mathrm{TT})} T ∈ Span F q B w ( TT ) . Let H = ∑ a i H [ h i ; s i ] H=\sum a_i\mathcal{H}[\mathfrak{h}_i;\mathfrak{s}_i] H = ∑ a i H [ h i ; s i ] . Since R ∈ R w R\in\mathcal{R}_w R ∈ R w , we have Li ( R ) = Li ( L ) + Li ( T ) = 0 \operatorname{Li}(R)=\operatorname{Li}(L)+\operatorname{Li}(T)=0 Li ( R ) = Li ( L ) + Li ( T ) = 0 . But Li ( L ) = − D 1 Li ( H ) \operatorname{Li}(L)=-D_1\operatorname{Li}(H) Li ( L ) = − D 1 Li ( H ) , we have Li ( T ) − D 1 Li ( H ) = 0 \operatorname{Li}(T)-D_1\operatorname{Li}(H)=0 Li ( T ) − D 1 Li ( H ) = 0 . Now repeat this procedure for H H H until all tuples belonging to B w ( T T ) B_w^{(\mathrm{TT})} B w ( TT ) , then we obtain a F q ( D 1 ) \mathbb{F}_q(D_1) F q ( D 1 ) -linear relation among B w ( T T ) B_w^{(\mathrm{TT})} B w ( TT ) with the zero-degree part T T T . By the Theorem 1.2 , there have to be T = 0 T=0 T = 0 .
Remark 2.5. The proof of R w ⊆ L w \mathcal{R}_w\subseteq\mathcal{L}_w R w ⊆ L w is essentially the one in [4 ] .
Next we define Ind : L w → S w ( F q ) \operatorname{Ind}:\mathcal{L}_w\to\mathcal{S}_w^{(\mathbb{F}_q)} Ind : L w → S w ( F q ) by Ind ( L [ h ; s ] ) = H [ h ; s ] \operatorname{Ind}(\mathcal{L}[\mathfrak{h};\mathfrak{s}])=\mathcal{H}[\mathfrak{h};\mathfrak{s}] Ind ( L [ h ; s ]) = H [ h ; s ] for h ∈ [ q ] ∗ \mathfrak{h}\in[q]^* h ∈ [ q ] ∗ , which is exactly the Ind operator in [4 ] but is extended to L w \mathcal{L}_w L w . It is easy to see Ind preserves R w \mathcal{R}_w R w by definition. Moreover, it is nilpotent on R w \mathcal{R}_w R w .
Lemma 2.6. For any w ≥ q w\ge q w ≥ q , Ind acts on R w \mathcal{R}_w R w nilpotently.
Proof. For any R ∈ R w R\in\mathcal{R}_w R ∈ R w , note that if Ind ( R ) ≠ 0 \operatorname{Ind}(R)\ne0 Ind ( R ) = 0 , then in the (depth, lex)-order ≺ \prec ≺ , min ≺ R ≺ min ≺ Ind ( R ) \min_{\prec}R\prec\min_{\prec}\operatorname{Ind}(R) min ≺ R ≺ min ≺ Ind ( R ) , where min ≺ P \min_{\prec}P min ≺ P means the smallest tuple of P P P . Since there are only finitely many tuples for a fixed weight, there exists a k ∈ Z + k\in\mathbb{Z}_+ k ∈ Z + such that Ind k = 0 \operatorname{Ind}^k=0 Ind k = 0 .
The following theorem will be used to prove our final result.
Theorem 2.7. For any w ≥ q w\ge q w ≥ q and subspace L ⊆ R w L\subseteq\mathcal{R}_w L ⊆ R w , if Ind − 1 L ⊆ L \operatorname{Ind}^{-1}L\subseteq L Ind − 1 L ⊆ L , then L = R w L=\mathcal{R}_w L = R w .
Proof. It is a direct corollary of Theorem 2.6.
Kernel of L \mathcal{L} L
We now determine ker L \ker\mathcal{L} ker L , where we can see the similarity in spirit between the method in this paper and the idea in [2 ] .
For any w ≥ q w\ge q w ≥ q , s = ( s 1 , ⋯ , s l ) ∈ I w ∖ B w ( T T ) \mathfrak{s}=(s_1,\cdots,s_l)\in I_w\setminus B_w^{(\mathrm{TT})} s = ( s 1 , ⋯ , s l ) ∈ I w ∖ B w ( TT ) , and s i s_i s i which is a component of s \mathfrak{s} s such that s i > q s_i>q s i > q or s i = q s_i=q s i = q and i = l i=l i = l (Here we don’t require s i s_i s i is the first component satisfying this condition), write s = ( h i , q + r i , t i ) \mathfrak{s}=(\mathfrak{h}_i,q+r_i,\mathfrak{t}_i) s = ( h i , q + r i , t i ) , s i = ( h i , q , r i , t i ) \mathfrak{s}^i=(\mathfrak{h}_i,q,r_i,\mathfrak{t}_i) s i = ( h i , q , r i , t i ) and E i ( s ) = [ h i ; ( r i , t i ) ] E_i(\mathfrak{s})=[\mathfrak{h}_i;(r_i,\mathfrak{t}_i)] E i ( s ) = [ h i ; ( r i , t i )] . Use the previous notation, we still write s = ( h , q + r , t ) \mathfrak{s}=(\mathfrak{h},q+r,\mathfrak{t}) s = ( h , q + r , t ) if q + r q+r q + r is the first component satisfying condition, and we call the position of q + r q+r q + r is a canonical position. We also set E ( s ) = [ h ; ( r , t ) ] E(\mathfrak{s})=[\mathfrak{h};(r,\mathfrak{t})] E ( s ) = [ h ; ( r , t )] , s c a n o = ( h , q , r , t ) \mathfrak{s}^{\mathrm{cano}}=(\mathfrak{h},q,r,\mathfrak{t}) s cano = ( h , q , r , t ) .
Theorem 2.8. For any w ∈ Z + w\in\mathbb{Z}_+ w ∈ Z + , L w = Span F q { L [ h ; s ] ∣ wt ( h ) + wt ( s ) + q = w } \mathcal{L}_w=\operatorname{Span}_{\mathbb{F}_q}\{\mathcal{L}[\mathfrak{h};\mathfrak{s}]\mid\operatorname{wt}(\mathfrak{h})+\operatorname{wt}(\mathfrak{s})+q=w\} L w = Span F q { L [ h ; s ] ∣ wt ( h ) + wt ( s ) + q = w } .
Proof. Denote the right hand side by L w ′ \mathcal{L}'_w L w ′ . For s = ( s 1 , s 2 , ⋯ , s l ) ∈ I w \mathfrak{s}=(s_1,s_2,\cdots,s_l)\in I_w s = ( s 1 , s 2 , ⋯ , s l ) ∈ I w , it can be uniquely written as ( q k 1 + r 1 , q k 2 + r 2 , ⋯ , q k l + r l ) (qk_1+r_1,qk_2+r_2,\cdots,qk_l+r_l) ( q k 1 + r 1 , q k 2 + r 2 , ⋯ , q k l + r l ) with k i ≥ 0 k_i\ge0 k i ≥ 0 , 1 ≤ r i ≤ q 1\le r_i\le q 1 ≤ r i ≤ q . Define the F q \mathbb{F}_q F q -linear map E : S w ( F q ) → Span F q B w ( T T ) E:\mathcal{S}_w^{(\mathbb{F}_q)}\to\operatorname{Span}_{\mathbb{F}_q}B_w^{(\mathrm{TT})} E : S w ( F q ) → Span F q B w ( TT ) by
E ( s ) = { ( − 1 ) ∑ k i ( q , ⋯ , q , r 1 , q , ⋯ , q , r 2 , ⋯ , q , ⋯ , q , r l ) , r l ≠ q , 0 , r l = q E(\mathfrak{s})=
\begin{cases}
(-1)^{\sum k_i}(q,\cdots,q,r_1,q,\cdots,q,r_2,\cdots,q,\cdots,q,r_l), & r_l\ne q,\\
0, & r_l=q
\end{cases} E ( s ) = { ( − 1 ) ∑ k i ( q , ⋯ , q , r 1 , q , ⋯ , q , r 2 , ⋯ , q , ⋯ , q , r l ) , 0 , r l = q , r l = q
It is easy to see E ∣ Span F q B w ( T T ) = id E|_{\operatorname{Span}_{\mathbb{F}_q}B_w^{(\mathrm{TT})}}=\operatorname{id} E ∣ Span F q B w ( TT ) = id and E ∘ L = 0 E\circ\mathcal{L}=0 E ∘ L = 0 . Define another F q \mathbb{F}_q F q -linear map f : S ( F q ) → Span F q { [ s ; t ] } f:\mathcal{S}^{(\mathbb{F}_q)}\to\operatorname{Span}_{\mathbb{F}_q}\{[\mathfrak{s};\mathfrak{t}]\} f : S ( F q ) → Span F q {[ s ; t ]} inductively in the reverse (dep,lex)-order
f ( s ) = { 0 , s ∈ B w ( T T ) , E ( s ) − f ( s c a n o ) , s ∈ L w ∖ B w ( T T ) , s c a n o ≠ s , E ( s ) , s ∈ L w ∖ B w ( T T ) , s c a n o = s . f(\mathfrak{s})=
\begin{cases}
0, & \mathfrak{s}\in\mathcal{B}^{(\mathrm{TT})}_w,\\
E(\mathfrak{s})-f(\mathfrak{s}^{\mathrm{cano}}), & \mathfrak{s}\in\mathcal{L}_w\setminus\mathcal{B}^{(\mathrm{TT})}_w,\ \mathfrak{s}^{\mathrm{cano}}\ne\mathfrak{s},\\
E(\mathfrak{s}), & \mathfrak{s}\in\mathcal{L}_w\setminus\mathcal{B}^{(\mathrm{TT})}_w,\ \mathfrak{s}^{\mathrm{cano}}=\mathfrak{s}.
\end{cases} f ( s ) = ⎩ ⎨ ⎧ 0 , E ( s ) − f ( s cano ) , E ( s ) , s ∈ B w ( TT ) , s ∈ L w ∖ B w ( TT ) , s cano = s , s ∈ L w ∖ B w ( TT ) , s cano = s .
Now we can begin the proof, by induction in the reverse (dep,lex)-order, we have L ∘ f = id − E \mathcal{L}\circ f=\operatorname{id}-\mathcal{E} L ∘ f = id − E , which implies ker E = { P ∈ S w ( F q ) ∣ P = L ∘ f ( P ) } \ker\mathcal{E}=\{P\in\mathcal{S}^{(\mathbb{F}_q)}_w\mid P=\mathcal{L}\circ f(P)\} ker E = { P ∈ S w ( F q ) ∣ P = L ∘ f ( P )} . Note that the image of f f f lies in Span F q { [ h ; s ] ∣ h ∈ [ q ] ∘ , wt ( h ) + wt ( s ) + q = w } \operatorname{Span}_{\mathbb{F}_q}\{[\mathfrak{h};\mathfrak{s}]\mid\mathfrak{h}\in[q]^{\circ},\operatorname{wt}(\mathfrak{h})+\operatorname{wt}(\mathfrak{s})+q=w\} Span F q {[ h ; s ] ∣ h ∈ [ q ] ∘ , wt ( h ) + wt ( s ) + q = w } , we have ker E ⊆ L w \ker\mathcal{E}\subseteq\mathcal{L}_w ker E ⊆ L w . Since E ∘ L = 0 \mathcal{E}\circ\mathcal{L}=0 E ∘ L = 0 , we have ker E = L w \ker\mathcal{E}=\mathcal{L}_w ker E = L w . Because L w ′ ⊆ ker E = L w ⊆ L w ′ \mathcal{L}'_w\subseteq\ker\mathcal{E}=\mathcal{L}_w\subseteq\mathcal{L}'_w L w ′ ⊆ ker E = L w ⊆ L w ′ , we are done.
Theorem 2.9. For any w ∈ Z + w\in\mathbb{Z}_+ w ∈ Z + , Set
Q w = Span F q { − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − 1 r j ≠ 0 E i ( s j ) ∣ s ∈ I w , i < j run over all possible positions } , Q_w=\operatorname{Span}_{\mathbb{F}_q}\{-E_i(\mathfrak{s})+E_j(\mathfrak{s})+E_{j+1}(\mathfrak{s}^{i})-\mathbb{1}_{r_j\ne0}E_i(\mathfrak{s}^{j})\mid\mathfrak{s}\in\mathcal{I}_w,\ i<j\text{ run over all possible positions}\}, Q w = Span F q { − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − 1 r j = 0 E i ( s j ) ∣ s ∈ I w , i < j run over all possible positions } , then ker L = Q w \ker\mathcal{L}=Q_w ker L = Q w .
Proof. We first prove that for any s ∈ I w \mathfrak{s}\in\mathcal{I}_w s ∈ I w and possible i i i , we have E i ( s ) ≡ f ∘ L ( E i ( s ) ) ( m o d Q w ) E_i(\mathfrak{s})\equiv f\circ\mathcal{L}(E_i(\mathfrak{s}))\pmod{Q_w} E i ( s ) ≡ f ∘ L ( E i ( s )) ( mod Q w ) .
We do it by induction on s \mathfrak{s} s with respect to reverse (dep,lex)-order.
When E i = E E_i=E E i = E (i.e. i i i is canonical), it is an equality. In other cases, if r i > 0 r_i>0 r i > 0 , we have
− E i ( s ) + E ( s ) ≡ − E ( s i ) + E i + 1 ( s c a n o ) . (9) -E_i(\mathfrak{s})+E(\mathfrak{s})\equiv-E(\mathfrak{s}^{i})+E_{i+1}(\mathfrak{s}^{\mathrm{cano}}). \tag*{(9)} − E i ( s ) + E ( s ) ≡ − E ( s i ) + E i + 1 ( s cano ) . (9)
We first show − E ( s i ) + E i + 1 ( s c a n o ) ≡ − f ( s i ) + f ( s c a n o ) -E(\mathfrak{s}^{i})+E_{i+1}(\mathfrak{s}^{\mathrm{cano}})\equiv-f(\mathfrak{s}^{i})+f(\mathfrak{s}^{\mathrm{cano}}) − E ( s i ) + E i + 1 ( s cano ) ≡ − f ( s i ) + f ( s cano ) . It suffices to show
− E i + 1 ( s c a n o ) + E ( s c a n o ) ≡ f ( ( s c a n o ) c a n o ) − f ( ( s i ) c a n o ) , -E_{i+1}(\mathfrak{s}^{\mathrm{cano}})+E(\mathfrak{s}^{\mathrm{cano}})\equiv f((\mathfrak{s}^{\mathrm{cano}})^{\mathrm{cano}})-f((\mathfrak{s}^{i})^{\mathrm{cano}}), − E i + 1 ( s cano ) + E ( s cano ) ≡ f (( s cano ) cano ) − f (( s i ) cano ) ,
Using Equation (9) , it suffices to show
− E ( ( s c a n o ) i + 1 ) + E i + 2 ( ( s c a n o ) c a n o ) ≡ f ( ( s c a n o ) c a n o ) − f ( ( s i ) c a n o ) . -E((\mathfrak{s}^{\mathrm{cano}})^{i+1})+E_{i+2}((\mathfrak{s}^{\mathrm{cano}})^{\mathrm{cano}})\equiv f((\mathfrak{s}^{\mathrm{cano}})^{\mathrm{cano}})-f((\mathfrak{s}^{i})^{\mathrm{cano}}). − E (( s cano ) i + 1 ) + E i + 2 (( s cano ) cano ) ≡ f (( s cano ) cano ) − f (( s i ) cano ) .
Note that ( s i ) c a n o = ( s c a n o ) i + 1 (\mathfrak{s}^{i})^{\mathrm{cano}}=(\mathfrak{s}^{\mathrm{cano}})^{i+1} ( s i ) cano = ( s cano ) i + 1 , inductive assumption implies desired result.
If r i = 0 r_i=0 r i = 0 , then
E i ( s ) ≡ E ( s ) − E i + 1 ( s c a n o ) . E_i(\mathfrak{s})\equiv E(\mathfrak{s})-E_{i+1}(\mathfrak{s}^{\mathrm{cano}}). E i ( s ) ≡ E ( s ) − E i + 1 ( s cano ) .
Inductive assumption implies
E i + 1 ( s c a n o ) ≡ f ( s c a n o ) , E_{i+1}(\mathfrak{s}^{\mathrm{cano}})\equiv f(\mathfrak{s}^{\mathrm{cano}}), E i + 1 ( s cano ) ≡ f ( s cano ) ,
hence E i ( s ) ≡ f ( s ) E_i(\mathfrak{s})\equiv f(\mathfrak{s}) E i ( s ) ≡ f ( s ) .
Then we have
E i ( s ) ≡ f ( s ) + 1 r i > 0 f ( s i ) ≡ f ∘ L ( E i ( s ) ) . E_i(\mathfrak{s})\equiv f(\mathfrak{s})+\mathbb{1}_{r_i>0}f(\mathfrak{s}^{i})\equiv f\circ\mathcal{L}(E_i(\mathfrak{s})). E i ( s ) ≡ f ( s ) + 1 r i > 0 f ( s i ) ≡ f ∘ L ( E i ( s )) .
Now for any R ∈ ker L R\in\ker\mathcal{L} R ∈ ker L , we can always find some s i ∈ S w ( F q ) \mathfrak{s}_i\in\mathcal{S}^{(\mathbb{F}_q)}_w s i ∈ S w ( F q ) such that R = ∑ a i E j i ( s i ) R=\sum a_iE_{j_i}(\mathfrak{s}_i) R = ∑ a i E j i ( s i ) , hence R ≡ 0 R\equiv0 R ≡ 0 . So ker L ⊆ Q w \ker\mathcal{L}\subseteq Q_w ker L ⊆ Q w , the converse can be checked directly.
General P \mathcal{P} P operator and cut identities
In ideas and techniques, this subsection is very similar to [3 ] . The goal of this subsection is to construct a more general P \mathcal{P} P operator, and realize it by using the original C , P \mathcal{C},\mathcal{P} C , P operators. For s , t ∈ I \mathfrak{s},\mathfrak{t}\in\mathcal{I} s , t ∈ I , we define
P [ s ; t ] = [ ( q ) ( ◃ + ⋄ ) ( s + 1 + ( s , 1 ) , ( q − 1 ) ∗ t ) ; − ( 1 , ( q − 1 ) ∗ ( s , ( q ) ( ◃ + ⋄ ) t ) ) ] . \mathcal{P}[\mathfrak{s};\mathfrak{t}]=\left[(q)(\triangleleft+\diamond)\left(\mathfrak{s}^{+1}+(\mathfrak{s},1),(q-1)\ast\mathfrak{t}\right);-\left(1,(q-1)\ast\left(\mathfrak{s},(q)(\triangleleft+\diamond)\mathfrak{t}\right)\right)\right]. P [ s ; t ] = [ ( q ) ( ◃ + ⋄ ) ( s + 1 + ( s , 1 ) , ( q − 1 ) ∗ t ) ; − ( 1 , ( q − 1 ) ∗ ( s , ( q ) ( ◃ + ⋄ ) t ) ) ] .
Note that it is the previous P \mathcal{P} P operator if set t = ∅ \mathfrak{t}=\varnothing t = ∅ . We will show the image of general P \mathcal{P} P still lies in B R \mathbb{B}\mathbb{R} BR .
To do this, we first introduce the cut of tuples. For a s = ( s 1 , ⋯ , s l ) ∈ I \mathfrak{s}=(s_1,\cdots,s_l)\in\mathcal{I} s = ( s 1 , ⋯ , s l ) ∈ I , a cut of s \mathfrak{s} s is a pair of tuple u , v \mathfrak{u},\mathfrak{v} u , v , such that s = ( u , v ) \mathfrak{s}=(\mathfrak{u},\mathfrak{v}) s = ( u , v ) , i.e. u = ( s 1 , ⋯ , s k ) , v = ( s k + 1 , ⋯ , s l ) \mathfrak{u}=(s_1,\cdots,s_k),\mathfrak{v}=(s_{k+1},\cdots,s_l) u = ( s 1 , ⋯ , s k ) , v = ( s k + 1 , ⋯ , s l ) for some k k k , possibly u = ∅ \mathfrak{u}=\varnothing u = ∅ or v = ∅ \mathfrak{v}=\varnothing v = ∅ . The following cut identities are complex but intuitive.
Lemma 2.10. For any s , t ∈ I ∖ { ∅ } \mathfrak{s},\mathfrak{t}\in\mathcal{I}\setminus\{\varnothing\} s , t ∈ I ∖ { ∅ } and c ∈ Z + c\in\mathbb{Z}_{+} c ∈ Z + ,
(i)
( s , c ) ∗ t = ∑ t = ( u , v ) ( s ∗ u , ( c ) ( ◃ + ⋄ ) v ) ; (10) (\mathfrak{s},c)\ast\mathfrak{t}=\sum_{\mathfrak{t}=(\mathfrak{u},\mathfrak{v})}(\mathfrak{s}\ast\mathfrak{u},(c)(\triangleleft+\diamond)\mathfrak{v}); \tag*{(10)} ( s , c ) ∗ t = t = ( u , v ) ∑ ( s ∗ u , ( c ) ( ◃ + ⋄ ) v ) ; (10) (ii)
( s + 1 + ( s , 1 ) ) ∗ t = ∑ t = ( u , v ) ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , v ) ; \left(\mathfrak{s}^{+1}+(\mathfrak{s},1)\right)\ast\mathfrak{t}=\sum_{\mathfrak{t}=(\mathfrak{u},\mathfrak{v})}\left((\mathfrak{s}\ast\mathfrak{u})^{+1}+(\mathfrak{s}\ast\mathfrak{u},1),\mathfrak{v}\right); ( s + 1 + ( s , 1 ) ) ∗ t = t = ( u , v ) ∑ ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , v ) ; (iii)
( s + 1 + ( s , 1 ) , q − 1 ) ∗ t = ∑ t = ( u , v ) ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , ( q − 1 ) ∗ v ) ; (11) \left(\mathfrak{s}^{+1}+(\mathfrak{s},1),q-1\right)\ast\mathfrak{t}=\sum_{\mathfrak{t}=(\mathfrak{u},\mathfrak{v})}\left((\mathfrak{s}\ast\mathfrak{u})^{+1}+(\mathfrak{s}\ast\mathfrak{u},1),(q-1)\ast\mathfrak{v}\right); \tag*{(11)} ( s + 1 + ( s , 1 ) , q − 1 ) ∗ t = t = ( u , v ) ∑ ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , ( q − 1 ) ∗ v ) ; (11) where we set ( c ) ( ◃ + ⋄ ) ∅ = ( c ) (c)(\triangleleft+\diamond)\varnothing=(c) ( c ) ( ◃ + ⋄ ) ∅ = ( c ) .
Proof. For a = ( a 1 , ⋯ , a k ) , b = ( b 1 , ⋯ , b l ) \mathfrak{a}=(a_1,\cdots,a_k),\mathfrak{b}=(b_1,\cdots,b_l) a = ( a 1 , ⋯ , a k ) , b = ( b 1 , ⋯ , b l ) , Equation (1) yields that
a ∗ b = ∑ ′ ( c 1 ∣ c 2 ∣ ⋯ ∣ c k + l ) (12) \mathfrak{a}\ast\mathfrak{b}=\sum{}'(c_1|c_2|\cdots|c_{k+l}) \tag*{(12)} a ∗ b = ∑ ′ ( c 1 ∣ c 2 ∣ ⋯ ∣ c k + l ) (12)
where the restricted sum means:
c 1 c 2 ⋯ c k + l c_1c_2\cdots c_{k+l} c 1 c 2 ⋯ c k + l is a permutation of a 1 , ⋯ , a k , b 1 , ⋯ , b l a_1,\cdots,a_k,b_1,\cdots,b_l a 1 , ⋯ , a k , b 1 , ⋯ , b l preserving the order of a i a_i a i ’s and b i b_i b i ’s;
“∣ | ∣ ” is “+ + + ” or “,” satisfying there are at most one a i a_i a i and one b i b_i b i between a pair of adjacent “,”;
if two terms differ only by a commutation of addition, they are counted once in the sum (for example, ( a 1 + b 1 , a 2 , b 2 ) (a_1+b_1,a_2,b_2) ( a 1 + b 1 , a 2 , b 2 ) and ( b 1 + a 1 , a 2 , b 2 ) (b_1+a_1,a_2,b_2) ( b 1 + a 1 , a 2 , b 2 ) are only counted once).
Then (i) is directly yielded by Equation (12) .
For (ii), use Equation (12) to expand the left hand side, there are terms of forms ( c 1 ∣ c 2 ∣ ⋯ ∣ a k + 1 ∣ ⋯ ∣ c k + l ) (c_1|c_2|\cdots|a_k+1|\cdots|c_{k+l}) ( c 1 ∣ c 2 ∣ ⋯ ∣ a k + 1∣ ⋯ ∣ c k + l ) corresponding to s + 1 ∗ t \mathfrak{s}^{+1}\ast\mathfrak{t} s + 1 ∗ t and ( c 1 ∣ c 2 ∣ ⋯ ∣ a k ∣ ⋯ ∣ 1 ∣ ⋯ ∣ c k + l ) (c_1|c_2|\cdots|a_k|\cdots|1|\cdots|c_{k+l}) ( c 1 ∣ c 2 ∣ ⋯ ∣ a k ∣ ⋯ ∣1∣ ⋯ ∣ c k + l ) corresponding to ( s , 1 ) ∗ t (\mathfrak{s},1)\ast\mathfrak{t} ( s , 1 ) ∗ t . By (3), we may assume that the ( c 1 ∣ c 2 ∣ ⋯ ∣ a k + 1 ∣ ⋯ ∣ c k + l ) = ( c 1 ∣ c 2 ∣ ⋯ ∣ a k + 1 , ⋯ ∣ c k + l ) (c_1|c_2|\cdots|a_k+1|\cdots|c_{k+l})=(c_1|c_2|\cdots|a_k+1,\cdots|c_{k+l}) ( c 1 ∣ c 2 ∣ ⋯ ∣ a k + 1∣ ⋯ ∣ c k + l ) = ( c 1 ∣ c 2 ∣ ⋯ ∣ a k + 1 , ⋯ ∣ c k + l ) and ( c 1 ∣ c 2 ∣ ⋯ ∣ a k ∣ ⋯ ∣ 1 ∣ ⋯ ∣ c k + l ) = ( c 1 ∣ c 2 ∣ ⋯ ∣ a k ∣ ⋯ ∣ 1 , ⋯ ∣ c k + l ) (c_1|c_2|\cdots|a_k|\cdots|1|\cdots|c_{k+l})=(c_1|c_2|\cdots|a_k|\cdots|1,\cdots|c_{k+l}) ( c 1 ∣ c 2 ∣ ⋯ ∣ a k ∣ ⋯ ∣1∣ ⋯ ∣ c k + l ) = ( c 1 ∣ c 2 ∣ ⋯ ∣ a k ∣ ⋯ ∣1 , ⋯ ∣ c k + l ) . Set u = ( b 1 , ⋯ , b n ) \mathfrak{u}=(b_1,\cdots,b_n) u = ( b 1 , ⋯ , b n ) such that b n b_n b n precedes a l + 1 a_l+1 a l + 1 or 1 1 1 , and b n + 1 b_{n+1} b n + 1 follows a l + 1 a_l+1 a l + 1 or 1 1 1 . Summing over the terms with the same u \mathfrak{u} u , it is ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , v (\mathfrak{s}\ast\mathfrak{u})^{+1}+(\mathfrak{s}\ast\mathfrak{u},1),\mathfrak{v} ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , v , so we are done.
A similar argument to (ii) proves (iii).
Theorem 2.11. For any s , t ∈ I \mathfrak{s},\mathfrak{t}\in\mathcal{I} s , t ∈ I , C t P ( s ) = ∑ t = ( u , v ) P [ s ∗ u ; v ] \mathcal{C}_{\mathfrak{t}}\mathcal{P}(\mathfrak{s})=\sum_{\mathfrak{t}=(u,v)}\mathcal{P}[\mathfrak{s}*\mathfrak{u};\mathfrak{v}] C t P ( s ) = ∑ t = ( u , v ) P [ s ∗ u ; v ]
Proof. It suffices to show
[ ( q ) ( △ + ⋄ ) ( s + 1 + ( s , 1 ) , q − 1 ) ( △ + ⋄ ) t ; − ( 1 , ( q − 1 ) ∗ ( s , q ) ) ◃ t ] = ∑ t = ( u , v ) P [ s ∗ u ; v ] \left[(q)(\triangle+\diamond)\left(\mathfrak{s}^{+1}+(\mathfrak{s},1),q-1\right)(\triangle+\diamond)\mathfrak{t};-(1,(q-1)*(\mathfrak{s},q))\triangleleft\mathfrak{t}\right]=\sum_{\mathfrak{t}=(u,v)}\mathcal{P}[\mathfrak{s}*\mathfrak{u};\mathfrak{v}] [ ( q ) ( △ + ⋄ ) ( s + 1 + ( s , 1 ) , q − 1 ) ( △ + ⋄ ) t ; − ( 1 , ( q − 1 ) ∗ ( s , q )) ◃ t ] = t = ( u , v ) ∑ P [ s ∗ u ; v ]
It is easy to check that for any P , Q , S ∈ S ( F q ) P,Q,S\in\mathcal{S}(\mathbb{F}_q) P , Q , S ∈ S ( F q ) , ( P ( △ + ⋄ ) Q ) ( △ + ⋄ ) S = P ( △ + ⋄ ) ( Q ∗ S ) (P(\triangle+\diamond)Q)(\triangle+\diamond)S=P(\triangle+\diamond)(Q*S) ( P ( △ + ⋄ ) Q ) ( △ + ⋄ ) S = P ( △ + ⋄ ) ( Q ∗ S ) (check it hold for single tuples then extend linearly). So we need to show
[ ( q ) ( △ + ⋄ ) ( ( s + 1 + ( s , 1 ) , q − 1 ) ∗ t ) ; − ( 1 , ( q − 1 ) ∗ ( s , q ) ) ◃ t ] = ∑ t = ( u , v ) P [ s ∗ u ; v ] \left[(q)(\triangle+\diamond)\left(\left(\mathfrak{s}^{+1}+(\mathfrak{s},1),q-1\right)*\mathfrak{t}\right);-(1,(q-1)*(\mathfrak{s},q))\triangleleft\mathfrak{t}\right]=\sum_{\mathfrak{t}=(u,v)}\mathcal{P}[\mathfrak{s}*\mathfrak{u};\mathfrak{v}] [ ( q ) ( △ + ⋄ ) ( ( s + 1 + ( s , 1 ) , q − 1 ) ∗ t ) ; − ( 1 , ( q − 1 ) ∗ ( s , q )) ◃ t ] = t = ( u , v ) ∑ P [ s ∗ u ; v ]
Using Equation (11) , we have
L H S = [ ∑ t = ( u , v ) ( q ) ( △ + ⋄ ) ( ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , ( q − 1 ) ∗ v ) ; − ( 1 , ( q − 1 ) ∗ ( s , q ) ) ◃ t ] \mathrm{LHS}=[\sum_{\mathfrak{t}=(u,v)}(q)(\triangle+\diamond)(((\mathfrak{s}*\mathfrak{u})^{+1}+(\mathfrak{s}*\mathfrak{u},1),(q-1)*\mathfrak{v});-(1,(q-1)*(\mathfrak{s},q))\triangleleft\mathfrak{t}] LHS = [ t = ( u , v ) ∑ ( q ) ( △ + ⋄ ) ((( s ∗ u ) + 1 + ( s ∗ u , 1 ) , ( q − 1 ) ∗ v ) ; − ( 1 , ( q − 1 ) ∗ ( s , q )) ◃ t ]
Using Equation (10) ,
R H S = ∑ t = ( u , v ) [ ( q ) ( △ + ⋄ ) ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , ( q − 1 ) ∗ v ) ; − ( 1 , ( q − 1 ) ∗ ( s ∗ u , ( q ) ( △ + ⋄ ) v ) ) ] = [ ∑ t = ( u , v ) ( q ) ( △ + ⋄ ) ( ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , ( q − 1 ) ∗ v ) ; − ( 1 , ( q − 1 ) ∗ ( s , q ) ∗ t ) ) ] \begin{aligned}
\mathrm{RHS}=\sum_{\mathfrak{t}=(u,v)}\left[(q)(\triangle+\diamond)\left((\mathfrak{s}*\mathfrak{u})^{+1}+(\mathfrak{s}*\mathfrak{u},1),(q-1)*\mathfrak{v}\right);-(1,(q-1)*(\mathfrak{s}*\mathfrak{u},(q)(\triangle+\diamond)\mathfrak{v}))\right] \\
&=\left[\sum_{\mathfrak{t}=(u,v)}(q)(\triangle+\diamond)\left(\left((\mathfrak{s}*\mathfrak{u})^{+1}+(\mathfrak{s}*\mathfrak{u},1),(q-1)*\mathfrak{v}\right);-(1,(q-1)*(\mathfrak{s},q)*\mathfrak{t})\right)\right]
\end{aligned} RHS = t = ( u , v ) ∑ [ ( q ) ( △ + ⋄ ) ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , ( q − 1 ) ∗ v ) ; − ( 1 , ( q − 1 ) ∗ ( s ∗ u , ( q ) ( △ + ⋄ ) v )) ] = t = ( u , v ) ∑ ( q ) ( △ + ⋄ ) ( ( ( s ∗ u ) + 1 + ( s ∗ u , 1 ) , ( q − 1 ) ∗ v ) ; − ( 1 , ( q − 1 ) ∗ ( s , q ) ∗ t ) )
Note that ( 1 , ( q − 1 ) ∗ ( s , q ) ) ◃ t = ( 1 , ( q − 1 ) ∗ ( s , q ) ∗ t ) (1,(q-1)*(\mathfrak{s},q))\triangleleft\mathfrak{t}=(1,(q-1)*(\mathfrak{s},q)*\mathfrak{t}) ( 1 , ( q − 1 ) ∗ ( s , q )) ◃ t = ( 1 , ( q − 1 ) ∗ ( s , q ) ∗ t ) , we done. □
Now we show the general P \mathcal{P} P can be realized by using the original C \mathcal{C} C and P \mathcal{P} P operators.
Corollary 2.12. For any s , t ∈ I \mathfrak{s},\mathfrak{t}\in\mathcal{I} s , t ∈ I , P [ s ; t ] \mathcal{P}[\mathfrak{s};\mathfrak{t}] P [ s ; t ] is a linear combination of C a P ( b ) \mathcal{C}_a\mathcal{P}(\mathfrak{b}) C a P ( b ) for some a , b \mathfrak{a},\mathfrak{b} a , b .
Proof. We prove it by induction on dep ( t ) \operatorname{dep}(\mathfrak{t}) dep ( t ) . When dep ( t ) = 0 \operatorname{dep}(\mathfrak{t})=0 dep ( t ) = 0 , t = ∅ \mathfrak{t}=\varnothing t = ∅ , there is nothing to prove. Assume we have done for all t \mathfrak{t} t with dep < d \operatorname{dep}<d dep < d . Now for a t \mathfrak{t} t with depth d d d , by previous theorem, we have
P [ s ; t ] = C t P ( s ) − ∑ t = ( u , v ) u ≠ ∅ P [ s ∗ u ; v ] . \mathcal{P}[\mathfrak{s};\mathfrak{t}]=\mathcal{C}_{\mathfrak{t}}\mathcal{P}(\mathfrak{s})-\sum_{\substack{\mathfrak{t}=(u,v)\\u\ne\varnothing}}\mathcal{P}[\mathfrak{s}*\mathfrak{u};\mathfrak{v}]. P [ s ; t ] = C t P ( s ) − t = ( u , v ) u = ∅ ∑ P [ s ∗ u ; v ] .
The v \mathfrak{v} v ’s in RHS all have depth less than d d d . By inductive assumption, RHS can be written as a linear combination of C a P ( b ) \mathcal{C}_a\mathcal{P}(\mathfrak{b}) C a P ( b ) , then we are done. □
We now use Theorem 2.12 to describe B C P w \mathcal{BCP}_w BC P w .
Theorem 2.13. For any w ∈ Z + w\in\mathbb{Z}_{+} w ∈ Z + , B C P w = H ( ker L ) \mathcal{BCP}_w=\mathcal{H}(\ker\mathcal{L}) BC P w = H ( ker L ) .
Proof. We first show H ( ker L ) ⊆ B C P w \mathcal{H}(\ker\mathcal{L}) \subseteq\mathcal{BCP}_w H ( ker L ) ⊆ BC P w . By Theorem 2.9 , it suffices to show H ( − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − 1 r j ≠ 0 E i ( s j ) ) ∈ B C P w \mathcal{H}(-E_i(\mathfrak{s})+E_j(\mathfrak{s})+E_{j+1}(\mathfrak{s}^i)-\mathbb{1}_{r_j\ne0}E_i(\mathfrak{s}^j)) \in\mathcal{BCP}_w H ( − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − 1 r j = 0 E i ( s j )) ∈ BC P w for any s ∈ I w \mathfrak{s}\in\mathcal{I}_w s ∈ I w and possibly i , j i,j i , j .
For a s = ( h , q + r i , m , q + r j , t ) \mathfrak{s}=(\mathfrak{h},q+r_i,\mathfrak{m},q+r_j,t) s = ( h , q + r i , m , q + r j , t ) with r i , r j > 0 r_i,r_j>0 r i , r j > 0 , we have
− E i ( s ) + E j ( s ) + E j + 1 ( s i ) − E i ( s j ) = − [ h ; ( r i , m , ( q ) ( ⋄ + ⋄ ) ( r j , t ) ) ] + [ ( h , ( q ) ( ⋄ + ⋄ ) ( r i , m ) ) ; ( r j , t ) ] . -E_i(\mathfrak{s})+E_j(\mathfrak{s})+E_{j+1}(\mathfrak{s}^i)-E_i(\mathfrak{s}^j)=-\left[\mathfrak{h};(r_i,\mathfrak{m},(q)(\diamond+\diamond)(r_j,t))\right]+\left[(\mathfrak{h},(q)(\diamond+\diamond)(r_i,\mathfrak{m}));(r_j,t)\right]. − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − E i ( s j ) = − [ h ; ( r i , m , ( q ) ( ⋄ + ⋄ ) ( r j , t )) ] + [ ( h , ( q ) ( ⋄ + ⋄ ) ( r i , m )) ; ( r j , t ) ] .
Then
H ( − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − E i ( s j ) ) = − ( h + 1 + ( h , 1 ) , ( q − 1 ) ∗ ( r i , m , ( q ) ( ⋄ + ⋄ ) ( r j , t ) ) ) + ( h , ( ( q ) ( ⋄ + ⋄ ) ( ( r i , m ) + 1 + ( r i , m , 1 ) ) , ( q − 1 ) ∗ ( r j , t ) ) ) . \mathcal{H}(-E_i(\mathfrak{s})+E_j(\mathfrak{s})+E_{j+1}(\mathfrak{s}^i)-E_i(\mathfrak{s}^j))=-\left(\mathfrak{h}^{+1}+(\mathfrak{h},1),(q-1)*(r_i,\mathfrak{m},(q)(\diamond+\diamond)(r_j,t))\right)
+\left(\mathfrak{h},\left((q)(\diamond+\diamond)((r_i,\mathfrak{m})^{+1}+(r_i,\mathfrak{m},1)),(q-1)*(r_j,t)\right)\right). H ( − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − E i ( s j )) = − ( h + 1 + ( h , 1 ) , ( q − 1 ) ∗ ( r i , m , ( q ) ( ⋄ + ⋄ ) ( r j , t )) ) + ( h , ( ( q ) ( ⋄ + ⋄ ) (( r i , m ) + 1 + ( r i , m , 1 )) , ( q − 1 ) ∗ ( r j , t ) ) ) .
We can see
P [ ( r i , m ) ; ( r j , t ) ] = [ ( q ) ( ⋄ + ⋄ ) ( ( r i , m ) + 1 + ( r i , m , 1 ) , ( q − 1 ) ∗ ( r j , t ) ) ; − ( 1 , ( q − 1 ) ∗ ( r i , m , ( q ) ( ⋄ + ⋄ ) ( r j , t ) ) ) ] . \mathcal{P}\left[(r_i,\mathfrak{m});(r_j,t)\right]=\left[(q)(\diamond+\diamond)((r_i,\mathfrak{m})^{+1}+(r_i,\mathfrak{m},1),(q-1)*(r_j,t));-\left(1,(q-1)*(r_i,\mathfrak{m},(q)(\diamond+\diamond)(r_j,t))\right)\right]. P [ ( r i , m ) ; ( r j , t ) ] = [ ( q ) ( ⋄ + ⋄ ) (( r i , m ) + 1 + ( r i , m , 1 ) , ( q − 1 ) ∗ ( r j , t )) ; − ( 1 , ( q − 1 ) ∗ ( r i , m , ( q ) ( ⋄ + ⋄ ) ( r j , t )) ) ] .
So we have B h ∗ ( P [ ( r i , m ) ; ( r j , t ) ] ) = [ H ( − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − E i ( s j ) ) ; 0 ] \mathcal{B}_{\mathfrak{h}}^*\left(\mathcal{P}\left[(r_i,\mathfrak{m});(r_j,t)\right]\right)=\left[\mathcal{H}(-E_i(\mathfrak{s})+E_j(\mathfrak{s})+E_{j+1}(\mathfrak{s}^i)-E_i(\mathfrak{s}^j));0\right] B h ∗ ( P [ ( r i , m ) ; ( r j , t ) ] ) = [ H ( − E i ( s ) + E j ( s ) + E j + 1 ( s i ) − E i ( s j )) ; 0 ] (if h = ∅ \mathfrak{h}=\varnothing h = ∅ , we need a lift).
For s = ( h , q + r i , m , q ) \mathfrak{s}=(\mathfrak{h},q+r_i,\mathfrak{m},q) s = ( h , q + r i , m , q ) with r i > 0 r_i>0 r i > 0 , we can obtain desired results similarly.
For B C P w ⊆ H ( ker L ) \mathcal{BCP}_w\subseteq\mathcal{H}(\ker\mathcal{L}) BC P w ⊆ H ( ker L ) , it suffices to show B h ∗ ( P [ s ; t ] ) ∈ H ( ker L ) \mathcal{B}_{\mathfrak{h}}^*(\mathcal{P}[\mathfrak{s};t])\in\mathcal{H}(\ker\mathcal{L}) B h ∗ ( P [ s ; t ]) ∈ H ( ker L ) for all h , s , t ∈ I \mathfrak{h},\mathfrak{s},t\in\mathcal{I} h , s , t ∈ I . Let R = [ ( h , L [ 0 ; s ] ) ; t ] − [ h ; L [ s ; t ] ] R=[(\mathfrak{h},\mathcal{L}[0;\mathfrak{s}]);t]-[\mathfrak{h};\mathcal{L}[\mathfrak{s};t]] R = [( h , L [ 0 ; s ]) ; t ] − [ h ; L [ s ; t ]] , direct calculation shows L ( R ) = 0 \mathcal{L}(R)=0 L ( R ) = 0 and H ( R ) = B h ∗ ( P [ s ; t ] ) ‾ \mathcal{H}(R)=\overline{\mathcal{B}_{\mathfrak{h}}^*(\mathcal{P}[\mathfrak{s};t])} H ( R ) = B h ∗ ( P [ s ; t ]) , so we are done. □
Remark 2.14. If we admit the results in [2 ] , then we have done, because H ( ker L ) \mathcal{H}(\ker\mathcal{L}) H ( ker L ) is actually the space spanned by all quadruple-carry relations.
Separate singletons
Let C = Span F q { [ h ; t ] ∣ h ≠ ∅ } \mathcal{C}=\operatorname{Span}_{\mathbb{F}_q}\{[\mathfrak{h};t]\mid\mathfrak{h}\ne\varnothing\} C = Span F q {[ h ; t ] ∣ h = ∅ } . We study Im H ∣ C \operatorname{Im}\mathcal{H}|_{\mathcal{C}} Im H ∣ C precisely in this subsection.
It is easy to see that
H ( C ) = Span F q { ( s , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) ∣ s , t ∈ I , a ∈ Z + } . (13) \mathcal{H}(\mathcal{C})=\operatorname{Span}_{\mathbb{F}_q}\{(\mathfrak{s},(a+1)+(a,1),(q-1)*t)\mid\mathfrak{s},t\in\mathcal{I},a\in\mathbb{Z}_+\}. \tag*{(13)} H ( C ) = Span F q {( s , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) ∣ s , t ∈ I , a ∈ Z + } . (13)
Denote the above set by H + H_+ H + , we will show the following lemma.
Lemma 2.15. For any P ∈ S ( F q ) P\in\mathcal{S}^{(\mathbb{F}_q)} P ∈ S ( F q )
(i) P ∈ H + ⟺ ( 1 , P ) ∈ H + P\in H_+\Longleftrightarrow(1,P)\in H_+ P ∈ H + ⟺ ( 1 , P ) ∈ H + ;
(ii) P ∈ H + ⟺ ( q − 1 ) ∗ P ∈ H + P\in H_+\Longleftrightarrow(q-1)*P\in H_+ P ∈ H + ⟺ ( q − 1 ) ∗ P ∈ H +
Proof. (i) “⟹ \Longrightarrow ⟹ ” is obvious by Equation (13) , in fact H + H_+ H + is stable under adding any prefix (we will repeatedly use this fact).
To prove “⟸ \Longleftarrow ⟸ ”, for a A ∈ H + A \in H_+ A ∈ H + , using Equation (13) , it can be written as
A = ∑ i ( ( i + 1 ) + ( i , 1 ) , B i ) + ∑ j ( j , C j ) , for some i , j ∈ Z + , B i ∈ ( q − 1 ) ∗ S ( F q ) , C j ∈ H + . A=\sum_i\bigl((i+1)+(i,1),B_i\bigr)+\sum_j(j,C_j),\qquad\text{for some }i,j\in\mathbb{Z}_+, B_i\in(q-1)*\mathcal{S}^{(\mathbb{F}_q)}, C_j\in H_+. A = i ∑ ( ( i + 1 ) + ( i , 1 ) , B i ) + j ∑ ( j , C j ) , for some i , j ∈ Z + , B i ∈ ( q − 1 ) ∗ S ( F q ) , C j ∈ H + .
To see this, just write A A A as a linear combination of elements in RHS of Equation (13) , then separate the terms with s = ∅ \mathfrak{s}=\varnothing s = ∅ and the terms with s ≠ ∅ \mathfrak{s}\ne\varnothing s = ∅ , for the latter ones, replace s \mathfrak{s} s by s T \mathfrak{s}^{T} s T to obtain C j C_j C j .
Now we define the extraction operator ρ n \rho_n ρ n for n ∈ Z + n\in\mathbb{Z}_+ n ∈ Z + . For a tuple s = ( s 1 , s T ) \mathfrak{s}=(s_1,\mathfrak{s}^{T}) s = ( s 1 , s T ) , we define
ρ n ( s ) = { 0 , s 1 ≠ n , s T , s 1 = n . \rho_n(\mathfrak{s})=
\begin{cases}
0, & s_1\ne n,\\
\mathfrak{s}^{T}, & s_1=n.
\end{cases} ρ n ( s ) = { 0 , s T , s 1 = n , s 1 = n .
Apply it to A A A , we have
ρ 1 ( A ) = ( 1 , B 1 ) + C 1 , \rho_1(A)=(1,B_1)+C_1, ρ 1 ( A ) = ( 1 , B 1 ) + C 1 ,
ρ n ( A ) = B n − 1 + ( 1 , B n ) + C n , n ≥ 2. \rho_n(A)=B_{n-1}+(1,B_n)+C_n,\qquad n\ge2. ρ n ( A ) = B n − 1 + ( 1 , B n ) + C n , n ≥ 2.
There is a smallest N N N such that ρ n ( A ) = 0 \rho_n(A)=0 ρ n ( A ) = 0 for any n > N n>N n > N . So for n ≥ N n\ge N n ≥ N , we have B n = − ( 1 , B n + 1 ) − C n + 1 B_n=-(1,B_{n+1})-C_{n+1} B n = − ( 1 , B n + 1 ) − C n + 1 . For n n n large enough, B n = 0 B_n=0 B n = 0 , hence B n ∈ H + B_n\in H_+ B n ∈ H + . Since C n ∈ H + C_n\in H_+ C n ∈ H + and B n + 1 ∈ H + ⟹ ( 1 , B n + 1 ) ∈ H + B_{n+1}\in H_+\Longrightarrow(1,B_{n+1})\in H_+ B n + 1 ∈ H + ⟹ ( 1 , B n + 1 ) ∈ H + , we have B n ∈ H + B_n\in H_+ B n ∈ H + for all n ≥ N n\ge N n ≥ N by backward induction. As result, we have
ρ 1 ( A ) = ( 1 , B 1 ) + C 1 ∈ H + if N = 1 , (14) \rho_1(A)=(1,B_1)+C_1\in H_+\quad\text{if }N=1, \tag*{(14)} ρ 1 ( A ) = ( 1 , B 1 ) + C 1 ∈ H + if N = 1 , (14)
ρ N ( A ) = B N − 1 + ( 1 , B N ) + C N ∈ ( q − 1 ) ∗ S ( F q ) + H + if N ≥ 2. (15) \rho_N(A)=B_{N-1}+(1,B_N)+C_N\in(q-1)*\mathcal{S}^{(\mathbb{F}_q)}+H_+\quad\text{if }N\ge2. \tag*{(15)} ρ N ( A ) = B N − 1 + ( 1 , B N ) + C N ∈ ( q − 1 ) ∗ S ( F q ) + H + if N ≥ 2. (15)
Apply Equation (14) to A = ( 1 , P ) A=(1,P) A = ( 1 , P ) , we have P ∈ H + P\in H_+ P ∈ H + .
(ii) To prove “⟹ \Longrightarrow ⟹ ”, note that
( q − 1 ) ∗ ( s , t ) = ( ( q − 1 ) ∗ s , t ) + ( s , ( q − 1 ) ∗ t ) − ( s , q − 1 , t ) . (q-1)*(\mathfrak{s},t)=((q-1)*\mathfrak{s},t)+(\mathfrak{s},(q-1)*t)-(\mathfrak{s},q-1,t). ( q − 1 ) ∗ ( s , t ) = (( q − 1 ) ∗ s , t ) + ( s , ( q − 1 ) ∗ t ) − ( s , q − 1 , t ) .
So we have
( q − 1 ) ∗ ( s , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) = ( ( q − 1 ) ∗ s , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) + ( s , ( q − 1 ) ∗ ( ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) ) − ( s , q − 1 , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) , \begin{aligned}
(q-1)*\bigl(\mathfrak{s},(a+1)+(a,1),(q-1)*t\bigr)
={}&\bigl((q-1)*\mathfrak{s},(a+1)+(a,1),(q-1)*t\bigr)\\
&+\bigl(\mathfrak{s},(q-1)*\bigl((a+1)+(a,1),(q-1)*t\bigr)\bigr)\\
&-\bigl(\mathfrak{s},q-1,(a+1)+(a,1),(q-1)*t\bigr),
\end{aligned} ( q − 1 ) ∗ ( s , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) = ( ( q − 1 ) ∗ s , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) + ( s , ( q − 1 ) ∗ ( ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) ) − ( s , q − 1 , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) ,
where the first and the last terms in RHS belong to H + H_+ H + , so we only need to prove
( s , ( q − 1 ) ∗ ( ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) ) ∈ H + . \bigl(\mathfrak{s},(q-1)*\bigl((a+1)+(a,1),(q-1)*t\bigr)\bigr)\in H_+. ( s , ( q − 1 ) ∗ ( ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) ) ∈ H + .
It can be implied from the following calculation
( q − 1 ) ∗ ( ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) = ( ( q + a ) + ( q + a − 1 , 1 ) , ( q − 1 ) ∗ t ) + ( q − 1 , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) + ( ( a , q ) + ( a , q − 1 , 1 ) , ( q − 1 ) ∗ t ) + ( ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ ( q − 1 ) ∗ t ) . (q-1) * \bigl((a+1)+(a,1),(q-1)*t\bigr)
=\bigl((q+a)+(q+a-1,1),(q-1)*t\bigr)+\bigl(q-1,(a+1)+(a,1),(q-1)*t\bigr)
+\bigl((a,q)+(a,q-1,1),(q-1)*t\bigr)+\bigl((a+1)+(a,1),(q-1)*(q-1)*t\bigr). ( q − 1 ) ∗ ( ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) = ( ( q + a ) + ( q + a − 1 , 1 ) , ( q − 1 ) ∗ t ) + ( q − 1 , ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ t ) + ( ( a , q ) + ( a , q − 1 , 1 ) , ( q − 1 ) ∗ t ) + ( ( a + 1 ) + ( a , 1 ) , ( q − 1 ) ∗ ( q − 1 ) ∗ t ) .
To show “⇐ \Leftarrow ⇐ ”, we first show that if ( q − 1 ) ∗ ( 1 , P ) ∈ H + (q-1)*(1,P)\in H_+ ( q − 1 ) ∗ ( 1 , P ) ∈ H + , then ( q − 1 ) ∗ P ∈ H + (q-1)*P\in H_+ ( q − 1 ) ∗ P ∈ H + . In fact, the greatest first component of the tuples in ( q − 1 ) ∗ ( 1 , P ) (q-1)*(1,P) ( q − 1 ) ∗ ( 1 , P ) is q q q , so ρ q ( ( q − 1 ) ∗ ( 1 , P ) ) ∈ ( q − 1 ) ∗ S ( F q ) + H + \rho_q\bigl((q-1)*(1,P)\bigr)\in(q-1)*\mathcal{S}(\mathbb{F}_q)+H_+ ρ q ( ( q − 1 ) ∗ ( 1 , P ) ) ∈ ( q − 1 ) ∗ S ( F q ) + H + by Equation (15) . Since ρ q ( ( q − 1 ) ∗ ( 1 , P ) ) = P \rho_q\bigl((q-1)*(1,P)\bigr)=P ρ q ( ( q − 1 ) ∗ ( 1 , P ) ) = P , we have ( ( q ) + ( q − 1 , 1 ) , P ) ∈ H + \bigl((q)+(q-1,1),P\bigr)\in H_+ ( ( q ) + ( q − 1 , 1 ) , P ) ∈ H + . Since ( q − 1 ) ∗ ( 1 , P ) = ( q , P ) + ( q − 1 , 1 , P ) + ( 1 , ( q − 1 ) ∗ P ) (q-1)*(1,P)=(q,P)+(q-1,1,P)+(1,(q-1)*P) ( q − 1 ) ∗ ( 1 , P ) = ( q , P ) + ( q − 1 , 1 , P ) + ( 1 , ( q − 1 ) ∗ P ) , we are done by using (i).
Now we prove ( q − 1 ) ∗ P ∈ H + ⟹ P ∈ H + (q-1)*P\in H_+\Longrightarrow P\in H_+ ( q − 1 ) ∗ P ∈ H + ⟹ P ∈ H + by induction on wt ( P ) \operatorname{wt}(P) wt ( P ) . For wt ( P ) = 0 \operatorname{wt}(P)=0 wt ( P ) = 0 , there is nothing to prove. Assume we have done for wt < w \operatorname{wt}<w wt < w , now for P ∈ S ( F q ) w P\in\mathcal{S}(\mathbb{F}_q)_w P ∈ S ( F q ) w , write it as P = ∑ 1 ≤ i ≤ m ( i , P i ) P=\sum_{1\leq i\leq m}(i,P_i) P = ∑ 1 ≤ i ≤ m ( i , P i ) , where m m m is the maximal first component among the tuples of P P P , then
( q − 1 ) ∗ P = ( q − 1 , P ) + ∑ 1 ≤ i ≤ m ( q − 1 + i , P i ) + ∑ 1 ≤ i ≤ m ( i , ( q − 1 ) ∗ P i ) . (q-1)*P=(q-1,P)+\sum_{1\leq i\leq m}(q-1+i,P_i)+\sum_{1\leq i\leq m}(i,(q-1)*P_i). ( q − 1 ) ∗ P = ( q − 1 , P ) + 1 ≤ i ≤ m ∑ ( q − 1 + i , P i ) + 1 ≤ i ≤ m ∑ ( i , ( q − 1 ) ∗ P i ) .
Use Equation (15) , we have
ρ q − 1 + m ( ( q − 1 ) ∗ P ) = P m ∈ ( q − 1 ) ∗ S ( F q ) + H + . \rho_{q-1+m}\bigl((q-1)*P\bigr)=P_m\in(q-1)*\mathcal{S}(\mathbb{F}_q)+H_+. ρ q − 1 + m ( ( q − 1 ) ∗ P ) = P m ∈ ( q − 1 ) ∗ S ( F q ) + H + .
We may choose a decomposition P m = S + T P_m=S+T P m = S + T with S ∈ ( q − 1 ) ∗ S ( F q ) , T ∈ H + S\in(q-1)*\mathcal{S}(\mathbb{F}_q),T\in H_+ S ∈ ( q − 1 ) ∗ S ( F q ) , T ∈ H + , then
P = ∑ 1 ≤ i ≤ m − 1 ( i , P i ) + ( m , S ) + ( m , T ) . P=\sum_{1\leq i\leq m-1}(i,P_i)+(m,S)+(m,T). P = 1 ≤ i ≤ m − 1 ∑ ( i , P i ) + ( m , S ) + ( m , T ) .
Since ( m − 1 , 1 , S ) + ( m , S ) ∈ H + (m-1,1,S)+(m,S)\in H_+ ( m − 1 , 1 , S ) + ( m , S ) ∈ H + , we have
P ≡ ∑ 1 ≤ i ≤ m − 1 ( i , P i ) − ( m − 1 , 1 , S ) ( m o d H + ) . P\equiv\sum_{1\leq i\leq m-1}(i,P_i)-(m-1,1,S)\pmod{H_+}. P ≡ 1 ≤ i ≤ m − 1 ∑ ( i , P i ) − ( m − 1 , 1 , S ) ( mod H + ) .
Repeatedly use the above argument, we have
P ≡ ( 1 , Q ) ( m o d H + ) , for some Q ∈ S ( F q ) . P\equiv(1,Q)\pmod{H_+},\qquad\text{for some }Q\in\mathcal{S}(\mathbb{F}_q). P ≡ ( 1 , Q ) ( mod H + ) , for some Q ∈ S ( F q ) .
Since ( q − 1 ) ∗ H + ⊆ H + (q-1)*H_+\subseteq H_+ ( q − 1 ) ∗ H + ⊆ H + , we have ( q − 1 ) ∗ ( 1 , Q ) ∈ H + (q-1)*(1,Q)\in H_+ ( q − 1 ) ∗ ( 1 , Q ) ∈ H + , which implies ( q − 1 ) ∗ Q ∈ H + (q-1)*Q\in H_+ ( q − 1 ) ∗ Q ∈ H + . As wt ( Q ) < wt ( P ) \operatorname{wt}(Q)<\operatorname{wt}(P) wt ( Q ) < wt ( P ) , we have Q ∈ H + Q\in H_+ Q ∈ H + . Then by (i), we are done.
Kernel of H H H
The final of our preparation is determining ker H \ker H ker H .
Define F q \mathbb{F}_q F q -linear map Λ : C → C \Lambda:\mathcal{C}\to\mathcal{C} Λ : C → C by
Λ [ s ; t ] = [ ( q − 1 ) ∗ s ; t ] + [ s ; ( q − 1 ) ∗ t ] . \Lambda[s;t]=[(q-1)*s;t]+[s;(q-1)*t]. Λ [ s ; t ] = [( q − 1 ) ∗ s ; t ] + [ s ; ( q − 1 ) ∗ t ] .
Lemma 2.16. For any [ P ; Q ] ∈ C [P;Q] \in\mathcal{C} [ P ; Q ] ∈ C ,
(i) L ( Λ [ P ; Q ] ) = ( q − 1 ) ∗ L [ P ; Q ] ; \mathcal{L}(\Lambda[P;Q])=(q-1)*\mathcal{L}[P;Q]; L ( Λ [ P ; Q ]) = ( q − 1 ) ∗ L [ P ; Q ] ;
(ii) H ( Λ [ P ; Q ] ) = ( q − 1 ) ∗ H [ P ; Q ] . \mathcal{H}(\Lambda[P;Q])=(q-1)*\mathcal{H}[P;Q]. H ( Λ [ P ; Q ]) = ( q − 1 ) ∗ H [ P ; Q ] .
Proof. It suffices to show theorem for [ P ; Q ] = [ s ; t ] [P;Q]=[s;t] [ P ; Q ] = [ s ; t ] .
(i) We have
L H S = ( ( q − 1 ) ∗ s , q + t ) + ( ( q − 1 ) ∗ s , q , t ) + ( s , q + ( ( q − 1 ) ∗ t ) ) + ( s , q , ( q − 1 ) ∗ t ) , \mathrm{LHS}=\bigl((q-1)*s,q^{+}t\bigr)+\bigl((q-1)*s,q,t\bigr)+\bigl(s,q^{+}\bigl((q-1)*t\bigr)\bigr)+\bigl(s,q,(q-1)*t\bigr), LHS = ( ( q − 1 ) ∗ s , q + t ) + ( ( q − 1 ) ∗ s , q , t ) + ( s , q + ( ( q − 1 ) ∗ t ) ) + ( s , q , ( q − 1 ) ∗ t ) , R H S = ( q − 1 ) ∗ ( ( s , q + t ) + ( s , q , t ) ) . \mathrm{RHS}=(q-1)*\bigl((s,q^{+}t)+(s,q,t)\bigr). RHS = ( q − 1 ) ∗ ( ( s , q + t ) + ( s , q , t ) ) . Note that
q + ( ( q − 1 ) ∗ t ) = ( q − 1 ) ∗ q + t − ( q − 1 , q + t ) + ( 2 q − 1 , t ) , q^{+}\bigl((q-1)*t\bigr)=(q-1)*q^{+}t-(q-1,q^{+}t)+(2q-1,t), q + ( ( q − 1 ) ∗ t ) = ( q − 1 ) ∗ q + t − ( q − 1 , q + t ) + ( 2 q − 1 , t ) , then directly calculation implies.
(ii) Note that
( ( q − 1 ) ∗ s ) + 1 = ( q − 1 ) ∗ s + 1 + ( s , q ) − ( s + 1 , q − 1 ) , \bigl((q-1)*s\bigr)^{+1}=(q-1)*s^{+1}+(s,q)-(s^{+1},q-1), ( ( q − 1 ) ∗ s ) + 1 = ( q − 1 ) ∗ s + 1 + ( s , q ) − ( s + 1 , q − 1 ) , Similar calculation implies.
Theorem 2.17.
ker H = Span F q { s ; H ( R ) ∣ ( s + 1 + ( s , 1 ) , Λ ( R ) ) ∣ R ∈ C } , \ker\mathcal{H}=\operatorname{Span}_{\mathbb{F}_q}\{s;\mathcal{H}(R)\mid(s^{+1}+(s,1),\Lambda(R))\mid R\in\mathcal{C}\}, ker H = Span F q { s ; H ( R ) ∣ ( s + 1 + ( s , 1 ) , Λ ( R )) ∣ R ∈ C } , where ( s , [ μ ; b ] ) = [ ( s , u ) ; b ] (s,[\mu;b])=[(s,u);b] ( s , [ μ ; b ]) = [( s , u ) ; b ] , and we set ∅ + 1 + ( ∅ , 1 ) = ( 1 ) \varnothing^{+1}+(\varnothing,1)=(1) ∅ + 1 + ( ∅ , 1 ) = ( 1 ) .
Proof. Using,
H ( h , R ) = ( h , H ( R ) ) , for any h ∈ I , R ∈ C . \mathcal{H}(h,R)=(h,\mathcal{H}(R)),\qquad\text{for any }h\in\mathcal{I},R\in\mathcal{C}. H ( h , R ) = ( h , H ( R )) , for any h ∈ I , R ∈ C . Direct calculation implies “⊇ \supseteq ⊇ ”.
We prove “⊆ \subseteq ⊆ ” by induction on wt ( P ) + wt ( Q ) \operatorname{wt}(P)+\operatorname{wt}(Q) wt ( P ) + wt ( Q ) for H [ P ; Q ] = 0 \mathcal{H}[P;Q]=0 H [ P ; Q ] = 0 . If wt ( P ) + wt ( Q ) = 0 \operatorname{wt}(P)+\operatorname{wt}(Q)=0 wt ( P ) + wt ( Q ) = 0 , then [ P ; Q ] = k [ ∅ ; ∅ ] [P;Q]=k[\varnothing;\varnothing] [ P ; Q ] = k [ ∅ ; ∅ ] for some k ∈ F q k\in\mathbb{F}_q k ∈ F q , the result is obvious. Assume we have done for wt ( P ) + wt ( Q ) < w \operatorname{wt}(P)+\operatorname{wt}(Q)<w wt ( P ) + wt ( Q ) < w . For a R ∈ ker H R\in\ker\mathcal{H} R ∈ ker H , it can be written as a sum ∑ [ ∅ ; T ] + ∑ [ P ; Q ] \sum[\varnothing;T]+\sum[P;Q] ∑ [ ∅ ; T ] + ∑ [ P ; Q ] for some T ∈ S ( F q ) T\in\mathcal{S}^{(\mathbb{F}_q)} T ∈ S ( F q ) and [ P ; Q ] ∈ C [P;Q]\in\mathcal{C} [ P ; Q ] ∈ C , then
0 = H ( R ) = ∑ ( 1 , ( q − 1 ) ∗ T ) + ∑ ( P + 1 + ( P , 1 ) , ( q − 1 ) ∗ Q ) . 0=\mathcal{H}(R)=\sum(1,(q-1)*T)+\sum(P^{+1}+(P,1),(q-1)*Q). 0 = H ( R ) = ∑ ( 1 , ( q − 1 ) ∗ T ) + ∑ ( P + 1 + ( P , 1 ) , ( q − 1 ) ∗ Q ) . The second term in RHS lies in H + H_+ H + , hence ( 1 , ( q − 1 ) ∗ T ) ∈ H + (1,(q-1)*T)\in H_+ ( 1 , ( q − 1 ) ∗ T ) ∈ H + .
Theorem 2.15 implies T ∈ H + T\in H_+ T ∈ H + , so we can choose R 1 ∈ C R_1\in\mathcal{C} R 1 ∈ C such that H ( R 1 ) = T \mathcal{H}(R_1)=T H ( R 1 ) = T . Replace R R R by R − ( [ ∅ ; H ( R 1 ) ] − ( 1 , Λ ( R 1 ) ) ) R-\bigl([\varnothing;\mathcal{H}(R_1)]-(1,\Lambda(R_1))\bigr) R − ( [ ∅ ; H ( R 1 )] − ( 1 , Λ ( R 1 )) ) , we may assume R ∈ ker H ∩ C R\in\ker\mathcal{H}\cap\mathcal{C} R ∈ ker H ∩ C . For such R ∈ ker H ∩ C R\in\ker\mathcal{H}\cap\mathcal{C} R ∈ ker H ∩ C , it can be written as
R = ∑ [ ( n ) ; P n ] + ∑ ( m , S m ) , P n ∈ S ( F q ) , S m ∈ C , R=\sum[(n);P_n]+\sum(m,S_m),\qquad P_n\in\mathcal{S}^{(\mathbb{F}_q)},S_m\in\mathcal{C}, R = ∑ [( n ) ; P n ] + ∑ ( m , S m ) , P n ∈ S ( F q ) , S m ∈ C , where we separate terms depending the depths of the first part.
Then apply H \mathcal{H} H to R R R , we have
0 = ∑ ( ( n + 1 ) + ( n , 1 ) , ( q − 1 ) ∗ P n ) + ∑ ( m , H ( S m ) ) . 0 = \sum\left((n+1)+(n,1),(q-1)*P_n\right)+\sum\left(m,\mathcal{H}(S_m)\right). 0 = ∑ ( ( n + 1 ) + ( n , 1 ) , ( q − 1 ) ∗ P n ) + ∑ ( m , H ( S m ) ) .
Use the similar argument in the proof of Theorem 2.15 (ii), we can show ( q − 1 ) ∗ P n ∈ H + (q-1)*P_n \in H_+ ( q − 1 ) ∗ P n ∈ H + for all n n n . Theorem 2.15 implies P n ∈ H + P_n \in H_+ P n ∈ H + , so there are some R n ∈ C R_n \in\mathcal{C} R n ∈ C such that H ( R n ) = P n \mathcal{H}(R_n)=P_n H ( R n ) = P n .
Replace R R R by R − ∑ ( [ ( n ) ; H ( R n ) ] − ( ( n + 1 ) + ( n , 1 ) , Λ ( R n ) ) ) R-\sum\left([(n);\mathcal{H}(R_n)]-\left((n+1)+(n,1),\Lambda(R_n)\right)\right) R − ∑ ( [( n ) ; H ( R n )] − ( ( n + 1 ) + ( n , 1 ) , Λ ( R n ) ) ) , then R R R has form of ∑ ( m , S m ) \sum(m,S_m) ∑ ( m , S m ) with S m ∈ C S_m\in\mathcal{C} S m ∈ C . Since the depths of their first part are at least 2, the first components of H ( m , S m ) \mathcal{H}(m,S_m) H ( m , S m ) have to be different, which implies H ( m , S m ) = 0 \mathcal{H}(m,S_m)=0 H ( m , S m ) = 0 for all m m m . Note that H ( m , S m ) = ( m , H ( S m ) ) \mathcal{H}(m,S_m)=\left(m,\mathcal{H}(S_m)\right) H ( m , S m ) = ( m , H ( S m ) ) , by the inductive assumption, we are done.
Proof of thm:BCP
We can prove Theorem 1.10 now. We first prove the final lemma in this section.
Lemma 2.18. Let R = [ s ; t ] ∈ C R=[s;t]\in\mathcal{C} R = [ s ; t ] ∈ C
L ( [ u ; H ( R ) ] − ( u + 1 + ( u , 1 ) , Λ ( R ) ) ) = B u ∗ ( P ( R ) ‾ ) . \mathcal{L}\left([u;\mathcal{H}(R)]-\left(u^{+1}+(u,1),\Lambda(R)\right)\right)=\mathcal{B}^{*}_{u}\left(\overline{\mathcal{P}(R)}\right). L ( [ u ; H ( R )] − ( u + 1 + ( u , 1 ) , Λ ( R ) ) ) = B u ∗ ( P ( R ) ) . where we set B ∅ ∗ = id \mathcal{B}^{*}_{\varnothing}=\operatorname{id} B ∅ ∗ = id for convenience.
Proof. A complicated but straightforward calculations shows
RHS = ( u , q + ( s + 1 + ( s , 1 ) , ( q − 1 ) ∗ t ) + ( q , s + 1 + ( s , 1 ) , ( q − 1 ) ∗ t ) ) − ( u + 1 + ( u , 1 ) , ( q − 1 ) ∗ t ) ( s , q + t + ( q , t ) ) . \operatorname{RHS}=\left(u,q^{+}\left(s^{+1}+(s,1),(q-1)*t\right)+\left(q,s^{+1}+(s,1),(q-1)*t\right)\right)
-\left(u^{+1}+(u,1),(q-1)*t\right)\left(s,q^{+}t+(q,t)\right). RHS = ( u , q + ( s + 1 + ( s , 1 ) , ( q − 1 ) ∗ t ) + ( q , s + 1 + ( s , 1 ) , ( q − 1 ) ∗ t ) ) − ( u + 1 + ( u , 1 ) , ( q − 1 ) ∗ t ) ( s , q + t + ( q , t ) ) . LHS needs a little attention:
LHS = ( u , q + H ( R ) + ( q , H ( R ) ) ) − ( u + 1 + ( u , 1 ) , ( q − 1 ) ∗ L ( R ) ) , \operatorname{LHS}=\left(u,q^{+}\mathcal{H}(R)+(q,\mathcal{H}(R))\right)-\left(u^{+1}+(u,1),(q-1)*\mathcal{L}(R)\right), LHS = ( u , q + H ( R ) + ( q , H ( R )) ) − ( u + 1 + ( u , 1 ) , ( q − 1 ) ∗ L ( R ) ) , where the right first term is direct, the second term needs Theorem 2.16 and the fact
L ( h , R ) = ( h , L ( R ) ) , \mathcal{L}(h,R)=\left(h,\mathcal{L}(R)\right), L ( h , R ) = ( h , L ( R ) ) , for any h ∈ I , R ∈ C h\in\mathcal{I},R\in\mathcal{C} h ∈ I , R ∈ C .
By the definition of H , L \mathcal{H},\mathcal{L} H , L , we are done.
Combine Theorem 2.12 , Theorem 2.17 and Theorem 2.18, we have L ( ker H ) ⊂ B C P \mathcal{L}(\ker\mathcal{H})\subset\mathcal{BCP} L ( ker H ) ⊂ BC P .
Given an P ∈ L w P\in\mathcal{L}_w P ∈ L w , there exists a R = ∑ a i [ h i ; s i ] R=\sum a_i[h_i;s_i] R = ∑ a i [ h i ; s i ] with h i ∈ [ q ] ∗ h_i\in[q]^* h i ∈ [ q ] ∗ , wt ( h i ) + wt ( s i ) + q = w \operatorname{wt}(h_i)+\operatorname{wt}(s_i)+q=w wt ( h i ) + wt ( s i ) + q = w such that P = L ( R ) P=\mathcal{L}(R) P = L ( R ) . Then H ( R ) = Ind P \mathcal{H}(R)=\operatorname{Ind}P H ( R ) = Ind P . If Ind P = H ( R ) ∈ B C P \operatorname{Ind}P=\mathcal{H}(R)\in\mathcal{BCP} Ind P = H ( R ) ∈ BC P , by Theorem 2.13 , we have R ∈ ker L + ker H R\in\ker\mathcal{L}+\ker\mathcal{H} R ∈ ker L + ker H , which implies P ∈ L ( ker H ) P\in\mathcal{L}(\ker\mathcal{H}) P ∈ L ( ker H ) . So we get Ind − 1 ( B C P ) ⊆ L ( ker H ) \operatorname{Ind}^{-1}(\mathcal{BCP})\subseteq\mathcal{L}(\ker\mathcal{H}) Ind − 1 ( BC P ) ⊆ L ( ker H ) . So we have
Ind − 1 ( B C P ) ⊆ L ( ker H ) ⊆ B C P . \operatorname{Ind}^{-1}(\mathcal{BCP})\subseteq\mathcal{L}(\ker\mathcal{H})\subseteq\mathcal{BCP}. Ind − 1 ( BC P ) ⊆ L ( ker H ) ⊆ BC P .
Now use Theorem 2.7 , we prove Theorem 1.10 .
Dimension of R w \mathcal{R}_w R w
We determine the dimension of R w \mathcal{R}_w R w , hence Z w \mathcal{Z}_w Z w . Our method is relatively simpler than that in [2 ] .
F q + F q D 1 \mathbb{F}_q+\mathbb{F}_qD_1 F q + F q D 1 -relation
Our starting point is the following set
U w = { P + D 1 Q ∣ P , Q ∈ S w ( F q ) , Li ( P + D 1 Q ) = 0 } . U_w=\left\{P+D_1Q\mid P,Q\in\mathcal{S}^{(\mathbb{F}_q)}_w,\ \operatorname{Li}(P+D_1Q)=0\right\}. U w = { P + D 1 Q ∣ P , Q ∈ S w ( F q ) , Li ( P + D 1 Q ) = 0 } .
Lemma 3.1. For any w ∈ Z + w\in\mathbb{Z}_+ w ∈ Z +
U w = Span F q { B h ∗ ‾ C t ( R 1 ) ∣ wt ( h ) + wt ( t ) + q = w } . U_w=\operatorname{Span}_{\mathbb{F}_q}\left\{\overline{\mathcal{B}^{*}_{h}}\mathcal{C}_t(R_1)\mid\operatorname{wt}(\mathfrak{h})+\operatorname{wt}(\mathfrak{t})+q=w\right\}. U w = Span F q { B h ∗ C t ( R 1 ) ∣ wt ( h ) + wt ( t ) + q = w } . Proof. Direct calculation shows
B h ∗ ‾ C t ( R 1 ) = ( h , q + + t + ( q , t ) ) + D 1 ( h + 1 + ( h , 1 ) , ( q − 1 ) ∗ t ) ∈ U w , \overline{\mathcal{B}^{*}_{h}}\mathcal{C}_t(R_1)=\left(\mathfrak{h},q^++t+(q,t)\right)+D_1\left(\mathfrak{h}^{+1}+(\mathfrak{h},1),(q-1)*t\right)\in U_w, B h ∗ C t ( R 1 ) = ( h , q + + t + ( q , t ) ) + D 1 ( h + 1 + ( h , 1 ) , ( q − 1 ) ∗ t ) ∈ U w , where we set q + + ∅ + ( q , ∅ ) = ( q ) q^++\varnothing+(q,\varnothing)=(q) q + + ∅ + ( q , ∅ ) = ( q ) for convenience.
For reverse inclusion, write P = ∑ u i ∈ B w ( T T ) a i u i + ∑ v j ∈ B w ( T T ) b j v j P=\sum_{u_i\in\mathcal{B}^{(\mathrm{TT})}_w}a_iu_i+\sum_{v_j\in\mathcal{B}^{(\mathrm{TT})}_w}b_jv_j P = ∑ u i ∈ B w ( TT ) a i u i + ∑ v j ∈ B w ( TT ) b j v j . Note that each u i ∉ B w ( T T ) u_i\notin\mathcal{B}^{(\mathrm{TT})}_w u i ∈ / B w ( TT ) , it can be written as ( h i , q + + t i ) (\mathfrak{h}_i,q^++t_i) ( h i , q + + t i ) for some h i , t i \mathfrak{h}_i,t_i h i , t i . Repeatedly subtracting these a i B h i ∗ ‾ C t i ( R 1 ) a_i\overline{\mathcal{B}^{*}_{\mathfrak{h}_i}}\mathcal{C}_{t_i}(R_1) a i B h i ∗ C t i ( R 1 ) , we can eliminate all terms not in B w ( T T ) \mathcal{B}^{(\mathrm{TT})}_w B w ( TT ) , with
Li ( P + D 1 Q − ∑ a i B h i ∗ ‾ C t i ( R 1 ) ) = 0. \operatorname{Li}\left(P+D_1Q-\sum a_i\overline{\mathcal{B}^{*}_{\mathfrak{h}_i}}\mathcal{C}_{t_i}(R_1)\right)=0. Li ( P + D 1 Q − ∑ a i B h i ∗ C t i ( R 1 ) ) = 0. Set P + D 1 Q − ∑ a i B h i ∗ ‾ C t i ( R 1 ) = P ′ + D 1 Q ′ P+D_1Q-\sum a_i\overline{\mathcal{B}^{*}_{\mathfrak{h}_i}}\mathcal{C}_{t_i}(R_1)=P'+D_1Q' P + D 1 Q − ∑ a i B h i ∗ C t i ( R 1 ) = P ′ + D 1 Q ′ , then P ′ ∈ Span F q B w ( T T ) P'\in\operatorname{Span}_{\mathbb{F}_q}\mathcal{B}^{(\mathrm{TT})}_w P ′ ∈ Span F q B w ( TT ) . By comparing the degree of D 1 D_1 D 1 and using Theorem 1.2 , we have P ′ = 0 P'=0 P ′ = 0 . So it suffices to show that if Q ∈ R w Q\in\mathcal{R}_w Q ∈ R w , then D 1 Q ∈ Span F q { B h ∗ ‾ C t ( R 1 ) ∣ wt ( h ) + wt ( t ) + q = w } D_1Q\in\operatorname{Span}_{\mathbb{F}_q}\{\overline{\mathcal{B}^{*}_{\mathfrak{h}}}\mathcal{C}_{t}(R_1)\mid\operatorname{wt}(\mathfrak{h})+\operatorname{wt}(\mathfrak{t})+q=w\} D 1 Q ∈ Span F q { B h ∗ C t ( R 1 ) ∣ wt ( h ) + wt ( t ) + q = w } .
Direct calculation shows that
D 1 P [ s ; t ] = B L [ ∅ ; s ] ∗ C t ( R 1 ) − C s , L [ ∅ ; t ] ( R 1 ) , D_1P[\mathfrak{s};\mathfrak{t}]=\mathcal{B}^{*}_{\mathcal{L}[\varnothing;\mathfrak{s}]}\mathcal{C}_{\mathfrak{t}}(R_1)-\mathcal{C}_{\mathfrak{s},\mathcal{L}[\varnothing;\mathfrak{t}]}(R_1), D 1 P [ s ; t ] = B L [ ∅ ; s ] ∗ C t ( R 1 ) − C s , L [ ∅ ; t ] ( R 1 ) , then Theorem 1.10 and Theorem 2.12 imply the desired result.
Corollary 3.2. For any w ∈ Z + w\in\mathbb{Z}_+ w ∈ Z + , dim F q U w = dim F q L w + dim F q R w \dim_{\mathbb{F}_q}U_w=\dim_{\mathbb{F}_q}\mathcal{L}_w+\dim_{\mathbb{F}_q}\mathcal{R}_w dim F q U w = dim F q L w + dim F q R w .
Proof. Note that L [ s ; t ] + D 1 H [ s ; t ] = B s ∗ C t ( R 1 ) \mathcal{L}[\mathfrak{s};\mathfrak{t}]+D_1\mathcal{H}[\mathfrak{s};\mathfrak{t}]=\mathcal{B}^{*}_{\mathfrak{s}}\mathcal{C}_{\mathfrak{t}}(R_1) L [ s ; t ] + D 1 H [ s ; t ] = B s ∗ C t ( R 1 ) . Consider the map π : U w → S w ( F q ) \pi:U_w\to\mathcal{S}^{(\mathbb{F}_q)}_w π : U w → S w ( F q ) defined by π ( P + D 1 Q ) = P \pi(P+D_1Q)=P π ( P + D 1 Q ) = P , then Theorem 3.1 shows Im π = L w \operatorname{Im}\pi=\mathcal{L}_w Im π = L w and ker π = D 1 R w \ker\pi=D_1\mathcal{R}_w ker π = D 1 R w .
Fixed relation
Now let V V V be R \mathcal{R} R or U U U , and use V w F i x V_w^{\mathrm{Fix}} V w Fix to denote the set consisting of P ∈ V w P\in V_w P ∈ V w such that [ P ; 0 ] ∈ B R w [P;0]\in\mathcal{B}\mathcal{R}_w [ P ; 0 ] ∈ B R w (such [ P ; 0 ] [P;0] [ P ; 0 ] is called a fixed relation).
Theorem 3.3. For all w ∈ Z + w\in\mathbb{Z}_+ w ∈ Z + ,
dim F q V w F i x = ∑ n = 1 w dim F q V w − n . \dim_{\mathbb{F}_q}V_w^{\mathrm{Fix}}=\sum_{n=1}^{w}\dim_{\mathbb{F}_q}V_{w-n}. dim F q V w Fix = n = 1 ∑ w dim F q V w − n .
Proof. For 1 ≤ n ≤ w 1 \le n \le w 1 ≤ n ≤ w , set
V w , n F i x = { P ∈ V w F i x ∣ ρ k ( P ) = 0 for all k < n } , V^{Fix}_{w,n}=\{P\in V^{Fix}_{w}\mid\rho_k(P)=0\text{ for all }k<n\}, V w , n F i x = { P ∈ V w F i x ∣ ρ k ( P ) = 0 for all k < n } ,
Given a P n ∈ V w − n P_n\in V_{w-n} P n ∈ V w − n , using Theorem 1.10 for V = R V=\mathcal{R} V = R and Theorem 3.1 for V = U V=U V = U , there exists a binary relation [ A n ; B n ] [A_n;B_n] [ A n ; B n ] such that P n = A n + B n P_n=A_n+B_n P n = A n + B n (Note that such binary relation is not unique, so we should fix it for a basis to ensure well-defined). Then
B ( n ) [ A n ; B n ] = [ ( n , P n ) + n + B n ; 0 ] , \mathcal{B}_{(n)}[A_n;B_n]=\left[(n,P_n)+{}^{n+}B_n;0\right], B ( n ) [ A n ; B n ] = [ ( n , P n ) + n + B n ; 0 ] ,
hence ( n , P n ) + n + B n ∈ V w , n F i x (n,P_n)+{}^{n+}B_n\in V^{Fix}_{w,n} ( n , P n ) + n + B n ∈ V w , n F i x . This induces an injection τ w − n : V w − n → V w , n F i x / V w , n + 1 F i x \tau_{w-n}:V_{w-n}\to V^{Fix}_{w,n}/V^{Fix}_{w,n+1} τ w − n : V w − n → V w , n F i x / V w , n + 1 F i x .
We show that τ \tau τ has an inverse: For a P = ∑ k = n w ( k , P k ) ∈ V w , n F i x P=\sum_{k=n}^{w}(k,P_k)\in V^{Fix}_{w,n} P = ∑ k = n w ( k , P k ) ∈ V w , n F i x , P n ∈ V w − n P_n\in V_{w-n} P n ∈ V w − n . By definition, we have
∑ k = n w Si d ( k , P k ) = ∑ k = n w l d − k Si < d ( P k ) = 0. \sum_{k=n}^{w}\operatorname{Si}_d(k,P_k)=\sum_{k=n}^{w}l_d^{-k}\operatorname{Si}_{<d}(P_k)=0. k = n ∑ w Si d ( k , P k ) = k = n ∑ w l d − k Si < d ( P k ) = 0.
Multiplied by l d n l_d^n l d n , we have
Si < d ( P n ) + ∑ k = n + 1 w l d n − k Si < d ( P k ) = 0. \operatorname{Si}_{<d}(P_n)+\sum_{k=n+1}^{w}l_d^{n-k}\operatorname{Si}_{<d}(P_k)=0. Si < d ( P n ) + k = n + 1 ∑ w l d n − k Si < d ( P k ) = 0.
Let d → ∞ d\to\infty d → ∞ , note that l d − 1 → 0 l_d^{-1}\to0 l d − 1 → 0 , we have Li ( P n ) = 0 \operatorname{Li}(P_n)=0 Li ( P n ) = 0 , i.e. P n ∈ V w − n P_n\in V_{w-n} P n ∈ V w − n . Then P ↦ P n P\mapsto P_n P ↦ P n define a linear map from V w , n F i x → V w − n V^{Fix}_{w,n}\to V_{w-n} V w , n F i x → V w − n . It factors through V w , n F i x / V w , n + 1 F i x V^{Fix}_{w,n}/V^{Fix}_{w,n+1} V w , n F i x / V w , n + 1 F i x and is actually the inverse of τ w − n \tau_{w-n} τ w − n .
Now we know τ w − n \tau_{w-n} τ w − n is an isomorphism. Then we are done by recursion.
Proof of thm:dimension
Lemma 3.4. For all w ≥ q w\ge q w ≥ q ,
S w − q ( F q ) / R w − q F i x ≅ U w / U w F i x \mathcal{S}^{(\mathbb{F}_q)}_{w-q}/\mathcal{R}^{Fix}_{w-q}\cong U_w/U^{Fix}_w S w − q ( F q ) / R w − q F i x ≅ U w / U w F i x
Proof. Define the map S w − q ( F q ) → U w / U w F i x : P ↦ C P ( R 1 ) ‾ + U w F i x \mathcal{S}^{(\mathbb{F}_q)}_{w-q}\to U_w/U^{Fix}_w:P\mapsto\overline{C_P(R_1)}+U^{Fix}_w S w − q ( F q ) → U w / U w F i x : P ↦ C P ( R 1 ) + U w F i x , Theorem 3.1 and the proof of Theorem 3.3 imply it is surjective (In fact, the proof of Theorem 3.3 shows that U w F i x U^{Fix}_w U w F i x is generated by these B h ∗ C t ( R 1 ) B_h^*C_t(R_1) B h ∗ C t ( R 1 ) with h ≠ ∅ h\ne\varnothing h = ∅ ). We just need to show the kernel of this map is R w − q F i x \mathcal{R}^{Fix}_{w-q} R w − q F i x .
If a P ∈ S w − q ( F q ) P\in\mathcal{S}^{(\mathbb{F}_q)}_{w-q} P ∈ S w − q ( F q ) satisfies C P ( R 1 ) ‾ ∈ U w F i x \overline{C_P(R_1)}\in U^{Fix}_w C P ( R 1 ) ∈ U w F i x , then we have
Si d ( q ) Si < d + 1 ( P ) + D 1 Si d ( 1 , ( q − 1 ) ∗ P ) = 0. \operatorname{Si}_d(q)\operatorname{Si}_{<d+1}(P)+D_1\operatorname{Si}_d\left(1,(q-1)*P\right)=0. Si d ( q ) Si < d + 1 ( P ) + D 1 Si d ( 1 , ( q − 1 ) ∗ P ) = 0.
On the other hand, C P ( R 1 ) C_P(R_1) C P ( R 1 ) is a binary relation, we have
Si d ( q ) Si < d + 1 ( P ) + D 1 Si d + 1 ( 1 , ( q − 1 ) ∗ P ) = 0. \operatorname{Si}_d(q)\operatorname{Si}_{<d+1}(P)+D_1\operatorname{Si}_{d+1}\left(1,(q-1)*P\right)=0. Si d ( q ) Si < d + 1 ( P ) + D 1 Si d + 1 ( 1 , ( q − 1 ) ∗ P ) = 0.
So we have Si d ( 1 , ( q − 1 ) ∗ P ) = Si d + 1 ( 1 , ( q − 1 ) ∗ P ) \operatorname{Si}_d\left(1,(q-1)*P\right)=\operatorname{Si}_{d+1}\left(1,(q-1)*P\right) Si d ( 1 , ( q − 1 ) ∗ P ) = Si d + 1 ( 1 , ( q − 1 ) ∗ P ) for all d d d . But Si d ( 1 , ( q − 1 ) ∗ P ) = 0 \operatorname{Si}_d\left(1,(q-1)*P\right)=0 Si d ( 1 , ( q − 1 ) ∗ P ) = 0 for d d d small enough, so we have
Si d ( 1 , ( q − 1 ) ∗ P ) = Si d ( 1 ) Si < d ( q − 1 ) Si < d ( P ) = 0 \operatorname{Si}_d\left(1,(q-1)*P\right)=\operatorname{Si}_d(1)\operatorname{Si}_{<d}(q-1)\operatorname{Si}_{<d}(P)=0 Si d ( 1 , ( q − 1 ) ∗ P ) = Si d ( 1 ) Si < d ( q − 1 ) Si < d ( P ) = 0
for all d d d . Hence P ∈ R w − q F i x P\in\mathcal{R}^{Fix}_{w-q} P ∈ R w − q F i x .
For the converse, it is easy to see if P ∈ R w − q F i x P\in\mathcal{R}^{Fix}_{w-q} P ∈ R w − q F i x , then C P ( R 1 ) ‾ ∈ U w F i x \overline{C_P(R_1)}\in U^{Fix}_w C P ( R 1 ) ∈ U w F i x . Above lemma implies
dim F q R w − q F i x = dim F q S w − q ( F q ) − dim F q U w + dim F q U w F i x . \dim_{\mathbb{F}_q}\mathcal{R}^{\mathrm{Fix}}_{w-q}=\dim_{\mathbb{F}_q}\mathcal{S}^{(\mathbb{F}_q)}_{w-q}-\dim_{\mathbb{F}_q}U_w+\dim_{\mathbb{F}_q}U_w^{\mathrm{Fix}}. dim F q R w − q Fix = dim F q S w − q ( F q ) − dim F q U w + dim F q U w Fix .
By Theorem 3.2, Theorem 3.3 and Theorem 2.4, recall we use r w r_w r w to denote dim F q R w \dim_{\mathbb{F}_q}\mathcal{R}_w dim F q R w , we have
r w = ∑ n = 1 q r w − n + ∣ I w − q ∣ − ∣ I w − B w ( T T ) ∣ + ∑ n = 1 w ∣ I w − n − B w − n ( T T ) ∣ . r_w=\sum_{n=1}^{q}r_{w-n}+\lvert\mathcal{I}_{w-q}\rvert-\lvert\mathcal{I}_w-\mathcal{B}^{(\mathrm{TT})}_w\rvert+\sum_{n=1}^{w}\lvert\mathcal{I}_{w-n}-\mathcal{B}^{(\mathrm{TT})}_{w-n}\rvert. r w = n = 1 ∑ q r w − n + ∣ I w − q ∣ − ∣ I w − B w ( TT ) ∣ + n = 1 ∑ w ∣ I w − n − B w − n ( TT ) ∣ .
Multiplied by x w x^w x w , summing over all w ≥ 1 w\geq1 w ≥ 1 , use the following generating functions
∑ w ≥ 0 ∣ I w ∣ x w = 1 + ∑ w ≥ 1 2 w − 1 x w = 1 − x 1 − 2 x , \sum_{w\geq0}\lvert\mathcal{I}_w\rvert x^w=1+\sum_{w\geq1}2^{w-1}x^w=\frac{1-x}{1-2x}, w ≥ 0 ∑ ∣ I w ∣ x w = 1 + w ≥ 1 ∑ 2 w − 1 x w = 1 − 2 x 1 − x ,
∑ w ≥ 0 ∣ B w ( T T ) ∣ x w = 1 + ∑ w = 1 ∞ d w ( K ) x w = 1 + x ( 1 − x q − 1 ) 1 − 2 x + x q + 1 , \sum_{w\geq0}\lvert\mathcal{B}^{(\mathrm{TT})}_w\rvert x^w=1+\sum_{w=1}^{\infty}d_w^{(K)}x^w=1+\frac{x(1-x^{q-1})}{1-2x+x^{q+1}}, w ≥ 0 ∑ ∣ B w ( TT ) ∣ x w = 1 + w = 1 ∑ ∞ d w ( K ) x w = 1 + 1 − 2 x + x q + 1 x ( 1 − x q − 1 ) ,
and the following formulation
∑ w ≥ 0 ( ∑ k = 0 w a k ) x w = 1 1 − x ∑ w ≥ 0 a w x w . \sum_{w\geq0}\left(\sum_{k=0}^{w}a_k\right)x^w=\frac{1}{1-x}\sum_{w\geq0}a_wx^w. w ≥ 0 ∑ ( k = 0 ∑ w a k ) x w = 1 − x 1 w ≥ 0 ∑ a w x w .
Complicated but direct calculation implies Theorem 1.12
Another proof of completeness
In this section, we give another proof of Theorem 1.10 , which does not depend on the reduction of Theorem 2.13 (Hence is relatively independent of [2 ] ). The main ideas are similar to the ones in [4 ] . We will admit some results in Section 2.
Main idea of proof
For a P ∈ S w ( F q ) P\in\mathcal{S}_w^{(\mathbb{F}_q)} P ∈ S w ( F q ) , we use min ≺ P \min_{\prec}P min ≺ P to denote the smallest tuple in P P P in the (depth,lex)-order.
Lemma 4.1. For s , t , h , u ∈ I s,t,h,u\in\mathcal{I} s , t , h , u ∈ I with s ≠ ∅ s\neq\varnothing s = ∅ ,
(i) min ≺ B h ∗ P ( s ) ‾ = ( h , q + s + 1 , q − 1 ) \min_{\prec}\overline{\mathcal{B}_h^*P(s)}=(h,q+s+1,q-1) min ≺ B h ∗ P ( s ) = ( h , q + s + 1 , q − 1 ) . We call B h ∗ P ( s ) ‾ \overline{\mathcal{B}_h^*P(s)} B h ∗ P ( s ) the relation of TYPE I, and ( h , q + s + 1 , q − 1 ) (h,q+s+1,q-1) ( h , q + s + 1 , q − 1 ) the tuple of type i i i ;
(ii) For t ≠ ∅ t\neq\varnothing t = ∅ , min ≺ B h ∗ P [ s ; t ] ‾ = ( h , q + s + 1 , t + ( q − 1 ) ) \min_{\prec}\overline{\mathcal{B}_h^*P[s;t]}=(h,q+s+1,t^{+(q-1)}) min ≺ B h ∗ P [ s ; t ] = ( h , q + s + 1 , t + ( q − 1 ) ) . We call B h ∗ P [ s ; t ] ‾ \overline{\mathcal{B}_h^*P[s;t]} B h ∗ P [ s ; t ] the relation of TYPE II, and ( h , q + s + 1 , t + ( q − 1 ) ) (h,q+s+1,t^{+(q-1)}) ( h , q + s + 1 , t + ( q − 1 ) ) the tuple of type i i ii ii ;
(iii) For u ≠ ∅ u\neq\varnothing u = ∅ , min ≺ B h ∗ ( P [ s ; ( u + 1 , t ) ] − P [ ( s + 1 , u ) ; t ] ) ‾ = ( h , q + s + 1 , u + q , t ) \min_{\prec}\overline{\mathcal{B}_h^*\left(P[s;(u^{+1},t)]-P[(s^{+1},u);t]\right)}=(h,q+s+1,u^{+q},t) min ≺ B h ∗ ( P [ s ; ( u + 1 , t )] − P [( s + 1 , u ) ; t ] ) = ( h , q + s + 1 , u + q , t ) . We call B h ∗ ( P [ s ; ( u + 1 , t ) ] − P [ ( s + 1 , u ) ; t ] ) ‾ \overline{\mathcal{B}_h^*\left(P[s;(u^{+1},t)]-P[(s^{+1},u);t]\right)} B h ∗ ( P [ s ; ( u + 1 , t )] − P [( s + 1 , u ) ; t ] ) the relation of TYPE III, and ( h , q + s + 1 , u + q , t ) (h,q+s+1,u^{+q},t) ( h , q + s + 1 , u + q , t ) the tuple of type i i i iii iii .
Proof. Direct calculation implies desired result.
By using Theorem 2.12 , it suffices to show there is no P ∈ R w P \in\mathcal{R}_{w} P ∈ R w such that min ≺ P \min_{\prec} P min ≺ P is not of type i, ii or iii (We call such P P P illegal). In fact, if we prove it, then for any P ∈ R w P \in\mathcal{R}_{w} P ∈ R w , we can repeatedly eliminate the minimal term of P P P by subtracting some relation in LHS of Theorem 4.1 . This procedure have to become 0 and stop after finitely many steps, then we prove that P P P is a linear combination of BCP relations.
Assume there exists an illegal P ∈ R w P \in\mathcal{R}_{w} P ∈ R w . We may choose the P P P satisfying min ≺ P \min_{\prec} P min ≺ P is maximal among all illegal P P P , then Ind P \operatorname{Ind} P Ind P must be 0 or legal, because min ≺ P ≺ min ≺ Ind P \min_{\prec} P \prec\min_{\prec} \operatorname{Ind} P min ≺ P ≺ min ≺ Ind P if Ind P ≠ 0 \operatorname{Ind} P \ne0 Ind P = 0 . Now we show that min ≺ P \min_{\prec} P min ≺ P is not maximal to derive a contradiction. We will show that Ind P \operatorname{Ind} P Ind P can not be eliminated by subtracting the relations of TYPE I, II or III, then there will remain an illegal relation with minimal tuple greater than min ≺ P \min_{\prec} P min ≺ P .
Choose tuples
By Theorem 2.4, and at most multiplied by a scale, we may write P = L [ s ; t ] + ∑ a i L [ s i ; t i ] P = \mathcal{L}[\mathfrak{s};\mathfrak{t}] + \sum a_i\mathcal{L}[\mathfrak{s}_i;\mathfrak{t}_i] P = L [ s ; t ] + ∑ a i L [ s i ; t i ] with a i ∈ F q a_i \in\mathbb{F}_q a i ∈ F q , s , s i ∈ [ q ] ∙ \mathfrak{s},\mathfrak{s}_i \in[q]^{\bullet} s , s i ∈ [ q ] ∙ , and ( s , q + t ) = min ≺ P (\mathfrak{s},q^{+\mathfrak{t}}) = \min_{\prec} P ( s , q + t ) = min ≺ P (Let n ∅ + = ( n ) n_{\emptyset}^{+} = (n) n ∅ + = ( n ) here). Then Ind P = H [ s ; t ] + ∑ a i H [ s i ; t i ] \operatorname{Ind} P = \mathcal{H}[\mathfrak{s};\mathfrak{t}] + \sum a_i\mathcal{H}[\mathfrak{s}_i;\mathfrak{t}_i] Ind P = H [ s ; t ] + ∑ a i H [ s i ; t i ] . Note that
min ≺ H [ s ; t ] = { ( s + 1 , t + ( q − 1 ) ) , s ≠ ∅ ; ( 1 , t + ( q − 1 ) ) , s = ∅ . \min_{\prec}\mathcal{H}[\mathfrak{s};\mathfrak{t}] =
\begin{cases}
(\mathfrak{s}^{+1},\mathfrak{t}^{+(q-1)}), & \mathfrak{s} \ne\emptyset;\\
(1,\mathfrak{t}^{+(q-1)}), & \mathfrak{s} = \emptyset.
\end{cases} ≺ min H [ s ; t ] = { ( s + 1 , t + ( q − 1 ) ) , ( 1 , t + ( q − 1 ) ) , s = ∅ ; s = ∅.
Now for the case s ≠ ∅ \mathfrak{s} \ne\emptyset s = ∅ , set dep ( s , q + t ) = d \operatorname{dep}(\mathfrak{s},q^{+\mathfrak{t}}) = d dep ( s , q + t ) = d , we choose the tuples in Ind P \operatorname{Ind} P Ind P of the form ( s + 1 , u ) (\mathfrak{s}^{+1},\mathfrak{u}) ( s + 1 , u ) with dep ( s + 1 , u ) = d \operatorname{dep}(\mathfrak{s}^{+1},\mathfrak{u}) = d dep ( s + 1 , u ) = d for some u \mathfrak{u} u .
In H [ s ; t ] \mathcal{H}[\mathfrak{s};\mathfrak{t}] H [ s ; t ] , write t = ( t 1 , ⋯ , t l ) \mathfrak{t} = (t_1,\cdots,t_l) t = ( t 1 , ⋯ , t l ) , such tuples are of form ( s + 1 , t 1 , ⋯ , t j + q − 1 , ⋯ , t l ) (\mathfrak{s}^{+1},t_1,\cdots,t_j+q-1,\cdots,t_l) ( s + 1 , t 1 , ⋯ , t j + q − 1 , ⋯ , t l ) for some j j j .
For other H [ s i ; t i ] \mathcal{H}[\mathfrak{s}_i;\mathfrak{t}_i] H [ s i ; t i ] , existence of such tuples implies dep ( s i , q + t i ) = d \operatorname{dep}(\mathfrak{s}_i,q^{+\mathfrak{t}_i}) = d dep ( s i , q + t i ) = d . In fact, if dep ( s i ) + dep ( t i ) > d \operatorname{dep}(\mathfrak{s}_i) + \operatorname{dep}(\mathfrak{t}_i) > d dep ( s i ) + dep ( t i ) > d , then each tuple of H [ s i ; t i ] \mathcal{H}[\mathfrak{s}_i;\mathfrak{t}_i] H [ s i ; t i ] has depth greater than d d d ; ( s , q + t ) ≺ ( s i , q + t i ) (\mathfrak{s},q^{+\mathfrak{t}}) \prec(\mathfrak{s}_i,q^{+\mathfrak{t}_i}) ( s , q + t ) ≺ ( s i , q + t i ) ensures dep ( s i ) + max { 1 + dep ( t i ) } ≥ d \operatorname{dep}(\mathfrak{s}_i) + \max\{1+\operatorname{dep}(\mathfrak{t}_i)\} \ge d dep ( s i ) + max { 1 + dep ( t i )} ≥ d .
Moreover, we have s i = s \mathfrak{s}_i = \mathfrak{s} s i = s or s i = ( s + 1 , u ) \mathfrak{s}_i = (\mathfrak{s}^{+1},\mathfrak{u}) s i = ( s + 1 , u ) for some u \mathfrak{u} u : If dep ( s i ) < dep ( s ) \operatorname{dep}(\mathfrak{s}_i) < \operatorname{dep}(\mathfrak{s}) dep ( s i ) < dep ( s ) , the tuples of H [ s i ; t i ] \mathcal{H}[\mathfrak{s}_i;\mathfrak{t}_i] H [ s i ; t i ] with depth d d d have the forms of ( s i + 1 , t i 1 , ⋯ , t j i + q − 1 , ⋯ , t m i i ) (\mathfrak{s}_i^{+1},t_i^1,\cdots,t_j^i+q-1,\cdots,t_{m_i}^i) ( s i + 1 , t i 1 , ⋯ , t j i + q − 1 , ⋯ , t m i i ) , where t i = ( t 1 i , ⋯ , t m i i ) \mathfrak{t}_i = (t_1^i,\cdots,t_{m_i}^i) t i = ( t 1 i , ⋯ , t m i i ) . If these tuples have the forms of ( s + 1 , u ) (\mathfrak{s}^{+1},\mathfrak{u}) ( s + 1 , u ) , let s i = ( s 1 i , ⋯ , s dep ( s i ) i ) \mathfrak{s}_i = (s_1^i,\cdots,s_{\operatorname{dep}(\mathfrak{s}_i)}^i) s i = ( s 1 i , ⋯ , s dep ( s i ) i ) , s = ( s 1 , ⋯ , s dep ( s ) ) \mathfrak{s} = (s_1,\cdots,s_{\operatorname{dep}(\mathfrak{s})}) s = ( s 1 , ⋯ , s dep ( s ) ) , then we have s k i = s k s_k^i = s_k s k i = s k for k < dep ( s i ) k < \operatorname{dep}(\mathfrak{s}_i) k < dep ( s i ) and s dep ( s i ) i + 1 = s dep ( s i ) s_{\operatorname{dep}(\mathfrak{s}_i)}^i + 1 = s_{\operatorname{dep}(\mathfrak{s}_i)} s dep ( s i ) i + 1 = s dep ( s i ) by comparing components, which contradicts ( s , q + t ) ≺ ( s i , q + t i ) (\mathfrak{s},q^{+\mathfrak{t}}) \prec(\mathfrak{s}_i,q^{+\mathfrak{t}_i}) ( s , q + t ) ≺ ( s i , q + t i ) . Now we have dep ( s i ) ≥ dep ( s ) \operatorname{dep}(\mathfrak{s}_i) \ge\operatorname{dep}(\mathfrak{s}) dep ( s i ) ≥ dep ( s ) , comparing components derives s = s i \mathfrak{s} = \mathfrak{s}_i s = s i or s i = ( s + 1 , u ) \mathfrak{s}_i = (\mathfrak{s}^{+1},\mathfrak{u}) s i = ( s + 1 , u ) .
For the case s = ∅ \mathfrak{s} = \emptyset s = ∅ , set dep ( q + t ) = d \operatorname{dep}(q^{+\mathfrak{t}}) = d dep ( q + t ) = d , we choose the tuples of form ( 1 , u ) (1,\mathfrak{u}) ( 1 , u ) with dep ( 1 , u ) = d + 1 \operatorname{dep}(1,\mathfrak{u}) = d+1 dep ( 1 , u ) = d + 1 . In H [ s ; t ] \mathcal{H}[\mathfrak{s};\mathfrak{t}] H [ s ; t ] , such tuples are of forms ( 1 , t 1 , ⋯ , t j + q − 1 , ⋯ , t l ) (1,t_1,\cdots,t_j+q-1,\cdots,t_l) ( 1 , t 1 , ⋯ , t j + q − 1 , ⋯ , t l ) for some j j j with t = ( t 1 , ⋯ , t l ) \mathfrak{t} = (t_1,\cdots,t_l) t = ( t 1 , ⋯ , t l ) . For other H [ s i ; t i ] \mathcal{H}[\mathfrak{s}_i;\mathfrak{t}_i] H [ s i ; t i ] , the same discussion as the above implies that if H [ s i ; t i ] \mathcal{H}[\mathfrak{s}_i;\mathfrak{t}_i] H [ s i ; t i ] has such tuples, then s i = ∅ \mathfrak{s}_i = \emptyset s i = ∅ , dep ( t i ) = d \operatorname{dep}(\mathfrak{t}_i) = d dep ( t i ) = d ; or the first component of s i \mathfrak{s}_i s i is 1, dep ( s i ) ≥ 2 \operatorname{dep}(\mathfrak{s}_i) \ge2 dep ( s i ) ≥ 2 , and dep ( s i , q + t i ) = d + 1 \operatorname{dep}(\mathfrak{s}_i,q^{+\mathfrak{t}_i}) = d+1 dep ( s i , q + t i ) = d + 1 .
Tuples can not be eliminated
Now we show we can not eliminate the tuples we choose in § 4.2 to finish our proof. There are two cases:
I. t = ( 1 , 1 , ⋯ , 1 , t ) \mathfrak{t} = (1,1,\cdots,1,t) t = ( 1 , 1 , ⋯ , 1 , t ) or ∅ \emptyset ∅ , i.e. all components of t \mathfrak{t} t except the last one are 1 or t \mathfrak{t} t is empty set.
II. t ≠ ∅ \mathfrak{t} \ne\emptyset t = ∅ and has components not equal to 1 before the last one.
Case I: For t ≠ ∅ \mathbf{t} \ne\emptyset t = ∅ , we consider the tuple ( s + 1 , t + ( q − 1 ) ) = ( s + 1 , 1 , 1 , … , t + q − 1 ) (\mathbf{s}^{+1},\mathbf{t}^{+(q-1)})=(\mathbf{s}^{+1},1,1,\ldots,t+q-1) ( s + 1 , t + ( q − 1 ) ) = ( s + 1 , 1 , 1 , … , t + q − 1 ) . It is the minimal tuple of H [ s ; t ] \mathcal{H}[s;t] H [ s ; t ] . Similar argument as in the previous subsection implies that other H [ s i ; t i ] \mathcal{H}[s_i;t_i] H [ s i ; t i ] can not generate this tuple. So comparing components implies ( s + 1 , t + ( q − 1 ) ) = min ≺ Ind P (\mathbf{s}^{+1},\mathbf{t}^{+(q-1)})=\min_{\prec}\operatorname{Ind} P ( s + 1 , t + ( q − 1 ) ) = min ≺ Ind P . However, it is easy to see ( s + 1 , t + ( q − 1 ) ) (\mathbf{s}^{+1},\mathbf{t}^{+(q-1)}) ( s + 1 , t + ( q − 1 ) ) is not of type i, ii or iii. We are done.
For t = ∅ \mathbf{t}=\emptyset t = ∅ , the same argument works.
Case II: This case will be more complicated.
First, fix a tuple ( v 1 , … , v n , b ) (v_1,\ldots,v_n,b) ( v 1 , … , v n , b ) with v i ≤ q v_i\le q v i ≤ q for all i i i and b ≤ q − 1 b\le q-1 b ≤ q − 1 . For tuple ( x 1 , … , x n + 1 ) (x_1,\ldots,x_{n+1}) ( x 1 , … , x n + 1 ) with x n + 1 ≡ b ( m o d q − 1 ) x_{n+1}\equiv b\pmod{q-1} x n + 1 ≡ b ( mod q − 1 ) , we define λ ( x 1 , … , x n + 1 ) ∈ F q \lambda(x_1,\ldots,x_{n+1})\in\mathbb{F}_q λ ( x 1 , … , x n + 1 ) ∈ F q by induction: if 1 ≤ x i ≤ q 1\le x_i\le q 1 ≤ x i ≤ q for all 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n and x n + 1 = b x_{n+1}=b x n + 1 = b , then let
λ ( x 1 , … , x n + 1 ) = { 1 , ( x 1 , … , x n + 1 ) = ( v 1 , … , v n , b ) ; 0 , ( x 1 , … , x n + 1 ) ≠ ( v 1 , … , v n , b ) . \lambda(x_1,\ldots,x_{n+1})=
\begin{cases}
1, & (x_1,\ldots,x_{n+1})=(v_1,\ldots,v_n,b);\\
0, & (x_1,\ldots,x_{n+1})\ne(v_1,\ldots,v_n,b).
\end{cases} λ ( x 1 , … , x n + 1 ) = { 1 , 0 , ( x 1 , … , x n + 1 ) = ( v 1 , … , v n , b ) ; ( x 1 , … , x n + 1 ) = ( v 1 , … , v n , b ) .
We introduce a relation ← \leftarrow ← . For x = ( x 1 , … , x n + 1 ) \mathbf{x}=(x_1,\ldots,x_{n+1}) x = ( x 1 , … , x n + 1 ) and y = ( y 1 , … , y n + 1 ) \mathbf{y}=(y_1,\ldots,y_{n+1}) y = ( y 1 , … , y n + 1 ) , let r r r be the greatest number such that x r > q x_r>q x r > q if r ≤ n r\le n r ≤ n , or x r > b x_r>b x r > b if r = n + 1 r=n+1 r = n + 1 . We say y ← x \mathbf{y}\leftarrow\mathbf{x} y ← x if there exists an k < r k<r k < r such that y = ( x 1 , … , x k + ( q − 1 ) , … , x r − ( q − 1 ) , … , x n + 1 ) \mathbf{y}=(x_1,\ldots,x_k+(q-1),\ldots,x_r-(q-1),\ldots,x_{n+1}) y = ( x 1 , … , x k + ( q − 1 ) , … , x r − ( q − 1 ) , … , x n + 1 ) . For tuples outside the preceding case, define
λ ( x ) = { 0 , if there is no y such that y < x ; − ∑ y ← x λ ( y ) , otherwise . \lambda(\mathbf{x})=
\begin{cases}
0, & \text{if there is no }\mathbf{y}\text{ such that }\mathbf{y}<\mathbf{x};\\
-\sum_{\mathbf{y}\leftarrow\mathbf{x}}\lambda(\mathbf{y}), & \text{otherwise}.
\end{cases} λ ( x ) = { 0 , − ∑ y ← x λ ( y ) , if there is no y such that y < x ; otherwise .
Now we set x ( j ) = ( x 1 , … , x j + q − 1 , … , x n + 1 ) \mathbf{x}^{(j)}=(x_1,\ldots,x_j+q-1,\ldots,x_{n+1}) x ( j ) = ( x 1 , … , x j + q − 1 , … , x n + 1 ) . Then by definition, we have
∑ j = 1 n + 1 λ ( x ( j ) ) = 0. \sum_{j=1}^{n+1}\lambda(\mathbf{x}^{(j)})=0. j = 1 ∑ n + 1 λ ( x ( j ) ) = 0.
For any i ≤ n i\le n i ≤ n such that x i > 1 x_i>1 x i > 1 , we have
∑ j = 1 i λ ( x ( j ) ) = 0. \sum_{j=1}^{i}\lambda(\mathbf{x}^{(j)})=0. j = 1 ∑ i λ ( x ( j ) ) = 0.
In fact, if there is no r > i r>i r > i such that x r > q x_r>q x r > q if r ≤ n r\le n r ≤ n , or x r > b x_r>b x r > b if r = n + 1 r=n+1 r = n + 1 , then definition implies the equality. If there exists such r r r , choose the greatest one, let η k = ( x 1 , … , x k + ( q − 1 ) , … , x r − ( q − 1 ) , … , x n + 1 ) \boldsymbol{\eta}_k=(x_1,\ldots,x_k+(q-1),\ldots,x_r-(q-1),\ldots,x_{n+1}) η k = ( x 1 , … , x k + ( q − 1 ) , … , x r − ( q − 1 ) , … , x n + 1 ) . Then
λ ( x ( j ) ) + ∑ k = 1 r − 1 λ ( η k ( j ) ) = 0 , \lambda(\mathbf{x}^{(j)})+\sum_{k=1}^{r-1}\lambda(\boldsymbol{\eta}_k^{(j)})=0, λ ( x ( j ) ) + k = 1 ∑ r − 1 λ ( η k ( j ) ) = 0 ,
hence
∑ j = 1 i λ ( x ( j ) ) = − ∑ k = 1 r − 1 ∑ j = 1 i λ ( η k ( j ) ) . \sum_{j=1}^{i}\lambda(\mathbf{x}^{(j)})=-\sum_{k=1}^{r-1}\sum_{j=1}^{i}\lambda(\boldsymbol{\eta}_k^{(j)}). j = 1 ∑ i λ ( x ( j ) ) = − k = 1 ∑ r − 1 j = 1 ∑ i λ ( η k ( j ) ) .
By induction on ∑ j = 1 n + 1 j x j \sum_{j=1}^{n+1}jx_j ∑ j = 1 n + 1 j x j , we can prove it.
Combine these two equalities, we have
∑ j = i + 1 n + 1 λ ( x ( j ) ) = 0. \sum_{j=i+1}^{n+1}\lambda(\mathbf{x}^{(j)})=0. j = i + 1 ∑ n + 1 λ ( x ( j ) ) = 0.
We now begin our discussion: In P = L [ s ; t ] + ∑ a i L [ s i ; t i ] P=\mathcal{L}[\mathfrak{s};\mathfrak{t}]+\sum a_i\mathcal{L}[\mathfrak{s}_i;\mathfrak{t}_i] P = L [ s ; t ] + ∑ a i L [ s i ; t i ] , we may assume we can not eliminate any tuples in P P P by subtracting relations of TYPE I, II and III (Because subtracting them does not change the minimal tuple of P P P ).
For t = ( t 1 , … , t l ) \mathfrak{t}=(t_1,\ldots,t_l) t = ( t 1 , … , t l ) , choose r r r such that t j = 1 t_j=1 t j = 1 for all j ≤ r j\le r j ≤ r , and t r + 1 ≥ 2 t_{r+1}\ge2 t r + 1 ≥ 2 (possibly r = 0 r=0 r = 0 ). By assumption, 0 ≤ r ≤ l − 2 0\le r\le l-2 0 ≤ r ≤ l − 2 . Now we consider the L [ s i ; t i ] \mathcal{L}[\mathfrak{s}_i;\mathfrak{t}_i] L [ s i ; t i ] (including L [ s ; t ] \mathcal{L}[\mathfrak{s};\mathfrak{t}] L [ s ; t ] ) satisfying s i = s \mathfrak{s}_i=\mathfrak{s} s i = s , t i = ( t 1 i , … , t l i ) \mathfrak{t}_i=(t^i_1,\ldots,t^i_l) t i = ( t 1 i , … , t l i ) with t j i = 1 t^i_j=1 t j i = 1 for all j ≤ r j\le r j ≤ r and t r + 1 i ≥ 2 t^i_{r+1}\ge2 t r + 1 i ≥ 2 . We choose the one whose t r + 1 i t^i_{r+1} t r + 1 i is maximal among theirs, denote it by L [ s ; t ′ ] \mathcal{L}[\mathfrak{s};\mathfrak{t}'] L [ s ; t ′ ] . We write t ′ = ( 1 , … , 1 ⏟ r 1 ′ s , m , v 1 , … , v n , b ) \mathfrak{t}'=(\underbrace{1,\ldots,1}_{r\ 1's},m,v_1,\ldots,v_n,b) t ′ = ( r 1 ′ s 1 , … , 1 , m , v 1 , … , v n , b ) , and set u = ( 1 , … , 1 ⏟ r 1 ′ s , m − 1 ) \mathfrak{u}=(\underbrace{1,\ldots,1}_{r\ 1's},m-1) u = ( r 1 ′ s 1 , … , 1 , m − 1 ) . Then min ≺ L [ s ; t ′ ] = ( s , q + u + 1 , v 1 , … , v n , b ) \min_{\prec}\mathcal{L}[\mathfrak{s};\mathfrak{t}']=(\mathfrak{s},q+\mathfrak{u}+1,v_1,\ldots,v_n,b) min ≺ L [ s ; t ′ ] = ( s , q + u + 1 , v 1 , … , v n , b ) .
By our assumption that tuples of P P P can not be eliminated. ( s , q + u + 1 , v 1 , … , v n , b ) (\mathfrak{s},q+\mathfrak{u}+1,v_1,\ldots,v_n,b) ( s , q + u + 1 , v 1 , … , v n , b ) has no form of type i, ii or iii. By comparing the components, we have v i ≤ q v_i\le q v i ≤ q for 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n , b ≤ q − 1 b\le q-1 b ≤ q − 1 ; and if b = q − 1 b=q-1 b = q − 1 , then n ≥ 1 n\ge1 n ≥ 1 and v n = 1 v_n=1 v n = 1 . This argument also works for the previous L [ s i ; t i ] \mathcal{L}[\mathfrak{s}_i;\mathfrak{t}_i] L [ s i ; t i ] we consider.
We consider all the tuples in Ind P \operatorname{Ind}P Ind P of forms
( s + 1 , 1 , … , 1 ⏟ r 1 ′ s , m + q − 1 , x 1 , … , x n + 1 ) with x n + 1 ≡ b ( m o d q − 1 ) , (\mathfrak{s}^{+1},\underbrace{1,\ldots,1}_{r\ 1's},m+q-1,x_1,\ldots,x_{n+1})\quad\text{with }x_{n+1}\equiv b\pmod{q-1}, ( s + 1 , r 1 ′ s 1 , … , 1 , m + q − 1 , x 1 , … , x n + 1 ) with x n + 1 ≡ b ( mod q − 1 ) ,
where we set ∅ + 1 = 1 \varnothing^{+1}=1 ∅ + 1 = 1 .
Define an invariant S = ∑ λ ( x 1 , … , x n + 1 ) c ( x 1 , … , x n + 1 ) ∈ F q S=\sum\lambda(x_1,\ldots,x_{n+1})c(x_1,\ldots,x_{n+1})\in\mathbb{F}_q S = ∑ λ ( x 1 , … , x n + 1 ) c ( x 1 , … , x n + 1 ) ∈ F q , where c ( x 1 , … , x n + 1 ) c(x_1,\ldots,x_{n+1}) c ( x 1 , … , x n + 1 ) is the coefficient of ( s + 1 , 1 , … , 1 ⏟ r 1 ′ s , m + q − 1 , x 1 , … , x n + 1 ) (\mathfrak{s}^{+1},\underbrace{1,\ldots,1}_{r\ 1's},m+q-1,x_1,\ldots,x_{n+1}) ( s + 1 , r 1 ′ s 1 , … , 1 , m + q − 1 , x 1 , … , x n + 1 ) in Ind P \operatorname{Ind}P Ind P . Assume the coefficient of L [ s ; t ′ ] \mathcal{L}[\mathfrak{s};\mathfrak{t}'] L [ s ; t ′ ] in P P P is c c c , we prove S = c S=c S = c :
For the L [ s i ; t i ] \mathcal{L}[\mathfrak{s}_i;\mathfrak{t}_i] L [ s i ; t i ] in P P P with s i = s \mathfrak{s}_i=\mathfrak{s} s i = s , if H [ s ; t i ] \mathcal{H}[\mathfrak{s};\mathfrak{t}_i] H [ s ; t i ] has the tuples we consider, we have shown that x i ≤ q x_i\le q x i ≤ q for all 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n and x n + 1 ≤ q − 1 x_{n+1}\le q-1 x n + 1 ≤ q − 1 . By comparing the component, we have λ ( x 1 , … , x n + 1 ) = 1 ⟺ t i = t ′ \lambda(x_1,\ldots,x_{n+1})=1\Longleftrightarrow\mathfrak{t}_i=\mathfrak{t}' λ ( x 1 , … , x n + 1 ) = 1 ⟺ t i = t ′ , and others are 0 0 0 . Hence these tuples do not contribute to S S S except H [ s ; t ′ ] \mathcal{H}[\mathfrak{s};\mathfrak{t}'] H [ s ; t ′ ] contributing c c c .
For the L [ s i ; t i ] \mathcal{L}[\mathfrak{s}_i;\mathfrak{t}_i] L [ s i ; t i ] in P P P with s i ≠ s \mathfrak{s}_i\ne\mathfrak{s} s i = s , the similar argument as in previous subsection implies
s i = ( s + 1 , 1 , … , 1 ⏟ r 1 ′ s , m + q − 2 ) . \mathfrak{s}_i=(\mathfrak{s}^{+1},\underbrace{1,\ldots,1}_{r\ 1's},m+q-2). s i = ( s + 1 , r 1 ′ s 1 , … , 1 , m + q − 2 ) .
So the L [ s i ; t i ] \mathcal{L}[\mathfrak{s}_i;\mathfrak{t}_i] L [ s i ; t i ] contribute ∑ j = 1 n + 1 λ ( t i ( j ) ) = 0 \sum_{j=1}^{n+1}\lambda(t_i^{(j)})=0 ∑ j = 1 n + 1 λ ( t i ( j ) ) = 0 .
Combine above discussion, we get S = c S=c S = c .
Finally, we show subtracting relations of TYPE I, II or III does not change S S S . We just need to show it for special relations: We first define G = Ind P G=\operatorname{Ind}P G = Ind P , if G G G is illegal, we have done. If not, we subtract a multiple of relation corresponding to the minimal tuple of G G G to eliminate it, we assume this relation is B h ∗ P [ u ; v ] B_h^*P[\mathfrak{u};\mathfrak{v}] B h ∗ P [ u ; v ] of TYPE II, other two cases can be treated similarly. Then we have
dep ( h ) + dep ( u ) + max { dep ( v ) , 1 } = { dep ( min ≺ P ) , s ≠ ∅ ; dep ( min ≺ P ) + 1 , s = ∅ . \operatorname{dep}(\mathfrak{h})+\operatorname{dep}(\mathfrak{u})+\max\{\operatorname{dep}(\mathfrak{v}),1\}
=
\begin{cases}
\operatorname{dep}(\min_{\prec}P), & \mathfrak{s}\ne\varnothing;\\
\operatorname{dep}(\min_{\prec}P)+1, & \mathfrak{s}=\varnothing.
\end{cases} dep ( h ) + dep ( u ) + max { dep ( v ) , 1 } = { dep ( min ≺ P ) , dep ( min ≺ P ) + 1 , s = ∅ ; s = ∅ .
At this time, the desired tuples has two possibilities: it can come from
( h , q + u + 1 , ( q − 1 ) ∗ v ) , (\mathfrak{h},q+\mathfrak{u}+1,(q-1)*\mathfrak{v}), ( h , q + u + 1 , ( q − 1 ) ∗ v ) ,
or come from
( h + 1 , ( q − 1 ) ∗ ( u , q + v ) ) . (\mathfrak{h}^{+1},(q-1)*(\mathfrak{u},q+\mathfrak{v})). ( h + 1 , ( q − 1 ) ∗ ( u , q + v )) .
If it come from the former. By comparing components with the current minimal tuples, we have
( h , q + u + 1 ) = ( s + 1 , 1 , … , 1 ⏟ r 1 ′ s , m + q − 1 ) , (h,q^{+u+1})=(s^{+1},\underbrace{1,\ldots,1}_{r\ 1's},m+q-1), ( h , q + u + 1 ) = ( s + 1 , r 1 ′ s 1 , … , 1 , m + q − 1 ) ,
or
( h , q + u + 1 ) = ( s + 1 , 1 , … , 1 ⏟ r 1 ′ s , m + q − 1 , x 1 , … , x u ) , (h,q^{+u+1})=(s^{+1},\underbrace{1,\ldots,1}_{r\ 1's},m+q-1,x_1,\ldots,x_u), ( h , q + u + 1 ) = ( s + 1 , r 1 ′ s 1 , … , 1 , m + q − 1 , x 1 , … , x u ) ,
for some 1 ≤ u ≤ n 1\leq u\leq n 1 ≤ u ≤ n .
When v ≠ ∅ \mathbf{v}\ne\emptyset v = ∅ , in the former case, B h ∗ P [ u ; v ] B_h^*P[u;\mathbf{v}] B h ∗ P [ u ; v ] contributes
∑ j = 1 n + 1 λ ( p ( j ) ) = 0 ; \sum_{j=1}^{n+1}\lambda(\mathbf{p}^{(j)})=0; j = 1 ∑ n + 1 λ ( p ( j ) ) = 0 ;
in the latter case, it contributes
∑ j = u + 1 n + 1 λ ( ( x 1 , … , x u , v ) ( j ) ) = 0. \sum_{j=u+1}^{n+1}\lambda((x_1,\ldots,x_u,\mathbf{v})^{(j)})=0. j = u + 1 ∑ n + 1 λ (( x 1 , … , x u , v ) ( j ) ) = 0.
When v = ∅ \mathbf{v}=\emptyset v = ∅ , ( q − 1 ) ∗ ∅ = ( q − 1 ) (q-1)*\emptyset=(q-1) ( q − 1 ) ∗ ∅ = ( q − 1 ) , hence b = q − 1 b=q-1 b = q − 1 . By previous discussion, we have v n = 1 v_n=1 v n = 1 . But it must be
( h , q + u + 1 ) = ( s + 1 , 1 , … , 1 ⏟ r 1 ′ s , m + q − 1 , x 1 , … , x n ) , (h,q^{+u+1})=(s^{+1},\underbrace{1,\ldots,1}_{r\ 1's},m+q-1,x_1,\ldots,x_n), ( h , q + u + 1 ) = ( s + 1 , r 1 ′ s 1 , … , 1 , m + q − 1 , x 1 , … , x n ) ,
as this time. Note that x n ≥ 2 > v n x_n\geq2>v_n x n ≥ 2 > v n , and if x n > q x_n>q x n > q , then x n − ( q − 1 ) ≥ 2 > v n x_n-(q-1)\geq2>v_n x n − ( q − 1 ) ≥ 2 > v n . By definition, λ ( x 1 , … , x n , q − 1 ) = 0 \lambda(x_1,\ldots,x_n,q-1)=0 λ ( x 1 , … , x n , q − 1 ) = 0 . It also has no contribution to S S S .
If it come from the latter. By comparing components, we have
h + 1 = ( s + 1 , 1 , … , 1 ⏟ r 1 ′ s , m + q − 1 ) , h^{+1}=(s^{+1},\underbrace{1,\ldots,1}_{r\ 1's},m+q-1), h + 1 = ( s + 1 , r 1 ′ s 1 , … , 1 , m + q − 1 ) ,
or
h + 1 = ( s + 1 , 1 , … , 1 ⏟ r 1 ′ s , m + q − 1 , x 1 , … , x u ) , h^{+1}=(s^{+1},\underbrace{1,\ldots,1}_{r\ 1's},m+q-1,x_1,\ldots,x_u), h + 1 = ( s + 1 , r 1 ′ s 1 , … , 1 , m + q − 1 , x 1 , … , x u ) ,
for some 1 ≤ u ≤ n 1\leq u\leq n 1 ≤ u ≤ n . The same argument implies zero contribution.
Now if G − k B h ∗ P [ u ; v ] G-kB_h^*P[u;\mathbf{v}] G − k B h ∗ P [ u ; v ] is illegal, where k k k is the coefficient of min ≺ G \min_{\prec}G min ≺ G , we are done. Otherwise use G − k B h ∗ P [ u ; v ] G-kB_h^*P[u;\mathbf{v}] G − k B h ∗ P [ u ; v ] replace G G G , then min ≺ G ≺ min ≺ ( G − k B h ∗ P [ u ; v ] ) \min_{\prec}G\prec\min_{\prec}(G-kB_h^*P[u;\mathbf{v}]) min ≺ G ≺ min ≺ ( G − k B h ∗ P [ u ; v ]) and repeat above procedure. We have proved S S S is still equal to c ≠ 0 c\ne0 c = 0 . So G G G can not become 0. After finitely many steps, G G G will become illegal with min ≺ P ≺ min ≺ G \min_{\prec}P\prec\min_{\prec}G min ≺ P ≺ min ≺ G , which derives a contradiction.
Remarks and declarations
We give some remarks on the proof in this paper to explain the main ideas. Some curious and subtle techniques and constructions can be explained from these ideas, but this is by no means easy.
Section 2 basically follows the ideas in [2 ] : we want to use the nilpotentency of Ind \operatorname{Ind} Ind on R w \mathcal{R}_w R w , which can be use to prove certain subspaces of R w \mathcal{R}_w R w are actually the whole space. To do this, establishing Theorem 2.13 and studying H ( ker L ) \mathcal{H}(\ker\mathcal{L}) H ( ker L ) are natural:
Informally, we can think Ind = H ∘ L − 1 \operatorname{Ind}=\mathcal{H}\circ\mathcal{L}^{-1} Ind = H ∘ L − 1 , then Ind − 1 = L ∘ H − 1 \operatorname{Ind}^{-1}=\mathcal{L}\circ\mathcal{H}^{-1} Ind − 1 = L ∘ H − 1 . So if we want to find a space V V V such that Ind − 1 ( V ) ⊆ V \operatorname{Ind}^{-1}(V)\subseteq V Ind − 1 ( V ) ⊆ V , the simplest idea is making L ∘ H − 1 ( V ) = 0 \mathcal{L}\circ\mathcal{H}^{-1}(V)=0 L ∘ H − 1 ( V ) = 0 , hence V = H ( ker L ) V=\mathcal{H}(\ker\mathcal{L}) V = H ( ker L ) .
However, unlike the arguments in [2 ] that introduce the so-called gInd operator and use more linear algebra methods, the space B C P w \mathcal{BCP}_w BC P w allows us to get desired results by using more techniques about tuples and their operations.
The construction of P ( s ; t ) \mathcal{P}(s;t) P ( s ; t ) seems to be mysterious, but directly calculating the LHS of Theorem 2.11 basically explains how to find it.
Another key construction in the proof is the RHS of Theorem 2.17 . Unfortunately, the author has no feasible idea for it.
Section 3 gives a new method to calculate dimensions: We study the relations among certain spaces instead of detailed linear relations.
The core idea seems to be Theorem 3.4, which leads to the final dimension formula. However, Theorem 3.1 may be more essential: We want to calculate dim F q B C P w \dim_{\mathbb{F}_q}\mathcal{BCP}_w dim F q BC P w , so considering the linear relations among B ∗ \mathcal{B}^{*} B ∗ and C \mathcal{C} C is necessary. Theorem 3.1 ensures that we can obtain some information from U w U_w U w . Since { B ∗ C t ( R 1 ) ∣ h ≠ ∅ } \{\mathcal{B}^{*}\mathcal{C}_t(R_1)\mid h\ne\emptyset\} { B ∗ C t ( R 1 ) ∣ h = ∅ } carries the information of U w F i x U_w^{Fix} U w F i x . So C t ( R 1 ) \mathcal{C}_t(R_1) C t ( R 1 ) will tell us information about U w / U w F i x U_w/U_w^{Fix} U w / U w F i x , which may be the starting point of Theorem 3.4.
Section 4 almost completely follows the path of [4 ] . The readers who are familiar with the technique of [4 ] may not find it difficult. There are essentially no new ideas but new complicated constructions, such as Theorem 4.1 (iii) and λ \lambda λ .
The author would also like to give some explanations for the BCP relations. The B ∗ \mathcal{B}^{*} B ∗ and C \mathcal{C} C operators, due to Todd in [8 ] , are ready-made, which can be understood as operations adding prefixes and suffixes to a tuples. If we study the relations computed by computers, after deleting the possible prefixes and suffixes, we may find there should exist other two operations: add 1 to the second component or insert 1 before the second component, which are actually the D 0 \mathcal{D}_0 D 0 and D 1 \mathcal{D}_1 D 1 operators in Theorem 2.1. Todd’s idea is that all K K K -relations come from the fundamental relation R 1 R_1 R 1 , so we similarly hope that all F q \mathbb{F}_q F q -relations come from Equation (8) , which is the unique F q \mathbb{F}_q F q -relation with the smallest weight.
There are some further problems which may be worth discussing:
First, the difference of Theorem 1.6 and Theorem 1.10 is what B ∗ ∘ C \mathcal{B}^{*}\circ\mathcal{C} B ∗ ∘ C acts on. It is easy to see P ( s ) = ∑ a B u ∗ C v ( R 1 ) \mathcal{P}(\mathfrak{s})=\sum a\mathcal{B}^{*}_{\mathfrak{u}}\mathcal{C}_{\mathfrak{v}}(R_1) P ( s ) = ∑ a B u ∗ C v ( R 1 ) for any s \mathfrak{s} s and some a ∈ K , u , v ∈ I a\in K,\mathfrak{u},\mathfrak{v}\in\mathcal{I} a ∈ K , u , v ∈ I . The problem is whether we can obtain more precise description for these a , u , v a,\mathfrak{u},\mathfrak{v} a , u , v , which may uncover how to descend from K K K to F q \mathbb{F}_q F q .
Another problem is about basis. Can we find a basis with a simple form for B C P w \mathcal{BCP}_w BC P w ? It is equivalent to study the linear independence among B u ∗ C v P ( s ) \mathcal{B}^{*}_{\mathfrak{u}}\mathcal{C}_{\mathfrak{v}}\mathcal{P}(\mathfrak{s}) B u ∗ C v P ( s ) or B u ∗ P ( s ; t ) \mathcal{B}^{*}_{\mathfrak{u}}\mathcal{P}(\mathfrak{s};t) B u ∗ P ( s ; t ) , for which there have been some results when w < 3 q w<3q w < 3 q in [4 ] .
The author believes these problems may not be too difficult, but decides to leave them for others’ time or token. The readers with intelligence or artificial intelligence may give it a try.
About AI use. The author provided the construction of D 0 , D 1 \mathcal{D}_0,\mathcal{D}_1 D 0 , D 1 and some relevant research notes for ChatGPT (GPT-6 Astra, OpenAI), then it generated all mathematical results in this paper.
However, you can still find a few traces of human presence in a flood of AI-generated outputs: The author rewrites and verifies the proofs, and simplifies some of them. The previous remarks are written independently by the author (The author hopes that they will be helpful to the readers, if there are any).
Doubao (ByteDance) was also used to assist the author in writing, especially providing the first sentence of the preceding paragraph.
Since the results were generated by AI, there may be some results not cited properly, and the author apologizes to the relevant authors. Please contact the author for revisions if such cases are found.
About verification and formalization. The author has independently verified all proofs in this paper.
This paper will not be submitted. So if readers find any errors, or find the proofs correct after careful examination, the author would appreciate being notified.
ChatGPT (GPT-6 Astra, OpenAI) also generated the formal proof of this paper in Lean 4, which can be found in https://github.com/jinyuanhu2004/On-the-Fq-linear-relations.git .
About credit. As for credits, the author has no idea who this belongs to. All he knows is it’s definitely not him.
Maybe it can belong to Coco, an extremely cute lady cat, and Bella, a wonderfully beautiful lady Pomeranian.
Acknowledgements. The author is deeply grateful to ITZY for their encouragement and support. The author also thanks ITZY, TWICE, LE SSERAFIM, NMIXX and MEOVV for staying up late with him while writing this paper. J. Hu: School of Mathematical Sciences, Fudan University, Shanghai, China
E-mail address: jinyuanhu2004@gmail.com