Hypercontractivity for global functions and sharp thresholds

Keevash, Peter; Lifshitz, Noam; Long, Eoin; Minzer, Dor

doi:10.1090/jams/1027

Hypercontractivity for global functions and sharp thresholds
HTML articles powered by AMS MathViewer

by Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer

J. Amer. Math. Soc. 37 (2024), 245-279

DOI: https://doi.org/10.1090/jams/1027

Published electronically: July 18, 2023

HTML | PDF | Request permission

Abstract:

The classical hypercontractive inequality for the noise operator on the discrete cube plays a crucial role in many of the fundamental results in the Analysis of Boolean functions, such as the Kahn-Kalai-Linial theorem, Friedgut’s junta theorem and the invariance principle of Mossel, O’Donnell and Oleszkiewicz. In these results the cube is equipped with the uniform ($1/2$-biased) measure, but it is desirable, particularly for applications to the theory of sharp thresholds, to also obtain such results for general $p$-biased measures. However, simple examples show that when $p$ is small there is no hypercontractive inequality that is strong enough for such applications.

In this paper, we establish an effective hypercontractivity inequality for general $p$ that applies to ‘global functions’, i.e. functions that are not significantly affected by a restriction of a small set of coordinates. This class of functions appears naturally, e.g. in Bourgain’s sharp threshold theorem, which states that such functions exhibit a sharp threshold. We demonstrate the power of our tool by strengthening Bourgain’s theorem, making progress on two conjectures of Kahn and Kalai (both these conjectures were open when we arXived this paper in 2019; one of them was solved in 2022; the other is still open), and proving a $p$-biased analogue of the seminal invariance principle of Mossel, O’Donnell, and Oleszkiewicz.

In this 2023 version of our paper we will also survey many further applications of our results that have been obtained by various authors since we arXived the first version in 2019.

References

