PFR

10 Approximate homomorphism version of PFR

Definition 10.1 Additive energy
#

If G is a group, and A is a finite subset of G, the additive energy E(A) of A is the number of quadruples (a1,a2,a3,a4)A4 such that a1+a2=a3+a4.

Lemma 10.2 Cauchy–Schwarz bound
#

If G is a group, A,B are finite subsets of G, then

E(A)|{(a,a)A×A:a+aB}|2|B|.
Proof
Lemma 10.3 Balog–Szemerédi–Gowers lemma
#

Let G be an abelian group, and let A be a finite non-empty set with E(A)|A|3/K for some K1. Then there is a subset A of A with |A||A|/(C1KC2) and |AA|C3KC4|A|, where (provisionally)

C1=24,C2=1,C3=210,C4=5.
Theorem 10.4 Approximate homomorphism form of PFR
#

Let G,G be finite abelian 2-groups. Let f:GG be a function, and suppose that there are at least |G|2/K pairs (x,y)G2 such that

f(x+y)=f(x)+f(y).

Then there exists a homomorphism ϕ:GG and a constant cG such that f(x)=ϕ(x)+c for at least |G|/(2144K122) values of xG.

Proof