Vanishing of Multiple Zeta Values over $\mathbb{F}_q[t]$ at Negative Integers
Shuhui Shi
math.NT 11M38, 11M32, 11R58





Department of Mathematics, Texas A&M University, College Station,
TX 77843, USA
shuhui@math.tamu.edu










Let _q be the finite field of q elements. In this paper, we study the vanishing behavior of multizeta values over _q[t] at negative integers. These values are analogs of the classical multizeta values. At negative integers, they are series of products of power sums S_d(k) which are polynomials in t. By studying the t-valuation of S_d(s) for s < 0, we show that multizeta values at negative integers vanish only at trivial zeros. The proof is inspired by the idea of Sheats in the proof of a statement of “greedy element" by Carlitz.




Vanishing of Multizeta Values over _q[t] at Negative Integers
    Shuhui Shi
    version of December 30, 2023
=============================================================





§ INTRODUCTION
 

Classical multizeta values (i.e., over ), also known as “multiple zeta values", are defined as the convergent series

    ζ() =∑_ n_1 > n_2  > ⋯ > n_r  ≥ 11/n_1^s_1n_2^s_2⋯ n_r^s_r  ∈,

where =(s_1, …, s_r) ∈_+^r with s_1 > 1. We call r the depth and ∑_i s_i the weight of ζ(). Here and in the rest of the paper, _+ is the set of positive integers and =_+ ∪{0}. Multizeta values of depth 1 are the usual Riemann zeta values. Double zeta values (i.e., r=2) were first considered by Euler in 1776 <cit.> in the study of ζ(3). After a long time of oblivion, multizeta values of higher depth were introduced independently by Hoffman <cit.> and Zagier <cit.> in 1992. During the last three decades, great attention has been drawn to the study of multizeta values because of their appearance in many different contexts, including the absolute Galois group <cit.>, periods of mixed Tate motives <cit.>, knot invariants and calculations of integrals associated to Feynman diagrams in perturbative quantum field theory <cit.>. These various connections with other fields have led to big progresses in the study of classical multizeta values, although some fundamental questions still remain open (see <cit.>). 

Having learned about the rich interconnections in the classical case, Thakur, in 2002, defined two types of multizeta values over function fields <cit.>, one complex valued (generalizing special values of Artin-Weil zeta functions) and the other with values in Laurent series over finite field (generalizing Carlitz zeta values). The first type was completely evaluated in <cit.> for _q(t) (see <cit.> for a study in the higher genus case). In this paper, we focus on the second type and stick to the rational function field _q(t).

Throughout this paper, p is a prime and q := p^f is a power of p. We say an integer is q-even if it is divisible by q-1 and q-odd otherwise. Let K := _q(t) be the rational function field over the finite field _q, ∞ be the rational place of K with uniformiser 1/t and K_∞ := _q((1/t)) be its completion at ∞. Let A := _q[t] be the polynomial ring in t, A_+ := {monics in A} and A_d+:= {monic in A of degree d} for d ≥ 0. For d ≥ 0 and s ∈, we define the power sum

    S_d(s):=∑_a ∈ A_d+1/a^s∈ K.

Note that S_d(s) ∈ A if s < 0. The multizeta values at ∈^r over _q[t] are defined as

    ζ():=∑_d_1 > ⋯ > d_r ≥ 0 S_d_1(s_1) ⋯ S_d_r(s_r)   ∈ K_∞.

The convergence of ζ() at positive integers, i.e., ∈_+^r, is clear from definition of S_d. At non-positive integers, it follows from the fact that S_d(0)=0 for d > 0 and S_d(s)=0 for d ≫ 0 if s < 0 (see <ref> for details). At positive integers, the definition above can be restated as

    ζ() = ∑_a_1, a_2, …, a_r1/a_1^s_1 a_2^s_2⋯ a_r^s_r∈ K_∞,

where the sum is over all a_i ∈ A_d_i+ with d_1 > d_2 > ⋯ > d_r ≥ 0. Following the classical case, we say ζ() is of depth r and weight ∑_i s_i. For general introduction of results on function field multizeta values and comparison with the classical case, we refer the reader to the survey papers <cit.>. In this paper, ζ() is used to denote multizeta values in both the classical and function field cases. It should be clear which one we are referring to from the context. 

A natural question to ask is when ζ() vanishes. In classical case, ζ() > 0 by definition at positive integers with s_1 > 1. Treating s_i's as complex variables, the series defining ζ() is absolutely convergent in the region
{ (s_1, …, s_r) ∈^r: (s_1 + ⋯ + s_j) > j  for  1 ≤ j ≤ r } and can be meromorphically continued to ^r with singular hyperplanes { s_1=1, s_1+s_2 ∈{2,1,0,-2, -4, -6, …}, ∑_i=1^k s_i ∈_≤ k for  3 ≤ k ≤ r}. In particular, all the negative integer points, except when r=2 or s_1+s_2 odd, lie on these hyperplanes. Moreover, they are points of indeterminacy. See <cit.> and the references mentioned in its “Introduction" for several different approaches to define and determine the multizeta values at these points.

In function field case, Thakur <cit.> showed that ζ() ≠ 0 at positive integers. At negative integers, the vanishing of multizeta values of depth 1 is completely understood by Goss <cit.>. Its vanishing behavior is quite similar to that of the Riemann zeta values although lacking a functional equation. In this paper, we study the vanishing of ζ() at negative integers of higher depth. 

Replacing a by t^d+∑_i=1^d θ_i t^d-i in (<ref>), we can rewrite S_d(s) as a sum of monomials in t for negative s, whose sum indices are in ^d+1 satisfying some restrictions. Denote the set of these indices as U_d(-s). Our main result (restated as Theorem <ref>) gives an explicit description of the t-valuation of S_d(s) in terms of elements in U_d(-s). 

 
  Assume U_d(-s) ≠∅, then there is a unique monomial in the sum S_d(s) acheving the lowest degree. Moreover, this term correpsonds to the element in U_d(-s) whose reverse is lexicographically the largest.


This result implies monotonicity of the t-valuation of S_d(s) with respect to d, using which we completely solve the vanishing of ζ() at negative integers (stated as Theorem <ref> later). See <ref> for definition of “trivial zero".

 
  At negative integers, ζ() of depth at least 2 only vanishes at trivial zeros.


Here is the outline of the paper. In <ref>, we study the behavior of S_d(s) at negative s in detail and discuss how our main result implies Theorem <ref>. <ref> gives the proof of Theorem <ref>.


  The results of this paper are a part of the author's Ph.D. thesis at the University of Rochester. The author would like to express her sincere gratitude for her advisor, Prof. Dinesh Thakur, for suggesting this problem and for all of his guidance and encouragement.




§ MAIN RESULT
 

In this section, we study the vanishing behavior of multizeta values in detail. We continue to use the notations in the previous section. Our main object of study is S_d(s), the building blocks of multizeta values. The reader will see that the vanishing of ζ() is really a reflection of properties of S_d(s).



 §.§ Trivial Zeros.
 

