\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\newcommand{\ZZ}{{\mathbb{Z}}}
\newcommand{\CC}{{\mathbb{C}}}
\newcommand{\OO}{{\mathcal{O}}}
\newcommand{\NN}{{\mathbb{Z}_{\geq 0}}}
\newcommand{\FF}{{\mathbb{F}}}
\newcommand{\pp}{\tilde{\pi}}
\DeclareMathOperator{\ord}{ord}
\def\modd#1 #2{#1\ ({\rm mod}\ #2)}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 1cm{\LARGE\bf 
Valuations of $v$-adic Power Sums and Zero \\
\vskip .06in
Distribution for the Goss $v$-adic Zeta Function \\
\vskip .13in
for  $\FF_q[t]$
}
\vskip 1cm
\large
Dinesh S. Thakur\footnote{The author
was supported by NSA grant H98230-08-1-0049.}\\
Department of Mathematics\\
University of Arizona\\
Tucson, AZ 85721\\
USA\\
\href{mailto:thakur@math.arizona.edu}{\tt thakur@math.arizona.edu}
\end{center}

\vskip .2 in
\begin{abstract}
We study the valuation at an irreducible polynomial $v$  of the
$v$-adic  power sum, for exponent $k$ (or $-k$), of  polynomials of a
given degree $d$ in  $\FF_q[t]$, as a sequence in $d$ (or $k$).
Understanding these sequences has immediate consequences, via standard
Newton polygon calculations, for the zero distribution of the
corresponding $v$-adic Goss zeta functions. We concentrate on $v$ of
degree one and two and give several results and conjectures describing
these sequences. As an application,  we show, for example, that the
naive Riemann hypothesis statement which works in several cases, needs
modifications, even for a prime of degree two. In the last section, we
give an elementary proof of (and generalize) a product formula of Pink
for the leading term of the Goss zeta function.
\end{abstract}


\centerline{\it Dedicated to Jean-Paul Allouche on his 60th birthday}


\section{Introduction}

In a previous paper \cite{T09},
we investigated valuation sequences at the infinite place of the
power sums of polynomials in $\FF_q[t]$, with positive and negative
exponents.  We gave 
\begin{itemize}
\item[(i)] a simple recipe to find these;
\item[(ii)] a duality between valuations for positive and negative exponents;
\item[(iii)] a simple recursion in case $q$ was prime; and
\item[(iv)] applications to the zero distribution of the Goss
zeta function \cite{G, G2, T},
giving a cleaner approach to the Riemann hypothesis (due
to Wan and Sheats \cite{W, D, S}) and to the study of the multizeta
values in this case.
\end{itemize}

In this paper, we look at finite places $v$ of 
$\FF_q[t]$ and study the $v$-adic valuations of power sums with the
$v$-factor removed. We give  conjectural formulas for them describing 
very interesting patterns, for $v$ of degree one and two, and
proving full results  in some  special cases. 
We then give applications to the zero distribution 
of the Goss $v$-adic zeta function, showing that 
in the degree-two case, the Riemann hypothesis type 
statement, holding at the infinite degree-one place,  needs 
modification. We also calculate a particular power 
sum, which is a leading term of the Goss zeta, when 
$q$ is a prime, and in particular, give an elementary
proof of (and generalize) Pink's nice product formula for the same when 
$q=2$. 

Patterns of these valuation sequences exhibit symmetries remarkably
similar to those occurring in several papers of Allouche, Shallit,
Mend\`es France, Lasjaunias, etc., as well as those found by the author
for continued fractions for analogs of $e$, Hurwitz numbers, and  some
algebraic quantities.


\section{Power sums}
\subsection{Notation}
$$\begin{array}{rcl}

\ZZ&=&\mbox{\{integers\}}\\
\ZZ_+&=&\mbox{\{positive integers\}}\\
\ZZ_{\geq 0}&=&\mbox{\{nonnegative integers\}}\\
q&=&\mbox{a power of a prime} \ p, \ q=p^f\\
A&=&\FF_q[t]\\
A+&=&\mbox{\{monics in $A$\}}\\
A_{d}+&=&\mbox{\{monics in $A$ of degree $d$\}}\\
%A_{<d}+&=&\mbox{\{monics in $A$ of degree less than $d$\}}\\
K&=&\FF_q(t)\\
K_v&=&\mbox{completion of $K$ at the place $v$ of $K$}\\
C_{v}&=& \mbox{the completion of an algebraic closure of}\  K_{v}\\
\mbox{[$n$]}&=&t^{q^n}-t\\
d_n&=&\prod_{i=0}^{n-1}(t^{q^n}-t^{q^i})\\
\ell_n&=&\prod_{i=1}^n(t-t^{q^i})\\
\ell(k)&=& \mbox{sum of the digits of the base $q$ expansion of $k$}\\
\deg&=&\mbox{function assigning to $a\in A$ its degree in $t$, $\deg(0)=-\infty$}
\end{array}
$$

While in the notation above, we let $v$  be any place of $K$,  
we use $v$ for the finite places (i.e., those corresponding to 
irreducible polynomials of $A$), and we use $\infty$ for the 
usual infinite place of $K$ (i.e., the place corresponding to the valuation 
coming from the degree in $t$). 

\subsection{Power sums}



For  $k\in \ZZ$ and $d\in \ZZ_{\geq 0}$, and $v$ a prime of $A$, write 
$$S_d(k):=
\sum_{a\in A_d+}\frac{1}{a^k}\in K,\ \ \ S_{d,
v}(k):=\sum_{\begin{subarray}{c}a\in A_d+\\(v,
  a)=1\end{subarray}}\frac{1}{a^k}\in K.$$



\subsection{Goss Zeta and $v$-adic zeta} For $k\in \ZZ$,  put
$$\zeta(k):=\sum_{d=0}^{\infty} S_d(k)\in K_{\infty}, \ \ \ 
\zeta_v(k):=\sum_{d=0}^{\infty}S_{d, v}(k)\in K_v.$$

More generally, we have two-variable Goss zeta functions defined 
as follows. Define exponent spaces  $S_{\infty}:= C_{\infty}^*\times \ZZ_p$ and
$S_v:= C_v^*\times \lim \ZZ/(q^{\deg v}-1)p^j\ZZ.$ 

For $s=(x, y)\in S_{\infty}$, 
put $$\zeta(s)=\sum_{d=0}^{\infty} x^d\sum_{a\in A_{d}+}(a/t^d)^y\in C_{\infty}.$$
Note that for $y$ an integer, the coefficient of the $d$-th term in this 
power series in $x$ is nothing but $S_d(-y)t^{-dy}$, hence $\zeta(k)$ 
as above is $\zeta(t^{-k}, -k)$. 

For $s=(x, y)\in S_v$, put $$\zeta_v(s)=\sum_{d=0}^{\infty}x^d\sum_{\begin{subarray}{c}a\in A_d+\\
 (a, v)=1\end{subarray}}a^y\in C_v.$$
Note that for $y$ an integer, the coefficient of the $d$-th term in this power 
series is nothing but $S_{d, v}(-y)$, hence $\zeta_v(k)$ above is $\zeta(1, -k)$. 

See \cite{C, G, T} and references there for more details on these 
interpolations,  properties. 

We begin with definitions and basic results on the valuations of these power sums. 

\subsection{Valuations}

For a finite prime $v$ of $A$, and the usual place at infinity, put 
$$s_d(k):=\mbox{val}_{\infty}(S_d(k))=-\deg (S_d(k)), \ \ \ v_d(k)
:=\mbox{val}_v(S_{d, v}(k)).$$

\subsection{Valuation sequence at $\infty$}
In this paper, we concentrate on valuations at finite primes, but 
for comparison only, we mention some results on valuations at infinity, 
and give some remarks. 

Previously \cite{T09}, we described interesting behavior of $s_d(k)$.
For example, when $q$ is a prime, we proved \cite[Thm.
1]{T09} $$s_d(k)=s_{d-1}(s_1(k))+s_1(k) =\sum_{i=1}^{d} s_1^{(i)}(k),$$
where $s_1^{(i)}$ is the $i$-th iteration of $s_1$.  There are several other formulas, 
and applications in \cite{T09}, including Riemann hypothesis type 
zero-distribution results for the Goss two-variable zeta function for 
the place at infinity.  

\subsection{Remarks}

\begin{enumerate}
\item 
For non-prime $q$, $s_d(k)$ is not even determined by $s_1(k)$.
Example: for $q=4$, $s_1(75)=s_1(93)=96$, whereas $s_2(75)=348$ and
$s_2(93)=480$.  
For general $q$,  \cite[Thm.  2]{T09} gives a 
sort of `duality' connection between the values at positive and negative $k$, linking
values at $-k$ and $q^n-k$ under certain conditions.
An example dual to the one above is $q=4$, $s_1(-181)=s_1(-163)= -160$ and $s_2(-181)=
-164$, whereas $s_2(-163)$ is infinite.


