Structure and regularity for subsets of groups with finite VC-dimension. (English) Zbl 07499437
Summary: Suppose \(G\) is a finite group and \(A\subseteq G\) is such that \(\{gA:g\in G\}\) has VC-dimension strictly less than \(k\). We find algebraically well-structured sets in \(G\) which, up to a chosen \(\epsilon > 0\), describe the structure of \(A\) and behave regularly with respect to translates of \(A\). For the subclass of groups with uniformly fixed finite exponent \(r\), these algebraic objects are normal subgroups with index bounded in terms of \(k,r\), and \(\epsilon\). For arbitrary groups, we use Bohr neighborhoods of bounded rank and width inside normal subgroups of bounded index. Our proofs are largely model-theoretic, and heavily rely on a structural analysis of compactifications of pseudofinite groups as inverse limits of Lie groups. The introduction of Bohr neighborhoods into the nonabelian setting uses model-theoretic methods related to the work of Breuillard, Green, and Tao [8] and Hrushovski [28] on approximate groups, as well as a result of Alekseev, Glebskiĭ, and Gordon [1] on approximate homomorphisms.
MSC:
| 03C45 | Classification theory, stability, and related concepts in model theory |
| 03C20 | Ultraproducts and related constructions |
| 20D60 | Arithmetic and combinatorial problems involving abstract finite groups |
| 22C05 | Compact groups |
| 22E35 | Analysis on \(p\)-adic Lie groups |
References:
| [1] | Alekseev, M. A., Glebskiȋ, L. Y., Gordon, E. I.: On approximations of groups, group actions and Hopf algebras. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. 256, 224-262, 268 (1999) Zbl 1130.20306 MR 1708567 · Zbl 1130.20306 |
| [2] | Alon, N., Fischer, E., Newman, I.: Efficient testing of bipartite graphs for forbidden induced subgraphs. SIAM J. Comput. 37, 959-976 (2007) Zbl 1141.05073 MR 2341924 · Zbl 1141.05073 |
| [3] | Alon, N., Fox, J., Zhao, Y.: Efficient arithmetic regularity and removal lemmas for induced bipartite patterns. Discrete Anal. 2019, art. 3, 14 pp. Zbl 07152902 MR 3943117 · Zbl 1472.11054 |
| [4] | Aschenbrenner, M., Dolich, A., Haskell, D., Macpherson, D., Starchenko, S.: Vapnik-Chervonenkis density in some theories without the independence property, I. Trans. Amer. Math. Soc. 368, 5889-5949 (2016) Zbl 1423.03119 MR 3458402 · Zbl 1423.03119 |
| [5] | Basu, S.: Combinatorial complexity in o-minimal geometry. Proc. London Math. Soc. (3) 100, 405-428 (2010) Zbl 1186.52017 MR 2595744 · Zbl 1186.52017 |
| [6] | Bélair, L.: Panorama of p-adic model theory. Ann. Sci. Math. Québec 36, 43-75 (2012) Zbl 1362.11107 MR 3113291 · Zbl 1362.11107 |
| [7] | Bourgain, J.: On triples in arithmetic progression. Geom. Funct. Anal. 9, 968-984 (1999) Zbl 0959.11004 MR 1726234 · Zbl 0959.11004 |
| [8] | Breuillard, E., Green, B., Tao, T.: The structure of approximate groups. Publ. Math. Inst. Hautes Études Sci. 116, 115-221 (2012) Zbl 1260.20062 MR 3090256 · Zbl 1260.20062 |
| [9] | Chernikov, A., Simon, P.: Definably amenable NIP groups. J. Amer. Math. Soc. 31, 609-641 (2018) Zbl 06870167 MR 3787403 · Zbl 1522.03112 |
| [10] | Chernikov, A., Starchenko, S.: Regularity lemma for distal structures. J. Eur. Math. Soc. 20, 2437-2466 (2018) Zbl 06966829 MR 3852184 · Zbl 1459.03041 |
| [11] | Chernikov, A., Starchenko, S.: Definable regularity lemmas for NIP hypergraphs. Quart. J. Math. (online, 2021) · Zbl 1480.05098 · doi:10.1093/qmath/haab011 |
| [12] | Conant, G.: Quantitative structure of stable sets in arbitrary finite groups. arXiv:2004.02819 (2020) |
| [13] | Conant, G.: On finite sets of small tripling or small alternation in arbitrary groups. Combin. Probab. Comput. 29, 807-829 (2020) MR 4173133 · Zbl 1504.20028 |
| [14] | Conant, G., Pillay, A., Terry, C.: A group version of stable regularity. Math. Proc. Cambridge Philos. Soc. 168, 405-413 (2020) Zbl 07167602 MR 4064112 · Zbl 1539.03116 |
| [15] | Conant, G., Pillay, A.: Pseudofinite groups and VC-dimension. J. Math. Logic (online, 2020) · Zbl 07410403 · doi:10.1142/S0219061321500094 |
| [16] | Dixon, J. D., du Sautoy, M. P. F., Mann, A., Segal, D.: Analytic pro-p Groups. 2nd ed., Cam-bridge Stud. Adv. Math. 61, Cambridge Univ. Press, Cambridge (1999) Zbl 0934.20001 MR 1720368 · Zbl 0934.20001 |
| [17] | Erdős, P., Hajnal, A.: Ramsey-type theorems. Discrete Appl. Math. 25, 37-52 (1989) Zbl 0715.05052 MR 1031262 · Zbl 0715.05052 |
| [18] | Fox, J., Gromov, M., Lafforgue, V., Naor, A., Pach, J.: Overlap properties of geometric expanders. J. Reine Angew. Math. 671, 49-83 (2012) Zbl 1306.05171 MR 2983197 · Zbl 1306.05171 |
| [19] | Fox, J., Pach, J., Suk, A.: A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing. SIAM J. Comput. 45, 2199-2223 (2016) Zbl 1353.05090 MR 3585030 · Zbl 1353.05090 |
| [20] | Fox, J., Pach, J., Suk, A.: Erdős-Hajnal conjecture for graphs with bounded VC-dimension. Discrete Comput. Geom. 61, 809-829 (2019) Zbl 1411.05179 MR 3943496 · Zbl 1411.05179 |
| [21] | Gowers, W. T.: Lower bounds of tower type for Szemerédi’s uniformity lemma. Geom. Funct. Anal. 7, 322-337 (1997) Zbl 0876.05053 MR 1445389 · Zbl 0876.05053 |
| [22] | Gowers, W. T.: Quasirandom groups. Combin. Probab. Comput. 17, 363-387 (2008) Zbl 1191.20016 MR 2410393 · Zbl 1191.20016 |
| [23] | Gowers, W. T., Wolf, J.: Linear forms and higher-degree uniformity for functions on F n p . · Zbl 1262.11012 |
| [24] | Geom. Funct. Anal. 21, 36-69 (2011) Zbl 1262.11012 MR 2773103 · Zbl 1262.11012 |
| [25] | Green, B.: A Szemerédi-type regularity lemma in abelian groups, with applications. Geom. Funct. Anal. 15, 340-376 (2005) Zbl 1160.11314 MR 2153903 · Zbl 1160.11314 |
| [26] | Green, B., Tao, T.: An arithmetic regularity lemma, an associated counting lemma, and applications. In: An Irregular Mind, Bolyai Soc. Math. Stud. 21, János Bolyai Math. Soc., Budapest, 261-334 (2010) Zbl 1222.11015 MR 2815606 · Zbl 1222.11015 |
| [27] | Hewitt, E., Ross, K. A.: Abstract Harmonic Analysis. Vol. I. 2nd ed., Grundlehren Math. Wiss. 115, Springer, Berlin (1979) Zbl 0837.43002 MR 551496 |
| [28] | Hofmann, K. H., Morris, S. A.: The Structure of Compact Groups. De Gruyter Stud. Math. 25, De Gruyter, Berlin (2013) Zbl 1441.22001 MR 3114697 · Zbl 1277.22001 |
| [29] | Hrushovski, E.: Stable group theory and approximate subgroups. J. Amer. Math. Soc. 25, 189-243 (2012) Zbl 1259.03049 MR 2833482 · Zbl 1259.03049 |
| [30] | Hrushovski, E., Peterzil, Y., Pillay, A.: Groups, measures, and the NIP. J. Amer. Math. Soc. 21, 563-596 (2008) Zbl 1134.03024 MR 2373360 · Zbl 1134.03024 |
| [31] | Hrushovski, E., Pillay, A.: Groups definable in local fields and pseudo-finite fields. Israel J. Math. 85, 203-262 (1994) Zbl 0804.03024 MR 1264346 · Zbl 0804.03024 |
| [32] | Hrushovski, E., Pillay, A.: On NIP and invariant measures. J. Eur. Math. Soc. 13, 1005-1061 (2011) Zbl 1220.03016 MR 2800483 · Zbl 1220.03016 |
| [33] | Hrushovski, E., Pillay, A., Simon, P.: Generically stable and smooth measures in NIP theories. Trans. Amer. Math. Soc. 365, 2341-2366 (2013) Zbl 1294.03023 MR 3020101 · Zbl 1294.03023 |
| [34] | Iltis, R.: Some algebraic structure in the dual of a compact group. Canad. J. Math. 20, 1499-1510 (1968) Zbl 0169.34801 MR 232892 · Zbl 0169.34801 |
| [35] | Krupiński, K., Newelski, L.: On bounded type-definable equivalence relations. Notre Dame J. Formal Logic 43, 231-242 (2003) (2002) Zbl 1050.03026 MR 2034748 · Zbl 1050.03026 |
| [36] | Lovász, L., Szegedy, B.: Regularity partitions and the topology of graphons. In: An Irregular Mind, Bolyai Soc. Math. Stud. 21, János Bolyai Math. Soc., Budapest, 415-446 (2010) Zbl 1242.05188 MR 2815610 · Zbl 1242.05188 |
| [37] | Macpherson, D., Tent, K.: Profinite groups with NIP theory and p-adic analytic groups. Bull. London Math. Soc. 48, 1037-1049 (2016) Zbl 1430.03054 MR 3608949 · Zbl 1430.03054 |
| [38] | Malliaris, M., Shelah, S.: Regularity lemmas for stable graphs. Trans. Amer. Math. Soc. 366, 1551-1585 (2014) Zbl 1283.05234 MR 3145742 · Zbl 1283.05234 |
| [39] | Marker, D.: Model Theory. Grad. Texts in Math. 217, Springer, New York (2002) Zbl 1003.03034 MR 1924282 · Zbl 1003.03034 |
| [40] | Nikolov, N., Schneider, J., Thom, A.: Some remarks on finitarily approximable groups. J. École Polytech. Math. 5, 239-258 (2018) Zbl 1452.20025 MR 3749196 · Zbl 1452.20025 |
| [41] | Onshuus, A., Pillay, A.: Definable groups and compact p-adic Lie groups. J. London Math. Soc. (2) 78, 233-247 (2008) Zbl 1153.03015 MR 2427062 · Zbl 1153.03015 |
| [42] | Pillay, A.: Type-definability, compact Lie groups, and o-minimality. J. Math. Logic 4, 147-162 (2004) Zbl 1069.03029 MR 2114965 · Zbl 1069.03029 |
| [43] | Pillay, A.: Remarks on compactifications of pseudofinite groups. Fund. Math. 236, 193-200 (2017) Zbl 1420.03063 MR 3591278 · Zbl 1420.03063 |
| [44] | Ribes, L., Zalesskii, P.: Profinite Groups, 2nd ed., Ergeb. Math. Grenzgeb. 40, Springer, Berlin (2010) Zbl 1197.20022 MR 2599132 · Zbl 1197.20022 |
| [45] | Shelah, S.: Minimal bounded index subgroup for dependent theories. Proc. Amer. Math. Soc. 136, 1087-1091 (2008) Zbl 1144.03026 MR 2361885 · Zbl 1144.03026 |
| [46] | Simon, P.: Distal and non-distal NIP theories. Ann. Pure Appl. Logic 164, 294-318 (2013) Zbl 1269.03037 MR 3001548 · Zbl 1269.03037 |
| [47] | Simon, P.: A Guide to NIP Theories. Lecture Notes in Logic 44, Assoc. Symbolic Logic, Chicago, IL, and Cambridge Sci. Publ., Cambridge (2015) Zbl 1332.03001 MR 3560428 · Zbl 1332.03001 |
| [48] | Simon, P.: Rosenthal compacta and NIP formulas. Fund. Math. 231, 81-92 (2015) Zbl 1372.03068 MR 3361236 · Zbl 1372.03068 |
| [49] | Simon, P.: VC-sets and generic compact domination. Israel J. Math. 218, 27-41 (2017) Zbl 1367.03068 MR 3625123 · Zbl 1367.03068 |
| [50] | Sisask, O.: Convolutions of sets with bounded VC-dimension are uniformly continuous. Dis-crete Anal. (online, 2018) · Zbl 1498.11043 · doi:10.19086/da.18561 |
| [51] | Szemerédi, E.: Regular partitions of graphs. In: Problèmes combinatoires et théorie des graphes (Orsay, 1976), Colloq. Internat. CNRS 260, CNRS, Paris, 399-401 (1978) Zbl 0413.05055 MR 540024 · Zbl 0413.05055 |
| [52] | Tao, T., Vu, V.: Additive Combinatorics. Cambridge Stud. Adv. Math. 105, Cambridge Univ. Press, Cambridge (2006) Zbl 1127.11002 MR 2289012 · Zbl 1127.11002 |
| [53] | Terry, C., Wolf, J.: Stable arithmetic regularity in the finite field model. Bull. London Math. Soc. 51, 70-88 (2019) Zbl 07040809 MR 3919562 · Zbl 1462.11015 |
| [54] | Terry, C., Wolf, J.: Quantitative structure of stable sets in finite abelian groups. Trans. Amer. Math. Soc. 373, 3885-3903 (2020) Zbl 07207622 MR 4105513 · Zbl 1477.11023 |
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.
