Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

NEW CONJECTURE: There is no general upper bound.

Wadim Zudilin suggested that I make this a separate question. This follows representability of consecutive integers by a binary quadratic form where most of the people who gave answers are worn out after arguing over indefinite forms and inhomogeneous polynomials. Some real effort went into this, perhaps it will not be seen as a duplicate question.

So the question is, can a positive definite integral binary quadratic form $$ f(x,y) = a x^2 + b x y + c y^2 $$ represent 13 consecutive numbers?

My record so far is 8: the form $$6x^2+5xy+14y^2 $$ represents the 8 consecutive numbers from 716,234 to 716,241. Here we have discriminant $ \Delta = -311,$ and 2,3,5,7 are all residues $\pmod {311}.$ I do not think it remotely coincidental that $$6x^2+xy+13 y^2 $$ represents the 7 consecutive numbers from 716,235 to 716,241.

I have a number of observations. There is a congruence obstacle $\pmod 8$ unless, with $ f(x,y) = a x^2 + b x y + c y^2 $ and $\Delta = b^2 - 4 a c,$ we have $\Delta \equiv 1 \pmod 8,$ or $ | \Delta | \equiv 7 \pmod 8.$ If a prime $p | \Delta,$ then the form is restricted to either all quadratic residues or all nonresidues $ \pmod p$ among numbers not divisible by $p.$

In what could be a red herring, I have been emphasizing $\Delta = -p$ where $p \equiv 7 \pmod 8$ is prime, and where there is a very long string of consecutive quadratic residues $\pmod p.$ Note that this means only a single genus with the same $\Delta = -p,$ and any form is restricted to residues. I did not anticipate that long strings of represented numbers would not start at 1 or any predictable place and would be fairly large. As target numbers grow, the probability of not being represented by any form of the discriminant grows ( if prime $q \parallel n$ with $(-p| q) = -1$), but as the number of prime factors $r$ with $(-p| r) = 1$ grows so does the probability that many forms represent the number if any do. Finally, on the influence of taking another $\Delta$ with even more consecutive residues, the trouble seems to be that the class number grows as well. So everywhere there are trade-offs.

EDIT, Monday 10 May. I had an idea that the large values represented by any individual form ought to be isolated. That was naive. Legendre showed that for a prime $q \equiv 7 \pmod 8$ there exists a solution to $u^2 - q v^2 = 2,$ and therefore infinitely many solutions. This means that the form $x^2 + q y^2$ represents the triple of consecutive numbers $q v^2, 1 + q v^2, u^2$ and then represents $4 + q v^2$ after perhaps skipping $3 + q v^2$. Taking $q = 8 k - 1,$ the form $ x^2 + x y + 2 k y^2$ has no restrictions $\pmod 8,$ while an explicit formula shows that it represents every number represented by $x^2 + q y^2.$ Put together, if $8k-1 = q$ is prime, then $ x^2 + x y + 2 k y^2$ represents infinitely many triples. If, in addition, $ ( 3 | q) = 1,$ it seems plausible to expect infinitely many quintuples. It should be admitted that the recipe given seems not to be a particularly good way to jump from length 3 to length 5, although strings of length 5 beginning with some $q t^2$ appear plentiful.

EDIT, Tuesday 11 May. I have found a string of 9, the form is $6 x^2 + x y + 13 y^2$ and the numbers start at $1786879113 = 3 \cdot 173 \cdot 193 \cdot 17839$ and end with $1786879121$ which is prime. As to checking, I have a separate program that shows me the particular $x,y$ for representing a target number by a positive binary form. Then I checked those pairs using my programmable calculator, which has exact arithmetic up to $10^{10}.$

EDIT, Saturday 15 May. I have found a string of 10, the form is $9 x^2 + 5 x y + 14 y^2$ and the numbers start at $866988565 = 5 \cdot 23 \cdot 7539031$ and end with $866988574 = 2 \cdot 433494287.$

EDIT, Thursday 17 June. Wadim Zudilin has been running one of my programs on a fast computer. We finally have a string of 11, the form being $ 3 x^2 + x y + 26 y^2$ of discriminant $-311.$ The integrally represented numbers start at 897105813710 and end at 897105813720. Note that the maximum possible for this discriminant is 11. So we now have this conjecture: For discriminants $\Delta$ with absolute values in this sequence http://www.oeis.org/A000229 some form represents a set of $N$ consecutive integers, where $N$ is the first quadratic nonresidue. As a result, we conjecture that there is no upper bound on the number of consecutive integers that can be represented by a positive quadratic form.

