VC-dimension of generalized progressions in some nonabelian groups
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908382018928640 |
|---|---|
| author | Conant, Gabriel Arodirik, Aycin Iplikci Ozawa, Tora Zeng, David |
| author_facet | Conant, Gabriel Arodirik, Aycin Iplikci Ozawa, Tora Zeng, David |
| contents | We analyze generalized progressions in some nonabelian groups using a measure of complexity called VC-dimension, which was originally introduced in statistical learning theory by Vapnik and Chervonenkis. Here by a "generalized progression" in a group $G$, we mean a finite subset of $G$ built from a fixed set of generators in analogy to a (multidimensional) arithmetic progression of integers. These sets play an important role in additive combinatorics and, in particular, the study of approximate groups. Our two main results establish finite upper bounds on the VC-dimension of certain set systems of generalized progressions in finitely generated free groups and also the Heisenberg group over $\mathbb{Z}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21789 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | VC-dimension of generalized progressions in some nonabelian groups Conant, Gabriel Arodirik, Aycin Iplikci Ozawa, Tora Zeng, David Group Theory Combinatorics Logic We analyze generalized progressions in some nonabelian groups using a measure of complexity called VC-dimension, which was originally introduced in statistical learning theory by Vapnik and Chervonenkis. Here by a "generalized progression" in a group $G$, we mean a finite subset of $G$ built from a fixed set of generators in analogy to a (multidimensional) arithmetic progression of integers. These sets play an important role in additive combinatorics and, in particular, the study of approximate groups. Our two main results establish finite upper bounds on the VC-dimension of certain set systems of generalized progressions in finitely generated free groups and also the Heisenberg group over $\mathbb{Z}$. |
| title | VC-dimension of generalized progressions in some nonabelian groups |
| topic | Group Theory Combinatorics Logic |
| url | https://arxiv.org/abs/2505.21789 |