\item The recursion above when $q$ is a prime and the 
duality for $s_d(k)$ for general $q$ 
\cite[Thm. 2]{T09} 
also gives a fast way of calculating these valuations
at positive $k$. Note that the case of  
negative $k$ (even when $d=1$) is a much easier polynomial calculation than 
rational calculation at positive $k$. 

\item We do not know whether there is any duality of
actual power sums $S_d(k)$ or
zeta values $\zeta(k)$ themselves, giving some kind of functional 
equation.  For the two-parameter special family $k=q^n-q^r$, 
with $r<n$, we have the
following nice relation, for $n-r\geq d$, 
 $$S_d(q^r-q^n)/S_d(q^r)=(q^{n-r}!)^{q^r}/(q^{n-(r+d)}!)^{q^{r+d}},$$ 
using the Carlitz factorial \cite[p.\ 102]{T} and Carlitz's
results (see \cite[Sec.5.6]{T}).
While all the factorial-gamma values are monomials in $[i]$'s, the ratios 
of power sums for dual exponents are not these kinds of monomials for general 
$k$, so we do not know what, if any, a correct generalization of such
phenomena would be. 

\item In \cite[2.2.5 (ii)]{T09}, I showed that if $S_d(k_1)=S_d(k_2)$ 
holds for $d=1$, then it holds for all $d$. While true, it should 
be pointed out that, in addition to the proof there,  
in case of positive $k$, it is vacuously true, 
because \cite[2.3]{T09} shows that $S_d(k)\ell_d^k$ is a polynomial 
congruent to $1$ (mod $t$), so the equality above for any $d$ 
and $k_2>k_1>0$ would imply $\ell_d^{k_2-k_1} \equiv \modd{1} {t}$,
whereas it is divisible by $t$.  On the other hand, 
interestingly,  the statement  is true, when $q$ is prime,  with $S_d$ replaced by $s_d$ by 
\cite[Thm.\ 1]{T09}, and not in general as we saw above, for example. 
(In my editing gaffe, these motivating remarks were  inadvertently 
left off in \cite{T09}). 

\end{enumerate}


\subsection{Valuation sequence at $v$}
We have $v_d(k)\geq 0$ for all $k\in \ZZ$, with it being infinite 
when the corresponding power sum is zero. 
Note $v_d(pk)=pv_d(k)$, so without loss of generality, we can restrict to 
$k$ prime to $p$. 

Another simple remark is that  two primes  
related by automorphisms 
$t\rightarrow t+\theta$, ($\theta\in \FF_q$) of $A$ (e.g., any two degree-one
primes) give the same 
valuation sequence. 




\subsection{Non-vanishing of power sums}
The power sums  $S_{d, v}(k)$ are non-zero for $k>0$, as can be seen by
choosing a monic prime $P$, unequal to $v$ and of degree $d$ (which can be done unless
$q=2$, $v$ is of degree $2$ and $d=2$, which we can check separately),
and noticing that except for $a=P$ term, all other terms in
the power sum $S_{d, v}(k)$  have valuation $0$ at $P$.

For $k\leq 0$, these power sums can be zero.  In fact, $S_{d,v}(k)$  is 
zero if $d>\ell(-k)/(q-1)+\deg(v)$, by the Carlitz result 
\cite[Cor. 5.6.2]{T} that 
$S_d(k)=0$ if $d>\ell(-k)/(q-1)$ (with the converse of the latter 
holding also for $q$ prime). 
 We have not investigated the exact 
conditions corresponding to the  non-vanishing. For a similar necessary 
and sufficient condition for vanishing of $S_d(k)$, for general 
$q$,  due to Carlitz, Sheats and B\" ockle, 
see \cite[A5]{T09} and \cite{B12}.



\section{Some evaluations and simple bounds for $k>0$} 
\label{sec3}

We recall \cite[Sec.\ 5.6]{T} the formulas for power sums and valuations of $[n]$ and $\ell_n$. 

$$S_d(r)=\frac{1}{\ell_d^r},\ \ 0<r\leq q,  \ \ \ S_d(q+1)=\frac{[1]-[d]^q}
{[1]\ell_d^{q+1}}.$$

Note that $[n]$ is the product of all monic irreducible polynomials of degree
dividing $n$. When $q=2$ and $v=t^2+t+1$, we have 
$$[d]=v^{2^{d-1}}+v^{2^{d-2}}+\cdots+v, \ \ \ \mbox{or}\  [d]=v^{2^{d-1}}+\cdots +v^2+v+1$$
according to whether $d$ is even or odd.

Hence, the valuation of $[n]$ (resp., $\ell_n$)
at a degree one prime is $1$ (resp., $n$), whereas 
at the degree $2$ prime $v$, when $q=2$, the valuation 
is $1$ or $0$ according as $n$ is even or odd (resp., $\lfloor n/2\rfloor$).


\begin{claim}
If  $v$ is a prime of degree $1$, 
then $v_d(1)=q^d-(d+1)$.
\end{claim}

\begin{proof} Without loss of generality, using automorphisms 
$t\rightarrow t+\theta$
($\theta\in \FF_q$) of $\FF_q[t]$ which preserve sign, we
may assume that $v=t$. Then
$$S_{d, v}(1)=\frac{1}{\ell_d}-\frac{1}{t\ell_{d-1}}=\frac{t-(t-t^{q^d})}
{t\ell_d}.$$
\end{proof}

\begin{claim}
If $q=2$, $v$ is a prime of degree $1$, then
$v_d(3)=2^{d+1}-3d-1$, for $d\geq 1$. 
\end{claim}

\begin{proof} Since  $S_d(3)=(1+[d]^q/[1])/\ell_d^3=[d+1]/([1]\ell_d^3)$, 
we have $S_{d, v}(3)=S_d(3)-S_{d-1}(3)/t^3 =(t^{2^{d+1}}+t^{2^{d+2}-3})/([1]\ell_d^3)$. 
\end{proof}

\begin{claim}
If $q=2$, $v$ is the  prime of degree $2$, namely 
$v=t^2+t+1$, then $v_d(1)=2^{d-1}-\lfloor (d+1)/2\rfloor$, for $d\geq 1$. 
\end{claim}

\begin{proof} Proceeding as before, we have 
$$S_{d, v}(1)=\frac{v+[d][d-1]}{v\ell_d}$$
so the valuation of the denominator is $1+\lfloor d/2\rfloor$. 
Let us write $M=v^{2^{d-2}}+\cdots +v^2+v$ temporarily, so that 
$M^2+M=v^{2^{d-1}}+v$. The numerator is $v+(v^{2^{d-1}}+M)(M+1)=v^{2^{d-1}}M$
or $v+(v^{2^{d-1}}+M+1)M=v^{2^{d-1}}+v^{2^{d-1}}M$ 
according as whether $d$ is even or odd, so its valuation is $2^{d-1}+1$ or 
$2^{d-1}$, respectively. 
\end{proof}