Let s < 0. We first take a closer look at when S_d(s) vanishes. Writing out the coefficients of a  in (<ref>), we get

    S_d(s)    = ∑_θ_i ∈_q (t^d+θ_1 t^d-1+ ⋯ +θ_d)^-s
       = ∑_θ_i ∈_q∑_m_0+⋯ +m_d = -s
     m_i ≥ 0-sm_0, …, m_d θ_1^m_1⋯θ_d^m_d  t^dm_0+(d-1)m_1+⋯ +m_d-1
       = (-1)^d∑_m_0+⋯ +m_d = -s
     m_0 ≥ 0, m_i > 0 q-even for   i > 0-sm_0, …, m_d  t^dm_0+(d-1)m_1+⋯ +m_d-1
       = (-1)^d∑_⊕_i=0^d m_i= -s
     m_0 ≥ 0, m_i > 0 q-even for   i > 0-sm_0, …, m_d  t^dm_0+(d-1)m_1+⋯ +m_d-1,

where ⊕_i=0^d m_i denotes sum ∑_i=0^d m_i with no carry over of digits base p. The third equality comes from exchanging the two sum indices and the fact that ∑_θ∈_qθ^k=-1 if k is a positive multiple of q-1 and 0 otherwise. The last equality follows from Lucas' theorem. 

For k>0 and d ≥ 0, let

    U_d(k) := { (m_0, …, m_d) ∈^d+1: k = ⊕_i=0^d m_i  and  m_i > 0  is q-even for 1 ≤ i ≤ d}.

Let (n) be the multiset of p-powers adding up to n with no carry over in base p. More precisely, if n=∑_i=0^k a_i p^i with 0 ≤ a_i < p, (n) := {{p^i}_a_i: 0 ≤ i ≤ k }, where {m}_k denotes the sequence m, …, m with m repeated k times. Then the condition k = ⊕_i=0^d m_i is equivalent to

    (k) = _i=0^d (m_i).

Note that U_d(-s) is the set of sum indices in (<ref>). Clearly, S_d(s) vanishes if U_d(-s) = ∅. In <cit.>, Carlitz claimed without proof that the converse also holds. More precisely, he asserted that if U_d(-s) ≠∅, the term t^dm_0+(d-1)m_1+⋯ +m_d-1 with (m_0, …, m_d) lexicographically largest among sum indices attains the unique maximal degree. Such (m_0, …, m_d) is called greedy. This claim was not proved until 50 years later. Diaz-Vargas <cit.> gave a proof for the case q=p and a general proof for any q is given by Sheats <cit.>.

 
  For s< 0, S_d(s) ≠ 0 if and only if U_d(-s) ≠∅. Moreover, if U_d(-s) ≠∅, the summand in S_d(s) corresponding to the greedy element achieves the unique maximal degree.


Böeckle pointed out that with some results in <cit.>, one gets a more straightforward criterion when S_d(s) vanishes. 

  For k ∈_+ with base q expansion k=a_0 + a_1 q + ⋯ + a_n q^n, let l(k)=∑ a_i be the sum of base q digits of k. Recall that q=p^f. Define
  
    L_k:= min_i=0,…,f-1{l(kp^i)/(q-1)}.

  We note that since k ≡ l(k) q-1, L_k is an integer if and only if (q-1)|k, i.e., k is q-even.




  For s negative, S_d(s) = 0 ⇔ d > L_-s.


For reader's convenience, we provide a proof of the result above. For d ≥ 0 and k > 0, let

    V_d(k):={ (m_0, …, m_d) ∈ U_d(k) : m_0 >0 }.

The proposition follows from the following lemma of Sheats. We note that the notations and expression of the lemma are slightly different from those in Sheats' paper, but one can check that they are equivalent.

 
  V_d(k) = ∅⇔ d ≥ L_k.



  By Theorem <ref>, it is enough to show that U_d(k) = ∅ iff d > L_k. We break it up into two cases.

  If k is q-even, U_d(k)=V_d(k) ∪{ (0, m_1, …, m_d) | (m_1, …, m_d) ∈ V_d-1(k) }. U_d(k)=∅ iff V_d(k)=V_d-1(k)=∅, i.e., d-1 ≥ L_k by Lemma <ref>. Since L_k is an integer, d-1 ≥ L_k ⇔ d > L_k.

  If k is q-odd, then U_d(k)=V_d(k). Thus U_d(k)=∅ iff d ≥ L_k by Lemma <ref>. As L_k is not an integer in this case, d ≥ L_k ⇔ d > L_k.


Note that in (<ref>), the least d appearing in S_d(s_i) is r-i. Thus, if r-i>L_-s_i, all terms in the sum vanishes and so does the multizeta value. With this observation, we define

 
  Let r>1 and (s_1, …, s_r) ∈^r_- such that ζ (s_1, …, s_r)=0. We call (s_1, …, s_r) a trivial zero of ζ if there exists some 1 ≤ i ≤ r-1 such that r-i > L_-s_i. Otherwise, (s_1, …, s_r) is a nontrivial zero.




 §.§ Existence of Nontrivial Zero.
 

We now investigate nontrivial zeros of ζ() where s_i < 0. The depth 1 case is completely understood by Goss <cit.>.


  For s negative, ζ(s)=0 if and only if s is q-even.


Note that multizeta values in this case reduce to Carlitz zeta values. The above theorem shows that the behavior of zeros of Carlitz zeta at negative integers is analogous to that of the trivial zeros of the classical Riemann zeta function. However, unlike a direct implication from the functional equation of the Riemann zeta, the vanishing of ζ(s), without any known functional equations in the function field case, follows from cancellations among monomials. 

The proof of the nonvanishing of ζ(s) at q-odd s <cit.> showed that there is a unique term of least degree, 1, in the polynomial sum of ζ(s), which could not be canceled. Similarly, the fact that multizeta values at positive integers never vanish <cit.> follows from the strict monotonicity in d of the ∞-valuation of S_d(). We use the same strategy to show that there is no nontrivial zeros in higher depth case.


  M=(M_0, …, M_d) ∈ U_d(k) is called modest if (M_d, M_d-1, …, M_0) is lexicographically the largest, i.e., M_d ≥ m_d for all (m_0, …, m_d) ∈ U_d(k), M_d-1≥ m_d-1 for those (m_0, …, m_d) with m_d=M_d and so on. Such element always exists and is unique if U_d(k) ≠∅.


Our main result is the following theorem, which characterises the term in S_d(s) with least degree. Its proof is given in <ref>.


  Assume S_d(s) ≠ 0. The term corresponding to the modest element in U_d(-s) attains the unique minimum degree in t among all summands in S_d(s).


Recall that for d ≤ L_-s, elements in U_d(-s) and summands in (<ref>) are in one-to-one correspondence. Take (m_0, m_1, …, m_d) ∈ U_d(-s), then its corresponding term in S_d(s) has degree dm_0+(d-1)m_1+⋯+m_d-1. Define ν_d(s) := v_t(S_d(s)), where v_t is the t-valuation. We have the following corollary.

 
  Fix s < 0, then
  
    ν_⌊ L_-s⌋(s) > ν_⌊ L_-s⌋-1(s) > ⋯ > ν_1(s) ≥ν_0(s).




  Since ν_0(s)=v_t(1)=0 for all s, the last inequality is obvious. Assume 0 < d ≤ L_-s and let M=(M_0, …, M_d) be the modest element in U_d(-s), then Theorem <ref> implies ν_d(s)=dM_0+(d-1)M_1+⋯+M_d-1. Consider N=(M_0, …, M_d-2, M_d-1+M_d), then N∈ U_d-1(-s) and thus ν_d-1(s) ≤ (d-1)M_0+(d-2)M_1+⋯+M_d-2≤ν_d(s), where the second inequality is equality iff d=1 and M_d=-s.


