• No results found

Chapter A

Appendix: Estimates for the Weighted Squares

The material in this section is entirely standard and we give barely enough detail to make this exposition self-contained. For an introduction to the circle method, see [Vau81].

By Dirichlet’s Theorem, t/N ∈ I(a/q,(qQ)−1) for some 1 ≤ a ≤ q ≤ Q,(a, q) = 1.

Call the set of those t for which q ≤ R the major arcs and the set of those t for which R < q ≤ Q = N/K the minor arcs. It is a typical feature of the Hardy-Littlewood method that the exact values of the boundaries between the arcs need to be determined in the course of the proof. Throughout, R will be of the order of magnitude of K =el2 defined in the introduction to Chapter 1.

We define the generating function of the weighted squares by FS(θ) = X

x2≤N1

√2x N1

e(x2θ).

Note that FS(t/N)/N coincides with our earlier definition of S(t) used throughoutb the proof.

We would like to stress that although the estimates presented here are classical, one could alternatively view them as a manifestation of the fact that it is possible to decompose any bounded function into a structured and a random-looking part. In the case of the set of squares we can be very explicit about the structure we obtain.

We start off by considering simple weighted exponential sum estimates for the squares.

Lemma A.1. Let θ belong to the interval I(a/q, η). Then we have the bound

|FS(θ)|

√logq

√q |FS(η)|+p

qlogq(1 +|η|N).

Proof. Consider the truncated version FS(θ, m) = P

x≤m2xe(x2θ)/√

N1 of FS, as well as the Gauss sum B(a/q, m) =P

x≤me(x2a/q). Ifm ≤q, we haveB(a/q, m)

√qlogq. Using Abel’s Inequality, which says that ifg is a monotone function, then

|P

x≤mg(x)f(x)|is bounded above by supx≤m|g(x)|supj≤m|P

x≤jf(x)|, we conclude that FS(a/q, m) mp

qlogq/N. It follows that FS(a/q) √

qlogq. In the case wherem > q, we findFS(a/q, m) = B(a/q, q)m2/(q√

N) +O(mp

qlogq/N) by split-ting into segments of length q, and so FS(a/q) = B(a/q, q)√

N /q + O(√

qlogq).

Now let θ = a/q+η with (a, q) = 1. By partial summation, we obtain FS(θ, m)− B(a/q, q)FS(η, m)/q=O(mp

qlogq/N(1+|η|m2)), whence the final estimateFS(θ) = B(a/q, q)FS(η)/q+O(√

qlogq(1 +|η|N)).

For small values ofη, we can give a fairly good estimate for FS(η). Note that without weighting the exponential sum, we would have a bound of σ−1|h|−1/2 here, which is not good enough for the purposes of this paper.

Lemma A.2. Let 101 < h=ηN ≤H =N1/8. Then we obtain the estimate

|FS(η)| σ−1

|h|.

Proof. Let us split the range of summation for FS into intervals Rij ={x:x2 ∈[N(i+j/H)/h, N(i+ (j+ 1)/H)/h)}.

Now break up the sum

FS(h/N) =

bh/2c−1

X

i=1 H

X

j=0

X

x∈Rij

2xe(x2h/N)/σ+O(σ−1/|h|).

On Rij, x2h/N is equal to an integer plus a small remainder of at most H−1, so the sum becomes

h/2

X

i=1 T

X

j=0

e(j/H)σ X

x∈Rij

2x+ X

x2≤N1

2x/(Hσ−1).

It is easily shown thatP

x∈Rij2x=N/(Hh) +O(σ−1), and hence the sum is bounded by O(hH+σ−1/H)

We next describe the behaviour of the weighted squares on what we called the major arcs.

Lemma A.3. For t ∈I(a/q,(qQ)−1) with q ≤R, we have the major arcs estimate

|FS(t/N)| σ−1

3

q.

Proof. IfqK, thenh >1/10 and putting together the previous two lemmas yields

|FS(t/N)| = p

logq/q/σ|h|+O(√

qlogqN/(qQ)). The first term clearly dominates and thus, if q≤R, we have FS(t/N)σ−1q−1/3.

We also need to investigate the behaviour on the minor arcs in more detail, which is done in the following lemma.

