5
$\begingroup$

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.

  • 1
    In errata [here](http://terrytao.wordpress.com/books/additive-combinatorics/) 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.2012-06-05

1 Answers 1

2

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

  • 1
    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...2012-06-05