With this result, we finish the discussion of the vanishing of multizeta values of higher depth at negative integers.

 
  For =(s_1, …, s_r) with s_i < 0 and r > 1, ζ()=0 if and only if  is a trivial zero.



  It is equivalent to show that ζ() ≠ 0 if  is not a trivial zero. In this case, the sum ζ()=∑_d_1 > ⋯ > d_r ≥ 0 S_d_1(s_1) ⋯ S_d_r(s_r) is nonempty. In particular, S_r-1(s_1) ⋯ S_0(s_r) ≠ 0 and 
  
    v_t(S_r-1(s_1) ⋯ S_0(s_r))=∑_i=1^r ν_r-i(s_i).

  For any other term S_d_1(s_1) ⋯ S_d_r(s_r) in the sum, d_i ≥ r-i for all i and there exist some j such that d_j > r-j > 0. Thus, by Corollary <ref>,
  
    v_t(S_d_1(s_1) ⋯ S_d_r(s_r))=∑_i=1^r ν_d_i(s_i) > v_t(S_r-1(s_1) ⋯ S_0(s_r)).

  By strict triangle inequality, v_t(ζ())=v_t(S_r-1(s_1) ⋯ S_0(s_r))=∑_i=1^r ν_r-i(s_i). In particular, ζ() ≠ 0.



  We note that the same strategy fails in analysing the vanishing of ζ() at integers of mixed signs. For both place t and ∞, s being positive and negative give opposite monotonicity of the valuation of S_d(s) in d. Hence there is no unique term with least valuation in general. For example, let q=3, 
  
    ζ(-8, 2)    = S_1(-8)S_0(2)+S_2(-8)S_0(2)+S_2(-8)S_1(2)
       = (2t^6+2t^4+2t^2+2)+(t^6+t^4+t^2)+(1)=0

  is a “nontrivial zero" in the sense of Definition <ref>. In the sum, S_1(-8)S_0(2), S_2(-8)S_1(2) attain the least valuation at t and S_1(-8)S_0(2), S_2(-8)S_0(2) attain the least valuation at ∞.




§ PROOF OF THEOREM <REF>
 

The proof of Theorem <ref> is quite complicated and combinatorial. This is because the two conditions on elements of U_d(-s) are with respect to p and q each while p and q are different in general. Major difficulty of the proof arises from how to track these two conditions simultaneously. 



 §.§ Special case.
 

When q=p is a prime, the problem mentioned above disappears and the theorem can be proved in a way similar to the proof of Theorem <ref> for q=p case by Diaz-Vargas. Another simple case, without restriction on q, is where s is q-even, which follows directly from the result on greedy element. We first prove these two special cases.


  Let k=-s and M=(M_0, …, M_d) ∈ U_d(k) be the modest element. For m = (m_0, …, m_d) ∈ U_d(k), define
  
    (m):=dm_0+(d-1)m_1+⋯+m_d-1

  to be its weight, which equals the degree of its corresponding term in S_d(s). For both cases, we need to show M achieves the unique minimum weight.

  (1) q=p is a prime: We show that given any non-modest element m, one can always adjust it to get another m' of smaller weight.  Let l > 0 be the largest index such that M_l > m_l. Then M_i=m_i for i>l by the choice of M. Recall that (n) is the multiset of p-powers represented by the base p digits of n. When q=p,  n is q-even iff (q-1)|#(n). We split the discussion into two cases. 
  
      
  (a) If #(M_l) ≤#(m_l), then there exist some p^e ∈(m_l) and p^e'∈(M_l)\(m_l) such that p^e < p^e'. By (<ref>), p^e'∈(m_l') for some l' < l. Let
      
    m'=(m_0, …, m_l'-p^e'+p^e, …, m_l-p^e+p^e', …, m_d),

      then it is easy to check that m'∈ U_d(k) and (m') < (m).
      
  (b) If #(M_l) > #(m_l), then #(M_l) - #(m_l) ≥ q-1 since both M_l and m_l are q-even. Note that ∑_i=0^d #(M_i)=∑_i=0^d #(m_i)=#(k). Thus there exists l'<l such that #(m_l') - #(M_l') ≥ q-1. Write (m_l')=P_1 ⊔ P_2, where #P_1 = q-1, and this implies m_l'=n_1 ⊕ n_2 with n_1 q-even. If l'>0, then n_2 > 0 and is also q-even. Consider
      
    m'=(m_0, …, m_l'-n_1, …, m_l+n_1, …, m_d),

      then m'∈ U_d(k) and (m') < (m).
   

  (2) s is q-even: Recall that
  
    V_d(k)={(m_0, …, m_d) ∈ U_d(k) : m_0 > 0 }.

  In this case, M∈ U_d(k) ∖ V_d(k) since otherwise (0, M_1, …, M_d+M_0) is also contained in U_d(k) whose reverse is lexicographically larger. Similar argument shows that m∈ U_d(k) ∖ V_d(k) if m is of minimum weight. Consider the bijective map 
  
    φ: (0, m_1, …, m_d) ↦ (m_d, …, m_1)

  between U_d(k) ∖ V_d(k) and V_d-1(k). Note that k=∑_i m_i, thus, for m∈ U_d(k) ∖ V_d(k),
  
    (m)=(d-1)m_1+⋯+m_d-1=(d-1)k-(φ(m)).

  (m) being minimum indicates that φ(m)=(m_d, …, m_1) achieves the largest weight in V_d-1(k). By Theorem <ref>, φ(m) has to be the greedy element in U_d-1(k). This implies that the reverse of m is lexicographically the largest in U_d(k) ∖ V_d(k), hence m=M.




 §.§ General case.
 

Our proof for general case is inspired by Sheats' proof <cit.> of Theorem <ref> on greedy element. We prove by contradiction. Roughly speaking, assuming there exists a tuple not modest in U_d(-s) gives a term of lowest degree in S_d(s), we construct another term with smaller degree.

We fix a prime power q=p^f. In this section, x̅ denotes a column vector of length f, where x is either an English or Greek letter, with or without subscript. If not mentioning explicitly, its entires are denoted as x_i with 0 ≤ i < f, e.g., u̅=[u_0, u_1, …, u_f-1]^t. Note that the subscripts start from 0. The zero vector is denoted as 0̅.



  §.§.§ Set up and preliminaries.
 

Before the proof, we change to a different notation for easy expression. A d-tuple (X_1, …, X_d) ∈^d is said to be a composition of N if N=∑_i=1^d X_i. For d > 0 and N ∈_+, let

    W_d(N)    = { (X_1, X_2, …, X_d) ∈^d : (X_d, X_d-1, …, X_1) ∈ U_d-1(N) }
       = { (X_1, X_2, …, X_d) ∈^d : N = ⊕_i=1^d X_i,  and  X_i > 0  is q-even for  i < d }.

In this new set up, the modest element in U_d-1(N) corresponds to be the lexicographically largest composition in W_d(N), which we again call it modest.


  Let X=(X_1, …, X_d) ∈ W_d(N). Define its weight, denoted as (X), by
  
    (X)=X_1+2X_2+⋯+dX_d.

  Any composition X achieving the minimum weight in W_d(N) is called optimal. 


One can check that Theorem <ref> is equivalent to the following.

 
  For W_d(N) ≠∅, the modest composition is the only optimal composition. 


 
  The theorem holds for d=1 trivially since W_1(N)={(N)} has only one composition. For d=2, (X)=2N-X_1 for any X∈ W_2(N) and hence the modest composition is the only optimal element.


