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

I have two related questions on the representability of integers by quadratic forms in two variables :

(1) Let $f: {\mathbb Z} \times {\mathbb Z} \to {\mathbb Z} $ be such a quadratic form, i.e. we have $f(x,y)=ax^2+bxy+cy^2+dx+ey+g$ for some integer constants $a,b,c,d,e,g$. Suppose that $f$ is not surjective, i.e. some integer is not represented by $f$. Is it true that there is an integer constant $C$ such that in any block of $C$ consecutive integers, at least one of them is not represented by $f$ ?

(2) If the answer to (1) is yes, is there a uniform bound ? In other words, is there a uniform constant $C$ such that for any non-surjective $f$, in any block of $C$ consecutive integers, at least one of them is not represented by $f$ ?

Update : Good answers to my original questions appeared quickly. It seems the only interesting subquestion left is the one asked by fedja : (2') is there a universal $C$ such that for any $f$ with positive definite quadratic part, in any block of $C$ consecutive integers, at least one of them is not represented by $f$ ?

One may also ask, (3) is there a universal $C$ such that for any non-surjective and irreducible $f$, in any block of $C$ consecutive integers, at least one of them is not represented by $f$ ?

share|improve this question
1  
A point of terminology -- Do you really mean quadratic form? If so then $f(x,y)=ax^2+bxy+cy^2$. –  SJR May 6 '10 at 11:31
1  
@Ewan: one trivial typo in your $f(x,y)$ -- should be $dx+ey$ (not $dx+ex$). Can I suggest that you remove $+g$ from $f(x,y)$ because it does not influence on your problem. Finally, it seems important to say something about signature: if the form is sign definite, then the property "not represented by $f$" holds for at least half of integers. –  Wadim Zudilin May 6 '10 at 12:02
    
@Wadim: just because 1/2 the integers aren't represented doesn't mean that C exists, right? Somehow more pertinent would be that if f is not surjective mod p for some p then it's not surjective and in this case C definitely exists as C=p will do. –  Kevin Buzzard May 6 '10 at 12:20
    
@Kevin: I just wonder whether the problem is trivial in the sign definite case (the density of integers represented by $ax^2+bxy+cy^2$ is zero, isn't it? the linear terms shouldn't influence on this). But you are right: if the mod $p$ reduction works then there is no difference in doing all the cases in one way. –  Wadim Zudilin May 6 '10 at 12:38
1  
@Wadim: of course you're right. I was misled by thinking it was positive definite in 1 variable. To get rid of the linear terms you can multiply by a constant (which will affect density issues in the obvious way) and then complete the square. –  Kevin Buzzard May 6 '10 at 13:11

3 Answers 3

up vote 9 down vote accepted

Such a $C$ does not exist, if I got it right.

My example is the function $f(x,y)=(2x+1)(5y+1)$. An integer is represented by $f$ iff it can be written as the product of an odd integer and a number which is 1 mod 5. So for example it is not hard to check that 2 cannot be written in this way (the odd number had better be $\pm1$, and neither of $\pm2$ are 1 mod 5). However a tedious construction using the Chinese Remainder Theorem gives arbitrarily large sequences of consecutive integers which are representable by $f$.

Let me explain a bit more about the CRT argument. Clearly any positive integer $N$ can be written as the product $M2^r$ of an odd integer and a power of two. If furthermore this odd integer $M$ is divisible by three distinct primes, one of which is 2 mod 5, one of which is 3 mod 5 and one of which is 4 mod 5, then moving one of these factors $p$ from $M$ to the power of two gives $N=(M/p)(p2^r)$, and if $2^r$ isn't 1 mod 5 then there will be some $p$ such that $p2^r$ will be 1 mod 5, so we have our decomposition of $N$ which is hence representable by $f$.

So it suffices to find arbitrarily large strings of integers each of which has a prime factor which is 2 mod 5, a prime factor which is 3 mod 5 and a prime factor which is 4 mod 5 (in fact by using sign changes one can even get away with primes which are 2 mod 5). But now this is easy: enumerate the primes which are 2 mod 5, 3 mod 5 and 4 mod 5, let C_n be the product of the n'th 2-mod-5, the n'th 3-mod-5 and the n'th 4-mod-5, and now choose a big positive $N$ with $N=0$ mod C_1, $N+1=0$ mod $C_2$,... $N+10^6=0$ mod $C_{10^6+1}$ (such an $N$ exists by CRT) and there you have it.

share|improve this answer
    
@Kevin: Taking $f(x,y)=x^2+y^2$ one gets no negative integer represented by the form. So, $C$ again does not exists by taking the range $-C\le n\le-1$. –  Wadim Zudilin May 6 '10 at 13:20
    
Wadim, you need to show that either every block of $C$ consecutive integers has an element not in the range of $f$, or that some particular block has all its elements represented (as Kevin does). –  Robin Chapman May 6 '10 at 13:57
    
@Wadim: we are interpreting the question in different ways! My interpretation is that one is supposed to find C such that in any block of C consecutive integers, one is not represented. Just because -3<=n<=-1 are not represented does not mean that C=3 is OK, because 8,9,10 can all be represented. –  Kevin Buzzard May 6 '10 at 13:57
    
Kevin, wouldn't $(2x+1)(3y+1)$ be easier? Let $C_n=p_n$ where $p_n$ is the $n$-th prime congruent to 2 mod 3, and proceed in roughly the same manner. –  Robin Chapman May 6 '10 at 14:06
    
I was worried about sign issues! Any number is odd*(+-power of 2) and you change the sign to make the power of 2 equal to 1 mod 3 :-/ –  Kevin Buzzard May 6 '10 at 14:10

"If the question is rectricted to positive definite forms, then a C exists. ".

If $C$ is allowed to depend on the form, it is quite simple. Shifting to get rid of linear terms, completing the square and multiplying by an appropriate integer, one can reduce the problem to showing that for every positive integers $b$ and $D$ the quadratic form $x^2+by^2$ cannot represent too many successive integers divisible by $D$. Now just choose a prime $p>D$ such that $-b$ is not a quadratic residue modulo $p$ (you do not need Dirichlet theorem or even quadratic reciprocity law to find such prime though these two tools make its existence obvious) and notice that the form cannot represent any number divisible by $p$ but not by $p^2$. But such numbers are fairly dense among the ones divisible by $D$.

The interesting question is whether one can find a universal $C$ that would work for every quadratic polynomial of 2 variables with integer coefficients and positive definite quadratic part.

share|improve this answer
    
Fedja, you didn't give me a chance to write down the proof I had developed in my dreams! :) It's exactly the same one (but I did the reduction to $(4*a*c-b^2)*X^2+Y^2$ explicitly), and exactly the same question (is it possible to get a universal $C$) arises... +1. –  Wadim Zudilin May 6 '10 at 22:36

Seems worth recording my thoughts so far. I am sticking with positive forms, which means homogeneous. My guess of $C=31$ was probably larger than necessary, but we will see. Certainly I think there is a finite uniform $C$ and it can be taken quite small.

It turns out to be quite difficult to have a positive binary represent any string of 7 consecutive positive integers. I finally managed it, $x^2 + x y + 18 y^2$ represents the numbers from 1,953,139 to 1,953,145. Of course, even for this form, most intervals of length 7 contain a nonrepresented number.

If the discriminant is even there is a congruence obstruction on represented numbers mod 4 or mod 8, of a nature that prevents strings longer than 5. The form $x^2 + 2 y^2$ does well, many strings of length 5 as high as I could check.

If the discriminant is 5 mod 8 no numbers 2 mod 4 are represented.

So we have explicit bounds of length no more than 5 unless $ \Delta \equiv 1 \pmod 8.$ Even here, for composite discriminant, say $ 3 | \Delta $ any form of that discriminant is restricted to all quadratic residues or all quadratic nonresidues $ \pmod 3 ,$ maximum length 3. Similar for $ 5 | \Delta $ or $ 7 | \Delta .$

The way to get big lengths is prime discriminants with either a long set of consecutive residues or a long set of consecutive nonresidues. Residues seem a better bet, as if 2,3,5 are residues then so are 1,2,3,4,5,6. And, indeed we have $ 1953139 \equiv 0 \pmod {71}, \ldots, \; 1953145 \equiv 6 \pmod {71} .$ Note that 7 is a nonresidue mod 71, the first nonresidue is always prime (for a prime modulus).

Note that Fedja's argument also concerns the first nonresidue $q.$ Whatever else may or may not matter, the maximum length is $2 q - 1,$ for a possible interval from $ k q^2 - q + 1$ through to $ k q^2 + q - 1.$

share|improve this answer
2  
$ 6 x^2 + 5 x y + 14 y^2 $ represents the 8 consecutive numbers from 716,234 to 716,241. $ \Delta = -311,$ and 2,3,5,7 are all residues $\pmod {311}.$ By the way, having now checked, modulo any given prime, the longest string of residues need not start with 1. Taking the prime 31, the longest string of consecutive residues is 7,8,9,10. But with $\Delta = -p$ with $p$ prime and $p \equiv 7 \pmod 8,$ only residues are represented among numbers not divisible by $p,$ the discriminant has just one genus. So long strings of nonresidues are little help. –  Will Jagy May 7 '10 at 22:56

Your Answer

 
discard

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.