share|improve this question
Neat question. Why 13, exactly? –  Pete L. Clark May 8 '10 at 19:44
This is reminscent of Conway's "15 theorem": if a positive definite quadratic form with integral matrix represents 1,2,...,15 then it represents all positive integers –  Victor Protsak May 9 '10 at 7:32
Yes, Victor. That applies to four or more variables, and the related 290 result allowing non-integral matrix is now proved. Density for positive binaries is 0 in the long run: if $B(n)$ is the count of integers from 1 to $n$ that are representable by $x^2 + y^2,$ then there is a constant $C = 0.7642...$ such that $ B(n) \sim C n / \sqrt{\log n} .$ So there is some reason to suspect, for any individual form, that large represented values are isolated or nearly isolated. Less predictable is the possibility of some new discriminant doing much better than smaller ones. –  Will Jagy May 9 '10 at 16:25
@David: This is wrong, for each fixed positively definite form the length is bounded, see fedja's answer to the question quoted by Will as a motivation. Will's point was, in fact, that it's tricky to think of the representability of consecutive numbers as independent events. –  Victor Protsak May 12 '10 at 3:02
Will, these are impressive examples of long strings, but why are there two Mondays this week? :) –  Victor Protsak May 12 '10 at 3:05
show 5 more comments

3 Answers

up vote 15 down vote accepted

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.

share|improve this answer
Goodness, thank you for your effort. First, please see David Speyer's mathoverflow.net/questions/29280/… If, as I suspect, you have shown that Schinzel's H implies an answer to David's question, you might put a relatively short answer there and link back to this. Next, note among my questions, we did eventually confirm that any positive binary represents arbitrarily long arithmetic progressions of primes by Green-Tao, but being primes these numbers will be very far from consecutive. Consider registering on MO! –  Will Jagy Jul 31 '10 at 2:19
Just to record this, my strongest conjecture is that (for my favorite discriminants $\Delta = -q$) there is a string of $p$ consecutive integers (where $p$ is the first quadratic nonresidue $\pmod q$) that are integrally represented by ALL the positive forms of discriminant $-q.$ So, for $\Delta = -311$ we are asking for 11 numbers, for $-479$ we want 13 numbers, for $-1559$ we want 17 consecutive numbers. Note that I cannot exhibit anything even for $-71.$ But as long as I'm just making up things up, why not? –  Will Jagy Jul 31 '10 at 3:36
@Jagy, your "stronger conjecture" follows immediately from Hypotheses H by the same argument I gave --- If you think about Lemma 2, it also shows (under the same hypothesis) that for every ideal class [c] in C, there exists an ideal N_c of norm n*prod_{A_i} p_i. Correspondingly, the integers dM+k+j are represented by ALL positive forms of discriminant -q. –  user631 Aug 2 '10 at 4:53
Powerpuff, I asked them to merge your two accounts under the registered one. I did not notice your comment until today. The intention of the software is that a comment immediately after an answer or question, but by someone else, is brought to the user's attention if they leave MO and then log back in. It does not always work anyway, I am not sure what variables affect that. So anyway, this comment and yours on August 2 are counted as comments to your post. Have you any idea how to search for seven consecutive numbers represented by all forms with $\Delta = -71$? Will. –  Will Jagy Aug 13 '10 at 3:46
add comment

I'm making this an answer to make it more visible, a suggestion of Pete L. Clark that seems correct to me.

Wadim Zudilin has been running a computer program of mine on a fast computer. Today we found a string of length 11. The form is $ 3 x^2 + x y + 26 y^2 $ of discriminant $\Delta = -311.$ The numbers represented run from 897105813710 to 897105813720. Note that this is the longest possible string for this discriminant, as the first quadratic nonresidue $\pmod {311}$ is $11.$ The first number in the string is $\equiv 0 \pmod {311},$ indeed 897105813710 = 2 * 5 * 311 * 288458461. So at this point I conjecture that there is NO general upper bound on the number of consecutive integers that can be represented by a positive form. The discriminants I have in mind are $\Delta = -p,$ where $ p \equiv 7 \pmod 8$ is a prime with a large minimal nonresidue. Such primes can be found in particular among http://www.oeis.org/A000229 although not all of these are $\equiv 7 \pmod 8.$ The conjecture, to be more specific, is that for any of these desirable discriminants, there is a represented set of consecutive integers of length $N,$ where $N$ is the smallest quadratic nonresidue $\pmod p. $

