# Complexity and randomness in the Heisenberg groups (and beyond)

@article{Diaconis2021ComplexityAR, title={Complexity and randomness in the Heisenberg groups (and beyond)}, author={Persi Diaconis and Maryanthe Malliaris}, journal={New Zealand Journal of Mathematics}, year={2021} }

By studying the commuting graphs of conjugacy classes of the sequence of Heisenberg groups $H_{2n+1}(p)$ and their limit $H_\infty(p)$ we find pseudo-random behavior (and the random graph in the limiting case). This makes a nice case study for transfer of information between finite and infinite objects. Some of this behavior transfers to the problem of understanding what makes understanding the character theory of the uni-upper-triangular group (mod p) “wild.” Our investigations in this paper… Expand

#### One Citation

Isomorphisms between random graphs

- Mathematics
- 2021

Consider two independent Erdős–Rényi G(N, 1/2) graphs. We show that with probability tending to 1 as N → ∞, the largest induced isomorphic subgraph has size either ⌊xN − εN⌋ or ⌊xN + εN⌋, where xN =… Expand

#### References

SHOWING 1-10 OF 51 REFERENCES

On the role of the Heisenberg group in harmonic analysis

- Mathematics
- 1980

In this article I want to popularize the Heisenberg group, which is remarkably little known considering its ubiquity. I use the word ubiquity advisedly. To justify it, let me give a sample of the… Expand

Do infinite nilpotent groups always have equipotent Abelian subgroups

- Mathematics
- 1972

$ 1. INTRODUCTION In 14; Theorem 31, it was shown that every infinite ZPC-group G (this class of groups includes both FC-groups and nilpotent groups) has an abelian subgroup A such that exp IAl >… Expand

ON HIGMAN’S k(Un(q)) CONJECTURE

- 2015

A classical conjecture by Graham Higman states that the number of conjugacy classes of Un(q), the group of upper triangular n × n matrices over Fq, is polynomial in q, for all n. In this paper we… Expand

Counting characters of upper triangular groups

- Mathematics
- 2007

Abstract Working over a finite field of order q, let U n ( q ) be the group of upper triangular n × n matrices with all diagonal entries equal to 1. It is known that all complex irreducible… Expand

Random walk on unipotent matrix groups

- Mathematics
- Annales scientifiques de l'École Normale Supérieure
- 2021

We introduce a new method for proving central limit theorems for random walk on nilpotent groups. The method is illustrated in a local central limit theorem on the Heisenberg group, weakening the… Expand

Finite Structures with Few Types

- Mathematics
- 1993

I will report on joint work with G. Cherlin on the quasi-finite axiomatizability of smoothly approximable structures, and on finite structures with few types. Let L be a finite language, k an… Expand

An Exercise (?) in Fourier Analysis on the Heisenberg Group

- Mathematics
- 2015

Let H(n) be the group of 3x3 uni-uppertriangular matrices with entries in Z/nZ, the integers mod n. We show that the simple random walk converges to the uniform distribution in order n^2 steps. The… Expand

Natural quasirandomness properties

- Mathematics
- 2020

The theory of quasirandomness has greatly expanded from its inaugural graph theoretical setting to several different combinatorial objects such as hypergraphs, tournaments, permutations, etc.… Expand

Large Networks and Graph Limits

The book Large Networks and Graph Limits, xiv + 475 pp., published in late 2012, comprises five parts, the first an illuminating introduction and the last a tantalizing taste of how the scope of the… Expand

ON THE COMMUTING PROBABILITY IN FINITE GROUPS

- Mathematics
- 2006

For Bernd Fischer on the occasion of his 70th birthdayIntroduction: When Gis a nite group, we may endow G Gwith the structureof a probability space by assigning the uniform distribution. As was… Expand