The following proposition consists of some observations on how to get new modest or optimal compositions from old ones.

 
  Suppose W_d(N) ≠∅. X=(X_1, …, X_d) is the modest composition in W_d(N). Then
  
    
  (i) (X_1, X_2, …, X_d-1) is the modest composition in W_d-1(N-X_d);
    
  (ii) (X_2, X_3, …, X_d) is the modest composition in W_d-1(N-X_1);
    
  (iii) for any n ≥ 0, (p^nX_1, …, p^nX_n) is the modest composition in W_d(p^nN).
  
  These three statements remain true when replacing “the modest composition" with “an optimal composition".



  (i) and (ii) are obvious from definition in each case. To show (iii), we observe that all p-powers in (p^nN) are divisible by p^n. Thus, for (Y_i) ∈ W_d(p^nN), p^n | Y_i for all i since (Y_i) ⊂(p^nN). Moreover, (Y_i) ↦ (p^-nY_i) gives a 1-to-1 correspondence between compositions in W_d(p^nN) and W_d(N). (iii) follows from this observation easily in both cases.


Given base p expansion n=∑_j ≥ 0 a_jp^j, we define Γ(n) ∈^f to be the column vector [μ_0, …, μ_f-1]^t, where 

    μ_i=∑_j ≡ i f a_j.

Let ψ̅_0 := [1, p, …, p^f-1]^t, then

    ψ̅_0Γ(n)=μ_0+⋯+p^f-1μ_f-1

is the sum of base q digits of N. In particular, n is q-even iff (q-1) |ψ̅_0Γ(n). Then X∈ W_d(N) if and only if

  
  (1) Γ(N)=Γ(X_1)+Γ(X_2)+⋯+Γ(X_d),
  
  (2) for 1 ≤ i ≤ (d-1), (q-1) |ψ̅_0Γ(X_i)≠ 0. 

For a composition X=(X_1, …, X_d) of N, define Γ(X) to be the f × d matrix with columns Γ(X_1), …, Γ(X_d).

 
  Let q=9 and N=131. In base 3, N=11212_3. Thus Γ(N)=[5, 2]^t. For any X∈ W_2(N), Γ(X) is one of the two matrices: [ 5 0; 1 1 ], [ 2 3; 2 0 ]. (128, 3)=(11202_3, 10_3), (104, 27)=(10212_3, 1000_3) ∈ W_2(N) correspond to the first one, and the rest correspond to the second one. 


In the example above, we give a partition of compositions in W_d(N) with respect to matrix representation. Given B ∈_f × d(), define

    W^B_d(N):={X∈ W_d(N): Γ(X)=B}.

We call B a valid matrix of W_d(N) if W^B_d(N) ≠∅. Let B_1, …, B_d be columns of B, then B is valid if and only if 

  
  (1) Γ(N)=B_1+⋯+B_d,
  
  (2) for 1 ≤ i ≤ (d-1), (q-1) |ψ̅_0B_i≠ 0. 

For n > 0, denote τ(n) the nonincreasing sequence of p-powers in (n) and τ_k(n) be its subsequence consisting of those p^i with i ≡ k f for 0 ≤ k < f. 

 
  Take q=9 and N=131=11212_3. Then 
  
    τ(N)=(3^4, 3^3, 3^2, 3^2, 3^1, 3^0, 3^0), τ_0(N)=(3^4, 3^2, 3^2, 3^0, 3^0),  τ_1(N)=(3^3, 3^1).



Given X∈ W_d(N), τ_k(X_i)'s give a partition of p-powers in τ_k(N) for each k. We call X is τ-monotonic if the sequence τ_k(N)  is the concatenation of the subsequences τ_k(X_1), τ_k(X_2), …, τ_k(X_d) for all 0 ≤ k < f. Note that there is a unique τ-monotonic composition in W^B_d(N) for each valid B.


  Suppose B is a valid matrix of W_d(N), then the τ-monotonic composition with respect to B is lexicographically the largest and acheives the unique minimum weight in W_d^B(N). In particular, both modest and optimal compositions are τ-monotonic.



  Take X=(X_1, …, X_d) ∈ W_d^B(N) which is not τ-monotonic. Then there exist some k, i, j, m, n such that i < j, m < n, with p^m ∈τ_k(X_i), p^n ∈τ_k(X_j). Consider the composition Y=(X_1, …, X_i-p^m+p^n, …, X_j-p^n+p^m, …, X_d). Then Y∈ W_d^B(N) since m ≡ n ≡ k f. Clearly, Y is lexicographically larger than X. Easy computation shows that (Y)=(X)-(j-i)(p^n-p^m) < (X).


Define

    := {Γ(n): n > 0  is q-even}.

Given B=[B_1, …, B_d] an f × d matrix with columns B_i, the conditions for B being valid for W_d(N) can be translated as

  
  (1) Γ(N)=B_1+⋯+B_d,
  
  (2) B_i ∈ for 1 ≤ i ≤ (d-1). 

We follow Sheats' discussion in <cit.> to give a characterization of vectors in . Let _0, …, _f-1 be the standard basis of ^f, i.e., [_0, …, _f-1]=I, the identity matrix. Define matrix E=[E_0, E_1, …, E_f-1] with columns

    E_i := p_i-1-_i.

Here and from now on, subcripts which should range from 0 to f-1 are evaluated modulo f, e.g. _-1=_f-1 and E_0=p_f-1-_0. Given vectors u̅ and v̅=Eu̅, we have, for all i

    v_i=pu_i+1-u_i.

Let R = [_1, _2, …, _f-1, _0] be the permutation matrix such that R_i=_i+1. Then R^f=I and Ru̅Rv̅=⟨u̅, v̅⟩ for any u̅ and v̅. Recall that ψ̅_0= [1, p, …, p^f-1]^t. Define 

    ψ̅_i := R^i ψ̅_0=[p^f-i, …, p^f-1, 1, …, p^f-1-i]^t

for 1 ≤ i < f. Then

    ψ̅_iE_j= q-1      if  i=j
     0      otherwise,

which implies

    E^-1=(q-1)^-1[ψ̅_0, ψ̅_1, …, ψ̅_f-1]^t.

Given two vectors u̅ and v̅, we denote u̅≥v̅ if u_i ≥ v_i for all i, u̅ > v̅ if u̅≥v̅ and u_i > v_i for some i and u̅≫v̅ if  u_i > v_i for all i.

 
  Let u̅=Ea̅ and v̅=Eb̅, then
  
    
  (i) u̅ > v̅⇒a̅≫b̅. In particular, if u̅ > 0̅, then a̅≫0̅.
    
  (ii) Let 1̅=[1, …, 1]^t. If 0̅ < u̅ < (p-1) 1̅, then 0̅≪a̅≪1̅.
  



  a̅-b̅=E^-1(u̅-v̅). Since all components of E^-1 are positive, u̅-v̅>0̅ implies a̅-b̅≫0̅. This proves (i). (ii) is a direct application of (i) as [p-1, …, p-1]^t=E[1, …, 1]^t.


Take a positive integer n. Let Eα̅=Γ(n), then we have, for each i

    α_i=(q-1)^-1ψ̅_0Γ(p^f-in)

since RΓ(n)=Γ(pn) and ψ̅_iΓ(n)=R^iψ̅_0Γ(n)=ψ̅_0R^f-iΓ(n). In particular,

    α̅∈^f ⇔ n .

