6
$\begingroup$

I know that Mazur–Ulam theorem holds for normed linear spaces over $\mathbb{R}$. I wanted to know whether under some "weak" conditions on the map $f$, can we have Mazur-Ulam theorem for a vector space over ${\mathbb{F}_2}$?.

I apologize for being vague about the "weak" condition.

More generally, I am interested in characterizing the isometries of $\mathbb{F}_2 ^n$ with Hamming distance as the metric. Clearly permutation matrices and translations are isometries. But I wanted to know if there are isometries other than these?

Thank you,

Iso

  • 2
    I think there are no more. If I am not mistaken, an isometry of your metric space is the same as an automorphism of the hypercube graph. Preliminary google search gives a [paper by Harary (2000)](http://www.jucs.org/jucs_6_1/the_automorphism_group_of/Harary_F.pdf) on the topic. I do not fully follow the details, but the paper does say that the order of the automorphism group of the hypercube is $2^n n!$. Here $2^n$ is the number of translations and $n!$ the number of permutations, which is checks out with your observation.2011-11-09
  • 1
    Agree with Srivatsan that there are no more in $F_2^n$. I initially thought that in $F_q^n$ and the Hamming metric all you get in addition to the above are all the monomial matrices (those are the ones that usually qualify as isomorphisms in the context of linear codes). Then I realized that any permutation of the alphabet field $F_q$ gives rise to an isomorphism w.r.t. the Hamming metric in $F_q^n$, so for $q>2$ there are plenty of more. I would guess that you get the wreath product $S_q^n\rtimes S_n$ as the group of isometries in that case, but I need to think about a proof.2011-11-09
  • 0
    @Srivatsan: Thanks for the link and the answer :)2011-11-14
  • 0
    @JyrkiLahtonen: I was thinking along similar lines. First of all, the idea seems similar, we can map vectors in $F_q ^n$ to $F_2^n$ such that non zero co-ordinates go to $1$ and $0$ goes to $0$. This map is an isometry. I was trying to show that somehow we can count all the isometries through this projections and some variants of these maps.2011-11-14
  • 0
    @Isomorphism: That mapping is not injective, so cannot be an isometry?2011-11-14
  • 0
    @JyrkiLahtonen: Ya realized it after posting :( It seems to preserve weights and that's it! I am thinking about it. Do you have any leads on how to prove the isometry is exactly the wreath product you mentioned? The idea seems to be permute each co-ordinate among the finite field elements and permute co-ordinates. I am not sure that these are the only isometries. Moreover I am not sure that some that the operations mentioned above are independent...2011-11-16
  • 0
    @Isomorphism: It's a bit fuzzy in my head. Real life duties keep me from devoting enough time to think through a proof. The idea is that if we fix a point $P_0$, and a coordinate position $i$, then there will be $q-1$ points $P_j, j=1,\ldots,q-1$ that differ from $P$ at position $i$. All these $q$ points are at Hamming distance 1 from each other, so the same must hold for their images under an isometry $f$. I would like to conclude from this that the points $f(P_j),j=0,1,\ldots,q-1$ must then agree on all but a single position, call that position $\sigma(i)$. Do this for all $i$....2011-11-16
  • 0
    ... then get a permutation $\tau_i:F_q\rightarrow F_q$ by looking at what is the relation between $x_i(P_j)$ and $x_{\sigma(i)}(f(P_j))$. And then try and prove by induction (w.r.t. Hamming distance from $P$) that all the points must map under the same rule. Scores of details to check, so it will take a while. If you can wade your way through this, go ahead and post it. I'll upvote fer sure!2011-11-16
  • 0
    @JyrkiLahtonen Perhaps you're now in more of a position to promote your comments to an answer?2013-06-07

0 Answers 0