# Freiman homomorphism on generating set

I got stuck in an exercise from Tao and Vu's book Additive Combinatorics. It is ex. 5.3.4. on page 226.

In the following let (Z,+) and (W,+) be two abelian groups and let A $\subset$ Z and B $\subset$ W be two finite subsets.

The definition of a Freiman hom. goes as follows:

Let $k \in \mathbb{N}\setminus \{0\}$. We call a map $\varphi:A\rightarrow B$ a $k$-Freiman homomorphism : $\Leftrightarrow \; \sum_{i=1}^{k}{a_{i}}= \sum_{i=1}^{k}{\tilde{a}_{i}} \implies \sum_{i=1}^{k}{\varphi(a_{i})}= \sum_{i=1}^{k}{\varphi(\tilde{a}_{i})}$ for $(a_{i})_{i = 1}^{k}, (\tilde{a}_{i})_{i = 1}^{k}$ elements in A.

The exercise I'm stucked with is:

Let $\varphi: A \rightarrow B$ be a Freiman $k$-homomorphism for any $k\geq 2$. Suppose further that $A$ generates $Z$ as a group.

$\exists!$ group homomorphism $\psi: Z \rightarrow W$ and $\exists! c \in W$ such that $$\varphi(x)=\psi(x)+c \;\; \forall x \in A.$$

Here are my thoughts so far:

Clearly $c$ should be something like $\varphi(0)$ but in general $0 \notin A.$ I can define a $\tilde{\varphi}$ on $Z$ to be just $\widetilde{\varphi}(z):=\sum{\varphi(a_i)}$ for $z=\sum{a_i} \in Z.$ However, I don't see how I can show that this is well-defined:

If $z=\sum_{i=1}^{n}{a_i}=z=\sum_{i=1}^{m}{\tilde{a}_i}$ and (WLOG) $\; m-n \geq 0\,$ I could add just zeroes on the left side to get the same number of summands and then use the property of the Freiman homomorphism. But as I cannot make sense of $\varphi(0)$ this doesn't help for getting the well-definition.

I also cannot add any other elements from $A$, can I?

The remaining parts of the proof I will be able to do, but I am stuck with this problem. I am very thankful for any hints or comments.

-
In the exercise you want to write $\forall x\in A$ and not $\forall x\in Z$. (Otherwise the statement does not make much sense.) – Martin Sleziak Jun 1 '12 at 12:12
For $A=\{2,3\}$ and $B=\{1\}$ considered as subset of $(\mathbb Z,+)$ there is only one possible map $\phi \colon A\to B$. You get $c=1$ and $\psi=0$. This example should show that "the naive" method will not work, since the map given by $\widetilde\phi(2k+3l)=k+l$ is not well defined; you get both $\widetilde\phi(6)=\widetilde\phi(3+3)=2$ and $\widetilde\phi(6)=\widetilde\phi(2+2+2)=3$. – Martin Sleziak Jun 1 '12 at 12:16
@MartinSleziak Thank you for your comment. Of course it was meant to be A. Also the example is interesting -- Although it is not a counterexample as in the exercise there is a $k$-isomorphism (Which is just a bijective $k$-hom.). But this makes me wonder if injectivity is important. (or even surjectivity? - but I don't think B plays a big role...) – AndreasS Jun 1 '12 at 14:50
The copy of Tao-Vu which is available to me (and also the one linked from the question in google books) has formulation of Exercise 5.3.4 with Freiman homomorphism. – Martin Sleziak Jun 1 '12 at 14:55
In errata here I found: In Exercise 5.3.4, the hypothesis "$0 \in A$” is missing. I guess after this addition the exercise is relatively simple. Perhaps it would be worth mentioning another typo $Z'$ instead of $W$ in the comments to the blog post with errata. – Martin Sleziak Jun 5 '12 at 16:59
show 1 more comment

EDIT:

In errata here I found: In Exercise 5.3.4, the hypothesis "$0 \in A$” is missing. I guess after this addition the exercise is relatively simple. (Basically the solution sketched by OP in the question.)

My original post (before finding the erratum) follows:

I have probably misunderstood something, but I think I have a counterexample. I will post it here; perhaps when someone points out where the mistake is, it might help with the solution. (The other possibility is that the counterexample is indeed correct and some assumption is missing in the exercise.)

Non-uniqueness

This example should give a situation, where $\psi$ and $c$ exists, but they are not determined uniquely.

Consider $A=B=\{1\}$ as subsets of $(\mathbb Z,+)$. Define $\varphi(1)=1$.

We have several choices for $\psi$ and $c$, e.g. $\psi=0$ and $c=1$ or $\psi=id_{\mathbb Z}$ and $c=0$.

Non-existence

Consider $A=\{(1,0),(0,1),(2,3)\}$ as a subset of $\mathbb Z\oplus\mathbb Z$. Consider $B=\{1,2\}$ as a subset of $\mathbb Z$.

Define $\varphi(1,0)=1$, $\varphi(0,1)=1$ and $\varphi(2,3)=2$.

Let us check whether this is a $k$-Freiman homomorphism. We want to find out whether we can obtain some elements of $\mathbb Z \oplus \mathbb Z$ in two different ways as a sum of $(1,0)$, $(0,1)$ and $(2,3)$, such that we have the same number of summands. I.e. we are looking for non-negative integers $a$, $b$, $c$, $a'$, $b'$, $c'$, such that $$a+b+c=a'+b'+c'\\a(1,0)+b(0,1)+c(2,3)=a'(1,0)+b'(0,1)+c'(2,3).$$ By solving this system we find out that it is possible only if $a=a'$, $b=b'$ and $c=c'$. (Solving this system is equivalent to checking whether $(1,0,1)$, $(0,1,1)$ and $(2,3,1)$ are linearly independent.) So there are no non-trivial sums of this form, which means that the condition from the definition of $k$-Freiman homomorphism is fulfilled.

Now if $\varphi=\psi+c$, we have $\psi=\varphi-c$. Using the fact that $\psi$ is a homomorphism we get $\psi(2,3)=2\psi(1,0)+3\psi(0,1)$ which means $$\varphi(2,3)-c=2\varphi(1,0)+3\varphi(0,1)-5c$$ which implies $2-c=5-5c$, i.e.and $4c=3$. So we cannot find $c\in\mathbb Z$.

-
I agree. These are (nice) counterexamples to the uniqueness. I'd say that the problem lies in the formulation of the question. (In the original one from the book there is written $c \in Z'$ instead of $c \in W$) The only thing that I could imagine to be wrong in the statement of the exercise is that Z and W have to be finite (or at least not torsion-free). But I didn't think this through yet. – AndreasS Jun 4 '12 at 14:04
I did not notice that there is $Z'$ and not $W$. In section 5.5 the notation $Z'$ is used for universal ambient group, see Definition 5.37; but this exercise is given before introducing this notion. – Martin Sleziak Jun 4 '12 at 14:30
This ambient group looks promising for this problem. However, would it even make sense that $\varphi(x)=\psi(x)+c$ if $c$ is in $Z'$? I mean the right-handside is a sum in $W$ (we can't embbed $W$ in $Z'$, can we?) So I changed the formulation not thinking that $Z'$ might be of any importance... – AndreasS Jun 4 '12 at 15:18
The definition of universal ambient group depends on $k$, so this might be red herring. Since the question is tagged homework - is there someone you could ask for the clarification of notation? – Martin Sleziak Jun 4 '12 at 15:28
Thanks a lot. You know I had to hand it in some days ago and I just add the assumption $0 \in A$ together with a bad feeling... – AndreasS Jun 5 '12 at 19:38