54 1. Higher order Fourier analysis

Exercise 1.3.11. Obtain a complete solution to the functional equation

(1.29) in the case when |G| is allowed to be divisible by 2 or 3. (This is an

open-ended and surprisingly tricky exercise; it of course depends on what

one is willing to call a “solution” to the problem. Use your own judgement.)

Exercise 1.3.12. Call a map φ: G → R/Z a polynomial of degree ≤ d if

one has ∂h1 . . . ∂hd+1 φ(x) = 0 for all x, h1,...,hd+1 ∈ G. Show that if k ≥ 1

and φ1,...,φk obey the functional equation

φ1(x) + φ2(x + y) + · · · + φk(x + (k − 1)y) = c

and |G| is not divisible by any integer between 2 and k − 1, then φ1,...,φk

are polynomials of degree ≤ k − 2.

We are now ready to turn to the general case of solving equations of

the form (1.27). We relied on two main tricks to solve these equations:

differentiation, and change of variables. When solving an equation such as

(1.29), we alternated these two tricks in turn. To handle the general case,

it is more convenient to rearrange the argument by doing all the change of

variables in advance. For instance, another way to solve (1.29) is to first

make the (non-injective) change of variables

(x, y) := (b + 2c + 3d, −a − b − c − d)

for arbitrary a, b, c, d ∈ G, so that

(x, x+y, x+2y, x+3y) = (b+2c+3d, −a+c+2d, −2a−b+d, −3a−2b−c)

and (1.29) becomes

(1.31)

φ1(b+2c+3d)+φ2(−a+c+2d)+φ3(−2a−b+d)+φ4(−3a−2b−c) = const

for all a, b, c, d ∈ G. The point of performing this change of variables is

that while the φ4 term (for instance) involves all three variables, a, b, c, the

remaining terms only depend on two of the a, b, c variables at a time. If we

now pick h, k, l ∈ G arbitrarily, and then differentiate in the a, b, c variables

by the shifts h, k, l, respectively, then we eliminate the φ1,φ2,φ3 terms and

arrive at

(∂−l∂−2k∂−3hφ4)(−3a − 2b − c) = 0

which soon places us back at (1.30) (assuming as before that |G| is not

divisible by 2 or 3).

Now we can do the general case, once we put in place a definition (from

[GrTa2010]):

Definition 1.3.2 (Cauchy-Schwarz complexity). A system ψ1,...,ψt :

Gd

→

G of aﬃne-linear forms (with linear coeﬃcients in Z) have Cauchy-Schwarz

complexity at most s if, for every 1 ≤ i ≤ t, one can partition [t]\{i} into

s + 1 classes (some of which may be empty), such that ψi does not lie in