The above discussion can be rephrased as following.


  =(E^f)∩ (^f\{0̅}).




  §.§.§ Criterion for W_d(N) ≠∅.
  

For d > 0, define

    I_d := {Γ(n): ∃ v̅_1, …, v̅_d-1∈Γ(n) > v̅_1+⋯+v̅_d-1},


    J_d := ∩ (I_d \ I_d+1).

For d=0, we set J_0 = ∅. By definition, J_d consists of those Γ(n) such that n can be written as a sum of d many, but not d+1 many, positive q-even numbers without carry over in base p. Then 

    W_d(N) ≠∅⇔Γ(N) ∈ J_d-1∪ I_d.

The next proposition by Sheats characterizes elements in I_m and J_m.

 
  For m ≥ 1,
  
    
  (i) I_m={ Ex̅∈^f\{0̅}: x̅∈^f min_0 ≤ i < f(x_i)>m-1},
    
  (ii) J_m={ Ea̅∈^f\{0̅}: a̅∈^f min_0 ≤ i < f(a_i)=m}.
  


With (<ref>), it implies the following result which is indeed equivalent to Proposition <ref>.

 
  Let Γ(N)=Eα̅, then W_d(N) ≠∅ iff min_0 ≤ i < f(α_i) ≥ d-1. 



  §.§.§ Modest/optimal composition.
 

The following results give estimation on components of the modest and optimal compositions.


  Let X=(X_1, …, X_d) ∈ W_d(N) be modest or optimal. Then Γ(X_i) ∈ J_1 for 2 ≤ i ≤ d-1, X_d=0 if N is q-even or Γ(X_d) ∈ I_1\ I_2 if N is q-odd.



  We prove by contrapositive. 
  
  N is q-even: If X_d ≠ 0, then X is neither modest nor optimal from the discussion in <ref>. If Γ(X_i)=v̅_1+v̅_2 for some 2 ≤ i ≤ d-1 and vectors v̅_1, v̅_2 ∈, define 
  
    Y := ( X_1+a_1, …, X_i-1, a_2, X_i, …, X_d ).

  Since v̅_i ∈, both a_i's are q-even. The sum of entries in Y has no carry over in base p. So Y∈ W_d(N). Moreover, Y is lexicographically larger than X, and (Y)=(X)-(i-1)a_1<(X).
  
  N is q-odd: Suppose Γ(X_d)=w̅_1+w̅_2 with w̅_1 ∈, w̅_2 ∈ I_1. We have X_d=b_1 ⊕ b_2 with Γ(b_i)=w̅_i and b_1 q-even. Define Y := (X_1+b_1, X_2, …, X_d-1, b_2). Then similar argument as above shows that Y∈ W_d(N), Y is lexicographically larger than X and (Y)<(X).


Take N ∈_+, let u̅=Γ(N) and β̅=E^-1u̅.

 
  Let v̅=Eα̅∈^f with 0̅ < v̅ < u̅. Suppose min_0 ≤ i < f(β_i-α_i) = k for some  k ∈, then there exists some w̅∈ with v̅≤w̅≤u̅ and u̅-w̅∈ J_k ∪ I_k+1.


 
  To find such an w̅ is equivalent to find a γ̅ with w̅=Eγ̅. Recall that if x̅=Ea̅, x_i=pa_i+1-a_i. By Propositions <ref> and <ref>, we get the following conditions on γ̅:
  
    
  (1) v_i ≤ pγ_i+1-γ_i ≤ u_i,
    
  (2) γ_i ∈ and min_0 ≤ j < f(β_j-γ_j) ≥ k.
  
  To construct γ̅, take an l such that β_l-α_l=k. Let γ_l=α_l. For i=l-1, l-2, …, l-f+1, define inductively
  
    γ_i=min(β_i-k, pγ_i+1-v_i).

  Condition (2) holds automatically by the construction of γ_i. The construction also implies v_i ≤ pγ_i+1-γ_i for i ≠ l. To prove it for i=l, we first show that γ_i ≥α_i for all i. By definition, γ_l=α_l. We prove the rest by backwards induction. Suppose γ_i+1≥α_i+1. If γ_i=β_i-k, then clearly γ_i ≥α_i since β_i-α_i≥ k; otherwise,
  
    γ_i     = pγ_i+1-v_i
        = pγ_i+1-pα_i+1+α_i ≥α_i.

  Since γ_i is an integer, we have γ_i ≥α_i. Now we have v_l ≤ pγ_l+1-γ_l since
  
    pγ_l+1-v_l = pγ_l+1-pα_l+1+α_l ≥α_l=γ_i.

  Next we show pγ_i+1-γ_i ≤ u_i. For i=l,
  
    u_l-(pγ_l+1-γ_l)     = pβ_l+1-β_l-(pγ_l+1-γ_l)
        = p(β_l+1-γ_l+1)-(β_l-γ_l)
        = p(β_l+1-γ_l+1)-(β_l-α_l)
        > p(β_l+1-γ_l+1)-k-1 ≥ -1,

  where the last inequality comes from that β_l+1-γ_l+1≥ k and p ≥ 2. Since the left-hand side is an integer, we have
  
    u_l-(pγ_l+1-γ_l) ≥ 0.

  Now let i ≠ l. If γ_i=pγ_i+1-v_i, then pγ_i+1-γ_i=v_i ≤ u_i; otherwise, γ_i=β_i-k, then a similar computation as in the i=l case shows pγ_i+1-γ_i ≤ u_i.


 
  Take N with base p-expansion N=∑_i=0^n a_ip^i, where a_n ≠ 0. Suppose W_d(N) ≠∅. Let X=(X_1, …, X_d) ∈ W_d(N) be modest or optimal, then
  
    
  (i) X_1 ≥ a_np^n. In particular, X_1>N/2.
    
  (ii) N ≤(X) < 2N.
    
  (iii) W_d(N-X_1)=∅ if d ≥ 2. In particular, by (<ref>), Γ(N-X_1) ∉I_d.



 
  We prove each case separately.

  X modest: Let u̅=Γ(N) and α̅=E^-1u̅. By Corollary <ref>, min_i(α_i) = m ≥ d-1. Let k=n f and β̅=E^-1(a_ne̅_k). Lemma <ref> implies β_i = 1 for each i. By Lemma <ref>, we can extend v̅=a_ne̅_k to some w̅_1 ∈ with u̅-w̅_1 ∈ J_m-1∪ I_m. In particular, we can write u̅-w̅_1 as u̅-w̅_1=w̅_2+⋯+w̅_d-1+w̅_d, where w̅_i ∈ for 2 ≤ i ≤ d-1 and w̅_d ∈^d. Take B=[w̅_1, …, w̅_d], then B is a valid matrix, i.e., W_d^B(N) ≠∅. Let Y be the τ-monotonic element in W_d^B(N), then Y_1 ≥ a_np^n since w̅_1 ≥ a_ne̅_k. X is modest so X_1 ≥ Y_1 ≥ a_np^n. This proves (i).

  We prove (ii) by induction on d. For d=1, X=(N) and (X)=N. Suppose (ii) holds for d-1. By Proposition <ref> (ii), Y=(X_2, …, X_d) is modest in W_d-1(N-X_1). By induction, N-X_1 ≤(Y)<2(N-X_1)<N. Thus N ≤(X)=N+(Y)<2N.

  Suppose (iii) fails. Take (X'_1, …, X'_d) ∈ W_d(N-X_1), then (X_1+X'_1, X'_2, …, X'_d) ∈ W_d(N). But this contradicts that X is modest. 

  X optimal: (ii) holds automatically by the minimum weight property. 
  
  To prove (i), we first show that X_1 ≥ p^n. If N is q-even or d < 3, by <ref> and Remark <ref>, optimal is equivalent to modest, thus (1) holds. We assume N is q-odd and d ≥ 3. Then X_1+X_2 > p^n since otherwise X_1+X_2 < p^n < N/2 and (X)>N+2(N-X_1-X_2)>2N. For (X) being minimal, X_1 ≥ X_2 which implies X_1 ≥ p^n. Now suppose X_1=∑_i=0^nb_ip^i with 0 < b_n < a_n, then N-X_1>p^n. Note that (X_2, …, X_d) is optimal in W_d-1(N-X_1), thus X_2 ≥ p^n and N-X_d>(b_n+1)p^n. But by Proposition <ref> (i), (X_1, …, X_d-1) ∈ W_d-1(N-X_d) is optimal and thus modest since N-X_d is q-even. In particular, X_1 ≥ (b_n+1)p^n. Contradiction.

  At last, we show (iii) holds. If not, let (X'_1, …, X'_d) ∈ W_d(N-X_1) be optimal. Then X'_1>(N-X_1)/2 by (i). (X'_2, …, X'_d) being optimal in W_d-1(N-X_1-X'_1), (X'_2, …, X'_d)<2(N-X_1-X_1')<N-X_1. Let Y=(X_1+X'_1, X'_2, …, X'_d), then Y∈ W_d(N) and (Y)=N+(X'_2, …, X'_d)<2N-X_1. However, (X)=N+(X_2, …, X_d)≥ 2N-X_1. Contradiction.




  §.§.§ Constructing composition of smaller weight.
 

Suppose Theorem <ref> fails. Then q=p^f with f > 1. Take the least d and some N such that there exist M=(M_i), O=(O_i) ∈ W_d(N) with M modest, O optimal and M≠O. Then N is q-odd, d ≥ 3 and M_1 > O_1 by <ref>, Remark <ref> and Proposition <ref> (ii) respectively. Let p^a be the largest p-power in (M_1) ∖(O_1). By Proposition <ref> (iii), we may assume a ≡ f-1 f. Let 

    u̅   :=Γ(N),    x̅   :=Γ(M_1),    y̅   :=Γ(O_1),
    η̅   :=E^-1u̅,    α̅   :=E^-1x̅,   β̅   :=E^-1y̅.

By our construction, x_f-1 > y_f-1 since both M and O are τ-monotonic. Define

    v̅=[v_i]^t:=[min(x_i, y_i)]^t,   w̅=[w_i]^t:=y̅-v̅.

Then w_f-1=0. Note that w̅ > 0̅, since otherwise x̅ > y̅ and x̅-y̅∈, Γ(N-O_1)=(x̅-y̅)+Γ(M_2)+⋯+Γ(M_d) ∈ I_d, contradicting Proposition <ref> (iii). Let 0 ≤ k ≤ f-2 be the least subscript such that w_k>0. We have the following result.

 
  
    
  (i) ψ̅_iw̅ < ψ̅_ie̅_f-1 for 0 ≤ i ≤ k.
    
  (ii) η_i-β_i ≥ d-2 for all i and there exists k < l ≤f-1 such that η_l-β_l=d-2 and η_i-β_i ≥ d-1
    for l-f < i ≤ k, i.e., i=l+1, l+2, …, f-1, 0, 1, …, k.
  



  We show (i) by contradiction. For each 0 ≤ i ≤ k, by definition of ψ̅_i,
  
    ⟨ψ̅_i, e̅_f-1⟩=p^f-1-i

  and ⟨ψ̅_i, w̅⟩ is a sum of p-powers less than p^f-1-i since w_j=0 for -1 ≤ j <i. Suppose ⟨ψ̅_i, w̅⟩≥⟨ψ̅_i, e̅_f-1⟩ for some 0 ≤ i ≤ k. Then there is a subset of p-powers in the sum ⟨ψ̅_i, w̅⟩ whose terms add up to p^f-1-i. In other words, there exists some w̅' ≤w̅ such that
  
    ψ̅_iw̅'=ψ̅_ie̅_f-1.

  Another observation is that w̅ represents those p-powers p^b in (O_1) ∖(M_1). In particular, b<a for each b since O_1<M_1. w̅' ≤w̅ represents a subset of such p-powers. Let M be the sum of p-powers represented by w̅', then M<p^a and Γ(M)=w̅'. Note that Γ(p^a)=e̅_f-1, then (<ref>) implies
  
    M ≡ p^a q-1.

  By the choice of p^a, we can find some j>1 such that p^a ∈(O_j). Consider composition
  
    X=(O_1-M+p^a, …, O_j-p^a+M, …, O_d),

  then X∈ W_d(N) and (X)<(O). Contradiction.

  To prove (ii), we note that E(η̅-β̅)=Γ(N-O_1)=Γ(O_2)+ ⋯ + Γ(O_d) ∈ I_d-1. Hence, by Proposition <ref> (i), η_i-β_i > d-2. Thus 
  
    η_i-β_i ≥ d-2

  for all i. On the other hand, Γ(N-O_1) ∉I_d implies min_i (η_i-β_i) = d-2. Let l be the largest subscript such that η_l-β_l = d-2. Then for l < i < f,
  
    η_i-β_i ≥ d-1.

  To finish the proof, we show η_i-β_i ≥ d-1 for 0 ≤ i ≤ k. By construction, we have
  
    x̅=v̅+w̅_1,   y̅=v̅+w̅,

  where w̅_1 ≥e̅_f-1. For 0 ≤ i ≤ k,
  
    β_i     = (q-1)^-1ψ̅_iy̅
        = (q-1)^-1(ψ̅_iv̅+ψ̅_iw̅)
    
        (by (i))     < (q-1)^-1(ψ̅_iv̅+ψ̅_ie̅_f-1)
       ≤ (q-1)^-1(ψ̅_iv̅+ψ̅_iw̅_1)
        = (q-1)^-1ψ̅_ix̅ = α_i.

  Note that E(η̅-α̅)=Γ(N-M_1) ∈ I_d-1, then by Proposition <ref> (i), we have η_i-α_i > d-2 for all 0 ≤ i < f. For 0 ≤ i ≤ k, β_i < α_i by the above calculation, and thus η_i-β_i ≥ d-1.


Define, for 1 ≤ j ≤ d,

    u̅_j=[u_0, j, …, u_f-1, j]^t:=∑_s=j^dΓ(O_s),  θ̅_j=[θ_0,j, …,θ_f-1, j]^t:=E^-1u̅_j.

Note that u̅_1=u̅ and θ̅_1=η̅. By Lemma <ref> (ii), we have

    θ_l, 2=d-2,   θ_i, 2≥ d-1  l-f < i ≤ k.

The following construction uses θ̅_j to get a new composition Z∈ W_d(N) whose weight is less than that of O. Let ϕ̅_1=[ϕ_i, 1]^t:=θ̅_1. Define ϕ̅_2=[ϕ_i, 2]^t inductively as following.

    ϕ_i, 2=θ_i, 2   for  k < i ≤ l
    min(θ_i, 2-1, pϕ_i+1, 2)     i=k, k-1, …, 0, f-1, f-2, …, l+1.

