research30 min studyLesson 644 in Mathematics

Additive energy and balancing identities

Count collisions exactly and separate the density contribution from structured fluctuations.

Before you begin

Plünnecke–Ruzsa inequalities

On this page

The question for today

What you’ll understand

Compute energy using sum and difference representation counts.
Derive the small-sumset energy lower bound.
Distinguish an indicator’s density from its balanced fluctuation.

Two sets may have the same sumset size but distribute representations very differently across its outputs. Additive energy records that distribution through a second moment. It counts ordered quadruples, so repeated coordinates and reversed pairs must not be silently removed. We first work in an arbitrary abelian group with finite nonempty sets, then introduce a finite ambient group only when averages and densities are needed. This separation keeps the counting normalization visible.

Two equivalent collision counts

Let the sum representation count at an output s be the number of ordered pairs from A and B adding to s. Squaring this count chooses two representations of the same sum, and summing over outputs gives mixed additive energy. A rearrangement of the equality of two sums shows that the same number is the sum, over differences d, of the product of the within-A and within-B difference counts. This latter formula uses within-set differences, rather than the square of an arbitrary mixed difference count without checking the indexing.

For a single set both descriptions reduce to sums of squares of its representation counts. Energy is at least the number of trivial coincidences, but large energy on the cubic scale indicates many additional relations. An upper bound follows because choosing three coordinates determines the fourth; for a set of size m, energy is at most m cubed. A finite subgroup attains that bound. These are ordered relations, so an unordered-pair counting convention would introduce different coefficients.

E(A,B)=\sum_s r_{A+B}(s)^2=\sum_d r_{A-A}(d)r_{B-B}(d),\qquad E(A)\le |A|^3.

All representation counts use ordered pairs; the equality follows by rearranging a+b=a′+b′.↔ Scroll wide equations horizontally.

Cauchy–Schwarz links energy to growth

The sum of all representation counts is the product of the input sizes. Apply Cauchy–Schwarz on their support, which is exactly the sumset. A small support forces a large second moment. For one set, doubling at most K therefore forces energy at least its cardinality cubed divided by K. This direction is immediate and quantitative. It is a statement about collisions averaged over the output distribution, not a claim that every output has many representations.

The converse fails for the whole set. A structured piece can supply a large collection of collisions while other elements scatter their sums widely. Balog–Szemerédi–Gowers later extracts a large structured subset from high energy; it does not reverse Cauchy–Schwarz into a whole-set bound. When testing a putative converse, adding unrelated elements to an interval is a useful diagnostic. The interval retains many relations even if the added elements create numerous distinct outputs.

E(A,B)\ge\frac{|A|^2|B|^2}{|A+B|},\qquad |A+A|\le K|A|\Longrightarrow E(A)\ge\frac{|A|^3}{K}.

Cauchy–Schwarz applies to the nonzero representation counts, indexed by A+B.↔ Scroll wide equations horizontally.

Balance an indicator before asking about randomness

Now let the ambient group G be finite of size N, and let alpha be the density of A. Subtract alpha from its indicator to obtain a balanced function f. Its normalized mean is zero, and its mean square is alpha times one minus alpha. The subtraction removes the constant density contribution, making a correlation with a nonconstant test meaningful. It does not assert that f is random or that its other correlations vanish. Balancing is a definition, not a pseudorandomness theorem.

The normalized additive-quadruple average of an indicator is its counting energy divided by N cubed: three group coordinates are free and determine the fourth. An independent-density heuristic would suggest alpha to the fourth power. This heuristic is a baseline rather than an exact identity for an arbitrary set. In the next lesson Fourier analysis identifies that baseline as the trivial-character contribution and expresses the excess as a nonnegative sum. Mixing the normalizations N cubed and the set size cubed would confuse ambient density with internal additive structure.

Work it through

Energy of a three-point interval

Let $A=\{0,1,2\}\subset\mathbb Z$ . Compute energy from sums and from differences, and compare with the Cauchy–Schwarz lower bound.

The sum outputs zero through four have multiplicities 1,2,3,2,1. Squaring and summing gives 1+4+9+4+1=19.
The difference multiplicities are three at zero, two at each of ±1, and one at each of ±2. Their squared sum is 9+4+4+1+1=19, agreeing with the sum calculation.
The sumset has size five, so the lower bound is 3⁴/5=81/5=16.2. Energy nineteen lies above this bound and below the cubic upper bound twenty-seven.

The result

Different multiplicity conventions would change nineteen; retaining all ordered pairs makes both identities agree exactly.

The living notebook

Explore the model

Interactive lab

Interactive lab · modular

An orbit with maximal cubic energy

Reset and set modulus 12, step 3. Predict the orbit H={0,3,6,9} and its period four, then inspect it with Step. For every three elements a,b,c of H, predict whether a+b−c remains in H. Use that closure to count energy as 4³=64 on paper. The lab enumerates residues, not quadruples or energy; Reset restores both settings and time, while a control change retains time.

Additive orbitCurrent residue / next edge

Residue r0: 0
Orbit period · m/gcd(m,a): 12
Distinct residues visited: 1 of 12

Modulus m12Additive step a5

t = 0 s

Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forSubgroup closure makes every choice of three coordinates complete to an additive quadruple, attaining cubic energy.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

Cauchy–Schwarz gives a lower bound on the second moment. It does not force equal representation counts, and balancing removes the mean rather than the variance.

Your turn

Try it yourself

Compute the energy of $A=\{0,1,3\}\subset\mathbb Z$ and compare with $|A|^4/|A+A|$ . List the multiplicities rather than counting only distinct sums.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

There are six outputs. Off-diagonal ordered pairs contribute twice, but diagonal pairs contribute once.

Compare with the solution

The outputs 0,1,2,3,4,6 have multiplicities 1,2,1,2,2,1 respectively. Their total is nine, as required for three squared ordered pairs. Their squared sum is 1+4+1+4+4+1=15. The sumset size is six, so Cauchy–Schwarz gives 81/6=13.5, consistent with energy fifteen. The upper bound twenty-seven also holds. Treating each distinct sum as one representation would incorrectly return six.

Keep the idea

Take it with you

Energy counts ordered collisions and can be computed from sums or within-set differences.
Small doubling forces high energy; a whole-set converse needs replacement by a subset theorem.
Balanced indicators remove the mean, while ambient normalization divides energy by |G|³.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.