3
$\begingroup$

Suppose I want to consider Dirichlet characters $$\chi: \mathbb{F}_p(\zeta_r)^{*} \longrightarrow \mathbb{C}$$ Can I prove something similar to the Polya Vinogradov inequality for these characters?

Basically I want look for quadratic non-residues in $\mathbb{F}_p(\zeta_r)^{*}$. What can I say about non-residues

  1. Without assuming GRH (something similar to burgess bound ??)
  2. Assuming GRH (something similar to N.C Ankeny's result ??)
$\endgroup$
5
  • 2
    $\begingroup$ Sums of characters (multiplicative as well as additive) are well studied. Because you mention Polya-Vinogradov, you are probably interested in incomplete character sums. Like $$S(M,\chi)=\sum_{x\in M} \chi(x),$$ where $M$ is some subset of the finite field $\Bbb{F}_p(\zeta_r)$. But, for me to be able to answer you need to say more. 1) What kind of subsets $M$ are you interested in? Bear in mind that there is no very natural concept of an interval inside $\Bbb{F}_p(\zeta_r)$. 2)Is your character additive or multiplicative? Which rule $\chi(x+y)=\chi(x)\chi(y)$ or $\chi(xy)=\chi(x)\chi(y)$? $\endgroup$ Jul 7, 2016 at 7:08
  • 2
    $\begingroup$ (cont'd) You mentioning Dirichlet characters suggests (IIRC, I'm not a number theorist) that you want the character to be multiplicative. But the only intervals $M$ I've seen inside a finite field that is not a prime field consist of the elements with discrete logarithms in a given range. That pair of answers to 1+2 in my previous comment is, unfortunately, uninteresting, because the sum is then geometric and trivial to calculate exactly. This underlines my need to get a more precise question from you. $\endgroup$ Jul 7, 2016 at 7:12
  • 2
    $\begingroup$ Also, this type of questions lead to study of function fields and number theory inside the polynomial ring $\Bbb{F}_p[T]$ as opposed to $\Bbb{Z}$. In the former all variants of Riemann Hypothesis are theorems, so I don't understand the part about with/without GRH. $\endgroup$ Jul 7, 2016 at 7:13
  • $\begingroup$ @JyrkiLahtonen can you suggest me some reading material? Actually I was thinking on the lines of deterministically finding square roots modulo primes. As finding non-residues in $F_p$ is really hard without assuming GRH, I thought can I do anything better in a Cyclotomic extension of $F_p$. Also if you want a subset of $F_p(\zeta_r)$ consider this $$\zeta +1 ,\zeta +2 ,\ldots \zeta+k $$ for $k =O(\log^2p)$ $\endgroup$
    – xyz
    Jul 8, 2016 at 3:40
  • 1
    $\begingroup$ Ok, xyz. That is a tiny set. I looked up Polya-Vinogradov. That does generalize, but I don't know about the GRH improvements (and, yes this is a difficult problem in finite fields as well, I take that back) $\endgroup$ Jul 9, 2016 at 20:33

1 Answer 1

1
$\begingroup$

I think that the Polya-Vinogradov method amounts to the following.

If $\chi$ is a multiplicative character of a finite field $K$, i.e. a homomorphism from $K^*$ to $\Bbb{C}^*$, and $M$ is some subset of $K^*$, then we seek to bound the character sums $$ S(M,\chi)=\sum_{x\in M}\chi(x). $$ We could replace the character $\chi$ with another complex valued function, say with $\chi(f(x))$ for some polynomial $f(x)\in K[x]$, but let's stick to this basic case for now.

We begin by writing the characteristic function $\chi_M:K\to\Bbb{C}$ of $M$, $\chi_M(z)=1$ if $z\in M$ and $\chi_M(z)=0$ if $z\notin M$, as a linear combination of additive characters of $K$.

The additive characters, i.e. homomorphisms $\psi:(K,+)\to(\Bbb{C}^*,\cdot)$ have the following description. Let $tr:K\to\Bbb{Z}_p$ be the trace function $$ tr(x)=x+x^p+x^{p^2}+\cdots+x^{p^{n-1}}, $$ where the integer $n$ is determined by $q:=|K|=p^n$. Denote $\omega=e^{2\pi i/p}$. Because the trace is a surjetive homomorphism of additive groups, to each constant $a\in K$ the function $\psi_a:K\to\Bbb{C}^*$ defined by $$ \psi_a(x)=\omega^{tr(ax)} $$ is also a homomorphism, i.e. an additive character. Furthermore, all the additive characters of $K$ are gotten in this way.

