Re: Kronecker symbol

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

On Mon, 25 Aug 2003, Jack Fearnley wrote:
> I have been having some trouble with kronecker(x,y) which is described in the
> documentation as a generalization of the Legendre symbol (x|y).  I was
> expecting kronecker to behave like a Dirichlet character.  In particular, I
> expected kronecker(3,4) to equal -1 whereas it computes as 1.
>
> I have two questions:
>
> 1) What is the precise definition of kronecker in Pari?

Legendre symbol (x|y) extended to Z x Z by complete multiplicativity, plus
the following special rules for y = 0, -1 or 2:

y = 0:  (x|0)  =  1 if |x| = 1
                  0 otherwise

y = -1: (x|-1) =  1 if x >= 0,
                 -1 if x < 0.

y = 2:  (x|2)  =  0 if x is even
               =  1 if x = 1, -1 mod 8
               = -1 if x = 3, -3 mod 8

> 2) Is there a quick and easy way to generate quadratic Dirichlet characters
> in Pari?

Not really. You can use

  if (issquare(Mod(x, y)), 1, -1)

[ assuming gcd(x,y) = 1 ], but issquare(x,y) requires factoring y in most
cases and is very wasteful if the same y is used over and over again.
[ better to factor it once and loop by hand over the cyclic components of
(Z/yZ)^* ]

> 2a) What about higher order Dirichlet characters?

You have to program it yourself. Reduce to the case y prime, then the best
solution depends on the size of y, the number of characters you need for a
given y, available memory... and the actual efficiency required.  A quick and
very inefficient solution is to use znprimroot and znlog [ define an explicit
isomorphism with additive characters of Z/(y-1)Z ]

Cheers,

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425   Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://www.parigp-home.de/  [PARI/GP]