Cubic and quartic congruences modulo a prime. (Q1403935)

For \(p\) a prime, the author considers \(N_p(f)\), the number of solutions of \(f(x)\equiv 0\pmod p\) with \(0\leq x<p-1\) and \(f\) a cubic or quartic polynomial with integer coefficients. He derives necessary and sufficient criteria for \(N_p(f)\) to assume a prescribed value in terms of the \(k\)th term of a third-order recurrence sequence associated with \(f\) and with \(k\) linear in \(p\). In the case of a quartic polynomial \(f\) the third-order recurrence is associated to the resolvent of \(f\) (a cubic polynomial). Also, in various cases, the solutions of \(f(x)\equiv 0\pmod p\) are expressed in terms of the \(k\)th term of a recurrence sequence with \(k\) linear in \(p\). The naive way of computing \(N_p(f)\) requires exponential time (with respect to the number of digits of \(p\)). The criteria of the author, however, require polynomial time (the \(k\)th term of the recurrence \(s_k\) can be computed by matrix multiplication, and by the method of repeated squaring this requires \(O(\log k)\) multiplications). Different polynomial time methods, which can handle primes of about 100 digits, are known, cf. 5.1 of \textit{J.-P. Serre} [Bull. Am. Math. Soc., New Ser. 40, 429--440 (2003; Zbl 1047.11045)]. The latter paper also makes clear that \(N_p(f)\) is a subtle arithmetic quantity and that light on its behaviour can be shed for example by the theory of quadratic forms, class field theory, representation theory and modular forms. It is thus quite surprising to the reviewer that the author proves his (many) results by elementary methods, using only the barest rudiments of algebraic number theory. For different \(f\) the results in the approach as taken by e.g. Serre can take on a quite different form. The results of the author, however, offer the advantage that they are quite uniform. The author states (p. 44) that his results are elementary and are not easy consequences of Galois theory, and he mentions a result (1.3) which he could not prove using Galois theory. Serre and, independently, P. Stevenhagen kindly showed me straightforward Galois-theoretic proofs of several of the main results of the author, including that of (1.3). In the reviewer's opinion these are rather more illuminating than the proofs given by the author. The author states that the connection between cubic congruences and binary quadratic forms was revealed in 1992 by B. K. Spearman and K. S. Williams. However, this connection was already known to Gauss and suspected by Euler: Gauss proved Euler's conjecture that a prime \(p\) is represented by \(X^2+27Y^2\) iff \(p\equiv 1\pmod 3\) and \(X^3\equiv 2\pmod p\) has a solution mod \(p\). Since the study of \(N_p(f)\) goes back several centuries (with contributions from Cauchy, Skolem, Stickelberger to name a few), it is all the more remarkable and quite an achievement that the author, using such elementary tools, managed to find new and interesting results on this topic.