Opened 21 months ago

Closed 21 months ago

Last modified 17 months ago

#23456 closed enhancement (fixed)

Compute Gauss sums with Gross-Koblitz formula

Reported by: asteele Owned by:
Priority: minor Milestone: sage-8.1
Component: padics Keywords: sd87 gamma p-adic
Cc: Merged in:
Authors: Adriana Salerno, Ander Steele Reviewers: Adele Bourgeois, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 95a100a (Commits) Commit:
Dependencies: Stopgaps:

Description

This code uses the Gross-Koblitz formula to compute Gauss sums as products of p-adic Gamma functions. The result is an element of a totally ramified extension of Q_p. This can be much faster than computing gauss sums in the naive way. References: Benedict Gross & Neil Koblitz, "Gauss sums and the $p$-adic $\Gamma$-function", 1979 Alain Robert, "The Gross-Koblitz formula revisited", 2001

Change History (27)

comment:1 Changed 21 months ago by asteele

  • Branch set to u/asteele/compute_gauss_sums_with_gross_koblitz_formula

comment:2 Changed 21 months ago by git

  • Commit set to 45b56d0cd0ae65795ce9da3d42b43c22bee4c3a3

Branch pushed to git repo; I updated commit sha1. New commits:

45b56d0Add documentation

comment:3 Changed 21 months ago by git

  • Commit changed from 45b56d0cd0ae65795ce9da3d42b43c22bee4c3a3 to b77e34f83d4c50ca8517abc66e2e333aad3600f0

Branch pushed to git repo; I updated commit sha1. New commits:

b77e34ffix import on doctests

comment:4 Changed 21 months ago by git

  • Commit changed from b77e34f83d4c50ca8517abc66e2e333aad3600f0 to cb21c90a1ed8e169c2f71237fe9f3573b1805c49

Branch pushed to git repo; I updated commit sha1. New commits:

cb21c90Fix whitespace problems with documentation

comment:5 Changed 21 months ago by git

  • Commit changed from cb21c90a1ed8e169c2f71237fe9f3573b1805c49 to 1c3d06ab244343f2f3c6ce956d1ca502f3b6eef2

Branch pushed to git repo; I updated commit sha1. New commits:

1c3d06aprettify documentation with latex tags

comment:6 Changed 21 months ago by git

  • Commit changed from 1c3d06ab244343f2f3c6ce956d1ca502f3b6eef2 to f5583f680a031dd20544a3dea950f700538d6bc8

Branch pushed to git repo; I updated commit sha1. New commits:

f5583f6Add documentation

comment:7 Changed 21 months ago by asalerno

  • Status changed from new to needs_review

comment:8 Changed 21 months ago by abourgeois

  • Reviewers set to Adele Bourgeois
  • Status changed from needs_review to positive_review

Looks good.

comment:9 Changed 21 months ago by git

  • Commit changed from f5583f680a031dd20544a3dea950f700538d6bc8 to 88b954e7c2bc522f4cf5d0d04de424f8296bff76
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

88b954eFix modulus for argument a, which depends only on residue class mod(p^f-1)

comment:10 Changed 21 months ago by abourgeois

  • Status changed from needs_review to positive_review

comment:11 Changed 21 months ago by chapoton

  • Status changed from positive_review to needs_work

I am happy to see this available; this will come handy for some code I am working on right now.

But the documentation is not properly formatted. I am going now to make a quick reviewer commit to fix that.

comment:12 Changed 21 months ago by chapoton

  • Authors changed from asalerno, asteele to Adriana Salerno, Ander Steele
  • Branch changed from u/asteele/compute_gauss_sums_with_gross_koblitz_formula to public/23456
  • Commit changed from 88b954e7c2bc522f4cf5d0d04de424f8296bff76 to dd10796b0bece236bd8381627cb7dcba897088c9
  • Reviewers changed from Adele Bourgeois to Adèle Bourgeois, Frédéric Chapoton
  • Status changed from needs_work to needs_review

Here it is. If you agree with my (small) changes, please set back to positive review in my name.


New commits:

87a5bd4Merge branch 'u/asteele/compute_gauss_sums_with_gross_koblitz_formula' in 8.1.b0
dd10796trac 23456 small reviewer's commit for cleanup

comment:13 Changed 21 months ago by chapoton

The patchbot is morally green. Please one of you set this ticket to positive !

comment:14 Changed 21 months ago by asalerno

  • Status changed from needs_review to positive_review

comment:15 Changed 21 months ago by vbraun

  • Status changed from positive_review to needs_work

Docbuild fails (merge in 8.1.beta1)

comment:16 Changed 21 months ago by git

  • Commit changed from dd10796b0bece236bd8381627cb7dcba897088c9 to c6536fd1a1a52971065118975e8ccde534277b50

Branch pushed to git repo; I updated commit sha1. New commits:

840ab1aMerge branch 'public/23456' of git://trac.sagemath.org/sage into t/23456/gross_koblitz
c6536fdMove imports inside gauss_sum

comment:17 Changed 21 months ago by roed

  • Status changed from needs_work to needs_review

I moved the imports inside the function, and documentation builds now.

comment:18 Changed 21 months ago by git

  • Commit changed from c6536fd1a1a52971065118975e8ccde534277b50 to 5c7db5d54bf07a7ec5194ea3041a27a2ce4b5dc1

Branch pushed to git repo; I updated commit sha1. New commits:

5c7db5dtrac 23456 one doc detail

comment:19 Changed 21 months ago by chapoton

  • Status changed from needs_review to positive_review

I changed a detail in the doc, and checked that doc builds. I am setting back to positive review.

comment:20 Changed 21 months ago by git

  • Commit changed from 5c7db5d54bf07a7ec5194ea3041a27a2ce4b5dc1 to 68dedc74951ee49ea4684b14e550d4ef940a3782
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

68dedc7trac 23456 fixing pdf documentation

comment:21 Changed 21 months ago by chapoton

There was a r""" missing at the beginning of the file.

comment:22 Changed 21 months ago by git

  • Commit changed from 68dedc74951ee49ea4684b14e550d4ef940a3782 to 95a100a63d3d75cbaea714b4f2dce2c071ac84bb

Branch pushed to git repo; I updated commit sha1. New commits:

95a100atrac 23456 missing capital for Gauss

comment:23 Changed 21 months ago by chapoton

  • Status changed from needs_review to positive_review

I was fixing details and pdf doc, now setting back to positive

comment:24 Changed 21 months ago by vbraun

  • Branch changed from public/23456 to 95a100a63d3d75cbaea714b4f2dce2c071ac84bb
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:25 follow-up: Changed 20 months ago by chapoton

  • Commit 95a100a63d3d75cbaea714b4f2dce2c071ac84bb deleted

Silly question maybe, but are we completely sure of the correctness of the code here ? I am asking because I have some problems in #23671 that could possibly come from here.

comment:26 in reply to: ↑ 25 Changed 20 months ago by kedlaya

Replying to chapoton:

Silly question maybe, but are we completely sure of the correctness of the code here ? I am asking because I have some problems in #23671 that could possibly come from here.

There is a code snippet on #23671 that checks the p-adic computation against the computation by roots of unity. Perhaps that could be added as a doctest, but not on this ticket since it's already closed.

comment:27 Changed 17 months ago by jdemeyer

  • Reviewers changed from Adèle Bourgeois, Frédéric Chapoton to Adele Bourgeois, Frédéric Chapoton
Note: See TracTickets for help on using tickets.