For j=3, …, d, define ϕ̅_j=[ϕ_i, j]^t recursively as

    ϕ_i, j=θ_i, j   for  k < i ≤ l
    min(ϕ_i, j-1-1, pϕ_i+1, j)     i=k, k-1, …, 0, f-1, f-2, …, l+1.


 
  For 1 ≤ j ≤ d, let
  
    z̅_j=[z_0, j, …, z_f-1, j]^t:= Eϕ̅_j.

  Then
  
    
  (i) ϕ̅_j-ϕ̅_j+1∈_+^f for 1 ≤ j ≤ d-1.
    
  (ii) z̅_j∈^f for all j.
    
  (iii) min_0 ≤ i ≤ f-1(ϕ_i, j)=ϕ_l, j=d-j for 2 ≤ j ≤ d.
    
  (iv) z_k, 2=u_k, 2+1 ≤ u_k.
    
  (v) 0 ≤ z_l, 2≤ u_l, 2-p.
    
  (vi) 0 ≤ z_i, 2≤max(u_i, 2-(p-1), 0) for l-f < i < k.
    
  (vii) z_i, j=u_i, j for k<i<l and 2 ≤ j ≤ d.
    
  (viii) 0 ≤ z_i, j≤max(z_i, j-1-(p-1), 0) for l-f ≤ i ≤ k and 3 ≤ j ≤ d.
  



  (i): By construction, ϕ_i,j-ϕ_i,j+1 > 0 for all i,j. Hence it is enough to show 
  
      
  (a) θ̅_j - θ̅_j+1∈^f for 1 ≤ j ≤ d-1;
      
  (b) {ϕ_i, j}={θ_i, j} for all i, j, where {x} is the fractional part of x.
  
  We note that for 1 ≤ j ≤ d-1
  
    E(θ̅_j-θ̅_j+1)=Γ(O_j) ∈.

  This implies (a) by Proposition <ref>. (a) says  {θ_i,j}={θ_i, j+1} for all i and j. Also p{θ_i+1, j}-{θ_i, j}∈ since pθ_i+1, j-θ_i, j=u_i, j∈. With these two properties in mind, starting with the initial case {ϕ_i, 1}={θ_i, 1} since ϕ̅_1=θ̅_1, following the inductive construction of ϕ_i, j, one can check that (b) holds.

  (ii): Since ϕ̅_1=η̅, z̅_1=Eη̅=u̅∈^f. For j > 1,
  
    z̅_j=Eϕ̅_1-∑_s=1^j-1 E(ϕ̅_s-ϕ̅_s+1).

  By (i), ϕ̅_s-ϕ̅_s+1∈^f for each s, hence z̅_j ∈^f.

  (iii): We first show that ϕ_i,j≥ d-j for 2 ≤ j ≤ d and k < i ≤ l. This is the same as showing  
  
    θ_i,j≥ d-j

  for 2 ≤ j ≤ d, since ϕ_l,j=θ_i,j by construction. Note that for each j, Eθ̅_j=∑_s=j^dΓ(O_j) ∈ I_d-j+1. Thus the statement follows from Proposition <ref>.
  
  Next, we prove ϕ_l,j = d-j for each j. The j=2 case is given by (<ref>). For 3 ≤ j ≤ d, θ̅_2-θ̅_j=∑_s=2^j-1 E^-1Γ(O_s). By Propositions <ref> and <ref>, θ_l, 2-θ_l, j≥ j-2, which implies θ_l, j≤θ_l, 2-(j-2)=d-j. Thus the statement follows since θ_l, j≥ d-j.
  
  Last, we show ϕ_i,j≥ d-j for l-f < i ≤ k by induction on j. For j=2, we have 
  
    θ_i, 2-1≥ d-2

  for l-f < i ≤ k by (<ref>). Taking i=k, since pϕ_k+1, 2 = pθ_k+1, 2≥ d-2, we get
  
    ϕ_k, 2=min(θ_k, 2-1, pϕ_k+1, 2) ≥ d-2.

  Note that 
  
    ϕ_i+1, 2≥ d-2    ⇒pϕ_i+1, 2≥ d-2
       ⇒ϕ_i, 2=min(θ_i, 2-1, pϕ_i+1, 2) ≥ d-2.

  Hence, a backwards induction on i starting from k implies that for k ≥ i > l-f,
  
    ϕ_i,2≥ d-2.

  Suppose ϕ_i, j-1≥ d-j+1 for l-f < i ≤ k. Then ϕ_k,j-1-1≥ d-j and pϕ_k+1, j≥ d-j since ϕ_k+1, j≥ d-j by previous statement. This implies ϕ_k, j=min(ϕ_k, j-1-1, pϕ_k+1, j) ≥ d-j. Similarly, we have
  
    ϕ_i+1, j≥ d-j    ⇒pϕ_i+1, j≥ d-j 
       ⇒ϕ_i, j=min(ϕ_i, j-1-1, pϕ_i+1, j) ≥ d-j.

  Again, a backwards induction on i shows that ϕ_i, j≥ d-j for k ≥ i  > l-f.

  (iv): Since
  
    pϕ_k+1, 2-(θ_k, 2-1)=pθ_k+1, 2-θ_k, 2+1=u_k, 2+1 > 0,

  ϕ_k, 2=θ_k, 2-1 and z_k, 2=u_k, 2+1. By construction,
  
    u_k, 2=u_k-y_k ≤ u_k-w_k ≤ u_k-1,

  so u_k, 2+1≤ u_k.

  (v): The second inequality is given by
  
    z_l, 2=pϕ_l+1, 2-ϕ_l, 2≤ p(θ_l+1, 2-1)-θ_l, 2=u_l, 2-p.

  To show z_l, 2≥ 0, we have min_0 ≤ i ≤ f-1(ϕ_i, 2)=ϕ_l, 2=d-2 by (iii). This implies
  
    z_l, 2=pϕ_l+1, 2-ϕ_l, 2≥ p(d-2)-(d-2)-{ϕ_l, 2}≥ 0.

  
  (vi): For l-f < i < k, if ϕ_i, 2=pϕ_i+1, 2, z_i, 2=pϕ_i+1, 2-ϕ_i, 2=0; otherwise, ϕ_i, 2=θ_i, 2-1 and z_i, 2 = pϕ_i+1, 2-(θ_i, 2-1) ≤ p(θ_i+1, 2-1)-(θ_i, 2-1)=u_i, 2-(p-1).

  (vii): This follows directly from the construction of the ϕ̅_j's.
  
  (viii): We break up the proof into three cases.
  
  For l-f < i < k, we only need to check for the case where ϕ_i, j=ϕ_i, j-1-1, since otherwise z_i, j=0. In this case, ϕ_i, j-1 ≤ pϕ_i+1, j and
  
    0 ≤ z_i, j=pϕ_i+1, j-(ϕ_i, j-1-1) ≤ p(ϕ_i+1, j-1-1)-(ϕ_i, j-1-1)=z_i, j-1-(p-1).

  
  For i=k, again, we may assume ϕ_k, j=ϕ_k, j-1-1, then
  
    0 ≤ z_k, j    = pθ_k+1, j-(ϕ_k, j-1-1)
       ≤ p(θ_k+1, j-1-1)-(ϕ_k, j-1-1)=z_k, j-1-(p-1),

  where the second inequality follows from the fact that θ̅_j-1-θ̅_j=E^-1Γ(O_j-1) ≥ 1 by Propositions <ref> and <ref>. 
  
  For i=l, by (iii), we have
  
    z_l, j=pϕ_l+1, j-ϕ_l, j≥ p(d-j)-(d-j)-{ϕ_l, j}≥ 0.

  Finally, z_l, j=pϕ_l+1, j-θ_l, j≤ p(ϕ_l+1,j-1-1)-(θ_l, j-1-1)=z_l, j-1-(p-1).


