Dual functions not approximable by higher-order characters

Dual functions, known in ergodic theory as multiple correlation sequences, are an important but poorly-understood class of functions in additive combinatorics. An example of such a function is one that, given a subset A and element d, counts the number of arithmetic progressions in A with common difference d.

To make progress on an equally poorly-understood probabilistic version of Szemerédi's theorem with random common differences, it has been suggested to determine if dual functions can be decomposed in terms of "higher-order characters" (polynomial phases or nilsequences) plus a small error function. Conjectured bounds for Szemerédi's theorem with random differences were motivated by an apparent expectation that the error can always be taken to have small L_inf norm. It turns out that this is too much to hope for. In this talk we discuss counterexamples to such decompositions, ideas of which originate from coding theory.

This is based on joint works with Ben Green and Farrokh Labib.