\begin{claim}
If $q=2$, $v=t^2+t+1$, then $v_d(3)=
2^d-3\lfloor d/2\rfloor +(-1)^{d-1}$, for $d>1$. We have 
$v_1(3)=1$, $v_0(3)=0$.  
\end{claim}

\begin{proof} We have 
$$S_{d, v}(3)=\frac{[d+1]v^3+[d-1]^4[d]^3}{v^3[1]\ell_d^3}.$$
The valuation of the denominator is $3+3\lfloor d/2\rfloor$. The valuation 
of the numerator is $2^d+2$ for $d$ even, and $2^d+4$ for $d$ odd, by 
a straight calculation (we omit the details) as in the proof above.
\end{proof}

More generally, we have the following {\it conjectural recipe} guessed
 from a small 
numerical data computed:

If  $q=2$, $v=t^2+t+1$, $d>1$, 
$$v_d(2^n-1)=2^{n+d-2}-(2^n-1)\lfloor d/2\rfloor +(-1)^{d-1}, 
\ \mbox{if $n$ is 
  even}, $$
and 
$$v_d(2^n-1)=2^{n+d-2}-(2^n-1)\lfloor d/2\rfloor-\lfloor (d+1)/2\rfloor+\lfloor 
d/2\rfloor, \ \mbox{if $n$ is odd}.$$

\subsection{Trivial lower bound} 
\begin{claim}
If $k>0$, 
 and $d>m\deg(v)$, then $v_d(k)\geq m$. 
\end{claim}

\begin{proof} The terms in the sum 
$S_{d, v}(k)$ can be grouped by orbits $1/(n+\theta v^m)^k$, as $\theta$ 
runs through elements of $\FF_q$. The terms of each orbit 
add to zero (mod $v^m$).
\end{proof}

\subsection{Trivial upper bound} 
\begin{claim}
For $k>0$, $d\geq \deg(v)$, 
we have 
$v_d(k)\leq dk(q^d-q^{d-\deg(v)}-1)/\deg(v)$. 
\end{claim}

\begin{proof} By definition $S_{d, v}(k)$ is the sum of $q^d-q^{\deg(v)}$ terms of 
the form $1/n^k$ with $n$ monic and prime to $v$, so with the common denominator the product of $n^k$'s, the numerator is sum of products of 
$q^d-q^{d-\deg(v)}-1$ terms of degree $dk$. 
\end{proof}

\subsection{Congruences and periodicity} In contrast to $(\ZZ/p^n)^*$ 
which is cyclic for odd prime $p$, the analog $(A/v^n)^*$ is far from cyclic in 
general, when $n>1$. If $v$ has degree $D$, then $(A/v^n)^*$  has order 
$(q^D-1)q^{D(n-1)}$, but it has exponent 
$$e_n=(q^D-1)p^{\lceil \log_p(n)\rceil}.$$ So 
$S_{d, v}(k)\equiv \modd{S_{d, v}(k+me_n)} {v^n}$. In particular, 
$$\mbox{if } v_d(k)<n, \mbox{ then } v_d(k)=v_d(k+me_n), \ m\in\ZZ.$$
(Hence for any fixed $d$, $v_d(k)$ can be small even for large $k$. )

 We will see 
applications resulting in nice patterns below. Also note that 
as $m$ can be negative, we can  replace calculation with rational functions
to get $v_d(k)$ at positive $k$, by easier  calculation with polynomials
to get it from  negative $k$. 


We know \cite[Thm. 2]{T09} says that $s_d(q^n-k)-s_d(-k)=dq^n$, if
$s_d(-k)\neq 0$ and $q^n>k>0$.  Using the congruence idea at the
infinite prime together with a switching trick, let us now give
another proof of this equality claimed, but using a slightly stronger
hypothesis that $s_d(-k)\neq 0$ and $q^n>k\ell(k)/(q-1)$.

Let us temporarily denote by $w$ the prime $1/t$ of $\FF_q[1/t]$. 
We have 
$$S_d(-k)=t^{dk}\sum (1+\frac{f_{d-1}}{t}+\cdots +\frac{f_0}{t^d})^k, \ \ 
S_d(q^n-k)=t^{dk-dq^n}\sum (1+\cdots )^{k-q^n}.$$
Now the first sum  is (term-by-term) congruent modulo 
$w^{q^n}$ to the second sum. Since the first sum is non-zero, we get 
a trivial upper  bound $dk$ on its valuation at $w$. On the other hand, 
we know by \cite[5.6.2]{T} that $d\leq \ell(k)/(q-1)$, because $s_d(-k)\neq 0$. 
Hence the claim follows as before. 







\section{Recipes and inter-relations for degree $1$ primes, 
  $k\in\ZZ$}

Let us write $a\oplus b\oplus c+\cdots$ to denote the sum
$a+b+c+\cdots$, where this sum has no carry over base $p$.
In Theorem~\ref{thm1}
below, by the ``greedy algorithm'' we mean first choosing among
valid decompositions with $m_d\leq \cdots \leq m_1$, the least $m_d$,
then among these, the least $m_{d-1}$, and so forth.

\begin{theorem}
\begin{enumerate}
\item[(i)] Let $k$ be negative and $m=-k$. Then  either 
$s_d(k)=-dm+\min(m_1+2m_2+\cdots +dm_d)$, where 
$m=m_0\oplus \cdots \oplus m_d$, $m_i\geq 0$, and for $i\geq 1$, 
$(q-1)$ divides $m_i>0$, or $s_d(k)$ is infinite, if there is no 
such decomposition. When the decompositions exist, the minimum 
is uniquely given by greedy algorithm. 

\item[(ii)] Let $k$ be positive. Then $s_d(k)=dk+\min(m_1+\cdots +dm_d)$, 
with $(k-1)+m=(k-1)\oplus m$ and 
$m=m_1\oplus\cdots\oplus m_d$, with $m_i$ positive and divisible by 
$q-1$. The minimum is uniquely given by the greedy algorithm. 

\item[(iii)] Let $k$ be negative and $m=-k$. Let $v$ be a prime of $A$ of
degree one.  Then either $v_d(k)=\min(m_1+\cdots +dm_d)$, where
$m=m_0\oplus\cdots \oplus m_d$, where $(q-1)$ divides $m_i>0$ for
$0<i<d$, and $q-1$ divides $m_0\geq 0$; or $v_d(k)$ is infinite, if
there is no such decomposition.  When the decompositions exist, the
minimum is uniquely given by the greedy algorithm. (We
see immediately that if $r$  is the least non-negative residue of $m$ 
(mod $q-1$), then the minimal $m_d$ is the least sum of $p$ powers 
chosen from the $p$-expansion of $m$ which is $r$ (mod $q-1$). If $q=p$ a prime, then 
it is just the sum of the least $r$ of the $p$ powers chosen from the expansion, because 
$p^n$ is $1$ (mod $q-1$) then. ) 

\item[(iv)] Let $k$ be positive. Let $v$ be a prime of $A$ of degree one. 
Then $v_d(k)=\min(m_1+\cdots + dm_d)$, with
 $(k-1)+m=(k-1)\oplus m$, $m=m_1\oplus\cdots m_d$, 
and $(q-1)$ divides $m_j>0$ for $j<d$ and $(q-1)$ divides $k+m_d$. 
The unique minimum is given by the greedy algorithm. 
\end{enumerate}
\label{thm1}
\end{theorem}

