Dyson's transform

Dyson's transform is a fundamental technique in additive number theory for transforming a pair of integer sequences into another pair of integer sequences. It was developed by Freeman Dyson as part of his proof of Mann's theorem on the Schnirelmann density of sumsets, is used to prove such fundamental results of additive number theory as the Cauchy–Davenport theorem on the size of restricted sumsets, and was used by Olivier Ramaré in his work (related to the Goldbach conjecture) that proved that every even integer is the sum of at most 6 prime numbers. The term Dyson's transform for this technique is used by Ramaré. Halberstam and Roth call it the τ-transformation.

Formulation

This formulation of the transform is from Ramaré. Let $A$ be a sequence of natural numbers, and $x$ be any real number. Write $A(x)$ for the number of elements of $A$ which lie in $[1,x]$. Suppose $A=\{a_{1}<a_{2}<\cdots \}$ and $B=\{0=b_{1}<b_{2}<\cdots \}$ are two sequences of natural numbers. We write $A+B$ for the sumset, that is, the set of all elements $a+b$ where $a$ is in $A$ and $b$ is in $B$; and similarly $A-B$ for the set of differences $a-b$. For any element $e$ in $A$, Dyson's transform consists in forming the sequences $A'=A\cup (B+\{e\})$ and $\,B'=B\cap (A-\{e\})$.

Properties

The transformed sequences have the properties:

• $A'+B'\subset A+B$
• $\{e\}+B'\subset A'$
• $0\in B'$
• $A'(m)+B'(m-e)=A(m)+B(m-e)$

Related transforms

Other closely related transforms are sometimes referred to as Dyson transforms. This includes the transform defined by $A_{1}=A\cap (A+\{e\})$, $A_{2}=A\cup (A+\{e\})$, $B_{1}=B\cap (-\{e\}+B)$, $B_{2}=B\cup (-\{e\}+B)$ for $A,B$ sets in a (not necessarily abelian) group. This transformation has the property that

• $A_{1}+B_{1}\subset A+B,A_{2}+B_{2}\subset A+B$
• $|A_{1}|+|A_{2}|=2|A|$, $|B_{1}|+|B_{2}|=2|B|$

It can be used to prove a generalisation of the Cauchy-Davenport theorem.