×

The sharp threshold for making squares. (English) Zbl 1430.11165

Summary: Consider a random sequence of \(N\) integers, each chosen uniformly and independently from the set \(\{1,\dots,x\}\). Motivated by applications to factorization algorithms such as Dixon’s algorithm, the quadratic sieve, and the number field sieve, Pomerance in 1994 posed the following problem: how large should \(N\) be so that, with high probability, this sequence contains a subsequence, the product of whose elements is a perfect square? Pomerance determined asymptotically the logarithm of the threshold for this event and conjectured that it in fact exhibits a sharp threshold in \(N\). More recently, Croot, Granville, Pemantle and Tetali [E. Croot et al., Ann. Math. (2) 175, No. 3, 1507–1550 (2012; Zbl 1321.11122)] determined the threshold up to a factor of \(4/\pi +o(1)\) as \(x\to\infty\) and made a conjecture regarding the location of the sharp threshold.
In this paper we prove both of these conjectures by determining the sharp threshold for making squares. Our proof combines techniques from combinatorics, probability and analytic number theory; in particular, we use the so-called method of self-correcting martingales in order to control the size of the 2-core of the random hypergraph that encodes the prime factors of our random numbers. Our method also gives a new (and completely different) proof of the upper bound in the main theorem of Croot, Granville, Pemantle and Tetali.

MSC:

11Y05 Factorization
60C05 Combinatorial probability

Citations:

Zbl 1321.11122

References:

[1] Azuma, Kazuoki, Weighted sums of certain dependent random variables, T\^ohoku Math. J. (2). The Tohoku Mathematical Journal. Second Series, 19, 357-367, (1967) · Zbl 0178.21103 · doi:10.2748/tmj/1178243286
[2] Balister, P.; Bollob\'as, P.; Lee, J.; Morris, R., On the 2-core of a random set of numbers
[3] Balogh, J\'ozsef; Bollob\'as, B\'ela; Duminil-Copin, Hugo; Morris, Robert, The sharp threshold for bootstrap percolation in all dimensions, Trans. Amer. Math. Soc.. Transactions of the American Mathematical Society, 364, 2667-2701, (2012) · Zbl 1238.60108 · doi:10.1090/S0002-9947-2011-05552-2
[4] Bohman, Tom; Keevash, Peter, Dynamic concentration of the triangle-free process. The {S}eventh {E}uropean {C}onference on {C}ombinatorics, {G}raph {T}heory and {A}pplications, CRM Series, 16, 489-495, (2013) · Zbl 1291.05183 · doi:10.1007/978-88-7642-475-5_78
[5] Bohman, Tom; Frieze, Alan; Lubetzky, Eyal, A note on the random greedy triangle-packing algorithm, J. Comb.. Journal of Combinatorics, 1, 477-488, (2010) · Zbl 1244.05213 · doi:10.4310/JOC.2010.v1.n4.a5
[6] Bohman, Tom; Frieze, Alan; Lubetzky, Eyal, Random triangle removal, Adv. Math.. Advances in Mathematics, 280, 379-438, (2015) · Zbl 1312.05123 · doi:10.1016/j.aim.2015.04.015
[7] Bohman, Tom; Picollelli, Michael, S{IR} epidemics on random graphs with a fixed degree sequence, Random Structures Algorithms. Random Structures & Algorithms, 41, 179-214, (2012) · Zbl 1401.92176 · doi:10.1002/rsa.20401
[8] Bollob\'as, B\'ela, Random Graphs, Cambridge Stud. Adv. Math., 73, xviii+498 pp., (2001) · Zbl 0979.05003 · doi:10.1017/CBO9780511814068
[9] de Bruijn, N. G., On the number of positive integers {\(\leq x\)} and free of prime factors {\(>y\)}, Nederl. Acad. Wetensch. Proc. Ser. A., 54, 50-60, (1951) · Zbl 0042.04204 · doi:10.1016/S1385-7258(51)50008-2
[10] de Bruijn, N. G., On the number of positive integers {\(\leq x\)} and free prime factors {\(>y\)}. {II}, Nederl. Akad. Wetensch. Proc. Ser. A., 69, 239-247, (1966) · Zbl 0139.27203
[11] Canfield, E. R.; Erd\H{o}s, Paul; Pomerance, Carl, On a problem of {O}ppenheim concerning ““‘factorisatio numerorum””’, J. Number Theory. Journal of Number Theory, 17, 1-28, (1983) · Zbl 0513.10043 · doi:10.1016/0022-314X(83)90002-1
[12] Chernoff, Herman, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics. Annals of Mathematical Statistics, 23, 493-507, (1952) · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[13] Croot, Ernie; Granville, Andrew; Pemantle, Robin; Tetali, Prasad, On sharp transitions in making squares, Ann. of Math. (2). Annals of Mathematics. Second Series, 175, 1507-1550, (2012) · Zbl 1321.11122 · doi:10.4007/annals.2012.175.3.10
[14] Dickman, K., On the frequency of numbers containing prime factors of a certain relative magnitude, Ark. Mat. Astron. Fys., 22, 1-14, (1930) · JFM 56.0178.04
[15] Dixon, John D., Asymptotically fast factorization of integers, Math. Comp.. Mathematics of Computation, 36, 255-260, (1981) · Zbl 0452.10010 · doi:10.2307/2007743
[16] Fiz Pontiveros, G.; Griffiths, S.; Morris, R., The triangle-free process and the {R}amsey numbers {\(R(3,k)\)}
[17] Hildebrand, Adolf, On the number of positive integers {\(\leq x\)} and free of prime factors {\(>y\)}, J. Number Theory. Journal of Number Theory, 22, 289-307, (1986) · Zbl 0575.10038 · doi:10.1016/0022-314X(86)90013-2
[18] Hildebrand, Adolf; Tenenbaum, G\'erald, On integers free of large prime factors, Trans. Amer. Math. Soc.. Transactions of the American Mathematical Society, 296, 265-290, (1986) · Zbl 0601.10028 · doi:10.2307/2000573
[19] Hildebrand, Adolf; Tenenbaum, G\'erald, Integers without large prime factors, J. Th\'eor. Nombres Bordeaux. Journal de Th\'eorie des Nombres de Bordeaux, 5, 411-484, (1993) · Zbl 0797.11070 · doi:10.5802/jtnb.101
[20] Hoeffding, Wassily, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc.. Journal of the American Statistical Association, 58, 13-30, (1963) · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830
[21] Janson, Svante; {\L}uczak, Tomasz; Turova, Tatyana; Vallier, Thomas, Bootstrap percolation on the random graph {\(G_{n,p}\)}, Ann. Appl. Probab.. The Annals of Applied Probability, 22, 1989-2047, (2012) · Zbl 1254.05182 · doi:10.1214/11-AAP822
[22] Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thom\'e, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alexander; Montgomery, Peter L.; Osvik, Dag Arne; te Riele, Herman; Timofeev, Andrey; Zimmermann, Paul, Factorization of a 768-bit {RSA} modulus. Advances in Cryptology—{CRYPTO} 2010, Lecture Notes in Comput. Sci., 6223, 333-350, (2010) · Zbl 1196.11167 · doi:10.1007/978-3-642-14623-7_18
[23] Le Cam, Lucien, An approximation theorem for the {P}oisson binomial distribution, Pacific J. Math.. Pacific Journal of Mathematics, 10, 1181-1197, (1960) · Zbl 0118.33601 · doi:10.2140/pjm.1960.10.1181
[24] Kurtz, Thomas G., Solutions of ordinary differential equations as limits of pure jump {M}arkov processes, J. Appl. Probability. Journal of Applied Probability, 7, 49-58, (1970) · Zbl 0191.47301 · doi:10.2307/3212147
[25] Lenstra, Jr., H. W., The number field sieve: an annotated bibliography. The Development of the Number Field Sieve, Lecture Notes in Math., 1554, 1-3, (1993) · Zbl 0806.11063 · doi:10.1007/BFb0091535
[26] McNew, Nathan, The most frequent values of the largest prime divisor function, Exp. Math.. Experimental Mathematics, 26, 210-224, (2017) · Zbl 1426.11108 · doi:10.1080/10586458.2016.1155188
[27] Pittel, Boris; Sorkin, Gregory B., The satisfiability threshold for {\(k\)}-{XORSAT}, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 25, 236-268, (2016) · Zbl 1372.68193 · doi:10.1017/S0963548315000097
[28] Pomerance, C., Analysis and comparison of some integer factoring algorithms. Computational Methods in Number Theory, {P}art {I}, Math. Centre Tracts, 154, 89-139, (1982) · Zbl 0508.10004
[29] Pomerance, Carl, The role of smooth numbers in number-theoretic algorithms. Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol.1, 2, 411-422, (1995) · Zbl 0854.11047
[30] Pomerance, Carl, A tale of two sieves, Notices Amer. Math. Soc.. Notices of the American Mathematical Society, 43, 1473-1485, (1996) · Zbl 1042.11529
[31] Pomerance, Carl, Multiplicative independence for random integers. Analytic Number Theory, {V}ol.2, Progr. Math., 139, 703-711, (1996) · Zbl 0865.11085
[32] Rankin, R. A., The difference between consecutive prime numbers, J. London Math. Soc.. The Journal of the London Mathematical Society, 11, 242-245, (1936) · JFM 64.0982.01 · doi:10.1112/jlms/s1-13.4.242
[33] Telcs, Andr\'as; Wormald, Nicholas; Zhou, Sanming, Hamiltonicity of random graphs produced by 2-processes, Random Structures Algorithms. Random Structures & Algorithms, 31, 450-481, (2007) · Zbl 1129.05026 · doi:10.1002/rsa.20133
[34] Williams, David, Probability with Martingales, Cambridge Math. Textbooks, xvi+251 pp., (1991) · Zbl 0722.60001 · doi:10.1017/CBO9780511813658
[35] Wormald, N., The differential equation method for random graph processes and greedy algorithms. Lectures on Approximation and Randomized Algorithms, 73-155, (1999) · Zbl 0943.05073
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.