\begin{proof}
Part (i) follows from results of Carlitz, Diaz-Vargas, Sheats 
as explained and referenced in \cite[5.8]{T} or \cite[Sec.\ 4]{T09}. 
Part (ii) is proved in \cite[Sec.\ 4]{T09}. The parts (iii) and (iv) 
follow by exactly the same arguments, once we note a crucial difference 
as follows. First consider negative $k=-m$, then we have 
$$S_d(k)=\sum_{f_i\in\FF_q}(t^d+f_{d-1}t^{d-1}+\cdots +f_0)^{m}=
\sum {m\choose m_0, \cdots, m_d}(t^d)^{m_d}\cdots (f_0)^{m_0}, 
$$
whereas for $v=t$, $S_{d, v}(k)$ is given by exactly the same sum,
except that the condition $f_0\neq 0$ is added and rather than looking
at highest power of $t$ present in the answer, we now look at the
lowest power.  
The parity and positivity conditions come from the well-known fact that
$\sum f^n$, (where $f$ runs through elements of $\FF_q$ and 
$n$ is a positive integer) is $-1$ or $0$, according as 
whether $n$ is divisible by $q-1$ or not. The carry over 
conditions come from Lucas' theorem that the binomial coefficient 
above is non-zero exactly when there is no carry.
Hence our assertions follow easily if the minimum is unique. 
This is the hard part, proved in Sheats \cite{S} in general (and by 
Diaz-Vargas \cite{D} for much easier case of prime $q$). 
So (iii) follows similarly by reduction to the Sheats
minimization theorem and then (iv) is deduced exactly the same way as
in the proof of \cite[Theorem 1, Sec.\ 4]{T09}.
\end{proof}


\begin{corollary}
Let $v$ be a prime of degree one. 

\begin{itemize}
\item[(i)]
Let $k$ be positive. Then $v_{d+1}(k)=s_d(k)-dk$ if $q-1$ divides 
$k$. 

\item[(ii)] Let $k$ is negative. Then $v_{d+1}(k)=s_d(k)-dk$ if $q-1$ divides 
$k$ and $s_d(k)$ is finite. 

\item[(iii)]
If $q-1$ divides $k$, then $v_d(k)$ is also divisible by $q-1$. 

\item[(iv)]
If $q$ is prime and $k$ is divisible by $q-1$, then
$v_{d+1}(k)=v_d(v_2(k)+k)+dv_2(k)$. 

\end{itemize}
\label{cor2}
\end{corollary}

\begin{proof}
Part (i) (resp., part (ii)) follows from comparing (ii)
and (iv) (resp., (i) and (iii)) of Theorem~\ref{thm1}.
Part (iii) follows from (i) and (ii) and the fact 
\cite[Thm.\ 6, Thm.\ 14]{T09} that $s_d(k) \equiv \modd{dk} {q-1}$.
Part (iv) follows from
(i), (ii) and the fact \cite[Thm.\ 1]{T09} that for $q$ prime, we have
$s_d(k)=s_{d-1}(s_1(k))+s_1(k)$.
\end{proof}

Another direct way to prove Corollary~\ref{cor2} is as follows. 
For $k$ divisible by $q-1$, we have  
$$t^{-dk}S_d(k)=\sum (1+f_1/t+\cdots +f_0/t^d)^{-k}=\sum_{i=0}^dS_i'(k),$$
where we temporarily write $S_d'$ for the power sum $S_{d, v}$ for 
$A=\FF_q[1/t]$ for its degree-one finite prime $1/t$. Replacing $t$ 
by $1/t$, and telescoping, we see that $v_{d+1}(k)$ is $s_d(k)-k$ 
(as it is greater than  $s_{d+1}(k)-(d+1)k$, by 
the last paragraph in the proof of \cite[Theorem 4]{T09}, combined 
with $s_1(k)>k$). 

\subsection{Remarks} 

\begin{enumerate}
\item By part (iii) of Corollary~\ref{cor2}, the recursion in (iv) can
  be continued, so that $v_2(k)$ determines $v_d(k)$, for $d\geq 2$, 
  for a prime $v$ of degree one.  

\item All parts no longer hold if we drop the divisibility condition. 

\item The second proof mentioned above 
is achieved by developing the ideas 
of Wan \cite{W} and Goss \cite[Prop.\ 9]{G2}  further.

\end{enumerate}

\section{$v_d(k)$ when $q$ is a prime, $v$ is of degree $1$, and $k<0$}

\begin{theorem}
Let $q=p$ be a prime, $v$ a prime of $A$ of degree one and $-m=k<0$. 
Write $m=\sum_{i=1}^{\ell}p^{e_i}$, with $e_i$ monotonically increasing and 
with not more than $p-1$ of the consecutive values being the same
(i.e., consider the base $p$-digit expansion sequentially one digit at a time).
Also, let $r$ be the least non-negative residue of $m$ (mod $q-1$). 
 Then $v_d(k)$ is infinite if $\ell < (p-1)(d-1)+r$, and otherwise 
$$v_d(k)=d\sum_{s=1}^r p^{e_s} +\sum_{j=1}^{d-1}j\sum_{s=1}^{p-1}p^{e_{(d-1-j)(p-1)+r+s}}.$$
\label{thm3}
\end{theorem}

\begin{proof}
Note that $p^i \equiv \modd{1} {q-1}$ when $q$ is prime.  Hence $p-1$ powers 
together give divisibility by $q-1$. Hence the recipe in (iii) of 
the Theorem~\ref{thm1} simplifies and 
has for the minimum the choice 
$m_d$ being the sum of the $r$ least $p$ powers from the base $p$ expansion of $m$, and 
$m_{d-1}, \cdots, m_1$ obtained by picking $p-1$ digits 
from the base $p$ expansion of $m-m_d$ starting from the lowest 
digits (and dumping the rest of the expansion, if any, into $m_0$). 
\end{proof} 

Note that it looks even simpler for $q=2$, so that $r=0$ and inner
sums are singletons, and also that in this case $v_1(k)=0$, $v_2(k)$
is, in fact, the valuation of $k$ at $2$.

\section{$v_d(k)$ when $q=2$, $v$ is of degree $1$, and $k>0$}

First note that $v_d(2k)=2v_d(k)$, so we will focus on the case where $k$
is odd. 

Next, observe that $v_1(k)=0$ for all $k$ and $v_2(k)=1$ for all odd $k$. 

From  \cite[Sec.\ A.2 (1)]{T09} and duality part (i) of Corollary~\ref{cor2}, we see that
$$w_n: =v_d(2^n-1)=2^{d+n-1}-2^nd+(d-1).$$

We define sequence $f_n$ (it is  $v_{n-3}(5)-v_{n-3}(1)$) by 
$$f_0=0 \mbox{ and } f_n=2f_{n-1}+4n.$$

Here is the recipe: For a given $d$, we describe the sequence of
$v_d(k)$ with $k$ odd, so that the $n$-th entry will correspond to
$k=2n-1$ and thus $w_n$ is $2^{n-1}$-th entry. Let $X_n$ be the vector
of the first $2^{n-1}-1$ entries, and write $X_{n+1}=X_n, w_n, X_n'$, 
in two halves. 
In other words, the whole sequence is of the form $X_1, w_1, X_1',
w_2, X_2', w_3, X_3',\cdots$ or equivalently, 
$$X_n, w_n, X_n', w_{n+1}, \cdots, $$