Lemma A.4. For t ∈ I(a/q,(qQ)−1) with R < q ≤ Q, we have the minor arcs estimate

|FS(t/N)| σ−1 pK/L.

Proof. If q ranges between R and N1/8, the result follows from the methods used above. For very large q, that is for q > N1/8, it follows from Weyl’s Inequality that

|FS(t/N)| √

NlogN(q−1/2 +p

Q/N), which is clearly bounded above by √ QL provided that q K.

Finally, we need the following variant of Hua’s Lemma, which is a classical ingredient in the solution of Waring’s problem by Hardy and Littlewood.

Lemma A.5.

N

X

t=1

|FS(t/N)|6 σ6.

We omit the proof but point out that the lemma corresponds to (a weighted version of) the well-known fact that the number of representations of an integernas the sum of six squares is asymptotic to n2.

Bibliography

[AS00] N. Alon and J. Spencer. The probabilistic method. Wiley, 2000.

[Beh46] F.A. Behrend. On sets of integers which contain no three elements in arithmetic progression. Proc. Nat. Acad. Sci., 23:331–332, 1946.

[Ber41] A. C. Berry. The accuracy of the Gaussian approximation to the sum of independent variates. Trans. Amer. Math. Soc., 49:122–136, 1941.

[Ber45] H. Bergstrom. On the central limit theorem in the case Rk,k > 1. Skand.

Aktuarietidskr., 2(3):106–127, 1945.

[BL96] V. Bergelson and A. Leibman. Polynomial extensions of Van der Waer-den’s and Szemer´edi’s theorems. J. Amer. Math. Soc., 9:725–753, 1996.

[Bou06] J. Bourgain. Roth’s theorem on progressions revisited. Preprint, 2006.

[BPPS94] A. Balog, J. Pelik´an, J. Pintz, and E. Szemer´edi. Difference sets without κth powers. Acta Math. Hungar., 65(2):165–187, 1994.

[CCS05] P. Cameron, J. Cilleruelo, and O. Serra. On monochromatic solutions of equations in groups. Preprint, 2005.

[CFS82] I. P. Cornfeld, S. V. Fomin, and Ya. G. Sina˘ı. Ergodic theory, volume 245 of Grundlehren der Mathematischen Wissenschaften [Fundamental Prin-ciples of Mathematical Sciences]. Springer-Verlag, New York, 1982. Trans-lated from the Russian by A. B. Sosinski˘ı.

[CG90] F. R. K. Chung and R. L. Graham. Quasi-random hypergraphs. Random Structures Algorithms, 1(1):105–124, 1990.

[CL84] J.-P. Conze and E. Lesigne. Th´eor`emes ergodiques pour des mesures di-agonales. Bull. Soc. Math. France, 112:143–175, 1984.

Bibliography

[CL87] J.-P. Conze and E. Lesigne. Sur un th´eor`eme ergodique pour des mesures diagonales. Publications de l’Institut de Recherche de Math´ematiques de Rennes, Probabilit´es, 1987.

[CL88] J.-P. Conze and E. Lesigne. Sur un th´eor`eme ergodique pour des mesures diagonales. C. R. Acad. Sci. Paris, S´erie I, 306:491–493, 1988.

[Dat03] B.A. Datskovsky. On the number of monochromatic Schur triples. Ad-vances in Applied Mathematics, 31:193–198, 2003.

[DT97] M. Drmota and R.F. Tichy. Sequences, Discrepancies and Applications.

Springer, 1997.

[Ess45] C.-G. Esseen. Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law. Acta Math., 77:1–125, 1945.

[Fur77] H. Furstenberg. Ergodic behavior of diagonal measures and a theorem of Szemer´edi on arithmetic progressions. J. Analyse Math., 31:204–256, 1977.

[FW96] H. Furstenberg and B. Weiss. A mean ergodic theorem for (1/N)PN

n=1f(Tnx)g(Tn2x). In Convergence in ergodic theory and prob-ability (Columbus, OH, 1993), volume 5 of Ohio State Univ. Math. Res.

Inst. Publ., pages 193–227. de Gruyter, Berlin, 1996.

[Gir79] G. Giraud. Sur le probl`eme de Goodman pour les quadrangles et la majo-ration des nombres de Ramsey. J. Combin. Theory Ser. B, 27(3):237–253, 1979.

[Goo59] A.W. Goodman. On sets of acquaintances and strangers at any party.

Amer. Math. Monthly, 66:778–783, 1959.

[Gow98] W.T. Gowers. A new proof of Szemer´edi’s theorem for progressions of length four. Geom. Funct. Anal., 8(3):529–551, 1998.

[Gow01] W.T. Gowers. A new proof of Szemer´edi’s theorem. Geom. Funct. Anal., 11:465–588, 2001.

[Gow06a] W. T. Gowers. Quasirandomness, counting and regularity for 3-uniform hypergraphs. Combin. Probab. Comput., 15(1-2):143–184, 2006.

[Gow06b] W.T. Gowers. Two examples in additive combinatorics. Unpublished, 2006.

[GR05] B.J. Green and I. Ruzsa. Sum-free sets in abelian groups. Israel J. Math., 147:157–189, 2005.

[Gre02] B.J. Green. On arithmetic structure in dense sets of integers. Duke Math.

Journal, 114:215–238, 2002.

Bibliography

[Gre03] B.J. Green. Some constructions in the inverse spectral theory of cyclic groups. Combin. Probab. Comput., 12(2):127–138, 2003.

[Gre05a] B.J. Green. Finite field models in additive combinatorics. In Surveys in combinatorics 2005, volume 327 of London Math. Soc. Lecture Note Ser., pages 1–27. Cambridge Univ. Press, Cambridge, 2005.

[Gre05b] B.J. Green. Montreal lecture notes on quadratic Fourier analysis. Available at arXiv:math.CA/0604089, 2005.

[GT04] B.J. Green and T. Tao. There are arbitrarily long arithmetic progressions in the primes. Available at arXiv:math.NT/0404188, 2004.

[GT05a] B.J. Green and T. Tao. An inverse theorem for the Gowers U3-norm. To appear. Available at arXiv:math.NT/0503014, 2005.

[GT05b] B.J. Green and T. Tao. New bounds for Szemer´edi’s theorem, I: Pro-gressions of length 4 in finite field geometries. Submitted. Available at arXiv:math.CO/0509560, 2005.

[GT06a] B.J. Green and T. Tao. Linear equations in primes. Submitted. Available at arXiv:math.NT/0606088, 2006.

[GT06b] B.J. Green and T. Tao. New bounds for Szemer´edi’s theorem, II: A new bound for r4(N). Submitted. Available at arXiv:math.NT/0610604, 2006.

[GT06c] B.J. Green and T. Tao. Quadratic uniformity of the M¨obius function.

Available at arXiv:math.NT/0606087, 2006.

[GW07a] W.T. Gowers and J. Wolf. Decompositions into polynomial phase func-tions. In preparation, 2007.

[GW07b] W.T. Gowers and J. Wolf. The true complexity of a system of linear equations. Available at arXiv:math.NT/0711.0185, 2007.

[Har66] L.H. Harper. Optimal numberings and isoperimetric problems on graphs.

J. Combinatorial Theory, 1:385–393, 1966.

[HB87] D.R. Heath-Brown. Integer sets containing no arithmetic progressions. J.

London Math. Soc. (2), 35:385–394, 1987.

[HK01] B. Host and B. Kra. Convergence of Conze-Lesigne averages. Erg. Th. &

Dyn. Sys., 21:493–509, 2001.

[HK04] B. Host and B. Kra. Averaging along cubes. In Dynamical systems and related topics. Cambridge University Press, Cambridge, 2004.

[HK05] B. Host and B. Kra. Nonconventional ergodic averages and nilmanifolds.

Annals of Math., 161(1):397–488, 2005.

Bibliography

[J LR00] S. Janson, T. Luczak, and A. Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.

[JˇST96] C. Jagger, P. ˇSˇtov´ıˇcek, and A. Thomason. Multiplicities of subgraphs.

Combinatorica, 16(1):123–141, 1996.

[Kra06] B. Kra. Ergodic methods in additive combinatorics. Available at arXiv:math.DS/0608105, 2006.

[Led01] M. Ledoux. The concentration of measure phenomenon. AMS Mathemat-ical Surveys and Monographs, 2001.

