Skip to main content
Post Made Community Wiki
Source Link
Boris Bukh
  • 7.8k
  • 1
  • 36
  • 71

Let $G$ and $G'$ be groups. A Freiman homomorphism of order $s$ from a $A\subset G$ to $G'$ is a map $\phi\colon A\to G$ such $$\phi(a_1)\phi(a_2)\cdots\phi(a_s)=\phi(a_1a_2\cdots a_s)$$ for any $s$ (not necessarily distinct) elements $a_1,a_2,\ldots,a_s\in A$. The Freiman homomorphism are the correct notion of equivalence between sets in additive combinatorics. For example, if $A$ and $B$ are Freiman $2$-isomorphic, then $\lvert A+A\rvert=\lvert B+B\rvert$. There are other versions of almost morphisms that arise naturally in combinatorial number theory. For instance, one of the equivalent versions of the polynomial Freiman-Ruzsa conjecture (for $(\mathbb{Z}/2\mathbb{Z})^n$) asserts that if $\phi\colon (\mathbb{Z}/2\mathbb{Z})^n\to (\mathbb{Z}/2\mathbb{Z})^n$ is a map for which $\phi(x+y)-\phi(x)-\phi(y)$ takes only $K$ values, then $\phi$ can be written as $\phi=\phi_0+\psi$ where $\phi_0$ is a genuine linear map, and $\psi$ takes only $K^{O(1)}$ values.

Another interesting example of an `almost morphism', this time in non-algebraic setting, are Lipschitz maps between metric spaces. A true morphism of metric spaces is supposed to preserve distances, but there are very few of them. However, Lipschitz embeddings are much more plentiful, and give rise to beautiful geometry, with many applications (notably in theoretical computer science).