Apply part (a). The subgroup is finite because it lies in the finite set . Conjugation gives a homomorphism
Its kernel has finite index in and centralizes . Since is a subgroup of the -step nilpotent group , it is itself nilpotent of class . Hence
for some . As centralizes , one more group commutator vanishes, so . Thus is nilpotent of class at most .
Both and are finite, so
This is the Gromov theorem on groups of polynomial growth in the form needed here.
Put and consider the powers
where is maximal subject to . For sufficiently large in terms of , one has . Since the successive growth ratios telescope,
Thus one ratio is at most . For the corresponding ,
Set . Then , so the small-tripling argument from Question 1(b) makes
an -approximate group. Apply the Breuillard-Green-Tao structure theorem for approximate groups. It gives subgroups
such that
is a nilpotent group of class , and is covered by left cosets of .
It remains to pass from a covering to an index bound. The ball meets only vertices of the Schreier graph of . If had more vertices, a simple path from would give more than that many distinct cosets within distance . Since and is sufficiently large, this is impossible. Therefore
Choose one representative from above each point of and collect them in . Part (c) gives . If has the same image as , then , so
This is the required covering of by at most left cosets of the abelian translation subgroup .
The set is a -approximate group by the intersection of an approximate group power with a subgroup. Apply the Freiman-Green-Ruzsa theorem inside . Because the additive group of the complex numbers is a torsion-free group, the finite subgroup part is trivial, so there is an abelian progression with
Since , enlarging the implicit constant gives
Write and identify it with as in part (a). If every two members of commuted, then would be Abelian, contrary to hypothesis. Thus some commutator of two members of is a nonidentity translation in . Consequently the translation-coordinate set
contains both zero and a nonzero element.
The identity
shows that is contained in the translation coordinates of , while is contained in those of . The intersection of an approximate group power with a subgroup therefore gives
Apply the Solymosi sum-product theorem over the complex numbers with and . Since , its hypotheses hold, and
Cancelling and absorbing the absolute constant proves
The Solymosi sum-product theorem over the complex numbers states that if finite satisfy and , then
Composition and inversion in the Affine group of the complex line are
The map
is therefore a surjective group homomorphism with kernel
Its target is Abelian, so . On the other hand, the stated computation gives
Fixing any and varying produces every translation. Thus , and hence
Let be the abelianization map. Its image is again a -approximate group. Apply the large-progression form of the Freiman-Green-Ruzsa theorem to . It gives a finite subgroup , elements , and lengths , with
and
The large lifted product from a coset progression applied to this progression gives
Briefly, choose a section of on . Multiplication by that section is multiplicative up to ; lifting successively the subgroup part and each progression direction therefore places every element of in the displayed product. The fiber-counting lemma for a quotient map gives , which proves the estimate.
Set
The intersection of an approximate group power with a subgroup shows that each is a -approximate group contained in . The preimage of a cyclic subgroup of has step less than . The same is true of the preimage of the finite subgroup because is a torsion-free group. Consequently each has step less than , and the displayed estimate is the required conclusion.
Choose a covering set of size at most such that , as allowed by the definition of an approximate group. Discard every for which does not meet . Each remaining belongs to , so . Induction gives
Because is symmetric and contains the identity, . Hence
We use the bounded-exponent finitely generated nilpotent group order bound. In an -step nilpotent group, a subgroup generated by elements is generated in collected form by the simple group commutators in those generators of weights at most . There are at most
such commutators. Every one has order at most , so
Taking now gives
By the Plünnecke-Ruzsa inequality,
Apply the Ruzsa covering lemma to and . Since , there is a set with such that
Adding and reusing this inclusion inductively gives
A sum of members of the fixed set depends only on the multiplicity of each member. The number of possible multiplicity vectors is at most , and therefore
Since , it follows that
For fixed , this differs from the Plünnecke–Ruzsa bound only by a polynomial factor in , so both have the same leading exponential function factor .
The Noncommutative Ruzsa triangle inequality says that nonempty finite subsets of a group satisfy
The Ruzsa covering lemma says that if , then some with satisfies
Now let be a symmetric subset of a group, so and . Apply the triangle inequality with the middle set to obtain, for ,
The hypothesis therefore gives . Starting from proves
In particular . Apply the covering lemma to and . There is with such that
The set is symmetric and contains the identity element, so this inclusion is exactly the covering condition showing that
Small doubling alone is insufficient in a noncommutative group. Let be a finite group, let be its free product with an infinite cyclic group, and put
Then is symmetric and , while contains the double coset . Distinct pairs give distinct reduced words , so . Letting proves the small doubling does not control tripling in a noncommutative group phenomenon.
The Plünnecke-Ruzsa inequality states that, for all nonnegative integers ,
Here is the iterated sumset of copies of , with . In particular, .
Give the uniform probability measure and let be the indicator function of the edge set. For partitions and , define the energy
Because conditional expectation is an orthogonal projection in L2 space, .
Suppose the pair of partitions is not -regular. For each irregular choose witnesses and with
Refine each by all sets and each by all sets . If the old partitions have cells, the refined ones have at most cells.
The Pythagorean theorem for the two nested conditional-expectation projections gives
Inside an irregular , the witness rectangle occupies at least an proportion and the mean of the displayed difference over it has magnitude greater than . The Cauchy-Schwarz inequality therefore gives an energy gain greater than
from that pair. Since irregular pairs have total weight greater than , the complete refinement raises the energy by more than .
Energy is at most one, so after at most refinements the process stops at an -regular pair of partitions. Iterating the cell-count bounds and from a bounded number of times produces a finite independent of . This proves the Bipartite Szemerédi regularity lemma.
For nonempty and , their edge density of a bipartite graph is
The pair is -regular when every and with and satisfy
For set partitions and , the regular pair of bipartite partitions condition is
Remove the quadratic phase by setting
The phase around the parallelogram is
so the hypothesis says exactly that , with harmless negative choices of the increments. The Fourier identity for the Gowers U2 norm and the Parseval identity now give
where the last inequality uses . Thus the Quadratic phase detection by the Gowers U2 norm supplies an such that
We prove the polynomial nonvanishing below the field size by mathematical induction on . The case is the Lagrange root bound over a field: a nonzero polynomial of degree below cannot have all elements of as roots.
For the induction step, suppose that vanishes on all of and write
The upper limit is valid because the total degree of a polynomial is less than . Fixing the first variables produces a univariate polynomial of degree below which vanishes at every . It is therefore the zero polynomial, so every vanishes on all of . Each also has total degree below , and the induction hypothesis gives for every . Thus .
Taking the contrapositive, every nonzero such has some for which

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact