Timeline for $p$-adic sums of $p$ terms
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 11, 2018 at 15:34 | answer | added | Julian Rosen | timeline score: 3 | |
| Sep 10, 2018 at 0:43 | comment | added | Mark | Due to partial-fraction decomposition it would make sense to first restrict the question to special cases, like $f(x) = 1/(x+a)^n$ for some constants $a,n$. | |
| Sep 9, 2018 at 19:38 | comment | added | Itai Bar-Natan | @Speiser Good point; I forgot about the fast polynomial evaluation algorithm. In fact I believe I see a way to apply this arbitrary sums of rational functions -- I might write this up later. Perhaps I should have asked whether an algorithm could be faster than a general algorithm for summing $n$ terms applied to $n = p$. | |
| Sep 9, 2018 at 18:55 | comment | added | Dror Speiser | @Julian: factorials can be computed in square root time using fast polynomial evaluation, so the binomial coefficient identity gives a $O(\sqrt{p})$ algorithm :) My guess is that this can be achieved for general rational functions. | |
| Sep 9, 2018 at 18:00 | history | edited | Itai Bar-Natan | CC BY-SA 4.0 |
edited body
|
| Sep 9, 2018 at 16:32 | comment | added | efs | I don't have a copy with me right now, but maybe the chapter on $p$-adic $L$-functions in volume II of Henri Cohen's book on Analytic number theory might help, including the exercises. | |
| Sep 9, 2018 at 15:23 | comment | added | Julian Rosen | Some expressions for the harmonic sum: $H_{p-1}\equiv ({2p\choose p}-2)/(4p)\equiv -p^2 B_{p-3}/3\equiv -p^2\zeta_p(3)\mod p^3$. I'm not sure if any of these are fast to compute, though. | |
| Sep 9, 2018 at 13:28 | comment | added | Itai Bar-Natan | Oops, fixed that. | |
| Sep 9, 2018 at 13:27 | history | edited | Itai Bar-Natan | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Sep 9, 2018 at 13:09 | comment | added | David E Speyer | You say "Let $f$ be a rational polynomial." Do you mean a rational function, in view of your motivation? | |
| Sep 9, 2018 at 12:32 | history | asked | Itai Bar-Natan | CC BY-SA 4.0 |