Proposition <ref> implies that the matrix

    B=[z̅_1-z̅_2, …, z̅_d-1-z̅_d, z̅_d]

is a valid matrix of W_d(N). Let Z=(Z_1, …, Z_d) be the τ-monotonic element in W_d^B(N). We show that (Z) < (O) and hence get a contradiction. 



  §.§.§ Estimation on (Z).
 

For 2 ≤ j ≤ d, define

    Z'_j     := Z_j+Z_j+1+⋯+Z_d,
    
      O'_j     := O_j+O_j+1+⋯+O_d.

Then Γ(Z'_j)=z̅_j and Γ(O'_j)=u̅_j. And weights of Z and O can be expressed as

    (Z)     = N+Z'_2+⋯+Z'_d,
    (O)     = N+O'_2+⋯+O'_d.

To describe these Z'_j, O'_j explicitly, for each 0 ≤ i ≤ f-1, denote

    τ_i(N)=(τ_i, u_i, τ_i, u_i-1, …, τ_i, 1).

We recall that τ_i(N) is defined as the subsequence of the nonincreasing sequence of p-powers in (n), where the exponents of powers in it are congruent to i modulo f. 

Let τ_i, 0=0. Then, by τ-monotonicity, we have

    Z'_j=∑_i=0^f-1∑_s=0^z_i, jτ_i, s,    O'_j=∑_i=0^f-1∑_s=0^u_i, jτ_i, s.

By Proposition <ref> (vii),

    O'_j-Z'_j=∑_i ∈ I( ∑_s=0^u_i, jτ_i, s-∑_s=0^z_i, jτ_i, s),

where

    I={ l, …, f-1, 0, …, k }.

For j=2 and i ∈ I, we have the following:

    
  (1) By Proposition <ref> (iv, v, vi), z_k, 2=u_k, 2+1 and for i ∈ I\{k}, z_i, 2≤  u_i, 2 where “=" holds iff z_i, 2=u_i, 2=0.
    
  (2) τ_f-1, u_f-1, 2=p^a since it is the largest p-power not in (O_1) whose exponent is f-1 mod n. In particular, u_f-1, 2>0 and hence z_f-1, 2<u_f-1, 2 by (1).
    
  (3) Let τ_k, z_k, 2=p^b, then z_k, 2=u_k, 2+1 implies that p^b is the last p-power in τ_k(O_1). By our choice of k, p^b ∈(O_1) ∖(M_1). In particular, p^b<p^a.

With these observations, we have

    O'_2-Z'_2 ≥τ_f-1, u_f-1, 2-τ_k, z_k, 2+∑_i ∈ I\{k, f-1}τ_i, z_i, 2=p^a-p^b+∑_i ∈ I\{k, f-1}τ_i, z_i, 2.
 
Thus

    (O)-(Z)=∑_j=2^d O'_j-Z'_j≥ p^a-p^b+∑_i ∈ I\{k, f-1}τ_i, z_i, 2+∑_j=3^d O'_j-Z'_j.

The next lemma gives a lower bound for ∑_j=3^d O'_j-Z'_j.

 
  Let I={ l, …, f-1, 0, …, k }, then
  
    ∑_j=3^d O'_j-Z'_j>-∑_i ∈ Iτ_i, z_i, 2.




  We note that τ_k, z_k, 2>0 since z_k,2 > 0 by Proposition <ref> (iv). The statement is trivial if z_i,j=0 for all i ∈ I and 3 ≤ j ≤ d. Assuming they are not all vanishing, the statement follows from the following calculation.
  
    ∑_j=3^d O'_j-Z'_j    = ∑_j=3^d ∑_i ∈ I(∑_s=0^u_i,jτ_i, s-∑_s=0^z_i, jτ_i, s)
        > -∑_i ∈ I∑_j=3^d∑_s=0^z_i, jτ_i, s
        > -p∑_i ∈ I∑_j=3^dτ_i, z_i,j
        > -p^2/q∑_i ∈ Iτ_i, z_i,2
       ≥ -∑_i ∈ Iτ_i, z_i,2.

  The first inequality is trivial. The last one follows from the assumption f ≥ 2. For the second inequality, we note that each p-power appearing in the sum ∑_s=0^z_i, jτ_i, s repeats at most p-1 times and the largest term is τ_i, z_i,j, which indicates ∑_s=0^z_i, jτ_i, s < pτ_i, z_i,j. By a similar argument and Proposition <ref> (viii), for all i ∈ I and 3 ≤ j ≤ d, we have τ_i, z_i,j≤ q^-1τ_i, z_i, j-1, thus
  
    ∑_j=3^dτ_i, z_i,j≤ q^-1∑_j=2^d-1τ_i, z_i, j < p/qτ_i, z_i,2.

  This gives the third inequality.


Now we are ready to claim the contradiction, which finishes the proof of Theorem <ref>.


  (Z)<(O).



  We first show τ_f-1, z_f-1,2 < p^a. Assume z_f-1,2>0 since otherwise τ_f-1, z_f-1,2=0. Then τ_f-1, z_f-1,2≤ q^-1τ_f-1, u_f-1,2 because z_f-1, 2≤ u_f-1, 2-(p-1) by Proposition <ref>. Note that τ_f-1, u_f-1,2=p^a as we mentioned earlier, thus τ_f-1, z_f-1,2 < p^a. 

  Putting together (<ref>) and Lemma <ref>, we have
  
    (O)-(Z) > p^a-2p^b-τ_f-1, z_f-1,2.

  Here p^b and τ_f-1, z_f-1,2 are p-powers less than p^a and they are distinct since their exponents fall into different residue classes mod f. We break up the proof into 3 cases.
  
  (1) p ≥ 3: (O)-(Z)>0 since 2p^b+τ_f-1, z_f-1,2<p^a. 
  
  (2) p=2 and b+1<a: 2p^b+τ_f-1, z_f-1,2=p^b+1+τ_f-1, z_f-1,2≤ p^a, thus (O)-(Z)>0. 
  
  (3) p=2 and b+1=a: In this case, we have k+1=l=f-1 and I={0, …, f-1 }.
  By Proposition <ref> (v), u_f-1, 2-z_f-1, 2≥ 2. Hence
  
    O'_2-Z'_2     = (∑_s=0^u_f-1,2τ_i, s -∑_s=0^z_f-1, 2τ_i, s)+∑_i=0^k(∑_s=0^u_i,2τ_i, s -∑_s=0^z_i, 2τ_i, s)
       ≥  p^a + τ_f-1, 1+z_f-1, 2- p^b +∑_i=0^k-1τ_i, z_i, 2
 
  and by Lemma <ref>,
  
    (O)-(Z)     = ∑_j=2^d O'_j-Z'_j 
        >  p^a+τ_f-1, 1+z_f-1, 2-p^b+∑_i=0^k-1τ_i, z_i, 2-∑_i ∈ Iτ_i, z_i, 2
        = p^a+τ_f-1, 1+z_f-1, 2-p^b-p^b-τ_f-1, z_f-1, 2
        = τ_f-1, 1+z_f-1, 2-τ_f-1, z_f-1, 2≥ 0.



Book:Goss-1996, Thakur-2017
amsalpha

