Combinatorial expressions and inexpressibility in metafinite structures

Amaldev Manuel

Combinatorial expressions are expressions formed by two kinds of functions, those with a finite arity, and those with a finite image. We prove indefinability results for such expressions of bounded height: Indefinability of functions (i.e., maps from tuples over some domain to some domain) using the pigeonhole principle, and indefinability of problems (i.e., maps from tuples over some domain to \{0,1\}) using reductions to problems of `window-definability'. Window-definable properties are properties that can be described as Boolean combinations of properties over subsets of the inputs. Using combinatorial arguments from Ramsey-theory, namely Hales-Jewett theorem, we show that some problems are not window-definable (for instance GCD of the inputs is 1, or Sum of the inputs modulo some fixed n is 0 etc). These techniques are then used for proving indefinability results over meta-finite structures.

This is based on a joint work with Thomas Colcombet titled 'Combinatorial expressions and lowerbounds’.