Intuition for Freiman dimension

Question

Let $A\subset G$ and $B\subset H$ be subsets of abelian groups. We say that a map $f\colon A\to B$ is a Freiman homomorphism if for all $a_1,\dots, a_4\in A$ one has $$f(a_1)+f(a_2)=f(a_3)+f(a_4),\quad\text{whenever }a_1+a_2=a_3+a_4.$$ Denote the set of Freiman homomorphisms between $A$ and $B$ by $\mathrm{Hom}(A,B)$. Fix some field $k$ and notice that if $B$ is a vector space over $k$, then $\mathrm{Hom}(A,B)$ is also a vector space over $k$. We say that $\dim \mathrm{Hom}(A,k)-1$ is the Freimen dimension (or, more precisely, $k$-Freiman dimension) of the set $A$.

Although I have worked with Freimen dimension quite a few times during my research, I must admit I still don't have a satisfactory way of thinking about it.

Basically, there are some examples that seem to be a bit contradictory to the way one usually thinks about the word dimension. One such example is its nonmonotonicity. For example, if $A=\{1,2,4,\dots,\ 2^{10}\}$, then $A$ has Freiman dimension (over $\mathbb{Q}$) equal to $10$, but the set $A\cup\{0\}$ has Freiman dimension $1$.

So basically, my question is: What is a good way of thinking about Freiman dimension?

Answer 1

I would say that in the case where $A$ is a subset of ${\mathbb R}^n$, the original Freiman's definition is very intuitive: the Freiman dimension of $A$ is the largest integer $d$ such that $A$ is isomorphic to a subset of ${\mathbb R}^d$ not contained in a proper affine subspace.

For the specific set $A=\{1,2,4,\ldots,2^{10}\}$, think of a homomorphic mapping $\phi\colon A\to{\mathbb R}^n$. Each pair of points $(\phi(2^i),\phi(2^{i+1}))$ determines a line, and there are no relations between the elements of $A$ which would force any relations between these nine lines. You thus have lots of degrees of freedom, and can map the elements of $A$ wherever you want. However, if you through the point $0$ into $A$, you get nine new relations $2^{i+1}+0=2^i+2^i$, which force $\phi(2^i),\phi(2^{i+1})$, and $\phi(0)$ to all lie on the same line. It follows that actually all the points $\phi(0),\phi(1),\ldots,\phi(2^{10})$ are on the same line, and therefore the dimension of $A\cup\{0\}$ is $1$.

Answer 2

Seva's answer is in my opinion quite nice. I will elaborate on some other things that I have thought of to try to supplement what he has said.

The Freiman dimension of an additive set, $A$, can be determined solely by the collisions of $A$, that is the solutions to $a_1 + a_2 = a_3 + a_4$.

Your first example, $\{ 2^i : 1 \leq i \leq 10\}$ is a Sidon set, that is there are no nontrivial collisions. Any Sidon set as an additive set it is a $(|A|-1)$-dimensional simplex. A property like monoticity cannot hold, as seen for instance by the observation that the integers $\{1 , \ldots , 2^{10}\}$ is a 1-dimensional set.

Another example that is useful to build some intuition is the set $\{0 , 1 , 2 , 3 , 6\}$. If we try to map this set, via a Freiman homomorphism, into $\mathbb{Z}^2$, the relations $1 + 1 = 2 + 0 , 1+2 = 3 + 0$, and $3+3 = 6+0$ force all of these elements to lie on the same line. But, if we consider the set $X = \{0,1,2,3,7\}$, note $7$ is no longer forced to lie on the same line as $0,1,2,3$. Thus the Freiman dimension is at least 2. A theorem of Freiman says that a $d$-dimensional additive set has size at least $(d+1)|A| - d(d+1)/2$, and this set enjoys this bound for $d=2$ (actually $|X+X| = 3|X| -3$). I will mention that here $X$ is in my opinion a sort of "imposter" of a 2-dimensional set in that a hyperplane contains a positive proportion of $X$.

In the presence of torsion, things are slightly different. First, for torsion to even have an impact, you must be able to derive the relation $ma = 0$ for some $a \in A$ from the collisions of $A$. Let $A \subset \mathbb{F}_2^n$ of size at least 2 and let $a,b \in A$ be distinct. By the fact that $a+a = b + b$, we can already see there is 2-torsion. At this point it is hopeless to find a Freiman homomorphism to a torsion free group.

In the opposite vain, the set $\{2^i : 1 \leq i \leq 10\} \subset \mathbb{Z} / (p)$ where $p$ is sufficiently large is still a $(|A|-1)$- dimensional simplex as it is impossible to detect torsion from the collisions.

A rather small subset of $\mathbb{Z} / (p)$, where $p = 2^n -1$ a Mersenne prime, where it is evident from the collisions that there is torsion is $\{0 , 1 , \ldots , 2^{n-1}\}$.

To have a notion of dimension can be useful in increasing the lower bound of the sumset, but I will briefly mention another example of a different flavor. A result (Theorem 3.40 in Tao in Vu's book on additive combinatorics) says roughly that if $P$ is a rank $d$ generalized arithmetic progression, then there is a not much bigger proper generalized arithmetic progression $Q$ such that $P \subset Q$. The key observation is that if $P$ is not a proper generalized arithmetic progression then one can use the relation to show that the proper dimension of $P$ is at most $d-1$ and then use induction on $d$.