6
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hmmm, I think this is not true in general. For example, let $A\subset \mathbb{F}_2^n$. Then $A$ has a lot of $2$-torsion and thus doesn't have isomorphic copy in any $\mathbb{Q}^d$. I can imagine it is true if $A$ is a subset of $k$-vector space, but I would still like some intuition that deals nicely with the example I stated in my question. $\endgroup$ – user0810 Jun 23 '14 at 9:41
  • $\begingroup$ @Proba: I modified my answer to address your comment. $\endgroup$ – Seva Jun 23 '14 at 10:02
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.