Now, I admit we do not have any sequence of length 12 or 13 or 14. But, as with Jodie Foster in "Contact," I am the scientific type who comes around to depending on faith by the end of the movie. Meanwhile the religious guy, Matthew McConaughey, comes around to accepting the scientific conclusions.

As Wadim comments, for lengths 12 and 13 we are looking at discriminant $-479,$ the first nonresidue for $479$ is 13. For lengths 14,15,16,17 we must move to $-1559.$ But it is truly astonishing how much higher we must run the target numbers as the length increases, and as the class number and absolute value of the discriminant increase. Wadim has machines available that have built-in integers up to about $10^{18}$ and that has been critical. I have a very different program design that relies on factoring, suitable for Mathematica or gp-Pari, this program being asymptotically faster. But gp-Pari is new to me.

My recent question on the Green-Tao theorem and positive quadratic forms was an attempt to get people thinking about how to prove the non-existence of a general bound for this problem.

Finally, many thanks to Wadim Zudilin.

share|improve this answer
I could probably add that we have several length 11 examples for discriminant -479, but there Will (and me, of course, as well) expect to get lengths 12 and 13, as the least quadratic nonresidue is 13. Long live quadratic (non)residues! –  Wadim Zudilin Jun 18 '10 at 7:37
add comment

Here's a heuristic that suggests why arbitrarily large strings of consecutive numbers should be representable by some binary quadratic form. For simplicity consider a prime $p$ that is $3\pmod 4$ so that $-p$ is a fundamental discriminant. Suppose that $p$ has been chosen in such a way that all the primes $\le k$ are quadratic residues $\pmod p$. Suppose there are $h$ quadratic forms of discriminant $-p$ (and note that there is only one genus).

Recall that a number $n$ is represented by some form of discriminant $-p$ if every prime factor $\ell$ of $n$ satisfies $\chi(\ell)=1$. As discussed in my answer to Achieving consecutive integers as norms from a quadratic field we should expect to find many strings of $k$ consecutive numbers, each of which is representable by some form of discriminant $-p$.

In my answer to that question, I focused on such strings of (almost) prime numbers, but the same Hardy-Littlewood heuristics would predict lots of strings $n+1$, $\ldots$, $n+k$ where each $n+j$ is divisible only by primes that are quadratic residues $\pmod p$, and each $n+j$ has a typical number of prime factors. Under the restriction that all prime factors of $n$ are quadratic residues $\pmod p$, if $n$ is large then typically it will have about $\frac 12 \log \log n$ such prime factors. Moreover we may expect these prime factors to be roughly equally distributed in the class group (which is of fixed size $h$). Thus since there are $2^{\omega(n)}$ factorizations of $n$ as a product of two ideals, we would expect that typically there are many such factorizations with one of the factors lying in a prescribed ideal class.

Summarizing one would expect that there are many strings $n+j$ ($1\le j\le k$) with each $n+j$ composed of about $\frac 12\log \log n$ primes that are all quadratic residues $\pmod p$, and (typically) each such $n+j$ would be represented by every form of discriminant $-p$.

It should be possible with a little effort to turn this into a precise Hardy-Littlewood type conjecture, but I don't see any hope of a proof.

The heuristic described above is probably classical. One place where this heuristic is described is a paper of Blomer and Granville: see pages 9 and 10 of http://www.dms.umontreal.ca/~andrew/PDF/quadraticforms.pdf

share|improve this answer
Very nice. I had some email recently from one of Andrew Granville's etudiants dirigibles, who wanted information on positive ternary forms. It is "deleted" below, but Frictionless Jellyfish left an answer in 2010 showing that Schinzel's Hypothesis H implies the strongest conjecture i had. I did not accept it (not sure why) and FJ deleted many unnaccepted answers last August. –  Will Jagy Aug 21 '13 at 4:16
Frictionless Jellyfish's answer is very nice indeed. Of course if I had seen that, there wouldn't have been any need to write mine up. –  Lucia Aug 21 '13 at 16:13
Lucia, I guess I missed some doings overnight. Gerry Myerson posted F.J.'s answer again, it was visible to those with over 10,000 points in any case. Then someone undeleted F.J.'s answer. meta.mathoverflow.net/questions/665/… –  Will Jagy Aug 21 '13 at 19:01
Oh, and etudiants dirigibles is French for students in hot air balloons. –  Will Jagy Aug 21 '13 at 19:06
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.