Kloosterman vs. Salié

I’ve just realized a rather obvious fact concerning the vague question at the end of my latest post on Kloostermania, which I’ll rephrase informally:

Can one guess with better than even chance that a graph like Kloostermania’s represents a Kloosterman or a Salié sum?

I had said that, for fixed p, just knowing the sum shouldn’t leave much room to make any choice except a random one. To make sense, the rule must be made more precise: you are given a bare real number, say


and you are told that it is either the value of a Kloosterman sum S(1,1;p) for some prime, or of a Salié sum T(1,-1;p) for some prime. You can win a drink of your choice by picking up the right one. What can you say? The reason it is hard to do better than heads-Kloosterman/tail-Salié is that you do not know p. If you knew the value of the prime, then you could compute the angle in [0,π] such that


and use the fact that these are supposed to be distributed differently for Kloosterman and Salié sums. For instance, the probability that θ is(conjecturally) larger than 3π/4 is bigger for Salié sums (it is 1/4) than for Kloosterman sums (about 0.09…), and hence, finding an angle in this range would give a big hint that it comes from a Salié sum (but no certainty, of course).

And now for the really obvious point: if you can, in addition to knowing S, actually see the graph of the partial sums, then — of course — you know the prime: you just have to count the steps on the graph.

It seems that similar ideas should lead to a slightly better than average guess even without knowing p: the size of S gives a lower bound on p, and for each possible guess of p, we have a guess of either Salié or Kloosterman. Presumably, combining these should be possible to get a small gain on pure chance…

(Note: readers are welcome to make a guess concerning the value above…)

Published by


I am a professor of mathematics at ETH Zürich since 2008.

One thought on “Kloosterman vs. Salié”

  1. If one is given the pair (S,p), and one is also allowed to assume that the a priori chance of a Kloosterman or Salié sum occurring is 1/2, then it would seem that the obvious guess (determined by whether theta was in [pi/4,3 pi/4] or not) would work 1/2 + 1/(2*Pi) of the time, and would be the best guest.

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *