The amount and type of structure of a function in terms of its small images

Thomas Karam (University of Oxford)

It is well known that if \(G\) is an abelian group and \(A\) is a finite subset of \(G\) which minimises the size of \(A+A\) for a fixed size of \(A\), then \(A\) must essentially be as close as possible to being a coset of some subgroup of \(G\): for instance, if \(G\) is finite then the set \(A\) must be a coset in \(G\) (provided that \(G\) has subgroups with size \(|A|\)), and if \(G = Z\) then the set \(A\) must be an arithmetic progression. One may wish to describe an extension of this phenomenon to more arbitrary functions than addition on abelian groups. If \(X\) is a set and \(F : X \times X \to X\) is a function, then can the structure of \(F\) (to the extent that there is some) be read from the structure of the subsets \(A\) of \(X\) minimising the size of the image \(F(A, A)\) for a fixed size of \(A\), and can the “amount of stucture” of \(F\) be read from how quickly that minimal size grows with the size of \(A\)? We will discuss the progress that has been made in this direction, starting with the results of Elekes-Ronyai, and what remains to be understood.

 Overview  Program