\begin{theorem} The second half 
$X_n'$ is obtained from the first half $X_n$ by adding $2^{n-2}f_m$ to the 
entries with index (i.e., $(k+1)/2$) having the base-$2$ expansion 
$$\sum_{i=w}^{n-2}b_i2^i, \ b_w\neq 0, \mbox{with exactly $d-3-m$ of 
the $b_i$'s zero},$$
where $1\leq m\leq d-3$. 
\label{thm4}
\end{theorem}

\begin{proof}
We replace $d$ by $d+1$ for convenience. We then need to prove 
$v_{d+1}(k+2^n)-v_{d+1}(k)=2^{n-2}f_m$. 
  By using the duality (i) of Theorem~\ref{thm3}, we are reduced to
  proving $s_d(k+2^n)-s_d(k)=d2^n+2^{n-2}f_m$, for $2^n-1>
  k$ odd and $m$ as in Theorem~\ref{thm4}, but with $d$ replaced by $d+1$. 
By   \cite[3.3]{T09}, we have
$$s_d(k)-dk=d \cdot 2^{e_0}+\cdots +1 \cdot 2^{e_{d-1}},$$ 
where we  write the base $2$ expansion of $k$ as 
$$k=\cdots 0_{e_{t+1}}0_{e_t}1\cdots 10_{e_{t-1}}1\cdots1\cdots 0_{e_2}
1\cdots 10_{e_1}1\cdots 1_{e_0}0\cdots 0.$$
Since, for us, $k$ is odd, less than $2^n$,  (with $n=e_t+r$, $r\geq 0$) 
$k+2^n$ has expansion of the form 
$$\cdots 0_{e_{t+r}} 1 0_{e_{t+r-1}}\cdots 0_{e_t}1\cdots 
10_{e_{t-1}}1\cdots1\cdots 0_{e_2}
1\cdots 10_{e_1}1\cdots 1_{e_0}.$$ Observe that
$(d+1)-3-m=t+r-2$,  by counting the relevant
zeros in the expansion of $(k+1)/2$. If $m\leq 0$, the relevant
$e_i$'s are the same for $k$ and for $k+2^n$, and hence the left side
of the first formula is $d2^n$, which agrees with the right side
as $f_m=0$ then. Now we proceed by an induction on $m$. Now the
$e_i$'s which are different are $e_{d-m}, \cdots, e_{d-1}$ which
are $n, \cdots , n+(m-1)$ for $k$ whereas $n+1, \cdots , n+m$ for
$k+2^n$ resulting in the difference $X_m:=(2^{n+m}+2 \cdot 2^{n+m-1}+\cdots
+m2^{n+1})-(2^{n+m-1}+\cdots +m2^n)$. Hence
$X_{m+1}-2X_m=(m+1)\cdot 2^n=4 \cdot 2^{n-2}(m+1)$, matching the recursion for
$2^{n-2}f_m$'s.
\end{proof} 

\begin{remark}
Using duality, we have converted 
the recursion in $d$ for valuations 
at infinity into proving nice fast `doubling' pattern for a fixed $d$. 
\end{remark}


\subsection{Examples} For $d\leq 3$, $X_n'=X_n$, so there is block
repetition after new entries $w_n$. The case $d=0$ (resp., $d=1$)
corresponds to vectors with all entries zero (resp, one), as
mentioned above.  On the other hand, for $d=3$, we get
$$\overline{4}, \overline{6}, 4, \overline{10}, 4, 6, 4, \overline{18}, 
4, 6, \cdots, 4, \overline{34}, 4, 6, 4, \cdots, $$
where the over-lined entries are the $w_n$'s. 

For $d=4$, the quantity
$X_n'$ is obtained by keeping its first half the same and 
adding $2^n=2^{n-2} \cdot 4$ to the half-way entry,
half of the next half-way, etc.,
entries (i.e., $\sum_{w}^{n-2}2^i$-th entries).  

More generally, $X_n$ and $X_n'$ share their first $X_{n-(d-3)}$ part. 
This also follows  another way from 3.3. 




\section{When $q=3$, $v$ is of degree $1$, and $k>0$}

We list valuation sequence $v_d(k)$ for $k$ not divisible by $3$. 

For $d=1$, $v_d(k)$ is zero for even $k$ and $1$ for odd $k$. 
So the sequence is periodic of period $1, 0, 0, 1$  of length $4$, when  only $k$ not divisible by $3$ are used. 

\subsection{Conjectural recipe for $d=2$}

The valuation sequence is of the form $X_1, a_1, X_2, a_2, X_3, a_3,
\cdots$ where

(i) $X_1=X_{3n}=X_{3n+1}=[6, 4, 2, 14, 12, 10, 2, 8, 6, 4, 2]$, 

(ii) $X_{3n+2}$ is the same as $X_1$ except $a_{3n+1}-a_{3n+2}$ is added to 
fourth, fifth and sixth terms of $X_1$ to get the corresponding entries, 

(iii) The $a_n$'s (which correspond to $k=17+18(n-1)$) look like
$3^r+3^s+2$, with $r\geq s\geq 2$ (and $a_{3m+2}=20$, so that $r=s=2$
and for $n$ of the form $3m+1$, we have $s=2$). More precisely, we
describe the full sequence $[a_1, a_2, \cdots]$ as follows:
$a_{3^n}=3^{n+3}+3^{n+2}+2$, $a_{2 \cdot 3^n}=3^{n+2}+3^{n+2}+2$, the block
between $a_{2 \cdot 3^n+1}$ to $a_{3^{n+1}-1}$ is exactly the block between
$a_1$ to $a_{3^n-1}$, whereas you get the block between $a_{3^n+1}$ to
$a_{2 \cdot 3^n-1}$ by taking the block between $a_1$ to $a_{3^n-1}$ and
replacing the entries $3^{n+2}+3^k+2$ by the new entries
$3^{n+3}+3^k+2$.

So the sequence is $X_1$ followed by $38$ followed by 6, 4, 2, 32, 30, 28, 
2, 8, 6, 4, 2, followed by 20, $X_1$, 110, $X_1$, 92, followed by 
6, 4, 2, 86, 84, 82, 2, 8, 6, 4, 2, followed by 20, $X_1$, 56, $X_1$, 38, 
....



\section{When $q=4$, $v$ is of degree $1$, and $k>0$}

Here is the {\it conjectural recipe} for $d=1$: 

We describe the sequence  $v_1(k)$ with $k$ odd, 
so that the $n$-th entry will correspond to $k=2n-1$ and thus $w_n$ is 
$2^{n-1}$-th entry: 

The whole sequence is limit of vectors $X_n$ (of increasing sizes with
initial portion being $X_{n-1}$) with 

(i) $X_1$ being $[2, 0, 1, 8, 0, 1]$ and

(ii) $X_n$ consisting of $X_{n-1}$ followed by $X_{n-1}'$, where the
entries of $X_{n-1}'$ are the same as that of $X_{n-1}$, except one entry is
 changed as follows: If $n$ is odd, change the $k=2^n-1$-th entry (which is 
$2^n$) to $2^{n+2}$ and if $n$ is even, change $k=2^{n+1}-1$-th entry 
(which is $2^{n+1}$) to $2^n+1$. 

So the sequence is $X_1$ followed by 2, 0, 1, 5, 0, 1, 2, 0, 1, 32, 0, 1, 
2, 0, 1, 5, 0, 1, $X_1$, ....




\section{When $q=2$, $v$ is of degree $2$, and $k>0$}

For a given $d$, we describe the sequence of $v_d(k)$ with $k$ odd, 
so that the $n$-th entry will correspond to $k=2n-1$. 

By definition, it is easy to see that $v_1(k)=1$ or $0$, respectively,
and $v_2(k)=0$ or $1$, respectively, according to whether $k$ is divisible by
$3$ or not. Let us check this for $d=1$: the numerator of
$1/t^k+1/(t+1)^k$ is congruent to
$t^k+(t+1)^k\equiv t^k+(t^2)^k\equiv t^k(1+t^k)$
modulo $v$, but $t^{3m}\equiv 1$ and $(t^{3m}+1)/(v(t+1))\equiv
t^{3m-3}+t^{3m-6}+\cdots +1\equiv m\not\equiv 0$ (mod $v$) (as $m$ is 
odd). 

Now we fix  $d\geq 3$, so it will be dropped from the notation sometimes.

We write the  sequence in the form $X_1, w_1, X_1', w_2, X_2', w_3,
X_3',\cdots$ where $X_{n+1}=X_n, w_n, X_n'$. In other words, 
For every $n$, we write the sequence in the form 
$$X_n, w_n, X_n', w_{n+1},  \cdots,  $$ where 
$X_n$ and $X_n'$ are vectors of entries of length $3 \cdot 2^{n-1}-1$, with
$X_n$ containing entries (odd $k$'s) from $v_d(1)$ to $v_d(3 \cdot 2^n-3)$
and $w_n=v_d(3 \cdot 2^n-1)$.  We can further subdivide $X_n$ in `thirds'.
More precisely, $X_n=(A_n, B_n, C_n)$ with $A_n$ consisting of first
$2^{n-1}$ entries, namely for (odd) $k=1$ to $k=2^n-1$, i.e. those 
with at most $n$ (base $2$) digits, with $B_n$ consisting of entries 
with $k$ from $2^n+1$ to $2^{n+1}-1$, i.e., with $n+1$ digits and with 
$C_n$ consisting of entries with $k$ from $2^{n+1}+1$ to $3 \cdot 2^n-3$, 
i.e. with those entries in $X_n$ with $k$ of $n+2$ digits. 
We write $X_n'=(A_n', B_n', C_n')$ in the obvious fashion. 

