Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the number of prime solutions to a system of quadratic equations Fraser, Robert 2013

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2013_spring_fraser_robert.pdf [ 433.44kB ]
Metadata
JSON: 24-1.0071953.json
JSON-LD: 24-1.0071953-ld.json
RDF/XML (Pretty): 24-1.0071953-rdf.xml
RDF/JSON: 24-1.0071953-rdf.json
Turtle: 24-1.0071953-turtle.txt
N-Triples: 24-1.0071953-rdf-ntriples.txt
Original Record: 24-1.0071953-source.json
Full Text
24-1.0071953-fulltext.txt
Citation
24-1.0071953.ris

Full Text

On the Number of Prime Solutions to a System of Quadratic Equations by Robert Fraser  A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Mathematics)  THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) April 2013 c Robert Fraser 2013  Abstract Consider the system of quadratic diophantine equations bX 2 − aY 2 = 0  bX · Y − eY 2 = 0 constrained to the prime numbers contained in the box [0, N ]2n . The HardyLittlewood circle method is applied to show that, under some local conditions on a, b, and e, the number of prime solutions contained in the box is N 2n−4 asymptotic to a constant times (log , where the constant depends on a, N )2n b, and e.  ii  Preface The strategy of applying the Hardy-Littlewood Circle Method to determine the number of prime solutions to a system of quadratic equations is wellknown and not an invention of the author. The strategy for the estimates appearing in Chapter 4 was devised by Akos Magyar. The proofs for Lemmas 4.3.1 and 4.3.2 were written by A. Magyar. Vaughan’s Identity is a well-known result in additive number theory due to R. C. Vaughan appearing in [7], and the exposition given in this paper is based on the exposition given by T. Gowers in [4]. The strategy for the mean value estimate in Chapter 5 was devised by A. Magyar. The singular series appearing in Chapter 5 is similar to the one given in J. Blair’s thesis [1]. The decomposition of the minor arcs given in Chapter 6 is standard, and is similar to the decomposition of the minor arcs given in chapter 8 of M. Nathanson’s book [6]. The techniques used to evaluate the singular series in Chapter 7 were suggested by A. Magyar. The convergence of the singular series is based on the convergence of the singular series in J. Blair’s thesis [1]. The proof that the singular series does not vanish is the original, unpublished work of the author. The estimation of the singular integral in Chapter 8 appears in J. Blair’s thesis [1], and is included in this thesis for expository purposes only. The strategies for the results in Appendix A and Appendix B were devised by Akos Magyar.  iii  All other parts of the thesis are the original, unpublished work of the author.  iv  Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  ii  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  iii  Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . .  v  Abstract Preface  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction and Background Information . . . . . . . . . .  1  2 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  3  3 Outline of the Proof . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Preliminary Definitions . . . . . . . . . . . . . . . . . . . . . 3.2 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  5 5 6  4 Uniform Bound for the Minor Arcs . . . . . . . . . . . . . . 4.1 Bounds for Linear Exponential Sums . . . . . . . . . . . . . 4.2 Vaughan’s Identity . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Lemmas for Estimating the Bivariate Exponential Sums . . . 4.4 Bound for the Quadratic Exponential Sums . . . . . . . . . . 4.5 Dealing With More General Quadratic Polynomials . . . . . 4.6 Case Where β is not Close to a Rational With Small Denominator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Case Where α is not Close to a Rational with Small Denominator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  8 8 9 12 15 16  5 Mean Value Estimate for the 5.1 Decomposing the Integrand 5.2 The Singular Series . . . . 5.3 The Singular Integral . . .  Minor Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  6 Decomposition of the Major Arcs  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .  17 18  . . . .  20 20 22 29  . . . . . . . . . . . . . . .  30 v  Singular Series . . . . . . . . . . . . . . . . . . . . . . . . Multiplicativity of S . . . . . . . . . . . . . . . . . . . . . . . Convergence of the Product Representation of the Series . . Local Factors and the Asymptotic Density of Solutions mod pr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Finding a Large Space of Solutions with Prime Modulus . . Some Results for Smaller Moduli . . . . . . . . . . . . . . . . Finding a Nonsingular Solution mod p for Odd Primes p . . Lifting Argument for Odd Primes when b is not Divisible by p Lifting Argument for Odd Primes when b is Divisible by p . The Local Factor mod 2 . . . . . . . . . . . . . . . . . . . . .  44 45 47 48 49 50 52  . . . . . . . . . . . . . . . . . . . . . . .  56  Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  64  7 The 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9  8 The Singular Integral  36 36 37  Appendices A Changing the Von Mangoldt Factors to Logarithmic Factors 65 . . . .  67  . . . . . .  70  . .  72  . . . . . . . . . . . . . . . .  76  B Eliminating the Logarithmic Factors from the Sum C The Number of Solutions to a Modified System  D Program for Testing Prime Moduli Between 5 and 19 E Program for Testing the Value 3  vi  Acknowledgements I would like to thank Akos Magyar and Mahta Khosravi for supervising my thesis. I thank Malabika Pramanik for agreeing to read my thesis. Thanks to Malcolm Rupert for help with formatting, and Pam Sargent, Dimitrios Karslidis, and Matthew Coles for helping me organize my thoughts. Thanks to my family for all of their moral support.  vii  Chapter 1  Introduction and Background Information In this paper, we obtain an asymptotic estimate for the number of prime solutions to the following system of Diophantine equations: bX 2 − aY 2 = 0  bX · Y − eY 2 = 0 where X and Y are n-dimensional vectors with components(x1 , . . . , xn ) and (y1 , . . . , yn ), respectively; the notation X 2 refers to the square of the Euclidean 2-norm of X; that is, x21 +. . .+x2n ; X ·Y is the Euclidean dot product of the vectors X and Y , and a, b, and e are integers satisfying ab > e2 . This problem has a geometric interpretation. A triangle is uniquely determined up to congruence by two of its side lengths and the angle between the sides. However, given the two side lengths, we can uniquely determine the angle between them if we are given the dot product of the vectors corresponding to the two sides we are given the length of. In other words, we can uniquely determine a triangle up to congruence by knowing the lengths of the vectors X and Y corresponding to two of the sides of the triangle, and the dot product X · Y of these two vectors. Fix a triangle T with a vertex at the origin, and let X0 and Y0 be vectors corresponding to the sides of the triangle that intersect at the origin. Let a = X02 , b = Y02 , and e = X0 · Y0 . Now, consider another triangle S with a vertex at the origin that is similar to the triangle T , with the similarity set ||Y1 || ||X1 || = ||Y = k where X1 and Y1 are vectors that correspond up so that ||X 0 || 0 || to the sides of S that intersect at the origin. If the triangles S and T are similar, then we would need the angle between X1 and Y1 to be the same as the angle between X0 and Y0 . But the cosine of the angle between X1 X1 ·Y1 ·Y1 = k2 ||X . It follows that for the angle to and Y1 is given by ||XX11||||Y 1 || 0 ||||Y0 || 2 be the same, we need X1 · Y1 = k X0 · Y0 . Let a = ||X0 ||2 , b = ||Y0 ||2 , and 1  e = X · Y . Then ab > e2 by the Cauchy-Schwarz inequality. Furthermore, Y2 X2 we just showed that k2 = a1 = b1 = X1e·Y1 if S and T are similar. So an embedding of T corresponds to a solution to the system of equations bX 2 − aY 2 = 0  (1.1)  2  bX · Y − eY = 0. Conversely, if the ratio of the side length ||X1 || to the length ||X0 || is the same as the ratio of ||Y1 || to ||Y0 || and the angle between X1 and Y1 is the same as the angle between X0 and Y0 , it follows from the law of cosines that the triangle determined by the vectors X0 and Y0 is similar to the triangle determined by the vectors X1 and Y1 . Therefore, each solution to the system 1.1 corresponds to an embedding of T . Therefore, if we restrict ourselves to X and Y such that each coordinate of X and Y is a prime number, then a solution to the system 1.1 will correspond to an embedding of a triangle similar to T with prime coordinates. A lot of work has been done on similar problems. For example, in [5], Hua discusses which numbers can be written as sums of squares of primes. This problem also has a geometric interpretation of embedding vectors of certain lengths into the grid formed by the prime numbers. Hua demonstrated that, for almost all n congruent to 3 mod 24 but not congruent to 0 mod 5, n can be written as the sum of three prime numbers. More recently, James Blair has obtained an asymptotic for the number of solutions to the system of equations bX 2 − aY 2 = 0  bX · Y − eY 2 = 0 among the integers for dimensions n ≥ 5. This result, along with its proof, will be referred to frequently throughout this paper. In particular, the calculation of the singular integral for this problem is exactly the same as in [1], and the minor arc mean value estimates in this paper follow from the asymptotic for the number of solutions to this problem among the integers.  2  Chapter 2  Main Results Instead of counting the number of solutions to the system bX 2 − aY 2 = 0  (2.1)  2  bX · Y − eY = 0 directly, we will first obtain an asymptotic for the number of integer solutions of 2.2 weighted by the Von Mangoldt function Λ. More precisely, we will define RN ((a, b, e), Λ) := Λ(X)Λ(Y )χN (X)χN (Y ) bX 2 −aY 2 =0 bX·Y −eY 2 =0  where for X = (x1 , . . . , xn ), Y = (y1 , . . . , yn ): n  Λ(xi )  Λ(X) = i=1  and  n  χN (xi )  χN (X) = i=1  where χN is the indicator function of the interval [1, N ] and Λ is the Von Mangoldt function defined by Λ(x) =  log p, if x = pr 0 otherwise  In order for 2.2 to have solutions among the primes, we need to have solutions to 2.2 (mod pr ) for each prime p where each x and y coordinate is relatively prime to p: bX 2 − aY 2 ≡ 0 (mod pr )  bX · Y − eY 2 ≡ 0 (mod pr ). For small values of p, this will impose restrictions on the values a, b, and e. We will use the notation p a to denote the largest positive integer of the form pr such that pr divides a. 3  Theorem 2.0.1. Let a, b, e be nonnegative integers such that ab > e2 . Let n ≥ 7 and N > 1 be fixed. Then we have that RN ((a, b, e), Λ) = CN 2n−4 + O(N 2n−4 (log N )−1 )  (2.2)  for some constant C > 0, whenever the following conditions hold. na ≡ nb  (mod 24(2 (a, b))(3 (a, b))  (2.3)  3 a=3 b  (2.4)  3 b≤3 e  (2.5)  2 a=2 b=2 e  (2.6)  The constant C in this theorem is the product of the singular series and singular integral, which are explained in chapters 8 through 10. The local conditions 2.3, 2.4, 2.5, and 2.6 are needed in order to show that the constant C in Theorem 2.0.1 is positive. We will use Theorem 2.0.1 in order to obtain an asymptotic for the number of prime solutions Rn ((a, b, e), P ) := #{(X, Y ) ∈ P2n : bX 2 − aY 2 = 0, bX · Y − eY 2 = 0} Theorem 2.0.2. Let a, b, e be nonnegative integers such that ab > e2 . Let n ≥ 7 and N > 1 be fixed positive integers. Then we have RN (T, P ) = σN 2n−4 (log N )−2n + O(N 2n−4 (log N )−2n−1 ) with a constant σ > 0 as long as a, b, and e satisfy the local conditions 2.3-2.6.  4  Chapter 3  Outline of the Proof 3.1  Preliminary Definitions  We start by writing the weighted number of solutions as an integral of an exponential sum: 1  1  Λ(X)Λ(Y )  RN ((a, b, e), Λ) = 0  (3.1)  0 |X|≤N |Y |≤N  ·e α(bX 2 − aY 2 ) + β(bX · Y − eY 2 ) and we notice that the integrand in 3.1 is the nth power of the exponential sum TN (α, β) := x≤N y≤N  e(α(bx2 − ay 2 ) + β(bxy − ey 2 ))Λ(x)Λ(y)  (3.2)  In order to estimate this integral, we split up the square [0, 1] × [0, 1] in the following way: The major arcs are the points in the square such that α is log(N )A )A k of a rational number of a rational and β is within within log(N 2 q N q N 2q number qℓ where (k, ℓ, q) = 1, and q < (log N )A . More precisely, Let A > 1 and for a given triple (k, ℓ, q) of integers satisfying 1 = (k, ℓ, q) := gcd(k, ℓ, q), let M(k,ℓ,q) =  (α, β) : α −  (log N )A (log N )A ℓ k ≤ , ≤ β − q qN 2 q qN 2  and define the major arcs to be the union MA =  M(k,ℓ,q) q≤(log N )A  (3.3)  (k,ℓ,q)=1  We will define the minor arcs to be the complement of the major arcs: mA = [0, 1]2 \ MA  (3.4) 5  3.2  Heuristics  Then most of the contribution to the integral will come from the major arcs. This is because there is very little cancellation on the major arcs. Heuristically, this is because if α = kq and β = qℓ , the sum T (α, β) is (ignoring the Von Mangoldt factors) periodic with period q, so the sum is comparable to N 2 . We can get better estimates on the minor arcs. In particular, we will prove the following key estimates on the minor arcs: Proposition 3.2.1. On the minor arcs mA , we have the uniform estimate |TN (α, β)| ≤ N 2 (log N )−c(A) where c(A) is an increasing function of A that can be made arbitrarily large by taking A arbitrarily large. This estimate can be used alongside a variant of the estimate proved in [1]: Proposition 3.2.2. Let n ≥ 6, a ≥ 1 be fixed. Then we have mA  |TN (α, β)|n dα dβ ≤ N 2n−4 (log N )12 .  In particular, if we define SN to be the exponential sum SN (α, β) := x≤N y≤N  e(α(bx2 − ay 2 ) + β(bxy − ey 2 ))  (3.5)  n over all of [0, 1] × [0, 1] it is shown in [1] that the integral of the sum SN is asymptotic to a constant times N 2n−4 . We trivially estimate the Von Mangoldt factors by log N , and prove an upper bound of the same form for |SN |n .  We now obtain an asymptotic formula for the integral over the major arcs MA . This asymptotic is obtained via a standard application of the Hardy-Littlewood circle method. We will follow the treatment in [6] We show that Proposition 3.2.3. T (α, β)n = CN 2n−4 + O(N 2n−4 (log N )−1 ).  (3.6)  MA  6  For estimating the major arcs, we decompose the sum (with an error term) into a product of a singular series, that decomposes into a product representation where each factor represents the asymptotic density of solutions to the system mod pk for every p, and a singular integral. The conditions on a, b, and e in the statement of Theorem 2.0.1 are imposed in order to prevent the local factors from being equal to zero. The singular integral is shown to be positive and to contribute the correct power of N to the asymptotic formula.  7  Chapter 4  Uniform Bound for the Minor Arcs The goal for this section is to obtain a uniform bound for |T (α, β)|, where T (α, β) is the sum T (α, β) = x,y≤N  e(α(bx2 − ay 2 ) + β(bxy − ey 2 ))Λ(x)Λ(y),  and Λ is the Von Mangoldt function. The uniform bound will give us a gain of a power of log N on the minor arcs. In order to do this, we will (in the case where α is not close to a rational number) use a version of Vaughan’s identity to rewrite the sums in a more tractable form. In the case where β is not close to a rational number, we will apply standard bounds on exponential sums with linear exponents.  4.1  Bounds for Linear Exponential Sums  First, we obtain standard bounds for exponential sums in which the exponent is linear. In order to obtain these bounds, we need the following lemma on the distribution of the fractional part {kα} of rational numbers α close to some rational number aq : Lemma 4.1.1. If |α − aq | ≤ qb2 , where (a, q) = 1, then for k, k′ such that q 1 0 < k − k′ < 2b , we have that |{kα} − {k′ α}| ≥ 2q . Proof. Write α =  a q  + β, where |β| ≤  b . q2  |{kα} − {k′ α}| = |(k − k′ )α − ℓ| for some integer ℓ. But this is at least (k − k′ )a − ℓ − |(k − k′ )β|. q 8  |(k − k′ )β| is at most  1 2q ,  and  (k−k ′ )a q  − ℓ is a nonzero multiple of 1q . We  know it is nonzero, since ℓ is an integer and |k − k′ | < not divisible by q.  q b  < q, so (k − k′ ) is  In particular, we use Lemma 4.1.1 to prove the following bound on linear exponential sums: b q2  Lemma 4.1.2. Suppose that β is within (ℓ, q) = 1. Then: e(βxz)  of some rational number  N+  |z|≤N |x|≤N  ℓ q  where  N2 + q log q. q  Proof. We start with the sum: e(βxz) |z|≤N |x|≤N  ≤  min N, z≤N  1 βz  Where βz is the distance from βz to the nearest integer. Since the fracq 1 values βz are 2q -separated by 4.1.1, we can split the tional parts of any 2b sum in z up into at most  max 1, Nq  component sums, each of which has  one term equal to N , and the other terms at most equal to 2q j , for j between q N 1 + q sums, each of which is 1 and 2b . So, in other words, there are N + q log q. Multiplying these together gives that that the whole sum is 2 (N + Nq + q) log q, as desired. This linear exponential sum bound is significantly better than the trivial bound of N 2 when q is “medium-sized”; that is, the bound is best when q is between (log N )A and (logNN )A for some A.  4.2  Vaughan’s Identity  Vaughan’s identity is a useful tool for estimating sums containing Von Mangoldt factors. Vaughan’s identity was proven by Vaughan in [7]. In particular, Vaughan’s identity lets us rewrite a sum of terms containing Von 9  Mangoldt factors as a double sum of exponentials (with a small error term), which in practice is usually easier to estimate than the original sum containing the Von Mangoldt factors. We begin by considering the sum Λ(x)f (x). x≤N  For this section, f should be a bounded function. In the sections following this one, we will f (x) = e(x2 ), and after this, we will apply this for a general quadratic polynomial f (x) = e(ax2 + bx + c) using the same principles as for the estimate for x2 . We now follow the idea of the proof given in [4]: Because of the summatory property of the M¨obius function, we have the following: If τu is the sum of the M¨obius function among the divisors of u that are at most X, we have Λ(x)f (xu)  τu u≤N  X≤x≤N/u  =  µ(d) X<u≤N d|u,d≤X  Λ(x)f (xu) +  Λ(x)f (x) X<x≤N  X<x≤N/u  because the terms for 1 < u < X are equal to zero. Note further that Λ(x)f (x) 1≤x≤X  X sup |f (x)| x  X,  by the prime number theorem. But we also have that Λ(x)f (xu)  τu u≤N  X<x≤N/u  =  µ(d) u≤N d|u,d≤X  =  Λ(x)f (xu) X<x≤N/u  µ(d) d≤X  =  Λ(x)f (xdz) z≤N/d X≤x≤N/dz  µ(d) d≤X  z≤N/d x≤N/dz  Λ(x)f (xdz) −  µ(d) d≤X  Λ(x)f (xdz) z≤N/d  x≤X x≤N/dz  So, x≤N  Λ(x)f (x) = S1 − S2 − S3 + O(X), 10  where S1 =  µ(d) d≤X  =  Λ(x)f (xdz) z≤N/d x≤N/dz  µ(d) d≤X  =  Λ(y)f (dz) z≤N/d y|z  µ(d) d≤X  S2 =  log(z)f (dz) z≤N/d  µ(d) d≤X  =  Λ(x)f (xdz) x≤X x≤N/dz  z≤N/d  Λ(x) x≤X  µ(d) d≤N/x d≤X  =  z≤N/dx  Λ(x)µ y≤X 2 x|y,x≤X  But  x|y x≤X  Λ(x)  y x  f (yz) z≤N/y  log(y), so we get φ1 (y) y≤X 2  where φ1 (y)  f (xdz)  f (yz) z≤N/y  log(y). and S3 =  µ(d) X<u≤N d|u,d≤X  Λ(x)f (xu) X<x≤N/u  But  d|u,d≤X  µ(d) ≤ τ (u),  so this comes out to |S3 | ≤ Where φ2 (u) u< N X:  φ2 (u) X≤u≤N  Λ(x)f (xu) X<x≤N/u  τ (u). But the sum is empty if N/u ≤ X, so we must have φ2 (u) X≤u≤N/X  Λ(x)f (xu) X<x≤N/u  11  4.3  Lemmas for Estimating the Bivariate Exponential Sums  The following lemma allows us to estimate a term that will arise when we evaluate the double sums given to us by Vaughan’s identity. Lemma 4.3.1. Let A be the set {|h|, |k| ≤ N/Y, |ℓ| ≤ Y : ||hkℓα|| ≤ 1/Y }. Then: 1 N 2 Y (log Y )|A|. min Y, N2 ||hkℓα|| |h| N/m |ℓ| Y |k|≤N/m  Proof. Fix h and k, and use the linearity of the function mapping ℓ to hkℓα. Partition the interval [−1/2, 1/2] into a disjoint union of intervals as ∗−Y /2≤j≤Y /2 [ Yj , j+1 Y ). Let Bj = {|h|, |k| ≤ N/Y, |ℓ| ≤ Y : ||hkℓα|| ∈ , j+1 }. Suppose that ℓ1 and ℓ2 are in the same Bj , and that ℓ1 and ℓ2 Y have the same sign. Then |ℓ1 − ℓ2 | ≤ Y and ℓ1 − ℓ2 maps to the subinterval (−1/Y, 1/Y ). So for each point in Ah,k = {|ℓ| ≤ Y : ||hkℓα|| ≤ 1/Y } there are at most two ℓ in any given Bj . So j Y  N2  min Y, |h| N/m |ℓ Y |k|≤N/m  1 ||hkℓα||     ≤ N2  Y +  |h| N/m |j≤Y /2,j=0 |k|≤N/m     ≤ 2Y log(Y )N 2    |h| N/m |k|≤N/m  = 2Y log(Y )N 2 |A|.  |Bj |     Y  j   |Ah,k |   Now, we will want to estimate the quantity |A| appearing in lemma 4.3.1. The following lemma provides an estimate for the size of the set A. Lemma 4.3.2. Let N 2/5 ≤ M ≤ N 3/5 , let L =  N , M (log N )B  and let K =  12  M . (log N )B  Then M 1 N , |ℓ| ≤ : ||hkℓα|| ≤ ML K M L2 K 1 N , |ℓ| ≤ M : ||hkℓα|| ≤ |h|, |k| ≤ M M  |h|, |k| ≤ 1 L2 K  In order to prove this lemma, we will need the following result appearing in Davenport’s paper [3]. Lemma 4.3.3. Let P be an origin-symmetric parallelogram with area at most 1. Then the parallelogram PA with side lengths equal to A1 times the 1 side lengths of P will contain A |P | lattice points, where |P | is the number of lattice points in P . We will use Lemma 4.3.3 to prove Lemma 4.3.2. Proof. We use the Lemma 4.3.3 on each of the three variables h, k, and ℓ. We start by using the lemma on h. In particular, for a fixed ℓ and k, the number of |h| ≤ MNL such that ||hkℓα|| ≤ is  1 L  times the number of |h| ≤  N M  such that  ||hkℓα|| ≤ Note that this holds because Therefore,  N M 2 LK  1 M L2 K  1 . M LK  ≤ 1 by the choices of M, L, and K.  M 1 N , |ℓ| ≤ : ||hkℓα|| ≤ ML K M L2 K N M 1 N , |k| ≤ , |ℓ ≤ : ||hkℓα|| ≤ |h| ≤ M ML K M LK  |h|, |k| ≤ 1 L  .  We then apply the same argument in the k variable, noting that everything works this time because MN2 K ≤ 1 by the choices of M and K. Finally, we 1 times apply the same argument in the ℓ variable, which works because M M is equal to 1. Therefore, we obtain the desired result.  13  Finally, we need this bound on the sum of the square of the divisor function appearing in [4] Lemma 4.3.4. x≤n  d(x)2 ≤ 2n(log n)3 .  Proof. d(x)2 = x≤n  x≤n  =     2  1  b|x  1.  x≤n b|x c|x  If b and c divide x, then we can write x as a multiple of lcm(b, c) =  1 b≤n c≤n ylcm(b,c)≤n  Now let a = (b, c) be the greatest common divisor of b and c. Write d = and e = ac . Then the above sum is equal to  b a  1 a≤n d≤ n a  n y≤ ade e≤ n a (d,e)=1  we can only increase the value of the sum by dropping the condition (d, e) = 1 in the sum in e. So we do so: ≤  1 a≤n  d≤ n a  e≤ n a  n y≤ ade  Now, the innermost sum will be empty if e > = d≤ n a  n e≤ ad  n y≤ ade  = n a≤n d≤ n e≤ ad a  ≤  so this sum is equal to:  1 a≤n  ≤  n ad ,  a≤n d≤ n a  a≤n  n ade  n (log n + 1) ad  n (log n + 1)2 a  ≤ n(log n + 1)3  ≤ 2n(log n)3 .  14  4.4  Bound for the Quadratic Exponential Sums  With the lemmas 4.3.1 and 4.3.2 in hand, we can now proceed to estimate the double sums that appear in Vaughan’s identity. We start with the third one, S3 . Split S3 up dyadicly. For some Y between N 2/5 and N 3/5 , we have: Tj =  φ2 (m) Y ≤m≤2Y  Λ(n)f (mn) N 1/5 ≤n≤N m−1  We apply the Cauchy-Schwarz inequality to the summation in m:   |Tj | ≤   Y ≤m≤2Y  1/2   |φ2 (m)|2     Y ≤m≤2Y N 1/5 ≤n≤N m−1  2 1/2  Λ(n)f (mn)   Squaring both sides, and using the bound given in 4.3.4 [4] for the sum of the divisor function squared: |Tj |2  (log N )3 Y Y ≤m≤2Y N 1/5 ≤n1 ≤N m−1 N 1/5 ≤n2 ≤N m−1 Λ(n1 )Λ(n2 )e(αm(n21 − n22 )) 3  Y (log N )  Y ≤m≤2Y N 1/5 ≤n1 ≤N m−1 |h|≤N m−1 −N 1/5 Λ(n1 )Λ(n1 + h)e(αm2 (−2hn1 − h2 )).  Now we interchange the order of summation, take an absolute value inside the outer two sums, relax the summation condition on the outer sums, and use the trivial bound Λ(n) ≤ log(N ): Y (log N )5 n1 ≤N/Y |h|≤N/Y Y ≤m≤2Y  e(αm2 (−2hn1 − h2 ))  We then use Cauchy-Schwarz again: |Tj |4  Y 2 (log N )10  N2 Y2  min(Y, n1 ≤N/Y h≤N/Y ℓ Y  1 ) ||α2h(2n1 + h)ℓ||  15  S1 and S2 are even simpler to handle. We then apply lemmas 1 and 2 to bound each Tj by |Tj |4  (log N )N 2 Y ·  N2 Y (log N )−3B · Y2  |h|, |k|, |ℓ| ≤ (log N )B : ||hkℓα|| ≤  N 4 (log N )−3B+1  (log N )3B N2  (log N )B : ||hkℓα|| ≤  |h|, |k|, |ℓ|  (log N )3B N2  .  Then, if the only triples in the set are those for which h, k, or ℓ is equal to zero, then the quantity is N 4 (log N )−B+1 If there is another solution, then taking q = |hkℓ| gives a q ≤ (log N )3B with 3B ||qα|| (c logNN2 ) . In other words, if N is sufficiently large, then α must be in the major arc M3B+ǫ Therefore, if α ∈ / MA+ǫ , then |Tj |  −A  1  N (log N ) 12 + 4 .  We apply the same argument to each corresponding sum for S1 and S2 , and use the fact that there are only O(log(N )) sums present.So we gain a power of log(N ) in each of the three sums given above, which shows that we 2 gain a power of log(N ) for the sum N n=1 Λ(n)e(αn ).  4.5  Dealing With More General Quadratic Polynomials  Let’s suppose that we want to evaluate ξm ηk e(αm2 k2 + βmk + γ), m∼Y k∼N/m  where the sum in m consists only of terms that are larger than Y , and the ξm and ηk are constants with absolute value 1. We use the Cauchy-Schwarz inequality like in the previous section (and modify the summation condition on the second sum since the quantity being summed is nonnegative): |S|2  e(bαh(2k + h)m2 + βm(h))  Y |h|≤N/Y k≤N/Y m∼Y  16  Then we have upon using Cauchy-Schwarz again: |S|4  Y2  N2 Y2  e(bα2h(2k + h)2ℓ(2s + ℓ) + βℓh) |h|≤N/Y k≤N/Y |ℓ|≤Y s Y  We then change variables, letting 2k + h be the new k and 2s + ℓ be the new s: e(bα4hkls + β(ℓh)) |h|≤N/Y k≤N/Y |ℓ|≤Y s Y  We now switch the order of summation around a bit and pull the absolute value signs inside the sum: e(bα4hkls + β(ℓh)) |h|≤N/Y |ℓ|≤Y k≤N/Y s Y  ≤  e(bα4hkls) |h|≤N/Y |ℓ|≤Y k≤N/Y s Y  min Y, |h|≤N/Y |ℓ|≤Y k≤N/Y  1 ||bα4hkl||  .  The rest of the argument proceeds almost exactly the same way as before, except for the fact that the extra constant necessitates enlarging the major arcs by a little bit. In particular, the bound from the previous section must be modified a little to state that that if α ∈ / MA+ǫ , then for sufficiently large −A 1 N depending on ǫ, |Tj | N (log N ) 12 + 4 .  Case Where β is not Close to a Rational With Small Denominator  4.6 Define:  T (α, β) = |x|≤N |y|≤N  e(α(bx2 − ay 2 ) + β(bxy − ey 2 ))Λ(x)Λ(y)  and S(x, α, β) = |y|≤N  e(α(bx2 − ay 2 ) + β(bxy − ey 2 ))Λ(y)  Then S(x, α, β)Λ(x).  T (α, β) = |x|≤N  17  We now apply the Cauchy-Schwarz inequality: |T (α, β)|2 ≤  |x|≤N  |Λ(x)|2  |x|≤p  |S(x, α, β)|2  Then, applying PNT to one instance of the Von Mangoldt function and the uniform bound to the other one: N log(N ) |x|≤N |y|≤N |y ′ |≤N  Λ(y)Λ(y ′ )e(bβx(y − y ′ ) + (−αa − βe)(y 2 − y ′2 ))  N (log N )3 |y|≤N |x|≤N |y ′ |≤N  e(βbx(y − y ′ ))  Now, let z = y − y ′ , and notice that a given z occurs at most 2N times in the sum: N 2 (log N )3  e(bβxz) |z|≤N |x|≤N  The Dirichlet principle implies that for any β irrational, there exists a q < A N2 such that ||qα|| < (logNN2 ) Now, because β is in a minor arc, we (log N )A know that this q must also be larger than (log N )A . So that means that bβ N )A is within b(log ≤ qb2 of a rational number of the form rℓ where r is some qN 2 2  number between qb and q, where (log N )A < r ≤ (logNN )A . This, together with Lemma 4.1.2, implies that the above sum is bounded above by N 2 (log N )3 (N + N 2 /q + q)(log q) (log N )3 N4 (log log N ). (log N )A  4.7  Case Where α is not Close to a Rational with Small Denominator |T (α, β)| =  x≤N y≤N  e(α(bx2 − ay 2 ) + β(bxy − ey 2 ))Λ(x)Λ(y)  18  We then interchange the order of summation: ≤  y≤N  e(−αay 2 − βey 2 )Λ(y)  ≤ log N  e(αbx2 + βbxy)Λ(x) x≤N  e(αbx2 + βbxy)Λ(x) y≤N x≤N  We then apply the version of Vaughan’s identity given here along with the exponential sum estimates: N (log N )−C(A)  log N y≤N  where C(A) is some unbounded, increasing function of A. So the sum comes out to N 2 (log N )−C(A)+1 So, we conclude that for any (α, β) in the minor arcs, we have that Proposition 4.7.1. On the minor arcs mA , we have the uniform estimate |TN (α, β)| ≤ N 2 (log N )−c(A) where c(A) is an increasing function of A that can be made arbitrarily large by taking A arbitrarily large.  19  Chapter 5  Mean Value Estimate for the Minor Arcs 5.1  Decomposing the Integrand  We want to estimate the integral: T (α, β)7 mA  where T (α, β) = |x|,|y|≤N  e(α(bx2 − ay 2 ) + β(bxy − ey 2 ))Λ(x)Λ(y).  and Λ(X) is the Von Mangoldt function. We split the integral up in the typical way: ≤ log(N )12 sup |T (α, β)| mA  [0,1]2  |S(α, β)|6 ,  where S(α, β) = |x|,|y|≤N  e(α(bx2 − ay 2 ) + β(bxy − ey 2 )).  We estimate the supremum using the uniform bound. In order to estimate the integral, we split up [0, 1]2 into major arcs of the same size as in [1], and the corresponding minor arcs. The minor arc estimate works exactly the same way as in [1], and we gain a small power of N in the process. The major arc estimate is slightly different because of the presence of the absolute value signs. We start by attempting to factor the integrand into a product of a singular series and a singular integral, as usual. We begin by expanding the product in the absolute value, and writing α = kq + γ, β = qℓ + δ with γ and δ smaller than  N −2+2θ : q  |S(α, β)|6 = S(α, β)3 S(α, β)3 20  k ℓ e(( + γ)f (qX + S, qY + T ) + ( + δ)g(qX + S, qY + T ))· q q 6  =  X,Y,S,T ∈Z  ·χ  qX + S N  χ  qY + T N  where f (X, Y ) = b(x21 + x22 + x23 − x24 − x25 − x26 )  −a(y12 + y22 + y32 − y42 − y52 − y62 )  and g(X, Y ) = b(x1 y1 + x2 y2 + x3 y3 − x4 y4 − x5 y5 − x6 y6 ) −e(y12 + y22 + y32 − y42 − y52 − y62 ).  Note that the changing X and Y shifts the parts of the exponent depending on kq and qℓ by a full period, so we can pull the parts depending on γ and δ out of the sum in X and Y . This gives e(h(S, T ))G(S, T ) S,T (modq)  where h(S, T ) =  kb(s21 + s22 + s23 − s24 − s25 − s26 ) q ℓb(s1 t1 + s2 t2 + s3 t3 − s4 t4 − s5 t5 − s6 t6 ) + q (ka + ℓe)(t21 + t22 + t23 − t24 − t25 − t26 ) − q  and G(S, T ) =  e(δf (qX + S, qY + T ) + γg(qX + S, qY + T ))· X,Y  ·χ  qX + S N  χ  qY + T N  We then make the change from G(S, T ) into the singular integral as in [1].  21  5.2  The Singular Series  The singular series is treated in a manner similar to [1]. We want to estimate the quantity K6 (K, ℓ, q) gcd(k,ℓ,q)=1  where K6 (k, ℓ, q) = Note that K6 (k, ℓ, q) =  1 q 12  |K(k, ℓ, q)|6 ,  K(k, ℓ, q) = s,t(mod q)  e(h(S, T )). S,T (mod q)  where  e(kbs2 + ℓbst − (ka + ℓe)t2 )  I will start by looking at K6 (k, ℓ, pr ) for prime powers pr . K6 (k, ℓ, pr ) =  1 p12r  e(h(S, T )). S,T (mod pr )  Then K6 (k, ℓ, pr ) 1 = 12r p  S,T (mod pr )  k (bf (S, S) − af (T, T ) + 2) pr ℓ (bf (S, T ) − ef (T, T ) ·e pr  e  where f (X, Y ) = x1 y1 + x2 y2 + x3 y3 − x4 y4 − x5 y5 − x6 y6 . Define S1 = (s1 , s2 , s3 ) and S2 = (s4 , s5 , s6 ) where S = (s1 , s2 , s3 , s4 , s5 , s6 ), and similarly set T1 = (t1 , t2 , t3 ) and T2 = (t4 , t5 , t6 ) where T = (t1 , t2 , t3 , t4 , t5 , t6 ). Then: K6 (k, ℓ, pr ) 1 = 12r p  S1 ,T1 ,S2 ,T2 (mod pr )  ·e  e  k (b(S12 − S22 ) − a(T12 − T22 )) pr  ℓ (b(S1 · T1 − S2 · T2 ) − e(T12 − T22 ) pr 22  Now reindex the sums, taking S1 = S2 + U , T1 = T2 + U . This has the advantage of linearizing the S2 and T2 terms appearing in the sum. =  1 p12r  e U,V,S2 ,T2 (mod pr )  k (b(U 2 + 2U · S2 ) − a(V 2 + 2V · T2 )) pr  ℓ (b(U · T2 + V · S2 + U · V ) − e(V 2 + 2V · T2 )) pr  ·e(  We now take out the parts of the sum that don’t depend on U and V and apply the triangle inequality: ≤  1 p12r  U,V (mod pr )  e  k (2bU · S2 − 2aV · T2 ) pr  e  ℓ (bU · T2 + bV · S2 − 2eV · T2 ) pr  S2 ,T2 mod pr  Note that the sum in S2 and T2 is over a complete residue system mod pr in each variable, so the sum is zero when any of the coefficients of S2 or T2 is nonzero. That is, the sum in S2 and T2 will only be nonzero when 2bkU + bℓV ≡ 0 (mod pr ) and −2akV + bℓU − 2eℓV ≡ 0 (mod pr ),  in which case the sum will be p6r since there are 6r terms in the inner sum in S2 and T2 , all of which are equal to one. We will first deal with the case where p is an odd prime. Let pγ = (b, pr ), and let b = b′ pγ . Then the first equation becomes: 2kb′ U + b′ ℓV ≡ 0 (mod pr−γ ), or, after dividing by b′ , 2kU + ℓV ≡ 0  (mod pr−γ ),  Now, one of k and ℓ must be relatively prime to pγ because we’re only looking at cases where (k, ℓ, pr ) = 1. assume (k, p) = 1. Then k is invertible mod p and U ≡ −(2k)−1 ℓV. (mod pr−γ ) 23  So plugging into the second equation gives (−2ka − 2ℓe)V − (ℓ2 b(2k)−1 )(V + Cpr−γ ) ≡ 0 (mod pr ) (−2ka − ℓ2 b(2k)−1 − 2ℓe)V ≡ 0 (mod pr )  (−4k2 a − ℓ2 b − 4kℓe)V ≡ 0 (mod pr ).  A quick calculation shows that we achieve the same result (with U instead of V) we instead assume that ℓ is not divisible by p. This equation has p3δ solutions, where pδ = (pr , −4k2 a + ℓ2 b − 4kℓe). Putting this together with the p3γ solutions to the first equation, we have a total of (−4k2 ab + ℓ2 b2 − 4kℓbe, pr )3 solutions to the system. Multiplying this by the p6r choices for S2 and T2 , we have that the sum is at most 1 (−4k2 ab − ℓ2 b2 − 4kℓbe, pr )3 . p6r Now we consider numbers of the form 2r . Again, we’re trying to count the number of solutions to the system 2bkU + bℓV ≡ 0 (mod 2r )  −2akV + bℓU − 2eℓV ≡ 0 (mod 2r ). Now, we write b = 2γ b′ , where 2γ = (2r , b). 2b′ kU + b′ ℓV ≡ 0 2kU + ℓV ≡ 0  (mod 2r−γ ) (mod 2r−γ )  if r > γ. Then if ℓ is odd, the second equation reduces to 4ak2 U + bℓ2 U + 4ekℓU ≡ 0  (mod 2r−γ ),  as in the case where p is an odd prime. But if ℓ is even, then k must be odd since (k, l, 2r ) = 1, so therefore k is invertible mod 2r , so we can divide the equation by 2: ℓ b′ kU + b′ V ≡ 0(mod 2r−γ−1 ). 2 Then, the second equation reduces to the same thing as in the odd case. So the sum is bounded above by 2 r (2 , −4k2 ab − ℓ2 b2 − 4kℓbe)3 26r 24  We then wish to calculate |{(k, ℓ) : (k, ℓ, p) = 1 and (pr , 4k2 ab + ℓ2 b2 + 4kℓbe) = ps }| for prime powers pr and 0 ≤ s ≤ r. We start by assuming p is an odd prime. Since (k, ℓ, p) = 1, either (k, p) or (ℓ, p) is equal to 1. Assume first that (ℓ, p) = 1. Then we complete the square in k: 4k2 ab + 4kℓbe + ℓ2 b2 ≡ 0  (mod ps )  (2abk + 2bℓe)2 − 4e2 b2 ℓ2 + a3 ℓ2 b3 ≡ 0  (mod ps )  4k2 a2 b2 + 4kℓab2 e + ℓ2 a2 b4 ≡ 0 (2abk + 2bℓe)2 ≡ (4e2 b2 − ab3 )ℓ2  (mod ps ) (mod ps )  Now, the right hand side is divisible by pα where pα is the largest power of p that divides (4e2 b2 − ab3 ); furthermore, the right hand side is not divisible by pα+1 because we assumed that ℓ is not divisible by p. So there are at most 2pα values mod ps that that can square to give the right hand side (as we can see by dividing the right hand side by pα ). Note further that for a given ℓ, the expression 2abk + 2bℓe hits each residue class (mod ps ) at most (ab, ps ) ≤ ab times as k is chosen (mod ps ). So therefore there are at most 2abpα 1 solutions for any given ℓ. The same argument works up to a constant factor if p = 2, and a similar argument works if (k, p) = 1 instead. So, there are at most 2abφ(ps ) ps values of k and ℓ (mod ps ) for which ps divides 4k2 ab+ℓ2 b2 +4kℓbe. So that means that there are ps p2r−2s = p2r−s values of (k.ℓ) mod pr for which ps divides 4k2 ab+ℓ2 b2 +4kℓbe, and therefore p2r−s choices for (k, ℓ) mod pr for which (4k2 ab + ℓ2 b2 + 4kℓbe, pr ) = ps . Putting these facts together, we get K6 (pr ) ≤ 2  p6r (pr , 4k2 ab + 4kℓbe + b2 ℓ2 )3 k,ℓ(mod pr )  = 2p−6r s  p  −6r  =p  −4r  p3s |{(k, ℓ) : ps = (pr , 4k2 ab + 4kℓbe + b2 ℓ2 )}| p3s p2r p−s  0≤s≤r  p2s 0≤s≤r  p−4r p2r = p−2r . Therefore, if we can prove that K6 is multiplicative, then we will have shown that for any q we have K6 (q) ≤ C ωq q −2 . 25  In order to show that K6 is multiplicative, I first will show the following multiplicative property: K6 (k1 , ℓ1 , q1 )K6 (k2 , ℓ2 , q2 ) = K6 (k1 q2 + k2 q1 , ℓ1 q2 + ℓ2 q1 , q1 q2 ) whenever (q1 , q2 ) = 1. Proof. Note that it suffices to prove that K has the multiplicative property. K(k1 q2 + k2 q1 , ℓ1 q2 + ℓ2 q1 , q) k1 q2 + k2 q1 ℓ1 q 2 + ℓ2 q 1 (bx2 − ay 2 ) + (bxy − ey 2 ) = e q q x(mod q) y(mod q)  We apply the Chinese remainder theorem: = x1 (mod q1 ) x2 (mod q2 ) y1 (mod q1 ) (y2 mod q2 ) (k1 q2 + k2 q1 )(b(x1 q2 + x2 q1 )2 − a(y1 q2  e  + y2 q1 )2 )  q (ℓ1 q2 + ℓ2 q1 )(b(x1 q2 + x2 q1 )(y2 q1 + y1 q2 ) − e(y1 q2 + y2 q1 )2 ) q  ·e  Then, noting that the cross terms all cancel out in the expansion: = x1 (mod q1 ) x2 (mod q2 ) y1 (mod q1 ) (y2 mod q2 ) (k1 q2 + k2 q1 )(b(x21 q22 + x22 q12 ) − a(y12 q22  e  ·e  (ℓ1 q2 +  ℓ2 q1 )(b(x1 y1 q22  + y22 q12 ))  q + x2 y2 q12 ) − e(y12 q22 + y22 q12 )) q  = x1 (mod q1 ) x2 (mod q2 ) y1 (mod q1 ) (y2 mod q2 ) k1 (bx21 q22 − ay12 q22 ) + ℓ1 (bx1 y1 q22 − ey12 q22 )  e  ·e  q1 k2 (bx22 q12 − ay22 q12 ) + ℓ2 (bx2 y2 q12 − ey22 q12 ) q2  Now, since q1 and q2 are relatively prime, it follows that multiplication by q2 is a bijection on the residue classes mod q1 , and vice versa. So it follows that  26  we can ignore the q1 and q2 factors multiplying x1 , x2 , y1 , and y2 . Therefore, the above sum reduces to K(k1 , ℓ1 , q1 )K(k2 , ℓ2 , q2 ).  From this we conclude that K is multiplicative: K(q1 )K(q2 )   =  (k.ℓ,q1 )=1    S(k, ℓ, q1 )   (k,ℓ,q2)=1)    S(k, ℓ, q2 )  K(k1 , ℓ1 , q1 )K(k2 , ℓ2 , q2 )  =  (k1 ,ℓ1 ,q2 )=1 (k2 ,ℓ2 ,q1 )=1  =  K(k1 q2 + k2 q1 , ℓ1 q2 + ℓ2 q1 , q1 q2 ). (k1 ,ℓ1 ,q1 )=1 (k2 ,ℓ2 ,q2 )=1  It follows from a basic CRT argument that this is equal to K(q1 q2 ), as desired. So K is multiplicative, and therefore K6 is also multiplicative. Now we show that K6 (pr ) 0≤r≤R  is equal to the density of solutions to the modified system of equations in ((Z/pr Z))12 . K6 (pr ) 0≤r≤R  = 0≤r≤R (k,ℓ,pr )=1  |K(k, ℓ, pr )6 |  1  = 0<r≤R  (pr )2n  e (k,ℓ,pr )=1 X,Y ∈((Z/pr Z))n  k ℓ f (X, Y ) + r g(X, Y ) , r p p  where f (x, y) and g(x, y) are defined as above. First, consider the inner sums over k, ℓ, X, and Y , fixing r for now. We interchange the order of summation: 1 (pr )2n  e X,Y ∈((Z/pr Z))n (k,ℓ,pr )=1  k ℓ f (x, y) + r g(X, Y ) r p p 27  The sum over k and ℓ satisfying (k, ℓ, pr ) = 1 is equal to the sum over all k and ℓ minus the sum over k and ℓ such that p|k and p|ℓ. We will first consider the sum over all k and ℓ and then subtract off the remaining terms later. Note that since the summand is linear in k and ℓ, the inner sum comes out to zero unless we have f (X, Y ) ≡ g(X, Y ) ≡ 0 mod pr , in which case each term in the sum is equal to 1 so the sum is equal to p2r . So, after 1 out front, the sum over all k and ℓ comes out to multiplying by the p12r p2r N (pr ) , p12r  where N (pr ) is the number of X and Y in ((Z/pr Z))n solving f (X, Y ) ≡ g(X, Y ) ≡ 0 mod pr . Now, we look at the terms being subtracted off, in particular, the k and ℓ such that p divides both k and ℓ. 1 p6r =  1 p6r  e X,Y ∈((Z/pr Z))n p|k,ℓ  k ℓ f (X, Y ) + r g(X, Y ) r p p e  X,Y  ∈((Z/pr Z))n  k,ℓ∈Z/pr−1 Z  k pr−1  f (X, Y ) +  ℓ pr−1  g(X, Y )  Note that the sum in k and ℓ is nonzero precisely when f (X, Y ) ≡ g(X, Y ) ≡ 0 (mod pr−1 ), which happens N (pr−1 ) times mod pr−1 . Because f and g don’t change (mod pr−1 ) when pr−1 is added to any component X or Y , it follows that there are p12 N (pr−1 ) choices for X and Y for which the inner sum is nonzero. But when the inner sum is nonzero, each term in the sum is equal to 1 so the sum evaluates to p2r−2 . So the subtracted terms’ sum comes out to 1 2r−2 12 p p N (pr−1 ) p12r 1 = (pr−1 )2 N (pr−1 ) r−1 12 , (p ) which is the sum over all k and ℓ for the r − 1 term. Therefore, the sum is 2 telescoping, and the sum of the first N terms is equal to p12r Np(pr−1 ) , which is the density of solutions (mod pr ). Therefore, the local factor corresponding to p is the asymptotic density of solutions mod pr as r → ∞. So the singular series comes out the same as in [1], except for the fact that the An (p) will be different because we’re counting solutions to a different system of equations. 28  5.3  The Singular Integral  Most of the calculation for the singular integral here is identical to the singular integral appearing in [1], which is exactly the same as the singular integral appearing here. Since we only need an upper bound, and all of the techniques used to show the convergence of the singular integral depend only on the absolute value of the quantity L(δ, γ), the upper bounds obtained in the evaluation of the singular integral in Chapter 8 are sufficient to show the integral is convergent, and to show that the major arcs are of order N 8 . Therefore, we have the mean value estimate for the minor arcs, as desired (losing a 12th power of log, which is acceptable).  29  Chapter 6  Decomposition of the Major Arcs In order to decompose the integrand into a product of a singular integral and a singular series, we mimic the strategy in chapter 8 of [6]. We will use the following notation: N  N  u(α, β) = x=1 y=1  e α(bx2 − ay 2 ) + β(bxy − ey 2 )  S(k, ℓ, q) =  e y=1 x=1 (x,q)=1 (y,q)=1  S(q) =  ℓ k (bx2 − ay 2 ) + (bxy − ey 2 ) q q  S(k, ℓ, q) (k,ℓ,q)=1  We start out wanting to estimate the sum Fw,z (α, β) = p1 ≤x p2 ≤x  (log p1 )(log p2 )e α(bp21 − ap22 ) + β(bp1 p2 − ep22 ) .  It is sufficient to consider this sum instead of the corresponding sum with the Von Mangoldt factors, as we show in Appendix A. Consider the case where α = kq and β = qℓ , where q ≤ Q = (log N )A . We split each sum up mod q, noting that we’re only leaving out primes that divide q if we only consider the reduced residue classes mod q. Then: Fw,z  k ℓ , q q  30  q  q  = s=1 r=1 p2 ≤z p1 ≤w (r,q)=1 p1 ≡r (mod q) (s,q)=1 p2 ≡s (mod q)  (log p1 )(log p2 )e  k 2 ℓ (bp1 − ap22 ) + (bp1 p2 − ep22 ) + O(q log2 q) q q  We now notice that the value of the exponential depends only on the residue class of p1 and p2 and not on p1 and p2 themselves. So we pull out the parts of the sum that don’t depend on p1 and p2 . q  q  = r=1 s=1 (r,q)=1 (s,q)=1  ℓ k e( (br 2 − as2 ) + (brs − er 2 )) q q (log p1 )(log p2 ) + O(q log2 q)  p2 ≤z p1 ≤w p1 ≡r (mod q) p2 ≡s (mod q)  We now proceed to apply Siegel-Walfisz to both of the inner sums, leaving q  q  = r=1 s=1 (r,q)=1 (s,q)=1  ℓ k e( (br 2 − as2 ) + (brs − er 2 ))· q q  w w z z + O( ))( + O( )) C φ(q) (log w) φ(q) (log z)C +O(Q log2 Q) q 2 wz q 2 wz S(k, ℓ, q) = wz + O + O φ(q)2 (log w)C (log z)C Q2 N 2 S(k, ℓ, q)wz + O = φ(q)2 (log N )C ·(  + O(Q log2 Q)  We now prove the equivalent of lemma 8.3 in [6] for this problem. The proof is almost exactly the same as the proof appearing in [6]. Lemma 6.0.1. For a given α = F (α, β) =  k q  + δ and β =  S(k, ℓ, q) u(δ, γ) + O φ(q)2  ℓ q  + γ, we have that  Q4 N 2 (log N )C  and therefore F (α, β)n =  S(k, ℓ, q)n u(δ, γ)n + O φ(q)2n  Q4 N 2n (log N )C 31  Proof. Write α = kq + δ, β = qℓ + γ, and let λ be the indicator function for the primes weighted by the logarithm. For any 1 ≤ x, y ≤ N , we have F (α, β) − N  S(k, ℓ, q) u(δ, γ) φ(q)2  N  = m1 =1 m2 =1  λ(m1 )λ(m2 )e(α(bm21 − am22 ) + β(bm1 m2 − em22 ))  S(k, ℓ, q) − φ(q)2 m  N  n  1 =1 m2 =1  N  e(δ(bm21 − am22 ) + γ(bm1 m2 − em22 ))  N  = m1 =1 m2 =1  k ℓ S(k, ℓ, q) λ(m1 )λ(m2 )e( (bm21 − am22 ) + (bm1 m2 − em22 )) − q q φ(q)2 2 2 2 ·e(δ(bm1 − am2 ) + γ(bm1 m2 − em2 )).  ·  Define B1 (w, z) = 1≤m1 ≤w  ℓ S(k, ℓ, q) k λ(m1 )λ(m2 )e( (bm21 − am22 ) + (bm1 m2 − em22 )) − q q φ(q)2 B(w, z) = 1≤m1 ≤w 1≤m2 ≤z  k ℓ S(k, ℓ, q) λ(m1 )λ(m2 )e( (bm21 − am22 ) + (bm1 m2 − em22 )) − . q q φ(q)2 Then S(k, ℓ, q) k ℓ , wz + O(1) − q q φ(q)2 Q2 N 2 (log N )C  B(w, z) = Fw,z =O  Let ψ(x, y) = δ(bx2 − ay 2 ) + γ(bxy − ey 2 ). We then use partial summation  32  in the m1 variable to conclude: F (α, β) − =  S(k, ℓ, q) u(δ, γ) φ(q)2  B1 (N, m2 )e(ψ(N, m2 )) 1≤m2 ≤N N  −  2πi 1  =  ∂ψ (w, m2 )B1 (w, m2 )e(ψ(w, m2 )) dw ∂w  (B1 (N, m2 )e(ψ(N, m2 ))) 1≤m2 ≤N N  −  2πi 1  1≤m2 ≤N  ∂ψ (w, m2 )B1 (w, m2 )e(ψ(w, m2 ))dw ∂w  We then perform partial summation in the m2 variable: = B(N, N )e(ψ(N, N )) N ∂ψ 2πi (N, z)B(N, z)e(ψ(N, z))dz − ∂z 1 N ∂ψ 2πi − (w, N )B(w, N )e(ψ(w, N )) ∂w 1 N ∂ψ ∂ψ ∂ψ 4π 2 B(w, z) − (w, z) + (w, z) (w, z) e(ψ(w, z))dzdw ∂z∂w ∂w ∂z 1 Q Now, note that the first partials of ψ are O( N ) since they are linear expressions in w and z, which are O(N ), and each coefficient contains a δ or γ, which is O NQ2 . Similarly, the second partials of ψ are O NQ2 . Therefore,  since the B terms are O  Q2 N 2 (log N )C  , it follows that the whole expression is  Q4 N 2 (log N )C  O( . The statement about higher powers of this expression follows trivially from this one. n  n The S(k,ℓ,q) φ(q)2n terms become the singular series. We then transform u into the singular integral as in [1]:  F (α, β)n = O  Q4 N 2n log(N )C  +  S(k, ℓ, q)n u(δ, γ)n φ(q)2n  33  where u(δ, γ)n = X,Y  e(δ(b(X)2 − a(Y )2 ) + γ(b(X) · (Y ) − e(Y )2 ))) X N  ·χ  χ  Y N  .  We then show that the summand in un is close to the integral 1  1  X ′ =0  Y  ′ =0  e(δ(b(X + X ′ )2 − a(Y + Y ′ )2 )) ·e(γ(b((X + X ′ )) · (Y + Y ′ ) − e(Y + Y ′ )2 )) (Y + Y ′) (X + X ′ ) ·χ χ N N  We do this by noting that the changing X + X ′ to X in the above integral has only a small effect on its value. In particular, changing X + X ′ to X in the characteristic function only changes the boundary terms in the sum, of which there are only O((N )2n−1 ), and integrating this error term over the major arcs yields an error of N 2n−5 (log N )C(A) . We also change the exponent in the above integral. Noting that e(x) − e(t) |x − t|, we realize through direct calculation that the error in changing the exponential is O ((|γ| + |δ|)N ), but since we’re in a N )C(A) , and 1 ≤ q < (log N )C(A) so the major arc γ and δ are at most (logqN 2 1 error becomes O N (log N )C(A) . We now integrate the difference over all of the major arcs, giving an error of O N 2n−5 (log N )2C(A) . So we can change un to the integral X  Y  e(δ(b(X)2 − a(Y )2 ) + γ(b(X) · (Y ) − e(Y )2 ))) ·χ  X N  χ  Y N  dXdY  This yields the product F (α, β) = Major Arcs  Kn (k, ℓ, q) · L(δ, γ, k, ℓ, q) + o(N 2n−4 )  where Kn (k, ℓ, q) =  S(k, ℓ, q)n φ(q)2n 34  and L(δ, γ, k, ℓ, q) = X,Y  e δ(b(X)2 − a(Y )2 ) + γ(bX · Y − eY 2 ) ·χ  X N  χ  Y N  dXdY.  35  Chapter 7  The Singular Series 7.1  Multiplicativity of S  Suppose q = q1 q2 with (q1 , q2 ) = 1. S(k1 q2 + k2 q1 , ℓ1 q2 + ℓ2 q1 , q) ℓ1 q 2 + ℓ2 q 1 k1 q2 + k2 q1 (bx2 − ay 2 ) + (bxy − ey 2 ) = e q q (x,q)=1 (y,q)=1  We apply the Chinese remainder theorem: = (x1 ,q1 )=1 (x2 ,q2 )=1 (y1 ,q1 )=1 (y2 ,q2 )=1 (k1 q2 + k2 q1 )(b(x1 q2 + x2 q1 )2  e  − a(y1 q2 + y2 q1 )2 )  q (ℓ1 q2 + ℓ2 q1 )(b(x1 q2 + x2 q1 )(y2 q1 + y1 q2 ) − e(y1 q2 + y2 q1 )2 ) q  ·e  Then, noting that the cross terms all cancel out in the expansion: = (x1 ,q1 )=1 (x2 ,q2 )=1 (y1 ,q1 )=1 (y2 ,q2 )=1 (k1 q2 + k2 q1 )(b(x21 q22 + x22 q12 ) −  e  ·e  a(y12 q22 + y22 q12 ))  q (ℓ1 q2 + ℓ2 q1 )(b(x1 y1 q22 + x2 y2 q12 ) − e(y12 q22 + y22 q12 )) q  = (x1 ,q1 )=1 (x2 ,q2 )=1 (y1 ,q1 )=1 (y2 ,q2 )=1 k1 (bx21 q22 − ay12 q22 ) + ℓ1 (bx1 y1 q22  e  ·e  k2 (bx22 q12  −  ay22 q12 )  − ey12 q22 )  q1 + ℓ2 (bx2 y2 q12 − ey22 q12 ) q2 36  Now, since q1 and q2 are relatively prime, it follows that multiplication by q2 is a bijection on the reduced residue classes mod q1 , and vice versa. So it follows that we can ignore the q1 and q2 factors multiplying x1 , x2 , y1 , and y2 . Therefore, the above sum reduces to S(k1 , ℓ1 , q1 )S(k2 , ℓ2 , q2 ). We then use this fact as follows:  S(q )S(q2 )  1  =  (k.ℓ,q1 )=1  =    S(k, ℓ, q1 )   (k,ℓ,q2)=1    S(k, ℓ, q2 )  S(k1 , ℓ1 , q1 )S(k2 , ℓ2 , q2 )  (k1 ,ℓ1 ,q2 )=1 k2 ,ℓ2 ,q1 )=1  =  S(k1 q2 + k2 q1 , ℓ1 q2 + ℓ2 q1 , q1 q2 ). (k1 ,ℓ1 ,q1 )=1 (k2 ,ℓ2 ,q2 )=1  It follows from a basic CRT argument that this is equal to S(q1 q2 ), as desired.  7.2  Convergence of the Product Representation of the Series  Given the multiplicativity shown in the previous section, along with the multiplicativity of the totient function, we hope that the singular series ∞ q=1  1 S(q)n φ(q)2n  will have the Euler product representation ∞  1+ pprime  r=1  S(pr )n φ(pr )2n  .  In order to do this, we find an estimate on S(k, ℓ, q) for prime powers q. 37  S(k, ℓ, q)n =  e (X,q)=1 (Y,q)=1  ℓ k (bX 2 − aY 2 ) + (bX · Y − eY 2 ) . q q  Where the condition (X, q) = 1 means that each component of X is relatively prime to q. In order to estimate this sum for odd prime powers pr , we break X up as X1 + p⌈r/2⌉ X2 S(k, ℓ, pr ) = (x,p)=1 0≤X2 <p⌊r/2⌋ (Y1 ,p)=1 0≤Y2 <p⌊r/2⌋ 0≤Y1 <p⌈r/2⌉ 0≤X1 <p⌈r/2⌉  k (b(X1 + p⌈r/2⌉ X2 )2 − a(Y1 + p⌈r/2⌉ Y2 )2 ) pr ℓ ·e (b(X1 + p⌈r/2⌉ X2 )(Y1 + p⌈r/2⌉ Y2 ) − e(Y1 + p⌈r/2⌉ Y2 )2 ) pr  e  (Here, the condition in the sum means that each component of X1 , X2 , Y1 , and Y2 satisfies each inequality.) = (x,p)=1 0≤X2 <p⌊r/2⌋ (Y1 ,p)=1 0≤Y2 <p⌊r/2⌋ 0≤Y1 <p⌈r/2⌉ 0≤X1 <p⌈r/2⌉  k (b(X12 + 2p⌈r/2⌉ X1 · X2 + (p⌈r/2⌉ X2 )2 )) pr k ·e (−a(Y12 + 2p⌈r/2⌉ Y1 · Y2 + (p⌈r/2⌉ Y2 )2 )) pr ℓ (b(X1 · Y1 + p⌈r/2⌉ X1 · Y2 + p⌈r/2⌉ X2 · Y1 + X2 · Y2 (p⌈r/2⌉ )2 )) ·e pr ℓ ·e (−e(Y12 + 2p⌈r/2⌉ Y1 · Y2 + (p⌈r/2⌉ Y2 )2 )) pr  e  Now we eliminate all of the integers from the exponent and pull out everything that doesn’t depend on X2 and Y2 : e  S(k, ℓ, q) = (X1 ,p)=1 (Y1 ,p)=1 X1 ≤p⌈r/2⌉ Y1 ≤p⌈r/2⌉  e X2  ·e  ≤p⌊r/2⌋  Y2  ℓ p⌊r/2⌋  ≤p⌊r/2⌋  k ℓ (bX12 − aY12 ) + r (bX1 · Y1 − eY12 pr p k p⌊r/2⌋  (2bX1 · X2 − 2aY1 · Y2 )  (bX1 · Y2 + bX2 · Y1 − 2eY1 · Y2 ) 38  Now, we take the absolute value of both sides and apply the triangle inequality: ≤  (X1 ,p)=1 (Y1 ,p)=1 X1 ≤p⌈r/2⌉ Y1 ≤p⌈r/2⌉  e X2 ≤p⌊r/2⌋ Y2 ≤p⌊r/2⌋  ·e  k p⌊r/2⌋  (2bX1 · X2 − 2aY1 · Y2 )  ℓ p⌊r/2⌋  (bX1 · Y2 + bX2 · Y1 − 2eY1 · Y2 )  Now, we concern ourselves with the sums inside of the absolute value signs. This sum is  X2  ≤p⌊r/2⌋  Y2  ≤p⌊r/2⌋  1  e X2 ·  p⌊r/2⌋  ·e Y2 ·  p⌊r/2⌋  1  (2kbX1 + ℓbY1 ) (−2kaY1 + ℓbX1 − 2ℓeY1 )  The exponent in the summand is linear in each of X2 and Y2 , so the sum is equal to zero unless both the vector multiplying X2 and the vector multiplying Y2 are componentwise congruent to zero mod p⌊r/2⌋ . So we count the number of solutions to the system of equations 2kbX1 + ℓbY1 ≡ 0  ℓbX1 − 2kaY1 − 2ℓeY1 ≡ 0  (mod p⌊r/2⌋ ) (mod p⌊r/2⌋ ).  Suppose first that b is invertible mod p⌊r/2⌋ . Consider an arbitrary component x1 of X1 . Then we can (assuming without loss of generality that (k, p) = 1; the same result is obtained if (l, p) = 1) simplify the first equation to ℓ x1 ≡ − y 1 2k and then −ℓ2 b − 2ka − 2ℓe)(y1 ) ≡ 0 ( 2k Note that since (y1 , p⌊r/2⌋ ) = 1 by assumption, this system only has solutions 2 in the case where ℓ2b − 2k2 a − 2kℓe ≡ 0, in which case there are (φ(p⌈r/2⌉ ))n solutions corresponding to each different choice of Y1 .  39  Now suppose instead that b is divisible by p. Let pγ = (b, p⌊r/2⌋ ). Then there are pγ different values of x1 that could solve the first equation for a given y1 . These values all differ by a multiple of p⌊r/2⌋−γ . Since one ℓ y1 , it follows that the solution to the first equation is given by x1 = − 2k other solutions are of the form x1 = −  ℓ y1 + cp⌊r/2⌋−γ 2k  for each component x1 of the vector of the vector X1 and each corresponding component y1 of Y1 . Note that in this case, bcp⌊r/2⌋−γ is divisible by p⌊r/2⌋ so this term dis(k) appears in the second equation upon substituting for X1 , and the second equation again becomes (  −ℓ2 b − 2ka − 2ℓe)(y1 ) ≡ 0. 2k  So we now pick up pnγ φ(p⌈r/2⌉ )n solutions if −4k2 a − ℓ2 b − 4kℓe ≡ 0 and pγ < p⌊r/2⌋ , φ(p⌊r/2⌋ )n φ(p⌈r/2⌉ )n solutions if −4k2 a − ℓ2 b − 4kℓe ≡ 0 and pγ = p⌊r/2⌋ , and 0 solutions otherwise. Since there are (p⌊r/2⌋ )2n terms in the inner two sums, we have that S(k, ℓ, pr ) is bounded above by r pγn p2⌊ 2 ⌋n φ(p⌈r/2⌉ )n χ(4k2 a − ℓ2 b − 4kℓe ≡ 0, pγ |b). Note that pγn is further bounded above by bn . Now we count the number of k, ℓ such that −4k2 a − ℓ2 b − 4kℓe ≡ 0 ( mod p⌊r/2⌋ ) We can assume without loss of generality that at least one of a ,b, and e is not divisible by p. If a is not divisible by p, then fixing ℓ and completing the square in k shows that there are at most 2 solutions (mod p⌊r/2⌋ ) where k is not divisible by p. Write k = k ′ ps where (k′ , p) = 1. Suppose that pδ divides exactly 2 terms for some δ. Then the third term is not divisible by pδ and therefore the system has no solutions. This will happen if, say, ps > b, since that would imply that the other two terms, each of which contains a factor of k, are divisible by ps , but not the bℓ2 term. So there are at most log b 1 possible values of s here. 1 + log p  40  If p2s divides all 3 terms, we’re left with the equation −4ak ′2 − 4e′ k′ ℓ − ℓ2 b′ ≡ 0  r (mod p)⌊ 2 ⌋−2s  for some b′ |b and some e′ |e (it is possible that b′ or e′ may be divisible by p). So k can take the values cp⌊r/2⌋ + ps k′ . Note that for a given ℓ there are at most two values of k′ that solve this congruence and therefore there are p⌈r/2⌉ pr solutions to the equation for which k = ps k′ , where (p, k′ ) = 1. If b is maximally divisible by pδ , but the terms containing e and a are also both divisible by pδ , then we divide the congruence by pδ to arrive at r −4ap2s−δ k′2 − 4ek′ ps−δ ℓ − ℓ2 b′ ≡ 0 (mod p⌊ 2 ⌋−δ ),  where b′ is not divisible by p. Now, noting that since p divides k and (p, k, ℓ) = 1, it follows that p doesn’t divide ℓ. So we can complete the square in ℓ and determine that for k such that pδ |k (of which there are r at most pr ), there are at most two values of ℓ (mod p)⌊ 2 ⌋−δ that solve r the congruence. Therefore, there are at most 2pr p⌈ 2 ⌉+δ solutions to the congruence (mod p)r . But since pδ ≤ b in this case, we have that there are pr p⌈r/2⌉ solutions to the congruence (mod p)r . The exact same arguments work, flipping k and ℓ around, if b is not divisible by p. Suppose that a and b but not e are divisible by pδ (and one of a and b is maximally divisible by pδ . Then one of k and ℓ must be divisible by pδ . Losing a factor of 2, say that k = k′ pδ for some k′ . Divide the equation by the pδ to reduce the problem to solving a congruence in k ′ and ℓ where at least one of a and b is relatively prime to p. The number of solutions to this congruence will be at most pδ pr p⌈r/2⌉ , and, noting that pδ < b, it follows that the number of solutions is pr p⌈r/2⌉ , as desired. So no matter what a, b, and e are, there are pr p⌈r/2⌉ solutions, where the implicit constant depends on the values of a, b, and e.  41  So the term added to 1 in the product corresponding to p is bounded above in absolute value by a constant times the expression: ∞ r=1 ∞ r=1 ∞  ≤  r=1  r  bn p2⌊ 2 ⌋n φ(p⌈r/2⌉ )n p⌈r/2⌉ pr φ(pr )2n p⌈r/2⌉ pr (p⌈r/2⌉ )n (1 − 1p )n pr−(n−1)(r/2) (1 − p1 )n ∞  3−n 1 ≤ (1 − )−n (p 2 )r p r=1  which converges so long as n ≥ 4. This converges to 1 (1 − )−n p  p  3−n 2  1−p  3−n 2  n  p  3−n 2  .  So the product over all odd primes converges for n ≥ 6. Now we show that the local factor σ2 corresponding to p = 2 also converges. It follows just as before that we need to count the number of solutions to the equations 2kbX1 + ℓbY1 ≡ 0  ℓbX1 − 2kaY1 − 2ℓeY1 ≡ 0  (mod 2⌊r/2⌋ ) (mod 2⌊r/2⌋ ).  Now, note that this system of equations only has solutions if either b is divisible by 2⌊r/2⌋ or if ℓ is divisible by 2 but not by 4 (since if ℓ is divisible by 2, k can’t be divisible by 2). Note that for sufficiently large r we must have ℓ divisible by 2 but not by 4 since b is a constant. So we let b = 2γ b′ and let ℓ = 2ℓ′ : 2γ+1 kb′ X1 + 2γ+1 ℓ′ b′ Y1 ≡ 0 kb′ X1 + ℓ′ b′ Y1 ≡ 0  (mod 2⌊r/2⌋ ) (mod 2⌊r/2⌋−γ−1 ) ℓ′  X1 ≡ − Y1 k  (mod 2⌊r/2⌋−γ−1 ) ′  We then substitute into the other equation, noting that if X1 = − ℓ kY1 + 2⌊r/2⌋−γ−1 c, the multiple of 2⌊r/2⌋−γ−1 cancels out since it is multiplied by 42  2b. So we get 2γ+1  ℓ′2 b′ Y1 − 2kaY1 − 4ℓ′ ey1 ≡ 0 (mod 2⌊r/2⌋ ). k2  Factoring out the Y1 , 2γ+1  ℓ′2 b′ − 2ka − 4ℓ′ e Y1 ≡ 0 (mod 2⌊r/2⌋ ). k  We then multiply through by k and eliminate a factor of 2 from the equation, and note that Y1 is componentwise relatively prime to pr : 2γ ℓ′2 b′ − k2 a − 2kℓ′ e ≡ 0 (mod 2⌊r/2⌋−1 ) So we again count the number of k and ℓ solving this equation. It is then clear that for r ≥ 4 there are no solutions if a and b don’t have the same parity. If a and b are both odd, this equation has at most four solutions, as can be seen by completing the square (this is always possible in at most two ways as the mixed term is always divisible by 2). As with other primes, we can assume that if a and b are even, then e must be odd. We then remove another factor of two from the equation, setting a = 2δ a′ 2γ−1 ℓ′2 b′ − 2δ−1 k2 a′ − kℓ′ e = 0 (mod 2⌊r/2⌋−2 )  which only has solutions for γ = 1, δ = 1, or r ≤ 5. So for r > 6, there are at most 8φ(2r ) solutions in k and ℓ (mod 2⌊r/2⌋−1 ). So in either case, the number of solutions in k and ℓ for a given X1 and Y1 is φ(2r )2⌈r/2⌉ . Furthermore, for a given Y1 there are ≤ 2(γ+1)n ≤ bn 1 choices for X1 . So the sum over all k, ℓ of S(k, ℓ, 2r ) is bounded by (2⌊r/2⌋ )2n φ(2⌈r/2⌉ )n 2⌈r/2⌉ φ(2r ), so as in the case for the odd primes, the local factor σ2 is finite. Therefore the product representation of the singular series converges. 3−n  p( 2 )r shown in this section, along Note that the bound φ(p1r )2 S(pr ) with the multiplicativity shown in the previous section, is enough to show that the sum representation of the singular series converges absolutely, since it follows from this statement and the multiplicativity that 3−n 3−n +ǫ 1 S(q) C ω(q) q 2 , so the sum over all q of this quantity ǫ q 2 φ(q)2 converges for n ≥ 6. 43  In the following few sections, we show that none of the local factors are equal to zero.  7.3  Local Factors and the Asymptotic Density of Solutions mod pr  In this section, it is shown that the sum  0≤r≤R  1 Sn (pr ) φ(pr )2n  is equal to the density of solutions to the system of equations in ((Z/pr Z)∗ )2n .  0≤r≤R  1 Sn (pr ) φ(pr )2n S(k, ℓ, pr )n  = 0≤r≤R (k,ℓ,pr )=1  = 0<r≤R  1 φ(pr )2n  e (k,ℓ,pr )=1 X,Y ∈((Z/pr Z)∗ )n  k ℓ f (X, Y ) + r g(X, Y ) r p p  First, consider the inner sums over k, ℓ, X, andY , fixing r for now. We interchange the order of summation: 1 φ(pr )2n  e X,Y ∈((Z/pr Z)∗ )n (k,ℓ,pr )=1  k ℓ f (X, Y ) + r g(X, Y ) r p p  The sum over k and ℓ satisfying (k, ℓ, pr ) = 1 is equal to the sum over all k and ℓ minus the sum over k and ℓ such that p|k and p|ℓ. We will first consider the sum over all k and ℓ and then subtract off the remaining terms later. Note that since the summand is linear in k and ℓ, the inner sum comes out to zero unless we have f (X, Y ) ≡ g(X, Y ) ≡ 0 mod pr , in which case each term in the sum is equal to 1 so the sum is equal to p2r . So, after multiplying by the φ(p1r )2n out front, the sum over all k and ℓ comes out 2r  r  ) ∗ n r r to pφ(pNr (p )2n , where N (p ) is the number of X and Y in ((Z/p Z) ) solving f (X, Y ) ≡ g(X, Y ) ≡ 0 mod pr .  44  Now, we look at the terms being subtracted off, in particular, the k and ℓ such that p divides both k and ℓ. 1 φ(pr )2n =  1 φ(pr )2n  e X,Y ∈((Z/pr Z)∗ )n p|k,ℓ  k ℓ f (X, Y ) + r g(X, Y ) pr p e  X,Y ∈((Z/pr Z)∗ )n k,ℓ∈Z/pr−1 Z  k ℓ f (X, Y ) + r−1 g(X, Y ) pr−1 p  Note that the sum in k and ℓ is nonzero precisely when f (X, Y ) ≡ g(X, Y ) ≡ 0 (mod pr−1 ), which happens N (pr−1 ) times mod pr−1 . Because f and g don’t change (mod pr−1 ) when pr−1 is added to any component X or Y , it follows that there are p2n N (pr−1 ) choices for X and Y for which the inner sum is nonzero. But when the inner sum is nonzero, each term in the sum is equal to 1 so the sum evaluates to p2r−2 . So the subtracted terms’ sum comes out to 1 p2r−2 p2n N (pr−1 ) φ(pr )2n 1 , = (pr−1 )2 N (pr−1 ) r−1 φ(p )2n which is the sum over all k and ℓ for the r − 1 term. Therefore, the sum 2 is telescoping, and the sum of the first N terms is equal to φ(ppr )2n N (pr−1 ), which is the density of solutions (mod pr ). Therefore, the local factor corresponding to p is the asymptotic density of solutions mod pr as r → ∞.  7.4  Finding a Large Space of Solutions with Prime Modulus  We can find a set of  p12 solutions to the system bX 2 − aY 2 ≡ 0 (mod p)  bX · Y − eY 2 ≡ 0 (mod p)  for any prime that is at least 23. Select any choices for x1 , . . . xn , y5 , y6 , . . . , yn that satisfy x21 + x22 = 0, x23 + x24 = 0, and x21 + x22 + x23 + x24 = 0 (mod p). We will show that some ”2-dimensional” set in the remaining 4 variables solves the two equations (mod p) (assuming for now that none or a ,b, and e is divisible by p). In particular, we can select y1 , y2 , y3 , and y4 such that bX 2 − aY 2 = 0 and so that bX · Y − eY 2 = 0. 45  To do this, we seek solutions to the system w1 z1 + w2 z2 = A w3 z3 + w4 z4 = B z12  + z22 + z32 + z42 = C.  Then, we get 1 (A − w1 z1 ) w2 1 z4 = (B − w3 z3 ) w4  z2 =  (we can do this because wj is invertible mod p for every j). Then, we must solve z12 +  1 1 (w2 z 2 − 2Aw1 z1 + A2 ) + z32 + 2 (w32 z32 − 2Bw3 z3 + B 2 ) = C w22 1 1 w4  We then divide by w12 + w22 and w32 + w42 , and complete the square in z1 and z3 , leaving Aw1 2 1 Bw3 2 1 (z1 − 2 ) + 2 (z3 − 2 ) (w32 + w42 )w22 w1 + w22 (w1 + w22 )w42 w3 + w42 C = 2 2 (w1 + w2 )(w32 + w42 ) A2 B2 − 2 2 − w2 (w1 + w22 )(w32 + w42 ) w42 (w12 + w22 )(w32 + w42 ) A2 w12 B 2 w32 + 2 2 + w2 (w1 + w22 )2 (w32 + w42 ) w42 (w12 + w22 )(w32 + w42 )2 The right hand side simplifies to A2 w22 B 2 w42 C − − (w12 + w22 )(w32 + w42 ) w22 (w12 + w22 )2 (w32 + w42 ) w42 (w12 + w22 )(w32 + w42 )2 , which is a nontrivial first degree polynomial expression in A2 and B 2 . We will show that only at most two choices of A make this expression zero. In particular, note that since we’re fixing A + B, the system A + B = D1 , GA2 + HB 2 = D2 has at most 2 solutions as long as G = −H, which in this case would mean that w12 + w22 + w32 + w42 = 0 (mod p) (this is a necessary 46  assumption anyway). Then, there are 4 “bad” ways to decompose the right side as a sum of residues/nonresidues (that correspond to zj being zero for some j), so as long as p is at least 23, it follows from [2] are at least 5 (and in particular ∼ 4p ) ways to write the rhs as desired, showing our result. Since A was allowed to range over p − 1 different choices, and B depends on A, and the number of decompositions of the right side of the equation at the end is a multiple of 4p , there are at least a nonzero constant times φ(p10 ) ∗ p2 solutions mod p. Suppose instead that e is equal to zero, and that b is nonzero. Then we can select X, y5 , y6 , . . . , yn however we want, and then select the remaining y variables to make the dot product zero and to make the first equation work out, as in the case where e is nonzero. If b is divisible by p, then the equations reduce to aY 2 = 0 and eY 2 = 0, which clearly has at least a 12dimensional solution space. If a is divisible by p, then the equations reduce to bx2 = 0 and bX · Y − eY 2 = 0. Here, we use a different solution strategy, selecting all the y variables first and choosing the last four x variables as in the above argument, to make both equations work out.  7.5  Some Results for Smaller Moduli  For p = 5, 11, 13, 17, or 19, we use a different strategy. A brute-force computation using the program in Appendix D shows that we can achieve any values we want for x1 y1 + x2 y2 + x3 y3 + x4 y4 and y12 + y22 + y32 + y42 simultaneously, for any choice of x1 , x2 , x3 , and x4 , guaranteeing a solution. Furthermore, another brute force computation using the program in Appendix D shows that we can accomplish the same feat mod 7 for any x1 , x2 , x3 , x4 such that at most 3 of the variables are either 1 or 6, at most 3 of the variables are either 2 or 5, and at most 3 of the variables are either 3 or 4. This, together with the lifting argument, is sufficient to show that the local factor mod 7 is positive. Mod 9, a brute force computation using the program in Appendix E shows that we can get any value for x1 y1 +x2 y2 +x3 y3 +x4 y4 that we want provided that none of x1 , x2 , x3 , and x4 are divisible by 3 (which is certainly true if they are prime), and simultaneously get y12 + y22 + y32 + y42 to be any value mod 9 as long as it’s congruent to 1 mod 3, providing us with a solution to the system (mod 9). 47  7.6  Finding a Nonsingular Solution mod p for Odd Primes p  In the previous section, we have found, for each odd prime p except for 3, a solution to the system bX 2 − aY 2 ≡ 0 (mod p)  bX · Y − eY 2 ≡ 0 (mod p). (We have also found a solution for 9). Call a solution to the system “nonsingular” if any of the following conditions hold: 1. b is not divisible by p, and the matrix 2bx5 −2ay5 by5 bx5 − 2ey5 has nonzero determinant. 2. p divides b and p divides a or e, 3. p > 3, p divides b, p doesn’t divide a or e, and the system 2b′ x5 −2ay5 b′ y5 bx5 − 2ey5 has nonzero determinant, where b′ is the largest divisor of b that is relatively prime to p, that is b′ = pbb . We will show that nonsingular solutions exist for every odd prime p, and then use a lifting argument to generate pr(2n−2) nonsingular solutions (mod p) for each p. Note that the argument in the previous section only required control over the first four variables x1 , x2 , x3 , x4 and y1 , y2 , y3 , and y4 . So there are solutions to the system (mod p) or (mod 9) for any values of x5 and y5 . So in case 1, we need only find x5 and y5 for which the quadratic form 2b(bx25 − 2ex5 y5 + ay52 ) is nonzero, which is certainly possible if e is not divisible by p (since we can complete the square in x5 to conclude that for a fixed y5 there are at least p−1 2 possible values for this expression), but also possible if e is divisible by p since then we’re left with a linear form in x25 and y52 , so fixing y5 and letting x5 vary will produce at least 2 different values for 2b2 x25 since p > 3; specifically, the quadratic residues (mod p) 2 translated by the value − eb y52 . In case 2, any solution is nonsingular, so there is nothing to do. Case 3 is handled in exactly the same way as case 1. So there is always a nonsingular solution (mod p). 48  7.7  Lifting Argument for Odd Primes when b is not Divisible by p  In this section, we produce a “lifting” argument that will generate p2n−2 nonsingular solutions (X, Y ) to the system bX 2 − aY 2 ≡ 0 (mod pr+1 )  bX · Y − eY 2 ≡ 0 (mod pr+1 ). ˜ Y˜ to the system mod pr . These generated given a nonsingular solution X, ˜ Y˜ ) (mod pr ). Therefore, if N ((a, b, e), pr ) solutions will satisfy (X, Y ) ≡ (X, is the number of solutions to the system (mod pr ), then we have that N ((a, b, e), pr+1 ) ≥ p2n−2 N ((a, b, e), pr ). ˜ Y˜ ) satisfy Suppose that (X, ˜ 2 − aY˜ 2 ≡ 0 (mod pr ) bX ˜ · Y˜ − eY˜ 2 ≡ 0 (mod pr ). bX ˜ Y˜ ) is nonsingular Suppose first that b is not divisible by p. Suppose that (X, in the sense that the matrix 2bx5 2ay5 by5 bx5 − ey5 is nonsingular (mod p). ˜ Y˜ ) (mod pr ). Take X = Let X, Y ∈ Z/(pr+1 Z) satisfy (X, Y ) ≡ (X, X + c5 f5 pr and Y = Y + d5 f5 pr , where f1 is the vector (1, 0, . . . , 0). I will show that there is a pair (c1 , c2 ) that solves the equation. Since there are p2n−2 choices for the remaining X and Y variables, we will eventually obtain p2n−2 solutions. Solving the system of equations is equivalent to solving b(X + c5 pr f5 )2 − a(Y + d5 pr f5 )2 ≡ 0 (mod pr+1 )  b((X + c5 pr f5 ) · (Y + d5 pr f5 ) + (Y + d5 pr f5 )2 ≡ 0 (mod pr+1 ). Expanding and immediately cancelling out the p2r terms gives bX 2 − aY 2 + 2bc5 pr x5 f5 − 2ay5 d5 pr f5 ≡ 0 (mod pr+1 ) 49  bX · Y − eY 2 + bc5 pr y5 f5 + bd5 x5 pr f5 − 2ed5 y5 pr f5 ≡ 0 (mod pr+1 ).  ˜ and Y˜ (mod pr ), so bX 2 − aY 2 is divisible But X and Y are congruent to X r 2 by p . Similarly, bX · Y − eY is divisible by pr . Write bX 2 − aY 2 = spr and bX · Y − eY 2 = tpr . Then the above system reduces to 2bpr x5 c5 − 2apr y5 d5 ≡ −spr  bpr y5 c5 + bpr x5 d5 − 2epr y5 d5 ≡ −tpr  (mod pr+1 ) (mod pr+1 ).  But a solution to this system is equivalent to solving 2bx5 c5 − 2ay5 d5 ≡ −s (mod p)  by5 c5 + bx5 d5 − 2ey5 d5 ≡ −t  (mod p),  which has at least one solution in c5 and d5 given the nonsingularity of ˜ Y˜ ). Since the coordinates of X and Y other than the 5th one can take (X, ˜ and Y˜ (mod pr ), there are on any values as long as they’re congruent to X 2n−2 r+1 p solutions (mod p ) corresponding to each solution (mod pr ).  7.8  Lifting Argument for Odd Primes when b is Divisible by p  At least one of a and e is not divisible by p. Assume for now that e is not divisible by p. Note that a solution to bX 2 − aY 2 ≡ 0 (mod pr+1 )  bX · Y − eY 2 ≡ 0 (mod pr+1 ) must solve b′ X 2 − a′ Y 2 ≡ 0 (mod pr+1 )  bX · Y − eY 2 ≡ 0 (mod pr+1 ) ˜ Y˜ , X, Y , and X and Y as in the where b′ |b, a′ |a, and (b′ , a′ , p) = 0. Define X, ′ previous section. If b is not divisible by p, then applying the linearization argument from the previous section gives that the system is equivalent to 2b′ x5 c5 − 2a′ y5 d5 ≡ −s −2ey5 d5 ≡ −t  (mod p) (mod p). 50  Note that any solution to the system (mod pr ) must therefore be nonsingular since we required that x5 and y5 = 0, and the system is upper triangular. Similarly, if a is not divisible by p, and (b′ , p) = 1, the system becomes  ′  ′  −ay5 d5 ≡ −s (mod p)  b x5 d5 + b y5 c5 − 2e′ y5 d5 ≡ −t  (mod p),  Which is always solvable since the first equation depends only on d5 and the second equation depends on both of c5 and d5 (noting again that y5 is assumed to be nonzero). So the only remaining case is when p b > max(p a, p e). Note that this case is never going to happen if p = 3 because the local conditions prevent it. To get this case to work, we will need to modify the lifting argument somewhat. Suppose p does not divide e. Let pδ be the largest power of p dividing a and b, and let b′ = pbδ and a′ = paδ . By assumption, p divides b′ but not a′ . Let pγ be the largest power of p dividing b′ , so that pγ+δ is the largest power of p dividing b. Then we have that we wish to solve b′ X 2 − a′ Y 2 ≡ 0  bX · Y − eY 2 ≡ 0  (mod pr−δ+1 ) (mod pr+1 ).  This system has more solutions than b′ X 2 − a′ Y 2 ≡ 0 (mod pr+1 )  bX · Y − eY 2 ≡ 0 (mod pr+1 ). ˜ Y˜ , X, and Y be as in all the other cases. If r < γ, then the Now, let X, system is solved whenever Y 2 is divisible by pr+1 , and the linearized version of this equation (following the strategy in the previous section) is solved for the correct choice of d5 . So suppose that r ≥ γ and choose X = X+c5 pr−γ f5 , and Y = Y +d5 pr f5 . Note that (X, Y ) is a solution to the system (mod pr ). We perform the linearization as in the previous section: b′ (X + c5 pr−γ f5 )2 − a′ (Y + d5 pr f5 )2 ≡ 0  b((X + c5 pr−γ f5 ) · (Y + d5 pr f5 ) + (Y + d5 pr f5 )2 ≡ 0  (mod pr+1 ) (mod pr+1 ).  51  Now, we expand and collect the terms in the same way, noting that b′ pr−γ is divisible by pr but not pr+1 : b′ (X)2 − a′ (Y )2 + 2b′ pr−γ x5 c5 f5 + 2a′ pr y5 d5 f5 ≡ 0  b(X) · (Y ) − e(Y )2 + bpr−γ y5 c5 f5 − 2epr y5 d5 f5 ≡ 0  (mod pr+1 ) (mod pr+1 ).  Note that if p divides a, then b is divisible by pγ+1 and so the bpr−γ y5 c5 f5 term drops out. Since (X, Y ) solves the system (mod pr ), this system is of the form 2b′′ x5 c5 − 2a′ y5 d5 ≡ s (mod p)  b′′′ y5 c5 f5 − 2ey5 d5 f5 ≡ t  (mod p)  ′  for some s and t, where b′′ := pbγ and b′′′ = b′′ if b = b′ (or equivalently, if p does not divide a, and b′′′ = 0 otherwise. If p divides a, then the system is upper triangular and automatically nonsingular. If p does not divide a, ˜ Y˜ ) is a nonsingular solution to the then the system is solvable as long as (X, ′′ system with b replaced by b and a replaced by a′ . In the case where p doesn’t divide a but does divide e, the argument is exactly the same, except with the roles of b′′ and b′′′ reversed.  7.9  The Local Factor mod 2  We seek to find odd solutions to the system bX 2 − aY 2 ≡ 0 (mod 2r+1 )  bX · Y − eY 2 ≡ 0 (mod 2r+1 ). The local conditions state that a, b and e are all maximally divisible by the same power of 2. We can therefore assume by division that each of a, b, and e is odd. Note that X and Y are of the form X = 2X1 + 1 Y = 2Y1 + 1 So we want to solve b(2X1 + 1)2 − a(2Y1 + 1)2 ≡ 0  b(2X1 + 1) · (2Y1 + 1) − e(2Y1 + 1)2 ≡ 0  (mod 2r+1 ) (mod 2r+1 ) 52  Expanding gives b(4X12 + 4X1 · 1 + n) − a(4Y12 + 4Y1 · 1 + n) ≡ 0 (mod 2r+1 )  b(4X1 · Y1 + 2X1 · 1 + 2Y1 · 1 + n) − e(4Y12 + 4Y1 · 1 + n) ≡ 0 (mod 2r+1 ) and combining terms gives: 4(bX12 + bX1 · 1 − aY12 − aY1 · 1) + n(b − a) ≡ 0 (mod 2r+1 )  2(2bX1 · Y1 − 2eY12 + (b − 2e)Y1 · 1 + bX1 · 1) + n(b − e) ≡ 0 (mod 2r+1 ) By the local conditions, we can assume that n(b − a) is equal to 8k for some k and that n(b − e) is equal to 2ℓ for some ℓ. Dividing the first equation by 4 and the second equation by 2 gives bX12 + bX1 · 1 − aY12 − aY1 · 1 + 2k ≡ 0 (mod 2r−1 )  2bX1 · Y1 − 2eY12 + (b − 2e)Y1 · 1 + bX1 · 1 + ℓ ≡ 0 (mod 2r ).  We can only decrease the number of solutions by insisting that the first equation hold (mod 2r ) as well. Let X1 = (x1 , . . . , xn ) and Y1 = (y1 , . . . yn ). For now, fix all the X-coordinates and fix (y6 , y7 , . . . , yn ). Let γ = x1 y1 + x2 y2 + x3 y3 + x4 y4 + x5 y5 , g = y12 + y22 + y32 + y42 + y52 , and h = y1 + y2 + y3 + y4 + y5 . We then wish to solve −ag − ah ≡ 2k′  (b − 2e)h + 2bγ − 2eg ≡ ℓ′  (mod 2r ) (mod 2r )  for g, h, with the same parity, and γ with the opposite parity. Using the fact that a is odd and therefore a unit, we can solve the first equation for g to get g ≡ −h − 2a−1 k′ (mod 2r ) which implies that g and h will have the same parity, and we solve the second equation to get (b − 2e)h + 2bγ − 2e(−h − 2a−1 k′ ) ≡ ℓ′  (mod 2r ),  (7.1)  which is guaranteed to have a solution in h because the coefficient b − 4e on h is certainly odd. So, for any γ, we can solve the system −ag − ah ≡ 2k′  (b − 2e)h + 2bγ − 2eg ≡ ℓ′  (mod 2r ) (mod 2r ) 53  in a unique way that guarantees that g and h must have the same parity. Note that since the coefficient b − 4e of h in the equation 7.1 is always odd, and the constant being added to ℓ′ is always even, it follows that h will have the parity of ℓ′ . In particular, the parity of h does not depend on the parity of γ. We will now show via a lifting argument that there are 2r(n−2) solutions in X and Y to −ag − ah ≡ 2k′  (b − 2e)h + 2bγ − 2eg ≡ ℓ′  (mod 2r ) (mod 2r ).  We now show that we can construct simultaneous solutions to y12 + y22 + y32 + y42 + y52 ≡ g  (mod 4)  x1 y 1 + x2 y 2 + x3 y 3 + x4 y 4 + x5 y 5 ≡ γ  (mod 2)  y1 + y2 + y3 + y4 + y5 ≡ h (mod 2)  whenever g and h have the same parity, and γ has the opposite parity, such that x1 , x2 , x3 are odd,x4 , x5 are even (which uniquely determines these (mod 2)), and where y4 is odd and y5 is even (which uniquely determine y4 and y5 (mod 2) and y42 and y52 (mod 4)). We then take exactly g − 1 of y1 , y2 , and y3 to be odd. We also take y4 and to be odd, making the equation for g work out. Finally, since yj2 and yj have the same parity, it follows that y1 + y2 + y3 + y4 + y5 must be congruent to h (mod 2), and since x1 y1 + x2 y2 + x3 y3 has the same parity as g − 1, it has the opposite parity of h and therefore γ and h will have opposite parity. ˜ and Y˜ satisfying It suffices to show that given g, h, γ (mod 2r+1 ), and X y12 + y22 + y32 + y42 + y52 ≡ g  (mod 2r+1 )  y1 + y2 + y3 + y4 + y5 ≡ h (mod 2r )  x1 y 1 + x2 y 2 + x3 y 3 + x4 y 4 + x5 y 5 ≡ γ  (mod 2r ),  ˜ (mod 2r ) and Y ≡ Y˜ and any X and Y (mod 2r+1 ) satisfying X ≡ X r (mod 2 ), where y4 is odd, y5 is even, x1 , x2 , and x3 are odd, x4 and x5 are even, we can select d3 , d4 and d5 , Y = (y1 , y2 , y3 +2r d3 , y4 +2r d4 , y5 +2r d5 , ) so that y12 + y22 + (y3 + 2r d3 )2 + (y4 + 2r d4 )2 + (y5 + 2r d5 )2 ≡ g  y1 + y2 + (y3 + 2r d3 ) + (y4 + 2r d4 ) + (y5 + 2r d5 ) ≡ h  (mod 2r+2 ), (mod 2r+1 ), 54  and x1 y1 + x2 y2 + x3 (y3 + 2r d3 ) + x4 (y4 + 2r d4 ) + x5 (y5 + 2r d5 ) ≡ γ  (mod 2r+1 ).  This is good enough because there are 2n−5 variables for which we can make 2 choices at each step that determine k and ℓ, and 2 additional variables y1 and y2 that can be chosen in any way, leading to 2(2n−3)r solutions for a given triple (g, h, γ), and the space of solutions to the system given a fixed r k′ and ℓ′ is a hyperplane in g, h, γ, which has 22 solutions that satisfy the parity condition for γ. We do this in the following way: γ does not depend on d4 or d5 , so select d3 to make x1 y1 + x2 y2 + x3 (y3 + 2n−1 d3 ) + x4 y4 + x5 y5 ≡ γ (mod 2r+1 ). Now, if r > 1, the expression for g does not depend on d5 , since y5 is even so (y5 + 2r d5 )2 − y52 will always be divisible by 2r+2 . So select d4 to make y12 + y22 + (y3 + 2r d3 )2 + (y4 + 2r d4 )2 + y52 ≡ g (mod 2r+2 ). Finally, we select d5 to make y1 + y2 + y3 + y4 + y5 + 2r (d3 + d4 + d5 ) congruent to h (mod 2)r . If instead r = 1, then the roles of d4 and d5 are reversed, since if y5 is odd then (y5 + 2r d5 )2 − y52 will always be divisible by 8. So there are 2(n−2)r values for x1 , . . . , xn , y1 , . . . , yn that satisfy bX 2 − aY 2 ≡ 0  bX · Y − eY 2 ≡ 0  (mod 2r ) (mod 2r ).  55  Chapter 8  The Singular Integral A  In this section, we wish to show, for q ≤ (log N ) 2 , that the integral Ln (δ, γ; k, ℓ, q) dδdγ = |δ|,|γ|≤  M (k,ℓ,q)  N2 q(log N)A  X,Y  e((δ(b(X)2 − a(Y )2 )) ·e(γ(bX · Y − eY 2 )) X Y ·χ χ N N  converges to some nonzero value L that is independent of q, and that for A (log N ) 2 < q < (log N )A , the difference between Kn (k, ℓ, q)L(δ, γ; k, ℓ, q) MK,ℓ,q) (k,ℓ,q)=1  and L (k,ℓ,q)=1 Kn (k, ℓq) is negligible. We follow the strategy used in [1]. In particular, we first show that, where L(δ, γ) is the integral for x and y each single-dimensional variables in R, Lemma 8.0.1. L(δ, γ)  N 2 log(N ) . 1 + N 2 (|δ| + |γ|)  Proof. We start by making a change of variables to replace and y. Then L(δ, γ) = N 2 x,y  x N  and  y N  by x  e N 2 (δ(b(x)2 − a(y)2 ) + γ(bxy − e(y)2 )) χ(x)χ(y)dxdy  We consider |L(δ, γ)|2 = L(δ, γ)L(δ, γ). Then |L(δ, γ)|2 = N 4  x,y,x′ ,y ′  e N 2 (δb((x′ )2 − x2 ) − a((y ′ )2 − y 2 )) ·e N 2 γ(b((x′ )(y ′ ) − xy) − e((y ′ )2 − y 2 )))  ·χ(x)χ(y) dxdydx′ dy ′  56  Now, write u = x′ − x, v = y ′ − y. Then this integral is equal to N4  e N 2 (δ(b(u(u + 2x)))) x,y,u,v  ·e N 2 (δ(a(v(v + 2y))))  ·e N 2 (γ(b(uv + (x + u)y + (y + v)x − 2xy)))  ·e N 2 (γ(−e(v(v + 2y)))) χ(x)χ(y) dxdydudv = N4 u,v  e( N 2 (δ(bu2 − av 2 ) + γ(buv − ev 2 )) ·  x,y  e N 2 (δ(2bux − 2avy))  e N 2 γ(buy + bvx − 2evy) χ(x)χ(y) dxdydudv. As with the singular series, we use the triangle inequality: ≤ N4  u,v  x,y  e N 2 (δ(2bux − 2avy)) e N 2 γ(buy + bvx − 2evy) χ(x)χ(y)dxdy dudv.  Now let u′ be the coefficient of x and let v ′ be the coefficient of y. Then we can split the inner integral into the product of two integrals of the form e(tx)χ(x)dx. Note that by the triangle inequality each of these two integrals is at most 2, and by directly carrying out the integration, it follows that each integral is bounded above by a constant over t. So, in particular, 1 . Therefore, we have that we have that e(tx)χ(x)dx 1+t  x,y  e N 2 (δ(2bux − 2avy) + γ(buy + bvx − 2evy) dxdy  1 1 2 ′ 1 + N |u | 1 + N 2 |v ′ | Now, we try to count the measure of the set where u′ and v ′ are of a given size. Since u and v are less than 2, and a, b, and e are all constants, it follows that u′ and v ′ are each bounded above by some constant c. Split −2 the box [−c, c] × [−c, c] into N 4 blocks of side length N2 We want to get an estimate on the measure of the (u, v) that correspond to (u′ , v ′ ) in each block Bi,j . Fix (u1 , v1 ) such that (u′1 , v1′ ) is in Bi,j . Then by linearity, if (u2 , v2 ) such that (u′2 , v2′ ) is in Bi,j , then it follows that (u1 − u2 , v1 − v2 ) satisfies |(u1 − u2 )′ | ≤ N12 , and |(v1 − v2 )′ | ≤ N12 . So therefore the measure of 57  the set of (u, v) such that (u′ , v ′ ) is in Bij is bounded above by the measure of the set B, where B is the set of (u, v) for which |u′ | ≤ N12 and |v ′ | ≤ N12 . So, we have that L(δ, γ)2  N4 0≤s N 2 0≤t N 2  1 1 meas(B) 1+s1+t  N 4 log2 (N )meas(B).  So all we need to do now is estimate meas(B). but |u′ | is always at least a constant times max(|γu|, |δv|), and |v ′ | is always at least a constant times max(|γv|, |δu|), so it follows that |(u′ , v ′ )| |u′ | + |v ′ | (|δ| + |γ|) max(u, v) So, 1 }), meas(B) meas({(u, v) : max(u, v) ≤ 2 N (|δ| + |γ|)  because if |(u′ , v ′ )| is smaller than above expression is  1 N2  then max(|u′ |, |v ′ |) <  1 . N2  But the  1 . N 4 (|δ| + |γ|)2  So,  L(δ, γ)  N 2 log(N ) , N 2 (|δ| + |γ|)  But we also know trivially that |L(δ, γ)|2 < N 4 , so combining these estimates gives N 2 log(N ) . L(δ, γ) 1 + N 2 (|δ| + |γ|)  as desired.  The next step is to extend the integral in δ and γ to all of R2 with a small error. In other words, we want to calculate  |γ|+|δ|≥N −2 q −1 (log N )A  |L(δ, γ)|n −  |γ|+|δ|<N −2 (log N )A  = |γ|+|δ|≥N −2 q −1 (log N )A  ≤ (log N )n = 4(log N )n  |L(δ, γ)|n dγdδ  |L(δ, γ)|n dγdδ  |γ|+|δ|≥N −2 q −1 (log N )A  |γ|+|δ|≥N −2 q −1 (log N )A γ,δ≥0  1 |γ| + |δ| 1 |γ| + |δ|  n  dγdδ n  dγdδ  58  ∞  = 4(log N )n  u  u=N −2 q −1 (log N )A  1 ( )n dδdu δ=0 u  ∞  = 4(log N )n  u−n+1 du  u=N −2 q −1 (log N )A  =  4 (log N )n N 2n−4 q n−2 (log N )A(−n+2) n−2 A  N 2n−4 (log N )n− 2 (n−2) ,  A  if q < (log N ) 2 . But we have from the singular series bound that  (k,ℓ,q)=1  3  q− 2  |Kn (k, ℓ, q)|  A  (log N )− 4 ,  A  q>(log N ) 2  A q>(log N ) 2  so the total contribution from extending the integral in δ and γ for all the A (k, ℓ, q) where q is at least (log N ) 2 is bounded above by A  N 2n−4 (log N )n− 4 . Therefore, we can extend the integral in γ and δ to all of R2 with an error term that is smaller than the main term, which will be O(N 2n−4 ). This leaves us with the following integral:  δ,γ  X,Y  e (δ(b(X)2 − a(Y )2 ) + γ(bX · Y − eY 2 ) ·χ  X N  χ  Y N  dXdY.  Note that by the estimate in the previous lemma, this integral is absolutely convergent. We are therefore free to rearrange the integrals however we want. Note that the integral is unaffected by removing the hyperplane where x1 = 0. We then split the R2n without this hyperplane into two half-spaces, H and G, where H is the halfspace where x1 > 0 and G is the halfspace where x1 < 0, and write the integral as a sum of the integral over H and the integral over G. Since the function we’re integrating is even (in the sense that plugging in (−X, −Y ) always yields the same value as plugging in (X, Y ), we know that  δ,γ  (X,Y )∈R2n  e (δ(b(X)2 − a(Y )2 ) + γ(bX · Y − eY 2 ) 59  ·χ =2 δ,γ  (X,Y )∈H  X N  χ  Y N  dXdY  e (δ(b(X)2 − a(Y )2 ) + γ(bX · Y − eY 2 )  ·χ  X N  χ  Y N  dXdY  We make the following change of variables in this integral: Send the vector (X, Y ) to (U, V ) where U = (u1 , u2 , . . . , un ) := (bX 2 − aY 2 , x2 , x3 , . . . , xn ) V = (v1 , v2 , . . . , vn ) := (bX · Y − eY 2 , y2 , y3 , . . . , yn ). First, I will verify that this change of variables is injective on each of G and H, and, for any selection of u2 , . . . , un , v2 , . . . , vn ”misses” only a ray in the (u1 , v1 )-plane. Fix x2 , . . . , xn , and y2 , . . . , yn . Then, we want to solve the equations bX 2 − aY 2 = u1 bX · Y − eY 2 = u2  for x1 and y1 . Moving all the other components of X and Y to the other side, we want to solve a system of the form bx21 − ay12 = C1 bx1 y1 − ay12 = C2 . For convenience, we will now replace x1 by x and y1 by y. I will begin by checking the case where C1 is nonnegative. Then, we have (remembering that we’re looking for solutions in the half-plane where x is nonnegative, but it doesn’t matter whether we’re in G or H since this term will be squared anyway) √ bx = C1 + ay 2 . This will be strictly positive unless C1 and y are both equal to zero. Upon substituting this into the other equation, we get √ by C1 + ay 2 − ey 2 = C2 by 2 (C1 + ay 2 ) = (ey 2 + C2 )2 bC1 y 2 + ab(y 2 )2 = e2 (y 2 )2 + 2eC2 y 2 + C22 60  0 = (ab − e2 )(y 2 )2 + (bC1 − 2eC2 )y 2 − C22 . We then use the quadratic formula: y2 =  2eC2 − bC1 ±  (bC1 − 2eC2 )2 + 4(ab − e2 )C22 . 2(ab − e2 )  But our condition on a, b, and e implies that ab − e2 is always positive. So, as long as C2 is nonzero, we have that (bC1 − 2eC2 )2 + 4(ab − e2 )C22 > |2eC2 − bC1 |, so exactly one of the possible values for y 2 is positive. If C2 is zero, then one of the possible values for y 2 will be zero and the other one will be negative, again allowing for only one plausible value for y 2 . Furthermore, since x was assumed to be nonzero, if (x, y) is a solution of bxy − ey 2 = C2 , then −y will not be a solution, so the system of equations has exactly one real solution satisfying x > 0 as long as C1 is nonnegative and C2 is nonzero, or if C1 is positive regardless of the sign of C2 . If C1 is negative, then bx2 − C1 is positive, so it makes sense to write that 1 y = ±√ a  bx2 − C1 ,  since bx2 − C1 is a nonnegative number. So we want to solve e(bx2 − C1 ) = C2 a  bx ±√ a  bx2 − C1 −  bx ±√ a  bx2 − C1 = C2 +  b2 x 2 (bx2 − C1 ) = a  be 2 eC1 x − a a  bex2 eC1 C2 + − a a  2  e2 b2 eC1 bex2 eC1 2 b3 (x2 )2 b2 C1 x2 − = 2 (x2 )2 + 2(C2 − ) + (C2 − ) a a a a a a So, multiplying both sides by a2 gives ab3 (x2 )2 − ab2 C1 x2 = e2 b2 (x2 )2 + 2(aC2 − eC1 )bex2 + (aC2 − eC1 )2 Then, we solve for x2 using the quadratic formula: x2 =  ab2 C1 + 2(aC2 − eC1 )be 2(ab3 − e2 b2 ) (−ab2 C1 − 2(aC2 − eC1 )be)2 + 4(ab3 − e2 b2 )(aC2 − eC1 )2 . ± 2(ab3 − e2 b2 ) 61  Here, we notice that 4ab3 − e2 b2 is nonnegative since e2 < ab. So the square root term is larger in magnitude than the other term in the numerator as long as we don’t have aC2 = eC1 , meaning that there is exactly one possible value for x2 . If aC2 = eC1 , then one of the roots is zero, and the other root is ab2 C1 , which is negative because we were operating under the assumption that C1 was negative. So the system bx2 − ay 2 = C1  bxy − ey 2 = C2 will always have exactly one real solution with x > 0 unless aC2 = eC1 where C1 < 0. That is, for a fixed u2 , . . . , un , v2 , . . . , vn , we hit each point (U, V ) except for a ray depending on u2 , . . . , un , v2 , . . . , vn exactly once when x1 > 0 and exactly once when x1 < 0. The Jacobian matrix J(X, Y ) for the has the following form (when the X and Y variables are arranged in the order (x1 , y1 , x2 , y2 , . . . , xn , yn ):   2bx1 −2ay1 0 ··· 0 J(X, Y ) =  by1 bx1 − 2ey1 0 · · · 0 , J0 I2n−2  So the Jacobian determinant |J(X, Y )| is the value 2b2 x21 − 4bex1 y1 + 2aby12  Since we’re looking at the hyperplane where x1 is positive, we know that if y1 is nonpositive then this quantity will be (strictly) positive. So we need only consider the case where y1 is strictly positive. We factor out a 2b from the Jacobian determinant: 2b(bx21 − 2ex1 y1 + ay12 ) √ However, we assumed that e < ab, so the above expression is strictly larger than √ 2b(bx21 − 2 abx1 y1 + ay12 ) √ √ = 2b( bx1 − ay1 )2 , which is nonnegative. Therefore, as long as we’re not on the hyperplane where x1 is zero, the Jacobian determinant for this change of variables is 62  strictly positive. Therefore, since the determinant of this Jacobian is positive everywhere except on the hyperplane H where x1 is equal to zero, |J −1 (U, V )| is well-defined and positive. So we make the change of variables in our integral to get e(δu1 + γv1 )ρ(u1 , U ′ , v1 , V ′ ) dU dV dδdγ,  2 R2  (X,Y )∈H  where φ is the transformation representing the change of variables, ρ is the nonnegative function χ(φ−1 (U, V ))|J(U, V )|−1 , and U ′ and V ′ are the vectors (u2 , . . . , un ) and (v2 , . . . , vn ). Now, it suffices to show that by excluding the places where x1 = 0, haven’t excluded much of the integral in u1 and v1 . In other words, let’s fix U ′ and V ′ , and see which values for the vector (u1 , v1 ) we exclude by forcing x1 to be nonzero. Then u1 = bx21 − ay12 + C1  v1 = bx1 y1 − ey12 + C2 .  So, the set of points we get when x1 = 0 is the line (−ay12 + C1 , −ey12 + C2 ). Note that this ray is a set of measure zero in the (u1 , v1 ) plane. In other words, removing this ray never affects the integral in (u1 , v1 ), regardless of the other coordinates of U and V . But the integral in u1 and v1 is the Fourier transform of ρ in the u1 and v1 variables. So the above integral comes out to ρ(δ, U ′ , γ, V ′ ) dδdγdU ′ dV ′ . 2 R2n−2  R2  By the Fourier inversion theorem, this is equal to ρ(0, U ′ , 0, V ′ ). dU ′ dV ′  2 R2n−2  But ρ(0, U ′ , 0, V ′ ) is strictly positive at any point U ′ , V ′ for which there exists a positive x1 and a real y1 such that (x1 , U ′ ) and (y1 , V ′ ) satisfy the equations bX 2 − aY 2 = 0  bX · Y − eY 2 = 0. Since ρ is continuous and nonnegative, and since we know by the result in [1] that that a, b, and e correspond to the squares of the side lengths of a triangle with rational coordinates, it follows that these equations have at least one solution with x1 > 0, and therefore the singular integral is positive since the integrand must be strictly positive on some open set. 63  Bibliography [1] James Blair. On the Embedding of Triangles into Integer Lattices. PhD thesis, University of Georgia, 2004. [2] Michele Elia Chris Monico. Note on an additive characterization of quadratic residues modulo p. Journal of Combinatorics, Information & System Sciences, 31:209–215, January 2006. [3] Henry Davenport. Cubic forms in thirty-two variables. Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences, 251(993):193–232, March 1959. [4] Timothy Gowers. Vinogradov’s three-primes theorem. URL: https://www.dpmms.cam.ac.uk/~wtg10/3primes.dvi [cited 2013-0411]. [5] Loo-Keng Hua. Some results in the additive prime-number theory. Quarterly Journal of Mathematics, os-9(1), 1938. [6] Melvyn B. Nathanson. Additive Number Theory: the Classical Bases. Springer-Verlag, New York, 1996. [7] Robert-C Vaughan. Sommes trigonom´etriques sur les nombres premiers. C.R. Acad. Sci. Paris S´er A-B, 285(16), 1977.  64  Appendix A  Changing the Von Mangoldt Factors to Logarithmic Factors We want to make the change from evaluating Λ(X)Λ(Y )χ(X, Y ) |X|,|Y |≤N  where χ is the indicator function for the X and Y satisfying bX 2 − aY 2 = 0  bX · Y − eY 2 = 0. We want to change the Λ functions into logarithm functions times the indicator of the primes. To do this, we note that the sum of log pk over all 1 prime powers pk less than or equal to N is at most O(N 2 (log N )A ) for some A. So Λ(X)Λ(Y )χ(X, Y ) |X|,|Y |≤N  =  log(x1 )Λ(x2 , . . . , xn )Λ(Y )χ(X, Y ) |X|,|Y |≤N x1 prime 3  Λ(X ′ )Λ(Y ′ )χk,ℓ (X ′ , Y ′ )  +O N 2 (log N )A max k,ℓ  |X ′ |,|Y ′ |≤N  We now trivially estimate the Von Mangoldt factors in the error term by a large power of log N . =  log(x1 )Λ(x2 , . . . , xn )Λ(Y )χ(X, Y ) |X|,|Y |≤N x1 prime 3  χk,ℓ (X ′ , Y ′ ).  +O N 2 (log N )B max k,ℓ  |X ′ |,|Y ′ |≤N  65  Now we apply the result in Appendix C to the sum in the error term. So the order of the sum is N 2(n−1)−4 = N 2n−6 . So the error term is 9 O(N 2n− 2 (log N )B ), which is smaller than the main term. We apply the same estimate in each of the other variables to change from estimating Von Mangoldt factors to estimating the logarithm function applied to the primes.  66  Appendix B  Eliminating the Logarithmic Factors from the Sum We now have an asymptotic estimate for the number of prime solutions to the system bX 2 − aY 2 = 0  bX · Y − eY 2 = 0 when weighted by the logarithmic factors. We now seek to obtain an asymptotic the logarithmic weights by the following method: We start with the sum n  n  log(xi ) log(yj )χ(X, Y ) = CN 2n−4 , |X|,|Y |≤N i=1 j=1 X,Y prime  where χ(X, Y ) is the indicator that X and Y solve the system. We cut the sum off at (logNN )A , where A is a dimension-dependent power that will be determined later: n  n  log(xi ) log(yj )χ(X, Y ) X,Y  N (log N)A  i=1 j=1  X,Y prime n  n  log(xi ) log(yj )χ(X, Y ) = CN 2n−4 .  + N (log N)A  ≤X,Y ≤N i=1 j=1  X,Y prime  Note that if X and Y are not pointwise greater than (logNN )A , then there is (at least) one coordinate xj or yj such that xj < (logNN )A or yj < (logNn)A Assume this coordinate is x1 . Then, after losing a factor of 2n (since there are 2n possible variables that could be less than (log N )A ), the first sum is  67  bounded above by n  n  log(xi ) log(yj )χ(X, Y ) X,Y  N (log N)A  i=1 j=1  X,Y prime n  n  log(xi ) log(yj )χ((x, X ′ ), Y ). x1 <  N (log N)A  |X ′ |,|Y |≤N i=1 j=1  x1 prime  Now, we apply a trivial estimate to the sum in x1 and y1 , as well as all of the logarithm factors appearing in the sum:   ≤   N2 (log N )2n max  A c1 ,c2  (log N )  X ′ prime Y ′ prime X ′ ≤N Y ′ ≤N   χc1 ,c2 (X ′ , Y ′ )   where χc1 ,c2 (X ′ , Y ′ ) is the indicator for solutions to bX 2 − aY 2 = c1  bX · Y − eY 2 = c2 . Removing the restrictions in the sum that force X ′ and Y ′ to be prime can only make the sums bigger:   2 N (log N )2n max  χc1 ,c2 (X ′ , Y ′ ) . ≤ c1 ,c2 (log N )A ′ ′ X ≤N Y ≤N  We then use the result in Appendix C to conclude that the above sum is N 2n−4 . (log N )A−2n  Now, the other sum will become the main term. n  n  log(xi ) log(yj )χ(X, Y ). N (log N)A  ≤X,Y ≤N i=1 j=1  X,Y prime  68  We estimate each logarithmic factor by log N . The error in this estimate in each factor will be at most a constant times log log N . = (log N )2n  χ(X, Y ) N (log N)A  ≤X,Y ≤N  X,Y prime 2n−1  +O((log N )  log log N )  χ(X, Y ) N ≤X,Y (log N)A  ≤N  X,Y prime  = (1 + o(1)) (log N )2n  χ(X, Y ). N ≤X,Y (log N)A  ≤N  X,Y prime  So, if we select A = 2n + 1, we get that  N (log N)A  ≤X,Y ≤N  χ(X, Y ) ∼  CN 2n−4 . (log N )2n  X,Y prime  The sum of the remaining terms without the logarithmic factor will be bounded above by the sum of the remaining terms with the logarithmic factor, which we showed to be smaller than the main term. So  X,Y ≤N X,Y prime  χ(X, Y ) ∼  CN 2n−4 (log N )2n  69  Appendix C  The Number of Solutions to a Modified System In this appendix, we show that the number of integer solutions to the system of equations bX 2 − aY 2 = c1  bX · Y − eY 2 = c2 is bounded above by CN 2n−4 , where C is a constant depending on a, b, and e but not on c1 or c2 . We can use most of [1] verbatim, but a few tiny modifications need to be made to some of the arguments in this slightly more general setting. The integral we are trying to estimate is slightly different from the one in [1]:  1 0  1 0    e(−c1 α − c2 β)   |x|,|y|≤N  n  e(α(bx2 − ay 2 ) + β(bxy − ey 2 )) dα dβ.  However, since the minor arc estimates in [1] involve an immediate invocation of the triangle inequality, the extra e(−c1 α− c2 β) term in my integral immediately drops out and the minor arc estimates are exactly the same. So it is only necessary to check that the major arc estimates work in almost the same way as in [1]. The decomposition of the major arcs into the singular series and the singular integral is almost exactly the same: The terms in the singular series are now Kn (k, ℓ, q) =  k ℓ 1 e(−c1 − c2 ) 2n q q q  e S,T  kbS 2 + ℓbS · T − (ka + ℓe)T 2 q  , 70  where the sum over S and T is taken mod q, and the singular integral is now L(δ, γ, k, ℓ, q) = e(−c1 δ − c2 γ)  exp (2πiφ(X, Y )) χ X,Y  X P  χ  Y P  dXdY.  Because only an upper bound is necessary, there is no need to show that the singular series or singular integral is nonzero. The bounds in [1] on K(k, ℓ, q) (using the definition of K(k, ℓ, q) given in [1]) are exactly the same. Since the bounds on Kn (q) that are used to show the convergence of the sum depend only on the absolute value of Kn (k, ℓ, q), which hasn’t changed here since we only multiplied by a unit complex number, it follows that the singular series has the same termwise upper bound as in [1], and therefore the singular series is bounded above by a constant not depending on c1 or c2 . As for the singular integral, the extension of the integral in δ and γ to all of R works out in the same way as in [1] (for which the singular integral is the same as the singular integral in this paper). We make the same change of variables as in [1]. The only difference is that, in the last step, when we apply the Fourier inversion theorem, we arrive at the expression ρ(  c2 c1 , U ′ , 2 , V ′ ). N2 N  Since the system will never have any solutions unless c1 and c2 are bounded above by a dimension-dependent constant times N , it follows that this is bounded above by the maximum of ρ on a compact set not depending on c1 and c2 , and therefore the constant arising from the singular integral does not depend on c1 and c2 . Therefore, the number of solutions to the system bX 2 − aY 2 = c1  bX · Y − eY 2 = c2 is bounded above by CN 2n−4 , where C is a constant that does not depend on c1 or c2 .  71  Appendix D  Program for Testing Prime Moduli Between 5 and 19 The computation performed by the following program is referenced in the section ”Some Results for Small moduli.” import java.util.Scanner; /*This program calculates the possible vector sums * (x_1r_1+x_2 r_2+x_3r_3+x_4r_4,r_1^2+r_2^2+r_3^2+r_4^2) * and prints out the values for x_j that don’t give a * complete list. This only works for prime moduli and * should be used only for primes that are at most 19. */ public class BruteForceSmallModulus { public static void main(String[] args){ //select a modulus Scanner scanner = new Scanner(System.in); System.out.println("Which modulus would you like to test?"); int modulus = scanner.nextInt(); //make a list of (r, r^2) mod p int[][] qrs = new int[modulus - 1][2]; boolean modulusok = true; for(int i=0; i< modulus - 1; i++) { qrs[i][0] = i + 1; qrs[i][1] = ((i+1) * (i+1))%modulus; }; //initialize the list of vectors int[][]vectorlist = qrs; for(int x1 = 1; x1 < modulus; x1++ ) { for(int x2 = 1; x2 < modulus; x2++) { for(int x3 = 1; x3 < modulus; x3++) { for(int x4 = 1; x4 < modulus; x4++) { //initialize the list of vectors 72  vectorlist = qrs; //multiply the first term of each vector by x_1 //make vectorlist point to a different array vectorlist = mult(vectorlist, x1, modulus); //add (x_2 r_2, r_2^2) for every r_2 vectorlist = vecsums(vectorlist, qrs, modulus,x2); //add (x_3 r_3, r_3^2) for every r_3 vectorlist = vecsums(vectorlist, qrs, modulus,x3); //add (x_4 r_4, r_4^2) for every r_4 vectorlist = vecsums(vectorlist, qrs, modulus,x4); //test to see if the list of vectors is complete if(vectorlist.length < modulus * modulus) { if(true == modulusok) { System.out.println("Here are the bad values:"); modulusok = false; } System.out.print(x1); System.out.print(x2); System.out.print(x3); System.out.println(x4); } } } } //output current progress System.out.print("Progress:"); System.out.println(x1 + " out of " + (modulus - 1)); } //produce output if every quadruple works if(true == modulusok) { System.out.println("There are no problems mod " + modulus); } } /*Create a list of sums of 2 vectors in a list of vectors * multiplying the first component of the vectors in the * second list by x*/ static int[][]vecsums(int[][] in1, int[][] in2, int p, int x){ int[][] preout = new int[in1.length * in2.length][2]; //list (v_1 + x_2 v_2, v_1 + v_2) for(int i = 0; i < in1.length; i++) { 73  for(int j = 0; j < in2.length; j++) { preout[i * in2.length + j][0] = (in1[i][0] + x*in2[j][0]) % p; preout[i * in2.length + j][1] = (in1[i][1] + in2[j][1]) % p; } } //eliminate redundancies in the list int[][] out = eliminate(preout, p); return out; } /*eliminate redundancies in a list of vectors*/ public static int[][] eliminate(int[][] input, int modulus) { //initialize boolean[][] inset = new boolean[modulus][modulus]; for(int i=0; i< modulus; i++) { for(int j = 0; j< modulus; j++) { inset[i][j] = false; } } //mark the elements in the set for(int i= 0; i< modulus; i++) { for(int j = 0;j < modulus; j++) { for(int k = 0; k < input.length; k++) { if(input[k][0] == i && input[k][1] == j) { inset[i][j] = true; } } } } //determine the length of the output int size = 0; for(int i = 0; i< modulus; i++) { for(int j = 0; j< modulus; j++) { if(inset[i][j] == true) { size ++; } } } //include one copy of each vector in the list int index= 0; int[][] out = new int[size][2]; 74  for(int i = 0; i< modulus; i++) { for(int j= 0; j< modulus; j++) { if(inset[i][j] == true) { out[index][0] = i; out[index][1] = j; index++; } } } return out; } /*Multiplies the first term of a vector by x*/ public static int[][] mult(int[][] input, int x, int modulus){ //initialize int[][] out = new int[input.length][2]; for(int i = 0; i< out.length; i++) { out[i][0] = input[i][0]; out[i][1] = input[i][1]; } //multiply the first term by x for(int i=0; i<input.length; i++) { out[i][0] = input[i][0] * x % modulus; } return out; } }  75  Appendix E  Program for Testing the Value 3 The computation performed by the following program is referenced in the section ”Some Results for Small moduli.” /*This program shows the existence of solutions mod 9*/ public class BruteForceNine { public static void main(String[] args){ System.out.println("Here are the bad values mod 9."); //set the modulus to 9 int modulus = 9; int[][] qrs = new int[6][2]; int count = 0; for(int i=0; i< 6; i++) { //skip over multiples of 3 if(count % 3 == 2) { count++; } //find (r, r^2) mod 9 qrs[i][0] = count + 1%modulus; qrs[i][1] = ((count + 1) * (count +1))%modulus; count++; }; //initialize the list of sums int[][]vectorlist = qrs; for(int x1 = 1; x1 < modulus; x1++ ) { for(int x2 = 1; x2 < modulus; x2++) { for(int x3 = 1; x3 < modulus; x3++) { for(int x4 = 1; x4 < modulus; x4++) { //initialize the sums vectorlist = qrs; 76  //multiply linear term by x_1 //make vectorlist point to a different array vectorlist = mult(vectorlist, x1, modulus); //add (x_2 r_2, r_2^2) for every r_2 vectorlist = vecsums(vectorlist, qrs, modulus,x2); //add (x_3 r_3, r_3^2) for every r_3 vectorlist = vecsums(vectorlist, qrs, modulus,x3); //add (x_4 r_4, r_4^2) for every r_4 vectorlist = vecsums(vectorlist, qrs, modulus,x4); //Print out (x_1, x_2, x_3, x_4) that //don’t yield a complete list for //(x_1r_1 + ... +x_4r_4, r_1^2,r_2^2r_3^2r_4^2) if(vectorlist.length < 27) { System.out.print(x1); System.out.print(x2); System.out.print(x3); System.out.println(x4); } } } } } } /*Create a list of sums of 2 vectors in a list of vectors * multiplying the first component of the vectors in the * second list by x*/ static int[][]vecsums(int[][] in1, int[][] in2, int p, int x){ int[][] preout = new int[in1.length * in2.length][2]; for(int i = 0; i < in1.length; i++) { //initialize the output for(int j = 0; j < in2.length; j++) { preout[i * in2.length + j][0] = (in1[i][0] + x*in2[j][0]) % p; preout[i * in2.length + j][1] = (in1[i][1] + in2[j][1]) % p; } } //eliminate the redundancy in the output int[][] out = eliminate(preout,p); return out; } 77  /*eliminate redundancies in a list of vectors*/ public static int[][] eliminate(int[][] input, int modulus) { boolean[][] inset = new boolean[modulus][modulus]; //initialize for(int i=0; i< modulus; i++) { for(int j = 0; j< modulus; j++) { inset[i][j] = false; } } //mark off the vectors in the list for(int i= 0; i< modulus; i++) { for(int j = 0;j < modulus; j++) { for(int k = 0; k < input.length; k++) { if(input[k][0] == i && input[k][1] == j) { inset[i][j] = true; } } } } //determine the length for the output vector int size = 0; for(int i = 0; i< modulus; i++) { for(int j = 0; j< modulus; j++) { if(inset[i][j] == true) { size ++; } } } int index= 0; //output the list without redundancies int[][] out = new int[size][2]; for(int i = 0; i< modulus; i++) { for(int j= 0; j< modulus; j++) { if(inset[i][j] == true) { out[index][0] = i; out[index][1] = j; index++; } } } 78  return out; } /*Multiplies the first coordinate of a vector * by x*/ public static int[][] mult(int[][] input, int x, int modulus){ int[][] out = new int[input.length][2]; //initialize the output for(int i = 0; i< out.length; i++) { out[i][0] = input[i][0]; out[i][1] = input[i][1]; } //multiply the first coordinate by x for(int i=0; i<input.length; i++) { out[i][0] = input[i][0] * x % modulus; } return out; } }  79  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0071953/manifest

Comment

Related Items