Assume that we can find constants $c_a\in\Bbb{C}$ such that $$ \chi_M=\sum_{a\in K}c_a\psi_a. $$ Then we can write the sum $S(M,\chi)$ as follows: $$ \begin{aligned} S(M,\chi)&=\sum_{x\in M}\chi(x)\\ &=\sum_{x\in K}\chi(x)\chi_M(x)\\ &=\sum_{x\in K}\chi(x)\sum_{a\in K}c_a\psi_a(x)\\ &=\sum_{a\in K}c_a\sum_{x\in K}\chi(x)\psi_a(x). \end{aligned} $$ We can make progress here provided that:

  1. We have a good idea of coefficients $c_a$. Whether this is true depends heavily on the choice of $M$.
  2. We have a good idea about the inner sums $\sum_{x\in K}\chi(x)\psi_a(x)$. This is true, because such sums are the well studied Gauss sums. If $a=0$ or $\chi$ is the principal character, then the sum is trivial, and otherwise it is known that the inner sum has absolute value $\sqrt q$.

So it is about the coefficients $c_a$. Any function $f:K\to\Bbb{C}$ can be written as a linear combination of the characters $\psi_a$, $a\in K$. This is just basic discrete Fourier analysis on a finite abelian group (call it using the Pontryagin dual if so inclined - my background is more on the telecommunication applications, so my past readers welcomed me calling it a DFT :-) Anyway, by orthogonality and completeness of the set of characters $\psi_a,a\in K,$ we always have $$ f=\sum_{a\in K}\hat f_a\psi_a, $$ where the coefficients $\hat f_a$ are defined as inner products $$ \hat f_a=\frac1q\sum_{x\in K}f_a(x)\overline{\psi_a(x)}. $$

Another key ingredient in Polya-Vinogradov is that when $M$ is an interval the sums $c_a=\widehat{\chi_M}_a$ are just geometric sums. Let's look at the classical case of the prime field first. When $q=p$ and $M=\{b,b+1,b+2,\ldots,b+N-1\}\subset [0,p-1]$ we get that whenever $a\neq0$ $$ c_a=\frac1p\sum_{x=b}^{b+N-1}\overline{\psi_a(x)}= \frac1p\sum_{j=b}^{b+N-1}\omega^{-aj}=\frac{\overline{\omega^{ab}-\omega^{a(b+N)}}}{p(1-\overline{\omega^a})}. $$ This worked because $c_a$ is a geometric sum with ratio $\overline{\omega^a}\neq1$, or, because $$ \psi_a(x+1)=\omega^a\psi_a(x).\qquad(*) $$ When $a=0$, the sum is trivial, and we get $c_0=N/p$. That will often give the main term in the end result because the other sums oscillate.

You asked specifically about sets of the type $$ M=\{\zeta+1,\zeta+2,\zeta+3,\ldots,\zeta+k\}. $$ The same calculations go thru. However, a possible obstruction to progress may be that this time many coefficients $c_a$ in the expansion of $\chi_M$ will share that maximum absolute value. We still have $$ \psi_a(\zeta+m+1)=\psi_a(\zeta+m)\psi_a(1) $$ for all natural numbers $m$. But this time the ratio of the consecutive terms, $\psi_a(1)$ is often enough equal to $1$ even when $a\neq0$. This is because $$ \psi_a(1)=\omega^{tr(a)}=1 $$ whenever $tr(a)=0$. By linearity of trace this happens for $q/p=p^{n-1}$ choices of $a$. I don't know, if that will ruin your day or not.


Another situation where Polya-Vinogradov works the same way is when $M=\{g^a,g^{a+1},\ldots,g^{a+N-1}\}$, where $g$ is a generator of $K^*$ and we are interested in evaluating a sum of the form $$ S(M,f)=\sum_{x\in M}f(x). $$ This time we want to write $\chi_M$ as a linear combination of the multiplicative characters (i.e. the analogues of Dirichlet characters), and perform a DFT in the group $K^*$ instead. This variant is near and dear to me for its applications in the analysis of certain pseudorandom sequences consisting of values $\psi_1(f(g^k))$ for some polynomial $f(x)\in K[x]$. Such sequences are all over the place in coding theory and such.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .