Khovanskii's Theorem

Angeliki Koutsoukou-Argyraki 🌐 and Lawrence C. Paulson

September 2, 2022

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.


We formalise the proof of an important theorem in additive combinatorics due to Khovanskii, attesting that the cardinality of the set of all sums of $n$ many elements of $A$, where $A$ is a finite subset of an abelian group, is a polynomial in $n$ for all sufficiently large $n$. We follow a proof due to Nathanson and Ruzsa as presented in the notes “Introduction to Additive Combinatorics” by Timothy Gowers for the University of Cambridge.
BSD License


Theories of Khovanskii_Theorem