For the Gauss sums which are defined by S_n(a,q) := \sum_{x (mod q)} e(ax^n/q), Stechkin (1975) conjectured that the quantity A := \sup_{n,q\ge 2} \max_{\gcd(a,q)=1} |S_n(a,q)|/q^(1-1/n) is finite. Shparlinski (1991) proved that A is finite, but in the absence of effective bounds on the sums S_n(a,q) the precise determination of A has remained intractable for many years. Using recent work of Cochrane and Pinner (2011) on Gauss sums with prime moduli, in this paper we show that with the constant given by A = |S_6(4787,4606056)|/4606056^(5/6) = 4.709236... one has the sharp inequality |S_n(a,q)| \le Aq^(1-1/n) for all n,q \ge 2 and all integers a with gcd(a,q)=1. One interesting aspect of our method is that we apply effective lower bounds for the center density in the sphere packing problem due to Cohn and Elkies (2003) to optimize the running time of our primary computational algorithm.

16 pages, 3 figures, 2 tables