Rado’s criterion over squares and higher powers. (English) Zbl 1497.11028
Schur’s theorem from 1916 states that in any finite colouring of the positive integers, there exists a monochromatic solution to the equation \(x + y = z\). Erdős and Graham conjectured that the same is true for the Pythagorean equation \(x^2+y^2=z^2\). This questions is notoriously difficult but the authors manage to obtain a corresponding result with five variables, i.e. their Theorem 1.1 states that in any finite colouring of the positive integers, there exists a monochromatic solution to \(x_1^2 + x_2^2 + x_3^2 + x_4^2 = x_5^2\).
This is a consequence of a much more general result concerning partition regularity of polynomials. Given a polynomial \(P \in \mathbb{Z}[x_1, \dotsc, x_s]\) and a set \(S\) we call the equation \(P(x) = 0\) non-trivially partition regular if, in any finite colouring of \(S\), there exists a monochromatic solution \(x \in S^s\) with each variable distinct.
Rado’s criterion tells that, for \(s \geq 3\) and non-zero integers \(c_1, \dotsc, c_s\), the equation \(\sum_{i= 1}^s c_i x_i = 0\) is non-trivially partition regular over positive integers if and only if there exists a non-empty subset \(I \subseteq \{1, \dotsc, s\}\) such that \(\sum_{i \in I} c_i = 0\).
The authors make a vast generalization of this to \(k\)th powers, once the number of variables is sufficiently large. Theorem 1.3 states that, for each \(k \geq 2\), there exists \(s_0(k) \in \mathbb{N}\) such that for \(s \geq s_0(k)\) and non-zero integers \(c_1, \dotsc, c_s\), the equation \[ \sum_{i=1}^s c_i x_i^k = 0 \] is non-trivially partition regular over the positive integers if and only if there exists a non-empty subset \(I \subseteq \{1, \dotsc, s\}\) such that \(\sum_{i \in I} c_i = 0\). Furthermore one can take \(s_0(2) = 5, s_0(3) = 8\) and \[ s_0(k) = k(\log k + \log \log k +2 + O(\log \log k/\log k)). \]
The authors also provide results concerning partition-regularity of linear equations over shifted squares and smooth numbers.
The proof strategy is explained well in Section 2 of the paper – the authors need to use variety of methods such as the transference principle and a density increment argument.
This is a consequence of a much more general result concerning partition regularity of polynomials. Given a polynomial \(P \in \mathbb{Z}[x_1, \dotsc, x_s]\) and a set \(S\) we call the equation \(P(x) = 0\) non-trivially partition regular if, in any finite colouring of \(S\), there exists a monochromatic solution \(x \in S^s\) with each variable distinct.
Rado’s criterion tells that, for \(s \geq 3\) and non-zero integers \(c_1, \dotsc, c_s\), the equation \(\sum_{i= 1}^s c_i x_i = 0\) is non-trivially partition regular over positive integers if and only if there exists a non-empty subset \(I \subseteq \{1, \dotsc, s\}\) such that \(\sum_{i \in I} c_i = 0\).
The authors make a vast generalization of this to \(k\)th powers, once the number of variables is sufficiently large. Theorem 1.3 states that, for each \(k \geq 2\), there exists \(s_0(k) \in \mathbb{N}\) such that for \(s \geq s_0(k)\) and non-zero integers \(c_1, \dotsc, c_s\), the equation \[ \sum_{i=1}^s c_i x_i^k = 0 \] is non-trivially partition regular over the positive integers if and only if there exists a non-empty subset \(I \subseteq \{1, \dotsc, s\}\) such that \(\sum_{i \in I} c_i = 0\). Furthermore one can take \(s_0(2) = 5, s_0(3) = 8\) and \[ s_0(k) = k(\log k + \log \log k +2 + O(\log \log k/\log k)). \]
The authors also provide results concerning partition-regularity of linear equations over shifted squares and smooth numbers.
The proof strategy is explained well in Section 2 of the paper – the authors need to use variety of methods such as the transference principle and a density increment argument.
Reviewer: Kaisa Matomäki (Turku)
MSC:
| 11B30 | Arithmetic combinatorics; higher degree uniformity |
| 11D72 | Diophantine equations in many variables |
References:
| [1] | Baker, R. C.: Diophantine Inequalities. London Math. Soc. Monographs (N.S.) 1, Clarendon Press, Oxford (1986)Zbl 0592.10029 MR 0865981 · Zbl 0592.10029 |
| [2] | Bergelson, V.: Ergodic Ramsey theory—an update. In: Ergodic Theory ofZdActions (Warwick, 1993-1994), London Math. Soc. Lecture Note Ser. 228, Cambridge Univ. Press, Cambridge, 1-61 (1996)Zbl 0846.05095 MR 1411215 · Zbl 0846.05095 |
| [3] | Bergelson, V.: Mutually enriching connections between ergodic theory and combinatorics—lecture 7. CIRM lecture,https://bit.ly/2GNaL7d |
| [4] | Bergelson, V., Glasscock, D.: Interplay between notions of additive and multiplicative largeness.arXiv:1610.09771(2016) · Zbl 1433.05313 |
| [5] | Bergelson, V., Leibman, A.: Polynomial extensions of van der Waerden’s and Szemer´edi’s theorems. J. Amer. Math. Soc.9, 725-753 (1996)Zbl 0870.11015 MR 1325795 · Zbl 0870.11015 |
| [6] | Birch, B. J.: Forms in many variables. Proc. Roy. Soc. Ser. A265, 245-263 (1961/62) Zbl 0103.03102 MR 0150129 · Zbl 0103.03102 |
| [7] | Bourgain, J.: On3(p)-subsets of squares. Israel J. Math.67, 291-311 (1989) Zbl 0692.43005 MR 1029904 · Zbl 0692.43005 |
| [8] | Bourgain, J., Demeter, C., Guth, L.: Proof of the main conjecture in Vinogradov’s mean value theorem for degrees higher than three. Ann. of Math.184, 633-682 (2016) Zbl 1408.11083 MR 3548534 · Zbl 1408.11083 |
| [9] | Browning, T. D., Prendiville, S.: A transference approach to a Roth-type theorem in the squares. Int. Math. Res. Notices2017, 2219-2248Zbl 1405.11131 MR 3658196 · Zbl 1405.11131 |
| [10] | Chapman, J.: Partition regularity and multiplicatively syndetic sets. Acta Arith.196, 109-138 (2020)Zbl 07301078 MR 4146371 · Zbl 1464.05347 |
| [11] | Chow, S.: Waring’s problem with shifts. Mathematika62, 13-46 (2016) Zbl 1396.11058 MR 3430375 · Zbl 1396.11058 |
| [12] | Chow, S.: Roth-Waring-Goldbach. Int. Math. Res. Notices2018, 2341-2374 Zbl 1441.11022 MR 3801486 · Zbl 1441.11022 |
| [13] | Cook, R.: Simultaneous quadratic equations. J. London Math. Soc.4, 319-326 (1971) Zbl 0224.10021 MR 0289406 · Zbl 0224.10021 |
| [14] | Croot, E., Ruzsa, I. Z., Schoen, T.: Arithmetic progressions in sparse sumsets. In: Combinatorial Number Theory, de Gruyter, Berlin, 157-164 (2007)Zbl 1178.11011 MR 2337044 · Zbl 1178.11011 |
| [15] | Csikv´ari, P., Gyarmati, K., S´ark¨ozy, A.: Density and Ramsey type results on algebraic equations with restricted solution sets. Combinatorica32, 425-449 (2012) Zbl 1286.11026 MR 2965285 · Zbl 1286.11026 |
| [16] | Cwalina, K., Schoen, T.: Tight bounds on additive Ramsey-type numbers. J. London Math. Soc.96, 601-620 (2017)Zbl 1431.11024 MR 3742435 · Zbl 1431.11024 |
| [17] | Davenport, H.: Analytic Methods for Diophantine Equations and Diophantine Inequalities. 2nd ed., Cambridge Univ. Press, Cambridge (2005)Zbl 1125.11018 MR 2152164 · Zbl 1125.11018 |
| [18] | Deuber, W.: Partitionen und lineare Gleichungssysteme. Math. Z.133, 109-123 (1973) Zbl 0254.05011 MR 0325406 · Zbl 0254.05011 |
| [19] | Di Nasso, M., Luperi Baglini, L.: Ramsey properties of nonlinear Diophantine equations. Adv. Math.324, 84-117 (2018)Zbl 1376.05159 MR 3733882 · Zbl 1376.05159 |
| [20] | Drappeau, S., Shao, X.: Weyl sums, mean value estimates, and Waring’s problem with friable numbers. Acta Arith.176, 249-299 (2016)Zbl 1385.11052 MR 3580114 · Zbl 1385.11052 |
| [21] | Frankl, P., Graham, R. L., R¨odl, V.: Quantitative theorems for regular systems of equations. J. Combin. Theory Ser. A47, 246-261 (1988)Zbl 0654.05002 MR 0930955 · Zbl 0654.05002 |
| [22] | Frantzikinakis, N., Host, B.: Higher order Fourier analysis of multiplicative functions and applications. J. Amer. Math. Soc.30, 67-157 (2017)Zbl 1355.11094 MR 3556289 · Zbl 1355.11094 |
| [23] | Furstenberg, H., Ergodic behavior of diagonal measures and a theorem of Szemer´edi on arithmetic progressions. J. Anal. Math.31, 204-256 (1977)Zbl 0347.28016 MR 0498471 · Zbl 0347.28016 |
| [24] | Graham, R.: Some of my favorite problems in Ramsey theory. In: Combinatorial Number Theory, de Gruyter, Berlin, 229-236 (2007)Zbl 1124.05087 MR 2337049 · Zbl 1124.05087 |
| [25] | Graham, R.: Old and new problems in Ramsey theory. In: Horizons of Combinatorics, Bolyai Soc. Math. Stud. 17, Springer, Berlin, 105-118 (2008)Zbl 1178.05094 MR 2432529 · Zbl 1178.05094 |
| [26] | Graham, R., Rothschild, B., Spencer, J. H.: Ramsey Theory. Wiley (1990) Zbl 0705.05061 MR 1044995 · Zbl 0705.05061 |
| [27] | Granville, A.: Smooth numbers: computational number theory and beyond. In: Algorithmic Number Theory: Lattices. Number Fields, Curves and Cryptography, Math. Sci. Res. Inst. Publ. 44, Cambridge Univ. Press, Cambridge, 267-323 (2008) Zbl 1230.11157 MR 2467549 · Zbl 1230.11157 |
| [28] | Green, B.: On arithmetic structures in dense sets of integers. Duke Math. J.114, 215- 238 (2002)Zbl 1020.11010 MR 1920188 · Zbl 1020.11010 |
| [29] | Green, B.: Roth’s theorem in the primes. Ann. of Math.161, 1609-1636 (2005) Zbl 1160.11307 MR 2180408 · Zbl 1160.11307 |
| [30] | Green, B., Lindqvist, S.: Monochromatic solutions tox+y=z2. Canad. J. Math.71, 579-605 (2019)Zbl 1439.11076 MR 3952491 · Zbl 1439.11076 |
| [31] | Green, B., Sanders, T.: Monochromatic sums and products. Discrete Anal.2016, art. 5, 43 pp.Zbl 1400.11024 MR 3533304 · Zbl 1400.11024 |
| [32] | Green, B., Tao, T.: Linear equations in primes. Ann. of Math.171, 1753-1850 (2010) Zbl 1242.11071 MR 2680398 · Zbl 1242.11071 |
| [33] | Green, B., Tao, T.: An arithmetic regularity lemma, an associated counting lemma, and applications. In: An Irregular Mind, Bolyai Soc. Math. Stud. 21, J´anos Bolyai Math. Soc., 261-334 (2010)Zbl 1222.11015 MR 2815606 · Zbl 1222.11015 |
| [34] | Harper, A.: Minor arcs, mean values, and restriction theory for exponential sums over smooth numbers. Compos. Math.152, 1121-1158 (2016)Zbl 1362.11077 MR 3518307 · Zbl 1362.11077 |
| [35] | Heilbronn, H.: On the distribution of the sequencen2θ (mod 1). Quart. J. Math.19, 249-256 (1948)Zbl 0031.20502 MR 0027294 · Zbl 0031.20502 |
| [36] | Heule, M., Kullmann, O., Marek, V.: Solving and verifying the Boolean Pythagorean triples problem via cube-and-conquer. In: Theory and Applications of Satisfiability Testing—SAT 2016 (Bordeaux, 2016), Springer, 228-245 (2016)Zbl 1403.68226 MR 3534782 · Zbl 1403.68226 |
| [37] | Hindman, N.: Partitions and sums and products of integers. Trans. Amer. Math. Soc. 247, 227-245 (1979)Zbl 0401.05012 MR 0517693 · Zbl 0401.05012 |
| [38] | Hua, L.-K.: Additive Theory of Prime Numbers. Transl. Math. Monogr. 13, Amer. Math. Soc., Providence (1965)Zbl 0192.39304 MR 0194404 · Zbl 0192.39304 |
| [39] | Keil, E.: On a diagonal quadric in dense variables. Glasgow Math. J.56, 601-628 (2014)Zbl 1364.11030 MR 3250267 · Zbl 1364.11030 |
| [40] | Khalfalah, A., Szemer´edi, E.: On the number of monochromatic solutions ofx+y= z2. Combin. Probab. Comput.15, 213-227 (2006)Zbl 1093.11017 MR 2195583 · Zbl 1093.11017 |
| [41] | Kloosterman, H. D.: On the representation of numbers in the formax2+by2+cz2+ dt2. Acta Math.49, 407-464 (1927)JFM 53.0155.01 MR 1555249 · JFM 53.0155.01 |
| [42] | Lamb, E.: Maths proof smashes size record. Nature534, 17-18 (2016) |
| [43] | Lˆe, T. H.: Partition regularity and the primes. C. R. Math. Acad. Sci. Paris350, 439- 441 (2012)Zbl 1275.11023 MR 2929045 · Zbl 1275.11023 |
| [44] | Lefmann, H.: On partition regular systems of equations. J. Combin. Theory Ser. A58, 35-53 (1991)Zbl 0746.05076 MR 1119700 · Zbl 0746.05076 |
| [45] | Li, H., Pan, H.: A Schur-type addition theorem for primes. J. Number Theory132, 117-126 (2012)Zbl 1276.11016 MR 2843302 · Zbl 1276.11016 |
| [46] | Moreira, J.: Monochromatic sums and products inN. Ann. of Math.185, 1069-1090 (2017)Zbl 1430.05128 MR 3664819 · Zbl 1430.05128 |
| [47] | Noel, J., Scott, A., Sudakov, B.: Supersaturation in posets and applications involving the container method. J. Combin. Theory Ser. A154, 247-284 (2018)Zbl 1373.05197 MR 3718067 · Zbl 1373.05197 |
| [48] | Pach, P.: Monochromatic solutions tox+y=z2in the interval[N, cN4]. Bull. London Math. Soc.50, 1113-1116 (2018)Zbl 1439.11077 MR 3891947 · Zbl 1439.11077 |
| [49] | Prendiville, S.: Four variants of the Fourier-analytic transference principle. Online J. Anal. Combin.12, art. 5, 25 pp. (2017)Zbl 1377.42003 MR 3680137 · Zbl 1377.42003 |
| [50] | Prendiville, S.: Quantitative bounds in the polynomial Szemer´edi theorem: the homogeneous case. Discrete Anal.2017, art. 5, 34 pp.Zbl 1404.11114 MR 3631611 · Zbl 1404.11114 |
| [51] | Rado, R.: Studien zur Kombinatorik. Math. Z.36, 424-470 (1933)Zbl 0006.14603 MR 1545354 · Zbl 0006.14603 |
| [52] | Rogovskaya, N. N.: An asymptotic formula for the number of solutions of a system of equations. In: Diophantine Approximations, Part II, Moskov. Gos. Univ., Moscow, 78-84 (1986) (in Russian)Zbl 0648.10010 MR 0936656 · Zbl 0648.10010 |
| [53] | Roth, K. F.: On certain sets of integers. J. London Math. Soc.28, 104-109 (1953) Zbl 0050.04002 MR 0051853 · Zbl 0050.04002 |
| [54] | Schur, I.: ¨Uber die Kongruenzxm+ym≡zm(modp). Jahresber. Deutsch. Math.Verein.25, 114-117 (1916)JFM 46.0193.02 · JFM 46.0193.02 |
| [55] | Varnavides, P.: On certain sets of positive density. J. London Math. Soc.34, 358-360 (1959)Zbl 0088.25702 MR 0106865 · Zbl 0088.25702 |
| [56] | Vaughan, R. C.: On Waring’s problem for cubes. J. Reine Angew. Math.365, 122-170 (1986)Zbl 0574.10046 MR 0826156 · Zbl 0574.10046 |
| [57] | Vaughan, R. C.: A new iterative method in Waring’s problem. Acta Math.162, 1-71 (1989)Zbl 0665.10033 MR 0981199 · Zbl 0665.10033 |
| [58] | Vaughan, R. C.: The Hardy-Littlewood Method. 2nd ed., Cambridge Tracts in Math. 125, Cambridge Univ. Press, Cambridge (1997)Zbl 0868.11046 MR 1435742 |
| [59] | Vaughan, R. C., Wooley, T. D.: On Waring’s problem: some refinements. Proc. London Math. Soc. (3)63, 35-68 (1991)Zbl 0736.11058 MR 1105718 · Zbl 0736.11058 |
| [60] | Walters, M.: Combinatorial proofs of the polynomial van der Waerden theorem and the polynomial Hales-Jewett theorem. J. London Math. Soc.61, 1-12 (2000) Zbl 0948.05056 MR 1745405 · Zbl 0948.05056 |
| [61] | Wooley, T. D.: Large improvements in Waring’s problem. Ann. of Math. (2)135, 131- 164 (1992)Zbl 0754.11026 MR 1147960 · Zbl 0754.11026 |
| [62] | Wooley, T. D.: Breaking classical convexity in Waring’s problem: sums of cubes and quasi-diagonal behaviour. Invent. Math.122, 421-451 (1995)Zbl 0851.11055 MR 1359599 · Zbl 0851.11055 |
| [63] | Wooley, T. D.: The asymptotic formula in Waring’s problem. Int. Math. Res. Notices 2012, 1485-1504Zbl 1267.11104 MR 3455880 · Zbl 1267.11104 |
| [64] | Zhao, L.: On translation invariant quadratic forms in dense sets. Int. Math. Res · Zbl 1471.11029 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
