IPM Calendar 
Saturday 8 August 2020   Today  
Events for day: Wednesday 29 July 2020    
           15:30 - 17:30     Mathtematical Logic Weekly Seminar
Cardinalities of Definable Sets in Finite Structures


A theorem of Chatzidakis, van den Dries and Macintyre, stemming ultimately from the Lang-Weil estimates, asserts, roughly, that if $phi(x,y)$ is a formula in the language of rings (where $x,y$ are tuples) then the size of the solution set of $phi(x,a)$ in any finite field $F_q$ (where $a$ is a parameter tuple from $F_q$) takes one of finitely many dimension-measure pairs as $F_q$ and a vary: roughly, for a finite set $E$ of pairs $(mu,d)$ ($mu$ rational, $d$ integer) dependent on $phi$, any set $phi(F_q,a)$ has size roughly $mu.q^d$ for some $(mu,d) in E$. It follows, for example, that there is no single formula $phi(x,y)$ such that in e ...