The Balog–Szemerédi–Gowers theorem

For a single finite nonempty set A, suppose its counting energy is at least the cube of its cardinality divided by K, with K at least one. There are absolute positive constants c and C such that one can find a subset A′ containing at least c times K to a negative absolute power times the size of A, and with doubling at most an absolute constant times a fixed power of K. Enlarging the same symbol C if necessary gives the concise formulation below. No specific optimal exponent is claimed.

The constants are uniform over the group and the set, but their existence does not give a numerical promise such as retaining half the elements when K equals two. The theorem does not say every subset of that size has small doubling, and it does not control the entire original set. A two-set version uses mixed energy with a geometric-mean normalization and gives two extracted subsets. That version needs its own careful bookkeeping; the single-set theorem already captures the essential extraction principle used here.

Take an integer interval I with n elements and add n widely separated positive integers R, chosen as successive powers of an integer M greater than twice n. The translates I+r for r in R are disjoint, so the mixed sums alone supply n squared outputs. The full set A has size twice n, and its doubling constant is therefore at least n divided by two. This growth becomes unbounded with n, despite the fixed-density interval core inside A.

The energy contributed by that interval alone is already at least two thirds of n cubed. Relative to the cube of the full size, this is at least one twelfth. Thus A has energy at least |A| cubed divided by twelve while its doubling grows without bound. This is a concrete family disproving a whole-set converse. The subset I supplies the small-doubling object that the extraction theorem predicts in qualitative terms, without telling us that every high-energy input must literally contain an interval.

A proof first identifies differences with many representations. Their popularity captures a substantial part of the energy rather than just many arbitrary pairs. Regard the associated relations as edges of a bipartite graph. A graph lemma finds large vertex subsets with many short connecting paths between their members. Labels along a path express endpoint differences as combinations of popular differences, converting robust connectivity into a small collection of possible endpoint differences. Counting many paths is what controls multiplicity in this conversion.

Ruzsa inequalities then convert the resulting difference control into small doubling for an extracted set. This paragraph is a proof roadmap, not a replacement for the graph lemma or its quantitative proof. The reason to learn the roadmap is operational: energy is a second-moment statistic that may be concentrated, and the graph step removes that concentration before a structural theorem is invoked. In applications one should carry both the retained-size lower bound and the doubling upper bound into the next argument; retaining only the word structured loses the quantitative content.