Ticket #3081 (new enhancement)

Opened 8 months ago

Last modified 1 month ago

[with patch; needs work] Added support for Kloosterman sums

Reported by: kkilger Assigned to: was
Priority: major Milestone: sage-3.4
Component: number theory Keywords: editor_craigcitro
Cc: ncalexan

Description

This (nearly trivial patch) adds support for exact and numerical evaluation of "twisted" Kloosterman sums. This generalizes Gauss sums, Salie sums and normal Kloosterman sums.

Attachments

dirichlet2.patch (5.6 kB) - added by kkilger on 05/02/2008 08:13:31 AM.

Change History

05/02/2008 08:10:39 AM changed by mabshoff

  • owner changed from mabshoff to was.
  • component changed from Cygwin to number theory.

Hi Kilian,

Aside from the fact that this is a number theory ticket everything looks good. Hopefully somebody will review this patch shortly.

Cheers,

Michael

05/02/2008 08:13:31 AM changed by kkilger

  • attachment dirichlet2.patch added.

05/02/2008 08:23:06 AM changed by wdj

This sounds extremely cool! What is based on? I can't get it to apply on either 3.0 or 3.0.1.alpha1.

05/02/2008 08:27:40 AM changed by was

QUESTION:

You've rewritten some of the functions to be more general, e.g., this 

707	 	            z *= zeta 
708	 	            g += phi(c)*z

becomes this: 

763	                z = zeta ** (a*e + b*(e**(-1))) 
764	                g += phi(self.__call__(c))*z

What impact does this have on performance in the original case of computing Gauss sums? Is it slower or faster or the same?

Also, why use 

self.__call__(c)

instead of 

self(c)

?

05/02/2008 08:50:08 AM changed by kkilger

It computes the modular inverse every time. So it should be somewhat slower as before. I read that there is an ongoing discussion between code duplication and speed ...

I wanted to use this to introduce Poincare series in SAGE (and compute their Fourier coefficients) but this is far to slow. I am planning to reimplement the numerical stuff in C/Cython next week (or this weekend).

Question: Why are Dirichlet characters in modular/dirichlet.py? Is it for historical reasons?

Regards, Kilian.

(follow-up: ↓ 6 ) 05/02/2008 08:54:37 AM changed by kkilger

P.S.: ... oh. I will change self.call(c) to self(c). I have to get used to python ;-).

(in reply to: ↑ 5 ) 05/02/2008 08:59:29 AM changed by kkilger

P.P.S: It should be based on 3.0 ...

05/02/2008 09:08:11 AM changed by was

Question: Why are Dirichlet characters in modular/dirichlet.py? Is it for historical reasons?

Yep, Historical reasons. Where would you want to put it.

It computes the modular inverse every time. So it should be somewhat slower as before. I read that there is an ongoing discussion between code duplication and speed ...

Worrisome, but like you say below it is too slow in the first place.

I wanted to use this to introduce Poincare series in SAGE (and compute their Fourier coefficients) but this is far to slow. I am planning to reimplement the numerical stuff in C/Cython next week (or this weekend).

Excellent!

-- William

05/02/2008 10:25:15 AM changed by kkilger

Yep, Historical reasons. Where would you want to put it.

Are there some other character groups implemented? Perhaps it should go to the dual groups?

Another question:

If I compute for example the Kloosterman sum K(2,4,13) in Magma it returns: 2*zeta_1310 + 2*zeta_139 + 2*zeta_137 + 2*zeta_136 + 2*zeta_134 + 2*zeta_133

If I compute it with SAGE it returns: 2*zeta15640 - 2*zeta15634 + 2*zeta15628 - 2*zeta15624 + 2*zeta15618 - 2*zeta15614 - 2*zeta15612 + 2*zeta1568 - 2*zeta1562 - 2

This is the same number but it is much more reduced in MAGMA. The corresponding MAGMA code is:

Kloosterman := func< u, v, n | &+[z(IntegerRing?() ! (u*x+v*x-1)) : x in F | IsUnit?(x) ] where z is RootOfUnity?(n, CyclotomicField?(n)) where F is ResidueClassRing?(n) >;

Kilian.

05/02/2008 10:28:19 AM changed by kkilger

Again ... I forgot the code block

Magma-Number: 

2*zeta_13^10 + 2*zeta_13^9 + 2*zeta_13^7 + 2*zeta_13^6 + 2*zeta_13^4 + 2*zeta_13^3

SAGE-Number: 

2*zeta156^40 - 2*zeta156^34 + 2*zeta156^28 - 2*zeta156^24 + 2*zeta156^18 - 2*zeta156^14 - 2*zeta156^12 + 2*zeta156^8 - 2*zeta156^2 - 2

Magma-Code: 

>  Kloosterman := func< u, v, n |
>      &+[z^(IntegerRing() ! (u*x+v*x^-1)) : x in F | IsUnit(x) ]
>          where z is RootOfUnity(n, CyclotomicField(n))
>          where F is ResidueClassRing(n) >;

06/15/2008 02:40:36 PM changed by craigcitro

  • keywords set to editor_craigcitro.

06/19/2008 03:08:24 PM changed by craigcitro

  • cc set to ncalexan.
  • summary changed from [with patch; needs review] Added support for Kloosterman sums to [with patch; under review by ncalexan before 7/1] Added support for Kloosterman sums.

09/24/2008 05:18:39 PM changed by mabshoff

Nick,

anything going on here?

Cheers,

Michael

10/30/2008 11:07:15 AM changed by was

  • summary changed from [with patch; under review by ncalexan before 7/1] Added support for Kloosterman sums to [with patch; needs review] Added support for Kloosterman sums.

From Nick: 

I seem to remember thinking this code was mildly flawed (easily fixed) and not fast.  But please pass it on to someone more tuned in.

11/27/2008 08:39:42 PM changed by was

  • summary changed from [with patch; needs review] Added support for Kloosterman sums to [with patch; needs work] Added support for Kloosterman sums.

REFEREE REPORT:

This patch needs work. Just totally delete the first part of the patch that replaces lines 636-652 by nothing and calls kloosterman_sum, since kloosterman_sum is much slower. Just leave the code like it used to be.

Otherwise, i think the code is good to have included in sage. In particular, the issue the author raises about the representation of a certain output and a root of unity is interesting, but not something to stop this patch from going in.

So I think with some very obvious simple work, this can easily be included. Just delete the part that will slow down the gauss_sum.