research30 min studyLesson 642 in Mathematics

Ruzsa distance and the covering lemma

Turn overlap of translates into a triangle inequality and a controlled covering.

Before you begin

Sumsets and basic growth inequalities

On this page

The question for today

What you’ll understand

Derive Ruzsa’s triangle inequality from an injection.
Explain why Ruzsa distance need not vanish on the diagonal.
Construct a covering from a maximal disjoint family of translates.

Difference sets connect additive growth with a useful geometry of finite sets. This geometry is deliberately weaker than a metric: a set can have positive distance from itself, and distinct subgroup cosets can have zero distance. Its power comes from a triangle inequality that transfers information between pairs of sets. A companion covering lemma replaces many overlapping translates by a few translates of one difference set. Both statements require finite nonempty inputs inside the same abelian group.

An injective encoding proves the triangle inequality

For each difference between A and C, choose one ordered representation once and keep it fixed. Pair that chosen difference with an arbitrary element of B. Record the difference between its A representative and the B element, and the difference between that B element and its C representative. Adding the recorded differences recovers the original difference. Its fixed representation then recovers the B element as well, so the encoding is injective. Counting the domain and codomain gives the displayed inequality.

Divide the inequality by the square root of the relevant cardinalities and take logarithms. The resulting normalized quantity is symmetric because negating a difference set preserves its size. It is nonnegative because the difference set contains translates of both inputs and thus has size at least their geometric mean. The square-root normalization is not cosmetic: it exactly cancels the intermediate set size when composing two bounds, turning a multiplicative counting inequality into an additive triangle inequality.

|A-C|\,|B|\le |A-B|\,|B-C|,\qquad d(A,C)=\log\frac{|A-C|}{\sqrt{|A||C|}}\le d(A,B)+d(B,C).

The logarithm is natural; all three sets must be finite and nonempty.↔ Scroll wide equations horizontally.

A distance with deliberately missing metric axioms

An integer interval with more than one element has a difference set larger than itself, so its distance from itself is positive. By contrast, two cosets of the same finite subgroup have a difference set that is one coset of that subgroup. Their normalized distance is zero, even if the cosets are disjoint. These examples rule out treating zero distance as equality, or importing metric-space arguments that require a zero diagonal and separation of points.

The useful interpretation is similarity of additive scale and shape, measured through differences. A small distance also controls cardinality imbalance: the larger input cannot be arbitrarily larger than the smaller one because their difference set already contains the larger translate. Notice the sign in the definition. A bound for a sumset directly bounds distance from the negative of the other set, not automatically distance from that set itself. Switching sums and differences without checking the sign obscures which inequality is being applied.

Maximal disjoint translates become a cover

Assume the sumset of A and B has size at most K times the size of B. Select an inclusion-maximal subset X of A for which the translates x+B are pairwise disjoint. Their union sits inside A+B, so counting the disjoint copies gives a bound of K on the size of X. Finite nonempty sets ensure that a maximal family exists and is nonempty. Maximal means no new translate can be added; it does not mean that the family has the largest possible size.

Every remaining translate a+B intersects some selected translate x+B. At an intersection one can write a plus one B element as x plus another B element, placing a in x+(B−B). This proves the cover. The conclusion uses a difference set, which can be substantially larger than B. It does not assert that A is covered by K translates of B itself, nor that the selected translates tile A. The disjointness argument and the overlap argument have separate roles.

|A+B|\le K|B|\quad\Longrightarrow\quad \exists X\subseteq A:\ |X|\le K,\qquad A\subseteq X+(B-B).

The maximal disjoint family has integer size at most floor(K); the covering sets themselves may overlap.↔ Scroll wide equations horizontally.

Work it through

Build the cover explicitly

Take $A=\{0,1,2,3,4,5\}$ and $B=\{0,1\}$ in the integers. Find a maximal disjoint family and verify the covering conclusion.

The sumset is {0,1,2,3,4,5,6}, so its size seven gives K=7/2 relative to B. Any disjoint family of translates contains at most three members.
Choose X={0,2,4}. The translates are {0,1}, {2,3}, and {4,5}. They are disjoint, and every other translate indexed by A intersects this family.
Now B−B={−1,0,1}. The union X+(B−B) is {−1,0,1,2,3,4,5}, which contains every element of A.

The result

Three selected translates suffice for the difference-set cover. The nonintegral bound seven halves is a cardinality bound, not a demand for a fractional translate.

The living notebook

Explore the model

Interactive lab

Interactive lab · modular

Zero distance between different cosets

Reset and set modulus 9, step 3. Step until the residues 0,3,6 are visible. Call this subgroup H and form the translated set 1+H on paper. Predict the size of H−(1+H) and the resulting normalized distance. The instrument shows only the generating orbit; it does not compute the cover or logarithm. Control changes retain the clock, so Reset and restore both settings for a fresh run.

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 forTwo different cosets can have Ruzsa distance zero; separation is not a metric axiom available here.

Pause & reason

Check your understanding

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

Read the checkpoint explanation

A maximal disjoint family gives a difference-set cover with at most K indices. It need not tile A, need not have exactly K members, and maximal families need not be maximum families.

Your turn

Try it yourself

In the group $\mathbb Z/9\mathbb Z$ , let $A=\{0,3,6\}$ and $B=\{1,4,7\}$ . Compute A−B, d(A,B), and d(A,A). Explain why these values cause no contradiction.

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

Give me a hint

Subtract one coset from another; each result is a coset of the same subgroup.

Compare with the solution

A−B={2,5,8}, while A−A={0,3,6}. Each difference set has size three, and both inputs have size three. The normalized ratio is three divided by the square root of nine, hence one; both logarithms are zero. A and B are nevertheless distinct disjoint cosets. Ruzsa distance obeys symmetry, nonnegativity, and the triangle inequality, but it is not a metric on finite sets.

Keep the idea

Take it with you

The triangle inequality follows from a recoverable encoding of differences and an intermediate element.
Ruzsa distance can have a positive diagonal or vanish between distinct sets.
The covering lemma covers with translates of B−B, with the denominator |B|.

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.