I just wanted to remark that if $p$ is a prime such that
$\ell$ splits in $F = \mathbb{Q}(\sqrt{-p})$ for all $\ell \le N$,
then one may prove the existence of $N$ consecutive integers which
are norms of integers in $\mathcal{O}_F$, providing one is willing
to assume a standard hypothesis about prime numbers, namely,
Schinzel's Hypothesis H.
First, note the following:
Lemma 1: If $C$ is an abelian group of odd order, then there exists a finite
(ordered) set $S = \{c_i\}$ of elements of $C$ such that every element in $C$ can be
written in the form
$\displaystyle{\sum \epsilon_i \cdot c_i}$
where $\epsilon_i = \pm 1$.
Proof: If $C = A \oplus B$, take $S_C = S_A \cup S_B$. If $C
= \mathbb{Z}/n \mathbb{Z}$ then take $S = \{1,1,1,\ldots,1\}$ with
$|S| = 2n$.
Let $C$ be the class group of $F$. It has odd order, because
$2$ splits in $F$ and thus $\Delta_F = -p$.
Let $S$ be a set as in the lemma. Let $A$ denote an ordered
set of distinct primes $\{p_i\}$ which split in $\mathcal{O}_F$ such
that one can write $p_i = \mathfrak{p}_i \mathfrak{p}'_i$ with
$[\mathfrak{p}_i] = c_i \in C$, where $c_i$ denotes a set of elements
whose existence was shown in Lemma 1.
Lemma 2: If $n$ is the norm of some ideal $\mathfrak{n} \in \mathcal{O}_F$,
and $n$ is not divisible by any prime $p_i$ in $A$, then
$$n \cdot \prod_{A} p_i$$
is the norm of an algebraic integer in $\mathcal{O}_F$.
Proof: We may choose
$\epsilon_i = \pm 1$ such that
$\displaystyle{[\mathfrak{n}] + \sum \epsilon_i \cdot c_i = 0 \in C}$.
By assumption, $[\mathfrak{p}_i] = c_i \in C$ and thus
$[\mathfrak{p}'_i] = -c_i \in C$. Hence the ideal
$$\mathfrak{n}
\prod_{\epsilon_i = 1}
{ \mathfrak{p}}
\prod_{\epsilon_i = -1}
\mathfrak{p}'$$
is principal, and has the desired norm.
By the Chebotarev density theorem (applied to the Hilbert class field
of $F$), there exists a set $A$ of primes as above which avoids any fixed finite set of
primes. In particular, we may
find $N$ such sets which are pairwise distinct and which contain
no primes $\le N$. Denote these sets by $A_1, \ldots, A_N$.
By the Chinese remainder theorem, the set of integers $m$ such that
$$m \equiv 0 \mod p \cdot (N!)^2$$
$$m + j \equiv 0 \mod \prod_{p_i \in A_j} p_i, \qquad 1 \le j \le N$$
is of the form $m = d M + k$ where $0 \le k < M$, $d$ is arbitrary, and $M$
is the product of the moduli.
Lemma 3: Assuming Schinzel's Hypothesis H, there exists infinitely many integers
$d$ such that
$$ P_{dj}:= \frac{dM + k + j}{j \cdot \prod_{p_i \in A_j} p_i}$$
are simultaneouly prime for all $j = 1,\ldots,N$.
Proof: By construction, all these numbers are coprime to $M$ (easy check).
Hence, as $d$ varies, the greatest common divisor of the product of these
numbers is $1$, so Schinzel's Hypothesis H applies.
Let $\chi$ denote the quadratic character of $F$. Note that
$dM + k + j = j \mod p$, and so
$\chi(dM + k + j) = \chi(j) = 1$ (as all primes less than $N$ split in $F$).
Moreover, $\chi(p_i) = 1$ for all
primes $p_i$ in $A_j$
by construction. Hence
$\chi(P_{dj}) = 1$. In particular, if $P_{dj}$ is prime, then
$P_{dj}$ and $j \cdot P_{dj}$ are norms of (not necessarily principal) ideals in
the ring of integers of $F$. By Lemma 2, this implies that
$$dM + k + j = j \cdot P_{dj} \prod_{p_i \in A_j} p_i$$
is the norm of some element of $\mathcal{O}_F$ for all $j = 1,\ldots, N$.
One reason to think that current sieving technology will not be sufficient
to answer this problem is the
following: when Sieving produces a non-trivial lower bound, it usually
produces a pretty good lower bound. However, there are no good (lower) bounds known for the following problem: count the number of integers $n$
such that $n$, $n+1$, and $n+2$ are all sums of two squares. Even for the
problem of estimating the number of $n$ such that $n$ and $n+1$ are both sums of squares is tricky - Hooley implies that the natural sieve does not give lower bounds
(for reasons analogous to the parity problem). Instead,
he relates the problem to sums of the form
$\displaystyle{\sum_{n < x} a_n a_{n+1}}$ where
$\sum a_n q^n = \theta^2$ is a modular form. In particular, he
implicitly uses
automorphic methods which won't work
with three or more terms.
Hi, Pete. There are a few observations related to this, not widely known although basic, and that includes your colleague. First, Conway gives a quick proof on page 142 of The Sensual Quadratic Form, including over the rationals.
Next, also Conway, the form (five variables) that he and Schneeberger found that represents all the numbers from 1 to 289, fails to represent 290, then represents 291 and on forever, he initially called Methusaleh. It is just a binary added to a ternary that represents the numbers from 1 to 28 consecutive, discriminant 29. However, for ternaries that is not the record. The form he called Little Methusaleh, discriminant 31, represents 1 to 30 consecutive. The theorem is in this material, as the conditions for a positive ternary to represent, say, 1,2,3,5, places strong restrictions on a partly reduced form. Kap wrote this sort of argument up several times, including a repeat in the unpublished 1996 Classification. It is quite easy. OK, Little Methusaleh and your result over the integers are proved on page 81 of The Sensual Quadratic Form
Finally, a positive form is anisotropic at the "prime" infinity. In Cassels Rational Quadratic Forms he shows global relations on the Hilbert Norm Residue symbol that show that any ternary is anisotropic at an even number of primes. So a positive ternary is anisotropic at an odd number of finite primes. Taken with the observation above that at least one number below 31 is missed, and a positive ternary fails to integrally represent an infinite number of positive integers.
I will look up some of my tables and fill things in. Note that some of this is discussed in an early article by William Duke, 1997 Notices, but he mistyped the form with discriminant 29.
Let's see, Conway and Schneeberger probably had an acceptable proof of the 15 Theorem scattered about, but it never got put together. Bhargava was looking for diversions from his own dissertation, Conway mentioned this in passing. Bhargava showed the fundamental result that one of these forms must have a regular ternary as a sub-form, thus the project became a careful inspection of my paper with Kap on all possible regular ternaries. Also, correspondence between Kap and Bhargava first revealed some important errors in Magma relating to calculating the spinor genus, and hilarity ensued.
EDIT: thinking about the history question, it is quite possible that this result was never written down as a separate proposition, by Gauss, Legendre, etc. The reason I suggest this is the great weight placed on positive ternary forms missing certain "progressions," in the language of Jones, Dickson, other early books. So, in Jones, chapter 8, we read "Thus there will be a finite number of arithmetical progressions of this type" of numbers not represented by any form in the genus under consideration. Not much motivation for proving that a form misses at least one number if you are going to quickly show that it misses an entire arithmetic progression.
EDIT TOOO: note that Conway replaces the prime usually called $\infty$ by the prime $-1.$
No definite ternary form is universal
However, a simple argument shows that
any definite ternary form must fail to
represent infinitely many integers,
even over the rationals. For if a
ternary form $f$ of determinant $d$
represents anything in the $p$-adic
squareclass of $-d$ over $\mathbf
> Q_p,$ then it must be $p$-adically
equivalent to $[ -d,a,b]$ where the
"quotient form" $[a,b]$ has
determinant $-1,$ and so $p$-adically,
$f$ must be the isotropic form $[
> -d,1,-1].$
But a positive definite form fails to
represent $-1,$ and so it is not
$p$-adically isotropic for $p=-1.$ By
the global relation, there must be
another $p$ for which it is not
$p$-adically isotropic, and so it
also fails to represent all numbers in
the $p$-adic square-class of $-d$ for
this $p$ too!
The Three Squares Theorem illustrates
this nicely--the form $[ 1,1,1]$ fails
to represent $-1$ both $-1$-adically
and $2$-adically. In the Third
Lecture, we showed that The Little
Methusaleh Form $$ x^2 + 2 y^2 + y z
> + 4 z^2 $$ fails to represent 31. We now see that since it fails to
represent the $-1$-adic class of its
determinant $-31/4$ (i.e., the
negative numbers), it must also fail
to represent the infinitely many
positive integers in the $31$-adic
squareclass of $-31/4.$
Best Answer
Theorem. Let $Q(x_1,\dots,x_k)$ be a positive definite integral quadratic form in $k\geq 2$ variables. Then the number of integral representations $Q(x_1,\dots,x_k)=n$ satisfies $$r_Q(n)\ll_{k,\epsilon}n^{k/2-1+\epsilon}.$$ The implied constant depends only on $k$ and $\epsilon$, so it is independent of the actual coefficients of $Q$.
Remark. The "Added 1" section, posted with the permission of Valentin Blomer, contains a more precise result for $k=4$.
Proof. We induct on $k$, and for simplicity we do not indicate the dependence of implied constants on $k$. The case $k=2$ is classical and goes back to Gauss (see the "Added 2" section for more details). So let $k\geq 3$, and assume that the statement holds with $k-1$ in place of $k$. We can assume that $$ Q(x_1,\dots,x_k)=\sum_{1\leq i,j\leq k} a_{ij}x_ix_j$$ is Minkowski reduced. In particular, $a_{ij}=a_{ji}$ and $$ 0<a_{11}\leq a_{22}\leq\dots\leq a_{kk}. $$ Then we have a decomposition $$ Q(x_1,\dots,x_k)=\sum_{i=1}^k h_i\left(\sum_{i\leq j\leq k}c_{ij}x_j\right)^2,$$ where $h_i\asymp a_{ii}$, $c_{ii}=1$ and $c_{ij}\ll 1$ (see Theorem 3.1 and Lemma 1.3 in Chapter 12 of Cassels: Rational quadratic forms). In particular, the coefficients of $Q$ satisfy $$ a_{11}\dots a_{kk}\asymp h_1\dots h_k=\det(Q),$$ hence also $a_{ij}\ll a_{kk}\ll\det(Q)$ and $h_k\asymp a_{kk}\gg\det(Q)^{1/k}$.
We fix the positive integer $n$, and we consider the integral representations $Q(x_1,\dots,x_k)=n$. The number of representations with $x_k=0$ is $\ll_{\epsilon}n^{k/2-3/2+\epsilon}$ by the induction hypothesis, so we can focus on the representations with $x_k\neq 0$. From the above, we see immediately that $x_k\ll\sqrt{n}\det(Q)^{-1/(2k)}$, and then also that $x_{k-1}\ll\sqrt{n}$, then $x_{k-2}\ll\sqrt{n}$, and so on, finally $x_3\ll\sqrt{n}$. It follows that there are $\ll n^{(k-2)/2}\det(Q)^{-1/(2k)}$ choices for the $(k-2)$-tuple $(x_3,\dots,x_k)$ such that $x_k\neq 0$. Fixing such a tuple, we are left with an inhomogeneous binary representation problem $$ a_{11}x_1^2 + 2a_{12}x_1x_2 + a_{22}x_2^2 + d_1 x_1 + d_2 x_2 + e = 0 $$ with fixed integral coefficients $d_1,d_2\ll\sqrt{n}\det(Q)$ and $e\ll n\det(Q)$. Using Lemma 8 in this paper of Blomer and Pohl, it follows that the number of choices for $(x_1,x_2)$ is $\ll_\epsilon n^\epsilon\det(Q)^\epsilon$. Summing up, we get $$ r_Q(n)\ll_{\epsilon} n^{k/2-3/2+\epsilon} + n^{(k-2)/2+\epsilon}\det(Q)^{-1/(2k)+\epsilon} \ll n^{k/2-1+\epsilon},$$ and we are done.
Added 1. I have been in touch with Valentin Blomer about the original question, and my answer above incorporated a key input from him. More importantly, he realized that the above argument together with some automorphic input allows one to prove, for the case of $k=4$ variables, the striking uniform upper bound (with an absolute implied constant) $$r_Q(n) \ll \sigma(n).$$ Here is the argument of Valentin Blomer, posted with his permission. For $n\leq\det(Q)^{10}$, the last line of the inductive proof above gives $$ r_Q(n)\ll_{\epsilon} n^{1/2+\epsilon} + n^{1+\epsilon}\det(Q)^{-1/8+\epsilon} \ll n^{79/80+2\epsilon},$$ so we can (and we shall) assume that $n>\det(Q)^{10}$. We decompose the $\theta$-series of $Q$ uniquely as $$\theta_Q(z) = E(z) +S(z) = \sum_{n=1}^\infty a(n) e(nz) + \sum_{n=1}^\infty b(n) e(nz)$$ into an Eisenstein series and a cusp form of weight $2$ and level $N$, which is the level of $Q$. Accordingly, $r_Q(n)=a(n)+b(n)$, so it suffices to show that $a(n)\ll\sigma(n)$ and $b(n)\ll\sigma(n)$. The first bound was proved by Gogishvili (Georgian Math. J. 13 (2006), 687-691.), as follows from (2) and (13)-(14) in his paper. Therefore, it suffices to prove the second bound. We write $$S = \sum_{f \in B} c(f) f$$ in terms of an orthonormal Hecke eigenbasis $B$ for $S_2(N, \chi)$, where $\chi$ is a quadratic character and the inner product is given by $$(f, g) = \int_{\Gamma_0(N)\backslash \mathcal{H}} f(z)\bar{g}(z) \frac {dx\, dy}{y^2}.$$ We write $f(z) = \sum_n \lambda_f(n) e(nz)$, so that $b(n) = \sum_f c(f) \lambda_f(n)$. We avoid any use of Eichler/Deligne, among other things because it would require us to deal with oldforms carefully. Instead, we use the Petersson formula and Weil's bound for Kloosterman sums (together with Cauchy-Schwarz and Parseval): $$\begin{split} |b(n) |^2 \| S \|_2^{-2} n^{-1} & \leq n^{-1} \sum_f |\lambda_f(n)|^2 \ll 1 + \sum_{c} \frac{1}{c} S_{\chi}(n, n, c) J_1\left(\frac{4\pi n}{c}\right)\\ & \ll 1 + \sum_{c} \frac{(n, c)^{1/2}\tau(c)}{c^{1/2}} \min\left(\frac{n}{c}, \frac{c^{1/2}}{n^{1/2}}\right) \ll_\epsilon n^{1/2 + \epsilon}, \end{split}$$ so that $$b(n) \ll_\epsilon \| S \|_2 n^{3/4 + \epsilon}.$$ We have, by Lemma 4.2 of Blomer (Acta Arith. 114 (2004), 1-21.), $$\| S \|_2 \ll_\epsilon \det(Q)^{2+\epsilon},$$ whence in the end $$b(n) \ll_\epsilon \det(Q)^{2+\epsilon} n^{3/4 + \epsilon} \leq n^{19/20+2\epsilon}.$$ This concludes the proof. We note that for the twisted Kloosterman sum, the Weil-Estermann bound is not always true for higher prime powers, see Section 9 of Knightly-Li (Mem. Amer. Math. Soc. 224 (2013), no. 1055), but it is true for the case of quadratic characters that we are using here.
Added 2. Let me provide the details for the case $k=2$. Without loss of generality, $$Q(x,y)=ax^2+bxy+cy^2$$ is a reduced form. That is, $$|b|\leq a\leq c,\qquad\text{whence also}\qquad a\ll\det(Q)^{1/2}.$$ The equation $Q(x,y)=n$ can be rewritten as $$(2ax+by)^2+4\det(Q)y^2=4an.$$ We can assume that there are (integral) solutions with nonzero $y$, for otherwise there are at most two solutions. In this case, $$n\geq\det(Q)/a\gg a.$$ The equation factors in the ring of integers of an imaginary quadratic number field, hence a standard divisor bound argument combined with the previous display yields that the number of solutions is $$\ll_\epsilon(an)^\epsilon\ll_\epsilon n^{2\epsilon}.$$