Then as we have already proved in Section~\ref{sec3}, we have  

\medskip

\noindent (i) {\bf Initial value} $X_1=[2^{d-1}-\lfloor (d+1)/2\rfloor, 2^d+(-1)^{d-1}-3\lfloor d/2\rfloor]$,

\medskip

Here is the {\it conjectural recipe} for  the rest: 

\medskip

\noindent (ii) {\bf The sequence $w_n=w_{n, d}$} 
For $d$ odd, put 
$$w_1=2^d-(5d-1)/2, \ \ w_{n+1}=2w_n-(d-1)/2,$$
so that $w_{n, 1}=0$, put $w_{n, 2}=1$, and for $d>2$ even, put  
$$w_1=2^d+6-5d/2, \ \ w_{2n}=2w_{2n-1}-d/2+5, \ \ \ 
w_{2n+1}=2w_{2n}-4-d/2. $$

We now give conjectural description of the value of 
$$t_k:=
t_{k, n, d}:=v_d(k+3 \cdot 2^n)-v_d(k)$$ depending on whether 
$k$ belongs to $A_n, B_n, C_n$, respectively: 

\medskip

\noindent (iii) {\bf Description of $A_n$ to $A_n'$ transition}: 
$t_k=v_{d-i}(2^{n+2}-1)-v_{d-i}(2^n-1)$ when  $k$ has
$n-i$ ones, with $0\leq i\leq d-3$, otherwise $t_k=0$. 

In other words, add $v_{d-i}(2^{n+2}-1)-v_{d-i}(2^n-1)$ (which is
$3 \cdot 2^n(2^{d-i-2}-\lfloor (d-i)/2\rfloor)$ by conjecture above) to the
entry in $A_n$ with $k$ having $n-i$ ones, with $0\leq i\leq d-3$, to
get the corresponding entry in $A_n$.  All other entries remain
unchanged.

\medskip

\noindent (iv) {\bf Description of $B_n$ to $B_n'$ transition}: 
Let us temporarily write $f(n, d):=v_d(5 \cdot 2^n-1)-v_d(2^{n+1}-1)$. 


Then $t_{k, n, d}=-f(n, d-i-1)$ and $0$, respectively, 
if the base $2$ expansion of $k$ has $n-i$ number of ones (there 
is exactly one term with $i=-1$, otherwise $i\geq 0$), 
with $i< d-4$ and $i>d-4$, respectively. The special case $i=d-4$ 
has $t_k<0$ and is described later. 

\medskip

\noindent (v) {\bf Description of $C_n$ to $C_n'$ transition}: 
Put $g(n, i):=w_{n+1, i}-w_{n, i}$, 
when $i\geq 0$ and $0$ otherwise,  and 
$r(n, i):=(-1)^{n+i-1} \cdot 3 \cdot 2^{n-i}$, when $1\leq i\leq n-1$. 
Note $g(n, i)=0$ for $i\leq 3$. 


Let $k$ have $n-m$ number of ones in its base-$2$ expansion, so that 
$0\leq m\leq n-2$.  If $m\geq d-4$, then $t_k=0$. So fix $m>d-4$. 
If $d$ and $m$ have the same parity, then $t_k=g(n, d-(m+1))$. 
If $d$ and $m$ have opposite parity, list such $k$'s 
(there are ${n-1\choose n-m-2}={n-1\choose m+1}$ of these, 
as out of the $n+2$ digits, 
first two are $1, 0$ and the last is $1$) in increasing 
order and add to corresponding entries the amounts
$$g(n, d-(m+1))+r(n, i_1)+r(n, i_2)+\cdots +r(n, i_{m+1}),$$ 
with $1\leq i_1<\cdots <i_{m+1}\leq n-1$, in lexicographic order, 
where smaller $i$ (i.e., larger absolute value of $r(n, i)$) comes first.  

\subsection{Remarks on consequences}

\begin{enumerate}
\item In the $A_n$ to $A_n'$ and $C_n$ to $C_n'$ transition to 
$t_k\geq 0$,  while in $B_n$ to $B_n'$ transition, $t_k\leq 0$. 

\item 
The first $2^{n-d+2}-1$ entries of $X_n$ are unchanged (i.e.,
with $t_k=0$) in $X_n'$. More generally, those entries in $A_n$
(resp., $B_n$, $C_n$) with $k$ having at most $n+2-d$ (resp., $n+3-d$,
$n+4-d$) ones in their base-$2$ expansion remain
unchanged in the corresponding places of $X_n'$. (Some other entries also
remain unchanged, so this is not an if and only if condition.)


The first consequence can be proved from the hypothesis that the
maximum of $v_d(k)$ with odd $k\leq 2^n-1$ occurs at $k=2^n-1$ and the
conjectural formula of $v_d(2^n-1)$ as well as the congruence noted above.
(Another way to see this is to note $1/a^k+1/a^{k+3 \cdot 2^n}=
(a^{3 \cdot 2^n}+1)/a^{k+3 \cdot 2^n}$, for $a$ prime to $v$,
so that $a^3 \equiv \modd{1} {v}$ implies the sum has valuation at least $2^n$.). In more
detail, if $k\leq 2^{n-d+2}-1$, then by these hypotheses we have
$v_d(k)\leq v_d(2^{n-d+2}-1)< 2^n$, so that $v_d(k)=v_d(k+m \cdot 3 \cdot 2^n)$.

\item In (iii) the bound $d-3$ could have been 
changed to $d$, since the addition amount for $d-2\leq i\leq d$ is zero. 

\item In (iv) we also conjecture that  $f(n, d)$ is $(3d-6)2^n$ for $d$ even 
and $(3d-15) \cdot 2^n$ for $d>3$ odd, while for $d=3$, it is $2^n$ for 
$n$ odd and $2^n-1$ for $n$ even. Note $f(n, 5)=0$, so that 
by (iv) more entries are unchanged than listed in the part 2 of these Remarks. 

\end{enumerate}

\noindent {\bf Special case (iv), $i=d-4$}:  
Since $k$ is odd with $n+1$ digits, we have $3\leq d\leq n+2$ and
there are ${n-1\choose d-3}$ such entries in $B_n$. Let  
$a_n$ denote $2^n-1$, if $n$ is even and $2^n$, if $n$ is odd. 

For $d=3$ (resp., $d=n+2$), we have a unique such $k$ and we
have $t_k=-a_n$ (resp., $t_k=-2^n$). 

For $d=4$, the $n-1$
differences $-t_k-a_n$ are $(-1)^{i-1}(2^{n-i}-1)$ with increasing $1\leq i\leq
n-1$, if $n$ is even and they are $2^{n-1}+1, -2^{n-2}, \cdots, 2^2-1,
-2$ if $n$ is odd. 

For $d=n+1$, the differences $-t_k-a_n$  are $0, 2^3, -(2^2-1), 2^5,
\cdots, 2^{n-1}, -(2^{n-2}-1)$ if $n$ is even and $2^2+1, -2, \cdots,
2^{n-1}+1, -2^{n-2}$ if $n$ is odd.  

For $d=5$, $-t_k-a_n$ are  given as follows. Write these differences in
$d=4$ case described above as $c_{n-1}, \cdots, c_1$, then in $d=5$
case, the first $n-2$ differences are (for $k$'s in the special case
written in increasing order) $0, c_{n-1}+c_{n-3},
c_{n-1}+c_{n-2}+c_{n-3}+c_1, c_{n-1}+c_{n-5},
c_{n-1}+c_{n-4}+c_{n-5}+c_1, \cdots$, (thus ending with
$c_{n-1}+c_4+c_3+c_1, c_{n-1}+c_1$ when $n$ is even and with
$c_{n-1}+c_2, c_{n-1}+c_3+c_2+c_1$ when $n$ is odd. These are followed 
by $n-3$ copies of $-a_{n-2}$, followed by the differences at 
$(n-2, d)$ level (there are ${n-3\choose 2}$ of them.) 

For $d\geq 3$, for $k$ written in increasing order, for the
${n-1\choose d-3}$ $k$'s that we consider at the $(n, d)$-level,
the differences $t_{k, n, d}-a_n$ are given by repeating these differences
(${n-3\choose d-5}$ of them) at the $(n-2, d-2)$ level, followed by a
portion denoted by $Q$, as we have not been able to guess it yet. It consists
of ${n-3\choose d-4}$ entries), followed by $-a_{n-2}$ repeated
${n-3\choose d-4}$ times, followed by the differences at $(n-2, d)$
level (${n-3\choose d-3}$ of them.

The portion $Q$ is 
$2^{n-1}+(-1)^{n-1}$ for $d=4$. For $d=5$, it is sum of first and third 
differences at $(n, 4)$ level, followed by $3 \cdot 2^{n-3}$+ top 
entries ($n-4$ of them) from $(n-2, 5)$ level.
The first term of the portion $Q$ in the
$d=6$ case is $2^{n-1}+(-1)^{n-1}$. For $d=n+1$, the portion $Q$ is
$2^{n-1}+1$ and $2^{n-1}$,  according to whether 
$n$ is odd or even, respectively. 
More generally, the first (resp., last) entry of the portion 
$Q$ is $2^{n-1}+(-1)^{n-1}$ (resp., $2^{n-1}$) according to whether
$d$ is even (resp., $d$ is odd and $n$ is even). 

\medskip

\noindent {\bf Special cases of low $d$}:  
We consider the $v_d(k)$ sequence for $k$ odd. 

($d=1$) The pattern is 0, 1, 0, 0, 1, 0, ...,  periodic with period $3$. 

($d=2$) The pattern is 1, 0, 1, 1, 0, 1, ... , periodic with period $3$. 

($d=3$)  $w_n=1$ for $d=3$, 
 $X_n'$ is obtained from $X_n$ by adding $3 \cdot 2^n$ to the
$2^{n-1}$-th entry (i.e., $k=2^n-1$) and subtracting from $2^n$-th
entry (i.e., $k=2^{n+1}-1$) either $2^n$ or $2^n-1$, respectively, as
$n$ is odd or even.

So the pattern is 2, 6, 1, 8, 4, 1, 2, 18, 1, 5, 4, 1, 2,
6, 1, 32, 4, 1, 2, 10, $\ldots$ with $k$ being 5, 11, 1, 9 modulo 12 giving
the entries 1, 1, 2, 4, respectively.

\section{Zero distribution of  Goss zeta functions}

For a given $y$, $\zeta(x, y)$ is a  power series in $x$ with coefficients 
in $K_{\infty}$.  Wan \cite{W} noticed and proved using a Newton polygon 
calculation, using estimates of $s_d(-y)$, that the zeros of $\zeta(x,y)$
are simple and 
always lie in $K_{\infty}$,
when $q$ is a prime. This was later generalized by Sheats to any $q$. See 
\cite[Sec.\ 5.8]{T}
and \cite{G, G2} 
for the references for this development and discussion of higher genus case. 

Noting that 
$K_{\infty}$ and $C_{\infty}$ are, respectively, the
analogues of the real and complex number fields,
this restrictive behavior reminds one of the Riemann hypothesis 
situation \cite{G, G2, T}. This looks even more remarkable, if one notices 
further that algebraic degree of $C$ over $R$ is just 2, whereas 
in our case, it is infinity.

We now turn to the $v$-adic case and the zero distribution for 
the power series $\zeta_v(x, y)$ in $x$ with coefficients 
in $K_v$, for a given $y$.
We can ask whether the zeros of $\zeta_v(x, y)$ are 
in $K_v$ and whether they are simple.
Our results can be used to calculate Newton polygons 
and the zero distribution. For this we can approach the $p$-adic integers $y$
through the sequence of positive $k$'s,
or through negative $k$, or indeed through 
any dense subsequence (See \cite[5.8]{T} and \cite{T09}).   
We leave this for a future paper and note here only two simple
applications requiring only a few things we have proved.

\medskip

\noindent (I)  When degree of $v$ is one, and $q=2$, Wan \cite{W} 
(see also \cite[Prop.\ 9]{G2}) already showed 
that the zeros are simple and in $K_v$. For general 
$q$, one has the same results for $y\in (q-1)S_v$. 
(Note that  when $q=2$, non-zero is the same as monic, otherwise we
restrict to `even' $k$ to kill the signs.)
This can be also derived immediately from Corollary~\ref{cor2}, which in fact 
provides much more precise information to calculate the Newton polygon. 

We remark that, when $q=2$, the one unit part of $S_d(k)$ when you substitute $1/t$ for $t$
is $S_{\leq d}(k)$ with $t$ factor removed.  So $s_d(k)-k\geq \mbox{ min } 
v_i(k)$ ($i\leq d$) with equality if there are no clashes. (But there can be
clashes, even for $d=1$, $k$ odd.)

To do the general $q$ case, without restriction of `evenness', for degree 
one primes, we need to use 
information provided by  Theorems~\ref{thm1} and \ref{thm3}.
We leave this for a future paper.

\noindent (II) We now show that when $q=2$,  $v=t^2+t+1$, the 
zeros need not be  in $K_v$.  

For the first example, let $k=5$. 
In fact, we saw that 
 $v_d(5)=0, 0, 1, 1, 12, 20, \ldots$. We do not need the full pattern.
 We can say that the first
two slopes are $0$ and $1/2$ because  degree of $v$ being
$2$, we have easy estimate $v_d(k)\geq m$, if $d>2m$, by the trivial 
lower bound described above. (In fact, since the valuations are 
not zero infinitely often, the slope would be at most $1/2$ in any case.) 

Here is  a second example:  $q=2$, $v=t^2+t+1$, and $k=3$.
Now $v_d(3)$ for $d=0, 1, 2, \cdots$ is $0, 1, 0, 6, 9, 27, \ldots$, 
so that  the first two 
slopes are $0$ and $9/2$. To see this,  trivial lower bounds 
above are not sufficient, but in this case, we know   $v_d(3)$, by 
Section~\ref{sec3}, 
so a straightforward calculation justifies this.  

\section{Leading term formulas}

It follows \cite[Cor. 5.6.2]{T} from Carlitz' work that for $k>0$, 
$S_d(-k)=0$ if
and only if $d>\ell(k)/(q-1)$, for $q$ prime. 
(See \cite{B12} and \cite[A.5]{T09} for the 
general situation). Hence, for  $k>0$, $S_{\lfloor \ell(k)/(q-1)\rfloor}(-k)$ 
is the leading term of the Goss zeta series, at least when $q$ 
is prime, and also for general $q$, when $\ell(k)$ is the minimum of 
$\ell(p^ik)$.   

\begin{theorem}
  Let $q$ be any prime power. Let $k>0$ 
and $\ell(k) =(q-1)d+r$, with $0\leq r<(q-1)$, so that 
$d=\lfloor \ell(k)/(q-1)\rfloor$.   Write
  the base $q$-expansion $k=\sum_1^{d(q-1)+r} q^{k_i}$. Then
$$S_d(-k)=(-1)^d\sum t^{\sum_{i=1}^{d-1} i\sum_1^{q-1} q^{k_j}+d\sum_1^r q^{k_m}},$$
where the sum is over all assignments to $i$'s of groups of $q-1$
of the powers $q^{k_j}$'s corresponding to indices in 
partitions of $d(q-1)+r$ indices 
into $d$ groups of $q-1$ each and one group of $r$ powers. 
\label{thm5}
\end{theorem}

\begin{proof}
Let us first see the simplest $q=2$ case. Then $r=0$ and we have
\begin{eqnarray*}S_d(-k)& = & \sum_{f_0, \ldots, f_{d-1}\in \FF_q}(t^d+f_{d-1}t^{d-1}
+\cdots +f_0)^k\\
& = & \sum \prod_{i=1}^{d(q-1)}(t^{dq^{k_i}}+f_{d-1}t^{(d-1)q^{k_i}}+\cdots +f_0)
\end{eqnarray*}

Keep the sum and consider the terms obtained by expanding the product.
Any term not containing all $f_i$'s will vanish after summing over
that missing $f_i$ (compare proof of \cite[Thm. 5.1.2]{T}). So terms
that matter are of the form $f_0\cdots f_{d-1}t^{\sum_1^{d-1}
  iq^{k_{j_i}}}$, where there is really only one non-zero term corresponding 
to $f_i=1$, so that $S_d(-k)$ is exactly the sum of these $t$ powers,
over $j_i$'s which are permutations of $1$ to $d$.

Now consider the general $q$ case. 
 Then,  as before,
we have exactly the same displayed expression, and as before, when we
expand the product, all $f_i$'s need to be there and each $f_i$ with minimal 
power $q-1$ to get the non-zero sum, so only terms that matter 
have coefficient $(f_0\cdots f_{d-1})^{q-1}$ (as the  relation between 
$d$ and $\ell(k)$ shows) so that we get the expression as claimed. 
\end{proof}

\subsection{Example} Let $q=3, k=38=27+9+1+1$, so that $d=2$ and our 
our formula gives $S_d(-k)=t^{27+9}+2 \cdot t^{27+1}+2 \cdot t^{9+1}+t^2$. 


\begin{corollary}
With the notation as in Theorem~\ref{thm5},
when $q=2$, we have a product formula 
$$S_d(-k)=\prod_{d\geq n>m}(t^{2^{k_n}}+t^{2^{k_m}}).$$
More generally, for any $q$, but for the special family 
$k=(q-1)\sum_1^d q^{k_i}>0$ (with $k_i$ distinct) we have the leading term 
$$S_d(-k)=(-1)^d\prod_{d\geq n>m} (t^{q^{k_n}}-t^{q^{k_m}})^{q-1}.$$
\label{cor6}
\end{corollary}



\begin{proof}
Put $T_n=t^{q^{k_n}}$. The product formula  follows immediately, 
when $q=2$, by simple counting of monomials in
$\prod (T_n+T_m)$. For general $q$, one has to only note, in addition, that 
${q-1 \choose i} = (-1)^i$, so that $(T_n-T_m)^{q-1}=\sum T_n^aT_m^b$, where 
the sum is over $a, b$ with $a+b=q-1$. 
\end{proof}

\subsection{Remarks} 

\begin{enumerate}

\item The product formula 
in the $q=2$ case was obtained earlier by 
Pink  using a cohomological formula for the leading power sum. 
See \cite[7.1]{B12} for this, as well as the 
proof of the Corollary using the Vandermonde determinantal formula
combined with cohomological machinery.  

\item When $q>2$, we  do not have  a  product formula involving 
only monomials in $[n]$'s, in the general 
case, for the leading term, even if $q$ is a prime. For example, 
when $q=3$, $k=13$, $S_1(-13)=-(t^3-t)(t^3-t+1)(t^3-t-1)$. On the 
other hand, for many families of $q, k$, 
we can prove the product expression (for the leading term $S_d(-k)$ 
as above) 
$$c\prod (t^{q^j}-t^{q^i})^{r_{i, j}},$$
where $c\in \FF_q$ expressed in terms of multinomial coefficient, 
product being over $i<j$ such that $k_i+k_j=q-1+r_{i, j}$, 
with $r_{i, j}>0$, where $k=\sum k_jq^j$ is the base $q$ expansion of $k$. 
We leave it to a future paper to investigate
 the exact scope of when it works, and the cohomological explanation of
 the prime factors which enter in terms of the $p$-ranks of the
Jacobians (components) of the corresponding cyclotomic extensions.

\item When $q=2$, the product has $d(d-1)/2$ terms of two terms. When
expanded, it has $2^{(d-1)d/2}$ terms, and the sum has $d!$ terms
(some can cancel), whereas if we just use the definition there are
$2^d$ terms to be added each consisting of $(d+1)^k$ (or rather
$(d+1)^{\ell(k)}$ using $p-$th powers) terms.

\end{enumerate}

\section{Acknowledgments} I thank Alejandro Lara Rodriguez for
creating data (using SAGE) on which many of the guesses of this paper
are based. I also thank Gebhard B\" ockle and David Goss for
discussions on these issues and their encouragement. I am grateful to 
Javier Diaz-Vargas for pointing out the careless parenthetical remark 
in part (iii) of Theorem 7 and the resulting correction in Theorem 9. 



\begin{thebibliography}{99}

\bibitem{B12}
G. B\" ockle,  The distribution of the zeros of the Goss zeta function 
for $A=\FF_2[x, y]/(y^2+y=x^3+x+1)$, preprint, 2012.

\bibitem{C}
L. Carlitz,  On certain functions connected with
polynomials in a Galois field,
{\it Duke Math.\ J.}\ {\bf 1} (1935), 139--158.

\bibitem{D}
J. Diaz-Vargas,  Riemann hypothesis for $F_q[t]$, 
{\it J. Number Theory} {\bf 59} (1996), 313--318. 

\bibitem{G} D. Goss, {\em Basic Structures of Function Field
    Arithmetic},  Ergebnisse der Mathematik und ihrer Grenzgebiete,
  \textbf{35}, Springer-Verlag, 1996.

\bibitem{G2}
D. Goss, 
A Riemann hypothesis for characteristic $p$ $L$-functions, 
{\it J. Number Theory}, {\bf  82} (2000), 299--322. 

\bibitem{S}
J. Sheats,
The Riemann hypothesis for the Goss zeta function for $F_q[t]$, 
{\it J. Number Theory}, {\bf 71 } (1998), 121--157. 

\bibitem{Tz}
D. Thakur, Zeta measure associated to $\FF_q[t]$, 
{\it J. Number Theory}, {\bf  35} (1990), 1--17. 

\bibitem{T} D. Thakur, {\em Function Field Arithmetic,}
World Scientific, 2004.

\bibitem{T09} D. Thakur, Power sums with applications to multizeta 
and zeta zero distribution for $\FF_q[t]$, {\it Finite Fields 
Appl.}, {\bf  15} (2009), 534--552. 

\bibitem{W}
D. Wan, 
On the Riemann hypothesis for the characteristic $p$ zeta function, 
{\it J. Number Theory}, {\bf  58} (1996), 196--212. 


\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11M38; Secondary 11M26, 11R58.

\noindent \emph{Keywords: }
zeros of the zeta function, valuation, power sum.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  August 1 2012;
revised version received January 7 2013.  
Published in {\it Journal of Integer Sequences}, March 2 2013.
Minor revisions, March 13 2014.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                