[Lei04] A. Leibman. Convergence of multiple ergodic averages along poly-nomials of several variables. Available at http://www.math.ohio-state.edu/∼Leibman/preprints, 2004.

[Lei07] A. Leibman. Orbit of the diagonal of a power of a nilmanifold. Available at http://www.math.ohio-state.edu/∼Leibman/preprints, 2007.

[L LS01] V. Lev, T. Luczak, and T. Schoen. Sum-free sets in abelian groups. Israel J. Math., 125:347–367, 2001.

[LOS82] J.C. Lagarias, A.M. Odlyzko, and J.B. Shearer. On the density of se-quences of integers the sum of no two of which is a square. I. Arithmetic progressions. J. Comb. Theory, Series A., 33:167–185, 1982.

[Luc07] J. Lucier. Difference sets and shifted primes. Preprint. Available at arxiv:math.NT/0705.3749, 2007.

[McD89] C. McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc.

Lecture Note Ser., pages 148–188. Cambridge Univ. Press, Cambridge, 1989.

[Mes95] R. Meshulam. On subsets of finite abelian groups with no 3-term arith-metic progressions. J. Combin. Theory Ser. A, 71(1):168–172, 1995.

[NP73] H. Niederreiter and W. Philipp. Berry-Esseen bounds and a theorem of Erd˝os and Tur´an on uniform distribution mod 1. Duke Math. J., 40(3):633–649, 1973.

[NRS06] B. Nagle, V. R¨odl, and M. Schacht. The counting lemma for regular k-uniform hypergraphs. Random Structures Algorithms, 28(2):113–179, 2006.

[Pol46] G. Polya. Remarks on computing the probability integral in one and two dimensions. Proc. Berkeley Symp., pages 63–78, 1946.

Bibliography

[PSS88] J. Pintz, W.L. Steiger, and E. Szemer´edi. On sets of natural numbers whose difference set contains no squares. J. London Math. Soc. (2), 37:219–231, 1988.

[Rot53] K.F. Roth. On certain sets of integers. J. London Math. Soc., 28:104–109, 1953.

[RS04] V. R¨odl and J. Skokan. Regularity lemma for k-uniform hypergraphs.

Random Structures Algorithms, 25(1):1–42, 2004.

[RS07] I.Z. Ruzsa and T. Sanders. Difference sets and the primes. Preprint.

Available at arxiv:math.NT/, 2007.

[Rud95] D.J. Rudolph. Eigenfunctions of T×S and the Conze-Lesigne algebra. In Ergodic theory and its Connections with Harmonic Analysis, pages 369–

432. Cambridge Univ. Press, New York, 1995.

[Ruz84] I.Z. Ruzsa. Difference sets without squares. Periodica Math. Hungar., 15:205–209, 1984.

[Ruz87] I.Z. Ruzsa. Essential components. Proc. London Math. Soc. (3), 54(1):38–

56, 1987.

[Ruz91] I.Z. Ruzsa. Arithmetic progressions in sumsets. Acta Arith., 2:191–202, 1991.

[Sad66] S.M. Sadikova. Two-dimensional analogues of an inequality of Esseen with applications to the Central Limit Theorem. Theory of Probability and Its Applications, 11:325–335, 1966.

[S´ar78a] A. S´ark¨ozy. On difference sets of sequences of integers I. Acta Math. Acad.

Sci. Hungar., 31:125–149, 1978.

[S´ar78b] A. S´ark¨ozy. On difference sets of sequences of integers II. Ann. Univ. Sci.

Budapest, 21:45–53, 1978.

[S´ar78c] A. S´ark¨ozy. On difference sets of sequences of integers III. Acta Math.

Acad. Sci. Hungar., 31:355–386, 1978.

[Shi84] A.N. Shiryayev. Probability. Springer, 1984.

[Sze75] E. Szemer´edi. On integer sets containing no k elements in arithmetic progression. Acta Arith., 27:199–245, 1975.

[Sze90] E. Szemer´edi. Integer sets containing no arithmetic progressions. Acta Math. Hungar., 56(1-2):155–158, 1990.

[Tao05] T. Tao. The dichotomy between structure and randomness, arithmetic progressions, and the primes. Available at arXiv:math.NT/0512114, 2005.