A polynomial Freiman-Ruzsa inverse theorem for function fields

A polynomial Freiman-Ruzsa inverse theorem for function fields, Discrete Analysis 2025:24, 11 pp.

A recent result of Gowers, Green, Manners and Tao gave a proof of Freiman’s theorem in $\mathbb F_q^n$ with a polynomial dependence, thereby establishing a conjecture of Marton, also known as the polynomial Freiman-Ruzsa conjecture. The precise statement is that if $A\subset\mathbb F_q^n$ and $|A+A|\leq K|A|$, then there is a subspace $H\subset\mathbb F_q^n$ of size at most $|A|$ and a set $X$ of size at most $K^{O(1)}$ such that $A\subset H+X$.

This paper is about an extension of the above result to the setting of $\mathbb F_q[t]$ – that is, the set of polynomials in a single variable $t$ with coefficients in $\mathbb F_q$. (Throughout this discussion, $q$ is a prime power.) One might object that $\mathbb F_q[t]$ is isomorphic to $\mathbb F_q^{(<\omega)}$, the vector space of finitely supported sequences of elements of $\mathbb F_q$, and therefore that there would be no interesting difference between $\mathbb F_q[t]$ and $\mathbb F_q^n$ from the point of view of the structure of sets with small sumsets. Indeed, that is true, but the twist is that the paper makes a stronger assumption that reflects in a natural way that it is about a space of polynomials. That assumption is that $|A+tA|\leq K|A|$ rather than that $|A+A|\leq K|A|$. (It is a stronger assumption in the sense that by the Ruzsa triangle inequality if $|A+tA|\leq K|A|$, then $|A+A|\leq K^2|A|$.)

A natural example of a set $A$ for which $A+tA$ is not too much larger than $A$ is the set of all polynomials of degree at most $d$, since then $A+tA$ is the set of all polynomials of degree at most $d+1$, which is $q$ times as big (since there are $q$ choices for the coefficient of $t^{d+1}$).

We can also translate this example by fixing a polynomial $P$ and taking $A$ to be the set of all polynomials $PQ$ with $Q$ of degree at most $d$.

A more general example still is obtained as follows. Let $[d]$ denote the set of polynomials of degree at most $d$. Then define a generalized arithmetic progression of rank $k$ in $\mathbb F_q[t]$ to be a set of the form $A=P_1[d_1]+\dots+P_k[d_k]$. Then $A+tA=P_1[d_1+1]+\dots+P_k[d_k+1]$, which has size at most $q^k|A|$, so if $A$ is a generalized arithmetic progression of small rank then $A+tA$ is again not too much larger than $A$.

The main result of this paper is that, as with Freiman’s theorem, generalized arithmetic progressions essentially exhaust all examples of sets $A$ for which $A+tA$ is small. More precisely, if $|A+tA|\leq K|A|$, then there must be a generalized progression $P$ of size at most $K^{O(1)}|A|$ and a set $X$ of size at most $K^{O(1)}$ such that $A\subset P+X$. This is Corollary 1 of the paper, which follows from a result that gives more precise information about the dependence on both $|A+A|/|A|$ and $|A+tA|/|A|$.

The proof of Corollary 1 works by first looking at subspaces $V$ of $\mathbb F_q[t]$ that satisfy the condition $|V+tV|\leq q^k|V|$. Theorem 3 of the paper, which has an elementary and self-contained proof, shows that such a subspace must be a generalized arithmetic progression of rank at most $k$. This result is then combined in a relatively standard way with the resolution of Marton’s conjecture to yield the main result of the paper.

An interesting footnote is that Theorem 3, the main novelty of the paper, formed part of the author’s PhD thesis, submitted in July 2014. However, the consequences that one can derive from it are now much stronger, and potentially considerably more useful for applications, so in a certain sense this is a result whose time has finally arrived.