Amirali Abdullah and Suresh Venkatasubramanian, A directed isoperimetric inequality with application to Bregman near neighbor lower bounds, STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 509–517. MR 3388230
Dimitris Achlioptas and Ehud Friedgut, A sharp threshold for $k$-colorability, Random Structures Algorithms 14 (1999), no. 1, 63–70. MR 1662274, DOI 10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7
Daniel Ahlberg, Erik Broman, Simon Griffiths, and Robert Morris, Noise sensitivity in continuum percolation, Israel J. Math. 201 (2014), no. 2, 847–899. MR 3265306, DOI 10.1007/s11856-014-1038-y
Rudolf Ahlswede and Levon H. Khachatrian, The diametric theorem in Hamming spaces—optimal anticodes, Adv. in Appl. Math. 20 (1998), no. 4, 429–449. MR 1612850, DOI 10.1006/aama.1998.0588
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang, Improved bounds for the sunflower lemma, Ann. of Math. (2) 194 (2021), no. 3, 795–815. MR 4334977, DOI 10.4007/annals.2021.194.3.5
László Babai and Vera T. Sós, Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin. 6 (1985), no. 2, 101–114. MR 810691, DOI 10.1016/S0195-6698(85)80001-9
Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, and David Steurer, Playing unique games on certified small-set expanders, STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2021] ©2021, pp. 1629–1642. MR 4398946, DOI 10.1145/3406325.3451099
Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett, High dimensional expanders: eigenstripping, pseudorandomness, and unique games, Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2022, pp. 1069–1128. MR 4415084, DOI 10.1137/1.9781611977073.47
Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett, Hypercontractivity on high dimensional expanders, STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2022] ©2022, pp. 185–194. MR 4489993
William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159–182. MR 385456, DOI 10.2307/1970980
Michael Ben-Or and Nathan Linial, Collective coin flipping, Randomness and computation, vol. 5, 1990, pp. 91–115.
Itai Benjamini, Stéphane Boucheron, Gábor Lugosi, and Raphaël Rossignol, Sharp threshold for percolation on expanders, Ann. Probab. 40 (2012), no. 1, 130–145. MR 2917769, DOI 10.1214/10-AOP610
Itai Benjamini and Jérémie Brieussel, Noise sensitivity of random walks on groups, Preprint, arXiv:1901.03617, 2019.
Itai Benjamini, Gil Kalai, and Oded Schramm, Noise sensitivity of Boolean functions and applications to percolation, Inst. Hautes Études Sci. Publ. Math. 90 (1999), 5–43 (2001). MR 1813223, DOI 10.1007/BF02698830
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman, Optimal testing of Reed-Muller codes, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010, IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 488–497. MR 3025222
B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, DOI 10.1007/BF02579198
Aline Bonami, Étude des coefficients de Fourier des fonctions de $L^{p}(G)$, Ann. Inst. Fourier (Grenoble) 20 (1970), no. fasc. 2, 335–402 (1971) (French, with English summary). MR 283496, DOI 10.5802/aif.357
Christer Borell, Geometric bounds on the Ornstein-Uhlenbeck velocity process, Z. Wahrsch. Verw. Gebiete 70 (1985), no. 1, 1–13. MR 795785, DOI 10.1007/BF00532234
J. Bourgain and G. Kalai, Influences of variables and threshold intervals under group symmetries, Geom. Funct. Anal. 7 (1997), no. 3, 438–461. MR 1466334, DOI 10.1007/s000390050015
Irit Dinur and Ehud Friedgut, Intersecting families are essentially contained in juntas, Combin. Probab. Comput. 18 (2009), no. 1-2, 107–122. MR 2497376, DOI 10.1017/S0963548308009309
Irit Dinur, Ehud Friedgut, and Oded Regev, Independent sets in graph powers are almost contained in juntas, Geom. Funct. Anal. 18 (2008), no. 1, 77–97. MR 2399096, DOI 10.1007/s00039-008-0651-1
Sean Eberhard, Product mixing in the alternating group, Discrete Anal. , posted on (2016), Paper No. 2, 19. MR 3533301, DOI 10.19086/da.610
B. Efron and C. Stein, The jackknife estimate of variance, Ann. Statist. 9 (1981), no. 3, 586–596. MR 615434, DOI 10.1214/aos/1176345462
David Ellis, Guy Kindler, and Noam Lifshitz, An analogue of Bonami’s lemma for functions on spaces of linear maps, and 2-2 games, Preprint, arXiv:2209.04243, 2022.
Yuval Filmus, Guy Kindler, Noam Lifshitz, and Dor Minzer, Hypercontractivity on the symmetric group, Preprint, arXiv:2009.05503, 2020.
Peter Frankl and Norihide Tokushige, The Erdős-Ko-Rado theorem for integer sequences, Combinatorica 19 (1999), no. 1, 55–63. MR 1722210, DOI 10.1007/s004930050045
Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park, Thresholds versus fractional expectation-thresholds, Ann. of Math. (2) 194 (2021), no. 2, 475–495. MR 4298747, DOI 10.4007/annals.2021.194.2.2
Ehud Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998), no. 1, 27–35. MR 1645642, DOI 10.1007/PL00009809
Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 (1999), no. 4, 1017–1054. With an appendix by Jean Bourgain. MR 1678031, DOI 10.1090/S0894-0347-99-00305-7
Ehud Friedgut, Hiệp Hàn, Yury Person, and Mathias Schacht, A sharp threshold for van der Waerden’s theorem in random subsets, Discrete Anal. , posted on (2016), Paper No. 7, 20. MR 3533306, DOI 10.19086/da.615
Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993–3002. MR 1371123, DOI 10.1090/S0002-9939-96-03732-X
Zoltán Füredi, Tao Jiang, and Robert Seiver, Exact solution of the hypergraph Turán problem for $k$-uniform linear paths, Combinatorica 34 (2014), no. 3, 299–322. MR 3223966, DOI 10.1007/s00493-014-2838-4
N. Fusco, F. Maggi, and A. Pratelli, The sharp quantitative isoperimetric inequality, Ann. of Math. (2) 168 (2008), no. 3, 941–980. MR 2456887, DOI 10.4007/annals.2008.168.941
W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363–387. MR 2410393, DOI 10.1017/S0963548307008826
Leonard Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1975), no. 4, 1061–1083. MR 420249, DOI 10.2307/2373688
Tom Gur, Noam Lifshitz, and Siqi Liu, Hypercontractivity on high dimensional expanders, STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2022] ©2022, pp. 176–184. MR 4489992
Elad Haramaty, Amir Shpilka, and Madhu Sudan, Optimal testing of multivariate polynomials over small prime fields, SIAM J. Comput. 42 (2013), no. 2, 536–562. MR 3035491, DOI 10.1137/120879257
Hamed Hatami, A structure theorem for Boolean functions with small total influences, Ann. of Math. (2) 176 (2012), no. 1, 509–533. MR 2925389, DOI 10.4007/annals.2012.176.1.9
Hao Huang, Po-Shen Loh, and Benny Sudakov, The size of a hypergraph and its matching number, Combin. Probab. Comput. 21 (2012), no. 3, 442–450. MR 2912790, DOI 10.1017/S096354831100068X
Vishesh Jain and Huy Tuan Pham, Optimal thresholds for Latin squares, Steiner triple systems, and edge colorings, Preprint, arXiv:2212.06109, 2022.
Anders Johansson, Jeff Kahn, and Van Vu, Factors in random graphs, Random Structures Algorithms 33 (2008), no. 1, 1–28. MR 2428975, DOI 10.1002/rsa.20224
Jeff Kahn and Gil Kalai, Thresholds and expectation thresholds, Combin. Probab. Comput. 16 (2007), no. 3, 495–502. MR 2312440, DOI 10.1017/S0963548307008474
Jeff Kahn, Gil Kalai, and Nathan Linial, The influence of variables on Boolean functions, 29th Annual Symposium on Foundations of Computer Science, IEEE, 1988, pp. 68–80.
Tali Kaufman and Dor Minzer, Improved optimal testing results from global hypercontractivity, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022, pp. 98–109. MR 4537194
Peter Keevash, The optimal edge-colouring threshold, Preprint, arXiv:2212.04397, 2022.
Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer, Sharp thresholds and expanded hypergraphs, 2019.
Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer, Forbidden intersections for codes, Preprint, arXiv:2103.05050, 2021.
Peter Keevash, Noam Lifshitz, and Dor Minzer, On the largest product-free subsets of the alternating groups, arXiv preprint arXiv:2205.15191, 2022.
Peter Keevash and Eoin Long, Stability for vertex isoperimetry in the cube, J. Combin. Theory Ser. B 145 (2020), 113–144. MR 4102766, DOI 10.1016/j.jctb.2020.04.009
Peter Keevash and Eoin Long, A stability result for the cube edge isoperimetric inequality, J. Combin. Theory Ser. A 155 (2018), 360–375. MR 3741433, DOI 10.1016/j.jcta.2017.11.005
Nathan Keller and Noam Lifshitz, The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture, Adv. Math. 392 (2021), Paper No. 107991, 95. MR 4312859, DOI 10.1016/j.aim.2021.107991
Nathan Keller and Noam Lifshitz, Approximation of biased Boolean functions of small total influence by DNFs, Bull. Lond. Math. Soc. 50 (2018), no. 4, 667–679. MR 3870950, DOI 10.1112/blms.12167
Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra, Small set expansion in the Johnson graph, Electronic Colloquium on Computational Complexity (ECCC), 2018.
Subhash Khot, Dor Minzer, and Muli Safra, Pseudorandom sets in Grassmann graph have near-perfect expansion, 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018, IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 592–601. MR 3899624, DOI 10.1109/FOCS.2018.00062
Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoǧlu, and Rüdiger L. Urbanke, Reed-Muller codes achieve capacity on erasure channels, IEEE Trans. Inform. Theory 63 (2017), no. 7, 4298–4316. MR 3666961, DOI 10.1109/TIT.2017.2673829
Noam Lifshitz, Hypergraph removal lemmas via robust sharp threshold theorems, Discrete Anal. , posted on (2020), Paper No. 11, 46. MR 4132062, DOI 10.19086/da
Eyal Lubetzky and Jeffrey E. Steif, Strong noise sensitivity and random graphs, Ann. Probab. 43 (2015), no. 6, 3239–3278. MR 3433581, DOI 10.1214/14-AOP959
G. Margulis, Probabilistic characteristic of graphs with large connectivity, Problems Info. Transmission, Plenum Press, 1977.
Madan Lal Mehta, Random matrices, 3rd ed., Pure and Applied Mathematics (Amsterdam), vol. 142, Elsevier/Academic Press, Amsterdam, 2004. MR 2129906
Richard Montgomery, Spanning trees in random graphs, Adv. Math. 356 (2019), 106793, 92. MR 3998769, DOI 10.1016/j.aim.2019.106793
Elchanan Mossel, Gaussian bounds for noise correlation of functions, Geom. Funct. Anal. 19 (2010), no. 6, 1713–1756. MR 2594620, DOI 10.1007/s00039-010-0047-x
Elchanan Mossel and Joe Neeman, Robust optimality of Gaussian noise stability, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 2, 433–482. MR 3317748, DOI 10.4171/JEMS/507
Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2) 171 (2010), no. 1, 295–341. MR 2630040, DOI 10.4007/annals.2010.171.295
Ryan O’Donnell, Analysis of Boolean functions, Cambridge University Press, New York, 2014. MR 3443800, DOI 10.1017/CBO9781139814782
Jinyoung Park and Huy Tuan Pham, A proof of the Kahn-Kalai conjecture, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022, pp. 636–639. MR 4537242
MichałPrzykucki and Alexander Roberts, Vertex-isoperimetric stability in the hypercube, J. Combin. Theory Ser. A 172 (2020), 105186, 19. MR 4046315, DOI 10.1016/j.jcta.2019.105186
Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, DOI 10.1007/BF00537230
Oded Schramm and Jeffrey E. Steif, Quantitative noise sensitivity and exceptional times for percolation, Ann. of Math. (2) 171 (2010), no. 2, 619–672. MR 2630053, DOI 10.4007/annals.2010.171.619
Stanislav Smirnov, Critical percolation and conformal invariance, XIVth International Congress on Mathematical Physics, World Sci. Publ., Hackensack, NJ, 2005, pp. 99–112. MR 2227824
Michel Talagrand, On Russo’s approximate zero-one law, Ann. Probab. 22 (1994), no. 3, 1576–1587. MR 1303654